US4979168A — Dynamic sensing point CSMA packet switching contr…

Claim 1

Independent Claim 139 words

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.

Claim 2

Dependent Claim 139 words

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.

Claim 3

Dependent Claim 27 words

A system as claimed in claim 1 comprising estimating means for estimating E=the average idle period and wherein G.sub.n-l =(E[l(I)]-a).sup.-l where a=the switching time of a station.

Claim 4

Dependent Claim 31 words

A system as claimed in claim 2, wherein the average idle period length E[l(I)]=SI/NI where SI=the current sum of the lengths of the idle periods and NI=the number of idle periods.

Claim 5

Dependent Claim 48 words

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.

Claim 6

Dependent Claim 43 words

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.

Claim 7

Dependent Claim 105 words

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

Claim 8

Dependent Claim 107 words

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

Claim 9

Dependent Claim 86 words

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.

Claim 10

Dependent Claim 60 words

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 2 =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.

Claim 11

Dependent Claim 36 words

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 2 +l+2a-δ where l=the transmission time of an information packet.

Claim 12

Dependent Claim 57 words

A system as claimed in claim 8, comprising means for dynamically determining the observation period U=max(2TS, U.sub.1) where TS=the current control variable, U 1 is the minimum time needed to obtain a confident estimation of G, and ##EQU37## where n m =the minimum number of idle periods to be observed to obtain a confident estimation of G.

Claim 13

Independent Claim 132 words

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

Claim 14

Independent Claim 132 words

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

Claim 15

Dependent Claim 21 words

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

Claim 16

Dependent Claim 52 words

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.

Claim 17

Dependent Claim 44 words

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.

Claim 18

Dependent Claim 24 words

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

Claim 19

Dependent Claim 134 words

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

Claim 20

Dependent Claim 144 words

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

Claim 21

Independent Claim 136 words

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.

Claim 22

Dependent Claim 59 words

A method as claimed in claim 19, comprising estimating the delay ##EQU39## between the end of the preceding idle period and the instant (t 2 ) 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.

Claim 23

Dependent Claim 30 words

A system as claimed in claim 20, comprising estimating the beginning of the next following idle period as t.sub.2 +l+2a-δ. where l is the transmission time of an information packet.

Claim 24

Dependent Claim 63 words

A method as claimed in claim 19, comprising dynamically determining the observation period (U) on the basis of U=max(2TS, U.sub.1) where TS is the current control variable, U 1 is the minimum time needed to obtain a confident estimation of G, and ##EQU40## where n m is the minimum number of idle periods to be observed to obtain a confident estimation of G.

Claim 25

Dependent Claim 212 words

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 1 , 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 1 =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.

Claim 26

Dependent Claim 212 words

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 1 , 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 1 =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.

Claim 27

Dependent Claim 35 words

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.

Claim 28

Dependent Claim 56 words

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.

Claim 29

Dependent Claim 49 words

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.

Claim 30

Dependent Claim 19 words

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

Claim 31

Dependent Claim 103 words

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

Claim 32

Dependent Claim 110 words

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

Claim 33

Dependent Claim 86 words

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.

Claim 34

Dependent Claim 60 words

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 2 =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.

Claim 35

Dependent Claim 35 words

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 t.sub.2 +l+2a-δ where l=the transmission time of an information packet.

Claim 36

Dependent Claim 62 words

A station as claimed in claim 30, 31 or 32, comprising means for dynamically determining the observation period dynamically on the basis of U=max(2TS, U.sub.1) where TS=the current control variable, and ##EQU43## the minimum time needed to obtain a confident estimation of G, where n m =the minimum number of idle periods to be observed to obtain a confident estimation of G.

Claim 37

Dependent Claim 142 words

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 1 =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.

Claim 38

Dependent Claim 142 words

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 1 =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.

Claim 39

Dependent Claim 173 words

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 1 =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.

Claim 40

Dependent Claim 173 words

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 1 =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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1993-12-17	1994-06-18	1994-12-18	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1997-12-17	1998-06-18	1998-12-18	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2001-12-17	2002-06-18	2002-12-18	$7700.00	Window Closed / Lapsed

Dynamic sensing point CSMA packet switching controller

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag