State table TCP (sequence number checks on each packet), ICMP error messages match referred to packet (simplifies rules without breaking PMTU discovers etc.) UDP, ICMP queries/replies, other protocols: pseudo-connections with timeouts adjustable timeouts binary search tree (AVL, now Red-Black), O(log n) even in worst-case key is two address/port pairs