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/
