Method and apparatus providing network coding based flow control
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.
1. 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.
2. The method of claim 1 further comprising determining if a packet is no longer involved in received linear combinations of packets, and removing said packet from said transmit queue.
3. The method of claim 1 wherein said network comprises a network operating in accordance with a Transmission Control Protocol (TCP).
4. The method of claim 1 wherein said transmitting said linear combination of packet further comprises including coding coefficients in a header of said linear combination of packets.
5. The method of claim 1 further comprising dropping the witness of packets prior to the one requested by said receiving node.
6. 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.
7. The method of claim 6 further comprising determining if a packet is no longer involved in received linear combinations of packets, and removing said packet from said transmit queue.
8. The computer readable storage medium of claim 6 wherein said network comprises a network operating in accordance with a Transmission Control Protocol (TCP).
9. The computer readable medium of claim 6 wherein said transmitting said linear combination of packet further comprises including coding coefficients in a header of said linear combination of packets.
10. The computer readable medium of claim 6 further comprising dropping the witness of packets prior to the one requested by said receiving node.
11. 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.
12. The intermediate node of claim 11 further comprising determining if a packet is no longer involved in received linear combinations of packets, and removing said packet from said transmit queue.
13. The intermediate node of claim 11 wherein said network comprises a network operating in accordance with a Transmission Control Protocol (TCP).
14. The intermediate node of claim 11 wherein said transmitting said linear combination of packet further comprises including coding coefficients in a header of said linear combination of packets.
15. The intermediate node of claim 11 further comprising dropping the witness of packets prior to the one requested by said receiving node.