Just want to ask a direct question. Will an AS export all it gets from
its customers and itself to its providers? Or even under valley-free,
the BGP export policy is also selective?
Thanks a lot,
Kai,
That's correct. A network purchasing transit will advertise its
internally-originated prefixes, as well as those it's learning from
downstream customers, to its provider.
(At least that's the theory. It's not terribly uncommon for transit
purchasers to advertise a full table, or for their providers to have
lax or non-existent filters, but that's neither here nor there. 
I'm not sure what "valley-free" means in this context. You might want
to try the Rosetta Stone patches and make sure your copy is up to
date.
Drive Slow,
Paul Wall
http://www.linkedin.com/in/paulwall
that's the idea. but your use of valley-free in this context confuses
me. care to clarify?
Valley-free is a property of AS mesh models that says that, where edges
are classified as peering (p2p) or transit (c2p) that a valid path
contains zero or one peering link and that the peering link occurs
adjacent to the top of the path. That is that valid paths look like,
[c2p c2p ... c2p p2p p2c ... p2c p2c]
(slightly abusing the notation for clarity)
The idea is that a small, customer AS should not provide transit between
its upstreams, though this does, apparently happen sometimes.
Barring misconfigurations, I believe that AS paths are normally valley-
free.
See, for example,
"Toward Valley-Free Inter-domain Routing"
http://nsrc.cse.psu.edu/tech_report/NAS-TR-0054-2006.pdf
"AS Relationships: Inference and Validation"
http://www.caida.org/publications/papers/2006/as_relationships_inference/
Cheers,
- -w
- --
William Waites <ww@styx.org>
http://www.irl.styx.org/ +49 30 8894 9942
CD70 0498 8AE4 36EA 1CD7 281C 427A 3F36 2130 E9F5
I get the valley-free but not the selective.
Iljitsch
(guessing)
Suppose,
C1 P1
\ /
A
/ \
C2 P2
Suppose A has different policies for its two customers, such as, "announce
C1 routes to P1 but not P2" and "announce C2 routes to P2 but not P1"
In this case there would be valley-free paths [C1 A P2], [C2 A P1] that are
not allowed because of A's policy. Though such a policy might be unusual,
this is a case where the set of paths generated from the topology with the
valley-free rule contains paths that would not occur in reality.
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.
Cheers,
- -w
- --
William Waites <ww@styx.org>
http://www.irl.styx.org/ +49 30 8894 9942
CD70 0498 8AE4 36EA 1CD7 281C 427A 3F36 2130 E9F5
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.
randy, on holiday and should not be reading nanog, let alone responding
On 08-09-03 at 11:40, Randy Bush on holiday and should not be
reading nanog, let alone responding wrote :
i assure you that the actual topology is not valley free. e.g. there
are many backup or political hack transit paths [0]
Sorry to further impinge on your vacation, but was there a footnote there?
between otherwise peers and there are also backup customer/provider
reversals.
Perhaps the first case could be called misclassification of the edge by
the link-labelling heuristics (and "otherwise peers" dropped)?
But where such a relationship is symmetric it runs into the second
case, and I agree that the model breaks down in the mutual transit
scenario where a link can look like either c2p or p2c depending on
the path being considered.
How useful/productive is it to say that any observed path is always,
by definition, valley-free and that the labels are not really
properties of the graph but properties of the path? I'm not sure.
Bonne vacances,
- -w
- --
William Waites <ww@styx.org>
http://www.irl.styx.org/ +49 30 8894 9942
CD70 0498 8AE4 36EA 1CD7 281C 427A 3F36 2130 E9F5
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/
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1Just want to ask a direct question. Will an AS export all it gets from
its customers and itself to its providers? Or even under valley-free,
the BGP export policy is also selective?I get the valley-free but not the selective.
(guessing)
Suppose,
C1 P1
\ /
A
/ \
C2 P2Suppose A has different policies for its two customers, such as, "announce
C1 routes to P1 but not P2" and "announce C2 routes to P2 but not P1"
This is exactly what I think? But I am not sure if it is ture. My
observation is that Routeviews cannot see a lot p2c(c2p) links which
they should see if it is strict "valley-free" --- an AS will export
all its customers to every neighbor.
OK, I'm looking at this, and having a *little* trouble buying that there's
exactly zero or one p2p links - consider the case where the last 'c2p' link
is to provider A, who peers with B but not C, and B peers with both A and C,
and the first p2c link lands at C. Don't you end up with "cp2 p2p p2p p2c" in
that case? Or is there a convention saying we compress the A-B and B-C
links into a notational A-C link? Or are we defining A-B or B-C links as
being a c2p type instead, even though they're peering and not transit?
If B passes along C's routes to A then that is not (in the model) a peering
relationship. Only your own and your customers' routes get sent to peers not
routes learned from other peers.
So in this case B-C looks like p2c and A-B could be either p2p or c2p.
Cases of partial transit, where B might repeat C's routes to peers but not
to upstrem providers are not, AFAIK treated in the model.
Cheers,
- -w
- --
William Waites <ww@styx.org>
http://www.irl.styx.org/ +49 30 8894 9942
CD70 0498 8AE4 36EA 1CD7 281C 427A 3F36 2130 E9F5
i assure you that the actual topology is not valley free. e.g. there
are many backup or political hack transit paths [0]Sorry to further impinge on your vacation, but was there a footnote there?
apologies. one publicly known (because someone used traceroute) example
is mentioned in <http://www.mcabee.org/lists/nanog/Jun-01/msg00207.html>
and likely more widely discussed around that time. usually such
arrangements, peering and transit (occasionally bi-dir selective
transit) mixed.
expect to see more next year when the court restrictions have expired
and the other randy releases his pent up anger/greed 
randy
Ahh... that's the part I was missing. Thanks... (All the scenarios I though
of were basically different partial transits...)
Well, _not_ announcing stuff as a rule doesn't break BGP convergence so don't worry about it.
(These Gao and Rexford guys are on to something... I ran their example non-valley-free topology and it was still converging after 15000 iterations.)