Topology-based consolidation of link state information
View Patent ↗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.
1. A method, comprising:
in a network element that forwards packets to destination nodes, identifying a plurality of groups of the destination nodes, each group containing destination nodes that are reachable from the network element over a common set of multiple candidate network paths and respective candidate ports of the network element;
determining performance values for links of the network,
maintaining a table with a plurality of entries, the table including an entry for each given group of the destination nodes, each entry including a plurality of performance metrics, such that each entry includes a current respective performance metric for each of the candidate ports of the network element over which the destination nodes in the given group are reachable from the network element;
receiving a packet at the network element;
determining a destination node of the received packet;
determining, by the network element, a group to which the determined destination node belongs;
selecting a port from among the candidate ports based on the performance metrics for the group of the destination of the packet, in the table; and
forwarding the received packets through the selected port,
wherein the respective performance metric comprises a global load or latency value dependent on performance values of a plurality of links along a path to the destination nodes of the group, and
wherein each respective performance metric of a destination group and a candidate port of the network element is calculated from a plurality of performance values of links along a path to the destination nodes of the group through the candidate port.
2. The method according to claim 1 , wherein the table has a single respective entry holding the performance metrics for each group.
3. The method according to claim 1 , wherein the performance metrics comprise respective communication loads of the candidate network paths.
4. The method according to claim 3 , wherein selecting the port comprises choosing the network path having the lowest communication load.
5. The method according to claim 1 , wherein the performance metrics comprise respective latencies of the candidate network paths.
6. The method according to claim 5 , wherein selecting the port comprises choosing the network path having the lowest latency.
7. 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.
8. 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.
9. The method according to claim 1 , wherein the number of entries in the table corresponds to the number of groups and is substantially smaller than the number of nodes in the network.
10. The method according to claim 1 , wherein maintaining the table comprises estimating the current respective performance metrics based on information received from other network elements.
11. The method according to claim 1 , wherein the respective performance metric comprises a global load dependent on load values of a plurality of links along a path to the destination nodes of the group.
12. The method according to claim 1 , wherein the respective performance metric comprises a global latency dependent on latency values of a plurality of links along a path to the destination nodes of the group.
13. 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, each group containing destination nodes that are reachable from the network element over a common set of multiple candidate network paths through respective ones of the multiple ports, to maintain a table with a plurality of entries, the table including an entry for each given group of the destination nodes, each entry including a plurality of performance metrics, such that each entry includes a current respective performance metric for each of the candidate ports through which the destination nodes in the given group are reachable from the network element, to receive a packet, to determine a destination node of the received packet, determine a group to which the determined destination node belongs, to select a port from among the candidate ports based on the performance metrics for the group of the destination of the packet, in the table, and to forward the packets addressed to the destination nodes in the given group through the selected port,
wherein the respective performance metric comprises a global load or latency value dependent on performance values of a plurality of links along a path to the destination nodes of the group, and
wherein each respective performance metric of a destination group and a candidate port of the network element is calculated from a plurality of performance values of links along a path to the destination nodes of the group through the candidate port.
14. The network element according to claim 13 , and comprising a memory, wherein the circuitry is configured to store the table and wherein the table has a single respective entry holding the performance metrics for each group.
15. The network element according to claim 13 , 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 port by choosing the network path having the lowest communication load.
17. The network element according to claim 13 , 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 port by choosing the network path having the lowest latency.
19. The network element according to claim 13 , 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, each group containing destination nodes that are reachable from the network element over a common set of multiple candidate network paths through respective ones of the multiple ports, to maintain a table with a plurality of entries, the table including an entry for each given group of the destination nodes, each entry including a plurality of performance metrics, such that each entry includes a current respective performance metric for each of the candidate ports through which the destination nodes in the given group are reachable from the network element, to receive a packet, to determine a destination node of the received packet, determine a group to which the determined destination node belongs, to select a port from among the candidate ports based on the performance metrics for the group of the destination of the packet, in the table, and to forward the packets addressed to the destination nodes in the given group through the selected port,
wherein the respective performance metric comprises a global load or latency value dependent on performance values of a plurality of links along a path to the destination nodes of the group, and
wherein each respective performance metric of a destination group and a candidate port of the network element is calculated from a plurality of performance values of links along a path to the destination nodes of the group through the candidate port.