Scheduling method improves decoding speed for multiple coded message streams
Message-Level Scheduling for RLNC-Coded Multi-Source Traffic
Networking and Internet Architecture
Summary
When several streams of coded messages arrive at a destination to be processed, deciding which message to handle first can reduce delays. The authors study how to schedule these messages to minimize the weighted decoding delay, meaning more important messages get decoded faster. They show that finding the absolute best schedule is very hard, but their proposed method called MAIDS prioritizes messages efficiently based on their remaining work and importance. Simulations demonstrate MAIDS consistently lowers delays compared to other approaches and reaches near-optimal performance in many cases.
What this means in practice
- •For network schedulers: Order processing of multiple coded data streams at destinations to reduce delay for higher priority traffic.
- •For streaming platform engineers: Optimize decoding sequences in multi-source streaming systems to minimize weighted delay and improve playback smoothness.
Authors
Zhaohong Lu, Qingyu Liu, Haibo Zeng
Abstract
This paper studies weighted decoding-delay minimization for multiple RLNC-coded message streams that compete for finite processing capacity at a destination. Packet arrivals are exogenous, while the scheduler only determines the processing order of packets already available at the destination. A trace-conditioned offline scheduling formulation shows that a batch-release subclass is strongly NP-hard even with a single processing unit. Message-Aware Innovation-Deficit Scheduling (MAIDS) is then developed to prioritize each serviceable message according to its weight and remaining decoding deficit. For a single processing unit, MAIDS is shown to be exactly optimal under nonblocking progressive arrivals with equal weights and under common activation with arbitrary positive weights, while the unrestricted weighted online problem admits no universal deterministic $O(1)$ competitive ratio. Simulation results on streaming and batch benchmarks show that MAIDS consistently reduces weighted decoding delay relative to the tested baselines, remains close to the offline optimum on average, and recovers the predicted exact performance boundaries.