[ovs-discuss] Tuple Space Search implementation in the MegaFlow Cache

thibaut stimpfling thibaut.stimpfling at polymtl.ca
Thu Jan 19 22:57:49 UTC 2017

Sorry for the delay, my e-mail was somehow stuck in the draft folder :-/  

Yes, I’ve read a couple of times the NSDI paper, but I wasn’t sure how the ranges were handled ! You answer helped me a lot :-), thank you!

Regarding the use of Nesting ID/ Nesting Levels, which step (Translation of the ranges of the rules into Nesting ID/ Nesting Levels or Identification of the IDs/Levels associated to a packet header) is unclear to you?


> On Oct 25, 2016, at 2:37 AM, Ben Pfaff <blp at ovn.org> wrote:
> 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