基于BBGGPP的域間二維路由方案

金飛蔡/JIN Feicai2

徐明偉/XU Mingwei1

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

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

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

域間路由是互聯網路由體系結構的重要構成部分，自治系統（AS）之間構成的域間路由具有管控難度大、路由因素復雜等特點。由于可擴展性等原因，MPLS、SDN等方案在域間難以實際部署，當前廣泛應用的域間路由協議仍然是邊界網關協議（BGP）[5]，那么能否在傳統BGP的基礎上，實現更加靈活的轉發控制？

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

1 二維路由簡介

1.1 二維路由的概念

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

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

1.2 域間二維路由的應用場景

本節通過2個例子來展示文中提出的域間二維路由的應用場景，每個場景都用域間二維路由來解決傳統網絡遇到的難題。

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

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

圖1 多宿主環境下的域間二維路由應用

圖2 負載均衡場景下的域間二維路由應用

2 域間二維路由協議設計

2.1 基于BGP的二維路由動態學習過程

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

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

域間二維路由器建立協議連接時，會向對端路由器其發送攜帶二維路由標識的OPEN報文。如果對端路由器支持域間二維路由則回復攜帶有相同標識的OPEN報文，如果對端路由器不支持二維路由即無法識別標識信息，則返回常規的OPEN報文。發起連接的域間二維路由器會根據返回的OPEN報文是否攜帶特定標識來識別和記錄對端路由器是否支持二維路由，將來二維路由相關信息只會發給建立連接的二維路由器，而不會發給傳統路由器。

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

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

2.2 基于BGP的二維路由的報文設計

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

2.2.1 域間二維路由協議OPEN報文

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

2.2.2 域間二維路由協議UPDATE報文

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

圖3 域間二維路由的OPEN報文結構圖

3 域間二維路由轉發層方案

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

圖5 域間二維路由網絡層可達信息字段的結構圖

幸運的是：楊術等人提出的企業轉發表結構（FISE）[9]能夠較好地解決該問題。FISE結合TCAM和靜態隨機存取存儲器（SRAM）壓縮了二維轉發表所需的TCAM空間，同時保證報文的線速處理。

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

圖6 FISE的結構圖

圖7 FISE的查找流程圖

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

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

4 結束語

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