(12) United States Patent
`Karnath et al.
`
`I 1111111111111111 11111 111111111111111 lllll 111111111111111 1111111111 11111111
`US006754696Bl
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,754,696 Bl
`Jun.22,2004
`
`(54) EXTENDED FILE SYSTEM
`
`(75)
`
`Inventors: Vivek P. Karnath, Redmond, WA (US);
`Craig S. Brown, Bothell, WA (US);
`John B. Pence, Renton, WA (US); M.
`Chandra Shekaran, Woodinville, WA
`(US); Thomas G. Lorimor, Redmond,
`WA (US); Thomas R. Firman,
`Bellevue, WA (US); Elizabeth J.
`Gentile, Seattle, WA (US); Keith M.
`Toussaint, Seattle, WA (US)
`
`(73) Assignee: Micosoft Corporation, Redmond, WA
`(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/535,058
`
`(22) Filed:
`
`Mar. 24, 2000
`
`(Under 37 CFR 1.47)
`
`(60)
`
`(51)
`(52)
`
`(58)
`
`(56)
`
`Related U.S. Application Data
`Provisional application No. 60/171,995, filed on Dec. 23,
`1999, and provisional application No. 60/126,094, filed on
`Mar. 25, 1999.
`
`Int. Cl.7 .............................................. G06F 15/167
`U.S. Cl. ....................... 709/213; 709/218; 709/219;
`709/203; 707 /3
`Field of Search ................................. 709/203, 213,
`709/218, 219; 707 /3
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`3,735,360 A *
`5,721,916 A *
`5,893,920 A
`6,243,760 Bl *
`6,260,061 Bl *
`6,269,371 Bl *
`6,578,054 Bl *
`
`5/1973 Anderson et al. ........... 711/149
`2/1998 Pardikar ..................... 707 /201
`4/1999 Shaheen et al.
`6/2001 Armbruster et al. ........ 709/243
`7/2001 Krishnan et al.
`........... 709/213
`7/2001 Ohnishi ....................... 707/10
`6/2003 Hopmann et al.
`. . . . . . . . . . 707 /201
`
`FOREIGN PATENT DOCUMENTS
`
`JP
`WO
`
`10 149310
`WO 98/22881
`
`2/1998
`5/1998
`
`OTHER PUBLICATIONS
`
`Huizinga et al., "Mobile File System Support with Virtual
`Device Drivers," Proceedings of the 1999ACM Symposium
`onApplied Computing, San Antonio, TX, pp. 373-381 (Mar.
`2, 1999).
`Schroeder, et al., "A Caching File System for a Program(cid:173)
`mer's Workstation," Proceedings of the ACM Symposium on
`Operating System Principles, Association for Computing
`Machinery, pp. 25-34 (Dec. 1, 1985).
`Copy of International Search Report from corresponding
`PCT Application No. PCT/US00/07973 mailed Dec. 21,
`2001.
`
`* cited by examiner
`
`Primary Examiner-John Follansbee
`Assistant Examiner-Jinsong Hu
`(74) Attorney, Agent, or Firm-Law Offices of Albert S.
`Michalik, PLLC
`
`(57)
`
`ABSTRACT
`
`A method and system for transparently combining remote
`and local storage to provide an extended file system such as
`a virtual local drive for a computer system client/user, e.g.,
`a user of a pocket sized personal computer or a cable set-top
`box. A client device may load file system object data, storing
`the directories and files remotely, and retrieving the files
`only when required. Via its local storage, the extended file
`system handles unreliable connections and delays. When a
`connection to an extended file system server is present, the
`extended file system provides automatic downloading of
`information that is not locally cached, and automatically
`uploading of information that has been modified on the
`client. Extended file system attributes are employed to
`determine the actual location of file system data, and a
`lightweight protocol is defined to download or upload
`remote data by low-level components that make the remote
`source transparent from the perspective of the application.
`The system scales to large networks as it employs the
`lightweight protocol and establishes a connection only to
`retrieve and submit data.
`
`EP
`
`0 713 183
`
`5/1996
`
`11 Claims, 12 Drawing Sheets
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 1
`
`

`

`i,-
`~
`
`'° a-...
`O'I
`,I;;..
`(It
`-...,l
`_,.a-...
`rJ'J.
`e
`
`'"""' N
`'"""' 0 ....,
`~ ....
`'JJ. =(cid:173)~
`
`~
`
`~
`
`,i;;..
`0
`0
`N
`~N
`N
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`:
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`-----------------------------------------------7
`
`Input
`Screen
`
`36
`
`35
`
`'Display
`Sensitive
`
`Touch
`
`39
`
`Video Driver
`
`21
`
`20
`
`Unit
`
`Processing
`
`22
`
`PROGRAM 31 I
`! XFSDISK 34 ! ~
`
`DATA
`
`MODULES 30
`OTHER PROGRAM
`
`XFS Client
`
`MANAGER
`FILE SYSTEM 32
`
`-
`
`28
`
`-
`
`SYSTEM
`
`OPERATING
`
`PROGRAMS~
`APPLICA 110N
`
`(NV-RAM) 25
`
`---------
`System Memory
`
`______________ I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`1
`
`Interface
`
`Audio
`
`Port
`Serial
`
`Interface
`
`1/0
`
`Infrared
`
`Interface
`Button
`
`Hardware
`
`Interface
`
`37
`
`Detector
`
`42
`
`Device(s)
`External
`
`49
`
`Device(s)
`External
`
`FIG. 1
`
`40_..,
`
`42
`
`BUTTONS! <IJ' \-__
`
`43
`
`45
`
`-----
`
`BIOS ~ 1 I
`
`11
`L __ _
`I
`
`(ROM)
`--------
`
`24
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 2
`
`

`

`i--
`~
`
`,I;;.. °' '° a-...
`
`(It
`-...,l
`_,.a-...
`rJ'J.
`e
`
`'"""'
`N
`0 ....,
`N
`~ ....
`=-
`
`'JJ.
`
`~
`
`~
`
`=
`.
`=
`
`,i;;..
`0
`0
`N
`~N
`N
`
`=
`......
`~ ......
`~
`•
`r:JJ.
`d •
`
`~
`
`74-t=j
`
`76_.
`
`XFS File I A
`
`Server(s)
`
`Internet
`To/ From
`
`Satellite
`Cable/
`
`r-· ----~341
`
`Cable/ JJO I
`
`Modem
`Satellite
`
`Source(s)
`Program
`
`From
`
`I
`54
`
`~}3
`
`Client
`XFS
`
`FIG. 2
`
`62
`
`Device
`Input
`User
`
`./" 56
`
`/ Monitor
`Receiver
`Television
`
`Interface
`Device
`Input
`
`64
`
`I
`
`Application 1 ...
`
`Components
`I
`
`Other
`
`I
`
`58<
`
`Set-Top Box
`
`72 I
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 3
`
`

`

`U.S. Patent
`
`Jun.22,2004
`
`Sheet 3 of 12
`
`US 6,754,696 Bl
`
`C1) C1)
`:=c,
`u. ns
`U) L.
`u..S
`>< U)
`
`-tn
`a., -u L.
`·- a.,
`C: ~
`U) e
`a., >
`
`0.
`
`~
`L.
`
`0 .! a., z
`
`"q'
`r--
`
`E
`(D
`r--
`
`M
`(,D
`r--
`
`r,,
`•
`
`(!) re
`
`(D
`C0
`
`"q'
`C0
`
`-C1) u ·s: a.,
`
`C
`+,I
`C: a.,
`(.)
`
`-0
`
`C0
`
`-M
`
`M
`
`L&. C1)
`
`>< C: a.,
`
`U)
`
`-tn -U) L.
`-(D
`
`r--
`
`N a.,
`u ·s: a.,
`
`C
`+,I
`
`(.)
`
`C: a., ·- ~ ••
`
`C:
`a.,
`
`u ·s: a.,
`
`C
`+,I
`
`C: a., ·-(.)
`
`~ C:
`
`M
`M
`
`N
`M
`M
`
`N
`0
`00
`
`C:
`0
`C0
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 4
`
`

`

`U.S. Patent
`
`Jun.22,2004
`
`Sheet 4 of 12
`
`US 6,754,696 Bl
`
`Client
`
`Application
`+
`11 APls I
`
`..v~~n n.vn..v.•-·•·
`
`.. -•~:,,..-.-,.
`
`•
`
`n
`
`--
`
`80
`
`76
`
`(
`
`FIG. 4
`
`Server
`
`OS Kernel
`
`' .
`
`' '
`File System Manager -
`
`r---
`
`92
`.......
`
`.--
`
`- 32
`
`XFS-SERVER
`102 ___
`_____,.
`
`NAME
`SERVICES
`
`100
`~ PERMISSIONS
`' .
`- MANAGER
`
`'
`' '
`ACCESS
`r--. I ' - . - CONTROLLER
`
`l
`
`1'
`
`74
`
`' '
`
`<
`'-
`_/
`'---
`_/
`'--
`_/
`XFS File
`Storage
`
`Winsock over TCP/IP
`
`' .
`
`l
`
`' ,
`
`33
`XFS-CLIENT
`J
`-..- 98-
`'
`XFSDISK -... - - 34
`
`XFSFSD
`
`•
`'
`XFSCLNT
`
`_ ... -- 96
`
`-
`..-- - 94
`
`•
`' '
`Winsock over TCP/IP
`
`' l
`
`84
`\_
`'
`Network
`-
`
`--
`
`-
`
`'
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 5
`
`

`

`U.S. Patent
`
`Jun.22,2004
`
`Sheet 5 of 12
`
`US 6,754,696 Bl
`
`begin
`Server Enlist
`
`FIG. 5
`
`Send Enlist Request
`Primitive via UDP
`Broadcast
`
`,___ 500
`
`Continue
`to Wait
`
`504
`
`Record IP Address
`Corresponding to
`Each Response
`
`510
`
`end Reso ve equest to
`One of Known XFS-NS's for
`Servers of Type XFS-NS,
`Receive Res onse
`
`Send UDP-Directed (non(cid:173)
`broadcast) Enlist Requests to
`Non-Broadcast-Responding
`XFS-NSes
`
`512
`
`514'-._..---
`
`Save IP Addresses for
`Servers that Respond to
`Directed Enlist requests.
`
`end
`Enlist
`
`Yes
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 6
`
`

`

`U.S. Patent
`
`Jun.22,2004
`
`Sheet 6 of 12
`
`US 6,754,696 Bl
`
`begin
`Server Defect
`
`FIG. 6
`
`Send DefectRequest
`Primitive via UDP
`Broadcast
`
`_,___, 600
`
`Time
`up
`
`606
`
`end
`
`602
`
`Continue
`to Wait
`
`604
`
`Record Each
`Responding XFS-NFS
`
`No
`
`Send UDP-Directed (non(cid:173)
`broadcast) Defect
`Requests to
`Non-Broadcast-Responding
`XFS-NSes
`
`610
`
`Record Each
`Responding XFS-NFS
`
`612
`
`Continue
`Processing
`Requests
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 7
`
`

`

`U.S. Patent
`
`Jun.22,2004
`
`Sheet 7 of 12
`
`US 6,754,696 Bl
`
`FIG. 7
`
`80
`
`<Control>
`
`Enlist
`Enlistment Response
`
`76
`\__. Server
`-
`-
`
`(2)
`
`<Name Resolution >
`Resolve
`Resolve Response (Server List)
`
`Locate
`Locate Response
`
`Establish Secure Channel
`<Session>
`CALL (with User-id, password,
`deviceid, token)
`CALL Response with Token
`
`-
`-
`
`-
`-
`
`-
`
`Directory Request
`Directory Response (Root Directory) -
`
`Hang Up Request
`Hang Up Response
`
`<New Session>
`CALL (with User-id, password,
`deviceid, token)
`CALL Response
`
`XFS Request
`XFS Response
`
`Hang Up Request
`Hang Up Response
`
`-
`-
`
`-
`-
`
`-
`-
`
`-
`-
`
`(4)
`
`(6)
`
`(8)
`
`(10)
`
`(12)
`
`(14)
`
`(16)
`
`(18)
`
`Client
`
`(1)
`
`(3)
`
`(5)
`
`--
`-
`
`-
`-
`
`~
`
`-
`
`(7)
`
`(9)
`
`(11)
`
`(13)
`
`(15)
`
`(17)
`
`-
`-
`
`-
`-
`
`-
`-
`
`-
`-
`
`-
`-
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 8
`
`

`

`U.S. Patent
`
`Jun.22,2004
`
`Sheet 8 of 12
`
`US 6,754,696 Bl
`
`begin
`Client Enlist
`
`FIG. 8
`
`Send Enlist Request
`Primitive via UDP
`Broadcast
`
`,_.___.,, 800
`
`Continue
`to Wait
`
`804
`
`Record IP Address
`Corresponding to
`Each Response
`
`810
`
`Send Resolve Request
`to One of Known
`XFS-NS's for Servers
`of Type XFS-NS,
`Receive Res onse
`
`Save IP Addresses for
`Servers from the Resolve
`Response data
`
`812
`
`814~ Save IP Addresses for
`Servers that Respond to
`Directed Enlist Requests.
`
`end
`
`Yes
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 9
`
`

`

`U.S. Patent
`
`Jun.22,2004
`
`Sheet 9 of 12
`
`US 6,754,696 Bl
`
`begin
`Client Locate
`
`FIG. 9
`
`Select First XFS
`Access Controller
`
`900
`
`Send Locate Request to
`Selected XFS Access
`Controller (via UDP/TCP)
`
`902
`
`904
`
`No
`
`Yes
`
`910
`
`Send Resolve Request
`to One of Known
`XFS-NS's for Servers
`of Type XFS-NS,
`Receive Res onse
`
`end
`
`908
`
`Select Next XFS
`Access
`Controller
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 10
`
`

`

`U.S. Patent
`
`Jun.22,2004
`
`Sheet 10 of 12
`
`US 6,754,696 Bl
`
`[client root]
`
`FIG. 10
`
`-\DIR2 ®
`~ \File0 ®I
`• .
`\DIRi
`
`[client root]
`
`FIG. 11
`
`\DIR1
`
`\DIR2
`
`\DIR3 ®
`• .
`\DIRj ®
`\File1 ®
`.
`\Filek ®@
`~ (cid:127)
`
`•
`
`\DIRi
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 11
`
`

`

`U.S. Patent
`
`Jun.22,2004
`
`Sheet 11 of 12
`
`US 6,754,696 Bl
`
`FIG. 12
`
`[client root]
`
`--\DIR2
`
`___ \DIR3
`
`1-------- \File11 @ _. (9
`-------1 \File12 ®®
`
`•
`•
`--\DIRj @
`
`- - - - \File1 @
`•
`•
`
`~ \Fileo ~
`•
`\DIRj
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 12
`
`

`

`U.S. Patent
`
`Jun.22,2004
`
`Sheet 12 of 12
`
`US 6,754,696 Bl
`
`begin
`Open
`
`FIG. 13
`
`1302
`
`Yes
`
`1304
`
`Retrieve I Update
`Object Data
`From I To
`Remote Store
`
`1314
`
`Retrieve I Update
`Object Data
`From I To
`Remote Store
`
`1316
`
`Update Local
`Storage unless
`Sync-Always
`
`1308
`
`Retrieve I Update
`Object Data
`From I To
`Local Storage
`
`Synchronize
`Remote Store
`
`end
`Open
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 13
`
`

`

`US 6,754,696 Bl
`
`1
`EXTENDED FILE SYSTEM
`
`This application claims benefit of Provisional Nos.
`60/126,094 filed Mar. 25, 1999 and 60/171,995 filed Dec.
`23, 1999.
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to computer
`devices and networks, and more particularly to file storage
`and access by a computer-related device.
`
`BACKGROUND OF THE INVENTION
`
`2
`to act as one or more virtual local drives for a computer
`system client, such as a pocket sized personal computer or
`a set top box. When a connection to an extended file system
`server is present, the extended file system provides auto-
`s matic downloading of information that is not locally cached,
`and automatically uploading of information that has been
`modified on the client. Providing such a remote drive allows
`any client device to load file system objects, storing the
`directories and files remotely, and retrieving the files only
`10 when required. Via its local storage, the extended file system
`handles unreliable connections and delays, particularly with
`small files such as cookies, e-mail text and so forth.
`To provide the extended file system, the client includes
`components that determine via object attributes the remote/
`15 local location of file system data, and when appropriate,
`download or upload the data in a manner that is transparent
`from the perspective of the application. Thus, an application
`makes normal file/operating system application program(cid:173)
`ming calls or the like, and the client components determine
`20 the source and retrieve/update the data appropriately. Data
`that is updated ( e.g., written) locally is automatically syn(cid:173)
`chronized with the remote server.
`Moreover, communication is fast by use of a relatively
`lightweight protocol using straightforward primitives
`25 described herein, and may be made secure via authentication
`and encryption. The system scales to large networks as it
`employs the lightweight protocol and establishes a connec(cid:173)
`tion only to retrieve and submit data.
`Other advantages will become apparent from the follow-
`30 ing detailed description when taken in conjunction with the
`drawings, in which:
`
`Consumer devices such as Pocket PCs or palm-sized and
`handheld computers are limited in their available storage
`space. These devices are capable of loading and executing
`software packages in much the same way as a desktop
`computer, but lack the storage necessary to have several of
`these packages loaded onto the system concurrently along
`with other data needed by a user. Other devices such as cable
`television set-top boxes, satellite receivers and so forth have
`the same lack-of-memory problems.
`As access to the Internet via such devices is being planned
`and to some extent implemented, the lack of storage on the
`devices create problems not seen in home or business
`computers. For example, personal site customizations,
`favorites, saved data such as credit card information, cookies
`and so forth are typically stored on computing devices
`having relatively large hard disks wherein storage is not
`normally an issue. E-mail files, which on a device such as a
`single set-top box, will differ for (possibly multiple) indi(cid:173)
`vidual users of that device. However, saving such data along
`with other needed information would quickly fill up the
`available storage on many devices, and if, for example, a
`relatively large file was downloaded to the device, the saved 35
`data would have to be discarded in order to fit the large file.
`Indeed, in at least one contemporary cable television set-top
`box, only 128 kilobytes are available for persisting user data,
`which is several orders of magnitude smaller than the
`hundreds of megabytes to dozens of gigabytes typically 40
`provided by contemporary personal computers. Contempo(cid:173)
`rary pocket-size devices have somewhat more memory, but
`are still on the order of tens megabytes or less, of which the
`operating system and stored programs consume a consider(cid:173)
`able amount.
`While network shares allow greater amounts of storage to
`be accessed via remote drive connections, their implemen(cid:173)
`tations require constant connection to the network in order
`to access a network share. Among other drawbacks, this
`makes network shares unsuitable for use with the Internet.
`For example, NetBIOS and other drive-sharing (redirector)
`systems currently require constant communication between
`the server and the client. Data is not cached, but instead is
`used directly off the shared file system, and is updated
`immediately. This is not acceptable for Internet-based file
`sharing, as the Internet is unreliable, and can be susceptible
`to long delays in transmission. The NetBios service and
`SMB protocol are also point-to-point, relatively heavy, and
`do not scale well to large numbers of remote users and
`multiple servers. Other existing services are unable and/or
`impractical to provide a solution to these low memory
`problems.
`
`45
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram representing one exemplary
`computer system into which the present invention may be
`incorporated;
`FIG. 2 is a block diagram representing a television set-top
`box including a computer system into which the present
`invention may be incorporated;
`FIG. 3 is a block diagram generally representing an
`extended file system installation in accordance with one
`aspect of the present invention;
`FIG. 4 is a block diagram generally representing logical
`components in a client and server for remotely accessing
`objects in accordance with in accordance with one aspect of
`the present invention;
`FIG. 5 is a flow diagram generally representing logical
`steps when enlisting a server to participate in an extended
`50 file system in accordance with one aspect of the present
`invention;
`FIG. 6 is a flow diagram generally representing logical
`steps when defecting a server from participation in an
`extended file system in accordance with one aspect of the
`present invention;
`FIG. 7 is a representation of communications between a
`client device and a server to initiate access to remote objects
`and perform file system-related operations thereto in accor(cid:173)
`dance with one aspect of the present invention;
`FIG. 8 is a flow diagram generally representing logical
`steps when enlisting a client to participate in an extended file
`system in accordance with one aspect of the present inven(cid:173)
`tion;
`FIG. 9 is a flow diagram generally representing logical
`65 steps when a client attempts to locate a selected server for
`accessing an extended file system in accordance with one
`aspect of the present invention;
`
`55
`
`60
`
`SUMMARY OF THE INVENTION
`
`Briefly, the present invention provides a method and
`system for transparently combining remote and local storage
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 14
`
`

`

`US 6,754,696 Bl
`
`3
`FIGS. 10---12 are representations of how the client com(cid:173)
`ponents access local objects locally and remote objects
`remotely in accordance with one aspect of the present
`invention; and
`FIGS. 13 is a flow diagram generally representing logical
`steps when determining the source of an object in accor(cid:173)
`dance with one aspect of the present invention.
`
`DETAILED DESCRIPTION
`
`Exemplary Operating Environments
`
`FIG. 1 and the following discussion are intended to
`provide a brief, general description of one suitable comput(cid:173)
`ing environment in which the invention may be imple(cid:173)
`mented. Although not required, the invention will be
`described in the general context of computer-executable
`instructions, such as program modules, in one alternative
`being executed by a pocket-sized computing device such as
`a personal desktop assistant. Generally, program modules
`include routines, programs, objects, components, data struc(cid:173)
`tures and the like that perform particular tasks or implement
`particular abstract data types.
`Moreover, those skilled in the art will appreciate that the
`invention may be practiced with other computer system
`configurations, including hand-held, laptop or desktop per(cid:173)
`sonal computers, mobile devices such as pagers and
`telephones, multi-processor systems, microprocessor-based
`or programmable consumer electronics including a cable or
`satellite set-top box (FIG. 2), network PCs, minicomputers,
`mainframe computers and the like. Part of the invention is
`also practiced in distributed computing environments where
`tasks are performed by remote processing devices that are
`linked through a communications network. In a distributed
`computing environment, program modules may be located
`in both local and remote memory storage devices, as
`described below.
`With reference to FIG. 1, one exemplary system for
`implementing the invention includes a general purpose
`computing device in the form of a pocket-sized personal
`computing device 20 or the like, including a processing unit
`21, a system memory 22, and a system bus 23 that couples
`various system components including the system memory to
`the processing unit 21. The system bus 23 may be any of
`several types of bus structures including a memory bus or
`memory controller, a peripheral bus, and a local bus using
`any of a variety of bus architectures. The system memory
`includes read-only memory (ROM) 24 and random access
`memory (RAM) 25, typically non-volatile RAM (e.g.,
`battery-backed up) in a pocket-sized personal computing 50
`device. A basic input/output system 26 (BIOS), containing
`the basic routines that help to transfer information between
`elements within the hand-held computer 20, such as during
`start-up, is stored in the ROM 24.
`A number of program modules are stored in the ROM 24 55
`and/or RAM 25, including an operating system 28 (such as
`Windows® CE), one or more application programs 29, other
`program modules 30, program data 31 and a file system
`manager 32.
`In accordance with one aspect of the present invention, a
`local memory is used as part of a virtual local drive is
`provided by an XFS client component 33, which includes an
`XFS Ramdisk manager and storage 34 (XFSDISK), and
`other components (described below). A user may enter
`commands and information into the hand-held computer 20
`through input devices such as a touch-sensitive display
`screen 35 with suitable input detection circuitry 36. Other
`
`10
`
`4
`input devices may include a microphone 37 connected
`through a suitable audio interface 38 and physical
`(hardware) or a logical keyboard (not shown). Additional
`other devices (not shown), such as LED displays or other
`5 peripheral devices controlled by the computer, may be
`included. The output circuitry of the touch-sensitive display
`35 is also connected to the system bus 23 via video driving
`circuitry 39. In addition to the display 35, the device may
`include other peripheral output devices, such as at least one
`speaker 40 and printers (not shown).
`Other external input or output devices 42 such as a
`joystick, game pad, satellite dish, modem or the like
`(satellite, cable or DSL interface), scanner or the like may be
`connected to the processing unit 21 through an RS-232 or
`the like serial port 40 and serial port interface 41 that is
`15 coupled to the system bus 23, but may be connected by other
`interfaces, such as a parallel port, game port or universal
`serial bus (USE). Such devices may also be internal. The
`hand-held device 20 may further include or be capable of
`connecting to a flash card memory (not shown) through an
`20 appropriate connection port ( e.g., slot) 43 and interface 44.
`A number of hardware buttons 45 such as switches, buttons
`(e.g., for switching application) and the like may be further
`provided to facilitate user operation of the device 20, and are
`also connected to the system via a suitable interface 46. An
`25 infrared port 47 and corresponding interface/driver 48 are
`provided to facilitate communication with other peripheral
`devices 49, including other computers, network connection
`mechanism (e.g., modems or the like), printers, and so on
`(not shown). It will be appreciated that the various compo-
`30 nents and connections shown are exemplary and other
`components and means of establishing communications
`links may be used.
`Turning to FIG. 2 of the drawings, there is shown an
`alternate computer system into which the present invention
`35 may be incorporated, implemented in a set-top box 54
`connected to a television receiver/monitor 56. In FIG. 2, an
`application 58 which may, for example, provide a user
`interface configured to control set-up, parental control,
`tuning, timed operation, and/or the like is provided. The
`40 application may also provide a user interface via which a
`user is able to access the Internet, and may include a
`browser, although as is known, the browser may be inte(cid:173)
`grated into the operating system 60 of the set-top box 54. A
`user interacts with the application 58 and/or operating
`45 system 60 (such as Windows® CE) via a user input device
`62 (such as an attached keypad, infrared remote control
`and/or hard-wired keyboard) and suitable device interface
`64.
`As is known, one of the functions of a contemporary
`set-top box 54 is to output to the receiver/monitor 56
`television programming and Internet content received from
`a provider 66. To this end, some signal processing mecha(cid:173)
`nism 68 or the like is generally provided, such as including
`one or more splitters, filters, multiplexers, demultiplexers,
`mixers, tuners and so forth as required to output appropriate
`video to the receiver/monitor 56, and to both output and
`input Internet-related data via a cable/satellite modem 70. Of
`course, consumer satellite dishes only receive content, and
`thus in a satellite system an additional mechanism (e.g.,
`60 telephone line, not shown) is required to output data to the
`provider 66. Other components 72 such as to display closed(cid:173)
`captioning, allow parental control, provide on-screen pro(cid:173)
`gram guides, control video recorders and so forth may be
`provided as is also known. In any event, these functions of
`65 set-top boxes are known, and are not described herein for
`purposes of simplicity, except to the extent that they relate
`to the extended file system of the present invention.
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1032, p. 15
`
`

`

`US 6,754,696 Bl
`
`5
`Extended File System
`
`In accordance with one aspect of the present invention, to
`provide access to remote client-owned objects (directories
`and/or files therein) maintained in remote storage 74 by one
`or more XFS file servers 76, the set-top box includes (e.g.,
`in system memory) an XFS client 33 comprising a number
`of components (described below) including the XFS Ram(cid:173)
`disk manager/virtual local drive 34. A file system manager
`32 is also provided, as described below. For example, in the
`Windows® CE operating system, a suitable file system
`manager is known as "FSDMGR."
`An exemplary extended file system (XFS) installation is
`represented in FIG. 3, and typically comprises a large
`number (e.g., millions) of client devices 801-80n (for
`example, the pocket computing device 20 or the set-top box
`54). The client devices 801-80n are capable of connecting to
`one or more of the servers (76c76m in FIG. 3) over a
`network 84 via a service provider 86. The servers 76 1-76m
`participate in XFS as name servers, access controllers and
`permission managers, or a combination of access controller,
`permission manager and name server as described below
`with reference to FIG. 4.
`The servers 76c76m (more particularly the access
`controllers) point to a common remote file system for storing
`files in one or more XFS storage devices 74 implemented
`using DFS shares. DFS is a feature of Windows® 2000 ( or
`Windows® NT®) that provides file replication (used for
`providing redundancy of data) and load balancing for a file
`system. In one preferred implementation, the remote file
`system is the Windows® NTFS file system, which among
`other benefits, is considered secure. As will be understood,
`however, the XFS file system of the client is independent of
`the remote file system/server configuration, and thus virtu(cid:173)
`ally any operating and/or file system (e.g., UNIX, FAT,
`FAT32) or combination thereof that works with the server(cid:173)
`side storage media 74 will suffice for purposes of the present
`invention.
`In the set-top box implementation, the client devices 54
`will normally be physically connected to the servers
`76 1-76m at all times via the cable/satellite modem 70
`therein. Indeed, since broadband is in use, remote files may
`be quickly accessed by the client, as described below, even
`though logical connections are preferably made on a per(cid:173)
`access basis. In keeping with the present invention, however,
`the client device provides local storage for caching some of
`the data maintained at the remote storage device 74, thereby
`enabling operation without a physical connection. Synchro(cid:173)
`nization may be performed at some later time or on demand.
`As can be appreciated, this is particularly useful with client
`devices such as pocket-sized computing devices (e.g., 20),
`digital cameras, and so forth wherein a physical connection
`is occasional. Moreover, local caching is generally valuable
`when dealing with Internet content, as even when physically
`connected to a provider, the Internet is unreliable and can be
`susceptible to long delays in transmission and also helps in
`optimizing bandwidth utilization.
`As generally represented in FIG. 4, the extended file
`system (XFS) comprises the XPS-Client portion 33 and an
`XPS-Server portion 92, which together generally include the 60
`XFS Ramdisk manager/virtual local drive 34 and other
`components 94--102 (described below). Note that the vari(cid:173)
`ous components 94--102 are logical components, and it is
`likely that several of the components may be integrated into
`and handled by a single program. For example, the XFS 65
`server portion 92 may comprise a single physical component
`servicing the requests for its logical components. For
`
`30
`
`6
`extremely large installations, however, it may be desirable
`for the components to be implemented separately for scal(cid:173)
`ability reasons. Similarly, the virtual local drive of XFS
`(managed by the XFSDISK 34) may be at any physical or
`5 virtual location or locations in system memory, not neces(cid:173)
`sarily adjoining or within the memory allocated to the other
`XFS client components.
`The XFSDISK RAMdisk manager 34 that provides the
`virtual local drive is a complete, thread-safe implementation
`10 of a stream interface driver (as defined in the "Windows®
`CE DDK," available from Microsoft® Corporation,
`Redmond, Wash.) The XFSDISK 34 is loaded at boot time,
`and is configured based on information provided in the
`system registry. The XFSDISK 34 is capable ofloading a file
`15 system device on itself, thereby appearing as an actual folder
`off of the root folder of a hierarchically organized file
`system. To provide accessible memory, the XFSDISK 34
`creates a specified number of heaps of a specified size and
`then "stitches" them together to give the appearance of a
`20 single, contiguous, addressable block of memory which
`serves as a local cache of the virtual local drive. This address
`space is shared by the threads and processes which access
`XFSDISK, either through the associated file system device
`( e.g., the file system manager 32) or by directly reading from
`25 or writing to the disk locations. XFSDISK serves as the local
`cache for the remote file system of the present invention.
`Two XPS-Client 33 components include the XFS Client
`Interface (XFSCLN1) 94 and the XFS File System Driver
`(XFSFSD) 96. The XFS Client Interface 94 is the interface
`to the XFS Server 92, and is responsible for translating file
`system requests into XFS primitives (XFS network
`functions) and marshaling the primitives across to the server.
`As will be described below, the XFS Client Interface
`(XFSCLNT) 94 performs initialization operations.
`The XFS File System Driver (XFSFSD) 96 is an install-
`able file system driver, which in one implementation is
`modeled after the well-documented FAT file system. In
`keeping with the present invention, a remotely maintained
`40 file system is presented as a local file system through
`XFSFSD 96. As the local disk 33 fills up, the XFSFSD 96
`implements a Least Recently Used (LRU) algorithm to make
`space available. As described below, if it is not possible to
`make space, the files presented as available in the local file
`45 system are marked as remote and for those files, the file
`system essentially behaves like a redirector. The local cache
`of files is thus intelligently managed.
`The XFS server portion 92 includes an XFS Access
`Controller 98, an XFS Permissions manager 100, and an
`50 XFS Name Resolution Manager (name services module)
`102. The access controller 98 is responsible for receiving
`primitives from the client and taking actions on them,
`although when the access controller 98 receives name-server
`primitives, it routes them to name services module 102. As
`55 described below, the access controller 98 translates primi(cid:173)
`tives to appropriate actions to be taken on the file system and
`sends the response back to the client.
`The Permissions manager 100 is responsible for authen(cid:173)
`ticating clients and users on the clients. Having authenti(cid:173)
`cated the client, and a specified user, the permissions man(cid:173)
`ager 100 provides access to the private folder for a given
`client. This is done as a part of PRIMITIVE_CALL,
`described below. The permissions manager 100 may use