IP網路之高可用性繞徑機制

Abstract

自從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.