[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: [Lua Workshop 2017] RE: Efficient Layer 7 Search of IP Address Space in LuaJIT/OpenResty
- From: William Ahern <william@...>
- Date: Thu, 19 Oct 2017 10:47:41 -0700
On Thu, Oct 19, 2017 at 01:33:45PM +0100, dyngeccetor8 wrote:
> On 10/18/2017 06:17 AM, Sean Conner wrote:
> > Assume the following addresses/masks:
> >
> > 0000/0000 (our default match for "no match")
> > 1000/1000 addresses 8-15
> > 0100/1100 addresses 4-7
> > 0010/1111 address 2
> >
> > So address 0, 1 and 3 (if my data is correct) should be a "no match". A
> > constructed tree will look like:
> >
> > [*] 0000/0000
> > / \
> > 0 1
> > / \
> > [ ] [*] 1000/1000
> > / \
> > 0 1
> > / \
> > [ ] [*] 0100/1100
> > \
> > 1
> > \
> > [ ]
> > /
> > 0
> > /
> > [*] 0010/1111
> >
>
> Looks like TRIE structure for me.
More specifically, a crit-bit tree.
https://cr.yp.to/critbit.html
