Performance evaluation of wireless ad hoc networks and the presence of heavy-tails & LRD.

摘要

Multi-hop wireless networks lack widespread deployment due to their performance issues. There are very few models which can aid detailed analysis of performance bottlenecks and design improvements. Our objective is to develop hybrid (analytical and numerical) models which can efficiently approximate the performance of wireless multi-hop networks. We focus on modeling the MAC and routing protocol performance, and their impact on network performance. For MAC layer modeling, we improve a fixed-point loss network model to evaluate throughput and packet loss for 802.11 MAC protocol. For routing, we model the OLSR protocol, one of the popular routing protocols. Unlike any work before, we give a combined model of a MAC and Routing Protocol which captures the cross-layer interaction. Most of the performance models assume smooth or exponential input traffic models in the usual Markovian framework. However, it is known, at least for wired networks, that traffic sources can have heavy-tails and the traffic arrival pattern bursty even at large timescales, which is characterized by self-similarity and long-range dependence (LRD). This can significantly impact network performance through higher queue-occupancy, service times, packet losses, etc. Both the presence of these phenomenon and their impact on network performance of wireless multi-hop networks has not be studied before. Hence, we study traffic LRD in three stages, which form the main contributions of this work.;Heavy-tails in traffic sources, for example file sizes on the web, have been attributed as the main causes of traffic LRD. Previous protocol studies, for both wired and wireless networks, have argued that the network protocols dynamics affect only the small-time scale properties, and that they cannot create traffic LRD by themselves. However, recent work show that ALOHA protocol can lead to heavy-tailed delays in certain situations. With that as a motivation, we investigate the role of more complex 802.11 MAC protocols in shaping the delays and traffic burstiness. We show, through simulations, that service times for 802.11 MAC, can indeed have power-law (or truncated heavy-tail) distributions. However, even with complex topologies with hidden-nodes, the maximum MAC service times are bounded at a few seconds. Hence, they are not sufficient to create traffic LRD.;Secondly, due to variable link conditions in wireless networks, the routing protocol can also cause changes in multi-hop routes even in a static topology. The link 'failure' detection mechanisms are different for wireless networks; a certain number of consecutive packet drops is usually used as indicator of link failure, even though these packet drops can be due to fading or congestion. Thus, the wireless medium can introduce spurious route changes which can potentially affect traffic burstiness at large timescales. We show, contrary to conventional wisdom, wireless multi-hop network protocols indeed create traffic burstiness at large time-scales. In particular, routing control packet losses at MAC due to congestion can lead to route oscillations in link-state routing protocols like OLSR. These route oscillations can create pseudo-traffic LRD. We modify our previous MAC and OLSR models to predict which network scenarios will lead to route oscillations. We also show, using our models, how we can appropriately tune the protocol design parameters to avoid route oscillations and traffic LRD.;Lastly, we investigate the impact of traffic burstiness on network performance. Service times of 802.11 MAC frames depends significantly on the congestion perceived in the wireless channel. Bursty traffic can also lead to increased retries or losses during periods to high load. We analyze the average achievable throughput at the MAC layer and the impact of traffic LRD. We show that traffic LRD can significantly impact network performance. However, contrary to our intuition, bursty traffic can lead to higher throughput in some scenarios. We give some models to explain and predict such behavior in simple 4 node topologies with two links. We use these models to characterize the 'capacity region' defined in terms of the MAC protocol functioning for these 2 link topologies. In particular, given bursty or smooth traffic on one link, we characterize what is the maximum achievable throughput ('capacity') on the other link as well as the sum capacity. The models show that the achievable / maximum throughput depends on the traffic burstiness at some load levels. Thus, it is important to use appropriate input traffic models for any good performance analysis.