Share Email Print

Proceedings Paper

Polynomial time algorithm for hop constrained QoS routing
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 8 August 2003
PDF: 5 pages
Proc. SPIE 5245, Internet Quality of Service, (8 August 2003); doi: 10.1117/12.511062
Show Author Affiliations
Shekhar Verma, Indian Institute of Information Technology and Management (India)
Anil Kishore Saxena, Indian Institute of Information Technology and Management (India)

Published in SPIE Proceedings Vol. 5245:
Internet Quality of Service
Mohammed Atiquzzaman; Mahbub Hassan, Editor(s)

© SPIE. Terms of Use
Back to Top