可重構集群路由器并行路由分發模型

陳文龍，徐明偉，徐恪

(1.首都師范大學 信息工程學院，北京 100048；2.清華大學 計算機科學與技術系，北京 100084)

1 引言

作為互聯網最核心的網絡設備，路由器經歷了單處理器集中式總線結構、多處理器分布式共享總線結構、多處理器分布式交換結構3個發展階段，可重構、可擴展體系結構是路由器發展的下一個階段[1]。所謂可重構路由器，就是由若干個子路由器級連，重構而成的一個統一的路由器系統。它在功能、性能、接口規模等方面，具有極大的可重構性。它的主要優點包括:保護前期運營投資、提高系統性能、增強設備功能模塊的可靠性、簡化網絡拓撲等。當今主要的路由器廠商已開發出自己的可重構路由器產品，包括:Cisco公司的 CRS-1[2]、JUNIPER公司的路由矩陣(routing matrix)[3]、AVICI公司 TSR[4]等。

分布式路由器體系中，一般通過一對多點的單播分發模式實現系統的路由分發。該模式存在分發周期長、負載不均衡等問題。路由器中大量路由分發，常與設備啟動、接口UP/DOWN、路由協議啟動等事件同時發生。此時，一般都伴有高負荷的路由協議計算、路由決策以及路由模塊或其他輔助模塊的大量協議報文收發。路由分發和上述事件同時搶占處理器資源及板間通信帶寬資源，會導致路由器系統性能瞬時降低。當路由器線卡數量較少及路由容量較小時，問題顯得并不明顯。然而，面對新的網絡環境:路由器結構可重構、互聯網路由表急劇增加[5,6]等，傳統的路由表分發模式面臨極大的挑戰。

首先，隨著路由器體系結構向可重構方向發展，若干子路由器級連。一個路由器系統包含的板卡大量增加，路由表分發時間將明顯延長，發送者的負載會急劇增大。其次，隨著互聯網規模的不斷擴大，以及Multi-Homing的實施，核心路由器的路由表容量不斷增大。與此同時，互聯網上對延遲和丟失敏感的新型應用（如VoIP，流媒體，網絡游戲，視頻會議）正在大量部署，路由分發慢會影響用戶的體驗。而且，路由分發慢還會導致大量分組被錯誤轉發，造成線卡處理和鏈路帶寬等網絡資源的浪費。這要求路由器在面對更多路由的情況下，更快地將核心路由表同步到各板卡。

從分布式體系結構開始，路由器設計者就開始研究系統的路由同步問題。路由表同步是指分布式路由器中，如何使所有板卡盡快與系統當前的核心路由表(KRT，kernel routing table)保持一致，從而保證報文轉發和路由查詢的正確性。關于路由器的路由同步方式，相關的研究和實現可以參考國防科技大學一種集群路由器轉發表同步框架及關鍵算法[7]和JUNIPER公司的路由矩陣(routing matrix)[3]等。業界普遍采用主動廣播更新，全冗余備份存儲的路由同步機制。一般由主控卡集中計算出整個可重構路由器的核心路由表，進而通過主動廣播更新方式同步所有板卡的路由表，每塊板卡都存儲核心路由表的完全鏡像。

本文的貢獻是，面向可重構路由器體系及互聯網新環境帶來的路由同步問題，設計了樹型并行路由分發模型，給出了具體實施方法。理論分析和基于NS2的仿真實驗，驗證了模型能大大減少路由分發時間，并使負載更為均衡。

本文第2節給出了可重構路由器典型路由結構模型及傳統同步模式下的分發性能，設計了樹型路由并行分發（TPRD, tree-based parallel route distribution）模型，推導出k叉樹分發中每一發送周期達到路由同步的板卡數；第3節介紹了TPRD模型相關算法及實施步驟，并從同步時間及負載均衡出發分析了不同板卡數對應的最佳k值；第4節給出了性能分析及基于NS2的實驗；第5節是結束語。

2 并行路由分發

2.1 可重構路由器體系結構模型

可重構路由器是由若干個子路由器級連而成，級連后會形成2個層次的板間通信功能模塊[8]。一方面是數據層快速交換模塊，用于線卡間外部轉發分組的快速交換，完成整個路由系統的報文轉發；另一方面是控制層通信模塊，用于本地收發的協議報文及控制消息的板間傳遞。每個子路由器等同于現在分布式路由器，其內部通信結構是一個高速以太網交換模塊實現控制層通信。可重構體系中，所有子路由器的交換模塊將級連在一起，控制層通信結構是一個多級高速以太網交換模塊。邏輯上，可認為可重構路由器中任意2塊板卡之間通過一個以太網交換模塊直接進行控制層通信。

圖1給出了本文可重構路由器結構模型。把首先計算出核心路由表的主控卡稱為超級路由主控（SRM, super route mater），由SRM發起對整個可重構系統的路由同步工作。本文有如下定義:

m表示可重構路由器中的子路由器數；

Pi表示第i個子路由器的板卡數；

Cone表示發送一條路由消息的代價，主要包括處理器及帶寬消耗等；

q表示SRM某個時間段內產生的核心路由的數量；

Tone為可重構路由器任意兩板間收發一條路由項消息所需時間，也叫傳遞周期。

圖1 本文的可重構路由器結構模型

無論采取何種方案，路由同步完成后每塊板卡都會接收所有核心路由，而板卡接收一條路由消息的代價總是一樣的，所以忽略分析接收代價，只分析發送代價。另外，本文設定可重構路由器路由表同步模型的優劣評價包括2個方面:1）從SRM將路由分發到系統中所有板卡所需要的時間應盡量短；2）在路由同步的過程中，系統中各板卡為此工作所付出的代價盡可能均衡。

2.2 分析

傳統分布式路由同步模式是簡單的一對多串行路由分發(SRD，serial route distributing)策略，SRM 依次向每個接收者單播發送路由消息。除去SRM，共有-1個路由消息接收者。所以，發送路由消息所需代價 Ctotal以及系統路由分發時間Ttotal分別為它們都隨路由消息數和板卡總數呈線性增長。可重構路由器中板卡數大量增加，SRM發送路由消息需要的處理器負載和帶寬都非常大，瞬間極大地影響板卡的處理性能。同時，可重構系統中的其他板卡只負責路由消息接收工作，發送代價為 0，出現負載極度不均的情況，造成資源浪費。另一方面，系統中路由同步時間也較長，容易造成網絡設備路由表和轉發表不一致及大量分組丟失。

由于路由同步是一對多的分發過程，因此先要權衡組播方式和單播方式的優劣。本文認為單播方式更為合理，主要基于以下考慮:1）路由分發必需是一個可靠傳遞過程，要有重傳和確認機制；2）可重構路由器中，支持多種協議族分組尋徑方式；板卡可配置成只支持某種或某幾種協議族尋徑，所以不是每塊板卡都需要所有協議族的路由（本文把所有協議族的尋徑策略都統稱為路由）；組播將導致組播風暴，給板卡帶來大量的無效消息，嚴重影響內部通信性能；3）組播分發機制，對于發送源SRM來說，需要保證所有板卡路由消息接收的可靠性，帶來了太大的負載；4）路由消息是有狀態的，不能亂序；SRM 要考慮接收者的狀態以及鏈路狀況，對于組播來說算法太復雜；5）若專門為路由消息構建組播可靠傳輸機制，會使得現有的路由器內部通信機制更加復雜，不易實現。

2.3 TPRD模型

為了提高可重構路由器路由同步時間以及均衡路由消息分發過程中各板卡的負載，本文提出了一種新型的樹型路由并行分發模型。SRM計算出新的核心路由表后，構造路由更新消息，依次向k塊板卡發送。每個獲取到路由消息的板卡再向k個接收者發送，直到所有板卡都獲取到該路由消息，完成該路由消息在整個路由系統的同步。每個板卡遵循先傳播再處理的原則來節省系統同步時間，即板卡在轉發路由消息之后再進行本地核心路由表更新處理。可以發現，整個路由分發體系如同一棵 k叉樹。初始狀態只有樹根節點，即計算出新的核心路由表的SRM；每個節點只負責對自己子節點的路由消息發送，直到葉子節點。當k=1時，所有節點連成一條線，稱其為單路蔓延。

由于分發過程中節點對其子節點的路由傳遞是依次進行的，當給第2個子節點傳遞消息時，第1個子節點也開始給它的子節點傳遞消息。因此，樹的形成過程并不是平衡、均勻地向下蔓延。每一個周期，所有未滿k個子節點的節點，同時向自己的某個子節點傳送路由消息。最終形成一棵傾向一側的不均衡的k叉樹，樹的深度就是路由消息最長的轉發跳數，也就是整個系統路由分發的周期數。

圖2以2叉樹為例，描繪了路由分發過程中前4個周期路由分發情況，形成的是一棵不均衡2叉樹。任一狀態，準備進行消息傳遞的都是那些尚未滿2個子節點的節點，即圖2中實心節點。不失一般性，規定節點總是先將路由消息傳遞給左子節點，再傳給右子節點。所以，對于任一節點，其左子節點為根的子樹深度總比右子節點為根的子樹深度大 1。可以計算出每經過一個傳遞周期 Tone，能夠達到路由同步的節點數分別為1、2、4、7、12、20、33等。

圖2 基于2叉樹的并行分發示例

定義1 k路分發中，路由消息經過i個傳遞周期后，可重構路由器達到同步的線卡數為Fk(i)。

定義2 k路分發中，路由消息經過i個傳遞周期后，分發樹中有j個子節點的節點個數為Vk(i, j)，0≤j≤k。

根據TPRD模型路由分發規則，任一傳遞周期，分發樹中只有那些子節點數未滿k的節點會進行路由分發。所以，n個周期到n+1個周期增加的節點數，等于n個周期完成時子節點個數未滿k的節點數。滿足式(1):

而且，第n個分發周期后，分發樹中子節點數為0的節點個數，就是n?1個周期到第n個周期增加的節點數:Fk(n)?Fk(n?1)。同理，第n個周期后，分發樹中子節點數為1的節點個數，就是n?2個周期到 n?1 個周期增加的節點數 Fk(n?1)?Fk(n?2)。所以，第n個分發周期后，分發樹中各類節點滿足以下等式:

用上述等式替代式(1)中右邊Vk(i, j)項，得到:

所以，Fk(n)的計算公式為

所以，TPRD模型中可重構路由器路由消息的同步周期為 nTone，并滿足式(4)，符號定義同前面描述。

大規模路由消息分發事件發生，一般都伴隨著大量BGP update報文的收發，而update報文從線卡上交到SRM需要占用大量板間帶寬及板卡CPU資源。另一方面，TPRD模型中葉子節點沒有發送路由消息的工作，路由分發負載最輕，或者子節點數較少的節點（可稱其為近葉子節點）相對會有略少的路由消息傳遞工作。所以，將涉及 BGP協議報文收發的線卡設定為分發樹的葉子節點或近葉子節點，就可提高系統面對大量 BGP路由學習情況下的路由同步性能。令 LCBGP為路由器中 BGP會話連接收發報文所經線卡，此類線卡數量為θ。由于TPRD模型會將所有線卡對應成序列為從1到的節點，并且算法使得序列號大的節點總是后加入到分發樹中，成為葉子節點或近葉子節點的可能性極大。所以，可令θ個LCBGP的分發樹節點序號分別為從而達到LCBGP路由消息傳遞負載盡量小的目的。

3 算法實現

TPRD模型實施的關鍵在于將可重構路由器所有板卡視為樹節點，構造成符合模型思想的分發樹，即確定板卡間的父子關系（消息分發關系）。算法主要思想是:在設備剛啟動尚未進行核心路由表計算之前，由 SRM 根據當前板卡數計算出路由分發周期數；接著為每塊板卡計算其路由消息的下一個轉發板卡，即子節點；最后SRM將父子關系信息通告各板卡。SRM核心路由表變化時，將更新消息發給它的下一跳目的板卡；每塊板卡收到路由消息后，按預定轉發關系將消息依次轉發給它的下一跳目的板卡。也就是說，事先已計算每塊板卡的子節點號信息，路由分發時只需根據父子關系轉發路由消息。為方便描述，符號定義如表1所示。

表1 相關符號定義

算法假設路由器中所有板卡號都是從1開始依次編號，SRM的序號為1且為樹根節點。系統各板卡獲得路由轉發關系包括以下4步:

步驟1 SRM根據t計算路由同步到所有板卡需要的周期n，n滿足式(4)；

步驟 2 對所有節點的子節點號初始化為無效值，并將樹根節點放入處理隊列，詳見圖3(a)；

步驟 3 從樹根節點開始，依次計算節點間的父子關系，詳見圖3(b)；

步驟4 SRM將每塊板卡的子節點信息:S(i)(j)，即路由消息的下一跳轉發板卡號，通告各板卡。

圖3 TPRD模型相關算法

上述步驟后，系統每塊板卡都獲知了自已的子板卡號（分發樹中的子節點），收到路由消息后根據子板卡號進行下一跳轉發即可。各板卡路由消息接收處理過程如圖4所示，為了提高速度，板卡總是先轉發路由消息再進行本地存儲。子板卡號等于?1為無效值，無需處理。

表2給出了一個分配算法示例，給出了當系統中有7塊板卡時，針對2路分發通過隊列實現板卡父子關系計算的過程。初始化階段:計算出7塊板卡需要的分發周期為 3，即分發樹的深度為 3，1號板板卡入隊列。隊列中存儲的節點都是非葉子節點。每次針對隊列頭部節點計算它的子節點，左子節點的子樹深度為父節點減1，右子節點的子樹深度為父節點減2。節點代表的子樹深度大于0則需有入隊列操作。此后，頭部節點出隊列。由 SRM執行上述算法。

上述TPRD算法是針對路由系統正常工作時的描述，如果考慮板卡故障及熱插拔，則涉及分發樹的重計算。只要路由系統感知板卡增刪，TPRD算法就要根據新的板卡數重新進行上述4個步驟的工作，并按照新的分發樹進行路由同步。限于篇幅，本文不對該問題深入探討。另外，在實際路由器中（例如CRS1路由器和TSR路由器），線卡間的物理拓撲將會影響其對等關系屬性，而線卡間的交換結構是未來路由器體系結構的另一個研究難點。所以，本文采用了一個較理想的以太網總線交換模型開展研究工作。

圖4 板卡路由消息接收轉發處理流程

表2 TPRD算法實施示例

4 實驗及性能分析

本文從路由同步時間和負載均衡程度來評價路由分發算法。圖5給出了TPRD模型中k取值為1、2、3、4時，一條路由消息同步的板卡數隨發送周期的變化，圖5(a)和圖5(b)分別是針對不同板卡數量的分析。可以看出，板卡數量在100以下時，2路分發較單路蔓延同步速度提高的較快，3路分發較 2路分發有少量提高。隨著板卡數量增加，3路分發的優勢逐漸體現。當板卡數量達到10000以上時，3路分發較2路分發有明顯提高，4路分發較3路分發略有提高。對于負載均衡，在k路分發中，每個節點的路由消息傳遞負載就是與其子節點數相關。負載最重的就是擁有k個子節點的節點，負載為kCone，而負載最輕的就是葉子節點，負載為0。所以 k的值越小，整個可重構系統各板卡對于路由消息傳遞的負載就最均衡。

圖5 分發周期與同步板卡關系

基于上述分析，由于目前可重構路由器的系統規模不會到達萬塊板卡，加上對板卡負載均衡的考慮，本文建議通過2路TPRD分發方式實現可重構系統中各板卡的路由同步。當然，隨著路由器可重構體系結構的發展，設計者可以平衡同步時間及負載均衡再來選定k的值。

模擬實驗基于NS2進行，測試TPRD（2路分發）、TPRD（3路分發）和SRD 3種分發模式下，達到路由同步狀態的板卡數與所需時間的關系。每條路由消息為50byte，圖6(a)和圖6(b)分別是針對1條路由分發和100條路由分發的測試結果。顯然，TPRD相對傳統SRD分發模式同步時間有了很大的節省，并且隨著板卡數量增多優勢更明顯。另一方面，TPRD模式下2路分發和3路分發的路由同步速度卻相差無幾。由于2路分發相對3路分發各板卡負載更為均衡，因此本文認為TPRD模型2路分發最為合適。這與圖5的理論分析完全一致。接著，分析了板間有大量 BGP協議報文傳遞時路由同步模式的性能。實驗中 SRM 與 5個板卡間有185kbyte/s的 BGP協議報文交互。如前文分析，TPRD總會設置這些有背景流量的板卡為分發樹的葉子節點。實驗結果如圖6(c)和圖6(d)所示，與沒有BGP流量的實驗結果基本一致。

5 結束語

面對互聯網路由表容量的急劇增長，一個高效的路由分發模型是可重構路由器體系結構設計面臨的一個挑戰。本文首先對當前普遍實施的一對多點的主動廣播更新的路由同步模式進行了性能分析，它存在同步周期長、負載不均衡等問題。于是，基于可重構路由器典型路由體系架構，設計了TPRD樹型并行路由分發模型來分攤系統路由分發負載、提高路由同步速度。推導出TPRD模型的k路分發中，任一周期能達到路由同步的板卡數，并分析了k路分發時各板卡的負載均衡狀況。TPRD模型考慮了路由分發時伴隨大量 BGP update報文收發的情況，設置進行BGP協議報文收發的線卡為分發樹的葉子節點，從而保證這些線卡盡少量的路由消息分發負載。論文給出了TPRD模型的實現算法和具體實施方法，并就當前可重構路由器的體系結構而言，建議采用2路分發方式。基于NS2的實驗驗證了TPRD模型的快速路由分發特性。

圖6 不同分發模式基于NS2的實驗結果

可重構路由器的發展尚處于初期發展階段，還有很多重要問題需要研究，如:分布式路由協議、高速交換網絡互連結構、FIB表高效存儲等。本文下一步工作將圍繞這些問題展開研究，并將進行可重構路由器原型系統的實現。

[1]徐恪, 吳建平, 徐明偉.高等計算機網絡:體系結構、協議機制、算法設計與路由器技術[M].北京:機械工業出版社, 2009.XU K, WU J P, XU M W.Advanced Computer Networks:Architecture, Protocol Mechanism, Algorithm Design and Router Technology[M].Beijing:Mechanism Industry Press, 2009.

[2]Cisco CRS-1 carrier routing system[EB/OL].http://www.cisco.com,2011.

[3]TX matrix platform[EB/OL].http://www.juniper.net, 2010.

[4]The avici TSR:cornerstone of the multi-terabit core[EB/OL].http://www.avici.com, 2008.

[5]BGP routing table data[EB/OL].http://bgp.potaroo.net, 2011.

[6]MEYER D, ZHANG L, FALL K.Report from the IAB Workshop on Routing and Addressing[S].RFC 4984.2007.

[7]張曉哲, 盧錫城, 朱培棟.一種可擴展路由器轉發表同步框架及關鍵算法[J].軟件學報, 2006, 17(3):445-453.ZHANG X Z, LU X C, ZHU P D.A synchronization framework and critical algorithm maintaining single image of IP forwarding tables among cluster router’s nodes[J].Journal of Software, 2006, 17(3):445-453.

[8]吳鯤.可擴展路由器軟件體系結構研究[D].北京:清華大學,2006.WU K.Research on Software Architecture for Extensible Router [D].Beijing:Tsinghua University, 2006.