Stability routing with constrained path length

摘要

Quality of Service (QoS) routing is known to be an NP-hard problem in case of two or more additive constraints and several exact algorithms and heuristics have been proposed to address this issue. In this work, we consider a particular two-Constrained Quality of Service Routing Problem where one constraint is superlative and the other is comparative. We consider the superlative constraint to represent the path stability and the comparative constraint to represent the path length in hops. As such, we are proposing to solve the problem of finding the most stable path not exceeding C hops. We propose an exact polynomial algorithm based on the Extended Bellman-Ford algorithm (EBFA) to solve a two quality of service constraints problem. Besides, we extend our algorithm to compute all routes from a given source node towards all the remaining nodes in the network with almost no additional cost.