Blocking avoidance in wireless Networks

Shanyu Zhou, Hulya Seferoglu, Erdem Koyuncu

TL;DR

This paper tackles the challenge of optimizing throughput in wireless networks that use simple First-In, First-Out (FIFO) queues, which are common in low-cost devices but suffer from head-of-line (HOL) blocking. The authors introduce novel algorithms, dFC and qFC, that effectively characterize and exploit the stability region of these systems, leading to significant throughput improvements over existing methods.

What Problem Does This Paper Address?

Modern wireless networks are experiencing a surge in demand for bandwidth, driven by rich media applications. This puts a strain on network resources, especially on low-cost devices that often employ First-In, First-Out (FIFO) queueing. Unlike more sophisticated per-flow queueing mechanisms required by optimal network control schemes like backpressure routing and scheduling, FIFO queues can lead to "head-of-line" (HOL) blocking. This occurs when a packet at the front of the queue is destined for a receiver that is currently unavailable, preventing subsequent packets (even those for available receivers) from being transmitted, thus wasting valuable wireless resources. While the problem of HOL blocking is known, characterizing the achievable throughput and developing optimal resource allocation strategies for wireless networks with shared FIFO queues has remained an open challenge.

Methods

The paper proposes a two-pronged approach to address the FIFO queueing problem:

  1. Stability Region Characterization: The authors first characterize the stability region of a general wireless network scenario involving multiple shared FIFO queues and an arbitrary number of flows. They identify that this stability region is generally non-convex. To overcome this, they develop a convex inner-bound on the stability region, which is shown to be tight in certain cases. This convex inner bound is crucial for enabling efficient resource allocation.
  2. Resource Allocation Algorithms:
    • Deterministic FIFO-Control (dFC): Based on the convex inner bound, dFC is developed as a deterministic resource allocation scheme. It aims to optimize a concave utility function subject to constraints derived from the inner bound.
  3. Queue-Based FIFO-Control (qFC): Recognizing that dFC is a centralized solution and may be difficult to implement in dynamic wireless environments, the authors propose qFC. This is a stochastic, queue-based algorithm that combines flow control and scheduling. The flow controller adjusts arrival rates based on queue backlogs and utility, while the scheduler determines which queue to serve based on queue states and channel conditions. qFC is designed to achieve optimal operating points within the convex inner bound.

Datasets

Not discussed in the paper. The evaluation is based on simulations with synthetic traffic and channel models.

Key Insights and Ideas

  • FIFO's Achilles' Heel: The paper clearly articulates how the simplicity of FIFO queues, while attractive for low-cost devices, introduces significant performance limitations due to HOL blocking, especially in shared wireless environments.
  • Non-Convexity is the Enemy: The inherent non-convexity of the FIFO queue stability region is identified as a major hurdle for traditional optimization techniques.
  • Convex Inner Bound as a Bridge: The development of a convex inner bound on the stability region is a key contribution, providing a tractable optimization space for designing resource allocation algorithms.
  • Fairness and Channel Quality Trade-off: The proposed algorithms (dFC and qFC) explicitly consider channel quality and aim for fairness, penalizing flows with poor channels more to improve overall system throughput. This is a significant departure from simpler max-weight schemes.
  • Practicality Matters: The transition from the centralized dFC to the decentralized qFC highlights the authors' consideration for real-world implementation challenges in dynamic wireless networks.

Key Results

  • Stability Region Characterization: The paper provides a mathematical characterization of the stability region for arbitrary numbers of FIFO queues and flows.
  • Algorithm Performance: Simulation results demonstrate that both dFC and qFC significantly outperform the well-known queue-based flow control and max-weight scheduling schemes.
  • Throughput Improvement: For a single FIFO queue shared by multiple flows, qFC showed up to a 100% improvement in throughput compared to max-weight when the number of flows increased to 10.
  • Fairness: The algorithms were shown to provide fairness by not penalizing flows with good channels when competing flows experience poor channel conditions.
  • Adaptability: The algorithms effectively adapt to varying channel conditions, leading to near-optimal performance even in challenging scenarios.

Limitations and Future Work

  • Assumptions: The analysis relies on several assumptions, including i.i.d. channel states over time slots and a specific form of utility function (though the framework is generalizable). The paper also assumes a single wireless medium shared by all queues.
  • Centralized vs. Decentralized: While qFC offers a more practical decentralized approach, dFC is centralized. The paper focuses on the theoretical performance of both.
  • Future Work: The authors suggest exploring more complex channel models and network topologies. Further investigation into the trade-offs between fairness and throughput for different utility functions and the exponent $\beta$ in their algorithms could also be valuable. The practical implementation and performance of these algorithms in real-world heterogeneous wireless environments would be a natural next step.

Summary updated

Abstract

We investigate the performance of First-In, First-Out (FIFO) queues over wireless networks. We characterize the stability region of a general scenario where an arbitrary number of FIFO queues, which are served by a wireless medium, are shared by an arbitrary number of flows. In general, the stability region of this system is non-convex. Thus, we develop a convex inner-bound on the stability region, which is provably tight in certain cases. The convexity of the inner bound allows us to develop a resource allocation scheme; dFC. Based on the structure of dFC, we develop a stochastic flow control and scheduling algorithm; qFC. We show that qFC achieves optimal operating point in the convex inner bound. Simulation results show that our algorithms significantly improve the throughput of wireless networks with FIFO queues, as compared to the well-known queue-based flow control and max-weight scheduling.
BibTeX
@inproceedings{zhou2016blocking,
  author = {Shanyu Zhou and Hulya Seferoglu and Erdem Koyuncu},
  title = {{Blocking avoidance in wireless Networks}},
  booktitle = {ITA},
  year = {2016},
  url = {https://openreview.net/forum?id=PdG77rPJ7L},
}
Figure