| 摘要 |
Methods and apparatus are provided with improved routing techniques for bifurcated flows. Routing methods and apparatus are provided that obtain a fractional flow from a set of nodes to a given destination having a maximum load, L, on any link between a node in the set and the given destination; and generate a bifurcated flow between the set of nodes and the given destination from the fractional flow such that the maximum load on any link in the bifurcated flow does not exceed 2L, wherein the bifurcated flow allows a flow from a given node to be sent on at most two outgoing links. The fractional flow can be, for example, a fractional single-sink multicommodity flow. |
| 主权项 |
1. A routing method, comprising:
obtaining a fractional flow on operational links between nodes in a set of nodes and a given destination, wherein each of said operational links has a load, l, and wherein a maximum load, L, is a maximum of said loads, l, on any operational link between a node in said set and said given destination; applying one or more flow simplifying operations to said fractional flow to remove one or more of said operational links in said fractional flow until at most two outgoing operational links are employed from each node in said set to said given destination, wherein said one or more removed operational links have a flow at a time of said removal, wherein said operational links are selected for removal by said one or more flow simplifying operations by identifying one or more of said operational links in said fractional flow that one or more of satisfy a contraction property and are identified in a saw-tooth structure, wherein said contraction property comprises a link between a first node and a second node, where said first node has out-degree one and said second node is an out-neighbor of said first node, and wherein said saw-tooth structure is a collection:
{(u0,v0),P0,(u1,v1),P1,(u2,v2),P2, . . . ,(ur,vr),Pr}where (ui, vi) is an arc between said nodes ui and vi and Pi is a directed path from ui+1 to vi (subscripts modulo r+1); and
generating, based on said applying, a bifurcated flow between said set of nodes and said given destination from said fractional flow such that the maximum load on any operational link in said bifurcated flow does not exceed 2L, wherein said bifurcated flow allows a flow from a given node to be sent on at most two outgoing operational links, wherein one or more of said obtaining and generating steps are performed by a hardware device. |
