Avoiding Routing Loops on the Internet

摘要

Suppose that some particular link in the Internet is currently congested. Then a natural idea is to try to make packets bypass that link. This can be done by increasing the cost of that link intentionally, say from a_1 to a_2, since the Internet uses the shortest-path routing. Unfortunately, however, this often causes temporary loops for packet traveling, called routing loops. In this paper, we show that routing loops can be avoided by increasing the cost of the link not directly from a_1 to a_2 but through an intermediate value, a_3, i.e., from a_1 to a_3 and then to a_2. We may need several (more than one) intermediate values. We show that in such a occasion, the greedy strategy, namely raising the cost as much as possible in each step, is optimal.