首要，题目中说是路由项定位结构而非查找结构，说的是，运用这个结构，以一个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的 地址子空间。

那么现在的问题便是，怎么将其差异开来，这个时分，刚刚知道到的榜首个现实就有用了。对!便是用一级表索引的点区间编号来索引二级表索引到的那个表，这个表很明显便是区间下一跳相关表。整体示意图如下：

可见，享受数组下标寻址的终极的方针便是，将稀少的变成密布的，假如不能，就要引进额定的表用来提取同享数据。

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