DIMACS TR: 2008-02
Towards a Realistic Model of Incentives in Interdomain Routing: Decoupling Forwarding from Signaling
Authors: Aaron D. Jaggard, Vijay Ramachandran and Rebecca N. Wright
ABSTRACT
We model the task of interdomain routing---the task of connecting the networks that compose the Internet---as an iterative, highly distributed, asynchronous game. Unlike previous examinations of this game that assumed quasi-linear utilities, we assume that each node has a quasi-bilinear utility depending not only on the route it believes it is assigned in the outcome, but also on other
nodes assigned to route through it. This more realistic model captures out-of-band business relationships that may affect nodes'behavior in the game and the difficulty of monitoring traffic flows
on the Internet. We show by example that conditions that guarantee incentive compatibility when utility does not depend on signaling do not provide this assurance in the model we study. We also extend
the Stable Paths Problem to decouple forwarding from signaling and show that this allows stable signaling solutions to have forwarding loops, and we give a sufficient condition to prevent this. Finally, we provide positive results about incentive compatibility when using utility functions that depend on both forwarding and signaling; this relies on nodes having next-hop policies (so that their
forwarding preferences depend only on the next hops of available routes) and certain other assumptions. In conjunction with these results, we provide examples of networks that violate these conditions and in which nodes have incentive to lie about their chosen paths.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2008/2008-02.pdf
DIMACS Home Page