M ulticas t Routing

Algorithms and Protocols: A Tutorial

Laxman H. Sahasrabuddhe and Biswanath Mukherjee, University of California

Abstract
Multicasting is the ability of a communication network to accept a single message
from an application and to deliver copies of the message to multiple recipients at
< . there has been an exolosion of research literature on
different locations. Recentlv.
multicast communication. This

ulticasling is the ability of a communication (LANs) and wide area nctworks (WANs). A LAN spans a
network to acccpt a single message from an small geographical area, typically a single building or a cluster
application and to dclivcr copies of the mcs- of buildings, while a WAN spans a large geographical area
sagc to multiple recipients at different loca- (e.g., a nation). Often, nodes connccted to a LAN communi-
tions. One of the cliallcngcs is to minimize tho amount of catc over a broadcast network, while nodes connected to a
network resources employcd by multicasting. To illustrate this WAN communicate via a switched network. In a broadcast
point, k t us assume that a vidco server wants to transmit a LAN, a transmission from any one node is received by all the
movie to 1000 recipients (Fig. l a ) . If the server wcre to nodes on the network; thus, multicasting is easily implement-
cmploy 1000 scparate point-to-point connections (e.g., TCP
connections), 1000 copies of the movie may
have ti) be sent over a singlc link, thus making
poor usc of the availablc bandwidth. An effi-
cient implementation of multicasting permits
much bettcr nsc of the availeblc bandwidth by
transmitting at most onc copy of the movic on
cach link in the nctwork, as shown in Fig. l b .
Rcccntly, there has bccn a lot of research in
the area of multicast communication. Although
many excellent surveys and books cxist which
cxamine varions aspccts of multicasting [I-61,
i n thc course of our studies wc have found a
need for a tutorial-cum-survcy of the various
multicast routing algorithms and their relation-
ship with mnlticast routing protocols. In this
work we present a tutorial-cum-survcy of the

-
following two important topics in multicasting:
Multicast routing algorithms
* Multicast routing protocols
Communication networks can be classificd
into two categories: local area networks

This work has heor supporied inpar( />yike Nalional . _ I

Suie,rce Foundution (NSF) under G,owts Nos. NCR u&"g a movie" 1000 di&ent users; b) multicasting the movie. (R=slan-
9508238 nnd ANI-9XO52U5. dard router, MR= rnullicast router.)

90 o 2uuo IEEE
ox~o-xn4~~nn1~[Link] IEEE Network * JanuaryiFebrualy 2000
 6.1, UT, MI, and NY; bj a directedgraph that modelithe WANshown in a).

. .
. ... ..... . -.. .. . . ..
ed on a broadcast LAN. On the other hand, imple-
menting mnlticasting on a switched network is quite
challenging; hence, throughout this work, we will
focus on the multicasting problem in a WAN which
I WA

is hascd on a switched network.

Today, many multicast applications exist, such as NI
news feeds, filc distribution, interactive games, and CA1
videoconferencing, but the implementation of these
applications is not necessarily efficient because
today's WANs were designed to mainly support
point-to-point (unicast) communication, In the
future, as multicast applications become more pop-
CA2 Tx
ular and handwidth-intensive, there will emerge a .. .. - .. . . . .. .-
pressing need to provide efficient multicasting sup- ~~ F'aure 3. hi ~ ~ n i m ui ~I t li ..5rwwr
~ i w . MuIiir.o.%rvruui) = I ( A l . 'I'X. II.
part O ~ W A N S . NY). Cost ofall l i h 1. cost of Steiner tree =>.
A WAN consists of nodes (i.e., switches o r
routers) intcrconnected by communication links. A
transmission from a source to a destination is routed through metric and asymmetric. Symmetric links have the same weight
these interconnected nodcs. Fieure 2a shows an examvle of a in hoth directions. while asvmmetric links have different
route of a transmission from ;source to a destination on a weights depending'on the diiection. Thus, in Fig. 2b, which
WAN.' shows weights on only four links, the link between nodes CA2
A WAN can be modeled by a directed graph. Figurc 2h shows and TX is symmetric, while the link between nodes TX and
a dirccted graph that models the communication network MD is asymmetric. If all the links in a WAN are symmetric,
shown in Fig. 2a. A directed graph consists of a set of nodes V we can model the WAN by an undirectedgraph, as shown in
and a set of links E. A link connecting node u to nodc U is rep- Fig. 3. In an Undirected graph, the direction of a link is unim-
resented by an ordered tuple ( U , U). Nodes in the directed portant; hence, a link between node u and node U can he rep-
graph reprcsent nodes in the WAN, while links in the directed resented by an unordercd tuple (U, v). Traditionally,
graph reprcsent communication links in the WAN. (Note that communication networks have been modcled by undirected
the graph in Fig. 2b is a special one in the sense that if there is graphs. Henceforth in this work, unless othcnvise stated, the
a link ( U , v ) , there also cxists a link (U, U); this characteristic, term graph will refer to an undirected graph.
however, is not a necessity in a gencral directed graph.) In unicast (point-to-point) Communication, routing is often
Communication links in a network may have different treated as the shortest-path problem in graphs. When two nodcs
properties. For example, a fiber optic communication link wish to Communicate, a minimum-weight path (shortestpath)
may have very large bandwidth compared to a copper wirc connecting the corresponding pair of nodes is selected. In mul-
communication link. A property of a communication link is ticasting, a group of more than two nodes (also called the mul-
represented by a weight of the corresponding link in a graph. ticast group) wish to communicate with one another. Now,
For examplc, if the propagation delay of the communication instead of the shortest path, we are interested in the minimum-
link (CA2,TX) is 1 ms, this information can be represented by weight tree which spans all the nodcs in the multicast group.
assigning a weight equal to 1 to the link (CA2,TX) in Fig. 2h, In gcneral, differcnt multicast applications havc different
with the weights of the other links being their corresponding requirements. For cxample, a reliable data transfer multicast
propagation delays in milliseconds. application, such as software distribution, has very different
The communication links in Fig. 2 can hc of two typcs: sym- requirements from a real-time multimedia multicast applica-
tion, such as nationwide videoconferencing. Thus, it is helpful
to classifv multicast communication into two tvnes:

IEEE Nehvork IanualyiFebruary 2000 91

 ticast group as well as reccivc data from other nodes in the at CA1 is equal to 2.33 (the average of the delay from source
multicast group. CA1 to nodes TX, IL, and Ny). In comparison, the source-spe-
The next section discusses multicast routing algorithms. We cific delay (with CA1 as the source) of thc group-shared multi-
then study the implementation of multicast routing protocols cast tree shown in Fig. 4b is equal to 3.33. On the other hand,
on the Internet. Note that the current Internet uses IPv4, if we were to calculate the average group-shared dclay of the
while the next-generation Internet (NGI) will employ lPv6. source-specific tree by taking the average of the end-to-end
Since some topics discussed are specific to IPv4, they are not delays over all (multicast-member. multicast-member) pairs, the
applicable to the NGI, although the general principles dis- average group-shared delay is equal to 3.5 in Fig. 4a, while the
cussed will still be applicable. On the other hand, the subscc- average group-shared delay of the group-shared tree in Fig. 4h
tions on multicast routing algorithms are relevant to both IPv4 is equal to 2.67. Thus, the application requirements dictate
and IPv6 because they do not presuppose any particular net- which type of multicast trees are “better.”
work-layer protocol. Finally, we provide concluding rcmarks. The following is a list of the properties of a good multicast
tree. Since for most multicast applications some properties are
Mulficast Routing Algorifhms more important than others, we have divided the properties
into thrce priority levels:4 high, medium, and low.
Figure 3 shows an undirected graph G = (V, E), where Vis
the set of nodes and E the set of links. Note that, siuce graph High Priority
G is undirected, it models a communication network which * Low cost: Thc cost (or weight) of a multicast tree is the sum
has symmetric links. Let M = (CA1, TX, IL, NY) be a multi- of the costs (or weights) of all the links in the multicast
cast group. (Shaded nodes in Fig. 3 belong to the multicast
group.) Now, in order to perform multicast communication,
the nodes in the multicast group must he interconnected by a
- trcc. A good multicast tree tries to minimize this cost.
Low delay: Thc end-to-end delay from the source node to
the destinatioii node is thc sum of the individual link delays
tree. Thus, the problem of multicast routing in communication along the route. A good multicast tree tries to minimize the
networks is equivalent to finding a tree T i n graph G such that T end-to-end delay for every sourcc-dcstioation pair in the
spans all vertices in the multicast group M. Such a tree is called multicast group.
a multicast lree and is shown in Fig. 3 by thick lines.* (The Scalability: A good multicast tree is scalable in two respects.
term Steiner free used in Fig. 3 will be clarified next.) First, constructing a multicast trec for a large multicast
Just as multicast communication can be of two types, multicast group should requirc reasonable amounts of time and
trees can also be classified into two corresponding categories: resources. Second, the switches in the communication net-
source-specific (or source-rooted) and group-shared. For the work should he able to simultaneously support a large num-
same multicast example as in Fig. 3, Fig. 4a shows a source- bcr of multicast trees.
specific multicast tree which employs unidirectional links?
(with source = CAl), while Fig. 4b shows a group-shared mul- Medium Priority
ticast tree. The key difference between a source-specific multi- Support for dynamic multicast groups: Multicast groups can
cast tree and a group-shared multicast tree is that a he classified as static and dynamic. The members of a static
source-specific multicast tree is optimized for source-specific multicast group do not change over time; in a dynamic multi-
multicast communication, while a group-shared multicast tree cast group, new membcrs may join or existing members
is optimized for group-shared multicast communication. For leave. A good multicast tree should allow multicast members
example, if we want to minimize the average delay for source- to join or leave the multicast trcc in a seamless fashion.
specific communication, we need to minimize the average Moreover, the properties of a good multicast tree should not
sourcc-specific delay which is calculated by taking thc avcragc degrade due to the dynamic nature of thc multicast grnup.
of the end-to-end delays over all (source, multicast-member) Survivability: A good multicast tree should bc ablc to sur-
pairs. Now, assuming that each link in Fig. 4a has delay equal vive multiplc node and link failures.
to 1, the source-specificdelay of thc source-specifictree rooted

Note that the priori& 1eveI.v may he different for certain [Link]
Throughout thir work, the default weight of all links, unless pecrfied oth- erample, while the jkimempmpeny ofn mullicast tree i.v not wry impor;
envise, is equal to 1. tant in general, it may be the mmt impnrtamproper&of the midticast tree
if the multicust tree is being employed by n multiplaycrgamr. Moreover;
Note that a source-specificmulticast free cormecls n source node to other although Some properties arc runsidered low-priorityfor today’s applica-
nodes in the mellicast group by employingeither unidi~ctionalor bidirection- tions, they may become more implant in thefite,a due to enzerRi,tg
al links, while a pup-shared mullicast tree employs on& bidirectional link. applications which may he beyond our cumprekension today.

92 IEEE Network * JanuarylFebruary 2000

low Priorify
* Fairness: A good multicast tree is fair in two
respects. First, it tries to provide a minimum quality
of service (e.g., hounded delay) to each member in
the multicast group. (It is not fair to unncccssarily
punish one membcr in order to improve thc quality
of service to other mcmbers.) Second, it tries to
evenly dividc the multicasting effort (c.g., packet
duplication effort) among the participating nodes.
Most algorithms that havc been proposed in the
literature mainly focus 011 Cost and delay OPtimiza- W Figure [Link] m m p l e of agraph for which the Steiner tree can be found by
tion, although the nther Properties havc also heen employingthe reduction rules. Cost of all Iinh = 1; costofthe Steinertree = 4.
addressed to a lesser extent. Before we examine each
of the above prnpcrties in detail, let us examine
some important theoretical concepts and dcfinitions which j ) can he removed from G. Furthermore, if cji = d y and
will help us better undcrstand the nature of the multicast there is a path of cost dij from i to j not containing ( i , j ) ,
routing problem. then link (i,j ) can be removed from G.
4)If G contains thrce distinct nodes U , v, w E M , such that U
Thc classical optimization problem in multicast routing is and v arc adjaccnt, cuy > d,,, and cuv > d,,, then link ( U , v)
called the Steiner tree problem in networks ( S P N ) , and is can bc removed from G. In other words, if U , v, and w are
defined as follows. Given any three nodes in the multicast group such that the cost of
An undirectcd graph G = (V,E ) the link (U, v) is more than the cost of a path from nodc w
A cost function which assigns a positive real cost cZ,”to link to node U as well as node v, then link ( U , v) does not belong
- v)
A set of nodes M L Vwhich belong to the multicast group
find a tree T = ( V ,Er) which spans M , such that its cost CT =
to thc Steiner tree.
5)Let u E M . Let v and w be the closest and second closest
adjacent nodes to U , respcctively. Now, if cBVt min{d, Ip
E<,<, v , e ~ r ~ uisvminimized. Such a minimum-cost multicast tree E M and p # U } S c,,,, then the link ( U , v) belongs to the
is called a Steiner tree. Notc that since graph G is undirected, it Stciner tree and G can he contracted along ( U , v ) . In other
models a communication network which has bidirectional links; words, if the closest adjaccnt node (v) brings you nearer to
thus, Steiner tree Tis a group-shared multicast tree. other members of the multicast group, then link ( U , v)
Figure 3 shows a Stciner tree which connects the multicast should belong to the Steiner tree.
group consisting of nodes CA1, TX,IL, and [Link] we assumc For example, the graph shown in Fig. 5 (nodes in the multi-
the cost of each link to be equal to 1, the cost of the Steiner cast set are shaded) can h e reduced to a single node by
tree will he equal to 5 . Note that nodes CA2 and PA do not cmploying reduction 5 repetitively as follows. First, we con-
belong to the multicast group, but are part of the Steiner trcc. tract along link (CA2, CAI); second, we contract along link
Such nodes are called Steiner nodes. (MI, NY); third, wc contract along link (C41, UT); and finally,
Although SPN is NP-complete [7], thcre are some trivialS we contract along link (UT,MO.
cases of SPN that can he solved in polynomial timc, as shown Unfortunately, as the following lemma demonstrates, these
helow [I]: reductions cannot he applied to a large number of instances
* I MI ,= 2 (unicast case): There are only two nodes in the of SPN which occur in typical communication networks. Usu-
multicast group. SPN reduces to the well-known shortest- ally, these reductions cannot he applied to cases in which IMI
path problem. Polynomial-time algorithms for this problem << I VI, G is not sparse: and G satisfies the triangle inequality
are known [S, 91. (to he explained shortly). The following Lemma describes a
IMI = I VI (broadcast case): In this case, the multicast group sufficient condition for an instance of SPN to he “irreducible.”
contains all the nodes in the network. Thus, SPN reduces to
the well-known minimum spanning trec problem. Polynomi- Lemma 1 - If an instance of SPN (say P) satisfies all of the
al-time algorithms for this problem are known [lo, 111. following three conditions, then P cannot he reduced to a
G is a tree: In this case, there is only one suhtree which spans smaller instancc of SPN by using the aforementioned reduc-
thc multicast group M this suhtree is the solution to SPN. tion rules.
Moreover, for certain c a w of SPN, we can reduce the size of [Link] graph satisfies the triangle inequality, that is, the cost
the problem by employing the following rules [l].Note that cUyof a link ( U , v) is strictly less than the cost of any path
each rule can hc pcrformed in polynomial time. Let deg(v) from node u to nodc v which does not include link ( U , v).
denotc thc degree of the node v E VI [Link] minimum degree of the graph is 3, that is, Vv E V ,
1)If G contains a node v with deg(v) = 1, then v and the link dcg(v) 2 3.
( U , v) can he removed from G. If v E M and u e M, then u [Link] of the nodes in the multicast group are adjacent to
is added to the multicast group in thc reduced graph. Note one another, that is, Vu, v t M, (U, v) e E.
that, if v E M , thcu link ( U , v) belongs to the Steiner trec.
2)If C contains a node v 6 M with dcg(v) = 2, then the two Proof - Reductions 1 and 2 cannot he applied because the
links ( i , v) and (v. j ) can be rcplaced by a link ( i , j ) of cost minimum degree of the graph is 3. Rcdnction 3 cannot be
c~ = cjv t cvp If, as a rcsnlt, two links becomc parallel, the applied because the graph satisfies the triangle inequality.
onc with the larger cust can be removed from G. Reduction 4 cannot he applicd hccause none of the nodes in
3)If G contains a link (i,j ) such that cjj > dg, where djj is the thc multicast group are adjacent to one another. Finally, reduc-
cost of the shortest-path between nodcs i and j , then link (i, tion 5 cannot bc applied because the graph satisfies the triangle

* There are ,comeother special caSes of SPN for which polynomial-time We definegraph G lo be sparse ifall the spanning trees ofgraph G can
algorithms exist [l]. be enumerated in polynomial fime.

IEEE Network JanualyiFcbrualy 2000 93

inequality, and none of the nodes in the multicast group are (after applying steps 3 , 4 , and 5 ) . The KMB algorithm has a
adjacent to one another. The graph shown in Fig. 3 satisfies all performance guarantee of 2(1 - 11lMI).
the above conditions; thus, it is an “irreducible” graph. w Recall that the KMB algorithm assumes that the commuui-
cation network has symmetric link costs. Given the increasing
Thus, for typical wmmunication networks, it may he impossi- heterogeneity of applications and communication links (e.g.,
ble to find a Steiner tree in a reasonable amount of time; hence, satellite and radio links are becoming common), the link costs
it is important to develop apprmimation algorithms for SPN. may he asymmetric; that is, the cost of a link hctween any two
Approximation algorithms for SPN run in polynomial time adjacent nodes is not the same in both directions. In a commu-
and produce good-quality (hut not necessarily optimal) solu- nication network with asymmetric links, the problem of finding
tions to SPN. For some approximation algorithms, it is possi- a minimum-cost group-shared multicast tree can he reduced to
ble to prove aperformanceguarantee (i.e., a bound on the SPN as follows. Let G = (V,E ) he a directed graph which
quality of the solution). A formal definition of performancc models a communication network with asymmetric links. Now,
guarantee is as follows. Let r he a class of problems (such as construct an undirected graph G’ = (V,E’) (note that G and G‘
SPN) and P E r he a problem instance. Let A(P) denote the have the same set of vertices) such that for every pair of direct-
cost of the solution found by algorithmA and OPT(P) denotc ed links ( U , v ) and (v. U ) in G, there is a corresponding undi-
the cost of the optimal solution. We define the performance rected link ( U , v ) in G’ which has a cost equal to the sum of the
guarantee of algorithmA as II, = maxp,riA(P)lOPT(P)}. In costs of the directed links ( U , v ) and ( v , U ) in G. Thus, given a
other words, if the performance guarantee of an algorithm is group-shared multicast tree, say T,in G , we can construct the
cqual to p, then for all problem instances P E r, thc approxi- corresponding multicast tree, say T,in G’, and vice versa. Now,
mate solution is guaranteed to he at most p times costlier it is easy to verify that T i s a minimum-cost group-shared multi-
than the optimal solution. While most approximation algo- cast tree in G if and only if T is a Steiner tree in G‘. Similarly,
rithms for SPN have a pcrformance guarantee of 2, to the it can be shown that there is a one-to-one correspondence
bcst of our knowledge, none of the known approximation between a source-specific multicast tree in G which employs
algorithms have a performance guarantee better than 1116 bidirectional links and a source-specific multicast tree in G .
[12]. In the following subsections, we examine the six proper- Next, wc cxamine the problem of finding a source-specific
ties of a multicast tree that were mentioned at the beginning multicast tree which employs unidirectional links (note that
of this section, paying more attention to the higher-priority this problem cannot be reduced to SPN). Such a multicast
properties, particularly cost and delay. trec can he modeled using a source-rooted directed Steiner
tree (DST), as follows [17].
Cost Optimization Let G = (V,E ) be a directed graph, C a cost function, M
Approximation algorithms for optimizing the cost of a multi- the multicast group, and s E M the source nodc. Lct inde-
cast tree employ different kinds of heuristics [13-161. Recall gree(v) denote the in-degree of node v, and let outdegree(v)
that if the multicast group consists of all the nodes in the denote the out-degree of node v in the directed graph G. Let
graph, the problem reduces to the well-known minimum span- T = (Vr,ET) he a DST of G, where VTL V,ET i E , and M c
ning tree problem. Thus, it is no surprise that some approxi- [Link] a directed path exists in T from s to every node in M
mation algorithms are based on t h e so-called minimum - {s) such that t’v E VT - (s}, indegree(v) = 1, indegree(s) =
spanning tree heuristic. One such approximation algorithm 0; t’v E VT- (M - i s ) ) , outdegree(v) B 1, and thc cost of the
which was proposed by Kou, Markowsky, and Berman (hence- directed tree CT = Z(u, cut,is thc minimum of all such
forth referred to as KMB) [13] is examined below. directed trees of G. In otier words, a DST is a minimum-cost
KMB consists of five steps. First, using the nodcs in thc directed tree, rooted at sources, containing the destination
multicast group, we construct an undirected closure graph GI; nodes M - i s ) with all links directed away from s.
thus, for every node pair ( U , v ) in the multicast group M, GI Recall that in the Undirected vcrsion of thc Steiner tree
has an edge (U. v ) , such that the weight of the edge (c’.,,) is prohlcm, wc wcrc able to develop many simple algorithms
equal to the weight of the shortest path (d,<,,)between nodes U which had a constant performance guarantee of 2. For the
and v in G. Second, we find the minimum spanning tree of thc DST problem, the existence of an approximate algorithm with
closure graph GI. Third, we construct graph Gz by replaciug a constant performance guarantee ,is as unlikely as P = N P
each link in the spanning tree of G I by the corrcsponding (171. Thus, the asymmetry in the directed graph prevents us
shortest path in G. Next, we find the minimum spanning tree from finding a good approximate solution for the DST prob-
Tz of graph Gz, Finally, we construct the multicast tree TMby lem. We formalize the notion of asymmetry of a graph by
deleting links in Tz, if necessary, in such a way that all the defining the maximum link asymmetry as follows [17]:
leaves in TMbelong to the multicast group. The m m i m u m link asymmetry Y,,,(G) of a graph G = ( V ,
Figure 6a shows a graph G and the multicast group M E ) is the maximum ratio of the costs between the two directed
(shaded nodes). Figure 6h shows thc corrcsponding undirect- links of a link pair. That is,
ed closure graph with thick lincs corresponding to the mini-
mal spanning tree T I(after applying steps 1 and 2 from
above). Finally, Fig. 6c shows the Steiner tree in thick lines
~

94 IEEE Network 1anuarylFehm;~ry2000

W Figure 7. Delay optimization examples: a) a shoitest-path tree rooted at the source node CAI; b) ail optimum center-based tree roofed
at the center node TX The multicast group [Link] of nodes (CAI, TX, 1 1 NY). The cost of a shortest-path tree is 7, and the average
[Link] delay is 2.33. The cost of the center-bared tree is 5, and the averagegroup-shared delay is 2.67.

node and v is a multicast nodc. Now, tlic shortcst-pith multicast

trcc is oblained by removing all thc loops in [Link] Fig. 7a, thc
shortcst paths from source CAI to dcstinatious ?;U,IL, aiid NY
arc CAl-CA2-TX, CAI-WA-IL, and CA1-UT-MI-NY, respec-
tively. Thus, the cost of the shortcst-path tree is 7, and it consists
of links ( C A I , CAZ), (CAZ, T X ) , (CA1, W A ) , (WA, U>),( C A I ,
UT),(UT, !I), and (MI, NY), as shown in Fig. 7a.
As inentioncd bcforc, finding a multicasl tree which opti-
mizes the averagc group-shared delay (DG) is NP-complete,
although polynomial-time approximation algorithms exist
which have a constant performancc gmirantcc. One such algo-
rithm finds an optimum centcr-based tree which is defined as
follows. Let T, be the shortcst-path multicast tree rooted at
node v and DCLhe the avcragc group-shared delay of T,,.
Then an optimum ccntcr-based tree is defined as the shortest-
path tree with the minimum value of DGT This tree can easily
be found in polynomial time by computing thc DGTvalues for
all nodes v E G, and taking the minimum. An optimum cen-
ter-based trcc has a performance guarantee of 2, that is, the
average gmup-shared delay of an optimum center-bascd tree
is guarantccd to be within two times an optimum group-
shared delay [19]. Note that the root of the shortcst-path tree
may not be a multicast member; it may be any node in the
graph. If wc choose the center only from thc multicast mem-
bers, the performance guarantee of such a ccntcr-based lree is
3 [19]. Figure 7b shows an optimum center-based tree. Thc
cmter is TX, and the avcriige group-shared delay is 2.67.
The CostDeiay lrade-off
In thc previous 1wo subsections, wc studicd algorithins for
uptimizing lhe cost and dclay of a multicast routing trcc. In
this subsectioii we examinc thc prohlem or Iinding a source-
where P&, v ) is the delay of the path from sources to multi- specific multicast tree which attempts to optimizc both cost
cast node v in the multicast tree. Similarly, the averagc group- and delay. In general, a single multicast trcc cannot hevc
shared delay, DG, of a multicast tree is defined as miiiimum cost and minimum dclay. For example, i f s is the
source of a multicast connection aiid T i s the Steiner trcc
I found by the KMB algorithm, the average source-spccific
DC=- OS,, (3)
IMI" t M dclay (with respect to sourcc s) of Tis hounded from above
by (IMI +
I ) / 2 timcs the minimum average sourcc-spccific
where OS, is the average source-specific dclay (with respect to delay [20]. Similarly, thc shortest-path tree optiniizcs the
source v ) of the multicast tree. source-spccific dclay (with respect to sourcc s), but it can bc
Thc problem of finding a source-specific multicast tree I MI timcs costlier than the Steincr trcc, although empirical
which minimizes DS, has a simple solution, dcscribed below. data suggests that, on an avcragc, the shortest-path trcc may
On thc othcr hand, the problem of fi~idiiiga group-sharcd only be sligktly (20 pcrcent) costlier than thc Steiner trcc
multicast tree which minimizes thc value of DG is NP-cam- foiind by approximation algorithms such a s KMB [XI]. On
plete [MI, and will be discusscd later in this subscction. t h e othcr hand, the averagc source-specific delay of an
An optimum source-specific delay multicast tree (for both approximation algorithm, w c h as KMB, is typically larger'
unidirectional and bidirectional link cases) is also called tlic
shortest-path tree and is defined as follows. Lct s be the source of
a source-specificmulticast tree and SP(s, v ) bc the shortest-path 'Note rhnt ihese [Link] assrime llrnt e w y link has the fume cost arid
from s to node v t M - {s). Construct a graph Gsr by taking delay value.^ (i.e., if the cost of U h k i , x,~ liten the delay of the link micit
the union of all thc shortest paths SP[s, v), where s is the sourcc also be x).

IEEE Nctwork * JanualylFchruaty 2000 95

(50 pcrccnt) than the avcragc source-specific delay of thc specific tree is identified by the tuple (source-address, mulfi-
shortest-path multicast tree [21]. cusf-address). Thus, if nodc B belongs to M multicast groups,
Thus, it is natural to ask if an algorithm exists to improvc cacli of which have S sources, its multicast routing table will
the source-specific dclay characteristics of a multicast trcc pro- have at least M x S entrics - onc cntry for cach source in
duced by an approximation algorithm such as KMB. One such each multicast group. Now, sincc thc numhcr of sources in a
algorithm, which is described below, is bascd on the following multicast group may he quite large, a multicast routing proto-
intuition. Givcn an optimum-cost (or ncar-optimum-cost) col bascd on sourcc-spccific trces is not as scalahle as a multi-
Steiner trec, if wc find the multicast dcstination for which the cast routing protocol bascd on center-based trees [22, 231.
delay in tlic Steiner tree differs thc most from the delay of the
corrcsponding shortest path, and connect this destination to Dynamic Multicast Groups
thc sonrcc by the shortest path, wc can decrease the averagc Multicast groups are dynamic in nature; that is, new mcmbcrs
sourcc-spccific delay. Thus, if Pd(s,v ) is the delay of the path may join the multicast group and existing memhers leavc at
in tlic optimum-cost (or ncar-optimum-cost) Steiner tree from diffcrcnt points in time. Thus, a good multicast routing algo-
source s to multicast dcstination v, and if SP(s, v ) is the short- rithm should not only allow multicast memhers to join and
est-path delay from nodc s to nodc v, then the rollowing rcprc- lcavc the multicast tree in a seamless fashion; it should also
seiits 1.44 - 1 different tradc-off algorithms, parameterized by cnsurc that a join or leave event does not requirc widcsprcad
the variable i, whcrc i = 1, ..., [MI - 1. changes in the routing tables in thc nctwork. Morcovcr, the
* Do i times: quality of a multicast tree (cost, delay, ctc.) should not degrade
S t e p I: Find v E M - Is} which maximizes Pd(s, v ) - SP(s, v). hecause of a join or lcave cvcnt.
-Stcp 2: Replace the path from s to v in tlie Steiner tree by Thc following algorithm tries to minimize the cost of a nml-
the shortest path from s to v. ticast trcc for a dynamic multicast group [24]. Let T h e a mul-
If we assume that every link has the same cost and delay ticast routing tree. First, let us consider a join event. Lct U hc
values, the above method gcncrates Steiner trees within ii nodc that is to be included in the multicast tree. Lct v hc ii
c m o f thc optimum source-specific delay and cost values node in the multicast trec, and Ict d,,,. bc thc distance of the
for some constant c 1201. shortest path from nodc U to nodc v in thc nctwork. Let w t
(0, 0.5) he a real-valucd cnnstant. Also, Ict cach multicast tree
Scalability contain a special nodc, say z. Now, coiincct node U to the
In ordcr to support multicast applications ovcr largc nctworks, node v in the multicast trec which minimizcs thc valne of (1 -
thc multicast routing algorithm should he scalahlc, that is: w)d,,, + wfvz, If w = 0, thcn thc algorithm is greedy (i.e., it
For a nctwork with a large numbcr of nodcs, finding a mulli- connects nodc U to thc ncarcst node in the multicast tree),
cast tree should rcqnire little time and Sew resources pcr nodc. while if w = 0.5, then the algorithm connects nodc U to the
* It should be possihle for a large number of multicast trees special node (z) by the shortest path. In case of a lcave event,
to cocxist without requiring an unreasonahlc amount of we simply remove thc nudc from the multicast tree if it is a
routing information at each nodc. leaf nodc; uthcrwisc, wc rcmovc the nodc from the multicast
This subsection examincs thcsc two properties of a scalahle group hut not from the tree. Empirical results show that a
multicast algorithm. valuc for w in the neighborhood of 0.3 yields tlic bcst rcsnlts
One methnd to catcgorize multicast routing algorithms is iis (i.e., the quality of the multicast trcc does not dctcriorate
follows: even arter numerous join and leavc cvcnts) [24].
Algorithms that require global knowlcdgc of the network
topology Survivability
Algorithms that rcquirc partial knowledge of the network It is wcll known that a communication network failure can
topology have an extremely crippling effect 0 1 1 today's socicty. In the
For cxamplc, if we employ the KMB algorithm, each node future, as morc applications cmploy multicast routing, a
rcqnires global knowledge of the nctwork topology in order to strong nccd will cmcrgc for algorithms that can be employed
compntc the closure graph. On thc othcr hand, if we employ by snwivablc multicast routing protocols.
the center-hased-tree algorithm, cach nodc only needs to know A survivahlc routing protocol is designcd so that it can sur-
the next hop along thc shortcst path to every destination (which vivc multiplc link (or node) failures; that is, in the cvent of
is exactly thc information contained in the unicast routing multiplc link (or node) failures, the routing protocol reroutcs
tahle). In general, algorithms which require global knowledgc thc conncction(s) so as to minimize tlie networkwidc data
of thc nctwork topology are not as scalahlc as thosc which loss. Unicast routing protocnls cmploy various rcrouting algo-
rcqnirc partial knowledge of the network topology. rithms to provide survivability against multiplc link (or node)
The second charactcristic of a scalable multicast algorithm tccliniqucs can bc broadly classified into two
is that it should bc possihlc for a large number of multicast cxtcgorics: protection and restoration. In protection, cxtra nct-
trees to cncxist withont requiring large routing tablcs at cach work resources are reserved during tlie conncction sctup
nodc. Givcn that every source and every dcstination has its phase in order to implemcnt survivability. Thc nctwork
own unique address, if the nctwork has a large numher of resources nscd for protcctioii may bc rcscrvcd sepamtely for
nodes, it is impossihlc to storc routing information for every cach failnrc sccnario; alternatively, the resources used for pro-
destination. Hence, to rcdncc tlic size o f the rontiiig tahles, tection may bc shared among diffcrent failure scenarios. In
large networks oftcn usc a hierarchical addressing scheme. In rcstoration, tlic nctwork resources are dynamically reassigned
a hierarchical addressing schcmc, routing is pcrformcd by i n the event ol a failurc. Usually packct-switchcd networks
inspecting only a portion of the destination addrcss; thns, a cmploy restoration to implement survivability. Routing Infor-
single entry in the routing tablc is sufficicnt for routing to a mation Protocol (RIP) and Opcii Shortest Path First (OSPF)
large number of destinations. For multicasting, it is difficult (if are cxamplcs of protocols that implement restoration on IP
not inipossihlc) to construct such a hierarchical addressing nctworks. To the best of our knowledge, we are not awdrc of
scheme. Thus, if nodc A hclongs to N multicast trees, the any multicast routing protocol that employs an algorithm
multicast routing tablc at nodc A has at least N entries - one dcsigncd spccifically to provide survivahility for multicast con-
entry for each multicast group. On thc nthcr hand, it sourcc- nections. We helieve that this topic nccds furthcr research.

96
 Notc that multicast routing protocols bascd on an underly- switchcs translates to a n upper limil on the dcgrce of the
ing unicast routing protocol are as survivahlc as the underly- nodes i n the multicast k e .
ing unicasl routing protocol. For examplc, an iinplementalion Thc problem of finding an optimum multicast k c such
of thc Distance-Vector Multicast Routing Protocol (DVMRP) that lhc dcgrcc of cvciy nude in thc tree is less than a certain
nmy employ unicast routcs in tlic underlying nctwork to per- valuc is callcd thc degree-constrained multicast rree problem
form multicast routing. Thus, in tlie event of a failure, if tlic [27], and it can bc iiiodclcd using thc d e g r e e - c ~ i i , s t ~ ~Stein-
;~,e~
unicast routing tahles are updated appropriately, DVMRP will crprohlern in networlis (DCSPN) [ZS] a s fnllnws. Let n(v) hc
also function correctly. On the otlicr hand, if a multicast rout- the degrec constraint at node v, and let dcg(v) denotc thc
ing protocol is independent of the unicast routing protocol, it degree of uodc v in thc dcgrcc-constreined multicast trcc.
must implcment its own restoration mcchanism. Then, Cor all nodcs U in tlic dcgrcc-constrained multicast Lrcc,
deg(u) 5 n(v). Thus, given the dcgrce coiislraint x ( v ) Cor a11
Fairness nodes in the nctwork, a dcgrcc-constrained Steiner trcc, T , is
Since multiple snurccs and destiuations participate in multi- a trcc which spins a11 lhe nodes in M siicli that t'v E T, dcg(v)
cast routing, thc issuc of fairness ariscs naturally. In this suh- 5 n(u), and thc cost of the lree is minimum among all possible
scctinn wc consider two lairncss issues. T h e [irst issuc multicast trees satisrying tlic dcgrcc constraint.
conccrns the variation OS the delay valucs from tlic sourcc to DCSPN is NP-coniplctc (2x1. I n k ~ tIiiidiirg
, a n y multicast
diffcrcnt dcstinatioiis in a source-spccific multicasl tree. For tree (not necessarily tlic minimum-cost multicast trcc) which
cxiimplc, during a teleconfcrcncc, it may he important that satisfies lhc dcgrcc constr;iint is iin NP-completc prohlcm.
the spcaker he heard by a11 participants within a hounded
timc; otherwise, the teleconfcrcncc may lack thc fccl of an Multicast Routing Protocols
intcractivc discussion. Similarly, in a distrihutcd g a m , the
ability to access multicast data hcfore olhers may rcsult in an In this scctinn we providc a n overview OS various multicast
unfair competitive advantage. Thus, some applications (c.s., protocols employcd on thc Intcrnct. For a delailcd discussion
tclcconferencing) may impose an upper bound on thc dclay ol lhese and otlicr multicast routing prolocols, the readcr may
from the source Lo a destination in a mullicast trcc, whilc Icier Lo some rcccnt hiinks 011 multiciisting 15, 61.
other applications (e.g., distributcd games) may impose a Multicasting nvcr a large portion OS the Inlernct was first
morc stringent condition nn the dclay: not only should the demonstrated in March 1992 [291 ovcr the Multicast Back-
dclay be bounded, hut thc variation of the delay fnr diffcreiil hone (MUnnc). Thc Mbonc is a virtual network on top of the
(source, destination) pairs should also bc bounded. First, wc Internet which provides a midticast facility to the Intcrnct.
fiirmulatc tlic problem of finding a delay-bounded Steiner tree The MBone can he vicwcd a s a collcctioii of "islands" that
(DBST): then, we formulate the problem of finding a deluy- support multicasting within their domains. Each island h a s a
bounded and deluy-variation:bouiided niiiltic7<ist tr& host machine which cxccutes tlic mrouted inulticast routing
(DVBMT). daemon. The mrouted dacmons (in diffcrcnt islands) are con-
The prbhlcm of finding a DBST can hc formulated as f n - nccted to one anollier via point-til-point IP connections
lows [XI. Lct G = (V,E ) he an undircctcd graph and l e t s E (callcd tunnels) over tlic Intcrnct. In this mmncr, the mroutcd
M he t h e snurce of a sourcc-specific multicast trcc. Let the daemons and the tnnnels that ciiiincct them form a virtual
delay of link ( U , I,) bc denoted D,,,., a positivc integer. Given nclwork on top (if the Intcrnct.
an integer delay tolcraiicc A, a constrained multicasl tree Tis Multicasling on the Internet is implcmcntcd by cmplnying
dcfincd as a tree, rooled at s, that spans tlie nodes in M such three types nf prntocols. Thc first typc oC prolocol is cmploycd
that for each node t E M - {s}, thc dclay on the path from s by a host to join m d Icavc a multicasl group. An examplc of
to t is hounded from abovc by A. Thus, lor each I E M - b}, this typc of protocol is tlic Inlcrnet Group Managcnicnt Pro-
, ~ , < A. Now,
if P,, is the path in T from s to t , thcn E<,,,, , I ~ ~ ,D,,, tocnl (IGMP) [30]. Thc sccond typc nf protocol is callcd a
the DBST is defined as a constrained multicast trcc spwuiing Multicast Intcrkir Gatcway Prolocol (MIGP) and is cmployed
M such that E(6z, c,," is minimized. by multicast routcrs to cnahle multicast communication within
Thc problcm ol finding a DVBMT cdn he Sorinulatcd as fol- an aulononious systcm (AS).x Soinc examples of MlGPs arc
lows [26]. Lets E M he thc sourcc of a source-spccific multicast DVMRP [31], Multicast Extensions lor OSPF (MOSPF) 132,
tree, let D,,,, be the dclay of link ( U , v). let A bc thc dclay toler- 331, Corc-Based Trcc (CBT) [22, 231, and Protocol-Indcpcn-
ance, and le1 F he thc dclay variation lolerancc. Now, t h e dent Multicast (PIM) 134, 3.51. The third type of protocol is
DVBMT is a trcc Tspuining M, such that if P,,(s, v ) is the delay cmploycd by [Link] ti) allow multicast communication
of the path from s to v in thc multicast tree, thcn for all v E M - across AScs. An cxamplc of this typc nf protocol is the Bordcr
{s}, P&, v ) 5 A, and for all pairs ol multicast nodcs 11, v E M - Gatcway Multicasl Protocol (BGMP) [36]. Figure 8 shnws
{,TI, [P&, U) -P&, v ) I < 6. In other words, in the multicasl lrec, how the three lypcs oS protocols intcropcratc i n a network
the distancc from the source lo each multicast node should bc (furthcr details nn Fig. 8 can bc found later).
Icss thin the delay tolerance (A) and, for tiny two multicast nudes Of all thc multicast routing algorilhms discussed in tlic pre-
(say ii and v). tlie difSerence betwccn thc dclay Cram thc sourcc to vious seclion, only a fcw arc used i n praclice. DVMRP and
thcsc twn nodcs (IP<,(s,U ) - P&, U ) I ) should he less than the MOSPF employ a shortcst-path trcc,ln while CBT and BGMP
delay variation tolcrance (6). DVBMT is NP-complele [Zh]. In cinploy a cenler-hascd trcc to rontc multicast packets. PIM
1261, a polynomial-time heuristic algorithm is describcd for can employ cithcr a ccntcr-bascd tree or a revcrsc-shurtest-
DVMBT. Of course, sincc DVBMT is NP-complctc, a polynomi-
al-time algorithm may fail to find a solution even if one exists.
The sccond fairness issue concerus tlic data duplication
rcsponsihility OS a multicast router. Kccall tlial in multicast
routing, some routcrs nccd to duplicate packcts. In a hctero-
gcneous high-speed network, somc switches may not havc
multicast capability. Evcn if 1111the switches havc mnlticast
capability, by limiting t h e number of copies made, we may
rcduce thc load at a switch. Limited dala duplication at the

97
path tree (how PIM determines which type of tree to use will those with 1110 as their high-ordcr four bits). Thc addres [Link]
be discussed later). We believe that the two main reasons why is guarantccd not to be assigned to any group, and [Link] is
other, more-sophisticated multicast routing algorithms, such assigncd to thc pcrmancnt group of all IP hosts (including gatc-

-
as KMB, are not used arc:
Ease of implementation: Recall that the shortcst-path tree
(or the center-bascd tree) is composed of two or more
ways). This address is uscd to address all multicast hosts on the
directly cvnncctcd nctwork. There is no multicast address (or any
other 1P addrcss) for all hosts on the entire Internet.
shortest paths. Since unicasl routing algorithms also com- lGMP enables a multicasl router to kcep track of multicast
pute shortcst paths, the multicast routing protocol can be group membership information by employing two types of
implemcnted as an add-on to thc unicast routing protocol. IGMP messages: host membership query and host membership
* Efficient computation of the multicast tree: Note that finding report. Hosl membership qucry mcssagcs arc periodically sent
the shortest-path or centcr-based tree requires much lcss by multicast routers to discovcr which multicast groups have
computation and mcmory resources than arc rcquircd hy members o n thc attachcd local network. Queries arc
other sophisticated algorithms, such as KMB. addrcsscd to thc all-hosts group (address [Link]). Hosts
The remainder of this section is orfanizcd as follows. We respond to a query by generating host membership rcports
examine IGMP and describe Revers-Path Multicast (RPM), (hcrcaftcr called join-group reports), reporting each multicast
a multicast routing algorithm employed by DVMKP. We also group to which thcy belong. When a host joins a ncw group, it
examine DVMRP, MOSPF, CBT, PIM, and BGMP, respec- imnicdiately sends a join-group report for that group rather
tively. We also briefly examine two ncw protocols, called than wait for a query. When a host decides to lcavc a group, it
EXPRESS [37] and Simple Multicast [38]. sends a Icavc-group report to the multicast router.
Internet Group Management Protocol Reverse-Path Multicast
IGMP [30] is a protocol that is implcmented within the IP RPM [39] enables multicast routing over a network of routers
module of a host," and it extends the host's IP iniplemcnta- connected to each othcr via commuuication links.'2 In order
tion to support multicasting. IGMP is used between a host to understand RPM, we must first examine a rclated protocol
and the immediately neighboring multicast router. callcd Reiwse-Path Forwarding (RPF) [40] which broadcasts a
Multicast groups are identificd by class D IP addresses (is., packet over a network.

" A host is any Intemet hort orgateway other than those acting us mu& l 2A corrmzrurication link muy be a ~egiilarpoint-lo,oint link, a tunnel,
cu3t Ioutem WR LAN which i.y shared by the two routem.

98 IEEE Network * JanuaryFcbruary 2000

 In RPF, a routcr 11 forwards a restrict thc scopc of a n IP multi-
hroadcast packet originating at cast.13
source s if and only if it arrivcs via In DVMRP, multicast routcrs
the shortest path from thc router R perivdically exchange routing table
back to thc source S (i.e., the revcrsc update messages with their ncigh-
path). The router forwards the pack- hors. Thcsc updatcs arc indepen-
et on all incident links except thc dent of those generated by any
one on which the packet arrivcd. In interior gatcway protocol, such as
this manncr, RPF accomplishes a RIP, which maintains routing tablcs
broadcast by flooding packets for unicasting. Based on thc
throughout the network. It should updates from its neighbors, a routcr
be noted that in RPF, multiple W Table 1. An example of lTL va1ue.s and thL'
'cr scopes. builds its multicast routing tables.14
copics of the same packet may bc A sample routing table for a
scnt over a sinele
~~~~~ ~ ~~
o~ link.
~~ ~~~~
~
DVMRP router is shown in Table
In RPM, three modifications are made to the RPP algorithm: 2. Since a multicast routing tablc is hascd on thc RSPT, the
Each multicast routcr R knows its child links, thc links with Sourcc and From gatcway columns in Table 2 correspond to
routcrs whose next-hop routcr along the shortest path to thc Dcstination and Gateway columns in a normal unicast
the source is 11. In other words, cach link in the nctwork routing table.
has a unique parcnt router relative to each possiblc source
S . The sct of routcrs and the corresponding child links form Muiticast Extensions to OSPF
a spanning trcc rootcd at source S called thc reverse-short- MOSPF [32, 331 multicasts packcts ovcr thc shvrtcst-path tree
est-path tree (RSPT). Thus, by cmploying the RSPT, a within an AS. OSPF [33] is a unicast routing protocol that is
source node (S) can broadcast a packet to all thc nodcs in employed within an AS. Each OSPF rvutcr maintains a database,
the network. called the link state database, which describes thc network topolo-
* Each multicast router knows whether its subnetwork (i.e., gy of the AS. In OSPF, the link state datahase is constructed
thc LAN to which it is conncctcd) has any hosts which arc using five different types of link-state advcrtisements (LSAs). An
mcmbcrs of a multicast group. Rccall that a multicast LSA is a "unit of data describing the local state of a router or
router collecls this infnrmation bv emolovine IGMP. network. For a router, this iiicludcs thc statc of the rvutcr's inter-

sage to its parcnt (ncxt-hip'router to the source'). Notc that adding a new typc of LSA, ciillc~thcgroupmembership LSA. In
the prune messagcs implcment on-demand pruning of the MOSPF, a router uscs IGMP to kccp track of group member-
RSPT. ship infvrmatinn on its attached network, and distributes this
Thus, RPM consists of two steps. First, a multicast packct is information by flooding thc group mcmbcrship LSA throughout
broadcast over the RSPT. Whcn thc packet reaches a multi- the AS. Thus, by employing the link statc database, a router can
cast router Cor whom nonc of thc child links have mcmhcrs compute a shortest-path trcc for any nodc in thc AS. When a
that hclong to the multicast address, a prune message for that router receives a multicast packet, it computcs a shortest-path
(source, group) pair is generatcd and scnt back to the parcnt trce rooted at the source of the packet and forwards thc packet
mullicast routcr (Fig. 9). Whcn a member of a ncw group on accordingly. In order to conscrvc CPU and memory resourccs at
a particular link appcars, a cancellation mcssagc to undo the the routcr, thc shortcst-path tree is computed on demand (is!., at
cffcct of tlic pruiic message is sent out by thc router. the arrival of the first multicast packet).
A prunc message includes an age ficld which is initialized by
thc router that generates the rcport and increased in value by ~- ______-~
cvcry routcr along the reverse shortcst path that receives the
rcport. When the age of a prunc mcssagc reaches a threshold,
T,,,axagcr
it is discarded. This idca ensures that the prunc mcs-
sages in the nelwork do not contain outdated information.
Distance-Vector Multicasf Routing Protoco/
DVMRP [31] is a mullicast routing protocol which employs
RPM to send multicast packcts ovcr a communication network.
DVMRP assigns cach communication link a metric and a
threshold. The metric specilies the routing cost of the link and is
uscd for constructing the RSPT. Thc thrcshold is the minimum
timc to live (TTL) a multicast packct nccds to be forwardcd
onto a given link. In this way, the threshold can he uscd to limit
the geographical scope (is., region) of a multicast transmission.
Table 1 lists somc convcntional TTL values that are used lo

j3 Since TTL-based scoping is coarse-grained, it may not be appropriate

11. .~~
for certain applicatiurrs. I n such cmes, we may employ Adminirtrutively W Figure 9. An example of how a prune me,ssage is generated and
S c q ~ dIP Multicast [4I. 421 which is a mo,rfine-@ned ,scoping method sent to the parent router. Nodes 6 and Isend a prime message
than the TIL-based method. to theirparent node (31, which in turn generates a prune mes-
sage and sends it to itrparent node (1). Node 2 does notgener-
The algoyithm employed in DVMRP to build routing tabks ii vey simi- ate a prune message because it received a prune message from
lar lo the one employed by HIP. Forfirther details, please refer to {.?I, 431, only one of its two child nodes.

IEEE " w o r k JanualyIFcbrua~y2000 99

 ~

Table 2. An example of a DVMRProuting table. are as follows:

*PIM-SM employs per-group rendezvous points
(RPs) for receivers to meet new sources. RPs
Core-Based Fee JCBTJ are used by senders to announce their existence, and by
In a very largc network with many simultaneously active mul- receivers to learn ahout new scnders of a group.
ticast groups, DVMRP can become very costly for two rea- * Routers with local (or downstream) members join a PIM-
sons. First, the broadcast of thc initial packet in RPM can he SM tree using explicit join messages. (In contrast, DVMRP
costly if the network consists of tens of thousands of nodes, of gencratcs the multicast tree by pruning an RSPT.)
which only a few are a part of the multicast group. Second, Now we explain how a host can join a group and receive
each multicast routcr has to keep track of every (source, multicast packets using PIM-SM. We assume that routers lis-
group) pair, which may become unwieldy as the number of ten to a well-known multicast group to obtain the group-
multicast groups and sources increase. The CBT architecture address-to-RP bindings. Thus, every router knows the
[22, 231 is an attempt to overcome the shortcomings of designated RPs for a given multicast gronp. When a host sig-
DVMRP. In CBT, branchcs cmanate from a single node nals that it wants to join a PIM-SM multicast group (i.e., by
known as the core of the tree. These branches are made up of sending an IGMP messagc), its first-hop router sends a PIM-
other routers, so-called on-tree routers, which form a shortest join message toward the RP advertised for the group. Proccss-
path between a host’s dircctly attached router and the core. ing of this messagc by intermediate routers sets up the
The CBT architccture significantly decreases the size of multi- multicast tree branch from the RP to the host. When a source
cast routing tables at the routcrs, because it requires tho starts to send data packets to a multicast group, it sends a PIM
routcrs to Store routing information for every active group register message, piggyhacked on the data packet, to the RI’s
(i.e., per tree) as opposcd to storing information for every for that group. The RP responds by sending a join toward the
active (source,group) pair. Once the core router is chosen, sourcc. Processing of these messages by intermediate routers
route13 that arc not on the CBT can send a JOINREQUEST sets up a packet delivery path from the source to the RP.
message to the core router which sets up the routing tables at If source-specific (i.e., RSPT) distribution trees are desired,
every hop. In this manner, CBT creates a bidirectional shared a router sends a PIM-join message toward the source. Figure
center-based tree. 10 shows the steps involved in joining a multicast group and
setting up a source-specific distribution tree. A router can
Protocoi-Independent Multicast send a PIM prune message to tear down a connection. A
In attempting to rcmove the shortcomings of DVMRP, CBT router may want to tear down a connection because it is no
inadvertently introduces some new problems. In [34] CBT’s longer a part of a multicast group, or it has a RSPT connec-
shortcomings were analyzed, and a new protocol, called PIM tion to the source and does not need the connection to the
[34, 44, 451, was presented, which addresses these shortcom- RP anymore. Note that when a routcr joins the source through
ings. To understand the motivation behind PIM, we must first an RSPT, it effectively changes the path for all its downstream
understand the limitations of CBT. routers and hosts.
As seen in the previous section, CBT uses a singlc dclivery
tree for each group, routed at a core router and shared by all Border Gateway Multicast Protocol
nodes which send packets to the multicast destination set. As Border routers employ BGMP [36] to facilitate multicast com-
desired for sparse groups, CBT does not exhibit the occasion- munication across different ASes. BGMP consists of two com-
al broadcasting behavior of RPM. However, CBT does so at ponents, namely, t h e M I G P component and t h e B G M P
thc expcnse of imposing a single shared tree for each multi- component. The border router employs the MIGP component
cast group. This can result in conccntration of all the sourccs’ to participate in the MIGP protocol within the AS, and the
traffic on a singlc link. In [34], this phenomenon is referred lo BGMP component to construct a bidirectional center-based
as traffic concentration. This is one of thc limitations of CBT, tree with other border routers. In BGMP, the root of the cen-
or any protocol that imposes a singlc shared tree per group ter-based tree is an entire AS rather than a single router. The
for distribution of all data packcts. root AS of a multicast address is the AS which has claimed
It is evident, though, that both types of trees (RSPTs and the multicast address hy employing a global multicast address
CBTs) have their advanlilgcs. For example, shared trees may allocation Drotocol such as the Multicast Address Set Claim
perform very well for a large number of low-data-rate sources (MASC) [46] protocol.
which are sprcad over a large geographical area (e.g., resource BGMP uses TCP as its transvort protocol. Border routers
discovery applications), while RSPTs may be better suited for set up a TCP connection between tlkmselves, and exchange
high-data-rate sources (e.g., real-time vidcoconferencing). An BGMP messages. When group memberships change, border
analysis of these trade-offs can he found in [21]. It would he routers send incremental joiniprune updates to one anothcr.
ideal to flexibly support both types of trees within one multi- Since the shortest path from a multicast source to a destina-
cast architccture, so the selection of tree typcs becomes a con- tion can he diffcrent than the path imposed by the shared
figuration decision within a multicast protocol. tree, BGMP also allows a border router to attach a source-
PIM is designed to addrcss thc two issues stated above: to specific branch to the center-based tree.
avoid the overhead of broadcasting packets when group mem- Figure 8 demonstrates how BGMP enables multicasting
hers sparsely populate the Internet, and to do so in a way that across ASes. Shown in the figurc are six ASes (or domains),
suppurla good-quality distribution trees for heterogeneous each of which eniploys a different MIGP. Consider a multicast
applications. Thus, PIM has two modes of operation: PIM group consisting of sources S1 and S2 in domains B and A,
Dcnsc Mode (PIM-DM), which employs an RSPT (similar to respectively, and three multicast receivers R1, R2, and R3 in
DVMRP), and PIM Sparse Modc (PIM-SM), which employs domains D, A, and E, respectively. We assume that domain B

100 -
IEEE Network JanuaryiFcbruary 2000
 or& in which they &cur

is the root domain of the multicast group. Thus, the ccnter- of the source node. Unauthorized hosts can bc restrictcd by
based tree crcatcd by BGMP for the multicast group is rooted associating a key with a channel which is initialized by the
at domain B and is shown by thick bidirectional lincs in thc source. EXPRESS also provides a mechanism for counting
figurc. Since domain C does not have any nodes belonging Lo the numhcr of rcccivcrs in a multicast group.
the multicast group, it is not included in thc bidirectional mul- Simple Multicast [38] addresses the problem of allocating a
ticast tree. Note that multicast packcts originating from globally uniquc multicast address to each group. It proposes
source B traverse domain F i n order to reach domains A and that each multicast group be referred to by the tuple (C, M),
E. Packets originating from sourcc S2 i n domain A reach whcrc C is the address of the core router of the mullicast tree
receiver R3 in domain E via thc bordcr router in domain F. and M is a multicast address. Simple Multicast builds bidircc-
Since border rnutcrs in domains A and E are directly conncct- tional shared trees rooted at the core node. Glohal addrcss
ed, rcccivcr R2 can set up a source-specific branch via the managemenl is not an issue bccnuso a multicast group is iden-
shortest path frnm source S2 to receiver R2 as shown by thc tified not only by the multicast address (class U address), but
dashed line. Now, reccivcr R 2 will receive packcts from also by the 11’ address of the core node.
sourcc S2 via the source-specific branch, and from other
sources via the ccutcr-bascd tree that was set up by BGMP.
Conclusion
Recent fiends Today, many multicast applications cxist, but thc irnplementa-
In this section we briefly discuss two rccently proposed prnto- tion of these applications is not necessarily efficient becausc
cols which cxtcnd thc IP multicast model. In the currcnt IP today’s WANs were designed to mainly support point-to-point
multicast model, a multicast address (class D address) refers to (unicast) communication. In the future, as multicast applica-
a group of hosts. Some of the problems with this modcl arc: tions become more popular and bandwidth-intcnsivc, there
* There is no mechanism to cstimatc the multicast grvup sizc. will emerge a pressing need to provide efficient multicast sup-
* Thcrc is 110 mechanism to restrict unauthorized senders port on WANs. I n this work wc prcscnt a tutorial-cum-survey
ircccivcrs) from sendine (receiving) traffic to (from)
~, the of some vf the important topics in multicasting. First, we

-
I~

multicast ~ r o u p . study the problem of multicast routing algorithms which are

The model reouires a nrotocol such as MASC to allocate Fundamcntal to all of the research in multicasting, such as
glohally unique multicak addresses. what is n multicast tree, and how does one con,Wnct it? We euu-
The two protocols discussed in this section attempt to address mcrate the properties of a good multicast tree, and note that
the above problems by extending the IP multicast model. finding such a multicast trce can he very diSficult. Since most
Explicitly Requested Singlc Source (EXPRESS) [37] algorithms that have been proposed in the literature mainly
extends IP multicast to support thc chnnnel model. A channcl focus on optimizing one of the properties of a good multicast
consists of one cxplicitly dcsiguated source and zero or morc trcc, we categorize the algorithms based on the property they
subscribers. EXPRESS huilds source-specific trccs for each attcmpt to optimize and separatcly cxaminc cach catcgory, viz.
channel which are addressed by thc tuple (C, M),where C is low cost, low delay, scalability, support for dynamic multicast
the source’s IP addrcss and M is 21 multicast address. Note groups, surviv;tbility, and fairness.
that EXPRESS does not require a protocol to allocate global- Next, we examine various protocols that arc employed on
ly unique multicast addrcsscs, bccausc a chauiiel is identiIied the Intcrnet, namely, Internet Group Management Protocol
not ouly by the multicast address, hut also by thc IP address (IGMP) 1301, Distancc-Vcctor Multicast Routing Protocol

IEEE Network * JanuarylFehruary 2000 101

(DVMRP) [31], Multicast Extcnsions for OSPF (MOSPF) E31 T . Ballordie, "Core Eosed Trees (CBT version 2) Multicost Routing," RFC
[32, 331, Corc-Bascd Tree (CBT) [ZZ, 231, Protocol-lndepen- 2189, Sept. 1997.
[24] B. M. Woxmon, "Routing of Multipoint Connections," IEEE JSAC, vol. 6,
dent Multicast (PIM) [34,35], and Border Mnlticast Gatcway Dec. 1 9 8 8 , ~ 1617-22.
Protocol (BGMP) 1361. We also briefly examinc rcccntly pro- 1251V. P. KmpelE,J. C. Parquale, ond G. C. Polyros, "Multicost Routing for M h -
posed protocols, namely, Explicitly Requested Singlc Sourcc medio Communication," IEEE/ACAI Tram Net., vol. I , June 1993, p 28&92.
(EXPRESS) [37] and Simple Multicast [38]. [26] G. N. Rourkor and I. Boldine, "Multicod Routing with End~To-EnJDelay and
Delay Variation Conrtroinlr," IEEE JSAC, "01. 15,Apr. 1997, pp. 346-56.
Rcscarch in multicasting covers a vcry wide range of topics. [271 F. Bausr and A. Vorma, "Degree-ConstrainedMulticasting in Poinl-To-Point
In this tutorial we covcr thc topics wc believe are most relc- Network$," Proc. IEEE INFOCOM '95,"01. 4, Apr. 1995, pp. 39-76,
vant to a general networking
; " k u a thus, additional topics I281 S. Vas, "Problems wifh Generalized Steiner Problems," Algorilhmico, vol.
such as reliable multicast, multicast support for mobilc com- 7, no. 2, 1992-1993, pp. 333-35.
I291 H. Erikmon, "MBone: the Mullicort Backbone," Common. ACM. vol. 37,
puting, laycrcd encoding techniques for multicast audio and ~~

Aug. 1994, pp. 54-60.

video applications, multicast in optical networks, and multicast [30l S. E. Deering, "Host exlensions for IP multicorting," RFC I 1 12, Aug. 1989.
address managemcnt were not covered. Future rescarch top- [31] D. Waitrman and C. Partridge, "Dirtonce Vector Multicast Routing Prola-
ics, solutions to which will be very desirable, includc sccure col," RFC 1075, Nov. 1988.
I321 J. Moy, "Multicast Routina Extensions for OSPF," Commun. ACM, vol. 37,
group communication, snrvivahility in multicast routing, and
congestion control in reliable multicast protocols.
. . " ~ . ._,
.I ~~ "I "_I.

1331J. Moy, "OSPF V i r i o n 2," RFC 2328, Apr. 1998.

[34] S. Deering et 01.. "The PIM Architecture for Wide-Area Mullicort Routing,"
References IEEE/ACM rroos. N~I..d.4. A ~ I 996.
~ . DD. I 53-62,
[ I ] P. Winter, "Steiner Problem in Networks: A Sulvey," Networks, vol. 17, Sum- I351 D. Estrin et al., "Prolocol Iid&endent M h c a r t - S'm r r e Mode IPIM-SMI:
~~

mer 1987. pp. 129-67. Protocol rpecificalion," RFC 2362, June 1998.
[2] C. Diot, W. Dabbour, and J. Crowcroh, "Multipoint Communication: A Sur- 1361 D. Tholer, D. Estrin, and D. Meyer, "Border Gateway Multicast Protocol
vey of Prolocols. Functions. and Mechanisms." IEEE JSAC. vol. 15. Aor. IBGMP]: Protocol Specification." Internel draft, Aug. 1998.
1697, p. 277-90. . . H. Holbrook ond D. Cheriton. "IP Multicost Channels: EXPRESS Suooort for
1371
[3] G. Cork and E. W. Biersack, "Sulvey of Error Recovery Techniques for IP- Large-Scole Single-Source Applications," Proc., ACM SIGCOMM '99, Sept.
Bared Audio-Visual Mullicart Applicalionr," IEEE Network, vol. I I , .....
1999

Nov./Dec. 1997,7'' 24-36. 1381 R. Perlmon et al., "Simple Mullicart: A Design for Simple, towoverhead
Multicast," Internel dmh, Feb. 1999.
. . Obrocrka. "Mu ticast Tranroort Protocols: A Sulvev' and Taxoonomv."
141 K. ,. IEEE [39] S. E. Deerin and D. R. Cheriton, " M u l h r t Rouling in Datagram lnferneworkr
[Link]., vol. 36, Jon. 'I 998, pp. 94-1 02.
151 S. Paul, Multicmtihg on he lntemet and L Applimtion$, Borfon, MA: KIwer, 1998. and Extendd LANs," ACM Trans. Comp. Sys., vol. 8, May 1983, p 85 I IO
[6] C. K. Miller, Multicad Networking and Applications, Reading, M A Addiron- 1401 Y. K. D a b and R. M. Metcolfe, "Reverse Pafh Forwarding ofBro&&t
Werlev. 1999 Packets," C m m w ACM, vol.21, pp, 104&48, Dec. 1978.
~~ ~
.... 1411 D. Meyer, "Administratively Scoped IP Mullicart," RFC 2365, July 1998.
[7] R. M. Korp, Complexity of Computer Computotionr, New Y o r k Plenum,
1972, p . 85-103. 1421 D. Thaler, M. Handley, and D. Eilrin, "The Internet Mullicort Address Allo-
P
181 R. E. Belmon, "On CI Routing Problem." Qtdy. AppliedMdh., "01. 16, 1958,
pp. 87-90.
cution Architecture," lnternef dmh, Oct. 1999.
(431 C. Hedrick, "Routing Informotion Protocol," RFC 1058, June 1988.
[ 9 l E. W. Diikstro, "A Note on Two Problems in Connection with Grophs," 1441 S. Deering et al., "Pralocol Independent Multicast-Dense Mode (PIM-DM):
Numer. Moth., vol. 1, 1959, pp. 269-71 Protocol Specification." Internet droh, June 1999.
[IO] J. 8. Krukral, "On the Shortest Spanning Subtree of A Graph ond the Tmv- [45] D. Erbin et al., "Protocol lnde endent Multicast Sparre Mode (PIM-SM):
ding Solermon Problem," Proc. Amer. Moth. Soc., vol. 7, 1956, pp. 48-50. Job,
Protocol Specification," Internet Oct. 1999.
[ I 11 R. C. Prim, "Shortest Connection Networks ond Some Generolizotions," Bell I461 D. Estrin el al., "The Multicart Addrerr-Set Claim (MASC) Protocol," Internet
Sys. Tech. J., vol. 36, 1957, p 1389-1401 drah, Aug. 1999.
[ I 2 1 A. Z. Zelikovrky, "An 11b-Approximation Algorithm for the Network
Steiner Problem," Algorilhmico, vol. 9, May 1993, pp. 463-70. Bioqraphies
[ I 31 1. Kou, G. Markowsky, ond 1. Bermon, "A Fast Algorithm for Steiner &S~HASRABUDDHE(rohorrab@[Link]) received a [Link]. degree from
Trees," Acta Informoka,vol. 15,no. 2, 1981, pp. 141-45. fhe Indian InslitUte of Technology, Konpur, in 1992, and an [Link]. degree from
[I41 J. Plesnik, "A Bound for the Steiner Tree Problem in Graphs," Mothematica Ihe lndion Inititale of Technology, Modrar, in 1994. He is currendy a research os+
Slovaca, vol. 31, no. 2, 1981, pp. 155-63. Ian! with the Networks Research Labomtory at the University of California, Davis,
[ I 5 1 V. J. Ro wadSmith and A. Clare, "On Finding Steiner Vertices," Net- where he is workin toward a Ph.D. degree. His research inieresis include orchitec-
works, YO( 16, Fall 1986, pp, 283-94. tarer and protocolr~orWDM local-area and wide-area optical networks.
[I61 H. Takahashi and A. Motwyoma, "An Approximate Solution for the Steiner
Problem in Graphs," Mothemotica Joponica, vol. 24, no. 6, 1980, pp. 573-77. BISWANATHMUKHEPJEE [MI (mUkherjee~[Link]~.~d"l received o [Link]. (Honr)
[ I 71 S. Ramonathan, "Multicast Tree Generation in Networks with Arymmelric degree from !he Indian Inititule of Technology, Kharagpur, in 1980 and CI Ph.D.
Links," IEEE/ACM Trans. Net., vol. 4, Aug. 1996, pp. 5 8 - 6 8 , de ree from the University of Washington, SeoHle, in June 1987. At Warhin tan
[I81 D. S. Johnson, J. K. Lenrtra, and A. H. G. R. Kan, "The Complexity of fhe h e h d CI GTE Teaching Fellowship and a General Electric Foundation Fel%w-
Network Design Problem," Networks, vol. 8, Winter 1978, pp. 279-85. ship. In Jul 1987 he ioined the University of California, Davis, where he hor
[ I 91 D. W. Wall, "Mechanisms for Broodcart and Selective Broadcast," Ph.D. been a proLrror of computer science since July 1995, and choir of the Comput-
fheiir, Stanford Univ., June 1980. er Science De ortment since September 1997. He is co-vrinnei of poper owaids
120) K. Bharath-Kumar ond J. M. JaL, "Routing to Multiple Destinations in Compub presented at tte I991 and I 9 9 4 Notional Computer Security Conferences. He
er Neworks," IEEE Trans. Commun., vol. COM-31, Mar. 1983, pp. 343-51 sewel on the editorial boards of IEEE/ACM Tronractioor on Networking, IEEE
[21] 1. Wei ond D. Estrin, "The Trade-offs of Multicost Trees ood Algorithms," Network, ACM/Boltzer Wireless Information Networks IWINET), Journal o i
Proc. I d C o d Comp. Common. Networks, Sept. 1994. High-speed Networks, and Photonic Network Communications. He rewed os
[22l T. Bollordie, P. Francis, and J. Crowcroft, "Core Bored Trees (CBTJ: An Technical Program Choir of IEEE INFOCOM '96. He is aulhor of the textbook
Architecture for Scalable Inter-Domain Multicost Rouling," Comp. Commun. Opticol Communication Networks (McGrow-Hill, 19971. His r e m m h interests
Rev., "01. 23, Oct. 1993, pp. 85-95. include lightwove networks, network security, and wireless networks.

102 IEEE Nchvork * JanualyiFehruary 2000