Paper Info
Title
A fractional model of the border gateway protocol (BGP)
Abstract
The Border Gateway Protocol (BGP) is the interdomain routing protocol used to exchange routing information between Autonomous Systems (ASes) in the internet today. While intradomain routing protocols such as RIP are basically distributed algorithms for solving shortest path problems, the graph theoretic problem that BGP is trying to solve is called the stable paths problem (SPP). Unfortunately, unlike shortest path problems, it has been shown that instances of SPP can fail to have a solution and so BGP can fail to converge. We define a fractional version of SPP and show that all such instances of fractional SPP have solutions. We also show that while these solutions exist they are not necessarily half-integral.
Year
DOI
Venue
2008
10.5555/1347082.1347104
SODA
Keywords
DocType
ISBN
fractional model,fractional spp,shortest path problem,border gateway protocol,autonomous systems,interdomain routing protocol,intradomain routing protocol,graph theoretic problem,stable paths problem,fractional version,distributed algorithm,routing protocol
Conference
978-0-89871-698-6
Citations 
PageRank 
References 
11
0.83
5
Authors
2
Name
Order
Citations
PageRank
P. E. Haxell121226.40
G. T. Wilfong2131.21