域間路由協(xié)議,域間路由協(xié)議的內(nèi)容有哪些?

當(dāng)前Internet被劃分為多個(gè)自治系統(tǒng)，自治系統(tǒng)是一個(gè)實(shí)體，一般是指隸屬于一個(gè)管理機(jī)構(gòu)的路由器集合。每個(gè)自治系統(tǒng)可以制定自己的路由策略。自治系統(tǒng)內(nèi)部的路由器通過域內(nèi)路由協(xié)議彼此交換路由信息，一般域內(nèi)路由協(xié)議分為距離向量協(xié)議和鏈路狀態(tài)協(xié)議，前者以RIP代表，后者常用的有OSPF、IS-IS協(xié)議；自治系統(tǒng)邊界路由器通過域間路由協(xié)議交換路由信息，目前Internet上的域間路由協(xié)議事實(shí)標(biāo)準(zhǔn)是BGP-4協(xié)議。

BGP-4協(xié)議軟件的總體設(shè)計(jì)

如圖1所示，作者從功能上把協(xié)議軟件分為Init，Event Generator，F(xiàn)SM，Message Parser，Routing Information Processor，Protocol Messager和I/O等7個(gè)模塊，還有Config和RIB兩個(gè)數(shù)據(jù)庫.為了提高處理效率，減輕系統(tǒng)負(fù)擔(dān)，整個(gè)軟件設(shè)計(jì)為單進(jìn)程結(jié)構(gòu)，各個(gè)模塊之間的交互采用函數(shù)調(diào)用和數(shù)據(jù)交換的方式.下面簡(jiǎn)單敘述各個(gè)模塊的功能.

圖1　BGP-4協(xié)議實(shí)現(xiàn)總體結(jié)構(gòu)圖

Init：對(duì)用戶配置文件或控制臺(tái)輸入進(jìn)行分析，從中讀取BGP-4協(xié)議軟件運(yùn)行時(shí)所需的各項(xiàng)參數(shù)，同時(shí)進(jìn)行語法和語義檢查，把正確的參數(shù)寫入Config數(shù)據(jù)庫中，供其他模塊在運(yùn)行時(shí)檢索引用；之后初始化全局?jǐn)?shù)據(jù)結(jié)構(gòu)（如事件隊(duì)列、時(shí)鐘鏈等），并為某些結(jié)構(gòu)分配空間；最后向FSM發(fā)送Start事件，啟動(dòng)FSM模塊，進(jìn)而使整個(gè)協(xié)議軟件開始運(yùn)行.

Event Generator：生成事件，從而驅(qū)動(dòng)FSM模塊.這些事件包括通過I/O模塊收到BGP報(bào)文以及檢測(cè)到TCP連接成功或失敗，通過檢查時(shí)鐘鏈得到時(shí)鐘超時(shí)事件.本模塊還負(fù)責(zé)維護(hù)事件隊(duì)列和時(shí)鐘鏈，提供對(duì)這些數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的函數(shù)接口.

FSM：接收模塊Init和Event Generator送來的事件，作為有限狀態(tài)機(jī)的輸入，產(chǎn)生狀態(tài)變遷及相應(yīng)動(dòng)作，控制Message Parser模塊的運(yùn)行.本模塊還通過I/O模塊負(fù)責(zé)TCP連接的建立，同時(shí)還通過Event Generator產(chǎn)生新的事件.

Message Parser：對(duì)收到的4種BGP-4報(bào)文進(jìn)行正確性檢查和分析.如果是UPDATE報(bào)文，還要通過調(diào)用模塊Routing Information Processor更新路由信息數(shù)據(jù)庫RIB，調(diào)用模塊Protocol Messager向相鄰的內(nèi)部BGP網(wǎng)關(guān)發(fā)送協(xié)議報(bào)文.本模塊還在FSM的控制下，周期性地掃描路由器中的全局路由表，向相鄰的外部BGP網(wǎng)關(guān)廣播本地路由表的變化情況.

Routing Information Processor：從Message Parser模塊中得到要撤銷的和聲明為有效的路由，更新路由信息庫RIB.為了減小RIB的規(guī)模，提高處理效率，這里還對(duì)RIB中的路由進(jìn)行合并和壓縮.另外，本模塊還提供了對(duì)RIB中的數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的所有函數(shù).

Protocol Messager：對(duì)4種BGP報(bào)文進(jìn)行格式化，并調(diào)用I/O模塊將其發(fā)出.

I/O：直接調(diào)用操作系統(tǒng)提供的TCP服務(wù)接口，完成TCP連接的建立和釋放；接收相鄰BGP網(wǎng)關(guān)送來的報(bào)文，提交給上層模塊；接收上層模塊發(fā)來的格式化為字節(jié)流的BGP報(bào)文，發(fā)送給相應(yīng)的BGP網(wǎng)關(guān).此外，對(duì)這些操作中產(chǎn)生的相應(yīng)事件，本模塊還通過Event Generator發(fā)送給FSM.

Config：存放BGP協(xié)議軟件運(yùn)行時(shí)所需的各項(xiàng)配置參數(shù).這些參數(shù)可能來自配置文件，也可以由用戶通過控制臺(tái)輸入.

RIB：存放所有協(xié)議軟件所產(chǎn)生和要利用的路由信息的數(shù)據(jù)庫.實(shí)際上分為3個(gè)相互獨(dú)立的數(shù)據(jù)結(jié)構(gòu)：Adj-RIBs-In存放從其他BGP網(wǎng)關(guān)收到的路由信息，Loc-RIB存放路由器中本地路由表的映射，Adj-RIBs-Out存放向相鄰BGP網(wǎng)關(guān)廣播過的路由信息.

由于BGP-4協(xié)議是一個(gè)比較復(fù)雜的動(dòng)態(tài)路由協(xié)議，因此在實(shí)現(xiàn)中遇到了許多難點(diǎn).主要有：如何在連接數(shù)比較多的情況下保證系統(tǒng)的效率，如何保證路由信息的及時(shí)交換，如何支持可變長(zhǎng)地址掩碼和如何保證I/O的效率等.

BGP-4協(xié)議軟件的實(shí)現(xiàn)策略和優(yōu)化

（1）　單進(jìn)程體系結(jié)構(gòu)

在高性能路由器中要同時(shí)運(yùn)行多個(gè)路由協(xié)議軟件并且要維護(hù)很大的路由表.如果BGP-4在設(shè)計(jì)時(shí)采用傳統(tǒng)的多進(jìn)程體系結(jié)構(gòu)，那么當(dāng)連接數(shù)比較多時(shí)，進(jìn)程數(shù)會(huì)很多，勢(shì)必影響整個(gè)路由器系統(tǒng)的效率.為了提高系統(tǒng)效率，BGP-4軟件設(shè)計(jì)時(shí)沒有采用多進(jìn)程結(jié)構(gòu)，而是采用了單進(jìn)程結(jié)構(gòu).這樣雖然提高了效率，但是也增加了實(shí)現(xiàn)的難度.為了在一個(gè)進(jìn)程中實(shí)現(xiàn)本來需要多個(gè)進(jìn)程完成的工作，我們把整個(gè)軟件設(shè)計(jì)成事件驅(qū)動(dòng)方式，所有的系統(tǒng)操作和收發(fā)幀都通過向軟件發(fā)送事件來進(jìn)行.而軟件的FSM模塊則不停的輪詢事件隊(duì)列，如果有事件則處理，如果沒有事件，軟件自動(dòng)休眠2秒，這也是為了提高系統(tǒng)的效率.

（2）　基于二叉樹的支持可變長(zhǎng)掩碼的路由表

為了便于路由的查找、更新及合并，同時(shí)支持可變長(zhǎng)掩碼，作者把BGP-4協(xié)議軟件中的3種路由表（Adj_RIBs_In，bgpIGP，Adj_RIBs_Out）都設(shè)計(jì)為二叉數(shù)結(jié)構(gòu).這3種二叉數(shù)的結(jié)構(gòu)和意義都大體相同.每個(gè)有效節(jié)點(diǎn)表示一條路由，從根到該節(jié)點(diǎn)的路徑表示此路由可達(dá)的目的網(wǎng)絡(luò)，其中左右子樹表示“0”或“1”，路徑長(zhǎng)度表示子網(wǎng)掩碼的長(zhǎng)度.這樣可以方便地表示變長(zhǎng)掩碼的網(wǎng)絡(luò)，同時(shí)還可以大大加快路由表的查找速度，因?yàn)闊o論路由表的規(guī)模有多大，最多32次比較就可以找到某路由（通常情況下比較次數(shù)要少得多）.此外，路由的插入、刪除和合并操作也可以高效地實(shí)現(xiàn).

（3）　基于靜態(tài)數(shù)組的時(shí)鐘隊(duì)列

時(shí)鐘鏈?zhǔn)且粋€(gè)按照超時(shí)順序由近到遠(yuǎn)排序的時(shí)鐘鏈表，各模塊啟動(dòng)的時(shí)鐘都按序插入到此表中.判斷是否有時(shí)鐘超時(shí)，只要從鏈表頭節(jié)點(diǎn)（最先超時(shí)的時(shí)鐘）開始，把當(dāng)前時(shí)刻與此節(jié)點(diǎn)超時(shí)時(shí)刻比較，小于則說明此時(shí)鐘已超時(shí)，發(fā)送超時(shí)事件.為了加快處理速度和減輕插入負(fù)擔(dān)，作者把時(shí)鐘鏈設(shè)計(jì)為靜態(tài)鏈表的結(jié)構(gòu).如下所示：

typedef struct_timerItem {

bgpTime timeout_val;

bgpPeer×peer;

int ev;

int next; 　 int last;

} timerItem;

typedef struct_bgpTimerChain {

int av_head;

timerItem timer［BGPMAXTIMER］;

} bgpTimerChain;

每個(gè)時(shí)鐘用一個(gè)timerItem結(jié)構(gòu)表示，其中timeout_val記錄超時(shí)時(shí)刻，peer記錄此時(shí)鐘對(duì)應(yīng)哪個(gè)網(wǎng)關(guān)，ev是超時(shí)后要發(fā)送的事件，last和next分別指向鏈表中的前后節(jié)點(diǎn).時(shí)鐘鏈結(jié)構(gòu)bgpTimerChain中av_head指向當(dāng)前未分配時(shí)鐘構(gòu)成的空閑鏈表的頭節(jié)點(diǎn).初始時(shí)，所有未分配時(shí)鐘構(gòu)成一個(gè)大的空閑鏈表.啟動(dòng)時(shí)鐘時(shí)只要把此節(jié)點(diǎn)摘下，插入時(shí)鐘鏈的相應(yīng)位置，并返回時(shí)鐘號(hào).因?yàn)闀r(shí)鐘在數(shù)組timer中的位置不會(huì)變化，所以關(guān)閉時(shí)鐘時(shí)可以通過時(shí)鐘號(hào)把此節(jié)點(diǎn)直接摘下，放入到空閑鏈表中.

（4）　基于單進(jìn)程體系結(jié)構(gòu)的I/O模塊設(shè)計(jì)

BGP-4協(xié)議建立在TCP層之上，利用TCP協(xié)議軟件提供的服務(wù)接口完成建立連接和發(fā)送報(bào)文的工作.I/O模塊便是協(xié)議軟件中與TCP服務(wù)接口進(jìn)行交互的部分.為了盡量減少系統(tǒng)開銷，作者把整個(gè)BGP-4協(xié)議軟件設(shè)計(jì)為單進(jìn)程結(jié)構(gòu)，這樣就加大了I/O模塊的設(shè)計(jì)難度.因?yàn)橥ǔ５脑O(shè)計(jì)思路是為每個(gè)BGP連接生成一個(gè)獨(dú)立進(jìn)程，TCP調(diào)用采用阻塞模式，調(diào)用后等待，直到成功或失敗而返回，各進(jìn)程之間互不影響；但是在單進(jìn)程結(jié)構(gòu)中，與所有相鄰網(wǎng)關(guān)的交互都在同一進(jìn)程內(nèi)執(zhí)行，如果仍用阻塞模式，就會(huì)由于一個(gè)連接的等待而使其他連接的交互掛起，從而使協(xié)議失敗.因此，所有TCP調(diào)用必須立即返回，不管其運(yùn)行狀態(tài)如何.之后再定期輪詢檢查各個(gè)連接的當(dāng)前運(yùn)行狀態(tài)，如有變化則通過Event Generator向FSM發(fā)送相應(yīng)事件.這也是采用事件驅(qū)動(dòng)機(jī)制的原因之一.

為了在輪詢時(shí)檢查哪些連接在等待哪些狀態(tài)，需要設(shè)立一些集合以記錄等待某狀態(tài)的連接.這里共有3種集合：

A、 等待建連響應(yīng)的集合.這里記錄那些已經(jīng)發(fā)出連接請(qǐng)求，正在等待對(duì)方響應(yīng)的連接號(hào).判斷連接是否建立好實(shí)際上是通過檢測(cè)此連接是否可寫完成的；

B、 等待主動(dòng)連接的集合.這里記錄已經(jīng)bind成功，正在等待對(duì)方發(fā)起主動(dòng)連接請(qǐng)求的連接號(hào).因?yàn)槔肨CP服務(wù)可以監(jiān)聽來自所有地址的連接請(qǐng)求，所以這個(gè)集合中實(shí)際上只有一個(gè)連接號(hào)，即bind調(diào)用成功后返回的連接號(hào).判斷是否有主動(dòng)連接請(qǐng)求到來是通過檢測(cè)此連接是否可讀（readable）完成的；

C、 等待數(shù)據(jù)到來的集合.這里記錄連接已正常建立且進(jìn)入Established狀態(tài)，等待接收對(duì)方報(bào)文的連接號(hào).判斷是否有數(shù)據(jù)到來也是通過檢測(cè)此連接是否可讀完成的.

為了在檢查到狀態(tài)變化時(shí)向某狀態(tài)機(jī)發(fā)送事件，還需要設(shè)置一個(gè)連接號(hào)到bgpPeer結(jié)構(gòu)指針的映射表.實(shí)際上，輪詢檢查和發(fā)送事件是在Event Generator模塊中實(shí)現(xiàn)的.下面著重講一下TCP連接建立和數(shù)據(jù)發(fā)送的實(shí)現(xiàn).

（5）　TCP連接的建立

這里采用了與BSD Socket兼容的一系列TCP調(diào)用來完成連接的建立.實(shí)際上，這里并不等待連接建立的完成，而只是在調(diào)用結(jié)束后把返回的連接號(hào)置入相應(yīng)的集合中待以后輪詢事件時(shí)檢測(cè).

（6）　數(shù)據(jù)的發(fā)送

由于數(shù)據(jù)發(fā)送也采用了無阻塞方式，而且沒有設(shè)立等待發(fā)送完成的連接集合，因此，要在發(fā)送過程中累計(jì)實(shí)際發(fā)送的字節(jié)數(shù)，直到全部發(fā)送完為止.通常TCP協(xié)議軟件在實(shí)現(xiàn)時(shí)，先把待發(fā)送數(shù)據(jù)拷入系統(tǒng)緩沖區(qū)中，然后再逐步發(fā)送給遠(yuǎn)端.因此，提供給用戶的數(shù)據(jù)發(fā)送接口不會(huì)發(fā)生阻塞.這樣，采用“全部發(fā)送完為止”的方式便不會(huì)影響協(xié)議軟件對(duì)其他TCP連接的響應(yīng).另外，在發(fā)送數(shù)據(jù)的過程中也會(huì)檢測(cè)到TCP連接失敗或關(guān)閉等事件，這時(shí)要通過Event Generator發(fā)送給相應(yīng)的FSM.