Source-linked AI summary
Network coding meets TCP
Jay Kumar Sundararajan, Devavrat Shah, Muriel Medard, Michael Mitzenmacher, Joao Barros
TL;DR
Lossy links make conventional TCP congestion control problematic because packet losses are treated as congestion signals. The paper adds endpoint network coding and ACKs for newly seen degrees of freedom, enabling a TCP-like control approach. Simulations report much higher throughput than TCP, while field size and coding overhead remain practical questions.
Problem
The paper addresses how to incorporate network coding into TCP with minimal protocol-stack changes for incremental deployment over lossy links.
Method
The protocol transmits random linear combinations at the endpoints and acknowledges degrees of freedom when packets become newly seen.
Results
In a 4-hop tandem network with a 5% loss rate on each link, throughput rises from about 0.007 Mbps with TCP to about 0.39 Mbps with the correct redundancy factor.
Takeaways & Limitations
The endpoint-only coding design supports a practical TCP-compatible approach that masks packet losses from congestion control on lossy links.
Takeaways & Limitations
The simulations assume a large field size, and the practical overhead of coding operations remains to be understood.
Abstract
from arXiv · showhide
We propose a mechanism that incorporates network coding into TCP with only minor changes to the protocol stack, thereby allowing incremental deployment. In our scheme, the source transmits random linear combinations of packets currently in the congestion window. At the heart of our scheme is a new interpretation of ACKs - the sink acknowledges every degree of freedom (i.e., a linear combination that reveals one unit of new information) even if it does not reveal an original packet immediately. Such ACKs enable a TCP-like sliding-window approach to network coding. Our scheme has the nice property that packet losses are essentially masked from the congestion control algorithm. Our algorithm therefore reacts to packet drops in a smooth manner, resulting in a novel and effective approach for congestion control over networks involving lossy links such as wireless links. Our experiments show that our algorithm achieves higher throughput compared to TCP in the presence of lossy wireless links. We also establish the soundness and fairness properties of our algorithm.
I. INTRODUCTION
The paper addresses how to bring network coding into existing TCP-based systems with minimal protocol-stack changes, especially for lossy wireless links. It introduces concepts for representing coded information and motivates a TCP-like sliding-window design.
- Motivation: Network coding improves robustness on lossy wireless networks by mixing data across time and flows.
- Motivation: The incremental deployment problem is how to add network coding naturally to current network systems while preserving practical operation.
- Motivation: The proposed direction seeks a TCP-like sliding-window approach for network coding with very little change to the protocol stack.
- Preliminaries: Coded receivers obtain linear combinations rather than original packets, so TCP’s ordered packet acknowledgments require modification.
- Previous work: Prior network-coding theory had not yet been implemented broadly in practical systems, despite advances toward implementation.
- Preliminaries: The paper represents received information using knowledge spaces, basis matrices, seen packets, and witnesses.
III. THE NEW PROTOCOL
The new protocol masks losses from TCP by transmitting coded combinations and acknowledging newly seen degrees of freedom. It combines this mechanism with RTT-based congestion inference and a separate protocol-stack layer.
- A. Logical description: The protocol transmits random linear combinations of packets in the congestion window instead of original packets.
- A. Logical description: The sink acknowledges a newly seen packet even when it cannot yet decode that original packet.
- A. Logical description: With a large field size, successful coded receptions are likely to reveal the next unseen packet, masking individual losses from TCP.
- A. Logical description: Because masked losses no longer provide a suitable congestion signal, the protocol uses increased RTT and TCP-Vegas-style inference.
- A. Logical description: The RTT estimator matches an ACK to the transmission after the one that triggered the previous ACK.
- A. Logical description: In the four-packet example, transmissions 2, 3, and 4 are treated as attempts to convey the second degree of freedom, with RTT measured from transmission 2.
B. Implementation
Implementation places coding modules below TCP and above IP at the endpoints. The modules buffer packets, generate coded transmissions, recover newly seen packets, and adapt redundancy and RTT signaling.
- B. Implementation: A separate network-coding layer is inserted below TCP and above IP on the source and receiver sides.
- B. Implementation: The sender buffers TCP packets in an encoding buffer and sends coded combinations whose coefficients are included in the header.
- B. Implementation: The redundancy parameter R controls the average number of coded combinations sent per TCP packet.
- B. Implementation: Too little redundancy causes ineffective loss masking and timeouts, while too much can limit coding throughput and congest the network.
- B. Implementation: The receiver appends coefficients to its knowledge-space basis matrix, uses Gaussian elimination to identify newly seen packets, and delivers decoded packets to TCP.
- B. Implementation: Transmit serial numbers and previous-ACK serial numbers support the protocol’s RTT matching procedure.
1) Source side:
The source-side procedure responds to TCP packets and ACKs by maintaining a coding window, scheduling redundancy-controlled coded transmissions, and recording transmission metadata.
- 3) Packet arrives from TCP: The source-side algorithm waits for events and handles packets arriving from TCP or ACKs arriving through IP.
- 3) Packet arrives from TCP: Control packets used for connection management are delivered to IP and return the module to the wait state.
- 3) Packet arrives from TCP: A non-control TCP packet is added to the coding window if it is not already present.
- 3) Packet arrives from TCP: The algorithm increases NUM by the redundancy factor R and repeats coded transmission steps according to the resulting integer part.
- 3) Packet arrives from TCP: Each transmission is a random linear combination with a header containing coefficients, the current window’s packets, and a transmit serial number.
- 3) Packet arrives from TCP: After sending, the source records transmission time and retains the fractional part of NUM for future scheduling.
4) ACK arrives from receiver:
On the receiver side, incoming ACKs are processed according to their type, with network-coding metadata used to update TCP acknowledgment information.
- The TCP ACK header is modified by setting its timestamp-echo field to the transmission time associated with the relevant transmission number.
- The receiver-side algorithm handles arrivals from both the source and the TCP sink.
2) Receiver side:
The receiver records each new coding degree of freedom, updates its decoding state, and acknowledges arrivals using the oldest unseen packet sequence number. Soundness follows because n seen packets provide n independent equations for an n-packet file, and the approach extends to multicast scenarios.
- Receiver processing: The receiver adds each coding vector to its coefficient matrix and uses Gaussian elimination to update the set of seen packets.Payloads are also added to the decoding buffer, where corresponding elimination operations are performed.
- ACK generation: After processing an arrival, the receiver generates a TCP ACK numbered for the oldest unseen packet and adds network-coding ACK metadata.The metadata includes the current PREV NUM and the transmission number of the new arrival.
- Reliable transfer: The acknowledgment mechanism prevents the sender from removing a packet from the coding window before the sink has seen it.
- Soundness: From a file of n packets, if every packet has been seen, then every packet can also be decoded.Seeing n packets corresponds to n linearly independent equations in n unknowns.
- Incremental decoding: The receiver can decode packets during transfer when the number of received equations catches up with the number of involved unknowns, acknowledging each new equation.The resulting decoding buffer tends to remain stable.
- Generality: The soundness arguments can extend to random linear coding multicast over arbitrary topologies.
V. FAIRNESS OF THE PROTOCOL
Simulations evaluate fairness for coded flows and mixed coded/uncoded flows in a four-hop tandem network. With zero loss and unit redundancy, coding preserves fair bandwidth redistribution and compatibility with TCP.
- Simulation setup: Fairness is evaluated through simulations using two competing flows in a four-hop tandem topology.The simulated links have 1 Mbps bandwidth, 100 ms propagation delay, and buffers of 200 packets.
- Fairness criterion: Fairness requires similar competing flows to receive approximately equal bandwidth regardless of their joining order.
- Compared flows: The simulations compare two TCP/NC flows with a coded flow competing against an uncoded TCP flow, using the same α and β values.
- Experimental conditions: 0% loss rate and redundancy parameter 1 are used in both cases for a fair comparison.
- TCP/NC fairness: After the second TCP/NC flow starts, bandwidth is redistributed fairly between the two flows.The result is reported for a simulation in which the two flows start at different times.
- TCP compatibility: When TCP starts first and TCP/NC joins later, bandwidth is again divided fairly, and coding is compatible with TCP in the absence of losses.
VI. EFFECTIVENESS OF THE PROTOCOL
The protocol achieves high throughput under lossy conditions, with performance depending strongly on redundancy and remaining close to capacity as losses increase. Simulations also assess fairness and compatibility with TCP, while omitting coding-header overhead and finite-field effects.
- Simulation results: The simulations study protocol throughput under losses, including redundancy variation and loss-rate comparisons with TCP.The setup also includes fairness and compatibility experiments.
- Redundancy and throughput: 0.399 Mbps is the peak throughput for TCP/NC near R = 1.25, close to the calculated 0.405 Mbps per-flow capacity.The theoretical optimum redundancy is approximately 1.23.
- Redundancy and throughput: 0.011 Mbps per flow is achieved by TCP/NC even with R = 0, improving on TCP by almost a factor of 2.With the correct redundancy choice, TCP/NC throughput is much higher than the reported TCP-flow throughputs of 0.0062 and 0.0072 Mbps.
- Loss-rate comparison: TCP/NC remains robust as loss rates increase and reaches throughput close to capacity, whereas TCP throughput falls rapidly.The comparison varies all-link loss rates from 0 to 5%, using the optimum redundancy for each TCP/NC loss rate.
- Limitations: The simulations omit network-coding header overhead and throughput loss from insufficient field size; quantifying the latter remains future work.The authors note that practical field sizes may limit these effects to transient behavior.
B. The ideal case
The ideal-case analysis models coded forwarding across an erasure-channel daisy chain with perfect end-to-end feedback. It examines queue behavior and extends the model to nodes that simply forward packets.
- The ideal case: The idealized analysis focuses on how coding and feedback interact, providing a first-order model for later practical extensions.The analysis investigates queue sizes at various nodes.
- The ideal case: The network is a daisy chain of N nodes connected by packet-erasure channels, with random linear combinations transmitted from each queue.The source generates packets at rate λ, and transmissions occur in slotted time.
- The ideal case: The model assumes perfect, delay-free feedback from sink to source and independent erasures across channels and time.Channel i is ON with probability µ_i, giving capacity min_i µ_i packets per slot.
- The ideal case: The analysis also covers networks where some intermediate nodes do not code by combining adjacent links into an equivalent link.An erasure on either adjacent link causes packet erasure through the forwarding node.
- The ideal case: The sink sends an ACK to the source in every slot to support queue-content updates in the coding scheme.This feedback is part of the mechanism for maintaining coded queues.
2) Queue update mechanism:
The queue update mechanism relies on random linear coding: successful receptions usually reveal the next unseen packet, allowing queue evolution to be analyzed through packet arrivals, departures, and ACK-driven updates.
- Queue update mechanism: Intermediate nodes receive sink ACK information through feed-forward, while the source removes packets older than the sink’s requested index.The ACK contains the oldest packet not yet seen by the sink.
- Queue update mechanism: Coding at intermediate nodes can achieve network capacity, while forwarding-only nodes support the capacity of a network formed by collapsing links across them.The capacity is stated as min_i µ_i.
- Queue update mechanism: Queues at every node are stable when λ < µ_k for all 0 ≤ k < N.The theorem also gives the expected steady-state queue size at node k.
- Queue update mechanism: With equal channel loads, heavy traffic produces longer queues near the source than near the sink.This behavior follows in the limit as ρ → 1.
- Queue update mechanism: For sufficiently large fields, each successful reception reveals the next unseen packet with high probability, supporting contiguous seen-packet sets in the queueing analysis.The analysis assumes this event always occurs; the lemma indicates that the assumption becomes increasingly accurate as field size grows.
- Queue update mechanism: Packet arrival is defined by first observation, departure by dropping its witness from the queue, and expected queue size follows from the associated waiting time via Little’s law.The proof divides a packet’s queue residence time into two parts.
1) Time until the packet is seen by the sink:
The time for a packet to reach the sink is modeled as the sum of waiting times across downstream links, with each term determined by channel availability and traffic load.
- Time until the packet is seen by the sink: The expected time until the sink sees a packet is the sum of N − k downstream waiting-time terms.Each term corresponds to the time for the next node to see the packet.
2) Time until sink’s ACK reaches intermediate node:
The analysis accounts for ACK propagation through intermediate nodes and concludes with the proposal’s practical deployment and simulated throughput gains on lossy links.
- Time until sink’s ACK reaches intermediate node: ACK information propagates toward node k through feed-forward, with each channel’s expected ON-wait equal to 1/µ_i.The total propagation time to node k is expressed as a sum over preceding channels.
- Time until sink’s ACK reaches intermediate node: Little’s law converts the expected queue residence time into the expected queue size at node k when λ < min_i µ_i.This calculation assumes the system is stable.
- Conclusions and future work: Coding only at end hosts preserves TCP’s end-to-end philosophy while placing the network coding layer between transport and network layers.The design is intended to be deployable in existing systems.
- Conclusions and future work: 0.39 Mbps versus about 0.007 Mbps: in a 4-hop tandem network with 5% loss per link, throughput increases for the correct redundancy factor.This is the reported simulation example comparing the proposed protocol with TCP.
- Conclusions and future work: The simulations assume a large field size, and the impact of field size and practical coding overhead remains future work.The impact of coding at intermediate nodes is also left for future study.
- Conclusions and future work: The framework is proposed for extension to multicast over general networks and to multipath TCP based on network coding.These are identified as future directions.