Name
Abstract | ||
|---|---|---|
We consider a variation of a constrained Steiner minimal tree problem that is applicable for multicast conferencing. We assume a network having a cost and delay values associated with each edge. Then, we find an optimal shared tree with minimal cost subject to the constraint that the delay between any two nodes of the tree must be bounded by some maximal value. Such a constraint on the delay is appropriate for an application such as a multicast conference that uses a shared tree. We consider a new heuristic algorithm for solving this problem. Our approach is inspired by Lagrangian relaxation techniques. We first develop a novel distance metric on trees, termed delta diameter. Using this metric, our algorithm then uses a Prim-like labeling algorithm coupled with the Takahashi Matsuyama Steiner tree algorithm. Simulation results show how cost and delay can be traded off smoothly. Using simulation, we also compare our heuristic with the optimal achievable. We believe that our approach is practical for dynamically building shared trees to support applications such as real-time video conferencing with delay constraints. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/QSHINE.2004.15 | QSHINE |
Keywords | DocType | ISBN |
steiner minimal tree problem,minimal cost subject,new heuristic algorithm,delay constraint,simulation result,multicast conference,multicast conferences,lagrangian relaxation technique,shared tree,multicast conferencing,takahashi matsuyama steiner tree,overlay networks,constrained diameter steiner trees,distance metric,real time,video conferencing,lagrangian relaxation,tree data structures,overlay network,heuristic algorithm,steiner tree | Conference | 0-7695-2233-5 |
Citations | PageRank | References |
7 | 0.57 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sudhir Aggarwal | 1 | 463 | 31.19 |
| Madhura Limaye | 2 | 7 | 0.57 |
| Arun Netravali | 3 | 88 | 6.46 |
| Krishan K. Sabnani | 4 | 1510 | 286.64 |