Michael Schapira: Internet Routing, Distributed Computation, Game Dynamics and Mechanism Design I

This post is authored by Michael Schapira. (It is the first in a series of two posts.)

In this post, I’ll outline work on Internet routing and sketch important areas for future work, both on routing itself and, more broadly, on mechanism design, game theory and distributed computation.

The Internet comprises administrative domains known as Autonomous Systems (ASes), which vary in size, from large (multi)national networks to small networks servicing schools or small businesses. The task of establishing routes between ASes, called interdomain routing, is currently handled by the Border Gateway Protocol (BGP)—the core routing protocol of the Internet. BGP is one of the most critical pieces of the Internet’s infrastructure and can be regarded as the glue that holds the Internet together.

Over the past decade, routing with BGP has been studied from engineering, computational, game theoretic and economic perspectives. Combining algorithmic and economic considerations in the study of interdomain routing is natural, because the many separate domains that make up the Internet are independent economic agents that must jointly execute a distributed algorithm in order to route traffic. In addition, interdomain routing motivates exciting new questions in computer science, game theory, and economics.

A (Simplified) Model of Interdomain Routing

The following is a simplified model of interdomain routing, based on the seminal work of Thimothy Griffin and Gordon Wilfong, and on the game-theoretic model of Hagay Levin, Michael Schapira, and Aviv Zohar  There is a connected AS graph G=(N,L), where he set of nodes (vertices) N represents ASes and the set of links (edges) L represents communication links between ASes. Because BGP computes routes for each destination AS independently, without loss of generality, we assume that N consists of n source nodes {1,…,n} and a unique destination node d.

Each source node (AS) i has a ranking function <i that expresses i’s strict preferences over all simple (loop-free) routes from i to d (including the “empty route’’ Ø). ASes’ route preferences can be quite complex and reflect both ASes’ business interests and engineering considerations (e.g., ASes’ desires to route traffic through specific neighbours, avoid sending traffic through competitors, load balance traffic, minimize congestion, etc.). In particular, nodes do not always prefer shorter paths to longer ones.

BGP allows ASes great expressiveness in selecting routes; a routing tree to each destination is built, hop-by-hop, as knowledge about how that destination can be reached propagates through the network. Generally speaking, in a BGP execution nodes continuously “best-reply’’ to neighbouring nodes’ most recent actions. Importantly, BGP operates in an asynchronous computational environment in which nodes can potentially select routes simultaneously and in an uncoordinated manner.

 The above high-level description is formally captured as follows: there is an infinite sequence of discrete time-steps t=1,… In each time step t, a subset of the source nodes is activated. Each activated node chooses its single best available route. That is, each activated source node i examines the current routes of i’s neighbouring nodes (after time step t-1) and selects to forward traffic to the neighbor whose route i likes the most, given its ranking function. There is an adversarial entity named the “Scheduler’’ that decides which nodes are activated in each time step. The only restriction on the “schedule’’ chosen is that each node must be activated in infinitely many time steps (i.e, no node is indefinitely starved from selecting routes).


Consider, for means of illustration, the small network in Fig. 1 (system “DISAGREE” from here). Consider the case that the schedule chosen is such that node 1 is activated at time t=1 and node 2 is activated at time t=2. Observe that at time t=1 node 1 will choose its direct route to d (for lack of other options), and at time t=2 node 2 will choose the route 21d (which it prefers to the direct route 2d). Observe that, from this moment forth, no matter how nodes are activated, this routing state will remain constant (an “equilibrium’’, or “stable state’’, was reached).

We will mention now two main challenges in this area. We will discuss these challenges in more detail in the second part.  

Challenge I: The Quest for Network Stability

Informally, a “stable state’’ is a global routing state that, once reached by BGP, remains unchanged. Researchers seek conditions (on the network and ranking functions) that ensure BGP safety, i.e., guaranteed BGP convergence to a stable state (for every schedule). In a landmark paper, Lixin Gao and Jennifer Rexford proposed simple guidelines that are naturally induced by ASes’ business relationships and are sufficient for BGP safety.

Challenge II: Incentivizing ASes to Adhere to BGP

Internet Service Providers (ISPs) like AT&T and Comcast make revenue from selling connectivity to customers. Can an ISP do better for itself (and its customers) by not executing BGP? That is, can an AS better its routing outcome by “deviating’’ from BGP? Joan Feigenbaum, Christos Papadimitiou, Rahul Sami, and Scott Shenker initiated an economic, or “mechanism design’’, approach to BGP.

This entry was posted in Computer Science and Optimization, Economics, Guest blogger and tagged , , , . Bookmark the permalink.

4 Responses to Michael Schapira: Internet Routing, Distributed Computation, Game Dynamics and Mechanism Design I

  1. Gil says:

    For a review of the last decade events in the interface between computer science and economics see this post http://agtb.wordpress.com/2009/12/31/agt-decade-in-review/ in Noam Nisan’s blog. Noam’s blog is mainly devoted to this area.

  2. Pingback: Tweets that mention Michael Schapira: Internet Routing, Distributed Computation, Game Dynamics and Mechanism Design I « Combinatorics and more -- Topsy.com

  3. Pingback: Biweekly Links – 01/04/2010 « God, Your Book Is Great !!

  4. Pingback: Michael Schapira: Internet Routing, Distributed Computation, Game Dynamics and Mechanism Design II « Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s