Efficient Bandwidth Constrained Routing Protocols For Communication Networks

Abstract

QoS routing is one of the major building blocks for supporting QoS in communication networks and, hence, a necessary component of future communication networks. Bandwidth- Constrained Routing Algorithm (BCRA) may help to satisfy QoS requirements such as end-to-end delay, delay-jitter etc when WFQ-like (Weighted Fair Queuing) scheduling mechanisms are deployed. The existing algorithms for bandwidth constrained routing suffer from high message overhead and have a high computational and space complexity. The work presented in the thesis, therefore, focuses on the different techniques that an be used to reserve bandwidth for a unicast connection with low protocol overhead in terms of number of messages. We have compared the performance of the proposed routing algorithms using simulation studies with other bandwidth constrained routing algorithms. The call blocking ratio and message overhead have been used as the performance metric to compare the proposed algorithm with the existing ones.

We present three source routing algorithms for unicast connections satisfying the band- width requirement. The first two routing algorithms are based on the partitioning of the network. The link-state broadcasts are limited to the partition. In the first algorithm, the source node queries the other partitions for the state information on a connection request and computes the path based on the information received from the other partitions. The second algorithm is based on state aggregation. The aggregated state of other partitions is maintained at every node. The source node finds a feasible path based on the aggregated information. The path is expanded in every partition, if required, at the time of resource reservation. The third QoS routing algorithm uses the Distance Vector Tables to find a route for a connection. If the shortest path satisfies the bandwidth requirement, then it is selected; otherwise a random deviation is taken at the point where bandwidth requirement is not satisfied and shortest path algorithm is again followed. In all the three algorithms presented, the packets carry the entire path information to the destination node. Therefore, no per connection information is required to be maintained at the intermediate nodes. Simulation results indicate that the proposed algorithms indeed help educing the protocol overhead considerably, and at the same time they give comparable or better performance in terms of resource utilization across a wide range of workloads.