計算機(jī)網(wǎng)絡(luò)路由研究概述

摘要：近年來，隨著計算機(jī)網(wǎng)絡(luò)的日益普及，其現(xiàn)已成為各行各業(yè)中不可或缺的工具之一。由于互聯(lián)網(wǎng)上的IP流量增長日益加劇，當(dāng)前的互聯(lián)網(wǎng)已經(jīng)無法滿足各種IP服務(wù)的需求，為此提高服務(wù)質(zhì)量已經(jīng)勢在必行。正因如此，人們開始關(guān)注計算機(jī)網(wǎng)絡(luò)路由的研究?；诖它c，本文首先對計算機(jī)網(wǎng)絡(luò)路由進(jìn)行概述，進(jìn)而分析了路由器技術(shù)，并在此基礎(chǔ)上提出

關(guān)鍵詞：計算機(jī)網(wǎng)絡(luò)；網(wǎng)絡(luò)路由；路由器技術(shù)；路由算法

中圖分類號：TP393.02 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9599 (2012) 10-0000-02

一、計算機(jī)網(wǎng)絡(luò)路由概述

一直以來網(wǎng)絡(luò)路由都是計算機(jī)網(wǎng)絡(luò)領(lǐng)域中研究的關(guān)鍵問題?，F(xiàn)如今，計算機(jī)網(wǎng)絡(luò)的規(guī)模越來越龐大，網(wǎng)速也越來越快，各種媒體信息的傳播都離不開網(wǎng)絡(luò)這一載體，為此，對網(wǎng)絡(luò)路由提出了更高的要求，路由算法更是層出不窮，無論是何種路由算法其最終目的都是為了尋找最佳路徑對信息進(jìn)行傳遞，以此來提高服務(wù)質(zhì)量，并提高網(wǎng)絡(luò)資源的整體利用率。計算機(jī)網(wǎng)絡(luò)中的路由選擇是一個比較復(fù)雜的問題，其不僅具有組合優(yōu)化問題的性質(zhì)，而且又屬于其中的NP完全一類。由下面的例子中便可以看出這一問題的復(fù)雜性。例如，某一個網(wǎng)絡(luò)具有21個節(jié)點，每個節(jié)點對應(yīng)5條候選路由，若是采用枚舉法大約需要嘗試上億次才能夠得出全局最優(yōu)解。換言之，就算以最快的計算機(jī)進(jìn)行運(yùn)算也需要近萬年的時間，為此，只能采用近似算法或是隨機(jī)算法。

通常在研究計算機(jī)網(wǎng)絡(luò)設(shè)計中路由選擇的優(yōu)化過程中，在預(yù)先給定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及鏈路容量后，便可從中選出一條最佳的路由，進(jìn)而達(dá)到數(shù)據(jù)信息經(jīng)過網(wǎng)絡(luò)的平均時延最小的目的，這樣能夠使資源的利用率最高。計算機(jī)網(wǎng)絡(luò)路由的優(yōu)化研究開始于對通信網(wǎng)絡(luò)的分析，自此之后逐步滲透到計算機(jī)網(wǎng)絡(luò)等領(lǐng)域當(dāng)中。最初網(wǎng)絡(luò)路由的效能分析方法僅僅局限于兩個終端的問題上，近年來，隨著大型網(wǎng)絡(luò)系統(tǒng)的出現(xiàn)，使得這一分析變得更加復(fù)雜，許多新的計算方法和理論也隨之出現(xiàn)。自上世紀(jì)70年代以來，網(wǎng)絡(luò)路由的優(yōu)化理論獲得了長足的發(fā)展，大量與之有關(guān)的文獻(xiàn)資料也都相繼發(fā)表。有人提出使用條件概率的方法對路由的效能進(jìn)行求解。上世紀(jì)70年代，印度的學(xué)者雖然對原有的算法進(jìn)行了改進(jìn)，但由于需要列舉2 個狀態(tài)，從而使得該方法在復(fù)雜的網(wǎng)絡(luò)中無法適用。上世紀(jì)80年代，通過圖論中的條件概率及邊收縮原理對網(wǎng)絡(luò)路由作出了相應(yīng)的簡化，但由于實現(xiàn)的過程較為復(fù)雜，故此該方法也未獲得推廣使用。在1986時有人提出了網(wǎng)絡(luò)路由效能綜合的概念，這一概念的提出是網(wǎng)絡(luò)路由優(yōu)化的研究更具實質(zhì)性內(nèi)容，同年我國以廖炯生為代表的多為專家學(xué)者在對路由效能進(jìn)行系統(tǒng)研究的基礎(chǔ)上，提出了一些數(shù)學(xué)改進(jìn)算法，但是這些算法對于較為復(fù)雜的網(wǎng)絡(luò)路由優(yōu)化效果并不明顯。直到1998年，巴拉巴斯與其同事在對萬維網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究中發(fā)展，計算機(jī)網(wǎng)絡(luò)并不完全是隨機(jī)的，其具有一定的規(guī)律性，通過網(wǎng)絡(luò)拓?fù)鋱D能夠清晰的看出，其所產(chǎn)生的是一條遞減的曲線，而這種性質(zhì)的網(wǎng)絡(luò)被稱為無標(biāo)度網(wǎng)絡(luò)。

二、路由器技術(shù)

近年來，隨著互聯(lián)網(wǎng)的快速發(fā)展以及用戶數(shù)量的不斷增多，形式各樣的網(wǎng)絡(luò)應(yīng)用隨之不斷涌現(xiàn)，人們對于網(wǎng)絡(luò)互聯(lián)設(shè)備的安全性、穩(wěn)定性以及各方面性能的要求也越來越高。路由器作為IP網(wǎng)絡(luò)的核心設(shè)備之一，路由器技術(shù)現(xiàn)已成為網(wǎng)絡(luò)領(lǐng)域研究的重點和熱點課題，正因如此，越來越多的科研機(jī)構(gòu)開始關(guān)注路由器的發(fā)展。通常情況下，路由器是在OSI/RM的網(wǎng)絡(luò)層上工作的，其主要負(fù)責(zé)不同網(wǎng)絡(luò)之間的數(shù)據(jù)轉(zhuǎn)發(fā)、分粗以及存貯，并決定在網(wǎng)絡(luò)間傳輸數(shù)據(jù)時的路由取向，可以說路由器是實現(xiàn)網(wǎng)間互聯(lián)的必備設(shè)備之一。路由器最為基本的用途是能夠?qū)⒎珠_在多個邏輯上的網(wǎng)絡(luò)進(jìn)行連接，而該功能的實現(xiàn)需要路由器具備選擇路徑及網(wǎng)絡(luò)地址判斷的功能，這樣才能在多個網(wǎng)絡(luò)互連的環(huán)境中建立靈活的連接。路由器一般只接收其它路由傳輸過來的信息，其屬于網(wǎng)絡(luò)層中的一種互聯(lián)設(shè)備。雖然路由器能夠支持多種協(xié)議，但大部分路由都是在TCP/IP下運(yùn)行。路由器一般可連接兩個或兩個以上由IP子網(wǎng)的邏輯端口，并且至少有一個物理端口。路由器按照接收到數(shù)據(jù)包中的網(wǎng)絡(luò)層地址以及路由器內(nèi)部維護(hù)的路由表決定輸出端口以及下一跳的地址。而路由表的維護(hù)主要是通過與網(wǎng)絡(luò)上其它路由器交換路由及鏈路信息來實現(xiàn)的。路由器通常由輸入和輸出端口、路由處理器以及交換網(wǎng)絡(luò)等幾個部分組成。輸入端口既是報文接收點也是物理鏈路的連接點；輸出端口主要負(fù)責(zé)緩沖及隊列管理，同時利用復(fù)雜的調(diào)度算法能夠?qū)崿F(xiàn)QoS等功能；交換網(wǎng)絡(luò)主要負(fù)責(zé)完成輸入與輸出端口間的互聯(lián)；路由處理器則負(fù)責(zé)運(yùn)行各種路由協(xié)議及系統(tǒng)軟件，借此來實現(xiàn)維護(hù)計算轉(zhuǎn)發(fā)表以及路由表等功能，這些功能既可以通過計算機(jī)硬件予以實現(xiàn)，也可以通過相應(yīng)的軟件予以實現(xiàn)。路由器最主要的作用就是為經(jīng)過其中的每一個數(shù)據(jù)幀找到一條最佳的傳輸路徑，并通過該路徑將這些數(shù)據(jù)信息傳送至目的節(jié)點。由此可見，最佳路徑的選擇策略即路由算法就是路由器的關(guān)鍵之所在。正常情況下，路由器中會保存有與各種傳輸路徑相關(guān)的數(shù)據(jù)信息，這些數(shù)據(jù)就是我們所說的路由表，其可供路由選擇路徑時使用。在路由表中存儲著大量的子網(wǎng)信息和下一個路由器的名稱。

現(xiàn)階段，TCP/IP網(wǎng)絡(luò)基本都是利用路由器實現(xiàn)互連的，換言之，互聯(lián)網(wǎng)就是由諸多IP子網(wǎng)并以路由器進(jìn)行互連的國際性網(wǎng)絡(luò)。該網(wǎng)絡(luò)又被稱之為以路由為基礎(chǔ)的網(wǎng)絡(luò)。路由器不但負(fù)責(zé)對IP分組進(jìn)行轉(zhuǎn)發(fā)，同時還負(fù)責(zé)與其它路由的聯(lián)絡(luò)。路由動作主要包括尋找最佳路徑和轉(zhuǎn)發(fā)這兩項內(nèi)容。尋找最佳路徑通常是由路由選擇算法予以實現(xiàn)的。由于這一過程中會涉及不同的路由選擇算法及選擇協(xié)議，故此該過程相對比較復(fù)雜。為了能夠準(zhǔn)確判定出最佳路徑，路由選擇算法應(yīng)啟動并維護(hù)含有路由信息的路由表。

三、路由算法的設(shè)計原則及其分類

（一）路由算法的設(shè)計原則

路由算法是指路由問題的求解方法與步驟，是計算機(jī)網(wǎng)絡(luò)路由器的重要組成部分，采用何種算法往往能夠決定最終的尋徑結(jié)果。通常情況下，路由算法的設(shè)計應(yīng)當(dāng)遵循以下原則：

其一，最優(yōu)性原則。是指路由算法選擇最佳路徑的能力。

其二，簡潔性原則。路由算法力求設(shè)計簡潔，在確保有效功能的前提下，減少軟件開銷成本。

其三，堅固性原則。路由算法即使處于不可預(yù)料和非正常環(huán)境下，也能夠保證正常運(yùn)行。由于路由器分布于網(wǎng)絡(luò)連接點上，一旦其發(fā)生故障便會極易產(chǎn)生無法預(yù)知的嚴(yán)重后果，所以路由算法的設(shè)計必須能夠經(jīng)受時間的考驗，并確保其在網(wǎng)絡(luò)運(yùn)行環(huán)境下具備可靠性。

其四，快速收斂性原則。收斂是指在最佳路徑的判斷上所有路由器達(dá)到一致的過程。當(dāng)網(wǎng)絡(luò)發(fā)生突發(fā)事件時，會引起路由處于可用或不可用狀態(tài)。這時，路由器會發(fā)出更新信息，并將更新信息傳播至整個網(wǎng)絡(luò)，從而啟動重新計算最佳路徑的功能，直至所有路由器均處于公認(rèn)的最佳路徑，避免由于路由算法收斂慢而造成網(wǎng)絡(luò)中斷或路徑循環(huán)。

其五，靈活性原則。路由算法應(yīng)當(dāng)準(zhǔn)確、快速地適應(yīng)各種網(wǎng)絡(luò)環(huán)境，如當(dāng)某個網(wǎng)段出現(xiàn)故障時，路由算法必須及時發(fā)現(xiàn)故障，同時為該網(wǎng)段中的所有路由重新選擇最佳路徑。

（二）路由算法的分類

路由算法能夠使用多樣化的度量標(biāo)準(zhǔn)來選擇最佳路徑，復(fù)雜的路由算法可以采用多種度量來選擇路由，其常用度量包括以下幾個方面，即路徑長度、帶寬、可靠性、負(fù)載、時延、通信成本等。路由算法包括非自適應(yīng)和自適應(yīng)兩類。

1.非自適應(yīng)算法是指不測量和不利用當(dāng)前的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和交通流量，而只是通過遵循某項原則選擇路由。由于網(wǎng)絡(luò)中有中心節(jié)點，它可以依據(jù)最佳路由算法來獲取每對節(jié)點間的最佳路由，而后針對每個節(jié)點構(gòu)建固定路由表，并在網(wǎng)絡(luò)拓?fù)涓淖兊臓顟B(tài)下，重新計算和裝入路由表，或者在各個路由相關(guān)節(jié)點上人工修改路由表。

2.自適應(yīng)算法的路由主要以網(wǎng)絡(luò)當(dāng)前狀態(tài)信息為依據(jù)進(jìn)行選擇，來設(shè)法適應(yīng)不斷變化的網(wǎng)絡(luò)流量和拓?fù)浣Y(jié)構(gòu)。在自適應(yīng)路由的選擇過程中，當(dāng)前能夠提供的路由信息必須在網(wǎng)絡(luò)節(jié)點間傳送，所以，不可再用路由、改變的路由以及新的路由均可以在相應(yīng)的路由表中得以反映。為了確保自適應(yīng)路由選擇的順利實現(xiàn)，必須依靠路由選擇協(xié)議，并采取計算最短路徑的方法和定義交換路由選擇信息的方式?，F(xiàn)階段，使用最為廣泛的路由選擇協(xié)議是鏈路狀態(tài)路由選擇和距離向量路由選擇協(xié)議。鏈路狀態(tài)算法，也被稱為最短路徑算法，是指發(fā)送路由信息到互聯(lián)網(wǎng)上所有的節(jié)點。然而，就每個路由器而言，僅發(fā)送它的路由表中描述了其自身鏈路狀態(tài)的一部分，而不是全部；距離向量算法是指每個路由器將路由表全部或部分信息發(fā)送到鄰近節(jié)點上。兩種路由選擇協(xié)議的區(qū)別在于，鏈路狀態(tài)算法可以在網(wǎng)絡(luò)各處發(fā)送極少量的信息，距離向量算法是在鄰接路由器上發(fā)送大量信息。鏈路狀態(tài)算法具備較強(qiáng)的收斂性，相比較距離向量算法而言不易產(chǎn)生路由循環(huán)。此外，鏈路狀態(tài)算法具有更強(qiáng)的CPU處理能力以及更大的內(nèi)存空間，所以導(dǎo)致鏈路狀態(tài)算法的運(yùn)行成本較高。

參考文獻(xiàn)：

[1]倪縣樂，周衛(wèi)華，曾志民，丁煒.高速路由交換技術(shù)的研究及展望[J].計算機(jī)工程與應(yīng)用，2008，2

[2]劉懷亮，王東，徐國華.一種基于流量工程的網(wǎng)絡(luò)端到端性能分析算法[J].系統(tǒng)工程與電子技術(shù)，2009，3

[3]于建軍.寬帶網(wǎng)絡(luò)建設(shè)中基層交換技術(shù)的應(yīng)用探討[J].經(jīng)濟(jì)技術(shù)協(xié)作信息，2007，27

[4]王梓斌，鄭襪華，向良軍.基于專家決策的網(wǎng)絡(luò)性能管理系統(tǒng)的設(shè)計[J].電腦知識與技術(shù)，2007，4

[5]休曉明，褚慶昕，朱明英等.一種新的自相似流量模型的網(wǎng)絡(luò)性能分析[J].科學(xué)技術(shù)與工程，2007，14

[6]付方發(fā)，張慶利，王進(jìn)祥等.支持多種流量分布的片上網(wǎng)絡(luò)性能評估技術(shù)研究[J].哈爾濱工業(yè)大學(xué)學(xué)報，2007，5

[7]李旸.基于粒度計算智能的計算機(jī)網(wǎng)絡(luò)路由研究[D].安徽大學(xué)，2007，4