郭斯彥臺灣大學：電機工程學研究所林敬育Lin, Ching-YuChing-YuLin2007-11-262018-07-062007-11-262018-07-062005http://ntur.lib.ntu.edu.tw//handle/246246/53179自從1990年代，網際網路盛行開始，人們對於網際網路的依賴不斷加深。越來越多的服務可透過網際網路獲得，同時越來越多的活動轉移到網際網路上進行。人們透過網際網路從事工作、購物和娛樂，網際網路已與現代人們的生活密不可分。一旦網際網路無法獲得，已如同沒有電力、車輛或電話一般，將造成人們生活極大的不方便。對於企業而言，網際網路更是不可或缺的工具，企業透過網際網路服務客戶並且獲得收益。每一分鐘無法透過網際網路提供服務都代表著客戶、收益跟競爭力的流失。網際網路的高可用性因此顯得特別重要。 本論文將專注在網際網路的繞徑問題上討論其高可用性，並且主要涵蓋繞徑路徑(routing path)與目的地(routing destination)備援兩個方向。首先，在繞徑路徑的備援部份，我們提出一個基於k-connected graph與flooding algorithm的多點傳播(multicast)方法，以達成高度可靠的網際網路多點傳播。其次，在繞徑目的地的備援部份，我們提出一個基於WRS的任一群播(anycast)方法，同時擁有負載平衡之特性，以多目的地的備援方式達到高可用性的網際網路傳播。 網際網路上的任一群播，在本質上具備有容錯及負載平衡之特性，因此被廣泛的討論與研究。但是其在定義及實現方法上的不明確性，使得任一群播尚無法廣泛的被應用。因此本篇論文，根據IPv6 extension header的規範，定義出Type 3的routing extension header以為任一群播所使用。我們同時揭露了多種具有前瞻性的任一群播的繞徑方式。Internet has become popular since 90s’. From that time, people relay more and more on Internet. A vast amount services are provided on Internet. People work on Internet, shop on Internet, and entertain on Internet. Internet has deeply and completely integrated into people’s daily lives. The unavailability of Internet will make people inconveniently just as the unavailability of electric force, telephone, or vehicle. From the view of corporations, the unavailability of Internet will lead to their Internet service become inaccessible. Every minute of service down time can mean lost of customer, revenue, and productivity. High availability of Internet can be considered and achieved in many aspects. This dissertation will focus on the routing issues of IP networks. Two major dimensions of redundancy will be covered: (1) Redundancy of routing path. (2) Redundancy of routing destination. A reliable multicast scheme based on the flooding algorithm and the k-connected graph is proposed to achieve Internet high availability by way of having redundant routing paths. Besides, a load-balanced anycast routing scheme based on the WRS method is presented to achieve Internet high availability by way of having redundant routing destinations. Anycast is naturally fault-tolerant and load-balanced. However, the definition and behavior of anycasting are not clear enough until now. To realize anycast, we design the type 3 routing extension header for IPv6 anycasting. A number of new possible anycast routing models are explored too.CHAPTER 1 INTRODUCTION 1 1.1 HIGH AVAILABILITY 1 1.2 COMMUNICATION TYPES OF IP NETWORKS 3 1.3 RELATED TERMINOLOGY 3 1.4 DISSERTATION OUTLINE 4 CHAPTER 2 RELIABLE MULTICAST BASED ON k-CONNECTED GRAPH 6 2.1 OVERVIEW 7 2.2 MULTICAST ROUTING ALGORITHMS 9 2.3 PROBLEMS OF MULTICAST TREE 11 2.4 K-CONNECTED GRAPH 14 2.4.1 Connectivity 14 2.4.2 Minimum k-Connected Graph Augmentation Problem 16 2.4.3 Applying Graph Augmentation Algorithm to Multicast 17 2.4.4 Characteristics of Minimum k-Connected Graph 18 2.5 FLOODING ON K-CONNECTED GRAPH 19 2.6 ANALYSIS AND COMPARISONS 23 2.7 SUMMARY 27 CHAPTER 3 LOAD-BALANCED ANYCAST WITH MINIMAL AVERAGE DELAY 28 3.1 OVERVIEW 30 3.2 RELATED WORK AND BACKGROUND 31 3.2.1 Related Work 31 3.2.2 Background 32 3.3 PROBLEM MODEL AND MATHEMATICAL DERIVATIONS 34 3.3.1 Problem Model 34 3.3.2 Mathematical Derivations 35 3.4 LOAD-BALANCED ANYCAST ROUTING SCHEME 37 3.4.1 Routing Table Establishment Stage 37 3.4.2 Outgoing Interface Selection Stage 40 3.4.3 Weight Calculation Algorithm 42 3.4.4 Remarks 44 3.5 EVALUATIONS AND ANALYSIS 47 3.6 SUMMARY 49 CHAPTER 4 EXTENSION HEADERS FOR IPv6 ANYCAST 52 4.1 OVERVIEW 53 4.2 SURVEY AND ANALYSIS 55 4.3 DESIGN OF ANYCAST ROUTING HEADERS 57 4.3.1 Format of anycast routing header 58 4.3.2 Routing header for multiple destination routing method 60 4.3.3 Routing header for favorite-list routing method 62 4.3.4 Routing header for decision-deferred routing method 67 4.3.5 Extensibility of anycast routing header 69 4.4 SCENARIOS 70 4.4.1 Scenarios for the multiple destination routing header 70 4.4.2 Scenarios for the favorit-list routing header 71 4.4.3 Scenario for the decision-deferred routing header 72 4.5 SUMMARY 72 CHAPTER 5 CONCLUDING REMARKS 74 5.1 RESEARCH CONTRIBUTIONS 74 5.1.1 Reliable Multicast Based on k-Connected Graph 74 5.1.2 Load-Balanced Anycast Routing 75 5.1.3 Extension Headers for IPv6 Anycast 75 5.2 FUTURE WORKS 76 BIBLIOGRSPHY 78 PUBLICATION LIST 821311190 bytesapplication/pdfen-US網際網路協定繞徑高可用性負載平衡任一群播IP NetworksRouting MechanismHigh-AvailabilityLoad BalanceAnycastingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53179/1/ntu-94-D87921022-1.pdf