Abstract
As a potential solution to provide quality of service (QoS) for next-generation IP networks, QoS routing (QoSR) seeks to find a multi-constrained path, where the scalability and routing performance are still open problems. We propose a novel Clustering-based Distributed Precomputation algorithm (CDP) for multi-constrained QoSR. After dominating path selection is analyzed to omitting numerous dominated paths, a clustering technique is further presented for dominating path aggregation in routing computation. These two techniques in turn achieve efficient aggregation of the QoS routing table. CDP greatly decreases the computational complexity on a single node by utilizing the distributed computation on each node in the network. Simulation results confirm that CDP not only has low computational complexity, but also achieves high routing performance with good scalability on both QoS parameters and the network scale.
Supported by: (1) the National Natural Science Foundation of China (No. 60403035); (2) the National Major Basic Research Program of China (No. 2003CB314801).
Chapter PDF
Similar content being viewed by others
References
Xiao, X., Ni, L.M.: Internet QoS: A big picture. IEEE Network 13(2), 8–18 (1999)
Cui, Y., Xu, K., Wu, J.P.: Precomputation for Multi-constrained QoS Routing in High-speed Networks. In: Proceedings of the IEEE INFOCOM 2003, San Francisco, CA (April 2003)
Cui, Y., Wu, J.P., Xu, K., et al.: Research on internetwork QoS routing algorithms: a survey. Chinese Journal of Software 13(11), 2065–2076 (2002)
Chen, S., Nahrstedt, K.: An overview of quality-of-service routing for next-generation high-speed networks: Problems and solutions. IEEE Network 12(6), 64–79 (1998)
Wang, Z., Crowcroft, J.: Quality-of-service routing for supporting multimedia applications. IEEE Journal on Selected Areas in Communications 14(7), 1228–1234 (1996)
Cui, Y., Xu, K., Wu, J., et al.: Multi-constrained routing based on simulated annealing. In: IEEE ICC 2003 (2003)
Korkmaz, T., Krunz, M.: Multi-Constrained Optimal Path Selection. In: IEEE INFOCOM 2001, vol. 2, pp. 834–843 (2001)
Xiao, L., Lui, K.S., Wang, J., Nahrstedt, K.: QoS Extension to BGP. In: IEEE ICNP (2003)
Garey, M.S., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)
Orda, A., Sprintson, A.: QoS routing: the precomputation perspective. In: IEEE INFOCOM 2000, vol. 1, pp. 128–136 (2000)
Yuan, X., Liu, X.: Heuristic Algorithms for Multi-Constrained Quality of Service Routing. In: IEEE INFOCOM 2001, vol. 2, pp. 844–853 (2001)
Shaikh, A., Rexford, J., Shin, K.G.: Evaluating the impact of stale link state on quality-of-service routing. IEEE/ACM Transactions on Networking 9(2) (April 2001)
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
Cui, Y., Wu, J. (2005). Clustering-Based Distributed Precomputation for Quality-of-Service Routing. In: Sunderam, V.S., van Albada, G.D., Sloot, P.M.A., Dongarra, J.J. (eds) Computational Science – ICCS 2005. ICCS 2005. Lecture Notes in Computer Science, vol 3515. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11428848_72
Download citation
DOI: https://doi.org/10.1007/11428848_72
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26043-1
Online ISBN: 978-3-540-32114-9
eBook Packages: Computer ScienceComputer Science (R0)