Efficient and Robust Routing in the Presence of Competing Interests

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, as is known to be the case in the Internet, because it leads to self-interested decisions based largely on local information.

I describe practical mechanisms to achieve efficient and robust routing when parties act in their own interest. In the context of the Internet, I present a routing method that is based on simple contracts between pairs of ISPs. I use measured ISP topologies to quantify the benefits o this method and find that, for instance, 5% of the routing paths more than double their performance. I also find that this method performs almost as well as the globally optimal solution that treats all ISPs as one party, implying that it largely eliminates the costs of competing interests (or, the price of autonomy) in the Internet. Moreover, it provides a strong adoption incentive because, unlike the globally optimal solution, individual ISPs do not suffer for the greater good. I also consider routing in multi-hop wireless networks, in which some nodes relay packets on behalf of other nodes. In this setting, free-riders can refuse to relay packets, hurting overall performance and connectivity. I describe a protocol that uses anonymous messages novelly to disconnect free-riders, and I present experimental results from an 802.11 testbed to show its effectiveness.

Speaker Details

Ratul Mahajan received his M.S. from the University of Washington, Seattle and his B.Tech. from the Indian Institute of Technology, Delhi, India. He is currently at the University of Washington, from where he expects to graduate with a Ph.D. in the summer of 2005. His research interests lie in the area of networked computer systems, especially the architecture and design of large-scale systems.

Date:
Speakers:
Ratul Mahajan
Affiliation:
University of Washington
    • Portrait of Jeff Running

      Jeff Running

    • Portrait of Ratul Mahajan

      Ratul Mahajan

      Principal Researcher