Note: Descriptions are shown in the official language in which they were submitted.
CA 02349115 2001-05-25
METHOD AND APPARATUS FOR DYNAMIC BANDWIDTH ALLOCATION TO
MIT~VIIZE FRAGMENTATION OF DATA PACKETS IN A BROADBAND
WIRELESS ACCESS SYSTEM THAT PROVIDES VOICE, DATA AND
MULTIMEDIA SERVICES
FIELD OF THE INVENTION
The present invention relates generally t.o the media access control protocol
applied to a bi-directional
communications medium, such as a Broadband Wireless Access system where
competing access stations
are connected via a bro;~dband wireless network to a common base station, to
communicate different types
of information, or traffic, such as voice, data, or control information. This
invention also relates to bi-
directional hybrid fibencoax networks, which are akin to broadband wireless
access networks in offering a
wide range of telecommunication services to residences and businesses.
BACKGROUND OF THE INVENTION
Currently a great deal of activity is directed towards broadband wireless
access networks to connect
multiple residential and business users using wireless systems in order to
provide new interactive
multimedia services, including telephony and data networking. The present
invention is related to establish
an upstream MAC (Me~3ia Access Control] protocol in the controller of the base
station such that
bandwidth is dynamically allocated for a mix of interactive and non-
interactive traffic types. The
conventional LAN protocols, for example CSMA/CD and R-ALOHA protocols, are not
suitable for use in
wireless systems because the wireless networks have separate upstream and
downstream channels, and the
subscribers can only listen to the downstream from the base station and
transmit in the allocated upstream.
The subscribers cannot listen directly tca the upstream transmissions from
other subscribers, and are
therefore incapable of coordinating their' transmissions by themselves. Usage
of the upstream is centrally
managed in the base station.
Many media access protocols have been proposed. The Data-Over-Cable Service
Interface
Specification (DOCSI~~) standard has been initially developed by CATV
operators and CableLabs. This
specification has begun. to find a home outside the TV market. Specifically, a
group of companies formed a
CA 02349115 2001-05-25
consortium, called the Wireless DSL Consortium, to produce an enhanced version
of the standard for
broadband wireless applications, and are currently under study by the IEEE
802.16 committee.
The upstream channel is modeled as a stream of mini-slots. Protocols have been
proposed to describe
the elements of requesting, granting, and using the upstream bandwidth. The
basic mechanism for assigning
bandwidth is the bandwidth allocation MAl' which describes the uses to which
the upstream mini-slots
must be put, and through which the base station controls access to these slots
by the access stations. Many
numbers of contiguous. slots may be granted to an access station to transmit
data. A larger MAC PDU may
need to be fragmented into smaller pieces that are individually transmitted
and then reassembled at the base
station.
The main objective of this inventic7n is to provide an optimum method of
bandwidth allocation in a
transmission system, and in particular in a. broadband wireless access
network, such that the fragmentation
of data packets is minimized to improve system performance while not
introducing an additional delay and
fitter into the real-time traffic.
SUMMARY OF THE INVENTION
Although there arc: protocols available that provide mechanisms for bandwidth
allocation for
multimedia traffic types, we propose another way to optimize the efficiency of
bandwidth allocation in an
access protocol that also minimizes the need for the fragmentation of larger
data packets. In particular, and
in accordance with achieving the objective of the present invention, a base
station communicates to access
stations via a broadband wireless access network using a media access control
protocol, which is modified
to support a variable number of voice mini-slots and a variable number of data
mini-slots in each frame.
The base station dynamically adjusts the positioning of mini-slots over a
period time for on-line voice
traffic in order to reduce its random distribution and random availability of
free mini-slots to be used for
other traffic types. As a result, the inventive; concept allows the base
station to efficiently utilize remaining
bandwidth on the communications channel for data traffic by minimizing their
fragmentation. It should be
noted that the fragmentation introduces overhead by adding extra fragmentation
header, and costs more
memory and CPU cycles for the packet assembly and disassembly functions. For
example, the number of
times all larger data packets are fragmented will introduce a bandwidth
overhead at least equal to the
product of this number and the fragmentation overhead. The objective of the
present invention is to
minimize the addition of this fragmentation overhead by minimizing the need
for fragmentation.
In an embodiment of the invention, a base station communicates to access
stations via a broadband
wireless access network using the conventional DOCSIS based media access
control protocol, which is
modified to dynamically allocate bandwidth such that the on-line voice traffic
mini-slots are positioned
back-to-back and the remaining mini-slots. can service larger data packets
without fragmentation. Any
presence of voice silence reflects in its mini-slat being dynamically utilized
for other traffic types and
affects the size of contiguous data slots available to service best effort
traffic. For example, less voice slots
provide larger data slots to service larger data traffic.
BRIEF DESCRIPTION OF THE DRAWINGS
Fig. 1 illustrates an exemplary arrangement of a broadband wireless access
network utilized in
accordance with the present invention, the network connecting a base station
to a plurality of access
stations for downstream signal broadcasting and allowing upstream information
transmission from the
individual access statians to the base station as well;
--2_
CA 02349115 2001-05-25
DETAILED DESCRIPTION OF THE INVENTION
The present invention encompasses a system utilizing a broadband link protocol
that specifies the
physical and media-acceas control layers over a broadband communication
network. A variety of traffic
types can be time division multiplexed and modulated for integrated transport
within the single radio
frequency channel. Thecae traffic types may include variable length data units
and constant bit rate voice
data units.
Although the present invention is particularly well suited for broadband
wireless access networks, and
shall be so described with respect to this application, the present invention
also applies to bi-directional
hybrid fiber/coax networks, which are akin to broadband wireless access
networks, in that the cable
modems do not usually directly listen to each other, but instead depend on the
headend for feedback.
Therefore, it is understood that the present invention may also function in
the context of a "headend" and a
"cable modem", where the base station may be replaced with a headend. and
access stations may be
replaced by cable modems.
Figures 1 through Ei, and the accompanying detailed description contained
herein, are to be used as an
illustrative example of a preferred embodirnent of the present invention.
Details of the structure may be
varied substantially without departing from the spirit of the invention.
Fig. 1 illustrates an exemplary point-to-multipoint broadband wireless access
(BWA) system
connected to IP backbone network with whuch the present invention may be used.
The system supports the
delivery of integrated data and voice services to business and residential
customers providing the operators
with the ability to provision differentiated :services such as "tall quality"
voice, "mission-critical" data, and
low priority "best-efforr." data. The base st;~tion is the central element of
the BWA network, providing
integrated multi-service access by dynamically scheduling packet flow between
access stations and
backbone networks. The access stations are the suite of local wireless
hardware and integrated software
products deployed at customer premises, which provide physical interfaces to
data and voice equipments.
The access stations may interface with the base station at several frequency
bands.
Fig. 2 illustrates an exemplary frame structure of the downstream transmission
of the upstream
bandwidth allocation m.ap (MAP) for the next upstream frame in accordance with
the present invention.
The bandwidth allocation map uses time units of "mini-slots" that represent
the byte-time needed for
transmission of a fixed number of bytes. This MAP is generated by the MAP
generator in the base station
based on the architecture presented in Fig 5. Successive MAPS are generated
each containing Information
,-
CA 02349115 2001-05-25
Elements. Each Information Element determines source identifier, usage and
duration of the time-slot
where each time slot can be used for bandwidth request, data transmission or
maintenance.
Fig. 3 illustrates an example of an overall interchange between the access
station and the base station
when the access station has data to transrr~it.
At time t,, the base station transmits a MAP whose effective period is between
t3 and t9. Among others,
there is a Request element starting at t5. This lets the access stations know
the starting contention period
during which they can transmit their request for bandwidth. As we can see, the
MAP is sent ahead of time
to compensate for various delays in the system (e.g. propagation delay and
processing delay).
At time tz, the access station receives the MAP and scans it for request
opportunities. If every access
station starts transmitting request at t4, there will be a collision in all
request periods. To avoid this, each
access station calculates t6 as a random offset and starts request at that
time. An access station determines
that a collision occurred when the next MAP fails to include acknowledgment of
the request.
Upon reception of this reduest at t~, the base station schedules it for
service in the next MAP.
At t~, the base station transmits a MAP whose effective starting time is t9.
Within this MAP, a data
grant for the access station will start at t"
At t8, the access station receives the MAP, detects the data grant in it and
starts transmission of data at
t,o. The access station transmits its data so that it will arrive at the base
station at t".
The methodology for slot allocation of multiple voice packets in upstream is
provided by an example
in Fig. 4. Fig. 4 (a) illustrates the conventional approach to reserve
bandwidth for voice packets. Bandwidth
is reserved for the exact time where the voice packet is available. This
approach results in a randomly
distributed voice packets among other types of data and management packets.
The random use of the voice
slots results in the free slots being of unpredictable and random size. This
increases the probability of
fragmentation of data packets and results in poor bandwidth utilization.
Fig. 4 (b) illustrad~s the new appro<tch where all the voice grants are
grouped together. Management of
the voice grants is done by a module separate from the MAP generator. The
total size of the voice grant is
still variable because new voice sessions may join, others may leave and some
others may switch between
voice and silence, but 'the starting point of the grant is always periodic. It
is obvious that this results in
larger free slots, and consequently the probability of having fragmented data
reduces considerably. The
size of the MAP being variable, the position and number of voice slots in a
MAP is also unpredictable. As
it is shown in Fig. 4, there may be MAPS with no voice slot and others with
one or more voice slots. Every
time the MAP generator creates a new M~~P, it keeps track of the time up to
which the upstream is
allocated (based on the; IEs inserted in t:he MAP). At the appropriate time
for the voice grant to be inserted
(every T seconds), it asks the voice manal;er for the number of voice grants
necessary at that time and
inserts it into the MAP' under creation. If the MAP generator has to transmit
the MAP without all the voice
grants, it will keep the remaining grants and puts them in the next MAP. One
major point stays to be
considered: Do we need to shift all the voice grants to have them allocated
during the big voice grant? The
answer is positive but only for the first grant of any voice session that has
been created or is switching from
silence to voice. The maximum delay introduced this way is not greater than
the period of the big voice
grant (being equal to the period of packet generation). This delay is
unnoticeable by the user because it is
the inter-packet delay ~~hange that is noticeable in interactive
communication. Each time an access station
starts transmission of voice packets, some delay is already introduced for the
base station, due to the
propagation delay in the upstream, to receive the request and assign bandwidth
to it. This covers the above
delay. As a consequen~:e any additional delay is not introduced in the system.
Fig. 5 illustrates a proposed architecture comprising of a MAP generator and a
Voice manager. The
MAP generator receives requests from different sources. Two types of requests
are considered in the figure:
~ requests for data transmission: the access station should obtain the
permission by requesting to
transmit and t:he MAP generator grants the request based on predefined
policies.
~ requests from the voice manager: the voice manager keeps track of all the
existing voice sessions
and the timin;; of each one. It providers the MAP generator the grants to be
serviced, at the right
time. The Mf~P generator is not responsible for the number of voice grants;
this is managed by the
voice manager which is already configured as to how much of the bandwidth is
reserved for voice
CA 02349115 2001-05-25
Now we will presc;nt the simulation results based on our methodology and on
conventional approach
that describe the number of times a dat<r packet is fragmented, and the number
of times fragmentation is
needed per second for data packets in the upstream, both with respect to voice
utilization when the total
bandwidth is utilized only for voice and data traffic. These results were
obtained based on the probability
distribution of incoming MAC data packet size as specified in Table 1. Voice
packets were considered to
be of fixed size and utilize exactly one mini slot of 101 bytes. It is also to
be mentioned that in the
simulation an amount of physical overhead size considered due to preamble and
guard time is 30 bytes, and
a fragmentation overhead considered is 16 bytes.
MAC PacketData Bytes Number of mini-slotsProbability
per of
Size mini-slot: per packet data packet
(b tes) -_ - occurrence
70 _ 1 (min,max*) 0.35
101
400 101 5 (min*) 0.45
8 (max**)
1500 101 16(min*) 0.20
28 (max**)
* when all mini slots are granted consecutively, there is only once a physical
overhead of
preamble ~~nd guard time, andl there is none fragmentation overhead; then
MACPacketSize + PhysicalOverheadSize
Nur,~berOfMinislotsPer-Packet =
DataBytesPerMinislot
** when only one mini slot is granted at a time, there is a physical overhead
of preamble and
guard time, and a fragmentation overhead in each mini slot; then
MACPacketSize
NumberOfMinislotsPerPacket -
~(DatczB~tesPerMinislot - PhysicalOverheadSize - FragmentationOverhead)
Table 1
Fig 6 illustrates a comparison of the number of times fragmentation of data
packets is needed per
second in the upstream for the conventional and proposed approaches. It is
seen that in the conventional
approach the number of fragmentations per second increases initially as the
percentage of total bandwidth
used for voice increases, and decreases as the total bandwidth is eventually
utilized mainly for voice traffic
and less and less is utilized for data traffic:. For different distribution of
data packet size the shape will be
the same but the maximum will be different. For example if the probability of
larger size data packets is
higher, the maximum number of fragment:ations per second will be high and the
curve will move higher.
Similarly, in the case of probability of smaller size data packets is high in
the distribution, the maximum
number of fragmentations per second will be lower and the curve will move
lower. The big advantage of
the proposed inventive; approach is that the number of fragmentations per
second is constant (except when
there is no voice traffic and when there are no data packets, in which case
there are no fragmentations) and
it does not depend on the percentage of bandwidth utilized for voice. This
number is related to the voice
slot period as 1/T.
i
