Efficient and robust streaming provisioning in VPNs

ABSTRACT

Today, most large companies maintain virtual private networks (VPNs) to connect their remote locations into a single secure network. VPNs can be quite large covering more than 1000 locations and in most cases use standard Internet protocols and services. Such VPNs are implemented using a diverse set of technologies such as Frame Relay, MPLS, or IPSEC to achieve the goal of privacy and performance isolation from the public Internet.Using VPNs to distribute live content has recently received tremendous interest. For example, a VPN could be used to broadcast a CEO-employee town hall meeting. To distribute this type of content economically without overloading the network, the deployment of streaming caches or splitters is most likely required.In this paper, we address the problem of optimally placing such streaming splitters or caches to broadcast to a given set of VPN endpoints under the constraints typically found within a VPN. In particular, we introduce an efficient algorithm with complexity O(V), V being the number of routers in the VPN. This guarantees the optimal cache placement if interception is used for redirection. We prove that the general problem is NP-hard and introduce multiple heuristics for efficient and robust cache placement suitable under different constraints. At the expense of increased implementation complexity, each heuristic solution provides additional saving in the number of caches required. We evaluate proposed solutions using extensive simulations. In particular, we show our flow-based solution is very close to the optimal.

REFERENCES

• 1: GT-ITM: Georgia Tech Internetwork Topology Models. http://www.cc.gatech.edu/projects/gtitm/.
• 2: A. Barbir, B. Cain, F. Douglis, M. Green, M. Hofmann, R. Nair, D. Potter, and O. Spatscheck. Known CN Request-Routing Mechanisms.
• 3: M. Cieslak, D. Forster, G. Tiwana, and R. Wilson. Web Cache Coordination Protocol V2.0. http://www.wrec.org/Drafts/draft-wilson-wrec-wccp-v2-00. txt.
• 4: Michael R. Garey and David S. Johnson. Computers and Intractability. W. H. Freeman and Company, 1979.
• 5: Sugih Jamin, Cheng Jin, Anthony Kurc, Yuval Shavitt, and Danny Raz. Constrained Mirror Placement on the Internet. In Proceedings of IEEE Infocom, April 2001.
• 6: J. Kangasharju, J. W. Roberts, and K. W. Ross. Object replication strategies in content distribution networks. In 6th International Web Content Caching and Distribution Workshop, June 2001.
• 7: Magnus Karlsson, Christos Karamaolis, and Mallik Mahalingam. A framework for evaluating replica placement algorithms. http://www.hpl.hp.com/personal/Magnus_Karlsson/papers/rp_ framework.pdf, 2002.
• 8: Magnus Karlsson and Mallik Mahalingam. Do We Need Replica Placement Algorithms in Content Delivery Networks? In Proceedings of 7th International Web Content Caching and Distribution Workshop, August 2002.
• 9: Donald E. Knuth. The Stanford GraphBase. Addison-Wesley, 1993.
• 10: Balachander Krishnamurthy , Craig Wills , Yin Zhang, On the use and performance of content distribution networks, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505224]
• 11: Bo Li , Xin Deng , Mordecai J. Golin , Kazem Sohraby, On the Optimal Placement of Web Proxies in the Internet: The Linear Topology, Proceedings of the IFIP TC-6 Eigth International Conference on High Performance Networking, p.485-495, September 21-25, 1998
• 12: Lili Qiu, Venkata N. Padmanabhan, and Geoffrey M. Voelker. On the Placement of Web Server Replicas. In Proceedings of INFOCOM, April 2001.
• 13: Sherlia Shi and Jonathan Turner. Placing servers in overlay networks. In Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPETS), July 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Client/server

General Terms:
Algorithms, Performance, Reliability

Keywords:
VPNs, streaming server placement