I 1111111111111111 11111 111111111111111 IIIII IIIII IIIII IIIII 1111111111 11111111
`US007266555B 1
`
`c12) United States Patent
`Coates et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,266,555 Bl
`Sep.4,2007
`
`(54) METHODS AND APPARATUS FOR
`ACCESSING REMOTE STORAGE
`THROUGH USE OF A LOCAL DEVICE
`
`(75)
`
`Inventors: Joshua L. Coates, Orinda, CA (US);
`Patrick E. Bozeman, San Francisco,
`CA (US)
`
`(73) Assignee: Intel Corporation, Santa Clara, CA
`(US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by O days.
`
`(21) Appl. No.: 09/733,314
`
`(22) Filed:
`
`Dec. 8, 2000
`
`Related U.S. Application Data
`
`(60) Provisional application No. 60/186,693, filed on Mar.
`3, 2000, provisional application No. 60/186, 774, filed
`on Mar. 3, 2000.
`
`(51)
`
`Int. Cl.
`G06F 17130
`(2006.01)
`(52) U.S. Cl. ............................................. 707/10; 707/4
`(58) Field of Classification Search .............. 707/1-10,
`707/100-102, 200-206; 709/200---203
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,497,422 A
`5,506,984 A
`5,550,986 A
`5,692,155 A
`5,708,832 A *
`5,757,920 A
`5,764,972 A
`
`3/1996 Tysen et al.
`4/1996 Miller
`8/1996 DuLac
`11/1997 Iskiyn et al.
`1/1998 Inniss et al . ................ 709/229
`Misra et al.
`5/1998
`6/1998
`Crouse et al.
`
`5,796,952 A
`5,805,699 A
`5,870,537 A
`5,923,846 A
`5,933,834 A
`5,937,406 A *
`5,978,577 A
`
`8/1998 Davis et al.
`9/1998 Akiyama et al.
`2/1999 Kern et al.
`7/1999 Gage et al.
`8/1999 Aichelen
`8/1999 Balabine et al. ............ 707/100
`ll/ 1999 Rierden et al.
`
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`
`0646858 Al
`
`8/1994
`
`(Continued)
`
`OTHER PUBLICATIONS
`
`MOGUL, RFC0917: Internet Subnets, 1984, ACM, pp. 1-17.
`
`(Continued)
`
`Primary Examiner-loon Hwan Hwang
`(74) Attorney, Agent, or Firm-Caroline M. Fleming
`
`(57)
`
`ABSTRACT
`
`A network storage system includes a virtual file system
`("VFS"), to manage the files of the network storage system,
`and a storage center that stores the files. The VFS and the
`storage center are separated, such that a client accesses the
`VFS to conduct file system operations and the client
`accesses the storage center to upload/download files. The
`client accesses the network storage system through one or
`more storage ports. The storage center includes a plurality of
`distributed object storage managers (DOSMs) and a storage
`cluster that includes a plurality of intelligent storage nodes.
`The network storage system includes additional storage
`centers at geographically disparate locations. The network
`storage system uses a multi-cast protocol to maintain file
`information at the DOSMs regarding files stored in the
`intelligent storage nodes, including files stored in disparate
`storage centers.
`
`23 Claims, 32 Drawing Sheets
`
`Chentlo~I
`FIie System
`2310
`
`Lo~IFlleSy&tem
`Operation
`
`Storag=SystemA=ss
`Prooesses
`2330
`
`" VFS
`
`FoleSys1em
`Translator
`
`""
`
`LocelF1leSyslem
`lntercept,an
`
`""
`
`Stor!l(l;!:~:;sKemel !+----+--'-"'_""_" ~
`""
`
`storage System
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 1
`
`

`

`US 7,266,555 Bl
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`............... 709/213
`
`............... 707/202
`
`6,081,883 A *
`6/2000 Popelka et al. . . . . . . . . . . . . . . . 712/28
`8/2000 Tanaka et al.
`6,108,155 A
`6,128,627 A * 10/2000 Mattis et al.
`11/2000 Chow et al.
`6,148,349 A
`6,170,013 Bl
`1/2001 Murata
`1/2001 Heil et al.
`6,173,374 Bl
`6,236,999 Bl *
`5/2001 Jacobs et al. ................. 707/10
`6,256,673 Bl
`7/2001 Gayman
`6,263,402 Bl
`7/2001 Ronstrom et al.
`6,272,584 Bl
`8/2001 Stancil
`6,304,980 Bl
`10/2001 Beards! ey et al.
`6,314,465 Bl
`11/2001 Paul et al.
`6,324,581 Bl
`11/2001 Xu et al.
`6,327,614 Bl* 12/2001 Asano et al.
`2/2002 Yu
`6,351,775 Bl
`3/2002 Gall et al.
`6,356,929 Bl
`6,360,306 Bl
`3/2002 Bergsten
`6,389,462 Bl
`5/2002 Cohen et al.
`6,393,466 Bl
`5/2002 Hickman et al.
`6,405,201 Bl
`6/2002 Nazari
`6,438,125 Bl
`8/2002 Brothers
`6,442,548 Bl
`8/2002 Balabine et al.
`6,507,883 Bl
`1/2003 Bello et al.
`4/2003 Lewis et al.
`6,553,376 Bl
`6,553,389 Bl
`4/2003 Golding et al.
`6,574,641 Bl
`6/2003 Dawson et al.
`8/2003 Eschelbeck et al.
`6,611,869 Bl
`6,622,247 Bl
`9/2003 Isaak
`6,654,772 Bl
`11/2003 Crow et al.
`6,704,838 B2
`3/2004 Anderson
`6,718,347 Bl *
`4/2004 Wilson ....................... 707/201
`6,782,389 Bl
`8/2004 Chrin et al.
`6,895,418 Bl
`5/2005 Crow et al.
`6,912,548 Bl
`6/2005 Black
`
`6,931,450 B2
`6,948,062 Bl
`2002/00107 57 Al
`2002/0054114 Al
`2002/0083120 Al
`2002/0133491 Al
`2002/0133539 Al
`2004/0078465 Al
`2004/0078466 Al
`2004/0088297 Al
`
`8/2005 Howard et al.
`9/2005 Clapper
`1/2002 Granik et al.
`5/2002 Shuping et al.
`6/2002 Soltis
`9/2002 Sim et al.
`9/2002 Monday
`4/2004 Coates et al.
`4/2004 Coates et al.
`5/2004 Coates
`
`FOREIGN PATENT DOCUMENTS
`
`WO
`WO
`WO
`
`WO99/45491
`WO 01/66707 Al
`WO 01/67707 A2
`
`9/1999
`9/2001
`9/2001
`
`OTHER PUBLICATIONS
`
`Microsoft Press, Computer Dictionary 3rd Editon, 1997, p. 337.
`Kline: Distributed File Systems for Storage Area Networks;
`Advanced Digital Info Corp; 11 pages.
`Apache-SSL: Certificates, Configuration and More Information
`Systems and Technology; University ofWaterloo; Sep. 15, 1998; 16
`pages.
`Schroeder: Implementing Multi-Protocol Authentication/Security
`Systems; Grid (GSI) Secure Socket Layer (X.509 Certificates),
`Kerberos, DCE, and Custom Systems for Secure Distributed Data
`Access; Jul. 19, 1999; 4 pages.
`BEA WebLogic SSL; Server 4.5; 20 pages.
`Certificate to LDAP Mapping in Netscape Servers, Rev 1.2; Aug.
`28, 1997; Structured Arts Technical Notes.
`U.S. Appl. No. 10/367,541 Office action dated Oct. 11, 2006, 1-15.
`U.S. Appl. No. 09/753,332, Office action dated Oct. 19, 2006, 1-26.
`U.S. Appl. No. 09/695,499, Office action, (Dec. 11, 2006), 1-16.
`
`* cited by examiner
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 2
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 1 of 32
`
`US 7,266,555 Bl
`
`-
`
`ts IF)
`.91..!!l
`.c ·(cid:173)o LL
`
`.9! <I)
`u:: 1i,
`-
`(D 0::,
`<D CT g~
`
`E
`Ql
`1n
`>,
`Cl)
`Ql
`Cl
`
`~o om
`u5
`'t:
`1 Ql z
`
`E
`(D -
`-
`0
`IF) ~
`> , - 0
`
`Cl) 5 <O
`.9! (.)
`u::
`
`Ql C
`
`2=-
`0 u IF)
`i5 ._g
`"' ~ Q)
`0 a. ~o
`
`0
`(.)
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 3
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 2 of 32
`
`US 7,266,555 Bl
`
`Wa
`.!ll.!Pi ~
`
`.••• ,,
`
`l'-
`
`Q)
`
`0 .?!
`
`Q)
`(/) 0
`Q) C")
`Ol ..--
`e!
`.8
`(/)
`
`!!!
`0 -o
`(f) '°
`ro~
`"' 0
`
`(/)
`(/)
`..., Q)
`(/)_
`:Ju.
`Q) · (cid:173)
`CT...,
`Q) u
`0::: .!£,
`..c
`a. 0
`~ 0
`I u.
`
`_g
`(/)
`Q) =
`(/) Q)
`:J u.
`CT ....J
`Q) ~
`0::: f-
`a. I
`f- ....
`f- 0
`I.,_
`
`...
`*
`a.
`E
`0 uo
`0
`Gi ~
`(/)
`::J
`-6
`C: w
`
`N
`Q)
`:::s
`C,
`LL
`
`...
`·-
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 4
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 3 of 32
`
`US 7,266,555 Bl
`
`File Upload/Download
`Operations
`
`300
`
`Load Balancing Fabric
`310
`
`I
`
`Distributed Object Storage Managers
`
`320
`
`(cid:127)
`
`(cid:127) (cid:127)
`
`,,
`
`DOSM
`2
`
`, '
`
`DOSM
`"n"
`
`,,
`
`DOSM
`1
`
`'
`
`+
`
`Interconnect Fabric
`330
`
`I
`
`, '
`
`' '
`
`Storage Node
`"n"
`
`340
`
`(cid:127)
`
`(cid:127) (cid:127)
`
`Storage Node
`1
`
`Storage Node
`2
`
`Intelligent Storage Nodes
`
`Figure 3
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 5
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 4 of 32
`
`US 7,266,555 Bl
`
`Start
`
`No
`
`Switching Fabric Selects DOSM
`410
`
`Parse SRL to Extract Certificate and
`Object Fingerprint
`415
`
`Figure 4
`
`Error Message Is
`No
`Sent to Recipient 1 4 1 - - - - - -<
`425
`
`420
`
`No
`
`Broadcast Request To
`Storage Nodes to Locate
`Object
`450
`
`Each Storage Node
`Determines Whether It
`Stores The Object
`460
`
`No
`
`DOSM Obtains Connection
`With Storage Node With
`Object
`435
`
`Object Is Transmitted From
`Storage Cluster to Recipient
`495
`
`>--'~----~
`
`DOSM Establishes Point to
`Point Communications With
`Each Storage Node
`464
`
`Storage Node With Object
`Broadcasts Object
`Identification Information
`for all DOSMs
`470
`
`Yes
`
`r466
`
`End
`
`Perform Failover Operation
`to Obtain Object
`468
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 6
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 5 of 32
`
`US 7,266,555 Bl
`
`Start
`
`Decode SRL To Extract Client
`Identification, Object Fingerprint
`And SRL Certificate
`500
`
`Extract Secret For
`The Corresponding Client
`510
`
`Generate Calculated Certificate
`520
`
`Compare Calculated Certificate
`With SRL Certificate
`530
`
`r s40
`
`No
`
`Yes
`
`Generate Error Message
`To Requester
`550
`
`SRL Authenticates
`560
`
`End
`
`Figure 5
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 7
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 6 of 32
`
`US 7,266,555 Bl
`
`DOSM File Look-up Table
`610
`
`File Id
`file1.MD5
`
`IP Addr
`10.3.100.1
`
`file2.MO5
`
`10.3.098.1
`
`file3.MD5
`
`10.3.050.1
`
`file4.MD5
`
`10.3.100.1
`
`file5.MD5
`
`10.3.098.1
`
`file6.MD5
`
`10.3.050.1
`
`Disk Id
`
`3
`
`1
`
`6
`
`2
`
`1
`
`8
`
`Data Cache
`620
`
`l:C:2J:1i~
`
`•El•:~
`:-.•.•.•,•:-.•:
`Film Snippet
`
`l:l!l:1:~
`•l!l•:~
`
`:-:•:•:·-.-:
`Advertisement
`
`l:m:1:rfc11
`•(cid:143)•:~
`•·········•···
`Film Preview
`
`State Table
`630
`
`Read - Write State of Storage Nodes
`
`Health of Storage Nodes
`
`Load of Storage Nodes
`- Storage Capacity
`- Number of 1/0 Operations
`Per Second
`
`DOSM Server
`600
`
`Figure 6
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 8
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 7 of 32
`
`US 7,266,555 Bl
`
`(/)
`
`g?
`·.:: 0 Ov
`.,,_ ,-..
`0
`
`(/)
`
`•
`•
`•
`
`N
`]2
`.,,_
`0
`
`(/)
`
`]2
`.,,_
`0
`
`(/)
`
`...... e ::::s
`.OJ u:
`
`I!!
`0 u
`g'o
`"2? ;:
`~ e
`
`0..
`
`-..
`
`~ B
`(0 0
`0
`i 't: N
`(l) 2 r,...
`ZE
`
`-
`-
`
`-
`.
`
`~
`Oo
`E<'>
`Q) ,-..
`~
`
`-
`
`-- ~
`
`(
`
`0
`,-..
`tO
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 9
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 8 of 32
`
`US 7,266,555 Bl
`
`Start
`
`VFS Performs Directory Operations for New
`Object File And Transmits Upload Request
`To Storage Cluster
`805
`
`Switching Fabric Selects DOSM
`810
`
`Parse Request to Extract Certificate, Client,
`Directory And Object Information
`820
`
`No
`
`DOSM Communicates Fingerprint, Folder
`Id, Client Information and Meta Data to VFS
`880
`
`No
`
`DOSM Selects Destination Storage Node(s)
`To Store Object File
`840
`
`DOSM Obtains Connection With
`Destination Storage Node(s)
`850
`
`Object File Is Transmitted to Destination
`Storage Node(s)
`860
`
`DOSM Verifies Upload To The Source
`895
`
`Generate and Verify A Fingerprint for the
`Object File
`870
`
`Send Error
`Message to
`Source
`835
`
`Figure 8
`
`End
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 10
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 9 of 32
`
`US 7,266,555 Bl
`
`Start
`
`Create A Temporary File With The Contents Of
`The Object At The Destination Node.
`900
`
`Compute an MOS Hash On The Contents Of The
`Temporary File
`910
`
`DOSM Determines Whether The MOS Hash
`Fingerprint Currently Exists In The Storage
`System
`920
`
`No
`
`Convert Temporary File To
`Permanent File With MOS
`Fingerprint Identification
`960
`
`Delete Temporary File
`940
`
`Increment The Reference
`Count For The Existing
`Fingerprint
`950
`
`End
`
`Figure 9
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 11
`
`

`

`UI = "'""'
`
`UI
`tit
`0--,
`0--,
`'N
`-....l
`d r.,;_
`
`N
`~
`
`0 ....
`0
`....
`.....
`rJJ =(cid:173)
`
`('D
`('D
`
`Figure 10
`
`DOSM "n"
`
`DOSM3
`
`DOSM2
`
`DOSM 1
`
`Data Cache "n"
`
`Data Cache 3
`
`Data Cache 2
`
`Data Cache 1
`
`Video Snippet 2
`
`Advertisement 10
`
`New Film Preview
`
`BLOB A
`
`'
`
`Photos Z
`
`New Film Preview
`
`'.
`
`New Film Preview
`
`Video Snippet 8
`
`Ad 5
`
`•Ir
`
`Photos Y
`
`BLOBX
`
`New Film Preview
`
`'"
`
`~ ...
`
`'?
`('D
`rJJ
`
`-....J
`0
`0
`N
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`310
`
`Load Balancing Fabric
`
`Operations
`
`File Upload/Download
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 12
`
`

`

`UI = "'""'
`
`UI
`tit
`0--,
`0--,
`'N
`-....l
`d r.,;_
`
`N
`~
`
`0 ....
`....
`....
`.....
`rJJ =(cid:173)
`
`('D
`('D
`
`~ ...
`
`'?
`('D
`rJJ
`
`-....J
`0
`0
`N
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`1100
`
`Figure 11
`
`Distributed Directories 1120
`
`Distributed Directory "n"
`
`(cid:127)
`
`(cid:127)
`
`(cid:127)
`
`Distributed Directory 2
`
`Distributed Directory 1
`
`,
`
`, r
`
`j
`
`,
`
`i.
`
`Distributed Directory Manager "n"
`
`Distributed Directory Manager 2
`
`Distributed Directory Manager 1
`
`(cid:127)
`
`(cid:127)
`
`(cid:127)
`
`Distributed Directory Managers 1110
`
`Operation Requests
`
`HTTP Directory
`
`Operation Requests
`
`HTTP Directory
`
`Operation Requests
`
`HTTP Directory
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 13
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 12 of 32
`
`US 7,266,555 Bl
`
`Customer Table
`
`Customer Name Customer Reserved Fields
`
`Customer A
`
`Customer B
`
`[Customer stores data ... ]
`
`[Customer stores data ... ] r 1200
`
`Customer C
`
`[Customer stores data ... ]
`
`Customer D
`
`[Customer stores data ... ]
`
`Customer Id
`
`Folder Id
`
`3
`
`3
`
`3
`
`3
`
`2
`
`100
`
`251
`
`166
`
`Folder Table
`
`Folder Parent Id
`-
`2
`
`Metadata
`
`[Reserved] V
`
`[Reserved]
`
`1210
`
`2
`
`251
`
`[Reserved]
`
`[Reserved]
`
`File Table
`
`Customer Id File Handle Folder Id Folder Parent Id Metadata
`1220
`[Reserved] ~
`[Reserved]
`
`100
`
`100
`
`2
`
`2
`
`3
`3
`
`52.MD5
`
`55.MD5
`
`3
`3
`
`99.MD5
`
`67.MDS
`
`166
`166
`
`251
`
`251
`
`[Reserved]
`
`[Reserved]
`
`Figure 12
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 14
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 13 of 32
`
`US 7,266,555 Bl
`
`Start
`
`No
`
`Parse Request to Extract Certificate, Client
`Information, Operation Code and
`Arguments
`1310
`
`Send Error
`Message To
`Requester
`1325
`
`Access File And Folder
`Tables To Extract File
`Ids And Sub-Folder Ids
`1345
`
`Revise Folder Table
`Entries To Reflect New
`Location
`1355
`
`Add Entry For New
`Folder In Folder Table
`1365
`
`Revise File Table
`Entries To Reflect New
`Location
`1375
`
`Figure 13A
`
`Return Arguments To Requester
`1390
`
`End
`
`(To Figure 13B)
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 15
`
`

`

`UI = "'""'
`
`UI
`tit
`0--,
`0--,
`'N
`-....l
`d r.,;_
`
`N
`~
`
`0 ....
`.... ...
`.....
`rJJ =(cid:173)
`
`('D
`('D
`
`Figure 13B
`
`End
`
`Return Arguments To Requester
`
`1396
`
`1394
`Entry
`
`Table For File
`Metadata In File
`Update Client
`
`1388
`Entry
`
`Table For Folder
`Metadata In Folder
`
`Update Client
`
`1384
`
`In File Table
`
`Add Entry For File
`
`From File Table
`Delete File Entry
`
`1378
`
`1374
`Table
`
`Entry From Folder
`
`Delete Folder
`
`~ ...
`
`'?
`('D
`rJJ
`
`-....J
`0
`0
`N
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`(From Figure 13A)
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 16
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 15 of 32
`
`US 7,266,555 Bl
`
`Start
`
`Perform Validation Using Client Information
`and Certificate From The Request
`1405
`
`Send Error
`Message
`1415
`
`No
`
`Extract MD5 Handler From Database Entry
`1420
`
`Delete File Identification in File Table
`1450
`
`DDM Constructs A Delete SRL And Transmits
`The Delete SRL To The Storage Cluster
`1460
`
`Decrement Reference Count By One
`1440
`
`Storage Cluster Deletes File From Appropriate
`Storage Node
`1470
`
`No
`
`End
`
`Figure 14
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 17
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 16 of 32
`
`US 7,266,555 Bl
`
`..
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 18
`
`

`

`UI = "'""'
`
`UI
`tit
`0--,
`0--,
`'N
`-....l
`d r,r;_
`
`0 ....
`-....J
`....
`.....
`rJJ =(cid:173)
`
`('D
`('D
`
`N
`(,H
`
`~ ...
`
`'?
`('D
`rJJ
`
`-....J
`0
`0
`N
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`Figure 16
`
`Intelligent Storage Nodes 340
`
`Intelligent Storage Nodes 340
`
`"n"
`Node
`Storage
`
`...
`
`2
`
`Node
`Storage
`
`, '
`
`1
`
`Node
`Storage
`
`,,
`
`IPAddr;
`
`IP Addr,'
`
`330
`
`Interconnect Fabric
`
`'
`
`:::
`
`320
`
`Distributed Object Storage Managers
`
`-
`
`IPAddr1'
`
`"nu
`Node
`Storage
`
`, '
`
`...
`
`2
`
`Node
`Storage
`
`"
`
`1
`
`Node
`Storage
`
`'
`
`IP Addr2
`
`330
`
`Interconnect Fabric
`
`::::
`
`320
`
`Distributed Object Storage Managers
`
`IPAddr1
`
`-
`-
`
`310
`
`Load Balancing Fabric
`
`,,
`
`50
`
`Virtual File System
`
`'
`
`-
`
`310
`
`Load Balancing Fabric
`
`"
`
`50
`
`Virtual File System
`
`,,
`-:::
`
`Requests
`
`Upload/Download
`
`C "-'11~ ... ,
`
`s
`
`Requests
`
`Directory Operation
`
`Requests
`
`Upload/Download
`
`1510
`
`VlUld9t: l.,t:mu:n
`
`Requests
`
`Directory Operation
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 19
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 18 of 32
`
`US 7,266,555 Bl
`
`\
`
`Q) C')
`
`iii
`~o
`Cl) l'-z ~
`Cl
`<.)
`
`i::N
`
`~ Q) en
`-fil
`3:o
`:g,~
`0
`i:
`.2!
`i::
`0
`(.)
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 20
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 19 of 32
`
`US 7,266,555 Bl
`
`Start
`
`End-User Computer Generates HTTP Request
`To Content Origin Web Server
`1800
`
`Content Origin Server Returns to End-User
`Computer HTML With Embedded File URL
`1810
`
`End-User Computer Generates HTTP File
`Request To Content Delivery Network
`1820
`
`Yes
`
`CON Generates An HTTP File Request to
`Storage Center
`1830
`
`Storage Center Downloads File To CON Cache
`1840
`
`CON Delivers File To End-User Computer
`1850
`
`End
`
`Figure 18
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 21
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 20 of 32
`
`US 7,266,555 Bl
`
`End-User
`
`Computer 1 ••oo l
`
`/
`
`1920
`
`j.
`
`Client Site
`1910
`
`1J
`
`Content Web Server
`
`1925 ,.
`
`Storage Port
`1930
`
`,,
`
`Storage Center
`1950
`
`Figure 19
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 22
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 21 of 32
`
`US 7,266,555 Bl
`
`Start
`
`Client Receives URL File Request From End-User
`2010
`
`Client Generates Local File System Request
`2020
`
`Retrieve Object File
`From Data Cache
`2040
`
`-
`
`Yes
`
`Object File
`Local?
`
`f 2030
`
`No
`
`.,
`
`Request Object File From Storage Center(s)
`2050
`
`. '
`
`Receive Object File From Storage Center(s)
`2060
`
`-~ , '
`
`Return Object File In Response To Local File System
`Request
`2070
`
`, '
`
`Deliver Object File To End-User In Response To URL
`File Request
`2080
`
`, '
`
`End
`
`Figure 20
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 23
`
`

`

`UI = "'""'
`
`UI
`tit
`0--,
`0--,
`'N
`-....l
`d r.,;_
`
`N
`~
`
`0 ....
`
`N
`N
`.....
`rJJ =- ('D
`
`('D
`
`~ ...
`
`'?
`('D
`rJJ
`
`-....J
`0
`0
`N
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`Storage Center
`
`2160
`
`.. --..
`
`:f(I
`
`2157
`
`2155
`
`Figure 21b
`
`2180
`
`(
`
`Content Web Server
`
`2140
`
`File Operations
`
`!!!!WI
`
`I -Call Storage System APls --
`
`Call(s)
`-Storage System Library
`
`le:llOIII Directory Operations
`
`Software
`
`(2150
`
`Figure 21a
`
`Storage Center
`
`2130
`
`File Operations
`
`torage ort
`
`2110
`P
`
`S
`
`1: rnrectory Operations
`
`I ~(cid:143)
`
`Content Web Server
`
`2100
`
`i uuuuuuul
`
`ODDDOOD
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 24
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 23 of 32
`
`US 7,266,555 Bl
`
`(\
`
`--
`
`-
`-
`
`)
`
`6 ~
`ll. 0
`llJ u5 ~
`Cl <ll N
`~ (U N
`.S Cl
`(/)
`
`.
`.
`.
`
`\
`
`J
`
`:c
`(I) -~
`Cl
`-"'
`1/l
`i5
`
`~
`(I)
`>
`i§
`-"' 1/l
`i5
`
`-
`
`--
`
`~
`0
`(.)
`Clo
`.5 .....
`f/l N
`f/lN
`
`8 e
`
`ll.
`
`t::
`0
`ll.o
`CDo
`ClN
`~N
`
`.s (/)
`
`8
`~
`.!!Z
`..s "O
`-"' iii aU
`l (I) z
`
`B
`"'
`'t:
`.!JN
`E"E
`~ cu
`oU
`l
`Q) z
`
`2l
`"'
`'t:
`.!l~
`..!:: "E
`~"' oU
`l Q) z
`
`~ -
`
`-
`-
`
`en
`~
`~
`Q) 0
`-N
`..: N
`-"'N
`a
`l
`z
`
`Q)
`
`c'.'o
`0 C')
`EN
`~N
`
`~
`
`~
`
`--
`
`[
`
`IO
`N
`N
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 25
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 24 of 32
`
`US 7,266,555 Bl
`
`XML Requests
`
`--
`
`-~
`Directory
`Information
`
`To
`VFS
`
`Client Local
`File System
`2310
`
`Local File System
`Operation
`
`,
`
`Operating System Kernel
`2360
`
`Directory Cache
`2370
`
`a
`
`,,
`
`Storage System Access
`Processes
`2330
`
`h
`
`File System
`Translator
`2320
`
`,r
`
`Local File System
`Interception
`2340
`
`1'
`
`Storage System Kernel
`Processes
`2350
`
`--
`
`Storage System
`Requests
`
`Figure 23
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 26
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 25 of 32
`
`US 7,266,555 Bl
`
`Start
`
`Client Issues Local File Open Request
`2400
`
`Import Local File Request
`2410
`
`Dispatch File System Request to File System Translator
`2420
`
`2430
`_/
`
`No
`
`Additional Directory
`Information Required?
`
`Yes
`
`Return Directory
`Information
`2437
`
`Generate SRL Request To Download
`File From Storage Cluster
`2450
`
`Generate Request to VFS for File
`and Directory Information
`2470
`
`Receive and Cache Object File
`2460
`
`Receive Directory Information
`And Store In Directory Cache
`2480
`
`Transfer Object From Storage Port
`to Client Requester
`2490
`
`Figure 24
`
`End
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 27
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 26 of 32
`
`US 7,266,555 Bl
`
`2600
`
`End-User
`Computer
`2610
`
`Client Site 2620
`
`Content Web Server
`2630
`
`Storage Port
`2640
`
`r 2 6 6 0
`
`--~ ~•:
`
`SRL
`Request
`
`Object File
`Served
`
`Storage Center
`2650
`
`Figure 25
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 28
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 27 of 32
`
`US 7,266,555 Bl
`
`Start
`
`Content Web Server Generates Local File
`System Request for SRL(s) for File(s)
`2700
`
`Storage Port Generates SRL(s) for File(s)
`. 2710
`
`Time Out Parameter Is Added to SRL
`2720
`
`SRL Is Embedded In HTML Web Page
`2730
`
`End-User Issues Web Page Request
`2740
`
`Content Web Server Downloads HTML With
`Embedded SRL
`2745
`
`End-User Generates HTTP Request to Storage
`Center With SRL
`2750
`
`No
`
`Storage Center Downloads
`Object File To End-User
`2770
`
`Figure 26
`
`End
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 29
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 28 of 32
`
`US 7,266,555 Bl
`
`2800
`
`URL
`Request
`
`Client Site 2820
`
`Content Web Server
`2830
`
`File
`Location
`Request
`
`File's
`SRL
`
`Private File Manager
`2840
`
`End-User
`Computer
`2810
`
`HTML With
`Embedded SRL
`
`2860
`
`(
`
`SRL
`Request
`
`Object File
`Served
`
`Storage Center
`2850
`
`Figure 27
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 30
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 29 of 32
`
`US 7,266,555 Bl
`
`Start
`
`End-User Issues URL Request
`2900
`
`Content Web Server Generates A File Location
`Request to File Manager
`2910
`
`File Manager Retrieves File SRL for Content
`Web Server
`2920
`
`Content Web Server Transmits To End-User
`HTML With Embedded SRL
`2930
`
`End-User Generates HTTP Request to Storage
`Center With SRL
`2940
`
`No
`
`Storage Center Generates MD5 Hash on "SRL"
`and Identifies File
`2947
`
`Storage Center Downloads Object File To End(cid:173)
`User
`2950
`
`End
`
`Figure 28
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 31
`
`

`

`UI = "'""'
`
`UI
`tit
`0--,
`0--,
`'N
`-....l
`d r.,;_
`
`N
`~
`
`0
`~
`.....
`rJJ =(cid:173)
`
`('D
`('D
`
`0 ....
`
`~ ...
`
`'?
`('D
`rJJ
`
`-....J
`0
`0
`N
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`Network
`Client Site
`
`r 3060
`
`/
`
`Figure 29
`
`3035
`
`Interface
`Network
`
`Monitoring
`
`3080
`
`Health
`
`...-
`
`-
`
`Storage Port
`
`3020
`
`Passive
`
`+
`
`3025
`
`-Interface
`-Network
`
`Interface
`3030 Network
`
`,,
`
`Monitoring
`Failover
`
`j
`
`Interface
`Network
`
`3D55
`
`IPAddr
`
`3050
`
`Interface
`Network
`
`Monitoring
`
`3070
`
`Health
`
`-;..
`
`f
`
`Storage Port
`
`3010
`
`Active
`
`3045
`
`Interface
`.
`-Network
`
`JI
`
`.,
`
`"
`
`3065
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 32
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 31 of 32
`
`US 7,266,555 Bl
`
`Start
`
`Execute Open File Operation
`3140
`
`Generate XML Request To VFS for File
`Identification
`3150
`
`VFS Returns File Identification
`3160
`
`Storage Port Updates Directory Cache
`3170
`
`Generate SRL Request To Storage Cluster
`3180
`
`Receive File and Update Cache
`3190
`
`End
`
`Figure 30
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 33
`
`

`

`U.S. Patent
`
`Sep.4,2007
`
`Sheet 32 of 32
`
`US 7,266,555 Bl
`
`Start
`
`DOSMs Updates State Table For Storage
`Node Failover
`3220
`
`DOSM Issues Multi-cast Protocol Request
`To Storage Nodes
`3230
`
`Each Storage Node Determines Whether It
`Contains The Requested File
`3240
`
`3245
`
`Yes
`
`Storage Node With File Broadcasts File
`Identification Information
`3250
`
`DOSM Snoops, Through Multi-Cast
`Protocol, To Update File Information
`3260
`
`DOSM Selects Different
`Storage Center
`3247
`
`Figure 31
`
`End
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 34
`
`

`

`US 7,266,555 Bl
`
`1
`METHODS AND APPARATUS FOR
`ACCESSING REMOTE STORAGE
`THROUGH USE OF A LOCAL DEVICE
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`
`This application claims the benefit of U.S. patent appli(cid:173)
`cation Ser. No. 09/695,499, filed Oct. 23, 2000, entitled "A
`Network Storage System."
`The application also claims the benefit of U.S. Provisional
`Application No. 60/186,693, filed Mar. 3, 2000, entitled
`"Method and Apparatus for Implementing AN etwork-Based
`Storage Service", and U.S. Provisional Application No.
`60/186,774, filed Mar. 3, 2000, entitled "Method and Appa(cid:173)
`ratus for Establishing Control and Data Lines To A Storage
`Facility, And API For Supporting Such Lines."
`
`BACKGROUND OF THE INVENTION
`
`2
`To date, only traditional storage solutions from estab(cid:173)
`lished enterprise vendors have been available to a Web site
`developer implementing rich media repositories. One chal(cid:173)
`lenge with adopting today's existing storage technology for
`5 use with the Internet is meeting current and future scalability
`requirements. Today, large scale storage systems only scale
`to a few dozen terabytes. This amount of storage space is
`inadequate for storing substantial amounts of rich media
`objects. For example, if just 10 percent of America on line
`10 ("AOL") users place two 15 minute videos on a personal
`home page, then one petabyte (i.e., 1000 terabytes) of
`storage would be required. Today's enterprise storage sys(cid:173)
`tem architectures camiot support this level of storage capac-
`15 ity.
`In the Internet world, in addition to providing mass
`storage, it is also critically important to provide universal
`access to that storage across the wide area network. The
`content provider, regardless of the location of their content
`20 servers, cache servers, or stream servers, would ideally like
`to provide ubiquitous access to an entire store of rich media
`objects. Current technology, including storage area networks
`and network attached storage technologies, do not provide
`direct access to the wide area network. Only servers located
`25 within the same metropolitan area can directly access these
`types of storage systems.
`Since Internet users are measured in the tens of thousands
`or even millions of users, instead of hundreds of users,
`another challenge in mass storage is the ability to scale
`delivery of media as the demand increases. A true Internet
`based storage system must be able to handle peak loads of
`millions of simultaneous requests from all around the world.
`Traditional storage architectures are designed for supporting
`a few hundred simultaneous requests from the fastest pos(cid:173)
`sible response time to match the speed of the server CPU.
`For the Internet, storage systems must be able to manage
`literally millions of simultaneous downloads at the speed of
`the wide area network. Thus, these traditional storage archi(cid:173)
`tectures are not "impedance matched" with the wide area
`network because the storage devices handle far too few
`simultaneous transactions
`that far exceed the latency
`requirements of the wide area network. In addition, these
`traditional storage architectures are typically implemented
`with expensive disks and expensive connection technolo(cid:173)
`gies.
`Another issue regarding storage of rich media objects is
`the time to market. The time to market is often times a
`crucial requirement for new rich media Web sites. Growth
`rates are measured in terabytes per month. Quickly bringing
`new capacity online becomes a strategic advantage in fast(cid:173)
`moving markets. Typically, with traditional storage solu(cid:173)
`tions, it takes a customer two to six months to integrate a
`fully operational multi-terabytes storage unit with the con(cid:173)
`tent providers site. This start-up time is to slow to meet
`rapidly increasing business demands. Pre-building large
`amounts of excess capacity in anticipation of this demand is
`one tactic to deal with unpredictable demand spikes, but this
`approach is prohibitively expensive.
`Traditional storage architectures have been optimized for
`database and file server applications. The Internet introduces
`a whole new set of demands on storage devices, including
`scalability, global access, user accounts, and rapid deploy(cid:173)
`ment. With the explosive growth in rich media served over
`the Internet over the next several years, this is coming to a
`head. The coming title wave of rich content will surpass the
`capabilities of even the most robust enterprise storage archi-
`
`1. Field of the Invention:
`The present invention is directed toward the field of
`storage, and more particularly toward accessing remote
`storage through use of a local device.
`2. Art Background:
`With the rapid digitization of music, film and photo(cid:173)
`graphs, customer demand is driving the Internet to become
`the most preferred transport mechanism for all forms of
`digital media. Using the Internet, users have instantaneous 30
`worldwide access to their favorite movies, songs, or per(cid:173)
`sonal memorabilia. As the producers and owners of media
`content increasingly use the Internet as a primary method for
`worldwide distribution, the aggregate amount of rich media
`content available over the Internet is increasing at an 35
`extremely rapid rate.
`Not only is the number of rich media objects available
`over the Internet growing exponentially, but the size of the
`media, generally referred to herein as objects, is also dra(cid:173)
`matically increasing. A median Web object is 5 kilobytes 40
`(KB) in size, while the size of a rich media object may be
`100 to 1 million times larger. For example, high-resolution
`digital photographs average 500 KB per picture. Digital
`music runs 3 to 5 megabytes ("MB") per song, and digital
`movies may reach up to 4 gigabytes ("GB") in size.
`As the number of personal computers, digital camcorders,
`digital cameras, and personal digital audio players grow,
`demand for Internet bandwidth to store, share and retrieve
`media files across the Internet also will grow. As the use of
`high-bandwidth digital subscriber lines ("DSL"), cable 50
`modems, and digital broadcast satellite networks gain in
`popularity, which grows the infrastructure of the Internet
`backbone, the demand for using the Internet as a primary
`delivery chamiel for rich media objects also gains in popu(cid:173)
`larity. This development causes a virtuous cycle, where the 55
`installation of broadband networks drives the use of rich
`media devices, which in turn, creates demand for further
`improvements in network bandwidth, and so on.
`The distribution of rich media objects across the Internet
`creates the need for increased storage capacity to store these 60
`rich media objects. As the number of personal media devices
`grows, and the network bandwidth expands, the amount of
`storage media required to store the various MP3 files,
`photographs, films, and video clips will also grow. Also, as
`more storage becomes readily available, more people will 65
`use the Internet to catalog, store, and access their rich media
`objects (e.g., digital photographs of family members).
`
`45
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 35
`
`

`

`US 7,266,555 Bl
`
`3
`tectures. Accordingly, there is a demand to develop new
`paradigms in new ways of designing Internet ready rich
`media storage systems.
`
`SUMMARY OF THE INVENTION
`
`A storage port interfaces a client computer, such as a web
`or application server, to a network storage system. The
`network storage system stores files at one or more storage
`centers, remote from the client site. To gain access to content 10
`stored at the remote storage center, the client computer
`mounts the storage port as a storage device for the client
`computer. The client computer issues local file system
`requests to conduct network storage system operations. In
`response, the storage port translates local file system 15
`requests to network storage system requests. In one embodi(cid:173)
`ment, the local file system and network storage system
`requests include file request and directory operations. The
`storage port processes the network storage system requests
`at the storage port, and accesses, as necessary, the remote 20
`storage center.
`In one embodiment, the storage port further includes a
`data cache and a directory cache. The data cache store