Routing with QoS constraints in integrated services networks

Though the complexity for finding QoS guaranteed route in integrated services networks is proved to be NP-complete, the proof has been done without the assumption of any specific service discipline. Because each service discipline has different QoS bound computation expressions, we propose that QoS routing algorithm should be designed for specific service discipline used. We then present a proof that, when the considered QoS constraints are bandwidth, delay, delay jitter, and loss free, by employing Weight Fair Queueing (WFQ) service discipline, the complexity of the problem could be reduced to that of shortest path routing without any QoS constraints. Therefore we can search such a multiple QoS constrained route in polynomial time. We also present that routing algorithm (called `QoSR_BF'), which is a modified version of Bellman-Ford. QoSR_BF can, not only successfully find the route that can satisfy the required QoS constraints, but also utilize resources wisely to minimize the call blocking probability for future calls.