# Posts Tagged ‘heuristic algorithms

### Constrained 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.

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 delayconstrained 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  at,  but  its execution  time  is  exponential  and  used  only  for comparison  with  other  algorithms.  Heuristic  for  this problem  is  presented  in, 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  in.  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.