Virtual topologies for abstraction service for IP-VPNs

VPN service providers(VSP) and IP-VPN customers have maintained service demarcation boundaries between their routing and signaling entities resulting in the VPN's viewing the VSP network as an opaque entity and therefore limiting interaction between the two. Ravi et. al in [1] introduced the notion of topology abstraction as a means for sharing the core topology information as abstract graphs associated with QoS metric information. This has been further studied in a series of papers [2], [9] and [4]. In the more recent work [4], three decentralized schemes to generate topology abstractions were proposed and evaluated through extensive simulations. These schemes used some very powerful tools from graph theory and combinatorial optimization. But the topology considered in [4] for abstraction is very simple and sparse. In this paper we continue this study and propose two new schemes for topology abstraction. Specifically, given a core network with node set V, and also given the node-to-node maximum flow matrix F = [f(u, v)] for any connected graph G = (V *,E) with V * a subset of V, we show how to assign capacities to the edges of G such that the maximum available flow between any pair of vertices u, v ∈ V * in G is at most the maximum available flow between u and v in the core network. Though this methodology is applicable to any graph, we seek abstract topologies with certain other desirable properties: low degree, number of edges being linear in the number of vertices, amenable to survivable logical topology routing in an IP over WDM optical networks etc. Chordal graphs have such properties. In this paper we show how to construct 2-vertex and 2-edge connected chordal graphs, starting from the Gomory-Hu tree of the flow matrix of the core network. Using the theory of graph augmentation presented in [10] one can develop other sparse virtual
¹
topologies possessing the properties demanded by an application.