[ovs-discuss] Tuple Space Search implementation in the MegaFlow Cache
Ben Pfaff
blp at ovn.org
Tue Oct 25 06:37:10 UTC 2016
On Mon, Oct 24, 2016 at 04:55:52PM -0400, thibaut stimpfling wrote:
> I am looking for implementation details of the Tuple Space Search
> algorithm in the MegaFlow Cache. More specifically, I am interested in
> how ranges are handled by the tuple space search lookup algorithm. Is
> each range converted into (a) prefix(es) ?
Yes.
In more detail, OVS itself doesn't handle ranges at all. Instead,
whatever feeds flows to it must break ranges into multiple flows that
use prefix matching.
> Are ranges converted into Nesting IDs/Nesting Levels, as described in
> the paper "Packet classification using tuple space search” ?
No.
I've read that paper a couple of times and I've always failed to
understand that part of it. I'd very much appreciate it if someone
would explain it to me.
> If so, which data structure are you using to find the nesting Id /
> nesting level associated with a packet header field ?
>
> Can you point me to any documentation that could answer this question ?
Did you read our NSDI paper? It's all about the OVS classifier.
https://www.usenix.org/node/188961
More information about the discuss
mailing list