一種基于Bitmap的虛擬路由表算法的Petri網(wǎng)建模與分析

陳相宇，胡懷湘，張 玉

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

0 引 言

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

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

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

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

1.1 簡單的Trie樹合并

一個(gè)FIB包含一系列前綴，每個(gè)前綴都有其相應(yīng)的長度和下一條的地址。可以把FIB對(duì)應(yīng)轉(zhuǎn)化為一個(gè)樹，如圖1所示。

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

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

圖2 FIB存儲(chǔ)圖示

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

1.2 基于Leaf Pushing算法的合并

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

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

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

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

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

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

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

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

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

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

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

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

1.3 基于Braiding算法的改進(jìn)

然而對(duì)于這種方法的評(píng)估并不能得到很好的效果。因?yàn)樗?個(gè)樹基本上相同。當(dāng)2個(gè)樹如果相差很大，比方說一個(gè)從0開始，另外一個(gè)從1開始，則得到的合并樹并不能比分開存儲(chǔ)有多大的優(yōu)勢(shì)，如圖6所示。

圖6 合并前兩個(gè)相差大的樹

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

圖7 2個(gè)樹合并圖示（一）

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

圖8 2個(gè)樹合并圖示（二）

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

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

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

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

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

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

2.2 性能評(píng)價(jià)

2.2.1 簡單合并方案

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

2.2.2 Leaf Pushing方案

Trie體積減小，共享下一跳表比原來大大縮?。磺熬Y節(jié)點(diǎn)集合比原來大，更新算法復(fù)雜。

2.2.3 Braiding方案

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

2.2.4 Bitmap方案

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

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

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

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

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

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

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

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

圖10 路由器大小比較圖示

2.3 進(jìn)一步設(shè)計(jì)

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

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

3 Petri網(wǎng)簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論和展望

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

[1]范曉勃，林闖，吳建平，等.分布式路由器的性能模型與分析[J].計(jì)算機(jī)學(xué)報(bào)，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.