Methods and apparatus for network coding
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
93 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
-
-
32. At least one non-transitory 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. - View Dependent Claims (33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62)
-
-
63. A sending network node configured 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. - View Dependent Claims (64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90)
-
-
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 an 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 at 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 an 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; andusing the first message to decode the encoded message to obtain a second message.
-
Specification