Re: Open Source BGP Route Optimization?
At first I wasn't sure what a "route optimizer" was supposed to do -- the term is rather generic and could have a lot of different interpretations. A multi-path traffic balancing solution in the style of Cisco's OER has to be tightly integrated with the routing infrastructure. Specifically, it needs first hand BGP peer data in order to work reliably. There will be a number of cases where an add-on solution might be able to improve on certain things, but there is one major hurdle: a BGP speaker only forwards its own best paths, so an add-on analyzer might well never learn about alternative paths. The only way for any implementation to reliably learn (all) alternative paths and otherwise maintain routing integrity is by receiving BGP data first hand, ie directly peer with transit providers and other peers. Best, -- Per
Are there any BGP extensions that would cause a BGP speaker to foward all of it's paths, not just it best? I believe quagga had made some recent attempts in this direction. IIRC the problem isn't to do with the route annoucements, it's the route withdrawals. I believe BGP only specifies the prefix being withdrawn and not the path, so if it's advertised multiple paths to a prefix it's impossible to know which has been withdrawn. Sam Per Gregers Bilse <bilse@networksignature.com> wrote:
At first I wasn't sure what a "route optimizer" was supposed to do -- the term is rather generic and could have a lot of different interpretations.
A multi-path traffic balancing solution in the style of Cisco's OER has to be tightly integrated with the routing infrastructure. Specifically, it needs first hand BGP peer data in order to work reliably. There will be a number of cases where an add-on solution might be able to improve on certain things, but there is one major hurdle: a BGP speaker only forwards its own best paths, so an add-on analyzer might well never learn about alternative paths. The only way for any implementation to reliably learn (all) alternative paths and otherwise maintain routing integrity is by receiving BGP data first hand, ie directly peer with transit providers and other peers.
Best,
-- Per
On May 28, 10:37am, "Sam Stickland" <sam_ml@spacething.org> wrote:
Are there any BGP extensions that would cause a BGP speaker to foward all of it's paths, not just it best? I believe quagga had made some recent attempts
It has been discussed and been on wish lists, but:
in this direction. IIRC the problem isn't to do with the route annoucements, it's the route withdrawals. I believe BGP only specifies the prefix being withdrawn and not the path, so if it's advertised multiple paths to a prefix it's impossible to know which has been withdrawn.
That is 100% correct, yes. Selective withdrawal is not supported. Another issue is that there isn't much point, as far as regular BGP and routing considerations go. Whichever is the best path for a border router is the best path; telling other routers about paths it will not use serves no (or at best very little) point in this context. Funny coincidence, just earlier today I was talking to somebody about BGP and its general applicability, and while there can be no question that BGP has stood the test of time and achieved all its objectives, there are things one would do differently if one were to start over. But that's always the case. Best, -- Per
On 28.05.2004 15:37 Per Gregers Bilse wrote:
On May 28, 10:37am, "Sam Stickland" <sam_ml@spacething.org> wrote:
in this direction. IIRC the problem isn't to do with the route annoucements, it's the route withdrawals. I believe BGP only specifies the prefix being withdrawn and not the path, so if it's advertised multiple paths to a prefix it's impossible to know which has been withdrawn.
That is 100% correct, yes. Selective withdrawal is not supported.
Wouldn't Equal Cost Multi-Path (ECMP) solve this? Arnold
On May 28, 6:34pm, Arnold Nipper <arnold@nipper.de> wrote:
Wouldn't Equal Cost Multi-Path (ECMP) solve this?
In some, or maybe even many, cases, yes, mostly, but what people really want is an AS-wide solution, covering any number of boxes, and preferably not depending on a pseudo-random selection between multiple paths. In particular, balancing outbound towards two or more different transits, one would want a more carefully configured and policed balancing act, not a "whatever hits some cache first and stays there for a while" choice. Best, -- Per
Per Gregers Bilse <bilse@networksignature.com> wrote:
On May 28, 10:37am, "Sam Stickland" <sam_ml@spacething.org> wrote:
Are there any BGP extensions that would cause a BGP speaker to foward all of it's paths, not just it best? I believe quagga had made some recent attempts
It has been discussed and been on wish lists, but:
in this direction. IIRC the problem isn't to do with the route annoucements, it's the route withdrawals. I believe BGP only specifies the prefix being withdrawn and not the path, so if it's advertised multiple paths to a prefix it's impossible to know which has been withdrawn.
That is 100% correct, yes. Selective withdrawal is not supported.
Another issue is that there isn't much point, as far as regular BGP and routing considerations go. Whichever is the best path for a border router is the best path; telling other routers about paths it will not use serves no (or at best very little) point in this context.
Well something came up recently on a transit router. It takes multiple Tier-1 feeds, but management wanted to sell a just MFN to a customer. It's possible to policy route all of their traffic to the MFN interface and only advertise their prefixes to MFN, but not possible to only feed them the MFN routes without starting to use VRFs etc. Of course this is a great perversion of resources ;) Sam
On May 28, 10:37am, "Sam Stickland" <sam_ml@spacething.org> wrote:
Are there any BGP extensions that would cause a BGP speaker to foward all of it's paths, not just it best? I believe quagga had made some recent attempts
It has been discussed and been on wish lists, but:
in this direction. IIRC the problem isn't to do with the route annoucements, it's the route withdrawals. I believe BGP only specifies the prefix being withdrawn and not the path, so if it's advertised multiple paths to a prefix it's impossible to know which has been withdrawn.
That is 100% correct, yes. Selective withdrawal is not supported.
Another issue is that there isn't much point, as far as regular BGP and routing considerations go. Whichever is the best path for a border router is the best path; telling other routers about
will not use serves no (or at best very little) point in
Per Gregers Bilse <bilse@networksignature.com> wrote: paths it this context.
Well something came up recently on a transit router. It takes multiple Tier-1 feeds, but management wanted to sell a just MFN to a customer. It's possible to policy route all of their traffic to the MFN interface and only advertise their prefixes to MFN, but not possible to only feed them the MFN routes without starting to use VRFs etc.
Of course this is a great perversion of resources ;)
Indeed. Makes me somehow wonder how come that customer did not think of buying transit directly from MFN? KISS, that is. Or am I missing something? mh
Sam
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Per Gregers Bilse wrote: | On May 28, 10:37am, "Sam Stickland" <sam_ml@spacething.org> wrote: | |>Are there any BGP extensions that would cause a BGP speaker to foward all of |>it's paths, not just it best? I believe quagga had made some recent attempts | | | It has been discussed and been on wish lists, but: | And as I said in my other post, there were two drafts submitted that never went anywhere. | |>in this direction. IIRC the problem isn't to do with the route annoucements, |>it's the route withdrawals. I believe BGP only specifies the prefix being |>withdrawn and not the path, so if it's advertised multiple paths to a prefix |>it's impossible to know which has been withdrawn. | | But the "optimizing" device is in need of receiving all potential paths from the border routers. Essentially, it needs a complete picture of all viable paths, not just the best that each border has. It would not be advertising multiple paths. | That is 100% correct, yes. Selective withdrawal is not supported. | But the "optimizing" device wouldn't be advertising multiple paths. It would be advertising its selected path from all viable paths based on the selection criteria/policy implemented by the user. The optimizing device can then keep track of what it has advertised and withdraw as appropriate/necessary. | Another issue is that there isn't much point, as far as regular BGP | and routing considerations go. Whichever is the best path for a border | router is the best path; telling other routers about paths it will not | use serves no (or at best very little) point in this context. | The point is not to tell other borders about paths it will not use, but for the "optimizing" device to select the desired path from all available paths and cause that path to become "best path" for all border routers. And "best" in this case is a user influenced choice based on any number of factors including path performance, cost, load, or other policies that the device can use as a selection criteria. | Funny coincidence, just earlier today I was talking to somebody about | BGP and its general applicability, and while there can be no question | that BGP has stood the test of time and achieved all its objectives, | there are things one would do differently if one were to start over. | But that's always the case. | Does a great job at what it was designed for as appropriate for the time it was conceived. As always, times change. - -- ========= bep -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.2 (MingW32) iD8DBQFAt5SKE1XcgMgrtyYRAt+MAKDNboo++qImRl1eAofO/ICi5BsKEgCfVdzW jrVxUmirv7Hc2ZhlJCuV+bw= =TUny -----END PGP SIGNATURE-----
Bruce Pinsky <bep@whack.org> wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Per Gregers Bilse wrote:
On May 28, 10:37am, "Sam Stickland" <sam_ml@spacething.org> wrote:
Are there any BGP extensions that would cause a BGP speaker to foward all of it's paths, not just it best? I believe quagga had made some recent attempts
It has been discussed and been on wish lists, but:
And as I said in my other post, there were two drafts submitted that never went anywhere.
in this direction. IIRC the problem isn't to do with the route annoucements, it's the route withdrawals. I believe BGP only specifies the prefix being withdrawn and not the path, so if it's advertised multiple paths to a prefix it's impossible to know which has been withdrawn.
But the "optimizing" device is in need of receiving all potential paths from the border routers. Essentially, it needs a complete picture of all viable paths, not just the best that each border has. It would not be advertising multiple paths.
No, that's not what I meant. I simply meant that the optimising device couldn't just be a iBGP peer - it wouldn't get enough information. It occurs to me now that walking the BGP4-MIB could be enough, but I'm wouldn't like to bet on the efficently of detecting prefix withdrawals by constantly rewalking the table! To bring this back on topic, I imagine I'd be happy with a tool that simply identified top traffic flows and automatically provided me with traceroute and ping results. Though admittedly I'm not sure how useful it would end up in real life, it sounds like it could be relatively useful tool in the hands of a someone that understands it. Thinking about the potential problems with it, I wonder if there could be any milage in the idea of preformance beacons: Points at key points in an AS (possibly registered in an RIR) that are garanteed to be useable for prefined traffic metrics. Hmm.. maybe it's late and I haven't had enough coffee - one of the route optimisation does something like this already? Sam
On Fri, 28 May 2004, Bruce Pinsky wrote:
But the "optimizing" device wouldn't be advertising multiple paths. It would be advertising its selected path from all viable paths based on the selection criteria/policy implemented by the user. The optimizing device can then keep track of what it has advertised and withdraw as appropriate/necessary.
But how do the edge routers, which are passing on all their paths, pass on withdraws? The edge routers would have resend all routes after a withdraw (which current implementations do not do, obviously). Also, the optimising device would not be BGP compliant, an update of a route is an implicit withdraw, so the optimising device could not know, if given additional UPDATE messages for additional prefixes, whether the edge device still had the previous route or not. Essentially, it's impossible to do right with BGP at the moment. If it is possible, I'd love to hear how having previously tried to implement this (and failed). regards, -- Paul Jakma paul@clubi.ie paul@jakma.org Key ID: 64A2FF6A warning: do not ever send email to spam@dishone.st Fortune: If you wish to succeed, consult three old people.
On Fri, May 28, 2004 at 02:37:23PM +0100, Per Gregers Bilse wrote:
Another issue is that there isn't much point, as far as regular BGP and routing considerations go. Whichever is the best path for a border router is the best path; telling other routers about paths it will not use serves no (or at best very little) point in this context.
what about persistent route oscillations when you use route reflectors? You wouldn't have that problem if you could announce several paths... tschuess Stefan -- Stefan Mink, Schlund+Partner AG (AS 8560) Primary key fingerprint: 389E 5DC9 751F A6EB B974 DC3F 7A1B CF62 F0D4 D2BA
On May 30, 11:21am, Stefan Mink <mink@schlund.net> wrote:
what about persistent route oscillations when you use route reflectors? You wouldn't have that problem if you could announce several paths...
Good to see that creativity is still alive and kicking. But, no, that sounds like a questionable solution to an unnecessary problem.-) Best, -- Per
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Per Gregers Bilse wrote: | At first I wasn't sure what a "route optimizer" was supposed to do -- | the term is rather generic and could have a lot of different | interpretations. | | A multi-path traffic balancing solution in the style of Cisco's OER has | to be tightly integrated with the routing infrastructure. Specifically, | it needs first hand BGP peer data in order to work reliably. There will | be a number of cases where an add-on solution might be able to improve on | certain things, but there is one major hurdle: a BGP speaker only forwards | its own best paths, so an add-on analyzer might well never learn about | alternative paths. The only way for any implementation to reliably learn | (all) alternative paths and otherwise maintain routing integrity is by | receiving BGP data first hand, ie directly peer with transit providers | and other peers. | Having helped design and implement one such a system, I can tell you that there are alternatives to peering directly with transit providers. We were able to learn alternate paths directly from the border routers of the entity whose exit paths our product was "optimizing". I am also aware of other implementations that did not rely on BGP NLRI data for determining if an exit path was valid for any given destination or prefix. In those implemenations, BGP was used merely as a mechanism to influence the outbound routing decision. Additionally, there were two RFC drafts published regarding the capability to negotiate for receiving both the active and inactive paths. draft-fletcher-bgp-inactive-path draft-walton-bgp-add-paths Given the failure of this market segment to mature, I suspect both of those are expired by now. - -- ========= bep -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.2 (MingW32) iD8DBQFAt5ITE1XcgMgrtyYRAn14AJ4ruf+9zpTxjwwlHqDnCRaClhWq5gCgmArk jXgwS/2xiwqQlfUFqfpWg/Y= =qKz1 -----END PGP SIGNATURE-----
Hi bep, good to see you're still kicking.-) On May 28, 12:25pm, Bruce Pinsky <bep@whack.org> wrote:
Having helped design and implement one such a system, I can tell you that there are alternatives to peering directly with transit providers. We were able to learn alternate paths directly from the border routers of the entity whose exit paths our product was "optimizing".
'Learn' as in how? Either you need protocol (extension) and/or hooks and out-of-band (ie, some other protocol), or you have to probe and synthesize (which I would be reluctant to trust). There's no other way.
I am also aware of other implementations that did not rely on BGP NLRI data for determining if an exit path was valid for any given destination or prefix. In those implemenations, BGP was used merely as a mechanism to influence the outbound routing decision.
But that wasn't really the point. If I telnet to all border routers and do 'sh ip b' I can get all tables too; likewise if I have a starting point and do a lot of LS traceroutes; and maybe even via SNMP (haven't checked what various MIBs support). The point was that an optimizer can't simply be an internal BGP peer, as there is no guarantee that it will in fact get any alternative paths. And the secondary point/issue is that it may be unwise to have two loosely connected protocols in charge of routing: one the regular BGP, and one some out-of-band add-on trying to manipulate the first. I think I would want these things to be tightly integrated in only one protocol. On May 28, 12:35pm, Bruce Pinsky <bep@whack.org> wrote:
| It has been discussed and been on wish lists, but:
And as I said in my other post, there were two drafts submitted that never went anywhere.
And as I said it had been discussed and been on wish lists; same thing, if a little more floral in tone.-) There's nothing scientific that prevents implementation of selective withdrawal and/or any other addition to BGP, but they're not implemented, so it's a moot point.
But the "optimizing" device is in need of receiving all potential paths from the border routers. Essentially, it needs a complete picture of all viable paths, not just the best that each border has. It would not be
Yes, that's precisely what we're saying: it can't just be an internal BGP peer in a normal setup.
The point is not to tell other borders about paths it will not use, but for the "optimizing" device to select the desired path from all available paths and cause that path to become "best path" for all border routers. And
And again, yes, the other way around, this is what we're saying: The borders need to tell the optimizer about all paths. Coffee machine dead? :-) Best, -- Per
"Per" == Per Gregers Bilse <bilse@networksignature.com> writes:
Per> But that wasn't really the point. If I telnet to all border Per> routers and do 'sh ip b' I can get all tables too; likewise if I Per> have a starting point and do a lot of LS traceroutes; and maybe Per> even via SNMP (haven't checked what various MIBs support). You can get the received routes via SNMP. I've done this manually on occasion for the purposes of doing "what-if" analysis of potential traffic plans - take a dump of all available external routes via SNMP, apply to that the proposed policy with regard to selecting the best route, then correlate the resulting route choices with known traffic statistics to determine the resulting utilisation levels of each external link. This has proven useful in a number of situations where radical changes to external routing were being made, to avoid unexpectedly overloading particular links. -- Andrew, Supernews http://www.supernews.com
Andrew - Supernews <andrew@supernews.net> wrote:
"Per" == Per Gregers Bilse <bilse@networksignature.com> writes:
Per> But that wasn't really the point. If I telnet to all border Per> routers and do 'sh ip b' I can get all tables too; likewise if I Per> have a starting point and do a lot of LS traceroutes; and maybe Per> even via SNMP (haven't checked what various MIBs support).
You can get the received routes via SNMP. I've done this manually on occasion for the purposes of doing "what-if" analysis of potential traffic plans - take a dump of all available external routes via SNMP, apply to that the proposed policy with regard to selecting the best route, then correlate the resulting route choices with known traffic statistics to determine the resulting utilisation levels of each external link. This has proven useful in a number of situations where radical changes to external routing were being made, to avoid unexpectedly overloading particular links.
I would had liked to had been able to have done such things in the past. I was thinking about having a go at writing something, but it's not like I have enough time as it is, and our network isn't really big enough to warrant it. Though I am interested in what tools already exist to support this (more out of curiousity than need). A quick google search threw up a couple of research papers and IP/MPLSView (www.wandl.com), but I presume others on this list will know of more? Sam
Sam,
You can get the received routes via SNMP. I've done this manually on
occasion for the purposes of doing "what-if" analysis of potential traffic plans - take a dump of all available external routes via SNMP, apply to that the proposed policy with regard to selecting the best route, then correlate the resulting route choices with known traffic statistics to determine the resulting utilisation levels of each external link. This has proven useful in a number of situations where radical changes to external routing were being made, to avoid unexpectedly overloading particular links.
I would had liked to had been able to have done such things in the past. I was thinking about having a go at writing something, but it's not like I have enough time as it is, and our network isn't really big enough to warrant it.
Though I am interested in what tools already exist to support this (more out of curiousity than need).
C-BGP (http://cbgp.info.ucl.ac.be) developped by Bruno Quoitin, can be used to perform this kind of analysis. It can import the BGP routes in MRTD format, but other formats can be easily converted to the MRTD format. C-BGP allows you to build a model of your network that considers both the IGP, the iBGP and eBGP sessions as well as the BGP routing policies that you use. Each C-BGP router is configured by using a Cisco-like syntax that should be familiar to most network engineers. One the model has been written, you can use it to perform different types of what-if analysis such as : - impact of IGP weight change - impact of the loss of one eBGP session - impact of the addition of a new peer/provider If there are other types of analysis that you would like to be able to perform in your network, let us know... Best regards, Olivier Bonaventure -- CSE Dept. UCL, Belgium - http://www.info.ucl.ac.be/people/OBO/
We used such system in Russia for many years, with a few exceptions: -- did not used SNMP (because it is a sux!), used 'ssh/rsh router show ...' commands instead; - not top 10 traffic flows, but top 10 traffic flows + top 10 unusual traffic flows. Worked effectively.
To bring this back on topic, I imagine I'd be happy with a tool that simply identified top traffic flows and automatically provided me with traceroute and ping results. Though admittedly I'm not sure how useful it would end up i>n real life, it sounds like it could be relatively useful tool in the hands of a someone that understands it.
participants (10)
-
Alexei Roudnev -
Andrew - Supernews -
Arnold Nipper -
Bruce Pinsky -
Michael Hallgren -
Olivier Bonaventure -
Paul Jakma -
Per Gregers Bilse -
Sam Stickland -
Stefan Mink