Measurement-based characterization of IP VPNs

ABSTRACT

Virtual Private Networks (VPNs) provide secure and reliable communication between customer sites. With the increase in number and size of VPNs, providers need efficient provisioning techniques that adapt to customer demand by leveraging a good understanding of VPN properties.

In this paper, we analyze two important properties of VPNs that impact provisioning: 1) structure of customer endpoint (CE) interactions and 2) temporal characteristics of CE-CE traffic. We deduce these properties by computing traffic matrices from SNMP measurements. We find that existing traffic matrix estimation techniques are not readily applicable to the VPN scenario due to the scale of the problem and limited measurement information. We begin by formulating a scalable technique that makes the most out of existing measurement information and provides good estimates for common VPN structures. We then use this technique to analyze SNMP measurement information from a large IP VPN service provider.

We find that even with limited measurement information (no per-VPN data for the core) we can estimate traffic matrices for a significant fraction of VPNs, namely, those constituting the "Huband-Spoke" category. In addition, the ability to infer the structure of VPNs holds special significance for provisioning tasks arising from topology changes, link failures and maintenance. We are able to provide a classification of VPNs by structure and identify CEs that act as hubs of communication and hence require prioritized treatment during restoration and provisioning.

REFERENCES

• 1: Satish Raghunath , K. K. Ramakrishnan , Shivkumar Kalyanaraman , Chris Chase, Measurement based characterization and provisioning of IP VPNs, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028836]
• 2: E. Rosen , Y. Rekhter, BGP/MPLS VPNs, RFC Editor, 1999
• 3: N. G. Duffield , Pawan Goyal , Albert Greenberg , Partho Mishra , K. K. Ramakrishnan , Jacobus E. van der Merwe, Resource management with hoses: point-to-cloud services for virtual private networks, IEEE/ACM Transactions on Networking (TON), v.10 n.5, p.679-692, October 2002 [doi>10.1109/TNET.2002.803918]
• 4: [4] S. Raghunath, K. Chandrayana, and S. Kalyanaraman, "Edge-based QoS provisioning for point-to-set assured services," in Proc. ICC 2002, vol. 2, pp. 1128-1134.
• 5: [5] S. Raghunath and S. Kalyanaraman, "Statistical point-to-set edge-based quality of service provisioning," in Proc. QoFIS 2003, vol. 2, Springer Verlag, LNCS 2811, pp. 132-141.
• 6: [6] S. Raghunath, S. Kalyanaraman, and K. Ramakrishnan, "Trade-offs in resource management for virtual private networks," in Proc. IEEE INFOCOM 2005.
• 7: Yin Zhang , Matthew Roughan , Carsten Lund , David Donoho, An information-theoretic approach to traffic matrix estimation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863990]
• 8: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 9: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.265-280, June 2001 [doi>10.1109/90.929850]
• 10: [10] Y. Vardi, "Network tomography: Estimating source-destination traffic intensities from link data," J. Amer. Statist. Assoc., vol. 91, pp. 365-377, 1996.
• 11: [11] C. Tebaldi and M. West, "Bayesian inference on network traffic using link count data," J. Amer. Statist. Assoc., vol. 93, no. 442, pp. 557-576, 1998.
• 12: [12] J. Cao, D. Davis, S. Wiel, and B. Yu, "Time-varying network tomography," J. Amer. Statist. Assoc., vol. 95, no. 452, pp. 1063-1075, 2000.
• 13: [13] M. Bertero, T. Poggio, and V. Torre, "Ill-posed problems in early vision," Proc. IEEE, vol. 76, no. 8, pp. 869-889, Aug. 1988.
• 14: [14] I. Craig and J. Brown, Inverse Problems in Astronomy: A Guide to Inversion Strategies for Remotely Sensed Data. Boston, MA: Adam Hilger, 1986.
• 15: Arnold Neumaier, Solving Ill-Conditioned and Singular Linear Systems: A Tutorial on Regularization, SIAM Review, v.40 n.3, p.636-666, Sept. 1998 [doi>10.1137/S0036144597321909]
• 16: Yin Zhang , Matthew Roughan , Nick Duffield , Albert Greenberg, Fast accurate computation of large-scale IP traffic matrices from link loads, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 17: Amit Kumar , Rajeev Rastogi , Avi Silberschatz , Bulent Yener, Algorithms for provisioning virtual private networks in the hose model, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.135-146, August 2001, San Diego, California, United States
• 18: Anupam Gupta , Jon Kleinberg , Amit Kumar , Rajeev Rastogi , Bulent Yener, Provisioning a virtual private network: a network design problem for multicommodity flow, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.389-398, July 2001, Hersonissos, Greece [doi>10.1145/380752.380830]
• 19: Jogesh Muppala, Provisioning Virtual Private Networks in the Hose Model with Delay Requirements, Proceedings of the 2005 International Conference on Parallel Processing, p.211-218, June 14-17, 2005 [doi>10.1109/ICPP.2005.65]
• 20: [20] T. Erlebach and M. Ruegg, "Optimal bandwidth in hose-model VPNs with multi-path routing," in Proc. IEEE INFOCOM 2004, vol. 4, pp. 2275-2282.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.m Miscellaneous

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
      C.2.3 Network Operations
      C.2.5 Local and Wide-Area Networks
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Algorithms, Design, Management, Measurement

Keywords:
estimation, provisioning, traffic engineering, traffic matrix, virtual private network (VPN)