(12) United States Patent
`Chuah
`
`USOO6469991B1
`(10) Patent No.:
`US 6,469,991 B1
`(45) Date of Patent:
`*Oct. 22, 2002
`
`(54) METHOD FOR OVERLOAD CONTROL INA
`MULTIPLE ACCESS SYSTEM FOR
`COMMUNICATION NETWORKS
`
`(75) Inventor: Mooi Choo Chuah, Eatontown, NJ
`(US)
`(73) Assignee: Lucent Technologies Inc., Murray Hill,
`NJ (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`This patent is Subject to a terminal dis
`claimer.
`
`(*) Notice:
`
`(21) Appl. No.: 09/083,759
`(22) Filed:
`May 22, 1998
`Related U.S. Application Data
`(60) Provisional application No. 60/061,790, filed on Oct. 14,
`1997, and provisional application No. 60/077,741, filed on
`Mar. 12, 1998.
`(51) Int. Cl. .................................................. H04Q 7/00
`(52) U.S. Cl. ....................... 370/329; 370/347; 370/412;
`370/442; 370/469
`(58) Field of Search ................................. 370/252, 280,
`370/281, 294, 295, 296, 329, 333,336,
`337, 469,345, 347, 412,442
`References Cited
`U.S. PATENT DOCUMENTS
`
`(56)
`
`5,181,200 A 1/1993 Harrison
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`
`EP
`
`O 599 515
`6/1994
`(List continued on next page.)
`OTHER PUBLICATIONS
`European Search Report, Mar. 23, 1999, 6 pages.
`(List continued on next page.)
`
`Primary Examiner Alpus H. Hsu
`ASSistant Examiner Roberta Stevens
`(57)
`ABSTRACT
`
`In the method for overload control in a wireless communi
`cations network employing On-Demand Multiple Access
`Fair Queuing, if the downlink/uplink buffer occupancy of
`the network has exceeded a high threshold, the base Station
`determines if this is caused by a specific remote host or by
`a group of remote hosts. If caused by a Specific remote host,
`the base Station normally sends a flow control Signal to the
`remote host to prevent it from Sending more data, but may
`alternatively elect to disconnect other remotes if the remote
`experiencing bad performance is of a higher priority. The
`base Station may additionally reduce the bandwidth shares
`allocated to any remote that have indicated tolerance for a
`variable allocated bandwidth. If the measured frame error
`rates for many remote hosts are increasing, then the base
`Station may elect to disconnect those remote hosts that
`permit Service interruption in order that more bandwidth
`may be allocated to the remaining users. If a majority of all
`asSociated remote hosts experience high uplink frame error
`rates, the base Station may instead Senda Signal to a wireleSS
`hub which can coordinate the actions of other access points.
`Short packets queued up for So long at the base Station that
`they exceed the time-to-live value allocated will be thrown
`away. The base Station may also or alternatively elect to
`disconnect Some users of a lower priority or redirect them to
`other nearby base Stations that have a lower load. In a
`particular embodiment, an uplink Frame Error Rate (FER),
`an average uplink bit rate, a burstineSS factor of uplink
`traffic, and a packet loSS rate are measured at the base Station
`for each remote host. Similarly, a downlink Frame Error
`Rate is measured at each remote host and then each FER is
`Sent to the base Station. If an overload condition exits,
`connections with a Frame Error Rate that has exceeded a
`threshold for a specified time and that have indicated that
`their connections can be interrupted are disconnected. Other
`combinations of the possible actions are Suitable, with the
`exact combination being determined by the base Station
`depending on the particular congestion conditions observed
`in the network.
`
`17 Claims, 34 Drawing Sheets
`
`
`
`230
`
`244
`
`246
`
`Ex. 1015 / Page 1 of 61
`ERICSSON v. UNILOC
`
`

`

`US 6,469,991 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`8/1994 Fennel et al.
`5,335,357 A
`7/1996 Bodnar
`5,539,729 A
`5,721,762 A 2/1998 Sood
`FOREIGN PATENT DOCUMENTS
`
`EP
`GB
`GB
`WO
`WO
`WO
`
`O 660 626
`2311 191
`2311 192
`WOO95/15644
`WO95/35002
`WO 97/O1941
`
`6/1995
`9/1997
`10/1997
`6/1995
`12/1995
`1/1997
`
`OTHER PUBLICATIONS
`Lu et al., Fair Scheduling in Wireless Packet Networks,
`Sigcom 97.
`Kautz, R., A Distributed Self-Clocked Fair Queueing Archi
`tecture for Wireless ATM Networks, (1996).
`Kautz and Leon-Garcia, A Distributed Self-Clocked Fair
`Queueing Architecture for Wireless ATM Networks, Int’l
`Symposium on Personal Indoor and Mobile Radio Commu
`nications (1997).
`Karol et al., Distributed-Queueing Request Update Multiple
`Access (DORUMA) for Wireless Packet (ATM) Networks,
`pp. 1224–1229 (1995).
`Karol et al., An efficient demand-assignment multiple
`access protocol for wireless packet (ATM) networks, Wire
`less Networks 1:267–279 (1995).
`
`Doshi et al., A Broadband Multiple Access Protocol for
`STM, ATM, and Variable Length Data Services on Hybrid
`Fiber-Coax Networks, Bell Labs Technical Journal, pp.
`36-65 (Summer, 1996).
`Golestani, S.J., A Self-Clocked Fair Queueing Scheme for
`Broadband Applications, IEEE INFOCOM 94: Proceed
`ings: Conference on Computer Commun., Toronto, Ontario,
`Jun. 12-16, 1994, pp. 636-646.
`CDMA Access Channel Power Control, International Stan
`dard IS95, pp. 6-106-6-112.
`Zhang, L., VirtualClock: A New Traffic Control Algorithm
`for Packet-Switched Networks, ACM Transactions on Com
`puter Systems 9:101-124 (1991).
`Rege, K., Equivalent Bandwidth and Related Admission
`Criteria for ATM Systems-A Performance Study, Int’l J. of
`Commun. Systems 7:181-197 (1994).
`Parekh and Gallager, A Generalized Processor Sharing
`Approach to Flow Control in Integrates Service Networks:
`The Single-Node Case, IEEE/ACM Transactions on Net
`working 1:344–357 (1993).
`Siram and Magill, Enhanced Throughout Efficiency by Use
`of Dynamically Variable Request Mini-Slots in MAC Pro
`tocols for HEC and Wireless Access Networks, Submitted to
`INFOCOM 98.
`
`Ex. 1015 / Page 2 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 1 of 34
`
`US 6,469,991 B1
`
`O
`sa-
`
`i
`
`S.
`
`& H
`
`s
`sh NJ
`
`|
`
`V
`
`s
`its 2 Gas
`1 s
`e a al
`
`cao
`
`is
`
`2
`
`
`
`Ex. 1015 / Page 3 of 61
`ERICSSON v. UNILOC
`
`

`

`US. Patent
`
`Oct. 22, 2002
`
`Sheet 2 0f 34
`
`US 6,469,991 B1
`
`<_::
`‘u-
`N
`
`+——
`*2D_
`CC<
`OE
`<__> :2:D-—I
`
`f\
`v
`m
`
`:
`m
`
`‘
`I
`
`C)
`er
`
`("\J
`
`N
`LI?
`
`(\J
`
`(:3
`<=r
`
`("\J
`
`|:::l[::il
`
`I::l[::lil
`
`|:::l:::lil
`
`|
`
`l
`I
`l
`I
`
`I
`I
`
`I
`I
`I
`l
`I
`I
`
`|:::|I:::lil
`
`I
`I
`I
`'
`
`l
`'
`
`I
`I mV-
`I
`(«\J
`I
`‘
`‘
`I
`
`N
`
`.
`(-!:’
`H
`
`<::>
`r1'3
`m
`
`I
`I
`
`U1
`
`N
`
`_ ______> _ _ _______ __ _ _______ __ _
`
`_ __ “______ _» _ _______ _ _
`
`<__>m
`z I
`
`<::>
`~=r
`N
`
`N
`m
`m
`
`236if
`
`235
`
`—_
`
`235
`
`N
`m
`m
`
`7
`
`II
`I
`‘L
`I
`
`,/’ I
`nnnnn
`I
`m IJDIJD
`
`[jjUnU
`
`I
`3mm
`quu I
`I
`I
`I
`M Wang
`I
`___7 II
`I
`
`
`
`”Dan
`IiIJDIIU
`nnJD
`I f""‘9
`I
`DDJU
`II
`‘
`I man
`I
`I
`I
`Dang
`‘
`we Um
`
`
`
`/
`
`Dunn
`, 7
`LIEU”
`r
`'
`'
`I
`JDUD
`I "'__'“I
`;
`JIJUU
`:
`‘
`
` I Dunn 5 I
`
`I
`DUDE
`.
`I
`I
`
`
`,,,, ,
`I
`I.
`I
`I
`HUD]
`
`,
`“and
`nUU’J
`HUG?
`mm
`um
`Dun]
`Dflflu
`1IJED
`
`
`
`
`
`
`
`
`
`
`
`Ex. 1015 / Page 4 of61
`ERICSSON v. UNILOC
`
`Ex. 1015 / Page 4 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 3 of 34
`
`US 6,469,991 B1
`
`31O 314
`
`330
`320 350 322
`360
`irrir PPNSS BROADCASI!' ...
`Ack ACK ACK ACK s
`MULTICAST
`
`FIG 3
`
`312
`
`355 340
`
`380
`
`355 380 355 380 355
`
`
`
`sts:
`
`410
`
`420
`
`422
`
`FIG. 4
`
`415
`
`
`
`
`
`CONTENTION
`DATA
`
`DATA
`
`DATA
`ACK
`
`486
`--
`
`440
`
`440
`
`480 480 488
`
`490
`
`FIG. 5
`
`504
`502
`N- FRAME in
`
`508
`506
`FRAME n2
`
`FRAME n-1
`
`520
`c
`Tp
`T R
`H
`
`564-
`
`FRAME n-1
`
`516
`518
`||
`FRAME n-2
`
`
`
`512
`
`514
`FRAME n |
`-530
`:
`566
`568
`562
`FRAE na T FRAE na -1
`TAP-7 - --
`520
`540
`- Tip-4
`I
`-
`572 574
`N- FAE n-1
`FRAME n2
`—e
`T-Cpe
`
`5
`76
`
`570
`FRAME n-3
`
`550
`
`Ex. 1015 / Page 5 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 4 of 34
`
`US 6,469,991 B1
`
`
`
`FIG EA
`
`601
`
`602
`
`630 632
`
`4 3
`6
`
`636
`
`622
`
`624
`
`PHY
`OWERHEAD
`
`SRC
`
`DS
`T
`DR
`
`SEO FRAME
`
`604.
`
`606 608
`
`610
`
`12
`6
`
`4
`6.
`
`6
`16
`
`
`
`FIG. BB
`620
`--
`
`
`
`
`
`SRC
`
`DST
`
`SEO ) . . .
`
`640
`
`
`
`626
`
`602
`
`630
`650
`
`634
`
`632
`660
`
`636
`670
`
`628 624
`
`BROADCASTI
`ACKS
`BEACON RESERVATION TRANSMIT
`TRANSMIT
`gear PERMITS | SCHEDULES "ugs' E.
`
`622
`
`Ex. 1015 / Page 6 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet S of 34
`
`US 6,469,991 B1
`
`FIG. SC
`640
`
`SUB
`
`BEACON MSG BODY
`
`642
`
`644
`
`641
`
`FIG. SD
`
`SUB
`TYPE | SS
`
`TRANSMIT PERMITS
`
`
`
`
`
`
`
`651
`
`652
`
`654
`
`GT3 12s 35
`
`65
`
`5
`
`655 657 658 659 657 658 659
`N- 1 --
`656
`656
`
`FIG. SE
`660
`
`
`
`
`
`SUB is TRANSMIT SCHEDULES
`
`GS2
`
`664
`
`661
`
`FIG. SF
`670
`
`IYDE | SJB | BROADCASTINYTICAST
`TYPE
`PAYLOAD
`
`S72
`
`674
`
`671
`
`Ex. 1015 / Page 7 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 6 of 34
`
`US 6,469,991 B1
`
`FIG 7A
`701
`
`700
`
`SEC,
`ADDR
`
`DS
`ADDR
`
`SEO,
`CNTR
`
`UNICAST
`DATA
`
`ECS
`
`702
`
`704
`
`7 OS
`
`708
`
`710
`
`720
`
`712
`
`FIG 7B
`720
`
`
`
`SUB
`
`722
`
`724
`
`726
`
`730
`
`FIG. 7C
`72O
`
`
`
`SUB
`
`DATA
`
`MORE
`
`740
`
`742
`
`44
`7
`
`746
`
`748
`
`Ex. 1015 / Page 8 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`US. Patent
`
`a"0
`
`mm.
`
`hS
`
`7
`
`3
`
`US 6,469,991 B1
`US 6,469,991 B1
`
`nQR.mHm
`
`2:
`
`
`
`
`
`
`
`
`0GL
`OE
`
`ME:#:5$84.
`
`$5395
`
`m“::5
`
`4E5E3meg
`
`4m:CEmmmENEOS2:NEE:
`
`3:NE
`
`9:
`
`mmN
`
`m2
`
`E
`
`NE
`
`Ex. 1015 / Page 9 of61
`ERICSSON v. UNILOC
`
`Ex. 1015 / Page 9 of 61
`ERICSSON v. UNILOC
`
`
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 8 of 34
`
`US 6,469,991 B1
`
`FIG. BA
`
`808
`
`810
`
`B12
`
`FIG. BB
`812
`
`B20
`-n-
`
`CONTEN-CONTEN
`TION
`TION
`DATA
`DATA
`
`DATA
`
`DATA
`
`DATA
`
`822
`
`824
`
`824
`
`826
`
`826
`
`826
`
`FIG. BC
`
`
`
`DATA
`DATA
`: RES.
`RES...
`:
`RES...
`:
`RES...
`MINI : MINI : MINI : MINI post DATA
`
`822
`
`822
`
`822
`
`B22
`
`B32
`
`832
`
`826
`
`B26
`
`Ex. 1015 / Page 10 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 9 of 34
`
`US 6,469,991 B1
`
`FIG. BD
`
`CS
`
`B40
`
`842
`
`844
`
`FIG. BE
`
`MAC
`
`848
`
`850
`
`852
`
`B54
`
`856
`
`858
`
`FIG. BF
`
`
`
`MAC
`
`86O
`
`862
`
`864
`
`854
`
`866
`
`858
`
`Ex. 1015 / Page 11 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 10 of 34
`
`US 6,469,991 B1
`
`FIG. BG
`
`MAC
`
`870
`
`B72
`
`874
`
`854
`
`76
`
`878
`
`858
`
`FIG. BH
`
`
`
`MAC is cost soofs
`
`880
`
`882
`
`884
`
`854
`
`886
`
`888
`
`890
`
`858
`
`Ex. 1015 / Page 12 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 11 of 34
`
`US 6,469,991 B1
`
`FIG. 9A
`
`908 924 92O 906 920 918 904 916 914 902 912
`
`12 ele
`
`3232 2s2 220 G 16
`to
`910
`- Y
`)
`PACKELIN
`N SERVICEur
`
`(
`
`N
`
`:
`
`FIG. 9B
`
`908 924 922 906 920
`
`3232 2s2 24
`t=3
`- - - - -/918
`...)
`PACKET IN
`NSERVICE
`
`\
`
`Ex. 1015 / Page 13 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 12 of 34
`
`US 6,469,991 B1
`
`FIG. 90
`
`94G 944 942 94O 908 924 938 93G 922 934. 932 906 920 930
`
`
`
`3
`
`
`
`$
`
`||38|963. 3232 3230 28.2e2G 2922422
`() )
`
`t=3
`- - - -
`
`918
`
`PACKELIN
`N SERVICEu
`
`FIG 9D
`
`952 946 944 942 940 950 924 938 936 922 934. 932
`
`40.383,33232 3230 2828 262
`906 r/ )
`
`t= 4.5
`- - - -
`
`PACKELIN
`NSERVICE
`
`Ex. 1015 / Page 14 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 13 of 34
`
`US 6,469,991 B1
`
`FIG 10
`
`1010
`
`1012
`
`1012
`
`1020
`
`1020
`
`1030
`
`103O
`
`1030
`
`1040
`
`RES
`
`RES
`
`is is colonoe
`
`RES
`
`RES
`
`1050
`
`1012
`
`O12
`
`1020
`
`1020
`
`102O
`
`1030
`
`1030
`
`OGO
`
`
`
`RES
`
`RES
`
`RES
`
`RES
`
`Ex. 1015 / Page 15 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 14 of 34
`
`US 6,469,991 B1
`
`FIG 11
`
`1110
`
`
`
`
`
`
`
`
`
`Location
`SERVER
`
`1112
`
`
`
`HOME
`REGISTRATION
`SERVER
`WH/IWF
`
`1142
`
`1120
`
`Ex. 1015 / Page 16 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 15 of 34
`
`US 6,469,991 B1
`
`
`
`1203 (>
`
`N = N - K
`SLOTS = SLOTS 1
`STATE = 1
`
`1204
`
`
`
`
`
`
`
`
`
`
`
`
`
`N = N + K
`SLOTS = SLOTS-1
`STATE - O
`
`1208
`
`Ex. 1015 / Page 17 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 16 of 34
`
`US 6,469,991 B1
`
`FIG.
`12B
`
`ONED
`
`NO
`
`1226
`
`YES
`
`1227
`STATE o)
`
`YES
`
`1228
`YES
`
`YES
`
`NO
`
`1220
`
`YES
`
`NO
`
`1212
`NO
`
`G) YES
`
`NC
`
`1214
`
`N
`O
`
`1213
`
`1221
`
`YES
`
`YES
`
`1215
`
`YES
`
`N = N - 2K
`SLOTS = SLOTS 2
`STATE = 2
`
`N = N - K
`SLOTS = SLOTS 1
`STATE = 2
`
`NO
`
`1222 ONE)
`NO
`
`ONED
`
`ONE)
`
`YES
`
`1223
`YES
`
`225
`
`1224
`
`N = N + K
`SLois's ois
`STATE = 1
`
`1230
`
`NO
`
`1229
`
`NO
`
`NO
`
`N = N + 2K
`SLOTS = SLOTS-2
`STATE = 0
`
`N = N + K
`SLOTS = SLOTS-1
`STATE = 0
`
`ONED
`
`ONED
`
`
`
`
`
`
`
`
`
`1219
`
`- K
`N
`SLOTS = SLOTS 1
`STATE = 1
`
`Ex. 1015 / Page 18 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 17 of 34
`
`US 6,469,991 B1
`
`FIG. 12C
`
`START
`
`1240
`YES
`
`1241
`N
`
`YES
`
`1242
`
`NO
`
`CDONED
`
`1243
`
`YES
`
`N = N - K
`SLOTS = SLOTS 1
`
`1244
`
`YES
`
`245
`
`YES
`
`1246
`
`YES
`
`1247
`
`NO
`
`NO
`
`N = N K
`SLOTS = SLOTS-1
`
`Ex. 1015 / Page 19 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 18 of 34
`
`US 6,469,991 B1
`
`FIG, 12D
`
`1250
`
`1251
`YES
`
`NO
`
`1255
`YES
`
`ONED
`NO
`
`OND
`NO
`1252
`
`YES
`
`1253
`
`YES
`
`OONED
`
`N - N - 2K
`SLOTS = SLOTS?
`
`ONED-
`
`1257
`
`N = N - K
`
`SLOTS = SLOTS 1
`CDONE)
`
`NO
`
`1254
`
`NO
`
`1258
`
`YES
`
`256
`
`1259
`
`G> M-ONED
`
`YES
`
`NO
`
`1262
`
`YES
`
`1260
`
`NO
`
`NO
`
`YES
`
`YES
`
`DONE Gy (C) ONE)
`1269
`1251
`N = N + 2K
`SLOTS = SLOTS-2
`
`ONED NO
`
`DONE
`
`YES
`
`1264
`
`ONED <C)
`
`1265
`
`(YES
`
`N = N + K
`SLOTS = SLOTS-1
`
`Ex. 1015 / Page 20 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 19 of 34
`
`US 6,469,991 B1
`
`FIG. 13A
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ESTABLISH VPLINK 11310
`TRANSMISSION
`POWER LEVEL
`
`UPLINK
`CONTENTION
`
`ACCESS N YES
`UPLINK
`REOUEST =
`CONFLICT
`CONFLICT? Y RESOLUTION
`
`1325
`
`UPLINK
`BANDWIDTH
`ALLOCATION
`
`1330
`
`DOWNLINK
`BANDWIDTH
`ALLOCATION
`
`1335
`
`WAIT FOR
`TRANSMIT
`PERMITS
`
`1337
`
`
`
`WAIT UNTIL
`NEW PACKETS
`ARRIVE
`
`1339
`
`Ex. 1015 / Page 21 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 20 of 34
`
`US 6,469,991 B1
`
`FIG. 13B
`
`1360
`
`MONITOR
`ACTIVITIES IN
`RESERVATION SLOTS
`
`1365
`
`
`
`
`
`
`
`ANY
`ACCESS
`REOUEST =
`SUCCESS
`
`
`
`1370
`
`
`
`SEND
`RESERVATION
`ACKS
`
`1375
`
`
`
`
`
`ADD NEWLY
`SUCCESSFUL
`REMOTES TO
`SCHEDULERS
`LIST
`
`1380
`
`
`
`
`
`MONITOR
`UPLINK
`DATA SLOTS
`
`1985
`
`
`
`DATA
`SLOTS =
`SUCCESS
`
`130Y is a
`SLOT ACKS
`
`
`
`
`
`
`
`
`
`
`
`
`
`TRANSMIT
`DOWNLINK
`DATA PACKETS
`
`1355
`
`1350
`
`
`
`
`
`ISSUE
`TRANSMIT
`PERMITS
`
`1345
`
`SCHEDULE
`UPLINK
`PACKETS
`
`
`
`St. 1340
`PACKETS
`
`
`
`Ex. 1015 / Page 22 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 21 of 34
`
`US 6,469,991 B1
`
`NODE TRANSMITS
`CURRENT PACKET
`
`1406
`
`1405
`
`OUEUE
`AT NODE
`EMPTY?
`
`1403
`
`
`
`NODE TRANSMITS
`CURRENT PACKET
`WITH PIGGYBACKED
`RESERVATION REOUEST
`AFTER RECEIVING
`TRANSMIT PERMIT
`
`FIG. 14A
`
`
`
`
`
`1402
`
`
`
`REMOTE NODE
`WAITING TO ACCESS
`AP RANDOMLY
`PICKS MAILSLOT
`
`NODE
`AFFECTED BY A
`COLLISION?
`
`NODE GENERATES
`RANDOM H, I,
`O< I < 2-1.
`j < 10
`
`
`
`
`
`
`
`NODE SKIPS NEXT
`I-1 CONTENTION
`SLOT OPPORTUNITIES
`OF SAME KIND
`
`
`
`NODE RETRANSMITS
`COLLIDED PACKET AT
`NEXT IMMEDIATE
`CONTENTION SLOT
`OPPORTUNITY
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ex. 1015 / Page 23 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 22 of 34
`
`US 6,469,991 B1
`
`FIG, 14B
`
`
`
`
`
`
`
`1432
`
`REMOTE NODE
`WAITING TO ACCESS
`AP OR IOMAIL WHEN
`DATASETS STACK
`LEVEL = O AND ENTERS
`REOUEST STATE
`
`
`
`INCREMENT STACK
`LEVEL BY 1.
`
`
`
`
`
`OUTCOME
`FOR PREVIOUS
`MINISLOT =
`COLLIDED2
`
`NO
`
`DECREMENT STACK
`LEVEL BY 1.
`
`LEAVE STACK
`LEVEL = 0
`
`INCREMENT STACK
`LEVEL BY 1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`NODE TRANSMITS
`CURRENT PACKET
`AND EXITS
`REQUEST STATE
`
`NODE TRANSMITS
`CURRENT PACKET
`WITH PIGGYBACKED
`RESERVATION REQUEST
`AFTER RECEIVING
`TRANSMIT PERMIT
`
`
`
`
`
`NODE RANDOMLY
`PICKS MINISLOT
`FOR TRANSMISSION
`OF ACCESS REOUEST
`PACKET S TRANSMITS
`ACCESS REQUEST
`
`
`
`1444
`
`NO 6NS
`INCREMENT
`
`Ex. 1015 / Page 24 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 23 of 34
`
`US 6,469,991 B1
`
`FIG. 14C
`
`
`
`
`
`
`
`432
`
`REMOTE NODE
`WAITING TO ACCESS
`AP OR SEND NEW
`DATA SETS STACK
`LEVEL = O AND ENTERS
`REOUEST STATE
`
`
`
`
`
`NODE TRANSMITS
`CURRENT PACKET
`AND EXITS
`REOUEST STATE
`
`OUEUE
`AT NODE
`EMPTY?
`
`NODE TRANSMITS
`CURRENT PACKET
`WITH PIGGYBACKED
`RESERVATION REOUEST
`AFTER RECEIVING
`TRANSMIT PERMIT
`
`
`
`
`
`NODE RANDOMLY
`PICKS MINISLOT
`FORTRANSMISSION
`OF ACCESS REOUEST
`PACKETS TRANSMITS
`ACCESS REQUEST
`
`DECREMENT STACK
`LEVEL BY 1.
`
`
`
`
`
`OUTCOMEDF >
`THRESHHOLD ALL
`MINISLOTS =
`COLLIDED?
`
`YES
`
`INCREMENT STACK
`LEVEL BY 1
`
`LEAVE STACK
`LEVEL = O
`
`
`
`NO 6.
`INCREMENT
`
`
`
`1444
`
`INCREMENT STACK
`LEVEL BY 1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ex. 1015 / Page 25 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 24 of 34
`
`US 6,469,991 B1
`
`FIG. 15A
`
`1510
`
`
`
`1515-N
`
`BROADCAST SYSTEM
`VIRTUAL TIME FROM
`AP TO REMOTES
`
`COMPUTE SERVICE
`TAGS AT EACH REMOTE
`
`1520
`
`TRANSMIT SMALLEST
`TAG VALUE FROM
`EACH REMOTE TO AP
`
`1530-N
`
`
`
`DETERMINE TRANSMIT
`PERMITS AT AP GATED
`ONTAG VALUES AND
`AVAILABLE DATA SLOTS
`
`
`
`1535-N
`
`SEND TRANSMIT
`PERMITS TO REMOTES
`
`
`
`
`
`1540-N
`
`RECEIVE PACKET
`FROMA REMOTE
`
`
`
`1545
`
`
`
`IN ERROR2
`
`
`
`
`
`
`
`
`
`
`
`MORE
`SCHEDULED
`PACKETS TO
`EXAMINE
`
`REMOTE RECOMPUTES
`OWN TAG VALUES
`
`Ex. 1015 / Page 26 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 25 of 34
`
`US 6,469,991 B1
`
`FIG. 15B
`
`1560
`
`
`
`TRANSMIT PACKET
`COUNT FROM EACH
`REMOTE TO AP
`
`1565-N
`
`COMPUTE AT AP TAG
`WALUES FOR ALL REMOTES
`
`DETERMINE TRANSMIT
`PERMITS AT AP GATED
`ONTAG VALUES AND
`AVAILABLE DATA SLOTS
`
`SEND TRANSMIT
`PERMITS TO REMOTES
`
`
`
`
`
`RECEIVE PACKET
`FROMA REMOTE
`
`
`
`1545
`
`IN ERROR2
`
`
`
`
`
`
`
`
`
`RECOMPUTE AT AP TAG
`WALUES FOR THAT MODE
`
`
`
`
`
`
`
`
`
`MORE
`SCHEDULED
`PACKETS TO
`EXAMINE2
`
`Ex. 1015 / Page 27 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 26 of 34
`
`US 6,469,991 B1
`
`FIG 16
`
`1610
`
`CAL CULATE SERVICE TAG
`INCREMENT FOR EACH NODE
`
`
`
`1612-N-
`
`ASSIGN SERVICE TAGS
`TO EACH NODE'S PACKETS
`BASED ON FO ALGORITHM
`
`SERVICE PACKETS
`
`PACKETS
`ARRIVE FROM
`NEW NODE
`
`PACKET
`TRANSMITTED
`IN ERROR2
`
`REASSIGN SERVICE TAG
`OF THAT PACKET =
`CURRENT TAG
`INCREMENT
`FOR THAT NODE
`
`1622
`
`REMAINING NODE PACKETS
`GET SERVICE TAG = OLD
`SERVICE TAG
`INCREMENT
`
`1624
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ASSIGN TAGS TO PACKETS
`OF NEW NODE STARTING
`FROM TAG OF PACKET
`CURRENTLY IN SERVICE .
`SERVICE TAG INCREMENT
`OF THAT NODE
`
`1618
`
`Ex. 1015 / Page 28 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 27 of 34
`
`US 6,469,991 B1
`
`FIG. 17
`
`UPLINK
`TRANSMISSION
`POWER LEVEL
`STORED?
`
`1710
`
`
`
`
`
`
`
`
`
`
`
`MAKE CONNECTION
`REOUEST AT
`INITIAL LEVEL
`
`USE STORED POWER
`LEVEL FOR UPLINK
`TRANSMISSION
`
`1715
`
`ACK RECEIVED?
`
`
`
`STORE CURRENT
`POWER LEVEL
`
`1735
`
`INCREASE POWER
`LEVEL BY PRE
`DETERMINED
`INCREMENT
`
`RENEW CONNECTION
`REOUEST USING
`NEW POWER LEVEL
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ex. 1015 / Page 29 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 28 of 34
`
`US 6,469,991 B1
`
`FIG 1BA
`
`PERFORM CONFLICT
`RESOLUTION
`AT MOBILES
`
`GRANT ACCESS TO
`"WINNING" HOST
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CONFIGURE N
`CONTENTION MINI
`SLOTS IN EACH
`UPLINK FRAME
`
`ALLOW FORM
`ACCESS PRIORITY
`CLASSES AT AP
`
`
`
`
`
`
`
`EACH HOST OF
`ACCESS PRIORITY i
`PICKS MINISLOT FROM
`RANGE OF 1 TO Ni
`
`RECEIVE ACCESS
`REQUESTS AT AP
`
`UNCOLLIDED
`REOUEST IN
`CURRENT MINI
`SLOT?
`
`GRANT ACCESS TO
`HOST MAKING REOUEST
`
`MORE
`MINISLOTS TO
`EXAMINE 2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ex. 1015 / Page 30 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 29 of 34
`
`US 6,469,991 B1
`
`FIG. 1BB
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CONFIGURE N
`CONTENTION MINI
`SLOTS IN EACH
`UPLINK FRAME
`
`ALLOW FOR M
`ACCESS PRIORITY
`CLASSES AT AP
`
`
`
`EACH HOST WITH
`STACK LEVEL 10 AND
`ACCESS PRIORITY i
`TRANSMITS ACCESS
`REOUEST WITH
`PROBABILITY Pi
`
`RECEIVE ACCESS
`REOUESTS AT AP
`
`UNCOLLIDED
`REOUEST IN
`CURRENT MINI
`SLOT2
`
`PERFORM CONFLICT
`RESOLUTION
`AT MOBILES
`
`
`
`
`
`GRANT ACCESS TO
`"WINNING" HOST
`
`GRANT ACCESS TO
`HOST MAKING REOUEST
`
`
`
`
`
`MORE
`MINISLOTS TO
`EXAMINE2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ex. 1015 / Page 31 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 30 of 34
`
`US 6,469,991 B1
`
`FIG. 19
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CONNECTION
`REOUEST RECEIVED
`FROM REMOTE
`
`IS ST
`A HIGHEST
`PRIORITY
`REMOTE?
`
`TOTAL
`# ADMITTED
`CONNECTION
`< MAX?
`
`DOES
`ST ALLOW DIS
`CONNECTION?
`
`TOTAL
`ADMITTED
`CONNECTIONS
`< MAX?
`
`LEAST
`ONE AL READY
`AE e
`PRIORITY
`REMOTE
`
`
`
`REFUSE TO ADMIT
`NEW CONNECTION
`
`
`
`ADMITTED
`LOWER PRIORITY
`REMOTES <
`THRESHOLD2
`
`ADMIT NEW
`CONNECTION
`
`LEAST ONE
`LOWER PRIORITYNYES
`ALLOWS DIS-
`CONNECTION?
`
`
`
`DISCONNECTS A
`DISCONNECTABLE
`OWER PRIORITY
`CONNECTION
`
`1945
`
`REFUSE TO ADMIT
`NEW CONNECTION
`
`1935
`
`Ex. 1015 / Page 32 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 31 of 34
`
`US 6,469,991 B1
`
`FIG. 20
`
`
`
`2010
`
`2015
`
`2020
`
`
`
`
`
`MEASURE UPLINK
`FER AT AP
`
`MEASURE DOWNLINK
`FER AT REMOTE
`
`SEND DOWNLINK
`FER AT AP
`FROM REMOTE
`
`
`
`2025
`
`
`
`MORE
`REMOTES TO
`MEASURE2
`
`
`
`COMPUTE EOUIWALENT
`BANDWIDTHAT AP
`
`CAL CULATE EOUIVALENT
`NUMBER OF CONNECTIONS
`
`2050-N COMPUTE AT AP WHETHER
`OOS MAINTAINABLE
`IF ADMITTED
`
`
`
`NEW
`CONNECTION
`REOUEST?
`
`
`
`DENY ADMISSION
`TO CONNECTION
`
`2055
`
`
`
`
`
`OOS
`MAINTAIN
`ABLE
`
`N ADMIT NEW COLLECTION
`
`Ex. 1015 / Page 33 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 32 of 34
`
`US 6,469,991 B1
`
`FIG 21
`
`2110
`
`2115
`
`
`
`MEASURE UPLINK
`FER AT AP
`
`MEASURE DOWNLINK
`FER AT REMOTE
`
`2120-N
`
`SEND DOWNLINK
`FER FROM
`REMOTE TO AP
`
`
`
`2125
`
`
`
`MORE
`REMOTES TO
`MEASURE?
`
`2130
`
`SEND FLOW CONTROL
`MESSAGES BETWEEN AP AND
`AT LEAST ONE REMOTE
`
`AT AP WITH
`DELAY > THRES
`HOLD?
`
`YES
`
`DISCARD
`DELAYED
`PACKETS
`
`
`
`
`
`
`
`
`
`
`
`CONNECTIONS
`WITH PER >
`THRESHOLD?
`
`CONNECTION
`INTERRUPTIBLE
`
`DISCONNECT
`CONNECTION
`
`
`
`Ex. 1015 / Page 34 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 33 of 34
`
`US 6,469,991 B1
`
`
`
`REQUEST
`ACCESS
`CHANNEL
`y
`
`2220
`
`2230
`
`REMOTE HOST
`
`fi-
`
`REMOTE HOST
`
`' Ho
`
`---- SCHEDULER
`
`o
`
`- 2252
`
`2250
`
`WIRED HOST
`
`WIRED HOST
`
`2210
`
`2210
`
`
`
`2210
`
`2240
`
`2240
`
`2240
`
`Ex. 1015 / Page 35 of 61
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 22, 2002
`
`Sheet 34 of 34
`
`US 6,469,991 B1
`
`rives a
`'N packet
`EMPTY BUFFER OUEUE
`
`SOURCE
`BURSTY?
`
`MAKE ACCESS
`REOUEST
`
`
`
`ACK
`RECEIVED?
`
`TRANSMIT
`PERMIT
`RECEIVED?
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 23
`
`MAKE ACCESS REOUEST
`AND INFORM AP OF
`PACKET ARRIVAL RATE
`S CONNECTION
`DURATION TIME
`
`ACK
`RECEIVED?
`
`TRANSMIT
`PERMIT
`RECEIVED?
`
`
`
`SEND PACKET
`
`CONNECTION
`DURATION TIME
`OVER
`
`
`
`MORE
`PACKETS IN
`OUEUE?
`
`SEND PACKET
`
`SEND PACKET
`WITH PIGGYBACKED
`RESERVATION
`REQUEST
`
`Ex. 1015 / Page 36 of 61
`ERICSSON v. UNILOC
`
`

`

`1
`METHOD FOR OVERLOAD CONTROLINA
`MULTIPLE ACCESS SYSTEM FOR
`COMMUNICATION NETWORKS
`
`RELATED APPLICATIONS
`This application claims priority under Title 35, United
`States Code S120 from Provisional Application Serial No.
`60/061,790, filed Oct. 14, 1997, and Provisional Application
`Serial No. 60/077,741, filed Mar. 12, 1998. This application
`is one of Seven application having the Same Detailed
`Description and assignee that were filed on the Same date,
`the Seven related applications being application Ser. Nos.:
`09/083:675, 09/083,677, 09/083,797, 09/084,072, 09/683,
`792, 09/083,762 and 09/083,759.
`
`15
`
`FIELD OF THE INVENTION
`The present invention relates to a medium access control
`(MAC) protocol, known as an “on-demand multiple access
`fair queuing System, for application in a wireleSS commu
`nications network System. In particular, the invention relates
`to a method for managing queue overload in time and
`frequency division half- and full-duplex multiple acceSS
`wireleSS communications networks employing the “on
`demand multiple access fair queuing System.
`
`25
`
`BACKGROUND OF THE INVENTION
`WireleSS Services, Such as cellular voice and data and
`wireleSS LANs, are expected to enjoy rapid growth in the
`years to come. Third generation wireleSS networks designed
`to carry multimedia traffic are currently under intensive
`research, with the major goals being to provide SeamleSS
`communications, high bandwidth availability, and guaran
`teed Quality of Service (QoS) without any location or
`mobility constraints.
`FIG. 1 depicts a prior art wired network for data
`eXchange. Shown are the three existing business entities
`whose equipment, working in concert, is typically utilized
`today to provide remote internet access through modems to
`user computers. User computers 2 and user modems 4
`constitute end Systems. The first busineSS entity shown in
`FIG. 1 is the telephone company (telco) that owns and
`operates the dial-up plain old telephone system (POTS) or
`integrated services data network (ISDN). The telco provides
`a transmission medium in the form a of public Switched
`telephone network (PSTN) 6 over which bits or packets can
`flow between users and the other two business entities.
`The second business entity shown in FIG. 1 is the internet
`service provider (ISP). The ISP deploys and manages one or
`more points of presence (POPs) 8 in its service area, to
`which end users connect for network service. An ISP typi
`cally establishes a POP in each major local calling area in
`which the ISP expects to have subscribers. The POP 8
`converts message traffic from the PSTN 6 into a digital form
`to be carried over intranet backbone 10, which is either
`owned by the ISP or leased from an intranet backbone
`provider such as MCI, Inc. An ISP typically leases fractional
`or full T1 or T3 lines from the telco for connectivity to the
`PSTN. The POPs 8 and the ISP's media data center 14 are
`connected together over the intranet backbone 10 through
`router 12A. The data center 14 houses the ISP's web servers,
`mail Servers, accounting, and registration Servers, enabling
`the ISP to provide web content, e-mail, and web hosting
`Services to end users. Future value-added Services may be
`added by deploying additional types of Servers in the data
`center 14. The ISP maintains router 12A in order to connect
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,469,991 B1
`
`2
`to public internet backbone 20. In the existing model for
`remote access, end users typically have Service relationships
`with both their telco and their ISP, usually getting separate
`bills from each. End users access the ISP and, through the
`ISP, public internet 20, by dialing the nearest POP and
`running a communication protocol known as the Internet
`Engineering Task Force (IETF) point-to-point (PPP) proto
`col.
`The third business entity shown in FIG. 1 is a private
`corporation which owns and operates its own private intra
`net 18, accessed through router 12B. Corporate employees
`may remotely access corporate network 18 (e.g., from home
`or while on the road) by making POTS/ISDN calls to
`corporate remote access server 16 and running the IETF PPP
`protocol. For corporate access, end users pay only for the
`cost of connecting to corporate remote access Server 16. The
`ISP is not involved. The private corporation maintains router
`12B in order to connect an end user to either corporate
`intranet 18 or public internet 20.
`End users currently pay the telco for both the cost of
`making phone calls and the cost of a phone line into their
`home. End users also must pay the ISP for access to the
`ISP's network and services. Today, internet service provid
`erS offer internet access Services, web content Services,
`e-mail Services, content-hosting Services, and roaming to
`end users. Because of low margins and lack of market
`Segmentation based on features and price, ISPs are looking
`for value-added Services to improve margins. In the short
`term, equipment vendors want to be able to offer Solutions
`to ISPs that enable them to offer faster access, virtual private
`networking (the ability to use public networks Securely as
`private networks and connect to intranets), roaming
`consortiums, push technologies, and specific Quality of
`Service. In the longer term, it is desired to offer voice over
`internet and mobility. ISPs will then be able to use these
`value-added Services to escape from the low margin Strait
`jacket. Many of these value-added services fall into the
`category of network Services and can be offered only
`through the network infrastructure equipment. Other value
`added Services fall into the category of application Services
`which require Support from the network infrastructure, while
`Still others do not require any Support from the network
`infrastructure. In particular, Services like faster access, Vir
`tual private networking, roaming, mobility, Voice, Quality of
`Service, and QoS-based accounting all need enhanced net
`work infrastructure.
`WireleSS communications networks have the advantage of
`being able to extend the reach of wired networks. However,
`achievable bandwidths in wireleSS networks frequently lag
`behind those available in wired networks. Wired broadband
`Systems like asynchronous transfer mode (ATM) are capable
`of providing Services with different QoS (e.g., constant bit
`rate (CBR), variable bit rate (VBR), and available bit rate
`(ABR)) for enhanced Support of multimedia applications. It
`is desired to extend Such Services to wireleSS networkS.
`Research on merging ATM and wireleSS networks is there
`fore currently underway in many institutions and research
`laboratories. Many fundamental issues, affecting everything
`from the access layer to the transport layer, are being
`studied. Besides use of ATM as a transmission format at the
`air interface of a wireless network, ATM is also being
`considered for the wired infrastructure of cellular Systems.
`Such a wired ATM infrastructure would be capable of
`Supporting multiple access air interface technologies (e.g.,
`CDMA, TDMA, etc.).
`In a wireleSS network that Supports multimedia traffic, an
`efficient channel acceSS protocol needs to be maximize the
`
`Ex. 1015 / Page 37 of 61
`ERICSSON v. UNILOC
`
`

`

`3
`utilization of the limited wireless spectrum while still Sup
`porting the quality of Service requirements of all traffic.
`Several well-known channel access protocols are currently
`used in wireless data systems, such as Slotted Aloha, PRMA,
`etc. Slotted Aloha is a simple protocol but, because it does
`not attempt to avoid or resolve collisions between data users,
`its theoretical capacity is just 0.37. In addition, Slotted Aloha
`is unsuitable for efficient transmission of variable-length
`packets.
`Reservation-based protocols attempt to avoid and resolve
`collisions by dynamically reserving channel bandwidth for
`users needing to Send packets. Typically, in Such protocols
`a channel is divided into slots which are grouped into frames
`of N slots. A slot can be further Subdivided into k minislots.
`Normally, N of the slots will be used for reservation
`purposes while the remaining N-N Slots are data slots. The
`users that need to Send packets Send a reservation request
`packet in one of the M=N*k minislots. If the reservation
`request packet is Successful, then the user will be allocated
`a certain number of data slots until the user or the base
`Station releases the reservation. If the reservation request
`packet is not Successful, the user will use a conflict resolu
`tion method to retransmit the reservation request until it is
`Successfully transmitted.
`A multiple acceSS protocol for hybrid fiber-coaX networks
`has been proposed by Doshi et al. in “A Broadband Multiple
`Access Protocol for STM, ATM, and Variable Length Data
`Services on Hybrid Fiber-Coax Networks,” Bell Labs Tech
`nical Journal, Summer 1996, pp. 36-65. While sharing many
`issues with the wireleSS environment, this protocol does not
`completely address the unique problems encountered in the
`design of a wireleSS access Scheme, Such dealing with
`retransmissions over an error-prone wireleSS link and estab
`lishment of the transmission power level needed to ensure
`proper packet delivery. While this Scheme does