路由查找算法.ppt

并行前缀长度猜测算法——PPLS 相关技术介绍 并行技术 CIDR(无类域间路由) 最长前缀匹配 前缀扩展技术 前缀截取技术 前缀缩进 CIDR(构造超网) 特点 1.消除了传统的A,B,C类地址以及划分子网的概念 形式：IP地址={网络前缀，主机号} 2.把网络前缀都相同的连续IP地址组成一个“CIDR地址块” 最长前缀匹配 路由表的每个表项由“网络前缀”和“下一跳地址”组成。但是在查找路由表时可能会得到不止一个匹配结果。 所以，应当从匹配结果中选择具有最长网络前缀的路由，这就是最长匹配。 Bloom Filter技术 Bloom Filter技术关键技术—Hash函数技术（快速索引技术） Bloom Filter 初始状态时，Bloom Filter是一个包含M位的位数组，每一位都置0，一套事先定义好的哈希函数. 当我们往Bool filter添加元素X时，使用K个Hash函数得到K个值，并将所得结果所对应的比特数组下标的比特位置置1 判断Y是否属于这个集合时，同样的得到K个哈希值，然后判断该数组中是相应位置是否置1，都被置1了，则说明Y属于该集合，若不全为1，则它一定不在关键字集合中。所以BF只有误判，没有漏判。 PPLS算法基本思想 先用数据结构存储前缀长度的信息，当数据分组到达时，先取出它的目的IP地址，在上面的结构中猜测它的前缀长度信息。当猜测到长度信息之后，以这个长度为基准去相应的精确路由表中进行匹配，查看这个长度的路由表信息中是否确实存在该前缀。 PPLS结构 PPLS由三部分组成 长度猜测部分 Hash表部分 重新猜测部分 详细过程——建立比特数组和Hash表 (1.1).将所有IP前缀分为N组即为图中的G(i)，采用比特数组集合来存储，然后通过在每组尾部加0的方式扩展到该组所包含的最长前缀长度。 例如：将IP前缀分为4组(N=4)： 8~12 ,13~16,17~20,21~24 对于13~16需要扩展成16比特 (1.2).建造完N组比特数组后，每组用来记录相应IP前缀组的长度信息；每个前缀的长度信息就是通过截取它上面的‘M’个比特串的值，并将这些值对应的比特数组位置置1来实现的。 查表过程 2.1）例如：当一个数据包的目的IP地址为192.184.0.1，构造长度为12的前缀为101101101011/12 这N个前缀我们定义为：P(1),P(2),...P(N) 然后并行地对每个前缀p(i)按照G(i)对应的规则截取出’M’个值。为了缩进的要求，\\M个比特串必须是IP前缀的最后若干比特 则101101101011/12对应的比特数组有两个比特数组组成，拆01101011 查表过程 2.2）查找各个比特数组集合G(i)中对应比特数组相应比特位，检测各个值所对应的比特是否被置为1.若不全为1，则该IP前缀绝对不属于此时的前缀长度。 2.3）若全为1，则说明IP的前缀长度可能为此表所存在的前缀组所包含的长度，需要进一步精确匹配。 2.4）若某个比特数组集合中并不是所有的比特位都被置1.采用前缀缩进。 精确匹配 改写IP长度，形成此长度的前缀，然后建立此长度对应Hash链表时用到的Hash函数计算该前缀，以结果作为索引，去相应的Hash链表位置精确匹配。这样很快可以找到对应的链表表头，进入链表后，依次将IP前缀与链表的各个表项相匹配，如果找到了对应长度的前缀匹配项，则返回它的下一跳信息。 前缀缩进 如果是第一次缩进，则将该IP前缀的最后一个比特位置置0；第二次缩进，继续将该前缀的倒数第二位置0，以此类推。然后再返回进入比特数组集合中判断是否皆被置为1，即返回2.2 仿真 为何会采用8~26的前缀进行分析？分析如下图：可以看出在0~7和25~32的前缀分布较少，不予考虑 仿真 将IP分四组：8~12 ,13~16,17~20,21~24 各段的分配情况 仿真结果 PPLS优势 PPLS算法先进行了长度猜测，找出可能前缀长度P_len，之后再精确匹配验证。这样做摆脱了传统查找的盲目性。 (1).快捷，查找比特数组和Hash表的次数比较少而且在比特数组和Hash表的查找也都十分快捷 (2).省空间，除Hash表外，之前存储比特数组的空间是比较小的 (3).方便，简单。 * * 例如：已知IP地址128.14.35.7/20是某个CIDR地址块中的一个地址，写成二进制地址 0000111000000111 (1)前20位是网络前缀，后12位是主机号 (2)