Dynamic sensing point CSMA packet switching controller

• US 4,979,168 A
• Filed: 10/28/1988
• Issued: 12/18/1990
• Est. Priority Date: 10/30/1987
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Semal, Pierre-Nicholaas W., Courtois, Pierre-Jacques F., Scheys, Guy F. J.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Jung, Min
• Application Number:
  US07/265,363
• Time in Patent Office: 781 Days
• Field of Search: 370/85, 370/94, 370/95, 370/86, 370/85.7, 370/95.1, 370/95.3, 370/85.3, 340/825.5
• US Class Current: 370/349
• CPC Class Codes: H04W 74/085 collision avoidance

Abstract

A controlled CSMA packet switching system of a non-persistent carrier type in which in the event of a channel being sensed busy, a new sensing point is scheduled at random in a dynamically determined time interval TS_n where ##EQU1## where TS_u is the scheduling time interval that maximizes the expected throughput when all the stations compete for the channel access, TS₁ is the scheduling time interval that maximizes the expected throughput when two stations complete for the channel access, TS_n-1 is a scheduling time interval determined in a preceding (n-1)th observation interval, G_n-1 is the average offered load in the (n-1)th observation interval, and G_o is a nominal average offered load. An estimation of the average offered load G_n-1 is derived from an estimation of the average idle period length in the (n-1) observation interval. Three strategies for obtaining such an estimation when a station participates to at least one transmission in the observation interval are disclosed.

Claims

1. A controlled carrier sense multiple access (CSMA) packet switching system comprising at least two stations each of the stations comprising sensing means for sensing if a communications channel is busy;

channel control means for determining;

TS_u =the scheduling time interval that maximises the expected throughput when all the stations compete for the channel access, TS_l =the scheduling time interval that maximises the expected throughput when two stations compete for the channel access, TS_n-l =the scheduling time interval determined in a preceding (n-l)th observation interval, G_n-l =the average offered load in the (n-l)th observation interval, and G_o =the nominal average offered load;

the channel control means including scheduling means responsive to the sensing means for scheduling a new sensing point at random in a dynamically determined time interval ##EQU35## when the channel is sensed busy.

2. A system as claimed in claim 1 comprising estimating means for estimating E=the average idle period and wherein

3. A system as claimed in claim 2, wherein the average idle period length

4. A system as claimed in claim 3 wherein the estimating means comprises means for estimating the average idle period in the event of the station participating in a busy period which cannot detect the end of the preceding idle period and the beginning of the following idle period.

5. A system as claimed in claim 4, wherein said estimating means comprises means for discarding from its current estimation the idle periods which border the busy period in which its station is transmitting and for basing its estimation on only fully observed periods.

6. A system as claimed in claim 4, wherein said estimating means comprises means for integrating into its estimation an approximation of the combined length in the time domain of the idle periods immediately preceding and following the busy period in which the station transmits, said approximation being based on determining t^b (I_m)=the beginning of the preceding idle period and t^e (I_m+l)=the end of the next following idle period and upper bounding the length of the intervening busy period by (l+a) where a=the switching time and subtracting t^b (I_m) and (l+a) from t^e (I_m+l).

7. A system as claimed in claim 4, wherein the estimating means comprises means for integrating into its estimation an approximation of the combined length in the time domain of the idle periods immediately preceding and following the busy period in which the station transmits, said approximation being based on determining (T^b (I_m))=the beginning of the preceding idle period and (T^e (I_m+1))=the end of the next following idle period and estimating E[l(B)_m ]=the length of the intervening busy period in which the station transmits and subtracting t^b (I_m) and E[l(B)_m ] from t^e (I_m+1).

8. A system as claimed in claim 4, wherein the estimating means comprises means for integrating into its estimation an approximation of the length of the preceding idle period by estimating the end of the preceding idle period and subtracting the time of occurrence of the preceding idle period, and an approximation of the length of the immediately following idle period by subtracting an estimation of the beginning of the immediately following idle period from the time of occurrence of the end of the following time period.

9. A system as claimed in claim 8, wherein the estimating means comprises means for estimating the delay ##EQU36## between the end of the preceding idle period and t₂ =the time when the station having a packet for transmission found the channel idle;

where a=the receive to transmit switching time of the station and G=the load offered to the channel.

10. A system as claimed in claim 9, wherein the estimating means comprises means for estimating the beginning of the next following idle period as being t₂ +l+2a-δ

where l=the transmission time of an information packet.

11. A system as claimed in claim 8, comprising means for dynamically determining the observation period

12. A method of operating a controlled CSMA packet switching system of a non-persistent type, the system comprising at least two stations operating on at least one communication channel, comprising sensing that at least one channel is busy, and scheduling a new sensing point at random in a dynamically determined time interval TS_n where ##EQU38## where TS_u is the scheduling time interval that maximises the expected throughput when all the stations compete for the channel access, TS₁ is the scheduling time interval that maximises the expected throughput when two stations compete for the channel access, TS_n-1 is a scheduling time interval determined in a preceding (n-1)th observation interval, G_n-1 is the average offered load in the (n-1)th observation interval, and G_c is a nominal average offered load.

13. A method as claimed in claim 12, comprising dynamically updating the time interval TS_n to maximise the expected channel throughput.

14. A method as claimed in claim 12, wherein the dynamic updating of the time interval TS_n comprises estimating G_n-1 on the basis of an estimation of the average idle period length E[l(I)] during the observation interval, where G_n-1 =(E[l(I)]-a)^-1 where a is the switching time of a station.

15. A method as claimed in claim 14, wherein the estimating step comprises estimating the average idle period E[l(I)]=SI/NI, where SI is the current sum of the lengths of the idle periods and NI is the number of idle periods contributing to the current sum.

16. A method as claimed in claim 14 wherein the estimating step comprises estimating the average idle period length based on fully observed periods only.

17. A method as claimed in claim 14 comprising, in the event of a station participating in a transmission on the or one of the channels and being unable to detect the end of an immediately preceding idle period and the beginning of the next following idle period, the step of approximating the combined length in the time domain of the immediately preceding and next following idle periods and including the approximation in the estimation of E[l(I)], said approximating step comprising determining the commencement (t^b (I_m)) of the preceding idle period and the termination t^e (I_m+1)) of the next following idle period and upper bounding the length of the intervening busy period by (1+a) and subtracting t^b (I_m) and (1+a) from t^e (I_m+1).

18. A method as claimed in claim 14 comprising, in the event of a station participating in a transmission on at least one of the at least one channel and being unable to detect the end of an immediately preceding idle period and the beginning of the next following idle period, approximating the combined length in the time domain of the immediately preceding and next following idle period and including the approximation in the estimation of E[l(I)], and wherein the approximating step comprises determining the commencement (t^b (I_m)) of the immediately preceding idle period and the termination (t^e (I_m+1)) of the next following idle period and estimating the length of the intervening busy period E[l(B_m)] during which the station transmits and subtracting t^b (I_m) and E[l(B_m)] from t^e (I_m+1).

19. A method as claimed in 14 comprising, in the event of a station participating in a transmission on at least one of the at least one channel and being unable to detect the end of the immediately preceding idle period and the beginning of the next following idle period approximating the lengths of said preceding and following idle periods and the estimating step comprises including the approximations in the estimation of E[l(I)], wherein the approximation of the immediately preceding idle period is made by subtracting the time of commencement of said idle period from an estimation of the end of said idle period and the approximation of the next following idle period is made by subtracting an estimation of the time of commencement of said idle period from the time of termination of said idle period.

20. A method as claimed in claim 19, comprising estimating the delay ##EQU39## between the end of the preceding idle period and the instant (t₂) when the station having a packet for transmission found the channel idle where a is the receive to transmit switching time of the station and G is the load offered to the channel.

21. A system as claimed in claim 20, comprising estimating the beginning of the next following idle period as

22. A method as claimed in claim 19, comprising dynamically determining the observation period (U) on the basis of

23. A station for use in a non-persistent controlled CSMA packet switching system, comprising a receiver, a transmitter, switching means to switch either the receiver or the transmitter to a communications channel, sensing means connected to the switching means to sense the busy/idle state of the communication channel and to actuate the switching means to switch from the receiver to the transmitter in the event of the station having an information packet ready for transmission and the channel being sensed idle, information packet ready for transmission and the channel is sensed busy, a new sensing point is scheduled at random in a dynamically determined time interval TS_n where TS_n =min(TS_u, max(TS₁, TS_n-1. Gn-1/G_o)) channel control means for determining TS_u =the scheduling time interval that maximises the expected throughput when all the stations complete for the channel access, TS₁ =a scheduling time interval determined in a preceding (n-1)th observation interval, G_n-1 =the average offered load in the (n-1)th observation interval, and G_o =a nominal average offered load, the channel control means including scheduling means responsive to the sensing means for scheduling a new sensing point at random in a dynamically determined time interval ##EQU41## when the channel is sensed busy.

24. A station as claimed in claim 23 comprising estimating means for estimating G_n-1 =(E[l(I)]-a)^-1 where E[l(I)] is the estimator of the average idle period and a is the switching time of a station.

25. A station as claimed in claim 24, wherein said estimating means comprises averaging means for averaging the lengths of the idle periods occurring during an observation period, and the estimator of average idle period E[l(I)]=SN/NI where SI is the current sum of the lengths of the idle periods and NI is the number of idle periods.

26. A station as claimed in claim 24 in which the estimating means comprises means for estimating the average idle period in the event of the station participating in a busy period and cannot detect the end of the preceding idle period and the beginning of the following idle period.

27. A station as claimed in claim 26, wherein said estimating means bases its estimation on only fully observed periods.

28. A station as claimed in claim 26, wherein said estimating means comprises means for integrating an approximation of the combined length in the time domain of the idle periods immediately preceding and following the busy period in which the station transmits into the estimation, said approximation being based on determining the commencement (t^b (I_m)) of the preceding idle period and the termination (t^e (I_m+1)) of the next following idle period and upper bounding the length of the intervening busy period by (1+a) and subtracting t^b (I_m) and (1+a) from t^e (I_m+1).

29. A station as claimed in claim 26, wherein said estimating means comprises means for integrating an approximation of the combined length in the time domain of the idle periods immediately preceding and following the busy period in which the station transmits into its estimation, said approximation being based on determining the commencement (t^b (I_m)) of the preceding idle period and the termination (t^e (I_m+1)) of the next following idle period and estimating the length of the intervening busy period E[l(B)_m ] in which the station transmits and subtracting t^b (I_m) and E[l(B)_m ] from t^e (I_m+1).

30. A station as claimed in claim 26, wherein said estimating means comprises means for integrating an approximation of the length of the preceding idle period by estimating the end of the preceding idle period and substracting the time of occurrence of the preceding idle period, and an approximation of the length of the immediately following idle period by subtracting an estimation of the beginning of the immediately following idle period from the time of occurrence of the end of the following time period into its estimation.

31. A station as claimed in claim 30, wherein the estimating means comprises means for estimating the delay ##EQU42## between the ends of the preceding idle period and t₂ =the time when the station having a packet for transmission found the channel idle;

where a=the receive to transmit switching time of the station and G=the load offered to the channel.

32. A station as claimed in claim 31, wherein the estimating means comprises means for estimating the beginning of the next following idle period as being

33. A station as claimed in claim 30, 31 or 32, comprising means for dynamically determining the observation period dynamically on the basis of

34. A controlled carrier sense multiple access (CSMA) packet switching system comprising at least two stations each of the stations comprising sensing means for sensing of a communications channel is busy;

channel control means for determining;

TS_u =the scheduling time interval that maximises the expected throughput when all the stations compete for the channel access,

TS₁ =the scheduling time interval that maximises the expected throughput when two stations compete for the channel access,

TS_n-1 =the scheduling time interval determined in a preceding (n-1)th observation interval,

G_n-1 =the average offered load in the (n-1)th observation interval,

G_o =the nominal average offered load; and

α

=a smoothing factor

the channel control means including scheduling means responsive to the sensing means for scheduling a new sensing point at random in a dynamically determined time interval ##EQU44## when the channel is sensed busy.

35. A station for use in a non-persistent controlled CSMA packet switching system, comprising a receiver, a transmitter, switching means to switch either the receiver or the transmitter to a communications channel, sensing means connected to the switching means to sense the busy/idle state of the communication channel and to actuate the switching means to switch from the receiver to the transmitter in the event of the station having an information packet ready for transmission and the channel being sensed idle, channel control means for determining

TS_u =the scheduling time interval that maximises the expected throughput when all the stations compete for the channel access,

TS₁ =a scheduling time interval determined in a preceding (n-1)th observation interval,

G_n-1 =the average offered load in the (n-1)th observation interval,

G_o =a nominal average offered load, and

α

=a smoothing factor;

the channel control means including scheduling means responsive to the sensing means for scheduling a new sensing point at random in a dynamically determined time interval ##EQU45## when the channel is sensed busy.