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

Ben Pfaff blp at ovn.org
Thu Jan 19 23:26:58 UTC 2017


I don't understand the definitions of nesting level and ID.

On Thu, Jan 19, 2017 at 05:57:49PM -0500, thibaut stimpfling wrote:
> 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?
> 
> Thibaut 
> 
> 
> 
> 
> > 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