Re: Question on PE Checksum

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Dear Michael, Walter,

see my comments in-line.

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

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).


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

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
- -- 
=======================================================================
 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 protected]
 Homepage:   http://www.exp-math.uni-essen.de/~dreibh
=======================================================================
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFC4Mwd32BbsHYPLWURApnaAJ41OxpD1Yz6O12m6RNVkSYWvHsiWwCeIw9a
HvCZEHp4bsmRNvQCSBBsNGs=
=IlON
-----END PGP SIGNATURE-----