Apple Inc. v. WI-LAN Inc., et al

Filing 1

COMPLAINT against WI-LAN Inc. ( Filing fee $ 400, receipt number 0971-8709033.). Filed byApple Inc.. (Attachments: # 1 Exhibit 1, # 2 Exhibit 2, # 3 Exhibit 3, # 4 Exhibit 4, # 5 Exhibit 5, # 6 Civil Cover Sheet)(Scarsi, Mark) (Filed on 6/19/2014)

Exhibit 2

US008462723B2

(12) United States Patent
Stanwood et al.
(54)

METHODS AND SYSTEMS FOR

*Jun. 11, 2013

FOREIGN PATENT DOCUMENTS

TRANSMISSION OF MULTIPLE
MODULATED SIGNALS OVER WIRELESS
NETWORKS

EP
EP

0353759
0507384

2/1992
10/1992

(Continued)

(75) Inventors: Kenneth L. Stanwood, Cardiff by the
Sea, CA (US); James F. Mollenauer,
Newton, MA (US); Israel Jay Klein,

OTHER PUBLICATIONS
Ulm et al., “Data-Over-Cable Interface Speci?cations, Radio Fre
quency Interface Speci?cation”, Hewlett Packard Interim Speci?ca
tion Doc. Control No. SP-RFII0l-97032l, published Mar. 21, 1997

San Diego, CA (US); Sheldon L.

Gilbert, San Diego, CA (US)
Assignee: WI-LAN, Inc., Ottawa (CA)
(73)
( * ) Notice:

US 8,462,723 B2

(10) Patent N0.:
(45) Date of Patent:

by MCNS Holdings, L.P., Section 6, pp. 43-85.

Subject to any disclaimer, the term of this
patent is extended or adjusted under 35

(Continued)

U.S.C. 154(b) by 217 days.
This patent is subject to a terminal dis
claimer.

Primary Examiner * Hassan KiZou
Assistant Examiner * Roberta A Shand

(21) Appl. No.: 13/089,024
Apr. 18, 2011
(22) Filed:
Prior Publication Data
(65)

(74) Attorney, Agent, orFirm * Procopio, Cory, Hargreaves
& Savitch LLP

(57)

US 2011/0249585 A1
Oct. 13,2011
Related U.S. Application Data

(60)

A method and apparatus for requesting and allocating band

Division of application No. 12/645,937, ?led on Dec.
23, 2009, now Pat. No. 8,315,640, which is a
continuation of application No. 11/170,392, ?led on
Jun. 29, 2005, now Pat. No. 8,189,514, which is a
continuation of application No. 09/859,561, ?led on
May 16, 2001, now Pat. No. 6,956,834, which is a
continuation of application No. 09/316,518, ?led on

May 21, 1999, now Pat. No. 6,925,068.

(51)
(52)

width in a broadband wireless communication system. The
inventive method and apparatus includes a combination of
techniques that allow a plurality of CPEs to communicate

their bandwidth request messages to respective base stations.
One technique includes a “polling” method whereby a base
station polls CPEs individually or in groups and allocates
bandwidth speci?cally for the purpose of allowing the CPEs
to respond with bandwidth requests. The polling of the CPEs
by the base station may be in response to a CPE setting a

Int. Cl.
H04 W 4/00
U.S. Cl.

“poll-me bit” or, alternatively, it may be periodic. Another
technique comprises “piggybacking” bandwidth requests on

(2009.01)

USPC .......................... .. 370/329; 370/341; 455/450

(58)

ABSTRACT

Field of Classi?cation Search
None

bandwidth already allocated to a CPE. In accordance with this

technique, currently active CPEs request bandwidth using
previously unused portions of uplink bandwidth that is

See application ?le for complete search history.

already allocated to the CPE. The CPE is responsible for
distributing the allocated uplink bandwidth in a manner that

References Cited

accommodates the services provided by the CPE. By using a
combination of bandwidth allocation techniques, the present
invention advantageously makes use of the ef?ciency bene?ts
associated with each technique.

(56)

U.S. PATENT DOCUMENTS
3,949,404 A
4,464,767 A

4/1976 Fletcher et al.
8/1984 Bremer

9 Claims, 13 Drawing Sheets

(Continued)
50 2

504

BS

506

510

512

CPE

CPE

MAC

BS
LL-MAA

ig her Layer

514

Higher Layers

508
<—data for connection k

_

indiviJual poll

>

(BW grant in UL Subframe Map)

congestion

<—Bwidth request

indication, ~--—

516

If necessary

in UL Subframe Map
+-———data for onnection k

518

bandwidth grant/
<—-——data for connection k
V

US 8,462,723 B2
Page 3
7,548,534
7,562,130
7,636,571
7,693,093

B2
B2
B2
B2

6/2009
7/2009
12/2009
4/2010

Zimmerman et al.
Dillon et al.
Lee et a1.
Riedel et a1.

7,751,437
7,783,311
7,809,373
7,817,666
7,962,139
8,027,298
8,085,891
8,131,295
8,189,514
8,243,663
8,249,014
8,249,051

B2
B2
B2
B2
B2
B2
B2
B2
B2
B2
B2
B2

7/2010
8/2010
10/2010
10/2010
6/2011
9/2011
12/2011
3/2012
5/2012
8/2012
8/2012
8/2012

Spinar et a1.
Takiishi et al.
Park et al.
Spinar et a1.
Kangude et al.
Stanwood et al.
Owen
Wang et a1.
Stanwood et al.
Spinar et a1.
Stanwood et al.
Spinar et a1.

2001/0038620
2002/0080816
2004/0213197
2005/0047368
2005/0089064
2005/0111409
2006/0002336
2008/0049678
2008/0232342
2008/0232391
2008/0253394
2008/0268844
2009/0168802
2009/0175235
2009/0207795
2010/0150093
2010/0150094
2010/0157928
2011/0249586
2011/0249645
2011/0292904
2012/0033634

A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1

11/2001 Stanwood et al.

6/ 2002 Spinar et a1.
10/ 2004 Zimmerman et al.
3/ 2005 KotZin et al.
4/ 2005 Zimmerman et al.

5/2005 Spear et al.
1/2006 Stanwood et al.

2/2008
9/2008
9/2008
10/2008

Chindapol et al.
Spinar et a1.
Spinar et a1.
Spinar et a1.

10/2008 Ma et al.

7/ 2009 Spinar et a1.
7/ 2009 Spinar et a1.
8/ 2009 Spinar et a1.

G. Narlikar, et al., Designing Multihop Wireless Backhand Networks
with Delay Guarantees, Bell Labs, 2005, 1-4244-0222-0/06/$20.00
2006 IEEE, 12 pages.
J. Pons and J. Dunlop, Bit Error Rate Characterisation and Modelling
for GSM, IEEE 1998, pp. 3722-3727.
J.B. Andersen, et al., Prediction of Future Fading Based on Past

Measurements, Vehicular Technology Conference, VTC 99, vol. 1, p.
151-155.

J .M. Torrance, et al., Upper Bound Performance of Adaptive Modu
lation in a Slow Rayleigh Fading Channel, 2 pages.
L.H. Charles Lee, “Convolutional Coding, Fundamentals and Appli
cations”, Artech House, Inc., 1997, p. 11-51.
Lin et al., “Error Control Coding, Fundamentals and Applications”,

Prentice-Hall Computer Applications in Electrical Engineering
Series., 1993, pp. 315-349.
Lin, Ying-Dar, On IEEE 802.14 Medium Access Control Protocol,

IEEE Communications Surveys, http://www.comsoc.org/pubs/sur
veys, Fourth Quarter 1998, vol. 1 No. 1, pp. 1-10.
Mollenauer, James F. et al., “An Ef?cient Media Access Control
Protocol for Broadband Wireless Access Systems”, Submission to
IEEE 802.16 Broadband Wireless Access Working Group, Oct. 28,
1999, pp. 1-18.
Mollenauer, James F., et al., “MAC Proposal for IEEE 802.16.1”,
Submission to IEEE 802.16 Broadband Wireless Access Working
Group, Dec. 24, 1999, pp. 1-84.
P. Bender et al., CDMNHDR: A Bandwidth Ef?cient High Speed
Wireless Data Service for Nomadic Users, Communications Maga

6/ 2010 Stanwood et al.
6/ 2010 Stanwood et al.

Zine, IEEE, vol. 38, No. 7, Jul, 2000, pp. 70-77.

6/ 2010 Spinar et a1.

Adaptive Modulation, Dec. 2002, 92 pages.
Redl, et al., “An Introduction to GSM”, Artech House, Inc., 1995, pp.

10/2011 Stanwood et al.

10/2011 Spinar et a1.
12/2011 Stanwood et al.
2/2012 Spinar et a1.

FOREIGN PATENT DOCUMENTS
EP
EP
EP
EP
EP
GB
JP
WO
WO
WO
WO
WO
WO
WO
WO
WO

Elfeitori et al., A MAC Protocol for supporting real-time VBR traf?c
over IEEE 802.14 based HFC access networks, Published May 9-12,
1999, pp. 197-201.

0622924
0720405
0845916
0891060
1045559
2320162
11122289 A
WO92/22162
WO9810568
9837706 A2
9907170 A2
WO99/38343
WO99/39532
WO00/01188
WO0072626
WO01/33772

4/1994
7/1996
6/1998
1/1999
10/2000
12/1996
4/1999
12/1992
3/1998
8/1998
2/1999
8/1999
8/1999
1/2000
11/2000
5/2001

OTHER PUBLICATIONS

Qiu et al., Dynamic Reservation Multiple Access (DRMA): A New
Multiple Access Scheme for Personal Communication System
(PCS), Wireless Networks 2 (1996), pp. 117-128, J.C. BaltZer AG,
Science Publishers.
Kim, et al., PRMNDA: A New Media Access Control Protocol for

Wireless ATM, IEEE, Jun. 23, 1996, pp. 240-244.
US. District Court, Northern District of California, “Amended Com

P. Jain, On the Impact of Channel and Channel Quality Estimation on
84-85 and 95.

Superseded Data-Over-Cable Service Interface Speci?cations, Radio
Frequency Interface Speci?cation, SP-RFIv1.1-I01-990311
(DOCSIS1.1), dated Mar. 11, 1999, http://www.cablelabs.com/
speci?cations/SP/RFIv.1.1-I01-990311.pdf, pp. I310, 320 pages.
Wolf et al., “On the Weight Distribution of Linear Block Codes
Formed From Convolutional Codes”, IEEE, IEEE Transactions on

Communications, vol. 44:9, Sep. 9, 1996, pp. 1049-1051.
Sampei et al., Adaptive Modulation/TDMA Scheme for Personal
Multi-Media Communication System, Proceedings of the Global
Telecommunications Conference, US, New York, IEEE, Nov. 28,
1994, pp. 989-993.
Ue et al., Symbol Rate and Modulation Level Controlled Adaptive
Modulation/TDMNTDD for Personal Communication Systems,

Proceedings of the Vehicular Technology Conference, US, New
York, IEEE, vol. Conf. 45, Jul. 25, 1995, pp. 306-310.
Papadopoulos et a1 ., “Reduction of Mixed Co -channel Interference in

Microcellular STDD Systems”, Vehicular Technology Conference,
1995 IEEE 45.sup.th, vol. 2, pp. 759-763.
United States District Court, Southern District of Florida. Wi-LAN
USA, Inc. and Wi-LAN, Inc., Plaintiffs, v. HTC Corporation, and
HTC America, Inc., Defendants. “Complaint” Entered Dec. 6, 2012.
Case No. 1:12-cv-24319-KMM. 6 pages.

United States District Court, Southern District of Florida. Wi-LAN

USA, Inc. and Wi-LAN, Inc., Plaintiffs, v. Apple Inc., Defendant.
“Complaint” Entered Dec. 6, 2012. Case No. 1: 12-cv-24318-KMM.
6 pages.

United States District Court, Southern District of Florida. Wi-LAN
USA, Inc. and Wi-LAN, Inc., Plaintiffs, v. Sierra Wireless America,
Inc., Defendant. “Complaint” Entered Dec. 6, 2012. Case No. 1: 12

plaint for Declaratory Judgment Demand for Jury Trial” ?led Sep. 30,

cv-24320-KMM. 6 pages.

2008 in Case No. 5:08-cv-4555, 20 pages.

United States District Court, Southern District of Florida. Wi-LAN
USA, Inc. and Wi-LAN, Inc., Plaintiffs, v. Telefonakz‘iebolaget LM

Harry J .R. Dutton, P Leuhard, Asynchronous Transfer Mode (ATM)
Technical Overview, 2.sup.nd Edition, Prentice Hail Oct. 1995,

Chap, 3,pp, 21-25.

Ericsson, and Ericsson Inc., Defendants. “Complaint” Entered Oct.

1948.

1, 2012. Case No. 1:12-cv-23569-DMM. 7 pages.
United States District Court, Southern District of Florida. Wi-LAN
USA, Inc. and Wi-LAN, Inc., Plaintiffs, v. Alcatel-Lucent USA Inc.,
Defendant. “Complaint” Entered Oct. 1, 2012. Case No. 1:12-cv

Conti et al., E-DCP, an extension of the distributed-control polling

23568-CMA. 7 pages.

C.E. Shannon, “A Mathematical Theory of Communication”, Bell

System Technical Journal, pp. 379-423 (Part 1), 623-656 (Part 2), Jul.

MAC protocol (DCP) for integrated services, published 1994, pp.
7 1 1 -7 19.

* cited by examiner

US. Patent

Jun. 11,2013

112

Sheet 1 0f 13

US 8,462,723 B2

110

1IF GURE

nuance

112
112

104 cseilte
a

C
1-1
_

1..

‘

US. Patent

Jun. 11, 2013

Sheet 3 0f 13

US 8,462,723 B2

Modulation
Transition

Tx/Rx
Transition

Gap
302

304

J

Gap

/

1

Frame
Control

Header
(CAM-4)

306

306'

l

Data

Data

Data

(QAM-4)

(QAM-16)

(QAM~64)

l

304'

/
302

P'eambb
I

\

PHY
Control

304"

MAC
Control

r

l

1

l

J

310

312

\
314

300

FIGURE 3

308

US. Patent

Jun. 11,2013

Sheet 4 0f 13

US 8,462,723 B2

CPE
406

402

404

.

Transition

40a

TX/RX
4063'

Transition

i

Registration

Bggd‘ljgh

Contention

C

Gap

Slots

q

.

ontentlon
Slots

(QAM-4)

(QAM4)

Gap \

CPE1

CPE N

Scheduled

Scheduled

Data

Data

(QAM-CPE 1)

(QAM-CPE N)
AL

408"

Access Burst

. .

COlliSlOl’l

Access Burst

Bandwidth \ .

Request

Collision

400

FIGURE 4

406"

US. Patent

Jun. 11,2013

Sheet 6 0f 13

6 U0

. .

US 8,462,723 B2

.

individual PO/ll?

\

of CPEs g

602

r604
More BW

{.614

available for

Set up poll to

. .

.

initiate multioasl

and Mada?“

polling algorithm.

individual CPE &
mark as polled.

I
At GPE's

operational
modulation

,nac N8 s
“loaf
7

614 '3

PHY/MAC DAM-4 DAM-16 DAM-64
CONTROL

Data _ Data

Data

\
_

PHY

MAC

Pmmble Control 00mm!
3021

400'

. .

\

/314

/

-

'

. .

"84”" Map

H

BW requests in

.

scheduled CPE

OPE k additional BW/wocatlon
r622‘
Resg Cont BW Req P -1 CPE-Z : OPEN
lots . Slots
.3 _
406/ Datan. Data 5186

400/

430

PHY

62th

as

Use BW 'allocation

MAC

algorithm?‘

400 \ uptlink Map
CPE k BWAllocation

uplink time.

ow H‘eoest

PHY/MAC (JAM-4 (JAM-16 QAM~64
CONTROL Data
Data
Data
.
Preamble

. .

Await individual

subl‘rame map.
FIG, 6

%

US. Patent

Jun. 11,2013

402" 404"

\

\

410

406"

Sheet 7 0f 13

US 8,462,723 B2

406'"

i

8096 wmmow o mxo omww.“ Eouxo 3vmm nEmxo mwvwm mnox momwm
‘\X Scheduled CPE Uplink Traftic
Broadcast Bandwidth Request Contention Slots

Muiticast Group OxFOA1 Bandwidth Request Contention Slots
Multicast Group OxFOOO Bandwidth Request Contention Slots

Registration Contention Slots

400"

FIGURE 7

US. Patent

Jun. 11,2013

Sheet 8 0f 13

WIN

US 8,462,723 B2

Multicast and

bmadcast polling
B02

(806
Poll next multicast
group in MAC

-

Control black.

available for
broadcast

Ils

Place broadcast
oil in MAG
0mm] block.

PHY/MAC LIAM-4 ‘(JAM-16 (JAM-6
CONTROL

Data

. Data . Data

PHY

MAC [314

P'eamb/e Comm! Control
302/

“

400 \ uqnk Map
Multicast or Broadcast Poll

He Cant 8W Ban @1151

sglots . Slots

Data

Request

OPE-2 ' CPEN

Data": Data

Common SIMS

forBWrequesrs.

Valid (non
OPE ID

co/lis'ion) BW

Connection ID
Amount
PHY/MAC HAM-4 (JAM-16 (JAM-64

CONTROL Data

Data

;

Data

-

”Si_,,Bg”Z,,-‘i,’,?,°§"””
5U fame ma .

Preamble Gontm! Comm/n

p

F168

US. Patent

Jun. 11,2013

Sheet 9 0f 13

US 8,462,723 B2

Pol! Me Bit Usage
902

["904

8§311 ga

exnagste

Connection _= first _

connection

9123
Yes
Set poll~me bit in
available packet.
916\

,

L__Oonnecti0n 7—- Next 7

CONNECTION

914

Attempt

piggyback/ng first

'

US. Patent

Jun. 11, 2013

Sheet 11 0f 13

US 8,462,723 B2

950

l Piggybacking 5
V

"

952

PE nee

additional
andwidth
Yes

Insert BW

request(s).

No
962 ——

Use Poll Me Bit

Any Packets

No
960

Await polling by/
BS

964

FIGURE 11

US. Patent

Jun. 11,2013

Sheet 12 0f 13

III

Queues

ItnAAh/IAFC‘

US 8,462,723 B2

Ld

lll 1\III\I\ |\nl\r'\ cummme

— Q08 1 +

LL-MAA MAC Sublayer

— QoS 2 —>

(1 instance per physical channel)

0
I

-—-

-> \

Q08“
Phy Channel 2

2

g

.
BW Avall —: [BW(control messages)+
BW(CPE 1, Q08 1) +...~|~
BW(CPE k, Q08 1)];

QOS ; Q05 2'.

Queues

%

‘2°

— QOS1 —>

‘

—'

e

— Q08 2 +

'

E

.g

:

'5)

g

‘:E

:5

__

While BW Avail && Qos >: lowest QoS
(

aw Needed = BW(QOS);

'

+

If BW Needed > BW Avail

QOS n

g

(

0
O
0

BW Avail = 0,
.
Use fairness algorlthm;
.

Notify l-[L-MAA;

Phy Channel]

)

Queues
— Q08 1 —> /

Else
(

— Q08 2 —>

BW Avail -= BW Needed;

:
HL-MAA

——

MAC

QOS++,'

'

+

)

QoS n

)

sublayer
‘mw

Preamble

PHY
MAC
Control Control

OPE 1
Q03 1

_
Order Allocated Bandwldth;

OPE 1
Q08 2 to n

°"

CPE k
Q03 1

as Space Allows

CPE k
Q05 2 to n

as Space Allows

Order by Modulation
Control

Data

Data

Data

(QAM-4)

(QAM-M1)

(QAM-M2)

(QAM-M3)

FIGURE 12

_

US 8,462,723 B2
1

2

METHODS AND SYSTEMS FOR
TRANSMISSION OF MULTIPLE
MODULATED SIGNALS OVER WIRELESS
NETWORKS

band Wireless communication system is described in the co

pending application and is shoWn in the block diagram of
FIG. 1. As shoWn in FIG. 1, the exemplary broadband Wire
less communication system 100 includes a plurality of cells
102. Each cell 102 contains an associated cell site 104 that
primarily includes a base station 106 and an active antenna

CROSS-REFERENCE TO RELATED
APPLICATION

array 108. Each cell 102 provides Wireless connectivity
betWeen the cell’ s base station 106 and a plurality of customer

This application is a divisional of 12/645,937, ?led Dec.
23, 2009, Which is a continuation of US. patent application
Ser. No. 11/170,392, ?led Jun. 29, 2005, Which is a continu
ation of US. patent application Ser. No. 09/859,561, ?led
May 16, 2001, now US. Pat. No. 6,956,834, Which is a
continuation of US. patent application Ser. No. 09/316,518,
?led May 21, 1999, now US. Pat. No. 6,925,068, the disclo

premises equipment (CPE) 110 positioned at ?xed customer
sites 112 throughout the coverage area of the cell 102. The
users of the system 100 may include both residential and
business customers. Consequently, the users of the system

have different and varying usage and bandWidth requirement
needs. Each cell may service several hundred or more resi
5

dential and business CPEs.
The broadband Wireless communication system 100 of
FIG. 1 provides true “bandWidth-on-demand” to the plurality
of CPEs 110. CPEs 110 request bandWidth allocations from
their respective base stations 106 based upon the type and

20

quality of services requested by the customers served by the

sures of Which are incorporated herein by reference in its

entirety.
BACKGROUND OF THE INVENTION

1. Field of the Invention
This invention relates to Wireless communication systems,
and more particularly to a method and apparatus for e?i
ciently allocating bandWidth betWeen base stations and cus
tomer premises equipment in a broadband Wireless commu

nication system.
2. Description of Related Art
As described in US. Pat. No. 6,016,311, by Gilbert et al.,
issued Jan. 18, 2000, entitled “Adaptive Time Division
Duplexing Method and Apparatus for Dynamic BandWidth

CPEs. Different broadband services have different bandWidth

and latency requirements. The type and quality of services
available to the customers are variable and selectable. The
amount of bandWidth dedicated to a given service is deter
25

mined by the information rate and the quality of service

30

required by that service (and also taking into account band
Width availability and other system parameters). For
example, T1-type continuous data services typically require a
great deal of bandWidth having Well-controlled delivery
latency. Until terminated, these services require constant

Allocation Within a Wireless Communication System,”

bandWidth allocation on each frame. In contrast, certain types

hereby incorporated by reference, a Wireless communication

of data services such as Internet protocol data services (TCP/
IP) are bursty, often idle (Which at any one instant requires
Zero bandWidth), and are relatively insensitive to delay varia

system facilitates tWo-Way communication betWeen a plural
ity of subscriber radio stations or subscriber units (?xed and
portable) and a ?xed netWork infrastructure. Exemplary com
munication systems include mobile cellular telephone sys

35

tems, personal communication systems (PCS), and cordless
telephones. The key objective of these Wireless communica
tion systems is to provide communication channels on
demand betWeen the plurality of subscriber units and their
respective base stations in order to connect a subscriber unit
user With the ?xed netWork infrastructure (usually a Wire-line

40

system). In the Wireless systems having multiple access
schemes a time “frame” is used as the basic information

transmission unit. Each frame is sub-divided into a plurality
of time slots. Some time slots are used for control purposes
and some for information transfer. Subscriber units typically
communicate With the base station using a “duplexing”

45

50

are commonly referred to as “doWnlink” transmissions.
Transmissions from the subscriber unit to the base station are

commonly referred to as “uplink” transmissions. Depending
upon the design criteria of a given system, the prior art Wire
less communication systems have typically used either time

55

requests. If uncontrolled, the bandWidth allocation requests
Will detrimentally affect system performance. If left
unchecked, the bandWidth required to accommodate CPE
bandWidth allocation requests Will become disproportion
ately high in comparison With the bandWidth allocated for the
transmission of substantive tra?ic data. Thus, the communi
cation system bandWidth available to provide broadband ser

vices Will be disadvantageously reduced.

division duplexing (TDD) or frequency division duplexing
(FDD) methods to facilitate the exchange of information
betWeen the base station and the subscriber units. Both the
TDD and FDD duplexing schemes are Well knoWn in the art.
Recently, Wideband or “broadband” Wireless communica

any given time. Consequently, requests for changes to the
uplink bandWidth allocation are necessarily frequent and
varying. Due to this volatility in the uplink bandWidth
requirements, the many CPEs serviced by a selected base
station Will need to frequently initiate bandWidth allocation

scheme thus allowing the exchange of information in both
directions of connection.
Transmissions from the base station to the subscriber unit

tions When active.
Due to the Wide variety of CPE service requirements, and
due to the large number of CPEs serviced by any one base
station, the bandWidth allocation process in a broadband
Wireless communication system such as that shoWn in FIG. 1
can become burdensome and complex. This is especially true
With regard to the allocation of uplink bandWidth. Base sta
tions do not have a priori information regarding the band
Width or quality of services that a selected CPE Will require at

60

Therefore, a need exists for a method and apparatus that
can dynamically and e?iciently allocate bandWidth in a
broadband Wireless communication system. The method and
apparatus should be responsive to the needs of a particular
communication link. The bandWidth needs may vary due to

tions netWorks have been proposed for providing delivery of

several factors, including the type of service provided over the

enhanced broadband services such as voice, data and video
services. The broadband Wireless communication system
facilitates tWo-Way communication betWeen a plurality of
base stations and a plurality of ?xed subscriber stations or

link and the user type. The bandWidth allocation method and
apparatus shouldbe e?icient in terms of the amount of system

Customer Premises Equipment (CPE). One exemplary broad

65

bandWidth consumed by the actual bandWidth request and
allocation process. That is, the plurality of bandWidth
requests generated by the CPE should consume a minimum

US 8,462,723 B2
3

4

percentage of available uplink bandwidth. In addition, the
bandwidth allocation method and apparatus should respond

bandWidth request process. There are a number of means by

to bandWidth requests in a timely manner. BandWidth should

associated base station.

be allocated to high priority services in a suf?ciently short
time frame to maintain the quality of service speci?ed by the
CPE. Further, the bandWidth allocation method and apparatus
should be capable of proces sing an arbitrarily large number of
bandWidth allocation requests from a relatively large number
of CPEs. For example, in the system shoWn in FIG. 1, as many

One such means uses a “polling” technique Whereby a base
station polls one or more CPEs and allocates bandWidth spe

Which a CPE can transmit a bandWidth request message to an

ci?cally for the purpose of alloWing the CPEs to respond With
a bandWidth request. The polling of the CPEs by the base
station may be in response to a CPE setting a “poll-me bit” or,

alternatively, it may be periodic. In accordance With the
present invention, periodic polls may be made to individual

as one hundred CPEs may be alloWed to be simultaneously

CPEs, to groups of CPEs, or to every CPE on a physical

active, coordinating their transmissions on the uplink. Fur

channel. When individually polling a CPE, the base station
polls an individual CPE by allocating uplink bandWidth in an

thermore, the system can accommodate approximately one
thousand CPEs on the physical channel. Therefore, the need
exists for a bandWidth allocation method and apparatus that
can process and respond to the bandWidth allocation requests

generated by a large number of CPEs.
Some prior art systems have attempted to solve bandWidth
allocation requirements in a system having a shared system
resource by maintaining logical queues associated With the

uplink sub-frame map to alloW the CPE to respond With a

bandWidth request. Similarly, in group polling, the base sta

tion polls several CPEs by allocating uplink bandWidth in the
uplink sub-frame map to alloW the CPEs to respond With a
bandWidth request. The CPEs must contend for the allocated
bandWidth if collisions occur. BandWidth allocations are not
20

various data sources requiring access to the shared system

resource. Such a prior art system is taught by Karol et al., in
US. Pat. No. 5,675,573, that issued on Oct. 7, 1997. More
speci?cally, Karol et al. teach a bandWidth allocation system
that alloWs packets or cells Within tra?ic ?oWs from different

25

sources that are contending for access to a shared processing
fabric to get access to that fabric in an order that is determined

technique, currently active CPEs request bandWidth using
previously unused portions of uplink bandWidth that is
30

access to the shared processing fabric in an order determined
secondarily on overall system criteria, such as a time of
arrival, or due date of packets or cells Within the traf?c ?oWs.
Packets or cells of data from each data source (such as a

bandWidth requesting device) are queued in separate logical
buffers While they aWait access to the processing fabric.

already allocated to the CPE. Alternatively, the bandWidth
requests can be piggybacked on uplink bandWidth already
allocated and currently being used by a data service. In accor
dance With this alternative, the CPE “steals” bandWidth
already allocated for a data connection by inserting band
Width requests in time slots previously used for data.
The CPE is responsible for distributing the allocated uplink
bandWidth in a manner that accommodates the services pro

A need exits for a bandWidth allocation method and appa

vided by the CPE. The CPE is free to use the uplink band

ratus for ef?ciently processing and responding to bandWidth
allocation requests. The bandWidth allocation method and
apparatus should accommodate an arbitrarily large number of

tions are transmitted implicitly by allocating bandWidth in the
uplink sub-frame map.
Another means used by the present invention in reducing
bandWidth consumed by the bandWidth request messages is
the technique of “piggybacking” bandWidth requests on
bandWidth already allocated to a CPE. In accordance With this

primarily on individual guaranteed bandWidth requirements
associated With each traf?c ?oW. In addition, the system
taught by Karol et al. alloW the different sources to gain

in the form of an explicit message that is communicated by
the base station to the CPEs, but rather the bandWidth alloca

Width that Was allocated to it in a manner that is different than
40

that originally requested or granted by the base station. The
CPE advantageously determines Which services to give band

CPEs generating frequent and varying bandWidth allocation

Width to and Which services must Wait for subsequent band

requests on the uplink of a Wireless communication system.
Such a bandWidth allocation method and apparatus should be
e?icient in terms of the amount of bandWidth consumed by

Width requests. One advantage of having the CPE determine
45

hoW to distribute its allocated bandWidth is that it relieves the
base station from performing this task. In addition, the com

munication overhead that is required by having the base sta

the bandWidth request control messages exchanged betWeen
the plurality of base stations and the plurality of CPEs. In
addition, the bandWidth allocation method and apparatus

tion instruct the CPE hoW to distribute its allocated bandWidth
is eliminated. By using a combination of bandWidth alloca

should respond to the bandWidth allocation requests in a
timely and accurate manner. The bandWidth allocation
method and apparatus should also be able to process an arbi

use of the ef?ciency bene?ts associated With each technique.
The base station media access control (“MAC”) allocates

trarily large number of bandWidth allocation requests gener
ated by a relatively large number of CPEs. The present inven

the doWnlink. Within the uplink and doWnlink sub-frames,

tion techniques, the present invention advantageously makes
available bandWidth on a physical channel on the uplink and

the base station MAC allocates the available bandWidth

tion provides such a bandWidth allocation method and

apparatus.

55

SUMMARY OF THE INVENTION

base station MAC maintains a set of queues for each physical
channel that it serves. Within each physical channel queue set,
the base station maintains a queue for each QoS. The queues
hold data that is ready to be transmitted to the CPEs present on

The present invention is a novel method and apparatus for
requesting and allocating bandWidth in a broadband Wireless
communication system. The method and apparatus reduces

the physical channel. The base station higher MAC control

the amount of bandWidth that must be allocated for band
Width request and bandWidth allocation purposes. The oppor
tunities for alloWing a CPE to request bandWidth are very

tightly controlled in accordance With the present invention.
The present invention utiliZes a combination of a number of

bandWidth request and allocation techniques to control the

betWeen the various services depending upon the priorities
and rules imposed by their quality of service (“QoS”). The

layers are free to implement any convenient fairness or tra?ic

shaping algorithms regarding the sharing of access betWeen
65

connections at the same QoS, Without impacting the base
station loWer MAC control layers. In determining the amount
of bandWidth to allocate at a particular QoS for a particular
CPE, the base station takes into account the QoS, modulation,

US 8,462,723 B2
5

6

and the fairness criteria used to keep an individual CPE from
using up all available bandwidth. In one embodiment, the

physical medium. The MAC determines When subscribers are
alloWed to transmit on the physical medium. In addition, if
contentions are permitted, the MAC controls the contention

base station attempts to balance the uplink/doWnlink band
Width allocations using an adaptive time-division duplexing

process and resolves any collisions that occur.

In the system shoWn in FIG. 1, the MAC executed by
softWare present in the base stations 106 (in some embodi

technique (ATDD).
The uplink bandWidth allocation method is very similar to
the doWnlink bandWidth allocation except that, rather than
being maintained by the base station, the data queues are
distributed across and maintained by each individual CPE.
Rather than check the queue status directly, the base station
preferably receives requests for bandWidth from the CPEs

ments, the softWare may execute on processors both in the

base stations and the CPE) control the transmission time for
all of the CPEs 110. The base stations 106 receive requests for
transmission rights and grant these requests Within the time
available taking into account the priorities, service types,
quality of service and other factors associated With the CPEs
110. As described above in the background of the invention,
the services provided by the CPEs 110 TDM information

using the techniques described above.
BRIEF DESCRIPTION OF THE DRAWINGS

such as voice trunks from a PBX. At the other end of the

service spectrum, the CPEs may uplink bursty yet delay

FIG. 1 shoWs a broadband Wireless communication system

tolerant computer data for communication With the Well

adapted for use With the present invention.

knoWn World Wide Web or Internet.

FIG. 2 shoWs a TDD frame and multi-frame structure that

can be used by the communication system of FIG. 1 in prac

ticing the present invention.

20

FIG. 3 shoWs an example of a doWnlink sub-frame that can

be used by the base stations to transmit information to the
plurality of CPEs in the Wireless communication of FIG. 1.
FIG. 4 shoWs an exemplary uplink sub-frame that is
adapted for use With the present bandWidth allocation inven
tion.

are referred to as the Uplink Sub-frame Maps and DoWnlink
Sub-frame Maps. The MAC must allocate su?icient band
25

Width to accommodate the bandWidth requirements imposed
by high priority constant bit rate (CBR) services such as T1,
E1 and similar constant bit rate services. In addition, the
MAC must allocate the remaining system bandWidth across
the loWer priority services such as Internet Protocol (IP) data
services. The MAC distributes bandWidth among these loWer

FIG. 5 is a How diagram shoWing the information exchange

sequence used in practicing the individual polling technique
of the present invention.
FIG. 6 is a How diagram shoWing the individual polling

The base station MAC maps and allocates bandWidth for
both the uplink and doWnlink communication links. These
maps are developed and maintained by the base station and

30

priority services using various QoS dependent techniques

technique of the present invention.
FIG. 7 shoWs an exemplary uplink sub-frame map that is

such as fair-Weighted queuing and round-robin queuing.
The doWnlink of the communication system shoWn in FIG.

used to facilitate the present multicast/broadcast bandWidth

1 operates on a point-to-multi-point basis (i.e., from the base
station 106 to the plurality of CPEs 110).As described in US.
Pat. No. 6,016,311, by Gilbert et al., issued Jan. 18, 2000,

allocation technique.
FIG. 8 is a How diagram shoWing the multicast and broad

35

cast polling technique of the present invention.

entitled “Adaptive Time Division Duplexing Method and

FIG. 9 is a How diagram shoWing use of a “poll-me” to
stimulate polling of a CPE in accordance With the present
invention.
FIG. 10 shoWs the message sequence that is used by the

Apparatus for Dynamic BandWidth Allocation Within a Wire
less Communication System,” the central base station 106
40

present invention in requesting polls using the “poll-me” bit.
FIG. 11 is a How diagram shoWing the bandWidth request
piggybacking process of the present invention.

given frequency channel and antenna sector, all stations
receive the same transmission. The base station is the only

FIG. 12 shoWs the doWnlink bandWidth allocation method

used by the present invention.

45

tions, except for the overall time-division duplexing that
divides time into upstream (uplink) and doWnstream (doWn
link) transmission periods. The base station broadcasts to all

used by the present invention.
Like reference numbers and designations in the various
draWings indicate like elements.
50

DETAILED DESCRIPTION OF THE INVENTION

and examples shoWn should be considered as exemplars,
55

The preferred embodiment of the present invention is a
method and apparatus for allocating bandWidth in a broad
band Wireless communication system. One very important
performance criterion of a broadband Wireless communica
tion system, and any communication system for that matter
having a physical communication medium shared by a plu
rality of users, is hoW e?iciently the system uses the physical

(“MA ”) protocol typically controls user accesses to the

of the CPEs in a sector (and frequency). The CPEs monitor
the addresses in the received messages and retain only those
addressed to them.
The CPEs 110 share the uplink on a demand basis that is

Throughout this description, the preferred embodiment

medium. Because Wireless communication systems are
shared-medium communication netWorks, access and trans
mission by subscribers to the netWork must be controlled. In
Wireless communication systems a Media Access Control

transmitter operating in the doWnlink direction, hence it
transmits Without having to coordinate With other base sta

FIG. 13 shoWs the uplink bandWidth allocation method

rather than as limitations on the present invention.

includes a sectored active antenna array 108 Which is capable
of simultaneously transmitting to several sectors. In one
embodiment of the system 100, the active antenna array 108
transmits to six independent sectors simultaneously. Within a

controlled by the base station MAC. Depending upon the
class of service utiliZed by a CPE, the base station may issue
a selected CPE continuing rights to transmit on the uplink, or

the right to transmit may be granted by a base station after
receipt of a request from the CPE. In addition to individually
addressed messages, messages may also be sent by the base
station to multicast groups (control messages and video dis
tribution are examples of multicast applications) as Well as
broadcast to all CPEs.

65

Within each sector, in accordance With the present inven
tion, CPEs must adhere to a transmission protocol that mini
miZes contention betWeen CPEs and enables the service to be
tailored to the delay and bandWidth requirements of each user
application. As described beloW in more detail, this transmis

US 8,462,723 B2
7

8

sion protocol is accomplished through the use of a polling
mechanism, With contention procedures used as a backup
mechanism should unusual conditions render the polling of

hyper-frame structures can be used With the present inven

all CPEs unfeasible in light of given delay and response-time

202, and each hyper-frame comprises thirty-tWo multi

constraints. Contention mechanisms can also be used to avoid

frames 206. Exemplary doWnlink and uplink sub-frames used
to in practicing the present invention are shoWn respectively

tion. For example, in another embodiment of the present
invention, each multi-frame 206 comprises sixteen frames

individually polling CPEs that are inactive for long time

periods. The polling techniques provided by the present

in FIGS. 3 and 4.

inventive method and apparatus simpli?es the access process

DoWnlink Sub-Frame Map

and guarantees that service applications receive bandWidth
allocation on a deterministic basis if required. In general, data

FIG. 3 shoWs one example of a doWnlink sub-frame 300
that can be used by the base stations 106 to transmit informa

service applications are relatively delay-tolerant. In contrast,

tion to the plurality of CPEs 110. The base station preferably

real-time service applications such as voice and video ser

maintains a doWnlink sub-frame map that re?ects the doWn

vices require that bandWidth allocations be made in a timely

link bandWidth allocation. The doWnlink sub-frame 300 pref
erably comprises a frame control header 302, a plurality of

manner and in adherence to very ti ghtly-controlled schedules.

doWnlink data PSs 304 grouped by modulation type (e.g., PS
304 data modulated using a QAM-4 modulation scheme, PS
304' data modulated using QAM-16, etc.) and possibly sepa
rated by associated modulation transition gaps (MTGs) 306

Frame MapsiUplink and DoWnlink Sub-Frame Mappings
In one preferred embodiment of the present invention, the
base stations 106 maintain sub-frame maps of the bandWidth
allocated to the uplink and doWnlink communication links.
As described in US. Pat. No. 6,016,311, by Gilbert et al.,
issued Jan. 18, 2000, entitled “Adaptive Time Division

20

Duplexing Method and Apparatus for Dynamic BandWidth
Allocation Within a Wireless Communication System,” the
uplink and doWnlink are preferably multiplexed in a time
division duplex (or “TDD”) manner. In one embodiment, a
frame is de?ned as comprising N consecutive time periods or

time slots (Where N remains constant). In accordance With
this “frame-based” approach, the communication system
dynamically con?gures the ?rst N.sub.1 time slots (Where N
is greater than or equal to N.sub.1) for doWnlink transmis
sions only. The remaining N.sub.2 time slots are dynamically

frame any one or more of the differently modulated data
blocks may be absent. In one embodiment, modulation tran
sition gaps (MTGs) 306 are 0 PS in duration. As shoWn in
FIG. 3, the frame control header 302 contains a preamble 310
25

the MAC (314).
30

example) and transmitted at the current operating modulation

35

40

scheme changes. Finally, as shoWn in FIG. 3, the Tx/Rx
transition gap 308 separates the doWnlink sub -frame from the
uplink sub-frame Which is described in more detail beloW.

Uplink Sub-Frame Map

lomon encoding method, is performed on the digital informa
tion over a pre-de?ned number of bit units referred to as
50

FIG. 4 shoWs one example of an uplink sub-frame 400 that
is adapted for use With the present bandWidth allocation
invention. In accordance With the present bandWidth alloca
tion method and apparatus, the CPEs 110 (FIG. 1) use the
uplink sub-frame 400 to transmit information (including
bandWidth requests) to their associated base stations 106. As
shoWn in FIG. 4, there are three main classes of MAC control
messages that are transmitted by the CPEs 110 during the
uplink frame: (1) those that are transmitted in contention slots

reserved for CPE registration (Registration Contention Slots
402); (2) those that are transmitted in contention slots

issued Jan. 18, 2000, entitled “Adaptive Time Division
Duplexing Method and Apparatus for Dynamic BandWidth
Allocation Within a Wireless Communication System,” in one

by QAM-16, folloWed by QAM-64. The modulation transi
tion gaps 306 contain preambles and are used to separate the
modulations. The PHY Control portion 312 of the frame
control header 302 preferably contains a broadcast message
indicating the identity of the PS 304 at Which the modulation

shoWn in FIG. 1) in practicing the present invention. As

information elements (PI). The modulation may vary Within
the frame and determines the number of PS (and therefore the
amount of time) required to transmit a selected PI.
As described in US. Pat. No. 6,016,311, by Gilbert et al.,

The doWnlink data PSs are used for transmitting data and
control messages to the CPEs 110. This data is preferably
encoded (using a Reed-Solomon encoding scheme for

used by the selected CPE. Data is preferably transmitted in a
pre-de?ned modulation sequence: such as QAM-4, folloWed

FIG. 2 shoWs a TDD frame and multi-frame structure 200
that can be used by a communication system (such as that

shoWn in FIG. 2, the TDD frame is subdivided into a plurality
of physical slots (PS) 204. In the embodiment shoWn in FIG.
2, the frame is one millisecond in duration and includes 800
physical slots. Alternatively, the present invention can be used
With frames having longer or shorter duration and With more
or feWer PSs. The available bandWidth is allocated by a base
station in units of a certain pre-de?ned number of PSs. Some
form of digital encoding, such as the Well-knoWn Reed-So

used by the physical protocol layer (or PHY) for synchroni
Zation and equaliZation purposes. The frame control header
302 also includes control sections for both the PHY (312) and

con?gured for uplink transmissions only (Where N.sub.2
equals N-N.sub.1). Under this TDD frame-based scheme, the
doWnlink sub-frame is preferably transmitted ?rst and is pre
?xed With information that is necessary for frame synchroni
Zation.

used to separate differently modulated data, and a transmit/
receive transition gap 308. In any selected doWnlink sub

55

reserved for responses to multicast and broadcast polls for

embodiment of the broadband Wireless communication sys

bandWidth allocation (BandWidth Request Contention Slots

tem shoWn in FIG. 1, the TDD framing is adaptive. That is, the

404); and those that are transmitted in bandWidth speci?cally
allocated to individual CPEs (CPE Scheduled Data Slots

number of PSs allocated to the doWnlink versus the uplink
varies over time. The present bandWidth allocation method
and apparatus can be used in both adaptive and ?xed TDD
systems using a frame and multi-frame structure similar to
that shoWn in FIG. 2. As shoWn in FIG. 2, to aid periodic

406).
The bandWidth allocated for contention slots (i.e., the con

tention slots 402 and 404) is grouped together and is trans
mitted using a pre-determined modulation scheme. For
example, in the embodiment shoWn in FIG. 4 the contention

functions, multiple frames 202 are grouped into multi-frames
206, and multiple multi-frames 206 are grouped into hyper
frames 208. In one embodiment, each multi-frame 206 com

slots 402 and 404 are transmittedusing a QAM-4 modulation.
65

The remaining bandWidth is grouped by CPE. During its

prises tWo frames 202, and each hyper-frame comprises

scheduled bandWidth, a CPE 110 transmits With a ?xed

tWenty-tWo multi-frames 206. Other frame, multi-frame and

modulation that is determined by the effects of environmental