Note: Descriptions are shown in the official language in which they were submitted.
CA 02341917 2004-02-10
METHOD AND APPARATUS FOR PACKET SIZE DEPENDENT LINK
ADAPTATION FOR WIRELESS PACKET
Technical Field
The invention relates to data systems communicating by wireless links and
more particularly to adapting the size and coding of packets in order to
reduce over-
l0 all delay when communicating data over the wireless links.
Background of the Invention
In wireless packet data systems such as Enhanced General Packet Radio
Service (EGPRS), selective Automatic Repeat Request (ARQ) is used for error
recovery over the wireless link. In an earlier analysis, Radio Link Control
(RI,C)
performance was usually characterized in terms of the throughput, while the
size of
the higher layer Protocol Data Units (PDUs) or packets to be transferred was
ignored.
In wireless packet data systems, such as Enhanced General Packet Radio
Service (EGPRS), selective ARQ is used for error recovery over the radio link;
see
for example K. Balachandran, R. Ejzak, and S. Nanda, "Efficient transmission
of
ARQ feedback for EGPRS radio link control," in IEEE Vehicular Technology
Conf., May 1999. Currently, nine Modulation and Coding Schemes (MCSs) have
been proposed for EGPRS with MCS-l having the most robust coding and MCS-9
having the least robust coding.
Each higher layer packet is segmented into multiple Radio Link Control
(RLC) blocks. The RLC block size and the number of RLC blocks transmitted in a
20 ms block period vary depending on the MCS chosen for transmission. For
example, the RLC block sizes for MCS-1 and MCS-2 are 22 octets and 2$ octets,
respectively. For MCS-1 to MCS-6, a single RLC block is transmitted in a 20ms
block period on each time slot. For MCS-7 to MCS-9, two RLC blocks are
CA 02341917 2001-03-19
_2.
K. Balachandran 14-7-19-2-42
transmitted in a 20 ms block period on each time slot. This state of the art
is known
from: A. Furuskar, S. Mazur, F. Muller and H. Olofsson, "EDGE: enhanced data
rates for GSM and TDMA/136 evolution," IEEE personal Communications, pp. 56-
66, June 1999; ETSI GSM 03.60, "Digital cellular telecommunications system
(phase 2+); General Packet Radio Service (GPRS); service description: stage
2";
and K. Balachandran, K. Conner, R. Ejzak, and S. Nanda, "A Proposal for EGPRS
Radio Link Control Using Link Adaptation and Incremental Redundancy," Bell
Labs
Technical Journal, vol. 4, no. 3, pp. 19-36, July-Sept. 1999. If mobile
stations are
mufti-slot capable, then multiple time slots (up to 8 in EGPRS) are available
for use.
to The RLC Block Error Rate (BLER) can be reduced significantly by using
more robust codes. The result of using robust schemes, such as MCS-1, is that
fewer rounds of retransmission are required to complete a transmission.
However,
stronger coding reduces the number of data bits that can be transmitted in one
RLC
block. Less robust schemes such as MCS-9 are able to pack more bits in a
single
RLC block, but operate at higher BLERs under typical channel conditions and
may
require more retransmissions to complete a transmission. For Selective ARQ,
the
throughput upper bound is R(1-Pe), where R is the transmission rate and Pe is
the
block error rate. This applies well to the transfer of large amounts of data
(for
example file transfer protocol (ftp) applications). However, for applications
such as
2o web browsing and telnet, the concern is with the delay in transfernng short
packets.
So, for transferring short packets, the long term throughput does not quantify
the
quality of service. In what follows, the EGPRS framework is assumed in order
to
study the tradeoffs between Forward Error Correction (FEC) and ARQ for
different
packet sizes from a delay perspective.
There have been several studies on the delay performance of selective repeat
(SR) ARQ. In M. E. Anagnostou and E. N. Protonotarios, "Performance analysis
of
the selective repeat ARQ protocol," IEEE Trans. on Communications, vol. 34,
no. 2,
pp. 127-135, Feb. 1986, an exact and an approximate analysis on RLC block
delay
was derived in the single slot case. In R. Fantacci, "Queueing analysis of the
selective repeat automatic repeat request protocol wireless packet network,"
IEEE
CA 02341917 2001-03-19
-3-
K. Balachandran 14-7-19-2-42
transactions on Vehicular technologies, vol. 45, no. 2, pp. 258-264, May 1996,
the
author analyzed the performance of the SR-ARQ in the Markov two-state channel.
Another approximation can be found in J. Chang and T. Yang, "End-to-end delay
of
an adaptive selective repeat ARQ protocol," IEEE Transactions on
Communications, vol. 42, no. 11, pp. 2926-2928, Nov. 1994. In all the above
referenced works, only delay for a block has been calculated.
The important measure is not the time (delay) for delivering a block of data.
Rather, the important measure is the time (delay) to communicate a message. To
come closer to the delay for a message, it is desirable to measure the delay
for in-
l0 sequence delivery of a higher layer packet, which contains multiple RLC
blocks.
Once a measure of the delay times of in sequence delivery of higher level
packets
containing multiple blocks is achieved, improvements in the method and
apparatus
for communicating blocks of data in the imperfect world of wireless
communications can be also be achieved. It is desirable to provide
improvements to
the method and apparatus for communicating messages made up of data blocks via
wireless communications in imperfect transmission/reception channel
conditions.
Summary of the Invention
Briefly stated in accordance with one aspect of the invention, the
aforementioned shortcoming of the art is overcome by providing a method for
2o reducing delay time of data delivery comprising the steps of storing at
least one data
packet to be transmitted over a link; transmitting a first segment of the data
packet at
a first modulation and coding scheme level; and transmitting a second segment
of
the data packet at a second modulation and coding scheme level which is more
robust.
In accordance with another aspect of the invention, the aforementioned
shortcoming of the art is overcome by providing an apparatus for reducing
delay
time of data delivery, comprising a buffer for storing at least one data
packet to be
transmitted over a link and a modulator and coder for modulating and coding a
first
segment of the data packet at a first modulation-and-coding level. The
modulator
and coder also modulating and coding a second segment of the data packet at a
CA 02341917 2001-03-19
-4-
K. Balachandran 14-7-19-2-42
second modulation-and-coding level which is more robust than the first
modulation-
and-coding level. The apparatus has a transmitter for transmitting the first
and
second segments. By using a more robust code for the second segment, the delay
time to the user is reduced.
Brief Description of the Drawing
FIG. 1 is a block diagram of a previously known wireless system.
FIG. 2 is a block diagram of a wireless system for practicing the invention.
FIG. 3 is a table of results for various MCS levels.
FIGS. 4-7 are results of simulations for various MCS levels.
l0 Detailed Description
Referring now to FIG. 1, system 10 has a base station 12 that is connected to
an antenna 13. System 10 is an EGPRS system. Antenna 13 both transmits and
receives wireless packet data over radio links. Antenna 13 is illustrated as
communicating data packets to and from radio equipped automobile 20, wireless
portable computer 30 and hand-held unit 40.
Base station 12 has a transceiver 14 for transmitting and receiving data with
other units. Transceiver 14 has a buffer 16 in which it stores each message to
be
transmitted. The data of a message is held in buffer 16 until all of the
message has
been properly received, which is defined as received without uncorrectable
errors, at
2o the destination of the message, such as automobile 20, computer 30 or hand-
held
device 40. If a data block becomes lost or corrupted during initial
transmission, a
re-transmission is requested by the destination unit. Such re-transmission
requests
are then fulfilled from data in the buffer 16. Once all of the message has
been
delivered, the buffer 16 is either cleared or simply marked as invalid until
it is
overwritten with different, valid data. Since buffers and link control units
controlling transmitting of data blocks have existed in previous systems, a
major
part of the present invention is a faster and more reliable method and system
for
providing data communications.
FIG. 2 shows a faster and more reliable method and system for data
3o communications. Base station 12' has the additional link adaptation unit 18
to help
CA 02341917 2001-03-19
-5-
K. Balachandran 14-7-19-2-42
provide the improvements . The link adaptation unit 18 has a buffer draining
monitor (not shown). The buffer draining monitor determines the time when the
data in buffer 16' is almost completely transmitted the first time. This is
the time
for the buffer draining monitor to signal the link adaptation unit 18 to
change the
MCS level of the transmission to a more robust one. Similarly, units 20', 30'
and
40' in their requests-to-transmit all indicate the size of their respective
messages to
be transmitted. Link adaptation unit 18 takes a similar action to change the
MCS
level the transmitting unit 20', 30' or 40' is using as the end portion of the
message
is reached.
l0 Link Adaptation unit 18 tests the radio link between the transceiver 14'
and
mobile units 20', 30' and 40' as a baseline way for radio link control (RLC)
to
operate. RLC at least selects an MCS level or levels to allow communication in
the
presence of noise on the radio link. As will be shown below, judicious RLC
selection of MCS levels during a message can achieve significant time savings,
i.e.
delay savings. Additionally, an analysis of the delay performance of selective
ARQ's as a function of packet size and the channel coding scheme is employed.
The
analysis has been verified through simulations, which have shown the
advantages of
the present invention.
The RLC ARQ procedure operates as follows. At a transmitter, e.g.
2o transmitter 14', each packet provided by the higher layer is segmented into
K RLC
blocks, each of the K RLC blocks is assigned a sequence number. The RLC blocks
are then queued in the transmitter buffer, e.g. buffer 16', in order to be
scheduled for
transmission. The transmitter maintains a window the size of which is
incremented
by one when an RLC block is transmitted and decremented by one when an RLC
block is acknowledged as received in sequence by the receiver. It is assumed
that
there is a maximum window size of W blocks beyond which the window size cannot
be incremented. At the initial transmission or retransmission of each RLC
block, a
timer (not shown) associated with that block is activated. If a block is
negatively
acknowledged after its timer expires, it is scheduled for retransmission.
Ideally the
3o timer is set equal to the round trip delay between transceiver 14' and
units 20', 30'
CA 02341917 2001-03-19
-6-
K. Balachandran 14-7-19-2-42
or 40', (or from one of the units 20', 30' or 40' to transceiver 14') which
includes
propagation and processing delays in both directions, to prevent propagation
and
processing retransmissions.
For example, if transmitter 14' polls receiver 20', 30' or 40', for feedback
every P block periods, receiver 20', 30' or 40' responds with an ARQ feedback
bitmap providing the ACK/NACK receipt status of each RLC block within the
window. The ARQ feedback message also includes the sequence number up to
which all RLC blocks have been received in sequence.
Further, for the below given analysis, the following assumptions are made:
l0 1. A quantity of B RLC blocks can be transmitted within a 20 ms block
period. This
number is a function of the MCS and the mufti-slot capability of the mobile
station.
2. The probability of error for each RLC block is given by Pe and RLC block
errors
are independent from one block to another block.
3. The timer expires after the round trip delay of T block periods.
4. The Window size W is greater than the size of the packet (i.e. W > K) so
protocol
stalling never occurs.
5. The polling period is P = 1. So every 20ms, the receiver sends back its
reception
status to the transmitter.
6. There are no errors in acknowledgments.
7. There are no undetected errors.
With these assumptions, the performance of system 10' between base station
12' and any unit 20', 30' or 40' may be characterized in terms of the packet
delay
(D) defined as the time period between the arnval of the packet at the RLC
layer and
the reception of acknowledgments to every RLC block comprising the packet.
Considering the operation conditions that each packet sees an empty buffer
(e.g. buffer 16') when it arrives and there is no packet queuing delay. If
only the
delay in queuing, transmitting and acknowledging RLC blocks is considered,
then
CA 02341917 2001-03-19
K. Balachandran 14-7-19-2-42
the packet delay can be written as:
D=A~T+T (1)
where A can be approximated as
1_ InK , K_58T
In Pe
A K ~ In BT - Pe + K K > BT
In Pe 1 _ Pe BT(1 _ Pe )
This is the approximation that is used for the delay in the rest of this
description.
CA 02341917 2001-03-19
.8.
K. Balachandran 14-7-19-2-42
An intuitive explanation of the approximation above for A(K) is as follows.
The delay of a packet
consists of two parts: the "draining delay" and the "tail delay". During each
round trip delay
period, if there is sufficient backlog, BT blocks are transmitted. On average,
the residual number
of blocks left for transmission decreases at a constant rate, i.e., by BT(1-
Pe), for every round trip
period. Therefore, it takes BT(1K Pe) round trips to drain the packet of size
K. So the "draining
delay" is BT(1K Pe ) round trips. However, when the residual number of blocks
falls to less than
BT, or if the packet length K is less than BT, the depletion rate is smaller
than BT(1-Pe), since in
every round trip, there are not enough blocks to fill up the transmission
interval. This "tail delay"
depends on the number of round trips it takes to successfully transmit the
remaining blocks when
the error rate is Pe. If the packet size is less than BT, the total delay only
consists of "tail delay"
which is dependent on the packet size. For larger packets, the total delay
consists of the draining
delay for K - BT blocks and the tail delay for the last BT blocks. For packets
of moderate size,
the effect of "tail delay" can not be ignored, while the "tail delay" becomes
negligible when packet
size is large enough. This will be shown later.
Based on the approximate results for A(k), the delay expressions can be
expressed in
block periods. When the polling period is not 1, the delay can be approximated
by
TN~RTD1P
IP
And delay of the packet of size (K) is
D(K) _ (A(K) + 0.5)T
The above analysis is counter intuitive in some ways because the analysis
shows that in order to reduce the overall time to send a communication a
method
and apparatus would change the MCS level from a higher throughput data
transmission type of data blocks to a lower throughput type of data blocks.
To validate these counter intuitive results of the above analysis and the
method and apparatus of the present invention, simulations were performed. The
CA 02341917 2001-03-19
-9-
K. Baiachandran 14-7-19-2-42
findings of these simulations were taken and used to guide the selection of
modulation and coding schemes MCS in system 10', an EGPRS system, in order to
reduce the packet delay between base station 12' and mobile stations 20', 30',
and
40' .
In FIGS. 3 and 4 the results of a simulation and analysis for A are shown.
FIG. 4 shows some parameters used in comparison of MCS 5, MCS 6 and MCS 7,
including the delay for MCS-7, the higher throughput coding scheme, in channel
condition type HT-100 (GSM hilly terrain model, 1 OOkmph mobile speed) with
SNR equal to l2dB, 18dB, and 22dB respectively. The round trip delay was 80ms,
i.e. T = 4. Some of the parameters of the MCS codes are shown in FIG. 3 (Table
1 ).
As can be seen, analysis results agree well with the simulation results. The
advantages of the counter intuitive method and apparatus of the present
invention
were definitely validated by the simulation.
As mentioned before in the Background, the unfulfilled need for this
invention was to provide an appropriate modulation and coding scheme (MCS)
that
minimizes user perceived delay. To examine such, FIGS. 5-7 show a numerical
comparison of modulation and coding schemes MCS 5 to MCS 7.
Through FIG. 5 to FIG. 7 modulation and coding schemes MCS-5, MCS-6
and MCS-7, which are used in EGPRS, are compared. In Fig. 5, the signal-to-
noise
2o ratio of the channel is l2dB. Under these conditions, it can be observed
that MCS-5
results in a lower delay than MCS-7 (i.e., stronger MCS-5 coding is
preferable).
When the channel signal to noise conditions improve (as shown in the FIGS.),
the
advantage of using MCS-5 (the stronger code) diminishes. The trade-off between
using more robust coding to combat channel loss and less robust coding to
increase
transmission rate becomes more visible for mobile wireless communications
through the FIGs. 5-7. For a signal-to-noise ratio at l8dB, MCS-6 performs the
best
among the three coding schemes when packet size is above l Okbits. Under very
good channel conditions (e.g. a signal-to-noise ratio of 22dB as shown in Fig.
6),
MCS-7 provides the best delay performance when the packet size is above 42
kbits.
CA 02341917 2001-03-19
-1~-
K. Balachandran 14-7-19-2-42
Generally speaking, when the packet size is very small (about the size of
BT), the most robust coding scheme (MCS 5, in FIGs. 5-7) provides the best
communication. As packet size increases, the crossover points to switch
between
different coding schemes occur. Where the crossover points are, depends on the
tail
delay, as well as the draining delay. When the packet size is large enough,
the
draining delay becomes the dominant factor, and the best modulation and coding
scheme to yield the minimal delay is the one achieving the highest long-term
throughput. Thus, modulation and coding scheme selection cannot be based
purely
on the basis of the throughput upper bound under the prevailing channel
conditions
to as it had been selected by previous methods and systems. Instead, selection
of a
modulation and coding scheme needs to be adapted to the underlying
applications
being used, such as voice, FTP, telnet, web browsing, etc. and the channel
condition
in order to reduce delay.
The crossover points between coding schemes of a system are applicable to
the case where a link is dedicated to a single user and the objective is to
minimize
the packet delay. For a shared channel, where the objective is to maximize the
channel throughput, the crossovers between coding schemes would be different.
Since the packet transmission consists of two phases, "draining" and "tail"
phases. In
the "draining" phase, packet size decreases at constant average rate. In the
"tail"
phase, the packet size decreases at a reduced rate, since in every round trip,
there are
not enough blocks to fill up the transmission interval. If there are multiple
users
statistically sharing a common channel, one user's idle slot may be filled by
another
user. When the system loading is high, the shared channel is never idle. Then
the
system of multiple users has each user draining his or her packet at the peak
rate
within his or her share of the channel. In such a case, the modulation and
coding
scheme should be chosen to maximize the "draining rate", i.e. the one with the
greater long term throughput. The method and apparatus of the present
invention
will also help guide the selection of the appropriate modulation and coding
schemes
for the cases where the system loading is light or sharing of channels by
users is not
3o possible.
CA 02341917 2001-03-19
y 1-
K. Balachandran 14-7-19-2-42
Thus, it will now be understood that there has been disclosed a heretofore
unknown and counter intuitive method and arrangement for reducing delay in a
system by increasing the robustness of coding over a segment of a packet.
While the
invention has been particularly illustrated and described with reference to
preferred
embodiments thereof, it will be understood by those skilled in the art that
narrows
changes in form, details and applications may be made therein. It is
accordingly
intended that the appended claims shall cover all such changes in form,
details and
applications which do not depart from the true spirit and scope of the
invention.
