`
`s
`
`t
`
`c,
`
`‘
`
`7/¢Lll
`
`IN THE UNITED STATES PATEN AND TRADEMARK OFFICE
`
`"(J
`t
`
`--
`
`PATENT
`
`Applicant: Leonid Golfdstein
`
`_
`
`Examiner:
`
`Hai Nguyen
`
`Serial No.: 09/398,007
`
`I
`
`l
`
`'
`
`Art Unit:
`
`2142
`
`Filed:
`
`_ September 16, 1999
`
`For:
`
`System and Method for Data Access -
`'
`Attorney Docket: 00:21 973.0003
`
`CERTIFICATE OF
`MAKLING/TRANSMISSION
`(37 c.m.§1.sA)
`I hereby certify that this correspondence is, on the
`date shown 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.
`.
`
`.,
`
`Jan 2}, 2004
`
`H
`RITY no "
`'
`I
`TRANSMITTAL on CERTIFIED com on PRIO c ENED
`
`Commissioner for Patents
`
`‘
`
`AlW_”d"‘a’ W‘ 223134450
`Sir:
`
`Technology Center 2100
`
`-
`In reply to the notice of allowance dated December 12, 2003, Applicant hereby
`
`suomits a certified copy of the priority document, Israeli patent application No. 126,292 filed
`
`September l8, 1998.
`
`January 21, 2003
`
`LOSANGELES il6546vl
`
`Respectfully submitted
`
`
`
`Proxyconn, Inc.
`Exhibit No. 2004
`
`
`
`
`
`'7 R1 (D " I11‘ TT]
`
`STATE OF ISRAEL
`
`Ministry of Justice
`Patent Office
`
`U"l']!-JIIJTH1 T'|UJ1’]
`
`U‘l'J]flEli1 TIDUJ7
`
`This is to certify that annexed
`
`hereto is a true copy of the
`
`documents
`
`as
`
`originaiiy
`
`deposited with
`
`the
`
`patent
`
`application
`
`of
`
`which
`
`particulars are specified on the
`
`first page of the annex.
`
`D"El"l3"l
`
`"'3
`
`:"lT113}T? HNT
`
`'70]
`
`[P113] U‘|7TT1Ju'1
`
`fit}
`
`TTE?§Ti"E{13
`
`U"‘:}TJUT]:"'|
`
`F1[.Ui7Zla'l
`
`U1}
`
`TF7"T1H3'?
`
`U"‘1'J'!Elfl
`
`‘'37
`
`13313217
`
`1'|LUR"3Tl
`
`T1TJ}J.'1
`
`u*n"1t13"m
`
`.11‘,-3331'} 7(1)
`
`
`
`"lEllN1"l]
`
`Certified
`
`
`
`D
`
`-“W/’*'* ‘-”"”‘””
`For Office Use
`
`'
`
`l
`
`.
`
`7
`
`1957 ~ rvzwmn ,tnuJosm pm
`PATENTS LAW 5727-1967
`'
`
`'
`
`18 -u9-19sa 7%
`
`mmData "’""”°m?"“
`
`_
`
`A““’m°5"d“‘°d
`
`
`
`LEONID GOLDSTEIN
`
`an Israeli citizen
`15 Rabenu Tam Street
`Herzlta, ISRAEL.
`
`:1 w ‘.7 2
`U 3 D 9 tr
`Application for Patent
`
`(mmmm mzm-—-— damn rm u:b1—- mm ,\vp::m1 mu) gm)
`E (Name and address of applicant, and, in case of a body corporate, place of incorporation)
`
`l”°W‘75l3 '-F’31N5'
`
`1
`_n,:73.m
`
`mfi mww
`
`
`13"???
`
`nan BNSIJN '1»:
`
`Owner, by ‘virtue of
`
`_
`
`of an invention, the title of which is:
`
`ummb mm mmm nzmm
`
`-
`
`(Hebrew)
`
`SYSTEM AND METHOD FOR DATA ACCESS
`
`tmtmun)
`English
`
`Hereby apply for a patent to be. gransccl to me in rcspectthcreofl
`
`.u:-as nib» >3 pm 7:: rum: wpan
`
`.
`
`‘
`
`- -.-man nv:p:*
`'
`Applica1ionforDivisl0n
`
`' ‘I993 0199 31\’Ji7='
`A 3‘
`'
`f P
`mad‘ ‘
`PP‘°“"°" °' “W0
`‘"0"
`
`711:7-r;:1v1 nwwr-
`Prioritvclaim
`
`
`
`
`mug nw,-:31:
`
`
`from Application
`No.
`'0):
`No.
`"an
`Date
`211973
`Date
`ow:
`
`
`
`
`mmtn rm-m
`Convention Coumrv
`
`T’*“"
`Dale
`
`
`
`1*=’°/“*9”
`Number/Mark
`
`
`
`7 uau::b/nwp:b-
`to Patent/Appl.
`
`
`
`
`
`um» ‘mt - 755:7 :97: mn-
`
` P. O. A.: generalfspccific - to follow
`
`
`
` bmwvn u9:mu:m mmm mmnb wan ,
`
`Address for Service in Israel
`
`WOLFF, BREGMAN AND GOLLER
`P. O. Box 1352
`'
`lerusalem. Israel. 91013
`
`
`
`
` vipmn mama
`Signature of Applicant
`
`This
`
`of
`
`I993
`
`\X/OLFF, BREGMAN AND GOLLER
`
`
`‘ by:
`
`nawbn mnmb
`For Officc Use
`
`
`
`SYSTEM AND METHOD FOR DATA ACCESS _
`
`tzavnma‘: mm nuwn tnrrwrz
`
`
`
`Field of the Invention
`
`The present invention relates to data access in networks. Specificaliy, 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 ciient
`
`(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-knowntechniques 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 dataentity 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
`
`
`
`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)
`
`in)
`
`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.
`
`
`
`Summary of the Invention
`
`The terms “data” or “data object” as used herein refer to a tile or range of
`
`octets in a file, a range of frames in a video strearn 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 sarne digital
`digest as that of the data to be sent, it can be assumed with sufficient probability
`for most practical applications that
`the receiver/cornputer 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
`
`
`
`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 pacl<et—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
`
`p 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 identicai to one of
`
`the received digests, only the difference(s) between these data is sent.
`
`
`
`In accordance with the present invention, there is therefore provided a
`
`a
`comprising
`a packeoswitched . 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 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 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 calculating 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, comprisingaa 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 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 digitaledigests.
`
`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 digitai
`
`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 fiarther 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
`
`
`
`constituting the difference between said principal data and corresponding
`
`auxiliary data.
`
`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
`
`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.
`
`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
`
`
`
`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 substantially identical to one of said auxiliary digital digests; and if data
`havingithe same digital digest as one of said auxiiiary 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 substantiaiiy
`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 incl‘uding‘a networks 'cache'“1nemory"and ‘being operationaiiy 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
`
`
`
`sender/computer in response to said message containing a digital digest, and
`
`transmitting data with a digital digest substantiaiiy identicai 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 item 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
`
`e computer.
`
`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 iiiustrative
`
`
`
`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 rnaking 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 diagarn of a first embodiment of a sender/computer-
`
`receiver/cornputer 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 sender/cornputer
`
`g
`
`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;
`
`
`
`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 diagam iiiustrating the method of operating the
`receiver/computer according to the embodiment of Fig. 9;
`Fig. 11 is a biock diagram of the configuration of the gateway system according
`to the present invention;
`interaction between a
`the
`ic
`representation of
`uter, and the gateway configuration
`
`Fig.
`
`schernat
`a
`is
`12
`sender/computer, a receiver/comp
`
`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-
`rn according to the present invention; and
`receiver!computer syste
`f the
`interaction between the
`
`Fig.
`
`schematic representation o
`a
`is
`15
`sender/computenreceiverlcomputer system of Fig. 14.
`
`Detailed Description of Preferred Embodiments
`
`Theperforrnance 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 heteiii satay taltethe 'fo‘1"rri”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 MD5
`algorithm, described in RFC 1321 by R. Rivest, which is a preferred calculation
`however, just as well be used. For example, a
`method. Other algorithms may,
`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
`
`
`
`l2
`
`consecutively applying CRC and MD5.
`
`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 -
`
`Dl. 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 ml is set at the beginning of the data Di and a marker
`
`m2 at the beginning of D2.
`
`An octet ml is designated as *ml and an octet m2 as *m2. An integer
`
`K > i, which represents a minimal length of a fragment encoded, e.g., K “A 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 ml is at the end of
`
`D1 (16), a number of fragment pairs is saved at 18, and the algorithm is
`i completed. If m2 is at the end of D2 (20), the rest ofD1 from ml is saved at 22,
`a number of fragment pairs is saved, and the algorithm is completed.
`If *mi
`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 1 at.28.
`
`The subroutine “Frament” proceeds as foliowst
`
`New markers tl=ml
`
`and t2=—"m2 are set and"Length*0 is assigned at 30.
`
`It and :2 are moved by an
`
`
`
`13
`
`octet toward the ends of D1 and D2 and Length is increased at 32. If :1 is at the
`end of D1, or 12 is at the end of D2, or *t1 does not equal "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, ml 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 firrther reduced in size by using
`the per se known Huffman encoding or by using an arithmetic coding, e.g., as '
`disclosed in U.S. Patent 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, 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/computetureceiver/computer 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/cornpnter”) 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/cornputer”) 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
`
`
`
`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 cornparingb
`digest and a digital digest received from the network.
`
`etween such a calculated digital
`
`It
`
`receiver/c
`
`in different ways. The
`system,
`this
`to modify
`possible
`is
`omputer 46 and sender/computer 42 may each‘
`include means for
`al digest in its first memory or permanent storage
`_ storing the calculated digit
`ter 46 may have means for calculating
`memory. Additionally, the receiver/cornpu
`a dig
`side of its cache
`ital digest on data in its permanent storage memory out
`e, the system may be modified in such a way that the
`iating the difference between two data
`
`memory.
`Furtherrnor
`sender/computer 42 has means 56 for calcu
`
`objects.
`
`\
`
`\
`eceiver/computer and the sender/computer is
`Interaction between the r
`depicted in Figs. 5 to 7. The data sender/computer 42 calculates a digital digest
`its
`the “calculated digest to
`on the data in means 50 and then transm
`receiver/computer 46. The receiver/computer receives the digtal digest from
`sender/computer 42 and then searches its network 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
`e indication signal
`to the
`sender/computer. Otherwise,
`it sends a negativ
`sender/computer.
`Upon
`receiving
`a
`negative
`
`indication
`
`signal,
`
`the
`
`
`
`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 signal 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 pluraiity of data may be processed in one transaction, a digitai digest being
`caicuiated 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 iiiustrated 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
`iirniting the scope of the invention,
`recommended:
`(a) a previous version of the data requested; (b) a file similar to
`the data requested. Then the sender/computer sends the principal and auxiiiary
`i digests to‘the-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 datauis 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 substantialty equai to one of the auxiiiary digests,
`
`
`
`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 signai, 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 for ‘a 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 senderfcornputer and obtained from there instead of being calcuiated
`i-rnrnediately before the transaction. Alternatively, a pluraiity 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 aiternatively,
`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/cornputer’s
`
`perrnanent 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
`
`
`
`i7
`
`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 caicuiated digital digest in its first memory or permanent
`
`storage memory.
`
`By way of example, operations which may be performed in such a system
`will now be described with reference to Figs. 12 and 13. The gateway‘ 60,
`operationally interposed between a sender/computer 42 and a receiver/computer
`46,
`intercepts
`a digital digest
`sent
`from , the sender/computer
`to the
`receiver/computer, saves it
`in its memory, and pas