多級索引路由查找算法及其實現

摘要：路由查找是IP網絡傳輸中或者基于IP構建的通信分組網中的重要組成部分。多分枝trie樹查找算法是一種快速高效的路由查找算法，但同時也帶來了巨大的內存開銷。一種改進的多分枝trie樹查找算法，即多級索引路由查找算法，將原有算法中的二級索引擴展為多級索引，并引入了標志位連續存儲的方式，在基本不影響查找效率的前提下，極大地減小了路由索引表的內存開銷。

關鍵詞：路由；查找算法；trie樹；多級索引

Abstract: Routing lookup is an important technology for IP transmission network and IP-based packet switching network. Although the multi-branch trie tree lookup algorithm is a fast and efficient routing lookup algorithm， it also makes large memory consuming. A multi-level index lookup algorithm， i.e.， an improved multi-branch trie tree lookup algorithm， is proposed. It expands the original two-level index to multi-level index， and introduces a continuous flag bit storage method that is able to extremely reduce memory overhead of routing index table while not obviously affecting the lookup efficiency.

Key words:route; lookup algorithm; trie tree; multi-level index

IP網絡傳輸中或者以IP構建的通信分組網中，路由查找是極其重要的部分。本文介紹一種路由快速查找的軟件算法，并針對該算法內存開銷較大的問題提出改進方案及實現方法。多分枝trie樹查找算法^[1]是一種快速高效的路由查找算法，通過IP地址的某一段比特位依次查找一個trie樹結構的索引表，找到對應的路由。該算法雖然查找效率極高，但內存開銷較大，一種改進算法是加入索引壓縮機制，稱為二層多分枝壓縮trie樹算法^[2]。壓縮后的索引在一定程度上減少了內存開銷，但是其內存開銷仍很大，同時由于索引項數與添加的路由掩碼長度等特征有關，使得人們不能預知索引表的內存大小，很難適用于內存池集管理方式。本文首先介紹該算法的原理及其實現，其后給出改進后的算法，最后給出性能比較。

1 路由查找的最佳匹配準則

下面先給出幾個路由相關的稱謂，同時給出它們的數學表達：

(1)如果IP地址a在路由A的索引范圍之內，則稱路由A是地址a的路由，即路由A匹配地址a。

數學表達為：

(2)如果路由A的索引范圍包含路由B的索引范圍，則稱路由A為路由B的次匹配路由。

數學表達為：

(3)如果路由A在所有a的路由中掩碼最長，則稱路由A是地址a的最優匹配路由，即最長掩碼路由，也是對地址a進行有效轉發的那條路由。當用地址a進行路由查找時，結果應該是A。

數學表達為：

其中Ra為一張路由表中所有a的路由集合，如果a∈A，則一定有A∈Ra；a∈=A表示路由A是地址a的最優路由。

(4)如果路由A在路由B的所有次匹配路由中掩碼長度最長，則稱路由A是路由B的最長掩碼次匹配路由。

數學表達為：

下面給出路由查找的最佳匹配準則，也稱最長掩碼匹配準則：查找一個地址對應的路由時，如果路由中存在多個路由滿足條件，選用掩碼最長的那條路由。

2 分段索引表的原理

分段索引表是根據地址的映射空間直接定位路由表，用索引來表達路由的前綴地址空間，從而建立地址與索引一對多的對應關系。如果不考慮內存的問題，我們可以建立一個索引數組來表達IPv4的全地址空間，我們將這個索引表稱為“全IP地址映射索引表”，如圖1。整個路由表分為路由索引表和下一跳表兩部分，左側的路由索引表負責路由的快速查找，而右側下一跳表存儲路由的下一跳轉發信息，也就是通常所說的路由表。索引表由4 294 967 296個索引表項組成，依次表示IPv4地址的從0x00000000到0xFFFFFFFF間的所有地址，索引表的每一項用于存儲其對應的下一跳表的指針。通過IP地址查找路由時，只需將IP地址作為索引表的數組下標，取出對應的路由表項。例如，如果要查找IP地址1.2.3.4所屬的路由，只需取出索引表的第0x01020304項，通過下一跳表，該索引表項便指向對應的路由0x01020300/24。每一個索引表項都唯一對應一項路由表(如果沒有對應的路由，則指針為“空”)，但一條路由往往對應多個索引表項，圖1中路由0x01020300/24對應著從0x01020300到0x010203FF的256項索引。

在全IP地址映射索引表中，路由對應的索引項數取決于路由掩碼長度，如果該路由掩碼長度為pfx_len，它將對應232-pfx_len項索引表。

當存在一個索引對應多條路由時，即這些路由的索引范圍出現重疊，索引將選擇掩碼最長的那條路由與之對應，這便是索引表的路由最長掩碼匹配實現。即索引機制中的最優匹配準則體現在路由的增刪中，不影響路由的查找，這一點有別于其他一些路由查找算法(如radix樹)。圖2中，路由表中有3條路由0x01020300/24、0x01020300/16和0x01020304/32都是地址0x01020304的路由，但由于第三條路由的掩碼最長，最終將選用第三條路由。

3 二級索引表

3.1 二級索引表的結構

全IP地址映射索引表無疑具有很高的查找效率(這種索引表的路由查找非常精確，是“定位”而非“查找”)，但問題是索引表的內存消耗過大：索引表擁有4G個表項，每個索引表項存儲4字節的下一跳表指針，那么整個索引表將占用16 GB的內存，這在目前幾乎是不可能實現的。實際使用的路由表采用的是分級索引的方式，即通過多級索引表鏈接定位一條路由，這種算法來源于Gupta的多分枝trie樹查找算法，其后Huang等人引入索引壓縮機制，這種索引機制通常被稱作二級索引。

二級索引表由兩級索引組成(如圖3所示)。第一級索引步長固定，其索引表項由兩部分組成：指針和標志。指針采用復用的形式，一級索引表既可能直接指向路由表，也可能指向二級索引表，再由二級索引表指向路由表；標志用于表示二級索引表的步長，如果標志為0，表示索引表直接指向路由表。第二級索引采用索引壓縮機制，根據路由掩碼長度選擇適當的步長(每級索引表所能表達的IP地址的長度稱作該級索引表的步長)，如果某級索引表步長為n，則該級索引表便具有2n個索引表項。

為了描述簡單，我們采用24-8的索引形式來說明，即一級索引表步長為24，二級索引表步長最大為8。仍以查找地址0x01020304為例，因為一級索引表的步長為24，所以取出地址的前3個字節0x010203作為一級索引表的數組下標；對應的索引表的標志為6，表示一級索引表的指針表項并不直接指向路由表，而是指向一個步長為6的二級索引表；由最低的1個字節去定位它在二級索引表中的偏移，因為該二級索引表的步長為6，所以偏移量為最后1個字節的高6比特，即0x04>>2，該位置存儲的便是對應路由的指針。二級索引表總步長為30，則該二級索引指向的路由掩碼最長為30，也就是說索引表的總步長不能小于路由掩碼。如果路由的掩碼長度小于一級索引的步長，便不需要添加二級索引表，這時對應的一級索引表中標志為0，索引項直接指向路由表。

3.2 二級索引的內存開銷

下面我們來討論一下二級索引表需要占用的內存大小。以20-12的二級索引表為例，如果路由表最大支持1K條路由，則整個索引表最大耗用內存的情形是每條路由都有一個一一對應的最大的二級索引表指向它，則索引表需要的索引項數為：2²⁰+2¹²×1K=5M，而前面說到的全IP地址映射索引表需要4G個索引表項，已然是天壤之別。顯然分級索引極大的節省了內存空間，這是因為：

●路由的掩碼長度并不總是32；

●程序支持的路由條目數是有限的。

也就是說，分級索引表之所以節省內存空間，主要在于它不必映射全部的IP地址空間，而只是按路由表中的路由映射部分IP地址空間，這樣在一定程度上，便將地址的樣本空間與路由樣本空間相關聯。如果用二級索引表來表達一個IPv4的全地址空間，需要每個一級索引都掛有一個最大的二級索引表，總計需要2²⁰+2¹²×2²⁰=4 097M個索引表項。所以分級索引之所以節省內存空間，主要在于它對IP地址的部分映射。

分級索引表沿用了通過IP地址直接定位路由表的形式，所不同的是定位次數，全IP地址映射索引表只需一次定位，二級索引最大需要兩次定位，但這仍舊是直接定位的方式，相比而言，查找效率并未明顯降低。

但是二級索引表仍舊不完全適合我們的系統，因為首先這種索引結構還是需要較大的內存空間：為了表達一條32位掩碼的地址路由，需要申請2¹²×4=16K字節的內存空間作為第二級索引表，這就造成了極大的內存浪費；其次，第二級索引由于采用了壓縮機制，雖然一定程度節省了內存，但也使得索引表的大小不可預知，很難適應內存池集技術的內存管理方式。

4 多級索引表

4.1 多級索引表結構

多級索引是一種多層多分枝trie樹，仍采用通過地址分段定位的方式進行路由表查找，但針對二級索引存在的內存問題做了如下改進：

●采用多層索引表串聯的形式定位路由表。根據上一節的分析，這種算法更加細化了IP地址空間，從而可以有效的減小索引表的內存開銷。

●將索引項由4字節的指針改為2字節的數組標號。

●二級索引表中標志字段雖然申明為1個字節，但由于字節對齊的緣故，耗用了4個字節。如果將標志位連續存儲，可以減小標志字段的實際內存開銷。

●不采用索引壓縮技術，即索引步長固定。如果索引步長較小，索引壓縮技術節省內存開銷的效果便不是那么明顯了，相反還會使算法復雜化。同時固定步長的索引塊不受內存管理方式的限制。

多級索引表是一種多分枝的trie樹，由多級索引構成，同一級索引的步長相等，但不同級之間的索引步長不要求相等。IPv4路由表的各級索引表步長和為32。多級索引表的表項，我們稱之為“索引項”，是一個16比特的序號。該序號是復用的，表示路由表的數組下標或者下一級索引的索引描述符表的數組下標。這里路由表為狹義路由表，指用來存儲下一跳等信息結構體數組。由索引表項組成的數組稱為“索引塊”，與二級索引算法中的索引表相對應，用以表達路由前綴特定的幾個比特位。不同的是多級索引中每一級的步長都是固定的(二級索引算法中第二級索引的項數是不定的)，所以每級索引塊的大小是固定的，這使得每個索引塊耗用的內存空間是預知的，同時降低了一定的代碼復雜度。

由于索引項的序號是復用的，所以需要用1比特的標志位來區分索引項的含義。如果這個標志作為索引表項的一個成員存在，那么它將至少占用1個字節(還需要考慮字節對齊問題)。

為了節省空間，我們為每個索引塊關聯一個標志位塊，如圖4，標志位塊的每一個比特位與索引塊的每一項在邏輯上一一對應，用以區分索引項表征的內容。如果索引塊有8項，對應的標志位塊的大小便為1字節，即8比特。

為了加強標志位塊與索引塊的關聯，將它們的起始地址放到同一個結構體中，稱該結構體為“索引描述符”。如圖4，索引描述符的兩個指針成員：標志指針和塊指針分別指向標志位塊和索引塊，而標志位塊中的每一位與索引塊中的每一項一一對應，例如，索引塊中的第5項中索引的含義由標志位塊中第5比特決定。引入索引描述符后，便可以通過索引描述符間接定位索引塊及其對應的標志位塊。標志位塊是一個用字節形式存儲的數組，如果已知地址在索引塊中的偏移，即數組下標，將下標除以8，即得到對應的標志位塊的下標，而下標對8取余，便可得對應的比特。

每級索引都可能包括多個描述符，這些描述符以數組的形式存在，稱之為“索引描述符表”。每一級索引都有一個唯一的索引描述符表，用以存儲本級的所有描述符。因為可以通過索引描述符來定位索引塊，所以當要連接下一級索引塊時，可以記錄索引塊所對應的描述符在索引描述符表中的下標，如圖5。多級索引算法通過描述符表與索引塊、標志位塊相互鏈接定位一條路由：

●通過索引描述符表定位索引塊及其對應的標志位塊；

●通過地址和索引表對應的比特位計算在該級索引塊中的偏移，取出序號，根據對應標志位是否置位判決是否為路由表序號；

●如果索引中存儲的是次級索引表的序號，那么就以此序號作為次級索引描述符表的數組下標，取出相應的索引描述符，重復以上步驟。

相比圖3，顯然多級索引表更為復雜，不但增加了索引級數，而且在各級索引表的連接中增加了描述符表節點，該節點的引入主要由于將索引表(塊)的每一項由指針改為索引的緣故。

圖5中需要注意的是：

●為了結構與代碼實現上的統一，第一級索引塊和第一級標志位塊也用索引描述符關聯。第一級索引描述符表只有一項。

●因為最后一項索引塊存儲的一定是路由表索引，所以不需要標志位數組，但仍用索引描述符表將索引塊關聯，只是將描述符表的標志位塊指針置為“空”。

●索引描述符中存儲的是索引塊和標志位塊的指針，而非數組實例。這樣可以使索引描述符的使用更為靈活，因為其結構不受索引表步長的影響，各級索引表的描述符可以使用相同的結構，從而使得索引表的級數和步長可以定制。

4.2 多級索引的開銷

首先我們給出多級索引的最大內存開銷公式：

其中L為索引表內存開銷，M為路由條目數，路由級數為n+1，各級索引的步長依次為x0，x1......xn。第一級索引表的大小與路由容量無關，所以第一級索引表的內存開銷只與第一級索引步長x0有關，為項索引；而第二級、第三級……的內存開銷與路由容量相關，最差的情形下，各級索引表(第一級索引表除外)的個數為路由表容量M，所以L表示的是索引表最大所需要的索引表的索引項數。使內存開銷L最小的最大內存開銷問題便近似為求取以上公式的條件極值。求得：

不難看出，式(1)、式(2)所表達的含義為：如果路由表容量為M時，當第一級索引步長比其余各級索引步長長logM時，索引表的最大內存開銷最小。

根據公式(1)，表1列出幾種典型的索引配置在不同路由條目數下的內存開銷。

表1中第一列表示索引級數及索引長度，如(20，6，6)表示索引表級數為3，各級索引表步長依次為20、6和6；第一行表示路由表容量，即路由表所能支持的路由最大條目數；表中數據表示在不同索引長度和索引表容量下索引表所需的最大內存開銷，單位為兆字節。而二級索引表所對應的最大內存開銷見表2，在相同的路由表容量下，二級索引表的最大內存開銷要比多級索引表的大很多，顯然多級索引表在最大內存開銷方面的性能要遠優于二級索引表。表2中“/”表示開銷過大，無統計意義。

另外，從表1中可以看出，通常索引級數越大，最大內存開銷便越小，但并不是說索引級數越大越好，因為伴隨著索引級數的增大，路由查找的效率會有一定程度的降低，如表3所示，表中顯示的是不同索引表(第一列)在不同路由條目數下路由最佳匹配所需的時鐘周期數，測試環境為ARM公司主頻為200 MHz的處理器。可以看出索引級數的增大，一定程度上會導致查找效率的降低，所以并非索引級數越長越好，而是要兼顧內存開銷和查找效率，極端的，當索引級數為32時，多分枝trie樹便退化成了二進制trie樹。有關多分枝trie樹和二進制trie樹的查找性能可以查看文獻^[3]。

5 結束語

多級索引相比二級索引而言，索引級數較多，步長較短，因而可以很大程度地減少路由前綴地址在索引表中的映射空間，從而可以有效地節省內存。因為索引采用了索引序號復用的形式，相比指針節省了一半的索引存儲空間。又因為引入了標志位塊，有效地避免了存儲上由于按字節存儲、字節對齊等原因造成的實際占用內存遠大于變量需求空間的問題。因為多級索引的步長較小，而不必采用索引壓縮機制，從而對內存的管理方式的依賴性較小，同時路由索引的級數和索引步長可以根據路由表容量靈活設定。

6 參考文獻

[1] Gupta P， Lin S， McKeown N. Routing Lookups in Hardware at Memory Access Speeds[C]// Proceedings of INFOCOM. Mar 29-Apr 2，1998， San Francisco， CA，USA. Piscataway， NJ，USA: IEEE，1998: 1240-1247.

[2] Huang Nenfu， Zhao Shiming. A Novel IP-routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers[J]. IEEE Journal on Selected Areas in Communications， 1999，17(6): 1093-1104.

[3] Srinivasan V. Fast and Efficient Internet Lookups[D]. Washington DC，USA: Washington University， 1999.

收稿日期：2005-12-27

作 者 簡 介

閆新成，東南大學信號與信息系統碩士研究生畢業，中興通訊股份有限公司中心研究院南京研究所軟件研發工程師，主要從事3G IP網絡的研究和產品開發。