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

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

In thse two post, I 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.

A brief reminder from post 1:

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.

We brefly mentioned two main challenges in this area. The first is the quest for network stability, and the second was giving  agents incentives to “behave well”. We will discuss here these challenges in more detail.  

Challenge I: The Quest for Network Stability

Informally, a “stable state’’ is a global routing state that, once reached by BGP, remains unchanged. Formally, a stable state is an assignment of routes R1,…,Rn to the n source nodes (d is assigned the “empty route’’ Rd=Ø) such that for every node i (1) there is a node j such that Ri=(i,j)Rj, where (i,j) Rj is the route that has (i,j) as a first link and then follows Rj to d; and (2) for every node j such that Ri≠(i,j)Rj, and (i,j)Rj is simple, it holds that Ri >i (i,j)Rj.

Observe that a stable state (in a connected graph) is always in the form of a spanning tree rooted in d. BGP “convergence’’ to a stable state is of paramount importance and has received much attention (BGP “oscillations’’ make the network unpredictable and hard to debug, and can lead to the flooding of the network with update messages). Unfortunately, even in simple networks a stable state might not even exist, and hence BGP is bound to oscillate indefinitely. The reader can verify that this is indeed the case for the simple network in the following figure (BAD GADGET from here).


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, Gao and Rexford proposed simple guidelines that are naturally induced by ASes’ business relationships and are sufficient for BGP safety.

Recently, Rahul Sami, Michael Schapira and Aviv Zohar presented the first non-trivial necessary condition for BGP safety:

Theorem: If two stable states (or more) exist in a network then BGP is not safe on that network.

That is, if there are multiple stable states then there is a schedule of ASes’ activations for which BGP will never reach a stable state.

Aaron Jaggard, Michael Schapira and Rebecca Wright strengthened this result in work that also has applications to game dynamics in general, distributed computation, social networks, and Boolean circuits.

Bridging the gaps between the known sufficient and necessary conditions, and characterizing BGP safety, is an interesting (and long-standing) open question. More generally, there is still much to understand regarding “historyless’’ asynchronous interaction in both computational and game-theoretic environments (see here and references therein).

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. Unfortunately, as shown by Hagay Levin, Michael Schapira, and Aviv Zohar, BGP is not incentive-compatible even on very small and realistic networks. One main reason for this is that, in practice, nodes do not have a global view of the network and learn about neighbours’ routes via update messages.

Consider, for example, the small network in the following figure (from here). Observe that node 2’s most preferred route (2md) does not actually exist in the network (say, due to a recent link failure). The reader can verify that there is but one stable state in the network (in which nodes 1, 2 and m, use routes 12d, 2d and m12d, respectively). Moreover, BGP safety holds for this network.  However, observe that if node m falsely announces to node 2 that it is sending traffic via the direct route md, and both 1 and 2 execute BGP, then in the resulting routing state 1 will no longer route through 12d (because 2 will forward traffic to m) and will be forced to settle for 1d, thus enabling m to use its most preferred route m1d. Thus, m can benefit from “dishonest’’ behaviour.


To overcome this challenge, three distinct approaches have been taken.

1)     Incentivize ASes via payments. Starting in the work of Feigenbaum et al., researchers have been looking at ways to implement distributed (VCG-based) payment mechanisms that guarantee incentive-compatibility. Many negative results (see here and here), and a positive one, are known.

2)     Restrict ASes’ ranking functions to obtain incentive-compatibility without payments. Obtaining incentive-compatibility without money is a relatively rare phenomenon in mechanism design. However, this is achievable in non-trivial interdomain routing environments, as shown here.

3)     Combining security and incentives. Observe that in Fig. 2 node m’s manipulation of BGP would not have been possible had node 2 been able to verify that a route announced to it by node m is indeed available to m. Recently, Levin et al. have shown that if such “Route Verification’’ is achievable then BGP is incentive-compatible in realistic environments. Fortunately, Route Verification can, in fact, be achieved via well known security enhancements of BGP (using cryptographic machinery). Sharon Goldberg, Shai Halevi, Aaron Jaggard, Vijay Ramachandran, and Rebecca Wright further explored the interesting connections between security and incentives in interdomain routing.

Despite much progress, we still do not have a good understanding of the possibility/impossibility borderline for incentive-compatible route computation with BGP. This suggests many interesting directions for future research (see some concrete questions here). In addition, the general connections between mechanism design and security research (two research agendas that handle non-compliant behaviour) are yet to be explored.

About these ads
This entry was posted in Computer Science and Optimization, Economics. Bookmark the permalink.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s