Trading potatoes in distributed multi-tier routing systems

ABSTRACT

The The Internet is an example of a distributed system where the task of routing is performed in a multi-tier fashion: interdomain paths between autonomously-managed networks are sub ject to a global agreement (BGP), and the choice of intradomain paths is left to the discretion of each such network. When forwarding packets, Autonomous Systems (ASes) frequently choose the shortest path in their network to the next-hop AS in the BGP path, a strategy known as hot potato routing. As a result, paths in the Internet are suboptimal from a global perspective. In this paper we explore complementary deviations from hot-potato routing in a manner which benefits both ASes. We show that even for a pair of ASes obtaining such path trading solutions is NP-complete, and give pseudo-polynomial algorithms to find them. We use PoP-level maps of ASes obtained from measurements of real AS topologies in the Internet to show that, in comparison to hot-potato routing, path trading can substantially reduce the cost of intradomain routing.

REFERENCES

• 1: D. Feldman. and Y. Shavitt. Automatic large scale generation of PoP level maps. In GLOBECOM 2008, December 2008.
• 2: R. Johari and J. Tsitsiklis. Routing and peering in a competitive internet. In Decision and Control, volume 2, pages 1556--1561, 2004.
• 3: Peter B. Key, Laurent Massoulié, and Donald F. Towsley. Path selection and multipath congestion control. In INFOCOM, pages 143--151, 2007.
• 4: Ratul Mahajan , David Wetherall , Thomas Anderson, Negotiation-based routing between neighboring ISPs, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.29-42, May 02-04, 2005
• 5: John F. Nash. The bargaining problem. Econometrica, 18:155--162, 1950.
• 6: Yuval Shavitt , Eran Shir, DIMES: let the internet measure itself, ACM SIGCOMM Computer Communication Review, v.35 n.5, October 2005 [doi>10.1145/1096536.1096546]
• 7: Gireesh Shrimali, Aditya Akella, and Almir Mutapcic. Cooperative inter-domain traffic engineering using nash bargaining and decomposition. In INFOCOM, pages 330--338, 2007.
• 8: Neil Spring , Ratul Mahajan , David Wetherall , Thomas Anderson, Measuring ISP topologies with rocketfuel, IEEE/ACM Transactions on Networking (TON), v.12 n.1, p.2-16, February 2004 [doi>10.1109/TNET.2003.822655]
• 9: Renata Teixeira , Aman Shaikh , Tim Griffin , Jennifer Rexford, Dynamics of hot-potato routing in IP networks, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking

General Terms:
Economics, Experimentation

Keywords:
bargaining, hot-potato routing, ospf