A bandwidth analysis of reliable multicast transport protocols.
Multicast is an efficient communication technique to save bandwidth for group communication purposes. A number of protocols have been proposed in the past to provide a reliable multicast service. Briefly classified, they can be distinguished into sender-initiated, receiver-initiated and tree-based approaches. In this paper, an analytical bandwidth evaluation of generic reliable multicast protocols is presented. Of particular importance are new classes with aggregated acknowledgments. In contrast to other approaches, these classes provide reliability not only in case of message loss but also in case of node failures. Our analysis is based on a realistic system model, including data packet and control packet loss, asynchronous local clocks and imperfect scope-limited local groups. Our results show that hierarchical approaches are superior. They provide higher throughput as well as lower bandwidth consumption. Relating to protocols with aggregated acknowledgments, the analysis shows only little additional bandwidth overhead and therefore high throughput rates.
INTRODUCTION
A number of reliable multicast transport protocols have been
proposed in the literature, which are based on the acknowledgment
scheme. Reliability is ensured by replying acknowledgment
messages from the receivers to the sender, either
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
Second International Workshop on Networked Group Communication '00,
Palo Alto, CA USA
Copyright 2000 ACM 0-89791-88-6/97/05 .$5.00
to conrm correct data packet delivery or to ask for a re-
transmission. Reliable multicast protocols are usually clas-
sied into sender-initiated, receiver-initiated and tree-based
ones. Brie
y characterized, in sender-initiated approaches
receivers reply positive acknowledgments (ACKs) to conrm
correct message delivery in contrast to receiver-initiated
protocols, which indicate transmission errors or losses by
negative acknowledgments (NAKs). Both classes can result
in an overwhelming of the sender and the network around
the sender by a large number of ACK or NAK messages.
This problem is the well-known acknowledgment implosion
problem, which is a vital challenge for the design of reliable
multicast protocols, since it limits the scalability for
large receiver groups. Tree-based approaches promise to be
scalable even for a large number of receivers, since they arrange
receivers into a hierarchy, called ACK tree [10]. Leaf
node receivers send their positive or negative acknowledgments
to their parent node in the ACK tree. Each non-leaf
receiver is responsible for collecting ACKs or NAKs only
from their direct child nodes in the hierarchy. Since the
maximum number of child nodes is limited, no node is overwhelmed
with messages and scalability for a large receiver
group is ensured. The maximum number of child nodes can
be determined according to the processing performance of
a node, its available network bandwidth, its memory equip-
ment, and its reliability.
In this paper we present a throughput analysis based on
bandwidth requirements as well as the overall bandwidth
consumption of all group members, which refer to the data
transfer costs. One characteristic of multicast transmissions
is that the component with the weakest performance may
determine the transmission speed. This means, a group
member with a low bandwidth connection, low processing
power, high packet loss rate or high packet delay may prevent
high transmission rates. Therefore, it is very useful to
be able to quantify the necessary requirements for a given
multicast protocol.
The remainder of this paper is structured as follows. In Section
2 we discuss the background of our throughput analysis
and take a look at related work. In Section 3 we brie
y
classify the analyzed protocols. Our bandwidth evaluation
in Section 4 starts with a denition of the assumed system
model before the various protocol classes are analyzed in
detail. To illustrate the results, some numerical evaluations
are presented in Section 5 before we conclude with a brief
summary.
2. RELATED WORK
Reliable multicast protocols were already analyzed in previous
work. The rst processing requirements analysis of
generic reliable multicast protocols was presented by Pingali
et al. [8]. They compared the class of sender- and receiver-initiated
protocols. Following analytical papers are often
based on the model and analytical methods introduced by
[8]. Levine et al. [3] have extended the analysis to the class
of ring- and tree-based approaches. In Maihofer et al. [5]
protocols with aggregated acknowledgments are considered.
A bandwidth analysis of generic reliable multicast protocols
was done by Kasera et al. [2], Nonnenmacher et al. [6]
and Poo et al. [9]. In [2], local recovery techniques are analyzed
and compared. The system model is based on a special
topology structure consisting of a source link from the
sender to the backbone, backbone links and nally tail links
from the backbone to the receivers. In [6] a similar topology
structure is used. They studied the performance gain
of protocols using parity packets to recover from transmission
errors. The protocols use receiver-based loss detection
with multicasted NAKs and NAK avoidance. In [9], non-hierarchical
protocols are compared. In contrast to previous
work, not only stop-and-wait error recovery is considered
in the analysis but also go-back-N and selective-repeat
schemes.
Our paper diers from previous work in the following ways.
First, we consider the loss of data packets and control pack-
ets. Second, we assume that local clocks are not synchronized
which aects the NAK-avoidance scheme (see Section
3.2). NAK-avoidance works less e-ciently with this more
realistic assumption. Third, our analysis considers that local
groups may not be conned perfectly, so that local data
or control packets may reach nodes in other local groups.
Finally, our work extends previous analysis by two new tree-based
protocol classes. They are based on aggregated ACKs
to be able to cope with node failures.
3. CLASSIFICATIONOFRELIABLEMUL-
In this section we brie
y classify the reliable multicast protocols
analyzed in this paper. A more detailed and more
general description for some of these classes can be found in
[8], [3] and [6].
3.1 Sender-Initiated Protocols
The class of sender-initiated protocols is characterized by
positive acknowledgments (ACKs) returned by the receivers
to the sender. A missing ACK detects either a lost data
packet at the corresponding receiver, a lost ACK packet or
a crashed receiver, which cannot be distinguished by the
sender. Therefore, a missing ACK packet leads to a data
packet retransmission from the sender. We assume that such
a retransmission is always sent using multicast. This protocol
class will be referred to as (A1). Note that the use of
negative acknowledgments, for example to speed up retrans-
missions, does not necessarily mean that a protocol is not
of class (A1). Important is that positive acknowledgments
are necessary, for example to release data from the sender's
buer space. An example for a sender-initiated protocol is
the Xpress Transport Protocol (XTP) [12].
3.2 Receiver-Initiated Protocols
In contrast to sender-initiated protocols, receiver-initiated
protocols return only negative acknowledgments (NAKs) instead
of ACKs. As in the sender-initiated protocol class, we
assume that retransmissions are sent using multicast. When
a receiver detects an error, e.g. by a wrong checksum, a skip
in the sequence number or a timeout while waiting for a data
packet, a NAK is returned to the sender. Pure receiver-initiated
protocols have a non-deterministic characteristic,
since the sender is unable to decide when all group members
have correctly received a data packet.
Receiver-initiated protocols can either send NAKs using unicast
or multicast transmission. The protocol class sending
unicast NAKs will be called (N1). An example for (N1)
is PGM [11]. The approach using multicast NAKs (N2) is
known as NAK-avoidance scheme. A receiver that has detected
an error sends a multicast NAK provided that it has
not already received a NAK for this data packet from another
receiver. Thus, in optimum case, only one NAK is
received by the sender for each lost data packet. An example
for such a protocol is the scalable reliable multicasting
protocol (SRM) [1].
3.3 Tree-Based Protocols
Tree-based approaches organize the receivers into a tree
structure called ACK tree, which is responsible for collecting
acknowledgments and sending retransmissions. We
assume that the sender is the root of the tree. If a receiver
needs a retransmission, the parent node in the ACK tree
is informed rather than the sender. The parent nodes are
called group leaders for their children which form a local
group. Note that a group leader may also be a child of another
local group. A child which is only a receiver rather
than a group leader is called leaf node.
The rst considered scheme of this class (H1) is similar to
sender-initiated protocols since it uses ACKs sent by the receivers
to their group leaders to indicate correctly received
packets. Each group leader that is not the root node also
sends an ACK to its parent group leader until the root node
is reached. If a timeout for an ACK occurs at a group
leader or the root, a multicast retransmission is invoked.
An example of a protocol similar to our denition of (H1)
is RMTP [7]. The second scheme (H2) is based on NAKs
with NAK suppression similar to (N2) and selective ACKs
(SAKs), which are sent periodically for deciding deterministically
when packets can be removed from memory. A SAK
is sent to the parent node after a certain number of packets
are received or after a certain time period has expired, to
propagate the state of a receiver to its group leader. TMTP
[14] is an example for class (H2).
Before the next scheme will be introduced, it is necessary to
understand that (H1) and (H2) can guarantee reliable delivery
only if no group member fails in the system. Assume for
example that a group leader G1 fails after it has acknowledged
correct reception of a packet to its group leader G0
which is the root node. If a receiver of G1 's local group
needs a retransmission, neither G1 nor G0 can resend the
data packet since G1 has failed and G0 has removed the
packet from memory. This problem is solved by aggregated
hierarchical ACKs (AAKs) of the third scheme (H3). A
group leader sends an AAK to its parent group leader after
all children have acknowledged correct reception. After
a group leader or the root node has received an AAK, it can
remove the corresponding data from memory because all
members in this subhierarchy have already received it cor-
rectly. Lorax [4] and RMTP-II [13] are examples for AAK
protocols. Our denition of (H3)'s generic behavior is as
follows:
1. Group leaders send a local ACK after the data packet
is received correctly.
2. Leaf node receivers send an AAK after the data packet
is received correctly.
3. The root node and group leaders wait a certain time
to receive local ACKs from their children. If a timeout
occurs, the packet is retransmitted to all children or selective
to those whose ACK is missing. Since leaf node
receivers send only AAKs rather than local ACKs, a
received AAK from a receiver is also allowed to prevent
the retransmission.
4. The root node and group leaders wait to receive AAKs
from their children. Upon reception of all AAKs, the
corresponding packet can be removed from memory
and a group leader sends an AAK to its parent group
leader. If a timeout occurs while waiting for AAKs, a
unicast AAK query is sent to the aected nodes.
5. If a group leader or leaf node receiver receives further
retransmissions after an AAK has been sent or the
prerequisites for sending an AAK are met, these data
packets are acknowledged by AAKs rather than ACKs.
The same applies for receiving an AAK query that is
replied with an AAK if the prerequisites are met.
In summary, ACKs are used for fast error recovery in case
of message loss and AAKs to clear buer space. Besides the
AAK scheme, we consider in our analysis of (H3) a threshold
scheme to decide whether a retransmission is performed
using unicast or multicast. The sender or group leader compares
the number of missing ACKs with a threshold pa-
rameter. If the number of missing ACKs is smaller than
this threshold, the data packets are retransmitted using uni-
cast. Otherwise, if the number of missing ACKs exceeds the
threshold, the overall network and node load is assumed to
be lower using multicast retransmission.
Our next protocol will be denoted as (H4) and is a combination
of the negative acknowledgment with NAK suppression
scheme (H2) and aggregated acknowledgments (H3). Similar
to (H2), NAKs are used to start a retransmission. Instead
of selective periodical ACKs, aggregated ACKs are
used to announce the receivers' state and allow group leaders
and the sender to remove data from memory. Like SAKs,
we assume that AAKs are sent periodically. We dene the
generic behavior of (H4) as follows:
1. Upon detection of a missing or corrupted data packet,
receivers send a NAK per multicast scheduled at a random
time in the future and provided that not already a
NAK for this data packet is received before the scheduled
time. If no retransmission arrives within a certain
time period, the NAK sending scheme is repeated.
2. Group leaders and the sender retransmit a packet per
multicast if a NAK has been received.
3. After a certain number of correctly received data pack-
ets, leaf node receivers send an AAK to its group leader
in the ACK tree. A group leader forwards this AAK
to its parent group leader or sender, respectively, as
soon as the same data packets are correctly received
and the corresponding AAKs from all child nodes are
received.
4. The sender and group leaders initiate a timer to wait
for all AAKs to be received. If the timer expires, an
AAK query is sent to those child nodes whose AAK is
missing.
5. If a group leader or leaf node receiver gets an AAK
query and the prerequisites for sending an AAK are
met, the query is acknowledged with an AAK.
4. BANDWIDTH ANALYSIS
4.1 Model
Our model is similar to the one used by Pingali et al. [8] and
Levine et al. [3]. A single sender is assumed, multicasting
to R identical receivers. In case of tree-based protocols,
the sender is the root of the ACK tree. We assume that
nodes do not fail and the network is not partitioned, i.e.
that retransmissions are nally successful. In contrast to
previous work, packet loss can occur on both, data packets
and control packets. Multicast packet loss probability is
given by q and unicast packet loss probability by p for any
node.

Table

1 summarizes the notations for protocol classes
(A1), (N1), (N2), (H1) and (H2). In Table 2 the additional
notations for the protocol classes (H3) and (H4) are given.
We assume that losses at dierent nodes are independent
events. In fact, since receivers share parts of the multicast
routing tree, this assumption does not hold in real networks.
However, if all classes have similar trees no protocol class is
privileged relative to another one by this assumption.
In the following subsections, the generic protocol classes are
analyzed in detail. Although our work considers more protocols
and a more general system model, the notations and
basic analyzing methods follows [8] and [3].
4.2 Sender-Initiated Protocol (A1)
We determine the bandwidth requirements at the sender
S and each receiver W A1
R , based on the necessary band-width
for sending a single data packet correctly to all re-
ceivers. We assume that the sender waits until all ACKs are
received and then sends a retransmission if necessary.
The bandwidth consumption at the sender is:
(receiving ACKs)
e
Wa (i) (1)
E(W
E( e
Wd (m) and Wa(i) are the bandwidths required for a data
packet or ACK packet for the m-th or i-th transmission,

Table

1: Notations for the analysis of (A1), (N1),
(N2), (H1) and (H2)
R Size of the receiver set.
Branching factor of a tree or the local group size.
Bandwidth for a data packet, ACK, NAK and
SAK, respectively.
Bandwidth requirements for protocols
w at the sender, receiver, group leader
and overall bandwidth consumption.
Throughput respectively relative bandwidth efciency
for protocols w at the sender, receiver,
group leader and overall system throughput.
S Number of periodical SAKs received by the
sender in the presence of control message loss.
Probability for unicast or multicast data loss at
a receiver, respectively.
Probability for unicast ACK, NAK or multicast
loss.
~ Probability that a retransmission is necessary
for protocol (A1) or (N2), respectively.
ps Probability for simultaneous and therefore un-necessary
NAK sending in (N2), (H2) and (H4).
l Probability for receiving a data or control packet
from another local group.
L w Number of ACKs or NAKs per data packet sent
by receiver r that reach the sender or total number
of ACKs or NAKs per data packet received
from all receivers.
r , N w
Total number of transmissions per data packet
received by receiver r from the parent node or
total number of received data packets from all
local groups, respectively.
Total number of transmissions per data packet
received by a group leader from all local groups.
w Number of necessary transmissions for receiver
r, to receive a data packet correctly in the presence
of data and ACK or NAK loss or total number
of transmissions for all receivers.
O Number of necessary rounds to correctly deliver
a packet to all receivers or to receiver r.
O Total number of empty rounds or empty rounds
for receiver r, respectively.
k Number of NAKs sent in round k.
respectively. M A1 is the total number of transmissions necessary
to transmit a packet correctly to all receivers in the
presence of data packet and ACK loss and e
L A1 is the total
number of ACKs received for this data packet. E(W A1
S ) is
the expectation of the bandwidth requirement at the sender.
The only unknowns are E(M A1 ) and E( e
E( e L
This means, the sender gets one ACK per data packet transmission
E(M A1 ) from every receiver R, provided that the
data packet is not lost with probability (1 qD ) and the
ACK is not lost with probability (1 pA ).
Now, the number of transmissions have to be analyzed. The
probability for a retransmission is:
i. e. either a data packet is lost (qD ) or the data packet is
received correctly and the ACK is lost ((1 qD )pA ). So,
the probability that the number of necessary transmissions
r for receiver r is smaller or equal to m (m=1, 2, .) is:
As the packet losses at dierent receivers are independent
from each other:
R
Y
R
R
R
R
R
~
R
E(M A1 ) is the expected total number of necessary transmissions
to receive the data packet correctly at all receivers.
Now E(W A1
S ) is entirely determined. The bandwidth efciency
respectively maximum throughput for the sender
S , to send data packets successfully to a receiver is:
Accordingly, the processing requirement for a packet at the
receiver is:
(sending ACKs) (10)
E(W
where a packet is received with probability (1 qD ) and each
received packet is acknowledged. The maximum throughput
of a receiver is:
R =E(W A1
system throughput  A1 is determined by the minimum
of the throughput rates at the sender and receivers:
R g:
Now we are able to determine the total bandwidth consump-
tion. In contrast to previous work, our denition of total
bandwidth consumption is the bandwidth that is necessary
at the sender and receivers to send and receive messages.
This means, we assume that the internal network structure
is not known and therefore not considered in the analysis.
In [2] and [6], total bandwidth is dened on a per link basis.
Such a denition encompasses the total costs within the net-work
but has the disadvantage, that a network topology has
to be dened with routers and links between routers. Here,
we want to determine the total costs at the communication
endpoints, i.e. the costs for the sender and receivers.
The total bandwidth consumption of protocol (A1) is then
the sum of the sender's and receivers' bandwidth consumptions

E(W
R
4.3 Receiver-Initiated Protocol (N1)
As in the sender-initiated protocol, data packets are always
transmitted using multicast. In (N1), error control is realized
by unicast NAKs. The sender collects all NAKs received
within a certain timeout period and sends only one
retransmission independent of the number of received or lost
control packets during that round.
The bandwidth requirement at the sender is:
(receiving NAKs)
e
Wn (i) (15)
E(W N1
E( e
The only unknowns are E(M N1 ) and E( e
L N1 ). The number
of transmissions, M N1 , until all receivers correctly receive a
packet is only determined by the probability for data packet
loss analogous to Eq. 8 of (A1) with qD instead of ~
p.
To determine E( e
steps have to be
done. First, the number of transmissions, M N1
r , for a single
receiver is given by the probability qD . This means, M N1
r
counts the number of trials until the rst success occurs. The
probability for the rst success in a Bernoulli experiment at
trial k with probability for success (1 qD ) is:
The necessary number of transmissions for a single receiver
r follows from the Bernoulli distribution and [8]:
E(M N1
E(M N1
r jM N1
E(M N1
r jM N1 r >
r > 1)[E(M N1
r jM N1
Besides the necessary number of transmissions, we have to
introduce the number of rounds, necessary to correctly deliver
a data packet. A round starts with the sending of a
data packet and ends with the expiration of a timeout at
the sender. Normally, there will be one data transmission
in each round. However, if the sender receives no NAKs
due to NAK loss, no retransmission is made and new NAKs
must be sent by the receivers in the next round. O N1 r is
the number of necessary rounds for receiver r. The number
of rounds is the sum of the number of necessary rounds
for sending transmissions M N1
r and the number of empty
rounds O N1 e;r in which all NAKs are lost and therefore no
retransmission is made:
O N1
r +O N1
E(M N1
r ) is given in Eq. 18. E(O N1
e;r ) can be determined
analogous to E(M N1
r ), with probability pk for the loss of all
sent NAKs in round k (see Eq. 25). The expected number
of empty rounds E(O N1
e;r ) is the expected number of empty
rounds after the rst transmission plus the expected number
of empty rounds after the second transmission and so on:
E(O N1
is the expectation for the number of empty rounds
plus the last successful NAK reception at the sender which
is subtracted. Nk , the number of NAKs sent in round k is
given by:
where qD k is the probability for a single receiver that until
round k all data packets are lost. The number of empty
rounds after transmission k is determined by the failure
probability:
pk is the probability that all sent NAKs in round k are lost.
The number of sent NAKs is equal to the number of receivers
qD k R that need a retransmission in round k (see Eq. 24).
e
L N1 is the number of NAKs received by the sender and #1
is the total number of NAKs sent in all rounds:
E( e
Finally, at the receiver we have:
E(W N1
r > 1)[E(O N1
r jO N1
Note that the last, successful transmission is not replied with
a NAK.
The throughput rates are analogous to (A1):
N1
R =E(W N1
R g:
The total bandwidth consumption is:
E(W
R
4.4 Receiver-Initiated Protocol (N2)
In contrast to (N1), this protocol class sends NAKs to all
group members using multicast. Ideally, NAK suppression
ensures that only one NAK is received by the sender. As in
the previous protocol, the sender collects all NAKs belonging
to one round and then starts a retransmission:
(receiving NAKs)
e L N2
Wn (i) (31)
E(W N2
E( e
E(M N2 ) is determined analogous to (A1) and (N1) with
loss probability qD (see Eq. 8). e
contains the number of
necessary and additional NAKs received at the sender:
E( e
Nk , the number of NAKs sent in round k, is the sum of:
NAK of the rst receiver that did not receive the data packet
plus NAK of another unsuccessful receiver that did not receive
the rst NAK packet and sends a second NAK and so
on:
The rst receiver sends a NAK provided that the data packet
was lost with probability qD k . The second receiver sends a
NAK provided that the data packet was lost and the NAK
of the rst receiver was lost (Nk;1qN ) or the rst receiver
sends no NAK (1 Nk;1 ), and so on.
In Eq. 38, a perfect system model is assumed in which additional
NAKs are only sent due to NAK loss at receivers.
This means, receivers must have synchronized local clocks
and a dened sending order for NAKs. However, since receivers
are usually not synchronized in real systems it can
occur that NAKs are sent simultaneously. Therefore, we extend
Equations 36-38 with the probability for simultaneous
sending (ps) to:
ps qN ps
The number of rounds O N2 r for receiver r is obtained analogous
to protocol (N1). It is the sum of the number of necessary
rounds for sending transmissions M N2
r and the number
of empty rounds O N2
e;r in which all NAKs are lost and therefore
no retransmission is made. The total number of rounds
O N2 for all receivers can be dened analogous to O N2
O N2
r +O N2
e;r (41)
O
The number of necessary transmissions, M N2
r , for a single
receiver r is given by the probability qD . Analogous to Eq.
of protocol (N1) the expectation is:
E(M N2
The number of empty rounds after transmission k is determined
by the failure probability:
pk is the probability that all sent NAKs in round k are lost.
The expected number of empty rounds E(O N2
e ) is equal to
the expected number of empty rounds after the rst transmission
plus the expected number of empty rounds after the
second transmission and so on. Now, E(O N2
e ) and E(O N2
can be determined analogous to M N2
r (see Eq.
E(O
E(O N2
is the expectation for the number of empty rounds
plus the last successful NAK reception at the sender, which
is subtracted.
At the receiver we have:
E(W N2
r > 1)[E(O N2
r jO N2
r > 1)[E(O N2
r jO N2
#2 is the average number of NAKs sent in each round and
#3 is the mean number of receivers that did not receive a
data packet and therefore want to send a NAK:
where (1=1 pk ) is the number of empty rounds plus the
last successful NAK sending (see Eq. 18, 45 and 46).
The second term in E(W N2
R ) is the processing requirement
to send NAKs, where the considered receiver r is only with
probability #2/#3 the one that sends a NAK. In the third
term the number of sent NAKs is subtracted from the number
of total NAKs to get the number of received NAKs.
The throughput rates are:
N2
R =E(W N2
R g: (50)
The total bandwidth consumption is:
E(W
R
4.5 Tree-Based Protocol (H1)
Our analysis distinguishes between the three dierent kinds
of nodes in the ACK tree, the sender at the root of the
tree, the receivers that form the leaves of the ACK tree
and the receivers that are inner nodes. We will call these
inner receivers group leaders. Group leaders are sender and
receiver as well.
Our analysis of all tree-based protocols is based on the
assumption that each local group consists of exactly B
members and one group leader. We assume further, that
when a group leader has to sent a retransmission, the group
leader has already received this packet correctly. The following
subsections analyze the bandwidth requirements at
the sender W H1
S , receivers W H1
R and group leaders W H1
H .
4.5.1 Sender (root node)
e
Wa (i) (52)
E(W H1
E( e
M H1 is the number of necessary transmissions until all
members of a local group have received a packet correctly.
E(M H1 ) is determined analogous (B instead of R) to Eq.
8 of protocol (A1), since every local group is like a sender-based
system. Furthermore, the number of ACKs received
by the sender and group leaders in the presence of possible
ACK loss E( e
similar to E( e
of
R:
E( e L H1
4.5.2 Receiver (leaf node)
E(N H1
r;t ) is the total number of received transmissions at receiver
r and consists mainly of the sent messages from the
parent E(N H1
r ), provided that each local group has its own
multicast address. However, if the whole multicast group
has only one multicast address, retransmissions may reach
members outside of this local group. The probability for receiving
a retransmission from another local group is assumed
to be p l for any receiver. Such received transmissions from
other local groups increase the load of a node. In our analysis
we assume that transmissions from other local groups
do not decrease the necessary number of local retransmis-
sions, since in many cases they are received after a local
retransmission have already been triggered.
First we want to determine the number of group leaders.
The number of nodes R in a complete tree with branching
factor B and height h is:
and the tree height follows to:
The number of group leaders plus the sender is therefore:
The number of received transmissions E(N H1
r ) from the parent
node at receiver r is:
E(N H1
The total number of received transmissions E(N H1
r;t ) at receiver
r is now:
E(N H1 r;t
Finally, the bandwidth requirement W H1
R for a receiver is:
r
Wa (j) (60)
E(W H1
r )E(Wa
4.5.3 Group leader (inner node)
Since a group leader is a sender and receiver as well, the
bandwidth requirement is the sum of the sender and receiver
bandwidth requirements. However, Wd(1) is not considered
here, since the initial transmission is sent using the multi-cast
routing tree rather than the ACK tree. Furthermore,
a group leader may receive additional retransmissions only
from G 2 group leaders, since its parents group leader and
this group leader itself have to be subtracted.
e
Wa
| {z }
as sender
r
| {z }
as receiver
E(N H1
E(W H1
E( e
E(N H1
E(Wd (1)) E(M H1 )(1 qD )p l E(Wd
The maximum throughput rates  H1
R ,  H1
H for the
sender, receiver and group leader are:
H1
R =E(W H1
system throughput  H1 is given by the minimum
of the throughput rates for the sender, receiver and group
leader:
R g: (66)
The total bandwidth consumption of protocol (H1) is then
the sum of the sender's, leaf node receivers' and group lead-
ers' bandwidth consumptions:
(R G+ 1)W H1
4.6 Tree-Based Protocol (H2)
uses selective periodical ACKs (SAKs) and NAKs with
avoidance. The sender and group leaders collect all
NAKs belonging to one round and send a retransmission
if the waiting time has expired and at least one NAK has
been received. We have to distinguish between the number
of rounds and the number of transmissions. The number of
rounds is equal or greater than the number of retransmis-
sions, since if a sender or receiver receives no NAK within
one round, no retransmission is invoked.
A SAK is sent by the receiver to announce its state, i.e.
its received and missed packets, after a sequence of data
packets have been received. We assume that a SAK is sent
after a certain period of time. Therefore, when analyzing
the processing requirements for a single packet, only the
proportionate requirements for sending and receiving a SAK
(W ) is considered. S is assumed to be the number of SAKs
received by the sender in the presence of possible SAK loss:
4.6.1 Sender (root node)
e
E(W H2
E( e
E(M H2 ) is determined analogous to protocol (N2) (B instead
of R).
To determine E( e
that NAKs are received
from the child nodes of this local group as well as may be
received from other local groups with probability p l (see Eq.
33, 34 and 59):
E( e
Nk , the number of NAKs sent in round k and pk , the failure
probability for empty rounds are obtained analogous to Eq.
44 of (N2). G, the number of group leaders
is obtained analogous to Eq. 57 of (H1).
4.6.2 Receiver (leaf node)
Retransmissions are received mainly from the parent node,
but may also be received from other group leaders. Analo-
gous, NAKs are mainly received from other receivers in the
same local group but may also be received from receivers
in other local groups. The bandwidth requirement for a receiver
is analogous to Eq. 47 of protocol (N2):
E(W H2
r > 1)[E(O H2
r jO H2
r > 1)[E(O H2
r jO H2
| {z }
from this local group
| {z }
from other local groups
#2 and #3 can be obtained analogous to Eq. 48 and 49 of
protocol (N2) with B instead of R.
4.6.3 Group leader (inner node)
As the group leader role contains the sender role and the
receiver role as well, the processing requirements are:
E(W H2
l E(M H2 )(1 qD )E(Wd )
The second and third line in the above equation are the processing
requirements for one other local group. They have to
be subtracted because in contrast to the sender or receivers,
a group leader has a local parent group and local child group
which are already considered for the normal operations.
Finally, the maximum throughput rates are:
H2
R =E(W H2
R g: (75)
The total bandwidth consumption of protocol (H2) is:
(R G+ 1)W H2
4.7 Tree-Based Protocol (H3)
We assume that the correct transmission of a data packet
consists of two phases. In the rst phase, the data is transmitted
and ACKs are collected until all ACKs are received,
i.e. until all nodes have received the data packet. Then the
second phase starts, in which the missing AAKs are col-
lected. Note that most AAKs are already received in phase
one, since AAKs are sent from group leaders as soon as all
children have sent their AAKs. In this case, a retransmission
is acknowledged with an AAK rather than an ACK. So,
only nodes whose AAK is missing must be queried in phase
two.

Table

2: Additional notations for (H3) and (H4)
Bandwidth for an AAK or AAK query packet.
bandwidth for a periodical
AAK or AAK query packet, respectively.
Bandwidth to send a data packet per unicast
or multicast, respectively.
pq Probability for AAK query loss.
AA Probability of a unicast AAK loss.
Current number of receivers that need a re-transmission

Threshold for unicast retransmission. If n k is
smaller than , unicast is used for retransmission
and multicast otherwise.
Probability that n k is smaller than the threshold
for multicast retransmissions and therefore
unicast is used.
Probability that a retransmission is necessary
due to data or ACK loss.
Probability that an AAK query fails.
Mean number of sent unicast messages per
packet retransmission.
m Number of necessary unicast or multicast
transmissions in the presence of failures, respectively

aa Number of sent ACKs or AAKs.
Number of received ACKs or AAKs.
Number of sent AAK queries.
e L w aaq Number of received AAK queries.
Baa Number of receivers in a local group from
which the AAK is missing when phase two
starts.
pc Probability that no AAK can be sent due to
missing AAKs of child nodes.
4.7.1 Sender (root node)
The bandwidth requirement of a sender is:
e
L H3 a
e
Waa
u are the number of necessary multicast or
unicast transmissions, respectively. Wd;m and W d;u determine
the bandwidth requirements for a multicast or unicast
packet transmission. Waa is the necessary bandwidth for an
AAK and e
L H3 aa is the number of received AAKs. The processing
of AAKs is similar to the processing of data packets
and ACKs. If AAKs are missing after a timeout has oc-
curred, the sender or group leader sends unicast AAK query
messages (Waaq ) to the corresponding child nodes. Note
that this processing is started after all ACKs have been received
and no further retransmissions due to lost data packets
are necessary. L H3
aaq is the number of necessary unicast
AAK queries in the presence of message loss.
that unicast is used for retransmissions,
the number of unicast and multicast transmissions are:
Please note that the rst transmission is always sent with
multicast. The probability for a retransmission due to data
or ACK loss is given by:
unicast z }| {
multicast
z }| {
| {z }
data loss
unicast z }| {
multicast
z }| {
pA
| {z }
no data loss but ACK loss
E(M H3 ) is determined by  instead of ~
instead of R
analogous to Eq. 8 of protocol (A1).  is the threshold for
unicast or multicast retransmissions. If the current number
of nodes nk , which need a retransmission is smaller than the
threshold , then unicast is used for the retransmission. p t
is the probability that the current number of nodes nk is
smaller than the threshold :
is used to obtain M H3 , p t can only be determined
. In this case, parameter p t is unnecessary to
determine M H3 . Nu is the mean number of receivers per
round for which a unicast retransmission is invoked:
E(N H3
r ) is the total number of transmissions that reach receiver
r with unicast and multicast from its parent node in
the ACK tree:
E(N H3
The number of ACKs that reach the sender or group leader
in the presence of ACK loss is given by:
E( e
a
pc is the probability that no AAK can be sent due to missing
AAKs of child nodes. The number of AAK query rounds L1 ,
is determined by the probability ^
p that a query fails:
E(L1 ) can be determined analogous to M A1 of protocol (A1)
(see Eq. 8) with Baa instead of R and
p instead of ~ p. Baa is
the number of receivers, the sender has to query when the
rst AAK timeout occurs, which is equal to the number of
receivers that have not already successfully sent an AAK in
the rst phase:
Baa X
Baa
E(N H3 r
is the probability that no AAK can be
sent in a round or that the AAK is lost. Queries are sent
with unicast to the nodes whose AAK is missing. The total
number of queries in all rounds are:
E(L H3
The number of AAKs received at the sender is the number
of AAKs in the retransmission phase plus the number of
AAKs in the AAK query phase, which is exactly one AAK
from every receiver in Baa (see Eq. 84).
E( e
S ) is entirely determined by:
E(W H3
E( e
a
E( e
aa )E(Waa
4.7.2 Receiver (leaf node)
The bandwidth requirement at the receiver is given by:
a
Wa (j)
aa
e L H3 aaq
Waa (l) +Waaq (l)
r;t is the total number of transmission that reach receiver
r. In contrast to the already obtained N H3
r , additional data
retransmissions are considered from other local groups that
may be received with probability
E(N H3
r
The number of transmissions that are acknowledged with an
ACK, L H3
a , or with an AAK, L H3
aa , are:
r
Here we assume that only transmissions from this local
group are acknowledged. e
the number of AAK queries
received by an receiver are:
e
aaq =Baa E(L H3
where 1=Baa is the probability to be a receiver that gets an
AAK query. Finally, the expectation for a receiver's band-width
requirements is:
E(W H3
a
E( e
4.7.3 Group leader (inner node)
The bandwidth requirement at a group leader consists of the
sender and receiver bandwidth requirements (see Eq. 64):
E(W H3
E(Wd;m (1)) E(N H3
r )p l E(Wd
Finally, the maximum throughput rates are:
H3
R =E(W H3
R g:
The total bandwidth consumption of protocol (H3) is:
(R G+ 1)W H3
4.8 Tree-Based Protocol (H4)
The generic denition of protocol class (H4) is given in Section
3.3. As in (H3), the correct transmission of a data
packet consists of two phases. In the rst phase, the data is
transmitted. If NAKs are received by the sender or group
leaders, retransmissions are invoked. We assume that the re-transmission
phase is nished before the second phase starts.
In this phase AAKs are sent from receivers to their parent
in the ACK tree. Missing AAKs are queried per unicast
messages by the sender and group leaders. In a NAK-based
protocol this is only reasonable if it is done after a certain
number of correct data packet transmissions rather than after
every transmission. Therefore, the costs for sending and
receiving AAKs (Waa; ) as well as the costs for querying
AAKs (Waaq; ) can be set to a proportionate cost of the
other costs.
4.8.1 Sender (root node)
e
Wn (j)
e
aa
E(W H4
E( e
E(L H4
E( e
E(M H4 ) and E( e L H4 ) are determined analogous to protocol
(H2). The number of AAK queries is determined by the
p that a query fails:
The number of query rounds E(L1) can be determined analogous
to M A1 of protocol (A1) (see Eq. 8) with Baa instead
of R and
p instead of ~
p. Baa is the number of receivers,
the sender has to query when the rst AAK timeout at the
sender occurs. Since receivers send one AAK autonomously
after a certain number of successfully receptions, the number
of nodes to query in phase 2 is the number of lost AAKs.
Baa X
Baa
The total number of unicast query messages in all rounds
are:
E(L H4
Using unicast, only those nodes are queried whose AAK is
missing. So nally, the number of received AAKs at the
sender is equal to the number of child nodes in the ACK
tree:
E( e
4.8.2 Receiver (leaf node)
E(W H4
r > 1)[E(O H4
r jO H4
E( e
r > 1)[E(O H4
r jO H4
| {z }
from this local group
| {z }
from other local groups
#2 and #3 can be obtained analogous to (N2) with B instead
of R. E( e
aaq ), the number of received AAK queries and
replied AAKs is (see Eq. 95):
e
aaq =Baa E(L H4
and the number of rounds O H4 is determined analogous to
(N2).
4.8.3 Group leader (inner node)
As the group leader role contains the sender role and the
receiver role as well, the processing requirements are:
E(W H4
l E(M H4 )(1 qD )E(Wd )
Finally, the maximum throughput rates at the sender, re-
ceiver, group leader and overall throughput are:
H4
R =E(W H4
R g: (112)
The total bandwidth consumption of protocol (H4) is:
(R G+ 1)W H4
5. NUMERICAL RESULTS
We examine the relative performance and bandwidth consumption
of the analyzed protocols by means of some numerical
examples. The mean bandwidth costs are set equal to 1
for data packets (Wd , W d;u , Wd;m ), 0.1 for control packets
(Wa , Wn , Waa , Waaq ) and 0.01 for periodical control packets
(W , Waa; and Waaq; ). The following graphs show
the throughput of the various protocol classes relative to
the normalized maximum throughput of 1.

Figure

1.a shows the bandwidth limited maximum through-put
of the sender-initiated protocol (A1) and the receiver-initiated
protocols (N1) and (N2). The loss probability for
data packets as well as control packets is 0.01 for the dotted
lines and 0.1 for the solid ones. The probability for simultaneous
NAK sending in (N2) is set to 0.1.
The results in Figure 1.a show, that a protocol based on positive
acknowledgments like (A1) is not applicable for large
receiver groups, since the large number of ACKs overwhelms
the sender. The performance of (N1) and (N2) is much
better than (A1)'s performance. Particularly, if packet loss
probability is low, only few NAK messages are returned to
the sender which improves the performance. (N2) with NAK
avoidance scheme provides the best performance of all non-hierarchical
approaches.
In

Figure

1.b, the results for the hierarchical protocol classes
(H1), (H2), (H3) and (H4) are shown. The number of child
nodes is set equal to 10 for all classes and the probability
for receiving packets from other local groups, p l , is set equal
to 0.001. (H3) is shown with which corresponds with
protocol (H1) except for the additional aggregated ACKs of
(H3). means that all retransmission are sent with
multicast.
All protocol classes experience a throughput degradation
with increasing group sizes although the local group size
0,3
0,4
0,6
Number of Receivers
Throughput
(a) sender and receiver-initiated protocols0,1
0,3
0,4
0,6
Number of Receivers
Throughput
(b) tree-based protocols

Figure

1: Throughput of reliable multicast protocols1000100000
Number of Receivers
Bandwidth
Consumption
(a) sender and receiver-initiated protocols1000100000
Number of Receivers
Bandwidth
Consumption H1 (p=0,01)
(b) tree-based protocols

Figure

2: Bandwidth consumption of reliable multicast protocols
remains constant. This results from our assumption that a
packet is received with probability outside the
scope of a local group. With increasing number of receivers,
the number of groups increase also and therefore more packets
from other local groups are received. Note that if each
local group is assigned a separate multicast address for re-
transmissions, no packets from other local groups are received
and therefore p l has to be set equal to 0. In this
case, the throughput of all hierarchical approaches remains
constant.
The protocols with negative acknowledgments and NAK
avoidance provide again the best performance. As it can
be further seen in the gure, the additional overhead for
periodical aggregated acknowledgments is very low, therefore
provides almost the same performance as (H2). In
case of (H3), the aggregated acknowledgments are sent after
every correct message transmission. Therefore, the performance
reduction compared to (H1) is more signicant than
between (H4) and (H2). If (H3)'s aggregated ACKs are also
sent periodically as in (H4), the performance would be almost
the same as (H1)'s performance. This means that the
additional costs for providing reliability even in the presence
of node failures are small and therefore acceptable for
protocol implementations.
Due to readability, the result for (H3) with
shown in the gure. With only retransmissions for
equal or more than 2 nodes are made using multicast and
with unicast otherwise. In this case, (H3) provides better
performance especially for a large number of receivers. For
a packet loss probability of 0.1 the performance is equal to
(H1).
By comparing Figure 1.a and 1.b it can be seen that tree-based
protocols are superior. Their throughput degradation
with increasing multicast group size is much smaller compared
to non-hierarchical approaches. Furthermore, they
are more robust against high packet loss probabilities.
The following gure depicts the bandwidth consumption of
all analyzed protocols. Figure 2.a shows that the bandwidth
consumption of (N2) for small group sizes is below (A1)'s
requirements. However, for large group sizes and higher loss
probability, (N2)'s bandwidth consumption is 2,5 times the
bandwidth consumption of (A1). (N1) provides the lowest
bandwidth consumption of the three classes.
In

Figure

2.b it can be seen that tree-based protocols require
less overall bandwidth than non-hierarchical approaches. In
tree-based protocols save in most cases about 50%
of the bandwidth costs and compared to (N2) up to 85%
(please note the logarithmic y-axis). The results for (H3)
with are not shown in the gure, which are in any
case lower compared to (H3) with In case of a
packet loss probability of 0.01, (H3) with
only the bandwidth of (H1). If the packet loss probability is
higher than 0.01, the bandwidth consumption is even smaller
than that of (H1). For example, with packet loss probability
0.1, (H3)'s bandwidth consumption with
than 30% below (H1)'s requirements. In contrast to non-hierarchical
approaches, i.e. if local group sizes are small,
NAK with NAK avoidance protocols require low bandwidth
costs. Therefore, protocols (H2) and (H4) provide the lowest
bandwidth consumption.
6.


We have analyzed the throughput in terms of bandwidth
requirements and the overall bandwidth consumption of
sender-initiated, receiver-initiated and tree-based multi-cast
protocols assuming a realistic system model with data
packet loss, control packet loss and asynchronous clocks.
Of particular importance are the analyzed protocol classes
with aggregated acknowledgments. In contrast to other hierarchical
approaches, these classes provide reliability even
in the presence of node failures.
The results of our numerical examples show that hierarchical
approaches are superior. They provide higher through-put
and lower overall bandwidth consumption compared to
sender-initiated or receiver-initiated protocols. The protocol
classes with aggregated acknowledgments lead to only
a small throughput decrease and slightly increased overall
bandwidth consumption compared to the same classes without
aggregated acknowledgments. This means, that the additional
costs for providing a reliable multicast service even
in the presence of node failures are small and therefore acceptable
for reliable multicast protocol implementations.
7.



--R

A reliable multicast framework for light-weight sessions and application level framing
A comparison of server-based and receiver-based local recovery approaches for scalable reliable multicast



How bad is reliable multicast without local recovery.
Reliable multicast transport protocol (RMTP).
A comparison of sender-initiated and receiver-initiated reliable multicast protocols
Performance comparison of sender-based and receiver-based reliable multicast protocols

PGM reliable transport protocol speci

An overview of the reliable multicast transport protocol II.
A reliable dissemination protocol for interactive collaborative applications.
--TR
XTP: the Xpress Transfer Protocol
A comparison of sender-initiated and receiver-initiated reliable multicast protocols
A reliable dissemination protocol for interactive collaborative applications
The case for reliable concurrent multicasting using shared ACK trees
A reliable multicast framework for light-weight sessions and application level framing
A comparison of reliable multicast protocols

--CTR
Thorsten Lohmar , Zhaoyi Peng , Petri Mahonen, Performance Evaluation of a File Repair Procedure Based on a Combination of MBMS and Unicast Bearers, Proceedings of the 2006 International Symposium on on World of Wireless, Mobile and Multimedia Networks, p.349-357, June 26-29, 2006
analysis;receiver-initiated;bandwidth;tree-based;reliable multicast;sender-initiated;AAK