互聯(lián)網(wǎng)路由擴展性研究狀況分析

摘要:Internet的快速發(fā)展對路由擴展性造成了巨大的壓力。為了Internet能夠持續(xù)、穩(wěn)定、快速的發(fā)展，互聯(lián)網(wǎng)技術領域學術界和工業(yè)界提出了一些針對Internet的路由擴展性的解決方案。文章基于Internet面臨的路由擴展性問題，分析導致問題的原因；在對影響Internet路由擴展性的若干因素進行分析的基礎上，重點介紹互聯(lián)網(wǎng)技術領域學術界和工業(yè)界提出的一些典型解決方案；在對Internet路由擴展性問題行總結的基礎上，提出未來Internet路由系統(tǒng)的需求。

關鍵字:Internet路由系統(tǒng)；邊界網(wǎng)關協(xié)議；可擴展性

英文摘要: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

基金項目：國家重點基礎研究發(fā)展規(guī)劃 (“973”計劃)課題 (2009CB320504)；國家高技術研究發(fā)展計劃資助(“863”計劃)課題(2007AA01Z206, 2009AA01Z210)

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

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

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

1 影響互聯(lián)網(wǎng)路由擴展性因素

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

1.1 IP地址的語義重載

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

1.2 站點多歸屬

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

1.3 流量工程

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

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

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

1.5 反前綴劫持

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

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

2 Internet路由擴展性研究狀況

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

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