A Multi-constrained Quality of Service Routing Based on Metrics Transform

The problem of multi-constrained QoS (quality of service) routing is known to be NP-complete. It has absorbed many attentions. Varied heuristic algorithms have been presented to solve it. Most of them were based on basic algorithms, for example BFS (Bread First Search), DFS (depth first search), Dijkstra, and Bellman-Ford. Among them, BFS has least computation complexity. Whereas BFS can deal with only one QoS constraint, this paper introduces an average idea of QoS metrics integrated with BFS fronting to multiple constraints. By the idea, additive metrics are converted to concave metrics on average. As this idea transforms additive metrics to concave metrics and uses BFS, we name it as additive-to-concave-BFS, or ATC-BFS.