Incentive-Compatible Interdomain Routing

Joan Feigenbaum, Vijay Ramachandran, and Michael Schapira

Abstract

The routing of traffic between Internet domains, or Autonomous Systems (ASes), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). Using BGP, autonomous systems can apply semantically rich routing policies to choose interdomain routes in a distributed fashion. This expressiveness in routing-policy choice supports domains' autonomy in network operations and in business decisions, but it comes at a price: The interaction of locally defined routing policies can lead to unexpected global anomalies, including route oscillations or overall protocol divergence. Networking researchers have addressed this problem by devising constraints on policies that guarantee BGP convergence without unduly limiting expressiveness and autonomy.
In addition to taking this engineering or "protocol-design" approach, researchers have approached interdomain routing from an economic or "mechanism-design" point of view. It is known that lowest-cost-path (LCP) routing can be implemented in a truthful, BGP-compatible manner but that several other natural classes of routing policies cannot. In this paper, we present a natural class of interdomain-routing policies that is more realistic than LCP routing and admits incentive-compatible, BGP-compatible implementation. We also present several positive steps toward a general theory of incentive-compatible interdomain routing.

Current Citation

J. Feigenbaum, V. Ramachandran, and M. Schapira. "Incentive-Compatible Interdomain Routing." In Proc. ACM Electronic Commerce (EC'06), pp. 130-139, June 2006. Ext. version available as Yale Univ. Tech. Rep't YALEU/DCS/TR-1342, May 2006.
 

@inproceedings{frs06,
	title = {Incentive-Compatible Interdomain Routing},
	author = {Joan Feigenbaum and Vijay Ramachandran and Michael Schapira},
	booktitle = {Proc.\ {ACM} Electronic Commerce {(EC)}},
	month = {June},
	year = {2006},
	publisher = {{ACM} Press},
	pages = {130-139},
	note = {Ext.\ version available as Yale Univ.\ Tech.\ Report
		YALEU/DCS/TR-1342, May 2006.} }

Download
(in reverse chronological order)

Filetype	Version
(176KB)	Conference version (June 2006)
(240KB)	Extended version (YALEU/DCS/TR-1342, May 2006)
(224KB)	Slides from conference talk