Load balancing techniques for inter-domain traffic engineering
A method for balancing traffic across paths connecting a network to the Internet using a fractional allocation strategy for distributing the traffic from a congested selected path. The strategy includes: (a) associating the paths j with a counter i; (b) calculating the total initial selected path overload; (c) calculating the selected path load, wherein the load is equal to the initial selected path overload less the sum of the low capacity boundary for i path(s); (d) calculating the portion of the traffic on the selected path to be distributed using a bi-sectional search strategy; (e) distributing a portion of the traffic on the selected path to the other paths; and (f) stopping if there are no more paths (i=j), otherwise increasing the numerical value of the counter by one (1) and go to step (c).
1. A method for balancing traffic across paths connecting a network to the Internet comprising:
forming a connection between a home network and a large network which connects to a plurality of networks, wherein the connection comprises a plurality of paths (p), carrying traffic in the form of data packets between the home network and the large network, wherein each path has a path load (x i ), which is the amount of traffic allocated to a path (p), an available capacity (c i ), which is the amount of traffic that the path (p) can transmit, and a low capacity boundary (l i ) and a high capacity boundary (h i ), which are the measured high and low capacity bounds of the available capacity (c i );
measuring the path load (x i )of each of the plurality of paths (p);
measuring the high capacity boundary (h i ) of each of the plurality of paths (p);
comparing the path load (x i ) and the high capacity boundary (h i (0)) for each of the plurality of paths (p);
selecting one of the plurality of paths (p), wherein the plurality of paths (p) comprises the selected path (p 0 ) and other paths (p i ), wherein the selected path (p 0 ) has an initial overload (x 0 (0)), and wherein the overload exists when the initial selected path load (x 0 ) is greater than the initial selected path high capacity boundary (h 0 ); and
choosing the path load (x i ) for each of the plurality of other paths (p i ) using a fractional allocation strategy, wherein the fractional allocation strategy comprises:
(a) indexing the other paths (p i ) by i, wherein i is a set of integers from 1 to P, wherein P is the total number of other paths (p i );
(b) associating a plurality of pinning intervals with a counter (t), wherein the initial value of the counter is set to zero (t=0) and there are a total of N pinning intervals;
(c) calculating a portion (y(t)) of the initial selected path overload (x 0 (0)) to be off-loaded and distributed to the other paths (p i ) using a bi-sectional search strategy and skipping to step (f);
(d) calculating an updated selected path overload (x 0 (t)), wherein the updated selected path overload (x 0 (t)) is equal to the initial selected path overload (x 0 (0)) less the sum of the low capacity boundary for i path(s);
(e) calculating the portion (y(t)) of the updated selected path load (x 0 (t)) to be off-loaded and distributed to the other paths (p i ) using a bi-sectional search strategy;
(f) measuring the low capacity boundary (l i ) and the high capacity boundary (h i ) of the other paths (p i ) at pinning interval (t);
(g) distributing the portion (y(t)) of the initial selected path overload or the updated selected path load (x 0 (t)) to the other paths (p i ), wherein the portion of the traffic (y(t)) is distributed to the other paths (p i ) using the equation
x
i
=
l
i
(
t
)
+
h
i
(
t
)
-
l
i
(
t
)
∑
i
=
1
P
(
h
i
(
t
)
-
l
i
(
t
)
)
and
(h) stopping if there are no more pinning intervals (t =N), otherwise increasing the numerical value of the counter by one (1) and go to step (d).
2. The method for balancing traffic across paths connecting a network to the Internet according to claim 1 , wherein the bi-sectional search strategy chooses the portion (y(t)) of the traffic to be off-loaded and distributed using the equation:
y
(
t
)
=
min
{
(
0.5
)
[
∑
i
=
1
P
(
h
i
(
t
)
-
l
i
(
t
)
)
]
,
(
x
0
(
t
)
)
}
.
3. The method for balancing traffic across paths connecting a network to the Internet according to claim 1 , wherein the amount of traffic from the home network to the large network over the selected path (p 0 ) is measured using flow level measurements or Simple Network Management Protocol (SNMP).
4. The method for balancing traffic across paths connecting a network to the Internet according to claim 1 , wherein the initial selected path high capacity boundary (h 0 (0)) is measured using active probes, or passive measurements of traffic details.
5. The method for balancing traffic across paths connecting a network to the Internet according to claim 1 , wherein the initial selected path high capacity boundary (h 0 (0)) is measured using Transmission Control Protocol (TCP) Synchronize/Acknowledgement (SYN/ACK) response time.
6. The method for balancing traffic across paths connecting a network to the Internet according to claim 1 , wherein the initial selected path high capacity boundary (h 0 (0)) is measured using Round Trip Time (RTT), and loss measurements.
7. The method for balancing traffic across paths connecting a network to the Internet according to claim 1 , wherein the initial selected path low capacity boundary (l 0 (0) is equal to 0 and the initial selected path high capacity boundary (h 0 (0)) is equal to 1.