臺灣博碩士論文加值系統

在行動隨意網路中，IP位址指派是一個很重要的問題，尤其在第四代行動網路系統，以全IP為基礎的異質型網路中更顯的重要。現存的解決方法大多採用分散式演算法，因此在(1)維護可用的IP 位址與(2)確保沒有位址衝突時，導致大量的廣播(broadcast)訊息發生。在本篇論文中，我們提出了一個以環為基礎的位址自動組態協定來設定節點的位址。我們主要的工作鎖定在分散式的以環為基礎之位址自動組態協定(DRAA)，它具有低延遲時間、低通訊負載與高不中斷連線的優點。DRAA協定是一個低延遲時間的解決方法，因為每個節點獨立地指派IP位址並且在新節點加入網路時，不需要做位址衝突偵測(DAD)。通訊負載也因邏輯環的應用而明顯的減低，因為邏輯環可使用少量的單一傳播(uni-cast)來分配與取回無效的位址資源。此外，DRAA協定在網路聚合(network merging)時，同時檢查了TCP連線與網路節點的數量，使位址衝突的節點能盡量選擇在較小的網路中重新加入網路，使得節點能以較快的速度重新建立連線並繼續傳輸資料。為了能降低更多的網路負載並提供位址資源能平均分配在每個節點，我們進一步討論一個集中式的以環為基礎之位址自動組態協定(CRAA)。CRAA協定可使位址資源平均分配給每個節點，並且在網路聚合時減少大量的廣播訊息。基於以上的理由，我們的解決方法適合在大型的行動隨意網路中使用。最後，經由模擬結果與效能分析，顯示出DRAA協定具有最低的延遲時間，而CRAA協定具有平均分散位址資源的能力，並且DRAA與CRAA協定都達到了低通訊負載與高不中斷連線的好處。

The problem for dynamic IP address assignment is manifest in mobile ad hoc networks (MANETs), especially in 4G all-IP-based heterogeneous networks. Existing solutions are mainly riveted to decentralized algorithms, applying a large number of broadcast messages to (1) maintain available IP address pools and (2) ensure no address duplication occurring. In this thesis, we propose a ring-based address autoconfiguration protocol to configure node addresses. This work aims at the decentralized ring-based address autoconfiguration (DRAA) protocol, which has the advantage of low latency, low communication overhead and high uninterruptible connection. The DRAA protocol is a low-latency solution because each node independently allocates partial IP addresses and does not need to perform the duplicate addresses detection (DAD) during
the node-join operation. Communication overhead is significantly lessened in that DRAA protocol uses the logical ring, thus utilizing fewer control messages solely by means of uni-cast messages to distribute address resources and to retrieve invalid addresses. Furthermore, if duplicate addresses are shown at network merging, the DRAA protocol checks the number of both TCP connections and of nodes to allow duplicate nodes to rejoin the smaller network so that lost connections are fast re-connected. To improve communication overhead and provide the evenness of address resources, the centralized ring-based address autoconfiguration (CRAA) protocol is discussed. The CRAA protocol reduces larger numbers of broadcast messages during network merging. The other contribution is that our CRAA protocol also has an even capability so that
address resources can be evenly distributed in each node in networks; this accounts for the reason our solution is suitable for large-scale networks. Finally, the performance analysis illustrates performance achievements of RAA protocols. The simulation result shows that the DRAA protocol has the shortest latency, that the CRAA protocol has the capability to evenly distribute address resources, and that both of DRAA and CRAA protocols are the good solutions which achieve low communication overhead and high uninterruptible connection.

1 Introduction 1
2 Basic Ideas 6
3 Decentralized Ring-Based Address Autoconfiguration Protocol (DRAA) 15
3.1 Initial State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Node Joining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2.1 Address Requesting Phase . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2.2 Failed Node Checking Phase . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Node Leaving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 Network Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.4.1 Holder Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.5 NetworkMerging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Centralized Ring-Based Address Autoconfiguration Protocol (CRAA) 24
5 Performance Analysis 29
5.1 Performance of Latency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.2 Performance of Communication Overhead . . . . . . . . . . . . . . . . . . . 33
5.3 Performance of Evenness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.4 Performance of Uninterruptible Connections . . . . . . . . . . . . . . . . . . 35
6 Conclusions 36

[1] C. E. Perkins and P. Bhagwat. “DSDV routing over a multihop wireless network of mobile
computers“. In Tomasz Imielinski and Henry F. Korth, editors, Mobile Computing,
pages 183 – 206. Kluwer Academic Publishers, 1996.
[2] C. E. Perkins and E. M. Royer. “The ad hoc on-demand distance vector routing“. In
C.E. Perkins, editor, Ad Hoc Networking, pages 173 – 219. Addison-Wesley, 2001.
[3] Zygmunt J. Haas and Marc R. Pearlman. “ZRP: a hybrid framework for routing in ad
hoc networks“. In C.E. Perkins, editor, Ad Hoc Networking, pages 221 – 253. Addison-
Wesley, 2001.
[4] D. Johnson, D. Maltz, and J. Broch. “DSR: The Dynamic Source Routing protocol
for multihop wireless ad hoc networks“. In C.E. Perkins, editor, Ad Hoc Networking,
pages 139 – 172. Addison- Wesley, 2001.
[5] C. E. Perkins, J. T. Malinen, R.Wakikawa, E. M. Belding-Royer, and Y. Sun. “Ad hoc
Address Autoconfiguration“. Internet Engineering Task Force, Internet Draft, draftietf-
manet-autoconf-01.txt, 2001. (Work in Progress).
[6] R. Droms. “Dynamic Host Configuration Protocol“. Internet Engineering Task Force,
RFC 2131, Mar. 1997.
[7] M. Gerla, X. Hong, and G. Pei. “Fisheye State Routing Protocol (FSR) for Ad Hod
Networks“. Internet Engineering Task Force, Internet Draft, draft-ietf-manet-fsr-03.txt,
Jun. 2002 (Work in Progress).
[8] T. Narten, E. Nordmark, and W. Simpson. “Neighbor Discovery for IP Version 6
(IPv6)“. Internet Engineering Task Force, RFC 2461, Dec. 1998. (Work in Progress).
[9] Y. Sun and E. M. Belding-Royer. “Dynamic Address Configuration in Mobile Ad hoc
Networks“. Technical report, Computer Science Department, UCSB, Mar. 2003.
[10] S. Thomson and T. Narten. “IPv6 stateless address autoconfiguration“. Internet Engineering
Task Force, RFC 2462, Dec. 1998.
[11] Zero Configuration Networking. http://www.ietf.org/html.charters/zeroconfcharter.
html.
[12] J. Broch, D. Maltz, D. Johnson, Y.-C. Hu, and J. Jetcheva. “A Performance Comparison
of Multi-Hop Wireless Ad-Hic Network Routing Protocols“. In Proceedings
of the Fourth Annual ACM/IEEE International Conference on Mobile computing and
Networking (Mobicom’98), pages 85 - 97, Oct. 1998.
[13] P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot.
“Optimized link state routing protocol for ad hoc networks“. In Proceedings of IEEE
International Multi Topic Conference (IEEE INMIC) 2001, pages 62 - 68, 28-30 Dec.
2001.
[14] Mansoor Mohsin and Ravi Prakash. “IP address assignment in a mobile ad hoc network“.
In Proceedings of IEEE Military Communications Conference (MILCOM 2002),
volume 2, pages 856 - 861, Anaheim, CA, United States, 7-10 Oct. 2002.
[15] Sanket Nesargi and Ravi Prakash. “MANETconf: Configuration of hosts in a mobile
ad hoc network“. In Proceedings of the Twenty-first Annual Joint Conference of the
IEEE Computer and Communications Societies (INFOCOM 2002), volume 2, pages
1059 - 1068, 23-27 Jun. 2002.
[16] I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. Frans Kaashoek, F. Dabek, and
H. Balakrishnan. “Chord: A scalable peer-to-peer lookup protocol for internet applications“.
IEEE/ACM Transactions on Networking, pages 149 - 160, 2002.
[17] Abhishek Prakash Tayal and L. M. Patnaik. “An address assignment for the automatic
configuration of mobile ad hoc networks“. Personal Ubiquitous Computer, volume 8,
issue 1, pages 47 - 54, Feb. 2004.
[18] Nitin H. Vaidya. “Weak duplicate address detection in mobile ad hoc networks“. In
Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking and
computing (MobiHoc 2002), pages 206 - 216, Lausanne, Switzerland, 9-11 Jun. 2002.
[19] Kilian Weniger and Martina Zitterbart. “IPv6 Autoconfiguration in Large Scale Mobile
Ad-Hoc Networks“. In Proceedings of European Wireless 2002, pages 142 - 148,
Florence, Italy, Feb. 2002.
[20] Hongbo Zhou, Lionel M. Ni, and Matt W. Mutka. “Prophet address allocation for large
scale MANETs“. In Proceedings of the Twenty-Second Annual Joint Conference of the
IEEE Computer and Communications Societies (INFOCOM 2003), volume 2, pages
1304 - 1311, San Francisco, CA, United States, Mar. 30-Apr. 3 2003.
38