...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computer networks >Compressing IP Forwarding Tables with Small Bounded Update Time
【24h】

Compressing IP Forwarding Tables with Small Bounded Update Time

机译：以有限的更新时间压缩IP转发表

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

With the fast development of the Internet, the size of Forwarding Information Base (FIB) maintained at backbone routers is experiencing an exponential growth, making the storage support and lookup process of FIBs a severe challenge. One effective way to address the challenge is FIB compression, and various solutions have been proposed in the literature. The main shortcoming of FIB compression is the overhead of updating the compressed FIB when routing update messages arrive. Only when the update time of FIB compression algorithms is small bounded can the probability of packet loss incurred by FIB compression operations during update be completely avoided. However, no prior FIB compression algorithm can achieve small bounded worst case update time, and hence a mature solution with complete avoidance of packet loss is still yet to be identified. To address this issue, we propose the Unite and Split (US) compression algorithm to enable fast update with controlled worst case update time. Further, we use the US algorithm to improve the performance of a number of classic software and hardware lookup algorithms. Simulation results show that the average update speed of the US algorithm is a little faster than that of the binary trie without any compression, while prior compression algorithms inevitably seriously degrade the update performance. After applying the US algorithm, the evaluated lookup algorithms exhibit significantly smaller on-chip memory consumption with little additional update overhead. (C) 2016 Elsevier B.V. All rights reserved.
机译：随着Internet的快速发展，骨干路由器上维护的转发信息库（FIB）的规模呈指数级增长，这使FIB的存储支持和查找过程成为严峻的挑战。解决挑战的一种有效方法是FIB压缩，文献中已经提出了各种解决方案。 FIB压缩的主要缺点是在路由更新消息到达时更新压缩的FIB的开销。只有当FIB压缩算法的更新时间较小时，才可以完全避免FIB压缩操作在更新过程中引起丢包的可能性。但是，没有任何现有的FIB压缩算法可以实现有限的最坏情况下的更新时间，因此仍需要确定一种完全避免丢包的成熟解决方案。为解决此问题，我们提出了Unite and Split（US）压缩算法，以在受控的最坏情况下更新时间实现快速更新。此外，我们使用US算法来改善许多经典软件和硬件查找算法的性能。仿真结果表明，US算法的平均更新速度比不进行任何压缩的二进制树的平均更新速度要快一些，而现有的压缩算法不可避免地会严重降低更新性能。在应用US算法之后，评估后的查找算法显示出显着较小的片上内存消耗，并且几乎没有其他更新开销。 （C）2016 Elsevier B.V.保留所有权利。

著录项

  • 来源
    《Computer networks》 |2016年第4期|77-90|共14页
  • 作者

    Zhang Yuanyuan; Xu Mingwei; Wang Ning; Li Jun; Chen Penghan; Liang Fei;

  • 作者单位

    Tsinghua Univ, Dept Comp Sci & Technol, Tsinghua Natl Lab Informat Sci & Technol, Beijing, Peoples R China;

    Tsinghua Univ, Dept Comp Sci & Technol, Tsinghua Natl Lab Informat Sci & Technol, Beijing, Peoples R China;

    Univ Surrey, Inst Commun Syst, Guildford GU2 5XH, Surrey, England;

    Univ Oregon, Dept Comp & Informat Sci, Eugene, OR 97403 USA;

    Beijing Univ Posts & Telecommun, Broadband Network Res Ctr, Beijing, Peoples R China;

    Beijing Univ Posts & Telecommun, Broadband Network Res Ctr, Beijing, Peoples R China;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    FIB Compression; FIB update; IP address lookup; Tries; Longest prefix matching;

    机译：FIB压缩;FIB更新;IP地址查找;重试;最长前缀匹配;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号