Patent ID: 7492717

Claim:
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.