Faster IP lookups using controlled prefix expansion
Faster IP lookups using controlled prefix expansion
复制标题
DOI：
10.1145/277851.277863
复制
发表时间：
1998-06
期刊：
影响因子：
--
通讯作者：
V. Srinivasan;G. Varghese
中科院分区：
文献类型：
--
作者：
V. Srinivasan;G. Varghese
Internet（IP）地址查找是高性能路由器中的主要瓶颈。 IP地址查找具有挑战性，因为它需要最长的匹配前缀查找。它通过增加路由表尺寸，增加流量，更高的速度链接以及迁移到128位IPv6地址而加重了它。我们描述了如何使用称为受控前缀扩展的新技术更快地制作IP查找。受控前缀扩展以及基于动态编程的优化技术可用于将最著名的IP查找算法的速度提高至少两个。当应用于Trie搜索时，我们的技术提供了一系列可以调整性能的算法。例如，使用1 MB的L2高速缓存，可以在最坏的情况下，对MAEEAST数据库进行38,000个前缀的搜索，在最坏的情况下，搜索时间为181 NSEC，最坏的情况插入/删除时间为2.5毫秒，平均插入时间/删除时间/删除时间4个USEC。我们的实际实验使用了512 kb L2缓存，获得了226 NSEC的最差案例搜索时间，最差的情况最差的情况插入/删除时间为2.5毫秒，平均插入/删除时间为4 USEC。我们还描述了如何使用我们的技术来提高前缀长度上的二进制搜索速度，以为IPv6提供可扩展的解决方案。我们的算法设计方法是基于使用五角星上的VTune工具来获得动态时钟周期计数的测量值。
Internet (IP) address lookup is a major bottleneck in high performance routers. IP address lookup is challenging because it requires a longest matching prefix lookup. It is compounded by increasing routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. We describe how IP lookups can be made faster using a new technique called controlled prefix expansion. Controlled prefix expansion, together with optimization techniques based on dynamic programming, can be used to improve the speed of the best known IP lookup algorithms by at least a factor of two. When applied to trie search, our techniques provide a range of algorithms whose performance can be tuned. For example, with 1 MB of L2 cache, trie search of the MaeEast database with 38,000 prefixes can be done in a worst case search time of 181 nsec, a worst case insert/delete time of 2.5 msec, and an average insert/delete time of 4 usec. Our actual experiments used 512 KB L2 cache to obtain a worst-case search time of 226 nsec, a worst-case worst case insert/delete time of 2.5 msec and an average insert/delete time of 4 usec. We also describe how our techniques can be used to improve the speed of binary search on prefix lengths to provide a scalable solution for IPv6. Our approach to algorithm design is based on measurements using the VTune tool on a Pentium to obtain dynamic clock cycle counts.