论文标题
迈向无法伸缩的最短路径路由问题的可扩展算法
Toward Scalable Algorithms for the Unsplittable Shortest Path Routing Problem
论文作者
论文摘要
在本文中，我们考虑了IP网络流量工程领域中出现的延迟限制了无法限制的最短路径路由问题。根据这些权重，该问题包括有向图和一组商品，以计算一组路由路径和相关的管理权重，以便根据这些权重，每种商品都沿其来源和目的地之间的唯一最短路径路由。我们为该问题提供了一个紧凑的MILP公式，从而扩展了（A. Bley，2010年）的作品，并有一些有效的不平等，以增强其线性放松。该公式被用作我们开发的迭代方法的大块块，以解决大规模实例。我们进一步提出了基于图的树分解的动态编程算法。据我们所知，这是第一个解决该问题的确切组合算法。最后，我们通过一系列有关最新实例的实验来评估方法的效率。
In this paper, we consider the Delay Constrained Unsplittable Shortest Path Routing problem which arises in the field of traffic engineering for IP networks. This problem consists, given a directed graph and a set of commodities, to compute a set of routing paths and the associated administrative weights such that each commodity is routed along the unique shortest path between its origin and its destination, according to these weights. We present a compact MILP formulation for the problem, extending the work in (A. Bley, 2010) along with some valid inequalities to strengthen its linear relaxation. This formulation is used as the bulding block of an iterative approach that we develop to tackle large scale instances. We further propose a dynamic programming algorithm based on a tree decomposition of the graph. To the best of our knowledge, this is the first exact combinatorial algorithm for the problem. Finally, we assess the efficiency of our approaches through a set of experiments on state-of-the-art instances.
