TOPOLOGY-BASED CONSOLIDATION OF LINK STATE INFORMATION

• US 20120300669A1
• Filed: 05/24/2011
• Published: 11/29/2012
• Est. Priority Date: 05/24/2011
• Status: Active Grant

• Current Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Original Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Inventors: Zahavi, Eitan
• Granted Patent: US 9,225,628 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/111 Switch interfaces, e.g. port details
• CPC Class Codes: H04L 49/112 Switch control, e.g. arbitration
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method in a network element that forwards packets to destination nodes includes identifying groups of the destination nodes. Respective performance metrics of multiple different candidate network paths, over which the destination nodes in a given group are reachable from the network element, are estimated jointly for all the destination nodes in the given group. A network path is selected from among the candidate network paths based on the estimated performance metrics. The packets addressed to the destination nodes in the given group are forwarded over the selected network path.

Claims

1. A method, comprising:

in a network element that forwards packets to destination nodes, identifying groups of the destination nodes;

estimating, jointly for all the destination nodes in a given group, respective performance metrics of multiple, different candidate network paths over which the destination nodes in the given group are reachable from the network element;

selecting a network path from among the candidate network paths based on the estimated performance metrics; and

forwarding the packets addressed to the destination nodes in the given group over the selected network path.

2. The method according to claim 1, wherein identifying the groups comprises defining each group to contain a respective subset of the destination nodes that are reachable from the network element over a common network path.

3. The method according to claim 1, wherein estimating the performance metrics comprises storing the estimated performance metrics in a data structure having a single respective entry holding the estimated performance metrics for each group.

4. The method according to claim 1, wherein the candidate network paths traverse respective different output ports of the network element, and wherein selecting the network path comprises selecting one of the output ports for forwarding the packets addressed to the destination nodes in the given group.

5. The method according to claim 1, wherein estimating the performance metrics comprises estimating respective communication loads of the candidate network paths.

6. The method according to claim 5, wherein selecting the network path comprises choosing the network path having the lowest communication load.

7. The method according to claim 1, wherein estimating the performance metrics comprises estimating respective latencies of the candidate network paths.

8. The method according to claim 7, wherein selecting the network path comprises choosing the network path having the lowest latency.

9. The method according to claim 1, wherein the network element comprises a network switch that is connected to multiple other network switches in a Fat-Tree configuration.

10. The method according to claim 1, wherein the network element comprises a network switch that is connected to multiple other network switches in a Dragonfly configuration.

11. A network element, comprising:

multiple ports for forwarding packets to destination nodes; and

circuitry, which is configured to accept an identification of groups of the destination nodes, to estimate, jointly for all the destination nodes in a given group, respective performance metrics of multiple, different candidate network paths over which the destination nodes in the given group are reachable from the network element, to select a network path from among the candidate network paths based on the estimated performance metrics, and to forward the packets addressed to the destination nodes in the given group over the selected network path.

12. The network element according to claim 11, wherein each group contains a respective subset of the destination nodes that are reachable from the network element over a common network path.

13. The network element according to claim 11, and comprising a memory, wherein the circuitry is configured to store the estimated performance metrics in the memory in a data structure having a single respective entry holding the estimated performance metrics for each group.

14. The network element according to claim 11, wherein the candidate network paths traverse respective different ones of the ports, and wherein the circuitry is configured to select the network path by selecting one of the output ports for forwarding the packets addressed to the destination nodes in the given group.

15. The network element according to claim 11, wherein the circuitry is configured to estimate the performance metrics by estimating respective communication loads on the candidate network paths.

16. The network element according to claim 15, wherein the circuitry is configured to select the network path by choosing the network path having the lowest communication load.

17. The network element according to claim 11, wherein the circuitry is configured to estimate the performance metrics by estimating respective latencies on the candidate network paths.

18. The network element according to claim 17, wherein the circuitry is configured to select the network path by choosing the network path having the lowest latency.

19. The network element according to claim 11, wherein the network element comprises a network switch that is connected to multiple other network switches in a Fat-Tree configuration.

20. The network element according to claim 11, wherein the network element comprises a network switch that is connected to multiple other network switches in a Dragonfly configuration.

21. A computer software product for use in a network element that forwards packets to destination nodes under control of a processor, the product comprising a tangible non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by the processor, cause the processor to accept an identification of groups of the destination nodes, to estimate, jointly for all the destination nodes in a given group, respective performance metrics of multiple, different candidate network paths over which the destination nodes in the given group are reachable from the network element, to select a network path from among the candidate network paths based on the estimated performance metrics, and to forward the packets addressed to the destination nodes in the given group over the selected network path.