About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Fri, 17 Nov 2006

Netchannels wildcard design and implementation.


It was first described here, but I did not present memory usage for that scenario.
After some calculations I found it is about O(d*(N^d)/4 + N) where N is number of netchannels in the whole tree and d is number of dimensions we search in. With 5 dimensions (source/desctination address/port and protocol number) it becomes completely unfeasible.

And after my implementation completed (although it requires some cleaning now) I've found that memory limit on practice.

Presented design allows extremely fast searching, but it is too memory hungry, so I will modify it to not replicate sub-trees of intervals in each interval, but instead to have different kind of trees which will reduce memory consumption down to O(d*N) instead of above O(d*(N^d)) and increased search time.
So, stay tuned...

/devel/networking :: Link / Comments ()