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

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

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

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

虛擬路由器對(duì)于支持客戶(hù)制定的路由規(guī)則、策略路由、多種拓?fù)浣Y(jié)構(gòu)路由和網(wǎng)絡(luò)虛擬是一項(xiàng)不錯(cuò)的技術(shù)。在策略路由中，不同以往的單靠目的地址來(lái)路由，路由選擇可能根據(jù)的是應(yīng)用程序、協(xié)議和包的大小。在多種拓?fù)浣Y(jié)構(gòu)路由中，配置不同獨(dú)立拓?fù)涞穆酚蓙?lái)提供不同的服務(wù)。一個(gè)獨(dú)立的拓?fù)渎酚墒且蝗郝酚珊玩溄拥淖蛹?，例如?duì)于需要隱私保護(hù)的一個(gè)拓?fù)洌粋€(gè)路由子集就可以排除掉那些不安全的的鏈接或者路由。在這種方法中，需要同時(shí)幾個(gè)本地轉(zhuǎn)發(fā)信息庫(kù)（FIB）來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)包。同樣虛擬路由對(duì)于簡(jiǎn)化網(wǎng)絡(luò)管理和減少潛在的網(wǎng)絡(luò)擾亂也有一定的意義。同時(shí)虛擬路由對(duì)于研究人員實(shí)現(xiàn)并且評(píng)估新的網(wǎng)絡(luò)協(xié)議和網(wǎng)絡(luò)架構(gòu)有不錯(cuò)的效果。現(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)存大小都不足以滿(mǎn)足很多的FIB同時(shí)存儲(chǔ)。例如：在juniper的路由器中，只能最多支持16個(gè)左右的虛擬路由。

當(dāng)進(jìn)行IP地址查找時(shí)，通過(guò)咨詢(xún)FIB路由器從數(shù)據(jù)包中提取出目的地址來(lái)決定下一跳目的地址。在現(xiàn)有的主干網(wǎng)絡(luò)上，一個(gè)FIB一般是包含250 KB個(gè)以上的路由表項(xiàng)。所有表項(xiàng)加起來(lái)大約是1.5 MB左右。當(dāng)用軟件來(lái)實(shí)現(xiàn)路由算法時(shí)，可能需要的內(nèi)存更多了。當(dāng)幾個(gè)FIB同時(shí)存儲(chǔ)在一個(gè)路由器上面，所需的內(nèi)存更多。如果直接用TCAM或者SRAM存儲(chǔ)的話，系統(tǒng)不僅復(fù)雜而且耗錢(qián)。若用軟件實(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)有虛擬路由方案簡(jiǎn)介

1.1 "簡(jiǎn)單的Trie樹(shù)合并

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

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

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

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

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

圖2 FIB存儲(chǔ)圖示

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

1.2 "基于Leaf Pushing算法的合并

接下來(lái)，探索是否能對(duì)于每個(gè)樹(shù)節(jié)點(diǎn)的查找只進(jìn)行一次存儲(chǔ)器讀取。對(duì)于最長(zhǎng)前綴的匹配，需要存儲(chǔ)最近的匹配項(xiàng)，使得在進(jìn)一步的匹配中沒(méi)有能夠匹配上的項(xiàng)時(shí)，使用最近一次的匹配項(xiàng)。為避免寫(xiě)存儲(chǔ)器，只能把最長(zhǎng)匹配法變成精確匹配法。在這種方法里面，所有的前綴都存儲(chǔ)在葉子節(jié)點(diǎn)中，這樣的話中間節(jié)點(diǎn)便不需要存儲(chǔ)FIB表項(xiàng)。構(gòu)建共享數(shù)據(jù)結(jié)構(gòu)的第一步，便是所有FIB的前綴集合轉(zhuǎn)化為一個(gè)共同的前綴集合。通過(guò)加入一個(gè)默認(rèn)的前綴N0，使得集合完全。第二步，通過(guò)把聚合的前綴推往他們的子節(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是樹(shù)節(jié)點(diǎn)數(shù)目。構(gòu)建過(guò)程如圖3所示。

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

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

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

樹(shù)節(jié)點(diǎn)序列包括樹(shù)節(jié)點(diǎn)的分支值和指向端口的指針。因?yàn)闃?shù)是完全樹(shù)，所有一般代表2N個(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來(lái)說(shuō)，他們都同時(shí)指向N1，這樣就可以減少共享下一條表的大小?？偟膩?lái)說(shuō)：共享下一跳表項(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)建這個(gè)數(shù)據(jù)結(jié)構(gòu)的步驟為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

然而對(duì)于這樣的算法來(lái)說(shuō)，雖然說(shuō)總體上節(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所示。

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 "性能評(píng)價(jià)

2.2.1 "簡(jiǎn)單合并方案

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

2.2.2 "Leaf Pushing方案

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

2.2.3 "Braiding方案

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

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)增長(zhǎng)，這是本方案的一個(gè)待改進(jìn)之處。

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

Trie樹(shù)節(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; //表示這個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)的位數(shù)，比如如果有2個(gè)孩子，那么需要1位，0表示第一個(gè)孩子，1表示第二個(gè)孩子;如果有4個(gè)孩子就需要2位，以此類(lèi)推

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

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

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

struct bitmap_item item; " " " " " " "http://該節(jié)點(diǎn)對(duì)應(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個(gè)時(shí)bitmap算法與簡(jiǎn)單Trie樹(shù)合并算法的路由表大小比較，見(jiàn)圖10。

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

圖10 路由器大小比較圖示

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

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

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

3 "Petri網(wǎng)簡(jiǎn)介

1962年，德國(guó)的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)格定義與圖形語(yǔ)言?xún)蓚€(gè)方面，具有豐富而嚴(yán)格的模型語(yǔ)義，同時(shí)又是一種圖形化的語(yǔ)言，具有直觀、易懂與易用的優(yōu)點(diǎn)。它采用庫(kù)所（Place）、變遷（Transition）、?。ˋrc）的鏈接來(lái)表示系統(tǒng)的功能和結(jié)構(gòu)。

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

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

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

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

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

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

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

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

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

當(dāng)P6和P2同時(shí)滿(mǎn)足時(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)測(cè)試得到。

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

分析過(guò)程中，需要確定的函數(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ò)測(cè)量工作，以確定模型參數(shù)。進(jìn)而希望能通過(guò)對(duì)Petri網(wǎng)絡(luò)模型的分析，得出對(duì)本設(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.