一種實用高效的FIB壓縮算法

廖夢虎，張立平

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

一種實用高效的FIB壓縮算法

廖夢虎，張立平

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

研究了高性能路由器FIB空間壓縮的問題。基于多位特里算法和結(jié)構(gòu)化分割的方式構(gòu)造FIB表，實現(xiàn)FIB表的結(jié)構(gòu)冗余和信息冗余的消除。以學(xué)校接入路由器FIB數(shù)據(jù)和FIB自動生成工具生成的FIB數(shù)據(jù)進行壓縮效率對比分析實驗，表明該算法具有接近信息熵邊界的壓縮效率和較高的轉(zhuǎn)發(fā)性能。

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

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

一、系統(tǒng)概述

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

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

二、算法實現(xiàn)

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

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

三、算法評估

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

表1 壓縮效率對比列表

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

隨著Web的快速發(fā)展，網(wǎng)絡(luò)信息需要有效的描述和存儲。FIB是一個典型的應(yīng)用需求。本文利用數(shù)據(jù)集節(jié)點間的關(guān)聯(lián)關(guān)系，通過巴羅斯—惠勒轉(zhuǎn)換，將葉壓入樹進一步優(yōu)化，在不影響FIB查詢性能的前提下，使得位串壓縮率接近信息理論限制。同時，將巴羅斯—惠勒轉(zhuǎ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ī)劃項目（2010ZX03004-003-03）。

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