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

張立平，廖夢虎

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

張立平，廖夢虎

（武漢鐵路職業技術學院，湖北 武漢 430205）

高性能IP路由器使用復雜的轉發表查找算法優化查找時間、存儲空間和更新時間．在對ORTC壓縮算法及信息熵理論研究的基礎上，提出了一種基于多位特里算法，通過消除信息冗余的方式實現對FIB的壓縮方法．該方法具有不改變路由語義和外部路由器行為特征，在典型的路由器應用環境下，可以節省約50%的存儲空間，路由查找效率可提高25%．

IP轉發表; 數據壓縮; 前綴樹

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

1 FIB壓縮實現原理

1.1FIB聚合原理

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

這種FIB壓縮算法是Draves等[4]在1998年設計的，稱為優化路由表構造器算法（ORTC：Optimal Routing Table Constructor）．不過該算法中針對源表的每次改變都需要重新計算一次聚合，算法的時間耗費與前綴樹種的節點線性相關，通常達到秒級．因此在高性能的路由器中無法實用．

本文在ORTC的基礎上，結合信息理論，通過驗證一個聚合調整后的FIB前綴樹的存儲空間是否達到了它的信息理論邊界作為FIB壓縮抉擇的依據，選擇最優的解集的方式實現理論最優化的FIB壓縮算法，簡稱為XB算法．

圖1 FIB聚合原理示意圖

1.2FIB壓縮實現框架

圖2 FIB壓縮實現框架示意圖

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

2 FIB壓縮算法描述

2.1 壓縮FIB構造

本文提出的FIB壓縮結構，是基于Jacobson[5]提出的簡潔的分級索引的二叉樹，通過巴羅斯—惠勒轉換，得到可以進一步簡潔描述的葉壓入樹．壓縮算法的前提是一個常規的葉標識特里樹．即在本壓縮算法執行前，已經進過葉壓入處理．

本算法思想是將T結構編碼歸并到2個位串中Slast和SI，將葉標識編碼為Sa串．通過無損的串壓縮來達到壓縮空間的邊界．該轉換算法可以用一個三元組表示：XB（T）=（Slast，SI，Sa）．其中：

Slast：一個長度為t的位串，T中第i個節點是層級中最后一個孩子該位置1，否則置0；

SI：如果第i個節點是內節點則該位為0，否則置1；

Sa：長度為n的串，用來編碼葉標識．

為了實現該轉換，需要使用樹的寬度優先遍歷來實現．算法過程描述如下：

i←0; j←0

BFS-TRAVERSE(節點v,i,j)

If v 是父節點的最后一個孩子 then

END BFS-TRAVERSE

假定根是last：Slast[0] = 1，對于一個有t個節點的葉標識特里樹T，XB（T）轉換可以在O(t)時間內完成，如圖3所示．

圖3 葉節點壓入特里樹的壓縮轉換示意圖

2.2Memory尺寸邊界

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

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

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

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

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

上述的零階熵邊界可以很容易地推進到高階熵．這是因為數據集中的成員之間相互依賴，他們之間的關聯關系越密切，就越容易從他們的鄰居推測出來，壓縮的效率就越高．高階串壓縮可以使用巴羅斯-惠勒轉換來計算數據集成員間的關聯關系，

3 算法評估

為了評估本文提出的算法的有效性，在Linux環境下，將FIB壓縮算法作為一個獨立的模塊插入到RIB和FIB之間，其運行在用戶空間，而FIB查找等嵌入到Linux內核．代碼在一個單核2.5GHz的Intel Core i5處理器上，64K字節L1數據緩存、256K字節的L2緩存和3M字節的L3緩存．

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

表1 壓縮效率對比列表

另外，還將本算法的查找執行效率與linux內核實現的fib_tries算法進行了對比．本文實現算法的FIB查找次數約為3萬次/s左右，遠小于fib_tries的300萬次/s．利用本文FIB算法的路由器轉發吞吐量是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

*項目來源：湖北省“十二五”規劃項目（2010ZX03004-003-03）

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