att_abstract={{Enterprise networks are increasingly adopting
Layer 3 Multiprotocol Label Switching (MPLS) Virtual Private
Network (VPN) technology to connect geographically disparate
locations. The any-to-any direct connectivity model of this technology
involves a very high memory footprint and is causing
associated routing tables in the service provider´┐Żs routers to grow
very large. The concept of Relaying was proposed earlier [9]
to separately minimize the routing table memory footprint of
individual VPNs, and involves selecting a small number of hub
routers to maintain complete reachability information for that
VPN, and enabling non-hub spoke routers with reduced routing
tables to achieve any-to-any reachability by routing traffic via a
A large service provider network typically hosts many thousands
of different VPNs. In this paper, we generalize Relaying
to the multi-VPN environment, and consider new constraints on
resources shared across VPNs, such as router uplink bandwidth
and memory. The hub selection problem involves complex tradeoffs
along multiple dimensions including these shared resources,
and the additional distance traversed by traffic. We formulate the
hub selection as a constraint optimization problem and develop
an algorithm with provable guarantees to solve this NP-complete
problem. Evaluations using traces and configurations from a
large provider and many real-world VPNs indicate that the
resulting Relaying solution substantially reduces the total router
memory requirement by 85% while smoothing out the utilization
on each router and requiring only a small increase in the endto-
end path for the relayed traffic.}},
	att_authors={mb359y, ag1971 , mh0357, ss2864},
	att_copyright_notice={{This version of the work is reprinted here with permission of IEEE for your personal use. Not for redistribution. The definitive version was published in Proc. IEEE INFOCOM Mini-Conference and IEEE/ACM Transactions on Networking,  2009. {{, 2009-04-19}}
	att_tags={Optimization, VPN management, Relaying},
	author={MohammadHossein Bateni and Alexandre Gerber and Mohammad Hajiaghayi and Subhabrata Sen},
	institution={{in Proc. IEEE INFOCOM Mini-Conference and IEEE/ACM Transactions on Networking}},
	title={{Multi-VPN Optimization for Scalable Routing via Relaying}},