陳相宇，胡懷湘，張 玉

（華北計算技術(shù)研究所，北京 100091）

0 引 言

現(xiàn)代社會里可以依賴虛擬路由來實現(xiàn)客戶所特定需要的路由規(guī)則。大的ISP通常有很多客戶并且有大量的通往不同自治域的路由器，ISP的客戶通常對于路由器擁有不同的需求實現(xiàn)。對于金融企業(yè)和政府機構(gòu)的客戶來說，他們需要更安全的路由器，然而對于需要實時多媒體業(yè)務(wù)的客戶來說需要的是低延遲和高帶寬。為了滿足不同客戶的需要，ISP應(yīng)該根據(jù)不同客戶來分配適合其特色的路由器。然而在現(xiàn)有的BGP協(xié)議中，每一個BGP路由器對于每一個數(shù)據(jù)包只會選著一條看似不錯的路徑并把它發(fā)送給鄰居自治域。為了滿足更靈活且基于客戶要求的路由選擇策略，就只能為每個客戶分配路由器。這樣做無疑是很浪費且很昂貴的，從而在一個路由器上實現(xiàn)虛擬多個路由器是一個不錯的選擇。

虛擬路由器對于支持客戶制定的路由規(guī)則、策略路由、多種拓撲結(jié)構(gòu)路由和網(wǎng)絡(luò)虛擬是一項不錯的技術(shù)。在策略路由中，不同以往的單靠目的地址來路由，路由選擇可能根據(jù)的是應(yīng)用程序、協(xié)議和包的大小。在多種拓撲結(jié)構(gòu)路由中，配置不同獨立拓撲的路由來提供不同的服務(wù)。一個獨立的拓撲路由是一群路由和鏈接的子集，例如對于需要隱私保護的一個拓撲，一個路由子集就可以排除掉那些不安全的的鏈接或者路由。在這種方法中，需要同時幾個本地轉(zhuǎn)發(fā)信息庫（FIB）來轉(zhuǎn)發(fā)數(shù)據(jù)包。同樣虛擬路由對于簡化網(wǎng)絡(luò)管理和減少潛在的網(wǎng)絡(luò)擾亂也有一定的意義。同時虛擬路由對于研究人員實現(xiàn)并且評估新的網(wǎng)絡(luò)協(xié)議和網(wǎng)絡(luò)架構(gòu)有不錯的效果?，F(xiàn)在在虛擬路由中最核心的技術(shù)是路由的可擴展性和性能。對于一個實際的路由器，它可能需要支持幾十個或者上百個的虛擬路由并且每個虛擬路由都需要一個他自己的FIB。而且高速率的數(shù)據(jù)包到達的時間間隔是不一定的，這樣就更加要求邏輯上的路由器能夠同時支持所有的FIB。為了提供有效的數(shù)據(jù)轉(zhuǎn)發(fā)和IP地址路由，所有的FIB必須存儲在讀取延遲低的存儲體中。在通用處理器中的CACHE大小或者TCAM的內(nèi)存大小都不足以滿足很多的FIB同時存儲。例如：在juni?per的路由器中，只能最多支持16個左右的虛擬路由。

當(dāng)進行IP地址查找時，通過咨詢FIB路由器從數(shù)據(jù)包中提取出目的地址來決定下一跳目的地址。在現(xiàn)有的主干網(wǎng)絡(luò)上，一個FIB一般是包含250 KB個以上的路由表項。所有表項加起來大約是1.5 MB左右。當(dāng)用軟件來實現(xiàn)路由算法時，可能需要的內(nèi)存更多了。當(dāng)幾個FIB同時存儲在一個路由器上面，所需的內(nèi)存更多。如果直接用TCAM或者SRAM存儲的話，系統(tǒng)不僅復(fù)雜而且耗錢。若用軟件實現(xiàn)，現(xiàn)在通用CPU的CACHE一般只有2 MB左右，這明顯小于所需要存儲所有FIB的內(nèi)存大小。這樣實現(xiàn)一個共享的能夠存儲多個FIB的數(shù)據(jù)結(jié)構(gòu)至關(guān)重要。這數(shù)據(jù)結(jié)構(gòu)不僅要小而且能實現(xiàn)有效的查找。

1 現(xiàn)有虛擬路由方案簡介

1.1 簡單的Trie樹合并

一個FIB包含一系列前綴，每個前綴都有其相應(yīng)的長度和下一條的地址?？梢园袴IB對應(yīng)轉(zhuǎn)化為一個樹，如圖1所示。

圖1 FIB轉(zhuǎn)化圖示

當(dāng)有多個FIB在同一個邏輯路由器上，首先，用最直接的方法在共享的數(shù)據(jù)結(jié)構(gòu)上存放所有的FIB，即把所有的FIB存儲在同一個樹上。如圖2所示。

圖2 FIB存儲圖示

這種方法每個節(jié)點都需要存放每個FIB的表項并且用0表示某個節(jié)點沒有FIB的表項，這樣基本上就等于所有FIB的的表項。每個節(jié)點很大，比如一個表項是P大小，那么對于能夠?qū)崿F(xiàn)100個FIB的虛擬路由器來說，這個節(jié)點的大小為100P，這樣的話當(dāng)查找每個節(jié)點時，一次存儲器讀取可能會不夠，需要多次以上的讀取。對于最長前綴匹配的方法，可能需要多次的訪問節(jié)點。以往的單個FIB訪問每個節(jié)點的時候只需要讀取一次存儲器。

1.2 基于Leaf Pushing算法的合并

接下來，探索是否能對于每個樹節(jié)點的查找只進行一次存儲器讀取。對于最長前綴的匹配，需要存儲最近的匹配項，使得在進一步的匹配中沒有能夠匹配上的項時，使用最近一次的匹配項。為避免寫存儲器，只能把最長匹配法變成精確匹配法。在這種方法里面，所有的前綴都存儲在葉子節(jié)點中，這樣的話中間節(jié)點便不需要存儲FIB表項。構(gòu)建共享數(shù)據(jù)結(jié)構(gòu)的第一步，便是所有FIB的前綴集合轉(zhuǎn)化為一個共同的前綴集合。通過加入一個默認的前綴N0，使得集合完全。第二步，通過把聚合的前綴推往他們的子節(jié)點，使分支集合不相交。最后一步便是節(jié)點收縮，如果一個節(jié)點有2個相同的子節(jié)點的話，那么他們可以被刪去并保留他們父親節(jié)點。構(gòu)建所需的時間復(fù)雜度為O（M），M是樹節(jié)點數(shù)目。構(gòu)建過程如圖3所示。

圖3 構(gòu)建樹的圖示

當(dāng)數(shù)構(gòu)建完后，需要構(gòu)建一個樹節(jié)點序列、共享的下一跳表和所有的下一跳地址端口表。如圖4所示。

樹節(jié)點序列包括樹節(jié)點的分支值和指向端口的指針。因為樹是完全樹，所有一般代表2N個子節(jié)點。對于中間節(jié)點，指針指向的是它最左邊的節(jié)點。對于一個葉節(jié)點，指針指向的是共享下一條表的某個項目。假設(shè)在一個路由器中下一跳地址的數(shù)目少于256個，這樣的話需要1 B便能標(biāo)示每個FIB。對于T3和T4來說，他們都同時指向N1，這樣就可以減少共享下一條表的大小?？偟膩碚f：共享下一跳表項比所有的FIB的下一跳表項的總和要小。

圖4 所有下一跳表地址端口表構(gòu)建圖示

構(gòu)建這個數(shù)據(jù)結(jié)構(gòu)的步驟為：

（1）構(gòu)建所有的虛擬路由的下一跳地址端口表；

（2）構(gòu)建共享下一跳路由表，這一步通過遍歷所有的前綴集合，對于每一個前綴只有沒有相同的時候才能建立。對于冗余的更新下一跳表項的需要移除出去；

（3）構(gòu)建樹節(jié)點序列。

然而對于構(gòu)建這種算法，這種樹上的前綴節(jié)點集合大小要大于直接的前綴直接。這種算法的更新也有一定的困難。如果只是對于某個長24 b或者16 b的前綴進行更新，那么只需要一部分的更新，但是如果是對于默認路由那么就要更新很多地方了，如圖5所示。

圖5 構(gòu)建樹節(jié)點序列圖示

對于移除一個前綴來說可能會導(dǎo)致的是大部分的更新，這樣的話對于刪除操作來說就不能在樹上面進行從而降低復(fù)雜度。但是這樣需要額外的存儲空間容納新的樹節(jié)點隊列、共享的下一跳表和下一跳地址端口表。注意這種更新操作可能導(dǎo)致和開始創(chuàng)建的樹結(jié)構(gòu)完全不一樣，這樣的話需要定時的從新建造樹。

1.3 基于Braiding算法的改進

然而對于這種方法的評估并不能得到很好的效果。因為它要求2個樹基本上相同。當(dāng)2個樹如果相差很大，比方說一個從0開始，另外一個從1開始，則得到的合并樹并不能比分開存儲有多大的優(yōu)勢，如圖6所示。

圖6 合并前兩個相差大的樹

對于這2個樹的合并得到的樹如下。像這樣得到的leaf pushing樹節(jié)點就多很多了。如圖7所示。

圖7 2個樹合并圖示（一）

根據(jù)樹的結(jié)構(gòu)，可以對樹進行一定的處理來使得剛開始的樹是大致一樣的。就是在每個節(jié)點上都可以任意的調(diào)整其左右子樹，調(diào)整位置標(biāo)示為1。如把圖6中（b）樹根節(jié)點的左右子樹互換，這樣就可以使2棵樹大致形狀相等，然后再進行l(wèi)eaf pushing就有效的多。合并后如圖8所示。

圖8 2個樹合并圖示（二）

然而對于這樣的算法來說，雖然說總體上節(jié)點數(shù)目減少了，但是不是葉節(jié)點的節(jié)點需要的存儲空間變?yōu)榱薕（M+2P），M是虛擬路由的數(shù)目，P是指針的大小。這樣消耗的存儲空間也不小。并且這種方法只對于路由表有不同結(jié)構(gòu)的時候有效。

2 基于Bitmap的虛擬路由表結(jié)構(gòu)設(shè)計

2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計

為葉節(jié)點信息設(shè)計了一種新的數(shù)據(jù)結(jié)構(gòu)。

對于8個FIB的合并，Bitmap值定義為8位，每位對應(yīng)一個FIB。其中為1的位標(biāo)示相應(yīng)FIB在此節(jié)點存在匹配端口，指針指向一個特殊的端口表用以完成匹配；0則標(biāo)示不存在，需取最近的存在匹配端口的父節(jié)點做匹配。端口表每一行中的Bitmap位值均代表相應(yīng)FIB表中是否匹配緊跟其后的下一跳，若為1代表匹配，若為0則在下一行比對Bitmap。Bitmap為全1的行，表示此行為結(jié)尾行，其他未匹配上的均匹配此行下一跳。末尾一般建議留出幾行空白行，用于表項的添加，如圖9所示。

圖9 數(shù)據(jù)結(jié)構(gòu)設(shè)計圖示

2.2 性能評價

2.2.1 簡單合并方案

低效、高成本，節(jié)點體積太大，讀取操作多；更新速度快，算法簡單。

2.2.2 Leaf Pushing方案

Trie體積減小，共享下一跳表比原來大大縮??；前綴節(jié)點集合比原來大，更新算法復(fù)雜。

2.2.3 Braiding方案

Trie樹整合度高，壓縮了表的體積；需要周期性更新Trie樹。

2.2.4 Bitmap方案

在FIB數(shù)量較多時，減少冗余效果十分明顯，更新算法容易實現(xiàn)；但在FIB數(shù)量龐大而某節(jié)點冗余極少時，效果不明顯。另外，本設(shè)計中Bitmap位數(shù)必須先確定，當(dāng)虛擬路由表很多時，Bitmap位數(shù)也將對應(yīng)增長，這是本方案的一個待改進之處。

為了比較算法空間復(fù)雜度，設(shè)計了模擬實驗，并根據(jù)實驗結(jié)果做出曲線圖。

Trie樹節(jié)點數(shù)據(jù)結(jié)構(gòu)：

unsigned char pos；//本node要比較的位在32位IP中的偏移

unsigned char bits；//表示這個節(jié)點的孩子節(jié)點的位數(shù)，比如如果有2個孩子，那么需要1位，0表示第一個孩子，1表示第二個孩子；如果有4個孩子就需要2位，以此類推

unsigned int full_children；//表示孩子中有幾個是full的，所謂的full就是在插入操作的時候不能把這個孩子作為新插入的孩子的孩子從而擴展了。

Bitmap表項數(shù)據(jù)結(jié)構(gòu)：

路由表項數(shù)量為250 KB個時bitmap算法與簡單Trie樹合并算法的路由表大小比較，見圖10。

圖10 路由器大小比較圖示

2.3 進一步設(shè)計

通過上述介紹可以發(fā)現(xiàn)，本設(shè)計是基于對葉子節(jié)點的冗余信息的優(yōu)化。它本身沒有改變Trie樹整體結(jié)構(gòu)。因此，只要是適用于Trie樹結(jié)構(gòu)優(yōu)化的算法和設(shè)計，理論上都能適用于本設(shè)計。

在進一步的設(shè)計中，考慮加入Braiding方案對Trie樹結(jié)構(gòu)的優(yōu)化壓縮，這樣雖然提高了算法復(fù)雜度，但可以進一步壓縮儲存空間。而且對于Braiding方案，當(dāng)Trie樹結(jié)構(gòu)逐漸惡化，只需花費少量資源定期更新Trie樹，即可實現(xiàn)大部分時間空間和時間資源的有效壓縮。對于時間和空間資源分配的平衡性和算法效率的評價工作我們將在進一步工作中進行。

3 Petri網(wǎng)簡介

1962年，德國的C.A.Petri在他的博士論文《用自動機通信》中首次使用網(wǎng)狀結(jié)構(gòu)模擬通信系統(tǒng)，這是Petri網(wǎng)建立系統(tǒng)模型的起點。Petri網(wǎng)兼顧了嚴(yán)格定義與圖形語言兩個方面，具有豐富而嚴(yán)格的模型語義，同時又是一種圖形化的語言，具有直觀、易懂與易用的優(yōu)點。它采用庫所（Place）、變遷（Transition）、弧（Arc）的鏈接來表示系統(tǒng)的功能和結(jié)構(gòu)。

庫所表示系統(tǒng)中的條件、資源和信息等可以靜態(tài)表達的事物，在圖形具體表示中，用圓圈“○”或橢圓表示。變遷表示系統(tǒng)中的變化，如狀態(tài)的變化、條件的變化、信息的流動以及資源的消耗和產(chǎn)生等需要動態(tài)表達的事件，用矩形“口”或短棒“|”代表。弧表示庫所與變遷之間的流關(guān)系，用“→”來表示有向弧，用“—○”來表示抑制?。↖nhibitor Arc）。token表示庫所中代表的事物的數(shù)量，用黑點“?”表示庫所中含有的托肯。

4 Petri網(wǎng)建模分析

用Petri網(wǎng)理論建立起路由器內(nèi)部模型見圖11。

圖11 路由器內(nèi)部模型

Petri網(wǎng)模型中庫所及變遷含義：

P1為路由器緩存，它接收服從泊松到達的數(shù)據(jù)包，其容量以一個限制弧權(quán)來表示；

P2表示路由器CPU閑置狀態(tài)。當(dāng)同時滿足緩存中有數(shù)據(jù)包，且路由器閑置時通過即時變遷T1，CPU進入路由表查找態(tài)P3；

P5表示路由表的“整齊程度”，它的值用以度量路由表的匹配速度，其值為0時，路由表需要更新，即經(jīng)過變遷T5進入P6“路由表混亂態(tài)”；

當(dāng)P6和P2同時滿足時，CPU經(jīng)T3執(zhí)行路由表整理操作，這里定義T3優(yōu)先級比T1高；

T4表示整理路由表操作，其操作速度為路由表混亂度的函數(shù)，T2表示路由表查找操作，其速度也由路由表混亂度決定；

P0態(tài)用以實現(xiàn)系統(tǒng)閉環(huán)，其Token數(shù)可由實驗測試得到。

初始狀態(tài)下，路由表處于整齊態(tài)，即P5為1；CPU處于閑置態(tài)，即P2為1。

分析過程中，需要確定的函數(shù)有：路由表查找速度，即T2變遷速度函數(shù)；路由表惡化速度，即T5變遷速度函數(shù)；路由表整理操作速度函數(shù)，即T4變遷速度；路由器工作周期，即T6變遷速度。

5 結(jié)論和展望

本文提出了一種新的基于Bitmap的路由葉子節(jié)點冗余信息的壓縮儲存結(jié)構(gòu)，并借鑒前人工作，結(jié)合Braiding方案對本設(shè)計進行了進一步壓縮，使得虛擬路由表結(jié)構(gòu)從理論上得到大大壓縮。至此，本設(shè)計工作已完成對構(gòu)想的設(shè)計和建模。進一步工作需要進行仿真實驗和網(wǎng)絡(luò)測量工作，以確定模型參數(shù)。進而希望能通過對Petri網(wǎng)絡(luò)模型的分析，得出對本設(shè)計的改進和優(yōu)化有意義的參考。

[1]范曉勃，林闖，吳建平，等.分布式路由器的性能模型與分析[J].計算機學(xué)報，1999（11）：1?6.

[2]FU Jing，REXFORD Jennifer.Efficient IP?address lookup with a shared forwarding table for multiple virtual routers[C]//Pro?ceedingsoftheACM CoNEXT.New York， NY， USA：ACM 2008：4012?4033.

[3]SONG Hao?yu，KODIALAM Murali，HAO Fang，et al.Building scalable virtual routers with Trie braiding[C]//Proceedings of IEEE Conference on INFOCOM.[S.l.]：IEEE，2010：1442 ?1450.

[4]DRAVES R，KING C，VENKATACHARY S，et al.Constructing optimal IP routing tables[C]//Proc.of IEEE Infocom.[S.l.]：IEEE，1999：111?120.

[5]SRINIVASAN V，VARGHESE G.Fast address lookups using controlled prefix expansion[J].ACM Transactions on Computer Systems，1999，17（1）：1?4.

[6]DEGERMARK M.Small Forwarding Tables for Fast Routing Lookups[C]//Proceedings of ACM SIGCOMM Conference’97.[S.l.]：ACM，1997：3?14.