16 Jul
2002
16 Jul
'02
3:48 a.m.
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