Re: PIM Bsr hash value

From
http://tools.ietf.org/html/draft-ietf-pim-v2-sm-01

3.7 Hash Function

   The hash function is used by all routers within a domain, to map a
   group to one of the C-RPs from the RP-Set. For a particular group, G,
   the hash function uses only those C-RPs whose Group-prefix covers G.
   The algorithm takes as input the group address, and the addresses of
   the Candidate RPs, and gives as output one RP address to be used.

   The protocol requires that all routers hash to the same RP within a
   domain (except for transients). The following hash function must be
   used in each router:

      1 For RP addresses in the RP-Set, whose Group-prefix is the longest
        that covers G, select the RPs with the highest priority (i.e.
        lowest `Priority' value), and compute a value:

   Value(G,M,C(i))=
   (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31

        where C_i is the RP address and M is a hash-mask included in
        Bootstrap messages. The hash-mask allows a small number of
        consecutive groups (e.g., 4) to always hash to the same RP. For
        instance, hierarchically-encoded data can be sent on consecutive
        group addresses to get the same delay and fate-sharing
        characteristics.

        For address families other than IPv4, a 32-bit digest to be used
        as C_i must first be derived from the actual RP address. Such a
        digest method must be used consistently throughout the PIM
        domain. For IPv6 addresses, we recommend using the equivalent
        IPv4 address for an IPv4-compatible address, and the CRC-32
        checksum [7] of all other IPv6 addresses.

      2 From the RPs with the highest priority (i.e. lowest
        `Priority' value), the candidate with the highest resulting
        value is then chosen as the RP for that group, and its identity
        and hash value are stored with the entry created.

        Ties between RPs having the same hash value and priority, are
        broken in advantage of the highest address.

   The hash function algorithm is invoked by a DR, upon reception of a
   packet, or IGMP membership indication, for a group, for which the DR
   has no entry. It is invoked by any router that has (*,*,RP) state
   when a packet is received for which there is no corresponding (S,G)
   or (*,G) entry. Furthermore, the hash function is invoked by all
   routers upon receiving a (*,G) or (*,*,RP) Join/Prune message.

There is a nice thread regarding this in the following link
http://www.ietf.org/mail-archive/web/pim/current/msg01253.html

On Fri, Jul 2, 2010 at 8:56 PM, Muzammil Malick <malickmuz_at_gmail.com> wrote:
> Thanks, have the book at work, will have a read.
>
> On 2 July 2010 18:48, Anthony Sequeira <terry.francona_at_gmail.com> wrote:
>> Doyle/Carroll also do a great job explaining this in Routing TCP/IP Volume 2. If you do not have access, search Google with the following terms:
>>
>> hash-mask-length doyle
>>
>> You should receive a Google Books excerpt.
>>
>>
>> On Jul 2, 2010, at 1:04 PM, Muzammil Malick wrote:
>>
>>> Hi
>>> Err will we asked to be calculate the hash-mask-length value in:
>>> ip pim bsr-candidate [hash-mask-length] [priority]
>>> Because the following just goes way over my head:
>>>
>>> Input: Group Address (G), RP-Set (R1, R2 Rn), Mask. This information
>>> is used as the input to the hash funcation. R1, R2.. Rn are IP
>>> addresses of the RPs mapped to the Group address G. The Mask is
>>> calculated based on the mask-length distributed by the BSR.
>>>
>>> 1) Among the routers in RP-Set, select those that have numerically
>>> lowest priority values. By default all cRPs advertise priority of
>>> zero, so they all are eligible.
>>>
>>> 2) For every RP IP address, calculate the hash function value:
>>>
>>> value1 = Hash(G&Mask, R1),
>>> value2 = Hash(G&Mask, R2)
>>> valueN = Hash(G&Mask,Rn).
>>>
>>> Anthony forgive my ignorance here but I cant quite grasp what you are
>>> saying in step 1 and 2.
>>>
>>> On 2 July 2010 07:43, Gabriel Adam Kujawski <gabriel_at_brama.waw.pl> wrote:
>>>>
>>>> IMHO you should also take a look at RFC4601
>>>> (http://tinyurl.com/348slwc)
>>>>
>>>> Take a closer look at point "4.7.2 Hash Function".
>>>>
>>>> --
>>>> BRs
>>>> Gab
>>>>
>>>>
>>>> Blogs and organic groups at http://www.ccie.net
>>>>
>>>> _______________________________________________________________________
>>>> Subscription information may be found at: http://www.groupstudy.com/list/CCIELab.html
>>>
>>>
>>> Blogs and organic groups at http://www.ccie.net
>>>
>>> _______________________________________________________________________
>>> Subscription information may be found at:
>>> http://www.groupstudy.com/list/CCIELab.html
>
>
> Blogs and organic groups at http://www.ccie.net
>
> _______________________________________________________________________
> Subscription information may be found at:
> http://www.groupstudy.com/list/CCIELab.html
>
>
>
>
>
>
>
>

-- 
Victor Cappuccio
CCIE R/S# 20657
CCSI# 31452
www.anetworkerblog.com
www.linkedin.com/in/vcappuccio
Blogs and organic groups at http://www.ccie.net