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   Continue reading