摘 "要： 路由器共享能極大地節(jié)約運(yùn)營商成本，而建立高效的虛擬路由表是構(gòu)建共享路由器的前提。在此提出一種新的路由表合并方案，創(chuàng)新地借助Bitmap這種高效低耗的工具，構(gòu)建一種新型的共享Tire樹，建立一種高效的虛擬路由表結(jié)構(gòu)。這種新型路由表結(jié)構(gòu)，可以有效降低虛擬路由表的空間占用率，同時也具備較低的算法復(fù)雜度。最后，為算法建立了Petri網(wǎng)模型，希望在進(jìn)一步的工作中，能借助Petri網(wǎng)模型來優(yōu)化路由表結(jié)構(gòu)，獲得更好的性能。

關(guān)鍵字： 虛擬路由表; Bitmap; Trie樹; Petri網(wǎng)

中圖分類號： TN964?34 " " " " " " " " " 文獻(xiàn)標(biāo)識碼： A " " " " " " " " " " " " " "文章編號： 1004?373X（2015）06?0065?05

Petri network modeling and analysis of virtual routing table based on Bitmap

CHEN Xiang?yu， HU Huai?xiang， ZHANG Yu

（North China Institute of computing technology， Beijing 100091， China）

Abstract： Sharing of routers can greatly save the cost of ISPs. Establishment of efficient virtual routing table is a premise to build the shared routers. A new scheme for combining routing tables based on Bitmap is proposed in this paper. A novel sharing Tire and efficient virtual routing table are established by the aid of efficient low consumption tool Bitmap. The virtual routing table structure can reduce the space occupancy rate of virtual routing table effectively. It also has low algorithm complexity. A Petri model was established for the algorithm. It is expected to optimize the routing table structure by means of Petri model and get a better performance.

Keywords： virtual routing table; Bitmap; Trie; Petri

0 "引 "言

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

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

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

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

1.1 "簡單的Trie樹合并

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼20t1.tifgt;

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

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼20t2.tifgt;

圖2 FIB存儲圖示

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

1.2 "基于Leaf Pushing算法的合并

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼20t3.tifgt;

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

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

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼20t4.tifgt;

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

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

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

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

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

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼20t5.tifgt;

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

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

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

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼20t6.tifgt;

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

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼20t7.tifgt;

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

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼20t8.tifgt;

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

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

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)。

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼20t9.tifgt;

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

2.2 "性能評價(jià)

2.2.1 "簡單合并方案

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

2.2.2 "Leaf Pushing方案

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

2.2.3 "Braiding方案

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

2.2.4 "Bitmap方案

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

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

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

struct tnode {

unsigned long parent;

t_key key;

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

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

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

unsigned int empty_children; " " " " " " "http://表示空孩子的個數(shù)

struct node *child[0]; " " " " " " " " " " " " " //一個定長的結(jié)構(gòu)

struct bitmap_item item; " " " " " " "http://該節(jié)點(diǎn)對應(yīng)的bitmap表

};

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

struct bitmap_item {

char *bitmap; " " " " " " " " " " " " " " " " " " " " " " //位圖信息

long next_ptr; " " " " " " " " " " " " " " " " " " " //下一表項(xiàng)地址

struct next_address; " " " " " " " " " " " " " " " " " //下一跳地址

};

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼20t10.tifgt;

圖10 路由器大小比較圖示

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

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

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

3 "Petri網(wǎng)簡介

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

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

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

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼20t11.tifgt;

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

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

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

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

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

當(dāng)P6和P2同時滿足時，CPU經(jīng)T3執(zhí)行路由表整理操作，這里定義T3優(yōu)先級比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)冗余信息的壓縮儲存結(jié)構(gòu)，并借鑒前人工作，結(jié)合Braiding方案對本設(shè)計(jì)進(jìn)行了進(jìn)一步壓縮，使得虛擬路由表結(jié)構(gòu)從理論上得到大大壓縮。至此，本設(shè)計(jì)工作已完成對構(gòu)想的設(shè)計(jì)和建模。進(jìn)一步工作需要進(jìn)行仿真實(shí)驗(yàn)和網(wǎng)絡(luò)測量工作，以確定模型參數(shù)。進(jìn)而希望能通過對Petri網(wǎng)絡(luò)模型的分析，得出對本設(shè)計(jì)的改進(jìn)和優(yōu)化有意義的參考。

參考文獻(xiàn)

[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]// Proceedings of the ACM 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.