一種按需域間路徑構(gòu)建方法＊

柳立言

（寧夏師范學(xué)院教育技術(shù)中心，寧夏 固原75600）

1 引言

在域間路由中，邊界網(wǎng)關(guān)協(xié)議BGP（Border Gateway Protocol）作為當(dāng)前Internet域間路由的事實標(biāo)準(zhǔn)，節(jié)點可以決定選擇和轉(zhuǎn)發(fā)哪些路徑，但是節(jié)點的可用路徑取決于下游節(jié)點的決策，節(jié)點無法對此過程進(jìn)行控制，故往往不能獲得其真正所需的路徑。在BGP中，盡管每個節(jié)點可能擁有多條備選路徑，但是協(xié)議要求每個路由器僅僅選取一條最優(yōu)路徑通告至鄰居節(jié)點，導(dǎo)致了某些自治域不能獲得自己需要的路徑。這種情況通過圖1的例子可以看出，在圖1中，如果源端S希望能夠擁有到達(dá)目的端D 的兩條不相交的路徑，一條作為傳輸路徑，一條作為備份路徑，在S的路由表中無法找到這樣的兩條路徑。事實上，這樣的路徑是存在的，比如，SBCEFD與SAD，SBCEFD與SAD 不與網(wǎng)絡(luò)中任何一個節(jié)點的本地策略相沖突，由于BGP中節(jié)點僅僅轉(zhuǎn)發(fā)一條最優(yōu)路徑，在節(jié)點C路徑CEFD被屏蔽了。

Figure 1 BGP routing to a destination node D圖1 BGP路由至目標(biāo)節(jié)點D

為了解決BGP可控性不高的問題，最近的研究出現(xiàn)了幾種替代BGP的備選方案，包括源路由［1～6］、overlay網(wǎng)絡(luò)［7］以及多路徑 路由［8～11］。在源路由中，端用戶擁有全網(wǎng)的拓?fù)湟晥D，可以自主選擇報文傳輸?shù)穆窂?，通過在報文的頭部加入報文路徑的方式指示中間節(jié)點將其轉(zhuǎn)發(fā)至合適的下一跳。在overlay網(wǎng)絡(luò)中，報文可以穿越中間節(jié)點提高性能或者可靠性。多路徑路由的研究剛剛起步，其主要思想為增加通告的路徑信息量，直接在底層網(wǎng)絡(luò)上構(gòu)建多條路徑。但是，當(dāng)前替代BGP的這幾種方法都存在明顯的問題：源路由的實現(xiàn)代價較大，可行性沒有得到驗證；overlay網(wǎng)絡(luò)的可擴(kuò)展性制約了其實際的應(yīng)用；多路徑路由用途較為單一，比如只是提高可靠性或者提高傳輸效率等，無法滿足用戶差異化的路徑需求。

針對域間路徑選擇過程不可控的問題，本文提出了一種按需的域間路徑構(gòu)建方法，以增強(qiáng)域間路由的可控性。為了簡便起見，在以下的討論中，用源端表示報文的發(fā)送方，也是路徑的發(fā)起者；用目的端表示報文的接收方，也是路徑的終點?？拷鼒笪脑炊说墓?jié)點稱為上游節(jié)點，靠近報文接收方的節(jié)點稱為下游節(jié)點。比如在圖1中，S是上游節(jié)點，D是下游節(jié)點。本文解決方案基于當(dāng)前域間路由的如下特性［8］：

（1）BGP協(xié)議提供的基本路徑滿足大多數(shù)節(jié)點的需求；

（2）少數(shù)的節(jié)點有著特殊的路徑需求，需要BGP提供個性化的路徑服務(wù)，例如：Avoiding、Preferring以及Disjoint，其中，Avoiding常見于避開網(wǎng)絡(luò)中某個惡意自治系統(tǒng)AS（Autonomous System）［12，13］，或者避開某條擁塞連接等。Preferring常見于希望優(yōu)先通過［14］可信節(jié)點提供的路徑。Disjoint常常用來提高網(wǎng)絡(luò)可靠性，選擇一條與已有路徑最不相交的路徑［6，7，11］，當(dāng)前的 BGP 協(xié)議無法滿足節(jié)點的個性化需求的主要原因為：BGP中每個節(jié)點的可用路徑由下游節(jié)點決定，而其無法對下游節(jié)點的選路過程進(jìn)行控制從而獲取自身所需的路徑。既然BGP協(xié)議能夠滿足網(wǎng)絡(luò)中大多數(shù)節(jié)點的需求，本文在避免對BGP協(xié)議的邏輯結(jié)構(gòu)進(jìn)行太大改變的基礎(chǔ)上，對BGP協(xié)議進(jìn)行擴(kuò)展。如果上游節(jié)點希望下游節(jié)點根據(jù)其需要選路，則在路徑選擇前上游節(jié)點需要將路徑需求提交至下游節(jié)點。主要思路如下：采用基本的BGP協(xié)議保證源端與目的端的可達(dá)性，在此基礎(chǔ)上，需要構(gòu)建特殊路徑的源端將路徑構(gòu)建請求發(fā)送至目的端，由目的端發(fā)起一個與BGP相似的網(wǎng)絡(luò)收斂過程協(xié)助源端構(gòu)建滿足需求的路徑。

本文主要貢獻(xiàn)如下：（1）對BGP［15］協(xié)議擴(kuò)展提出了基于策略的路由協(xié)議 P－BGP（Policy－based BGP）。P－BGP與BGP最大的區(qū)別在于在其通告中嵌入了更多的策略信息，嵌入的策略用來指導(dǎo)中間節(jié)點選擇滿足源端期望的路徑。

（2）通過多次的P－BGP收斂過程構(gòu)建了按需的域間路徑，并且通過實驗驗證了其具備良好的性能。相比于當(dāng)前的其他BGP替代方案，本文方法能夠構(gòu)建滿足用戶需求的路徑，并且理論上路徑的構(gòu)建數(shù)量可以任意多。除此之外，本文方法僅僅對BGP進(jìn)行了簡單修改，易于實現(xiàn)。

本文結(jié)構(gòu)如下：第2節(jié)對當(dāng)前域間路由的相關(guān)工作進(jìn)行了總結(jié)；第3節(jié)提出了P－BGP；第4節(jié)闡述了按需路徑構(gòu)建方法的主要思想以及實現(xiàn)方式；第5節(jié)為實驗以及性能分析；第6節(jié)總結(jié)全文并指出未來工作。

2 相關(guān)工作

2.1 當(dāng)前的域間路由

BGP協(xié)議［15］是當(dāng)前域間路由的事實標(biāo)準(zhǔn)，具有以下幾個特征：

（1）基于目標(biāo)：BGP通告地址塊的可達(dá)信息，并且每個路由器根據(jù)報文目的地址最長前綴匹配發(fā)送報文。不同源端發(fā)送的報文通過同一個路由器后將會采用同樣的下游路徑。

（2）單路徑路由：一個路由器從一個鄰居至多學(xué)習(xí)到一條最優(yōu)路徑，并且只能選擇向其他鄰居通告一條最優(yōu)路徑。這個特征限制了BGP通告的路徑的數(shù)量，限制了路由的適應(yīng)性。

（3）路徑向量協(xié)議：與連接狀態(tài)協(xié)議泛洪拓?fù)湫畔⒉煌氖?，BGP是一個路徑向量協(xié)議，路由器只能獲得由其鄰居通告的路徑。BGP的這個特征通過犧牲某些路徑的可達(dá)性提高了協(xié)議的可擴(kuò)展性。

（4）基于本地策略：每個域采用某些策略來決定選取哪條BGP路徑?？捎玫穆窂揭蕾囉谙掠温酚善鞯牟呗越M合。這個特征限制了每個AS有過多的路徑可以選擇。

選擇和輸出BGP路由的本地策略主要依賴于鄰居域間的商業(yè)關(guān)系。最著名的商業(yè)關(guān)系是文獻(xiàn)［16］中闡述的服務(wù)提供商－顧客（Provider－Customer）、對等（Peer）以及兄弟（Sibling）關(guān)系。在服務(wù)提供商－顧客的關(guān)系中，顧客為傳輸服務(wù)向服務(wù)商支付報酬。一般來說，服務(wù)商將從顧客處獲取的路徑向所有的鄰居通告，但是顧客僅僅將從服務(wù)商處獲取的路徑向自己的顧客通告。在端對端的關(guān)系中，兩個AS發(fā)現(xiàn)為對方的顧客傳送流量對自身都有益，一般不收取傳輸服務(wù)費。對等關(guān)系下，一般從一個對等端獲取的路徑僅僅被通告至本端的鄰居。兄弟AS一般屬于同一個組織，比如一個大的互聯(lián)網(wǎng)服務(wù)提供商ISP（Internet Service Provider），他們互相提供傳輸服務(wù)而不涉及商業(yè)關(guān)系。一旦從多個鄰居收到同一個地址前綴的通告，AS傾向使用的路徑優(yōu)先級為：顧客提供的通告、兄弟關(guān)系通告、對等關(guān)系通告、提供商提供通告。

2.2 源路由

為了構(gòu)建真正滿足用戶需求的網(wǎng)絡(luò)路徑，在過去的幾年中，部分研究者提出了源路由來提供更好的適應(yīng)性［1～6］。在源路由中，源端確定到達(dá)目的端的端至端路徑。源端發(fā)送的數(shù)據(jù)報文中包含了報文要經(jīng)過的路徑的每一跳，網(wǎng)絡(luò)中的中間節(jié)點根據(jù)報文的下一跳指示將報文發(fā)送至正確的下一跳。盡管源路由擴(kuò)大了選路的適應(yīng)性，但要在網(wǎng)絡(luò)中部署存在幾個問題：

（1）中間節(jié)點缺乏對數(shù)據(jù)的控制：在源路由中，中間節(jié)點僅僅按照報文攜帶的路徑下一跳將報文發(fā)送至下一跳，缺乏控制流量的措施，使中間節(jié)點很難基于自身的商業(yè)關(guān)系選擇路徑，這將導(dǎo)致網(wǎng)絡(luò)服務(wù)商不愿在網(wǎng)絡(luò)中部署源路由，極大地阻礙了源路由的應(yīng)用。

（2）可擴(kuò)展性：源路由需要獲取全部的網(wǎng)絡(luò)拓?fù)洹Ｍ負(fù)鋽?shù)據(jù)的快速更新將是一個難點，由于網(wǎng)絡(luò)的規(guī)模越來越大，必須將節(jié)點以及連接的變化情況快速地發(fā)送至網(wǎng)絡(luò)的每個邊界節(jié)點，這是一個極大的挑戰(zhàn)。

2.3 Overlay網(wǎng)絡(luò)

在overlay［7］網(wǎng)絡(luò)中，幾個節(jié)點在當(dāng)前Internet上形成一個虛擬拓?fù)?。?dāng)?shù)讓泳W(wǎng)絡(luò)的直接路徑存在問題時，發(fā)送節(jié)點可以將流量發(fā)送至中間節(jié)點，由中間節(jié)點轉(zhuǎn)發(fā)至目標(biāo)節(jié)點。盡管overlay有助于解決直接路徑的若干問題，但還不能大規(guī)模應(yīng)用在網(wǎng)絡(luò)中，主要原因如下：

（1）數(shù)據(jù)層過載：通過中間節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)增加了網(wǎng)絡(luò)的延時，并且消耗了網(wǎng)絡(luò)帶寬以及節(jié)點的處理能力。數(shù)據(jù)包需要通過封裝的方式進(jìn)行傳送，消耗了額外的帶寬。

（2）探測過載：為了補(bǔ)償對底層網(wǎng)絡(luò)的不可見，overlay網(wǎng)絡(luò)一般通過探測的方式推算底層路徑的性質(zhì)。當(dāng)前沒有適合大規(guī)模網(wǎng)絡(luò)的探測方式，難以在網(wǎng)絡(luò)中得到部署。

2.4 域間多路徑路由

由于BGP路由的局限性以及源路由和overlay的無法大規(guī)模實施，近年來有研究者將目光投向了域間的多路徑構(gòu)建，期望通過在底層網(wǎng)絡(luò)上直接構(gòu)建多路徑的方式提高路由的服務(wù)質(zhì)量。當(dāng)前域間多路徑的構(gòu)建方式主要有兩種：不改變BGP通過其他進(jìn)程構(gòu)建多路徑［8］和對BGP進(jìn)行擴(kuò)展使其一次通告多條路徑［11］。域內(nèi)多路徑路由MIRO（Multi－path Interdomain Routing）［8］和 D－BGP［11］是這兩種方案的典型代表。

MIRO允許節(jié)點在使用BGP默認(rèn)路由的基礎(chǔ)上通過協(xié)商的方式構(gòu)建節(jié)點間的隧道，使節(jié)點可以對流過其中的報文流進(jìn)行更多的控制。MIRO的最大優(yōu)點是不用對BGP協(xié)議進(jìn)行修改，但是不能保證滿足用戶期望的路徑總能被發(fā)現(xiàn)，并且因為采用了隧道方式傳送報文，消耗額外的網(wǎng)絡(luò)資源。DBGP提出允許BGP通告除基本路徑外的一條與基本最優(yōu)路徑最不相交的備份路徑來提高路由應(yīng)對錯誤的能力，但是其附帶的備份路徑只能夠作為最優(yōu)路徑的備份，無法用來進(jìn)行并發(fā)傳輸。

事實上，在當(dāng)前的網(wǎng)絡(luò)下，BGP提供的最優(yōu)路徑能夠滿足絕大多數(shù)用戶的需求，只有少部分用戶需要構(gòu)建特定需求的路徑［8］。在全網(wǎng)范圍內(nèi)統(tǒng)一采用多路徑的方式是一種巨大的浪費，按需的路徑構(gòu)建是一種更加合理的方法，存在特定需求的節(jié)點按需構(gòu)建特殊路徑，其他節(jié)點采用基本的BGP路徑。

3 P－BGP及其性質(zhì)

作為按需路徑構(gòu)建方法的準(zhǔn)備工作，本節(jié)對當(dāng)前的BGP協(xié)議進(jìn)行擴(kuò)展提出了P－BGP。P－BGP的主要特征為在路徑通告中增加了更多的策略項，這些添加的策略項稱為S＿P策略項。目的端可以在路徑通告時將選路的要求添加到路徑通告中的S＿P項中，指導(dǎo)中間節(jié)點選擇滿足需求的路徑進(jìn)行通告。

3.1 BGP決策分析過程

由于P－BGP的具體實現(xiàn)涉及對BGP決策過程的修改，在提出具體的P－BGP方案前，首先對BGP的路徑選擇過程進(jìn)行闡述。文獻(xiàn)［17］對ISP中常用的BGP決策過程使用的策略進(jìn)行了總結(jié)。一個ISP中的BGP路由器擁有多個到達(dá)目的地址的路徑，BGP路由器需要根據(jù)策略選擇一條最優(yōu)的路徑轉(zhuǎn)發(fā)給鄰居節(jié)點。如果沒有策略的存在，路由器將選擇一條最短的路徑轉(zhuǎn)發(fā)至鄰居。但是，為了使得網(wǎng)絡(luò)管理員能夠控制路徑選擇過程，路由通告中加入了一些特殊的屬性，允許一個路由器根據(jù)這些屬性進(jìn)行路徑的選擇。這個過程就是決策過程，包括對一系列屬性的對比。路由器依照表1的次序?qū)蜻x路徑依次對比下去。如果候選路徑擁有不同屬性值，路由器選擇最能滿足本地利益的那條路徑。如果候選路徑擁有相同的屬性值，則路由器繼續(xù)進(jìn)行下一屬性的對比，直到找到最優(yōu)路徑。比如，LocalPref屬性作為決策過程的第一步，通過更改LocalPref屬性，管理員可以選擇一條不是最短的路徑作為最優(yōu)路徑。MED屬性通常用在兩個擁有多條連接的AS間，顯示應(yīng)當(dāng)使用哪條端連接。BGP使用嚴(yán)格的排序過程使得網(wǎng)絡(luò)策略的表達(dá)更加清晰明了。

Table 1 The BGP decision attribute表1 BGP決策屬性

文獻(xiàn)［17］總結(jié)了影響ISP策略的幾種因素。（1）商業(yè)關(guān)系：常見的商業(yè)關(guān)系為服務(wù)提供商－顧客，對等以及兄弟關(guān)系。商業(yè)關(guān)系是ISP決策過程中最重要的一項因素。（2）流量工程：ISP為了調(diào)整其域內(nèi)的流量走向以達(dá)到較好的網(wǎng)絡(luò)利用率，其通過設(shè)定BGP選路參數(shù)的方式調(diào)整網(wǎng)路流量狀況。（3）可擴(kuò)展性：為了限制網(wǎng)絡(luò)路由表的大小或者是避免路由振蕩，網(wǎng)絡(luò)管理員可能將某些路徑過濾或者修改路由參數(shù)。（4）安全：為了保證路由的安全，網(wǎng)絡(luò)管理員需要將無效的路徑刪除，阻斷DDoS攻擊等，一般都是通過調(diào)整路由參數(shù)來實現(xiàn)這些目標(biāo)。

3.2 P－BGP

P－BGP與BGP最大的區(qū)別在于在路徑通告中添加了更多策略項，在P－BGP中有兩種策略可以添加到S＿P項中：路徑選擇策略和路徑取消策略。路徑選擇策略用來指導(dǎo)中間節(jié)點選擇何條路徑進(jìn)行通告；路徑取消策略用來指導(dǎo)節(jié)點有選擇地刪除路徑。表2前三項表示P－BGP中可以包含的三種路徑選擇策略，表2的最后一項為P－BGP中包含的路徑刪除策略。在當(dāng)前的P－BGP版本中暫時確定了這四種策略，在后續(xù)的研究中可以添加更多的策略。

Table 2 Path notices contained in the policy表2 路徑通告中包含的策略

由于在路徑選擇過程中涉及更多的策略，PBGP中間節(jié)點對路徑通告的處理過程也與BGP不同。在BGP中，節(jié)點如果收到路徑通告，則根據(jù)表1的決策過程選擇一條最優(yōu)的路徑通告給鄰居節(jié)點。在P－BGP中，最優(yōu)路徑不單純由本地策略決定，而是由本地策略與S＿P策略共同決定。為了將S＿P策略添加至路徑選擇過程中，同時又保留中間節(jié)點對路徑的控制能力，我們將S＿P策略在路徑選擇過程中的優(yōu)先級設(shè)定為在表1中的第一個屬性后、其他六個屬性前，即在P－BGP路徑選擇過程中參考的屬性順序為：LocalPref、S＿P屬性、AS path length、Origin type、MED、eBGP－learned over iBGP－learned、IGP cost、Router ID。

性質(zhì)1 路由節(jié)點有部署P－BGP的動機(jī)。

說明 通過對表1以及影響ISP策略的幾種因素的分析可以看到，ISP基于以下的利益關(guān)系確定通告路徑：本地的利益、下游節(jié)點的利益以及上游節(jié)點的利益。LocalPref作為最常用的屬性，較多地被ISP的管理者用來控制路由，代表域的本地的利益需求。我們認(rèn)為，AS path length屬性綜合考慮了下游節(jié)點以及上游節(jié)點的利益：AS依據(jù)AS path length屬性選擇最短的路徑，AS出于為下游節(jié)點的利益考慮，因為其采用最短路徑作為路徑性能的衡量標(biāo)準(zhǔn)，認(rèn)為最短的路徑具備最好的性能，最能滿足下游節(jié)點的需求；然而，AS path length屬性又是由下游節(jié)點設(shè)定的，下游節(jié)點在將路徑通告給鄰居時可以將AS path length值設(shè)定為一個對自身有利的值。MED屬性是AS為上游節(jié)點的利益考慮，采用有利于上游節(jié)點的路徑進(jìn)行傳送。從路徑選擇的決策過程可以看出，在決策過程中本地的利益需求被放在首位，上游節(jié)點的利益在不損害下游節(jié)點的利益基礎(chǔ)上能夠得到滿足。我們將S＿P屬性添加到BGP的決策過程中的第二項，使其位于 LocalPref屬性后，AS path length屬性前，仍然沒有打破AS選路的利益順序。LocalPref仍然處于決定過程的第一步，保證了中間AS對選路過程的絕對控制權(quán)，保證了本地的利益；如果S＿P屬性代表了上游節(jié)點的利益需求，但是其值仍然由下游節(jié)點設(shè)定，沒有打破AS選擇路徑的利益順序，S＿P屬性能夠能到AS的支持，路由節(jié)點有部署P－BGP的動機(jī)。

性質(zhì)2 P－BGP比BGP能夠提供更加差異化的路徑構(gòu)建能力。

說明 如果P－BGP路徑通告中的策略項都為空，則P－BGP退化為BGP。當(dāng)策略項不為空時，能夠構(gòu)建滿足不同需求的路徑。因此，相比于BGP，P－BGP能夠提供更加差異化的路徑構(gòu)建能力。

4 一種按需域間路徑構(gòu)建方法

本節(jié)基于多個P－BGP過程提出了按需的域間路徑構(gòu)建方法 OIPBM（On－demand Inter－domain Path Building Method）。

4.1 OIPBM主要流程

OIPBM的主要思想如下：采用現(xiàn)有網(wǎng)絡(luò)的BGP協(xié)議保證網(wǎng)絡(luò)的可達(dá)性，如果某個源端S需要構(gòu)建通向目的端D的特殊路徑，則S將路徑的構(gòu)建需求發(fā)送至D，由D發(fā)起一個全網(wǎng)的P－BGP收斂過程協(xié)助其完成特殊路徑的構(gòu)建。

Figure 2 OIPBM schematic diagram圖2 OIPBM示意圖

在OIPBM中BGP與P－BGP共存，但其相互獨立，不相互影響，如圖2所示。BGP保證網(wǎng)絡(luò)的可達(dá)性，而P－BGP則負(fù)責(zé)網(wǎng)絡(luò)中有特殊需求的節(jié)點間的特定路徑構(gòu)建。BGP過程通告網(wǎng)絡(luò)的可達(dá)性信息，使得網(wǎng)絡(luò)中需要構(gòu)建特殊路徑的節(jié)點間可以互相通信；在P－BGP中，構(gòu)建符合源端需求的特殊路徑，并且在路徑構(gòu)建成功后將網(wǎng)絡(luò)中的冗余路徑消除。在P－BGP中，需要構(gòu)建特殊路徑的源端將構(gòu)建多路徑的需求發(fā)送至目的端，請求目的端幫助其構(gòu)建滿足需求的路徑；目的端為自身生成一個別名，將別名回復(fù)至源端，同時以別名作為目的地址發(fā)起全網(wǎng)收斂過程，將所需的路徑構(gòu)建策略添加到路由通告的S＿P選項中。等到該全網(wǎng)過程收斂，源端獲得目的地址為目的端別名的滿足要求的域間路徑。由于采用了全網(wǎng)的收斂過程來協(xié)助源端構(gòu)建滿足要求的路徑，在網(wǎng)絡(luò)中產(chǎn)生了冗余路徑，發(fā)起一個額外P－BGP收斂過程將網(wǎng)絡(luò)中的冗余路由表項刪除，源端將需要保留的路徑發(fā)送至目的端，目的端發(fā)送帶有S＿P策略的路徑取消通告將網(wǎng)絡(luò)中冗余路由表項刪除。

按需域間路徑構(gòu)建方法處理流程如下：

（1）BGP全網(wǎng)信息通告，BGP的全網(wǎng)通告保證了網(wǎng)絡(luò)的可達(dá)性。

（3）D收到源端S發(fā)送的路徑構(gòu)建請求后，為自己生成一個別名D′，將別名D′發(fā)送至S。

（4）D以D′為目的端生成新的網(wǎng)絡(luò)可達(dá)性通告，并且將S所要求的路徑構(gòu)建策略嵌入到以D′為目的地址的路徑通告的S＿P選項中，發(fā)起一個P－BGP收斂過程。

（5）中間轉(zhuǎn)發(fā)節(jié)點選擇和通告最優(yōu)路徑。在目的端為D′的P－BGP過程收斂后，如果S收到目的端為D′的路徑，則S獲得了滿足其要求的路徑。

（6）S將確定采用的路徑通告至D，D以D′為目的端發(fā)起路徑取消通告，并且將路徑取消的策略嵌入到路徑通告中，將網(wǎng)絡(luò)中的冗余路徑消除。

（7）S可以根據(jù)需要重復(fù)（2）～（6）的步驟構(gòu)建任意數(shù)量的路徑。

通過（1）～（7）的步驟，源端S可以收到目的端為D以及D′的路由表項。由于S已經(jīng)知道D′為D的別名，因此其實際上擁有了到達(dá)D的滿足要求的路徑。S可以將構(gòu)建的路徑用作其希望的任何用途，不論是用作備份路徑或者并發(fā)傳輸。

4.2 一個例子

現(xiàn)在通過圖3的例子闡述按需路徑的構(gòu)建過程，S表示需要構(gòu)建路徑的源端，D表示路徑的目的端。

曾任諾貝爾物理學(xué)獎評委主任的瑞典皇家學(xué)會愛克斯朋教授，在解密諾貝爾獎評選過程時坦言：這是一個“很令人不安的、沒法再彌補(bǔ)的疏漏，趙忠堯在世界物理學(xué)家心中是實實在在的諾貝爾獎得主!”

Figure 3 BGP state diagram and OIPBM state diagram圖3 BGP狀態(tài)圖以及OIPBM狀態(tài)圖

圖3 a是BGP協(xié)議收斂后的網(wǎng)絡(luò)狀態(tài)，節(jié)點的路由表如圖3所示，其中部分路由表項被省略了。節(jié)點C的本地策略為CEFD與CAD都不違背域的商業(yè)利益，但是從路徑跳數(shù)考慮選擇路徑CAD。假設(shè)S需要向D發(fā)送大規(guī)模的實時數(shù)據(jù)，由于連接A－D的傳輸容量有限，路徑SAD不能滿足網(wǎng)絡(luò)傳輸?shù)囊?，S希望另外通過一條不通過連接A－D的路徑進(jìn)行并發(fā)傳輸，但是S查詢自身的路由表發(fā)現(xiàn)，路由表中的SAD以及SBAD兩條路徑都要通過連接A－D，不能滿足實時數(shù)據(jù)傳輸?shù)囊?。下面以S構(gòu)建不通過連接A－D 的路徑為例闡述OIPBM的消息過程。

OIPBM中由D協(xié)助源端S選擇一條不通過連接A－D的路徑。由于BGP過程與P－BGP過程相互獨立，且BGP過程已被大家所熟知，因此不對BGP收斂過程進(jìn)行過多闡述，著重闡述P－BGP的消息過程。圖3b給出了P－BGP中的網(wǎng)絡(luò)消息順序。（1）源端S與目的端D通信，S向D通報再次構(gòu)建一條新路徑p′的請求，并且標(biāo)記構(gòu)建策略為Avoiding（A－D）。（2）D 收到了源端S 的路徑構(gòu)建請求后，為自身重新生成一個別名D′，并且將D′回復(fù)至源端S。（3）以D′為目的地址發(fā)起新的PBGP收斂過程，并且在P－BGP通告的S＿P項中攜帶對新路徑的策略Avoiding（A－D）。節(jié)點A收到目的端為D′的路徑通告，發(fā)現(xiàn)新路徑不愿意通過連接A－D，則A不轉(zhuǎn)發(fā)任何路徑。節(jié)點C收到目的端為D′的路徑通告后，再根據(jù)按需域間路徑構(gòu)建處理流程的前五個步驟的選擇最終決定了CEFD作為傳輸路徑。（4）節(jié)點S在收到目的端為D′的路徑P′＝SBCEFD′后，將P′向節(jié)點D 通報，請求刪除網(wǎng)絡(luò)中的冗余路徑。（5）節(jié)點D發(fā)起冗余路由表項刪除過程。生成目的端為D′的UPDATE通告，在通告的S＿P選項中添加路徑刪除的策略except（P′），將通告向全網(wǎng)分發(fā)。節(jié)點A收到路徑取消通告后，將本地通向D′的路由表項完全刪除，并向節(jié)點S發(fā)出路徑取消通告，節(jié)點S將D′：SACFD′刪除，保留路徑D′：SBCEFD′。最終得到的網(wǎng)絡(luò)狀態(tài)如圖3c所示。由于有了節(jié)點D的預(yù)先通知，節(jié)點S知道D′是節(jié)點D 的別名，因此，節(jié)點S實際上擁有了一條不通過連接A－D 到達(dá)目標(biāo)節(jié)點D的路徑SBCEFD′。

4.3 幾個關(guān)鍵問題

4.3.1 別名的表示

從3.1節(jié)的描述中可以看到，別名在OIPBM中發(fā)揮了極其重要的作用。OIPBM采用別名尋找通向目標(biāo)地址的滿足要求的路徑。我們可以對當(dāng)前的IP地址進(jìn)行擴(kuò)充以表示別名，在IP地址后附上一個數(shù)表示該地址的第幾個別名，比如，用152.172.33.44（3）表示地址152.172.33.44的第三個別名。在構(gòu)建了滿足要求的要求路徑后，可以仿照MIRO的思路在源端與目的端間構(gòu)建隧道?；蛘唠S著多路徑要求的增多，可以對IP報文以及路由表的格式進(jìn)行修改，為其增加更多的位數(shù)，使其能夠支持別名。

4.3.2 冗余路由表項的消除

在目的地址為D′的路由過程收斂后，S實際上擁有了到達(dá)節(jié)點D 的特殊路徑P′1，P′2，…，P′n。然而造成極大浪費的是，因為采用了一個全網(wǎng)的收斂過程來構(gòu)建由S至D的路徑，網(wǎng)絡(luò)中產(chǎn)生了許多的額外路由表項，如果這些路由表項一直保留，隨著網(wǎng)絡(luò)多路徑的增多必將導(dǎo)致路由表規(guī)模的無限擴(kuò)大，影響路由表查找的性能。因此，在S至D′的路由過程收斂后，需要將網(wǎng)絡(luò)中冗余的路由表項消除。OIPBM中采用了一個額外的全網(wǎng)收斂過程來消除網(wǎng)絡(luò)中的冗余路由表項。S將確定使用的路徑P′1，P′2，…，P′n告知節(jié)點D，節(jié)點D 發(fā)出帶有S＿P策略的 UPDATE通告，將策略can＿exc（D′，P′1，P′2，…，P′n）添加到通告中的S＿P策略中，每個節(jié)點收到帶有策略的路徑取消通知后，將本地目標(biāo)地址為D′但不屬于P′1，P′2，…，P′n的路徑刪除。通過這種方式，僅僅保留源端選擇的那些路徑，將網(wǎng)絡(luò)中的冗余路由表項全部刪除。然而一個重要的問題是：如果在冗余路由表項消除的過程中發(fā)生了路徑失效，OIPBM是否能保證其正確性。

路徑的失效可能發(fā)生在三個時刻：（1）冗余消除通告從S發(fā)送至D的過程中；（2）D發(fā)出冗余消除通告后的已更新節(jié)點；（3）D發(fā)出冗余消除通告后的未更新節(jié)點。下面以圖3b為例對這三種情況分別討論：

（1）如果冗余消除消息在從S發(fā)送至D 的過程中發(fā)生了路徑失效。節(jié)點D發(fā)出冗余路徑刪除信息，節(jié)點S失去了最優(yōu)路徑，重新向D發(fā)出一個路徑構(gòu)建請求，并且在通告中附上失去了到達(dá)D′的路徑，則節(jié)點D重新發(fā)起目標(biāo)地址為D′的收斂過程。

（2）如若失效發(fā)生在D已經(jīng)發(fā)出冗余消除通告后的已更新節(jié)點。比如，在圖3b中，當(dāng)冗余更新消息處于節(jié)點A、B，且節(jié)點F、E、C已更新時連接C－E 失效，則C發(fā)出路徑取消信息，節(jié)點A、B、C、S到達(dá)D′的路由表項全都刪除，節(jié)點S失去到達(dá)D′的最優(yōu)路徑，S請求D重新構(gòu)建。

（3）如若冗余消除消息處于節(jié)點A、C時發(fā)生了連接BC的失效，則節(jié)點B、S消去通向D′的路由表項，節(jié)點S失去了通向D 的最優(yōu)路徑，S請求節(jié)點D重新構(gòu)建。

根據(jù)以上的討論我們可以看到，如果在S發(fā)出了冗余消除消息后構(gòu)建的路徑發(fā)生了失效，則都要重新開始OIPBM的第二個以及第三個全網(wǎng)收斂過程。因此，OIPBM適合用于網(wǎng)絡(luò)狀況比較穩(wěn)定、失效率不高的環(huán)境，Internet的主干網(wǎng)滿足這個條件。

5 實驗與分析

5.1 實驗方案

評價OIPBM最理想的方法是在Internet上對其進(jìn)行分析，但是這種方法的難度較大，因此我們在AS級別的拓?fù)渖戏抡鍻IPBM的性能，假設(shè)每個AS根據(jù)它和鄰居間的商業(yè)關(guān)系選擇和輸出路徑。每個AS作為一個節(jié)點對待。

實驗采用三個年份（2005年、2007年和2009年）的AS級別拓?fù)浞治鼍W(wǎng)絡(luò)規(guī)模增大對網(wǎng)絡(luò)對多路徑的影響，評價OIPBM的性能，實驗拓?fù)鋪碜杂赗outeViews［18］項目。為了推導(dǎo)AS間的關(guān)系，我們采用了Gao［16］的算法。AS拓?fù)浜蜕虡I(yè)關(guān)系的關(guān)鍵特性在表3中給出。

Table 3 Experimental data set表3 實驗數(shù)據(jù)集

5.2 選取不通過某些節(jié)點的路徑

為了進(jìn)行一個橫向的對比，我們分別考察了BGP、源路由（采用source進(jìn)行標(biāo)記）、多路徑路由（以MIRO為代表）以及OIPBM的表現(xiàn)，MIRO的設(shè)置如文獻(xiàn)［8］中所示。圖4給出了本實驗的結(jié)果，其中后綴a1、a2以及a3分別表示避免網(wǎng)絡(luò)中的一個、兩個以及三個節(jié)點的情形。實驗采用了文獻(xiàn)［8］中所述的 Respect Export Policy作為 MIRO的選路方式，即節(jié)點認(rèn)為符合其輸出策略的每條路徑都是等價的，節(jié)點在不違背其輸出策略的前提下考慮路由通告中的策略進(jìn)行路徑選擇，具體選擇哪條路徑由P－BGP通告中攜帶的期望信息決定。

Figure 4 Avoid node diagram圖4 避免節(jié)點實驗結(jié)果圖

從圖4中可以看到，在避免一個、兩個以及三個節(jié)點的情況下，OIPBM的成功率都接近于源路由，遠(yuǎn)遠(yuǎn)超過多路徑路由。特別是隨著避免的節(jié)點數(shù)目的增多，多路徑路由的成功率急劇下降，而OIPBM保持了平穩(wěn)的下降趨勢。我們認(rèn)為，這是由網(wǎng)絡(luò)中的節(jié)點連接度的分布情況決定的，在Internet中，少量的節(jié)點擁有最大的節(jié)點連接度［8］。BGP下的網(wǎng)絡(luò)路徑基本都通過這些大連接度的節(jié)點，一旦需要選擇避免這些節(jié)點的備選路徑，則MIRO通過協(xié)商的方式很難找到滿足要求的備選路徑。

5.3 選取最不相交的路徑

網(wǎng)絡(luò)中常用的另外一種選路策略為選取一條與最優(yōu)路徑不相交的路徑作為備份路徑，本文在MIRO、D－BGP以及OIPBM下實現(xiàn)了這個功能并將其結(jié)果進(jìn)行了對比。MIRO中原有跳數(shù)為2～3跳，我們放寬對其的限制，將MIRO的跳數(shù)設(shè)定為10跳，以此結(jié)果下的成功率與OIPBM進(jìn)行對比。

本文采用文獻(xiàn)［11］中計算路徑相交度的方法來度量兩條路徑的相似程度，計算方法如式（1）所示，結(jié)果越小表明兩條路徑越不相交，實驗結(jié)果如圖5所示。

Figure 5 Select a basic path and the disjoint path圖5 選擇一條與基本路徑最不相交的路徑

通過圖5可以看到，即使在MIRO已經(jīng)采用了很大的泛洪跳數(shù)的情況下，其選擇一條最不相交路徑的成功率仍然不如OIPBM。D－BGP性能介于MIRO與OIPBM之間，同樣也沒有OIPBM性能好。但是，隨著網(wǎng)絡(luò)規(guī)模的增大，MIRO、D－BGP以及OIPBM的性能都有較大的提高。

6 結(jié)束語

當(dāng)前Internet路由的可控性不夠，本文針對域間路由可控性不夠的問題，提出了一種滿足Internet要求的按需路徑構(gòu)建方式。首先在BGP路由通告報文中添加了策略信息對BGP協(xié)議進(jìn)行擴(kuò)展，擴(kuò)展后的協(xié)議稱為P－BGP。在P－BGP的基礎(chǔ)上進(jìn)一步提出了按需的域間路徑構(gòu)建方法OIPBM，OIPBM在空策略的P－BGP收斂的基礎(chǔ)上，需要構(gòu)建多路徑的源端向目的端發(fā)出請求，由目的端協(xié)助其構(gòu)建滿足需求的多路徑。OIPBM在不改變BGP邏輯正常路由過程的基礎(chǔ)上實現(xiàn)了滿足源端需求的BGP路徑構(gòu)建。

未來的工作包括擴(kuò)大OIPBM的應(yīng)用場景，與加強(qiáng)域內(nèi)路由可控性的方案結(jié)合，構(gòu)建一個可控的路由體系。

［1］ Zhu D，Gritter M，Cheriton D.Feedback based routing［J］.ACM SIGCOMM Computer Communication Review，2003，33（1）：71－76.

［2］ Kaur H T，Kalyanaraman S，Weiss A，et al.BANANAS：An evolutionary framework for explicit and multipath routing in the Internet［J］.ACM SIGCOMM Computer Communication Review，2003，33（4）：277－288.

［3］ Raghavan B，Snoeren A C.A system for authenticated policy－compliant routing［J］.ACM SIGCOMM Computer Communication Review，2004，34（4）：167－178.

［4］ Argyraki K，Cheriton D R.Loose source routing as a mechanism for traffic policies［C］∥Proc of the ACM SIGCOMM Workshop on Future Directions in Network Architecture，2004：57－64.

［5］ Yang X.NIRA：A new Internet routing architecture［C］∥Proc of the ACM SIGCOMM Workshop on Future Directions in Network Architecture，2003：301－312.

［6］ Godfrey P B，Ganichev I，Shenker S，et al.Pathlet routing［C］∥Proc of the ACM SIGCOMM 2009Conference on Data Communication，2009：111－122.

［7］ Andersen D，Balakrishnan H，Kaashoek F，et al.Resilient overlay networks［C］∥Proc of the ACM Symposium on Operating Systems Principles，2001：131－145.

［8］ Xu W，Rexford J.MIRO：Multi－path interdomain routing［C］∥Proc of the 2006Conference on Applications，Technology，Architectures，and Protocols for Computer Communications，2006：171－182.

［9］ Walton D，Retana A，Chen E，et al.Advertisement of mul－tiple paths in BGP［EB／OL］.［2012－12－17］.http：／／tools.ietf.org／html／draf－ietf－idr－add－paths－08.

［10］ Motiwala M，Elmore M，F(xiàn)eamster N，et al.Path splicing［C］∥Proc of SIGCOMM’08，2008：27－38.

［11］ Wang Feng，Gao Li－xin.Path diversity aware interdomain routing［C］∥Proc of the 28th IEEE International Conference on Computer Communications，2009：307－315.

［12］ Zlatokrilov H，Levy H.Area avoidance routing in distancevector networks［C］∥Proc of the 27th Conference on Computer Communications，2008：475－483.

［13］ Li Y，Gouda M G.The blocking option in routing protocols［C］∥Proc of the 28th IEEE International Symposium on Reliable Distributed Systems，2009：227－235.

［14］ Hu Nin，Zou Peng，Zhu Pei－dong.Based on the reputation mechanism of the inter－domain routing security coordination management approach［J］.Journal of Software，2010，21（3）：505－515.（in Chinese）

［15］ Rekhter Y，Li T，Hares S.RFC 4271，A border gateway

protocol 4（BGP－4）［S］.NY：The Internet Society，2006.

［16］ Gao L.On inferring autonomous system relationships in the Internet［J］.IEEE／ACM Transactions on Networking，2001，9（6）：733－745.

［17］ Caesar M，Rexford J.BGP routing policies in ISP networks［J］.IEEE Network，2005，19（6）：5－11.

［18］ Route Views［EB／OL］.［2005－01－27］.http：／／www.Route－Views.org.

［19］ Griffin T G，Wilfong G.An analysis of BGP convergence properties［C］∥Proc of the Conference on Applications，Technologies，Architetures，and Protocols for Computer COmmunication，1999：277－288.

附中文參考文獻(xiàn)：

［14］ 胡寧，鄒鵬，朱培棟.基于信譽(yù)機(jī)制的域間路由安全協(xié)同管理方法［J］.軟件學(xué)報，2010，21（3）：505－515.