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

From: Jeroen Van Bemmel <[email-masked]>
Date: Thu, 14 Sep 2006 18:52:19 +0200

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" <[email-masked]>
Aan: "Robert Sparks" <[email-masked]>; "Jeroen Van Bemmel" <[email-masked]>
CC: "Cullen Jennings" <[email-masked]>; "SIP" <[email-masked]>
Verzonden: 14-9-06 17:59
Onderwerp: Re: [Sip] Good Hash: draft-ietf-sip-fork-loop-fix-03

----- From: "Robert Sparks" <[email-masked]>

> 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 [email-masked] for questions on current sip
Use [email-masked] for new developments on the application of sip

---

From: "Pete Cordell" <[email-masked]>
Date: Thu, 14 Sep 2006 18:29:20 +0100

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" <[email-masked]>
To: "Pete Cordell" <[email-masked]>; "Robert Sparks" 
<[email-masked]>
Cc: "Cullen Jennings" <[email-masked]>; "SIP" <[email-masked]>
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)

Regards,
Jeroen

-----Oorspronkelijk bericht -----
Van: "Pete Cordell" <[email-masked]>
Aan: "Robert Sparks" <[email-masked]>; "Jeroen Van Bemmel" 
<[email-masked]>

---

From: "Jeroen van Bemmel" <[email-masked]>
Date: Thu, 14 Sep 2006 20:06:39 +0200

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" <[email-masked]>
To: "Jeroen Van Bemmel" <[email-masked]>; "Robert Sparks" 
<[email-masked]>
Cc: "SIP" <[email-masked]>
Sent: Thursday, September 14, 2006 7:29 PM
Subject: Re: [Sip] Good Hash: draft-ietf-sip-fork-loop-fix-03

>     HASH(routing info1) + HASH( call-id2 ) == HASH(routing info2) + 
> HASH( call-id2 )
>

---

From: "Pete Cordell" <[email-masked]>
Date: Thu, 14 Sep 2006 20:22:29 +0100

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.

----- Original Message ----- 
From: "Jeroen van Bemmel" <[email-masked]>
To: "Pete Cordell" <[email-masked]>; "Robert Sparks" 
<[email-masked]>
Cc: "SIP" <[email-masked]>
Sent: Thursday, September 14, 2006 7:06 PM
Subject: Re: [Sip] Good Hash: draft-ietf-sip-fork-loop-fix-03

> What might work is HASH( routing-info ^ call-id ), where '^' is defined 
> over individual characters ie
>> 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:

---

From: Cullen Jennings <[email-masked]>
Date: Thu, 14 Sep 2006 17:28:57 -0700

I don't think we should require any specific hash but I think it  
would be nice to give implementors some advice on what might be a  
reasonable choice.