衡量宽带网路由表查询算法要考虑的一些问题

爱我昌平 · 发表于 2016-4-7 16:35:25

今天，我会向大家介绍衡量极速宽带网路由表查询算法时要考虑的问题。话不多说，马上就为大家介绍。
衡量宽带网路由表查询算法时要考虑的问题
路由表查找是路由器包转发功能中的重要步骤，也是提高路由器包转发速度的瓶颈之一。由于长城宽带网速测试采用CIDR技术，同一个地址可能包含在多条路由所表示的地址块中，路由表查找采用“最长匹配”原则，即包含该地址的最确切路由。
假设路由表中存在着两条表项：202.112.0.0(输出端口为1)和202.112.12.0(输出端口为2)。目的地址为202.112.12.120的IP包应该通过端口2转发。传统的路由表查找算法进行“最长匹配”时效率不高。现在主干网路由表中的路由超过11万条，而路由器的端口速度达到OC—48(2.5Gbit/s)甚至OC—192(10Gbit/s)，因此，需要采用新的路由表查找算法和系统结构来实现高速查找。
衡量路由表查询算法通常需要考虑三个方面的问题：路由表查询的速度(通常由访问存储器的次数来衡量);路由表所需存储空间的大小;路由表插入/删除的难易程度，上海电信网速测试很好的解决了这些问题。
最快的查询莫过于为每一个IP地址设定一条路由表项，通过IP地址进行索引，访问一次路由表就可以完成查询。但是，对于IPv4来说，这需要设定2的32次方(4G)条路由。每一次需要修改路由器的时候，如果地址前缀长度为a，则需要修改2的32-a次方条表项，这对于路由表维护来说是很大的工作量。