Abstract
Existing approaches to determining network topology, which are typically reliant on integer programming, struggle with scalability and complexity. This disclosure describes techniques to efficiently determine the logical topology of a network, considering its physical layout and desired capacity between blocks. The techniques leverage principles of graph theory and break down the problem into four stages, e.g., rounding to an integral target topology; partitioning into supernode-level graphs; converting to a bipartite graph; and recursively partitioning the bipartite graphs. By substituting existing integer programming algorithms — which are NP-hard and scale exponentially — with polynomial time combinatorial algorithms such as flows and matchings, the described techniques achieve faster, more performant, and more scalable optimization of network topology. The use of graph theoretic and combinatorial algorithms enables efficient management of complex data center fabrics.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Recommended Citation
NA, "Scalable Determination of Network Topology", Technical Disclosure Commons, (November 15, 2024)
https://www.tdcommons.org/dpubs_series/7535