On the benefits and feasibility of incentive based routing infrastructure

ABSTRACT

Routing on the Internet today is as much about money as it is traffic. The business relationships of an ISP largely dictate its routing policy and drive the work of its engineers. In today's routing mechanism, this leads to a number of well-known pathologies. This structure is further challenged by the emergence of user-directed routing.This paper explores these challenges and argues for the introduction of explicit incentives (prices) into the routing fabric of the Internet. We argue that doing so addresses limitations of the current system that are significant today and will only be exacerbated by user-directed routing. To support this claim, we describe the benefits and properties of incentive-based routing frameworks and demonstrate how such frameworks can be applied to a number of routing architectures, including BGP.

REFERENCES

• 1: Lixin Gao , Jennifer Rexford, Stable Internet routing without global coordination, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.307-317, June 18-21, 2000, Santa Clara, California, United States
• 2: David D. Clark , John Wroclawski , Karen R. Sollins , Robert Braden, Tussle in cyberspace: defining tomorrow's internet, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 3: 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
• 4: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 5: Nick Feamster, Practical verification techniques for wide-area routing, ACM SIGCOMM Computer Communication Review, v.34 n.1, January 2004 [doi>10.1145/972374.972390]
• 6: A. M. Odlyzko. Pricing and architecture of the internet: Historical perspectives from telecommunications and transportation. http://www.dtc.umn.edu/~odlyzko/doc/pricing.architecture.pdf.
• 7: Tobias Oetiker, MRTG: The Multi Router Traffic Grapher, Proceedings of the 12th Conference on Systems Administration, p.141-148, December 06-11, 1998
• 8: Akamai technologies homepage. http://www.akmai.com/.
• 9: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 10: David D. Clark. Policy routing in Internet protocols. RFC 1102, Internet Engineering Task Force, May 1989. ftp://ftp.ietf.org/rfc/rfc1102.txt.
• 11: Xiaowei Yang, NIRA: a new Internet routing architecture, ACM SIGCOMM Computer Communication Review, v.33 n.4, October 2003
• 12: Alex C. Snoeren , Barath Raghavan, Decoupling policy from mechanism in Internet routing, ACM SIGCOMM Computer Communication Review, v.34 n.1, January 2004 [doi>10.1145/972374.972389]
• 13: Akamai glitch causes web traffic disruption. http://biz.yahoo.com/rc/040524/tech_akamai_outage_2.html.
• 14: Lixin Gao, Timothy Griffin, and Jennifer Rexford. Inherently safe backup routing with BGP. In INFOCOM, pages 547--556, 2001.
• 15: An architecture for differentiated services. http://www.ietf.org/rfc/rfc2475.txt.
• 16: Interpret the destination class usage mib. http://www.juniper.net/techpubs/software/junos/junos56/swconfig56-net-mgmt/h%
• 17: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571856]
• 18: L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the internet hierarchy from multiple vantage points, 2001.
• 19: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 20: Ramesh Johari Rjohari. Routing and peering in a competitive internet. citeseer.ist.psu.edu/572286.html.
• 21: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]

INDEX TERMS

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

General Terms:
Design, Economics, Management