Distributed scheduling

• US 8,467,369 B2
• Filed: 06/04/2008
• Issued: 06/18/2013
• Est. Priority Date: 06/04/2007
• Status: Active Grant

• Current Assignee: MainNet Communications Ltd., Qualcomm Atheros Incorporated (Qualcomm, Inc.)
• Original Assignee: Qualcomm Atheros Incorporated (Qualcomm, Inc.)
• Inventors: Yonge, Lawrence W. III, Katar, Srinivas, Goldfisher, Shmuel, Geva, Erez
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): Ganguly, Sumitra
• Application Number:
  US12/133,270
• Publication Number:
  US 20090116461A1
• Time in Patent Office: 1,840 Days
• Field of Search: 370/254, 370/345, 370/348, 370/352, 370/335, 370/328, 370/278, 370/236, 370/401, 370/458, 370/432, 370/445, 455/67.11, 455/432
• US Class Current: 370/345
• CPC Class Codes: H04B 2203/5445 Local network
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04L 12/2856 Access arrangements, e.g. Internet access asynchronous transfer mode networks H04L12/5601; broadband local area networks H04L12/2801; optical access or distribution networks H04Q11/0067; access to open networks H04L12/5691; digital subscriber line end-user equipment and bit-level processing of data on a PSTN-based network H04M11/00; home network gateways H04L12/2834; wireless access networks H04W
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]
• CPC Class Codes: H04L 12/44 Star or tree networks
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 47/787 Bandwidth trade among domains

Abstract

In a network, some data are transmitted between stations during time slots in contention free periods. Selecting the time slots includes collecting timing information at some stations in the network. The timing information indicates the times of existing time slots used by stations whose transmissions can be reliably received by the station collecting the timing information. The timing information is distributed to other stations in the network. A new time slot for transmission between a first and a second station is selected based at least on timing information indicating the times of existing time slots used by stations whose transmissions can be reliably received by at least one of the first and second station.

Claims

1. In a network in which some data are transmitted between stations during time slots in contention free periods, a method for selecting the time slots, the method comprising:

collecting timing information at at least one of the stations in the network, the timing information indicating the times of existing time slots used by stations for inter-beacon transmissions that can be reliably received by the at least one station collecting the timing information; and

distributing the timing information to other stations in the network including a first station;

wherein a new time slot for inter-beacon transmission between the first and a second station is selectable based at least on the distributed timing information and timing information indicating the times of existing time slots used by stations whose inter-beacon transmissions can be reliably received by the first station.

2. The method of claim 1, further comprising collecting additional information about inter-beacon transmissions made during the existing time slots by the stations whose inter-beacon transmissions can be reliably received, the additional information being useful in selecting the new time slot and including at least one of information on transmit power level, information on received signal strength, and information on priority.

3. The method of claim 2, wherein the new time slot is selected to overlap in time with at least one existing time slot, and wherein processing of the additional information establishes that overlapping of the new time slot with the existing time slot can be accomplished because the transmit power level used by the station transmitting during the existing time slot is less than that used by the first or second station for transmission during the new time slot, wherein the overlapping new time slot and the at least one existing time slot allow for respective overlapping inter-beacon transmissions.

4. The method of claim 2, wherein the new time slot is selected to overlap in time with at least one existing time slot, and wherein processing of the additional information establishes that overlapping of the new time slot with the existing time slot can be accomplished because a transmit power level to be used for transmissions during the new time slot will not interfere with existing transmissions in the existing time slot, wherein the overlapping new time slot and the at least one existing time slot allow for respective overlapping inter-beacon transmissions.

5. The method of claim 2, wherein the new time slot is selected to overlap in time with at least one existing time slot, and wherein processing of the additional information establishes that overlapping of the new time slot with the existing time slot can be accomplished because of the received signal strength of transmissions in the existing time slot being less than a received signal strength of the transmissions in the new time slot, wherein the overlapping new time slot and the at least one existing time slot allow for respective overlapping inter-beacon transmissions.

6. The method of claim 2, wherein beacons contain the timing and additional information on existing time slots.

7. The method of claim 2, wherein the timing and additional information on existing time slots is transmitted to other stations in the inter-beacon transmissions.

8. The method of claim 2, wherein the information on priority comprises information on the priority of transmissions during the existing time slot.

9. The method of claim 8, wherein the new time slot is selected to overlap at least one existing time slot in which the priority of transmissions is lower than the priority of transmissions to occur during the new time slot.

10. The method of claim 9, wherein the network is a point to multi-point network and priority is based on the number of hops that inter-beacon transmission traffic belonging to the existing and new time slots is from a head end.

11. The method of claim 8, wherein the network is a point to multi-point network and priority is based on the number of hops that inter-beacon transmission traffic belonging to the existing and new time slots is from a head end.

12. The method of claim 1, wherein selecting the new time slot is also based at least on information indicating the times of existing time slots during which stations heard by the first station are receiving.

13. The method of claim 12, wherein the new time slot excludes times when stations heard by the first station are scheduled to receive other transmissions.

14. The method of claim 13, wherein the new time slot is selected at the first station for transmission from the first station to the second station.

15. The method of claim 1, wherein selecting the new time slot is also based at least on information indicating the times of existing time slots during which stations scheduled to transmit can be heard by the second station.

16. The method of claim 15, wherein the new time slot excludes times when stations heard by the second station are scheduled to transmit other transmissions.

17. The method of claim 1, wherein selecting the new time slot is also based at least on information indicating the times of existing time slots during which stations heard by first station are transmitting.

18. The method of claim 17, wherein the new time slot excludes times when stations heard by the first station are scheduled to transmit other transmissions.

19. The method of claim 18, wherein the new time slot is selected at the first station for transmission from the second station to the first station.

20. The method of claim 1, wherein selecting the new time slot is also based at least on information indicating the times of existing time slots during which stations scheduled to receive can be heard by the second station.

21. The method of claim 20, wherein the new time slot excludes times when stations heard by the second station are scheduled to receive other transmissions.

22. The method of claim 21, wherein the new time slot is selected at the first station for transmission from the second station to the first station.

23. The method of claim 1, wherein the new time slot is selected to overlap in time with at least one existing time slot, wherein the overlapping new time slot and the at least one existing time slot allow for respective overlapping inter-beacon transmissions.

24. The method of claim 1, wherein the timing information on existing time slots comprises the source and/or destination address of transmissions in the existing period.

25. The method of claim 1, wherein the network comprises a plurality of neighboring home networks, and the existing time slot is used in one neighboring home network and the new time slot is selected for use in a different neighboring home network.

26. The method of claim 1, wherein the stations in the network are configured as peers.

27. The method of claim 1, wherein the stations in the network are configured to use a point to multipoint network protocol.

28. The method of claim 1, wherein at least one of the stations is a head end station and the selection of time slots is initiated after the head end station has agreed to establish a network connection with another station in the network.

29. The method of claim 28, wherein the first station is the head end station, and the second station is a station that can be heard by the head end station.

30. The method of claim 28, wherein selecting a time slot for transmission between the second station and a third station is performed after the time slot has been chosen for transmission from the first to the second station.

31. The method of claim 1, wherein beacons contain the timing information on existing time slots.

32. The method of claim 1, wherein the timing information on existing time slots is transmitted to other stations in the inter-beacon transmissions.

33. The method of claim 1, wherein the timing information provided by a station includes at least some time periods that the station is using for contention periods.

34. The method of claim 1, wherein at least a portion of the new time slot selected comprises time intervals currently used for CSMA communication by at least the first and second stations.

35. The method of claim 1, wherein the first station is a head end of a point to multi-point network, and wherein the new time slots for multiple hops downstream from the head end are selectable by the head end, including a hop from the head end to the second station, and from the second station to a third station.

36. The method of claim 1, wherein each station in the network can reliably receive transmissions from all other stations in the network.

37. The method of claim 1, wherein at least some stations in the network cannot reliably receive transmissions from all other stations in the network.

38. The method of claim 1, wherein transmissions in the existing time slot cannot be reliably received by only one of the first and second stations.

39. The method of claim 1, wherein a first time slot is allocated for transmission from the first station to the second station and a second time slot is allocated for transmission from the second station to the first station, and the second time slot is used to send acknowledgements of previous transmissions from the first station during the first time slot.

40. The method of claim 1, wherein the network is a powerline network.

41. A method for communicating among stations in a network, the method comprising:

providing repeated beacon transmissions from a first station for coordinating inter-beacon transmissions among a plurality of the stations, wherein the repeated beacon transmissions include information regarding allocated time for the first station to transmit or receive inter-beacon transmissions,

wherein at least some information received at a second station is capable of retransmission by the second station to a third station, including at least a portion of a received beacon transmission from the first station; and

wherein information regarding allocated time for the third station to transmit or receive transmissions is based on available time slots in the retransmitted information by the second station to the third station and is capable of being transmitted by the third station, wherein the third station is configured to reliably receive transmissions from the second station but not the first station;

wherein inter-beacon transmissions from stations in the network are hierarchically determined in time based on proximity to the first station.

42. The method of claim 41, wherein information regarding allocated time for the second station to transmit or receive inter-beacon transmissions is transmittable by the second station.

43. The method of claim 41, wherein the information regarding allocated time for the first station to transmit or receive transmissions is also usable to determine allocated time for the second station to transmit or receive transmissions.

44. The method of claim 41, wherein determining allocated time for a station to transmit or receive transmissions includes determining the allocated time relative to a periodic time reference indicated in a beacon transmission.

45. The method of claim 41, wherein the second station is capable of reliably receiving transmissions from the first station.

46. The method of claim 41, wherein the first station is in communication with a fourth station over a route that includes the second station and the third station.

47. The method of claim 41, conflicts between time allocations by different stations are resolved based on proximity of the different stations to the first station.

48. The method of claim 47, wherein the proximity of a given station to the first station comprises a number of hops along a route from the first station to the given station.

49. The method of claim 47, wherein the proximity of a given station to the first station comprises a signal strength of a transmission from the first station received by the given station.

50. The method of claim 47, wherein the proximity of a given station to the first station comprises a data rate of a transmission from the first station received by the given station.

51. A method for communicating among stations in a powerline network, the method comprising:

from a first station in the powerline network, transmitting information characterizing transmissions received by the first station from other stations; and

at the first station in the powerline network, determining allocated time for the station to transmit or receive transmissions based on at least some of the information characterizing transmissions, and transmitting information indicating the allocated time;

wherein each of multiple other stations in the powerline network are capable of determining allocated time for the respective station to transmit or receive transmissions based on at least some of the information characterizing transmissions and based on at least some of the information indicating the allocated time from the first station,

wherein each station in the powerline network is separated from the first station by a number of hops over which transmissions are repeated, and wherein the first station determines allocated time for a first set of stations to transmit or receive transmissions over multiple hops, and remaining stations are configured to collectively determine allocated times to transmit or receive transmissions over individual hops.

52. The method of claim 51, wherein the information characterizing transmissions received by the first station from other stations includes at least one of:

times at which the transmissions were received, and signal strengths of the transmissions.

53. The method of claim 51, wherein at least some of the multiple other stations are capable of forwarding the information characterizing transmissions.

54. The method of claim 53, wherein each of the other multiple stations in the powerline network is capable of determining their respective allocated time based on at least some of the forwarded information.

55. A system for communicating among multiple stations, comprising:

a first station configured to provide repeated beacon transmissions for coordinating inter-beacon transmissions among a plurality of the stations, wherein the repeated beacon transmissions include information regarding allocated time for the first station to transmit or receive inter-beacon transmissions;

wherein at least some information received at a second station is retransmittable by the second station to a third station, including at least a portion of a received beacon transmission; and

wherein information regarding allocated time for the third station to transmit or receive transmissions is based on available time slots in the retransmitted information by the second station to the third station and is capable of being transmitted by the third station, wherein the third station is capable of reliably receiving transmissions from the second station but not from the first station;

wherein inter-beacon transmissions from stations in the network are hierarchically determined based on proximity to the first station.