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

高性能路由器FIB壓縮方法*

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

（武漢鐵路職業(yè)技術(shù)學(xué)院，湖北 武漢 430205）

高性能IP路由器使用復(fù)雜的轉(zhuǎn)發(fā)表查找算法優(yōu)化查找時(shí)間、存儲(chǔ)空間和更新時(shí)間．在對(duì)ORTC壓縮算法及信息熵理論研究的基礎(chǔ)上，提出了一種基于多位特里算法，通過消除信息冗余的方式實(shí)現(xiàn)對(duì)FIB的壓縮方法．該方法具有不改變路由語義和外部路由器行為特征，在典型的路由器應(yīng)用環(huán)境下，可以節(jié)省約50%的存儲(chǔ)空間，路由查找效率可提高25%．

IP轉(zhuǎn)發(fā)表; 數(shù)據(jù)壓縮; 前綴樹

FIB（Forwarding Information Base）表的快速增長成為存儲(chǔ)空間和管理的負(fù)擔(dān)．如果采用已在Linux內(nèi)核中實(shí)現(xiàn)的fib_trie數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)這些路由前綴，需要占用大量的存儲(chǔ)空間，并且嚴(yán)重影響高速率的分組轉(zhuǎn)發(fā)性能[1]．文獻(xiàn)[2]研究以FIB聚合的方式壓縮FIB的大小，進(jìn)而延長已部署網(wǎng)絡(luò)設(shè)備的生命周期，緩解互聯(lián)網(wǎng)路由規(guī)模擴(kuò)張的問題．FIB聚合是一種將原始FIB表述轉(zhuǎn)換為一個(gè)占用空間小但又能提供快速查找的替代表述的技術(shù)．從最初的24字節(jié)/每前綴，可以采用哈希、路徑或?qū)訅嚎s多位Tries、位圖等壓縮方法將FIB的存儲(chǔ)空間占用降到2～4.5字節(jié)/每前綴．同時(shí)查找性能也會(huì)提升[3]．理論上，上述這些方法還未達(dá)到FIB表的壓縮極限．基于FIB信息熵壓縮度量，本文以FIB聚合為前提，提出一個(gè)熵壓縮的FIB數(shù)據(jù)結(jié)構(gòu)，以期實(shí)現(xiàn)FIB壓縮的理論極限．

1 FIB壓縮實(shí)現(xiàn)原理

1.1FIB聚合原理

FIB聚合就是在轉(zhuǎn)發(fā)等價(jià)的條件下將多個(gè)相同下一跳的路由條目減少為一個(gè)．一個(gè)明顯的例子是2個(gè)地址空間相鄰的路由前綴條目，如下一跳相同的2.0.0.0/8和3.0.0.0/8可以聚合為一個(gè)路由前綴條目2.0.0.0/7．圖1說明FIB表的聚合過程，其中2個(gè)下一跳為A的路由前綴條目可以聚合為一個(gè)/14條目．

這種FIB壓縮算法是Draves等[4]在1998年設(shè)計(jì)的，稱為優(yōu)化路由表構(gòu)造器算法（ORTC：Optimal Routing Table Constructor）．不過該算法中針對(duì)源表的每次改變都需要重新計(jì)算一次聚合，算法的時(shí)間耗費(fèi)與前綴樹種的節(jié)點(diǎn)線性相關(guān)，通常達(dá)到秒級(jí)．因此在高性能的路由器中無法實(shí)用．

本文在ORTC的基礎(chǔ)上，結(jié)合信息理論，通過驗(yàn)證一個(gè)聚合調(diào)整后的FIB前綴樹的存儲(chǔ)空間是否達(dá)到了它的信息理論邊界作為FIB壓縮抉擇的依據(jù)，選擇最優(yōu)的解集的方式實(shí)現(xiàn)理論最優(yōu)化的FIB壓縮算法，簡(jiǎn)稱為XB算法．

圖1 FIB聚合原理示意圖

1.2FIB壓縮實(shí)現(xiàn)框架

圖2 FIB壓縮實(shí)現(xiàn)框架示意圖

在Internet環(huán)境下，一個(gè)實(shí)用的FIB壓縮算法應(yīng)該是對(duì)現(xiàn)有的協(xié)議、關(guān)聯(lián)的數(shù)據(jù)結(jié)構(gòu)和FIB查找算法的影響盡量的小，這樣才能在現(xiàn)網(wǎng)中部署實(shí)施．本文提出的FIB壓縮算法可以在不改變FIB查找算法、路由協(xié)議及其關(guān)聯(lián)的數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，在現(xiàn)有的路由解析過程中作為一個(gè)模塊構(gòu)件插入．如圖2所示，在常規(guī)的路由器操作中，路由解析函數(shù)從BGP、IGP獲得路由條目，形成前前綴和下一跳的條目列表（FIB表）．同時(shí)，路由器在收到分組數(shù)據(jù)后，需要進(jìn)行FIB查找操作，在FIB表中尋找前綴最佳匹配的條目，指導(dǎo)分組數(shù)據(jù)的轉(zhuǎn)發(fā)．FIB壓縮算法插入到這兩塊功能之間，將FIB源表壓縮為便于轉(zhuǎn)發(fā)語義等價(jià)的新的FIB表．這個(gè)新表不影響原有的FIB查詢，指導(dǎo)分組轉(zhuǎn)發(fā)等操作．

2 FIB壓縮算法描述

2.1 壓縮FIB構(gòu)造

本文提出的FIB壓縮結(jié)構(gòu)，是基于Jacobson[5]提出的簡(jiǎn)潔的分級(jí)索引的二叉樹，通過巴羅斯—惠勒轉(zhuǎn)換，得到可以進(jìn)一步簡(jiǎn)潔描述的葉壓入樹．壓縮算法的前提是一個(gè)常規(guī)的葉標(biāo)識(shí)特里樹．即在本壓縮算法執(zhí)行前，已經(jīng)進(jìn)過葉壓入處理．

本算法思想是將T結(jié)構(gòu)編碼歸并到2個(gè)位串中Slast和SI，將葉標(biāo)識(shí)編碼為Sa串．通過無損的串壓縮來達(dá)到壓縮空間的邊界．該轉(zhuǎn)換算法可以用一個(gè)三元組表示：XB（T）=（Slast，SI，Sa）．其中：

Slast：一個(gè)長度為t的位串，T中第i個(gè)節(jié)點(diǎn)是層級(jí)中最后一個(gè)孩子該位置1，否則置0；

SI：如果第i個(gè)節(jié)點(diǎn)是內(nèi)節(jié)點(diǎn)則該位為0，否則置1；

Sa：長度為n的串，用來編碼葉標(biāo)識(shí)．

為了實(shí)現(xiàn)該轉(zhuǎn)換，需要使用樹的寬度優(yōu)先遍歷來實(shí)現(xiàn)．算法過程描述如下：

i←0; j←0

BFS-TRAVERSE(節(jié)點(diǎn)v,i,j)

If v 是父節(jié)點(diǎn)的最后一個(gè)孩子 then

END BFS-TRAVERSE

假定根是last：Slast[0] = 1，對(duì)于一個(gè)有t個(gè)節(jié)點(diǎn)的葉標(biāo)識(shí)特里樹T，XB（T）轉(zhuǎn)換可以在O(t)時(shí)間內(nèi)完成，如圖3所示．

圖3 葉節(jié)點(diǎn)壓入特里樹的壓縮轉(zhuǎn)換示意圖

2.2Memory尺寸邊界

首先，XB算法是一個(gè)簡(jiǎn)潔FIB表達(dá)方式，因此它支持FIB查找的算法時(shí)間復(fù)雜度為O(W)，且編碼為信息理論低界限．

定理1：假設(shè)一個(gè)有n個(gè)葉子的葉標(biāo)識(shí)特里樹T，通過XB(T)壓縮，可以用4n+nlgS位來儲(chǔ)存，且XB(T)的查找可以在O(W)時(shí)間內(nèi)完成．

證明：使用RRR簡(jiǎn)潔位串索引[6]，一個(gè)T樹可以最多用2t≈4n位來編碼形成Slast和SI位串，且可以在O(1)時(shí)間內(nèi)完成其中的選擇和排序操作．另外，最復(fù)雜的Sa也可以用δnlg位編碼，且編碼操作可以在O(1)時(shí)間內(nèi)完成．因此，每次迭代查找都可以在一個(gè)常量時(shí)間內(nèi)完成．

定理2：假定T為一個(gè)有n個(gè)葉子的適度的葉標(biāo)識(shí)特里樹，其大小為O(polylogn)．H0為葉標(biāo)識(shí)分布的香農(nóng)熵．那么XB(T)可以用4n+nH0+o(n)位編碼存儲(chǔ)，其查找時(shí)間花費(fèi)在O(W)時(shí)間內(nèi)．

證明：Slast和SI可以如前所述的方法進(jìn)行編碼，而Sa在字符空間為O(polylogn)的條件下，可以使用廣義小波分析樹編碼，存儲(chǔ)在4n+nH0+o(n)位的位串中，且訪問時(shí)間是O(1)[7]．

上述的零階熵邊界可以很容易地推進(jìn)到高階熵．這是因?yàn)閿?shù)據(jù)集中的成員之間相互依賴，他們之間的關(guān)聯(lián)關(guān)系越密切，就越容易從他們的鄰居推測(cè)出來，壓縮的效率就越高．高階串壓縮可以使用巴羅斯-惠勒轉(zhuǎn)換來計(jì)算數(shù)據(jù)集成員間的關(guān)聯(lián)關(guān)系，

3 算法評(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緩存．

FIB數(shù)據(jù)集的產(chǎn)生來源于實(shí)際IP路由器和隨機(jī)生成器．實(shí)際的IP路由器選擇了學(xué)校的接入路由器AR，采集的前綴數(shù)據(jù)有400K．隨機(jī)生成了兩組FIB數(shù)據(jù)，一組為600K的數(shù)據(jù)量，一組為1百萬數(shù)據(jù)量．隨機(jī)FIB數(shù)據(jù)集依照泊松分布（H0 = 1.06，δ= 5）進(jìn)行前綴分離和下一跳設(shè)置的方式生成的．用這三組數(shù)據(jù)驗(yàn)證本文壓縮算法的有效性．表1描述了采用XB算法和fib-tries算法可以實(shí)現(xiàn)的FIB數(shù)據(jù)集的存儲(chǔ)空間的需求對(duì)比列表，其中N為前綴數(shù)量；s下一跳數(shù)量；H0為下一跳分布的香農(nóng)熵；I為信息理論限制；E為熵．后兩列為針對(duì)三組數(shù)據(jù)集經(jīng)過XB壓縮算法和Fib-tries算法處理后所需存儲(chǔ)空間．從表1可以看出，XB算法可以實(shí)現(xiàn)2-4bit/每前綴的壓縮效果，是當(dāng)前FIB軟件壓縮最常用的fib-tries算法的2倍左右的壓縮效率，并接近信息理論邊界值．

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

另外，還將本算法的查找執(zhí)行效率與linux內(nèi)核實(shí)現(xiàn)的fib_tries算法進(jìn)行了對(duì)比．本文實(shí)現(xiàn)算法的FIB查找次數(shù)約為3萬次/s左右，遠(yuǎn)小于fib_tries的300萬次/s．利用本文FIB算法的路由器轉(zhuǎn)發(fā)吞吐量是fib_tries算法的2～3倍．

[1] Bolla R and Bruschi R. RFC2544 performance evaluation and internal measurements for a Linux based open router[J/OL]. http://ieeexplore.ieee.org/xpl/mostRecent Issuejsp?punumber=11206[2006-06-07/09].

[2] Zhao Xiaoliang, Dante J Pacella, and Jason Schiller. Routing scalability: an operator’s view[J]. IEEE J Sel A Commun, 2010，28（8）：1262-1270．

[3] Nilsson S and Karlsson G. IP-address lookup using LC-tries[J]. IEEE JSAC, 1999，17（6）：1083-1092．

[4] Draves R P, King C, Venkatachary S, et al. Constructing Optimal IP Routing Tables[C]// Proceedings of IEEE Infocom, 1999：88-97．

[5] Jacobson G. Space-efficient static trees and graphs[J]. IEEE FOCS, 1989，12（5）：549-554．

[6] Raman R, Raman V, Rao S S. Succinct indexabledictionaries with applications to encoding k-ary trees andmultisets[A]//ACM-SIAM SODA, 2002：233-242．

[7] Ferragina P, Manzini G, M¨akinen V, et al. Compressed representations of sequences and full-text Indexes[J]. ACM Trans Algorithms, 2007，3（2）：243-249．

FIB Compression Techniques of High Performance Router

ZHANG Liping, LIAO Menghu

（Wuhan Railway Vocational College of Technology, Wuhan, Hubei 430205,China）

IP routers use sophisticated forwarding table (FIB) lookup algorithms that reduce lookup time, storage, and update time. This paper presents a practical, optimal FIB aggregation scheme that reduces forwarding table size without modifying routing semantics or the external behavior of routers, and FIB lookup algorithms and related hardware and software. On typical IP routers, this method will reduce FIB storage by at least 50%, and reduce average lookup time by 25% for a uniform traffic matrix.

IP forwarding table; data compression; prefix tree

T319

A

1672-0318（2014）03-0017-04

2013-12-18

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

張立平（1977-），女，湖北隨州人，講師，主要研究方向：計(jì)算機(jī)軟件及應(yīng)用．