Cost-Effective Resource Allocation of Overlay Routing Relay Nodes
Keywords:
Autonomous Systems, Voice-over-IP, Round-Trip Time (RTT), Overlay Routing Resource Allocation (ORRA), Voice-over-IP(VoIP), Overlay Router, BGP Router, Virtual Private Network (VPN)Abstract
Overlay routing is a very attractive scheme that allows improving certain properties of the routing (such as delay or TCP throughput) without the need to change the standards of the current underlying routing. However, deploying overlay routing requires the placement and maintenance of overlay infrastructure. This gives rise to the following optimization problem: Find a minimal set of overlay nodes such that the required routing properties are satisfied. In this research paper, we rigorously study this optimization problem. We show that it is NP-hard and derive a nontrivial approximation algorithm for it, where the approximation ratio depends on specific properties of the problem at hand. We examine the practical aspects of the scheme by evaluating the gain one can get over several real scenarios. The first one is BGP routing, and we show, using up-to-date data reflecting the current BGP routing policy in the Internet, that a relative small number of less than 100 relay servers is sufficient to enable routing over shortest paths from a single source to all autonomous systems (ASs), reducing the average path length of inflated paths by 40%. We also demonstrate that the scheme is very useful for TCP performance improvement (results in an almost optimal placement of overlay nodes) and for Voice-over-IP (VoIP) applications where a small number of overlay nodes can significantly reduce the maximal peer-to-peer delay.
References
H. Pucha and Y. C. Hu, “Overlay TCP: Multi-hop overlay transport for high throughput transfers in the Internet,” Purdue University, West Lafayette, IN, USA, Tech. Rep., 2005.
D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris, “Resilient overlay networks,” in Proc. 18th ACM SOSP, 2001, pp. 131–145.
S. Savage, T. A. A. Aggarawl, T. Anderson, A. Aggarwal, D. Becker, N. Cardwell, A. Collins, E. Hoffman, J. Snell, A. Vahdat, G. Voelker, and J. Zahorjan, “Detour: A case for informed internet routing and transport,” IEEE Micro, vol. 19, no. 1, pp. 50–59, Jan.–Feb. 1999.
R. Cohen and A. Shochot, “The “global-ISP” paradigm,” Comput. Netw., vol. 51, no. 8, pp. 1908–1921, 2007.
L. Gao and F. Wang, “The extent of as path inflation by routing policies,” in Proc. IEEE GLOBECOM, 2002, vol. 3, pp. 2180–2184.
S. Savage, A. Collins, E. Hoffman, J. Snell, and T. Anderson, “The end-to-end effects of Internet path selection,” in Proc. ACM SIGCOMM, 1999, pp. 289–299.
R. Cohen and S. Ramanathan, “Using proxies to enhance TCP performance over hybrid fiber coaxial networks,” Comput. Commun, vol. 20, no. 16, pp. 1502–1518, Jan. 1998.
N. Spring, R. Mahajan, and T. Anderson, “The causes of path inflation,” in Proc. ACM SIGCOMM, 2003, pp. 113–124.
H. Tangmunarunkit, R. Govindan, S. Shenker, and D. Estrin, “The impact of routing policy on Internet paths,” in Proc. IEEE INFOCOM, 2001, pp. 736–742.
M. Cha, S. Moon, C.-D. Park, and A. Shaikh, “Placing relay nodes for intra-domain path diversity,” in Proc. IEEE INFOCOM, Apr. 2006, pp. 1–12.
M. Kodialam, T. V. Lakshman, and S. Sengupta,“Efficient and robust routing of highly variable traffic,” in Proc. HotNets III, 2004.
S. Roy, H. Pucha, Z. Zhang, Y. C. Hu, and L. Qiu, “On the placement of infrastructure overlay nodes,” IEEE/ACM Trans. Netw., vol. 17, no. 4, pp. 1298–1311, Aug. 2009.
L. Qiu, V. N. Padmanabhan, and G. M. Voelker “On the placement of Web server replicas,” in Proc. IEEE INFOCOM, 2001, vol. 3, pp. 1587–1596.
E. Cronin, S. Jamin, C. Jin, A. R. Kurc, D. Raz, and Y. Shavitt, “Constrained mirror placement on the Internet,” in Proc. IEEE INFOCOM, 2001, vol. 1, pp. 31–40.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA, USA: Freeman, 1979.
U. Feige, “A threshold of ln n for approximating set cover,” J. ACM, vol. 45, no. 4, pp. 634–652, 1998.
R. Bar-Yehuda and S. Even, “A local-ratio theorem for approximating the weighted vertex cover problem,” Ann. Discrete Math., vol. 25, pp. 27–46, 1985.
Y. Rekhter, T. Watson, and T. Li, “Border gateway protocol 4,” RFC 1771, 1995.
C. Alaettinoglu, “Scalable router configuration for the Internet,” in Proc. IEEE IC3N, Oct. 1996.
G. Huston, “Interconnection, peering and settlement,” Internet Protocol J., vol. 2, no. 1, Mar. 1999.
L. Gao and J. Rexford, “Stable Internet routing without global coordination,” IEEE/ACM Trans. Netw., vol. 9, no. 6, pp. 681–692, Dec. 2001.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2016 COMPUSOFT: An International Journal of Advanced Computer Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
©2023. COMPUSOFT: AN INTERNATIONAL OF ADVANCED COMPUTER TECHNOLOGY by COMPUSOFT PUBLICATION is licensed under a Creative Commons Attribution 4.0 International License. Based on a work at COMPUSOFT: AN INTERNATIONAL OF ADVANCED COMPUTER TECHNOLOGY. Permissions beyond the scope of this license may be available at Creative Commons Attribution 4.0 International Public License.
