Quality-of-service (QoS) requirements for the timely delivery of real-time multimedia raise new challenges for the networking world. A key component of QoS is QoS routing which allows the selection of network routes with sufficient resources for requested QoS parameters. Several techniques have been proposed in the literature to compute QoS routes, most of which require dynamic update of link-state information across the Internet. Given the growing size of the Internet, it is becoming increasingly difficult to gather up-to-date state information in a dynamic environment. We propose a new technique to compute QoS routes on the Internet in a fast and efficient manner without any need for dynamic updates. Our method, known as Selective Flooding, checks the state of the links on a set of pre-computed routes from the source to the destination in parallel and based on this information computes the best route and then reserves resources. We implemented Selective Flooding on a QoS routing simulator and evaluated the performance of Selective Flooding compared to source routing for a variety of network parameters. We find Selective Flooding consistently outperforms source routing in terms of call-blocking rate and outperforms source routing in terms of network overhead for some network conditions. The contributions of this thesis include the design of a new QoS routing algorithm, Selective Flooding, extensive evaluation of Selective Flooding under a variety of network conditions and a working simulation model for future research.

An ad hoc network is a collection of mobile wireless devices that cooperate with each other to route packets amongst themselves. The main difficulty in designing routing algorithms for such a network is the large number of topology changes that the network undergoes due to device movement. Selective flooding is a routing technique that is more resilient to topology changes than traditional algorithms but is more bandwidth efficient than pure flooding. An on-demand selective flooding algorithm has been designed and tested on the ns-2 simulator. In scenarios involving a large number of topology changes, selective flooding outperforms other ad hoc network routing techniques. Unfortunately, selective flooding is much more bandwidth hungry and is unable to scale to handle reasonable traffic loads. Interestingly, the analysis of selective flooding reveals major problems with traditional ad hoc networking techniques. Many current algorithms demonstrate shortcomings when dealing with bursty traffic, and current wireless hardware cannot handle ad hoc networking traffic in an efficient manner. These issues need to be addressed before ad hoc networking technology can become feasible for widespread use.

An ad hoc network is a collection of mobile wireless devices that cooperate with each other to route packets amongst themselves. The main difficulty in designing routing algorithms for such a network is the large number of topology changes that the network undergoes due to device movement. Selective flooding is a routing technique that is more resilient to topology changes than traditional algorithms but is more bandwidth efficient than pure flooding. An on-demand selective flooding algorithm has been designed and tested on the ns-2 simulator. In scenarios involving a large number of topology changes, selective flooding outperforms other ad hoc network routing techniques. Unfortunately, selective flooding is much more bandwidth hungry and is unable to scale to handle reasonable traffic loads. Interestingly, the analysis of selective flooding reveals major problems with traditional ad hoc networking techniques. Many current algorithms demonstrate shortcomings when dealing with bursty traffic, and current wireless hardware cannot handle ad hoc networking traffic in an efficient manner. These issues need to be addressed before ad hoc networking technology can become feasible for widespread use.

The routing strategy used in today's Internet is best-effort service, where all data packets are treated equally. This type of service is not suited for applications such as video conferencing, and video on demand, that requires the availability of certain resources (such as bandwidth) to be guaranteed for them to function properly. The routing in this context, called Quality-of-Service (QoS) Routing, is the problem of finding suitable paths that meet the application's resource requirements. The majority of proposed QoS routing schemes operate by maintaining the global state of the network, and using this knowledge to compute the QoS route. However, all these schemes suffer from the inherent drawback of scalability, because of the need for each node to collect state information about the complete network. The other type of QoS routing schemes do not maintain network state information, but instead flood the network with QoS connection establishment requests. This type of scheme suffers from excessive message overhead during QoS connection establishment. In this thesis, we present a new QoS routing algorithm that is a combination of the above-mentioned two schemes (i.e., global state and flooding based). The algorithm aims at minimizing the message overhead associated with these two schemes and still maintaining the positive aspects of both of them. The basic idea of the algorithm is: to reach to a destination, the path(s) will always pass through a specific set of intermediate nodes. The algorithm discovers such intermediate nodes (limited by a hop count threshold value needed to reach there). When a QoS connection request arrives at a node, it selects the feasible path leading to the intermediate node for the requested destination. The QoS connection establishment message (or routing message) is forwarded along this path. When the message arrives at the intermediate node, the further path is decided through same logic. To decide the path that leads to the intermediate node, the algorithm maintains the link state related to these intermediate nodes, and link state updates are restricted only with regard to these intermediate nodes. Because of this restriction in link state updation, one has less message overhead, compared to the global state based routing scheme. Further, the algorithm tries to group these intermediate nodes in such a way that the routing message need be sent to only one of the grouped intermediate nodes, and still makes sure that all the possible paths are covered. Therefore, one has a reduced message overhead because of grouping.