Abstract
The delay and delay variation-bounded multicast tree (DVBMT) problem is known to be NP-complete. In this paper, we propose an efficient distributed dynamic multicast routing algorithm to produce routing trees with delay and delay variation constraints. The proposed algorithm is fully distributed, and supports the dynamic reorganizing of the multicast tree in response to changes for the destination. Simulations demonstrate that our algorithm is better in terms of tree delay and routing success ratio as compared with other existing algorithms, and performs excellently in delay variation performance under lower time complexity, which ensures it to support the requirements of real-time multimedia communications more effectively.
Supported by: (1)the National High Technology Research and Development Plan of China (No.2001AA113161); (2)the National Natural Science Foundation of China (No.60273035); (3)the Research and Development Foundation of Nanjing University of Science & Technology (No.96126).
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Rouskas, G.N., Baldine, I.: Multicast Routing with End-to-End Delay and Delay Variation Constraints. IEEE Journal on Selected Areas in Communications 15(3), 346–356 (1997)
Sheu, P.R., Chen, S.T.: A Fast and Efficient Heuristic Algorithm for the Delay- and Delay Variation-bounded Multicast Tree Problem. Computer Communications 25(8), 825–833 (2002)
Yu, Y.P., Qiu, P.L.: A Heuristic of Multicast Routing with Delay and Delay Variation Constraints. Journal of China Institute of Communications 24(2), 132–137 (2003)
Zhang, K., Wang, H., Liu, F.Y.: Distributed Multicast Routing for Delay and Delay Variation-bounded Steiner Tree using Simulated Annealing. Computer Communications 28 (2005) (to be published)
Jia, Z.F., Varaiya, P.: Heuristic Methods for Delay Constrained Least Cost Routing Using k-Shortest-Paths. In: Proc. of IEEE INFOCOM 2001 (2001)
Bellman, R.E.: Dynamic Programming. Princeton University Press, New Jersy (1997)
Waxman, B.M.: Routing of Multipoint Connections. IEEE Journal on Selected Areas in Communications 6(9), 1617–1622 (1988)
Salama, H.F.: Multicast Routing for Real-time Communication on High-speed Networks. PhD Dissertation, North Carolina State University, Department of Electrical and Computer Engineering (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhang, K., Zhang, H., Xu, J. (2005). An Efficient Distributed Dynamic Multicast Routing with Delay and Delay Variation Constraints. In: Lu, X., Zhao, W. (eds) Networking and Mobile Computing. ICCNMC 2005. Lecture Notes in Computer Science, vol 3619. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11534310_23
Download citation
DOI: https://doi.org/10.1007/11534310_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28102-3
Online ISBN: 978-3-540-31868-2
eBook Packages: Computer ScienceComputer Science (R0)