Avoiding Routing Loops on the Internet

Suppose that some particular link in the Internet is currently congested. A natural solution is to try to make packets bypass that link. This can be done by increasing the cost of that link intentionally, say from a ₁ to a ₂, since the Internet uses 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 ₁ to a ₂ but through an intermediate value, a ₃, i.e., from a ₁ to a ₃ and then to a ₂. We may need several intermediate values. We show that in this case the greedy strategy, namely, raising the cost as much as possible in each step, is optimal.