1 引言
光傳輸技術(shù)飛速發(fā)展和核心路由表快速增長(zhǎng)對(duì)路由器性能提出了更高的需求,互聯(lián)網(wǎng)快速發(fā)展要求路由器隨著網(wǎng)絡(luò)規(guī)模和流量增長(zhǎng)不斷擴(kuò)展自身性能,雖然通過(guò)硬件升級(jí)在短期內(nèi)能夠提高路由器的性能,但受硬件性能限制,僅依靠硬件升級(jí)無(wú)法滿足互聯(lián)網(wǎng)快速發(fā)展的需要,為了克服硬件的性能束縛,一些路由器在數(shù)據(jù)平面采用多機(jī)柜分布式互連的集群體系結(jié)構(gòu)提高轉(zhuǎn)發(fā)性能,但目前路由器控制平面只有一個(gè)控制單元處理控制任務(wù),數(shù)據(jù)平面規(guī)模擴(kuò)展將增加控制平面的負(fù)載,容易造成控制單元過(guò)載。
目前對(duì)路由器的研究大部分集中在數(shù)據(jù)平面,對(duì)于逐漸成為路由器性能瓶頸的控制平面缺乏成體系的研究,為了解決現(xiàn)有路由器控制平面基于單一控制單元的集中式控制所面臨的問(wèn)題,研究人員提出了路由器分布式控制方案。
為了更好地了解路由器集中控制與分布式控制的特點(diǎn),我們從可靠性、可擴(kuò)展性和部署代價(jià)等方面對(duì)它們進(jìn)行了比較,如表1所示。
路由器控制平面分布式互連和多實(shí)例并行可有效地避免單一硬件或軟件失效導(dǎo)致的網(wǎng)絡(luò)振蕩,提高網(wǎng)絡(luò)穩(wěn)定性和路由器容錯(cuò)能力,分布式控制能夠支持性能和功能的靈活擴(kuò)展,提高路由器的可擴(kuò)展性,控制單元之間和控制單元與轉(zhuǎn)發(fā)單元之間分擔(dān)負(fù)載,可克服單一硬件的性能瓶頸,減少控制單元過(guò)載,提高路由器的可靠性,硬件分布式互連和軟件功能分布式、模塊化設(shè)計(jì)和實(shí)現(xiàn)可實(shí)現(xiàn)不中斷服務(wù)升級(jí),提高路由器的可用性,但與集中式控制相比,分布式控制存在內(nèi)部通信開(kāi)銷大和能耗高、管理和維護(hù)復(fù)雜等不足。
表1 路由器集中式控制與分布式控制比較
文獻(xiàn)[5]雖然按照分層模型綜述了可擴(kuò)展路由器目前的研究進(jìn)展,但它重點(diǎn)分析和比較了數(shù)據(jù)平面的擴(kuò)展方案,而對(duì)控制平面—這個(gè)制約路由器可擴(kuò)展的瓶頸和關(guān)鍵問(wèn)題缺少系統(tǒng)和針對(duì)性分析。
本文深入剖析了路由器集中控制存在的局限性,總結(jié)出路由器控制平面從集中式向分布式發(fā)展需要解決三個(gè)關(guān)鍵問(wèn)題:(1)分布式控制平面,由多個(gè)控制單元分布式互連而成的分布式控制平面可有效克服單一控制單元的性能瓶頸和可擴(kuò)展性差等不足,為控制平面的性能和功能靈活擴(kuò)展提供支持;(2)分布式控制平面內(nèi)部通信,物理上分布的控制單元和軟件功能模塊要形成一個(gè)整體,需要分布式控制平面內(nèi)部通信協(xié)議實(shí)現(xiàn)硬件和軟件的透明通信;(3)分布式路由協(xié)議,為適應(yīng)分布式控制平面體系結(jié)構(gòu),路由協(xié)議和算法應(yīng)分布式實(shí)現(xiàn),充分利用系統(tǒng)的計(jì)算和存儲(chǔ)資源,提高路由器的性能,本文重點(diǎn)圍繞這三個(gè)關(guān)鍵問(wèn)題綜述了這一領(lǐng)域的最新研究進(jìn)展,并對(duì)各種方案進(jìn)行了分析和比較。
2 路由器集中控制面臨的主要問(wèn)題
2.1 性能瓶頸
目前路由器控制平面只有一個(gè)控制單元處理協(xié)議分組,Iannaccone,G等人通過(guò)網(wǎng)絡(luò)測(cè)量得出,50%的網(wǎng)絡(luò)故障可能因路由器控制平面過(guò)載丟失“心跳”消息引起,根據(jù)目前互聯(lián)網(wǎng)的發(fā)展速度和硬件技術(shù)發(fā)展速度,基于單一控制單元的集中式控制平面很難滿足互聯(lián)網(wǎng)快速增長(zhǎng)的需求。
2.2 單點(diǎn)失效
現(xiàn)有路由協(xié)議大部分集中在主控制單元上運(yùn)行,很容易因硬件或軟件局部功能失效或代碼錯(cuò)誤導(dǎo)致整個(gè)協(xié)議失效,例如:鄰居建立與維護(hù)功能失效將導(dǎo)致整個(gè)協(xié)議失效,雖然現(xiàn)有路由器控制平面采用主、從備份方式,但是主、從備份的失效恢復(fù)速度相對(duì)較慢,影響了網(wǎng)絡(luò)的可用性,為提高網(wǎng)絡(luò)可用性,目前通過(guò)向網(wǎng)絡(luò)中增加路由器和運(yùn)行虛擬路由器冗余協(xié)議(VirtualRouterRedundancyProtocol,簡(jiǎn)稱VRRP)實(shí)現(xiàn)冗余備份,這提高了網(wǎng)絡(luò)的運(yùn)營(yíng)成本,增加了網(wǎng)絡(luò)連接的復(fù)雜度和網(wǎng)絡(luò)管理的難度。
2.3 可擴(kuò)展性差
各路由器廠商都采用私有技術(shù),分別設(shè)計(jì)各自專用的部件、接口和通信協(xié)議,不同生產(chǎn)廠商的路由器部件之間不能互換和通信,因此,在網(wǎng)絡(luò)中,這些路由器只能作為獨(dú)立的網(wǎng)絡(luò)設(shè)備互連,而不能通過(guò)互連擴(kuò)展為一臺(tái)更高性能和更多功能的路由器,技術(shù)封閉私有和集中控制嚴(yán)重影響了路由器的可擴(kuò)展性。
基于路由器集中控制所面臨的問(wèn)題,研究人員提出了路由器分布式控制方案,通過(guò)分布式互連、并行處理和冗余備份等技術(shù)提高路由器的性能、可靠性和可擴(kuò)展性。
雖然路由器分布控制是一種發(fā)展趨勢(shì),但是隨著硬件處理能力的不斷提高,集中式還將長(zhǎng)期存在,Ballani,Hitesh等人研究表明兩種控制方式相結(jié)合將有效延長(zhǎng)現(xiàn)有路由器的生存周期,改進(jìn)網(wǎng)絡(luò)性能。
3 分布式控制平面
路由器分布式控制平面主要分為集群路由器(ClusterRouter,簡(jiǎn)稱CR)和轉(zhuǎn)發(fā)與控制分離(ForwardingandControlElementsSeparation,簡(jiǎn)稱ForCES)兩種結(jié)構(gòu)。
3.1 CR
CR是多個(gè)可獨(dú)立運(yùn)行的、具有路由功能的節(jié)點(diǎn)通過(guò)某種互連結(jié)構(gòu)(例如:高速以太網(wǎng))連接成性能、功能可擴(kuò)展的單映像路由器,集群路由器根據(jù)內(nèi)部節(jié)點(diǎn)的類型可分為軟件集群路由器和集群路由器。
軟件集群路由器由一臺(tái)路由器與多臺(tái)具有路由處理能力的PC機(jī)相連而成,軟件集群路由器通過(guò)向集群中增加路由處理節(jié)點(diǎn)擴(kuò)展路由器的性能和功能,目前比較典型的軟件集群路由器有CLARA、Suez和VERA,軟件集群路由器借助多個(gè)路由處理節(jié)點(diǎn)并行,實(shí)現(xiàn)分布式控制單元間的負(fù)載分擔(dān),提高路由處理性能,多臺(tái)PC機(jī)和一臺(tái)路由器組成的分布式控制平面可實(shí)現(xiàn)功能和性能靈活擴(kuò)展,部署代價(jià)比較低,但軟件集群路由器不支持?jǐn)?shù)據(jù)平面的擴(kuò)展,無(wú)法提高數(shù)據(jù)平面性能,在軟件集群路由器中,路由器節(jié)點(diǎn)失效會(huì)導(dǎo)致整個(gè)系統(tǒng)不可用,降低了系統(tǒng)的可靠性。
與軟件集群路由器相比,集群路由器HCR的內(nèi)部節(jié)點(diǎn)都是具有路由和轉(zhuǎn)發(fā)功能的路由器,在集群路由器內(nèi)部,節(jié)點(diǎn)之間分擔(dān)負(fù)載,并行處理不同協(xié)議的分組,分布式控制單元之間功能可相互冗余備份,能夠支持?jǐn)?shù)據(jù)平面的靈活擴(kuò)展。
由于集群路由器的最小組成單元是路由器,控制單元與轉(zhuǎn)發(fā)單元之間采用私有協(xié)議和專用接口通信,因此,內(nèi)部節(jié)點(diǎn)的互連需要對(duì)路由器進(jìn)行相應(yīng)的修改,增加了部署代價(jià)。
3.2 ForCES
ForCES體系結(jié)構(gòu)如圖1所示,ForCES體系結(jié)構(gòu)允許一臺(tái)路由器的控制平面有多個(gè)控制單元,它們之間通過(guò)內(nèi)部高速網(wǎng)絡(luò)互連,控制單元(CE)與轉(zhuǎn)發(fā)單元(FE)可采取預(yù)先配置或動(dòng)態(tài)聯(lián)合的方式實(shí)現(xiàn)路由器相應(yīng)的功能,CE和FE間的自由聯(lián)合可靈活擴(kuò)展路由器的性能和功能,控制單元之間可彼此分擔(dān)負(fù)載、冗余備份和實(shí)現(xiàn)分布式控制,ForCES體系結(jié)構(gòu)為一臺(tái)路由器內(nèi)部多個(gè)控制單元分布式互連和規(guī)模擴(kuò)展提供了一種靈活的機(jī)制,FE/CE、FE/FE、CE/CE間的標(biāo)準(zhǔn)接口和FE/CE間的ForCES通信協(xié)議為控制平面的性能和功能靈活擴(kuò)展提供了支持,通過(guò)標(biāo)準(zhǔn)化的機(jī)制,CE和FE變成相互分離的標(biāo)準(zhǔn)組件,克服了集群路由器控制單元和轉(zhuǎn)發(fā)單元不能分離的不足,可對(duì)CE和FE數(shù)量靈活擴(kuò)展,有效克服單個(gè)部件性能的束縛,延長(zhǎng)路由器生存周期,保護(hù)投資,
圖1 ForCES體系結(jié)構(gòu)
ForCES方案雖然為路由器實(shí)現(xiàn)控制單元、數(shù)據(jù)單元的規(guī)模擴(kuò)展和擴(kuò)展路由器的功能提供了一種靈活機(jī)制,但是,它只提出了分布式控制平面體系結(jié)構(gòu)和CE與FE之間的ForCES通信協(xié)議,沒(méi)有對(duì)路由軟件進(jìn)行分布式、模塊化設(shè)計(jì)。
DMR(DecentralizedModularRouter,簡(jiǎn)稱DMR)是基于ForCES框架實(shí)現(xiàn)的分布式模塊化路由器,在DMR中,CE和FE是獨(dú)立的標(biāo)準(zhǔn)組件,設(shè)計(jì)有標(biāo)準(zhǔn)的ForCES接口,相互通過(guò)內(nèi)部高速以太網(wǎng)互連,DMR路由器支持控制單元數(shù)量和控制平面功能的靈活擴(kuò)展,通過(guò)內(nèi)部通信協(xié)議Forz(ForCESonzebra,簡(jiǎn)稱Forz),多個(gè)分布式互連的控制單元聚合為一個(gè)整體,彼此分擔(dān)負(fù)載和冗余備份,DMR對(duì)路由協(xié)議進(jìn)行了功能分解和模塊化設(shè)計(jì),將路由協(xié)議的鄰居建立與維護(hù)功能遷移到轉(zhuǎn)發(fā)單元上實(shí)現(xiàn),利用轉(zhuǎn)發(fā)單元的處理資源分擔(dān)控制平面的負(fù)載,實(shí)現(xiàn)了路由協(xié)議分組的并行處理,提高了路由器對(duì)網(wǎng)絡(luò)變化的感知能力和路由協(xié)議的可用性,多個(gè)控制單元分布式互連和路由協(xié)議的功能分布可提高路由器的可靠性。
由于CE與FE的標(biāo)準(zhǔn)化需要一段較長(zhǎng)的時(shí)間,在短時(shí)期內(nèi),這種方案還很難體現(xiàn)它的優(yōu)勢(shì),但是,DMR實(shí)現(xiàn)了基于FE與CE分離的多個(gè)控制單元間的分布式互連的原型系統(tǒng),為路由器分布式控制平面的設(shè)計(jì)提供了很好的參考和借鑒作用。
4 分布式控制平面內(nèi)部通信
隨著路由器控制平面由集中式向分布式發(fā)展,為了使物理上分布式互連的控制單元和轉(zhuǎn)發(fā)單元組合成一臺(tái)完整的路由器,需要設(shè)計(jì)和實(shí)現(xiàn)分布式控制平面內(nèi)部通信協(xié)議,目前分布式控制平面內(nèi)部通信方案主要有集群路由器內(nèi)部通信協(xié)議(RouterClustERProtocol,簡(jiǎn)稱RCP)和Forz兩種。
4.1 RCP
J.B-Guan等人設(shè)計(jì)了集群路由器內(nèi)部通信協(xié)議RCP,其內(nèi)部接口和協(xié)議框架模型如圖2所示。
圖2 RCP協(xié)議內(nèi)部接口和協(xié)議框架模型
通過(guò)RCP協(xié)議,集群路由器內(nèi)部各節(jié)點(diǎn)都可獲得組成該集群路由器的節(jié)點(diǎn)數(shù)量、編號(hào)、鄰居節(jié)點(diǎn)的性能和類型、內(nèi)部端口號(hào)和外部端口號(hào)等信息,集群路由器內(nèi)部各節(jié)點(diǎn)形成對(duì)整個(gè)集群路由器一致的內(nèi)部拓?fù)湟晥D,在轉(zhuǎn)發(fā)平面上,多個(gè)路由器節(jié)點(diǎn)通過(guò)標(biāo)準(zhǔn)互連卡互連。
集群路由器內(nèi)部互連接口的物理層采用高速光互連技術(shù)(VeryShortReach,簡(jiǎn)稱VSR);鏈路層使用常用的高級(jí)數(shù)據(jù)鏈路控制(HighLevelDataLinkControl,簡(jiǎn)稱HDLC)幀封裝格式,通過(guò)制定多種速率等級(jí)備選,滿足了集群路由器內(nèi)部不同速率互連的需要,提高了互連的靈活性,傳輸?shù)臄?shù)據(jù)幀中包含符合NPSI規(guī)范的數(shù)據(jù)信元和流控信元兩種格式,數(shù)據(jù)信元交換數(shù)據(jù)報(bào)文,流控信元交換集群路由器內(nèi)部各個(gè)交換網(wǎng)絡(luò)的流量控制信息,數(shù)據(jù)信元頭部附加一個(gè)包含信元全局目的端口信息的標(biāo)簽,在它所經(jīng)過(guò)的每一個(gè)交換網(wǎng)絡(luò)節(jié)點(diǎn)的內(nèi)部互連卡上,互連卡根據(jù)全局端口設(shè)備視圖與本地交換網(wǎng)絡(luò)端口的映射關(guān)系確定本地交換網(wǎng)絡(luò)的目的端口,將信元送往本地交換網(wǎng)絡(luò)進(jìn)行交換。
在控制平面,多個(gè)控制單元通過(guò)RCP協(xié)議交換拓?fù)湫畔ⅲ纬山y(tǒng)一的集群路由器管理視圖和設(shè)備視圖,相互間協(xié)同路由計(jì)算和協(xié)議處理,同步轉(zhuǎn)發(fā)表等功能,由于RCP方案只設(shè)計(jì)了集群路由器內(nèi)部通信協(xié)議的框架,沒(méi)有可參考的協(xié)議的具體工作機(jī)制,而且它只適用于集群路由器內(nèi)部節(jié)點(diǎn)間的通信和數(shù)據(jù)交換,具有一定的局限性。
4.2 Forz
O,Hagsand等人基于開(kāi)源路由軟件Zebra和ForCES體系結(jié)構(gòu)設(shè)計(jì)了路由器分布式控制平面內(nèi)部的通信協(xié)議Forz,Forz協(xié)議在ForCES協(xié)議框架的基礎(chǔ)上,對(duì)其內(nèi)部通信機(jī)制進(jìn)行了擴(kuò)展,可實(shí)現(xiàn)CE/FE,CE/CE,FE/FE間的通信,其消息格式如圖3所示,Forz協(xié)議的通信機(jī)制分為:聯(lián)合、配置和數(shù)據(jù)傳輸三個(gè)階段。
圖3 Forz協(xié)議消息格式
在聯(lián)合階段,每個(gè)CE或FE通過(guò)IP可靠組播的方式向同組內(nèi)的其它成員發(fā)送Hello消息,報(bào)告自身的信息,Hello機(jī)制管理成員的加入和離開(kāi),通告內(nèi)部控制和數(shù)據(jù)流的組播地址、成員的信息和心跳檢測(cè)。
當(dāng)一個(gè)成員剛加入時(shí),它的初始Forz數(shù)據(jù)庫(kù)為空,首先,它向內(nèi)部控制流的組播地址發(fā)送一個(gè)Hello消息,Hello消息中包括自身的性能、端口數(shù)量、類型等信息,收到Hello消息后,組內(nèi)的其它成員將新成員的信息加入到自己的數(shù)據(jù)庫(kù),同時(shí),組內(nèi)現(xiàn)有成員向新加入的成員發(fā)送Hello消息通告自己的功能、資源和端口地址等信息,收到消息后,新加入的成員向自己本地的Forz數(shù)據(jù)庫(kù)中添加相應(yīng)成員的信息,當(dāng)一個(gè)成員離開(kāi)時(shí),它發(fā)送Bye消息,組內(nèi)其它成員收到這個(gè)消息后,將它的信息從數(shù)據(jù)庫(kù)中刪除,當(dāng)一個(gè)成員失效時(shí),由于缺少心跳消息,其它的成員將其從數(shù)據(jù)庫(kù)中刪除。
在配置階段,Forz協(xié)議用于創(chuàng)建、刪除和獲取網(wǎng)絡(luò)接口、IP地址、路由信息和鄰居的信息等,Forz協(xié)議通過(guò)可靠組播對(duì)配置信息進(jìn)行分發(fā),建立本地端口與全局端口的映射關(guān)系,形成內(nèi)部一致的路由表。
在數(shù)據(jù)傳輸階段,Forz協(xié)議對(duì)本地?cái)?shù)據(jù)進(jìn)行封裝,然后通過(guò)內(nèi)部網(wǎng)絡(luò)交換到相應(yīng)的輸出端口,在輸出端口解封裝后發(fā)送到外部網(wǎng)絡(luò)。
Forz實(shí)現(xiàn)了分布式控制平面內(nèi)部通信的工作機(jī)制和協(xié)議消息格式;對(duì)分布式控制平面內(nèi)部路由和通信機(jī)制的設(shè)計(jì)具有很好的參考和借鑒作用。
4.3 小結(jié)
現(xiàn)有的分布式控制平面方案及其內(nèi)部通信協(xié)議如表2所示。
集中式控制平面路由器內(nèi)部通信采用私有協(xié)議,技術(shù)成熟,部署代價(jià)相對(duì)較低,但性能和功能相對(duì)固定,可擴(kuò)展性差,集群路由器分布式控制單元間采用RCP協(xié)議通信,但它需要對(duì)部分路由器進(jìn)行修改,增加了部署代價(jià),ForCES和DMR內(nèi)部采用標(biāo)準(zhǔn)的接口和協(xié)議進(jìn)行通信,基于標(biāo)準(zhǔn)化組件容易實(shí)現(xiàn)對(duì)控制單元的功能定制,支持性能和功能的靈活擴(kuò)展,但標(biāo)準(zhǔn)化設(shè)計(jì)是一個(gè)長(zhǎng)期的過(guò)程,因此部署代價(jià)目前相對(duì)較高。
表2 路由器控制平面體系結(jié)構(gòu)與內(nèi)部通信
5 分布式路由協(xié)議和算法
現(xiàn)有路由協(xié)議的功能大都集中在控制平面,為充分利用分布式控制單元和轉(zhuǎn)發(fā)單元的資源,需要對(duì)路由協(xié)進(jìn)行功能分解和分布式設(shè)計(jì),將不同的功能分布在相應(yīng)的控制單元或轉(zhuǎn)發(fā)單元上實(shí)現(xiàn),設(shè)計(jì)分布式路由算法,充分利用多個(gè)控制單元的計(jì)算資源,提高路由計(jì)算性能。
5.1 分布式路由協(xié)議
5.1.1 DCP
M,Deval等人提出了分布式控制方案(DistributedControlPlane,簡(jiǎn)稱DCP),將路由協(xié)議的功能分為三類:
(1)鏈路相關(guān)功能,主要包括分組轉(zhuǎn)發(fā)和鄰居狀態(tài)維護(hù),這些功能可分布在轉(zhuǎn)發(fā)單元上實(shí)現(xiàn),利用轉(zhuǎn)發(fā)單元的處理資源分擔(dān)控制單元的負(fù)載,
(2)協(xié)議處理功能,例如:路由計(jì)算,協(xié)議狀態(tài)機(jī)的維護(hù),這些功能需要在多個(gè)控制單元間實(shí)現(xiàn)分布,
(3)更新控制信息功能,例如,更新路由表,這些功能很難進(jìn)行分布式設(shè)計(jì),應(yīng)在控制單元實(shí)現(xiàn),DCP方案將OSPF的Hello機(jī)制遷移在轉(zhuǎn)發(fā)單元實(shí)現(xiàn),有效地利用了轉(zhuǎn)發(fā)單元的處理資源處理協(xié)議的信令分組,分擔(dān)了控制單元的負(fù)載,減少了Hello分組到控制平面的傳輸時(shí)間,縮短了等待控制單元處理的排隊(duì)時(shí)間,加快了路由器對(duì)網(wǎng)絡(luò)故障的感知和響應(yīng),信令功能分布在轉(zhuǎn)發(fā)單元實(shí)現(xiàn)可避免轉(zhuǎn)發(fā)單元規(guī)模擴(kuò)展而導(dǎo)致的內(nèi)部通信開(kāi)銷,緩解了數(shù)據(jù)平面擴(kuò)展對(duì)控制平面處理能力的需求,協(xié)議信令功能的分布和并行,提高了協(xié)議的可靠性和容錯(cuò)性。
DCP雖然提出了路由協(xié)議功能分布的原則,但缺乏對(duì)路由協(xié)議功能分布和模塊化設(shè)計(jì)的細(xì)節(jié)。
5.1.2 MCPB
模塊化BGP(ModularControlPlaneforBGP,簡(jiǎn)稱MCPB)按照功能將BGP協(xié)議劃分為信令模塊(BGPSessionManager)和路由處理模塊(BGPProcessing),信令模塊分布在轉(zhuǎn)發(fā)單元,用于維護(hù)鄰居關(guān)系、接收鄰居路由通告和處理“心跳”消息、分配路由計(jì)算任務(wù),路由處理模塊分布在控制單元,進(jìn)行路由計(jì)算,通過(guò)對(duì)BGP協(xié)議功能分解和模塊化設(shè)計(jì),MCPB方案可實(shí)現(xiàn)對(duì)BGP協(xié)議分組并行處理,能夠利用轉(zhuǎn)發(fā)單元的處理資源分擔(dān)控制單元的負(fù)載,BGP相應(yīng)的功能模塊分布在不同的控制單元或轉(zhuǎn)發(fā)單元上并行運(yùn)行提高了可靠性和可擴(kuò)展性。
5.1.3 DCPA
K-K,Nguyen等人設(shè)計(jì)了路由軟件的分布式控制平面體系結(jié)構(gòu)(DistributedControlPlaneArchitecture,簡(jiǎn)稱DCPA),分別對(duì)OSPF/ISIS和BGP等路由協(xié)議進(jìn)行了功能分解和模塊化設(shè)計(jì),例如:將OSPF協(xié)議分解為OCC(OSPFControlComponent)模塊和OSC(OSPFSignalingComponent)模塊,OSC模塊分布在轉(zhuǎn)發(fā)單元,OCC模塊分布在控制單元,每個(gè)控制單元上運(yùn)行的路由協(xié)議模塊在其它控制單元上都相應(yīng)地備份,提高了可靠性,DCPA將BGP協(xié)議分解為BGP鄰居建立與維護(hù)模塊、本地路由管理(L-RTM)模塊和全局路由管理(G-RTM)模塊,鄰居建立與維護(hù)模塊分布在轉(zhuǎn)發(fā)單元,L-RTM和GRTM分布在不同的控制單元,每個(gè)控制單元的BGP鄰居建立與維護(hù)模塊接收來(lái)自鄰居的路由信息,L-RTM先決策出本地最優(yōu)路由,然后發(fā)送給G-RTM模塊,G-RTM模塊從各個(gè)L-RTM發(fā)送的本地最優(yōu)路由中計(jì)算出全局最優(yōu)路由,BGP路由協(xié)議功能的分布和模塊化設(shè)計(jì)提高了控制平面的可擴(kuò)展性。
DCPA方案為路由協(xié)議的功能分布和模塊化設(shè)計(jì)提供了很好的參考,由于DCPA方案只是從功能上考慮了路由協(xié)議的功能分布,沒(méi)有考慮路由協(xié)議模塊相互之間的耦合度和通信開(kāi)銷,因此,在實(shí)際的路由協(xié)議功能分布和模塊化設(shè)計(jì)中需要考慮這些因素。
5.1.4 DRTM
K,Khoa等人對(duì)路由表管理進(jìn)行了分布式、模塊化設(shè)計(jì)(DistributedRTM,簡(jiǎn)稱DRTM),DRTM方案將路由表管理分解為線卡路由表管理模塊(LC-RTM)和全局路由表管理模塊(G-RTM),LC-RTM分布在線卡,線卡維護(hù)它所在區(qū)域的鏈路狀態(tài)數(shù)據(jù)庫(kù),當(dāng)多個(gè)線卡具有相同的拓?fù)湫畔r(shí),這些線卡組成一個(gè)集群,在集群中選舉超級(jí)節(jié)點(diǎn)負(fù)責(zé)計(jì)算重疊區(qū)域的路由表,G-RTM分布在控制單元,G-RTM模塊接收各LC-RTM模塊發(fā)送的路由信息最終計(jì)算出全局路由表。
DRTM方案充分利用數(shù)據(jù)平面的計(jì)算和存儲(chǔ)資源來(lái)提高路由表的計(jì)算效率,但目前路由器的線卡不具備路由計(jì)算能力,因此,該方案不適合于常規(guī)路由器,實(shí)現(xiàn)代價(jià)比較高,另外,它在一臺(tái)集中式控制路由器的控制單元與轉(zhuǎn)發(fā)單元之間實(shí)現(xiàn)路由表計(jì)算的分布式,無(wú)法避免控制單元或G-RTM模塊導(dǎo)致的單點(diǎn)失效,降低了可靠性。
5.1.5 小結(jié)
路由協(xié)議的分布式和模塊化設(shè)計(jì)方案如表3所示。
表3 路由協(xié)議功能分布式設(shè)計(jì)
目前路由協(xié)議大都集中在主控制單元,影響了可靠性,不能實(shí)現(xiàn)負(fù)載分擔(dān)和并行處理,DCP將路由協(xié)議信令功能遷移到轉(zhuǎn)發(fā)單元,與集中式控制相比,在一定程度上提高了系統(tǒng)的可靠性和并行處理能力,MCPB和DCPA對(duì)現(xiàn)有協(xié)議功能進(jìn)行分布式模塊化設(shè)計(jì),提高了并行性、可靠性和可擴(kuò)展性,DRTM基于高端路由器的線卡具備計(jì)算能力設(shè)計(jì)了路由表分布式管理方案,對(duì)線卡的性能要求較高,由于它在同一路由器的控制單元與線卡之間實(shí)現(xiàn)分布式路由表管理,影響了系統(tǒng)的可靠性,但是,利用轉(zhuǎn)發(fā)單元計(jì)算路由較好地分擔(dān)了控制單元的負(fù)載,提高了路由器的并行處理性能。
5.2 分布式路由算法
為了提高路由計(jì)算性能,應(yīng)設(shè)計(jì)分布式路由算法,充分利用分布式控制平面多個(gè)控制單元的資源,提高路由計(jì)算性能,目前的分布式路由算法主要分為:(1)分布式并行OSPF路由算法,包括PDSPT、BPA和PRTC;(2)分布式并行BGP路由算法,主要有FDHP和ITBGP。
5.2.1 分布式并行OSPF路由算法
(1)PDSPT
Zhu-Y.B等人根據(jù)最短路徑樹(shù)(ShortestPathTree,簡(jiǎn)稱SPT)增量更新的特點(diǎn),利用原有的SPT樹(shù)設(shè)計(jì)了并行動(dòng)態(tài)SPT算法(ParallelDynamicSPT,簡(jiǎn)稱PDSPT),每次網(wǎng)絡(luò)拓?fù)浒l(fā)生變化,將原SPT樹(shù)上受鏈路變化影響的節(jié)點(diǎn)加入隊(duì)列,并分配給相應(yīng)的控制單元,每個(gè)控制單元每次從本地選出距離增量最小的節(jié)點(diǎn),控制單元之間利用廣播方式選出全局距離增量最小的節(jié)點(diǎn),每次選出全局距離增量最小的節(jié)點(diǎn)后,根據(jù)原SPT樹(shù)上的父子關(guān)系,相應(yīng)更新全局最小節(jié)點(diǎn)原SPT樹(shù)上子孫的距離,并將它們從受影響節(jié)點(diǎn)的隊(duì)列中刪除,然后將新受影響的節(jié)點(diǎn)加入隊(duì)列,反復(fù)迭代,直到受影響節(jié)點(diǎn)的隊(duì)列為空。
PDSPT算法利用分布式控制平面多個(gè)處理器資源分擔(dān)計(jì)算負(fù)載,實(shí)現(xiàn)了OSPF路由表的并行計(jì)算,由于利用了SPT增量更新,減少了整個(gè)算法的迭代次數(shù),當(dāng)網(wǎng)絡(luò)拓?fù)湟?guī)模比較大,并且鏈路故障對(duì)原SPT樹(shù)上的節(jié)點(diǎn)影響比較多時(shí),這個(gè)算法的并行性能較好,當(dāng)網(wǎng)絡(luò)拓?fù)渲忻總(gè)受影響節(jié)點(diǎn)的入度和出度比較接近時(shí),控制單元的負(fù)載比較均衡,由于每次迭代控制單元間需要相互通信,因此,路由器內(nèi)部通信開(kāi)銷比較大,受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和迭代算法的影響,系統(tǒng)的負(fù)載均衡性差,影響了并行性能。
(2)PSPT
Zhang-X.P等人針對(duì)OSPF協(xié)議設(shè)計(jì)了并行SPT算法(ParallelSPTAlgorithm,簡(jiǎn)稱PSPT),PSPT根據(jù)路由器中控制單元的數(shù)量p利用圖分割理論將網(wǎng)絡(luò)拓?fù)浞指畛蓭讉(gè)區(qū)域,每個(gè)控制單元負(fù)責(zé)相應(yīng)區(qū)域的路由計(jì)算,首先,每個(gè)控制單元并行計(jì)算出各自區(qū)域內(nèi)所有邊界程度上提高了系統(tǒng)的可靠性和并行處理能力,MCPB和DCPA對(duì)現(xiàn)有協(xié)議功能進(jìn)行分布式模塊化設(shè)計(jì),提高了并行性、可靠性和可擴(kuò)展性,DRTM基于高端路由器的線卡具備計(jì)算能力設(shè)計(jì)了路由表分布式管理方案,對(duì)線卡的性能要求較高,由于它在同一路由器的控制單元與線卡之間實(shí)現(xiàn)分布式路由表管理,影響了系統(tǒng)的可靠性,但是,利用轉(zhuǎn)發(fā)單元計(jì)算路由較好地分擔(dān)了控制單元的負(fù)載,提高了路由器的并行處理性能。
5.2 分布式路由算法
為了提高路由計(jì)算性能,應(yīng)設(shè)計(jì)分布式路由算法,充分利用分布式控制平面多個(gè)控制單元的資源,提高路由計(jì)算性能,目前的分布式路由算法主要分為:(1)分布式并行OSPF路由算法,包括PDSPT、BPA和PRTC;(2)分布式并行BGP路由算法,主要有FDHP和ITBGP。
5.2.1 分布式并行OSPF路由算法
(1)PDSPT
Zhu-Y,B等人根據(jù)最短路徑樹(shù)(ShortestPathTree,簡(jiǎn)稱SPT)增量更新的特點(diǎn),利用原有的SPT樹(shù)設(shè)計(jì)了并行動(dòng)態(tài)SPT算法(ParallelDynamicSPT,簡(jiǎn)稱PDSPT),每次網(wǎng)絡(luò)拓?fù)浒l(fā)生變化,將原SPT樹(shù)上受鏈路變化影響的節(jié)點(diǎn)加入隊(duì)列,并分配給相應(yīng)的控制單元,每個(gè)控制單元每次從本地選出距離增量最小的節(jié)點(diǎn),控制單元之間利用廣播方式選出全局距離增量最小的節(jié)點(diǎn),每次選出全局距離增量最小的節(jié)點(diǎn)后,根據(jù)原SPT樹(shù)上的父子關(guān)系,相應(yīng)更新全局最小節(jié)點(diǎn)原SPT樹(shù)上子孫的距離,并將它們從受影響節(jié)點(diǎn)的隊(duì)列中刪除,然后將新受影響的節(jié)點(diǎn)加入隊(duì)列,反復(fù)迭代,直到受影響節(jié)點(diǎn)的隊(duì)列為空。
PDSPT算法利用分布式控制平面多個(gè)處理器資源分擔(dān)計(jì)算負(fù)載,實(shí)現(xiàn)了OSPF路由表的并行計(jì)算,由于利用了SPT增量更新,減少了整個(gè)算法的迭代次數(shù),當(dāng)網(wǎng)絡(luò)拓?fù)湟?guī)模比較大,并且鏈路故障對(duì)原SPT樹(shù)上的節(jié)點(diǎn)影響比較多時(shí),這個(gè)算法的并行性能較好,當(dāng)網(wǎng)絡(luò)拓?fù)渲忻總(gè)受影響節(jié)點(diǎn)的入度和出度比較接近時(shí),控制單元的負(fù)載比較均衡,由于每次迭代控制單元間需要相互通信,因此,路由器內(nèi)部通信開(kāi)銷比較大,受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和迭代算法的影響,系統(tǒng)的負(fù)載均衡性差,影響了并行性能。
(2)PSPT
Zhang-X,P等人針對(duì)OSPF協(xié)議設(shè)計(jì)了并行SPT算法(ParallelSPTAlgorithm,簡(jiǎn)稱PSPT),PSPT根據(jù)路由器中控制單元的數(shù)量p利用圖分割理論將網(wǎng)絡(luò)拓?fù)浞指畛蓭讉(gè)區(qū)域,每個(gè)控制單元負(fù)責(zé)相應(yīng)區(qū)域的路由計(jì)算,首先,每個(gè)控制單元并行計(jì)算出各自區(qū)域內(nèi)所有邊界節(jié)點(diǎn)到這些區(qū)域每個(gè)節(jié)點(diǎn)的最短路徑,對(duì)于包含根節(jié)點(diǎn)的區(qū)域,計(jì)算根節(jié)點(diǎn)到這些區(qū)域中每個(gè)節(jié)點(diǎn)的最短路徑,然后,將每個(gè)區(qū)域的邊界節(jié)點(diǎn)和根節(jié)點(diǎn)組成新的拓?fù)鋱D,再計(jì)算根節(jié)點(diǎn)到這個(gè)區(qū)域邊界節(jié)點(diǎn)的最短路徑;最后并行地將根節(jié)點(diǎn)到每個(gè)區(qū)域邊界節(jié)點(diǎn)的路徑和區(qū)域邊界節(jié)點(diǎn)到區(qū)域內(nèi)每個(gè)節(jié)點(diǎn)的最短路徑合并,生成最終的SPT樹(shù)。
每次拓?fù)渥兓,PSPT算法需要重新分割網(wǎng)絡(luò)拓?fù)洌惴◤?fù)雜度高,因此,PSPT算法不適用于網(wǎng)絡(luò)拓?fù)漕l繁變化時(shí)的SPT計(jì)算,基于圖分割能夠較好地實(shí)現(xiàn)負(fù)載均衡,并行性能較好,PSPT算法在網(wǎng)絡(luò)拓?fù)湟?guī)模比較大時(shí)能夠獲得較好的性能。
(3)PRTC
Xiao-X,P等人根據(jù)集群路由器的分布式控制平面提出了并行OSPF路由算法(ParallelRoutingTableComputation,簡(jiǎn)稱PRTC),利用集群路由器多個(gè)路由節(jié)點(diǎn)將OSPF區(qū)域按照收集的拓?fù)湫畔⑦M(jìn)行分割,每個(gè)節(jié)點(diǎn)負(fù)責(zé)維護(hù)自己所在區(qū)域的拓?fù),各自?jì)算這個(gè)區(qū)域的路由表,當(dāng)多個(gè)路由節(jié)點(diǎn)的路由區(qū)域重疊時(shí),選舉指派節(jié)點(diǎn)計(jì)算重疊區(qū)域的路由表,每個(gè)區(qū)域的指派節(jié)點(diǎn)向所有節(jié)點(diǎn)通告自己的路由表,每個(gè)節(jié)點(diǎn)選擇性地將接收的路由合并生成最終的路由表,當(dāng)自己所在區(qū)域的路由變化,每個(gè)指派路由節(jié)點(diǎn)向其它路由節(jié)點(diǎn)廣播變化的路由。
PRTC算法可實(shí)現(xiàn)OSPF路由表的并行計(jì)算,但它對(duì)網(wǎng)絡(luò)拓?fù)湟蕾嚤容^大,由于每個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置不同,它們各自的計(jì)算負(fù)載不同,不能很好地實(shí)現(xiàn)節(jié)點(diǎn)間的負(fù)載均衡,并行性較低,每個(gè)節(jié)點(diǎn)不維護(hù)全局的鏈路狀態(tài)數(shù)據(jù)庫(kù),一定程度上降低了可靠性。
5.2.2 分布式并行BGP路由算法
(1)FDHP
Zhang-X,Zh等人設(shè)計(jì)了BGP并行路由算法(FullDistributedHighParallelizedBGP,簡(jiǎn)稱FDHP),集群路由器的每個(gè)路由節(jié)點(diǎn)分別充當(dāng)與它相連的BGP鄰居的代理,負(fù)責(zé)與其相連的BGP鄰居交換路由信息,每個(gè)節(jié)點(diǎn)根據(jù)本地路由信息計(jì)算本地最優(yōu)路由,每個(gè)節(jié)點(diǎn)將本地最優(yōu)路由廣播給集群中其它節(jié)點(diǎn),從而保證每個(gè)路由節(jié)點(diǎn)都維護(hù)一致的全局路由表,當(dāng)集群中某個(gè)節(jié)點(diǎn)失效時(shí),將它代理的BGP鄰居會(huì)話和路由計(jì)算任務(wù)重新分配給其它節(jié)點(diǎn)。
FDHP方案有效地利用了集群內(nèi)部各個(gè)路由節(jié)點(diǎn)的計(jì)算資源和存儲(chǔ)資源,每個(gè)路由節(jié)點(diǎn)只計(jì)算和存儲(chǔ)一部分BGP候選路由,多個(gè)路由節(jié)點(diǎn)分擔(dān)負(fù)載提高了路由計(jì)算性能,但節(jié)點(diǎn)間以廣播的方式同步路由信息增加了內(nèi)部的通信開(kāi)銷。
(2)ITBGP
Wu-Kun等人設(shè)計(jì)了“迭代樹(shù)”BGP并行路由算法(IterativeTreeBGP,ITBGP),ITBGP方案根據(jù)BGP鄰居的數(shù)量n和每個(gè)控制單元的BGP鄰居數(shù)量,采用廣度優(yōu)先算法構(gòu)建一棵k階迭代樹(shù),每當(dāng)路由發(fā)生變化,樹(shù)中相應(yīng)的葉子節(jié)點(diǎn)首先計(jì)算出本地最優(yōu)路由,然后發(fā)送給自己的父節(jié)點(diǎn),這樣沿著葉子向根的方向反復(fù)迭代,最后在根節(jié)點(diǎn)計(jì)算出全局最優(yōu)路由。
當(dāng)負(fù)載分布比較均衡時(shí),ITBGP算法的性能最優(yōu),當(dāng)負(fù)載分布不均衡時(shí),例如,到某一目的地的路由只存儲(chǔ)在一個(gè)內(nèi)部節(jié)點(diǎn)時(shí),基于樹(shù)形結(jié)構(gòu)需要從葉子到根的方向多次迭代計(jì)算,降低了路由計(jì)算效率。
5.2.3 小結(jié)
PDSPT將計(jì)算SPT樹(shù)步驟中計(jì)算鄰居節(jié)點(diǎn)的距離和搜索全局距離最小節(jié)點(diǎn)實(shí)現(xiàn)了并行處理,但算法復(fù)雜度較高,不能實(shí)現(xiàn)較好的負(fù)載均衡,PSPT將拓?fù)溥M(jìn)行分割,能夠較好實(shí)現(xiàn)路由計(jì)算的并行和負(fù)載均衡,但算法復(fù)雜度較高,PRTC對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行分割,算法性能受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)影響比較大,負(fù)載均衡性能差,但算法復(fù)雜度低。
FDHP按鄰居會(huì)話將BGP路由計(jì)算任務(wù)進(jìn)行劃分,能夠較好地實(shí)現(xiàn)BGP路由計(jì)算并行,算法復(fù)雜度低,采用廣播的方式進(jìn)行路由信息同步,減少了路由計(jì)算的迭代次數(shù),多個(gè)節(jié)點(diǎn)并行計(jì)算,提高了系統(tǒng)的并行性能,但是,在互聯(lián)網(wǎng)中,由于多個(gè)鄰居會(huì)通告同一故障,基于廣播的方式進(jìn)行路由信息同步將導(dǎo)致內(nèi)部大量的通信開(kāi)銷,ITBGP雖然按鄰居會(huì)話劃分負(fù)載并行計(jì)算BGP路由,但需要經(jīng)過(guò)多次迭代才能計(jì)算出全局最優(yōu)路由,隨著樹(shù)高度增加,內(nèi)部通信開(kāi)銷和延時(shí)不斷增大,影響了系統(tǒng)的并行性能。
6 結(jié)論和研究展望
路由器控制平面的分布式實(shí)現(xiàn)是一種發(fā)展趨勢(shì),也是路由器體系結(jié)構(gòu)及軟件設(shè)計(jì)必須解決的一個(gè)關(guān)鍵性技術(shù)問(wèn)題,通過(guò)以上分析和比較,本文認(rèn)為實(shí)現(xiàn)分布式控制平面應(yīng)該從以下幾個(gè)方面入手:
(1)分布式控制平面體系結(jié)構(gòu)是實(shí)現(xiàn)路由器分布式控制的基礎(chǔ),它為標(biāo)準(zhǔn)化接口和內(nèi)部通信設(shè)計(jì)提供依據(jù),為控制平面性能和功能的靈活擴(kuò)展提供支持。
(2)標(biāo)準(zhǔn)化接口和通信機(jī)制是實(shí)現(xiàn)與互連技術(shù)無(wú)關(guān)的關(guān)鍵技術(shù),是控制單元與轉(zhuǎn)發(fā)單元數(shù)量和功能靈活擴(kuò)展的基本保證。
(3)軟件分布式、模塊化設(shè)計(jì)是提高路由器性能,支持路由器功能和性能動(dòng)態(tài)擴(kuò)展的主要途徑,合理設(shè)計(jì)將有利于提高路由器的可用性和可擴(kuò)展性。
雖然目前提出了一些路由器分布式控制方案,但是路由器實(shí)現(xiàn)分布式控制仍然面臨一些關(guān)鍵問(wèn)題亟待解決,需要進(jìn)一步深入研究:(1)任務(wù)分配,如何將原來(lái)并行運(yùn)行在一個(gè)控制單元上的多個(gè)路由協(xié)議任務(wù)合理地分布到多個(gè)分布式的控制單元,這需要研究分布式控制平面的任務(wù)分配方案,即要考慮每個(gè)任務(wù)對(duì)CPU的占用時(shí)間,又要考慮不同路由協(xié)議模塊之間的通信開(kāi)銷,實(shí)現(xiàn)負(fù)載均衡,使內(nèi)部通信開(kāi)銷最小,從而優(yōu)化整個(gè)系統(tǒng)的性能,(2)分布式路由算法,應(yīng)設(shè)計(jì)高效的分布式路由算法,充分利用各個(gè)節(jié)點(diǎn)的計(jì)算和存儲(chǔ)資源,提高系統(tǒng)的性能。
轉(zhuǎn)載請(qǐng)注明出處:拓步ERP資訊網(wǎng)http://www.ezxoed.cn/
本文標(biāo)題:路由器分布式控制研究綜述
本文網(wǎng)址:http://www.ezxoed.cn/html/support/1112159113.html