A Distributed Protocol for Fractional Stable Paths Problem

Content Provider	Semantic Scholar
Author	Kintali, Shiva
Copyright Year	2008
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 define a game-theoretic model for FSPP and present a relation between -Nash and -stable solution.
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://www.cs.princeton.edu/~kintali/papers/fspp.pdf
Alternate Webpage(s)	http://smartech.gatech.edu/bitstream/handle/1853/25466/GT-CS-08-06.pdf?sequence=1
Alternate Webpage(s)	http://www.cc.gatech.edu/~kintali/papers/fspp.pdf
Alternate Webpage(s)	http://shivakintali.org/papers/fspp.pdf
Alternate Webpage(s)	http://smartech.gatech.edu/bitstream/1853/25466/1/GT-CS-08-06.pdf
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article