PaperlayerView exact revision on arXiv

Source-linked AI summary

ARQ for Network Coding

Jay Kumar Sundararajan, Devavrat Shah, Muriel Médard

arXiv:0802.1754v1cs.ITcs.NI

TL;DR

The paper tackles decoding delay and physical queue growth in coded communication networks. It proposes an online coding and queue-update algorithm using degrees-of-freedom acknowledgments, and reports lower queue size for the new algorithm than for the baseline drop-when-decoded approach.

  • Problem

    Block-based coding schemes can create decoding delay, while retaining packets until all receivers decode them can make the physical queue exceed the degrees-of-freedom backlog.

  • Method

    The paper proposes an online algorithm that acknowledges degrees of freedom and drops packets when all receivers have seen them.

  • Results

    The new algorithm has significantly lower queue size than Algorithm 1 and allows the physical queue size to track the virtual queue size.

  • Takeaways & Limitations

    The scheme is presented as a natural extension of ARQ for coded networks and as a bridge between virtual and physical queues.

Abstract

from arXiv · show

A new coding and queue management algorithm is proposed for communication networks that employ linear network coding. The algorithm has the feature that the encoding process is truly online, as opposed to a block-by-block approach. The setup assumes a packet erasure broadcast channel with stochastic arrivals and full feedback, but the proposed scheme is potentially applicable to more general lossy networks with link-by-link feedback. The algorithm guarantees that the physical queue size at the sender tracks the backlog in degrees of freedom (also called the virtual queue size). The new notion of a node "seeing" a packet is introduced. In terms of this idea, our algorithm may be viewed as a natural extension of ARQ schemes to coded networks. Our approach, known as the drop-when-seen algorithm, is compared with a baseline queuing approach called drop-when-decoded. It is shown that the expected queue size for our approach is $O(\frac1{1-ρ})$ as opposed to $Ω(\frac1{(1-ρ)^2})$ for the baseline approach, where $ρ$ is the load factor.

I. INTRODUCTION

The paper addresses decoding delay and queue-management problems in coded networks by combining network coding with ARQ through ACKs on degrees of freedom. Its online drop-when-seen approach aims to align the sender’s physical queue with the virtual degrees-of-freedom backlog while supporting timely packet recovery.

  • Motivation: Block-based fountain codes and random linear network coding can impose high delay for continuous real-time streams.High throughput may require waiting for a large block, whereas streaming applications need earlier packet recovery.
  • Motivation: Playback delay depends on which packets are recovered and their recovery order, not only on the number of recovered packets.The paper distinguishes packet delay from block delay because older packets recovered earlier reduce streaming delay.
  • Related approaches: Link-by-link ARQ is optimal for tandem networks but cannot achieve multicast capacity in general networks and is inefficient on broadcast links.Retransmitting a packet to receivers that missed it wastes transmissions for receivers that already have it.
  • Contribution: The proposed scheme combines network coding and ARQ by acknowledging degrees of freedom rather than original packets.A degree of freedom is a new dimension in the appropriate vector space, allowing feedback to represent coded information progress.
  • Queue management: When receivers have received coded combinations but decoded no original packet, the degrees-of-freedom backlog can be small even though the sender cannot drop packets under drop-when-decoded.The paper calls this backlog the virtual queue and seeks to make the physical queue track it.
  • Contribution: The drop-when-seen algorithm drops a packet once all receivers have seen it, enabling the physical queue size to track the virtual backlog.The approach uses ACKs on degrees of freedom and provides an online alternative to retaining packets until they are decoded.

A. Our contribution and its implications

The paper proposes an online coding and queue-update algorithm based on acknowledgments for degrees of freedom and the notion of receivers seeing packets. The drop-when-seen rule supports coded broadcast transmission while keeping the sender’s physical queue aligned with the degrees-of-freedom backlog.

  • The proposed algorithm uses ACKs on degrees of freedom to guarantee that the physical queue tracks the degrees-of-freedom backlog.
  • A node sees packet p when it can compute p plus a linear combination involving only packets that arrived later.Decoding implies seeing by choosing the later-packet combination as zero.
  • The drop-when-seen algorithm drops a packet once all receivers have seen it, rather than waiting for decoding.
  • The coding scheme targets broadcast constraints by making a successfully received coded packet cause each receiver to see its next unseen packet.The innovation guarantee then connects seeing a new packet with receiving a new degree of freedom.
  • The scheme is truly online, uses a stable set of unseen packets, and achieves 100% throughput under its guarantee property.The presented example uses a packet erasure broadcast channel and two receivers, with an extension to more receivers described later.

1) Example:

In the two-receiver example, the sender transmits either the common oldest unseen packet or the XOR of the receivers’ different oldest unseen packets. This makes both receivers advance their unseen-packet frontier and shortens the queue relative to drop-when-decoded.

  • For two receivers, the sender selects each receiver’s oldest unseen packet and sends that packet if both selections match, otherwise sending their XOR.
  • The transmission rule causes both receivers to see their oldest unseen packet.
  • In slot 2, A decodes p2 from p1 ⊕ p2, while B sees p1 without decoding it.
  • Once both receivers have seen p1, the sender drops it even though B has not yet decoded it.B can later obtain p1 after decoding p2.

2) Implications of our new scheme: •

The scheme keeps coding online and connects physical queue size to virtual degrees-of-freedom queues, while limiting each coded packet to n source packets. Its stated setting is a single erasure broadcast channel, with broader extensions left prospective.

  • The information deficit at each receiver is confined to a streaming window of packets that advances over time.
  • All receivers see packets in order, and the encoding scheme remains truly online with a stable set of unseen packets.
  • The physical queue is upper-bounded by the sum of the degrees-of-freedom backlogs between the sender and receivers.This bridges virtual and physical queue sizes and supports extending virtual-queue stability results to physical queues.
  • At most n packets participate in a coded packet, reducing decoding complexity and coding-coefficient storage overhead.
  • The proposed setting assumes a single packet erasure broadcast channel, while extension to tandem broadcast links and more general lossy networks is prospective.
  • A receiver that is a leader in received degrees of freedom can decode all packets up to that point, although some seen packets may be decoded earlier.

feedback.

The setup places arrivals, service, departure, transmission, and feedback within slotted time. The comparison examines expected queue size for drop-when-decoded and drop-when-seen as ρ approaches one from below.

  • Figure 1 specifies the relative timing of arrival, service, and departure events within a slot.
  • Transmission reaches receivers before feedback, and feedback from all receivers reaches the sender before the same slot ends.Thus, feedback includes the current slot’s reception.
  • The load factor is defined as ρ := λ/µ, and expected queue sizes are compared asymptotically as ρ →1−.

III. ALGORITHM 1 – DROP WHEN DECODED

Algorithm 1 uses an online linear-combination scheme with virtual queues representing degrees-of-freedom backlogs, and drops packets only after every receiver decodes them. Its physical queue has a heavier steady-state scaling than the proposed drop-when-seen approach.

  • The coding scheme is an online version of with no preset generation size.
  • Decoding occurs when the difference between received equations and unknown packets, represented by the virtual queue size, reaches zero.
  • Packets are dropped only after every receiver has decoded them.
  • For ρ < 1, the virtual-queue Markov chain is positive recurrent with geometric steady-state distribution π_k = (1 − α)α^k.
  • The physical queue analysis uses the maximum time until each virtual queue next empties, with Little’s law relating this delay to expected queue size.
  • Theorem 1 establishes a lower bound on the steady-state expected physical queue size for Algorithm 1.
  • The analysis notes that packets may sometimes be found before a virtual queue empties, but treats this as a higher-order effect.

IV. ALGORITHM 2 – DROP WHEN SEEN

Algorithm 2 tracks packets that receivers have seen through RREF representations of their knowledge spaces, then transmits combinations targeted at each receiver’s oldest unseen packet. Packets seen by all receivers can be removed incrementally.

  • The algorithm represents each receiver’s knowledge space using a unique reduced row echelon form basis.
  • A packet with index k is seen exactly when column k in the knowledge-space RREF basis is a pivot column.
  • A receiver seeing packet p_k knows one combination p_k + q, where q contains only unseen packets with larger indices.
  • The number of seen packets equals the dimension of the receiver’s knowledge space, and the associated combination is called its witness.
  • The algorithm tracks seen rather than decoded packets and uses perfect erasure feedback to retain only enough data for the innovation guarantee.
  • The coding module selects a linear combination that makes each receiving node see its oldest unseen packet.
  • Theorem 3 guarantees the required coefficient choice when the field size is at least n.
  • Packets are dropped once all receivers have seen them, while knowledge-space tracking is restricted to dimensions still present in the queue.

A. The formal description of the algorithm

The formal algorithm maintains receiver knowledge bases over the current queue, appends arrivals, and transmits a coded combination whenever the queue is nonempty.

  • A. The formal description of the algorithm: The algorithm works with the RREF bases of receivers’ knowledge spaces.
  • The drop-when-seen algorithm:: The coefficient representation uses the current queue contents rather than the original packet set.
  • The drop-when-seen algorithm:: It initializes matrices B_1, ..., B_n to the empty matrix.
  • The drop-when-seen algorithm:: New arrivals are appended to the end of the queue.
  • The drop-when-seen algorithm:: Each receiver basis matrix receives a zero appended to every row when arrivals extend the queue.
  • The drop-when-seen algorithm:: When the queue is nonempty, the sender computes g using the coding module and transmits it.

4) Incorporate channel state feedback:

After feedback, the algorithm updates receiver bases, identifies the oldest unseen packets, constructs coefficients for a targeted linear combination, and removes packets seen by all receivers.

  • For each receiver that received the transmission, the sender adds g’s queue-coordinate vector to its basis and performs Gaussian elimination.
  • The update procedure then refreshes the relevant packet sets and receiver bases.
  • Packets seen by all receivers are collected into S and removed from the basis matrices and queue.
  • After the queue update, the algorithm returns to the arrival-incorporation step for the next slot.
  • The sender processes the receivers’ oldest unseen packets in ascending packet-index order.
  • For each packet group, it uses witnesses to cancel earlier seen packets before selecting a coefficient.
  • The selected coefficient differs from the relevant residual coefficient for every receiver sharing that oldest unseen packet.

2) Compute the transmit packet:

The coding module chooses a linear combination that makes each receiver see its oldest unseen packet after successful reception. This innovation property links the physical sender queue to the receivers’ virtual degrees-of-freedom backlogs.

  • 2) Compute the transmit packet:: If the field size is at least n, the coding module selects a combination that causes any receiver to see its oldest unseen packet upon successful reception.The construction chooses coefficients sequentially so the desired packet remains distinguishable at every receiver.
  • 2) Compute the transmit packet:: The coefficient construction ensures that subtracting a receiver’s known combination leaves its oldest unseen packet together with only later packets.This is the mechanism by which the receiver can see the target packet.
  • 2) Compute the transmit packet:: Seeing an unseen packet corresponds to receiving an unknown degree of freedom, so the construction satisfies the innovation guarantee and supports throughput.The paper explicitly connects the seeing operation to unknown degrees of freedom.
  • 2) Compute the transmit packet:: The notation tracks arrived packets, sender and receiver knowledge spaces, and the sets of packets each receiver has seen.S(t), V(t), Vj(t), and Sj(t) provide the state variables used in the queue-size argument.
  • 2) Compute the transmit packet:: Theorem 4 upper-bounds the physical sender queue by the sum of virtual backlogs, and Corollary 3 gives Algorithm 2’s steady-state expected physical queue size as O.The supplied passage truncates the final expression after O.

V. CONCLUSIONS AND EXTENSIONS

The conclusions present the scheme as an online ARQ extension for coded networks that keeps physical queues aligned with virtual queues. They also identify extensions to delayed or imperfect feedback and to tandem broadcast networks, while leaving broader topologies as an expectation.

  • V. CONCLUSIONS AND EXTENSIONS: The new algorithm’s queue size is significantly lower than Algorithm 1 and can reduce congestion.The comparison is stated alongside the claim that physical and virtual queue sizes track each other.
  • V. CONCLUSIONS AND EXTENSIONS: The physical queue tracks the virtual queue, extending stability and other queuing-theoretic results from virtual queues to physical queues.This is presented as a bridge between the two queue representations.
  • V. CONCLUSIONS AND EXTENSIONS: The authors believe the scheme will be robust to delayed or imperfect feedback, as conventional ARQ is.This is stated as an expectation rather than an established guarantee.
  • V. CONCLUSIONS AND EXTENSIONS: The scheme extends to a tandem network of broadcast links without mergers when intermediate nodes use evidence packets instead of original packets.The extension is stated for this specific topology and intermediate-node operation.
  • V. CONCLUSIONS AND EXTENSIONS: Broader extension to other network topologies is presented as an expectation rather than a demonstrated result.The supplied conclusion does not specify which additional topologies are covered.
  • V. CONCLUSIONS AND EXTENSIONS: The paper describes the proposal as a natural ARQ extension for coded networks and a first step toward feedback-based control of throughput–decoding-delay tradeoffs.The feedback concerns degrees of freedom and dynamic adjustment of packet mixing.
Loading 0802.1754v1…