`
`.
`
`I
`
`J
`
`k3
`i
`
`"
`
`*
`
`I
`
`5%“
`
`PATENT
`
`Applicant: Leonid Goidstein
`
`.
`
`Examiner:
`
`Hai Nguyen
`
`Serial No: 89/398,007
`
`'
`
`i
`
`'
`
`Art Unit:
`
`2142
`
`Filed:
`
`. September 16, 1999
`
`For:
`
`System and Method for Data Access -
`'
`.
`Attorney Docket: 002i 973—0003
`
`CERTIFICATE OF
`MAILING/TRANSMISSION
`(37 C-‘ER. § 1.8A)
`I hereby certify that this correspondence is, on the
`.date showu below, being:
`(X) deposited with the United States Postal
`Service with sufficient postage as first class mail
`in an envelope addressed to: Commissioner for
`Patents
`PO BOX 3450
`Alexandria, VA 22313-1450
`
`( ) transmitted by facsimile to the Patent and
`
`Trademark Office.
`0
`-
`
`Jan 21, 2004
`
`unmwéwaononmnnnnaopéafiab
`
`I
`TRANSMITTAL OF CERTIFIED COPY OF PRIORITY DOC F
`~
`WEIVED
`
`Commissioner for Patents
`PO BOX 1450
`Alexa-ndria, VA 22313—1450
`
`‘
`
`‘
`
`JAN 2 8 2804 .
`Technology Center 2100
`
`Sir:
`
`'
`In reply to the notice of allowance dated December 12, 2003, Applicant hereby
`
`submits a certified copy of the priority document, Israeli patent application No. 126,292 filed
`
`September l8, 1998.
`
`January 21, 2003
`
`Respectfully submitted
`
`LOSANGELES il6546vl
`
`Attorney for App icants
`
`
`
`
`1
`
`
`
`
`
`7R1!!!" HJ‘TT]
`
`STATE OF ISRAEL
`
`Ministry of Justice
`Patent Office
`
`u‘uamnn T‘Iflm
`U‘Ulfl'fli'l TDD}?
`
`This is to certify that annexed
`
`‘
`
`13‘5”?!
`
`‘3 WWW? HNT
`
`hereto is a true copy of the
`
`as
`
`originaiiy
`
`documents
`.
`.
`deposfled With
`_
`,
`apphcatlon
`‘
`particulars are specified on the
`
`the
`
`of
`
`patent
`,
`whmh
`
`first page of the annex.
`
`‘73]
`
`131113] WWW” m3
`
`TTE’BIF‘EHJ
`"ILUT’J'I
`i
`E
`a
`mean
`
`131}
`
`umnnnn
`TWTIHD'?
`I
`""37 meg?
`
`WEIR")?! T113133 wmmn
`
`.naem 7(1)
`
`
`
`
`T1115 wm—WI—mw‘l3 4n“ 23' £3; “REM
`
`5
`
`
`
`°__,:.,_«
`w “1:33:21
`
`w //W
`n‘uman
`Coriir'riins'éione of Patteni ls
`
`:3:
`'
`
`‘.
`
`WEUNTI]
`
`Certified
`
`
`
`2
`
`
`
`.
`
`nav‘m mmwb
`For Office Use
`
`.
`
`‘
`
`1967 ~ vvawnn ,tnpaonn pm
`PATENTS LAW 5727-1967
`'
`
`'
`
`18 439-1998 "
`
`mmData
`
`awn-mmpm
`Ante/Post'dated
`
`_
`
`LEONID GOLDSTEI‘N
`
`an Israeli citizen
`15 Rapenu Tam Street
`Herzha, ISRAEL.
`
`u 3 p s b n w p :1
`Application for Patent
`
`(mmum bappm 1mm rm um —~ mm ,wpnnn my) pm)
`-
`-
`-
`.
`E (Name and address of applicant, and, In case of a body corporate, place of Incorporation)
`
`pmmfim #93me
`
`15:31:;21N.1
`.r‘pban
`
`mm nnww
`
`
`1""???
`
`nan mum: by:
`
`Owner, by virtue of
`
`7
`
`of an invention, the title of which is:
`
`ummb mm mum mum
`
`-
`
`(Hebrew)
`
`SYSTEM AND METHOD FOR DATA ACCESS
`
`(mmm)
`English
`
`Hereby apply for a patent to be. gramcd to me in rcspéct‘thcreof.
`
`.mm mm: >3 pm m am: 10:73::
`
`-
`
`‘
`
`- npwn nw‘pr
`Application for Division
`
`" 9??” ”1'09 3W}???
`APPa‘ca‘w" 1"” We“ “Adam"
`
`mm; m nww-
`Prioriw Claim
`
`W" "9“”
`Number/Mark
`
`1"“
`Date
`
`Address for Service in Israel
`
`
`
`
`
`mmn I'm-m
`
`‘ mush/n wpnb-
`mug nwpm
`
`
`
`Convemion Coumrv
`
`from Application
`to Pazent/Appl.
`
`N07
`"an
`
`own
`
`
`
`VJ)” ‘11), ‘ ’55:) :ht} ’39"
`
`
` P. O. A.: general/specific - lo fofiow
`
` but-wan mmum mmm mmpb 1mm .
`
`
`
`
`
`
`
`
`’ ,Mp by gig/7K”
`
`WOLFF, BREGMAN AND GOLLER
`P. O. Box 1352
`'
`Ierusalem‘ Israei. 91013
`
`wmnn nnmn
`
`
`Signature of Applicant
`
`WOLFF, BREGMAN AND GOLLER
`:
`
`nwbn mum)
`For Officc Use
`
`3
`
`
`
`SYSTEM AND METHOD FOR DATA ACCESS _
`
`mama? mm 31mm 31mm
`
`
`
`4
`
`
`
`
`
`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 amassing 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 avaiiable 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 (Fi g. 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, 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.
`
`2)
`
`In response to a request from a receiver, the sender attaches a validator to
`
`the sent data. The validator changes at least every time the data changes; in many
`
`5
`
`5
`
`
`
`
`
`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 vaiidator. The sender
`
`keeps track of the data and resends it only if it was changed.
`
`The problems associated with this technique are:
`
`Data is cached according to requests and senders. If the same request is
`
`directed to different servers, cached data cannot be reused.
`
`Requests without concrete data cannot be cached.
`
`The sender must track the cached data, which is not always possible.
`
`a)
`
`to)
`
`c)
`
`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.
`
`A yet further object of the present invention is to maintain accessed data
`
`integrity and to improve security.
`
`6
`
`
`
`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.
`
`'
`
` Summary of the Invention
`
`routers .
`
`The term “gateway” as used herein also includes network proxies and
`
`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. Additionaliy,
`
`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
`
`7
`
`
`
`
`
`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
`
`calculating 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 digitai digest from a receiver/computer computer, if
`
`it has data with the same digest, it sends this data to the receiveticomputer.
`
`In another embodiment of the present invention, a client computer sends to
`a server computer a request inciuding 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 difference(s) between these data is sent.
`
`8
`
`
`
`
`
`In accordance with the present invention, there is therefore provided a
`
`a
`comprising
`a packetvswitched . network,
`in
`access
`system for data
`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 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.
`
`The invention also provides a system for data access in a packetoswitched
`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 computers 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 caiculating a digital digest
`on data stored therein and means for comparison between a digital digest
`
`calculated 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, comprisingsa 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
`
`9
`
`
`
`
`
`storage memory
`
`and
`
`a
`
`processor,
`
`said
`
`sender/computer
`
`and
`
`said
`
`receiver/computer communicating through a network; said sender/computer
`
`further
`
`including 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 digitaldigests.
`
`The invention further provides a method performed by a sender/computer
`
`in a packet-switched network for increasing 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 transmit 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 signai from said receiver/computer at said sender/computer,
`
`said response signal containing a positive, partial or negative indication signal for
`said digitai digest, and if a negative indication signal is received, transmitting
`
`said data from said sender/computer to said receiver/computer.
`
`The invention still fiirther provides a method for increasing data access
`
`performed
`
`by
`
`a
`
`sender/computer
`
`in
`
`a
`
`packet-switched
`
`network,
`
`said
`
`sender/computer including an operating 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 receiver/computer, said response signai
`containing a positive, negative or partial
`indication signal, and if a partiai
`
`indication signal
`
`is received,
`
`said sender/computer
`
`transmitting a
`
`signal
`
`10
`
`10
`
`
`
`auxiliary data.
`
`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 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
`uncovered, forming a positive indication signal and transmitting it back through
`
`said network.
`
`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 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 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
`
` constituting the difference between said principal data and corresponding
`
`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 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 containing a principal digital digest
`and one or more auxiliary digitai digests from said network; searching in
`
`11
`
`11
`
`
`
`
`
`predetermined iocations in said permanent storage memory for data with a digital
`digest substantially identical to said principal digital digest; searching in
`predetermined locations in said permanent storage memory for data with a digital
`digest substantiaiiy 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 further, the invention provides a method for increased data access
`
`performed by a computer system in a packet—switched network, said computer
`system inciuding a network 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 system; 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-switched network, said computer
`system including‘a netWOrk‘ 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 system; said method 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 signai other
`than a positive indication signai transmitted from said receiver/computer to said
`
`12
`
`12
`
`
`
`
`
`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.
`
`Additionally, the invention provides a method for 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 substantially 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
`
`' cotnp'flter.
`
`The invention will now be described in connection with certain preferred
`
`embodiments with reference to the following illustrative figures so that it may be
`
`more fully understood.
`
`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
`
`13
`
`13
`
`
`
`
`
`10
`
`discussion of the preferred embodiments of the present invention only, and are
`
`presented in the cause of providing what is believedto be the most useful and
`
`readily understood description of the principles and conceptual aspects of the
`
`invention. In this regard, no attempt is made to show structurai details of the
`
`invention in more detail than is necessary for a fundamental understanding of the
`invention,
`the description taken with the drawings melting apparent to those
`skilied in the art how the severai 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/computer system according to the present invention;
`
`Fig! 5
`
`is a schematic representation illustrating the interaction between a
`sender/computer and a receiver/computer according to the system of Fig.
`
`4;
`
`Fig. 6 is a flow diagram illustrating the method of operating the sendericoniputerm ,
`
`according to the present invention;
`
`Fig.
`
`7
`
`is
`
`a
`
`flow diagram iiiustrating the method of operating the
`
`receiver/computer according to the present invention;
`
`Fig. 8 is a schematic representation illustrating the interaction between a
`
`sender/computer
`
`and
`
`a
`
`receiver/computer
`
`according
`
`to
`
`another
`
`embodiment of the present invention;
`
`14
`
`14
`
`
`
`
`
`11
`
`Fig.
`
`Fig. 9 is a flow diagram illustrating the method of operating the sender/computer
`according to a further embodiment of the present invention;
`10
`is
`a
`flow diagram iilustrating the method of operating the
`receiver/computer according to the embodiment of Fig. 9;
`Fig. 11 is a block diagram of the configuration of the gateway system according
`to the present invention;
`interaction between a
`the
`c
`representation of
`mputer, and the gateway configuration
`
`Fig.
`
`schemati
`a
`is
`12
`sender/computer, a receiver/co
`
`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-
`m according to the present invention; and
`receiver!computer syste
`f the
`interaction between the
`
`Fig.
`
`schematic representation 0
`a
`is
`15
`sender/computerareceiver/computer system of Fig. 14.
`
`Detailed Description of Preferred Embodiments
`
`The‘perforrnance 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 hetéifi any iaké'th’e 'fdrrri‘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
`ever, just as well be used. For example, a
`method. Other algorithms may, how
`digital digest may be calculated according to the CR
`the CRC algorithm to different subsets or different reorderings of data, or by
`
`C algorithm, or by applying
`
`15
`
`15
`
`
`
`
`
`i2
`
`consecutively applying CR0 and MDS.
`
`In addition, any other algorithm may be
`
`fixed-size binary value calculated from
`it produces -a
`used, provided that
`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 consistsof three parts:
`
`the number of fragment pairs, the array of fragment pairs, and the remainder of -
`
`Di. 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 of octets in the fragment
`(Dist,Length). A marker m1 is set at the beginning of the data Di and a marker
`
`m2 at the beginning of D2.
`
`An octet ml is designated as *m1 and an octet m2 as *mZ. An integer
`
`K > i, which represents a minimal length of a fragment encoded, e.g., K m 3, is
`
`chosen.
`
`As stated above, ml is set at the beginning of D1, m2 at the beginning of
`
`D2, and DistflO is assigned at 14. A loop is then entered:
`
`if ml is at the end of
`
`D1 (16), a number of fragment pairs is saved at 18, and the algorithm is
`‘ seaplane. m is a the end of 132 (20), the rest ofDl from m1 is saved at 22,
`a number of fragment pairs is saved, and the algorithm is completed.
`If *ml
`equals *m2 (24), a subroutine “Fragment” is entered at 26; otherwise, m2 is
`moved by one octet toward the end of D2 and Dist is increased by l at28.
`
`The subroutine “Fragment” proceeds as folioWs:
`
`New markers tl=mi
`
`and tzr—"mz are set and'Lengthr—O is assigned at 30.
`
`It and :2 are moved by an
`
`16
`
`16
`
`
`
`
`
`13
`
`octet toward the ends of D1 and D2 and Length is increased at 32. If :1 is at the
`end of D1, or 1‘2 is at the end of DZ, or *tl does not equai ‘72 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 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 Huffman encoding or by using an arithmetic coding, e.g., as '
`disclosed in US. Patent No. 4,122,440.
`
`Restoration of the data is simple. Marker m2 is set at the beginning of the
`known 132.1 Then for each fragment pair (Dist, Length)
`from the known
`difference, m2 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~receiverlcomputer system according
`Fig. 4. A preferred
`
`invention is schematically illustrated in
`to the present
`embodiment is a network computer system having at least two computers.
`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
`aiso connected to thenetwork. The receiver/computer 46 uses a part of its
`permanent storage memory or its first memory, or both, as network cache
`
`A
`
`17
`
`17
`
`
`
`
`
`14
`
`memory 48. The sender/computer has caiculation 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
`twork cache memory 48. The receiver/computer
`
`digest on data stored in its me
`also has comparison means 54 for comparingb
`digest and a digital digest received from the network.
`
`etween such a calculated digital
`
`An example of a first memo
`permanent storage memory may be a disk driVe, a He
`
`ry couid be a RAM; an exampie of a
`sh RAM or a bubbie
`
`memory.
`
`It
`
`receiver/c
`
`system in different ways. The
`this
`to modify
`possible
`is
`omputer 46 and sender/computer 42 may each include means for
`_ storing the calculated digital digest in its first memory or permanent storage
`ter 46 may have means for calculating
`memory. Additionally, the receiver/compu
`a dig
`ide of its cache
`ital digest on data in its permanent storage memory outs
`memory.
`Furthermore, the system may be modified in such a way that the
`iating the difference between two data
`sender/computer 42 has means 56 for calcn
`
`objects.
`
`\
`
`Interaction between the receiver/computer and the sender/computer is
`\
`depictedin Figs 5 to 7. Thedata 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 network cache memory 48 for data
`with the same digest. Ifit finds such data, it uses it as ifit were received from the
`sender/computer
`42
`and
`issues
`a
`positive
`indication
`signal
`to
`the
`it sends a negative indication signai
`to the
`the
`
`a
`
`negative
`
`indication
`
`signal,
`
`sender/computer. Otherwise,
`sender/computer.
`Upon
`receiving
`
`18
`
`18
`
`
`
`
`
`15
`
`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.
`
`The above—described method may be modified in different ways. For
`
`example, absence of a signai from the receiver/computer for a predetermined
`period of time may be considered by the sender/computer to be a negative
`indication signai. Aiternativeiy, the digital digests, for some data may be stored in
`the permanent storage memory of the sender/computer and obtained from there,
`or a piuraiity of data may be processed in one transaction, a digitai digest being
`caiouiated for each data object and a separate indication signal issued on each
`
`digitai digest. ’
`
`Another method of interaction between the receiver/computer 46 and the
`
`sender/computer 42 is illustrated in Figs. 8-»10. The data sender/computer
`caicuiates a digital digest on the data to be sent (hereinafter, “principai digest”)
`and for one or more other data objects (hereinafter, “auxiiiary digests”). Without
`
`the foliowing data objects may be
`iimiting the scope of the invention,
`recommended:
`(a) a previous version of the data requested; (is) a file similar to
`the data requested. Then the sender/computer sends the principal and auxiiiary
`‘ digests tothe-receiver/computer. - Upon-receiving a message with these digital
`digests from the sender/computer,
`the receiver/computer 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 sender/computer 42 and issues a positive
`
`receiver/computer 46
`to the sender/computer. Otherwise,
`indication signai
`searches its network cache memory 48 for data with the auxiliary digests.
`if it
`
`finds data with a digitai digest substantialiy equal to one of the auxiliary digests,
`
`19
`
`19
`
`
`
`
`
`16
`
`it issues a partial indication signal to the sender/computer, with a reference to the
`
`digest. Otherwise, it issues a negative indication signal to the sender/computer.
`Upon receiving a negative indication signal, the sender/computer sends the data.
`Upon receiving a partial
`indication signal,
`the sender/computer transmits the
`difference between the digital digest of the data required to be sent and that of the
`
`data whose digital digest was found by the receiver/computer. This transaction
`may also begin with the
`receiver/computer
`sending a request
`to the
`
`sender/computer.
`
`A modification of the above method is possible. For example, absence of
`
`the indication signal from the receiver/computer fora predefined period of time
`may be considered by the sender/computer as a negative indication signal, or the
`digital digests for some data may be stored in the permanent storage memory of
`the sender/computer and obtained from there instead of being calculated
`immediately before the transaction. Alternatively, a plurality of 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,
`receiver/computer 46 may search not only in its network cache memory 48, but
`also in predefined locations in its permanent storage memory. Sender/computer
`42 may add to a digest it sends to the receiver/computer information about the
`possible location of the data with that digital digest in the receiver/computer’s
`
`permanent storage memory.
`
`Another embodiment of the present invention is schematically illustrated
`in Fig. 11. Shown is a system comprising a gateway computer or gateway 60
`including an operating unit, a first memory and a processor, and acaching
`
`computer 62 including an Operating unit, a first memory, a permanent storage
`memory and a processor, connected to the gateway 60 through any fast network
`
`20
`
`20
`
`
`
`
`
`1’?
`
`connection 64, e.g., Ethernet. Gateway 60 is connected to a wide-area packet!
`switched network in such a way that network packets sent between at least two
`other computers 42 and 46 pass through the gateway 60. The caching computer
`62 uses a part of its permanent storage memory for network cache memory 66.
`Caching computer 62 has means 68 for calculating the digital digest of data in its
`network cache memory 66, and means 70 for comparison between such a
`calculated digital digest and a digital digest received by gateway computer 60
`from the wide«area network.
`It should be noted that gateway computer 60 may
`
`be integrally formed with the caching computer. The caching computer may
`have means for storing a calculated digital digest in its first memory or permanent
`
`storage memory.
`
`By way of example, operations