| Title: | A Distributed Protocol for Fractional Stable Paths Problem |
| Author: | Kintali, Shiva |
| 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. |
| Type: | Technical Report |
| URI: | http://hdl.handle.net/1853/25466 |
| Date: | 2008 |
| Contributor: |
Georgia Institute of Technology. College of Computing
Georgia Institute of Technology. School of Computer Science |
| Relation: | SCS Technical Report ; GT-CS-08-06 |
| Publisher: | Georgia Institute of Technology |
| Subject: |
Border Gateway Protocol (BGP)
Fractional routing Interdomain routing Path vector protocol Routing games Stable paths problem |
| Files | Size | Format | View |
|---|---|---|---|
| GT-CS-08-06.pdf | 169.8Kb |
View/
|
