Re: No one behind the wheel at WorldCom
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 :-) regards, Pedro.
On Tuesday, July 16, 2002, at 02:44 , Pedro R Marques wrote:
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
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)
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 -----Original Message----- From: owner-nanog@merit.edu [mailto:owner-nanog@merit.edu] On Behalf Of Pedro R Marques Sent: Tuesday, July 16, 2002 2:44 AM To: msa@samurai.sfo.dead-dog.com Cc: nanog@merit.edu Subject: Re: No one behind the wheel at WorldCom msa@samurai.sfo.dead-dog.com (Majdi S. Abbas) writes: 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 :-) regards, Pedro.
On Mon, 15 Jul 2002, Pedro R Marques 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
Vadim Antonov wrote:
On Mon, 15 Jul 2002, Pedro R Marques 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.
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
participants (4)
-
Joe Abley -
Pedro R Marques -
Phil Rosenthal -
Vadim Antonov