• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE International Conference on Network Protocols >Scalable and Efficient Multipath Routing: Complexity and Algorithms
【24h】

Scalable and Efficient Multipath Routing: Complexity and Algorithms

机译：可扩展和高效的多路径路由：复杂性和算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A fundamental unsolved challenge in multipath routing is to provide disjoint end-to-end paths, each one satisfying certain operational goals (e.g., shortest possible), without overwhelming the data plane with prohibitive amount of forwarding state. In this paper, we study the problem of finding a pair of shortest disjoint paths that can be represented by only two forwarding table entries per destination. Building on prior work on minimum length redundant trees, we show that the underlying mathematical problem is NP-complete and we present heuristic algorithms that improve the known complexity bounds from cubic to the order of a single shortest path search. Finally, by extensive simulations we find that it is possible to very closely attain the absolute optimal path length with our algorithms (the gap is just 1-5%), eventually opening the door for wide-scale multipath routing deployments.
机译：多路径路由中的基本未解决的挑战是提供不相交的端到端路径，每个路径满足某些操作目标（例如，尽可能短的），而不需要具有禁止的转发状态的数据平面。在本文中，我们研究了找到一对最短不相交路径的问题，该路径只能由每个目的地的两个转发表条目表示。建立在最低长度的最小冗余树上的工作中，我们表明潜在的数学问题是NP完成，我们呈现出启发式算法，使从立方到单个最短路径搜索的顺序提高已知复杂性界限的启发式算法。最后，通过广泛的仿真，我们发现，可以使用我们的算法（间隙仅为1-5％）非常紧密地达到绝对最佳路径长度，最终为广泛的多径路由部署打开门。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号