METHOD AND APPARATUS FOR HOP-BY-HOP RELIABLE MULTICAST IN WIRELESS NETWORKS

• US 20120182860A1
• Filed: 10/06/2009
• Published: 07/19/2012
• Est. Priority Date: 10/06/2009
• Status: Active Grant

• Current Assignee: Thomson Licensing (Vantiva SA)
• Original Assignee: Illumina Incorporated
• Inventors: Liu, Hang, Dong, Lijun
• Granted Patent: US 9,215,082 B2
• Time in Patent Office: Days
• US Class Current: 370/216
• 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/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0076 Distributed coding, e.g. network coding, involving channel coding coding in both space and time H04L1/0618; cooperative diversity H04B7/022
• CPC Class Codes: H04L 1/1819 with retransmission of additional or different redundancy
• CPC Class Codes: H04L 12/1863 comprising mechanisms for improved reliability, e.g. status reports arrangements for detecting or preventing errors by carrying supervisory signal the return channel H04L1/16
• 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
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method and apparatus are described including performing hop-by-hop multicasting including network coding of data packets of a portion of content, wherein network coding further includes encoding data packets of a portion of content, multicasting said network coded data packets to downstream receivers, determining if an acknowledgement message has been received from at least one of the downstream receivers, determining if acknowledgement messages have been received from all of the downstream receivers responsive to the first determination.

Claims

1. A method, said method comprising:

performing hop-by-hop multicasting including network coding of data packets of a portion of content, wherein network coding further comprises;

encoding data packets of a portion of content;

multicasting said network coded data packets to downstream receivers;

determining if an acknowledgement message on a hop-by-hop basis has been received from at least one of said downstream receivers;

determining if acknowledgement messages on said hop-by-hop basis have been received from all of said downstream receivers responsive to said first determination; and

resending said encoded data packets if either said first or said second determining acts are negative.

2. The method according to claim 1, further comprising building a multicast tree connecting a source to said downstream receivers, wherein said multicast tree is built using an expected transmission time function to determine shortest paths connecting said source to said downstream receivers, and further wherein said shortest path multicast tree is reconstructed whenever connectivity between said source and any of said downstream receivers changes.

3. The method according to claim 1, wherein said content is divided into multiple portions, each portion having multiple data packets, before encoding.

4. The method according to claim 1, wherein each of said encoded data packets includes an identifier corresponding to said portion and a coding vector of random coefficients used to generate each of said encoded data packets.

5. The method according to claim 1, wherein link rate adaptation is also performed in said hop-by-hop multicasting, wherein said link rate adaptation further comprises:

transmitting a periodic link quality measurement request to said downstream receivers;

receiving a link measurement report from said downstream receivers;

storing said link measurement report;

determining if there are additional data packets to be multicast to said downstream receivers; and

determining a link physical layer transmission mode responsive to said first determination and said link measurement report for said downstream receivers.

6. The method according to claim 1, wherein said congestion control adaptation is also performed in said hop-by-hop multicasting, wherein said congestion control further comprises:

receiving a congestion control notification;

decreasing a transmission rate for said encoded data packets of said portion of said content by a factor, wherein said decreased transmission rate is greater than a minimum transmission rate;

increasing said transmission rate for said encoded data packets of said portion of said content by a factor, wherein said increased transmission rate is less than a maximum transmission rate if no further congestion control messages are received for a period of time.

7. The method according to claim 1, wherein adaptive scheduling adaptation is also performed in said hop-by-hop multicasting, wherein said further comprises:

updating a first table responsive to said first determination; and

removing an entry from a second table responsive to said second determination.

8. An apparatus, comprising:

means for performing hop-by-hop multicasting including means for network coding of data packets of a portion of content, wherein said means for network coding further comprises;

means for encoding data packets of a portion of content;

means for multicasting said network coded data packets to downstream receivers;

means for determining if an acknowledgement message on a hop-by-hop basis has been received from at least one of said downstream receivers;

means for determining if acknowledgement messages on said hop-by-hop basis have been received from all of said downstream receivers responsive to said first determination; and

resending said encoded data packets if either said first or said second determining acts are negative.

9. The apparatus according to claim 8, further comprising means for building a multicast tree connecting a source to said downstream receivers, wherein said multicast tree is built using an expected transmission time function to determine shortest paths connecting said source to said downstream receivers, and further wherein said shortest path multicast tree is reconstructed whenever connectivity between said source and any of said downstream receivers changes.

10. The apparatus according to claim 8, wherein said content is divided into multiple portions, each portion having multiple data packets, before encoding.

11. The apparatus according to claim 8, wherein each of said encoded data packets includes an identifier corresponding to said portion and a coding vector of random coefficients used to generate each of said encoded data packets.

12. The apparatus according to claim 8, wherein said means for hop-by-hop multicasting also includes means for link rate adaptation, wherein said means for link rate adaptation further comprises:

means for transmitting a periodic link quality measurement request to said downstream receivers;

means for receiving a link measurement report from said downstream receivers;

means for storing said link measurement report;

means for determining if there are additional data packets to be multicast to said downstream receivers; and

means for determining a link physical layer transmission mode responsive to said first determination and said link measurement report for said downstream receivers.

13. The apparatus according to claim 8, wherein said means for hop-by-hop multicasting also includes means for congestion control, wherein said means for said congestion control further comprises:

means for receiving a congestion control notification;

means for decreasing a transmission rate for said encoded data packets of said portion of said content by a factor, wherein said decreased transmission rate is greater than a minimum transmission rate;

means for increasing said transmission rate for said encoded data packets of said portion of said content by a factor, wherein said increased transmission rate is less than a maximum transmission rate if no further congestion control messages are received for a period of time.

14. The apparatus according to claim 8, wherein said means for hop-by-hop multicasting also includes means for adaptive scheduling, wherein said means for adaptive scheduling further comprises:

means for updating a first table responsive to said first determination; and

means for removing an entry from a second table responsive to said second determination.