On Virtual Id Assignment in Networks for High Resilience Routing: A Theoretical Framework

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-identity-space 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.