Method and apparatus providing network coding based flow control

• US 8,130,776 B1
• Filed: 08/28/2009
• Issued: 03/06/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: Massachusetts Institute of Technology
• Inventors: Barros, Joao, Jakubczak, Szymon, Sundararajan, Jay Kumar, Shah, Devavrat, Medard, Muriel, Mitzenmacher, Michael
• Primary Examiner(s): Moe, Aung S
• Assistant Examiner(s): ROSE, KERRI M
• Application Number:
  US12/549,925
• Time in Patent Office: 921 Days
• Field of Search: 370/400, 370/401, 370/431, 370/432, 370/462, 370/463
• US Class Current: 370/401
• 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, 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.

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, 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; 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 further comprising maintaining a buffer of linear combinations of packets that have not been decoded yet.

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

11. 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.

12. 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;

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

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

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

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

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

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

15. 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 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, 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.

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

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

18. The computer readable storage medium of claim 15 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. 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 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, 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; 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.

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

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

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

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

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

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

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

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

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

29. 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, 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.

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

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

32. The transmitting node of claim 29 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.

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

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

35. 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, 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; 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.

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

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

38. The receiving node of claim 35 further comprising delivering decoded packets to a node.

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

40. 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;

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

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

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

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