路由交換協(xié)議路由算法

路由協(xié)議按路由算法一般劃分為距離向量協(xié)議和鏈路狀態(tài)協(xié)議兩類。距離向量協(xié)議，也稱為Bellman-Ford算法，是指使用中繼計數(shù)表示源節(jié)點到目的節(jié)點的距離，它基于下面的計算公式來計算兩個節(jié)點間距離：

D(i，i)=0

D(i，j)=min[d(i，k) D(k，j)]

其中，D(i，j)表示從節(jié)點(節(jié)點為網(wǎng)絡(luò)或路由器)i到節(jié)點j的最短路徑，d(i，k)表示從節(jié)點i到k的直接路徑，也就是說，節(jié)點i和k之間沒有中介節(jié)點。具體運算步驟如下：

①所有的路由器都建有一個路由表，使系統(tǒng)中的所有目的地址都出現(xiàn)在表中，每一個表項內(nèi)容均包括目的地址和下一站地址，記為元組(N，G)。

②路由器周期性地向鄰居發(fā)送更新分組，更新分組的內(nèi)容為路由表中的所有信息。

③鄰居路由器接收處理更新分組。設(shè)更新分組來自G'，根據(jù)更新分組計算到目的地址N的路由開銷為D'，如果D'

鏈路狀態(tài)協(xié)議，也稱最短路徑算法，其計算原理可以分為以下4個過程來描述：

①發(fā)現(xiàn)該路由器的鄰居，獲取它們的網(wǎng)絡(luò)地址，建立相鄰關(guān)系，并測量到每個相鄰路由器的開銷或延遲。建立相鄰關(guān)系是通過發(fā)送Hello分組來實現(xiàn)的。

②將用于交換的信息收集起來，構(gòu)造包含這些信息的鏈路狀態(tài)消息。創(chuàng)建鏈路狀態(tài)消息的時機分兩種，一種為定期創(chuàng)建，另一種就是當有事件發(fā)生時創(chuàng)建。

③通過flood(擴散)算法，向所有的其他路由器發(fā)送該消息。在鏈路狀態(tài)路由選擇算法中，如何可靠地發(fā)布鏈路狀態(tài)消息包是相當重要的。鏈路狀態(tài)算法實現(xiàn)的好壞在一定程度上取決于flood算法的優(yōu)劣。

④根據(jù)收集到的鏈路狀態(tài)信息，通過Dijkstra算法計算本路由器到全網(wǎng)其他路由器或網(wǎng)絡(luò)的最短距離。

鏈路狀態(tài)協(xié)議與距離向量協(xié)議相比，其優(yōu)點是基于量度值(如鏈路帶寬和時延)，而不是由中繼計數(shù)來選擇優(yōu)化路由，因此可使網(wǎng)絡(luò)負載平衡；通過鏈路狀態(tài)更新，將鏈路和節(jié)點狀態(tài)的變化情況擴散到整個網(wǎng)絡(luò)，使所有路由器馬上更新路由表，使網(wǎng)絡(luò)具有更好的收斂特性。

路由交換協(xié)議RIP

RIP(RoutingInformationProtocol)是一種距離向量協(xié)議，是當今應用最為廣泛的內(nèi)部網(wǎng)關(guān)協(xié)議。在默認情況下，RIP使用一種非常簡單的度量制度：距離就是通往目的站點所需經(jīng)過的鏈路數(shù)，取值為1～15，數(shù)值16表示無窮大。RIP進程使用UDP的520端口來發(fā)送和接收RIP分組。RIP分組每隔30s以廣播的形式發(fā)送一次，為了防止出現(xiàn)“廣播風暴”，其后續(xù)的分組將做隨機延遲后再發(fā)送。在RIP中，如果一個路由在180s內(nèi)未被刷新，則相應的距離就被設(shè)定成無窮大，并從路由表中刪除該表項。RIP分組分為兩種：請求分組和響應分組。

由于RIP1存在一些缺陷，因此RIP2試圖定義一套有效的RIP改進方案，例如子網(wǎng)路由選擇、支持無類型域間路由(CIDR，ClasslessInter-DomainRouting)、驗證機制和多點廣播等，并且還定義了過渡策略。但RIP2是一個兼容性的升級，也就繼承了RIP1的大部分缺點。

路由交換協(xié)議OSPF

為了解決RIP協(xié)議的缺陷，IETF于1998年4月在RFC2328中發(fā)布了OSPF協(xié)議的第二版(OSPFv2)。OSPF(OpenShortest-PathFirst)全稱為開放式最短路徑優(yōu)先協(xié)議，OSPF中的O意味著OSPF標準是對公共開放的，而不是封閉的專有路由方案。

OSPF采用鏈路狀態(tài)協(xié)議算法，每個路由器維護一個相同的鏈路狀態(tài)數(shù)據(jù)庫，保存整個AS的拓撲結(jié)構(gòu)(在自治系統(tǒng)不再劃分的情況下)。一旦每個路由器都有了完整的鏈路狀態(tài)數(shù)據(jù)庫之后，該路由器就可以自己為根構(gòu)造最短路徑樹，然后再根據(jù)最短路徑構(gòu)造路由表。對于大型的網(wǎng)絡(luò)，為了進一步減少路由協(xié)議通信流量，利于管理和計算，OSPF將整個自治系統(tǒng)劃分為若干個區(qū)域，區(qū)域內(nèi)的路由器維護一個相同的鏈路狀態(tài)數(shù)據(jù)庫，保存該區(qū)域的拓撲結(jié)構(gòu)。OSPF路由器相互間交換信息，但它們交換的信息不是路由，而是鏈路狀態(tài)。OSPF定義了5種分組：Hello分組用于建立和維護連接；數(shù)據(jù)庫描述分組用于初始化路由器的網(wǎng)絡(luò)拓撲數(shù)據(jù)庫，當發(fā)現(xiàn)數(shù)據(jù)庫中的某部分信息已經(jīng)過時時，路由器發(fā)送鏈路狀態(tài)請求分組，請求相鄰節(jié)點提供更新信息；路由器使用鏈路狀態(tài)更新分組來主動擴散自己的鏈路狀態(tài)數(shù)據(jù)庫或?qū)︽溌窢顟B(tài)請求分組進行響應；由于OSPF直接運行在IP層，協(xié)議本身要提供確認機制，鏈路狀態(tài)應答分組是對鏈路狀態(tài)更新分組的確認。

與其他協(xié)議相比，OSPF有許多優(yōu)點。例如，OSPF支持各種不同鑒別機制(如簡單口令驗證、MD5加密驗證等)，并且允許各個系統(tǒng)或區(qū)域采用互不相同的鑒別機制；提供負載均衡功能，如果計算到某個目的站有若干條費用相同的路由，OSPF路由器則會把通信流量均勻地分配給這幾條路由，沿這幾條路由把該分組發(fā)送出去；在一個自治系統(tǒng)內(nèi)可劃分出若干個區(qū)域，每個區(qū)域根據(jù)自己的拓撲結(jié)構(gòu)計算最短路徑，可以減少OSPF路由實現(xiàn)的工作量；OSPF屬動態(tài)的自適應協(xié)議，對于網(wǎng)絡(luò)的拓撲結(jié)構(gòu)變化可以迅速地做出反應，并進行相應調(diào)整，提供短的收斂期，使路由表盡快穩(wěn)定，并且與其他路由協(xié)議相比，OSPF在對網(wǎng)絡(luò)拓撲變化的處理過程中僅需要最少的通信流量；OSPF提供點到多點的接口，支持CIDR地址。

OSPF的不足之處就是協(xié)議本身龐大復雜，實現(xiàn)起來較RIP困難。

路由交換協(xié)議IS-IS協(xié)議

和OSPF一樣，IS-IS也包含一些子協(xié)議。其中，Hello協(xié)議用來發(fā)現(xiàn)鄰機，在廣播鏈路上選舉指派路由器；擴散協(xié)議用來在區(qū)域或主干中傳播鏈路狀態(tài)記錄。

路由交換協(xié)議IGRP

由于RIP的局限性，Cisco公司在20世紀80年代中期開發(fā)了IGRP(InteriorGatewayRoutingProtocol)，它是一個距離向量家族的路由協(xié)議。IGRP使用組合度量制式，其路由更新的每一項都包含了一組4種度量制式：延遲(D)、帶寬(B)、可靠性(R)和負載(L)。此外，它還包括2個不參與路徑計算的變量：路由中的跳數(shù)(H)和路徑MTU的計算結(jié)果。

IGRP的更新發(fā)送間隔更長(90s)，使用組合度量制式，可選擇多路徑路由、環(huán)路檢測和處理默認路由的新手段。IGRP最大的缺點是它為Cisco私有，故僅局限于Cisco產(chǎn)品，而RIP是任何平臺上IP路由的一部分。

路由交換協(xié)議EIGRP

IGRP存在的缺點是它的環(huán)路檢測會持續(xù)較長時間，且路由更新的周期性發(fā)送也會造成同樣效應。因此Cisco公司還開發(fā)了EIGRP(EnhancedlnteriorGatewayRoutingProtocol)。EIGRP仍是一個距離向量協(xié)議，使用了與IGRP相同的組合度量制式，除此之外就沒什么相似之處了。EIGRP使用了擴散計算系統(tǒng)，保持快速收斂、避免環(huán)路產(chǎn)生。EIGRP比傳統(tǒng)的距離向量協(xié)議使用更少的帶寬。這使它適用于低帶寬、高費用WAN鏈路。最重要的是，EIGRP不僅可用于IP，而且還可用于IPX和AppleTalk。

早期的互聯(lián)網(wǎng)最初采用一種外部網(wǎng)關(guān)協(xié)議(EGP，ExteriorGatewayProtocol)的。EGP是為一個簡單的樹形拓撲結(jié)構(gòu)設(shè)計的。隨著互聯(lián)網(wǎng)的迅速擴大，EGP逐漸暴露出了很多的局限性，如不能處理環(huán)路和多個網(wǎng)絡(luò)網(wǎng)狀連接等情況。為了克服EGP的局限性，IETF制定了實際上現(xiàn)已成為標準的邊界網(wǎng)關(guān)協(xié)議(BGP，BorderGatewayProtocol)。

BGP經(jīng)歷了不同的階段，從最早的版本BGP1發(fā)展到了當前的版本BGP4。BGP4是第一個支持CIDR的版本。

BGP是一種用于在自治系統(tǒng)之間傳遞路由信息的路徑向量協(xié)議。路徑向量的含義是指BGP路由消息中帶有一個自治域號碼的序列，它說明了一條路由所通過的路徑，這樣可有效地檢測并避免復雜拓撲結(jié)構(gòu)中可能出現(xiàn)的環(huán)路問題。BGP支持CIDR尋址方式，減少了路由表長度，從而加快了選路速度。另外，BGP使用TCP作為其傳輸協(xié)議(缺省端口號為179)，這保證了傳輸?shù)目煽啃裕捎诓铄e控制功能全部由TCP協(xié)議完成，因此BGP自身的實現(xiàn)就變得非常簡單。

BGP協(xié)議在TCP連接上傳送4種消息類型，包括：Open分組用來建立對等體連接；Update消息用來在BGP對等體之間傳輸路由信息；Keepalive消息用于周期性刷新對等體連接，以確保連接的有效性；Notification消息用于通知其他BGP對等體檢測到一個差錯。

BGP協(xié)議的運行分為建立對等體連接和路由更新處理兩個階段。BGP進程的對等體連接建立過程可用如圖2所示的有限狀態(tài)機模型來表示。

圖2BGP對話的有限狀態(tài)機模型

①空閑狀態(tài)：這是連接的第一階段。BGP進程等待一個通常由網(wǎng)絡(luò)管理員發(fā)出的啟動事件，然后BGP初始化資源，復位連接重試計數(shù)器，打開一個TCP連接端口，并開始監(jiān)聽可能由遠程對等體啟動的連接，若成功，就轉(zhuǎn)換到連接狀態(tài)，否則將回到空閑狀態(tài)。

②連接狀態(tài)：BGP進程等待TCP連接的建立。如果TCP連接已建立，就轉(zhuǎn)換到OPEN發(fā)送狀態(tài)，同時發(fā)送OPEN消息。如果TCP連接沒有建立，那么將轉(zhuǎn)換到行動(active)狀態(tài)。如果連接重試計時器溢出，狀態(tài)就停留在連接階段，計時器將被復位，一個TCP連接請求被啟動。

③行動狀態(tài)：BGP進程建立一個TCP連接，獲得一個對等體。若成功，則轉(zhuǎn)換為Open發(fā)送狀態(tài)，同時發(fā)送Open消息。如果TCP連接計時器溢出，那么BGP進程將重新設(shè)置計時器，并回到連接狀態(tài)。一般地，如果BGP進程的狀態(tài)在連接與行動之間來回變化，則表明存在故障，不能建立TCP連接。這可能是因為對等體的IP地址不可達。

④Open發(fā)送狀態(tài)：BGP進程等待接收來自對等體的Open消息。若收到Open消息，就對Open消息進行正確性檢查：如果沒有錯誤，就轉(zhuǎn)換為Open確認狀態(tài)，同時開始發(fā)送Keepalive消息，并且復位Keepalive時鐘；否則，發(fā)送Notification消息，轉(zhuǎn)換到空閑狀態(tài)。在這個階段，BGP進程比較對等體的自治域號碼，以確認對等體是內(nèi)部對等體還是外部對等體。

⑤Open確認狀態(tài)：BGP進程等待一個Keepalive或Notification報文。如果收到Keepalive報文，就進入對等已建立狀態(tài)，表示對等體連接已建立；如果收到Notification報文，則回到空閑狀態(tài)。

⑥已建立狀態(tài)：BGP進程與對等體交換Update或Keepalive數(shù)據(jù)包，假設(shè)Keepalive計時器的值不是零，那么當收到Update或Keepalive數(shù)據(jù)包時，計時器將復位。如果收到任何Notification報文，則說明系統(tǒng)出現(xiàn)錯誤，將就回到空閑狀態(tài)。

路由更新處理是BGP協(xié)議的核心。當BGP收到一個Update消息時，首先驗證Update數(shù)據(jù)包的有效性，若Update消息內(nèi)沒有錯誤信息，那么就調(diào)用圖3所示的路由更新處理過程。

一個Update消息或者通告一條可達路由，或者撤銷多條不再可達路由。對于不可達路由，BGP將從BGP路由表或路由信息庫的輸入路由表中刪除這些不可達路由，然后再調(diào)用決策過程處理。對于收到的可達路由信息，BGP將根據(jù)輸入路由策略進行路由過濾及屬性控制。例如，BGP要過濾從一個對等體收到的一條路徑的某個自治域號碼，為了防止流量通過該對等體到達該自治網(wǎng)絡(luò)，輸出的路由將存儲到BGP路由表或路由信息庫的輸入路由表中。

BGP決策過程基于路徑屬性值，在多條可達路由中選擇一條到達某個目的地的最佳路由。BGP協(xié)議使用的一些重要的路徑屬性包括：

①起源(Origins)：表示一條路由的起源，如由外部BGP獲取，或者由內(nèi)部路由協(xié)議輸入等。

圖3BGP路由更新處理過程

②自治系統(tǒng)路徑(AS_Path)：一條路由到達一個目的地址所經(jīng)過的一系列自治系統(tǒng)號碼。

③下一段地址(Next-hop)：到達一個網(wǎng)絡(luò)的下一跳地址。

④多出口判別(MULTI_EXIT_DISC)：用于提示進入一個多入口自治系統(tǒng)的入口優(yōu)先級。

⑤本地優(yōu)先(LOCAL_PREF)：用于自治系統(tǒng)內(nèi)部到達某一地址出口點的優(yōu)先權(quán)。

BGP決策過程分為以下幾個步驟：

①如果下一段地址是不可達的，這路由就要被忽略；

②優(yōu)先選擇最大本地優(yōu)先的路由；

③如果本地優(yōu)先相同，優(yōu)先選擇本地始發(fā)的路由；

④如果本地始發(fā)相同，優(yōu)先選擇具有最短自治系統(tǒng)路徑的路由；

⑤如果自治系統(tǒng)路徑相同，優(yōu)先選擇具有低起源屬性的路由；

⑥如果起源屬性相同，優(yōu)先選擇具有最低多出口判別屬性值的路由；

⑦如果以上情況都相同，優(yōu)先選擇可通過最近對等體到達的路由。

由以上決策過程產(chǎn)生的最佳路由是路由器本身使用的，將被存儲到BGP路由表的內(nèi)部使用路由表中，同時輸入到路由轉(zhuǎn)發(fā)表。

BGP路由表中內(nèi)部使用路由表的路由以及路由器在本地產(chǎn)生的路由需要通告給其他的對等體。在送出更新消息以前，要應用輸出策略進行路由過濾及屬性控制。例如，自治系統(tǒng)內(nèi)存在多個入口，給各個入口設(shè)置不同的多出口判別屬性來調(diào)整各個入境流量的大小。另外，還需區(qū)別內(nèi)部和外部對等體，例如從內(nèi)部對等體得知的路由不應傳送到內(nèi)部對等體。

總之，BGP協(xié)議是一種基于策略的路由協(xié)議，雖然協(xié)議本身相對簡單，但配置相當復雜，若使用不當，則有可能影響其他網(wǎng)絡(luò)。更詳細的BGP協(xié)議內(nèi)容及應用指導參見IETFRFC1771、RFC1773等。

ldp利用路由轉(zhuǎn)發(fā)表建立lsp 　ldp通過逐跳方式建立lsp時，利用沿途各lsr路由轉(zhuǎn)發(fā)表中的信息來確定下一跳，而路由轉(zhuǎn)發(fā)表中的信息一般是通過igp、bgp等路由協(xié)議收集的。ldp并不直接和各種路由協(xié)議關(guān)聯(lián)，只是間接使用路由信息。 　通過已有協(xié)議的擴展支持mpls標簽分發(fā) 　雖然ldp是專門用來實現(xiàn)標簽分發(fā)的協(xié)議，但ldp并不是唯一的標簽分發(fā)協(xié)議。通過對bgp、rsvp（resource reservation protocol）等已有協(xié)議進行擴展，也可以支持mpls標簽的分發(fā)。 　通過某些路由協(xié)議的擴展支持mpls應用 　在mpls的應用中，也可能需要對某些路由協(xié)議進行擴展。例如，基于mpls的vpn應用需要對bgp進行擴展，使bgp能夠傳播vpn的路由信息；基于mpls的流量工程te（traffic engineering）需要對ospf或is-is協(xié)議進行擴展，以攜帶鏈路狀態(tài)信息。 　lspm: lsp management

隧道技術(shù)的實質(zhì)是如何利用一種網(wǎng)絡(luò)層的協(xié)議來傳輸另一種網(wǎng)絡(luò)層的協(xié)議，其基本功能是封裝和加密，主要利用隧道協(xié)議來實現(xiàn)。封裝是構(gòu)建隧道的基本手段。從隧道的兩端來看，封裝就是用來創(chuàng)建、維持和撤銷一個隧道，來實現(xiàn)信息的隱蔽和抽象。而如果流經(jīng)隧道的數(shù)據(jù)不加密，那么整個隧道就暴露在公共網(wǎng)絡(luò)中，VPN的安全性和私有性就得不到體現(xiàn)。

網(wǎng)路隧道技術(shù)涉及了3種網(wǎng)絡(luò)協(xié)議：網(wǎng)絡(luò)隧道協(xié)議、隧道協(xié)議下面的承載協(xié)議和隧道協(xié)議所承載的被承載協(xié)議。如圖所示

隧道協(xié)議作為VPN IP層的底層，將VPN IP分組進行安裝封裝；隧道協(xié)議同時作為公用IP網(wǎng)的一種特殊形式，將封裝的VPN分組利用公網(wǎng)內(nèi)的IP協(xié)議棧進行傳輸，以實現(xiàn)隧道內(nèi)的功能。隧道協(xié)議在這個協(xié)議體系中起著承上啟下的作用。

隧道協(xié)議存在多種可能的實現(xiàn)方式，按照工作的層次，可分為兩類：一類是二層隧道協(xié)議，用于傳輸二層網(wǎng)絡(luò)協(xié)議，它主要應用于構(gòu)建撥號VPN（Access VPN）；另一類是三層隧道協(xié)議，用于傳輸三層網(wǎng)絡(luò)協(xié)議，它主要應用于構(gòu)建內(nèi)部網(wǎng)VPN（Intranet VPN）和外聯(lián)網(wǎng)（VPN Extranet VPN）。

隧道協(xié)議二層隧道協(xié)議

二層隧道協(xié)議指用公用網(wǎng)絡(luò)來封裝和傳輸二層（數(shù)據(jù)鏈路層）協(xié)議，此時在隧道內(nèi)傳輸?shù)氖菙?shù)據(jù)鏈路層的幀。工作原理如圖所示

在點到點的二層鏈路上，最常用的二層協(xié)議是PPP協(xié)議，隧道協(xié)議實現(xiàn)中，首先將IP分組封裝在二層的PPP協(xié)議幀中，也就是會所，先把各種網(wǎng)絡(luò)協(xié)議封裝在PPP中，再把整個數(shù)據(jù)包裝入二層隧道協(xié)議中。這種雙層封裝方法形成的數(shù)據(jù)包在公用網(wǎng)絡(luò)中傳輸。

第二層隧道協(xié)議具有簡單易行的優(yōu)點，但是他沒的可擴展性不太好，而且提供內(nèi)在的安全機制安全強度低，因此它們不支持企業(yè)和企業(yè)的外部客戶以及供應商之間通信的保密性需求，不適合用來構(gòu)建連接企業(yè)內(nèi)部網(wǎng)和企業(yè)的外部客戶和供應商的企業(yè)外部網(wǎng)VPN。

隧道協(xié)議三層隧道協(xié)議

三層隧道協(xié)議是用公用網(wǎng)來封裝和傳輸三層（網(wǎng)路層）協(xié)議（如IP、IPX、AppleTalk等），此時在隧道內(nèi)傳輸?shù)氖蔷W(wǎng)路層的分組。三層隧道協(xié)議并非是一種很新的技術(shù)，早已出現(xiàn)的RFC 1701 通路路由封裝協(xié)議就是一個三層隧道協(xié)議。IETF制定的IP層加密標準協(xié)議IPSec 也是一個三層速到協(xié)議，利用IPSec（ESP/AN）的隧道模式構(gòu)成的VPN隧道。三層隧道協(xié)議的協(xié)議棧如圖所示，

ANCP由GSMPv3（General Switch Management Protocol Version 3）協(xié)議承載，并對GSMPv3協(xié)議進行了擴充，增加了鄰接關(guān)系的建立與維護體制。