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

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

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

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

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

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

二、路由器技術(shù)

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

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

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

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

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

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

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

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

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

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

（二）路由算法的分類(lèi)

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

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

2.自適應(yīng)算法的路由主要以網(wǎng)絡(luò)當(dāng)前狀態(tài)信息為依據(jù)進(jìn)行選擇，來(lái)設(shè)法適應(yīng)不斷變化的網(wǎng)絡(luò)流量和拓?fù)浣Y(jié)構(gòu)。在自適應(yīng)路由的選擇過(guò)程中，當(dāng)前能夠提供的路由信息必須在網(wǎng)絡(luò)節(jié)點(diǎn)間傳送，所以，不可再用路由、改變的路由以及新的路由均可以在相應(yīng)的路由表中得以反映。為了確保自適應(yīng)路由選擇的順利實(shí)現(xiàn)，必須依靠路由選擇協(xié)議，并采取計(jì)算最短路徑的方法和定義交換路由選擇信息的方式?，F(xiàn)階段，使用最為廣泛的路由選擇協(xié)議是鏈路狀態(tài)路由選擇和距離向量路由選擇協(xié)議。鏈路狀態(tài)算法，也被稱(chēng)為最短路徑算法，是指發(fā)送路由信息到互聯(lián)網(wǎng)上所有的節(jié)點(diǎn)。然而，就每個(gè)路由器而言，僅發(fā)送它的路由表中描述了其自身鏈路狀態(tài)的一部分，而不是全部；距離向量算法是指每個(gè)路由器將路由表全部或部分信息發(fā)送到鄰近節(jié)點(diǎn)上。兩種路由選擇協(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]倪縣樂(lè)，周衛(wèi)華，曾志民，丁煒.高速路由交換技術(shù)的研究及展望[J].計(jì)算機(jī)工程與應(yīng)用，2008，2

[2]劉懷亮，王東，徐國(guó)華.一種基于流量工程的網(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]王梓斌，鄭襪華，向良軍.基于專(zhuān)家決策的網(wǎng)絡(luò)性能管理系統(tǒng)的設(shè)計(jì)[J].電腦知識(shí)與技術(shù)，2007，4

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

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

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