Hop-by-hop routing algorithms for premium-class traffic in DiffServ networks

For the provision of quality of service (QoS) in the Internet, differentiated service (DiffServ) has been proposed as a cost-effective solution. Traffic is classified into several service classes with different priorities, premium class traffic being the highest. The routing algorithm used by the premium class service has significant effects on the traffic of all other classes as well as its own. Shortest hop-count routing used in the current Internet is no longer sufficient in DiffServ networks. Based on hop-by-hop routing, an optimal routing algorithm must be found for premium class traffic such that (1) it works correctly and efficiently for premium traffic; (2) it reduces negative influences (such as bandwidth starvation, excessive delay jitter, etc.) to other traffic classes. This problem, the optimal premium-class routing (OPR) problem, is NP-complete. To handle the OPR problem, first, we analyze the strength and weaknesses of two existing algorithms (widest-shortest-path algorithm and bandwidth-inversion shortest-path algorithm). Second, we apply to the OPR problem a novel heuristic algorithm, called the enhanced bandwidth-inversion shortest-path (EBSP) algorithm. We prove theoretically the correctness of the EBSP algorithm, i.e., it is a consistent and loop-free hop-by-hop routing algorithm. Our extensive simulations in different network environments show clearly that the EBSP algorithm performs better for premium class traffic in complex, heterogeneous networks than the other two hop-by-hop routing algorithms.