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.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    Not applicable 
       BACKGROUND OF THE INVENTION 
       [0002]    The present invention relates to computer networks and, in particular, to architectures and devices for increasing the effective network bandwidth. 
         [0003]    Computer networks provide for the exchange of digital data among computers over a variety of media including electrical cable, optical fiber, and radio links. Commonly, the data is broken into data packets each provided with a header indicating a destination for the packet and a packet sequence number. The packets are forwarded over a complex and changing network topology through the agency of “routers” which read the packet headers and forward the packets on particular links to other routers according to a router table. At the destination, the packets are reassembled. 
         [0004]    The term “router” as used herein will refer broadly to any network node processing data packets for the purpose of communicating them through a network and may include hubs, switches, and bridges as well as conventional routers. 
         [0005]    The bandwidth of a network is a general measure of the rate of data transfer that can be obtained. Limits on bandwidth can result from physical limitations in the media of the links between nodes, for example, caused by the impedance of electrical conductors, as well as from processing limitations of the node hardware such as limitations of processor speed or memory capacity. While bandwidth limitations can generally be addressed by over-provisioning the network (e.g. adding additional links and faster hardware) these measures can be costly. Increased demand for high bandwidth content (e.g. video) and the importance of accommodating highly variable network traffic, for example “flash crowds”, makes it desirable to find ways to increase the bandwidth efficiency of existing networks. 
         [0006]    The effective bandwidth of the network may be effectively increased by a number of software techniques. “Traffic engineering” may be used to allocate the routing of data to spread the load evenly across network links by central control of the routing tables or the like. This technique, by eliminating congestion, improves the effective bandwidth of the network. Traffic engineering can be limited, however, by the difficulty of anticipating rapid variation in traffic volumes and coordinating spatially separate routers. 
         [0007]    Data compression can also be used to increase the effective bandwidth of the network. Thus, for example, video can be compressed using an MPEG compression system to significantly decrease the amount of data required to support a video transmission. 
         [0008]    Application layer caching can also be used to improve the effective bandwidth of a network by taking commonly used network data and placing it in proxy caches at various locations on the network. The proxy caches limit the need to transmit the data over the network when it is subject to separated requests. 
         [0009]    Improved network capacity can also be provided by monitoring and removing packet-level redundancy, for example, at network routers or hardware “middleboxes” attached to routers. Such systems will be termed “redundancy-aware devices” and generally operate independently of the application layer by inspecting packets for redundancy, removing the redundant strings from the packets (henceforth referred to as “compression” or “encoding”), and allowing the removed material to be reconstructed at a downstream cache (referred to as “decompression” or “decoding”), before it is forwarded to the intended destination. The removal and reconstruction is transparent to the source and destination end-systems and requires no separate upgrades to the end-systems. 
       SUMMARY OF THE INVENTION 
       [0010]    The present inventors have recognized that the throughput of redundancy-aware devices, and hence the effective improvement in network capacity, can be substantially increased by intelligently allocating compression and decompression responsibilities across a network of devices. This allocation accommodates the asymmetry between the processing time required for compressing packets and decompression packets (driven largely by differences in the required number of memory accesses), spreads caching responsibilities to better utilize the available memory resources, and better addresses “bottlenecks” caused by network topology or changing traffic patterns. Significantly, packet caching and decompression need not be performed at the downstream node immediately adjacent to the compressing node. This has two advantages. First, this avoids a repeated sequence of compression-decompression actions along a series of routers, which is especially important since compression is a resource-intensive operation. Second, it magnifies the benefits of each decompression action, in that each decompression saves the transfer of content across several router-hops in the network. 
         [0011]    Specifically, the present invention provides an apparatus for reducing redundant network transmissions in a network having a compressing node and one or more decompressing nodes along a transmission path from the compressing node. The compressing node marks the compressed packets for decompression at one of the first and second decompressing nodes, to spread the computational task of decompressing redundant packets among the first and second decompressing nodes. While marking, the compressing node may consider that the allocated node for decompression would have antecedent packet in its store to decompress the packet. The first and second decompressing nodes selectively decompress packets marked for the given first or second decompressing node. 
         [0012]    It is thus a feature of a least one embodiment of the invention to distribute decompression tasks among nodes for improved load sharing and increased throughput. 
         [0013]    The first and second decompressing nodes may selectively store antecedent packets identified by using a predefined rule based on data in the antecedent packets and allocate storage of the antecedent packets among the first and second decompressing nodes. The compressing node may compress redundant packets by identifying portions of each given redundant packet that are redundant with a given stored antecedent packet previously passing through the compressing node and the compressing node may mark the given compressed redundant packets for decompression at a given decompressing node previously storing the antecedent packet according to the predefined rule. 
         [0014]    It is thus a feature of a least one embodiment of the invention to allocate caching burdens associated with compression among different nodes by using preexisting data of the packets. 
         [0015]    The predefined rule may assign a range to each of the first and second decompressing node and hash the header data of the antecedent packets, storing those antecedent packets whose hash falls with in the range assigned to the node. When ranges are overlapping, an antecedent packet can be stored in more than one decompressing node, and the compressing node can mark the given packet, redundant with the antecedent packet, for decompression at any one of the decompressing nodes storing the antecedent packet. 
         [0016]    It is thus a feature of a least one embodiment of the invention to provide a simple allocation system that admits to adjustment of caching and decompression burdens by a simple adjustment of hash ranges. 
         [0017]    The invention may employ a supervisory node connecting for communication with the compressing and decompressing nodes; the supervisory node providing data to the connected nodes to control the predefined rule according to capabilities of the compressing node and the decompressing nodes. 
         [0018]    It is thus a feature of a least one embodiment of the invention to permit dynamic changes to the predefined rule to accommodate historical and current patterns in network traffic, information about the nodes&#39; hardware capabilities, for example memory capacity or memory speed or processor speed. 
         [0019]    The supervisory node may take into account different types of suitable network-wide objectives specified by a network operator, along with the prevailing traffic and resource conditions, and optimize these objectives while controlling the allocations. 
         [0020]    It is thus a feature of a least one embodiment of the invention to allocate responsibilities to different devices to suitably optimize different operator-specified objective functions, while respecting the resource constraints of the devices. 
         [0021]    Instead of a predefined rule for the decompressing nodes, the compressing node may also decide at runtime which decompressing nodes should store a given packet. The compressing node can indicate that using/adding extra bits in the packet header. 
         [0022]    The compressing node may excise multiple portions of a given redundant network packet, the portions redundant with different antecedent network packets, and may mark the given redundant network packet for decompression of different portions at different of the first and second decompressing nodes. 
         [0023]    It is thus a feature of a least one embodiment of the invention to permit the allocation of decompression tasks for a single packet among multiple decompressing nodes. 
         [0024]    The compressing node may include a table, or its logical equivalent, describing the connection topology of the first and second nodes for each transmission path connected to compressing node. The compressing node may check the table to ensure that the first and second decompressing nodes for the compressed packet are on the same transmission path and not compress different portions of the compressed packet for decompression at both the first and second nodes if the first and second decompressing nodes are not on the same transmission path. The compressing node may also check the table to ensure that the compressed packet can be decompressed along the transmission path, when the compressed packet and the corresponding antecedent packet have different transmission paths. 
         [0025]    It is thus a feature of a least one embodiment of the invention to provide a mechanism for preventing decompression that would require the single compressed packet to traverse divergent paths from the compressing node. 
         [0026]    The compressing node may include 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 so that 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 areas of the first and second decompressing nodes. 
         [0027]    It is thus a feature of a least one embodiment of the invention to provide coordination between limited cache resources on separate nodes without the need for independent cache coordination signals between the compressing and decompressing nodes. 
         [0028]    A decompressing node may be on the transmission path from at least a first and second compressing node and the first and second compressing nodes may include storage areas for storing portions of antecedent packets marked for storage at the decompressing node. The decompressing node may have first and second storage areas equal in size to the storage areas of the first and second 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 areas of the decompressing node. 
         [0029]    It is thus a feature of a least one embodiment of the invention to permit a single decompressing node to coordinate its cache structure with multiple compressing nodes, again without communication of ancillary data. 
         [0030]    The decompressing node may provide decompression of redundant packets only with respect to uncompressed portions of antecedent packets. Analogously, the compressing node may only compress packets with respect to uncompressed portions of antecedent packets. 
         [0031]    It is thus a feature of a least one embodiment of the invention to avoid problems of decompressing data at decompressing nodes using cached data at the decompressing node that is not fully decompressed. 
         [0032]    The compressing node and the first and second decompressing nodes may be components of network routers or may be non-router middle boxes attached to a single network linecard. 
         [0033]    It is thus a feature of a least one embodiment of the invention to provide a system that may be flexibly integrated into different network devices. 
         [0034]    This architecture can be extended to multiple compressing nodes on a transmission path, where caching and compression responsibilities are distributed across different compressing nodes, similar to the manner in which the caching and decompressing responsibilities are distributed across decompressing nodes. The decompressing node can have storage area, per compressing node, per transmission path, and similar techniques can be used for coordinating the cache structure without any independent communication. 
         [0035]    It is thus a feature of a least one embodiment of the invention to provide a system that may have multiple compressing devices on a network path. 
         [0036]    The above architecture can also be applied to other types of redundancy-aware devices that may compress traffic contents more generally at conceptual “object” rather than physical packet granularities. 
         [0037]    It is thus a feature of a least one embodiment of the invention to provide a system that may compress and decompress traffic contents at different logical granularities. 
         [0038]    These particular objects and advantages may apply to only some embodiments falling within the claims and thus do not define the scope of the invention. 
     
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
         [0039]      FIG. 1  is a simplified diagram of prior art redundancy-aware routers using look-up tables of cached antecedent packets at compressing nodes to remove redundant data through the insertion of a shim and using similar caches at decompressing nodes to restore the shimmed data; 
           [0040]      FIG. 2  is a figure similar to that of  FIG. 1  showing the present invention&#39;s allocation of the decompressing of network packets among different decompressing nodes along a single path; 
           [0041]      FIG. 3  is a diagram showing the compressed packets used in the process of  FIG. 2 ; 
           [0042]      FIG. 4  is a diagram of the coordinated cache structures used in compressing nodes and decompressing nodes; 
           [0043]      FIG. 5  is a block diagram of hardware suitable for implementing compressing or decompressing nodes; 
           [0044]      FIG. 6  is a flow chart of a program executed on the hardware of  FIG. 5  for a decompressing node; 
           [0045]      FIG. 7  is a simplified diagram of information contained in the overlap table of  FIG. 6 ; 
           [0046]      FIG. 8  is a flow chart of a program executed on the hardware of  FIG. 5  for a decompressing node; 
           [0047]      FIG. 9  is a schematic representation of the connection of the supervisory node to the compressing and decompressing nodes to provide hash ranges to the nodes; and 
           [0048]      FIG. 10  is a network diagram showing implementation of the present invention on middle boxes. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0049]    Referring now to  FIG. 1 , a network  10  may include a set of network nodes  11  and  12  interconnected by media  14  defining paths between nodes  12 . The media may be, for example, electrical cable, optical link, or radio link or the like. 
         [0050]    A packet  16  with redundant payload information may arrive at a compressing node  11  which reviews the payload against a cache table  18  holding payloads for antecedent packets  20  previously passing through node  11 . Payload data of the packets  20  (or portions of that data) in common with the payload data of instant packet  16  (here represented by the letter A) may be identified by a search of the table  18  and this “redundant” data A removed from the instant packet  16  and replaced by a shim  22  to create a compressed packet  24 . The shim  22  may include a logical index number (here represented by 1), such as a hash, identifying the redundant information (A) within the cache table  18 . 
         [0051]    The compressed packet  24  may be received by a decompressing node  12  having a cache table  18 ′ identical to cache table  18  which may be indexed using the index value (1) contained in the shim  22  to replace the shim  22  with the redundant information (A) to produce decompressed packet  27  identical to compressed packet  16 . 
         [0052]    Generally the process of compressing of node  11  is more demanding of hardware resources than the process of decompressing of node  12 , principally because far more memory accesses are required to identify redundant data at node  11  than to find the indexed redundant data at node  12 . Accordingly, in the simple topology shown in  FIG. 1 , compressing node  11  represents a bottleneck in data throughput. 
         [0053]    Referring now to  FIG. 2 , alternatively, multiple compressing nodes of  11   a - 11   c  may connect to a first decompressing node  12   a  creating a bottleneck at the decompressing node  12   a  caused by a “funneling in” of data to this interior node. In both cases, throughput may be compromised. 
         [0054]    Referring still to  FIG. 2 , the present invention generally provides a method of flexibly yet systematically allocating decompression tasks to multiple decompressing nodes  12  not necessarily having direct connection to the compressing node  11 . Using the present invention, the tasks of decompressing data from the nodes  11   a - 11   c  may be allocated over multiple different downstream nodes  12   a - 12   c  for improved load sharing even though compressing nodes  11   a - 11   c  (which may be ingress nodes of the network) are only connected directly to decompressing node  12   a.    
         [0055]    Thus, a first compressed packet  24   a  from compressing node  11   a  may have a shim  22   a  providing not only an index value (1) but also data (c), in this case, indicating that the decompression should be performed at decompressing node  12   c . Likewise, second compressed packet  24   b  from compressing node  11   b  may have a shim  22   b  directing its decompression to occur at decompressing node  12   b , and third compressed packet  24   c  may have a shim  22   c  directing its decompression to occur at decompressing node  12   c . As will be described in more detail below, this allocation process may be controlled to conform to the topology of the system, the demands of network traffic, and the capabilities of the nodes  11  and  12 . 
         [0056]    In one embodiment of the invention, the cache tables  18   a - c  have different contents reflecting a similar allocation of cache responsibilities for “antecedent” data packets that fill the cache tables  18   a - 18   c  and that are used for the decompression. Generally, then, the responsibilities for decompressing compressed packets  24  will follow the responsibilities for caching the antecedent packets that will be used to decompress the packets  24 . In one embodiment, the responsibility for caching is determined by a simple hashing of the header of the packet and a comparison of the hash value to preestablished ranges stored in each decompressing node  12  as a cache manifest. 
         [0057]    Referring now to  FIGS. 2 ,  3  and  6 , the invention may be implemented by a program  28  executed by the compressing node  11  receiving a new packet  16  as indicated by process block  30 . Per process block  32 , the header information of the packet  16 , including the IP header  34  and transport header  36  as shown in  FIG. 3 , will be hashed to a value having a range, for example, between zero and one. The headers  34  and  36  generally include the source/destination IP address, port and protocol, and the Internet Protocol identification field, but can be any invariant field that does not change in the packet  16  as the packet is forwarded along the routing path from the compressing node  11  through the decompressing nodes  12 . 
         [0058]    At process block  35 , the hash range is compared to a caching manifest representing the union of hash ranges that have been: (1) preassigned to each of the decompressing nodes  12   a - 12   c  communicating with the given compressing node  11  when the decompressing nodes  12   a - 12   c  were commissioned or (2) assigned dynamically by a supervisory node as will be described below. If the hash range is not within the caching manifest, then the packet  16  is forwarded without compression, as indicated by process block  37 , because it will not be able to be decompressed by the downstream decompressing nodes. 
         [0059]    Assuming that the hash range is within the caching manifest, then at decision block  38 , it is determined whether the payload of the packet  16  matches an entry of cache table  18  of the compressing node  11 . If not, then at process block  40 , the payload is stored in the cache table  18  along with the hash value as an antecedent packet whose data may be used for the compression of later packets. The storage may be accompanied by the ejection of a previously stored payload value in a FIFO arrangement or other deterministic cache management technique. The packet is then transmitted at process block  37  uncompressed. 
         [0060]    The process of identifying payloads within the cache table  18  and storing new payloads may use standard techniques known in the art of redundancy-aware devices or the technique described in co-pending application Ser. No. 12/418,396 filed Apr. 3, 2009 by some of the inventor of the present application and hereby incorporated by reference. 
         [0061]    If at decision block  38 , a match is found between the new packet  16  and data in the cache table  18 , then at decision block  42 , the compressing node  11  evaluates an overlap table to determine whether decompressing nodes  12  previously having stored the matching packet (or packets) of the cache table  18  are along a single path from the compressing node  11 . This is to ensure that the compressed packet can be decompressed by subsequent nodes as will be explained in detail below. 
         [0062]    If at decision block  42  it is determined that the packet  16 , once compressed by node  11 , will be received by the necessary decompressing nodes  12 , then at process block  44 , the redundant information in the new packet  16  (found in the cache table  18 ) is removed and replaced with a shim. The shim will be shorter than the replaced data and thus this operation effects a compression of the packet  16 . Once the compression is complete, the compressed packet  24  is transmitted at process block  37 . 
         [0063]    Referring now to  FIG. 3 , the shim  22  will typically replace only a portion of the payload  46  (unless there is a complete match between the current payload and the payload of an antecedent packet  20 ). Multiple shims may be inserted when there are multiple matches with the data of the cache table  18 . 
         [0064]    The shim  22  contains one or more matching specifications  50  representing information about the data of the cache table  18  replaced by the shim  22 . The matching specification  50  may include the path ID  48  of the matched packet  52 , unless this can be derived downstream by other means. The matching specification  50  also includes the hash  53  previously stored in the cache table  18 , that is, the hash of the header information of the antecedent packet providing the matching data of the cache table  18 . Also included in the specification  50  is a matching region  54  describing the portion of the payload of the antecedent packet matching the new packet  16  expressed in terms of start byte and end byte as will be used for reconstituting the compressed packet  24  at the decompressing node  12 . 
         [0065]    Referring now to  FIG. 8 , a program  60  executing on the decompressing nodes  12  may receive a new packet as indicated by process block  62  and may hash the header of the packet as indicated by process block  64  in a process similar to that described above with respect to process block  32 . The result is compared to a caching manifest of the decompressing node  12  which describes a subset of the range of zero to one that will determine whether the particular decompressing node  12  will cache the packet for use in later decompression of the packet as will be described. 
         [0066]    Referring momentarily to  FIG. 7 , each decompressing node  12  will have caching manifests with different disjoint ranges (depicted as R 1 -R 4 ) so that only one node  12   a - 12   d  will be responsible for caching (and ultimately decompressing) a given shim of a packet. 
         [0067]    Referring again to  FIG. 8 , if at decision block  66  the hash of the header of the arriving packet falls within the range assigned to the particular decompressing node  12  and is not a compressed packet (as indicated by a lack of shims), then at process block  68  the packet is stored in the cache table  18  (possibly with an eviction of a previously stored element) and the packet is retransmitted as indicated by process block  70 . 
         [0068]    If the hash of process block  64  is not within the range assigned to the given decompressing node  12  or the packet is compressed, then at decision block  73 , the hash  53  of the shims of the packet (if the packet has been compressed) are also compared to the caching manifest used at decision block  66 . If there is no match or no compression, the packet is transmitted without modification at process block  70 . 
         [0069]    If there is a match at decision block  73 , then at process block  74 , decompression is performed on the shims that have matching hashes per the process described with respect to  FIG. 1 . 
         [0070]    Referring now to  FIGS. 2 ,  6  and  7 , for compressed packets  24  having multiple shims  22 , decompression may be performed at multiple decompressing nodes  12   a  and  12   b  on a single path. On the other hand, decompression of compressed packets  24  having multiple shims  22  associated with different decompressing nodes  12  cannot be performed if the nodes  12  are on separate paths such as indicated by nodes  12   c  and  12   d  which are on separate paths P 1  and P 2 . Accordingly, as described above at  FIG. 6 , decompressing node  11  provides an overlap table to ensure that all of the ranges of hashes  53  of the shims match to caching manifest of decompressing nodes  12  on a single path. If the decompressing nodes  12  are on multiple paths, the compression is not performed. 
         [0071]    In the above described embodiment, a packet that is compressed by compressing node  11  is not stored in the cache table  18 . Alternatively, compressing node  11  may store only portions of the packet that were not matched. Decompressing nodes  12  may employ a matching strategy. 
         [0072]    Referring now to  FIG. 4 , it is important for this system that the cache tables  18  at the compressing nodes  11  match those at the decompressing nodes  12  both in terms of their particular organizational structure and in terms of the content of the cache tables  18  at any time. This may be accomplished by dividing the cache tables  18  of the compressing nodes  11  and decompressing nodes  12  into sub-tables  71  each holding data associated only with a particular other corresponding node. Thus, for example, the compressing node  11   a  may have sub-table  71  (labeled  12   a  and  12   b ) used exclusively for different decompressing nodes  12   a  and  12   b , respectively, while decompression node  12   a  may have sub-table  71  (labeled  11   a  and  11   b ) used exclusively for different compressing nodes  11   a  and  11   b , respectively. The sub-table  71  labeled  12   a  of compressing node  11   a  is organized identically to and is of identical size to the sub-table  71  labeled  11   a  of decompressing node  12   a  so that the cache tables  18  fill and evict contents identically, to always be synchronized with each other. 
         [0073]    Referring now to  FIG. 9 , the present invention admits to a supervisory node  80  that may logically communicate with the other nodes  11  and  12  as indicated by lines  82 , for example, using special packets communicated over the network. This communication may permit the supervisory node  80  to collect information about the resources of each of the nodes  11  and  12 , for example the size and speed of their memories and their processing speeds. Alternatively or in addition, the supervisory node  80  may collect network statistics indicating the amount of traffic handled by each of the nodes  11  and  12 . 
         [0074]    This information collected by the supervisory node  80  may be used by the supervisory node  80  to determine the caching manifests for the nodes  11  and  12  defining the relative hash ranges of the compressing nodes  12 . Thus, for example, the hash range 72 of node  12   a  having limited resources and high traffic may be reduced with respect to the hash ranges 75 and 76 of nodes  12   b  and  12   c  having less traffic or greater processing resources. The hash ranges measured in terms of the range of the hash function  78  may be dynamically adjusted as traffic conditions change on a periodic basis or may be static and configured at the time of initialization. The supervisory node  80  may set the hash ranges or similar rule for allocating compression and decompression by applying network objectives such as maximum throughput, load leveling, capacity reserves, or the like agains the data collected relating to current and historical traffic conditions. 
         [0075]    Referring now to  FIG. 10 , the present invention may be implemented with the compressing nodes  11  and decompressing nodes  12  within routers  83  connected to multiple other devices through media  14 , or maybe so-called “middle boxes”  84  positioned along a single run of the media  14  so as to intercept traffic along that path. Generally, a decompressing node and compressing node may be in the same device implementing different functions for different connections. 
         [0076]    Referring now to  FIG. 5 , an electronic computer  90  suitable for use in implementing the present invention may include one or more network cards  92 , for example Ethernet cards, providing low-level network communications. The network cards  92  may connect by means of an internal bus  94  with a processor  96  and with a memory  98 , the memory  98  holding, in the case of a router, a router program and table  100  and an operating system  102 . Programs  28  or  60  or both may be stored in the memory together with the necessary cache manifests and overlap matrices to be executed by the processor  96  according to techniques well known in the art. 
         [0077]    It should be understood that the invention is not limited in its application to the details of construction and arrangements of the components set forth herein. The invention is capable of other embodiments and of being practiced or carried out in various ways. Variations and modifications of the foregoing are within the scope of the present invention. It also being understood that the invention disclosed and defined herein extends to all alternative combinations of two or more of the individual features mentioned or evident from the text and/or drawings. All of these different combinations constitute various alternative aspects of the present invention. The embodiments described herein explain the best modes known for practicing the invention and will enable others skilled in the art to utilize the invention.