Architecture and system for coordinated network-wide redundancy elimination

• US 8,509,237 B2
• Filed: 06/26/2009
• Issued: 08/13/2013
• Est. Priority Date: 06/26/2009
• Status: Active Grant

• Current Assignee: Carnegie Mellon University, Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Akella, Srinivasa Aditya, Anand, Ashok, Sekar, Vyas
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): CHAU, PETER P
• Application Number:
  US12/492,749
• Publication Number:
  US 20100329256A1
• Time in Patent Office: 1,509 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/19 at layers above the network layer network arrangements for networked applications for scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/38 by adapting coding or compression rate
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

A network employing redundancy-aware hardware may actively allocate decompression tasks among different devices along a single path to improve data throughput. The allocation can be performed by a hash or similar process operating on a header of the packets to distribute caching according to predefined ranges of hash values without significant additional communication overhead. Decompression of packets may be similarly distributed by marking shim values to match the earlier caching of antecedent packets. Nodes may use coordinated cache sizes and organizations to eliminate the need for separate cache protocol communications.

Claims

1. An apparatus for reducing redundant network transmissions in a network, the apparatus comprising at least one compressing node and at least a first and second decompressing node along a transmission path from the at least one compressing node, packets from the at least one compressing node passing first through the first decompressing node and then to the second decompressing node, all nodes intercommunicating and spatially separated on the network;

wherein the at least one compressing node compresses redundant packets and marks them for decompression at different ones of the first and second decompressing nodes to spread the computational task of decompressing redundant packets among the first and second decompressing nodes;

wherein the first decompressing node receives packets marked for decompression by both the first and second decompressing nodes and selectively decompresses the received packets only when a given received packet is marked for decompression by the first decompressing node and performs that decompression before forwarding the given received packet to the second decompressing node.

2. The apparatus of claim 1 wherein first and second decompressing nodes selectively store portions of antecedent packets identified by using a predefined rule based on data in the antecedent packets that allocates storage of the portions of the antecedent packets among the first and second decompressing nodes;

and

wherein the at least one compressing node compresses redundant packets by identifying and excising portions of each given redundant packet that are redundant with a given stored portion of an antecedent packet previously passing through the at least one compressing node and wherein the at least one compressing node marks the given redundant packet for decompression at a given decompressing node previously storing the given stored portion of the antecedent packet according to the predefined rule.

3. The apparatus of claim 2 wherein the predefined rule assigns a range to each of the first and second decompressing node and hashes header data of the antecedent packets and stores those antecedent packets whose hash falls within the range assigned to a given first and second decompressing node.

4. The apparatus of claim 2 further including a supervisory node connecting for communication with at least one of the at least one compressing node and first and second decompressing nodes, the supervisory node providing data to the at least one of the at least one compressing node and the first and second decompressing nodes to control the predefined rule according to capabilities of the first and second decompressing nodes.

5. The apparatus of claim 4 wherein the capabilities are selected from a group consisting of:

cache memory size for storing antecedent network packets, cache memory speed, and processor speed.

6. The apparatus of claim 2 further including a supervisory node connecting for communication with at least one of the at least one compressing node and first and second decompressing nodes, the supervisory node providing data to the at least one connected node to control the predefined rule according to network-wide objectives.

7. The apparatus of claim 6 wherein the network-wide objectives are applied to historical measurements of network traffic to control the predefined rule.

8. The apparatus of claim 2 wherein the at least one compressing node excises multiple portions of a given redundant network packet, the multiple portions redundant with portions of different antecedent network packets, and marks the given redundant network packet for decompression of different portions of the given redundant network packet at different ones of the first and second decompressing nodes.

9. The apparatus of claim 1 wherein the at least one compressing node includes a table describing a connection topology of the first and second decompressing nodes and wherein the at least one compressing node checks the table to ensure that the first and second decompressing nodes are on a same transmission path and not compressing different portions of a redundant packet for decompression at both the first and second decompressing nodes if the first and second decompressing nodes are not on the same transmission path.

10. The apparatus of claim 2 wherein the at least one compressing node includes a first storage area for storing portions of antecedent packets also for storage at the first decompressing node and a second storage area for storing portions of antecedent packets also for storage at the second decompressing node, and wherein the first and second decompressing nodes have storage areas equal in size to the first storage area and second storage area respectively, whereby ejection of stored data caused by overflow of the storage areas of the at least one compressing node causes synchronous ejection of stored data in the respective storage areas of the first and second decompressing nodes.

12. The apparatus of claim 2 wherein the first and second decompressing nodes provide decompression of redundant packets only with respect to uncompressed portions of antecedent packets.

13. The apparatus of claim 1 wherein the at least one compressing node and the first and second decompressing nodes are portions of network routers.

14. The apparatus of claim 1 wherein the at least one compressing node and the first and second decompressing nodes are non-router middle boxes attached on a single network line.

11. An apparatus for reducing redundant network transmissions in a network, the apparatus comprising at least one compressing node and at least a first and second decompressing node along a transmission path from the at least one compressing node, all nodes intercommunicating and spatially separated on the network;

wherein the at least one compressing node compresses redundant packets and marks them for decompression at different ones of the first and second decompressing nodes to spread the computational task of decompressing redundant packets among the first and second decompressing nodes;

wherein the first and second decompressing nodes selectively decompress packets according to whether the packets are marked for a particular first or second decompressing node;

wherein the first and second decompressing nodes selectively store portions of antecedent packets identified by using a predefined rule based on data in the antecedent packets that allocates storage of the antecedent packets among the first and second decompressing nodes; and

wherein the at least one compressing node compresses redundant packets by identifying and excising portions of each given redundant packet that are redundant with a given stored portion of an antecedent packet previously passing through the at least one compressing node and wherein the at least one compressing node marks each given redundant packet for decompression at a given decompressing node previously storing the given stored portion of the antecedent packet according to the predefined rule; and

wherein the first decompressing node further communicates with a second compressing node and wherein each of the at least one and second compressing nodes include a storage area for storing portions of antecedent packets marked for storage at the first decompressing node; and

wherein the first decompressing node has first and second storage areas equal in size to the storage area of the at least one and second compressing nodes respectively;

whereby ejection of stored data caused by overflow of the storage area of the at least one and second compressing nodes causes synchronous ejection of stored data in the respective storage area of the first decompressing node.

15. An apparatus for reducing redundant data transmissions in a network, the apparatus comprising at least one compressing node and at least a first and second decompressing node connected in series along at least one transmission path from the at least one compressing node, packets from the at least one compressing node passing first through the first decompressing node and then to the second decompressing node, all nodes intercommunicating and spatially separated on the network and operating according to stored programs executed by electronic hardware;

wherein the at least one compressing node;

(a) receives and stores at least a portion of an antecedent network packet and marks the antecedent network packet for storage of the portion, at one of the first and second decompressing nodes according to a system distributing storage of different network packets from the at least one compressing node among ones of the first and second decompressing nodes;

(b) excises at least a portion of a subsequent network packet that is redundant with the stored portion of the antecedent network packet and marking the subsequent network packet for decompression by a same one of the first and second decompressing node as was marked to store the portion of the antecedent network packet;

wherein the first decompressing node;

(a) receives a given antecedent network packet and stores a portion of the given antecedent network packet as marked by the at least one compressing node for storage by the first decompressing nodes;

(b) receives a given subsequent network packet, which is subsequent to the given antecedent network packet; and

(c) restores a previously excised portion of the given subsequent network packet from the stored portion of the given antecedent network packet using the stored portion of the given antecedent network packet and then forwards the restored given subsequent network packet to the second decompressing node; and

wherein the second decompressing node;

(a) receives a second given antecedent network packet from the first decompressing node and stores a portion of the second given antecedent network packet as marked by the at least one compressing node for storage by the second decompressing node;

(b) receives a second given subsequent network packet, which is subsequent to the second given antecedent network packet; and

(c) restores a previously excised portion of the second given subsequent network packet from the stored portion of the second given antecedent network packet using the stored portion of the second given antecedent network packet.