No one behind the wheel at WorldCom

Mailman List Mirror (Read Only)
1

msa@samurai.sfo.dead-dog.com (Majdi S. Abbas) writes:

> Actually, I think you'll find that bad data is only a small part
> of the problem; even with good data, there isn't enough support from
> various router vendors to make it worthwhile; it's effectively impossible
> to prefix filter a large peer due to router software restrictions. We
> need support for very large (256k+ to be safe) prefix filters, and the
> routing process performance to actually handle a prefix list this large,
> and not just one list, but many.
>
> IRR support for automagically building these prefix lists would
> be a real plus too. Building and then pushing out filters on another
> machine can be quite time consuming, especially for a large network.
>

From a point of view of routing software the major challenge of
handling a 256k prefix list is not actually applying it to the
received prefixes. The most popular BGP implementations all, to my
knowledge, have prefix filtering algorithms that are O(log2(N)) and
which probably scale ok... while it would be not very hard to make
this a O(4) algorithm that is probably not the issue.

Implementations do always have to do a O(log2(N)) lookup on the
routing table with a received prefix, and to afaik that is not
a performance problem for anyone.

What all implementations that i'm familiar with do have a problem with
is to actually accept the configuration of 256k lines of text to use
as a filter. Configuration parsing is typically not designed for such
numbers... it tends to work with major vendors albeith a bit slowly.

If the above disagrees with your experience please let me know.

Assuming that the bottleneck is in fact being able to parse
configuration, it begs the question what to do about it...

I'm sure all vendors will be able to, given enought incentive,
optimize their text parsing code in order to do this faster... but it
begs the question, would you actually fix anything by doing that ?

My inclination would be to think that you would just tend to move the
bottleneck to the backend systems managing the configuration of such
lists, if it isn't there already, presently.

Of course i'm completly ignorant of the backends that most of you use
to manage your systems and the above is just uneducated guessing,
although i would apreciate further education.

I would be inclined to agree with your statement that the major blame
should lie on "router vendors" if you see your router vendor as
someone that sells you the network elements + the NMS to manage it.

But in my guestimate the focal point of our search for a culprit
should be the NMS or the NMS -> router management mechanism. Idealy
the latter should be more computer friendly than text parsing.

Just an attempt to equally and democratically distribute blame around :slight_smile:

regards,
   Pedro.

2

I would be inclined to agree with your statement that the major blame
should lie on "router vendors" if you see your router vendor as
someone that sells you the network elements + the NMS to manage it.

The NMS for the vast majority of network operators is "telnet", occasionally augmented with "syslog".

But in my guestimate the focal point of our search for a culprit
should be the NMS or the NMS -> router management mechanism. Idealy
the latter should be more computer friendly than text parsing.

Amen to that.

Joe

3

I've found that a regex that is longer than about 200 characters with
the format of ^1_(2|3|4|5)$ (say 20 different as numbers in the
parenthesis) can easily crash a Bigiron running the latest code.

If you were to set up a filter that only accepted updates with
^customer_(d1|d2|d3)$ d1=downstream of customer 1, it will choke with a
fairly large peer...

Don't know how the other vendors handle it.

I reported this to foundry a few weeks ago, no fix as of yet (and I
doubt there will be).

--Phil

4

Mmmm... There's also an issue of applying AS-path filters which are (in
cisco world) regular expressions. Although it is possible to compile
several REs together into a single FSM (lex is doing exactly that), I'm
not sure IOS and/or JunOS do that.

--vadim

5

Vadim Antonov wrote:

From a point of view of routing software the major challenge of
handling a 256k prefix list is not actually applying it to the
received prefixes. The most popular BGP implementations all, to my
knowledge, have prefix filtering algorithms that are O(log2(N)) and
which probably scale ok... while it would be not very hard to make
this a O(4) algorithm that is probably not the issue.
   
Mmmm... There's also an issue of applying AS-path filters which are (in
cisco world) regular expressions. Although it is possible to compile
several REs together into a single FSM (lex is doing exactly that), I'm
not sure IOS and/or JunOS do that.

--vadim

My comment implied 'prefix-lists' which i believe was what the original poster refered to. Assuming that the primary key is a prefix, i believe all major implementations can perform this efficiently. I do agree with you that whenever the intended primary key is something else most implementations do not have an efficient way of expressing this. Route-maps and policy-statements in Juniper-parlance are sequentially evaluated, rule by rule.

I would still contend that the number 1 issue is how you do express the policy to the routing code. One could potentially attempt to recognise the primary key is a route-map/policy-statement and compile it as you suggest.
It is an idea that ends up being tossed up in the air frequently, but would that solve anything ?

Is there the ability in the backend systems to manage that effectivly and if so is text interface via the CLI the most apropriate API ?

regards,
   Pedro.

6

I would still contend that the number 1 issue is how you do express
the policy to the routing code. One could potentially attempt to
recognise the primary key is a route-map/policy-statement and compile
it as you suggest. It is an idea that ends up being tossed up in the
air frequently, but would that solve anything ?

Actually, expressing RP on per-router basis is kind of silly, and an
artifact of enterprise-box mentality. A useful design would allow
formulation of RP for the entire network with subsequent synchronization
of routers with the policy repository.

Is there the ability in the backend systems to manage that effectivly
and if so is text interface via the CLI the most apropriate API ?

Cisco-style CLI is extremely annoying and silly. There's no useful way to
perform a switch-over to a new config, and there's no good way to compare
two config and produce applicable difference.

That said, I think a well-designed CLI is a powerful thing, and can be
used to integrate routers with provider-specific NMSes.

--vadim