Subject: [MMUSIC] ICE-10 Issue #2: 32 bit storage for candidate pair priority

From: Jonathan Rosenberg <[email-masked]>
Date: Tue, 05 Sep 2006 16:40:09 -0400

In ICE-10, the priority for a candidate is computed as:

priority = 1000*(type preference) +
             100*(local preference) +
              10*(stream ID) +
               1*(10 - component ID)

So that priorities for a candidate go from 0 to 9999.

A candidate pair is then given a priority which is computed as:

pair priority = 10000*MIN(O-P,A-P) + MAX(O-P,A-P) + O-IP/SZ

where:

O-P is offerer’s priority, A-P is answerers priority, O-IP is 
candidate’s IP from offerer, SZ is 2^32 for v4, 2^128 for v6.

This has a maximum value of 99999999.999, which is likely to exceed the 
precision of a 32 bit floating point number. We'd like it to be possible 
to represent pair priority using a 32 bit unsigned integer.

So, here is the proposal.

One part of it is to implement the suggestion for Issue #1. If that 
happens, the stream ID gets removed from the computation for a candidate 
priority, and the formula becomes:

            100*(type preference) +
             10*(local preference) +
               1*(10 - component ID)

And then to have the pair priority be:

pair priority = 10000*MIN(O-P,A-P) + 10*MAX(O-P,A-P) + (O-P>A-P:1?0)

where the last term means "If the priority of the offerers canddiate is 
greater than the priority of the answerers candidate, then its a one, 
else its a zero". This is used to break ties. The resulting pair 
priority is always an integer, and always less than 9999991, easily 
represented by a 32 bit unsigned integer.

This works equally well with the current formula in ICE-10 and is 
simpler too, since its no longer address type specific.

Any comments or objections?

-Jonathan R.
-- 
Jonathan D. Rosenberg, Ph.D.                   600 Lanidex Plaza
Cisco Fellow                                   Parsippany, NJ 07054-2711
Cisco Systems
[email-masked]                              FAX:   (973) 952-5050
http://www.jdrosen.net                         PHONE: (973) 952-5000
http://www.cisco.com

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

---

From: Philip Matthews <[email-masked]>
Date: Thu, 7 Sep 2006 07:34:43 -0400

Jonathan:

My take on this is that trying to fit the priority into 32 bits is  
not important.
Support for Int64 and UInt64 is pretty common these days, and can be  
readily implemented in a simple class otherwise.

- Philip

---

From: Jonathan Rosenberg <[email-masked]>
Date: Thu, 07 Sep 2006 12:45:42 -0400

I suspect this depends a lot on whether the ICE endpoint is an embedded 
device or not.

-Jonathan R.

Philip Matthews wrote:

> Jonathan:
> 
> My take on this is that trying to fit the priority into 32 bits is  not 
> important.

---

From: Philip Matthews <[email-masked]>
Date: Thu, 7 Sep 2006 13:38:17 -0400

Not sure which way you meant this, but our main product is a hard- 
phone and our compilers (gcc and Microsoft) support Int64 and UInt64.
I haven't checked the details of the generated code (our main target  
is a MIPS processor), but the compiler generates whatever code is  
needed to make it work.

(I haven't actually tried this, but I strongly suspect that gcc just  
generates whatever code is required to make it work regardless of the  
target processor ... and gcc supports a huge number of targets).

- Philip

On 7-Sep-06, at 12:45 , Jonathan Rosenberg wrote:

> I suspect this depends a lot on whether the ICE endpoint is an  
> embedded device or not.
>
> -Jonathan R.
>
> Philip Matthews wrote:
>
>> Jonathan:
>> My take on this is that trying to fit the priority into 32 bits  
>> is  not important.
>> Support for Int64 and UInt64 is pretty common these days, and can  
>> be  readily implemented in a simple class otherwise.
>> - Philip
>
> --

---

From: Jonathan Rosenberg <[email-masked]>
Date: Wed, 13 Sep 2006 12:55:30 -0400

We had an ICE call yesterday, and discussed this topic.

The conclusion of our discussion was the following proposal, which makes 
a lot of sense I think.

The idea is to have the *pair* priority be 64 bits, cleanly split into 
two 32 bit parts. This allows 32 bits for the priority of a single 
candidate. Furthermore, to more fully utilize the space, use base-2 
shifting to separate the components, rather than base 10. This will view 
nicely on a hex dump, from a debug purposes, although not as nice in ascii.

Assuming for the moment that the media stream ID is removed from the 
candidate priority, this results in the following formulas:

priority = 2^24*(type preference) +
            2^8*(local preference) +
            2^0*(256 - component ID)

The type preference would have 7 (NOT 8!!) bits, for 128 values (its 
currently 10). The local preference would have 16 bits, for 65536 values 
(currently 10). The component ID would have 8 bits, for 256 values 
(currently 10). The much-larger space for local preference is to leave 
the door open for multiple stun servers. The local preference would need 
to be unique for each distinct interface/stun server combo. That leaves 
room for 256 interfaces paired with 256 stun servers, much better than 
the 3 interfaces with 3 stun servers implied by the 10 values allowed now.

The pair priority computation is then:

pair priority = 2^32*MIN(O-P,A-P) + 2*MAX(O-P,A-P) + (O-P>A-P:1?0)

The spec would point out that this requires 64 bit or two 32 bit 
unsigned ints for storage.

I believe the amount of space, with this change, is more than adequate.

Furthermore, I believe that these two formulas are at different 
strengths - they serve different purposes. The pair priority computation 
would be at MUST strength. It ensures both sides get the same ordered 
list, so that suicide checks are roughly coordinated. The candidate 
priority computation would be at SHOULD strength; it largely ensures 
that you end up selecting things which are the most mutually agreeable. 
That means that, if for some reason, you can't use the formula, thats fine.

Does this sound OK?

-Jonathan R.

Philip Matthews wrote:

> Not sure which way you meant this, but our main product is a hard- phone 
> and our compilers (gcc and Microsoft) support Int64 and UInt64.
> I haven't checked the details of the generated code (our main target  is 
> a MIPS processor), but the compiler generates whatever code is  needed 
> to make it work.
>

---

From: Philip Matthews <[email-masked]>
Date: Wed, 13 Sep 2006 15:41:07 -0400

This looks fine to me.
- Philip

On 13-Sep-06, at 12:55 , Jonathan Rosenberg wrote:

> The conclusion of our discussion was the following proposal, which  
> makes a lot of sense I think.
>
> The idea is to have the *pair* priority be 64 bits, cleanly split  
> into two 32 bit parts. This allows 32 bits for the priority of a  
> single candidate. Furthermore, to more fully utilize the space, use  
> base-2 shifting to separate the components, rather than base 10.  
> This will view nicely on a hex dump, from a debug purposes,  
> although not as nice in ascii.
>
> Assuming for the moment that the media stream ID is removed from  
> the candidate priority, this results in the following formulas:
>
> The type preference would have 7 (NOT 8!!) bits, for 128 values  
> (its currently 10). The local preference would have 16 bits, for  
> 65536 values (currently 10). The component ID would have 8 bits,  
> for 256 values (currently 10). The much-larger space for local  
> preference is to leave the door open for multiple stun servers. The  
> local preference would need to be unique for each distinct  
> interface/stun server combo. That leaves room for 256 interfaces  
> paired with 256 stun servers, much better than the 3 interfaces  
> with 3 stun servers implied by the 10 values allowed now.
>
> strengths - they serve different purposes. The pair priority  
> computation would be at MUST strength. It ensures both sides get  
> the same ordered list, so that suicide checks are roughly  
> coordinated. The candidate priority computation would be at SHOULD  
> strength; it largely ensures that you end up selecting things which  
> are the most mutually agreeable. That means that, if for some  
> reason, you can't use the formula, thats fine.
>
> Does this sound OK?
>
> -Jonathan R.
>
>
>
>
> Philip Matthews wrote:
>
>> I haven't checked the details of the generated code (our main  
>> target  is a MIPS processor), but the compiler generates whatever  
>> code is  needed to make it work.
>> (I haven't actually tried this, but I strongly suspect that gcc  
>> just  generates whatever code is required to make it work  
>> regardless of the  target processor ... and gcc supports a huge  
>> number of targets).
>> - Philip
>>>> Support for Int64 and UInt64 is pretty common these days, and  
>>>> can  be  readily implemented in a simple class otherwise.
>>>> - Philip
>>>
>>>
>>> --

---

From: Anders Kristensen <[email-masked]>
Date: Wed, 13 Sep 2006 20:08:21 -0400

> nicely on a hex dump, from a debug purposes, although not as nice in ascii.

[From the peanut gallery] If this is a consideration you could just say 
that it's hex encoded in the SDP.

Anders