Scalable high speed IP routing lookups
Scalable high speed IP routing lookups
复制标题
DOI：
10.1145/263105.263136
复制
发表时间：
1997-10
期刊：
影响因子：
--
通讯作者：
M. Waldvogel;G. Varghese;J. Turner;B. Plattner
中科院分区：
文献类型：
--
作者：
M. Waldvogel;G. Varghese;J. Turner;B. Plattner
Internet地址查找是一个具有挑战性的问题，因为路由台的大小增加，流量增加，更高的速度链接以及迁移到128位IPv6地址。 IP路由查找需要计算最佳匹配前缀，对于诸如哈希（Hashhing）之类的标准解决方案是不适用的。我们知道的最好的解决方案是BSD Radix尝试，随着IP移动到128位地址时，缩放很差。我们的论文描述了一种新的算法，该算法使用前缀长度组织的哈希表上的二进制搜索，用于最佳匹配前缀。我们的方案量表非常恰当，因为地址和路由表的大小增加：独立于表尺寸，它需要log2（地址位）哈希查找的最差时间。因此，对于IPv6，IPv4和7只需要5个哈希查找。我们还介绍了突变的二进制搜索和其他优化，对于具有超过33,000个条目的典型IPv4骨干路由器，大大将平均哈希数量减少到少于2，其中一个可以简化为索引阵列访问。我们预计IPv6的平均案例行为相似。
Internet address lookup is a challenging problem because of increasing routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. IP routing lookup requires computing the best matching prefix, for which standard solutions like hashing were believed to be inapplicable. The best existing solution we know of, BSD radix tries, scales badly as IP moves to 128 bit addresses. Our paper describes a new algorithm for best matching prefix using binary search on hash tables organized by prefix lengths. Our scheme scales very well as address and routing table sizes increase: independent of the table size, it requires a worst case time of log2(address bits) hash lookups. Thus only 5 hash lookups are needed for IPv4 and 7 for IPv6. We also introduce Mutating Binary Search and other optimizations that, for a typical IPv4 backbone router with over 33,000 entries, considerably reduce the average number of hashes to less than 2, of which one hash can be simplified to an indexed array access. We expect similar average case behavior for IPv6.