Method and apparatus for reducing network traffic over low bandwidth links
First Claim
1. A method of reducing network traffic, the method comprising the computer-implemented steps of:
- at a sender, receiving a data block for transmission to a receiver, wherein the sender and the receiver are connected over a communication link;
identifying one or more data chunks in the data block;
computing a signature for each of the one or more data chunks;
for each of the one or more data chunks, performing the steps of;
determining whether that data chunk has previously been transmitted by looking up the signature of that data chunk in a sender index table that associates signatures with unique index values, wherein looking up the signature of that data chunk comprises retrieving, from the sender index table, an index value that is associated with the signature of that data chunk if that data chunk has been previously transmitted; and
creating a new index value, in the sender index table, that is associated with the signature of that data chunk if that data chunk has not been previously transmitted;
wherein, in the sender index table, each signature is a single numeric value that does not include the associated unique index value;
wherein the sender does not cache any previously transmitted data chunks;
creating a message for transmitting the data block to the receiver, wherein;
for each of the one or more data chunks that has previously been transmitted, the message includes the index value that is associated with the signature of that data chunk, but not that data chunk; and
for each of the one or more data chunks that has not been previously transmitted, the message includes that data chunk and the new index value that is associated with the signature of that data chunk;
transmitting the message to the receiver; and
at the receiver, assembling the data block based on the message, wherein;
for each of the one or more data chunks that has previously been transmitted, retrieving that data chunk from a receiver cache of previously transmitted data chunks, wherein that data chunk is located in the receiver cache by looking up the index value for that data chunk received in the message in a receiver index table that associates the unique index values with the locations in the receiver cache of the previously transmitted data chunks; and
for each of the one or more data chunks that has not been previously transmitted, storing that data chunk in the receiver cache and associating, in the receiver index table, the new index value for that data chunk received in the message with the location of that data chunk in the receiver cache.
1 Assignment
0 Petitions
Accused Products
Abstract
A method is disclosed for reducing network traffic. At a sender, a data chunk is identified for transmission to a receiver, which is connected to the sender over a communication link. The sender computes a signature of the data chunk and determines whether the data chunk has been previously transmitted by looking up the signature in a sender index table. The sender index table associates the signatures of previously transmitted data chunks with unique index values. A message is transmitted to the receiver, where if the data chunk has previously been transmitted then the message includes an index value from the sender index table that is associated with the signature of the data chunk. At the receiver, the data chunk is located in a receiver cache that stores the previously transmitted data chunks by looking up the index value included in the message in a receiver index table. The receiver index table associates the unique index values with the locations in the receiver cache of the previously transmitted data chunks.
233 Citations
38 Claims
-
1. A method of reducing network traffic, the method comprising the computer-implemented steps of:
-
at a sender, receiving a data block for transmission to a receiver, wherein the sender and the receiver are connected over a communication link; identifying one or more data chunks in the data block; computing a signature for each of the one or more data chunks; for each of the one or more data chunks, performing the steps of; determining whether that data chunk has previously been transmitted by looking up the signature of that data chunk in a sender index table that associates signatures with unique index values, wherein looking up the signature of that data chunk comprises retrieving, from the sender index table, an index value that is associated with the signature of that data chunk if that data chunk has been previously transmitted; and creating a new index value, in the sender index table, that is associated with the signature of that data chunk if that data chunk has not been previously transmitted; wherein, in the sender index table, each signature is a single numeric value that does not include the associated unique index value; wherein the sender does not cache any previously transmitted data chunks; creating a message for transmitting the data block to the receiver, wherein; for each of the one or more data chunks that has previously been transmitted, the message includes the index value that is associated with the signature of that data chunk, but not that data chunk; and for each of the one or more data chunks that has not been previously transmitted, the message includes that data chunk and the new index value that is associated with the signature of that data chunk; transmitting the message to the receiver; and at the receiver, assembling the data block based on the message, wherein; for each of the one or more data chunks that has previously been transmitted, retrieving that data chunk from a receiver cache of previously transmitted data chunks, wherein that data chunk is located in the receiver cache by looking up the index value for that data chunk received in the message in a receiver index table that associates the unique index values with the locations in the receiver cache of the previously transmitted data chunks; and for each of the one or more data chunks that has not been previously transmitted, storing that data chunk in the receiver cache and associating, in the receiver index table, the new index value for that data chunk received in the message with the location of that data chunk in the receiver cache. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A method of reducing network traffic, the method comprising the computer-implemented steps of:
-
at a sender, identifying a data chunk for transmission to a receiver, wherein the sender and the receiver are connected over a communication link; computing a signature of the data chunk; determining whether the data chunk has previously been transmitted by looking up the signature in a sender index table, wherein the sender index table associates signatures of previously transmitted data chunks with unique index values; wherein looking up the signature comprises retrieving, from the sender index table, an index value that is associated with the signature when the data chunk has been previously transmitted; wherein, in the sender index table, each signature is a single numeric value that does not include the associated unique index value; wherein the sender does not cache any previously transmitted data chunks; transmitting a message to the receiver, wherein if the data chunk has previously been transmitted, then the message includes the index value, retrieved from the sender index table, that is associated with the signature of the data chunk; and at the receiver, locating the data chunk in a receiver cache that stores the previously transmitted data chunks by looking up the index value included in the message in a receiver index table, wherein the receiver index table associates the unique index values with the locations in the receiver cache of the previously transmitted data chunks. - View Dependent Claims (17, 18, 19, 20)
-
-
21. A system for reducing network traffic, comprising:
-
a sender that comprises first one or more processors and first one or more stored sequences of instructions; and a receiver that comprises second one or more processors and second one or more stored sequences of instructions; wherein; the sender and the receiver are connected over a communication link; the first one or more stored sequences of instructions, when executed by the first one or more processors, cause the first one or more processors to perform the steps of; receiving a data block for transmission to the receiver; identifying one or more data chunks in the data block; computing a signature for each of the one or more data chunks; for each of the one or more data chunks, performing the steps of; determining whether that data chunk has previously been transmitted by looking up the signature of that data chunk in a sender index table that associates signatures with unique index values, wherein looking up the signature of that data chunk comprises retrieving, from the sender index table, an index value that is associated with the signature of that data chunk if that data chunk has been previously transmitted; and creating a new index value, in the sender index table, that is associated with the signature of that data chunk if that data chunk has not been previously transmitted; wherein, in the sender index table, each signature is a single numeric value that does not include the associated unique index value; wherein the sender is not operable to cache any previously transmitted data chunks; creating a message for transmitting the data block to the receiver, wherein; for each of the one or more data chunks that has previously been transmitted, the message includes the index value that is associated with the signature of that data chunk, but not that data chunk; and for each of the one or more data chunks that has not been previously transmitted, the message includes that data chunk and the new index value that is associated with the signature of that data chunk; and transmitting the message to the receiver; and the second one or more stored sequences of instructions, when executed by the second one or more processors, cause the second one or more processors to perform the steps of; receiving the message from the sender; and assembling the data block based on the message, wherein; for each of the one or more data chunks that has previously been transmitted, retrieving that data chunk from a receiver cache of previously transmitted data chunks, wherein that data chunk is located in the receiver cache by looking up the index value for that data chunk received in the message in a receiver index table that associates the unique index values with the locations in the receiver cache of the previously transmitted data chunks; and for each of the one or more data chunks that has not been previously transmitted, storing that data chunk in the receiver cache and associating, in the receiver index table, the new index value for that data chunk received in the message with the location of that data chunk in the receiver cache. - View Dependent Claims (22, 23)
-
-
24. An apparatus for reducing network traffic, comprising:
-
one or more processors; a network interface coupled to the one or more processors for sending and receiving one or more packet flows therefrom; and one or more stored sequences of instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of; receiving a data block for transmission to a receiver, wherein the receiver is connected to the network interface over a communication link; identifying one or more data chunks in the data block; computing a signature for each of the one or more data chunks; for each of the one or more data chunks, performing the steps of; determining whether that data chunk has previously been transmitted by looking up the signature of that data chunk in a sender index table that associates signatures with unique index values, wherein looking up the signature of that data chunk comprises retrieving, from the sender index table, an index value that is associated with the signature of that data chunk if that data chunk has been previously transmitted; and creating a new index value, in the sender index table, that is associated with the signature of that data chunk if that data chunk has not been previously transmitted; wherein, in the sender index table, each signature is a single numeric value that does not include the associated unique index value; wherein the sender is not operable to cache any previously transmitted data chunks; creating a message for transmitting the data block to the receiver, wherein; for each of the one or more data chunks that has previously been transmitted, the message includes the index value that is associated with the signature of that data chunk, but not that data chunk; and for each of the one or more data chunks that has not been previously transmitted, the message includes that data chunk and the new index value that is associated with the signature of that data chunk; and transmitting the message to the receiver, wherein the receiver assembles the data block based on the message, wherein; for each of the one or more data chunks that has previously been transmitted, the receiver retrieves that data chunk from a receiver cache of previously transmitted data chunks, wherein that data chunk is located in the receiver cache by looking up the index value for that data chunk received in the message in a receiver index table that associates the unique index values with the locations in the receiver cache of the previously transmitted data chunks; and for each of the one or more data chunks that has not been previously transmitted, the receiver stores that data chunk in the receiver cache and associates, in the receiver index table, the new index value for that data chunk received in the message with the location of that data chunk in the receiver cache. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. An apparatus for reducing network traffic, comprising:
-
one or more processors; means for identifying a data chunk for transmission to a receiver, wherein the receiver is connected to the apparatus over a communication link; means for computing a signature of the data chunk; means for determining whether the data chunk has previously been transmitted by looking up the signature in a sender index table, wherein the sender index table associates signatures of previously transmitted data chunks with unique index values; means for retrieving from the sender index table, as part of looking up the signature, an index value that is associated with the signature of the data chunk when the data chunk has been previously transmitted; wherein, in the sender index table, each signature is a single numeric value that does not include the associated unique index value; wherein the sender is not operable to cache any previously transmitted data chunks; means for transmitting a message to the receiver, wherein if the data chunk has previously been transmitted, then the message includes the index value, retrieved from the sender index table, that is associated with the signature of the data chunk; and wherein the receiver locates the data chunk in a receiver cache that stores the previously transmitted data chunks by looking up the index value included in the message in a receiver index table, wherein the receiver index table associates the unique index values with the locations in the receiver cache of the previously transmitted data chunks. - View Dependent Claims (36, 37, 38)
-
Specification