SnabbCo/snabbswitch — pull request #251 by javierguerragiraldez (2014-09-03 07:25:08+00:00)
Title: Stateful packet filter, first draft

** not in a mergable state ** this PR is just for comments **

this is the first part (the 'easy' part) of stateful packet filters:

if a rule definition includes `stateful=true`, then any packet that passes by this rule updates a connection tracking table.

if a ruleset includes any stateful rule, then a previous check is added: if the packet belongs to a tracked connection, it passes without further checking, and the connection expiry time reset.

a connection is identified by a `connKey`, which is a binary string of the form `` fortunately, both IP and port numbers are contiguous in both IPv4 and IPv6, so that part can be simply converted into a string straight from the packet.

the complex (and still missing) part is handling the connection expiration. the naive solution would be to simply store the timestamp at which each connection should expire, but that would mean either scanning the whole table on each expire collection round, or keeping the list in order, which means some shuffling on each passed packet. even using a heap instead of a queue or a ring-like array doesn't buy much improvement.

my still nebulous idea is based on the fact that nobody cares if a connection lasts a few minutes more than the precise defined lifetime. then we can predefine a fixed number of very rough 'expiry buckets', maybe 10 buckets, each 10 minutes 'wide'. when a packet passes, it's connection key is added to the last bucket (and removed from any other bucket it might be), every 10 minutes the first bucket is killed, every connection registered on it are expired and the bucket is reassigned after the last one.

the goal is to make the expiry time reset operation O(1).