微信服务号

微信订阅号

2025年3月24日 9:44 星期一
首页 > 过刊浏览>2009年第20卷第6期 >1574-1590
PDF HTML阅读 XML下载 导出引用 引用提醒
网络距离预测技术研究
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant Nos.60621003, 60873215 (国家自然科学基金); the National Basic Research Program of China under Grant No.2005CB321801 (国家重点基础研究发展计划(973)); the Foundation for the Author of National Excellent Doctoral Dissertation of China under Grant No.200141 (高等学校全国优秀博士学位论文作者专项)


Network Distance Prediction Technology Research
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [65]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    P2P网络中节点间的距离信息是实现拓扑感知以优化覆盖网应用以及解决网络监管等问题的基础. P2P网络的大规模、自组织、高度动态等复杂特征使得要准确、完全地测量节点间的距离信息面临着极大的困难.因此,研究者们提出各种预测技术,目前对网络距离预测技术的研究已成为P2P领域的研究热点.首先,提出了一个网络距离预测技术的研究框架,指出了研究的重点以及相关技术问题,分析了研究历史;其次,对各种预测方法加以分类,在分类的基础上,介绍了各种典型的预测方法并进行了对比分析;最后总结了各种精确性度量标准,并指出了未来的研究

    Abstract:

    The distance information between nodes in P2P network is the basis for achieving topology-awareness which aims at optimizing the applications of overlay and solving the problems such as network monitoring. However, it seems infeasible to accurately and completely measure the distances between nodes due to the characteristics of P2P, such as being large-scale, self-organized, highly dynamic and so on. Consequently, researchers have put forward various prediction methods, and currently the network distance prediction technology is emerging as a new hotspot of research in P2P area. Firstly, a research framework is proposed, based on which the main aspects and the related technical issues of the research are analyzed. Meanwhile, the research history and the analysis of the classification are investigated. Many typical methods are introduced and compared. Lastly, the metrics of precision, as well as future research trends of network distance prediction is reviewed.

    参考文献
    [1] Kubiatowicz J, Bindel D, Chen Y, Czerwinski S, Eaton P, Geels D, Gummadi R, Rhea S, Weatherspoon H, Weimer W, Zhao B. OceanStore: An architecture for global-scale persistent storage. ACM SIGPLAN Notices, 2000,35(11):190-201.
    [2] Maymounkov P, Mazieres D. Kademlia: A peer-to-peer information system based on the XOR metric. In: Proc. of the 1st Int'l Workshop on Peer-to-Peer Systems (IPTPS 2002). Berlin: Springer-Verlag, 2002. 53-65.
    [3] Castro M, Druschel P, Kermarrec A M, Nandi A. SplitStream: High-Bandwidth content distribution in a cooperative environment. In: Proc. of the 19th ACM Symp. on Operating Systems Principles (SOSP 2003). New York: ACM Press, 2003.
    [4] Hefeeda M, Habib A, Botev B, Xu D, Bhargava B. PROMISE: Peer-to-Peer media streaming using CollectCast. In: Proc. of the 11th ACM Int'l Conf. on Multimedia. 2003. 45-54. http://www.cs.sfu.ca/～mhefeeda/Papers/mm03.pdf
    [5] Kostic D, Rodriguez A, Albrecht J, Vahdat A. Bullet: High bandwidth data dissemination using an overlay mesh. ACM SIGOPS Operating Systems Review, 2003,37(5):282-297.
    [6] Zhao BY, Huang L, Stribling J, Rhea SC, Joseph AD, Kubiatowicz JD. Tapestry: A resilient global-scale overlay for service deployment. IEEE Journal on Selected Areas in Communications, 2004. 41-53.
    [7] Ratnasamy S, Francis P, Handley M, Karp R. A scalable content-addressable network. In: Proc. of the ACM SIGCOMM. New York: ACM Press, 2001. 149-160.
    [8] Stoica I, Robert M, Liben-Nowell D, Karger, Kaashoek MF, Dabek F, Balakrishnan H. Chord: A scalable peer-to-peer lookup protocol for Internet applications. 2001. http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf
    [9] Rowstron A, Druschel P. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In: Proc. of the 18th IFIP/ACM Int'1 Conf. on Distributed Systems Platforms (Middleware 2001). Berlin: Springer-Verlag, 2001. 329-350.
    [10] Malkhi D, Naor M, Ratajczak D. Viceroy: A scalable and dynamic emulation of the butterfly. In: Proc. of the 21th Annual ACM Symp. on Principles of Distributed Computing (PODC 2002). New York: ACM Press, 2002. 183-192.
    [11] Rewaskar S, Kaur J. Testing the scalability of overlay routing infrastructures. 2004. http://www.pamconf.org/2004/papers/262.pdf
    [12] Chu Y, Rao SG, Seshan S, Zhang H. A case for end system multicast. IEEE Journal on Selected Areas in Communications. 2002, 20(8):1456-1471.
    [13] Liebeherr J, Nahas M, Si W. Application-Layer multicasting with Delaunay triangulation overlays. IEEE Journal on Selected Areas in Communications. 2002,20(8):1472-1488.
    [14] Awerbuch B, Shavitt Y. Topology aggregation for directed graphs. IEEE/ACM Trans. on Networking, 2001,9(1): 82-90.
    [15] Jamin S, Jin C, Kurc A R, Raz D, Shavitt Y. Constrained mirror placement on the Internet. In: Proc. of the IEEE INFOCOM. Piscataway: IEEE Press, 2001
    [16] Theilmann W, Rothermel K. Dynamic distance maps of the Internet. In: Proc. of the IEEE INFOCOM. Piscataway: IEEE Press, 2000.
    [17] Ratnasamy S, Handley M, Karp R, Shenker S. Topologically-Aware overlay construction and server selection. In: Proc. of the IEEE INFOCOM. Piscataway: IEEE Press, 2002.
    [18] Winter R, Zahn T, Schiller J. Topology-Aware overlay construction in dynamic networks. In: Proc. of the IEEE Int'l Competition Network ICN. 2004. http://cst.mi.fu-berlin.de/publications/pdf/rlm_cnpa_icn2004_final.pdf
    [19] Wang W, Jin C, Jamin S. Network overlay construction under limited end-to-end reachability. In: Proc. of the IEEE INFOCOM. Piscataway: IEEE Press, 2005.
    [20] Francis P, Jamin S, Jin C, Jin Y, Raz D, Shavitt Y, Zhang L. IDMaps: A global internet host distance estimation service. IEEE/ACM Trans. on Networking, 2001,9(5):525-540.
    [21] Chen Y, Lim KH, Katz RH, Overton C. On the stability of network distance estimation. ACM SIGMETRICS Performance Evaluation Review, 2002. 21-30.
    [22] Gummadi KP, Saroiu S, Gribble SD. King: Estimating latency between arbitrary Internet end hosts. In: Proc. of the 2nd ACM SIGCOMM Workshop on Internet measurement. New York: ACM Press, 2002. 5-18.
    [23] Leonard D, Loguinov D. Turbo king: Framework for large-scale internet delay measurements. In: Proc. of the IEEE INFOCOM. Piscataway: IEEE Press, 2008.
    [24] Srinivasan S, Zegura E. M-Coop: A scalable infrastructure for network measurement. In: Proc. of the 3rd IEEE Workshop on Internet Applications. Washington: IEEE Computer Society, 2003. 35-39.
    [25] Wong B, Slivkins A, Sirer EG. Meridian: A lightweight network location service without virtual coordinates. In: Proc. of the ACM SIGCOMM. New York: ACM Press, 2005.
    [26] Sharma P, Xu Z, Banerjee S, Lee SJ. Estimating network proximity and latency. ACM SIGCOMM Computer Communication Review. 2006. 39-50. http://networking.hpl.hp.com/s-cube/nv.pdf
    [27] Guyton JD, Schwartz MF. Locating nearby copies of replicated Internet servers. In: Proc. of the ACM SIGCOMM. New York: ACM Press, 1995. 288-298.
    [28] Ng TS, Zhang H. Predicting Internet network distance with coordinates-based approaches. In: Proc. of the IEEE INFOCOM. Piscataway: IEEE Press, 2002.
    [29] Lim H, Hou JC, Choi CH. Constructing Internet coordinate system based on delay measurement. In: Proc. of the 2nd ACM SIGCOMM Workshop on Internet measurement. New York: ACM Press, 2003. 129-142.
    [30] Tang L, Crovella M. Virtual landmarks for the Internet. In: Proc. of the ACM SIGCOMM Conf. on Internet measurement (IMC). New York: ACM Press, 2003. 143-152.
    [31] Ng TS, Zhang H. A network positioning system for the Internet. In: Proc. of the USENIX Annual Technical Conf. Boston: USENIX Association Press, 2004.
    [32] Waldvogel M, Rinaldi R. Efficient topology-aware overlay network. ACM SIGCOMM Computer Communication Review. 2003. 101-106. http://conferences.sigcomm.org/hotnets/2002/papers/waldvogel.pdf
    [33] Pias M, Crowcroft J, Wilbur S, Harris T, Bhatti S. Lighthouses for scalable distributed location. In: Proc. of the Int'l Workshop on Peer-to-Peer Systems (IPTPS 2003). Berlin: Springer-Verlag, 2003
    [34] Zhang R, Hu YC, Lin X, Fahmy S. A hierarchical approach to Internet distance prediction. In: Proc. of the 26th IEEE Int'l Conf. on Distributed Computing Systems. IEEE Computer Society, 2006.
    [35] Shavitt Y, Tankel T. Big-Bang simulation for embedding network distances in euclidean space. IEEE/ACM Trans. on Networking, 2004,12(6):993-1006.
    [36] Shavitt Y, Tankel T. On the curvature of the Internet and its usage for overlay construction and distance estimation. In: Proc. of the IEEE INFOCOM. Piscataway: IEEE Press, 2004.
    [37] Shavitt Y, Tankel T. Hyperbolic embedding of Internet graph for distance estimation and overlay construction. IEEE/ACM Trans. on Networking, 2008: 25-36. http://www.eng.tau.ac.il/～tankel/pub/TonHyp07.pdf
    [38] Dabek F, Cox R, Kaashoek F, Morris R. Vivaldi: A decentralized network coordinate system. In: Proc. of the ACM SIGCOMM. New York: ACM Press, 2004. 15-26.
    [39] Costa M, Castro M, Rowstron R, Key P. PIC: Practical Internet coordinates for distance estimation. In: Proc. of the 24th IEEE Int'l Conf. on Distributed Computing Systems (ICDCS). 2004. 178-187. http://ieeexplore.ieee.org/xpls/abs_all. jsp- arnumber=1281582
    [40] Mao Y, Saul LK, Smith JM. IDES: An Internet distance estimation service for large networks. IEEE Journal on Selected Areas in Communications, 2006,24(12):2273-2284.
    [41] Lehman L, Lerman S. PCoord: Network position estimation using peer-to-peer measurements. In: Proc. of the 3rd IEEE Int'l Symp. on Network Computing and Applications. 2004. 15-24.
    [42] Wei L, Lerman S. A decentralized network coordinate system for robust internet distance. In: Proc. of the 3rd Int'l Conf. on Information Technology: New Generations (ITNG 2006). IEEE Computer Society, 2006.
    [43] Xing C, Chen M. HNDP: A novel network distance prediction mechanism. In: Proc. of the IFIP NPC. 2007. http://www. springerlink.com/content/9k83022708m81336/
    [44] Lua EK, Griffin T, Pias M, Zheng H, Crowcroft J. On the accuracy of embeddings for Internet coordinate systems. In: Proc. of the ACM SIGCOMM Conf. on Internet Measurement (IMC). New York: ACM Press, 2005.
    [45] Hotz S. Routing information organization to support scalable interdomain routing with heterogeneous path requirements. 1994.
    [46] Madhyastha HV, Anderson T, Krishnamurthy A, Spring N, Venkataramani A. A structural approach to latency prediction. In: Proc. of the ACM SIGCOMM Conf. on Internet Measurement (IMC). New York: ACM Press, 2006. 99-104.
    [47] Madhyastha HV, Isdal T, Piatek M, Dixon C, Anderson T, Krishnamurthy A, Venkataramani A. iPlane: An information plane for distributed services. 2006.
    [48] Freedman MJ, Lakshminarayanan K, Mazieres D. OASIS: Anycast for any service. In: Proc. of the 3rd Conf. on Symp. on Networked Systems Design & Implementation (NSDI 2006). Berkeley: USENI Press, 2006.
    [49] Yan C, Randy K. Tomography-Based overlay network monitoring. sites. 2001. http://www.cs.berkeley.edu/yanchen/wnms
    [50] Nelder JA, Mead R. A simplex method for function minimization. Computer Journal, 1965,7:308-313.
    [51] Onbilger O K, Chen S, Chow R. A peer-to-peer network positioning architecture. In: Proc. of the 12th IEEE Int'l Conf. on Networks (ICON). Piscataway: IEEE Press, 2004.
    [52] Zheng H, Lua EK, Pias M, Griffin TG. Internet routing policies and round-trip-times. In: Proc. of the 6th Int'l Workshop on Passive And Active Network Measurement (PAM 2005). Berlin: Springer-Verlag, 2005.
    [53] Zhang B, Ng TS, Nandi A, Riedi R, Druschel P, Wang GH. Measurement based analysis, modeling, and synthesis of the internet delay space. In: Proc. of the 6th ACM SIGCOMM on Internet measurement (IMC). New York: ACM Press, 2006. 85-98.
    [54] Wang G, Zhang B, Ng TS. Towards network triangle inequality violation aware distributed systems. In: Proc. of the 7th ACM SIGCOMM Conf. on Internet Measurement (IMC). New York: ACM Press, 2007. 175-188.
    [55] Lee S, Zhang ZL, Sahu S, Saha D. On suitability of Euclidean embedding of Internet hosts. In: Proc. of the Joint Int'l Conf. on Measurement and Modeling of Computer Systems. 2006. 157-168. http://www.dtc.umn.edu/publications/reports/2006_32.pdf
    [56] Eades P, Lin X. Spring algorithm and symmetry. Theoretical Computer Science, 2000. 379-405.
    [57] Pietzuch P, Ledlie J, Seltzer M. Supporting network coordinates on PlanetLab. In: Proc. of the WORLDS. 2005. http://www.doc.ic.ac.uk/～peter/doc/nc-worlds05-camera1.pdf
    [58] Ledlie J, Pietzuch P, Seltzer M. Stable and accurate network coordinates. In: Proc. of the 26th IEEE Int'l Conf. on Distributed Computing Systems (ICDCS). 2006. http://www.eecs.harvard.edu/～syrah/nc/icdcs06.pdf
    [59] Ledlie J, Gardner P, Seltzer M. Network coordinates in the wild. In: Proc. of the 3rd Conf. on Symp. on Networked Systems Design & Implementation (NSDI 2007), 2007. http://www.eecs.harvard.edu/～syrah/nc/wild06-tr.pdf
    [60] Kaafar MA, Mathy L, Barakat C, Salamatian K, Turletti T, Dabbous W. Securing Internet coordinate system: embedding phase. In: Proc. of the ACM SIGCOMM. New York: ACM Press, 2007.
    [61] Ingwer B, Patrick G. Modern Multidimensional Scaling: Theory and Applications. Springer-Verlag. 1997.
    [62] Stutzbach D, Rejaie R. Capturing accurate snapshots of the gnutella network. In: Global Internet Symp. 2005. 127-132. http://www. postel.org/gi2005/
    [63] Stutzbach D, Rejaie R. Characterizing today's gutella topology. Technical Report, CIS-TR-04-02, University or Oregon, 2004.
    [64] Kaafar MA, Mathy L, Turletti T, Dabbous W. Real attacks on virtual networks: Vivaldi out of tune. In: Proc. of the SIGCOMM Workshop on Large-Scale Attack Defense. 2006. 139-146. http://planete.inria.fr/dabbous/publis/lsad06.pdf
    [65] Kaafar MA, Mathy L, Turletti T, Dabbous W. Virtual networks under attack: Disrupting internet coordinate systems. In: Proc. of the 2nd CoNext Conf. 2006. http://planete.inria.fr/dabbous/publis/conext06.pdf
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

王意洁,李小勇.网络距离预测技术研究.软件学报,2009,20(6):1574-1590

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2008-07-02
  • 最后修改日期:2008-11-17
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19727414位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号