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.