[c-nsp] C65K: Any significant correlation between import filter route-map complexity and BGP Router process utilization?

Roman Sokolov rps at cheater.ru
Sat Sep 4 14:23:41 EDT 2010


Nick Hilliard wrote:
> I meant to mention prefix lists vs access-lists.
> prefix-lists are invariably implemented using a trie structure, while
> access-list are generally implemented as ordered lists.  Trie lookups are
> O(log N), while an ordered list must be examined iteratively - which is an
> O(N) operation.  So, where possible, it's a Real Good Idea to to use prefix
> lists if it's appropriate to do so.  This is particularly important if
> you're doing lots of RIB prefix filtering.

Not always necessary to look up access-list line by line. Google about 
"access-list compiled" and hashes.

  Roman Sokolov
  mailto:rps at cheater.ru

More information about the cisco-nsp mailing list