周媛媛,陳文龍,趙成安,唐曉嵐 ,郭思聰

1(首都師范大學(xué) 信息工程學(xué)院,北京 100048)2(首都師范大學(xué) 管理學(xué)院,北京 100048)3(陸軍炮兵防空兵學(xué)院 士官學(xué)校,沈陽 110867)

1 引 言

互聯(lián)網(wǎng)單徑路由傳輸過多依賴最短路徑或最優(yōu)路徑,這種傳輸模式容易導(dǎo)致負(fù)載不均、鏈路擁塞等問題.多徑路由的提出對(duì)解決上述問題提供了幫助,但現(xiàn)有多徑路由機(jī)制在實(shí)施靈活性等方面還不夠理想.已實(shí)際部署的典型多徑傳輸機(jī)制中,多協(xié)議標(biāo)簽交換技術(shù)(MPLS)對(duì)報(bào)文的再次封裝會(huì)增加數(shù)據(jù)負(fù)載,且主要適用于運(yùn)營商自治域網(wǎng)絡(luò)；策略路由方案因?yàn)殪o態(tài)配置導(dǎo)致效率較低,也無法隨網(wǎng)絡(luò)拓?fù)錉顟B(tài)變化動(dòng)態(tài)調(diào)整.

本文針對(duì)互聯(lián)網(wǎng)的出口流量進(jìn)行優(yōu)化控制,提出網(wǎng)絡(luò)出口流量的多徑路由處理機(jī)制(MET).在傳統(tǒng)流量傳輸基礎(chǔ)上加入二維路由元素,以此控制網(wǎng)絡(luò)中外訪流量的出口網(wǎng)關(guān)及路徑的選擇.并且,針對(duì)網(wǎng)絡(luò)中發(fā)生頻率較高的單鏈路、單節(jié)點(diǎn)故障問題,提出MET的改進(jìn)方案：BMET,即通過預(yù)先為重要故障設(shè)置備份路徑并計(jì)算路徑切換點(diǎn),實(shí)現(xiàn)備份路徑的快速切換.

本文主要貢獻(xiàn)包括：1)提出了MET機(jī)制,基于二維路由高效控制外訪流量的出口網(wǎng)關(guān)；MET不增加任何報(bào)文負(fù)載,并與已有一維轉(zhuǎn)發(fā)兼容共存；2)針對(duì)網(wǎng)絡(luò)中發(fā)生頻率較高的單點(diǎn)故障問題對(duì)MET機(jī)制進(jìn)行優(yōu)化改進(jìn),通過預(yù)先計(jì)算備份路徑及最優(yōu)切換點(diǎn)位置,實(shí)現(xiàn)重要故障后的路徑快速切換,提升數(shù)據(jù)傳輸?shù)目煽啃?

本文的結(jié)構(gòu)組織如下：第2部分介紹了相關(guān)研究及背景;然后在第3部分描述MET機(jī)制的主要思想及實(shí)施辦法;在第4部分,對(duì)MET機(jī)制進(jìn)行改進(jìn),實(shí)現(xiàn)重要故障后路徑的快速切換;第5部分對(duì)MET機(jī)制進(jìn)行模擬仿真,并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析;第6部分總結(jié)了全文.

2 相關(guān)研究

多宿主方式(Multi-homing)往往被應(yīng)用于末節(jié)網(wǎng)絡(luò)中來增強(qiáng)其網(wǎng)絡(luò)連接的可靠性.文獻(xiàn)[1]將多宿主簡(jiǎn)單定義為擁有多個(gè)外部鏈接的網(wǎng)絡(luò).文獻(xiàn)[2]研究分析了多宿主網(wǎng)絡(luò),他們認(rèn)為多宿主可以顯著提高網(wǎng)絡(luò)性能,并通過大量數(shù)據(jù)證明了多宿主的可靠性.二維路由可以同時(shí)根據(jù)源地址與目的地址進(jìn)行選路,并在實(shí)現(xiàn)多宿主技術(shù)、多路徑路由等方面均具有很大的優(yōu)勢(shì).文獻(xiàn)[3]基于二維路由研究域間流量工程,利用二維路由能夠細(xì)分流量的特點(diǎn),細(xì)粒度的進(jìn)行流量調(diào)度,充分展現(xiàn)了二維路由的優(yōu)勢(shì).文獻(xiàn)[4]同樣對(duì)流量工程問題進(jìn)行了討論.

多路徑路由(MRP)因其在實(shí)現(xiàn)低能量消耗、負(fù)載均衡、避免擁塞發(fā)生等方面具有的重要作用,長(zhǎng)期以來一直是學(xué)者們研究的熱點(diǎn)話題.網(wǎng)絡(luò)中使用最多同時(shí)也最為普遍的是等價(jià)多路徑路由(ECMP[5]),ECMP沿著多個(gè)相等代價(jià)的路徑進(jìn)行流量的傳輸,雖然多個(gè)路徑可以對(duì)流量進(jìn)行分擔(dān),但其路徑選擇是靜態(tài)確定的,不能對(duì)變化的網(wǎng)絡(luò)環(huán)境及時(shí)的做出反應(yīng).文獻(xiàn)[6]對(duì)數(shù)據(jù)中心網(wǎng)絡(luò)流量進(jìn)行研究,發(fā)現(xiàn)使用ECMP算法易將多條大數(shù)據(jù)流轉(zhuǎn)發(fā)至同一鏈路,導(dǎo)致鏈路瓶頸.多路徑路由在鏈路或節(jié)點(diǎn)故障恢復(fù)方面也具有一定的意義,文獻(xiàn)[7]提出了多路由機(jī)制(MRC),通過預(yù)先計(jì)算備份路徑以確保IP網(wǎng)絡(luò)中鏈路或節(jié)點(diǎn)故障的快速恢復(fù).從負(fù)載均衡角度出發(fā),文獻(xiàn)[8]提出了一種具有負(fù)載均衡功能的多網(wǎng)關(guān)路由協(xié)議,由此均衡整個(gè)網(wǎng)絡(luò)的負(fù)載,避免擁塞的發(fā)生.文獻(xiàn)[9]設(shè)計(jì)并實(shí)現(xiàn)一種動(dòng)態(tài)負(fù)載均衡策略,并對(duì)其性能進(jìn)行驗(yàn)證.不相交的多路徑路由的提出對(duì)避免路徑之間爭(zhēng)用帶寬以及提高流量傳輸安全性產(chǎn)生了很大的作用[10,11],文獻(xiàn)[12]對(duì)MRC繼續(xù)深入研究,提出了不相交的多路由機(jī)制(D-MRC),使得求出的備份路徑互不相交.同樣基于多路徑路由,文獻(xiàn)[13]設(shè)計(jì)了分級(jí)拓?fù)淇尚艡C(jī)制,為不同級(jí)別的流量提供不同的傳輸路徑,實(shí)現(xiàn)數(shù)據(jù)的可信傳輸.

如今,由于互聯(lián)網(wǎng)的普及,網(wǎng)絡(luò)已逐漸滲透到人們的工作、生活當(dāng)中.尤其在電子商務(wù)領(lǐng)域中,即使是一個(gè)短暫的服務(wù)中斷,也會(huì)造成巨大的經(jīng)濟(jì)損失.不幸的是,由于多種原因,網(wǎng)絡(luò)故障時(shí)有發(fā)生,即使是在管理良好的網(wǎng)絡(luò)中.文獻(xiàn)[14]對(duì)IP主干網(wǎng)故障特征進(jìn)行研究,發(fā)現(xiàn)大約85%的故障為單個(gè)鏈路或路由器故障所致.傳統(tǒng)的鏈路狀態(tài)路由協(xié)議如OSPF通過鏈路狀態(tài)廣播以及路由表的重計(jì)算來應(yīng)對(duì)鏈路故障,這種反應(yīng)方式會(huì)導(dǎo)致嚴(yán)重的轉(zhuǎn)發(fā)中斷問題.針對(duì)這一情況,文獻(xiàn)[15]提出了故障不敏感路由(FIR)這種主動(dòng)式的域內(nèi)路由方法,對(duì)于任何的單鏈路故障能夠很好的處理,但是一旦遇到由單個(gè)節(jié)點(diǎn)引起的多條鏈路同時(shí)失效時(shí),則會(huì)產(chǎn)生環(huán)路.針對(duì)這個(gè)問題,文獻(xiàn)[16]基于FIR,提出了基于快速重路由的故障推理方法(FIFR),不僅可以解決單鏈路故障,也可以對(duì)單節(jié)點(diǎn)故障進(jìn)行有效的處理.為了減少故障反應(yīng)時(shí)間,IETF確定了一個(gè)框架,稱為IP快速重路由(IPFRR[17]),IPFRR基于本地路由變更和預(yù)計(jì)算繞行兩個(gè)準(zhǔn)則.文獻(xiàn)[18]提出了無環(huán)路變更的方法(LFA),LFA簡(jiǎn)單、易于部署,具有很高的商業(yè)價(jià)值.但是,大量的數(shù)值研究表明[19],LFA只能對(duì)75-85%的鏈路故障以及50-75%的節(jié)點(diǎn)故障提供保護(hù).因此,文獻(xiàn)[20]中專注于LFA故障覆蓋率的分析,提出了提高LFA故障覆蓋率的方法,即通過使用貪心算法向拓?fù)渲性黾?-4條新的鏈路,就會(huì)達(dá)到接近于LFA的完全覆蓋.

3 MET機(jī)制及實(shí)施辦法

本文針對(duì)多出口網(wǎng)絡(luò)的外訪流量進(jìn)行優(yōu)化控制,提出網(wǎng)絡(luò)出口流量的多徑路由處理機(jī)制(MET).MET可基于源、目的IP前綴指定外訪流量的出口網(wǎng)關(guān).便于分析,本文令特定接入路由器的所有外訪流量總是經(jīng)相同的邊界網(wǎng)關(guān)路由器進(jìn)行傳輸.即對(duì)于外訪流量,接入路由器會(huì)與唯一的出口網(wǎng)關(guān)綁定.

圖1 外訪流量控制示例圖Fig.1 Outgoing traffic control example

針對(duì)圖1進(jìn)行分析,令M、N為自治域的2個(gè)出口網(wǎng)關(guān),有A～F共6個(gè)接入路由器.該區(qū)域的流量策略是：A、B、D、F通過M向外傳輸流量；C、E通過N負(fù)責(zé)向外傳輸流量.

二維轉(zhuǎn)發(fā)的重要優(yōu)勢(shì)就是與現(xiàn)有一維轉(zhuǎn)發(fā)不沖突.對(duì)于網(wǎng)絡(luò)中最普遍使用的出口網(wǎng)關(guān),服務(wù)的流量仍使用現(xiàn)有一維轉(zhuǎn)發(fā)完成對(duì)外傳輸,從而減少二維轉(zhuǎn)發(fā)的部署,降低各項(xiàng)代價(jià).

定義 1.令自治域中默認(rèn)出口網(wǎng)關(guān)為DEr,自治域的外訪流量默認(rèn)情況基于一維轉(zhuǎn)發(fā)傳輸?shù)紻Er.

DEr基于傳統(tǒng)域內(nèi)路由協(xié)議在自治域中發(fā)布外部IP前綴,無法獲得二維轉(zhuǎn)發(fā)傳輸服務(wù)的外訪流量都經(jīng)DEr傳輸.圖1中,經(jīng)出口網(wǎng)關(guān)M負(fù)責(zé)最多的外訪流量傳輸,可設(shè)置M為DEr,所以A、B、D、F的外訪流量基于一維轉(zhuǎn)發(fā)傳輸.

定義 2.令提供二維轉(zhuǎn)發(fā)服務(wù)的出口網(wǎng)關(guān)為TEr,它可為外訪流量提供高性能或特定功能的轉(zhuǎn)發(fā)服務(wù)(區(qū)別于DEr).自治域中,TEr提供服務(wù)的流量基于二維轉(zhuǎn)發(fā)傳輸?shù)絋Er.

由于不同出口網(wǎng)關(guān)提供二維轉(zhuǎn)發(fā)傳輸服務(wù)時(shí),相互之間沒有任何影響,所以本節(jié)分析單個(gè)出口網(wǎng)關(guān)的二維轉(zhuǎn)發(fā)設(shè)計(jì),二維轉(zhuǎn)發(fā)基于OSPF協(xié)議擴(kuò)展來實(shí)施.二維轉(zhuǎn)發(fā)機(jī)制的主要設(shè)計(jì)思想如下：首先,TEr配置其服務(wù)的二維轉(zhuǎn)發(fā)流量,以源、目的IP前綴對(duì)描述外訪流量；然后,TEr發(fā)布二維LSA消息通告自治域內(nèi)節(jié)點(diǎn),路由節(jié)點(diǎn)根據(jù)收到二維LSA部署二維轉(zhuǎn)發(fā)項(xiàng),構(gòu)建二維轉(zhuǎn)發(fā)路徑.

上述過程中,若沿用現(xiàn)有的洪泛機(jī)制發(fā)送二維LSA通告,各項(xiàng)代價(jià)較大.由于每個(gè)二維轉(zhuǎn)發(fā)項(xiàng)總是針對(duì)特定源IP前綴部署,只需自治域中的部分路由節(jié)點(diǎn)對(duì)其關(guān)注.因此,針對(duì)每個(gè)二維轉(zhuǎn)發(fā)項(xiàng),可以先計(jì)算出自治域內(nèi)接受服務(wù)的特定用戶到指定出口網(wǎng)關(guān)的最優(yōu)路徑,并沿該最優(yōu)路徑的逆路徑進(jìn)行二維LSA消息的發(fā)布.該方法可以在最小范圍通告鏈路狀態(tài)信息,減少控制層開銷,實(shí)現(xiàn)二維轉(zhuǎn)發(fā)路徑的高效建立.而且,每個(gè)二維轉(zhuǎn)發(fā)項(xiàng)只在部分路由節(jié)點(diǎn)存儲(chǔ)也可降低數(shù)據(jù)層的二維轉(zhuǎn)發(fā)項(xiàng)存儲(chǔ)開銷.

令自治域網(wǎng)絡(luò)表示為G,其中,R為路由器集合,E表示鏈路集合.令提供二維轉(zhuǎn)發(fā)服務(wù)的出口網(wǎng)關(guān)為TEr,接受服務(wù)的接入路由器為ACr,PS是接受該服務(wù)的用戶IP前綴(源IP)集合,PS對(duì)應(yīng)的子網(wǎng)經(jīng)接入路由器連入互聯(lián)網(wǎng),PD是該轉(zhuǎn)發(fā)服務(wù)的可達(dá)目的IP前綴集合.通過報(bào)文源IP和目的IP對(duì)目標(biāo)流量進(jìn)行描述,該流量集合表示為：

(1)

定義 3.令A(yù)Cr到TEr最優(yōu)二維轉(zhuǎn)發(fā)路徑(最短路徑)記為：Path(ACr,TEr)={r1,r2,…,rm},其中r1=ACr,rm=TEr.

由于任意2個(gè)節(jié)點(diǎn)間的往返路徑經(jīng)過的節(jié)點(diǎn)相同,所以,二維LSA消息發(fā)布的路徑即為ACr到TEr最優(yōu)二維轉(zhuǎn)發(fā)路徑的逆路徑,即Path-(ACr,TEr)={rm,rm-1,…r1}.其中r1=ACr,rm=TEr.

圖2 構(gòu)建二維轉(zhuǎn)發(fā)路徑示例拓?fù)銯ig. 2 Example topology of building a two-dimensional forwarding path

圖2為構(gòu)建最優(yōu)二維轉(zhuǎn)發(fā)路徑示例拓?fù)?其中,令s為ACr,d為TEr.則二維轉(zhuǎn)發(fā)路徑為s-a-e-f-c-d,二維LSA消息發(fā)布路徑為d-c-f-e-a-s.構(gòu)建二維轉(zhuǎn)發(fā)路徑時(shí),d首先發(fā)送二維LSA通告到c,c接收到LSA通告后,生成下一跳為d的二維轉(zhuǎn)發(fā)項(xiàng),并且繼續(xù)向f發(fā)布此二維LSA.后續(xù)節(jié)點(diǎn)同理構(gòu)建二維轉(zhuǎn)發(fā)路徑.

4 MET優(yōu)化

現(xiàn)有互聯(lián)網(wǎng)中,由于路由器損壞、網(wǎng)絡(luò)維護(hù)、配置錯(cuò)誤等多種原因?qū)е碌木W(wǎng)絡(luò)故障仍時(shí)有發(fā)生.文獻(xiàn)[14]對(duì)于IP骨干網(wǎng)中的故障特征進(jìn)行研究,發(fā)現(xiàn)網(wǎng)絡(luò)中大約85%的故障為單個(gè)鏈路或路由器故障所致.為此,本文針對(duì)最優(yōu)二維路徑中最易發(fā)生的單個(gè)鏈路及節(jié)點(diǎn)故障問題預(yù)先計(jì)算備份路徑,并研究分析故障發(fā)生后兩路徑間切換的最佳節(jié)點(diǎn).以此達(dá)到在盡量少的節(jié)點(diǎn)中部署二維轉(zhuǎn)發(fā)項(xiàng),減小控制層開銷并提升部署效率.

MET中,一旦網(wǎng)絡(luò)狀態(tài)發(fā)生變化,如：增加新的節(jié)點(diǎn)/鏈路或刪除已有的節(jié)點(diǎn)/鏈路,會(huì)由TEr觸發(fā)二維轉(zhuǎn)發(fā)路徑的維護(hù).此時(shí),需要注意將路徑切換對(duì)數(shù)據(jù)傳輸?shù)挠绊懡抵磷畹?本文主要分以下2種情況分析：

1)若有更優(yōu)轉(zhuǎn)發(fā)路徑出現(xiàn),可待新路徑構(gòu)建完成后再撤除當(dāng)前轉(zhuǎn)發(fā)路徑；

2)若現(xiàn)有轉(zhuǎn)發(fā)路徑發(fā)生故障,則必定導(dǎo)致數(shù)據(jù)傳輸出現(xiàn)一段時(shí)間的中斷.因此,本文設(shè)計(jì)了針對(duì)重要故障的備份路徑快速切換機(jī)制.

4.1 確定重要節(jié)點(diǎn)及鏈路

現(xiàn)有網(wǎng)絡(luò)中,單鏈路故障或單個(gè)路由器所引發(fā)的故障發(fā)生頻率極高.通過一段時(shí)間對(duì)網(wǎng)絡(luò)的監(jiān)控觀察,可以很容易找出網(wǎng)絡(luò)中某路徑中最易發(fā)生故障的鏈路及節(jié)點(diǎn).由于其對(duì)網(wǎng)絡(luò)影響較大,我們稱其為重要鏈路、重要節(jié)點(diǎn),并將重要鏈路或重要節(jié)點(diǎn)所引發(fā)的故障稱為重要故障.

定義 4.令二維轉(zhuǎn)發(fā)路徑Path(ACr,TEr)的鏈路集合為ETP,路徑中最易發(fā)生故障的鏈路為重要鏈路：Ie,有Ie∈ETP.

定義 5.令二維轉(zhuǎn)發(fā)路徑Path(ACr,TEr)的節(jié)點(diǎn)集合為RTP,路徑中最易發(fā)生故障的節(jié)點(diǎn)為重要節(jié)點(diǎn)：Ir,Ir∈RTP.令它的直連鏈路集合為Eco{Ir}.

4.2 計(jì)算備份路徑及路徑的切換

針對(duì)區(qū)域中發(fā)生可能性較大的單鏈路故障、單節(jié)點(diǎn)故障的問題,我們通過為重要鏈路、重要節(jié)點(diǎn)設(shè)置備份路徑的方法來解決.

令B-Path(ACr,TEr)為自治域內(nèi)去除重要鏈路或重要節(jié)點(diǎn)后,ACr到TEr的最優(yōu)路徑,我們稱B-Path(ACr,TEr)為二維轉(zhuǎn)發(fā)路徑Path(ACr,TEr)的備份路徑.其中,B-Path(ACr,TEr) ={rb1,rb2,…rbm},rb1=ACr,rbm=TEr.

若為重要鏈路故障,則更新拓?fù)浔硎緸椋?/p>

若為重要節(jié)點(diǎn)故障,則更新拓?fù)浔硎緸椋?/p>

定義 6.令STr為路徑切換負(fù)責(zé)節(jié)點(diǎn),即二維轉(zhuǎn)發(fā)路路徑Path(ACr,TEr)以及備份路徑B-Path(ACr,TEr)在故障發(fā)生時(shí)的關(guān)鍵切換點(diǎn).

圖3 備份路徑更換拓?fù)銯ig.3 Path switching topology

STr滿足2個(gè)約束條件：1)它是2條轉(zhuǎn)發(fā)路徑的公共節(jié)點(diǎn)；2)它在2條路徑中的轉(zhuǎn)發(fā)下一跳不同.

即：(STr=rpi=rbj)∧(rpi+1≠rbj+1).

顯然,只要備份路徑存在,就必定存在STr.Path(ACr,TEr)中,STr一定出現(xiàn)在ACr到Ir或者Ie的直連節(jié)點(diǎn)之前,它可能是ACr,但一定不會(huì)是TEr.

圖3為備份路徑更換拓?fù)涫纠?其中,圖3(a)、圖3(b)為鏈路(c,e)發(fā)生故障時(shí)備份路徑更新拓?fù)鋱D.圖3(c)、圖3(d)為節(jié)點(diǎn)e發(fā)生故障時(shí)的示例圖.可以看到,當(dāng)故障發(fā)生時(shí),不是由ACr進(jìn)行二維轉(zhuǎn)發(fā)路徑與備份路徑之間的切換,而是由距離故障鏈路或節(jié)點(diǎn)更為相近的帶陰影節(jié)點(diǎn)完成此項(xiàng)操作,這樣不僅可以減少數(shù)據(jù)轉(zhuǎn)發(fā)量,更可以很大程度上縮短收斂時(shí)間,達(dá)到二維轉(zhuǎn)發(fā)路徑與備份路徑之間的快速切換.

4.3 下發(fā)針對(duì)備份路徑的二維轉(zhuǎn)發(fā)項(xiàng)

和最優(yōu)二維轉(zhuǎn)發(fā)路徑一樣,我們同時(shí)也針對(duì)備份路徑上的部分節(jié)點(diǎn)下發(fā)二維轉(zhuǎn)發(fā)項(xiàng),一旦重要鏈路或重要節(jié)點(diǎn)發(fā)生故障,只需STr獲知該網(wǎng)絡(luò)狀態(tài)發(fā)生的變化,即可完成二維轉(zhuǎn)發(fā)路徑的快速切換.

RTP表示最優(yōu)二維轉(zhuǎn)發(fā)路徑上的所有節(jié)點(diǎn)的集合,RB-TP表示備份二維路徑上所有節(jié)點(diǎn)的集合.令集合RB-deploy表示備份路徑上需要進(jìn)行二維轉(zhuǎn)發(fā)項(xiàng)部署的節(jié)點(diǎn)集,滿足：RB-deploy=RB-TP-RTP+{STr}.

需要對(duì)RB-deploy中所有節(jié)點(diǎn)下發(fā)二維轉(zhuǎn)發(fā)項(xiàng).其中,STr只是存儲(chǔ)針對(duì)RB-TP的二維轉(zhuǎn)發(fā)項(xiàng),并不生效.一旦重要鏈路/節(jié)點(diǎn)發(fā)生故障,只需STr獲知該網(wǎng)絡(luò)狀態(tài)所發(fā)生的變化,就可以迅速完成二維轉(zhuǎn)發(fā)路徑的切換.即,路徑切換負(fù)責(zé)節(jié)點(diǎn)STr刪除針對(duì)RTP的二維轉(zhuǎn)發(fā)項(xiàng),并使RB-TP的二維轉(zhuǎn)發(fā)項(xiàng)生效.圖3(a)中,針對(duì)s到d的二維轉(zhuǎn)發(fā)項(xiàng),c節(jié)點(diǎn)生效的下一跳節(jié)點(diǎn)為e,當(dāng)c感知到c-e鏈路故障,立刻將下一跳切換為m.易知,STr為最后一個(gè)同時(shí)出現(xiàn)在2個(gè)有序集合中的節(jié)點(diǎn).

STr節(jié)點(diǎn)的算法如下,即在RTP和RB-TP中,尋找最后一個(gè)同時(shí)出現(xiàn)在2個(gè)有序集合中的節(jié)點(diǎn).

Algorithm1.CalculationofSTr

Node*switch_node(RTP,RB-TP)

{

Get the first node ofRTP：r1;

Get the first node ofRB-TP：r2;

While(r1==r2)

{

STr=r1;

r1=r1->next;

r2=r2->next;

}

returnSTr;

}

5 實(shí)驗(yàn)評(píng)估

1條二維轉(zhuǎn)發(fā)項(xiàng)所占存儲(chǔ)空間包括：4字節(jié)源IP網(wǎng)段、4字節(jié)目的IP網(wǎng)段、4字節(jié)下一跳地址、1字節(jié)源IP子網(wǎng)掩碼長(zhǎng)度、1字節(jié)目的IP子網(wǎng)掩碼長(zhǎng)度、2字節(jié)出接口號(hào),共計(jì)16字節(jié).令自治域中路由節(jié)點(diǎn)數(shù)：NA=|R|.給定1條二維轉(zhuǎn)發(fā)項(xiàng),需要部署的節(jié)點(diǎn)數(shù)為：NT,其占用存儲(chǔ)空間為16*NT.對(duì)于普通MET機(jī)制,需進(jìn)行二維轉(zhuǎn)發(fā)項(xiàng)部署的節(jié)點(diǎn)數(shù)為：NT= |Rp|.對(duì)于改進(jìn)的MET機(jī)制(BMET),需進(jìn)行二維轉(zhuǎn)發(fā)項(xiàng)部署的節(jié)點(diǎn)數(shù)為：NT= |Rbp|.顯然,使用優(yōu)化的MET方法需要進(jìn)行二維轉(zhuǎn)發(fā)項(xiàng)部署的節(jié)點(diǎn)數(shù)更多.同時(shí),對(duì)于不同拓?fù)渲械牟煌S轉(zhuǎn)發(fā)項(xiàng),其二維轉(zhuǎn)發(fā)路徑和備份路徑都會(huì)有所不同,部署節(jié)點(diǎn)數(shù)也不同.不過,對(duì)于OSPF現(xiàn)有洪泛鏈路狀態(tài)機(jī)制(Flooding),則會(huì)將1條二維轉(zhuǎn)發(fā)項(xiàng)在自治域中除出口路由器外的所有路由器節(jié)點(diǎn)生成,即：NT=|R|-1.

通過仿真研究MET機(jī)制與OSPF現(xiàn)有洪泛鏈路狀態(tài)機(jī)制下二維轉(zhuǎn)發(fā)項(xiàng)部署節(jié)點(diǎn)數(shù)以及內(nèi)存消耗情況.假定ACr與TEr所攜帶的IP前綴數(shù)量均為10,并將3個(gè)方法應(yīng)用于四種拓?fù)洌篈NS,Abilene,NSFNET,ARPANET[21,22].每個(gè)拓?fù)渲羞x擇10個(gè)隨機(jī)樣本,不同隨機(jī)樣本具有不同的接入路由器、默認(rèn)出口路由器以及提供二維轉(zhuǎn)發(fā)服務(wù)的出口路由器,并假定重要節(jié)點(diǎn)及鏈路.在計(jì)算每種方法需部署二維轉(zhuǎn)發(fā)項(xiàng)的節(jié)點(diǎn)數(shù)后,可分析對(duì)應(yīng)的內(nèi)存消耗情況.

圖4 針對(duì)重要節(jié)點(diǎn)故障部署二維轉(zhuǎn)發(fā)項(xiàng)所需存儲(chǔ)消耗Fig.4 Storage consumption required to deploy two-dimensional forwarding items for important node failures

圖4、圖5分別為重要鏈路故障、重要節(jié)點(diǎn)故障情況下,在4個(gè)不同拓?fù)渲惺褂肕ET、BMET以及OSPF現(xiàn)有洪泛鏈路狀態(tài)機(jī)制(Flooding)3種方法部署二維轉(zhuǎn)發(fā)項(xiàng)所需要的內(nèi)存消耗情況.OSPF現(xiàn)有洪泛鏈路狀態(tài)機(jī)制(Flooding)由于需要對(duì)二維鏈路狀態(tài)信息進(jìn)行全網(wǎng)洪泛,所以需要部署二維轉(zhuǎn)發(fā)項(xiàng)的節(jié)點(diǎn)數(shù)量最多,所需內(nèi)存消耗最大.MET方法只需在接入路由器ACr到出口路由器TEr的最優(yōu)路徑上進(jìn)行二維轉(zhuǎn)發(fā)項(xiàng)的部署,需部署節(jié)點(diǎn)數(shù)最少,因此所需內(nèi)存消耗最小.改進(jìn)的MET方法(BMET)除需要在最優(yōu)路徑上部署二維轉(zhuǎn)發(fā)項(xiàng),還需將其部署到備份路徑上.相比于MET方法會(huì)增加一定的內(nèi)存消耗.

圖5 針對(duì)重要鏈路故障部署二維轉(zhuǎn)發(fā)項(xiàng)所需存儲(chǔ)消耗Fig.5 Storage consumption required to deploy two-dimensional forwarding items for important link failures

由圖4、圖5可以看出,4種拓?fù)渲?使用我們提出的MET方法相比于OSPF現(xiàn)有洪泛鏈路狀態(tài)機(jī)制(Flooding)所需的內(nèi)存消耗情況有了明顯的改善,可以節(jié)約更多的內(nèi)存空間.而改進(jìn)的MET方法相較于普通的MET方法雖然需要更多內(nèi)存空間,但當(dāng)重要故障發(fā)生時(shí)可以很快的對(duì)故障進(jìn)行反應(yīng),切換到備份路徑,減少收斂時(shí)間.

6 總 結(jié)

本文針對(duì)互聯(lián)網(wǎng)的出口流量進(jìn)行優(yōu)化控制,提出網(wǎng)絡(luò)出口流量的多徑路由處理機(jī)制：MET.即在傳統(tǒng)流量傳輸基礎(chǔ)上加入二維路由元素,基于源、目的IP前綴實(shí)現(xiàn)更細(xì)粒度的外訪流量控制.其中,自治域內(nèi)路由器到指定出口的流量傳輸基于二維轉(zhuǎn)發(fā)實(shí)現(xiàn),因此無需考慮其與自治域內(nèi)現(xiàn)有一維轉(zhuǎn)發(fā)路徑的沖突,可提升多徑路由的實(shí)施靈活性.MET機(jī)制的部署代價(jià)主要體現(xiàn)在二維LSA消息的傳播及二維轉(zhuǎn)發(fā)項(xiàng)的部署上,針對(duì)此種情況,我們對(duì)構(gòu)建最優(yōu)二維轉(zhuǎn)發(fā)路徑進(jìn)行討論,并只沿此最優(yōu)路徑傳播二維LSA消息及進(jìn)行二維轉(zhuǎn)發(fā)項(xiàng)的部署.

此外,針對(duì)網(wǎng)絡(luò)中發(fā)生頻率較高的單鏈路、單節(jié)點(diǎn)故障問題,提出MET機(jī)制的改進(jìn)方案：BMET,即通過預(yù)先為重要故障設(shè)置備份路徑并計(jì)算路徑切換點(diǎn),實(shí)現(xiàn)備份路徑的快速切換.后續(xù),我們將對(duì)多出口網(wǎng)絡(luò)的外訪流量進(jìn)行更深入的研究.