Network Coding Meets TCP: Theory and Implementation
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...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/75026 https://orcid.org/0000-0003-4059-407X https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1826197916935520256 |
|---|---|
| author | Sundararajan, Jay Kumar Shah, Devavrat Medard, Muriel Jakubczak, Szymon Kazimierz Mitzenmacher, Michael Barros, Joao |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Sundararajan, Jay Kumar Shah, Devavrat Medard, Muriel Jakubczak, Szymon Kazimierz Mitzenmacher, Michael Barros, Joao |
| author_sort | Sundararajan, Jay Kumar |
| collection | MIT |
| description | 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 wind ow 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. |
| first_indexed | 2024-09-23T10:55:36Z |
| format | Article |
| id | mit-1721.1/75026 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:55:36Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/750262022-09-30T23:59:09Z Network Coding Meets TCP: Theory and Implementation Sundararajan, Jay Kumar Shah, Devavrat Medard, Muriel Jakubczak, Szymon Kazimierz Mitzenmacher, Michael Barros, Joao Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shah, Devavrat Medard, Muriel Jakubczak, Szymon Kazimierz Sundararajan, Jay Kumar 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 wind ow 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. National Science Foundation (U.S.) (Grant CNS-0627021) National Science Foundation (U.S.) (Grant CNS-0721491) National Science Foundation (U.S.) (Grant CCF-0915922) United States. Defense Advanced Research Projects Agency (Subcontract 18870740-37362-C) United States. Defense Advanced Research Projects Agency (Subcontract 060786) United States. Defense Advanced Research Projects Agency (Subcontract 069145) United States. Defense Advanced Research Projects Agency (Contract N66001-06-C-2020) Space and Naval Warfare Systems Center San Diego (U.S.) (Contract N66001- 08-C-2013) 2012-11-26T19:57:40Z 2012-11-26T19:57:40Z 2011-01 2010-03 Article http://purl.org/eprint/type/JournalArticle 0018-9219 1558-2256 http://hdl.handle.net/1721.1/75026 Sundararajan, Jay Kumar et al. “Network Coding Meets TCP: Theory and Implementation.” Proceedings of the IEEE 99.3 (2011): 490–512. https://orcid.org/0000-0003-4059-407X https://orcid.org/0000-0003-0737-3259 en_US http://dx.doi.org/10.1109/JPROC.2010.2093850 Proceedings of the IEEE Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Sundararajan, Jay Kumar Shah, Devavrat Medard, Muriel Jakubczak, Szymon Kazimierz Mitzenmacher, Michael Barros, Joao Network Coding Meets TCP: Theory and Implementation |
| title | Network Coding Meets TCP: Theory and Implementation |
| title_full | Network Coding Meets TCP: Theory and Implementation |
| title_fullStr | Network Coding Meets TCP: Theory and Implementation |
| title_full_unstemmed | Network Coding Meets TCP: Theory and Implementation |
| title_short | Network Coding Meets TCP: Theory and Implementation |
| title_sort | network coding meets tcp theory and implementation |
| url | http://hdl.handle.net/1721.1/75026 https://orcid.org/0000-0003-4059-407X https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT sundararajanjaykumar networkcodingmeetstcptheoryandimplementation AT shahdevavrat networkcodingmeetstcptheoryandimplementation AT medardmuriel networkcodingmeetstcptheoryandimplementation AT jakubczakszymonkazimierz networkcodingmeetstcptheoryandimplementation AT mitzenmachermichael networkcodingmeetstcptheoryandimplementation AT barrosjoao networkcodingmeetstcptheoryandimplementation |