A Fractional BGP Game
01 January 2008
The Border Gateway Protocol (BGP) is the interdomain routing protocol used in the internet. BGP is a protocol for enabling policy based routing. That is, BGP allows network administrators to encode their routing policies, which are in turn based on the economic contracts, called Service Level Agreements (SLAs), that have been formed between neighboring networks. The conflicting economic goals of the different domains can cause BGP to fail to converge. In order to study properties of BGP such as convergence, BGP has been modeled as a static graph problem called the Stable Paths Problem (SPP). In turn SPP can be thought of in game theoretic terms. In particular, stable routings established by an instance of BGP correspond to the solutions of the equivalent instance of SPP which in turn correspond to the Nash equilibria of the equivalent non-cooperative game. Since BGP can fail to converge, SPP can fail to have a solution and hence the corresponding game can fail to have Nash equilibria. We define a fractional version of SPP and its corresponding fractional game and show that all such instances of fractional SPP have solutions, and so all corresponding fractional games have Nash equilibria. We also show that while these solutions exist they are not necessarily half-integral.
