Open Source BGP Route Optimization?

Mailman List Mirror (Read Only)
1

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

2

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

3

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

4

Wouldn't Equal Cost Multi-Path (ECMP) solve this?

Arnold

5

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 :wink:

Sam

6

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

7

-----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.

- --

8

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Per Gregers Bilse 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.

- --

9

Hi bep,

good to see you're still kicking.-)

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.

> 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? :slight_smile:

Best,

  -- Per

10

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).

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.

11

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

12

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

13

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,

14

>> 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 :wink:

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

15

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

16

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
n real life, it sounds like it could be relatively useful tool in the

hands

17

what about persistent route oscillations when you use route reflectors?
You wouldn't have that problem if you could announce several paths...

   tschuess
             Stefan

18

Good to see that creativity is still alive and kicking. But, no, that
sounds like a questionable solution to an unnecessary problem.-)

Best,

  -- Per