Voronoi-based Overlap Netwok 是一種peer-to-peer 的network virtual environment (NVE)，也由於它具有peer-to-peer的特性，因此讓彼此能自動搜尋及自動維持網路連結的功能，更能進一步應用到資源搜尋、分享機制、檔案分享及即時訊息傳遞等功能。
    本論文將提出一個以peer-to-peer概念為基礎的網路虛擬環境，在TCP/IP的基礎上，分析每個node的IP及netmask資訊，透過本論文中提及的演算方式，轉換成多個不同的Voronoi 2D平面，將彼此串聯成一拓樸樹狀結構；而在透過將IP 資訊轉換為Voronoi 平面上的（ x,y ） 座標的過程中， 使得Voronoi-based Overlap Network架構能夠順利連線溝通，也使其能運用於建立可擴展式的網路虛擬環境。

Voronoi-based Overlap Network is a kind of peer-to-peer network virtual envirement(NVE). As a result of the characteristic of peer-to-peer network,it can automatically search nodes and automatically maintain the network connection . It can also apply to the following applications such as files or streaming resource searching,sharing or instant messaging.
    This thesis proposes an algorithm to transform the node IP address into Voronoi plane coordinate(x,y), it transforms the IP address into many two dimension Voronoi plane , and connect each plane into a topology structure. This Voronoi network can communicate easily, also can be used on a scalable network virtual environment.

第一章 序 論………………………………………………1
1.1.NVE 環境需要具備的特性……………………………2
1.2.動機與研究目的..………………………………………4
1.3.問題的定義..……………………………………………4
1.4.未來應用..………………………………………………5
第二章 相關研究..……………………………………………7
2.1.TCP/IP 的基本概念..…………………………………7
2.1.1.IP Address…………………………………………8
2.1.2.Netmask…………………………………………9
2.1.3.網路間Router 介面……………………………10
2.2. Voronoi-based Overlap Network……………………11
2.2.1. Voronoi Diagram………………………………12
2.2.2. Voronoi-based Overlap Network………………13
第三章 將IP位置轉換到Voronoi-based Overlap Network環境的轉址方法…15
3.1.基本概念………………………………………………15
3.1.1.將Network Number 轉換到Plane Number……18
3.1.2.將Host Number 轉換到VON 座標平面………19
3.1.3.將Host Number 的轉換方式…………………20
3.1.4.建構轉換方程式Transformation Function……20
3.2.IP-based Voronoi-based Overlay Network Operations..26
3.2.1.Join………………………………………………26
3.2.2.Leave…………………………………………….29
第四章 實作………………………………………………… 30
4.1.程式設計規劃…………………………………………30
4.2.測試情境與測試結果…………………………………32
第五章 結論與未來發展應用……………………………… 35
5.1.結論……………………………………………………35
5.2.未來發展應用…………………………………………35
參考文獻..……………………………………………………..36
英文稿…..……………………………………………………..41

圖目錄
圖2-1 TCP/IP 協定架構的層次…………...……………….....7
圖2-2 網路架構 …………	…………………………………11
圖2-3 Voronoi Diagram………………………………………12
圖3-1 IP-based Voronoi overlap Network …………………...16
圖3-2 Sample Multi-plane Tree Architecture………………...17
圖3-3 node環繞(0,0)為中心網外擴散擺放..………………..20
圖 3-4以座標(0,0)為中心的四個區塊切割方式……………21
圖 3-5當i=1 時的四個區塊切割方式……………………..	22
圖 3-7 Joining Procedure……………………………………..	26
圖 4-1 程式的Class diagram………………………………..31
圖 4-2 Transformation 程式的圖示說明..…………………..32
圖 4-3測試範例網路架構圖..……………………………….33
圖 4-4 Voronoi Map ID=2917917184的圖形………………..33
圖 4-5 Voronoi Map ID=2917916992的圖形………………..34
圖 4-6 Voronoi Map ID=2917917120的圖形………………..34

表目錄
表3-1 Transformation Function ……………………………...24
表3-2 Transformation Function Algorithm…………………..25
表5-1 IPV4 與IPV6的比較…………………………………36

公式目錄
[Equation.1] VONMapID=NetworkNumber ………………...17
[Equation.2] NetworkNumber=IP&netmask ………………...17
[Equation.3] VONID=NetworkNumber……………………...18
[Equation.4] HostNumber=IP&netmask^……………………18

[Dwyer 86] R. A. Dwyer.”A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(n
loglog n ) expected time,” in Proc.2nd, Annual Symp. Computational Geometry, Yorktown Heights ,1986 , Pages 276 -284.
[Eclipse 04] [online] The Eclipse Foundation organization, Inc,2004 , available at http://www.eclipse.org .
[eDonkey 03] [online] electronic donkeys (c) MetaMachine, 2003,availiabe at http://www.edonkey.com .
[Fortune 87] S.Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmic 2, 1987, Pages 153-174.
[Gnultella 00] [online] Justin Frankel and Tom Pepper of Nullsoft ,Gnutella,14,March,2000 ,avialiable at http://en.wikipedia.org/wiki/gnutella.
[Hu 05] Shun-Yun Hu, “Scalable Peer-to-peer Networked VirtualEnvironment,” Master’s thesis, Tamkang Univ,
Taiwan, 2005.
[Hu 04] Shun-Yun Hu and Guan-Ming Liao, “Scalable Peerto-
Peer Networked Virtual Environment” in Proc.ACM SIGCOMM 2004 workshops on NetGames,Aug.2004, Pages, 129-133.
[MMOG 05] Woodcock, Bruce Sterling “An Analysis of MMOG
Subscription Growth” MMOGCHART.COM Nov 2004. 1, Jan 2005. http://www.mmog chart.com.
[Napster 03] Napster LLC and subscription service, 2003-2006 Abvailable at http://www.napster.com.
[RFC 768] User Datagram Protocol RFC 768 IETF ,January,
1983.
[RFC 821] J. Postel Simple Mail Transfer Protocol RFC 821
IETF ,January, 1982.
[RFC 854] Postel &Reynolds TELNET PROTOCOL SPECIFICATION
RFC 854 IETF, January 1983.
[RFC 959] Postel & Reynolds FILE TRANSFER PROTOCOL
RFC 959 IETF , January 1985.
[RFC 1180] Socolofsky & Kale A TCP/IP Tutorial IETF RFC
1180 IETF ,January 1991.
[RFC 2460] S. Deering, R. Hinden, Internet Protocol, Version 6 Specification(IPv6) , RFC 2460, December 1998.
[Sangoma 05] TCP/IP and IPX Routing Tutorial ,Sangoma Technologies Corp. 2005 http://www.sangoma.com.
[Singhal&Zyda 99] S. Singhal and M. Zyda，Networked Virtual Environments : Design and Implementation. ACM Press,New York,1999.