Small Group Multicast
draft-boivie-sgm-02

Versions: 00 01 02                                                      
IETF Draft                Small Group Multicast            March 2000




Internet Draft                                            Rick Boivie
Expires: September 2000                                 Nancy Feldman
                                           IBM Watson Research Center

                                                           March 2000



                        Small Group Multicast
                      <draft-boivie-sgm-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 obsoleted 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.


Abstract

   Multicast has become increasingly important with the emergence of
   network-based applications such as IP telephony and video
   conferencing. The Internet community has done a significant amount
   of work on IP multicast over the last decade [1-10] and as a
   result, there are a number of multicast applications that are used
   today on the Mbone, the multicast-capable virtual network that is
   layered on top of (portions of) the Internet [10]. However, while
   today's multicast schemes are scaleable in the sense that they can
   support very large multicast groups, there are scalability issues
   when a network needs to support a very large number of distinct
   multicast groups. This document describes a new scheme for
   multicast that complements the existing schemes. Whereas the
   existing schemes can support a limited number of very large



Boivie et al.             Expires September 2000              [Page 1]


IETF Draft                Small Group Multicast            March 2000



   multicast groups, the scheme described here can support a very
   large number of small multicast groups.


1.   Introduction

   Multicast, the ability to efficiently send data to a group of
   destinations, is becoming increasingly important for applications
   such as IP telephony, video-conferencing, video distribution,
   collaborative work environments, multiparty networked games, etc.

   There seem to be two kinds of multicasts that are important: a
   broadcast-like multicast that sends data to a very large number of
   destinations and a "narrowcast" multicast that sends data to a
   fairly small group. An example of the first is the audio & video
   multicasting of a working group session from an IETF meeting to
   sites all around the world. An example of the second is a
   videoconference involving 3 or 4 parties. For reasons described
   below, it seems prudent to use different mechanisms for these two
   cases. As the reliable multicast transport group has stated: "it
   is believed that a 'one size fits all' protocol will be unable to
   meet the requirements of all applications" [11].

1.1. Current Multicast Schemes

   Current multicast schemes [1,3,4,6,8] were designed to handle very
   large multicast groups. These work well if one is trying to
   distribute broadcast-like channels all around the world but they
   have scalability problems when there is a very large number of
   groups.

   In some of these schemes, the nodes in the network build a
   multicast distribution tree for each <source, multicast group>
   pair and they disseminate this multicast routing information to
   places where it isn't necessarily needed, which leads to scaling
   problems if there are a large number of multicast groups.

   Some other schemes try to limit the amount of multicast routing
   information that needs to be disseminated, processed and stored
   throughout the network. These schemes use a "shared distribution
   tree" that is shared by all the members of a multicast group and
   they try to limit the distribution of multicast routing
   information to just those nodes that "really need it". But these
   schemes also have problems. Because of the shared tree, they use
   less than optimal paths in routing packets to their destinations
   and they tend to concentrate traffic in small portions of a
   network. They also require that all of the routers in a multicast
   tree "signal", process and store multicast routing information.
   And they require that multicast routing information for the
   various multicast groups be communicated across inter-AS



Boivie et al.             Expires September 2000              [Page 2]


IETF Draft                Small Group Multicast            March 2000



   administrative boundaries. These requirements cause scalability
   problems and increase administrative complexity if there are a
   large number of multicast groups.


2.   Small Group Multicast (SGM)

2.1. Overview

   The "Small Group Multicast" (SGM) scheme described here attempts
   to eliminate these problems for the case of small groups. In SGM,
   the source node keep track of the destinations that it wants to
   send packets to, and creates packet headers that contain the list
   of destination addresses. SGM-capable routers receive these
   packets, parse the SGM headers and use the ordinary unicast route
   table to determine how to route the packet to each destination.
   This eliminates the need for network routers to store any state
   for the various multicast groups. This makes SGM very scaleable in
   terms of the number of groups that can be supported since the
   nodes in the network do not need to disseminate or store any
   multicast routing information for these groups. And since it
   doesn't use any multicast routing protocol, there are no inter-AS
   multicast routing "peering" issues to contend with. SGM has the
   additional benefit that packets always take the "right" path as
   determined by the ordinary unicast route protocols. Unlike the
   shared tree schemes, SGM minimizes network latency and maximizes
   network "efficiency". This removes some important obstacles that
   have, to this point, prevented the widespread acceptance and
   adoption of multicast. Thus, SGM makes multicast practical for
   very large numbers of small groups, which as suggested above is a
   very important case. Note that while SGM is not suitable for large
   multicast groups, such as the broadcast of an IETF meeting, it
   does provide an important complement to existing multicast schemes
   in that it can support very large numbers of small groups.

   SGM takes advantage of one of the fundamental tenets of the
   Internet "philosophy", namely that one should move complexity to
   the edges of the network and keep the middle of the network
   simple. This is the principle that guided the design of IP and TCP
   and it's the principle that has made the incredible growth of the
   Internet possible. For example, one reason that the Internet has
   been able to scale so well is that the routers in the core of the
   network deal with large CIDR blocks as opposed to individual hosts
   or individual "connections". The routers in the core don't need to
   keep track of the individual TCP connections that are passing
   through them. Similarly, the IETF's diffserv effort is based on
   the idea that the routers shouldn't have to keep track of a large
   number of individual RSVP flows that might be passing through
   them. It's the authors' belief that the routers in the core
   shouldn't have to keep track of a large number of individual



Boivie et al.             Expires September 2000              [Page 3]


IETF Draft                Small Group Multicast            March 2000



   multicast flows either.

2.2. Mechanism

   In Small Group Multicast, the source node keeps track of the
   destinations that it wants to send packets to. The source encodes
   the list of destinations in an SGM header that follows the L3
   header, and then sends the packet to a router. Each router along
   the way parses the SGM header, partitions the destinations based
   on each destination's next hop, and forwards an appropriate SGM
   packet to each of the next hops. Each "final" hop removes the SGM
   encoding, and forwards the data as a standard unicast packet to
   its destination.

   Note that in the case of IP, the destination may be an IP-
   destination/UDP-port pair. Since a destination will always receive
   an ordinary unicast packet, it can receive an SGM multicast
   transmission with a standard TCP/IP stack. Source nodes can also
   use standard TCP/IP stacks as long as raw sockets are supported
   (in which case SGM packets can be sent over a raw socket).

   For example, suppose that A is trying to get packets distributed
   to B, C & D in figure 1 below:


                                R4 ---- B
                               /
                              /
    A ----- R1 ---- R2 ---- R3                      R8 ---- C
                              \                    /
                               \                  /
                                R5 ---- R6 ---- R7
                                                 \
                                                  \
                                                    R9 ---- D
                              Figure 1

   This is accomplished as follows: A sends an SGM packet to its
   default router, R1, that includes the list of destinations for the
   packet. Ignoring some details, the packet that A sends to R1 might
   look like this:

   Level 3 header:
     < dest = R1 >
     < src = A >
     < protocol = small group multicast >  (new protocol type)

   Level "3.5" header:
     < dest = B C D >
     < src = A >



Boivie et al.             Expires September 2000              [Page 4]


IETF Draft                Small Group Multicast            March 2000




   followed by the payload that A wants delivered to B, C and D.

   (Note that the SGM layer is said to be at "level 3.5" since it's
   between IP and UDP in the protocol stack. SGM uses IP and is
   carried within an IP datagram and it's used by UDP and carries a
   UDP payload.)

   When R1 receives this packet, it needs to properly process the SGM
   header. The processing that a router does on receiving one of
   these small group multicast packets is as follows:

     o Perform a route table lookup to determine the next hop for each
       of the destinations listed in the packet.
     o Partition the set of destinations based on their next hops.
     o Replicate the packet so that there's one copy of the packet for
       each of the next hops found in the previous steps.
     o Modify the list of destinations in each of the copies so that
       the list in the copy for a given next hop includes just the
       destinations that ought to be routed through that next hop.
     o Send the modified copies of the packet on to the next hops.
     o Optimization: If there is only one destination for a particular
       next hop, send the packet as a standard unicast packet to the
       destination, as there is no multicast gain by formatting it as an SGM
       packet.

   So, in the example above, R1 will send a single packet on to R2
   with a destination list of < B C D > and R2 will send a single
   packet to R3 with the same destination list.

   When R3 receives the packet, it will, by the algorithm above, send
   one copy of the packet to destination R5 with an SGM list of < C D
   >, and one ordinary unicast packet addressed to < B >. R4 will
   receive a standard unicast packet and forward it on to < B >. R5
   will forward the SGM packet that it receives on to R6 which will
   pass it on to R7. When the packet reaches R7, R7 will transmit
   ordinary unicast packets addressed to < C > and < D >
   respectively. R8 and R9 will receive standard unicast packets, and
   forward the packets on to < C > and < D > respectively.

   It's important that the SGM packet that is sent to a given next
   hop only includes destinations for which that next hop is the next
   hop listed in the route table. If the list of destinations in the
   packet sent to R4, for example, had also included C and D, R4
   would send extra packets on to those nodes on a less than optimum
   path. This could waste a lot of bandwidth if one is, for example,
   multicasting a videoconference. And this could cause serious
   problems when route loops occur since a multicast packet could
   "spray" large numbers of packets in a number of different
   directions as it travels around a loop. Since the SGM packet that



Boivie et al.             Expires September 2000              [Page 5]


IETF Draft                Small Group Multicast            March 2000



   is sent to a given next hop only includes the destinations that
   are supposed to be reached through that next hop, these problems
   are eliminated.

   Note that when routing topology changes, the routing for a
   multicast flow will automatically adapt to the new topology since
   the path a multicast packet takes to a given destination always
   follows the ordinary, unicast routing for that destination.

   Note also that since the SGM header is added to the data portion
   of the packet, if the sender wishes to avoid IP fragmentation, it
   must take the size of the SGM header into account.

   See Appendix A.1 for the standard SGM encoding formats.


3.   Interoperability with Today's Routers

   In the description above all of the routers in the network were
   "SGM-capable". But the scheme can also be used in an environment
   that includes routers that have no knowledge of SGM. This is
   important since it allows SGM to be used without upgrading all the
   routers in a network. There are two methods that can be used: the
   first uses SGM "tunnels"; the second icmp unreachable messages.

3.1. SGM Tunnels

   One way to deploy SGM in a network that has routers that have no
   knowledge of SGM is to setup "tunnels" between SGM peers. This
   enables the creation of a virtual network layered on top of an
   existing network. The SGM routers exchange and maintain SGM
   routing information via any standard unicast routing protocol
   (e.g. RIP, OSPF, ISIS). The SGM routing table that is created is
   simply a standard unicast routing table that contains the
   destinations that have SGM connectivity, along with their
   corresponding SGM next hops. In this way, packets may be forwarded
   hop-by-hop to other SGM routers, or may be "tunneled" through non-
   SGM routers in the network.

   For example, suppose that A is trying to get packets distributed
   to B, C & D in figure 2 below, where "S" routers are SGM-capable,
   and "R" routers are not. Figure 3 shows the routing tables created
   via the SGM tunnels:











Boivie et al.             Expires September 2000              [Page 6]


IETF Draft                Small Group Multicast            March 2000



                                R4 ---- B
                               /
                              /
    A ----- S1 ---- R2 ---- S3                      R8 ---- C
                              \                    /
                               \                  /
                                R5 ---- R6 ---- S7
                                                 \
                                                  \
                                                    R9 ---- D
                              Figure 2


   Router S1 establishes a tunnel to SGM peer S3.
   Router S3 establishes a tunnel to SGM peers S1 and S7.
   Router S7 establishes a tunnel to SGM peer S3.

   S1 routing table:     S3 routing table:     S7 routing table:
    Dest |  NextHop       Dest | NextHop        Dest | NextHop
   ------+----------     ------+---------      ------+---------
     B   |   S3             A  |   S1            A   |  S3
     C   |   S3             C  |   S7            B   |  S3
     D   |   S3             D  |   S7

                            Figure 3


   The source A will send an SGM packet to its default SGM router,
   S1, that includes the list of destinations for the packet. As
   described in section 2.2, the packet that A sends to S1 might look
   like this:

   Level 3 header:
     < dest = S1 >
     < src = A >
     < protocol = small group multicast >  (new protocol type)

   Level "3.5" header:
     < dest = B C D >
     < src = A >

   followed by the payload that A wants delivered to B, C and D.

   When S1 receives this packet it needs to properly process the
   multicast. The processing that this router does on receiving one
   of these small group multicast packets is as follows:

     o Perform a route table lookup in the SGM routing table to
       determine the SGM next hop for each of the destinations listed in the
       packet.



Boivie et al.             Expires September 2000              [Page 7]


IETF Draft                Small Group Multicast            March 2000



     o If no SGM next hop is found, replicate the packet and send a
       standard unicast to the destination.
     o For those destinations for which an SGM next hop is found,
       partition destinations based on their next hops.
     o Replicate the packet so that there's one copy of the packet for
       each of the SGM next hops found in the previous steps.
     o Modify the list of destinations in each of the copies so that
       the list in the copy for a given next hop includes just the
       destinations that ought to be routed through that next hop.
     o Send the modified copies of the packet on to the next hops.
     o Optimization: If there is only one destination for a particular
       SGM next hop, send the packet as a standard unicast packet to the
       destination, as there is no multicast gain by formatting it as an
       SGM packet.

   So, in the example above, S1 will send a single packet on to S3
   with a destination list of < B C D >. This packet will be received
   by R2 as a unicast packet with destination S3, and R2 will forward
   it on, having no knowledge of SGM. When S3 receives the packet, it
   will, by the algorithm above, send one copy of the packet to
   destination < B > as an ordinary unicast packet, and 1 copy of the
   packet to S7 with a destination list of < C D >. R4, R5, and R6
   will behave as standard routers with no knowledge of SGM. When S7
   receives the packet, it will parse the packet and transmit
   ordinary unicast packets addressed to < C > and < D >
   respectively.

   By using tunnels, packets follow the "best possible" path to the
   various destinations (as determined by the unicast routing
   protocols), while at the same minimizing the total number of
   packets that must be transmitted on the network.

3.2. ICMP

   The second method for gradual deployment of SGM is based on the
   use of ICMP. In this case, forwarding follows as described in
   figure 1 (see section 2.2). However, an assumption is made that
   any router receiving an SGM packet that does not understand this
   new protocol will send an icmp message back to the source. This is
   a router requirement as specified in RFC1812, "Requirements for IP
   Version 4 Routers" [12]. Section 5.2.7.1 of RFC1812 says that a
   router should send an ICMP Destination Unreachable message with a
   code of 2, signifying Protocol Unreachable, if the transport
   protocol designated in a datagram is not supported in the
   transport layer of the final destination.

   Thus, a router that doesn't understand this new protocol should
   send an icmp "destination unreachable, protocol unreachable"
   message back to the source. (If the icmp message is lost for some
   reason, a subsequent small group multicast packet will cause



Boivie et al.             Expires September 2000              [Page 8]


IETF Draft                Small Group Multicast            March 2000



   another icmp to be sent.) This enables the source to know when a
   router doesn't understand the new protocol. Furthermore, since the
   icmp message will include the initial part of the original packet,
   the source will also know the destinations that are not reachable
   via SGM, so the source can use unicast packets to reach those
   destinations. When routing topology changes, additional icmp
   "destination unreachable, protocol unreachable" messages may be
   generated and the source may use unicasts for additional
   destinations. The source can also periodically send an SGM packet
   to the destinations that are on its "unicast list" i.e. the list
   of nodes that it is reaching via unicast. Destinations that become
   reachable via SGM (i.e. those do not appear in subsequent icmp
   "destination unreachable, protocol unreachable" messages) can then
   be removed from the unicast list. (Note that another possibility
   would be to send an SGM "ping" periodically to the set of
   destinations and then use unicast to reach those destinations that
   don't respond to the ping).

   Thus, Small Group Multicast can perform some multicasting in an
   environment that includes "legacy" routers which do not understand
   SGM. It won't work particularly well if there are many routers
   that don't understand SGM but this backwards compatibility may be
   important since it makes some of the benefits of multicast
   possible before all the routers in a network have been upgraded.
   This can be very useful since it may take some time to upgrade all
   the routers in a large network.

   See Appendix A.2 for the encoding required of packets which may be
   returned via ICMP.


4.   Summary

   In summary, the disadvantages of Small Group Multicast are:
     o the extra bytes that are sent in a multicast packet for the list
       of destinations.
     o the need to use unicast packets in some cases to reach
       destinations that are behind "legacy" routers.
     o the need for a new IP stack in hosts (unless raw sockets are
       available in which case SGM packets can be sent over a raw socket).
     o the fact that SGM is not suitable for huge broadcast-like
       multicasts. It's targeted for "small" conferences.

   The key advantages are:
     o it's very scaleable; it can handle a very large number of small
       groups.
     o the work involved is limited to just the nodes that are on the
       multicast tree.
     o no per flow state information is stored on the routers.
     o no multicast route protocol messages are communicated or



Boivie et al.             Expires September 2000              [Page 9]


IETF Draft                Small Group Multicast            March 2000



       processed; no intra-AS or inter-AS route protocols.
     o minimum administrative complexity; no need for complicated inter-
       AS peering agreements; it's just as easy for a network administrator
       to support multicast as it is to support unicast, and it will be just
       as easy to support multicast across the Internet as it is to support
       unicast.
     o traffic follows the correct paths; traffic is not concentrated
       in a small part of the network; minimum network latency; maximum
       network "efficiency".
     o no need for class D addresses which means:
       -  no need for a server that hands out class D addresses which can
          be a bottleneck or a point of failure.
       -  no one can join the class D group and "eavesdrop" on the class D
          address; the source knows who he's sending to.
     o SGM can be easily adapted to provide a "reliable multicast".

   The advantages of Small Group Multicast suggest that this scheme
   can be a very useful complement to the existing multicast schemes.
   Whereas the existing schemes can support a limited number of very
   large multicast groups, SGM can support a huge number (i.e.
   virtually an unlimited number) of small multicast groups and thus
   can play an important role in supporting applications such as
   conferencing applications on the Internet.


5.   Security Considerations

   An "eavesdropper" cannot join a multicast "group", as the source
   controls the  membership of the multicast transmissions. Also,
   there is no need for a server to hand out class D addresses which
   could be subject to "denial of service" or other forms of attack.

   Further security considerations will be addressed in a future
   document.


6.   Acknowledgements

   The authors would like to thank Brian Carpenter, chairman of the
   Internet Architecture Board, for several discussions and for his
   feedback and ideas on the "Small Group Multicast" scheme. The
   authors would also like to thank Joe Mambretti and Ralph Demuth of
   iCAIR, as well as Micah Beck and Bert Dempsey, co-leads of the
   Internet2 Distributed Storage Infrastructure Initiative, for their
   support in deploying SGM in the Internet2 environment.


7.   References

   [1] RFC 1075, Distance Vector Multicast Routing Protocol, D.



Boivie et al.             Expires September 2000             [Page 10]


IETF Draft                Small Group Multicast            March 2000



   Waitzman, C. Partridge, S.E. Deering, Nov. 1988

   [2] S.E. Deering. Multicast Routing in a Datagram Internetwork.
   PhD thesis, Electrical Engineering  Dept., Stanford University,
   Dec. 1991

   [3] RFC 1584, Multicast Extensions to OSPF, J. Moy, March 1994

   [4] S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, and
   L. Wei.  The Pim Architecture for Wide-area Multicast Routing, ACM
   Transactions on Networks, April 1996

   [5] RFC 2189, Core Based Trees (CBT version 2) Multicast Routing
   Protocol Specification, A. Ballardie, Sept., 1997

   [6] RFC 2201, Core Based Trees (CBT) Multicast Routing
   Architecture, A. Ballardie, Sept. 1997

   [7] RFC 2236, Internet Group Management Protocol, Version 2, W.
   Fenner, Nov. 1997

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

   [9] D. Estrin, D. Farinacci, V. Jacobson, C. Liu, L. Wei, P.
   Sharma, and A. Helmy, "Protocol Independent Multicast-dense Mode
   (pim-dm): Protocol Specification", Work in Progress.

   [10] Frequently Asked Questions (FAQ) on the Multicast Backbone
   (MBONE), ftp://venera.isi.edu/mbone/faq.txt

   [11] Reliable Multicast Transport Working Group web site,
   http://www.ietf.org/html.charters/rmt-charter.html, June 15, 1999

   [12] RFC 1812, Requirements for IP Version 4 Routers, F. Baker,
   June 1995


8.   Authors

   Rick Boivie
   IBM T. J. Watson Research Center
   30 Saw Mill River Rd.
   Hawthorne, NY 10532
   Phone: 914-784-3251
   Email: rhboivie@us.ibm.com


   Nancy Feldman
   IBM T. J. Watson Research Center



Boivie et al.             Expires September 2000             [Page 11]


IETF Draft                Small Group Multicast            March 2000



   30 Saw Mill River Rd.
   Hawthorne, NY 10532
   Phone: 914-784-3254
   Email: nkf@us.ibm.com



A.   Appendix

   This appendix describes the packet formats for SGM when layered on
   top of IPv4.

   SGM packets are assigned IP protocol type:
   IPPROTO_SGM    0xTBD

A.1. Standard SGM Encoding

   The standard SGM header encoding is as follows:

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Ver  |  Res  |S|  DestCnt    |           Checksum            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Protocol    |                IPv4 Address
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        . . .      |           PortNum             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |
   ~
   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          IPv4 Address                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |          PortNum              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Version
      Four-bit field indicating the format of the SGM header.  This
      document describes version 1.

   Res
      Four-bits reserved for future use. Must be set to 0 on
      transmission, and ignored on receipt.

   S-bit (header style)
      One-bit indication of the SGM style header in use. 0 indicates
      the presence of the standard SGM header, 1 indicates the
      presence of the bitmap SGM header. See section A.2.



Boivie et al.             Expires September 2000             [Page 12]


IETF Draft                Small Group Multicast            March 2000




   DestCnt
      Seven-bit value containing the number of SGM destinations in
      the SGM header.  An SGM-destination is an IP-address and port
      number.

   Checksum
      A checksum on the SGM header only.  This is verified and
      recomputed at each point that the SGM header is processed.  The
      checksum field is the 16 bit one's complement of the one's
      complement sum of all the bytes in the header.  For purposes of
      computing the checksum, the value of the checksum field is
      zero.

   Protocol
      A one octet value containing the protocol of the receiving port
      for the following SGM destinations.  In version 1 of SGM, this
      value must be IPPROTO_UDP.

   IPv4 Address
      A four octet value containing a destination IP address.

   PortNum
      A two octet value containing the destination port number,
      corresponding to the preceding IP address.  In this version of
      SGM, the destination port must be a UDP port.



A.2. ICMP SGM Encoding

   Only the first 64-bits of the originating header are returned in
   an icmp packet.  For this reason, the encoding requirement of the
   SGM packet is more complicated than the standard header, as the
   information that is returned to the originator must clearly
   indicate which destinations are not reachable via SGM.  In this
   case, the SGM header contains a bitmap with one bit corresponding
   to each of the destinations, where a value of 1 indicates that the
   packet should be sent to the corresponding destination. Each SGM
   router that forwards the SGM packet to a next hop router clears
   those bits for which that next hop is not on the path for the
   corresponding destinations. When a router doesn't understand SGM,
   it will return an icmp message to the originator of the packet,
   and the returned bitmap in the icmp message indicates the
   destinations that could not be reached via SGM. Note that with
   this type of encoding, the SGM header size remains fixed.








Boivie et al.             Expires September 2000             [Page 13]


IETF Draft                Small Group Multicast            March 2000




    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Ver  | GrpID |S|   DestCnt   |    Bitmap (variable)
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        . . .
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            Checksum           |  Protocol     |  IPv4 Address
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                                   |    PortNum
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                 |
   +-+-+-+-+-+-+-+
   |
   ~
   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          IPv4 Address                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           PortNum             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Version
      Four-bit field indicating the format of the SGM header.  This
      document describes version 1.

   GrpID
      Four-bit field containing a unique SGM group identifier.  This
      is returned in an ICMP error message, and may be used to
      correlate the error with the originating SGM group.

   S-bit (header style)
      One-bit indication of the SGM style header in use. 0 indicates
      the presence of the standard SGM header, 1 indicates the
      presence of the bitmap SGM header. See section A.1.

   DestCnt
      Seven-bit value containing the number of SGM destinations in
      the SGM header. An SGM-destination is an IP-address and port
      number.

   Bitmap
      A variable length field of one to six octets.  This field is a
      bitmap which corresponds to the SGM destinations in the header,
      such that the first SGM destination corresponds to the first
      bit, the second destination corresponds to the second bit, and
      so on. Each i-th bit is set if the packet should be forwarded
      to the i-th destination. The size of the field is determined by



Boivie et al.             Expires September 2000             [Page 14]


IETF Draft                Small Group Multicast            March 2000



      the number of destinations, padded to an octet boundary.

      This field will be returned in an ICMP error message.  The
      bitmap allows us to determine which destinations are not
      reachable via SGM, as an ICMP error message is only guaranteed
      to return the first 64-bits of the original IP datagram
      payload.

      Note the limitation that only 48 destinations may be included
      in packets with the ICMP encoding, as there are only six octets
      available for the associated bitmap.

   Checksum
      A checksum on the SGM header only.  This is verified and
      recomputed at each point that the SGM header is processed.  The
      checksum field is the 16 bit one's complement of the one's
      complement sum of all the bytes in the header.  For purposes of
      computing the checksum, the value of the checksum field is
      zero.

   Protocol
      A one octet value containing the protocol of the receiving port
      for the following SGM destinations.  In version 1 of SGM, this
      value must be IPPROTO_UDP.

   IPv4 Address
      A four octet value containing a destination IP address.

   PortNum
      A two octet value containing the destination port number,
      corresponding to the preceding IP address.  In this version of
      SGM, the destination port must be a UDP port.





















Boivie et al.             Expires September 2000             [Page 15]