首先，題目中說是路由項定位結構而非查找結構，說的是，使用這個結構，以一個IPv4地址作為輸入的時候，在得到下一跳的過程中，將不會有任何的查找操作，僅僅不斷使用索引定位就可以了。為了先有一個直觀上的認識，先給出查找結構圖： 

1.先從多級索引說起

在 我的那次失敗經歷中，我企圖完全模仿MMU來設計路由查找結構，結果失敗了。其實現在想想，也不失敗，因為路由項的數目畢竟是有限的，對于整個4G個 IPv4地址來講，它的數量可以忽略。因此還是可以使用多級索引的。以16-16二級分割，效果也還不錯，構建和查找結構理解起來都不難。但是我們計算一 下它的內存占用，64k的一級索引表是必須的，根據前綴長度大于16的路由項的數目N，分裂出N個64k的二級表項，然后就結束了，一共N+1個64k的 表項，一級索引指向二級表的地址，起碼要4字節，二級表項可以指向一個下一跳表的索引，鑒于直連下一跳的數量不會超過256，1字節足夠。

如果使用多級表，也還可以。但是有更優化的方式，因為你會看到，這么多表中，很多內容都是重復的，我們需要的是，再引入一些表，壓縮掉這些重復的數據。

2.再談DxR算法

我終于可以在本文中給出一個DxR的真實結構而不僅僅是一個思想。如下圖所示：

關于它，我要說的就是那個“如果”，事實上，就剩下這一步了。只要能找出一個辦法快速索引到區間idx，問題就結了。#p#

3.直觀的設想

依然保持二級結構，然而我需要想辦法壓縮N張二級表。壓縮到多少算好呢?于是狠一點，就死死地保持1張!至于怎么做?再想!

既然只有1張二級表，就要想辦法將之前的N張二級表的內容壓縮到一個位置，即另外一組表。

必須明白一個事實，即我知道一級表中點區間的數量和位置。位置可以通過一級索引在預處理時定位，數量可以在預處理時數出來。

這個事實至關重要，為此，我將一級索引表中所有的點區間進行順序編號，并將這個號保存在點區間對應的索引項中。在明白了這個事實之后，接下來我在想如何利 用它，此時另一個事實也逐漸呈現，即二級表只有1個，而對于所有的一級表索引的每一個點區間而言，對應的低16位二級表空間同樣都是從從0到65535的 地址子空間。

那么現在的問題就是，如何將其區分開來，這個時候，剛剛認識到的第一個事實就有用了。對!就是用一級表索引的點區間編號來索引二級表索引到的那個表，這個表很顯然就是區間下一跳關聯表?？傮w示意圖如下：

可見，享用數組下標尋址的終極的目標就是，將稀疏的變成密集的，如果不能，就要引入額外的表用來提取共享數據。

4.低區間的分割方式

從現在開始，我將路由表說成是轉發表。因為路由表經過預處理已經完全變成轉發表了。

此時，如果我能給出轉發表預處理中最關鍵的一步，即低區間的分割方式，那么就幾乎可以構建轉發表了。構建過程如下圖所示

之 所以需要如此構建是因為我只有一個二級低區間表，由于對于不同的一級點區間，低區間無論從數量還是分布上看都是不同的，也就是說，每一個一級點區間都有自 己獨立的低區間，這樣一來就根本沒有辦法用唯一的一張低區間表來索引多個一級點區間引申出來的低區間，因此，我必須將所有這些獨立的低區間集合映射到同一 個16bit域上，而映射的過程就是上圖所示的過程!這個過程用文字描述如下：

1).所有M個一級點區間對應的低區間分割點元素放入一個集合S中;

2).將這個集合S進行排序，去掉重復點元素，此時S中元素個數為N;

3).構建N張關聯表，每張關聯表n的元素按照一級點區間索引順序排列，其中下一跳索引要么使用自己在低區間合并前保存的-該分割點為該低區間固有，要么繼承關聯表n-1的對應下標處的下一跳-該分割點乃為了統一映射而硬放進來的。

到此，我們可以比較一下DxR的思想和我的低區間合并思想了。

DxR思想：一級點區間對應的所有二級低區間分別排列，由于所有低區間都在同一個16bit域上，它們中間有可能出現嚴重數據冗余，DxR算法無法發現這一點;

低區間合并思想：一級點區間對應的所有二級低區間統一排列，因此可以去除冗余數據，比如1.2.3.0/24和2.2.3.0/24的低區間分割點都有3.0/8，它們顯然可以合并，但是也可能將一個大區間拆分成多個小的...

我們來舉一個例子，有下列4個一級點區間對應的低區間分割點序列：

點區間1：0,1,3,4,7,8,16,32

點區間2：0,3,7,8,20,25,32

點區間3：0,2,4,24,32

點區間4：0,7,16,32

對于DxR算法，很顯然在區間表中會將上述分割點全部寫下：0,1,3,4,7,8,16,32|0,3,7,8,20,25,32|0,2,4,24,32|0,7,16,32

而在低區間合并法中，合并后的區間為：0,1,2,3,4,7,8,16,20,24,25,32

可見，消除了很多冗余區間分割點，但是對于所有點區間，它都將一些低區間劈開成了完全相同的兩個，當然，下一跳也完全相同...這就是代價，不多的代價，但是必須付出的代價。#p#

5.我的下一跳定位結構

筆不多墨，火車上不啰嗦，關鍵是流量不穩定，只能離線寫。事實上是目前移動IP做的太垃圾，高鐵快速移動的時候，不能保證應用層不中斷，MLXGB，于是就少說，慎獨?Oh，NO!

我這玩意兒到底有多好，我要說它起碼拒絕了所有的查找操作，它只是單純的定位!但是它是不是用龐大且高尚的空間換了可恥的時間呢?oh，NO!現在讓我們看一下DxR算法的內存占用，這個圖來自http://www.nxlab.fer.hr/dxr/。

以16-16分割為例，它的區間表占用量幾乎是64k的3-4倍，只要我能證明我的數據結構中二級表和關聯表的內存占用量總和也是這個數量級的，我就贏了(之前華為有家伙寫過一篇論文，使用并推崇了多級索引算法設計轉發表，但是我不屑于這種方案，隨便算一下DxR或者我的方案的空間復雜度，就會發現即便華為的人也不是不可及的...國內很多論文總是有欺世盜名之嫌疑，旋轉升降座椅一定會爆炸，等著吧)。我贏的前提是，我沒有使用任何“算法”，我只是基于索 引定位!然而，我也并沒有因此使用更多的內存!

在DxR算法中，區間表的數量為所有一級索引表中點區間分割的二級區間的總和，其實我完全可以用西格瑪符號寫個算式的，但是需要截圖，就算了。所以我用文 字表示：一級點區間1的a個元素低區間數組+點區間2的b個元素低區間數組+點區間3的c個元素低區間數組...+點區間M的x個元素低區間數組

我的算法中，使用了一個唯一的二級索引表，大小固定64k，而關聯表數量不固定，關聯表的數量為合并后的低區間數量，而每一個關聯表的大小為一級索引表點區間的數量，計算公式為：

a,b,c,...x這M個低區間合并后的新區間1的M個元素數組+a,b,c,...x這M個低區間合并后的新區間2的M個元素數組....+a,b,c,...x這M個低區間合并后的新區間N的M個元素數組

寫了個Python腳本，計算結果，發現我的方案在大多數路由項均勻排布情況下，比DxR占用空間更小...爆炸!這個實際的工作促進了我對Python的學習。

6.轉發表和路由表

這個小節本來我想寫一篇完整的文章的，但是現在在高鐵上，怕旁座的人嘲笑我(其實按照概率算，80%的人都不知道我在寫什么...)，就只能把它寫成項目報告的形式了，爆炸!

在Linux中，路由表就是轉發表，每一個數據包都要去查詢這個表(別扯路由Cache，目前已經被cut了，why?因為考慮到應用的多樣性，特別是P2P環境下，數據包的時間局部性特性已經不再是一個前提，so，....)，這就會帶來一個問題...路由表存儲的是前綴-下一跳映射，而數據包要完成 是找到這么一個路由項，因此就需要進行一系列的查找過程...

為什么不對路由項進行一系列預處理呢?結果就是讓一個IP地址直接找到下一跳!我在想我如果能建立一張表，能讓一個IP地址能以“最快的速度”映射到下一 跳，那么我就足以月薪還貸養女無壓力了....但是，我錯了，因為這是一個傻逼都能想出的思路。我只是把它描述了一下而已，不過如果要是能早出生30年， 現在應該已經是一個爺爺了...

“以最快的速度”直接找到下一跳，有兩種方式，第一就是在空間占有有嚴格要求的苛刻環境下使用更高效的算法，第二種方式就是用大量的空間節省寶貴的時間，但是我的方案是，用稍微的一點空間占用完全索引化路由定位!

路由表是什么?是協議棧IP層控制平面的內容。轉發表是什么?是協議棧IP層數據平面的內容。理解了這個區別，你就可以用最大的可能性優化轉發表，即便路 由表的數據結構是如此的固定。換句話說，路由表需要更高的效率進行增，刪，更新操作，而轉發表則需要更高的效率進行查詢操作。路由表在穩定的時候，可以 “慢慢地”轉化為轉發表。Linux并沒有區分路由表和轉發表(別把Linux的路由cache理解成轉發表)，這是一個通用操作系統內核協議棧的通用做 法，而不是專業路由器操作系統的做法，因為，專業路由器的操作系統內核協議棧往往只注重控制平面和管理平面，而數據平面的操作則完全不在操作系統協議棧里 面完成，而是專門的硬件或者軟件子系統來完成的，控制平面和管理平面控制和管理的是什么?是數據平面!#p#

7.非要16-16分割嗎?

雖 然我在上面一直都是使用一二級索引表的16bit-16bit分割，就好像一定要這樣才可以，事實上不是這樣的。畢竟我的一部分思想來自DxR，另一部分 來自區間位圖匹配，還有一部分來自MMU，不管這些中的哪個，都沒有固定一級索引的長度，區間位圖索引實際上也不一定非要固定長度索引。

一級索引長度可以根據路由項的分布以及CPU Cache Line情況具體情況具體分析，比如說，如果路由項中有大量的16-20前綴長度的路由項，那么完全可以使用20bit的一級索引，因為這樣可以減少二級 低區間合并后的數量。甚至，還可以更加靈活一點，一級索引表中額外使用2bit數據，00指示一級索引直接索引下一跳，01指示一級索引的作用是索引低區 間，10指示一級索引用來定位DxR區間表的start和end，也就是說使用DxR的算法，我的最初想法是采用下面的序列動態變換一級索引表項的那 2bit數據：

1).離線統計，作為2bit數據設置的依據

基于一段時間作離線統計，得到路由項命中最不經常(它們只是平添了 二級低區間的分割數量)最不絕對(意味著這些路由項沒有時間局部性，延遲可容忍)且前綴分布最散列(分布太散，意味著二級低區間將因為這些路由項被分割成 數量巨大的小塊)的前K個路由項(涉及到KD樹算法)。這三個指標可以加權取平均，權值自定義。同時統計出上述三個指標的另一端極致，取D個路由項，統計 出D個中前綴長度依次從小到大排列的m個路由項。

2).設置DxR區間表

將這K個路由項的一級索引的2bit指示位設置成10，并設置DxR區間表。既然這K個路由項最不經常使用且碎片化而且在很大概率上是可以容忍延遲的，那么就讓它們慢慢被二分檢索吧，不會增加由于二級低區間的過度切割帶來的內存用量遞增。

3).設置一級索引bit長度

將m個路由項的最長長度前綴的長度值作為一級索引的長度，以保證這些路由項的下一跳可以在最少的CPU周期內直接被一級索引表項定位到。

4).設置二級低區間

剩下的所有路由項采用我的辦法進行二級定位。

8.結束

這 篇文章沒有什么技術含量和技術門檻，但是卻占用了我很多的時間。這個想法很久以前就縈繞在老濕心里了。那得從一次不賺一分錢的私活兒說起，純粹是幫 忙...在物聯網時代，仿佛一切又回到了20年前從新開始，內存苛刻，延遲不能容忍...自然路由子系統也逐步不再只是高大上的核心網管理員才能碰觸的圣 物，我也不能再僅僅局限于能看懂講明白甚至移植或者寫出Linux內核的那套算法了，不管是HASH還是LC-Trie...我要找的是一個忽略時間復雜 度的定位結構，而不是一個查找結構，注意，是找而不是設計。然而這不可避免的會遇到空間復雜度的問題...恰恰是華為的人幫我理清了思路，雖然不管怎么 說，他的方法我不敢恭維...

雖然構思了很久，但是一直沒有動筆，直到聽說本周要來京出差，我想這次應該可以擠出一些時間了，從來京的高鐵上開始，工作結束后到酒店開始畫圖，整理思 路，終于有了一點邏輯，然后手寫了一個預處理好的測試結構程序，注意，難點在預處理，我不想花太多的精力寫這個預處理程序，因為這不可避免要碰到排序，二 叉樹，路徑壓縮樹，統計，KD樹，消除重復項，尋找接近點等問題，這些過程都很簡單，程序算法也能在各種面試寶典上找到，我想當我debug的時候，肯定 又會去baidu，連goolge都不用，所以我假設這些預處理都已經做好了，我只需要做一個索引即可，而這個程序只有不到200行代碼，大概去掉打印# 號也就150行左右吧...數據使用了DxR的測試數據，加入了100k到500k左右的路由項，這已經是核心路由器的數量級了，測試下來，真的碉堡了 DxR，至于毫不區分路由表和轉發表的Linux協議棧IP路由算法，我就不描述它的慘象了。只能說還行吧，確實還行，沾了點邊。

這篇文章算是寫完了，北京今天天氣不錯，藍藍的天沒有云，明天又是新的一天，又有新的任務，踏上新的征途，感覺像是又一個2012/2013年要來了，在 那個初期我在地獄接著爬上山腰的項目中我鍛煉了自身，學到了很多，但是卻依然沒有達到山頂，可以旋轉360度俯視野草的境界(其實野草我是看不見的，看見 的只是云...)，于是又有了希望，不管是設計一個新東西，還是繼續SP，對于一個1983年出生的程序員中的網管，網管中的程序員，比較能扯歷史，拘謹 又無畏，養女又還貸的IT技術男而言，接下來還有多少機會呢?我是一個平凡的人，雖然也曾經像每一個有夢想且自戀的技術宅男一樣覺得自己是偉大且不自信 的。平凡的人不會創造歷史，歷史是英雄創造的，但是平凡的人是幸福的。人人為我，我為人人，我們都是平凡的人。最后用一段我對一件真實且平凡的事件的評價徹底結束本文：

知道什么叫學習和傳道嗎?今天和同事在出租車上聊起了古希臘馬拉松的起源，出租車司機也參與了進來，他說起了古希臘有個人計算了地 球的周長，自以為精通希臘的我雖知道算法但竟然不知道這人叫什么，司機說此人名字很長，但他也記不清了，...于是到酒店后趕緊把那個人相關的時代和背景 復習了一下...現在我知道他叫埃拉托克尼(這個名字對于我而言，真心不算長)....事實上，我也教了司機一件他不知道的 事情，那就是旋轉升降座椅會爆炸，并baidu了圖片給他看...無論是誰，都可以是自己的老濕...他可能是的哥，三輪車夫，送快遞外賣的，甚至飯店服 務員，然則你也要教他一件事作為回報，比如座椅爆炸...這就是基督教真諦，人人為我，我為人人。我媽信教，不知不覺，我也信了....爆炸如果我能本著 宣傳座椅爆炸的精神和能力宣傳公司的產品和技術，促進和別家的互補合作，促進產品的完善，那將會一幅多么美麗的畫卷...爆炸!

原文地址：http://dog250.blog.51cto.com/2466061/1623638