徐明偉，李 清

(1.清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，北京 100084;2.清華信息科學(xué)與技術(shù)國(guó)家實(shí)驗(yàn)室(籌)，北京 100084)

0 引言

自上個(gè)世紀(jì)70年代誕生之日起，互聯(lián)網(wǎng)飛速發(fā)展，現(xiàn)已經(jīng)成為全球性的商業(yè)網(wǎng)絡(luò)平臺(tái)。據(jù)統(tǒng)計(jì)，當(dāng)前互聯(lián)網(wǎng)終端數(shù)量已經(jīng)從上個(gè)世紀(jì)80年代初的幾百增長(zhǎng)到2012的近10億;而用戶(hù)數(shù)量也從最初的幾百增長(zhǎng)到2012的近25億［1］。此外，隨著移動(dòng)終端(手機(jī)、平板電腦等)的加入，互聯(lián)網(wǎng)將得到進(jìn)一步發(fā)展。然而隨著規(guī)模的膨脹，互聯(lián)網(wǎng)面臨越來(lái)越多的問(wèn)題:安全問(wèn)題、節(jié)能問(wèn)題、擴(kuò)展問(wèn)題等。其中，當(dāng)前互聯(lián)網(wǎng)路由系統(tǒng)面臨嚴(yán)重的可擴(kuò)展問(wèn)題已經(jīng)成為廣泛的共識(shí)［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é)議為開(kāi)放最短路徑優(yōu)先協(xié)議(open shortest path first，OSPF)和中間系統(tǒng)到中間系統(tǒng)路由協(xié)議(intermediate system to intermediate system routing protocol，ISIS)。BGP路由器通過(guò)路由通告完成域間路由的傳播，通過(guò)屏蔽自治域的拓?fù)湫畔?，BGP可以控制域間路由信息的規(guī)模。然而，由于多宿主(multihoming)、流量工程(traffic engineering，TE)等原因，越來(lái)越多不可聚合的提供商獨(dú)立(provider independent，PI)地址通過(guò)BGP注入到全局網(wǎng)絡(luò)中。這直接導(dǎo)致核心網(wǎng)路由表急劇增加，使互聯(lián)網(wǎng)路由系統(tǒng)面臨嚴(yán)重的可擴(kuò)展性問(wèn)題。圖1顯示了1994-2012年互聯(lián)網(wǎng)骨干網(wǎng)絡(luò)路由表的增長(zhǎng)情況:1994年的骨干網(wǎng)路由表僅包含不到2萬(wàn)條表項(xiàng);2012年這個(gè)數(shù)字已經(jīng)超過(guò)40萬(wàn)［3］。隨著IPv6的逐漸部署，被網(wǎng)絡(luò)地址轉(zhuǎn)換等技術(shù)抑制的地址會(huì)得到釋放，可能會(huì)進(jìn)一步加劇互聯(lián)網(wǎng)路由可擴(kuò)展性問(wèn)題。

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

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

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

1 可擴(kuò)展路由研究概述

1.1 路由可擴(kuò)展性原因分析

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

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

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

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

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

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

1.2 可擴(kuò)展路由解決方案概述

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

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

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

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

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

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

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

2 基于主機(jī)的ID/Loc分離

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

2.1 Shim6 協(xié)議

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

2.1.1 Shim6 簡(jiǎn)介

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

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

2.1.2 Shim6 通信流程

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

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

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

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

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

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

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

7)除了擴(kuò)展檢測(cè)之外，某個(gè)主機(jī)也會(huì)通過(guò)某種方式發(fā)現(xiàn)自己的某個(gè)Loc失效，此外該主機(jī)可以通過(guò)Shim子層主動(dòng)告知對(duì)方該故障。

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

2.1.3 性能分析

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

此外，Shim6主機(jī)和不支持Shim6的主機(jī)通信會(huì)退化到?jīng)]有Shim6的標(biāo)準(zhǔn)通信方式。Shim6具有很強(qiáng)的局限性，因?yàn)樗皇菍?duì)多宿主導(dǎo)致的可擴(kuò)展性問(wèn)題有效。其他因素，如主機(jī)移動(dòng)帶來(lái)的renumbering，仍然會(huì)導(dǎo)致路由可擴(kuò)展性問(wèn)題。而相比之下，ILNP［12］的解決就更加全面。

2.2 Host identifier protocol(HIP)

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

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

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

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

2.3 Identifier locator network protocol

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

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

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

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

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

2.3.1 移動(dòng)性支持

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

2.3.2 多宿主支持

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

2.3.3 NAT 支持

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

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

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

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

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

當(dāng)數(shù)據(jù)包進(jìn)入核心網(wǎng)絡(luò)時(shí)，入口路由器向映射系統(tǒng)查詢(xún)?cè)?邊緣)地址和目的(邊緣)地址對(duì)應(yīng)的核心網(wǎng)絡(luò)地址，然后通過(guò)封裝(隧道)或翻譯(地址重寫(xiě))的方式將數(shù)據(jù)包發(fā)送到目的網(wǎng)絡(luò)的出口路由器。如果采用的是封裝的方式，當(dāng)數(shù)據(jù)包到達(dá)出口路由器時(shí)，只需要解封裝就可以還原該數(shù)據(jù)包。因此，數(shù)據(jù)包離開(kāi)核心網(wǎng)時(shí)不需要查詢(xún)映射系統(tǒng)。在這種情況下，一個(gè)核心網(wǎng)地址可以對(duì)應(yīng)多個(gè)邊緣網(wǎng)絡(luò)地址，因?yàn)椴恍枰煤诵木W(wǎng)絡(luò)地址來(lái)查詢(xún)對(duì)應(yīng)的邊緣網(wǎng)絡(luò)地址。如果采用的是翻譯的方式，一個(gè)核心網(wǎng)絡(luò)只能映射到一個(gè)邊緣網(wǎng)絡(luò)地址。這樣才能夠保證出口路由器能夠根據(jù)重寫(xiě)后的地址(核心網(wǎng)絡(luò)地址)查詢(xún)映射系統(tǒng)，從而還原目的(邊緣)地址。

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

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

4 路由聚合

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

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

4.1 虛擬聚合

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

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

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

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

4.2 傳統(tǒng)FIB聚合

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

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

圖7 ORTC計(jì)算步驟Fig.7 Steps of ORTC

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

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

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

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

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

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

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

4.3 NSFIB 聚合

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

圖9 NSFIB聚合機(jī)制Fig.9 NSFIB aggregation scheme

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

4.4 RIB 聚合

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

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

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

5 總結(jié)與分析

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

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

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

［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.