Routing is a critical element of wireless mesh network design and serves to enhance the network's capacity as a whole and the performance of individual flows. Achieving both robustness and efficiency in mesh routing is an important, yet challenging issue due to uncertain traffic demands. To ensure routing performance while retaining robustness, we explore using knowledge of historical traffic demands. Two concepts of robustness, namely congestion robustness and performance ratio robustness are examined. We show that though a routing that is robust with respect to the interior of a convex region of traffic demands implies future robustness, the similar property does not hold for the boundaries of the region because the performance ratio is not limited by the boundaries, while the absolute congestion is. We develop a performance-ratio robust routing formulation for multi-radio, multi-channel networks that exploits traffic demands that fall into a predicted region. A linear problem transformation is presented to solve this highly complex non-linear formulation. A detailed simulation study is conducted over representative topologies with a real traffic trace to evaluate the novel algorithm. We find a strong performance improvement with little margin for further gains.

Wireless mesh networks have attracted increasing attention and deployment as a high-performance and low-cost solution to last-mile broadband Internet access. Traffic routing plays a critical role in determining the performance of a wireless mesh network. To investigate the best routing solution, existing work assumes traffic demand is static and known a priori. However, recent studies of wireless network traces show that traffic demand, is highly dynamic and hard to estimate. This paper studies an oblivious routing algorithm that is able to provide the optimal worst-case performance on all possible traffic demands users may impose on the wireless mesh network. To the best of our knowledge, this work is the first attempt that investigates oblivious routing in the context of wireless mesh networks. A trace-driven simulation study demonstrates that our oblivious routing solution performs competitively.

Traffic routing plays a critical role in determining the performance of a wireless mesh network. To investigate the best solution, existing work proposes to formulate the mesh network routing problem as an optimization problem. In this problem formulation, traffic demand is usually implicitly assumed as static and known a priori. Contradictorily, recent studies of wireless network traces show that the traffic demand, even being aggregated at access points, is highly dynamic and hard to estimate. Thus, in order to apply the optimization-based routing solution in practice, one must take into account the dynamic and uncertain nature of wireless traffic demand. There are two basic approaches to address the traffic uncertainty in network routing: (1) predictive routing which infers the traffic demand with maximum possibility based in its history and optimizes the routing strategy based on the predicted traffic demand and (2) oblivious routing which considers all the possible traffic demands and selects the routing strategy where the worst-case network performance could be optimized. This paper conducts a systematic comparison study of these two approaches based on the extensive simulation study over a variety of network and traffic scenarios. It identifies the key factors of the network topology and traffic profile that affect the performance of each routing strategy and provides guidelines towards the strategy selection in mesh network routing under uncertain traffic demands.