HIGH-PERFORMANCE ADAPTIVE ROUTING

• US 20110096668A1
• Filed: 10/25/2010
• Published: 04/28/2011
• Est. Priority Date: 10/26/2009
• Status: Active Grant

• Current Assignee: Mellanox Technologies TLV Ltd. (NVIDIA Corporation)
• Original Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Inventors: MARELLI, Amiad, KAGAN, Michael, WEBMAN, Alon, CRUPNICOFF, Diego, BLOCH, Gil, RABENSTEIN, Itamar, BUKSPAN, Ido
• Granted Patent: US 8,576,715 B2
• Time in Patent Office: Days
• US Class Current: 370/237
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 45/38 Flow based routing

Abstract

A method for communication includes routing a first packet, which belongs to a given packet flow, over a first routing path through a communication network. A second packet, which follows the first packet in the given packet flow, is routed using a time-bounded Adaptive Routing (AR) mode, by evaluating a time gap between the first and second packets, routing the second packet over the first routing path if the time gap does not exceed a predefined threshold, and, if the time gap exceeds the predefined threshold, selecting a second routing path through the communication network that is potentially different from the first routing path, and routing the second packet over the second routing path.

Claims

1. A method for communication, comprising:

routing a first packet, which belongs to a given packet flow, over a first routing path through a communication network; and

routing a second packet, which follows the first packet in the given packet flow, using a time-bounded Adaptive Routing (AR) mode, by;

evaluating a time gap between the first and second packets;

routing the second packet over the first routing path if the time gap does not exceed a predefined threshold; and

if the time gap exceeds the predefined threshold, selecting a second routing path through the communication network that is potentially different from the first routing path, and routing the second packet over the second routing path.

2. The method according to claim 1, wherein routing the second packet comprises selecting a routing mode for routing the second packet from a set of routing modes comprising at least:

the time-bounded AR mode;

a static routing mode in which routing the second packet comprises routing the second packet unconditionally over the first routing path; and

an un-bounded AR mode in which routing the second packet comprises selecting the second routing path that is potentially different from the first routing path irrespective of the time gap, and routing the second packet over the second routing path.

3. The method according to claim 2, wherein selecting the routing mode comprises choosing the routing mode responsively to one or more attributes of the second packet.

4. The method according to claim 2, wherein selecting the routing mode comprises choosing the routing mode responsively to one or more attributes of the given packet flow.

5. The method according to claim 2, wherein selecting the routing mode comprises classifying the second packet to a packet class selected from two or more packet classes, classifying the given flow to a flow class selected from two or more flow classes, and choosing the routing mode depending on both the packet class and the flow class.

6. The method according to claim 2, and comprising routing the second packet using the selected routing mode.

7. The method according to claim 1, and comprising setting the predefined threshold based on an expected propagation delay of the first and second packets in the communication network.

8. The method according to claim 1, and comprising assessing a severity of packet re-ordering, and setting the predefined threshold based on the assessed severity of the packet re-ordering.

9. The method according to claim 1, wherein routing the second packet comprises sending the second packet to one of multiple ports of a network element, and wherein selecting the second routing path comprises assigning the ports respective grades that are indicative of traffic load levels of the ports, and choosing the one of the multiple ports based on the grades.

10. The method according to claim 1, wherein routing the second packet comprises occasionally permitting setting of the second routing path to be different from the first routing path irrespective of the time gap.

11. The method according to claim 10, wherein time gaps between successive packets in the given packet flow do not exceed the predefined threshold, and wherein permitting the setting of the second routing path comprises occasionally enabling the time-bounded AR mode for the given packet flow regardless of the time gaps.

12. The method according to claim 1, wherein routing the second packet comprises occasionally stalling the given flow in order to cause the time gap to exceed the predefined threshold.

13. A communication apparatus, comprising:

multiple ports for exchanging packets with a communication network;

a switch fabric, which is configured to forward the data packets between the ports so as to cause the packets to traverse routing paths through the communication network; and

a control unit, which is configured to cause the switch fabric to route a first packet belonging to a given packet flow over a first routing path, and to route a second packet that follows the first packet in the given packet flow, using a time-bounded Adaptive Routing (AR) mode, by evaluating a time gap between the first and second packets, routing the second packet over the first routing path if the time gap does not exceed a predefined threshold and, if the time gap exceeds the predefined threshold, selecting a second routing path that is potentially different from the first routing path, and routing the second packet over the second routing path.

14. The apparatus according to claim 13, wherein the control unit is configured to select a routing mode for routing the second packet from a set of routing modes comprising at least:

the time-bounded AR mode;

a static routing mode in which routing the second packet comprises routing the second packet unconditionally over the first routing path; and

an un-bounded AR mode in which routing the second packet comprises selecting the second routing path that is potentially different from the first routing path irrespective of the time gap, and routing the second packet over the second routing path.

15. The apparatus according to claim 14, wherein the control unit is configured to select the routing mode responsively to one or more attributes of the second packet.

16. The apparatus according to claim 14, wherein the control unit is configured to select the routing mode responsively to one or more attributes of the given packet flow.

17. The apparatus according to claim 14, wherein the control unit is configured to classify the second packet to a packet class selected from two or more packet classes, to classify the given flow to a flow class selected from two or more flow classes, and to select the routing mode depending on both the packet class and the flow class.

18. The apparatus according to claim 14, wherein the control unit is configured to route the second packet using the selected routing mode.

19. The apparatus according to claim 13, wherein the predefined threshold is set based on an expected propagation delay of the first and second packets in the communication network.

20. The apparatus according to claim 13, wherein the control unit is configured to assess a severity of packet re-ordering, and to set the predefined threshold based on the assessed severity of the packet re-ordering.

21. The apparatus according to claim 13, wherein the control unit is configured to route the second packet by sending the second packet to one of the multiple ports, and to select the second routing path by assigning the ports respective grades that are indicative of traffic load levels of the ports, and choosing the one of the multiple ports based on the grades.

22. The apparatus according to claim 13, wherein the control unit is configured to occasionally permit setting of the second routing path to be different from the first routing path irrespective of the time gap.

23. The apparatus according to claim 22, wherein time gaps between successive packets in the given packet flow do not exceed the predefined threshold, and wherein the control unit is configured to occasionally enable the time-bounded AR mode for the given packet flow regardless of the time gaps by permitting the setting of the second routing path.

24. The apparatus according to claim 13, wherein the control unit is configured to occasionally stall the given flow in order to cause the time gap to exceed the predefined threshold.