The basic means of conserving resources via multicasting is sharing: instead of transmitting packets from a sender to each receiver separately, we can arrange for routes that share some links to carry each packet only once. Furthermore, we can design the routes in such a way as to maximize shared links and thus minimize resource consumption. We can picture a multicast route as a tree rooted at the sender with a receiver at each leaf, and possibly some receivers on internal nodes.
Traditional unicast routing decisions intend to
minimize transmission costs or delay (depending on the interpretation
of the metric used), using shortest path algorithms, with the
Dijkstra[34] and
Bellman-Ford[35][36] algorithms being two common cases.
These algorithms find optimal routes between one node (the sender)
and all other nodes in the network (including all receivers). Thus, a
straightforward solution to the multicast routing problem can be based on
the shortest path trees produced by these algorithms,
by pruning off any branches that do not lead to any receivers in the
group (see Figure 1 and Figure 2).
Although details
vary according to the base algorithm[37][38], there
are some observations that apply to those approaches in general. On the
plus side, these algorithms are easy to implement, as direct extensions of
existing ones, and thus fast to deploy; additionally, each path is optimal
by definition, regardless of changes in group membership, and this optimality
comes essentially for free. On the down side, these algorithms suffer from
poor scalability since they make unnecessary calculations (routing to all
network nodes) and, even though they are not affected by membership
dynamics, they are affected by network dynamics, i.e. link failures and
network reconfigurations, which can cause them to frequently repeat routing
calculations. For large internetworks with widely dispersed groups,
either the scale of the network or the continuous network changes will
restrict use of these algorithms to subnetworks that already use
their unicasting counterparts.
Cost optimization in multicasting can be viewed from another angle: overall cost optimization for the distribution tree. The shortest path algorithms concentrate on pairwise optimizations between the source and each destination and only conserve resources when paths happen to converge. We can instead try to build a tree that exploits link sharing as much as possible, and by duplicating packets only when paths diverge, minimize total distribution cost, even at the expense of serving some receivers over longer paths. Since we need a tree that reaches all receivers and may use any additional network nodes on the way, finding the optimal tree is identical to solving the Steiner tree problem with the sender and the receivers as the Steiner points[39] (see Figure 3). Even though this problem is NP-complete[40], approximation algorithms exist with proven constant worst case bounds[41][42]. Implementations of such algorithms have been shown to produce low cost multicast trees with very good average behavior[43][44][45]. The advantage of this approach is its overall optimality with respect to a single cost metric, such as transmission cost. However, the disadvantages are also important: the algorithm needs to run in addition to the unicast algorithms, and it will itself have scaling problems for large networks. Furthermore, optimality is generally lost after group membership changes and network reconfigurations if the tree is not recomputed from scratch. Thus, Steiner tree algorithms are best suited to slowly changing environments since changes lead to expensive recalculations to regain optimality.
Both approaches discussed above suffer from an inability to maintain their measure of optimality in a large and dynamic network. Approaches for extending these algorithms to deal with changes in group membership without complete tree reconfigurations include extending an existing tree in the cheapest way possible to support a new group member and pruning the redundant branches of the tree when a group member departs[46][44]. The quality of the trees after several local modifications of this sort will deteriorate over time though, eventually leading to a need for global tree reconfiguration.
A radically different approach to the routing problem opts for a solution in realistic settings by adopting the practical goal of finding good rather than optimal trees, that can also be easily maintained. The departure point for this approach is the center based trees[43] which is an optimal cost tree that instead of being rooted at the sender, is rooted at the topological center of the receivers. Even though such a tree may not be optimal for any one sender, it was proved to be an adequate approximation for all of them together. The implication is that one basic tree can serve as a common infrastructure for all senders. Thus, maintenance of the tree is greatly simplified and nodes on the tree need only maintain state for one shared tree rather than many source rooted trees. Since this method has been developed for broadcasting rather than multicasting, much of the theoretical investigation does not hold when we prune the broadcast trees to get multicast ones. In addition, the topological center of the tree, apart from being hard to find for the multicast case, will not even be of use in a dynamic environment.
Practical proposals for multicast routing abandon the concrete optimality
claims discussed above, but keep the basic idea of having a single shared
multicast tree for all senders to a group. This is a departure
from approaches that build one tree for each sender. Routing is
then performed by defining one or more core[47] or
rendez-vous[48] points to serve as the basis for
tree construction
and adding branches by separately routing optimally (in the unicast sense)
packets from the senders to these fixed points and then from there to the
receivers (see Figure 4).
Again, merging of paths is exploited whenever possible, but it is
not an explicit goal of the routing calculations. Instead, because of the
concentration of
paths around the fixed points, common paths are expected to arise.
These trees are clearly not optimal in any strict sense, but their
advantages are numerous. First, a shared tree for the whole group means that
this approach scales well in terms of maintenance costs as the number of
senders increases. Second, the
trees can be made quite efficient by clever choice of the fixed points.
Third, routing is performed independently for each sender and receiver,
with entering and departing receivers influencing only their own path to the
fixed points of the single shared tree,
employing any underlying mechanism available for unicast routing. This last
property means that network and group membership dynamics can be dealt with
without global recalculations and by using available mechanisms. In practice,
these multicast algorithms are expected to use
the underlying unicast algorithms,
but are
independent of them. Interoperability with different unicast schemes, coupled
with the scalability of the shared trees, make these algorithms ideal for
use on very large scale heterogeneous networks. The fixed points can also
be selected so as to facilitate hierarchical routing for very
large internetworks, further enhancing scalability properties.