# [Lua Workshop 2017] RE: Efficient Layer 7 Search of IP Address Space in LuaJIT/OpenResty

7 messages
Open this post in threaded view
|

## [Lua Workshop 2017] RE: Efficient Layer 7 Search of IP Address Space in LuaJIT/OpenResty

Open this post in threaded view
|

## Re: [Lua Workshop 2017] RE: Efficient Layer 7 Search of IP Address Space in LuaJIT/OpenResty

Open this post in threaded view
|

## Re: [Lua Workshop 2017] RE: Efficient Layer 7 Search of IP Address Space in LuaJIT/OpenResty

 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. -- Martin
Open this post in threaded view
|

## Re: [Lua Workshop 2017] RE: Efficient Layer 7 Search of IP Address Space in LuaJIT/OpenResty

 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
Open this post in threaded view
|

## Re: [Lua Workshop 2017] RE: Efficient Layer 7 Search of IP Address Space in LuaJIT/OpenResty

 On Thu, Oct 19, 2017 at 10:47 AM, William Ahern <[hidden email]> wrote: > 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.htmlI ❤ Daniel Bernstein. He's my hero. Russ