Augmenting predictive with oblivious routing for wireless mesh networks under traffic uncertainty

摘要

Traffic routing is central to the utility and scalability of wireless mesh networks. Many recent routing studies have examined this issue, but generally they have assumed that the demand is constant and given in advance. On the contrary, wireless traffic studies have shown that demand is highly variable and difficult to predict, even when aggregated at access points.rnThere are several approaches for handling volatile traffic. On one hand, traffic may be modeled in real-time with a dynamic routing based upon forecasted traffic demand. On the other hand, routing can be made with the focus towards maximally unbalanced demand, such that the worst-case performance is contained (known as oblivious routing). The first approach can perform competitively when traffic can be forecasted with accuracy, but may result in unbounded worst-case performance when forecasts go wrong. It is an open question how these two approaches would compare with each other in real networks and if possible at all, whether a benchmark could be defined to guide the selection of the appropriate routing strategy.rnTo answer the above open question, this paper conducts a systematic comparison study of the two approaches based on the extensive simulation study over a variety of network scenarios with real-world traffic trace. It identifies the key factors of the network topology and traffic profile that affect the performance of each routing strategy. A series of metrics are examined with varying powers of forecasting whether predictive routing or oblivious routing will perform better. Following the guidelines defined by these metrics, we present an adaptive strategy which augments the performance of the predictive routing with the worst-case bound provided by the oblivious routing through adaptive selection of routing strategies based on the degree of traffic uncertainty.