一種實(shí)用高效的FIB壓縮算法

廖夢(mèng)虎，張立平

（武漢鐵路職業(yè)技術(shù)學(xué)院 電子信息工程系，湖北 武漢 430205）

一種實(shí)用高效的FIB壓縮算法

廖夢(mèng)虎，張立平

（武漢鐵路職業(yè)技術(shù)學(xué)院 電子信息工程系，湖北 武漢 430205）

研究了高性能路由器FIB空間壓縮的問(wèn)題?；诙辔惶乩锼惴ê徒Y(jié)構(gòu)化分割的方式構(gòu)造FIB表，實(shí)現(xiàn)FIB表的結(jié)構(gòu)冗余和信息冗余的消除。以學(xué)校接入路由器FIB數(shù)據(jù)和FIB自動(dòng)生成工具生成的FIB數(shù)據(jù)進(jìn)行壓縮效率對(duì)比分析實(shí)驗(yàn)，表明該算法具有接近信息熵邊界的壓縮效率和較高的轉(zhuǎn)發(fā)性能。

FIB表壓縮；多位特里樹；結(jié)構(gòu)分割；FIB信息熵

現(xiàn)今，由于網(wǎng)絡(luò)規(guī)模的不斷增長(zhǎng)，影響IP查詢效率的FIB（Forward Information Base）表越來(lái)越龐大，需要占用更大的存儲(chǔ)空間，對(duì)路由器線卡上的網(wǎng)絡(luò)處理器（NP：Network Processor）的要求也就越高。文獻(xiàn)[1]指出當(dāng)前預(yù)設(shè)自由區(qū)（DFZ：Defaul Free Zone）中活動(dòng)IPv4路由前綴超過(guò)440，000，IPv6前綴也會(huì)很快達(dá)到這個(gè)程度?；诖?，許多專家認(rèn)為不斷增加的存儲(chǔ)需求遲早成為高性能路由器轉(zhuǎn)發(fā)平面的瓶頸[2]。FIB聚合是一種有效的降低FIB表大小、延長(zhǎng)已部署網(wǎng)絡(luò)設(shè)備生命周期、緩解互聯(lián)網(wǎng)路由擴(kuò)張帶來(lái)的擴(kuò)展性的解決方案[3，4]。其中以O(shè)RTC[3]為代表的降低FIB表轉(zhuǎn)發(fā)語(yǔ)義冗余和以多位特里樹[4]為代表的降低FIB表結(jié)構(gòu)冗余的方案最為典型。FIB壓縮除了要考量壓縮空間效率，還需要考慮壓縮后FIB查找和更新的算法復(fù)雜度必須在可控制范圍內(nèi)。只有滿足了這兩個(gè)條件，才有可能得到實(shí)際應(yīng)用。本文以多位特里樹算法為基礎(chǔ)，采用多位巴羅斯—惠勒編碼，通過(guò)降低FIB表的信息冗余的方式，將FIB表壓縮到進(jìn)一步接近FIB信息熵邊界的程度。同時(shí)，通過(guò)采取結(jié)構(gòu)化分割處理的方式，按照設(shè)定的子樹深度門限，將FIB多位特里樹分割成主干樹和特里子樹，降低FIB查找算法的時(shí)間復(fù)雜度。

一、系統(tǒng)概述

1.FIB冗余消除。為了實(shí)現(xiàn)FIB壓縮，首先需弄清楚FIB有哪些信息冗余。路由器中一個(gè)FIB表是由地址前綴及其關(guān)聯(lián)的下一跳索引標(biāo)識(shí)構(gòu)成的。下一跳索引標(biāo)識(shí)取值可以用[1，K]的整型表示。我們將FIB的條目數(shù)記為N。一個(gè)路由器不需要維護(hù)與互聯(lián)網(wǎng)中的其他所有路由器之間的鄰接關(guān)系，即K<

2.FIB層次消減。即使按照多位特里樹結(jié)構(gòu)來(lái)組織FIB，F(xiàn)IB查找的時(shí)間復(fù)雜度是O（W）。由于前綴地址長(zhǎng)度W可以到128位（IPv6地址），要實(shí)現(xiàn)分組的線性轉(zhuǎn)發(fā)還需要通過(guò)層次消減，減少FIB查詢次數(shù)才有可能?？梢酝ㄟ^(guò)將FIB結(jié)構(gòu)分割的方式減少FIB樹的層次。將源多位特里樹分割為設(shè)定層次閾值內(nèi)的多個(gè)特里子樹。子樹根節(jié)點(diǎn)作為中繼節(jié)點(diǎn)實(shí)現(xiàn)各子樹的關(guān)聯(lián)。

二、算法實(shí)現(xiàn)

1.多位特里子樹節(jié)點(diǎn)生成。本文在實(shí)現(xiàn)算法中，每個(gè)特里子樹節(jié)點(diǎn)采用多位特里算法生成。首先通過(guò)葉壓入算法生成多位特里樹，然后利用巴斯特—惠勒編碼，將多位特里樹進(jìn)行編碼轉(zhuǎn)換。這個(gè)基于巴斯特—惠勒編碼的多位特里樹節(jié)點(diǎn)生成算法可用一個(gè)三元組表示：XB（T）=（Slast，SI，Sa）來(lái)表示。其中：Slast和SI是描述特里子樹結(jié)構(gòu)的編碼，Sa是描述特里子樹下一跳索引標(biāo)識(shí)的編碼。其中各子串的生成方法如下：Slast是一個(gè)長(zhǎng)度為N的位串，如果在T中第i個(gè)節(jié)點(diǎn)是層級(jí)中最后一個(gè)“孩子”，則該位置1，否則置0；SI是一個(gè)長(zhǎng)度為N的位串，如果T中第i個(gè)節(jié)點(diǎn)是內(nèi)節(jié)點(diǎn)，則該位置0，否則置1；Sa長(zhǎng)度為N的串，用來(lái)編碼葉標(biāo)識(shí)。為了實(shí)現(xiàn)巴斯特—惠勒轉(zhuǎn)換，需要使用樹的寬度優(yōu)先來(lái)實(shí)現(xiàn)。假定根是last：Slast[0]=1，對(duì)于一個(gè)有t個(gè)節(jié)點(diǎn)的葉標(biāo)識(shí)特里樹T，XB（T）轉(zhuǎn)換可以在O（t）時(shí)間內(nèi)完成。

2.層次化多位特里子樹構(gòu)建。形成巴斯特—惠勒編碼的多位特里樹后，需要根據(jù)設(shè)定的子樹層級(jí)閾值進(jìn)行結(jié)構(gòu)化分割。當(dāng)子樹層次超過(guò)設(shè)定層次閾值時(shí)，將子樹結(jié)構(gòu)化分割為多個(gè)特里子樹。結(jié)構(gòu)化分割為兩個(gè)過(guò)程：節(jié)點(diǎn)增加和節(jié)點(diǎn)刪除過(guò)程。當(dāng)進(jìn)行特里子樹節(jié)點(diǎn)刪除操作時(shí)，如果子樹層次深度小于設(shè)定閾值h，且該子樹擁有一個(gè)父特里子樹，則需要將特里子樹的根合并到父特里子樹中，同時(shí)更新根在中繼中刪除的特里子樹中的樹節(jié)點(diǎn)。

三、算法評(píng)估

為了評(píng)估本文提出的算法的有效性，在Linux環(huán)境下，將FIB壓縮算法作為一個(gè)獨(dú)立的模塊插入到RIB和FIB之間，其運(yùn)行在用戶空間，而FIB查找等嵌入到Linux內(nèi)核。代碼在一個(gè)單核2.5GHz的Intel Core i5處理器上，64K字節(jié)L1數(shù)據(jù)緩存、256K字節(jié)的L2緩存和3M字節(jié)的L3緩存。評(píng)估結(jié)果如表1所示：

表1 壓縮效率對(duì)比列表

其中N為前綴數(shù)量，為下一跳的個(gè)數(shù)，H0為下一跳分布的香農(nóng)熵，I為信息理論限制，E為熵，XB為壓縮算法所需空間。可以實(shí)現(xiàn)2-4bit/每前綴的壓縮效果，接近信息理論邊界值。

隨著Web的快速發(fā)展，網(wǎng)絡(luò)信息需要有效的描述和存儲(chǔ)。FIB是一個(gè)典型的應(yīng)用需求。本文利用數(shù)據(jù)集節(jié)點(diǎn)間的關(guān)聯(lián)關(guān)系，通過(guò)巴羅斯—惠勒轉(zhuǎn)換，將葉壓入樹進(jìn)一步優(yōu)化，在不影響FIB查詢性能的前提下，使得位串壓縮率接近信息理論限制。同時(shí)，將巴羅斯—惠勒轉(zhuǎn)換后的多位特里樹進(jìn)行層次化分割處理，提升了FIB查詢算法的效率。

[1]G.Huston.BGP routing table analysis reports[DB/OL].

http：//bgp.potaroo.net/.

[2]D.Meyer，L.Zhang，and K.Fall.Report from the IABW orkshop on Routing and Addressing[D].RFC 4984，2007.

[3]V.Khare，D.Jen，X.Zhao，el.Evolution towardsglobal routingscalability[J].IEEE JSAC，2010，28（8）：1363-1375.

[4]R.P.D raves，C.King，S.Venkatachary，and B.D.Zill.Constructing Optimal IP Routing Tables[C].In Proceedings of IEEE Infocom，1999，3（1）：88-97.

G642.0

A

1674-9324（2014）25-0245-02

湖北省“十二五”規(guī)劃項(xiàng)目（2010ZX03004-003-03）。

廖夢(mèng)虎（1972-），男，湖北通城人，碩士研究生，武漢鐵路職業(yè)技術(shù)學(xué)院電子電氣工程系講師，主要研究方向：計(jì)算機(jī)應(yīng)用，計(jì)算機(jī)軟件，計(jì)算機(jī)網(wǎng)絡(luò)；張立平（1977-），女，湖北隨州人，碩士研究生，武漢鐵路職業(yè)技術(shù)學(xué)院電子電氣工程系講師，主要研究方向：計(jì)算機(jī)應(yīng)用，計(jì)算機(jī)軟件，計(jì)算機(jī)網(wǎng)絡(luò)。