Method and apparatus providing network coding based flow control
AssigneesPresident and Fellow of Harvard College, Universidade Do Porto, Massachusetts Institute of Technology
InventorsJay Kumar Sundararajan, Devavrat Shah, Muriel Medard, Michael Mitzenmacher, Joao Barros, Szymon Jakubczak
Life of this patent
Estimating the term…
Abstract
A method, apparatus and computer program product for providing network based flow control is presented. A linear combination of packets to transmit from a transmit queue is determined. The linear combination of packets is transmitted across a network using a sliding window protocol. An acknowledgement (ACK) is generated, wherein a packet is acknowledged when a receiving node receives the linear combination of packets and determines which packet of the linear combination of packets has been newly seen.
Claims15
A computer-implemented method in which an intermediate node performs operations comprising:
- receiving, at said intermediate node, a linear combination of packets from a transmitting node, wherein when said intermediate node receives an innovative packet, determining from said innovative packet a newly seen packet and adding the witness of the newly seen packet to said transmit queue, wherein said determining whether a packet is newly seen includes retrieving coding coefficients from a header of said linear combination of packets, appending said coding coefficients to a basis matrix, and performing Gaussian elimination to determine whether the packet is newly seen;
- determining a linear combination of packets to transmit from a transmit queue of said intermediate node;
- and
- transmitting said linear combination of packets from said intermediate node to a receiving node across a network using a sliding window protocol.
A non-transitory computer readable storage medium having computer readable code thereon for providing network coding based flow control, the medium including instructions in which an intermediate node performs operations comprising:
- receiving, at said intermediate node, a linear combination of packets from a transmitting node, wherein when said intermediate node receives an innovative packet, determining from said innovative packet a newly seen packet and adding the witness of the newly seen packet to said transmit queue, wherein said determining whether a packet is newly seen includes retrieving coding coefficients from a header of said linear combination of packets, appending said coding coefficients to a basis matrix, and performing Gaussian elimination to determine whether the packet is newly seen;
- determining a linear combination of packets to transmit from a transmit queue of said intermediate node;
- and
- transmitting said linear combination of packets across a network to a receiving node using a sliding window protocol.
An intermediate node comprising:
- a memory;
- a processor,
- a communications interface;
- an interconnection mechanism coupling the memory, the processor and the communications interface;
- and
- wherein the memory is encoded with an application providing network coding based flow control, that when performed on the processor, provides a process for processing information, the process causing the intermediate node to perform the operations of:
- receiving, at said intermediate node, a linear combination of packets from a transmitting node, wherein when said intermediate node receives an innovative packet, determining from said innovative packet a newly seen packet and adding the witness of the newly seen packet to said transmit queue, wherein said determining whether a packet is newly seen includes retrieving coding coefficients from a header of said linear combination of packets, appending said coding coefficients to a basis matrix, and performing Gaussian elimination to determine whether the packet is newly seen;
- determining a linear combination of packets to transmit from a transmit queue of said intermediate node;
- and
- transmitting said linear combination of packets across a network to a receiving node using a sliding window protocol.
Dependencies are inferred from the claim text.