面向IPv6分組轉(zhuǎn)發(fā)的路由技術(shù)研究.pdf

1、自從Intemet誕生至今，網(wǎng)絡(luò)互連性能一直是Intenet網(wǎng)絡(luò)管理者和學術(shù)界所關(guān)心的話題。近年來，隨著多媒體網(wǎng)絡(luò)技術(shù)的廣泛應用，Internet上的數(shù)據(jù)流量正以每年一倍以上的速率增長，在可以預見的未來，這個增長速率還會更快。隨著光通信網(wǎng)絡(luò)技術(shù)的提出和發(fā)展，光纖鏈路的負載容量每12個月可翻一番，以滿足不斷增長的網(wǎng)絡(luò)流量的需求。然而，根據(jù)摩爾定律，計算機處理能力和硬件水平的擴充大約以18個月一番的速率提高，這使得Intemet網(wǎng)絡(luò)中心節(jié)點

2、路由器性能的發(fā)展水平與應用的需求差距很大。為此，需要在提高路由器性能方面進行廣泛深入的研究，同時為數(shù)據(jù)傳輸提供必要的服務質(zhì)量保證。 IPv6作為下一代互連網(wǎng)絡(luò)協(xié)議，已經(jīng)開始有計劃、有步驟的部署，逐漸取代現(xiàn)階段在Intemet中廣泛應用的IPv4網(wǎng)絡(luò)協(xié)議。IPv4在Intemet發(fā)展初期取得了巨大的成功，但是它地址數(shù)量不足的問題很大程度上限制了Internet規(guī)模的進一步擴張。IPv6協(xié)議吸收了IPv4協(xié)議的優(yōu)點，并對用戶在安

3、全、QoS等方面的要求提供了支持，其中更重要的是重新設(shè)計了長達128位長度的地址和支持更多層次的編址體系結(jié)構(gòu)，解決了地址短缺的問題。可是，IPv6協(xié)議又給路由器的設(shè)計帶來了挑戰(zhàn)。一方面，巨大的地址空間必然帶來更多的路由表項，對海量路由表的查詢、維護會給路由器帶來繁重的系統(tǒng)負荷；另一方面，128位長度的地址使得原本應用于IPv4路由器的關(guān)鍵算法的效率嚴重下降，難以滿足分組快速轉(zhuǎn)發(fā)的需求。因此，開展基于IPv6的路由器關(guān)鍵技術(shù)的研究具有重要

4、的意義。 本論文在分析Internet發(fā)展現(xiàn)狀以及下一代網(wǎng)絡(luò)協(xié)議IPv6的基礎(chǔ)上，對于路由器技術(shù)的發(fā)展進行了跟蹤，圍繞著路由器協(xié)議軟件以及路由器分組轉(zhuǎn)發(fā)系統(tǒng)關(guān)鍵技術(shù)這兩大主題開展研究，論文的創(chuàng)新性工作主要體現(xiàn)在以下幾個方面： 1.本文在詳細分析了OSPF路由協(xié)議的基礎(chǔ)上，比較了OSPF路由協(xié)議與RIP路由協(xié)議之間的異同，重點分析了OSPF路由協(xié)議的IPv6版本(OSPFv3)相比其IPv4版本的改變。本文通過仔細對照OS

5、PFv3路由協(xié)議規(guī)范，設(shè)計并實現(xiàn)了面向IPv6網(wǎng)絡(luò)環(huán)境的OSPFv3路由協(xié)議軟件，保證軟件實現(xiàn)與協(xié)議規(guī)范的一致性和功能完整性，盡可能提高軟件的運行效率，減小系統(tǒng)負擔。在所提出的軟件實現(xiàn)方案當中，對協(xié)議的信令交換機制、消息的接收處理與消息發(fā)送以及協(xié)議實體的狀態(tài)轉(zhuǎn)換，嚴格按照協(xié)議規(guī)范的標準實現(xiàn)。為了提高路由轉(zhuǎn)發(fā)子系統(tǒng)的工作效率，提出了一種面向分組轉(zhuǎn)發(fā)子系統(tǒng)的路由表維護模塊設(shè)計方案，通過對路由表存儲方式的改變，一方面可以減小路由轉(zhuǎn)發(fā)子系統(tǒng)的系

6、統(tǒng)負荷，另一方面可以提高路由協(xié)議子系統(tǒng)中路由表更新過程的效率，保證了路由器整體性能的提高。 2.本文在分析了幾種常見的基于IPv4的路由搜索算法的基礎(chǔ)上，比較了它們在搜 索時間復雜度、空間復雜度上的差別，分析了它們在IPv4網(wǎng)絡(luò)向IPv6網(wǎng)絡(luò)過渡期的適應性，參考其中算法性能和可擴展性較好的基于地址前綴長度的二分搜索算法的設(shè)計思想，重點針對該算法在IPv6協(xié)議體系結(jié)構(gòu)下面臨的問題，提出了一種新的基于IPv6的快速路由表搜索

7、算法-ABSH算法。ABSH算法采用兩級搜索方式，合理劃分地址前綴空間，使得每一個子空間內(nèi)的算法數(shù)據(jù)結(jié)構(gòu)改變不會影響到其它子空間內(nèi)的數(shù)據(jù)，從而提高了算法的效率和魯棒性。通過論證前綴擴展的特性，提出了對一級線性索引表進行快速添加、刪除及更新的方法。在分析算法核心數(shù)據(jù)結(jié)構(gòu)——二分搜索樹的構(gòu)建形式之后，提出了兩種構(gòu)建二分搜索樹的方案，進一步優(yōu)化了算法執(zhí)行的平均效率。還針對BSH算法中更新效率較差的缺點，設(shè)計了附加于原算法數(shù)據(jù)結(jié)構(gòu)之上的新數(shù)據(jù)結(jié)

8、構(gòu)——BMP樹，使得算法的更新效率得到了顯著的提高。ABSH算法的設(shè)計充分考慮了IPv6網(wǎng)絡(luò)環(huán)境和分組格式的特點，使其更加適用于IPv6路由器分組轉(zhuǎn)發(fā)過程中的路由表搜索模塊。最后，編寫程序用軟件實現(xiàn)了ABSH路由表搜索算法，并且通過對測試數(shù)據(jù)與BSH算法的比較，驗證了在IPv6環(huán)境下ABSH算法的搜索和更新效率都遠遠優(yōu)于BSH算法，即使執(zhí)行大規(guī)模路由表的搜索任務，該算法仍可保持優(yōu)異的性能。 3.在深入淺出的闡明IP分組分類問題之

9、后，分析了幾種常見的基于IPv4的IP分組分類算法，比較了這幾種算法在搜索時間復雜度和空間復雜度方面的差別，詳細論述了其中一類廣泛應用的IP分組分類算法——元組空間搜索算法，針對該算法在IPv6協(xié)議體系結(jié)構(gòu)下面臨的挑戰(zhàn)，并且基于論文工作在路由表搜索算法方面做出的貢獻，提出了一種改進的元組空間搜索算法，通過ABSH算法針對IP分組分類問題和元組空間搜索算法中剪裁過程的需要進行的修改，提高了元組空間搜索算法剪裁的效率。相比元組空間搜索算法原