User-directed routing: from theory, towards practice

ABSTRACT

User-directed routing technologies - that is, systems in which users choose their own routes through a communications network - have generated considerable interest in recent years. Despite their numerous theoretical advantages, ISPs have so far resisted these technologies, even as users have learned to capture some routing power through overlay networks. This study responds to this disconnect between theory and practice by asking how user-directed routing would affect three prominent objectives of network operators: maintaining control over the network, earning profits, and keeping inner details of the network secret. Contrary to the modern theme in routing proposals, we argue that user-directed routing is not fundamentally incompatible with ISP-control, as long as a flexible pricing system is in place. Instead - and under surprisingly general assumptions - an ISP can use prices on the open market to induce any feasible traffic pattern. Moreover, we argue that the market-based approach maximizes welfare for any given traffic pattern. In general, our model does not guarantee whether an ISP will earn more money under user-directed routing. Nevertheless, we provide some intuition to suggest why a typical ISP may expect higher profits. Finally, we suggest that giving routing power to users conflicts with an ISP's desire for secrecy. At the same time, widespread adoption of user-directed routing, perhaps promoted through regulation, may facilitate a transparent and civil industry, to the benefit of many ISPs.

REFERENCES

• 1: Mike Afergan , John Wroclawski, On the benefits and feasibility of incentive based routing infrastructure, Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems, September 03-03, 2004, Portland, Oregon, USA [doi>10.1145/1016527.1016533]
• 2: Vinay Aggarwal , Anja Feldmann , Christian Scheideler, Can ISPS and P2P users cooperate for improved performance?, ACM SIGCOMM Computer Communication Review, v.37 n.3, July 2007 [doi>10.1145/1273445.1273449]
• 3: 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
• 4: Bell, C. E., S. Stidham. Individual versus social optimization in the allocation of customers to alternative servers. Management Sci. 29: 831--839, 1983.
• 5: Yang-hua Chu , Sanjay G. Rao , Hui Zhang, A case for end system multicast (keynote address), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 18-21, 2000, Santa Clara, California, United States
• 6: 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
• 7: Computer Science and Telecommunications Board, National Research Council. Looking Over the Fence at Networks: A Neighbor's View of Networking Research. The National Academies Press. 2001.
• 8: Eckersley, P., von Lohmann, F., Schoen, A. Packet Forgery By ISPs: A Report on the Comcast Affair. Electronic Frontier Foundation. 2007.
• 9: Estan, C., Akella, A. & Banerjee, S. Achieving Good End-to-End Service Using Bill-Pay. HotNets 2006.
• 10: He, J., Bresler, M., Chiang, M. & Rexford, J. Towards Multi-Layer Traffic Engineering: Optimization of Congestion Control and Routing. IEEE Journal on Selected Areas in Communications (June 2007).
• 11: Kelly, F. P. Charging and Rate Control for Elastic Traffic. European Transactions on Telecommunications, 8: 33--37, 1997.
• 12: Keralapura, R., Taft, N., Chuah, C., Iannaccone, G. Can ISPs Take the Heat from Overlay Networks? HOTNETS 2004.
• 13: Lakshminarayanan, K., Stoica, I. & Shenker, S. Routing as a Service. UC Berkeley EECS Technical Report No. UCB/CSD-04-1327 2004.
• 14: Paul Laskowski , John Chuang, Network monitors and contracting systems: competition and innovation, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 15: Laskowski, P. & Chuang, J. Market Power, Innovation, and the Interplay of Routing and Pricing Design. Under submission, 2008.
• 16: Liu, Y., Zhang, H., Gong, W. & Towsley, D. On the Interaction Between Overlay Routing and Traffic Engineering. IEEE INFOCOM 2005.
• 17: Madison River Communications LLC, Consent Decree, 20 FCC Rcd 4,295 (2005).
• 18: Yasushi Masuda , Seungjin Whang, Capacity Management in Decentralized Networks, Management Science, v.48 n.12, p.1628-1634, December 2002 [doi>10.1287/mnsc.48.12.1628.446]
• 19: Norton, W. The Art of Peering: The Peering Playbook. Equinix Inc. 2002.
• 20: Norton, W. Video Internet: The Next Wave of Disruption to the US Peering Ecosystem. NANOG 40, 2007.
• 21: Parker, A. The True Picture of Peer-to-Peer Filesharing. CacheLogic 2004.
• 22: Parker, A. P2P in 2005. CacheLogic 2005.
• 23: Peha, J. The Benefits and Risks of Mandating Network Neutrality, and the Quest for a Balanced Policy. International Journal of Communication, 2007.
• 24: Peterson, L., Shenker, S. & Turner, J. Overcoming the Internet Impasse through Virtualization. HotNets 2004.
• 25: Lili Qiu , Yang Richard Yang , Yin Zhang , Scott Shenker, On selfish routing in internet-like environments, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863974]
• 26: Sylvia Ratnasamy , Scott Shenker , Steven McCanne, Towards an evolvable internet architecture, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 27: 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]
• 28: 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]
• 29: "Telus cuts subscriber access to pro-union website", CBC News, 2005. Retrieved on 2007-08-02. http://www.cbc.ca/canada/story/2005/07/24/telus-sites050724.html
• 30: Wen Xu , Jennifer Rexford, MIRO: multi-path interdomain routing, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 31: Xiaowei Yang, NIRA: a new Internet routing architecture, ACM SIGCOMM Computer Communication Review, v.33 n.4, October 2003
• 32: Xiaowei Yang , David Wetherall, Source selectable path diversity via routing deflections, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Design, Economics, Legal Aspects, Theory

Keywords:
control, market-based routing, pricing, traffic engineering, transparency, user-directed routing