Combining multi-hop and multicast wireless networking in classroom-like settings

• US 20020196789A1
• Filed: 11/16/2001
• Published: 12/26/2002
• Est. Priority Date: 05/15/2001
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Patton, Charles
• Granted Patent: US 7,116,661 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 1/188 Time-out mechanisms
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

Described are a system and method of transmitting packets over a network having a plurality of nodes. A multicast packet is received by one of the nodes. For a period of time, that one node counts the number of retransmissions of the multicast packet that the node receives from one or more other nodes in the network. When the period of time elapses, the node retransmits the multicast packet if the number of counted retransmissions is less than a predetermined number.

Claims

1. In a network including a plurality of nodes, a method of transmitting packets over the network, comprising:

receiving a multicast packet by one of the nodes;

counting for a period of time by the one node a number of retransmissions of the multicast packet received from one or more other nodes in the network; and

retransmitting the multicast packet by the one node if the number of counted retransmissions when the period of time elapses is less than a predetermined number.

2. The method of claim 1 further comprising assigning the period of time to the one node.

3. The method of claim 1 further comprising assigning a different period of time to each node in the network.

4. The method of claim 3 further comprising periodically reassigning the periods of time among the nodes in the network to distribute evenly how long each node counts retransmission.

5. The method of claim 1 further comprising randomly determining the period of time for counting retransmissions.

6. The method of claim 5 wherein the step of randomly determining the period of time for counting retransmissions occurs for each different multicast packet received by the one node.

7. The method of claim 1 further comprising transmitting by the one node a multicast query and counting a number of responses received in reply to the multicast query to determine the predetermined number.

8. The method of claim 7 wherein the multicast query is an Internet Protocol (IP) multicast query.

9. The method of claim 7 further comprising:

receiving the multicast query at a neighboring node; and

issuing by the neighboring node a response to the multicast query during a time slot unless another response to the multicast query is received by the neighboring node before the time slot occurs.

10. The method of claim 9 further comprising assigning the time slot to the neighboring node.

11. The method of claim 9 further comprising assigning a different time slot to each node in the network.

12. The method of claim 11 further comprising periodically reassigning the time slots among the nodes in the network to evenly distribute when each node responds to multicast queries.

13. The method of claim 9 further comprising randomly determining by the neighboring node the time slot in which to respond to a multicast query.

14. The method of claim 1 wherein each of the nodes communicates with another node in the network by a wireless link.

15. The method of claim 1 wherein the plurality of nodes are located within one room.

16. The method of claim 1 further comprising determining not to re-transmit the multicast packet if a context associated with the multicast packet fails to satisfy a criterion.

17. The method of claim 1 wherein the multicast packet has a multicast address, and further comprising binding a context to the multicast address in the multicast packet.

18. The method of claim 17 wherein the multicast packet has a multicast address and each node in the network can transmit packets to the multicast address and receive packets addressed to the multicast address.

20. The network node of claim 19 further comprising means for assigning the period of time to the computing device.

21. The network node of claim 20 wherein the means for assigning periodically reassigns the period of time to vary how long the computing device counts retransmission.

22. The network node of claim 20 wherein the means for assigning randomly determines the period of time for counting retransmissions.

23. The network node of claim 20 wherein the means for assigning assigns the period of time for counting retransmissions for each different multicast packet received by the computing device.

24. The network node of claim 19 wherein the transmitter transmits a multicast query and further comprising a second counter counting a number of responses received in reply to the multicast query to determine the predetermined number.

25. The network node of claim 24 wherein the multicast query is an Internet Protocol (IP) multicast query.

26. The network node of claim 24 further comprising a receiver receiving a multicast query from a neighboring node;

and wherein the transmitter issues a response to the multicast query during a time slot unless the receiver receives another response to the multicast query before the time slot occurs.

27. The network node of claim 26 further comprising means for assigning the time slot.

28. The network node of claim 27 wherein the means for assigning periodically reassigns the time slot to the computing to vary when the network node responds to multicast queries.

29. The network node of claim 26 wherein the means for assigning randomly determines the time slot in which to respond to a multicast query.

30. The network node of claim 19 wherein the transmitter communicates with another device by a wireless link.

31. The network node of claim 19 wherein the transmitter does not re-transmit the multicast packet if a context associated with the multicast packet fails to satisfy a criterion.

32. The network node of claim 19 wherein the multicast packet has a multicast address, and further comprising means for binding a context to the multicast address in the multicast packet.

52. The network of claim 1 wherein the plurality of nodes are located within one room.

53. The network of claim 1 further comprising means for determining whether to re-transmit the multicast packet based on a context associated with the multicast packet.

19. A network node comprising:

a receiver receiving a multicast packet over a network;

a counter counting for a period of time a number of retransmissions of the multicast packet received over the network from one or more other nodes in the network; and

a transmitter retransmitting the multicast packet if the number of counted retransmissions when the period of time elapses is less than a predetermined number.

33. A computing device comprising:

means for generating a number representing a local connectivity of a network with respect to the computing device;

a receiver receiving at least one copy of a packet over the network;

means for selecting a time period in which to retransmit the packet over the network; and

a transmitter transmitting the packet over the network if the number of copies of the packet received by the receiver when the period of time arrives is less than the local connectivity number.

34. The computing device of claim 33 wherein the means for generating the local connectivity number comprises means for issuing a query over the network.

35. The computing device of claim 33 further comprising means for determining a time slot in which to respond to a query received over the network, and means for responding to the query in the time slot if the receiver has received over the network fewer than one response to the query when the time slot occurs.

36. The computing device of claim 33 further comprising:

means for associating a multicast address with a particular context; and

means for designating the packet for retransmission if a multicast address in the packet is associated with the particular data context, otherwise for non-retransmission if the multicast address in the packet is unassociated with the particular context.

38. The network of claim 37, wherein the transceiver is a RF (radio frequency) transceiver.

39. The network of claim 37, wherein the transceiver is an IR (infrared) transceiver.

40. The network of claim 37 further comprising means for assigning the period of time to the one node.

41. The network of claim 37 further comprising means for assigning a different period of time to each node in the network.

42. The network of claim 41 wherein the means for assigning periodically reassign the periods of time among the nodes in the network to distribute evenly how long each node counts retransmission.

43. The network of claim 37 further comprising means for randomly determining the period of time for counting retransmissions.

44. The network of claim 43 wherein the means for randomly determining the period of time for counting retransmissions occurs for each different multicast packet received by the one node.

45. The network of claim 37 wherein the transceiver of the one node transmits a multicast query and counts a number of responses received in reply to the multicast query to determine the predetermined number.

46. The network of claim 45 wherein the multicast query is an Internet Protocol (IP) multicast query.

47. The network of claim 37 wherein the transceiver receives a multicast query from another node in the network and transmits a response to the multicast query during a time slot unless another response to the multicast query is received before the time slot occurs.

48. The network of claim 47 further comprising means for assigning the time slot.

49. The network of claim 47 further comprising means for assigning a different time slot to each node in the network.

50. The network of claim 49 further comprising means for periodically reassigning the time slots among the nodes in the network to evenly distribute when each node responds to multicast queries.

51. The network of claim 47 further comprising means for randomly determining the time slot in which to respond to a multicast query.

54. The network of claim 37 wherein the multicast packet has a multicast address, and further comprising means for binding a context to the multicast address in the multicast packet.

55. The network of claim 54 wherein the multicast packet has a multicast address and each node in the network can transmit packets to the multicast address and receive packets addressed to the multicast address.

37. A network, comprising:

a plurality of nodes connected by a communication medium, one of the nodes having a transceiver that receives a multicast packet over the communication medium, that one node further comprising a counter counting for a period of time a number of retransmissions of the multicast packet that the transceiver receives from one or more of the other nodes in the network, wherein the transceiver retransmits the multicast packet over the communication medium if the number of counted retransmissions when the period of time elapses is less than a predetermined number.

56. An article of manufacture having computer-readable program means embodied thereon for transmitting packets over a network, the article of manufacture comprising:

computer-readable program means for receiving a multicast packet;

computer-readable program means for counting for a period of time a number of retransmissions of the multicast packet received from one or more other nodes in the network; and

computer-readable program means for retransmitting the multicast packet if the number of counted retransmissions when the period of time elapses is less than a number of groups of neighbor nodes.

57. A method of propagating information over a network having a plurality of nodes, the method comprising:

receiving a multicast packet over a network communication medium by one of the nodes; and

determining by that one node without using route information whether to retransmit the multicast packet over the network communication medium.

58. A networked node, comprising:

a receiver receiving a multicast packet over a communication medium; and

a channel manager determining whether to retransmit the multicast packet over the communication medium without using route information.