ip路由技術(shù)綜述

《ip路由技術(shù)綜述》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、IP路由技術(shù)綜述因特X的高速增長(zhǎng)給路由系統(tǒng)帶來(lái)了巨大的壓力。IP路由查找操作已經(jīng)成為路由器轉(zhuǎn)發(fā)性能乃至因特X整體性能的主要瓶頸之一。本文通過(guò)深入研究業(yè)界提出的關(guān)于IP路由的多種解決方案，提出了IP路由未來(lái)的發(fā)展方向。關(guān)鍵詞：因特X；IP；路由查找；一、IP協(xié)議簡(jiǎn)介　　IP(InterProtocol)協(xié)議是TCP/IP協(xié)議族中兩個(gè)最重要的協(xié)議之一。IP協(xié)議是以信息包為基礎(chǔ)的協(xié)議，位于OSI七層模型中的X絡(luò)層，同時(shí)還有地址解析協(xié)議ARP，逆地址解析協(xié)議RARP，Inter控制報(bào)文協(xié)議ICMP(InterControlMessageProtocol)與之配套使

2、用。Ip協(xié)議通過(guò)計(jì)算機(jī)X絡(luò)交換數(shù)據(jù)、處理尋址、分割、拼接及協(xié)議信號(hào)分解，它是所有其他IP協(xié)議套件的基礎(chǔ)?！　P協(xié)議工作在X絡(luò)層，它與數(shù)據(jù)鏈路層形成了鮮明的對(duì)比。X絡(luò)層的功能是將源端發(fā)出的分組經(jīng)各種途徑送到目的端，數(shù)據(jù)鏈路層僅將數(shù)據(jù)幀從導(dǎo)線(xiàn)的一端送到其另一端。可見(jiàn)X絡(luò)層是處理端到端數(shù)據(jù)傳輸?shù)淖畹讓?。因此，決定了IP路由尋址最根本的任務(wù)就是進(jìn)行地址轉(zhuǎn)換[1]?！　P協(xié)議的路由功能是由路由器實(shí)現(xiàn)的的。路由器其實(shí)是一種專(zhuān)用計(jì)算機(jī)，具有CPU、內(nèi)存和X絡(luò)接口等硬件，能在多個(gè)X絡(luò)和介質(zhì)之間提供X絡(luò)互聯(lián)的能力。一個(gè)典型的X絡(luò)，包含了一定量的局域X和廣域X，在這種路由

3、器連接的X絡(luò)中，有一個(gè)選擇最短路徑進(jìn)行通信的問(wèn)題，如果某條通道壞了，有選擇另一條通道把信息傳送出去的能力，我們稱(chēng)之為路由路徑選擇[2]。路由器工作在OSI七層模型的X絡(luò)層，它通過(guò)執(zhí)行路由算法，路徑選擇將報(bào)文分組從物理連接的一端傳送到另一端，最終實(shí)現(xiàn)點(diǎn)到點(diǎn)的通信。概括起來(lái)，路由器的基本功能有兩個(gè)：一是直接將報(bào)文發(fā)送到正確的目的地；二是維持路由器用來(lái)決定正確路徑的路由選擇表。二、IP協(xié)議的路由　　IP協(xié)議的路由功能是由路由器實(shí)現(xiàn)的的，當(dāng)路由器接收到一個(gè)報(bào)文，它抽出報(bào)文中的目的地址，然后，從目的地址中找出目的地的X絡(luò)號(hào)查找路由選擇表尋找與目的地址中X絡(luò)相匹配的項(xiàng)

4、。每個(gè)路由選擇表項(xiàng)包含了用來(lái)轉(zhuǎn)發(fā)報(bào)文的接口信息，也就是到目的地路徑中的下一個(gè)路由器的地址。路由器的第二個(gè)工作，是維持路由選擇表。這些表是由X絡(luò)管理者創(chuàng)建的，或通過(guò)與其它路由器交換路由信息創(chuàng)建。當(dāng)一個(gè)路由器初始引導(dǎo)時(shí)，它只知道與它直接相連的接口，如果X絡(luò)中的路由器正在運(yùn)行路由選擇協(xié)議，當(dāng)路由器知道與它相鄰接的路由器相連的X絡(luò)時(shí)，新的路由表表項(xiàng)將被創(chuàng)建每個(gè)路由選擇表表項(xiàng)都被標(biāo)識(shí)一個(gè)字符，該字符表示路由信息的源端。1．路由查找　　整個(gè)路由過(guò)程中，查表算法的優(yōu)劣直接影響了當(dāng)前和未來(lái)因特XX絡(luò)的整體性能。當(dāng)前，因特X的規(guī)模、鏈路速度、帶寬、流量等都呈指數(shù)級(jí)增長(zhǎng)[3]

5、，這對(duì)路由器中IP路由查找算法對(duì)大容量路由表處理的適應(yīng)性以及報(bào)文轉(zhuǎn)發(fā)查表的能力提出了更高要求。路由器是構(gòu)成因特X的中間節(jié)點(diǎn)，其轉(zhuǎn)發(fā)性能決定了因特X的整體性能。因此，IP路由查找操作已經(jīng)成為了當(dāng)前路由器轉(zhuǎn)發(fā)性能的瓶頸之一[4]。其實(shí)路由查找問(wèn)題本身很簡(jiǎn)單，但由于其對(duì)性能要求很高，因此有很大的難度。通常評(píng)價(jià)IP路由查表算法的標(biāo)準(zhǔn)主要有高速查找、內(nèi)存需求小、更新時(shí)間短、實(shí)現(xiàn)的靈活性強(qiáng)、能夠處理真實(shí)的大容量路由表以及預(yù)處理時(shí)間短等。IP路由查找方案可以分為以下幾類(lèi)：（1）基于精確匹配的改進(jìn)方案：這種方案一般效率不高，為了找到最佳結(jié)果，一般需要log2N步（N為路由

6、表項(xiàng)的數(shù)目）；（2）層次方案：這是普遍采用的一種查找方案，在BSD內(nèi)核中得到實(shí)現(xiàn)。它最壞情況下的復(fù)雜度為O（ultin等。這些算法的基本思想是根據(jù)前綴值的二進(jìn)制位構(gòu)建二叉樹(shù)，在檢索時(shí)用目標(biāo)地址作為索引，在二叉樹(shù)中遍歷；當(dāng)找到一個(gè)匹配的前綴時(shí)，將其作為到目前為止所發(fā)現(xiàn)的最長(zhǎng)前綴，繼續(xù)搜索更長(zhǎng)的匹配前綴，直到再?zèng)]有分支可以搜索時(shí)，搜索結(jié)束，此時(shí)所記錄的最長(zhǎng)前綴就是所要尋找的最長(zhǎng)前綴匹配。　　在基于多分支的算法二叉樹(shù)算法中，每個(gè)搜索步驟能夠?qū)⒌谝徊介_(kāi)始的整個(gè)232搜索空間減少一半，而多叉樹(shù)可以令每個(gè)搜索步驟減少更多的搜索空間。此類(lèi)算法的典型有LCTrie樹(shù)算法、

7、受控前綴擴(kuò)展算法?？勺兎种?shù)目的多分支Trie樹(shù)結(jié)構(gòu)，其搜索過(guò)程與二叉樹(shù)類(lèi)似，只是由一位比較變成了多位比較以決定下一步搜索的子樹(shù)?！　rinivasan對(duì)分支數(shù)目和層次數(shù)目的選取做了詳細(xì)的分析，并提出了多分支樹(shù)的一般結(jié)構(gòu)，所有基于Trie樹(shù)的算法都可以看作是該一般結(jié)構(gòu)的特例或變形。此外他還提出了前綴擴(kuò)展技術(shù)，以耗費(fèi)更多內(nèi)存為代價(jià)來(lái)避免最長(zhǎng)前綴匹配所帶來(lái)的回溯問(wèn)題。　　其它軟件算法有前綴維度上的二分搜索算法、最差性能受限的近似最優(yōu)路由查找算法、多路前綴值范圍搜索樹(shù)算法等。這些算法并不是對(duì)整個(gè)前綴地址空間進(jìn)行搜索，因此對(duì)于地址寬度的敏感性較低。前者的搜索時(shí)間

8、復(fù)雜度是O(log2yofIPAddressLookupAlgor