On the placement of infrastructure overlay nodes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the placement of infrastructure overlay nodes

Full text

Pdf (690 KB)

Source

IEEE/ACM Transactions on Networking (TON) archive
Volume 17 , Issue 4 (August 2009) table of contents

Pages 1298-1311

Year of Publication: 2009

ISSN:1063-6692

Authors

Sabyasachi Roy	School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN
Himabindu Pucha	School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN
Zheng Zhang	School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN
Y. Charlie Hu	School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN
Lili Qiu	Department of Computer Science, University of Texas at Austin, Austin, TX

Publisher

IEEE Press Piscataway, NJ, USA

Bibliometrics

Downloads (6 Weeks): 38, Downloads (12 Months): 38, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1109/TNET.2008.2007433

ABSTRACT

Overlay routing has emerged as a promising approach to improving performance and reliability of Internet paths. To fully realize the potential of overlay routing under the constraints of deployment costs in terms of hardware, network connectivity and human effort, it is critical to carefully place infrastructure overlay nodes to balance the tradeoff between performance and resource constraints. In this paper, we investigate approaches to perform intelligent placement of overlay nodes to facilitate (i) resilient routing and (ii) TCP performance improvement. We formulate objective functions to capture application behavior: reliability and TCP performance, and develop several placement algorithms, which offer a wide range of tradeoffs in complexity and required knowledge of the client-server location and traffic load. Using simulations on synthetic and real Internet topologies, and PlanetLab experiments, we demonstrate the effectiveness of the placement algorithms and objective functions developed, respectively. We conclude that a hybrid approach combining greedy and random approaches provides the best tradeoff between computational efficiency and accuracy. We also uncover the fundamental challenge in simultaneously optimizing for reliability and TCP performance, and propose a simple unified algorithm to achieve both.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Stefan Savage , Thomas Anderson , Amit Aggarwal , David Becker , Neal Cardwell , Andy Collins , Eric Hoffman , John Snell , Amin Vahdat , Geoff Voelker , John Zahorjan, Detour: Informed Internet Routing and Transport, IEEE Micro, v.19 n.1, p.50-59, January 1999 [doi>10.1109/40.748796]
	2	David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
	3	Y. Liu, Y. Gu, H. Zhang, W. Gong, and D. Towsley, "Application level relay for high-bandwidth data transport," in Proc. GridNets, 2004.
	4	H. Pucha and Y. C. Hu, "Slot: Shortened Loop overlay Transport," Purdue Univ., West Lafayette, IN, TR-ECE-05-12, Jul. 2005.
	5	T. Fei, S. Tao, L. Gao, and R. Guerin, "How to select a good alternate path in large peer-to-peer systems?," in Proc. IEEE INFOCOM, 2006.
	6	P. Krishnan , Danny Raz , Yuval Shavitt, The cache location problem, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.568-582, Oct. 2000 [doi>10.1109/90.879344]
	7	P. Radoslavov, R. Govindan, and D. Estrin, "Topology-informed internet replica placement," in Proc. WCW, 2001.
	8	L. Qiu, V. N. Padmanabhan, and G. M. Voelker, "On the placement of web server replicas," in Proc. IEEE INFOCOM, 2001.
	9	S. Jamin, C. Jin, A. R. Kurc, D. Raz, and Y. Shavitt, "Constrained mirror placement on the internet," in Proc. IEEE INFOCOM, 2001.
	10	J. Xu, B. Li, and D. Lee, "Placement problems for transparent data replication proxy services," IEEE J. Sel. Areas Commun., vol. 20, no. 7, pp. 1383-1398, Jul. 2002.
	11	E. Cronin, S. Jamin, C. Jin, A. R. Kurc, D. Raz, and Y. Shavitt, "Constrained mirror placement on the Internet," IEEE J. Sel. Areas Commun., vol. 20, no. 7, pp. 1369-1382, Jul. 2002.
	12	M. Karlsson and M. Mahalingam, "Do we need replica placement algorithms in content delivery networks," in Proc. WCW, 2002.
	13	S. Shi and J. Turner, "Placing servers in overlay networks," in Proc. SPECTS, 2002.
	14	B. Li, M. J. Golin, G. F. Italiano, X. Deng, and K. Sohraby, "On the optimal placement of web proxies in the internet," in Proc. IEEE INFOCOM , 1999.
	15	Krishna P. Gummadi , Harsha V. Madhyastha , Steven D. Gribble , Henry M. Levy , David Wetherall, Improving the reliability of internet paths with one-hop source routing, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.13-13, December 06-08, 2004, San Francisco, CA
	16	J. Han, D. Watson, and F. Jahanian, "Topology aware overlay networks,"in Proc. IEEE INFOCOM, 2005.
	17	Sumi Choi , Yuval Shavitt, Proxy Location Problems and Their Generalizations, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.898, May 19-22, 2003
	18	Min-You Wu , Yan Zhu , Wei Shu, Placement of proxy-based multicast overlays, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.48 n.4, p.627-655, 15 July 2005 [doi>10.1016/j.comnet.2004.11.019]
	19	V. Padmanabhan, L. Qiu, and H. Wang, "Server-based inference of internet link lossiness," in Proc. IEEE INFOCOM, 2003.
	20	Jitendra Padhye , Victor Firoiu , Don Towsley , Jim Kurose, Modeling TCP throughput: a simple model and its empirical validation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.303-314, August 31-September 04, 1998, Vancouver, British Columbia, Canada
	21	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	22	S. Roy, H. Pucha, Z. Zhang, Y. C. Hu, and L. Qiu, "Overlay node placement: analysis, algorithms and impact on applications," Purdue Univ., West Lafayette, IN, TR-ECE-07-11, Jan. 2007.
	23	K. Calvert and E. Zegura, Internetwork Topology Models (gt-itm). [Online]. Available: http://www.cc.gatech.edu/fac/Ellen.Zegura/gt-itm
	24	Hyunseok Chang , Ramesh Govindan , Sugih Jamin , Scott J. Shenker , Walter Willinger, Towards capturing representative AS-level Internet topologies, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
	25	L. Peterson, T. Anderson, D. Culler, and T. Roscoe, "A blueprint for introducing disruptive technology into the internet," in Proc. ACM Hot-Nets , 2002.
	26	Chun Zhanga , Jim Kurosea , Don Towsley , Zihui Ge , Yong Liu, Optimal Routing with Multiple Traffic Matrices Tradeoff between Average andWorst Case Performance, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.215-224, November 06-09, 2005 [doi>10.1109/ICNP.2005.30]
	27	C. Zhang, Y. Liu, W. Gong, J. Kurose, R. Moll, and D. Towsley, "On optimal routing with multiple traffic matrices," in Proc. IEEE INFOCOM, 2005.
	28	Balachander Krishnamurthy , Jia Wang, On network-aware clustering of Web clients, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.97-110, August 28-September 01, 2000, Stockholm, Sweden