互聯(lián)網(wǎng)可擴展路由研究與分析

徐明偉，李 清

(1.清華大學(xué)計算機科學(xué)與技術(shù)系，北京 100084;2.清華信息科學(xué)與技術(shù)國家實驗室(籌)，北京 100084)

0 引言

自上個世紀(jì)70年代誕生之日起，互聯(lián)網(wǎng)飛速發(fā)展，現(xiàn)已經(jīng)成為全球性的商業(yè)網(wǎng)絡(luò)平臺。據(jù)統(tǒng)計，當(dāng)前互聯(lián)網(wǎng)終端數(shù)量已經(jīng)從上個世紀(jì)80年代初的幾百增長到2012的近10億;而用戶數(shù)量也從最初的幾百增長到2012的近25億［1］。此外，隨著移動終端(手機、平板電腦等)的加入，互聯(lián)網(wǎng)將得到進一步發(fā)展。然而隨著規(guī)模的膨脹，互聯(lián)網(wǎng)面臨越來越多的問題:安全問題、節(jié)能問題、擴展問題等。其中，當(dāng)前互聯(lián)網(wǎng)路由系統(tǒng)面臨嚴(yán)重的可擴展問題已經(jīng)成為廣泛的共識［2］。

互聯(lián)網(wǎng)路由系統(tǒng)主要由2部分組成:域間路由和域內(nèi)路由。當(dāng)前主流的域間路由協(xié)議為邊界網(wǎng)關(guān)協(xié)議(border gateway protocol，BGP);主流的域內(nèi)路由協(xié)議為開放最短路徑優(yōu)先協(xié)議(open shortest path first，OSPF)和中間系統(tǒng)到中間系統(tǒng)路由協(xié)議(intermediate system to intermediate system routing protocol，ISIS)。BGP路由器通過路由通告完成域間路由的傳播，通過屏蔽自治域的拓?fù)湫畔?，BGP可以控制域間路由信息的規(guī)模。然而，由于多宿主(multihoming)、流量工程(traffic engineering，TE)等原因，越來越多不可聚合的提供商獨立(provider independent，PI)地址通過BGP注入到全局網(wǎng)絡(luò)中。這直接導(dǎo)致核心網(wǎng)路由表急劇增加，使互聯(lián)網(wǎng)路由系統(tǒng)面臨嚴(yán)重的可擴展性問題。圖1顯示了1994-2012年互聯(lián)網(wǎng)骨干網(wǎng)絡(luò)路由表的增長情況:1994年的骨干網(wǎng)路由表僅包含不到2萬條表項;2012年這個數(shù)字已經(jīng)超過40萬［3］。隨著IPv6的逐漸部署，被網(wǎng)絡(luò)地址轉(zhuǎn)換等技術(shù)抑制的地址會得到釋放，可能會進一步加劇互聯(lián)網(wǎng)路由可擴展性問題。

圖1 互聯(lián)網(wǎng)骨干網(wǎng)絡(luò)路由表增長Fig.1 Growth of routing tables in the core internet

互聯(lián)網(wǎng)路由可擴展性問題主要體現(xiàn)在兩方面:控制平面的路由信息交換和數(shù)據(jù)層面的數(shù)據(jù)包轉(zhuǎn)發(fā)［4］。如圖2所示，核心網(wǎng)路由器一方面要處理全網(wǎng)的路由更新，另一方面需要存儲全局轉(zhuǎn)發(fā)表用以實現(xiàn)數(shù)據(jù)包的轉(zhuǎn)發(fā)。首先，BGP路由器通過路由通告(更新)完成全局路由的傳播。隨著網(wǎng)絡(luò)規(guī)模及路由條目(即目的前綴數(shù)量)的增加，控制平面的路由更新急劇增加。據(jù)相關(guān)資料顯示，高峰時段路由器每秒可能收到上百條路由更新［3］。這給路由器帶來巨大的處理負(fù)擔(dān)。其次，路由表增大直接導(dǎo)致路由器的存儲負(fù)擔(dān)加重。轉(zhuǎn)發(fā)信息表(forwarding information base，F(xiàn)IB)用于數(shù)據(jù)層面的數(shù)據(jù)包轉(zhuǎn)發(fā)，對速度要求很高，因此，一般用昂貴的三態(tài)內(nèi)容關(guān)聯(lián)存儲器(ternary content addressable memory，TCAM)存儲，存儲代價難以接受。此外，龐大的路由表會導(dǎo)致查詢速度降低，從而影響數(shù)據(jù)轉(zhuǎn)發(fā)速度。

圖2 互聯(lián)網(wǎng)路由器基本模型Fig.2 Basic model of internet routers

1 可擴展路由研究概述

1.1 路由可擴展性原因分析

針對互聯(lián)網(wǎng)路由可擴展問題，學(xué)術(shù)界和工業(yè)界都展開了積極的研究?；ヂ?lián)網(wǎng)架構(gòu)委員會(internet architecture board，IAB)，互聯(lián)網(wǎng)工程任務(wù)組(internet engineering task force，IETF)及互聯(lián)網(wǎng)研究任務(wù)組(internet research task force，IETF)等對該問題展開了深入的研究;網(wǎng)絡(luò)設(shè)備巨頭Cisco和Juniper也針對該問題提出了相關(guān)方案;JSAC(IEEE journal on selected areas in communications)在2010年出版了一期關(guān)于可擴展路由的?？＝?jīng)過近年的深入研究，學(xué)術(shù)界和工業(yè)界對導(dǎo)致路由可擴展問題的原因有了比較統(tǒng)一的認(rèn)識。在文獻［2］中，作者總結(jié)了幾個原因:IP語義重載、多宿主、流量工程、不合理的地址分配等。

1)IP語義重載。IP語義重載是導(dǎo)致互聯(lián)網(wǎng)路由可擴展性的根本原因之一。在當(dāng)前的互聯(lián)網(wǎng)中，IP地址既作為標(biāo)識(identifier，ID)用來代表主機，又作為定位符(locator，Loc)用來標(biāo)識位置并實現(xiàn)路由。這導(dǎo)致當(dāng)前互聯(lián)網(wǎng)對移動性、多宿主等需求缺乏靈活的應(yīng)對方案。由于IP地址作為標(biāo)識，當(dāng)主機移動或?qū)崿F(xiàn)多宿主時無法全部使用提供商指定(provider assigned，PA)地址，從而引入無法聚合的PI地址。雖然IP語義重載對路由可擴展的影響是間接的，但是同時這種影響也是根本的。如果能夠打破IP語義重載，自然能夠有效解決路由可擴展性問題。

2)多宿主。80年代網(wǎng)絡(luò)規(guī)模很小，多宿主亦不常見。90年代多宿主興起，那時采用的多宿主方法一直沿用至今，即每個多宿主網(wǎng)絡(luò)(或主機)通過多個網(wǎng)絡(luò)提供商(internet service provider，ISP)網(wǎng)絡(luò)鏈接到互聯(lián)網(wǎng)。對某些ISP而言，該多宿主網(wǎng)絡(luò)的地址塊是不可聚合的PI地址，會隨著BGP路由通告擴散到全網(wǎng)，從而導(dǎo)致路由表的急劇增長。

3)流量工程。為了實現(xiàn)負(fù)載均衡等目的，有自治域(autonomous system，AS)網(wǎng)絡(luò)會將前綴切分成更小的地址塊通告出去，通過這種方式實現(xiàn)對流量的精確控制。這也導(dǎo)致更多的前綴被注入到網(wǎng)絡(luò)中，加劇了路由可擴展性問題。

4)不合理的地址分配。由于歷史原因，IPv4早期分配沒有考慮到地址空間的不足。當(dāng)前，有些企業(yè)無法獲得足夠大的連續(xù)地址塊，只能申請多個不可聚合的地址塊，這也導(dǎo)致了核心網(wǎng)路由表的增長。

在文獻［5］中，作者針對導(dǎo)致路由表增長的幾個因素做出相關(guān)研究和分析。結(jié)果表明，流量工程和多宿主導(dǎo)致路由表增長影響最大，分別貢獻了路由增長的20% ～30%和20% ～25%。而且，這2個因素的對路由表增長的作用還在逐年加劇。

1.2 可擴展路由解決方案概述

下面對當(dāng)前的研究現(xiàn)狀進行簡要的分類介紹，分類方式如圖3所示。

圖3 互聯(lián)網(wǎng)可擴展路由研究方案分類Fig.3 Classification of internet routing scalability solutions

如前文所述，IP語義重載導(dǎo)致網(wǎng)絡(luò)實現(xiàn)多宿主等需求時產(chǎn)生不可聚合的PI地址。因此，解決方案之一是通過消除IP地址語義重載來增強互聯(lián)網(wǎng)路由的可擴展性。代表的解決方案包括Shim6［6］，HIP(host identifier protocol)［7］，INLP(identifier locator network protocol)［8］等。這些方案通過在主機端實現(xiàn)ID/Loc的分離，消除了IP語義重載，因此也被稱為消除方案(elimination solutions)。此類方案大大增強了網(wǎng)絡(luò)對多宿主、移動性等的支持，避免產(chǎn)生無法聚合的PI地址碎片。

從控制平面來看，無論是多宿主還是流量工程，都會通告更詳細(xì)的前綴，并將相關(guān)路由擴散到核心網(wǎng)中。因此，解決路由可擴展性問題可以通過將邊緣/核心網(wǎng)絡(luò)地址隔離來實現(xiàn)。這類方案將邊緣網(wǎng)絡(luò)和核心網(wǎng)絡(luò)徹底隔離，通過引入映射系統(tǒng)完成邊緣網(wǎng)絡(luò)地址到核心網(wǎng)絡(luò)地址的映射。在數(shù)據(jù)包進入或離開核心網(wǎng)時，都需要進行地址轉(zhuǎn)換。這類方案在2010年之前是可擴展路由研究的主流方向，有大量方案被提出，主要代表有 Encaps［9］，LISP［10］，APT［11］，SIX/ONE［12］，MILSA［13］等。

目前，路由的動態(tài)性，即控制層面的開銷還是可以接受的，因為當(dāng)前路由器的計算能力還是足夠的;而且，路由表動態(tài)性的加劇速度遠(yuǎn)遠(yuǎn)不及路由表大小的增長速度。路由可擴展問題中亟待解決的一個問題是FIB膨脹的問題。原因如下:首先，轉(zhuǎn)發(fā)表一般用昂貴的TCAM存儲，按照路由表增長的速度來升級相關(guān)硬件會給網(wǎng)絡(luò)服務(wù)提供商(internet service provider，ISP)帶來巨大的運營成本;其次，為了實現(xiàn)線速轉(zhuǎn)發(fā)，TCAM每次IP地址查詢需要讀取所有的存儲單元，過大的路由表帶來巨大的能量消耗。此外，上述的解決方案對網(wǎng)絡(luò)改動較大，無法在短期內(nèi)解決ISP降低運行成本的需求。因此，越來越多的研究人員開始關(guān)注路由聚合，代表方案包括ORTC［14］，IFTA［15］，SMALTA［16］，Level 1-4 FIB 聚合［17］，ViAggr［18］，NSFIB 聚合［19-20］，RIB 聚合［21］等。

以上所有方案都有一個基本前提:基于當(dāng)前的IP網(wǎng)絡(luò)。然而，當(dāng)前的互聯(lián)網(wǎng)路由體系結(jié)構(gòu)，在設(shè)計之初并未考慮到當(dāng)前可能出現(xiàn)的諸多問題(包括可擴展性)，具有一定的局限性。因此，針對當(dāng)前網(wǎng)絡(luò)進行“修補”無法解決根本問題，需要用新的網(wǎng)絡(luò)體系結(jié)構(gòu)來解決當(dāng)前面臨的問題?；谶@個目標(biāo)，緊湊路由(compact routing)［22-23］和地理信息路由(geographic routing)［24-25］等非IP路由協(xié)議被提出用以替換當(dāng)前互聯(lián)網(wǎng)的路由系統(tǒng)。

在下文中，將主要針對前3個研究方向，即基于主機的ID/Loc分離、邊緣/核心網(wǎng)絡(luò)地址分離和路由聚合，進行詳細(xì)討論。

2 基于主機的ID/Loc分離

基于主機的ID/Loc分離方案是在主機端消除IP語義重載，因此也被稱為消除方案。IP語義重載消除的直接效果是網(wǎng)絡(luò)在實現(xiàn)多宿主時不再產(chǎn)生不可聚合的PI地址碎片，從而消除多宿主等對路由可擴展性的影響。本節(jié)，主要討論此類方案中的3個典型方案:Shim6［6］，HIP［7］和 ILNP［8］。

2.1 Shim6 協(xié)議

用戶網(wǎng)絡(luò)(主機)可以通過接入多個ISP以提高網(wǎng)絡(luò)的可靠性和服務(wù)質(zhì)量，但卻造成ISP核心路由表的膨脹(PI地址);為了避免這個問題，用戶網(wǎng)絡(luò)(主機)必須維護多個ISP分配的PA地址，這又給用戶造成了極大的不便。這就是多宿主在當(dāng)前的互聯(lián)網(wǎng)中面臨的困境，為此IETF組織了Shim6工作組來解決這個問題。

2.1.1 Shim6 簡介

Shim6協(xié)議是一個主機多宿主解決方案，其目標(biāo)是在不產(chǎn)生PI地址的前提下更好地支持多宿主，從而消除多宿主對路由可擴展性的影響。Shim6的主要思想是:在主機網(wǎng)絡(luò)層和傳輸層之間插入一個新的Shim6子層，該子層把IP地址的雙重語義分割開來。在Shim6子層之上的應(yīng)用層使用一個不變的上層協(xié)議標(biāo)識符(upper layer identifier，ULID);在Shim6子層之下的網(wǎng)絡(luò)層使用多個Loc，從而在不引入PI地址的情況下實現(xiàn)多宿主功能。Shim6不會為上層的ULID另外創(chuàng)造一個地址空間，而是在下層的Loc中選擇一個作為ULID。上層協(xié)議初始化ULID之后，即便下層的Loc變化，ULID也不會再變(至少在會話期間)。Shim6負(fù)責(zé)將多個Loc映射到一個ULID，供上層協(xié)議和應(yīng)用使用。Shim6子層維護ULID對狀態(tài)，每一對ULID是上層應(yīng)用公用的。而且，在通信的兩端這種映射是一致的。這樣，上層協(xié)議及應(yīng)用看到的就是基于ULID間的端到端通信。圖4描述了Shim6在協(xié)議棧中的位置。Shim子層擴展的部分(如圖4所示的AH，ESP等)在此不再詳細(xì)討論。

圖4 Shim6協(xié)議示意圖Fig.4 Sketch map of Shim6

2.1.2 Shim6 通信流程

以上討論了 SHIM6的基本概念，下面介紹SHIM6的通信流程，主要通過以下8點予以概括。

1)主機A上的某個應(yīng)用決定與主機B上的某個應(yīng)用通訊(通過某個上層協(xié)議ULP)。主機A上的ULP發(fā)送數(shù)據(jù)包給B，完成通訊初始化過程。在這個過程中Shim子層并不參與。

2)主機A或B(或者二者都)通過探索決定要用Shim6，雖然引入一定的通訊開銷，但是可以增強端到端通訊的可靠性(當(dāng)Loc失效時)。例如，這個探索過程可能是已經(jīng)收到或發(fā)送有50個數(shù)據(jù)包，或者發(fā)生了超時。Shim初始化是上下文建立的過程，這樣做是為了避免2個主機間只有少量的數(shù)據(jù)包需要交換，那么Shim的代價就很高了。在這個過程中，A和B都會獲得對方的多個Loc。如果這個過程失敗了，那么至少有一方不支持Shim6，這個通訊就退化為標(biāo)準(zhǔn)的IP通信過程。

3)在接下來的通信過程中，ULP數(shù)據(jù)包不會變化，也就是說不會添加Shim6擴展頭部(此時ULID=Loc)。當(dāng)然，Shim6子層可能會通過交換消息檢測可達性。

4)故障發(fā)生時(Shim6或ULP發(fā)現(xiàn))，主機A或主機B(或二者都)要探測另外一個可選的Loc，直到發(fā)現(xiàn)另外一個可用的Loc對。

5)此時，Shim6子層會給ULP數(shù)據(jù)包添加Shim擴展頭部，其中包含對方的上下文標(biāo)簽。接受當(dāng)可以利用上下文標(biāo)簽找到對應(yīng)的上下文狀態(tài)，從而按照正確的方式替換IPv6中的地址，并將處理后的數(shù)據(jù)包交給ULP。

6)Shim子層會監(jiān)視新的Loc對。

7)除了擴展檢測之外，某個主機也會通過某種方式發(fā)現(xiàn)自己的某個Loc失效，此外該主機可以通過Shim子層主動告知對方該故障。

8)當(dāng)Shim認(rèn)為某個上下文狀態(tài)不會再被使用，它會負(fù)責(zé)回收該狀態(tài)。

2.1.3 性能分析

以上描述主要是從多宿主支持的角度進行的。如果從可擴展性的角度講，Shim6使每個多宿主主機可以使用多個PA地址(Loc)。這些地址可以被對應(yīng)ISP的前綴聚合，因此，不會向核心網(wǎng)注入新的地址，從而增強了互聯(lián)網(wǎng)路由的可擴展性。然而，獲得此擴展性的代價是Shim6擴展帶來的通信開銷、Shim6子層的狀態(tài)維護等。

此外，Shim6主機和不支持Shim6的主機通信會退化到?jīng)]有Shim6的標(biāo)準(zhǔn)通信方式。Shim6具有很強的局限性，因為它只是對多宿主導(dǎo)致的可擴展性問題有效。其他因素，如主機移動帶來的renumbering，仍然會導(dǎo)致路由可擴展性問題。而相比之下，ILNP［12］的解決就更加全面。

2.2 Host identifier protocol(HIP)

在傳統(tǒng)的互聯(lián)網(wǎng)協(xié)議體系中，IP地址承擔(dān)雙重角色:ID和Loc。這使得主機移動和應(yīng)用多宿主時產(chǎn)生不可聚合的PI地址，導(dǎo)致路由可擴展性。另外，因為缺乏地址認(rèn)證方式，當(dāng)前互聯(lián)網(wǎng)面臨嚴(yán)重的安全問題(如地址欺騙)。

為了解決上述問題，主機標(biāo)識協(xié)議(host identifier protocol，HIP)引進一個新的命名空間:主機標(biāo)識(host identifier，HI)空間。網(wǎng)絡(luò)層的任何變化(多宿主、移動等導(dǎo)致的IP地址變化)不會影響傳輸層。IP地址在HIP中，有2種主機標(biāo)識表示方法:HI和HIT(host identifier tag)。HI是主機的一個公/私鑰對的公鑰。由于存在不同的加密算法，因此，HI可能具有不同的長度，不適合用作數(shù)據(jù)包標(biāo)識或表索引。HIT，作為HI的128位定長哈希，被引入用來替代HI。

HIP協(xié)議層位于應(yīng)用層和傳輸層之間，完成HI與IP地址之間的轉(zhuǎn)換:傳輸層使用＜HI，端口＞，而不是＜IP，端口＞;網(wǎng)絡(luò)層依然用IP地址進行路由。HI和IP地址通過動態(tài)綁定的方式實現(xiàn)，這樣IP地址改變之后只需要通過HIP層進行重新綁定即可，不會對應(yīng)用層產(chǎn)生影響。

從擴展性的角度講，HIP協(xié)議和Shim6類似，都是通過邏輯上分離ID/Loc，使互聯(lián)網(wǎng)對多宿主的支持不再需要產(chǎn)生不可聚合的PI地址。

2.3 Identifier locator network protocol

當(dāng)前互聯(lián)網(wǎng)面臨諸多需求，移動性、多宿主、網(wǎng)絡(luò)地址翻譯是其中的3個需求。由于IP地址語義重載，導(dǎo)致當(dāng)前的互聯(lián)網(wǎng)對這些網(wǎng)絡(luò)(用戶網(wǎng)絡(luò))需求支持不好，從而導(dǎo)致互聯(lián)網(wǎng)路由可擴展性。IP地址意義重載指的是IP地址既作為ID標(biāo)識主機，又作為Loc標(biāo)識位置，也就是說IP地址蘊含了拓?fù)湫畔ⅰ?)移動性。一個節(jié)點的移動就需要換個IP地址以反映這種位置的改變(renumbering)。但是IP本身還被當(dāng)作主機ID，用在應(yīng)用程序中。為了保證應(yīng)用的延續(xù)性，IP地址無法改變，這樣該主機就會向新的網(wǎng)絡(luò)注入不可聚合的PI地址。2)多宿主。80年代網(wǎng)絡(luò)規(guī)模很小，多宿主亦不常見。90年代多宿主興起，那時采用的多宿主方法一直沿用至今，即每個多宿主的網(wǎng)絡(luò)(或主機)需要其提供商為其通告一個PI前綴(地址)。這個前綴(地址)很難聚合，會隨著BGP路由通告擴散到全網(wǎng)中，從而導(dǎo)致路由表的急劇增長。雖然轉(zhuǎn)發(fā)速度通過引入基于ASIC的轉(zhuǎn)發(fā)引擎得以解決，然而，大家依然擔(dān)心路由表在大小方面的承受能力是很有限的。3)網(wǎng)絡(luò)地址翻譯。雖然NAT和路由可擴展性不是直接相關(guān)的，但是，NAT能夠延長IPv4地址的壽命并將大量的主機地址從全局網(wǎng)絡(luò)隔離，因此也間接地影響著互聯(lián)網(wǎng)路由可擴展性。

ILNP目標(biāo)是使互聯(lián)網(wǎng)更好地支持移動性、多宿主及NAT，尤其是使前2個需求不再產(chǎn)生無法聚合的PI地址，從而增強互聯(lián)網(wǎng)路由的可擴展性。在文獻［12］中，作者以IPv6作為基礎(chǔ)，提出了ILNPv6機制，并分析了該機制對移動性、多宿主及NAT的支持;同樣的思想也可以用在IPv4網(wǎng)絡(luò)中。

ILNPv6的關(guān)鍵思想是對IPv6地址進行重新編址，并借助DNS來完成地址查詢和更新，而在這個過程中Identifier保持不變。在ILNPv6中，地址被分為兩部分:64位的Loc和64位的Identifier。Identifier用來標(biāo)識一臺主機;Loc用來標(biāo)識其位置。網(wǎng)絡(luò)層路由協(xié)議幾乎不用改動，最大的變動發(fā)生在主機端。這也是此類方案共同面臨的問題:大批網(wǎng)絡(luò)應(yīng)用將無法在ILNP的框架下運行。

雖然ILNP宣稱并未改變IP語義重載，即IP地址仍然既包含Loc又包含Identifier，但是，邏輯上ILNP還是打破了“重載”，因為ILNP中Loc和Identifier是相互獨立的，不存在“重”的問題。此外，IPv6地址能夠分為兩部分:Identifier和Loc，而IPv4地址本身只有32位，因此無法拆分。所以，ILNPv4只能借助2套地址，這種情況下也打破了IP語義重載。

此外，IPv4下，DNS還能如IPv6下那樣完成ILNP需要的功能嗎?這一點很值得懷疑。

2.3.1 移動性支持

首先我們討論一下ILNP對移動性的支持。當(dāng)一臺主機從一個子網(wǎng)移動到另一個子網(wǎng)時，該節(jié)點首先要向全網(wǎng)更新其新的Loc。在ILNPv6中，這一功能主要通過擴展DNS來實現(xiàn)。在MIP中，這一過程等價于移動后的主機通知家鄉(xiāng)代理其當(dāng)前位置。不同于MIP的是，新的連接可以直接被定位到當(dāng)前的Loc，不需要家鄉(xiāng)代理來做間接轉(zhuǎn)發(fā)。在這個過程中，主機的Identifier不用改變，運行中的應(yīng)用程序只要向?qū)Χ税l(fā)送一個經(jīng)認(rèn)證的Loc更新消息，這樣可以在移動后保持通信狀態(tài)。

2.3.2 多宿主支持

下面介紹ILNP對多宿主的支持。這一點類似于ILNP對移動性的支持:一個子網(wǎng)可以使用多個Loc。這種方法同樣適用于站點、一組節(jié)點或單個節(jié)點的多宿主支持。但是，多個Loc僅僅用于標(biāo)識位置和路由，應(yīng)用層不會用到Loc相關(guān)的信息，因此不會破壞網(wǎng)絡(luò)主機對保持統(tǒng)一Identifier的需求。

2.3.3 NAT 支持

在ILNP中，NAT功能僅僅改變Loc的值，對應(yīng)用層而言，這個改變是不可見的。因此，在傳統(tǒng)NAT中不可用的協(xié)議，如FTP，P2P等，在ILNP的NAT中可以實現(xiàn)完美支持。

3 邊緣/核心網(wǎng)絡(luò)分離

互聯(lián)網(wǎng)面臨的路由可擴展性問題主要是因為所有的網(wǎng)絡(luò)都采用同一個地址空間，這樣導(dǎo)致了邊緣網(wǎng)絡(luò)增長會傳播到核心網(wǎng)絡(luò)。因此，邊緣/核心網(wǎng)絡(luò)地址分離能夠阻止邊緣網(wǎng)絡(luò)地址影響核心網(wǎng)絡(luò)路由系統(tǒng)，從而增強路由可擴展性。在2010年之前，這類方案一直是路由可擴展性的主流研究方向。

R.Hinden［9］在 1996 年第一次提出了通過封裝實現(xiàn)邊緣/核心網(wǎng)絡(luò)地址的分離，即ENCAPS機制。該機制基本確立了邊緣/核心網(wǎng)絡(luò)地址分離的基本方法，即通過映射機制及邊界路由器實現(xiàn)這種轉(zhuǎn)換。雖然只提出了簡單的思想，并沒有給出詳細(xì)的工作機制，但是，ENCAPS的重大意義在于開創(chuàng)了邊緣/核心網(wǎng)絡(luò)地址分離的研究方向。緊隨其后，有大量的方案被提出，包括 LISP［10］，APT［11］，SIX/ONE［12］，MILSA［13］等。這些方案在原理上大同小異，因此在本節(jié)中，我們將忽略具體方案，而主要將該類方案的統(tǒng)一模型及當(dāng)前的研究情況作出簡單的介紹。

首先介紹一下該類方案涉及到的相關(guān)概念。核心網(wǎng)絡(luò)和邊緣網(wǎng)絡(luò)兩部分組成整個網(wǎng)絡(luò)系統(tǒng)，對應(yīng)的地址系統(tǒng)也分為兩部分:邊緣網(wǎng)絡(luò)地址和核心網(wǎng)絡(luò)地址。地址映射系統(tǒng)(mapping system)維護全局的邊緣/核心地址映射關(guān)系。邊緣網(wǎng)絡(luò)地址雖然只出現(xiàn)在邊緣網(wǎng)絡(luò)中，但是一般也是全局唯一的。數(shù)據(jù)包在進入或離開核心網(wǎng)時都需要進行地址轉(zhuǎn)換:進入核心網(wǎng)時由入口路由器完成轉(zhuǎn)換;離開核心網(wǎng)時有出口路由器完成轉(zhuǎn)換。圖5是一個簡單的例子。

當(dāng)數(shù)據(jù)包進入核心網(wǎng)絡(luò)時，入口路由器向映射系統(tǒng)查詢源(邊緣)地址和目的(邊緣)地址對應(yīng)的核心網(wǎng)絡(luò)地址，然后通過封裝(隧道)或翻譯(地址重寫)的方式將數(shù)據(jù)包發(fā)送到目的網(wǎng)絡(luò)的出口路由器。如果采用的是封裝的方式，當(dāng)數(shù)據(jù)包到達出口路由器時，只需要解封裝就可以還原該數(shù)據(jù)包。因此，數(shù)據(jù)包離開核心網(wǎng)時不需要查詢映射系統(tǒng)。在這種情況下，一個核心網(wǎng)地址可以對應(yīng)多個邊緣網(wǎng)絡(luò)地址，因為不需要用核心網(wǎng)絡(luò)地址來查詢對應(yīng)的邊緣網(wǎng)絡(luò)地址。如果采用的是翻譯的方式，一個核心網(wǎng)絡(luò)只能映射到一個邊緣網(wǎng)絡(luò)地址。這樣才能夠保證出口路由器能夠根據(jù)重寫后的地址(核心網(wǎng)絡(luò)地址)查詢映射系統(tǒng)，從而還原目的(邊緣)地址。

圖5 邊緣/核心網(wǎng)絡(luò)地址分離方案模型Fig.5 Sketch map of edge/core network address separation solutions

邊緣/核心網(wǎng)絡(luò)地址分離實際上是將網(wǎng)絡(luò)可擴展性從路由系統(tǒng)轉(zhuǎn)移到了映射系統(tǒng)。因此，如何設(shè)計一個可擴展的映射系統(tǒng)是此類方案要解決的一個重要問題。因此，在這方面也有很多方案被提出，如LISP-DHT［26］，LISP-ALT［27］等。但是，目前還沒有被廣泛接受的統(tǒng)一方案。

4 路由聚合

以上方案，包括基于主機的ID/Loc分離和邊緣/核心網(wǎng)絡(luò)地址分離方案，都有一個共同的問題:對當(dāng)前互聯(lián)網(wǎng)改動較大，因此，無法在短期內(nèi)大范圍部署。而當(dāng)前網(wǎng)絡(luò)服務(wù)提供商當(dāng)前面臨核心網(wǎng)路由表過大導(dǎo)致運營成本不斷上升的問題，尤其是轉(zhuǎn)發(fā)表(forwarding information base，F(xiàn)IB)存儲在昂貴的TCAM中，給運營商帶來巨大的負(fù)擔(dān)。因此，ISP迫切需要立即可以投入使用的短期方案，在以上長期方案得到大范圍部署之前，這些短期方案可以用來減輕ISP的負(fù)擔(dān)。

在展開討論之前，首先介紹本節(jié)涉及的基本符號。IP前綴用0/1串附加*表示，如前綴1101*表示覆蓋所有起始4位為1101的IP地址。

4.1 虛擬聚合

為了迅速有效地減小路由表(尤其是FIB)，2009 年，H.Ballani等［18］提出虛擬聚合方案(virtual aggregation，ViAggr)。VA有2個設(shè)計目標(biāo):1)不改變路由軟件和路由協(xié)議;2)對外部網(wǎng)絡(luò)透明。目的只有一個，提高ViAggr的可部署性。

傳統(tǒng)互聯(lián)網(wǎng)路由系統(tǒng)中，每個路由器都存儲所有目的前綴的路由信息。這樣，收到任意數(shù)據(jù)包，該路由器都知道準(zhǔn)確的下一跳。在ViAggr中，每個路由器不需要保存全部前綴的路由信息。通過虛擬前綴的方式，如00*，01*，10*及11*。將整個路由空間分為少數(shù)子空間。對于每個虛擬前綴，都有相應(yīng)的聚合點(aggregation point，AP)負(fù)責(zé)保存相關(guān)路由信息。下面，我們從兩方面介紹ViAggr的原理。1)控制平面。當(dāng)鄰居自治域想本自治域通告路由時，通過路由反射的方法將路由發(fā)送給相應(yīng)的AP。AP向域內(nèi)其他路由器通告一條虛擬前綴路由即可。其他路由器只保存到AP的相關(guān)路由，總數(shù)為虛擬前綴的數(shù)量。2)數(shù)據(jù)平面。當(dāng)數(shù)據(jù)包進入本自治域時，入口路由器I如果不是對應(yīng)的AP，那么I通過隧道將該數(shù)據(jù)包發(fā)送到相關(guān)AP。該AP收到該數(shù)據(jù)包后，解封裝，然后根據(jù)全局路由表查詢出口路由器，同樣通過隧道的方式將數(shù)據(jù)包發(fā)送到出口路由器。出口路由器收到該數(shù)據(jù)包，解封裝后將該數(shù)據(jù)包發(fā)送到下一個自治域。圖6是ViAggr數(shù)據(jù)轉(zhuǎn)發(fā)實例。

圖6 ViAggr數(shù)據(jù)包轉(zhuǎn)發(fā)實例Fig.6 Instance of data transmission in ViAggr

雖然由于配置方面的代價，ViAggr還沒有實現(xiàn)大規(guī)模部署，但是ViAggr的出現(xiàn)使可擴展路由的研究熱點逐漸轉(zhuǎn)移到短期的聚合方案。在ViAggr之后出現(xiàn)了大量的FIB聚合方案。

4.2 傳統(tǒng)FIB聚合

ORTC(optimal routing table constructor)是最早系統(tǒng)研究FIB聚合的方案［14］。給定一個FIB，ORTC能夠計算出具有等價轉(zhuǎn)發(fā)行為的最小FIB。ORTC的計算過程包含3步。

1)“標(biāo)準(zhǔn)化”。將ORTC所有的非空內(nèi)部節(jié)點分裂到葉子，同時保證轉(zhuǎn)發(fā)行為不變。如圖7a所示，根節(jié)點是唯一的非空內(nèi)部節(jié)點，分裂后的結(jié)果如圖7b所示。

圖7 ORTC計算步驟Fig.7 Steps of ORTC

2)自底向上計算最流行下一跳。圖7c為計算的結(jié)果。

3)根據(jù)計算的結(jié)果從上到下實現(xiàn)聚合。圖7d為聚合之后的結(jié)果?？梢钥闯?，根據(jù)最長前綴匹配原則，聚合之后的FIB和初始的FIB具有相同的轉(zhuǎn)發(fā)行為。

ORTC雖然能夠計算出最小的FIB，但是ORTC有2個問題:1)空間開銷過大，其復(fù)雜度為O(WN)，其中O為復(fù)雜度上限;N為FIB前綴數(shù)量;對IPv4而言，W=32;2)沒有高效的在線更新算法。因此，IFTA［15］和 SMALTA［16］被提出用來彌補 ORTC 的不足。IFTA和SMALTA的基本思想是一致的:犧牲最優(yōu)聚合換取算法效率的提高。IFAT和SMALTA都采用了非最優(yōu)的算法來實現(xiàn)更新，每一次更新可能會使聚合結(jié)果偏離最小FIB。當(dāng)結(jié)果偏離最小FIB一定程度或處理了一定數(shù)量的更新之后，重新調(diào)用ORTC恢復(fù)最小FIB。

另外，X.Zhao等［17］在 2010 年提出 Level 1-4 FIB聚合。從Level 1到Level 4，聚合效果逐漸增強，算法復(fù)雜度也逐漸提高。相比ORTC，Level 1-4 FIB聚合將聚合對象限制為Trie(一種樹形結(jié)構(gòu)，用于路由表存儲)中的子樹，子樹最多3層。這樣，路由更新的影響可以限制在很小的范圍內(nèi)，從而提高更新效率。Level 1 FIB聚合:將和父親前綴下一跳一致的孩子前綴聚合;Level 2 FIB聚合:如果Trie中存在下一跳一致的兄弟前綴，那么通過插入其父親前綴將這2個前綴聚合，如圖8a所示;Level 3 FIB聚合:和Level 2類似，只是將范圍擴大到3層子樹中，如圖8b所示;Level 3 FIB聚合:比Level 3更進一步，如圖8c所示。

圖8 Level 2-4 FIB聚合方案示例Fig.8 Sketch map of level 2-4 FIB aggregation

傳統(tǒng)的FIB聚合方案具有2點重要特征:1)FIB聚合方案支持路由器級別的增量部署。也就是說，任何一個路由器可以根據(jù)需求部署FIB聚合方案，不需要任何其他路由器的配合。比如ViAggr在AS級別的可增量部署，這是一個巨大的進步;2)FIB聚合方案不改變路由和轉(zhuǎn)發(fā)行為。這一點保證了部署FIB聚合方案的路由器不會對其他路由器或AS產(chǎn)生任何影響。在這兩點中，尤其以第一點更為重要。

然后，F(xiàn)IB聚合也存在一些問題:1)FIB聚合定位為短期的解決方案，主要目標(biāo)是為長期解決方案爭取足夠的時間，緩解路由表增大為ISP帶來的巨大壓力。因此，F(xiàn)IB聚合并不能從根本上解決路由可擴展性問題，只能起到緩解的作用;2)傳統(tǒng)FIB聚合方案在大規(guī)模高密度的網(wǎng)絡(luò)中，性能比較差。具體原因如下:隨著鄰居數(shù)量的增大，2個前綴具有相同下一跳的概率降低，聚合的概率也隨之降低。而實際上，正是大規(guī)模的核心網(wǎng)絡(luò)迫切需要壓縮FIB表。

4.3 NSFIB 聚合

針對傳統(tǒng)FIB聚合方案存在的問題，Q.Li等在文獻［19-20］中提出了可選擇下一跳FIB(nexthopselectable FIB，NSFIB)聚合方案。該方案打破了傳統(tǒng)FIB聚合中每個前綴只有一個下一跳的限制，通過定義嚴(yán)格偏序(strict partial order，SPO)下一跳，為每個前綴構(gòu)建多個可選下一跳，從而形成NSFIB;并在此基礎(chǔ)上通過動態(tài)規(guī)劃算法，實現(xiàn)了NSFIB聚合算法。圖9顯示了NSFIB聚合機制。對比圖2顯示的路由器模型，NSFIB主要引入2個需要解決的問題:NSFIB構(gòu)造算法和NSFIB聚合算法。

圖9 NSFIB聚合機制Fig.9 NSFIB aggregation scheme

NSFIB聚合能夠大幅度地提升聚合的效果，根據(jù)實驗顯示，NSFIB可以將 FIB聚合到原來的10% ～20%。此外，相比傳統(tǒng)FIB聚合，NSFIB聚合效果屏蔽了網(wǎng)絡(luò)密度的影響:即性能不會隨著網(wǎng)絡(luò)度數(shù)的增加而降低。然而，作為一個全新的聚合方案，NSFIB聚合同樣存在一些問題。首先，NSFIB聚合引入非最優(yōu)下一跳，不可避免地導(dǎo)致路徑拉伸。針對這個問題，作者提出了限制下一跳數(shù)量的方法，從而有效控制路徑拉伸。其次，NSFIB聚合導(dǎo)致流量不可預(yù)測，給流量工程等帶來一定的困難。

4.4 RIB 聚合

除了 FIB聚合之外，RIB(routing information base)聚合也是一個可以有效壓縮路由表的方案。RIB聚合主要有2種方式:壓縮通告路由和壓縮本地路由。

壓縮通告路由:通過配置的聚合路由，減少向鄰居AS通告的前綴數(shù)量。假設(shè)自治域A有192.168.1.0/24，192.168.2.0/24 和 192.168.3.0/24 等路由，對鄰居自治域B配置如下聚合路由:＜192.168.0.0/16 A ＞。這樣，A 只會向B 通告192.168.0.0/16路由(下一跳AS為A本身)，被覆蓋的路由都不需要通告。雖然這種路由聚合方式無法直接壓縮本地路由表，但是廣泛部署不僅能夠有效減小核心網(wǎng)路由表的大小，還能將邊緣網(wǎng)絡(luò)的不穩(wěn)定屏蔽在核心網(wǎng)之外。然而，這種聚合方式影響了域間路由行為，有潛在的問題:路由環(huán)路和路由黑洞等。在文獻［28］中，作者針對這種聚合方式進行了詳細(xì)的分析。

壓縮本地路由:這種方法和FIB聚合類似，只是FIB聚合中針對具有相同下一跳的前綴，而此處的聚合針對的是具有相同下一跳AS的前綴。在文獻［21］中，作者將NSFIB聚合的思想應(yīng)用到本地路由壓縮方案中，大幅度減小了路由表。然而，該方案打破了FIB聚合路由器級別增量部署的特性，失去了FIB聚合最大的優(yōu)勢。

5 總結(jié)與分析

本文總結(jié)了現(xiàn)存的主流可擴展路由方案并給出相關(guān)分析。從6個方面討論了可擴展路由:解決/緩解路由可擴展性問題、路由表壓縮效果、是否能抑制路由更新、是否支持增量部署，是否影響路由轉(zhuǎn)發(fā)及是否改變路由協(xié)議。前3個因素反映性能，后3個因素反映代價。

如圖3所示，雖然基于主機的ID/Loc分離方案［6-8］和邊緣/核心網(wǎng)絡(luò)地址分離方案［9-12］都能夠解決路由可擴展性問題，然而這些方案都涉及路由協(xié)議的改變、對增量部署支持性較差且影響轉(zhuǎn)發(fā)。1)基于主機的ID/Loc分離方案。此類方案需要擴展IP頭部，導(dǎo)致轉(zhuǎn)發(fā)的有效載荷降低;需要主機端升級，推廣難度較大。2)邊緣/核心網(wǎng)絡(luò)地址分離方案。此類方案在轉(zhuǎn)發(fā)過程中需要查詢邊緣網(wǎng)絡(luò)地址和核心網(wǎng)絡(luò)地址的映射關(guān)系，并完成2次轉(zhuǎn)發(fā)，無法避免地會影響轉(zhuǎn)發(fā)速度。根據(jù)IPv6的部署經(jīng)驗，短期內(nèi)這些方案無法在互聯(lián)網(wǎng)中得到實際應(yīng)用，因此這些方案也被稱為長期方案。

然而，當(dāng)前互聯(lián)網(wǎng)迫切需要解決路由表過大帶來的成本上升、能耗過大等問題，因此，這給路由聚合［13-21］等短期方案提供了應(yīng)用的空間。雖然這些方案只能緩解路由可擴展性問題，但是部署代價比較小，體現(xiàn)在:1)FIB聚合路由器級別的增量部署，虛擬聚合支持自治域級別的增量部署;2)不改變路由協(xié)議;3)傳統(tǒng)FIB聚合不影響轉(zhuǎn)發(fā)行為，虛擬聚合和NSFIB聚合只影響域內(nèi)路由轉(zhuǎn)發(fā)行為。因此，這些方案可以作為短期方案來緩解ISP的壓力，為能夠徹底解決問題的長期方案爭取足夠的部署時間。

［1］The Miniwatts Marketing Group.Top 20 Countries with the highest number of Internet users［EB/OL］.(2012-12-01) ［2012-12-03］.http://www.internetworldstats.com/top20.htm.

［2］MEYER D，ZHANG L，F(xiàn)ALL K.RFC 4984，Report from the IAB Workshop on Routing and Addressing［R］.USA:IETF，2007.

［3］Huston Geoff.BGP analysis reports:BGP table statistics［EB/OL］.(2012-04-01) ［2012-11-13］.http://bgp.potaroo.net.

［4］ELMOKASHFI Ahmed，KVALBEIN Amund，DOVROLIS Constantine.On the scalability of BGP:the role of topology growth［J］.IEEE JSAC，2010，28(8):1250-1261.

［5］BU Tian，GAO Lixin，TOWSLEY Don.On characterizing BGP routing table growth［J］.Computer Networks，2004，45(1):45-54.

［6］NORDMARK E，BAGNULO M.RFC 5533，Shim6:Level 3 Multihoming Shim Protocol for IPv6［R］.USA:IETF，2009.

［7］MOSKOWITZ R，NIKANDER P，JOKELA P，et al.RFC 5201，Host Identity Protocol［R］.USA:IETF，2008.

［8］ATKINSON Randall，BHATTI Saleem，HAILES Stephen.Evolving the internet architecture through naming［J］.IEEE JSAC，2010，28(8):1319-1325.

［9］HINDEN R.RFC 1995，New Scheme for Internet Routing and Addressing(ENCAPS)for IPNG［R］.USA:IETF 1996.

［10］LEWIS Darrel，F(xiàn)ULLER Vince，F(xiàn)ARINACCI Dino，et al.Locator/ID separation protocol(LISP)，IETF Draft［R］.USA:IETF，2009.

［11］JEN Dan，MEISEL Michael，YAN He，et al.Towards a new Internet routing architecture:Arguments for separating edges from transit core［C］//Soul.Proceedings of HotNets VII.Galgary:ACM Press，2008:1-6.

［12］VOGT Christian.Six/one router:a scalable and backwards compatible solution for provider independent addressing［C］//Soul.Proceedings of MobiArch ＇08.Seattle:ACM Press，2008:13-18.

［13］PAN Jianli，JAIN Raj，PAUL Subharthi，et al.MILSA:a new evolutionary architecture for scalability，mobility，and multihoming in the future internet［J］.IEEE JSAC，2010，28(8):1344-1362.

［14］DRAVES R P，KING C，VENKATACHARY S，et al.Constructing optimal IP routing tables［C］//Soul.Proceedings of IEEE INFOCOM.New York:IEEE Press，1999:88-97.

［15］LIU Y，ZHAO X，NAM K，et al.Incremental forwarding table aggregation［C］//Soul.Proceedings of IEEE GLOBECOM.Miami:IEEE Press，2010:1-6.

［16］UZMI Zartash Afzal，NEBEL Markus，TARIQ Ahsan，et al.SMALTA:practical and near-optimal FIB aggregation［C］//Soul.Proceedings of ACM CoNEXT.New York:ACM Press，2011:1-12.

［17］ZHAO Xin ，LIU Yaoqing ，WANG Lan ，et al.On the aggregatability of router forwarding tables［C］//Soul.Proceedings of IEEE INFOCOM.Piscataway:IEEE Press，2010:848-856.

［18］BALLANI Hitesh ，F(xiàn)RANCIS Paul ，CAO Tuan，et al.Making routers last longer with ViAggre［C］//Soul.Proceedings of NSDI.Boston:USENIX Association，2009:453-466.

［19］LI Qing ，WANG Dan ，XU Mingwei，et al.On the scalability of router forwarding tables:Nexthop-selectable FIB aggregation［C］//Soul.Proceedings of IEEE INFOCOM.Shanghai:IEEE Press，2011:321-325.

［20］LI Qing，XU Mingwei，CHEN Meng.NSFIB construction＆ aggregation with next hop of strict partial order［C］//Soul.Proceedings of IEEE INFOCOM.Turin:IEEE Press，2013:1-5.

［21］WANG Yangyang，BI Jun，WANG Jianping .Towards an aggregation-aware internet routing［C］//Soul.Proceedings of ICCCN.Munich:IEEE Press，2012:1-7.

［22］KRIOUKOV Dmitri，F(xiàn)ALL Kevin.Compact routing on internet-like graphs［C］//Soul.Proceedings of IEEE INFOCOM.Hong Kong:IEEE Press，2004:209-219.

［23］JAIN S，CHEN Y，ZHANG Z L，et al.VIRO:a scalable，robust and namespace independent virtual id ROuting for future networks［C］//Soul.Proceedings of IEEE INFOCOM.Shanghai:IEEE Press，2011:2381-2389.

［24］OLIVEIRA R，LAD M，ZHANG Beichuan，et al.Geographically informed inter-domain routing［C］//Soul.Proceedings of IEEE ICNP.Beijing:IEEE Press，2007:103-112.

［25］LI Taoyu ，ZHU Yuncheng ，XU Ke，et al.Performance model and evaluation on geographic-based routing［J］.Comput Commun，2009:32(2):343-348.

［26］MATHY Laurent，IANNONE Luigi.LISP-DHT:towards a DHT to map identifiers onto locators［C］//Soul.Proceedings of ACM CoNEXT.Madrid:ACM Press，2008:1-6.

［27］FULLER Vince ，F(xiàn)ARINACCI Dino，MEYER David，et al.LISP alternative topology(LISP+ALT)［R］.USA:IETF Draft，2011.

［28］LE F，XIE G G，ZHANG H.On route aggregation［C］//Soul.Proceedings of ACM CoNEXT.Tokyo:ACM Press，2011:1-12.