Distributing information across equal-cost paths in a network

Abstract

A method of distributing data across a network having a plurality of equal-cost paths. Also, a device for distributing data over a network according to the method. The data, which is typically contained in data packets, may be distributed based on at least one attribute of each of the packets. The data may also be distributed according to a weighted distribution function that allows for unequal amounts of traffic to be distributed to each of the equal-cost paths.

1 . A distribution device, the distribution device comprising:
 a first distribution unit, including a device logic, wherein the first distribution unit is configured to use the device logic to distribute a packet of data entering the device through an ingress port among a set of ports to one of at least a first output port and a second output port among the set of ports, the device logic configured to
 determine whether at least two equal-cost paths exist between the distribution device and a destination device, wherein a first equal-cost path is associated with the first output port and a second equal-cost path is associated with the second output port; 
 determine, based on a packet attribute of the packet, a first weight associated with the first output port and the first equal-cost path; 
 determine, based on the packet attribute of the packet, a second weight associated with the second output port and the second equal-cost path, wherein the first weight is larger than the second weight; and 
 distribute the packet based on the first weight and the second weight, including distributing the packet with a higher likelihood of output to the first output port and the first equal-cost path based on a relation of the first weight to the second weight. 
   
   
   
       2 . The distribution device of  claim 1 , wherein the device logic is configured to distribute a set of packets including the packet, including distributing a first subset of the set of packets through the first output port and a second subset of the set of packets through the second output port, wherein the first subset is lager than the second subset in proportion to which the first weight is larger than the second weight. 
   
   
       3 . The distribution device of  claim 1 , wherein each packet of the set of packets includes the packet attribute. 
   
   
       4 . The distribution device of  claim 1 , wherein the first weight and the second weight correspond, respectively, to a first number of entries stored in at least one memory and to a second number of entries stored in the at least one memory. 
   
   
       5 . The distribution device of  claim 1 , wherein the first equal cost path and the second equal cost path are associated with first network traffic and second network traffic, respectively, that are unrelated to the packet, and wherein the first network traffic is less than the second network traffic. 
   
   
       6 . The distribution device of  claim 5 , wherein the first network traffic is less than the second network traffic in approximate proportion to an extent to which the first weight is larger than the second weight. 
   
   
       7 . The distribution device of  claim 1 , wherein the device logic comprises:
 a first lookup unit including an acknowledgment unit configured to acknowledge whether multiple equal cost-paths exist, a first referencing unit configured to reference a second lookup unit when multiple equal-cost paths do exist, and a second referencing unit configured to reference a third lookup unit otherwise,   the second lookup unit including a second distribution unit configured to distribute the packet across the set of ports and a third referencing unit for referencing the third lookup unit, and   the third lookup unit including a selection unit configured to select between the first port and the second port.   
   
   
       8 . The distribution device of  claim 7  wherein the second lookup unit includes multiple entries, each referencing a common set of instructions in the third lookup unit. 
   
   
       9 . The distribution device of  claim 8  wherein, in the second lookup unit, a first number of entries associated with the first packet determines the first weight, and a second number of entries associated with the second packet determines the second weight. 
   
   
       10 . A method of distributing data across a network, comprising:
 providing a distribution device configured to distribute a set of packets across a set of equal-cost paths in the network; and   distributing each packet in the set of packets across the set of equal-cost paths according to a weighted distribution in which a weight is assigned to each packet in proportion to relative loads of the set of equal-cost paths and a packet with a relatively higher weight is more likely to be distributed to an equal-cost path of the set of equal-cost paths having a relatively smaller network traffic load.   
   
   
       11 . The method of  claim 10  wherein the weight of each packet corresponds to a number of entries in a memory. 
   
   
       12 . The method of  claim 10  wherein the distributing further comprises using a packet attribute from each packet to determine the weighted distribution. 
   
   
       13 . The method of  claim 12  wherein the distributing comprises performing a hashing function on the packet attribute. 
   
   
       14 . The method of  claim 13  wherein the packet attribute includes one or more of a source address, a next-hop address, or a destination address. 
   
   
       15 . The method of  claim 10 , wherein the distributing comprises obtaining a match between a longest prefix in a first packet and a portion of a first set of instructions in a first compilation of sets of instructions. 
   
   
       16 . The method of  claim 15 , wherein the distributing comprises using a pointer portion from the first set of instructions to select a second set of instructions from a second compilation of sets of instructions, wherein the first set of instructions includes a first value that specifies how much weight is to be given to each equal-cost path in the set of equal-cost paths. 
   
   
       17 . The method of  claim 10 , further comprising updating a compilation of sets of instructions used to determine the weighted distribution, wherein the compilation is updated based on a best-fit algorithm. 
   
   
       18 . A device for distributing packets across a network, the device comprising:
 a set of interface means;   distribution means for distributing a set of packets entering the device through a first interface means of the set of interface means such that packets in the set of packets are distributed across all interface means in the set of interface means operably-connected to equal-cost paths according to a weighted distribution so that at least one of said packets is given greater weight to be distributed across at least one of said equal-cost paths than at least one other of said equal-cost paths   
   
   
       19 . The device of  claim 18  wherein said packet weight corresponds to a number of entries stored in a memory. 
   
   
       20 . The device of  claim 18  wherein the distribution means is configured to distribute the packets based on attributes of the packets.