Polynomial time algorithm for hop constrained QoS routing

Shekhar Verma; Anil Kishore Saxena

doi:10.1117/12.511062

8 August 2003 Polynomial time algorithm for hop-constrained QoS routing

Shekhar Verma, Anil Kishore Saxena

Proceedings Volume 5245, Internet Quality of Service; (2003) https://doi.org/10.1117/12.511062
Event: ITCom 2003, 2003, Orlando, Florida, United States

Abstract

The basis of a QoS-based routing algorithm is a dynamic network dependent cost function that is used to find the optimal or at least a feasible route across the network. However, all QoS-based routing algorithms suffer from a major drawback. The cost function at the core of the algorithms identifies segments of the network where resources are ample and exploits them to the benefit of connections that would otherwise cross a congested portion of the network. Thus, the algorithms consume more resources than Minimum Hop routing would do when the network traffic is non-stationary and heavy. QoS-based routing, thus, wastes resources and performs poorly compared with Minimum Hop routing in the event of congestion. The crux of the discussion is that whatever is gained at low or medium network loads, is offset at high network loads. What is required is a resilient algorithm that either allows the migration of a QoS-based routing algorithm to a Minimum Hop algorithm at high loads or an algorithm that merges Minimum Hop and QoS characteristics. The study opts for the latter approach and proposes and exhibits a hop constrained QoS routing algorithm that outperforms traditional QoS routing algorithms during simulation. This routing technique is based on an approximation algorithm that solves the hop constrained routing problem. The algorithm is derived from a dynamic programming FPAS scheme and finds the shortest walk for a single source destination pair in a graph with restricted number of hops when all the edge costs are non-negative. Simulated results demonstrate that routing technique based on the algorithm is robust to changes in the traffic pattern and consistently outperforms other QoS based routing techniques under heavy load conditions.

Citation Download Citation

Shekhar Verma and Anil Kishore Saxena "Polynomial time algorithm for hop-constrained QoS routing", Proc. SPIE 5245, Internet Quality of Service, (8 August 2003); https://doi.org/10.1117/12.511062

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available