Network Size Estimation Method Based Semantic Attraction
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [16]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Network size is the fundamental information of the distributed applications. Network size estimation methods must feature both high accuracy and adequate robustness in order to adapt to a large environment with a high node churn. Considering the fact that the existing network size estimation methods mainly focus on single optimization objective and fail to ensure accuracy and robustness simultaneously, a network size estimation method based semantic attraction—SEBSA is proposed in this paper. As the semantic information in SEBSA, hash values are hashed in real intervals by the peers’ identifies. The peers with adjacent hash values in SEBSA periodically exchange hash neighbors to attract the most adjacent peers in a hash space quickly. Meanwhile, every peer computes the average spacing among hash values of the hash neighbors to estimate network size. Theoretic analysis and experimental results reveal that compared with existing size estimation methods, SEBSA can provide accurate size estimation information quickly even in continually fluctuating network environment.

    Reference
    [1] Rowstron A, Druschel P. Pastry: Scalable, decentralied object location and routing for large-scale peer-to-peer systems. In: Proc. of the IFIP/ACM Int’l Conf. on Distributed Systems Platforms. 2001. 329-350. [doi: 10.1007/3-540-45518-3_18]
    [2] Stoica I, Morris R, Karger D, Kaashoek MF, Balakrishnan H. Chord: A scalable peer-to-peer lookup service for Internet applications. In: Proc. of the 2001 SIGCOMM Conf. New York: ACM Press, 2001,31(4):149-160. [doi: 10.1145/383059.383071]
    [3] Ganesh AJ, Kermarrec AM, Massoulié L. Peer-to-Peer membership management for gossip-based protocols. IEEE Trans. on Computers, 2003,52(2):139-149. [doi: 10.1109/TC.2003.1176982]
    [4] Baldoni R, Beraldi R, Quema V, Querzoni L, T-Piergiovanni S. TERA: Topic-Based event routing for peer-to-peer architectures. In: Proc. of the 2007 Inaugural Int’l Conf. on Distributed Event-Based Systems. New York: ACM Press, 2007. [doi: 10.1145/1266894. 1266898]
    [5] Jelasity M, Montresor A. Epidemic-Style proactive aggregation in large overlay networks. In: Proc. of the Int’l Conf. on Distributed Computing Systems. 2004. 102-109. [doi: 10.1109/ICDCS.2004.1281573]
    [6] Bawa M, G-Molina H, Gionis A, Motwani R. Estimating aggregates on a peer-to-peer network. Technical Report, Technical Department of Computer Science, Stanford University, 2003.
    [7] Flajolet P, Martin GN. Probabilistic counting algorithms for data base applications. Journal of Computer and System Sciences, 1985,31(2):182-209. [doi: 10.1016/0022-0000(85)90041-8]
    [8] Kennedy O, Koch C, Demers A. Dynamic approaches to in-network aggregation. In: Proc. of the IEEE 25th Int’l Conf. on Data Engineering. 2009. 1331-1334. [doi: 10.1109/ICDE.2009.233]
    [9] Massoulié L, Le Merrer E, Kermarrec AM, Ganesh A. Peer counting and sampling in overlay networks: Random walk methods. In: Proc. of the 25th Annual ACM Symp. on Principles of Distributed Computing. ACM Press, 2006. 123-132. [doi: 10.1145/1146381. 1146402]
    [10] Kostoulas D, Psaltoulis D, Gupta I, Birman K, Demers A. Decentralized schemes for size estimation in large and dynamic groups. In: Proc. of the 4th IEEE Int’l Symp. on Network Computing and Applications. 2005. 41-48. [doi: 10.1109/NCA.2005.15]
    [11] Cardoso JCS, Baquero C, Almeida PS. Probabilistic estimation of network size and diameter. In: Proc. of the 4th Latin- American Symp. on Dependable Computing. 2009. 33-40. [doi: 10.1109/LADC.2009.19]
    [12] Shafaat TM, Ghodsi A, Haridi S. A practical approach to network size estimation for structured overlays. In: Proc. of the IWSOS 2008. 2008. 71-83. [doi: 10.1007/978-3-540-92157-8_7]
    [13] Voulgaris S, Gavidia D, Van Steen M. CYCLON: Inexpensive membership management for unstructured P2P overlays. Journal of Network and Systems Management, 2005,13(2):197-217. [doi: 10.1007/s10922-005-4441-x]
    [14] Russo RP, Rothmann MD. Maximal divergent uniform spacings. Stochastic Processes and their Applications, 1989,33(1): 175-183. [doi: 10.1016/0304-4149(89)90074-4]
    [15] Peersim. http://peersim.sourceforge.net
    [16] Van Renesse RV, Minsky Y, Hayden M. A gossip-style failure detection service. In: Proc. of the Middleware’98. 1998.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

马行空,王意洁,郑重.一种基于语义吸引的节点规模估计方法.软件学报,2012,23(3):662-676

Copy
Share
Article Metrics
  • Abstract:4160
  • PDF: 5008
  • HTML: 0
  • Cited by: 0
History
  • Received:May 30,2010
  • Revised:January 20,2011
  • Online: March 05,2012
You are the first2043804Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063