> >Hi Carson, > >State entry lookups don't actually occur in constant time. > Yes they do, if you have enough memory, and a good enough hash function, > such that collisions are low. The paper you mentioned argued that for the > hash functions they tried, Khash > log(n)*Ktree, for reasonable values of > n. It never said that the hash function time wasn't invariant with n. The problem with a hashed state table is that hash tables are very easy to attack. The use of collision chains (linked lists) would let an attack totally blow out the D$ and TLB. I've make a sun U10 440mhz w/ 2MB L2 grind to a halt w/ 5 packets a second after a long series of collisions. Rehash paths aren't so bad if it is an array of state objects instead of an array of pointers since you'll get good D$ and TLB performance. But that has a much higher initial memory cost (and you may not have space in the kernel map to accomodate it). This is why PF uses a state tree. Optimal case is worse that hash tables. But worst case is O(log n) as opposed to O(n). Alright, it uses redblack trees so it is technically 2*log n worst case. .mike frantzen@(nfr.com | cvs.openbsd.org | w4g.org) _______________________________________________ firewall-wizards mailing list firewall-wizardsat_private http://honor.icsalabs.com/mailman/listinfo/firewall-wizards
This archive was generated by hypermail 2b30 : Thu Oct 17 2002 - 16:49:49 PDT