Performance Analysis of On-Demand Scheduling with and without Network Coding in Wireless Broadcast

G. G. Md. Nawaz Ali, Victor C. S. Lee, Yuxuan Meng, Peter Han Joo Chong, Jun ChenFuture 2019 · DOI

TL;DR

This paper tackles the challenge of efficiently disseminating data in wireless broadcast systems by integrating network coding with existing on-demand scheduling algorithms. By proposing a novel heuristic approach and conducting extensive simulations, the authors demonstrate that network coding significantly boosts performance across various scheduling objectives, leading to improved bandwidth utilization and faster data delivery.

What Problem Does This Paper Address?

In wireless communication, especially for applications like vehicular networks, efficiently delivering data to a large number of clients is crucial. On-demand broadcast systems allow clients to request specific data, but traditional methods are limited to sending only one data item per broadcast "tick," which is inefficient. Network coding offers a way to combine multiple data items into a single encoded packet, potentially increasing bandwidth efficiency. However, effectively integrating network coding with existing scheduling algorithms, while preserving their original goals (like meeting deadlines or minimizing response times), is a complex problem. This paper aims to bridge this gap by developing and evaluating a method to leverage network coding within various on-demand scheduling paradigms.

Methods

The core of this paper lies in its proposed heuristic coding-based approach. This method involves:

  1. CR-Graph Construction: Building a "Cache-Request-Graph" (CR-graph) that represents clients' requested and cached data items. This graph helps identify opportunities for coding.
  2. Selected Vertex Identification: Identifying a "selected vertex" within the CR-graph based on the priority assigned by the specific on-demand scheduling algorithm being used (e.g., earliest deadline for real-time, longest waiting time for non-real-time).
  3. Maximal Clique Finding: Finding a maximal clique (a group of vertices where every pair is connected) that covers the selected vertex. This clique represents a set of clients whose requests can potentially be satisfied by a single encoded packet.
  4. Encoding and Broadcasting: Creating an encoded packet using XOR operations for the data items requested by clients in the maximal clique and broadcasting it.

The authors then apply this heuristic to representative algorithms from three categories: real-time (EDF, SIN), non-real-time (FCFS, MRF, LWF, RxW), and stretch optimal (LTSF, STOBS). They implement coding versions of these algorithms (e.g., EDF_N, SIN_N) and compare their performance against their non-coding counterparts.

Datasets

Not discussed in the paper. The paper focuses on a simulated environment with parameters like the number of clients, database size, cache size, and data item sizes.

Key Insights and Ideas

  • Network Coding is a Game Changer for Broadcast: The most significant insight is that network coding isn't just a minor tweak; it fundamentally enhances the efficiency of on-demand broadcast, leading to substantial improvements across various performance metrics.
  • Preserving Scheduling Goals is Key: The heuristic approach successfully integrates network coding without sacrificing the original objectives of the scheduling algorithms. This means you get the benefits of coding and still meet deadlines or minimize response times.
  • Graph-Based Approach Unlocks Coding Potential: Using a CR-graph to model client requests and cache states is an effective way to identify optimal coding opportunities.
  • Heuristic is Practical: The proposed heuristic approach avoids the computational complexity of finding the absolute maximum clique, making it practical for real-world implementation.
  • Different Objectives Benefit Differently: While network coding generally improves performance, the degree of improvement varies depending on the scheduling objective. For instance, algorithms that already consider item popularity (like SIN) see less relative gain from coding compared to those that primarily focus on urgency (like EDF), as coding implicitly introduces a form of popularity awareness.

Key Results

The simulation results consistently show the superiority of the network coding versions of the algorithms:

  • Real-Time: Coding versions (EDF_N, SIN_N) achieved significantly lower Deadline Miss Ratios (DMRs) – up to 28% improvement for EDF_N and 19% for SIN_N under moderate workload. This was attributed to higher Average Broadcast Productivity (ABP).
  • Non-Real-Time: Coding versions achieved substantially lower Average Response Times (ARTs), with at least 40% less ART compared to their non-coding counterparts, irrespective of data access patterns. ABPs also increased significantly with coding.
  • Stretch Optimal: Coding versions consistently outperformed non-coding versions in minimizing ART. While the impact on Average Stretch (AS) was more nuanced, with coding showing a slight improvement for smaller data items but a diminishing return (or even penalty) for larger items, the ART benefits remained.

Limitations and Future Work

  • Data Item Size Trade-off: The paper notes that the benefit of network coding in stretch optimal scheduling can be a trade-off. While it can reduce response times, the increased transmission time of larger encoded packets can negatively impact stretch, especially for smaller data items.
  • Heterogeneous Environments: The authors suggest future work to investigate network coding strategies in more complex, heterogeneous environments where data items have varying sizes. The goal would be to strike a balance between encoding large and small items to maximize overall system performance.
  • Real-World Deployment: While the simulations are comprehensive, real-world deployment challenges and performance under highly dynamic network conditions are not explicitly addressed.

Summary updated

Abstract

On-demand broadcast is a scalable approach to disseminating information to a large population of clients while satisfying dynamic needs of clients, such as in vehicular networks. However, in conventional broadcast approaches, only one data item can be retrieved by clients in one broadcast tick. To further improve the efficiency of wireless bandwidth, in this work, we conduct a comprehensive study on incorporating network coding with representative on-demand scheduling algorithms while preserving their original scheduling criteria. In particular, a graph model is derived to maximize the coding benefit based on the clients’ requested and cached data items. Furthermore, we propose a heuristic coding-based approach, which is applicable for all the on-demand scheduling algorithms with low computational complexity. In addition, based on various application requirements, we classify the existing on-demand scheduling algorithms into three groups—real-time, non-real-time and stretch optimal. In view of different application-specific objectives, we implement the coding versions of representative algorithms in each group. Extensive simulation results conclusively demonstrate the superiority of coding versions of algorithms against their non-coding versions on achieving their respective scheduling objectives.
BibTeX
@inproceedings{ali2019performance,
  author = {G. G. Md. Nawaz Ali and Victor C. S. Lee and Yuxuan Meng and Peter Han Joo Chong and Jun Chen},
  title = {{Performance Analysis of On-Demand Scheduling with and without Network Coding in Wireless Broadcast}},
  booktitle = {Future},
  year = {2019},
  doi = {10.3390/fi11120248},
}
Figure