as) United States
`a2) Patent Application Publication (10) Pub. No.: US 2005/0060316 Al
`(43) Pub. Date: Mar. 17, 2005
`
`Kamathet al.
`
`US 20050060316A1
`
`(54) EXTENDED FILE SYSTEM
`
`(75)
`
`Inventors: Vivek P. Kamath, 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); ThomasR. Firman,
`Bellevue, WA (US); Elizabeth J.
`Gentile, Seattle, WA (US); Keith M.
`Toussaint, Seattle, WA (US)
`
`Correspondence Address:
`LAW OFFICES OF ALBERT S. MICHALIK,
`PLLC
`704 228TH AVENUE NE
`SUITE 193
`SAMMAMISH, WA 98074 (US)
`
`(73) Assignee: Microsoft Corporation, Redmond, WA
`
`(21) Appl. No.:
`
`10/819,624
`
`(22)
`
`Filed:
`
`Apr. 7, 2004
`
`Related U.S. Application Data
`
`(63) Continuation of application No. 09/535,058,filed on
`Mar. 24, 2000, now Pat. No. 6,754,696.
`
`(60) Provisional application No. 60/126,094,filed on Mar.
`25, 1999. Provisional application No. 60/171,995,
`filed on Dec. 23, 1999.
`
`Publication Classification
`
`(51) Ute C7 caccccssssssssssnssssssesnssnssstnesve GO0G6F 17/30
`(52) US. Che acssssssstssssesistsntnssesiststtstsntsnssee 707/9
`
`ABSTRACT
`(57)
`A method and system for transparently combining remote
`and local storage to provide an extendedfile system such as
`a virtual local drive for a computer system client/user, e.g.,
`a user of a pocket sized personal computeror a cable set-top
`box. A client device may loadfile 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.
`
`804
`
`Client Device,
`
`
`
` 33,
`XFSClient
`
`
`Service
`Provider(s)
`
`
`
`Client Device,
`
`
`
`XFS
`
`33
`
`
`
`=I
`
`
`Storage
`
`Xx
`Server(s)
`
`XFSFile
`
`Google Exhibit 1024
`Google Exhibit 1024
`Google v. Ericsson
`Google v. Ericsson
`
`

`

`Patent Application Publication Mar. 17,2005 Sheet 1 of 12
`
`US 2005/0060316 Al
`
`se
`
`9¢
`
`yonol,
`
`BAIISUaS
`
`Udal9S
`
`ez
`
`ov
`
`jeusa}xyed|
`
`
`NoneYa5SVNVIN
`
`
`_—OWNwvopnyHodolluoyngpies0€SATINGOW
`arPvscea
`
`
` —oboy9solaiLYOd1dOdbe(INOW)|lVTIGSyuVYSNI
`Aejdsiq\zBuisse20ldSE(wrve-An)
`
`|y|TeWWuDOud
`(s)aaiaaq(s)aolasqb9/4
`
`
`8ewuelldSAX
`
`
`
`
`.[elaspoleajuyauempieHysel4WVeSOddYSHLO
`
`INNyunNOLLW9IIddv
`viv
`
`
`
`a9e}9}u|a0Rpla}Uu|@oeplazuyaoRja}U|
`JOAO8PIAgzSWVuD0Nd
`4\iy|SNOLLNa|~*?
`
`
`
`Aiowapwaysks
`
`ONILVesdO
`
`WALSAS
`
`WALSAS315
`
`
`
`
`
`
`
`
`

`

`Patent Application Publication Mar. 17,2005 Sheet 2 of 12
`
`US 2005/0060316 Al
`
`wol4/OL
`
`yOuUs9}U|
`
`SPIES/81989
`
`JOP!AOld
`
`atldSAX
`
` Bulssas0ig
`
`(s)4aA19SjeuBis
`
`
`€Old
`
`UOISIAD]OL
`
`9SJOAIBIOY490xogdo-as
`
`
`JOWUOW/sjusuodwoy
`
`wol4
`
`jndu|
`
`ad1A0q
`
`aoeja}U|
`
`uonesjddy
`
`(s)aoinosg
`
`weibold>
`
`wash
`
`saBeuew
`
`syaeS/31489
`
`wepow
`
`
`
`
`
`

`

`Patent Application Publication Mar. 17,2005 Sheet 3 of 12
`
`US 2005/0060316 A1
`
`86
`
`FIG.3
`
`XFSFile
`
`Storage
`
`of=cs
`
`no
`a.
`
`84
`
` ClientDevice,
`ClientDevice,,
`ClientDevices
`
`

`

`Patent Application Publication Mar. 17,2005 Sheet 4 of 12
`
`US 2005/0060316 A1
`
`Application
`
`XFS-SERVER
`
`File System Manager
`
`Winsock over TCP/IP
`
`XFSDISK
`
`XFSFSD
`
`XFSCLNT
`
`Winsockover TCP/IP
`
`

`

`Patent Application Publication Mar. 17,2005 Sheet 5 of 12
`
`US 2005/0060316 A1
`
`begin
`
`FIG. 5
`
`Send Enlist Request
`Primitive via UDP
`Broadcast
`
` 500
`
`
`
`Continue
`
`
`to Wait
`
`Record IP Address
`
`
`506
`
`Corresponding to
`
`
`
`
`Time
`Each Response
`
`
`
`Ended with
`
`
`Responses
`Yes
`=0
`
`510
`?
`
`No
`
`
`Send Resolve Requestto
`
`
`One of Known XFS-NS'sfor
`No. of
`
`Servers of Type XFS-NS,
`
`
`ervers = No:
`Receive Response
`
`
`Reported from
`
`Enlist
`
` Send UDP-Directed (non-
`
`broadcast) Enlist Requests to
`
`
`Non-Broadcast-Responding
`
`XFS-NSes
`
`
`
`
`
`Save IP Addressesfor
`
`Directed Enlist requests.
`Servers that Respond to
`
`
`508
`
`esponse
`
`
`
`

`

`Patent Application Publication Mar. 17,2005 Sheet 6 of 12
`
`US 2005/0060316 A1
`
`begin.
`
`FIG. 6
`
`Send DefectRequest
`Primitive via UDP
`
`600
`
`Continue
`to Wait
`oma
`
`j
`Time
`up
`
`Record Each
`Responding XFS-NFS
`
`Broadcast
`
`
`
`
`Numberof
`FS-NS Servers =
`Known Number
`
`Send UDP-Directed (non-
`broadcast) Defect
`Requests to
`Non-Broadcast-Responding
`XFS-NSes
`
`606
`
`Yes
`
`
`
`
`
`610
`
`Record Each
`Responding XFS-NFS
`
`
`612
`Continue
`
`Processing
`Requests
`
`
`

`

`Patent Application Publication Mar. 17,2005 Sheet 7 of 12
`
`US 2005/0060316 A1
`
`FIG. 7
`
`Client
`
`<Control>
`
`
`
`(1)|Enlistment Response (2)
`
`Enlist
`
`<NameResolution >
`
`3(3)
`
`Resolve
`
`Resolve Response (ServerList)
`
`(4)
`
`Locate
`Locate Response
`
`Establish Secure Channel
`
`(13)
`
`(7)
`(9)
`
`(11)
`
`(15)
`
`(17)
`
`<Session>
`CALL(with User-id, password,
`deviceid, token)
`
`CALL Response with Token
`Directory Response (Root Directory)
`
`Directory Request
`
`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
`
`(8)
`(10)
`
`(12)
`
`(14)
`
`(16)
`(18)
`
`

`

`Patent Application Publication Mar. 17,2005 Sheet 8 of 12
`
`US 2005/0060316 A1
`
`FIG. 8
`
`
`Send Enlist Request
`Primitive via UDP
`Broadcast
`
`800
`
`
`
`
`
`
`Continue
`
`
`to Wait
`
`Record IP Address
`
`
`806
`
`
`Corresponding to
`
`Each Response
`Time
`
`
`
`Ended with
`Responses
`=0
`
` 810
`?
`
`
`
`Yes
`
`
`
`Send Resolve Request
`to One of Known
`
`XFS-NS's for Servers
`
`of Type XFS-NS,
`—
`Receive Response
`
`
`
`808
`
`No. of
`
`ervers = No:
`
`
`Reported from
`
`Enlist
`
`
`Response
`
`Save IP Addressesfor
`
`
`Servers from the Resolve
`
`Responsedata
`
`
`
`Save IP Addressesfor
`
`Servers that Respond to
`Directed Enlist Requests.
`
`
`

`

`Patent Application Publication Mar. 17,2005 Sheet 9 of 12
`
`US 2005/0060316 Al
`
`begin
`Client Locate
`
`FIG. 9
`
`Select First XFS
`Access Controller
`
`900
`
`
`Send Locate Requestto
`Selected XFS Access
`Controller (via UDP/TCP)
`
`
`
`
`Response
`
`
`
`_ No
`
`(Timeout)
`
`
`Another
`
`Access
`
`
`Controller
`?
`,
`
`
`
`
`Select Next XFS
`
`
`Access
`
`
`Controller
`
`Yes
`
`910
`
`
`
`
`Send Resolve Request
`to One of Known
`XFS-NS's for Servers
`of Type XFS-NS,
`Receive Response
`
`
`
`

`

`Patent Application Publication Mar. 17,2005 Sheet 10 of 12
`
`US 2005/0060316 A1
`
`110,
`
`FIG. 10
`
` [client root]
`110)
`
`

`

`Patent Application Publication Mar. 17,2005 Sheet 11 of 12
`
`US 2005/0060316 A1
`
`FIG. 12
`
`cient roo
`fore
`
`wy,
`
`ie @]+ ©
`
`\DIRj ®)
`
`

`

`Patent Application Publication Mar. 17,2005 Sheet 12 of 12
`
`US 2005/0060316 A1
`
`FIG. 13
`
`
`
`
`
`Retrieve / Update
`Object Data
`From /To
`Remote Store
`
`Object =
`Remote
`?
`
`
`1308
`
`
`reobiect 5peste
`Retrieve / Update
`
`
`
`
`
`From / To
`Local Storage
`
`Object Data
`From / To
`Remote Store
`
`
`Update Local
`1312
`
`Storage unless
`
`Sync-Always
`
`
`
`Synchronize
`Remote Store
`
`

`

`US 2005/0060316 Al
`
`Mar. 17, 2005
`
`EXTENDED FILE SYSTEM
`
`FIELD OF THE INVENTION
`
`[0001] The present invention relates generally to computer
`devices and networks, and moreparticularly to file storage
`and access by a computer-related device.
`
`BACKGROUND OF THE INVENTION
`
`[0002] 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 concur-
`rently 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.
`
`[0003] 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 homeor 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-
`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 downloadedto the device, the saved
`data would have to be discarded in order tofit 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
`provided by contemporary personal computers. Contempo-
`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 consumea consider-
`able amount.
`
`[0004] While network shares allow greater amounts of
`storage to be accessed via remote drive connections, their
`implementations 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 communica-
`tion 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 SMBprotocolare 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.
`
`SUMMARYOF THE INVENTION
`
`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 pro-
`vides automatic 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 when required. Via its local storage, the extended
`file system handles unreliable connections and delays, par-
`ticularly with small files such as cookies, e-mail text and so
`forth.
`
`the client
`[0006] To provide the extended file system,
`includes components that determine via objectattributes the
`remote/local location of file system data, and when appro-
`priate, 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
`programming calls or the like, and the client components
`determine the source and retrieve/update the data appropri-
`ately. Data that is updated (e.g., written) locally is automati-
`cally synchronized with the remote server.
`
`[0007] Moreover, communication is fast by use of a rela-
`tively lightweight protocol using straightforward primitives
`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-
`tion only to retrieve and submit data.
`
`[0008] Other advantages will become apparent from the
`following detailed description when taken in conjunction
`with the drawings, in which:
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0009] FIG.1 is a block diagram representing one exem-
`plary computer system into which the present invention may
`be incorporated;
`
`[0010] 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
`(0011]
`extended file system installation in accordance with one
`aspect of the present invention;
`
`[0012] 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;
`
`[0013] FIG. 5 is a flow diagram generally representing
`logical steps when enlisting a server to participate in an
`extended file system in accordance with one aspect of the
`present invention;
`
`[0014] FIG. 6 is a flow diagram generally representing
`logical steps when defecting a server from participation in
`an extendedfile system in accordance with one aspect of the
`present invention;
`
`[0015] FIG. 7 is a representation of communications
`between a client device and a server to initiate access to
`
`[0005] Briefly, the present invention provides a method
`and system for transparently combining remote and local
`storage to act as one or more virtual local drives for a
`
`remote objects and perform file system-related operations
`thereto in accordance with one aspect of the present inven-
`tion;
`
`

`

`US 2005/0060316 Al
`
`Mar. 17, 2005
`
`[0016] 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 invention;
`
`[0017] FIG. 9 is a flow diagram generally representing
`logical 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;
`
`[0018] FIGS. 10-12 are representations of how the client
`components access local objects locally and remote objects
`remotely in accordance with one aspect of the present
`invention; and
`
`[0019] FIG. 13 is a flow diagram generally representing
`logical steps when determining the source of an object in
`accordance with one aspect of the present invention.
`
`DETAILED DESCRIPTION
`
`[0020] Exemplary Operating Environments
`
`FIG.1 and the following discussion are intended to
`{0021]
`provide a brief, general description of one suitable comput-
`ing environment
`in which the invention may be imple-
`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-
`tures and the like that perform particular tasks or implement
`particular abstract data types.
`
`[0022] Moreover, those skilled in the art will appreciate
`that the invention may be practiced with other computer
`system configurations, including hand-held, laptop or desk-
`top personal computers, mobile devices such as pagers and
`telephones, multi-processor systems, microprocessor-based
`or programmable consumerelectronics 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.
`
`[0023] 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
`memorycontroller, 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., bat-
`tery-backed up)
`in a pocket-sized personal computing
`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 and/or RAM 25, includ-
`
`ing 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 manager32.
`
`In accordance with one aspectof the present inven-
`[0024]
`tion, a local memoryis used as part of a virtual local drive
`is provided by an XFSclient component 33, which includes
`an XFS Ramdisk manager and storage 34 (XFSDISK), and
`other components (described below). A user may enter
`commandsand 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
`input devices may include a microphone 37 connected
`through a suitable audio interface 38 and physical (hard-
`ware) or a logical keyboard (not shown). Additional other
`devices (not shown), such as LED displays or other periph-
`eral 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).
`
`[0025] Other external input or output devices 42 such as a
`joystick, game pad,satellite dish, modem or thelike (satel-
`lite, 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
`coupled to the system bus 23, but may be connected by other
`interfaces, such as a parallel port, game port or universal
`serial bus (USB). 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
`appropriate connection port (e.g., slot) 43 and interface 44.
`A numberof hardware buttons 45 such as switches, buttons
`(e.g., for switching application) and the like may be further
`providedto facilitate user operation of the device 20, and are
`also connected to the system via a suitable interface 46. An
`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., modemsor the like), printers, and so on
`(not shown). It will be appreciated that the various compo-
`nents and connections shown are exemplary and other
`components and means of establishing communications
`links may be used.
`
`[0026] Turning to FIG.2 of the drawings, there is shown
`an alternate computer system into which the present inven-
`tion 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, tun-
`ing, timed operation, and/or the like is provided. The appli-
`cation mayalso provide a user interface via which a useris
`able to access the Internet, and may include a browser,
`although as is known, the browser may beintegrated into the
`operating system 60 of the set-top box 54. A user interacts
`with the application 58 and/or operating 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.
`
`[0027] As is known,one of the functions of a contempo-
`rary set-top box 54 is to output to the receiver/monitor 56
`television programming and Internet content received from
`
`

`

`US 2005/0060316 Al
`
`Mar. 17, 2005
`
`a provider 66. To this end, some signal processing mecha-
`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, consumersatellite dishes only receive content, and
`thus in a satellite system an additional mechanism(e.g.,
`telephone line, not shown) is required to output data to the
`provider 66. Other components 72 such as to display closed-
`captioning, allow parental control, provide on-screen pro-
`gram guides, control video recorders and so forth may be
`provided as is also known. In any event, these functions of
`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.
`
`[0028] Extended File System
`
`In accordance with one aspect of the present inven-
`[0029]
`tion,
`to provide access to remote client-owned objects
`(directories and/orfiles therein) maintained in remote stor-
`age 74 by one or more XFSfile servers 76, the set-top box
`includes (e.g., in system memory) an XFS client 33 com-
`prising a number of components (described below) includ-
`ing the XFS Ramdisk manager/virtual local drive 34.A file
`system manager32 is also provided, as described below. For
`example, in the Windows® CEoperating system, a suitable
`file system manager is known as “FSDMGR.”
`
`enabling operation without a physical connection. Synchro-
`nization may be performed at somelater 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
`whendealing with Internet content, as even when physically
`connected to a provider, the Internet is unreliable and can be
`susceptible to long delays in transmission andalso helps in
`optimizing bandwidth utilization.
`
`[0033] As generally represented in FIG. 4, the extended
`file system (XFS) comprises the XFS-Client portion 33 and
`an XFS-Server portion 92, which together generally include
`the XFS Ramdisk manager/virtual local drive 34 and other
`components 94-102 (described below). Note that the various
`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 server
`portion 92 may comprise a single physical component
`servicing the requests for
`its logical components. For
`extremely large installations, however, it may be desirable
`for the components to be implemented separately for scal-
`ability reasons. Similarly,
`the virtual local drive of XFS
`(managed by the XFSDISK 34) may be at any physical or
`virtual location or locations in system memory, not neces-
`sarily adjoining or within the memoryallocated to the other
`XFS client components.
`
`[0034] The XFSDISK RAMdisk manager34 that provides
`[0030] An exemplary extended file system (XFS) instal-
`the virtual local drive is a complete, thread-safe implemen-
`lation is represented in FIG. 3, and typically comprises a
`tation of a stream interface driver (as defined in the “Win-
`large number(e.g., millions) of client devices 80,-80, (for
`dows® CE DDK,”available from Microsoft® Corporation,
`example, the pocket computing device 20 or the set-top box
`Redmond, Wash.) The XFSDISK 34is loaded at boottime,
`54). The client devices 80,-80,, are capable of connecting to
`and is configured based on information provided in the
`one or more of the servers (76,-76,, in FIG. 3) over a
`system registry. The XFSDISK 34is capable of loadingafile
`network 84 via a service provider 86. The servers 76,-76,,
`system device onitself, thereby appearing as an actual folder
`participate in XFS as nameservers, access controllers and
`off of the root folder of a hierarchically organized file
`permission managers, or a combination of access controller,
`system. To provide accessible memory, the XFSDISK 34
`permission manager and name server as described below
`with reference to FIG.4.
`creates a specified number of heaps of a specified size and
`then “stitches” them together to give the appearance of a
`single, contiguous, addressable block of memory which
`servesas a local cache ofthe 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 bydirectly reading from
`or writing to the disk locations. XFSDISKservesas the local
`cache for the remote file system of the present invention.
`
`[0031] The servers 76,-76,, (more particularly the access
`controllers) point to a common remotefile system for storing
`files in one or more XFSstorage devices 74 implemented
`using DFS shares. DFSis a feature of Windows® 2000 (or
`Windows® NT®) that provides file replication (used for
`providing redundancyof data) and load balancing fora file
`system. In one preferred implementation, the remote file
`system is the Windows® NTFSfile system, which among
`other benefits, is considered secure. As will be understood,
`however, the XFSfile system of the client is independent of
`the remote file system/server configuration, and thus virtu-
`ally any operating and/or file system (e.g., UNIX, FAT,
`FAT32) or combination thereof that works with the server-
`side storage media 74 will suffice for purposes of the present
`invention.
`
`the client
`In the set-top box implementation,
`[0032]
`devices 54 will normally be physically connected to the
`servers 76,-76,,, at all times via the cable/satellite modem 70
`therein. Indeed, since broadbandis in use, remote files may
`be quickly accessed by the client, as described below, even
`though logical connections are preferably made on a per-
`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
`
`[0035] Two XFS-Client 33 components include the XFS
`Client Interface (XFSCLNT) 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 performsinitialization operations.
`
`[0036] The XFS File System Driver (XFSFSD) 96 is an
`installable 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
`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
`
`

`

`US 2005/0060316 Al
`
`Mar. 17, 2005
`
`make space,the files presented as available in the local file
`system are marked as remote and for those files, the file
`system essentially behaveslike a redirector. The local cache
`of files is thus intelligently managed.
`
`[0037] The XFSserver portion 92 includes an XFS Access
`Controller 98, an XFS Permissions manager 100, and an
`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 whenthe access controller 98 receives name-server
`primitives, it routes them to name services module 102. As
`described below, the access controller 98 translates primi-
`tives to appropriate actions to be taken onthe file system and
`sends the response back to the client.
`[0038] The Permissions manager 100 is responsible for
`authenticating clients and users on the clients. Having
`authenticated the client, and a specified user, the permissions
`manager 100 provides access to the private folder for a given
`client. This is done as a part of PRIMITIVECALL,
`described below. The permissions manager 100 may use the
`standard X509-based authentication scheme for validating
`clients. In addition to validating client devices, the permis-
`sions manager 100 enables multiple users of a common
`device (e.g., a single set-top box) to share the same device
`while isolating the files of one user from each other user.
`SQL-based authentication,
`the Windows® 2000 Active
`Directory that specifies domain users or any custom authen-
`tication scheme may be used for authentication.
`
`[0039] The nameservices module 102 provides enlistment
`and nameresolution services, as also described below, by
`maintaining (e.g., in the local server registry) a local direc-
`tory of the name servers and access controllers. To enlist,
`when a server starts up, it sends a UDP broadcast of an
`enlistment request as described below.If the server gets an
`appropriate response from one of the other servers, it then
`sends a directed enlistment for confirming the entries, after
`which the local directory is synchronized via a directed
`resolve. The process of sending resolves across to known
`servers is done at periodic intervals of time to ensure that
`any server that is added is reflected in the local directory.
`The name services module 102 also handles defection
`(withdrawal from participation) of servers. When a defec-
`tion is initiated for a specific server,
`the name services
`module 92 sends directed defects to the other servers in the
`
`local directory. Once the other servers have acknowledged
`the deletion of the defecting server, no more requests are
`processed.
`[0040] For the purpose of XFS communications, there are
`three specific sets of network functions, called primitives,
`comprising a set of Name Resolution primitives, which
`include UDP/TCPpackets used to locate XFS components
`on the network, a set of control primitives, which are
`UDP/TCPpackets used for managementof the XFS system,
`and a set of session primitives, which are TCP streams used
`to transfer data among XFS components. Session primitives
`are conducted on TCP connections from machine to
`machine. TCP provides a minimal Quality of Service (QoS)
`scenario for the connection. Primitives have two distinct
`states, request and response. Thus, for example, the response
`to a Resolve request will be a Resolve response. The
`Maximumsize for a primitive is 512 bytes for UDPtrans-
`ported primitives and 1024 bytes for TCP transported primi-
`tives.
`
`[0041] One control primitive is the enlist primitive, which
`is used to enlist clients (as described below), and also by
`servers that are attempting to participate in an XFS instal-
`lation. A field in the primitive identifies whether a client or
`server sent the Enlist request.
`
`[0042] Moreparticularly, to enlist a server, an XFS server
`(e.g., 76,) sends an Enlist primitive to notify the name
`servers (XFS-NS)that it wants to begin participation in the
`XFS system. The server 76, does not begin processing
`requests until it has received an Enlist response primitive
`from the name services module at least one other server.
`
`After receiving an Enlist response primitive, the XFS server
`763 may begin processing requests, however,
`it should
`continue to send Enlist primitives until it has received and
`Enlist response primitive from every name services module
`102 server participating on the system. Servers (as well as
`clients) should maintain lists of resolved server IP’s, and
`preferably update the list in a Time To Live (TTL, which
`denotes the amount of time that a piece of data may be
`considered valid before it must be verified), manner.It is
`recommended that TTL’s be no less than 256 seconds for
`each XFS-NS, and 128 seconds for other servers. In the
`event that no XFS-NScan be located to resolve requests, the
`list should be invalidated, and an Enlist primitive should be
`sent via UDPbroadcast to retrieve the network topography.
`
`[0043] After the first Enlist response, the name services
`module of the server 76, should send its Enlist requests to
`unresponsive XFS-NSserversdirectly, instead of broadcast-
`ing the requests on the network. This will help to reduce
`network traffic and avoid responses from XFS-NSservers
`which have already responded to the earlier Enlist request.
`
`[0044] For the server control primitive “Enlist,” the logi-
`cal flow generally described with refere