INTERNET DRAFT Ali Boudani, Bernard Cousin
Expires: September 2004 IRISA-France
March 2004
Simple Explicit Multicast (SEM)
<draft-boudani-simple-xcast-04.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 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 anytime. 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
In this document, we propose a new multicast protocol called SEM
(Simple Explicit Multicast) or simple Xcast. This protocol uses an
efficient method to construct the multicast tree and deliver
multicast packets. In order to construct the multicast tree, this
protocol uses the same mechanism as Xcast+.
For the delivery of multicast packets it uses the mechanism
of branching routers similar to the mechanism used in REUNITE I
and REUNITE II.
Table of Contents:
1. Introduction
1.1 Terminology
2. SEM Overview
3. Control Plane in SEM
3.1 Receiver Considerations
3.2 Router Considerations
3.3 Sender Considerations
4. SEM messages
4.1 Encoding for SEM BRANCH messages
4.2 PREVIOUS_BRANCH
5. Packet format in SEM
6. comparison between ISM, SSM, Xcast, Xcast+, REUNITEII and SEM
6.1 Differences between Xcast+, REUNITE and SEM
6.2 Cost Analysis of ISM, SSM, Xcast, Xcast+, REUNITE and SEM
6.3 Limitations of Xcast protocol
Boudani & Cousin [Page 1]
INTERNET-DRAFT Simple Explicit Multicast (SEM) March 2004
7. Applicability and Other Considerations
8. Acknowledgments
9. Appendices
9.1 Appendix I: Explicit Multicast Using MPLS
9.2 Appendix II: Manager Router to Construct The Multicast Tree
References
1. Introduction
Recently several multicast mechanisms were proposed that scale
better with the number of multicast sessions than traditional
multicast does[5].
Explicit Multicast (Xcast)[1] is a newly proposed multicast scheme
to support a very large number of small multicast groups. Xcast+
[2] is an enhanced scheme for the support of receiver initiated
join in explicit multicast which complements the existing Xcast.
This is achieved by adding an IGMP join at receiver side and
sending the join request through source-specific join to the sender,
and then by explicitly encoding the list of addresses of the
multicast routers, instead of receiver addresses.
Xcast+ encoding of the destination list in IPv4 and IPv6 are the
same as Xcast. Whereas Xcast can support a very large number of
small multicast groups, Xcast+ can support a very large number of
medium size multicast groups.
In all the newly proposed protocols the source knows the addresses
of all the destinations before sending packets.
We think that when having medium group size the header processing
in every router for all packets traveling from the source to the
destinations is very expensive.
This document describes a new protocol called Simple Explicit
Multicast (SEM) which is an efficient method to construct and
forward multicast packets.
In order to construct the multicast tree, it uses the same
mechanism of Xcast+. Instead, for multicast packets delivery,
it uses the branching routers mechanism similar to that used in
REUNITE II[4]. Packets will be travel from a branching router
to another following the tree that have been constructed by a
control plane that uses the Xcast+ mechanism.
Using SEM will result in the following benefits :
- From the viewpoint of receivers, procedures in the control
plane are the same to existing ISM and SSM[7, 8] schemes.
Therefore, SEM receivers do not need to use additional
control to join in SEM session. This means that the control
plane of SEM is compatible with the existing ISM and SSM.
A receiver that is an IGMP capable host does not need to be
a SEM capable host.
- There can be an increase of the number of receivers, which
means Simple Xcast can support larger size number of
members compared to that of existing Xcast and Xcast+.
Comparing with Xcast and Xcast+, the packet header
Boudani & Cousin [Page 2]
INTERNET-DRAFT Simple Explicit Multicast (SEM) March 2004
processing in SEM is minimized and thus, SEM can support
larger size number of members.
- Similar to ALM (Application Level Multicast) and Overlay
Multicast schemes, SEM supports both multicast and unicast,
where multicast is used in sub-net and unicast is used between
branching routers. Therefore, this will result in a more
efficient and scalable mechanism that allow to increase the
number of receivers in a sub-net.
- When the scalability in ISM schemes is considered, one of the
main issues may be complexity of multicast tree construction
between multicast routers on Internet backbone. Because SEM
uses the multicast scheme in a sub-net level only (the use of
the multicast address is so simple in all other cases) ,
deployment and management are easy and simple, even if
multicast scheme is used.
- This protocol facilitates the use of MPLS to ensure multicast
traffic engineering.(see appendix I)
Note - SEM means the support of receiver initiated IGMP join
and leave messages, the use of encoded address of the multicast
routers in messages used for constructing the multicast tree, and
the use of a new message containing the next and the previous hop
branching router addresses. Previous hop branching router is the
router that has sent the message.
1.1. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in
this document are to be interpreted as described in RFC 2119.
In addition, this document frequently uses the following terms:
ISM Internet Standard Multicast
SEM Simple Explicit Multicast
SSM Source Specific Multicast
Xcast Explicit Multicast
Xcast+ Explicit Multicast extension
Standard multicast address
Multicast address which is used in ISM and SSM
Source-specific join
A join to be sent to sender from mulicast
sub-net router
It does not mean the source-specific join of
PIM-SSM
2. SEM Overview
In SEM, a receiver (like in Xcast+) initiates IGMP join message
Boudani & Cousin [Page 3]
INTERNET-DRAFT Simple Explicit Multicast (SEM) March 2004
(Current version of IGMP, IGMPv3[9] can support join of (S, G)).
When a multicast router receives the request, it sends source-
specific join to the sender.
The sender keeps track of the addresses of routers that send
source-specific join messages in the multicast session.
The sender encodes the list of router addresses in a BRANCH
message. The role of the BRANCH message is to determine routers
acting as branching routers in the multicast tree.
Branching router in SEM mean a router where a packet arrive in an
interface and should be forward to multiple interfaces
(according to the next hop toward the destination routers).
The sender router parses the header, partitions the destinations
based on each destination's next hop, and send the BRANCH
message to each of the next hops.
These procedures comply with the data plane for existing Xcast+
(encoding the addresses of multicast routers in the data packets,
instead of addresses of receivers).
For example, suppose that B, C, D, E, F and G are trying to receive
packets distributed from A in Figure 1 below:
B
/
R4 -- C
/ D
/ /
A --- R1 --- R2 --- R3 R8 -- E
\ / \
\ / F
R5 --- R6 --- R7
\
\
R9 -- G
Figure 1
This is accomplished as follows:
B, C, D, E, F and G initiate IGMP join. When R4, R8 and R9 receive
the IGMP request, they send source-specific join to A. A sends a
BRANCH message with the list of multicast routers (R4, R8 and R9) in
its SEM header to the first router, R1.
SEM encoding of the destination list in IPv4 and IPv6 are the
same as Xcast+.
The BRANCH message is encoded like following:
[IP header | SEM header]
where IP header contains the source address S and the group
address G and SEM header contains the list of all destination
routers and the address of the previous hop branching router.
Therefore, ignoring details, the BRANCH message that A sends to
Boudani & Cousin [Page 4]
INTERNET-DRAFT Simple Explicit Multicast (SEM) March 2004
R1 looks like following:
[ src = A | group address = G | dest = R4 R8 R9
| previous hop branching router]
(note that previous hop branching router initial value is the
source address S itself).
When R1 receives this packet, it needs to properly process the
SEM header of BRANCH message. The processing that a router
does on receiving one of these BRANCH messages is as follow:
At each router in the path to the destinations, the router checks
if it is a branching router for the group (it is a branching
router if there are different next hops for the destinations
encoded in SEM header of BRANCH message).
If all destinations have the same next hop then the router is
not a branching node and no further action is taken and the
same BRANCH message is forwarded to the unique next hop that
has been calculated. If it is not the case and there are
multiple next hops for the destinations, then an entry is
created at the router indicating that the router is a
branching router.
The entry created at the router contains the source address, the
multicast address for the group and the list of unicast addresses
for next hop branching routers(the list is empty at the beginning).
Then the router should send the BRANCH message to each of the
next hop branching routers. The same analysis is repeated at
each branching router.
When a router discovers that it is a branching router (it discovers
that because an entry will be created), it replaces the previous
hop branching router field in the BRANCH message with its proper
address before re-sending the BRANCH message.
It also sends a PREVIOUS_BRANCH message to the router that its
address figure in previous hop branching router field in the
BRANCH message.
The PREVIOUS_BRANCH message received by the previous hop
branching router will update the null list at the corresponding
entry (S,G) with the address of the next hop branching router
(it can be extracted from IP header of the message).
If an address to a next hop branching router already exists at
the entry then the list should be simply updated and the new
address should be added. (for an optimization issue, the
PREVIOUS_BRANCH message will not be generated if there is no
changing in the corresponding entry).
At the end of this operation, we will obtain a path to each
destination router using the next hop branching router
addresses.
A BRANCH message is sent periodically to ensure the maintenance
of the tree. A timer is associated with the group entry at the
source. If a new join message arrived, then a new BRANCH message
should be sent and the timer is set to zero.
It should be noted that another method is to send a BRANCH
message containing only the router who sent the last join
Boudani & Cousin [Page 5]
INTERNET-DRAFT Simple Explicit Multicast (SEM) March 2004
message. In that case, the entries in the branching routers may
not change.
The result of this tree maintenance is that in each branching
router an entry corresponding to each group exist. this
entry contains the previous and the next hop branching router
for that router.
When the source wants to send a packet to a group, the G entry is
examined. The packet is forwarded directly to the next hop
branching routers in the G entry. The packet is unicast to the
next hop branching router with a payload containing the G
address(see section 5).
When the subsequent branching routers receive the packet, the
same operation is repeated.
So if the router receiving the packet is not the next hop
branching router for that packet then it forwards the packet
in unicast to the specific next hop branching router.
When the packet arrives at the router in the destination field,
(to its next hop branching router), it will be then replicated
and sent to each router the next ho branching routers (their
addresses figure in the G entry).
When the packet arrives to the last destination routers, then
packet destination field should be replaced with the G address
to ensure that it will be delivered through multicast to all
receivers in the sub-net.
When a router discovers that there is no receivers, for a group
in its directly connected sub-net, who wants to receive packets
from the the source S, it will send a leave message toward the
source for the group. A new BRANCH message is generated.
For the use of MPLS : a previous hop branching router in each
entry can be added.
The construction of MPLS LSP should be deduced from the entries.
This is FFS.
3. Control Plane in SEM
In SEM, a standard multicast address is used to identify a
multicast session. A sender creates and advertises a multicast
session with standard multicast address. In order to identify
SEM session easily, compared with ISM sessions, special multicast
address range (e.g., similar with the SSM address range, 232/8)
can be used. And thus, advertisement method using web pages will
be useful. These allocations of SEM multicast addresses and the
advertisement method of SEM multicast session are outside the
scope of this document.
Figure 2 describes the whole control plane for SEM.
+-----------+ Receiver
Boudani & Cousin [Page 6]
INTERNET-DRAFT Simple Explicit Multicast (SEM) March 2004
| IGMPv3 app| Source Discovery
---------------------------------------------------------------
| IGMPv3 | IGMPv3 Host Reporting
+-----------+
| source-specific host report (S, G)
|
--------------------------------------------------------------
v
+-----------+ SEM Capable Router
| IGMPv3 | IGMPv3 Querier
--------------------------------------------------------------
| Unicast | Unicast Routing
+-----------+
| source-specific join (S, G)
... and
| source-specific leave (S, G)
|
v
+-----------+ SEM Capable Sender
| Unicast |
+-----------+
Figure 2 Control plane for SEM
3.1. Receiver Considerations
In SEM, like Xcast+, receivers send IGMP join (or leave) to their
multicast router in their sub-net they in order to receive SEM
packets, and then the join requests are sent through source-
specific join to the sender. It is necessary for receivers to know
the address of the sender. Current version of IGMP, IGMPv3 can
support source discovery and source-
specific host membership report. In addition, IGMPv3 leave
operation is also applicable to leave a multicast session
dynamically. That is, SEM receivers don't need to use
additional control to join or to leave a SEM session.
A receiver that is an IGMPv3 capable host does not require
modifications to be an SEM capable host. So,this requirement
for receivers can be easily achieved.
3.2. Router Considerations
In SEM, the router that receives the source-specific IGMP host
membership report (S, G) sends source-specific join (S, G) to the
sender. Unlike source-specific join of PIM-SSM, the join message
is sent to the sender directly with unicast address using unicast
routing,so intermediate routers don't need to keep the state
information of the multicast session (S, G).
The sender obtains the addresses of multicast routers that receive
source-specific IGMP host membership report for multicast session
Boudani & Cousin [Page 7]
INTERNET-DRAFT Simple Explicit Multicast (SEM) March 2004
(S, G) from the source-specific joins of SEM.
Of course, SEM scheme is extended from Xcast+ and REUNITE II, so
all routers on the unicast path between multicast senders and
receivers MUST be a SEM capable router to process and forward
SEM packets.
Each SEM router should be capable to process BRANCH and
PREVIOUS_BRANCH messages. It should also be capable to create and
update group entries.
3.3. Sender Considerations
In SEM, when a sender receives a source-specific join (S, G), it
encodes SEM header of the BRANCH message including addresses
of routers that have sent source-specific join (S, G). These
router addresses are extracted from source addresses of the
source-specific join (S, G) packets.
Encoding method is very similar to that described in Xcast+.
Unlike receivers, a sender MUST be SEM capable host.
Also when the sender transmits a packet to a group G, the
destination of the packet is the corresponding G entry next hop
routers.
It should be noted that the sender keep the information about
the group in an entry that contain the group address and the
addresses of all destinations.
4. SEM messages
4.1. BRANCH message
When the sender receives join messages, the sender explicitly
encodes the list of addresses of the multicast routers that
have received source-specific IGMP host membership report in
a BRANCH message.
The source address field of the IP header contains the address
of the sender. The destination address field carries the
standard multicast address.
The list of destinations will be encoded in a separate header.
the SEM header contains also the previous hop branching router
field (with initial value the source address S).
The IP header will carry the protocol number PROTO_SEM.
Like Xcast+, however, sender explicitly encodes the list of
addresses of the multicast routers that have sent source-
specific join message in SEM header.
4.2. PREVIOUS_BRANCH message
The PREVIOUS_BRANCH is a SEM message sent by a branching router
to its previous hop branching router. It is used to inform the
the previous hop branching router about the the next hop
Boudani & Cousin [Page 8]
INTERNET-DRAFT Simple Explicit Multicast (SEM) March 2004
branching router.(the next hop branching router router is the
one who sent the message).
When receiving this message the entry corresponding to the
group with G address is modified. The entry is updated with the
address of the next hop branching router.
This message contain the IP header (the source is the router it
self and the destination is the previous branch router). The
SEM header of the message contains only the G address.
5. SEM Packet format
Each SEM packet is as follow:
[ IP header | Group address | Transport header | Payload ]
The IP header contains the source address and the destination
address of the next hop branch router.
Join and leave messages could be normal SSM join and leave
messages. Thus, in order to not make confusion between SSM
and SEM, an interval of addresses could specified to be
used only with SEM protocol.
6. comparison between ISM, SSM, Xcast, Xcast+, REUNITEII and SEM
6.1. Differences between Xcast+, REUNITE and SEM
The major difference between Xcast+ and SEM is that Xcast+ encodes
the list of destinations in each packet while SEM uses this
mechanism only with the BRANCH message.
In both protocols the packet will follow the unicast path between
the sender and the destination but in SEM the packet will
follow a unicast path between branching routers. This seems a
good solution in order to optimize the header processing in
every router.
REUNITE II uses branching routers also like SEM but there are
some differences between the two protocols.
SEM uses a multicast address to identify a group of destinations.
The sender will be able to provide statistics about the
destinations. In REUNITE the sender will not be aware about
the receivers. It knows only about the first receiver if
the next hop router for all receivers is the same.
In REUNITE, when the first router that already joined a group
want to leave the group, the tree maintenance will be very
complex.
In comparison there are larger number of control messages
with REUNITE than SEM.
In REUNITE, once the tree is constructed, the packets will
follow an explicit path from the sender to all destinations.
It is not the case with SEM, where the packets should
follow only the unicast paths from a branching router to another.
The join message in SEM is not periodic like in REUNITE. Note
Boudani & Cousin [Page 9]
INTERNET-DRAFT Simple Explicit Multicast (SEM) March 2004
that if routing is asymmetric, even subsequent refresh join
messages can trigger BRANCH messages in REUNITE. That is not
the case in SEM.
Finally, since SEM uses the multicast addresses, The control
plane of SEM is compatible with the existing ISM and SSM.
The Join and leave latency still a major problem with SEM. While
Xcast did not specify any control plane it suggested that
using SIP protocol[6] can be integrated as a flexible control
plane protocol. Xcast+ has introduced the IGMP model and
Source specific join and leave for the receiving routers.
We used the same join and leave messages in SEM.
Note that if routing is asymmetric, the same limitations figure
with REUNITE also.
This limitations figure because we think that the source
should be always aware about the unicast address for every
destination. By this way the leave and join messages should
reach the source and not only the multicast tree.
6.2. Cost Analysis of ISM, SSM, Xcast, Xcast+, REUNITEII and SEM
Costs of ISM, SSM, Xcast, Xcast+, REUNITE II and SEM
schemes can be summarized as described in Table 1. As a
result of analysis, while SEM has some control plane
overhead compared to Xcast and Xcast+, its cost of packet
header processing is minimized.
While REUNITE has some advantages, it has a higher protocol
complexity and larger number of control messages.
6.3 Limitations of Xcast protocol
Two major limitations to the Xcast (Xcast+) protocol are:
1- When a receiver leaves the group, it sends an IGMP leave message
to the source S. S eliminates the receiver address and further
packets will not be sent to this receiver. Meanwhile all packets
sent (during the transition period) by the source with the list
containing the receiver address will be received by the receiver
which will drop it. SEM resolves this problem since further packets
contains only the branching nodes addresses.
2- Xcast packets can not be fragmented: If a router need to
fragment an Xcast packet, Data may be loosed since fragmented
Xcast packets may be not treated by subsequent (or the router
itself) as Xcast packets. SEM does not need to fragment packets,
since it will be treated exactly as TCP or UDP packets. But routers
may need to fragment the branch message. This issue is left for
further study (see appendix II).
7. Applicability and Other Considerations
The application areas for SEM include conferences, multi-player
Boudani & Cousin [Page 10]
INTERNET-DRAFT Simple Explicit Multicast (SEM) March 2004
games, collaborative working, etc., in light of the number of
members, however, SEM is very efficient and more scalable and
simple than other protocols.
Table 1 Cost Analysis of ISM, SSM, Xcast and Xcast+
+----------------------+-----+-----+-----+------+-----+---+
| | ISM | SSM |Xcast|Xcast+|REUN.|SEM|
+----------------------+-----+-----+-----+------+-----+---+
| Multicast | h | m | n | m | l | m |
| Address Allocation | | | | | | |
+----------------------+-----+-----+-----+------+-----+---+
| Multicast Routing | h | h/m | l | l | l | l |
| State Management | | | | | | |
+----------------------+-----+-----+-----+------+-----+---+
| Control | h | h/m | n | m | m | l |
| Overhead | | | | | | |
+----------------------+-----+-----+-----+------+-----+---|
| Overhead by Increase | l | l | h | l | l | l |
| of Receivers | | | | | | |
+----------------------+-----+-----+-----+------+-----+---+
| Extra Header | 1 | l | h | h/m | n | l |
| Processing Overhead | | | | | | |
+----------------------+-----+-----+-----+------+-----+---+
| Deployment | h | m | l | l | l | l |
| | | | | | | |
+----------------------+-----+-----+-----+------+-----+---+
| Join and Leave | | | | | | |
| Latency | m | l | h | h | m | h |
+----------------------+-----+-----+-----+------+-----+---+
h: high
m : medium
l : low or none
n : not applicable
8. Acknowledgments
The SEM protocol draws on a variety of prior work on alternative
approaches to IP multicast, including the Xcast[1], Xcast+[2],
REUNITE[3,4,5].
9. Appendices
9.1 Appendix I: Explicit Multicast Using MPLS
It is quite clear that having a previous hop and next hop in
each branching routers all the path from a sender to the
destinations will be the first step to MPLS multicast traffic
engineering. Once the tree is constructed, the sender will
know the egress routers and also the receivers will know
about the ingress router (witch is the sender).
When a multicast packet arrives at the root of an MPLS multicast
Boudani & Cousin [Page 11]
INTERNET-DRAFT Simple Explicit Multicast (SEM) March 2004
tree (the sender), an MPLS label is imposed to the packet. Then
at the subsequent hops, the LSR looks up the forwarding table
with the incoming label, finds out all the downstream routers and
corresponding outgoing labels, makes the duplications, and
forwards them to the downstream routers with the outgoing
labels. The branching routers should act as the LSRs for the MPLS
domain.
It should be noted that we are not supposing that MPLS will be
introduced just to serve multicasting.
We are supposing that MPLS will be widely used for unicast and thus
it will be normal, since it will exist anyway, to be used for
multicast routing at the same networks.
9.2 Appendix II: Manager Router to Construct The Multicast Tree
In [10], we proposed a novel approach to construct multicast trees in
MPLS networks. We used a special router called NIMS (Network
Information Manager System) as a core router that receive join and
leave messages from all destinations. This NIMS will calculate the
multicast tree and then send branch messages to branching node
routers. MPLS tunnels will be use for multicast traffic between
branching node routers.
The NIMS scheme could be used also in SEM.
All join and leave messages could be sent to the NIMS and then this
router will calculate the tree and determine the multicast branching
node routers. This procedure permanently used to keep the tree
maintenance.
References
[1] R. Boivie et al., Explicit Multicast (Xcast) Basic Specification,
<draft-ooms-xcast-basic-spec-00.txt>, 2000.
[2] M. Shin et al., Explicit Multicast (Xcast+) Supporting Initiated
Join, <draft-shin-xcast-reciever-join-00.txt>, 2001
[3] I. Stoica, et al., "REUNITE: A recursive Unicast Approach to
Multicast", http://www.ieee-infocom.org/2000/papers/613.ps.
[4] I. Stoica and al., REUNITE: A Recursive Unicast Approach to
Multicast, Tech. Rep., Carnegie Mellon University, Dec. 1999,
http://www.cs.cmu.edu/~hzhang/multicast/
[5] D. Ooms, Taxonomy of xcast/sgm proposals, <www.alcatel.com/xcast
/draft-ooms-xcast-taxonomy-00.txt>, 2000
[6] B. Van Doorselaer et al., SIP for the establishment of xcast-based
multiparty conferences, <draft-van-doorselaer-sip-xcast-00.txt>,
2000
[7] H. Holbrook and B. Cain, Source-Specific Multicast for IP, <draft-
Boudani & Cousin [Page 12]
INTERNET-DRAFT Simple Explicit Multicast (SEM) March 2004
ietf-holbrook-ssm-arch-00.txt>, 2000
[8] S. Bhattacharyya et al., A Framework for Source-Specific IP
Multicast Deployment, <draft-bhattach-pim-ssm-00.txt>, 2000
[9] H. Holbrook and B. Cain, Using IGMPv3 for Source Specific
Multicast, <draft-holbrook-idmr-igmpv3-ssm-00.txt>, 2000
[10] A. Boudani and B. Cousin, An effective Solution for Multicast
Scalability: The MPLS Multicast Tree (MMT),<draft-boudani-mpls-
multicast-tree-00.txt>, 2001
Authors Addresses
Ali Boudani
IRISA/INRIA Rennes
Campus Universitaire de Beaulieu
Avenue du General Leclerc 35042 Rennes France
Phone : (33) 02 99 84 25 37
Fax : (33) 02 99 84 25 29
E-mail : aboudani@irisa.fr
Bernard Cousin
IRISA/INRIA Rennes
Campus Universitaire de Beaulieu
Avenue du General Leclerc 35042 Rennes France
Phone : (33) 02 99 84 73 33
Fax : (33) 02 99 84 71 71
E-mail : bcousin@irisa.fr
Expiration Date: September 2004