An Efficient Fault-Tolerant Multicast Routing Protocol with Core-Based Tree Techniques.
AbstractIn this paper, we design and analyze an efficient fault-tolerant multicast routing protocol. Reliable multicast communication is critical for the success of many Internet applications. Multicast routing protocols with core-based tree techniques (CBT) have been widely used because of their scalability and simplicity. We enhance the CBT protocol with fault tolerance capability and improve its efficiency and effectiveness. With our strategy, when a faulty component is detected, some pre-defined backup path(s) is (are) used to bypass the faulty component and enable the multicast communication to continue. Our protocol only requires that routers near the faulty component be reconfigured, thus reducing the runtime overhead without compromising much of the performance. Our approach is in contrast to other approaches that often require relatively large tree reformation when faults occur. These global methods are usually costly and complicated in their attempt to achieve theoretically optimal performance. Our performance evaluation shows that our new protocol performs nearly as well as the best possible global method while utilizing much less runtime overhead and implementation cost.
Introduction
Reliable multicast communication is critical for the
success of many applications such as video/audio-
broadcasting, resource discovery, server location, etc.
Recently, these applications have become increasingly
popular due to the availability of the Internet.
In general, there are two approaches for multicast
routing protocols over the Internet: source-based-tree
routing and shared-tree routing. Many protocols have been
developed including Distance-Vector Multicast Routing
Protocol (DVMRP)[WPD88], Multicast Extensions to
Open Shortest-Path First (MOSPF) [M94b], Protocol
Independent Multicast (PIM) [DEFJLW96], and Core
Based Tree Multicast (CBT) [BFC93] etc.
A problem associated with source-based-tree routing is
that a router has to keep the pair information (source,
group) and it is a ONE tree per source. In reality the
Internet is a complex, heterogeneous environment, which
potentially has to support many thousands of active
groups, each of which may be sparsely distributed, this
technique clearly does not scale.
Shared tree based multicast routing is more scalable
than source-based-tree routing. For example, in
comparison with the source-based-tree approach, a shared
tree architecture associated with the CBT method offers an
improvement in scalability by a factor of the number of
active sources. Because of its scalability and simplicity,
core-based tree multicast protocols have been widely used
in many multicast systems.
However, the core-based-tree method may have a
reliability problem. Without any enhancement, a single
point of failure on the tree will partition the tree and hence
make it difficult, if not impossible, to fulfill the
requirement of multicasting [B97]. While various
solutions have been proposed to address the problem, they
usually require relatively large tree reformation when
faults occur [BFC93 and B97]. A global strategy of this
type can be costly and complicated.
In this paper, we aim at enhancing the CBT protocol
with fault-tolerant capability and improving its
performance in terms of packet delay and resource
consumption. Our approach can be briefly summarized as
follows:
localized configuration methodology is used. When
a faulty component in the network is detected, some pre-defined
backup path(s) is (are) used to bypass the faulty
component and thus enable the multicast communication
to continue. Backup paths can be identified off-line. At
runtime, our protocol will only require that routers on the
backup path(s) be reconfigured. In this way, we are able to
reduce the runtime overhead of the protocol without
compromising a significant amount of the performance.
Traditional CBT method routes a multicast packet
from its source towards the core of the shared tree. In
many situations, this could create traffic congestion (near
the core). We propose to route a multicast packet from its
source to the nearest node on the tree. This eliminates
potential congestion problem and improves the network
performance such as packet delay and resource
consumption.
Faults in the network occur randomly at runtime. In a
faulty situation, several routers may detect the fault and
initiate reconfiguration processes. A protocol should be
consistent in the sense that no matter how faults occur and
are detected, routers co-operate and restore the network in
an agreeable and operational state. In our protocol, the
functionality of routers during the fault management
process is clearly specified in accordance with the status
information available to the router. As a result, while
routers act asynchronously in a distributed environment,
the consistency requirement is met.
We evaluate the performance of our new fault-tolerant
multicast protocol. Performance data in terms of packet
delay and resource consumption are collected. They
indicate that in normal (i.e., non-faulty) situations, our
protocol outperforms the traditional core-based tree
protocol due to the fact that our protocol is capable of
eliminating potential traffic congestion. In the case when
faults do occur, our protocol performs very closely to the
best global reconfiguration method that provides the
theoretical performance bound.
2. Models and Notations
The network we consider consists of a number of nodes
(e.g., routers and hosts). Nodes are connected by physical
(dual directional) links along which packets can be
transmitted. Each link has an attribute called delay. A
network is modeled as a graph N(V, E) where V is a finite
set of vertices in N, representing nodes in the network
concerned; E is a finite set of edges, representing the links
between nodes.
A node (say R) is next hop from another node (say R')
if R can receive a packet directly from R' without going
through any other router. The key data structure which a
router uses for routing is routing table. An entry in a
routing table usually consists of fields for destination
address, next hop, distance, etc. For an incoming packet,
the router locates an entry in a routing table such that the
destination address of the packet matches the destination
address of the entry. In a router, once the next hop of a
packet is determined, the packet will be transported to a
proper output interface where the packet will be
transmitted into the associated output link, which, in turn,
connects to the next hop.
Obviously, if the network status is changed (e.g., some
link fails, some router joins, etc), the routing tables of
routers in the network may need to be updated. We say
that a router is reconfigured if its routing table is updated
(in accordance to some protocol).
Routers in the network cooperatively decide a path for
a packet and transmit the packet along the path. Formally,
P(X, Y) denotes a path from X to Y where X and Y are
nodes. Sometimes, we would like to list explicitly the
sequence of nodes in a path. We use terms "route" and
"path" interchangeably. d(P(X, Y)) denotes the total
distance of links on path P(X, Y). It is usually defined by a
numeric sum of the individual link distances.
A shortest path from X to Y is usually denoted as SP(X,
Y). That is, among all the path between X and Y, d(P(X, Y))
In this paper, we assume that for given X and Y, the
shortest path between them is unique. This assumption
simplifies our analysis but can be easily removed.
A packet is specified by addresses of its source and
destination. The source of a packet is usually a host. The
destination for a multicast packet is denoted as G that
represents a group of designated recipient hosts. That is, a
packet with multicast address G should be sent to all the
hosts in the recipient group.
At runtime, network components (e.g., links and
routers) can fail. We assume that the faulty state of a
component can be detected by (some of) its neighboring
routers. This can be achieved by a "keep-alive"
mechanism operating between adjacent (directly linked)
routers. A keep-alive mechanism may be implemented by
means of ICMP echo request/reply messages [D91].
3. Fault-Tolerant Multicast Protocol
3.1.

Overview

As stated earlier, our strategy is to enhance the existing
CBT protocol so that it will have fault tolerance capability
and at the same time its effectiveness and efficiency are
improved. Design and implementation of such a protocol
is, nevertheless, a challenging task. There are three
primary objectives:
Network performance. One of the protocol objectives
is to optimize various network performance metrics such
as the message delay, resource usage, etc.
Runtime overhead. To make the protocol fault-
tolerant, fault management function may be invoked at
runtime. Thus, the overhead of this function should be
minimized in order for the network to provide the best
possible services to the payload applications.
Consistency. The protocol should ensure that no
matter how a fault occurs and is detected, routers co-operate
and restore the network in an agreeable and
operational state. The consistency issue will be addressed
in Section 3.4.
While all these objectives are important, they may
conflict with each other. For example, reducing the
runtime overhead may compromise the network
performance. In our design of the protocol, we take a
balanced near-optimal performance and
at the same time we take measures to reduce runtime
overhead and to guarantee consistency.
Our fault-tolerant multicast routing protocol can be
divided into two parts:
Transmission Sub-Protocol that is responsible
for delivering multicast packets;
Management Sub-Protocol that will detect
faults, reconfigure the network, and hence provide
necessary infrastructure for the packet transmission sub-protocol
to achieve its mission.
3.2. Packet Transmission Sub-Protocol
Many protocols have been proposed and analyzed for
transmitting multicast packets. Proposed in [BFC93], the
Core-Based Tree Protocol (CBT) is a multicast routing
protocol that builds a single delivery tree per group that is
shared by all of the group's sources and receivers. An
advantage of the shared-tree approach is that it typically
offers more favorable scaling characteristics than all other
multicast algorithms [M94a, M94b, WPD88]. Because of
this, we choose CBT as our baseline protocol and intend to
enhance it with fault-tolerance capability and improve its
efficiency and effectiveness.
Step 1. Selecting a core for a given multicast group;
Step 2. For each member in the multicast group, locating
the shortest path from the member to the core;
Step 3. Merging the shortest paths identified in Step 2.
At runtime, when a source generates a multicast packet
the packet is first transmitted from the source to
(somewhere of) the tree. Once on the tree, the packet is
dispatched to all the branches of the tree and delivered to
all the receivers.
An interesting problem is what path to use for
transmitting a packet from its source to the tree. In
[BFC93], it is recommended that the shortest path from the
source to the core of the tree should be used. We call it the
"SP-To-Core" method. This method is simple, but it may
cause traffic congestion on the links close to the core
because the traffic from different sources is concentrated
there.
To improve network performance, we propose a new
method: For an off-tree router, we first find the shortest
paths from the router to all the nodes on the multicast tree.
Then, we select the path that is the shortest among these
shortest paths and use it to route a multicast packet from
this router to the tree. Because our method uses the
shortest of the shortest paths to the tree, we call it "SSP-to-
Tree".
Our method may appear to be more complex. But it
merely will take more off-line time to collect locations of
nodes and compute the shortest paths. Once the route is
determined, the runtime overhead is the same as the SP-to-
method.
Nevertheless, our new method may eliminate the
potential problem of traffic congestion. Figures 3-1 and 3-
2 show the traffic flow in a network with these two
methods. It is clear that with SSP-To-Tree method, the
bandwidth usage is better balanced and the traffic
congestion is removed.
3.3. Fault Management Sub-Protocol
Recall that Fault Management Sub-Protocol (FMSP) is
responsible for detecting faults and reconfiguring the
network once faults are detected. Thus, it provides
necessary infrastructure for the Packet Transmission Sub-Protocol
to deliver multicast packets. In this sub-section,
we will focus on the technique for handling single fault
that occurs on the Core-Based Tree.
3.3.1. General Approaches
Consider that at runtime a component (link or router) on
the Core-Based Tree becomes faulty. To continue
multicast communication, alternative routes for the
multicast packets, that used to be transmitted through the
faulty component, must be utilized. Two approaches can
be taken. With a global approach, the faulty status will be
informed to all the routers in the network. Consequently,
based on the faulty status the core-base tree may be rebuilt
and (potentially all) the routers may be reconfigured. Note
that all these operations have to be performed on-line.
Thus, while this may help to achieve theoretically optimal
performance, the runtime overhead (including the
notification of the faulty state and reconfiguration of
routers) may be too large to make this approach practical.
We take a local approach. Rather than rebuilding the
core-base tree and reconfiguring all the routers, we will
use pre-defined backup paths to bypass the faulty
component. We then just reconfigure the routers that are
on the involved backup paths. All the packets that were
supposed to be transmitted over the faulty link will be
routed via the backup path(s).
Obviously, our local approach is simple, and involves
very small runtime overhead in comparison with the global
approach. The performance evaluation in Section 4 will
show that our local reconfiguration approach performs
closely to the best possible global approach in most cases.
The fault management sub-protocol involves the following
tasks:
Initialization. The task here is to select backup paths.
detection. Assume that each router is continuously
monitoring the status of upstream link and router and
hence is able to determine if they are in a faulty state.
Backup path invocation. Once detecting a fault of
upstream link, the router should start notifying this state
information to all the routers on its backup path so that
they are ready to be used.
Router configuration. After all the routers on a backup
path confirm their readiness, they will be configured in
order to let traffic re-route via the backup path.
Before we describe each of the above tasks in detail, we
will first discuss the methods used for router
configuration. As we will see, these reconfiguration
methods have impact on the functions of other tasks.
3.3.2. Configuration Methods
We consider two methods to configure the routers on a
backup path. They differ in overhead and potential
performance. The first method is the virtual repair
R 1 R 2 and R 3 are source routers, each transmits 1 MBS multicast traffic. As a result, the
bandwidth usage on link from R 5 to R 7 is 3MBS, significantly higher than others.

Figure

3-1. A Traffic Flow with SP-To-Core Method
Link on CBT Link taken by off tree multicast traffic Other Link
3mbs
1mbs
1mbs
1mbs
R 11
R 7
R 8
R 4
R 5
R 6
core
R 9
R 12
are source routers, each transmits 1 MBS multicast traffic.
Due to the SSP-To-Tree method, the bandwidth usage on links is better balanced.

Figure

3-2. Traffic Flow with SSP-To-Tree Method
Link on CBT Link taken by off tree multicast traffic Other Link
1mbs
1mbs
1mbs
1mbs
R 7
R 4
R 5
R 6
1mbs 1mbs
core
R 8 R 9
R 12
method. With this method, no routing table is to be
changed on the invoked backup path. Instead, a pre-programmed
agent will be installed at the two end routers.
The agent will encapsulate a multicast packet, which was
supposed to be transmitted via the faulty component. The
encapsulated packet will be source-routed (via. the backup
path) to the other end of the backup path. The agent at the
other end of the backup path, once receiving the
encapsulated packet, will de-encapsulate it and transmit
along the normal path(s) where the packet should be
dispatched. Thus, the topology of the tree is virtually
unchanged, except that the faulty component is bypassed.
The second method is called the real repair method.
With this method, all the routing tables on the backup path
will be changed to reflect the new topology of the tree.
Packets are routed according to new routing table.

Figure

3-3 shows an example of using these two
methods. In Figure 3-3 (a) shows a portion of the network
with the original core-based tree. Assume that there is a
fault on the link between R 4 and R 6 . Let the backup path
that is used to reconnect the disjoint tree be <R 6 , R 5 , R 3 >.

Figure

3-3 (b) shows the situation after virtual repair. In
this case, the agent on R 3 will encapsulate the multicast
packets and source-route encapsulated packets to R 6 via
R 5 . Vice versa for the packets from R 6 to R 3 . However, R 3
still has to send multicast packets to R 5 . Hence, the load
between R 3 and R 5 is doubled because the tree is virtually
repaired. The situation will improve when the real repair
method is used as shown in Figure 3-3 (c). In this case, R 5
and R 6 will be reconfigured to recognize that while R 5
continues to be a son of R 3 , R 6 is now a new son of R 5 .
Hence, the packets between R 3 and R 5 will not be
transmitted twice.
Clearly, the virtual repair method is simple and can
quickly restore a path. But, it may utilize extra bandwidth
and cause longer delay because the routers on the path are
not configured to take the advantage of the new topology.
On the other hand, the real repair method may produce
better performance (in terms of packet delay, for example).
But this method is complicated and takes more runtime
overhead during the reconfiguration process. backup path
they can use. We discuss this topic next.
3.3.3. Selection of Backup Paths
3.3.3.1. Backup Paths with the Virtual Repair Method
For the sake of simplicity, we will first consider the
situation where fault only occurs on the core-based tree
and there is at most one fault at a time.
First, we need to introduce some notations. For any two
routers (R and R') on the core-base tree, R is a son of R'
and R' is the father of R if there is a link between R and R'
and R' is (in terms of distance) closer to the core than R.
R" is the grandfather of R if R" is the father of R'and R' is
the father of R. Note that the core router has neither father
nor grandfather. The sons of the core router have father
(which is the core), but have no grandfather. All other
routers have both father and grandfather.
One of the sons of the core is selected to be the backup-
core that will become core if the core fails. How to select
the backup-core is irrelevant to the function of the fault
management. In practice it may be selected from network
administrative point of view, as suggested in selecting the
core [BFC93].
With this method, every router on the tree, except the
core, owns a pre-defined backup path. For a router that has
grandfather (i.e., the one that is not a son of the core), its
backup path is a path that connects itself to its grandfather.
A constraint on the backup path of a router is that the path
does not contain the father of the owner. In Figure 3-4, for
example, <R 7 , R 4, R 2 , R 3 > cannot be the backup path of R 7
because it contains R 4 which is the father of R 7 . But <R 7 ,
can be the backup path of R 7 .
For a router that has no grandfather, its backup path is a
path that connects this router to the backup-core. In Figure
3-4, if the backup core is R 3 , then the backup path of R 2
could be <R 2 , R 3 >. For the backup-core router, its backup
path is a path that connects itself to the core, but bypasses
the link between itself and the core. In Figure 3-4, if the
backup-core is R 3 , then the backup path of R 3 could be
We assume that for each router on the tree (except the
core), at least one backup path exists. It easy to verify that
if a non-core router has no backup path, then the network
is not single fault tolerable. For a router, if multiple
backup paths exist, we select the one with the shortest
distance.
The routers on a backup path can be divided into three
kinds, namely owner, terminator, and on-path routers,

Figure

3-3. Reconfiguration Methods
(c) The CBT after Real Repair
(a) The Original CBT (b) The CBT after Virtual Repair
Link on CBT Other Link
Link on virtual path
Link with fault
x
core
R
x
R 7
R 5
R 8
R
R 9
R core
R
x
R 7 R
R 9
R core
R
x
R 9
R
R 6

Figure

3-4. Backup Path with the Virtual RepairMethod
Faulty Router Link on CBT Other Link
depending on their function in the fault management. The
first router on the backup path is the owner of backup path.
The router at the other end of a backup path is called
terminator. Other routers on the backup path excluding the
owner and terminator routers are called on-path routers.
3.3.3.2. Backup Paths with the Real Repair Method
As discussed above, with the virtual repair method the
shortest path from a router to its grandfather is used as its
backup path. One would think that we could define the
backup path in the same way for the real repair method.
Unfortunately, this idea does not work as shown by the
examples illustrated in Figure 3-5.

Figure

3-5 shows a portion of the network with the
core-based tree. Assume that there is a faulty router, R 4 .
Because of this, sub-trees T 1 and T 2 are disconnected from
the original core-based tree. In Figure 3-5, let the shortest
path from R 7 to its grandfather (R 3 ) be <R 7
and the shortest path from R 8 to its grandfather be
It is easy to see in Figure 3-5 that if these
two shortest paths were used as backup paths, a loop <R 3 ,
would occur. The example show that
if the backup path of a router transverses another
partitioned sub-tree, a loop may occur. Thus, the selection
of backup path with the real repair method is not a trivial
task. Before stating our selection method, we need to
establish some properties of the core-based tree.
Assume that there is a faulty router, R, on the core-based
tree. Because of this, the core-based tree is split into
m+1 sub-trees, namely T 0 , is the sub-tree
that contains the core, and T i m) is the sub-tree
whose root is a son of the faulty router. Let the
routers on T i be indexed R i,j . In particular, R i,0 is the root
of T i .
Let P i be the shortest path from R i,0 to the father of R.
relation  as follows: T i  T if and only if:
contains a router (say, R j,k ) that belongs to T j and
for any other R j',k' that is on T j' and is contained in P i ,
R j,k is closer to R i,0 than R j',k' is.
In this case, we say T
T is the first sub-tree which transverses, except T i itself.
For this relation, we have the following results.
Lemma 3-1. The relation  has the following properties:
Property A. The relation  is not cyclic. That is, there is
no subset of sub-trees (say, T k1 , T k2 , ., T kh ) such that T k1
T k2  T k3  .  T kh  T k1 .
Property B. Sub-tree T 0 does not relate itself to any other
Property C.Every other sub-tree T i (i > 0) uniquely relates
itself to some other sub-tree. That is, there is an unique T j
(j  i) such that T i  T j.
With this lemma, we can get the following theorem:
Theorem 3-1. For every sub-tree T i (i > 0), either
or there is a unique non-empty sequence of sub-trees <T i1 ,
such that
Proof. If then the theorem is proved. Assume (3-
1) is not true. By Property C, T i has to relate itself to some
sub-tree, say (T are
done. Otherwise, T i1 has to relate to another sub-tree, say
. We can keep doing this until we
reach T ih that does not relate to any other sub-tree. The
termination of this process is guaranteed because  is not
cyclic and there are finite number of sub-trees. Now, T ih
must be T 0 . Otherwise we violate Property C. The
sequence <T i1 , T i2 , ., T ih-1 > satisfies (3-2). Again by
Property C, this sequence has to be unique.
By Theorem 3-1, we have the following algorithm to
select backup paths with the real repair method.
Let P be the shortest path from R i,0 to its
grandfather.
the tail part of P such that it
terminates when it first reaches a router on T 0 . Else if T i
the tail
part of P such that it terminates when it first reaches an
router on T i1 .
The remaining of P is the backup path for R i,0 .
Once again, the first router of the backup path is called
the owner, the last one is the terminator, and the others
between them are on-path routers. Consider the example in

Figure

3-5. Using the above algorithm, we will select <R 7 ,
as the backup path of R 7 . R 7 is the owner, R 10 is
an on-path router, and R 11 is the terminator. Note that if
the virtual repair method is used, the backup path will be
much longer because over there we do not trim the path.
It is obvious that Theorem 3-1 guarantees that for every
son of the faulty router R, a backup path can be identified
with the above procedure. Trimming is necessary to avoid
the loops as shown in Figure 3-5.
3.3.4. Backup Path Invocation
Backup path invocation is the key part of fault
management algorithm. For the sake of completeness,

Figure

3-6 shows the entire fault Management algorithms
which are executed by different kinds of routers. These
algorithms are executed in the routers concurrently with
other tasks the routers have. In case a router plays multiple

Figure

3-5. Backup Path With the Real Repair Method
Link on CBT Other Link T
Faulty Router
R 4
R
R 7
R
R 8
R 12
R 4R 3
roles, these algorithms will be executed simultaneously in
the router.
It is clear from the above discussion that only the
routers on a backup path need to be re-configured in order
to repair a fault that occurs on the tree. This will result in
very small runtime overhead and can be scaled to large
networks. This is the advantage of our local configuration
approach.
3.4. Discussion
Our fault tolerant multicast protocol has the following
properties
In a normal situation (e.g., without any fault), our
protocol operates as a CBT protocol.
After the backup path is established, a tree is formed.
It consists of the backup path and all the links and routers
on the original tree except the faulty link or router.
For the newly formed tree, if the original core is not
fault, it will still be the core for the new tree. Otherwise,
the core of the new tree will be the backup-core.
Nevertheless, the above properties imply that while the
routers act asynchronously, our fault management sub-protocol
guarantees to bring the system into an agreeable
and operational state after a fault is detected. Thus, the
consistency requirement is met.
We would also like to argue that in addition to the
consistency requirement, our other design objectives
(stated in Section 3.1) are also well satisfied. Our local
approach obviously reduces the runtime overhead without
compromising much of the performance. Our SSP-To-
Tree method used in the packet transmission sub-protocol
eliminates the problem of potential traffic congestion and
will improve the delay performance. In Section 4, we will
show performance data that will quantitatively justify the
above claims.
Finally, we would like to say that our protocol can be
easily extended to deal with the case of multiple faults
that will not only impact paths on the CBT but also off-
tree ones. Due to the space limitation, we can not discuss
the extension in detail. The interested readers can refer
our paper [XXJZ99].
4. Performance Evaluation
4.1. Simulation Model
In this section, we will report performance results of
the new protocol introduced in this paper. To obtain the
performance data, we use a discrete event simulation
model to simulate data communication networks. The
simulation program is written in C programming language
and runs in a SUN SPARC work station 20. The network
simulated is the ARPA network [PG97]. During the
simulation, the multicast packets are randomly generated
as a Poisson process. Faults are also randomly generated
with X being the average life-time of a fault and Y being
the average inter-arrival time of faults. Thus, we have
Prob(The system is in a faulty
That is, Pf is the probability that the system is in a faulty
state. We will measure the network performance as
function of Pf. We are interested in the following metrics:
Average end-to-end delay (or average delay in short):
The end-to-end delay of a packet is the sum of the delays
at all the routers through which the packet passes.
Network resource usage: This is defined as the total
number of hops that (copies of) a multicast packet travel in
order to reach all the members in the multicast group.
Four systems are simulated:
SPP-To-Tree/V.R. In this system, our newly proposed
fault-tolerant multicast communication protocol is
simulated. For the router configuration method, the virtual
repair method (V.R.) is used.
SPP-To-Tree/R.R. This system is the same as SPP-To-
V.R. except that the real repair method (R.R.) is used.
SPP-To-Tree/N.F. In this system, our newly proposed
fault-tolerant multicast communication protocol is
simulated. But no fault is generated.
SP-To-Core/N.F. In this system, the original CBT
protocol is used. No fault is generated in the simulation.
We are interested in SP-To-Core/N.F. because it uses
the original CBT protocol. We take it as a baseline system.
All the performance measures of SPP-To-Tree/V.R., SPP-
To-Tree/R.R., and SPP-To-Tree/N.F. will be normalized
by the corresponding data of SP-To-Core/N.F. Thus, the
data we reported will be relative ones, relative to SP-To-
4.2. Performance Observations
The results of the average delay metric are shown in

Figure

4-1, while the results of network resource usage
metric are shown in Figure 4-2. In Figure 4-2, the
performance curve of SSP-to-Tree/N.F is virtually covered
by that of SSP-to-Tree/R.R, and is not easily visible.
From these data, we can make the following observations:
As expected, the SSP-to-Tree/N.F system achieves
better performance than the SP-to-Core/N.F. For example,
in

Figure

4-1, the average of relative delay of SSP-To-
Tree/N.F is 0.899. That is, on average the delay of SSP-
To-Tree is only 89.9% of that by SP-To-Core. Similarly,
in

Figure

4-2, the network resource usage of SSP-To-
Tree/N.F is 0.928, meaning the delay of SSP-To-Tree is,
on average, 92.8% of SP-To-Core/N.F.
Upstream
link/router
alive?
Initialization
msg(backup_path
to the upstream on the
backup path
Receive
msg(positive_conf
Reconfigure this router
yes
no
Receive
msg(backup_path
Initialization
Forward
to the upstream on the
backup path
Receive
Forward themsg and
reconfigure this router
yes
no
yes
Receive
msg(backup_path
Initialization
to the downstream on the
backup path
Reconfigure this router
yes
no
(a) Fault management
algorithm for
backup path owner
(b) Fault management
algorithm for
on-path router
(c) Fault management
algorithm for
backup path terminator
yes
no
no

Figure

3-6. Fault Management Algorithms
In the case of low probability of fault (say, Pf < 10%),
both SSP-to-Tree/V.R and SSP-to-Tree/R.R perform
almost identical to SSP-to-Tree/N.F. As we mentioned
earlier, SSP-To-Tree/N.F. provides a lower bound that any
(global) fault management algorithm can achieve. Hence,
we claim that when the fault probability is not too high,
our Fault Management Sub-Protocol with a localized
approach performs almost identically as the best possible
global one can. Meanwhile, our localized approach would
involve with low runtime overhead.
when the probability of fault becomes very large (i.e.,
greater than 10%), the performance of both the SSP-To-
Tree/V.R and SSP-To-Tree/R.R is clearly impacted. The
greater the Pf value, the worse the end-to-end delay and
resource usage are. Specifically, the delay performance
increases much more rapidly than the network resource
usage as Pf increases. This is because as more faults occur,
less functional links and routers are available. Hence,
some functional links and routers may become congested.
We note that 10% fault probability is really high and is
unlikely to happen in reality.
The system that uses the real repair method (SSP-To-
Tree/R.R.) always performs better than that with the
virtual repair method (SSP-To-Tree/V.R. This coincides
with our intuition because the real repair method explicitly
takes into account the new topology after a fault occurs.
and hence better utilizes the system resources.
5. Final Remarks
We have proposed and analyzed a new fault-tolerant
multicast communication protocol. Our protocol consists
of two sub-protocols: the Packet Transmission Sub-Protocol
and Fault Management Sub-Protocol. The Packet
Transmission Sub-Protocol uses an improved version of
the original CBT protocol. While maintaining the same
level of scalability, our improved CBT protocol has much
better performance because of the SSP-To-Tree
technology. For the Fault Management Sub-Protocol, we
take a localized approach that has a relatively low runtime
overhead. Our performance evaluation indicates that it
performs very closely to the possible theoretical bound.
Several extensions to our work are possible. We may
apply the technology we developed for the fault-tolerant
CBT protocol to anycast messages, and consequently
develop an integrated protocol for both multicast and
anycast messages. This protocol should be useful in
practice. For example, in a group of replicated database
servers, the multicast packets must be sent to all the
members in order to maintain information consistency. A
request of clients can be taken as an anycast message and
can be delivered to any of the server members.
Our protocol can also be extended to the applications
where the messages have both fault-tolerant and real-time
requirements. The key issue here is to model the traffic on
the shared multicast tree so that a delay bound can be
derived [MZ94, XJZ98].
Appendices
A-1. Proof of Lemma 4-1
Proof. By definition of T 0 , Property B is evident. Because of the
uniqueness of the shortest path, Property C is also obvious. Here,
we focus on the proof of Property A using contradiction.
Assume Property A is not true. That is, there is a sequence of
sub-tree <T k1 , T k2 , ., T k(n-1) , T kn , T k(n+1) .T kh > such that T k1
T k2  .  T k(n-1)  T kn .  T kh  T k1 . See Figure A-1.
Note that T 0 is the sub-tree that contains the core.
For a sub-tree (say, T kn , 1 < n < h) in the subset, let R kn,0 be
the root, P kn be the shortest path from R kn,0 to the father of the
faulty router (In figure A-1, R 0,1 is the father of R f ). Because T kn
Assume that R k(n+1),1 is the first
router in T k(n+1) encountered by P kn . Similarly, we assume that
1 For the convenience of discussion, (n+1) presents an
addition operation with mod n. That is,

Figure

A-1. Sub-Trees and Backup Paths with a Faulty Router
R Fault Router Link on CBT Backup Path T .T kn .T kh Sub-trees
core
R 0,0
R 0,2
R kh,1 R kh,2
R kh,0
R k(n+1),0
R k(n+1),2
R kn,1
R k(n-1),2
R k(n-1),1
R k(n-1),0
R k1,0
R k1,1 R k1,2
R
R kn,0
R kn,2
R 0,1
R k(n+1),1

Figure

4-1. Average Delay Relative to SP-to-Core/N.F1.01.41.80.01% 0.06% 0.32% 1.78% 10.00% 56.23%
Probability of Fault
era
ge
Del
ay
SSP-to-Tree/V.R
SSP-to-Tree/R.R.
SSP-to-Tree/N.F.

Figure

4-2. Network Resource Usage relative to SP-to-Core/N.F0.850.951.051.150.01% 0.06% 0.32% 1.78% 10.00% 56.23%
Probability of Fault
Net
wo
rk
Res
our
ce
Us
age
SSP-to-Tree/V.R.
SSP-to-Tree/R.R.
SSP-to-Tree/N.F.
R kn,1 is the first router in T kn encountered by the shortest path
from R k(n-1),0 to R 0,1 .
Denote SP f (X, Y) to be the shortest path from X to Y
conditioned on that a fault (Rf) has occurred. Recall that SP(X,
Y) represent the shortest path from X to Y in the normal case
(where there is no fault). Obviously, SP f (X, Y) varies depending
on the location of the fault. Nevertheless, SP f (X, Y) will be
different from SP(X, Y) if SP(X, Y) involves with the faulty
component.
Since the P kn is the shortest path from R kn,0 to R 0,1 when R f is
faulty, it is then denoted as SP f (R kn,0 , R 0,1 ). Similarly, SP f (R kn,0 ,
R k(n+1),1 ) denotes the portion of P kn from R kn,0 to R k(n+1),1 , and
(R k(n+1),1 , R 0,1 ) the portion of P kn from R k(n+1),1 to R 0,1 .
Using the above notations related path P kn and sub-tree T kn
h, we can derive some inequalities. Because
d(SP(R kn ,1, R f ) is the shortest path from R kn,1 to R f under normal
situation and
we have:
(R kn,1 , R k(n-1),0
Furthermore, because when R f is faulty
(R kn,0 , R 0,1
(R kn,0 , R k(n+1),1 (R k(n+1),1 , R 0,1
we have
(R kn,0 , R k(n+1),1 (R k(n+1),1 , R 0,1
(R kn,1 , R 0,1 )). (A-4)
Summing up both sides of (A-2) and (A-4), we have:
(R kn,0 , R k(n+1),1
(R k(n+1),1 , R 0,1 (R kn,1 , R k(n-1),0
(R kn,1 , R 0,1
Further, if we sum up (A-5) both sides for n from 1 to h,
we have
LHS < RHS (A-6)
where
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
f
f
kh
kn
f
kn
kn
kn
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
RHS
kn
kn
kn
kh
kh
kn
Since we assume that the links are dual directional, for any
routers X and Y, we have d(SP(X,
Because of this, (A-8) can be
reorganized as follows:
For the convenience otherwise Similarly,
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
RHS
kn
kn
kn
kh
kh
kn
f
Exchanging some items in (A-9), we
have
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
R
R
d
f
kh
kn
kn
kn
f
kn
kn
kh
kn
where LHS is given in (A-7). This contradicts to (A-6).

Acknowledgement

This work was partially sponsored by the Air Force Office of Scientific
Research, Air Force Material Command, USAF, under grant (F49620-96-
1-1076), by City University of Hong Kong under grant 7000765, and by
Cery HK with grant 9040352. The U.S. Government is authorized to
reproduce and distribute reprints for governmental purposes not
withstanding any copyright notation thereon. The views and conclusions
contained herein are those of the authors and should not be interpreted as
necessarily representing the official polices or endorsements, either
express or implied, of the Air Force Office of Scientific Research, the
U.S Government, Texas A&M University, City University of Hong Kong
or Cerg Hong Kong.



--R


Based Trees (CBT
ICMP Router Discovery Messages.
The PIM Architecture for Wide-Area Multicast Routing
Hard Real-Time Communication in Multiple-Access Networks
OSPF Version 2.
Multicast Extensions to OSPF.

Distance Vector Multicast Routing Protocol
Routing Algorithms for Anycast Messages
An Efficient Fault-Tolerant Multicast Routing Protocol with Core-Based Tree Techniques
--TR

--CTR
Zongming Fei , Mengkun Yang, A proactive tree recovery mechanism for resilient overlay multicast, IEEE/ACM Transactions on Networking (TON), v.15 n.1, p.173-186, February 2007
Weijia Jia , Gaochao Xu , Wei Zhao , Pui-On Au, Efficient Internet Multicast Routing Using Anycast Path Selection, Journal of Network and Systems Management, v.10 n.4, p.417-438, 2002
multicast routing;core-based trees;fault tolerance