Network Working Group                                     Dino Farinacci
INTERNET-DRAFT                                             Greg Shepherd
Expiration Date: November 2004                          Procket Networks
                                                            May 17, 2004


                   Population Count Extensions to PIM
                 <draft-farinacci-pim-pop-count-00.txt>


Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsolete by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.


Copyright Notice

   Copyright (C) The Internet Society (2002).  All Rights Reserved.


Abstract

   Performing an approximation in some form of multicast distribution
   tree accounting proves to be useful for billing and debugging. The
   Population Count extensions to PIM, documented in this draft,
   provide an efficient method to achieve this.








Farinacci & Shepherd                                            [Page 1]


Internet Draft     Population Count Extensions to PIM           May 2004


1. Introduction

   This draft proposes a mechanism to convey accounting information
   using the PIM protocol. Putting the mechanism in PIM allows efficient
   distribution and maintenance of such accounting information. Previous
   mechanisms require data to be correlated from multiple router
   sources.

   This proposal allows a single router to be queried to obtain
   accounting and statistic information for a multicast distribution
   tree as a whole or any distribution sub-tree downstream from a
   queried router. The amount of information is fixed and does not
   increase as multicast membership, tree diameter, or branching
   increase.

   The sort of acounting data this draft provides on a per multicast
   route basis are:

      1) The number of branches in a distribution tree.
      2) The membership type of the distribution tree, that is SSM or
         ASM.
      3) Routing domain and time zone boundary information.
      4) On-tree node and tree diameter counters.
      5) Effective MTU and bandwidth speed.

   This draft adds a new Encoded-Source-Address format to the Join/Prune
   message as well as a new Hello TLV. The mechanism is applicable to
   IPv4 and IPv6 multicast.


2. Terminology

   This section defines the terms used in this draft.

   Multicast Route:
       A (S,G) or (*,G) entry regardless if the route is in ASM, SSM, or Bidir
       mode of operation.

   Stub Link:
       A link with only members joined to the group via IGMP or MLD. Which
       means there are no PIM routers joining for the multicast route on the
       link.

   Transit Link:
       A link put in the oif-list for a multicast route because it was
       joined by PIM routers only (no IGMP or MLD reports were received on
       the link).




Farinacci & Shepherd                                            [Page 2]


Internet Draft     Population Count Extensions to PIM           May 2004


   Dual Link:
       Is a link in the oif-list which is has the attributes of a Stub
       Link *and* Transit Link. That is, there are IGMP and MLD members as
       well as PIM joiners for the multicast route on the link.


3. New Hello TLV for Pop-Count Support

   When a PIM router sends a Join/Prune message to a neighbor, it will use the
   new form of the Encoded-Source-Address (described in this draft) when the
   PIM router determines the neighbor can support this draft. If a PIM router
   supports this draft, it must send the Pop-Count-Supported TLV. The format
   of the TLV is defined to be:

    0                   1                   2                   3
    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       OptionType              |         OptionLength          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          OptionValue                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   OptionType = 24, OptionLength = 8, there is no OptionValue semantics
   defined at this time but will be included for expandability and be
   defined in future revisions of tihs draft. The format will look like:

    0                   1                   2                   3
    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             24                |              8                |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Unallocated Flags                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   "Unallocated Flags": for now should be sent as 0 and ignored on
   receipt. This field could be used to enable the use of future flags
   in the "Uncallocated Flags" field of the new Encoded-Source-Address
   format defined below.













Farinacci & Shepherd                                            [Page 3]


Internet Draft     Population Count Extensions to PIM           May 2004


4. New Encoded-Source-Address Format

   When a PIM router supports this draft and has determined from a received
   Hello, the neighbor supports this draft, it will send Join/Prune messages
   with the following format:

    0                   1                   2                   3
    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Addr Family   | Encoding Type | Rsrvd   |S|W|R|  Mask Len     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Source Address                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Effective MTU   |   Unallocated Flags (Reserved)   |a|t||A|S|
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Domain Count |  Node Count   | Diameter Count|    TZ Count   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    Transit Oif-List Count     |     Stub Oif-List Count       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      Minimum Speed Link       |      Maximum Speed Link       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   The above format is used only for entries in the join-list section of the
   Join/Prune message.

   The format is identical to the format defined for the Address-Family
   indepdent Encoded-Source-Address in [1] except there are additional fields
   appended. What distinguishes the above format from the format in [1] is the
   use of a different "Encoding Type" format. If the "Encoding Type" value is
   1, the above format will be used.

   The additional fields are:

   "Effective MTU": this contains the minimum MTU for any link in the oif-list.
   The sender of Join/Prune message takes the minimum value for the MTU (in
   bytes) from each link in the oif-list. If this value is less than the value
   stored for the multicast route (the one received from downstream joiners)
   then the value should be reset and sent in Join/Prune message. Otherwise,
   the value should remain unchanged. The value is in units of 10s of bytes
   (i.e. so the value for a traditional Ethernet MTU would be 150).

   This provides one to obtain the MTU supported by any router or link for the
   multicast disribution tree when examined at the first-hop router(s) or for
   aub-tree for any router on the distribution tree.

   "Unallocated Flags": The flags which are currently not defined. If a new
   flag is defined and sent by a new implementation, an old implementation
   should preserve the bit settings.



Farinacci & Shepherd                                            [Page 4]


Internet Draft     Population Count Extensions to PIM           May 2004


   "S" flag: if an IGMPv3 or MLDv2 report was received on any oif-list entry or
   the bit was set from any PIM Join message. This bit should only be cleared
   when the above becomes untrue.

   "A" flag: if an IGMPv1, IGMPv2, or MLDv1 report was received on any
   oif-list entry or the bit was set from any PIM Join message. This bit should
   only be cleared when the above becomes untrue.

   A combination of settings for these bits indicate:

   A=0, S=0: There are no members for the group ('Stub Oif-List Count' is 0
             too).
   A=0, S=1: All group members are only SSM capable.
   A=1, S=0: All group members are only ASM capable.
   A=1, S=1: There is a mixture of SSM and ASM capable members.

   "t" flag: if thera are any tunnels on the distribution tree. If a tunnel
   is in the oif-list, a router should set this bit in it's Join/Prune
   messages. Otherwise, it propogates the bit setting from downstream joiners.

   "a" flag: if thera are any auto-tunnels on the distribution tree. If an
   auto-tunnel is in the oif-list, a router should set this bit in it's
   Join/Prune messages. Otherwise, it propogates the bit setting from
   downstream joiners.

   "Domain Count": this indicates the number of routing domains the
   distribution tree traverses. A router should should increment this value if
   it is sending a Join/Prune message over a link which traverses a domain
   boundary.

   "Node Count": This indicates the number of routers on the distribution tree.
   Each router will sum up all the Node Counts from all joiners on all oifs and
   increment by 1 before including this value in the Join/Prune message.

   "Diameter Count": this indicates the longest length of any givin branch of
   the tree in router hops. Each router that sends a Join increments the max
   value received by all dowstream joiners by 1.

   "TZ Count": this indicates the number of timezones the distribution tree
   traverses. A router should should increment this value if it is sending
   a Join/Prune message over a link which traverses a time zone. This can be
   a confiugred link attribute or using some other means to determine the
   timzeone is acceptable.

   "Transit Oif-List Count" is filled in by a router sending a Join/Prune
   message which is equal to the number of oifs for the multicast route that
   has been joined by PIM only. This indicates the transit branches on a
   multicast distribution tree (no members on the links between this router



Farinacci & Shepherd                                            [Page 5]


Internet Draft     Population Count Extensions to PIM           May 2004


   and joing routers). This is added to the value advertised by all downstream
   PIM routers that have joined on this oif.

   "Stub Oif-List Count" is filled in by a router sending a Join/Prune
   message which is equal to the number of oifs for the multicast route that
   has been joined only by IGMP or MLD. This indicates the links where there
   are host members for the multicast route. This is added to the value
   advertised by all downstream PIM routers that have joined on this oif.

   "Minimum Speed Link": this contains the minimum bandwidth rate (in
   mbps) for any link in the oif-list. The sender of Join/Prune message takes
   the minimum value for each link in the oif-list for the multicst route. If
   this value is less than the value stored for the multicast route (the one
   received from downstream joiners) then the value should be reset and sent in
   Join/Prune message. Otherwise, the value should remain unchanged. A value
   of 0 means the link speed is < 1 mbps.

   "Maximum Speed Link": this contains the maximum bandwidth rate (in
   mbps) for any link in the oif-list. The sender of Join/Prune message takes
   the maximum value for each link in the oif-list for the multicst route. If
   this value is greater than the value stored for the multicast route (the one
   received from downstream joiners) then the value should be reset and sent in
   Join/Prune message. Otherwise, the value should remain unchanged.  A value
   of 0 means the link speed is < 1 mbps.

   This provides one to obtain the lowest and highest speed link for the
   multicast distribution tree.


5. How to use Pop-Count Encoding

   It is very important to note that any changes to the values maintained in
   this draft *must not* trigger a new Join/Prune message. Due to the periodic
   nature of PIM, the values can be accurately obtained at 1 minute intervals
   (or whatever Join/Prune interval used).

   When a router removes a link from an oif-list, it must be able to reevalute
   the values that it will advertise upstream. This happens when an oif-list
   entry is timed out or a Prune is received.

   It is recommended that the Encoded-Source-Address defined in this draft be
   used for entries in the join-list part of the Join/Prune message. If the new
   encoding is used in the prune-list, an implementation must ignore them but
   still process the Prune as if it was in the original encoding described in
   [1].


6. Implementation Approaches



Farinacci & Shepherd                                            [Page 6]


Internet Draft     Population Count Extensions to PIM           May 2004


   An implementation can decide how the accounting attributes are
   maintained.  The values can be stored as part of the multicast route
   data structure by combining the local information it has with the
   joined information on a per oif basis. So then when it is time to
   send a Join/Prune message, the values stored in the multicast route
   can be copied to the message.

   Or, an implementation could store the accounting values per oif and
   when a Join/Prune message is sent, it can combine the oifs with it's
   local information. Then the combined information can be copied to the
   message.

   When a downstream joiner stops joining accounting values cached must
   be reevaulated. There are two approaches which can be taken. One is
   to keep values learned from each joiner so when the joiner goes away
   the count/max/ min values are known and the combined value can be
   adjusted. The other approach is to set the value to 0 for the oif,
   and then start accumulating new values as subsequent Joins are
   received.

   The same issue arises when an oif is removed from the oif-list.
   Keeping per- oif values allows you to adjust the per-route values
   when an oif goes away.  Or, alternatively, a delay for reporting the
   new set a values from the route can occur while all oif values are
   zeroed (where accumulation of new values from subsequent Joins cause
   repopulation of values and a new max/min/ count can be reevalutatd
   for the route).


7. Caveats

   This draft requires each router on a multicast distribution tree to
   support this draft or else the accouting attributes for the tree will
   not be known.

   However, if there are a contiguous set of routers downstream in the
   distribution tree, they can maintain accounting information for the
   sub-tree.

   If there are a set of contiguous routers supporting this draft
   upstream on the multicast distribution tree, accounting information
   will be available but it will not represent an accurate assessment of
   the entire tree. Also, it will not be clear for how much of the
   distribution tree the accounting information covers.







Farinacci & Shepherd                                            [Page 7]


Internet Draft     Population Count Extensions to PIM           May 2004


8. Acknowledgments

   The authors would like to thank John Zwiebel, Amit Jain, and Clayton
   Wagar of Procket Networks for their review comments on the initial
   versions of this draft.


9. Author Information

   Dino Farinacci
   Procket Networks
   dino@procket.com

   Greg Shepherd
   Procket Networks
   shep@shepfarm.com



10. References

   [1] Estrin, et al., "Protocol Independent Multicast-Sparse Mode (PIM-
       SM): Protocol Specification", RFC 2362, June 1998.

   [2] Fenner, et al., "Protocol Independent Multicast-Sparse Mode (PIM-
       SM): Protocol Specification", Internet Draft, draft-ietf-pim-sm-v2-
       new-08.txt, October 2003.
























Farinacci & Shepherd                                            [Page 8]