Abstract:
A network employing multiple redundancy-aware routers that can eliminate the transmission of redundant data is greatly improved by steering redundant data preferentially into common data paths possibly contrary to other routing paradigms. By collecting redundant data in certain pathways, the effectiveness of the redundancy-aware routers is substantially increased.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a continuation-in-part of U.S. patent application Ser. No. 12/418,396 filed Apr. 3, 2009, and entitled “Network Routing System Providing Increased Network Bandwidth,” hereby incorporated by reference. 
     
    
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
       [0002]    This invention was made with United States government support awarded by the following agencies: NSF 0626889 and 0746531. The United States government has certain rights in this invention. 
     
    
     BACKGROUND OF THE INVENTION 
       [0003]    The present invention relates to computer networks and in particular to a routing system increasing effective network bandwidth. 
         [0004]    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. 
         [0005]    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. 
         [0006]    The bandwidth of a network is a general measure of the rate of data transfer that can be obtained. Limits on bandwidth can include physical limitations in the media of the links between nodes, for example, caused by the impendence of electrical conductors, as well as processing limitations of the node hardware. 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. 
         [0007]    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. 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. 
         [0008]    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. Some compression can be accomplished in this manner by the network operator trapping and converting files. 
         [0009]    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. 
         [0010]    Improved network capacity can also be provided by monitoring and removing packet-level redundancy, for example, at network routers. Such systems will be termed “redundancy-aware routers” and generally operate independently of the application layer by inspecting packets for redundancy, removing the redundant strings from the packets, and allowing the removed material to be replaced at the destination from a downstream cache. 
       SUMMARY OF THE INVENTION 
       [0011]    The present inventors have recognized that bandwidth efficiency of the network can be greatly boosted by a combination of redundancy-aware routers and a routing system that controls the paths of packets to preferentially steer redundant packets along common paths. By concentrating redundant packets in a single path, the effectiveness of packet redundancy removal is substantially boosted. The routing system makes use of the information about redundancy of packets also used by the redundancy-aware router and thus can be implemented on a local router basis. Alternatively, the routing decisions may be global providing a more comprehensive steering of redundant packets. 
         [0012]    In this regard, the present inventors have developed a practical method for implementing the necessary routing decisions. Experiments using real-world Internet traffic have shown that data reductions of 16 to 50% can be obtained. These results are described further in  Packet Caches on Routers: the Implication of Universal Redundant Traffic Elimination  by Anand et al, SIGCOMM &#39;08, Aug. 17-20, 2008, Seattle, Wash., USA ACM 978-1-60558-175-0/08/08 hereby incorporated by reference. 
         [0013]    Specifically then, the present invention provides a network router for use in a network between different routers. The network router identifies data-redundancy in packets received by the router with respect to a destination of the packets and uses this knowledge of the redundancy of the packets to select a routing path through the network so that a given packet is concentrated on a routing path with other packets having corresponding redundant data. 
         [0014]    It is thus a feature of a least one embodiment of the invention to leverage the capabilities of redundancy-aware routers to substantially increase network capacity. 
         [0015]    The router may modify packets to be transmitted on the network when the packets have redundant data by removing the redundant data and inserting an identification of the redundant data in a previously transmitted packet. Conversely, the router may modify packets received on the network, identifying redundant data of a previously received packet by inserting redundant data from the previously received packet. 
         [0016]    It is thus an object of invention to combine the routing system of the present invention with redundancy awareness. 
         [0017]    The redundant data in packets may be identified by hashing chunks of data in the packets to produce fingerprints that may be compared with previous or subsequent packets, a matching of the fingerprint indicating data redundancy. The comparison of fingerprints is made faster by maintaining a hashtable of fingerprints. The hashtable data-structure may, in one embodiment, employ “cuckoo hashing”. 
         [0018]    It is thus a feature of a least one embodiment of the invention to provide an efficient and rapid method of identifying redundant data at the packet level. 
         [0019]    The selection of the route through the network for a packet having redundant data may be obtained by linear programming, the linear programming configured to reduce a footprint variable over the network, the footprint variable being a function of size of an archetype redundant packet and network path latency. 
         [0020]    It is thus a feature of a least one embodiment of the invention to provide a flexible and powerful technique of optimizing network routes for redundant content. 
         [0021]    The selection of a routing path through the network may consider only packets within a limited subset of destination routers, the subset being less than all of the destination routers receiving packets with corresponding redundant data. 
         [0022]    It is thus a feature of a least one embodiment of the invention to improve scaling of the linear programming problem, permitting faster execution of the linear programming and/or centralization of the route selection process for multiple routers. 
         [0023]    Alternatively or in addition, the selection of a routing path through the network for a packet may first combine redundant content in packets with identical destinations into a virtual larger packet, and the linear programming may operate on the virtual larger packets. 
         [0024]    It is thus a feature of a least one embodiment of the invention to provide a second simplification to improve scalability of the linear programming. Note that this second simplification operates synergistically with the first simplification which makes it easier to construct a virtual packet having the same destinations. 
         [0025]    The network may include a single or multiple ISPs or single or multiple domains. 
         [0026]    It is thus a feature of a least one embodiment of the invention to provide a system that can be expanded as necessary to extremely large networks. 
         [0027]    The network router may use a local processor system fully contained at one node of the network or multiple processor systems contained at multiple nodes of the network and intercommunicating over the network. 
         [0028]    Thus, it is a feature of a least one embodiment of the invention to permit distributed or centralized routing models. 
         [0029]    In this latter centralized model, each interconnected device may sample redundancies of packets associated with particular destinations for a period of time and forward data from the sampling to the route manager, and a centralized device may return data indicating preferred network paths for packets according to packet destinations. In both of the distributed and centralized model, the determination of network paths may be performed episodically, for sampling interval, and those pads used predictably for a predetermined period of time. 
         [0030]    It is thus a feature of a least one embodiment of the invention to permit the use of the present invention in a predictive capacity reflecting an underlying time granularity of redundancy in transmitted data. By using predictive data, the calculation burden may be greatly reduced either in a centralized or distributed model. 
         [0031]    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 
         [0032]      FIG. 1  is a simplified block diagram of a network-aware router suitable for use with the present invention receiving data packets and forwarding them to other routers connected in a network; 
           [0033]      FIG. 2  is a flow chart of a program implemented by the network-aware routers of  FIG. 1 ; 
           [0034]      FIG. 3  is a graphical representation of the analysis of a packet for redundancy per the present invention; 
           [0035]      FIG. 4  is a figure similar to that of  FIG. 3  showing processing of the packet to remove and restore redundant information at a transmitting and receiving router; 
           [0036]      FIG. 5  is a simplified network diagram showing a prior art routing of packets in a simplified example network; 
           [0037]      FIG. 6  is a figure similar to that of  FIG. 7  showing the routing of packets using prior art redundancy-aware routers; 
           [0038]      FIG. 7  is a figure similar to that of  FIGS. 5 and 6  showing the use of redundancy-aware routers combined with redundancy-aware routing of the present invention; 
           [0039]      FIG. 8  is a flow chart providing the additional program steps added to a redundancy-aware router to implement the present invention; 
           [0040]      FIG. 9  is a figure similar to that of  FIG. 3  showing the modification of the data structure of the redundancy of aware router to include a redundancy profile used by an embodiment of the present invention; 
           [0041]      FIG. 10  is a figure similar to that of  FIG. 1  showing centralization of the routing problem to remove processing burden from the hardware at each network node; and 
           [0042]      FIG. 11  is a simplified view of a multi-domain network illustrating expansion of the present invention to an arbitrary network size. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0043]    Referring now to  FIG. 1 , a network  10  may include a set of network vertices  12   a - d  interconnected by network edges  14   a - d . Each of the vertices  12   a - d  may be a network-aware router  18  as is commonly understood in the art with the edges  14  being linking media such as electrical cable, optical link, or radio link or the like. Edge  14   a  in this example is an access point to the network leading typically to another network  16 . In this example, the router  18  of vertex  12   a  may be considered a “source” vertex transmitting data packets  20  from network  16  to “destination” routers  18  of each of vertices  12   b - d.    
         [0044]    As is understood in the art, each router  18  may include network interfaces  22  providing ports associated with each of the edges  14   a - d  that implement an electrical interface between the communication media of the edges  14  and a common internal bus  24  of the router  18 . The bus  24  may communicate with a processor  26  being, for example, a microprocessor or an application-specific integrated circuit (ASIC) or a combination of both, in turn, communicating with a memory  28 . The memory  28  may hold an operating program  30  implementing the present invention, as well as data structures  32  including, for example, a routing table and other data tables as will be described below. 
         [0045]    Referring now to  FIG. 2 , the program  34  of the present invention, as indicated by process block  36 , upon receipt of a data packet  20 , analyzes the data packet  20  for packet level redundancy with preceding data packets. Referring also to  FIG. 3 , the data packet  20  will typically include a data payload  38  being a portion generally holding the data to be communicated over the network  10 . Normally, the data payload  38  is preceded by a header  40  providing data necessary for the operation of the protocol of the network  10  and including, for example, a destination address  42  indicating the ultimate destination of the packet  20  and a packet serial number  44  allowing the data packet  20  to be assembled with other data packets  20  to complete a message. 
         [0046]    At process block  36 , a fingerprint of the payload  38  is developed by applying a sliding window  46  to the payload  38  and applying a hash function  48  to data within this window to produce a series of Rabin fingerprints  50 . Preferably, the fingerprints are maintained in cuckoo hash which provides a constant worst-case down time necessary to do a lookup and has less memory overhead compared to traditional hash-tables. The data window may, for example, be 64 bytes, resulting in the production of S-64 fingerprints for a payload  38  of length S bytes. Predetermined ones of these fingerprints  50  (depending on the degree of data reduction desired) are selected for each packet  20  to form a representative fingerprint  52  for storage in a fingerprint table  53 . While the representative fingerprints  52  are shown collected in a row (depicting their logical connection to the packets), they are in fact distributed in a hash table at hash “buckets” whose addresses are equal to the hash values of the windowed payload  38 . 
         [0047]    If the fingerprints  52  already exist in the fingerprint table  53  (any individual fingerprint  50 ), indicating that the data payload  38  is redundant with a previous data packet  20 , the generated fingerprints are discarded and a data packet  20  is processed as a redundant data packet  20 ′ per process blocks  82  and  83  of  FIG. 2  as will be described in more detail below. 
         [0048]    If the fingerprints  52  do not exist in the fingerprint table  53 , indicating that the data payload  38  is an archetype payload  38 ′ (unique within the experience contained in the fingerprint table  53 ), then the windowed data of the archetype payload  38 ′ associated with the matching fingerprint  52  is stored in a payload table  56 , and a pointer to the archetype payload  38  in the payload table  56 , together with an offset pointer to the matching windowed data of the archetype payload  38 ′, are stored in the hash bucket. The data packet  20  is then processed for normal transmission per process block  80  of  FIG. 2  as will be described in more detail below. 
         [0049]    Each hash bucket of fingerprint table  53  for an enrolled fingerprint  52  also holds a sequential index value  54  incremented for each new fingerprint  52  and archetype payload  38 ′. This index value  54  is used to implement a circular buffer, for example, several gigabytes in size. As the index value  54  is incremented, a “last valid index value” equal to the current index value  54  plus the size of the circular buffer is created. Valid fingerprints  52  may thus be quickly determined by comparing the index value in the hash bucket to the last valid index value. If that index value is greater than the last valid index value, the fingerprint  52  is invalid. This process eliminates the need to erase fingerprints  52  from the fingerprint table  53  allowing new fingerprint values to be simply written over invalid fingerprint values at considerable time savings. 
         [0050]    Referring now to  FIGS. 4 and 2 , a process of enrolling a payload  38  into the fingerprint table  53  and payload table  56  effectively determines whether the payload  38  of the packet  20  is redundant per decision block  39  of  FIG. 2 . At this time, the present invention also assesses of the degree of redundancy (cpy i,j ). 
         [0051]    Referring now to  FIG. 4 , redundant data packets  20  are specially processed to remove the redundant data before transmission. In this process the valid fingerprint(s)  50  previously discovered in the fingerprint table  53  are used to identify the portion  60  of the redundant packet  20 ′ matching the windowed data of the archetype payload  38  associated with the matching fingerprints  50 . An expanding comparison of the redundant data packet  20  and the archetype payload  38 ′ is performed to “grow” the portions  60  in each of the archetype payload  38 ′ and the payload of new packet  20 ′, as indicated by arrows  62 , to determine the full extent of the matching on either side of the portion identified by the fingerprint. 
         [0052]    The amount of matching (cpy i,j ) is saved as a redundancy index value  81  holding, for example, a number of matching bits  84 , the index value  54  ( i ) and a destination address  42  ( j ) to be used as described further below. 
         [0053]    When the full extent of the matching between the archetype payload  38 ′ and the redundant data packet  20 ′ has been determined, the unmatched portions  64  of the packet  20 ′ are spliced around a shim  66  providing the value of the fingerprint  50  (hash address) and a byte range  68  corresponding to the amount that the packet was grown per arrows  62 . The shortened packet  20 ″ is then transmitted as indicated by arrows  70  to a receiving router. 
         [0054]    As indicated by process block  85  of  FIG. 2 , at the receiving router  18 , the shim  66  and fingerprint  50  are removed and the fingerprint  50  used to identify the corresponding fingerprint  50  in the fingerprint table  53  of the receiving router  18 . This corresponding fingerprint  50  is in turn used to identify a stored archetype payload  38 ′ providing a missing section  72  defined by the fingerprint and the byte range  68 . Thus, the full payload  38  for the redundant data packet  20 ′ may be reconstituted at the receiving end. 
         [0055]    Referring now to  FIG. 5 , the operation of a redundancy-aware router may be illustrated by an example network  10 ′ having a source vertex  12   a  (S 1 ) and in turn connected via three separate edges with three first level vertices  12   b - d . Each of these vertices  12   b - d  is connected via single separate edges to corresponding third level vertices  12   e - g , each of the latter of which connects via separate single edges to destination vertices  12   h - j . Vertices  12   h  will be denoted destination D 1  and vertices  12   j  will be to designated destination D 2 . Vertex  12   i  also includes edges to each of destinations D 1  and D 2 . 
         [0056]    Assume now that the source vertex  12   a  needs to transmit packets P i , P i , and P j , to both of destinations D 1  and D 2  where packets P i  provide 100% redundant data with each other and packet P j  provides unique or non-redundant data. In the typical routing situation of  FIG. 5 , normal traffic engineering may route these packets to their respective destinations by the shortest path, thus through vertices  12   b  and  12   e  to destination D 1  and through vertices  12   d  and  12   g  to destination D 2 . This path, assuming similar latencies and bandwidths for each of the edges, provides the shortest number of hops and therefore the most efficient and fastest communication path. 
         [0057]    Referring now to  FIG. 6 , a redundancy aware router system described communicating the same packets on the same network  10 ′ recognizes the redundancy of packets P i  and therefore suppresses one packet P i  to transmit only one packet P i  and packet P j  by the same path as shown in  FIG. 5 . 
         [0058]    Referring now to  FIG. 7 , the present invention operates to concentrate the packet transmissions to a given destination D 1  or D 2  on a common path to leverage the redundancy-aware routers such that only two packets (packets P i  and P j ) are transmitted from vertices  12   a  to  12   c ,  12   f  and  12   i . At vertices  12   i , the packets P i  and P j  are duplicated to be transmitted separately through different edges to destinations D 1  and D 2 . 
         [0059]    Assuming, for the moment, that the capacities and latencies of each of the edges is the same, it will be seen that the present invention makes more efficient use of network resources. Network usage may be quantified by a footprint value of a transmission where the footprint value is the sum of the latency of each edge traversed times the total packet length that needs to be transmitted. If, in this example, all the edges have the same latency and that packets P i  and P j  are the same length (P i ), it will be seen that the footprint of the present invention per  FIG. 7  is 10P i  while the latency of  FIG. 5  is 18P i  and the latency of  FIG. 6  is 12P i    
         [0060]    This concept of footprint may be used to identify the ideal routing for packets based on knowledge of their redundancy, a knowledge which can be readily extracted from information used to create redundancy-aware routers. 
         [0061]    Referring now to  FIGS. 8 and 9  the present invention supplements the redundancy-aware router as previously described by determining redundancy per process block  90  and generating a redundancy index value  81  cpy i,j  per process block  94 . This redundancy index value  81  may be used to create a redundancy profile  92  that supplements the fingerprint table  53  and payload table  56  described above holding the redundancy values  81  linked to a particular redundant payload. By having these redundancy index values, the ideal route for a given packet may be determined by analyzing the footprint for all edges of the network along all possible routing paths and selecting the routing path which minimizes that footprint as indicated by process block  96 . This routing information may then be used to route the packet as indicated by process block  98 . 
         [0062]    One method of quickly assessing the ideal routing path using this criterion is linear programming in which the following objective function is minimized: 
         [0000]    
       
         
           
             
               
                 
                   
                     ∑ 
                     e 
                   
                    
                   
                     
                       ∑ 
                       i 
                     
                      
                     
                       F 
                        
                       
                         ( 
                         
                           P 
                           
                             i 
                             , 
                             e 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0063]    where e are edges between a source vertex (S) and a destination vertex (D), i is an index of distinct packets P i , and F(P i,e ) is the footprint for a unique packet P i  on an edge e between vertices  12  defined as follows: 
         [0000]        F ( P   i,e )= lat   e   ×|P   i |  (2) 
         [0064]    in which lat e  is the latency of a given edge, for example the delay in connecting media, and |P i | is the size of a “distinct” packet, meaning a packet that is an archetype, possibly redundant with other packets. 
         [0065]    The linear programming operates under the following constraints: 
         [0000]      ∀ j,F ( P   i,e )≧ lat   e   ×cpy   i,j   ×rte   j,e   ×|P   i |  (3) 
         [0066]    where rte j,e  is a variable that defines the portion of traffic to destination j that passes along edge e which defines the routing of packets and is computed by the linear programming. The variable rte j,e  is a value between zero and one and may be fractional permitting fractional routing. 
         [0067]    The following additional constraints are observed: 
         [0000]      ∀ e,F ( P   i,e )≦ lat   e   ×|P   i |  (4) 
         [0000]    
       
         
           
             
               
                 
                   
                     ∀ 
                     j 
                   
                   , 
                   
                     
                       
                         ∑ 
                         
                           e 
                           ∈ 
                           
                             
                               δ 
                               - 
                             
                              
                             
                               ( 
                               v 
                               ) 
                             
                           
                         
                       
                        
                       
                         rte 
                         
                           j 
                           , 
                           e 
                         
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           e 
                           ∈ 
                           
                             
                               δ 
                               + 
                             
                              
                             
                               ( 
                               v 
                               ) 
                             
                           
                         
                       
                        
                       
                         rte 
                         
                           j 
                           . 
                           e 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0068]    where eεδ + (ν) is the flow into a vertex and eεδ − (ν) is the flow out of a given vertex v. 
         [0069]    For the source and destination vertices S and D, the following conservation constraints apply 
         [0000]    
       
         
           
             
               
                 
                   
                     ∀ 
                     j 
                   
                   , 
                   
                     
                       
                         
                           ∑ 
                           
                             e 
                             ∈ 
                             
                               
                                 δ 
                                 - 
                               
                                
                               
                                 ( 
                                 S 
                                 ) 
                               
                             
                           
                         
                          
                         
                           rte 
                           
                             j 
                             , 
                             e 
                           
                         
                       
                       - 
                       
                         
                           ∑ 
                           
                             e 
                             ∈ 
                             
                               
                                 δ 
                                 + 
                               
                                
                               
                                 ( 
                                 S 
                                 ) 
                               
                             
                           
                         
                          
                         
                           rte 
                           
                             j 
                             . 
                             e 
                           
                         
                       
                     
                     = 
                     1 
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
             
               
                 
                   
                     ∀ 
                     j 
                   
                   , 
                   
                     
                       
                         
                           ∑ 
                           
                             e 
                             ∈ 
                             
                               δ 
                               + 
                               
                                 ( 
                                 D 
                                 ) 
                               
                             
                           
                         
                          
                         
                           rte 
                           
                             j 
                             , 
                             e 
                           
                         
                       
                       - 
                       
                         
                           ∑ 
                           
                             e 
                             ∈ 
                             
                               
                                 δ 
                                 - 
                               
                                
                               
                                 ( 
                                 D 
                                 ) 
                               
                             
                           
                         
                          
                         
                           rte 
                           
                             j 
                             . 
                             e 
                           
                         
                       
                     
                     = 
                     1 
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0070]    Finally, the capacity of each edge cannot be exceeded expressed as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     ∀ 
                     e 
                   
                   , 
                   
                     
                       
                         1 
                         
                           lat 
                           e 
                         
                       
                        
                       
                         
                           ∑ 
                           n 
                         
                          
                         
                           F 
                            
                           
                             ( 
                             
                               P 
                               
                                 n 
                                 , 
                                 e 
                               
                             
                             ) 
                           
                         
                       
                     
                     ≤ 
                     
                       Cap 
                       e 
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0071]    where Cap e  is derived from the edges transmission capabilities. 
         [0072]    The linear programming described above can be ideally performed for each time interval, during when the redundancy profile more or less remains same. But this may not be known in advance and small time intervals would lead to frequent route computations, so as a practical matter routing paths may be determined for particular destinations based on historical data collected on a periodic basis, and can be triggered to re-compute the routing paths if a significant change in redundancy profile is observed Thus, for example, having determined that it is best to send packets for a particular destination upon a certain route, this route information may be enrolled with the data of the packets or provided to the routers so that all packets to that destination are routed in the same manner for given period of time. This routing will not be perfect because it will at some times be based on stale redundancy profiles  92 , but this approach may represent a practical trade-off between computation burden and network efficiency. 
         [0073]    Referring now to  FIG. 10 , the possibility of routing using historical data allows given routers  18  at vertices  12   a  and  12   b , for example, to collect redundancy information in redundancy profiles  92   a  and  92   b  respectively and forward that data on a periodic basis to a central route manager  100 . The route manager  100  may also collect router table information  102  from each of the routers  18  of vertices  12   a  and  12   b  to create a system map  104  or may be pre-programmed with that network topology. The route manager  100  may then perform the linear programming of process block  96  of  FIG. 8  using an internal processor system  106  optimized for that purpose or having greater capacity than the individual routers. The route manager  100  then returns routing information  108  to the particular routers  18  at vertices  12   a  and  12   b  on a periodic basis. In this way, the hardware of the routers may be simplified and specialized hardware may address the task of optimal routing. By centralizing the routing problem, other traffic engineering considerations requiring a global scope may be readily combined it with the present invention. 
         [0074]    In order to improve the scalability of the linear programming of process block  96  of  FIG. 8 , the linear programming problem may be constrained by only considering redundancy between two different destinations for any given packet and by combining redundant content in packets for a single set of destinations into a larger virtual packet that is processed in lieu of the individual packets. 
         [0075]    Referring now to  FIG. 11 , it will be understood that the present invention may be readily expanded from given networks  10   a  and  10   b , for example representing local or campuswide networks, to larger domains simply by expanding the definition of the network and thus the present invention should not be considered limited to any particular domain or network size. 
         [0076]    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.