Is the export policy selective under valley-free?
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
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 On Tue, Sep 2, 2008 at 7:45 PM, Kai Chen <kch670@eecs.northwestern.edu> wrote:
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
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Le 08-09-03 à 02:23, Paul Wall a écrit :
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.
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.
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 -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (Darwin) iEYEARECAAYFAki+TKQACgkQQno/NiEw6fUsqQCeO4DN2glRopnWZwfgrhw1MdpZ 4kcAniuNr+O5KNl8GJKGM2C5RgHsd3ID =5AsJ -----END PGP SIGNATURE-----
On Wed, 03 Sep 2008 10:36:52 +0200, William Waites said:
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]
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?
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Le 08-09-03 à 19:26, Valdis.Kletnieks@vt.edu a écrit :
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 -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (Darwin) iEUEARECAAYFAki+zIoACgkQQno/NiEw6fUxkwCeOf84XppppZk32YxxQdyiCNgW gggAlRe2Gg93sS+/HPgscj9+qiVwQ8c= =oBAp -----END PGP SIGNATURE-----
On Wed, 03 Sep 2008 19:42:34 +0200, William Waites said:
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.
Ahh... that's the part I was missing. Thanks... (All the scenarios I though of were basically different partial transits...)
On 3 sep 2008, at 23:08, Valdis.Kletnieks@vt.edu wrote:
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.
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.)
On Tue, Sep 2, 2008 at 4:45 PM, Kai Chen <kch670@eecs.northwestern.edu> wrote:
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?
that's the idea. but your use of valley-free in this context confuses me. care to clarify?
On 3 sep 2008, at 1:45, Kai Chen wrote:
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?
I get the valley-free but not the selective. :-) Iljitsch
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Le 08-09-03 à 11:08, Iljitsch van Beijnum a écrit :
On 3 sep 2008, at 1:45, Kai Chen wrote:
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?
I get the valley-free but not the selective. :-)
(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 -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (Darwin) iEYEARECAAYFAki+WRAACgkQQno/NiEw6fW/bACeMoPGulTNd0+EiGesbTO8a3cX YfEAn2QOy9b3TVbA0t8CANp6BFPfcp8p =nYb4 -----END PGP SIGNATURE-----
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
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 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 -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (Darwin) iEYEARECAAYFAki+ZwsACgkQQno/NiEw6fWETwCeMxiDOV+Par8Twua8bPbbUJKg liYAnjhqLfbPD7hjQZSmPnnJHdR9lmUn =5KOT -----END PGP SIGNATURE-----
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
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/
On Wed, Sep 3, 2008 at 4:29 AM, William Waites <ww@styx.org> wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Le 08-09-03 à 11:08, Iljitsch van Beijnum a écrit :
On 3 sep 2008, at 1:45, Kai Chen wrote:
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?
I get the valley-free but not the selective. :-)
(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"
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.
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
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (Darwin)
iEYEARECAAYFAki+WRAACgkQQno/NiEw6fW/bACeMoPGulTNd0+EiGesbTO8a3cX YfEAn2QOy9b3TVbA0t8CANp6BFPfcp8p =nYb4 -----END PGP SIGNATURE-----
-- -Kai
participants (7)
-
Aaron Glenn -
Iljitsch van Beijnum -
Kai Chen -
Paul Wall -
Randy Bush -
Valdis.Kletnieks＠vt.edu -
William Waites