On Tue, Oct 31, 2017 at 04:39:33PM -0700, Yipeng Wang wrote: > Cuckoo distributor (CD) is a double-hash function hash table, that helps > redirect packets to their corresponding subtables to avoid the sequential > search of megaflow subtables. This is another layer of cache to cache flows > and their corresponding subtable indexes. Different from a hash table, CD > can have certain false positive rate (since the full key is not stored for > space efficiency). Our CD design was partially inspired by earlier concepts > proposed in "simTable"[1] and "Cuckoo Filter"[2], and DPDK's cuckoo hash > implementation. > > For the current implementation, the design does not allow displacing items > when a bucket is full, which is different from the behavior of a cuckoo hash > table. The advantage is that we do not need to store two signatures so that > the struct is more compact. We use 16 entries per bucket for the > convenience of vector lookup. > > Each classifier has its own cuckoo distributor. > > [1] H. Lee and B. Lee, Approaches for improving tuple space search-based > table lookup, ICTC '15 > [2] B. Fan, D. G. Andersen, M. Kaminsky, and M. D. Mitzenmacher, > Cuckoo Filter: Practically Better Than Bloom, CoNEXT '14 > > CC: Darrell Ball <dball at vmware.com> > CC: Jan Scheurich <jan.scheurich at ericsson.com> > Signed-off-by: Yipeng Wang <yipeng1.wang at intel.com> > Signed-off-by: Antonio Fischetti <antonio.fischetti at intel.com> > Co-authored-by: Antonio Fischetti <antonio.fischetti at intel.com> > --- > Evaluation: > We create set of rules with various src IP. We feed traffic containing 1M > flows with various src IP and dst IP. All the flows hit 10/20/30 > rules creating 10/20/30 subtables. > > The table below shows the preliminary continuous testing results (full line > speed test) we collected with a uni-directional phy-to-phy setup. OvS > runs with 1 PMD. We use Spirent as the hardware traffic generator. > > Scalar CD results: > 1M flows: > no.subtable: 10 20 30 > cd-ovs 3658328 3028111 2863329 > orig_ovs 2683455 1646227 1240501 > speedup 1.36x 1.84x 2.31x
Thank you for the evaluation results. I think that they should be included in the commit message. They are helpful in looking through the commits later. Did you consider adding the cuckoo distributor as part of a new source file? dpif-netdev is very big, which makes it harder to understand. _______________________________________________ dev mailing list d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev
