> 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.
Oh sure, I wasn't criticizing the design decision, I hardly think storing 32bits of information per flow is an issue, and we probably get much better hashing characteristics out of this approach. > > 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
