(12) Unlted States Patent
`(10) Patent N0.:
`US 6,757,717 B1
`
`Goldstein
`(45) Date of Patent:
`Jun. 29, 2004
`
`U8006757717B1
`
`(54) SYSTEM AND METHOD FOR DATA ACCESS
`
`6,279,041 B1 "
`
`8/2001 Baber et al.
`
`................ 709/232
`
`Inventor: Leonid Goldstein, Herzlia (IL)
`,
`,
`(73) Ass1gnee: PI‘OXyCOHH, Inc., Irvme, CA (US)
`,_
`.
`.
`.
`.
`.
`
`(75)
`
`<
`
`>
`
`‘J
`.
`b b
`5
`,V
`‘
`L
`U-S-L- 1 4( ) Yo “We
`
`‘
`
`.
`
`"
`
`(21) Appl- No: 09/398,007
`22
`F] d:
`s
`. 16, 1999
`)
`(
`eP
`‘6
`
`Int. Cl.7 ......................... G06F 15/16
`(51)
`
`'
`‘
`,. 709/217; 707/1; 707/10;
`(52)
`709/203; 709/225; 709/229
`'
`'
`n
`(58) Field of Search ................................. 709.17, 203,
`709/229, 225; 707/10, 1
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`.................... 707/1
`
`
`
`
`...... 707/10
`...... 707/10
`........... 709/217
`
`1/1990 Chang et a1.
`4,897,781 A
`1/1995 Gregory
`5,384,565 A
`5,682,514 A 7 10/1997 Yohe et a].
`5,732,265 A
`2/1998 Dewill el al.
`5,835,943 A
`11/1998 Yohe et a].
`5,852,717 A
`12/1998 Bhide et al.
`5,864,837 A
`/1999 Maimone
`5,878,213 A *
`3/1999 Bittinger et a1.
`5,909,569 A *
`6/1999 Housel el ill.
`5,919,247 A *
`7/1999 Van Hoff et a].
`5,924,116 A
`7/1999 Aggarwal et al.
`5,931,947 A x
`/1999 Burns et al.
`................ 713/201
`5,978,791 A
`11/1999 Farber et al.
`
`., 707/203
`6,003,087 A 7 12/1999 Housel el ill.
`6,006,034 A
`12/1999 IIeath et al.
`6,012,085 A
`1/2000 Yohe ct a],
`
`713/179
`6,021,491 A x 72000 Renaud ...............
`
`707/513
`6,073,173 A “
`6/2000 Bittinger et al.
`
`709/229
`6,085,249 A *
`7/2000 Wang el al.
`. 709/229
`6,101,543 A x
`/2000 Alden et a1.
`6,122,637 A "
`9/2000 Yohe ct a],
`, 709/204
`
`6,134,583 A " 10/2000 Herriot
`.........
`. 709/217
`6,148,340 A 7 11/2000 Bittinger et al.
`. 709/203
`., 709/204
`6,256,664 B1 '7
`7/2001 Donoho el Hl.
`
`
`OTHER PUBLICATIONS
`Rl-‘C2068: Hypertext Transfer l’rotocol—H’l"l‘l’/'1.1, Jan.
`1997, Pp 9_127 29_35’ 70_94, lOl—l38
`RFC791: Internet Protocol Darpa Internet Program Protocol
`3,
`R1—‘C761: DOD Standard Transmission Control Protocol,
`Jan. 1980, pp.4, 15—17.
`RFC1826: IP Authentication Header, Aug. 1995, pp, 1—10.
`RFC1864: The ContentiMDS Header Field, Oct. 1995,
`Pill—2-
`RFC1321zThe MD5 Message—DigestAlgorithm,Apr. 1992,
`pp. 1—21.
`Dave Fogle, Ethernet Frame Types, article from Feb. 1996
`issue of LAN Magazine/Network Magazine, pp. 14.
`W. Richard Stevens, TCP/ll’ Illustrated, vol. 1, 1994,
`33—37, 143—147, 223—228.
`
`PP
`
`.
`
`* Cited by examiner
`Primary Examiner—Jack B. Harvey
`Assistant Exmniner—Ilai V. Nguyen
`(74) Attorney, Agent, or Fir/117]. D, Harrinian, II, Esq.;
`Coudert Brothers LLP
`
`(57)
`
`ABSTRACT
`
`The invention provides a system for data access in a packet-
`switched network, including a sender/computer including an
`operating unit, a first memory, a permanent storage memory
`and a processor and a remote receiver/computer including an
`operating unit, a first memory, a permanent storage memory
`and a processor,
`the sender/computer and the receiver/
`computer communicating through the network; the sender/
`computer further including device for calculating digital
`digests on data; the receiver/computer further including a
`network cache memory and device for calculating digital
`digests on data in the network cache memory; and the
`receiver/computer and/or
`the sender/computer including
`device for comparison between digital digests. The inven-
`tion also provides a method and apparatus for increased data
`access in a packet—switched network.
`
`34 Claims, 9 Drawing Sheets
`
`
`
`Receiver
`
`E
`
`i
`
`Iin.
`
`Calculate digital digests
`
`Send digital digests
`
`Search for principal digest in cache
`
`Search for auxiliary digests in cache
`
`Issue "pariial" or "negative" signal
`
`It received "partial" signal - send the difference
`;
`€——————:
`
`5
`
`MICROSOFT
`MICROSOFT
`
`
`
`EXHIBIT 1002
`EXHIBIT 1002
`
`Page 1 of 19
`Page 1 of 19
`
`

`

`U.S. Patent
`
`Jun. 29, 2004
`
`Sheet 1 0f 9
`
`US 6,757,717 B1
`
`Client
`
`Wide Area Network
`
`(Receiver)
`
`FIG. 1 (PRIOR ART)
`
` Wide Area Network
`
`
`
`Client
`Server
`’
`.
`____________________
`Sender
`
`~~~~~
`‘
`
`
`FIG. 2 (PRIOR ART)
`
`Page 2 of 19
`Page 2 of 19
`
`

`

`U.S. Patent
`
`Jun. 29, 2004
`
`Sheet 2 0f 9
`
`US 6,757,717 B1
`
`Set m1 to beginning of D1, m2 to
`beginning of D2; assign Dist=0
`
`Save a number of fragement
`pairs. END
`
`*m2? Move m2 by an octet, increase
`
`*m1 equals
`
`Dist by 1
`
`SUBROUTINE 'Fragment'
`
`FIG. 3
`
`Assign t1 =m1, t2=m2, Length=0
`
`
`
`3O
`\\\_/’
`
`
`
`Move Hand t2 by an octet, assign
`Legnth = Length + 1
`
`/’*\\
`32
`
`End of D1 or end of D2
`or *t‘l not equal *t2?
`
`
`
`Save pair (Dist, Length).
`
`Move m1 and m2 by
`“
`Move m2 by an
`Length octets. Assign
`octet. Assign
`
`
`Di5t=0-
`DIST=0
`Length less than K?
`
`
`Page 3 of 19
`Page 3 0f 19
`
`

`

`U.S. Patent
`
`Jun. 29, 2004
`
`Sheet 3 0f 9
`
`US 6,757,717 B1
`
`46
`
` Receiver
`52
`
`54
`
`58
`
`42
`
`
`ii
`
`
`
`Network
`
`Connection
`
`
`
`Receiver
`
`Sender
`
`Calculate digital digest
`
`Send digital digest
`
`Check for digest in cache
`
`
`
`Issue "positive" or "negative" signal
`
`If received "negative" signal - send the object
`
`FIG. 5
`
`Page 4 of 19
`Page 4 of 19
`
`

`

`U.S. Patent
`
`Jun. 29, 2004
`
`Sheet 4 0f 9
`
`US 6,757,717 B1
`
`Sender
`
`
`Calculate digest on data
`
`
`
`Send digest to receiver
`
`
`
`Receive
`
`"negative" signal
`
`
`
`Send data to receiver
`
`
`
`Received
`"positive" signal
`
`
`
`
`Timeout expired
`
`
`
` FIG. 6
`
`Finish Transaction
`
`Receiver
`
`
`Receive digest
`
`
`
`
` issue “positive"
`issue “negative" signal
`signal
`
`Fetch from cache
`
`
`
`Page 5 of 19
`Page 5 0f 19
`
`

`

`U.S. Patent
`
`Jun. 29, 2004
`
`Sheet 5 0f 9
`
`US 6,757,717 B1
`
`Receiver
`
`Sender
`
`,
`
`Calculate digital digests
`
`Send digital digests
`
`Search for principal digest in cache
`
`
`
`Search for auxiliary digests in cache
`
`
`
`Issue "partial" or "negative" signal
`
`If received "partial" signal - send the difference
`%__—_——_——._—_——
`
`FIG. 8
`
`Page 6 of 19
`Page 6 0f 19
`
`

`

`U.S. Patent
`
`Jun. 29, 2004
`
`Sheet 6 0f 9
`
`US 6,757,717 B1
`
`Sender
`
`Calculate digest on data
`
`Send digest to receiver
`
`Receive
`"negative" signal Send data to receiver
`
`
`
`
`
`
`Send
` Received
`
`
`
`difference to
`
`"partial" signal
`
`receiver
`
`
`Received
`
`"positive" signal
`
`Timeout expired
`
`
`
`
`Finish Transaction
`
`FIG. 9
`
`Page 7 of 19
`Page 7 0f 19
`
`

`

`U.S. Patent
`
`Jun. 29, 2004
`
`Sheet 7 0f 9
`
`US 6,757,717 B1
`
`Recewer
`
`Receive digest
`
`Principle digest
`in cache?
`
`Issue "positive"
`signal
`
`Fetch from
`cache
`
`Auxiliary digest
`
`Issue "partial"
`signal
`
`
`
`
`
`
`in cache?
`
`
`
`
`N0
`
`Issue "negative"
`signal
`
`
`
`FIG. 10
`
`60
`
`42
`
`Receiver
`
`
`
`FIG.11
`
`Network
`cache
`memow
`
`Page 8 of 19
`Page 8 0f 19
`
`

`

`U.S. Patent
`
`Jun. 29, 2004
`
`Sheet 8 0f 9
`
`US 6,757,717 B1
`
`Receiver
`
`Gateway / Cacher
`
`Sender
`
`Send digest
`
`Save digest
`
`Forward digest
`
`Send "negative" signal
`
`5
`
`Search for data with same digest
`
`V
`
`If data found, send it and change
`
`E
`
`signal to positive
`
`,
`
`Pass indication signal to sender
`
`FIG- 12
`
`Gateway / Cacher
`
`Receive digest from sender
`
`Save digest, forward to receiver
`
`
`
`
`Receive indication signal from
`receiver
`
`
`
`Fonivard indication signal to
`Send object to receiverv
`
`
`sender
`Change signal to "positive"
`
`
`
`
`
`
`
`Page 9 of 19
`Page 9 0f 19
`
`

`

`U.S. Patent
`
`Jun. 29, 2004
`
`Sheet 9 0f 9
`
`US 6,757,717 B1
`
`Receiver
`
`76
`
`Connection
`
`Network
`
`Page 10 of 19
`Page 10 0f 19
`
`Receiver
`I
`
`(I) ('D 3 O.(D _,
`
`Calculate di ests
`
`
`Issue request, containing some digests
`
`Prepare response
`
`l C
`
`alculate digest
`
`ll
`
`Look for digest
`
`ll
`
`Send full data or differences
`
`FIG. 15
`
`

`

`US 6,757,717 B1
`
`2
`A yet further object of the present invention is to maintain
`accessed data integrity and to improve security.
`SUMMARY OF THE INVENTION
`
`10
`
`1
`SYSTEM AND METHOD FOR DATA ACCESS
`
`RELATED APPLICATION
`
`This application claims priority and is entitled to the filing
`date of Israeli application Ser. No. 126292 filed Sep. 18,
`1998, 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 of data
`accessing in communication networks.
`BACKGROUND OF THE INVENTION
`
`Many known applications and protocols provide means
`for caching and verifying of 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
`10 (FIG. 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 be changed before the expiration time, and the
`receiver would use an obsolete 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 validator. 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 validator. The
`sender keeps track of the data and resends it only if 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 different servers, cached
`data cannot be reused.
`b) Requests without concrete 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.
`
`The terms “data” or “data object” as used herein refer to
`a file or range of octets in a file, a range of frames 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 of the
`data and the low probability that two different data or objects
`have the same digital digest.
`The term “gateway” as used herein also includes network
`proxies and routers.
`If a sender/computer in a network is required to send data
`to another receiver/computer, and the receiver/computer has
`data with the same digital digest as that of the data to be sent,
`it can be assumed with sufficient probability for most
`practical applications that the receiver/computer has data
`which is exactly the same as the data to be sent. Then, the
`receiver/computer 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 invention, a sender/computer
`required to send data to a receiver/computer computer
`initially sends a digital digest of the data. If the receiver/
`computer already has data with the same digital digest, it
`uses this data as if it were actually transmitted from the
`sender/computer. Additionally, digital digests for other data
`objects can be sent together with the principal digest. If the
`receiver/computer cannot
`find data having the principal
`digest,
`it searches for data with one of these auxiliary
`digests. If such data is found,
`the sender/computer is
`required to send only the difference between the requested
`data object and the data object corresponding to the digest.
`The expression “difference 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 bit sequence and the
`method employed in calculating the difference.
`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 receiver/computer computer, if it has data with the same
`digest, it sends this data to the receiver/computer.
`In another embodiment of the present invention, a client
`computer sends to a server computer a request including
`, digital digests. A sender/computer 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 digests, the server only sends confirmation,
`If the digest of another data is identical to one of the received
`digests, only the dilference(s) between these data is sent.
`In accordance with the present invention, there is there-
`fore provided a system for data access in a packet-switched
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`Page 11 of 19
`Page 11 ofl9
`
`

`

`US 6,757,717 B1
`
`3
`network, comprising a sender/computer including an oper—
`ating unit, a first memory, a permanent storage memory and
`a processor and a remote receiver/computer including an
`operating unit, a first memory, a permanent storage memory
`and a processor, said sender/computer and said receiver/
`computer communicating through said network; said sender/
`computer further including means for calculating digital
`digests on data; said receiver/computer further including a
`network cache memory and means for calculating digital
`digests on data in said network cache memory; and said
`receiver/computer and/or said sender/computer including
`means for comparison between digital digests.
`'lhe invention also provides a system for data access in a
`packet-switched 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 corn—
`puters pass through it; a caching computer including an
`operating unit, a first memory, a permanent storage memory
`and a processor connected to said gateway computer through
`a fast local network; said caching computer further including
`a network cache memory in its permanent 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 sender/
`computer including an operating unit, a first memory, a
`permanent storage memory and a processor and a remote
`receiver/computer including an operating unit, a first
`memory, a permanent storage memory and a processor, said
`sender/computer and said receiver/computer communicat-
`ing through a network; said sender/computer further includ—
`ing means for calculating digital digests on data, and said
`receiver/computer further including a network cache
`memory, means for storing a digital digest received from
`said network in its permanent storage memory and means
`for comparison between digital digests.
`The invention further provides a method performed by a
`sender/computer in a packet—switched network [or increas—
`ing data access, said sender/computer including an operating
`unit, a first memory, a permanent storage memory and a
`processor and said sender/computer being operative to trans-
`mit data to a receiver/computer, the method comprising the
`steps of transmitting a digital digest of said data from said
`sender/computer to said receiver/computer;
`receiving a
`response signal from said receiver/computer 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, transmitting said data
`from said sender/computer to said receiver/computer.
`'lhe invention still further provides a method for increas-
`ing data access performed by a sender/computer in a packet-
`switched network, said sender/computer including an oper—
`ating unit, a first memory, a permanent storage memory and
`a processor and said sender/computer being operative to
`transmit principal data to a receiver/computer, said method
`comprising the steps of transmitting digital digests of said
`principal data and of one or more auxiliary data from said
`sender/computer
`to said receiver/computer;
`receiving a
`response signal at said sender/computer from said rcceiver/
`computer, said response signal containing a positive, nega-
`tive or partial indication signal, and if a partial indication
`signal is received, said sender/computer transmitting a sig—
`nal constituting the difference between said principal data
`and corresponding auxiliary data.
`
`10
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`4
`The invention yet further provides a method for increased
`data access performed by a receiver/computer in a packet-
`switched network, said receiver/computer 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 digital
`digest from said network; 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 performed by a receiver/computer in a
`packet-switched network, said receiver/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 the 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 receiver/computer in a packet-
`switched network, said receiver/computer 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 diges
`substantially identical to said principal digital digest; search-
`ing in predetermined locations in said permanent storage
`memory for data with a digital digest substantially identica
`to one of said auxiliary digital digests; and if data having the
`same digital digest as one of said auxiliary digital digests
`received is uncovered, forming a partial indication signa
`and transmitting it back through said network.
`Yet further, the invention provides a method for increasec
`data access performed by a computer system in a packet—
`switched network, said computer system including a net—
`work cache memory and being operationally interposec
`between a sender/computer and a receiver/computer so tha
`data packets sent between said sender/computer and saic
`receiver/computer are delivered through said computer sys—
`tem; said method comprising the steps of intercepting a
`message containing a digital digest transmitted from saic
`sender/computer to said receiver/computer, and transmitting
`data with a digital digest substantially identical to the digita
`digest received from said sender/computer to said receiver,
`computer.
`In addition, the invention provides a method for increasec
`data access performed by a computer system in a packet-
`switched network, said computer system including a net-
`work cache memory and being operationally interposec
`between a sender/computer and a receiver/computer so tha
`data packets sent between said sender/computer and saic
`receiver/computer are delivered through said computer sys-
`tem, said method comprising the steps of intercepting a
`message containing a digital digest transmitted from sair
`sender/computer to said receiver/computer; intercepting a
`message containing an indication signal other than a positive
`indication signal transmitted from said receiver/computer to
`said sender/computer in response to said message containing
`a digital digest, and transmitting data with a digital digest
`substantially identical to the digital digest received from said
`sender/computer to said receiver/computer.
`
`
`
`Page 12 of 19
`Page 12 of19
`
`

`

`US 6,757,717 B1
`
`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 first memory and a processor, said method
`comprising the steps of sending a request for data from said
`client computer to a server, said request containing digital
`digests for different data; said server 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 first 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 figures 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 useful 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 of the 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 of calculating the
`difference between two data digests according to the present
`invention;
`FIG. 4 is a block diagram of a first embodiment of a
`sender/computer-receiver/compu er system according to the
`present invention;
`FIG. 5 is a schematic represen ation illustrating the inter-
`action between a sender/computer and a receiver/computer
`according to the system of FIG. 4;
`FIG. 6 is a
`flow diagram ilustrating the method of
`operating the sender/computer according to the present
`invention;
`FIG. 7 is a flow diagram i
`operating the receiver/computer
`invention;
`FIG. 8 is a schematic represen ation illustrating the inter-
`action between a sender/computer and a receiver/computer
`according to another embodiment of the present invention;
`FIG. 9 is a flow diagram ilustrating the method of
`operating the sender/computer according to a
`further
`embodiment of the present invention;
`FIG. 10 is a flow diagram illustrating the method of
`operating the receiver/computer according to the embodi-
`ment of FIG. 9;
`
`lustrating the method of
`according to the present
`
`
`
`10
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`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
`between a sender/computer, a receiver/computer, and the
`gateway configuration according to the present invention;
`FIG. 13 is a flow diagram of the operation of the gateway;
`FIG. 14 is a block diagram of a further configuration of a
`sender/computer—receiver/computer system according to the
`present invention; and
`FIG. 15 is a schematic representation of the interaction
`between the serider/computer—receiver/computer system of
`FIG. 14.
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`The performance gains realized by the present invention
`are derived from the fact that computers in common wide—
`area 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 Internet.
`The term “digital digest” as used herein refers to the per
`se known MDS algorithm, described in RFC 1321 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 CRC
`algorithm, or by applying the CRC algorithm to different
`subsets or different reorderings of data, or by consecutively
`applying CRC and MDS. In addition, any other algorithm
`may be used, provided that it produces a fixed—size binary
`value calculated from arbitrarily-sized binary data in such a
`way that it depends only on the contents of said data and that
`the probability of two different 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 referred to as D1 and D2.
`The difference between them consists of three parts:
`the
`number of fragment pairs, the array of fragment pairs, and
`the remainder of D1. Afragment pair is a pair representing
`the distance from the beginning of this fragment to the end
`of the previous one, and the number of octets in the fragment
`(Dist,Length). A marker m1 is set at the beginning of the
`data D1 and a marker m2 at the beginning of D2.
`An octet m1 is designated as *ml and an octet m2 as *m2.
`An integer K>1, 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 D2, and Dist=0 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. If 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 *m1 equals *m2 (24), a subrou-
`tine “Fragment” is entered at 26; otherwise, m2 is moved by
`one octet toward the end of D2 and Dist is increased by l at
`28.
`
`The subroutine “Fragment” proceeds as follows: New
`markers t1=m1 and t2=m2 are set and Length=0 is assigned
`at 30. t1 and t2 are moved by an octet toward the ends of D1
`and D2 and I.ength is increased at 32. If t1 is at the end of
`D1, or t2 is at the end of D2, or *tl 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 between the beginning of
`
`Page 13 of 19
`Page 13 0f19
`
`

`

`US 6,757,717 B1
`
`7
`this fragment and the end of the previous one. If the Length
`<K as determined by 36, the fragment is dropped at 38, m2
`is moved by one octet and the subroutine is terminated.
`Otherwise, the pair (Dist,Length) is saved, the number of
`pairs is increased by one, m1 and m2 are moved by Length
`octets toward the ends of D1 and D2, and Dist is reset to 0
`at 40. The subroutine is ended.
`The sequence of fragment pairs may be further reduced in
`size by using the per se known I-qufman encoding or by
`using an arithmetic coding, e.g., as disclosed in US. Pat. No.
`4,122,440.
`Restoration of the data is simple. Marker m2 is set at the
`beginning of the known D2. Then for each fragment pair
`(Dist, Length) from the known difference, n12 is moved by
`Dist octets, Length octets are copied from m2 to D1 and m2
`is moved by Length. Then the rest of D1 is copied from the
`remainder
`An embodiment of a sender/computer-receiver/computer
`system according to the present invention is schematically
`illustrated in FIG. 4. Apreferred embodiment is a network
`computer system having at least two computers. A sender/
`computer 42 (also referred to herein as “sender/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 receiver/computer
`46 (also referred to herein as “receiver/computer”) having an
`operating unit, a first memory, a permanent storage memory
`and a processor,
`is also connected to the network. The
`receiver/computer 46 uses a part of its permanent storage
`memory or its first memory, or both, as network cache
`memory 48. The sender/computer has calculation means 50
`for calculating a digital digest on data in its first memory or
`in its permanent storage memory. Similarly, the receiver/
`computer has calculating means 52 for calculating a digital
`digest on data stored in its network cache memory 48. The
`receiver/computer also has comparison means 54 for com-
`paring between such a calculated digital digest and a digital
`digest received from the network.
`An example of a first memory could be 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 modin this system in different ways. The
`receiver/computer 46 and sender/computer 42 may each
`include means for storing the calculated digital digest in its
`first memory or permanent storage memory. Additionally,
`the receiver/computer 46 may have means for calculating a
`digital digest on data in its permanent storage memory
`outside of its cache memory. Furthermore, the system may
`be modified in such a way that the sender/computer 42 has
`means 56 for calculating the difference between two data
`objects.
`Interaction between the receiver/computer and the send er/
`computer is depicted in FIGS, 5 to 7. The data sender/
`computer 42 calculates a digital digest on the data in means
`50 and then transmits the calculated digest
`to receiver/
`computer 46. The receiver/computer receives the digital
`digest from sender/computer 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
`sender/computer 42 and issues a positive indication signal to
`the sender/computer. Otherwise, it sends a negative indica—
`tion signal to the sender/computer. Upon receiving a nega—
`tive indication signal,
`the sender/computer transmits the
`data. Upon receiving a positive indication signal, or upon
`expiration of a predefined period of time,
`the sender/
`computer completes the transaction. This transaction begins
`with a receiver/computer sending a request to the sender/
`computer.
`
`10
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`8
`The above -described method may be modified in different
`ways. For example, absence of a signal from the receiver/
`computer for a predetermined period of time may be con-
`sidered by the sender/computer to be a negative indication
`signa