Fault-tolerant routing algorithm for toroidal network topologies
Generally disclosed herein is an approach for optimizing routing strategy to tolerate faults in a toroidal network topology including, but not limited to, N-dimensional mesh, torus, and twisted torus. The approach may include balancing a load for a specified input traffic pattern operating offline or online. The approach may also include an optimization enhancement technique specifically applicable to symmetric, dynamically composable toroidal networks based on a set of centrally connected circuit switches.
1. Method for optimizing routing for a network, the method comprising:
(i) taking, by one or more processors, a first hop arbitrarily from a source node to a current node along any direction, the first hop establishing a candidate route;
(ii) taking, by the one or more processors, a subsequent hop across a link from the current node to an additional node following a dimension order;
(iii) assigning, by the one or more processors, the additional node as the current node and repeating steps (ii)-(iii) until the current node is a destination node; and
(iv) taking, by the one or more processors, a new first hop from the source node along a new direction to establish a new candidate route and repeating steps (ii)-(iv) until candidate routes are established for all directions from the source node,
further comprising load-balancing each link within the network using integer linear programming, and further comprising:
determining the load balance of each link using the following formula:
γ
C
=
∑
p
∈
c
x
p
wherein, γ C is the load on each link c, p is a candidate route, and x is a Boolean variable that determines whether the candidate route passing the link c is selected by the integer linear programming.
2. The method of claim 1 , further comprising:
minimizing a maximum load across all channels using the following optimization formula:
Minimize L,s·t
γ C ≤L dim(c) ,∀c
L d ≤L,∀d
wherein L is the maximum load across all dimensions, L dim(c) is a maximum load across all link c on a dimension, and L d is a maximum load on dimension d.
3. The method of claim 2 , further comprising:
reducing a number of the channels by taking a multiplier between a fault pattern and a traffic pattern of the network.
4. A routing system of optimizing routing for a network comprises:
a network fabric;
a plurality of circuit switches; and
a plurality of compute nodes, each compute node comprising one or more processors and memory storing instructions that, when performed by the one or more processors, causes the one or more processors to perform operations, the operations comprising:
(i) taking a first hop arbitrarily from either a source node to a current node along any direction, the first hop establishing a candidate route;
(ii) taking a subsequent hop across a link from the current node to an additional node following a dimension order;
(iii) assigning the additional node as the current node and repeating steps (ii)-(iii) until the current node is the destination node; and
(iv) taking a new first hop from the source node along a new direction to establish a new candidate route and repeating steps (ii)-(iv) until candidate routes are established for all directions from the source node,
wherein the operation further comprises load-balancing each link within the network using integer linear programming, and wherein the operation further comprises:
determining the load balance of each link using the following formula:
γ
C
=
∑
p
∈
c
x
p
wherein, γ C is the load on each link c, p is a candidate route, and x is a Boolean variable that determines whether the candidate route passing the link c is selected by the integer linear programming.
5. The system of claim 4 , wherein the operation further comprises: minimizing a maximum load across all channels using the following optimization formula:
Minimize L,s·t
γ C ≤L dim(c) ,∀c
L d ≤L,∀d
wherein L is the maximum load across all dimensions, L dim(c) is a maximum load across all link c on a dimension, and L d is a maximum load on dimension d.
6. The system of claim 5 , wherein the operation further comprises:
reducing a number of the channels by taking a multiplier between a fault pattern and a traffic pattern of the network.