Well, in some cases, we *do* use a deterministic hash function to generate tags (see tag_create_deterministic()), but in general I regard randomly selected bits to be better, when we can afford to store them, because to my mind it makes it harder for attackers to force collisions.
On Mon, Mar 28, 2011 at 02:17:38PM -0700, Ethan Jackson wrote: > I guess the only thing that makes them different from bloom filters is > how the hashing is done. We are basically using a random hash > function, only allowing the hash to be computed once, and forcing the > caller to store the result. Traditionally when people talk about > bloom filters, generally they have a hash function which given a flow, > for example, would always produce the same two bits for that flow. > Fundamentally it's the same data structure, just a slightly different > way of thinking about the problem. > > Ethan > > On Mon, Mar 28, 2011 at 2:09 PM, Ben Pfaff <b...@nicira.com> wrote: > > On Mon, Mar 28, 2011 at 01:59:34PM -0700, Ethan Jackson wrote: > >> As a side note, I finally took a moment to read how we actually > >> implemented tags. ?Very cool, reminds me of a very specialized version > >> of bloom filters. > > > > I think that they really are Bloom filters. ?They match the > > description for "Bloom filter" in Wikipedia. ?I probably should have > > just described them as Bloom filters in the header file, but I > > originally learned about them from Knuth v3, and he doesn't (IIRC) > > call them Bloom filters even though he cites Bloom as the inventor. > > _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev
