以DxR算法思想为基准设计出的路由项定位结构图解

首先,题目中说是路由项定位结构而非查找结构,说的是,使用这个结构,以一个IPv4地址作为输入的时候,在得到下一跳的过程中,将不会有任何的查找操作,仅仅不断使用索引定位就可以了。为了先有一个直观上的认识,先给出查找结构图:

1.先从多级索引说起在我的那次失败经历中,,我企图完全模仿MMU来设计路由查找结构,结果失败了。其实现在想想,也不失败,因为路由项的数目毕竟是有限的,对于整个4G个IPv4地址来讲,它的数量可以忽略。因此还是可以使用多级索引的。以16-16二级分割,效果也还不错,构建和查找结构理解起来都不难。但是我们计算一下它的内存占用,64k的一级索引表是必须的,根据前缀长度大于16的路由项的数目N,分裂出N个64k的二级表项,然后就结束了,一共N+1个64k的表项,一级索引指向二级表的地址,起码要4字节,二级表项可以指向一个下一跳表的索引,鉴于直连下一跳的数量不会超过256,1字节足够。 如果使用多级表,也还可以。但是有更优化的方式,因为你会看到,这么多表中,很多内容都是重复的,我们需要的是,再引入一些表,压缩掉这些重复的数据。2.再谈DxR算法

我终于可以在本文中给出一个DxR的真实结构而不仅仅是一个思想。如下图所示:

关于它,我要说的就是那个“如果”,事实上,就剩下这一步了。只要能找出一个办法快速索引到区间idx,问题就结了。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

可见,消除了很多冗余区间分割点,但是对于所有点区间,它都将一些低区间劈开成了完全相同的两个,当然,下一跳也完全相同…这就是代价,不多的代价,但是必须付出的代价。

5.我的下一跳定位结构笔不多墨,火车上不啰嗦,关键是流量不稳定,只能离线写。事实上是目前移动IP做的太垃圾,高铁快速移动的时候,不能保证应用层不中断,MLXGB,于是就少说,慎独?Oh,NO!

力微休负重,言轻莫劝人。

以DxR算法思想为基准设计出的路由项定位结构图解

相关文章:

你感兴趣的文章:

标签云: