Methods and apparatus for network coding

• US 20080075080A1
• Filed: 09/27/2006
• Published: 03/27/2008
• Est. Priority Date: 09/27/2006
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Katti, Sachin, Rahul, Hariharan, Katabi, Dina
• Granted Patent: US 8,081,641 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04B 7/15521 combining by calculations packets received from different stations before transmitting the combined packets as part of network coding network coding aspects for detection or prevention of errors in the information received H04L1/0076; network traffic management with optimizing of information sizing, e.g. header compression, by using assembly and disassembly of packets H04W28/065
• CPC Class Codes: H04L 1/1671 the supervisory signal being transmitted together with control information
• CPC Class Codes: H04L 1/1854 Scheduling and prioritising arrangements
• CPC Class Codes: H04L 12/1877 Measures taken prior to transmission
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00

Abstract

One embodiment is directed to transmitting encoded data over a broadcast medium to improve network throughput. A sending node may identify a first packet to be transmitted to a first network node and a second packet to be transmitted to a second network node. The sending node may determine whether the first network node stores the second packet and whether the second network node stores the first packet. If the sending node determines that the first network node stores the second packet and the second network node stores the first packet, it may code together the first and second packets to generate an encoded packet and may transmit the encoded packet over the broadcast medium. Thus, the first packet may be transmitted to the first network node and the second packet may be transmitted to the second node in a single transmission.

Claims

1. A method of transmitting data from a sending network node over a network comprising a plurality of nodes including the sending network node, at least some of the plurality of nodes being coupled by a broadcast medium, wherein the sending network node has a queue of messages to be transmitted, the queue including a first message received from a first previous hop and a second message received from a second previous hop, and wherein the method comprises acts of:

identifying the first message to be transmitted from the sending network node to a first destination node via a first network node;

identifying the second message to be transmitted from the sending network node to a second destination node via a second network node, wherein the second network node is not the first previous hop;

determining whether the first network node stores the second message;

determining whether the second network node stores the first message;

if it is determined that the first network node stores the second message and the second network node stores the first message, coding together the first and second messages to generate an encoded message; and

transmitting the encoded message over the broadcast medium.

2. The method of claim 1, further comprising acts of:

identifying a third message in the queue to be transmitted from the sending network node to a third destination node via a third network node;

determining whether the first and second network nodes store the third message;

determining whether the third network node stores the first and second messages; and

when it is determined that the first and second network nodes store the third message and the third network node stores the first and second messages, coding together the first, second, and third messages to generate the encoded message.

3. The method of claim 1, wherein the network is a wireless network and the broadcast medium is air.

4. The method of claim 1, wherein the broadcast medium includes at least one network cable.

5. The method of claim 1, wherein each of the plurality of nodes is a processor in a parallel computer and the broadcast medium includes at least one communication bus.

6. The method of claim 1, wherein the first destination node and the first network node are different nodes.

7. The method of claim 1, wherein the first destination node and the first network node are the same node.

8. The method of claim 1, wherein the second destination node and the second network node are different nodes.

9. The method of claim 1, wherein the second destination node and the second network node are the same node.

10. The method of claim 1, wherein the first and second destination nodes are different nodes.

11. The method of claim 1, wherein the first and second destination nodes are the same node.

12. The method of claim 1, wherein the first and second network nodes are different nodes.

13. The method of claim 1, wherein the act of coding together the first and second messages to generate the encoded message further comprises an act of XORing the first and second messages to generate the encoded message.

14. The method of claim 1, wherein the act of coding together the first and second messages to generates the encoded message further comprises an act of computing linear combinations of the first and second messages over a finite field to generate the encoded message.

15. The method of claim 1, further comprising an act of:

scheduling a retransmission of the first message to occur if an acknowledgment of receipt of the first message by the first network node is not received within a predetermined period of time.

16. The method of claim 1, further comprising an act of:

scheduling a retransmission of the second message to occur if an acknowledgment of receipt of the second message by the second network node is not received within a predetermined period of time.

17. The method of claim 1, wherein the sending network node includes a message pool in which messages received over the network are temporarily stored, and wherein the method further comprises an act of:

including in the encoded message a reception report that identifies at least a portion of the messages stored in the message pool of the sending network node.

18. The method of claim 1, wherein the act of determining whether the first network node stores the second message further comprises an act of:

determining whether the first network node stores the second message using a reception report received from the first network node that identifies at least some of the messages stored by the first network node.

19. The method of claim 1, wherein the act of determining whether the second network node stores the first message further comprises an act of:

determining whether the first network node stores the second message using a reception report received from the first network node that identifies at least some of the messages stored by the first network node.

20. The method of claim 1, wherein the act of determining whether the first network node stores the second message further comprises an act of:

probabilistically determining whether the first network node stores the second message.

21. The method of claim 1, wherein the act of determining whether the second network node stores the first message further comprises an act of:

probabilistically determining whether the second network node stores the first message.

22. The method of claim 1, wherein the act of determining whether the first network node stores the second message further comprises an act of:

determining whether the first network node is capable of computing the second message.

23. The method of claim 1, further comprising acts of:

receiving the encoded message at the first network node; and

decoding the encoded message at the first network node using the second message to obtain the first message.

24. The method of claim 23, wherein the act of decoding the encoded message further comprises an act of:

XORing the encoded message and the second message.

25. The method of claim 23, further comprising an act of:

adding the first message to a message pool on the first network node.

26. The method of claim 1, wherein the first message comprises at least a portion of a packet.

27. The method of claim 1, wherein the first message comprises at least a portion of a frame.

28. The method of claim 1, wherein the first message comprises at least a portion of a cell.

29. The method of claim 1, wherein the first message comprises a sequence of packets.

30. The method of claim 1, wherein the first message comprises a sequence of frames.

31. The method of claim 1, wherein the first message comprises a sequence of cells.

32. At least one computer readable medium encoded with instructions that, when executed, perform a method of transmitting data from a sending network node over a network comprising a plurality of nodes including the sending network node, at least some of the plurality of nodes being coupled by a broadcast medium, wherein the sending network node has a queue of messages to be transmitted, the queue including a first message received from a first previous hop and a second message received from a second previous hop, and wherein the method comprises acts of:

identifying the first message to be transmitted from the sending network node to a first destination node via a first network node;

identifying the second message to be transmitted from the sending network node to a second destination node via a second network node, wherein the second network node is not the first previous hop;

determining whether the first network node stores the second message;

determining whether the second network node stores the first message;

if it is determined that the first network node stores the second message and the second network node stores the first message, coding together the first and second messages to generate an encoded message; and

transmitting the encoded message over the broadcast medium.

33. The at least one computer readable medium of claim 32, wherein the method further comprises acts of:

identifying a third message in the queue to be transmitted from the sending network node to a third destination node via a third network node;

determining whether the first and second network nodes store the third message;

determining whether the third network node stores the first and second messages; and

when it is determined that the first and second network nodes store the third message and the third network node stores the first and second messages, coding together the first, second, and third messages to generate the encoded message.

34. The at least one computer readable medium of claim 32, wherein the network is a wireless network and the broadcast medium is air.

35. The at least one computer readable medium of claim 32, wherein the broadcast medium includes at least one network cable.

36. The at least one computer readable medium of claim 32, wherein each of the plurality of nodes is a processor in a parallel computer and the broadcast medium includes at least one communication bus.

37. The at least one computer readable medium of claim 32, wherein the first destination node and the first network node are different nodes.

38. The at least one computer readable medium of claim 32, wherein the first destination node and the first network node are the same node.

39. The at least one computer readable medium of claim 32, wherein the second destination node and the second network node are different nodes.

40. The at least one computer readable medium of claim 32, wherein the second destination node and the second network node are the same node.

41. The at least one computer readable medium of claim 32, wherein the first and second destination nodes are different nodes.

42. The at least one computer readable medium of claim 32, wherein the first and second destination nodes are the same node.

43. The at least one computer readable medium of claim 32, wherein the first and second network nodes are different nodes.

44. The at least one computer readable medium of claim 32, wherein the act of coding together the first and second messages to generate the encoded message further comprises an act of XORing the first and second messages to generate the encoded message.

45. The at least one computer readable medium of claim 32, wherein the act of coding together the first and second messages to generates the encoded message further comprises an act of computing linear combinations of the first and second messages over a finite field to generate the encoded message.

46. The at least one computer readable medium of claim 32, wherein the method further comprises an act of:

scheduling a retransmission of the first message to occur if an acknowledgment of receipt of the first message by the first network node is not received within a predetermined period of time.

47. The at least one computer readable medium of claim 32, wherein the method further comprises an act of:

scheduling a retransmission of the second message to occur if an acknowledgment of receipt of the second message by the second network node is not received within a predetermined period of time.

48. The at least one computer readable medium of claim 32, wherein the sending network node includes a message pool in which messages received over the network are temporarily stored, and wherein the method further comprises an act of:

including in the encoded message a reception report that identifies at least a portion of the messages stored in the message pool of the sending network node.

49. The at least one computer readable medium of claim 32, wherein the act of determining whether the first network node stores the second message further comprises an act of:

determining whether the first network node stores the second message using a reception report received from the first network node that identifies at least some of the messages stored by the first network node.

50. The at least one computer readable medium of claim 32, wherein the act of determining whether the second network node stores the first message further comprises an act of:

determining whether the first network node stores the second message using a reception report received from the first network node that identifies at least some of the messages stored by the first network node.

51. The at least one computer readable medium of claim 32, wherein the act of determining whether the first network node stores the second message further comprises an act of:

probabilistically determining whether the first network node stores the second message.

52. The at least one computer readable medium of claim 32, wherein the act of determining whether the second network node stores the first message further comprises an act of:

probabilistically determining whether the second network node stores the first message.

53. The at least one computer readable medium of claim 32, wherein the act of determining whether the first network node stores the second message further comprises an act of:

determining whether the first network node is capable of computing the second message.

54. The at least one computer readable medium of claim 32, wherein the method further comprises acts of:

receiving the encoded message at the first network node; and

decoding the encoded message at the first network node using the second message to obtain the first message.

55. The at least one computer readable medium of claim 54, wherein the act of decoding the encoded message further comprises an act of:

XORing the encoded message and the second message.

56. The at least one computer readable medium of claim 54, wherein the method further comprises an act of:

adding the first message to a message pool on the first network node.

57. The at least one computer readable medium of claim 32, wherein the first message comprises at least a portion of a packet.

58. The at least one computer readable medium of claim 32, wherein the first message comprises at least a portion of a frame.

59. The at least one computer readable medium of claim 32, wherein the first message comprises at least a portion of a cell.

60. The at least one computer readable medium of claim 32, wherein the first message comprises a sequence of packets.

61. The at least one computer readable medium of claim 32, wherein the first message comprises a sequence of frames.

62. The at least one computer readable medium of claim 33, wherein the first message comprises a sequence of cells.

63. A sending network node adapted for use in a network comprising a plurality of nodes including the sending network node, at least some of the plurality of nodes being coupled by a broadcast medium, wherein the sending network node has a queue of messages to be transmitted, the queue including a first message received from a first previous hop and a second message received from a second previous hop, and wherein the sending network node comprises:

at least one output; and

at least one controller, coupled to the output, that;

identifies the first message to be transmitted to a first destination node via a first network node;

identifies the second message to be transmitted from to a second destination node via a second network node, wherein the second network node is not the first previous hop;

determines whether the first network node stores the second message;

determines whether the second network node stores the first message;

if it is determined that the first network node stores the second message and the second network node stores the first message, codes together the first and second messages to generate an encoded message; and

transmits the encoded message, via the output, over the broadcast medium.

64. The sending network node of claim 63, wherein the at least one controller:

identifies a third message in the queue to be transmitted from the sending network node to a third destination node via a third network node;

determines whether the first and second network nodes store the third message;

determines whether the third network node stores the first and second messages; and

when it is determined that the first and second network nodes store the third message and the third network node stores the first and second messages, codes together the first, second, and third messages to generate the encoded message.

65. The sending network node of claim 63, wherein the network is a wireless network and the broadcast medium is air.

66. The sending network node of claim 63, wherein the broadcast medium includes at least one network cable.

67. The sending network node of claim 63, wherein each of the plurality of nodes is a processor in a parallel computer and the broadcast medium includes at least one communication bus.

68. The sending network node of claim 63, wherein the first destination node and the first network node are different nodes.

69. The sending network node of claim 63, wherein the first destination node and the first network node are the same node.

70. The a sending network node of claim 63, wherein the second destination node and the second network node are different nodes.

71. The sending network node of claim 63, wherein the second destination node and the second network node are the same node.

72. The sending network node of claim 63, wherein the first and second destination nodes are different nodes.

73. The sending network node of claim 63, wherein the first and second destination nodes are the same node.

74. The sending network node of claim 63, wherein the first and second network nodes are different nodes.

75. The sending network node of claim 63, wherein the at least one controller generates the encoded message by XORing the first and second messages to generate the encoded message.

76. The sending network node of claim 63, wherein the at least one controller generates the encoded message by computing linear combinations of the first and second messages over a finite field to generate the encoded message.

77. The sending network node of claim 63, wherein the at least one controller:

schedules a retransmission of the first message to occur if an acknowledgment of receipt of the first message by the first network node is not received within a predetermined period of time.

78. The sending network node of claim 63, wherein the at least one controller:

schedules a retransmission of the second message to occur if an acknowledgment of receipt of the second message by the second network node is not received within a predetermined period of time.

79. The sending network node of claim 63, wherein the at least one controller:

maintains a message pool in which messages received over the network are temporarily stored; and

includes in the encoded message a reception report that identifies at least a portion of the messages stored in the message pool.

80. The sending network node of claim 63, wherein the at least one controller determines whether the first network node stores the second message using a reception report received from the first network node that identifies at least some of the messages stored by the first network node.

81. The sending network node of claim 63, wherein the at least one controller determines whether the first network node stores the second message using a reception report received from the first network node that identifies at least some of the messages stored by the first network node.

82. The sending network node of claim 63, wherein the at least one controller probabilistically determines whether the first network node stores the second message.

83. The sending network node of claim 63, wherein the at least one controller probabilistically determines whether the second network node stores the first message.

84. The sending network node of claim 63, wherein the at least one controller determines whether the first network node stores the second message by determining whether the first network node is capable of computing the second message.

85. The sending network node of claim 63, wherein the first message comprises at least a portion of a packet.

86. The sending network node of claim 63, wherein the first message comprises at least a portion of a frame.

87. The sending network node of claim 63, wherein the first message comprises at least a portion of a cell.

88. The sending network node of claim 63, wherein the first message comprises a sequence of packets.

89. The sending network node of claim 63, wherein the first message comprises a sequence of frames.

90. The sending network node of claim 63, wherein the first message comprises a sequence of cells.

91. A method of transmitting data in a parallel computer comprising a plurality of processors including a sending processor, at least some of the plurality of processors being coupled by a communication bus, wherein the method comprises acts of:

identifying a first message to be transmitted from the sending processor to a first destination processor in the plurality of processors;

identifying a second message to be transmitted from the sending processor to a second destination processor in the plurality of processors;

determining whether the first destination processor stores the second message;

determining whether the second destination processor stores the first message;

if it is determined that the first destination processor stores the second message and the second destination processor stores the first message, coding together the first and second messages to generate an encoded message; and

transmitting the encoded message over the communication bus.

92. A method of processing data at a receiving network node, the data being transmitted from a sending network node to the receiving network node over a network comprising a plurality of nodes including the receiving network node and the sending network node, at least some of the plurality of nodes being coupled by a broadcast medium, wherein the method comprises acts of:

receiving, at the receiving network node, a first message from the sending network node, wherein the intended destination of the first message is a node different from the receiving network node, and wherein the first message includes information identifying messages stored by the sending network node;

using the information to determine, at the receiving network node, whether the sending network node stores a second message;

if it is determined that the sending network node stores the second message, coding together, at the receiving network node, the second message and a least one message not stored by the sending network node to generate an encoded message; and

sending the encoded message to the sending network node.

93. A method of processing data at a receiving network node, the data being transmitted from a sending network node to the receiving network node over a network comprising a plurality of nodes including the receiving node and the sending node, at least some of the plurality of nodes being coupled by a broadcast medium, wherein the method comprises acts of:

receiving, at the receiving network node, a first message from the sending network node, wherein the intended destination of the first message is a node different from the receiving network node;

storing the first message at the receiving network node;

receiving, at the receiving network node, an encoded message, wherein the receiving network node is an intended destination of the encoded message; and

using the first message to decode the encoded message to obtain a second message.