１ 引言
光傳輸技術(shù)飛速發(fā)展和核心路由表快速增長對路由器性能提出了更高的需求，互聯(lián)網(wǎng)快速發(fā)展要求路由器隨著網(wǎng)絡(luò)規(guī)模和流量增長不斷擴展自身性能，雖然通過硬件升級在短期內(nèi)能夠提高路由器的性能，但受硬件性能限制，僅依靠硬件升級無法滿足互聯(lián)網(wǎng)快速發(fā)展的需要，為了克服硬件的性能束縛，一些路由器在數(shù)據(jù)平面采用多機柜分布式互連的集群體系結(jié)構(gòu)提高轉(zhuǎn)發(fā)性能，但目前路由器控制平面只有一個控制單元處理控制任務(wù)，數(shù)據(jù)平面規(guī)模擴展將增加控制平面的負載，容易造成控制單元過載。
目前對路由器的研究大部分集中在數(shù)據(jù)平面，對于逐漸成為路由器性能瓶頸的控制平面缺乏成體系的研究，為了解決現(xiàn)有路由器控制平面基于單一控制單元的集中式控制所面臨的問題，研究人員提出了路由器分布式控制方案。
為了更好地了解路由器集中控制與分布式控制的特點，我們從可靠性、可擴展性和部署代價等方面對它們進行了比較，如表１所示。
路由器控制平面分布式互連和多實例并行可有效地避免單一硬件或軟件失效導致的網(wǎng)絡(luò)振蕩，提高網(wǎng)絡(luò)穩(wěn)定性和路由器容錯能力，分布式控制能夠支持性能和功能的靈活擴展，提高路由器的可擴展性，控制單元之間和控制單元與轉(zhuǎn)發(fā)單元之間分擔負載，可克服單一硬件的性能瓶頸，減少控制單元過載，提高路由器的可靠性，硬件分布式互連和軟件功能分布式、模塊化設(shè)計和實現(xiàn)可實現(xiàn)不中斷服務(wù)升級，提高路由器的可用性，但與集中式控制相比，分布式控制存在內(nèi)部通信開銷大和能耗高、管理和維護復雜等不足。
表１ 路由器集中式控制與分布式控制比較
文獻［５］雖然按照分層模型綜述了可擴展路由器目前的研究進展，但它重點分析和比較了數(shù)據(jù)平面的擴展方案，而對控制平面—這個制約路由器可擴展的瓶頸和關(guān)鍵問題缺少系統(tǒng)和針對性分析。
本文深入剖析了路由器集中控制存在的局限性，總結(jié)出路由器控制平面從集中式向分布式發(fā)展需要解決三個關(guān)鍵問題：（１）分布式控制平面，由多個控制單元分布式互連而成的分布式控制平面可有效克服單一控制單元的性能瓶頸和可擴展性差等不足，為控制平面的性能和功能靈活擴展提供支持；（２）分布式控制平面內(nèi)部通信，物理上分布的控制單元和軟件功能模塊要形成一個整體，需要分布式控制平面內(nèi)部通信協(xié)議實現(xiàn)硬件和軟件的透明通信；（３）分布式路由協(xié)議，為適應(yīng)分布式控制平面體系結(jié)構(gòu)，路由協(xié)議和算法應(yīng)分布式實現(xiàn)，充分利用系統(tǒng)的計算和存儲資源，提高路由器的性能，本文重點圍繞這三個關(guān)鍵問題綜述了這一領(lǐng)域的最新研究進展，并對各種方案進行了分析和比較。
２ 路由器集中控制面臨的主要問題
２.１ 性能瓶頸
目前路由器控制平面只有一個控制單元處理協(xié)議分組，Ｉａｎｎａｃｃｏｎｅ，Ｇ等人通過網(wǎng)絡(luò)測量得出，５０％的網(wǎng)絡(luò)故障可能因路由器控制平面過載丟失“心跳”消息引起，根據(jù)目前互聯(lián)網(wǎng)的發(fā)展速度和硬件技術(shù)發(fā)展速度，基于單一控制單元的集中式控制平面很難滿足互聯(lián)網(wǎng)快速增長的需求。
２.２ 單點失效
現(xiàn)有路由協(xié)議大部分集中在主控制單元上運行，很容易因硬件或軟件局部功能失效或代碼錯誤導致整個協(xié)議失效，例如：鄰居建立與維護功能失效將導致整個協(xié)議失效，雖然現(xiàn)有路由器控制平面采用主、從備份方式，但是主、從備份的失效恢復速度相對較慢，影響了網(wǎng)絡(luò)的可用性，為提高網(wǎng)絡(luò)可用性，目前通過向網(wǎng)絡(luò)中增加路由器和運行虛擬路由器冗余協(xié)議（ＶｉｒｔｕａｌＲｏｕｔｅｒＲｅｄｕｎｄａｎｃｙＰｒｏｔｏｃｏｌ，簡稱ＶＲＲＰ）實現(xiàn)冗余備份，這提高了網(wǎng)絡(luò)的運營成本，增加了網(wǎng)絡(luò)連接的復雜度和網(wǎng)絡(luò)管理的難度。
２.３ 可擴展性差
各路由器廠商都采用私有技術(shù)，分別設(shè)計各自專用的部件、接口和通信協(xié)議，不同生產(chǎn)廠商的路由器部件之間不能互換和通信，因此，在網(wǎng)絡(luò)中，這些路由器只能作為獨立的網(wǎng)絡(luò)設(shè)備互連，而不能通過互連擴展為一臺更高性能和更多功能的路由器，技術(shù)封閉私有和集中控制嚴重影響了路由器的可擴展性。
基于路由器集中控制所面臨的問題，研究人員提出了路由器分布式控制方案，通過分布式互連、并行處理和冗余備份等技術(shù)提高路由器的性能、可靠性和可擴展性。
雖然路由器分布控制是一種發(fā)展趨勢，但是隨著硬件處理能力的不斷提高，集中式還將長期存在，Ｂａｌｌａｎｉ，Ｈｉｔｅｓｈ等人研究表明兩種控制方式相結(jié)合將有效延長現(xiàn)有路由器的生存周期，改進網(wǎng)絡(luò)性能。
３ 分布式控制平面
路由器分布式控制平面主要分為集群路由器（ＣｌｕｓｔｅｒＲｏｕｔｅｒ，簡稱ＣＲ）和轉(zhuǎn)發(fā)與控制分離（ＦｏｒｗａｒｄｉｎｇａｎｄＣｏｎｔｒｏｌＥｌｅｍｅｎｔｓＳｅｐａｒａｔｉｏｎ，簡稱ＦｏｒＣＥＳ）兩種結(jié)構(gòu)。
３.１ ＣＲ
ＣＲ是多個可獨立運行的、具有路由功能的節(jié)點通過某種互連結(jié)構(gòu)（例如：高速以太網(wǎng)）連接成性能、功能可擴展的單映像路由器，集群路由器根據(jù)內(nèi)部節(jié)點的類型可分為軟件集群路由器和集群路由器。
軟件集群路由器由一臺路由器與多臺具有路由處理能力的ＰＣ機相連而成，軟件集群路由器通過向集群中增加路由處理節(jié)點擴展路由器的性能和功能，目前比較典型的軟件集群路由器有ＣＬＡＲＡ、Ｓｕｅｚ和ＶＥＲＡ，軟件集群路由器借助多個路由處理節(jié)點并行，實現(xiàn)分布式控制單元間的負載分擔，提高路由處理性能，多臺ＰＣ機和一臺路由器組成的分布式控制平面可實現(xiàn)功能和性能靈活擴展，部署代價比較低，但軟件集群路由器不支持數(shù)據(jù)平面的擴展，無法提高數(shù)據(jù)平面性能，在軟件集群路由器中，路由器節(jié)點失效會導致整個系統(tǒng)不可用，降低了系統(tǒng)的可靠性。
與軟件集群路由器相比，集群路由器ＨＣＲ的內(nèi)部節(jié)點都是具有路由和轉(zhuǎn)發(fā)功能的路由器，在集群路由器內(nèi)部，節(jié)點之間分擔負載，并行處理不同協(xié)議的分組，分布式控制單元之間功能可相互冗余備份，能夠支持數(shù)據(jù)平面的靈活擴展。
由于集群路由器的最小組成單元是路由器，控制單元與轉(zhuǎn)發(fā)單元之間采用私有協(xié)議和專用接口通信，因此，內(nèi)部節(jié)點的互連需要對路由器進行相應(yīng)的修改，增加了部署代價。
３.２ ＦｏｒＣＥＳ
ＦｏｒＣＥＳ體系結(jié)構(gòu)如圖１所示，ＦｏｒＣＥＳ體系結(jié)構(gòu)允許一臺路由器的控制平面有多個控制單元，它們之間通過內(nèi)部高速網(wǎng)絡(luò)互連，控制單元（ＣＥ）與轉(zhuǎn)發(fā)單元（ＦＥ）可采取預(yù)先配置或動態(tài)聯(lián)合的方式實現(xiàn)路由器相應(yīng)的功能，ＣＥ和ＦＥ間的自由聯(lián)合可靈活擴展路由器的性能和功能，控制單元之間可彼此分擔負載、冗余備份和實現(xiàn)分布式控制，ＦｏｒＣＥＳ體系結(jié)構(gòu)為一臺路由器內(nèi)部多個控制單元分布式互連和規(guī)模擴展提供了一種靈活的機制，ＦＥ／ＣＥ、ＦＥ／ＦＥ、ＣＥ／ＣＥ間的標準接口和ＦＥ／ＣＥ間的ＦｏｒＣＥＳ通信協(xié)議為控制平面的性能和功能靈活擴展提供了支持，通過標準化的機制，ＣＥ和ＦＥ變成相互分離的標準組件，克服了集群路由器控制單元和轉(zhuǎn)發(fā)單元不能分離的不足，可對ＣＥ和ＦＥ數(shù)量靈活擴展，有效克服單個部件性能的束縛，延長路由器生存周期，保護投資，
圖1 ForCES體系結(jié)構(gòu)
ＦｏｒＣＥＳ方案雖然為路由器實現(xiàn)控制單元、數(shù)據(jù)單元的規(guī)模擴展和擴展路由器的功能提供了一種靈活機制，但是，它只提出了分布式控制平面體系結(jié)構(gòu)和ＣＥ與ＦＥ之間的ＦｏｒＣＥＳ通信協(xié)議，沒有對路由軟件進行分布式、模塊化設(shè)計。
ＤＭＲ（ＤｅｃｅｎｔｒａｌｉｚｅｄＭｏｄｕｌａｒＲｏｕｔｅｒ，簡稱ＤＭＲ）是基于ＦｏｒＣＥＳ框架實現(xiàn)的分布式模塊化路由器，在ＤＭＲ中，ＣＥ和ＦＥ是獨立的標準組件，設(shè)計有標準的ＦｏｒＣＥＳ接口，相互通過內(nèi)部高速以太網(wǎng)互連，ＤＭＲ路由器支持控制單元數(shù)量和控制平面功能的靈活擴展，通過內(nèi)部通信協(xié)議Ｆｏｒｚ（ＦｏｒＣＥＳｏｎｚｅｂｒａ，簡稱Ｆｏｒｚ），多個分布式互連的控制單元聚合為一個整體，彼此分擔負載和冗余備份，ＤＭＲ對路由協(xié)議進行了功能分解和模塊化設(shè)計，將路由協(xié)議的鄰居建立與維護功能遷移到轉(zhuǎn)發(fā)單元上實現(xiàn)，利用轉(zhuǎn)發(fā)單元的處理資源分擔控制平面的負載，實現(xiàn)了路由協(xié)議分組的并行處理，提高了路由器對網(wǎng)絡(luò)變化的感知能力和路由協(xié)議的可用性，多個控制單元分布式互連和路由協(xié)議的功能分布可提高路由器的可靠性。
由于ＣＥ與ＦＥ的標準化需要一段較長的時間，在短時期內(nèi)，這種方案還很難體現(xiàn)它的優(yōu)勢，但是，ＤＭＲ實現(xiàn)了基于ＦＥ與ＣＥ分離的多個控制單元間的分布式互連的原型系統(tǒng)，為路由器分布式控制平面的設(shè)計提供了很好的參考和借鑒作用。
４ 分布式控制平面內(nèi)部通信
隨著路由器控制平面由集中式向分布式發(fā)展，為了使物理上分布式互連的控制單元和轉(zhuǎn)發(fā)單元組合成一臺完整的路由器，需要設(shè)計和實現(xiàn)分布式控制平面內(nèi)部通信協(xié)議，目前分布式控制平面內(nèi)部通信方案主要有集群路由器內(nèi)部通信協(xié)議（ＲｏｕｔｅｒＣｌｕｓｔERPｒｏｔｏｃｏｌ，簡稱ＲＣＰ）和Ｆｏｒｚ兩種。
４.１ ＲＣＰ
Ｊ.Ｂ-Ｇｕａｎ等人設(shè)計了集群路由器內(nèi)部通信協(xié)議ＲＣＰ，其內(nèi)部接口和協(xié)議框架模型如圖２所示。
圖2 RCP協(xié)議內(nèi)部接口和協(xié)議框架模型
通過ＲＣＰ協(xié)議，集群路由器內(nèi)部各節(jié)點都可獲得組成該集群路由器的節(jié)點數(shù)量、編號、鄰居節(jié)點的性能和類型、內(nèi)部端口號和外部端口號等信息，集群路由器內(nèi)部各節(jié)點形成對整個集群路由器一致的內(nèi)部拓撲視圖，在轉(zhuǎn)發(fā)平面上，多個路由器節(jié)點通過標準互連卡互連。
集群路由器內(nèi)部互連接口的物理層采用高速光互連技術(shù)（ＶｅｒｙＳｈｏｒｔＲｅａｃｈ，簡稱ＶＳＲ）；鏈路層使用常用的高級數(shù)據(jù)鏈路控制（ＨｉｇｈＬｅｖｅｌＤａｔａＬｉｎｋＣｏｎｔｒｏｌ，簡稱ＨＤＬＣ）幀封裝格式，通過制定多種速率等級備選，滿足了集群路由器內(nèi)部不同速率互連的需要，提高了互連的靈活性，傳輸?shù)臄?shù)據(jù)幀中包含符合ＮＰＳＩ規(guī)范的數(shù)據(jù)信元和流控信元兩種格式，數(shù)據(jù)信元交換數(shù)據(jù)報文，流控信元交換集群路由器內(nèi)部各個交換網(wǎng)絡(luò)的流量控制信息，數(shù)據(jù)信元頭部附加一個包含信元全局目的端口信息的標簽，在它所經(jīng)過的每一個交換網(wǎng)絡(luò)節(jié)點的內(nèi)部互連卡上，互連卡根據(jù)全局端口設(shè)備視圖與本地交換網(wǎng)絡(luò)端口的映射關(guān)系確定本地交換網(wǎng)絡(luò)的目的端口，將信元送往本地交換網(wǎng)絡(luò)進行交換。
在控制平面，多個控制單元通過ＲＣＰ協(xié)議交換拓撲信息，形成統(tǒng)一的集群路由器管理視圖和設(shè)備視圖，相互間協(xié)同路由計算和協(xié)議處理，同步轉(zhuǎn)發(fā)表等功能，由于ＲＣＰ方案只設(shè)計了集群路由器內(nèi)部通信協(xié)議的框架，沒有可參考的協(xié)議的具體工作機制，而且它只適用于集群路由器內(nèi)部節(jié)點間的通信和數(shù)據(jù)交換，具有一定的局限性。
４.２ Ｆｏｒｚ
Ｏ，Ｈａｇｓａｎｄ等人基于開源路由軟件Ｚｅｂｒａ和ＦｏｒＣＥＳ體系結(jié)構(gòu)設(shè)計了路由器分布式控制平面內(nèi)部的通信協(xié)議Ｆｏｒｚ，Ｆｏｒｚ協(xié)議在ＦｏｒＣＥＳ協(xié)議框架的基礎(chǔ)上，對其內(nèi)部通信機制進行了擴展，可實現(xiàn)ＣＥ／ＦＥ，ＣＥ／ＣＥ，ＦＥ／ＦＥ間的通信，其消息格式如圖３所示，Ｆｏｒｚ協(xié)議的通信機制分為：聯(lián)合、配置和數(shù)據(jù)傳輸三個階段。
圖3 Forz協(xié)議消息格式
在聯(lián)合階段，每個ＣＥ或ＦＥ通過ＩＰ可靠組播的方式向同組內(nèi)的其它成員發(fā)送Ｈｅｌｌｏ消息，報告自身的信息，Ｈｅｌｌｏ機制管理成員的加入和離開，通告內(nèi)部控制和數(shù)據(jù)流的組播地址、成員的信息和心跳檢測。
當一個成員剛加入時，它的初始Ｆｏｒｚ數(shù)據(jù)庫為空，首先，它向內(nèi)部控制流的組播地址發(fā)送一個Ｈｅｌｌｏ消息，Ｈｅｌｌｏ消息中包括自身的性能、端口數(shù)量、類型等信息，收到Ｈｅｌｌｏ消息后，組內(nèi)的其它成員將新成員的信息加入到自己的數(shù)據(jù)庫，同時，組內(nèi)現(xiàn)有成員向新加入的成員發(fā)送Ｈｅｌｌｏ消息通告自己的功能、資源和端口地址等信息，收到消息后，新加入的成員向自己本地的Ｆｏｒｚ數(shù)據(jù)庫中添加相應(yīng)成員的信息，當一個成員離開時，它發(fā)送Ｂｙｅ消息，組內(nèi)其它成員收到這個消息后，將它的信息從數(shù)據(jù)庫中刪除，當一個成員失效時，由于缺少心跳消息，其它的成員將其從數(shù)據(jù)庫中刪除。
在配置階段，Ｆｏｒｚ協(xié)議用于創(chuàng)建、刪除和獲取網(wǎng)絡(luò)接口、ＩＰ地址、路由信息和鄰居的信息等，Ｆｏｒｚ協(xié)議通過可靠組播對配置信息進行分發(fā)，建立本地端口與全局端口的映射關(guān)系，形成內(nèi)部一致的路由表。
在數(shù)據(jù)傳輸階段，Ｆｏｒｚ協(xié)議對本地數(shù)據(jù)進行封裝，然后通過內(nèi)部網(wǎng)絡(luò)交換到相應(yīng)的輸出端口，在輸出端口解封裝后發(fā)送到外部網(wǎng)絡(luò)。
Ｆｏｒｚ實現(xiàn)了分布式控制平面內(nèi)部通信的工作機制和協(xié)議消息格式；對分布式控制平面內(nèi)部路由和通信機制的設(shè)計具有很好的參考和借鑒作用。
４.３ 小結(jié)
現(xiàn)有的分布式控制平面方案及其內(nèi)部通信協(xié)議如表２所示。
集中式控制平面路由器內(nèi)部通信采用私有協(xié)議，技術(shù)成熟，部署代價相對較低，但性能和功能相對固定，可擴展性差，集群路由器分布式控制單元間采用ＲＣＰ協(xié)議通信，但它需要對部分路由器進行修改，增加了部署代價，ＦｏｒＣＥＳ和ＤＭＲ內(nèi)部采用標準的接口和協(xié)議進行通信，基于標準化組件容易實現(xiàn)對控制單元的功能定制，支持性能和功能的靈活擴展，但標準化設(shè)計是一個長期的過程，因此部署代價目前相對較高。
表２ 路由器控制平面體系結(jié)構(gòu)與內(nèi)部通信
５ 分布式路由協(xié)議和算法
現(xiàn)有路由協(xié)議的功能大都集中在控制平面，為充分利用分布式控制單元和轉(zhuǎn)發(fā)單元的資源，需要對路由協(xié)進行功能分解和分布式設(shè)計，將不同的功能分布在相應(yīng)的控制單元或轉(zhuǎn)發(fā)單元上實現(xiàn)，設(shè)計分布式路由算法，充分利用多個控制單元的計算資源，提高路由計算性能。
５.１ 分布式路由協(xié)議
５.１.１ ＤＣＰ
Ｍ，Ｄｅｖａｌ等人提出了分布式控制方案（ＤｉｓｔｒｉｂｕｔｅｄＣｏｎｔｒｏｌＰｌａｎｅ，簡稱ＤＣＰ），將路由協(xié)議的功能分為三類：
（１）鏈路相關(guān)功能，主要包括分組轉(zhuǎn)發(fā)和鄰居狀態(tài)維護，這些功能可分布在轉(zhuǎn)發(fā)單元上實現(xiàn)，利用轉(zhuǎn)發(fā)單元的處理資源分擔控制單元的負載，
（２）協(xié)議處理功能，例如：路由計算，協(xié)議狀態(tài)機的維護，這些功能需要在多個控制單元間實現(xiàn)分布，
（３）更新控制信息功能，例如，更新路由表，這些功能很難進行分布式設(shè)計，應(yīng)在控制單元實現(xiàn)，ＤＣＰ方案將ＯＳＰＦ的Ｈｅｌｌｏ機制遷移在轉(zhuǎn)發(fā)單元實現(xiàn)，有效地利用了轉(zhuǎn)發(fā)單元的處理資源處理協(xié)議的信令分組，分擔了控制單元的負載，減少了Ｈｅｌｌｏ分組到控制平面的傳輸時間，縮短了等待控制單元處理的排隊時間，加快了路由器對網(wǎng)絡(luò)故障的感知和響應(yīng)，信令功能分布在轉(zhuǎn)發(fā)單元實現(xiàn)可避免轉(zhuǎn)發(fā)單元規(guī)模擴展而導致的內(nèi)部通信開銷，緩解了數(shù)據(jù)平面擴展對控制平面處理能力的需求，協(xié)議信令功能的分布和并行，提高了協(xié)議的可靠性和容錯性。
ＤＣＰ雖然提出了路由協(xié)議功能分布的原則，但缺乏對路由協(xié)議功能分布和模塊化設(shè)計的細節(jié)。
５.１.２ ＭＣＰＢ
模塊化ＢＧＰ（ＭｏｄｕｌａｒＣｏｎｔｒｏｌＰｌａｎｅｆｏｒＢＧＰ，簡稱ＭＣＰＢ）按照功能將ＢＧＰ協(xié)議劃分為信令模塊（ＢＧＰＳｅｓｓｉｏｎＭａｎａｇｅｒ）和路由處理模塊（ＢＧＰＰｒｏｃｅｓｓｉｎｇ），信令模塊分布在轉(zhuǎn)發(fā)單元，用于維護鄰居關(guān)系、接收鄰居路由通告和處理“心跳”消息、分配路由計算任務(wù)，路由處理模塊分布在控制單元，進行路由計算，通過對ＢＧＰ協(xié)議功能分解和模塊化設(shè)計，ＭＣＰＢ方案可實現(xiàn)對ＢＧＰ協(xié)議分組并行處理，能夠利用轉(zhuǎn)發(fā)單元的處理資源分擔控制單元的負載，ＢＧＰ相應(yīng)的功能模塊分布在不同的控制單元或轉(zhuǎn)發(fā)單元上并行運行提高了可靠性和可擴展性。
５.１.３ ＤＣＰＡ
Ｋ-Ｋ，Ｎｇｕｙｅｎ等人設(shè)計了路由軟件的分布式控制平面體系結(jié)構(gòu)（ＤｉｓｔｒｉｂｕｔｅｄＣｏｎｔｒｏｌＰｌａｎｅＡｒｃｈｉｔｅｃｔｕｒｅ，簡稱ＤＣＰＡ），分別對ＯＳＰＦ／ＩＳＩＳ和ＢＧＰ等路由協(xié)議進行了功能分解和模塊化設(shè)計，例如：將ＯＳＰＦ協(xié)議分解為ＯＣＣ（ＯＳＰＦＣｏｎｔｒｏｌＣｏｍｐｏｎｅｎｔ）模塊和ＯＳＣ（ＯＳＰＦＳｉｇｎａｌｉｎｇＣｏｍｐｏｎｅｎｔ）模塊，ＯＳＣ模塊分布在轉(zhuǎn)發(fā)單元，ＯＣＣ模塊分布在控制單元，每個控制單元上運行的路由協(xié)議模塊在其它控制單元上都相應(yīng)地備份，提高了可靠性，ＤＣＰＡ將ＢＧＰ協(xié)議分解為ＢＧＰ鄰居建立與維護模塊、本地路由管理（Ｌ-ＲＴＭ）模塊和全局路由管理（Ｇ-ＲＴＭ）模塊，鄰居建立與維護模塊分布在轉(zhuǎn)發(fā)單元，Ｌ-ＲＴＭ和ＧＲＴＭ分布在不同的控制單元，每個控制單元的ＢＧＰ鄰居建立與維護模塊接收來自鄰居的路由信息，Ｌ-ＲＴＭ先決策出本地最優(yōu)路由，然后發(fā)送給Ｇ-ＲＴＭ模塊，Ｇ-ＲＴＭ模塊從各個Ｌ-ＲＴＭ發(fā)送的本地最優(yōu)路由中計算出全局最優(yōu)路由，ＢＧＰ路由協(xié)議功能的分布和模塊化設(shè)計提高了控制平面的可擴展性。
ＤＣＰＡ方案為路由協(xié)議的功能分布和模塊化設(shè)計提供了很好的參考，由于ＤＣＰＡ方案只是從功能上考慮了路由協(xié)議的功能分布，沒有考慮路由協(xié)議模塊相互之間的耦合度和通信開銷，因此，在實際的路由協(xié)議功能分布和模塊化設(shè)計中需要考慮這些因素。
５.１.４ ＤＲＴＭ
Ｋ，Ｋｈｏａ等人對路由表管理進行了分布式、模塊化設(shè)計（ＤｉｓｔｒｉｂｕｔｅｄＲＴＭ，簡稱ＤＲＴＭ），ＤＲＴＭ方案將路由表管理分解為線卡路由表管理模塊（ＬＣ-ＲＴＭ）和全局路由表管理模塊（Ｇ-ＲＴＭ），ＬＣ-ＲＴＭ分布在線卡，線卡維護它所在區(qū)域的鏈路狀態(tài)數(shù)據(jù)庫，當多個線卡具有相同的拓撲信息時，這些線卡組成一個集群，在集群中選舉超級節(jié)點負責計算重疊區(qū)域的路由表，Ｇ-ＲＴＭ分布在控制單元，Ｇ-ＲＴＭ模塊接收各ＬＣ-ＲＴＭ模塊發(fā)送的路由信息最終計算出全局路由表。
ＤＲＴＭ方案充分利用數(shù)據(jù)平面的計算和存儲資源來提高路由表的計算效率，但目前路由器的線卡不具備路由計算能力，因此，該方案不適合于常規(guī)路由器，實現(xiàn)代價比較高，另外，它在一臺集中式控制路由器的控制單元與轉(zhuǎn)發(fā)單元之間實現(xiàn)路由表計算的分布式，無法避免控制單元或Ｇ-ＲＴＭ模塊導致的單點失效，降低了可靠性。
５.１.５ 小結(jié)
路由協(xié)議的分布式和模塊化設(shè)計方案如表３所示。
表３ 路由協(xié)議功能分布式設(shè)計
目前路由協(xié)議大都集中在主控制單元，影響了可靠性，不能實現(xiàn)負載分擔和并行處理，ＤＣＰ將路由協(xié)議信令功能遷移到轉(zhuǎn)發(fā)單元，與集中式控制相比，在一定程度上提高了系統(tǒng)的可靠性和并行處理能力，ＭＣＰＢ和ＤＣＰＡ對現(xiàn)有協(xié)議功能進行分布式模塊化設(shè)計，提高了并行性、可靠性和可擴展性，ＤＲＴＭ基于高端路由器的線卡具備計算能力設(shè)計了路由表分布式管理方案，對線卡的性能要求較高，由于它在同一路由器的控制單元與線卡之間實現(xiàn)分布式路由表管理，影響了系統(tǒng)的可靠性，但是，利用轉(zhuǎn)發(fā)單元計算路由較好地分擔了控制單元的負載，提高了路由器的并行處理性能。
５.２ 分布式路由算法
為了提高路由計算性能，應(yīng)設(shè)計分布式路由算法，充分利用分布式控制平面多個控制單元的資源，提高路由計算性能，目前的分布式路由算法主要分為：（１）分布式并行ＯＳＰＦ路由算法，包括ＰＤＳＰＴ、ＢＰＡ和ＰＲＴＣ；（２）分布式并行ＢＧＰ路由算法，主要有ＦＤＨＰ和ＩＴＢＧＰ。
５.２.１ 分布式并行ＯＳＰＦ路由算法
（１）ＰＤＳＰＴ
Ｚｈｕ-Ｙ.Ｂ等人根據(jù)最短路徑樹（ＳｈｏｒｔｅｓｔＰａｔｈＴｒｅｅ，簡稱ＳＰＴ）增量更新的特點，利用原有的ＳＰＴ樹設(shè)計了并行動態(tài)ＳＰＴ算法（ＰａｒａｌｌｅｌＤｙｎａｍｉｃＳＰＴ，簡稱ＰＤＳＰＴ），每次網(wǎng)絡(luò)拓撲發(fā)生變化，將原ＳＰＴ樹上受鏈路變化影響的節(jié)點加入隊列，并分配給相應(yīng)的控制單元，每個控制單元每次從本地選出距離增量最小的節(jié)點，控制單元之間利用廣播方式選出全局距離增量最小的節(jié)點，每次選出全局距離增量最小的節(jié)點后，根據(jù)原ＳＰＴ樹上的父子關(guān)系，相應(yīng)更新全局最小節(jié)點原ＳＰＴ樹上子孫的距離，并將它們從受影響節(jié)點的隊列中刪除，然后將新受影響的節(jié)點加入隊列，反復迭代，直到受影響節(jié)點的隊列為空。
ＰＤＳＰＴ算法利用分布式控制平面多個處理器資源分擔計算負載，實現(xiàn)了ＯＳＰＦ路由表的并行計算，由于利用了ＳＰＴ增量更新，減少了整個算法的迭代次數(shù)，當網(wǎng)絡(luò)拓撲規(guī)模比較大，并且鏈路故障對原ＳＰＴ樹上的節(jié)點影響比較多時，這個算法的并行性能較好，當網(wǎng)絡(luò)拓撲中每個受影響節(jié)點的入度和出度比較接近時，控制單元的負載比較均衡，由于每次迭代控制單元間需要相互通信，因此，路由器內(nèi)部通信開銷比較大，受網(wǎng)絡(luò)拓撲結(jié)構(gòu)和迭代算法的影響，系統(tǒng)的負載均衡性差，影響了并行性能。
（２）ＰＳＰＴ
Ｚｈａｎｇ-Ｘ.Ｐ等人針對ＯＳＰＦ協(xié)議設(shè)計了并行ＳＰＴ算法（ＰａｒａｌｌｅｌＳＰＴＡｌｇｏｒｉｔｈｍ，簡稱ＰＳＰＴ），ＰＳＰＴ根據(jù)路由器中控制單元的數(shù)量ｐ利用圖分割理論將網(wǎng)絡(luò)拓撲分割成幾個區(qū)域，每個控制單元負責相應(yīng)區(qū)域的路由計算，首先，每個控制單元并行計算出各自區(qū)域內(nèi)所有邊界程度上提高了系統(tǒng)的可靠性和并行處理能力，ＭＣＰＢ和ＤＣＰＡ對現(xiàn)有協(xié)議功能進行分布式模塊化設(shè)計，提高了并行性、可靠性和可擴展性，ＤＲＴＭ基于高端路由器的線卡具備計算能力設(shè)計了路由表分布式管理方案，對線卡的性能要求較高，由于它在同一路由器的控制單元與線卡之間實現(xiàn)分布式路由表管理，影響了系統(tǒng)的可靠性，但是，利用轉(zhuǎn)發(fā)單元計算路由較好地分擔了控制單元的負載，提高了路由器的并行處理性能。
５.２ 分布式路由算法
為了提高路由計算性能，應(yīng)設(shè)計分布式路由算法，充分利用分布式控制平面多個控制單元的資源，提高路由計算性能，目前的分布式路由算法主要分為：（１）分布式并行ＯＳＰＦ路由算法，包括ＰＤＳＰＴ、ＢＰＡ和ＰＲＴＣ；（２）分布式并行ＢＧＰ路由算法，主要有ＦＤＨＰ和ＩＴＢＧＰ。
５.２.１ 分布式并行ＯＳＰＦ路由算法
（１）ＰＤＳＰＴ
Ｚｈｕ-Ｙ，Ｂ等人根據(jù)最短路徑樹（ＳｈｏｒｔｅｓｔＰａｔｈＴｒｅｅ，簡稱ＳＰＴ）增量更新的特點，利用原有的ＳＰＴ樹設(shè)計了并行動態(tài)ＳＰＴ算法（ＰａｒａｌｌｅｌＤｙｎａｍｉｃＳＰＴ，簡稱ＰＤＳＰＴ），每次網(wǎng)絡(luò)拓撲發(fā)生變化，將原ＳＰＴ樹上受鏈路變化影響的節(jié)點加入隊列，并分配給相應(yīng)的控制單元，每個控制單元每次從本地選出距離增量最小的節(jié)點，控制單元之間利用廣播方式選出全局距離增量最小的節(jié)點，每次選出全局距離增量最小的節(jié)點后，根據(jù)原ＳＰＴ樹上的父子關(guān)系，相應(yīng)更新全局最小節(jié)點原ＳＰＴ樹上子孫的距離，并將它們從受影響節(jié)點的隊列中刪除，然后將新受影響的節(jié)點加入隊列，反復迭代，直到受影響節(jié)點的隊列為空。
ＰＤＳＰＴ算法利用分布式控制平面多個處理器資源分擔計算負載，實現(xiàn)了ＯＳＰＦ路由表的并行計算，由于利用了ＳＰＴ增量更新，減少了整個算法的迭代次數(shù)，當網(wǎng)絡(luò)拓撲規(guī)模比較大，并且鏈路故障對原ＳＰＴ樹上的節(jié)點影響比較多時，這個算法的并行性能較好，當網(wǎng)絡(luò)拓撲中每個受影響節(jié)點的入度和出度比較接近時，控制單元的負載比較均衡，由于每次迭代控制單元間需要相互通信，因此，路由器內(nèi)部通信開銷比較大，受網(wǎng)絡(luò)拓撲結(jié)構(gòu)和迭代算法的影響，系統(tǒng)的負載均衡性差，影響了并行性能。
（２）ＰＳＰＴ
Ｚｈａｎｇ-Ｘ，Ｐ等人針對ＯＳＰＦ協(xié)議設(shè)計了并行ＳＰＴ算法（ＰａｒａｌｌｅｌＳＰＴＡｌｇｏｒｉｔｈｍ，簡稱ＰＳＰＴ），ＰＳＰＴ根據(jù)路由器中控制單元的數(shù)量ｐ利用圖分割理論將網(wǎng)絡(luò)拓撲分割成幾個區(qū)域，每個控制單元負責相應(yīng)區(qū)域的路由計算，首先，每個控制單元并行計算出各自區(qū)域內(nèi)所有邊界節(jié)點到這些區(qū)域每個節(jié)點的最短路徑，對于包含根節(jié)點的區(qū)域，計算根節(jié)點到這些區(qū)域中每個節(jié)點的最短路徑，然后，將每個區(qū)域的邊界節(jié)點和根節(jié)點組成新的拓撲圖，再計算根節(jié)點到這個區(qū)域邊界節(jié)點的最短路徑；最后并行地將根節(jié)點到每個區(qū)域邊界節(jié)點的路徑和區(qū)域邊界節(jié)點到區(qū)域內(nèi)每個節(jié)點的最短路徑合并，生成最終的ＳＰＴ樹。
每次拓撲變化，ＰＳＰＴ算法需要重新分割網(wǎng)絡(luò)拓撲，算法復雜度高，因此，ＰＳＰＴ算法不適用于網(wǎng)絡(luò)拓撲頻繁變化時的ＳＰＴ計算，基于圖分割能夠較好地實現(xiàn)負載均衡，并行性能較好，ＰＳＰＴ算法在網(wǎng)絡(luò)拓撲規(guī)模比較大時能夠獲得較好的性能。
（３）ＰＲＴＣ
Ｘｉａｏ-Ｘ，Ｐ等人根據(jù)集群路由器的分布式控制平面提出了并行ＯＳＰＦ路由算法（ＰａｒａｌｌｅｌＲｏｕｔｉｎｇＴａｂｌｅＣｏｍｐｕｔａｔｉｏｎ，簡稱ＰＲＴＣ），利用集群路由器多個路由節(jié)點將ＯＳＰＦ區(qū)域按照收集的拓撲信息進行分割，每個節(jié)點負責維護自己所在區(qū)域的拓撲，各自計算這個區(qū)域的路由表，當多個路由節(jié)點的路由區(qū)域重疊時，選舉指派節(jié)點計算重疊區(qū)域的路由表，每個區(qū)域的指派節(jié)點向所有節(jié)點通告自己的路由表，每個節(jié)點選擇性地將接收的路由合并生成最終的路由表，當自己所在區(qū)域的路由變化，每個指派路由節(jié)點向其它路由節(jié)點廣播變化的路由。
ＰＲＴＣ算法可實現(xiàn)ＯＳＰＦ路由表的并行計算，但它對網(wǎng)絡(luò)拓撲依賴比較大，由于每個節(jié)點在網(wǎng)絡(luò)中所處的位置不同，它們各自的計算負載不同，不能很好地實現(xiàn)節(jié)點間的負載均衡，并行性較低，每個節(jié)點不維護全局的鏈路狀態(tài)數(shù)據(jù)庫，一定程度上降低了可靠性。
５.２.２ 分布式并行ＢＧＰ路由算法
（１）ＦＤＨＰ
Ｚｈａｎｇ-Ｘ，Ｚｈ等人設(shè)計了ＢＧＰ并行路由算法（ＦｕｌｌＤｉｓｔｒｉｂｕｔｅｄＨｉｇｈＰａｒａｌｌｅｌｉｚｅｄＢＧＰ，簡稱ＦＤＨＰ），集群路由器的每個路由節(jié)點分別充當與它相連的ＢＧＰ鄰居的代理，負責與其相連的ＢＧＰ鄰居交換路由信息，每個節(jié)點根據(jù)本地路由信息計算本地最優(yōu)路由，每個節(jié)點將本地最優(yōu)路由廣播給集群中其它節(jié)點，從而保證每個路由節(jié)點都維護一致的全局路由表，當集群中某個節(jié)點失效時，將它代理的ＢＧＰ鄰居會話和路由計算任務(wù)重新分配給其它節(jié)點。
ＦＤＨＰ方案有效地利用了集群內(nèi)部各個路由節(jié)點的計算資源和存儲資源，每個路由節(jié)點只計算和存儲一部分ＢＧＰ候選路由，多個路由節(jié)點分擔負載提高了路由計算性能，但節(jié)點間以廣播的方式同步路由信息增加了內(nèi)部的通信開銷。
（２）ＩＴＢＧＰ
Ｗｕ-Ｋｕｎ等人設(shè)計了“迭代樹”ＢＧＰ并行路由算法（ＩｔｅｒａｔｉｖｅＴｒｅｅＢＧＰ，ＩＴＢＧＰ），ＩＴＢＧＰ方案根據(jù)ＢＧＰ鄰居的數(shù)量ｎ和每個控制單元的ＢＧＰ鄰居數(shù)量，采用廣度優(yōu)先算法構(gòu)建一棵ｋ階迭代樹，每當路由發(fā)生變化，樹中相應(yīng)的葉子節(jié)點首先計算出本地最優(yōu)路由，然后發(fā)送給自己的父節(jié)點，這樣沿著葉子向根的方向反復迭代，最后在根節(jié)點計算出全局最優(yōu)路由。
當負載分布比較均衡時，ＩＴＢＧＰ算法的性能最優(yōu)，當負載分布不均衡時，例如，到某一目的地的路由只存儲在一個內(nèi)部節(jié)點時，基于樹形結(jié)構(gòu)需要從葉子到根的方向多次迭代計算，降低了路由計算效率。
５.２.３ 小結(jié)
ＰＤＳＰＴ將計算ＳＰＴ樹步驟中計算鄰居節(jié)點的距離和搜索全局距離最小節(jié)點實現(xiàn)了并行處理，但算法復雜度較高，不能實現(xiàn)較好的負載均衡，ＰＳＰＴ將拓撲進行分割，能夠較好實現(xiàn)路由計算的并行和負載均衡，但算法復雜度較高，ＰＲＴＣ對網(wǎng)絡(luò)拓撲進行分割，算法性能受網(wǎng)絡(luò)拓撲結(jié)構(gòu)影響比較大，負載均衡性能差，但算法復雜度低。
ＦＤＨＰ按鄰居會話將ＢＧＰ路由計算任務(wù)進行劃分，能夠較好地實現(xiàn)ＢＧＰ路由計算并行，算法復雜度低，采用廣播的方式進行路由信息同步，減少了路由計算的迭代次數(shù)，多個節(jié)點并行計算，提高了系統(tǒng)的并行性能，但是，在互聯(lián)網(wǎng)中，由于多個鄰居會通告同一故障，基于廣播的方式進行路由信息同步將導致內(nèi)部大量的通信開銷，ＩＴＢＧＰ雖然按鄰居會話劃分負載并行計算ＢＧＰ路由，但需要經(jīng)過多次迭代才能計算出全局最優(yōu)路由，隨著樹高度增加，內(nèi)部通信開銷和延時不斷增大，影響了系統(tǒng)的并行性能。
６ 結(jié)論和研究展望
路由器控制平面的分布式實現(xiàn)是一種發(fā)展趨勢，也是路由器體系結(jié)構(gòu)及軟件設(shè)計必須解決的一個關(guān)鍵性技術(shù)問題，通過以上分析和比較，本文認為實現(xiàn)分布式控制平面應(yīng)該從以下幾個方面入手：
（１）分布式控制平面體系結(jié)構(gòu)是實現(xiàn)路由器分布式控制的基礎(chǔ)，它為標準化接口和內(nèi)部通信設(shè)計提供依據(jù)，為控制平面性能和功能的靈活擴展提供支持。
（２）標準化接口和通信機制是實現(xiàn)與互連技術(shù)無關(guān)的關(guān)鍵技術(shù)，是控制單元與轉(zhuǎn)發(fā)單元數(shù)量和功能靈活擴展的基本保證。
（３）軟件分布式、模塊化設(shè)計是提高路由器性能，支持路由器功能和性能動態(tài)擴展的主要途徑，合理設(shè)計將有利于提高路由器的可用性和可擴展性。
雖然目前提出了一些路由器分布式控制方案，但是路由器實現(xiàn)分布式控制仍然面臨一些關(guān)鍵問題亟待解決，需要進一步深入研究：（１）任務(wù)分配，如何將原來并行運行在一個控制單元上的多個路由協(xié)議任務(wù)合理地分布到多個分布式的控制單元，這需要研究分布式控制平面的任務(wù)分配方案，即要考慮每個任務(wù)對ＣＰＵ的占用時間，又要考慮不同路由協(xié)議模塊之間的通信開銷，實現(xiàn)負載均衡，使內(nèi)部通信開銷最小，從而優(yōu)化整個系統(tǒng)的性能，（２）分布式路由算法，應(yīng)設(shè)計高效的分布式路由算法，充分利用各個節(jié)點的計算和存儲資源，提高系統(tǒng)的性能。
轉(zhuǎn)載請注明出處：拓步ERP資訊網(wǎng)http://www.oesoe.com/
本文標題：路由器分布式控制研究綜述
本文網(wǎng)址：http://www.oesoe.com/html/support/1112159113.html
相關(guān)文章
