Show simple item record

dc.contributor.authorKintali, Shiva
dc.date.accessioned2008-11-07T21:24:34Z
dc.date.available2008-11-07T21:24:34Z
dc.date.issued2008
dc.identifier.urihttp://hdl.handle.net/1853/25466
dc.description.abstractThe 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.en
dc.language.isoen_USen
dc.publisherGeorgia Institute of Technologyen
dc.relation.ispartofseriesSCS Technical Report ; GT-CS-08-06en
dc.subjectBorder Gateway Protocol (BGP)en
dc.subjectFractional routingen
dc.subjectInterdomain routingen
dc.subjectPath vector protocolen
dc.subjectRouting gamesen
dc.subjectStable paths problemen
dc.titleA Distributed Protocol for Fractional Stable Paths Problemen
dc.typeTechnical Reporten
dc.contributor.corporatenameGeorgia Institute of Technology. College of Computing
dc.contributor.corporatenameGeorgia Institute of Technology. School of Computer Science


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record