臺灣博碩士論文加值系統

很多點對點(Peer-to-Peer)系統會利用系統中一部分功能較強的電腦來幫助他們完成一些特別的任務。這些電腦通常需要具備下列條件：有足夠的網路頻寬，較強的計算能力以及大容量的硬碟空間等。這些被系統選到用來做更多事的電腦通常被稱為系統中的主要節點(super node)。在我們實驗室之前做的通訊系統中，我們使用這些主要節點來幫助使用者判斷他們是否在網路位址轉換機制(Network Address Translator, NAT)後面以及幫助他們穿越網路位址轉換機制。在某些情況下，使用這種網路位址轉換機制的使用者必需藉由其它人的幫忙才能與外界的使用者通訊。這種情形下，我們的通訊系統會幫使用者找一個主要節點，使用者先將通訊用的聲音串流傳送給這個主要節點，然後再由這個主要節點幫使用者轉送通訊用的聲音串流。但是如果選到的主要節點距離使用者很遠，那麼轉送的過程將會使通訊品質下降。於本論文中，我們提出一種演算法，能夠找尋離使用者較近的主要節點。因此，能夠減少由於轉送所造成的不必要延遲。此外，我們採用了階級架構以減少為了搜尋較靠近的主要節點而需要的網路流量。最後我們模擬網路架構並且測試我們演算法的效率。測試結果說明了我們的演算法的確能夠選到較靠近使用者的主要節點。

Many Peer-to-Peer (P2P) systems take advantage of a subset of the peers that have better capability (sufficient network bandwidth, high computation power, more disk space, etc.) to enhance the quality and/or the functionalities of the services provided. These special peers are often referred to as super nodes. On the IP communication platform developed at Internet Communication Lab, NCTU, we utilized super nodes to help users in determining whether they are behind NAT (Network Address Translator) and in punching through the NAT. In certain conditions, users behind NAT need a super node to relay media streams for communication with others. If the relay super node is far from the communicating pair, it may impair the voice quality. In the thesis, we propose a greedy algorithm to search super nodes which are close to the end-users. Therefore, it can reduce unnecessary relaying delay between the users and the super node. In addition, we adopt a hierarchy structure to reduce network traffic in performing our super node selection algorithm. Finally, we evaluate our algorithm using computer simulation. The simulation results indicate that super nodes selected by our algorithm are indeed close to the end-users.

中文摘要 i
Abstract ii
誌謝 iii
Tables of Contents iv
List of Figures v
List of Tables vi
Chapter 1 Introductions 1
1.1 Introduction 1
1.2 Related Works 1
1.3 Objectives 3
1.4 Overview of This Thesis 4
Chapter 2 Super Node Selection Algorithm 5
2.1 Basic Concepts 5
2.2 Select a Super Node 7
2.3 Improvements 9
2.4 Fault Tolerant Model 12
2.5 Restructure Architecture 13
2.6 Path Optimization 14
2.7 Reduce Overhead of Querying Neighbors 17
Chapter 3 Simulation and Analysis 19
3.1 Implementation of the Simulator 19
3.2 Simulation Results and Analysis 21
3.2.1 Simulation Results 21
3.2.2 Simulation Analysis 22
Chapter 4 Conclusions 32
Reference 34

[1] Jian Liang, Rakesh Kumar and Keith W. Ross, “The KaZaA Overlay: A Measurement Study”, September 15 2004.
[2] Salman A. Baset and Henning Schulzrinne, “An Analysis of the Skype Peer-to-Peer Internel Telephony Protocol”, September 2004.
[3] Gnutella Protocol Specification. http://www.the-gdf.org/
[4] Virginia Lo, Dayi Zhou, Yuhong Liu, Chris GauthierDickey, and Jun Li, “Scalable Supernode Selection in Peer-to-Peer Overlay Networks”, IEEE Proceedings of the 2005 Second International Workshop on Hot Topics in Peer-to-Peer Systems, 2005.
[5] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, “A scalable content-addressable network,” presented at the ACM SIGCOMM, San Diego, CA, Aug. 2001.
[6] A. Rowstron and P. Druschel, “Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems,” presented at the 18th IFIP/ACM Int. Conf. Distributed Systems Platforms (Middleware 2001), Heidelberg, Germany, Nov. 2001.
[7] Honghao Wang, Yingwu Zhu and Yiming Hu, “An Efficient and Secure Peer-to-Peer Overlay Network”, IEEE Symposium on Applications and the Internet, 2003.
[8] K. Egevang, P. Francis, “The IP Network Address Translator (NAT)”, RFC 1631, May 1994.
[9] J. Rosenberg, J. Weinberger, C. Huitema and R. Mahy, ”STUN-Simple Traversal of User Datagram Protocol (UDP) Through Network Address Translators (NATs)”, RFC 3489, March 2003.
[10] Kazaa Website. http://www.kazaa.com
[11] Skype Website. http://www.skype.com/
[12] J. Rosenberg, Henning Schulzrinne, G. Gamarillo, E. Schooler, Mark Handley, A. Johnston, J. Peterson, R. Sparks, M. Handley, “SIP: Session Initiation Protocol”, RFC 3261, IETF, June 2002
[13] BRITE: Boston University Representative Internet Topology Generator. http://www.cs.bu.edu/brite/index.html.
[14] B. M. Waxman, “Routing of Multipoint Connections”, IEEE Journal on Selected Areas in Communications. VOL.6. NO.9. Dec. 1988.