- 學位論文
使用Interface Specific Routing以提高IP 網路存活率以及負載平衡的方法
Using Interface Specific Routing for Enhancing Survivability and Load Balancing in IP Networks
摘要
現今的網際網路已被用來承載各式各樣的通訊應用，對於需要高服務品質的應用而言，長時間的封包延遲或者服務中斷是不被允許的。然而，傳統IP路由協定如OSPF，在網路發生故障後需高達數十秒以便協定重新收斂並產生新的路由表，如此長的時間會造成大量封包遺失甚至導致連線中斷。為了避免網路故障所造成的損害，一個存活性網路的設計除了必須以達到高存活率為首要目標，尚須做到快速故障恢復以減少封包遺失並避免連線中斷。此外，並要考量負載平衡以避免因為故障後的重新路由造成部份鏈結的壅塞。目前IP網路中每個路由器內配有單一路由表，不論封包由何輸入介面進入路由器，只要是目的地相同，來自不同輸入介面的封包皆將被輸出至相同的輸出介面。 本文中我們指出採用單一路由表造成的路由限制，並提出採用多路由的 Interface Specific Routing (ISR) 架構，以減輕傳統單一路由表所造成的限制。ISR與傳統方法最大的差別在於允許每個節點的輸入界面使用獨立的路由表，因此可以大幅提高路由彈性並藉此可以提高網路存活率以及改進負載平衡。除此之外，我們搭配了IETF所提出的一種名為LFAs的備用路徑判斷準則，其優點為簡單並且能達到Loop-free，利用該準則，可以使得我們的設計達到快速的錯誤回復。然而LFAs的作用非常依靠權重，當所設定的權重為較差的，會使得LFAs所能提供的網路存活率大大的降低。由於權重的設定問題已經被證明是一個NP-complete問題，無法直接使用現有最佳化軟體進行解題，因此我們提出了一個模擬退火的演算法去解此問題。 最後，我們將提出的方法在數個常見的網路拓樸上進行實驗，並且和OSPF以及同樣使用LFA但每個路由器僅有一個路由表的方法做比較，經數值實驗得知，我們的方法可以與OSPF同樣達到100%的存活率，但不需要數十秒的收斂時間，此外相較於運用LFA於每個節點僅有單一路由表的網路中，本論文所採用的ISR架構還能夠有效地達到負載平衡，所付出的代價僅僅是稍微長一些的平均路徑長度。
並列摘要
IP networks have become the most important communication networks in the world. As a network device fails, an IP routing protocol requires tens of seconds to converge. Such long convergence time results in large amount of packet losses and even service disconnections for time sensitive applications. In order to resolve this problem, how to design an IP network with both high survivability and short failure recovery time has become an important issue. Besides survivability ratio and recovery time, load balancing is also needed to be taken into account so as to avoid network congestion after performing traffic rerouting in failover. Nowadays, each router uses only one routing table in an IP network. Packets coming from different input interface are forwarded to the same output interface if the destination nodes of these packets are the same. This one routing table paradigm imposes inflexibility in making routing decisions. In order to relax this constraint, we propose a multi-routing table scheme called Interface Specific Routing (ISR) in this work. In ISR based networks, each input interface has its own routing table. Packets coming from different input interfaces can be forwarded to different output interfaces even if their destination nodes are the same. Routing flexibility is greatly improved using ISR. Besides, we fully take the advantage of IETF LFA fast failure reroute scheme in the proposed ISR based networks. Combining the routing flexibility of ISR and fast failure recovery of LFA make IP networks to achieve highly survivable, fast protection, and load balancing more easily. Since the performance of LFA is strongly influenced by link weight metrics, we also need to determine link metrics to optimize the desired performance. However, weight assignment for a network performing LFA has been proved to be a NP-complete problem. We propose a Simulated Annealing based heuristic algorithm to solve this problem. Finally, we carried out simulations on several benchmark networks. We observe that our method like OSPF can achieve 100% survivability. However, unlike OSPF requires long convergence time, our approach takes only short time for failure recovery. Comparing our scheme to the network adopting LFA with single routing table, our approach can achieve higher network survivability and more load balancing. The expense that we have to pay is a little longer average path length.
參考文獻
延伸閱讀
- 黃鼎鈞（2006）。在All-IP異質網路環境下可與TCP互通之SCTP交遞平台之設計與實作〔碩士論文，國立清華大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0016-1303200709283997
- Chen, J. Y. (2009). 基於行動IP協定之路由效能與換手延遲的改善研究 [doctoral dissertation, National Chi Nan University]. Airiti Library. https://doi.org/10.6837/NCNU.2009.00052
- 高菁穗（2002）。IP網路電信服務時間序列效能評估模式之研究〔碩士論文，國立臺灣師範大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0021-1904200712255305
- Chow, K. P. (2000). Load-balancing in distributed multi-agent computing [master's thesis, The University of Hong Kong]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0029-1812201200006011
- 李麒傑（2018）。Deep Learning Based Auto-Scaling Load Balancing Mechanism for Distributed Software-Defined Storage Service〔碩士論文，國立臺中科技大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0061-2008201814435000