[Http-crcsync] General comments on crcsync document

Toby Collett toby.collett at gmail.com
Tue Oct 13 03:56:03 EDT 2009


Hi I have just picked this up again after some months of downtime, I will be
pushing out an updated document shortly taking into account hopefully all of
the comments in this thread.

One idea just occured to me as a compromise between CRC-64-ISO and crc32c,
we could calculate twice the actual number of hashes with crc32c and then
match them in pairs, this would create the equivalent of a 64bit hash in
most cases while allowing use of the more standardised algorithms.

This of course comes at the cost of greater complexity in the
implementation.

I guess there are multiple options down this route,
-match only in 32bit hash pairs
-match any two sequential hashes
-match any two matches with no literals in between
-...

Does this make sense to anyone, or is it just crazy ideas brought on by
getting up too early in the morning?

Toby

2009/8/3 Alex Wulms <alex.wulms at scarlet.be>

> All,
>
> Cool. So let's settle for CRC-64-ISO then for the time being and still
> leave
> the 'negotation' option in the protocol for future extensions, like
> discussed
> before. I'll update the document with the various protocol refinements.
>
>
> Hi Rusty,
>
> Assuming you are still following this list: does your library currently use
> the CRC-64-ISO polynomial when the client selects 64-bit CRC or does this
> require some code change?
>
>
> Cheers,
> Alex
>
>
> Op vrijdag 31 juli 2009, schreef Patrick McManus:
> > Alex, thanks for giving this some thought and experiments.
> >
> > Some thoughts of mine in no particular order:
> >
> > * 64 is way better than 60 in terms of giving people implementation
> > options. Personally I'd still go with 32, but I promise not to launch
> > further long rants in its defense.
> >
> > * the letters olpc should probably appear in the document as part of the
> > requirements. That was really interesting information to me, and it
> > isn't obvious that low bandwidth, high latency, low power environments
> > are the target of this without that mention.
> >
> > * your timing calculations are likely way off because you don't consider
> > tcp effects in a high latency env other than adding a 25% fudge factor
> > over the bit transfer rate. In a high latency environment short
> > transfers are totally dominated by rtt, not bandwidth. Slow start kills
> > you on cell based wireless networks (i.e. olpc).. think 256kbit at 500ms
> > latency being "good". You don't get to use the full 256kb/s bandwidth
> > until the 5th round trip that scenario... so you can just count transfer
> > time as rtt's * rtt-ms.. in the case of a 19KB document that's 4 rtt's
> > (2 seconds) compared to 3 rtt's for a 19/2KB document... and due to the
> > exponential growth of slow start that 1rtt is basically what you're
> > going to save in time vs 50% in bytes at any size until you fill up the
> > congestion window - and lots of cell-based-wireless environments require
> > a lot more than 5rtt's to fill the window. This is a big part of the
> > reason I think the 50% delta is completely uninteresting (well, I also
> > don't think it really happens in the wild very often).. I'm interested
> > in dividing the world into "really really good deltas" and "just send
> > everything else identity-compressed" because I really don't think there
> > is a signficant performance distinction between members of the second
> > group.. in which case crc32 would do just fine if aborting after finding
> > a solid run of hash misses.
> >
> > but crc64 makes that more or less an implementation decision rather than
> > something necessitated by the false positive rate of the protocol. And
> > that's a good thing.
> >
> > -Patrick
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.laptop.org/pipermail/http-crcsync/attachments/20091013/ae0f52f4/attachment.htm 


More information about the Http-crcsync mailing list