Find all matches with DPDK ACL

Find all matches with DPDK ACL

[Дмитрий Степанов]

[-- Attachment #1: Type: text/plain, Size: 516 bytes --]

Hi folks!

I'm using DPDK's ACL library to classify incoming packets by IPv4 5 tuple
match (src address, dst address, src port, dst port, protocol). Right now
it is possible to find only the best match based on the rule's priority.
Is there any way (maybe a custom patch for the ACL library exists?) to find
all matches in a single request? Decreased performance and even some
false-positive matches are acceptable.
It could be a big number of matches so using categories is not an option.

Thanks,
Dmitriy Stepanov

[-- Attachment #2: Type: text/html, Size: 578 bytes --]

Re: Find all matches with DPDK ACL

[Steffen Weise]

[-- Attachment #1: Type: text/plain, Size: 706 bytes --]

> Hi folks!
>
> I'm using DPDK's ACL library to classify incoming packets by IPv4 5 tuple
> match (src address, dst address, src port, dst port, protocol). Right now
> it is possible to find only the best match based on the rule's priority.
> Is there any way (maybe a custom patch for the ACL library exists?) to
> find all matches in a single request? Decreased performance and even some
> false-positive matches are acceptable.
> It could be a big number of matches so using categories is not an option.
>
> Thanks,
> Dmitriy Stepanov
>

Hi,

I have the very same question. Such a mechanism would help me in my
applications. Currently I go for lookup on multiple separate tables.

Cheers,
Steffen Weise

[-- Attachment #2: Type: text/html, Size: 983 bytes --]

Re: Find all matches with DPDK ACL

[Dmitry Kozlyuk]

2021-11-24 11:06 (UTC+0100), Steffen Weise:
> > Hi folks!
> >
> > I'm using DPDK's ACL library to classify incoming packets by IPv4 5 tuple
> > match (src address, dst address, src port, dst port, protocol). Right now
> > it is possible to find only the best match based on the rule's priority.
> > Is there any way (maybe a custom patch for the ACL library exists?) to
> > find all matches in a single request? Decreased performance and even some
> > false-positive matches are acceptable.
> > It could be a big number of matches so using categories is not an option.
> >
> > Thanks,
> > Dmitriy Stepanov
> >  
> 
> Hi,
> 
> I have the very same question. Such a mechanism would help me in my
> applications. Currently I go for lookup on multiple separate tables.
> 
> Cheers,
> Steffen Weise

Hi,

I wonder what is the original problem you're solving.

A set of IPv4 5-tuple rules can be viewed as a set of regular expressions:

ACL:	src 1.1.1.0/24 dst 2.2.2.2/32 sport any dport 0x0035 proto tcp
Regex:	^\x01\x01\x01.\x02\x02\x02\x02..\x00\x35\x06$

Here, "." stands for "any byte".
For masks/ranges not aligned on 8 bits regex ranges can be used, e.g.:

ACL:	sport 100-200
	# this one is easy, just one byte varies
Regex:  \x00[\x64-\xC8]

ACL:	sport 200-300
	# this one is hard, needs an algorithm to transform
	# 200-300 => 200-255,256-300 => 0xC8-0xFF,0x0100-0x012C
Regex:	(?:\x00[\xC8-xFF]|\x01[\x00-\x2C])

ACL:	src 192.0.2.64/26
	# this one is easy, there are also hard examples like above
Regex:  \xC0\x00\x02[\x40-\x7F]

IIUC, you need all matching expressions for every packet,
which is represented as a 4+4+2+2+1 byte "string".
This is exactly what Hyperscan library does, for example:
http://intel.github.io/hyperscan/dev-reference/runtime.html

There is now regexdev in DPDK,
take a look at it, maybe it will suit your needs and HW.

Re: Find all matches with DPDK ACL

[Дмитрий Степанов]

[-- Attachment #1: Type: text/plain, Size: 2566 bytes --]

Hi!
I have a big number of IPv4 5-tuple rules, every rule corresponds to some
action. I need to find all matched rules and perform all tied actions.
The search time greatly affects overall system performance, so I can't just
scan all rules. ACL is based on multi-bit tries and provides great
performance, so I'm looking for nearly the same performance with the
ability to find all matches within a single request.

ср, 24 нояб. 2021 г. в 18:20, Dmitry Kozlyuk <dmitry.kozliuk@gmail.com>:

> 2021-11-24 11:06 (UTC+0100), Steffen Weise:
> > > Hi folks!
> > >
> > > I'm using DPDK's ACL library to classify incoming packets by IPv4 5
> tuple
> > > match (src address, dst address, src port, dst port, protocol). Right
> now
> > > it is possible to find only the best match based on the rule's
> priority.
> > > Is there any way (maybe a custom patch for the ACL library exists?) to
> > > find all matches in a single request? Decreased performance and even
> some
> > > false-positive matches are acceptable.
> > > It could be a big number of matches so using categories is not an
> option.
> > >
> > > Thanks,
> > > Dmitriy Stepanov
> > >
> >
> > Hi,
> >
> > I have the very same question. Such a mechanism would help me in my
> > applications. Currently I go for lookup on multiple separate tables.
> >
> > Cheers,
> > Steffen Weise
>
> Hi,
>
> I wonder what is the original problem you're solving.
>
> A set of IPv4 5-tuple rules can be viewed as a set of regular expressions:
>
> ACL:    src 1.1.1.0/24 dst 2.2.2.2/32 sport any dport 0x0035 proto tcp
> Regex:  ^\x01\x01\x01.\x02\x02\x02\x02..\x00\x35\x06$
>
> Here, "." stands for "any byte".
> For masks/ranges not aligned on 8 bits regex ranges can be used, e.g.:
>
> ACL:    sport 100-200
>         # this one is easy, just one byte varies
> Regex:  \x00[\x64-\xC8]
>
> ACL:    sport 200-300
>         # this one is hard, needs an algorithm to transform
>         # 200-300 => 200-255,256-300 => 0xC8-0xFF,0x0100-0x012C
> Regex:  (?:\x00[\xC8-xFF]|\x01[\x00-\x2C])
>
> ACL:    src 192.0.2.64/26
>         # this one is easy, there are also hard examples like above
> Regex:  \xC0\x00\x02[\x40-\x7F]
>
> IIUC, you need all matching expressions for every packet,
> which is represented as a 4+4+2+2+1 byte "string".
> This is exactly what Hyperscan library does, for example:
> http://intel.github.io/hyperscan/dev-reference/runtime.html
>
> There is now regexdev in DPDK,
> take a look at it, maybe it will suit your needs and HW.
>

[-- Attachment #2: Type: text/html, Size: 3465 bytes --]

Re: Find all matches with DPDK ACL

[Dmitry Kozlyuk]

2021-11-26 16:53 (UTC+0300), Дмитрий Степанов:
> Hi!
> I have a big number of IPv4 5-tuple rules, every rule corresponds to some
> action. I need to find all matched rules and perform all tied actions.

I rather meant the subject field,
like splitting the flows or access control is a typical application of ACL.
I'm asking partially out of curiosity,
but also because there may be a better solution then DPDK ACL.

> The search time greatly affects overall system performance, so I can't just
> scan all rules. ACL is based on multi-bit tries and provides great
> performance, so I'm looking for nearly the same performance with the
> ability to find all matches within a single request.

Some regex libraries, Hyperscan or DPDK regexdev in particular,
take a database of rules, compile it to an efficient form
(Hyperscan generates vector instructions, regexdev may use HW acceleration),
and then allow to match input to the entire database in a single request,
yielding every match for every expression.

From my experience, performance is decent,
but of course it depends on the number or rules and their complexity.
How many rules do you have?
How many rules are expected to match (avg/max)?
How often do you need to insert/delete/update rules?

Re: Find all matches with DPDK ACL

[Дмитрий Степанов]

[-- Attachment #1: Type: text/plain, Size: 1653 bytes --]

I have approx 5K-10K (5 000 - 10 000) rules.
On average I have 10-20 matches (60 max).
I don't need to insert/delete/update rules frequently - you can consider
rules being permanent which are loaded once on startup.

пт, 26 нояб. 2021 г. в 17:12, Dmitry Kozlyuk <dmitry.kozliuk@gmail.com>:

> 2021-11-26 16:53 (UTC+0300), Дмитрий Степанов:
> > Hi!
> > I have a big number of IPv4 5-tuple rules, every rule corresponds to some
> > action. I need to find all matched rules and perform all tied actions.
>
> I rather meant the subject field,
> like splitting the flows or access control is a typical application of ACL.
> I'm asking partially out of curiosity,
> but also because there may be a better solution then DPDK ACL.
>
> > The search time greatly affects overall system performance, so I can't
> just
> > scan all rules. ACL is based on multi-bit tries and provides great
> > performance, so I'm looking for nearly the same performance with the
> > ability to find all matches within a single request.
>
> Some regex libraries, Hyperscan or DPDK regexdev in particular,
> take a database of rules, compile it to an efficient form
> (Hyperscan generates vector instructions, regexdev may use HW
> acceleration),
> and then allow to match input to the entire database in a single request,
> yielding every match for every expression.
>
> From my experience, performance is decent,
> but of course it depends on the number or rules and their complexity.
> How many rules do you have?
> How many rules are expected to match (avg/max)?
> How often do you need to insert/delete/update rules?
>

[-- Attachment #2: Type: text/html, Size: 2040 bytes --]

Re: Find all matches with DPDK ACL

[Dmitry Kozlyuk]

2021-11-26 17:56 (UTC+0300), Дмитрий Степанов:
> I have approx 5K-10K (5 000 - 10 000) rules.
> On average I have 10-20 matches (60 max).
> I don't need to insert/delete/update rules frequently - you can consider
> rules being permanent which are loaded once on startup.

Never mind my suggestion then.
I made a benchmark with your case parameters
and even a brute-force scan of all rules outperforms regex database.
When Hyperscan performed well in my experience,
it was with <100 rules and any single match.
Sorry for misdirection and thanks for an interesting algo problem :)