The exponential growth of Internet applications has created new challenges for the control and administration of large-scale networks, which consist of heterogeneous elements under dynamically changing traffic conditions. These emerging applications need guaranteed service levels, beyond those supported by best-effort networks, to deliver the intended services to the end user. Several models have been proposed for a Quality of Service (QoS) framework that can provide the means to transport these services. It is desirable to find efficient routing strategies that can meet the strict routing requirements of these applications. QoS routing is considered as one of the major components of the QoS framework in communication networks. In QoS routing, paths are selected based upon the knowledge of resource availability at network nodes and the QoS requirements of traffic. Several QoS routing schemes have been proposed that differ in the way they gather information about the network state and the way they select paths based on this information. The biggest downside of current QoS routing schemes is the frequent maintenance and distribution of global state information across the network, which imposes huge communication and processing overheads. Consequently, scalability is a major issue in designing efficient QoS routing algorithms, due to the high costs of the associated overheads. Moreover, inaccuracy and staleness of global state information is another problem that is caused by relatively long update intervals, which can significantly deteriorate routing performance. Localized QoS routing, where source nodes take routing decisions based solely on statistics collected locally, was proposed relatively recently as a viable alternative to global QoS routing. It has shown promising results in achieving good routing performance, while at the same time eliminating many scalability related problems. In localized QoS routing each source-destination pair needs to determine a set of candidate paths from which a path will be selected to route incoming flows. The goal of this thesis is to enhance the scalability of QoS routing by investigating and developing new models and algorithms based on the localized QoS routing approach. For this thesis, we have extensively studied the localized QoS routing approach and demonstrated that it can achieve a higher routing performance with lower overheads than global QoS routing schemes. Existing localized routing algorithms, Proportional Sticky Routing (PSR) and Credit-Based Routing (CBR), use the blocking probability of candidate paths as the criterion for selecting routing paths based on either flow proportions or a crediting mechanism, respectively. Routing based on the blocking probability of candidate paths may not always reflect the most accurate state of the network. This has motivated the search for alternative localized routing algorithms and to this end we have made the following contributions. First, three localized bandwidth-constrained QoS routing algorithms have been proposed, two are based on a source routing strategy and the third is based on a distributed routing strategy. All algorithms utilize the quality of links rather than the quality of paths in order to make routing decisions. Second, a dynamic precautionary mechanism was used with the proposed algorithms to prevent candidate paths from reaching critical quality levels. Third, a localized delay-constrained QoS routing algorithm was proposed to provide routing with an end-to-end delay guarantee. We compared the performance of the proposed localized QoS routing algorithms with other localized and global QoS routing algorithms under different network topologies and different traffic conditions. Simulation results show that the proposed algorithms outperform the other algorithms in terms of routing performance, resource balancing and have superior computational complexity and scalability features.

The exponential growth of Internet applications has created new challenges for the control and administration of large-scale networks, which consist of heterogeneous elements under dynamically changing traffic conditions. These emerging applications need guaranteed service levels, beyond those supported by best-effort networks, to deliver the intended services to the end user. Several models have been proposed for a Quality of Service (QoS) framework that can provide the means to transport these services. It is desirable to find efficient routing strategies that can meet the strict routing requirements of these applications. QoS routing is considered as one of the major components of the QoS framework in communication networks. In QoS routing, paths are selected based upon the knowledge of resource availability at network nodes and the QoS requirements of traffic. Several QoS routing schemes have been proposed that differ in the way they gather information about the network state and the way they select paths based on this information. The biggest downside of current QoS routing schemes is the frequent maintenance and distribution of global state information across the network, which imposes huge communication and processing overheads. Consequently, scalability is a major issue in designing efficient QoS routing algorithms, due to the high costs of the associated overheads. Moreover, inaccuracy and staleness of global state information is another problem that is caused by relatively long update intervals, which can significantly deteriorate routing performance. Localized QoS routing, where source nodes take routing decisions based solely on statistics collected locally, was proposed relatively recently as a viable alternative to global QoS routing. It has shown promising results in achieving good routing performance, while at the same time eliminating many scalability related problems. In localized QoS routing each source¿destination pair needs to determine a set of candidate paths from which a path will be selected to route incoming flows. The goal of this thesis is to enhance the scalability of QoS routing by investigating and developing new models and algorithms based on the localized QoS routing approach. For this thesis, we have extensively studied the localized QoS routing approach and demonstrated that it can achieve a higher routing performance with lower overheads than global QoS routing schemes. Existing localized routing algorithms, Proportional Sticky Routing (PSR) and Credit-Based Routing (CBR), use the blocking probability of candidate paths as the criterion for selecting routing paths based on either flow proportions or a crediting mechanism, respectively. Routing based on the blocking probability of candidate paths may not always reflect the most accurate state of the network. This has motivated the search for alternative localized routing algorithms and to this end we have made the following contributions. First, three localized bandwidth-constrained QoS routing algorithms have been proposed, two are based on a source routing strategy and the third is based on a distributed routing strategy. All algorithms utilize the quality of links rather than the quality of paths in order to make routing decisions. Second, a dynamic precautionary mechanism was used with the proposed algorithms to prevent candidate paths from reaching critical quality levels. Third, a localized delay-constrained QoS routing algorithm was proposed to provide routing with an end-to-end delay guarantee. We compared the performance of the proposed localized QoS routing algorithms with other localized and global QoS routing algorithms under different network topologies and different traffic conditions. Simulation results show that the proposed algorithms outperform the other algorithms in terms of routing performance, resource balancing and have superior computational complexity and scalability features. / Umm AlQura University, Saudi Arabia

The Quality of Service (QoS) routing approach is gaining an increasing interest in the Internet community due to the new emerging Internet applications such as real-time multimedia applications. These applications require better levels of quality of services than those supported by best effort networks. Therefore providing such services is crucial to many real time and multimedia applications which have strict quality of service requirements regarding bandwidth and timeliness of delivery. QoS routing is a major component in any QoS architecture and thus has been studied extensively in the literature. Scalability is considered one of the major issues in designing efficient QoS routing algorithms due to the high cost of QoS routing both in terms of computational effort and communication overhead. Localized quality of service routing is a promising approach to overcome the scalability problem of the conventional quality of service routing approach. The localized quality of service approach eliminates the communication overhead because it does not need the global network state information. The main aim of this thesis is to contribute towards the localised routing area by proposing and developing some new models and algorithms. Toward this goal we make the following major contributions. First, a scalable and efficient QoS routing algorithm based on a localised approach to QoS routing has been developed and evaluated. Second, we have developed a path selection technique that can be used with existing localized QoS routing algorithms to enhance their scalability and performance. Third, a scalable and efficient hierarchical QoS routing algorithm based on a localised approach to QoS routing has been developed and evaluated.

The Quality of Service (QoS) routing approach is gaining an increasing interest in the Internet community due to the new emerging Internet applications such as real-time multimedia applications. These applications require better levels of quality of services than those supported by best effort networks. Therefore providing such services is crucial to many real time and multimedia applications which have strict quality of service requirements regarding bandwidth and timeliness of delivery. QoS routing is a major component in any QoS architecture and thus has been studied extensively in the literature. Scalability is considered one of the major issues in designing efficient QoS routing algorithms due to the high cost of QoS routing both in terms of computational effort and communication overhead. Localized quality of service routing is a promising approach to overcome the scalability problem of the conventional quality of service routing approach. The localized quality of service approach eliminates the communication overhead because it does not need the global network state information. The main aim of this thesis is to contribute towards the localised routing area by proposing and developing some new models and algorithms. Toward this goal we make the following major contributions. First, a scalable and efficient QoS routing algorithm based on a localised approach to QoS routing has been developed and evaluated. Second, we have developed a path selection technique that can be used with existing localized QoS routing algorithms to enhance their scalability and performance. Third, a scalable and efficient hierarchical QoS routing algorithm based on a localised approach to QoS routing has been developed and evaluated.