Non-Bifurcated Routing in Wireless Multi-Hop Mesh Networks

In this paper we consider traffic routing in 802.11- based multi-hop wireless mesh networks (WMNs). Interest in such networks arises since they offer flexible, and cost effective means of providing Internet connectivity to communities of subscribers. Successful deployment of such networks, however, hinges on the ability of the network to serve subscribers at the data rates specified by service agreements, as well as providing quality of service to certain key traffic types, such as TCP traffic, delay-jitter sensitive traffic, and traffic that requires synchronized delivery to end users. Since delays on different routes in such networks may vary widely, routing of the above traffic types can potentially benefit from non-bifurcated routing schemes that do not split flows among multiple paths. In this paper, we formalize the problem of non-bifurcated routing, while meeting subscriber demands, as an optimization problem. We present a heuristic algorithm that utilizes results from the theory of maximum flows, and insights into the routing problem to obtain efficient solutions. Simulation experiments indicate improved achieved throughput, and delay-jitter results over the use of the standard Dynamic Source Routing (DSR) algorithm.