Method and apparatus for multi-path load balancing using multiple metrics

• US 20070140114A1
• Filed: 12/20/2005
• Published: 06/21/2007
• Est. Priority Date: 12/20/2005
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Mosko, Marc
• Granted Patent: US 7,492,717 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

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.

Claims

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; 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 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.

3. The method of claim 2, wherein computing the metric-specific path weight involves computing a distribution of the local path-metric values for the metric using the following formula:

${\mathrm{pw}}_{\mathrm{ij}}\leftarrow <br><br>\frac{\exp <br><br>\left({\mathrm{pm}}_{\mathrm{ij}}/T_j\right)}{\underset{k=1}{\overset{N}{\sum <br><br>}}<br><br>\exp <br><br>\left({\mathrm{pm}}_{\mathrm{kj}}/T_j\right)};<br><br>$

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.

4. The method of claim 3, 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.

5. The method of claim 3, 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\leftarrow <br><br>\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br>Q_j·<br><br>{\mathrm{pw}}_{\mathrm{ij}};<br><br>$

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.

6. The method of claim 5, 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:

${\mathrm{am}}_j\leftarrow <br><br>\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>w_i·<br><br>{\mathrm{pm}}_{\mathrm{ij}};<br><br>$

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.

7. The method of claim 6, further comprising communicating a rounded average metric value to a neighboring node.

8. The method of claim 7, 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.

9. The method of claim 5, wherein forwarding the packet involves forwarding the packet to a local link i with a probability of w_i.

11. The computer-readable storage medium of claim 9, 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.

12. The computer-readable storage medium of claim 11, wherein computing the metric-specific path weight involves computing a distribution of the local path-metric values for the metric using the following formula:

${\mathrm{pw}}_{\mathrm{ij}}\leftarrow <br><br>\frac{\exp <br><br>\left({\mathrm{pm}}_{\mathrm{ij}}/T_j\right)}{\underset{k=1}{\overset{N}{\sum <br><br>}}<br><br>\exp <br><br>\left({\mathrm{pm}}_{\mathrm{kj}}/T_j\right)};<br><br>$

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.

13. The computer-readable storage medium of claim 12, 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.

14. The computer-readable storage medium of claim 12, 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\leftarrow <br><br>\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br>Q_j·<br><br>{\mathrm{pw}}_{\mathrm{ij}};<br><br>$

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.

15. The computer-readable storage medium of claim 14, 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:

${\mathrm{am}}_j\leftarrow <br><br>\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>w_i·<br><br>{\mathrm{pm}}_{\mathrm{ij}};<br><br>$

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.

16. The computer-readable storage medium of claim 15, further comprising communicating a rounded average metric value to a neighboring node.

17. The computer-readable storage medium of claim 16, 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.

18. The computer-readable storage medium of claim 14, wherein forwarding the packet involves forwarding the packet to a local link i with a probability of w_i.

10. 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; 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.

19. 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; 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.

20. The apparatus of claim 19, wherein while the packet-forwarding probability, the computing mechanism is configured to compute 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.