非結構式同儕網路拓樸調整

Topology Adaptation for Unstructured Peer-to-Peer Networks

鄭荃瑋(Chuan-wei Cheng)

指導教授 ： 江振瑞

國立中央大學/資訊電機學院/資訊工程學系/碩士(2011年)

摘要

本論文探討兩個在非結構式同儕網路(Unstructured Peer-to-Peer Network)中的問題，並提出拓樸調整(Topology Adaptation)的方法加以解決。第一個問題是疊加網路的訊息跳躍次數過大，節點間容易有較長的溝通路徑，訊息需要更多次的轉傳才能送達，而當我們限制訊息的傳送跳數時，會導致較低的訊息覆蓋率(Coverage Ratio)。第二個問題是每當節點加入網路時，通常並不會考慮到實體的網路拓樸，造成疊加(Overlay)網路與實體(Physical)網路間存在拓樸的差異，稱之為拓樸失調問題(Topology Mismatch Problem)這會導致訊息傳遞的延遲時間增加。本論文提出一套分散式拓樸調整方法，可讓網路內的各個節點進行拓樸調整，以降低網路節點間的跳躍次數及網路延遲。我們提出的方法分為兩個策略：鄰居交換(Neighbor Swap, NS) 與連線交換(Link Swap, LS)，前者是節點藉由交換鄰居資訊後，得知連線能力較強且尚未到達連線上限的節點資訊，再將連線移到此連線能力強的鄰居節點，使網路收斂成類似冪次法則網路(Power-Law Networks)的拓樸，以降低網路的跳躍次數，提升訊息覆蓋率；而後者可利用ping的動作或是網路座標系統(Network Coordinate System, NCS)於訊息傳遞期間找出延遲較高的連線，再以延遲較低的連線作替換，降低網路延遲。我們針對NS與LS方法進行模擬實驗，實驗結果也顯示NS方法能使網路拓樸擁有較小的平均跳躍次數，因而可以提升訊息覆蓋率。LS方法能解決拓樸失調所引起的網路延遲問題，而因可以降低網路延遲。而我們發現NS策略往往也可以降低網路延遲，而將NS與LS兩個策略結合，則可以同時降低網路的跳躍次數與網路延遲。

關鍵字

網路延遲 ； 網路座標系統 ； 拓樸失調 ； 非結構式同儕網路

並列摘要

We address two problems that lead to long latency in unstructured peer-to-peer (P2P) networks. The first problem is that the P2P network usually has a large number of hop counts between two nodes, resulting in the low coverage ratio when messages are sent with a limited number of hops. The other problem is that peers randomly join a P2P network, resulting in topology mismatch between the P2P overlay and the physical IP network, which in turn causes long latency. We propose two methods, called Neighbor Swap (NS) and Link Swap (LS), to solve those problems. The NS method can connect more nodes to the nodes with higher connection capability, resulting in a topology similar to the power-law network, which has a low average number of hops and high coverage ratio between nodes. In the LS method, high latency links are substituted for lower latency links with the help of directly ping or the network coordinate system (NCS) to solve the topology mismatch problem to reduce latency. We perform simulaton experiments for both methods. The experiments results show that the NS method can reduce the number of hops between two nodes in average, and that the LS method can mitigate the topology mismatch problem to reduce the network latency. We also observe that the NS method can often reduce the network latency and that the combination of the NS and LS methods can reduce the number of hops and the network latency at the same time.

並列關鍵字

network coordinate system ； latency ； unstructured peer-to-peer network ； topology mismatch

參考文獻

[4] Andrea Ceccanti, and Gian Paolo Jesi, “Building Latency-aware Overlay Topologies with QuickPeer,” in Proceedings of the Joint International Conference on Autonomic and Autonomous Systems and International Conference on Networking and Services (ICAS-ICNS ’05), IEEE Computer Society, Washington, DC, USA, pp. 24–29, October 2005.

[6] Yang Chen, Yongqiang Xiong, Xiaohui Shi, Beixing Deng, and Xing Li, “Pharos: A Decentralized and Hierarchical Network Coordinate System for Internet Distance Prediction,” Iet Communications - IET COMMUN, Vol. 3, No. 4, pp. 539–548, 2009.

[7] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, “Section 24.3: Dijkstra’s algorithm,” Introduction to Algorithms (Second ed.), pp. 595–601, 2001.

[11] Mihajlo A. Jovanovi?, Fred S. Annexstein, and Kenneth A. Berman, “Modeling peer-to-peer network topologies through small world models and power laws,” in Proceedings of IX Telecommunications Forum TELFO, IEEE, Belgrade, 2001.

[14] Mei Li, Wang-Chien Lee, and Anand Sivasubramaniam, “Neighborhood signatures for searching P2P networks,” In Proceedings of International Database Engineering and Application Symposium (IDEAS), pp. 149–158, July 2003.