Traffic engineering for large scale data center networks

摘要

The present disclosure provides for the determination of bandwidth allocation of inter-block traffic in a data center network. It employs a number of optimization objectives and a heuristic water-filling strategy to avoid producing unnecessary paths and to avoid determining paths that would be unavailable when actually needed. Allocation may be adjusted incrementally upon node and link failure, for instance to perform only the minimal allocation changes necessary. If demand between a source and a destination cannot be satisfied, a decomposition process may be used to allocate remaining demand. One aspect constructs a graph for route computation based on inter-block topology. Here, the graph initially starts with a highest level of abstraction with each node representing a middle block, and gradually reduces the abstraction level to identify paths of mixed abstraction level to satisfy additional demand.

主权项

1. A method of traffic engineering in a computer network having a plurality of fabric blocks in communication with one another, the method comprising:
grouping, by one or more processors, a plurality of middle blocks into a plurality of logical clusters, each of the plurality of logical clusters forming one of the plurality of fabric blocks and including at least two middle blocks; identifying at least one destination fabric block from among the plurality of fabric blocks; evaluating, in round-robin order, each destination fabric block of the plurality of fabric blocks; choosing in round-robin order, by the one or more processors, a single destination middle block MBd in a selected destination fabric block FBd; selecting in round-robin order, by the one or more processors, a source fabric block FBs; identifying, by the one or more processors, a subset M of source middle blocks from among all middle blocks in the source fabric block FBs, the subset of middle blocks being identified as having a shortest available path length to the destination middle block MBd; and selecting for use in a network path, by the one or more processors, one of the source middle blocks MBs in the subset M that maximizes the following condition:
min(demand(MBs, FBd), spf_capacity(MBs, MBd)), in which spf_capacity(MBs, MBd) represents a shortest path capacity between the source middle block MBs and the destination middle block MBd, and demand(MBs, FBd) represents a demand between the source middle block MBs and the destination fabric block FBd.