Link Stress Reduction against Bursty Arrivals of Content Requests

Kenichi Yamashita, Kazumasa Oida

Department of Computer Science and Engineering, Fukuoka Institute of Technology, Wajiro-Higashi, Fukuoka, Japan.

DOI: 10.4236/ijcns.2012.55036                

Abstract

Content delivery networks are designed to extend the end-to-end transport capability of the Internet to cope with increases in video traffic. For further improvement, bursty request arrivals should be efficiently addressed. As opposed to previous approaches, in which the best client-server pair is individually selected (individual optimization), this paper proposes an algorithm for dealing with simultaneous arrival requests, in which client-server pairs are selected such that all requests receive good service (social optimization). The performance of the proposed algorithm is compared with that of the closest algorithm, an individual optimization algorithm, under the condition that a large number of requests arrive simultaneously. The evaluation criterion is the worst link stress, which is the largest number of streams per link. The numerical results show that the proposed algorithm is effective for large-scale networks and that the closest algorithm does not provide near-optimal solutions, especially when all requests arrive in a small part of the network or when there are many servers.

Keywords

Social Optimization; Content Delivery; Hypercube Overlay; Server Assignment; Link Stress

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	“Cisco Visual Networking Index: Forecast and Methodology, 2009-2014,” 2012. http://www.slideshare.net/jimkaskade/cisco-visual-networking-index-forecast-and-methodology-200914
[2]	N. Ramzan, E. Quacchio, T. Zgaljic and F. Rovati, “Peer-to-Peer Streaming of scalable video in Future Internet Applications,” IEEE Communications Magazine, Vol. 49, No. 1, 2011, pp. 128-135. doi:10.1109/MCOM.2011.5723810
[3]	K. Pussep, S. Oechsner, O. Abboud, M. Kantor and B. Stiller, “Impact of Self-Organization in Peer-to-Peer Overlays on Underlay Utilization,” 4th International Conference on Internet and Web Applications and Services, Venice, 24-28 May 2009, pp. 84-89. doi:10.1109/ICIW.2009.20
[4]	PPlive Website, 2011. http://www.pplive.com/
[5]	Zattoo Website, 2011. http://www.zattoo.com/
[6]	O. Abboud, K. Pussep, K. Mohr, A. Kovacevic, S. Kaune and R. Steinmetz, “Enabling Resilient P2P Video Streaming: Survey and Analysis,” Multimedia Systems, Vol. 17, No. 3, 2011, pp. 177-197. doi:10.1007/s00530-011-0229-x
[7]	S. Tonnies, B. Kohncke, P. Hennig, I. Brunkhorst and Wolf-Tilo Balke, “A Service Oriented Architecture for Personalized Universal Media Access,” Future Internet, Vol. 3, No. 2, 2011, pp. 87-116. doi:10.3390/fi3020087
[8]	R. Buyya, M. Pathan and A. Vakali, “Content Delivery Networks,” 1st Edition, Springer Publishing Company, Incorporated, Berlin, 2008. doi:10.1007/978-3-540-77887-5
[9]	S. Tarkoma, “Overlay Networks,” CRC Press, London, 2010. doi:10.1201/9781439813737
[10]	C. G. Plaxton, R. Rajaraman and A. W. Richa, “Accessing Nearby Copies of Replicated Objects in a Distributed Environment,” Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, New York, 22-25 June 1997, pp. 311-320.
[11]	I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek and H. Balakrishnan, “Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications,” IEEE/ACM Transactions on Networking, Vol. 11, No. 1, 2003, pp. 17-32. doi:10.1109/TNET.2002.808407
[12]	A. Rowstron and P. Druschel, “Pastry: Scalable, Decentralized Object Location and Routing for Large-Scale Peer-to-Peer Systems,” Proceedings of the 18th IFIP/ ACM International Conference on Distributed Systems Platforms, Heidelberg, 12-16 November 2001, pp. 329-350.
[13]	B. Y. Zhao, J. Kubiatowicz and A. D. Joseph, “Tapestry: An Infrastructure for Fault-tolerant Wide-Area Location and Routing,” Computer Science Division (EECS), University of California, Oakland, 2001.
[14]	E. Anceaume, F. Brasileiro, R. Ludinard and A. Ravoaja, “PeerCube: A Hypercube-Based P2P Overlay Robust against Collusion and Churn,” 2nd IEEE International Conference on Self-Adaptive and Self-Organizing Systems, Ann Arbor, 3-7 October 2008, pp. 15-24. doi:10.1109/SASO.2008.44
[15]	S. C. Han and Y. Xia, “Network Load-Aware Content Distribution in Overlay Networks,” Computer Communications, Vol. 32, 2009, pp. 51-61. doi:10.1016/j.comcom.2008.09.021
[16]	A. Shaikh, R. Tewari and M. Agrawal, “On the Effectiveness of DNS-Based Server Selection,” Proceedings of IEEE INFOCOM 2001 20th Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, Vol. 3, 22-26 April 2001, pp. 1801-1810.
[17]	S. Ratnasamy, M. Handley, R. M. Karp and S. Shenker, “Topologically-Aware Overlay Construction and Server Selection,” 21st Annual Joint Conference of the IEEE Computer and Communications Societies, New York, Vol. 3, 23-27 June 2002, pp. 1190-1199.
[18]	M. Hofmann and L. R. Beaumont, “Content Networking: Architecture, Protocols, and Practice,” Morgan Kaufmann Publishers, San Francisco, 2005, pp. 129-134.
[19]	C. M. Chen, Y. Ling, M. Pang, W. Chen, S. Cai, Y. Suwa and O. Altintas, “Scalable Request-Routing with Next-Neighbor Load Sharing in Multi-Server Environments,” Proceedings of the 19th International Conference on Advanced Information Networking and Applications, IEEE Computer Society, Washington, DC, 28-30 March 2005, pp. 441-446.
[20]	C. E. Bell and S. Stidham Jr., “Individual versus Social Optimization in the Allocation of Customers to Alternative Servers,” Management Science, Vol. 29, No. 7, 1983, pp. 831-839. doi:10.1287/mnsc.29.7.831
[21]	S. Shenker and A. Weinrib, “The Optimal Control of Heterogeneous Queueing Systems: A Paradigm for LoadSharing and Routing,” IEEE Transactions on Computers, Vol. 38, 1989, pp. 1724-1735. doi:10.1109/12.40850
[22]	K. Oida and S. Saito, “A Packet-Size Aware Adaptive Routing Algorithm for Parallel Transmission Server Systems,” Journal of Parallel and Distributed Computing, Vol. 64, No. 1, 2004, pp. 36-47. doi:10.1016/j.jpdc.2003.07.008
[23]	F. T. Leighton, “Introduction to Parallel Algorithms and Archtectures: Arrays, Trees, Hypercubes,” Morgan Kaufmann Publishers, Waltham, 1992.
[24]	Y. Saad and M. Schultz, “Topological Properties of Hypercubes,” IEEE Transactions on Computers, Vol. 37, No. 7, 1988, pp. 867-872. doi:10.1109/12.2234
[25]	T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, “Introduction to Algorithms,” 3rd Edition, The MIT Press, Cambridge, 2001.