Adaptive random access protocol for CATV networks

• US 5,956,325 A
• Filed: 10/22/1996
• Issued: 09/21/1999
• Est. Priority Date: 10/24/1995
• Status: Expired due to Term

• Current Assignee: LG Electronics, Inc. (LG Corporation)
• Original Assignee: Zenith Electronics Corporation (LG Corporation)
• Inventors: Lin, David D., Citta, Richard W., Xia, Jingsong
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US08/734,909
• Time in Patent Office: 1,064 Days
• Field of Search: 370/252, 370/322, 370/348, 370/431, 370/443, 370/447, 370/449, 370/461, 370/468, 370/477, 348/12, 348/13
• US Class Current: 370/252
• CPC Class Codes: H04J 3/1694 Allocation of channels in TDM/TDMA networks, e.g. distributed multiplexers Passive Optical Networks H04Q11/0062
• CPC Class Codes: H04L 12/2801 Broadband local area networks

Abstract

A communication system has a plurality of stations which communicate data in a data frame having a plurality of slots, wherein the plurality of slots are data slots DS and/or minislots MS. A master station determines a range parameter R which is based upon a number of slave stations transmitting reservation requests in a data frame, the master station determines a minislot parameter MP according to a number of reservation requests in a queue waiting to be processed by the master station, and the master station transmits the range parameter R and the minislot parameter MP to a plurality of slave stations. Each slave station independently determines a random transmission parameter N. Each slave station transmits a reservation request to the master station if its random transmission parameter N corresponds to the minislot parameter MP and abstains from transmitting a reservation request to the master station if its random transmission parameter N does not correspond to the minislot parameter MP.

Claims

1. A method of transmitting data between a plurality of stations comprising the steps of:

a) determining a range parameter R at a first of the stations, wherein the range parameter R is based upon a number of the stations transmitting reservation requests;

b) determining a slot parameter MP at the first station, wherein the slot parameter MP is based upon a number of reservation requests waiting to be processed;

c) transmitting the range parameter R and the slot parameter MP to others of the stations;

d) determining a transmission parameter N at the other stations which receive the range parameter R and the slot parameter MP, wherein the transmission parameter N is determined on the basis of the range parameter R;

e) transmitting a reservation request from those other stations whose transmission parameter N bears a predetermined relationship to the slot parameter MP; and

,

f) abstaining from transmitting the reservation request from those other stations whose transmission parameter N does not bear the predetermined relationship to the slot parameter MP.

2. The method of claim 1 wherein step f) comprises the step of abstaining from transmitting a reservation request from the stations which receive the range parameter R and the slot parameter MP if the transmission parameter N is between about the slot parameter MP and about the range parameter R.

3. The method of claim 1 wherein step b) comprises the steps of:

b1) if RDS(n)<

DQ(n)<

α

RDS(n), determining a minislot parameter MS based upon the following equation;

##EQU8## wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP, wherein RDS(n) is the number of data slots in a data frame at discrete time n, wherein DQ(n) is the number of reservation requests waiting to be processed at time n, wherein α

is a constant, wherein M is the number of minislots in steady state, wherein S is the number of slots in a data frame, wherein k is a number corresponding to an average number of data slots reserved by reservation requests, wherein e is 2.718281828 . . . , and wherein m is the number of minislots into which a slot of a data frame may be subdivided;

b2) if DQ(n)<

RDS(n), determining the slot parameter MP based upon the following equation;

space="preserve" listing-type="equation">MS(n+1)=m(S-DQ(n))

wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP; and

,

b3) if DQ(n)>

α

RDS(n), determining the slot parameter MP according to the following equation;

##EQU9## wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP.

4. The method of claim 1 wherein step a) comprises the following steps:

a₁) if a successful rate Psuc(n) at discrete time n is greater than about c, determining the range parameter R for discrete time n+1 according to the following equation;

##EQU10## wherein R(n) is the range parameter R at discrete time n, wherein c is a constant, and wherein Rcol(n) is based upon a number of reservation slots in which data collisions occurred at discrete time n;

a₂) if the successful rate Psuc(n) at discrete time n is not greater than about c, determining the range parameter R for discrete time n+1 according to the following equation;

##EQU11## and wherein Rsuc(n) is based upon a number of non-empty reservation slots in which data collisions did not occur at discrete time n; and

,

a₃) if R(n+1)<

MS(n+1), determining the range parameter R for discrete time n+1 according to the following equation;

space="preserve" listing-type="equation">R(n+1)=MS(n+1)

wherein R(n+1) in inequality R(n+1)<

MS(n+1) is determined by step a1) or a2) as appropriate, and MS(n+1) is the number of reservation slots in a data frame at discrete time n+1, and if R(n+1)>

MS(n+1), using R(n+1) as determined by step a1) or a2) as appropriate.

5. The method of claim 4 wherein reservation slots are minislots, wherein step b) comprises the steps of:

b1) if RDS(n)<

DQ(n)<

α

RDS(n), determining the slot parameter MP based upon the following equation;

##EQU12## wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP, wherein RDS(n) is the number of data slots in a data frame at discrete time n, wherein DQ(n) is the number of reservation requests waiting to be processed at time n, wherein α

is a constant, wherein M is the number of minislots in steady state, wherein S is the number of slots in a data frame, wherein k is a number corresponding to an average number of data slots reserved by reservation requests, wherein e is 2.718281828 . . . , and wherein m is the number of minislots into which a slot of a data frame may be subdivided;

b2) if DQ(n)<

RDS(n), determining the slot parameter MP based upon the following equation;

space="preserve" listing-type="equation">MS(n+1)=m(S-DQ(n))

wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP; and

,

b3) if DQ(n)>

α

RDS(n), determining the slot parameter MP based upon the following equation;

##EQU13## wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP.

6. The method of claim 5 wherein Rcol(n) is determined according to the following equation:

##EQU14## and wherein Rsuc(n) is determined according to the following equation;

##EQU15##

7. The method of claim 5 wherein Rcol(n) is determined from a look up table which is generated to substantially satisfy the following equation:

and wherein Rsuc(n) is determined from a look up table which is generated to substantially satisfy the following equation;

##EQU16##

8. The method of claim 5 wherein c≅

1/e.

9. The method of claim 1 wherein the others of the stations include first and second other stations, wherein step c) comprises the step of transmitting the range parameter R and the slot parameter MP to the first and second other stations, wherein step d) comprises the steps of determining a transmission parameter N₁ at the first other station and of determining a transmission parameter N₂ at the second other station, wherein the transmission parameter N₁ is a number determined on the basis of the range parameter R, wherein the transmission parameter N₂ is a number determined on the basis of the range parameter R, wherein step e) comprises the steps of transmitting a reservation request from the first other station if the transmission parameter N₁ corresponds to the slot parameter MP and of transmitting a reservation request from the second other station if the transmission parameter N₂ corresponds to the slot parameter MP, and wherein the step f) comprises the steps of abstaining from transmitting a reservation request from the first other station if the transmission parameter N₁ does not correspond to the slot parameter MP and of abstaining from transmitting a reservation request from the second other station if the transmission parameter N₂ does not correspond to the slot parameter MP parameter MP.

10. The method of claim 9 wherein the step of abstaining from transmitting a reservation request from the first other station comprises the step of abstaining from transmitting a reservation request from the first other station if the transmission parameter N₁ is between about the slot parameter MP and about the range parameter R, and wherein the step of abstaining from transmitting a reservation request from the second other station comprises the step of abstaining from transmitting a reservation request from the second other station if the transmission parameter N₂ is between about the slot parameter MP and about the range parameter R.

11. The method of claim 9 wherein step b) comprises the steps of:

b1) if RDS(n)<

DQ(n)<

α

RDS(n), determining the slot parameter MP based upon the following equation;

##EQU17## wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP, wherein RDS(n) is the number of data slots in a data frame at discrete time n, wherein DQ(n) is the number of reservation requests waiting to be processed at time n, wherein α

is a constant, wherein M is the number of minislots in steady state, wherein S is the number of slots in a data frame, wherein k is a number corresponding to an average number of data slots reserved by reservation requests, wherein e is 2.718281828 . . . , and wherein m is the number of minislots into which a slot of a data frame may be subdivided;

b2) if DQ(n)<

RDS(n), determining the slot parameter MP based upon the following equation;

space="preserve" listing-type="equation">MS(n+1)=m(S DQ(n))

wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP; and

,

b3) if DQ(n)>

α

RDS(n), determining the slot parameter MP based upon the following equation;

##EQU18## wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP.

12. The method of claim 9 wherein step a) comprises the following steps:

a₁) if a successful rate Psuc(n) at discrete time n is greater than about c, determining the range parameter R for discrete time n+1 according to the following equation;

##EQU19## wherein R(n) is the range parameter R at discrete time n, wherein c is a constant, and wherein Rcol(n) is based upon a number of reservation slots in which data collisions occurred at discrete time n;

a₂) if the successful rate Psuc(n) at discrete time n is not greater than about c, determining the range parameter R for discrete time n+1 according to the following equation;

##EQU20## and wherein Rsuc(n) is based upon a number of non-empty reservation slots in which data collisions did not occur at discrete time n; and

,

a₃) if R(n+1)<

MS(n+1), determining the range parameter R for discrete time n+1 according to the following equation;

space="preserve" listing-type="equation">R(n+1)=MS(n+1)

wherein R(n+1) in inequality R(n+1)<

MS(n+1) is determined by step a1) or a2) as appropriate, and MS(n+1) is the number of reservation slots in a data frame at discrete time n+1, and if R(n+1)>

MS(n+1), using R(n+1) as determined by step a1) or a2) as appropriate.

13. The method of claim 12 wherein reservation slots are minislots, wherein step b) comprises the steps of:

b1) if RDS(n)<

DQ(n)<

α

RDS(n), determining the slot parameter MP based upon the following equation;

##EQU21## wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP, wherein RDS(n) is the number of data slots in a data frame at discrete time n, wherein DQ(n) is the number of reservation requests waiting to be processed at time n, wherein α

is a constant, wherein M is the number of minislots in steady state, wherein S is the number of slots in a data frame, wherein k is a number corresponding to an average number of data slots reserved by reservation requests, wherein e is 2.718281828 . . . , and wherein m is the number of minislots into which a slot of a data frame may be subdivided;

b2) if DQ(n)<

RDS(n), determining the slot parameter MP based upon the following equation;

space="preserve" listing-type="equation">MS(n+1)=m(S-DQ(n))

wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP; and

,

b3) if DQ(n)>

α

RDS(n), determining the slot parameter MP based upon the following equation;

##EQU22## wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP.

14. The method of claim 13 wherein Rcol(n) is determined based upon the following equation:

##EQU23## and wherein Rsuc(n) is determined based upon the following equation;

##EQU24##

15. The method of claim 13 wherein Rcol(n) is determined from a look up table which is generated to substantially satisfy the following equation:

and wherein Rsuc(n) is determined from a look up table which is generated to substantially satisfy the following equation;

##EQU25##

16. The method of claim 13 wherein c≅

1/e.

17. A communication system having a plurality of stations which communicate data in a data frame having a plurality of slots, wherein the plurality of slots are data slots DS and/or reservation slots MS, and wherein the communication system comprises:

range parameter R determining means at a first station for determining a range parameter R;

slot parameter MP determining means at the first station for determining a slot parameter MP;

first station transmitting means at the first station for transmitting the range parameter R and the slot parameter MP to second and third stations;

transmission parameter N₁ determining means at the second station for determining a random transmission parameter N₁ within a range corresponding to the range parameter R;

transmission parameter N₂ determining means at the third station for determining a random transmission parameter N₂ within a range corresponding to the range parameter R;

second station transmitting means at the second station for transmitting a reservation request to the first station if the random transmission parameter N₁ bears a first predetermined relationship to the slot parameter MP and for abstaining from transmitting a reservation request to the first station if the random transmission parameter N₁ does not bear the first predetermined relationship to the slot parameter MP, wherein a reservation request, if any, is transmitted by the second station transmitting means in a reservation slot; and

,

third station transmitting means at the third station for transmitting a reservation request to the first station if the random transmission parameter N₂ bears a second predetermined relationship to the slot parameter MP and for abstaining from transmitting a reservation request to the first station if the random transmission parameter N₂ does not bear the second predetermined relationship to the slot parameter MP, wherein a reservation request, if any, is transmitted by the third station transmitting means in a reservation slot.

18. The communication system of claim 17 wherein the second station transmitting means comprises means for abstaining from transmitting a reservation request to the first station if the random transmission parameter N₁ is between about the slot parameter MP and about the range parameter R, and wherein the third station transmitting means comprises means for abstaining from transmitting a reservation request to the first station if the random transmission parameter N₂ is between about the slot parameter MP and about the range parameter R.

19. The communication system of claim 17 wherein reservation slots are minislots, wherein the slot parameter MP determining means determines the slot parameter MP as follows:

if RDS(n)<

DQ(n)<

α

RDS(n), determine the slot parameter MP based upon the following equation;

##EQU26## wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP, wherein RDS(n) is the number of data slots in a data frame at discrete time n, wherein DQ(n) is the number of reservation requests waiting to be processed by the first station at time n, wherein α

is a constant, wherein M is the number of minislots in steady state, wherein S is the number of slots in a data frame, wherein k is a number corresponding to an average number of data slots reserved by reservation requests, wherein e is 2.718281828 . . . , and wherein m is the number of minislots into which a slot of a data frame may be subdivided;

if DQ(n)<

RDS(n), determine the slot parameter MP based upon the following equation;

space="preserve" listing-type="equation">MS(n+1)=m(S-DQ(n))

wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP; and

,

if DQ(n)>

α

RDS(n), determine the slot parameter MP based upon the following equation;

##EQU27## wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP.

20. The communication system of claim 17 wherein the range parameter R determining means determines the range parameter R for discrete time n+1 as follows:

if a successful rate Psuc(n) at discrete time n is greater than about c, determining the range parameter R for discrete time n+1 according to the following first equation;

##EQU28## wherein R(n) is the range parameter R at discrete time n, wherein c is a constant, and wherein Rcol(n) is based upon a number of reservation slots in which data collisions occurred at discrete time n;

if the successful rate Psuc(n) at discrete time n is not greater than about c, determining the range parameter R for discrete time n+1 according to the following second equation;

##EQU29## and wherein Rsuc(n) is based upon a number of non-empty reservation slots in which data collisions did not occur at discrete time n; and

,

if R(n+1)<

MS(n+1), determining the range parameter R for discrete time n+1 according to the following third equation;

space="preserve" listing-type="equation">R(n+1)=MS(n+1)

wherein R(n+1) in inequality R(n+1) <

MS(n+1) is determined by the first or second equation as appropriate, and MS(n+1) is the number of reservation slots in a data frame at discrete time n+1, and if R(n+1)>

MS(n+1), using R(n+1) as determined by the first or second equation as appropriate.

21. The communication system of claim 20 wherein reservation slots are minislots, wherein the slot parameter MP determining means determines the slot parameter MP as follows:

if RDS(n)<

DQ(n)<

α

RDS(n), deter mine the slot parameter MP based upon the following equation;

##EQU30## wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP, wherein RDS(n) is the number of data slots in a data frame for discrete time n, wherein DQ(n) is the number of reservation requests waiting to be processed by the first station at time n, wherein α

is a constant, wherein M is the number of minislots in steady state, wherein S is the number of slots in a data frame, wherein k is a number corresponding to an average number of data slots reserved by reservation requests, wherein e is 2.718281828 . . . , and wherein m is the number of minislots into which a slot of a data frame may be subdivided;

if DQ(n)<

RDS(n), determine the slot parameter MP based upon the following equation;

space="preserve" listing-type="equation">MS(n+1)=m(S-DQ(n))

wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP; and

,

if DQ(n)>

α

RDS(n), determine the slot parameter MP based upon the following equation;

##EQU31## wherein MS(n+1) is the number of minislots in a data frame at discrete time n+1 and corresponds to the slot parameter MP.

22. The communication system of claim 21 wherein Rcol(n) is determined based upon the following equation:

##EQU32## and wherein Rsuc(n) is determined based upon the following equation;

##EQU33##

23. The communication system of claim 21 wherein Rcol(n) is determined from a look up table which is generated to substantially satisfy the following equation:

and wherein Rsuc(n) is determined from a look up table which is generated to substantially satisfy the following equation;

##EQU34##

24. The communication system of claim 21 wherein c=1/e.

25. A communication system comprising:

a master station;

a plurality of slave stations, wherein the plurality of slave stations communicate to the master station in a data frame having MS reservation slots and/or DS data slots, wherein the plurality of slave stations communicate data to the master station in the DS data slots, wherein the plurality of slave stations communicate reservation requests to the master station in the MS reservation slots, wherein MS may vary from MS_min to MS_max, and wherein DS may vary from DS_min, to DS_max ; and

,

a frame controller at the master station arranged to control the MS reservation slots and DS data slots in a data frame dependent upon load.

26. The communication system of claim 25 wherein the data frame has S slots, wherein MS_max =S, and wherein DS_min =0.

27. The communication system of claim 26 wherein the data frame has S slots, wherein DS_max =S, and wherein MS_min =0.

28. The communication system of claim 26 wherein the data frame has S slots and wherein MS_min =S-DS_max ≠

0.

29. The communication system of claim 25 wherein the data frame has S slots, wherein DS_max =S, and wherein MS_min =0.

30. The communication system of claim 25 wherein the data frame has S slots and wherein MS_min =S-DS_max ≠

0.

31. The communication system of claim 25 wherein the master station includes means for determining a range parameter R, wherein the range parameter R is based upon a number of reservation requests transmitted by the slave stations.

32. The communication system of claim 31 wherein the master station includes transmitting means for transmitting the range parameter R and a slot parameter corresponding to MS to the slave stations.

33. The communication system of claim 32 wherein each of the slave stations includes means for generating a transmission parameter N, for transmitting a reservation request to the master station if the transmission parameter N corresponds to the slot parameter, and for abstaining from transmitting a reservation request to the master station if the transmission parameter N does not correspond to the slot parameter, wherein a reservation request, if any, is transmitted in a reservation slot.

34. The communication system of claim 33 wherein the transmission parameter N is a random number with a range corresponding to the range parameter R.

35. A station connectable to a network comprising:

a receiver arranged to receive a downstream data frame having a range parameter and a variable reservation slot parameter;

a transmission parameter generator arranged to generate a transmission parameter according to the range parameter; and

,

a transmitter arranged to transmit a reservation request in a reservation slot of an upstream data frame if the transmission parameter and the reservation slot parameter have a predetermined relationship and to abstain from transmitting a reservation request if the transmission parameter and the reservation slot parameter do not have the predetermined relationship.

36. The station of claim 35 wherein the upstream data frame has S slots, wherein the S slots include MS reservation slots and/or DS data slots, wherein MS may vary from MS_min to MS_max, wherein DS may vary from DS_min to DS_max, wherein MS_max =S, and wherein DS_min =0.

37. The station of claim 36 wherein the upstream data frame has S slots, wherein DS_max =S, and wherein MS_min =0.

38. The station of claim 36 wherein the upstream data frame has S slots and wherein MS_min =S-DS_max ≠

0.

39. The station of claim 35 wherein the upstream data frame has S slots, wherein the S slots include MS reservation slots and/or DS data slots, wherein MS may vary from MS_min to MS_max, wherein DS may vary from DS_min to DS_max, wherein DS_max =S, and wherein MS_min =0.

40. The station of claim 35 wherein the upstream data frame has S slots, wherein the S slots include MS reservation slots and/or DS data slots, wherein MS may vary from MS_min to MS_max, wherein DS may vary from DS_min to DS_max, and wherein MS_min =S-DS_max ≠

0.

41. The station of claim 35 wherein the transmission parameter is a random number.

42. A station connectable to a network receiver comprising:

a receiver arranged to receive a downstream data frame having a range parameter R and a variable slot parameter MP;

a transmission parameter generator arranged to generate a transmission parameter N, wherein the transmission parameter N is less than about R; and

,

a transmitter arranged to transmit a reservation request on the basis of the transmission parameter N, the variable slot parameter MP, and the range parameter R, wherein the reservation request is transmitted in a reservation slot of an upstream data frame.

43. The station of claim 42 wherein the upstream data frame has S slots, wherein the S slots include MS reservation slots and/or DS data slots, wherein MS may vary from MS_min to MS_max, wherein DS may vary from DS_min to DS_max, wherein MS_max =S, and wherein DS_min =0.

44. The station of claim 43 wherein the upstream data frame has S slots, wherein DS_max =S, and wherein MS_min =0.

45. The station of claim 43 wherein the upstream data frame has S slots and wherein MS_min =S-DS_max ≠

0.

46. The station of claim 42 wherein the upstream data frame has S slots, wherein the S slots include MS reservation slots and/or DS data slots, wherein MS may vary from MS_min to MS_max, wherein DS may vary from DS_min to DS_max, wherein DS_max =S, and wherein MS_min =0.

47. The station of claim 42 wherein the upstream data frame has S slots, wherein the S slots include MS reservations slots and/or DS data slots, wherein MS may vary from MS_min to MS_max, wherein DS may vary from DS_min to DS_max, and wherein MS_min =S-DS_max ≠

0.

48. The station of claim 42 wherein the transmitter transmits a reservation request to the master station if the transmission parameter N is between about 0 and about the variable slot parameter MP, and for abstaining from transmitting a reservation request to the master station if the transmission parameter N is between about the variable slot parameter MP and about the range parameter R.

49. The station of claim 42 wherein the transmission parameter N is a random number.