State table purpose: track connections, associate all packets with connections 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