Model-driven optimization of opportunistic routing

Eric Rozner, Mi Kyung Han, Lili Qiu, Yin ZhangSigmetrics 2011 · DOI

TL;DR

This paper introduces a novel framework for optimizing opportunistic routing in IEEE 802.11 wireless networks. By developing a more accurate interference model and a joint optimization approach for routes and rate limits, they achieve significantly better performance and predictability compared to existing methods, making opportunistic routing practical for real-world deployments.

What Problem Does This Paper Address?

Wireless mesh networks, while promising, suffer from high packet loss rates due to the inherent nature of wireless communication and interference. Opportunistic routing aims to mitigate this by allowing any node to forward a packet, effectively combining weak links. However, achieving good, predictable performance in such dynamic environments is challenging. Existing approaches struggle with accurately modeling wireless interference, especially in IEEE 802.11 networks with broadcast transmissions, and often fail to jointly optimize both routing decisions and traffic rate limits, leading to suboptimal performance or network congestion. This paper tackles the problem of achieving high, predictable end-to-end performance in IEEE 802.11 opportunistic routing by developing a more accurate model and a robust optimization framework.

Methods

The authors propose a three-pronged approach:

  1. A General Optimization Framework: This framework jointly optimizes opportunistic routes and rate limits for both unicast and multicast traffic. It uses probabilistic characterizations of communication opportunities and can incorporate various wireless interference models.
  2. An IEEE 802.11 Broadcast Interference Model: This is a key contribution. Unlike previous models that might oversimplify interference or focus on unicast, this model specifically captures the complex interactions of carrier sensing and collisions in IEEE 802.11 broadcast transmissions. It models the relationships between sending rates, loss rates, and throughput, and is designed to be incorporated into optimization frameworks with a manageable number of constraints (O(E), where E is the number of edges).
  3. An Iterative Optimization Procedure: Since the interference model leads to non-convex optimization problems, the authors developed an iterative algorithm. This algorithm linearizes the non-linear interference constraints and uses a line search to find a feasible and improved solution in each iteration, guaranteeing convergence.
  4. A Practical Protocol Implementation: They developed a protocol that implements the optimized routes and rate limits in real IEEE 802.11 networks, building upon existing opportunistic routing concepts like network coding.

Datasets

The paper does not introduce new datasets. Instead, it relies on:

  • Measurements from a given network: To estimate link loss rate, carrier sense probability, and conditional collision loss probabilities for seeding their interference model.
  • Simulations: Using the Qualnet simulator with 5x5 grid and 25-node random topologies, employing 802.11a at 6 Mbps.
  • Testbed experiments: Using a 21-node wireless mesh testbed with 802.11a and 802.11b to validate their approach in a real-world environment.

Key Insights and Ideas

  • The critical role of accurate interference modeling: The paper strongly emphasizes that existing interference models (like conflict graphs) are insufficient for optimizing opportunistic routing because they oversimplify or misrepresent broadcast interference, leading to significant overestimation of performance.
  • Joint optimization of routes and rate limits is crucial: Simply optimizing routes without considering rate limits can lead to network congestion, especially with broadcast transmissions. Their framework's ability to jointly optimize these aspects is a key differentiator.
  • Broadcast transmissions require specialized modeling: The unique characteristics of IEEE 802.11 broadcast (e.g., lack of exponential backoff) necessitate a model that goes beyond unicast interference analysis.
  • Non-convexity is a fundamental challenge: The inherent non-linearities in wireless interference require sophisticated iterative optimization techniques rather than standard convex optimization methods.
  • Practical realization is key: The authors demonstrate that their optimized solutions can be effectively implemented and yield significant performance gains in real-world IEEE 802.11 networks.

Key Results

  • High Accuracy: The difference between achieved performance and model estimation is typically within 20%.
  • Significant Performance Improvement: Their protocol outperforms state-of-the-art shortest path routing (e.g., ETX) by up to 14x in total throughput and opportunistic routing protocols like MORE by up to 11x.
  • Robustness: The approach is robust to inaccuracies in traffic demand estimation and unknown external interference, with performance degrading gracefully.
  • Model Fidelity: Their new broadcast interference model significantly reduces over-prediction errors compared to the conflict-graph model, which consistently overestimates performance.
  • Effective for Multicast: The framework also shows substantial gains for multicast traffic, leveraging broadcast effectively.

Limitations and Future Work

  • Limitations:
    • The model assumes pairwise interference, which is a common simplification but might not hold in all complex scenarios.
  • The optimization is performed centrally, though they suggest distributed computation is possible.
  • The performance gains are most pronounced in lossy environments; in very stable networks, the advantage over shortest path routing diminishes.
  • Future Work:
    • Extend robust traffic engineering techniques to optimize for a convex combination of traffic patterns, covering a space of common traffic scenarios.
  • Cope with both traffic and topology variations in wireless networks.
  • Further explore distributed optimization approaches.

Summary updated

BibTeX
@inproceedings{rozner2011model,
  author = {Eric Rozner and Mi Kyung Han and Lili Qiu and Yin Zhang},
  title = {{Model-driven optimization of opportunistic routing}},
  booktitle = {Sigmetrics},
  year = {2011},
  doi = {10.1145/1993744.1993771},
}
Figure