Dynamic multipath allocation in Ad Hoc networks

Ad hoc networks are characterized by fast dynamic changes in the topology of the network. A known technique to improve quality of service (QoS) is to use multipath routing, where packets (voice/video/...) from a source to a destination travel in two or more maximal disjoint paths. We observe that the need to find a set of maximal disjoint paths can be relaxed by finding a set of paths S wherein only bottlenecked links are bypassed. In the proposed model, we assume that there is only one edge along a path in S that is a bottleneck and show that by selecting random paths in S the probability that bottlenecked edges get bypassed is high. We implemented this idea in the MRA system, which is a highly accurate visual ad hoc simulator currently supporting two routing protocols, AODV and MRA. We have extended the MRA protocol to use multipath routing by maintaining a set of random routing trees from which random paths can be easily selected. Random paths are allocated/released by threshold rules monitoring the session quality. The experiments show the following: (i) session QoS is significantly improved; (ii) the fact that many sessions use multiple paths in parallel does not depredate overall performances and (iii) the overhead in maintaining multipath in the MRA algorithm is negligible.¹