Path Trading: Fast Algorithms, Smoothed Analysis, and Hardness Results
Path Trading: Fast Algorithms, Smoothed Analysis, and Hardness Results
复制标题
路径交易：快速算法、平滑分析和硬度结果
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. V. D. Zwaan
中科院分区：
文献类型：
--
作者：
A. Berger;Heiko Röglin;R. V. D. Zwaan
边界网关协议（BGP）作为互联网的主要路由协议，确保自治系统（AS）之间的网络可达性。当流量根据该协议在 Internet 上的许多 AS 之间转发时，每个 AS 根据支持 AS 本地目标的某种内部协议自私地在其自己的网络内路由流量。我们考虑在此类系统中实现更高全局性能的可能性，同时保持各个 AS 的目标和成本。特别是，我们考虑路径交易（即偏离使用单独的最佳协议路由流量）如何导致更好的全局性能。 Shavitt 和 Singer（“自治系统之间路径交易的局限性和可能性”，INFOCOM 2010）是第一个考虑寻找此类路径交易解决方案的计算复杂性的人。他们表明该问题是弱 NP 困难问题，并提供了一个动态程序来查找 AS 对之间的路径交易。
在本文中，我们从理论上和实践上改进了他们的结果。首先，我们表明寻找 AS 集合之间的路径交易也是强 NP 困难的。此外，我们提供了一种算法，可以找到一对两个 AS 的所有帕累托最优路径交易。虽然原则上帕累托最优路径交易的数量可以是指数级的，但在我们的实验中，这个数量通常很小。我们使用平滑分析的框架来提供理论证据，证明这是一种普遍现象，而不仅限于我们进行实验的实例。计算结果表明，我们的算法产生了远远优越的运行时间，并且可以解决比以前的动态程序大得多的实例。
The Border Gateway Protocol (BGP) serves as the main routing protocol of the Internet and ensures network reachability among autonomous systems (ASes). When traffic is forwarded between the many ASes on the Internet according to that protocol, each AS selfishly routes the traffic inside its own network according to some internal protocol that supports the local objectives of the AS. We consider possibilities of achieving higher global performance in such systems while maintaining the objectives and costs of the individual ASes. In particular, we consider how path trading, i.e. deviations from routing the traffic using individually optimal protocols, can lead to a better global performance. Shavitt and Singer ("Limitations and Possibilities of Path Trading between Autonomous Systems", INFOCOM 2010) were the first to consider the computational complexity of finding such path trading solutions. They show that the problem is weakly NP-hard and provide a dynamic program to find path trades between pairs of ASes.
In this paper we improve upon their results, both theoretically and practically. First, we show that finding path trades between sets of ASes is also strongly NP-hard. Moreover, we provide an algorithm that finds all Pareto-optimal path trades for a pair of two ASes. While in principal the number of Pareto-optimal path trades can be exponential, in our experiments this number was typically small. We use the framework of smoothed analysis to give theoretical evidence that this is a general phenomenon, and not only limited to the instances on which we performed experiments. The computational results show that our algorithm yields far superior running times and can solve considerably larger instances than the previous dynamic program.