朱培棟 趙金晶 鄧文平

摘要:作為Internet的核心基礎設施,基于BGP協(xié)議的域間路由系統(tǒng)目前在擴展性、端到端性能、安全性與可信性等方面存在問題。由于部署的廣域性、AS的自治性以及ISP之間交互的復雜性、域間路由行為的動態(tài)性,使得人們對域間路由系統(tǒng)的結構和行為規(guī)律尚未充分理解,缺乏全面有效的解決方案,大規(guī)模的系統(tǒng)的網絡實驗難以開展。理想的域間路由系統(tǒng)及其支撐的Internet在性能上應具有快速恢復和全局優(yōu)化的能力,在安全上應具有自主防范和協(xié)同控制能力,在運營上應具有自主配置和協(xié)同管理能力。

關鍵詞:因特網;域間路由;擴展能力;性能;安全

Abstract: As the critical infrastructure of the Internet, the Inter-Domain Routing (IDR) system based on Border Gateway Protocol (BGP) is suffering from problems in scalability, end-to-end performance, security and trustability. The IDR routing behaviors and structures have not been understood thoroughly due to its wide deployment, autonomy of Autonomous System (AS), complexity of interactions between Internet Service Providers (ISPs) and dynamics of running behaviors. A comprehensive and efficient solution is not available, and it is hard to conduct large scale network experiments to deal with the intricate IDR issues. An ideal IDR and the Internet based on it are expected to have fast recovery and global optimization ability in performance, self-defense and collaborative control power in security, and self-configuration and cooperative management in operations.

Key words: Internet; inter-domain routing; scalability; performance; security

Internet是自治系統(tǒng)(AS)按照各種商業(yè)關系互連的集合。AS由互聯(lián)網服務提供商(ISP)擁有?；贏S的劃分,Internet采用層次式路由結構。

1 域間路由系統(tǒng)的結構

Internet結構模型是建立Internet系統(tǒng)模型的基礎,也是域間路由協(xié)議設計、域間路由系統(tǒng)開發(fā)與部署的重要依據(jù)。

1.1 拓撲模型

Internet的模型研究經歷了從經驗假設到客觀分析、從單純的計算機網絡研究到復雜系統(tǒng)特征化研究的過程。根據(jù)研究目的和生成方式不同,分為拓撲生成模型和動態(tài)演化模型。前者只要求保證產生的拓撲圖符合Internet關鍵的外在特征,而動態(tài)演化模型力求從內到外、從微觀到宏觀展現(xiàn)真實的Internet成長過程。

1.1.1 拓撲生成模型

最早的網絡拓撲模型是1988年提出的Waxman平面隨機模型。此后關注Internet的層次性特征,例如,Transit-Stub模型將AS域劃分為Transit類和Stub類?；趯哟侮P系模型的分析,處于頂層的十幾個AS絕大部分屬于美國的AT&T、Sprint、Verizon、Level3、Global Crossing、Qwest、Savvis以及日本NTT、印度Tata電信等公司,彼此全互連,構成了整個Internet的核心。從全球AS互連結構來看,香港電訊盈科(PCCW)的AS最高處于第二層,中國電信的AS4134大致處于第三層。1999年Faloutsos兄弟3人發(fā)現(xiàn)Internet拓撲結構中存在的冪律關系[1],從而將Internet拓撲與生物學、社會學中的復雜網絡聯(lián)系起來,使其成為無尺度網絡的一個實例。值得注意的是,Internet結構的冪律主要體現(xiàn)在AS級互連,在路由器級由于路由器端口限制以及網絡運營部署的約束,并沒有顯著的冪律特性。AS級互連還表現(xiàn)出異類相聚、小世界、富人俱樂部和社團特征,以及一定的自相似性,例如中國大陸AS級拓撲的宏觀特征與全球拓撲的某些類似[2]。

1.1.2 動態(tài)演化模型

AS級的無尺度結構特性是AS局部利益極大化決策的結果,選擇連附上層AS的概率正比于提供商能夠免費到達的網絡或提供商互連的度數(shù)。1999年D.Carlson和J.Doyle提出高度優(yōu)化的容錯模型(HOT)[3]。建模過程不僅關注統(tǒng)計特性的顯式表現(xiàn),還考慮網絡設計中單個ISP需要面對的經濟因素和技術約束等。在網絡朝最優(yōu)化方向發(fā)展的過程中,冪律等外部特性會自然地表現(xiàn)出來。HOT模型具有高度確定的組織結構,注重提高產出和容錯性,關注區(qū)域特性,進行網絡發(fā)展預測和求解域間路由系統(tǒng)的問題更為準確和可信。

1.2 AS商業(yè)關系模型

AS關系模型描述AS之間依據(jù)商業(yè)合同所形成的相互關系。主要包括:客戶-提供商,提供商-客戶,對等服務以及兄弟關系。L.Gao設計算法通過分析路由表數(shù)據(jù)可以比較準確地推導各個AS之間的商業(yè)關系[4]。根據(jù)商業(yè)關系約束可判斷路由宣告中AS-Path信息的異常,例如,如果AS把來自一個提供商的路由轉發(fā)給了其他提供商,即在層次關系圖中出現(xiàn)了“谷底”,可判定這條路由違背了商業(yè)關系,也可能是偽造的路由。

1.3 域間路由協(xié)議的演化

路由系統(tǒng)是隨著Internet的發(fā)展逐漸成長起來的。在ARPANET初建時只有一個骨干網,后來為了實現(xiàn)多個網絡互連設置了各種路由器。隨著互聯(lián)網規(guī)模的增長,再讓所有路由器保存整個互聯(lián)網的全部路由信息是不明智的,于是分為域間和域內路由。

邊界網關協(xié)議(BGP)是目前唯一在用的域間路由協(xié)議,最早的協(xié)議版本由1989年發(fā)布的RFC1105定義,由Cisco和IBM基于EGP協(xié)議及其在NSFNET骨干網的使用經驗編寫。目前廣泛使用的是1995年RFC1771定義的BGP-4版本。隨著設備制造商對BGP功能的擴展和完善,以及對Internet新技術的支持,IETF的域間路由(IDR)工作組多年來一直非?；钴S,先后修訂和發(fā)布了60多個RFC規(guī)范BGP協(xié)議及相關功能,最新的BGP-4規(guī)范由RFC4271定義,最新的功能規(guī)范是RFC5492對BGP能力宣告參數(shù)的重新定義。支持IPv6的BGP4+除了傳播的路由信息的地址格式外,與BGP-4沒有明顯的協(xié)議機制差別。BGP-4還擴展了對32位AS號的支持。

2 域間路由的性能問題

雖然基本的BGP只是一種簡單的路徑向量路由協(xié)議,但是域間路由系統(tǒng)卻是一個復雜系統(tǒng)。復雜性來源于域間路由系統(tǒng)規(guī)模的巨大性、ISP互連關系的豐富性、路由策略交互的動態(tài)性和BGP配置的多樣性。

2.1 擴展性問題

根據(jù)亞太網絡信息中心(APNIC)首席科學家G.Huston對核心網絡路由信息的統(tǒng)計,2009年7月IPv4路由表中可見的AS號近3.2萬,平均每個月新增200多個,表現(xiàn)出超線性趨勢;路由表(RIB)有58.7萬表項,轉發(fā)表(FIB)29.9萬,并以每兩年大致1.2倍和1.3倍的速度增長。Internet體系結構委員會(IAB)為此專門發(fā)布RFC4984指出了路由擴展性問題的嚴重性。對BGP這類基于拓撲的路由協(xié)議而言,控制路由表規(guī)模實用的主要方法是拓撲聚合,但是多宿主、流量工程、ISP的合并或收購等因素造成大量不可聚合的路由信息。路由表項的不可聚合增加了路由信息宣告的數(shù)量和頻率,從而加大了路由器處理路由信息和更新轉發(fā)表的時間。同時,將網絡邊緣的拓撲狀態(tài)擴散到整個網絡,大量前綴不斷修改、產生或撤銷造成了路由信息的震蕩,這其中也可能存在持續(xù)時間比較短的網絡前綴劫持。T.Li發(fā)現(xiàn)摩爾定律對高端路由器并不適用,主要因為高端路由器采用的低延遲高容量SRAM生產,批量小,其性能的提高和代價的下降跟不上轉發(fā)表的增長速度。轉發(fā)引擎的散熱問題也制約了路由器性能的進一步提升?？赡艿膶Σ甙ú捎肕ULTI6、SHIM6工作組的多宿主方案,定位器/標志符分離協(xié)議(LISP)等。LISP作為互聯(lián)網邊緣和核心路由器之間的隧道機制,也很好地解決了IP地址的重載問題,但是會增加核心路由器的復雜性。隧道技術增加經費并減慢網絡流量,甚至會因為傳送數(shù)據(jù)過大而丟失數(shù)據(jù)。各種方案目前都處于早期的試驗階段。文獻[5]指出,Internet結構的無尺度特性是實現(xiàn)基于聚合的層次路由的天然障礙,難以達到與網絡規(guī)模成對數(shù)關系的理想的路由更新數(shù)量和路由表大小;LISP這類名址分離的路由結構名址映射表的更新開銷也會制約擴展性。因此,如何實現(xiàn)不需要收斂的路由協(xié)議,如何像社會網絡那樣不需了解網絡全景視圖仍然能夠有效選路,以及如何充分利用Internet的各種拓撲特性設計高效緊致的路由算法,仍然是重要的課題。

2.2 端到端性能問題

收斂是指目標網絡的可達性視圖在全網達成一致。這種一致是相對的,由于觀察點的不同和路由選擇策略的差異,允許不同的節(jié)點具有到達目標網絡的不同路徑,但都必須是真實的、反映網絡拓撲實際互連狀態(tài)的路徑。

2.2.1 不收斂

研究發(fā)現(xiàn)BGP路由存在無法收斂的情況,主要表現(xiàn)某些情況下內部BGP最佳路由的選擇無法穩(wěn)定。由于各個路由器本地的選擇策略存在沖突,任何一組BGP路由都無法同時滿足它們的需求。統(tǒng)計表明Internet路由中只有25%～35%可用性超過99.99%,10%可用性少于95%。

2.2.2 收斂慢

收斂慢是路由協(xié)議的一種病態(tài)行為。2000年,C.Labovitz統(tǒng)計發(fā)現(xiàn)路由故障平均需要3分鐘恢復和重新路由,某些多宿主的故障恢復達15分鐘。路由的收斂速度對VoIP、Video Game和商業(yè)事務很重要,持續(xù)幾百毫秒就會中斷某些應用。2007年MIT的N.Kushman等對Skype和Vonage跨域語音電話的性能進行測量,發(fā)現(xiàn)BGP路由的慢收斂對通話質量的影響像網絡擁塞一樣嚴重,引起呼叫放棄或較長時間的不可用[6]。D.Pei等發(fā)現(xiàn)路由撤銷和恢復過程中,路由器最多會遍歷N !個可能路徑(N是系統(tǒng)中的AS數(shù)目),宣告多條暫時的無效路由,經過幾次路由擴散才達到收斂狀態(tài)。另外,其他類型的網絡可達性信息的快速變化引起“路由抖動”,也會增加報文丟失率、網絡收斂延時,帶來路由處理的額外開銷。

2.2.3 路徑長

ISP互聯(lián)遵循經濟學的規(guī)律,主要動力是減少轉發(fā)代價。各個ISP都是從自身利益的最大化出發(fā),在沒有全局規(guī)則調和約束的情況下,無法獲得全局利益的最大化。例如,具有對等關系的ISP往往采用“熱土豆(Hot Potato)”路由,選擇最快離開本ISP的出口把流量送到對方網絡,而不論流量在對方網絡中經歷的路徑長短。有的ISP承諾使用“冷土豆(Cold Potato)”路由,但是實際的測量發(fā)現(xiàn)很可能沒有實行這種策略。

從路由器級別考察,同樣存在自私路由的情況。E.Tardos等通過理論分析發(fā)現(xiàn),為了快速傳遞數(shù)據(jù),路由器往往選擇最少擁塞的路由,宏觀來看速度較快的路由很快就會被堵塞;當路由軟件再次更換路由后仍然造成堵塞的惡性循環(huán)。我們認為目前Internet路由協(xié)議還沒有這樣強的自適應能力和細粒度的調整性能,但是隨著流量工程技術的廣泛深入應用,在局部優(yōu)化的同時需要多個ISP共同考慮全局性能。

2.2.4 QoS路由

多年來服務質量(QoS)路由是各種類型網絡的重要研究內容。學者們設計的各種QoS路由機制很少得到應用,主要有3個原因:網絡規(guī)模的日益擴大、新型業(yè)務的不斷展開和網絡安全的嚴峻形勢,使保持網絡的可達性成為網絡管理員的核心任務;缺乏簡單有效的跨域QoS機制;有些ISP寧愿采用資源過量配置的方法實現(xiàn)高質量服務。但是,測試發(fā)現(xiàn)ISP對網絡流量做到一定程度的區(qū)分服務,例如處理來自不同上游AS的流量時優(yōu)先考慮來自客戶的數(shù)據(jù),對BitTorrent和UDP等類型流量的歧視等。但是,在網絡資源總量不足的情況下ISP對網絡流量區(qū)別對待,有人認為違背網絡中立性。

目前BGP只是把最佳路由寫入轉發(fā)表并轉告給下游路由器,影響了流量工程能力和路由的靈活性,但是如果把學到的多條路徑都宣告出去將會使擴展性問題更嚴重。在全網范圍實現(xiàn)跨域的QoS保證還比較遙遠。跨域的IP組播由于缺乏有效的商業(yè)模式和部署結構的過于復雜,現(xiàn)在的組播往往通過應用層來實現(xiàn),IP組播的高效率并沒有得到徹底的實現(xiàn)。

3 域間路由系統(tǒng)的安全性與可信性

路由系統(tǒng)的安全性與可信性是彼此交叉密切相關的2個方面,路由系統(tǒng)的安全性又與健壯性密切相關。由于BGP路由信息可以擴散到整個Internet,因此必須從全網角度來考察這3個方面,構建可依賴的路由系統(tǒng)。

3.1 路由系統(tǒng)的安全性

Internet路由系統(tǒng)的安全性多年來為人們所忽視,甚至等同于路由器的安全性。正如域名系統(tǒng)(DNS)的安全性一樣,作為網絡基礎設施的路由系統(tǒng)也面臨嚴峻的安全威脅,具體表現(xiàn)為:對路由系統(tǒng)的破壞;對特定網絡的破壞;對網絡流量的操縱;基于路由偽造的應用攻擊(2005年6月,Google對外服務中斷了約半個小時,分析發(fā)現(xiàn)是加拿大AS號為174的ISP非法宣告了其前綴)。北美網絡運營商協(xié)會(NANOG)披露,宣告?zhèn)卧斓刂方oEmail服務器使用,可制造并傳播大量難以溯源的垃圾郵件,由于垃圾郵件服務器需要與合法服務器進行TCP交互,離開路由偽造無法實施這類攻擊。網站釣魚最簡單的方法是通過域名偽造實現(xiàn),如果采用相同的域名可以通過DNS攻擊修改名址映射實現(xiàn),而如果采用和真實網站一樣的域名和IP地址,就可以通過路由偽造實現(xiàn),這種攻擊方式更加隱蔽。歷史上發(fā)生多起路由前綴劫持和路由泄漏的事件。這說明域間路由系統(tǒng)缺乏有效的路由鑒別機制,路由的可信性是目前威脅路由安全的主要問題。

目前,提高路由安全性的對策主要包括接收方驗證機制、路由安全監(jiān)測和可信性判斷系統(tǒng)、新型協(xié)議機制的設計等。提出的可信性驗證和評估方法主要有IRV和Listen-and-Whisper等。路由安全監(jiān)測系統(tǒng)主要有UCLA的PHAS、RIPE的MyASN服務、Renesys公司的Gradus服務以及國防科技大學的RouSSeau系統(tǒng)等,主要基于分布采集的路由表和路由報文進行異常判斷。為了便于多ISP間異構路由器不同格式路由表的采集和信息發(fā)布,IETF開始討論基于XML的統(tǒng)一格式問題。安全協(xié)議機制主要有美國BBN公司的S-BGP、CISCO公司的soBGP、加拿大Carleton大學的psBGP以及國防科技大學的SE-BGP[7]等,4種方案的安全能力大致相當,采用的信任模型各不相同,分別是以ICANN為根的層次信任模型、Web-of-trust信任模型、基于前綴斷言列表的分布式信任模型,以及基于AS聯(lián)盟的轉換者信任模型(TTM)。雖然RFC3779設計了基于X.509的IP地址和AS證書格式,也開展了局部實驗,但是S-BGP等離廣泛部署還很遙遠。

3.2 路由系統(tǒng)的可信性

BGP路由的可信性要求路由資源分配、路由策略、路由信息和數(shù)據(jù)轉發(fā)的一致性,即在Internet管理平面、ISP商業(yè)平面、路由協(xié)議控制平面和路由器轉發(fā)平面一致。

(1)路由信息的不可信,指ISP傳遞的路由信息中宣告的前綴不符合資源的分配知識,宣告的AS-Path不是路由信息實際經過的傳播路徑。

(2)路由行為的不可信,指路由信息與商業(yè)合約中聲明的路由策略不一致。例如,客戶把來自提供商A的路由泄露給提供商B而形成谷底路由;采用Prepend命令使宣告的路由具有較長路徑,導致其他ISP不選擇自己進行轉發(fā),雖然按照商業(yè)關系向對方宣告了路由但是實際上并不愿履行數(shù)據(jù)轉發(fā)義務。

(3)轉發(fā)行為的不可信,指ISP的數(shù)據(jù)轉發(fā)行為與路由信息中說明的不一致。例如,通過靜態(tài)路由或者改變下一跳路由器,向沒有宣告路由的網絡發(fā)送流量,以獲得免費的出口轉發(fā)等。

實現(xiàn)全面的可信路由需要在ISP之間建立廣泛的信任機制和分布式可信監(jiān)測體系。

4 域間路由系統(tǒng)的運營

BGP是基于策略的路由(PBR)協(xié)議。路由策略綜合考慮數(shù)據(jù)轉發(fā)的性能、安全、可靠性、經濟性等諸多要求。路由器的配置文件是ISP策略的重要體現(xiàn)。隨著網絡規(guī)模的擴展,ISP互連關系的錯綜復雜,網絡協(xié)議功能的日益豐富,系統(tǒng)中有大量的故障由人為因素引起,不恰當?shù)呐渲每赡軐е侣酚烧鹗幓蛞l(fā)路由安全事件。MIT開發(fā)的路由配置檢查器(RCC)已在一些ISP試用。RCC支持一個AS內部多個路由器的配置檢查,但是不提供多ISP或多AS協(xié)同檢查。國防科技大學開發(fā)了多ISP路由協(xié)同配置系統(tǒng)ISP-Policy,采用多方安全計算方法,在滿足ISP之間策略私密性和策略一致性的需求方面取得較好進展。

為了協(xié)調多個ISP的協(xié)同配置問題,美國自然基金會網絡(NSFNET)路由仲裁者(RA)項目1995年發(fā)起了基于路由注冊的方法,現(xiàn)有32個路由注冊庫(IRR)。與Internet各地區(qū)中心的網絡資源數(shù)據(jù)庫(RIR)不同,路由策略蘊含較多的網絡運營信息,具有一定私密性,公開到庫中的策略信息要么過時,要么與實現(xiàn)的策略不一致,無法保證內容的可信性與完整性。近年來IRR的實施取得較好的進展,例如一些大型ISP強制客戶注冊,不注冊的路由宣告將被過濾;歐洲網絡信息中心(RIPE-NCC)在實施路由注冊制度方面也取得成效。但是IRR的固有缺陷仍然沒有消除,對來自具有對等關系的ISP或者提供商的路由信息仍然無法有效驗證和過濾。

5 結束語

域間路由系統(tǒng)的這些問題是密切相關的,有的源于BGP協(xié)議和域間路由模式的固有缺陷,有的由于網絡運營商的利益約束和交互的復雜性。域間路由系統(tǒng)是以AS為節(jié)點構成的自組織系統(tǒng),單個AS體現(xiàn)出ISP的意志,整個域間路由系統(tǒng)的運行沒有統(tǒng)一的管理,因此需要充分考慮ISP的社會屬性,結合社會學和經濟學的方法,探求域間路由系統(tǒng)問題的求解,例如博弈論、市場理論的應用和信譽體系、協(xié)同機制的設計等。域間路由系統(tǒng)是高度動態(tài)、快速成長和不斷演化的,需要借鑒生態(tài)學的原理來引導、借用生物學的機理來設計有效的機制促進其健康發(fā)展。域間路由系統(tǒng)具有復雜巨系統(tǒng)的特點,仍然需要物理學的方法探求蘊含的規(guī)律,需要數(shù)學的方法刻畫結構與行為模型,在采用復雜性理論和系統(tǒng)科學方法把握其宏觀特征的同時,運用控制科學的理論和方法設計有效的控制與調節(jié)機制。

正如Internet一樣,盡管存在諸多問題,但是數(shù)十年的運行表明,BGP路由協(xié)議總的來說是高效、穩(wěn)定、安全和健壯的。BGP作為最重要的域間路由協(xié)議將在相當長的時間內繼續(xù)存在。通過研究者、制造商和運營商等長期不懈的努力,理想的域間路由系統(tǒng)及其支撐的Internet在性能上應具有快速恢復和全局優(yōu)化的能力,在安全上具有自主防范和協(xié)同控制能力,在運營上具有自主配置和協(xié)同管理能力。

6 參考文獻

[1] FALOUTSOS M, FALOUTSOS P, FALOUTSOS C. On power-law relationships of the Internet topology[J]. ACM Computer Communication Review, 1999,29(4): 251-262.

[2] 張國強, 張國清, 范晶. 中國大陸AS級拓撲的測量與分析[J]. 通信學報, 2007,28(10):92-101.

[3] ALDERSON D, DOYLE J, GOVINDAN R, et al. Toward an optimization-driven framework for designing and generating realistic Internet topologies[J]. ACM Computer Communication Review, 2003, 33(1):41-46.

[4] GAO L. On inferring autonomous system relationships in the Internet[J]. IEEE/ACM Transactions on Networking, 2001,9(6):733-745.

[5] KRIOUKOV D, CLAFFV K, FALL K, et al. On compact routing for the Internet[J]. ACM Computer Communication Review, 2007,37(3):41-52.

[6] KUSHMAN N, KANDULA S, KATABI D. Can you hear me now?! It must be BGP[J]. ACM Computer Communications Review, 2007,37(2): 77-84.

[7] 胡湘江, 朱培棟, 龔正虎. SE-BGP:一種BGP安全機制[J]. 軟件學報, 2008,19(1):167-176.

收稿日期:2009-07-30

朱培棟,國防科技大學計算機學院教授,從事高性能路由器的研制和路由技術研究,先后主持10余項國家科研課題。SCI/EI收錄論文50余篇,持有國家發(fā)明專利5項。

趙金晶,博士,北京系統(tǒng)工程研究所助理研究員,從事網絡路由和信息安全技術研究。發(fā)表論文20余篇,持有國家發(fā)明專利1項。

鄧文平,國防科技大學計算機學院在讀博士生,研究方向為路由安全及網絡健壯性。