United States Patent
`Yohe et al.
`
`[19]
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`USOOS83S943A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,835,943
`*Nov. 10, 1998
`
`[54] APPARATUS AND METHOD FOR
`INCREASED DATA ACCESS IN A NETWORK
`FILE ORIENTED CACHING SYSTEM
`
`[75]
`
`Inventors: Thomas Patrick Yohc, Centerville;
`Gordon L. Dorworth, Spring Valley,
`both of Ohio; Jon J. Penner, Austin;
`Scott Hertzog, Round Rock, both of
`Tex.
`
`[73] Assignee:
`
`Stampede Technologies,
`Ohio
`
`Inc., Dayton,
`
`[ * ] Notice:
`
`The term of tbis patent shall not extend
`beyood tbe expiration date of Pat. No.
`5,682,514.
`
`[21]
`[22]
`
`Appl, No.: 888,311
`Filed:
`Jul. 3, 1997
`
`Related U.S. Application Data
`
`[63]
`
`[51]
`[52]
`
`[58]
`
`[56]
`
`of Ser. No. 565,393, Nov. 30, 1995,
`
`Continuation-in-part
`Pat. No. 5,682,514.
`Int. CI.6
`U.S. CI.
`
`G06F 12/08
`.••..••..••..••..••..•••.•••.•••..••..••..••..••..•••
`711/118; 711/122; 395/200.33;
`395/200.09
`395/200.47, 200.49,
`Field of Search
`395/200.33, 200.09; 711/144, 118, 122
`
`References Cited
`U.S. PArENT DOCUMENTS
`
`7/1993 Baird et al.
`5,226,143
`11/1993 Wilkinson et al.
`5,261,069
`12/1993 Hirano et al.
`5,274,787
`1/1994 Mohan et aJ.
`5,276,835
`3/1994 Donaldson et al.
`5,297,269
`4/1994 Tetzaff el al.
`5,301,290
`2/1995 Hunter et aJ.
`5,394,555
`4/1995 Stamm et aJ.
`5,404,483
`6/1995 Herlihy et aJ.
`5,428,761
`9/1995 Nelson et al.
`5,452,447
`Primary Examiner---¥Jisna Lim
`Attorney, Agent, or Firm=R. William Grabam
`[57]
`ABSTRACT
`
`711/145
`711/145
`711/143
`711/144
`711/145
`711/142
`711/148
`711/144
`711/130
`........... 707/205
`
`.
`
`.
`.
`
`.
`
`.
`.
`.
`
`An apparatus for increased data access in a network includes
`a file server computer baving a permanent storage memory,
`a cache verifying computer operably connected to tbe file
`server computer
`in a manner to form a network for rapidly
`transferring data,
`tbe cacbe verifying computer having an
`operating system, a first memory and a processor with means
`for performing an operation on data stored in the permanent
`storage memory of the file server computer
`to produce a
`signature of the data characteristic
`of one of a file and
`directory, a remote client computer having an operating
`system, a first memory, a cache memory and a processor
`with means for performing an operation on data stored in the
`cacbe memory to produce a signature of the data, a com-
`munication server operably connected to the remote client
`computer to the cache verifying computer and the file server
`computer
`and comparators
`operably associated with the
`cacbe verifying computer and remote client computer
`for
`comparing the signatures of data with aile anotber to deter-
`mine whether
`the signature of data of the remote client
`is
`valid.
`
`4,410,944
`5,222,224
`
`.
`10/1983 Kronies
`6/1993 Flynn et al.
`
`711/147
`711/144
`
`.
`
`12 Claims, 12 Drawing Sheets
`
`Cache Verifying Computer
`
`14
`
`File Server Computer
`
`16
`
`
`
`Permanent
`Storage
`
`MICROSOFT
`
`EXHIBIT 1005
`
`Page 1 of 21
`
`

`
`.&;;;.. ~
`'"\C
`
`l
`
`~~U
`
`Ul
`
`.... N
`
`...,
`
`....
`tt...•
`'Jlg
`
`e.
`
`00
`\0\0
`....
`... ~c
`
`Ze~.
`
`="
`
`""
`
`""~
`
`~~ ~~"
`
`PermanentStorage
`
`Link<
`Comrr
`
`'\
`
`IWANDriver
`
`II
`Layer
`Transfer
`Network
`
`II
`
`I
`
`Pre-fetch
`II
`
`Data
`
`Redirector
`
`Network
`
`File
`
`Page 2 of 21
`
`Storage
`Permanent
`
`~
`
`IO.S.
`
`RelatedArt
`
`II
`IFileSystemInterface
`
`Jl
`Programs
`Application
`
`RemoteClient
`
`I
`
`I
`
`DiskDriver
`
`.r.
`
`II
`Cacher
`Disk
`Based
`Ram
`II
`
`System
`
`File
`Local
`II
`
`

`
`.&;;;.. ~
`'"\C
`
`l
`
`~~U
`
`Ul
`
`.... N
`tt...• N
`'Jlg
`
`...,
`
`e.
`
`00
`\0\0
`....
`... ~c
`
`Ze~.
`
`="
`
`""
`
`""~
`
`~~ ~~"
`
`Storage
`
`/""-..,
`
`~
`
`~
`
`6
`17
`
`8DiskDriver
`
`17
`
`DiskCacher
`RamBased
`
`II
`
`74
`
`II
`System
`File
`Local
`
`II
`
`72
`
`nerrace
`It
`FileSystem
`JL
`
`-<
`
`I
`
`70
`
`O.S.
`
`~~er
`
`I;
`
`I'
`
`I
`
`,
`
`84
`
`Transport
`Network
`\JY'
`11'
`
`86i1
`
`Application
`File~erver
`
`18
`
`FileServerComputer
`
`I
`
`.L-
`
`68
`
`'-----,.,-~I,.,-L-----~
`IFileSystemInterface62
`
`Redlrector
`Nei':"ork
`~~~~
`
`File
`
`~
`
`~~~_"__
`
`----'
`
`60
`
`64~1O,S.
`
`66
`
`:I[
`
`581Generator561Generator
`
`"
`
`Driver
`~N
`Jv
`I'
`Layer
`Transport
`Network
`/1
`
`57
`IComparatorIIBlockSignatureIIDirectorySignature
`54
`
`---"~a~~~'~~'~~i~;~:e~~-'
`
`L
`
`,..---
`
`r--
`
`Redirector
`File
`Network
`
`36
`
`26JO,S.24
`
`~~~U~
`
`FileSystemInterface
`
`,1/
`
`46
`
`Programs
`Application
`
`j
`
`,-
`
`-",
`
`-
`
`Cacher
`Directory
`:1
`FileCacher
`Network42
`.-
`
`k---,43
`
`~
`
`82Layer
`
`Server16V
`
`20
`Link
`LAN
`
`40
`
`river
`
`WAND'
`
`37
`Data
`Pre-letch
`II
`
`,
`
`~
`
`38
`
`Transfer
`Network
`~~
`
`f'7Layer
`
`~
`
`Comparator
`Signature
`46Directory
`Analyzer
`Ratio
`Hit
`Generator
`Signature
`144Block1
`
`45
`
`I--W-A~N~4""81ILAN50
`
`Driver
`
`DriverI
`
`JC
`Layer521
`IRouting1
`
`jl
`
`Page 3 of 21
`
`Fig.2
`
`,
`
`Storage
`Permanent
`
`In
`L'k
`Comm
`
`22
`
`34
`
`~
`
`~
`
`32!1
`
`DiskDriver
`
`30
`
`28
`
`II
`II
`Cacher
`IS
`D'k
`Based
`Ram
`
`II
`
`System
`F',le
`Local
`
`

`
`u.s. Patent
`
`Nov. 10, 1998
`
`Sheet 3 of 12
`
`5,835,943
`
`NFC42
`Intercept File System
`Call from AP 46
`
`100
`
`Yes
`
`104
`
`Fig. 3
`
`Allow Network
`File Redirector
`to Handle
`
`Page 4 of 21
`
`

`
`u.s. Patent
`
`Nov. 10, 1998
`
`Sheet 4 of 12
`
`5,835,943
`
`Happens on 12
`
`Invoke NFR 36 to Process
`Application Request
`
`No
`
`NFR36
`Return Results of
`Operation to AP 46 205
`
`NFR 36 Assigns Handle and
`NFC 42 Builds Open/Create
`Request and Sends it to CVA 54
`This Triggers 250
`
`NFC42
`Returns Results
`of 202 to AP 46
`
`216
`
`NFC 42 Associates
`"Handle" Assigned by
`CVA 54 with Handle
`returned in 202
`
`212
`
`NFC42
`Updates Network File
`Cache via LFS 28
`
`Fig. 4
`
`Page 5 of 21
`
`

`
`u.s. Patent
`
`Nov. 10, 1998
`
`Sheet 5 of 12
`
`5,835,943
`
`Happens on 14
`
`CVA 54 Opens File Specified
`in Open/Create
`Request via FSI 62
`,-------1
`252
`
`)-_N_O_~
`
`CVA 54 Sends Back Bad
`Response to NFC 42
`256
`
`CVA54
`Assigns a "Handle" to
`this Object
`
`CVA54
`Send Good Response
`to NFC 42
`260
`
`Fig. 5
`
`Page 6 of 21
`
`

`
`u.s. Patent
`
`Nov. 10, 1998
`
`Sheet 6 of 12
`
`5,835,943
`
`~
`
`12
`
`NFC42
`InvokesBSG44 to
`)-y,-es-~ Obtain Signature
`of Data 316
`
`NFC42 SendsVerify
`Requestto CVA.54
`via NTL 38
`320
`
`This Triggers350. Wait
`NFC42 ReceivesData
`from CVA54
`322
`
`Yes
`
`No
`
`This Triggers380.Wait
`NFC 42 ReceivesData
`from CVA54 312
`
`NFC42 Retrieves
`Data from File Server
`Computer 18
`
`No
`
`Yes
`
`Datawill have
`been Returned
`in Response
`
`328
`
`NFC42
`UpdatesNetworkFile
`Cachevia LFS 28,---1+-------------1
`308
`
`NFC42
`Return Datato AP46
`314
`
`Fig. 6
`
`Page 7 of 21
`
`

`
`u.s. Patent
`@)
`
`Nov. 10, 1998
`
`Sheet 7 of 12
`
`5,835,943
`
`12
`
`CVA54
`Reads Data from
`File Server Computer 18
`352
`
`eVA 54
`Invokes SSG 56
`to obtain Signature
`354
`of Data
`
`CVA 54 Invokes Comparator 55
`to Compare Signature
`with that
`found in
`Verify-Req.
`
`356
`
`No
`
`No
`
`Yes
`
`CVA 54 Sends Back
`Good Response
`to NFC 42
`
`366
`
`CVA 54 Sends BAD Response
`and includes the Just Read
`Data in the Response
`to NFC 42
`
`364
`
`CVA 54 Sends Back
`Bad Response
`to NFC 42
`
`362
`
`Fig. 7
`
`CVA 54 Reads Data from
`File Server Computer 18
`f3a2
`
`1
`
`Fig. 8
`
`CVA 54 Sends Back
`Response to NFC 421384
`
`Page 8 of 21
`
`

`
`u.s. Patent
`
`Nov. 10, 1998
`
`Sheet 8 of 12
`
`5,835,943
`
`No
`
`Yes
`
`Invoke NFR 36 to
`Write Data to
`File Server Computer 18 404
`
`NFC42 Sends
`Write_Request
`to CVA 54
`
`406
`
`This Triggers 450. Wait
`NFC 42 Receives
`Response
`from CVA 54 408
`
`No
`
`NFC 42 Updates Network
`Cache via LFS 28
`
`Fig. 9
`
`LFS 28 Reports
`Status to AP 46
`
`412
`
`CVA 54 Writes Data
`toFile Server
`Computer 18 452
`
`CVA54 Sends
`Back Response
`to NFC 42
`
`454
`
`Fig. 10
`
`Page 9 of 21
`
`

`
`u.s. Patent
`
`Nov. 10, 1998
`
`Sheet 9 of 12
`
`5,835,943
`
`NFC 42 Builds
`Lock I Unlock
`Request
`1502
`
`NFC 42 Sends to
`CVA54
`
`1504
`
`This Trig~er 550. Wait
`NFC 4 Receives
`from CVA 54
`!506
`
`CVA54
`Sends Lock/Unlock
`Request
`to File Server 18
`I5s2
`via FSI62
`
`NFC42
`Return results
`to AP 46 1508
`508
`
`CVA54
`Sends Back
`Response to
`12 via FSI6~
`
`554
`
`Fig. 11
`
`Fig. 12
`
`Page 10 of 21
`
`

`
`u.s. Patent
`
`Nov. 10, 1998
`
`Sheet 10 of 12
`
`5,835,943
`
`NFC 42 Builds
`Close _Req uest
`1602
`
`NFC 42 Sends
`to CVA 54
`I 604
`
`This Trigger 650. Wait
`NFC 42 Receives
`from CVA 54
`
`I 606
`
`NFC 42 Invokes
`NFR 36 to
`close the file
`I 608
`
`NFC42
`Returns results
`to AP 46
`
`I 610
`
`Fig. 13
`
`CVA54
`Performs Internal
`Processing
`I 652
`
`CVA54 Sends
`Back Response
`to NFC 42
`I 654
`
`Fig. 14
`
`Page 11 of 21
`
`

`
`u.s. Patent
`
`Nov. 10, 1998
`
`Sheet 11 of 12
`
`5,835,943
`
`Yes
`
`Yes
`>-----)i
`
`NFC 42 Retrieves
`signature associated
`with this directory
`request
`from cache
`via LFS 28
`
`719
`
`NFC42 Sends
`Directory Verify
`Request to
`
`eVA 54 via NTL 38nO
`
`NFC 42 Retrieves
`Next Directory
`Sub-Object
`from
`Cache via LFS 28
`
`NFC 42 Sends
`Directory Verify
`Request to
`CVA 54 via NTL 38
`710
`
`NFC 42 Returns
`"No More Objects"
`Status to AP 46
`
`706
`
`NFC 42 Returns
`First Sub-Object
`from
`cache via LFS 28
`and returns it to
`AP46
`723
`
`NFC 42 Returns
`Sub- Object
`toAP46
`
`705
`
`This triggers 750.
`Wait.
`NFC 42 Receives
`Signature from
`CVA54
`711
`
`NFC 42 Returns
`First Sub- Object from
`cache via LFS 28 and IE----j
`returns it to AP 46
`
`729
`
`Store signature
`obtained in either 721
`or 711 into cache
`via LFS 28
`
`728
`
`Yes
`
`Fig. 15
`
`NFC 42 Invokes
`NFR 36 to retrieve
`first directory
`Sub-Object
`
`724
`
`the Sub-Object
`into cache via
`LFS28
`
`NFR 36 to retrieve
`next directory
`Sub-Object
`
`727
`
`Page 12 of 21
`
`

`
`u.s. Patent
`
`Nov. 10, 1998
`
`Sheet 12 of 12
`
`5,835,943
`
`Initialize Signature
`of
`Directory~
`I 751
`
`Retrieve first directory
`Sub-Object from File Server
`Computer 18 ~
`1752
`
`No
`
`••.
`
`Factor the signature of this
`Sub-Object
`into the overall
`Signature of DirectorY--
`1754
`
`Retrieve the next
`Directory Sub-Object
`
`from File Server 18I7s5
`
`,
`CVA 54 Sends Back
`Signature of Directory
`
`to NFC 42 r-==-
`
`I 756
`
`Fig. 16
`
`Page 13 of 21
`
`

`
`5,835,943
`
`1
`APPARATUS AND METHOD FOR
`INCREASED DATA ACCESS IN A NETWORK
`FILE ORIENTED CACHING SYSTEM
`
`This is a continuation-in-part of U.S. Ser. No. 08/565,393
`filed Nov. 30, 1995 which has now issued as U.S. Pal. No.
`5,682,514 issued on Ocl. 28, 1997.
`
`2
`connected to LFS which in turn is connected to an RBDC,
`aDD and a PSD. Aside from the OS, there exists a file server
`application which employs the OS via the FSI.
`The problem associated witb tbese prior systems is their
`inability to provide a remote client user witb greater speed
`of access to file server data and/or
`file server directories.
`This is especially so because of the type of link in which the
`remote client may be accessing tbe data through, such as a
`modem phone link. In tbe context of the present
`invention,
`10 "remote client" is defined as a user, accessing data over a
`relatively slow link, such as a modem phone link. A typical
`modem phone link provides a transfer
`rate of about 28.8
`kilobits of information per second. Tbis is contrasted with a
`link in a LAN connection wbicb can transfer at about 10
`15 Megabits per second. These remote clients are thus greatly
`limited in speed of access.
`
`SUMMARY OF THE INVENTION
`The present
`invention overcomes
`tbe above described
`deficiencies which exist with remote clients accessing and
`verifying data in files and directories
`from a file oriented
`network environment.
`It is an object
`to increase the speed in which a remote
`client can access data and directories.
`It is another object
`to maintain integrity of the accessed
`data and directory while increasing the speed in which the
`data is accessed.
`to act as a
`an agent
`is to implement
`A further object
`caching verifier between a remote client and a file server
`computer.
`to a remote
`is to add intelligence
`Still, another object
`client in order to reduce tbe overall
`time in which a remote
`client accesses data.
`Another object
`is to overcome the deficiencies of data
`transfer for a remote client.
`Other ohjects and advantages will he readily apparent
`from reading the following description
`and viewing the
`drawings.
`invention is directed to an appa-
`the present
`Accordingly,
`ratus for increased data access in a network, which includes
`a file server computer having a permanent storage memory,
`a cache verifying computer operably connected to the file
`server computer
`in a manner to form a network for rapidly
`transferring data,
`the cache verifying computer having an
`operating system, a first memory and a processor with means
`for performing an operation on data stored in the permanent
`storage memory of the file server computer
`to produce a
`signature of the data characteristic
`of one of a file and
`directory, a remote client computer having an operating
`system, a first memory, a cache memory and a processor
`with means for performing an operation on data stored in the
`cache memory to produce a signature of the data, a com-
`munication server operably connected to the remote client
`computer to the cache verifying computer and the file server
`computer
`and comparators
`operably associated with the
`cache verifying computer and remote client computer
`for
`comparing the signatures of data with one another to deter-
`mine whether
`the signature of data of the remote client
`is
`valid. The remote client computer
`includes means respon-
`sive to each comparison performed by the comparator 00 the
`data for generating and storing a validation ratio for the data
`in the first memory and for removing the data from the cache
`memory when the validation ratio drops below a predeter-
`mined value. Also,
`the cache verifying computer
`includes
`means for recognizing a LOCK request
`from the remote
`
`Page 14 of 21
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`to data access in a file
`The present
`invention relates
`oriented network system. More particularly,
`the present
`invention is directed to a client-age nt-server utility which
`increases the speed in which data in the form of files and
`directories are accessed across slow link communications
`via remote node caching and verifying.
`2. Related Art
`Many operating systems are equipped to handle caching
`and verifying of data. Traditionally,
`in a remote client's
`caching system, optimization in retrieving data is limited to
`prefetching.
`In other words, an application program in a
`remote client requests from a file server transmission of a
`predetermined number of bytes of information (e.g., x bytes)
`and the operating
`system on the client prefetches
`the 25
`requested data plus another number of bytes of information
`(e.g., x-y bytes). Thus, when the application requests the
`bytes,
`it already exists in its readily accessible memory
`(cache).
`there also exist problems with verification of 30
`In addition,
`directories
`in existing systems.
`It has been found,
`for
`example,
`that two remote clients concurrently accessing data
`and attempting
`to verify a directory 'will not necessarily
`obtain the same data due to the fact that the data from the file
`server computer will not necessarily send out the data in the 35
`same order to each of the remote clients. Thus,
`there is no
`clear indication whether
`the directory data is current.
`In a desktop caching system, a high speed memory is used
`to cache data that is stored on a hard disk. While a desk-top 40
`cacbe program, such as Microsoft's SmartDrive is a useful
`tool
`to increase
`performance
`from the random access
`memory (RAM),
`this type of caching tecbnique
`is not
`applicable to remote environments because of its inability to
`correctly handle multiple remote clients accessing tbe same 45
`data files concurrently,
`i.e., it is likely to corrupt
`the data.
`File servers bave employed caching techniques wbich
`parallel
`techniques of tbe desktop. Here,
`the file server
`deviates in protecting against multiple common data user
`access by implementing or providing a file locking service
`to clients.
`includes a remote
`As sbown in FIG. 1, the related art
`client computer having an operating system (OS) witb a file
`system interface (FSI). Operatively connected to the FSI is
`a local
`file system (LFS) which in turn is operatively
`connected to a RAM based disk cacher (RBDC), disk driver
`(DD) and permanent
`storage disk (PSD). Also, operatively
`connected to tbe FSI is a network file redirector (NFR) with
`prefetch capability, and a network transport
`layer
`(NTL)
`connected to a WAN driver. Aside from the OS, there exist
`application programs (AP) which employs tbe OS via the
`FSI. A cnmmunication server (CS) connects to the remote
`client computer and includes a WAN driver, routing layer
`and LAN driver.
`through a LAN link to a file server
`The CS connects
`computer having an OS. Tbe file server computer OS
`includes an NTL connected to a LAN driver and an FSI
`
`20
`
`50
`
`55
`
`60
`
`65
`
`

`
`5,835,943
`
`25
`
`3
`client computer and for obtaining a lock on the data from the
`file server computer
`in response to the LOCK request.
`Terminology
`includes,
`storage memory," as used herein,
`"Permanent
`but
`is not
`limited to, disk drive,
`flash RAM or bubble
`memory, for example.
`"File oriented distributed network," as used in the present
`invention, will
`include a network wherein the file server
`computer data is accessed via the following set of file system 10
`primitives: OPEN, CREATE, READ, WRITE, SEEK,
`LOCK, UNLOCK, CLOSE and DIRECTORY REQUEST.
`"Caching" is the function of retrieving an object from a
`relatively high speed storage device from a list of most-
`recently-used objects.
`"Cache" is a file wbich resides in permanent storage and
`contains the most-recently-used
`blocks of data read from a
`remote file server.
`"Object" is a sequence of data of variable length.
`"Sub-object"
`is a portion of an Object.
`"File server computer"
`is a computer which includes a
`processor with its associated memory, an operating system,
`and a permanent storage memory.
`"Reverse channel"
`is the means by which a response
`message is sent over the same network layer
`interface in
`which a request was received.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 illustrates tbe block diagram configuration of the 30
`related art.
`FIG. 2 illustrates tbe block diagram configuration of the
`present
`invention.
`FIG. 3 illustrates a flow chart of the operations of the
`present
`invention corresponding
`to the requests within a 35
`remote client.
`FIG. 4 illustrates a flow chart of the operations of the
`present
`invention
`corresponding
`to OPEN/CREATE
`requests on remote client computer.
`FIG. 5 illustrates a flow cbart of the operations of the 40
`present
`invention
`corresponding
`to OPEN/CREATE
`requests on cache verifying computer.
`FIG. 6 illustrates a flow chart of the operations of the
`present
`invention
`corresponding
`to READ requests on
`remote client computer.
`FIG. 7 illustrates a flow chart of the operations of the
`present invention corresponding to READ requests on cache
`verifying computer.
`FIG. 8 illustrates a flow chart of additional operations of
`tbe present invention corresponding to READ requests in the
`cacbe verifying computer.
`FIG. 9 illustrates a flow cbart of the operations of the
`present
`invention corresponding
`to WRITE requests on
`remote client computer.
`FIG. 10 illustrates a flow cbart of the operations of the
`present
`invention corresponding
`to WRITE requests on
`cacbe verifying computer.
`FIG. 11 illustrates a flow cbart of the operations of the
`present
`invention
`corresponding
`to LOCK requests on 60
`remote client computer.
`FIG. 12 illustrates a flow cbart of the operations of the
`present invention corresponding to LOCK requests on cache
`verifying computer.
`FIG. 13 illustrates a flow cbart of the operations of the 65
`present
`invention corresponding
`to CLOSE requests on
`remote client computer.
`
`4
`FIG. 14 illustrates a flow chart of the operations of the
`present
`invention corresponding
`to CLOSE requests on
`cacbe verifying computer.
`FIG. 15 illustrates a flow chart of the operations of the
`present
`invention
`corresponding
`to DIRECTORY
`REQUEST on cache verifying computer.
`FIG. 16 illustrates a flow chart of the operations of the
`present
`invention corresponding to a part of the operations
`in FIG. 15.
`DETAILED DESCRIPTION OF A PREFERRED
`EMBODIMENT
`In the description which follows, the representation of the
`present
`invention is in part presented in terms of program
`15 operations executed on a file oriented distributed network of
`computers, but may as well be applicable to distributed file
`oriented network systems. The operations are steps leading
`to a certain result. Typically,
`these steps take the forrn of
`electrical signals which are manipulated, stored, transmitted,
`20 combined, compared or otherwise operated upon by a par-
`ticular computer in the network. For simplicity,
`these signals
`may be referred to herein as bits, bytes or data.
`The following description describes solutions to tbe prob-
`lems associated with a remote client computer's
`ability to
`access specified data from a file or directory of a file server
`computer
`located on a network or world wide web. An
`apparatus and met bod are disclosed which penn it the remote
`client computer
`to reduce the time for accessing such data
`using a cache verifying computer coupled with a caching
`technique.
`invention
`The performance gains realized by the present
`are derived from the fact that remote clients tend to repeti-
`tively access the same data by performing file reads.
`If a
`copy of the data can be stored in the permanent
`storage
`memory of the remote client computer and also verified to
`be current when it
`is subsequently
`retrieved,
`this will
`improve
`performance
`significantly.
`This
`is because
`it
`requires much less bandwidth to verify a block of data than
`it would to actually transfer a block of data.
`invention is
`Referring now to the FIGS. 2-15,
`the present
`a network computer system 10 having at least one remote
`client computer 12, cache verifying computer 14, commu-
`nication server 16 and file server computer 18. The cache
`45 verifying computer 14 and file server computer 18 are
`connected via a local area network (LAN)
`link 20. The
`communication server 16 links the remote client computer
`12 to the LAN 20, wbicb in turn permits communication
`with the cache verifying computer 14 and the file server
`computer 18.
`The remote client computer 12 communicates via com-
`munication link 22 to the communication
`server 16. The
`communication
`server 16 can be of a type such as that
`provided by Cisco, 3Com, Shiva, etc., which will act as a
`router of traffic between the LAN 20 and communication
`link 22 and convert data through the LAN 20. The LAN 20
`can be Ethernet or Token Ring, for example.
`The remote client computer 12 has an operating system
`(OS) 24 with a me system interface (FSI) 26. Operatively
`connected to the FSl26 is a local file system (LFS) 28 which
`in tum is operatively connected to a RAM based disk cacher
`(RBDC) 30, disk driver (DD) 32 and permanent storage disk
`(PSD) 34. A network file redirector (NFR) 36 with prefetch
`data 37, operatively connects
`to a network transport
`layer
`(NTL) 38 which in tum is connected to a WAN driver 40.
`Additionally,
`the invention includes a network file cacher
`(NFC) 42 which is operably disposed between and inter-
`
`50
`
`55
`
`Page 15 of 21
`
`

`
`5,835,943
`
`15
`
`5
`connects the FSI 26 and NFR 36. The NFC 42 has opera-
`tively associated therewith a directory cacher (DC) 43 and
`directory signature comparator
`(DSC) 46.
`The NTL38 operatively connects to the NFC 42. Also, the
`NFC 42 operatively connects to the LFS 28. The NFC 42
`includes a block signature generator (BSG) 44 and hit ratio
`analyzer
`(HRA) 45, which will be more fully described
`hereinafter. Aside from tbe OS, tbere exists on the computer
`12 application programs (AP) 46 which employ tbe OS 24
`via FSI 26.
`a WAN
`(CS) 16 includes
`server
`The communication
`(RL) 52
`driver 48, a LAN driver 50 and routing layer
`operatively interconnecting the WAN driver 48 and the LAN
`50 driver.
`The cache verifying computer 14 includes a cache veri-
`fying agent
`(CVA) 54 having a BSG 56 (of
`the type
`described herein), a directory signature generator (DSG) 57
`and a comparator 58. Also,
`included is an OS 60 having an
`FSI 62 operatively
`connected to CVA 54, an NFR 64
`operatively connected to the FSI 62, an NTL 66 operatively
`connected to the NFR 64 and CVA 54, and a LAN driver 68 20
`operatively connected to the NTL 66.
`TIle tile server computer 18 includes an OS 70 having an
`FSI 72 which is operatively connected to an LFS 74 which
`in turn is connected to an RBDC 76, aDD 78 and a PSD 80.
`Also, the OS 70 includes an NTL 82 operatively connected
`to a LAN driver 84. A tile server application (FSA) 86 exists
`on the computer 18 which is operably connected to both the
`NTL 82 and FSI 72.
`It should be noted that one skilled in the art can modify 30
`the basic network computer
`to accomplish the objects set
`forth herein and that such moditications are believed to fall
`within
`the
`scope
`of
`the
`claims
`appended
`hereto.
`Alteroatively,
`for example,
`the cacbe verifying agent 54
`could reside as part of the communication server 16 or as a 35
`stand alone processor with its own memory and operating
`system. Still, other persons skilled in the art will appreciate
`tbe verifying agent can be implemented in otber manners to
`accomplish the goals set forth herein.
`The operation of the system is as fnllows and as repre-
`seated in FIGS. 3-15. The operations discussed hereafter
`assumes connections have been made among all computers
`12, 14 and 18 and communication server 16.
`On the remote client computer, AP 46 makes requests
`from a tile server wherein the NFC 42 will intercept a file 45
`system call 100 from the AP 46 and query whether the object
`to be acted upon is "remotely located?" 102. If the answer
`is no, the NFC 42 "instructs" 104 the LFS 28 to handle the
`object request. If yes, the type of request
`is ascertained and
`handled accordingly as follows.
`the NFC
`In the case of OPEN or CREAfE 106 requests,
`42 follows the operation under 200. The NFC 42 "invokes"
`202 the NFR 36 to process the request. The NFR 36 asks
`"whether
`there is a good status" 204 for the request. If no,
`NFR 36 "returns" 205 the results of the operation to AP 46.
`If yes, the NFR 36 assigns a handle thereto and the NFC 42
`"builds and sends" 206 an OPEN/CREATE request
`to CVA
`54 via NTL 38 which triggers operation 250.
`CVA 54 "opens" 252 a tile specified in OPEN/CREATE
`request via FSI 62, NFR 62 and NTL 66. The CVA 54 asks
`"whether
`there is a good status on the tile?" 254. If the
`answer is no, CVA 54 "sends" 256 the bad response back to
`NFC 42 in a reverse channel. If the answer is yes, CVA 54
`"assigns a handle to the object" 258 and "sends" 260 a good
`response via a reverse channel.
`the response" 208 from
`NFC 42 via NTL 38 "receives
`CVA 54 and "asks for a good status?" 210. If the answer is
`
`6
`no, the NFC 42 "returns the results of the original OPEN/
`CREATE request" 216 to AP 46. If the answer is yes, then
`the NFC 42 "associates 212 the handle assigned by the CVA
`54 with the handle returned by the NFR 36 in nperation 202.
`Tbe NFC 42 "updates" 214 the network tile cache via LFS
`28 and "returns the results obtained by NFR 36" 216 to AP
`46 via FSI 26.
`the computer 12
`In the case of a READ 108 requests,
`follows the nperation 300. Via the FSI 26 and LFS 28, the
`10 NFC 42 "determines if the requested data is in cache?" 302.
`If the answer is no, a subquery becomes "is the data locked?"
`304. To this subquery,
`if the answer
`is no,
`the NFC 42
`"retrieves" 306 the data via NTL 38 from the file server
`computer 18 and tbe NFC 42 "updates" 308 tbe network tile
`cacbe via LFS 28. If the answer to the subquery is yes, the
`NFC 42 via the NTL 38 "sends" 310 a READ request
`to
`CVA 54 which triggers 380. CVA 54 via the FSI 62 "reads"
`382 the data from the file server computer 18. The CVA 54
`"sends" 384 a response back to NEC 42, wherein the data is
`"received" 312 and "updated" 308 as described above. The
`retrieved data is "returned" 314 by the NFC 42 to AP 46.
`If the data is in cache, NFC 42 is triggered to "invoke"
`316 the BSG 44 to generate a signature of data. NFC 42 via
`NFR 36 and NTL 38 "sends" 320 a VERIFY request having
`the first signature of data therein to CVA 54 which triggers
`350.
`CVA 54 via FSI 62 "reads" 352 data from the file server
`computer 18. CVA54 "invokes" 354 BSG 56 to generate a
`second signature of data. CVA 54 "invokes" 356 comparator
`58 to compare the first and second signatures of data and
`"asks whether
`there is a match?" 358. If the answer is no,
`CVA 54 "asks if data is locked?" 360. If no, the CVA 54
`"sends" 362 back a bad response to NFC 42 via a reverse
`cbannel. If yes, CVA 54 "sends" 364 back a bad response to
`NFC 42 along with read data via a reverse channel. If there
`is a match of the signatures, CVA 54 "sends" 366 a good
`response back to NFC 42 via NTL 66.
`The NFC 42 receives 322 the response from CVA 54 and
`asks "is the data valid?" 324. If no, NFC 42 asks "is the data
`locked?" 326. If not locked,
`the NFC 42 retrieves data 306
`as described above. If locked, data will have been "returned"
`328 for updating per 308. If the data was valid, NFC 42
`returns the data to AP 46.
`the computer 12
`In the case of a WRITE 110 request,
`follows the operation 400. TI,e NFC 42 "asks is the data
`locked?" 402. If no, the NFR 36 is invoked to "write" 404
`to the file server computer 18. If the data is locked, NFC 42
`via NTL 38 "sends" 406 a WRITE request to CVA 54 which
`triggers 450. CVA 54 "writes"
`452 data to tile server
`computer 18 via FSI 62. CVA 54 "sends" 454 back a
`response to NFC 42 which "receives" 408 the response. The
`NFC 42 "asks is the data in cache?" 410. If no, LFS 28
`"reports status" 412 to AP 46. If yes, NFC 42 "updates" 414
`network cache via LFS 28 and "reports status" 412 to AP46.
`In the case of LOCK/UNLOCK 112 request, operation
`500 is employed. The NFC 42 "builds" 502 an LOCK!
`UNLOCK request. The NFC 42 via NTL 38 "sends" 504 the
`LOCK/UNLOCK request
`to CVA 54 which triggers opera-
`tion 550. CVA 54 "sends" 552 an LOCK/UNLOCK request
`to the tile server computer 18 via FSI 62. CVA 54 "sends"
`554 a response back to NFC 42 via a reverse channel. The
`NFC 42 "receives" 506 the response and "returns" 508 the
`results to AP 46.
`In the case of a CLOSE 114 request, operation 600 is
`employed. The NFC 42 "builds" 602 a CLOSE request. The
`NFC 42 via NTL38 "sends" 604 the CLOSE request to CVA
`
`25
`
`40
`
`50
`
`55
`
`60
`
`65
`
`Page 16 of 21
`
`

`
`5,835,943
`
`7
`54 which triggers operation 650. CVA 54 "performs" 652
`internal processing of the request. CVA 54 "sends" 654 a
`response back to NFC 42. The NFC 42 "receives" 606 the
`response and invokes tbe NFR 36 to "close" 608 the file and
`"return" 610 the results to AP 46.
`In the case of a DIRECTORY REQUEST 115, operation
`700 is employed. Here, the NFC 42 "processes" 701 a first
`directory sub-object
`request.
`If the sub-object
`is not a first, NFC 42 "retrieves" 703 the
`next directory sub-object
`from cache via LFS 28. NFC 42
`"asks" 704 whether this is the last sub-object from cache via
`to AP 46. If
`LFS 28? If no, NFC "returns" 705 a sub-object
`yes and it is the last sub-object, NFC 42 "returns" 706 a "no
`more objects" status to AP 46.
`tbe NFC
`If the sub-object
`is tbe first directory sub-object,
`42 "determines"
`iftbe requested object is in cache 702. If no,
`the NFC 42 "sends" 710 a directory verify request
`to CVA
`54 via NTL 38. This triggers the steps 750 and NFC 42 waits
`to "receive" 711 signature from CVA54.As
`seen in FIG. 16,
`tbe steps 750 are performed by the CVA 54. Particularly,
`the
`DSG 57 "initializes" 751 signature of a directory. The DSG
`57 "retrieves" 752 the first directory sub-object
`from the FS
`18 via NTL 66. The DSG 57 "asks" 753 is this the last
`sub-object? If no, DSG 57 "factors" 754 the signature of this
`sub-object
`into the overall signature of tbe directory. The
`
`8
`DSG 57 then "retrieves" 755 the next sub-object from FS 18
`and returns
`to step 753.
`If the last sub-object, CVA 54
`"sends" 756 back signature of directory to NFC 42 at block
`724 and proceeds tberefrom.
`If yes and in cacbe, the NFC 42 "retrieves" 719 signature
`associated with this directory request
`from cache via LFS
`28. NFC 42 "sends" 720 directory verify request
`to CVA 54
`via NTL 38. This triggers the steps 750 wherein NFC 42
`waits and "receives" 721 signature from CVA 54. NFC 42
`722 DSC 46 to compare whether
`signature
`10 "invokes"
`matches
`the retrieved signature
`in 719? If yes and the
`signatures match, NFC 42 "returns" 723 the first sub-object
`from cache via LFS 28 and returns it to AP 46. If no and the
`signature does not match, NFC 42 "invokes" 724 NFR 36 to
`15 retrieve tbe first directory sub-object. NFC 42 "stores" 725
`the sub-object
`into cache via LFS 28. NFC 42 "asks" 726
`whether this is tbe last sub-object? If no and it is not the last
`the next
`sub-object, NFC 42 invokes NFR 36 to "retrieve"
`directory sub-object and returns to step 725. If yes and it is
`tbe last sub-object, NFC 42 "stores" 728 the signature
`obtained via 721 or 711 into cache via LFS 28. NFC 42
`"returns" 729 first sub-object
`from cache via LFS 28 and
`returns the same to AP 46.
`By way of example,
`the following packet formats define
`tbis client server protocol:
`
`20
`
`II
`II TYPE DEFINITIONS
`II
`
`II
`'pCVP _START_CONNECnON_REQ;
`
`(octet) unsigned
`BYTE => an 8 bit value
`important
`is not
`byte ordering
`DWORD => a 16 bit value in which network
`byte ordering
`WORD => 32 bit value in which network
`is not
`important
`MDWORD => 32 bit value in which network byte ordering
`is important
`using "motorola"
`or "big endian"
`format
`II S1ART CONNECTION REQUESr
`typedef
`struct {
`BYTE bFunctionCode;
`BYTE hResv;
`II
`WORD wSequenceV