Adaptive routing for asymmetrical topologies

Patent metadata

Field	Value
Publication number	US-12470486-B2
Application number	US-202217835696-A
Country	US
Kind code	B2
Filing date	Jun 8, 2022
Priority date	Jun 8, 2022
Publication date	Nov 11, 2025
Grant date	Nov 11, 2025

Abstract

An apparatus, system, and method include, for each of two or more switches of a communication network, identifying a set of routing paths from the switch to a destination node based on a topology associated with the communication network. The set of routing paths include a first subset of routing paths and a second subset of routing paths. The topology includes an indication of a convergence of the first subset of routing paths at a node between the switch and the destination node. The apparatus, system, and method include allocating a data flow to a first routing path of the first subset of routing paths and a second routing path of the second subset of routing paths according to a target data flow rate common to the first routing path and the second routing path.

First claim

What is claimed is:

1 . An apparatus comprising:
a processor; memory in electronic communication with the processor; and instructions stored in the memory, the instructions being executable by the processor to, for each of two or more switches of a communication network:
identify a set of routing paths from a switch in the two or more switches to a destination node based on a topology associated with the communication network, wherein the set of routing paths comprise a first subset of routing paths and a second subset of routing paths, and the topology comprises an indication that the first subset of routing paths converge at an intermediate node between the switch and the destination node;
select a first routing path of the first subset of routing paths and a second routing path of the second subset of routing paths such that, for a data flow to the destination node flowing from the switch through the intermediate node, the first and second routing paths do not converge at the intermediate node;
set a target data flow rate for the data flow to be the same for the first routing path and the second routing path; and
allocate the data flow to the first routing path and the second routing path at the target data flow rate.

2 . The apparatus of claim 1 , wherein the instructions are further executable by the processor to:
compare an instantaneous data flow rate of one or more routing paths of the set of routing paths to the target data flow rate, wherein allocating the data flow to the first routing path and the second routing path is based on a result of the comparison.

3 . The apparatus of claim 1 , wherein the instructions are further executable by the processor to:
identify, based on the topology, the convergence of the first subset of routing paths.

4 . The apparatus of claim 1 , wherein the instructions are further executable by the processor to:
select the first routing path from at least one other routing path of the first subset of routing paths based on the destination node.

5 . The apparatus of claim 4 , wherein the instructions are further executable by the processor to:
disable a port associated with the at least one other routing path.

6 . The apparatus of claim 5 , wherein the instructions are further executable by the processor to:
compare a congestion state of the communication network to a set of criteria, wherein allocating the data flow to the first routing path, disabling the port associated with the at least one other routing path, or both is based on a result of the comparison.

7 . The apparatus of claim 1 , wherein the instructions are further executable by the processor to:
compare a data throughput value of at least one other routing path of the second subset of routing paths to a threshold value; and allocate the data flow to the at least one other routing path at the target data flow rate or refrain from allocating the data flow to the at least one other routing path, based on a result of the comparison.

8 . The apparatus of claim 1 , wherein the instructions are further executable by the processor to:
compare an input flow rate at the intermediate node to an output flow rate capability at the intermediate node, wherein allocating the data flow to the first routing path and the second routing path at the target data flow rate is based on a result of the comparison.

9 . The apparatus of claim 1 , wherein the instructions are further executable by the processor to:
offload data traffic from at least one other routing path of the first subset of routing paths to the first routing path.

10 . The apparatus of claim 1 , wherein the instructions are further executable by the processor to:
compare an input flow rate at the destination node to a maximum line rate associated with the topology, wherein allocating the data flow to the first routing path and the second routing path at the target data flow rate is based on a result of the comparison.

11 . The apparatus of claim 1 , wherein the instructions are further executable by the processor to:
identify the topology based on traversing the communication network.

12 . The apparatus of claim 1 , wherein:
identifying the topology comprises accessing a data table indicating the topology.

13 . A system comprising:
a communication network comprising a controller and two or more switches, wherein:
the communication network comprises, for each of the two or more switches, a set of routing paths a destination node;
the set of routing paths comprise:
a first subset of routing paths that converge at an intermediate node between a switch of the two or more switches and the destination node; and
a second subset of routing paths; and

the controller is to:
select a first routing path of the first subset of routing paths and a second routing path of the second subset of routing paths such that, for a data flow to the destination node flowing from the switch through the intermediate node, the first and second routing paths do not converge at the intermediate node;
set a target data flow rate for the data flow to be the same for the first routing path and the second routing path; and
allocate the data flow to the first routing path of and the second routing path at the target data flow rate.

14 . The system of claim 13 , wherein the controller:
compares an instantaneous data flow rate of one or more routing paths of the set of routing paths to the target data flow rate, wherein allocating the data flow to the first routing path and the second routing path is based on a result of the comparison.

15 . The system of claim 13 , wherein:
the controller identifies, based on a topology associated with the communication network, the convergence of the first subset of routing paths.

16 . The system of claim 13 , wherein:
the controller selects the first routing path from at least one other routing path of the first subset of routing paths based on the destination node.

17 . The system of claim 16 , wherein the controller:
disables a port associated with the at least one other routing path.

18 . The system of claim 17 , wherein the controller:
compares an input flow rate at the intermediate node to an output flow rate capability at the intermediate node, wherein allocating the data flow to the first routing path and the second routing path at the target data flow rate is based on a result of the comparison.

19 . The system of claim 13 , wherein the controller:
compares an input flow rate at the destination node to a maximum line rate of a topology associated with the communication network, wherein allocating the data flow to the first routing path and the second routing path at the target data flow rate is based on a result of the comparison.

20 . A method comprising:
identifying a set of routing paths from a switch to a destination node based on a topology associated with a communication network, wherein the set of routing paths comprise a first subset of routing paths and a second subset of routing paths, and the topology comprises an indication that the first subset of routing paths converge at an intermediate node between the switch and the destination node; selecting a first routing path of the first subset of routing paths and a second routing path of the second subset of routing paths such that, for a data flow to the destination node flowing from the switch through the intermediate node, the first and second routing paths do not converge at the intermedi

Assignees

• Mellanox Technologies Ltd

Inventors

• Milgrom Michael Gandelman
• Klein Daniel
• Zahavi Eitan
• Koushnir Vladimir
• Levi Lion
• Mey-Tal Gil
• Minchiu Aleksandr

Classifications

• H04L45/02

  Topology update or discovery · CPC title

• H04L45/22

  Alternate routing · CPC title

• H04L45/125

  based on throughput or bandwidth · CPC title

• H04L47/122 Primary

  by diverting traffic away from congested entities · CPC title