libpeak: Tree-Based Flow Tracking in C

Welcome, this is a service announcement. It has come to my attention that there already is a libpeak library, but it hasn’t been active for years, so I don’t mind. Does anyone advise against that? Anyway, since I’m working on releasing fresh DPI code, there is still some code glue missing to invoke it properly. I’ve taken the time to implement simple flow tracking based on red-black trees. I know the implementation doesn’t hold up against the speed of hash tables (and has absolutely no optimisations), but the thing is that hash tables are not really optimal in all other aspects. Let’s get into the science for the sake of it!

Hash tables cause collisions (which cause premature timeouts), lack of space (try to fill a hash table 100% without using collision mitigation), make it hard to add more memory to a table (resize is slow and needs the whole key inside the structure), and they have no order (the mathematical precision makes them inflexible). Some people also have security doubts, because hash tables can be attacked — e.g. causing denial of service attacks. Trees do not tend to care about these things, but they need to be balanced and lookup speed may be slow for larger numbers of nodes. However, network flows are a quite persistent, so new inserts do not happen very likely. Tree height can be kept low as well, but that’s another story.

With this infrastructure in place, the next step will be a small application which can load a trace file and track its flows. After that the DPI code can be pulled in. Stay tuned for that.

Leave a Reply

Your email address will not be published. Required fields are marked *