.9173.
..
i 1
.3 ,..... :
my}? .
\ , at»... .
1h.h.u.§ .ndisn :
abnu
,. 3...! 70.... ..
$.1
imav i.
.r ﬁx
in!
z .1. x
”IT—'BSIS
3 .LlBRARY
2000; Michigan State
University
This is to certify that the
dissertation entitled
ANALYSIS AND DESIGN OF RELIABLE AND STABLE
LINKLAYER PROTOCOLS
FOR WIRELESS COMMUNICATION
presented by
SOHRAAB SOLTANI
has been accepted towards fulfillment
of the requirements for the
DOCTOR OF PHILOSOPHY degree in Computer Science
Major Professor’s Signature
AM 25; 200‘?
Date
MSU is an Affirmative Action/Equal Opportunity Employer
PLACE IN RETURN BOX to remove this checkout from your record.
To AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.
DATE DUE DATE DUE DATE DUE
5/08 K.IProj/Acc&Pres/ClRC/DateDue.indd
ANALYSIS AND DESIGN OF RELIABLE AND STABLE
LINKLAYER PROTOCOLS FOR WIRELESS
COMMUNICATION
By
Sohraab Soltani
A DISSERTATION
Submitted to
Michigan State University
in partial fulﬁllment of the requirements
for the degree of
DOCTOR OF PHILOSOPHY
Computer Science
2009
ABSTRACT
ANALYSIS AND DESIGN OF RELIABLE AND STABLE
LINKLAYER PROTOCOLS FOR WIRELESS
COMMUNICATION
By
Sohraab Soltani
Wireless links are errorprone and susceptible to noise imposed by fading, interference and
mobility. Therefore, current wireless networks suffer from high packet loss and poor connectivity
among users. Wireless linklayer protocol embedded in Medium Access Control (MAC) has
a signiﬁcant role in providing robust information delivery over wireless channels. A primary
focus of popular wireless linklayer protocols is to achieve some level of reliability using ARQ or
Hybrid ARQ mechanisms. However, these and other leading linklayer protocols largely ignore
the stability aspect of wireless communication, and rely on higher layers to provide stable trafﬁc
ﬂow control. This thesis investigates the problem of reliable and stable transmission over wireless
channels and highlights the inadequacies of the current IEEE802.11 standard linklayer which
attempts to recover from losses using retransmissions.
In this thesis, we aim to tackle the critical issues associated with the inefﬁciencies of current
wireless linklayer protocols and pursue a paradigm shift in the conventional 802.11 linklayer
design. We develop a new linklayer framework to provide both the reliability and stability for
pointtopoint contention free wireless communication. Using this framework, we introduced four
linklayer protocols: 1) Packet Embedded Error Control (PEEC) protocol, a linklayer protocol
designed to ensure reliable wireless communication by reducing the number of retransmissions
which essentially leads to improving system throughput. PEEC is layer oblivious and uses the
packet formats of current IEEE802.11 standard; 2) Delay Constraint PEEC (DCPEEC), an ex
tension of the PEEC protocol that targets the ﬂow control of realtime video trafﬁc (in addition to
reliability) in wireless communication. DCPEEC adjusts its parameters to provide lowlatency
communication to satisfy the delay constraint (required by the video application) while utilizing
the channel bandwidth effectively; 3) Automatic Code Embedding (ACE) linklayer protocol, the
ﬁrst effort to develop a theoretical framework for analyzing and designing a wireless linklayer
protocol that targets system stability in conjunction with reliable communication. The ACE proto
col uses a unique and optimal code embedding rate to construct coded linklayer packets in every
transmission to ensure stability, reliability and maximum throughput; 4) Prioritized ACE (PACE),
the ACE based stableandreliable linklayer that employs a novel rateadaptive Low Density Par
ity Check (LDPC) channel codes while interacting with the higher layers to provide a dynamic
decoder scheduling service over varying wireless channel condition. PACE provides prioritized
wireless linklayer communication that takes into consideration the level of importance/impact of
each packet to improve the overall performance.
Our analysis and results of various experimental scenarios show that these protocols signiﬁ
cantly outperform all competing link—layer protocols. Our ﬁndings in this thesis indeed provide
a clear evidence of the feasibility of designing stable and reliable link layer over pointtopoint
(singlehop) 802.11 channels; and more importantly the potential of achieving signiﬁcantly im
proved throughput by using this type of linklayer.
Copyright by
Sohraab Soltani
2009
To my parents, Reza and Afsaneh.
To my sisters, Soroor and Sima.
ACKNOWLEDGMENTS
I would like to thank my family for their great support. In particular, I like to recognize the
guidance my father provided through the course of my studies. I also thank my advisor Professor
Hayder Radha for showing me a successful path in my research. Shirish, Kiran, Ali, Usman, and
all of my colleagues at the WAVES laboratory; it was a privilege working with you. Finally, I am
sincerely thankful to Sally Newton for her encouragement in difﬁcult times.
vi
Keep away from people who try to belittle your ambitions. Small people always do
that, but the really great make you feel that you, too, can become great.
Mark Twain
vii
TABLE OF CONTENTS
LIST OF TABLES ..................................... xi
LIST OF FIGURES .................................... xii
1 Introduction ....................................... l
1.1 Overview of Contributions ............................. 3
1.2 Organization of this Thesis ............................. 7
2 Related Work ...................................... 8
2.1 ARQ—based Schemes ................................. 9
2.1.1 The IEEE802.11 Standard ......................... 9
2.1.2 Enhanced ARQ Strategies ......................... 10
2.2 Hybrid ARQ Schemes ............................... 12
2.3 CrossLayer Approach ............................... 13
3 Background ....................................... 15
3.1 802.11b Wireless Networks ............................. 15
3.2 Trace Collection ................................... 16
3.3 DiscreteTime Markov Chains ........................... 17
3.4 Binary Symmetric Channel ............................. 19
3.5 Markovian Wireless Channel ............................ 20
4 PEEC: A ChannelAdaptive FeedbackBased Error Control Protocol for Wireless
MAC Layer ....................................... 23
4.1 Communication Scheme .............................. 24
4.1.1 Sender Side ................................. 25
4.1.2 Receiver Side ................................ 25
4.2 Theoretical Settings ................................. 28
4.2.1 Message Model ............................... 28
4.2.2 Distortion Model .............................. 29
4.2.3 Buffer Model ................................ 31
4.3 PEEC Protocol ................................... 32
4.3.1 Channel State Estimation .......................... 33
4.3.2 Redundancy Allocation ........................... 35
4.3.3 MAC Frame Structure ........................... 37
4.4 Experimental Analysis ............................... 39
4.4.1 Multiple Decoders & Error Correcting Capability Factors ......... 39
4.4.2 Comparison with Contemporary Protocols ................. 42
viii
4.4.3 Implementation of PEEC using ALDPC ................. 50
4.5 Channel Coding Rate Analysis ........................... 52
4.5.1 IEEE802.11 ARQ ............................. 53
4.5.2 Enhanced ARQ ............................... 54
4.5.3 Hybrid ARQ (HARQ) ........................... 57
4.6 Discussion ...................................... 62
DCPEEC: Delay Constraint Error Control Protocol For Realtime Video Communi
cation .......................................... 63
5.1 Realtime Video Communication Model ...................... 65
5.2 Delay Constraint PEEC Protocol .......................... 71
5.2.1 Communication Model ........................... 71
5.2.2 Service Time Distribution under DCPEEC ................ 74
5.2.3 Channel State Estimation .......................... 75
5.2.4 Redundancy Allocation ........................... 77
5.3 Experiment ..................................... 79
5.3.1 Quality Selection .............................. 80
5.3.2 Scene Change ................................ 85
5.4 Discussion ...................................... 89
ACE: A Reliable and Stable Wireless Link Layer ................... 90
6.1 Preliminaries .................................... 93
6.1.1 Distortion Model .............................. 93
6.2 ACE Code Embedding Rate ............................ 95
6.2.1 Code Rate: Reliability ........................... 95
6.2.2 Code Rate: Stability ............................ 96
6.3 Automatic Code Embedding ............................ 101
6.3.1 ACE Protocol ................................ 104
6.4 Performance Evaluation ............................... 106
6.4.1 Realtime Trafﬁc .............................. 106
6.4.2 N onRealtime Trafﬁc ............................ l 11
6.5 Throughput analysis of TCP ............................ 113
6.5.1 Network Model ............................... 114
6.5.2 System Model under ACE ......................... 114
6.5.3 System Model under IEEE802.11 ARQ .................. 120
6.5.4 Analytical Performance Evaluations .................... 122
6.5.5 Experimental Performance Analysis .................... 126
6.6 Realtime Video Simulation ............................. 129
6.7 Discussion ...................................... 134
PACE: A Prioritized Wireless Link Layer ....................... 135
7.1 Illustrative Example ................................. 137
7.2 Model Formulation ................................. 141
7.2.1 LDPC Decoding Model .......................... 142
7.2.2 PACE Buffer Model ............................ 144
ix
7.3 PACE Protocol ................................... 149
7.3.1 PACE Sender ................................ 149
7.3.2 PACE Receiver ............................... 151
7.4 Experiment ..................................... 153
7.4.1 ThroughputDelay Tradeoff ........................ 154
7.4.2 Realtime and NonRealtime Application Performance .......... 158
7.5 Discussion ...................................... 161
8 Conclusions and Future Work ............................. 162
8.1 Link Layer Assignments .............................. 164
8.2 Code Assignment .................................. 166
8.3 GRACE Interactions with higherlayers ...................... 167
8.4 Broader Impact ................................... 171
APPENDICES ....................................... 172
A Proof of Lemmas for PEEC .............................. 173
B Proof of Lemmas for ACE ............................... 177
C Proof of Lemmas for PACE .............................. 180
D Steady State Balance Equations ............................ 182
BIBLIOGRAPHY ..................................... 185
3.1
4.1
LIST OF TABLES
The average BER for different channel traces. ...................
The throughput comparison of enhanced ARQ schemes. .............
xi
l7
3.1
3.2
3.3
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.9
4.10
4.11
4.12
4.13
5.1
5.2
LIST OF FIGURES
Trace collection setup. ............................... 16
A binary symmetric channel with crossover probability 6 .............. 19
Markovian Channel .................................. 21
An example of communication model consists of four transmission intervals. . . 26
The density of error aﬁer decoding is truncated on are, ............... 30
The architecture of the PEEC protocol ....................... 34
IEEE802.11 MAC frame formats and corresponding modiﬁcations necessary for
PEEC ......................................... 38
Average PEEC throughput for different a values with respect to the number of
decoders (s) ..................................... 40
Average service time (measured by the number of transmission intervals) for dif
ferent a values with respect to the number of decoders (s). ............ 41
The Impact of A value in throughput of HARQ schemes for a channel with PHY
rate lleps and transmission rate 1024kbps. ................... 44
The throughput of error control schemes with respect to variation in channel PER. 49
The change in the PEEC throughput with respect to a over the various channel
traces. ........................................ 50
The throughput of the PEEC protocol using the ALDPC decoder over various
channel traces ..................................... 51
continued ....................................... 60
The maximum channel coding rate and percentage of channel utilization over dif
ferent Markovian Channels. Note that the solid line in (a) represents the upper
bound of the channel capacity. ........................... 61
Realtime video communication model ........................ 66
The Gamma cumulative probability function ﬁtted on GOP data distribution of 15
video sequences encoded with QP 20. ....................... 70
xii
5.3
5.4
5.5
5.6
5.7
5.8
6.1
6.2
6.3
6.4
6.6
6.7
6.8
6.9
6.10
6.11
6.12
The acknowledgment format of the DCPEEC linklayer protocol. ........
An example of DC—PEEC operational communication model consists of four
transmission interval. ................................
continued .......................................
The Y — PSN R values of sequence frames encoded with QP 20 and transmitted
over channel with BER 0.001. ...........................
A quality comparison of ﬁve consecutive frame captures of “Stefan CIF” delivered
by different error control protocols ..........................
The impact of BER variations in frame quality (encoded with QP 20) under dif
ferent error control protocols ............................
The density of error after decoding is truncated on arz ...............
System model for stability analysis in wireless Communication. .........
Operational code embedding rate domain with respect to reliability and stability. .
An example of ACE operational communication model consists of four transmis
sion interval ......................................
The average goodput of ACE and IEEE802.11 ARQ over various channel condi
tions. Note that channel capacity in each ﬁgure represents the maximum amount
of achievable goodput without errors. .......................
Heterogenous network model. ...........................
A system of queuing network for the heterogenous network under ACE protocol.
The state diagram of system dynamics where Q1 = m, Q2 = Bg, Q3 = B3.
A system of queuing network for the heterogenous network under IEEE802.11
ARQ protocol .....................................
The state space of trafﬁc intensity in wired network .................
The steady throughput of network model using ACE and IEEE802.11 ARQ over
the various channel traces with respect to different congestion likelihoods .....
xiii
72
83
87
88
94
100
103
117
121
123
125
7.2
7.3
7.5
7.6
8.1
A LDPC Tanner graph with dv = 2 and dc = 4 ................... 142
The design architecture of the PACE protocol .................... 148
Simulation setup where heterogeneous trafﬁc is generated by nonrealtime TCP
and realtime video ﬂows. .............................. 158
The performances of nonrealtime and realtime applications in terms of through
put and video quality ................................. 160
An example of multihop wireless network. .................... 170
xiv
CHAPTER 1
Introduction
Despite the unprecedented success and proliferation of wireless LANs over the past decade, there
are a few arguably major shortcomings in the underlying linklayer protocols of wellestablished
wireless systems. These shortcomings are expected to be exacerbated as the level of heterogeneity
and highbandwidth requirements of emerging applications increase dramatically. In particular,
popular wireless linklayer protocols, such as the retransmission (ARQ) based approach employed
by the IEEE 802.11 standard suite, are designed to achieve some level of reliability by discarding
corrupted packets at the receiver and by performing one or more retransmission attempts until a
packet is received errorfree or a maximum number of retransmission attempts is reached. Many
leading research efforts [32] [39] have highlighted the inefﬁciencies of the current 802.11 link
layer protocol and proposed a variety of remedy solutions. Although recent proposed remedies for
the wireless linklayer focus on some aspects of the reliability issue, they largely ignore the stabil
ity dimension and they especially ignore the heterogeneous nature/demands of data/applications
at higher layers. Meanwhile, we believe that emerging and future wireless networks supporting
highend heterogeneous applications cannot afford piecemeal solutions. Hence, in this thesis we
aim to tackle the critical issues associated with the inefﬁciencies of current wireless linklayer
protocols and pursue a paradigm shift in the conventional 802.11 linklayer design. In particular,
we introduce a comprehensive framework that presents a thorough analysis and modeling of a
generic linklayer pointtopoint wireless communication which employs channel codes to pro
vide and maintain a reliable and stable communication. It is our belief that achieving the ultimate
objective in the development of a reliable and stable linklayer for heterogeneous wireless net
works that overcomes the shortcomings of current linklayer standards demands fundamental and
radical changes to the conventional linklayer protocol design. We highlight the key issues with
the 802.11 linklayer protocol:
1. Inefﬁcient reliability: The 802.11 ARQ approach discards corrupted packets that are mostly
errorfree, even when there is only a single bit error in a corrupted packet. Hence, the effec
tive throughput of 802.11 systems can be signiﬁcantly improved. This issue led many efforts
to propose new linklayer and crosslayer protocols that utilize corrupted packets (or partial
packets) instead of discarding them [40] [52]. In addition to Hybrid ARQ (HARQ) based
methods [43—45], examples of recent efforts for combating inefﬁciencies of ARQbased
wireless protocols include Partial Packet Recovery (PPR) [54], packet combining [32] [47],
CrossLayer Design with Sideinformation (CLDS) [72] [75], ZipTx [42]. Some of these
approaches, such as PPR and packet combining, exploit physical layer information regard
ing the quality of individual bits to improve the probability of recovering corrupted packets.
Others, such as CLDS and ZipTx utilize information available in current 802.11 linklayer
protocols in conjunction with error correcting codes to recover corrupted packets. In par
ticular, the work on CLDS demonstrates a signiﬁcant increase in throughput by utilizing
corrupted packets under current 802.11 systems and shows that the mere utility of binary
side information (packet is corrupted or not), which is available in the current 802.11 link
layer protocol, can increase the effective informationtheoretic capacity signiﬁcantly [5].
2. Largely absent stability: The ARQ approach is designed to provide “reliability in the long
run”, where information could eventually be delivered to the destination. Even then, the
linklayer does not guarantee delivery and the reliability burden (due to wireless errors) is
carried by higher layers, especially for applications that require guaranteed delivery. More
importantly, ARQbased 802.11 linklayer and other recent protocols largely ignore the
stability aspect of data communications in terms of maintaining a sustainable ﬂow, which
is critical for a dynamic and heterogeneous wireless environment. Although many leading
efforts have addressed the reliability and associated throughput inefﬁciency shortcoming of
current 802.11 linklayer (as highlighted above), current ARQ and many emerging link
layer protocols rely on (or arguably shift the problem to) higher layers to provide reliable
and stable ﬂow control for both realtime and nonrealtime trafﬁc. In conjunction with the
inefﬁcient reliability approach, this design strategy has led to a great deal of inefﬁciency
in throughput and to other major technical issues and challenges at higher layers. A well
known example is the TCP overwireless performance degradation phenomenon, which led
to major research efforts and numerous studies in attempt to mitigate the shortcoming of the
lower layers.
1.1 Overview of Contributions
This thesis introduces a comprehensive framework for analysis and design of wireless linklayer
protocols to overcome the above shortcomings. Our objective is to develop wireless linklayer
protocols which make use of incremental channel codes to (1) provide maximum reliability (high
likelihood of successful recovery data at the receiver) while ensures an efﬁcient utilization of
available bandwidth in transmission of new data, (2) offer system stability by ensuring that higher
layers are neither starved for information packets nor is there a glut of packets leading to buffer
overﬂows.
Using this framework, we ﬁrst focus on the reliability aspect of wireless linklayer communica
tion and identify its capabilities and limitations. These analyses lead to the development of a novel
linklayer Packet Embedding Error Control (PEEC) protocol [3]. Chapter 4 introduces the PEEC
protocol which uses a simple feedback mechanism to adaptively estimate channel conditions and
administer the transmission of (data and parity) symbols within a packet. Chapter 5 extends the
PEEC protocol and presents a novel error control protocol for wireless linklayer that targets both
reliability and trafﬁc ﬂow control for realtime video communication. Further, Chapter 6 proposes
a paradigm shift where both reliability and stability are targeted using an Automatic Code Em
bedding (ACE) wireless linklayer protocol. To the best of our knowledge this is the ﬁrst effort
to develop a theoretical framework for analyzing and designing a wireless linklayer protocol that
targets system stability in conjunction with reliable communication. In Chapter 7, we build on the
ACE framework [2] to achieve preferred data recovery order across connections, while maintain
ing stable and reliable data ﬂows in wireless networks.
Chapter 4 presents statistical analysis of a linklayer, point—topoint and contentionfree wire
less communication where a receiver stores corrupted packets in its buffer for future recovery.
We develop suitable models for each component of this communication scheme, which includes
message, channel, distortion and buffer models. We use these models to introduce the PEEC
linklayer protocol. PEEC employs packetembedded parity symbols (instead of retransmission)
for error recovery. Also, PEEC uses certain ﬂags embedded in the receiver feedback to determine
the amount of redundancy necessary for the next transmission. PEEC utilizes acknowledgment
ﬂags (a decoding and a buffer) to assess the channel and the receiver buffer conditions in every
transmission. Depending on this assessment, PEEC adaptively administers the transmission of the
data and redundancy (parity) symbols such that: (1) the level of parity symbols guarantees high
likelihood of successful recovery of new data as well as corrupted data at the receiver buffer; (2)
the available bandwidth is efﬁciently utilized for the transmission of new data. Our experimental
simulations show that PEEC outperforms the leading error control protocols designed for wire
less linklayer. PEEC is layer oblivious and compatible to IEEE802.11 standard linklayer packet
formats.
Chapter 5 develops an analytical framework for video communication which captures the be
havior of realtime video trafﬁc at the wireless linklayer while taking into consideration both
reliability and latency conditions. Using this framework, we introduce a Delay Constraint Packet
Embedded Error Control (DCPEEC) protocol for wireless linklayer. DCPEEC ensures reliable
and rapid delivery of video packets by employing various channel codes to minimize ﬂuctua
tions in throughput and provide timely arrival of video. The proposed effort begins by outlining
a novel analytic framework to capture video trafﬁc ﬂow at the wireless linklayer. In particular,
we develop a queuing model that captures realtime video trafﬁc behavior under reliability and
endtoend delay constraint at the wireless linklayer. Speciﬁcally, we model the linklayer buffer
as an MIG/1 queuing system with randomsized batch arrivals of video information having a sin
gle server representing the linklayer protocol with a general servicetime distribution. Using this
model, we ﬁnd an operational code rate for DCPEEC which guarantees video trafﬁc ﬂow with
tolerable latency while utilizing the channel bandwidth effectively. We compare the performance
of DCPEEC with that of IEEE802.11 ARQ and HARQ in terms of PSNR gain under various
realtime video communication setups. The simulation results suggest that DCPEEC is a suitable
wireless linklayer communication mechanism for realtime multimedia applications.
In Chapter 6, we propose a paradigm shift where both reliability and stability are ensured using
an Automatic Code Embedding (ACE) wireless linklayer protocol. The proposed wireless ACE
linklayer (a) employs a theoreticallysound framework and a corresponding strategy for embed
ding channel codes, using robust and welldeﬁned code rates, in each packet; and (b) selects the
code rates in an optimal and constrained manner to ensure reliability, stability, and maximum
throughput. We believe that this work is the ﬁrst to present a theoretical framework for analyzing
and designing a wireless linklayer protocol that targets system stability in conjunction with re
liable communication. We begin by outlining a novel joint analytic framework to predict system
behavior under ACE. Speciﬁcally, we ﬁrst obtain an upper bound on operational code embedding
rate that ensures reliability. Next, we develop a queuing model that captures system behavior
under stability condition. In particular, we describe the linklayer behavior as an onoff source
model using a twostate Continuous Time Markov chain (CT MC) model. We deploy ﬂuid ap
proximations to analytically characterize the buffer growth. By utilizing these models, we ﬁnd
a lower bound on operational code embedding rate which guarantees stable operation while uti
lizing the channel bandwidth effectively. An important conclusion of the above analysis is that
various trafﬁc demands (in terms of reliability and stability requirements) can be met using a
packetbypacket code embedding rate constraint that is independent of trafﬁc type. This leads
to simplistic, trafﬁcindependent and elegant design rules for the ACE protocol, while providing
reliability and stability in an optimal and joint manner. Our extensive analysis of ACE protocol
over real channel traces collected on 802.11b WLANs for realtime and nonrealtime trafﬁc, TCP
throughput and realtime video communication scenarios show that ACE signiﬁcantly outperforms
the conventional IEEE802.11 ARQ over varying wireless channels conditions.
Chapter 7 builds on the ACE framework [2] to achieve preferred data recovery order across
connections, while maintaining stable and reliable data ﬂows in wireless networks. Under the
proposed Prioritized ACE (PACE) framework, our ACE based stableandreliable linklayer will
employ a novel rateadaptive Low Density Parity Check (LDPC) channel codes while interact
ing with the higher layers to provide a dynamic decoder scheduling service over varying wireless
channel condition. Speciﬁcally, we develop a LDPC decoding model to capture the decoding
process for linklayer trafﬁc and use it to determine an optimal code selection strategy for max
imal bandwidth utilization. Further, we ﬁnd an optimal code embedding rate under the PACE
framework to jointly meet the reliability, stability, and delay constraints of the wireless linklayer
communication. We classify heterogeneous linklayer trafﬁc arrivals into different priority classes
based on packet delay constraints and the distortion suffered. The trafﬁc arriving in each priority
class is modeled as a Poisson process. Consequently, we formulate the linklayer buffer as a multi
class M / G / 1 priority queuing system where the decoding process (service process) of the PACE
buffer is captured by nonhomogeneous geometric distribution [99]. Given the linklayer buffer
model and the LDPC decoding model, we determine the optimal dynamic decoder scheduling un
der the PACE framework. This scheduling policy is a special case of a classic scheduling problem
solved by Plambeck et al. in [100] and is asymptotically optimal. The PACE protocol incorporates
the LDPC model and the dynamic scheduling policy into the original ACE protocol [2].
1.2 Organization of this Thesis
The rest of this thesis is organized as follows. Chapter 2 presents an overview of the related work.
Chapter 3 provides background that is required to understand the material presented in this the
sis. We introduce PEEC in Chapter 4. The DCPEEC protocol developed for realtime wireless
video communication is presented in Chapter 5. In Chapter 6, we present the ACE framework,
the ﬁrst analytical model that jointly targets reliability and stability of wireless linklayer com
munication. Chapter 7 analyzes the impact of prioritized wireless communication on the overall
system performance and develops the PACE protocol. We conclude the thesis in Chapter 8.
CHAPTER 2
Related Work
Various linklayer protocols have been developed over the years to ensure reliability of wireless
communication by using some sort of error detection and correction technique. In literature [1],
error detection and error correction are deﬁned as follows:
Deﬁnition 1. Error Det ect i on is the ability to detect the presence of errors caused by noise
or other impairments during transmission from the transmitter to the receiver.
Deﬁnition 2. Error Correction is the information processing ability which result in the
reconstruction of the original, errorfree data at the receiver
There are two different ways to design an error correction protocol:
1. Automatic repeatrequest (ARQ): The transmitter sends the data and also an error detec
tion code, which the receiver uses to check for errors, and requests retransmission of erro
neous data. In many cases, the request is implicit; the receiver sends an acknowledgement
(ACK) of correctly received data, and the transmitter resends anything not acknowledged
within a reasonable period of time.
2. Forward error correction (FEC): The transmitter encodes the data with an errorcorrectin g
code (ECC) and sends the coded message. The receiver never sends any messages back to
the transmitter. The receiver decodes what it receives into the “most likely” data. The codes
are designed so that it would take an “unreasonable” amount of noise to trick the receiver
into misinterpreting the data.
Popular linklayer protocols use either one of the above approaches or the combination of the
two to provide reliability.
2.1 ARQbased Schemes.
In this section, we present an overview of linklayer protocols that utilize automatic repeat request
(ARQ) to recover erroneous packets.
2.1.1 The IEEE802.11 Standard
The IEEE 802.11 standard covers two layers of the OSI reference model: the medium access con
trol (MAC) and the physical (PHY) layer. The fundamental function that provides fair access to
the channel and best effort service is the distributed coordination function (DCF) that is based on
a carrier sense multiple access with collision avoidance (CSMA/CA) algorithm. To deal with the
collision problem, and other severe sources of errors such as interference, fading, and attenuation,
the IEEE802.11 protocol incorporates positive acknowledgments: it incorporates frame check se
quence (FCS) to detect errors and automatic repeat request (ARQ) to retransmit corrupted packets.
If no ACK is returned (or FCS fails), the frame is scheduled for retransmission, until a maximum
retransmission limit is reached.
The IEEE802.11 ARQ protocol discards corrupted packets without regard to the number and
location of the errors. This approach is suitable for wireless channels with relatively low bit
error rates (BER) because the likelihood of receiving consecutive corrupted packets is small and
the original packet could be delivered after few retransmissions. However, for channels with
more severe error conditions (and arguably more realistic), IEEE802.11 ARQ causes multiple
retransmissions (even if there is a single error in a packet) which in turn leads to the transmission
of a large number of redundant (correct) data. As a result, the overall throughput deteriorates
steadily and rapidly with increasing average channel BER.
2.1.2 Enhanced ARQ Strategies
In the current IEEE 802.11 MAC standard no attempt is made to correct erroneous packets: error
detection provided by the PCS requires a retransmission even for a single erroneous bit. A rela
tively simple and standardcompatible way to improve the reliability of WLAN communications is
to retain received erroneous frames which are normally discarded by the standard ARQ. Memory
ARQ schemes combine several of such corrupted packets at the receiver to attempt to reconstruct
the original error free packet. The average number of combined copies varies according to the
channel condition, thus the effective degree of protection is dynamic. Each information packet, in
fact, contains a parity check sequence for error detection so that the receiver can determine when
to stop the packet combining algorithm because the original packet has been fully recovered.
Unlike conventional IEEE802.11 receivers, in the described methods the receiver stores an
erroneous received packet before requesting a retransmission. For the purpose of error control,
every different data MAC Protocol Data Unit (MPDU) can be identiﬁed by the 16bit sequence
control ﬁeld that indicates its sequence number. Using the 32bit FCS ﬁeld at the receiver, the
received packet can be checked for errors. If it is errorfree, a positive acknowledgment is sent
to the transmitter, inhibiting further retransmissions and the packet can be forwarded to the next
hop or to the application level. If it is not, the packet is dropped, but stored in the receiver
buffer waiting for a retransmission. All the received packets are then processed by the error
correction algorithm to be described. If the procedure is not able to recover a correct packet further
retransmissions are necessary. Transmissions are repeated till a correct frame is received, the data
10
in the cumulative buffer of received packets is correctable, or the maximum retransmission limit
is reached.
XOR Combining
A ﬁrst combination scheme, here referred to as xor combining [33,34], consists in xoring two
erroneous copies to locate errors in both packets. The decision process then involves a bruteforce
bitbybit inversion of the located bit error positions and checking for correctness using the PCS.
When two copies are erroneous this operation fails if there is at least one bit position in which
both copies have an error, or alternatively, if the total number of erroneous locations exceeds a
given Nmax. To make the algorithm implementable, in fact, an upper limit of computational
complexity is deﬁned which in practice is limited to values of Nmag; to 10, 11, or 12. Given a
buffer size greater than two packets, more than one combination of packets is available for xor
ing. If no error recovery is possible, however, a retransmission is sought. This algorithm suffers
from the performance limitations due to its high complexity.
Majority Combining
A second combination scheme, hereafter majority combining (MAk) [35, 36], is proposed to
overcome the performance limitation of working on packet pairs only and uses the last three
received erroneous copies of a packet. If xor combining fails, then a bitbybit majority decision
can be performed to construct a new packet where a bit is one if it is one at least in two of the
combined copies. The error correction algorithm succeeds if no biterror overlaps occur. This idea
can then be extended to cover combinations of more than three copies where a majority decision
over the last k packets is used as an estimate of the transmitted bits.
11
Generalized Majority Combining
The concept of combining packets to obtain a more reliable estimate of the transmitted bits can
offer a signiﬁcant advantage especially in applications where repeated packets can present a sig
niﬁcantly different error rate such as in case of a wireless connection. For these applications, the
possibility of selecting packets allows to avoid severely damaged ones. For instance in [37], all
the possible combinations of k stored packets are considered by exploiting the availability of an
error detection code to verify the correctness of their combination. For example, assume that, for a
given information packet, the maximum number of transmissions allowed is four and the received
packets corresponding to the four transmissions are A, B, C, and D. In this generalized majority
combining scheme, after the last transmission, the receiver can combine all the possible triplets
together with several choices, i.e., ABC, ABD, BCD, ACD. Each combination does not use all
available packets, but it is able to obtain good recovery by avoiding potentially highly damaged
packets. For instance, a combined ABC or BCD packet may have fewer errors than a combined
ABCD packet.
The analysis in [38—40] shows the xor and majority combining schemes are IEEE MAC com
patible, however the improvement of the throughput is not remarkable.
2.2 Hybrid ARQ Schemes
Prior work in information theory has discussed the concept of hybrid ARQ which employs various
codes including Reed Solomon and LDPC for error correction [48] [53]. In the simplest version
of HARQ, typeI HARQ [49], the sender encodes the packet payload with an errorcorrection code
prior to the transmission. Accordingly, the receiver requests for a retransmission when the decod
ing of the received packet fails. In typeII hybrid ARQ (HARQII) [50], each packet payload is
encoded to a codeword and is punctured before transmission. Upon decoding failure, the receiver
12
buffers the packet and sends a negative acknowledgment (NACK). In response to the NACK, the
sender sends additional redundancy symbols which the receiver recombines with the associated
packet in the buffer and reattempts to decode the combined packet. The HARQII is similar to
the PEEC and ACE protocols since these schemes achieve recovery through the transmission of
additional redundancy. However the HARQH is not designed for IEEE802.11 MAC environment
and is not adaptive with respect to channel condition. In addition, HARQII does not address
throughput stability issues raised by varying trafﬁc demand.
In addition to Hybrid ARQ (HARQ) based methods [43—45], examples of recent efforts
for combating inefﬁciencies of ARQbased wireless protocols include Partial Packet Recov
ery (PPR) [54], packet combining [32] [47], CrossLayer Design with Sideinformation
(CLDS) [72] [75], ZipTx [42]. Some of these approaches, such as PPR and packet combin
ing, exploit physical layer information regarding the quality of individual bits to improve the
probability or recovering corrupted packets. Others, such as CLDS and ZipTx utilize informa
tion available in current 802.11 link—layer protocols in conjunction with error correcting codes
to recover corrupted packets. In particular, the group work on CLDS demonstrated a signiﬁcant
increase in throughput by utilizing corrupted packets under current 802.11 systems. Furthermore,
the work on CLDS showed that the mere utility of binary side information (packet is corrupted
or not), which is available in the current 802.11 link layer protocol, can increase the effective
informationtheoretic capacity signiﬁcantly [5].
2.3 CrossLayer Approach
In recent years, many papers in multimedia applications have proposed cross—layer mechanisms
to overcome performance limitations imposed by conventional protocols. For instance UDP
Lite [73], tried to improve the bandwidth utilization by making adjustments to the protocol stack
13
at the transport and the link layers which relies on the errorresilient nature of multimedia content.
The analysis of the hybrid ErasureError protocols (HEEPs) in [5] shows that crosslayer proto
cols in general provide capacity improvement in many realistic scenarios and can signiﬁcantly
improve the overall performance as measured by video quality. However, a signiﬁcant drawback
of the crosslayer protocols is that their implementations require major modiﬁcations in transport
and application layers.
The primary objective of the related studies presented in this section is to provide reliability
of wireless communication. In this thesis, we analyze and develop novel linklayer protocols for
wireless linklayer that in addition to providing reliability, they target other aspects of wireless
communication such as ﬂow control for delay constrained trafﬁc, stability and trafﬁc prioritiza
tion.
14
CHAPTER 3
Background
This chapter provides the background that is required to understand the contributions of this thesis.
3.1 802.11b Wireless Networks
Due to their high data rates and use of the timetested TCP/IP protocol suite, 802.11b networks
have experienced widespread deployment. These LANs are ﬁnding their way into homes and busi
nesses ubiquitously. However, like other wireless technologies, 802.1 lb networks also suffer from
severe quality degradation in the presence of physical obstructions and intersymbolinterferences.
Two modes of operation are supported in 802.11 networks [30, 31]: ( 1) ad hoc mode in which
wireless nodes can communicate with each other directly, and (2) infrastructure mode in which
wireless nodes are arbitrated using a central entity called an access point (AP).
All 802.1 lbcomplaint networks support four basic physical layer data rates of 1 Mbps, 2 Mbps,
5.5 Mbps and 11 Mbps. Increase in the data rate reduces the robustness of the 802.11b physical
layer. In the infrastructure mode, if the number of retransmission requests exceeds a certain
threshold, the AP drops down to a lower data rate than its current data rate. For retransmissions,
802.11b relies on a 32bit frame check sequence (FCS) that computes checksum over the entire
15
A &
Sniffer 4 Sniffer 3 Sniffer 2
21 ft
y & Room &
Sniffer 1 2322 Sniffer 5
Passageway
& : p
(( ’) U Room
A 4— § 2320
AP Server [
Figure 3.1: Trace collection setup.
MAC layer frame. Positive acknowledgement (ACK) frames are employed to signal successful
transmission of data frames. If a frame fails checksum then it is dropped at the receivers MAC
layer. The sender after timing out schedules a retransmission.
3.2 Trace Collection
Throughout this thesis, the experimental evaluations are conducted using real channel traces that
are collected over the wireless setting depicted in Fig. 3.1. It can be described as follows: ﬁve
wireless receivers were used to simultaneously collect error traces on an 802.1 lb WLAN. These
receivers are placed in different locations in a room. The access point (AP) is located across the
hallway from the room. A wired sender is used to send multicast packets with a predetermined
payload on the WLAN; multicasting disabled MAC layer retransmissions. Each trace comprised
of one million packets with a payload of 1,000 bytes each. At the physical layer, the auto rate
selection feature of the AP was disabled and for each experiment the AP was forced to transmit at
a ﬁxed data rate. Each trace collection experiment was repeated for different physical layer (PHY)
l6
Table 3.1: The average BER for different channel traces.
2Mbps 5.5Mbps 1 leps
500kbps ' 0.008 0.007 0.0094
750kbps 0.0001 0.0102 0.0090
900kbps 0.005 0.006 0.01 86
1024kbps 0.0100 0.0038 0.0231
data rates (i.e., 2Mbps, 5.5 Mbps and lleps). For a speciﬁc PHY data rate, we have collected
traces using four transmission rates: 500kbps, 750kbps, 900kbps and 1024kbps respectively. We
collected 41 traces over different receivers. However for brevity, Table 3.1 shows the channel
average BERs associated to 12 of these traces.
We used Prism 2.5 Chipset WiFi adapter which allows us to modify the receiver’s MAC layer
device to pass corrupted packets to higher layers. To capture packets at high transmission rates,
packet dissectors were implemented inside the device drivers. These packet dissectors ensured
that only packets pertinent to our wireless experiment are processed, while all other packets are
dropped. In addition to a packet header and payload information, for each packet two additional
parameters (1) Signal strength (S), (2) Silence Value (N) were logged at the receivers. These
parameters are used to calculate the Signal to Silence Ratio (SSR) value (i.e., S SR = .S'  N)
observed with each packet.
3.3 DiscreteTime Markov Chains
Markov chains are employed to model statistical data with shortterm temporal dependence. Let
a stochastic process X n take on values denoted by nonnegative integers 0, 1,   ' , N . If X n = i
then the process is said to be in state i at time n . Whenever the process is in state i there is a ﬁxed
17
probability that the next state of the process will be state j . If that probability can beexpressed as
P(Xn+1= 3‘an =ian—1=in—1w“ ,X1=i1vX0 = 2'0) = P(Xn+1 =1an = i),
(3.1)
for all states to,   ,z'.n_1,i,j, n 2 0, then Xn is a Markov Chain.
The property given in 3.1 is commonly referred to as the Markov Property. Thus, for
a Markov chain the conditional distribution of any future state Xn+1, given the past states
X n— 1, .   , X 1, X 0 and the present state X n , is independent of the past states and depends only
on the present state. Equation (3.1) is also referred to as homogeneity property since it ensures
that the transition probabilities do not vary with time.
Let pm = P(Xn+1 = len = i) denote the probability of transiting to state j from i. Since
pm represents a probability measure, it exhibits the following properties: (i) pi, j 2 0, i, j 2 0,
and (ii) 29,1)“ 2 1,2' = 0,1,  ,N. The probability of transiting to the next state can be
represented in a matrix form. This matrix is referred to as the onestep state transition probability
matrix.
The steadystate or stationary probabilities of a Markov chain represent the longrun proportion
of the time spent in each state. Once the transitional probabilities of a Markov chain are known,
the steadystate probabilities of being in a particular state are the unique nonnegative solutions of
the following linear system of equations:
N
ZWtPi,j = 79. i=1.',N (3.2)
i
N
Zn, = 1. (3.3)
i=1
For stationary Markov chains, the steadystate and transition probabilities do not vary with time.
Throughout this thesis, we use stationary Markov chain for modeling wireless channel in every
transmission.
18
Figure 3.2: A binary symmetric channel with crossover probability 6.
3.4 Binary Symmetric Channel
A binary symmetric channel (or BSC) is a common communication channel model used in coding
theory and information theory. In this model, a transmitter wishes to send a bit (a zero or a one),
and the receiver receives a bit. It is assumed that the bit is usually transmitted correctly, but that
it will be “ﬂipped” with a small probability (the “crossover probability”). This channel is used
frequently in information theory because it is one of the simplest channels to analyze.
The BSC is a binary channel; that is, it can transmit only one of two symbols (usually called 0
and 1). (A non—binary channel would be capable of transmitting more than 2 symbols, possibly
even an inﬁnite number of choices) The transmission is not perfect, and occasionally the receiver
gets the wrong bit. Many problems in communication theory can be reduced to a BSC. On the
other hand, being able to transmit effectively over the BSC can give rise to solutions for more
complicated channels.
The BSC channel in Fig. 3.2 with crossover probability 6 is a channel with binary input and
binary output and probability of error e; that is, if X is the transmitted random variable and Y the
19
received variable, then the channel is characterized by the conditional probabilities
P(Y = 0X = 0) = 1— e (3.4)
P(Y = 0X = 1) = e (3.5)
P(Y = 1X = 0) = e (3.6)
P(Y =1X = 1) = 1— e “(3.7)
It is assumed that 0 5 e g 0.5. If e > 0.5, then the receiver can swap the output (interpret 1 when
it secs 0, and visa versa) and obtain an equivalent channel with crossover probability 1 — p g 0.5.
The capacity of the channel is 1 — H (e), where H (e) is the binary entropy function [55].
3.5 Markovian Wireless Channel
A channel model describes the process under which errors are introduced in a transmitted packet
over a wireless link. Packets are transmitted during discrete time slots Ti, 2' = 1,2,   ,+oo,
which we refer to as transmission intervals. During the ith transmission interval, a message is
transmitted over a Binary Symmetric Channel (BSC) with crossover BER 62'. To derive a channel
model for all transmission intervals, we assume that each e, of a particular Ti is valued from a ﬁnite
set FN with length N: e, E F N, IFNI = N. As a result, we can consider the channel model as a
combination of N various BSCs with unique BERs (i.e., El yé ej forl 763' l,j = 1,2,    ,N). In
every Ti, the channel is in one of the N possible states (S 1 ,   ' , SN) where each state corresponds
to a particular BSC. Based on these settings, we can model a wireless channel as a discrete Markov
chain with N states where each state is a representation of a BSC with a particular BER. Fig 3.3
shows a Markovian channel model. We assume a homogenous and stationary Markov chain with
transitional probability matrix P and the limiting probabilities 17 = (n1,    ,7rN). Under this
20
pN1,N
1711/
p11 ' p12 ,2 pN,—1Nl pN’i’N‘VN
‘70.,ng 000 Mo one «a
p21 pN,Nl
Figure 3.3: Markovian Channel.
model, the steady state average BER E and packet error rate (PER) c is
N
E = Zﬂiei (3.3)
i=0
N
c = Zni(1—(1—ei)n), (3.9)
where n is the length of the transmitted packet.
The probability that the channel rs in states S— — r and Sz+1— — t in r andr T'+1 is:
PT‘{S7: = T,Sz'+1=t}= errt. 7‘,t=1,2,~ ,N (3.10)
The Markovian channel model can be trained on real channel traces by using the statistics of
previous transmission intervals. This captures the effects of multipath fading and interference on
the channel BER in every transmission interval using a single aggregated model [19, 21].
The capacity of a BSC channel with crossover probability 6,; is 1 — H (5i) [55]. Using the
21
steady state probabilities 1r, the average channel capacity in any interval is determined as follows:
N
C: Emu—Hap). (3.11)
i=1
The channel capacity gives an upper bound on the average (reliable) information transmission
rate for the wireless channel under consideration.
22
CHAPTER 4
PEEC: A ChannelAdaptive
FeedbackBased Error Control Protocol for
Wireless MAC Layer
In this chapter, we investigate the problem of reliable wireless linklayer communication over a
lossy channel. Speciﬁcally, we introduce an analytical framework that presents a thorough anal
ysis and modeling of a generic linklayer pointtopoint wireless communication which employs
channel codes to provide and maintain a reliable communication. Our objective is to develop
a new wireless linklayer framework which make use of incremental channel codes to provide
maximum reliability (high likelihood of successful recovery data at the receiver) while ensures an
efﬁcient utilization of available bandwidth in transmission of new data.
This framework comprises various models including communication, message, distortion and
buﬁer models. The analysis provided under this framework leads to the development of a novel
linklayer Packet Embedding Error Control (PEEC) protocol [3].
PEEC employs packetembedded parity symbols (instead of retransmission) for error recovery.
Further, PEEC uses certain ﬂags embedded in the receiver feedback to determine the amount of
23
redundancy necessary for the next transmission. PEEC is similar to the HARQII protocol in
the sense that in both schemes, the recovery is achieved through the transmission of additional
redundancy information; however PEEC utilizes acknowledgment ﬂags, a decoding and a buﬁer,
to assess the channel and the receiver buffer conditions in every transmission. Depending on this
assessment, PEEC adaptively administers the transmission of the data and redundancy (parity)
symbols such that: (1) the level of parity symbols guarantees high likelihood of successful re
covery of new data as well as corrupted data at the receiver buffer; (2) the available bandwidth
is efﬁciently utilized for the transmission of new data. Another design objective of PEEC is its
compatibility with conventional higherlayer transport and application layer protocols. That is,
unlike crosslayer protocols, PEEC does not pass corrupted packets up to the higher layers of the
protocol stack.
4.1 Communication Scheme
In this section, we describe a general contention free communication model in which one trans—
mitter and one receiver are communicating over a wireless link. We deﬁne a transmission interval
Ti as the duration in which a transmitter sends the ith
message M2 and receives its corresponding
acknowledgment ACKi. A transmitter sends a new message after the reception of an acknowl
edgment (ACK). In our analysis we assume that the ACK message is errorfree. This assumption
is reasonable since the size of the ACK messages are small and often protected by FEC [102].
Alternatively, the ACK frames can be transmitted over low PHY rates to reduce the probability of
corruption.
24
4.1.1 Sender Side
During Ti, a sender transmits a message which is represented by the tuple M, = (CZ(hi, 222), Yi)
where k, represents the number of data symbols which are not being retransmitted. In each r, a
transmitter encodes ki with parity symbols xi creating a codeword Ci(kiv 5132). We refer to these
parity symbols as typeI parity. The receiver utilizes x, to decode Cr" Upon successful decoding,
C, is extracted and 19,; data symbols are passed up to the higher layer. The error correction fails
when the decoding operation fails as indicated in FCS. In that case, the receiver stores C, in
its buffer and issues a request for more parity symbols. The transmitter also sends additional
(typeII) parity symbols denoted by yi. The receiver utilizes yz symbols to recover old corrupted
codewords accumulated in its buffer (e.g., Cj, j = 1,    ,i — 1).
4.1.2 Receiver Side
We assume that the receiver has a ﬁnite buffer containing m rooms. That is, the receiver can
accommodate up to m corrupted messages waiting for recovery. If a newly corrupted packet ﬁnds
all rooms in the buffer occupied, it does not enter the buffer and is dropped.
We assume that there are 3, 1 S s g m, decoders available in the receiver. The status of the
receiver is reported to the transmitter via certain ﬂags in an acknowledgment message. Speciﬁ
cally, 1 + 3 ﬂags are encapsulated in every acknowledgement. Let Fi[k], k = 0,   . ,3 represent
values of these ﬂags in ACKi. We refer to the ﬁrst ﬂag (i.e., Fz [0]) as a decoding ﬂag, indicating
the decoding status of the transmitted message in Ti; F210] = 1 when decoding of M, was not
successful. The remaining 3 ﬂags (i.e., Fi[k], k = 1,    ,s) are called buffer ﬂags. Each buffer
ﬂag is associated with a particular decoder in the buffer and represents the status of that decoder.
For instance, if the jth decoder is busy then Fz [j] = 1.
To perceive the functionality of this communication mode], consider the example given in
25
( Decoding Achieved
X Decoding Failed a
' x1
Receiver 2
. kl
TypeI Typell
Parity Parity
Figure 4.1: An example of communication model consists of four transmission intervals.
__?¢‘
3.“
N
Fig. 4.1. A short communication consisting of four transmission intervals, buffer capacity of
two and one decoder at the receiver is shown. During the ﬁrst transmission interval T1, a mes
sage M1 = (Cl(kl,a:1),y1) is sent. There are no typeII parity symbols in M1, because there
is no prior corrupted message in the receiver buffer, so y1 = 0. A receiver that fails to decode
Cl, stores 01 in its buffer and sends an acknowledgment ACKl = (1, 1). In r2, the transmitter
sends M2 = (020:2, x2), y2 = {y%}). The receiver uses 122 to decode C2 and employs typeII
parity symbols yé (yzj denote additional parity for Cj, j < i transmitted in Ti) in addition to 2:1
to decode 01 The receiver acknowledges ACK2 = (1, 1), indicating decoding failure of Cg and
C1(k1,:r:1 + 31%). As a result, in T3, the sender sends M3 = (C3(k3,:r3),y3 = {y%}). Note
that since there is only one decoder in use, the sender transmits typeII parity which corresponds
to a particular message that the decoder is serving. In 73, the receiver successfully decodes C3
26
using 2:3 and Cl(kl,:r:1 + 31% + yé). Now, since decoding of the recent transmitted message
was successful, the receiver sets the decoding ﬂag to zero (i.e., F3[0] = 0) but at the same time
since the decoder is waiting for typeII parity symbols to perform decoding on Cg, the buffer
ﬂag is set to one (i.e., F3[1] = 1); so ACK 3 = (0, 1). Accordingly, in T4, the sender transmits
M4 = (C4(k4,:r4),y4 = {y2}). The receiver decodes C4 using 204 and Cg = (kg,:cg + 3/21)
successfully; so ACK4 = (0,0).
The communication model described above represents a general communication mechanism
that utilizes packetembedded parity symbols instead of retransmission to retrieve corrupted data.
For this communication scheme, developing a protocol that estimates and adjusts the amount of
necessary redundancy in every transmission, requires several controlling subtleties that we need
to handle carefully to achieve high performance. For instance, depending on the feedback from
the receiver, a transmitter should send enough typeI parity symbols to increase the likelihood
of reliable reception. On the other hand, a reasonable amount of typeII redundancy is required
to correct corrupted packets and prevent buffer overﬂow. Sending excessive redundancy will
deteriorate average bandwidth utilization; meanwhile, transmitting too few parity symbols may
result in unsuccessful decoding and will increase the number of corrupted messages accumulated
in the buffer. Therefore, the amount of redundancy transmitted over a channel has a critical impact
on overall performance of this communication scheme. To that end, we propose an error control
mechanism called Packet Embedded Error Control protocol (PEEC). In the next section, we study
underlying statistical characteristics of this communication model and develop necessary models
which provide essential tools for the design and analysis of PEEC. Note that, throughout this
chapter, the terms “packet” and “message” are used interchangeably.
27
4.2 Theoretical Settings
In this section, we investigate the statistical nature of the communication scheme described in the
previous section to ﬁnd a suitable model for each of its components. We introduce three models:
a message model that represents the distribution of the parity and data symbols in a particular
message; a distortion model that measures the distortion level of a message after a transmission;
and a buffer model which models the receiver buffer as a queuing system.
4.2.1 Message Model
Let random variables K, X and Y represent the number of data, typeI and typeII parity symbols
in a message. Consider a message M = (K, X, Y) containing 72 symbols. That is, any message
M is represented by a vector of three random variables and has a ﬁxed length K + X + Y = 72.. Let
p K be the probability measure that a particular symbol in a message is a data symbol. Similarly,
let p X (py) denote this likelihood for typeI (typeII) parity Symbol. Therefore, K, X and Y
each, has a binomial distribution with parameters (n, PK), (n, PX) and (n, Py) respectively.
Finding a model for a message M is equivalent to ﬁnding a distribution of the vector (K, X, Y).
Since K, X and Y are binomial random variables, a multinomial distribution can be used as an
accurate approximation of the distribution of M = (X, Y, Z) with the probability mass function
n!
Pr{K=k,X=x,Y=y}=WpIRp§(p3{/, k+x+y=n
where pK +pX +py =1.
In practice, since n is a large number, we can approximate the distributions of K, X, and Y by
Poisson distributions with parameters A K = npK, A X 2 hp X and ’\Y = npy. So for instance,
K has the following probability mass function:
Ak
P{K=k}=e"\Kk—If k=0,1,2,~,n. (4.1)
X and Y carry similar probability mass function with rates A X and Ay respectively.
28
4.2.2 Distortion Model
Suppose the transmitter sends a message M, = (k,, 23,, y,) to the receiver through the channel
which is a BSC with BER 6, during the transmission interval 7,. So each symbol in M, can
be distorted independently from the other symbols. Thus, the distortion of each symbol has a
Bernoulli distribution with parameter 6,. As a result, the distortion level of M, in a transmission
interval 7,, denoted by D,, has a binomial distribution with parameters (n, 6,). In practice, it is a
relatively large number, and e, is very small. Accordingly, we can approximate D, with a Poisson
distribution with rate AD, = 716,.
The receiver decodes M, and utilizes :13, to correct possible errors in the message. Depending on
the decoding algorithm, the receiver can correct some of the corruption proportional to the number
of parity symbols in the message. That is, if M, carries 3:, parity symbols, then the receiver is
capable of retrieving up to a x I, error symbols in the message. Here a measures the expected
errorcorrecting capability of a particular decoder. For example, the errorcorrecting capability of
ReedSolomon codes is half as many as redundant symbols (i.e., a = 0.5).
The distortion level D, is random and unknown to the receiver and therefore the notion of
partial recovery is unrealistic in error correction. That is, the receiver can either correct all errors
in M, and acknowledges successful decoding or just assumes that no recovery is achieved. So the
level of distortion in M, after decoding, denoted by U , is
0 D < 
U, = z — CF62 (4.2)
D, otherwrse
Equation (4.2) shows that the distribution of U, is equivalent to the distribution of D, truncated
on or, (see Fig. 4.2). So, the probability of successful decoding of M, is equivalent to the
probability that U, = 0. That is,
la$il _/\ Mb
P(U, = 0) = 19(1), 3 0.73,) = E: 8 01(7)}. (4.3)
d=0 '
29
are)
rule)
— D
I
ax: e
I
Figure 4.2: The density of error after decoding is truncated on our,
Equation (4.3) clearly illustrates that the probability of successful decoding is directly related to
the amount of available redundancy (i.e., x,) and the decoder errorcorrecting capability (i.e., a).
This relationship is presented in the following lemma.
Lemma 1. In a transmission interval 7', with error probability 6,, the V likelihood of successful
decoding of a message III, with typeI parity probability distribution p Xi can be achieved if
1 —1
> __ . .
sz, _ no (m, + ./n6,¢ (11)) ,
where (1)—101) is the Vquantile of the standard normal distribution.
Proof. See Appendix A. I]
30
4.2.3 Buffer Model
The receiver has a ﬁnite buffer with the capacity of m messages. A message enters the buffer
when its decoding with typeI parity symbols has failed. Meanwhile, a message leaves the buffer
when its decoding with additional typeII parity symbols was successful or it is timed out. Any
particular message in the buffer is being served with an individual decoder where a decoder uses
incoming typeII parity symbols to correct that message. Let us assume there are 3 identical
decoders in the receiver that can serve up to m messages in the buffer simultaneously. The buffer
can be modeled as the M / M / s / m queuing system with 3 servers and m buffer slots. Each server
(decoder) serves a particular costumer (message) in the queue and the queue has the capacity m.
In this system, if a new corrupted packet ﬁnds all of the slots busy, it does not enter the queue and
considered as lost to the system.
The M / M / s / m queuing system assumes that messages arrive according to the Poisson process
with rate /\ and the service time has exponential distribution with mean i. To determine these
rates, we let A, and )1, represent the corresponding arrival and service rates when a channel is in
state S, with BER 6,. According to the distortion model, a message enters the buffer if D, > aX,.
Thus, by using Equation (4.3), arrival rate is
Ai = PT{D2' > aXi} (4.4)
= 1— ZPT{X, = z}Pr{D, g oar} (4.5)
23:0
n [ax] (1+1: (1 :1:
n 6,p ,
= 1 — eXI) l—n(€i + 1%)]: Z —dI—$T£' (46)
x=0 d=0
Any particular decoder utilizes typeII parity symbols in addition to the original typeI parity
symbols to decode a particular message. So the service rate is equivalent to the probability of suc
31
cessful decoding using typeI and typeII parity symbols. As a result, according to the distortion
model,
M = PrlDt _<_ 009' + Y0}
Recall that Z, = X, + Y, which is the sum of two independent Poisson variables, is in fact a
Poisson random variable with rate A Z, 2 A X, + Ayi. Correspondingly, the service rate is
n [all nd+z d
6.192
u.=expl—n (e.+pz.)lZZn (,2, Z. (4.7)
.3: 0 d=0
where pZz' = pX, +pYi'
The channel rs in the state S, with the probability of 7r,, therefore the overall arrival and service
rates for the buffer is
N
A = 276,), (4.8)
i=1
N .
,u = Zﬂiui. (4.9)
i=1
From equations (4.6) and (4.7), we observe that A, and p, are functions of the parity symbols
. t . . . . . d . l l f
(118 nbutron parameters p X, and pyz. Each pair of p X, and pyi 111th uces a partrcu ar va ue or
A, and 11,. This veriﬁes our intuitive claim that average amount of parity symbols allocated in
every transmission has a critical impact on the behavior of the buffer and ultimately the overall
performance.
4.3 PEEC Protocol
The errorcombating scheme of the communication model of Section 4.1 is Forward Error Cor
rection (FEC). That is, a receiver uses redundancy symbols that are embedded in the transmitted
message to correct errors. In contrast to the IEEE standard ARQ mechanism, the receiver does
32
not drop a packet unless its buffer is full. As the steady state analysis of the receiver buffer shows,
the average amount of redundancy in a message has direct impact on the buffer behavior and the
overall performance. Transmitting too few parity symbols in every transmission may result in
frequent decoding errors, causing buffer overﬂow. On the other hand, transmitting many parity
symbols may result in degrading the bandwidth utilization (more parity symbols are transmitted
than data symbols). In both scenarios, the average amount of data that are decoded successfully
and delivered to the upper layer decays. So, it is important for an errorcontrol mechanism to
adaptively ﬁnd an accurate tradeoff between the number of data and parity symbols transmitted in
every interval.
In this section, we present the PEEC protocol that uses the receiver acknowledgement to deter
mine the amount of redundancy necessary for the next transmission. Speciﬁcally, PEEC utilizes
decoding and buffer ﬂags to assess the status of the channel condition and the receiver buffer.
Depending on this assessment, PEEC evaluates the amount of data symbols and parity symbols
necessary to send in the next transmission. Fig. 4.3 illustrates the PEEC in more details. It shows
that the PEEC performs two important procedures namely Channel State Estimation and Redun
dancy Allocation.
4.3.1 Channel State Estimation
PEEC uses the decoding ﬂag of the acknowledgment of the previous transmission interval (i.e.,
F,_1[0]) to estimate the state of the channel in the next transmission interval 7",. According to
the Markovian wireless channel model presented in Chapter 3, each state is a representation of
a BSC with a particular BER. Correspondingly, PEEC uses F,_1[0] to guess the BER of BSC
in T,'.
For instance, a decoding failure (F_1[0] = 1), indicates high BER, meaning that, the
amount of typeI parity symbols in the message was not sufﬁcient to correct distortion. Similarly,
a successful decoding (F_1[0] = 0) shows that the BER was low. The errorcorrecting capability
33
Receiver Freedback
Decoding Flag Buffer Flags
Channel State Estimation
Fi—l [O] 5‘
ill
= Redundancy Allocation
F ['11
._1] ,_1 19K," px,,,py.
DATA TYPE" Typf'"
parity parity
I'
I
I
I
l
I
l
I
I
I
l
I
I
I
l
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
Figure 4.3: The architecture of the PEEC protocol
of a decoder and the amount of parity symbols that are sent in the previous transmission have a
direct impact on our estimation. The boundedness of the channel state estimate is given by the
following two Lemmas. Note that, we use the notation 6 to represent 6 estimate.
Lemma 2. In T,__1, ifa decoder with errorcorrecting capability a decades a message with type—I
parity symbol rate p Xi— 1 = g(6,_1) successfully, then for 7,, 6, has the upper bound
. —1 €1—1
6, S g (T) .
Proof. See Appendix A El
Lemma 3. In T,_1, if a decoder with errorcorrecting capability (1 fails to decode a message
with typeI parity symbol rate p Xi = g(€,_1) , then the estimation of BER for T, has a lower
1
34
bound
€, 2 (Whit—1)
Proof See Appendix A. 1:]
Lemma 2 provides an upper bound for the estimate of BER for the next transmission interval
7', when the decoding ﬂag in ACK',1 indicates successful decoding of M __1 (F,_1[0] = 0).
Lemma 3 determines a lower bound when F,_1[0] = 1.
We let EEU) = g"1 (gig—1) and €Z(L) = ag(6,_1) represent the upper and lower bounds of
6, when F,_1[0] = 0 and F,_1[0] = 1 respectively. According to the channel model, since each
(U) (L)
i and 6, correspond to particular
state of the channel corresponds to a particular BER, so 6‘
states which we denote them as U, (i.e., S, = {U,6, = 6§U)}) and L, (i.e., S, = {L,6, =
(
6”,.L)}). Let S, represent the estimate of the state of the channel for transmission interval 7,.
According to Lemma 2, when F'_1[O] = 0, a candidate for S, should be selected from a set
A = {1,2,   ,U,}. To make the best guess, we calculate the joint probability of S _1 =
{Tlfr = 6,_1}, which represents the state of the channel in T'_1 and S, = {wlw E A}, which
represents one of the possible state of the channel in 1,. Using equation (3.10), we choose the
state that introduces the maximum joint likelihood as our best estimate for the state of the channel
in 7,. Therefore,
S, = arg must): Pr{S,_1 = r,S, = w}. w E A
Using similar technique, we can ﬁnd the best S, when F_1[0] = 1.
4.3.2 Redundancy Allocation
PEEC uses S, along with buﬂer ﬂags (i.e., F_1[j] j = 1,    ,s) in ACK,_1 to determine the
distribution of data and redundancy symbols of the message in 7“,, namely p Xi’ pYi , and p1,»,
35
PEEC uses S, to determine p Xi' Recall that, p X, is the rate of typeI redundancy in the
message. That is, p X, represents the minimum number of symbols required to correct each data
symbol transmitted over the BSC channel with BER 6,. For this BSC, there is an uncertainty about
the correctness of each transmitted symbols imposed by 6,. Conceptually, we can resolve this
uncertainty by sending additional information to the receiver which shows whether the channel
caused an error. This is equivalent to sending a redundancy that informs the receiver about the
BSC status with the transmission of every symbol. This redundancy have a minimum number of
symbols that is the same as the entropy of 6,. Thus, we have
. . 1 .
pX,=H=e.logg< >+(1e.>Iog2( ).
:1 1  éi
According to our communication model each buffer ﬂag in the acknowledgment message
(F '— 1 If I j = 1,    ,3) indicates the status of a particular decoder in the receiver. Let
pyz. = (pyz. 1, pin,   , pYis)’ where pYij shows the rate of typeH redundancy symbols al
located for the jth decoder. Intuitively if F _1[j] = 0 then pyij = 0. That is, it is unnecessary to
allocate redundancy for an idle decoder. On the other hand, if F_1 [j] = 1, it means that the j th
decoder is working on a speciﬁc message M (j ) in the buffer. To determine pyij’ let us assume
that M (j ) has been sent in the transmission interval r,_1. Therefore, from the sender perspective,
the uncertainty of corruption in M (j l is dictated by €,__1 (the estimated BER of BSC in T'___1).
Furthermore, every symbol in typeII parity symbols associated with M (j ) (say y(j)) transmitted
in 7, might be distorted with the probability 6,. Hence, the overall uncertainty of corruption in the
new message (M (j l + y(j)) is dictated by the combination of the BERs of BSCs in r,_1 and r,.
This is equivalent to assuming that the message (M (j) + 310)) has been transmitted over a single
BSC which is composed of two cascaded BSCs with parameters €,_1 and 6,. So, the overall error
in (M (j l + yUl) is caused by a channel with BER,
Thus,
Notice that similar technique is applicable for the messages that have entered the buffer before
7',_1 and have already utilized some amount of typeII parity symbols. According to the message
1' ' t ' ' h t' f = .
model, a va 1d message (118 nbutron as to sa 1s y p K, + p X, + py, 1 Thus,
5 (j)
pKizl—H(6‘,)— 2 11(6, )
j=1, F_1[j]=1
The transmitter constructs a message M, according to the message distribution speciﬁed by PEEC.
This distribution is adaptively computed in every transmission interval based on the channel and
the receiver buffer conditions. Therefore, the overall throughput of the communication model
increases when the PEEC protocol is utilized. To ascertain the capability of PEEC, in the next
section, we perform experimental analysis for the proposed protocol using real channel traces.
Meanwhile, in the next subsection, we describe the changes necessary in the current IEEE 802.11
standard to satisfy PEEC requirements.
4.3.3 MAC Frame Structure
The PEEC protocol is designed to provide reliable data delivery at the IEEE802.11 linklayer.
Fig. 4.4 shows the IEEE802.11 data and ACK frame formats. The IEEE802.11 linklayer only
employs an ARQ mechanism, and hence, a Frame Check Sequence (FCS) is used for error detec
tion. For the proposed scheme, we modify the data and ACK frame structures as shown in Fig. 4.4
to incorporate ﬁelds that used by PEEC. First, we modify the frame body ﬁeld and divide it into
three ﬁelds for data, typeI and typeII parity bits. Further, we modify the frame control (FC) ﬁeld
in the ACK frame to incorporate decoding ﬂag and buffer ﬂags. Speciﬁcally, we redeﬁne the retry
ﬁeld to serve as the decoding ﬂag.
37
Octets: 2 2 6 6 6 2 02304 4
equenoe Hamlel FCS I
Frame IID Duration/ IAddress 1 IAddress 2IAddress 3 IS
Control Control
ataii I TypelPerlty
(a) Data frame format
Octets: 2 2 6 4
7 Frame 7 . Receiver 1
Control IDuratron/lD Address FCS I
Bits: 2 2 4 1 1
From Buffer
sMI IRIRMIMMIw lo I all
. Protocol 7 7 To
I Version I Ty” Isumyp" I 08
OS Distribution System
MF More Fragments 7 .
RT Retry F,_1[0] F,_ ,_ Fi—r [S]
PM Power Managment
MD More Data Decoding Flag Buffer Flags
W VWred privacy bit
0 Order
(b) ACK frame format
Figure 4.4: IEEE802.11 MAC frame formats and corresponding modiﬁcations necessary for
PEEC.
As eluded above, when the decoding ﬂag is set to zero, this signals to the transmitter that the last
transmitted packet was decoded successfully. However, when the decoding ﬂag is set to one, this
signals to the transmitter that additional decoding bits are (still) needed for the last transmitted
packet (which was just transmitted and now is waiting to be correctly decoded at the receiver
buffer). The buffer ﬂags indicate the status of one or more (upto 3) previously corrupted packets,
which are being served by one or more 3 decoders at the receiver. Recall that these 3 corrupted
packets were not successfully decoded in prior attempts. Therefore, depending on the number of
decoders utilized, we increase the length of the FC ﬁeld by 3 bits for additional 3 buffer ﬂags.
In the next section, we observe that in practice, by utilizing a single buffer ﬂag that corresponds
38
to a decoder with errorcorrecting capability close to that of perfect codes, the feedback in the
proposed scheme can be limited to only one additional bit to the current IEEE802.11 standard PC
ﬁeld.
4.4 Experimental Analysis
In this section, we evaluate the performance of the PEEC protocol on real channel traces collected
on an 802.11b WLAN described in chapter 3. First, we analyze the impact of the number of
decoders and their errorcorrecting capability factor on the performance. Next, we compare the
performance of the PEEC protocol with the IEEE standard ARQ, enhanced ARQ schemes and
HARQ mechanisms in a practical scenario where the receiver uses a single decoder. Finally, we
evaluate the performance of PEEC using an adaptive LDPC decoder. The performance measure
is throughput (the proportion of transmitted data bits that are successfully delivered to the higher
layers).
4.4.1 Multiple Decoders & Error Correcting Capability Factors
In the communication mode] in Section 4.1, it is assumed that there are .3, s > 0 decoders operating
at the receiver buffer. In addition, the error correction capability of each decoder is measured by
the parameter a. For instance, for perfect codes a = 0.5, since they can correct half as many errors
as there are parity symbols in a message. Intuitively, we should get a better performance with
multiple decoders in place where each decoder is using an errorcorrecting code with capability
close to perfect codes. That is, we expect that the overall throughput monotonically increases
with respect to s and a. Fig. 4.5 shows the PEEC throughput for the channel trace with PHY rate
of 11Mbps and transmission rate 1024kbps. This ﬁgure illustrates the change in throughput with
respect to the variations of s and a. Interestingly, we observe that the throughput slightly increases
39
—e—a.lpha = 0.1 D~~ alpha = 0.2 —x alpha = 0.3 — V alpha = 0.4 —e—alpha = 0.5
0.95—
095 A <2 <2 4 <1 <.‘ e <1 4‘:
W,—€'—v—V——v—v——v——VL——v—V
/.,X' —————— x.............__x_.__x ______ *......___._.x_.__x.. ..... _.x._..._._.)(
0.85—,"
I!
45 13 ......... U ......... Ci ......... {3 ......... a ......... a ......... a ......... a .......... U
g, 0.8”
a
:1
o
$30.75
El
o.7~
c
0.65
1 l I l l l l l 41
1 2 3 4 5 6 7 8 9 10
Number of Decoders
Figure 4.5: Average PEEC throughput for different a values with respect to the number of de
coders (s)
when two decoders are used, but it remains unvaried as the number of decoders increases. This
result suggests that the service time for the buffer does not improve dramatically as the number of
decoders increases.
To investigate this, using equation (4.7), we compute the average service time measured by the
number of transmission intervals for this channel trace. Fig. 4.6 illustrates that the reduction in
average service time is relatively slower for large number of decoders. Moreover, the average ser
vice time is longer when decoders are using codes with lower 0:. Further, when there are multiple
decoders in place, the sender is obliged to transmit parity symbols requested by each decoder. As a
result, the average amount of parity symbols embedded in each message will increase with respect
to the number of decoders; because the service time is not signiﬁcantly improving, it is possible
that using multiple decoders degrades the overall throughput. This phenomenon is observed in
40
—e—alpha = 0.1 61 alpha = 0.2 —x— alpha = 0.3 — 6* alpha = 0.4 —4—alpha = 0.5
‘l
2.5 '
Average Service Time
"A
0.5
Number of Decoders
Figure 4.6: Average service time (measured by the number of transmission intervals) for different
a values with respect to the number of decoders (s).
Fig. 4.5 for a = 0.1. Therefore, using multiple decoders is not only ineffective in improving the
throughput but also may reduce the overall performance.
It is also observed in Fig. 4.5 that the performance increases signiﬁcantly when a decoder is
utilizing a code with decent errorcorrecting capability. So, we conclude that the only parameter
that plays a critical rule in improving the performance is a. This result is desirable in practice
since using more than one decoder in every receiver in the network is expensive and impractical.
This analysis shows that in order to achieve a better throughput, one should employ a decoder
with errorcorrecting capability close to that of perfect codes rather than multiple decoders.
41
Table 4.1: The throughput comparison of enhanced ARQ schemes.
Trace IEEE Standard ARQ MA3 MA5 GMA4 GMA—S
1024kbps 0.2217 0.2904 0.3053 0.3236 0.3261
750kbps 0.8412 0.8434 0.8434 0.8437 0.8437
900kbps 0.7554 0.7768 0.7795 0.7812 0.7816
500kbps 0.7354 0.7551 0.7562 0.7585 0.7586
4.4.2 Comparison with Contemporary Protocols
Various errorcombating schemes have been adopted in both physical layer and link layer for wire
less systems. The current IEEE 802.11 MAC standard uses a conventional ARQ technique [29]:
a single erroneous bit will result in the retransmission of the whole packet. To enhance the ARQ
performance, other techniques such as xor combining (XOR) [33] [34], majority combining al
gorithms (MA) [35] [36] and generalized majority combining algorithms [37] (GMA) have been
developed. Although these schemes are not standard protocol, but they have been used in various
applications such as multimedia. These methods share a common premise and that is to store the
corrupted packets in the receiver and combine them to restructure the original packet. A majority
combing scheme on the other hand uses the last k: received copies of a packet. In this technique, a
bitbybit majority decision is performed to reconstruct a packet. That is, for MA3 (i.e., M = 3),
a bit is one in particular location in a reconstructed packet if at least two copies of the packet
contain ones in that location. In the generalized majority combining scheme, all the possible com
binations of M stored packets are considered. The reader can refer to Chapter 2 for more detailed
description of the functionality of these schemes.
For the set of experiment evaluations presented here, we consider the maximum transmission
limit (MTL) to be six. That is, for every packet there is at most ﬁve retransmissions allowed.
The copies of a particular packet will be dropped if the original packet cannot be reconstructed in
this period. Correspondingly, in our communication scheme, a particular packet is dropped from
42
the receiver buffer if its delay exceeds the MTL. We consider IEEE standard ARQ, MAv3, MA
5, GMA4 and GMAS. The IEEE standard ARQ requests for a retransmission if the received
packet is corrupted and if the number of requested retransmissions is below the MTL. The MA3
performs the majority combining algorithm if the retransmissions of the second and third copies
have failed. The MA3 algorithm always performs majority decision on the last three received
copies. The MAS is employed if the retransmission and MA3 schemes have failed to recover the
corrupted packet. Similarly, the GMAS is applied if MA5, GMA4, MA3 and retransmission
schemes have failed. So, we expect that the GMAS produces a better performance than the other
schemes. Table 4.1 compares the the throughput of these protocols over four channel traces col
lected at sniffer one. We observe that the MA schemes have a slightly better performance than the
IEEE standard ARQ; however the increase in the performance is not signiﬁcant because the ma
jority combining algorithms are repetition code which is a 1—error correcting code. Furthermore,
it is well known that the codes with large length have a better errorcorrecting capability. Hence,
these schemes cannot achieve signiﬁcant improvement in the performance since they are utilizing
repetition codes with length three and ﬁve.
As mentioned in Chapter 2, the concept of Hybrid ARQ (HARQ) schemes have been developed
in information theory and coding theory which employs various codes including Reed Solomon
and LDPC for error correction [48] [5 3]. To compare the performance of PEEC with HARQI and
HARQII, we introduce parameter A. In particular, A speciﬁes the proportion of the redundancy
information in the packet. For instance, for the packet with size n, in the HARQI, the sender
transmits 2% redundancy and 94%;!) data symbols. Similarly, % speciﬁes the amount of addi
tional redundancy that is allocated by HARQII for a particular packet. As illustrated in Fig. 4.7,
the value of A has a direct impact on the overall throughput of the HARQ schemes. Using a small
A will result in the transmission of few redundancy bits which provide insufﬁcient information for
distortion recovery and so FEC becomes ineffective in improving the performance. On the hand,
43
0.9 F
—HARQJ
HARQJI
0.85
0.8
0.75
Throughput
0.55
0.5
0.45 l l _L l J l l I l 1
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5
Delta
Figure 4.7: The Impact of A value in throughput of HARQ schemes for a channel with PHY rate
lleps and transmission rate 1024kbps.
using a large value of A increases the likelihood of successful decoding at the receiver while
decreases the amount of data symbols that are transmitted in every packet; therefore the overall
throughput will decay. We refer to the maximum achievable throughput of HARQ schemes with
respect to A as the best performance of HARQ schemes.
We apply the IEEE standard ARQ, majority combining methods and HARQ techniques as well
as the PEEC on all channel traces. For each trace, we evaluate the throughput of the IEEE standard
ARQ and GMAS and we also ﬁnd the best performances of the HARQ schemes with respect to
A. For these experiments, the MTL is six; for HARQ schemes and PEEC a = 0.3, the buffer size
is 10 (i.e., m = 10) and there is only one decoder operates at the receiver (i.e., s = 1). Fig. 4.8
illustrates these performances with respect the average BERs of our channel traces. Speciﬁcally,
44
0.95
—IEEE ARQ GMA5 mmHARQI (Best)   HARQII (Best)
I
'1‘” .‘. .,: ..............................................
1“ , 
‘ , I Q ..
~ I Q
09......W ...... . ,..’. ,N.‘ ...... ...... ..................
’\ O"'.'~i .‘~
0851' .................. ., ‘ .............. '. ,~ ............................
I... ~
1 . Q
I. Q
*9 08F .................................................... l~’~~.~. .......
:3 I ’Ql
.S‘ 1 ‘
goons ............. 2.,
E ‘2
E4 07 :3
.0
8’»
I
s“
.0
a,
I
\
~‘\
0.95
0.9
_o
8
9
a:
o
'0: .0
or \I
l I
.0
O)
1
0.55 —
..... 1",“\VI........
,5 A 1 1 1 1
o 0.005 0.01 0.015 0.02 0.025
Channel average BER
(a)
—IEEE ARQ munGMAS D PEEC
1' .. .. ......... .....
. ....... V “In“ it .................
_ ............... ....f...h‘..'.‘.'.'3‘.f.11.“. ..
I ‘ '~'~o'
l ‘4.
... ..................................................... ...‘;.
I 1‘ ‘1‘
1".
43 ,_ .............................................................
:3 g .
D. . :
a . . =
50751 ..................... r:
fa’
E" ................. '2 ...........................
0”, innquu
1 1 1 1 1
0.005 0.01
0.5
0
0.015 0.02
Channel average BER
(b)
Figure 4.8: The throughput of different error control protocols over the various channel traces
45
......HARQI (Best) HARQII (Best) «taPEEC
Throughput
3
.o
N
r
81
0.6” ...... ., .. .. . ......
055... ............... .....
05 l J l 1 J
0 0.005 0.01 0.015 0.02 0.025
Channel average BER
(C)
....
 1" : t
0.95“. .. .1 ...........:. ..... ................. .............
~‘.I~  ’ 5 B : l
1 I ~  ' ' ‘—
ogt ... .3. It? ........ 5.1:. ,3 .......... ; .........
E ‘v" ..‘t 'T. 3
I‘ "' .,':. ... ~.;
085 .,¢‘ .............. 1.,‘,.~ ~ ,..M~. .....
' '.' ‘Q '~
7 ‘ I ' ~ In
*9 03.. .................................... lfr~u~m§ ........
a ' ' “N
.3
3075 1 ;
O ‘22
"‘ 1:
"3 2;
[—1 0.7» ,..
7',
0.65... ........... 3,”. ....................
’I” ‘ ““
0.6b ........................... 5’..‘“\II.‘.‘..‘....
055,. .............. . ....... I .......... ..................
0.5 l I L l J
0 0.005 0.01 0.015 0.02 0.025
Channel average BER
((1)
Figure 4.8 continued.
46
Figure 4.8a compares the performances of the IEEE standard ARQ and GMAS with those of the
HARQ schemes. In general, we observe that the HARQII outperforms HARQI for all traces. In
addition, as the previous experiments suggested, the GMAS has a slightly better performance than
IEEE ARQ especially when BER is large. However, we observe that IEEE ARQ performs better
than HARQ schemes when the BER is small (i.e., below 0.005) because these schemes transmit
a ﬁxed amount of redundancy regardless of the channel conditions. As a result, for channels
with low BERs these schemes suffer overcompensation. As the BER increases, the performance
of the IEEE ARQ decreases but at the same time the performance of HARQ schemes increases.
Therefore, they appear close to each other in Fig. 4.8a when BER is ranging from 0.005 to 0.01.
For BER larger than 0.01, the HARQ schemes outperform the IEEE ARQ scheme. Notice that
for some traces with the average BER in this range (0.005, 0.01), a sudden ﬂuctuations in the
performances of the IEEE ARQ and GMAS is detected; this is discussed in the sequel.
Fig. 4.8b shows PEEC performance with that of IEEE802.11 ARQ and GMA5. Similar to the
HARQ schemes, PEEC outperforms the IEEE802.11 ARQ scheme for channels with relatively
high average BERs, but unlike the HARQ techniques for small BERs, PEEC performs very close
to IEEE802.11 ARQ. This result shows that the adaptive redundancy allocation in the PEEC
protocol can successfully prevent overcompensation for the channels with low BERs. In Fig. 4.8c,
the performance of PEEC is compared with the performances of the HARQ schemes for all trace
channels. It shows that the PEEC protocol has even a better throughput than the best throughput
of the HARQ schemes regardless of the channel conditions. The performances of all schemes are
illustrated in Fig. 4.8d.
In our performance analysis, we observe that the throughput of the IEEE ARQ is ﬂuctuating
for the channels with BERs ranging from 0.005 to 0.01. Recall that the IEEE ARQ uses the
retransmission mechanism instead of forward error correction. Therefore, the overall throughput
of this scheme depends on the average number of receptions of distorted packets rather than the
47
average number of distorted bits in a packet. That is, the throughput of the IEEE ARQ scheme
depends on the packet error rate of the channel (PER) rather than its bit error rate (BER). So, the
IEEE throughput ﬂuctuations appear when the PER ﬂuctuates as the BER increase.
Figure 4.9a depicts the average PERs of our channel traces with respect to their average BERs.
We observe that in general for large (small) BERs, the PER is large (small). However, although
theoretically we expect that the PER monotonically increases with respect to BER; for real traces
this growth in not monotonic. Figure 4.9a shows noticeable ﬂuctuations of the PER values when
BER is in the range of (0.005, 0.01) which explains the sudden changes that appear in the IEEE
ARQ throughput in this range. Figure 4% shows the throughput of IEEE ARQ, HARQ—II and
the PEEC protocols with respect to the average PER value of each channel trace. As expected,
the IEEE ARQ performance decreases as the PER increases; however, since FEC is utilized by
HARQ and PEEC schemes, the variations in the PER values have a little impact on the overall
performances of these schemes.
For the experimental results illustrated in Fig. 4.8, it is assumed that the errorcorrecting capa
bility of a code is a = 0.3. To investigate whether the performance analysis given for these results
is always valid and they are not limited to a particular code, we evaluate the throughput of the
PEEC protocol for a values ranging from 0.1 to 0.5 over various channel traces.
In Fig. 4.10a, we observe that even for a = 0.1 the PEEC outperforms the IEEE standard ARQ
for the channel traces with large BER and at the same time, it performs close to IEEE standard
ARQ when the BER is less than 0.005. Notice that a code with an average errorcorrecting capa
bility of a = 0.1 requires 10 parity bits to correct a single error which is a code with a very low
complexity. So, this result suggests that by using a very simple decoder, one can achieve more
than 10% improvement in the overall throughput with respect to the IEEE standard ARQ. On the
other hand, Fig. 4.10 shows that the throughput is above 90% even for most of the channel traces
when a decoder uses a perfect code. Furthermore, it is shown in Fig. 4.10b that the performance
48
R
O O
O ‘ O ' O
1.. 8 z. 81 a.
1
Channel average PE
0
N
0.2
0.15
0.1
0.05
O r 1 i A 1
0 0.005 0.01 0.015 0.02 0.025
Channel average BER
(a) The average PER of the channel traces with respect to their aver
age BER values
_IEEE ARQ HARQII (Best)   PEEC
0.9 ‘
Throughput
.0 .o
‘1 a:
.0
a:
0.5
04 l l I I l I I
o 0.1 0.2 0.3 0.4 0.5 0.6 0.7
Channel average PER
(b) The throughput of the ARQ schemes with respect to the PER vari
ations
Figure 4.9 The throughput of error control schemes with respect to variation in channel PER.
of the PEEC is above the best performance of the HARQII scheme regardless of the value of a.
49
0.551»
0.5
0
0.95
Throughput
O
61’
—IEEE ARQ
PEEC (alpha = 0.1)
nurPEEC (alpha = 0.3)
  PEEC (alpha = 0.5)
1 1 1 g
0.005 0 01 0.015 0.02 0025
Channel average BER
(a)
—HARQII (Best) (alpha 2 0.1)
HARQII (Best) (alpha = 0.5)
III'PEEC (alpha = 0.1)
0.7 
0.65—‘ ..... .. . , . . .
0.6 I. ..........
0'55 ._ . . ............ j .................. j ................ , ................... ..............
05 I J I l A
0.005 0.01 0.015 0.02 0.025
Channel average BER
(b)
Figure 4.10 The change in the PEEC throughput with respect to a over the various channel traces.
4.4.3 Implementation of PEEC using ALDPC
For the experimental results illustrated in Fig. 4.8, it is assumed that the errorcorrecting capability
ofacodeisa =
0.3. To investigate whether the performance analysis given for these results is
50
  IEEE ARQ —PEEC (LDPC) PEEC (alpha = 0.1)
0.9
0.8
Throughput
o .0
O) \I
.0
01
0.4
0.3
o 0.005 0.01 0.015 0.02 0.025 0.03
Channel average BER
Figure 4.1 1 The throughput of the PEEC protocol using the ALDPC decoder over various channel
traces.
always valid, we evaluate the throughput of the PEEC protocol using a relatively simple Adap
tive LowDensityParityCheck code (ALDPC). The experimental setup is as follow: we let a
sender always transmits a zero codeword. We use our channel traces to distort the transmitted
codeword by ﬂipping distorted bits. The receiver uses ALDPC to decode the received word and
checks whether the decoded word is a zero codeword. Upon decoding failure, a receiver stores
the received word in its buffer and requests for additional redundancy. We use the LDPC source
code provided in [104] for our experiment. Note that we use a soft decision decoding using an
iterative belief propagation method which requires a knowledge of channel BER. So, we use our
estimate for channel BER for every transmission interval described in Section 4.3 to decode each
packet. For this experiment, the maximum iteration is 100; the variable side has degree three and
the check side degree is approximately regular.
51
Fig. 4.11 shows the overall performance could improve at a minimum of 25% with respect to
the performance of the IEEE802.11 standard ARQ scheme over channels with higher BER. Also,
PEEC performs close to IEEE standard ARQ when the BER is less than 0.005. To estimate the
average errorcorrecting capability of this decoder, we consider all the packets that are successfully
decoded; for each packet, we compute the fraction of the number of errors by the total amount of
parity symbols embedded in that packet. We ﬁnd that the estimated errorcorrecting capability of
this decoder is around 61 = 0.1. In Fig. 4.11, we also show the throughput of PEEC when a decoder
is utilizing a code with errorcorrecting capability a = 0.1. We observe that the performance of the
model captures the throughput obtained by employing ALDPC. This result veriﬁes the accuracy
of our analysis and suggests that by using a code with errorcorrecting capability close to perfect
codes, we can achieve higher throughput.
4.5 Channel Coding Rate Analysis
An important objective of errorcorrecting schemes is to increase the likelihood of successful re
covery of the original packet by utilizing a particular decoding procedure to recover a corrupted
packet. For instance, IEEE802.11ARQ uses retransmissions as its decoding procedure while
HARQ schemes and PEEC use Forward Error Correction (FEC) codes. Each errorcorrecting
method introduces a channel coding rate measured by
# of data symbols
2 4. 10
# transmitted symbols ( )
which measures the rate of new data transmitted over the channel.
According to the channel coding theorem, a particular decoding scheme has to operate below
the capacity to guarantee reliable transmission. That is
R k retransmission, a
In case of generalized majority combining scheme (GMAk), in i
GMAk successfully recovers a packet when an errorfree copy of a packet is received or any
combination of MAl (l < k) succeeds. For instance GMA5 should apply all cases of the MA3
method on 5 copies so for k = 5, l = 3. Equation (4.16) suggests that each MAl operation
successfully recovers the original packet with the probability of P, when the channel is in state
S,. We let random variable W represent the number of MAl cases that succeed. Having k
packets at the receiver, the number of possible MAl operations is L = (If). Therefore, W
has the binomial distribution with parameters (P,, L). Consequently, the likelihood that GMAk
algorithm successful recovers the original packet (at least one of the L MAl operations succeed)
when the channel is in state S, can be computed as follows,
L
PW(i,k) = Z (3133:“ — P,)L‘$. (4.21)
23:1
th
Therefore, the probability of successful recovery in i retransmission is
111,06) = (1— C,) + ijw(i, k). (4.22)
In general, enhanced ARQ mechanism which employs GMAk successfully recovers the origi
nal packet when (1) retransmission mechanism succeeds in the ﬁrst I — 1 transmissions, (2) MAl
method succeeds in 3,1 5 j 5 k — 1 transmissions and (3) GMAk succeeds in j, k g j _<_ d
transmissions, to recover a packet. Therefore the probability of successful decoding when the
channel is in state S, is computed as follows
Pgma.(i,l, k, d) = Pieeeuil — 1)
+<1 P1eeeli1l—1>)A(i,l.k — 1) (4.23)
+ (1 — A(i,l,k — mm, 1,111)
56
where
(1
111,11, d) = 2(1 w,(k))t_kw,(k) (4.24)
t=k
measures the successful probability of GMA algorithm. Accordingly, the probability of successful
decoding of enhanced ARQ mechanism using GMAk (on average) is
N
Pgma(k1d) = Z irinmaa, k1d). (4.25)
1:1
MA —— k and GM A — 1: have the same channel coding rate as IEEE802.11 in Equation (4.14).
4.5.3 Hybrid ARQ (HARQ)
The successful decoding probabilities computed so far are for decoding methods based on the
concept of pure retransmission. However, the Hybrid ARQ (HARQ) schemes utilize FEC codes
for error recovery. Let a represent an expected errorcorrecting capability of a particular decoder.
Speciﬁcally, if :1: represents the amount of parity bits embedded in a particular packet, then an
a—decoder can correct up to a x 2: corrupted bits in that packet. To calculate the likelihood of
successful recovery for HARQI method, we let random variable D, represent the distortion of
a transmitted packet when a channel is in state S,. Since in state S, the channel is a BSC with
crossover BER 6,, then D, has a binomial distribution with parameters 71 and 6,.
The distortion level D, is random and unknown to the receiver, the notion of partial recovery
is unrealistic in error correction. That is, the receiver can either correct all errors in a packet and
acknowledges successful decoding or can just assume that no recovery is achieved. So the level
of distortion in a packet after decoding, denoted by U,, is
0 13,301:
U ,' = . (4.26)
D, otherwrse
Equation (4.26) shows that the distribution of U, is equivalent to the distribution of D, truncated
on am. So, the overall probability of successful decoding (SD) is
SD(i,x) = P(D, S 0111:) = (0:6)(1— 6,)ax6?_a$. (4.27)
57
In the jth retransmission, a successful delivery occurs if a retransmission succeeds or a packet
h
is decoded. So the probability of successful decoding in jt retransmission g4(j) is
940') = (1 —<1)+<1;SD(J}IJ') (428)
Therefore the successful decoding likelihood in packet recovery under HARQI after (1 retrans
missions is
d .
W) = 2(1 g41—1(1— 94(2)). (4291
2'21
The channel coding rate for HARQI depends on the amount of redundancy carried with a
packet in the ﬁrst transmission 2:1,
Tl. —' II}
R4(2:1,d) = M 1 (4.30)
The derivations of the failure decoding probabilities of HARQII and PEEC are similar to
HARQI. Because the later protocols utilize additional parity bits, the failure likelihood decreases
dramatically as additional parity bits are employed. The channel coding rate for HARQII is
n  $1  (2L2 311')
n + (2L2 31,)
where Y = (yg,    ,yd) represents the amount of additional parity bits.
R5(:1:1,Y,d) = (4.31)
Using the trained channel Markov model of a particular channel trace, we compute the probabil
ity of decoding failure of each of the errorcorrecting scheme based on different channel coding
rates. Fig. 4.12 shows this performance over four different Markov channels, with the average
probabilities of 0.0025, 0.009, 0.018 and 0.03. We observe that the IEEE802.“ ARQ scheme has
a relatively poor performance because regardless of channel condition, the probability of decod
ing failure is very sensitive to the increase of the channel coding rate. MA3 and GMA5 have
a relatively better performance than IEEE802.11 ARQ and even HARQI, but they have to oper
ate way below channel capacity to achieve zero decoding failure. As it is illustrated in Fig. 4.12,
58
 IEEE802.11 "0“ MA3"+ GMSEHARQI '4HAROH —PEEC
_A
I
: : aw“
. ‘ and .
0.8’ ., ,..””—H‘ Q,‘,‘_.,£’
.6 z 9:»  
33 0.7L. ... ., .’.‘.'..’. ...'4. .
'8 : "_" :
8 0.6“ ,.. .....I‘...
D‘ . I".
II  s
I .I
8 05’ . ’.
In .
£11 ', _I
500.4» :~ .I
.5 : I
.U ' I. i
C .. ;.. ., .‘
8 0.3 g, ;
Q I ' 3
0.2—R” .I‘H #3.“.2 
l . I 1
GAIN”, .............. I ................................................................
I
‘ u
(a) Average BER: 0.0025
''''' IEEE602.11 "0' MA—3"+" GMSBHAROI '4HARQII —PEEC
0.8 ,v
.0
‘1
Q
0.6
0.5 ,
Decoding Error Probability
p
<10
0', .
. .4 0.5 . 0.7
Channel Coding Rate
(b) Average BER: 0.0090
Figure 4.12 The variation of decoding failure with respect to variation channel coding rate over
different Markovian Channels. Note that the vertical line represents the channel capacity of a
given channel.
HARQII and PEEC performance are superior to other methods. Meanwhile, as we observe PEEC
outperform HARQII as the channel conditions worsen.
Fig. 4.13 illustrates an overall performance of all schemes over various channels. Speciﬁcally,
59
 IEEE802.11 “0“ MA—3"'+" GM—SBHAROI '4HARQII PEEC
9
a
.0
;
Decoding Error Probability
p o
(A) U!
I Channel CodingoRate
(c) Average BER: 0.0180
0.8 0.9
.4 0.5 0.7
''''' IEEE802.11 "O" MASM"O'" GMSBHARQI 4 HARQII PEEC
_O
O

0.7 '
Decoding Error Probability
.0 .o .o o
M (a) «5 0
.0
.2
Fig. 4.13a shows the maximum channel coding rate of each scheme with respect to the channel
average BER. The maximum channel coding rate measures the highest achievable rate such that
the likelihood of decoding error is zero. The upper bound capacity of each channel is also depicted
in Fig. 4.13a. It is clear that PEEC and HARQII achieve higher rates regardless of the channel
0.e:~ J
............
., 11H}. 13'. 53,. Ram—3.41.543. '
4 0.5 0.6 0.7 0.5 0.9 1
I Channel Coding Rate
((1) Average BER: 0.0300
Figure 4.12 continued.
60
+ IEEE80211 —I—GM5 B HARQI < HAROII + PEEC
1 ....................................................................................
“'5
0.9 . .....................................
0)
*5 0.8._ ......................
Cl: 5
EGO] ...,...,..‘ ......................................
=8 3 i
(3 0.5.
'3 3
—=: ? f
QM ...................... , ..........
s s r
a I i
g 0.3]
2 0.2I "
.1
o ........... l ......... l .......... ‘L ............ L‘ .......... i ............ ; ........... g
0 0.005 0.01 0.015 0.02 0.025 0.03 0.035
Channel Average BER
(a) Maximum Channel Coding Rate
+ IEEE80211 I GM5 B HAROI + HARQII + PEEC
CI .
o .
:4 ; .
C0 7 ’
.5 ',
:3 F
>> 3
:1: .
o. f
d :
O 40' . .;. '1
E i , .
:3 1 ; : .
g 30' ........................................... : .......... \ I ..........
2 20 ..... . : ,
10 , ..........................................................
‘1 IA
° 1 1 1 1
0 0.005 0.01 0.015 0.02 0.025 0.03 0.035
Channel Average BER
(b) Channel Capacity Utilization
Figure 4.13 The maximum channel coding rate and percentage of channel utilization over different
Markovian Channels. Note that the solid line in (a) represents the upper bound of the channel
capacity.
61
condition. In Fig. 4.13b, we observe that PEEC utilizes more than 90% of channel capacity over
channels with average BER less than 0.015. On the other hand, over the channels with BER more
than 0.02 where all other schemes can only utilize less than 50% of the capacity, PEEC operates
above 80% of the capacity.
4.6 Discussion
In this chapter, we studied the problem of reliable transmission over wireless links. In particular,
a contention free wireless communication model was analyzed where a receiver stores corrupted
packets for future error recovery. We developed suitable models for each component of this com
munication scheme to introduce an errorcombating scheme at the link layer, which we refer to as
Packet Embedded Error Control (PEEC) protocol. In addition to theoretically analyzing PEEC,
the performance of the proposed scheme was extensively analyzed over real channel traces col
lected on 802.1lb WLANs. We compared PEEC performance (as measured by throughput) with
the performance of (a) the IEEE802.11 standard ARQ protocol, (b) enhanced ARQ schemes such
as majority combining mechanisms and (c) the well known hybrid ARQ/FEC (HARQ) schemes.
Our analysis and experimental simulations showed that PEEC outperforms all three competing
protocols over a wide range of actual channel traces. Finally, the implementation of PEEC using
an Adaptive LowDensityParityCheck (ALDPC) decoder was presented. In the next chapter, we
extend the PEEC protocol to provide both reliability and ﬂow control for realtime video trafﬁc.
62
CHAPTER 5
DCPEEC: Delay Constraint Error Control
Protocol For Realtime Video
Communication
Realtime multimedia applications require a communication mechanism that provides reliable in
formation delivery while ensuring (1) effective bandwidth utilization to deliver high quality video
contents, and (2) lowlatency to satisfy realtime delay constraint. These requirements make it
essential to design an error control protocol that provides ﬂexible ﬂow control mechanism (with
respect to cost, quality, and latency) in conjunction with reliability in data delivery. Such require
ments are even more critical under wireless environments since wireless channels are subject to
information loss due to the errorprone nature of wireless links and their susceptibility to a variety
of distortions caused by fading, interference, and mobility.
The de facto IEEE802.11 linklayer errorcontrol protocol [29] uses retransmissions to provide
reliability for wireless environments. Although this technique ensures reliability “overalong
run”, it does not provide ﬂow control mechanism with respect to latency. This design strategy
has led to a great deal of inefﬁciency in throughput which introduces frequent information loss in
63
the system. The impact of such information loss could be dramatic on multimedia applications
because any damage to the compressed video stream may lead to undesirable visual distortions at
the decoder [94]. Inefﬁcient channel bandwidth utilization is quite conspicuous in realtime video
streaming since it often results in frame freezing, skipping and/or playback jitter leading to an
unsatisfactory user experience.
Recent works in wireless multimedia communications have proposed crosslayer mechanisms
to overcome performance limitations imposed by conventional protocols [94] [95]. Examples of
these protocols are the Hybrid ErasureError Protocols (HEEPs), well established hybrid ARQ
(HARQ) schemes which make use of incremental channel codes to achieve reliable transmission
over wireless channels [43—45]. Although, these approaches can achieve reliability with fewer
packet retransmissions, but these and other conventional 802.1 1 ARQ based linklayer schemes do
not address issues raised by various realtime video demands such as quality and delay constraints.
In this chapter, we built on the PEEC protocol described in the previous chapter and intro
duce a novel error control protocol for wireless linklayer that targets both reliability and trafﬁc
flow control for realtime video communication. Delay Constraint Packet Embedded Error Control
(DC—PEEC) protocol employs channel codes (using robust and welldeﬁned code rates) in each
packet to ensure that video packets are delivered reliably within an endtoend delay deadline of
realtime video communication. The proposed effort begins by outlining a novel analytic frame
work to capture video trafﬁc ﬂow at the wireless linklayer. In particular, we develop a queuing
model that captures realtime video trafﬁc behavior under reliability and endtoend delay con
straint at the wireless linklayer. Speciﬁcally, we model the linklayer buffer as an M/G/l queuing
system with randomsized batch arrivals of video information having a single server representing
the linklayer protocol with a general servicetime distribution. Using this model, we ﬁnd an op
erational code rate for DCPEEC which guarantees video trafﬁc ﬂow with tolerable latency while
utilizing the channel bandwidth effectively. Our contributions can be summarized as follows:
64
e We develop a novel video communication model to analytically determine the expected
latency of realtime video trafﬁc at the wireless linklayer.
0 We propose the DCPEEC protocol for pointtopoint linklayer wireless communication
which is layer oblivious and provides reliability and ﬂow control for realtime video com
munication in an optimal and joint manner.
5.1 Realtime Video Communication Model
A fundamental objective in realtime video communication is the delivery of compressed video
in a timely fashion to ensure continuous decoding and presentation. To achieve this objective, it
is important to capture the behavior of realtime video trafﬁc more rigorously. To that end, we
adopt a generic realtime video communication model illustrated in Fig. 5 .1. This model captures
a dual—level view of video trafﬁc for wireless communication.
The upperlevel view (i.e., application layer) shows an ideal encoderdecoder buffer model
for video communication analyzed in many multimedia literatures [96]. Under this model, un
compressed video pictures ﬁrst enter the compression engine of the (sender’s application layer)
encoder at a particular frame rate. The compressed pictures exit the video encoder and enter the
encoder egress buffer (at the application layer). Current H.264/AVC standard for realtime video
(e. g., video conferencing) uses baseline proﬁle to encode video stream [93]. Each video frame is
encoded to a compressed Group of Pictures (GOPs) comprising of Islices followed by Pslices.
Similarly at the decoder side, the compressed pictures exit the decoder ingress buffer and enter
the decoding engine. Let Tenc and Tdec represent video encoder and decoder buffers delays re
spectively. Under this upperlevel view the endtoend delay is governed only by the total delay
encountered in both encoder and decoder buffers (encoding and decoding take zero time) and is
65
Aided! : T + Tdec
enc
— —IdeaI transmission —>
M .
Egress Buffer Ingress Buffer
Application Layer
upper Vlow
Transport and
Transport and Operating System Packetization Network Layers
Network Layers
Llnklayer buffer delay: T
[)I'()C
VIOW
ereless Channel Link Layer
Lower
“I Vldoo packet
Figure 5.1 Realtime video communication model.
constant. Therefore,
Aideal = Tenc + TdeC'
However, in general the compressed video data also encounters different protocol and network
delays before it arrives at the decoder buffer. This is captured at the lowerlevel view shown in
Fig. 5.1.
Compressed pictures exiting the encoder buffer are processed by the Operating System (OS)
and converted to transportlayer segments. These segments are then converted to networklayer
datagrams with appropriate headers added. In this packetization phase, compressed pictures are
divided into small video packets. Speciﬁcally, the Network Abstraction Layer Units (NALU) of
H.264 standard is utilized to encode the video stream. Traditionally each NALU is embedded in
MPEG2/RTPIP/H.32x/UDP packets. We choose each NALU packet (at the application layer) to
be embedded within a single UDP packet (at the transport layer) along with an incremental index
for packet sorting at the decoder. Under this setup, the video stream is partitioned into equal and
ﬁxed size video slices which is set to be at most the size of Maximum Transmission Unit (MTU)
including the UDP packet header size and index used for sorting. We represent OS processing
delay at the sender side by T tx The OS then delivers video packets to wireless linklayer where
66
they enter the linklayer buffer. Next, the link—layer error control protocol attempts to deliver each
video packet to the destination over a lossy wireless channel with the delay Tll The video packets
successfully delivered to the destination are passed up to the application layer to enter the decoder
ingress buffer. The processing delay of delivering each video packet from the link—layer to the
video decoder buffer at the application layer at the receiver side is denoted by Tm. Hence, the
total endtoend delay of a realtime wireless video communication A not only depends on the
encoder/decoder buffer at the application layer but also depends on the OS processing delay and
the delay of wireless linklayer protocol:
A = Aideal + Tm; + Try: + Tu.
The process of delivering video pictures is constrained to an endtoend delay A In
wireless:
other words, A is the total tolerable delay representing realtime video communication
wireless
deadline: A _<_ A Hence, those video pictures that miss this deadline are unusable
wireless
for video decoding. This leads to degradation in video quality. Therefore, for realtime video
communication we require the following inequality to be satisﬁed:
Aideal + Tia: + TTIL‘ + Tll S Awireless (5.1)
Let Tproc represent the maximum processing delay of the OS at the sender and receiver sides and
is constant (i.e., T ta: + Tm; S T proc) By substituting Tproc in Equation (5.1), we have:
Aideal + Tmoc + Tu S Awireless (5.2)
Tll S Awireless _ Aideal — TPTOC (5'3)
Tu S T. (5.4)
where T = Awir e l e s S _Aideal —Tpmc is the maximum tolerable delay at the wireless link—layer
(for realtime video communication). Therefore, satisfying the A constraint depends
wireless
directly on delivering the video packets to the linklayer destination within the linklayer tolerable
67
delay T. To that end, we analyze the video packet trafﬁc behavior at the linklayer and model the
linklayer buffer to analytically obtain an average (expected) delay of each video packet at the
linklayer (before it is successfully delivered to the destination).
Recall that, compressed video pictures at encoder egress buffer are partitioned into different
GOPs. OS packetization process generates video packets from each GOP. Here, based on the
GOP content, a random number of video packets are generated for each GOP. Let OS deliver the
video packets associated to every GOP to the linklayer at a rate A. This rate governs the GOP
arrival process at the linklayer buffer. Hence, the arrival process of the linklayer buffer is a
Poisson process having rate A. Thus, the linklayer buffer is a queue with customers arriving in
randomsized batch where each batch represents one GOP and each customer (in the batch) is
one video packet. On the other hand, the linklayer protocol attempts to reliably transmit each
video packet in the buffer over a wireless channel. Thus, the algorithm employed at the linklayer
protocol dictates the service time distribution of the buffer. Consequently, the linklayer buffer
can be modeled as an M / G /1 queuing system with randomsized batch arrivals having a single
server representing the linklayer protocol with a general service time distribution G'.
Let us denote by aj, j 2 1, the probability that an arbitrary GOP consists of j video packets;
and N denotes a random variable representing the size of a GOP (measured in terms of the number
of video packets); hence, P{N = j} = aj. Therefore, the average arrival rate of entering a video
packet in the linklayer buffer is AG 2 /\E [N]. Consequently, the (average) delay for delivering a
single video packet to the linklayer destination V becomes [71]
l E[G2]
v = ,\E[N] [mom/Q + ——2—— , (5.5)
where G and WQ represent, respectively, the service time and the latency of each video packet
(the time that a given video packet spends waiting in the linklayer buffer). On the other hand,
the latency of a given video packet in the queue is equal to the delay for delivering that packet
68
to the destination and the latency due to other video packets in the same batch associated with a
particular GOP WGOP' Thus
WQ = V + ElWGOPl (5.6)
However, the expected latency in the linklayer buffer due to other video packets is:
jaj
E[WGOP] = ; E[WGOPGOP Size] 13W] (5.7)
ElGl(E[N21 — EN). (58)
2E[N]
Using mathematical deductions, from Equations (5.5), (5.6), and (5.8) we obtain
ElGllfglgilEWD + AElleElG2l
WQ = T1]—,\1~:[N]E[G] ' (5'9)
In this work, we use constantquality encoding to have uniform video quality for all video
frames. Consequently, the distribution of the random variable N representing the GOP size is
determined by the nature of the video content being encoded, video encoder type, and the desired
playback quality. Speciﬁcally, the H.264/AVG standard codec uses the quantization parameter
(QP) for each macroblock in each video frame to achieve the desired playback quality for that
video frame. Under this setting, QP dictates the number of bits allocated to each video frame
leading to variable bit rate (VBR) video encoding. This in turn determines the number of video
packets in each GOP and consequently the distribution of the random variable N. Using 15 differ
ent video sequences1 with different QP values (e. g, 20 to 36) suggests that the Gamma distribution
can be well ﬁtted to the empirical distribution of N. For instance, Fig. 5.2 shows that the quantile
function of ﬁtted Gamma distribution accurately captures the quantile values of the empirical dis
tribution of GOP size captured using QP 20. Therefore, we model the random variable N using a
1We use the following video sequences (CIF): akiya, bowing, coastguard, container, deadline,
foreman, haleonitor, husky, mad900, mobile, paris, signJrene, silent, Stefan, students. These se
quences can be found at: http: //media . xiph . org/video/derf/index . html ?rev=
7 8 6 5
69
0.9 r
y
.0
m
r
0.7 r
I
0.5"“
0.3
umulative Probabilit
Q
.0
N
1
0.1 ..
1 000 2000 3000 4000 5000
GOP Size (Kbit)
Figure 5.2 The Gamma cumulative probability function ﬁtted on GOP data distribution of 15 video
sequences encoded with QP 20. '
Gamma distribution with density function
98—9x(9$)v—1
(v — I)!
fN(r) = (5.10)
Accordin 1 ,EN = v andEN2 = U.
g y 1 1 y 1 1 97
Consequently, the average time that a given video packet spends at the linklayer buffer before
it is successfully delivered to the destination is
E[G](%+1)+ $53210} — Va.r[G])
2 — 2%E[G]
W: WQ+E[G] = . (5.11)
To deploy the above video packetlevel queuing model within the context of delayconstrained
video, we adopt the following assumption. The realtime constraint of the proposed video commu
nication model demands that the latency of delivering each video packet to the destination does
not exceed the linklayer tolerable delay deadline T. It is important to note that adhering to this
70
video packetlevel delay constraint satisﬁes the traditional videoframe level delay constraint. As
we pointed out earlier, we adopt a packetlevel delay constraint to be consistent with the packet
level queueing model. The average waiting time of each video packet computed in Equation (5.1 1)
should be less than T (i.e., W S T). Consequently, the linklayer protocol should provide reli
able delivery of new video packets to the decoder while ensuring low latency. Toward that end,
in the next section, we present the Delay Constraint Packet Embedded Error Control (DCPEEC)
linklayer protocol which employs novel rateadaptive channel codes to minimize the latency in
Equation (5.11) while adhering to the realtime video communication delay constraints.
5.2 Delay Constraint PEEC Protocol
In the previous chapter, we have developed a novel reliable MAC layer that employs the same
level of feedback used in 802.11. However, targeting true realtime wireless video will require
muchfurther and muchneeded, novel developments and integration of communication solutions.
DCPEEC framework is designed (based on the realtime video communication model developed
in the last section) to provide reliable and delayconstraint information delivery at the linklayer.
We ﬁrst describe the operational communication model of DCPEEC. Next, we model the service
time distribution in Equation (5.11) based on the DCPEEC functionality. Finally, we describe
two important components of the DCPEEC protocol (namely Channel State Estimation and Re
dundancy Allocation) which are essential to maintain continuous and lowlatency realtime trafﬁc
ﬂow while ensuring maximal reliability and throughput.
5.2.1 Communication Model
In DCPEEC operational communication model a transmission interval Ti is expressed as the du
h
ration in which a transmitter sends the it message (packet) Mi and receives its corresponding
71
Figure 5.3 The acknowledgment format of the DCPEEC linklayer protocol.
acknowledgment ACKi. A transmitter sends a new message after the reception of an acknowl
edgment.
Sender Side
During Ti, a sender transmits a message which is represented by the tuple Mi = [CZ(ki, sci), yi]
where 1132 represents the number of bits in a video packets which are not being retransmitted. In
each Ti, a transmitter encodes kz with parity symbols :rz creating a codeword C, (19,, 272). We refer
to these parity symbols as typeX parity. The receiver utilizes 2:2 to decode Ci. Upon successful
decoding, C, is extracted and 192 data bits corresponding to a GOP are passed up to the higher
layer. In case of decoding failure, the receiver stores Ci in its buffer and issues a request for more
parity symbols. The transmitter also sends additional (typeY) parity symbols denoted by yi. The
receiver utilizes yz symbols to recover old corrupted codewords accumulated in its buffer (e.g.,
Cj,]=1,,i—1).
Receiver Side
We assume that the receiver has a ﬁnite buffer which can accommodate up to m corrupted mes
sages waiting for recovery. If a newly corrupted packet ﬁnds all rooms in the buffer occupied, it
does not enter the buffer and is dropped. The status of the receiver is reported to the transmitter via
certain ﬂags in an acknowledgment message (ACK) which are called buﬁer ﬂags. Fig. 5.3 illus
trates the ACK format. There are m buffer ﬂags are encapsulated in ACK. Let F211;], is = 1,    , m
represent buffer ﬂags in ACKi. Each buffer ﬂag is associated with a particular room in the buffer
and represents the status of that room. That is, if the kth room is occupied then Fi[k] = 1 (as
72
71:7
L kl 1x3] k2 Jxm k3 pm; k, x
Transmitter
L
I I I
 k1 WXEI k2 1x2lxililﬂlf(E
I I \, X \‘
l
f Decoding Achieved . ’_
X Decoding Failed :
Receiver
Buffer .
TypeX TypeY
Figure 5.4 An example of DCPEEC operational communication model consists of four transmis
sion interval.
illustrated in Fig. 5.4). In addition, the receiver estimate of channel condition 51 in 7'1 is also
encapsulated in acknowledgment message. Later, we describe channel estimation process by the
receiver. The DCPEEC feedback scheme requires m additional bits for buffer ﬂags and one ad
ditional byte for channel estimation feedback to the current IEEE802.11 standard frame control
ﬁeld. In our analysis, we choose m = 5.
An example of DCPEEC operational communication model is illustrated in Fig. 5.4. A short
communication consisting of four transmission intervals and buffer capacity of two at the receiver
is shown. During the ﬁrst transmission interval 7'1, a message Ml = [C1(k1,z1),y1] is sent.
There are no typeY parity symbols in Ml, because there is no prior corrupted message in the
receiver buffer, so y1 = 0. A receiver that fails to decode C1, stores 01 in its buffer and sends
73
an acknowledgment ACKI = (1,0, 81). In T2, the transmitter sends Mg 2 [Cg(kg,:1:g),yg =
{y%}]. The receiver uses mg to decode Cg and employs typeY parity symbols :6 (yzj denote
additional parity for Cj, j < i transmitted in Ti) in addition to $1 to decode 01 The receiver
acknowledges ACK g = (1, 1, rig), indicating decoding failure of Cg and C1(k1, $1 + yl). As a
result, in T3, the sender sends M3 = [C3(k3, 3:3), y3 = {3%, y§ H. In 73, the receiver successfully
decodes C3 using 3:3 and Cl(k1,a:1 + 31% + 31%). Because decoding of 01 was successful, the
receiver sets the buffer ﬂag of the ﬁrst room to zero (i.e., F3[1] = 0) but at the same time since
the receiver is waiting for typeY parity symbols to perform decoding on Cg, the buffer ﬂag for
the second room is set to one (i.e., F3[2] = 1); so ACK3 = (0,1,33). Accordingly, in T4,
the sender transmits M4 = [C4(k4,x4),y4 = {342]}. The receiver decodes C4 using x4 and
Cg 2 (kg, :rg + yg + yg) successfully; so ACK4 = (0,0, 34).
5.2.2 Service Time Distribution under DCPEEC
DCPEEC encodes each video packet data bits k7; with $2 typeX parity bits creating a codeword
Ci(kz, 332') in transmission interval Ti. Let the wireless channel be in state Si, each symbol in Ci
is distorted independently from the other symbols with probability of 6.1:. Thus, the distortion of
each symbol has a Bernoulli distribution [71] with parameter 62:. As a result, the error introduced
in C, with the length of ICiI = 192‘ + 332" can be represented by the random variable Ez which has
a binomial distribution Ei 2 Bi HQ ,9).
The receiver attempts to retrieve kz video data bits by utilizing 2:2 parity bits embedded in Ci
Depending on the decoding algorithm, the receiver can correct certain level of error proportional
to the number of parity symbols embedded in the message. DCPEEC uses an iterative belief
propagation LDPC decoder which requires an estimate of channel condition for decoding. There
fore, if the channel estimate is £23 for 2:, parity symbols, the receiver is capable of correcting
up to a(€i) x 2:7; errors out of '02" symbols in the message. Here a(€z) measures the expected
74
errorcorrecting capability of the LDPC soft decision decoder using channel estimate at“ Thus, the
probability of successfully recovering video data bits and passing them up to the video decoder is,
P(Ei S a X xi) = FEi(a(€i)CEz') (5.12)
where F E2, (.) is a cumulative density function of Ei.
Under DCPEEC, in every transmission a new video data bits are decoded by the probabil
ity of FEi (a(€z):ci). Upon decoding failure, the packet is buffered, and decoding attempts are
performed in the consecutive transmissions by utilizing typeY parity symbols. Therefore the
probability of successful recovery of a particular packet increases as more typeY parity symbols
are transmitted. Consequently, the error correction process of every packet under DCPEEC has a
nonhomogenous geometric distribution [99] with parameter pi; 2 FE, (9(3ilzt) which measures
the likelihood of successful decoding (when the channel is in state 52') on t decoding trial using
total parity bits (typeX and typeY) of 2t Consequently, the service time distribution G of the
linklayer buffer (under DCPEEC) in the proposed realtime video communication model has the
following density function
. . t—l .
félt) = P(Successful recovery on t trial) 2 p: H (1 — pic). (5.13)
k=1
Using the density function in Equation (5.13), we calculate (numerically) the ﬁrst and second
moments (i.e., E [G] and E [G2]) of service time distribution in Equation (5.11). As a result, we can
determine an average latency of each video packet at the linklayer under DCPEEC algorithm.
Later, we utilize this latency to ﬁnd an optimal redundancy allocation scenario for DCPEEC.
5.2.3 Channel State Estimation
Maintaining a low latency trafﬁc ﬂow and achieving maximum throughput and reliability under
the DCPEEC communication model will require accurate channel estimation and prediction in
75
realtime. To that end, we utilize physicallayer and linklayer sideinformation (provided in cur
rent 802.11 implementations). It is important to note that accurate estimation and prediction of the
channel condition has a critical impact on the performance of the proposed protocol. This is due
to the fact that DCPEEC employs LDPC codes for decoding linklayer packets, and LDPC codes
use a soft decision decoding (an iterative belief propagation method) which requires a knowledge
of channel bit error rate (BER). Therefore, it is essential to identify practically observable vari
ables, which can be used for reasonably robust channel state estimation. DCPEEC uses Signal to
Silence ratio (SSR) as side information in every transmission [21].
The Markovian channel model described in Chapter 3 implies that in every transmission the
channel is in a particular state represented by a BSC with a unique BER. The objective is to train
the Markovian channel model to achieve accurate estimations of BER values for each state of the
model. The training process is in an online fashion in the sense that DCPEEC adjusts its parame
ters as more and more packets arrived during a session. Speciﬁcally, upon a reception of a packet
in a transmission Ti, the receiver obtains the SSR and estimated BER values of packet preamble.
We let ssrz and D, = g(ssr,) represent the SSR value of packet M, and its corresponding esti
mated BER respectively. A receiver creates a onetoone mapping between each SSR value and
each state of a Markov chain [i.e., (ssrl E SI),   ,(ser E SN)]. It also keeps record of
the observed BER values associated with each SSR, denoted by (Ai,i = 1,    , N). Notice that
the number of states of the channel model is dictated by the total number of unique SSR values
observed by the receiver. The receiver training process is as follow:
1. Obtain ssrz and D, of the received packet in Ti.
2. Find a state where S, E ssri.
3. Add 19, to the list of observed BER values associated with (ssri E Si): Ai = {A13 D2}.
4. Adjust the BER estimation associated with state Si by taking the average value of the up
76
dated Ai
lAil * .
z lAil
In every transmission interval, the receiver adjusts the parameters of the channel model and
sends its estimate of the current channel condition in an acknowledgment message.
5.2.4 Redundancy Allocation
In 72, DCPEEC uses channel estimate of the previous transmission interval (ii—1 along with
buffer ﬂags in ACK _1 to allocate data and parity symbols for Mi Speciﬁcally, DCPEEC uses
5,_1 as its estimate of the channel BER in current transmission interval Ti; so Ei = 82'_1.
The realtime video communication model requires the delivery of each video packet at the link
layer within the linklayer tolerable delay T. Therefore DCPEEC should provide reliable and
rapid delivery of video information to meet this deadline. Meaning, the proposed scheme should
allocate parity bits to each video packet such that the average time that a video packet spends at
the linklayer (before it is delivered to the video decoder) is minimized. In summary the objective
is to ﬁnd an optimal allocation of parity bits in every transmission to
1. ensure the reliability video data bits transmission over the channel while utilizing channel
bandwidth efﬁciently, and
2. reduce the video packet latency at the linklayer obtained in Equation (5.11) to meet the
linklayer tolerable delay T.
To satisfy the ﬁrst objective, DCPEEC should allocate minimum number of parity symbols
which guarantee reliable packet delivery. DCPEEC uses E, to determine typeX parity symbols
33,. Let Txi represent the rate of typeX redundancy in the message. That is, sz represents the
minimum number of symbols required to correct each data symbol transmitted over the BSC chan
nel with BER €23 For this BSC, there is an uncertainty about the correctness of each transmitted
77
symbols imposed by 4%,. Conceptually, we can resolve this uncertainty by sending additional in
formation to the receiver which shows whether the channel caused an error. This is equivalent to
sending a redundancy that informs the receiver about the BSC status with the transmission of ev
ery symbol. According to the Shannon’s channel coding theorem [55] this redundancy must have
a minimum number of symbols equal to the entropy of a BSC channel with crossover parameter
éi Hence, for transmission of 1:, video data bits, DCPEEC should allocate at least k, x H (éi)
parity symbols in C2(ki, :ri). Thus we have
11,: 13,11,H(g,)= er,(e,1og2(%)+(1—e,)1og2( In), (5.14)
where B, is an adjustable parameter which should be tuned to satisfy the delay constraint (second
objective) when the channel is in state Si
Let Wi represent the video packet latency at the linklayer buffer calculated in Equation (5.11)
when the channel is in state 8,. By assuming that a channel permits the transmission of maximum
”2' bits in Ti, the length of a packet should not exceed ”i To ensure that the second objective is
met (i.e., Wi g T), we need to ﬁnd an optimal value of B, in Equation (5.14). This leads us to the
following optimization problem
min ,3, subject to:
W, s T, x, = a,l1~,H(€,) (515)
ki+$i Sni,ﬁi 21
By solving (5.15), DCPEEC calculates t3; ( minimum value for [3,, ﬂ, 2 1) such that the parity
bits :13, allocated to a new video packet it, reduces the average delay W, (when the channel is in
state Si) to meet the deadline T. Consequently, for a video packet with length ki, DCPEEC
allocates 2:, = [cl1323" H (Ei) typeX parity symbols and creates a codeword C2(lci, xi).
According to the DCPEEC communication model each buffer ﬂag in the acknowledgment
message (F_1[j] j = 1,   ,m) indicates the status of a particular room in the receiver. If
78
Fi_1[j] == 0, no parity symbol is necessary. However, F_1 [j] = 1 indicates that room j contains
a particular codeword Ck transmitted in some 7k, k < i which requires additional redundancy
symbols for recovery. Accordingly, Ck with length ”k requires at most T2!“ = 72. k6; H (1%,) parity
symbols for error recovery. However, for Ck, :1: k + 2;;11643 3);“ parity symbols are already
transmitted in the previous transmission intervals 7k,   ,Tz'_1. Thus, typeY parity symbols
necessary to transmit in T, for Ck is 3)? = T!“ — ark + 22;; +1 ylk.
The transmitter constructs a message M, = C, (ki: 13,, yi) according to the message distribution
speciﬁed by DCPEEC. This distribution is adaptively computed in every transmission interval
based on the channel and the receiver’s buffer conditions. It guarantees reliability and tolerable
latency for realtime video communication. Therefore, the overall video quality increases when the
DCPEEC protocol is utilized. To ascertain the capability of DCPEEC, in the next section, we
demonstrate the performance gain of realtime video communication using the proposed protocol
on real channel traces with various error conditions.
5.3 Experiment
In this section, we evaluate the performance of realtime video communication over real wire
less channel traces collected on an 802.11b WLAN as described in Section 3. In particular, we
analyze the impact of the variation in quality and scene change of a particular video stream trans
mitted over wireless channels with varying error conditions. We evaluate the performances for
DCPEEC, IEEE802.11 ARQ and HARQ protocols. For the following experiments, all three
protocols DCPEEC, HARQ, IEEE802.11 ARQ are implemented with OMNET++ network sim
ulator [105]. We use an Adaptive LDPC (ALDPC) codes [104] for channel coding operations
in DCPEEC, Reed—Solomon codes [67] for HARQ, and INET Framework IEEE802.11 mod
ule in OMNET++ for implementation of ARQ mechanism. The performance measure is YPSNR
79
which is a function of the mean square error (MSE) between the values of the original and decoded
Y frame pixels,
2552
”Yorg  ydecng
YPSNR=~ U,,. .......... 5
go .
c6 25 u
S
3:
20‘3".“ ........
T
0.33
O
1 00 1 50 200 250 300 350
Video Bitrate (Kbps)
(a) BER: 0.0001
'0 DCPEEC + ARQ IDEAL "'IIHHARQ
45,... . .1 .. .... ...... 1.
A40
CD
3 . _
a : : z
: ' ' ..... ﬂ
0"! 30 ..ll ......... “a. ......... ....u """"" ..
>1 ..ﬂ ........... 3 .
€90 ‘ :
ES 25" u
g
<
201;:
I
1 00 1 50 200 250 300 350
Video Bitrate (Kbps)
(b) BER: 0.001
0161‘
0
Figure 5.5 Average Y — PSN R of “Stefan” sequence with respect to variation of video bitrate
over different channel traces. The solid line in each ﬁgure represents maximum achievable video
quality for each video bitrate.
82
.h.
01
T
.5
O
I
.......................................................................
......................................................................
CD
01
Average YPSNR (dB)
(D
O
 DCPEEC + ARQ —IDE AL ~IIHARQ
1%0 100 150 200 250 300
Video Bitrate (Kbps)
(c) BER: 0.005
350
.. DCPEEC o ARQ ——IDEAL ~n~HARQ
453 ,
A
O
p—
00
U1
'0‘
""""""
I
Average YPSNR (dB)
(D
O
0 100 150 200 250 300
Video Bitrate (Kbps)
((1) BER: 0.01
Figure 5.5 continued.
83
...............................................................................
350
Average YPSN R (dB)
03
 DCPEEC o ARQ —IDEAL ”DHHARQ
453 ;
401. .
g .e
35. ............................ .............
1. _. .3. ........ 3'
f ..;»  " """"""" "
25. .i ...... : .......................... ‘ .........
201...“...H... ‘ ..... ....................................................
............ u f
?  o  ¢  o  9  +:  o
1 go 1 00 150 200 250 300 350
Video Bitrate (Kbps)
(e) BER: 0.015
 DCPEEC + ARQ —IDEAL ~nHARQ
45.... . , ...... ,
A40»
in
E
(I: 35*
Z.
to
“1* 30
> +
$0
«3 25*
5'3
>
<1:
201. .................... ..............................................
£2 ........... n  a  il  ﬂ  ll """""" '
1  9'''"?' """" f """" ?' """" i """ j
0 1 00 1 50 200 250 300 350
Video Bitrate (Kbps)
(0 BER: 0.03
Figure 5.5 continued.
84
for various video bitrate. This is due to channel adaptive nature of DCPEEC which allocates
parity bits based on the endtoend delay constraint. As a result, DCPEEC sends sufﬁcient video
data bits before the deadline T expires (while ensuring data reliability).
5.3.2 Scene Change
The simulation results presented in the last section illustrates the average playback video quality.
However, for realtime multimedia applications, a high average PSNR value is not necessarily
an indication of smooth realtime video playback. For instance, a single frame skipping, frame
loss or jitter in video conferencing is sufﬁcient to deteriorate the system performance from user
viewpoint. Therefore it is vital that all video frames are delivered and decoded on time. This
objective is more difﬁcult to achieve for video sequences with scene change where each encoded
GOP has signiﬁcantly different bitrate. Hence, it is important for the linklayer protocol to deliver
video data bits rapidly such that all video frames are decoded with high quality regardless of the
variations in channel conditions.
The average PSNR value is shown in Fig. 5.5b for Stefan CIF encoded with QP 20 (video
bitrate of 350Kbps) transmitted over a wireless channel with BER 0.001. It suggests that both
IEEE802.11 ARQ and DCPEEC should have comparably similar high performance (PSNR is
above 35dB) for Stefan CIF sequence. Fig. 5.6 shows PSNR values of individual decoded video
frames for Stefan and Foreman CIF for this simulation. Interestingly, Fig. 5.6b shows that al
though IEEE802.11 ARQ achieves high PSNR value for most of the frames, it cannot deliver all
of them (e. g., frame #100) on time and therefore we observe ﬂuctuations in frame quality.
To illustrate the impact of these ﬂuctuations on the playback quality of realtime multimedia
applications, Fig. 5.7 provides a sample of ﬁve consecutive frames captured from Stefan CIF
sequence. In this Figure, the frame: distortion, freeze and loss are easily identiﬁable under
IEEE802.11 ARQ and HARQ. This stems from the fact that these protocols are not adaptive to a
85
eDCPEEC a ARQ —IDEAL « a HARQ
1 0 _1 L 1 1 _L j
0 50 100 1 50 200 250 300
Frame number
(a) Foreman CIF 30 fps
—e DC—PEEC <> ARQ —IDEAL 1:1 HARQ
8
3
0'3.
Z
w
01*
>~
20
15 '
1 o l l l l l J
O 50 100 1 50 200 250 300
Frame number
(b) Stefan CIF 30 fps
Figure 5.6 The Y — PSN R values of sequence frames encoded with QP 20 and transmitted over
channel with BER 0.001.
sudden change in channel condition. Although the wireless channel has overall low BER (0.001),
it still has some temporal regions with severe error conditions which lead to the ﬂuctuations in
frame quality.
86
L€Z# aweH
11
3
,1... «ta Quart111,1,
,5 ' r
B N
3
(D
31’
(D
N
(D
92:11 aweu i
7£Z# award
sso7 salad
3 $231! 91112.13
Figure 5 .7 A quality comparison of ﬁve consecutive frame captures of “Stefan CIF" delivered by
different error control protocols.
87
 DCPEEC 1+ ARQ —IDEAL  HARQ
40,.9'9W_ ,1.
\‘ .m: :
A $3. 9"¢ ....... . .
35 1,1.  1‘ ’~"'*  '
5% :69 7 ; : 7
V E I
z N! 1
CD 3 1 7‘
ad: 25,. h..II ' ............................
: 'u..u.n: :
E '1 'u.,, j
6 f ...................................
15f .. .. .‘0‘9.n ..... Uzi _ _ _ _ _ _...._._.._. _ _'_"'_"_3
1O 1 1 1 1 P 1
0 0.005 0.01 0.015 0.02 0.025 0.03
BER
(a) “Foreman CIF”
 DCPEEC + ARQ —IDEAL HARQ
40_W _ ..... .
1 f
A :\ ~,°". ___________ :
@352 .. ...“ .......... ;..... .. ""'0
g Gunner ‘
ﬁ 1 11 ,
I 2
525. '1 3
! 2 ;
. .; ;
_ No ....... "'.'_“.';'.".':'_;:; """""""""""""""" a
15 1 A ‘Y' 1 ""‘7 '''''''' 9
0 0.005 0.01 0.015 0.02 0.025 0.03
BER
(b) “Stefan CIF”
Figure 5.8 The impact of BER variations in frame quality (encoded with QP 20) under different
error control protocols
Fig. 5.8 illustrates the impact of BER variations in frame quality. As we expected, for low
values of BER (BER less than 0.005) IEEE802.11 ARQ and DCPEEC performs close to ideal
88
frame quality. However, as BER increases the performance of IEEE802.11 dramatically decays
and falls below HARQ at the same time DCPEEC maintains the high visual quality. For trans
missions where BER is more than 0.015, DCPEEC achieves 1015dB PSNR gain over HARQ
and IEEE802.11. This result clearly demonstrates the efﬁcacy of DCPEEC in allocating parity
bits for video transmissions to achieve reliability condition and meet endtoend delay constraint.
5.4 Discussion
In this chapter, we investigated the problem of reliable and delay sensitive wireless video com
munication. We proposed a queuing system which captures the behavior of video trafﬁc ﬂow at
the wireless linklayer. Using this model, we introduced DCPEEC, an error control protocol for
wireless linklayer which deploys various channel codes to ensure the delivery of video packets
in a timely fashion while efﬁciently utilizing channel bandwidth. In particular, DCPEEC uses
the receiver feedback to estimate the channel condition and deploys optimal channel code rates
using realtime video communication mode] to construct each video packet. The performance of
the proposed scheme was analyzed by simulating realtime video communication over real chan
nel traces collected on 802.11b WLANs using H.264/JV T JM14.0 video codec. The experimental
results demonstrated performance gains of 510dB for different realtime video scenarios. In the
next chapter, we pursue a paradigm shift where both reliability and stability are ensured at the
underlying linklayer. We investigate the feasibility of designing stable and reliable link layer
over pointtopoint (singlehop) 802.11 channels; and more importantly we study the feasibility
of achieving signiﬁcantly improved throughput by using this type of linklayer.
89
CHAPTER 6
ACE: A Reliable and Stable Wireless Link
Layer
Reliable communication over wireless channels is very challenging since wireless links are error
prone and susceptible to noise imposed by fading, interference and mobility. Additionally, wire
less networks need to accommodate diverse trafﬁc types with various requirements for rate, re—
liability and delay. The wide variety in trafﬁc rate requirements leads to a large variance in the
trafﬁc volume injected into the network which often leads to throughput instability. This is ex
acerbated due to errors introduced in the wireless network. Leading linklayer protocols focus
primarily on reliability and ignore the stability aspect of wireless communication; relying on (or
arguably shifting the problem to) higher layers to provide stable ﬂow control for both realtime
and nonrealtime trafﬁc. It is our belief that one of the important goals for any link layer protocol
is to provide system stability by ensuring that higher layers are neither starved for information
packets, nor is there a glut of packets leading to buffer overﬂows. More speciﬁcally, the current
linklayer paradigms aim at providing reliability in hoptohop communication without regard to
trafﬁc demand. One outcome of failures at the linklayer, resulting from errors in the wireless
network, is that the network layer assumes there are broken links in the current packet route. This
90
leads to nonessential determination of new packet routes by the routing agent [76]. Similarly,
wireless errors are interpreted as congestion by the transportlayer resulting in an unnecessary
drop in transmission rate [82, 84].
Current IEEE802.11 ARQ protocol [29], which focuses only on reliability, attempt to recover
from losses using retransmissions. Corrupted packets are discarded without regard to the number
and location of the errors. This methodology is designed to ensure “reliability in the long run”,
i.e. the packet would eventually be recovered. However this approach suffers from degradation
of throughput rate and overall system instability. This is easy to see, since even a single bit error
in consecutive packets leads to packet drops and therefore discarding of a large number of correct
data bits. As a result, the network utilization deteriorates steadily and rapidly with increasing
channel Bit Error Rate (BER). In an alternative approach, Hybrid ARQ (HARQ) protocols are
proposed, which make use of incremental channel codes to achieve reliable transmission over
wireless channels using fewer packet transmissions [43,44]. However, both the ARQ and HARQ
based approaches follow the conventional paradigm and do not address throughput stability issues
raised by varying trafﬁc demand and intensity. This design strategy has led to a great deal of
inefﬁciency in throughput and to other major technical issues and challenges at higher layers. A
well—known example is the T CP overwireless performance degradation phenomenon, which led
to major research efforts and numerous studies [84] in attempt to mitigate the shortcoming of the
lower layers.
In this chapter, we propose a paradigm shift where both reliability and stability are ensured
using an Automatic Code Embedding (ACE) wireless linklayer protocol. The proposed wire
less ACE linklayer (a) employs a theoreticallysound framework and a corresponding strategy
for embedding channel codes, using robust and welldeﬁned code rates, in each packet; and (b)
selects the code rates in an optimal and constrained manner to ensure reliability, stability, and
maximum throughput. We believe that this work is the ﬁrst to present a theoretical framework for
91
analyzing and designing a wireless linklayer protocol that targets system stability in conjunction
with reliable communication. We begin by outlining a novel joint analytic framework to predict
system behavior under ACE. Speciﬁcally, we ﬁrst obtain an upper bound on operational code
embedding rate that ensures reliability. Next, we develop a queuing model that captures system
behavior under stability condition. In particular, we describe the linklayer failures as an onoff
source model using a twostate Continuous Time Markov chain (CTMC) model. We deploy ﬂuid
approximations to analytically characterize the buffer growth. By utilizing these models, we ﬁnd
a lower bound on operational code embedding rate which guarantees stable operation while uti
lizing the channel bandwidth effectively. An important conclusion of the above analysis is that
various trafﬁc demands (in terms of reliability and stability requirements) can be met using a
packetbypacket code embedding rate constraint that is independent of trafﬁc type. This leads
to simplistic, trafﬁcindependent and elegant design rules for the ACE protocol, while providing
reliability and stability in an optimal and joint manner.
The ACE protocol is a pointtopoint wireless communication protocol where the receiver stores
corrupted packets in its buffer for further recovery. The channel conditions are estimated using
simple feedback mechanism. ACE utilizes receiver BER estimate and buffer ﬂags encapsulated
in the ACK message to determine the composition of the next packet to be transmitted by the
sender. We demonstrate experimentally that ACE provides both rapid and reliable wireless data
transmission under varying channel conditions. Our contributions can be summarized as follows:
a We present two distinct analytical frameworks to determine optimal code embedding rates
which ensure system reliability and stability. We further show that these conditions are met
using a packetbypacket code embedding rate that is independent of trafﬁc type.
0 We propose the ACE protocol for pointtopoint linklayer wireless communication which
is layer oblivious and provides reliability and stability in an optimal and joint manner.
92
6.1 Preliminaries
In this section we determine the likelihood of successful transmission by introducing distortion
model for ACE. This model along with the channel model described in Chapter 3 provide essential
tools in ﬁnding an optimal code embedding rate constraint for the ACE protocol. Note that in the
,9 “
following discussion, the terms “message , packet” and “codeword” are used interchangeably.
6.1.1 Distortion Model
The distortion model measures the distortion level of a received packet and computes the like
lihood of successful recovery of the packet under embedded channel coding. To develop this
model, we let 02(11):, 552') represent the transmitted codeword in r, where kz is the number of data
symbols which are encoded with 11:, parity symbols. Letting the wireless channel be in state S ,
each symbol in C, is distorted independently from the other symbols with probability of 61'. Thus,
the distortion of each symbol has a Bernoulli distribution with parameter 62. As a result, the error
introduced in C, with the length of C, = k, + 37,, can be represented by the random variable E,
which has a binomial distribution a can be written as E2” z Bi(Ci, 62'). In practice, IQ] is a rel
atively large number, and e, is very small. So, we can approximate E, with a Poisson distribution
with rate AEi = [CZlei.
The receiver attempts to retrieve k, data symbols by utilizing 1:, parity symbols embedded in Ci
Depending on the decoding algorithm, the receiver can correct certain level of error proportional
to the number of parity symbols embedded in the message. Speciﬁcally, for 2:, parity symbols,
the receiver is capable of correcting up to a x 2:, errors out of C, symbols in the message.
Here (1 measures the expected errorcorrecting capability of a particular decoder. For example,
the errorcorrecting capability of ReedSolomon codes is half as many as redundant symbols (i.e.,
a = 0.5) [67].
93
f1, (e)
f1), (e)
006.5 e
1
Figure 6.1 The density of error after decoding is truncated on 0a,.
The distortion level E, is random and unknown to the receiver and therefore the notion of partial
recovery is unrealistic in error correction. Meaning, the receiver can either correct all errors in C,
declare successful decoding or just assumes that no recovery is achieved. So the level of distortion
in C, after decoding, denoted by U , is
0 E2: S arc,
E.
‘l
Ui = 9(51'1181') ={ (6.1)
otherwise
Equation (6.1) shows that the distribution of Uz is equivalent to the distribution of E, truncated
on 0133,; (see Fig. 6.1). Therefore, U, has the probability density function
FEz(O‘xi) u = 0
= 6.2
fUi(u) fEi(u) u>axz~ ( )
94
where F Ei (u) is a cumulative density function of Ei Correspondingly, the probability of suc
cessful decoding of 71, is equivalent to the probability that U21 = 0. That is,
[Gail MAC}?
P(U =0): FE2( (137;) :1; e ei— T()1' (6.3)
This density determines the likelihood of successfully error recovery using aerror correcting
codes. In the following section, we use this likelihood to determine an optimal code embedding
rate necessary for reliable and stable operations in wireless communication.
6.2 ACE Code Embedding Rate
This section describes two distinct analytical frameworks that determine the upper and lower
bounds on operational code embedding rates under Automatic Code Embedding (ACE) wireless
linklayer protocol. The ﬁrst analytic framework determines the upper bound on operational code
rate that ensures reliability. The second framework develops a queuing model that captures stable
system behavior and identiﬁes the lower bound on operational code rate under stability condition.
The operational code embedding rate measures the fraction of data symbols that are embedded
in a particular codeword. For instance a codeword Cz(ki, 1:2) is generated based on the code rate
k.
6.2.1 Code Rate: Reliability
One of the main objectives in wireless communication is reliable data transmission. We deﬁne
reliability as follows:
Deﬁnition 3. System is reliable when information is transmitted with no or diminishing error over
a wireless channel.
95
Recall that during 7, the channel is in state S, and every transmitted symbol is altered by the
error probability ei. The sender uses the channel kz' + 2:, times to transmit a codeword Ci (hi, xi)
encoded with parity symbols Ii The amount of error introduced in the received codeword (on
average) is (k, + Iilfi According to the distortion model developed in Section 6.1.1, a decoder
can correct up to arr, errors in the codeword. Thus, to successfully deliver kz data symbols over a
wireless channel, the following inequality has to be satisﬁed:
(’67: + l‘ﬂez' S O'Clii. 62' 6 FN
In addition, if a channel permits the transmission of n, symbols in r, then the length of a codeword
should not exceed 72,. Based on these requirements, we have the following optimization problem:
max kz subject to:
(6.4)
k215i + :L‘z'(€i — 01) S 0 and k7; + 21315 717;.
This leads us to ﬁnd an upper bound on the operational code embedding rate that ensures reliability
which is given by the following Lemma:
Lemma 1. The operational code embedding rate that ensures reliability in wireless transmission
over a channel in state Si is bounded above by
6i
RiS1——.€i<<01
a
where a is errorcorrecting capability of a decoder.
Proof See appendix. C]
6.2.2 Code Rate: Stability
Most Internet applications are subjected to various requirements for reliability and delay. For
example, the quality degradation is signiﬁcant in audio/video conferencing if data packets are
not delivered in a timely fashion. The wide variety in trafﬁc rate requirements leads to a large
96
gr——Linklayer————
ACE £1115)
“Decoder
Higher
:: b. Buffer Length] Layer
Figure 6.2 System model for stability analysis in wireless Communication.
variance in the trafﬁcvolume injected into the network. This often leads to throughput instability.
We deﬁne stability as follows:
Deﬁnition 4. System is stable when higher layers are neither starved for information packets nor
is there a glut of packets leading to buffer overﬂow
Figure 6.2 shows a queueing model for the system. The consumption rate 0 of the buffer repre
sents the rate at which higher layers remove data symbols from the buffer. One of the important
stability requirement is that the buffer has to be nonempty to avoid execution stalls. This property
is satisﬁed when data arrival rate is high enough to satisfy the data consumption rate. Execution
stalls refer to a condition where higher layers cannot continue execution because there is no data
symbol available in the buffer, leading to system instability.
The ﬂuctuations of the buffer growth can be captured by computing limiting distributions of
the buffer length using a general model of ﬂuid entering and leaving a single buffer. The input
and output rates of the buffer depend on the external environment: let Z (t) be the state of the
external environment and B(t) be the amount of ﬂuid in the buffer at time t. In our framework,
Z (t) indicates the decoding outcome in the linklayer (later, we model Z (t) as a twostate CT MC)
and B (t) is the number of data symbols in the buffer at time t. The dynamics of the buffer length
is captured by a ﬂuid process B = {B(t),t 2 0} (driven by Z = {Z(t),t 2 0} process) given
by:
%(K — 77(Z(t 1) (6.5)
97
where n(Z(t)) is called the drift function which measures the difference between entry rate and
exit rate at state Z (t). To ensure that B process does not become negative, we let 77(Z(t)) =
max(17(Z(t)), 0) when B(t) = 0.
To calculate the limiting distributions of B(t) with respect to Z (t), we let {Z (t),t 2 0} be
an irreducible CTMC on state space S = {1, 2,    ,M} with generator matrix Q = [qiji Cor
respondingly, (B, Z) = {(B(t), Z (t)),t 2 0} is a bivariate markov process with the limiting
distribution deﬁned as:
F(b1j)=t_1}$OOP(B(t) S b1Z(t) S j) 1S j S M (6.6)
By deﬁning:
F(b) = [F(b, 1), F(b, 2), . . ,F(b, M)]
D : d109177(1)177(2)1"'177(Mll
where D is the drift matrix, Mitra in [97] shows that F (b) satisﬁes the differential equation of a
form
dF(b)
dz
D = F(b)Q. (6.7)
By solving the differential equation in (6.7), we can obtain the limiting distributions in equa
tion (6.6).
The limiting distribution determines the likelihood of buffer length variations in every state of
Z (t). In our framework, we deploy these distributions to determine the lower bound on operational
code embedding rate which ensures stability regardless of the state of Z (t).
From the hi gherlayer viewpoint, Z (t) the decoding process in the linklayer, can be expressed
as an onoff ﬂuid source model. Such a source stays on for an exp(w) and stays oﬁr for an erp(,8)
amount of time. It generates ﬂuid at rate k, when it is on and does not produce any ﬂuid when it
is oﬁ’. Accordingly, a successful decoding at the linklayer indicates that the source is on. Using
98
the distortion model, with the channel in state S,. the amount of time that the source is on is
determined as
2
w. = Pr(Successful Decoding in Ti) = FEi(a:rz). (6.8)
Correspondingly, the amount of time that the source is oﬁr is ,8, = 1 — “’2"
Using the onoﬁ source model, the environment process Z = {Z (t), t _>_ 0} in equation (6.5) is
modeled as a twostate CTMC on state space S = {1 =on,2 =off} with the following generator
“wi wz’
Q—( 132' '1').
Recall that when the source in on, is, data symbols enters the buffer while data symbols are
matrix
removed from the buffer at the constant rate c regardless of the state of the source. Therefore, the
D: [Ci—C 0
0 c
Using the matrices Q and D, we can solve the differential equation in (6.7). The ﬁnal solution
drift matrix is given by
isgivenby
F(b,1) = 13.,(1—eAb) (6.9)
F(b,2) = wi—wgeib, (6.10)
Based on the above derivations, kiwi represent the expected number of data symbols injected
into the buffer when the channel is in state Si Since the buffer has ﬁnite capacity, the following
condition has to be satisﬁed to prevent buffer overﬂow
< c. (6.11)
Using this model, we determine the lower bound on operational code embedding rate under
ACE that satisﬁes the stability condition. This is given by the following Lemma:
99
0.95
Unreliable Region
C
RI
V? 5‘
Stability
Reliability for aError Correcting Codes
0.9
Code Embedding Rate
0 0.005 0.01 0.015 0.02 0.025 0.03
Channel BER
Figure 6.3 Operational code embedding rate domain with respect to reliability and stability.
Lemma 2. The operational code embedding rate that ensures stability in wireless transmission
over a channel in state S, has a lower bound
52'
Ri21_; ei<< 0.3"
Lﬂ
0.2r
O.1~ ......
0» 1 .. 1 . . . ; .. 1
0 200 400 600 800 1 000 1 200 1400
Consumption Rate (Kbps)
(C) BER: 0.007
+IEEE802.11 ARQ+ACE
1 .1 .
3" f
0.9. ................................. k .............
. 4 E
0.8“ ................................... I‘M... ...........
1:» 1 :
2:: 071. ........ ‘ ........
a 1 2
c6 O_6v =..:. ....................
C73 I
.8 0,5» ‘1' .........
4—7  I
04* .
8 '4.
0.3., 1.} ..........
C13 ‘:
0.2~ 1“
0.1a ....... 3‘ ..........
3‘
0,. .......... 1 .......... [... ...... ‘ ........... ' ........
0 200 400 600 800 1 000 1200 1 400
Consumption Rate (Kbps)
((1) BER: 0.009
Figure 6.5 continued.
than 0.002). This result is expected since for channels with low BER the likelihood of corrup
tion is very low and a simplistic ARQ mechanism is sufﬁcient for error recovery. Over channels
109
 + IEEE802.11 ARQ + ACE
1r .
9 ,
* 3
(19’ b 3
",g
0.3—  1g
>> ‘1
4n?
53(l7r ‘

“g 0.6.. I. .........
4.; 
m i
'U 0.5.. ‘ + ................
3 I
§i(l4r' 3‘ .........
CE 013* 
0.2,. 2‘ .....
s 3
0.1— .1.
0. 1 .. , M 1. ,. 1.x“ ' ‘ H.'
0 200 400 600 800 1000 1200 1400
Consumption Rate (Kbps)
(e) BER: 0.018
+ IEEE802.11 ARQ+ ACE
1.. . 1
09
08
if:
;: 07
.5
d 015
43
m
13(15
’8’ 0.4
$0.3 
El
02 .
OJ ........
0 200 400 600 800 1000 1200 1400
Consumption Rate (Kbps)
(f) BER: 0.020
Figure 6.5 continued.
with BER in a range of 0.002 to 0.007, both protocols produce similar performances, however
ACE outperforms IEEE802.11 ARQ for higher consumption rates. When the channel BER ex
110
ceeds 0.007, the ACE performance is signiﬁcantly better than IEEE802.11 ARQ performance.
For instance, ACE guarantees 100% expected stability for consumption rates up to 800Kbps over
channel with BER 0.009 while the trafﬁc delivery is 80% unstable under IEEE802.11 ARQ at
this rate. Further, over noisy channels with BER more than 0.18, we observe a drastic drop in
expected stability under IEEE802.11 ARQ as the consumption rate exceeds 300Kbps meanwhile
ACE maintains stability for source rates as high as 700Kbps. In this ﬁgure, the vertical line rep
resent the sender transmission rate. We observe that expected stability drops to zero (constant
instability) when the consumption rate exceeds the sender transmission rate.
6.4.2 N onRealtime 'h'afﬁc
The main objective in nonrealtime trafﬁc delivery is to maximize the bandwidth utilization of
the wireless medium “per channel use” while providing essential reliability. We compare the
performances of ACE and IEEE802.11 ARQ under different channel conditions. The performance
is in terms of average goodput which measures the average number of new data symbols that are
delivered correctly to the destination per channel use. So, average goodput closer to one is an
indication that the protocol utilizes the channel more efﬁciently.
Fig 6.6 illustrates the average goodput achieved by ACE and IEEE802.11ARQ over variety of
channel conditions. In Fig. 6.6a we observe that IEEE802.11 ARQ and ACE performances are
almost identical when the BER is small (i.e., below 0.005). As the BER increases the decline in
average goodput becomes more rapid for IEEE802.11 ARQ than ACE. For example, over traces
with BER ranging from 0.015 to 0.02, IEEE802.11 ARQ performance is around 50% while ACE
hovers around the 70% mark. We also observe that average goodput under IEEE802.11 ARQ
declines dramatically as channel Packet Error Rate (PER) increases as seen in Fig. 6.6b. Overall,
this result shows 10% to 30% improvement in average goodput under ACE for nonrealtime trafﬁc
communication. Also, it is observed than ACE in general operates closer to channel capacity than
111
— Channel Capacity  + IEEE802.11 ARQ I ACE
0 1 0.00511 A 0.01 A 10.015 v 002 ”10.025. 10.03
Average Channel BER
(a) Channel condition (Average BER)
— Channel Capacity  4 IEEE802.11 ARQ I ACE
...
3 :__
Q: ' 3
PG .
g0 i ’x L
8 0.4  a; 3
;> _ H‘s; ........
< 0.3 ;‘~,
0.2L w.
0.1”
0.1 0.2 0. 3 0. 4 0. 5 0.7 0.8
Average Channel PER
(b) Channel condition (Average PER)
Figure 6.6 The average goodput of ACE and IEEE802.11 ARQ over various channel conditions.
Note that channel capacity in each ﬁgure represents the maximum amount of achievable goodput
without errors.
IEEE802.11 ARQ.
112
Wired Network i W1
ireles
Access Point
TCP Receiver
TCP Sender Router
Figure 6.7 Heterogenous network model.
6.5 Throughput analysis of TCP
The J acobson’s adaptive window ﬂow control algorithm is common for most TCP variations [83]:
let W (t k) be TCP sender congestion window width at time instant t k and Wth(tk) be a slow
start threshold. TCP sender operates at slow start phase if W (t k) < Wth(tk). In this phase, each
ACK causes W(tk) to be incremented by one. When W(tk) exceeds slowstart threshold, the
TCP sender enters congestion avoidance phase where each ACK increments W(tk) by 1/W(tk).
TCP sender exits the congestion avoidance when the timeout occurs. In this case, the congestion
window is set to one and WWW?) is set to [W(tk)/2].
This simple algorithm is well established for congestion control in wired network. However,
due to lossy environment of wireless links, TCP congestion control suffers from performance
degradation since packet losses in wireless links are interpreted as congestion by the TCP agent.
Because leading linklayer protocols focus primarily on reliability and ignore the stability aspect
of wireless communication, numerous studies have led to vast variety of TCP congestion control
algorithms [84] in attempt to ﬁx TCP overwireless performance degradation phenomenon. We
argue that since ACE is designed to guarantee stability as well as reliability at the linklayer, the
traditional TCP congestion control algorithm should perform relatively well over wireless link
despite the lossy environment.
113
6.5.1 Network Model
We consider a heterogeneous network model consisting of wired and wireless sections depicted
in Fig. 6.7. A TCP sender located within a wired section of the network is connected to a TCP
receiver placed in a wireless section. An access point (AP) connected to the wired section, receives
transmitted packets and sends them over a contention—free wireless channel. The wired network
comprises multiple links connected through different routers. In our analysis, we model such
network as a single link with average capacity of c packet—per—second and a bottleneck router
buffer with ﬁnite capacity. A particular packet traversing the wired section is stored in the router
bottleneck buffer as well as AP buffer before it enters the wireless section.
In our network model, a packet loss occurs under the following scenarios: (1) Congestion
based loss: A transmitted packet is dropped at the wired section due to buffer overﬂow of the
bottleneck router. (2) APbased loss: A transmitted packet which successfully crossed the wired
section never enters the wireless channel and is rather dropped at AP. This kind of loss is due
to the instability of the linklayer which causes AP buffer overﬂow. (3) distortionbased loss: A
broadcasted packet over the wireless channel gets corrupted due to wireless noise. This packet is
not retrieved due to linklayer unreliability and is reported as lost to T CP agent.
6.5.2 System Model under ACE
In this section, we perform extensive analysis on our network scenario to determine steady state
loss observed at the T CP sender. We assume that ACE is an underlying error combating scheme
in wireless MAC layer.
According to our network model, a particular packet traverses multiple queues before it is sent
over the wireless channel. These queues represent the bottleneck router buffer at the wired section
and also the AP buffer. In addition, under ACE, if a decoding of corrupted packet fails, it is
114
Router Buffer AP Buffer ACE Buffer Higher
Layer
Figure 6.8 A system of queuing network for the heterogenous network under ACE protocol.
stored at the receiver buffer for future recovery. In this system, since all three buffers have limited
capacity, a packet loss occurs if any of these buffers are full. From the TCP sender perspective, the
cause of packet loss is unknown. That is, TCP sender is unable to identify the location of a loss
in the network. In addition, the behavior of one queue impacts the behavior of other queues. For
instance if the AP buffer is full, packets in the router buffer have to wait before they are transmitted
to the AP. So, the assumption that the loss process in these queues are independent is rather naive
and one has to analyze the joint behavior of these queues to capture more accurate estimate of
loss behavior. To that end, we model our network scenario using a system of queueing network
depicted in Fig. 6.8. In this system, Qi, i = 1, 2, 3 with a limited capacity of Bi, 1' = 1, 2, 3
represent the router, AP and ACE buffers respectively.
To analyze the behavior of this system, we let X, (t) denote the number of packets arrive at the
Qi: i = 1,2, 3 at time t. Then, X(t) = [X1 (t), X205), X3(t)] is a Markov Chain whose transition
rates are A, ”1, pug, quz and #3 where q,u2 and n3 measure the departure rate of a packet from the
system. Note that 1) measures the likelihood that the received packet is not decoded successfully
using typeI parity bits; q = 1 — p. To determine the steady state loss probability in this system,
we derive the stationary distribution of the process. Let
7r = lim PrX t=m,X t=n,X t=l
mm Hm { 1() 2() 3() }
denote the stationary distribution of X(t). By examining particular states of the Markov chain,
115
we drive the balance equations for the process stationary distribution. The intuition behind these
derivations is that in a steady state analysis, the outgoing rate from particular state is equivalent to
the incoming rate to that state. For instance, Fig. 6.9 illustrates steady state transitions when the
system in in state (m, 82, B3). It shows the system status where the router buffer accommodated
m packets and the AP and ACE buffers are full and drop any incoming packets. The system
enters to this state under the following scenarios: (1) there was m — 1 packets in Q1 and a new
packet arrives, (2) there was 172. + 1 and 82 — 1 packets in Q1 and Q2, and a packet is transmitted
from router to AP. On the other hand, a system exits state (m, 82, B3) if: (1) any incoming
packet arrives so there are m + 1 packets in Q1, (2) a receiver successfully decodes a transmitted
packet from the AP, (3) ACE successfully decodes a corrupted packet using typeII parity bits. By
applying the above scenarios, the steady state equation for
"77131.32 =_t_lj$100PT{X1(t) = va2(t) = Ble3(t) = B3}
(0+q#2+“3)7rm,32,33 : A”m—1,BQ,B3+l‘17Tm+1,Bg1,B3' IS m S 81_1 (6'13)
By applying this methodology, we derive the balance equations for all possible states of the
queueing system. The complete list of these equations are given in Appendix. To determine
7r we solve the balance equations of steady state distribution as a system of linear equations.
m,n,l’
Let H = (711,1,1, ~  ’Wm,n,lt   ”31,8218? represent a vector of unknown variables and A
is a L x L coefﬁcient matrix with L = Bl x 82 x B3. Then, the steady state equations can be
presented as
An=6 (on)
Using Gaussian—Jordan method, we are able to determine II and therefore ”m,n,l'
The steady state probability distribution enables us to perform thorough analysis of the proposed
queueing system. However, this probability distribution itself is a function of transition rates of
116
1 (m+1.Bz.Ba)
qlLtZ
(01.32.33)
#3
("1+1 2821 783)
(mr821B31)
Figure 6.9 The state diagram of system dynamics where Q1 = m, Ile = B2, Q3 = B3.
the process. Accordingly, it is necessary to compute the transition rates of a Markov Chain. In the
following section we determine the arrival and service rates of the queueing system namely A and
,ui,z' = 1, 2, 3 as well as parameter p.
Arrival and Service rates
In our analysis, we model a wired section of our network scenario as a single wired link with
average capacity of c packet—persecond and a bottleneck router buffer with size B1. Under this
model, the arrival rate of the system is equivalent to the transmission rate of a TCP sender X(t) =
W(t)/T where W(t) deﬁnes the maximum number of unacknowledged data outstanding in the
network at the sampling time instant t and T represents the roundtrip time (RTT) which refers
to the amount of time that elapses between the instant that the sender transmits a packet and the
instant at which it receives the acknowledgment (ACK) for that packet. We assume that the ACK’s
117
are cumulative and errorfree. Thus,
A = x(t) (6.15)
,ul 2 c. (6.16)
To compute the service rate of the AP buffer #2, it is important to consider the underlying error
control scheme utilized by AP. Under ACE, in every transmission interval Ti, AP transmits a new
packet. Further, additional parity bits are transmitted with a new packet upon of receiver request.
Thereby, in steady state, the AP buffer transmits a new packet at the every transmission interval.
Thus
#2 = Elrl (6:17)
The proportion of packets that enters the ACE buffer Q3 is characterized by parameter p. Any
particular packet transmitted over the wireless channel enters Q3 when its decoding with typeI
parity symbol fails. Therefore, ﬁnding p is equivalent to computing the expected rate of decoding
failure using typeI parity bits. To that end, we let 0, represent the distortion distribution of a
particular packet transmitted when a channel is in state S, with BER 52’ and Xi represent the
distribution of typeI parity bits. Then, the event A, 2 {Di > aXi} indicates the decoding
failure of a packet using typeI parity bits where a is an errorcorrecting capability of a decoder.
By applying the statistical models developed in Chapter 6, we have
an: T+x 7; :1:
—n(€i+pXi) n l' Jn elei
Pr(Az)=1— e (6.18)
l 1
(17:0 7‘20 T13.
According to the Markovian channel model introduced in Chapter 3, the channel is in state S,
with the steady state probability of 7Ti, therefore the overall probability of decoding failure is as
following
N+1
p: EilAl = Z rtPr(A.) (6.19)
i=1
118
Any particular packet leaves the ACE buffer Q3 when its decoding using its original typeI
parity with additional typeII parity bits is performed successfully. So, in the steady state analysis,
the service rate of ACE buffer is equivalent to the expected likelihood of successful decoding using
typeI and typeII parity bits. Let Yz represent the typeII parity distribution of a packet when the
channel is in state Si Then, the event T2 : {Dz _<_ a(Xz + 13)} indicates the successful decoding
of a packet in ACE buffer. Using the distortion model developed in Chapter 4, we have
n 1.021 nr+z€7fpz
— + . Z
Prm) = e ”(61 1’22) Z ' 2' I, (6.20)
r.z.
2:0 r=0
where Zz = Xi + Y2. Thus, the service rate of Q3 is
N+1
#3 = 13,[7‘] = Z 7rzPr(Tz). (6.21)
i=1
The derivations of transitions rates and the steady state probability distributions completely
characterize the dynamics of the proposed queueing system. The average time that a particular
packet spends in the system is
E[W] = 22: (mug1+5) + p 1.
The congestion likelihood region speciﬁes trafﬁc condition in wired section of the network.
To capture the impact of wireless channel condition on overall performance we use our channel
123
model to simulate various wireless channels. We use Equation (3.8) to compute the steady state
average BER and PER of channel.
Our analytical performance evaluations steps are as follows:
1. We consider each class of congestion likelihood in conjunction with various wireless chan
nels.
2. We compute the transitions rates of corresponding queueing systems associated with ACE
and IEEE802.11 ARQ using Equations(6.15)(6.29).
3. We utilize these rates to construct the balance equations for each queueing model (see Ap
pendix).
4. We apply GaussJordan method to solve the balance equations to evaluate the joint steady
distribution function of each model.
5. Using Equations (6.24) and (6.31), we evaluate the steady state loss likelihood under each
model.
This process is repeated for different combinations of congestion likelihoods and channel con
ditions. Fig. 6.12 illustrates the variations in steady state throughput in different congestion like
lihood regions. In this ﬁgure, the throughput is depicted for packet sizes of length n = 500 and
n = 1000. We observe that regardless of underlying wireless error control protocol, the overall
throughput decays when wired network becomes more congested. However, in each of conges
tion conditions in the wired network, ACE introduces higher throughput in comparison with the
IEEE802.11 ARQ scheme as the wireless channel BER increases. Further, it is observed that
IEEE802.11 ARQ throughput is very sensitive to the size variations of transmitted packets. This
phenomena stems from the fact that the overall PER of a channel which has a direct impact in
IEEE802.11 ARQ service rate increases as the size of the packet increases. However, since ACE
124
—ACE(n=500)
OACE(n=1000)
  IEEE802.11(n=500)
 o 1555802.1 1(n=1000)
Throughput
8
I
o 0.005 0.01 0.015
Channel Error Probability
(a) Low congestion
— ACE(n=500)
OACE(n=1000)
  IEEE802.11(n=500)
 o EEE802.11(n=1000)
.0
Throughput
o p o
(to b 0'!
I l l
’
I
.' o
I
I
x
O
N
1
?
I
I
o
T
P’;
E,
i
I:
o
I
0.005 0.01 0.015
Channel Error Probability
O
(b) High congestion
Figure 6.12 The steady throughput of network model using ACE and IEEE802.11 ARQ over the
various channel traces with respect to different congestion likelihoods.
125
uses parity instead of retransmission to recover errors, the overall throughput is a function of chan
nel BER. So, although an increase in packet size would decrease a throughput, this decay is not
signiﬁcant as in case of IEEE802.11 ARQ scheme.
The expected congestion window variation in congestion avoidance is,
m — T)<1— 56,,» _ 1
EAW= — t—T6t Wt. 6.34
l 1 WW) 2X( k ) (k) (k) ( )
Upon simpliﬁcation, the equilibrium throughput is
A 2(1 — 8) 1
= . — 6.35
x 5 T ( )
which is a wellknown result on steady state behavior of TCP [83] where 5 is the equilibrium loss
probability which is equivalent to it L 0 S S in our analysis.
The analysis of this section suggests that the steady state of loss probability decays dramati
cally when ACE is utilized at the link layer. Further, Equation (6.35) lshows the direct impact
of steady state loss probability of overall equilibrium throughput. Therefore, we expect that the
TCP throughput improves dramatically when ACE is utilized at the linklayer. In the next section,
we conduct an experimental analysis on TCP performance to demonstrate the accuracy of our
intuition.
6.5.5 Experimental Performance Analysis
Using I NET F ramewo rk TCP model in OMNET++, we analyze the TCP throughput variations
over different channel traces when ACE and IEEE802.11 ARQ are deployed in the linklayer. We
consider a heterogeneous network model consisting of wired and wireless sections depicted in
Fig. 6.7.
Fig. 6.13 illustrates TCP throughput under different wireless channel conditions. We observe
that over channels with low BER where the probability of packet loss is low, TCP achieves similar
performance under ACE and IEEE802.11 ARQ. Under these channels, mostly Congestionbased
126
 + IEEE802.11 ARQI—ACE
1100“.H.H...nh.ﬂ.hn .HH,.HMHV.H“”_H..HHHH.,H
1000?’ ............... E .......... _ ....... E ................... E ....................
ﬁr 90° i 2 i ‘
v I
f
'2? 600.. :3: ..H.pm. ‘ ......
g? 500,....If l ' ..H.H. A H
E ‘ l r l
B 4mH1:H:”‘ .......... ' ‘ ..... .l ......... i
. . l . .
O '1. " c'u', : . ' 2 g r... ‘
' ‘h f “' ‘
1m)... ....... . ....... , ................... ,........_ ........... : ....... ‘ ...........
0 1
0 50 100 150 200
Session Period (See)
(a) BER: 0.002
 + IEEE802.11 ARQIACE
1100, ..................... ' ....................... . ...................... ;
1000..“_MH.NU.H,3MNJ.H.HHH H..NHHHJHLHHHHHHHE
ii: 900.... g. .. E
g 8002
+3 7OO.M.H.....HHH..t.‘ "'E
:1 ti I .
ho _ 1 151? 1. r .1 .L. .', \ H._ 3
8 500 ' ' I t . .
1b O ‘ g
H ' 4 "2 ‘ I r ‘R I
J: 400, ,H . ""1 .....,¥ .‘ 5 .H , M,.‘,.
E4 g I V's; , y . f
100» , f
0 i i a
0 50 100 150
Session Period (Sec)
(b) BER: 0.005
Figure 6.13 TCP throughput variations over different channel traces having IEEE802.11 ARQ and
ACE in the linklayer. The horizontal line in each ﬁgure represents the transmission rate of the
corresponding channel trace.
losses are observed in the wired section. Meanwhile, signiﬁcant throughput difference is easily
identifiable as the channel BER increases. For instance, TCP gains throughput of 10% to 50%
(e.g., ACE achieves 500800Kpbs throughput while IEEE802.11 ARQ in under 200Kbps) over
127
 + IEEE802.11 ARQ I ACE
1100”
1000*
”g; 900
8:. 800—~
8.
.5: 600“ , , 2
.93”
O 500"
36:." 400»
E1
Q, 300*
E3 zoo
1oo~~~2
0 4g 1 i 1
0 50 100 150 200
Session Period (Sec)
(c) BER: 0.009
+IEEE802.11 ARQ+ACE
1100{ ................ . ....... ..: ........................... 1 ........................... .
1000 .
M 800» f , .
5 :
2.? .
o 500’ 3
3 400
E1 5
O 1‘» f ’“o
E4 200. 1"“‘54/1 ‘0"*‘.W,’H .3... . ...s. .. .
1mg ......... .......... . .:..
0 i 1 i
0 50 100 150
Session Period (Sec)
((1) BER: 0.011
Figure 6.13 continued.
channels with BER more 0.009 under ACE. This signiﬁcant difference stems from the fact that
ACE targets stability and reliability of wireless communication. This lead to fewer APbased and
distortionbased losses in wireless section under ACE in comparison with IEEE802.11 ARQ.
128
— + IEEE802.11 ARQIACE
1100,.. .
”c?
a.
.o
5
4.3
:1
o.
.1:
60
:1
o
H
.:t
E4
B 200, _ «......oué‘voodwo¢\'f*..’x.A,.‘
1oo~~ .. A
0 1 1 1
0 50 100 150
Session Period (Sec)
(e) BER: 0.018
+IEEE802.11 ARQ+ACE
1000’
E 900.... .
§ 800' ~
3.
a 600’ ‘
3"
O 500*
E 400»
H
g, 300...
O i 3
E" 200», r*++,o‘f+‘w**§+oo‘s «*‘W;
100» ~ i ‘
o l L J
0 50 100 150
Session Period (Sec)
(1) BER: 0.025
Figure 6.13 continued.
6.6 Realtime Video Simulation
To further analyze the impact of the ACE protocol and compare it with the conventional
IEEE802.1] ARQ protocol over the performance of particular application, we simulate realtime
129
h
C
1
<3
00
o
r
‘9
Average YPSNR (dB)
8 8
—L
(’1
1O0 500 1000 1500 2000
Video Bitrate (Kbps)
(a) BER: 0.002
 o IEEE802.11 ARQ+ACE
.5.
O
3
8
Average YPSNR (dB)
M
(II
20
15 ,
10 1 3' 1 1
0 500 1000 1500 2000
Video Bitrate (Kbps)
(b) BER: 0.005
Figure 6.14 Average Y  PSN R with respect to variation of video rate over different channel
traces. The vertical line in each ﬁgure represents the transmission rate of corresponding channel
trace.
130
+IEEE802.11 ARQ+ACE
40 ................... .. ..... ...................
CO
0
Average Y—PSNR (dB)
8 81
.—L
U‘
1 00 500 1000 1500 2000
Video Bitrate (Kbps)
(c) BER: 0.009
 + IEEE802.11 ARQIACE
A
0
ﬂ
0)
01
I
8
Average Y—PSNR (dB)
[0
0
20
15 '
10 1 if i g
0 500 1000 1500 2000
Video Bitrate (Kbps)
((1) BER: 0.011
Figure 6.14 continued.
131
Average YPSNR (dB)
 + IEEE802.1 1 ARQIACE
CD
01
0)
0
Average YPSNR (dB)
N
01
40 r ‘
35 _ . ........................................................
30 ....................................................................
25
20
15 '
10 m 1 1
0 500 1000 1500 2000
Video Bitrate (Kbps)
(6) BER: 0.018
20 '
15 ‘
El" *
0 500 1000 1500 2000
Video Bitrate (Kbps)
(f) BER: 0.020
Figure 6.14 continued.
132
video communication. The simulation setup is as follows: a particular video stream is encoded
using the H.264/WT standard software [106]. The encoded video streams (slices) are buffered
at the sender to be transmitted over the wireless channel. The ACE protocol is simulated with
the network simulator OMNET++ software [105]. ACE encodes each video slice using ALDPC
codes [104] and transmits the encoded packet over a wireless channel. Each transmitted packet is
distorted based on the channel traces. Speciﬁcally, an XOR operation is performed between the
trace packet and ACE packet. The corrupted packet is decoded using ALDPC. The A—LDPC uses
BER estimate determined by a channel model which was trained with previous received packets.
If the packet is not decoded successfully, it is stored in receiver’s buffer and additional redundancy
is requested according to ACE.
To prevent framefreezing or synchronization mismatches during realtime video communica
tion (for e.g., video conferencing), the video packets need to arrive in a timely fashion. Those
packets which miss their deadlines are unusable by the decoder, leading to degradation in video
quality. To ensure smooth video playback, we require packets arrive at or above particular rate
which is speciﬁed by the video bitrate. The simulation is terminated when all the video slices are
transmitted by the sender. We measure the decoded video quality (average PSNR) for different
video bitrates. We repeat the simulation to compute the performance of IEEE802.11 ARQ. We use
IEEE802.11 [29] ARQ implemented in OMNET++ INET Framework. In these simulations,
the maximum retransmission limit is set to four. To achieve a fair comparison, ACE receiver’s
buffer size is also set to four. For all simulations, the packet size is 1000 bytes and each video
slice is of length 125 bytes.
Figure 6.14 illustrates the decode video quality of StefanCIF (30fps) sequence in terms of
average PSNR over different channel traces. Notice that when video encoder/decoder uses low
video bitrate the video quality decays. Therefore, in these plots, we observe a low PSNR value
for both protocols for video rates below 100 Kbps. As the video rate increase, each video frame
133
Si
?m
. in“h".——
A
is encoded using more data samples. We observe that for good channel conditions (BER less than
0.002), IEEE802.11 performs slightly better than ACE. The reason is that the level of noise over
these channels is very low and since IEEE802.11 transfers video data only, more data is available
for the video decoder resulting in slightly better video quality than that of under ACE. However,
as the BER increases, PSNR values under IEEE802.11 ARQ tend to decline rapidly. Speciﬁcally,
we observe ACE protocol ensures the video quality of 30dB for video rate 800Kbps over channel
with BER 0.02 while IEEE802.11 ARQ is less than 20dB. Overall, we observe that utilizing ACE
protocol over channels with BER more than 0.009 produce 510dB performance gain in video
quality over wide range of video rates.
6.7 Discussion
In this chapter, we studied the problem of reliable and stable operations at the wireless link
layer. In particular, an Automatic Code Embedding (ACE) wireless linklayer protocol has been
proposed that (a) employs a theoreticallysound framework and a corresponding strategy for em
bedding channel codes, using robust and welldeﬁned code rates, in each packet; and (b) selects
the code rates in an optimal and constrained manner to ensure reliability, stability, and maximum
throughput. Through distinct analytical frameworks, we demonstrated that there is a unique solu
tion for the code embedding rate at which stability and reliability at the linklayer is achievable.
Our extensive analysis of ACE protocol over real channel traces collected on 802.11b WLANs
for realtime and nonrealtime trafﬁc, TCP throughput and realtime video communication scenar
ios show that ACE signiﬁcantly outperforms the conventional IEEE802.11 ARQ over varying
wireless channels conditions. In the next chapter, we investigate the impact of prioritization on
wireless communication. We build on the ACE framework to achieve preferred data recovery
order across connections, while maintaining stable and reliable data ﬂows in wireless networks.
134
'1'
CHAPTER 7
PACE: A Prioritized Wireless Link Layer
To achieve superior linklayer wireless communication one need to target the following critical ob
jectives: (i) achieving sustained trafﬁc stability (maintaining continuous realtime ﬂow under delay
constraints), (ii) ensuring maximal reliability and throughput, (iii) exploiting sideinformation for
channel estimation/prediction, and (iv) interacting with the higher layers for prioritized commu
nication and improving quality of service. We believe that these objectives represent a viable and
necessary set to support a diverse wireless linklayer communication with various requirements
in rate, reliability, and delay. However, achieving these objectives simultaneously is a difﬁcult
task since they have conﬂicting requirements. In our prior work [2], we have demonstrated the
feasibility of designing stable and reliable linklayer under Automatic Code Embedding (ACE)
framework over pointtopoint (singlehop) 802.11 channels. However, what is ultimately needed
is a comprehensive framework that targets all of the above objectives (stableandreliable commu
nications, exploitation of side information, and interaction with the higher layers) jointly.
In recent years, various decoding schedulers [8890] have been proposed to improve the overall
throughput in wireless linklayer communication. The majority of these efforts either consider the
standard ARQ approach [91] or the Hybrid ARQ (HARQ) schemes [92] such as: diversity com
binin g [63], code combining [52], and incremental redundancy. Approaches outlined in [52,63,92]
135
F. _n'v'; J. 'I. h"
l
are based on code puncturing methods [62]. These techniques assume (i) the complete knowledge
of channel quality; and (ii) a slowfading wireless environment. Under such assumptions, a de
coder scheduling scheme only attempts to balance the quality of service for heterogeneous trafﬁc
requirements. This design strategy only targets quality of service and largely ignores the other
objectives of wireless linklayer communication outlined above.
In this Chapter, we build on the ACE framework to achieve preferred data recovery order across
connections, while maintaining stable and reliable data ﬂows in wireless networks. Under the
proposed Prioritized ACE (PACE) framework, our ACE based stableandreliable1 linklayer will
employ a novel rateadaptive Low Density Parity Check (LDPC) channel codes while interact
ing with the higher layers to provide a dynamic decoder scheduling service over varying wireless
channel condition. Speciﬁcally, we develop a LDPC decoding model to capture the decoding
process for linklayer trafﬁc and use it to determine an optimal code selection strategy for max
imal bandwidth utilization. Further, we ﬁnd an optimal code embedding rate under the PACE
framework to jointly meet the reliability, stability, and delay constraints of the wireless linklayer
communication. We classify heterogeneous linklayer trafﬁc arrivals into different priority classes
based on packet delay constraints and the distortion suffered. The trafﬁc arriving in each prior
ity class is modeled as a poisson process. Consequently, we formulate the linklayer buffer as a
multiclass M / G / 1 priority queuing system where the decoding process (service process) of the
PACE buffer is captured by nonhomogeneous geometric distribution [99]. Given the linklayer
buffer model and the LDPC decoding model, we determine the optimal dynamic decoder schedul
ing under the PACE framework. This scheduling policy is a special case of a classic scheduling
problem solved by Plambeck et al. in [100] and is asymptotically optimal.
The PACE protocol incorporates the LDPC model and the dynamic scheduling policy into the
original ACE protocol. We show experimentally that PACE improves the performance of the ACE
1For the deﬁnitions of reliability and stability under the ACE framework refer to Chapter 6.
136
protocol over wireless channels with varying conditions. Our contributions are:
‘ 0 Develop a LDPC decoding model used to select the code with best errorcorrecting capabil
ity from an ensemble of codes.
0 Model the linklayer buffer as M / G / 1 priority multiclass queuing system to determine an
optimal dynamic decoder scheduling policy to achieve improved quality of service while
maintaining sustained stability.
0 We develop the PACE protocol that provides reliable and stable wireless communication for
high demand and delay sensitive heterogeneous linklayer trafﬁc.
7 .1 Illustrative Example
In this section, we brieﬂy consider a communication example between two wireless nodes. This
example consists of four transmission intervals where each transmission interval T represents a
time slot during which a sender transmits a packet and receives its acknowledgment. The sender
wants to transmit four data packets (e. g., K1,    , K 4) each with length of 1: bits to the receiver.
The ﬁrst and the last packets (K 1 and K 4) are nonrealtime. That is, impact of the delay in de
livering these packets to a higher layer is insigniﬁcant on the performance of the corresponding
application (e.g., SMTP packets). On the other hand, K 2 and K3 are realtime. Consequently,
these packets should be passed up to the higher layer within an endtoend delay constraint, oth
erwise they are unusable for the application (e.g., realtime video packets). The wireless channel
condition is gradually improving. Speciﬁcally, the channel is in severe condition (BER greater
than 0.02) in 1'1. During 72 and T3 the channel BER reduces to 0.01 and 0.005 and ﬁnally the
channel is errorfree in T4. We consider the following scenarios:
137
i i i
i. i Elf
: : :
I I
. : :
: : : 
§§§IBER=°
5 a 5 
‘ i i i  '
: : : +
lK1:LKrJ:[K1:K1l
: : :
: : :
(a) IEEE802.11 ARQ
i
5.x If
I
I
‘ BER = 0.01
lK1X1HK1IK1I 1K1 1...]  K2 lle
C1(K1’x1)5 C1(K1’x1) C1(K11X1)E C2(K2,x2)
(b) HARQ
..1I......I
..(booocconccc
.ocuocucucoucococu.no1
1—
CD
ITI
I!
ll
.0
O
0
0
1;]
Figure 7.1 A wireless linklayer communication example consisting of four transmission intervals
under different error control protocols.
1. Ideal scenario: Under an ideal scenario all four packets are transmitted over the channel and
received without errors. This gives the throughput of one and all packets are delivered to
138
Ea
IBER= 0.005I
BER=OD1
POOOW03Ccoccd
J
.....C.C.........1D......‘
5
F
l
Kixilé 1 K2 1sz 1
c ,,(K,,x ) :M 22[c (K2,x2),y‘2]:M2 [c2 (K2,x2),y,]:M [C (K..x.).y4]
j......F......6........
(c) PACE
Figure 7.] continued.
the higher layer. However, since the channel BER is nonzero in the ﬁrst three transmission
intervals, the odds of receiving an errorfree packet are very low.
. IEEE802.11 ARQ: This scheme uses a retransmission for error recovery. As illustrated in
Fig 7.1a, in 7'1, the sender transmits K1. Since the channel BER is nonzero, the received
packet is erroneous. Consequently, the receiver requests for a retransmission of K1 in 7'2
and also in T3 because the channel BER is still nonzero. In 7'4, K1 is ﬁnally delivered to
the receiver without errors and passed up to the higher layer. This creates the throughput of
1 _ 3k
IE 2 0.25 since K 2, K3 and K 4 are not transmitted during the four timeslot window
of this simple example.
3. Hybrid ARQ (HARQ): Fig 7.1b shows the performance of HARQ. In T1, the sender encodes
K1 data packets with :1:1 parity bits and creates a codeword Cl(K 1,2:1). The receiver
fails to decode Cl and requests for a retransmission of Cl. In 7'2, the sender retransmits
01 Since the channel BER is relatively high (BER is 0.01), the receiver cannot decode
139
01 and requests for the second copy of 01 In 13, the receiver successfully decodes 01
Consequently, in T4, the sender transmits 02(K2, 9:2). The channel is errorfree in T4 and
so the receiver decodes 02 successfully. Data packets K1 and K 2 are delivered to the
higher layer. This creates the throughput of 0.25 S 1 — W S 0.5 since K3 and
K4 are not transmitted and furthermore, some of the channel bandwidth is consumed for
the delivery of parity bits 271 and 3:2. Notice that in practice, the number of parity bits is
signiﬁcantly less than the number of data bits in a codeword (i.e., 2:, << k).
. PACE: Fig.7.lc shows the PACE protocol performance. In 7'1, a codeword 01(K1,a:1)
is sent. A receiver that fails to decode Cl, stores CI in its buffer and requests for ad
ditional parity bits (hereafter typeII parity bits) for 01 In 7'2, the transmitter sends
M2 = [02(K2,:r:2), 31%]. The receiver uses 2:2 to decode C2 and employs typeII par
ity bits y% (y? denote additional parity for Cj, j < 2' transmitted in 72) in addition to 2:1
to decode CI The receiver fails to decode Cl and Cg. Since the codeword 02 cor
responds to the realtime data packet K 2, it has higher priority than 01. Therefore, the
receiver requests for typeII parity bits for C2 rather than C1. As a result, in T3, the
sender transmits M3 = [C3(k3, x3), yg]. In T3, the receiver successfully decodes 03 us
ing 2:3 and 02002, 2:2 + 31%). Consequently, the receiver requests for typeH parity bits
for C1. Accordingly, in T4, the sender transmits M4 = [C4(K4, 1:4), yi]. The receiver
decodes C4 using 114 and CI = (K 1,22 + 31% + yi) successfully. Therefore, the data
packets K1,   ,K 4 are delivered to the higher layer. The throughput under PACE is
4
Zr=1$i+yi+y§+yi <
4k _ 1.
0.75 S 1—
This example demonstrates the efﬁcacy of PACE in improving throughputdelay performance
in wireless linklayer communication. However, the description above has intentionally ignored
important details. For PACE to become practical we need to address the following challenges:
140
0 Optimal Parity Allocation: PACE uses channel codes for error recovery and hence it re
quires embedding parity bits in every packet. Since the transmission of parity bits con
sumes channel bandwidth, it is important to identify the optimal allocation of parity bits
in every transmission based on the channel condition and the channel code algorithm. A
practical design of parity allocation for PACE has to ensure (i) high likelihood of successful
decoding; and (ii) efﬁcient utilization of the channel bandwidth.
0 Dynamic Decoder Scheduling In every transmission, PACE should perform error recovery
on the packets with higher priority and hence buffer less signiﬁcant ones for future recovery.
To achieve compliance with such policy, it is natural to consider two complementary modes
of dynamic scheduling: (i) PACE should choose the order in which arriving packets are
served to guarantee the delivery of the packets to the higher layer before they expired; and
(ii) to reject or drop insigniﬁcant packets when the buffer length is judged to be excessive,
thereby incurring penalties or lost potential throughput.
In what follows, we show how to address these two challenges. To that end, in the next section,
we study the behavior of the linklayer trafﬁc under the PACE framework and formulate necessary
models which provide essential tools to develop a practical design of PACE.
7 .2 Model Formulation
In this section, we develop the following models for PACE: (i) LDPC decoding model which
captures the decoding process of linklayer trafﬁc using LDPC codes; (ii) Buffer model which
describes the linklayer buffer as a multiclass priority queuing system with a single server. These
models will build the framework to determine optimal code selection and dynamic decoder
scheduling strategies for the PACE protocol.
141
Check Side
Variable Side
Figure 7.2 A LDPC Tanner graph with dv = 2 and dc = 4.
7.2.1 LDPC Decoding Model
PACE employs LDPC codes for decoding linklayer packets. Our objective in this section is
to formulate the LDPC decoding process to select the code with best error correcting capability
to maximize bandwidth utilization. PACE uses the LDPC check matrix represented by Tanner
bipartite graph shown in Fig 7.2. The nodes of the graph are separated into two distinctive sets
which are called variable and check nodes with the degree of d1; and dc respectively. The PACE
protocol uses an iterative belief propagation LDPC decoder [69] which attempts to correct errors in
the received packet in m iterations. The following equation, by Gallager [68] shows the reduction
of errors as the function of the iteration number m:
—1
_ (ml) dc—l d'v
.(m) = 40> _ 40) [LL
2
(7.1)
(11) — 1
1_ 1__ 2(m—1)dc—1
+ (1 _ 6(0)) [# ,
l 2
where 6(0) represents the crossover probability of the Binary Symmetric Channel (BSC) that the
th iteration.
packet is transmitted over and 6(m) is the probability of error in the packet after the m
Using Equation (7.1), we can formulate a relationship between the number of iterations in belief
propagation method m, LDPC parity check matrix parameters dv and dc, and the amount of error
in the received packet. This relationship is communicated to us by Karande [70] and presented in
the following Lemma:
142
Lemma 1. For a packet transmitted over BS C with crossover probability 6% that is decoded using
LDPC check matrix with parameters do and dc; the distortion level after m iterations can be
approximated by
Proof. See Appendix. C]
In a transmission interval Ti, the PACE sender creates a codeword Ci(k,;,:1:z) by employing
LDPC generator matrix, thus encoding 1:, data bits with x, typeI parity bits. Correspondingly,
the receiver attempts to retrieve ki data bits by utilizing at, parity bits embedded in the received
packet Ci Speciﬁcally, the receiver utilizes a LDPC check matrix with 71, 2 hi +32, variable nodes
and 23,; check nodes. Since the degree of each variable and check node is dv and dc respectively,
the following equality holds:
Lemma 1 suggests that LDPC belief propagation performance depends on the knowledge of
channel condition 6, and the check matrix parameters d1) and dc. In addition, the receiver can cor
rect a certain level of error proportional to the number of parity bits embedded in the packet.
Therefore, the receiver is capable of correcting up to 046,) x :5, errors out of n, bits in the
packet. Here a(e) measures the expected errorcorrecting capability of the LDPC soft decision
decoder when the channel BER is e. The sender uses the channel 71, times to transmit a codeword
Ci(k,, 22,). Consequently, the amount of error introduced in the received codeword (on average)
is éini As a result the receiver fails to decode 0,(ki, 372') if the amount of error in the received
packet exceeds the error correcting capability of the receiver. That is,
Gin, 2 (1(6i).’1?i. (7.3)
Using Equations (7.2) and (7.3), we obtain an upper bound on a(ei):
0(5 < dc (7.4)
2') _ CiE'
143
Our main objective in this section is to select the code with best errorcorrecting capability.
Toward this end, we employ Lemma 1 and Equation (7.4) to obtain the maximum value of a(ei).
According to Lemma 1, LDPC decoder successfully decodes C, (ki: 23,) when the distortion level
of the received packet after m iterations approaches zero. In practice, the LDPC belief propagation
algorithm is conﬁgured such that the number of iterations m and the degree of variable nodes dv
are predeﬁned and constant [104]. However, the degree of check nodes do is determined by
the algorithm based on the number of available parity bits. Consequently, a successful decoding
depends directly on dc. On the other hand, Equation (7.4) suggests that errorcorrecting capability
of the decoder cannot exceed the upper bound au(e) = 625%. So, to maximize au(ei), we have
the following optimization problem:
arg ngiax an (62') subject to:
c
62' [Wu 1)(dc—1)]m‘1 = 0 and (7.5)
dv,m are constants.
Solving (7.5) leads us to the best possible value of dc and the maximum errorcorrecting ca
pability a* (67:). Consequently, we select a code from an ensemble of codes which has the error—
correcting capability close to a*(e,). in Section 7.3, we will use this code to obtain the optimal
parity allocation strategy for PACE.
7.2.2 PACE Buffer Model
Each arriving packet at the PACE receiver was generated to serve a speciﬁc protocol or application
in the higher layers. Depending on the type of the protocol or application, the packet is conﬁned
to a speciﬁc delay constraint. In addition, the packet contains a certain level of distortion due
to the impact of wireless linklayer transmission. Under the PACE framework, each packet is
classiﬁed into a speciﬁc priority class based on its delay constraint and distortion. The PACE
144
receiver then attempts to serve a speciﬁc priority class according to dynamic decoder scheduling
rules. In Section 7.3.2 we will provide a thorough description of packet prioritization process
and dynamic decoder scheduling policy. These procedures require a complete formulation of the
PACE buffer. Therefore, in this section, we develop a comprehensive queuing model for the PACE
buffer. To that end, we ﬁrst model the arrival process and the service distribution of each priority
class.
Arrival Process and Service Distribution
We consider the Markovian channel described in Chapter 3. The linklayer wireless channel is
modeled as a discrete Markov chain with N states 31,    , SN. Each state S, is a representation
of a BSC with a particular BER 62 which is valued from a ﬁnite set FN with length N: e, 6
FN, ”Ni 2 N. In [2], and speciﬁcally Equation (4), we measured the probability of successful
decoding of a packet C (ki, :ci) transmitted over the channel in state Si Using the LDPC decoding
model, we reforrnulate this probability measure as follows:
[01(6i)1‘z'l
_AE z
P(Ez _<_ a(ez) X 33,) = FEz,(a(€Z)a:i) = Z 6 2W. (7.6)
d=0 I
Here 13, represents the packet distortion level that has a Poisson distribution with cumulative
densrty function FEz' (u) and rate AEz"
The PACE receiver stores the arriving packets in its buffer when the decodings with typeI
parity bits are unsuccessful. Consequently, the anival process of packets with distortion level E,
in the PACE buffer can be modeled as a poisson process with the rate A, which is equivalent to
the probability of decoding failure with typeI parity bits:
Ai = 1 — FEi(a(ei):cz) = FEi(a(ez):L‘i). (7.7)
On the other hand, each arriving packet at the PACE is conﬁned to a speciﬁc delay constraint
which is independent of the packet error. Consider the situation where a packet with delay con
145
straints dj arrives according to a Poisson process with rate Aj. Notice that from the PACE buffer
vantage point, the arrival process of this packet is independent of the arrival process of a packet
with error Ei However, both of these processes are Poisson processes. Therefore, if a packet
with delay constraint dj and distortion level E, is classiﬁed into priority class I, then the arrival
process of this priority class is a poisson process with rate )‘l where
)‘l = A, + Aj. (7.8)
A packet departs the PACE buffer either if (i) it is successfully decoded with additional typeII
parity bits. In this case the data bits embedded in the packet are delivered to the higher layer; or (ii)
its delay constraint expires, meaning that the packet is timed out and is dropped from the buffer.
In the latter case the service distribution of the PACE decoder has zero density since the packet
is dropped. In the former case, the service distribution depends on the probability of successful
decoding of a packet with typeII parity bits. The probability of successful recovery of a particular
packet increases as more typeII parity bits are added to the packet. Consequently, the error
correction process of every packet under PACE has a nonhomogeneous geometric distribution [99]
with the density function fact) with the parameter pi = FEi (a(ei)zt):
t—l
f&(t) = P(Successful recovery on t trial) = p2 H (1 — p2). (7.9)
k=1
where pg measures the likelihood of successful decoding (when the channel is in state 52') on tth
decoding trial using total parity bits (typeI and typeII) of Zt Therefore, the service distribution
01 for a priority class I is fé;(t) which is a truncated fgh‘.) on dj:
fé(t)={ fé.(t) ifdjt>0 (7.10)
0 otherwise
The service rate of priority class l is the expected value of the density function féﬂt). That is,
i if dj — t > 0
uz=Elflg(t)]= Pi (7.11)
0 otherwise
146
According to Equation (7.8), the trafﬁc arriving in each priority class is a poisson process. On
the other hand, a decoding process of each priority class has a nonhomogeneous geometric distri
bution given in (7.10). Consequently, the PACE buffer can be modeled with a multiclass M / G / 1
priority queuing system with a single server. Here the arriving customers represent packets with
different priority classes and the PACE decoder is the server.
Consider the situation where the packets in the PACE buffer are classiﬁed into 1,    , L priority
classes, which arrive according to independent Poisson processes with respective rates ”1]le
and have service distributions [G l]1L=1 as calculated in Equations (7.8) and (7.10). Let Wl denote
priority delay, the average waiting time of a packet with priority class 1 in the PACE buffer before
it is successfully transmitted to the higher layer. Our objective is to compute the wt
Under M / G / 1 priority queuing system, Vi the average amount of decoding time for priority
class I is as follows [71]:
1
Vl = xlE[Gl]W, + E,\,E[GZ‘3]. z:1, ,L (7.12)
On the other hand, the priority delay of an arbitrary class 1 is equivalent to the amount of decoding
time in the system requires upon its arrival plus the decoding time that remains for other arrivals
classes that are already under the service. Therefore,
Wl=Vl+Vj' jaél,l,j=1,,L (7.13)
Using Equations (7.12),(7.13) and some mathematical manipulations, we can solve for individual
Wli
211121 AlE[Gz2]
= l J“ . . '
2Hj=l—1 [1’ z:Ic=1’\‘JE[GJ]]
In this section, we modeled the PACE buffer as a multiclass M / G.1 priority queuing system
Wl (7.14)
and we obtained the arrival and service rates, and the expected delay for each priority class in the
buffer. In Section 7.3.2, we will employ this model to ﬁnd an optimal dynamic decoder scheduling
policy for PACE.
147
Receiver Freedback
Buffer Flags
PACE Scheduler I
PACE Classrfier LDPC Decoder
l
Channel State Estimation ll
'____...._____<___
SideInformation J
Link Layer Packet
(b) PACE Receiver
Figure 7.3 The design architecture of the PACE protocol.
148
7 .3 PACE Protocol
In this section, we describe the design architecture of the PACE protocol and the functionality of
each of its components. Fi g 7.3 illustrates the architecture of PACE sender and receiver. PACE is
built on the ACE framework developed in [2]. Speciﬁcally, in Fig. 7.3, the darkcolored compo
nents in sender and receiver sides are those components that are either added or modiﬁed in the
PACE framework. In the following sections, we present a thorough description for these compo
nents.
7.3.1 PACE Sender
As illustrated in Fig. 7.3a, the PACE sender has two components. The ﬁrst component is Channel
State Prediction where the linklayer wireless channel condition for the next transmission interval
is predicted based on the receiver feedback. Speciﬁcally, the sender uses 8241’ the receiver chan
nel estimate for Ti—l as its prediction of the channel BER in current transmission interval r; so
6, = 8,_1.
The second component is Parity Allocation where a new codeword is generated and an appropri
ate number of typeII parity bits is added to a packet for the next transmission. We use the LDPC
model developed in Section 7.2.1 to select an appropriate code (based on the channel condition)
to ﬁnd an optimal parity allocation.
In [2], we proved that under the ACE framework, there exist only one optimal code embedding
rate under which the reliability and stability of linklayer trafﬁc is ensured. Recall that the oper
ational code embedding rate measures the fraction of data bits that are embedded in a codeword.
For instance a codeword C, (ki, 172') is generated based on the code rate R, = kz—ilx—Z. This ﬁnding
is repeated in the following Lemma:
Lemma 2. An optimal solution for code embedding rate that ensures reliability and stability in
149
wireless transmission over a channel in state S, is a unique solution and is given by:
52'
Ri:1—_' e,< I, where
g = g (hD(T,,d,),fg(—r,)) 2'6 RN x j 6 RM : z e RMXN (7.16)
where hD(., .) is the delay penalty function, and fall) is the errorcorrecting density function
given in Equation (7.9). The domains of packet distortion and delay constraint values are presented
by RN and RM respectively.
The delay penalty function hD(r,, dj) measures the cost of postponing the delivery of data bits
1 k, to the higher layer in transmission interval 7, based on packet delay constraint d 3" Speciﬁcally,
hD(., .) ranges from zero to one where the cost of dropping a packet is one (the packet is never
151
delivered). We use the following delay penalty function [101]:
hD(Ti’dj) =aexp [MTZ' _dj)]’ (7.17)
where a and b are normalizing coefﬁcients.
The PACE Classiﬁer ﬁrst computes the penalty weight for each packet stored in the PACE
buffer. Speciﬁcally, the penalty weight w) for a packet with distortion level E, and delay constraint
(1 j is
w, = hD(r,,dj) [1— f&(r,)]. (7.18)
Notice that w, approaches one if and only if the delay penalty function h D(., .) reaches one and
f5(.) is very small. This is an indication of a critical situation where the packet is reaching its
deadline and has to be decoded immediately and at the same time the likelihood of decoding
the packet with the current number of parity bits is very low. Therefore, the PACE Classiﬁer
classiﬁes a packet with the highest penalty weight to a higher priority class. That is the priority
classes 1,    , L are numbered so that
w12w22~ZwL.
PACE Scheduler
Accordingly to the PACE buffer model, the lth priority class has the arrival rate Al, service rate
)1), and the priority delay W), as obtained in Equations (7.8), (7.11) and (7.14). Consider a
deterministic ﬂuid analogy in which ﬂuid of class l arrives at a constant rate ’\l and can be drained
at rate M if the PACE receiver devotes all its capacity to class I. If the ﬂuid level of class 1 in the
buffer is N [(25) at time t, then the oldest ﬂuid of that class arrived 9%? time units earlier. Thus
the ﬂuid level of class I is not increasing if
N10)
_< —»N t < w. 7.19
,1 —W1 l()—’\l z ( >
152
Therefore, the backlog of class l in the system at time t is given by:
N10)
71 (t) = —' (7.20)
1 MW,
Consequently, for a workload process Q(t) deﬁned as
L
Q(t) = Z 111N105), (7.21)
121
the associated threshold level is
L
9 = 2 #lez (7.22)
[:1
The PACE Scheduler performs the dynamic decoder scheduling policy which has two parts:
(i) Sequencing rule: the PACE receiver at each decision point t (every transmission interval),
decodes the oldest packet from the class 1 having the largest backlog 77(t); and (ii) Rejection rule:
The PACE receiver drops a packet of class L (class L has the lowest priority signiﬁcance) from its
buffer if and only if Q(t) > q. Plambeck et al. in [100] proved that the above scheduling policy is
asymptotically optimal under the heavy trafﬁc condition.
In this section, we described the functionality of the Classiﬁer and Scheduler components added
in the PACE receiver. in the next section, we conduct extensive performance evaluations of PACE
to demonstrate the advantage of the new components added to ACE in comparison with the origi
nal ACE protocol and other leading linklayer protocols.
7 .4 Experiment
In this section, we present performance evaluations of the PACE protocol on real wireless chan
nel traces collected on an 802.11b WLAN [2]. Speciﬁcally, we use 41 channel traces, each with
unique average BER to simulate 41 various channel conditions. We compare the performance of
the PACE protocol as opposed to the ACE, HARQ, and IEEE802.11 ARQ protocols. In particular,
we ﬁrst show the impact of throughputdelay tradeoff on the performance of each protocol. Then,
153
we measure the performances of a realtime video and a nonrealtime TCP applications in con
junction with these linklayer protocols. For the following experiments, all four protocols PACE,
ACE, HARQ, IEEE802.11 ARQ are implemented with OMNET++ network simulator [105]. We
use an Adaptive LDPC (ALDPC) codes [104] for channel coding operations in PACE and ACE,
and ReedSolomon codes [67] for HARQ2.
7.4.1 ThroughputDelay Tradeoff
The throughputdelay tradeoff suggests that a higher throughput can be achieved with a higher
tolerable delay. Consequently, applications with time sensitive delays (realtime delay constraints)
suffer from low throughput. In this section, we measure the cost of this tradeoff on the linklayer
protocol performance. We deﬁne the throughputdelay cost C (t) as follows:
((t) = 1 — 6(t)<(t), (7.23)
where the 6(t) is the throughput cumulative density function (CDF), measuring the fraction of data
bits, and <(t) is the delay CDF, measuring the fraction of packets that are delivered successfully to
a higher layer by the time t. Notice that the throughputdelay cost function C (t) approaches zero
if and only if both 0(t) and ((t) approach one at time t.
Consider a packet arrives at time to and has not decoded by time t Z to, then its “delay” at
time t is by deﬁnition tn = t — to. In Fig. 7.4, we show the throughputdelay cost ((tn) for
each protocol with respect to the packet delay tn over six different wireless channel conditions.
Speciﬁcally, in Fig. 7.4a, where the channel average BER is very low (0.001), we observe that the
cost reduces dramatically for the packet delay greater than one. This is so since the likelihood of
packet error over this channel is very low. Consequently, most of the packets are received without
2 It is important to note that HARQ protocols use hard decision algorithms. ReedSolomon
codes are known to be Maximum Distance Separable (MDS) codes and therefore used in HARQ
protocols.
154
0—PACE  ACE nunHARQ . ARQ
..............................................................................
ThroughputDelay Cost
6 Q Q Q Q
Packet Delay
(3) BER: 0.001
o—PACE  ACE meARQ  ARQ
0.8
0.7
Delay Cost
“0.5
:3
e
330.4 «a
9 1 =7. :
‘J‘HHHIHIIIUIHIIIIHIIIHIHII11111irlI1111(11111Illiiilrrrrlinnu ' i
s." : : ; : : : : ":""”":
.........,.'..o.,..f...’j...‘H;.......f........j ........ ; ........ : ...... ..; .......
' 2 '. ' '.""".'"'9''"'=':.'. ."9  '   '
99
~AM
1!
l
i
!
r
0 1 2 3 4 5 6 7 8 9 1O 11
Packet Delay
(b) BER: 0.005
Figure 7.4 The variation in throughputdelay cost with respect to the packet delay over different
channel traces.
155
—IPACE   ACE1mmHARQ ARQ
0.9 . ..................................
0.8 .. L... .....................................
a :
8 07 i
O ' T
>§ ' I
a: .. .,: ...............
"as 0.6 ':
e .
,, 0.5 ,
a
‘ \
go 04 ..... ?‘..‘ ....................................................................
e ?II”;\'E . . . . . .
g 0.3+" *'”"Y'Wtagtgtu'nssgtz:initiate:21:11:".2'21Lijnnnig‘.‘.'.'.'.;.;;
. I ~:._ . , :\ : :
. . .  ~ .
. . . . . . .‘f .‘ .
0.2_ ....... , ..... ..... 3 ........ , ........ , ................ ....... : ..... ‘..:...!...,
: .   . : : : 'im §
0 1.. ............................................ .' ....... V. ....... v ....... r ........ ....w_'.
L J
O 1 2 3 4 5 6 7 8 9 10 11
Packet Delay
(C) BER: 0.007
0—PACE ACE 1uHHARQm ARQ
0.9 3
0.8
+3 i
U ' 5
>7 1
'3" 006 .7
Q. ;
4E; 05 \.... ............................................
a ‘
$00.4 37,934.. . .,; .....
O ’H,3.M. ; : . . .
la .l'l'hh l 111iIriuurirr'iilinlliuli1111‘11111111}, ? f '
g 0.31 1'+‘'=.!I.ud_ ..... ..... 3""‘f’u‘ﬂ'lfiﬁiﬁlna‘u'n11r
C5
.—
>—
p—
p
_
)—
i—
l—
u
—
h
Packet Delay
((1) BER: 0.009
Figure 7.4 continued.
errors and passed up to the higher layer immediately. However, as the channel BER increases,
the likelihood of receiving erromous packets increases. Accordingly, IEEE802.11 ARQ performs
156
—i—PACE   ACE meARQ  ARQ
1 ...... I ...... . ........ ............................................
2's, 2 Z ;
' S, i l .
. ....V. ..
0.8 I~a~. .
... ".~
: ’ '~a
9
V
t
35
i
31
El
11
'i
7i
'1
1i
_i
;i
ii
:i
I;
’qu 1.1.11
3_ .....  ......  ...............  ....... . ......... , ........... ......
U . . . . . . . . .

ThroughputDelay Cost
0 Q Q Q
0
0 1 2 3 4 5 6 7 8 9 10 11
Packet Delay
(e) BER: 0.018
0—PACE   ACE .....uHARQ . ARQ
.. . ...........................................................
g  . . . r .
' ... . t 
0.7
6" ' ' 'ﬁ'gllu'. ' . . . . . .
‘ "'“HllhllllllllilllllllflllllllPHllllll)lllllll
" ' T . f . '7’1
5L...... ‘~. ........ ; ........ r ........ : ........ :. ..... .’ o, ...........
~~~~ I,
ThroughputDelay Cost
9
ﬁt
1
0 1 2 3 4 5 6 7 8 9 10 11
Packet Delay
(f) BER: 0.020
Figure 7.4 continued.
retransmissions to deliver an errorfree packet. This in turn will result in the consumption of
channel bandwidth and longer packet delays. Consequently, we observe that the throughput
157
1161“"
us
........... ....599:5991t1r991etsﬂert........, 119190931. ““°° ..'
(()) ”... Receiver
Cha 6‘
Wired
Network
Access ‘59 altime Tra
Point ‘.~~. ’aﬁic
W1
ire/ass Chan" e I
TCP Application
Sender
Router
Realtime Video
Sender
Figure 7.5 Simulation setup where heterogeneous trafﬁc is generated by nonrealtime TCP and
realtime video ﬂows.
delay cost for IEEE802.11 ARQ does not reduce signiﬁcantly as the channel BER increases. For
instance, the cost of IEEE802.1 1 ARQ hovers around 0.7 over the channel with BER 0.018. On the
other hand, unlike HARQ, PACE and ACE employ adaptive parity allocation based on the channel
condition. Accordingly, we observe that the cost function of these protocols is always lower than
HARQ protocol regardless of channel condition. However, for the channel with low BER, where
the packet prioritization has no signiﬁcant impact, we observe that PACE performs better than
ACE. We observe this because PACE selects an optimal code to maximize channel bandwidth
utilization. In addition, for the channels with higher BER value, PACE still outperforms other
protocols since it employs packet prioritization. For instance, the PACE cost reduces below the
0.3 point for packet delays greater than two while ACE, HARQ, and IEEE802.11 ARQ have
respective costs of more than 0.4, 0.5 and 0.9. Overall, the PACE protocol gains 10% — 40%
reduction in throughputdelay cost.
7 .4.2 Realtime and NonRealtime Application Performance
In this section, we evaluate the performances of a realtime video and a nonrealtime TCP applica—
tions in conjunction with PACE, ACE, HARQ and IEEE802.11 ARQ protocols at the linklayer.
158
Fig. 7.5 illustrates the simulation setup of this section. Speciﬁcally, a TCP application sender is
sitting at the wired section of the network and transmitting the TCP packets to the wireless re
ceiver. At the same time, a realtime video sender is also transmitting video packets. The TCP and
video trafﬁc both are redirected to the receiver by the access point (AP). Using OMNET++ INET
framework, we implemented this simulation setup for each linklayer protocol. Speciﬁcally,
for the TCP application sender, we use the TCPGenericCliAppBase module to simulate a
generic TCP application at the sender and receiver. We evaluate the average throughput of TCP
packets. The average throughput measures the fraction of channel capacity that is utilized for
a transmission of TCP packets. Further, for the realtime video application, we use H . 2 64 /AVC
J M1 4 . O codec [106] to serve as video encoder/decoder. The realtime video sender encodes Stefan
CIF 30fps sequence and transmits it to the receiver at 300Kbps video rate. The decoder receives
the video packets and decodes them if and only if the video packets arrive before the realtime
deadline. Hence, those video packets that miss the deadline are unusable for video decoding. This
leads to degradation in video quality as measured by YPSNR. YPSNR is a function of the mean
square error (MSE) between the values of the original and decoded Y frame pixels:
(7.24)
2552 ]
YPSNR =1010 [
910 Hng _ YdeCllg
We repeat this simulation to evaluate the average throughput and PSNR values over 41 channel
traces. Therefore, a total of 164 simulations were conducted for this section.
Fig. 7.6a shows the average throughput of the TCP packets over various channel conditions. In
this ﬁgure the solid line is the channel capacity. The channel capacity gives an upper bound on
the average reliable information that can be transmitted over the channel. We observe that for a
very low channel BER, IEEE802.11 ARQ achieves a higher throughput than other protocols. This
is so since the channel is almost errorfree and IEEE802.11 ARQ uses the channel to transmit
only data bits. Consequently, its throughput is near channel capacity. On the other hand, PACE
and ACE protocols achieve higher throughput than HARQ due the efﬁcacy of adaptive parity
159
*PACE ACE “""'HARQ ""' ARQ —CAPACITY
‘5
Q.
J:
to
s I
8
.5
F , . .
‘D 3 E ’s, E
“>3 ' ‘ 's t
< 003’— ‘\" d
\'3
\
0.2.. 3 . ,, . .. .3”.
03,...
0 i 1 1 1 r
0 0.005 0.01 0.015 0.02 0.025
Average Bit Error Rate
(a) Throughput
*PACE ACE "W'HARQ ' ARQ —IDEAL
.T l
(I,
 .
. . a. ,.
m ‘ ' 0i i! .. .§ 1 ' 
z [I I.!,": 1111111,, ~~~ : ‘;~.: ﬁt
CD 3 I "1' ”\:$““‘l"l ‘s ' ﬁ‘ 7‘
CL. 25.... ..... '..':;I....o...3 ........ — ......... ’,’.I.:.,,.!.f‘?‘.................;.,..'.'"..~._ .......... _
' 5 '51" \ ‘ ""11 ‘ '~
>4 {'0 I . , ‘ In” ‘
' ' \ ' III'II
a) '0 ' ° ' ‘ t "m
50 "  ' ‘' ”u”!
a . I ‘ ‘ ’I'lil,
g) * ‘ 11”,”
< 20.. ............. .“ ........................................ 1
‘.
‘.
‘.
‘ . .
u _1.'  .u I..    0..
15._ , ............ .1
i i 1 i 4
0 0. 005 0.01 0.015 0.02 0. 025
Average Bit Error Rate
Figure 7.6 The performances of nonrealtime and realtime applications in terms of throughput and
video quality.
allocation. Meanwhile, as the channel BER increases slightly, the performance of IEEE802.11
ARQ decays signiﬁcantly. The ACE and HARQ protocols manage to perform relatively better
160
than IEEE802.11 ARQ protocol but still their performances are noticeably below the channel
capacity. The PACE protocol, however, achieves the average throughput within a maximum of 0.1
distance of the channel capacity. Overall, PACE achieves 20%  60% throughput improvement
over the IEEE802.11 ARQ and HARQ protocols. In addition, the PACE protocol increases the
performance of ACE by 10% regardless of channel condition. This performance gain clearly
illustrates the impact of code selection and the decoding scheduling policy of the PACE protocol.
Fig 7.6b suggests that the average YPSNR experiences a similar trend. For low BER values, the
PSNR value is high and close to the ideal video quality (here 33dB). However, the PSNR value
for IEEE802.11 ARQ and HARQ degrades for channels with BER more than 0.01. The PACE
protocol manages to achieve signiﬁcantly better video quality regardless of channel condition.
For instance, the PSNR value is around 31dB under PACE while ACE, HARQ, and IEEE802.11
ARQ achieve 28dB, 27dB, and 25dB over the channel with BER 0.007. Overall PACE achieves
2 — 10dB PSNR gain with respect to the IEEE802.11 ARQ and HARQ protocols. Further, it
improves the ACE performance by 1 — 3dB.
7 .5 Discussion
In this Chapter, we introduced Prioritized Automatic Code Embedding (PACE) protocol which
takes into consideration the stability, reliability, and delay constraints in wireless linklayer com
munication. We developed a LDPC decoding model to capture the decoding process of linklayer
trafﬁc and the PACE Buffer model to describe linklayer buffer as a multiclass priority queuing
system. Using these models, we determined the optimal code selection for parity allocation and
dynamic decoder scheduling for heterogeneous linklayer trafﬁc. We showed experimentally that
PACE signiﬁcantly outperforms IEEE802.11 and HARQ protocols and improves the performance
of ACE over various wireless channel conditions.
161
F1— .....
.
CHAPTER 8
Conclusions and Future Work
In this thesis, we aimed to tackle the critical issues associated with the inefﬁciencies of cur
rent wireless linklayer protocols and pursued a paradigm shift in the conventional 802.11 link
layer design. We developed a new linklayer framework to overcome the shortcomings of current
linklayer standards and to provide both the reliability and stability for pointtopoint contention
free wireless communication. Using this framework, we introduced four linklayer protocols:
1) PEEC, a linklayer protocol designed to ensure reliable wireless communication by reducing
the number of retransmissions which essentially leads to improving system throughput. PEEC
is layer oblivious and uses the packet formats of current IEEE802.11 standard; 2) DCPEEC, an
extension of the PEEC protocol that targets the ﬂow control of realtime video trafﬁc in addition
to reliability in wireless communication. DCPEEC adjusts its parameters to provide lowlatency
communication to satisfy the delay constraint (provided by the application) while utilizing the
channel bandwidth effectively; 3) ACE, the ﬁrst effort to develop a theoretical framework for an
alyzing and designing a wireless linklayer protocol that targets system stability in conjunction
with reliable communication. The ACE protocol uses a unique and optimal code embedding rate
to construct coded linklayer packets in every transmission to ensure stability, reliability and max
imum throughput; 4) PACE, the ACE based stableandreliable linklayer that employs a novel
162
rateadaptive Low Density Parity Check (LDPC) channel codes while interacting with the higher
layers to provide a dynamic decoder scheduling service over varying wireless channel condition.
PACE provides prioritized wireless linklayer communication that takes into consideration the
level of importance/impact of each packet to improve the overall performance.
Although the linklayer frameworks developed in this thesis provide a thorough groundwork
that address reliability and stability issues, it is designed for a single pointtopoint connection
(e.g., between an access point and a wireless device). Meanwhile, emerging multihop adhoc
and mesh wireless networks supporting heterogeneous highend applications require signiﬁcantly
further research into new linklayer and corresponding crosslayer frameworks that achieve an
overall (“global”) reliability and stability while maximizing effective throughput and bandwidth
utilization throughout the network. That is, it is necessary to ensure the information packets ﬂow
among relays nodes in a timely fashion (i.e, stability) while experiencing minimum distortions
(i.e., reliability) over wireless channels with varying error conditions. Consequently, it is neces
sary to develop an underlying network of reliable and stable wireless linklayer connections that
meet several critical objectives simultaneously and jointly: (1) achieving sustained stability: sup
porting legacy TCP applications and maintaining continuous realtime ﬂow among dynamic and
heterogeneous wireless devices, (2) ensuring maximal reliability and throughput, (3) interacting
with the higher layers for prioritized communication, optimal path selection and rateallocation,
and (4) exploiting sideinformation for channel estimation/prediction in a distributed manner. For
future work, we will build on our ﬁndings (realized in this thesis) and develop a Global Rate
Adaptive Code Embedding (GRACE) framework for a network of reliable and stable wireless
linklayer communication. Under the GRACE framework, we aim to identify different challenges
and research questions and our proposed solution to address these problems to achieve global
reliability and stability.
163
8.1 Link Layer Assignments
Latency in delivering information packets (due to wireless errors) over multipath wireless systems
such as adhoc and mesh networks is critical and has a direct impact on the overall performance
of realtime and highdemand applications (e. g., video conferencing, HDTV, etc.). The linklayer
frameworks developed in this thesis are designed to ensure 100% accuracy of each packet. That
is, the link—layer protocol follows a correctitsendit strategy where every relay node has to verify
that each packet is successfully decoded (thus passed to the next hop) or otherwise is dropped at
the linklayer (marked as a lost packet). Although this design strategy guarantees the validity of
information at any time throughout the path, it a) suffers from a signiﬁcant endtoend delay due
to the complexity of error correction process since every packet has to be decoded completely
before transmitted to the nexthop; and b) introduces unnecessary packet losses at the linklayer
since partially corrupted packets (which are likely to be expired) are dropped from the linklayer
buffer.
We will investigate and develop a new decoding strategy to tackle the critical issues associ
ated with the inefﬁciency of the correctitsendit approach and pursue a paradigm shift in the
conventional linklayer design. This approach attempts to reduce the latency while maintaining
maximum throughput by partially and optimally decoding each packet in different relay nodes.
The design of the proposed framework requires a networkofqueues model that captures the er
ror correction process and networking effects of trafﬁc ﬂows over multihop path. In particular,
we aim to ﬁnd an optimal (low complex) error correction scenario for a given path to ensure a)
effective utilization of channel bandwidth, b) rapid delivery of packets to the destination, and c)
improvement of the overall throughput; and d) minimum information loss. Toward that end, we
will develop solutions that address the following key questions:
Research question 1. At what intermediate nodes (if any) a linklayer packet should be examined
164
for being decodable or not?
Here, there are two extreme options. First, one can implement a hopbyhop link—layer, where
full rateadaptive channel decoding/encoding is employed; and hence reliability and stability can
be achieved throughout. This option may not be feasible under certain scenarios due to high
complexity and delay considerations (since it requires buffering/queuing in conjunction with it
erative feedback transmissions over every single hop). The other extreme option is to perform
channel decoding at the ﬁnal destination only. This option may lead to high levels of redundancy
since a packet needs to be protected over the whole route from the source to the destination by
a single set of channel codes. The optimum solution resides between the two extreme options,
depending on the network condition, the nature of the supported application and most impor
tantly the structure of the network. For instance, the optimal GRACE assignment for a network
with tree structure might not necessarily be optimal for a network with cliques. Therefore, to
ﬁnd the optimal GRACE assignment, ﬁrst we should model the connections of the network with
a graph structure. However, the network connections are wireless channels with varying error
conditions and also (in case of mobile adhoc network) it is possible that some nodes join or
leave the network. Consequently, random graphs will provide more accurate formulation of the
stochastic processes in the network than the traditional graph models. Hence, to solve the GRACE
assignment problem, we plan to ﬁrst model a given network with a random graph. Then, we will
formulate the assignment problem to ﬁnd an optimal solution for the GRACE assignment 52*. The
optimal solution for the GRACE assignment {2* requires a global knowledge of network structure
and channel conditions. However, this solution might not lead to a practical solution since the
availability of global information may be unachievable. Consequently, the ﬁnal phase of address
ing this research question includes distributed solution for GRACE assignment that the achieves
a performance close to p’“.
165
intmue 0
J
8.2 Code Assignment
Under the GRACE framework, a new packet is encoded using minimum (but necessary) number
of typeI parity symbols. Further, if the packet is decoded using typeI parity symbols and the
decoder cannot successfully retrieve the corrupted symbols in the packet, it will request for ad
ditional typeII parity symbols. The management of the transmission of typeI and typeII parity
symbols is trivial for pointtopoint communication scenario where the typeII parity symbols are
always concatenated to future data packets. We envision that this management will not be trivial
for multihop network.
Research question 2. How to partition the handling of different code types at diﬁerent nodes?
Under this research question, one can envision a scenario where a packet M0 that is carrying
type I and type 11 codes gets segmented at a particular intermediate node 711, where the typeII
code is extracted (from M0) because it is needed for decoding a previously transmitted packet
M1 awaiting in the buffer of that intermediate node n1. 1 In this case, the current packet M0 may
continue its journey toward the receiver without being decoded at node 711. Further, M0 may
carry a new typeII code to be delivered to another intermediate node n2 that is located on the
Mo’s route toward its destination. Here this new typeH code is needed for the recovery of a
corresponding packet M2 awaiting in the buffer of 17.2. This example illustrates the importance
of transportation plan for typeII parity symbols in the GRACE network. Suppose that we have a
collection of m packets propagating throughout the network and a collection of l buffered packets
in different locations of network waiting for the arrivals of typeII parity symbols. Further, let a
cost function g(yj, M,) be the cost of delivering typeII parity yj to a packet M,. We deﬁne a
transport plan T : Y —+ M an arrangement where each typeII parity block yj E Y is delivered
to its corresponding packet T(yj) E M. We wish to ﬁnd the optimal transport plan, the plan T*
166
such that its total cost function
9(T*)= Z 9(yj,T*(3/j)),
GM
is the least of all possible transport plans.
8.3 GRACE Interactions with higherlayers
The proposed linklayer framework primarily focuses on the enhancement of the linklayer pro
tocol and the improvement of wireless linklayer communication. Another aspect of the GRACE
framework for multihop ad—hoc/mesh wireless networks is the design and analysis of dynamic
feedback mechanism between the linklayer and the higher layers. Using this feedback mecha
nism, the higher layers (while interacting with linklayer) reconﬁgure and readapt in reaction to
heterogeneous trafﬁc ﬂuctuations and wireless channel noise disruptions. This approach will en
able higherlayers to intelligently adjust the operating parameters of their protocols based on the
knowledge of wireless channel conditions passed on to them by the linklayer. This in turn will
provide the source and relay wireless nodes the capability of reacting rapidly to random failures
and noise over wireless links and expedites the reliable delivery of information to the destination.
We will investigate the following research questions which consider the impact of the dynamic
feedback at the linklayer on the performance of each of the higher layers.
Research question 3. How is the GRACE linklayer protocol coupled with the contention control
protocol at the MAC layer?
The 802.11 family uses a Medium Access Control (MAC) mechanism [85] known as
CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance) [86] to provide contention con
trol. An important objective in contention control is to ensure fairness among the transmitting
nodes [87]. To enforce fairness, each sender is permitted to access the medium for a transmission
167
of a single packet. In the current IEEE802.11 standard, a wireless node that wants to transmit ﬁrst
listens on the desired channel. If the channel is idle (no active transmitters), then it will send a
packet. However, if the channel is busy (there is another active transmitter) the node waits un
til transmission stops in addition to a further contention window. At the end of the contention
window, if the sender senses the channel is still idle then it will transmit its packet, otherwise it re
peats the carrier sense process until it gets a free channel. The receiver will return an ACK packet
if it has successfully received the packet. However, if the receiver has received the packet with
errors then it will not respond (i.e. there is no negative ACK). The CSMA/CA transmit window
(the period that the sender is allowed to access the channel) allows for the ACK and therefore the
contention period starts after the ACK is received by the sender. Under the GRACE framework,
the receiver is forced to always send the ACK packet. This mechanism may bias the CSMA/CA
mechanism toward the node that already has the medium (since all other nodes should wait un
til the end of the ACK transmission including additional contention window) and consequently
jeopardizes the fairness. Further, the GRACE receiver is designed to store corrupted packets in its
buffer for future recovery. After few contention windows different senders have transmitted their
packets to the GRACE receiver. Now envision the situation where some these packets could not
be decoded using typeI parities and are waiting for typeH parity symbols. Therefore, it is very
likely that after few contention windows, the receiver buffer contains different packets belonging
to different senders (waiting for error recovery). In this situation, each packet in the receiver is
subject to wait for typeII parity symbols that should be transmitted by the corresponding sender.
On the other hand, the typeH parity symbols will not arrive at the receiver unless the MAC con
tention mechanism would give the medium to that sender. Consequently, the decoding process
at the GRACE receiver is inﬂuenced by additional delay (besides the decoding delay and the
buffer delay) which is governed by the contention control mechanism. This in turn will result in
reduction in throughput at the linklayer. This situation introduces a tradeoff between the con
168
tention fairness and decoding delay under the GRACE framework. Consequently, it is necessary
to design an optimal feedback mechanism between the GRACE linklayer and the CSMA/CA
contention mechanism to ensure maximum contention fairness with minimum decoding delay at
the linklayer.
Research question 4. Can GRACE improve the performance of adhoc routing protocols?
The main objective of the network layer for mobile adhoc/mesh network is to route the wireless
packets between different senders and receivers. One of the challenging types of routing protocols
is an adhoc routing protocol [80]. In adhoc networks, nodes do not have a prior knowledge of
topology of network around them. Consequently, a new node (optionally) announces its pres
ence and listens to broadcast announcements from its neighbors. The node learns about new near
nodes and ways to reach them, and may announce that it can also reach those nodes. Exten
sive research has been conducted to ﬁnd an efﬁcient adhoc routing protocol and various routing
protocols have been proposed [76] [79]. Among these protocols, Adhoc Ondemand Distance
Vector (AODV) [81] has clear advantages in its moderate overheads and its route convergence
performance and became one of the promising protocols, currently available, for the mobile ad
hoc network. Under the AODV protocol nodes discover routes in requestresponse cycles. At
each node, AODV maintains a routing table where each entry for a destination contains three es
sential ﬁelds: a next hop node, a sequencenumber and a hopcount. All packets destined to the
destination are sent to the next hop node. The sequence number acts as a form of timestamping,
and is a measure of the freshness of a route. The hop count represents the current distance to the
destination node.
The AODV sender performs path selection when there are multiple routes available to the re
ceiver. In this situation, the receiver selects a path associated with the minimum hopcount. That
is, the sender chooses a route with a minimum distance to the destination. However, a path with a
169
Q
O s
f O”~~ 0' ‘Q
1 . . . .
0 \ O Q‘
0' “ " ‘s
O' “Q 0" 8 “~
'0 8 8 \~ '0 86/ / \ \8 Q‘
/ U
Figure 8.1 An example of multihop wireless network.
minimum distance is not always an optimal path. For instance consider a situation for the network
depicted in Fig 8.1 where there are two path P1 : (711,712, 714,725, n7) and P2 : (711,713,716, 717)
from the sender n1 to the receiver 717. For these paths, 6P1 : (61, e3, e6, 68) and 6P2 : (1:2, 65, 69)
represent respectively the channel conditions of the routes P1 and P2. The standard AODV path
selection policy enforces the sender to choose P2 to communicate with the receiver since P2 is
shorter than P1. However, assuming that the average wireless errors of P1 is signiﬁcantly lower
than P2: E P1 << €132, it is reasonable to select P1.
The information about the channel conditions for different paths can result in a better path se
lection policy which in turn will reduce the “loss connectivity” in AODV and consequently RERR
messages. To provide such information to the routing layer, we aim to establish a dynamic feed
back between the GRACE linklayer to the routing layer where the channel condition is reported
to the routing layer. In particular, we add a new ﬁeld called parityusage to each entry of the
AODV routing table. The parityusage ﬁeld is updated by GRACE after every linklayer trans
mission. More speciﬁcally, the GRACE informs the routing layer the number of parity bits it
employed for its coding operations. The parityusage represents an average number of parity bits
used in last W transmissions. The AODV sender will then employ a cost function that takes into
consideration both hopcount and parityusage and will select a path with a lower cost.
170
8.4 Broader Impact
The impact of the linklayer frameworks developed in this thesis is envisioned to be signiﬁcantly
effective in the following areas:
0 Sensor Networks and Power Constrained Systems: In addition to enabling a major shift
toward reliable and stable linklayer communications, the proposed effort will naturally
have signiﬁcant impact on related areas in wireless networking. For example, it is well
known that sensor networks cannot afford retransmission mechanisms due to severe power
constraints. Hence, we anticipate that the proposed effort could have a profound positive
impact on powerconstrained networks, in general, and sensor networks in particular.
0 High Demand Wireless Video Communication: The proposed approach will have a pro
found impact on enabling new levels of improved performance for highend applications
such as HDTV over wireless networks. What is ultimately needed for wireless HD video
is a comprehensive crosslayer framework that targets stableandreliable communications,
exploitation of side information, and interaction with the video layer jointly. In particular,
no effort has been pursued (to the best of our knowledge) of such comprehensive frame
work over multihop adhoc or mesh wireless networks. Consequently, a natural extension
of the proposed linklayer framework (presented in this thesis) is the development of a cross
layer based stableandreliable linklayer that interacts with the lower physical layer and the
higher video layer. We also envision realizing the proposed new linklayer approach with
a highend application over a small testbed with all supplementary softwares which can be
made available to the larger research community.
0 Neurotechnology Communication Systems: Braincomputer interfacing aims to provide
new means of communication by directly assessing and interpreting brain intentional states.
However, bypassing the brains biological outputs using an engineered interface comes at
171
the high price of beyond stateof—theart technology. This technology should overcome im
portant communication challenges such as a) bandwidth limitations: due to sensitivity of
brain tissues, b) power limitations: due to the minute nature of the implant chips; and c)
signiﬁcant communication error: since it is difﬁcult to align the sender (implant chip) and
the receiver (the antenna secured in the skull). The proposed framework aim to reduce
the communication errors and effectively utilize an available bandwidth while minimiz
ing retransmissions (reducing transmission power consumptions). It is our belief that the
proposed communication mechanism under the GRACE framework is wellsuited for such
environments and will provide a breakthrough in Neurotechnology communication.
172
APPENDIX A
Proof of Lemmas for PEEC
Lemma 1. In a transmission interval 7', with error probability 13,, the V likelihood of successful
decoding of a message .M, with typeI parity probability distribution p Xi can be achieved if
1 I—r
sz, Z a; (716, + ,/n€,qo (u)) ,
where (1710/) is the Vquantile of the standard normal distribution.
Proof. According to Equation (4.3), the u likelihood of successful decoding is
P{D, _<_ ax,} = V.
Since D, has Poisson distribution with mean AD” then
2
ax _AD'
P{D,§a2:,}=¢ —Z_i 2V)
AD,
Thus
023, 2 AD, l ADi¢_1(1/).
According to the message model, 2:, = max, and AD, = 715,; so u likelihood of successful
decoding can be achieved if
1 _
PX 2 E (796, + die—2'05 1M)
173
Lemma 2. In r,_1, ifa decoder with errorcorrecting capability at decodes a message with typeI
parity symbol rate p , = g 6_ successfully, then for 7', 6  has the upper bound
X ,_1 z 1 z z
6'
9139—1 (——zal)
Proof. In r_1, because the decoding of a message was successful, according to lemma 1, we
have
1
pX,_, =g.
(I
where V is close to one (i.e., V = 0.99). By assuming very slow fading, such that the channel does
not change signiﬁcantly between consecutive transmissions; because of successful decoding, we
assess that the actual BER for r, is at most 6,_1, that is
6,36,_1=> 9(5i) S 9(éi—1),
given that 9(6) > 6,6 > 0. Accordingly, for the estimation of 6, (i.e, 6,), g(6,~) is bounded
by g(6,_1). Consequently, the maximum 6, is the one that introduces g(6,) which satisﬁes the
equality. Thus
. _1 1 . . —1
maxe, = g (E(n6,_1+ n6,_1¢ (VD) .
In practice, since V is close to one, then (1)—1(V) z 8 and n is a large number. Therefore, we can
approximate the upper bound of 6, by calculating the above expression when n is inﬁnity. That is,
.. 0 —1
6_ 6'_ V
6,< lim 9”1 —za1l\/—————z 1‘15 ()
_n—rOO n
a
,2, 39—1 ( z 1).
a
Thus
El
Lemma 3. In T,_1, if a decoder with errorcorrecting capability a fails to decode a message
with typeI parity symbol rate p . = g 6_ , then the estimation of BER for 7" has a lower
X ,_1 z 1 z
174
bound
6}“ 2 0902—1)
Proof. According to the distortion model, the decoding failure in r,_1, suggests that the distortion
of the message was higher than its typeI redundancy. That is,
D,_1 > 01:17,_1.
Furthermore, the failure in decoding indicates that the actual BER 6, is greater than 6,__1. This
assumption is true under very slow fading. Accordingly, the distortion created by 6, in 7', should
satisfy,
PT{D, > OtIL‘,’_1} > V,
where V is close to one (i.e., V = .99) and D, is a Poisson random variable with rate )‘D, = 716,.
Thus
Pr{D, S ax,_1} S 1— V
axi—l _ )‘D,
AD,
/\
11
I
Q
<15
To ﬁnd a lower bound for 6,, we solve the equality. That is,
ax,_1—/\Di = ADi¢“1(1—V).
By rearranging this expression, we obtain a second order equation with respect to )1 D
2
)3), — ADi(2a$i_1+ $171) + 02332 1: 0.
Z—
The solution of this equation leads to
1 _ _ _
AD, : 5(2023,_1+ (bl/1i \/(¢V1)2 + 4072:,_1qb,/1.
Since ”\D, = 716, and 2:,__1 = ani—l = ng(6,_1), then the minimum 6”, is
—1 —1 2 ~. 1
A. _ .. d’V (¢V ) ag(€z—1>¢V
6, — ag(6,_11) + 2n. — 47,2 + n
175
In practice 72. is a large number and since V is close to one, of m 8. Consequently, we can ﬁnd
the lower bound for 6, by computing the limiting convergence of the above expression when n is
inﬁnity. That is
;1_\/< .71)? + age—19.71
6.> lim ag(6,_1)+ 2n 4”, n
2 “ 71—900
Thus
91' Z 09(91—1).
“i
176
APPENDIX B
Proof of Lemmas for ACE
Lemma 1. The operational code embedding rate that ensures reliability in wireless transmission
over a channel in state S, is bounded above by
5i
R,‘Sl——. 6,< 0
Since the primal problem is convex, the KarushKuhnTucker (KKT) conditions are sufﬁcient
for the points to be primal and dual optimal (zero duality gap). KKT conditions suggest that based
on complimentary slackness property for strong duality, we have
/\1 (hi"910L 91(0):  9)) = 0, (13.2)
(\2 ("2'  193‘ + 93;") = 0. (3.3)
where k: and 2:: are the optimal transmitted amount of data and parity symbols. On the other
hand, with the channel is in state 5,, and maximum network utilization of 77., symbols, the amount
177
of transmitted data symbols is bounded above by k, = [0, IR, 5 k: , where R, is a channel coding
rate. So, by substituting k; = 72,1222 2:;“ = n,(1 — R?) and solve the above equations for Rg‘, we
haveR,SR;‘=1—%. Cl
178
Lemma 2. The operational code embedding rate that ensures stability in wireless transmission
over a channel in state S, has a lower bound
52'
R,Zl——. 6,< T,’(Z) — _1 (C.1)
1 — 2
Now, the inverse Ztransform u[.] gives us the follows:
.217”) = 5E0)§—1u[m] = .9 [69m — 1)(dc — 1)]m— . ((12)
This completes the proof. U
181
APPENDIX D
Steady State Balance Equations
The following equations are the list of balance equation for the proposed queueing system under
PEEC protocol. In the following equations 1 S m 3 Bl — 1, 1 S n S 82 —1 and 1 g l g 83— 1.
A7r0,0,0 = (Ill2710,10 + #300,02
(A + #1l7rm,0,0 = (Vim—1,0,0 + (III2707120 + #3707101
#1031,0,0 = ”Bl—1,0,0 + (1112713120 + #393101
0 + #2llr0,n,0 = “l”1,n—1,0 + qu2710,n+1,0 + #300,722
(A + #2)7T0,BQ,0 : “1W1,Bg—1,0 + #37r0,32,1‘
(A + #3)7T0,0,1 = P92730224 + 4920022 + #37001“.
(A + #3)"0,O,B3 = W27r0,1,33—1 + (192002.33
(D.1)
(D.2)
(D.3)
(D4)
(D5)
(D6)
(D7)
(A + #1 '1' H2l7rm,n,0 = ”rm—1,7740 + #1”m+1,n—1,0 + W‘27rm,n+1,0 + u3”m,n,1° (D.8)
(A +,#2)Wm,32,0 = Am—l,Bg,0 + “17rm+1,B21,0 + 11371771322
(D.9)
(A + [”1 + l1'3l7r77't,0,l = A77m—1,0,l + q“2”m,l,l + pu27rm,1,l—1 + ”3”nt,0,l+1' (D.10)
(A + #1 + #3)7rm,0,B3 = A7Tm—1,0,B3 + CI/Wm,1,B3 + Pu27rni,1,B3—1~
182
(D.ll)
(#1 + #2l7rBl,n,0 = “Bl—1,710 + 90271312410 + #37131,n,19
#2031320 = (”Bl1,320 + 937131322
(91 + #:0713102 = )‘WBI 1,0,1 + 492713122 + 14927131224 + #3713102“
(Mr + M3>7TB1 ,O,B3 = ”Bl—1,0,B3 + P#2931,1,B3—1 + 91027131233
(A + #2 + ((3)7074 = “lﬂlm—IJ + PWO,n+1,1—1 + ”3W0,n,l+1'
(A + (1112 + #3l7ro,n,B3 = #191,71—1233 + 9#27ro,n+1,B3 + P#27ro,n+1,B3—1
(A + #2 + #3130322 = #101,32—1,1+ #330,322“
(A + W2 + #3)00,32,B3 = #101,32—1233
(D. 12)
(D.l3)
(D. 14)
(D.15)
(D. 16)
(D.l7)
(D.18)
(D.l9)
(#1 + #2 + #3l7131 ,n,l = A“”131 —1,n,l + W27r31,n+1,zP#27r31,n+1,i—1 + #3"31,n,1+1
(01+q#2+#3)031,n,33 = A7131—1,n,B3+q#27131,n+1,B3+Ptt27131,n+1,B3—1
(A + #2 + H3>Wm,32,1 = AWm—1,B2,l + Hrtm+1,Bg—1,t+ #3Wm,32,1+1
(A + W2 + #3)7Tm,32,B3 = Aim—1,132,133 + l‘l“m+1,Bg—1,B3°
(#2 + #3)”31,32,1 = A7Tel—1,1322 + #3WBI,32,1+1
(A + “I + (”‘2 + ”Bllrm,n,B3 = )‘ﬂm—l,n,B3 + ”1”m+1,n—1,B3
+ qﬂ27rm,n+1,B3 + pﬂ2ﬁm,n+1,B3—1'
(1‘12 + #3l7rBl,Bz,B3 : AWBl—1,BQ,B3'
(A + #1 + #2 + #3)7rm,n,l = Min—1,71,: + #1”m+1.n—1,l
+ qﬂzﬂm,n+1,1 + pl‘27rm,n+1,l—1 + #37rm,n,l+1 ,
(D20)
(D21)
(D22)
(D23)
(D24)
(D25)
(D26)
(D27)
The following equations are the list of balance equations for the proposed queueing system
under IEEE802.11 ARQ scheme. In these equations 1 S m 3 Bl — 1 and 1 S n S 82 — 1.
A"0,0 = #200,1
183
(D.28)
(A + ”llﬂmﬁ : Mrm—1,0 + “277ml:
#10310 = Mel—1,0 + #20312
(/\ + #2)”0,n = #101,71—1 + #2”0,n+1
(A + #2)”0,82 = #101,32—1
(#1 + #2)7rBl,n = “Bl—1,72 + #27rBl,n+1~
#2931,32 = Mel—1,32
(A + #2l7rm,B2 = Min—1,32 + Hrﬂm+1,Bg—1
(A + 191+ #2)Wm,n = Arm—1,7) + Hrtm+1,n—1 + H27Tm,n+1
184
(D.29)
(D.30)
(D.31)
(D.32)
(D.33)
(D34)
(D35)
(D36)
BIBLIOGRAPHY
[1] Clark, George C., Jr., and J. Bibb Cain. “ErrorCorrection Coding for Digital Communica
tions.” New York, Plenum Press, 1981. ISBN 0306406152.
[2] S. Soltani, K. Misra, and H. Radha, “On LinkLayer Reliability and Stability for Wireless
Communication,” ACM MOBICOM, 2008.
[3] S. Soltani, H. Radha, “PEEC: A ChannelAdaptive FeedbackBased Error Control Protocol
for Wireless MAC Layer,” IEEE JSAC Special Issue on Exploiting Limited Feedback in
Tomorrows Wireless Communication Networks, 2008.
[4] Syed A. Khayam and Hayder Radha, “ConstantComplexity Models for Wireless Channels,”
IEEE INFOCOM, April 2006. [50]
[5] S. S. Karande and H. Radha, “Hybrid ErasureError Protocols for Wireless Video,” IEEE
Transactions on Multimedia, vol. 9, no. 2, Feb 2007.
[6] S. Karande, S. A. Khayam, Y. Cho, K. Misra, H. Radha, J. Kim and J. Hong, “On Chan
nel State Inference and Prediction Using Observable Variables in 802.11b Networks,” IEEE
International Conference on Communications (ICC), Glasgow, UK, June 2007.
[7] Syed Ali Khayam, Shirish Karande, Muhammad Usman Ilyas, and Hayder Radha, “Header
Detection to Improve Multimedia Quality over Wireless Networks,” to appear in IEEE Trans
actions on Multimedia.
[8] Syed Ali Khayam, Hayder Radha, Selin Aviyente, and John R. Deller, Jr., “Markov and
Multifractal Wavelet Models for Wireless MACtoMAC Channels,” Elsevier Performance
Evaluation Journal.
[9] Shirish Karande, Utpal Parrikar, Kiran Misra, and Hayder Radha, “Utilizing Signal to Si
lence Ratio indications for improved Video Communication in presence of 802.11b Residue
Errors ”, IEEE International Conference on Multimedia & Expo (ICME), July 2006.
[10] Shirish Karande, U. Parrikar, Kiran Misra, and Hayder Radha, “On Modeling of 802.11b
Residue Errors,” Conference on Information Sciences & Systems (CISS), March 2006.
[11] Syed Ali Khayam, Shirish Karande, Muhammad Usman Ilyas, and Hayder Radha, “Improv
ing Wireless Multimedia Quality using Header Detection with Priors,” IEEE International
Conference on Communications (ICC), June 2006.
185
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
Syed Ali Khayam and Hayder Radha, “LinearComplexity Models for Wireless MACto
MAC Channels,” ACM/Kluwer Wireless Networks (WINET) Journal  Special Issue on Se
lected Papers from MSWiM’O3, vol. 11, no. 5, pp. 543555, September 2005.
Syed Ali Khayam, Selin Aviyente, and Hayder Radha, “On LongRange Dependence in
HighBitrate Wireless Residual Channels,” Conference on Information Sciences and Sys
tems (CISS), March 2005.
Shirish Karande and Hayder Radha, “The Utility of Hybrid Error Erasure LDPC (HEEL)
Codes for Wireless Multimedia,” IEEE International Conference on Communications (ICC),
May 2005.
Syed Ali Khayam, Muhammad U. Ilyas, Klaus Prsch, Shirish Karande, and Hayder Radha,
“A Statistical Receiverbased Approach for Improved Throughput of Multimedia Commu
nications over Wireless LANs,” IEEE International Conference on Communications (ICC),
May 2005.
Shirish Karande and Hayder Radha, “Does Relay of Corrupted Packets Lead to Capacity Im
provement?,” IEEE Wireless Communications and Networking Conference (WCNC), March
2005.
Shirish Karande and Hayder Radha, “RateConstrained Adaptive FEC for Video over Era
sure Channels with Memory,” IEEE International Conference on Image Processing (ICIP),
October 2004.
Syed Ali Khayam and Hayder Radha, “Markovbased Modeling of Wireless Local Area
Networks,” ACM Mobicom International Workshop on Modeling, Analysis and Simulation
of Wireless and Mobile Systems (MSWiM), September 2003.
Syed Ali Khayam, Shirish Karande, Hayder Radha, and Dmitri Loguinov, “Analysis and
Modeling of Errors and Losses over 802.1 lb LANs for HighBitrate RealTime Multimedia,”
EURASIP Signal Processing: Image Communication, vol.18, no.7, pp. 575595, August
2003.
Syed Ali Khayam, Shirish S. Karande, Michael Krappel, and Hayder Radha, ”CrossLayer
Protocol Design for RealTime Multimedia Applications over 802.11b Networks,” IEEE In
ternational Conference on Multimedia and Expo (ICME), July 2003.
Shirish Karande, Syed Ali Khayam, Michael Krappel, and Hayder Radha, “Analysis and
Modeling of Errors at the 802.11b LinkLayer,” IEEE International Conference on Multime
dia and Expo (ICME), July 2003.
Syed Irtiza Ali and Hayder Radha, “Hierarchical Handoff Schemes over Mreless
LAN/WAN Networks for Multimedia Applications,” IEEE International Conference on Mul
timedia and Expo (ICME), July 2003.
Kiran Misra, Shirish Karande, Hayder Radha, “Maximal Recovery Network Coding under
Topology Constraint,” Proceedings of the 27th IEEE International Conference on Computer
Communications (INFOCOM’08), Phoenix, AZ, United States, April, 2008.
186
[24] Kiran Misra, Shirish Karande, Keyur Desai, Hayder Radha, “Complexity Reduction Using
PowerLaw Based Scheduling For Exploiting Spatial Correlation In Distributed Video Cod
ing,” Proceedings of IEEE Conference on Image Processing (ICIP08), San Diego, USA,
2008.
[25] Muhammad U. Ilyas, and Hayder Radha, “Measurement Based Analysis and Modeling of
the Error Process in IEEE 802. 15.4 LR—WPANs,” Proceedings of the 27th IEEE International
Conference on Computer Communications (INFOCOM’OS), Phoenix, AZ, United States,
April, 2008
[26] Shirish Karande, Kiran Misra, Sohraab Soltani, Hayder Radha, ”Design and Analysis of
Generalized LTcodes using Colored Ripples,” Proceedings of International Symposium on
Information Theory (ISIT08), Toronto, Canada, 2008.
[27] Sohraab Soltani and Hayder Radha, ”Performance Evaluation of Error Control Protocols
over FiniteState Markovian Channels”, Proceedings of the Conference of Information Sci
ences and Systems (CISSO8), Princeton University, NJ, USA, March 2008
[28] D. Aguayo, J. Bicket, S. Biswas, G. Judd, and R. Morris. “Linklevel Measurements from
an 802.11b Mesh Network”. In SIGCOMM, 2004.
[29] IEEE Computer Society LAN MAN Standard Committee, “Wireless LAN Medium Access
Control (MAC) and Physical Layer (PHY) Specifcations,” IEEE Std. 802.111999, New
York, 1999.
[30] ISO/IEC 880211:1999(E), “Part 11: Wireless LAN Medium Access Control (MAC) and
Physical Layer (PHY) Speciﬁcations,” August 1999.
[31] IEEE Std 802.11b1999, “Part 11: Wireless LAN Medium Access Control (MAC) and Phys
ical Layer (PHY) Speciﬁcations: HigherSpeed Physical Layer Extension in the 2.4 GHz
band,” September 1999.
[32] J. G. Kim and M. M. Krunz, “Delay analysis of selective repeat ARQ for a Markovian source
over a wireless channel,” IEEE Trans. Veh. Technol, vol. 49, no. 5, pp. 19681981, Sep. 2000
[33] P. S. Sindhu, “Retransmission error control with memory”, IEEE Transactions on Commu
nications, vol. COM25, no. 5, pp. 473.479, May 1977.
[34] S. S. Chakraborty, E. YliJuuti, and M. Liinaharja, “An adaptive ARQ scheme with packet
combining,” IEEE Communications Letters, vol. 2, no. 7, pp. 200.202, July 1998.
[35] M. Gidlund, “Receiverbased packet combining in IEEE 802.11a wireless LAN,” in Proc.
IEEE Radio and Wireless Conference (RAWCON), August 2003, pp. 47.50.
[36] Y. Liang and S. S. Chakraborty, “ARQ and packet combining with postreception selection
diversity,” in Proc. 60th IEEE Semiannual Vehicular Technology Conference (VTC Fall),
2004.
[37] Q. Zhang and S. A. Kassam, “Hybrid ARQ with selective combining for fading channels,”
IEEE Journal on Selected Areas in Communications, vol. 17, no. 5, pp. 867.874, May 1999.
187
V1
[38] T. W. A. Avudainayagam, J.M. Shea and L. Xin. Reliability Exchange Schemes for Iterative
Packet Combining in Distributed Arrays. Proc. of the IEEE WCNC, volume 2, pages 832
837, 2003.
[39] S. S. Chakraborty, E. YliJuuti, and M. Liinaharja. An ARQ Scheme with Packet Combining.
IEEE Comm. Letters, 1998.
[40] H. Yomo, S. S. Chakraborty, and R. Prasad, “IEEE 802.11 WLAN with Packet Combin
ing”, International Conference on Computer and Device 2004 (CODECO4), January, 2004,
Kolkata, India
[41] Grace Woo, Pouya Kheradpour, Dawei Shen, and Dina Katabi, “Beyond the Bits: Coopera
tive Packet Recovery Using Physical Layer Information,” ACM MOBICOM, 2007.
[42] K. C. Lin, N. Kushman, and D. Katabi. Ziptx: Harnessing partial packets in 802.11 networks.
In Mobicom08, September 2008.
[43] E. Soljanin. Hybrid ARQ in Wireless Networks. DIMACS Workshop on Network Inform.
Theory, March 2003.
[44] E. C. Strinati, S. Simoens, and J. Boutros, “Performance evaluation of some Hybrid ARQ
schemes in IEEE 802.11a Networks“, IEEE VTC, 4(4):2735 2739, 2003
[45] G. Caire and D. “Tuninetti. The throughput of HybirdARQ protocols for the Gaussion col
lision channel”. IEEE Trans. Inform. Theory, July 2001.
[46] S. Cheng and M. C. Valenti. “Macrodiversity packet combining for the ieee 802.11a uplink”.
In IEEE WCNC, 2005.
[47] M. C. Valenti. “Improving uplink performance by macrodiversity combining packets from
adjacent access points”. IEEE WCNC, pages 636 641, 2003.
[48] S. Lin and D. J. Costello Jr., “Error Control Coding: Fundamentals and Applications,” En
glewood Cliffs, NJ: PrenticeHall, 1983.
[49] S. Lin and P. S. Yu, “A hybrid ARQ scheme with parity retransmission for error control of
satellite channels,” IEEE Trans. Commun., vol. 30, pp. 17011719, July 1982.
[50] Y. Wang and S Lin, “A modiﬁed selectiverepeat typeH hybrid ARQ system and its perfor
mance analyses,” IEEE Transactions on Communications 31(5), pp. 124133, 1983.
[51] G. Caire and D. Tuninetti, ”The throughput of HybirdARQ protocols for the Gaussion col
lision channel”, IEEE Trans. Inform. Theory, 47: 1971 1988, July 2001.
[52] D. Chase, “Codecombining: A maximum likelihood decoding approach for combining
an arbitrary number of noisy packets,” IEEE Trans. Commun., vol. COMM33, no. 5, pp.
385393, May 1985.
[53] J. C. Bolot, S. FosseParisis, and D. Towsley, “Adaptive FECbased error control for internet
telephony,” in Proc. IEEE INFOCOM 99, 1999, vol. 3, pp. 14531460.
188
[54] K. Jarrrieson and H. Balakrishnan. “PPR: Partial Packet Recovery for Wireless Networks”.
In ACM SIGCOMM, Kyoto, Japan, August 2007.
[55] TM. Cover, and J. A. Thomas. Elements of Information Theory. Wiley, 1991.
[56] J. Ha, J. Kim, and S.W. McLaughlin. Ratecompatible puncturing of lowdensity parity
check codes. IEEE Trans. Inform. Theory, 50:28242836, November 2004.
[57] Boris Bellalta I Jimenez and Alexandre Graell i Amat. Performance Analysis of a Type 2
Hybrid ARQ Protocol Based on RCPC Codes for 150  the IEEE802.11a Random Access
MAC Protocol. IEEE Trans. Comm, May 2005.
[58] J. Li and K. Narayanan, ”Ratecompatible lowdensity paritycheck codes for capacity
approaching ARQ scheme in packet data communications”, Int. Conf. on Comm, Internet,
and Info. Tech. (CIIT), Nov. 2002.
[59] J. Ha, J. Kim, and S.W. McLaughlin, ”Ratecompatible puncturing of lowdensity parity
check codes”, IEEE Trans. Inform. Theory, 50228242836, November 2004.
[60] D.N. Rowitch and LB. Milstein, ”On the performance of hybrid FEC/ARQ systems using
rate compatible punctured turbo (RCPT) codes”, IEEE Trans. Commun., 48:948959, June
2000.
[61] MR. Yazdani and AH. Banihashemi, ”On construction of ratecompatible lowdensity
paritycheck codes”, IEEE Commun. Lett., 8:159161, March 2004.
[62] J. Hagenauer, “Ratecompatible punctured convolutional codes and their applications,” IEEE
Trans. Commun., vol.36, no. 4, Apr. 1988.
[63] A. Banerjee, D. Costello, and T. Fuja, “Diversity combining techniques for bandwidth
efﬁcient turbo ARQ systems,” in IEEE Int. Symp. Information Theory, Washington, DC,
Jun.2001,p.213.
[64] V. Guruswami and M. Sudan. “Reﬂections on Improved Decoding of ReedSolomon and
AlgebraicGeometric Codes”. IEEE Information Theory Society Newsletter, 52(1):612,
2002.
[65] J. Hagenauer and P. Hoecher. “A Viterbi Algorithm with SoftDecision Outputs and its Ap
plications”. In IEEE GLOBECOM, 1989.
[66] R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inform. Theory,
vol. IT27, pp. 533547, Sept. 1981.
[67] SB. Wicker and V.K. Bhargava. ReedSolomon Codes and Their Applications. IEEE Press,
1994.
[68] R. G. Gallager, “Low Density Parity Check Codes,” Trans. of the IRE Prof. G. Info. Theo.,
vol. IT8, January 1962, pp. 2128.
[69] W. E. Ryan, “An introduction to LDPC codes,” August 2003.
189
[70] S. Karande, “A Simple Relationship between Iterations and Error,” Private Communication,
2008.
[71] S. M. Ross, “Introduction to Probability Models”, Acad. Press. 2003.
[72] L. Rizzo, “Effective erasure codes for reliable computer communication protocols,” Comput.
Commun. Rev., vol. 24, no. 2, pp. 2436, Apr. 1997.
[73] L. Larzon, M. Degermark, and S. Pink, “Efﬁcient Use of Wireless Bandwidth for Multi
media Applications,” IEEE International Workshop on Mobile Multimedia Communications
(MoMUC), November 1999.
[74] L. Larzon, M. Degermark, and S. Pink, “UDP Lite for Real Time Multimedia Applications,”
IEEE International Conference of Communications (ICC), June 1999.
[75] S. Shakkottai, T. Rappaport, and P. Karlsson, “Cross Layer Design for Wireless Networks,”
IEEE Commun. Mag., vol. 41, no. 10, Oct. 2003, pp. 7480.
[76] P. C. N g, and S. C. Liew. Rerouting instability in IEEE 802.11 multihop adhoc networks.
IEEE LCN, pages 602609, 2004.
[77] S. Biswas and R. Morris. “Opportunistic routing in multihop wireless networks”. ACM
SIGCOMM, 2005.
[78] S. Chachulski, M. Jennings, S. Katti, and D. Katabi. “Trading structure for randomness in
wireless opportunistic routing”. In Proc. of ACM SIGCOMM 2007, Kyoto, Japan.
[79] D. S. J. De Couto, D. Aguayo, J. Bicket, and R. Morris. “A high—throughput path metric for
multihop wireless routing”. In ACM MobiCom 03, San Diego, California, September 2003.
[80] J. Broch , D. A. Maltz , D. B. Johnson , Y. Hu , J. Jetcheva, “A performance compari
son of multihop wireless ad hoc network routing protocols”, Proceedings of the 4th annual
ACM/IEEE international conference on Mobile computing and networking, p.8597, Octo
ber 2530, 1998, Dallas, Texas.
[81] C. E. Perkins and E. M. Royer. “Ad hoc on demand distance vector (AODV) routing”, 1998.
Internet Draft.
[82] G. Xylomenos, G.C. Polyzos, P. Mahonen, and M. Saaranen. TCP performance issues over
wireless links. IEEE Comm. Magazine, 39(4):5258, 2001.
[83] V. Jacobson. Congestion Avoidance and Control. In Proc. ACM Sigcomm’88, Aug. 1988,
pp 314329.
[84] Y. Tian, K. Xu, and N. Ansari. TCP in Wireless Environments: Problems and Solutions.
IEEE Radio Communication, 43(3): 827832, March 2005.
[85] “IEEE Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer
(PHY) Speciﬁcations”, Nov. 1997, P802.11.
190
[86] T. S. Ho and K. C. Chen, “Performance evaluation and enhancement of the CSMA/CA MAC
protocol for 802.11 wireless LAN ’s,” in Proc. IEEE PIMRC Taipei, Taiwan, Oct. 1996, pp.
392396.
[87] X. Wang and K. Kar, “Throughput Modelling and Fairness Issues in CSMA/CA Based Ad
Hoc Networks,” in INFOCOM, Miami, 2005.
[88] X. Liu, E. K. P. Chong, and N. B. Shroff, “Opportunistic transmission scheduling with
resourcesharing constraints in wireless networks,” IEEE J. Sel. Areas Commun., vol. 19,
no. 10, pp. 20532064, Oct. 2001.
[89] M. Andrews, K. Kumaran, K. Ramanan, A. L. Stolyar, R. Vijayakumar, and P. Whiting,
“Providing quality of service over a shared wireless link,” IEEE Commun. Mag., vol. 39, no.
2. pp. 150154, Feb. 2001.
[90] P. Bhagwat, P. Bhattacharya, A. Krishna, and S. K. Tripathi, “Enhancing throughput over
wireless LANs using channel state dependent packet scheduling,” IEEE INFOCOM 1996.
[91] S. Shakkottai and R. Srikant, “Scheduling realtime trafﬁc with deadlines over a wireless
channel,” 2002 ACM Wireless Netw. J.
[92] J. Huang, R. A. Berry, and M. L. Honig, “Wireless Scheduling With Hybrid ARQ”, IEEE
Trans. Wire. Commun. vol. 4, no. 6, 2005.
[93] M. Horowitz, A. J och, and F. Kossentini, “H.264/AVC Baseline Proﬁle Decoder Complexity
Analysis,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7,
July 2003
[94] M. van der Schaar and S. Shankar, “CrossLayer Wireless Multimedia Transmission: Chal
lenges, Principles, and New Paradigms,” IEEE Wireless Commun., vol. 12, no. 4, Aug. 2005,
pp.5058.
[95] IA. Zhao, B.Li, C. Kok, and I.Ahmad, “MPEG4 Video Transmission over VVrreless: A
Link Level Performance Study,” ACM/Kluwer Journal of Wireless Networks, vol. 10, issue
2, March 2004, pp. 130146.
[96] I. E. G. Richardson, “Video Codec Design: Developing Image and Video Compression Sys
tems”, WIELY, 2002.
[97] D. Mitra. Stochastic Fluid Models. Perfomance 87, Elsevier Science Publisher, North Hol
land 1988.
[98] H. Chen and D. D. Yao, “Fundamentals of Queueing Networks”, Springer.
[99] M. Mandelbaum, M. Hlynka, and P. H. Brill,“Nonhomogeneous geometric distributions with
relations to birth and death processes,” Springer journal TOP on Business and Economics,
July 2007.
[100] E. Plambeck, S. Kumar, and J. M. Harrison, “ A Multiclass Queue in Heavy Trafﬁc with
Throughput Time Constraints: Asymptotically Optimal Dynamic Controls,” Queu. Sys.
Springer J. vol. 39, No. 1, 2001.
191
[101] S. Boyd and L. Vandenberghe, “Convex Optimization,”Cambridge University Press 2004.
[102] J. G. Kim and M. M. Krunz, ”Delay analysis of selective repeat ARQ for a Markovian
source over a wireless channel,” IEEE Trans. Veh. Technol., vol. 49, no. 5, pp. 19681981,
Sep.2000
[103] “ReedSolomon source code”, http : / /www . eccpage . com/
[104] “LDPC Software”, http://www.cs .utoronto.ca/radford/ldpc.
software.html
[105] OMNeT++ Community, http : / /www . omnetpp . org.
[106] H.264/AVC Software Coordination http : / / iphome . hhi .de/ suehring/tml /
192
067
3 1293 03062
illll[ll[ill][llWilli][[1111111l