• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Network Protocols >Fast shortest-path queries on large-scale graphs
【24h】

Fast shortest-path queries on large-scale graphs

机译：大型图形上的快速最短路径查询

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

摘要

Shortest-path queries on weighted graphs are an essential operation in computer networks. The performance of such algorithms has become a critical challenge in emerging software-defined networks (SDN), since SDN controllers need to perform a shortest-path query for every flow. Unlike classic solutions (e.g., Dijkstra's algorithm), high-performance shortest-path query algorithms include two stages: preprocessing and query answering. Despite the improved query answering time, existing two-stage algorithms are still extremely time-consuming in preprocessing large-scale graphs. In this paper, we propose an efficient shortest-path query algorithm, called BBQ, which reduces the running time of both stages via tree decomposition. BBQ constructs a distance oracle in a bottom-top-bottom manner, which significantly reduces preprocessing time over existing algorithms. In addition, BBQ can answer batch queries in bulk by traversing the decomposed tree instead of executing separate queries. Our experimental results show that BBQ outperforms state-of-the-art approaches by orders of magnitude for the running time of the preprocessing stage. Meanwhile, BBQ also offers remarkable acceleration for answering batches of queries. As a result, SDN controllers that use BBQ can sustain 1.1-27.9 times higher connection request rates.
机译：最短路径的查询加权图都是计算机网络中的一个基本操作。这种算法的性能已经成为新兴的软件定义网络（SDN）的一个关键挑战，因为SDN控制器需要为每个流进行最短路径查询。不同于传统的解决方案（例如，Dijkstra算法），高性能的最短路径查询算法包括两个阶段：预处理和查询应答。尽管提高了查询应答时，现有的两阶段算法仍然非常耗时的预处理大型图形。在本文中，我们提出了一种高效最短路径查询算法，叫做BBQ，它通过树分解减少两个阶段的运行时间。 BBQ构造在底上下的方式，这显著降低预处理时间在现有算法的距离预言。此外，烧烤可以通过遍历树分解，而不是执行单独的查询回答散装批次查询。我们的实验结果表明，烧烤性能优于国家的最先进的由预处理阶段的运行时间量级接近。同时，烧烤还提供解答问题的批次显着加速。其结果是，使用烧烤SDN控制器可维持较高的1.1-27.9倍连接请求速率。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号