A large number of streaming applications use reliable transport protocols such as TCP to deliver content over the Internet. However, head-of-line blocking due to packet loss recovery can often result in unwanted behavior and poor application layer performance. Transport layer coding can help mitigate this issue by helping to recover from lost packets without waiting for retransmissions. We consider the use of an on-line network code that inserts coded packets at strategic locations within the underlying packet stream. If retransmissions are necessary, additional coding packets are transmitted to ensure the receiver's ability to decode. An analysis of this scheme is provided that helps determine both the expected in-order packet delivery delay and its variance. Numerical results are then used to determine when and how many coded packets should be inserted into the packet stream, in addition to determining the trade-offs between reducing the in-order delay and the achievable rate. The analytical results are finally compared with experimental results to provide insight into how to minimize the delay of existing transport layer protocols.
A resurgence of interest in coding at the transport layer has taken place to help overcome TCP's poor performance in wireless networks. Sundararajan et. al. @cite_24 first proposed TCP with Network Coding (TCP NC). They insert a coding shim between the TCP and IP layers that introduces redundancy into the network in order to spoof TCP into believing the network is error-free. Loss-Tolerant TCP (LT-TCP) @cite_21 @cite_15 @cite_8 is another approach using Reed-Solomon (RS) codes and explicit congestion notification (ECN) to overcome random packet erasures and improve performance. In addition, Coded TCP (CTCP) @cite_11 uses RLNC @cite_6 and a modified additive-increase, multiplicative decrease (AIMD) algorithm for maintaining high throughput in high packet erasure networks. While these proposals have shown coding can help increase throughput, especially in challenged networks, only anecdotal evidence has been provided showing the benefits for time sensitive applications.
@cite_8 @cite_21 @cite_6 @cite_24 @cite_15 @cite_11
1993520373 2042955355 2048235391 2134795104 1590243065 1978227705
TCP is the ubiquitous transport protocol in the Internet. However, in a wireless ad-hoc environment where links are unreliable, TCP causes a number of performance issues. The key reason behind this is that TCP considers all packet losses to be due to congestion and reduces its send rate, which is not necessarily appropriate in a lossy ad-hoc environment. In prior work, we have designed Loss Tolerant TCP (LT-TCP) [1], [2], which extends TCP towards making it more efficient and robust in a wireless ad-hoc environment. LT-TCP uses Explicit Congestion Notification (ECN) and forward error correction (FEC) to mitigate the effects of random packet losses. The protocol uses these mechanisms to both distinguish between congestion and other losses, and recover from losses due to lossy wireless links. In this paper, we describe the implementation of LT-TCP in the Linux operating system kernel, and present and analyze initial performance results for the protocol on lossy links. Results show that LT-TCP provides much improved performance over TCP over lossy connections that model ad-hoc networks. In addition, it shows that performance of LT-TCP is nearly linear with loss rate, whereas TCP suffers disproportionately as loss rate increases. These promising implementation results point to further experimentation for LT-TCP, including a push towards Internet standards bodies. With increasing dependence on wireless networks as an integral part of the communication infrastructure, it is critical that data link and transport layer protocols perform reasonably under potentially severe lossy conditions. A key strategy is to use hybrid ARQ (HARQ) with erasure codes (a.k.a. forward error correction or FEC) sent both proactively and reactively in response to feedback about dynamic loss statistics. A challenge is to design HARQ to satisfy multiple objectives such as high goodput, low latency and negligible residual loss rate. In this paper, we analyze the performance benefits and trade-offs of these reliability strategies (hybrid ARQ+FEC). We derive expressions for the expected good-put (and overhead in terms of FEC wastage), latency, and residual loss for a given raw erasure loss process (e.g. uniform and bursty loss models). We show how the analysis can be used to explain and provide specialized design guidance for link-layer HARQ that is subject to tight delay constraints and a recently designed transport layer HARQ scheme (called loss-tolerant TCP). We validate our analysis by comparing the predictions with values obtained from simulations performed on the link and transport layer HARQ strategies with ns-2. We believe that such an analysis could also have value for other adaptive protocols using network coding and incremental redundancy techniques. We present a distributed random linear network coding approach for transmission and compression of information in general multisource multicast networks. Network nodes independently and randomly select linear mappings from inputs onto output links over some field. We show that this achieves capacity with probability exponentially approaching 1 with the code length. We also demonstrate that random linear coding performs compression when necessary in a network, generalizing error exponents for linear Slepian-Wolf coding in a natural way. Benefits of this approach are decentralized operation and robustness to network changes or link failures. We show that this approach can take advantage of redundant network capacity for improved success probability and robustness. We illustrate some potential advantages of random linear network coding over routing in two examples of practical scenarios: distributed network operation and networks with dynamically varying connections. Our derivation of these results also yields a new bound on required field size for centralized network coding on general multicast networks The theory of network coding promises significant benefits in network performance, especially in lossy networks and in multicast and multipath scenarios. To realize these benefits in practice, we need to understand how coding across packets interacts with the acknowledgment (ACK)-based flow control mechanism that forms a central part of today's Internet protocols such as transmission control protocol (TCP). Current approaches such as rateless codes and batch-based coding are not compatible with TCP's retransmission and sliding-window mechanisms. In this paper, we propose a new mechanism called TCP NC 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. Thus, our new TCP ACK rule takes into account the network coding operations in the lower layer and enables a TCP-compatible sliding-window approach to network coding. Coding essentially masks losses from the congestion control algorithm and allows TCP NC to react smoothly to losses, resulting in a novel and effective approach for congestion control over lossy networks such as wireless networks. An important feature of our solution is that it allows intermediate nodes to perform re-encoding of packets, which is known to provide significant throughput gains in lossy networks and multicast scenarios. Simulations show that our scheme, with or without re-encoding inside the network, achieves much higher throughput compared to TCP over lossy wireless links. We present a real-world implementation of this protocol that addresses the practical aspects of incorporating network coding and decoding with TCP's window management mechanism. We work with TCP-Reno, which is a widespread and practical variant of TCP. Our implementation significantly advances the goal of designing a deployable, general, TCP-compatible protocol that provides the benefits of network coding. TCP performance over wireless links suffers substantially when packet error rates increase beyond about 1 - 5 . This paper proposes end-end mechanisms to improve TCP performance over lossy networks with potentially much higher packet loss rates. Our proposed scheme separates congestion indications from wireless packet erasures by exploiting ECN. Timeout effects due to packet erasures are combated using a dynamic and adaptive Forward Error Correction (FEC) scheme that includes adaptation of TCP’s Maximum Segment Size. Proactive and reactive FEC overhead enhance TCP SACK to protect original segments and retransmissions respectively. Dynamically changing the MSS tailors the number of segments in the window for optimal performance. SACK and timeout mechanisms are used as a last resort. ns-2 simulations show that our scheme substantially improves TCP performance even for packet loss rates up to 30 , thus extending the dynamic range and performance of TCP over networks with lossy (e.g., wireless) links. United States. Dept. of Defense. Assistant Secretary of Defense for Research & Engineering (United States. Air Force Contract FA8721-05-C-0002)