Optimal decomposition of P2P networks based on file exchange patterns for multimedia content search & replication

ABSTRACT

In this paper, we address the issues of multimedia content search and replication over peer-to peer networks. We use the concept of semantic proximity that exploits the file exchange patterns exhibited among peer users so as to decompose the network into semantic clusters. Peer nodes are then decomposed into semantic clusters so that a) the probability that a node locates content within its own cluster is maximized, while simultaneously b) the respective probability of finding this content outside this cluster is minimized The semantic organization is then used for applying efficient cluster-based content replication strategies. Two different schemes are examined; the unrestricted and the restricted approach. The first one distributes multimedia content within peers of a cluster so that the average hop distance among nodes and objects weighted by the object popularity is minimized. This approach takes into account no Quality of Service (QoS) guarantees. Instead, the second scheme iteratively partitions the nodes of a cluster during each object replication based on a QoS violation criterion. The proposed algorithms are experimentally evaluated and compared with other approaches to demonstrate the efficacy of the proposed schemes.

REFERENCES

• 1: Karl Aberer , Magdalena Punceva , Manfred Hauswirth , Roman Schmidt, Improving Data Access in P2P Systems, IEEE Internet Computing, v.6 n.1, p.58-67, January 2002 [doi>10.1109/4236.978370]
• 2: R. Albert and A. L. Barabasi, "Statistical mechanics of complex networks," Reviews of modern physics, Vol 14, pp. 47--97, Jan 2002.
• 3: F. R. Bach and M. I. Jordan, "Learning Spectral Clustering," Advances in Neural Information Processing Systems (NIPS) , Vancouver Canada, 2004.
• 4: F. R. Bach and M. I. Jordan, "Learning Spectral Clustering," Technical Report No. UCB/CSD-03-124, Berkeley, 2003.
• 5: Mayank Bawa , Gurmeet Singh Manku , Prabhakar Raghavan, SETS: search enhanced by topic segmentation, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860491]
• 6: Bong-Jun Ko , Dan Rubenstein, Distributed self-stabilizing placement of replicated resources in emerging networks, IEEE/ACM Transactions on Networking (TON), v.13 n.3, p.476-487, June 2005 [doi>10.1109/TNET.2005.850196]
• 7: Fang Chen , Vana Kalogeraki, Resource management and multimedia support in peer-to-peer systems, University of California, Riverside, 2005
• 8: Yatin Chawathe , Sylvia Ratnasamy , Lee Breslau , Nick Lanham , Scott Shenker, Making gnutella-like P2P systems scalable, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.864000]
• 9: I. Clarke, O. Sandberg, B. Wiley and T.W. Hong, "Freenet: A Distributed Anonymous Information Storage and Retrieval System," Workshop on Design Issues in Anonymity and Unobservability, pp. 311--320, 2000, CA.
• 10: E. Cohen, A. Fiat and H. Kaplan, "Associative Search in Peer To Peer Networks: Harnessing Latent Semantics," 22nd IEEE INFOCOM, Vol. 2, pp. 1261--1271, April. 2003.
• 11: Brian F. Cooper , Hector Garcia-Molina, SIL: a model for analyzing scalable peer-to-peer search networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.13, p.2380-2400, 15 September 2006 [doi>10.1016/j.comnet.2005.09.018]
• 12: N. Doulamis, A. Doulamis and T. Varvarigou, "Optimal Adaptive Relevance Feedback Algorithms for Interactive Multimedia Content Personalization," IEEE Multimedia Magazine, Vol. 10, No. 4, pp. 38--47, Oct-Nov 2003.
• 13: N. Doulamis, A. Doulamis, D. Kalogeras and S. Kollias, "Low bit Rate Coding of Image Sequence using Adaptive Regions of Interest," IEEE Tran. on CSVT, Vol. 8, No. 8, pp. 928--934, December 1998.
• 14: N. D. Doulamis, A. D. Doulamis, Y. Avrithis, K. Ntalianis and S. Kollias, "Efficient Summarization of Stereoscopic Video Sequences," IEEE Trans. on CSVT, Vol. 10, No. 4, pp. 501--517, June 2000.
• 15: A. Doulamis and N. Doulamis, "Optimal Content-based Video Decomposition for Interactive Video Navigation over IP-based Networks," IEEE Trans. on CSVT, Vol. 14, No. 6, pp. 757--775, June 2004.
• 16: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 17: Ronaldo A. Ferreira , Murali Krishna Ramanathan , Asad Awan , Ananth Grama , Suresh Jagannathan, Search with Probabilistic Guarantees in Unstructured Peer-to-Peer Networks, Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing, p.165-172, August 31-September 02, 2005 [doi>10.1109/P2P.2005.33]
• 18: S. B. Handurukande , A.-M. Kermarrec , F. Le Fessant , L. Massoulié, Exploiting semantic clustering in the eDonkey P2P network, Proceedings of the 11th workshop on ACM SIGOPS European workshop, September 19-22, 2004, Leuven, Belgium [doi>10.1145/1133572.1133612]
• 19: Dennis Heimbigner, Expressive and Efficient Peer-to-Peer Queries, Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS'05) - Track 9, p.302.2, January 03-06, 2005 [doi>10.1109/HICSS.2005.267]
• 20: W.J Jeon,. and K. Nahrstedt, "Peer-to-peer multimedia streaming and caching service," IEEE International Conference on Multimedia and Expo, Vol. 2, pp. 57--60, Aug. 2002.
• 21: Jin Li, "MutualCast: A Serverless Peer-to-Peer Multiparty Real-Time Audio Conferencing System," IEEE International Conference on Multimedia and Expo, pp. 602--605 July 2005.
• 22: Jérôme Lacan , Laurent Lancérica , Laurent Dairaine, When FEC Speed up Data Access in P2P Networks, Proceedings of the Joint International Workshops on Interactive Distributed Multimedia Systems and Protocols for Multimedia Systems: Protocols and Systems for Interactive Distributed Multimedia, p.26-36, November 26-29, 2002
• 23: L Lancerica, L. Dairaine and J. Lacan, "Evaluation of Content-Access QoS for Various Dissemination Strategies in Peer to Peer Networks," 11th IEEE Intern. Conf. on Networks, pp.337--342, Oct. 2003.
• 24: Y. Liu, X. Liu, L. Xiao, L.M Ni and X. Zhang, "Location-Aware Topology Matching in P2P Systems," 23rd IEEE INFOCOM, Vol. 4, pp.2220--2230, March 2004.
• 25: I. Nakic and K. Veselic, "Wielandt and Ky-Fan Theorem for Matrix Pairs," Linear Algebra and its Applications, Vol. 369, No. 17, pp.77--73, August 2003.
• 26: Andy Oram, Peer-to-Peer: Harnessing the Power of Disruptive Technologies, O'Reilly & Associates, Inc., Sebastopol, CA, 2001
• 27: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 28: Daniel Schlosser , Tobias Hossfeld , Kurt Tutschku, Comparison of Robust Cooperation Strategies for P2P Content Distribution Networks with Multiple Source Download, Proceedings of the Sixth IEEE International Conference on Peer-to-Peer Computing, p.31-38, September 06-June 08, 2006 [doi>10.1109/P2P.2006.9]
• 29: K. Sripanidkulchai, B. Maggs and H. Zhang, "Efficient Content Location Using Interest-Based Locality in Peer-to-Peer Systems,"22nd IEEE INFOCOM, Vol. 3, pp. 2166--2176, Apr. 2003.
• 30: Hakim Weatherspoon , John Kubiatowicz, Erasure Coding Vs. Replication: A Quantitative Comparison, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.328-338, March 07-08, 2002
• 31: Zhe Xiang, Qian Zhang, Wenwu Zhu, Zhensheng Zhang, and Ya-Qin Zhang, "Peer to Peer Based Multimedia Distribution Service," IEEE Trans. on Multimedia, Vol. 6, No. 2, pp. 343--355, April 2004.
• 32: R. Zhang and Y.C. Hu, "Assisted Peer-to-Peer Search with Partial Indexing," 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Vol. 3, pp. 1514--1525, 2005.
• 33: J. Zhang, L. Liu and C.Pu, "Constructing a Proximity-Aware Power Law Overlay Network", In Proc. of Global Telecommunications Conference (GLOBECOM), Vol.2, 2005.
• 34: Yingwu Zhu , Yiming Hu, Efficient, Proximity-Aware Load Balancing for Structured P2P Systems, Proceedings of the 3rd International Conference on Peer-to-Peer Computing, p.220, September 01-03, 2003
• 35: {Online} Available: http://www.akamai.com/
• 36: {Online} Available: http://www.gnutella2.com
• 37: {Online} Available: http://www.gnutella.wego.com/

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.0 GENERAL

General Terms:
Algorithms, Design, Performance

Keywords:
clustering, content replication, content search, multimedia, peer-to-peer