Distributed Scheduling

• US 20090116461A1
• Filed: 06/04/2008
• Published: 05/07/2009
• Est. Priority Date: 06/04/2007
• Status: Active Grant

• Current Assignee: MainNet Communications Ltd., Qualcomm Atheros Incorporated (Qualcomm, Inc.)
• Original Assignee: Intellon Corporation (Qualcomm, Inc.)
• Inventors: Goldfisher, Shmuel, Geva, Erez, Yonge, Lawrence W. III, Katar, Srinivas
• Granted Patent: US 8,467,369 B2
• Time in Patent Office: Days
• US Class Current: 370/337
• 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 some stations in the network, the timing information indicating the times of existing time slots used by stations whose transmissions can be reliably received by the station collecting the timing information;

distributing the timing information to other stations in the network; and

selecting a new time slot for transmission between a first and a second station 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.

2. The method of claim 1, further comprising collecting additional information about transmissions made during the existing time slots by the stations whose 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 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.

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

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

6. 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.

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

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

9. 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.

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

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

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 scheduled to receive can be heard by the second station.

13. The method of claim 12, wherein the new time slot excludes times when stations heard by the second 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 second station to the first station.

15. The method of claim 1, wherein the new time slot is selected to overlap in time at least one existing time slot.

16. The method of claim 2, wherein the new time slot is selected to overlap in time 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 relatively low transmit power used by the station transmitting during the existing time slot.

17. 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 to be used for transmissions during the new time slot will not interfere with existing transmissions in the existing time slot.

18. 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 low signal strength of transmissions in the existing time slot.

19. 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.

20. 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.

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

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

23. 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.

24. The method of claim 23, 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.

25. The method of claim 23, 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.

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

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

28. The method of claim 1, wherein the timing information on existing time slots is transmitted to other stations in message packets.

29. The method of claim 2, wherein the timing and additional information on existing time slots is transmitted to other stations in message packets.

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

31. The method of claim 30, 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.

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

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

34. 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.

35. 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.

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

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

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

39. 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.

40. 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.

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

providing repeated beacon transmissions from a first station for coordinating transmissions among a plurality of the stations;

retransmitting from at least one second station at least some information received at the second station, including at least a portion of a received beacon transmission;

transmitting from the first station information that determines allocated time for the first station to transmit or receive transmissions; and

transmitting from a third station information that determines allocated time for the third station to transmit or receive transmissions, wherein the third station reliably receives transmissions from the second station and does not reliably receive transmissions from the first station.

42. The method of claim 41, further comprising transmitting from the second station information that is used to determine allocated time for the second station to transmit or receive transmissions.

43. The method of claim 41, wherein the information used to determine allocated time for the first station to transmit or receive transmissions is also used 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 reliably receives 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, further comprising resolving conflicts between time allocated by different stations 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 network, the method comprising:

from each of multiple stations in the network, transmitting information characterizing transmissions received by the station from other stations;

at each of multiple stations in the 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; and

at each of multiple stations in the network, determining allocated time for the 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 other stations.

52. The method of claim 51, wherein the information characterizing transmissions received by the 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, further comprising forwarding the information characterizing transmissions.

54. The method of claim 53, further comprising, at each of multiple stations in the network, determining the allocated time based on at least some of the forwarded information.

55. The method of claim 51, wherein each station in the network is separated from a first station by a number of hops over which transmissions are repeated.

56. The method of claim 55, wherein the first station determines allocated time for a first set of stations to transmit or receive transmissions over multiple hops, and remaining stations collectively determine allocated times to transmit or receive transmissions over individual hops.

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

at each of multiple stations in the network, collecting timing information about when transmissions from different stations are received or transmitted;

distributing the timing information to multiple stations in the network; and

using the distributed timing information at different stations to determine respective timing schedules for communicating with stations from which the station can reliably receive transmissions.

58. The method of claim 57, further comprises collecting information about activity at other stations that is determined based on the received transmissions.

59. The method of claim 58, wherein the information about activity at other stations comprises information about a flow of data associated with a connection between stations at the ends of a route having multiple hops over links between intermediate stations.

60. The method of claim 57, further comprising selecting time slots in the respective timing schedules for communicating between stations at the ends of a route having multiple hops over links between intermediate stations.

61. The method of claim 60, wherein there are at least as many time slots in the timing schedules as there are links on the route.

62. The method of claim 61, wherein transmissions over sequential links of the route are scheduled in respective sequential time slots.

63. The method of claim 57, wherein the timing schedules comprise time slots within at least one contention free period of a repeating schedule.

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

a first station configured to provide repeated beacon transmissions for coordinating transmissions among a plurality of the stations, and to transmit information that determines allocated time for the first station to transmit or receive transmissions;

at least one second station configured to retransmit at least some information received at the second station, including at least a portion of a received beacon transmission; and

at least one third station configured to transmit information that determines allocated time for the third station to transmit or receive transmissions, wherein the third station reliably receives transmissions from the second station and does not reliably receive transmissions from the first station.