Shortest Path Algorithm for Multicast Routing in Multimedia Applications

A new heuristic algorithm is proposed for constructing multicast tree for multimedia and real-time applications.
The tree is used to concurrently transmit packets from source to multiple destinations such that exactly one
copy of any packet traverses the links of the multicast tree. Since multimedia applications require some
Quality of Service, QoS, a multicast tree is needed to satisfy two main goals, the minimum path cost
from source to each destination (Shortest Path Tree) and a certain end-to-end delay constraint from source to
each destination. This problem is known to be NP-Complete. The proposed heuristic algorithm solves this
problem in polynomial time and gives near optimal tree. We first mention some related work in this area then
we formalize the problem and introduce the new algorithm with its pseudo code and the proof of its complexity
and its correctness by showing that it always finds a feasible tree if one exists. Other heuristic algorithms
are examined and compared with the proposed algorithm via simulation.

Handling group communication is a key requirement for numerous applications that have one source sends
the same information concurrently to multiple destinations. Multicast routing refers to the construction
of a tree rooted at the source and spanning all destinations. Generally, there are two types of such a tree,
the Steiner tree and the shortest path tree. Steiner tree or group-shared tree tends to minimize the total
cost of the resulting tree, this is an NP-Complete problem. Shortest path tree or source-based trees tends
to minimize the cost of each path from source to any destination, this can be achieved in polynomial time
by using one of the two famous algorithms of Bellman and Dijkstra and pruning the undesired links. Recently,
with the rapid evolution of multimedia and real-time applications like audio/video conferencing, interactive
distributed games and real-time remote control system, certain QoS need to be guaranteed in the resulted
tree. One such QoS, and the most important one is the end-to-end delay between source and each destination,
where the information must be sent within a certain delay constraint D. By adding this constraint to the
original problem of multicast routing, the problem is reformulated and the multicast tree should be either
delay constrained Steiner tree, or delay-constrained shortest path tree. Delay constrained Steiner tree
is an NP-Complete problem, several heuristics are introduced for this problem each trying to get near
optimal tree cost, without regarding to the cost of each individual path for each destination. Delay
constrained shortest path tree is also an NP-Complete problem. An optimal algorithm for this problem
is presented, but its execution time is exponential and used only for comparison with other algorithms.
Heuristic for this problem is presented, which tries to get a near optimal tree from the point of
view of each destination without regarding the total cost of the tree. An exhaustive comparison between
the previous heuristics for the two problems can be found. We investigate the problem of delay
constrained shortest path tree since it is appropriate in some applications like Video on Demand (VoD),
where the multicast group has a frequent change, and every user wants to get his information in the lowest
possible cost for him without regarding the total cost of the routing tree. Also shortest path tree always
gives average cost per destination less than Steiner tree. We present a new heuristic algorithm that finds
the required tree in polynomial time.

Advertisements

, , , , , , , , , , , , , ,

  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: