In recent years, the effort of promoting versatile, easy to manage routing schemes, as a replacement to OSPF has gathered momentum particularly in the context of large-scale enterprise networks, data center networks and software-defined wide area networks (SD-WANs). Such routing schemes rely on embedding the network into a geometric/topological space (e.g. a binary tree) to facilitate multi-path routing with reduced state maintenance and quick recovery in localized failure scenarios. In this work, we propose a systematic framework to embed the network topology into a hierarchical binary virtual-identityspace that is particularly amenable to multi-path routing. Our methodology firstly involves a relaxed form of the connected graph bi-partitioning problem that exploits a geometric embedding of the network in an n-dimensional Euclidean space (n being the number of hosts in the network) based on the Moore-Penrose pseudo inverse of the Laplacian for the graph associated with the network. The edges of the network are mapped to a weight distribution that helps construct a spanning tree from the core of the network towards the periphery, thereby providing a point of symmetry in the network to facilitate balanced bipartitions. This, in turn, yields a (nearly) full balanced binary tree embedding of the network and consequently a good virtual-id space. We also explore the binary identity assignment problem in another point of view by using bi-connected graph as the input graph to introduce a recursive bipartition algorithm. Through rigorous theoretical analysis and experimentation, we demonstrate that our methods perform well within reasonable bounds of computational complexity.
|Original language||English (US)|
|Title of host publication||2020 IEEE Global Communications Conference, GLOBECOM 2020 - Proceedings|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|State||Published - Dec 2020|
|Event||2020 IEEE Global Communications Conference, GLOBECOM 2020 - Virtual, Taipei, Taiwan, Province of China|
Duration: Dec 7 2020 → Dec 11 2020
|Name||2020 IEEE Global Communications Conference, GLOBECOM 2020 - Proceedings|
|Conference||2020 IEEE Global Communications Conference, GLOBECOM 2020|
|Country/Territory||Taiwan, Province of China|
|Period||12/7/20 → 12/11/20|
Bibliographical noteFunding Information:
ACKNOWLEDGEMENT This research was supported in part by US NSF grants CNS-1618339, CNS-1617729, CNS-1814322, and CNS-1836772.
© 2020 IEEE.
- Virtual Id
- recursive bipartition