跳到主要內容

臺灣博碩士論文加值系統

(3.236.110.106) 您好!臺灣時間:2021/07/29 17:51
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳志豪
研究生(外文):Chih Hao Chen
論文名稱:使用Interface Specific Routing以提高IP 網路存活率以及負載平衡的方法
論文名稱(外文):Using Interface Specific Routing for Enhancing Survivability and Load Balancing in IP Networks
指導教授:李詩偉李詩偉引用關係
指導教授(外文):Steven S.W. Lee
口試委員:李詩偉吳承崧張慶龍陳春秀
口試委員(外文):Steven S.W. LeeCheng-Shong WuChing-Lung ChangAlice Chen
口試日期:2012-07-24
學位類別:碩士
校院名稱:國立中正大學
系所名稱:通訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:50
中文關鍵詞:快速錯誤回復負載平衡高存活網路無迴路IP保護機制模擬退火
外文關鍵詞:Fast Failure RecoveryLoad BalancingSurvivable Networksloop-freeIP Protection SchemeSimulated Annealing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:406
  • 評分評分:
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
現今的網際網路已被用來承載各式各樣的通訊應用,對於需要高服務品質的應用而言,長時間的封包延遲或者服務中斷是不被允許的。然而,傳統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.
致謝辭
中文摘要
英文摘要
目錄
圖目錄
表目錄
第一章 緒論
1.1 研究動機與背景
1.2 論文架構
第二章 相關文獻探討
2.1 傳統IP中的網路回復
2.2 鏈結保護與節點保護
2.3 Multiple Routing Configuration(MRC)
2.4 Failure Insensitive Routing(FIR)
2.5 Loop Free Alternates(LFA)
第三章 提出的方法
3.1 我們的IP Protection設計
3.1.1 ISR的優點
3.1.2 圖形轉換
3.1.3 使用ISR的無迴路快速故障回復機制範例
3.1.4 為什麼我們的設計可以做到無迴路
3.1.5 如何獲得所有的鏈結狀態
3.2 模擬退火的演算法設計
第四章 實驗與結果分析
4.1 實驗環境設定
4.2 實驗結果
4.2.1 針對單一鏈結損壞之比較分析
4.2.2 針對單一節點損壞之比較分析
第五章 結論
參考文獻

[1] J. Moy, “OSPF Version2,” IETF RFC2328, April 1998.
[2] M. Shand and S.Bryant, “IP Fast Reroute Framework, IETF RFC5714, Jan .2010.
[3] S. Nelakuditi, S. Lee, Y. Yu, and Z.-L. Zhang,“Failure Insensitive Routing for Ensuring Service Availability,” in Proc. IWQoS, pp. 287–304, 2003.
[4] S. Lee, Y. Yu, S. Nelakuditi, Z.-L. Zhang, and C.-N. Chuah,“Proactive Versus Reactive Approaches to Failure Resilient Routing,” in Proc. IEEE INFOCOM , 2004.
[5] Sanghwan Lee , Yinzhe Yu, Zhi-Li Zhang, Chen-Nee Chuah, “Fast Local Rerouting for Handling Transient Link Failures,” IEEE/ACM Transactions on Networking, vol 15, pp. 359-372, April. 2007.
[6] Atlas, et al., “IP Fast Reroute: Loop-Free Alternates,” IETF RFC5286, Sept .2008.
[7] J. Tapolcai, G. Enyedi, A. Csaszar, ” IP Fast ReRoute: Loop Free Alternates Revisited,” IEEE INFOCOM, pp. 2948-2956, April. 2011.
[8] Po-Kai Tseng, Wei-Ho Chung, “Simulated Annealing based Weight Assignment Scheme for Load Balanced Fast IP Local Failure Recovery,” IEEE GLOBECOM Workshops, pp. 405-409, Dec. 2010.
[9] Gabor Retvari, Levente Csikor, Janos Tapolcai, Gabor Enyedi, Andras Csaszar, ” Optimizing IGP Link Costs for Improving IP-level Resilience,” International Workshop on the Design of Reliable Communication Networks (DRCN), pp. 62-69, 2011.
[10] A. Kvalbein, A. F. Hansen, T. Cicic, S. Gjessing, O. Lysne,”Fast IP Network Recovery using Multiple Routing Configurations,”IEEE INFOCOM , pp. 1-11, April. 2006.
[11] A. Kvalbein, A.F. Hansen, T. Cicic, S. Gjessing, O. Lysne, ”Multiple Routing Configurations for Fast IP Network Recovery,”IEEE/ACM Transactions on Networking, vol 17, pp. 473-486, April. 2009.
[12] T. Cicic, A.F. Hansen, A. Kvalbein, M. Hartmann, R. Martin, M. Menth, S. Gjessing, O. Lysne, ”Relaxed Multiple Routing Configurations: IP Fast Reroute for Single and Correlated Failures,” IEEE Transactions on Network and Service Management, vol 6, pp. 1-14, March 2009.
[13] Shohei Kamamura, Takashi Miyamura, Cristel Pelsser, Ichiro Inoue, and Kohei Shiomoto,”Minimum Backup Configuration-Creation Method for IP Fast Reroute,” IEEE GLOBECOM, pp. 1-6, 2009.
[14] Shohei Kamamura, Takashi Miyamura, Cristel Pelsser, Ichiro Inoue, and Kohei Shiomoto, ”Scalable Backup Configurations Creation for IP Fast Reroute,” Design of Reliable Communication Networks(DRCN), pp. 312-318, Oct. 2009.
[15] Yuanni Liu, Xin Li, Shanzhi Chen, Zhen Qin, ”A Fast Link Failure Recovery Technique based on Multi-Topology,” IEEE Broadband Network and Multimedia Technology (IC-BNMT), pp. 124-129, Oct. 2010.
[16] P. Psenak, S. Mirtorabi, A. Roy, L. Nguyen, P. Pillay-Esnault,” Multi-Topology (MT) Routing in OSPF, IETF RFC 4915, June. 2007.
[17] C. Metz, ”IP Protection and Restoration,” IEEE Internet Computing, vol 4, pp. 97-102, Mar/Apr. 2000.
[18] Shang Wang, Chun He, Yide Zhang, Gang Feng,”Construction of Multicast Protection Tree Based on Single Node Failure,” Communications and Mobile Computing (CMC), vol 2, pp. 202-206, April. 2010.
[19] Hui-Kai Su, Cheng-Shong Wu, Yuan-Sun Chu,”IP Local Node Protection,” ICSNC, pp. 58, Aug. 2007.
[20] D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon. “Optimization by Simulated Annealing: An Experimental Evaluation,” Operations Research, vol. 37:865–892, 1989.
[21] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated
Annealing. Science,” 220(4598):671–680, May 1983.
[22] M. Nagy, G. Retvari, “An evaluation of approximate network optimization methods for improving ip-level fast protection with loop-free alternates,” ICUMT, pp. 1-7, 2011.
[23] Michael Menth, Matthias Hartmann, Rüdiger Martin, Tarik Čičić, Amund Kvalbein,”Loop-free alternates and not-via addresses: A proper combination for IP fast reroute? ,” Computer Networks, vol 54, pp. 1300-1315, 2010.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top