Mathematical analysis on forwarding information base compression
Mathematical analysis on forwarding information base compression
复制标题
转发信息库压缩的数学分析
DOI：
10.1007/s42045-018-0010-1
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Li Xiaoming
中科院分区：
文献类型：
--
作者：
Yang Tong;Li Jinyang;Zhao Chenxingyu;Xie Gaogang;Li Xiaoming
随着Internet的快速发展，骨干路由器中的路由表规模不断快速增长。转发信息库（FIB）源自路由表，存储在线路卡中以进行路由查找。由于线卡的内存有限，因此有必要压缩 FIB 以消耗更少的存储空间。因此，各种FIB压缩算法被提出。然而，对于 FIB 压缩解决方案的可行性，没有很好的数学支持，也没有任何数学推导来证明这些算法的正确性。为了解决这些问题，我们提出了一种基于群论的通用数学方法。通过定义一个代表最长前缀匹配规则的组，可以计算出FIB压缩方案最坏情况的界限。此外，为了保证FIB压缩算法的最终正确性，提出并实现了路由表方程测试，通过遍历32位IP地址空间来验证压缩前后两个路由表的等价性。
With the fast development of Internet, the size of routing table in the backbone router continues to grow rapidly. forwarding information base (FIB), which is derived from routing table, is stored in line-card to conduct routing lookup. Since the line-card’s memory is limited, it would be worthwhile to compress the FIB for consuming less storage. Therefore, various FIB compression algorithms have been proposed. However, there is no well-presented mathematical support for the feasibility of the FIB compression solution, nor any mathematical derivation to prove the correctness of these algorithms. To address these problems, we propose a universal mathematical method based on theGrouptheory. By defining aGrouprepresenting the longest prefix matching rule, the bound of the worst case of FIB compression solution can be figured out. Furthermore, in order to guarantee theultimate correctnessof FIB compression algorithms, routing table equation test is proposed and implemented to verify the equivalence of the two routing tables before and after compression by traversing the 32-bit IP address space.
登录
查看更多内容
DOI：
10.1109/infcom.2013.6566915
发表时间：
2013-04
期刊：
2013 Proceedings IEEE INFOCOM
影响因子：
--
作者：
Ori Rottenstreich;Marat Radan;Yuval Cassuto;I. Keslassy;Carmi Arad;Tal Mizrahi;Yoram Revah;Avinatan Hassidim
通讯作者：
Ori Rottenstreich;Marat Radan;Yuval Cassuto;I. Keslassy;Carmi Arad;Tal Mizrahi;Yoram Revah;Avinatan Hassidim
DOI：
10.1109/icnp.2011.6089061
发表时间：
2011-10
期刊：
2011 19th IEEE International Conference on Network Protocols
影响因子：
--
作者：
Dan Li;Henggang Cui;Yan Hu;Yong Xia;Xin Wang
通讯作者：
Dan Li;Henggang Cui;Yan Hu;Yong Xia;Xin Wang
DOI：
10.1145/263105.263136
发表时间：
1997-10
期刊：
--
影响因子：
--
作者：
M. Waldvogel;G. Varghese;J. Turner;B. Plattner
通讯作者：
M. Waldvogel;G. Varghese;J. Turner;B. Plattner
DOI：
10.1145/277851.277863
发表时间：
1998-06
期刊：
--
影响因子：
--
作者：
V. Srinivasan;G. Varghese
通讯作者：
V. Srinivasan;G. Varghese
DOI：
10.1109/65.912716
发表时间：
2001-03
期刊：
IEEE Netw.
影响因子：
--
作者：
M. A. Ruiz-Sánchez;E. Biersack;Walid Dabbous
通讯作者：
M. A. Ruiz-Sánchez;E. Biersack;Walid Dabbous