Is the export policy selective under valley-free?
Iljitsch van Beijnum
iljitsch at muada.com
Wed Sep 3 05:32:59 CDT 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  between otherwise
> peers and there are also backup customer/provider reversals. often
> academic researchers assume the valley free condition to simplify
> 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
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/
More information about the NANOG