headers
Internet-Drafts | 10 Jun 2005 21:41
Picon
Favicon

I-D ACTION:draft-ietf-rserpool-mib-01.txt

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Reliable Server Pooling Working Group of the IETF.

	Title		: Reliable Server Pooling: Management Information 
			  Base using SMIv2
	Author(s)	: J. Mulik, et al.
	Filename	: draft-ietf-rserpool-mib-01.txt
	Pages		: 32
	Date		: 2005-6-10
	
RSerPool [20] is a framework to provide reliable server pooling.
   This document defines a SMIv2 compliant Management Information Base
   (MIB) providing access to managed objects in an RSerPool
   implementation.

A URL for this Internet-Draft is:
http://www.ietf.org/internet-drafts/draft-ietf-rserpool-mib-01.txt

To remove yourself from the I-D Announcement list, send a message to 
i-d-announce-request <at> ietf.org with the word unsubscribe in the body of the message.  
You can also visit https://www1.ietf.org/mailman/listinfo/I-D-announce 
to change your subscription settings.

Internet-Drafts are also available by anonymous FTP. Login with the username
"anonymous" and a password of your e-mail address. After logging in,
type "cd internet-drafts" and then
	"get draft-ietf-rserpool-mib-01.txt".

A list of Internet-Drafts directories can be found in
http://www.ietf.org/shadow.html
(Continue reading)

Permalink | Reply | 0 comments |
headers
Internet-Drafts | 13 Jun 2005 21:42
Picon
Favicon

I-D ACTION:draft-ietf-rserpool-policies-01.txt

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Reliable Server Pooling Working Group of the IETF.

	Title		: Reliable Server Pooling Policies
	Author(s)	: M. Tuexen, T. Dreibholz
	Filename	: draft-ietf-rserpool-policies-01.txt
	Pages		: 14
	Date		: 2005-6-13
	
This document describes server pool policies for Reliable Server
   Pooling including considerations for implementing them at name
   servers and pool users.

A URL for this Internet-Draft is:
http://www.ietf.org/internet-drafts/draft-ietf-rserpool-policies-01.txt

To remove yourself from the I-D Announcement list, send a message to 
i-d-announce-request <at> ietf.org with the word unsubscribe in the body of the message.  
You can also visit https://www1.ietf.org/mailman/listinfo/I-D-announce 
to change your subscription settings.

Internet-Drafts are also available by anonymous FTP. Login with the username
"anonymous" and a password of your e-mail address. After logging in,
type "cd internet-drafts" and then
	"get draft-ietf-rserpool-policies-01.txt".

A list of Internet-Drafts directories can be found in
http://www.ietf.org/shadow.html 
or ftp://ftp.ietf.org/ietf/1shadow-sites.txt
(Continue reading)

Permalink | Reply | 0 comments |
headers
Lele Abhijit-A21465 | 17 Jun 2005 20:56

Query Regarding Auditing Mechanism used in RserPool.

Hello all, 
 
This mail is regarding the auditing procedure as defined in RSerPool Draft (draft-ietf-rserpool-enrp-11.txt).  
 
 As per the auditing specifications defined in draft section 3.11.1, the auditing mechanism is based on the computing the PE checksum as defined in section 3.11.2 of the draft. The ADLER-32 checksum algorithm is to be used for computing the checksum over the byte block formed from combining the pool handle (padded to 32-bit word boundary) and the 32-bit PE Id.  It appears the RSerPool group wanted a PE checksum that is "order independent" so incremental updates (adds/deletes) of the checksum could occur. The observation is that the ADLER-32 checksum is "order dependent", which can be illustrated by the following example.  
 
Consider a system comprising of three enrp servers E1, E, and E3. Let "DatabaseEnrp1" be the database associated with the E1 for all Pool Elements Registered with E1. Consider the following DatabaseEnrp1 stored on E1. 
 
 "DatabaseEnrp1" 
 --------------------- 
 pool0001 -> 1234, 2345, 3456, 4567 
 pool1000 -> 0020, 0021, 0022, 0023 
 pool0110 -> 0030, 0031, 0032, 0033 
 
The data processed by the Adler-32 algorithm would be of the following format "pool00011234pool00012345pool00013456pool00014567pool10000020pool10000021pool10000022pool10000023pool01100030pool01100031pool01100032pool01100033". The data in the handlespaces of E2 and E3 would be the same for the PEs E1 owns. 
 
 Now consider a different ordering of the same data in E2 and E3 handlespaces. 
 
"DatabaseEnrp2" 
--------------------- 
pool0110 -> 0030, 0031, 0032, 0033 
pool0001 -> 1234, 2345, 3456, 4567 
pool1000 -> 0020, 0021, 0022, 0023  
 
 "DatabaseEnrp3" 
  ---------------------  
 
 pool1000 -> 0020, 0021, 0022, 0023 
 pool0110 -> 0030, 0031, 0032, 0033 
 pool0001 -> 1234, 2345, 3456, 4567 
 
 The ADLER-32 checksum as per the procedure defined in Section 3.11.2 results in the following:  
 
 Label                                                   INPUT                       ADLER-32 Checksum  
 -------                                                    --------                         ---------------------------- 
checksum1(pe.checksum.pr0)           DatabaseEnrp1                4bf92729 
checksum2(pe.checksum.prenrp1)     DatabaseEnrp2                45992729 
checksum3(pe.checksum.prenrp1)     DatabaseEnrp3                3ab92729 
 
 Observe that the checksums are different, even though the "content" of the database corresponding to E1 is the same; it is just organized in a differently on E2 and E3.  
 
 Now, during the auditing phase, when E1 sends "checksum1" to E2 (in a Peer Presence message), E2 most likely will find a mismatch in the checksum, and hence send a request for the handlespace corresponding to E1.  
 
 Thus the conclusion is that a mismatch in checksum necessarily does not mean that there is a mismatch in the handlespace.   
 
  The following questions arise: 
 
 1. Based on the above mentioned observations, for the proposed auditing scheme to work, the handlespace has to be ordered in some way, and this ordering has to be consistent across all enrp servers. Do we want to do this? And if we do, how do we want to define the ordering? We assume ordering of the handlespace is not wanted by the RSerPool group.  
 
 2. If the database is indeed ordered, there will be an overhead in terms of performance of the protocol. (The checksum will need to be computed whenever a Peer Presence message is received). As of now, we do not know what impact this will have on the performance, however, database queries and re-organization of the data entries is a time consuming process. Also the question arises, should a Session Layer protocol define how a database should be organized or in what sequence should it be retrieved? Will this not be very a specific requirement on the part of RSerPool? 
 
 3. One of the solutions as suggested in the RSerPool drafts is to compute the checksum incrementally. But ADLER-32 does not appear to work incrementally for subtraction of an byte block from a previous checksum. So we still need to extract individual objects from the database, and re-compute the checksum.  
 
 4. Since the auditing mechanism in RSerPool is currently based on a checksum, what approach is the right approach for auditing? To use a different checksum that allows "order independence". An alternate approach would be periodically request for the handlespace, and there can be many more approaches, all with their respective advantages and disadvantages. At this point in time, is there a need to look at alternate approaches for auditing and/or just focus on alternate checksum mechanisms, and/or ordering the database mechanisms?   
 
 5. Also, another question that comes to mind, is auditing really required in the present form? The general thread that is followed in RSerPool protocol is its so called "loosely" coupled nature. Unless and until there is a Transport Failure, the HANDLE SPACE DOWNLOAD mechanisms along with the HANDLE SPACE UPDATE mechanism will more or less ensure that the handlespace is up to date. If it is not up to date, then it just offers services with whatever is currently stored in the handlespace. In the worst case, assuming that we do not have any auditing, a PU will not get a HANDLE RESOLUTION RESPONSE, and it will try with another Enrp server.   
 
We will appreciate anyone views on this topic.  
 
Thanks 
Abhijit Lele 
Motorola Labs

 

_______________________________________________
rserpool mailing list
rserpool <at> ietf.org
https://www1.ietf.org/mailman/listinfo/rserpool
Permalink | Reply | 0 comments |
headers
Michael Tuexen | 28 Jun 2005 14:56
Picon

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:     dreibh <at> exp-math.uni-essen.de
>  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-----
>
>
Permalink | Reply | 5 comments |
headers
Thomas Dreibholz | 28 Jun 2005 15:02
Picon
Gravatar

Adler-32 Checksum


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

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:     dreibh <at> exp-math.uni-essen.de
 Homepage:   http://www.exp-math.uni-essen.de/~dreibh
=======================================================================
Permalink | Reply | 0 comments |
headers
Goyal Anurag-A20942 | 28 Jun 2005 15:15

RE: Re: Adler-32 Checksum

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: rserpool-bounces <at> ietf.org [mailto:rserpool-bounces <at> ietf.org] On Behalf
Of Michael Tuexen
Sent: Tuesday, June 28, 2005 6:27 PM
To: Thomas Dreibholz
Cc: rrs <at> cisco.com; rserpool <at> ietf.org; 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:     dreibh <at> exp-math.uni-essen.de
>  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
rserpool <at> ietf.org
https://www1.ietf.org/mailman/listinfo/rserpool
Permalink | Reply | 0 comments |
headers
Thomas Dreibholz | 28 Jun 2005 15:25
Picon
Gravatar

Re: Re: Adler-32 Checksum


On Tuesday 28 June 2005 14:56, Michael Tuexen wrote:
> > 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?

It is necessary to have an update possibility. Otherwise, each time a small 
change is made to the handlespace, a complete re-calculation of the 
handlespace checksum is necessary. Consider a handlespace with thousands of 
PEs this would cause a significant effort. An evil PE could exploit this 
behaviour by registering and deregistering at a high frequency and cause a 
DoS.

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

If PEs are removed, the implementation must update its checksum. If the 
checksum is not updated, the implementation is broken and should be fixed. 
IMHO, it should not be complicated to ensure that after an entry has been 
added or removed the checksum is updated. By using an inefficient checksum 
algorithm, a significant performance impact is imposed on every correct 
implementation. And this would be a very bad thing.

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

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:     dreibh <at> exp-math.uni-essen.de
 Homepage:   http://www.exp-math.uni-essen.de/~dreibh
=======================================================================
Permalink | Reply | 4 comments |
headers
Michael Tuexen | 28 Jun 2005 15:53
Picon

Re: Re: Adler-32 Checksum

Hi Thomas,

see my comments in-line.

Best regards
Michael

On Jun 28, 2005, at 3:25 PM, Thomas Dreibholz wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Tuesday 28 June 2005 14:56, Michael Tuexen wrote:
>
>>> 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?
>>
>
> It is necessary to have an update possibility. Otherwise, each time  
> a small
> change is made to the handlespace, a complete re-calculation of the
> handlespace checksum is necessary. Consider a handlespace with  
> thousands of
> PEs this would cause a significant effort. An evil PE could exploit  
> this
> behaviour by registering and deregistering at a high frequency and  
> cause a
> DoS.
I'm more concerned that an evil attacker can register PE which means  
that
he can pollute the namespace. The computation resource is not so  
important
compared to that, I think.
>
>
>
>> 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).
>>
>
> If PEs are removed, the implementation must update its checksum. If  
> the
> checksum is not updated, the implementation is broken and should be  
> fixed.
> IMHO, it should not be complicated to ensure that after an entry  
> has been
> added or removed the checksum is updated. By using an inefficient  
> checksum
> algorithm, a significant performance impact is imposed on every  
> correct
> implementation. And this would be a very bad thing.
>
>
> 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.
>
>
> 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:     dreibh <at> exp-math.uni-essen.de
>  Homepage:   http://www.exp-math.uni-essen.de/~dreibh
> ====================================================================== 
> =
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.4 (GNU/Linux)
>
> iD8DBQFCwU/Y32BbsHYPLWURAvVkAKCzmbkwGqSWUOhnO1LkTYMqbPE3iQCfZ/Na
> vhWiJ2Z2x1+ntoKqqkMSJjc=
> =N0tj
> -----END PGP SIGNATURE-----
>
>
Permalink | Reply | 3 comments |
headers
Thomas Dreibholz | 28 Jun 2005 15:59
Picon
Gravatar

Re: Re: Adler-32 Checksum


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

-- 
=======================================================================
 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:     dreibh <at> exp-math.uni-essen.de
 Homepage:   http://www.exp-math.uni-essen.de/~dreibh
=======================================================================
Permalink | Reply | 2 comments |
headers
Michael Tuexen | 28 Jun 2005 19:02
Picon

Re: Re: Adler-32 Checksum

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.

Best regards
Michael

On Jun 28, 2005, at 15:59 Uhr, Thomas Dreibholz wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> 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
> - --
> =======================================================================
>  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:     dreibh <at> exp-math.uni-essen.de
>  Homepage:   http://www.exp-math.uni-essen.de/~dreibh
> =======================================================================
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.4 (GNU/Linux)
>
> iD8DBQFCwVfb32BbsHYPLWURAs2+AJ4y4dQidaFk8BluPiOCvfbSQG6WiACgpT9t
> F391kp60lLQnAatchlEmwgo=
> =3/5a
> -----END PGP SIGNATURE-----
>
Permalink | Reply | 1 comment |

Gmane