A comparison of reliable multicast protocols.
We analyze the maximum throughput that known classes of reliable multicast transport protocols can attain. A new taxonomy of reliable multicast transport protocols is introduced based on the premise that the mechanisms used to release data at the source after correct delivery should be decoupled from the mechanisms used to pace the transmission of data and to effect error recovery. Receiver-initiated protocols, which are based entirely on negative acknowledgments (NAKS) sent from the receivers to the sender, have been proposed to avoid the implosion of acknowledgements (ACKS) to the source. However, these protocols are shown to require infinite buffers in order to prevent deadlocks. Two other solutions to the ACK-implosion problem are tree-based protocols and ring-based protocols. The first organize the receivers in a tree and send ACKS along the tree; the latter send ACKS to the sender along a ring of receivers. These two classes of protocols are shown to operate correctly with finite buffers. It is shown that tree-based protocols constitute the most scalable class of all reliable multicast protocols proposed to date.
Introduction
The increasing popularity of real-time applications supporting
either group collaboration or the reliable dissemination
of multimedia information over the Internet is making the
provision of reliable and unreliable end-to-end multicast services
an integral part of its architecture. Minimally, an end-
to-end multicast service ensures that all packets from each
source are delivered to each receiver in the session within a
finite amount of time and free of errors and that packets are
safely deleted within a finite time. Additionally, the service
may ensure that each packet is delivered only once and in the
# Supported in part by the Office of Naval Research under Grant N00014-
94-1-0688, and by the Defense Advanced Research Projects Agency
(DARPA) under grant F19628-96-C-0038
Correspondence to: B.N. Levine
order sent by the source. Although reliable broadcast protocols
have existed for quite some time [3], viable approaches
on the provision of end-to-end reliable multicasting over the
Internet are just emerging. The end-to-end reliable multicast
problem facing the future Internet is compounded by its current
size and continuing growth, which makes the handling
of acknowledgements a major challenge commonly referred
to as the acknowledgement (ack) implosion problem.
The two most popular approaches to end-to-end reliable
multicasting proposed to date are called sender-initiated
and receiver-initiated. In the sender-initiated approach, the
sender maintains the state of all the receivers to whom it
has to send information and from whom it has to receive
acknowledgments (acks). Each sender's transmission or re-transmission
is multicast to all receivers; for each packet
that each receiver obtains correctly, it sends a unicast ack
to the sender. In contrast, in the receiver-initiated approach,
each receiver informs the sender of the information that is
in error or missing; the sender multicasts all packets, giving
priority to retransmissions, and a receiver sends a negative
acknowledgement (nak) when it detects an error or a lost
packet.
The first comparative analysis of ideal sender-initiated
and receiver-initiated reliable multicast protocols was presented
by Pingali et al. [17, 18]. This analysis showed
that receiver-initiated protocols are far more scalable than
sender-initiated protocols, because the maximum through-put
of sender-initiated protocols is dependent on the number
of receivers, while the maximum throughput of receiver-initiated
protocols becomes independent of the number of
receivers as the probability of packet loss becomes negligi-
ble. However, as this paper demonstrates, the ideal receiver-initiated
protocols cannot prevent deadlocks when they operate
with finite memory, i.e., when the applications using the
protocol services cannot retransmit any data themselves, and
existing implementations of receiver-initiated protocols have
inherent scaling limitations that stem from the use of messages
multicast to all group members and used to set timers
needed for nak avoidance, the need to multicast naks to
all hosts in a session, and to a lesser extent, the need to store
all messages sent in a session.
This paper addresses the question of whether a reliable
multicast transport protocol (reliable multicast protocol, for
short) can be designed that enjoys all the scaling properties
of the ideal receiver-initiated protocols, while still being
able to operate correctly with finite memory. To address this
question, the previous analysis by Pingali et al. [17, 18, 22]
is extended to consider the maximum throughput of generic
ring-based protocols, which organize receivers into a ring,
and two classes of tree-based protocols, which organize receivers
into ack trees. These classes are the other three
known approaches that can be used to solve the ack implosion
problem. Our analysis shows that tree- and ring-based
protocols can work correctly with finite memory, and that
tree-based protocols are the best choice in terms of processing
and memory requirements.
The results presented in this paper are theoretical in
nature and apply to generic protocols, rather than to specific
implementations; however, we believe that they provide
valuable architectural insight for the design of future reliable
multicast protocols. Section 2 presents a new taxonomy of
reliable multicast protocols that organizes known approaches
into four protocol classes and discusses how many key papers
in the literature fit within this taxonomy. This taxonomy
is based on the premise that the analysis of the mechanisms
used to release data from memory after their correct reception
by all receivers can be decoupled from the study of the
mechanisms used to pace the transmission of data within
the session and the detection of transmission errors. Using
this taxonomy, we argue that all reliable unicast and multicast
protocols proposed to date that use naks and work
correctly with finite memory (i.e., without requiring the application
level to store all data sent in a session) use acks to
release memory and naks to improve throughput. Section 3
addresses the correctness of the various classes of reliable
multicast protocols introduced in our taxonomy. Section 4
extends the analysis by Pingali et al. [17, 18, 22] by analyzing
the maximum throughput of three protocol classes:
tree-based, tree-based with local nak avoidance and periodic
polling (tree-NAPP), and ring-based protocols. Section
5 provides numerical results on the performance of the
protocol classes under different scenarios, and discusses the
implications of our results in light of recent work on reliable
multicasting. Section 6 provides concluding remarks.
new taxonomy of reliable multicast protocols
We now describe the four generic approaches known to date
for reliable multicasting. Well-known protocols (for unicast
and multicast purposes) are mapped into each class. Our
taxonomy differs from prior work [8, 17, 18, 22] addressing
receiver-initiated strategies for reliable multicasting in that
we decouple the definition of the mechanisms needed for
pacing of data transmission from the mechanisms needed for
the allocation of memory at the source. Using this approach,
the protocol can be thought as using two windows: a congestion
window (cw ) that advances based on feedback from
receivers regarding the pacing of transmissions and detection
of errors, and a memory allocation window (mw ) that
advances based on feedback from receivers as to whether
the sender can erase data from memory. In practice, proto-010101000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111000000000000000000111111111111111111111111111000000000000000000111111111111111111111111111000000000000000000000000111111111111111111111111000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111
Ack
Source Receiver
Nak
Fig. 1. A basic diagram of a sender-initiated protocol
cols may use a single window for pacing and memory (e.g.,
TCP [10]) or separate windows (e.g., NETBLT [4]).
Each reliable protocol assumes the existence of multi-cast
routing trees provided by underlying multicast routing
protocols. In the Internet, these trees will be built using such
protocols as DVMRP [6], Core-Based Trees (CBT) [1], Ordered
Core-Based Trees (OCBT) [20], Protocol-Independent
Multicast (PIM) [7], or the Multicast Internet Protocol (MIP)
[14].
2.1 Sender-initiated protocols
In the past [17, 18], sender-initiated protocols have been
characterized as placing the responsibility of reliable delivery
at the sender. However, this characterization is overly
restrictive and does not reflect the way in which several reliable
multicast protocols that rely on positive acknowledgements
from the receivers to the source have been designed.
In our taxonomy, a sender-initiated reliable multicast protocol
is one that requires the source to receive acks from all
the receivers, before it is allowed to release memory for the
data associated with the acks. Receivers are not restricted
from directly contacting the source. It is clear that the source
is required to know the constituency of the receiver set, and
that the scheme suffers from the ack implosion problem.
However, this characterization leaves unspecified the mechanism
used for pacing of transmissions and for the detection
of transmission errors. Either the source or the receivers can
be in charge of the retransmission timeouts!
The traditional approach to pacing and transmission error
detection (e.g., TCP in the context of reliable unicasting) is
for the source to be in charge of the retransmission timeout.
However, as suggested by the results reported by Floyd et
al. [8], a better approach for pacing a multicast session is
for each receiver to set its own timeout. A receiver sends
acks to the source at a rate that it can accept, and sends a
nak to the source after not receiving a correct packet from
the source for an amount of time that exceeds its retransmission
timeout. An ack can refer to a specific packet or a
window of packets, depending on the specific retransmission
strategy. A simple illustration of a sender-initiated protocol
is presented in Fig. 1.
Notice that, regardless of whether a sender-driven or
receiver-driven retransmission strategy is used, the source is
still in charge of deallocating memory after receiving all the
acks for a given packet or set of packets. The source keeps
packets in memory until every receiver node has positively
acknowledged receipt of the data. For a sender-initiated pro-
tocol, if a sender-driven retransmission strategy is used, the
sender "polls" the receivers for acks by retransmitting after
a timeout. If a receiver-driven retransmission strategy is
used, the receivers "poll" the source (with an ack) after
they time out. 1
It is important to note that, just because a reliable multi-cast
protocol uses naks, it does not mean that it is receiver-
initiated, i.e., that naks can be the basis for the source to
ascertain when it can release data from memory. The combination
of acks and naks has been used extensively in the
past for reliable unicast and multicast protocols. For exam-
ple, NETBLT is a unicast protocol that uses a nak scheme
for retransmission, but only on small partitions of the data
(i.e., its cw ). In between the partitions, called "buffers", are
acks for all the data in the buffer (i.e., the mw ). Only upon
receipt of this ack does the source release data from mem-
therefore, NETBLT is really sender-initiated. In fact,
naks are unnecessary in NETBLT for its correctness, i.e.,
a buffer can be considered one large packet that eventually
must be acked, and are important only as a mechanism to
improve throughput by allowing the source to know sooner
when it should retransmit some data.
A protocol similar to NETBLT is the "Negative Acknowledgments
with Periodic Polling" (NAPP) protocol [19].
This protocol is a broadcast protocol for local area networks
(LANs). Like NETBLT, NAPP groups together large partitions
of the data that are periodically acked, while lost
packets within the partition are naked. NAPP advances the
cw by naks and periodically advances the mw by acks.
Because the use of naks can cause a nak implosion at the
source, NAPP uses a nak avoidance scheme. As in NET-
BLT, naks increase NAPP's throughput, but are not necessary
for its correct operation, albeit slow. The use of periodic
polling limits NAPP to LANs, because the source can still
suffer from an ack implosion problem even if acks occur
less often.
Other sender-initiated protocols, like the Xpress Transfer
Protocol (XTP) [21], were created for use on an internet, but
still suffer from the ack implosion problem.
The main limitation of sender-initiated protocols is not
that acks are used, but the need for the source to process all
of the acks and to know the receiver set. The two known
methods that address this limitation are: (a) using naks instead
of acks, and (b) delegating retransmission responsibility
to members of the receiver set by organizing the receivers
into a ring or a tree. We discuss both approaches
subsequently.
2.2 Receiver-initiated protocols
Previous work [17, 18] characterizes receiver-initiated protocols
as placing the responsibility for ensuring reliable packet
delivery at each receiver. The critical aspect of these protocols
for our taxonomy is that no acks are used. The receivers
send naks back to the source when a retransmission
Of course, the source still needs a timer to ascertain when its connection
with a receiver has failed.010011010000000000000000000000000000000000000000111111111111111111111111111111111111111111111111110000000000000000001111111111111111111111111110000000000000000001111111111111111111111111110000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111
Nak
Source Receiver
Fig. 2. A basic diagram of a receiver-initiated protocol
is needed, detected by either an error, a skip in the sequence
numbers used, or a timeout. Receivers are not restricted from
directly contacting the source. Because the source receives
feedback from receivers only when packets are lost and not
when they are delivered, the source is unable to ascertain
when it can safely release data from memory. There is no
explicit mechanism in a receiver-initiated protocol for the
source to release data from memory (i.e., advance the mw ),
even though its pacing and retransmission mechanisms are
scalable and efficient (i.e., advancing the cw ). Figure 2 is a
simple illustration of a receiver-initiated protocol.
Because receivers communicate naks back to the source,
receiver-initiated protocols have the possibility of experiencing
a nak implosion problem at the source if many receivers
detect transmission errors. To remedy this problem, previous
work on receiver-initiated protocols [8, 17, 18] adopts the
nak avoidance scheme first proposed for NAPP, which is a
sender-initiated protocol. Receiver-initiated with nak avoidance
(RINA) protocols have been shown [17, 18, 22] to have
better performance than the basic receiver-initiated protocol.
The resulting generic RINA protocol is as follows [17, 18].
The sender multicasts all packets and state information, giving
priority to retransmissions. Whenever a receiver detects
a packet loss, it waits for a random time period and then multicasts
a nak to the sender and all other receivers. When a
receiver obtains a nak for a packet that it has not received
and for which it has started a timer to send a nak, the receiver
sets a timer and behaves as if it had sent a nak.
The expiration of a timer without the reception of the corresponding
packet is the signal used to detect a lost packet.
With this scheme, it is hoped that only one nak is sent back
to the source for a lost transmission for an entire receiver
set. Nodes farther away from the source might not even get
a chance to request a retransmission. The generic protocol
does not describe how timers are set accurately.
The generic RINA protocol we have just described constitutes
the basis for the operation of the Scalable Reliable
Multicasting (SRM) algorithm [8]. SRM has been embedded
into an internet collaborative whiteboard application called
wb. SRM sets timers based on low-rate, periodic "session
messages" multicast by every member of the group. The
messages specify a time stamp used by the receivers to estimate
the delay from the source, and the highest sequence
number generated by the node as a source. 2 The average
Multiple sources are supported in SRM, we focus on the single-source
case for simplicity.
bandwidth consumed by session messages is kept small (e.g.,
by keeping the frequency of session messages low). SRM's
implementation requires that every node stores all packets,
or that the application layer store all relevant data.
We note that naks from receivers are used to advance the
cw , which is controlled by the receivers, and the sequence
number in each multicast session message is used to "poll"
the receiver set, i.e., to ensure that each receiver is aware
of missing packets. Although session messages implement
a "polling" function [19], they cannot be used to advance
the mw , as in a sender-initiated protocol, because a sender
specifies its highest sequence number as a source, not the
highest sequence number heard from the source. 3
In practice, the persistence of session messages forces the
source to process the same number of messages that would
be needed for the source to know the receiver set over time
(one periodic message from every receiver). Accordingly,
as defined, the basic dissemination of session messages in
SRM does not scale, because it defeats one of the goals of
the receiver-initiated paradigm, i.e., to keep the receiver set
anonymous from the source for scaling purposes.
There are other issues that limit the use of RINA protocols
for reliable multicasting. First, as we show in the next
section, a RINA protocol requires that data needed for re-transmission
be rebuilt from the application. This approach
is reasonable only for applications in which the immediate
state of the data is exclusively desired, which is the case of
a distributed whiteboard. However, the approach does not
apply for multimedia applications that have no current state,
but only a stream of transition states.
Second, naks and retransmissions must be multicast to
the entire multicast group to allow suppression of naks. The
nak avoidance scheme was designed for a limited scope,
such as a LAN, or a small number of Internet nodes (as it
is used in tree-NAPP protocols, described in the next sec-
tion). This is because the basic nak avoidance algorithm
requires that timers be set based on updates multicast by every
node. As the number of nodes increases, each node must
do increasing amount of work! Furthermore, nodes that are
on congested links, LANs or regions may constantly bother
the rest of the multicast group by multicasting naks. Approaches
to limit the scope of naks and retransmission are
still evolving [8]. However, current proposals still rely on
session messages that reach all group members.
Another example of a receiver-initiated protocol is the
"log-based receiver-reliable multicast" (LBRM) [9], which
uses a hierarchy of log servers that store information indefinitely
and receivers recover by contacting a log server.
Using log servers is feasible only for applications that can
afford the servers and leaves many issues unresolved. If a
single server is used, performance can degrade due to the
load at the server; if multiple servers are used, mechanisms
must still be implemented to ensure that such servers have
consistent information.
The ideal receiver-initiated protocol has three main advantages
over sender-initiated protocols, namely: (a) the
source does not know the receiver set, (b) the source does
3 Our prior description of SRM [11, 12] incorrectly assumed that session
messages contained the highest sequence number heard from the source.
We thank Steve McCanne for pointing this out.
not have to process acks from each receiver, and (c) the
receivers pace the source. The limitation of this protocol is
that it has no mechanism for the source to know when it
can safely release data from memory. Furthermore, as we
have argued, the practical implementations of the receiver-initiated
approach fail to provide advantages (a) and (b). The
following two protocol classes organize the receiver set in
ways that permit the strengths of receiver-initiated protocols
to be applied on a local scale, while providing explicit
mechanisms for the source to release memory safely (i.e.,
efficient management of the mw ).
2.3 Tree-based protocols
Tree-based protocols are characterized by dividing the receiver
set into groups, distributing retransmission responsibility
over an acknowledgement tree (ack tree) structure
built from the set of groups, with the source as the root of
the tree. A simple illustration of a tree-based protocol is presented
in Fig. 3. The ack tree structure prevents receivers
from directly contacting the source, in order to maintain
scalability with a large receiver set.
The ack tree consists of the receivers and the source
organized into local groups , with each such group having a
group leader in charge of retransmissions within the local
group. The source is the group leader in charge of retransmissions
to its own local group. Each group leader other than
the source communicates with another local group (to either
a child or the group leader) closer to the source to request
retransmissions of packets that are not received correctly.
Group leaders may be children of another local group, or
minimally, may just be in contact with another local group.
Each local group may have more than one group leader to
handle multiple sources. Group leaders could also be chosen
dynamically, e.g., through token passing within the local
group.
Hosts that are only children are at the bottom of the
ack tree, and are termed leaves. Obviously, an ack tree
consisting of the source as the only leader and leaf nodes
corresponds to the sender-initiated scheme.
Acknowledgments from children in a group, including
the source's own group, are sent only to the group leader.
The children of a group send their acknowledgements to
the group leader as soon as they receive correct packets,
advancing the cw ; we refer to such acknowledgements as
local acks or local naks, i.e., retransmissions are triggered
by local acks and local naks unicast to group leaders by
their children. Similar to sender-initiated schemes, the use
of local naks is unnecessary for correct operation of the
protocol.
Tree-based protocols can also delegate to leaders of sub-trees
the decision of when to delete packets from memory
(i.e., advance the mw ), which is conditional upon receipt of
aggregate acks from the children of the group. Aggregate
acks start from the leaves of the ack tree, and propagate
toward the source, one local group at a time. A group leader
cannot send an aggregate ack until all its children have
sent an aggregate ack. Using aggregate acks is necessary
to ensure that the protocol operates correctly even if group
leaders fail, or if the ack tree is partitioned for long periods
Group
Leaf
Source
Fig. 3. A basic diagram of a tree-based protocol
of time [12]. If aggregate acks are not used, i.e., if a group
leader only waits for all its children to send local acks before
advancing the mw , then correct operation after group
leaders fail can only be guaranteed by not allowing nodes
to delete packets; this is the approach used in all tree-based
protocols [13, 16, 24] other than Lorax [12]. The Lorax protocol
[12] is the first tree-based protocol to build a single
shared ack tree for use by multiple sources in a single ses-
sion, and to use aggregate acks to ensure correct operation
after hosts in the ack tree fail.
The use of local acks and local naks for requesting
retransmissions is important for throughput. If the source
scheduled retransmissions based on aggregate acks, it would
have to be paced based on the slowest path in the ack tree.
Instead, retransmissions are scheduled independently in each
local group.
Tree-based protocols eliminate the ack-implosion prob-
the source from having to know the receiver set,
and operate solely on messages exchanged in local groups
(between a group leader and its children in the ack tree).
Furthermore, if aggregate acks are used, a tree-based protocol
can work correctly with finite memory even in the
presence of receiver failures and network partitions.
To simplify our analysis and description of this protocol,
we assume that the group leaders control the retransmission
timeouts; however, such timeouts can be controlled by the
children of the source and group leaders. Accordingly, when
the source sends a packet, it sets a timer, and each group
leader sets a timer as it becomes aware of a new packet. If
there is a timeout before all local acks have been received,
the packet is assumed to be lost and is retransmitted by the
source or group leader to its children.
The first application of tree-based protocols to reliable
multicasting over an internet was reported by Paul et al. [15],
who compared three basic schemes for reliable point-to-
multipoint multicasting using hierarchical structures. Their
results have been fully developed as the reliable multicast
transport protocol (RMTP) [13, 16]. While our generic protocol
sends a local ack for every packet sent by the source,
RMTP sends local acks only periodically, so as to conserve
bandwidth and to reduce processing at each group leader, increasing
attainable throughput.
We define a tree-NAPP protocol as a tree-based protocol
that uses nak avoidance and periodic polling [19] in the
local groups. Naks alone are not sufficient to guarantee
reliability with finite memory, so receivers send a periodic
positive local ack to their parents to advance the cw . Note
that messages sent for the setting of timers needed for nak000000111111001111001110000000000001111111111111111
Receiver Set
Source
Nak
Ack
Fig. 4. A basic diagram of a ring-based protocol
avoidance are limited to the local group, which is scalable.
The tree-based multicast transport protocol (TMTP) [24] is
an example of a tree-NAPP protocol.
2.4 Ring-based protocols
Ring-based protocols for reliable multicast were originally
developed to provide support for applications that require an
atomic and total ordering of transmissions at all receivers.
One of the first proposals for reliable multicasting is the
token ring protocol (TRP) [3]; its aim was to combine the
throughput advantages of naks with the reliability of acks.
The Reliable Multicast Protocol (RMP) [23] discussed an
updated WAN version of TRP. Although multiple rings are
used in a naming hierarchy, the same class of protocol is
used for the actual rings. Therefore, RMP has the same
throughput bounds as TRP.
We base our description of generic ring-based protocols
on the LAN protocol TRP and the WAN protocol RMP. A
simple illustration of a ring-based protocol is presented in
Fig. 4. The basic premise is to have only one token site responsible
for acking packets back to the source. The source
times out and retransmits packets if it does not receive an
ack from the token site within a timeout period. The ack
also serves to timestamp packets, so that all receiver nodes
have a global ordering of the packets for delivery to the
application layer. The protocol does not allow receivers to
deliver packets until the token site has multicast its ack.
Receivers send naks to the token site for selective repeat
of lost packets that were originally multicast from the
source. The ack sent back to the source also serves as a token
passing mechanism. If no transmissions from the source
are available to piggyback the token, then a separate unicast
message is sent. Since we are interested in the maximum
throughput, we will not consider the latter case in this pa-
per. The token is not passed to the next member of the
ring of receivers until the new site has correctly received all
packets that the former site has received. Once the token is
passed, a site may clear packets from memory; accordingly,
the final deletion of packets from the collective memory of
the receiver set is decided by the token site, and is conditional
on passing the token. The source deletes packets only
when an ack/token is received. Note that both TRP and
RMP specify that retransmissions are sent unicast from the
token site. Because our analysis focuses on maximum attainable
throughput of protocol classes, we will assume that
the token is passed exactly once per message.
3 Protocol correctness
A protocol is considered correct if it is shown to be both
safe and live [2]. Given the minimum definition of reliable
service we have assumed, for any reliable multicast protocol
to be live, no deadlock should occur at any receiver or at the
source. For the protocol to be safe, all data sent by the source
must be delivered to a higher layer within a finite time. To
address the correctness of protocol classes, we assume that
nodes never fail during the duration of a reliable multicast
session and that a multicast session is established correctly
and is permanent. Therefore, our analysis of correctness focuses
only on the ability of the protocol classes to sustain
packet losses or errors. We assume that there exists some
non-zero probability that a packet is received error-free, and
that all senders and receivers have finite memory.
The proof of correctness for ring-based protocols is
given by Chang and Maxemchuk [3]. The proof that sender-initiated
unicast protocols are safe and live is available from
many sources (e.g., Bertsekas and Gallager [2]). The proof
does not change significantly for the sender-initiated class
of reliable multicast protocols and is omitted for brevity.
The liveness property at each receiver is not violated, because
each node can store a counter of the sequence number
of the next packet to be delivered to a higher layer. The
safety property proof is also essentially the same, because
the source waits for acks from all members in the receiver
set before sliding the cw and mw forward. Theorems 1 and 2
below demonstrate that the generic tree-based reliable multi-cast
protocol (TRMP for short) is correct, and that receiver-initiated
reliable multicast protocols are not live.
Theorem 1: TRMP is safe and live.
Proof. Let R be the set of all the nodes that belong to the reliable
multicast session, including a source s. The receivers
in the set are organized into a B-ary tree of height h. The
proof proceeds by induction on h.
For the case in which reduces to a non-hierarchical
sender-initiated scheme of
with each of the B receivers practicing a given retransmission
strategy with the source. Therefore, the proof follows
from the correctness proof of unicast retransmission protocols
presented by Bertsekas and Gallager [2].
For h > 1, assume the theorem holds for any t such that
must prove the theorem holds for some
Liveness. We must prove that each member of a tree of
height t is live. Consider a subset of the tree that starts at
the source and includes all nodes of the tree up to a height
of (t - 1); the leaves of this subtree are also group leaders
in the larger tree, i.e., group leaders of the nodes at the
bottom of the larger tree. By the inductive hypothesis, the
liveness property is true in this subtree. We must only show
that TRMP is live for a second subset of nodes consisting
of leaves of the larger tree and their group leader parents.
Each group in this second subset follows the same protocol,
and it suffices to prove that an arbitrary group are live.
The arbitrary group in the second subset of the tree constitutes
a case of sender-initiated reliable multicast, with the
only difference that the original transmission is sent from the
source (external to the group), not the group leader. Since
leaves can only contact the group leader, we must prove this
relationship is live. The inductive hypothesis guarantees that
the group leader and its parent is live.
Assume the source transmits a packet i at time c 1 , and
that it is received correctly and delivered at all leaves of
the arbitrary group at time c 2 . Let c 3 be the time at which
the group leader deletes the packet and advances the mw .
The protocol is live and will not enter into deadlock if
finite. The rest of the proof follows
from the proof by Bertsekas and Gallager [2] for unicast
protocols, where the group leader takes the place of
the source. Therefore, TRMP is live.
Safety. The safety of TRMP follows directly, because
our proof of liveness shows that any arbitrary packet i is
delivered at each receiver within a finite time. QED
Theorem 2. A receiver-initiated reliable protocol is not live.
Proof. The proof is by example focusing on the sender and
an arbitrary member of the receiver set R (where R # 1).
- Sender node, X , has enough memory to store up to M
packets.
Each packet takes 1 unit of time to reach a receiver node
Y . Naks take a finite amount of time to reach the sender.
- Let p i denote the i th packet, i beginning from zero. p 0
is sent at start time 0, but it is lost in the network.
sends the next (M - 1) packets to Y successfully.
sends a nak stating that p 0 was not received. The
nak is either lost or reaches the sender after time M
when the sender decides to send out packet pM .
store up to M packets, and it has not
received any naks for p 0 by time M , it must clear
assuming that it has been received correctly.
receives the nak for p 0 at time M
deadlocked, unable to retransmit p 0 . QED
The above indicates that the ideal receiver-initiated protocol
requires an infinite memory to work correctly. In prac-
tice, this requirement implies that the source must keep in
memory every packet that it sends during the lifetime of a
session.
Theorem 1 assumes that no node failures or network
traffic occur. However, node failures do happen in practice,
which changes the operational requirements of practical tree-based
protocols. For tree-based protocols, it can be shown
that deleting packets from memory after a node receives local
acks from its children is not live. Aggregate acks are
necessary to ensure correct operation of tree-based protocols
in the presence of failures. Lorax [12] is the only tree-based
protocol that uses aggregate acks and can operate with finite
memory in the presence of node failures or network
partitions.
4 Maximum throughput analysis
4.1 Assumptions
To analyze the maximum throughput that each of the generic
reliable multicast protocols introduced in Sect. 2 can achieve,
we use the same model as Pingali et al. [17, 18], which
focuses on the processing requirements of generic reliable
multicast protocols, rather than the communication band-width
requirements. Accordingly, the maximum throughput
of a generic protocol is a function of the per-packet processing
rate at the sender and receivers, and the analysis focuses
on obtaining the processing times per packet at a given node.
We assume a single sender, X , multicasting to R identical
receivers. The probability of packet loss is p for any
node.

Figure

5 summarizes all the notation used in this sec-
tion. For clarity, we assume a single ack tree rooted at a
single source in the analysis of tree-based protocols. A selective
repeat retransmission strategy is assumed in all the protocol
classes since it is well known to be the retransmission
strategy with the highest throughput [2], and its requirement
of keeping buffers at the receivers is a non-issue given the
small cost of memory. Assumptions specific to each protocol
are listed in Sect. 2, and are in the interest of modeling
maximum throughput.
We make two additional assumptions: (1) no acknowledgements
are ever lost, and (2) all loss events at any node
in the multicast of a packet are mutually independent.
Such multicast routing protocols as CBT, OCBT, PIM,
MIP, and DVMRP [1, 5, 7, 14, 20] organize routers into
trees, which means that there is a correlation between packet
loss at each receiver. Our first assumption benefits all classes,
but especially favors protocols that multicast acknowledge-
ments. In fact, this assumption is essential for RINA proto-
cols, in order to analyze their maximum attainable through-
put, because nak avoidance is most effective if all receivers
are guaranteed to receive the first nak multicast to the receiver
set. As the number of nodes involved in nak avoidance
increases, the task of successful delivery of a nak to all
receivers becomes less probable. Both RINA and tree-NAPP
protocols are favored by the assumption, but RINA protocols
much more so, because the probability of delivering naks
successfully to all receivers is exaggerated.
Our second assumption is equivalent to a scenario in
which there is no correlation among packet losses at receivers
and the location of those receivers in the underlying
multicast routing tree of the source. Protocols that can
take advantage of the relative position of receivers in the
multicast routing tree for the transmission of acks, naks,
or retransmissions would possibly attain higher throughput
than predicted by this model. However, no class is given
any relative advantage with this assumption.

Table

1 summarizes the bounds on maximum throughput
for all the known classes of reliable multicast protocols. Our
results clearly show that tree-NAPP protocols constitute the
most scalable alternative.
4.2 Sender- and receiver-initiated protocols
Following the notation introduced by Pingali et al. [17, 18],
we place a superscript A on any variable related to the
sender-initiated protocol, and N1 and N2 on variables related
to the receiver-initiated and RINA protocols, respec-
tively. The maximum throughput of the protocols for a constant
stream of packets to R receivers is [17, 18]
1/# A

Table

1. Analytical bounds
Protocol Processor requirements
p as a
con-
stant
Sender-initiated
[17,
O
Receiver-
initiated nak
avoidance
[17,
O
Ring-based (uni-
cast retrans.)
O
Tree-based O(B(1 - p)
Tree-NAPP O
# . (3)
Even as the probability of packet loss goes to zero, the
throughput of the sender-initiated protocol is inversely dependent
on R, the size of the receiver set, because an ack
must be sent by every receiver to the source once a transmission
is correctly received. In contrast, as p goes to zero,
the throughput of receiver-initiated protocols becomes independent
of the number of receivers. Notice, however, that
the throughput of a receiver-initiated protocol is inversely
dependent with R, the number of receivers, or with ln R,
when the probability of error is not negligible. We note that
this result assumes perfect setting of the timers used in a
RINA protocol without cost and that a single nak reaches
the source, because we are only interested in the maximum
attainable throughput of protocols.
4.3 Tree-based protocols
We denote this class of protocols simply by H1, and use
that superscript in all variables related to the protocol class.
In the following, we derive and bound the expected cost
at each type of node and then consider the overall system
throughput. To make use of symmetry, we assume, without
loss of generality, that there are enough receivers to form a
full tree at each level.
Without loss of generality, we assume that each local
group in the ack tree consists of B children and a group
leader. This allows us to make use of symmetry in our
throughput calculations. We also assume that local acks
advance the mw rather than aggregate acks, because by assumption
no receiver fails in the system. We assume perfect
setting of timers without cost and that a single nak reaches
the source, because we are only interested in the maximum
attainable throughput of protocols.
4.3.1 Source node
We consider first X H1 , the processing costs required by the
source to successfully multicast an arbitrarily chosen packet
Branching factor of a tree, the group size.
R - Size of the receiver set.
Time to feed in a new packet from the higher protocol layer.
Xp - Time to process the transmission of a packet.
Xa , Times to process transmission of an ack, nak, or local ack, respectively.
Time to process a timeout at a sender or receiver node, respectively.
Yp - Time to process a newly received packet.
Time to deliver a correctly received packet to a higher layer.
Ya , Yn , Y h - Times to process and transmit an ack, nak, or local ack, respectively.
Probability of loss at a receiver; losses at different receivers are assumed to be independent events.
r - Number of local acks sent by receiver r per packet using a tree-based protocol.
r - Number of acks sent by a receiver r per packet using a unicast protocol.
Total number of local acks received from all receivers per packet.
Mr - Number of transmissions necessary for receiver r to successfully receive a packet.
- Number of transmissions for all receivers to receive the packet correctly (for protocols A, N1 and N2);
Number of transmissions for all receivers to receive the packet correctly for protocols H1 and H2.
Processing time per packet at sender and receiver, respectively, in protocol w # {A, N1, N2, H1, H2, R}.
Processing time per packet at a group leader in tree-based and tree- NAPP protocols, respectively.
per packet at the token-site in ring-based protocols.
# w x - Throughput for protocol w # {A, N1, N2, H1, H2, R} where x is one of the source s, receiver (leaf) r, group leader h,
or token-site t. No subscript denotes overall system throughput.
X# , Y# - Times to process the reception and transmission, respectively, of a periodic local ack.
Fig. 5. Notation
to all receivers using the H1 protocol. The processing requirement
for an arbitrary packet can be expressed as a sum
of costs:
+(receiving acks)
where X f is the time to get a packet from a higher layer,
is the time taken on attempt m at successful transmission
of the packet, X t (m) is the time to process a timeout
interrupt for transmission attempt m, X h (i) is the time to
process local ack i, M H1 is the number of transmissions
that the source will have to make for this packet using the
H1 protocol, and L H1 is the number of local acks received
using the H1 protocol. Taking expectations, we have
What we have derived so far is extremely similar to Eqs. 1
and 2 in the analysis by Pingali et al. [17, 18]. In fact, we
can use all of their analysis, with the understanding that B is
the size of the receiver subset from which the source collects
local acks. Therefore, the expected number of local acks
received at the sender is
Substituting Eq. 6 into Eq. 5, we can rewrite the expected
cost at the source node as
Pingali et al. [17, 18] have shown that the expected number
of transmissions per packet in A, N1, and N2 equals
# . (8)
Because in H1 the number of receivers R = B, the expected
number of transmissions per packet in the H1 protocol is
which can be simplified to [17, 18, 19]
Pingali et al. [17, 18] provide a bound of E[M ] that we
apply to E[M H1 ] with
Using Eq. 11, we can bound Eq. 7 as follows
It then follows that, when p is a constant, E[X H1
O(B
4.3.2 Leaf nodes
Let Y H1 denote the requirement on nodes that do not have to
forward packets (leaves). Notice that leaf nodes in the H1
protocol will process fewer retransmissions and thus send
fewer acknowledgements than receivers in the A protocol.
We can again use an analysis similar to the one by Pingali
et al. [17, 18] for receivers using a sender-initiated protocol.
(receiving transmissions)
(sending local acks)
where Y p (i) is the time it takes to process (re)transmission i,
Y h (i) is the time it takes to send local ack i, Y f is the time
to deliver a packet to a higher layer, and L H1
is the number
of local acks generated by this node h (i.e., the number of
transmissions correctly received). Since each receiver is sent
transmissions with probability p that a packet will be
lost, we obtain
Taking expectations of Eq. 13 and substituting Eq. 14, we
have
Again, noting the bound of E[M H1 ] given in Eq. 11,
When p is treated as a constant, E[Y H1
4.3.3 Group leaders
To evaluate the processing requirement at a group leader, h,
we note that a node caught between the source and a node
with no children has a two jobs: to receive and to retransmit
packets. Because it is convenient, and because a group leader
is both a sender and receiver, we will express the costs in
terms of X and Y . Our sum of costs is
(receiving transmissions)
(sending local acks)
(collecting local acks)
Just as in the case for the source node, L H1 is the expected
number of local acks received from node h's children for
this packet, and L H1
h is the number of local acks generated
by node h.
We can substitute Eqs. 6 and 14 into Eq. to obtain
The first two terms are equivalent to the processing requirements
of a leaf node. The last two are almost the cost for
a source node. Substituting and subtracting the difference
yields
In other words, the cost on a group leader is the same as
a source and a leaf, without the cost of receiving the data
from higher layers and one less transmission (the original
one). Substituting Eqs. 12 and 16 into Eq. 20, we have
When p is a constant, E[H H1 which is the
dominant term in the throughput analysis of the overall system

4.3.4 Overall system analysis
Let the throughput at the sender # H1
s
be 1/E[X H1 ], at the
group leaders # H1
be 1/E[H H1 ], at the leaf nodes # H1
r
be
1/E[Y H1 ]. The throughput of the overall system is
r }. (22)
From Eqs. 12, 16, and 21 it follows that
If p is a constant and if p # 0, we obtain
Therefore, the maximum throughput of this protocol, as well
as the throughput with non-negligible packet loss, is independent
of the number of receivers. This is the only class
of reliable multicast protocols that exhibits such degree of
scalability with respect to the number of receivers.
4.4 Tree-based protocols with local nak avoidance
and periodic polling
To bound the overall system throughput in the generic Tree-
NAPP protocol, we repeat the method used for the tree-based
class; we first derive and bound the expected cost at the
source, group leaders, and leaves. As we did for the case
of tree-based protocols, we assume that there are enough
receivers to form a full tree at each level. We place a superscript
H2 on any variables relating to the generic Tree-NAPP
protocol.
4.4.1 Source node
We consider first X H2 , the processing costs required by the
source to successfully multicast an arbitrarily chosen packet
to all receivers using the H2 protocol. The processing requirement
for an arbitrary packet can be expressed as a sum
of costs:
+(receiving local naks)
+(receiving periodic local acks)
where X f is the time to get a packet from a higher layer,
(i) is the time for (re)transmission attempt i, X n (m) is
the time for receiving local nak m from the receiver set,
# is the amortized time to process the periodic local ack
associated with the current congestion window, and M H2 is
the number of transmission attempts the source will have to
make for this packet. Taking expectations, where
we have
Using Eq. 11, the bound of E[M H1 ], we can bound Eq. 28
as follows
It then follows that, when p is a constant, E[X H2
4.4.2 Leaf nodes
Let Y H2 denote the processing requirement on nodes that
do not have to forward packets (leaves). The sum of cost
can be expressed as
(receiving transmissions)
(sending periodic local acks)
(sending local naks)
(receiving local naks)
Let Y p (i) be the time it takes to process the (re)transmission
r be the number of transmissions required for the packet
to be received by receiver r, Y n (j) be the time it takes to
send local nak j, X n (j) be the time it takes to receiver
local nak j (from another receiver), Y t (k) be the time to
set timer k, Y f be the time to deliver a packet to a higher
layer, and Y # be the amortized cost of sending a periodic
local ack for a group of packets of which this packet is a
member. Taking expectations of Eq. 30,
It follows from the distribution of M r that [17, 18]
. (32)
Therefore, noting Eq. 32 and that Prob{M r >
derive from Eq. 31 the expected cost as
Again, using the bound of E[M H1 ] given in Eq. 11, we can
bound Eq. 33 by
# . (34)
When p is treated as a constant, E[Y H2
4.4.3 Group leaders
The sum of costs for group leaders, which have the job of
both sender and receiver, is
(receiving transmissions)
(sending periodic local acks)
(receiving periodic local acks)
(receiving local naks)
(sending local naks)
(retransmissions to children)
Taking expectations and substituting Eq. 32, we obtain
Similar to group leaders in the H1 protocol, the processing
cost at a group leader is the same as a source and a leaf,
without the cost of receiving the data from a higher layer
and one less transmission. Substituting Eq. 28 and Eq. 33
into Eq. 36 and subtracting the difference, the expected cost
can be expressed as
Therefore, Eq. 36 can be bounded by
# . (38)
When p is a constant, E[H H2 ] # O(1). Therefore, all nodes
in the Tree-NAPP protocol have a constant amount of work
to do with regard to the number of receivers.
4.4.4 Overall system analysis
The overall system throughput for the H2 protocol is the
minimum throughput attainable at each type of node in the
tree, that is,
r }. (39)
From Eqs. 29, 34, and 38, it follows that
Accordingly, if either p is constant or p # 0, we obtain
from Eq. 40 that
# O(1). (41)
Therefore, the maximum throughput of the Tree-NAPP pro-
tocol, as well as the throughput with non-negligible packet
loss, is independent of the number of receivers.
4.5 Ring-based protocols
In this section, we analyze the throughput of ring-based pro-
tocols, which we denote by a superscript R, using the same
assumptions as in Sects. 4.3 and 4.4. Because we are interested
in the maximum attainable throughput, we are assuming
a constant stream of packets, which means we can
ignore the overhead that occurs when there are no acks on
which to piggyback token-passing messages.
4.5.1 Source
Source nodes practice a special form of unicast with a roaming
token site. The sum of costs incurred is
(processing acks)
r
X a (i)
Mr
where M r is the number of transmissions required for the
packet to be received by the token site, and has a mean of
r
be the number of acks from
a receiver r (in this case the token site) sent unicast, i.e.,
the number of packets correctly received at r. This number
is always 1, accordingly:
Taking expectations of Eq. 42, we obtain
r
If we again assume constant costs for all operations, it can
be shown that
which, when p is a constant, is O(1) with regard to the size
of the receiver set.
4.5.2 Token site
The current token site has the following costs: (note both
TRP and RMP specify that retransmissions are sent unicast
to other R - 1 receivers.)
(multicasting ack/token )
(processing naks)
(unicasting retransmissions)
r
(R - 1)Prob{M r >1}
Mr
where L R is the number of naks received at the token site
when using a ring protocol. To derive L R , consider M r , the
number of transmissions necessary for receiver r to successfully
receive a packet. M r has an expected value of 1/(1-p),
and the last transmission is not naked. Because there are
(R - 1) other receivers sending naks to the token site, we
obtain
(R - 1)p
Therefore, the mean processing time at the token site is
(R
(R - 1)p
The expected cost at the token site can be bounded by
(R - 1)p
with regard to the number of receivers. When p is a constant,
4.5.3 Receivers
Receivers practice a receiver-initiated protocol with the current
token site. We assume there is only one packet for the
ack, token, and time stamp multicast from the token site
per data packet. The cost associated with an arbitrary packet
are therefore
(receiving first transmission)
(sending naks)
(receiving retransmissions)
r
Mr
Mr
The first term in the above equation is the cost of receiving
the ack/token/time stamp packet from the token site; the
second is the cost of receiving the first transmission sent
from the sender, assuming it is received error free; the third
is the cost of delivering an error-free transmission to a higher
layer; the fourth is the cost of receiving the retransmissions
from the token site, assuming that the first failed; and the
last two terms consider that a nak is sent only if the first
transmission attempt fails and that an interrupt occurs only
if a nak was sent. Taking expectations, we obtain
As shown previously [17, 18],
. (52)
Substituting Eqs. 43, 52, and 32 into Eq. 51, we have
Assuming all operations have constant costs, it can be shown
that
with regard to the size of the receiver set. If we consider p
as a constant, then E[Y R
4.5.4 Overall system analysis
The overall system throughput of R, the generic token ring
protocol, is equal to the minimum attainable throughput at
each of its parts:
r }. (55)
From Eqs. 45, 49 and 54 it follows that, if p is a constant
and for p # 0, we obtain
(R - 1)p
5 Numerical results
To compare the relative performance of the various classes
of protocols, all mean processing times are set equal to 1,
except for the periodic costs X # and Y # which are set to
0.1.

Figure

6 compares the relative throughputs of the protocols
A, N1, N2, H1, H2, and R as defined in Sect. 2.
The graph represents the inverse of Eqs. 19, 36, and 48, re-
spectively, which are the throughputs for the tree-based, tree-
NAPP, and ring-based protocols, as well as the inverse of the
throughput equations derived previously [17, 18] for sender-
and receiver-initiated protocols. The top, middle and bottom
graphs correspond to increasing probabilities of packet loss,
10%, and 25%, respectively. Exact values of E[M H1
were calculated using a finite version of Eq. 9; Exact values
of E[M ] were similarly calculated [22].
The performance of nak avoidance protocols, especially
tree-NAPP protocols, is clearly superior. However, our assumptions
place these two subclasses at an advantage over
their base classes. First, we assume that no acknowledgements
are lost or are received in error. The effectiveness
of nak avoidance is dependent on the probability of naks
reaching all receivers, and thus, without our assumption, the
effectiveness of nak avoidance decreases as the number of
receivers involved increases. Accordingly, tree-NAPP protocols
have an advantage that is limited by the branching
factor of the ack tree, while RINA protocols have an advantage
that increases with the size of the entire receiver
set. Second, we assume that the timers used for nak avoidance
are set perfectly. In reality, the messages used to set
timers would be subject to end-to-end delays that exhibit no
regularity and can become arbitrarily large.
1000 2000 3000 4000 5000 6000 7000 8000 9000 100000.2Throughput H2
A
1000 2000 3000 4000 5000 6000 7000 8000 9000 100000.2Number ofReceivers
Fig. 6. The throughput graph from the exact equations for each protocol.
The probability of packet loss is respectively. The
branching factor for trees is set at 10
We conjecture that the relative performance of nak avoidance
would actually lie closer to their respective
base classes, depending on the effectiveness of the nak
avoidance scheme; in other words, the curves shown are
upper bounds of nak avoidance performance. Our results
show that, when considering only the base classes (since
not one has an advantage over another), the tree-based class
performs better than all the other classes. When considering
only the subclasses that use nak avoidance, tree-NAPP
protocols perform better than RINA protocols, even though
our model provides an unfair advantage to RINA protocols.
It is the hierarchical structure organization of the receiver
set in tree-based protocols that guarantees scalability and improves
performance over other protocols. Using nak avoidance
on a small scale increases performance even further.
In addition, if nak avoidance failed for a tree-NAPP protocol
(e.g., due to incorrect setting of timers), the performance
would still be independent of the size of the receiver set.
RINA protocols do not have this property. Failure of the
nak avoidance for RINA protocols would result in unscalable
performance like that of a receiver-initiated protocol,
which degrades quickly with increasing packet loss.
Any increase in processor speed, or a smaller branching
factor would also increase throughput for all tree-based pro-
tocols. However, for the same number of receivers, a smaller
branching factor implies that some retransmissions must traverse
a larger number of tree-hops towards receivers expecting
them further down the tree. For example, if a packet is
lost immediately at the source, the retransmission is multi-cast
only to its children and all other nodes in the tree must
wait until the retransmission trickles down the tree struc-
ture. This poses a latency problem that can be addressed
by taking advantage of the dependencies in the underlying
multicast routing tree. Retransmissions could be multicast
only toward all receivers attached to routers on the subtree
of the router attached to the receiver which has requested
the missing data. The number of tree-hops from the receiver
to the source is also a factor in how quickly the source can
release data from memory in the presence of node failures,
as discussed by Levine et al. [12].
Supportable
receivers H2 N2
R A
Fig. 7. Number of supportable receivers for each protocol. The probability
of packet loss is respectively. The branching factor for
trees is set at 10

Figure

7 shows the number of supportable receivers by
each of the different classes, relative to processor speed
requirements. This number is obtained by normalizing all
classes to a baseline processor, as described by Pingali et
al. [17, 18]. The baseline uses protocol A and can support exactly
one
is the speed of the processor that can support at most R
receivers under protocol #, we set - A 1. The baseline
cost is equal to [17, 18]
=- A [1]
. (58)
Using Eqs. 18, 36, 48, and 58, we can derive the following
-s for tree-based, tree-NAPP, and ring-based protocols,
respectively:
(R - 1)p
# . (61)
The number of supportable receivers derived for sender- and
receiver-initiated protocols are shown to be [17, 18]
(2E[M ]) . (64)
From Fig. 6 and 7, it is clear that tree-based protocols
can support any number of receivers for the same processor
speed bound at each node, and that tree-NAPP protocols attain
the highest maximum throughput. It is also important to
note that the maximum throughput that RINA protocols can
attain becomes more and more insensitive to the size of the
receiver set as the probability of error decreases. Because
we have assumed that a single nak reaches the source, that
naks are never lost, and that session messages incur no processing
load, we implicitly assume the optimum behavior of
RINA protocols. The simulation results reported for SRM
by Floyd et al. [8] agree with our model and result from
assuming no nak losses and a single packet loss in the ex-
periments. Figure 7 shows that tree-NAPP protocols can be
made to perform better than the best possible RINA protocol
by limiting the size of the local groups.
Because of the unicast nature of retransmissions in ring-based
protocols, these protocols approach sender-initiated
protocols; this indicates that allowing only multicast retransmissions
would improve performance greatly.
6 Conclusions
We have compared and analyzed the four known classes of
reliable multicast protocols. Of course, our model constitutes
only a crude approximation of the actual behavior of reliable
multicast protocols. In the Internet, an ack or a nak
is simply another packet, and the probability of an ack or
nak being lost or received in error is much the same as
the error probability of a data packet. This assumption gives
protocols that use nak avoidance an advantage over other
classes. Therefore, it is more reasonable to compare them
separately: our results show that tree-based protocols without
nak avoidance perform better than other classes that do not
use nak avoidance, and that tree-NAPP protocols perform
better than RINA protocols, even though RINA protocols
have an artificial advantage over every other class. We conjecture
that, once the effects of ack or nak failure, and the
correlation of failures along the underlying multicast routing
trees are accounted for, the same relative performance
of protocols will be observed.
The results are summarized in Table 1. It is already
known that sender-initiated protocols are not scalable because
the source must account for every receiver listening.
Receiver-initiated protocols are far more scalable, unless
nak avoidance schemes are used to avoid overloading the
source with retransmission requests. However, because of
the unbounded-memory requirement, this protocol class can
only be used efficiently with application-layer support, and
only for a limited set of applications. Furthermore, to set the
timers needed for nak avoidance, existing instantiations of
RINA protocols require all group members to transmit session
messages periodically, which makes them unscalable.
Ring-based protocols were designed for atomic and total ordering
of packets. TRP and RMP limit their throughput by
requiring retransmissions to be unicast. It would be possible
to reduce the cost bound to O(ln R), assuming p to be
a constant, if the nak avoidance techniques presented by
Ramakrishnan and Jain [19] were used.
Our analysis shows that ack trees are a good answer
to the scalability problem for reliable multicasting. Practical
implementations of tree-based protocols maintain the
anonymity of the receiver set, and only the tree-based and
tree-NAPP classes have throughputs that are constant with
respect to the number of receivers, even when the probability
of packet loss is not negligible (which would preclude
accurate setting of nak avoidance timers). Because
tree-based protocols delegate responsibility for retransmission
to receivers and because they employ techniques applicable
to either sender- or receiver-initiated protocols within
local groups (i.e., a node and its children in the tree) of the
ack tree only, any mechanism that can be used with all the
receivers of a session in a receiver-initiated protocol can be
adopted in a tree-based protocol, with the added benefit that
the throughput and number of supportable receivers is completely
independent of the size of the receiver set, regardless
of the likelihood with which packets, acks, and naks are
received correctly.
On the other hand, while the scope of naks and retransmissions
can be reduced without establishing a structure in
the receiver set [8], limiting the scope of the session messages
needed to set nak avoidance timers and to contain the
scope of naks and retransmissions require the aggregation
of these messages. This leads to organizing receivers into
local groups that must aggregate sessions messages sent to
the source (and local groups). Doing this efficiently, how-
ever, leads to a hierarchical structure of local groups much
like what tree-based protocols require. Hence, it appears that
organizing the receivers hierarchically (in ack trees or oth-
erwise) is a necessity for the scaling of a reliable multicast
protocol.



--R

Core based trees (CBT): An architecture for scalable inter-domain multicast routing
Data Networks
Reliable broadcast protocols.
NETBLT: A high-throughput transport protocol
Multicast routing in a datagram internetwork.
Multicast routing in datagram internetworks and extended lans.
An architecture for wide-area multicast routing
A reliable multicast framework for light-weight sessions and application level framing

Transmission control protocol.

RMTP: A reliable multicast transport protocol.

Multicast transport protocols for high-speed networks
Reliable multicast transport protocol (RMTP).
Protocol and Real-Time Scheduling Issues for Multi-media Applications
A comparison of sender-initiated and receiver-initiated reliable multicast protocols
A negative acknowledgement with periodic polling protocol for multicast over lan.

XTP: The Xpress Transfer Protocol.


A reliable dissemination protocol for interactive collaborative applications.
He received the B.
His current research interest is the analysis and design of algorithms and protocols for computer communication.
--TR
Data networks
NETBLT: a high throughput transport protocol
Multicast routing in datagram internetworks and extended LANs
XTP: the Xpress Transfer Protocol
Multicast routing in a datagram internetwork
Core based trees (CBT)
A comparison of sender-initiated and receiver-initiated reliable multicast protocols
An architecture for wide-area multicast routing
A reliable dissemination protocol for interactive collaborative applications
Log-based receiver-reliable multicast for distributed interactive simulation
A reliable multicast framework for light-weight sessions and application level framing
Protocol and real-time scheduling issues for multimedia applications
The case for reliable concurrent multicasting using shared ACK trees
Reliable broadcast protocols
A High Performance Totally Ordered Multicast Protocol
The Ordered Core Based Tree Protocol
A Comparison of Known Classes of Reliable Multicast Protocols

--CTR
V. Ramakrishna , Max Robinson , Kevin Eustice , Peter Reiher, An Active Self-Optimizing Multiplayer Gaming Architecture, Cluster Computing, v.9 n.2, p.201-215, April     2006
Christian Maihfer, A bandwidth analysis of reliable multicast transport protocols, Proceedings of NGC 2000 on Networked group communication, p.15-26, November 08-10, 2000, Palo Alto, California, United States
Shuju Wu , Sujata Banerjee , Xiaobing Hou, A Comparison of Multicast Feedback Control Mechanisms, Proceedings of the 38th annual Symposium on Simulation, p.80-87, April 04-06, 2005
Shuju Wu , Sujata Banerjee , Xiaobing Hou, Performance Evaluation and Comparison of Multicast Feedback Control Mechanisms, Simulation, v.82 n.5, p.345-362, May       2006
Brian Neil Levine , Sanjoy Paul , J. J. Garcia-Luna-Aceves, Organizing multicast receivers deterministically by packet-loss correlation, Proceedings of the sixth ACM international conference on Multimedia, p.201-210, September 13-16, 1998, Bristol, United Kingdom
Maurice Herlihy , Srikanta Tirthapura , Roger Wattenhofer, Ordered Multicast and Distributed Swap, ACM SIGOPS Operating Systems Review, v.35 n.1, p.85-96, January 1, 2001
Athina P. Markopoulou , Fouad A. Tobagi, Hierarchical reliable multicast: performance analysis and placement of proxies, Proceedings of NGC 2000 on Networked group communication, p.27-35, November 08-10, 2000, Palo Alto, California, United States
Ryan G. Lane , Scott Daniels , Xin Yuan, An empirical study of reliable multicast protocols over Ethernet-connected networks, Performance Evaluation, v.64 n.3, p.210-228, March, 2007
Suman Banerjee , Seungjoon Lee , Ryan Braud , Bobby Bhattacharjee , Aravind Srinivasan, Scalable resilient media streaming, Proceedings of the 14th international workshop on Network and operating systems support for digital audio and video, June 16-18, 2004, Cork, Ireland
Suman Banerjee , Seungjoon Lee , Bobby Bhattacharjee , Aravind Srinivasan, Resilient multicast using overlays, ACM SIGMETRICS Performance Evaluation Review, v.31 n.1, June
Philip K. McKinley , Ravi T. Rao , Robin F. Wright, H-RMC: a hybrid reliable multicast protocol for the Linux kernel, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.8-es, November 14-19, 1999, Portland, Oregon, United States
Brian Neil Levine , Sanjoy Paul , J. J. Garcia-Luna-Aceves, Organizing multicast receivers deterministically by packet-loss correlation, Multimedia Systems, v.9 n.1, p.3-14, July
Suman Banerjee , Seungjoon Lee , Bobby Bhattacharjee , Aravind Srinivasan, Resilient multicast using overlays, IEEE/ACM Transactions on Networking (TON), v.14 n.2, p.237-248, April 2006
Carlos A. S. Oliveira , Panos M. Pardalos, A survey of combinatorial optimization problems in multicast routing, Computers and Operations Research, v.32 n.8, p.1953-1981, August 2005
ACK implosion;multicast transport protocols;reliable multicast;tree-based protocols