30-10-2012, 05:07 PM
The Stable Paths Problem and Interdomain Routing
The Stable Paths Problem.pdf (Size: 404.41 KB / Downloads: 16)
Abstract
Dynamic routing protocols such as RIP and OSPF essentially
implement distributed algorithms for solving the shortest
paths problem. The border gateway protocol (BGP) is currently
the only interdomain routing protocol deployed in the Internet.
BGP does not solve a shortest paths problem since any interdomain
protocol is required to allow policy-based metrics to override distance-
based metrics and enable autonomous systems to independently
define their routing policies with little or no global coordination.
It is then natural to ask if BGP can be viewed as a distributed
algorithm for solving some fundamental problem. We introduce
the stable paths problem and show that BGP can be viewed as a
distributed algorithm for solving this problem. Unlike a shortest
path tree, such a solution does not represent a global optimum, but
rather an equilibrium point in which each node is assigned its local
optimum.
We study the stable paths problem using a derived structure
called a dispute wheel, representing conflicting routing policies at
various nodes.We showthat if no dispute wheel can be constructed,
then there exists a unique solution for the stable paths problem.
We define the simple path vector protocol (SPVP), a distributed algorithm
for solving the stable paths problem. SPVP is intended to
capture the dynamic behavior of BGP at an abstract level. If SPVP
converges, then the resulting state corresponds to a stable paths solution.
If there is no solution, then SPVP always diverges. In fact,
SPVP can even diverge when a solution exists.We show that SPVP
will converge to the unique solution of an instance of the stable
paths problem if no dispute wheel exists.
INTRODUCTION
THE BORDER gateway protocol (BGP) is currently the
only interdomain routing protocol employed on the Internet
[13], [18], [19]. BGP allows each autonomous system to
independently formulate its routing policies, and it allows these
policies to override distance metrics in favor of policy concerns.
In contrast to pure distance-vector protocols such as RIP [2],
[14], BGP is not safe in the sense that routing policies can conflict
in a manner that causes BGP to diverge, resulting in persistent
route oscillations [21]. Moreover, the safety of BGP routing
policies may not be robust with respect to network failures. Recent
studies have highlighted the adverse effects of interdomain
routing instability [16], [17]. Although it is not known if any
of the observed BGP instability has been caused by policy conflicts,
in the worst case such conflicts could introduce extreme
oscillations into the global routing system.
Related Work
Bertsekas et al. [1] prove convergence for a distributed version
of the Bellman–Ford shortest path algorithm. Because of
the differences between BGP and shortest path routing mentioned
above, these results do not directly apply to a protocol
such as BGP.
In Varadhan et al. [21], the convergence properties of an abstraction
of BGP is studied. They describe a system (similar to
BAD GADGET of Fig. 2) as an example of policies which lead
to divergence. In their setting, a node must update each time it
receives a new route-to-origin “advertisement” from one of its
neighbors. This is in contrast to our model where an arbitrary update
sequence determines when nodes process their neighbor’s
path choices. They also define the notion of an auxiliary graph,
called a return graph, to study convergence. Return graphs are
defined only for systems with a ring topology, and a restricted
set of allowable paths at each node, namely the counterclockwise
paths. A return graph is defined as follows. For a node
and two permitted paths from to 0, they define an arc
if when storing at , and updating the nodes clockwise
around the ring, the node adopts when is considered again.
Thus return graphs are defined by the dynamic behavior of the
system for a particular activation sequence whereas the dispute
wheels defined in this paper is based purely on the static nature
of the local preference functions of the nodes in the system. In
addition, we consider a more general evaluation model, more
general topologies, and arbitrary ranking of permitted paths.
SIMPLE PATH VECTOR PROTOCOL (SPVP)
This section presents a simple path vector protocol (SPVP)
for solving the stable paths problem in a distributed manner.
SPVP represents an abstract version of the existing BGP
protocol. This protocol always diverges when a stable paths
problem has no solution. It can also diverge for stable path
problems that are solvable. The protocol SPVP defined below
differs from the simpler model of evaluation presented in [10],
[11]. Here, we use a message processing framework which
employs a reliable first-in-first-out (FIFO) queue of messages
for communication between peers.
Complexity of SPP Solvability
We now investigate the computational complexity of determining
if a solution exists for an instance of the stable paths
problem. For a review of complexity theory, see [5].
Theorem V.1: The problem of determining whether an instance
of the stable paths problem is solvable is NP-complete.
Proof: We begin by noting that this problem is in NP, since
we only need to guess a path assignment and check that it is
indeed stable. This can clearly be done in time polynomial in
the size of the instance of SPP.
The rest of the proof relies on a reduction from 3-SAT, a
well-known NP-complete problem. An instance of 3-SAT consists
of a set of Boolean variables and a formula based on these
variables and their negations where the formula has the form of
a conjunction of terms each of which is a disjunction of three
literals (a literal is either a variable or its negation ). The
3-SAT} problem asks if there exists a satisfying assignment for
a given instance.