Is the export policy selective under valley-free?

Wed Sep 3 10:32:59 UTC 2008

On 3 sep 2008, at 11:40, Randy Bush wrote:

>> I think that yes, the valley-free property is a necessary but not
>> sufficient criteria for generating the set of in-reality-valid paths
>> on the Internet.

> i assure you that the actual topology is not valley free.  e.g. there
> are many backup or political hack transit paths [0] between otherwise
> peers and there are also backup customer/provider reversals.  often
> academic researchers assume the valley free condition to simplify  
> their
> models.  often this creates serious amusing in their results.

Note that valley-freeness is possible in the presence of backup  
configurations, which are usually called "sibling" relationships in  
this context.

The basis for the valley-freeness rules is the paper "Stable Internet  
Routing Without Global Coordination" by Lixin Gao and Jennifer  
Rexford, although the term isn't used in this paper.

They start out with Guideline A which says that customers must have a  
higher local preference than peers. If everyone uses policies like  
this then BGP will provably converge to a single stable state.

But there's more. Assumption P is about clusters of ASes that peer  
with each other (possibly indirectly). ASes that don't peer are a  
cluster of their own. Assumption P is then that the graph of these is  
a directed acyclic graph: = when you follow the provider->customer  
relationships there are no cycles in the topology and there are no  
"self cycles". I guess this means you don't sell transit to  
yourself... or your peers.

(Note that it's possible to have one type of relationship for one  
prefix and another for another prefix, so a European and American  
network can sell each other transit for their home region and peer for  
Asian traffic and still conform to the assumption.)

With Assumption P in place Guideline A can be relaxed (as Guideline B)  
such that peers and customers may now have the same local preference.

The next step is Guidelince C which allows for mutual backup  
relationships. Any path that has a hop with a backup link in it is  
considered a backup path and must have a single local preference value  
that is lower than that of any non-backup paths. "Note that, unlike  
Guideline A or B, enforcing Guideline C requires cooperation between  
ASs. An AS can not tell which routes involve backup links between  
other AS pairs. Hence, the BGP advertisements must identify these  
routes. This is typically achieved using the community attribute".

So... I guess if we all set and recognize that "IHAZBACKUP" community  
we should be safe. Oh wait: http://www.iana.org/assignments/bgp-well-known-communities/