ipv6路由器存储多个路由作为n地址的第一位.2000年,研究人员在1500条ipv6路线中发现只有14种不同的前缀长度.传入数据包根据最长前缀匹配路由到不同的传出端口,因此如果数据包x的前8位与8位路由匹配,但同一数据包的前48位与48位路由匹配,则路由器必须选择48位路线.
我的路由器正在处理如此多的数据包,因此查找路由表的内存速度是一个限制因素.在路由表中找到最长匹配前缀的好算法是什么？
使用trie或基数树来存储"标准"前缀.后缀树/数组是不必要的过度杀戮; 它们用于查找中缀之间的匹配(使用任何中缀是后缀的前缀,如果要在多个字符串之间找到匹配,将它们相互连接),而不仅仅是在前缀之间.
京公网安备 11010802040832号 | 京ICP备19059560号-6 