Email this article Effective Resource Allocation in flexible Overlay Routing
Abstract
Overlay routing is the very attractive scheme that allows the improving certain properties of the routing 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 paper, we rigorously study this optimization problem. We show that it is NP- of the problem at hand. We examine the practical aspects of the scheme by evaluating the gain one can get over several hard and derive a nontrivial approximation algorithm for it, where the approximation ratio depends on specific properties 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.
Keywords
References
H. Pucha and Y. C. Hu, “Overlay TCP: Multi-hop overlay transportfor high throughput transfers in the Internet,” Purdue University, WestLafayette, IN, USA, Tech. Rep., 2005.
D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris, “Resilientoverlay 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 andtransport,” 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, “Theend-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 performanceover 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 impactof routing policy on Internet paths,” in Proc. IEEE INFOCOM,2001, pp. 736–742.
Refbacks
- There are currently no refbacks.
Copyright © 2013, All rights reserved.| ijseat.com
International Journal of Science Engineering and Advance Technology is licensed under a Creative Commons Attribution 3.0 Unported License.Based on a work at IJSEat , Permissions beyond the scope of this license may be available at http://creativecommons.org/licenses/by/3.0/deed.en_GB.