[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Sip] Good Hash: draft-ietf-sip-fork-loop-fix-03

Hi Jeroen,

For me I think something like the following would work and is efficient (if I feel inspired tomorrow I might compare its efficiency with an MD-5 implementation):-

   unsigned int hash = 0;
   int i;
   for( i=0; r[i] != '\0' && c[i] != '\0'; ++i ) {
       hash = hash * 33 + r[i] ^ c[i];
   }

   if( r[i] != '\0' ) {
       for( ; r[i] != '\0'; ++i ) {
           hash = hash * 33 + r[i];
       }
   }
   else if( c[i] != '\0' ) {
       for( ; c[i] != '\0'; ++i ) {
           hash = hash * 33 + c[i];
       }
   }

As a note, I imagine that in most cases the Call-Id string (c[]) will be shorter than the concatenated routing information (r[]), but I think it's important to work in the whole of the Call-Id into the hash even if that's not the case to allow for the two sessions' Call-Ids to share the same initial characters.

That's all low level implementation though, and I don't think it really belongs in an RFC. (Some may even think it doesn't belong on this mailing list!)

So once again, I'm not sure where that leaves the loop-fix draft!

Pete.
--
=============================================
Pete Cordell
Tech-Know-Ware Ltd
                        for XML to C++ data binding visit
                        http://www.tech-know-ware.com/lmx
                        (or http://www.xml2cpp.com)
=============================================

----- Original Message ----- From: "Jeroen van Bemmel" <jbemmel at zonnet.nl>
To: "Pete Cordell" <pete at tech-know-ware.com>; "Robert Sparks" <rjsparks at nostrum.com>
Cc: "SIP" <sip at ietf.org>
Sent: Thursday, September 14, 2006 7:06 PM
Subject: Re: [Sip] Good Hash: draft-ietf-sip-fork-loop-fix-03


Hi Pete,

No, you're right - after I sent that e-mail, I realized it has the same problem.

What might work is HASH( routing-info ^ call-id ), where '^' is defined over individual characters ie
HASH( r[0] ^ c[0] : r[1] ^ c[1] ... )

Recommendation could be to either use a non-linear hash function, or take care to mix in the call-id in a non-linear way

Regards,

Jeroen

----- Original Message ----- From: "Pete Cordell" <pete at tech-know-ware.com>
To: "Jeroen Van Bemmel" <jbemmel at zonnet.nl>; "Robert Sparks" <rjsparks at nostrum.com>
Cc: "SIP" <sip at ietf.org>
Sent: Thursday, September 14, 2006 7:29 PM
Subject: Re: [Sip] Good Hash: draft-ietf-sip-fork-loop-fix-03


Hi Jeroen,

I don't think it fixes it I'm afraid! Assuming your + operator is regular addition (modulo 32 or what ever):

If:
HASH(routing info1) + HASH( call-id1 ) == HASH(routing info2) + HASH( call-id1 )

then:
   HASH(routing info1)  == HASH(routing info2)

Therefore:
HASH(routing info1) + HASH( call-id2 ) == HASH(routing info2) + HASH( call-id2 )

Does that make sense or have I missed something?

Pete.
--
=============================================
Pete Cordell
Tech-Know-Ware Ltd
                        for XML to C++ data binding visit
                        http://www.tech-know-ware.com/lmx
                        (or http://www.xml2cpp.com)
=============================================

----- Original Message ----- From: "Jeroen Van Bemmel" <jbemmel at zonnet.nl>
To: "Pete Cordell" <pete at tech-know-ware.com>; "Robert Sparks" <rjsparks at nostrum.com>
Cc: "Cullen Jennings" <fluffy at cisco.com>; "SIP" <sip at ietf.org>
Sent: Thursday, September 14, 2006 5:52 PM
Subject: RE: [Sip] Good Hash: draft-ietf-sip-fork-loop-fix-03


Pete,

I use djb2 (a linear hash) with loop-hash = HASH(routing info) + HASH( call-id ), modulo 2^32 (or 64)

So no concatenation. I guess this avoids the issue you mentioned.

Regards,
Jeroen

-----Oorspronkelijk bericht -----
Van: "Pete Cordell" <pete at tech-know-ware.com>
Aan: "Robert Sparks" <rjsparks at nostrum.com>; "Jeroen Van Bemmel" <jbemmel at zonnet.nl>
CC: "Cullen Jennings" <fluffy at cisco.com>; "SIP" <sip at ietf.org>
Verzonden: 14-9-06 17:59
Onderwerp: Re: [Sip] Good Hash: draft-ietf-sip-fork-loop-fix-03

----- From: "Robert Sparks" <rjsparks at nostrum.com>

That may be exactly why call-id and cseq were included in the hash in
3261. Assuming that's so, then
all we need are bits that change between transactions. The first part of
the via branch parameter would
be enough.

So, I propose I add text explaining why you SHOULD (do we make this
MUST?) add some set of bits that
change between requests, and note that either the first part of the  via
branch or the combination of call-id
and cseq would be good choices.


That's quite cunning Jeroen!  I think it can only be SHOULD, because the
whole thing is SHOULD and RECOMMENDED etc.

One issue is that this works well for the cryptographic hashes, but I don't
think it will work for the linear hash I mentioned in an earlier e-mail,
i.e.:

for( i=0; i<strlen(data); ++i )
   hash = hash * MULTIPLIER + data[i];

where MULTIPLIER is 31 or 37.



_______________________________________________
Sip mailing list  https://www1.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use sip-implementors at cs.columbia.edu for questions on current sip
Use sipping at ietf.org for new developments on the application of sip




_______________________________________________
Sip mailing list  https://www1.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use sip-implementors at cs.columbia.edu for questions on current sip
Use sipping at ietf.org for new developments on the application of sip




_______________________________________________
Sip mailing list  https://www1.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use sip-implementors at cs.columbia.edu for questions on current sip
Use sipping at ietf.org for new developments on the application of sip