(12) United States Patent
`Goldstein
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US006757717B1
`US 6,757,717 Bl
`(10) Patent No.:
`.Jun.29, 2004
`(45) Date of Patent:
`
`SYSTEM AND METHOD FOR DA11\.ACCESS
`
`Inventor:
`
`Leonid Goldstein, Herzlia (IL)
`
`Assignee:
`
`Proxyf.onn,
`
`Inc., Irvine, CA (US)
`
`Notice:
`
`tbe term of this
`to an)' disclaimer,
`Subject
`is extended or adjusted under 35
`patent
`U.S.c. 154(b) by 0 days.
`
`App!. No.: 09/398,007
`Sep, 16, 1999
`
`Filed:
`Int. CI.7 .
`U.S. Cl.
`
`G06F 15/16
`709/217; 707/1; 707/10;
`709/203; 709/225; 709/229
`.................................
`709/217, 203,
`709/229, 225; 707/10, 1
`
`(54)
`
`(75)
`
`(73)
`
`( * )
`
`(21)
`(22)
`(51)
`(52)
`
`(58)
`
`Field of Search
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,897,781 A
`1/1990 Chang el al.
`5,384,565 A
`1/1995 Gregory
`5,682,514 A * 10/1997 Yohe et al.
`5,732,265 A
`3/1998 Dewitt et al.
`5,835,943 A
`11/1998 Yohe et aJ.
`5,852,717 A
`12/1998 Bhide et al.
`5,864,837 A
`1/1999 Maimone
`5,878,213 A *
`3/1999 Bittinger et al.
`5,909,569 A * 6/1999 Housel et al.
`5,919,247 A * 7/1999 Van Hoff et aJ.
`5,924,116 A
`7/1999 Aggarwal
`et al.
`5,931,947 A * 8/1999 Burns et al.
`5,978,791 A
`11/1999 Farber et al.
`6,003,087 A * 12/1999 Housel et al.
`6,006,034 A
`12/1999 Heath et al.
`6,012,085 A
`1/2000 Yohe et al.
`6,021,491 A * 2/2000 Renaud
`6,073,173 A * 6/2000 Bittinger et al.
`6,085,249 A * 7/2000 Wang ct al.
`6,101,543 A * 8/2000 AJden et al.
`6,122,637 A * 9/2000 Yohe et al.
`6,134,583 A * 10/2000 Herriot
`6,148,340 A * 11/2000 Bittinger et al.
`* 7/2001 Donoho et al.
`6,256,664 Bl
`
`707/1
`
`707/10
`707/10
`709/217
`
`713/201
`
`707/203
`
`713/179
`.. 707/513
`709/229
`.. 709/229
`.. 709/204
`709/217
`.. 709/203
`709/204
`
`709/232
`
`1, Jan.
`
`*
`8/2001 Baber et al.
`6,279,041 Bl
`OTHER PUBLICATIONS
`RFC2068: Hypertext Transfer Protocol-HTTP/I.
`1997,pp.
`9-12,29-35,70-94,101-138.
`RFC791: Internet Protocol Darpa Internet Program Protocol
`Specification, Sep. 1981, pp. 3, 11-14,26.
`RFC761: DOD Standard Transmission Control Protocol,
`Jan. 1980, pp.4, 15-17.
`RFC1826:
`IP Authentication Header, Aug. 1995, pp. 1-10.
`RFCI864: Tbe Content-MD5 Header Field, Oct. 1995,
`pp.I-2.
`RFC132l: Tbe MD5 Message-Digest Algorithm, Apr. 1992,
`pp. 1-21.
`Dave Fogle, Ethernet Frame Types, article from Feb. 1996
`issue of LAN Magazine/Network Magazine, pp. 1--4.
`W. Richard Stevens, TCP/IP Tllustrated, vol. 1, 1994, pp.
`33-37, 143-147, 223-228.
`* cited by examiner
`Primary Examiner-Jack
`B. Harvey
`Assistant Examiner-Hai
`V. Nguyen
`(74) Attorney, Agent, or Firm-J. D. Harriman,
`Coudert Brotbers LLP
`
`II, Esq.;
`
`(57)
`
`ABSTRACT
`
`The invention provides a system for data access in a packet-
`switcbed network,
`including an
`including a sender/computer
`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
`furtber
`including device for calculating digital
`digests on data;
`the receiver/computer
`furtber
`including a
`network cache memory and device for calculating digital
`digests on data in the network cacbe memory;
`and tbe
`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
`
`Calculate
`
`digital
`
`digests
`
`Send digital digests
`
`Sender
`
`
`
`~t
`
`i,
`i
`
`Issue "partial"
`
`or "neqanve"
`
`signal
`
`If received
`
`"partie!"
`
`signal
`
`- send the difference
`
`MICROSOFT
`
`EXHIBIT 1002
`
`Page 1 of 19
`
`

`

`u.s. Patent
`
`Jun. 29,20()4
`
`Sheet 1 of 9
`
`US 6,757,717 Bi
`
`Client
`(Receiver)
`
`Cache
`
`Client
`(Receiver)
`
`Cache
`
`4
`
`6
`
`4
`
`6
`
`2
`
`2
`
`Wide Area Network
`
`FIG. 1 (PRIOR ART)
`
`FIG. 2 (PRIOR ART)
`
`8
`
`Server
`(Sender)
`
`8
`
`Server
`(Sender)
`
`Page 2 of 19
`
`

`

`u.s. Patent
`
`Jun. 29,20()4
`
`Sheet 2 of 9
`
`US 6,757,717 Bi
`
`Set m1 to beginning of D1. m2 to
`beginning of D2; assign Dist=O
`
`--------14
`
`Yes
`
`Yes
`
`Yes
`
`28
`
`18
`
`Save a number of fragement
`pairs. END
`
`22
`
`Save the rest of D1 from m1
`
`26
`
`FIG.3
`
`SUBROUTINE 'Fragment'
`
`Assign t1=m1, t2=m2. Length=O ~
`
`30
`
`Move t1and t2 by an octet. assign
`Legnth = Length + 1
`
`~
`
`32
`
`38
`
`Move m2 by an
`octet. Assign
`Dist=O.
`
`40
`
`Save pair (Dist, Length).
`Move m1 and m2 by
`Length octets. Assign
`Dist=O
`
`Page 3 of 19
`
`

`

`u.s. Patent
`
`Jun. 29,20()4
`
`Sheet 3 of 9
`
`US 6,757,717 Bi
`
`42/
`56DO
`
`50
`
`Sender
`
`Sender
`
`Page 4 of 19
`
`Receiver
`52
`
`54
`
`46/
`58DOD Network
`44/
`
`Connection
`
`48............ Network
`-...........cache
`memory
`
`FIG.4
`
`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
`
`Receiver
`
`IIIIk
`
`IIIIl
`
`IIIIIk
`
`: IIIIIIIIIIIIIIk
`
`

`

`u.s. Patent
`
`Jun. 29,20()4
`
`Sheet 4 of 9
`
`US 6,757,717 Bi
`
`Sender
`
`Calculate digest on data
`
`--~50
`
`Send digest to receiver
`
`Send data to receiver
`
`No
`
`Yes
`
`Yes
`
`No
`
`FIG.6
`
`Finish Transaction
`
`Receiver
`
`Receive digest
`
`Issue "positive"
`signal
`
`..--------
`
`No
`
`Issue "negative" signal
`
`Fetch from cache
`
`FIG.7
`
`Page 5 of 19
`
`

`

`u.s. Patent
`
`U.S. Patent
`
`Jun. 29,20()4
`Jun. 29, 2004
`
`Sheet 5 of 9
`Sheet 5 0f 9
`
`US 6,757,717 Bi
`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,20()4
`
`Sheet 6 of 9
`
`US 6,757,717 Bi
`
`Sender
`
`Calculate digest on data
`
`Send digest
`
`to receiver
`
`No
`
`Yes
`
`Finish Transaction
`
`FIG.9
`
`Send data to receiver
`
`Yes
`
`Yes
`
`Yes
`
`Send
`difference to
`receiver
`
`Page 7 of 19
`
`

`

`u.s. Patent
`
`Jun. 29,20()4
`
`Sheet 7 of 9
`
`US 6,757,717 Bi
`
`Receiver
`
`Receive digest
`
`No
`
`No
`
`Issue "negative"
`signal
`
`46
`
`Yes
`
`Yes
`
`Issue "positive"
`signal
`
`Felch from
`cache
`
`Issue "partial"
`signal
`
`FIG. 10
`
`60
`
`Gateway
`
`42
`
`Cacher
`
`62
`
`FIG.11
`
`66",
`
`Network
`cache
`memory
`
`Page 8 of 19
`
`

`

`u.s. Patent
`
`Jun. 29,20()4
`
`Sheet 8 of 9
`
`US 6,757,717 Bi
`
`Sender
`
`Send digest
`
`Gateway / Cacher
`
`d
`
`IIIIk
`
`I
`
`IIII:
`
`Receiver
`
`Save diqest
`
`Forward digest
`
`Page 9 of 19
`
`II, II~
`
`Pass indication signal
`
`to sender
`
`FIG. 12
`
`Send "negative" signal
`
`If data found, send it and change
`signal
`to positive
`
`Gateway / Cacher
`
`Receive digest from sender
`
`Save digest, forward to receiver
`
`Receive indication signal from
`receiver
`
`Yes
`
`No
`
`FIG. 13
`
`Send object to receiver.
`Change signal to "positive"
`
`I-------~
`
`Forward indication signal to
`sender
`
`

`

`u.s. Patent
`
`Jun. 29,20()4
`
`Sheet 9 of 9
`
`US 6,757,717 Bi
`
`/
`44 0 0
`
`42
`
`78
`
`74
`
`~80
`
`I
`
`Sender
`
`Sender
`
`IIIII~
`
`IIIII
`
`>l
`I,
`
`IIIj IIIIIJ I
`
`J III:
`
`Page 10 of 19
`
`Prepare response
`
`Calculate
`
`digestc:
`c:=
`
`
`
`Look for d_.ig,:.:e:.:s.:..t_-----.:
`
`Receiver
`76
`
`820 0 Network
`
`Connection
`
`V
`
`72~
`
`Network
`cache
`memory
`
`FIG. 14
`
`Receiver
`
`Calculate digests
`
`Issue request, containing
`
`some digests
`
`Send full data or differences
`
`FIG. 15
`
`

`

`1
`SYSTEM AND METHOD FOR DATA ACCESS
`
`US 6,757,717 B1
`
`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 Metbod For Data Access,"
`and which describes the same invention as defined herein.
`
`FIELD OF THE INVENTION
`invention relates to data access in networks.
`The present
`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:
`1) 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, cacbe the data
`togetber with its request until
`the expiration time. Tben
`the data is retrieved from the cache. In some cases,
`the
`receiver guesses tbe expiration time.
`The problem associated with tbis technique is tbat the data
`entity can he cbanged before the expiration time, and tbe
`receiver would use an obsolete version of the data without
`even knowing it. Also, when the time has expired,
`the data
`wiU be resent, even if it is up to date.
`tbe sender
`2) In response to a request
`from a receiver,
`attaches a validator to tbe sent data. The validator changes
`at
`least every time the data changes;
`in many cases,
`system time is used as the validator. Tbe receiver, and
`possibly proxies, cache tbe data together with its request.
`When making the next request for the same data to tbe
`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 witb tbis technique are:
`a) Data is cached according to requests and senders. If tbe
`same request
`is directed to different servers, cacbed
`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 tecbniques discussed above provides
`means
`for
`transmitting
`minor
`differences
`in data.
`Additionally,
`if data is retrieved tbrough a cacbing proxy,
`there is a danger that an unauthorized user will have access
`to tbe data.
`invention to
`It is therefore a broad object of the present
`provide a method, system and apparatus for increasing the
`speed of data access in a packet-switched network.
`Anotber object of the preseot invention is to decrease data
`traffic throughout
`the network.
`Still another object of tbe present
`the required cache size.
`
`invention is to decrease
`
`2
`A yet furtber object of tbe preseot invention is to maintain
`accessed data integrity and to improve security.
`
`SUMMARY OF THE INVENTION
`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.
`as used herein refers to a
`The term "digital digest"
`10 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 oetwork
`15 proxies and routers.
`in a network is required to send data
`If a sender/computer
`to another receiver/computer,
`and the receiver/computer has
`data with the same digital digest as that of the data to be sent,
`
`25
`
`20 ~nl~~~ca~eap;l~~~~~s~:~~t ~~~~!~~:v~;~~,,!~l~~~r f~;.s ~~~,:
`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 tbe 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 bas data with tbe same digital digest,
`it
`30 uses tbis data as if it were actually transmitted from tbe
`sender/computer. Additionally, digital digests for other data
`objects can be sent together with the principal digest. If tbe
`receiver/computer
`cannot
`find data having tbe principal
`digest,
`it searches
`for data with one of
`these auxiliary
`35 digests.
`If such data is found,
`tbe sender/computer
`is
`required to send only the difference between the requested
`data object and tbe 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
`40 means any bit sequence that enables the restoration of tbe
`first data, given the second data,
`the bit sequence and tbe
`method employed in calculating the difference.
`The invention may be implemented in a gateway system.
`Such a system comprises a gateway computer connected to
`network in such a way that network
`45 a packet-switched
`packets
`sent between at
`least
`two other computers pass
`through it; a cacbing computer connected to tbe gateway
`computer,
`the caching computer having a network cache
`memory in its permanent
`storage memory, means for cal-
`50 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
`55 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
`60 digital digests. A sender/computer
`forming a response then
`searches
`for data with the same digital digests as those
`received. If the digest of tbe data in tbe 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
`65 digests, only the difference(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
`
`Page 11 of 19
`
`

`

`US 6,757,717 B1
`
`3
`including an oper-
`network, comprising a sender/computer
`storage memory and
`ating unit, a first Inemory, a permanent
`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 10
`receiver/computer
`and/or
`said sender/computer
`including
`means for comparison between digital digests.
`The 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 com-
`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 20
`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 25
`said gateway computer.
`In addition,
`a system for data
`the invention provides
`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
`seoder/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 35
`receiver/computer
`further
`including
`a network
`cache
`memory, means for storing a digital digest
`received from
`said network in its penn anent storage memory
`and means
`for comparison between digital digests.
`The invention further provides a method performed by a 40
`sender/computer
`in a packet-switched
`network for 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 beiog operative to trans-
`mit data to a receiver/computer,
`the method comprising the 45
`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 50
`negative indication signal is received,
`transmitting said data
`from said sender/computer
`to said receiver/computer.
`The 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 60
`sender/computer
`to said receiver/computer;
`receiving
`a
`response signal at said sender/computer
`from said receiver/
`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.
`
`55
`
`65
`
`15
`
`30
`
`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 cacbe 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 tbrougb said network.
`for
`a method
`Still
`furtber,
`tbe invention
`provides
`in a
`increased data access performed by a receiver/computer
`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 tbe 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 tbrougb said network.
`In addition, the invention provides a metbod 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 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 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 signal
`and transmitting it back through said network.
`Yet furtber, tbe 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 sender/computer
`and a receiver/computer
`so that
`data packets sent between said sender/computer
`and said
`receiver/computer
`are delivered through said computer sys-
`tem; said method comprising the steps of intercepting
`a
`message containing a digital digest
`transmitted from said
`sender/computer
`to said receiver/computer,
`and transmitting
`data with a digital digest substantially identical
`to the digital
`digest received from said sender/computer
`to said receiver/
`computer.
`In addition, the invention provides a method for increased
`data access performed by a computer system in a packet-
`switcbed network,
`said computer
`system including a net-
`work cache memory and being operationally
`interposed
`between a sender/computer
`and a receiver/computer
`so that
`data packets sent between said sender/computer
`and said
`receiver/computer
`are delivered through said computer sys-
`tem; said metbod comprising the steps of intercepting
`a
`message containing a digital digest
`transmitted from said
`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
`
`

`

`5
`for
`a method
`provides
`the invention
`Additionally,
`by a client computer
`in a
`increased
`data access performed
`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.
`for increased
`Finally,
`the invention provides apparatus
`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 20
`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 tbat it may be more fully under-
`stood.
`it is
`Witb specific reference now to the figures in detail,
`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 tbe cause of providing what
`is believed to be tbe 30
`most useful and readily understood description of the prin-
`ciples and conceptual aspects of the invention. In tbis 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,
`tbe description taken witb tbe 35
`drawings making apparent to those skilled in the art how tbe
`several forms of tbe 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 tbe 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/computer
`system according to tbe
`present
`invention;
`FIG. 5 is a schematic representation 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 illustrating
`operating the sender/computer
`according
`invention;
`tbe method of
`FIG. 7 is a flow diagram illustrating
`operating the receiver/computer
`according to tbe present
`invention;
`FIG. 8 is a schematic representation 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 illustrating the metbod 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;
`
`the method of
`to the present
`
`15
`
`25
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`invention
`The performance gains realized by the present
`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
`algoritbm, or by applying tbe CRC algorithm to different
`subsets or different reorderings of data, or by consecutively
`applying CRC and MOS. 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.
`40 3 may be employed. Tbe data are referred to as 01 and 02.
`The difference between them consists of three parts:
`the
`number of fragment pairs,
`the array of fragment pairs, and
`the remainder of 01. A fragment pair is a pair representing
`the distance from tbe beginning of this fragment
`to the end
`45 of the previous one, and tbe number of octets in the fragment
`(Dist,Length). A marker ml
`is set at the beginning of the
`data 01 and a marker m2 at the beginning of 02.
`An octet ml is designated as *ml and an octet m2 as *m2.
`length of a
`An integer K»L, whicb represents a minimal
`50 fragment encoded, e.g., K=3, is chosen.
`As stated above, ml
`is set at the beginning of 01, m2 at
`the beginning of 02, and Dist-O is assigned at 14. A loop is
`then entered:
`if ml
`is at the end of 01 (16), a number of
`fragment pairs is saved at 18, and tbe algorithm is com-
`55 pie ted. If m2 is at the end of 02 (20), the rest of 01 from ml
`is saved at 22, a number of fragment pairs is saved, and the
`algorithm is completed.
`If "mf 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 1 at
`60 28.
`as follows: New
`proceeds
`"Fragment"
`The subroutine
`markers tl=ml
`and t2=m2 are set and Length-O is assigned
`at 30. t1 and t2 are moved by an octet toward the ends of 01
`and 02 and Length is increased at 32. If tl
`is at tbe end of
`01, or t2 is at the end of 02, or *11does not equal *t2 at the
`end of the fragment (34), then the Length is a lengtb of the
`fragment and Dist is tbe distance between the beginning of
`
`US 6,757,717 B1
`
`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
`invention; and
`10 present
`FIG. 15 is a schematic representation of the interaction
`between the sender/compUler-receiver/computer
`system of
`FIG. 14.
`
`65
`
`Page 13 of 19
`
`

`

`US 6,757,717 B1
`
`10
`
`20
`
`35
`
`40
`
`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 ami
`the subroutine
`is terminated.
`Otherwise,
`the pair (Dist,Length)
`is saved,
`the numher of
`pairs is increased by one, ml and m2 are moved by Length
`octets toward the ends of Dl 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 Huffman encoding or by
`using an arithmetic coding, e.g., as disclosed in U.S. Pal. No.
`4,122,440.
`Restoration of the data is simple. Marker m2 is set at the
`beginning of the known 02. Then for each fragment pair
`(Oist, Length) from the known difference, m2 is moved by
`Dist octets, Length octets are copied from m2 to 01 and m2 15
`is moved by Length. Then the rest of 01 is copied from the
`remaioder
`An embodiment of a sender/computer-receiver/computer
`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 "sender/computer")
`having ao operating uoit, a first memory,
`a permanent
`storage memory and a processor,
`is connected to the oetwork
`by any network connection 44. A remote receiver/computer
`46 (also referred to berein as "receiver/computer")
`having an 25
`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 30
`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 modify this system in different ways. The
`receiver/computer
`46 and sender/computer
`42 may each
`include means for storing tbe calculated digital digest in its
`first memory or permanent
`storage memory. Additionally,
`the receiver/computer 46 may have means for calculating a 45
`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.
`and the sender/
`Interaction between the receiver/computer
`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. TI,e 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 tbe
`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.
`
`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
`signal. Alternatively,
`tbe digital digests for some data may be
`stored in the permanent
`storage memory of tbe sender/
`computer and obtained from tbere, or a plurality of data may
`be processed
`in one transaction,
`a digital digest being
`calculated for eacb data object and a separate indication
`signal
`issued on eacb digita