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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：150

、訪客IP：3.139.104.214

姓名

鄭荃瑋(Chuan-wei Cheng) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

非結構式同儕網路拓樸調整
(Topology Adaptation for Unstructured Peer-to-Peer Networks)

相關論文

★ 以IEEE 802.11為基礎行動隨意無線網路之混合式省電通訊協定	★ 以范諾圖為基礎的對等式網路虛擬環境相鄰節點一致性研究
★ 行動隨意網路可調適及可延展之位置服務協定	★ 同儕式網路虛擬環境高效率互動範圍群播
★ 巨量多人線上遊戲之同儕網路互動範圍語音交談	★ 基於范諾圖之同儕式網路虛擬環境狀態管理
★ 利用多變量分析之多人線上遊戲信任使用者選擇	★ 無位置資訊無線感測網路之覆蓋及連通維持
★ 同儕網路虛擬環境3D串流同儕選擇策略	★ 一個使用802.11與RFID技術的無所不在導覽系統U-Guide之設計與實作
★ 同儕式三維資料串流	★ IM Finder: 透過即時通訊網路線上使用者找尋解答
★ 無位置資訊無線感測網路自走車有向天線導航與協調演算法	★ 多匯點無線感測網路省能及流量分散事件輪廓追蹤
★ 頻寬感知同儕式3D串流	★ 無線感測網路旋轉指向天線定位法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本論文探討兩個在非結構式同儕網路(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

論文目次

中文摘要 I
Abstract II
1. 緒論 1
2. 相關研究 5
2.1. Gnutella . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2. 拓樸重新連線演算法(Topology Rewiring Algorithm) . . . . 9
2.3. 延遲測量(Latency Measurement) . . . . . . . . . . . . . 11
2.4. 冪次法則網路(Power-Law Network) . . . . . . . . . . . . 14
3. 提出方法 15
3.1. 鄰居交換(Neighbor Swap) . . . . . . . . . . . . . . . . 15
3.2. 連線交換(Link Swap) . . . . . . . . . . . . . . . . . . 18
4. 實驗模擬 21
4.1. 環境設定. . . . . . . . . . . . . . . . . . . . . . . . 21
4.2. 模擬度量. . . . . . . . . . . . . . . . . . . . . . . . 25
4.3. 效能評估. . . . . . . . . . . . . . . . . . . . . . . . 26
5. 結論 31
引用文獻 32

參考文獻

[1] Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani, and Bernardo A. Huberman, “Search in Power-Law Networks,” Physical Review, E, Vol. 64, No. 4, pp. 046135–046143, September 2001.
[2] Albert-Laszlo Barabasi, and Reka Albert, “Emergence of scaling in random networks,” Science, Vol. 286, No. 5439, pp. 509–512, October 1999.
[3] Nabhendra Bisnik, and Alhussein A. Abouzeid, “Optimizing random walk search algorithms,” Computer Networks: The International Journal of Computer and Telecommunications Networking, Vol. 51, No. 6, pp. 1499–1514, April 2007.
[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.
[5] Yatin Chawathe, Sylvia Ratnasamy, Lee Breslau, Nick Lanham, and Scott Shenker, “Making Gnutella-like P2P Systems Scalable,” in Proceedings of ACM SIGCOMM, pp. 407–418, August 2003.
[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.
[8] Frank Dabek, Russ Cox, Frans Kaashoek, and Robert Morris, “Vivaldi: a decentralized network coordinate system,” in Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, Vol. 34, No. 4, pp. 15–26, August 2004.
[9] Paul Erd?s, and Alfred Renyi, “On the evolution of random graphs,” Publ. Math. Inst. Hung. Acad. Sci, Vol. 5, pp. 17–61, 1960.
[10] “Gnutella website.” http://www.gnutella.com.
[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.
[12] Ram Keralapura, Nina Taft, Chen-Nee Chuah, and Gianluca Iannaccone, “Can ISPs take the heat from overlay networks?,” In Proceedings of ACM Workshop on Hot Topics in Networks (HotNets-III), pp. 29-34, November 2004.
[13] Jonathan Ledlie, Paul Gardner, and Margo Seltzer, “Network Coordinates in the Wild,” in Proceedings of USENIX NSDI’07, 2007.
[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.
[15] Rui-Xuan Li, Cui-Hua Zuo, Hai-Ying Shen, Kun-Mei Wen, and Xi-Wu Gu, “PercolationNET: A multi-tree P2P overlay network supporting high coverage search,” International Journal of Parallel, Emergent and Distributed Systems, Vol. 25, No. 1, pp. 73–89, February 2010.
[16] Yun-Hao Liu, Zhen-Yun Zhuang, Li Xiao, and Lionel M. Ni, “AOTO: Adaptive Overlay Topology Optimization in Unstructured P2P Systems,” Global Telecommunications Conference, 2003. GLOBECOM ’03. IEEE, Vol. 7, pp. 4186–4190, 2003.
[17] Yun-Hao Liu, Li Xiao, and Lionel M. Ni, “Building a Scalable Bipartite P2P Overlay Network,” IEEE Transactions on Parallel and Distributed Systems, Vol. 18, No. 9, pp. 1296–1306, September 2007.
[18] Qin Lv, Pei Cao, Edith Cohen, Kai Li, and Scott Shenker, “Search and replication in unstructured peer-to-peer networks,” in Proceedings of the 16th international conference on Supercomputing (ICS ’02), ACM, New York, NY, USA, pp. 84–95, 2002.
[19] Yun Mao, Lawrence K. Saul, and Jonathan M. Smith, “Ides: An internet distance estimation service for large networks,” IEEE J. Selected Areas Commun., Special Issue on Sampling the Internet, Techniques and Applications, Vol. 24, No. 12, pp. 2273–2284, December 2006.
[20] Eugene Ng, and Hui Zhang, “Predicting Internet network distance with coordinates-based approaches,” in Proceedings of IEEE INFOCOM, pp. 170–179, June 2002.
[21] Marcelo Pias, Jon Crowcroft, Steve Wilbur, Tim Harris, and Saleem Bhatti, “Lighthouses for Scalable Distributed Location,” in Proceedings of International workshop on Peer-To-Peer Systems, pp. 278–291, February 2003.
[22] Peter Pietzuch, Jonathan Ledlie, Michael Mitzenmacher, and Margo Seltzer, “Network-aware Overlays with Network Coordinates,” in Proceedings of the 26th IEEE International ConferenceWorkshops on Distributed Computing Systems, pp. 12, July 2006.
[23] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker, “A scalable content-addressable network,” in Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications (SIGCOMM ’01), ACM, New York, NY, USA, pp. 161–172, October 2001.
[24] Matei Ripeanu, Ian Foster, and Adriana Iamnitchi, “Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design,” IEEE Internet Computing Journal special issue on peer-to-peer networking, Vol. 6, No. 1, pp. 50–57, February 2002.
[25] Antony I. T. Rowstron, and Peter Druschel, “Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems,” in Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg (Middleware ’01), Rachid Guerraoui (Ed.), Springer-Verlag, London, UK, pp. 329–350, November 2001.
[26] Stefan Schmid, and Roger Wattenhofer, “Structuring unstructured peer-to-peer networks,” in Proceedings of the 14th international conference on High performance computing (HiPC’07), pp. 432–442, Goa, India, 2007.
[27] Hendrik Schulze, and Klaus Mochalski, “Internet Study 2008/2009,” http://www.ipoque.com, 2009.
[28] Mudhakar Srivatsa, Bugra Gedik, and Ling Liu, “Large Scaling Unstructured Peer-to-Peer Networks with Heterogeneity-Aware Topology and Routing,” International Journal of Parallel, Emergent and Distributed Systems, Vol. 17, No. 11, pp. 1277–1293, November 2006.
[29] Milgram Stanley, “The Small World Problem,” Psychology Today, Vol. 1, No. 1, pp. 60–67, May 1967.
[30] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan, “Chord: A scalable peer-to-peer lookup service for internet applications,” in Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications (SIGCOMM ’01), ACM, New York, NY, USA, pp. 149–160, October 2001.
[31] Suyong Eum, Shin’ichi Arakawa, and Masayuki Murata, “Self Organizing Topology Transformation for Peer-To-Peer (P2P) Networks,” IEICE Transactions on Communications, Vol. 93, No. 3, pp. 516–524, 2010.
[32] Li Xiao, Yunhao Liu, and Lionel M. Ni, “Improving Unstructured Peer-to-Peer Systems by Adaptive Connection Establishment,” IEEE Transactions on Computers, Vol. 54, No. 9, pp. 1091–1103, September 2005.
[33] Haiyong Xie, Y. Richard Yang, Arvind Krishnamurthy, Yanbin Grace Liu, and Abraham Silberschatz, “P4P: Provider Portal for (P2P) Applications,” in Proceedings of the ACM SIGCOMM 2008 conference on Data communication (SIGCOMM ’08), ACM, New York, NY, USA, pp. 351–362, 2008.
[34] Shuang-Hua Yang, “Dealing with Internet Transmission Delay and Data Loss from the Network View,” Internet-based Control Systems Design and Applications, pp. 53–65, February 2011.
[35] Rongmei Zhang, Charlie Hu, Xiaojun Lin, and Sonia Fahmy, “A Hierarchical Approach to Internet Distance Prediction,” in Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, pp. 73, Washington, DC, USA. July 2006.
[36] Han Zheng, Eng Keong Lua, Marcelo Pias, and Timothy G. Griffin, “Internet Routing Policies and Round-Trip-Times,” PAM, 2005.
[37] Yingwu Zhu, Xiaoyu Yang, and Yiming Hu, “Making search efficient on gnutella-like p2p systems,” In Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’2005), Vol. 1, pp. 56a, IEEE Computer Society, April 2005.

指導教授

江振瑞(Jehn-ruey Jiang)

審核日期

2011-7-24

推文