Guarantee IP lookup performance with FIB explosion
Guarantee IP lookup performance with FIB explosion
复制标题
DOI：
10.1145/2740070.2626297
复制
发表时间：
2014-08
影响因子：
2.8
通讯作者：
Tong Yang;Gaogang Xie;Yanbiao Li;Qiaobin Fu;A. Liu;Qi Li;L. Mathy
中科院分区：
文献类型：
--
作者：
Tong Yang;Gaogang Xie;Yanbiao Li;Qiaobin Fu;A. Liu;Qi Li;L. Mathy
骨干路由器的转发信息库（FIB）的规模一直在快速增长。理想的 IP 查找算法应该实现恒定但较小的 IP 查找时间和片上内存使用。然而，现有的IP查找算法还没有同时满足这两个要求。在本文中，我们首先提出 SAIL，一种 IP 查找的分割方法。一种拆分是沿着查找过程的维度，即查找前缀长度并查找下一跳，另一种拆分是沿着前缀长度的维度，即长度小于或等于24的前缀的IP查找和长度大于24的前缀的IP查找。其次，我们提出了一套基于我们的SAIL框架的IP查找算法。第三，我们在四个平台上实现了我们的算法：CPU、FPGA、GPU 和众核。我们使用来自中国主要 ISP 的真实 FIB 和真实流量进行了广泛的实验来评估我们的算法。实验结果表明，我们的 SAIL 算法比众所周知的 IP 查找算法快几倍甚至两个数量级。
The Forwarding Information Base (FIB) of backbone routers has been rapidly growing in size. An ideal IP lookup algorithm should achieve constant, yet small, IP lookup time and on-chip memory usage. However, no prior IP lookup algorithm achieves both requirements at the same time. In this paper, we first propose SAIL, a Splitting Approach to IP Lookup. One splitting is along the dimension of the lookup process, namely finding the prefix length and finding the next hop, and another splitting is along the dimension of prefix length, namely IP lookup on prefixes of length less than or equal to 24 and IP lookup on prefixes of length longer than 24. Second, we propose a suite of algorithms for IP lookup based on our SAIL framework. Third, we implemented our algorithms on four platforms: CPU, FPGA, GPU, and many-core. We conducted extensive experiments to evaluate our algorithms using real FIBs and real traffic from a major ISP in China. Experimental results show that our SAIL algorithms are several times or even two orders of magnitude faster than well known IP lookup algorithms.