A Distributed Protocol for Fractional Stable Paths Problem
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) . 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 . 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 . Recently, Haxell and Wilfong  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.