一种基于结点聚类的网络定位算法
|
摘要
大规模的网络服务应用系统已经在全世界的范围内得到运行和使用,例如:P2P文件共享系统、覆盖网络多播系统以及内容分发服务系统。这些大规模的网络应用系统能够从一些性能较好的路由选择算法以及邻居结点选择算法中获益。这是因为延迟和带宽等网络性能参数与大规模网络应用密切相关,测量这些网络性能参数值将对这些算法性能的提高有帮助。然而,在真实的网络环境下,由于大规模网络应用存在数量巨大的端到端连接,如果对每一个连接都进行测量,则会带来巨大的物理开销和时间消耗。为了解决这个问题,可以通过一定的算法来预测端到端的网络距离,而不用在真实的网络环境里进行测量,这样可以极大的减小网络开销。当前已经出现了一些网络定位算法来预测网络结点间的距离,在这些算法当中已经证明了网络坐标是简单并且实用的。网络坐标能够表示出网络中某个主机的位置,并且从某种意义上来说,还能够表示网络的拓扑结构。
本文提出了一种基于结点聚类的网络定位算法——Dumpling算法。该算法包括了两个核心机制:结点聚类机制和整体坐标移动机制。Dumpling算法致力于在更短的时间内对虚拟坐标空间中的误差进行收敛;在更少的显式测量内收敛更多的系统误差;尽量避免虚拟坐标系统的波动现象给带来的定位精度的影响。除了从理论上分析了Dumpling的优势外,本论文还经过仿真实验表明,Dumpling可以较好的达到上述三个目标,并且在最后的Dumpling整体性能测试中,表明Dumpling在真实的网络拓扑下,也能达到一定的效果。Dumpling是一个分布式的虚拟网络坐标定位系统,具有计算量少、通信开销低等优势,还能够与具体应用程序相结合。
The large-scale network systems are running and are employed within the all world scope, for example, peer-to-peer file share system, overlay network multicast and distributed content hosting services. These large-scale Internet applications can benefit from some routing selection methods and neighbor node selection algorithms. This is because the metrics of network performance have inpect on the large-scale network service systems, like the latency and bandwidth. How to measure these metrics efficently is userful to improve the performance of these large-scale network services. In the real Internet, unfortunately, measurement explicitly is impractical because the measurement of large number of end-to-end connection is too time-consuming and too costly, which may bring high overhead. To resolve this problem, we can predict network distance instead of measuring in the real network, which will reduce the overhead for measurement greatly. Some methods for predicting network distance have already been proposed. Among these methods, network coordinate methods are proved to be simple and useful. Network coordinates can indicate the positions of hosts in the network, and in some sense can indicate the topology of the network as a result.
This paper presents a network positioning algorithm based on node-clustering, called Dumpling, which contains two core mechanisms: The nodes clustering and network coordinate holistically moving. Dumpling aims at accelerating the speed of error converge, reducing the numbers of explicit measurement and easing the situation of system fluctuation. We not only analyzed the Dumpling’s performance from the perspective of theoretics, but also simulated experiments to verify that Dumpling can achieve the above three goals。In the end, we devised a simulant experiment to test the combination of Dumpling’s two mechanisms. The result shows Dumpling can also get better efficiency in the circumstances of true network topology. Dumpling is a distributed algorithm for network positioning, which has the advantages of less overhead for computation and communication. Dumpling can also be applied easily into Internet applications.
本文提出了一种基于结点聚类的网络定位算法——Dumpling算法。该算法包括了两个核心机制:结点聚类机制和整体坐标移动机制。Dumpling算法致力于在更短的时间内对虚拟坐标空间中的误差进行收敛;在更少的显式测量内收敛更多的系统误差;尽量避免虚拟坐标系统的波动现象给带来的定位精度的影响。除了从理论上分析了Dumpling的优势外,本论文还经过仿真实验表明,Dumpling可以较好的达到上述三个目标,并且在最后的Dumpling整体性能测试中,表明Dumpling在真实的网络拓扑下,也能达到一定的效果。Dumpling是一个分布式的虚拟网络坐标定位系统,具有计算量少、通信开销低等优势,还能够与具体应用程序相结合。
The large-scale network systems are running and are employed within the all world scope, for example, peer-to-peer file share system, overlay network multicast and distributed content hosting services. These large-scale Internet applications can benefit from some routing selection methods and neighbor node selection algorithms. This is because the metrics of network performance have inpect on the large-scale network service systems, like the latency and bandwidth. How to measure these metrics efficently is userful to improve the performance of these large-scale network services. In the real Internet, unfortunately, measurement explicitly is impractical because the measurement of large number of end-to-end connection is too time-consuming and too costly, which may bring high overhead. To resolve this problem, we can predict network distance instead of measuring in the real network, which will reduce the overhead for measurement greatly. Some methods for predicting network distance have already been proposed. Among these methods, network coordinate methods are proved to be simple and useful. Network coordinates can indicate the positions of hosts in the network, and in some sense can indicate the topology of the network as a result.
This paper presents a network positioning algorithm based on node-clustering, called Dumpling, which contains two core mechanisms: The nodes clustering and network coordinate holistically moving. Dumpling aims at accelerating the speed of error converge, reducing the numbers of explicit measurement and easing the situation of system fluctuation. We not only analyzed the Dumpling’s performance from the perspective of theoretics, but also simulated experiments to verify that Dumpling can achieve the above three goals。In the end, we devised a simulant experiment to test the combination of Dumpling’s two mechanisms. The result shows Dumpling can also get better efficiency in the circumstances of true network topology. Dumpling is a distributed algorithm for network positioning, which has the advantages of less overhead for computation and communication. Dumpling can also be applied easily into Internet applications.
引文
[1] Yang H C, Sanjay G R, Hui Z. A Case for End System Multicast. In: Proc of ACM SIGMETRICS. Santa Clara, CA, June 2000,1-12
[2] Yang H C, John C, Hui Z. A Case for Taxation in Peer-to-Peer Streaming Broadcast. In: Proc of ACM SIGCOMM Workshop on Practice and Theory of Incentives and Game Theory in Networked Systems (PINS), Portland, OR, August, 2004, 205-212
[3] B Knutsson, H Lu, W Xu, et al. Peer-to-Peer Support for Massively Multiplayer Games. In: Proc of 5th ACM SIGCOMM workshop on Network and system support for games, Singapore, 2006, 26-33
[4] Saroiu S, Gummadi PK, Gribble SD. A measurement study of peer-to-peer file sharing systems. In: Poc of the SPIE, Multimedia Computing and Networking, 2001, 156-170
[5] Michael F, Eric F, David M. Democratizing Content Publication with Coral. In: Pro of 1st USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI '04) San Francisco, CA, March 2004, 18-18
[6] M Castro, P Druschel, A M Kermarrec, et al. SplitStream: High-bandwidth multicast in a cooperative environment. In: Proc of ACM SOSP, Bolton Landing, NY. USA. 2003. USA: ACM press, 2003, 1-16
[7] Sylvia R, Paul F, Mark H. A Scalable Content-Addressable Network. In: Proc of ACM SIGCOMM 2001, San Diego, California, United States, 2001, 161-172
[8] 庄雷, 潘春建, 郭永强. Gnutella网络的连接管理. 软件学报, 2005, 16(1): 158-164
[9] 徐非, 杨广文, 鞠大鹏. 基于 Peer-to-Peer 的分布式存储系统的设计. 软件学报, 2004, 15(2):268-277
[10] 凌波, 王晓宇, 周傲英. 一种基于 Peer-to-Peer 技术的 Web 缓存共享系统研究. 计算机学报, 2005, 28(02):170-178
[11] 窦文, 贾焰, 王怀民. 基于对端重叠网络的通用大规模计算资源共享环境的构造. 计算机学报, 2004, 27(1):21-31
[12] 李伟, 徐志伟, 卜冠英. 网格环境下一种有效的资源查找方法. 计算机学报 , 2003, 26(11):1546-1549
[13] 王庆波, 代亚非, 田敬. 基于特征信息定位的 P2P 网络模型. 软件学报, 2003, 14(08):1481-1488
[14] 胡进锋, 黎明, 郑纬民. 带宽自适应的 P2P 网络路由协议. 软件学报, 2005, 16(05):991-999
[15] 陈贵海, 须成忠, 沈海英. 一种新的常数度数的 P2P 覆盖网络. 计算机学报, 2007,10(01):1084-1095.
[16] T.S.Eugene N, Hui Z. Predicting Internet Network Distance with Coordinates-Based Approaches. In: Proc of INFOCOM'02. New York, NY. June, 2002, 173-183
[17] T.S.Eugene N, Hui Z. A Network Positioning System for the Internet. In: Pro of USENIX Annual Technical Conference 2004. Boston, MA. June 2004, 424-438
[18] J Nelder, R Mead. A simplex method for function minimization. Computer Journal, 1965, Vol. 7: 308-313
[19] F Dabek, R Cox, F Kaashoek, et al. Vivaldi: A Decentralized Network Coordinate System. In: Proc of SIGCOMM’04, ACM, Portland, OR, 2004, 15-26
[20] M Costa, M Costro, A RowStron, et al. PIC: Practical Internet Coordinate for Distance Estimation. In: Proc of International Conference on DS, March, 2004, 178-187
[21] B Wong, A Slivkins, E Sirer. Meridian: A lightweight network location service without virtual coordinates. In: Proc of SIGCOMM’ 05, Philadelphia, Pennsylvania, 2005, 85-96
[22] P Francis, S Jamin, C Jin, et al. IDMaps: A Global Internet Host Distance Estimation Service. IEEE/ACM Transaction on Networking. Oct, 2001. Vol. 9, No. 5: 525-540
[23] Liao X, Jin H, Liu Y, et al. Anysee: peer-to-peer Live streaming. In: Proc of IEEE INFOCOM 2006, Barcelona, Spain, April 2006, 1-10
[24] Hu, Ming Li, Hongliang Yu, et al. PeerWindow: An Efficient Heterogeneous and Autonomic Node Collection Protocol. In: Proc of The 2005 International Conference on Parallel Processing (ICPP-05), June 2005, 511-520
[25] Azureus BT. Available: http://azureus.sourceforge.net, 2004-11-26.
[26] H Hoppe. Surface reconstruction from unorganized points:[PhD thesis]. Washingt- -on, Department of Computer Science and Engineering of University of Washington, 1994
[27] 陈阳,邓北星,李星. 基于坐标的网络结点聚类在Internet中的实验研究. 大连理工大学学报.2005,Z(1):826-829
[28] 陈浩. 对等网络拓扑相关的关键理论与技术研究[华中科技大学博士学位论文]. 武汉:华中科技大学计算机学院, 2005
[29] Jonathan L, Peter P, Margo S. Stable and Accurate Network Coordinates. In: Proc of the 26th IEEE International Conference on Distributed Computing Systems, Washington, DC, USA, 2006, 74-80
[30] Wei Z, Sheng Z, Yi O Y, et al. Node clustering based on link delay in P2P networks. In: Proc of Proceedings of the 2005 ACM symposium on Applied computing, Santa Fe, New Mexico, 2005, 744-749
[31] Lakshmish R, Bugra G, Ling L. A Distributed Approach to Node Clustering in Decentralized Peer-to-Peer Networks. IEEE Transactions on Parallel and Distributed Systems, Vol. 16, NO. 9: 814-829
[32] Qiang X, J Subhlok. Automatic Clustering of Grid Nodes. In: Proc of the 6th IEEE/ACM International Workshop on Grid Computing. Washington, DC, USA, 2005, 227-233
[33] Mehdi E, Mohammad R E, Akbar B, et al. Determining a Central Controlling Processor with Fault Tolerant Method in Distributed System. In: Proc of the International Conference on Information Technology. Washington, DC, USA, 2007, 658-663
[34] KINGDATA. Available: http://pdos.csail.mit.edu/p2psim/kingdata/, 2007-6-7.
[35] VivaldiSim. Available: http://www.eecs.harvard.edu/~syrah/nc/, 2008-4-1.
[36] Li-wei L, Steven L. PCoord: Network Potision Estimation Using Peer-to-Peer Measurements. In: Proc of the Network Computing and Applications, Third IEEE International Symposium, 2004, 15-24
[37] Xiao H S, Yang C, Bei X D, et al. Network Distance Prediction based on Network Coordinate System. In: Proc of GCCW’06, IEEE Computer Society, Washington, DC, USA, 2006, 170-175
[38] M Pias, J Crowcroft, S Wilbur, et al. Lighthouses for Scalable Distributed Location. In: Pro of Intl. Workshop on Peer-To-Peer Systems, Berkeley, CA, February 2003, 278-291
[39] L Tang, M Crovella. Virtual landmarks for the Internet. In: Proc of Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, Miami Beach, FL, October 2003, 143-152
[40] PlanetLab Website. Available: http://www.planet-lab.org/, 2007-5-21.
[41] M Castro, P Druschel, A Kermarrec. SCRIBE: A Large-scale and Decentralised Application-level Multicast Infrastructure. IEEE Journal on Selected Areas in Communications (JSAC) (Special issue on Network Support for Multicast Communications). October, 2002. Vol 20, No. 8:100-110
[42] B Y Zhao, J Kubiatowicz, A Joseph. Tapestry: An Infrastructure for Fault-tolerant Media Streaming Services Based on Peer-to-Peer Networks 15 Wide-area Location and Routing. Technical report, UCB/CSD-01-1141. University of California,Berkeley, CA, USA. Apr, 2001, 1-27
[43] S Ratnasamy, M Handley, R Karp, et al. Topologically-Aware Overlay Construction and Server Selection. In: Proc of IEEE INFOCOM 2002, 2002, 1190-1199
[44] M Castro, P Druschel, A M Kermarrec, et al. SCRIBE. A Large-scale and Decentralised Application-level Multicast Infrastructure. IEEE Journal on Selected Areas in Communications (JSAC) (Special issue on Network Support for Multicast Communications). October, 2002. Vol 20, No. 8:100-110
[45] Hai J, Xiang Z G, Chao Z, et al. A New Layered P2P Architecture with Efficient Resource Location Strategy. In: Proc of IEEE Conference on e-Commerce Technology for Dynamic E-Business (CEC-EAST’04). September, 2004, 298-301
[46] S Q Zhuang, B Y Zhao, A D Joseph, et al. Bayeux: An architecture for scalable and fault-tolerant wide-area data dissemination. In: Proc of Eleventh International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV 2001), 2001, 544-553
[47] H Deshpande, M Bawa, H Garcia-Molina. Streaming Live Media over Peers. Technical Report. Stanford University, 2001, 105-122
[48] 倪敏. P2P网络的应用层共享树多播方案研究. 计算机工程. 2004, 30(20): 34~36
[49] Y Guo, K Suh, J Kurose. A Peer-to-Peer On-Demand Streaming Service and Its Performance Evaluation. In: Proc of ICME 2003, Baltimore, MD. July, 2003, 147-151
[50] V N Padmanabhan, H J Wang, P A Chou, et al. Distributing streaming media content using cooperative networking. In: Proc of ACM/IEEE NOSSDAV. Miami, FL. USA. 2002. USA: ACM press, 2002, 114-125
[2] Yang H C, John C, Hui Z. A Case for Taxation in Peer-to-Peer Streaming Broadcast. In: Proc of ACM SIGCOMM Workshop on Practice and Theory of Incentives and Game Theory in Networked Systems (PINS), Portland, OR, August, 2004, 205-212
[3] B Knutsson, H Lu, W Xu, et al. Peer-to-Peer Support for Massively Multiplayer Games. In: Proc of 5th ACM SIGCOMM workshop on Network and system support for games, Singapore, 2006, 26-33
[4] Saroiu S, Gummadi PK, Gribble SD. A measurement study of peer-to-peer file sharing systems. In: Poc of the SPIE, Multimedia Computing and Networking, 2001, 156-170
[5] Michael F, Eric F, David M. Democratizing Content Publication with Coral. In: Pro of 1st USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI '04) San Francisco, CA, March 2004, 18-18
[6] M Castro, P Druschel, A M Kermarrec, et al. SplitStream: High-bandwidth multicast in a cooperative environment. In: Proc of ACM SOSP, Bolton Landing, NY. USA. 2003. USA: ACM press, 2003, 1-16
[7] Sylvia R, Paul F, Mark H. A Scalable Content-Addressable Network. In: Proc of ACM SIGCOMM 2001, San Diego, California, United States, 2001, 161-172
[8] 庄雷, 潘春建, 郭永强. Gnutella网络的连接管理. 软件学报, 2005, 16(1): 158-164
[9] 徐非, 杨广文, 鞠大鹏. 基于 Peer-to-Peer 的分布式存储系统的设计. 软件学报, 2004, 15(2):268-277
[10] 凌波, 王晓宇, 周傲英. 一种基于 Peer-to-Peer 技术的 Web 缓存共享系统研究. 计算机学报, 2005, 28(02):170-178
[11] 窦文, 贾焰, 王怀民. 基于对端重叠网络的通用大规模计算资源共享环境的构造. 计算机学报, 2004, 27(1):21-31
[12] 李伟, 徐志伟, 卜冠英. 网格环境下一种有效的资源查找方法. 计算机学报 , 2003, 26(11):1546-1549
[13] 王庆波, 代亚非, 田敬. 基于特征信息定位的 P2P 网络模型. 软件学报, 2003, 14(08):1481-1488
[14] 胡进锋, 黎明, 郑纬民. 带宽自适应的 P2P 网络路由协议. 软件学报, 2005, 16(05):991-999
[15] 陈贵海, 须成忠, 沈海英. 一种新的常数度数的 P2P 覆盖网络. 计算机学报, 2007,10(01):1084-1095.
[16] T.S.Eugene N, Hui Z. Predicting Internet Network Distance with Coordinates-Based Approaches. In: Proc of INFOCOM'02. New York, NY. June, 2002, 173-183
[17] T.S.Eugene N, Hui Z. A Network Positioning System for the Internet. In: Pro of USENIX Annual Technical Conference 2004. Boston, MA. June 2004, 424-438
[18] J Nelder, R Mead. A simplex method for function minimization. Computer Journal, 1965, Vol. 7: 308-313
[19] F Dabek, R Cox, F Kaashoek, et al. Vivaldi: A Decentralized Network Coordinate System. In: Proc of SIGCOMM’04, ACM, Portland, OR, 2004, 15-26
[20] M Costa, M Costro, A RowStron, et al. PIC: Practical Internet Coordinate for Distance Estimation. In: Proc of International Conference on DS, March, 2004, 178-187
[21] B Wong, A Slivkins, E Sirer. Meridian: A lightweight network location service without virtual coordinates. In: Proc of SIGCOMM’ 05, Philadelphia, Pennsylvania, 2005, 85-96
[22] P Francis, S Jamin, C Jin, et al. IDMaps: A Global Internet Host Distance Estimation Service. IEEE/ACM Transaction on Networking. Oct, 2001. Vol. 9, No. 5: 525-540
[23] Liao X, Jin H, Liu Y, et al. Anysee: peer-to-peer Live streaming. In: Proc of IEEE INFOCOM 2006, Barcelona, Spain, April 2006, 1-10
[24] Hu, Ming Li, Hongliang Yu, et al. PeerWindow: An Efficient Heterogeneous and Autonomic Node Collection Protocol. In: Proc of The 2005 International Conference on Parallel Processing (ICPP-05), June 2005, 511-520
[25] Azureus BT. Available: http://azureus.sourceforge.net, 2004-11-26.
[26] H Hoppe. Surface reconstruction from unorganized points:[PhD thesis]. Washingt- -on, Department of Computer Science and Engineering of University of Washington, 1994
[27] 陈阳,邓北星,李星. 基于坐标的网络结点聚类在Internet中的实验研究. 大连理工大学学报.2005,Z(1):826-829
[28] 陈浩. 对等网络拓扑相关的关键理论与技术研究[华中科技大学博士学位论文]. 武汉:华中科技大学计算机学院, 2005
[29] Jonathan L, Peter P, Margo S. Stable and Accurate Network Coordinates. In: Proc of the 26th IEEE International Conference on Distributed Computing Systems, Washington, DC, USA, 2006, 74-80
[30] Wei Z, Sheng Z, Yi O Y, et al. Node clustering based on link delay in P2P networks. In: Proc of Proceedings of the 2005 ACM symposium on Applied computing, Santa Fe, New Mexico, 2005, 744-749
[31] Lakshmish R, Bugra G, Ling L. A Distributed Approach to Node Clustering in Decentralized Peer-to-Peer Networks. IEEE Transactions on Parallel and Distributed Systems, Vol. 16, NO. 9: 814-829
[32] Qiang X, J Subhlok. Automatic Clustering of Grid Nodes. In: Proc of the 6th IEEE/ACM International Workshop on Grid Computing. Washington, DC, USA, 2005, 227-233
[33] Mehdi E, Mohammad R E, Akbar B, et al. Determining a Central Controlling Processor with Fault Tolerant Method in Distributed System. In: Proc of the International Conference on Information Technology. Washington, DC, USA, 2007, 658-663
[34] KINGDATA. Available: http://pdos.csail.mit.edu/p2psim/kingdata/, 2007-6-7.
[35] VivaldiSim. Available: http://www.eecs.harvard.edu/~syrah/nc/, 2008-4-1.
[36] Li-wei L, Steven L. PCoord: Network Potision Estimation Using Peer-to-Peer Measurements. In: Proc of the Network Computing and Applications, Third IEEE International Symposium, 2004, 15-24
[37] Xiao H S, Yang C, Bei X D, et al. Network Distance Prediction based on Network Coordinate System. In: Proc of GCCW’06, IEEE Computer Society, Washington, DC, USA, 2006, 170-175
[38] M Pias, J Crowcroft, S Wilbur, et al. Lighthouses for Scalable Distributed Location. In: Pro of Intl. Workshop on Peer-To-Peer Systems, Berkeley, CA, February 2003, 278-291
[39] L Tang, M Crovella. Virtual landmarks for the Internet. In: Proc of Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, Miami Beach, FL, October 2003, 143-152
[40] PlanetLab Website. Available: http://www.planet-lab.org/, 2007-5-21.
[41] M Castro, P Druschel, A Kermarrec. SCRIBE: A Large-scale and Decentralised Application-level Multicast Infrastructure. IEEE Journal on Selected Areas in Communications (JSAC) (Special issue on Network Support for Multicast Communications). October, 2002. Vol 20, No. 8:100-110
[42] B Y Zhao, J Kubiatowicz, A Joseph. Tapestry: An Infrastructure for Fault-tolerant Media Streaming Services Based on Peer-to-Peer Networks 15 Wide-area Location and Routing. Technical report, UCB/CSD-01-1141. University of California,Berkeley, CA, USA. Apr, 2001, 1-27
[43] S Ratnasamy, M Handley, R Karp, et al. Topologically-Aware Overlay Construction and Server Selection. In: Proc of IEEE INFOCOM 2002, 2002, 1190-1199
[44] M Castro, P Druschel, A M Kermarrec, et al. SCRIBE. A Large-scale and Decentralised Application-level Multicast Infrastructure. IEEE Journal on Selected Areas in Communications (JSAC) (Special issue on Network Support for Multicast Communications). October, 2002. Vol 20, No. 8:100-110
[45] Hai J, Xiang Z G, Chao Z, et al. A New Layered P2P Architecture with Efficient Resource Location Strategy. In: Proc of IEEE Conference on e-Commerce Technology for Dynamic E-Business (CEC-EAST’04). September, 2004, 298-301
[46] S Q Zhuang, B Y Zhao, A D Joseph, et al. Bayeux: An architecture for scalable and fault-tolerant wide-area data dissemination. In: Proc of Eleventh International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV 2001), 2001, 544-553
[47] H Deshpande, M Bawa, H Garcia-Molina. Streaming Live Media over Peers. Technical Report. Stanford University, 2001, 105-122
[48] 倪敏. P2P网络的应用层共享树多播方案研究. 计算机工程. 2004, 30(20): 34~36
[49] Y Guo, K Suh, J Kurose. A Peer-to-Peer On-Demand Streaming Service and Its Performance Evaluation. In: Proc of ICME 2003, Baltimore, MD. July, 2003, 147-151
[50] V N Padmanabhan, H J Wang, P A Chou, et al. Distributing streaming media content using cooperative networking. In: Proc of ACM/IEEE NOSSDAV. Miami, FL. USA. 2002. USA: ACM press, 2002, 114-125