att_abstract={{Enterprise customers are increasingly adopting MPLS(Multiprotocol Label  Switching) VPN (Virtual Private Network) service that offers direct  any-to-any reachability among the customer sites via a provider network.  Unfortunately this direct reachability model makes the service provider's  routing tables grow very large as the number of VPNs and the number of  routes per customer increase. As a result, router memory in the provider's network has become a key  bottleneck in provisioning new customers. This paper proposes Relaying, a  scalable VPN routing architecture that the provider can implement simply  by modifying the configuration of routers in the provider network, without  requiring changes to the router hardware and software. Relaying  substantially reduces the memory footprint of VPNs by choosing a small  number of hub routers in each VPN that maintain full reachability  information, and by allowing nonhub routers to reach other routers through  a hub. Deploying Relaying in practice, however, poses a challenging  optimization problem that involves minimizing router memory usage by  having as few hubs as possible, while limiting the additional latency due  to indirect delivery via a hub. We first investigate the fundamental tension between the two objectives and then develop algorithms to solve the optimization problem by leveraging some unique properties of VPNs, such as sparsity of traffic matrices and spatial locality of  customer sites. Extensive evaluations using real traffic matrices, routing  configurations, and VPN topologies demonstrates that Relaying is very  promising and can reduce routing-table usage by up to 90%, while  increasing the additional distances traversed by traffic by only a few  hundred miles, and the backbone bandwidth usage by less than 10%. }},
	att_authors={ag1971, cl9862, dp8327, ss2864},
	att_copyright_notice={{(c) ACM, 2008. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM SIGMETRICS 2008 {{, 2008-06-06}}.}},
	att_tags={VPN, traffic matrix, routing, indirection, provisioning},
	author={Changhoon Kim and Alexandre Gerber and Carsten Lund and Dan Pei and Subhabrata Sen},
	institution={{in Proc. ACM SIGMETRICS}},
	title={{Scalable VPN Routing via Relaying}},