Subject: RE: [Rserpool] Re: Adler-32 Checksum

From: Goyal Anurag-A20942 <[email-masked]>
Date: Tue, 28 Jun 2005 18:45:07 +0530

The problem is not whether we would like the additive/subtration property to
hold vs to recompute the checksum. Even if we recompute the checksum, there
might be inconsistency if the ordering of the elements is different. It is
for this reason that Alder-32 algorithm might not be the solution for the
audit mechanism. This calls for a "descriptor" which is order-invariant and
it would be desirable to have it relatively easy to compute.

Best Wishes,
Anurag

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf
Of Michael Tuexen
Sent: Tuesday, June 28, 2005 6:27 PM
To: Thomas Dreibholz
Cc: [email-masked]; [email-masked]; Silverton Aron-C1710C; Xie
Qiaobing-QXIE1
Subject: [Rserpool] Re: Adler-32 Checksum

Dear all,

see my comments in-line.

Best regards
Michael

On Jun 28, 2005, at 2:12 PM, Thomas Dreibholz wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Monday 27 June 2005 23:03, Michael Tuexen wrote:
> Hi all!
>
>
>>     Implementation Note: when the internal handlespace changes  
>> (e.g., a
>>     new PE added or an existing PE removed), an implementation  
>> needs not
>>     to re-calculate the affected PE checksum; it should instead  
>> simply
>>     update the checksum by adding or subtracting the byte block of  
>> the
>>     corresponding PE from the previous checksum value.
>>     is at least miss-leading.
>>
>
> The problem of the Adler-32 checksum is that adding or subtracting  
> a byte
> block from the checksum value is not possible. Example: The  
> handlespace
> contains the pool "PoolTEST" with PEs 0x1234, 0x5000, 0x5001, ...,  
> 0x5100.
> The checksum of the handlespace is therefore
> f(PoolTEST1234PoolTEST5000PoolTEST5001 ... PoolTEST5100). If PE  
> 0x5000 is
> removed, at least the Adler-32 checksum of PE 0x5001 to 0x5100 must be
> recalculated, with the seed set to the checksum of PE 0x1234. The  
> Adler-32
> algorithm depends on the checksum of the previous elements as seed,  
> therefore
> it is not possible to store the checksum of each PE entry and  
> finally combine
> the checksums of PE 0x1234 and the checksum of PE 0x5000 to PE  
> 0x5100 to the
> new checksum.
>
> This is the Adler-32 algorithm:
>
> const uint32_t crcBase = 65521;
> uint32_t adler32(const uint32_t seed, const char* buffer, const  
> size_t size)
> {
>    uint32_t s1  = seed & 0xffff;
>    uint32_t s2  = (seed >> 16) & 0xffff;
>    for(size_t i = 0;i < size;i++) {
>       s1 = (s1 + buffer[i]) % crcBase;
>       s2 = (s2 + s1) % crcBase;
>    }
>    unsigned int adler32 = (s2 << 16) + s1;
>    return(adler32);
> }
>
> Depending on the seed value (i.e. the checksum of the previous  
> elements), a
> counter wrap (due to modulo operation by crcBase) appears at different
> positions in the buffer.
>
>
> For the handlespace audit, it is necessary to have a checksum  
> function f which
> provides the property that when a PE entry b is deleted from the  
> set of PE
> entries a,b,c, then the checksum f(ac) has to be computable by f 
> (abc) - f(b)
> without re-computing f(a) or f(c). "-" denotes an appropriate  
> subtraction
> operation. Furthermore, it must be possible to add an element b to  
> the set of
> PE entries a,c and compute the checksum f(abc) = f(a) + f(b) + f(c)  
> without
> having to re-computing f(a) or f(c) ("+" denotes and appropriate
> concatencation function).
That is one question: Do we want such a function? Adler32 and CRC do not
have the property. The Internet checksum has. I would prefer the  
Internet
checksum to XOR.
But the question remains: Do we need the function which with 'an update
possibility' or can we just recompute the stuff?
The problem I see is that by computing we really compare stuff. But  
just doing
incremental updates we might report something we really do not have  
anymore
in the cache (due to sume bugs, for example). So it would be more  
robust to
use something like Adler32/CRC32 as the Internet Checksum, but it  
costs more
performance. But I'm not sure how critical that is.
>
>
> A possible checksum function fulfilling the described requirements  
> is XOR. But
> this function seems to be too simple, the probability that a  
> handlespace
> inconsistency is not recognised may be too high?
>
>
> Best regards
> - --
> ====================================================================== 
> =
>  Dipl.-Inform. Thomas Dreibholz
>
>  University of Essen,                            Room ES210
>  Inst. for Experimental Mathematics              Ellernstraße 29
>  Computer Networking Technology Group            D-45326 Essen/Germany
> -  
> ---------------------------------------------------------------------- 
> -
>  E-Mail:     [email-masked]
>  Homepage:   http://www.exp-math.uni-essen.de/~dreibh
> ====================================================================== 
> =
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.4 (GNU/Linux)
>
> iD8DBQFCwT7O32BbsHYPLWURAnYyAJ0ZC9dcA30KFDUwQa+7jkBuzqhhtgCfcMB7
> +B04WYiuaA4E+lF56LgHn9g=
> =k2EC
> -----END PGP SIGNATURE-----
>
>

_______________________________________________
rserpool mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rserpool

_______________________________________________
rserpool mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rserpool

---

From: Johnson Walter-CWJ002 <[email-masked]>
Date: Thu, 30 Jun 2005 10:35:43 -0500

The XOR is the simplest since the incremental update for both the addition/subtraction would be the same code. This is not the case for the Internet Checksum incremental update correct?

Basically is there some property of the Internet Checksum that improves it ability to detect a handlespace inconsistency since that is what we are concerned about. For instance does it have better spreading of the input data to result in better chance of a unique 32 bit PE checksum result?

Walter
 
-----Original Message-----
From: Peter Lei [mailto:[email-masked]] 
Sent: Thursday, June 30, 2005 10:06 AM
To: Johnson Walter-CWJ002
Cc: Michael Tuexen; Xie Qiaobing-QXIE1; Thomas Dreibholz; [email-masked]; [email-masked]; Silverton Aron-C1710C
Subject: Re: [Rserpool] Re: Adler-32 Checksum

Johnson Walter-CWJ002 wrote:
> Is there any property that makes the Internet Checksum better at detecting a handlespace inconsistency as compared to a simple XOR of the byte block data which is composed of the pool handle zero padded to a 32 bit work boundary and the 32 bit PE Id?
> 
> Wondering since the Internet checksum will be more computationally expensive.

I'm not sure what your concern is here.  The Internet checksum
is just the ones's complement of (one's complement sum + carry).
That's two additional steps over a simple XOR sum.

The checksum has the property that it is endian independent (of
course the checksum is in the same endian as the CPU though).

--peter

> Thanks
> Walter 
> From: [email-masked] [mailto:[email-masked]] On Behalf Of Peter Lei
> Sent: Wednesday, June 29, 2005 2:29 PM
> To: Michael Tuexen
> Cc: Xie Qiaobing-QXIE1; Thomas Dreibholz; [email-masked]; [email-masked]; Silverton Aron-C1710C
> Subject: Re: [Rserpool] Re: Adler-32 Checksum
> 
> Michael Tuexen wrote:
> 
>>32 bits are longer and therefore better, but the 16 bit algorithm is
>>- already described in RFC 1071
>>- supported on NICs in hardware.
>>
>>Since it might be difficult to use a NIC to do the computation,
>>because RSerPool normally will be implemented in userland,
>>I would also vote for the 32 bit version and describe the
>>algorithm explicitly in the ENRP ID.
>>
>>If others agree I can put some text in the ID.
> 
> 
> I agree with using 32-bit checksum.
> 
> --peter
> 
> 
>>Best regards
>>Michael
>>
>>On Jun 28, 2005, at 15:59 Uhr, Thomas Dreibholz wrote:
>>
>>On Tuesday 28 June 2005 15:53, Michael Tuexen wrote:
>>
>>
>>>>>>I think, the Internet checksum algorithm (may be with keeping the
>>>>>>full 32 bits
>>>>>>instead of truncating to 16 bits) should already be sufficient for
>>>>>>the audit
>>>>>>purpose. Using this checksum algorithm, we also get order-
>>>>>>invariancy and do
>>>>>>not need to force a specific ordering of the handlespace within a
>>>>>>management
>>>>>>component. It is furthermore very simple and fast (only + and ~
>>>>>>operations
>>>>>>are needed, no *, / or %).
>>>>>
>>>>>
>>>>>So the Internet checksum is the way to go... I have no particular
>>>>>preference
>>>>>in 16 bit or 32 bit.
>>
>>
>>I would prefer 32 bits. The checksum parameter pads the sum to 32
>>bits  of
>>space anyway - so why not use the full 32 bits, making the
>>probability  that
>>two states of the handlespace map to the same checksum value much 
>>smaller?
>>
>>
>>Best regards
>>--
>>=======================================================================
>>-----------------------------------------------------------------------
>>=======================================================================
> 
> 
>