DPDK usage discussions
 help / color / mirror / Atom feed
* Find all matches with DPDK ACL
@ 2021-11-18 16:55 Дмитрий Степанов
  2021-11-24 10:06 ` Steffen Weise
  0 siblings, 1 reply; 7+ messages in thread
From: Дмитрий Степанов @ 2021-11-18 16:55 UTC (permalink / raw)
  To: users

[-- 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 --]

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: Find all matches with DPDK ACL
  2021-11-18 16:55 Find all matches with DPDK ACL Дмитрий Степанов
@ 2021-11-24 10:06 ` Steffen Weise
  2021-11-24 15:19   ` Dmitry Kozlyuk
  0 siblings, 1 reply; 7+ messages in thread
From: Steffen Weise @ 2021-11-24 10:06 UTC (permalink / raw)
  To: Дмитрий
	Степанов
  Cc: users

[-- 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 --]

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: Find all matches with DPDK ACL
  2021-11-24 10:06 ` Steffen Weise
@ 2021-11-24 15:19   ` Dmitry Kozlyuk
  2021-11-26 13:53     ` Дмитрий Степанов
  0 siblings, 1 reply; 7+ messages in thread
From: Dmitry Kozlyuk @ 2021-11-24 15:19 UTC (permalink / raw)
  To: Steffen Weise,
	Дмитрий
	Степанов
  Cc: users

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.

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: Find all matches with DPDK ACL
  2021-11-24 15:19   ` Dmitry Kozlyuk
@ 2021-11-26 13:53     ` Дмитрий Степанов
  2021-11-26 14:12       ` Dmitry Kozlyuk
  0 siblings, 1 reply; 7+ messages in thread
From: Дмитрий Степанов @ 2021-11-26 13:53 UTC (permalink / raw)
  To: Dmitry Kozlyuk; +Cc: Steffen Weise, users

[-- 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 --]

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: Find all matches with DPDK ACL
  2021-11-26 13:53     ` Дмитрий Степанов
@ 2021-11-26 14:12       ` Dmitry Kozlyuk
  2021-11-26 14:56         ` Дмитрий Степанов
  0 siblings, 1 reply; 7+ messages in thread
From: Dmitry Kozlyuk @ 2021-11-26 14:12 UTC (permalink / raw)
  To: Дмитрий
	Степанов
  Cc: Steffen Weise, users

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?

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: Find all matches with DPDK ACL
  2021-11-26 14:12       ` Dmitry Kozlyuk
@ 2021-11-26 14:56         ` Дмитрий Степанов
  2021-11-26 23:56           ` Dmitry Kozlyuk
  0 siblings, 1 reply; 7+ messages in thread
From: Дмитрий Степанов @ 2021-11-26 14:56 UTC (permalink / raw)
  To: Dmitry Kozlyuk; +Cc: Steffen Weise, users

[-- 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 --]

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: Find all matches with DPDK ACL
  2021-11-26 14:56         ` Дмитрий Степанов
@ 2021-11-26 23:56           ` Dmitry Kozlyuk
  0 siblings, 0 replies; 7+ messages in thread
From: Dmitry Kozlyuk @ 2021-11-26 23:56 UTC (permalink / raw)
  To: Дмитрий
	Степанов
  Cc: Steffen Weise, users

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 :)

^ permalink raw reply	[flat|nested] 7+ messages in thread

end of thread, other threads:[~2021-11-28 12:57 UTC | newest]

Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-11-18 16:55 Find all matches with DPDK ACL Дмитрий Степанов
2021-11-24 10:06 ` Steffen Weise
2021-11-24 15:19   ` Dmitry Kozlyuk
2021-11-26 13:53     ` Дмитрий Степанов
2021-11-26 14:12       ` Dmitry Kozlyuk
2021-11-26 14:56         ` Дмитрий Степанов
2021-11-26 23:56           ` Dmitry Kozlyuk

DPDK usage discussions

This inbox may be cloned and mirrored by anyone:

	git clone --mirror http://inbox.dpdk.org/users/0 users/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 users users/ http://inbox.dpdk.org/users \
		users@dpdk.org
	public-inbox-index users

Example config snippet for mirrors.
Newsgroup available over NNTP:
	nntp://inbox.dpdk.org/inbox.dpdk.users


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git