WWWWMWM
`HWMWWWWM
`USIK16757717BI
`
`United States Patent
`(12)
`(10) Patent NIL:
`US 6,757,717 Bl
`
`Goldstein
`(45) Date of Patent:
`Jun. 29, 2004
`
`($4) SYSTEM AND METHOD FOR IJA'I'A ACCESE
`
`6.2?‘Lt1‘tl
`
`[5] ‘
`
`sump]
`
`linhcr l'I ul.
`
`_ ............... waltz
`
`lnventur: Leonid GuldsteinJ-[eratiMIL]
`(1’5)
`‘
`_
`.
`_
`(73] Asstgnee:
`l‘msndnn, 111$, Irvine. CA (Uh)
`.
`.
`_
`.
`,
`.
`( t ] Ntitiec:
`IEiItJlT-ztui'ltuan}:r ilfilmmfg“ lite‘tierrn (Ill Ill:
`parent
`:5 ”mm L Dr ‘1 ”bl“ "m” ‘
`‘
`U.b.(.. 154tb)l1ytjrlays.
`
`(3|) Nwl- No-I “9598-007
`22
`F'l‘d:
`Se . 16. 1999
`H.
`P
`i
`(
`Int. Cl.
`(51)
`(53) U.S. C].
`
`........................
`
`(553
`
`1119“] "1' 5mm],
`
`.Gllfii' lsflfi
`7097’]? 70?; I; 70M“;
`magm- jogging mg:39
`mg.-31-; gm.
`709:3?) 335 7073.1“ I
`
`(56)
`
`References Cited
`UHS PNi‘ENT DOCUMENIS
`
`'
`
`.._.._.__.._.,...... 7li7a'l
`
`HMO“ (:hnng rt at.
`4.897.7Ht A
`1:19"5 I-‘tt‘tlort'
`5.384.363 A
`IIIII907 Ynilt.’ et HI.
`itifilfild A
`3.:1998 [l'ewill er al.
`3332.36 A
`I “1905 YanJ at al.
`5.535.943 A
`llr'I‘NR Hhide cl at.
`5,952.7 I? A
`[51990 Maimnnl:
`5.fi()4,a_w A
`3:100” Bil'i'lgfl t‘i fll-
`--
`-- TWIN]
`$373113 A '
`
`“Um" lit-“NI t-‘l “L
`W173“!
`T‘s‘W’v-VJ‘J A '
`:13: X: ”Official“ """""" 700.31?
`2': iii-T: 2
`,r
`garwaea.
`.,-.
`fi-‘IUFJU Burnt-i mu.
`71mm
`same-n A -
`
`”“909 lwhfl a “L
`53:78,?01 A
`6.0!]?le A . 1211999 I lunhel cl al.
`__ gin-mm
`h_.t)l'bJLt-t A
`minor, new. fl at.
`(LI-112.035 A
`mum Yaht- r.'t at.
`713.11”;
`(iflJIAtJl A ‘
`l-lt’tflf] Renaud
`
`6173.173 A "
`(tr-3000 Billing“ er al.
`. 7i't7e'i513
`"“8324” A : 7’3“” w‘mg ‘9' “L
`. “HF?"
`film Nd?" H H"
`' “Hf”
`i'Jm 54“ A
`“7227;? A x
`”72000 Yahe m "L
`’ 709-204
`t-.13r1,583 A ' 10.5mm [{erriul
`.‘tm-Jl?
`6.14-8.34“ A ‘
`IIIZIIIIU Billinger el al.
`. 7005203
`H.256fifi4 lit
`*
`‘Hzntll
`launche- £1 at.
`Truth-204
`
`
`
`
`
`..
`
`mum FUN-1mm)“
`RITIZI'IIJR‘. Hypertext Trans-tier Pmmml—ll'l'l'Pfl.l. Jan.
`190?, pp. 0-13, 2945‘ Tit-94, 101433.
`RI-‘C'IDI: Internet Protocol Darpa Internet Program Prolueul
`Specification. Sup. 1981, FP- 3‘ “44‘ 311).
`RFC-4'61: DHD Standard Transmission Control
`Jan.
`'93”, NHL 1547'
`l—ltJ.
`It] 11520: It' Authentication ”cutter, Aug. le. pp.
`Rl-‘CIKM: Tilt:
`(Tut'ttcnI—MDS iltadct‘
`[-‘icltL Oct 1995,
`a
`PW“-
`_
`.
`.
`RI-IT‘ISE‘lz'I‘hu MD) Message—IllgestAlgnnlltrrI-JWI'. 1993.
`pp. 1-21.
`Dave Jingle, Ethernet I-‘rnm: 'I‘ypes. article from lr‘cb. 19%
`issue of LAN Magazine-J'Nelwnrk Magazine, pp.
`t—4.
`W. Richard Stevens.
`'l‘FPt'lP Illustrated. ml. 1. 1994. pp.
`33—37. 143—!47, 213—123.
`
`l’rotncrtl.
`
`“I“! W “9mm"
`['[HNL'Y
`PFIHIIIIT Efflflfllf-M'F—Jaci‘i B.
`Assistant f:.\‘:rrmrter—llal V. Nguyen
`(74) Attorney Agent. or Firm—J.
`I}. Harm-nan, I], Esq;
`(Triuderl Bmlllers [LP
`
`(57)
`
`ABS’I‘RAC'I‘
`
`.
`.
`The :nvenlwn provides a system for data access in .1 packet—
`switched network. includingawudertcomputer including an
`“Pu-rating unit. a first memory, a permanent storage memory
`and a Incinerator and a rentnle receiver.-'compnler including an
`operating unit, a Iirsl memory, a pem‘lanenl alciragc memory
`.
`H,
`.
`‘
`4;“:
`‘fnd “
`[’m‘m‘m’ 73?.“n‘L‘r'cn'rnplufcr “Wkly: r‘fcf'ln‘lr'.
`Ltuntpulur mnlmunteallng t magi] llL nelwnr .
`1. c th‘l-l‘Lf-
`enmputer further Including devtee fur ‘catL-ulalllng (Itgttal
`drgesls tn: data:
`Ilte meewurtemnputer hirther Including a
`network euche memoryr and device for calculating digital
`digusls on data in the network cache memory: and the
`receiverknrnpuler nndkrr
`the aentlera'cuntptlter
`including
`device [L‘II‘ comparison helwuen digital digests. The inven-
`lion also provides a method and apparatus for increased data
`fiCCL‘it-Z in a
`ackut-uwitehetl network
`"
`p
`'
`‘
`'
`'
`
`34 Claims, 9 Ilnlwing Sheets
`
`Sender
`
`Receiver
`i
`
`Calculate diullal digesla
`
`i
`Sand dig'tal dlgasla
`I————-—!
`
`E
`
`i
`
`Search tor principal digest In each.
`
`Seam In: summary ohm In cache
`
`Issue mt“ nr'nagalwo' yams
`
`| :
`
`titaniumW signal - 99'ch the WWW
`
`MICROSOFT
`MICROSOFT
`Dem. EX. 1029
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IPR2012-00026
`EXHIBIT 1002
`IPR 2013-00109
`
`Page 1 of 19
`Page 1 of 19
`
`
`
`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`US 6,757,717 131
`
`1
`SYSTEM AND METHOD FOR DATA ACCESS
`
`RELATED APPLICATION
`
`This application claims priority and is entitled to the tiling
`date of Israeli application Ser. No. 126292 filed Sep. 18,
`1993. and entitled "System And Method For Data Access,"
`and which describes the same invention as defined herein.
`
`FIELD OF THE INVENTION
`
`The present invention relates to data access in networks.
`Specifically,
`the invention is concerned with a method,
`system and apparatus for increasing the speed ol data
`accessing in communication networks.
`BACKGROUND OF THE INVENTION
`
`Many known applications and protocols provide means
`for caching and verifying ot'data transmitted via a network
`2 (FIG. 1, prior art}. Thus, a client (receiver) 4 caches data
`received from network 2 in cache 6. Then, when data from
`a remote server (sender) 8 is requested, it first searches its
`local cache. If the requested data is available in the cache
`and is verified to be valid, the client uses it, and transmission
`over the network is not required. Gateway or proxy caches
`100316. 2, prior art) are able to operate in a similar manner.
`The most well-known techniques are as follows:
`I) In response to a request from a receiver, a sender attaches
`to the sent data an expiration time in absolute or relative
`form. The receiver. and possibly proxies. cache the data
`together with its request until the expiration time. Then
`the data is retrieved from the cache. In some cases, the
`receiver guesses the expiration time.
`The problem associated with this technique is that the data
`entity can he changed before the expiration time. and the
`receiver would use an ohsolctu version of the data without
`even knowing it. Also, when the time has expired, the data
`will be resent, even if it is up to date.
`the sender
`2)
`in response to a request
`from a receiver.
`attaches a validator to the sent data. The validator changes
`at
`least every time the data changes:
`in many cases,
`system time is used as the vatidator. The receiver, and
`possibly proxies, cache the data together with its request.
`When making the next request for the same data to the
`same sender,
`the receiver includes the vaiidator. The
`sender keeps track of the data and rescnds it only it'it were
`changed.
`The problems associated with this technique are:
`a) Data is cached according to requests and senders. if the
`same request
`is directed to difl'erent servers, cached
`data cannot be mused.
`b) Requests without concretc data cannot be cached.
`c) The sender must track the cached data, which is not
`always possible.
`None of the prior art techniques discussed above provides
`means for transmitting minor differences in data.
`Additionally, if data is retrieved through a caching proxy.
`there is a danger that an unauthorized user will have access
`to the data.
`It is therefore a broad object of the present invention to
`provide a method, system and apparatus for increasing the
`speed of data access in a packet-switched network.
`Another object of the present invention is to decrease data
`traffic throughout the network.
`Still another object of the present invention is to decrease
`the required cache size.
`
`2
`Ayet further object of the present invention is to maintain
`accessed data integrity and to improve security.
`SUMMARY OF THE INVENTION
`
`5
`
`IU
`
`JS
`
`ll]
`
`35
`
`41]
`
`SH
`
`55
`
`till
`
`[IS
`
`
`
`The terms “data" or "data object" as used herein refer to
`a tile or range ot'octets in a file, a range oft'ramcs in a video
`stream or RAM-based range of octets. a transport
`level
`network packet, or the like.
`"the term “digital digest" as used herein refers to a
`fixed—size binary value calculated from arbitrary-size binary
`data in such a way that it depends only on the contents oflhe
`data and the low probability that two different data or objects
`have the saint: digital digest.
`The term “gateway" as used herein also includes network
`proxies and routers.
`a sen-ertcomputer in a networ
`to another receivertcornputer, and the rceeivericomputer has
`data with the same digital digest as that ol’ the data to be sent,
`it can he assumed with sufficient probability for most
`practical applications that
`the rcccivericomputer has data
`which is exactly the same as the data to be sent. Then. the
`receivertcomputer can use the data immediately without its
`actual transfer through the network. In the present invention,
`this idea is used in a variety of ways.
`In one embodiment of the inVcntion. a senderimmputer
`reguired to send data to a
`receivertcomgulcr computer
`initially sends a dig ital digest of the data. If the receiver:r
`computer already has data with the same digital digest, it
`uses this data as if it were actually transmitted from the
`sendcricomputcr. Additionally, digital digests for other data
`objects can be sent together with the principal digest. if the
`receivertmmputcr cannot
`find data having the principal
`digest, it searches for data with one of these auxiliary
`digests. If such data is found,
`the sendcrfcomputer
`is
`required to send only Lhe diil'crunce between the requested
`data object and the data object corresponding to the digest.
`The expression "dili'ference between a first data or data
`object and a second data or data object" as used herein
`means any bit sequence that enables the restoration of the
`first data. given the second data, the hit sequence and the
`method employed in calculating the dill‘erencc.
`The invention may be implemented in a gateway system.
`Such a system comprises a gateway computer connected to
`a packet-switched network in such a way that network
`packets sent between at
`least
`two other computers pass
`through it; a caching computer connected to the gateway
`computer,
`the caching computer having a network cache
`memory in its permanent storage memory. means for cal—
`culating a digital digest on the data it stores and means for
`comparison between a digital digest calculated on data in its
`network cache memory and a digital digest received From
`the packet-switched network by the gateway computer.
`When this system intercepts an indication signal other than
`a positive indication signal for a certain digital digest from
`a rcccivert’compnter computer, if it has data with the same
`digest, it sends this data to the reecivericomputcr.
`In another embodiment of the present invention, a client
`computer sends to a server computer a request including
`digital digests. A sendcricornputer forming a response then
`searches for data with the same digital digests as those
`received. If the digest of the data in the response equals one
`of the received digesLs. the server only sends confirmation.
`lithe digest of another data is identical to one of the received
`digests, only the difl'ereuce(s) between these data is sent.
`In accordancm with the present invention. there is there-—
`fore provided a system for data access in a packet—switched
`
`
`
`
`
`
`!
`
`
`
`
`
`
`
`
`
`"
`
`
`
`
`#
`
`
`
`$
`
`
`
`
`
`!
`
`%
`
`
`
`
`initiate
`
`Sender may
`
`&
`
`
`
`
`
`
`
`
`
`Page 11 of 19
`Page 11 ofl9
`
`

`

`US 6,757,717 131
`
`3
`network, comprising a sendencomputer including an oper-
`ating unit, a first memory. a permanent storage memory and
`a processor and a remote receivcrfcomputcr including an
`operating unit, a first memory, a permanent storage memory
`and a processor, said sendertoomputer and said receiver;r
`computer communicating through Said network; said sender,Ir
`computer Further including means for calculating digital
`digests on data; said receivert'eomputer further including a
`network cache memory and means for calculating digital
`digests on data in said network cache memory: and said
`receiverfcomputer andior said sendert’computer including
`means for comparison between digital digests.
`The invention also provides a system for data access in a
`packetswitched network. comprising a gateway computer
`including an operating unit, a memory and a processor
`connected to said packet-switched network in such a way
`that network packets sent between at least two other com-
`puters pass through it: a caching computer including an
`operating unit, a first memory. a permanent storage memory
`and ti pmcussor connected to said gateway camputer through
`a fast local network; said caching computer further including
`a network cache memory in its permanenl storage memory,
`means For calculating a digital digest on data stored therein
`and means for comparison between a digital digest calcu—
`lated on data in its network cache memory and a digital
`digest received from said packet-switched network through
`said gateway computer.
`In addition.
`the invention provides a system for data
`access in a packet-switched network, comprising a senrlcnr
`computer including an operating unit, a first memory, a
`permanent storage memory and a processor and a remote
`receivericomputcr
`including an operating unit, a first
`memory, a permanent storage memory and a processor, said
`sendert'computer and said receivert’computcr communicat-
`ing Ilirough a network; said sendericompuler f‘unller includ—
`ing means for calculating digital digests on data, and said
`receiven’computer further including a network cache
`memory. means for storing a digital digest received from
`said netwurk in its permanent storage memory and means
`for comparison between digital digests.
`The invention further provides a method performed by a
`scndcrt’computer in a packet-switched network for increas-
`ing data acceeei. said sendertcomputer including an operating
`unit, a first memory. a permanent storage memory and a
`processor and said sendericomputer being operative to tra ns-
`mit data to a receiverlcomputer, Ibe method comprising the
`steps of transmitting a digital digest of said data from said
`senderfcomputer
`to said rcceivericomputer;
`receiving a
`response signal from said reoeiverlcomputer at said sender!
`computer. said response signal containing a positive. partial
`or negative indication signal for said digital digest, and if a
`negative indication signal is received, Lransmitting said data
`from said scndcrlcomputer to said receiverlcompnter.
`The invention still further provides a method for increas-
`ing data access performed by a sendericomputcr in a packet—
`switched network. said sendericomputer including an oper-
`ating unit, a first memory. a permanent storage memory and
`a processor and said sendeo’enmputer being operative to
`transmit principal data to a receiven’eomputer, said method
`comprising the steps of transmitting digital digests of said
`principal data and of one or more auxiliary data from said
`senderi‘computcr
`to said receivcricompuler; receiving a
`response signal at said senderleomputer from said receivenr
`computer. said response signal containing a positive. nega—
`live or partial indication signal, and it" a partial indication
`signal is received, said sendericomputer transmitting a sig-
`nal constituting the difl'ercncx between said principal dilta
`and corresponding auxiliary data.
`
`ll]
`
`15
`
`dl-[l
`
`50
`
`U:In
`
`(all
`
`as
`
`4
`The invention yet further provides a method for increased
`data access performed by a receiverrcompuler in a packet—
`swilched network. said receivcri’compnter including an oper—
`ating unit. a first memory, a permanent storage memory. a
`processor and :1 network cache memory, said method com-
`prising the steps of receiving a message containing a digital
`digest from said nelWork; searching for data with the same
`digital digest in said network cache memory, and if data
`having the same digital digest as the digital digest received
`is not uncovered, forming a negative indication signal and
`transmitting it back through said network.
`Still
`further,
`the invention provides a method for
`increased data access per[on1‘ted by a remive'ri’compnlcr in a
`pectic-[switched network, said receives-“computer including
`an operating unit, a first memory. a permanent storage
`memory, a processor and a network cache memory, said
`method comprising the steps of receiving a message con—
`taining a digital digest from said network; searching for data
`with the same digital digest in said network cache memory.
`and if data having Ihe same digital digest as the digital digest
`received is uncovered, forming a positive indication signal
`and transmitting it back through said network.
`In addition, the invention provides a method for increased
`data access performed by a receiveri'computer in a packet-
`switched network, said receiveri'compttter including an oper-
`ating unit, a first memory, a permanent storage memory, a
`processor and a network cache memory. said method com—
`prising the steps of receiving a message containing a prin—
`cipal digital digest and one or more auxiliary digital digests
`from said network; searching in predetermined locations in
`said permanent storage memory for data with a digital digest
`substantially identical to said principal digital digest; search—
`ing in predetermined locations in said permanent storage
`memory for data with a digital digest substantially identical
`to one ofsaid auxiliary digital digests; and ildala having the
`same digital digest as one of mid auxiliary digital digests
`received is uncovered, forming a partial indication signal
`and transmitting it back through said network.
`Yet further. the invenlion provides a method for increased
`data access perfomled by a computer system in a packet-
`switched network. said computer system including a not-
`work cache memory and being operationally interposed
`between a sendertcomputer and a receiveri'compuler so that
`data packels sent between said sendericomputer and said
`receiven’computer are delivered through said computer sys-
`tem; said method comprising the steps of intercepting a
`message containing a digital digest
`transmitted from said
`sendericomputer to said receiverfcomputer, and transmitting
`data with a digital digest substantially identical to Ihe digilal
`digest received from said senderlcomputer to said receiverr
`computer.
`In addition, the invention provides a method for increased
`data access performed by a computer system in a packet-
`switched network, said computer system including a net—
`work cache memory and being operationally interposed
`between a senderi'computer and a receiverlcompuler so Ihal
`data packcls sent between said senderloomputer and said
`receiveri’compuler are delivered through said computer sys-
`tem: said method comprising the steps of intercepting a
`message containing a digilal digest transmitted from said
`senderi’computer to said rcoeiverioompuler; intercepting a
`message containing an indication signal other than a positive
`indication signal transmitted from said rcoeivcricompulcr to
`said sendericomputcr in response to said memgc containing
`a digital digest, and transmitting data with a digital digest
`substantially identical to the digital digest received from said
`senderlcomputer to said receiverfcontputer.
`
`Page 12 of 19
`Page 12 ofl9
`
`

`

`US 6,757,717 131
`
`5
`the invention provides a method for
`Additionally.
`increased data access performed by a client computer in a
`packet-switched network. said client computer including an
`operating unit. a tirst memory and a processor. said method
`comprising the steps ofsending a request for data from said
`client computer to a server. said request containing digital
`digests for different data; said senior preparing a response to
`said request, searching for data with a digital digest sub-
`stantially identical to one of the digital digests received in
`said request. and producing the difference between said
`response and the uncovered data.
`Finally, the invention provides apparatus for increased
`data access in a packet-switched network. comprising a
`computer connected to said packet—switched network.
`including an operating unit. a lirsl memory. a permanent
`storage memory, a processor and a network cache memory;
`means for calculating digital digests of data in said network
`cache memory; means for comparison between digital
`digests, and means for sending the results of comparison
`between a digital digest received from another computer in
`said network and a digital digest calculated on data in said
`network cache memory back to said other computer.
`The invention will now be described in connection with
`certain preferred embodiments with reference to the follow-
`ing illustrative figures so that it may be more fully under—
`stood.
`With specific reference now to the ligures in detail. it is
`stressed that the particulars shown are by way of example
`and. for purposes of illustrative discussion of the preferred
`embodiments of the present
`invention only. and are pre—
`sented in the cause of providing what is believed to be the
`most uset'ul and readily understood description of the prin-
`ciples and conceptual aspects of the invention. In this regard,
`no attempt is made to show structural details ofthe invention
`in more detail than is necessary for a fundamental under-
`standing of the invention,
`the description taken with the
`drawings making apparent to those skilled in the art how the
`several forms of the invention may be embodied in practice.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. .1 illustrates a prior art wide-area network;
`FIG. 2 illustrates a prior art wide-area network with a
`caching gateway;
`FIG. 3 is a flow diagram of the method ofcalculating the
`difiercnce between two data digests according to the present
`invention:
`FIG. 4 is a block diagram of a tirsl embodiment of a
`senderteomputer-receiverteomputer system according to the
`present invention;
`FIG. 5 is a schematic representation illustrating the inter-
`action between a sendertoomputer and a receiven'computcr
`according to the system of FIG. 4;
`FIG. 6 is a
`flow diagram illustrating the method of
`operating the senden'curnpuler awarding to the present
`invention;
`flow diagram illustrating the method of
`FIG. 7 is a
`operating the receivericomputer according to the present
`invention:
`FIG. 8 is a schematic representation illustrating the inter—
`action benveeo a sendertcomputer and a receivertcomputer
`according to another embodiment of the present invention:
`FIG. 9 is a flow diagram illustrating the method of
`operating the sendeo’computer according to a further
`embodiment of the present invenLion;
`FIG. 10 is a flow diagram illustrating the method of
`operating the receivert'computer according to the embodi—
`ment of FIG. 9;
`
`Ill
`
`IS
`
`.30
`
`35
`
`4!]
`
`fit]
`
`(all
`
`[In
`
`6
`FIG. 11 is a block diagram of the configuration of the
`gateway system according to the present invention;
`FIG. 12 is a schematic representation of the interaction
`bethun a sendert'computer, a receivcrrOomptlter. and the
`gateway configuration according to the present invention;
`FIG. 13 is a liow diagram of the operation of the gateway;
`FIG. 14 is a block diagram of a further configuration of a
`senden’computer-receiverfcompuler system according to the
`present invention; and
`FIG. 15 is a schematic representation of the interaction
`between the sendertcomputer-reeeivert'comptttcr system of
`FIG. 14.
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`The performance gains realized by the present invcntion
`are derived from the fact that computers in common wide-
`arca networks tend to repetitively transmit the same data
`over the network.
`The operations described herein may take the form of
`electrical or optical signals. The packet-switched network
`may be lntemet.
`The term "digital digest" as used herein refers to the per
`sc known MDS algorithm, described in RFC .l32l by R.
`Rivest, which is a preferred calculation method. Other
`algorithms may. however,just as well be used. For example,
`a digital digest may be calculated according to the (TRC
`algorithm. or by applying the CRC algorithm to diii'erenl
`subsets or different reorderings of data, or by consecutively
`applying EKG and MDS. In addition. any other algorithm
`may be used. provided that it produces a fitted-size binary
`value calculated from adiitrarily-siaed binary data in such a
`way that it depends only on the contents of said data and that
`the probability of two diil‘erent data having the same digital
`digest. is low.
`Whenever means for calculating the difference between
`two data are mentioned herein, the method as shown in FIG.
`3 may be employed. The data are referTed to as DI and D2.
`The difl'erence between them consists of three parts:
`the
`number of fragment pairs. the array of fragment pairs. and
`the remainder of D1. A fragment pair is a pair representing
`the distance from the beginning of this fragment to the end
`of the previous one. and the. number ofoctels in the fragment
`(Dist,[.cngth). A marker m1 is set at the beginning of the
`data DI and a marker m2 at the beginning of D2.
`An octet m1 is designated as 'ml and an octet m2 as 'm2.
`An integer lb]. which represents a minimal
`length of a
`fragment encoded. e.g., K=3. is chosen.
`As stated above, ml is set at the beginning of D1, m2 at
`the beginning of [12. and Dist=it is assigned at 14. A loop is
`then entered: if m1 is at the end of D1 (16), a number of
`fragment pairs is saved at 18. and the algorithm is com-
`pleted. [f m2 is at the end of D2 (20), the rest of D1 from ml
`is saved at 22. a number of fragment pairs is saved. and the
`algorithm is completed. if ‘ml equals ‘m2 (24}, a subrou-
`tine "Fragmenl'1 is entered at It); otherwise. [02 is moved by
`one octet toward the end of DE and Dist is increased by l at
`38.
`The subroutine “Fragment" proceeds as follows: New
`markers tl-ml and t2-m2 are set and Length-0 is assigned
`at 30. [I and. [2 are moved by an octet toward the ends of D1
`and D2 and Length is increased at 32. It I] is at the end of
`D1. or II is at the end of D2. or ‘t1 does not equal 't2 at the
`end of the fragment (34}, then the Length is a length of the
`fragment and Dist is the distance betwaen the beginning of
`
`Page 13 of 19
`Page 13 of19
`
`

`

`US 6,757,717 131
`
`7
`this fragment and the end of the previous one. If the Length
`<K as determined by so. the fragment is dropped at 38. m2
`is moved by one octet and the subroutine is terminated.
`Otherwise, the pair (Dist,l_ength) is saved. the number of
`pairs is increased by one. m1 and m2 are moved by Length
`octets toward the ends of D]. and DZ. and Dist is reset to (t
`at 40. The subroutine is ended.
`The sequence offragrncnt pairs may be further reduced in
`size by using the per sc known Huffman encoding or by
`using an arithmetic coding. e.g., as; dischtsed in U .5. Pat. No.
`4.lll.44ti.
`Restoration of the data is simple. Marker m2 is set at the
`beginning of the known DZ. Then for each fragment pair
`(Dist. length) from the known difference. ml is moved by
`Dist octets. Length octets are copied from ml to [)1 and m2
`is moved by Length. Then the rest of D1 is copied from the
`remainder
`An embodiment of a sendcricomputcr~rcccivericomptiter
`system according to the present invention is schematically
`illustrated in FIG. 4. A preferred embodiment is a network
`computer system having at least two computers. A sender!
`computer 42 (also referred to herein as "‘senderi'computer")
`having an operating unit, a first memory. a permanent
`storage memory and a processor, is connected to the network
`by any network connection 44. A remote receivericompuler
`46 {also referred to hen: in as “‘receivcrioomputer") having an
`operating unit. a first memory. a permanent storage memory
`and a processor.
`is also connected to the network. The
`recoivericomputer 46 uses a part ot" its permanent storage
`memory or its first memory, or both, as network cache
`memory 48. The sendericomputcr has calculation means 50
`for calculating a digital digest on data in its first memory or
`in its permanent storage memory. Similarly.
`the received
`computer has calculating means 52 for calculating a digital
`digest on data stored in its network cache memory 48. The
`receivericomputer also has comparison means 54 for com-
`paring belwuen such a calculated digital digest and a digital
`digest received from the network.
`An example of a lirst memory could he a RAM; an
`example of a permanent storage memory may be a disk
`drive, a flash RAM or a bubble memory.
`It is possible to modify this system in different ways. The
`receivericomputer 46 and sendericomputer 42 may each
`include means for storing the calculated digital digest in its
`first memory or permanent storage memory. Additionally,
`the receiven’compuler 46 may have means for calculating a
`digital digest on data in its permanent storage memory
`outside of its cache memory. Furthern'tore. the system may
`be modified in such a way that the scndcrtcomputer 42. has
`means 56 for calculating the dili'crcncc between two data
`objects.
`Interaction between the receivericomputer and the ruender,t
`computer is depicted in FIGS. 5 to T. The data sendcri'
`computer 42. calculates a digital digest on the data in means
`50 and then transmib;
`the calculated digest
`to receiver!
`computer 46. The receivericomputcr rewivcs the digital
`digest from senderrcornputer 42 and then searches its net-
`work cache memory 48 for data with the same digest. If it
`finds such data.
`it uses it as if it were received from the
`sendericomputer 42 and issues a positive indication signal to
`the sendericomputer. Otherwise. it sends a negative indica-
`tion signal to the scndcricomputcr. Upon receiving a nega-
`tive indication signal,
`the sendertcomputer transmits the
`data. Upon receiving a positive indication signal. or upon
`expiration of a predefined period of time.
`the sender;r
`computer completes the transaction. This transaction begins
`with a recoivericornpttter sending a request to the sender!
`computer.
`
`5
`
`ll]
`
`15
`
`4t]
`
`St]
`
`6t]
`
`[IS
`
`3
`The above-described method may be modified in dilierenl
`ways. For example. absence of a signal from the receiver!
`computer for a predetermined period of time may be con-
`sidered by the sendcricomputcr to be a negative indication
`signal. Alternatively. the digital digests for some data may be
`stored in the permanent storage memory of the sender;
`computer and obtained from there.or a plurality of data may
`be processed in one transaction, a digital digest being
`calculated for each data object and a separate indication
`signal issued on each digital digest.
`Another method of interaction between the receiver:r
`computer 46 and the senderteornputer 42 is illustrated in
`FIGS. 8-10. The data sendert'computer calculates a dig’tal
`digest on the data to be sent (hereinafter. "principal digest")
`and for one or more other data objects (hereinafter. "auxil-
`iary digests"). Without limiting the scope of the invention.
`the following data objects may be recommended: {a} a
`previous version of the data requested; (b) a file similar to
`the data requested.
`'I‘hen the scndcn‘computer sends the
`principal and auxiliary digests to the receivericomputec
`Upon receiving a message with these digital digests from the
`sendericornputcr, the rcccivcn'compuler searches its network
`cache memory 48 for data having the principal digest. If
`such data is found.
`it uses it as if it were received from
`senderi’computer 42 and issues a positive indication signal to
`the sendericomputer. Otherwise. receivcricomputcr 46
`searches its network cache memory 48 for data with the
`auxiliary digests. if it finds data with a digital digest sub-
`stantially equal to one o[’ the auxiliary digests. it issues a
`partial
`indication signal
`to the senderi’computer. with a
`reference to the digest. Otherwise,
`it
`issues a negative
`indication signal to the scndcri‘computor. Upon receiving a
`negative indication signal. the sendcrr‘cornputer sends the
`data. Upon receiving a partial indication signal, the sender}
`computer transmits the dilfercncc between the digital digest
`of the data required to be sent and that of the data whose
`digital digest was found by the receivericomputer. TE
`tr 1] ac ion
`a alsoh in
`'
`t erecciverico
`titer 5::
`d—
`ing a reguest to the senderi‘computer.
`A modification of the above method is possible. For
`example, absence of the indication signal from the rcccivcrt'
`computer for a predefined period of time may he considered
`by the senderi'colnputer as a negative indication signal. or
`the digital digests for some data may be stored in the
`permanent storage memory of the senderfcomputer and
`obtained from there instead of being calculated immediately
`before the transaction. Alternatively. a plurality ot‘data may
`be processed in one transaction; a digital digest is calculated
`for each data object and a separate indication signal issued
`on every digital digest. Still alternatively. receivert'computcr
`46 may search not only in its network cache memory 48. but
`also in predefined locations in its permanent storage
`memory. Sendcrfoompulcr 42 may add to a digest it sends to
`the receivericomputer information about the possible loca—
`tion of the data with that digital digest
`in the receiver-
`computer’s permanent storagc memory.
`Another embodiment of the present invention is schemati~
`cally illustrated in FIG. 11. Shown is a s