Computer Science Colloquium

Efficient and Robust Routing in the Presence of Competing Interests

Ratul Mahajan

Friday, April 15, 2005 11:30 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185

Colloquium Information:


Richard Cole, (212) 998-3119


A fundamental characteristic of many networks is that they are controlled by independent parties. These parties must cooperate to provide global connectivity even though they often have competing interests. This tension hurts the efficiency and robustness of routing because it leads to selfish decisions based largely on local information.

I present Wiser, a practical mechanism to achieve efficient and robust routing in the Internet when ISPs act in their own interest. Wiser is based on simple contracts between pairs of neighboring ISPs and does not require them to disclose sensitive information. I use measured ISP topologies to quantify the efficiency of both today's selfish routing (or, the "price of anarchy") and Wiser relative to the efficiency of socially optimal routing that treats all ISPs as one party. I show that Wiser performs almost as well as socially optimal routing, implying that it largely eliminates the costs of competing interests in the Internet. Moreover, unlike socially optimal routing, it provides a strong adoption incentive because individual ISPs do not suffer for the greater good.

top | contact