Distributing information across equal-cost paths in a network

• US 20040264380A1
• Filed: 04/16/2004
• Published: 12/30/2004
• Est. Priority Date: 06/27/2003
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Kalkunte, Mohan, Sampath, Srinivas, Kishore, Karagada Ramarao
• Granted Patent: US 7,606,161 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• 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 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/243 using M+N parallel active paths

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.

Claims

1. A method of distributing data across a network, the method comprising the steps of:

providing a distribution device configured to distribute packets of data across a set of equal-cost paths in the network; and

distributing the packets across the paths based on at least one attribute of each of the packets.

2. The method of claim 1, wherein the distributing step comprises distributing the packets based on source addresses.

3. The method of claim 1, wherein the distributing step comprises distributing the packets based on next-hop addresses.

4. The method of claim 1, wherein the distributing step comprises performing a hashing function on the attribute.

5. A method of distributing data across a network, the method comprising the steps of:

providing a distribution device configured to distribute a set of packets of data 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.

6. The method of claim 5, wherein the distributing step further comprises using a packet attribute from each packet to perform the weighted distribution.

7. The method of claim 6, wherein the distributing step comprises performing a hashing function on the packet attribute.

8. The method of claim 5, wherein the distributing step 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.

9. The method of claim 8, wherein the distributing step 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.

10. The method of claim 9, wherein the distributing step comprises:

performing a hashing function on an attribute of the first packet to obtain a hashed result;

dividing the hashed result by the first value, thereby obtaining a remainder value, and using the remainder value to obtain an offset;

adding the offset to the first pointer to select the second set of instructions, wherein the second set of instructions includes a pointer to a third set of instructions in a third compilation of sets of instructions.

11. The method of claim 10, wherein the distributing step further comprises forwarding the first packet to a port designated in the third set of instructions.

12. The method of claim 5, further comprising updating a compilation of sets of instructions used to perform the weighted distribution, wherein the compilation is updated based on a best-fit algorithm.

13. A distribution device, the device comprising:

a set of ports; and

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 a first port among the set of ports to a second port among the set of ports, the device logic comprising;

a first lookup unit including an acknowledgement unit for acknowledging whether multiple equal-cost paths exist, a first referencing unit for referencing a second lookup unit when multiple equal-cost paths do exist, and a second referencing unit for referencing a third lookup unit otherwise,

the second lookup unit including a second distribution unit for distributing 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 for selecting the second port.

14. The device of claim 13, wherein, in the second lookup unit, multiple entries, each referencing a common set of instructions in the third lookup unit, are included.

15. The device of claim 14, wherein, in the second lookup unit, a different number of entries resulting in the packet being distributed to the first path than to a second path are included.

16. A device for distributing Internet protocol packets across a network, the device comprising:

a set of interface means for interfacing the device with the network; and

distribution means for distributing a set of packets entering the device through a first interface means in 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.

17. The device of claim 16, wherein the distribution means is configured to distribute the packets based on attributes of the packets.