Internet DRAFT - draft-boudani-gxcast
draft-boudani-gxcast
INTERNET DRAFT Ali Boudani
Expires: April 2005 Alexandre Guitton
Bernard Cousin
IRISA-France
October 2004
GXcast: Generalized Explicit Multicast Routing Protocol
<draft-boudani-gxcast-02.txt>
Status of this Memo
By submitting this Internet-Draft, I certify that any applicable
patent or other IPR claims of which I am aware have been disclosed,
or will be disclosed, and any of which I become aware will be
disclosed, in accordance with RFC 3668."
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
Recently several multicast mechanisms were proposed that scale better
with the number of multicast groups than traditional multicast does.
These proposals are known as small group multicast (SGM) or explicit
multicast (Xcast). Explicit multicast protocols, such as the Xcast
protocol, encode the list of group members in the Xcast header of
every packet. If the number of members in a group increases, routers
may need to fragment an Xcast packet. Fragmented packets may not be
identified as Xcast packets by routers. In this paper, we show that
the Xcast protocol does not support the IP fragmentation and we show
also that avoiding fragmentation induces hard-coded limits inside the
protocol itself in terms of group size. First, we describe the Xcast
protocol, the Xcast+ protocol (which is an extension of Xcast) and we
compare these two protocols with traditional multicast protocols.We
propose then a generalized version of the Xcast protocol, called
GXcast, intended to permit the Xcast packets fragmentation and to
support the increasing in the number of members in a multicast
group.
I. INTRODUCTION
Boudani et al. [Page 1]
INTERNET-DRAFT GXcast October 2004
Multicast, the ability to efficiently send data to a group of
destinations, has become increasingly important with the emergence of
network-based applications like IP telephony, videoconferencing,
distributed interactive simulation and software upgrading. A
multicast routing protocol should be simple to implement, scalable,
robust, use minimal network overhead consume minimal memory resources
, and inter-operate with other multicast routing protocols.
Most of proposed multicast protocols like DVMRP [1] and MOSPF ([2],
[3]) perform well if group members are densely packed. However, the
fact that DVMRP periodically floods the network and the fact that
MOSPF sends group membership information over the links, make these
protocols not efficient in cases where group members are sparsely
distributed among regions and the bandwidth is not plentiful.
To address these issues, the Protocol Independent Multicast (PIM)
routing protocols are being developed by the Inter-Domain Multicast
Routing (IDMR), working group of the IETF. PIM contains two
protocols: PIM-Dense Mode (PIMDM) [4] which is more efficient with
applications where group members are densely distributed, and
PIM-Sparse Mode (PIM-SM) [5] which performs better with applications
where group members are sparsely distributed. Although these two
protocols share similar control messages, they are essentially
proposed for two different kinds of applications. Today's multicast
protocols [6] can be used to minimize bandwidth consumption, but it
suffers from a scalability problem with the number of concurrently
active multicast groups because it requires a router to keep a
forwarding state for every multicast tree passing through it and the
number of forwarding states grows with the number of groups. There
seem to be two kinds of multicast that are important: a broadcast-
like multicast that sends data to a large number of destinations and
a narrowcast multicast that sends data to a fairly small group. An
example of the first kind of multicast is the audio and video
multicasting of a presentation to all employees in a corporate
intranet. An example of the second kind of multicast is a
videoconference involving three or four parties [6]. Thus, a
one-size-fits-all protocol will be unable to meet the requirements
of all applications [7]. Providing for many groups of small
conferences (a small number of widely dispersed people) with global
topological scope scales badly given the current multicast model [8].
Recently several multicast mechanisms were proposed that scale better
with the number of multicast groups than traditional multicast does.
These proposals are known as small group multicast (SGM) [9] or
explicit multicast (Xcast) [10]. Explicit multicast protocols, such
as the Xcast protocol, encode the list of group members in the Xcast
header of every packet. Xcast assumes that there is no packet
fragmentation. However, if fragmentation occurs (e.g. if the group
size or the data is too large) the fragmented packets will not be
identified as Xcast packets by routers. In this paper we propose a
generalized Xcast protocol to support the group size increasing and
to overcome the fragmentation problem.
II. THE XCAST AND THE XCAST+ PROTOCOLS
To solve the problems of traditional multicast protocols, Boivie et
Boudani et al. [Page 2]
INTERNET-DRAFT GXcast October 2004
al. propose the Explicit Multicast protocol (Xcast).
A. The Xcast protocol
The Xcast protocol is a newly proposed multicast protocol to support
a very large number of small multicast groups. To send data to a
given group, the source first explicitly encodes the list of
destinations in the Xcast header of the packet. Then, the source
parses the header, partitions the destinations based on each next
unicast hop and forwards a packet with an appropriate header to each
of the next hops. Each router along the path to destinations repeats
the same processing on receiving an Xcast packet. If a router
detects that there is only one destination in the destination list
of a packet, the packet is converted to unicast. The algorithm
realizing the conversion of an Xcast packet to a unicast packet is
called Xcast-to-Unicast (X2U). This packet is then forwarded in
unicast along the remainder of the route.
B. The Xcast+ protocol
Xcast+ is an extension of Xcast for a more efficient delivery of
multicast packets [11]. Every source or destination is associated to
a Designated Router (DR). Instead of encoding in the Xcast packet
header the set of group members, Xcast+ encodes the set of their DRs.
When a new member wants to join the group G of source S, it sends an
IGMP-join message [12] to its DR. The DR will send a join-request
message to the source S. The DR of the source intercepts this message
and analyzes it in order to keep track of all concerned DR addresses.
When the source S wants to send a message to the group G, it sends a
multicast packet. This packet is received by its DR and converted to
an Xcast packet using the Multicast-to-Xcast algorithm (M2X). The
packet is then forwarded as in Xcast to the DRs, since the
destination list in the Xcast header contains the DR addresses
instead of the member addresses. Then, each DR converts the Xcast
packet to a multicast packet using the Xcast-to-Multicast protocol
(X2M) and sends it in its subnetworks.
C. The IP fragmentation mechanism
Due to physical reasons, every link can transfer only a limited
volume of information in each packet. The Internet protocol (IP)
[13] contains a mechanism called fragmentation which makes this
limitation transparent for end stations. The fragmentation
mechanism allows a packet to be cut into fragments in order to be
suitably transferred on a link. Suppose that a router receives a
packet. After having decided on which link this packet should be
forwarded, the router checks the maximum capacity of this
link which is the Maximum Transmission Unit (MTU). If the packet is
too large and unless it is explicitly forbidden, the router cuts out
it in order to respect the following constraints: each resulting
fragment is an autonomous IP packet, with a valid IP header, each
resulting fragment has a size less than or equal to the MTU, the
Boudani et al. [Page 3]
INTERNET-DRAFT GXcast October 2004
data is distributed between the fragments. The algorithm used to
fragment IPv4 packets is explained in [13]. The IPv6 protocol also
have a fragmentation mechanism, described in [14]. Note that one goal
of IPv6 is to avoid the fragmentation. This will be discussed later.
D. Xcast packet fragmentation
Since the Xcast packet header may be large, two cases can be
considered: either the whole Xcast packet header is short enough to
be kept in the first fragment, or the Xcast header has to be cut out.
In both cases, the second fragment is not a valid Xcast packet since
it has no Xcast header. Thus, these packets cannot be forwarded to
receivers and the data they contain is lost. Moreover, in the second
case the first fragment contains only a subset of receivers and no
data. The first fragment may however be forwarded up to the mentioned
receivers, inducing meaningful traffic.
These problems show that the fragmentation of an Xcast packet should
be forbidden. This can be done in IPv4 by setting the appropriate
flag (Don't Fragment, DF) in the IP header. In order to reach the
receivers, the source has to limit the size of its packets to 576
bytes which is the minimum MTU guaranteed by IPv4 on any link. This
size limits the number of receivers in an Xcast group to 134. In
IPv6, since the minimum MTU is 1280 bytes and since IPv6 addresses
are stored using 16 bytes, the limit in the size of the Xcast group
is 76. Having these limits hardly coded in protocols is restrictive.
What we propose is a simple mechanism to cancel these limitations
in the size of Xcast groups. The performance and the scalability of
our proposition will be analyzed.
E. Comparison between explicit multicast protocols and traditional
multicast protocols
Traditional multicast protocols and explicit multicast protocols are
two different approaches designed to handle multicast groups. We
will try to emphasis the main advantages of each method, compared to
the other one.
1) Drawbacks of explicit multicast protocols: In addition to the
important Xcast packet fragmentation problem, other related
drawbacks also exist.
a) Limited payload: packet size is limited as a result of network
MTU. In explicit multicast protocols, the larger the list of
destinations is, the lower the payload is.As a consequence, more
packets should be generated to transmit a given amount of data.
b) Complex header processing: in explicit multicast protocols, each
destination in the header needs a routing table lookup. A packet with
destinations in the list of destinations will require n+1 unicast
routing table lookups1. Additionally, a different header has to be
constructed per next hop. However, it can be noticed that since such
protocols are typically designed for sparse sessions, there will be
a limited number of branching routers compared to non-branching
routers. The construction of different headers only occurs in
branching points. The header construction can moreover be reduced
Boudani et al. [Page 4]
INTERNET-DRAFT GXcast October 2004
to a simple operation: the modification of a bitmap.
2) Advantages of explicit multicast protocols: Explicit multicast
protocols make easier the routing of multicast packets. It has many
advantages over traditional multicast protocols.
a) Routing state and signalisation messages management: in explicit
multicast protocols, routers do not have to maintain a state per
group. Indeed, there is no multicast forwarding table since only
unicast tables are used. This makes the Xcast protocol very scalable
in terms of the number of groups that can be supported
simultaneously since the routers in the network do not need to
disseminate information for the groups.
b) Automatic reaction to unicast reroutes and simplified traffic
engineering: explicit multicast protocols react immediately to
unicast route changes. Traditional multicast protocols need to
exchange information with unicast protocols in order to have an
adequate reaction. This is achieved on a polling basis in many
implementations, yielding a slower reaction to e.g. link failures.
This delay may also depend on the number of concerned groups.
Additionnaly, there is no need for a specific multicast traffic
engineering tool since packets follow traffic engineered unicast
paths.
c) Easier security and accounting: in explicit multicast protocols,
the source has a complete knowledge about members (or about DR
members). It will be able to drop dynamically some members and a
border router can be able to determine approximately how many times
a packet will be duplicated in its domain (especially when
link-state protocols like OSPF [15] are used in the domain).
Other advantages can be mentionned:
No multicast address allocation is needed except eventually in the
DR of the source in the case of the Xcast+ protocol.
Shortest path is always used even in an asymmetric network.
III. THE GXCAST PROTOCOL
As explained in the previous section, the Xcast protocol can not
support large groups due to its incompatibility with the IP
fragmentation mechanism. In this section, we propose a generalized
Xcast routing protocol, the GXcast protocol, which is designed
basically to avoid the fragmentation. Moreover, the GXcast protocol
can be parameterized in order to improve the Xcast behaviour.
A. The GXcast protocol
The GXcast protocol [18] is a simple generalized version of the
Xcast protocol: instead of sending a message to the destinations,
the source limits the number of destinations in a packet to nM. Thus,
the list of destinations is cutted into sub-lists of at most nM
destinations. Each sub-list corresponds to a destination list for
an Xcast packet. Several packets may have to be sent in order to
Boudani et al. [Page 5]
INTERNET-DRAFT GXcast October 2004
deliver data to all the destinations. is the parameter of the GXcast
protocol and it impacts the protocol performance in terms of several
criteria. GXcast packets are similar to Xcast packets: they have the
same header and are treated in the same way by intermediate routers,
DR destinations and destinations. The only difference between the
Xcast protocol and the GXcast protocol is done in the source or in
the DR of the source. The Xcast protocol and the GXcast protocol can
therefore inter-operate easily.
B. Study of the GXcast parameter
The behaviour of the GXcast protocol greatly depends on the value of
the parameter. Indeed, as we will see in this subsection, there is a
number of criteria that are directly influenced by the chosen value.
In the following, we will denote by MTU the value of the MTU which
depends on the IP version used, by E the size of the header plus
the size of the Xcast header (typically 16 bytes) and by IP the size
of an IP address. n will represent the number of destinations in the
group and d the volume in bytes of data to transfer.
1) Simple behaviour:
Since a packet has to contain at least one byte of data, the maximum
number of destinations n_max allowed in an Xcast packet is defined
as:
The values n_max = 134 and n_max = 76 correspond respectively to the
IPv4 and to the IPv6 specifications. The simplest behaviour GXcast
can have is to fix the value to the nM value. However, this is not
efficient for groups having a lot of members (typically more than
n_max).
2) The number of members influenced by a fault: if a drop occurred
on a GXcast packet, every member having its address in the member
list will be concerned by the drop. To reduce the number of
destinations concerned by such errors, small values of should be
chosen.
3) Number of generated packets: after studying the packet generating
functtion , we found that this function admits a minimum value for:
nM= n_max/2. Since this optimal value does not depend on n and on d
and since it is very simple to calculate it and provides good results
in terms of the number of generated packets, we propose it as a
default value for the GXcast protocol.
4) Using Path MTU instead of minimum MTU: At the beginning of this
section, we defined MTU as the minimum MTU guaranteed by IP.
However, the value of the Path MTU (PMTU) can also be used since we
don't make any assumptions on the stability of the MTU value in our
study. The PMTU is the minimum value of the MTU on the links of a
path. It can be noticed that the PMTU value is easy to obtain in
GXcast, since unicast paths are used.
References
Boudani et al. [Page 6]
INTERNET-DRAFT GXcast October 2004
[1] D. Waitzman, C. Partridge, and S. Deering. Distance Vector
Multicast Routing Protocol. IETF RFC 1075, 1988.
[2] J. Moy. Multicast Extensions to OSPF. IETF RFC 1584, 1994.
[3] J. Moy. MOSPF: Analysis and Experience. IETF RFC 1585, 1994.
[4] S. Deering et al. Protocol Independent Multicast version 2-Dense
Mode Specification. IETF Internet Draft,
http://catarina.usc.edu/pim/pimdm/pim-dm-06.txt, 1997.
[5] D. Estrin et al. Protocol Independent Multicast-Sparse Mode
(PIM-SM): Protocol Specification. IETF RFC 2362, 1998.
[6] M. Ramalho. Intra- and Inter-domain multicast routing protocols:
A survey and taxonomy. IEEE Communications Surveys and Tutorials,
First Quarter 2000.
[7] Reliable Multicast Transport Working Group Web Site.
http://www.ietf.org/html.charters/rmt-charter.html, February 2003.
[8] S. Deering, S. Hares, C. Perkins, and R. Perlman. Overview of
the 1998 IAB Routing Workshop. IETF RFC 2902, August 2000.
[9] D. Ooms. Taxonomy of xcast/sgm proposals. IETF Internet draft,
July 2000.
[10] R. Boivie, N. Feldman, Y. Imai, W. Livens, D. Ooms, and O.
Paridaens. Explicit multicast (Xcast) basic specification. IETF
Internet draft, October 2000.
[11] S. Myung-KI, K. Yong-Jin, P. Ki-Shik, and K. Sang-Ha. Explicit
multicast extension (xcast+) for efficient multicast packet delivery.
ETRI Journal, 23(4), December 2001.
[12] B. Cain, S. Deering, B. Fenner, I. Kouvelas, and A.
Thyagarajan. Internet group management protocol, version 3. IETF
Internet draft, January 2002.
[13] University of Southern California J. Postel from the
Information Sciences Institute. Internet Protocol. IETF RFC 791,
1981.
[14] S.Deering and R. Hinden. Internet Protocol, version 6 (ipv6)
Specification. IETF RFC 2460, 1998.
[15] J. Moy. Ospf version 2. IETF RFC1247, July 1991.
[16] K. Fall. and K. Varadhan. The NS Manual. UC Berkeley, LBL,
USC/ISI, and Xerox PARC, January 2001.
[17] E. Zegura, K. Calvert, and S. Bhattacharjee. How to model an
internetwork. In INFOCOM, 1996.
[18] A. Boudani, A. Guitton, B. Cousin. GXcast: Generalized Explicit
Multicast Routing Protocol. 9th IEEE Symposium on Computers and
Communications (ISCC 2004) [organis‰e par l'IEEE], Alexandria, Egypt,
June 2004 (ask authors for a hard copy).
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
Boudani et al. [Page 7]
INTERNET-DRAFT GXcast October 2004
Alexandre Guitton
IRISA/Universit‰ de Rennes1
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 : alexandre.guitton@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
Copyright Statement
Copyright (C) The Internet Society (2004). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights."
"This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."
Expiration Date: April 2005
