Systems and methods for network routing

• US 20090180480A1
• Filed: 01/15/2008
• Published: 07/16/2009
• Est. Priority Date: 01/15/2008
• Status: Active Grant

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation), Georgia Tech Research Corporation (University System of Georgia)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Seetharaman, Srinivasan, Hofmann, Markus Andreas, Hilt, Volker Friedrich
• Granted Patent: US 8,565,117 B2
• Time in Patent Office: Days
• US Class Current: 370/395.210
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/64 using an overlay routing layer

Abstract

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.

Claims

1. A network comprising:

a plurality of nodes forming a first layer, the first layer following a first routing objective in routing traffic;

a sub-set of the plurality of nodes forming a second layer, the second layer developing constraints based on the first routing objective and following a second routing objective within the developed constraints in routing traffic.

2. The network of claim 1, wherein

the first layer follows the first routing objective in routing traffic without exchanging information with the second layer, and

the second layer follows the second routing objective within the developed constraints in routing traffic without exchanging information with the first layer.

3. The network of claim 1, wherein the second layer develops the constraints by proactively considering a reaction of the first layer following the first routing objective in routing traffic to traffic routing at the second layer.

4. The network of claim 3, wherein

the first routing objective is to at least one of balance load in the network and minimize an overall cost of the network,

the second routing objective is to minimize end-to-end latency of traffic paths in the second layer, and

the second layer follows the second routing objective within the developed constraints in routing traffic by minimizing a sum of the end-to-end latency of each traffic path in the second layer while maintaining a load on each link in the second layer above a lower threshold and below an upper threshold.

5. The network of claim 4, wherein the second layer minimizes the sum of the end-to-end latency of each traffic path in the second layer while maintaining the load on each link in the second layer above the lower threshold and below the upper threshold in accordance with the following equations:

$\min <br><br><br><br>\mathrm{Total}<br><br><br><br>\mathrm{Latency}=\underset{\left(s,t\right)\in <br><br>V^{\mathrm{\prime <br><br>}}\times <br><br>V^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>\mathrm{latency}<br><br>\left(s,t\right)$ $\mathrm{subject}<br><br><br><br>\mathrm{to}<br><br>\text{;<br><br>}$ $\underset{\left(x,y\right)\in <br><br>E^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>F_{\left(x,y\right)}^{\left(s,t\right)}-\underset{\left(y,z\right)\in <br><br>E^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>F_{\left(y,z\right)}^{\left(s,t\right)}=\{\begin{array}{cc}-1,& \mathrm{if}<br><br><br><br>y=s\\ 1,& \mathrm{if}<br><br><br><br>y=t\\ 0,& \mathrm{otherwise}\end{array}<br><br><br><br>\forall <br><br>y,s,t\in <br><br>V^{\mathrm{\prime <br><br>}}<br><br><br><br>\mathrm{latency}<br><br>\left(s,t\right)=\underset{\left(x,y\right)\in <br><br>E^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>\mathrm{delay}<br><br>\left(x,y\right)\times <br><br>F_{\left(x,y\right)}^{\left(s,t\right)}<br><br><br><br>\forall <br><br>\left(s,t\right)\in <br><br>V^{\mathrm{\prime <br><br>}}\times <br><br>V^{\mathrm{\prime <br><br>}}<br><br><br><br>\underset{\left(s,t\right)\in <br><br>V^{\mathrm{\prime <br><br>}}\times <br><br>V^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>\mathrm{secondlayer\_demands}<br><br>\left(s,t\right)\times <br><br>F_{\left(x,y\right)}^{\left(s,t\right)}\le <br><br>L<br><br>\left(x,y\right)<br><br><br><br>\forall <br><br>\left(x,y\right)\in <br><br>E^{\mathrm{\prime <br><br>}}$

wherein secondlayer_demands(s,t) is the traffic demand between nodes s and t, F_(x,y)^(s,t) is the fraction of traffic between nodes s and t that goes over link (x,y) between nodes x and y in the second layer, F_(y,z)^(s,t) is the fraction of traffic between the nodes s and t that goes over link (y,z) between nodes y and z in the second layer, L(x,y) is the upper threshold for load on the link (x,y) in the second layer, latency(s,t) is the end-to-end latency between nodes s and t, delay(x,y) is the latency of the link (x,y) between the nodes x and y, V′

is the set of nodes in the second layer including nodes s, t, x, and y, and z, and E′

is the set of links in the second layer including the links (x,y) and (y,z).

6. The network of claim 3, wherein

the first routing objective is to at least one of balance load in the network and minimize an overall cost of the network,

the second routing objective is to minimize end-to-end latency of traffic paths in the second layer,

the second layer follows the second routing objective within the developed constraints in routing traffic by minimizing a sum of the end-to-end latency of each traffic path in the second layer while sending dummy traffic through links in the second layer such that the first layer in routing traffic cannot reroute traffic through the links including the dummy traffic, and

the dummy traffic is only sent over links unused by any traffic in the second layer and links which do not overlap with links used by traffic in the second layer.

13. The network of claim 1, wherein the first layer develops constraints based on the second routing objective and follows the first routing objective within the developed constraints in routing traffic.

7. A network comprising:

a plurality of nodes forming a first layer, the first layer following a first routing objective in routing traffic;

a sub-set of the plurality of nodes forming a second layer following a second routing objective in routing traffic, wherein

the first layer develops constraints based on the second routing objective and follows the first routing objective within the developed constraints in routing traffic.

8. The network of claim 7, wherein

the first layer follows the first routing objective within the developed constraints in routing traffic without exchanging information with the second layer, and

the second layer follows the second routing objective in routing traffic without exchanging information with the first layer.

9. The network of claim 7, wherein the first layer develops the constraints by proactively considering a reaction of the second layer following the second routing objective in routing traffic to traffic routing at the first layer.

10. The network of claim 9, wherein

the first routing objective is to at least one of balance load in the network and minimize an overall cost of the network,

the second routing objective is to minimize end-to-end latency of traffic paths in the second layer, and

the first layer follows the first routing objective within the developed constraints in routing traffic by balancing load in the first layer while maintaining traffic paths in the first layer at a same length such that latencies of links in the second layer are not changed.

11. The network of claim 10, wherein the first layer balances load in the first layer while maintaining the traffic paths in the first layer at the same length such that the latencies of the links in the second layer are not changed in accordance with the following equation:

$\min <br><br><br><br>\mathrm{Maximum}<br><br><br><br>\mathrm{util}=\underset{\left(x,y\right)\in <br><br>E}{\max }<br><br>\frac{\mathrm{load}<br><br>\left(x,y\right)}{\mathrm{capacity}<br><br>\left(x,y\right)}$ $\mathrm{subject}<br><br><br><br>\mathrm{to}<br><br>\text{;<br><br>}$ $\underset{\left(x,y\right)\in <br><br>E}{\sum <br><br>}<br><br>f_{\left(x,y\right)}^{\left(s,t\right)}-\underset{\left(y,z\right)\in <br><br>E}{\sum <br><br>}<br><br>f_{\left(y,z\right)}^{\left(s,t\right)}=\{\begin{array}{cc}-1,& \mathrm{if}<br><br><br><br>y=s\\ 1,& \mathrm{if}<br><br><br><br>y=t\\ 0,& \mathrm{otherwise}\end{array}<br><br><br><br>\forall <br><br>y,s,t\in <br><br>E<br><br><br><br>\mathrm{load}<br><br>\left(x,y\right)=\underset{\left(s,t\right)\in <br><br>V\times <br><br>V}{\sum <br><br>}<br><br>\mathrm{demand}<br><br>\left(s,t\right)\times <br><br>f_{\left(x,y\right)}^{\left(s,t\right)}<br><br><br><br>\forall <br><br>\left(x,y\right)\in <br><br>E<br><br><br><br>\underset{\left(x,y\right)\in <br><br>E}{\sum <br><br>}<br><br>f_{\left(x,y\right)}^{\left(s,t\right)}\le <br><br>1.02\times <br><br>{H<br><br>\left(s,t\right)}_{\mathrm{prev}}<br><br><br><br>\forall <br><br>\left(s,t\right)\in <br><br>V\times <br><br>V$

wherein f_(x,y)^(s,t) is an amount of traffic between nodes s and t in the first layer that goes over a link (x,y) between nodes x and y in the first layer, 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 layer computed as Σ

<sub>(x,y)∈

E</sub> f_(x,y)^(s,t), H(s,t)_prev is the hopcount of a traffic path between nodes s and t in the first layer computed in a previous iteration of load balancing, V is the set of nodes in the first layer including nodes s, t, x, and y, and z, and E is the set of links in the first layer including the links (x,y) and (y,z).

12. The network of claim 9, wherein

the first routing objective is to at least one of balance load in the network and minimize an overall cost of the network,

the second routing objective is to minimize end-to-end latency of traffic paths in the second layer,

the first layer follows the first routing objective within the developed constraints in routing traffic by balancing load in the first layer while artificially increasing latency on links in the first layer such that the second layer does not use the links having the artificially increased latency in routing traffic in the second layer, and

the first layer artificially increases the latency on the links in the first layer 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 layer, and

(c) repeating steps (a) and (b) until the maximum link utilization in the network is reduced to a utilization threshold.

14. A method, comprising:

routing traffic, by a plurality of nodes forming a first network layer, according to a first routing objective; and

developing constraints on a second routing objective based on the first routing objective;

routing traffic, by a sub-set of the plurality of nodes forming a second network layer, according to the second routing objective and the developed constraints.

15. A method, comprising:

developing constraints on a first routing objective based on a second routing objective;

routing traffic, by a plurality of nodes forming a first network layer, according to the first routing objective and the developed constraints; and

routing traffic, by a sub-set of the plurality of nodes forming a second network layer, according to the second routing objective.

16. A method comprising:

providing a plurality of nodes configured to form a first layer, the first layer following a first routing objective in routing traffic;

providing a sub-set of the plurality of nodes configured to form a second layer, the second layer developing constraints based on the first routing objective and following a second routing objective within the developed constraints in routing traffic.

17. A method comprising:

providing a plurality of nodes configured to form a first layer, the first layer following a first routing objective in routing traffic;

providing a sub-set of the plurality of nodes configured to form a second layer following a second routing objective in routing traffic, wherein

the first layer develops constraints based on the second routing objective and follows the first routing objective within the developed constraints in routing traffic.