ARCHITECTURE AND SYSTEM FOR COORDINATED NETWORK-WIDE REDUNDANCY ELIMINATION

• US 20100329256A1
• Filed: 06/26/2009
• Published: 12/30/2010
• 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: Sekar, Vyas, Akella, Srinivasa Aditya, Anand, Ashok
• Granted Patent: US 8,509,237 B2
• Time in Patent Office: Days
• 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 compressing node, all nodes intercommunicating and spatially separated on the network;

wherein the 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 first and second decompressing nodes selectively decompress packets according to whether they are marked for a particular first or second decompressing node.

2. The apparatus of claim 1 wherein first and second decompressing nodes selectively store 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 compressing node compresses redundant packets by identifying and excising portions of each given redundant packet that are redundant with a given stored antecedent packet previously passing through the compressing node and wherein the compressing node marks the given redundant packets for decompression at a given decompressing node previously storing 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 with in the range assigned to the node.

4. The apparatus of claim 2 further including a supervisory node connecting for communication with at least some of the compressing node and first and second decompressing nodes, the supervisory node providing data to the connected 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 the 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 some of the compressing node and first and second decompressing nodes, the supervisory node providing data to the connected nodes to control the predefined rule according to network-wide objectives.

7. The apparatus of claim 4 wherein the network objectives are applied to historical measurements of network traffic to control the predefined rules.

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

9. The apparatus of claim 1 wherein the compressing node includes a table describing a connection topology of the first and second nodes and wherein the 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 the redundant packet for decompression at both the first and second nodes if the first and second decompressing nodes are not on the same transmission path.

10. The apparatus of claim 2 wherein the 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 compressing node causes synchronous ejection of stored data in the respective storage area'"'"'s first and second decompressing nodes.

11. The apparatus of claim 2 wherein the first decompressing node further communicates with a second compressing node and wherein the first 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 nodes may have first and second storage areas equal in size to the storage areas of the compressing nodes respectively;

whereby ejection of stored data caused by overflow of the storage areas of the compressing nodes causes synchronous ejection of stored data in the respective storage area'"'"'s first decompressing node.

12. The apparatus of claim 2 wherein the decompressing node provides compression of redundant packets only with respect to uncompressed portions of antecedent packets.

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

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

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 compressing node, all nodes intercommunicating and spatially separated on the network and operating according to stored programs executed by electronic hardware;

wherein the compressing node;

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

(b) excise at least a portion of a subsequent network packet that is redundant with the stored portion of the antecedent network packet and marking the excised 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 and second decompressing nodes;

(a) receive and store the portion of the antecedent network packet when marked by the compressing node for storage by the decompressing node;

(b) receive and restore the excised portions of the subsequent network packet from the stored portion of the antecedent network packet only when marked for a particular first and second decompressing node using the stored antecedent network packet;

whereby decompressing tasks may be allocated among different nodes.

16. In a computer network of spatially separated nodes along a transmission path including multiple series connected decompressing nodes, a compressing node comprising:

(a) a storage allocator receiving network packets, storing at least portions of the network packets in a memory, and marking the packets for storage at a selected one of the multiple decompressing nodes;

(b) a compressor receiving a given network packet and matching at least portions of the given network packets to portions of network packets in the memory to excise those matched portions from the given network packet and to mark the excision for restoration, and to mark an excised network packet so obtained for decompression by a selected one of the multiple decompressing nodes previously marked for storage of the network packet whose portions stored in memory match to the given network packet.

17. In a computer network of spatially separated nodes along a transmission path including multiple series connected decompressing nodes, a decompressing node comprising:

(a) a storage allocator receiving network packets marked for storage at the decompressing node and storing at least portions of the network packets in a memory;

(b) a decompressor receiving a given network packet marked for decompression at the decompressing node and matching at least portions of the given network packets to portions of network packets in the memory to restore those matched portions into the given network packet; and

receiving other network packets not marked for decompression at the decompressing node and forwarding those other network packets without decompression.