《路由器原理与设计——高速IP查表算法》
在现代网络通信中，路由器扮演着至关重要的角色，其核心功能之一就是高效地进行IP路由查找，确保数据包能够准确无误地传输到目的地。本教程主要探讨了如何在硬件级别实现高速IP查表算法，以达到与内存访问速度相匹配的查找效率。
高速IP查表算法的设计目标是简化硬件实现，每次查表只需要一次内存访问。这是因为频繁的内存访问会显著影响路由器的性能，尤其是在处理海量数据包的网络核心节点。理想的算法应尽量减少访问次数，且即使需要多次访问，概率也应极低，通常限制在2次或3次以内。此外，数据分散存储在不同的物理存储器中，有利于流水线操作，同时控制表的更新开销也要尽可能小。
该算法的假设基于存储器价格低廉，且路由前缀长度分布具有特定特性。例如，在核心路由器中，超过24位的路由前缀非常少。为此，提出了DIR-24-8-BASIC算法，它包含两个主要的查找表：TBL24用于存储前缀长度小于等于24的路由信息，而TBLlong则存储超过24位的前缀信息。
TBL24的工作原理是将前缀扩展，如128.23/16会被扩展为256个条目，分别对应128.23.0至128.23.255，所有这些条目指向同一转发信息。查表过程首先使用IP地址的高24位在TBL24中查找，根据返回数据决定是否需要进一步在TBLlong中查找。
DIR-24-8-BASIC算法的优点在于大部分情况下只需一次内存访问，对于主要的24位以下前缀长度，可以支持无限数量的前缀，并且只需要3MB的存储空间。然而，它的缺点也很明显，包括低存储利用率、复杂的表项更新以及对超过24位前缀的支持有限。
为了优化这个算法，提出了DIR-24-8-INT，引入了第三级表TBLint来指示扩展表的大小，以及多级表结构，通过增加访存次数来降低存储开销。这种方法允许更灵活的表结构设计，以适应更广泛的路由前缀长度。
然而，随着网络规模的扩大，表更新问题变得复杂，尤其是处理"洞"结构（未分配的连续表项）时。为了解决这个问题，可以采用软件计算更新范围并触发硬件批量更新的方法，如Row update和Subrange update，它们可以在减少软件开销的同时提高更新效率。
总结起来，高速IP查表算法是路由器设计中的关键技术，通过巧妙的算法设计和硬件优化，可以在保证查找速度的同时，有效地管理和更新庞大的路由表，以满足不断增长的网络需求。
VIP享7折，此内容立减5.97元 
