Systems and methods for network routing
View Patent ↗A network may include a plurality of nodes forming a first layer and a sub-set of the plurality of nodes forming a second layer. The first layer may follow a first routing objective in routing traffic, and the second layer may develop constraints based on the first routing objective and follow a second routing objective within the developed constraints in routing traffic. In another network, the second layer may follow a second routing objective in routing traffic, and the first layer may develop constraints based on the second routing objective and follow a first routing objective within the developed constraints in routing traffic.
1. A method for routing a data packet, the method comprising:
determine, by a switching node, if a first network or a second network is a leader, the first network including a first plurality of switching nodes following a first routing objective, the second network including a second plurality of switching nodes, the second plurality of switching nodes being a sub-set of the first plurality of switching nodes, the second plurality of switching nodes following a second routing objective, at least one of the first network and the second network is an overlay network; and
if the first network is the leader,
determining, by the switching node, constraints based on the second routing objective, and
routing, by the switching node, the data packet based on the first routing objective and the determined constraints of the second routing objective;
if the second network is the leader,
determining, by the switching node, constraints based on the first routing objective, and
routing, by the switching node, the data packet based on the second routing objective and the determined constraints of the first routing objective.
2. The method of claim 1 , wherein
the first plurality of switching nodes follow the first routing objective within the determined constraints in routing traffic without exchanging information with the second plurality of switching nodes, and
the second plurality of switching nodes follow the second routing objective in routing traffic without exchanging information with the first plurality of switching nodes.
3. The method of claim 1 , wherein the switching node determines the constraints by proactively considering a reaction of the second plurality of switching nodes following the second routing objective in routing traffic to traffic routing at the first plurality of switching nodes.
4. The method of claim 3 , wherein
the first routing objective is to at least one of balance load in one of the first network and the second network and minimize an overall cost of one of the first network and the second network,
the second routing objective is to minimize end-to-end latency of traffic paths in the second plurality of switching nodes, and
the first plurality of switching nodes follow the first routing objective within the determined constraints in routing traffic by balancing load in the first plurality of switching nodes while maintaining traffic paths in the first plurality of switching nodes at a same length such that latencies of links in the second plurality of switching nodes are not changed.
5. The method of claim 4 , wherein the switching node balances load in the first plurality of switching nodes while maintaining the traffic paths in the first plurality of switching nodes at the same length such that the latencies of the links in the second plurality of switching nodes are not changed in accordance with the following equation:
min
Maximum
util
=
max
(
x
,
y
)
∈
E
load
(
x
,
y
)
capacity
(
x
,
y
)
subject
to
:
∑
(
x
,
y
)
∈
E
f
(
x
,
y
)
(
s
,
t
)
-
∑
(
y
,
z
)
∈
E
f
(
y
,
z
)
(
s
,
t
)
=
{
-
1
,
if
y
=
s
1
,
if
y
=
t
0
,
otherwise
∀
y
,
s
,
t
∈
E
load
(
x
,
y
)
=
∑
(
s
,
t
)
∈
V
×
V
demand
(
s
,
t
)
×
f
(
x
,
y
)
(
s
,
t
)
∀
(
x
,
y
)
∈
E
∑
(
x
,
y
)
∈
E
f
(
x
,
y
)
(
s
,
t
)
≤
1.02
×
H
(
s
,
t
)
prev
∀
(
s
,
t
)
∈
V
×
V
wherein f (x,y) (s,t) is an amount of traffic between nodes s and t in the first plurality of switching nodes that goes over a link (x,y) between nodes x and y in the first plurality of switching nodes, load(x,y) is the load on the link (x,y), capacity(x,y) is the traffic capacity of link (x,y), demand(s,t) is a traffic demand between nodes s and t, H(s,t) is the total hopcount between nodes s and t in the first plurality of switching nodes computed as Σ (x,y)εE f (x,y) (s,t) , H(s,t) prev is the hopcount of a traffic path between nodes s and t in the first plurality of switching nodes computed in a previous iteration of load balancing, V is the set of nodes in the first plurality of switching nodes including nodes s, t, x, and y, and z, and E is the set of links in the first plurality of switching nodes including the links (x,y) and (y,z).
6. The method of claim 3 , wherein
the first routing objective is to at least one of balance load in one of the first network and the second network and minimize an overall cost of one of the first network and the second network,
the second routing objective is to minimize end-to-end latency of traffic paths in the second plurality of switching nodes,
the first plurality of switching nodes follows the first routing objective within the determined constraints in routing traffic by balancing load in the first plurality of switching nodes while artificially increasing latency on links in the first plurality of switching nodes such that the second plurality of switching nodes does not use the links having the artificially increased latency in routing traffic in the second plurality of switching nodes, and the method further comprises,
artificially increasing, by the switching node, the latency on the links in the first plurality of switching nodes by,
(a) increasing latency on a link by a first amount if the load put on the link is greater than or equal to a capacity of the link,
(b) increasing the latency on the link by a second amount if the link has a utilization that is higher than the maximum link utilization observed after a current round of routing traffic according to the first routing objective within the developed constraints by the first plurality of switching nodes, and
(c) repeating steps (a) and (b) until the maximum link utilization in one of the first network and the second network is reduced to a utilization threshold.
7. A switching node for routing a data packet, the node comprising:
a processor configured to,
receive the data packet,
determine if a first network or a second network is a leader, the first network including a first plurality of switching nodes following a first routing objective, the second network including a second plurality of switching nodes, the second plurality of switching nodes being a sub-set of the first plurality of switching nodes, the second plurality of switching nodes following a second routing objective, at least one of the first network and the second network being an overlay network; and
if the first network is the leader,
determine constraints based on the second routing objective, and
route the data packet based on the first routing objective and the determined constraints of the second routing objective;
if the second network is the leader,
determining, by the switching node, constraints based on the first routing objective, and
routing, by the switching node, the data packet based on the second routing objective and the determined constraints of the first routing objective.
8. The switching node of claim 7 , wherein
the first plurality of switching nodes follow the first routing objective within the determined constraints in routing traffic without exchanging information with the second plurality of switching nodes, and
the second plurality of switching nodes follow the second routing objective in routing traffic without exchanging information with the first plurality of switching nodes.
9. The switching node of claim 7 , wherein the processor determines the constraints by proactively considering a reaction of the second plurality of switching nodes following the second routing objective in routing traffic to traffic routing at the first plurality of switching nodes.
10. The switching node of claim 9 , wherein
the first routing objective is to at least one of balance load in one of the first network and the second network and minimize an overall cost of one of the first network and the second network,
the second routing objective is to minimize end-to-end latency of traffic paths in the second plurality of switching nodes, and
the first plurality of switching nodes follow the first routing objective within the determined constraints in routing traffic by balancing load in the first plurality of switching nodes while maintaining traffic paths in the first plurality of switching nodes at a same length such that latencies of links in the second plurality of switching nodes are not changed.
11. The switching node of claim 10 , wherein the processor balances load in the first plurality of switching nodes while maintaining the traffic paths in the first plurality of switching nodes at the same length such that the latencies of the links in the second plurality of switching nodes are not changed in accordance with the following equation:
min
Maximum
util
=
max
(
x
,
y
)
∈
E
load
(
x
,
y
)
capacity
(
x
,
y
)
subject
to
:
∑
(
x
,
y
)
∈
E
f
(
x
,
y
)
(
s
,
t
)
-
∑
(
y
,
z
)
∈
E
f
(
y
,
z
)
(
s
,
t
)
=
{
-
1
,
if
y
=
s
1
,
if
y
=
t
0
,
otherwise
∀
y
,
s
,
t
∈
E
load
(
x
,
y
)
=
∑
(
s
,
t
)
∈
V
×
V
demand
(
s
,
t
)
×
f
(
x
,
y
)
(
s
,
t
)
∀
(
x
,
y
)
∈
E
∑
(
x
,
y
)
∈
E
f
(
x
,
y
)
(
s
,
t
)
≤
1.02
×
H
(
s
,
t
)
prev
∀
(
s
,
t
)
∈
V
×
V
wherein f (x,y) (s,t) is an amount of traffic between nodes s and t in the first plurality of switching nodes that goes over a link (x,y) between nodes x and y in the first plurality of switching nodes, load(x,y) is the load on the link (x,y), capacity(x,y) is the traffic capacity of link (x,y), demand(s,t) is a traffic demand between nodes s and t, H(s,t) is the total hopcount between nodes s and t in the first plurality of switching nodes computed as Σ (x,y)εE f (x,y) (s,t) , H(s,t) prev is the hopcount of a traffic path between nodes s and t in the first plurality of switching nodes computed in a previous iteration of load balancing, V is the set of nodes in the first plurality of switching nodes including nodes s, t, x, and y, and z, and E is the set of links in the first plurality of switching nodes including the links (x,y) and (y,z).
12. The switching node of claim 9 , wherein
the first routing objective is to at least one of balance load in one of the first network and the second network and minimize an overall cost of one of the first network and the second network,
the second routing objective is to minimize end-to-end latency of traffic paths in the second plurality of switching nodes,
the first plurality of switching nodes follows the first routing objective within the determined constraints in routing traffic by balancing load in the first plurality of switching nodes while artificially increasing latency on links in the first plurality of switching nodes such that the second plurality of switching nodes does not use the links having the artificially increased latency in routing traffic in the second plurality of switching nodes, and
the processor artificially increases the latency on the links in the first plurality of switching nodes by,
(a) increasing latency on a link by a first amount if the load put on the link is greater than or equal to a capacity of the link,
(b) increasing the latency on the link by a second amount if the link has a utilization that is higher than the maximum link utilization observed after a current round of routing traffic according to the first routing objective within the developed constraints by the first plurality of switching nodes, and
(c) repeating steps (a) and (b) until the maximum link utilization in one of the first network and the second network is reduced to a utilization threshold.