United States Patent
`
`[19]
`
`[11] Patent Number:
`
`5,835,943
`
`
`Yohe et al.
`[45] Date of Patent:
`*Nov. 10, 1998
`
`U8005835943A
`
`[54] APPARATUS AND METHOD FOR
`INCREASED DATA ACCESS IN A NETWORK
`FILE ORIENTED CACHING SYSTEM
`
`[75]
`
`anentorS: Thomas Patrick YOhe, CenterVille;
`.
`Gordon L. Dorworth, Spring Valley,
`.
`.
`.
`.
`bOth 0f Oh10> J0“ J- P9111199 Ausmh
`560“ HEI‘tZOg, Round ROCK both 0f
`TeX~
`
`5,226,143
`............................. 711/145
`7/1993 Baird et al.
`5,261,069
`11/1993 Wilkinson et al.
`.
`..... 711/145
`
`
`5,274,787 12/1993 Hirano et al. ............ 711/143
`.......................... 711/144
`5,276,835
`1/1994 Mohan et al.
`
`5,297,269
`5,301,290
`5 394 555
`,
`,
`5,404,483
`5,428,761
`5,452,447
`
`3/1994 Donaldson et al.
`.................... 711/145
`4/1994 Tetzaff et al. ............ 711/142
`
`2
`/1995 Hunter et al.
`..... 711/148
`4/1995 Stamm et al.
`..... 711/144
`
`6/1995 Herlihy et al.
`..... 711/130
`9/1995 Nelson et al.
`.......................... 707/205
`
`[73] Assignee: Stampede Technologies, Inc., Dayton,
`Ohio
`
`.
`Primary Examiner—Krisna Lim.
`Attorney, Agent, or Firm—R. William Graham
`
`,
`[ * ] Not1ce:
`
`,
`The term of this patent shall not extend
`beyond the expiration date of Pat. No.
`5,682,514.
`
`[21] Appl. No.: 888,311
`.
`Flled:
`
`[22]
`
`Jul. 3: 1997
`
`[63]
`
`_
`_
`Related U'S' Appllcatlon Data
`,
`,
`,
`Cont1nuat10n—1n—part of Ser. No. 565,393, Nov. 30, 1995,
`Pat. No. 5682514.
`5,
`’
`...................................................... G06F 12/08
`..................... 711/118; 711/122; 395/200.33;
`395/20009
`[58] Field of Search ......................... 395/20047, 200.49,
`395/200.33, 200.09; 711/144, 118, 122
`
`Int. Cl.
`[51]
`[52] US. Cl.
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`[57]
`
`ABSTRACT
`
`An apparatus for increased data access in a network 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
`d.
`1.
`h
`-
`-
`1rectory, a remote c 1ent computer
`avmg an operating
`system, a first memory, a cache memory and a processor
`Wlth 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.
`
`4,410,944 10/1983 Kronies ................................... 711/147
`
`5,222,224
`6/1993 Flynn et al.
`..
`711/144
`
`12 Claims, 12 Drawing Sheets
`
`1'0
`)
`
`OHS 24
`
`12_
`
`36
`
`
`
`
`
`
`
`Cache Verifying Computer 14
`Remote Client
`
` Cache Verifying Agent 54
`Application
`
`
`
`
`Comparator
`Block Signature
`Directory Signature
`
`
`
`
`58
`Generator
`56
`Generator
`57
`
`Programs 46
`
`
`
`
`
` Network
`66
`
`File System Interface
`26
`
`File System Interface 62
`
`Transport
`
`
`
`
`
`Layer
`
`
`Local
`28
`Network 42
`
`File
`Network 54 OHS
`File Cacher
`File
`
`
`
`Network
`Syslem
`43
`
`LAN 68
`Redirector
`60
`Driver
`
`
`File
`Directory
`
`Redirector
`Gamer
`
`
`
`
`
`'
`1
`File Server Computer
`13
`
`4‘; Block
`
`e‘egnr'éiéiéer
`Network
`Prevfetch
`
`
`
`
`
`Transfer
`Data
`45
`Hit
`Layer
`37
`Ratio
`
`
`
`Analyzer
`38
`
`46 Directory
`
`
`40
`Signature
`20
`
`
`empmmr
`WAN Driver
`
`
`
`
`
`
`
`
`
`
`30
`
`Ram
`gift!
`Cacher
`
`32
`Disk Driver
`
`
`
`34
`
`22
`
`Permanent
`Storage
`
`Communication
`
`Sewer
`16
`Routing
`
`Layer 52
`
`LAN 50
`WAN 48
`78 Disk Driver
`Driver
`Driver
`
`
`
`Permanent
`Storage
`MICROSOFT
`
`File Sewer
`86
`
`Application
`
`
`
`72
`File System
`
`
`Network
`Interface
`
`Transport
`Layer
`
`
`
`
`
`
`
`
`
`
`EXHIBIT 1006
`
`Page 1 of 21
`
`Page 1 of 21
`
`

`

`US. Patent
`
`Nov. 10, 1998
`
`Sheet 1 0f 12
`
`5,835,943
`
`52%2E
`
`232E
`V_C_l_.3500:me
`
`v—LOEOZ
`
`E853
`
`E26295m
`
`:o_“8__&<
`
`mEEmoi
`
`momtEEE9969E
`
`52.5xw_n_
`
`
`
`omflsmEmcmgwm
`
`vmmmmEmm
`
`.280in
`
`62362”.
`
`womtot:
`
`€0sz
`
`toamcmt.
`
`cozmoEsEEoo
`
`.mEom
`
`mcssom
`
`Lm>m4
`
`z<._z<>>
`
`525525
`
`r.3
`
`.525Z<>>
`
`EEOUEocmctmm
`v7.3”.69on
`
`Page 2 of 21
`
`Locomo
`
`:o_umo__qq<L964me
`
`5inBE55cm;Emanommm
`
`
`
`x5502coumhén.Ema
`
`Page 2 of 21
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Nov. 10, 1998
`
`Sheet 2 0f 12
`
`5,835,943
`
`
`3$5950.35th228
`orNFEgoEoEmm
`
`
`
`
`
`m:55an0.wtwwo__n_
`
`Nx.
`
`£296of.
`
`momtEE{02,52
`
`toqmcmt.
`
`Lw>m4
`
`Eammof.
`
`8:332
`
`Emcmctmn.
`
`@9205
`
`525v7.52
`
`ucmmmEma
`
`558in625
`
`5{0362
`
`2E_
`
`560.:vammz<._
`
`mm#6382
`
`toqwcmc.
`
`5%..
`
`
`
`Emm<952$280
`
`2.4....mmLmN>_m:<
`
`B>8mm5m1.:1
`
`Emahmhwcmfi5:80
`
`
`
`
`om.9855cmxwfi:uwn_€02sz9:5:ngumwmm
`
`x5...—bofimza0v
`
`omS928%mm
`525z<>>$25inLEEmano
`
`mmmomtBEE9962E
`
`ow
`
`cosmo=aa<
`
`mEEmoi
`
`{oémz
`
`
`
`590$:me.6580mi39095
`
`N¢{0262
`
`5882E
`
`
`
`xogm.3.Ema
`
`cosmoEzEEoo
`
`
`
`m:52%mm
`
`omZ<._avZ<>>
`
`95E5N.9”.
`
`
`
`mESomEmcmEBQ
`
`
`
`$53..$955
`
`Page 3 of 21
`
`Page 3 of 21
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Nov. 10,1998
`
`Sheet 3 0f 12
`
`5,835,943
`
`NFC 42
`Intercept File System
`Call from AP 46
`
`é
`
`03?"
`Create
`
`Yes
`
`No
`
`Read
`
`No
`
`No
`
`No
`
`é?
` Fig. 3
`
`W N
`
`o
`
`Allow Network
`File Redirector
`to Handle
`
`Page 4 of 21
`
`Page 4 of 21
`
`

`

`US. Patent
`
`Nov. 10,1998
`
`Sheet 4 0f 12
`
`5,835,943
`
`Happens on 12
`
`Application Request
`
`Invoke NFR 36 to Process
`
`
`
`
`
`
`
`
`NFR 36
`Return Results of
`O erat'
`t AP 46
`p
`Ion o
`
`
`NFR 36
`asks for
`Good Statu
`
`
`
`No
`
`
`
`
`
`Yes
`
`NFR 36 Assigns Handle and
`NFC 42 Builds Open/Create
`Request and Sends it to CVA 54
`This Triggers 250
`
`Response
`
`NFC 42
`Wait for 14
`
`Good
`Status
`
`No
`
`W
`
`NFC 42
`Returns Results
`
`of 202 to AP 46
`
`Yes
`
`NFC 42 Associates
`"Handle" Assigned by
`
`
`CVA 54 with Handle
`returned in 202
`
`
`NFC 42
`
`Cache via LFS 28
`
`Updates Network File
`
`Fig. 4
`
`Page 5 of 21
`
`Page 5 of 21
`
`

`

`US. Patent
`
`Nov. 10, 1998
`
`Sheet 5 0f 12
`
`5,835,943
`
`Happens on 14
`
`
`
`OVA 54 Opens File Specified
`in Open/Create
`Request via FSI 62
`
`
`
`
`
`OVA 54 Sends Back Bad
`Response to NFC 42
`
`
`
`Assigns a "Handle" to
`this Object
`
`
` OVA 54
`
`
`Send Good Response
`
`
`Page 6 of 21
`
`Page 6 of 21
`
`

`

`US. Patent
`
`Nov. 10,1998
`
`Sheet 6 0f 12
`
`5,835,943
`
`-2
`
`
`
`
`
`NFC 42
`
`NFC 42
`Determines
`
`lnvokes BSG 44 to
`
`
`if Requested
`
`Obtain Signature
`Data is in
`
`
`Cache
`
`
`
`NFC 42 Sends Verify
`Request to CVA .54
`via NTL 38
`
`
`
`
`NFC 42
`
`322
`from CVA 54
`
`
`
`
`asks Was
`RNFS :2 Send:
`
`9
`ea
`eques 0
`
`
`Data Locked.
`CVA 54
`
`
`
`This Triggers 350. Wait
`NFC 42 Receives Data
`
`
`
`This Triggers380. Wait
`NFC 42 Receives Data
`
`from CVA 54
`
`
`
`
`NFC 42 Retrieves
`
`Data from File Server
`
`Computer 18
`
`
`
`
`NFC 42
`
`
`Data will have
`
`Updates Network File
`
`
`been Returned
`Cache via LFS 28
`
`in ReSponse
`
`
`
`NFC 42
`
`
`Return Data to AP46
`
`
`Fig. 6
`
`Page 7 of 21
`
`Page 7 of 21
`
`

`

`US. Patent
`
`Nov. 10,1998
`
`Sheet 7 0f 12
`
`5,835,943
`
`12
`
`
`CVA 54
`
`Reads Data from
`
`
`File Server Computer 18
`
`
`
`CVA 54
`
`
`Invokes 386 56
`
`
`to obtain Signature
`of Data
`
`CVA 54 Invokes Comparator 55
`to Compare Signature
`with that found in
`Verify_Req.
`
`
`
`
`
`
`CVA 54
`
`
`
`asks if there
`
`is a Match
`
`
`
` CVA 54 Sends BAD Response
`
`CVA 54 Sends Back
`CVA 54 Sends Back
`
`
`and includes the Just Read
`
`Good Response
`Bad Response
`
`
`
`Data in the Response
`to NFC 42
`to NFC 42
`
`
`
`to NFC 42
`
`
`Fig. 7
`
`CVA 54 Reads Data from
`File Server Computer 18
`
`
`
`
`
`
`CVA 54 Sends Back
`
`
`
`
`
`Response to NFC 42
`
`Fig. 8
`
`Page 8 of 21
`
`Page 8 of 21
`
`

`

`US. Patent
`
`Nov. 10,1998
`
`Sheet 8 0f 12
`
`5,835,943
`
`NFC 42 Sends
`
`
`invoke NFR 36 to
`
`
`Write_Request
`Write Data to
`
`
`
`File Server Computer 18
`
`
`
`
`
`
`
`This Triggers 450. Wait
`NFC 42 Receives
`Response
`
`
`NFC 42
`
`
`asks is Data
`
`in Cache?
`
`
`
`
`
`
`
`NFC 42 Updates Network
`Cache via LFS 28
`
`
`
` LFS 28 Reports
`
`Status to AP 46
`
`
`CVA 54 Writes Data
`toFiie Server
`Computer 18
`
`Back Response
`
`CVA 54 Sends
`
`Page 9 of 21
`
`Page 9 of 21
`
`

`

`US. Patent
`
`Nov. 10, 1998
`
`Sheet 9 0f 12
`
`5,835,943
`
`
`
` OVA 54
`Sends Lock/Unlock
`
`Request to File Server 18
`via FSI 62
`
`
`
`NFC 42 Builds
`Lock / Unlock
`Request
`
`NFC 42 Sends to
`CVA 54
`
`This Trig er 550. Wait
`NFC 4 Receives
`from OVA 54
`
`
`
`NFC 42
`Return results
`to AP 46
`
` OVA 54
`
`Sends Back
`
`
`Response to
`12 via FSI 62
`
`
`
`
`Fig. 11
`
`Fig. 12
`
`Page 10 of 21
`
`Page 10 of 21
`
`

`

`US. Patent
`
`Nov. 10,1998
`
`Sheet 10 0f 12
`
`5,835,943
`
`NFC 42 Builds
`Close_Request
`
`NFC 42 Sends
`to CVA 54
`
`This Trigger 650. Wait
`NFC 42 Receives
`from CVA 54
`
`
`
`NFC 42 Invokes
`NFR 36 to
`close the file
`
`NFC 42
`Returns results
`to AP 46
`
`Fig. 13
`
`CVA 54
`Performs internal
`Processing
`
`to NFC 42
`
`CVA 54 Sends
`Back Response
`
`Fig. 14
`
`Page 11 of 21
`
`Page 11 of 21
`
`

`

`US. Patent
`
`Nov. 10,1998
`
`Sheet 11 0f 12
`
`5,835,943
`
`
`
`
`NFC 42 Retrieves
`
`NFC 42
`
`NFC 42 Sends
`
`
`
`
`signature associated
`
`Directory Verify
`Determines if
`Processes
`-
`-
`-
`
`
`
`Requested Object
`Directory
`rzv'fi‘efl'?rg:1eg%fie
`Request to
`
`
`
`
`via LFS 28
`CVA 54 via NTL 38
`Sub-Object
`is In Cache
`q
`
`
`NFC 42 Retrieves
`NFC 42 Sends
`
`
`Next Directory
`Directory Verify
`
`
`
`Request to
`Sub-Object from
`
`
`Cache via LFS 28
`OVA 54 via NTL 38
`
`
`
`
`This triggers 750
`
`Wait.
`
`NFC 42 Receives
`
`Signature from .
`CVA 54
`
`
`
`
`
`
`
`
`Is this the last
`nfimgé'Bng-‘Qfsn
`
`Sub-Object?
`Status to Ap 46
`
`
`
`NFC 42 Returns
`Does
`
`
`First Sub-Object from
`signature
`
`
`Yes
`cache via LFS 28
`match what was
`
`
`
`and 1:311:63 it to
`retrifiisgd in
`
`
`
`
`NFC 42 Invokes
`
`
`This tri
`ers 75o,
`NFR 36 to retrieve
`
`
`
`NFC 42 Returns
`Vii/gait.
`first directory
`
`Sub— Object
`, Sub-Object
`NFC 42 Receives
`
`
`
`to AP 46
`Signature from
`CVA 54
`
`
`the Sub-Object
`into cache via
`LFS 28
`
`via LFS 28
`
`Store signature
`obtalned .'" either 721
`
`NFC 42 Returns
`First Sub— Object from
`cache via LFS 28 and
`returns it to AP 46
`
`Fig. 15
`
`Is this the
`
`or 711 Into cache
`last Sub-Object?
`
`Yes
`
`
`
`
`, . . ‘
`.
`t
`NFR 36 to retrieve
`next directory
`Sub-Object
`
`
`Page 12 of 21
`
`Page 12 of 21
`
`

`

`US. Patent
`
`Nov. 10,1998
`
`Sheet 12 0f 12
`
`5,835,943
`
`Initialize Signature
`0
`Directory
`
`
`
`
`
`Retrieve first directory
`Sub-Object from File Sewer
`
`Computer 18
`
`
`
`Is this
`
`
`the last
`
`
`
`
`Sub-Object?
`
`
`
`Retrieve the next
`
`Factor the signature of this
`
`
`Directory Sub-Object
`Sub-Object into the overall
`
`
`from File Server 18
`
`Signature of Directo
`
`
`
`OVA 54 Sends Back
`
`
`Signature of Directory
`
`to NFC 42
`
`
`Fig. 16
`
`Page 13 of 21
`
`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 US. Ser. No. 08/565,393
`filed Nov. 30, 1995 which has now issued as US. Pat. No.
`5,682,514 issued on Oct. 28, 1997.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`invention relates to data access in a file
`The present
`oriented network system. More particularly,
`the present
`invention is directed to a client-agent-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
`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).
`In addition, there also eXist problems with verification of
`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
`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
`cache program, such as Microsoft’s SmartDrive is a useful
`tool
`to increase performance from the random access
`memory (RAM),
`this type of caching technique is not
`applicable to remote environments because of its inability to
`correctly handle multiple remote clients accessing the same
`data files concurrently, i.e., it is likely to corrupt the data.
`File servers have employed caching techniques which
`parallel
`techniques of the desktop. Here,
`the file server
`deviates in protecting against multiple common data user
`access by implementing or providing a file locking service
`to clients.
`
`As shown in FIG. 1, the related art includes a remote
`client computer having an operating system (OS) with 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 the 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 the OS via the
`FSI. A communication server (CS) connects to the remote
`client computer and includes a WAN driver, routing layer
`and LAN driver.
`
`The CS connects through a LAN link to a file server
`computer having an OS. The file server computer OS
`includes an NTL connected to a LAN driver and an FSI
`
`2
`connected to LFS which in turn is connected to an RBDC,
`a DD and a PSD. Aside from the OS, there eXists a file server
`application which employs the OS via the FSI.
`The problem associated with these prior systems is their
`inability to provide a remote client user with 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 the data through, such as a
`modem phone link. In the context of the present invention,
`“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. This is contrasted with a
`link in a LAN connection which can transfer at about 10
`
`Megabits per second. These remote clients are thus greatly
`limited in speed of access.
`
`SUMMARY OF THE INVENTION
`
`The present invention overcomes the above described
`deficiencies which eXist with remote clients accessing and
`verifying data in files and directories from a file oriented
`network environment.
`
`5
`
`10
`
`15
`
`20
`
`It is an object to increase the speed in which a remote
`client can access data and directories.
`
`25
`
`It is another object to maintain integrity of the accessed
`data and directory while increasing the speed in which the
`data is accessed.
`
`A further object is to implement an agent to act as a
`caching verifier between a remote client and a file server
`computer.
`Still, another object is to add intelligence to a remote
`client in order to reduce the overall time in which a remote
`client accesses data.
`
`Another object is to overcome the deficiencies of data
`transfer for a remote client.
`
`Other objects and advantages will be readily apparent
`from reading the following description and viewing the
`drawings.
`Accordingly, the present invention is directed to an appa-
`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 on 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
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 14 of 21
`
`Page 14 of 21
`
`

`

`5,835,943
`
`3
`client computer and for obtaining a lock on the data from the
`file server computer in response to the LOCK request.
`
`Terminology
`
`“Permanent storage memory,” as used herein, includes,
`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
`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 which 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 the block diagram configuration of the
`related art.
`
`FIG. 2 illustrates the 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
`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 chart of the operations of the
`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
`the present invention corresponding to READ requests in the
`cache verifying computer.
`FIG. 9 illustrates a flow chart of the operations of the
`present
`invention corresponding to WRITE requests on
`remote client computer.
`FIG. 10 illustrates a flow chart of the operations of the
`present
`invention corresponding to WRITE requests on
`cache verifying computer.
`FIG. 11 illustrates a flow chart of the operations of the
`present
`invention corresponding to LOCK requests on
`remote client computer.
`FIG. 12 illustrates a flow chart of the operations of the
`present invention corresponding to LOCK requests on cache
`verifying computer.
`FIG. 13 illustrates a flow chart of the operations of the
`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
`cache 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
`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 form of
`electrical signals which are manipulated, stored, transmitted,
`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 the 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 method are disclosed which permit the remote
`client computer to reduce the time for accessing such data
`using a cache verifying computer coupled with a caching
`technique.
`The performance gains realized by the present invention
`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.
`Referring now to the FIGS. 2—15, the present invention is
`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
`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, which 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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`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
`
`55
`
`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 file system interface (FSI) 26. Operatively
`connected to the FSI 26 is a local file system (LFS) 28 which
`in turn 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 turn is connected to a WAN driver 40.
`Additionally, the invention includes a network file cacher
`(NFC) 42 which is operably disposed between and inter-
`
`60
`
`65
`
`Page 15 of 21
`
`Page 15 of 21
`
`

`

`5,835,943
`
`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 NTL 38 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 the OS, there eXists on the computer
`12 application programs (AP) 46 which employ the OS 24
`via FSI 26.
`
`The communication server (CS) 16 includes a WAN
`driver 48, a LAN driver 50 and routing layer (RL) 52
`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
`operatively connected to the NTL 66.
`The file 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, a DD 78 and a PSD 80.
`Also, the OS 70 includes an NTL 82 operatively connected
`to a LAN driver 84. Afile 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
`the basic network computer to accomplish the objects set
`forth herein and that such modifications are believed to fall
`
`within the scope of the claims appended hereto.
`Alternatively, for example,
`the cache verifying agent 54
`could reside as part of the communication server 16 or as a
`stand alone processor with its own memory and operating
`system. Still, other persons skilled in the art will appreciate
`the verifying agent can be implemented in other manners to
`accomplish the goals set forth herein.
`The operation of the system is as follows and as repre-
`sented 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 file server wherein the NFC 42 will intercept a file
`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.
`In the case of OPEN or CREATE 106 requests, the NFC
`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 file 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 file?” 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.
`NFC 42 via NTL 38 “receives the response” 208 from
`CVA 54 and “asks for a good status?” 210. If the answer is
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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 operation 202.
`The NFC 42 “updates” 214 the network file cache via LFS
`28 and “returns the results obtained by NFR 36” 216 to AP
`46 via FSI 26.
`
`In the case of a READ 108 requests, the computer 12
`follows the operation 300. Via the FSI 26 and LFS 28, the
`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 the NFC 42 “updates” 308 the network file
`cache 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. CVA 54 “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
`channel. 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.
`
`In the case of a WRITE 110 request, the computer 12
`follows the operation 400. The 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 file 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 AP 46.
`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 file 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 NTL 38 “sends” 604 the CLOSE request to CVA
`
`Page 16 of 21
`
`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 the 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-obj ect from cache via
`LFS 28? If no, NFC “returns” 705 a sub-object to AP 46. If
`yes and it is the last sub-object, NFC 42 “returns” 706 a “no
`more objects” status to AP 46.
`If the sub-object is the first directory sub-object, the NFC
`42 “determines” if the 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 CVA 54. As seen in FIG. 16,
`the 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
`
`10
`
`15
`
`20
`
`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 therefrom.
`If yes and in cache, 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