Effective Delay Control in Online Network Coding

I. INTRODUCTION

• Receivers may wait for many packets before decoding, making delay a central concern when applying network coding to stringent end-to-end settings.Network coding combines packets algebraically, and recovering sent data can require computationally heavy Gaussian elimination.Source: §I · p. 1
• Earlier network-coding frameworks often omit delay, while fountain codes offer low overhead and near-optimal throughput when intermediate nodes cannot code and applications tolerate delay,,,,.Source: §I · p. 1
• The paper develops an analytical framework for online network coding delay and encoding decisions that use chain length to limit delay, including sending uncoded packets for weaker receivers.It maps receiver information backlog to a high-dimensional random walk.Source: §I · p. 1
• Prior feedback-based online schemes use seen packets and coding windows to improve reliability and queue management, but the paper identifies remaining throughput-delay trade-offs under heterogeneous loss rates.The cited throughput-optimal protocols are in, [11].Source: §I · p. 1
• The paper contrasts its setting with prior delay-oriented work by considering heterogeneous erasures, larger fields, and more users, without requiring immediate decoding, [11],.It positions the algorithms for streaming applications with stringent delay requirements.Source: §I · p. 2

A. System Setup

• Each receiver has an independent packet-erasure channel with its own loss probability, and perfect, immediate feedback lets the sender base coding decisions on receiver buffer states.Packets are available in order at the sender; each channel takes one packet per time slot.Source: A. System Setup · p. 2

B. ARQ for Network Coding

• The reference ANC scheme was shown throughput-optimal for Poisson arrivals, perfect feedback, and identical channel erasure probabilities.Source: B. ARQ for Network Coding · p. 2
• ANC sends a linear combination involving the last unseen packets across receivers, ensuring that each receiver receiving it sees its last unseen packet.A packet is seen when the receiver can form it plus a combination of newer packets; being seen does not necessarily mean decoded.Source: B. ARQ for Network Coding · p. 2
• The sender may drop a packet once every receiver has seen it, keeping queues small without compromising reliability; expected queue size was shown to be O((1 −ǫ)−1).Source: B. ARQ for Network Coding · p. 2
• A two-receiver extension requests packets that became unseen after their combinations were lost, allowing later retransmission through a new coded packet [11].In the example, receiver 2 requests p6 before p5, then requests p5 after decoding p6.Source: B. ARQ for Network Coding · p. 2

III. DELAY ANALYSIS

• Decoding delay is the number of slots from the first transmission of an encoding of a packet until the receiver decodes it.It includes the time for the packet to be seen and then decoded, but ends before application delivery.Source: §III · p. 2

A. Two Receivers

• With two receivers, the analysis assumes uncoded packets or XORs of two packets and attributes decoding delay to encoding rules and channel erasure patterns.The possible per-slot erasure events occur with probabilities determined by the two channels.Source: A. Two Receivers · p. 3, Table II · p. 3
• A chain of length K consists of K independent linear combinations over L > K symbols that the receiver cannot decode.In the example, an uncoded packet can break a chain and let receiver 2 recover several packets; a subsequent loss can let another chain continue growing.Source: A. Two Receivers · p. 3
• Decoding delay depends on chain length and on whether the sender can break chains in time despite random packet erasures.One listed event is receiver 1 receiving a coded packet while receiver 2 observes an erasure.Source: A. Two Receivers · p. 3

1) First-Order Analysis:

• After a type-B erasure starts a receiver-2 chain, the analysis gives the probability that it remains unbroken for T slots under the assumed ARQ rules.The chain duration is modeled probabilistically for channels with erasure probabilities ǫ1 and ǫ2.Source: 1) First-Order Analysis · p. 3
• A type-B-started chain breaks only after a C event followed immediately by A or C; D events extend delay but do not change recovery or chain length.The derivation counts D events, CB pairs, and isolated A/B events, then substitutes event probabilities to obtain the duration expression.Source: 1) First-Order Analysis · p. 3
• The corresponding receiver-1 chain-duration distribution follows by swapping events B and C in the preceding analysis.Source: 1) First-Order Analysis · p. 3

2) Higher-Order Analysis:

• The delay of the kth chain is D = Pk i=0 Ti, a sum of independent, identically distributed waiting times between erasures and chain breaks.The interval from the kth erasure to the first chain break follows the same distribution as the chain-breaking times.Source: 2) Higher-Order Analysis · pp. 3–4

B. Multiple Receivers

• A leader has the maximum packet count and can decode coded packets immediately while retaining leader status through its next reception; dropping out first may leave its chain unbroken.A receiver that becomes a leader can decode the transmitted combinations if it remains among the leaders until receiving one more packet.Source: B. Multiple Receivers · p. 4
• Tracking packet-count differences from receiver R1 to the others represents system evolution as a random walk in an (n−1)-dimensional lattice.For three receivers, the state is (x1, x2), with each coordinate describing a difference in received packets.Source: B. Multiple Receivers · p. 4, Figure 1 · p. 4
• During R1's leader slots, n − e packets have zero delay; nonleaders may also break chains, but that becomes very unlikely as receiver count or erasure heterogeneity increases.Here n counts leader slots and e counts erasures R1 observes during those slots.Source: B. Multiple Receivers · pp. 4–5
• Packets sent while R1 is not a leader have delay bounded above by t2 − t1, the interval until it regains leader status.The bound assumes those packets are decoded only after R1 returns to the first quadrant.Source: B. Multiple Receivers · p. 5
• For n receivers, the model requires random walks in n-dimensional lattices, whose quadrant-crossing times are difficult to characterize mathematically, motivating numerical techniques.The walks have non-uniform directional probabilities and can remain at the same position.Source: B. Multiple Receivers · p. 5
• With ε1 = 0.25, ε2 = 0.2, and ε3 = 0.1, almost all chains break only after leading receivers receive all their packets, resulting in very high decoding delay.If one receiver has a perfect channel, other receivers have no opportunities to break chains.Source: B. Multiple Receivers · p. 5, Figure 2 · p. 5

• The section presents online network coding algorithms targeted at effective delay control.Source: §IV · p. 5

A. Systematic Online Network Coding

• SNC sends each packet uncoded on its first transmission and, after a leader loses a packet, sends a coded combination of receivers’ last unseen packets.The example contrasts this with ANC, which encodes packets following receiver 2’s loss but sends an uncoded packet after receiver 1’s loss.Source: A. Systematic Online Network Coding · p. 5
• SNC’s average sender queue size is Ω((1 − ǫ)^−2), since packets remain queued until all receivers decode them.This matches the expected queue-size order of traditional random linear network coding over the sender’s queue.Source: A. Systematic Online Network Coding · pp. 5–6
• SNC is throughput optimal because each received packet is innovative.Uncoded packets are new to receivers that receive them; coded packets increase the receiving receiver’s information-subspace dimension.Source: A. Systematic Online Network Coding · p. 6
• Because most packets are uncoded, SNC has much lower average delay and requires far fewer encoding and decoding operations than ANC.Its chains form over missing packets rather than over all packets sent after a loss.Source: A. Systematic Online Network Coding · p. 6
• For real-time traffic, SNC skips only a missing packet whose deadline expires and can keep repairing other missing packets; ANC loses the whole chain, reducing throughput.This distinction matters when packets delivered after their deadline are no longer useful to the application.Source: A. Systematic Online Network Coding · p. 6

B. Online Network Coding with a Delay Threshold

• SNCT follows its usual rule until an undecoded packet is within δ slots of its deadline, then sends that packet uncoded.If a receiver loses it, the sender repeats it until receipt or deadline expiration.Source: B. Online Network Coding with a Delay… · p. 6
• If multiple SNCT deadlines are in danger, the sender randomly selects a suitable undecoded packet for uncoded transmission.Source: B. Online Network Coding with a Delay… · p. 6
• ANCT follows ANC until an undecoded packet’s deadline is in danger, then transmits it uncoded; after repair or expiry, it resumes combinations, and packets cannot be discarded once seen by all senders.The passage says expected queue size for ANC increases to Ω((1 − ǫ)^−2), the same as SNC and SNCT.Source: B. Online Network Coding with a Delay… · p. 6

V. SIMULATION RESULTS

• The custom simulator implements ANC, ANCT, SNC, and SNCT for broadcast packets over channels with independent erasures across receivers.Source: §V · p. 6
• Each simulation transmits 100 original packets, continuing until every receiver can decode them all.Source: §V · p. 6
• The evaluation measures mean and worst-case decoding delay, per-receiver throughput, and average and maximum sender queue size across multiple runs.Throughput is decoded packets divided by the slots elapsed until the last packet is decoded.Source: §V · p. 6

A. Impact of the Delay Threshold

• SNC’s worst-case delay is about half ANC’s, whose worst receiver’s delay approaches the 150-slot simulation duration.With eight receivers, ANC combinations typically involve eight packets, so breaking a chain can take longer than SNC’s decoding of its initiating packet.Source: A. Impact of the Delay Threshold · p. 6, Figure 3 · p. 7
• 75% of SNC(T) packets arrive without delay, while fewer than a third of ANC(T) packets do so in most cases.Plain SNC’s delay CDF reaches 1 at delay 75; increasing the threshold delays that point.Source: A. Impact of the Delay Threshold · p. 7, Figure 3 · p. 7
• A delay threshold reduces throughput by about 30% to 40%; without a threshold, ANC and SNC reach optimum throughput of 0.75.Lower thresholds bring the receivers’ maximum and minimum throughput closer, improving fairness; SNC also has slightly better fairness than ANC.Source: A. Impact of the Delay Threshold · p. 7, Figure 3 · p. 7
• Introducing a threshold decreases sender queue size, and keeps maximum queue size manageable even for larger packet batches.SNC requires a larger queue than ANC, but the paper reports that delay benefits outweigh the queue-size increase in most realistic application scenarios.Source: A. Impact of the Delay Threshold · p. 7, Figure 3 · p. 7

B. Impact of the Size of the Receiver Set

• With more receivers, ANC’s maximum decoding delay quickly approaches 150 slots; a threshold of 10 limits delivery delay to around 20 slots for both ANC and SNC.The remaining delay reflects simultaneous repairs and losses of uncoded repair packets.Source: B. Impact of the Size of the Receiver… · p. 7, Figure 4 · p. 8
• ANC’s average delay exceeds 50 slots, while SNCT’s average delay is negligible across the receiver-set analysis.SNC’s average delay is comparable to ANCT’s with a threshold; the stated worst possible average delay is 75 slots.Source: B. Impact of the Size of the Receiver… · p. 8, Figure 4 · p. 8
• At threshold 10, throughput may fall to around half that of the corresponding no-threshold algorithm, while ANC and SNC variants otherwise have comparable throughput.Source: B. Impact of the Size of the Receiver… · p. 8, Figure 4 · p. 8

C. Impact of the Erasure Probabilities

• The comparisons include two heterogeneous and two homogeneous eight-receiver settings, with a delay threshold of 10 for ANCT and SNCT.The heterogeneous cases use distinct erasure probabilities across receivers; the homogeneous cases use 0.25 and 0.1, respectively.Source: C. Impact of the Erasure Probabilities · p. 8
• For smaller receiver sets and more transmitted packets, delay thresholds more significantly reduce maximum decoding delay, while reducing throughput by around 40%.With eight receivers, even the homogeneous case has worst-case delay near the simulation duration, so heterogeneity cannot exacerbate it.Source: C. Impact of the Erasure Probabilities · p. 8

VI. IMPERFECT OR DELAYED FEEDBACK

• The approach assumes perfect knowledge of receiver decoding status, although continuous feedback may impose too much overhead and feedback packets may be erased, corrupted, or delayed.Source: §VI · pp. 8–9
• Missing feedback creates a throughput-delay tradeoff, and the algorithms need continuous feedback from the leader but can use less frequent feedback from other receivers.The source may assume reception or loss, randomize, or temporarily omit a receiver after feedback loss; aggregated feedback vectors are also described.Source: §VI · p. 9

VII. CONCLUSIONS

• Without effective delay control, weaker receivers are unlikely to recover from erasures within reasonable time, and decoding success depends on a received-packet advantage over other receivers.The analysis describes receiver backlogs as chains of undecoded packets and maps relative behavior using a class of random walks.Source: §VII · p. 9
• Sending a large fraction of packets uncoded provides a throughput-optimal solution with striking decoding-delay gains.The encoding redesign aims to let all receivers decode at least some packets most of the time.Source: §VII · p. 9
• The approach is particularly useful for streaming when the source codec can cope with missing packets and in-order delivery is not required.Source: §VII · p. 9
• Future work includes integrating the algorithms with a video codec, prioritizing packets by importance, improving coding for deadline-threatened packets, and investigating imperfect feedback further.The paper describes uncoded transmission of a packet near its deadline as a first step toward delay-optimized coding.Source: §VII · p. 9