Channel access method for powerline carrier based media access control protocol

• US 7,570,656 B2
• Filed: 06/18/2001
• Issued: 08/04/2009
• Est. Priority Date: 06/18/2001
• Status: Expired due to Fees

• Current Assignee: Yitran Communications Ltd. (Allalouf Capital Ltd.)
• Original Assignee: Yitran Communications Ltd. (Allalouf Capital Ltd.)
• Inventors: Gazit, Ronen, Mushkin, Mordechai, Erez, Amir, Kacen, Yael, Raphaeli, Dan
• Primary Examiner(s): Pham; Chi H.
• Assistant Examiner(s): MEW, KEVIN D
• Application Number:
  US09/883,589
• Publication Number:
  US 20030103521A1
• Time in Patent Office: 2,969 Days
• Field of Search: 370/445, 370/447, 370/448, 370/449, 370/450, 370/455, 370/458, 370/459, 370/461, 370/462
• US Class Current: 370/445
• CPC Class Codes: H04B 2203/5408 using protocols
• CPC Class Codes: H04B 3/542 the information being in digital form
• CPC Class Codes: H04B 3/58 Repeater circuits
• CPC Class Codes: H04L 1/0002 by adapting the transmission rate
• CPC Class Codes: H04L 1/0007 by modifying the frame length
• CPC Class Codes: H04L 1/0021 in which the algorithm uses adaptive thresholds
• CPC Class Codes: H04L 1/16 in which the return channel carries supervisory signals, e.g. repetition request signals
• CPC Class Codes: H04L 1/18 Automatic repetition systems, e.g. Van Duuren systems
• CPC Class Codes: H04L 1/1848 Time-out mechanisms
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04W 74/08 Non-scheduled access, e.g. ALOHA hybrid access H04W74/02
• CPC Class Codes: H04W 76/10 Connection setup

Abstract

A novel and useful media access control (MAC) protocol that is intended for use over noisy shared media channels. The MAC protocol provides layer 2 functionality over a network using a shared medium including a backoff mechanism for CSMA/CA channel access, link addressing that reduces the overhead of long MAC addresses, a flooding scheme having controlled exposure for broadcast transmissions, multicast transmissions using selective ACKs, implementation of traffic prioritization using an adaptive backoff scheme, a second layer repeater establishment process and multi-packet transport for short packets and fragmentation for long packet transport.

Claims

1. A method of accessing a channel in a communication transceiver coupled to a communications channel, the transceiver adapted to provide carrier sense signals including a fast carrier detect (FCD) signal to predict the early start of transmission on said channel and having a high false alarm rate and a carrier detect (CD) signal having a low false alarm rate and indicating that a transmission is starting, said method comprising the steps of:

establishing a channel contention period divided into a plurality of time slots, the width of each time slot substantially equal to the time of said FCD signal;

initializing a backoff counter with a backoff count equal to a random number of time slots;

decrementing said backoff counter while said medium is idle;

suspending said backoff counter upon receipt of a FCD signal;

resuming decrementing said backoff counter upon failure of a CD signal to arrive within a CD time, said CD time proportional to a time period during which the arrival of a CD signal is expected in the event a transmission is received;

deferring transmission until a next contention period upon receipt of a CD signal; and

starting transmission upon expiration of said backoff counter.

2. The method according to claim 1, wherein termination of said current transmission session is indicated by a change in state of said channel from busy to contention.

3. The method according to claim 1, further comprising inserting a contention interframe space (CIFS) between the end of a previous transmission session and the start of said channel contention period.

4. The method according to claim 1, further comprising the step of attempting to reserve said channel upon the expiration of said backoff counter.

5. The method according to claim 1, further comprising the step of reserving said channel by sending a request to send (RTS) frame incorporating a reservation time to a destination station.

6. The method according to claim 1, further comprising the step of reserving the channel by sending a clear to send (CTS) frame incorporating a reservation time from the destination station to the source station.

7. The method according to claim 1, wherein each contention period is further divided into a plurality of contention windows each corresponding to a different priority.

8. The method according to claim 7, wherein the size of each contention window is dynamically adapted as a function of the number of stations in said network.

9. The method according to claim 8, wherein said number of stations is determined using management frames.

10. The method according to claim 8, wherein said number of stations is determined by calculating an estimate of the number of stations in said network as a function of the current size of the contention window and the time from when a station is permitted to transmit to the time it actually starts transmitting.

11. The method according to claim 1, wherein said backoff counter is suspended until arrival of a contention window having a priority corresponding to that of the transmission to be sent.

12. The method according to claim 1, wherein said step of initializing comprises choosing a random number of time slots between zero and the size of a contention window.

13. The method according to claim 1, wherein said backoff counter resumes from the count before receipt of the most recent FCD signal.

14. The method according to claim 1, wherein the failure to receive a CD signal within a CD time of receiving a FCD signal indicates that said FCD signal was a false alarm.

15. The method according to claim 1, further comprising the step of releasing said channel once reserved or decreasing a reservation counter in the event of a link failure.

16. The method according to claim 15, wherein said link failure is indicated via a frame adapted to indicate a CTS failure.

17. The method according to claim 15, wherein said link failure is indicated via a frame adapted to indicate an RTS failure.

18. The method according to claim 1, further comprising the step of releasing said channel in the event a maximum time allocated to a session has expired.

19. The method according to claim 1, further comprising the step of decrementing one or more reservation counters, each holding a reservation time wherein separate reservation counters are maintained for each session detected by a station and wherein said channel is considered released only when the reservation counter with the maximum reservation time expires.

20. A method of accessing a channel in a communication transceiver coupled to a communications channel in a network including a plurality of stations, said method comprising the steps of:

dividing contention for access to said channel into one or more contention windows each contention window assigned a priority and subdivided into a plurality of backoff time slots;

deferring zero or more contention windows until arrival of a contention window whose priority corresponds to the priority of a particular transmission;

each station wishing to transmit, initializing a backoff counter with a backoff count equal to a random number of backoff time slots;

decrementing said backoff counter while said channel is idle; and

attempting to reserve said channel upon expiration of said backoff counter.

21. The method according to claim 20, wherein the width of said backoff time slot is on the order of a carrier detect (CD) signal.

22. The method according to claim 20, wherein the width of said backoff time slot is on the order of a fast carrier detect (FCD) signal adapted to indicate that a transmission may be starting and which is generated more quickly than a carrier detect (CD) signal.

23. The method according to claim 20, further comprising the steps of:

suspending said backoff counter upon receipt of a fast carrier detect (FCD) signal;

resuming decrementing said backoff counter upon failure of a carrier detect (CD) signal to arrive within a CD time; and

deferring transmission until after the subsequent transmission upon receipt of a CD signal.

24. The method according to claim 20, wherein said step of attempting to reserve said channel comprises sending a request to send (RTS) frame incorporating a reservation time to a destination station.

25. The method according to claim 20, further comprising a step of declaring a link failure after attempting to reserve said channel a predetermined number of times.

26. The method according to claim 20, further comprising a step of increasing the size of a contention window upon failure to reserve said channel.

27. The method according to claim 20, further comprising of a step of decreasing the size of said contention window up to a minimum contention window size if the channel reservation was successful.

28. The method according to claim 20, further comprising a step of adjusting the size of each contention window as a function of the number of stations in said network.

29. A carrier sense multiple access (CSMA) based communications system wherein transmissions are preceded by a contention phase during which one or more transmitters compete for access to a channel, comprising:

means for establishing one or more contention windows, each contention window assigned a priority;

means for dividing each contention window into a plurality of backoff time slots wherein detection of a carrier sense signal during a time slot potentially indicates that said channel is busy;

backoff means adapted to count using a backoff timer a randomly selected backoff time equal to a multiple of said backoff time slots; and

reservation means adapted to attempt reservation of said channel upon expiration of said backoff timer and to enable transmission upon successful reservation of said channel.

30. The system according to claim 29, wherein said backoff means comprises:

means for suspending said backoff timer during backoff time slots wherein a fast carrier detect (FCD) signal is detected;

resuming said backoff timer during backoff time slots wherein no FCD signal is received; and

deferring transmission to a subsequent contention phase upon receipt of a carrier detect (CD) signal within a CD time of receipt of a FCD signal, wherein said CD time is proportional to a time period during which the arrival of a CD signal is expected in the event a transmission is received.

31. The system according to claim 30, wherein said FCD signal is detected faster than said CD signal.

32. The system according to claim 30, wherein said FCD signal has a higher false alarm rate than said CD signal.

33. The system according to claim 30, wherein said backoff means comprises means for restarting a transmission session upon receipt of a CD signal.

34. The system according to claim 30, wherein said backoff timer is adapted to generate a new random backoff time in response to said transmission session being deferred.

35. The system according to claim 30, wherein said backoff timer is adapted to continue counting from a point at which said backoff timer was previously stopped upon said transmission session being resumed.

36. The system according to claim 29, wherein said reservation means is adapted to send a request to send (RTS) frame incorporating a reservation time to a destination station.

37. The system according to claim 29, wherein said reservation means is adapted to send a clear to send (CTS) frame incorporating a reservation time from the destination station to the source station.

38. The system according to claim 29, wherein said means for dividing each contention window comprises adjustment means adapted to adjust the size of each contention window as a function of the number of stations contending for the channel in said contention window.

39. The system according to claim 38, wherein said number of stations is determined using management frames.

40. The system according to claim 38, wherein said number of stations is determined using means for calculating an estimate of the number of stations in said network as a function of the current size of the contention window and the time from when a station is permitted to transmit to the time it actually starts transmitting.

41. The system according to claim 29, further comprising means for releasing said channel once reserved in the event of a link failure.

42. The system according to claim 41, wherein said link failure is indicated via a frame adapted to indicate a CTS failure.

43. The system according to claim 41, wherein said link failure is indicated via a frame adapted to indicate an RTS failure.

44. The system according to claim 41, wherein said link failure is indicated via a frame adapted to indicate an ACK failure.

45. The system according to claim 29, further comprising means for releasing said channel in the event a maximum time allocated to a session has expired.

46. The system according to claim 29, further comprising means for decrementing one or more reservation counters, each holding a reservation time wherein separate reservation counters are maintained for each session detected by a station and wherein said channel is considered released only when the reservation counter with the maximum reservation time expires.

47. A communications transceiver for transmitting and receiving over a carrier sense multiple access (CSMA) frame based communications network wherein frame transmissions are separated by a contention interframe space (CIFS) during which one or more nodes compete for access to said network, comprising:

a coupling circuit for generating a receive signal received over said network and for outputting a transmit signal onto said network;

a transmitter adapted to modulate data to be transmitted in accordance with a modulation scheme so as to generate said transmit signal therefrom;

a receiver adapted to demodulate said receive signal in accordance with said modulation scheme so as to generate a receive data signal therefrom and adapted to generate carrier sense signals including a fast carrier detect (FCD) signal having a high false alarm rate and predicting early on when a transmission may be starting and a carrier detect (CD) signal having a low false alarm rate and indicating that a transmission is starting;

a media access control (MAC) comprising means adapted to;

establish one or more contention windows wherein each contention window is assigned a priority and subdivided into a plurality of backoff time slots;

defer zero or more contention windows until arrival of a contention window whose priority corresponds to the priority of a particular transmission;

initialize a backoff counter with a backoff count equal to a random number of backoff time slots;

decrement said backoff counter while said channel is idle;

attempt to reserve said channel upon expiration of said backoff counter;

transmit onto said channel upon successfully reserving said channel; and

a processor adapted to control the operation of said transmitter, receiver and MAC and to provide an interface between said MAC and an external host.

48. The transceiver according to claim 47, wherein termination of said current transmission session is indicated by a change in state of said channel from busy to idle.

49. The transceiver according to claim 47, wherein said MAC means is adapted to insert a contention interframe space (CIFS) between the end of a previous transmission session and the start of said channel contention period.

50. The transceiver according to claim 47, wherein reserving said channel comprises sending a request to send (RTS) frame incorporating a reservation time to a destination station.

51. The transceiver according to claim 47, wherein the size of each of said one or more contention windows is dynamically adjusted as a function of the number of stations in said network.

52. The transceiver according to claim 51, wherein said number of stations is determined using management frames.

53. The transceiver according to claim 51, wherein said number of stations is determined using means for calculating an estimate of the number of stations in said network as a function of the current size of the contention window and the time from when a station is permitted to transmit to the time it actually starts transmitting.

54. The transceiver according to claim 47, wherein said backoff counter is suspended until arrival of a contention window having a priority corresponding to that of the transmission to be sent.

55. The transceiver according to claim 47, wherein said step of initializing comprises choosing a random number of time slots between zero and the size of a contention window.

56. The transceiver according to claim 47, wherein said backoff counter resumes from the count before receipt of a most recent fast carrier detect (FCD) signal.

57. The transceiver according to claim 47, wherein the failure to receive a carrier detect (CD) signal within a CD time of receiving a fast carrier detect (FCD) signal indicates that said FCD signal was a false alarm.

58. A computer readable storage medium having a computer program embodied thereon for causing a suitably programmed system to access a channel in a carrier sense multiple access (CSMA) frame based communications system wherein frame transmissions are separated by a contention interframe space (CIFS) during which one or more transmitters compete for access to said channel by performing the following steps when such program is executed on said system:

establishing one or more contention windows, wherein each contention window is assigned a priority and subdivided into a plurality of backoff time slots;

deferring zero or more contention windows until arrival of a contention window whose priority corresponds to the priority of a particular transmission;

initializing a backoff counter with a backoff count equal to a random number of backoff time slots;

decrementing said backoff counter while said channel is idle;

attempting to reserve said channel upon expiration of said backoff counter; and

transmitting onto said channel upon successful reservation of said channel.

59. The computer readable storage medium according to claim 58, wherein the width of said backoff time slot is on the order of a carrier detect (CD) signal.

60. The computer readable storage medium according to claim 59, wherein said CD signal is generated a relatively long time after the start of transmission, has a low false alarm rate and indicates that a transmission is starting.

61. The computer readable storage medium according to claim 58, wherein the width of said backoff time slot is on the order of a fast carrier detect (FCD) signal.

62. The computer readable storage medium according to claim 61, wherein said FCD signal is generated relatively shortly after the start of transmission, has a high false alarm rate and indicates that a transmission may be starting.

63. The computer readable storage medium according to claim 58, further comprising the steps of:

suspending said backoff counter upon receipt of a fast carrier detect (FCD) signal;

resuming decrementing said backoff counter upon failure of a carrier detect (CD) signal to arrive within a CD time, said CD time being proportional to a time period during which the arrival of a CD signal is expected in the event a transmission is received; and

deferring transmission until after the subsequent transmission upon receipt of a CD signal.

64. The computer readable storage medium according to claim 63, wherein said FCD signal is generated more quickly after transmission than said CD signal.

65. The computer readable storage medium according to claim 63, wherein said FCD signal has a higher false alarm rate than said CD signal.

66. The computer readable storage medium according to claim 63, wherein said CD signal has a higher probability of detection than said FCD signal.

67. The computer readable storage medium according to claim 58, further comprising the step of subsequently restarting a transmission session upon receipt of a carrier detect (CD) signal.

68. The computer readable storage medium according to claim 58, wherein the size of each said one or more contention windows is dynamically adjusted as a function of the number of stations in said network.

69. The computer readable storage medium according to claim 68, wherein said number of stations is determined using management frames.

70. The computer readable storage medium according to claim 68, wherein said number of stations is determined using means for calculating an estimate of the number of stations in said network as a function of the current size of the contention window and the time from when a station is permitted to transmit to the time it actually starts transmitting.

71. The computer readable storage medium according to claim 58, wherein said step of transmitting comprises the step of sending a request to send (RTS) frame incorporating a reservation time to a destination station.

72. The computer readable storage medium according to claim 58, wherein said step of transmitting comprises sending a clear to send (CTS) frame incorporating a reservation time from the destination station to the source station.

73. The computer readable storage medium according to claim 58, further comprising the step of releasing said channel once reserved in the event of a link failure.

74. The computer readable storage medium according to claim 73, wherein said link failure is indicated via a frame adapted to indicate a CTS failure.

75. The computer readable storage medium according to claim 73, wherein said link failure is indicated via a frame adapted to indicate an RTS failure.

76. The computer readable storage medium according to claim 58, further comprising the step of releasing said channel in the event a maximum time allocated to a session has expired.

77. The computer readable storage medium according to claim 58, further comprising the step of decrementing one or more reservation counters, each holding a reservation time wherein separate reservation counters are maintained for each session detected by a station and wherein said channel is considered released only when the reservation counter with the maximum reservation time expires.

78. A method of accessing a communications channel in a network including a plurality of stations, said method comprising the steps of:

establishing one or more contention windows in which said plurality of stations compete for access to said communications channel;

assigning a different priority to each of said one or more contention windows;

each station wishing to transmit, initializing a backoff counter with a backoff count equal to a random number of backoff time slots;

waiting until the arrival of a contention window having a priority corresponding to the priority of transmission of a particular station and upon the arrival thereof decrementing said backoff counter while said channel is idle; and

attempting to reserve said communications channel upon expiration of said backoff counter.

79. The method according to claim 78, wherein the size of said contention windows is increased upon a failure by a station to reserve said communications channel.

80. The method according to claim 78, wherein the size of said contention windows is decreased upon the successful reservation of said communications channel by a station.

81. A method of accessing a communications channel in a network including a plurality of stations, said method comprising the steps of:

establishing one or more contention windows during which said plurality of stations compete for access to said communications channel;

assigning a priority to each of said one or more contention windows;

each station wishing to transmit, initializing a backoff counter with a backoff count equal to a random number of backoff time slots;

waiting until the arrival of a contention window having a priority corresponding to the priority of transmission of a particular station and upon the arrival thereof decrementing said backoff counter while said channel is idle;

attempting to reserve said channel upon expiration of said backoff counter; and

adjusting the size of a contention window as a function of a number of said plurality of stations contending for said communications channel in said contention window.

82. The method according to claim 81, wherein the size of said contention windows is increased upon a failure by a station to reserve said communications channel.

83. The method according to claim 81, wherein the size of said contention windows is decreased increased upon the successful reservation of said communications channel by a station.

84. The method according to claim 81, wherein said number of said plurality of stations contending for said communications channel is estimated in accordance with the following

$N_{\mathrm{estimated}}=\frac{\mathrm{CW}}{t}-1$

where the expected value of t is given by

$E$

[ t ] = CW N + 1

and wherein CW is the contention window within which each station randomly selects a backoff value, N is the number of stations contending for said communications channel at any given time, t is the actual time from the moment the stations are allowed to transmit until one station starts transmitting and E[t] is the expected value of t.

85. A method of accessing a communications channel in a power line carrier based network including a plurality of stations, said method comprising the steps of:

establishing one or more contention windows in which said plurality of stations compete for access to said communications channel;

assigning a different priority to each of said one or more contention windows;

each station sensing said communication channel for the presence of carrier signal;

each station wishing to transmit, selecting a random backoff time and initializing a backoff counter with said backoff time;

each station waiting until the arrival of a contention window having a priority associated therewith corresponding to the priority of transmission of a particular station;

within the contention window having matching priority, waiting a random backoff time;

upon expiration of said backoff counter, attempting to reserve said communications channel; and

suspending countdown of said backoff counter if presence of carrier signal is detected.

86. A method of accessing a communications channel in a network including a plurality of stations, said method comprising the steps of:

establishing one or more contention windows in which said plurality of stations compete for access to said communications channel, each contention window corresponding to a different priority level;

each station wishing to transmit, initializing a backoff counter with a backoff count equal to a random number of backoff time slots;

waiting until the arrival of a contention window corresponding to a particular transmission priority, and upon the arrival thereof˜

decrementing said backoff counter while said channel is idle;

attempting to reserve said channel upon expiration of said backoff counter;

declaring the existence of a hidden station after a predetermined number of failed attempts to reserve said communications channel; and

in accordance therewith, increasing the width of said backoff time slot and repeating said steps of initializing, waiting and attempting to reserve said communications channel.

87. A method of accessing a communications channel in a network including a plurality of stations, said method comprising the steps of:

segmenting a transmission session into a plurality of frames;

establishing one or more contention windows in which said plurality of stations compete for access to said communications channel, each contention window corresponding to a different priority level;

initializing a backoff counter with a backoff count equal to a random number of backoff time slots;

waiting until the arrival of a contention window corresponding to a particular transmission priority and, upon the arrival thereof, decrementing said backoff counter while said channel is idle;

attempting to reserve said channel, upon expiration of said backoff counter, for a duration sufficient to transmit said plurality of frames;

transmitting said plurality of frames from a transmitting station to a receiving station; and

said receiving station transmitting an acknowledgement (ACK) reply to said transmitting station containing a plurality of ACK bits, each ACK bit indicating whether one of said frames is to be retransmitted.

88. A method of accessing a network channel by a station, said method comprising the steps of:

providing a fast carrier detect (FCD) signal generated by a receive circuit, said FCD signal having a high false alarm rate to predict the staff of packet transmissions from other stations on said channel;

dividing contention for channel access into a plurality of N windows, each window corresponding to one of N priority levels, wherein N is a positive integer greater than zero, and wherein each window is further divided into a plurality of time slots, each time slot having a width of said FCD signal; and

contending for access to said channel only during a window whose priority is less than or equal to that of a packet awaiting transmission.

89. The method according to claim 88, further comprising the step of dynamically adapting the size of a window to match current traffic requirements in said network.

90. The method according to claim 89, wherein said window is adjusted as a function of the number of stations estimated to be transmitting on said channel in the same priority class.