Method and apparatus for multi-path load balancing using multiple metrics
View Patent ↗One embodiment of the present invention provides a system for facilitating multi-path load balancing at a local node in a network. During operation, the system measures a value for a metric on a local link which couples the local node to a neighboring node. In addition, the system receives from the neighboring node a neighbor path-metric value which indicates a value for the metric associated with all paths from the neighboring node to a destination node. The system then computes a “local path-metric value” for the metric associated with all paths from the local node to the destination node via the local link and the neighboring node. The system further computes a “packet-forwarding probability” corresponding to the destination node for each local link coupled to the local node, wherein the distribution of the packet-forwarding probability bears a nonlinear relation to the distribution of the local path-metric values for all the local links. The system subsequently forwards a packet destined for the destination node to one of the local links based on the computed packet-forwarding probability for that local link.
1. A method for facilitating multi-path load balancing at a local node in a network, the method comprising:
measuring a value for a metric on a local link which couples the local node to a neighboring node;
receiving from the neighboring node a neighbor path-metric value which indicates a value for the metric associated with paths from the neighboring node to a destination node;
computing a local path-metric value for the metric associated with paths from the local node to the destination node via the local link and the neighboring node;
computing a packet-forwarding probability corresponding to the destination node for each local link coupled to the local node,
wherein the distribution of the packet-forwarding probability bears a nonlinear relation to the distribution of the local path-metric values for the local links,
wherein computing the packet-forwarding probability involves computing a metric-specific path weight for paths that traverse a local link and lead to the destination node,
wherein the metric-specific path weight indicates the likelihood of the corresponding local link being chosen for forwarding packets to the destination node,
wherein computing the metric-specific path weight involves computing a distribution of the local path-metric values for the metric using the following formula:
pw
ij
←
exp
(
pm
ij
/
T
j
)
∑
k
=
1
N
exp
(
pm
kj
/
T
j
)
;
wherein
i denotes the index of a local link;
j denotes the index of a metric, if more than one metric is associated with a local link;
pw ij denotes the metric-specific path weight for metric j and for paths traversing local link i;
pm ij denotes the local path-metric value for metric j and for paths traversing local link i;
T j denotes a pre-determined parameter associated with metric j; and
N denotes the total number of local links; and
forwarding a packet destined for the destination node to one of the local links based on the computed packet-forwarding probability for that local link.
2. The method of claim 1 wherein if a local link has more than one metric, the pre-determined parameter T j associated with metric j has a value of 1/N, wherein N denotes the total number of local links.
3. The method of claim 1 , wherein if a local link has more than one metric, computing the packet-forwarding probability involves computing a link weight for a local link as follows:
w
i
←
∑
j
=
1
M
Q
j
·
pw
ij
;
wherein
i denotes the index of a local link;
j denotes the index of a metric;
w i denotes the link weight for local link i;
pw ij denotes the metric-specific path weight for metric j and for a path traversing local link i;
Q j denotes the weight assigned to metric j for calculating the link weight; and
M denotes the total number of metrics.
4. The method of claim 3 , further comprising computing an average metric value associated with the destination node for a given metric and for the paths which lead to the destination node and which traverse the local links, as follows:
am
j
←
∑
i
=
1
N
w
i
·
pm
ij
;
wherein
i denotes the index of a local link;
j denotes the index of a metric;
am j denotes the average metric value for metric j;
w i denotes the link weight for local link i;
pm ij denotes the local path-metric value for metric j and for paths traversing local link i and leading to the destination node; and
N denotes the total number of local links.
5. The method of claim 4 , further comprising communicating a rounded average metric value to a neighboring node.
6. The method of claim 5 , wherein the communication of the rounded average metric value to the neighboring node occurs when the current rounded average metric value differs from a corresponding previously communicated value.
7. The method of claim 3 , wherein forwarding the packet involves forwarding the packet to a local link i with a probability of w i .
8. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for facilitating multi-path load balancing at a local node in a network, the method comprising:
measuring a value for a metric on a local link which couples the local node to a neighboring node;
receiving from the neighboring node a neighbor path-metric value which indicates a value for the metric associated with paths from the neighboring node to a destination node;
computing a local path-metric value for the metric associated with paths from the local node to the destination node via the local link and the neighboring node;
computing a packet-forwarding probability corresponding to the destination node for each local link coupled to the local node,
wherein the distribution of the packet-forwarding probability bears a nonlinear relation to the distribution of the local path-metric values for the local links,
wherein computing the packet-forwarding probability involves computing a metric-specific path weight for paths that traverse a local link and lead to the destination node; and
wherein the metric-specific path weight indicates the likelihood of the corresponding local link being chosen for forwarding packets to the destination node,
wherein computing the metric-specific path weight involves computing a distribution of the local path-metric values for the metric using the following formula:
pw
ij
←
exp
(
pm
ij
/
T
j
)
∑
k
=
1
N
exp
(
pm
kj
/
T
j
)
;
wherein
i denotes the index of a local link;
j denotes the index of a metric, if more than one metric is associated with a local link;
pw ij denotes the metric-specific path weight for metric j and for paths traversing local link i;
pm ij denotes the local path-metric value for metric j and for paths traversing local link i;
T j denotes a pre-determined parameter associated with metric j; and
N denotes the total number of local links; and
forwarding a packet destined for the destination node to one of the local links based on the computed packet-forwarding probability for that local link.
9. The computer-readable storage medium of claim 8 , wherein if a local link has more than one metric, the pre-determined parameter T j associated with metric j has a value of 1/N, wherein N denotes the total number of local links.
10. The computer-readable storage medium of claim 8 , wherein if a local link has more than one metric, computing the packet-forwarding probability involves computing a link weight for a local link as follows:
w
i
←
∑
j
=
1
M
Q
j
·
pw
ij
;
wherein
i denotes the index of a local link;
j denotes the index of a metric;
w i denotes the link weight for local link i;
pw ij denotes the metric-specific path weight for metric j and for a path traversing local link i;
Q j denotes the weight assigned to metric j for calculating the link weight; and
M denotes the total number of metrics.
11. The computer-readable storage medium of claim 10 , further comprising computing an average metric value associated with the destination node for a given metric and for the paths which lead to the destination node and which traverse the local links, as follows:
am
j
←
∑
i
=
1
N
w
i
·
pm
ij
;
wherein
i denotes the index of a local link;
j denotes the index of a metric;
am j denotes the average metric value for metric j;
w i denotes the link weight for local link i;
pm ij denotes the local path-metric value for metric j and for paths traversing local link i and leading to the destination node; and
N denotes the total number of local links.
12. The computer-readable storage medium of claim 11 , further comprising communicating a rounded average metric value to a neighboring node.
13. The computer-readable storage medium of claim 12 , wherein the communication of the rounded average metric value to the neighboring node occurs when the current rounded average metric value differs from a corresponding previously communicated value.
14. The computer-readable storage medium of claim 10 , wherein forwarding the packet involves forwarding the packet to a local link i with a probability of w i .
15. An apparatus for facilitating multi-path load balancing at a local node in a network, the apparatus comprising:
a metric-measurement mechanism configured to measure a value for a metric on a local link which couples the local node to a neighboring node;
a receiving mechanism configured to receive from the neighboring node a neighbor path-metric value which indicates a value for the metric associated with paths from the neighboring node to a destination node;
a computing mechanism configured to:
computing a local path-metric value for the metric associated with paths from the local node to the destination node via the local link and the neighboring node; and
to compute a packet-forwarding probability corresponding to the destination node for each local link coupled to the local node,
wherein the distribution of the packet-forwarding probability bears a nonlinear relation to the distribution of the local path-metric values for the local links
wherein computing the packet-forwarding probability involves computing a metric-specific path weight for paths that traverse a local link and lead to the destination node,
wherein the metric-specific path weight indicates the likelihood of the corresponding local link being chosen for forwarding packets to the destination node,
wherein computing the metric-specific path weight involves computing a distribution of the local path-metric values for the metric using the following formula:
pw
ij
←
exp
(
pm
ij
/
T
j
)
∑
k
=
1
N
exp
(
pm
kj
/
T
j
)
;
wherein
i denotes the index of a local link;
j denotes the index of a metric, if more than one metric is associated with a local link;
pw ij denotes the metric-specific path weight for metric j and for paths traversing local link i;
pm ij denotes the local path-metric value for metric j and for paths traversing local link t
T j denotes a pre-determined parameter associated with metric j; and
N denotes the total number of local links; and
a packet-forwarding mechanism configured to forward a packet destined for the destination node to one of the local links based on the computed packet-forwarding probability for that local link.