Fault tolerant and load balanced routing
AssigneeMicrosoft Technology Licensing, LLC
InventorsHaitao Wu, Chuanxiong Guo, Yongguang Zhang, Lihua Yuan
Life of this patent
Estimating the term…
Abstract
Techniques are described for balancing traffic load for networks configured in multi-rooted tree topologies, in the presence of link failures. Maximum flows (through minimum cuts) are calculated for subgraphs that incorporate effective link capacities on links between source and destination nodes. Effective link capacities may be determined that take into account link failures, as well as sharing of current available link capacities by multiple nodes. Traffic is balanced while simultaneously fully utilizing available link capacities, even available link capacities on partially failed links (e.g., partially failed Link Aggregation Groups (LAGs)).
Claims20
A method comprising:
- determining, by one or more processors, link capacities for logical links of two or more directly adjacent nodes between a sending node and a receiving node, the logical links including multiple physical links, the link capacities accounting for failure of a physical link of the physical links;
- determining, based on the link capacities, effective link capacities of the two or more nodes, the effective link capacities accounting for sharing of link capacity of the logical link at a node of the two or more nodes;
- determining, based on the effective link capacities, maximum flows of two or more distinct paths through the two or more nodes between the sending node and the receiving node;
- determining weights for the two or more distinct paths based on the maximum flows;
- and
- routing traffic along the two or more distinct paths between the sending node and the receiving node based on the weights.
A system comprising:
- one or more processors;
- one or more non-transitory computer-readable storage media having computer-executable instructions thereon that, upon execution by the one or more processors, configure the one or more processors to perform operations comprising:
- determining link capacities for logical links of two or more directly adjacent nodes between a sending node and a receiving node, the logical links including multiple physical links, the link capacities accounting for failure of a physical link of the physical links;
- determining, based on the link capacities, effective link capacities of the two or more nodes, the effective link capacities accounting for sharing of link capacity of the logical link at a node of the two or more nodes;
- determining, based on the effective link capacities, maximum flows of two or more distinct paths through the two or more nodes between the sending node and the receiving node;
- determining weights for the two or more distinct paths based on the maximum flows;
- and
- routing traffic along the two or more distinct paths between the sending node and the receiving node based on the weights.
A non-transitory machine-readable medium including instructions that, when executed by a machine, cause the machine to perform operations comprising:
- determining, by one or more processors, link capacities for logical links of two or more directly adjacent nodes between a sending node and a receiving node, the logical links including multiple physical links, the link capacities accounting for failure of a physical link of the physical links;
- determining, based on the link capacities, effective link capacities of the two or more nodes, the effective link capacities accounting for sharing of link capacity of the logical link at a node of the two or more nodes;
- determining, based on the effective link capacities, maximum flows of two or more distinct paths through the two or more nodes between the sending node and the receiving node;
- determining weights for the two or more distinct paths based on the maximum flows;
- and
- routing traffic along the two or more distinct paths between the sending node and the receiving node based on the weights.
Dependencies are inferred from the claim text.