"Incentives for Honest Behavior in Interdomain Routing with BGP"

Speaker: Sharon Goldberg, CS Department, Princeton University
Date: Thursday, 10 April 2008
Time: 2pm
Place: Ross 201

Abstract:

Interdomain routing on the Internet consists of a control plane, where  
Autonomous Systems (ASes) discover and establish routes via the Border  
Gateway Protocol (BGP), and a data plane, where they actually forward  
packets along these routes.   While the basic goal of the Internet is  
reliable packet delivery, in this work we explicitly consider an  
additional goal that has been implicit in many previous works; namely,  
finding incentives to ensure that, in BGP, ASes honestly announce the  
paths that they actually use to send packets in the data plane.

We take a game-theoretic approach by assuming that ASes will  
dishonestly announce paths only if doing so improves their own routing  
outcomes, and use mechanism design to find classes of routing policies  
and protocols that remove ASes incentive to lie.  In contrast to  
previous work, we assume that a `rational' AS not only cares about  
getting the best possible outgoing path for its traffic to the  
destination, but also about attracting incoming traffic, either out of  
greed (since other ASes pay it to carry their traffic), or malice (so  
it can eavesdrop, spoof or tamper with packets).

We find that while protocols like Secure BGP are necessary, they are
in general not sufficient unless ASes are only interested in the next
hop that their traffic takes to its destination. Our analysis
highlights the high cost of guaranteeing that paths announced during
the BGP protocol match the true paths that packets take through the
Internet, and suggest that it will be difficult to provide this
guarantee without resorting to expensive enforcement protocols.

This is joint work with Shai Halevi (IBM Research).