金飛蔡/JIN Feicai2

徐明偉/XU Mingwei1

（1.清華大學(xué)，北京100084；2.中興通訊股份有限公司，廣東深圳518057）

由于互聯(lián)網(wǎng)發(fā)展的歷史原因，以傳輸控制協(xié)議（TCP）/網(wǎng)際協(xié)議（IP）為核心的互聯(lián)網(wǎng)模型將“盡力而為”的可達性作為網(wǎng)絡(luò)的首要任務(wù)，這使得報文攜帶的目的地址在路由過程中成為了唯一的決定因素。這種僅依靠目的地址的路由方式，大大限制了對報文轉(zhuǎn)發(fā)控制的靈活性。并且隨著互聯(lián)網(wǎng)規(guī)模的迅速增長和用戶業(yè)務(wù)的多樣化，傳統(tǒng)路由協(xié)議越來越難以滿足許多業(yè)務(wù)對服務(wù)質(zhì)量的要求。

陸續(xù)出現(xiàn)的多協(xié)議標(biāo)簽交換（MPLS）[1]、軟件定義網(wǎng)絡(luò)（SDN）[2]等技術(shù)，試圖尋找除目的地址之外的新的路由計算維度。MPLS通過標(biāo)簽交換提前建立好一條專門的轉(zhuǎn)發(fā)路徑，指定的流量可以按照MPLS建立的路徑進行傳輸，然而這種源路由方式存在的安全性差、復(fù)雜性高以及開銷大等問題，使得網(wǎng)絡(luò)服務(wù)提供商（ISP）部署MPLS的積極性不高。SDN徹底解放了路由計算維度的限制，最新的OpenFlow協(xié)議[3]支持44個匹配域，能夠?qū)崿F(xiàn)對網(wǎng)絡(luò)流量的精細控制；但是這也造成了SDN流表空間爆炸的問題，使得SDN擴展性不高，另外集中式控制方式降低了網(wǎng)絡(luò)的魯棒性，因而廣泛部署SDN仍是一個很漫長的過程[4]。

域間路由是互聯(lián)網(wǎng)路由體系結(jié)構(gòu)的重要構(gòu)成部分，自治系統(tǒng)（AS）之間構(gòu)成的域間路由具有管控難度大、路由因素復(fù)雜等特點。由于可擴展性等原因，MPLS、SDN等方案在域間難以實際部署，當(dāng)前廣泛應(yīng)用的域間路由協(xié)議仍然是邊界網(wǎng)關(guān)協(xié)議（BGP）[5]，那么能否在傳統(tǒng)BGP的基礎(chǔ)上，實現(xiàn)更加靈活的轉(zhuǎn)發(fā)控制？

本文設(shè)計了一種基于BGP的域間二維路由方案，其在進行路由決策的時候，不僅僅考慮目的地址，而且考慮了源地址，這一思想彌補了傳統(tǒng)BGP中源地址語義缺失的問題，可以實現(xiàn)對網(wǎng)絡(luò)流量更加細粒度的控制，為滿足用戶和ISP的多樣化需求提供了新的解決方案。整個方案包括控制層和數(shù)據(jù)層，控制層主要是協(xié)議設(shè)計，基于現(xiàn)有的多協(xié)議BGP（MPBGP）[6]進行擴展，實現(xiàn)二維路由信息的傳遞、管理和使用，并保證二維路由協(xié)議與傳統(tǒng)路由協(xié)議的兼容性；數(shù)據(jù)層面主要是給出了支持二維匹配域的轉(zhuǎn)發(fā)表結(jié)構(gòu)方案，并進行了存儲空間壓縮。

1 二維路由簡介

1.1 二維路由的概念

二維路由是一種新型路由協(xié)議，它在進行路由決策的時候，不僅僅考慮目的地址，還要考慮源地址。傳統(tǒng)路由協(xié)議中，去往相同目的地址的報文的下一跳往往是相同的（不考慮等價多路徑）；但是在二維路由中，目的地址相同、源地址不相同的報文，其下一跳可能不同。二維路由的這種特性帶來2方面的好處：一是流量控制的粒度變細，網(wǎng)絡(luò)管理者可以更加靈活地管理網(wǎng)絡(luò)，如進行流量調(diào)度、策略路由等；二是用戶的多樣化需求可以被更好地滿足，例如：享受專門的轉(zhuǎn)發(fā)通道等。

本文介紹的是基于BGP的域間二維路由設(shè)計方案，它可以利用路徑屬性（如本地優(yōu)先級和多出口分辨器）實現(xiàn)二維路由策略。簡單來說，域間二維路由為所有可達的目的地址前綴設(shè)置一套默認的路徑屬性，然后再為<目的地址前綴，源地址前綴>這樣的前綴對兒設(shè)置專門的路徑屬性，這種設(shè)置只作用于對應(yīng)的前綴對兒，這樣就可以生成一條區(qū)別于默認方式的轉(zhuǎn)發(fā)路徑。

1.2 域間二維路由的應(yīng)用場景

本節(jié)通過2個例子來展示文中提出的域間二維路由的應(yīng)用場景，每個場景都用域間二維路由來解決傳統(tǒng)網(wǎng)絡(luò)遇到的難題。

圖1所示是一個多宿主場景，一個站點同時與2個上游ISP相連接，分別用ISP0和ISP1表示。其中ISP0為該站點分配地址前綴為P0的地址，ISP1為該站點分配地址前綴為P1的地址，因而網(wǎng)絡(luò)中的終端系統(tǒng)具有2個地址，其中地址A屬于P0，地址B屬于P1。在傳統(tǒng)的路由協(xié)議中，對于去往同一個目的地址的報文，無論終端系統(tǒng)使用地址A或是B作為源地址，其都將會被轉(zhuǎn)發(fā)至同一個上游ISP，假設(shè)是ISP0，此時，如果ISP0實施了源地址過濾機制，則有可能將來自源地址B的報文過濾掉，從而造成丟包。使用域間二維路由，可以根據(jù)報文的源地址選擇合適的出口路由，即來自源地址P0的報文將會通過路由器E0轉(zhuǎn)發(fā)至ISP0，來自源地址P1的報文將會通過路由器E1轉(zhuǎn)發(fā)至ISP1，從而保證了多宿主環(huán)境下正常的數(shù)據(jù)通信。

圖2所示是一個負載均衡場景，網(wǎng)絡(luò)中有2個源端AS，分別帶有地址前綴Ps1和Ps2，還有1個目的端AS，帶有地址前綴Pd，源端AS和目的端AS通過中間的ISP相連。默認情況下，2個源端AS發(fā)出的報文可能選擇了同一個ISP出口，如路由器E2，這樣可能會造成與E2相關(guān)聯(lián)的設(shè)備或鏈路負載比較重，而E3則負載很輕，出現(xiàn)了網(wǎng)絡(luò)負載不均衡的情況。負載不均衡會造成網(wǎng)絡(luò)應(yīng)對突發(fā)問題的容忍性下降、資源利用率降低等問題。使用域間二維路由，可以區(qū)分報文的源地址，為不同的源端AS選擇不同的出口路由，比如源前綴為Ps1的報文通過E2到達目的端AS，源前綴為Ps2的報文通過E3到達目的端AS，從而實現(xiàn)負載均衡。

圖1 多宿主環(huán)境下的域間二維路由應(yīng)用

圖2 負載均衡場景下的域間二維路由應(yīng)用

2 域間二維路由協(xié)議設(shè)計

2.1 基于BGP的二維路由動態(tài)學(xué)習(xí)過程

傳統(tǒng)的BGP是通過4種報文完成路由信息交互的，分別為：OPEN、KEEPALIVE、 UPDATE 和NOTIFICATION。假設(shè)路由器A向路由器B已經(jīng)建立了TCP鏈接，此時路由器A向路由器B發(fā)送OPEN報文，攜帶自己的協(xié)議版本等信息，如果路由器A在約定時間內(nèi)（計時器計時）收到路由器B返回的OPEN報文，路由器A就會向路由器B發(fā)送KEEPALIVE報文保持剛剛建立的連接。如果在另一約定時間內(nèi)路由器A收到對端發(fā)送的KEEPALIVE報文，則進入ESTABLISHED狀態(tài)，在此狀態(tài)下兩個路由器可以任意傳送UPDATE報文來更新路由或者撤銷路由。整個過程中，路由器可以通過NOTIFICATION報文報告可能出現(xiàn)的錯誤信息。

基于BGP的二維路由協(xié)議與傳統(tǒng)BGP的信息交互過程一樣，只不過需要對信息交互報文進行必要的擴展，使其能夠支持二維路由相關(guān)信息的傳遞。另外為了能夠支持二維路由的增量部署，在設(shè)計BGP二維路由協(xié)議的時候，需要保證二維路由協(xié)議與傳統(tǒng)路由協(xié)議的兼容。在本文中，我們是基于MP-BGP實現(xiàn)的域間二維路由協(xié)議。

域間二維路由器建立協(xié)議連接時，會向?qū)Χ寺酚善髌浒l(fā)送攜帶二維路由標(biāo)識的OPEN報文。如果對端路由器支持域間二維路由則回復(fù)攜帶有相同標(biāo)識的OPEN報文，如果對端路由器不支持二維路由即無法識別標(biāo)識信息，則返回常規(guī)的OPEN報文。發(fā)起連接的域間二維路由器會根據(jù)返回的OPEN報文是否攜帶特定標(biāo)識來識別和記錄對端路由器是否支持二維路由，將來二維路由相關(guān)信息只會發(fā)給建立連接的二維路由器，而不會發(fā)給傳統(tǒng)路由器。

進入ESTABLISHED狀態(tài)后，域間二維路由器間使用UPDATE報文傳遞網(wǎng)絡(luò)層可達信息（NLRI），該信息位于MP-BGP的可選屬性MP_REACH_NLRI 和MP_UNREACH_NLRI的 NLRI字段，域間二維路由擴展了該字段使其除了包含目的地址信息外，還包含源地址信息。與傳統(tǒng)MP-BGP類似，MP_REACH_NLRI負責(zé)攜帶二維路由更新信息，MP_UNREACH_NLRI負責(zé)攜帶二維路由撤回信息。

需要說明的是：域間二維路由在引入地址信息的時候，默認引入傳統(tǒng)路由協(xié)議中的所有一維網(wǎng)絡(luò)層可達信息，即目的地址信息，來保證最基本的可達性，在此基礎(chǔ)上可以通過路由器指令等方式引入二維的網(wǎng)絡(luò)層可達信息，實現(xiàn)進一步的二維路由策略。域間二維路由協(xié)議的選路規(guī)則同傳統(tǒng)BGP相同，傳統(tǒng)BGP的屬性例如本地優(yōu)先級等在域間二維路由協(xié)議中同樣適用。此外，當(dāng)需要使用AGGREGATOR等屬性進行路由聚合的時候，只聚合目的地址而不用不聚合源地址[7]。

2.2 基于BGP的二維路由的報文設(shè)計

域間二維路由協(xié)議的報文設(shè)計主要是涉及OPEN報文和UPDATE報文，剩余的KEEPALIVE報文和NOTIFICATION報文不做修改，保持與傳統(tǒng)路由協(xié)議一致。

2.2.1 域間二維路由協(xié)議OPEN報文

域間二維路由協(xié)議的OPEN報文跟原始的OPEN報文結(jié)構(gòu)基本一致，不同點在于前者需要通過可選參數(shù)字段攜帶二維路由標(biāo)識。本文中我們通過定義新的子地址族標(biāo)識來作為二維路由標(biāo)識，子地址族標(biāo)識位于報文可選參數(shù)部分Capability屬性包含的多協(xié)議擴展字段，具體攜帶方式如圖3所示。該標(biāo)識的具體數(shù)值需要向互聯(lián)網(wǎng)數(shù)字分配機構(gòu)（IANA）進行申請。

2.2.2 域間二維路由協(xié)議UPDATE報文

域間二維路由協(xié)議的UPDATE報文用于通知對端路由器有新的路由條目需要更新和撤銷，協(xié)議格式同MP-BGP類似。域間二維路由協(xié)議使用可選屬性MP_REACH_NLRI更新路由，使用可選屬性MP_UNREACH_NLRI撤銷路由，其中可選屬性MP_REACH_NLRI字段結(jié)構(gòu)如圖4所示，其子地址族標(biāo)識需要使用同OPEN報文一樣的二維路由標(biāo)識，另外其包含的NLRI字段（即圖4中網(wǎng)絡(luò)層可達信息字段）需要進行擴展。原始的NLRI字段只存放目的地址長度和目的地址前綴信息，域間二維路由協(xié)議對該字段擴展后，還存放了源地址長度和源地址前綴信息，擴展后的NLRI字段結(jié)構(gòu)如圖5所示。MP_UNREACH_NLRI字段結(jié)構(gòu)與MP_REACH_NLRI字段一致，不在此贅述。

圖3 域間二維路由的OPEN報文結(jié)構(gòu)圖

3 域間二維路由轉(zhuǎn)發(fā)層方案

域間二維路由器收到報文時，不僅需要匹配目的地址，還要匹配源地址，因而轉(zhuǎn)發(fā)表需要有2個地址匹配域。實際上，只有通過二維路由配置生成的轉(zhuǎn)發(fā)表項才需要二維的匹配，其他由傳統(tǒng)路由方式（僅基于目的）生成的轉(zhuǎn)發(fā)表項只需要匹配目的地址。一個很直接的轉(zhuǎn)發(fā)層設(shè)計方案為：路由器分配2個轉(zhuǎn)發(fā)表，一個是二維轉(zhuǎn)發(fā)表，另一個是傳統(tǒng)的一維轉(zhuǎn)發(fā)表。當(dāng)路由器收到報文時，需先在二維轉(zhuǎn)發(fā)表中進行最長前綴匹配，二維的最長前綴匹配規(guī)則是：先進行目的地址的最長前綴匹配，然后在匹配結(jié)果中進行源地址的最長前綴匹配，若找到匹配的表項，則終止查找，若無匹配表項，則尋找下一個最長前綴匹配的目的地址，然后再進行源地址的最長前綴匹配，這樣重復(fù)下去直到找到匹配結(jié)果或查完所有表項[8]。如果在二維轉(zhuǎn)發(fā)表中找到匹配表項，就按照其下一跳轉(zhuǎn)發(fā)報文，否則就查找傳統(tǒng)的一維轉(zhuǎn)發(fā)表。一維轉(zhuǎn)發(fā)表的查找只進行目的地址的最長前綴匹配。這樣的轉(zhuǎn)發(fā)層設(shè)計十分簡潔，但存在一個問題：當(dāng)二維路由策略很多時，就會生成很多的二維轉(zhuǎn)發(fā)表項，消耗大量的轉(zhuǎn)發(fā)表空間。轉(zhuǎn)發(fā)表一般使用三態(tài)內(nèi)容尋址存儲器（TCAM）實現(xiàn)高速匹配，但是TCAM成本高、能耗高，大大限制了二維轉(zhuǎn)發(fā)表的空間大小。

圖5 域間二維路由網(wǎng)絡(luò)層可達信息字段的結(jié)構(gòu)圖

幸運的是：楊術(shù)等人提出的企業(yè)轉(zhuǎn)發(fā)表結(jié)構(gòu)（FISE）[9]能夠較好地解決該問題。FISE結(jié)合TCAM和靜態(tài)隨機存取存儲器（SRAM）壓縮了二維轉(zhuǎn)發(fā)表所需的TCAM空間，同時保證報文的線速處理。

如圖6所示，新型的轉(zhuǎn)發(fā)表結(jié)構(gòu)FISE有2張TCAM表和2張SRAM表。一張TCAM表存儲目的表，每條表項是一個目的前綴到目的索引號的映射；另一張TCAM表存儲源表，每條表項是一個源前綴到源索引號的映射。一張SRAM表存儲所有轉(zhuǎn)發(fā)規(guī)則的下一跳的索引號，該表被稱為二維（TD）表，表里的每個單元格被稱為TD單元。通過一個目的索引號和一個源索引號，可以定位到一個TD單元并獲得一個下一跳索引號。另一張SRAM表中存儲了下一跳索引號和下一跳接口信息之間的映射關(guān)系，該表被稱為映射表，它能緩解下一跳信息占用存儲空間過大、冗余信息過多的問題。

圖6 FISE的結(jié)構(gòu)圖

圖7 FISE的查找流程圖

可以看到：FISE將二維轉(zhuǎn)發(fā)表的大部分開銷從TCAM中移到了SRAM中。這是因為SRAM要比TCAM便宜得多（TCAM成本大概是SRAM的10～100倍），能耗也相對低得多（TCAM能耗大概是SRAM的幾十倍到100倍）。FISE借助TCAM的高速匹配和SRAM的空間壓縮大大降低了二維轉(zhuǎn)發(fā)表的開銷并保證了匹配性能。

圖7展示了FISE的查找流程。當(dāng)一個報文到達時，F(xiàn)ISE首先在TCAM中分別匹配目的前綴和源前綴，通過目的表和源表可得指向TD單元的目的索引號和源索引號，最后利用TD單元存儲的下一跳索引號，在映射表中查找到下一跳的信息。

4 結(jié)束語

本文中我們提出了一個基于BGP的域間二維路由的設(shè)計方案，域間二維路由在進行路由決策的時候同時考慮目的地址和源地址，實現(xiàn)了靈活的流量控制，能夠滿足用戶的多樣化需求。本文中我們設(shè)計了域間二維路由協(xié)議的控制層，使用MPBGP的可選屬性攜帶二維路由的配置信息，同時兼容傳統(tǒng)路由協(xié)議，方便ISP進行增量部署。我們還給出了適用于域間二維路由的數(shù)據(jù)層設(shè)計，使用前人提出的FISE轉(zhuǎn)發(fā)表結(jié)構(gòu)，可以解決二維轉(zhuǎn)發(fā)表造成的TCAM空間爆炸的問題。整體而言，域間二維路由是一種新型路由方式，靈活和細粒度的流量控制使得其具有很好的應(yīng)用前景。