Source-linked AI summary
Message-Level Scheduling for RLNC-Coded Multi-Source Traffic
Zhaohong Lu, Qingyu Liu, Haibo Zeng
TL;DR
Weighted decoding-delay scheduling asks how to allocate finite receiver processing capacity among multiple RLNC-coded messages whose packet arrivals are exogenous. The paper formulates a trace-conditioned benchmark and develops MAIDS, which is close to the offline optimum on average in simulations and has exact optimality in specified single-unit regimes, while unrestricted weighted online scheduling lacks a deterministic O(1) competitive guarantee.
Problem
Multiple RLNC-coded messages compete for finite receiver processing capacity, and the scheduler must reduce weighted decoding delay without controlling packet arrivals.
Source: §I · pp. 1–2Method
MAIDS prioritizes serviceable messages by weight divided by remaining decoding deficit, alongside a trace-conditioned offline benchmark.
Source: §I · p. 2Results
Simulations show MAIDS performs favorably against tested online baselines, stays close to the exact offline optimum on average, and confirms predicted exact boundaries.
Source: §VI · p. 10, 2) Common full availability · p. 10Takeaways & Limitations
The results support MAIDS as a practical scheduler for heterogeneous coded-message streams within the evaluated settings.
Source: §VI · p. 10
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper shifts attention from network-side delivery to receiver-side scheduling, where finite processing capacity determines when already-arrived RLNC packets complete messages. It formulates this control boundary and develops MAIDS alongside exact complexity and performance results.
I. INTRODUCTION
- VANET mobility and changing wireless links make persistent routes difficult, motivating dissemination through available relays and multi-source arrivals.RLNC lets destinations recover messages after accumulating innovative degrees of freedom from potentially multiple upstream nodes.Source: §I · p. 1
- The receiver scheduler allocates finite capacity only among packets already available; upstream transmissions and future arrivals remain outside its control.The objective is weighted decoding delay from message activation to successful decoding.Source: §I · pp. 1–2
- The trace-conditioned offline benchmark is strongly NP-hard even for deterministic batch releases with one processing unit.The reduction connects the restricted problem to preemptive single-machine weighted completion scheduling.Source: §I · p. 2
- MAIDS prioritizes serviceable messages by weight divided by remaining decoding deficit, with exact single-unit optimality in two structured arrival regimes.The regimes are nonblocking progressive arrivals with equal weights and common activation with arbitrary positive weights; unrestricted weighted online scheduling has no deterministic O(1) competitive guarantee.Source: §I · p. 2
A. Streaming System
- The streaming system allows multiple unresolved messages to coexist as source assignments and transmissions evolve over time.A source serves one current message at a time, while different sources may contribute to the same or different messages.Source: A. Streaming System · p. 2
B. RLNC Arrivals and Receiver State
The receiver state tracks innovative information available and processed for each active message, while the scheduler controls only allocation of finite processing capacity. The objective is weighted delay until decoding, under explicit modeling and steady-state assumptions.
B. RLNC Arrivals and Receiver State
- The rank-unit abstraction treats each successfully received coded packet as one innovative DoF until the message reaches its decoding requirement.Arrivals are exogenous and may aggregate packets from multiple upstream sources; serviceable work cannot exceed the remaining decoding deficit.Source: B. RLNC Arrivals and Receiver State · pp. 2–3
C. Receiver Processing and Control Boundary
- The scheduler chooses how many innovative packets of each active message to process per slot, subject to the receiver’s finite capacity.Processing advances incorporated rank and reduces decoding deficit; message generation, source activity, arrivals, and system parameters are outside scheduler control.Source: C. Receiver Processing and Control… · p. 3
D. Message Decoding Delay and Objective
- The objective sums message weights times decoding delays measured from activation through completion, without requiring a terminal batch or future-arrival knowledge.Steady-state evaluation considers only workload regimes with ρ/C < 1; inter-message coding and joint transmitter–receiver scheduling are out of scope.Source: D. Message Decoding Delay and Objective · p. 3
III. TRACE-CONDITIONED OFFLINE BENCHMARK AND COMPLEXITY
The offline benchmark optimizes a finite selected trace with realized activations and arrivals, while preserving the rule that upstream traffic is exogenous. Its formulation exactly evaluates that trace and does not make the operational online scheduler require a horizon.
III. TRACE-CONDITIONED OFFLINE BENCHMARK AND COMPLEXITY
- The benchmark selects a finite message set and sufficiently long horizon from the stream, using realized activation times and packet-arrival traces.The offline receiver knows this finite trace, but upstream generation and arrivals remain exogenous.Source: §III · p. 3
A. Offline Optimization Formulation
- The formulation assigns per-slot processing and completion indicators while enforcing packet availability, receiver capacity, full decoding work, and feasible completion.Under the rank-unit abstraction, cumulative-rank constraints suffice to prevent processing more innovative information than has arrived.Source: A. Offline Optimization Formulation · pp. 3–4
- The finite formulation is an exact benchmark for a selected stream segment, whereas MAIDS operates on the dynamic active set without knowing a terminal horizon.Positive message weights make the earliest feasible completion slot optimal for the completion indicator.Source: A. Offline Optimization Formulation · p. 4
B. Computational Complexity under Exogenous Packet Availability
A batch-release restriction makes the trace-conditioned offline scheduling problem strongly NP-hard even with one processing unit. The proof maps it to preemptive weighted completion scheduling, showing that neither parallel processing nor packet-by-packet arrivals are needed for the hardness result.
B. Computational Complexity under Exogenous Packet Availability
- Strong NP-hardness holds with one processing unit, deterministic arrivals, and all required innovative packets for each message released together.The batch-release construction retains exogenous availability and permits messages to be interrupted and resumed.Source: B. Computational Complexity under… · p. 4
- The restricted problem maps to preemptive single-machine weighted completion scheduling, so minimizing weighted decoding delay is equivalent to minimizing weighted completion time up to an instance-fixed term.A message’s required packet processing corresponds to job processing, and its destination availability corresponds to the job release date.Source: B. Computational Complexity under… · p. 4
- The general problem inherits the restricted problem’s strong NP-hardness, while common availability with one unit has a Smith-ratio boundary.The paper identifies full initial availability with input-dependent capacity as a separate parallel-capacity boundary.Source: B. Computational Complexity under… · p. 4
C. Exact Homogeneous Full-Buffer Benchmark
The homogeneous full-buffer proposition gives an exact reference schedule, while the heterogeneous online section introduces MAIDS as a tractable heuristic whose general priority is not an exact finite-horizon optimizer.
C. Exact Homogeneous Full-Buffer Benchmark
- For homogeneous full-buffer instances, a non-increasing-weight schedule attains the lower bounds on ordered completion times by using residual capacity immediately after each completion.The reference assumes equal message requirements, all required packets available at slot 1, and deterministic processing; it does not bound heterogeneous requirements or delayed arrivals.Source: C. Exact Homogeneous Full-Buffer… · pp. 4–5
IV. ONLINE SCHEDULING FOR THE HETEROGENEOUS PROBLEM
- For the heterogeneous online problem, MAIDS uses receiver-local state and exactly solves a per-slot allocation surrogate rather than claiming global optimality over arbitrary traces.Its inputs include the active-message set, decoder ranks, and packets already buffered at the receiver.Source: §IV · p. 5
A. Residual-Work Priority of MAIDS
- MAIDS prioritizes unfinished messages using a residual-work ratio, recomputed each slot only for messages with innovative information buffered for service.The priority is a heuristic for general exogenous arrivals, not an exact one-step minimizer of the finite-horizon objective.Source: A. Residual-Work Priority of MAIDS · p. 5
B. Per-Slot MAIDS Allocation
MAIDS allocates each slot’s finite capacity among currently serviceable messages by priority, and its residual-ratio rule connects to classical scheduling disciplines only in specified cases.
B. Per-Slot MAIDS Allocation
- The per-slot allocation is solved exactly by sorting serviceable messages by priority and greedily assigning capacity, capped by each message’s buffered innovative availability.This exactness applies to the per-slot surrogate, not the original finite-horizon weighted-delay problem.Source: B. Per-Slot MAIDS Allocation · p. 5
- The allocation step requires O(|M(t)| log |M(t)|) ordering time, apart from linear-time buffer bookkeeping.The scheduler processes selected packets as innovative while a message remains unfinished, then removes decoded messages and their remaining packets from the active state.Source: B. Per-Slot MAIDS Allocation · p. 5
C. Relation to WSRPT and Smith’s Rule
- With a single processor and batch availability, MAIDS reduces to WSRPT; with common full availability, it recovers Smith’s non-increasing wm/Km order.These classical correspondences do not establish global optimality when availability times differ; for packet-by-packet arrivals, MAIDS considers only currently buffered innovative information.Source: C. Relation to WSRPT and Smith’s Rule · pp. 5–6
- With full availability and C > 1, MAIDS matches the fully parallel residual-ratio packing interpretation; equal message requirements also attain the homogeneous benchmark.Source: C. Relation to WSRPT and Smith’s Rule · p. 6
D. Performance Boundaries of MAIDS
The boundary results identify two single-processor settings where MAIDS is exactly optimal and contrast them with the unrestricted weighted online problem, which has no deterministic constant competitive guarantee.
D. Performance Boundaries of MAIDS
- With equal positive weights and a nonblocking progressive-arrival trace at C = 1, MAIDS is optimal because packet availability does not restrict service and its priority coincides with SRPT.Nonblocking arrivals need not make all required packets available at activation; the condition ensures useful information arrives at least as fast as a unit-rate processor could process it.Source: D. Performance Boundaries of MAIDS · p. 6
- With common activation and arbitrary positive weights at C = 1, MAIDS is optimal and completes messages in non-increasing wm/Km order.The proof links this order to Smith’s optimal ratio rule.Source: D. Performance Boundaries of MAIDS · p. 6
- For unrestricted weighted online scheduling at C = 1, no deterministic policy has an O(1) competitive ratio, even when all required packets are available at activation.The reduction identifies decoding delay with classical flow time, invoking the deterministic online weighted-flow-time lower bound.Source: D. Performance Boundaries of MAIDS · p. 7
V. SIMULATION RESULTS
The evaluation plan covers streaming traffic, finite batch releases, and two exact-performance regimes; the supplied passage describes the comparisons but gives no simulation outcomes.
V. SIMULATION RESULTS
- The streaming experiment tests MAIDS under exogenous packet-by-packet arrivals against two online baselines.Source: §V · p. 7
- The finite batch-release experiment compares MAIDS with WSRPT and the exact offline solution of (14) on the NP-hard special case.Source: §V · p. 7
- Boundary validation checks whether MAIDS coincides with SRPT for equal-weight nonblocking progressive arrivals and with Smith/WSPT for common full availability.The impossibility boundary is treated analytically rather than as a Monte Carlo validation.Source: §V · p. 7
A. Simulation Setup
The simulations replay exogenous packet-arrival traces across policies, so scheduling changes only the processing order of packets already received. The setup measures weighted mean decoding delay across streaming loads and finite boundary-validation instances.
A. Simulation Setup
- All policies replay the same exogenous trace, and each successfully received packet contributes one innovative degree of freedom until its message reaches rank K_m.This keeps simulated service aligned with the model while isolating scheduling from finite-field dependence.Source: A. Simulation Setup · p. 7
- The reported cohort metric is weighted mean decoding delay, normalized from the objective to compare random traces with different message counts and mixtures.Table I summarizes the simulation parameters.Source: A. Simulation Setup · p. 7, Table I · p. 8
- Streaming workload ρ/C ranges from 0.40 to 0.95 in 0.05 steps, keeping every steady-state streaming experiment below capacity.For finite batch and common-full benchmarks, x ≡ ρ/C is a workload-control parameter, not a steady-state offered load.Source: A. Simulation Setup · p. 7
- Streaming trials use a 5,000-slot warm-up, 15,000-slot measurement interval, and 15,000-slot guard interval so measured messages can finish without truncated delays.The metric is computed for messages activated during the measurement interval.Source: A. Simulation Setup · p. 7
- Boundary-validation instances use progressive arrivals for the equal-weight case and make all required packets available at slot 1 for common-full validation.The equal-weight setup has one progressive arrival per slot until each message's K_m arrivals.Source: A. Simulation Setup · p. 8
B. General Streaming Performance
In streaming experiments, MAIDS has the lowest weighted mean decoding delay among the tested online policies, with separation more pronounced at higher load. On finite batch-release instances, it matches WSRPT and remains close to the exact offline optimum on average, though gaps grow in some higher-capacity cases.
B. General Streaming Performance
- Across C = 1, 2, and 4, MAIDS has the lowest delay among the three online policies; at C = 4 and ρ/C = 0.40, its smallest baseline gaps are 0.0853 slots versus Static-WSPT and 0.0961 slots versus Weight-only.Both reported 95% confidence intervals are strictly positive; separation becomes more pronounced as ρ/C approaches one.Source: B. General Streaming Performance · pp. 8–9, Figure 1 · p. 8
- For C = 4, the policies stay close over a wider low-load region, but separate at high load, where MAIDS retains the lowest delay.The dynamic residual-work term is most useful when several heterogeneous messages are serviceable and processing capacity is scarce.Source: B. General Streaming Performance · p. 9
C. NP-Hard Batch-Release Benchmark
- Batch instances contain M = 8 messages, and x controls release-window compression; the same message sizes and weights are reused across x values within a trial.The experiment compares MAIDS, WSRPT, and the exact offline optimum.Source: C. NP-Hard Batch-Release Benchmark · p. 9
- MAIDS and WSRPT have identical objectives across the evaluated batch instances because they use the same per-slot ordering in this setting.Their curves are superimposed in all three Fig. 2 panels.Source: C. NP-Hard Batch-Release Benchmark · p. 9, Figure 2 · p. 9
- MAIDS/WSRPT and the offline optimum are nearly indistinguishable for C = 1, remain close on average for C = 2, and separate more visibly for C = 4.The exact benchmark uses future release-time information, whereas MAIDS is an online local policy.Source: C. NP-Hard Batch-Release Benchmark · p. 9, Figure 2 · p. 9
- Mean optimality gaps are 0.10% for C = 1, 0.41% for C = 2, and 1.86% for C = 4; the maximum reaches 16.36% in the most difficult evaluated C = 4 instance.All 576 offline MILP instances were solved successfully within the 30-second limit.Source: C. NP-Hard Batch-Release Benchmark · p. 10, Table II · p. 10
D. Performance Boundary Validation
The simulations recover MAIDS's exact performance in the equal-weight progressive-arrival and common-full-availability regimes. The paper also distinguishes these boundaries from the unrestricted weighted online setting, where no universal deterministic O(1) competitive guarantee exists.
1) Equal-weight nonblocking arrivals:
- Across 500 equal-weight nonblocking progressive-arrival instances, MAIDS and SRPT have zero objective difference and identical message completion-time vectors.This matches Theorem IV.2.Source: 1) Equal-weight nonblocking arrivals · p. 10
2) Common full availability:
- Across 480 heterogeneous common-full instances with all required packets available at slot 1, MAIDS matches the Smith/WSPT optimum exactly.The maximum absolute objective difference is 0.Source: 2) Common full availability · p. 10
VI. CONCLUSION
- The unrestricted weighted online setting admits no universal deterministic O(1) competitive guarantee, unlike the two structured single-unit regimes with exact optimality.The conclusion identifies equal-weight nonblocking progressive arrivals and common activation with arbitrary positive weights as the exact regimes.Source: §VI · p. 10
- Simulations confirm the predicted boundaries; MAIDS also performs favorably against tested online baselines and remains close to the exact offline optimum on average in the finite NP-hard benchmark.The paper presents these results as support for MAIDS as a practical scheduler for heterogeneous coded-message streams.Source: §VI · p. 10