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