An Efficient Heuristic Algorithm for QoS-Driven Multicast Tree Generation
| Autor: | Manas Ranjan Kabat, Rajib Mall, Sandeep Kumar Mohanty, Chitta Ranjan Tripathy |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Tree (data structure)
Source-specific multicast Multicast Computational complexity theory Protocol Independent Multicast Computer science Distributed computing Quality of service Shortest path problem Computer Science::Networking and Internet Architecture Xcast Time complexity Computer Science::Information Theory |
| Zdroj: | 2006 International Conference on Advanced Computing and Communications. |
| DOI: | 10.1109/adcom.2006.4289926 |
| Popis: | Many multimedia communication applications require a source to transmit messages to multiple destinations subject to quality of service (QoS) delay constraint. The problem to be solved is to find a minimum cost multicast tree where each source to destination path is constrained by a delay bound. This problem has been proven to be NP-complete. In this paper, we present a more efficient heuristic algorithm, namely, cost sensitive delay constrained multicast (CSDCM) algorithm, based on a novel heuristic function, to construct a minimum cost delay bounded multicast tree. A noteworthy feature of this algorithm is that it has very high probability of finding the optimal solution in polynomial time with low computational complexity. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|