METHOD AND APPARATUS PROVIDING NETWORK CODING BASED FLOW CONTROL

• US 20120218891A1
• Filed: 02/24/2012
• Published: 08/30/2012
• Est. Priority Date: 08/28/2009
• Status: Active Grant

• Current Assignee: President and Fellows of Harvard College (Harvard Corporation), Massachusetts Institute of Technology, Universidade D.O. Porto
• Original Assignee: President and Fellows of Harvard College (Harvard Corporation), Massachusetts Institute of Technology, Universidade D.O. Porto
• Inventors: Sundararajan, Jay Kumar, Shah, Devavrat, Medard, Muriel, Mitzenmacher, Michael, Barros, Joao, Jakubczak, Szymon
• Granted Patent: US 8,526,451 B2
• Time in Patent Office: Days
• US Class Current: 370/231
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]

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.

Claims

1. A computer-implemented method in which a transmitting node performs operations comprising:

determining a linear combination of packets to transmit from a transmit queue;

transmitting said linear combination of packets across a network using a sliding window protocol; and

receiving an acknowledgement (ACK), wherein a packet is acknowledged when a receiving node receives the linear combination of packets and determines which packet of said linear combination of packets has been newly seen.

2. The method of claim 1 further comprising removing a packet from said transmit queue which has been acknowledged.

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 packets across a network using a sliding window protocol further comprises including coding coefficients in a header of said linear combination of packets.

5. The method of claim 1 wherein said linear combination of packets is linearly independent of previously transmitted linear combinations of packets and therefore conveys new information.

6. The method of claim 1 wherein said ACK comprises receiving a request of a byte sequence number of a first byte of a first unseen packet.

7. A computer-implemented method in which a receiving node performs operations comprising:

receiving a linear combination of packets across a network using a sliding window protocol;

determining whether a packet is newly seen; and

transmitting an acknowledgement (ACK), wherein a packet is acknowledged when the receiving node receives the linear combination of packets and determines which packet of said linear combination of packets has been newly seen.

8. The method of claim 7 wherein said network comprises a network operating in accordance with a Transmission Control Protocol (TCP).

9. The method of claim 7 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 a Gaussian elimination to determine which packet is newly seen so that the newly seen packet can be acknowledged.

10. The method of claim 7 further comprising maintaining a buffer of linear combinations of packets that have not been decoded yet.

11. The method of claim 7 further comprising delivering decoded packets to a node.

12. The method of claim 7 wherein said ACK comprises receiving a request of a byte sequence number of a first byte of a first unseen packet.

13. A computer-implemented method in which an intermediate node performs operations comprising:

receiving a linear combination of packets;

determining a linear combination of packets to transmit from a transmit queue; and

transmitting said linear combination of packets across a network using a sliding window protocol.

14. The method of claim 13 further comprising determining if a packet is no longer involved in received linear combinations of packets, and removing said packet from said transmit queue.

15. The method of claim 13 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.

16. The method of claim 13 wherein said network comprises a network operating in accordance with a Transmission Control Protocol (TCP).

17. A computer readable storage medium having computer readable code thereon for providing network coding based flow control, the medium including instructions in which a transmitting node performs operations comprising:

determining a linear combination of packets to transmit from a transmit queue;

transmitting said linear combination of packets across a network using a sliding window protocol; and

receiving an acknowledgement (ACK), wherein a packet is acknowledged when a receiving node receives the linear combination of packets and determines which packet of said linear combination of packets has been newly seen.

18. The computer readable storage medium of claim 17 further comprising removing a packet from said transmit queue which has been acknowledged.

19. The computer readable storage medium of claim 17 wherein said network comprises a network operating in accordance with a Transmission Control Protocol (TCP).

20. The computer readable storage medium of claim 17 wherein said transmitting said linear combination of packets across a network using a sliding window protocol further comprises including coding coefficients in a header of said linear combination of packets.

21. The computer readable storage medium of claim 17 wherein said linear combination of packets is linearly independent of previously transmitted linear combinations of packets and therefore conveys new information.

22. The computer readable storage medium of claim 17 wherein said ACK comprises receiving a request of a byte sequence number of a first byte of a first unseen packet.

23. A computer readable storage medium having computer readable code thereon for providing network coding based flow control, the medium including instructions in which a receiving node performs operations comprising:

receiving a linear combination of packets across a network using a sliding window protocol;

determining whether a packet is newly seen; and

transmitting an acknowledgement (ACK), wherein a packet is acknowledged when the receiving node receives the linear combination of packets and determines which packet of said linear combination of packets has been newly seen.

24. The computer readable storage medium of claim 23 wherein said network comprises a network operating in accordance with a Transmission Control Protocol (TCP).

25. The computer readable storage medium of claim 23 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 a Gaussian elimination to determine which packet is newly seen so that the newly seen packet can be acknowledged.

26. The computer readable storage medium of claim 23 further comprising maintaining a buffer of linear combinations of packets that have not been decoded yet.

27. The computer readable storage medium of claim 23 further comprising delivering decoded packets to a node.

28. The computer readable storage medium of claim 23 wherein said ACK comprises receiving a request of a byte sequence number of a first byte of a first unseen packet.

29. A 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 a linear combination of packets;

determining a linear combination of packets to transmit from a transmit queue; and

transmitting said linear combination of packets across a network using a sliding window protocol.

30. The method of claim 29 further comprising determining if a packet is no longer involved in received linear combinations of packets, and removing said packet from said transmit queue.

31. The computer readable storage medium of claim 29 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.

32. The computer readable storage medium of claim 29 wherein said network comprises a network operating in accordance with a Transmission Control Protocol (TCP).

33. A transmitting 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 transmitting node to perform the operations of;

determining a linear combination of packets to transmit from a transmit queue;

transmitting said linear combination of packets across a network using a sliding window protocol; and

receiving an acknowledgement (ACK), wherein a packet is acknowledged when a receiving node receives the linear combination of packets and determines which packet of said linear combination of packets has been newly seen.

34. The transmitting node of claim 33 further comprising removing a packet from said transmit queue which has been acknowledged.

35. The transmitting node of claim 33 wherein said network comprises a network operating in accordance with a Transmission Control Protocol (TCP).

36. The transmitting node of claim 33 wherein said transmitting said linear combination of packets across a network using a sliding window protocol further comprises including coding coefficients in a header of said linear combination of packets.

37. The transmitting node of claim 33 wherein said linear combination of packets is linearly independent of previously transmitted linear combinations of packets and therefore conveys new information.

38. The transmitting node of claim 33 wherein said ACK comprises receiving a request of a byte sequence number of a first byte of a first unseen packet.

39. A receiving 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 receiving node to perform the operations of;

receiving a linear combination of packets across a network using a sliding window protocol;

determining whether a packet is newly seen; and

transmitting an acknowledgement (ACK), wherein a packet is acknowledged when the receiving node receives the linear combination of packets and determines which packet of said linear combination of packets has been newly seen.

40. The receiving node of claim 39 wherein said network comprises a network operating in accordance with a Transmission Control Protocol (TCP).

41. The receiving node of claim 39 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 a Gaussian elimination to determine which packet is newly seen so that the newly seen packet can be acknowledged.

42. The receiving node of claim 39 further comprising maintaining a buffer of linear combinations of packets that have not been decoded yet.

43. The receiving node of claim 39 further comprising delivering decoded packets to a node.

44. The receiving node of claim 39 wherein said ACK comprises receiving a request of a byte sequence number of a first byte of a first unseen packet.

45. 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 a linear combination of packets;

determining a linear combination of packets to transmit from a transmit queue; and

transmitting said linear combination of packets across a network using a sliding window protocol.

46. The intermediate node of claim 45 further comprising determining if a packet is no longer involved in received linear combinations of packets, and removing said packet from said transmit queue.

47. The intermediate node of claim 45 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.

48. The intermediate node of claim 45 wherein said network comprises a network operating in accordance with a Transmission Control Protocol (TCP).