Message-Level Scheduling for RLNC-Coded Multi-Source Traffic Zhaohong Lu∗ , Qingyu Liu† ,Haibo Zeng∗ ∗ Dept. of Electrical and Computer Engineering, Virginia Tech, Blacksburg, VA 24060, USA † Shenzhen Graduate School, School of Electric and Computer Engineering, Peking University, Shenzhen 518055, China
arXiv:2609.10940v1 [cs.NI] 10 Sep 2026
Emails: {zhaohonglu,hbzeng}@vt.edu, [email protected]
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 traceconditioned offline scheduling formulation shows that a batchrelease 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. I NTRODUCTION Vehicular ad hoc networks (VANETs) support direct vehicle-to-vehicle and vehicle-to-infrastructure communication for safety, cooperative driving, traffic efficiency, and infotainment [1], [2]. Their high mobility, limited communication range, and rapidly varying wireless links lead to frequent topology changes and make stable end-to-end routes difficult to maintain [3]. Broadcast and opportunistic forwarding are therefore natural dissemination mechanisms: information can propagate through whichever relays are available, rather than relying on a persistent source–destination path. These characteristics motivate multi-source packet arrivals at a destination, because packets belonging to the same message may be forwarded through different relays and reach the receiver at different times. Random linear network coding (RLNC) is well suited to such dissemination. Instead of forwarding only native packets, a node transmits coded combinations of packets from the same message generation, and a destination can recover the message after accumulating the required number of innovative degrees of freedom (DoFs) [4], [5]. Intermediate relays may also recode received packets. Consequently, from the destination’s perspective, an upstream packet source may be either the original message generator or a relay, and multiple upstream nodes may simultaneously contribute coded packets for the same message. Different sources may also serve different messages, producing overlapping message streams at the receiver.
Our previous work studied the network-side delay of network-coding-enabled multi-source dissemination, including propagation, relay queueing, path diversity, and congestion effects [6]. That analysis asks how coded packets travel through the network and how network structure determines delivery delay. The present work addresses the complementary problem that begins after reception: once coded packets from several messages have reached the same destination, limited receiver processing capacity can itself become a bottleneck. A destination may therefore hold several unfinished messages simultaneously, even when the upstream network has already delivered useful coded information for all of them. The receiver must decide which available packets to process first in order to reduce message-level decoding delay. Accordingly, the problem is formulated at the message level, where multiple RLNC-coded messages arrive over time at a destination with finite processing capacity. In each slot, the scheduler determines how the available processing capacity is allocated among coded packets that have already arrived, with the objective of minimizing weighted decoding delay from message activation to successful decoding. The upstream transmission process is outside the scheduler’s control: each source serves one current message at a time, repeatedly transmitting coded packets of that message and switching only after completing its assigned transmissions, while different sources may contribute to the same or to different messages. The scheduler cannot select transmitters, alter future packet arrivals, or feed scheduling decisions back upstream. Under the rank-unit abstraction used in this paper, each successfully received coded packet contributes one innovative DoF until the message reaches rank Km . Thus, the scheduling state is naturally described at the message level by its weight, remaining decoding deficit, and currently available innovative work. Although VANETs provide the primary motivating example, the theoretical model is intentionally more general. Mobility, forwarding, link losses, and source activity are summarized by an exogenous coded-packet arrival trace at one receiver. The resulting scheduling problem therefore applies to general RLNC-coded multi-source traffic satisfying the same control boundary, rather than to VANETs alone. This problem differs from both network-side coded-packet scheduling and decoder-internal computation scheduling. Prior work has optimized coding and transmission decisions before
reception [7]–[12], whereas our arrival trace is exogenous. Progressive multicore RLNC decoding has also been studied by scheduling Gauss–Jordan operations within a coded generation [13]; our scheduler instead allocates processing service across multiple incomplete messages. The closest classical connection is preemptive weighted scheduling with release times. Ratio-based online policies and WSRPT have been studied for weighted completion objectives [14]–[16], while our decoding-delay objective is a weighted-flow-time objective. This distinction matters because unrestricted online weighted flow time admits no deterministic O(1) competitive ratio [17]. The main contributions of this paper are: A general scheduling model is formulated for continuous multi-source RLNC traffic with exogenous packet arrivals, finite processing capacity, and weighted message decoding delay. • A finite trace-conditioned offline benchmark is constructed, and a deterministic batch-release subclass is shown to be strongly NP-hard even with one processing unit. • Message-Aware Innovation-Deficit Scheduling (MAIDS) is developed to prioritize serviceable messages by weight divided by remaining decoding deficit. For a single processing unit and nonblocking progressive arrivals, MAIDS is exactly optimal for equal weights via SRPT equivalence and for common activation with arbitrary positive weights via Smith’s ratio rule. In contrast, the unrestricted weighted online problem has no deterministic O(1) competitive guarantee.
•
The remainder of the paper is organized as follows. Section II introduces the receiver model and formulates the optimization objective, after which Section III establishes the trace-conditioned offline benchmark and its complexity. MAIDS and its performance boundaries are developed in Section IV, with numerical evaluation presented in Section V. II. S YSTEM M ODEL AND P ROBLEM F ORMULATION A. Streaming System Consider a slotted-time system with one focal destination v receiving RLNC-coded traffic from a fixed set of upstream sources N = {1, . . . , N }. Multiple messages are delivered continuously, and a source may be either an original generator or a relay. The same message may therefore be supplied by more than one source, while different sources may simultaneously carry different messages. Packets received at the beginning of a slot are immediately available for processing in that slot. For each message, one or more upstream sources may be assigned to generate or forward its coded packets. Once source n is assigned to a message, it repeatedly transmits coded packets for that message until its assigned number of transmissions is completed. The source then becomes available for reassignment to a subsequent message. The packet stream
observed at the destination is thus the superposition of transmissions from multiple sources, whose message assignments may evolve over time. Several source-side constraints govern this process. Each source is assigned to at most one current message at a time, so transmissions of successive messages do not interleave at an individual source. Different sources, however, may concurrently contribute to the same message or to different messages. Source assignment, transmission timing, forwarding, and message rollover are all upstream processes and remain outside the scheduler’s control. Once coded packets reach the destination, the scheduler therefore treats the resulting packet-arrival sequence as exogenous; the analytical model does not require a particular stochastic transmission law, while a concrete transmission process is introduced later for the streaming simulations. This separation allows the traffic seen by the scheduler to be described directly in terms of message activations. Let Mnew (t) denote the set of messages whose first coded packet is observed at the destination in slot t. For each message m, its activation time is am = min{t : m ∈ Mnew (t)}.
(1)
Once activated, message m enters M(t), the set of active notyet-decoded messages, with generation size Km and positive weight wm , and remains there until decoding. Because new messages may be activated before earlier ones complete, multiple unresolved messages can coexist at the destination, including messages served successively by the same upstream source. B. RLNC Arrivals and Receiver State The resulting packet arrivals are represented by a messagelevel decoding state at the destination. Each message m contains Km source DoFs and requires Km innovative DoFs for decoding. To focus on scheduling rather than finite-field dependence, a rank-unit abstraction is adopted: every successfully received coded packet contributes one innovative DoF until the message reaches rank Km , after which additional packets provide no further decoding progress. Coding is confined within a single message generation. Let Am (t) denote the set of coded packets of message m that become available at the destination at the beginning of slot t, possibly aggregated from multiple upstream sources. Because the scheduler does not influence upstream transmission or forwarding, the arrival trace {Am (t)} is treated as exogenous. It may therefore reflect source activity, forwarding, mobility, lower-layer access, wireless loss, and other reception effects without requiring those mechanisms to be modeled explicitly. For an active message m, let rm (t) be the number of innovative DoFs already incorporated before slot-t processing. The corresponding remaining decoding deficit is dm (t) = [Km − rm (t)]+ .
(2)
Let Qm (t) denote the unprocessed packet buffer carried into slot t. After the new arrivals are included, the available buffer is Q+ (3) m (t) = Qm (t) ∪ Am (t). Under the rank-unit abstraction, at most the remaining deficit can be usefully processed. Hence the serviceable work of message m in slot t is bm (t) = min dm (t), |Q+ (4) m (t)| , with 0 ≤ bm (t) ≤ dm (t). C. Receiver Processing and Control Boundary In each slot, the scheduler allocates finite processing capacity among active messages. Let C denote the maximum number of coded packets that can be processed per slot, and let ym (t) ∈ Z≥0 be the number of innovative packets of message m processed in slot t. A feasible allocation must satisfy X ym (t) ≤ C, (5) m∈M(t)
and 0 ≤ ym (t) ≤ bm (t),
m ∈ M(t).
(6)
Processing ym (t) packets advances the incorporated rank by the same amount, so the message state evolves according to dm (t+1) = [dm (t)−ym (t)]+ . (7) Thus ym (t) is the scheduler’s control variable, while message generation, source activity, transmitter identity, packet arrival times, wireless reception, and the parameters Km , wm , and C remain outside its control.
III. T RACE -C ONDITIONED O FFLINE B ENCHMARK AND C OMPLEXITY The operational system contains a continuing message stream, whereas exact offline optimization necessarily considers a finite trace-conditioned instance. Accordingly, a finite set MH of messages is selected from the stream together with their realized activation times and packet-arrival traces, and the horizon H is chosen large enough for all messages in MH to be feasibly completed. The offline receiver is omniscient with respect to this finite trace, but the control boundary is unchanged: upstream message generation and packet arrivals remain exogenous. For each m ∈ MH , define the cumulative innovative rank made available from its activation through slot t as ( ) t X arr Rm (t) = min Km , |Am (τ )| , t ≥ am . (11) τ =am arr Under the rank-unit abstraction, Rm (t) is the number of innovative DoFs that have become available at the destination by slot t, capped at the decoding requirement Km , and is independent of the receiver’s later processing order. The selected horizon H is assumed sufficiently long for every evaluated message to be decodable, i.e., arr Rm (H) ≥ Km ,
rm (t+1) = rm (t)+ym (t),
D. Message Decoding Delay and Objective The state and service dynamics above determine when each active message can be decoded. Message m completes in the first slot after which its remaining decoding deficit becomes zero: dec Tm = min{t ≥ am : dm (t + 1) = 0}. (8) The corresponding decoding delay, measured from activation through the completion slot, is dec ∆m = Tm − am + 1.
(9)
For any finite set S of evaluated messages, the scheduling objective is the total weighted decoding delay X J(S) = wm ∆m . (10) m∈S
The scheduler operates continuously and requires neither a terminal batch nor knowledge of future arrivals. Throughout the analysis, coded packets are assumed to be of fixed size, receiver buffering is sufficient, and packet processing is deterministic and homogeneous. For steadystate evaluation, ρ denotes the long-run average innovativepacket workload offered to the receiver, and only the stable regime ρ/C < 1 is considered. Inter-message coding and joint transmitter–receiver scheduling are outside the scope of this work.
m ∈ MH .
(12)
A. Offline Optimization Formulation For a newly activated message, the required receiver work is Km innovative packets. Let ym (t) ∈ Z≥0 denote the number of innovative packets of message m processed in slot t, and let zm,t ∈ {0, 1} designate slot t as its completion slot. Define Ym (t) ≜
t X
ym (τ ),
Zm (t) ≜
τ =am
t X
zm,τ .
(13)
τ =am
All message-specific constraints below hold for m ∈ MH and t = am , . . . , H. The complete finite trace-conditioned problem is min y,z
s.t.
X
H X
wm (t − am + 1)zm,t m∈MH t=am arr Ym (t) ≤ Rm (t), X
ym (t) ≤ C,
t = 1, . . . , H,
(14a) (14b) (14c)
m∈MH : am ≤t
Ym (H) = Km ,
(14d)
Zm (H) = 1,
(14e)
Km Zm (t) ≤ Ym (t),
(14f)
ym (t) ∈ Z≥0 ,
(14g)
zm,t ∈ {0, 1}.
Constraint (14b) enforces destination-side information availability. Constraint (14c) limits aggregate receiver processing to C coded packets per slot. Constraint (14d) requires every considered message to receive all Km decoding DoFs. Constraint (14e) assigns one designated completion slot, and (14f)
prevents that slot from occurring before all required DoFs have been processed. Because every wm > 0, an optimal solution places zm,t = 1 at the earliest feasible completion slot. The decoding delay recovered from the completion indicator is H X ∆m = (t − am + 1)zm,t . (15) t=am
For a fixed packet trace, packet identities need not appear explicitly in the mixed-integer program: under the rank-unit abstraction, the cumulative-rank constraint (14b) is sufficient to prevent service from exceeding the innovative information that has actually reached the destination. This finite formulation is an exact benchmark for a selected stream segment. It does not convert the operational model into a one-shot batch system; MAIDS in Section IV operates directly on the dynamic active set M(t) without knowing a terminal horizon. B. Computational Complexity under Exogenous Packet Availability The main complexity result keeps the control boundary and the time-varying packet availability of the general model, while removing parallel processing and RLNC uncertainty. Consider the following restricted destination-side availability pattern. For each message m, choose an integer availability rel rel slot τm and a packet set Pm containing exactly Km inrel is determined by the novative coded packets. The value τm upstream packet-generation and delivery process; it is not a receiver decision. Let ( rel rel Pm , t = τm , Am (t) = (16) ∅, otherwise, set rm (am ) = 0, and fix the receiver processing capacity to C = 1.
(17)
As a result, all innovative packets required by a message become available together at the destination at an exogenous availability time, while different messages may become available at different times. In this restricted construction, the rel message activation time is am = τm . The source generation time and the destination-side availability time need not be the same; the latter is the quantity relevant to scheduling. Once activated, a message may be processed for several slots, interrupted while another available message is processed, and resumed later. This restricted problem is identical to the classical preemptive single-machine problem X 1|rj , pmtn| wj Cj , (18) j
which is strongly NP-hard for arbitrary job weights [14]. Theorem III.1 (Strong NP-hardness with one processing unit). The offline scheduling problem (14) is strongly NP-hard even when C = 1, all arrivals are deterministic, the Km innovative
packets required by each message arrive together according to (16), and processing is lossless and deterministic. P Proof. Take an arbitrary instance of 1|rj , pmtn| j wj Cj with integer processing times pj , release dates rj , and positive weights wj . For every job j, construct one message m with Km = pj ,
rel τm = rj + 1,
wm = wj ,
(19)
rel and let Pm contain Km innovative coded packets. Set C = 1. rel Beginning in slot τm , each processed packet of message m consumes exactly one unit of service. Because processing may switch between messages at slot boundaries, the scheduler can preempt and later resume any message exactly as the singlemachine scheduler can preempt and resume a job. The absolute decoding-completion slot corresponds to the job completion time, dec Tm ←→ Cj , (20) dec while the decoding delay is ∆m = Tm − am + 1 = Cj − rj . Therefore X X X wm ∆m = wj Cj − wj rj . (21) m
j
j
The second term is a constant fixed by the instance. Hence minimizing weighted decoding delay is equivalent to minimizing the classical weighted completion-time objective, and the two problems have the same feasibility structure. Since P 1|rj , pmtn| j wj Cj is strongly NP-hard, the restricted problem is strongly NP-hard. The general problem contains this restriction and is therefore strongly NP-hard as well. The theorem is deliberately stated with C = 1, so the primary hardness result does not rely on parallel processing. It also uses the simple batch-release trace in which all packets of a message become available together; arbitrary packetby-packet exogenous arrivals only generalize this availability constraint. Two classical boundaries are useful for orientation. With a common availability epoch and C = 1, the problem reduces to Smith’s ratio rule, while full initial availability with input-dependent C contains the fully parallel weightedcompletion problem of Zhang et al. [18], [19]. The former correspondence is strengthened to progressive nonblocking arrivals in Section IV-D; the latter is a secondary parallelcapacity boundary rather than the main hardness mechanism. C. Exact Homogeneous Full-Buffer Benchmark As an analytical reference, suppose all messages have the same requirement Km = k, all k innovative packets for every message arrive at the beginning of slot 1, and processing is deterministic. Order the weights as w(1) ≥ · · · ≥ w(M ) . Proposition III.2 (Exact weighted delay under homogeneous full buffering). Under the assumptions above, M X jk OPThom = w(j) . (22) C j=1 Proof. Completing any j messages requires processing at least jk coded packets, so the jth ordered completion time of every
schedule is at least ⌈jk/C⌉. Pairing the largest weights with the smallest attainable completion times gives (22) as a lower bound. A work-conserving schedule that processes messages in non-increasing weight order and uses residual capacity in a completion slot immediately on the next message attains every bound with equality.
B. Per-Slot MAIDS Allocation Given the current priorities and buffered innovative availability, MAIDS solves the per-slot surrogate X max πm (t)ym (t) {ym (t)}
s.t. The proposition provides an exact reference for homogeneous full-buffer instances. It is not a lower bound for arbitrary heterogeneous requirements or delayed packet arrivals. IV. O NLINE S CHEDULING FOR THE H ETEROGENEOUS P ROBLEM The offline problem requires future packet-availability information and is strongly NP-hard even with a single processing unit under deterministic destination-side packet availabilities. This motivates a tractable online heuristic for the continuous message stream. At each slot, the scheduler uses only information available locally at the receiver: the current dynamic active-message set, decoder rank states, and coded packets already stored in the receiver buffers. MAIDS does not claim global optimality for arbitrary exogenous arrival traces; instead, it uses a residual-work priority and solves the resulting per-slot allocation problem exactly.
m∈M(t)
X
ym (t) ≤ C,
(24)
m∈M(t)
0 ≤ ym (t) ≤ bm (t),
∀m,
ym (t) ∈ Z≥0 . Each innovative DoF consumes one identical receiver processing unit, and the objective in (24) is linear. Hence the per-slot problem is solved exactly by sorting the serviceable messages in non-increasing order of πm (t) and greedily assigning processing units up to bm (t). This exactness applies only to (24), not to the original finite-horizon weighted-delay problem. The allocation step requires O(|M(t)| log |M(t)|) ordering time, apart from linear-time buffer bookkeeping. After the counts {ym (t)} are chosen, the receiver processes any ym (t) packets from Q+ m (t). Under the rank-unit abstraction, each selected packet contributes one innovative DoF while dm (t) > 0. Let Pm (t) ⊆ Q+ m (t) satisfy |Pm (t)| = ym (t).
(25)
The next-slot receiver buffer is therefore Qm (t + 1) = Q+ m (t) \ Pm (t)
A. Residual-Work Priority of MAIDS At the beginning of slot t, after adding the new arrivals, the scheduler computes the buffered innovative availability bm (t) from (4). Since 0 ≤ bm (t) ≤ dm (t), bm (t) is exactly the maximum useful service that message m can receive in the current slot. It is determined entirely by packets that have already arrived, so MAIDS schedules realized innovative information rather than predicted future packet contributions. The weighted decoding-delay objective favors completing important messages early, while heterogeneous messages may require different amounts of remaining receiver work. Motivated by Smith’s ratio rule and its preemptive residual-work counterpart WSRPT, MAIDS assigns each unfinished message the residual-work density
(26)
for messages that remain unfinished; once dm (t + 1) = 0, message m and any remaining packets associated with it are removed from the active receiver state. C. Relation to WSRPT and Smith’s Rule
(23)
The single-processor batch-availability special case of Theorem III.1 gives the clearest classical interpretation of MAIDS. Set C = 1, and suppose that all Km innovative packets required by each message become available together at its destination-side availability time. Once message m is available, its remaining receiver work is exactly dm (t). MAIDS therefore selects, among currently available unfinished messages, the message with maximum wm . (27) dm (t)
A positive priority is actionable only while message m remains in the dynamic active set and innovative information is currently buffered, i.e., when m ∈ M(t) and bm (t) > 0. Therefore MAIDS recomputes (23) every slot over the currently serviceable messages; decoded messages leave the set and newly observed messages enter it online. The ratio in (23) should be interpreted as a scheduling heuristic for the general exogenous-arrival problem, not as an exact one-step minimizer of the original finite-horizon objective. Its classical scheduling interpretation becomes exact only in the special cases discussed in Section IV-C.
Under the mapping used in the NP-hardness proof, dm (t) is the remaining processing time of the corresponding job. Hence MAIDS reduces exactly to the Weighted Shortest Remaining P Processing Time (WSRPT) rule for 1|rj , pmtn| j wj Cj . Batsyna et al. study this WSRPT rule as an efficient heuristic and establish a local optimality property for its ordering [15]. This equivalence does not imply global optimality when availability times differ. With common full availability and C = 1, the same residual-ratio rule starts from wm /Km and keeps the selected message at increasing priority as its deficit decreases; it therefore recovers Smith’s non-increasing wm /Km order [18].
πm (t) =
wm , dm (t)
dm (t) > 0.
Algorithm 1: Streaming Message-Aware InnovationDeficit Scheduling (MAIDS). Input: receiver processing capacity C. State: dynamic active-message set M(t), decoder ranks rm (t), and receiver buffers Qm (t). 3 Initialize M(1) ← ∅. 4 for t = 1, 2, . . . do // Observe the exogenous message/packet stream 5 Observe newly received packet sets {Am (t)} and newly observed message identities Mnew (t). 6 for each m ∈ Mnew (t) do 7 Initialize rm (t) ← 0 and Qm (t) ← ∅. 8 Add m to the active set M(t). 9 end 10 Set Q+ m (t) ← Qm (t) ∪ Am (t) for every m ∈ M(t). // Compute current serviceable states 11 for each m ∈ M(t) do 12 Compute dm (t) ← [Km − rm (t)]+ . 13 Compute bm (t) from (4). 14 if dm (t) > 0 and bm (t) > 0 then 15 πm (t) ← wm /dm (t) 16 else 17 πm (t) ← 0 18 end 19 end // Allocate receiver processing capacity 20 Sort serviceable messages by non-increasing πm (t). 21 Greedily allocate at most C processing units, with ym (t) ≤ bm (t) for each active message. // Select packets and update message states 22 for each m ∈ M(t) do 23 Select any Pm (t) ⊆ Q+ m (t) with |Pm (t)| = ym (t). 24 Set rm (t + 1) ← rm (t) + ym (t). 25 Update Qm (t + 1) using (26). 26 if rm (t + 1) ≥ Km then dec ← t and ∆ 27 Set Tm m ← t − am + 1. 28 Remove m and its remaining buffered packets from the next-slot active state. 29 end 30 end 31 Carry all remaining unfinished messages into M(t + 1). 32 end 1 2
The formal result in Section IV-D extends this intuition to progressive nonblocking arrivals. Under full availability and C > 1, the rule is also consistent with the fully parallel residual-ratio packing interpretation [19]; when all Km = k, it attains the homogeneous benchmark in Proposition III.2. Under general packet-by-packet exogenous arrivals, these classical relations no longer characterize the global optimum. MAIDS instead recomputes the residual-work ratio only over messages with currently buffered innovative information, so a high-priority message cannot consume processing service before its coded information has actually arrived. D. Performance Boundaries of MAIDS The preceding classical correspondences identify two sources of online difficulty in the general problem: heterogeneous message priorities and progressive packet availability. The following three boundary results separate cases in which MAIDS is exactly optimal from the unrestricted weighted online regime, where no constant competitive guarantee is possible for any deterministic scheduler.
The first condition identifies progressive arrival traces that do not starve a single-unit receiver. Definition IV.1 (Nonblocking arrival trace). For C = 1, a finite trace is nonblocking if, for every message m and every slot t ≥ am , arr Rm (t) ≥ min{Km , t − am + 1}.
(28)
Thus, from activation onward, innovative information for message m arrives at least as fast as a unit-rate processor could continuously process that message. This condition allows progressive arrivals and is strictly weaker than requiring all Km packets to be available at activation. Theorem IV.2 (Equal-weight optimality). Consider a finite trace-conditioned instance with C = 1, a nonblocking arrival trace, and equal positive message weights wm = w Pfor all m. Then MAIDS minimizes the total decoding delay m ∆m . Proof. At the beginning of slot t, any unfinished message m has received at most one unit of service in each earlier slot since its activation, and hence rm (t) ≤ t−am . If t−am +1 ≤ arr (t) ≥ t − am + 1 > rm (t); if Km , condition (28) gives Rm arr t − am + 1 > Km , it gives Rm (t) = Km > rm (t) for every unfinished m. Therefore every active unfinished message has at least one useful packet available whenever it could be selected, so packet availability never restricts the single-unit scheduling decision. The resulting problem is equivalent to preemptive singlemachine scheduling with release epoch rj = am − 1, processing requirement pj = Km , and equal weights. Since πm (t) = w/dm (t), MAIDS selects the message with the smallest remaining processing requirement and therefore coincides with the Shortest Remaining Processing Time (SRPT) discipline. SRPT minimizes total flow/completion time with release dates under preemption [20]. Identifying the classical completion dec dec − am + 1 = ∆m , gives Cj −P rj = Tm epoch with Cj = Tm so the same schedule minimizes m ∆m . Corollary IV.3 (Common-activation weighted optimality). Consider C = 1 and a nonblocking arrival trace. If all messages have a common activation time am = a but may have arbitrary positive weights, then MAIDS is optimal and completes messages in non-increasing wm /Km order. Proof. By Definition IV.1, packet availability never blocks an unfinished message. At the common activation time, MAIDS orders messages by wm /Km . Once a message m is selected, each unit of service decreases dm (t) while leaving every unserved message’s deficit unchanged. Hence wm /dm (t) can only increase relative to the ratios of the other waiting messages, so MAIDS continues serving m until completion. The resulting nonpreemptive completion order is therefore nonincreasing wm /Km , which is Smith’s optimal ratio rule [18]. Full initial availability is a special case of the nonblocking condition, so this corollary extends the full-availability Smithrule interpretation in Section IV-C to progressive arrivals.
The preceding results are exact positive boundaries. The next result shows why a universal constant competitive ratio should not be expected once arbitrary weights and arbitrary online activations are allowed. Proposition IV.4 (No constant deterministic competitive ratio). For the unrestricted weighted online problem with C = 1, no deterministic scheduling policy has an O(1) competitive ratio for total weighted decoding delay, even in the special case where all Km required packets of each message are available at its activation time. Proof. Consider the classical online preemptive singlemachine weighted-flow- time problem. For each job j with release time rj , processing requirement pj , and weight wj , construct a message with am = rj + 1, Km = pj , and wm = wj , and make all Km packets available at the beginning of slot am . One unit of service then corresponds exactly to one unit of preemptive machine processing. If the message dec completes in slot Tm , identify the classical completion epoch dec with Cj = Tm . Its decoding delay is dec ∆m = Tm − am + 1 = Cj − rj ,
(29)
which is exactly the classical flow time. Thus any deterministic O(1)-competitive scheduler for this special case would imply a deterministic O(1)-competitive algorithm for online preemptive single-machine weighted flow time. Bansal and Chan proved an ω(1) lower bound on the competitive ratio of every deterministic online algorithm for that problem [17], yielding the claim. Proposition IV.4 is a boundary for the entire online problem rather than a limitation specific to MAIDS. Together with Theorem IV.2 and Corollary IV.3, it identifies a clear frontier: MAIDS is exactly optimal when either equal weights reduce its priority to SRPT under nonblocking arrivals or common activation reduces it to Smith’s ratio rule, whereas the fully heterogeneous online weighted-delay problem does not admit a universal constant competitive guarantee for any deterministic policy. V. S IMULATION R ESULTS The evaluation consists of three complementary parts. First, the general streaming experiment tests the online scheduler under exogenous packet-by-packet arrivals against two online baselines. Second, the finite batch-release experiment instantiates the NP-hard special case of Section III-B and compares MAIDS with WSRPT and the exact offline solution of (14). Third, the performance-boundary validation checks two exact regimes from Section IV-D: an equal-weight nonblocking progressive-arrival regime, where MAIDS should coincide with SRPT, and a common-full-availability regime, which is the full-buffer endpoint of the common-activation weighted boundary and should coincide with Smith/WSPT. The impossibility boundary of Proposition IV.4 is a worst-case analytical statement and is therefore not treated as a Monte Carlo validation.
A. Simulation Setup All simulations are slot-based and preserve the control boundary of Section II. The upstream process first generates an exogenous coded-packet arrival trace; the same realized trace is then replayed under all policies being compared. Hence a scheduling decision can change only the order in which already-arrived packets are processed and cannot change future packet arrivals. The rank-unit abstraction is retained, so every successfully received coded packet contributes one innovative DoF until its message reaches rank Km . This isolates scheduling from finite-field dependence and makes the simulated service unit identical to that in (5). For a completed message cohort C, the reported performance metric is the weighted mean decoding delay P m∈C wm ∆m ∆w (C) = P . (30) m∈C wm This is the normalized form of the objective in (10); it keeps results comparable across random traces containing different numbers and mixtures of messages. Table I summarizes the main parameters. For streaming, ρ/C is the long-run innovative-packet workload offered to the receiver, normalized by processing capacity, and is varied from 0.40 to 0.95 in steps of 0.05; hence all steady-state experiments satisfy ρ/C < 1. For the finite batch and common-full benchmarks, the same numerical grid is denoted by x ≡ ρ/C only as a normalized workload-control parameter, not as a steady-state offered load. New-message requests follow a Poisson process with ρ , E[K] = 42, (31) λmsg = E[K] so increasing ρ increases the number of overlapping messages without increasing the packet-generation speed of an already active message. Each source assigned to a message independently emits its next coded packet with probability ps = 0.5 in each slot. A source remains locked to its current message until its assigned packet quota is exhausted, after which it may support a later message. Thus packets of successive messages do not interleave at an individual source, while a single message may simultaneously receive packets from multiple sources. Across all streaming settings, the mean realized ρ/C differs from the target value by at most 0.0132. The selected streaming parameters also keep the nominal packet workload below the aggregate source transmission opportunity N ps : the largest target workload is ρ = 4 × 0.95 = 3.8 packets/slot, whereas N ps = 12 × 0.5 = 6 is the aggregate expected transmission rate when all sources are active. For streaming, a trial contains a 5000-slot warm-up, a 15000-slot measurement interval, and a 15000-slot guard interval. The metric in (30) is computed for messages activated during the measurement interval; the guard interval allows those messages to finish without truncating their delays. Within a fixed trial and load, MAIDS and all baselines use exactly the same exogenous arrival trace.
TABLE I S IMULATION PARAMETERS Parameter
Value
General streaming Receiver capacity C {1, 2, 4} packets/slot Normalized load ρ/C 0.40 : 0.05 : 0.95 Message weights wm {1, 2, 4, 8, 16}, uniform Upstream sources N 12 Generation size Km U {4, . . . , 80} Support size Gm {1, 2, 3} Pr(Gm = 1, 2, 3) (0.50, 0.35, 0.15) Per-source send probability ps 0.5 Warm-up / measurement / guard 5000/15000/15000 slots Monte Carlo trials 96 per (C, ρ/C) NP-hard batch release Receiver capacity C {1, 2, 4} packets/slot Workload parameter x ≡ ρ/C 0.40 : 0.05 : 0.95 Message weights wm {1, 2, 4, 8, 16}, uniform Messages per instance M 8 Generation size Km U {2, . . . , 10} Release-window fraction β 0.35 Monte Carlo trials 16 per (C, x) Exact MILP time limit 30 s per instance
(a) C = 1
Equal-weight nonblocking boundary Receiver capacity / messages C = 1, M = 10 Message weights wm = 1 for all m Generation size Km U {2, . . . , 20} Activation time am U {1, . . . , 12} Packet availability one packet/slot from am Random instances 500 Common full availability Receiver capacity / messages C = 1, M = 5 Workload parameter x ≡ ρ/C 0.40 : 0.05 : 0.95 Message weights wm {1, 2, 4, 8, 16}, uniform Reference horizon 24 slots Monte Carlo trials 40 per x value
The positive performance boundaries use finite instances. In the equal-weight case, the parameters in Table I are combined with one progressive arrival per slot from activation until completion of the message’s Km arrivals: ( 1, am ≤ t ≤ am + Km − 1, |Am (t)| = (32) 0, otherwise.
(b) C = 2
arr Thus Rm (t) = min{Km , max(0, t − am + 1)} and the nonblocking condition holds with equality. The common-full validation instead makes all required packets available at slot 1 and compares MAIDS with Smith/WSPT.
B. General Streaming Performance MAIDS is compared with two online baselines. StaticWSPT uses the fixed index wm /Km throughout the lifetime of message m, whereas Weight-only uses wm and ignores message size and remaining work. MAIDS instead recomputes wm /dm (t) every slot and therefore adapts its priority as a message approaches decoding. Fig. 1 shows the weighted mean decoding delay for C = 1, 2, and 4. In all three cases, delay increases with ρ/C as more messages overlap and compete for the finite processing budget. MAIDS consistently yields the smallest delay among the three online policies. Because all policies replay the same trace within each trial, paired 95% confidence intervals are computed for the baseline-minus-MAIDS delay differences
(c) C = 4 Fig. 1. General streaming performance under exogenous coded-packet arrivals.
over the 96 trials at each setting. The intervals are strictly positive at all 36 tested (C, ρ/C) settings for both baselines. The smallest separation occurs at C = 4 and ρ/C = 0.40: the mean Static-WSPT–MAIDS difference is 0.0853 slots with a 95% confidence interval of [0.0756, 0.0951], while the corresponding Weight-only–MAIDS difference is 0.0961 slots with a 95% confidence interval of [0.0853, 0.1069]. At light load,
the policies are relatively close because receiver contention is limited. The separation becomes more pronounced as ρ/C approaches one, where completion order has a larger effect on queueing and decoding delay. The behavior across C also illustrates the role of receiver capacity. For C = 4, the three policies remain close over a wider low-load region because multiple buffered packets can be processed in the same slot. Once the load becomes high, however, the curves separate again and MAIDS retains the lowest delay. These results indicate that the dynamic residual-work term in wm /dm (t) is most useful when several heterogeneous messages are simultaneously serviceable and the receiver must decide which nearly completed messages should receive scarce processing capacity first. (a) C = 1
C. NP-Hard Batch-Release Benchmark The NP-hard benchmark evaluates MAIDS on finite batchrelease instances derived from the construction in Section III-B. Each instance contains M = 8 messages with Km ∼ U {2, . . . , 10} and weights drawn from {1, 2, 4, 8, 16}. For a realized total workload X W = Km (33) m
and finite workload-control parameter x ≡ ρ/C, the reference horizon is defined as W . (34) Hx = Cx Here x ∈ {0.40, 0.45, . . . , 0.95} controls release-window compression for this finite instance; unlike streaming ρ/C, it is not interpreted as a steady-state offered load. All Km packets of message m become available together at a random destination-side release time rel τm ∼ U {1, . . . , ⌈βHx ⌉} ,
β = 0.35.
(b) C = 2
(35)
The same (Km , wm ) realization is reused across x values within a Monte Carlo trial, while changing x changes the release window and therefore the amount of scheduling overlap. For every instance, MAIDS, WSRPT, and the exact offline optimum obtained from the mixed-integer formulation are evaluated. For C = 1, the batch-availability model makes dm (t) exactly equal to the remaining processing time, so MAIDS is classical WSRPT as established in Section IV-C. For C > 1, the plotted WSRPT curve denotes the natural capacity-C extension that applies the same weighted-shortestremaining-work ratio and allocates up to C units per slot. Consequently, in the batch experiments it uses exactly the same per-slot ordering as MAIDS. Numerically, the maximum absolute difference between the MAIDS and WSRPT objectives over all evaluated batch instances is zero. Accordingly, the WSRPT curve is completely superimposed on the MAIDS curve in all three panels of Fig. 2. Fig. 2 compares the resulting delays with Exact OPT. For C = 1, the three curves are nearly indistinguishable, although WSRPT/MAIDS is not globally optimal when release times
(c) C = 4 Fig. 2. NP-hard batch-release benchmark.
differ. The difference remains small on average for C = 2, while a more visible separation from the offline optimum appears for C = 4. The exact benchmark exploits complete future knowledge of all message release times, whereas MAIDS remains an online local policy. To quantify differences that are difficult to see in the absolute-delay plots, define the paired-instance relative opti-
TABLE II R ELATIVE O PTIMALITY G AP OF MAIDS ON NP-H ARD BATCH I NSTANCES C
Mean gap (%)
Maximum gap (%)
MAIDS-optimal instances (%)
1 2 4
0.098 0.409 1.862
3.723 5.861 16.364
91.67 77.60 50.52
mality gap g=
JMAIDS − JOPT × 100%. JOPT
whereas the unrestricted weighted online setting admits no universal deterministic O(1) competitive guarantee. Simulation results confirm the predicted exact performance boundaries and show that MAIDS performs favorably against the tested online baselines. Across the finite NP-hard benchmark, MAIDS also remains close to the exact offline optimum on average, supporting its use as a practical scheduler for heterogeneous coded-message streams. R EFERENCES
(36)
Because smaller delay is better, g = 0 indicates an optimal MAIDS schedule and positive g is the percentage by which its weighted delay exceeds the offline optimum. Table II aggregates the gap over all 12 x values and 16 random instances per value. The mean gap is only 0.10% for C = 1 and 0.41% for C = 2. For C = 4 it increases to 1.86%, showing that MAIDS remains close to the exact benchmark on average but should not be interpreted as globally optimal. The maximum observed gaps also increase with C, reaching 16.36% for the most difficult evaluated C = 4 instance. All 576 MILP instances are solved successfully within the 30-s time limit, so every value labeled Exact OPT in this benchmark corresponds to a solved offline optimum. The last column of Table II reports the fraction of instances on which MAIDS itself attains that optimum. D. Performance Boundary Validation The two positive exact boundaries in Section IV-D are validated as implementation-level consistency checks rather than new heuristic comparisons. 1) Equal-weight nonblocking arrivals: Under (32), arrivals are progressive but nonblocking. Across 500 independent instances, MAIDS and SRPT have zero objective difference in every instance, and their complete message completion-time vectors are identical. This matches Theorem IV.2. 2) Common full availability: For the common-full endpoint of Corollary IV.3, 480 heterogeneous instances are evaluated with all required packets available at slot 1. The maximum absolute difference between MAIDS and the Smith/WSPT optimum is 0, recovering the predicted full-availability boundary. Thus the simulations validate the equal-weight progressive boundary and the full-buffer endpoint of the commonactivation boundary. The negative result in Proposition IV.4 is a worst-case impossibility theorem and does not require Monte Carlo validation. VI. C ONCLUSION This paper studies weighted decoding-delay scheduling for continuous RLNC-coded multi-source traffic with exogenous packet arrivals and finite processing capacity. The traceconditioned offline problem is strongly NP-hard in a batchrelease subclass, while MAIDS provides a tractable online rule based on message weight and remaining decoding deficit. Exact optimality holds in two structured single-unit regimes,
[1] H. Hartenstein and L. Laberteaux, “A tutorial survey on vehicular ad hoc networks,” IEEE Communications Magazine, vol. 46, no. 6, pp. 164–171, 2008. [2] G. Karagiannis, O. Altintas, E. Ekici, G. Heijenk, B. Jarupan, K. Lin, and T. Weil, “Vehicular networking: A survey and tutorial on requirements, architectures, challenges, standards and solutions,” IEEE Communications Surveys & Tutorials, vol. 13, no. 4, pp. 584–616, 2011. [3] J. Blum, A. Eskandarian, and L. Hoffman, “Challenges of intervehicle ad hoc networks,” IEEE Transactions on Intelligent Transportation Systems, vol. 5, no. 4, pp. 347–351, 2004. [4] T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong, “A random linear network coding approach to multicast,” IEEE Transactions on Information Theory, vol. 52, no. 10, pp. 4413– 4430, 2006. [5] S. Chachulski, M. Jennings, S. Katti, and D. Katabi, “Trading structure for randomness in wireless opportunistic routing,” in Proceedings of the ACM SIGCOMM 2007 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, 2007, pp. 169–180. [6] Z. Lu, Q. Liu, and H. Zeng, “Theoretical delay analysis of network coding enabled m-to-n broadcasting in ad-hoc networks,” 2026. [Online]. Available: https://arxiv.org/abs/2503.03341 [7] A. Eryilmaz, A. Ozdaglar, M. Médard, and E. Ahmed, “On the delay and throughput gains of coding in unreliable networks,” IEEE Transactions on Information Theory, vol. 54, no. 12, pp. 5511–5524, 2008. [8] S. Huang, E. Izquierdo, and P. Hao, “Distributed bandwidth-efficient packet scheduling for live streaming with network coding,” in Proceedings of the 23rd ACM International Conference on Multimedia, 2015, pp. 1035–1038. [9] A. Garcia-Saavedra, M. Karzand, and D. J. Leith, “Low delay random linear coding and scheduling over multiple interfaces,” IEEE Transactions on Mobile Computing, vol. 16, no. 11, pp. 3100–3114, 2017. [10] E. Skevakis, I. Lambadaris, and H. Halabian, “Scheduling for optimal file-transfer delay using chunked random linear network coding broadcast,” ACM Transactions on Modeling and Performance Evaluation of Computing Systems, vol. 4, no. 3, pp. 17:1–17:31, 2019. [11] S. Wang, S. Lu, and Q. Zhang, “Instantly decodable network codingassisted data dissemination for prioritized services in vehicular ad hoc networks,” International Journal of Distributed Sensor Networks, vol. 15, no. 4, p. 1550147719842137, 2019. [12] E. Tasdemir, C. Lehmann, D. Nophut, F. Gabriel, and F. H. P. Fitzek, “Vehicle platooning: Sliding window RLNC for low latency and high resilience,” in 2020 IEEE International Conference on Communications Workshops (ICC Workshops), 2020, pp. 1–6. [13] S. Wunderlich, F. H. P. Fitzek, and M. Reisslein, “Progressive multicore rlnc decoding with online dag scheduling,” IEEE Access, vol. 7, pp. 161 184–161 200, 2019. [14] A. S. Schulz and M. Skutella, “The power of α-points in preemptive single machine scheduling,” Journal of Scheduling, vol. 5, no. 2, pp. 121–133, 2002. [Online]. Available: https: //onlinelibrary.wiley.com/doi/abs/10.1002/jos.93 [15] M. Batsyn, B. Goldengorin, P. M. Pardalos, and P. Sukhov, “Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time,” Optimization Methods and Software, vol. 29, no. 5, pp. 955–963, 2014. [16] B. Xiong and C. Chung, “Completion time scheduling and the wsrpt algorithm,” in Combinatorial Optimization: Second International Symposium, ISCO 2012, Revised Selected Papers, ser. Lecture Notes in Computer Science, vol. 7422. Springer, 2012, pp. 416–426.
[17] N. Bansal and H.-L. Chan, “Weighted flow time does not admit o(1)competitive algorithms,” in Proceedings of the Twentieth Annual ACMSIAM Symposium on Discrete Algorithms, 2009, pp. 1238–1244. [18] W. E. Smith, “Various optimizers for single-stage production,” Naval Research Logistics Quarterly, vol. 3, no. 1–2, pp. 59–66, 1956. [19] Q. Zhang, W. Wu, and M. Li, “Minimizing the total weighted completion time of fully parallel jobs with integer parallel units,” Theoretical Computer Science, vol. 507, pp. 34–40, 2013. [20] L. Schrage, “A proof of the optimality of the shortest remaining processing time discipline,” Operations Research, vol. 16, no. 3, pp. 687–690, 1968.