Subject: [Rserpool] Question on PE Checksum

From: Johnson Walter-CWJ002 <[email-masked]>
Date: Wed, 20 Jul 2005 16:05:23 -0500

The group had reached a consensus on using a 32 bit Internet Checksum for the 32 bit PE Checksum hash on the RSerPool mailing list. I see that the latest drafts use the 16 bit Internet Checksum to generate a 16 bit PE Checksum hash. 

What was the reasoning for this change in the newly released drafts?

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

---

From: Michael Tuexen <[email-masked]>
Date: Thu, 21 Jul 2005 09:21:27 +0200

Hi Walter,

I have looked into efficient ways of implementing the Internet checksum 
and figured
out that you need 32 bit arithmetic to calculate the 16 bit checksum. 
When using
a '32 bit Internet checksum' this would require support for 64 bit 
integers.
I do think that we should not require that. Therefore I prefer the 16 
bit Internet
Checksum.

I'm sorry for not bringing this up again to the mailing list before it 
went into
the ID.

Best regards
Michael

On Jul 20, 2005, at 23:05 Uhr, Johnson Walter-CWJ002 wrote:

> The group had reached a consensus on using a 32 bit Internet Checksum 
> for the 32 bit PE Checksum hash on the RSerPool mailing list. I see 
> that the latest drafts use the 16 bit Internet Checksum to generate a 
> 16 bit PE Checksum hash.
>

---

From: Thomas Dreibholz <[email-masked]>
Date: Thu, 21 Jul 2005 11:19:30 +0200

> a '32 bit Internet checksum' this would require support for 64 bit

Yes.

> I do think that we should not require that.

But is this really relevant on today's computers and compilers? Working with 
64-bit integers ("long long" datatype) is for example part of the ANSI-C 
standard since ANSI C99 (http://www.nirvani.net/docs/ansi_c.pdf). This 
standard is six years old.

I think the effort to use the 32-bit sum is not significantly higher than to 
use the 16-bit sum; but the probability that handlespace inconsistencies are 
detected is.

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
=======================================================================

---

From: Michael Tuexen <[email-masked]>
Date: Thu, 21 Jul 2005 16:59:57 +0200

Thomas,

the question is not if it is available in a programming language, but
if it is available on all processors the protocol runs on.
And that point is what I'm not sure about. And I'm not talking
about about servers or workstations, but processors used in embedded
devices and so on.

The other point is that people do have some highly optimized code
for the 16 bit stuff, but not for the 32 bit stuff. But they can build
it if the processor supports 64 bit integer arithmetic.

Best regards
Michael

On Jul 21, 2005, at 11:19 Uhr, Thomas Dreibholz wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> -  
> -----------------------------------------------------------------------
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.4 (GNU/Linux)
>
> iD8DBQFC32im32BbsHYPLWURAjLRAJ0Rw450qEZypJ52M6vfxi+WGeU5fACfX1hY
> 98Q/vzXnwNsqwmUEym2ILpc=
> =8ijA
> -----END PGP SIGNATURE-----
>

---

From: Thomas Dreibholz <[email-masked]>
Date: Fri, 22 Jul 2005 12:36:07 +0200

Dear Michael, Walter,

see my comments in-line.

> about about servers or workstations, but processors used in embedded

What devices and CPUs do you imagine? The checksum computation is only part of 
ENRP, i.e. only registrars have to do it. I think that running a registrar 
may be a job for routers. Having a look at the hardware of a Cisco 2500 
router (http://www.cisco.com/warp/public/63/arch_2500_5750.shtml) - which is 
a quite low-end device - the CPU is a Motorola 68030 32-bit CPU with 20 or 25 
MHz. This CPU generation - although about 15 years old - will have no 
problems with the 32-bit checksum example code Walter mentioned 
(http://www.csee.usf.edu/~christen/tools/check32.c).

> it if the processor supports 64 bit integer arithmetic.

Well, the 32 bit example code Walter mentioned 
(http://www.csee.usf.edu/~christen/tools/check32.c) has to check for an 
overflow every 4 bytes + for up to 3 remaining bytes. But the important 
question is: Does this really add significant runtime to a registrar 
implementation?

1. The checksum computation code for a full PE entry is invoked only when a PE 
is registered via ASAP_REGISTRATION or added from a peer by ENRP_UPDATE. When 
the PE is deregistered or its information is updated, the checksum may be 
computed incrementally. I do not assume that there are thousands of 
registrations per second - even in very large pools. That is, full checksum 
computations occur rarely.

2. The checksum is not computed over a "large" amount of bytes. Section 3.11.2 
of ENRP-12 defines that it is computed over PH and PE ID (4 bytes). I assume 
that the length of a realistic PH is may be up to 128 bytes. That is, when a 
checksum has to be computed, it is computed over "a few bytes" only.

In summary, full checksum computation occurs rarely and is not very expensive 
on realistic CPUs. If a device running a registrar already has 
performance problems with computing the checksum, it will have orders of 
magnitude more problems maintaining SCTP associations, handling ASAP/ENRP 
communications and managing the handlespace.

The real question is: Is it useful to decrease the probability of having an 
undetected handlespace inconsistency from 1/65536 to 1/(2^32) by using the 
32-bit checksum instead of the 16-bit one? The problem of an inconsistency is 
that a registrar may wrongly assume the existence or non-existence of PEs. 
That is, PUs get non-existing PE entries (PEs already deregistered but the 
registrar still has them in its handlespace copy) or PUs will not get an 
appropriate PE entry (PEs are registered but the registrar does not know). 

The impact of such inconsistencies of course depends on the application, but 
it could possibly be severe. Therefore, it is IMHO useful to choose the better 
32-bit algorithm until someone either proves that (1) the impact of 
handlespace inconsistencies is in any case unproblematic or (2) there are 
realistic devices on which the checksum computation becomes a bottleneck.

Best regards
- --

---

From: Michael Tuexen <[email-masked]>
Date: Fri, 22 Jul 2005 16:50:21 +0200

Dear all,

so the questions comes down to: is it acceptable to require
for ENRP servers
- 64 bit integer capabilities
or
- using a not so performant routine (approx. twice as slow)

So Walter and Thomas think this is acceptable. Do others have
an opinion too?

Maybe I was too conservative.

Best regards
Michael

On Jul 22, 2005, at 12:36 Uhr, Thomas Dreibholz wrote:

> iD8DBQFC4Mwd32BbsHYPLWURApnaAJ41OxpD1Yz6O12m6RNVkSYWvHsiWwCeIw9a
> HvCZEHp4bsmRNvQCSBBsNGs=
> =IlON