互聯網路由擴展性研究狀況分析

Internet的快速發展對路由擴展性造成了巨大的壓力。為了Internet能夠持續、穩定、快速的發展，互聯網技術領域學術界和工業界提出了一些針對Internet的路由擴展性的解決方案。文章基于Internet面臨的路由擴展性問題，分析導致問題的原因;在對影響Internet路由擴展性的若干因素進行分析的基礎上，重點介紹互聯網技術領域學術界和工業界提出的一些典型解決方案;在對Internet路由擴展性問題行總結的基礎上，提出未來Internet路由系統的需求。

關鍵詞:Internet路由系統;邊界網關協議;可擴展性

Rapid improvement of the Internet has imposed significant pressure on its routing scalability. However， in order to maintain this rapid improvement in a continuous and stable way， some solutions for the scalability problem in routing system have been proposed by academia and the Internet technology industry. In this paper， we first introduce the problem of routing scalability faced by the Internet. Then we analyze the root causes of the problem， and introduce some of the abovementioned solutions. Finally， we conclude on the scalability problem of Internet routing and the requirements of the future Internet routing system.

Internet routing system; BGP; scalability

Internet起源于美國國防部高級研究計劃署資助開發的阿帕網(ARPANET)，最初它只是分布于美國4所著名大學的4個節點互聯組成的數據分組交換網，網速56 kbit/s，但在后續的40多年中，Internet得到了快速發展和迅速普及，根據Internet系統協會2009年7月發布的數據顯示，Internet已成為超過6億個節點，核心節點系統處理能力達到每秒太比特級的全球超級信息系統。

隨著Internet規模的不斷擴大，全球邊界網關協議(BGP)路由表呈現出“超線性”增長的態勢，數據顯示全球BGP轉發信息表(FIB)已從20世紀90年代末期的5萬余條爆增至2010年的30萬余條，如圖1所示。有專家預測在未來15年內可能會增至200萬條，2050年甚至可達到1 000萬條[1]，路由表的“超線性”增長以及由其所引出的一系列問題將導致Internet體系結構和路由機制的擴展性面臨巨大的挑戰[2]。

全球BGP路由表的“超線性”增長需要BGP路由器采用容量更大、查詢速度更快的存儲器(動態隨機存取存儲器、靜態隨機存取存儲器、三重內容可尋址存儲器)保存路由信息表(RIB)和FIB;由于每條路由表項的維護包括新建、撤銷、更新等都需要發布BGP通告，路由表的增長增加了BGP通告發布的數量和頻率，使更多、更頻繁的BGP路由更新注入Internet核心，從而形成了Internet網絡中的“路由更新攪動”，導致路由的不穩定、路由器計算FIB的負擔加重以及路由收斂時間的延長;另外，路由表查詢速度要求的提高和計算負荷的增大導致更大的功耗，因此需要更大型的供電系統和散熱系統。全球BGP路由表的“超線性”增長以及由此引發的一些列問題無疑增加了網絡的運營成本，影響Internet的發展。因此，路由擴展性問題引起了學術界和工業界的廣泛關注。

1 影響互聯網路由擴展性因素

2006年10月，鑒于由于互聯網規模不斷擴大帶來的一系列問題，互聯網架構委員會(IAB)在荷蘭阿姆斯特丹就Internet路由技術舉行了路由和尋址專題討論會，并在會后形成了分析和研究互聯網路由擴展性問題的報告RFC4984。研究人員普遍認為導致互聯網路由擴展性問題的主要因素是IP地址的語義重載、站點多歸屬、流量工程、提供商獨立地址、反前綴劫持。

1.1 IP地址的語義重載

目前的IP地址具有雙重語義，一方面它是表示主機身份的端點標志符，另一方面它又是表示網絡拓撲位置的定位符。端點標志符原則上應該與網絡拓撲獨立，在網絡或主機改變拓撲位置的時候，端點標志符應該保持不變，但目前的IP地址卻擔負了這種目標并不一致的雙重角色。IP地址的語義重載是站點多歸屬、流量工程、PI地址導致路由系統出現擴展問題的根源。專家認為未來主機標志與網絡位置標志的分離對路由系統的可擴展性來說十分必要。

1.2 站點多歸屬

具有連接到多個服務提供商能力的站點被稱為多歸屬站點[3]。站點多歸屬能使站點在某一個ISP故障的時候為網絡提供其他可用連接，增強網絡的可靠性和可恢復性。目前至少有60%的接入服務器(AS)是多歸屬的，這個數字還在不斷上升[4]。為了保證數據分組經過多個ISP仍能到達正確的站點，為多歸屬站點提供Internet服務的所有服務提供商都必須向外單獨通告該站點的IP地址前綴，因此站點多歸屬破壞了地址的可聚合性，導致細小的地址塊注入到Internet核心路由表中，它是導致目前路由擴展性問題的主要原因之一。

1.3 流量工程

流量工程就是要實現運營網絡的性能優化，它通過對Internet流量的測量、建模、規劃和控制等科學原理和技術方法達到實現特定性能的目的，流量工程的目的是在優化網絡資源利用率和流量性能的同時提供可靠高效的網絡運營[5]。流量工程能幫助ISP降低運營成本(讓流量通過較低成本的路徑)、優化部署策略(較高優先級的流量通過較好質量的路徑)、保證負載均衡，目前在ISP處得到廣泛應用。但是目前的流量工程主要靠通過解聚合IP地址前綴、向全球路由系統注入更詳細(更長)的地址前綴、利用更多、更頻繁的BGP更新達到對流量的控制，因而在優化網絡性能的同時也會導致全球BGP路由表的相應膨脹。

1.4 提供商獨立地址PI的分配

站點的IP地址不由ISP分配，而是直接向區域Internet注冊機構(RIR)申請獲得，這類IP地址與ISP無關，被稱為提供商獨立(PI)地址。PI地址可以幫助用戶在更換ISP時避免重新編址，但由于PI地址不由ISP分配，因此ISP也無法將此地址塊聚合，只能向外單獨通告此網絡的詳細地址前綴。因此PI地址也破壞了地址的可聚合性，使越來越多的用戶網絡地址注入Internet核心路由表。

1.5 反前綴劫持

Internet是一個開放的分布式系統，其路由的通告、更新和撤銷等都是由各AS決定的。一些AS可能出于惡意或由于網絡管理員的錯誤配置，向外通告不屬于自己的地址前綴，導致目的為這些地址的數據分組被錯誤地引導到該AS而無法到達原本的目的地，這種現象被稱為前綴劫持。為了抵御前綴劫持的攻擊，目前AS一般采用為較重要的服務如域名服務器(DNS)向外通告盡可能長的前綴(至少24位)，所以反前綴劫持技術的使用也導致了全球路由表的增長[6]。

眾所周知，目前的路由技術都是基于拓撲的，拓撲聚合是目前保證路由系統擴展性的唯一實際方法。但上述情況在不同程度上都破壞了Internet地址的可聚合性，導致了全球BGP路由表的快速膨脹，引發了Internet路由擴展性的問題，影響了Internet的擴展性，最終將影響Internet的持續發展。Internet路由擴展性成為下一代Internet必須解決的首要問題之一。

2 Internet路由擴展性研究狀況

Internet路由擴展性的研究工作得到了互聯網技術領域學術界和工業界的高度關注，國際上的一些著名研究機構在該方向上進行了大量的研究并相繼提出了一些初步方案，比較著名的方案有:加州大學洛杉磯分校提出的eFIT[7]、麻省理工大學提出的LANI[8]、加州大學伯克利分校提出的HLP[9]、伊利諾伊大學提出的ROFL、康奈爾大學提出的核心路由器完整覆蓋(CRIO)和虛擬聚合(VA)、美國波特蘭第一基礎研究院提出的IVIP、思科公司提出的LISP、愛立信公司提出的HIP和Christian Vogt提出的Six/One以及Patrick Frejborg提出的HIPv4等。此外，也有一些學者將關注點轉移到其他一些相關研究領域上，例如壓縮路由，希望通過其他研究領域的一些研究成果推動路由系統可擴展問題的解決。Internet研究任務組(IRTF)為此也建立了路由研究工作組(RRG)進行路由擴展性問題的研究，eFIT、LISP、IVIP、Six/One都成為了RRG的提案，HIPv4等一些方案在RRG中還處于提交討論階段。

目前，解決互聯網路由擴展性的方案基于拓撲聚合的較多，大致可分為兩種類型:一種是虛擬聚合類，這類方案的主要思想是保留BGP路由系統不變，在其上搭建覆蓋網，將比較細小的前綴的路由表項從BGP路由系統中提取出來，存儲在覆蓋網上，如CRIO、VA;另一種類型是基于身份標志和位置標志分離的思想，將IP地址的主機身份標志與網絡位置標志分離，此類方案又可細分為主機驅動型(例如HIP)和路由器驅動型(例如LISP、eFIT、IVIP、Six/One)。另外，LANI將命名空間分為多層例如主機標志層、路由層、服務標志層;HLP是一個代替BGP的新的域間路由協議;ROFL的路由基于扁平結構的標志符;HIPv4通過在IPv4地址空間中引入了層次結構保證路由體系結構的擴展性。下面就這些方案中的幾種主要技術進行分析介紹。

2.1 虛擬聚合

這類方案一般是通過將拓撲上不可聚合的連續地址前綴虛擬聚合成虛擬前綴(VP)，達到減小BGP路由表規模的目的。VP是一個覆蓋了地址空間較大部分的超級前綴，是對多個子前綴(目前傳統網絡的網絡前綴)的虛擬聚合。聚合代理是針對某個VP來說的，它負責存儲這個VP所覆蓋的所有子前綴及每個子前綴對應的隧道出口路由器的地址，實現虛擬聚合功能。虛擬聚合類方案雖然減小了路由表，但卻存在拉長轉發路徑的問題。

CRIO是較早提出虛擬前綴的一種方案，聚合代理在CRIO中被稱為VP-TS，它作為隧道起點(TS)存儲了對應VP中的每個子前綴的映射信息(子前綴以及對應的TE)，并負責將數據分組通過隧道傳送到隧道終點(TE)，即此子前綴所屬提供商的邊緣路由器(PE)并向管理域內的其他BGP路由器通告這個VP。

CRIO的數據分組轉發過程如圖2所示，用戶網絡A中的一臺主機欲發送數據分組給用戶網絡B中的一臺主機，其中路由器PE3是VP 24.0.0.0/8的VP-TS，它將通過隧道技術虛擬聚合24.0.0.0/8覆蓋的所有子前綴，例如24.1.1.0/24。入口路由器PE1、出口路由器PE2分別屬于不同的AS，整個轉發流程如下:

PE3向PE1發送VP的BGP通告，PE1的路由表添加一條路由信息(24.0.0.0/8，PE3);

CE1向PE1發送一個24.1.1.0/24的數據分組;

PE1在路由表中未查詢到24.1.1.0/24的路由信息，但查到路由信息(24.0.0.0/8，PE3)于是將該數據分組轉發給PE3;

PE3存有24.1.1.0/24的映射信息(24.1.1.0/24，PE2)，根據此映射信息，PE3將數據分組通過隧道發往TE PE2;

PE2知道要通過CE2才能到達24.1.1.0/24網絡，因此將數據分組去掉封裝報頭后轉發給CE2。

整個轉發路徑為CE1→PE1→PE3→PE2→CE2，但若PE1存有24.1.1.0/24的映射消息，路徑為CE1→PE1→PE2→CE2。由此可見，CRIO在實現地址聚合的同時卻將分組的轉發路徑拉長了。

實施CRIO方案時，BGP路由器只需要存儲到Internet的入網點(POP)的路由以及VP-TS的路由。全球的大型提供商共有幾千個POP，如果VP被定為/8，整個地址空間共有256個VP，這樣傳統路由器的路由表(RIB)規模就可以從105量級減少到103量級，大大減少了BGP路由的計算量和路由表的大小;同時，路由器中存儲的路由指向終點(大型提供商的POP)也會非常的穩定，從而減少了BGP信息的更新頻率。文獻11對CRIO進行了仿真試驗(如圖3所示):采用在所有的ISP上隨機部署VP，或在每個ISP內部署所有的VP，或所有的ISP內部路由都是最短路徑的3種不同VP部署策略，考察轉發表大小與路徑長度的關系，結果表明在平均路徑長度增加很少的情況下，第一個策略使部署了CRIO的FIB的規模減小一個數量級，其他兩個方案則使FIB的規模減小到未部署CRIO的FIB的1/5左右，BGP RIB的規模則可以減少近兩個數量級。

CRIO雖然能夠緩解目前路由系統所面臨的路由表膨脹壓力，但是它尚存一些待解決的問題，當多個ISP同時部署VP-TS時，如何解決轉發路徑可能被多次拉長的問題目前尚不清楚;CRIO使數據分組的轉發路徑拉長，增加了數據分組在路由器內的處理時間，從而增加了傳送時延;由于CRIO使用隧道技術，封裝也會導致帶寬、CPU資源的開銷增加;VP-TS集中了所有發往被聚合的子前綴的流量，很容易成為網絡“瓶頸”;此外，CRIO缺乏對移動性的支持;以上這些問題都有待相關研究人員作進一步的研究。

VA是IETF GROW工作組的提案之一，用于解決當前路由擴展性。VA與CRIO一樣，使用隧道技術虛擬聚合分散的子前綴成VP。在VA中，聚合代理被稱為匯聚點路由器(APR)。VA的部署范圍僅限于ISP內，所以作為隧道起點的APR存儲VP內的每個子前綴及對應的遠端AS的邊界路由器(ASBR)地址，并負責將數據分組通過隧道傳送到隧道終點，即遠端AS的邊界路由器(ASBR)地址，如圖4所示。VA保持BGP路由器中的RIB不變，只是阻止RIB中的一些表項加載到BGP路由器的FIB中，這是VA與CRIO的一個不同之處。VA的隧道并不跨越多ISP，解封裝數據分組的任務由本地ISP的邊緣路由器完成，無需與其他ISP進行協作，這是VA與CRIO的另一區別。由于VA與CRIO的基本思路相似，所以也存在與CRIO一樣的問題。此外，由于VA只壓縮了路由器中FIB規模，RIB的快速增長仍未得到解決。

2.2 標志和位置標志分離

2.2.1 主機驅動型

主機驅動型是指在主機協議棧的網絡層和傳輸層之間加入主機標志層的分離類型，主機標志負責標志主機，網絡地址負責數據分組的尋址和傳送，應用連接不再與IP地址綁定，而是與主機標志綁定，網絡層IP地址只作為網絡層使用的位置標志，用于數據分組的路由轉發。IP地址的變更對傳輸層以上透明，從而IP地址的改變可以不中斷已經建立的應用連接，達到支持主機移動性和多歸屬的目的。HIP是主機驅動型的典型方案，主要要解決主機的安全和移動性問題，如果所有的IP網絡都部屬HIP，所有的主機都使用全新的名字空間作為主機標志，IP地址僅用于路由，IP地址就可完全按照網絡拓撲分配，IP地址恢復可聚合性，從而徹底解決路由擴展性的問題。

HIP在網絡層和傳輸層中間插入主機標志層(HIL)，實現了身份與位置標志的分離，引入主機標志層后的協議體系結構如圖5右側協議棧所示。HIP引進一個新的加密的命名空間，該命名空間引入了3個新的標志符:主機標志符(HI)、主機標志標簽(HIT)和局部標志符(LSI)。主機標志符唯一地標志了每臺連接到Internet上的主機，每個主機可以有多個HI。HI可以用不對稱加密算法中公/私密鑰對的公鑰來表示，由于不同的加密算法所擁有的密鑰長度不一樣，因此，在實際使用時，通常用128位定長的HIT來代替HI標志主機身份，HIT是對HI的某種哈希變換，與IPv6地址等長，在應用程序中使用非常方便，同時為了和現有的IPv4地址兼容，HIP協議還定義了LSI，作為局部系統中使用的主機標志符。HIP協議的基本交換是一個使用公鑰作為主機標志并建立HIP基本交換加密的4次握手過程，它可以保證通信的安全性。

在HIP體系結構中的兩臺主機在進行通信時，發起方首先要通過查詢DNS和映射系統獲得通信對端的標志和位置標志集，然后兩臺主機再通過HIP基本交換建立安全關聯，開始雙向數據傳輸。

由此可見，在HIP體系結構中由于主機標志層的引入，使得原來傳輸層和網絡層之間的緊耦合得以解耦，應用程序只看到一對不變的源、目的HIT，移動與多宿主對應用程序來說是透明的。此外，HIP通過引入匯聚服務器(RVS)用來維護移動節點的當前位置信息，保證節點移動能夠不中斷通信。

HIP也存在一定的缺陷:

HIP不支持組播;

需要大量部署RVS以解決主機移動問題，如果利用現有的DNS，需增強動態更新的處理能力;

HIP主機之間的通信需要對數據包進行加密和解密，增加CPU的額外負擔;

HIP的主機標志采用扁平結構，不具備合理的商業模型;

HIP的部屬需要對主機協議棧進行修改，對Internet影響較大。

2.2.2 路由器驅動型

路由器驅動型方案將整個Internet劃分為邊緣網絡與核心網絡，邊緣網絡內部使用PI地址，既作為主機的標志符也用于內部的路由尋址;核心網絡使用PA地址，用于核心網絡的路由;邊界路由器將數據分組中的目的PI地址改為核心網絡的PA地址，實現邊緣網絡與核心網絡分離。路由器驅動型方案使用PI地址前綴作為網絡標志符，PA地址作為該網絡接入Internet的拓撲位置，從而分離了邊緣網絡的IP地址前綴的雙重語義，保證了Internet的路由擴展性。

LISP是這類方案中的一種典型方案，LISP將地址空間分為端點標志(EID)和路由位置符(RLOC)。EID可以唯一地標志邊緣網絡內的主機，在邊緣網絡內既用于路由也用于主機標志，EID的前綴作為邊緣網絡的標志符。RLOC標志網絡位置，在核心網絡中用于路由。LISP還定義了入口隧道路由器(ITR)和出口隧道路由器(ETR)。

LISP將邊緣網絡內外主機間的通信路徑分成圖6所示的3個部分:邊緣網絡內從源主機到ITR(綠色)的路徑部分，使用EID路由;從ITR到ETR的隧道路徑部分(紅色)，使用RLOC路由;從ETR到目的主機的路徑部分，使用EID路由(紫色)。下面就以主機A向主機B發送數據分組的過程為例說明LISP的主要原理:

數據分組首先被轉發到ITR(路由器E);

ITR在本地映射緩存中查找目的EID到RLOC的映射，如果查找到對應的RLOC，則為數據分組添加一個外部LISP包頭，該LISP包頭中包括ETR和ITR的RLOC地址，將封裝好的數據分組發送到核心網的邊界路由器J;

核心網利用RLOC地址進行路由，將數據分組發送到ETR(即路由器I);

ETR接收到數據分組后進行解封裝，再將解封裝后的數據分組通過目的遠端標志進行路由并發送到目的主機B。

如果ITR沒有找到所需的映射信息，則需要先向映射系統發送請求映射信息的消息(映射請求、數據探針)。映射系統是LISP系統的一個重要組件，工作在路由系統的控制平面，負責處理ITR沒存所需映射信息的情況。LISP目前已提出了4類映射系統，分別為:內容分發覆蓋網絡服務(CONS)、非新穎的EID到RLOC的映射數據庫(NERD)、穿越合作系統的EID映射多播(EMACS)、可替代的邏輯拓撲(ALT)。當前的LISP原型系統采用的是ALT機制。

LISP-ALT由ALT路由器組成，通過通用路由協議封裝(GRE)隧道相互連接，在BGP路由系統之上組成一個樹形拓撲結構的邏輯覆蓋網絡，覆蓋網絡負責將映射請求信息和數據探針(數據探針的內部地址EID和外部地址RLOC相同)轉發至存有被請求的EID到RLOC映射信息的ETR，ALT路由器之間使用BGP協議通告EID前綴的可達性信息，這些EID前綴的可達性信息在樹形拓撲結構的覆蓋網絡中逐層匯聚，如圖7所示。

LISP將邊緣網絡與核心網絡分離，整個核心網的路由器使用PA地址，實現了核心網絡的拓撲聚合，從而減小了DFZ中的路由表規模，并能夠支持可擴展的站點多歸屬和流量工程;邊緣網絡由于使用EID作為地址空間，因此在更換ISP時無需重新編址。LISP方案不必修改核心路由器，僅要對邊緣路由器作一定的修改，對目前已有的網絡基礎設施改動較少。當然，LISP也存在一些缺點，由于采用隧道機制，存在最大傳輸單元(MTU)問題，且需要消耗一定的帶寬;LISP對移動性支持有限;未來Internet的需求之一是移動性，對移動性的有限支持是LISP亟待解決的重要問題之一;LISP引入了映射系統，方案的部署開銷仍需進一步評估。

3 結束語

Internet路由擴展性問題是目前互聯網技術領域一個需要解決的重要問題，與IPv4相比，IPv6具有更大的地址空間，但由于IPv6地址的結構、分配與IPv4并無區別，隨著IPv4地址的枯竭，IPv6的部署進程在不斷加快，Internet路由擴展性問題的解決將更加迫切。本文在對影響Internet路由擴展性的若干因素進行分析的基礎上，重點介紹了互聯網技術領域學術界和工業界提出的幾種典型解決方案，這些方案雖然在一定程度上部分解決了路由擴展性的問題，但是仍然存在進一步完善和改進的空間，Internet路由擴展性的研究已是當今互聯網技術領域最活躍的一個研究內容?？梢灶A見，為了Internet能夠持續、穩定、快速的發展，未來的互聯網路由系統應該具有更好的擴展性，能夠可擴展地支持多歸屬、流量工程、移動性，并支持安全性，能夠簡化重新編址，具備向后兼容性，支持IPv4和IPv6，并能夠保證路由質量，支持互聯網的增量部署。

4 參考文獻

[1] MEYER D， ZHANG L， FALL K， et al. Report from the IAB workshop on routing and addressing[R]. IETF RFC 4984. 2007.

[2] HUSTON G. Analyzing the Internet’s BGP routing table[J]. The Internet Protocol Journal， 2001，4(1):2-15.

[3] ABLEY J， LINDQVIST K， DAVIES E， et al. IPv4 multihoming practices and limitations[R]. IETF RFC 4116. 2005.

[4] LIU Xiaomei， XIAO Li. A survey of multihoming technology in stub networks: Current research and open issues[J]. IEEE Network Magazine， 2007， 21(3):32-40.

[5] AWDUCHE D， MALCOLM J， AGOGBUA J， et al. Requirements for traffic engineering over MPLS[R]. IETF RFC 2702.1999.

[6] MENTH M， HARTMANN M， TRAN-GIG P， et al. Future Internet routing: Motivation and design issues[J].Information Technology， 2008， 50(6):358-366.

[7] MASSEY D， WANG Lan， ZHANG Beichuan， et al. A scalable routing system design for future Internet[C]// Proceedings of the ACM SIGCOMM Workshop on Large Scale Attack Defense (LSAD '07)， Aug 27-31， 2007， Kyoto， Japan. New York， NY，USA: ACM， 2007:790-796.[8] BALAKRISHNAN H， LAKSHMINARAYANAN K， RATNASAMY S， et al. A layered naming architecture for the Internet[C]// Proceedings of Conference on Applications， Technologies， Architectures， and Protocols for Computer Communication (SIGCOMM’04)， Aug 30 Sep 3， 2004， Portland， OR， USA. New York， NY，USA: ACM， 2004:343-352 .

[9] SUBRAMANIAN L， CAESAR M， EE C T， et al. HLP: A next generation inter - domain routing protocol [C]//Proceedings of Conference on Applications， Technologies， Architectures， and Protocols for Computer Communications (SIGCOMM’05)， Aug 22-26， 2005， Philadelphia， PA， USA. New York， NY，USA: ACM， 2005:13-14.

收稿日期:2010-01-29

陸璇，北京郵電大學計算機科學與技術學院在讀博士，主要研究方向為互聯網的可擴展路由系統。

王文東，北京郵電大學網絡技術研究院副院長、教授，主要研究方向為新一代互聯網體系結構和服務質量保障機制。

程時端，北京郵電大學網絡與交換技術國家重點實驗室教授、博士生導師，長期從事通信網與計算機網絡的研究開發。1992—1999年擔任國家“863”通信主題網絡與交換專業專家組組長、北京郵電大學網絡與交換技術國家重點實驗室主任，現擔任北京通信學會理事、中國通信標準化協會專家咨詢委員會委員。目前研究方向為新一代互聯網的體系結構和性能優化技術。