home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_ietf_i / draft-ietf-idmr-pim-sm-specv2-00.txt < prev    next >
Text File  |  1997-09-11  |  153KB  |  4,843 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network    Working    Group                  Deborah  Estrin  (USC)
  8. Internet Draft                    Dino Farinacci (CISCO)
  9.                              Ahmed Helmy (USC)
  10.                           David    Thaler (UMICH)
  11.                         Steven Deering (XEROX)
  12.                             Mark Handley (UCL)
  13.                             Van    Jacobson (LBL)
  14.                            Chinggung Liu (USC)
  15.                            Puneet Sharma (USC)
  16.                             Liming Wei (CISCO) *
  17.  
  18. draft-ietf-idmr-pim-sm-specv2-00.txt                   September 9,1997
  19.  
  20.  
  21.  
  22.  
  23.    Protocol  Independent  Multicast-Sparse   Mode   (PIM-SM):    Protocol
  24.    Specification
  25.  
  26.  
  27.  
  28.    Status of This Memo
  29.  
  30.    This    document is an Internet     Draft.      Internet  Drafts  are     working
  31.    documents  of  the Internet Engineering Task    Force (IETF), its Areas,
  32.    and its Working Groups. (Note that other groups may    also  distribute
  33.    working documents as    Internet Drafts).
  34.  
  35.    Internet Drafts are draft  documents     valid    for  a    maximum     of  six
  36.    months.  Internet  Drafts  may  be updated, replaced, or obsoleted by
  37.    other documents at any time.     It is not appropriate to  use    Internet
  38.    Drafts  as  reference  material  or    to  cite  them    other  than as a
  39.    ``working'' draft'' or ``work in progress.''
  40.  
  41.    Please check    the I-D    abstract  listing  contained  in  each    Internet
  42.    Draft  directory  to     learn    the  current status of this or any other
  43.    Internet Draft.
  44.  
  45.  
  46. [*] The    author list has    been reordered to reflect the involvement in
  47.     detailed editorial work on this specification document.
  48.     The    first four authors are the primary editors and are listed
  49.     alphabetically.
  50.     The    rest of    the authors, also listed alphabetically, participated
  51.     in all aspects of  the architectural and detailed design but
  52.     managed to get away    without    hacking    the latex!
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Weia[Page 1]
  65.  
  66.  
  67.  
  68.  
  69.  
  70. Internet Draft          PIM-SM Specification              March 1997
  71.  
  72.  
  73. 1 Introduction
  74.  
  75.    This     document  describes  a     protocol  for    efficiently  routing  to
  76.    multicast   groups    that   may  span  wide-area  (and  inter-domain)
  77.    internets.  We  refer  to  the  approach  as      Protocol   Independent
  78.    Multicast--Sparse  Mode  (PIM-SM)  because it is not    dependent on any
  79.    particular unicast routing protocol,    and because it    is  designed  to
  80.    support  sparse  groups as defined in [1][2]. This document describes
  81.    the protocol    details. For the motivation  behind  the  design  and  a
  82.    description    of  the     architecture, see [1][2]. Section  2 summarizes
  83.    PIM-SM  operation.  It  describes  the  protocol   from   a     network
  84.    perspective,    in particular, how the participating routers interact to
  85.    create and maintain    the  multicast    distribution  tree.  Section   3
  86.    describes  PIM-SM  operations from the perspective of a single router
  87.    implementing    the protocol; this section constitutes the main    body  of
  88.    the    protocol  specification.  It  is  organized  according to PIM-SM
  89.    message type; for each message type we  describe  its  contents,  its
  90.    generation, and its processing.
  91.  
  92.    Sections  3.8 and  3.9 summarize the    timers    and  flags  referred  to
  93.    throughout this document. Section  4    provides packet    format details.
  94.  
  95.    The most significant    functional changes since the January '95 version
  96.    involve  the     Rendezvous  Point-related mechanisms, several resulting
  97.    simplifications to the protocol, and    removal    of the    PIM-DM    protocol
  98.    details to a    separate document [3] (for clarity).
  99.  
  100.  
  101. 2 PIM-SM Protocol Overview
  102.  
  103.    In  this  section  we  provide  an  overview     of  the   architectural
  104.    components of PIM-SM.
  105.  
  106.    A router receives explicit Join/Prune messages from those neighboring
  107.    routers  that have downstream group members.    The router then    forwards
  108.    data    packets    addressed to a    multicast  group,  G,  only  onto  those
  109.    interfaces  on which    explicit joins have been received. Note    that all
  110.    routers mentioned in    this document are assumed to be    PIM-SM    capable,
  111.    unless otherwise specified.
  112.  
  113.    A Designated    Router (DR) sends periodic Join/Prune messages toward  a
  114.    group-specific  Rendezvous Point (RP) for each group    for which it has
  115.    active members. Each    router along the path toward  the  RP  builds  a
  116.    wildcard  (any-source)  state  for  the  group  and    sends Join/Prune
  117.    messages on toward the RP. We use the term  route entry to  refer  to
  118.    the    state maintained in a router to    represent the distribution tree.
  119.    A route entry may include such fields  as  the  source  address,  the
  120.    group   address,  the  incoming  interface  from  which  packets  are
  121.  
  122.  
  123.  
  124. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Weia[Page 2]
  125.  
  126.  
  127.  
  128.  
  129.  
  130. Internet Draft          PIM-SM Specification              March 1997
  131.  
  132.  
  133.    accepted, the list of outgoing interfaces to    which packets are  sent,
  134.    timers, flag    bits, etc. The wildcard    route entry's incoming interface
  135.    points  toward  the    RP;  the  outgoing  interfaces    point    to   the
  136.    neighboring    downstream  routers  that  have    sent Join/Prune    messages
  137.    toward the RP. This state creates a shared, RP-centered, distribution
  138.    tree     that  reaches all group members. When a data source first sends
  139.    to a    group, its DR unicasts Register    messages  to  the  RP  with  the
  140.    source's  data packets encapsulated within. If the data rate    is high,
  141.    the RP can send source-specific Join/Prune messages back towards  the
  142.    source  and    the  source's  data  packets  will  follow the resulting
  143.    forwarding state and    travel unencapsulated to the  RP.  Whether  they
  144.    arrive  encapsulated     or  natively,    the  RP     forwards  the    source's
  145.    decapsulated    data packets  down  the     RP-centered  distribution  tree
  146.    toward  group  members.  If    the  data rate warrants    it, routers with
  147.    local  receivers  can  join     a   source-specific,    shortest   path,
  148.    distribution     tree, and prune this source's packets off of the shared
  149.    RP-centered tree. For low data rate    sources,  neither  the    RP,  nor
  150.    last-hop  routers  need join    a source-specific shortest path    tree and
  151.    data    packets    can be delivered via the shared, RP-tree.
  152.  
  153.    The following subsections describe SM operation in  more  detail,  in
  154.    particular, the control messages, and the actions they trigger.
  155.  
  156. 2.1 Local hosts    joining    a group
  157.  
  158.    In order to join a multicast    group, G, a host conveys its  membership
  159.    information through the Internet Group Management Protocol (IGMP), as
  160.    specified in    [4][5],    (see figure 1).    From this point    on we  refer  to
  161.    such    a host as a receiver, R, (or member) of    the group G.
  162.  
  163.    Note    that all figures used in this section are for  illustration  and
  164.    are    not  intended to be complete. For complete and detailed    protocol
  165.    action see Section  3.
  166.  
  167.  
  168.  
  169.  
  170.       [Figures are present only    in the postscript version]
  171.       Fig. 1  Example: how a receiver joins, and sets up shared    tree
  172.  
  173.  
  174.  
  175.    When    a DR (e.g., router A in    figure 1) gets a  membership  indication
  176.    from     IGMP for a new    group, G, the DR looks up the associated RP. The
  177.    DR creates a    wildcard multicast route entry for the    group,    referred
  178.    to  here  as     a (*,G) entry;    if there is no more specific match for a
  179.    particular source, the packet will be  forwarded  according    to  this
  180.    entry.
  181.  
  182.  
  183.  
  184. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Weia[Page 3]
  185.  
  186.  
  187.  
  188.  
  189.  
  190. Internet Draft          PIM-SM Specification              March 1997
  191.  
  192.  
  193.    The RP address is included in a special field in the    route entry  and
  194.    is  included     in  periodic upstream Join/Prune messages. The    outgoing
  195.    interface is    set to that included in    the IGMP  membership  indication
  196.    for    the  new  member. The incoming interface is set    to the interface
  197.    used    to send    unicast    packets    to the RP.
  198.  
  199.    When    there are no longer directly connected members    for  the  group,
  200.    IGMP     notifies  the    DR.  If     the  DR  has  neither local members nor
  201.    downstream receivers, the (*,G) state is deleted.
  202.  
  203. 2.2 Establishing the RP-rooted shared tree
  204.  
  205.    Triggered by    the (*,G) state, the DR     creates  a  Join/Prune     message
  206.    with     the  RP  address in its join list and the the wildcard    bit (WC-
  207.    bit)    and RP-tree bit    (RPT-bit) set to 1. The     WC-bit     indicates  that
  208.    any    source    may  match  and     be forwarded according    to this    entry if
  209.    there is no longer match; the RPT-bit indicates  that  this    join  is
  210.    being sent up the shared, RP-tree. The prune    list is    left empty. When
  211.    the RPT-bit is set to 1 it indicates    that the join is associated with
  212.    the shared RP-tree and therefore the    Join/Prune message is propagated
  213.    along the RP-tree. When the WC-bit is set to    1 it indicates that  the
  214.    address  is    an  RP    and  the  downstream receivers expect to receive
  215.    packets from    all sources via    this (shared tree) path. The  term  RPT-
  216.    bit    is used    to refer to both the RPT-bit flags associated with route
  217.    entries, and    the RPT-bit  included  in  each     encoded  address  in  a
  218.    Join/Prune message.
  219.  
  220.    Each    upstream router    creates    or updates its multicast route entry for
  221.    (*,G)  when it receives a Join/Prune    with the RPT-bit and WC-bit set.
  222.    The interface on which the Join/Prune message arrived is added to the
  223.    list     of  outgoing  interfaces  (oifs) for (*,G). Based on this entry
  224.    each    upstream  router  between  the    receiver  and  the  RP    sends  a
  225.    Join/Prune message in which the join    list includes the RP. The packet
  226.    payload   contains     Multicast-Address=G,     Join=RP,WC-bit,RPT-bit,
  227.    Prune=NULL.
  228.  
  229. 2.3 Hosts sending to a group
  230.  
  231.    When    a host    starts    sending     multicast  data  packets  to  a  group,
  232.    initially  its DR must deliver each packet to the RP    for distribution
  233.    down     the  RP-tree  (see  figure  2).  The  sender's      DR   initially
  234.    encapsulates     each  data packet in a    Register message and unicasts it
  235.    to the RP for that group. The RP decapsulates each  Register     message
  236.    and    forwards the enclosed data packet natively to downstream members
  237.    on the shared RP-tree.
  238.  
  239.  
  240.  
  241.  
  242.  
  243.  
  244. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Weia[Page 4]
  245.  
  246.  
  247.  
  248.  
  249.  
  250. Internet Draft          PIM-SM Specification              March 1997
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257.         [Figures are present only in the postscript version]
  258.         Fig. 2    Example: a host    sending    to a group
  259.  
  260.  
  261.  
  262.    If the data rate of the source warrants the use of a     source-specific
  263.    shortest  path tree (SPT), the RP may construct a new multicast route
  264.    entry that is specific to the source, hereafter referred to as  (S,G)
  265.    state,  and send periodic Join/Prune    messages toward    the source. Note
  266.    that    over time, the rules for when to switch    can be modified     without
  267.    global  coordination.  When and if the RP does switch to the    SPT, the
  268.    routers between the source and the RP build and maintain (S,G)  state
  269.    in response to these    messages and send (S,G)    messages upstream toward
  270.    the source.
  271.  
  272.    The source's    DR must    stop encapsulating  data  packets  in  Registers
  273.    when    (and so    long as) it receives Register-Stop messages from the RP.
  274.    The RP triggers Register-Stop messages in response to  Registers,  if
  275.    the    RP  has     no  downstream     receivers  for     the  group (or    for that
  276.    particular source), or if the RP has    already    joined    the  (S,G)  tree
  277.    and    is  receiving  the  data  packets  natively.  Each  source's  DR
  278.    maintains, per (S,G),  a  Register-Suppression-timer.  The  Register-
  279.    Suppression-timer  is  started  by  the  Register-Stop  message; upon
  280.    expiration, the source's DR resumes sending data packets to    the  RP,
  281.    encapsulated    in Register messages.
  282.  
  283. 2.4 Switching from shared tree (RP-tree)  to  shortest    path  tree  (SP-
  284.    tree)}
  285.  
  286.    A router with directly-connected members first joins    the  shared  RP-
  287.    tree.  The  router  can  switch to a    source's shortest path tree (SP-
  288.    tree) after receiving packets from that source over    the  shared  RP-
  289.    tree. The recommended policy    is to initiate the switch to the SP-tree
  290.    after receiving  a  significant  number  of    data  packets  during  a
  291.    specified  time  interval  from  a particular source. To realize this
  292.    policy the router can monitor data packets from sources for which  it
  293.    has     no  source-specific  multicast    route entry and    initiate such an
  294.    entry when the data rate exceeds the    configured threshold.  As  shown
  295.    in figure 3,    router `A' initiates a (S,G) state.
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Weia[Page 5]
  305.  
  306.  
  307.  
  308.  
  309.  
  310. Internet Draft          PIM-SM Specification              March 1997
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.     [Figures are present only in the postscript version]
  318.      Fig. 3  Example: Switching    from shared tree to shortest path tree
  319.  
  320.  
  321.  
  322.    When    a (S,G)    entry is activated (and     periodically  so  long     as  the
  323.    state  exists),  a  Join/Prune  message  is sent upstream towards the
  324.    source, S, with S in    the join list. The payload  contains  Multicast-
  325.    Address=G,  Join=S,    Prune=NULL. When the (S,G) entry is created, the
  326.    outgoing interface list is copied from (*,G), i.e., all local  shared
  327.    tree     branches  are replicated in the new shortest path tree. In this
  328.    way when a data packet from S arrives and matches on    this entry,  all
  329.    receivers  will  continue  to receive the source's packets along this
  330.    path. (In more complicated scenarios, other    entries     in  the  router
  331.    have     to  be    considered, as described in Section  3). Note that (S,G)
  332.    state must be maintained in each last-hop router that is  responsible
  333.    for    initiating and maintaining an SP-tree. Even when (*,G) and (S,G)
  334.    overlap, both  states  are  needed  to  trigger  the     source-specific
  335.    Join/Prune  messages.  (S,G)     state    is  kept  alive     by data packets
  336.    arriving from that source. A    timer, Entry-timer, is set for the (S,G)
  337.    entry and this timer    is restarted whenever data packets for (S,G) are
  338.    forwarded out at least one oif,  or    Registers  are    sent.  When  the
  339.    Entry-timer expires,    the state is deleted. The last-hop router is the
  340.    router  that     delivers  the    packets     to  their  ultimate  end-system
  341.    destination.     This  is  the    router    that  monitors if there    is group
  342.    membership and joins    or prunes the appropriate distribution trees  in
  343.    response.  In  general  the    last-hop router    is the Designated Router
  344.    (DR)    for the    LAN. However, under various conditions described  later,
  345.    a  parallel    router    connected  to  the same    LAN may    take over as the
  346.    last-hop router in place of the DR.
  347.  
  348.    Only    the RP and routers with    local members can initiate switching  to
  349.    the    SP-tree;  intermediate    routers     do  not. Consequently,    last-hop
  350.    routers create (S,G)    state in  response  to    data  packets  from  the
  351.    source,  S;    whereas     intermediate routers only create (S,G)    state in
  352.    response to Join/Prune messages from    downstream that    have  S     in  the
  353.    Join    list.
  354.  
  355.    The (S,G) entry is initialized with the SPT-bit  cleared,  indicating
  356.    that     the  shortest    path  tree  branch from    S has not yet been setup
  357.    completely, and the router can  still  accept  packets  from     S  that
  358.    arrive  on the (*,G)    entry's    indicated incoming interface (iif). Each
  359.    PIM multicast entry has an associated  incoming  interface  on  which
  360.    packets are expected    to arrive.
  361.  
  362.  
  363.  
  364. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Weia[Page 6]
  365.  
  366.  
  367.  
  368.  
  369.  
  370. Internet Draft          PIM-SM Specification              March 1997
  371.  
  372.  
  373.    When    a router with a    (S,G) entry and     a  cleared  SPT-bit  starts  to
  374.    receive packets from    the new    source S on the    iif for    the (S,G) entry,
  375.    and that iif    differs    from the (*,G) entry's iif, the    router sets  the
  376.    SPT-bit,  and  sends     a Join/Prune message towards the RP, indicating
  377.    that    the router no longer wants to receive packets  from  S    via  the
  378.    shared RP-tree. The Join/Prune message sent towards the RP includes S
  379.    in the prune    list, with the RPT-bit set indicating that  S's     packets
  380.    must     not  be  forwarded  down this branch of the shared tree. If the
  381.    router receiving the    Join/Prune message  has     (S,G)    state  (with  or
  382.    without  the    route entry's RPT-bit flag set), it deletes the    arriving
  383.    interface from the (S,G) oif    list.  If  the    router    has  only  (*,G)
  384.    state,  it  creates    an  entry  with     the  RPT-bit flag set to 1. For
  385.    brevity we refer to an (S,G)    entry that has the RPT-bit flag    set to 1
  386.    as  an  (S,G)RPT-bit     entry.    This notational    distinction is useful to
  387.    point out the different actions taken for (S,G) entries depending  on
  388.    the    setting    of the RPT-bit flag. Note that a router    can have no more
  389.    than    one active (S,G) entry for  any     particular  S    and  G,     at  any
  390.    particular  time;  whether  the  RPT-bit flag is set    or not.    In other
  391.    words, a router never has both an (S,G) and an (S,G)RPT-bit entry for
  392.    the    same  S     and  G    at the same time. The Join/Prune message payload
  393.    contains Multicast-Address=G, Join=NULL, Prune=S,RPT-bit.
  394.  
  395.    A new receiver may join an existing RP-tree on which     source-specific
  396.    prune  state    has been established (e.g., because downstream receivers
  397.    have    switched to SP-trees). In this case  the  prune     state    must  be
  398.    eradicated  upstream     of  the new receiver to bring all sources' data
  399.    packets down    to the    new  receiver.    Therefore,  when  a  (*,G)  Join
  400.    arrives at a    router that has    any (Si,G)RPT-bit entries (i.e., entries
  401.    that    cause the router to send source-specific prunes    toward the  RP),
  402.    these  entries  must    be updated upstream of the router so as    to bring
  403.    all sources'    packets    down to    the new    member.    To accomplish this, each
  404.    router  that    receives a (*,G) Join/Prune message updates all    existing
  405.    (S,G)RPT-bit    entries. The router may    also trigger a (*,G)  Join/Prune
  406.    message  upstream  to  cause     the  same  updating of    RPT-bit    settings
  407.    upstream and    pull down all active sources' packets. If  the    arriving
  408.    (*,G)  join    has  some  sources  included in    its prune list,    then the
  409.    corresponding (S,G)RPT-bit entries  are  left  unchanged  (i.e.,  the
  410.    RPT-bit remains set and no oif is added).
  411.  
  412.  
  413. 2.5 Steady state maintenance of    distribution tree (i.e., router    state)}
  414.  
  415.    In the steady state each router sends  periodic  Join/Prune    messages
  416.    for    each active PIM    route entry; the Join/Prune messages are sent to
  417.    the neighbor    indicated in the corresponding entry. These messages are
  418.    sent    periodically to    capture    state, topology, and membership    changes.
  419.    A Join/Prune    message    is also    sent on    an  event-triggered  basis  each
  420.    time     a new route entry is established for some new source (note that
  421.  
  422.  
  423.  
  424. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Weia[Page 7]
  425.  
  426.  
  427.  
  428.  
  429.  
  430. Internet Draft          PIM-SM Specification              March 1997
  431.  
  432.  
  433.    some    damping    function may be    applied, e.g., a short    delay  to  allow
  434.    for    merging     of  new  Join    information). Join/Prune messages do not
  435.    elicit any form of explicit acknowledgment; routers recover from lost
  436.    packets using the periodic refresh mechanism.
  437.  
  438. 2.6 Obtaining RP information
  439.  
  440.    To obtain the RP information, all routers within a PIM domain collect
  441.    Bootstrap messages. Bootstrap messages are sent hop-by-hop within the
  442.    domain; the    domain's  bootstrap  router  (BSR)  is    responsible  for
  443.    originating    the  Bootstrap    messages. Bootstrap messages are used to
  444.    carry out a dynamic BSR election when needed     and  to  distribute  RP
  445.    information in steady state.
  446.  
  447.    A domain in this context is a contiguous  set  of  routers  that  all
  448.    implement  PIM and are configured to    operate    within a common    boundary
  449.    defined by PIM Multicast Border Routers (PMBRs). PMBRs  connect  each
  450.    PIM domain to the rest of the internet.
  451.  
  452.    Routers use a set of    available RPs (called the RP-Set) distributed
  453.    in  Bootstrap  messages  to    get  the proper    Group to RP mapping. The
  454.    following  paragraphs  summarize  the  mechanism;  details    of   the
  455.    mechanism  may  be  found in    Sections 3.6 and Appendix 6.2. A (small)
  456.    set of routers, within a domain, are     configured  as     candidate  BSRs
  457.    and,     through  a  simple election mechanism,    a single BSR is    selected
  458.    for that domain. A set of routers within a domain are also configured
  459.    as  candidate  RPs  (C-RPs);    typically these    will be    the same routers
  460.    that    are configured as C-BSRs.  Candidate  RPs  periodically     unicast
  461.    Candidate-RP-Advertisement  messages     (C-RP-Advs)  to the BSR of that
  462.    domain. C-RP-Advs include the address of  the  advertising  C-RP,  as
  463.    well    as an optional group address and a mask    length field, indicating
  464.    the group prefix(es)    for which the candidacy    is advertised.    The  BSR
  465.    then     includes  a set of these Candidate-RPs    (the RP-Set), along with
  466.    the    corresponding  group  prefixes,      in   Bootstrap   messages   it
  467.    periodically     originates.  Bootstrap    messages are distributed hop-by-
  468.    hop throughout the domain.
  469.  
  470.  
  471.    Routers receive and store Bootstrap messages    originated by  the  BSR.
  472.    When     a  DR    gets  a     membership  indication    from IGMP for (or a data
  473.    packet from)    a directly connected host, for a group for which it  has
  474.    no entry, the DR uses a hash    function to map    the group address to one
  475.    of the C-RPs    whose  Group-prefix  includes  the  group  (see     Section
  476.    3.7).  The  DR  then     sends a Join/Prune message towards (or    unicasts
  477.    Registers to) that RP.
  478.  
  479.    The Bootstrap message indicates liveness of the RPs included    therein.
  480.    If an RP is included    in the message,    then it    is tagged as `up' at the
  481.  
  482.  
  483.  
  484. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Weia[Page 8]
  485.  
  486.  
  487.  
  488.  
  489.  
  490. Internet Draft          PIM-SM Specification              March 1997
  491.  
  492.  
  493.    routers; while RPs not included in the message are removed  from  the
  494.    list    of RPs over which the hash algorithm acts. Each    router continues
  495.    to use the contents of the most recently received  Bootstrap     message
  496.    until it receives a new Bootstrap message.
  497.  
  498.    If a    PIM domain partitions, each area separated from    the old    BSR will
  499.    elect  its  own  BSR,  which    will distribute    an RP-Set containing RPs
  500.    that    are reachable within that partition. When the  partition  heals,
  501.    another  election  will  occur automatically    and only one of    the BSRs
  502.    will    continue to send out Bootstrap messages. As is expected     at  the
  503.    time     of  a    partition or healing, some disruption in packet    delivery
  504.    may occur. This time    will be    on the order of    the region's  round-trip
  505.    time    and the    bootstrap router timeout value.
  506.  
  507. 2.7 Interoperation with    dense mode  protocols such as DVMRP
  508.  
  509.    In order  to     interoperate  with  networks  that  run  dense-mode,
  510.    broadcast and prune,    protocols, such    as DVMRP, all packets generated
  511.    within a PIM-SM region must    be  pulled  out     to  that  region's  PIM
  512.    Multicast  Border Routers (PMBRs) and injected (i.e., broadcast) into
  513.    the DVMRP network. A    PMBR is    a router that sits at the boundary of  a
  514.    PIM-SM domain and interoperates with    other types of multicast routers
  515.    such    as those that run DVMRP.  Generally  a    PMBR  would  speak  both
  516.    protocols  and  implement  interoperability functions not required by
  517.    regular PIM routers.    To support  interoperability,  a  special  entry
  518.    type,  referred to as (*,*,RP), must    be supported by    all PIM    routers.
  519.    For this reason we include details about (*,*,RP) entry  handling  in
  520.    this    general    PIM specification.
  521.  
  522.    A data packet will match on a (*,*,RP) entry     if  there  is    no  more
  523.    specific  entry  (such  as  (S,G) or    (*,G)) and the destination group
  524.    address in the packet maps to the RP    listed in the (*,*,RP) entry. In
  525.    this     sense,     a  (*,*,RP)  entry represents an aggregation of all the
  526.    groups that hash to that RP.    PMBRs initialize (*,*,RP) state    for each
  527.    RP in the domain's RPset. The (*,*,RP) state    causes the PMBRs to send
  528.    (*,*,RP) Join/Prune messages    toward each of the  active  RPs     in  the
  529.    domain.  As a result    distribution trees are built that carry    all data
  530.    packets originated within the PIM domain (and sent to the  RPs)  down
  531.    to the PMBRs.
  532.  
  533.    PMBRs  are  also  responsible  for  delivering   externally-generated
  534.    packets  to    routers    within the PIM domain. To do so, PMBRs initially
  535.    encapsulate externally-originated packets (i.e.,  received  on  DVMRP
  536.    interfaces)     in   Register     messages   and      unicast  them     to  the
  537.    corresponding RP within the PIM domain. The Register     message  has  a
  538.    bit    indicating  that it was    originated by a    border router and the RP
  539.    caches the originating PMBR's address in  the  route     entry    so  that
  540.    duplicate   Registers  from    other  PMBRs  can  be  declined     with  a
  541.  
  542.  
  543.  
  544. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Weia[Page 9]
  545.  
  546.  
  547.  
  548.  
  549.  
  550. Internet Draft          PIM-SM Specification              March 1997
  551.  
  552.  
  553.    Register-Stop message.
  554.  
  555.    All PIM routers must    be capable  of    supporting  (*,*,RP)  state  and
  556.    interpreting    associated Join/Prune messages.    We describe the    handling
  557.    of (*,*,RP) entries and messages throughout this  document;    however,
  558.    detailed  PIM  Multicast  Border  Router  (PMBR)  functions    will  be
  559.    specified in    a separate  interoperability  document    (see  directory,
  560.    http://catarina.usc.edu/pim/interop/).
  561.  
  562.  
  563. 2.8 Multicast data packet processing
  564.  
  565.    Data    packets    are processed in a manner  similar  to    other  multicast
  566.    schemes.  A    router    first performs a longest match on the source and
  567.    group address in the    data packet. A (S,G) entry is matched  first  if
  568.    one    exists;     a  (*,G)  entry  is matched otherwise.    If neither state
  569.    exists, then    a (*,*,RP) entry match    is  attempted  as  follows:  the
  570.    router  hashes  on  G to identify the RP for    group G, and looks for a
  571.    (*,*,RP) entry that has this    RP address associated with it.    If  none
  572.    of  the  above  exists,  then  the  packet  is dropped. If a    state is
  573.    matched, the    router    compares  the  interface  on  which  the  packet
  574.    arrived  to    the incoming interface field in    the matched route entry.
  575.    If the iif check fails the packet is    dropped, otherwise the packet is
  576.    forwarded to    all interfaces listed in the outgoing interface    list.
  577.  
  578.    Some    special    actions    are needed to deliver packets continuously while
  579.    switching  from the shared to shortest-path tree. In    particular, when
  580.    a (S,G) entry is matched, incoming packets are forwarded as follows:
  581.  
  582.  
  583.     1    If    the SPT-bit is set, then:
  584.  
  585.  
  586.          1      if the incoming interface is the same     as  a    matching
  587.           (S,G)     iif, the packet is forwarded to the oif-list of
  588.           (S,G).
  589.  
  590.          2      if the incoming interface is different than a    matching
  591.           (S,G)    iif , the packet is discarded.
  592.  
  593.  
  594.  
  595.     2    If    the SPT-bit is cleared,    then:
  596.  
  597.  
  598.          1      if the incoming interface is the same     as  a    matching
  599.           (S,G)     iif, the packet is forwarded to the oif-list of
  600.           (S,G). In addition, the SPT bit is set for that  entry
  601.  
  602.  
  603.  
  604. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 10]
  605.  
  606.  
  607.  
  608.  
  609.  
  610. Internet Draft          PIM-SM Specification              March 1997
  611.  
  612.  
  613.           if  the  incoming  interface differs from the    incoming
  614.           interface of the (*,G) or (*,*,RP) entry.
  615.  
  616.          2      if the incoming interface is different than a    matching
  617.           (S,G)     iif, the incoming interface is    tested against a
  618.           matching (*,G) or (*,*,RP) entry. If the  iif     is  the
  619.           same    as  one    of those, the packet is    forwarded to the
  620.           oif-list of the matching entry.
  621.  
  622.          3      Otherwise the    iif does not match any entry for  G  and
  623.           the packet is    discarded.
  624.  
  625.  
  626.  
  627.     Data packets never trigger prunes.  However,  data  packets  may
  628.     trigger     actions  that in turn trigger prunes. For example, when
  629.     router    B in figure 3 decides to switch    to SP-tree at step 3, it
  630.     creates     a  (S,G) entry    with SPT-bit set to 0. When data packets
  631.     from S arrive at interface 2 of     B,  B sets  the  SPT-bit  to  1
  632.     since  the  iif    for (*,G) is different than that for (S,G). This
  633.     triggers the sending of    prunes towards the RP.
  634.  
  635.  
  636.      2.9 Operation over    Multi-access Networks
  637.  
  638.  
  639.     This section describes    a  few    additional  protocol  mechanisms
  640.     needed    to  operate  PIM  over multi-access networks: Designated
  641.     Router election, Assert    messages to resolve parallel paths,  and
  642.     the  Join/Prune-Suppression-Timer to suppress redundant    Joins on
  643.     multi-access networks.
  644.  
  645.     Designated router election:
  646.  
  647.     When there are multiple     routers  connected  to     a  multi-access
  648.     network, one of    them must be chosen to operate as the designated
  649.     router (DR) at any point in time.  The    DR  is    responsible  for
  650.     sending     triggered  Join/Prune    and Register messages toward the
  651.     RP.
  652.  
  653.     A simple designated router (DR)    election mechanism is  used  for
  654.     both  SM  and  traditional  IP    multicast  routing.  Neighboring
  655.     routers    send Hello messages to each other. The sender  with  the
  656.     largest     network  layer     address  assumes  the    role of    DR. Each
  657.     router connected  to  the  multi-access     LAN  sends  the  Hellos
  658.     periodically in    order to adapt to changes in router status.
  659.  
  660.  
  661.  
  662.  
  663.  
  664. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 11]
  665.  
  666.  
  667.  
  668.  
  669.  
  670. Internet Draft          PIM-SM Specification              March 1997
  671.  
  672.  
  673.     Parallel  paths     to  a    source    or  the     RP--Assert process:
  674.  
  675.     If a router receives a multicast datagram on a multi-access  LAN
  676.     from  a    source whose corresponding (S,G) outgoing interface list
  677.     includes the interface    to  that  LAN,    the  packet  must  be  a
  678.     duplicate.  In    this  case  a  single forwarder    must be    elected.
  679.     Using Assert messages addressed    to `224.0.0.13'    (ALL-PIM-ROUTERS
  680.     group)    on  the    LAN, upstream routers can resolve which    one will
  681.     act as the forwarder. Downstream routers listen    to  the     Asserts
  682.     so  they know which one    was elected, and therefore where to send
  683.     subsequent Joins. Typically this is the    same as     the  downstream
  684.     router's  RPF  (Reverse    Path Forwarding) neighbor; but there are
  685.     circumstances where this might not be the case,    e.g., when using
  686.     multiple unicast routing protocols on that LAN.    The RPF    neighbor
  687.     for a particular source    (or RP)    is the next-hop    router to  which
  688.     packets     are  forwarded     en  route  to    that source (or    RP); and
  689.     therefore is considered    a good path via    which to accept     packets
  690.     from that source.
  691.  
  692.     The upstream router elected is the one    that  has  the    shortest
  693.     distance  to the source. Therefore, when a packet is received on
  694.     an outgoing interface a    router sends an    Assert    message     on  the
  695.     multi-access  LAN  indicating  what  metric it uses to reach the
  696.     source    of  the     data  packet.    The  router  with  the    smallest
  697.     numerical  metric  (with  ties    broken    by highest address) will
  698.     become the forwarder. All other    upstream routers will delete the
  699.     interface  from     their    outgoing  interface list. The downstream
  700.     routers     also  do  the    comparison  in    case  the  forwarder  is
  701.     different than the RPF neighbor.
  702.  
  703.     Associated with    the metric is a    metric preference value. This is
  704.     provided  to  deal  with the case where    the upstream routers may
  705.     run different unicast routing protocols. The numerically smaller
  706.     metric    preference is always preferred.    The metric preference is
  707.     treated    as the high-order part of an assert  metric  comparison.
  708.     Therefore,  a  metric  value can be compared with another metric
  709.     value provided both metric preferences are the    same.  A  metric
  710.     preference  can     be  assigned  per  unicast routing protocol and
  711.     needs to be consistent    for  all  routers  on  the  multi-access
  712.     network.
  713.  
  714.     Asserts    are also needed    for (*,G) entries since    an  RP-Tree  and
  715.     an  SP-Tree  for  the  same group may both cross the same multi-
  716.     access network.    When an    assert is sent for a  (*,G)  entry,  the
  717.     first  bit in the metric preference (RPT-bit) is always    set to 1
  718.     to indicate that this path corresponds to the RP tree, and  that
  719.     the  match  must be done on (*,G) if it    exists.    Furthermore, the
  720.  
  721.  
  722.  
  723. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 12]
  724.  
  725.  
  726.  
  727.  
  728.  
  729. Internet Draft          PIM-SM Specification              March 1997
  730.  
  731.  
  732.     RPT-bit    is always cleared for metric preferences that  refer  to
  733.     SP-tree     entries;  this     causes     an  SP-tree path to always look
  734.     better than an RP-tree path. When the SP-tree and  RPtree  cross
  735.     the  same  LAN,     this  mechanism  eliminates the duplicates that
  736.     would otherwise    be carried over    the LAN.
  737.  
  738.     In case    the packet, or the Assert message, matches  on    oif  for
  739.     (*,*,RP) entry,    a (*,G)    entry is created, and asserts take place
  740.     as if the matching state were (*,G).
  741.  
  742.  
  743.     The DR may lose    the (*,G) Assert process to  another  router  on
  744.     the  LAN  if there are multiple    paths to the RP    through    the LAN.
  745.     From then on, the DR is    no longer the last-hop router for  local
  746.     receivers  and    removes     the  LAN  from     its (*,G) oif list. The
  747.     winning    router becomes the last-hop router  and     is  responsible
  748.     for sending (*,G) join messages    to the RP.
  749.  
  750.     Join/Prune suppression:
  751.  
  752.     Join/Prune suppression may  be    used  on  multi-access    LANs  to
  753.     reduce    duplicate  control  message overhead; it is not    required
  754.     for correct performance    of the protocol. If a Join/Prune message
  755.     arrives     and  matches  on the incoming interface for an    existing
  756.     (S,G), (*,G), or (*,*,RP) route    entry, and the Holdtime    included
  757.     in  the     Join/Prune  message is    greater    than the recipient's own
  758.     [Join/Prune-Holdtime] (with ties resolved in favor of the higher
  759.     network     layer    address),  a  timer (the Join/Prune-Suppression-
  760.     timer) in the recipient's route    entry may be started to    suppress
  761.     further     Join/Prune  messages.    After  this  timer  expires, the
  762.     recipient triggers a Join/Prune     message,  and    resumes     sending
  763.     periodic   Join/Prunes,      for    this   entry.    The  Join/Prune-
  764.     Suppression-timer should be restarted  each  time  a  Join/Prune
  765.     message    is received with a higher Holdtime.
  766.  
  767.      2.10 Unicast Routing Changes
  768.  
  769.     When unicast routing changes, an RPF check is done on all active
  770.     (S,G),    (*,G)  and  (*,*,RP)  entries, and all affected    expected
  771.     incoming interfaces are     updated.  In  particular,  if    the  new
  772.     incoming interface appears in the outgoing interface list, it is
  773.     deleted    from the outgoing interface list. The previous    incoming
  774.     interface  may    be  added  to  the  outgoing interface list by a
  775.     subsequent  Join/Prune    from  downstream.  Join/Prune    messages
  776.     received   on    the  current  incoming    interface  are    ignored.
  777.     Join/Prune messages  received  on  new    interfaces  or    existing
  778.     outgoing  interfaces  are not ignored. Other outgoing interfaces
  779.     are left as is until they are explicitly  pruned  by  downstream
  780.  
  781.  
  782.  
  783. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 13]
  784.  
  785.  
  786.  
  787.  
  788.  
  789. Internet Draft          PIM-SM Specification              March 1997
  790.  
  791.  
  792.     routers     or  are timed out due to lack of appropriate Join/Prune
  793.     messages. If the router    has a (S,G) entry with the SPT-bit  set,
  794.     and  the  updated  iif(S,G)  does   not     differ    from iif(*,G) or
  795.     iif(*,*,RP), then the router resets the    SPT-bit.
  796.  
  797.     The router must    send a Join/Prune message with    S  in  the  Join
  798.     list  out any new incoming interfaces to inform    upstream routers
  799.     that it    expects    multicast datagrams over the interface.     It  may
  800.     also  send a Join/Prune    message    with S in the Prune list out the
  801.     old incoming interface,    if the link is    operational,  to  inform
  802.     upstream  routers  that     this  part  of    the distribution tree is
  803.     going away.
  804.  
  805.  
  806.      2.11 PIM-SM for Inter-Domain Multicast
  807.  
  808.  
  809.     Future documents will address the use of PIM-SM     as  a    backbone
  810.     inter-domain  multicast     routing protocol. Design choices center
  811.     primarily around the distribution and usage  of     RP  information
  812.     for wide area, inter-domain groups.
  813.  
  814.      2.12 Security
  815.  
  816.     All PIM    control    messages may use IPsec [6] to  address    security
  817.     concerns.  Security  mechanisms    are likely to be enhanced in the
  818.     near future.
  819.  
  820.  
  821.  
  822.  
  823.  
  824.  
  825.  
  826.  
  827.  
  828.  
  829.  
  830.  
  831.  
  832.  
  833.  
  834.  
  835.  
  836.  
  837.  
  838.  
  839.  
  840.  
  841.  
  842.  
  843. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 14]
  844.  
  845.  
  846.  
  847.  
  848.  
  849. Internet Draft          PIM-SM Specification              March 1997
  850.  
  851.  
  852.      3 Detailed    Protocol Description
  853.  
  854.  
  855.     This  section  describes  the  protocol     operations   from   the
  856.     perspective   of   an    individual   router  implementation.  In
  857.     particular,  for  each    message     type  we  describe  how  it  is
  858.     generated and processed.
  859.  
  860.      3.1 Hello
  861.  
  862.     Hello messages are sent    so neighboring routers can discover each
  863.     other.
  864.  
  865.      3.1.1 Sending Hellos
  866.  
  867.     Hello messages are  sent  periodically    between     PIM  neighbors,
  868.     every    [Hello-Period]     seconds.   This  informs  routers  what
  869.     interfaces have    PIM  neighbors.     Hello    messages  are  multicast
  870.     using  address    224.0.0.13  (ALL-PIM-ROUTERS  group). The packet
  871.     includes a Holdtime, set to [Hello-Holdtime], for  neighbors  to
  872.     keep  the  information    valid.    Hellos    are sent on all    types of
  873.     communication links.
  874.  
  875.      3.1.2 Receiving Hellos
  876.  
  877.     When a router receives a Hello message,    it  stores  the     network
  878.     layer address for that neighbor, sets its Neighbor-timer for the
  879.     Hello  sender  to  the    Holdtime  included  in    the  Hello,  and
  880.     determines  the     Designated  Router (DR) for that interface. The
  881.     highest    addressed system is  elected  DR.  Each     Hello    received
  882.     causes the DR's    address    to be updated.
  883.  
  884.     When a router that is the active DR receives a Hello from a  new
  885.     neighbor  (i.e.,  from    an  address  that  is not yet in the DRs
  886.     neighbor  table),  the    DR  unicasts  its  most     recent      RP-set
  887.     information to the new neighbor.
  888.  
  889.      3.1.3 Timing out neighbor entries
  890.  
  891.     A periodic process is run to time out PIM  neighbors  that  have
  892.     not  sent Hellos. If the DR has    gone down, a new DR is chosen by
  893.     scanning all neighbors on the interface    and selecting the new DR
  894.     to  be    the  one  with    the highest network layer address. If an
  895.     interface has gone down, the router may    optionally time    out  all
  896.     PIM neighbors associated with the interface.
  897.  
  898.  
  899.  
  900.  
  901.  
  902.  
  903. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 15]
  904.  
  905.  
  906.  
  907.  
  908.  
  909. Internet Draft          PIM-SM Specification              March 1997
  910.  
  911.  
  912.      3.2 Join/Prune
  913.  
  914.     Join/Prune messages are    sent to    join or    prune a     branch     off  of
  915.     the  multicast distribution tree. A single message contains both
  916.     a join and prune list, either one of which  may     be  null.  Each
  917.     list  contains a set of    source addresses, indicating the source-
  918.     specific trees or shared tree that the router wants to    join  or
  919.     prune.
  920.  
  921.      3.2.1 Sending Join/Prune Messages
  922.  
  923.  
  924.     Join/Prune messages are    merged such that a  message  sent  to  a
  925.     particular  upstream  neighbor,     N,  includes all of the current
  926.     joined and pruned sources that are reached via N;  according  to
  927.     unicast    routing    Join/Prune messages are    multicast to all routers
  928.     on multi-access    networks with the target address set to    the next
  929.     hop  router  towards S or RP. Join/Prune messages are sent every
  930.     [Join/Prune-Period] seconds. In    the  future  we     will  introduce
  931.     mechanisms  to    rate-limit  this control traffic on a hop by hop
  932.     basis, in order    to avoid excessive overhead on small  links.  In
  933.     addition,  certain events cause    triggered Join/Prune messages to
  934.     be sent.
  935.  
  936.     Periodic Join/Prune Messages:
  937.  
  938.     A  router  sends  a periodic Join/Prune    message    to each    distinct
  939.     RPF neighbor associated    with  each  (S,G),  (*,G)  and    (*,*,RP)
  940.     entry.    Join/Prune messages are    only sent if the RPF neighbor is
  941.     a  PIM    neighbor.  A  periodic    Join/Prune  message  sent  to  a
  942.     particular RPF neighbor    is constructed as follows:
  943.  
  944.  
  945.  
  946.     1     Each router determines the RP for    a (*,G)    entry  by  using
  947.          the  hash    function described. The    RP address (with RPT and
  948.          WC    bits set) is included in the join  list     of  a    periodic
  949.          Join/Prune    message    under the following conditions:
  950.  
  951.  
  952.          1      The Join/Prune  message  is  being  sent  to    the  RPF
  953.           neighbor toward the RP for an    active (*,G) or    (*,*,RP)
  954.           entry, and
  955.  
  956.          2      The outgoing interface list in the (*,G)  or    (*,*,RP)
  957.           entry    is non-NULL, or    the router is the DR on    the same
  958.           interface as the RPF neighbor.
  959.  
  960.  
  961.  
  962.  
  963. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 16]
  964.  
  965.  
  966.  
  967.  
  968.  
  969. Internet Draft          PIM-SM Specification              March 1997
  970.  
  971.  
  972.     2    A particular source address, S, is     included  in  the  join
  973.          list  with     the RPT and WC    bits cleared under the following
  974.          conditions:
  975.  
  976.  
  977.          1      The Join/Prune  message  is  being  sent  to    the  RPF
  978.           neighbor toward S, and
  979.  
  980.          2      There    exists an active (S,G) entry  with  the     RPT-bit
  981.           flag cleared,    and
  982.  
  983.          3      The oif list in the (S,G) entry is not null.
  984.  
  985.  
  986.  
  987.     3    A particular source address, S, is    included  in  the  prune
  988.          list  with     the RPT and WC    bits cleared under the following
  989.          conditions:
  990.  
  991.  
  992.          1      The Join/Prune  message  is  being  sent  to    the  RPF
  993.           neighbor toward S, and
  994.  
  995.          2      There    exists an active (S,G) entry  with  the     RPT-bit
  996.           flag cleared,    and
  997.  
  998.          3      The oif list in the (S,G) entry is null.
  999.  
  1000.  
  1001.  
  1002.     4    A particular source address, S, is    included  in  the  prune
  1003.          list with the RPT-bit  set    and the    WC bit cleared under the
  1004.          following conditions:
  1005.  
  1006.  
  1007.          1      The Join/Prune  message  is  being  sent  to    the  RPF
  1008.           neighbor  toward the RP and there exists a (S,G) entry
  1009.           with the RPT-bit flag    set and    null oif list, or
  1010.  
  1011.          2      The Join/Prune  message  is  being  sent  to    the  RPF
  1012.           neighbor  toward  the     RP,  there exists a (S,G) entry
  1013.           with the RPT-bit flag    cleared    and SPT-bit set, and the
  1014.           incoming  interface  toward  S  is  different    than the
  1015.           incoming interface toward the    RP, or
  1016.  
  1017.          3      The Join/Prune  message  is  being  sent  to    the  RPF
  1018.           neighbor toward the RP, and there exists a (*,G) entry
  1019.           and (S,G) entry for a    directly connected source.
  1020.  
  1021.  
  1022.  
  1023. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 17]
  1024.  
  1025.  
  1026.  
  1027.  
  1028.  
  1029. Internet Draft          PIM-SM Specification              March 1997
  1030.  
  1031.  
  1032.     5    The RP address (with RPT and WC bits set)    is  included  in
  1033.          the prune list if:
  1034.  
  1035.  
  1036.  
  1037.          1      The Join/Prune  message  is  being  sent  to    the  RPF
  1038.           neighbor  toward the RP and there exists a (*,G) entry
  1039.           with a null oif list (see Section  3.5.2).
  1040.  
  1041.  
  1042.  
  1043.     Triggered Join/Prune Messages:
  1044.  
  1045.     In  addition  to  periodic  messages,  the following events will
  1046.     trigger    Join/Prune messages if as a result, a) a  new  entry  is
  1047.     created,  or  b)  the  oif list    changes    from null to non-null or
  1048.     non-null to null. The contents of  triggered  messages    are  the
  1049.     same as    the periodic, described    above.
  1050.  
  1051.  
  1052.     1    Receipt of    an  indication    from  IGMP  that  the  state  of
  1053.          directly-connected-   membership  has  changed  (i.e.,  new
  1054.          members have just joined  `membership  indication'     or  all
  1055.          members  have  left), for a group G, may cause the    last-hop
  1056.          router to build or    modify corresponding (*,G)  state.  When
  1057.          IGMP  indicates that there    are no longer directly connected
  1058.          members, the oif is removed from the oif list if  the  oif-
  1059.          timer  is not running. A Join/Prune message is triggered if
  1060.          and only if a) a new entry    is created, or b) the  oif  list
  1061.          changes  from  null  to  non-null    or  non-null to    null, as
  1062.          follows :
  1063.  
  1064.  
  1065.          1      If the receiving router does not have     a  route  entry
  1066.           for G    the router creates a (*,G) entry, copies the oif
  1067.           list from the     corresponding    (*,*,RP)  entry     (if  it
  1068.           exists),  and     includes  the interface included in the
  1069.           IGMP membership indication in    the oif    list; as always,
  1070.           the  router  never includes the entry's iif in the oif
  1071.           list.    The router sends a  Join/Prune    message     towards
  1072.           the RP with the RP address and RPT-bit and WC-bits set
  1073.           in the join list. Or,
  1074.  
  1075.  
  1076.          2      If a (S,G)RPT-bit or (*,G) entry already  exists,  the
  1077.           interface  included  in the IGMP membership indication
  1078.           is added to the oif  list  (if  it  was  not    included
  1079.           already).
  1080.  
  1081.  
  1082.  
  1083. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 18]
  1084.  
  1085.  
  1086.  
  1087.  
  1088.  
  1089. Internet Draft          PIM-SM Specification              March 1997
  1090.  
  1091.  
  1092.     2    Receipt  of  a  Join/Prune     message  for  (S,G),  (*,G)  or
  1093.          (*,*,RP)  will  cause  building  or modifying corresponding
  1094.          state, and    subsequent  triggering    of  upstream  Join/Prune
  1095.          messages, in the following    cases:
  1096.  
  1097.  
  1098.          1      When there is    no current route entry,    the  RP     address
  1099.           included  in the Join/Prune message is checked against
  1100.           the local RP-Set information.    If it matches, an  entry
  1101.           will be created and the new entry will in turn trigger
  1102.           an upstream Join/Prune message. If the router     has  no
  1103.           RP-Set  information  it  may    discard     the message, or
  1104.           optionally use the RP    address    included in the    message.
  1105.  
  1106.  
  1107.          2      When the outgoing interface list  of    an  (S,G)RPT-bit
  1108.           entry     becomes  null,    the triggered Join/Prune message
  1109.           will contain S in the    prune list.
  1110.  
  1111.  
  1112.          3      When there exists a (S,G)RPT-bit with    null  oif  list,
  1113.           and  an  (*,G)  Join/Prune  message  is  received, the
  1114.           arriving interface is    added to  the  oif  list  and  a
  1115.           (*,G)    Join/Prune message is triggered    upstream.
  1116.  
  1117.  
  1118.          4      When there exists a (*,G) with null oif  list,  and  a
  1119.           (*,*,RP) Join/Prune message is received, the receiving
  1120.           interface is added to    the  oif  list    and  a    (*,*,RP)
  1121.           Join/Prune message is    triggered upstream.
  1122.  
  1123.  
  1124.  
  1125.  
  1126.     3    Receipt of    a packet that matches on  a  (S,G)  entry  whose
  1127.          SPT-bit  is  cleared  triggers  the following if the packet
  1128.          arrived on    the correct incoming interface and  there  is  a
  1129.          (*,G)   or      (*,*,RP)   entry  with  a  different    incoming
  1130.          interface:    a) the router sets  the     SPT-bit  on  the  (S,G)
  1131.          entry, and    b) the router sends a Join/Prune message towards
  1132.          the RP with S in the prune    list and the RPT-bit set.
  1133.  
  1134.  
  1135.     4    Receipt of    a packet at the    DR  from  a  directly  connected
  1136.          source  S,    on the subnet containing the address S,    triggers
  1137.          a Join/Prune message towards the RP with  S  in  the  prune
  1138.          list and the RPT-bit set under the    following conditions: a)
  1139.          there is no matching (S,G)    state, and  b)    there  exists  a
  1140.  
  1141.  
  1142.  
  1143. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 19]
  1144.  
  1145.  
  1146.  
  1147.  
  1148.  
  1149. Internet Draft          PIM-SM Specification              March 1997
  1150.  
  1151.  
  1152.          (*,G) or (*,*,RP) for which the DR    is not the RP.
  1153.  
  1154.  
  1155.     5    When a Join/Prune message is received for a  group     G,  the
  1156.          prune  list is checked. If    the prune list contains    a source
  1157.          or    RP for which the receiving router  has    a  corresponding
  1158.          active (S,G), (*,G) or (*,*,RP) entry, and    whose iif is
  1159.          that on which the Join/Prune was received,    then a join  for
  1160.          (S,G),  (*,G)  or    (*,*,RP)  is  triggered     to override the
  1161.          prune, respectively. (This    is  necessary  in  the    case  of
  1162.          parallel  downstream  routers  connected  to a multi-access
  1163.          network.)
  1164.  
  1165.  
  1166.     6    When the RP fails,    the RP    will  not  be  included     in  the
  1167.          Bootstrap messages    sent to    all routers in that domain. This
  1168.          triggers the DRs to send (*,G) Join/Prune messages     towards
  1169.          the  new  RP for the group, as determined by the RP-Set and
  1170.          the hash function.     As  described    earlier,  PMBRs     trigger
  1171.          (*,*,RP) joins towards each RP in the RP-Set.
  1172.  
  1173.  
  1174.     7    When an entry's  Join/Prune-Suppression  timer  expires,  a
  1175.          Join/Prune     message  is triggered upstream    corresponding to
  1176.          that  entry,  even     if  the  outgoing  interface  has   not
  1177.          transitioned between null and non-null states.
  1178.  
  1179.     8    When the RPF neighbor changes (whether due    to an Assert  or
  1180.          changes in    unicast    routing), the router sets a random delay
  1181.          timer  (the   Random-Delay-Join-Timer)   whose   expiration
  1182.          triggers  sending    of a Join/Prune    message    for the    asserted
  1183.          route  entry  to  the  Assert  winner  (if     the  Join/Prune
  1184.          Suppression timer has expired.)
  1185.  
  1186.     We do not trigger prunes onto interfaces based on data    packets.
  1187.     Data  packets  that  arrive  on    the wrong incoming interface are
  1188.     silently  dropped.   However,    on   point-to-point   interfaces
  1189.     triggered prunes may be    sent as    an optimization.
  1190.  
  1191.     aragraphFragmentation It is possible that a  Join/Prune     message
  1192.     constructed  according    to  the    preceding rules    could exceed the
  1193.     MTU of a network. In this case,    the message can    undergo    semantic
  1194.     fragmentation  whereby    information  corresponding  to different
  1195.     groups    can  be     sent  in  different  messages.     However,  if  a
  1196.     Join/Prune  message  must  be fragmented the complete prune list
  1197.     corresponding to  a  group  G  must  be     included  in  the  same
  1198.     Join/Prune message as the associated RP-tree Join for G. If such
  1199.     semantic fragmentation is not possible,    IP fragmentation  should
  1200.  
  1201.  
  1202.  
  1203. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 20]
  1204.  
  1205.  
  1206.  
  1207.  
  1208.  
  1209. Internet Draft          PIM-SM Specification              March 1997
  1210.  
  1211.  
  1212.     be used    between    the two    neighboring hops.
  1213.  
  1214.  
  1215.      3.2.2 Receiving  Join/Prune  Messages  When  a  router  receives  a
  1216.     Join/Prune message, it processes it as follows.
  1217.  
  1218.  
  1219.     The receiver of    the Join/Prune notes the interface on which  the
  1220.     PIM  message arrived, call it I. The receiver then checks to see
  1221.     if the Join/Prune message was addressed    to the receiving  router
  1222.     itself    (i.e.,    the  router's  address    appears     in  the Unicast
  1223.     Upstream Neighbor Router field of the Join/Prune  message).  (If
  1224.     the  router is connected to a multiaccess LAN, the message could
  1225.     be intended for    a different router.) If    the  Join/Prune     is  for
  1226.     this router the    following actions are taken.
  1227.  
  1228.     For each  group     address  G,  in  the  Join/Prune  message,  the
  1229.     associated  join  list is processed as follows.    We refer to each
  1230.     address    in the join list as Sj;    Sj refers to the RP if the  RPT-
  1231.     bit and    WC-bit are both    set. For each Sj in the    join list of the
  1232.     Join/Prune message:
  1233.  
  1234.  
  1235.     1    If    an address, Sj,    in  the     join  list  of     the  Join/Prune
  1236.          message  has  the RPT-bit and WC-bit set, then Sj is the RP
  1237.          address used by the downstream router(s) and the  following
  1238.          actions are taken:
  1239.  
  1240.  
  1241.          1      If Sj    is not the same    as  the     receiving  router's  RP
  1242.           mapping  for    G,  the     receiving router may ignore the
  1243.           Join/Prune message with respect to that  group  entry.
  1244.           If the router    does not have any RP-Set information, it
  1245.           may use the address  Sj  included  in     the  Join/Prune
  1246.           message as the RP for    the group.
  1247.  
  1248.          2      If Sj    is the same as the receiving router's RP mapping
  1249.           for  G,  the    receiving  router adds I to the    outgoing
  1250.           interface list of the    (*,G) route entry (if  there  is
  1251.           no (*,G) entry, the router creates one first)    and sets
  1252.           the Oif-timer     for  that  interface  to  the    Holdtime
  1253.           specified  in    the Join/Prune message.    In addition, the
  1254.           Oif-Deletion-Delay for that interface    is set to  1/3rd
  1255.           the Holdtime specified in the    Join/Prune message. If a
  1256.           (*,*,RP) entry exists, for the RP associated    with  G,
  1257.           then    the oif    list of    the newly created (*,G)    entry is
  1258.           copied from that (*,*,RP) entry.
  1259.  
  1260.  
  1261.  
  1262.  
  1263. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 21]
  1264.  
  1265.  
  1266.  
  1267.  
  1268.  
  1269. Internet Draft          PIM-SM Specification              March 1997
  1270.  
  1271.  
  1272.          3      For each (Si,G) entry    associated with    group G:  i)  if
  1273.           Si  is not included in the prune list, ii) if    I is not
  1274.           on the same subnet as    the address Si,    and iii) if I is
  1275.           not  the iif,    then interface I is added to the oif
  1276.           list and the Oif-timer  for  that  interface    in  each
  1277.           affected  entry  is increased    (never decreased) to the
  1278.           Holdtime  included  in  the  Join/Prune  message.   In
  1279.           addition,  if     the  Oif-timer     for  that  interface is
  1280.           increased, the Oif-Deletion-Delay for     that  interface
  1281.           is   set  to    1/3rd  the  Holdtime  specified     in  the
  1282.           Join/Prune message.
  1283.  
  1284.           If the group address in the Join/Prune message is  `*'
  1285.           then    every (*,G) and    (S,G) entry, whose group address
  1286.           hashes to the    RP indicated in    the (*,*,RP)  Join/Prune
  1287.           message,  is    updated     accordingly. A    `*' in the group
  1288.           field    of the Join/Prune  is  represented  by    a  group
  1289.           address  224.0.0.0  and  a  group  mask  length  of 4,
  1290.           indicating a (*,*,RP)    Join.
  1291.  
  1292.  
  1293.          4      If the (Si,G)    entry has its RPT-bit flag set to 1, and
  1294.           its  oif  list  is  the same as the (*,G) oif
  1295.           list,    then the (Si,G)RPT-bit entry is    deleted,
  1296.  
  1297.  
  1298.          5      The incoming interface is set    to the interface used to
  1299.           send    unicast     packets  to  the  RP in the (*,G) route
  1300.           entry, i.e., RPF interface toward the    RP.
  1301.  
  1302.  
  1303.  
  1304.  
  1305.     2    For each address, Sj, in the join list  whose  RPT-bit  and
  1306.          WC-bit  are   not    set,  and for which there is no    existing
  1307.          (Sj,G) route entry, the router initiates  one.  The  router
  1308.          creates  a     (S,G)    entry and copies all outgoing interfaces
  1309.          from the (S,G)RPT-bit entry, if it    exists.    If there  is  no
  1310.          (S,G)  entry,  the    oif list is copied from    the (*,G) entry;
  1311.          and if there is no    (*,G) entry, the oif list is copied from
  1312.          the  (*,*,RP) entry, if it    exists.    In all cases, the iif of
  1313.          the (S,G) entry is    always excluded    from the oif list.
  1314.  
  1315.  
  1316.          1      The outgoing interface for (Sj,G) is    set  to     I.  The
  1317.           incoming  interface for (Sj,G) is set    to the interface
  1318.           used to send unicast packets    to  Sj    (i.e.,    the  RPF
  1319.           neighbor).
  1320.  
  1321.  
  1322.  
  1323. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 22]
  1324.  
  1325.  
  1326.  
  1327.  
  1328.  
  1329. Internet Draft          PIM-SM Specification              March 1997
  1330.  
  1331.  
  1332.          2      If the interface used    to reach Sj, is    the same  as  I,
  1333.           this represents an error (or a unicast routing change)
  1334.           and the Join/Prune must not be processed.
  1335.  
  1336.  
  1337.  
  1338.  
  1339.     3    For each address, Sj, in the join list  of     the  Join/Prune
  1340.          message, for which    there is an existing (Sj,G) route entry,
  1341.  
  1342.  
  1343.  
  1344.          1      If the RPT-bit  is  not  set    for  Sj     listed     in  the
  1345.           Join/Prune message, but the RPT-bit flag is set on the
  1346.           existing (Sj,G) entry, the router clears  the     RPT-bit
  1347.           flag    on the (Sj,G) entry, sets the incoming interface
  1348.           to point towards Sj for that (Sj,G) entry, and sends a
  1349.           Join/Prune message corresponding to that entry through
  1350.           the new incoming interface; and
  1351.  
  1352.  
  1353.          2      If  I     is  not  the  same  as     the  existing    incoming
  1354.           interface,  the  router adds I to the    list of    outgoing
  1355.           interfaces.
  1356.  
  1357.  
  1358.          3      The Oif-timer    for I is increased (never decreased)  to
  1359.           the  Holdtime     included  in the Join/Prune message. In
  1360.           addition, if    the  Oif-timer    for  that  interface  is
  1361.           increased,  the  Oif-Deletion-Delay for that interface
  1362.           is  set  to  1/3rd  the  Holdtime  specified    in   the
  1363.           Join/Prune message.
  1364.  
  1365.  
  1366.          4      The (Sj,G) entry's SPT bit is    cleared    until data comes
  1367.           down the shortest path tree.
  1368.  
  1369.  
  1370.  
  1371.  
  1372.  
  1373.     For each  group     address  G,  in  the  Join/Prune  message,  the
  1374.     associated  prune list is processed as follows.    We refer to each
  1375.     address    in the prune list as Sp; Sp refers  to    the  RP     if  the
  1376.     RPT-bit     and  WC-bit are both set. For each Sp in the prune list
  1377.     of the Join/Prune message:
  1378.  
  1379.  
  1380.  
  1381.  
  1382.  
  1383. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 23]
  1384.  
  1385.  
  1386.  
  1387.  
  1388.  
  1389. Internet Draft          PIM-SM Specification              March 1997
  1390.  
  1391.  
  1392.     1    For each address, Sp, in the prune    list whose  RPT-bit  and
  1393.          WC-bit are    cleared:
  1394.  
  1395.  
  1396.          1      If there is an existing (Sp,G) route entry, the router
  1397.           lowers  the  entry's    Oif-timer  for    I  to  its  Oif-
  1398.           Deletion-Delay, allowing for other downstream     routers
  1399.           on  a    multi-access LAN to override the prune.    However,
  1400.           on point-to-point  links,  the  oif-timer  is     expired
  1401.           immediately.
  1402.  
  1403.  
  1404.          2      If the router    has a current (*,G), or    (*,*,RP),  route
  1405.           entry,  and  if the existing (Sp,G) entry has    its RPT-
  1406.           bit flag set to 1, then this    (Sp,G)RPT-bit  entry  is
  1407.           maintained   (not   deleted)     even  if  its    outgoing
  1408.           interface list is null.
  1409.  
  1410.  
  1411.  
  1412.  
  1413.     2    For each address, Sp, in the prune    list  whose  RPT-bit  is
  1414.          set and whose WC-bit cleared:
  1415.  
  1416.  
  1417.          1      If there is an existing (Sp,G) route entry, the router
  1418.           lowers  the  entry's    Oif-timer  for    I  to  its  Oif-
  1419.           Deletion-Delay, allowing for other downstream     routers
  1420.           on  a    multi-access LAN to override the prune.    However,
  1421.           on point-to-point  links,  the  oif-timer  is     expired
  1422.           immediately.
  1423.  
  1424.  
  1425.          2      If the router    has a current (*,G), or    (*,*,RP),  route
  1426.           entry,  and  if the existing (Sp,G) entry has    its RPT-
  1427.           bit flag set to 1, then this    (Sp,G)RPT-bit  entry  is
  1428.           not deleted, and the Entry-timer is restarted, even if
  1429.           its outgoing interface list is null.
  1430.  
  1431.  
  1432.          3      If (*,G), or corresponding (*,*,RP), state exists, but
  1433.           there     is  no     (Sp,G)    entry, an (Sp,G)RPT-bit    entry is
  1434.           created . The    outgoing interface list    is  copied  from
  1435.           the  (*,G), or (*,*,RP), entry, with the interface, I,
  1436.           on which the prune was received, is  deleted.     Packets
  1437.           from    the  pruned  source, Sp, match on this state and
  1438.           are not forwarded toward the pruned receivers.
  1439.  
  1440.  
  1441.  
  1442.  
  1443. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 24]
  1444.  
  1445.  
  1446.  
  1447.  
  1448.  
  1449. Internet Draft          PIM-SM Specification              March 1997
  1450.  
  1451.  
  1452.          4      If there exists a (Sp,G) entry, with    or  without  the
  1453.           RPT-bit  set,     the oif-timer for I is    expired, and the
  1454.           Entry-timer is restarted.
  1455.  
  1456.  
  1457.  
  1458.  
  1459.     3    For each address, Sp, in the prune    list whose  RPT-bit  and
  1460.          WC-bit are    both set:
  1461.  
  1462.  
  1463.  
  1464.          1      If there is an existing (*,G)    entry, with Sp as the RP
  1465.           for  G,  the router lowers the entry's Oif-timer for I
  1466.           to  its   Oif-Deletion-Delay,      allowing   for   other
  1467.           downstream  routers  on a multi-access LAN to    override
  1468.           the prune. However, on point-to-point    links, the  oif-
  1469.           timer    is expired immediately.
  1470.  
  1471.  
  1472.          2      If the corresponding (*,*,RP)    state exists, but  there
  1473.           is  no  (*,G)     entry,     a  (*,G)  entry is created. The
  1474.           outgoing interface list is copied from (*,*,RP) entry,
  1475.           with     the  interface,  I,  on  which     the  prune  was
  1476.           received, deleted.
  1477.  
  1478.  
  1479.          For any new (S,G),    (*,G) or (*,*,RP) entry     created  by  an
  1480.          incoming Join/Prune message, the SPT-bit is cleared (and if
  1481.          a Join/Prune-Suppression timer is used, it    is left    off.)
  1482.  
  1483.  
  1484.  
  1485.     If the entry has a Join/Prune-Suppression timer    associated  with
  1486.     it,  and if the    received Join/Prune does not indicate the router
  1487.     as its target, then the    receiving router examines the  join  and
  1488.     prune  lists  to  see  if any addresses    in the list `completely-
  1489.     match' existing    (S,G), (*,G), or (*,*,RP) state     for  which  the
  1490.     receiving  router  currently  schedules     Join/Prune messages. An
  1491.     element    on the join or prune list `completely-matches'    a  route
  1492.     entry  only if both the    addresses and RPT-bit flag are the same.
  1493.     If  the     incoming  Join/Prune  message    completely  matches   an
  1494.     existing  (S,G),  (*,G),  or  (*,*,RP)    entry and the Join/Prune
  1495.     arrived    on the iif for that entry, then    the router  compares
  1496.     the  Holdtime  included     in  the  Join/Prune message, to its own
  1497.     [Join/Prune-Holdtime].    If  its     own  [Join/Prune-Holdtime]   is
  1498.     lower,     the  Join/Prune-Suppression-timer  is    started     at  the
  1499.     [Join/Prune-Suppression-Timeout]. If  the  [Join/Prune-Holdtime]
  1500.  
  1501.  
  1502.  
  1503. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 25]
  1504.  
  1505.  
  1506.  
  1507.  
  1508.  
  1509. Internet Draft          PIM-SM Specification              March 1997
  1510.  
  1511.  
  1512.     is equal, the tie is resolved in favor of the Join/Prune Message
  1513.     originator that    has the    higher network layer address.  When  the
  1514.     Join/Prune  timer  expires,  the  router  triggers  a Join/Prune
  1515.     message    for the    corresponding entry(ies).
  1516.  
  1517.      3.3 Register and Register-Stop
  1518.  
  1519.     When a source first starts sending to a    group  its  packets  are
  1520.     encapsulated  in  Register  messages  and sent to the RP. If the
  1521.     data rate warrants source-specific paths, the RP sets up  source
  1522.     specific  state     and  starts  sending  (S,G) Join/Prune    messages
  1523.     toward the source, with    S in the join list.
  1524.  
  1525.      3.3.1 Sending Registers and Receiving Register-Stops
  1526.  
  1527.     Register messages are sent as follows:
  1528.  
  1529.  
  1530.  
  1531.     1    When a DR receives     a  packet  from  a  directly  connected
  1532.          source, S,    on the subnet containing the address S,
  1533.  
  1534.  
  1535.          1      If there is no  corresponding     (S,G)    entry,    and  the
  1536.           router  has  RP-Set information, and the DR is not the
  1537.           RP for G, the    DR  creates  an     (S,G)    entry  with  the
  1538.           Register-Suppression-timer   turned  off  and     the  RP
  1539.           address set according    to the hash function mapping for
  1540.           the  corresponding  group. The oif list is copied from
  1541.           existing (*,G) or (*,*,RP) entries, if they exist. The
  1542.           iif of the (S,G) entry is always excluded from the oif
  1543.           list.    If there exists    a (*,G)    or (*,*,RP)  entry,  the
  1544.           DR sends a Join/Prune    message    towards    the RP with S in
  1545.           the prune list and the RPT-bit set.
  1546.  
  1547.  
  1548.          2      If there is a    (S,G) entry in existence, the DR  simply
  1549.           restarts the corresponding Entry-timer.
  1550.  
  1551.          When a PMBR (e.g.,    a router that connects the PIM-SM region
  1552.          to     a dense mode region running DVMRP or PIM-DM) receives a
  1553.          packet from a source in the dense mode region,  the  router
  1554.          treats  the  packet as if it were from a directly connected
  1555.          source. A separate    document will describe    the  details  of
  1556.          interoperability.
  1557.  
  1558.  
  1559.  
  1560.  
  1561.  
  1562.  
  1563. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 26]
  1564.  
  1565.  
  1566.  
  1567.  
  1568.  
  1569. Internet Draft          PIM-SM Specification              March 1997
  1570.  
  1571.  
  1572.     2    If    the new    or previously-existing (S,G)  entry's  Register-
  1573.          Suppression-timer    is  not     running,  the    data  packet  is
  1574.          encapsulated in a Register    message    and unicast  to     the  RP
  1575.          for that group. The data packet is    also forwarded according
  1576.          to    (S,G) state in the DR if the oif list is not null; since
  1577.          a    receiver  may  join  the  SP-tree  while the DR    is still
  1578.          registering to the    RP.
  1579.  
  1580.  
  1581.     3    If    the (S,G) entry's Register-Suppression-timer is    running,
  1582.          the  data    packet    is not sent in a Register message, it is
  1583.          just forwarded according to the (S,G) oif list.
  1584.  
  1585.  
  1586.  
  1587.     When the DR receives a Register-Stop message,  it  restarts  the
  1588.     Register-Suppression-timer in the corresponding    (S,G) entry(ies)
  1589.     at [Register-Suppression-Timeout] seconds. If there is    data  to
  1590.     be  registered,     the  DR  may  send  a null Register (a    Register
  1591.     message    with a zero-length data    portion    in the inner packet)  to
  1592.     the  RP,  [Probe-Time]    seconds    before the Register-Suppression-
  1593.     timer expires, to avoid    sending    occasional bursts of traffic  to
  1594.     an RP unnecessarily.
  1595.  
  1596.      3.3.2 Receiving Register Messages and Sending Register-Stops
  1597.  
  1598.     When a router (i.e., the RP) receives a     Register  message,  the
  1599.     router does the    following:
  1600.  
  1601.  
  1602.  
  1603.     1    Decapsulates  the     data    packet,      and    checks     for   a
  1604.          corresponding (S,G) entry.
  1605.  
  1606.  
  1607.  
  1608.          1      If a (S,G) entry with    cleared    (0) SPT    bit exists,  and
  1609.           the    received   Register  does  not    have  the  Null-
  1610.           Register-Bit set to 1, the packet  is     forwarded;  and
  1611.           the  SPT bit is left cleared (0). If the SPT bit is 1,
  1612.           the packet is    dropped, and Register-Stop messages  are
  1613.           triggered.  Register-Stops  should be    rate-limited (in
  1614.           an implementation-specific manner)  so  that    no  more
  1615.           than a few are sent per round    trip time. This    prevents
  1616.           a high datarate stream of packets  from  triggering  a
  1617.           large     number     of  Register-Stop  messages between the
  1618.           time that the    first packet is    received  and  the  time
  1619.           when the source receives the first Register-Stop.
  1620.  
  1621.  
  1622.  
  1623. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 27]
  1624.  
  1625.  
  1626.  
  1627.  
  1628.  
  1629. Internet Draft          PIM-SM Specification              March 1997
  1630.  
  1631.  
  1632.          2      If there is no (S,G)    entry,    but  there  is    a  (*,G)
  1633.           entry,  and  the  received  Register does not    have the
  1634.           Null-Register-Bit set    to 1, the  packet  is  forwarded
  1635.           according to the (*,G) entry.
  1636.  
  1637.  
  1638.          3      If there is a    (*,*,RP) entry but no (*,G)  entry,  and
  1639.           the    Register   received  does  not    have  the  Null-
  1640.           Register-Bit set to 1,  a  (*,G)  or    (S,G)  entry  is
  1641.           created  and    the oif    list is    copied from the    (*,*,RP)
  1642.           entry    to  the     new  entry.  The  packet  is  forwarded
  1643.           according to the created entry.
  1644.  
  1645.  
  1646.          4      If there is no G or (*,*,RP) entry corresponding to G,
  1647.           the    packet     is  dropped,  and  a  Register-Stop  is
  1648.           triggered.
  1649.  
  1650.  
  1651.          5      A ``Border bit'' bit is added    to the Register    message,
  1652.           to  facilitate  interoperability mechanisms. PMBRs set
  1653.           this bit when    registering for     external  sources  (see
  1654.           Section   2.7).  If  the  ``Border bit'' is set in the
  1655.           Register, the    RP does    the following:
  1656.  
  1657.  
  1658.  
  1659.           1    If there    is no matching (S,G)  state,  but  there
  1660.                exists  (*,G) or    (*,*,RP) entry,    the RP creates a
  1661.                (S,G) entry, with  a  `PMBR'  field.  This  field
  1662.                holds  the source of the    Register (i.e. the outer
  1663.                network layer address of     the  register    packet).
  1664.                The  RP    triggers a (S,G) join towards the source
  1665.                of the data packet, and clears the  SPT    bit  for
  1666.                the  (S,G) entry. If the    received Register is not
  1667.                a  `null     Register'  the     packet      is   forwarded
  1668.                according to the    created    state. Else,
  1669.  
  1670.  
  1671.           2    If the `PMBR' field for the  corresponding  (S,G)
  1672.                entry  matches the source of the    Register packet,
  1673.                and  the     received  Register  is     not   a   `null
  1674.                Register',  the    decapsulated packet is forwarded
  1675.                to the oif list of that entry. Else,
  1676.  
  1677.  
  1678.  
  1679.           3    If the `PMBR' field for the  corresponding  (S,G)
  1680.  
  1681.  
  1682.  
  1683. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 28]
  1684.  
  1685.  
  1686.  
  1687.  
  1688.  
  1689. Internet Draft          PIM-SM Specification              March 1997
  1690.  
  1691.  
  1692.                entry  matches the source of the    Register packet,
  1693.                the decapsulated    packet is forwarded to    the  oif
  1694.                list of that entry, else
  1695.  
  1696.  
  1697.           4    The packet is dropped,  and  a  Register-stop  is
  1698.                triggered towards the source of the Register.
  1699.  
  1700.  
  1701.  
  1702.  
  1703.          The (S,G) Entry-timer is restarted     by  Registers    arriving
  1704.          from that source to that group.
  1705.  
  1706.  
  1707.     2    If    the matching (S,G) or (*,G) state contains  a  null  oif
  1708.          list, the RP unicasts a Register-Stop message to the source
  1709.          of    the Register message; in the latter  case,  the     source-
  1710.          address  field, within the    Register-Stop message, is set to
  1711.          the wildcard value    (all 0's). This    message    is not processed
  1712.          by      intermediate     routers,   hence   no    (S,G)  state  is
  1713.          constructed between the RP    and the    source.
  1714.  
  1715.  
  1716.     3    If    the Register message arrival rate warrants it and  there
  1717.          is     no  existing  (S,G) entry, the    RP sets    up a (S,G) route
  1718.          entry with    the outgoing interface list, excluding iif(S,G),
  1719.          copied  from the (*,G) outgoing interface list, its SPT-bit
  1720.          is    initialized to 0. If a (*,G) entry does    not  exist,  but
  1721.          there  exists a (*,*,RP) entry with the RP    corresponding to
  1722.          G , the oif list for (S,G)    is copied  -excluding  the  iif-
  1723.          from that (*,*,RP)    entry.
  1724.  
  1725.          A timer (Entry-timer) is set for the (S,G)    entry  and  this
  1726.          timer  is    restarted  by receipt of data packets for (S,G).
  1727.          The (S,G) entry causes the    RP to send a Join/Prune     message
  1728.          for  the indicated    group towards the source of the    register
  1729.          message.
  1730.  
  1731.          If    the (S,G) oif list  becomes  null,  Join/Prune    messages
  1732.          will not be sent towards the source, S.
  1733.  
  1734.  
  1735.  
  1736.      3.4 Multicast Data    Packet Forwarding
  1737.  
  1738.     Processing a multicast data packet involves the    following steps:
  1739.  
  1740.  
  1741.  
  1742.  
  1743. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 29]
  1744.  
  1745.  
  1746.  
  1747.  
  1748.  
  1749. Internet Draft          PIM-SM Specification              March 1997
  1750.  
  1751.  
  1752.     1    Lookup route state    based on a longest match of  the  source
  1753.          address,  and  an exact match of the destination address in
  1754.          the data packet. If neither S, nor    G, find    a longest  match
  1755.          entry,  and  the  RP  for    the  packet's  destination group
  1756.          address  has  a  corresponding  (*,*,RP)  entry,  then  the
  1757.          longest  match  does  not    require     an  exact  match on the
  1758.          destination group address.    In summary, the    longest    match is
  1759.          performed    in the following order:    (1) (S,G), (2) (*,G). If
  1760.          neither is    matched, then a    lookup is performed on    (*,*,RP)
  1761.          entries.
  1762.  
  1763.  
  1764.  
  1765.     2    If    the  packet  arrived  on  the  interface  found     in  the
  1766.          matching-entry's iif field, and the oif list is not
  1767.          null:
  1768.  
  1769.  
  1770.          1      Forward the packet to    the oif    list for that entry,
  1771.           excluding  the  subnet  containing  S, and restart the
  1772.           Entry-timer  if   the      matching   entry   is      (S,G).
  1773.           Optionally,  the (S,G) Entry-timer may be restarted by
  1774.           periodic checking of the matching packet count.
  1775.  
  1776.  
  1777.          2      If the entry is a (S,G) entry    with a cleared    SPT-bit,
  1778.           and  a  (*,G)    or associated (*,*,RP) also exists whose
  1779.           incoming interface is    different than that  for  (S,G),
  1780.           set  the  SPT-bit  for  the (S,G) entry and trigger an
  1781.           (S,G)    RPT-bit    prune towards the RP.
  1782.  
  1783.  
  1784.          3      If the source    of the packet  is  a  directly-connected
  1785.           host    and  the  router  is  the  DR  on  the receiving
  1786.           interface,   check   the    Register-Suppression-timer
  1787.           associated with the (S,G) entry. If it is not    running,
  1788.           then the router encapsulates    the  data  packet  in  a
  1789.           register message and sends it    to the RP.
  1790.  
  1791.  
  1792.          This covers the common case of a packet arriving on the RPF
  1793.          interface    to  the     source    or RP and being    forwarded to all
  1794.          joined branches. It also detects when packets arrive on the
  1795.          SP-tree, and triggers their pruning from the RP-tree. If it
  1796.          is     the  DR  for  the  source,  it      sends      data     packets
  1797.          encapsulated in Registers to the RPs.
  1798.  
  1799.  
  1800.  
  1801.  
  1802.  
  1803. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 30]
  1804.  
  1805.  
  1806.  
  1807.  
  1808.  
  1809. Internet Draft          PIM-SM Specification              March 1997
  1810.  
  1811.  
  1812.     3    If    the packet matches to an entry but did not arrive on the
  1813.          interface    found  in  the    entry's    iif field, check the
  1814.          SPT-bit of    the entry. If  the  SPT-bit  is     set,  drop  the
  1815.          packet.  If  the SPT-bit is cleared, then lookup the (*,G),
  1816.          or    (*,*,RP), entry    for G. If the packet arrived  on  the
  1817.          iif  found     in  (*,G),  or     the  corresponding  (*,*,RP),
  1818.          forward the packet    to the    oif  list  of  the  matching
  1819.          entry. This covers    the case when a    data packet matches on a
  1820.          (S,G)  entry  for    which  the  SP-tree  has  not  yet  been
  1821.          completely    established upstream.
  1822.  
  1823.  
  1824.     4    If    the packet does    not match any entry, but the  source  of
  1825.          the  data    packet    is a local, directly-connected host, and
  1826.          the router    is the DR on a multi-access LAN    and  has  RP-Set
  1827.          information, the DR uses the hash function    to determine the
  1828.          RP    associated with    the destination    group, G. The DR creates
  1829.          a    (S,G)  entry,  with  the  Register-Suppression-timer not
  1830.          running, encapsulates the data packet in a    Register message
  1831.          and unicasts it to    the RP.
  1832.  
  1833.  
  1834.     5    If    the packet does    not match to any entry,    and it is not  a
  1835.          local host    or the router is not the DR, drop the packet.
  1836.  
  1837.  
  1838.  
  1839.      3.4.1 Data    triggered switch to shortest path tree (SP-tree)
  1840.  
  1841.     Different criteria can be applied to trigger switching over from
  1842.     the  RP-based  shared  tree  to     source-specific,  shortest path
  1843.     trees.
  1844.  
  1845.     One proposed example is     to  do     so  based  on    data  rate.  For
  1846.     example,  when    a  (*,G),  or  corresponding  (*,*,RP),    entry is
  1847.     created, a data    rate counter may be initiated  at  the    last-hop
  1848.     routers.  The  counter    is  incremented     with  every data packet
  1849.     received for directly connected    members    of an SM group,     if  the
  1850.     longest     match    is  (*,G) or (*,*,RP). If and when the data rate
  1851.     for the    group exceeds a    certain    configured threshold  (t1),  the
  1852.     router    initiates  `source-specific'  data rate    counters for the
  1853.     following data packets.    Then, each  counter  for  a  source,  is
  1854.     incremented  when  packets  matching  on (*,G),    or (*,*,RP), are
  1855.     received from that source. If the data rate from the  particular
  1856.     source    exceeds     a  configured    threshold (t2),    a (S,G)    entry is
  1857.     created    and a Join/Prune message is sent towards the source.  If
  1858.     the RPF    interface for (S,G) is
  1859.      not the same as that for (*,G)    -or (*,*,RP), then  the     SPT-bit
  1860.  
  1861.  
  1862.  
  1863. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 31]
  1864.  
  1865.  
  1866.  
  1867.  
  1868.  
  1869. Internet Draft          PIM-SM Specification              March 1997
  1870.  
  1871.  
  1872.     is cleared in the (S,G)    entry.
  1873.  
  1874.     Other configured rules may  be    enforced  to  cause  or     prevent
  1875.     establishment of (S,G) state.
  1876.  
  1877.  
  1878.  
  1879.  
  1880.  
  1881.      3.5 Assert
  1882.  
  1883.     Asserts    are used  to  resolve  which  of  the  parallel     routers
  1884.     connected  to  a  multi-access LAN is responsible for forwarding
  1885.     packets    onto the LAN.
  1886.  
  1887.      3.5.1 Sending Asserts
  1888.  
  1889.     The following Assert rules are provided    when a multicast  packet
  1890.     is  received  on  an outgoing multi-access interface ``I'' of an
  1891.     existing active    (S,G), (*,G) or    (*,*,RP) entry:
  1892.  
  1893.  
  1894.  
  1895.     1    Do    unicast    routing    table lookup on    source address from data
  1896.          packet,  and  send     assert     on  interface    ``I'' for source
  1897.          address  in  data    packet;     include  metric  preference  of
  1898.          routing protocol and metric from routing table lookup.
  1899.  
  1900.  
  1901.     2    If    route is not found, use    metric preference of  0x7fffffff
  1902.          and metric    0xffffffff.
  1903.  
  1904.     When an    assert is sent for a (*,G) entry, the first bit     in  the
  1905.     metric preference (the RPT-bit)    is set to 1, indicating    the data
  1906.     packet is routed down the RP-tree.
  1907.  
  1908.     Asserts    should be  rate-limited     in  an     implementation-specific
  1909.     manner.
  1910.  
  1911.      3.5.2 Receiving Asserts
  1912.  
  1913.     When an    Assert is received the router performs a  longest  match
  1914.     on  the     source     and  group  address in    the Assert message, only
  1915.     active entries -- that    have  packet  forwarding  state     --  are
  1916.     matched.   The    router    checks    the  first  bit     of  the  metric
  1917.     preference (RPT-bit).
  1918.  
  1919.  
  1920.  
  1921.  
  1922.  
  1923. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 32]
  1924.  
  1925.  
  1926.  
  1927.  
  1928.  
  1929. Internet Draft          PIM-SM Specification              March 1997
  1930.  
  1931.  
  1932.     1    If    the RPT-bit is set, the    router first  does  a  match  on
  1933.          (*,G), or (*,*,RP), entries; if no    matching entry is found,
  1934.          it    ignores    the Assert.
  1935.  
  1936.  
  1937.     2    If    the RPT-bit is not set in the Assert, the  router  first
  1938.          does  a  match  on     (S,G)    entries; if no matching    entry is
  1939.          found, the    router matches (*,G) or    (*,*,RP) entries.
  1940.  
  1941.  
  1942.     Receiving Asserts on an    entry's    outgoing interface:
  1943.  
  1944.  
  1945.     If  the     interface  that received the Assert message is    in the
  1946.     oif list of the    matched    entry, then this Assert     is  processed
  1947.     by this    router as follows:
  1948.  
  1949.  
  1950.     1    If    the Assert's RPT-bit is    set and    the  matching  entry  is
  1951.          (*,*,RP), the router creates a (*,G) entry. If the    Assert's
  1952.          RPT-bit is    cleared    and the     matching  entry  is  (*,G),  or
  1953.          (*,*,RP),     the   router    creates     a  (S,G)RPT-bit  entry.
  1954.          Otherwise,    no new entry  is  created  in  response     to  the
  1955.          Assert.
  1956.  
  1957.  
  1958.     2    The router    then compares the metric values    received in  the
  1959.          Assert  with  the metric values associated    with the matched
  1960.          entry. The    RPT-bit    and metric preference  (in  that  order)
  1961.          are  treated  as  the  high-order    part of    an Assert metric
  1962.          comparison. If the    value in the Assert  is     less  than  the
  1963.          router's  value  (with ties broken    by the IP address, where
  1964.          higher network layer address wins),  delete  the  interface
  1965.          from  the    entry.    When  the deletion occurs for a    (*,G) or
  1966.          (*,*,RP) entry , the interface is    also  deleted  from  any
  1967.          associated    (S,G)RPT-bit or    (*,G) entries, respectively. The
  1968.          Entry-timer for the affected entries is restarted.
  1969.  
  1970.  
  1971.     3    If    the router has won the election     the  router  keeps  the
  1972.          interface    in  its     outgoing interface list. It acts as the
  1973.          forwarder for the LAN.
  1974.  
  1975.  
  1976.     The winning router sends an Assert message  containing    its  own
  1977.     metric to that outgoing    interface. This    will cause other routers
  1978.     on the LAN to prune that interface from    their route entries. The
  1979.     winning    router sets the    RPT-bit    in the Assert message if a (*,G)
  1980.  
  1981.  
  1982.  
  1983. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 33]
  1984.  
  1985.  
  1986.  
  1987.  
  1988.  
  1989. Internet Draft          PIM-SM Specification              March 1997
  1990.  
  1991.  
  1992.     or (S,G)RPT-bit    entry was matched.
  1993.  
  1994.     Receiving Asserts on an    entry's    incoming interface
  1995.  
  1996.     If  the     Assert    arrived    on the incoming    interface of an    existing
  1997.     (S,G), (*,G), or (*,*,RP) entry,  the  Assert  is  processed  as
  1998.     follows.  If  the  Assert  message  does  not  match  the entry,
  1999.     exactly, it is ignored;    i.e, longest-match is not used    in  this
  2000.     case. If the Assert message does match exactly,    then:
  2001.  
  2002.  
  2003.     1    Downstream    routers    will select the    upstream router    with the
  2004.          smallest    metric     preference  and  metric  as  their  RPF
  2005.          neighbor. If two metrics are the same, the    highest     network
  2006.          layer address is chosen to    break the tie. This is important
  2007.          so    that downstream    routers    send subsequent    Joins/Prunes (in
  2008.          SM)  to  the correct neighbor. An Assert-timer is initiated
  2009.          when changing the RPF neighbor to the Assert  winner.  When
  2010.          the  timer     expires,  the    router    resets    its RPF    neighbor
  2011.          according to its unicast routing tables to    capture     network
  2012.          dynamics and router failures.
  2013.  
  2014.  
  2015.     2    If    the downstream routers have downstream members,     and  if
  2016.          the   Assert   caused  the     RPF  neighbor    to  change,  the
  2017.          downstream    routers    must trigger  a     Join/Prune  message  to
  2018.          inform the    upstream router    that packets are to be forwarded
  2019.          on    the multi-access network.
  2020.  
  2021.  
  2022.  
  2023.      3.6 Candidate-RP-Advertisements and Bootstrap messages
  2024.  
  2025.     Candidate-RP-Advertisements   (C-RP-Advs)   are      periodic   PIM
  2026.     messages unicast to the    BSR by those routers that are configured
  2027.     as Candidate-RPs (C-RPs).
  2028.  
  2029.     Bootstrap messages are periodic    PIM messages originated     by  the
  2030.     Bootstrap router (BSR) within a    domain,    and forwarded hop-by-hop
  2031.     to distribute the current RP-set to all    routers    in that    domain.
  2032.  
  2033.  
  2034.     The Bootstrap messages also support a simple mechanism by  which
  2035.     the  Candidate    BSR  (C-BSR)  with  the    highest    BSR-priority and
  2036.     address    (referred to as    the preferred BSR) is elected as the BSR
  2037.     for  the  domain.  We recommend    that each router configured as a
  2038.     C-RP also be configured    as a C-BSR. Sections  3.6.2  and   3.6.3
  2039.     describe  the  combined     function  of  Bootstrap messages as the
  2040.  
  2041.  
  2042.  
  2043. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 34]
  2044.  
  2045.  
  2046.  
  2047.  
  2048.  
  2049. Internet Draft          PIM-SM Specification              March 1997
  2050.  
  2051.  
  2052.     vehicle    for BSR    election and RP-Set distribution.
  2053.  
  2054.     A Finite State Machine description of the BSR election    and  RP-
  2055.     Set distribution mechanisms is included    in Appendix II.
  2056.  
  2057.      3.6.1 Sending Candidate-RP-Advertisements
  2058.  
  2059.     C-RPs periodically unicast C-RP-Advs to    the BSR    for that domain.
  2060.     The  interval  for  sending  these  messages is    subject    to local
  2061.     configuration at the C-RP.
  2062.  
  2063.     Candidate-RP-Advertisements carry group    address    and  group  mask
  2064.     fields.     This  enables    the  advertising  router  to  limit  the
  2065.     advertisement to certain  prefixes  or    scopes    of  groups.  The
  2066.     advertising  router  may  enforce  this     scope    acceptance  when
  2067.     receiving Registers or Join/Prune messages.  C-RPs  should  send
  2068.     C-RP-Adv messages with the `Priority' field set    to `0'.
  2069.  
  2070.  
  2071.  
  2072.      3.6.2 Receiving C-RP-Advs and Originating Bootstrap
  2073.  
  2074.     Upon receiving a C-RP-Adv, a router does the following:
  2075.  
  2076.  
  2077.     1    If    the router is  not  the     elected  BSR,    it  ignores  the
  2078.          message, else
  2079.  
  2080.  
  2081.     2    The BSR adds the RP address to its    local pool of  candidate
  2082.          RPs,  according  to  the associated group prefix(es) in the
  2083.          C-RP-Adv message. The Holdtime in the C-RP-Adv  message  is
  2084.          also stored with the corresponding    RP, to be included later
  2085.          in    the Bootstrap message. The BSR may apply a local  policy
  2086.          to     limit    the  number  of     Candidate  RPs     included in the
  2087.          Bootstrap    message.  The  BSR  may     override   the      prefix
  2088.          indicated    in a C-RP-Adv unless the `Priority' field is not
  2089.          zero.
  2090.  
  2091.  
  2092.     The BSR    keeps an RP-timer per RP in its    local  RP-set.    The  RP-
  2093.     timer  is initialized to the Holdtime in the RP's C-RP-Adv. When
  2094.     the timer expires, the corresponding RP    is removed from    the  RP-
  2095.     set.  The  RP-timer  is     restarted  by    the  C-RP-Advs    from the
  2096.     corresponding RP.
  2097.  
  2098.     The BSR    also  uses  its     Bootstrap-timer  to  periodically  send
  2099.     Bootstrap  messages.  In  particular,  when  the Bootstrap-timer
  2100.  
  2101.  
  2102.  
  2103. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 35]
  2104.  
  2105.  
  2106.  
  2107.  
  2108.  
  2109. Internet Draft          PIM-SM Specification              March 1997
  2110.  
  2111.  
  2112.     expires, the BSR originates a Bootstrap    message    on each     of  its
  2113.     PIM  interfaces. To reduce the bootstrap message overhead during
  2114.     partition healing, the BSR  should  set     a  random  time  (as  a
  2115.     function  of the priority and address) after which the Bootstrap
  2116.     message    is originated  only  if     no  other  preferred  Bootstrap
  2117.     message    is received. For details see appendix
  2118.      6.2. The message is sent with a  TTL  of  1  to  the  `ALL-PIM-
  2119.     ROUTERS'  group.  In  steady state, the    BSR originates Bootstrap
  2120.     messages  periodically.     At  startup,  the  Bootstrap-timer   is
  2121.     initialized  to    [Bootstrap-Timeout], causing the first Bootstrap
  2122.     message    to be originated only when and if the timer expires. For
  2123.     timer  details,     see  Section    3.6.3. A DR unicasts a Bootstrap
  2124.     message    to each    new PIM    neighbor, i.e.,    after  the  DR    receives
  2125.     the  neighbor's     Hello    message     (it  does  so    even  if the new
  2126.     neighbor becomes the DR).
  2127.  
  2128.     The  Bootstrap    message     is  subdivided     into  sets  of      group-
  2129.     prefix,RP-Count,RP-addresses.     For    each   RP-address,   the
  2130.     corresponding Holdtime is included in the ``RP-Holdtime"  field.
  2131.     The   format   of   the      Bootstrap   message  allows  `semantic
  2132.     fragmentation',    if the length of the original Bootstrap     message
  2133.     exceeds    the packet maximum boundaries (see Section  4).    However,
  2134.     we recommend against configuring a large number     of  routers  as
  2135.     C-RPs, to reduce the semantic fragmentation required.
  2136.  
  2137.      3.6.3 Receiving and Forwarding Bootstrap
  2138.  
  2139.     Each router keeps a Bootstrap-timer, initialized to  [Bootstrap-
  2140.     Timeout] at startup.
  2141.  
  2142.     When a router  receives     Bootstrap  message  sent  to  `ALL-PIM-
  2143.     ROUTERS' group,    it performs the    following:
  2144.  
  2145.  
  2146.     1    If    the message was    not sent by the    RPF neighbor towards the
  2147.          BSR address included, the message is dropped. Else
  2148.  
  2149.  
  2150.     2    If    the included BSR is  not preferred over, and  not  equal
  2151.          to, the currently active BSR:
  2152.  
  2153.  
  2154.          1      If the Bootstrap-timer has  not yet expired, or if the
  2155.           receiving  router  is     a  C-BSR,  then  the  Bootstrap
  2156.           message is dropped. Else
  2157.  
  2158.          2      If the Bootstrap-timer  has expired and the  receiving
  2159.           router is not    a C-BSR, the receiving router stores the
  2160.  
  2161.  
  2162.  
  2163. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 36]
  2164.  
  2165.  
  2166.  
  2167.  
  2168.  
  2169. Internet Draft          PIM-SM Specification              March 1997
  2170.  
  2171.  
  2172.           RP-Set and BSR  address  and    priority  found     in  the
  2173.           message,  and     restarts  the    timer  by  setting it to
  2174.           [Bootstrap-Timeout]. The  Bootstrap  message    is  then
  2175.           forwarded  out  all  PIM interfaces, excluding the one
  2176.           over which the message arrived,  to  `ALL-PIM-ROUTERS'
  2177.           group, with a    TTL of 1.
  2178.  
  2179.  
  2180.  
  2181.     3    If    the Bootstrap message includes a BSR  address  that   is
  2182.          preferred    over, or equal to, the currently active    BSR, the
  2183.          router restarts its Bootstrap-timer at  [Bootstrap-Timeout]
  2184.          seconds. and stores the BSR address and RP-Set information.
  2185.  
  2186.          The  Bootstrap  message  is  then    forwarded  out    all  PIM
  2187.          interfaces,  excluding  the  one  over  which  the     message
  2188.          arrived, to `ALL-PIM-ROUTERS' group, with a TTL of    1.
  2189.  
  2190.  
  2191.     4    If    the receiving router has no current RP    set  information
  2192.          and  the  Bootstrap  was  unicast    to  it    from  a    directly
  2193.          connected neighbor, the router stores  the     information  as
  2194.          its  new  RP-set.    This covers the    startup    condition when a
  2195.          newly booted router obtains the RP-Set and    BSR address from
  2196.          its DR.
  2197.  
  2198.  
  2199.     When a router receives a new RP-Set, it    checks if  each     of  the
  2200.     RPs  referred to by existing state (i.e., by (*,G), (*,*,RP), or
  2201.     (S,G)RPT-bit entries) is in the    new RP-Set. If an RP is     not  in
  2202.     the  new  RP-set, that RP is considered    unreachable and    the hash
  2203.     algorithm (see    below)    is  re-performed  for  each  group  with
  2204.     locally     active     state    that  previously hashed    to that    RP. This
  2205.     will cause those groups    to be distributed  among  the  remaining
  2206.     RPs. When the new RP-Set contains a new    RP, the    value of the new
  2207.     RP is calculated for each group    covered    by  that  C-RP's  Group-
  2208.     prefix.     Any  group for    which the new RP's value is greater than
  2209.     the previously active RP's value is switched over to the new RP.
  2210.  
  2211.  
  2212.  
  2213.  
  2214.      3.7 Hash Function
  2215.  
  2216.     The hash function is used by all routers within    a domain, to map
  2217.     a  group  to  one of the C-RPs from the    RP-Set.    For a particular
  2218.     group, G, the hash function uses only those C-RPs  whose  Group-
  2219.     prefix covers G. The algorithm takes as    input the group    address,
  2220.  
  2221.  
  2222.  
  2223. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 37]
  2224.  
  2225.  
  2226.  
  2227.  
  2228.  
  2229. Internet Draft          PIM-SM Specification              March 1997
  2230.  
  2231.  
  2232.     and the    addresses of the Candidate RPs,    and gives as output  one
  2233.     RP address to be used.
  2234.  
  2235.     The protocol requires that all    routers     hash  to  the    same  RP
  2236.     within    a  domain  (except  for     transients). The following hash
  2237.     function must be used in each router:
  2238.  
  2239.  
  2240.  
  2241.  
  2242.     1     For RP addresses in the RP-Set, whose Group-prefix  covers
  2243.          G,     select     the  RPs with the highest priority (i.e. lowest
  2244.          `Priority'    value),    and compute a value:
  2245.  
  2246.        Value(G,M,C(i))=
  2247.        (1103515245 * ((1103515245 *    (G&M)+12345) XOR C(i)) + 12345)    mod 2^31
  2248.  
  2249.          where C_i is the  RP  address  and    M  is  a  hash-mask
  2250.          included  in  Bootstrap  messages.     The  hash-mask    allows a
  2251.          small number of consecutive groups    (e.g., 4) to always hash
  2252.          to     the  same RP. For instance, hierarchically-encoded data
  2253.          can be sent on consecutive    group addresses    to get the  same
  2254.          delay and fate-sharing characteristics.
  2255.  
  2256.          For address families other    than IPv4, a 32-bit digest to be
  2257.          used  as  C_i  must  first     be derived from the actual RP
  2258.          address. Such a digest method  must  be  used  consistently
  2259.          throughout    the PIM    domain.    For IPv6 addresses, we recommend
  2260.          using the equivalent IPv4 address    for  an     IPv4-compatible
  2261.          address,  and  the     CRC-32     checksum  [7] of all other IPv6
  2262.          addresses.
  2263.  
  2264.     2    From  the    RPs  with  the    highest     priority  (i.e.  lowest
  2265.          `Priority'    value),    the candidate with the highest resulting
  2266.          value is then chosen as the RP  for  that    group,    and  its
  2267.          identity and hash value are stored    with the entry created.
  2268.  
  2269.          Ties between RPs having the same hash value  and  priority,
  2270.          are broken    in advantage of    the highest address.
  2271.  
  2272.  
  2273.  
  2274.  
  2275.     The hash function algorithm is invoked by a DR,     upon  reception
  2276.     of  a  packet,    or  IGMP membership indication,    for a group, for
  2277.     which the DR has no entry. It is invoked by any    router that  has
  2278.     (*,*,RP)  state     when a    packet is received for which there is no
  2279.     corresponding  (S,G)  or  (*,G)     entry.     Furthermore,  the  hash
  2280.  
  2281.  
  2282.  
  2283. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 38]
  2284.  
  2285.  
  2286.  
  2287.  
  2288.  
  2289. Internet Draft          PIM-SM Specification              March 1997
  2290.  
  2291.  
  2292.     function  is  invoked  by  all routers upon receiving a    (*,G) or
  2293.     (*,*,RP) Join/Prune message.
  2294.  
  2295.      3.8 Processing Timer Events
  2296.  
  2297.     In this    subsection, we    enumerate  all    timers    that  have  been
  2298.     discussed  or  implied.    Since some critical timer events are not
  2299.     associated with    the receipt or sending of messages, they are not
  2300.     fully covered by earlier subsections.
  2301.  
  2302.     Timers are implemented in an implementation-specific manner. For
  2303.     example, a timer may count up or down, or may simply expire at a
  2304.     specific time. Setting a timer to a value T means that    it  will
  2305.     expire after T seconds.
  2306.  
  2307.      3.8.1 Timers related to tree maintenance
  2308.  
  2309.     Each (S,G), (*,G), and (*,*,RP)    route entry has    multiple  timers
  2310.     associated  with  it:  one  for     each  interface in the    outgoing
  2311.     interface list,    one for    the multicast routing entry itself,  and
  2312.     one  optional Join/Prune-Suppression-Timer. Each (S,G) and (*,G)
  2313.     entry also has an Assert-timer and a Random-Delay-Join-Timer for
  2314.     use   with   Asserts.    In   addition,    DR's  have  a  Register-
  2315.     Suppression-timer for each (S,G) entry and every  router  has  a
  2316.     single    Join/Prune-timer. (A router may    optionally keep    separate
  2317.     Join/Prune-timers for different    interfaces or route  entries  if
  2318.     different Join/Prune periods are desired.)
  2319.  
  2320.  
  2321.  
  2322.     *    [Join/Prune-Timer]    This  timer  is     used  for  periodically
  2323.          sending    aggregate    Join/Prune      messages.   To   avoid
  2324.          synchronization among routers booting simultaneously, it is
  2325.          initially    set to a random    value between 1    and [Join/Prune-
  2326.          Period].  When  it     expires,  the    timer    is   immediately
  2327.          restarted    to  [Join/Prune-Period]. A Join/Prune message is
  2328.          then sent out each    interface.  This  timer     should     not  be
  2329.          restarted by other    events.
  2330.  
  2331.  
  2332.     *    [Join/Prune-Suppression-Timer (kept  per  route  entry)]  A
  2333.          route  entry's  (optional)    Join/Prune-Suppression-Timer may
  2334.          be     used  to  suppress  duplicate     joins     from    multiple
  2335.          downstream     routers on the    same LAN. When a Join message is
  2336.          received from a neighbor on the entry's incoming  interface
  2337.          in     which the included Holdtime is    higher than the    router's
  2338.          own  [Join/Prune-Holdtime]     (with    ties  broken  by  higher
  2339.          network  layer  address),    the timer is set to [Join/Prune-
  2340.  
  2341.  
  2342.  
  2343. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 39]
  2344.  
  2345.  
  2346.  
  2347.  
  2348.  
  2349. Internet Draft          PIM-SM Specification              March 1997
  2350.  
  2351.  
  2352.          Suppression-Timeout], with    some random jitter introduced to
  2353.          avoid  synchronization  of    triggered Join/Prune messages on
  2354.          expiration. (The random timeout value must     be  <    1.5  *
  2355.          [Join/Prune-Period]  to prevent losing data after 2 dropped
  2356.          Join/Prunes.)  The     timer    is  restarted    every    time   a
  2357.          subsequent     Join/Prune  message  (with  higher  Holdtime/IP
  2358.          address)  for  the     entry    is  received  on  its    incoming
  2359.          interface.     While the timer is running, Join/Prune    messages
  2360.          for the entry  are     not  sent.  This  timer  is  idle  (not
  2361.          running) for point-to-point links.
  2362.  
  2363.  
  2364.     *    [Oif-Timer    (kept per oif for each route entry)] A timer for
  2365.          each  oif    of  a  route entry is used to time out that oif.
  2366.          Because some of the outgoing interfaces in    an  (S,G)  entry
  2367.          are copied    from the (*,G) outgoing    interface list,    they may
  2368.          not have explicit (S,G) join  messages  from  some     of  the
  2369.          downstream     routers (i.e.,    where members are joining to the
  2370.          (*,G) tree    only). Thus, when an Oif-timer is restarted in a
  2371.          (*,G)  entry, the Oif-timer is restarted for that interface
  2372.          in    each existing (S,G) entry whose    oif list  contains  that
  2373.          interface.    The same rule applies to (*,G) and (S,G) entries
  2374.          when restarting an    Oif-timer on a (*,*,RP)    entry.
  2375.  
  2376.          The following table shows its usage when first  adding  the
  2377.          oif  to  the  entry's  oiflist, when it should be restarted
  2378.          (unless it    is  already  higher),  and  when  it  should  be
  2379.          decreased (unless it is already lower).
  2380.  
  2381. Set to             |   When            |  Applies  to
  2382. included Holdtime     | adding oif off Join/Prune    | (S,G)    (*,G) (*,*,RP)
  2383.  
  2384. Increased (only) to     | When                |  Applies to
  2385. included  Holdtime     | received Join/Prune        | (S,G)    (*,G) (*,*,RP)
  2386. (*,*,RP) oif-timer value | (*,*,RP) oif-timer restarted    | (S,G)    (*,G)
  2387. (*,G)  oif-timer  value     | (*,G) oif-timer restarted    | (S,G)
  2388.  
  2389.          When the timer expires, the oif is    removed    from the oiflist
  2390.          if     there    are no directly-connected members. When    deleted,
  2391.          the oif is    also removed in    any associated    (S,G)  or  (*,G)
  2392.          entries.
  2393.  
  2394.  
  2395.     *    [Entry-Timer (kept    per route entry)] A timer for each route
  2396.          entry  is    used to    time out that entry. The following table
  2397.  
  2398.  
  2399.  
  2400. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 40]
  2401.  
  2402.  
  2403.  
  2404.  
  2405.  
  2406. Internet Draft          PIM-SM Specification              March 1997
  2407.  
  2408.  
  2409.          summarizes    its usage when    first  adding  the  oif     to  the
  2410.          entry's oiflist, and when it should be restarted (unless it
  2411.          is    already    higher).
  2412.  
  2413. Set to              |     When             | Applies to
  2414. [Data- Timeout]          |    created    off data packet     | (S,G)
  2415. included Holdtime     |    created    off Join/Prune     | (S,G) (*,G) (*,*,RP)
  2416.  
  2417. Increased  (only)  to |     When             | Applies to
  2418. [Data-Timeout]          |    receiving  data     packets | (S,G)no RPT-bit
  2419. oif-timer  value      |    any oif-timer restarted     | (S,G)RPT-bit    (*,G) (*,*,RP)
  2420. [Assert-Timeout]      |    assert received         | (S,G)RPT-bit    (*,G) w/null oif
  2421.  
  2422.          When the timer expires, the route entry is    deleted; if  the
  2423.          entry   is     a  (*,G)  or  (*,*,RP)     entry,     all  associated
  2424.          (S,G)RPT-bit entries are also deleted.
  2425.  
  2426.  
  2427.     *    [Register-Suppression-Timer (kept per (S,G)  route     entry)]
  2428.          An     (S,G)    route entry's Register-Suppression-Timer is used
  2429.          to    suppress registers when    the RP is receiving data packets
  2430.          natively.    When  a     Register-Stop    message    for the    entry is
  2431.          received from the RP, the timer is    set to a random    value in
  2432.          the  range     0.5  *     [Register-Suppression-Timeout]    to 1.5 *
  2433.          [Register-Suppression-Timeout]. While the timer is    running,
  2434.          Registers    for  that  entry  will    be  suppressed.     If null
  2435.          registers are used, a null    register  is  sent  [Probe-Time]
  2436.          seconds before the    timer expires.
  2437.  
  2438.  
  2439.     *    [Assert-Timer  (per  (S,G)     or  (*,G)  route  entry)]   The
  2440.          Assert-Timer  for an (S,G)    or (*,G) route entry is    used for
  2441.          timing out    Asserts    received. When an Assert is received and
  2442.          the  RPF  neighbor     is  changed  to  the Assert winner, the
  2443.          Assert-Timer is set to [Assert-Timeout], and  is  restarted
  2444.          to     this value every time a subsequent Assert for the entry
  2445.          is    received on  its  incoming  interface.    When  the  timer
  2446.          expires,  the  router  resets its RPF neighbor according to
  2447.          its unicast routing table.
  2448.  
  2449.  
  2450.     *    [Random-Delay-Join-Timer (per (S,G) or (*,G) route     entry)]
  2451.          The  Random-Delay-Join-Timer  for    an  (S,G) or (*,G) route
  2452.          entry is used to prevent synchronization  among  downstream
  2453.          routers  on a LAN when their RPF neighbor changes.    When the
  2454.          RPF neighbor changes, this    timer is set to    a  random  value
  2455.  
  2456.  
  2457.  
  2458. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 41]
  2459.  
  2460.  
  2461.  
  2462.  
  2463.  
  2464. Internet Draft          PIM-SM Specification              March 1997
  2465.  
  2466.  
  2467.          between 0 and [Random-Delay-Join-Timeout] seconds.    When the
  2468.          timer expires, a triggered    Join/Prune message is  sent  for
  2469.          the   entry   unless  its    Join/Prune-Suppression-Timer  is
  2470.          running.
  2471.  
  2472.  
  2473.  
  2474.      3.8.2 Timers relating to neighbor discovery
  2475.  
  2476.  
  2477.  
  2478.     *    [Hello-Timer] This    timer is used to periodically send Hello
  2479.          messages.    To  avoid  synchronization among routers booting
  2480.          simultaneously, it    is  initially  set  to    a  random  value
  2481.          between 1 and [Hello-Period]. When    it expires, the    timer is
  2482.          immediately restarted to [Hello-Period]. A    Hello message is
  2483.          then  sent     out  each  interface.    This timer should not be
  2484.          restarted by other    events.
  2485.  
  2486.  
  2487.     *    [Neighbor-Timer (kept per neighbor)] A  Neighbor-Timer  for
  2488.          each  neighbor is used to time out    the neighbor state. When
  2489.          a Hello message is    received from a    new neighbor, the  timer
  2490.          is     initially  set     to  the  Holdtime included in the Hello
  2491.          message (which is equal to    the neighbor's value of     [Hello-
  2492.          Holdtime]).  Every    time a subsequent Hello    is received from
  2493.          that neighbor, the    timer is restarted to  the  Holdtime  in
  2494.          the  Hello.  When    the timer expires, the neighbor    state is
  2495.          removed.
  2496.  
  2497.  
  2498.      3.8.3 Timers relating to RP information
  2499.  
  2500.  
  2501.  
  2502.  
  2503.     *    [C-RP-Adv-Timer  (C-RP's  only)]  Routers     configured   as
  2504.          candidate RP's use    this timer to periodically send    C-RP-Adv
  2505.          messages. To avoid    synchronization     among    routers     booting
  2506.          simultaneously,  the  timer  is  initially     set to    a random
  2507.          value between 1 and [C-RP-Adv-Period]. When it expires, the
  2508.          timer  is    immediately restarted to [C-RP-Adv-Period]. A C-
  2509.          RP-Adv message is then sent to the    elected    BSR. This  timer
  2510.          should not    be restarted by    other events.
  2511.  
  2512.  
  2513.     *    [RP-Timer (BSR only, kept per RP in RP-Set)] The BSR uses a
  2514.          timer per RP in the RP-Set    to monitor liveness. When a C-RP
  2515.  
  2516.  
  2517.  
  2518. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 42]
  2519.  
  2520.  
  2521.  
  2522.  
  2523.  
  2524. Internet Draft          PIM-SM Specification              March 1997
  2525.  
  2526.  
  2527.          is    added to the RP-Set, its timer is set  to  the    Holdtime
  2528.          included  in  the C-RP-Adv    message    from that C-RP (which is
  2529.          equal to the C-RP's value of [RP-Holdtime]). Every     time  a
  2530.          subsequent     C-RP-Adv is received from that    RP, its    timer is
  2531.          restarted to the Holdtime in the C-RP-Adv.    When  the  timer
  2532.          expires,  the  RP    is  removed  from the RP-Set included in
  2533.          Bootstrap messages.
  2534.  
  2535.  
  2536.     *    [Bootstrap-Timer]    This  timer  is     used  by  the    BSR   to
  2537.          periodically  originate  Bootstrap     messages,  and    by other
  2538.          routers to    time out the BSR (see
  2539.           3.6.3).  This  timer  is    initially  set    to   [Bootstrap-
  2540.          Timeout].    A  C-BSR  restarts  this  timer     to  [Bootstrap-
  2541.          Timeout]  upon  receiving    a  Bootstrap  message    from   a
  2542.          preferred    router,     and  originates a Bootstrap message and
  2543.          restarts the timer    to [Bootstrap-Period] when  it    expires.
  2544.          Routers  not  configured  as  C-BSR's restart this    timer to
  2545.          [Bootstrap-Timeout] upon receiving    a Bootstrap message from
  2546.          the  elected  or a    more preferred BSR, and    ignore Bootstrap
  2547.          messages from non-preferred C-BSRs    while it is running.
  2548.  
  2549.  
  2550.  
  2551.      3.8.4 Default timer values
  2552.  
  2553.     Most of    the default timeout values for state information are 3.5
  2554.     times  the  refresh period. For    example, Hellos    refresh    Neighbor
  2555.     state and the default Hello-timer period is  30     seconds,  so  a
  2556.     default     Neighbor-timer     duration  of 105 seconds is included in
  2557.     the  Holdtime  field  of  the  Hellos.    In  order   to     improve
  2558.     convergence,  however, the default timeout value for information
  2559.     related    to RP liveness and Bootstrap messages is 2.5  times  the
  2560.     refresh    period.
  2561.  
  2562.     In this    version    of the spec,  we  suggest  particular  numerical
  2563.     timer  settings.  A  future  version  of  the specification will
  2564.     specify    a mechanism for    timer values to     be  scaled  based  upon
  2565.     observed network parameters.
  2566.  
  2567.  
  2568.  
  2569.  
  2570.     *    [Join/Prune-Period]  This    is  the      interval   between
  2571.          sending  Join/Prune  messages. Default: 60    seconds. This
  2572.          value may be set to take into account such     things     as  the
  2573.          configured      bandwidth   and  expected  average  number  of
  2574.          multicast route entries for the attached  network    or  link
  2575.  
  2576.  
  2577.  
  2578. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 43]
  2579.  
  2580.  
  2581.  
  2582.  
  2583.  
  2584. Internet Draft          PIM-SM Specification              March 1997
  2585.  
  2586.  
  2587.          (e.g., the    period would be    longer for lower-speed links, or
  2588.          for routers in the    center of the  network    that  expect  to
  2589.          have  a  larger  number of    entries    ). In addition,    a router
  2590.          could modify  this     value    (and  corresponding  Join/Prune-
  2591.          Holdtime  value)  if  the    number    of route entries changes
  2592.          significantly  (e.g.,  by    an  order  of  magnitude).   For
  2593.          example,  given  a    default    minimum    Join/Prune-Period value,
  2594.          if    the number  of    route  entries    with  a     particular  iif
  2595.          increases    from  N     to N*100, the router could increase its
  2596.          Join/Prune-Period    (and  Join/Prune-Holdtime),   for   that
  2597.          interface,     by  a    factor    of 10; and if/when the number of
  2598.          entries decreases back to    N,  the     Join/Prune-Period  (and
  2599.          Join/Prune-Holdtime)  could  be  decreased     to its    previous
  2600.          value. If the Join/Prune-Period is    modified, these     changes
  2601.          should  be     made  relatively  infrequently     and  the router
  2602.          should continue to     refresh  at  its  previous  Join/Prune-
  2603.          Period  for at least Join/Prune-Holdtime, in order    to allow
  2604.          the upstream router to adapt.
  2605.  
  2606.  
  2607.     *    [Join-Prune Holdtime] This    is the Holdtime    specified in
  2608.          Join/Prune     messages,  and     is  used to time out oifs. This
  2609.          should be set to 3.5 * [Join/Prune-Period].  Default:  210
  2610.          seconds.
  2611.  
  2612.  
  2613.     *    [Join/Prune-Suppression-Timeout]  This  is      the    mean
  2614.          interval  between    receiving  a  Join/Prune  with    a higher
  2615.          Holdtime (with ties broken    by higher network layer    address)
  2616.          and  allowing  duplicate Join/Prunes to be    sent again. This
  2617.          should be set to approximately 1.25 *  [Join/Prune-Period].
  2618.           Default: 75 seconds.
  2619.  
  2620.  
  2621.     *    [Data-Timeout] This is the    time after which (S,G) state
  2622.          for  a  silent  source  will  be  deleted.       Default: 210
  2623.          seconds.
  2624.  
  2625.  
  2626.     *    [Register-Suppression-Timeout]   This   is      the    mean
  2627.          interval  between    receiving  a  Register-Stop and    allowing
  2628.          Registers to be  sent  again.  A  lower  value  means  more
  2629.          frequent  register    bursts at RP, while a higher value means
  2630.          longer join  latency  for    new  receivers.       Default:  60
  2631.          seconds.  (Note  that  if    null Registers are sent    [Probe-
  2632.          Time] seconds  before  the     timeout,  register  bursts  are
  2633.          prevents, and [Register-Suppression-Timeout] may be lowered
  2634.          to    decrease join latency.)
  2635.  
  2636.  
  2637.  
  2638. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 44]
  2639.  
  2640.  
  2641.  
  2642.  
  2643.  
  2644. Internet Draft          PIM-SM Specification              March 1997
  2645.  
  2646.  
  2647.     *    [Probe-Time] When null Registers are used,    this is     the
  2648.          time  between  sending  a    null  Register and the Register-
  2649.          Suppression-Timer    expiring  unless  it  is  restarted   by
  2650.          receiving    a  Register-Stop. Thus,    a null Register    would be
  2651.          sent  when     the  Register-Suppression-Timer  reaches   this
  2652.          value.  Default: 5    seconds.
  2653.  
  2654.  
  2655.     *    [Assert-Timeout] This is the interval between the    last
  2656.          time  an  Assert  is  received,  and  the time at which the
  2657.          assert is timed out.  Default: 180    seconds.
  2658.  
  2659.  
  2660.     *    [Random-Delay-Join-Timeout]   This      is   the   maximum
  2661.          interval  between    the  time when the RPF neighbor    changes,
  2662.          and the time at which a  triggered     Join/Prune  message  is
  2663.          sent. Default: 4.5    seconds.
  2664.  
  2665.  
  2666.     *    [Hello-Period] This is  the  interval  between  sending
  2667.          Hello messages.  Default: 30 seconds.
  2668.  
  2669.  
  2670.     *    [Hello-Holdtime] This  is    the  Holdtime  specified  in
  2671.          Hello  messages,  after which neighbors will time out their
  2672.          neighbor entries for the router. This should be set to  3.5
  2673.          * [Hello-Period]. Default:    105 seconds.
  2674.  
  2675.  
  2676.     *    [C-RP-Adv-Period]    For  C-RPs,  this  is  the  interval
  2677.          between sending C-RP-Adv messages.    Default: 60 seconds.
  2678.  
  2679.  
  2680.     *    [RP-Holdtime] For C-RPs, this is the Holdtime specified
  2681.          in     C-RP-Adv  messages,  and is used by the BSR to    time out
  2682.          RPs. This should be  set  to  2.5    *  [C-RP-Adv-Period].
  2683.          Default: 150 seconds.
  2684.  
  2685.  
  2686.     *    [Bootstrap-Period]    At the    elected     BSR,  this  is     the
  2687.          interval between originating Bootstrap messages, and should
  2688.          be    equal to 60 seconds.
  2689.  
  2690.  
  2691.     *    [Bootstrap-Timeout] This is the time  after  which     the
  2692.          elected  BSR  will     be  assumed  unreachable when Bootstrap
  2693.          messages are not received from it.    This should be set to
  2694.          `2    * [Bootstrap-Period] + 10'. Default: 130 seconds.
  2695.  
  2696.  
  2697.  
  2698. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 45]
  2699.  
  2700.  
  2701.  
  2702.  
  2703.  
  2704. Internet Draft          PIM-SM Specification              March 1997
  2705.  
  2706.  
  2707.      3.9 Summary of flags used
  2708.  
  2709.     Following is a summary of all the flags    used in    our scheme.
  2710.  
  2711. Bit          |     Used in    |  Definition
  2712.  
  2713. Border          |    Register    | Register for external sources is coming from
  2714.                   PIM multicast  border  router
  2715. Null          |    Register    | Register sent as Probe of    RP, the    encapsulated
  2716.                   IP data packet should  not  be  forwarded
  2717. RPT          |    Route entry | Entry represents    state  on  the    RP-tree
  2718. RPT          |    Join/Prune  | Join is associated with the shared tree and
  2719.                   therefore    the Join/Prune message is propagated
  2720.                   along the    RP-tree    (source    encoded    is an RP
  2721.                   address)
  2722. RPT          |    Assert        | The data packet was routed down the shared
  2723.                   tree; thus, the path indicated corresponds
  2724.                   to the RP    tree
  2725. SPT          |    (S,G) entry | Packets have arrived on the iif towards S, and
  2726.                   the iif is different from    the (*,G) iif
  2727. WC          |Join        | The receiver expects to receive packets from all
  2728.                   sources via this (shared tree) path. Thus, the
  2729.                   Join/Prune applies to a (*,G) entry
  2730. WC          |    Route entry | Wildcard entry; if there is no more specific
  2731.                   match for    a particular source, packets will
  2732.                   be forwarded according to    this entry
  2733.  
  2734.  
  2735.  
  2736.      3.10 Security
  2737.  
  2738.     All PIM    control    messages may use IPsec [6] to  address    security
  2739.     concerns.
  2740.  
  2741.  
  2742.  
  2743.  
  2744.  
  2745.  
  2746.  
  2747.  
  2748.  
  2749.  
  2750.  
  2751.  
  2752.  
  2753.  
  2754.  
  2755.  
  2756.  
  2757.  
  2758.  
  2759.  
  2760. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 46]
  2761.  
  2762.  
  2763.  
  2764.  
  2765.  
  2766. Internet Draft          PIM-SM Specification              March 1997
  2767.  
  2768.  
  2769.      4 Packet Formats
  2770.  
  2771.     This section describes the details of the packet formats for PIM
  2772.     control    messages.
  2773.  
  2774.     All PIM    control    messages have protocol number 103.
  2775.  
  2776.     Basically, PIM messages    are either unicast (e.g.  Registers  and
  2777.     Register-Stop),     or  multicast    hop-by-hop  to `ALL-PIM-ROUTERS'
  2778.     group `224.0.0.13' (e.g. Join/Prune, Asserts, etc.).
  2779.  
  2780.  
  2781.      0             1             2             3
  2782.      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  2783.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2784.     |PIM Ver| Type  | Reserved        |        Checksum        |
  2785.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2786.  
  2787.  
  2788.  
  2789.  
  2790.  
  2791.     PIM Ver
  2792.           PIM Version number is 2.
  2793.  
  2794.  
  2795.     Type  Types for    specific PIM messages.    PIM Types are:
  2796.  
  2797.  
  2798.  
  2799.        0 = Hello
  2800.        1 = Register
  2801.        2 = Register-Stop
  2802.        3 = Join/Prune
  2803.        4 = Bootstrap
  2804.        5 = Assert
  2805.        6 = Graft (used in PIM-DM only)
  2806.        7 = Graft-Ack (used in PIM-DM only)
  2807.        8 = Candidate-RP-Advertisement
  2808.  
  2809.  
  2810.  
  2811.     Reserved
  2812.           set to zero. Ignored upon    receipt.
  2813.  
  2814.  
  2815.     Checksum
  2816.           The checksum is the 16-bit one's complement of  the  one's
  2817.  
  2818.  
  2819.  
  2820. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 47]
  2821.  
  2822.  
  2823.  
  2824.  
  2825.  
  2826. Internet Draft          PIM-SM Specification              March 1997
  2827.  
  2828.  
  2829.          complement     sum  of  the entire PIM message, (excluding the
  2830.          data portion in the Register message).  For  computing  the
  2831.          checksum, the checksum field is zeroed.
  2832.  
  2833.  
  2834.  
  2835.  
  2836.  
  2837.  
  2838.  
  2839.  
  2840.  
  2841.  
  2842.  
  2843.  
  2844.  
  2845.  
  2846.  
  2847.  
  2848.  
  2849.  
  2850.  
  2851.  
  2852.  
  2853.  
  2854.  
  2855.  
  2856.  
  2857.  
  2858.  
  2859.  
  2860.  
  2861.  
  2862.  
  2863.  
  2864.  
  2865.  
  2866.  
  2867.  
  2868.  
  2869.  
  2870.  
  2871.  
  2872.  
  2873.  
  2874.  
  2875.  
  2876.  
  2877.  
  2878.  
  2879.  
  2880. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 48]
  2881.  
  2882.  
  2883.  
  2884.  
  2885.  
  2886. Internet Draft          PIM-SM Specification              March 1997
  2887.  
  2888.  
  2889.      4.1 Encoded Source    and Group Address formats
  2890.  
  2891.  
  2892.  
  2893.     1    Encoded-Unicast-address: Takes the    following format:
  2894.  
  2895.  
  2896.       0              1              2              3
  2897.       0 1 2    3 4 5 6    7 8 9 0    1 2 3 4    5 6 7 8    9 0 1 2    3 4 5 6    7 8 9 0    1
  2898.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2899.      | Addr    Family     | Encoding Type |     Unicast Address         |
  2900.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+++++++
  2901.  
  2902.  
  2903.  
  2904.  
  2905.          Addr Family
  2906.            The address family of the `Unicast Address' field  of
  2907.           this address.
  2908.  
  2909.           Here is the address family numbers assigned by IANA:
  2910.  
  2911.  
  2912.          Number    Description
  2913.          - ------     ---------------------------------------------------------
  2914.           0    Reserved
  2915.           1    IP (IP version 4)
  2916.           2    IP6 (IP version 6)
  2917.           3    NSAP
  2918.           4    HDLC (8-bit multidrop)
  2919.           5    BBN 1822
  2920.           6    802 (includes all 802 media plus    Ethernet "canonical format")
  2921.           7    E.163
  2922.           8    E.164 (SMDS, Frame Relay, ATM)
  2923.           9    F.69 (Telex)
  2924.          10    X.121 (X.25, Frame Relay)
  2925.          11    IPX
  2926.          12    Appletalk
  2927.          13    Decnet IV
  2928.          14    Banyan Vines
  2929.          15    E.164 with NSAP format subaddress
  2930.  
  2931.  
  2932.  
  2933.          Encoding Type
  2934.            The type of encoding    used within a  specific     Address
  2935.           Family.  The value `0' is reserved for this field, and
  2936.           represents the native    encoding of the    Address    Family.
  2937.  
  2938.  
  2939.  
  2940. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 49]
  2941.  
  2942.  
  2943.  
  2944.  
  2945.  
  2946. Internet Draft          PIM-SM Specification              March 1997
  2947.  
  2948.  
  2949.          Unicast Address
  2950.            The unicast    address     as  represented  by  the  given
  2951.           Address Family and Encoding Type.
  2952.  
  2953.  
  2954.  
  2955.  
  2956.     2    Encoded-Group-Address: Takes the following    format:
  2957.  
  2958.  
  2959.       0              1              2              3
  2960.       0 1 2    3 4 5 6    7 8 9 0    1 2 3 4    5 6 7 8    9 0 1 2    3 4 5 6    7 8 9 0    1
  2961.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2962.      | Addr    Family     | Encoding Type |   Reserved     |  Mask Len     |
  2963.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2964.      |          Group    multicast Address             |
  2965.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2966.  
  2967.  
  2968.  
  2969.  
  2970.          Addr Family
  2971.            described above.
  2972.  
  2973.          Encoding Type
  2974.            described above.
  2975.  
  2976.          Reserved
  2977.            Transmitted as zero.    Ignored    upon receipt.
  2978.  
  2979.          Mask Len
  2980.            The Mask length is 8    bits. The value    is the number of
  2981.           contiguous  bits  left  justified used as a mask which
  2982.           describes the    address. It is less than or equal to the
  2983.           address  length  in  bits for    the given Address Family
  2984.           and Encoding Type. If    the message is sent for    a single
  2985.           group     then  the  Mask  length  must equal the address
  2986.           length in  bits  for    the  given  Address  Family  and
  2987.           Encoding  Type.  (e.g. 32 for    IPv4 native encoding and
  2988.           128 for IPv6 native encoding).
  2989.  
  2990.          Group multicast Address
  2991.            contains the    group address.
  2992.  
  2993.  
  2994.  
  2995.     3    Encoded-Source-Address: Takes the following format:
  2996.  
  2997.  
  2998.  
  2999.  
  3000. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 50]
  3001.  
  3002.  
  3003.  
  3004.  
  3005.  
  3006. Internet Draft          PIM-SM Specification              March 1997
  3007.  
  3008.  
  3009.  
  3010.       0              1              2              3
  3011.       0 1 2    3 4 5 6    7 8 9 0    1 2 3 4    5 6 7 8    9 0 1 2    3 4 5 6    7 8 9 0    1
  3012.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3013.      | Addr    Family     | Encoding Type | Rsrvd   |S|W|R|  Mask Len     |
  3014.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3015.      |              Source Address             |
  3016.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3017.  
  3018.  
  3019.  
  3020.  
  3021.  
  3022.          Addr Family
  3023.            described above.
  3024.  
  3025.          Encoding Type
  3026.            described above.
  3027.  
  3028.          Reserved
  3029.            Transmitted as zero,    ignored    on receipt.
  3030.  
  3031.          S,W,R See Section 4.5 for details.
  3032.  
  3033.          Mask Length
  3034.            Mask    length is 8 bits. The value  is     the  number  of
  3035.           contiguous  bits  left  justified used as a mask which
  3036.           describes the    address. The mask length  must    be  less
  3037.           than    or  equal  to the address length in bits for the
  3038.           given    Address    Family and Encoding Type. If the message
  3039.           is  sent  for    a single group then the    Mask length must
  3040.           equal    the address length in bits for the given Address
  3041.           Family  and  Encoding    Type. In version 2 of PIM, it is
  3042.           strongly recommended that this field be set to 32  for
  3043.           IPv4 native encoding.
  3044.  
  3045.          Source Address
  3046.            The source address.
  3047.  
  3048.  
  3049.  
  3050.  
  3051.  
  3052.  
  3053.  
  3054.  
  3055.  
  3056.  
  3057.  
  3058.  
  3059.  
  3060. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 51]
  3061.  
  3062.  
  3063.  
  3064.  
  3065.  
  3066. Internet Draft          PIM-SM Specification              March 1997
  3067.  
  3068.  
  3069.      4.2 Hello Message
  3070.  
  3071.     It is sent periodically    by routers on all interfaces.
  3072.  
  3073.  
  3074.      0             1             2             3
  3075.      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  3076.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3077.     |PIM Ver| Type  | Reserved        |        Checksum        |
  3078.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3079.     |        OptionType            |          OptionLength        |
  3080.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3081.     |                   OptionValue                |
  3082.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+++
  3083.     |                    .                    |
  3084.     |                    .                    |
  3085.     |                    .                    |
  3086.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3087.     |        OptionType            |          OptionLength        |
  3088.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3089.     |                   OptionValue                |
  3090.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+++
  3091.  
  3092.  
  3093.  
  3094.  
  3095.     PIM Version, Type, Reserved, Checksum
  3096.           Described    above.
  3097.  
  3098.     OptionType
  3099.           The type of the option given in the following  OptionValue
  3100.          field.
  3101.  
  3102.     OptionLength
  3103.           The length of the    OptionValue field in bytes.
  3104.  
  3105.     OptionValue
  3106.           A    variable length    field, carrying    the value of the option.
  3107.  
  3108.     The Option fields may contain the following values:
  3109.  
  3110.  
  3111.     *    OptionType    = 1; OptionLength = 2; OptionValue  =  Holdtime;
  3112.          where  Holdtime  is the amount of time a receiver must keep
  3113.          the neighbor reachable, in    seconds. If the    Holdtime is  set
  3114.          to     `0xffff',  the    receiver of this message never times out
  3115.          the neighbor. This    may be used with ISDN  lines,  to  avoid
  3116.          keeping   the   link   up    with  periodic    Hello  messages.
  3117.  
  3118.  
  3119.  
  3120. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 52]
  3121.  
  3122.  
  3123.  
  3124.  
  3125.  
  3126. Internet Draft          PIM-SM Specification              March 1997
  3127.  
  3128.  
  3129.          Furthermore, if the Holdtime is set to `0', the information
  3130.          is    timed out immediately.
  3131.  
  3132.     *    OptionType    2 to 16: reserved
  3133.  
  3134.     *    The  rest    of  the     OptionTypes  are  defined  in     another
  3135.          document.
  3136.  
  3137.  
  3138.     In general, options may    be ignored; but    a router must not ignore
  3139.     the
  3140.  
  3141.  
  3142.  
  3143.  
  3144.  
  3145.  
  3146.  
  3147.  
  3148.  
  3149.  
  3150.  
  3151.  
  3152.  
  3153.  
  3154.  
  3155.  
  3156.  
  3157.  
  3158.  
  3159.  
  3160.  
  3161.  
  3162.  
  3163.  
  3164.  
  3165.  
  3166.  
  3167.  
  3168.  
  3169.  
  3170.  
  3171.  
  3172.  
  3173.  
  3174.  
  3175.  
  3176.  
  3177.  
  3178.  
  3179.  
  3180. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 53]
  3181.  
  3182.  
  3183.  
  3184.  
  3185.  
  3186. Internet Draft          PIM-SM Specification              March 1997
  3187.  
  3188.  
  3189.      4.3 Register Message
  3190.  
  3191.     A Register message is sent by the DR or    a PMBR to the RP when  a
  3192.     multicast  packet needs    to be transmitted on the RP-tree. Source
  3193.     address    is set to the address of the DR, destination address  is
  3194.     to the RP's address.
  3195.  
  3196.  
  3197.      0             1             2             3
  3198.      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  3199.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3200.     |PIM Ver| Type  | Reserved        |        Checksum        |
  3201.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3202.     |B|N|            Reserved                |
  3203.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3204.     |                                    |
  3205.               Multicast data packet
  3206.     |                                    |
  3207.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3208.  
  3209.  
  3210.  
  3211.  
  3212.     PIM Version, Type, Reserved, Checksum
  3213.           Described    above.    Note that the checksum    for  Registers
  3214.          is     done  only on the PIM header, excluding the data packet
  3215.          portion.
  3216.  
  3217.     B     The Border bit. If the router is a DR for    a source that it
  3218.          is     directly  connected  to, it sets the B    bit to 0. If the
  3219.          router is a PMBR for  a  source  in  a  directly  connected
  3220.          cloud, it sets the    B bit to 1.
  3221.  
  3222.  
  3223.  
  3224.  
  3225.     N     The Null-Register    bit. Set to 1 by a DR  that  is     probing
  3226.          the  RP  before  expiring    its  local  Register-Suppression
  3227.          timer. Set    to 0 otherwise.
  3228.  
  3229.  
  3230.     Multicast data packet
  3231.           The original packet sent by the source.
  3232.  
  3233.     For (S,G) null Registers,  the    Multicast  data     packet     portion
  3234.     contains  only a dummy header with S as    the source address, G as
  3235.     the destination    address, and a data length of zero.
  3236.  
  3237.  
  3238.  
  3239.  
  3240. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 54]
  3241.  
  3242.  
  3243.  
  3244.  
  3245.  
  3246. Internet Draft          PIM-SM Specification              March 1997
  3247.  
  3248.  
  3249.      4.4 Register-Stop Message
  3250.  
  3251.     A Register-Stop    is unicast from    the RP    to  the     sender     of  the
  3252.     Register  message.  Source  address  is    the address to which the
  3253.     register  was  addressed.  Destination    address     is  the  source
  3254.     address    of the register    message.
  3255.  
  3256.  
  3257.      0             1             2             3
  3258.      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  3259.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3260.     |PIM Ver| Type  | Reserved        |        Checksum        |
  3261.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3262.     |             Encoded-Group Address                |
  3263.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3264.     |             Encoded-Unicast-Source    Address            |
  3265.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3266.  
  3267.  
  3268.  
  3269.  
  3270.     PIM Version, Type, Reserved, Checksum
  3271.           Described    above.
  3272.  
  3273.     Encoded-Group Address
  3274.           Format described above. Note that    for  Register-Stops  the
  3275.          Mask  Len    field  contains    full address length * 8    (e.g. 32
  3276.          for IPv4 native encoding),    if the message    is  sent  for  a
  3277.          single group.
  3278.  
  3279.     Encoded-Unicast-Source Address
  3280.           host address of  source  from  multicast    data  packet  in
  3281.          register.    The  format  for  this    address     is given in the
  3282.          Encoded-Unicast-Address in     4.1. A    special    wild card  value
  3283.          (0's), can    be used    to indicate any    source.
  3284.  
  3285.  
  3286.  
  3287.  
  3288.  
  3289.  
  3290.  
  3291.  
  3292.  
  3293.  
  3294.  
  3295.  
  3296.  
  3297.  
  3298.  
  3299.  
  3300. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 55]
  3301.  
  3302.  
  3303.  
  3304.  
  3305.  
  3306. Internet Draft          PIM-SM Specification              March 1997
  3307.  
  3308.  
  3309.      4.5 Join/Prune Message
  3310.  
  3311.     A Join/Prune message is    sent by    routers    towards    upstream sources
  3312.     and  RPs.  Joins  are  sent  to    build shared trees (RP trees) or
  3313.     source trees (SPT). Prunes are sent to prune source  trees  when
  3314.     members     leave    groups    as  well  as sources that do not use the
  3315.     shared tree.
  3316.  
  3317.  
  3318.  
  3319.  
  3320.  
  3321.  
  3322.  
  3323.  
  3324.  
  3325.  
  3326.  
  3327.  
  3328.  
  3329.  
  3330.  
  3331.  
  3332.  
  3333.  
  3334.  
  3335.  
  3336.  
  3337.  
  3338.  
  3339.  
  3340.  
  3341.  
  3342.  
  3343.  
  3344.  
  3345.  
  3346.  
  3347.  
  3348.  
  3349.  
  3350.  
  3351.  
  3352.  
  3353.  
  3354.  
  3355.  
  3356.  
  3357.  
  3358.  
  3359.  
  3360. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 56]
  3361.  
  3362.  
  3363.  
  3364.  
  3365.  
  3366. Internet Draft          PIM-SM Specification              March 1997
  3367.  
  3368.  
  3369.  
  3370.      0             1             2             3
  3371.      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  3372.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3373.     |PIM Ver| Type  | Reserved        |        Checksum        |
  3374.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3375.     |          Encoded-Unicast-Upstream Neighbor Address        |
  3376.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3377.     |  Reserved        | Num groups    |           Holdtime            |
  3378.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3379.     |         Encoded-Multicast Group Address-1            |
  3380.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3381.     |    Number of Joined  Sources   |    Number of Pruned Sources    |
  3382.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3383.     |            Encoded-Joined Source Address-1            |
  3384.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3385.     |                  .                    |
  3386.     |                  .                    |
  3387.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3388.     |            Encoded-Joined Source Address-n            |
  3389.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3390.     |            Encoded-Pruned Source Address-1            |
  3391.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3392.     |                  .                    |
  3393.     |                  .                    |
  3394.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3395.     |            Encoded-Pruned Source Address-n            |
  3396.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3397.     |                .                    |
  3398.     |                .                    |
  3399.     |                .                    |
  3400.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3401.     |             Encoded-Multicast Group Address-n            |
  3402.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3403.     |    Number of Joined  Sources   |    Number of Pruned Sources    |
  3404.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3405.     |            Encoded-Joined Source Address-1            |
  3406.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3407.     |                  .                    |
  3408.     |                  .                    |
  3409.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3410.     |            Encoded-Joined Source Address-n            |
  3411.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3412.     |            Encoded-Pruned Source Address-1            |
  3413.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3414.     |                  .                    |
  3415.     |                  .                    |
  3416.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3417.  
  3418.  
  3419.  
  3420. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 57]
  3421.  
  3422.  
  3423.  
  3424.  
  3425.  
  3426. Internet Draft          PIM-SM Specification              March 1997
  3427.  
  3428.  
  3429.     |            Encoded-Pruned Source Address-n            |
  3430.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3431.  
  3432.  
  3433.  
  3434.  
  3435.     PIM Version, Type, Reserved, Checksum
  3436.           Described    above.
  3437.  
  3438.     Encoded-Unicast    Upstream Neighbor Address
  3439.           The address of the RPF or    upstream  neighbor.  The  format
  3440.          for this address is given in the Encoded-Unicast-Address in
  3441.          4.1. .IP "Reserved"
  3442.           Transmitted as zero, ignored on receipt.
  3443.  
  3444.     Holdtime
  3445.           The amount of time a receiver  must  keep     the  Join/Prune
  3446.          state  alive,  in    seconds.  If  the  Holdtime  is     set  to
  3447.          `0xffff', the receiver of this message never times    out  the
  3448.          oif. This may be used with    ISDN lines, to avoid keeping the
  3449.          link up with periodical Join/Prune     messages.  Furthermore,
  3450.          if    the Holdtime is    set to `0', the    information is timed out
  3451.          immediately.
  3452.  
  3453.     Number of Groups
  3454.           The number  of  multicast     group    sets  contained     in  the
  3455.          message.
  3456.  
  3457.     Encoded-Multicast group    address
  3458.           For format description see Section
  3459.           4.1. A wild card group in    the (*,*,RP) join is represented
  3460.          by     a  224.0.0.0  in the group address field and `4' in the
  3461.          mask length field.    A (*,*,RP) join    also has the WC-bit  and
  3462.          the RPT-bit set.
  3463.  
  3464.  
  3465.     Number of Joined Sources
  3466.           Number of    join source addresses listed for a given group.
  3467.  
  3468.  
  3469.     Join Source Address-1 .. n
  3470.           This list    contains the sources  that  the     sending  router
  3471.          will  forward  multicast  datagrams  for if received on the
  3472.          interface this message is sent on.
  3473.  
  3474.          See format    section     4.1. The  fields  explanation    for  the
  3475.          Encoded-Source-Address format follows:
  3476.  
  3477.  
  3478.  
  3479.  
  3480. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 58]
  3481.  
  3482.  
  3483.  
  3484.  
  3485.  
  3486. Internet Draft          PIM-SM Specification              March 1997
  3487.  
  3488.  
  3489.          Reserved
  3490.            Described above.
  3491.  
  3492.          S       The Sparse bit is a 1 bit value, set    to 1 for PIM-SM.
  3493.           It is    used for PIM v.1 compatibility.
  3494.  
  3495.          W       The WC bit is a 1 bit value.    If 1, the join or  prune
  3496.           applies to the (*,G) or (*,*,RP) entry. If 0,    the join
  3497.           or prune applies to the (S,G)    entry where S is  Source
  3498.           Address.  Joins  and    prunes    sent towards the RP must
  3499.           have this bit    set.
  3500.  
  3501.          R       The RPT-bit is a 1 bit value. If 1,    the  information
  3502.           about     (S,G)    is  sent  towards  the    RP.  If     0,  the
  3503.           information must be sent toward  S,  where  S     is  the
  3504.           Source Address.
  3505.  
  3506.          Mask Length, Source Address
  3507.            Described above.
  3508.  
  3509.  
  3510.  
  3511.          Represented  in  the  form     of
  3512.          <    WC-bit    ><  RPT-bit  ><Mask length >< Source address>:
  3513.  
  3514.          A source address could  be     a  host  IPv4    native    encoding
  3515.          address :
  3516.  
  3517.           <    0 >< 0 >< 32 ><    192.1.1.17 >
  3518.  
  3519.          A source address could be the RP's    IP address :
  3520.  
  3521.           <    1 >< 1 >< 32 ><    131.108.13.111 >
  3522.  
  3523.          A source address could be a subnet    address     to  prune  from
  3524.          the RP-tree :
  3525.  
  3526.           <    0 >< 1 >< 28 ><    192.1.1.16 >
  3527.  
  3528.          A source address could be a general aggregate :
  3529.  
  3530.           <    0 >< 0 >< 16 ><    192.1.0.0 >
  3531.  
  3532.     Number of Pruned Sources
  3533.           Number of    prune source addresses listed for a group.
  3534.  
  3535.     Prune Source Address-1 .. n
  3536.           This list    contains the sources  that  the     sending  router
  3537.  
  3538.  
  3539.  
  3540. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 59]
  3541.  
  3542.  
  3543.  
  3544.  
  3545.  
  3546. Internet Draft          PIM-SM Specification              March 1997
  3547.  
  3548.  
  3549.          does  not    want  to  forward  multicast  datagrams    for when
  3550.          received on the interface this message is sent on.     If  the
  3551.          Join/Prune     message  boundary  exceeds  the  maximum packet
  3552.          size, then    the join and prune lists for the same group must
  3553.          be    included in the    same packet.
  3554.  
  3555.  
  3556.  
  3557.  
  3558.  
  3559.  
  3560.  
  3561.  
  3562.  
  3563.  
  3564.  
  3565.  
  3566.  
  3567.  
  3568.  
  3569.  
  3570.  
  3571.  
  3572.  
  3573.  
  3574.  
  3575.  
  3576.  
  3577.  
  3578.  
  3579.  
  3580.  
  3581.  
  3582.  
  3583.  
  3584.  
  3585.  
  3586.  
  3587.  
  3588.  
  3589.  
  3590.  
  3591.  
  3592.  
  3593.  
  3594.  
  3595.  
  3596.  
  3597.  
  3598.  
  3599.  
  3600. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 60]
  3601.  
  3602.  
  3603.  
  3604.  
  3605.  
  3606. Internet Draft          PIM-SM Specification              March 1997
  3607.  
  3608.  
  3609.      4.6 Bootstrap Message
  3610.  
  3611.     The Bootstrap messages are multicast to    `ALL-PIM-ROUTERS' group,
  3612.     out  all interfaces having PIM neighbors (excluding the    one over
  3613.     which the message was received).  Bootstrap  messages  are  sent
  3614.     with  TTL  value  of 1.    Bootstrap messages originate at    the BSR,
  3615.     and are    forwarded by intermediate routers.
  3616.  
  3617.     Bootstrap message is divided up    into  `semantic     fragments',  if
  3618.     the original message exceeds the maximum packet    size boundaries.
  3619.  
  3620.     The semantics of a single `fragment' is    given below:
  3621.  
  3622.  
  3623.  
  3624.  
  3625.  
  3626.  
  3627.  
  3628.  
  3629.  
  3630.  
  3631.  
  3632.  
  3633.  
  3634.  
  3635.  
  3636.  
  3637.  
  3638.  
  3639.  
  3640.  
  3641.  
  3642.  
  3643.  
  3644.  
  3645.  
  3646.  
  3647.  
  3648.  
  3649.  
  3650.  
  3651.  
  3652.  
  3653.  
  3654.  
  3655.  
  3656.  
  3657.  
  3658.  
  3659.  
  3660. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 61]
  3661.  
  3662.  
  3663.  
  3664.  
  3665.  
  3666. Internet Draft          PIM-SM Specification              March 1997
  3667.  
  3668.  
  3669.  
  3670.      0             1             2             3
  3671.      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  3672.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3673.     |PIM Ver| Type  | Reserved        |        Checksum        |
  3674.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3675.     |          Fragment Tag        | Hash Mask    len | BSR-priority  |
  3676.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3677.     |              Encoded-Unicast-BSR-Address            |
  3678.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3679.     |                  Encoded-Group Address-1            |
  3680.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3681.     | RP-Count-1    | Frag RP-Cnt-1 |          Reserved            |
  3682.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3683.     |              Encoded-Unicast-RP-Address-1            |
  3684.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3685.     |           RP1-Holdtime        | RP1-Priority  |    Reserved    |
  3686.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3687.     |              Encoded-Unicast-RP-Address-2            |
  3688.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3689.     |           RP2-Holdtime        | RP2-Priority  |    Reserved    |
  3690.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3691.     |                    .                    |
  3692.     |                    .                    |
  3693.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3694.     |              Encoded-Unicast-RP-Address-m            |
  3695.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3696.     |           RPm-Holdtime        | RPm-Priority  |    Reserved    |
  3697.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3698.     |                  Encoded-Group Address-2            |
  3699.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3700.     |                    .                    |
  3701.     |                    .                    |
  3702.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3703.     |                  Encoded-Group Address-n            |
  3704.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3705.     | RP-Count-n    | Frag RP-Cnt-n |           Reserved            |
  3706.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3707.     |              Encoded-Unicast-RP-Address-1            |
  3708.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3709.     |           RP1-Holdtime        | RP1-Priority  |    Reserved    |
  3710.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3711.     |              Encoded-Unicast-RP-Address-2            |
  3712.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3713.     |           RP2-Holdtime        | RP2-Priority  |    Reserved    |
  3714.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3715.     |                    .                    |
  3716.     |                    .                    |
  3717.  
  3718.  
  3719.  
  3720. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 62]
  3721.  
  3722.  
  3723.  
  3724.  
  3725.  
  3726. Internet Draft          PIM-SM Specification              March 1997
  3727.  
  3728.  
  3729.     |                    .                    |
  3730.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3731.     |              Encoded-Unicast-RP-Address-m            |
  3732.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3733.     |           RPm-Holdtime        | RPm-Priority  |    Reserved    |
  3734.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3735.  
  3736.  
  3737.  
  3738.  
  3739.  
  3740.     PIM Version, Type, Reserved, Checksum
  3741.           Described    above.
  3742.  
  3743.     Fragment Tag
  3744.           A    randomly  generated  number,  acts  to    distinguish  the
  3745.          fragments     belonging   to     different  Bootstrap  messages;
  3746.          fragments belonging to same  Bootstrap  message  carry  the
  3747.          same `Fragment Tag'.
  3748.  
  3749.     Hash Mask len
  3750.           The length (in bits) of  the  mask  to  use  in  the  hash
  3751.          function.    For IPv4 we recommend a    value of 30. For IPv6 we
  3752.          recommend a value of 126.
  3753.  
  3754.     BSR-priority
  3755.           Contains the BSR priority    value of the included BSR.  This
  3756.          field is considered as a high order byte when comparing BSR
  3757.          addresses.
  3758.  
  3759.     Encoded-Unicast-BSR-Address
  3760.           The address of the bootstrap router for  the  domain.  The
  3761.          format  for  this    address    is given in the    Encoded-Unicast-
  3762.          Address in     4.1. .IP "Encoded-Group Address-1..n"
  3763.           The  group  prefix  (address  and     mask)    with  which  the
  3764.          Candidate RPs are associated. Format previously described.
  3765.  
  3766.  
  3767.     RP-Count-1..n
  3768.           The number of Candidate RP addresses included in the whole
  3769.          Bootstrap    message     for  the  corresponding group prefix. A
  3770.          router does  not replace its old RP-Set for a  given  group
  3771.          prefix  until/unless  it  receives    `RP-Count' addresses for
  3772.          that prefix; the addresses    could be  carried  over     several
  3773.          fragments.     If  only  part     of the    RP-Set for a given group
  3774.          prefix  was  received,  the  router  discards  it,     without
  3775.          updating that specific group prefix's RP-Set.
  3776.  
  3777.  
  3778.  
  3779.  
  3780. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 63]
  3781.  
  3782.  
  3783.  
  3784.  
  3785.  
  3786. Internet Draft          PIM-SM Specification              March 1997
  3787.  
  3788.  
  3789.     Frag RP-Cnt-1..m
  3790.           The number of Candidate  RP  addresses  included    in  this
  3791.          fragment  of  the    Bootstrap message, for the corresponding
  3792.          group prefix. The `Frag RP-Cnt' field  facilitates     parsing
  3793.          of     the  RP-Set for a given group prefix, when carried over
  3794.          more than one fragment.
  3795.  
  3796.  
  3797.     Encoded-Unicast-RP-address-1..m
  3798.           The address of the Candidate RPs,     for  the  corresponding
  3799.          group  prefix.  The format    for this address is given in the
  3800.          Encoded-Unicast-Address in     4.1. .IP "RP1..m-Holdtime"
  3801.           The Holdtime for    the  corresponding  RP.     This  field  is
  3802.          copied  from  the    `Holdtime'  field  of  the associated RP
  3803.          stored at the BSR.
  3804.  
  3805.     RP1..m-Priority
  3806.           The `Priority' of    the corresponding RP  and  Encoded-Group
  3807.          Address.  This  field  is    copied from the    `Priority' field
  3808.          stored  at     the  BSR   when   receiving   a   Candidate-RP-
  3809.          Advertisement.  The highest priority is `0' (i.e. the lower
  3810.          the value of the `Priority' field,    the higher).  Note  that
  3811.          the priority is per RP per    Encoded-Group Address.
  3812.  
  3813.  
  3814.  
  3815.  
  3816.  
  3817.  
  3818.  
  3819.  
  3820.  
  3821.  
  3822.  
  3823.  
  3824.  
  3825.  
  3826.  
  3827.  
  3828.  
  3829.  
  3830.  
  3831.  
  3832.  
  3833.  
  3834.  
  3835.  
  3836.  
  3837.  
  3838.  
  3839.  
  3840. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 64]
  3841.  
  3842.  
  3843.  
  3844.  
  3845.  
  3846. Internet Draft          PIM-SM Specification              March 1997
  3847.  
  3848.  
  3849.      4.7 Assert    Message
  3850.  
  3851.     The Assert message is sent  when  a  multicast    data  packet  is
  3852.     received  on an    outgoing interface corresponding to the    (S,G) or
  3853.     (*,G) associated with the source.
  3854.  
  3855.  
  3856.      0             1             2             3
  3857.      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  3858.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3859.     |PIM Ver| Type  | Reserved        |        Checksum        |
  3860.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3861.     |               Encoded-Group Address            |
  3862.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3863.     |           Encoded-Unicast-Source Address            |
  3864.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3865.     |R|                   Metric Preference            |
  3866.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3867.     |                   Metric                    |
  3868.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3869.  
  3870.  
  3871.  
  3872.  
  3873.     PIM Version, Type, Reserved, Checksum
  3874.           Described    above.
  3875.  
  3876.     Encoded-Group Address
  3877.           The group    address    to which the data packet was  addressed,
  3878.          and   which   triggered   the   Assert.  Format  previously
  3879.          described.
  3880.  
  3881.     Encoded-Unicast-Source Address
  3882.           Source address from multicast datagram that triggered  the
  3883.          Assert  packet  to     be sent. The format for this address is
  3884.          given in the Encoded-Unicast-Address in  4.1. .IP "R"
  3885.           RPT-bit is a 1 bit value.    If the multicast  datagram  that
  3886.          triggered    the  Assert  packet  is    routed down the    RP tree,
  3887.          then the RPT-bit is 1; if the multicast datagram is  routed
  3888.          down the SPT, it is 0.
  3889.  
  3890.     Metric Preference
  3891.           Preference value assigned    to the unicast routing    protocol
  3892.          that provided the route to    Host address.
  3893.  
  3894.     Metric The unicast routing table metric. The metric is in  units
  3895.          applicable    to the unicast routing protocol    used.
  3896.  
  3897.  
  3898.  
  3899.  
  3900. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 65]
  3901.  
  3902.  
  3903.  
  3904.  
  3905.  
  3906. Internet Draft          PIM-SM Specification              March 1997
  3907.  
  3908.  
  3909.      4.8 Graft Message
  3910.  
  3911.     Used in    dense-mode. Refer to PIM dense mode specification.
  3912.  
  3913.      4.9 Graft-Ack Message
  3914.  
  3915.     Used in    dense-mode. Refer to PIM dense mode specification.
  3916.  
  3917.  
  3918.  
  3919.  
  3920.  
  3921.  
  3922.  
  3923.  
  3924.  
  3925.  
  3926.  
  3927.  
  3928.  
  3929.  
  3930.  
  3931.  
  3932.  
  3933.  
  3934.  
  3935.  
  3936.  
  3937.  
  3938.  
  3939.  
  3940.  
  3941.  
  3942.  
  3943.  
  3944.  
  3945.  
  3946.  
  3947.  
  3948.  
  3949.  
  3950.  
  3951.  
  3952.  
  3953.  
  3954.  
  3955.  
  3956.  
  3957.  
  3958.  
  3959.  
  3960. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 66]
  3961.  
  3962.  
  3963.  
  3964.  
  3965.  
  3966. Internet Draft          PIM-SM Specification              March 1997
  3967.  
  3968.  
  3969.      4.10 Candidate-RP-Advertisement
  3970.  
  3971.     Candidate-RP-Advertisements are    periodically  unicast  from  the
  3972.     C-RPs to the BSR.
  3973.  
  3974.      0             1             2             3
  3975.      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  3976.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3977.     |PIM Ver| Type  | Reserved        |        Checksum        |
  3978.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3979.     | Prefix-Cnt    |    Priority    |          Holdtime        |
  3980.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3981.     |              Encoded-Unicast-RP-Address            |
  3982.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3983.     |                  Encoded-Group Address-1            |
  3984.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3985.     |                    .                    |
  3986.     |                    .                    |
  3987.     |                    .                    |
  3988.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3989.     |                  Encoded-Group Address-n            |
  3990.     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3991.  
  3992.  
  3993.  
  3994.  
  3995.  
  3996.     PIM Version, Type, Reserved, Checksum
  3997.           Described    above.
  3998.  
  3999.     Prefix-Cnt
  4000.           The number of encoded  group  addresses  included     in  the
  4001.          message;  indicating  the group prefixes for which    the C-RP
  4002.          is    advertising. A Prefix-Cnt of `0'  implies  a  prefix  of
  4003.          224.0.0.0 with mask length    of 4; i.e. all multicast groups.
  4004.          If     the  C-RP   is      not    configured   with   Group-prefix
  4005.          information,  the    C-RP puts a default value of `0' in this
  4006.          field.
  4007.  
  4008.     Priority
  4009.           The `Priority' of    the included RP, for  the  corresponding
  4010.          Encoded-Group  Address  (if  any).     highest priority is `0'
  4011.          (i.e. the lower the value    of  the     `Priority'  field,  the
  4012.          higher  the priority). This field is stored at the    BSR upon
  4013.          receipt  along  with  the    RP  address  and   corresponding
  4014.          Encoded-Group Address.
  4015.  
  4016.     Holdtime
  4017.  
  4018.  
  4019.  
  4020. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 67]
  4021.  
  4022.  
  4023.  
  4024.  
  4025.  
  4026. Internet Draft          PIM-SM Specification              March 1997
  4027.  
  4028.  
  4029.           The amount of time the advertisement is valid. This  field
  4030.          allows advertisements to be aged out.
  4031.  
  4032.     Encoded-Unicast-RP-Address
  4033.           The address of the interface to advertise    as  a  Candidate
  4034.          RP.  The  format  for this    address    is given in the    Encoded-
  4035.          Unicast-Address in     4.1. .IP "Encoded-Group Address-1..n"
  4036.           The group    prefixes for  which  the  C-RP    is  advertising.
  4037.          Format previously described.
  4038.  
  4039.  
  4040.  
  4041.  
  4042.  
  4043.  
  4044.  
  4045.  
  4046.  
  4047.  
  4048.  
  4049.  
  4050.  
  4051.  
  4052.  
  4053.  
  4054.  
  4055.  
  4056.  
  4057.  
  4058.  
  4059.  
  4060.  
  4061.  
  4062.  
  4063.  
  4064.  
  4065.  
  4066.  
  4067.  
  4068.  
  4069.  
  4070.  
  4071.  
  4072.  
  4073.  
  4074.  
  4075.  
  4076.  
  4077.  
  4078.  
  4079.  
  4080. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 68]
  4081.  
  4082.  
  4083.  
  4084.  
  4085.  
  4086. Internet Draft          PIM-SM Specification              March 1997
  4087.  
  4088.  
  4089.      5 Acknowledgments
  4090.  
  4091.     Tony Ballardie,    Scott Brim, Jon     Crowcroft,  Bill  Fenner,  Paul
  4092.     Francis,   Joel     Halpern,  Horst  Hodel,  Polly     Huang,     Stephen
  4093.     Ostrowski,  Lixia  Zhang  and  Girish    Chandranmenon    provided
  4094.     detailed comments on previous drafts. The authors of CBT [8] and
  4095.     membership of the IDMR WG provided many    of the motivating  ideas
  4096.     for this work and useful feedback on design details.
  4097.  
  4098.     This work was supported     by  the  National  Science  Foundation,
  4099.     ARPA, cisco Systems and    Sun Microsystems.
  4100.  
  4101.  
  4102.  
  4103.  
  4104.  
  4105.  
  4106.  
  4107.  
  4108.  
  4109.  
  4110.  
  4111.  
  4112.  
  4113.  
  4114.  
  4115.  
  4116.  
  4117.  
  4118.  
  4119.  
  4120.  
  4121.  
  4122.  
  4123.  
  4124.  
  4125.  
  4126.  
  4127.  
  4128.  
  4129.  
  4130.  
  4131.  
  4132.  
  4133.  
  4134.  
  4135.  
  4136.  
  4137.  
  4138.  
  4139.  
  4140. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 69]
  4141.  
  4142.  
  4143.  
  4144.  
  4145.  
  4146. Internet Draft          PIM-SM Specification              March 1997
  4147.  
  4148.  
  4149.      6 Appendices
  4150.      6.1 Appendix I: Major Changes and Updates to the Spec
  4151.  
  4152.     This appendix populates    the major changes in  the  specification
  4153.     document as compared to    `draft-ietf-idmr-pim-spec-01.ps,txt'.
  4154.  
  4155.     bsubsection*Major Changes
  4156.  
  4157.     List of    changes    since March '96    IETF:
  4158.  
  4159.  
  4160.     1. (*,*,RP) Joins state    and data forwarding check;  replaces  (*,G-
  4161.     Prefix)     Joins    state for interoperability. (*,G) negative cache
  4162.     introduced for the (*,*,RP) state supporting mechanisms.
  4163.  
  4164.     2. Semantic fragmentation for the Bootstrap message.
  4165.  
  4166.     3. Refinement of Assert    details.
  4167.  
  4168.     4. Addition and    refinement of Join/Prune suppression  and  Register
  4169.     suppression (introduction of null Registers).
  4170.  
  4171.     5. Editorial changes and clarifications    to the timers section.
  4172.  
  4173.     6. Addition of Appendix    II (BSR    Election and RP-Set  Distribution),
  4174.     and Appendix III (Glossary of Terms).
  4175.  
  4176.     7. Addition of table of    contents.
  4177.  
  4178.  
  4179.     List of    changes    incurred since version 1 of the    spec.:
  4180.  
  4181.     1. Proposal and     refinement  of     bootstrap  router  (BSR)  election
  4182.     mechanisms
  4183.  
  4184.     2. Introduction    of hash    functions for Group to RP mapping
  4185.  
  4186.     3. New    RP-liveness  indication     mechanisms  based  upon  the    the
  4187.     Bootstrap Router (BSR) and the Bootstrap messages.
  4188.  
  4189.     4. Removal of reachability messages, RP    reports     and  multiple    RPs
  4190.     per group.
  4191.  
  4192.  
  4193.  
  4194.  
  4195. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 70]
  4196.  
  4197.  
  4198.  
  4199.  
  4200.  
  4201. Internet Draft          PIM-SM Specification              March 1997
  4202.  
  4203.  
  4204.     *Packet    Format Changes
  4205.  
  4206.     Packet Format incurred updates to accommodate different     address
  4207.     lengths, and address aggregation.
  4208.  
  4209.  
  4210.  
  4211.  
  4212.     1    The `Addr Family' and `Encoding Type' fields were added  to
  4213.          the packet    formats.
  4214.  
  4215.  
  4216.     2    The  Encoded  source  and    group    address      formats   were
  4217.          introduced,  with the use of a `Mask length' field    to allow
  4218.          aggregation, section  4.1.
  4219.  
  4220.     3    Packet formats are    no  longer  IGMP  messages;  rather  PIM
  4221.          messages.
  4222.  
  4223.  
  4224.  
  4225.     PIM message types and formats were also    modified:
  4226.  
  4227.  
  4228.     [Note: most changes were made to the May  95  version,    unless
  4229.     otherwise specified].
  4230.  
  4231.  
  4232.  
  4233.  
  4234.     1    Obsolete messages:
  4235.  
  4236.         Register-Ack [Feb. 96]
  4237.  
  4238.         Poll and Poll Response [Feb. 96]
  4239.  
  4240.         RP-Reachability [Feb. 96]
  4241.  
  4242.         RPlist-Mapping [Feb. 96]
  4243.  
  4244.  
  4245.     2     New messages:
  4246.  
  4247.  
  4248.  
  4249. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 71]
  4250.  
  4251.  
  4252.  
  4253.  
  4254.  
  4255. Internet Draft          PIM-SM Specification              March 1997
  4256.  
  4257.  
  4258.         Candidate-RP-Advertisement [change made in    October     95]
  4259.         RP-Set [Feb. 96]
  4260.  
  4261.     3    Modified messages:
  4262.  
  4263.         Join/Prune [Feb. 96]
  4264.         Register [Feb. 96]
  4265.         Register-Stop [Feb.     96]
  4266.         Hello (addition of OptionTypes) [Aug 96]
  4267.  
  4268.     4     Renamed messages:
  4269.  
  4270.          Query messages are    renamed    as Hello messages [Aug.    96]
  4271.          RP-Set  messages are renamed as Bootstrap messages    [Aug. 96]
  4272.  
  4273.  
  4274.  
  4275.  
  4276.  
  4277.  
  4278.  
  4279.  
  4280.  
  4281.  
  4282.  
  4283.  
  4284.  
  4285.  
  4286.  
  4287.  
  4288.  
  4289.  
  4290.  
  4291.  
  4292.  
  4293.  
  4294.  
  4295.  
  4296.  
  4297.  
  4298.  
  4299. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 72]
  4300.  
  4301.  
  4302.  
  4303.  
  4304.  
  4305. Internet Draft          PIM-SM Specification              March 1997
  4306.  
  4307.  
  4308.      6.2 Appendix II: BSR Election and RP-Set Distribution
  4309.  
  4310.     For simplicity,    the bootstrap message is used in  both    the  BSR
  4311.     election   and     the   RP-Set    distribution  mechanisms.  These
  4312.     mechanisms  are     described  by    the  following    state    machine,
  4313.     illustrated   in  figure  4.  The  protocol  transitions  for  a
  4314.     Candidate-BSR are given    in state diagram (a).  For  routers  not
  4315.     configured as Candidate-BSRs, the protocol transitions are given
  4316.     in state diagram (b).
  4317.  
  4318.  
  4319.  
  4320.  
  4321.  
  4322.  
  4323.  
  4324.  
  4325.      [Figures are present only in the postscript version]
  4326.      Fig. 4     State Diagram for the BSR election and    RP-Set distribution
  4327.  
  4328.  
  4329.  
  4330.     Each  PIM  router  keeps  a  bootstrap-timer,    initialized   to
  4331.     [Bootstrap-Timeout],   in  addition  to     a  local  BSR    field
  4332.     `LclBSR' (initialized to a local address if  Candidate-BSR,  or
  4333.     to  0  otherwise),  and    a local    RP-Set `LclRP-Set' (initially
  4334.     empty).    The main stimuli to the    state machine are  timer  events
  4335.     and arrival of bootstrap messages:
  4336.  
  4337.  
  4338.  
  4339.  
  4340.  
  4341.  
  4342.  
  4343.  
  4344.  
  4345.  
  4346.  
  4347.  
  4348.  
  4349.  
  4350.  
  4351.  
  4352.  
  4353.  
  4354.  
  4355.  
  4356.  
  4357.  
  4358.  
  4359. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 73]
  4360.  
  4361.  
  4362.  
  4363.  
  4364.  
  4365. Internet Draft          PIM-SM Specification              March 1997
  4366.  
  4367.  
  4368.     bsubsection*Initial States and Timer Events
  4369.  
  4370.  
  4371.  
  4372.     1
  4373.  
  4374.     2    If    the router is a    Candidate-BSR:
  4375.  
  4376.  
  4377.          1
  4378.  
  4379.          2      The router operates initially    in the `CandBSR'  state,
  4380.           where    it does    not originate any bootstrap messages.
  4381.  
  4382.          3      If the bootstrap-timer expires, and the current  state
  4383.           is   `CandBSR',  the    router    originates  a  bootstrap
  4384.           message carrying the local  RP-Set  and  its    own  BSR
  4385.           priority  and    address, restarts the bootstrap-timer at
  4386.           [Bootstrap-Period]  seconds,    and  transits  into  the
  4387.           `ElectedBSR'    state.    Note  that the actual sending of
  4388.           the bootstrap    message    may be delayed by a random value
  4389.           to  reduce  transient    control    overhead. To obtain best
  4390.           results,  the     random     value    is  set     such  that  the
  4391.           preferred  BSR  is  the first    to originate a bootstrap
  4392.           message. We propose  the  following  as  an  efficient
  4393.           implementation of the    random value delay (in seconds):
  4394.  
  4395.        Delay = 5 + 2 * log_2(1 + bestPriority - myPriority)    + AddrDelay
  4396.  
  4397.           where     myPriority is the Candidate-BSR's
  4398.           configured priority, and  bestPriority equals:
  4399.  
  4400.           bestPriority = Max(storedPriority, myPriority) ]
  4401.  
  4402.           and  AddrDelay is given by the following:
  4403.  
  4404.  
  4405.           1    if  (  bestPriority  equals    myPriority)   then
  4406.                [AddrDelay = log_2(bestAddr - myAddr) / 16, ]
  4407.  
  4408.           2    else [AddrDelay = 2 - (myAddr / 2^31) ]
  4409.  
  4410.           where     myAddr     is  the  Candidate-BSR's  address,  and
  4411.           bestAddr is the stored BSR's address.
  4412.  
  4413.  
  4414.          4      If the bootstrap-timer expires, and the current  state
  4415.           is  `ElectedBSR',  the  router  originates a bootstrap
  4416.           message, and restarts    the RP-Set timer at  [Bootstrap-
  4417.           Period]. No state transition is incurred.
  4418.  
  4419.  
  4420.  
  4421.  
  4422. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 74]
  4423.  
  4424.  
  4425.  
  4426.  
  4427.  
  4428. Internet Draft          PIM-SM Specification              March 1997
  4429.  
  4430.  
  4431.           This    way,  the  elected   BSR   originates    periodic
  4432.           bootstrap messages every [Bootstrap-Period].
  4433.  
  4434.  
  4435.  
  4436.     3    If    a router is not    a Candidate-BSR:
  4437.  
  4438.  
  4439.          1
  4440.  
  4441.          2      The router operates initially    in the `AxptAny'  state.
  4442.           In  such  state,  a router accepts the first bootstrap
  4443.           message from the The    Reverse     Path  Forwarding  (RPF)
  4444.           neighbor  toward the included    BSR. The RPF neighbor in
  4445.           this case is the next     hop  router  en  route     to  the
  4446.           included BSR.
  4447.  
  4448.  
  4449.          3      If the bootstrap-timer expires, and the current  state
  4450.           is   `AxptPref'--   where   the  router  accepts  only
  4451.           preferred bootstrap messages (those  that  carry  BSR-
  4452.           priority  and     address  higher  than,     or  equal to,
  4453.           `LclBSR') from the RPF neighbor toward  the  included
  4454.           BSR--    the router transits into the `AxptAny' state.
  4455.  
  4456.           In this case,    if an elected BSR  becomes  unreachable,
  4457.           the  routers    start  accepting bootstrap messages from
  4458.           another  Candidate-BSR   after   the     bootstrap-timer
  4459.           expires.  All     PIM routers within a domain converge on
  4460.           the preferred    reachable Candidate-BSR.
  4461.  
  4462.  
  4463.  
  4464.     Receiving Bootstrap Message:
  4465.  
  4466.     To avoid loops,    an RPF check is    performed on  the  included  BSR
  4467.     address.  Upon    receiving  a  bootstrap     message  from    the  RPF
  4468.     neighbor toward    the included  BSR,  the     following  actions  are
  4469.     taken:
  4470.  
  4471.     1    If    the router is not a Candidate-BSR:
  4472.  
  4473.  
  4474.  
  4475.  
  4476. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 75]
  4477.  
  4478.  
  4479.  
  4480.  
  4481.  
  4482. Internet Draft          PIM-SM Specification              March 1997
  4483.  
  4484.  
  4485.          1      If the current state is `AxptAny', the router     accepts
  4486.           the    bootstrap   message,   and   transits  into  the
  4487.           `AxptPref' state.
  4488.  
  4489.          2      If the current state is `AxptPref', and the  bootstrap
  4490.           message  is  preferred,  the    message     is accepted. No
  4491.           state    transition is incurred.
  4492.  
  4493.  
  4494.  
  4495.     2    If    the router is a    Candidate-BSR, and the bootstrap message
  4496.          is     preferred,  the  message  is accepted.    Further, if this
  4497.          happens when the current state is `Elected    BSR', the router
  4498.          transits into the `CandBSR' state.
  4499.  
  4500.  
  4501.     When a bootstrap message is accepted, the  router  restarts  the
  4502.     bootstrap-timer     at [Bootstrap-Timeout], stores    the received BSR
  4503.     priority and address in    `LclBSR', and the received RP-Set  in
  4504.     `LclRP-Set',  and  forwards  the  bootstrap  message out all
  4505.     interfaces except the receiving    interface.
  4506.  
  4507.     If a bootstrap message is rejected,  no     state    transitions  are
  4508.     triggered.
  4509.  
  4510.  
  4511.  
  4512.  
  4513.  
  4514.  
  4515.  
  4516.  
  4517.  
  4518.  
  4519.  
  4520.  
  4521.  
  4522.  
  4523.  
  4524.  
  4525.  
  4526.  
  4527.  
  4528.  
  4529.  
  4530.  
  4531.  
  4532.  
  4533.  
  4534.  
  4535.  
  4536. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 76]
  4537.  
  4538.  
  4539.  
  4540.  
  4541.  
  4542. Internet Draft          PIM-SM Specification              March 1997
  4543.  
  4544.  
  4545.      6.3 Appendix III: Glossary    of Terms
  4546.  
  4547.     Following is an    alphabetized list of terms and definitions  used
  4548.     throughout this    specification.
  4549.  
  4550.  
  4551.     *    { Bootstrap router    (BSR)}.    A BSR is a  dynamically     elected
  4552.          router   within   a  PIM  domain.    It  is    responsible  for
  4553.          constructing the RP-Set and originating Bootstrap messages.
  4554.  
  4555.  
  4556.     *    { Candidate-BSR (C-BSR)}. A C-BSR is a router configured to
  4557.          participate in the    BSR election and act as    BSRs if    elected.
  4558.  
  4559.  
  4560.     *    { Candidate RP (C-RP)}. A C-RP is a  router  configured  to
  4561.          send  periodic  Candidate-RP-Advertisement     messages to the
  4562.          BSR, and act as  an  RP  when  it    receives  Join/Prune  or
  4563.          Register messages for the advertised group    prefix.
  4564.  
  4565.  
  4566.     *    { Designated Router (DR)}.    The DR sets up    multicast  route
  4567.          entries  and  sends  corresponding     Join/Prune and    Register
  4568.          messages on  behalf  of  directly-connected  receivers  and
  4569.          sources,  respectively.  The  DR may or may not be    the same
  4570.          router as the IGMP    Querier. The DR    may or may  not     be  the
  4571.          long-term,     last-hop  router for the group; a router on the
  4572.          LAN that has a lower metric route to the data source, or to
  4573.          the   group's  RP,     may  take  over  the  role  of     sending
  4574.          Join/Prune    messages.
  4575.  
  4576.  
  4577.     *    { Incoming    interface (iif)}. The iif of a    multicast  route
  4578.          entry  indicates  the  interface  from which multicast data
  4579.          packets are accepted for forwarding. The iif is initialized
  4580.          when the entry is created.
  4581.  
  4582.  
  4583.     *     Join list. The Join list is one of two lists of  addresses
  4584.          that  is  included     in  a    Join/Prune message; each address
  4585.          refers to a source    or RP. It indicates those sources or RPs
  4586.          to    which downstream receiver(s) wish to join.
  4587.  
  4588.  
  4589.     *    { Last-hop    router}. The last-hop router is    the last  router
  4590.          to    receive    multicast data packets before they are delivered
  4591.          to    directly-connected member hosts. In general the    last-hop
  4592.          router  is     the  DR  for  the  LAN.  However, under various
  4593.  
  4594.  
  4595.  
  4596. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 77]
  4597.  
  4598.  
  4599.  
  4600.  
  4601.  
  4602. Internet Draft          PIM-SM Specification              March 1997
  4603.  
  4604.  
  4605.          conditions    described in this  document  a    parallel  router
  4606.          connected    to  the     same  LAN may take over as the    last-hop
  4607.          router in place of    the DR.
  4608.  
  4609.  
  4610.     *    { Outgoing    interface  (oif)  list}.  Each    multicast  route
  4611.          entry has an oif list containing the outgoing interfaces to
  4612.          which multicast packets should be forwarded.
  4613.  
  4614.  
  4615.     *     Prune List. The Prune list is the    second list of addresses
  4616.          that  is  included     in  a    Join/Prune message. It indicates
  4617.          those sources or RPs from which downstream    receiver(s) wish
  4618.          to    prune.
  4619.  
  4620.  
  4621.     *    { PIM Multicast Border Router (PMBR)}. A  PMBR  connects  a
  4622.          PIM domain    to other multicast routing domain(s).
  4623.  
  4624.  
  4625.     *    { Rendezvous  Point  (RP)}.  Each    multicast  group  has  a
  4626.          shared-tree via which receivers hear of new sources and new
  4627.          receivers hear of all sources. The    RP is the root    of  this
  4628.          per-group shared tree, called the RP-Tree.
  4629.  
  4630.  
  4631.     *    { RP-Set}.    The RP-Set is a    set of RP addresses  constructed
  4632.          by     the  BSR based    on Candidate-RP    advertisements received.
  4633.          The RP-Set    information is distributed to all PIM routers in
  4634.          the BSR's PIM domain.
  4635.  
  4636.  
  4637.     *    { Reverse Path Forwarding (RPF)}. RPF is used to select the
  4638.          appropriate  incoming interface for a multicast route entry
  4639.          . The RPF neighbor    for an address X  is  the  the    next-hop
  4640.          router  used to forward packets toward X. The RPF interface
  4641.          is    the interface to that RPF neighbor. In the  common  case
  4642.          this  is  the next    hop used by the    unicast    routing    protocol
  4643.          for sending unicast packets toward    X. For example,    in cases
  4644.          where  unicast  and  multicast routes are not congruent, it
  4645.          can be different.
  4646.  
  4647.  
  4648.     *    { Route entry.} A multicast route entry is    state maintained
  4649.          in    a router along the distribution    tree and is created, and
  4650.          updated based on incoming control messages. The route entry
  4651.          may  be  different    from the forwarding entry; the latter is
  4652.          used to forward data packets  in  real  time.  Typically  a
  4653.  
  4654.  
  4655.  
  4656. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei[Page 78]
  4657.  
  4658.  
  4659.  
  4660.  
  4661.  
  4662. Internet Draft          PIM-SM Specification              March 1997
  4663.  
  4664.  
  4665.          forwarding     entry is not created until data packets arrive,
  4666.          the forwarding entry's iif    and oif    list are copied    from the
  4667.          route  entry,  and     the forwarding    entry may be flushed and
  4668.          recreated at will.
  4669.  
  4670.  
  4671.     *    { Shortest    path tree  (SPT)}.  The     SPT  is  the  multicast
  4672.          distribution  tree     created  by  the  merger  of all of the
  4673.          shortest paths that connect receivers  to    the  source  (as
  4674.          determined    by unicast routing).
  4675.  
  4676.  
  4677.     *    { Sparse Mode (SM)}. SM is     one  mode  of    operation  of  a
  4678.          multicast     protocol.   PIM  SM  uses  explicit  Join/Prune
  4679.          messages and Rendezvous points in place of    Dense Mode PIM's
  4680.          and DVMRP's broadcast and prune mechanism.
  4681.  
  4682.  
  4683.     *    { Wildcard    (WC) multicast route entry}. Wildcard  multicast
  4684.          route entries are those entries that may be used to forward
  4685.          packets for any source  sending  to  the  specified  group.
  4686.          Wildcard  bots  in     the  join  list of a Join/Prune message
  4687.          represent either a    (*,G) or (*,*,RP)  join;  in  the  prune
  4688.          list they represent a (*,G) prune.
  4689.  
  4690.  
  4691.     *    { (S,G) route entry}.  (S,G)  is  a  source-specific  route
  4692.          entry.  It     may  be  created  in  response    to data    packets,
  4693.          Join/Prune    messages, or Asserts. The (S,G)    state in routers
  4694.          creates a source-rooted, shortest path (or    reverse    shortest
  4695.          path) distribution    tree. (S,G)RPT bit entries  are     source-
  4696.          specific  entries    on the shared RP-Tree; these entries are
  4697.          used to prune particular sources off of the shared    tree.
  4698.  
  4699.  
  4700.     *    { (*,G) route entry}. Group members join the shared RP-Tree
  4701.          for  a  particular    group. This tree is represented    by (*,G)
  4702.          multicast route entries along the    shortest  path    branches
  4703.          between the RP and    the group members.
  4704.  
  4705.  
  4706.     *    { (*,*,RP)    route entry}. (*,*,RP) refers to any source  and
  4707.          any  multicast  group  that  maps to the RP included in the
  4708.          entry. The    routers    along the shortest path    branches between
  4709.          a    domain's RP(s) and its PMBRs keep (*,*,RP) state and use
  4710.          it    to determine how to deliver packets toward the PMBRs  if
  4711.          data  packets arrive for which there is not a longer match.
  4712.          The  wildcard  group  in  the  (*,*,RP)  route   entry   is
  4713.  
  4714.  
  4715.  
  4716. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Weiall   [Page 79]
  4717.  
  4718.  
  4719.  
  4720.  
  4721.  
  4722. Internet Draft          PIM-SM Specification              March 1997
  4723.  
  4724.  
  4725.          represented  by  a     group    address     of 224.0.0.0 and a mask
  4726.          length of 4 bits.
  4727.  
  4728.  
  4729.  
  4730.  
  4731.  
  4732.  
  4733.  
  4734.  
  4735.  
  4736.     References
  4737.  
  4738.  
  4739.    1.    S.Deering,  D.Estrin,  D.Farinacci,  V.Jacobson,  C.Liu,  L.Wei,
  4740.     P.Sharma,  and    A.Helmy.  Protocol independent multicast (pim) :
  4741.     Motivation and architecture.
  4742.      Internet Draft, May 1995.
  4743.  
  4744.  
  4745.    2.    S.Deering, D.Estrin, D.Farinacci, V.Jacobson, C.Liu, and  L.Wei.
  4746.     The pim    architecture for wide-area multicast routing.
  4747.      ACM Transactions on Networks, April 1996.
  4748.  
  4749.  
  4750.    3.    D.Estrin, D.Farinacci, V.Jacobson, C.Liu, L.Wei,  P.Sharma,  and
  4751.     A.Helmy.  Protocol  independent     multicast-dense mode (pim-dm) :
  4752.     Protocol specification.     Internet Draft, November 1995.
  4753.  
  4754.  
  4755.    4.    S.Deering.  Host  extensions  for  ip  multicasting,  aug  1989.
  4756.     RFC1112.
  4757.  
  4758.  
  4759.    5.    W.Fenner. Internet group management protocol, version 2.
  4760.      Internet Draft, May 1996.
  4761.  
  4762.  
  4763.    6.    R.Atkinson. Security architecture  for    the  internet  protocol,
  4764.     August 1995. RFC-1825.
  4765.  
  4766.  
  4767.    7.    MarkR.    Nelson.     File  verification  using  CRC.  Dr.  Dobb's
  4768.     Journal, May 1992.
  4769.  
  4770.  
  4771.    8.    A.J. Ballardie,    P.F. Francis, and J.Crowcroft. Core based trees.
  4772.     In  Proceedings    of the ACM SIGCOMM, San    Francisco, 1993.
  4773.  
  4774.  
  4775.  
  4776. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei  [Page 80]
  4777.  
  4778.  
  4779. Addresses of Authors:
  4780.  
  4781. Deborah    Estrin
  4782. Computer Science Dept/ISI
  4783. University of Southern Calif.
  4784. Los Angeles, CA    90089
  4785. estrin@usc.edu
  4786.  
  4787. Dino Farinacci
  4788. Cisco Systems Inc.
  4789. 170 West Tasman    Drive,
  4790. San Jose, CA 95134
  4791. dino@cisco.com
  4792.  
  4793. Ahmed Helmy
  4794. Computer Science Dept.
  4795. University of Southern Calif.
  4796. Los Angeles, CA    90089
  4797. ahelmy@catarina.usc.edu
  4798.  
  4799. David Thaler
  4800. EECS Department
  4801. University of Michigan
  4802. Ann Arbor, MI 48109
  4803. thalerd@eecs.umich.edu
  4804.  
  4805. Stephen    Deering
  4806. Xerox PARC
  4807. 3333 Coyote Hill Road
  4808. Palo Alto, CA 94304
  4809. deering@parc.xerox.com
  4810.  
  4811. Mark Handley
  4812. Department of Computer Science
  4813. University College London
  4814. Gower Street
  4815. London,    WC1E 6BT
  4816. UK
  4817. m.handley@cs.ucl.ac.uk
  4818.  
  4819. Van Jacobson
  4820. Lawrence Berkeley Laboratory
  4821. 1 Cyclotron Road
  4822. Berkeley, CA 94720
  4823. van@ee.lbl.gov
  4824.  
  4825. Ching-gung  Liu
  4826. Computer Science Dept.
  4827. University of Southern Calif.
  4828. Los Angeles, CA    90089
  4829. charley@catarina.usc.edu
  4830.  
  4831. Puneet Sharma
  4832. Computer Science Dept.
  4833. University of Southern Calif.
  4834. Los Angeles, CA    90089
  4835. puneet@catarina.usc.edu
  4836.  
  4837. Liming Wei
  4838. Cisco Systems Inc.
  4839. 170 West Tasman    Drive,
  4840. San Jose, CA 95134
  4841. lwei@cisco.com
  4842.  
  4843.