Method and apparatus for distributing packets across multiple paths leading to a destination

• US 6,826,186 B1
• Filed: 03/07/2000
• Issued: 11/30/2004
• Est. Priority Date: 03/07/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Fingerhut, John Andrew, Lenoski, Daniel E., Dittia, Zubin D.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): ODLAND, DAVID E
• Application Number:
  US09/519,715
• Time in Patent Office: 1,729 Days
• Field of Search: 370/351, 370/369, 370/370, 370/372, 370/389, 370/392, 370/394, 370/395.1, 370/396, 370/397, 370/395--39, 370/395--39, 370/395.7, 370/400, 370/412, 370/417, 370/464-468
• US Class Current: 370/395.31
• 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/24 Multipath
• CPC Class Codes: H04L 45/243 using M+N parallel active paths

Abstract

According to the invention, methods and apparatus are disclosed for selecting one of multiple of paths between two points over which to route a data item based on the destination of the data item and the traffic between the two points over the multiple paths. A switching system can use the disclosed methods and apparatus to more efficiently distribute data packets among switching fabrics than currently accomplished by known techniques. In one implementation, distribution cycles have been established for sending data between two points, where each path between the endpoints is used a predetermined number of times (e.g., one, two) within each cycle. To economize the amount of traffic data collected, the multiple paths can be partitioned into subsets for which traffic data is maintained only for the current subset. Additionally, the distribution of traffic between the two points can be further partitioned into traffic of a particular type or priority between the two points.

Claims

1. An apparatus for switching packets comprising:

a plurality of distributors, each including a plurality of input ports;

a plurality of receivers, each including a plurality of output ports; and

a plurality of interconnection elements, each coupled to each of the plurality of distributors and each of the plurality of receivers, forming a plurality of paths between each of the plurality of distributors and each of the plurality of receivers;

wherein each of the plurality of input ports maintains one or more data structures indicating which of the plurality of interconnection elements remain available to be selected in a current distribution cycle for each of the plurality of output ports, with a different distribution cycle defined for each input port-output port pair, and each of the plurality of input ports sends exactly a predetermined number of packets across each of the plurality of interconnection elements in a distribution cycle.

2. The apparatus of claim 1, wherein each of the plurality of input ports selects a distinct one of the plurality of interconnection elements indicated as available to send a packet in the current distribution cycle corresponding to the output port to which a particular packet is to be sent, said selection based on a traffic pattern within the apparatus.

3. The apparatus of claim 1, wherein each of the plurality of input ports selects a distinct one of the plurality of interconnection elements indicated as available to send a packet in the current distribution cycle corresponding to the output port to which a particular packet is to be sent, said selection based on congestion within the apparatus.

4. The apparatus of claim 1, wherein at least one of the interconnection elements includes an interconnection network.

5. The apparatus of claim 1, wherein the predetermined number of times is one.

6. The apparatus of claim 1, comprising buffers to buffer at least a portion of the packets to be sent from the plurality of distributors across the plurality of interconnection elements to the plurality of receivers, wherein each of the plurality of input ports selects which of the plurality of interconnection elements indicated as available to next send a packet in the current distribution cycle corresponding to the output port to which a particular packet is to be sent, said selection based on queuing lengths of said interconnection elements indicated as available in the current distribution cycle.

7. The apparatus of claim 1, wherein a different distribution cycle is defined for each combination of said input port-output port pair and a type, priority, or type and priority of service.

8. The apparatus of claim 6, wherein the predetermined number of times is at least two.

9. A packet switching system comprising:

a distributor;

a plurality of receivers; and

a plurality of interconnection elements coupled to the distributor and to each of the plurality of receivers to form a plurality of paths between the distributor and each of the plurality of receivers;

wherein a different distribution cycle is defined for each receiver of the plurality of receivers, and the distributor is configured to send exactly a predetermined number of packets across each of the plurality of interconnection elements leading to a particular receiver of the plurality of receivers in a distribution cycle corresponding to said particular receiver; and

wherein the distributor is not predetermined to send packets in a round-robin fashion across the plurality of interconnection elements leading to said particular receiver in a distribution cycle corresponding to said particular receiver;

wherein, for a packet being sent to a specific receiver of the plurality of receivers, the distributor is configured to identify a next particular interconnection element of the plurality of interconnection elements that remain available in a current distribution cycle corresponding to the specific receiver.

10. The packet switching system of claim 9, comprising a set of buffers, the set of buffers including a buffer for each of the plurality of interconnection elements for buffering packets to be sent over a corresponding one of the plurality of interconnection elements;

and

wherein the distributor is configured to identify the next particular interconnection element based on the occupancies of buffers for said plurality of interconnection elements that remain available in the current distribution cycle corresponding to the specific receiver.

12. The packet switching system of claim 9, wherein the distribution cycle is defined for a combination of each receiver with a plurality of type, priority, or type and priority of service.

13. The packet switching system of claim 9, wherein a single packet switch includes the plurality of interconnection elements, the plurality of receivers, and the distributor.

14. The packet switching system of claim 13, wherein the packet switch includes an input interface, which includes the distributor.

15. The packet switching system of claim 13, wherein the packet switch includes a plurality of switching planes, and each of the plurality of interconnection elements corresponds to a different switching plane of the plurality of switching planes.

11. The packet switching system of clam 9, wherein the distributor includes a bitmap data structure to represent which of said plurality of interconnection elements remain available in the current distribution cycle corresponding to the specified receiver.

16. A packet switching system comprising:

a distributor;

a receiver;

a plurality of interconnection elements coupled to the distributor and the receiver and forming a plurality of paths between the distributor and the receiver, the plurality of interconnection elements partitioned into a plurality of subsets of interconnection elements, each of the plurality of subsets of interconnection elements including at least two interconnections elements not in another of subset of the plurality of subsets of interconnection elements;

wherein the distributor is configured to identify for a current subset of the plurality of subsets which of the plurality of interconnection elements in the current subset are available to be selected in a current distribution cycle for the receiver and configured to send exactly a predetermined number of packets to the receiver through each of said interconnection elements in the current subset in the current distribution cycle for the receiver; and

the packet switching system includes a selector to identify the current subset of the plurality of subsets of interconnection elements.

17. The packet switching system of claim 16, wherein a single packet switch includes the plurality of interconnection elements, the plurality of receivers, and the distributor.

18. The packet switching system of claim 17, wherein the packet switch includes an input interface, which includes the distributor.

19. The packet switching system of claim 17, wherein the packet switch includes a plurality of switching planes, and each of the plurality of interconnection elements corresponds to a different switching plane of the plurality of switching planes.

20. An apparatus for switching packets comprising:

a plurality of distributors, each including a plurality of input ports;

a plurality of receivers, each including a plurality of output ports; and

a plurality of interconnection elements, each coupled to each of the plurality of distributors and each of the plurality of receivers, forming a plurality of paths between each of the plurality of distributors and each of the plurality of receivers;

wherein the plurality of receivers are partitioned into a plurality of non-overlapping subsets with each of said non-overlapping subsets including at least two of the plurality of output ports, and wherein each of the plurality of input ports maintains one or more data structures indicating a current subset of the non-overlapping subsets and which of the plurality of interconnection elements in the current one of the non-overlapping subsets remain available to be selected in the current subset of a current distribution cycle, with a different distribution cycle defined for each input port-output port pair, and each of the plurality of input ports sends exactly a predetermined number of packets across each of the plurality of interconnection elements in a distribution cycle.

21. The apparatus of claim 20, wherein the predetermined number of times is one.

22. The apparatus of claim 20, wherein the predetermined number of times is at least two.

23. The apparatus of claim 20, wherein each of the plurality of input ports selects a distinct one of the plurality of interconnection elements indicated as available to send a packet in the current subset of the current distribution cycle corresponding to the output port to which a particular packet is to be sent, said selection based on a traffic pattern within the apparatus.

24. The apparatus of claim 20, wherein each of the plurality of input ports selects a distinct one of the plurality of interconnection elements indicated as available to send a packet in the current subset of the current distribution cycle corresponding to the output port to which a particular packet is to be sent, said selection based on congestion within the apparatus.

25. The apparatus of claim 20, wherein at least one of the interconnection elements includes an interconnection network.

26. The apparatus of claim 20, comprising buffers to buffer at least a portion of the packets to be sent from the plurality of distributors across the plurality of interconnection elements to the plurality of receivers, wherein each of the plurality of input ports selects which of the plurality of interconnection elements indicated as available to next send a packet in the current subset of the current distribution cycle corresponding to the output port to which a particular packet is to be sent, said selection based on queuing lengths of said interconnection elements indicated as available in the current subset of the current distribution cycle.

27. The apparatus of claim 20, wherein a different distribution cycle is defined for each combination of said input port-output port pair and a type, priority, or type and priority of service.