© 2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Multi-VPN Optimization for Scalable Routing via Relaying

MohammadHossein Bateni , Alexandre Gerber , MohammadTaghi Hajiaghayi , Subhabrata Sen ,

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 is causing routing tables in the service provider's routers to grow very large. The concept of relaying was proposed earlier to separately minimize the routing table memory footprint of individual VPNs by selecting a small number of hub routers to maintain complete reachability information for each VPN and enabling nonhub spoke routers with reduced routing tables to reach others by routing traffic via a hub. A large service provider network typically hosts 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 approximate this NP-complete problem. Evaluations using traces and configurations from a large provider indicate that the resulting relaying solution reduces the total router memory requirement by 85% while smoothing out the utilization on each router and requiring only a small increase in the end-to-end path for the relayed traffic.



References

  1. “Sample prices of CISCO 12416 components,” , [online]. Avalilable: http://www.google.com/products?q=cisco+12416&btnG=Search+Products&hl=en&show=dd/
  2. “Sample prices of Juniper M320 components,” , [online]. Avalilable: http://www.google.com/products?q=juniper+m320&btnG=Search+Products&hl=en&show=dd/
  3. A. Archer , “Inapproximability of the asymmetric facility location and $k$ -median problems,” , 2000
  4. M. Bateni , A. Gerber , M. Hajiaghayi , S. Sen , " Multi-VPN optimization for scalable routing via relaying " , Proc. IEEE INFOCOM , Apr. 2009 , pp. 2756 - 2760
  5. M. Bateni , M. Hajiaghayi , " The assignment problem in content distribution networks: Unsplittable hard-capacitated facility location " , Proc. ACM-SIAM SODA , 2009 , pp. 805 - 814
  6. J. Byrka , " An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem " , Proc. APPROX , 2007 , pp. 29 - 43
  7. M. Caesar , T. Condie , J. Kannan , K. Lakshminarayanan , I. Stoica , " ROFL: Routing on flat labels " , Proc. ACM SIGCOMM , Sep. 2006 , pp. 363 - 374
  8. N. G. Duffield , P. Goyal , A. Greenberg , P. Mishra , K. K. Ramakrishnan , J. E. M. van der , " Resource management with hoses: point-to-cloud services for virtual private networks " , IEEE/ACM Trans. Netw. , Oct. 2002 , pp. 679 - 692
  9. D. Farinacci , V. Fuller , D. Meyer , D. Lewis , “Locator/ID separation protocol (LISP),” , 2009
  10. U. Feige , " A threshold of ln n for approximating set cover " , J. ACM , 1998 , pp. 634 - 652
  11. B. Ford , " Unmanaged Internet protocol: Taming the edge network management crisis " , Proc. HotNets , Mar. 2006
  12. D. S. Johnson , " Approximation algorithms for combinatorial problems " , J. Comput. Syst. Sci. , 1974 , pp. 256 - 278
  13. C. Kim , A. Gerber , C. Lund , D. Pei , S. Sen , " Scalable VPN routing via relaying " , Proc. ACM SIGMETRICS , 2008 , pp. 61 - 72
  14. M. Mahdian , M. Pál , " Universal facility location " , Proc. ESA , 2003 , pp. 409 - 421
  15. A. Meyerson , K. Munagala , S. Plotkin , " Cost-distance: Two metric network design " , Proc. IEEE FOCS , 2000 , pp. 624 - 624
  16. S. Raghunath , S. Kalyanaraman , K. K. Ramakrishnan , " Trade-offs in resource management for virtual private networks " , Proc. IEEE INFOCOM , Mar. 2005 , pp. 1467 - 1477
  17. S. Raghunath , K. K. Ramakrishnan , S. Kalyanaraman , C. Chase , " Measurement based characterization and provisioning of IP VPNs " , Proc. IMC , Oct. 2004 , pp. 342 - 355
  18. R. Raz , S. Safra , " A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP " , Proc. ACM STOC , 1997 , pp. 475 - 484
  19. D. Shmoys , " Approximation algorithms for facility location problems " , Proc. APPROX , 2000 , pp. 27 - 33
  20. C. Wilson , “Cogent throws down pricing gauntlet,” , [online]. Avalilable: http://telephonyonline.com/ethernet/news/Cogent_price_cuts_06112008/2008
  21. J. Zhang , B. Chen , Y. Ye , " A multi-exchange local search algorithm for the capacitated facility location problem " , Proc. IPCO , 2004 , pp. 219 - 233
  22. X. Zhang , P. Francis , J. Wang , K. Yoshida , " Scaling IP routing with the core router-integrated overlay " , Proc. ICNP , 2006 , pp. 147 - 156