Survey and taxonomy of IP address lookup algorithms
Survey and taxonomy of IP address lookup algorithms
复制标题
DOI：
10.1109/65.912716
复制
发表时间：
2001-03
期刊：
影响因子：
--
通讯作者：
M. A. Ruiz-Sánchez;E. Biersack;Walid Dabbous
中科院分区：
文献类型：
--
作者：
M. A. Ruiz-Sánchez;E. Biersack;Walid Dabbous
由于互联网中流量的迅速增长，通常部署了每秒几千兆位的骨干链接。为了处理每秒千兆位的交通率，骨干路由器必须能够在每个端口上每秒转发数百万个数据包。因此，路由器中使用数据包的目标地址来确定每个数据包的快速IP地址查找，因此对于达到所需的数据包转发率至关重要。 IP地址查找很困难，因为它需要最长的匹配前缀搜索。在过去的几年中，提出了针对高性能IP地址查找的各种算法。我们介绍了最先进的IP地址查找算法的调查，并在查找速度，可扩展性和更新开销方面进行比较。
Due to the rapid growth of traffic in the Internet, backbone links of several gigabits per second are commonly deployed. To handle gigabit-per-second traffic rates, the backbone routers must be able to forward millions of packets per second on each of their ports. Fast IP address lookup in the routers, which uses the packet's destination address to determine for each packet the next hop, is therefore crucial to achieve the packet forwarding rates required. IP address lookup is difficult because it requires a longest matching prefix search. In the last couple of years, various algorithms for high-performance IP address lookup have been proposed. We present a survey of state-of-the-art IP address lookup algorithms and compare their performance in terms of lookup speed, scalability, and update overhead.