The Border Gateway Protocol, BGP, is currently the
Policy Disputes in Path-Vector Protocols Timothy G.Grif?n F.Bruce Shepherd Gordon Wilfong griffin,bshep,gtw@https://www.wendangku.net/doc/7b13677207.html, Bell Laboratories,Lucent Technologies
Abstract
The Border Gateway Protocol,BGP,is currently the only interdomain routing protocol employed on the Inter-net.As required of any interdomain protocol,BGP al-lows policy-based metrics to override distance-based met-rics and enables each autonomous system to independently de?ne its routing policies with little or no global coordi-nation.Varadhan et al.[11]have shown that there are collections of routing policies that together are not safe in the sense that they can cause BGP to diverge.That is,an unsafe collection of routing policies can result in some au-tonomous systems exchanging BGP routing messages indef-initely,without ever converging to a set of stable routes.In this paper we present suf?cient conditions on routing poli-cies that guarantee BGP safety.We use a new formalism, called the Simple Path Vector Protocol(SPVP),that is de-signed to capture the underlying semantics of any path vec-tor protocol such as BGP.We identify a certain circular set of relationships between routing policies at various au-tonomous systems that we call a dispute cycle.We show that systems with no dispute cycles are guaranteed to be safe.While these include systems whose policies are con-sistent with shortest paths under some link metric,the class of systems with no dispute cycles is strictly larger.
1Introduction
BGP[9,7,10]allows each autonomous system to inde-pendently formulate its routing policies,and it allows these policies to override distance metrics in favor of policy con-cerns.In contrast to pure distance-vector protocols such as RIP[8],Varadhan et al.[11]have shown that there are rout-ing policies that are unsafe in the sense that they can cause BGP to diverge.Although it seems that BGP divergence has not yet occurred in practice,it could potentially introduce a great deal of instability into the global routing system.
The goal of this paper is to clarify the nature of BGP pol-icy inconsistencies that can give rise to protocol divergence. Our main contributions can be summarized as follows.We introduce a general formalism,called the Simple Path Vec-tor Protocol(SPVP),that is designed to capture the under-lying semantics of any path vector protocol such as BGP. We de?ne a dispute cycle whose arcs correspond to a cer-tain type of policy dispute.We show that systems with no dispute cycles are guaranteed to be safe.While these in-clude systems whose policies are consistent with shortest paths under some link metric,the class of systems with no dispute cycles is strictly larger.
The paper is organized as follows.In Section2we de?ne the Simpli?ed Path-Vector Protocol(SPVP).In an SPVP speci?cation each node(representing an autonomous sys-tem)has a list of permitted paths to a destination,together with a ranking of these paths.Solutions to such speci?ca-tions are de?ned to be routing trees that satisfy certain sta-bility conditions.We de?ne a model of dynamic evaluation whose stable states correspond to such solutions.
In Section3we de?ne two equivalent structures,the dis-pute wheel and the dispute cycle,that capture a certain type of circular policy inconsistency.We show that an SPVP speci?cation with no dispute cycle(no dispute wheel)al-ways has a unique solution.In addition,we show that such a speci?cation is safe and so its dynamic evaluation will al-ways arrive at a stable state.
BGP is different from shortest path routing for several reasons.First,the relative ranking of routes in BGP is not, in general,based on path lengths,or any other universally agreed upon cost function.Second,each autonomous sys-tem can reject paths arbitrarily(even shortest paths)based on policy considerations.Even so,it seems a natural ques-tion to ask which policies are consistent with an edge cost function.We explore this question in Section4.We in-troduce the concept of an SPVP speci?cation being con-sistent with a given edge cost function.Even in this case, one may?nd routing trees that are not shortest path trees with respect to the cost function.However,we show that any SPVP speci?cation that is consistent with a cost func-tion without non-positive cycles will be safe.An immedi-ate consequence of this is that BGP con?gurations that are simply based on“hop count”are safe(even with“padding”of AS-paths).On the other hand,we show that BGP-like
systems can actually violate“distance metrics”and remain safe.Finally,Section5suggests some problems for fu-ture work.Full proofs for those omitted here can be found in[5].
1.1Related Work
Bertsekas et al.[1]prove convergence for a distributed version of the Bellman-Ford shortest path algorithm.Be-cause of the differences between BGP and shortest path routing mentioned above,these results do not directly ap-ply to a protocol such as BGP.
In Varadhan et al.[11],the convergence properties of an abstraction of BGP is studied.They describe a system similar to our BAD GADGET,for instance,as a simple example of policies which lead to divergence.In their set-ting,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 the update sequence de-termines when nodes process their neighbor’s path choices. They also de?ne the notion of an auxiliary graph,called a return graph,to study convergence.Return graphs are de-?ned only for systems with a particular topology,namely a ring topology,and a restricted set of allowable paths at each node,namely only counterclockwise paths.A return graph is de?ned as follows.For a node and two permitted paths from to,we de?ne an arc if when storing at,and updating the nodes clockwise around the ring,the node adopts when is once again reached.
Gouda and Schneider[2,3]have studied metrics which always have a maximal tree,that is,a tree in which every node has its‘favorite’path to the origin,contained in the tree.Their notion of a maximal tree is different from the central notion of a stable tree introduced in Section2.2.The latter is based on reaching a local,as opposed to a global, equilibrium.Roughly speaking,a metric in their work cor-responds to a method for ranking paths based on edge costs. They characterize metrics which admit a maximal tree for any graph and any possible cost function.
2A Simple Path-Vector Protocol
This section introduces a framework,called the Simple Path Vector Protocol(SPVP),that is designed to capture the underlying semantics of any path vector protocol such as BGP.The intent is to strip away all but the essentials from BGP,leaving only the basic notions of permitted paths to a destination and the ranking of those paths.We seek to study the safety of routing policies in a manner independent of the details used to implement those policies(for example,BGP attributes and import and export transformations).In mod-eling BGP we make several simplifying assumptions.First, we ignore all issues relating to internal BGP(iBGP).As a corollary to this,we assume that there is at most one link between any two autonomous systems.Second,we ignore address aggregation.We believe that these simpli?cations are not of fundamental importance,and we adopt them in order to improve the clarity of the statements and proofs.
2.1BGP Route Selection
In order to motivate the SPVP formalism,we brie?y re-view the route selection process of BGP[9,7,10].BGP employs a large number of attributes to convey information about each destination.For example,one BGP attribute records the path of all autonomous systems that the route announcement has traversed.For these reasons BGP is of-ten referred to as a path vector protocol.The BGP attributes are used by import policies and export policies at each au-tonomous system in order to implement its routing policies.
In BGP,route announcements are records that include the following attributes.
:network layer reachability information
(address block for a set of destinations)
:next hop(address of next hop router)
:ordered list of vertices traversed
:local preference
:multi-exit discriminator
:set of community tags
The local preference attribute is not passed be-tween autonomous systems,but is used internally within an autonomous system to assign a local degree of preference. Each record is associated with a4-tuple,rank-tuple, de?ned as
For a given destination,the records with are ranked using lexical ordering on rank-tuple.The best route selection procedure for BGP[9]picks routes with the highest rank.In other words,if two route records share the same value,then the record with the highest lo-cal preference is most preferred.If local preference values are equal,then the record with the shortest is pre-ferred.If these paths have the same length,then the record with the lowest value is preferred.Finally,ties are broken with preference given to the record with the lowest IP address for its value.Note that this ordering is“strict”in the sense that if two records are ranked equally,then.Route selec-tion based on highest rank is always deterministic since at any time there is at most one route record with a given and a given.
A route transformation is a function on route records,
,that operates by deleting,inserting,or modi-fying the attribute values of.If(the empty record),then we say that has been?ltered out by.
Suppose and are autonomous systems with a BGP peering relationship.As a record moves from to it undergoes three transformations.First,export represents the application of export policies(de?ned by)to.Second,PVT is the BGP-speci?c path vector transformation that adds to the of and?lters out the record if its con-tains.Finally,import represents the application of import policies(de?ned at)to.In par-ticular,this is the function that assigns a value for.We call the composition of these transformations the peering transformation,pt,de?ned as import PVT export
Suppose autonomous system is originating a destina-tion by sending a route record with to (some of)its peers.If is an autonomous system and
is a simple path where each pair of autonomous systems,are BGP peers,then we de?ne,the route record received at from along path,to be
pt pt pt
We say that is permitted at when.We can then de?ne a ranking function,,on AS-paths permitted at as lex-rank rank-tuple.
The SPVP formalism de?ned below is based on the no-tion of permitted paths and ranking functions on these paths. In terms of BGP,we can think of SPVP as capturing the semantics that translate the apparent routing policies at au-tonomous system(the import and export policies de?ned at)into the actual routing policies at.Note that the actual routing policies at are the result of the interac-tion between routing policies of many,possibly distant,au-tonomous systems.
2.2SPVP Speci?cations
A simple,undirected,connected graph rep-resents a network of nodes connected by edges.For any node,peers
is the set of peers for.We assume that node,called the origin,is special in that it is the destination to which all other nodes will attempt to establish a path.
A path in is a sequence,,of nodes such that for each,is an edge in.The empty path is written.We assume that all non-empty paths
implicitly have a direction from the?rst node to the last node.Suppose
is an edge in.If node is the?rst node of path,then denotes the path that starts at node,traverses edge ,and then follows path.
If and are non-empty paths such that the?rst node in is the same as the last node in,then denotes the path formed by the concatenation of these paths.We extend this with the convention that,for any path .For a simple path and for any with we denote by the subpath
.
For each,let be the set of permitted paths from to the origin(node).If is a path from to the origin and,then is said to be rejected at node .If is in,then the node is called the next hop for path.Let be the set of all permitted paths to the origin.
For each,there is a non-negative,integer-valued ranking function representing how node ranks its permitted paths.If and
,then is said to be preferred over.Let
.An SPVP speci?cation, ,is a graph together with the permitted paths at each non-zero node and the ranking functions for each non-zero node.
We impose the following restrictions on and. (empty path is permitted)for each,, (empty path is lowest ranked)for each,
,
(strictness)if,then or there is
a such that and(paths
and have the same next-hop). (simplicity)if path,then is a simple path(no repeated nodes),
(consistency of permitted paths)If and is in,then.
Paths correspond to BGP’s attribute.Unlike BGP however,in SPVP the number is prepended to all paths at node.This merely simpli?es the exposition.The “consistency of permitted paths”is also not an essential condition,since any speci?cation that does not satisfy it can easily be transformed into one that does.
Let be an SPVP speci?cation.A routing tree is a vector of paths with ,such that the union of these paths is a tree.Note that some of the may be the empty path.Node is stable with respect to this tree if whenever .A tree is stable if every node is stable.
An SPVP speci?cation is called solvable if there exists a stable routing tree for.Otherwise,is called unsolvable.A stable routing tree is called a solu-tion for the speci?cation.
2 0
2 1 01
3 01 0
4 3 04 2 0
3 0
2 02 1 01
3 01 0
4 3 04 2 0
2 02 1 01
3 01 0
3 0
4 2 04 3 0
3 4 2 03 0
3 4 2 0
(a)GOOD GADGET
(b)(c)
NAUGHTY GADGET
(d)
BAD GADGET
A routing tree
Figure 1.Examples of SPVP speci?cations.
Grif?n and Wilfong [6]have shown that statically de-tecting solvability for real-world BGP is NP-hard.Simi-larly,[5]shows that the basic question of solvability is still NP-complete for the more abstract model of SPVP .
Figure 1(a)presents an SPVP speci?cation called GOOD GADGET .The ranking function for each non-zero node is depicted as a vertical list next to the node,with the highest ranked path at the top going down to the lowest ranked non-empty path at the bottom.The routing tree
is a solution for this speci?cation,and it is illustrated in Figure 1(b).The dynamic model of SPVP ,de?ned below,will always converge to this solution.Also,this is the only solution for GOOD GADGET since any other routing tree is not stable.For example,in the tree
nodes and would both prefer to change their paths to ones of higher rank.A modi?cation of GOOD GAD -GET ,called NAUGHTY GADGET ,is shown in Figure 1(c).NAUGHTY GADGET adds one permitted path for node ,yet it has the same unique solution as GOOD GAD -GET .However,as is explained below,the dynamic evalua-tion of this speci?cation can diverge.Finally,by reordering the ranking of paths at node ,we produce a speci?cation called BAD GADGET ,presented in Figure 1(d).This speci?-cation,which is similar to examples of [11],has no solution and its dynamic evaluation will always diverge.
2.3A Simple Dynamic Model
We now present a simpli?ed model of distributed evalua-tion that ignores the implementation details related to mes-sage queues and message passing.This model was used in [6],but with a different speci?cation language.This model is equivalent to a special case of a more general mes-sage passing model,where it is assumed that each node performs an atomic step that processes all of its message queues,computes any changes to best routes,and sends up-date messages to all of its peers.
A state for a speci?cation is a vector
of paths where .Note that
states do not always represent trees.We say that path is stored at node in this state,and we also say that the trivial path is always stored at node .The system moves from state to state as nodes update .When a node updates it can replace its current path with a path of higher rank,if such a path is available.It can also lose its path,if it is no longer available from its next hop,and be forced to accept a path of lower rank.
To formalize this,we de?ne the set of choices that a node has when it updates,how it chooses a best path,and how it updates.The choice of paths for node in state
is the set ,which is de-?ned to be all such that either and
or for some .There
is one best choice in any state ,,de?ned to be
the unique
such that is maximal,if is not empty.Otherwise,is the empty path.
In order to model asynchronous routing processes we al-low multiple nodes to update simultaneously.Let be non-empty,and be a state.Then state is reached from by updating the nodes of if
if
,(does not update)
otherwise.
We use the notation to denote this state transition.
For example,
is a state transition for BAD GADGET .A state is stable if for each
we have ,or equivalently,if
for every set .Informally,in a stable state there is no node that could pick a path better than its current path.It is easy to show that any stable state must contain a solution (a stable routing tree).
Figure2.A strongly connected component
from the evaluation digraph of NAUGHTY GAD-
GET.
The evaluation digraph of a speci?cation
,denoted,is a labeled directed graph having one node for each possible state.If,then
there is an arc from the node representing to the node rep-resenting labeled.A cycle in is a sequence of states
where.This cycle is non-trivial if it contains no self loops.It is clear that if contains a non-trivial cycle,then the speci?cation can diverge.
An update sequence is a function such that, for each.From any starting state the function de?nes an in?nite path in composed of arcs .We write to denote.
A speci?cation is said to converge with update se-quence and initial state,written,if there is some time such that is a stable state.Other-wise,is said to diverge with and initial state,written .An update sequence is fair if each node,
for in?nitely many’s.A system is said to be safe if for every fair and every initial state.
The speci?cation GOOD GADGET is safe.On the other hand,NAUGHTY GADGET is solvable,but not safe.The evaluation digraph of NAUGHTY GADGET has81states. Figure2shows a strongly connected component from this digraph.For readability we have not labeled arcs,and we do not show parallel arcs nor self loops().Any update sequence that remains within this strongly connected com-ponent will diverge.Finally,BAD GADGET will diverge for any update sequence.
3Suf?cient Conditions
In this section we develop a suf?cient condition that will guarantee that an SPVP speci?cation has a unique solution and is safe.The suf?cient condition concerns the absence of a circular set of relationships between ranking functions that we call a dispute cycle.The structure of dispute cy-cles is further elucidated with the de?nition of an equivalent structure called a dispute wheel.
3.1The Dispute Digraph
For any speci?cation we construct a di-rected graph,,called the dispute digraph.For each permitted path of there is a node in labeled. There are two kinds of arcs in the dispute digraph,trans-mission arcs and dispute arcs.
Figure3.Conditions for dispute arc. Suppose that nodes and are peers.If is a permitted path at and is a permitted path at,then a dispute arc from path to path,denoted,represents a local policy dispute between peers and concerning the rela-tive ranking of paths https://www.wendangku.net/doc/7b13677207.html,rmally,it represents the fact that node could increase the rank of its best path by abandoning and adopting,while this action would
force to abandon path and select as its best path one that could potentially have lower rank than .More formally,
is a dispute arc if and only if the following condi-tions hold :
1.
is a permitted path from
to with next-hop ,
2.is a path from
to ,permitted at ,
3.path is rejected at ,or
,
4.
.
Figure 3illustrates these conditions.There is a transmission arc from to ,denoted
,when nodes and are peers,is
permitted at ,and is permitted at .Informally,
might be read as “node permits path ,
which allows to permit path ”.Figure 4shows the dispute digraphs for the speci?cations of Figure 1.Again,the dotted arcs are transmission arcs,while the solid arcs are dispute arcs.
(a)
3 0
4 2 04 3 0
2 0
2 1 0 1 0
1 3 0
3 0
4 2 04 3 0
2 0
2 1 0 1 0
1 3 0
3 4 2 0
(c)
3 0
4 2 04 3 0
2 0
2 1 0 1 01
3 0
(b)
3 4 2 0
Figure 4.Dispute digraphs for (a)GOOD ,(b)NAUGHTY ,and (c)BAD GADGET .
A directed path in
is of the form
where ,and each represents a dispute arc or a transmission arc.A directed path contains a cycle if
for some .We usually refer to cycles in the
dispute digraph as dispute cycles .
Lemma 3.1Any dispute cycle must contain at least two dispute arcs.
From Figure 4we see that the dispute digraph of GOOD GADGET has no cycles,while the dispute digraph of NAUGHTY GADGET contains the simple cycles
and
The second cycle is also contained in the dispute digraph of BAD GADGET .
3.2Dispute Wheels
We now give an alternate representation of dispute cycles in terms of structures called dispute wheels .While dispute cycles are built from local relationships between the rank-ing functions of peers,dipute wheels are based on “long distance”relationships.
A dispute wheel,
,of size ,is a set of nodes ,and sets of paths
and ,such
that for each we have (1)is a path from to ,(2),(3),and (4)
.When discussing dispute wheels,
all subscripts are to be interpreted modulo .See Figure 5for an illustration of a dispute wheel.Since permitted paths are simple,it follows that the size of any dispute wheel is at least
.
Figure 5.A dispute wheel of size .
The rim of a dispute wheel is the (possibly non-simple)path ,which is a (possibly non-simple)cycle in the graph .A rim fragment is any path of the form ,where and
.
A dispute wheel,is a sub-wheel of a dispute wheel if,,and each is a rim fragment of.
A minimal dispute wheel is one in which for each
,either is not permitted at,or
.Note that any dispute wheel of size is minimal.
Lemma3.2Every dispute wheel contains a minimal sub-wheel.
Proof:Suppose that is a dispute wheel that is not min-imal.Then for some in we have
.Create a sub-wheel of size by deleting and,and replacing path with rim fragment.Repeating this process must eventually arrive at a minimal sub-wheel.
We now show that dispute wheels are equivalent to dis-pute cycles.We can extend the notion of a dispute arc to “distant disputes”in the following way.Let be a path permitted at,where is a path permitted at some node.Suppose that is also permitted at,and we have
1.path is rejected at,or,
2..
We write when these conditions hold.
Lemma3.3If,then there is a path in the dispute digraph from to of length.
Corollary3.4Suppose that is a minimal dispute wheel of size.Then
and so there is a directed cycle in the dispute digraph. Lemma3.5If the dispute digraph contains a cycle, then has a dispute wheel.
Corollary3.6A speci?cation has a dispute wheel if and only if the dispute digraph contains a cycle.
3.3Two Trees Imply a Dispute Wheel
In general,an SPVP speci?cation may have more than one solution.We show that in this case the dispute digraph has a cycle.
Although a solution is not always a spanning tree,it of-ten simpli?es proofs to assume that all solutions of are spanning trees.For any speci?cation we can construct an essentially equivalent speci?cation all of whose solu-tions are spanning trees.Add a new node adjacent to for which is its only permitted path.Also add the edge
for each and make the unique path whose-ranking is greater than,and modify so that this is less than all other paths in.This allows us to use the following fact.
Fact3.7For any speci?cation there is a1-1mapping be-tween its solutions and those https://www.wendangku.net/doc/7b13677207.html,ly,for for each solution for there is a unique solution for such that is a subtree of.
Theorem3.8If a speci?cation has more than one solu-tion,then it has a dispute wheel.
Proof:Suppose has two distinct solutions
and.We repre-sent the two stable con?gurations as two trees rooted at the https://www.wendangku.net/doc/7b13677207.html,ing Fact3.7,we assume that
are spanning.Let be the graph which is induced by the intersection of these two trees.Now let be the component of containing the origin.Thus every edge of entering is either in or
.
We now construct a dispute wheel.Since is nonempty(otherwise)we may choose an edge ,where and.On the other hand,has a path to the origin in.This path must be of the form where(i)
and is the unique path in from to the origin, (ii)is a path from to in but entirely contained in the node set and(iii)has at least one edge(for otherwise one of would not be stable).We repeat this process at,except we now examine a path from to the origin in the tree.Continuing to alternate in this fashion we must eventually repeat some node,which without loss of generality is.
To see that this is a dispute wheel,we need only show that for each,
Without loss of generality,assume that is in. If the inequality did not hold,then we would have
which would mean that is not stable.
Note that NAUGHTY GADGET illustrates the fact that the converse of this result does not hold.NAUGHTY GADGET has a unique solution but is not safe,and so has a cycle in its dispute digraph.
3.4No Dispute Wheel Implies a Solution
Theorem3.9Let be an SPVP speci?cation.If has no dispute wheel,then is solvable.
Proof:Using Fact3.7,we can assume that any solution for will be a spanning tree.Suppose that is a tree(not necessarily spanning)in,rooted at,such that each node of is stable with respect to.If and ,then is said to be consistent with if it can be written as,where is a path in ,,is the unique path from to the origin in,and.Such a is called a direct path to if is empty and.Let be the set of nodes that have a direct path to.Note that if is not empty,then is not empty(is connected).Let be the set of nodes whose highest ranked path consistent with is a direct path.If is not empty,let be the tree formed by adding the nodes of to together with their highest ranked direct paths.
Let be the trivial tree rooted at the origin.If is such that is not empty,then de?ne
if is not empty
error otherwise
Note that if all nodes of are stable with respect to,then all nodes of are stable with respect to.Thus,if there exists an with,then is a solution for ,since it is stable.
On the other hand,suppose there exists an such that error.Let be any node in and let be a direct path.Note that there must be a path, permitted at and consistent with,which has higher rank than.Since is consistent with it has the form
where is a path from to in ,,is the unique path from to in,and.Note that,and since is empty we can repeat this process with.If we continue in this manner it is clear that we will eventually form a dispute wheel.
3.5Divergence Implies a Dispute Wheel
Suppose that is a non-trivial cycle in the evaluation digraph.A node is changing in a cycle if there are at least two distinct states of in which has different paths. Since is non-trivial,there is at least one node changing in.Let be the set of paths that adopts in.Let be the set of nodes that store a?xed path throughout.Note that,so this set is never empty.
Lemma3.10Suppose is adopted by in, and let be the?rst?xed node of.Then each node ,stores the path in some state of. In particular,stores throughout.Proof:Let.The result holds by assumption for,so suppose that for some ,and for each,adopts the path in some state of.If,the result is proved.Otherwise
is changing in and adopts the path;thus at this point in the cycle,must have stored.The result follows by induction.
Theorem3.11If there is a non-trivial cycle in the evalua-tion digraph,then contains a dispute wheel.
Proof:Let be a non-trivial cycle in.Let be the subset of nodes changing in such that there is a path where.That is, adopts a path in that leads directly to a?xed node.By Lemma3.10,cannot be empty.
We now construct a dispute wheel.Let be a node in .Let be’s direct path to,.It is easy to check that is unique,and that of all paths in
the path is of lowest rank.Let
be the adopted path of highest rank at. Lemma3.10tells us that we can write this path as ,where is a path from to of changing nodes,
,and for some.We can now perform the same construction for.Repeating this process in the obvious way results in a dispute wheel.
Corollary3.12If has no dispute wheel,then the evalu-ation graph has no non-trivial cycles,and so is safe.
The converse of this result does not hold.For example, BAD BACKUP presented in Figure6is the result of a slight modi?cation to BAD GADGET(the path is added and made the highest ranked path at node).This speci?cation has a dispute wheel but the evaluation graph has no cycles. In other words,the dispute wheel of BAD BACKUP is not dynamically realizable in our simple model of evaluation. Note that if the edge is deleted(modeling link fail-ure),then this system becomes BAD GADGET.
2 0
2 1 0
1 3 0
1 0
3 0
3 4 2 0 4 3 0
4 2 0
4 0
Figure6.The speci?cation BAD BACKUP.
4SPVP and Shortest Paths
Varadhan et al.[11]?rst observed that BGP policies could interact in a way that results in protocol divergence. Their examples always include autonomous systems that choose longer paths(in terms of“hop count”)over shorter ones.They stated“We believe that only shortest path route selection is provably safe.”The results of the previous sec-tions will be used to explore this statement.We interpret it to mean that any class of policies not based on shortest path route selection will not be provably safe.Notice that implicitly,the conjecture is suggesting that systems whose policies are based on shortest path route selection will,in fact,be safe.
We begin by formalizing a fairly liberal notion of“short-est path route selection”that seems appropriate for proto-cols such as BGP.We then show that any SPVP speci?ca-tion that is consistent with shortest path route selection will indeed be safe.However,we show that the converse is not true.Hence,BGP-like systems can actually violate“dis-tance metrics”and remain safe.
As is standard for undirected graphs,we work with an associated orientation of it;we think of an undirected edge as being replaced by two arcs,and
.We are also given costs and asso-ciated with traversing the edge in the two directions.Thus induces a cost function on any directed path in the re-sulting oriented graph:.The cost
function is positive if for each arc,.
There are several possible ways to formalize the notion of“shortest path route selection”for a cost function.Since a node in an SPVP speci?cation is not required to treat all possible paths to the origin as permitted paths,we cannot insist that take the shortest path.However,it seems rea-sonable to insist that if has a choice between two permit-ted paths and these paths have different costs,then cannot prefer the higher cost path over the lower cost path.For-mally,we say that the is consistent with the cost function if for each and,(1) if,then,and(2)if
,then.
If is consistent with a cost function,then there are only two sources for policy disputes.First,not all paths have to be permitted at any given node.Second,ranking functions force ties to be broken,and this may be done dif-ferently at different nodes.Both reasons are captured in the following lemma.
Lemma4.1If speci?cation is consistent with cost func-tion,and is a dispute arc,where
and.Then either(a)or(b)
.
If a cost function has negative directed cycles,then
2 0
2 1 0
1 3 0
1 0
4 3 0
4 2 0
3 0
3 4 2 0
Figure7.NAUGHTY GADGET with negative link
costs
can be consistent with and yet not safe.For example,con-sider the costs attached to the edges of NAUGHTY GADGET in Figure7,where the cost of traversing an edge is the same in each direction.NAUGHTY GADGET is consistent with this cost function,but we know from Section2that this sys-tem is not safe.Note that this graph contains a cycle of cost .Also,notice that any will be consistent with the cost function that has cost for every arc and so,in par-ticular,NAUGHTY GADGET will be consistent with such a cost function.Thus we restrict ourselves to SPVP speci?ca-tions consistent with cost functions that do not realize any directed cycles of cost at most.
De?ne a cost function to be coherent if it does not result in any non-positive directed cycles.Note that any positive cost function is coherent.
Theorem4.2If is consistent with a coherent cost func-tion,then has no dispute wheel.
Proof:Suppose that is a coherent cost function,is consistent with,and contains a dispute wheel of size. For any we have, and so.Summing these inequalities we obtain
After cancellation this implies.Thus the rim of the dispute wheel is a cycle of cost at most zero, which is a contradiction.
From Corollary3.12,we can conclude that any consis-tent with a positive cost function is safe.In particular,rout-ing policies based on hop-count(even with AS-padding)are always safe.In addition,it can be shown that if all paths are permitted,then this results in a shortest-path routing tree.
We now show that the converse of Theorem4.2is not true.The speci?cation INCOHERENT of Figure8has an acyclic dispute digraph and hence is safe.However,it is not consistent with any coherent cost function.To see this,suppose that we are given arc costs,
,
,,
and .The cost for any other arc is arbi-trary.Suppose INCOHERENT is consistent with these costs,then the fact that node prefers path over path
means that .Also the fact that
node prefers path
over path means that .Adding these inequalities together
we obtain .By cancellation,we arrive at ,so there is a nonpositive cycle .That is,INCOHERENT is not consistent with any coherent cost function.Notice that the dispute digraph of INCOHERENT ,as shown in Figure 8,is acyclic and hence INCOHERENT is safe.
In summary,the class of speci?cations with acyclic dis-pute digraphs is provably safe,yet it is strictly larger than those based on shortest paths.
1
041 2 3 01 0
4 3 1 04 3 0
4 3 0
3 0
2 3 0
1 2 3 0
1 03 1 04 3 1 0
3
3 03 1 0
22 3 0
A B
C D D
F Figure 8.INCOHERENT and its dispute digraph.
5Discussion and Future Work
Is it possible to guarantee that BGP will not diverge?Broadly speaking,this problem can be addressed either stat-ically or dynamically .A static solution would rely on pro-grams to analyze routing policies to verify that they do not contain policy con?icts that could lead to protocol di-vergence.This is essentially the approach advocated in Govindan et al.[4].However,there are two practical chal-lenges facing this approach.First,autonomous systems cur-rently do not widely share their routing policies,or only publish incomplete speci?cations.Second,even if there were complete knowledge of routing policies,Grif?n and Wilfong [6]have recently shown that checking for various global convergence conditions is either NP-complete or NP-hard.Therefore,a static approach would most likely require the development of new heuristic algorithms for detecting this class of policy con?ict.
A dynamic solution to the BGP divergence problem would be some mechanism to suppress or completely pre-vent at “run time”those BGP oscillations that arise from policy con?https://www.wendangku.net/doc/7b13677207.html,ing route ?ap dampening [12]as a dy-namic mechanism to address this problem has two distinct drawbacks.First,route ?ap dampening cannot eliminate BGP protocol oscillations,it will only make these oscilla-tions run in “slow motion”.Second,route ?ap dampening events do not provide network administrators with enough information to identify the source of the route ?apping.In other words,route ?apping caused by policy con?icts will look the same as route ?apping caused by unstable routers or defective network interfaces.So it seems that any dy-namic solution would require an extension to the BGP pro-tocol to carry additional information that would allow pol-icy disputes to be detected and identi?ed at run time .
The proof of Theorem 3.11contains an algorithm for ex-tracting dispute wheels from dynamic cycles in the eval-uation graph.This may provide a key to the design of a dynamic solution.It might be possible to extend the BGP protocol in such a way that this “extraction”can be done in a distributed manner.This could allow for the suppression of routes involved in policy-based oscillations and for the identi?cation of the autonomous systems involved.
References
[1] D.Bertsekas and R.Gallagher.Data Networks .Prentice
Hall,1992.
[2]M.Gouda and M.Schneider.Maximizable routing metrics.
Proc.Sixth International Conference on Network Protocols ,pages 71–78,1998.
[3]M.Gouda and M.Schneider.Stabilization of maximal met-ric trees.Workshop on Self-Stabilizing Systems ’99,1999.[4]https://www.wendangku.net/doc/7b13677207.html,indan,C.Alaettinoglu,G.Eddy,D.Kessens,S.Ku-mar,and W.Lee.An architecture for stable,analyzable in-ternet routing.IEEE Network ,13(1):29–35,1999.
[5]T.Grif?n,F.Shepherd,and G.Wilfong.Policy disputes in
path-vector protocols.Bell Labs Technical Memorandum,1999.
[6]T.Grif?n and G.Wilfong.An analysis of BGP convergence
properties.In SIGCOMM’99,1999.
[7] B.Halabi.Internet Routing Architectures .Cisco Press,
1997.
[8] C.Hendrick.Routing information protocol.RFC 1058,
1988.
[9]Y .Rekhter and T.Li.A border gateway protocol.RFC 1771
(BGP version 4),1995.
[10]J.W.Stewart.BGP4,Inter-Domain Routing in The Internet .
Addison-Wesley,1998.
[11]K.Varadhan,https://www.wendangku.net/doc/7b13677207.html,indan,and D.Estrin.Persistent route
oscillations in inter-domain routing.ISI technical report 96-631,USC/Information Sciences Institute,1996.
[12] C.Villamizar,R.Chandra,and https://www.wendangku.net/doc/7b13677207.html,indan.BGP route ?ap
damping.RFC 2439,1998.