DISTRIBUTED QOS ROUTING ALGORITHMS IN WIRELESS NETWORKS

Abstract

In this thesis three distributed routing algorithms have been studied, the ticket based probing algorithm, the flooding algorithm and the shortest path algorithm. The ticket based probing algorithm is considered as a heuristic solution to the DCLCR (delay constrained least cost routing) problem. Each path is probed by one probing packet called probe, in each probe the probe state is recorded. A ticket is the permission of searching one path. The source node issues a number of tickets based on the available state information. One guideline is that more tickets are issued for the connections with tighter requirements. The flooding algorithm floods routing messages from the source to the destination. Each routing message accumulates the delay of the path it has traversed, and the message proceeds only if the accumulated delay does not exceed the delay bounds. it is equivalent to the ticket based probing algorithm with infinite number of tickets. The flooding algorithm does not take into consideration the low cost path, it does not make priority to the path with lower cost. On the other hand it prefer the path with the lowest delay regardless the cost of the selected path. The shortest path algorithm maintains a state vector at each node i. The vector has an entry to every possible destination t, containing two elements, D(t) and H,(t). D(t) is the delay of the least delay path from i to t, and H,(t) is the next hop on the least delay path. When a request arrives at s with D<= D(t), the algorithm sends out routing message along the least delay path to check the current resources availability for possible connection establishment.