مسیریابی اینترنت بین سیستم های مستقل: الگوریتم های سریع برای معاملات مسیر .

Routing traffic on the internet efficiently has become an important research topic over the past decade. In this article we consider a generalization of the shortest path problem, the path-trading problem, which has applications in inter-domain traffic routing. When traffic is forwarded between autonomous systems (ASes), such as competing internet providers, each AS selfishly routes the traffic inside its own network. Efficient solutions to the path trading problem can lead to higher global performance in such systems, while maintaining the objectives and costs of the individual ASes. First, we extend a previous hardness result for the path trading problem. 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 a theoretical explanation for that fact. The computational results show that our algorithm yields far superior running times and can solve considerably larger instances than a previously known algorithm.