Optimizing cluster formation in super-peer networks via local incentive design

详细信息    查看全文

• 作者：Aditya Kurve (1)
  Christopher Griffin (2)
  David J. Miller (1)
  George Kesidis (1) (3)
  
• 关键词：Super ; peers ; Game theory ; Optimization ; Graph partitioning ; Self ; organizing networks
• 刊名：Peer-to-Peer Networking and Applications
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：8
• 期：1
• 页码：1-21
• 全文大小：2,040 KB
• 参考文献：1. Freenet. http://freenet.sourceforge.net. Accessed 09 Apr 2013
  2. Gnutella. http://www.gnutella.com. Accessed 09 Apr 2013
  3. Kazaa. http://www.kazaa.com. Accessed 09 Apr 2013
  4. Skype. http://www.skype.com. Accessed 09 Apr 2013
  5. Beverly Yang B, Garcia-Molina H (2003) Designing a super-peer network. In: Proceeding 19th IEEE international conference on data engineering, pp 49鈥?0
  6. Busnel Y, Kermarrec A (2007) Proxsem: Interest-based proximity measure to improve search efficiency in p2p systems. In: Proceeding fourth IEEE European conference on universal multiservice networks, ECUMN鈥?7, pp 62鈥?4
  7. Cramton P, Shoham Y, Steinberg R (2006) Combinatorial auctions. MIT Press, Cambridge
  8. Crespo A, Garcia-Molina H (2005) Semantic overlay networks for p2p systems. In: Agents and peer-to-peer computing. Springer, Berlin Heidelberg, pp 1鈥?3 CrossRef
  9. Doulkeridis C, Vlachou A, N酶rv氓g K, Kotidis Y, Vazirgiannis M (2010) Efficient search based on content similarity over self-organizing p2p networks. Peer-to-peer Netw Appl 3(1):67鈥?9 CrossRef
  10. Doulkeridis C, Vlachou A, N酶rv氓g K, Vazirgiannis M (2010) Distributed semantic overlay networks. In: Handbook of peer-to-peer networking. Springer, New York, pp 463鈥?94 CrossRef
  11. Feldman M, Lai K, Stoica I, Chuang J (2004) Robust incentive techniques for peer-to-peer networks. In: Proceedings of the 5th ACM conference on electronic commerce. ACM, New York, pp 102鈥?11 CrossRef
  12. Garbacki P, Epema D, van Steen M (2008) Broker-placement in latency-aware peer-to-peer networks. Comput Netw 52(8):1617鈥?633 CrossRef
  13. Garbacki P, Epema D, Van Steen M (2010) The design and evaluation of a self-organizing superpeer network. IEEE Trans Comput 59(3):317鈥?31 CrossRef
  14. Garey M, Johnson D (1979) Computers and intractability. Freeman, San Francisco
  15. Goldschlag D, Reed M, Syverson P (1999) Onion routing. Commun ACM 42(2):39鈥?1 CrossRef
  16. Karger D, Ruhl M (2004) Simple efficient load balancing algorithms for peer-to-peer systems. In: Proceeding 16th annual ACM symposium on parallelism in algorithms and architectures, pp 36鈥?3
  17. Karypis G, Kumar V (1996) Parallel multilevel k-way partitioning scheme for irregular graphs. In: Proceeding 1996 ACM/IEEE conference on supercomputing
  18. Karypis G, Kumar V (1999) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J Sci Comput 20(1):359 CrossRef
  19. Kernighan B, Lin S (1970) An efficient heuristic procedure for partitioning graphs. Bell Syst Tech J 49(2):291鈥?07 CrossRef
  20. Kurve A, Kotobi K, Kesidis G (2013) An agent-based framework for performance modeling of an optimistic parallel discrete event simulator. newblock Complex Adaptive Systems Modeling (accepted)
  21. Lv Q, Ratnasamy S, Shenker S (2002) Can heterogeneity make gnutella scalable? In: peer-to-peer networks. Springer, Berlin Heidelberg, pp 94鈥?03
  22. Maymounkov P, Mazieres D (2002) Kademlia: A peer-to-peer information system based on the xor metric. In: peer-to-peer networks. Springer, Berlin Heidelberg, pp 53鈥?5
  23. Monderer D, Shapley L (1996) Potential games. Games Econ Behav 14:124鈥?43 CrossRef
  24. Nejdl W,Wolf B, Qu C, Decker S, Sintek M, Naeve A, Nilsson M, Palm茅r M, Risch T (2002) Edutella: A p2p networking infrastructure based on rdf. In: Proceeding of the 11th ACM international conference on world wide web. ACM, New York, pp 604鈥?15
  25. Nejdl W, Wolpers M, Siberski W, Schmitz C, Schlosser M, Brunkhorst I, L枚ser A (2003) Super-peer-based routing and clustering strategies for rdf-based peer-to-peer networks. In: Proceeding 12th ACM international conference on world wide web, pp 536鈥?43
  26. Pothen A (1997) Graph partitioning algorithms with applications to scientific computing. ICASE LaRC Interdiscip Ser Sci Eng 4:323鈥?68 CrossRef
  27. Ratnasamy S, Francis P, Handley M, Karp R, Shenker S (2001) A scalable content-addressable network. ACM SIGCOMM Comput Commun Rev 31(4):161鈥?72 CrossRef
  28. Saroiu S, Gummadi P, Gribble S (2002) A measurement study of peer-to-peer file sharing systems. In: Proceeding multimedia computing and networking, vol 2002, p 152
  29. Schlosser M, Condie T, Kamvar S (2003) Simulating a file-sharing p2p network. In: Proceeding 1st workshop on semantics in grid and P2P networks
  30. Sripanidkulchai K, Maggs B, Zhang H (2003) Efficient content location using interest-based locality in peer-to-peer systems. In: Proceeding IEEE INFOCOM , vol 3, pp 2166鈥?176
  31. Stoica I, Morris R, Karger D, Kaashoek M, Balakrishnan H (2001) Chord: A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Comput Commun Rev 31(4):149鈥?60 CrossRef
  32. Tirado J, Higuero D, Isaila F, Carretero J, Iamnitchi A (2010) Affinity p2p: A self-organizing content-based locality-aware collaborative peer-to-peer network. Comput Netw 54(12):2056鈥?070 CrossRef
  33. Tisue S, Wilensky U (2004) Netlogo: A simple environment for modeling complexity. In: Proceeding international conference on complex systems, pp 16鈥?1
  34. Van Den Bout D, Thomas Miller T III (1990) Graph partitioning using annealed neural networks. IEEE Trans Neural Netw 1(2):192鈥?03 CrossRef
  35. Voulgaris S, Kermarrec A, Massouli茅 L (2004) Exploiting semantic proximity in peer-to-peer content searching. In: Proceeding 10th IEEE international workshop on future trends of distributed computing systems, FTDCS, pp 238鈥?43
  
• 作者单位：Aditya Kurve (1)
  Christopher Griffin (2)
  David J. Miller (1)
  George Kesidis (1) (3)
  
  1. Department of Electrical Engineering, The Pennsylvania State University, University Park, PA, USA
  2. Applied Research Lab, The Pennsylvania State University, University Park, PA, USA
  3. Computer Science and Engineering, The Pennsylvania State University, University Park, PA, USA
  
• 刊物类别：Engineering
• 刊物主题：Communications Engineering and Networks
  Information Systems and Communication Service
  Computer Communication Networks
  
• 出版者：Springer New York
• ISSN：1936-6450

文摘

A super-peer based overlay network architecture for peer-to-peer (P2P) systems allows for some nodes, known as the super-peers, that are more resource-endowed than others, to assume a higher share of workload. Ordinary peers are connected to the super-peers and rely on them for their transactional needs. Many criteria for a peer to choose its super-peer have been explored, some of them based on physical proximity, semantic proximity, or by purely random choice. In this paper, we propose an incentive-based criterion that uses semantic similarities between the content interests of the peers and, at the same time, encourages even load distribution across the super-peers. The incentive is achieved via a game theoretic framework that considers each peer as a rational player, allowing stable Nash equilibria to exist and hence guarantees a fixed point in the strategy space of the peers. This guarantees convergence (assuming static network parameters) to a locally optimal assignment of peers to super-peers with respect to a global cost that approximates the average query resolution time. We also show empirically that the local cost framework that we employ performs closely to (and in some cases better than) a similar scheme based on the formulation of a centralized cost function that requires the peers to know an additional global parameter.