首先，題目中說是路由項(xiàng)定位結(jié)構(gòu)而非查找結(jié)構(gòu)，說的是，使用這個(gè)結(jié)構(gòu)，以一個(gè)IPv4地址作為輸入的時(shí)候，在得到下一跳的過程中，將不會(huì)有任何的查找操作，僅僅不斷使用索引定位就可以了。為了先有一個(gè)直觀上的認(rèn)識(shí)，先給出查找結(jié)構(gòu)圖： 

1.先從多級(jí)索引說起

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

如果使用多級(jí)表，也還可以。但是有更優(yōu)化的方式，因?yàn)槟銜?huì)看到，這么多表中，很多內(nèi)容都是重復(fù)的，我們需要的是，再引入一些表，壓縮掉這些重復(fù)的數(shù)據(jù)。

2.再談DxR算法

我終于可以在本文中給出一個(gè)DxR的真實(shí)結(jié)構(gòu)而不僅僅是一個(gè)思想。如下圖所示：

關(guān)于它，我要說的就是那個(gè)“如果”，事實(shí)上，就剩下這一步了。只要能找出一個(gè)辦法快速索引到區(qū)間idx，問題就結(jié)了。#p#

3.直觀的設(shè)想

依然保持二級(jí)結(jié)構(gòu)，然而我需要想辦法壓縮N張二級(jí)表。壓縮到多少算好呢?于是狠一點(diǎn)，就死死地保持1張!至于怎么做?再想!

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

必須明白一個(gè)事實(shí)，即我知道一級(jí)表中點(diǎn)區(qū)間的數(shù)量和位置。位置可以通過一級(jí)索引在預(yù)處理時(shí)定位，數(shù)量可以在預(yù)處理時(shí)數(shù)出來。

這個(gè)事實(shí)至關(guān)重要，為此，我將一級(jí)索引表中所有的點(diǎn)區(qū)間進(jìn)行順序編號(hào)，并將這個(gè)號(hào)保存在點(diǎn)區(qū)間對(duì)應(yīng)的索引項(xiàng)中。在明白了這個(gè)事實(shí)之后，接下來我在想如何利 用它，此時(shí)另一個(gè)事實(shí)也逐漸呈現(xiàn)，即二級(jí)表只有1個(gè)，而對(duì)于所有的一級(jí)表索引的每一個(gè)點(diǎn)區(qū)間而言，對(duì)應(yīng)的低16位二級(jí)表空間同樣都是從從0到65535的 地址子空間。

那么現(xiàn)在的問題就是，如何將其區(qū)分開來，這個(gè)時(shí)候，剛剛認(rèn)識(shí)到的第一個(gè)事實(shí)就有用了。對(duì)!就是用一級(jí)表索引的點(diǎn)區(qū)間編號(hào)來索引二級(jí)表索引到的那個(gè)表，這個(gè)表很顯然就是區(qū)間下一跳關(guān)聯(lián)表。總體示意圖如下：

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

4.低區(qū)間的分割方式

從現(xiàn)在開始，我將路由表說成是轉(zhuǎn)發(fā)表。因?yàn)槁酚杀斫?jīng)過預(yù)處理已經(jīng)完全變成轉(zhuǎn)發(fā)表了。

此時(shí)，如果我能給出轉(zhuǎn)發(fā)表預(yù)處理中最關(guān)鍵的一步，即低區(qū)間的分割方式，那么就幾乎可以構(gòu)建轉(zhuǎn)發(fā)表了。構(gòu)建過程如下圖所示

之 所以需要如此構(gòu)建是因?yàn)槲抑挥幸粋€(gè)二級(jí)低區(qū)間表，由于對(duì)于不同的一級(jí)點(diǎn)區(qū)間，低區(qū)間無論從數(shù)量還是分布上看都是不同的，也就是說，每一個(gè)一級(jí)點(diǎn)區(qū)間都有自 己獨(dú)立的低區(qū)間，這樣一來就根本沒有辦法用唯一的一張低區(qū)間表來索引多個(gè)一級(jí)點(diǎn)區(qū)間引申出來的低區(qū)間，因此，我必須將所有這些獨(dú)立的低區(qū)間集合映射到同一 個(gè)16bit域上，而映射的過程就是上圖所示的過程!這個(gè)過程用文字描述如下：

1).所有M個(gè)一級(jí)點(diǎn)區(qū)間對(duì)應(yīng)的低區(qū)間分割點(diǎn)元素放入一個(gè)集合S中;

2).將這個(gè)集合S進(jìn)行排序，去掉重復(fù)點(diǎn)元素，此時(shí)S中元素個(gè)數(shù)為N;

3).構(gòu)建N張關(guān)聯(lián)表，每張關(guān)聯(lián)表n的元素按照一級(jí)點(diǎn)區(qū)間索引順序排列，其中下一跳索引要么使用自己在低區(qū)間合并前保存的-該分割點(diǎn)為該低區(qū)間固有，要么繼承關(guān)聯(lián)表n-1的對(duì)應(yīng)下標(biāo)處的下一跳-該分割點(diǎn)乃為了統(tǒng)一映射而硬放進(jìn)來的。

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

DxR思想：一級(jí)點(diǎn)區(qū)間對(duì)應(yīng)的所有二級(jí)低區(qū)間分別排列，由于所有低區(qū)間都在同一個(gè)16bit域上，它們中間有可能出現(xiàn)嚴(yán)重?cái)?shù)據(jù)冗余，DxR算法無法發(fā)現(xiàn)這一點(diǎn);

低區(qū)間合并思想：一級(jí)點(diǎn)區(qū)間對(duì)應(yīng)的所有二級(jí)低區(qū)間統(tǒng)一排列，因此可以去除冗余數(shù)據(jù)，比如1.2.3.0/24和2.2.3.0/24的低區(qū)間分割點(diǎn)都有3.0/8，它們顯然可以合并，但是也可能將一個(gè)大區(qū)間拆分成多個(gè)小的...

我們來舉一個(gè)例子，有下列4個(gè)一級(jí)點(diǎn)區(qū)間對(duì)應(yīng)的低區(qū)間分割點(diǎn)序列：

點(diǎn)區(qū)間1：0,1,3,4,7,8,16,32

點(diǎn)區(qū)間2：0,3,7,8,20,25,32

點(diǎn)區(qū)間3：0,2,4,24,32

點(diǎn)區(qū)間4：0,7,16,32

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

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

可見，消除了很多冗余區(qū)間分割點(diǎn)，但是對(duì)于所有點(diǎn)區(qū)間，它都將一些低區(qū)間劈開成了完全相同的兩個(gè)，當(dāng)然，下一跳也完全相同...這就是代價(jià)，不多的代價(jià)，但是必須付出的代價(jià)。#p#

5.我的下一跳定位結(jié)構(gòu)

筆不多墨，火車上不啰嗦，關(guān)鍵是流量不穩(wěn)定，只能離線寫。事實(shí)上是目前移動(dòng)IP做的太垃圾，高鐵快速移動(dòng)的時(shí)候，不能保證應(yīng)用層不中斷，MLXGB，于是就少說，慎獨(dú)?Oh，NO!

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

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

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

我的算法中，使用了一個(gè)唯一的二級(jí)索引表，大小固定64k，而關(guān)聯(lián)表數(shù)量不固定，關(guān)聯(lián)表的數(shù)量為合并后的低區(qū)間數(shù)量，而每一個(gè)關(guān)聯(lián)表的大小為一級(jí)索引表點(diǎn)區(qū)間的數(shù)量，計(jì)算公式為：

a,b,c,...x這M個(gè)低區(qū)間合并后的新區(qū)間1的M個(gè)元素?cái)?shù)組+a,b,c,...x這M個(gè)低區(qū)間合并后的新區(qū)間2的M個(gè)元素?cái)?shù)組....+a,b,c,...x這M個(gè)低區(qū)間合并后的新區(qū)間N的M個(gè)元素?cái)?shù)組

寫了個(gè)Python腳本，計(jì)算結(jié)果，發(fā)現(xiàn)我的方案在大多數(shù)路由項(xiàng)均勻排布情況下，比DxR占用空間更小...爆炸!這個(gè)實(shí)際的工作促進(jìn)了我對(duì)Python的學(xué)習(xí)。

6.轉(zhuǎn)發(fā)表和路由表

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

在Linux中，路由表就是轉(zhuǎn)發(fā)表，每一個(gè)數(shù)據(jù)包都要去查詢這個(gè)表(別扯路由Cache，目前已經(jīng)被cut了，why?因?yàn)榭紤]到應(yīng)用的多樣性，特別是P2P環(huán)境下，數(shù)據(jù)包的時(shí)間局部性特性已經(jīng)不再是一個(gè)前提，so，....)，這就會(huì)帶來一個(gè)問題...路由表存儲(chǔ)的是前綴-下一跳映射，而數(shù)據(jù)包要完成 是找到這么一個(gè)路由項(xiàng)，因此就需要進(jìn)行一系列的查找過程...

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

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

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

7.非要16-16分割嗎?

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

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

1).離線統(tǒng)計(jì)，作為2bit數(shù)據(jù)設(shè)置的依據(jù)

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

2).設(shè)置DxR區(qū)間表

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

3).設(shè)置一級(jí)索引bit長度

將m個(gè)路由項(xiàng)的最長長度前綴的長度值作為一級(jí)索引的長度，以保證這些路由項(xiàng)的下一跳可以在最少的CPU周期內(nèi)直接被一級(jí)索引表項(xiàng)定位到。

4).設(shè)置二級(jí)低區(qū)間

剩下的所有路由項(xiàng)采用我的辦法進(jìn)行二級(jí)定位。

8.結(jié)束

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

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

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

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

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