Emulating a Source Based Multicast Routing Tree for the Core Based Tree Protocol

Gary S. Withrow

1.0 Committee Members and Signatures:

Dr. C. E. Chow: date
: date
: date

2.0 Introduction

Group communication is becoming more important in distributed network environments. Supporting the group communication is multicast routing protocols which allows transfer of information as effectively as possible to all members of the group. One of the highly complex existing problems in multicast routing is how to effectively handle the changes in a network with dynamic properties. Changes can occur for several reasons such as evolving group membership, available bandwidth, or network topology.

An ideal multicast routing algorithm is one that will design a tree that spans the members of the group with only these characteristics: [1]

Evolve with group membership. The algorithm will need to differentiate group members so only actual members are reached.
Minimize state information that is contained in the node routing tables.
Optimize the route based on cost functions.
Avoid traffic concentrations on any subset of the links.

There are several techniques that can be used to implement multicast routing protocols and each have their strengths and weaknesses. These techniques are:

Flooding algorithms
Spanning Trees such as the Steiner Tree
Source-based routing trees using the reverse path forwarding technique.
Center based trees or Group Shared Trees

Although the first three mentioned techniques may be suitable in smaller, dense, bandwidth-plentiful, networks, one unresolved problem is to determine the most effective multicast routing protocol that can be used for sparsely populated networks in a globally dynamically evolving environment.

Currently running on top of the Internet is the Mbone IP application which uses such protocols as the Distance Vector Multicast Routing Protocol (DVMRP) or a link-state protocol called Multicast OSPF [2]. These protocols where designed for networks where bandwidth is generally plentiful and group members are located in relative proximity such as campus environments. Although these dense-mode multicast methods may minimize delay, they do not scale well over sparse area networks, and are therefore inefficient. [3] Much of this is due to the broadcast behavior of the algorithms and amount of state information that must be kept for the network nodes.

Based on the important characteristics of a multicast routing algorithm, in order to meet the demands of multicast routing in sparse networks, there have been two main protocols proposed which both use a group-shared tree approach. These are the Core Based Tree (CBT) [4] and the Protocol Independent Multicast - Sparse Mode (PIM-SM) [6]. Group-shared trees are the most recent proposals to multicast techniques. These trees scale much better than source-based trees in widely distributed networks since they only require a router to maintain state information for each group, and not each group-source pair, thereby reducing the router state memory significantly. They also provide significant bandwidth saving when used in sparse networks since data is not sent to unneeded nodes [1]. However, one current limitation and common criticism of the shared trees is that they are more adept to suffer from traffic concentration when traffic from several sources of one group converge near the core center. Also, they may create suboptimal routes resulting in longer delays for receivers.

The fundamental difference between the CBT and the PIM-SM is the ability to switch between a shared tree and a source based tree. [1][3] The PIM-SM solution to the traffic concentration concern is that the protocol allows for both a shared tree technique and a source-based tree technique that can be changed when the source's data rate exceeds a given threshold [3]. Currently the CBT does not support the dynamic reconfiguration of the CBT to a version of a source-based tree, and there is concern that traffic concentration and suboptimal routes will remain [2]. In depth simulations have been performed in [7] and [8] which have concluded that based on current technology, the CBT protocol is more favorable than the PIM-SM protocol mainly due to requiring fewer routing table entries and fewer associated timers.

3.0 Thesis

3.1 Plan

The main goal of this thesis will be to extend the abilities of the CBT protocol to allow it to dynamically emulate a source-based tree on demand while still retaining its original shared tree protocol. This will allow the CBT protocol to reduce the traffic concentration in particular environments and minimize suboptimal routing paths. In the process of expanding the abilities of the CBT technique, other goals will be to minimize the router state information, which is one of CBT's benefits over PIM-SM and preserve the scalability of the CBT's shared tree architecture.

The following models will all need to be implemented:

PIM-SM Shared Tree

PIM-SM Source-Based Tree

CBT (existing shared tree)

CBT Source-based extension emulation

After the above models are complete, simulations will be run comparing the following:

CBT (Source Based Model) <----> CBT (Existing Shared Tree Model)
This will determine which tree will be better suited for different networks, and verify the reduction of traffic concentration in the pure shared tree.
CBT (Source Based Model & Existing Shared Tree Model) <----> CBT (Existing Shared Tree)
This will show how the combination of both trees implemented in the CBT protocol compare against the current shared tree model.
CBT (Source Based Model) <----> PIM-SM (Source Based Model)
This will show how each source based model matches up standalone.
CBT (both tree models) <----> PIM-SM (both tree models)
This will show overall how the improved CBT compares with the existing PIM-SM protocol.

3.2 Tasks:

Learn C++ (Currently a good understanding of object oriented languages exist from programming in Eiffel)
Attain simulation input from previous algorithm comparisons (S. Deering, Nat. Labs, ...)
Generate a simulation input random generator
Study both CBT and PIM-SM protocols
Create CBT existing shared tree in C++
Create PIM-SM Shared Tree in C++
Create PIM-SM Source Based Tree in C++
Create the CBT source based extension in C++
Simulate all comparisons shown above
Write Thesis

3.3 Deliverables:

Extended source based model for the CBT
Full thesis report
Description of the simulation language I am using for simulation output reading
Description of all simulation input networks and parameters
Resulting output simulation from the simulation code executions
Documentation of comparisons
Graph comparisons of the four main comparisons of all metrics and constants

4.0 References

Diot, Christophe and Dabbous, Walid and Crowcroft, Jon, "Multipoint Communication: A Survey of Protocols, Functions, and Mechanisms", IEEE J. Select. Areas Commun., vol 15, pp. 227-290, April 1997.
Semeria, C. and Maufer, T., "Introduction to IP Multicast Routing",, January 1997.
Deering, S., Estrin, D., Farinacci, D., Handley, M., Helmy, A., Jacobson, V., Liu, C., Sharma, P., Thaler, D., Wei, L., "Protocol Independent Multicast-Sparse Mode (PIM-SM) : Motivation and Architecture", , October 24, 1996
Deering, S., Estrin, D., Farinacci, D., Handley, M., Helmy, A., Jacobson, V., Liu, C., Sharma, P., Thaler, D., Wei, L., "Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification",, March 15, 1997.
Ballardie, A., "Core Based Trees (CBT) Multicast Routing and Architecture", , March 1997.
Ballardie, A., "Core Based Trees (CBT) Multicast Routing -- Protocol Specification --", , March 1997.
Billhartz, T., Cain, J., Farrey-Goudreau, E., Fieg, D., Batsell, S.G., "Performance and Resource Cost Comparisons for the CBT and PIM Multicast Routing Protocols", IEEE J. Select. Areas Commun., vol 15, pp. 304-215, April 1997.
Billhartz, T., Cain, J., Farrey-Goudreau, E., Fieg, D., Batsell, S.G., "Simulation Comparison of CBT and PIM Multicasting for Distributed Interactive Simulation (DIS)", http://www.epm.ornl.gov/~batsell/pubs.html, Proceedings of the 1996 SCS Western Multiconference, SCS, January, 1996.