Interdomain Routing and Games

The Internet consists of many administrative domains, or Autonomous Systems
(ASes), each owned by an economic entity (Microsoft, AT&T, The Hebrew
University, etc.). The task of ensuring connectivity between ASes, known as
interdomain routing, is currently handled by the Border Gateway Protocol (BGP).

ASes are self-interested economic agents and might be willing to manipulate BGP for their benefit.

We present a game-theoretic model that captures the intricacies of ``real
life'' interdomain routing (asynchronous network, partial information of ASes,
sequential interaction, network failures, and more). We highlight various
connections between networking research and Distributed Algorithmic Mechanism
Design concepts and techniques, and prove several impossibility and possibility
results. In particular, we show that, in the realistic Gao-Rexford setting, BGP
(with slight modifications) is immune to all forms of rational manipulation by
single ASes. The Gao-Rexford setting is said to accurately depict the business
relationships between ASes in today's Internet. Formally, we prove that, in
this setting, a slight modification of BGP is incentive-compatible in ex-post
Nash equilibrium. Moreover, we show that, if a reasonable condition holds, then
this slightly modified BGP is also collusion-proof in ex-post Nash (i.e.,
immune to rational manipulations even by coalitions of ASes of any size).

 Unlike the vast majority of works in Algorithmic Mechanism Design (and, in
particular, most previous works on incentive-compatibility in interdomain
routing), our results do not require any monetary transfer between ASes (as is
the case in practice). Our results can be regarded as the strategic
justification for using BGP in practice.

 
Based on joint work with Hagay Levin and Aviv Zohar
(http://www.cs.huji.ac.il/~mikesch/bgp.pdf  and subsequent research)