A Distributed Protocol for Fractional Stable Paths Problem

Abstract

The Border Gateway Protocol (BGP) is currently the only interdomain routing protocol deployed in the Internet. BGP can be viewed as a distributed algorithm for solving the Stable Paths Problem (SPP) [4]. Not every instance of SPP has a stable solution. The most general condition known to guarantee stability of SPP is the absence of dispute wheel, proposed by Griffin, Shepherd and Wilfong [4]. They also defined the Simple Path Vector Protocol (SPVP), a distributed algorithm for solving SPP. SPVP is sensitive to timing issues and can diverge even when a stable solution exists [4]. Recently, Haxell and Wilfong [5] defined a fractional version of SPP and showed that every instance of fractional-SPP (FSPP) has a stable solution. But their proof was non-constructive. In this paper, we define є-stable solution of FSPP and present a distributed protocol that always converges to an є-stable solution of an FSPP instance, for any given є > 0. We definne a game-theoretic model for FSPP and present a relation between є-Nash and є-stable solution.