{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/54230"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/54230","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"On the role of feedback in network coding","abstract":"Network coding has emerged as a new approach to operating communication networks, with a promise of improved efficiency in the form of higher throughput, especially in lossy conditions. In order to realize this promise in practice, the interfacing of network coding with existing network protocols must be understood well. Most current protocols make use of feedback in the form of acknowledgments (ACKs) for reliability, rate control and/or delay control. In this work, we propose a way to incorporate network coding within such a feedback-based framework, and study the various benefits of using feedback in a network coded system. More specifically, we propose a mechanism that provides a clean interface between network coding and 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 TCP congestion window. At the heart of our scheme is a new interpretation of ACKs - the receiver 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-compatible sliding-window implementation of network coding. Thus, with feedback, network coding can be performed in a completely online manner, without the need for batches or generations. Our scheme has the nice feature that packet losses on the link can be essentially masked from the congestion control algorithm by adding enough redundancy in the encoding process.","abstract_html":"Network coding has emerged as a new approach to operating communication networks, with a promise of improved efficiency in the form of higher throughput, especially in lossy conditions. In order to realize this promise in practice, the interfacing of network coding with existing network protocols must be understood well. Most current protocols make use of feedback in the form of acknowledgments (ACKs) for reliability, rate control and/or delay control. In this work, we propose a way to incorporate network coding within such a feedback-based framework, and study the various benefits of using feedback in a network coded system. More specifically, we propose a mechanism that provides a clean interface between network coding and 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 TCP congestion window. At the heart of our scheme is a new interpretation of ACKs - the receiver 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-compatible sliding-window implementation of network coding. Thus, with feedback, network coding can be performed in a completely online manner, without the need for batches or generations. Our scheme has the nice feature that packet losses on the link can be essentially masked from the congestion control algorithm by adding enough redundancy in the encoding process.","abstract_has_math":false,"creators":["Sundararajan, Jay Kumar, 1982-"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Muriel Médard and Devavrat Shah."],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009","date_published":"2009","updated_at":"2026-07-22T22:20:51Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/54230","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Muriel Médard and Devavrat Shah."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Sundararajan, Jay Kumar, 1982-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2010-04-26T19:40:59Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2010-04-26T19:40:59Z"]},{"key":"dc:date.issued","label":"Date","values":["2009"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/54230"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.","This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.","Cataloged from student submitted PDF version of thesis.","Includes bibliographical references (p. 143-149)."]},{"key":"dc:description.abstract","label":"Abstract","values":["Network coding has emerged as a new approach to operating communication networks, with a promise of improved efficiency in the form of higher throughput, especially in lossy conditions. In order to realize this promise in practice, the interfacing of network coding with existing network protocols must be understood well. Most current protocols make use of feedback in the form of acknowledgments (ACKs) for reliability, rate control and/or delay control. In this work, we propose a way to incorporate network coding within such a feedback-based framework, and study the various benefits of using feedback in a network coded system. More specifically, we propose a mechanism that provides a clean interface between network coding and 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 TCP congestion window. At the heart of our scheme is a new interpretation of ACKs - the receiver 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-compatible sliding-window implementation of network coding. Thus, with feedback, network coding can be performed in a completely online manner, without the need for batches or generations. Our scheme has the nice feature that packet losses on the link can be essentially masked from the congestion control algorithm by adding enough redundancy in the encoding process.","(cont.) This results in a novel and effective approach for congestion control over networks involving lossy links such as wireless links. Our scheme also allows intermediate nodes to perform re-encoding of the data packets. This in turn leads to a natural way of running TCP flows over networks that use multipath opportunistic routing along with network coding. We use the new type of ACKs to develop queue management algorithms for coded networks, which allow the queue size at nodes to track the true backlog in information with respect to the destination. We also propose feedback-based adaptive coding techniques that are aimed at reducing the decoding delay at the receivers. Different notions of decoding delay are considered, including an order-sensitive notion which assumes that packets are useful only when delivered in order. We study the asymptotic behavior of the expected queue size and delay, in the limit of heavy traffic."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["On the role of feedback in network coding"]}]}],"canonical_facts":{"dc:contributor.advisor":["Muriel Médard and Devavrat Shah."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Sundararajan, Jay Kumar, 1982-"],"dc:date.accessioned":["2010-04-26T19:40:59Z"],"dc:date.available":["2010-04-26T19:40:59Z"],"dc:date.issued":["2009"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.","This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.","Cataloged from student submitted PDF version of thesis.","Includes bibliographical references (p. 143-149)."],"dc:description.abstract":["Network coding has emerged as a new approach to operating communication networks, with a promise of improved efficiency in the form of higher throughput, especially in lossy conditions. In order to realize this promise in practice, the interfacing of network coding with existing network protocols must be understood well. Most current protocols make use of feedback in the form of acknowledgments (ACKs) for reliability, rate control and/or delay control. In this work, we propose a way to incorporate network coding within such a feedback-based framework, and study the various benefits of using feedback in a network coded system. More specifically, we propose a mechanism that provides a clean interface between network coding and 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 TCP congestion window. At the heart of our scheme is a new interpretation of ACKs - the receiver 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-compatible sliding-window implementation of network coding. Thus, with feedback, network coding can be performed in a completely online manner, without the need for batches or generations. Our scheme has the nice feature that packet losses on the link can be essentially masked from the congestion control algorithm by adding enough redundancy in the encoding process.","(cont.) This results in a novel and effective approach for congestion control over networks involving lossy links such as wireless links. Our scheme also allows intermediate nodes to perform re-encoding of the data packets. This in turn leads to a natural way of running TCP flows over networks that use multipath opportunistic routing along with network coding. We use the new type of ACKs to develop queue management algorithms for coded networks, which allow the queue size at nodes to track the true backlog in information with respect to the destination. We also propose feedback-based adaptive coding techniques that are aimed at reducing the decoding delay at the receivers. Different notions of decoding delay are considered, including an order-sensitive notion which assumes that packets are useful only when delivered in order. We study the asymptotic behavior of the expected queue size and delay, in the limit of heavy traffic."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/54230"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["On the role of feedback in network coding"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:20:51Z"}