Our motivation for routing multicast traffic along trees rather than along arbitrary paths was transmission cost minimization through link sharing; for continuous media, the volume of data transferred makes this goal even more important. However, for real time multimedia applications we must take into account two additional factors: delay constraints, particularly for interactive applications, and media heterogeneity. As we have already discussed, separate handling of media streams is essential if we want to use the most effective coding techniques for each stream, and in order to gain maximum benefits from hierarchical coding. The question arises then whether we should use the same or separate distribution trees for each stream. Considering the load that continuous media puts on network links and the interaction among admission control and routing, it would seem better to use a separate tree for each media type. Thus, each media stream (or sub-stream) can ask for the appropriate quality of service parameters and get routed accordingly, and receivers would choose to connect to any subset of the trees. On the other hand, the management overhead of multiple trees per source would be prohibitive.
Turning to delay requirements, if we use transmission delay for link cost
during routing, we can easily see that the shortest delay tree, made up
from the shortest paths from sender to each receiver, is not the same as the
tree of total minimal cost, which maximizes link sharing at the expense of
individual path delays. We have then a global tree metric (tree cost) and
many individual receiver metrics (path delays) that are in conflict. Since
we cannot hope to optimize everything, we can try to optimize cost,
subject to the
constraint that delay is tolerable. As we have
seen, interactive applications can be characterized by upper bounds
on end-to-end delay and/or limits on jitter. In this sense, it is reasonable
to design the tree so as to optimize total cost while keeping individual
paths within their respective bounds.
This new problem is essentially a version of the Steiner tree
problem with additional constraints on the paths (see
Figure 5). Even though it is
NP-complete, fast heuristic algorithms[69][70]
that are nearly optimal on the average have been developed. A similar
formulation can be used when the
constraint is link capacities which must not be exceeded, instead of a delay
bound. Again, heuristics exist to solve this variant of the
problem[71].
Group dynamics are an obstacle in maintaining optimality, whatever the method of constructing the initial trees. Since repeating all routing calculations whenever members join or leave the group is prohibitively expensive, an alternative is to prune extraneous links when a member leaves the group, and add the most economical (and admissible, if delay bounds have been specified as above) extension path towards a new member, either from a fixed or from the optimal location in the existing group[72]. Rather than making modifications blindly, thus deteriorating tree quality up to the point of needing complete tree redesign, the most advanced algorithms store some of the state accumulated during tree construction and make only local calculations that still satisfy the requirements of the application. However, simulations have shown that even simple multicast routing[73], using the shortest path tree, is not significantly worse in terms of cost from the optimal solutions or the near optimal heuristics. Since shortest delay trees are easily built and modified using the underlying unicast routing and they never deteriorate in terms of delay, but simply vary in their inefficiency in terms of total cost, if an application is prepared to accept a moderate cost overhead, it can avoid special multicast tree construction and maintenance methods.
A similar cost vs. simplicity trade-off is involved when using shared trees
for all senders to a group[47]. But in this case, both total cost and
path delays will suffer. The overhead under extreme conditions has been
determined theoretically[43] but in practice, simulations have been
used to determine the average performance of such schemes in terms of cost and
delay sub-optimality[74]. Interestingly,
again the overhead in practice is not excessive in either dimension, making
shared trees an acceptable solution for many applications. Furthermore,
a single tree constructed using the underlying unicast routing mechanisms
minimizes state and maintenance overhead.
Unfortunately, apart from sub-optimality, shared trees also suffer from traffic
concentration[74], since they route data from all senders through
the same
links. For these reasons, more recent proposals[48] try to combine
shared trees and shortest paths by starting each group connection in
the shared tree mode and then changing individual paths to shortest delay
ones on the receiver's request. The overhead vs. delay trade-offs
and the point at which change from one paradigm to the other should
occur can be determined experimentally[75].
A final point regarding routing is dealing with network dynamics. Unicast routing in most internetworks is dynamic in order to guide packets around hosts and links that are down. Even though this is sufficient for best effort service, it creates problems when routes are carefully planned to support quality of service guarantees. With multicasting the problem is even more complicated as resource reservations are shared and group dynamics interact with network reconfigurations. Little is known on how to deal with such problems, but a conservative approach would be to make the multicast routing algorithm ignore unnecessary routing changes, i.e. changes that reduce route costs but are not due to failed links or switches. This approach, called route pinning, preserves the quality guarantees as far as physically possible. Note that multicast algorithms using the underlying unicast routing mechanisms need to ignore such dynamic optimizations in order to implement route pinning.