.9173.
..

i 1
.3 ,..... :
my}? .

\ , at»... .-
1h.h.u.§ .ndisn :

abnu

,. 3...! 70.... ..
$.1-

 

imav i.

.r fix
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
LINK-LAYER 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
LINK-LAYER PROTOCOLS FOR WIRELESS
COMMUNICATION

By

Sohraab Soltani

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Computer Science

2009

ABSTRACT

ANALYSIS AND DESIGN OF RELIABLE AND STABLE
LINK-LAYER PROTOCOLS FOR WIRELESS
COMMUNICATION

By

Sohraab Soltani

Wireless links are error-prone 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 link-layer protocol embedded in Medium Access Control (MAC) has
a significant role in providing robust information delivery over wireless channels. A primary
focus of popular wireless link-layer protocols is to achieve some level of reliability using ARQ or
Hybrid ARQ mechanisms. However, these and other leading link-layer protocols largely ignore
the stability aspect of wireless communication, and rely on higher layers to provide stable traffic
flow control. This thesis investigates the problem of reliable and stable transmission over wireless
channels and highlights the inadequacies of the current IEEE802.11 standard link-layer which
attempts to recover from losses using retransmissions.

In this thesis, we aim to tackle the critical issues associated with the inefficiencies of current
wireless link-layer protocols and pursue a paradigm shift in the conventional 802.11 link-layer
design. We develop a new link-layer framework to provide both the reliability and stability for

point-to-point contention free wireless communication. Using this framework, we introduced four

link-layer protocols: 1) Packet Embedded Error Control (PEEC) protocol, a link-layer 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 (DC-PEEC), an ex-
tension of the PEEC protocol that targets the flow control of realtime video traffic (in addition to
reliability) in wireless communication. DC-PEEC adjusts its parameters to provide low-latency
communication to satisfy the delay constraint (required by the video application) while utilizing
the channel bandwidth effectively; 3) Automatic Code Embedding (ACE) link-layer protocol, the
first effort to develop a theoretical framework for analyzing and designing a wireless link-layer
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 link-layer packets in every
transmission to ensure stability, reliability and maximum throughput; 4) Prioritized ACE (PACE),
the ACE based stable-and-reliable link-layer that employs a novel rate-adaptive 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 link-layer 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 signifi-
cantly outperform all competing link—layer protocols. Our findings in this thesis indeed provide
a clear evidence of the feasibility of designing stable and reliable link layer over point-to-point
(single-hop) 802.11 channels; and more importantly the potential of achieving significantly im-

proved throughput by using this type of link-layer.

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 difficult 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 Cross-Layer Approach ............................... 13

3 Background ....................................... 15
3.1 802.11b Wireless Networks ............................. 15

3.2 Trace Collection ................................... 16

3.3 Discrete-Time Markov Chains ........................... 17

3.4 Binary Symmetric Channel ............................. 19

3.5 Markovian Wireless Channel ............................ 20

4 PEEC: A Channel-Adaptive Feedback-Based 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 A-LDPC ................. 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

DC-PEEC: 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 DC-PEEC ................ 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 Traffic .............................. 106
6.4.2 N on-Realtime Traffic ............................ 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 Throughput-Delay Tradeoff ........................ 154

7.4.2 Realtime and Non-Realtime 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 higher-layers ...................... 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 afier decoding is truncated on are, ............... 30
The architecture of the PEEC protocol ....................... 34

IEEE802.11 MAC frame formats and corresponding modifications 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 A-LDPC 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 fitted 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 DC-PEEC link-layer 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 five 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 figure 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 traffic 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 traffic is generated by non-realtime TCP
and realtime video flows. .............................. 158

The performances of non-realtime and realtime applications in terms of through-
put and video quality ................................. 160

An example of multi-hop 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 link-layer protocols of well-established
wireless systems. These shortcomings are expected to be exacerbated as the level of heterogeneity
and high-bandwidth requirements of emerging applications increase dramatically. In particular,
popular wireless link-layer 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 error-free or a maximum number of retransmission attempts is reached. Many
leading research efforts [32]- [39] have highlighted the inefficiencies of the current 802.11 link-
layer protocol and proposed a variety of remedy solutions. Although recent proposed remedies for
the wireless link-layer 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
high-end heterogeneous applications cannot afford piecemeal solutions. Hence, in this thesis we
aim to tackle the critical issues associated with the inefficiencies of current wireless link-layer

protocols and pursue a paradigm shift in the conventional 802.11 link-layer design. In particular,

we introduce a comprehensive framework that presents a thorough analysis and modeling of a
generic link-layer point-to-point 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 link-layer for heterogeneous wireless net-
works that overcomes the shortcomings of current link-layer standards demands fundamental and
radical changes to the conventional link-layer protocol design. We highlight the key issues with

the 802.11 link-layer protocol:

1. Inefficient reliability: The 802.11 ARQ approach discards corrupted packets that are mostly
error-free, even when there is only a single bit error in a corrupted packet. Hence, the effec-
tive throughput of 802.11 systems can be significantly improved. This issue led many efforts
to propose new link-layer and cross-layer 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 inefficiencies of ARQ-based
wireless protocols include Partial Packet Recovery (PPR) [54], packet combining [32]- [47],
Cross-Layer Design with Side-information (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 link-layer
protocols in conjunction with error correcting codes to recover corrupted packets. In par-
ticular, the work on CLDS demonstrates a significant 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 information-theoretic capacity significantly [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
link-layer 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, ARQ-based 802.11 link-layer and other recent protocols largely ignore the
stability aspect of data communications in terms of maintaining a sustainable flow, which
is critical for a dynamic and heterogeneous wireless environment. Although many leading
efforts have addressed the reliability and associated throughput inefficiency shortcoming of
current 802.11 link-layer (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 flow control for both realtime and non-realtime traffic. In conjunction with the
inefficient reliability approach, this design strategy has led to a great deal of inefficiency
in throughput and to other major technical issues and challenges at higher layers. A well-
known example is the TCP over-wireless 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 link-layer
protocols to overcome the above shortcomings. Our objective is to develop wireless link-layer
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 efficient 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

overflows.

Using this framework, we first focus on the reliability aspect of wireless link-layer communica-
tion and identify its capabilities and limitations. These analyses lead to the development of a novel
link-layer 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 link-layer that targets both
reliability and traffic flow 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 link-layer protocol. To the best of our knowledge this is the first effort
to develop a theoretical framework for analyzing and designing a wireless link-layer 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 flows in wireless networks.

Chapter 4 presents statistical analysis of a link-layer, point—to-point and contention-free 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
link-layer protocol. PEEC employs packet-embedded parity symbols (instead of retransmission)
for error recovery. Also, PEEC uses certain flags embedded in the receiver feedback to determine
the amount of redundancy necessary for the next transmission. PEEC utilizes acknowledgment
flags (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 efficiently utilized for the transmission of new data. Our experimental

simulations show that PEEC outperforms the leading error control protocols designed for wire-
less link-layer. PEEC is layer oblivious and compatible to IEEE802.11 standard link-layer packet
formats.

Chapter 5 develops an analytical framework for video communication which captures the be-
havior of realtime video traffic at the wireless link-layer while taking into consideration both
reliability and latency conditions. Using this framework, we introduce a Delay Constraint Packet
Embedded Error Control (DC-PEEC) protocol for wireless link-layer. DC-PEEC ensures reliable
and rapid delivery of video packets by employing various channel codes to minimize fluctua-
tions in throughput and provide timely arrival of video. The proposed effort begins by outlining
a novel analytic framework to capture video traffic flow at the wireless link-layer. In particular,
we develop a queuing model that captures realtime video traffic behavior under reliability and
end-to-end delay constraint at the wireless link-layer. Specifically, we model the link-layer buffer
as an MIG/1 queuing system with random-sized batch arrivals of video information having a sin-
gle server representing the link-layer protocol with a general service-time distribution. Using this
model, we find an operational code rate for DC-PEEC which guarantees video traffic flow with
tolerable latency while utilizing the channel bandwidth effectively. We compare the performance
of DC-PEEC with that of IEEE802.11 ARQ and HARQ in terms of PSNR gain under various
realtime video communication setups. The simulation results suggest that DC-PEEC is a suitable
wireless link-layer 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 link-layer protocol. The proposed wireless ACE
link-layer (a) employs a theoretically-sound framework and a corresponding strategy for embed-
ding channel codes, using robust and well-defined 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 first to present a theoretical framework for analyzing

and designing a wireless link-layer 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. Specifically, we first 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 link-layer behavior as an on-off source
model using a two-state Continuous Time Markov chain (CT MC) model. We deploy fluid ap-
proximations to analytically characterize the buffer growth. By utilizing these models, we find
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 traffic demands (in terms of reliability and stability requirements) can be met using a
packet-by-packet code embedding rate constraint that is independent of traffic type. This leads
to simplistic, traffic-independent 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 non-realtime traffic, TCP
throughput and realtime video communication scenarios show that ACE significantly 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 flows in wireless networks. Under the
proposed Prioritized ACE (PACE) framework, our ACE based stable-and-reliable link-layer will
employ a novel rate-adaptive 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. Specifically, we develop a LDPC decoding model to capture the decoding
process for link-layer traffic and use it to determine an optimal code selection strategy for max-
imal bandwidth utilization. Further, we find an optimal code embedding rate under the PACE

framework to jointly meet the reliability, stability, and delay constraints of the wireless link-layer

 

communication. We classify heterogeneous link-layer traffic arrivals into different priority classes
based on packet delay constraints and the distortion suffered. The traffic arriving in each priority
class is modeled as a Poisson process. Consequently, we formulate the link-layer 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 link-layer 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 DC-PEEC protocol developed for realtime wireless
video communication is presented in Chapter 5. In Chapter 6, we present the ACE framework,
the first analytical model that jointly targets reliability and stability of wireless link-layer 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 link-layer 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 defined as follows:

Definition 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.

Definition 2. Error Correction is the information processing ability which result in the

reconstruction of the original, error-free data at the receiver
There are two different ways to design an error correction protocol:

1. Automatic repeat-request (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 re-sends anything not acknowledged

within a reasonable period of time.

2. Forward error correction (FEC): The transmitter encodes the data with an error-correctin 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 link-layer protocols use either one of the above approaches or the combination of the

two to provide reliability.

2.1 ARQ-based Schemes.

In this section, we present an overview of link-layer 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 standard-compatible 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 identified by the 16-bit sequence
control field that indicates its sequence number. Using the 32-bit FCS field at the receiver, the
received packet can be checked for errors. If it is error-free, 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 first combination scheme, here referred to as xor combining [33,34], consists in xor-ing two
erroneous copies to locate errors in both packets. The decision process then involves a brute-force
bit-by-bit 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 defined 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 (MA-k) [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 bit-by-bit 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 bit-error 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 significant advantage especially in applications where repeated packets can present a sig-
nificantly 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, type-I HARQ [49], the sender encodes the packet payload with an error-correction code
prior to the transmission. Accordingly, the receiver requests for a retransmission when the decod-
ing of the received packet fails. In type-II hybrid ARQ (HARQ-II) [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 HARQ-II is similar to
the PEEC and ACE protocols since these schemes achieve recovery through the transmission of
additional redundancy. However the HARQ-H is not designed for IEEE802.11 MAC environment
and is not adaptive with respect to channel condition. In addition, HARQ-II does not address
throughput stability issues raised by varying traffic demand.

In addition to Hybrid ARQ (HARQ) based methods [43—45], examples of recent efforts
for combating inefficiencies of ARQ-based wireless protocols include Partial Packet Recov-
ery (PPR) [54], packet combining [32]- [47], Cross-Layer Design with Side-information
(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 significant
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

information-theoretic capacity significantly [5].

2.3 Cross-Layer 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 error-resilient nature of multimedia content.
The analysis of the hybrid Erasure-Error protocols (HEEPs) in [5] shows that cross-layer proto-
cols in general provide capacity improvement in many realistic scenarios and can significantly
improve the overall performance as measured by video quality. However, a significant drawback
of the cross-layer protocols is that their implementations require major modifications 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 link-layer protocols for
wireless link-layer that in addition to providing reliability, they target other aspects of wireless
communication such as flow control for delay constrained traffic, stability and traffic 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 time-tested TCP/IP protocol suite, 802.11b networks
have experienced widespread deployment. These LANs are finding 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 inter-symbol-interferences.
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 lb-complaint 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 32-bit 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: five
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 fixed 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 specific 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 Discrete-Time Markov Chains

Markov chains are employed to model statistical data with short-term temporal dependence. Let
a stochastic process X n take on values denoted by non-negative 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 fixed

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 one-step state transition probability
matrix.

The steady-state or stationary probabilities of a Markov chain represent the long-run proportion
of the time spent in each state. Once the transitional probabilities of a Markov chain are known,
the steady-state probabilities of being in a particular state are the unique non-negative 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 steady-state 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 “flipped” 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 infinite 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 = 0|X = 0) = 1— e (3.4)
P(Y = 0|X = 1) = e (3.5)
P(Y = 1|X = 0) = e (3.6)
P(Y =1|X = 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 cross-over BER 62'. To derive a channel
model for all transmission intervals, we assume that each e,- of a particular Ti is valued from a finite
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

pN-1,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 = Zfliei (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 cross-over 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 Channel-Adaptive
Feedback-Based Error Control Protocol for

Wireless MAC Layer

In this chapter, we investigate the problem of reliable wireless link-layer communication over a
lossy channel. Specifically, we introduce an analytical framework that presents a thorough anal-
ysis and modeling of a generic link-layer point-to-point wireless communication which employs
channel codes to provide and maintain a reliable communication. Our objective is to develop
a new wireless link-layer framework which make use of incremental channel codes to provide
maximum reliability (high likelihood of successful recovery data at the receiver) while ensures an
efficient utilization of available bandwidth in transmission of new data.

This framework comprises various models including communication, message, distortion and
bufier models. The analysis provided under this framework leads to the development of a novel
link-layer Packet Embedding Error Control (PEEC) protocol [3].

PEEC employs packet-embedded parity symbols (instead of retransmission) for error recovery.

Further, PEEC uses certain flags embedded in the receiver feedback to determine the amount of

23

redundancy necessary for the next transmission. PEEC is similar to the HARQ-II protocol in
the sense that in both schemes, the recovery is achieved through the transmission of additional
redundancy information; however PEEC utilizes acknowledgment flags, a decoding and a bufier,
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 efficiently utilized for the transmission of new data. Another design objective of PEEC is its
compatibility with conventional higher-layer transport and application layer protocols. That is,
unlike cross-layer 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 define 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 error-free. 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 type-I 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
(type-II) 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 finite buffer containing m rooms. That is, the receiver can
accommodate up to m corrupted messages waiting for recovery. If a newly corrupted packet finds
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 flags in an acknowledgment message. Specifi-
cally, 1 + 3 flags are encapsulated in every acknowledgement. Let Fi[k], k = 0, - - . ,3 represent
values of these flags in ACKi. We refer to the first flag (i.e., Fz- [0]) as a decoding flag, indicating
the decoding status of the transmitted message in Ti; F210] = 1 when decoding of M,- was not
successful. The remaining 3 flags (i.e., Fi[k], k = 1, - - - ,s) are called buffer flags. Each buffer
flag 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
Type-I Type-ll
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 first transmission interval T1, a mes-
sage M1 = (Cl(kl,a:1),y1) is sent. There are no type-II 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 type-II
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 type-II 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 flag to zero (i.e., F3[0] = 0) but at the same time
since the decoder is waiting for type-II parity symbols to perform decoding on Cg, the buffer
flag 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 packet-embedded 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 type-I parity symbols to increase the likelihood
of reliable reception. On the other hand, a reasonable amount of type-II redundancy is required
to correct corrupted packets and prevent buffer overflow. 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 find 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, type-I and type-II 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 fixed 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 type-I (type-II) 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 finding 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
error-correcting capability of a particular decoder. For example, the error-correcting capability of
Reed-Solomon 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 error-correcting 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 type-I parity probability distribution p Xi can be achieved if

1 —1
> __ . .
sz, _ no (m, + ./n6,¢ (11)) ,
where (1)—101) is the V-quantile of the standard normal distribution.

Proof. See Appendix A. I]

30

4.2.3 Buffer Model

The receiver has a finite buffer with the capacity of m messages. A message enters the buffer
when its decoding with type-I parity symbols has failed. Meanwhile, a message leaves the buffer
when its decoding with additional type-II 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 type-II 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 finds 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£' (4-6)

x=0 d=0

Any particular decoder utilizes type-II parity symbols in addition to the original type-I parity

symbols to decode a particular message. So the service rate is equivalent to the probability of suc-

31

cessful decoding using type-I and type-II 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 = Zfliui. (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 verifies 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 error-combating 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 overflow. 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 error-control mechanism to
adaptively find 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. Specifically, PEEC utilizes
decoding and buffer flags 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 flag 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 type-I parity symbols in the message was not sufficient to correct distortion. Similarly,

a successful decoding (F-_1[0] = 0) shows that the BER was low. The error-correcting 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 error-correcting 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 error-correcting capability (1 fails to decode a message

with type-I 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 flag 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 find the best S, when F-_1[0] = 1.

4.3.2 Redundancy Allocation

PEEC uses S, along with bufler flags (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 type-I 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.->=e.logg< >+(1-e.->Iog2( ).

:1 1 - éi

According to our communication model each buffer flag 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 type-H 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 specific 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 type-II 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 type-II 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 specified 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 link-layer.
Fig. 4.4 shows the IEEE802.11 data and ACK frame formats. The IEEE802.11 link-layer 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 fields that used by PEEC. First, we modify the frame body field and divide it into
three fields for data, type-I and type-II parity bits. Further, we modify the frame control (FC) field
in the ACK frame to incorporate decoding flag and buffer flags. Specifically, we redefine the retry

field to serve as the decoding flag.

37

Octets: 2 2 6 6 6 2 0-2304 4

 

 
    

equenoe Hamlel FCS I

Frame IID Duration/ IAddress 1 IAddress 2IAddress 3 IS

Control Control

 

ataii I Type-lPerlty

 

 

(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 modifications necessary for
PEEC.

As eluded above, when the decoding flag is set to zero, this signals to the transmitter that the last
transmitted packet was decoded successfully. However, when the decoding flag 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 flags indicate the status of one or more (up-to 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 field by 3 bits for additional 3 buffer flags.

In the next section, we observe that in practice, by utilizing a single buffer flag that corresponds

38

to a decoder with error-correcting 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

field.

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 error-correcting 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 error-correcting 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 figure 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-
E-l
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 significantly 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 significantly when a decoder is
utilizing a code with decent error-correcting 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 error-correcting 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 MA-3 MA-5 GMA-4 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 error-combating 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
bit-by-bit majority decision is performed to reconstruct a packet. That is, for MA-3 (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 five 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, GMA-4 and GMA-S. 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 MA-3
performs the majority combining algorithm if the retransmissions of the second and third copies
have failed. The MA-3 algorithm always performs majority decision on the last three received
copies. The MA-S is employed if the retransmission and MA-3 schemes have failed to recover the
corrupted packet. Similarly, the GMA-S is applied if MA-5, GMA-4, MA-3 and retransmission
schemes have failed. So, we expect that the GMA-S 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 significant 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 error-correcting capability. Hence,
these schemes cannot achieve significant improvement in the performance since they are utilizing
repetition codes with length three and five.

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 HARQ-I and
HARQ-II, we introduce parameter A. In particular, A specifies the proportion of the redundancy
information in the packet. For instance, for the packet with size n, in the HARQ-I, the sender
transmits 2% redundancy and 94%;!) data symbols. Similarly, % specifies the amount of addi-
tional redundancy that is allocated by HARQ-II 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 insufficient 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 GMA-S and we also find 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. Specifically,

44

0.95

—IEEE ARQ GMA-5 mmHARQ-I (Best) - - -HARQ-II (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 munGMA-S --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

......HARQ-I (Best) HARQ-II (Best) «ta-PEEC

 

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 GMA-S with those of the
HARQ schemes. In general, we observe that the HARQ-II outperforms HARQ-I for all traces. In
addition, as the previous experiments suggested, the GMA-S 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 fixed 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 fluctuations in the
performances of the IEEE ARQ and GMA-S is detected; this is discussed in the sequel.

Fig. 4.8b shows PEEC performance with that of IEEE802.11 ARQ and GMA-5. 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 fluctuating
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 fluctuations appear when the PER fluctuates 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 fluctuations 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 error-correcting 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 error-correcting 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 HARQ-II (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 HARQ-II scheme regardless of the value of a.

49

0.551»-

 

0.5
0

0.95

Throughput
O
61’

—IEEE ARQ

PEEC (alpha = 0.1)
n-u-rPEEC (alpha = 0.3)
- - -PEEC (alpha = 0.5)

 

1 1 1 g
0.005 0 01 0.015 0.02 0025
Channel average BER

(a)

—HARQ-II (Best) (alpha 2 0.1)
HARQ-II (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 A-LDPC

For the experimental results illustrated in Fig. 4.8, it is assumed that the error-correcting 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 A-LDPC decoder over various channel
traces.

always valid, we evaluate the throughput of the PEEC protocol using a relatively simple Adap-
tive Low-Density-Parity-Check code (A-LDPC). 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 flipping distorted bits. The receiver uses A-LDPC 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 error-correcting 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 find that the estimated error-correcting 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 error-correcting capability a = 0.1. We observe that the performance of the
model captures the throughput obtained by employing A-LDPC. This result verifies the accuracy
of our analysis and suggests that by using a code with error-correcting capability close to perfect

codes, we can achieve higher throughput.

4.5 Channel Coding Rate Analysis

An important objective of error-correcting 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 error-correcting

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<C

52

where C is the channel capacity. Ideally, a perfect error-combating scheme should operate with
a channel coding rate very close to the capacity while achieving a likelihood of decoding failure
close to zero. However, in practice error-correcting codes have to operate considerably below
capacity to achieve zero decoding failure probability. In this section, we derive the likelihood of
successful decoding and the channel coding rate of the contemporary error-correcting methods

and PEEC.

4.5.1 IEEE802.1] ARQ

IEEE802.11 ARQ mechanism requests a retransmission for the copy of the corrupted received
packet. This procedure is repeated until an uncorrupted copy is received or the Maximum Trans-
mission Limit (M TL) is reached. To find the probability of decoding failure of IEEE802.1] ARQ,
we let d represent the tolerable delay of every transmitted packet at the receiver side. According
to the IEEE802.1] ARQ mechanism, this delay should be at most M TL. Let 6, represent the

likelihood that the transmitted packet is erroneous when the channel is in state 3,. Thus,
q,- = 1 — (1 — 6,)”. (4.11)

Under IEEE802.1 1 ARQ, a particular packet is successfully delivered if it is errorless in the first
transmission or in any of consecutive d — 1 retransmissions. Therefore, the process of recovering
the original packet under IEEE802.1] ARQ has the geometric distribution with parameter 6,.
Consequently, the likelihood of successful decoding under IEEE802.1] ARQ after 01 transmissions

when the channel is in state S, is,

P1138604) = Z <f‘1(1— <1)- (4.12)

The channel is in state S, with the steady state probability of 1r,, correspondingly, the probability

53

of successful decoding (on average) is:

N
Pieee(d) = Z 7rtlpz'eee(ir dl' (4-13)
i=1

Under IEEE802.1 1 ARQ, a sender transmits a new packet in the first transmission and performs
d — 1 retransmissions until an errorless packet is received. Since each packet has length n, the

channel coding rate is

mw=—=. mm

4.5.2 Enhanced ARQ

Under Enhanced ARQ mechanisms such as majority combining (MA-k) and generalized majority
combining (GMA-k) methods, a majority combination of the original packet and its corrupted
copies is performed on the top of the retransmission mechanism when the original packet is not
retrieved after I: — 1 retransmissions. In the following sections, we compute the probability of
successful decoding (recovering the original packet) of each of these schemes. In general, this
probability is governed by the number of packets that are combined k and the maximum retrans-

mission limit d.

Majority Combining with k Copies

In the case of MA-k, bit-by-bit comparisons of 11: copies of a packet are performed, if a retrans-
mission mechanism fails to recover the original packet after k - 1 transmissions. Assuming the
channel is in state 5,, equation 4.12 suggests that a retransmission mechanism fails to recover a

packet after h — 1 transmissions with probability of
19—1
r—§:§*H1—gf. (an)
i=1
In ith

,i 2 k transmission, a MA-k method successfully retrieves a packet when an errorless

copy is received or a majority combining method succeeds. Having a channel in state 5,, the

54

probability of receiving an error-free packet is (1 — q, ). Further, under MA-k, a successful recovery
is achieved if any m = [129] combinations of 1: copies are identical. Let random variable Z
represent the number of bits of a particular location in [0 packets that have identical values. Since
each bit can be distorted with probability of 1 — 6,, Z has the binomial probability mass function
with parameters (1 - 6,, k). Therefore, the probability that the majority combining algorithm

successfully decodes a bit (at least m bits have identical value) can be computed as follows:

16
k k—a:
P,- = Z ($)(1—e,)$6§ ). (4.16)
332171.
Each packet has the length of 71 bits, therefore using the majority combining algorithm, all 71. bits
are decoded successfully with the probability of P2." when the channel is in state 8,. Consequently,

the likelihood of successful delivery in ith,i 2 k retransmission is

91 = (1 - g) +<,-P,-. (4.17)

In general, the enhanced ARQ mechanism which uses MA-k recovers the original packet after
61, d 2 k transmissions if (1) the ARQ mechanism succeeds in the first (is — 1) transmissions and
(2) the majority combining method succeeds for the rest of the possible transmissions. Therefore,
assuming the channel is in state S, using equations (4.15) and (4.17), the probability of successful

decoding under MA-k method is

Pmaa, k, d) = 13,66,301 — 1) + (1 — 113-6860,11 — 1))A(i, k, d) (4.18)
where
d
A(z’,k,d) = 2(1— g,)t—kgj. (4.19)
t=k

The channel is in state S, with steady state probability of 7r,, therefore the probability of suc-

cessful decoding enhanced ARQ method using MA-k (on average) is

N
Pmaw, d) = Z «,Pmap, k, d). (4.20)
1:1

55

Generalized Majority Combining with 11: Copies

th,i > k retransmission, a

In case of generalized majority combining scheme (GMA-k), in i
GMA-k successfully recovers a packet when an error-free copy of a packet is received or any
combination of MA-l (l < k) succeeds. For instance GMA-5 should apply all cases of the MA-3
method on 5 copies so for k = 5, l = 3. Equation (4.16) suggests that each MA-l 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 MA-l cases that succeed. Having k
packets at the receiver, the number of possible MA-l operations is L = (If). Therefore, W
has the binomial distribution with parameters (P,, L). Consequently, the likelihood that GMA-k

algorithm successful recovers the original packet (at least one of the L MA-l 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 GMA-k successfully recovers the origi-
nal packet when (1) retransmission mechanism succeeds in the first I — 1 transmissions, (2) MA-l
method succeeds in 3,1 5 j 5 k — 1 transmissions and (3) GMA-k 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 GMA-k (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 error-correcting capability of a particular decoder.
Specifically, 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 HARQ-I 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 HARQ-I after (1 retrans-

missions is
d .
W) = 2(1- g4<i)>1—1(1— 94(2)). (4291
2'21

The channel coding rate for HARQ-I depends on the amount of redundancy carried with a

packet in the first transmission 2:1,

Tl. —' II}
R4(2:1,d) = M 1 (4.30)

 

The derivations of the failure decoding probabilities of HARQ-II and PEEC are similar to
HARQ-I. Because the later protocols utilize additional parity bits, the failure likelihood decreases
dramatically as additional parity bits are employed. The channel coding rate for HARQ-II 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 error-correcting 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. MA-3 and GMA-5 have
a relatively better performance than IEEE802.11 ARQ and even HARQ-I, 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“ MA-3-"+-- GM-S-E-HARQI '4-HAROH —PEEC

_A
I

: : aw“
. ‘ and .
0.8’ ., ,..””—H‘ Q,‘,‘_.,£’
.6 z 9:» - -
33 0.7L. ... ., .’.‘.'..’. ...-'4. .
'8 : "_" :
8 0.6“ ,.. .....I‘...
D‘ . I".
I-I - 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-"+" GM-S-B-HAROI '4-HARQII —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.

HARQ-II and PEEC performance are superior to other methods. Meanwhile, as we observe PEEC
outperform HARQ-II as the channel conditions worsen.

Fig. 4.13 illustrates an overall performance of all schemes over various channels. Specifically,

59

----- IEEE802.11 “0“ MA—3"'+" GM—S-B-HAROI '4-HARQII --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" MA-SM-"O'" GM-S-B-HARQI 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 HARQ-II 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 error-combating 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 Low-Density-Parity-Check (A-LDPC) decoder was presented. In the next chapter, we

extend the PEEC protocol to provide both reliability and flow control for realtime video traffic.

62

CHAPTER 5

DC-PEEC: 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) low-latency to satisfy realtime delay constraint. These requirements make it
essential to design an error control protocol that provides flexible flow 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 error-prone nature of wireless links and their susceptibility to a variety
of distortions caused by fading, interference, and mobility.

The de facto IEEE802.11 link-layer error-control protocol [29] uses retransmissions to provide
reliability for wireless environments. Although this technique ensures reliability “over-a-long-
run”, it does not provide flow control mechanism with respect to latency. This design strategy

has led to a great deal of inefficiency 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]. Inefficient 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 cross-layer mechanisms
to overcome performance limitations imposed by conventional protocols [94] [95]. Examples of
these protocols are the Hybrid Erasure-Error 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 link-layer 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 link-layer that targets both reliability and traffic
flow control for realtime video communication. Delay Constraint Packet Embedded Error Control
(DC—PEEC) protocol employs channel codes (using robust and well-defined code rates) in each
packet to ensure that video packets are delivered reliably within an end-to-end delay deadline of
realtime video communication. The proposed effort begins by outlining a novel analytic frame-
work to capture video traffic flow at the wireless link-layer. In particular, we develop a queuing
model that captures realtime video traffic behavior under reliability and end-to-end delay con-
straint at the wireless link-layer. Specifically, we model the link-layer buffer as an M/G/l queuing
system with random-sized batch arrivals of video information having a single server representing
the link-layer protocol with a general service-time distribution. Using this model, we find an op-
erational code rate for DC-PEEC which guarantees video traffic flow 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 traffic at the wireless link-layer.

0 We propose the DC-PEEC protocol for point-to-point link-layer wireless communication
which is layer oblivious and provides reliability and flow 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 traffic 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 traffic for wireless communication.

The upper-level view (i.e., application layer) shows an ideal encoder-decoder buffer model
for video communication analyzed in many multimedia literatures [96]. Under this model, un-
compressed video pictures first 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 profile to encode video stream [93]. Each video frame is
encoded to a compressed Group of Pictures (GOPs) comprising of I-slices followed by P-slices.
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 upper-level view the end-to-end 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

Llnk-layer 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 lower-level view shown in
Fig. 5.1.

Compressed pictures exiting the encoder buffer are processed by the Operating System (OS)
and converted to transport-layer segments. These segments are then converted to network-layer
datagrams with appropriate headers added. In this packetization phase, compressed pictures are
divided into small video packets. Specifically, the Network Abstraction Layer Units (NALU) of
H.264 standard is utilized to encode the video stream. Traditionally each NALU is embedded in
MPEG-2/RTP-IP/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
fixed 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 link-layer where

66

they enter the link-layer 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 end-to-end 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 link-layer protocol:
A = Aideal + Tm; + Try: + Tu.

The process of delivering video pictures is constrained to an end-to-end 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 satisfied:
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 link-layer destination within the link-layer tolerable

67

delay T. To that end, we analyze the video packet traffic behavior at the link-layer and model the
link-layer buffer to analytically obtain an average (expected) delay of each video packet at the
link-layer (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 link-layer at a rate A. This rate governs the GOP
arrival process at the link-layer buffer. Hence, the arrival process of the link-layer buffer is a
Poisson process having rate A. Thus, the link-layer buffer is a queue with customers arriving in
random-sized batch where each batch represents one GOP and each customer (in the batch) is
one video packet. On the other hand, the link-layer protocol attempts to reliably transmit each
video packet in the buffer over a wireless channel. Thus, the algorithm employed at the link-layer
protocol dictates the service time distribution of the buffer. Consequently, the link-layer buffer
can be modeled as an M / G /1 queuing system with random-sized batch arrivals having a single
server representing the link-layer 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 link-layer buffer is AG 2 /\E [N]. Consequently, the (average) delay for delivering a

single video packet to the link-layer 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 link-layer 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 link-layer buffer due to other video packets is:

jaj

 

 

 

 

E[WGOP] = ; E[WGOP|GOP 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
ElGllfglgil-EWD + AElleElG2l
WQ = T1-]—,\1~:[N]E[G] ' (5'9)

In this work, we use constant-quality 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. Specifically, 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 fitted to the empirical distribution of N. For instance, Fig. 5.2 shows that the quantile
function of fitted 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 fitted 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 link-layer 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 packet-level queuing model within the context of delay-constrained
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 link-layer tolerable delay deadline T. It is important to note that adhering to this

70

video packet-level delay constraint satisfies the traditional video-frame level delay constraint. As
we pointed out earlier, we adopt a packet-level 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 link-layer 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 (DC-PEEC)
link-layer protocol which employs novel rate-adaptive 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
much-further and much-needed, novel developments and integration of communication solutions.
DC-PEEC framework is designed (based on the realtime video communication model developed
in the last section) to provide reliable and delay-constraint information delivery at the link-layer.
We first describe the operational communication model of DC-PEEC. Next, we model the service
time distribution in Equation (5.11) based on the DC-PEEC functionality. Finally, we describe
two important components of the DC-PEEC protocol (namely Channel State Estimation and Re-
dundancy Allocation) which are essential to maintain continuous and low-latency realtime traffic

flow while ensuring maximal reliability and throughput.

5.2.1 Communication Model

In DC-PEEC 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 DC-PEEC link-layer 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 type-X 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 (type-Y) 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 finite buffer which can accommodate up to m corrupted mes-
sages waiting for recovery. If a newly corrupted packet finds 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 flags in an acknowledgment message (ACK) which are called bufier flags. Fig. 5.3 illus-
trates the ACK format. There are m buffer flags are encapsulated in ACK. Let F211;], is = 1, - - - , m
represent buffer flags in ACKi. Each buffer flag 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 1x2lxililfllf-(E
I I \, X \‘

 

 

l
f Decoding Achieved . ’_

  

X Decoding Failed :

Receiver
Buffer .
Type-X Type-Y

Figure 5.4 An example of DC-PEEC 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 DC-PEEC feedback scheme requires m additional bits for buffer flags and one ad-
ditional byte for channel estimation feedback to the current IEEE802.11 standard frame control
field. In our analysis, we choose m = 5.

An example of DC-PEEC 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 first transmission interval 7'1, a message Ml = [C1(k1,z1),y1] is sent.
There are no type-Y 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 type-Y 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 flag of the first room to zero (i.e., F3[1] = 0) but at the same time since
the receiver is waiting for type-Y parity symbols to perform decoding on Cg, the buffer flag 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 DC-PEEC

DC-PEEC encodes each video packet data bits k7; with $2- type-X 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. DC-PEEC 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

error-correcting 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 DC-PEEC, 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 type-Y parity symbols. Therefore the
probability of successful recovery of a particular packet increases as more type-Y parity symbols
are transmitted. Consequently, the error correction process of every packet under DC-PEEC 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 (type-X and type-Y) of 2t- Consequently, the service time distribution G of the
link-layer buffer (under DC-PEEC) 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 first 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 link-layer under DC-PEEC algorithm.

Later, we utilize this latency to find an optimal redundancy allocation scenario for DC-PEEC.

5.2.3 Channel State Estimation

Maintaining a low latency traffic flow and achieving maximum throughput and reliability under

the DC-PEEC communication model will require accurate channel estimation and prediction in

75

realtime. To that end, we utilize physical-layer and link-layer side-information (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 DC-PEEC employs LDPC codes for decoding link-layer 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. DC-PEEC 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 DC-PEEC adjusts its parame-
ters as more and more packets arrived during a session. Specifically, 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 one-to-one 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-, DC-PEEC uses channel estimate of the previous transmission interval (ii—1 along with
buffer flags in ACK -_1 to allocate data and parity symbols for Mi- Specifically, DC-PEEC 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 link-layer tolerable delay T. Therefore DC-PEEC 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 link-layer (before it is delivered to the video decoder) is minimized. In summary the objective

is to find 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 efficiently, and

2. reduce the video packet latency at the link-layer obtained in Equation (5.11) to meet the

link-layer tolerable delay T.

To satisfy the first objective, DC-PEEC should allocate minimum number of parity symbols
which guarantee reliable packet delivery. DC-PEEC uses E,- to determine type-X parity symbols
33,-. Let Txi represent the rate of type-X 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, DC-PEEC 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 link-layer 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 find 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(€,-) (5-15)
ki+$i Sni,fii 21
By solving (5.15), DC-PEEC calculates t3; ( minimum value for [3,, fl,- 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, DC-PEEC
allocates 2:,- = [cl-1323" H (Ei) type-X parity symbols and creates a codeword C2-(lci, xi).
According to the DC-PEEC communication model each buffer flag 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, type-Y 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
specified by DC-PEEC. 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
DC-PEEC protocol is utilized. To ascertain the capability of DC-PEEC, 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
DC-PEEC, IEEE802.11 ARQ and HARQ protocols. For the following experiments, all three
protocols DC-PEEC, HARQ, IEEE802.11 ARQ are implemented with OMNET++ network sim-
ulator [105]. We use an Adaptive LDPC (A-LDPC) codes [104] for channel coding operations
in DC-PEEC, Reed—Solomon codes [67] for HARQ, and INET Framework IEEE802.11 mod-

ule in OMNET++ for implementation of ARQ mechanism. The performance measure is Y-PSNR

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=<mwmo[
In case of, frame loss, we use the variance of the pixels to calculate the frame PSNR as follows:

2552
”Yorg — Yorgllg

 

 

YPSNR = 1010910 [

where yorg represents the mean of the values of the original frame pixels and ||.||g is the £2-
norrn. We have conducted the following experiments for all the 15 video sequences listed in

Section 5.1, however for brevity only results for Stefan CIF and Foreman CIF are presented.

5.3.1 Quality Selection

Often in realtime multimedia application (such as video streaming and video conferencing), a
user can choose the video playback quality based on available bandwidth and latency of Internet
connection. As mentioned before, we configure the H.264/AVG JM14.0 codec to achieve uniform
playback quality by setting the quantization parameter (QP) to a specific value for each frame.
Under this setting, QP dictates the number of bits allocated to each video frame leading to variable
bit rate (VBR) video encoding. Accordingly, the sender should deliver video data at or above
particular rate which is specified by the video bitrate. The value of video bitrate determines the
video decoder tolerable delay. Those packets which miss their deadlines are unusable by the
decoder, leading to degradation in video quality.

We setup the simulations based on the realtime video model depicted in Fig 5.1. We use
H.264/AVG IM14.0 codec [106] to serve as video encoder/decoder. The simulation setup is as
follows: A video stream is encoded based on a specific QP value at the sender-side in the applica-
tion layer. The encoded video streams (video packets) are buffered at the sender’s link-layer to be

transmitted over the wireless channel. The DC-PEEC protocol is simulated with the network sim-

80

ulator OMNET++ software [105]. DC-PEEC encodes each video packet using LDPC codes [104]
and transmits the encoded packet over a wireless channel. Each transmitted packet tcr: is distorted
based on the channel traces tr. Specifically, an XOR operation is performed between the trace
packet and DC-PEEC packet: rx = tx EB tr.

The corrupted packet rx is decoded using LDPC. The LDPC decoder uses BER estimates deter-
mined by a channel model trained using previously received packets. If the packet is not decoded
successfully, it is stored in receiver’s link-layer buffer and additional redundancy is requested ac-
cording to DC-PEEC. Otherwise, the decoded video data is passed up to the (video decoder at)
receiver’s application layer. The simulation is terminated when all the video slices are transmitted
by the sender. We repeat the simulation for different video bitrates as governed by different QP
values ranging from 20 to 36. We increase QP by two to obtain nine different video bitrates. We
transmitted the video bitstreams over 12 different channel traces with different BERs. Therefore,
for each video sequence, a total of 168 simulations were conducted. We repeat these simulations
to compute the performances of IEEE802.11 ARQ and HARQ protocols using the above settings.

Fig. 5.5 shows the PSNR values for Stefan CIF 30fps sequence transmitted by different link-
layer protocols over various channel traces. In this figure, the solid line represents the best PSNR
value that can be achieved for each video bitrate. We observe that DC-PEEC and IEEE802.11
ARQ protocols perform well over channels with low BERs in comparison with HARQ. This is due
to low probability of packet corruption which mitigates the need to perform retransmissions (in
case of ARQ) or allocate many parity bits (in case of PEEC). However, since HARQ is not channel
adaptive [44], it allocates a fixed amount of redundancy regardless of channel conditions. As a
result HARQ does not send enough video data bits on time (causing frequent frame losses) and the
degradation in PSNR value. However, as the BER increases, we observe that the performance of
IEEE802.1 1 ARQ decreases dramatically while DC-PEEC manages to achieve significantly better

quality. In particular, we observe 5-10 dB PSNR gains over channels with BER greater than 0.005

81

-. -DC—PEEC -+ ARQ --IDEAL ----- HARQ

 
 
 
  

 

45,. ............. y .............. . ............. ............ ‘ .............. :.
A40? ...............................................................................
m
3 1
m 35 .............. .....
z 1 . a
g3 : f ........ fl

1 30— ....u ,,,,,,,,,,, I, ............ 1. ..... ..

>~ 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 -DC-PEEC -+ ARQ --IDEAL "'IIHHARQ
45,... . .1 .. .... ...... 1.
A40-
CD
3 . _
a : : z
: ' ' ..... fl
0"! 30 ..-ll ......... “a. ......... ....u """"" ..
>1 ..fl ........... 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 figure represents maximum achievable video
quality for each video bitrate.

82

.h.
01

T

.5
O
I

.......................................................................

......................................................................

CD
01

Average Y-PSNR (dB)
(D
O

 

- -DC-PEEC -+ ARQ —-IDE AL -~II--HARQ

 
 
 
 

 

1%0 100 150 200 250 300
Video Bitrate (Kbps)
(c) BER: 0.005

350

.. -DC-PEEC --o- ARQ ——IDEAL ~-n~HARQ

453 ,

A
O

p—

00
U1

 

'0‘
""""""
I

Average Y-PSNR (dB)
(D
O

 

0 100 150 200 250 300
Video Bitrate (Kbps)
((1) BER: 0.01

Figure 5.5 continued.

83

 
 
 
   

...............................................................................

350

Average Y-PSN R (dB)
03

- -DC-PEEC --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
-- -DC-PEEC -+ ARQ —IDEAL ~-n--HARQ
45.... . , ...... ,
A40»
in
E
(I: 35*
Z.
to
“1* 30--
> +
$0
«3 25*
5'3
>
<1:
201. .................... ..............................................
£2 ........... n ------------- a ------------ il- ----------- fl ---------- 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 DC-PEEC which allocates
parity bits based on the end-to-end delay constraint. As a result, DC-PEEC sends sufficient 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 sufficient 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 difficult to achieve for video sequences with scene change where each encoded
GOP has significantly different bitrate. Hence, it is important for the link-layer 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 DC-PEEC 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 fluctuations in frame quality.

To illustrate the impact of these fluctuations on the playback quality of realtime multimedia
applications, Fig. 5.7 provides a sample of five consecutive frames captured from Stefan CIF
sequence. In this Figure, the frame: distortion, freeze and loss are easily identifiable under

IEEE802.11 ARQ and HARQ. This stems from the fact that these protocols are not adaptive to a

85

-e-DC-PEEC 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 fluctuations in

frame quality.

86

 

   

L€Z# awe-H

11
3
,1... «ta Quart-111,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 five consecutive frame captures of “Stefan CIF" delivered by
different error control protocols.

87

 

 

 

 

 

 

-- -DC-PEEC 1+ ARQ —-IDEAL ---- HARQ
40,.9'9W_ ,1.
\‘ .m: :
A $3. 9"---¢- ....... . .
35- 1,1. - 1‘ ’~"'* ---- '
5% :6-9 7 ; : 7
V E I
z N! 1
CD 3 1 7‘
ad: 25,. h..I-I ' ............................
: '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”
- -DC-PEEC -+ ARQ —IDEAL ------HARQ
40_W _ ..... .
1 f
A :\ ~,°"---. ___________ :
@352 .. ...“ .......... ;..... .. ""'0
g Gunner ‘
fi 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 DC-PEEC 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 DC-PEEC maintains the high visual quality. For trans-
missions where BER is more than 0.015, DC-PEEC achieves 10-15dB PSNR gain over HARQ
and IEEE802.11. This result clearly demonstrates the efficacy of DC-PEEC in allocating parity

bits for video transmissions to achieve reliability condition and meet end-to-end 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 traffic flow at
the wireless link-layer. Using this model, we introduced DC-PEEC, an error control protocol for
wireless link-layer which deploys various channel codes to ensure the delivery of video packets
in a timely fashion while efficiently utilizing channel bandwidth. In particular, DC-PEEC 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 5-10dB for different realtime video scenarios. In the
next chapter, we pursue a paradigm shift where both reliability and stability are ensured at the
underlying link-layer. We investigate the feasibility of designing stable and reliable link layer
over point-to-point (single-hop) 802.11 channels; and more importantly we study the feasibility

of achieving significantly improved throughput by using this type of link-layer.

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 traffic types with various requirements for rate, re—
liability and delay. The wide variety in traffic rate requirements leads to a large variance in the
traffic volume injected into the network which often leads to throughput instability. This is ex-
acerbated due to errors introduced in the wireless network. Leading link-layer 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 flow control for both realtime
and non-realtime traffic. 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 overflows. More specifically, the current
link-layer paradigms aim at providing reliability in hop-to-hop communication without regard to
traffic demand. One outcome of failures at the link-layer, 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 transport-layer 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 traffic demand and intensity. This design strategy has led to a great deal of
inefficiency in throughput and to other major technical issues and challenges at higher layers. A
well—known example is the T CP over-wireless 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 link-layer protocol. The proposed wire-
less ACE link-layer (a) employs a theoretically-sound framework and a corresponding strategy
for embedding channel codes, using robust and well-defined 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 first to present a theoretical framework for

91

analyzing and designing a wireless link-layer 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. Specifically, we first 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 link-layer failures as an on-off
source model using a two-state Continuous Time Markov chain (CTMC) model. We deploy fluid
approximations to analytically characterize the buffer growth. By utilizing these models, we find
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 traffic demands (in terms of reliability and stability requirements) can be met using a
packet-by-packet code embedding rate constraint that is independent of traffic type. This leads
to simplistic, traffic-independent and elegant design rules for the ACE protocol, while providing
reliability and stability in an optimal and joint manner.

The ACE protocol is a point-to-point 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 flags 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 packet-by-packet code embedding rate that is independent of traffic type.

0 We propose the ACE protocol for point-to-point link-layer 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 finding 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 = [CZ-lei.

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. Specifically, 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 error-correcting capability of a particular decoder. For example,
the error-correcting capability of Reed-Solomon 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 a-error 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
link-layer protocol. The first 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 identifies 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 define

reliability as follows:

Definition 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 satisfied:

(’67: + l‘flez' 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; + 2131-5 717;.
This leads us to find 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 error-correcting 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 significant in audio/video conferencing if data packets are

not delivered in a timely fashion. The wide variety in traffic rate requirements leads to a large

96

gr-——Link-||layer————

ACE £1115)
“Decoder
Higher

:: b. Buffer Length] Layer

        

Figure 6.2 System model for stability analysis in wireless Communication.

variance in the traffic-volume injected into the network. This often leads to throughput instability.

We define stability as follows:

Definition 4. System is stable when higher layers are neither starved for information packets nor

is there a glut of packets leading to buffer overflow

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 non-empty to avoid execution stalls. This property
is satisfied 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 fluctuations of the buffer growth can be captured by computing limiting distributions of
the buffer length using a general model of fluid 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 fluid in the buffer at time t. In our framework,
Z (t) indicates the decoding outcome in the link-layer (later, we model Z (t) as a two-state 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 fluid 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 defined as:

F(b1j)=t_1}$OOP(B(t) S b1Z(t) S j)- 1S j S M (6.6)

By defining:

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) satisfies 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 gher-layer viewpoint, Z (t) the decoding process in the link-layer, can be expressed
as an on-off fluid source model. Such a source stays on for an exp(w) and stays ofir for an erp(,8)
amount of time. It generates fluid at rate k,- when it is on and does not produce any fluid when it

is ofi’. Accordingly, a successful decoding at the link-layer 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 ofir is ,8,- = 1 — “’2"
Using the on-ofi source model, the environment process Z = {Z (t), t _>_ 0} in equation (6.5) is

modeled as a two-state 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 final 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 finite capacity, the following

condition has to be satisfied to prevent buffer overflow

< c. (6.11)

Using this model, we determine the lower bound on operational code embedding rate under

ACE that satisfies the stability condition. This is given by the following Lemma:

99

0.95

 
    

Unreliable Region

C

RI
V? 5‘
Stability

Reliability for a-Error 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<<a
Proof. See appendix. El

Lemma 2 suggests that for the channel in state 3,, stability condition is guaranteed for a variety
of traffic demands using operational code embedding rate of at least R, = 1 — Earl. Meanwhile,
Lemma 1 suggests that this rate is the upper bound of operational code rate which achieves re-
liability. As illustrated in Fig. 6.3, the domain of operational code rate is partitioned into two
subdomains which intersect at R, = 1 — $171. Further, this domain is bounded by the channel cod-
ing theorem [55] which requires the operational code embedding rate to operate below channel

capacity of equation (3.11) (R,- < C). An important conclusion of this analysis is that an opti-

100

ma] solution for code embedding rate that ensures reliability and stability conditions is a unique
solution:
R; =1— 51. 5,- << a (6.12)
a

This conclusion leads to simplistic, traffic independent and elegant design rules for the ACE

protocol, while providing reliability and stability in an optimal and joint manner.

6.3 Automatic Code Embedding

In this section, we present the architecture design and implementation of ACE which uses the op-
timal code embedding rate deduced in the previous section for redundancy allocation and deploys
channel side information to assess an accurate estimate of the channel condition in every trans-
mission. To that end, we first describe a point-to-point communication model under which ACE
is operating. Next, we present detailed functionality of ACE, specifically channel state estimation
and redundancy allocation.

In this section, we describe ACE operational communication model. Here a transmission inter-

val Ti is expressed as the duration in which a transmitter sends the ith

message (packet) M,- and
receives its corresponding acknowledgment ACKi. A transmitter sends a new message after the

reception of an acknowledgment.

Sender Side

During 72-, a sender transmits a message which is represented by the tuple M,- = (CZ-(hi, xi), 3’2")
where it,- represents the number of data symbols which are not being retransmitted. In each Ti, a
transmitter encodes k, with parity symbols :12,- creating a codeword Ci(k,-, 33,-). We refer to these
parity symbols as type-I parity. The receiver utilizes :13,- to decode Ci. Upon successful decoding,

C,- is extracted and k,- data symbols are passed up to the higher layer. The error correction fails

101

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
(type-II) parity symbols denoted by yi. The receiver utilizes y,- symbols to recover old corrupted

codewords accumulated in its buffer (e.g., Cj, j = 1, - . - ,i — 1).

Receiver Side

We assume that the receiver has a finite buffer which can accommodate up to m corrupted mes-
sages waiting for recovery. If a newly corrupted packet finds 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 flags in an acknowledgment message which are called buffer flags. Specifically, m flags
are encapsulated in every acknowledgement. Let Fi[k], k = 1, - - ~ ,m represent buffer flags in
AC K 7;. Each buffer flag 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 F2111] = 1 (as illustrated in Fig. 6.4). In ad-
dition, the receiver estimate of channel condition 5,- in 7',- is also encapsulated in acknowledgment
message. Later, we describe channel estimation process by the receiver.

An example of ACE operational communication model is illustrated in Fig. 4.1. A short com-
munication consisting of four transmission intervals and buffer capacity of two at the receiver is
shown. During the first transmission interval 7'1, a message M1 = (01011, $1),y1) is sent. There
are no type-II parity symbols in M 1, because there is no prior corrupted message in the receiver
buffer, so y1 = 0. A receiver that fails to decode C1, stores C1 in its buffer and sends an ac-
knowledgment ACKI = (1, 0, 51). In rg, the transmitter sends Mg 2 (Cg(kg,:cg),yg = {y%}).
The receiver uses mg to decode Cg and employs type-II parity symbols y% (y'ij denote additional
parity for CJ- , j < i transmitted in Ti) in addition to :51 to decode 01- The receiver acknowledges
ACKg = (1, 1, 5g), indicating decoding failure of Cg and Cl(k1,a:1 + 31%). As a result, in T3,

the sender sends M3 = (C3(k3,:r3), y3 =2 {3%, y§}). In T3, the receiver successfully decodes

102

 

 

 

 

Transmitter

 

  
 

Receiver

 

 

X :
/ Decoding Achieved .

X Decoding Failed

_eceiver
_ulfer

m-ype-X Type II
P_rity Parity

 

 

 

 

Figure 6.4 An example of ACE operational communication model consists of four transmission
interval.

C3 using 1153 and 01(k1, :51 + 31% + 31%). Because decoding of 01 was successful, the receiver sets
the buffer flag of the first room to zero (i.e., F3[1] = 0) but at the same time since the receiver is
waiting for type-II parity symbols to perform decoding on Cg, the buffer flag for the second room
is set to one (i.e., F3[2] = 1); so ACK3 = (0, 1, 53). Accordingly, in T4, the sender transmits
M4 = (C4(k4, x4), y4 = {y2}). The receiver decodes C4 using $4 and Cg = (kg, 11:2 +3132) +342)
successfully; so ACK4 = (0,0, 34).

The model described above represents ACE operational communication mechanism. In the
following section, we describe the functionality of ACE protocol in estimating and adjusting the
amount of necessary redundancy in every transmission under the delay constraint imposed by the

application to achieve high performance.

103

 

6.3

AC
10'

of

{61

6.3.1 ACE Protocol

ACE utilizes the receiver channel estimate and buffer flags to assess the status of the channel
condition and the receiver buffer. Depending on this assessment, ACE determines the composition

of the next message to be transmitted by the sender.

Channel State Estimation

Recall that the Markovian channel model implies that in every transmission interval 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 an accurate estimations of BER values for each state of the
model. The training process is in an online fashion in the sense that ACE adjusts its parameters as
more and more packets arrived during a session.

There are many ways to predict channel BER. One example is to use readily available infor-
mation in the received packet. ACE uses Signal to Silence ratio (SSR) as side information in
every transmission interval. Specifically, upon a reception of a packet in transmission interval
Ti, the receiver obtains the SSR and estimated BER values of packet preamble. We let ssrz- and

A

D .

z = g(ssr,~) represent the SSR value of packet M,- and its corresponding estimated BER re-

spectively. A receiver creates a one-to-one mapping between each SSR value and each state of
a Markov chain [i.e., (3er E 51), - - - ,(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 ssri and D,- of the received packet in T2".

2. Find a state where S,- E 557i

3. Add Di to the list of observed BER values associated with (ssrz- E Si): Az- = {A23 Di}-

104

4. Adjust the BER estimation associated with state S,- by taking the average value of the up-

dated Ai
lAz'l * .
2 lAz'l

 

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.

Redundancy Allocation

In Ti, ACE uses channel estimate of the previous transmission interval (1,-_1 along with buffer
flags in ACKZ-__1 to allocate data and parity symbols for Mi. Specifically, ACE uses (1,-_1 as its
estimate of the channel BER in current transmission interval Ti; so éz- = (1,-_1.

According to the communication model each buffer flag in the acknowledgment message
(F-_1[j] j = 1, - - - ,m) indicates the status of a particular room in the receiver. ACE first al-
locates the amount of type-II parity symbols (yi) necessary to transmit based on the buffer flags.
If 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 Th1 k < i which requires additional
redundancy symbols for recovery. According to optimal code embedding rate obtained in Sec-
tion 6.2, Ck with length "is requires a at most Tik = Egg-i parity symbols for error recovery.
However, for Ck, :1: k + Zl;llc+1 ylk parity symbols are already transmitted in the previous trans-
mission intervals Tk, - - - , rz-_1. Thus, type-II parity symbols necessary to transmit in r,- for Ck is
91k: Tik ’ “’k + Z1:11c+1 yik'

ACE protocol requires that each message must have a fixed length 71. After allocating type-H
parity symbols for corrupted codewords, ACE has 77.,- = n. — 2k yzk symbols to transmit a new
codeword C2-(ki, 33,-). The amount of parity symbols necessary for encoding C,- is :23,- = 2152,, and

therefore the amount of new data in C,- is k,- = n,- — 55i-

105

The transmitter constructs a message M,- according to the message distribution specified by
ACE. This distribution is adaptively computed in every transmission interval based on the channel
and the receiver buffer conditions while it guarantees to satisfy the stability and reliability con-
ditions. Therefore, the overall performance increases when the ACE protocol is utilized. In the
next section, we conduct extensive performance evaluations of ACE through simulations under

varying operating requirements.

6.4 Performance Evaluation

In this section, we present extensive performance evaluation of the ACE protocol using real chan-
nel traces collected on an 802.11b WLAN. First, we compare the performance ACE protocol as
opposed to the conventional IEEE802.11 ARQ protocol on realtime and non-realtime traffic. Sec-
ond, we analyze the impact of deploying ACE in the link-layer on the traditional TCP throughput.
Finally, we illustrate the quality of real-time video communication in terms of PSNR gain under

ACE and IEEE802.11 ARQ.

6.4.1 Realtime 'h'affic

An important aspect of realtime traffic delivery is to prevent instability (by delivering information
in timely fashion) while ensuring the required reliability. To determine the impact of deploying

ACE protocol on stability for realtime traffic, we introduce the following parameters:

0 Consumption rate: This parameter determines minimum number of data symbols required
per second to ensure stability for realtime traffic. This rate is determined by the delay
constraint imposed on the realtime traffic. During a particular session, the rate of correct

information delivery must satisfy the consumption rate to guarantee stability.

106

0 Expected stability: This parameter measures the time period during a particular session that

the traffic delivery is stable (see definition of stability in section 6.2.2).

For lower consumption rate, it is more likely that the traffic will be delivered to the upper layers
on time and therefore avoid instability. However, as the consumption rate increases the likeli-
hood that the upper-layers do not receive the packets in a timely fashion increases. Ultimately,
if the consumption rate exceeds the sender transmission rate, then the traffic never reaches the
destination on time and therefore the system becomes constantly unstable. The expected stability
declines significantly as the consumption rate reaches the sender transmission rate.

To measure impact of the ACE protocol on expected stability, we use network simulator OM-
NET++ [105] to incorporate the ACE protocol in the current IEEE802.1 1 MAC layer. Specifically,
we utilize the INET Framework package and modified the link layer (Ieee8 02 . 1 1Nic mod-
ule) to add the ACE protocol. We also incorporated A-LDPC [104] into the software for embedded
coding operations. The simulation setup is as follow: we let a sender transmits a codeword. We
use our channel traces to distort the transmitted codeword by flipping distorted bits. The receiver
uses A-LDPC to decode the received word and checks whether the decoded word is a valid code-
word. 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, ACE uses its estimate for channel BER for every transmission
interval described in Section 6.3.1 to decode each packet. For this experiment, the maximum iter-
ation is 100; the variable side has degree three and the check side degree is approximately regular.
Upon successful decoding of a packet, the header of the packet is extracted and the payload is sent
to the upper-layers. To simulate the delivery of realtime traffic, the consumption rate is set at a

range of 100 to 1300Kbps.

107

- + - IEEE802.11 ARQ -I- ACE

A
I

   
         

T

I

.099
VCDCO
I

F3
o:
.'

I

..............................................

j

Expected Stability

p _o _o _o p
_. to a: I: 01
I

r

 

 

       

C
1

 

200 400 600 800 1 000 1 200 1 400

Consumption Rate (Kbps)
(a) BER: 0.001

O

- + -IEEE802.11 ARQ-I-ACE

 

0.9
0.8

T

..............................................................

I

E 0.7- --------- 1 ........

..........................................

:6 0.6
43

C005
F8 0

8 0.4
o.
X 0.3-~

T

F

0.2PHH

 

 

0.1- ......... .......... ........... ........

0 200 400 600 800 1 000 1 200 1 400

Consumption Rate (Kbps)
(b) BER: 0.005

Figure 6.5 Expected stability of realtime traffic with respect to variation of consumption rate over
different channel traces. The vertical line in each figure represents the sender transmission rate.

Fig. 6.5 illustrates the variation of expected stability over various channel traces. We observe

that the IEEE802.11 ARQ performs slightly better that ACE over channels with low BERs (less

108

- . - IEEE802.1 1 ARQ -- ACE

   
         

 

 

 

   

 

 
      

 

 

1..
a“
0.9- 1 ~
08- ’1
5’. 0.7- \31.
'3 0.61 1’... ..................
<73 ‘1
'8 0.5.. .................... . .....
’8’ 0.4»
Q.
>< 0.3"
Lfl
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 sufficient 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 significantly 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 traffic 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 figure, 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 on-Realtime 'h'affic

The main objective in non-realtime traffic 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 efficiently.

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 non-realtime traffic

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 figure 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 flow 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 slow-start 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 link-layer 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 fix TCP over-wireless performance degradation phenomenon. We
argue that since ACE is designed to guarantee stability as well as reliability at the link-layer, 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 finite 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 overflow of the
bottleneck router. (2) AP-based 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 link-layer which causes AP buffer overflow. (3) distortion-based loss: A
broadcasted packet over the wireless channel gets corrupted due to wireless noise. This packet is

not retrieved due to link-layer 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 type-I 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 type-II 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,Bg-1,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 coefficient 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 282-1 783)

(mr821B3-1)

 

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—per-second 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) defines the maximum number of unacknowledged data outstanding in the
network at the sampling time instant t and T represents the round-trip 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 error-free. 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 type-I
parity symbol fails. Therefore, finding p is equivalent to computing the expected rate of decoding
failure using type-I 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 type-I parity bits. Then, the event A, 2 {Di > aXi} indicates the decoding
failure of a packet using type-I parity bits where a is an error-correcting 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 type-I
parity with additional type-II 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
type-I and type-II parity bits. Let Yz represent the type-II 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 7rz-Pr(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: (mug-1+5) + p <E[W3] + 7113) . (6.22)
i=1 2

where E [Wii is the average time that a packet spends in 622' is as following

 

 

B-+1
E[W-] — i “i — (Bi + 1)a,- 2 (6 23)
2 _A, 1—6, 1_aB,;+1 , -

i
where — J)“

a . — o

7. [ii

In this system, a loss occurs if a particular packet in the system is blocked by one the queues.

Correspondingly, the steady state loss probability is

1
«L083 = Til—WT (Em/1n Bl + E[W2]7r32 + E[W3]7rB3), (6.24)

119

where
B2 33

W31 = Z ZWBl,m,l (6.25)
n=1l=1

B1 B3

«32 = Z 2%, 32,1 (6.26)
m=1l=1

B1 32
«B3 = Z Z ””333. (6.27)
1

m=1n=

In this section, we presented a queueing system that captures the behavior of packet flow in our
network scenario. We determined the steady state packet loss of this system when ACE is used
as an underlying error control protocol in wireless link layer. In the next section, we model our
network scenario under IEEE802.11 ARQ scheme and we drive the steady state loss under this
protocol. In the sequel, we will comparatively analyze the impact of different parameters on the
loss behavior under ACE and IEEE802.11 ARQ schemes and finally we observe the impact of

loss on the overall TCP throughput.

6.5.3 System Model under IEEE802.11 ARQ

IEEE802.11 is a de facto wireless MAC protocol designed to ensure reliable transmission in wire-
less channel: it incorporates frame check sequence (FCS) to detect errors and automatic repeat
request (ARQ) to retransmit corrupted packets. The IEEE 802.11 link layer discards corrupted
packets with no regard to the number and location of the errors. The IEEE802.11 ARQ mecha-
nism request for a retransmission of a corrupted packet until it reaches the maximum retransmis-
sion limit (M TL). If an error-free copy of a packet is not received by then, it discards the packet
and labels it as lost.

Fig. 6.10 illustrates queuing system for our network scenario under IEEE802.11. Notice that
unlike our model for ACE, this system comprises only two queues which represent the router

and AP buffer. Similarly, to derive the steady state loss in this system, we should compute the

120

 

 

Router Buffer AP Buffer Higher
Layer

Figure 6.10 A system of queuing network for the heterogenous network under IEEE802.11 ARQ
protocol.

 

joint steady distribution of Q1 and Q2. Let Xi(t) denote the number of packets arrive at the
in i = 1, 2 at time t. Then, X(t) = [X1(t), X2(t)] is a Markov Chain whose transition rates

are x\, #1 and #2. The stationary distribution of X(t),
= l' P X t = X t =
rm,n H1300 7'{ 1() m, 2() n}.

is computed by forming the balance equations for different states of X(t). The complete list of
balance equation of this system is presented in Appendix.

Before solving the steady state balance equations it is necessary to compute the arrival and
service rates in the queueing system. The anival and service rate of Q1 is given in Equation 6.15
since Q1 represents the router buffer which its rates are characterized by wired network and is
identical in both models. However, the service rate of AP is a function of IEEE802.11 ARQ
mechanism. Let d represent the tolerable delay of every transmitted packet at the receiver side.
According to IEEE802.11 mechanism, this delay should be at most MTL. (i.e., d S M TL). We
let event Y represent a successful delivery of a particular packet and recall q is a packet error rate
in every transmission interval under our wireless channel model. Under IEEE802.11, a particular

packet is successfully delivered if it is errorless in the first transmission or in any of consecutive

121

d — 1 retransmissions. Thus the expected number of successful delivery is
d .
Em = Z g"1(1— c). (6.28)
i=1

The service rate of AP buffer is equivalent to the expected rate of successful delivery. Thereby,

d Ci—1(1_ C)
#2 = E [E[S|Y]] = Z W' (6.29)
i=1

Once the transition rates are computed, we form a system of linear equations similar to Equa-
tion (6.14) where II = (”111’ - -- ,7rm,n,7rBl,Bz) and A is a L x L coefficient matrix with
L = Bl x 82 constructed by transitions rates given in Equations (6.15) and (6.29).

By solving this system of equations, we can determine the steady state distribution presented in
a vector 11. Accordingly, the average time that a particular packet is in the system is

2 1
Em»....1=:(6w.1+_)
._ Iii
z—l
where E [Wt] is the average time that a packet spends in Qz- and is computed using Equation (6.23).
The steady state loss probability captures the proportion of time that a particular packet is

blocked by any of the queues in the system. Thus

1 7
«L088 _ m (Em/11631 + E[Vl2]7rB2) ., (6.31)
where
32
7rB1 = Z n31”, (6.32)
n=1
31
n32 = 2 «WE? (6.33)
m=1

6.5.4 Analytical Performance Evaluations

In this section, we comparatively analyze the impact of ACE and IEEE802.11 ARQ scheme on the

overall performance of our network model. We measure the performance in terms of steady state

122

High Congestion

 

 

 

 

    

Low Congestion

0 1 2

Figure 6.11 The state space of traffic intensity in wired network.

 

throughput 7r7- which is the fraction of packets successfully transmitted to the receiver: 7r—r = l —
"loss- In the proposed network model, two critical factors overshadow the overall performance:
(1) traffic intensity in wired network, (2) the overall condition of wireless channel. The traffic
intensity in the wired section dictated by the TCP sender transmission rate and the wired link

average capacity (i.e., A and n1) governs the existence of congestion-based loss, where as the

channel condition imposes the level of corruption in the transmitted packet.

Congestion Likelihood Classification

Let us assume that the transmission rates and link average capacity are normalized (0 S A, [11 S
1). Figure 6.11 shows the state space of traffic intensity in wired network based on the values of

A and ill. According to this space, the likelihood of congestion occurrence in wired network can

be categorized in following regions: (1) Low congestion: where % S 1. (2) High congestion:

A
where #1 > 1.
The congestion likelihood region specifies traffic 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 Gauss-Jordan 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 figure, 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)
-O-ACE(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)
-O-ACE(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

significant 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 simplification, the equilibrium throughput is
A 2(1 — 8) 1
= . — 6.35
x 5 T ( )

which is a well-known 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 link-layer. 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 link-layer. 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 Congestion-based

126

- + -IEEE802.11 ARQ-I—ACE
1100-“.H.H...nh.fl.hn .HH,.HMHV.H“”_H..HHHH.,H

 

 

1000?’ ............... E .......... _ ....... E ................... E ....................
fir 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 4m-H1: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 ARQ-I-ACE

 

 

 

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,.‘,.
E-4 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 link-layer. The horizontal line in each figure represents the transmission rate of the
corresponding channel trace.

losses are observed in the wired section. Meanwhile, significant throughput difference is easily
identifiable as the channel BER increases. For instance, TCP gains throughput of 10% to 50%

(e.g., ACE achieves 500-800Kpbs 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»-
E-1
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-
E-1 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 significant difference stems from the fact that

ACE targets stability and reliability of wireless communication. This lead to fewer AP-based and

distortion-based losses in wireless section under ACE in comparison with IEEE802.11 ARQ.

128

 

— + -IEEE802.11 ARQ-I-ACE

 

 

 

 

 

 

 

 

 

1100,..- .
”c?
a.
.o
5
4.3
:1
o.
.1:
60
:1
o
H
.:t
E-4
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 real-time

129

h
C
1

<3

00
o
r
‘9

 

Average Y-PSNR (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 Y-PSNR (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 figure 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 ARQ-I-ACE

A
0
fl

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 Y-PSNR (dB)

 

- + -IEEE802.1 1 ARQ-I-ACE

 

 

 

CD
01

0)
0

Average Y-PSNR (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 A-LDPC
codes [104] and transmits the encoded packet over a wireless channel. Each transmitted packet is
distorted based on the channel traces. Specifically, an XOR operation is performed between the
trace packet and ACE packet. The corrupted packet is decoded using A-LDPC. 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 frame-freezing or synchronization mismatches during real-time 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 specified 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 Stefan-CIF (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. Specifically,
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 5-10dB 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 link-layer protocol has been
proposed that (a) employs a theoretically-sound framework and a corresponding strategy for em-
bedding channel codes, using robust and well-defined 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 link-layer is achievable.
Our extensive analysis of ACE protocol over real channel traces collected on 802.11b WLANs
for realtime and non-realtime traffic, TCP throughput and realtime video communication scenar-
ios show that ACE significantly 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 flows in wireless networks.

134

'1'

CHAPTER 7

PACE: A Prioritized Wireless Link Layer

To achieve superior link-layer wireless communication one need to target the following critical ob-
jectives: (i) achieving sustained traffic stability (maintaining continuous realtime flow under delay
constraints), (ii) ensuring maximal reliability and throughput, (iii) exploiting side-information 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 link-layer communication with various requirements
in rate, reliability, and delay. However, achieving these objectives simultaneously is a difficult
task since they have conflicting requirements. In our prior work [2], we have demonstrated the
feasibility of designing stable and reliable link-layer under Automatic Code Embedding (ACE)
framework over point-to-point (single-hop) 802.11 channels. However, what is ultimately needed
is a comprehensive framework that targets all of the above objectives (stable-and-reliable commu-
nications, exploitation of side information, and interaction with the higher layers) jointly.

In recent years, various decoding schedulers [88-90] have been proposed to improve the overall
throughput in wireless link-layer 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 slow-fading wireless environment. Under such assumptions, a de-
coder scheduling scheme only attempts to balance the quality of service for heterogeneous traffic
requirements. This design strategy only targets quality of service and largely ignores the other
objectives of wireless link-layer 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 flows in wireless networks. Under the
proposed Prioritized ACE (PACE) framework, our ACE based stable-and-reliable1 link-layer will
employ a novel rate-adaptive 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. Specifically, we develop a LDPC decoding model to capture the decoding
process for link-layer traffic and use it to determine an optimal code selection strategy for max-
imal bandwidth utilization. Further, we find an optimal code embedding rate under the PACE
framework to jointly meet the reliability, stability, and delay constraints of the wireless link-layer
communication. We classify heterogeneous link-layer traffic arrivals into different priority classes
based on packet delay constraints and the distortion suffered. The traffic arriving in each prior-
ity class is modeled as a poisson process. Consequently, we formulate the link-layer 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 link-layer
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 definitions 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 error-correcting capabil-

ity from an ensemble of codes.

0 Model the link-layer 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 link-layer traffic.

7 .1 Illustrative Example

In this section, we briefly 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 first and the last packets (K 1 and K 4) are non-realtime. That is, impact of the delay in de-
livering these packets to a higher layer is insignificant 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 end-to-end delay constraint, oth-
erwise they are unusable for the application (e.g., realtime video packets). The wireless channel
condition is gradually improving. Specifically, 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 finally the

channel is error-free 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

 

   

 

 

lK1|X1HK1IK1I 1K1 1...] | K2 lle

C1(K1’x1)5 C1(K1’x1) C1(K11X1)E C2(K2,x2)

(b) HARQ

 

 

 

.---.1I-.-----..-.-.----.I

---..(booocconccc
--.-ocuocucucoucococu.---no-1
1—
CD
ITI
I!
ll
.0
O
0
0|
1;]

 

 

 

Figure 7.1 A wireless link-layer 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

 

     

POO-------OW03-Ccoccd

    

 

 

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 non-zero in the first three transmission

intervals, the odds of receiving an error-free 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 non-zero, 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 non-zero. In 7'4, K1 is finally 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 time-slot 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 error-free 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

significantly 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 type-II 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 type-II 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 type-II 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 type-H 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 efficacy of PACE in improving throughput-delay performance
in wireless link-layer 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) efficient 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 significant 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 insignificant 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 link-layer traffic 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 link-layer traffic using LDPC codes; (ii) Buffer model which
describes the link-layer 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 link-layer 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
_ (m-l) 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 cross-over 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 cross-over 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,- type-I parity bits. Correspondingly,
the receiver attempts to retrieve ki data bits by utilizing at,- parity bits embedded in the received
packet Ci- Specifically, 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 error-correcting 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 error-correcting 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 configured such that the number of iterations m and the degree of variable nodes dv
are predefined 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 error-correcting 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 error-correcting 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 specific protocol or application
in the higher layers. Depending on the type of the protocol or application, the packet is confined
to a specific delay constraint. In addition, the packet contains a certain level of distortion due
to the impact of wireless link-layer transmission. Under the PACE framework, each packet is

classified into a specific priority class based on its delay constraint and distortion. The PACE

144

receiver then attempts to serve a specific 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 first 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 link-layer 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 finite set FN with length N: e,- 6
FN, ”Ni 2 N. In [2], and specifically 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 type-I
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 type-I 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 confined to a specific 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 classified 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 type-II
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 type-II parity bits. The probability of successful recovery of a particular
packet increases as more type-II 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 (type-I and type-II) 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) ifdj-t>0 (7.10)

0 otherwise
The service rate of priority class l is the expected value of the density function féflt). That is,
i if dj — t > 0

uz=Elflg(t)]= Pi (7.11)
0 otherwise

146

According to Equation (7.8), the traffic 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 classified 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 find an optimal dynamic decoder scheduling

policy for PACE.

147

 

Receiver Freedback

Buffer Flags

 

 

 

 

 

 

 

 

 

 

 
   

 

PACE Scheduler I

 

 

PACE Classrfier LDPC Decoder

   
 
  

 

 

 

l
Channel State Estimation l-l

 

'____...._____<__-_

 
 
 

 

 

 

Side-Information 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]. Specifically, in Fig. 7.3, the dark-colored compo-
nents in sender and receiver sides are those components that are either added or modified 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 first component is Channel
State Prediction where the link-layer wireless channel condition for the next transmission interval
is predicted based on the receiver feedback. Specifically, 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 type-II 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 find 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 link-layer traffic 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 finding

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,-<<a
a
where a is error-correcting capability of a decoder.

Proof. See Appendix. [:1

Lemma 2 determines the optimal code embedding rate for a general decoder with error-
correcting capability (1. However, the LDPC decoder model selects a code (when the channel
BER is 6,) with a error-correcting capability close to a* (6,) computed in (7.5). In practice, PACE
uses of“ (6,) to measure the expected error-correcting capability of the LDPC soft decision. This is
so since PACE sender uses é,- as an estimate of the expected error in the next transmission interval

7,. Therefore, an operational optimal code embedding rate for parity allocation is

z . (7.15)

 

PACE first determines the amount of type-II parity bits (yzk) for a particular codeword Ck

transmitted in some 77,, k < 2'. According to Equation (7.15) Ck with length ”k requires at most

k_.

n E,- . . 1-1 is . .
zz. — 5&2? parity brts for error recovery. However, for Ck, 2: k + Zl=k+1 y, parity brts are

already transmitted in the previous transmission intervals 77,, - - - ,r,-_1. Thus, type-II parity bits
necessary to transmit in r,- for Ck is y? 2 22h — :1: k + 23;}: +1 31;“.

After allocating type-II parity bits for codewords in the PACE buffer, PACE has n,- = n-Z k y:-C
bits to transmit a new codeword C,-(k,,2:,-) where n is the maximum number of bits that can
be transmitted in a packet. Similarly, the amount of parity bits necessary for encoding C, is
2:,- = (3218,77, and therefore the amount of new data in C,- is k,- = n,- — 22,-. The PACE sender then

transmits a new codeword along with the additional type-II parity bits in a new link-layer packet

denoted by M, = [C,-(k,-, 23,), y,] to the receiver.

150

 

7 .3.2 PACE Receiver

Upon the reception of the link-layer packet M,- = [C,-(k,-,2:,-),y,], the type-II parity bits are
extracted and sent to the receiver buffer. PACE receiver first attempts to decode a codeword
C,(k,-, 23,-) with type-I parity bits 2:,. If the decoding is successful, the data bits k, are sent to the
higher layer. But if the decoding fails, then the codeword is sent to the receiver buffer for future
recovery.

Under the PACE framework, each packet is mapped to a specific priority class based on its
delay constraint and distortion suffered. The PACE receiver then attempts to serve packets with a
specific priority class according to dynamic decoder scheduling rules. The Classifier and Sched-
uler components in Fig. 7.3b implement the packet prioritization and dynamic decoder scheduling

policy in the PACE receiver.

PACE Classifier

Consider a codeword C,- (k,, 23,) was transmitted over the channel with state S,. Let d j represent
the delay constraint of the packet with the distortion level E,. The PACE Classifier assigns this
packet to a priority class I based on the parameters dj and E,- using a classification function

g : [i,j] —-> 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 error-correcting 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" Specifically,

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 coefficients.

The PACE Classifier first computes the penalty weight for each packet stored in the PACE
buffer. Specifically, 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 Classifier

classifies 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 fluid analogy in which fluid 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 fluid level of class 1 in the
buffer is N [(25) at time t, then the oldest fluid of that class arrived 9%? time units earlier. Thus

the fluid 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) defined 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 significance) 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 traffic condition.

In this section, we described the functionality of the Classifier 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 link-layer 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]. Specifically, 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 first show the impact of throughput-delay tradeoff on the performance of each protocol. Then,

153

 

we measure the performances of a realtime video and a non-realtime TCP applications in con-
junction with these link-layer 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 (A-LDPC) codes [104] for channel coding operations in PACE and ACE,

and Reed-Solomon codes [67] for HARQ2.

7.4.1 Throughput-Delay Tradeoff

The throughput-delay 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 link-layer

protocol performance. We define the throughput-delay 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 throughput-delay 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 definition tn = t — to. In Fig. 7.4, we show the throughput-delay cost ((tn) for
each protocol with respect to the packet delay tn over six different wireless channel conditions.
Specifically, 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. Reed-Solomon
codes are known to be Maximum Distance Separable (MDS) codes and therefore used in HARQ
protocols.

154

-0—PACE - --ACE nun-HARQ --.- ARQ

 
 
 

..............................................................................

Throughput-Delay 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 throughput-delay cost with respect to the packet delay over different
channel traces.

155

 

—I-PACE - - -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 1-u-HHARQm- 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. ; : . . .
l-a .l'l'hh l 111iIriuurirr'iilinlliuli1111‘11111111}, ? f '
g 0.31- 1'+‘-'=.!-I.-ud_ ..... ..... 3""‘f’u‘fl'lfifiifilna‘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 . . . . . . . . .
-

Throughput-Delay 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" ' ' 'fi'gllu'. ' . . . . . .
‘ "'“HllhllllllllilllllllflllllllPHllllll)lllllll
" ' T . f . '7’1
5L...... ‘~. ........ ; ........ r ........ : ........ :. ..... .’ o, ...........
~~~~--- I,

 

Throughput-Delay Cost

9
fit
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 error-free 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:5991t1r991etsflert........, 119190931. ““°° ..---'
(()) ”... Receiver
Cha 6‘

  
 

Wired
Network

 
  
  

Access ‘59 altime Tra
Point ‘.~~. ’afiic

W1

ire/ass Chan" e I

TCP Application
Sender

Router

Realtime Video
Sender

Figure 7.5 Simulation setup where heterogeneous traffic is generated by non-realtime TCP and
realtime video flows.

delay cost for IEEE802.11 ARQ does not reduce significantly 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 significant 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 throughput-delay cost.

7 .4.2 Realtime and Non-Realtime Application Performance

In this section, we evaluate the performances of a realtime video and a non-realtime TCP applica—

tions in conjunction with PACE, ACE, HARQ and IEEE802.11 ARQ protocols at the link-layer.

158

 

Fig. 7.5 illustrates the simulation setup of this section. Specifically, 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 traffic both are redirected to the receiver by the access point (AP). Using OMNET++ INET
framework, we implemented this simulation setup for each link-layer protocol. Specifically,
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 Y-PSNR. Y-PSNR 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 figure 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 error-free 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 efficacy 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,, ~~~ : ‘;~.: fit
CD 3 I "1' ”\:$““‘l"l ‘s ' fi‘ 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 non-realtime 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 significantly. 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 Y-PSNR 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 significantly 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 link-layer com-
munication. We developed a LDPC decoding model to capture the decoding process of link-layer
traffic and the PACE Buffer model to describe link-layer 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 link-layer traffic. We showed experimentally that
PACE significantly 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 inefficiencies of cur-
rent wireless link-layer protocols and pursued a paradigm shift in the conventional 802.11 link-
layer design. We developed a new link-layer framework to overcome the shortcomings of current
link-layer standards and to provide both the reliability and stability for point-to-point contention
free wireless communication. Using this framework, we introduced four link-layer protocols:
1) PEEC, a link-layer 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) DC-PEEC, an
extension of the PEEC protocol that targets the flow control of realtime video traffic in addition
to reliability in wireless communication. DC-PEEC adjusts its parameters to provide low-latency
communication to satisfy the delay constraint (provided by the application) while utilizing the
channel bandwidth effectively; 3) ACE, the first effort to develop a theoretical framework for an-
alyzing and designing a wireless link-layer protocol that targets system stability in conjunction
with reliable communication. The ACE protocol uses a unique and optimal code embedding rate
to construct coded link-layer packets in every transmission to ensure stability, reliability and max-

imum throughput; 4) PACE, the ACE based stable-and-reliable link-layer that employs a novel

162

 

rate-adaptive 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 link-layer communication that takes into consideration the
level of importance/impact of each packet to improve the overall performance.

Although the link-layer frameworks developed in this thesis provide a thorough groundwork
that address reliability and stability issues, it is designed for a single point-to-point connection
(e.g., between an access point and a wireless device). Meanwhile, emerging multi-hop ad-hoc
and mesh wireless networks supporting heterogeneous high-end applications require significantly
further research into new link-layer and corresponding cross-layer 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 flow
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 link-layer connections that
meet several critical objectives simultaneously and jointly: (1) achieving sustained stability: sup-
porting legacy TCP applications and maintaining continuous realtime flow 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 rate-allocation,
and (4) exploiting side-information for channel estimation/prediction in a distributed manner. For
future work, we will build on our findings (realized in this thesis) and develop a Global Rate-
Adaptive Code Embedding (GRACE) framework for a network of reliable and stable wireless
link-layer 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 ad-hoc and mesh networks is critical and has a direct impact on the overall performance
of realtime and high-demand applications (e. g., video conferencing, HDTV, etc.). The link-layer
frameworks developed in this thesis are designed to ensure 100% accuracy of each packet. That
is, the link—layer protocol follows a correct-it-send-it 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 link-layer (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 significant end-to-end delay due
to the complexity of error correction process since every packet has to be decoded completely
before transmitted to the next-hop; and b) introduces unnecessary packet losses at the link-layer
since partially corrupted packets (which are likely to be expired) are dropped from the link-layer
buffer.

We will investigate and develop a new decoding strategy to tackle the critical issues associ-
ated with the inefficiency of the correct-it-send-it approach and pursue a paradigm shift in the
conventional link-layer 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 network-of-queues model that captures the er-
ror correction process and networking effects of traffic flows over multi-hop path. In particular,
we aim to find 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 link-layer packet should be examined

164

 

for being decodable or not?

Here, there are two extreme options. First, one can implement a hop-by-hop link—layer, where
full rate-adaptive 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 final 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
find the optimal GRACE assignment, first 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 ad-hoc 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 first model a given network with a random graph. Then, we will
formulate the assignment problem to find 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 final phase of address-
ing this research question includes distributed solution for GRACE assignment that the achieves

a performance close to p’“.

165

int-mue- 0
J

8.2 Code Assignment

Under the GRACE framework, a new packet is encoded using minimum (but necessary) number
of type-I parity symbols. Further, if the packet is decoded using type-I parity symbols and the
decoder cannot successfully retrieve the corrupted symbols in the packet, it will request for ad-
ditional type-II parity symbols. The management of the transmission of type-I and type-II parity
symbols is trivial for point-to-point communication scenario where the type-II parity symbols are
always concatenated to future data packets. We envision that this management will not be trivial

for multi-hop network.
Research question 2. How to partition the handling of different code types at difierent 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 type-II
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 type-II code to be delivered to another intermediate node n2 that is located on the
Mo’s route toward its destination. Here this new type-H 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 type-II 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 type-II parity symbols. Further, let a
cost function g(yj, M,) be the cost of delivering type-II parity yj to a packet M,. We define a
transport plan T : Y —+ M an arrangement where each type-II parity block yj E Y is delivered

to its corresponding packet T(yj) E M. We wish to find 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 higher-layers

The proposed link-layer framework primarily focuses on the enhancement of the link-layer pro-
tocol and the improvement of wireless link-layer communication. Another aspect of the GRACE
framework for multi-hop ad—hoc/mesh wireless networks is the design and analysis of dynamic
feedback mechanism between the link-layer and the higher layers. Using this feedback mecha-
nism, the higher layers (while interacting with link-layer) reconfigure and readapt in reaction to
heterogeneous traffic fluctuations and wireless channel noise disruptions. This approach will en-
able higher-layers to intelligently adjust the operating parameters of their protocols based on the
knowledge of wireless channel conditions passed on to them by the link-layer. 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 link-layer on the performance of each of the higher layers.

Research question 3. How is the GRACE link-layer 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 first
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 type-I parities and are waiting for type-H 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 type-II parity symbols that should be transmitted by the corresponding sender.
On the other hand, the type-H 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 influenced 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 link-layer. 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 link-layer and the CSMA/CA
contention mechanism to ensure maximum contention fairness with minimum decoding delay at

the link-layer.
Research question 4. Can GRACE improve the performance of ad-hoc routing protocols?

The main objective of the network layer for mobile ad-hoc/mesh network is to route the wireless
packets between different senders and receivers. One of the challenging types of routing protocols
is an ad-hoc routing protocol [80]. In ad-hoc 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 find an efficient ad-hoc routing protocol and various routing
protocols have been proposed [76]- [79]. Among these protocols, Ad-hoc On-demand 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 request-response cycles. At
each node, AODV maintains a routing table where each entry for a destination contains three es-
sential fields: a next hop node, a sequence-number and a hop-count. All packets destined to the
destination are sent to the next hop node. The sequence number acts as a form of time-stamping,
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 hop-count. 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 multi-hop 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 significantly 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 link-layer to the routing layer where the channel condition is reported
to the routing layer. In particular, we add a new field called parity-usage to each entry of the
AODV routing table. The parity-usage field is updated by GRACE after every link-layer trans-
mission. More specifically, the GRACE informs the routing layer the number of parity bits it
employed for its coding operations. The parity-usage 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 hop-count and parity-usage and will select a path with a lower cost.

170

8.4 Broader Impact

The impact of the link-layer frameworks developed in this thesis is envisioned to be significantly

effective in the following areas:

0 Sensor Networks and Power Constrained Systems: In addition to enabling a major shift
toward reliable and stable link-layer communications, the proposed effort will naturally
have significant 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 power-constrained 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 high-end applications
such as HDTV over wireless networks. What is ultimately needed for wireless HD video
is a comprehensive cross-layer framework that targets stable-and-reliable 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 multi-hop ad-hoc or mesh wireless networks. Consequently, a natural extension
of the proposed link-layer framework (presented in this thesis) is the development of a cross-
layer based stable-and-reliable link-layer that interacts with the lower physical layer and the
higher video layer. We also envision realizing the proposed new link-layer approach with
a high-end application over a small testbed with all supplementary softwares which can be

made available to the larger research community.

0 Neurotechnology Communication Systems: Brain-computer 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 state-of—the-art 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)
significant communication error: since it is difficult 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 well-suited 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 type-I parity probability distribution p Xi can be achieved if
1 I—r
sz, Z a; (716, + ,/n€,-qo (u)) ,
where (1710/) is the V-quantile 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 error-correcting capability at decodes a message with type-I

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<a.-_1)2 n (ma-4+ né,_1¢—1<u)>.

(I

where V is close to one (i.e., V = 0.99). By assuming very slow fading, such that the channel does
not change significantly 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 satisfies 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 infinity. That is,

.. 0 —1
6-_ 6'_ V
6,< lim 9”1 —--za1-l-\/-—————-z 1‘15 ()

_n—rOO n
a-
,2, 39—1 ( z 1).
a

 

Thus

 

El

Lemma 3. In T,_1, if a decoder with error-correcting capability a fails to decode a message

with type-I 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 type-I 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,-

|/\

1-1
I

Q

<15

 

To find 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 find
the lower bound for 6, by computing the limiting convergence of the above expression when n is

infinity. 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,<<a
a
where a is error-correcting capability of a decoder

Proof The optimization problem in (5.15) is a convex problem with the Lagrangian in a from of

131091, (\1, A2) = ki + A103191+ 131(61- 0))
(B.1)
+212 (k, +13, —n,) . A1,)? > 0
Since the primal problem is convex, the Karush-Kuhn-Tucker (KKT) conditions are sufficient

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,<<a
a

Proof To guarantee the stability condition, the buffer has to be always non—empty and at the
same time does not overflow. To ensure that the buffer is always non-empty, the buffer length
limiting distributions should not carry any density at the value zero (i.e,F(0, j) = 0, j = 1,2). By

substituting b = 0 in equations (6.9)(6.10) we have

51091 — C)

F(0,1)=0 F(O,2)=w,— C
The steady state probability of the buffer at length zero is always zero when the decoding is
successful at the link layer (e. g., Z (t) = 1). To ensure that the buffer is non-empty when the link

layer fails to decode new data ( Z (t) = 2), the following equality has to be satisfied

 

w- = . (8.4)

To ensure that the buffer does not overflow, the stability condition in equation (6.11) should hold.

By using equations (6.8) and (6.11), we obtain F E, (612,) = 1 — f- 5 %. Therefore, 2:,- g
z
-1
F

. (0-5) A . . .
£3— = 75:1 = l—C—gIE—L. Correspondingly, by substituting 2:, = |C,-|(1 — R,), the lower
bound of code embedding rate is R,- 2 1 — a1. Cl

179

 

 

APPENDIX C

Proof of Lemmas for PACE

Lemma 1. For a packet transmitted over BSC with cross-over probability 6,- that is decoded using
LDPC check matrix with parameters dv and dc; the distortion level after m iterations can be

approximated by

elm) z e,- [ta-(C1,. —1)(dc —1)]m—1

Proof. Equation (7.1) can be simplified significantly with following approximations:

180

 

 

2

(Tn—1))dc-1 dv—l
6. 2

(m) _ €(0)_ (0)[1+<1-20.

 

 

_ _ €(m—1) dc—l (iv—1
+ (1 — 40)) [1 (1 2 22 )
dv-l
~ (0) (0) [1+1 — (dc —1)2€§m—1)]

 

(m-l) d” 1
(0) 1+ 1 + (dc —1)2€i
(1— 6i ) I: 2

 

 

 

' ' d —1 d —1
2 62(0) — 62(0) 1— (dc — 1)6§m_1) v +(1— 6 0)) [1+ (dc — 1)6z(-m-1) 1)
Z :d _1
x 62(0) — 62(0) 1— (dc — 1)€2(m—1) v
= .210) — 62(0) [1 — ((1., —1)(dc — helm-1)]
l.
= 62(0)(dv —1)(dc _1)€z(m—1) = {civil—1),
wheref = 62(0)(dv — 1)(dc — 1). By taking a unilateral Z-transform, we have,
_ 0
<0) _ _ 9 10E )
ZT,(Z) — Ez- — €T,‘(Z) —> T,’(Z) — _1 (C.1)
1 — 2
Now, the inverse Z-transform 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 = (Ill-2710,10 + #300,02-
(A + #1l7rm,0,0 = (Vim—1,0,0 + (III-2707120 + #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,B2-1,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 = (”Bl-1,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 = “lfllm—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 = )‘flm—l,n,B3 + ”1”m+1,n—1,B3

+ qfl27rm,n+1,B3 + pfl2fim,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

+ qflzflm,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 + ”llflmfi : 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 + Hrflm+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. “Error-Correction Coding for Digital Communica-
tions.” New York, Plenum Press, 1981. ISBN 0-306-40615-2.

[2] S. Soltani, K. Misra, and H. Radha, “On Link-Layer Reliability and Stability for Wireless
Communication,” ACM MOBICOM, 2008.

[3] S. Soltani, H. Radha, “PEEC: A Channel-Adaptive Feedback-Based 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, “Constant-Complexity Models for Wireless Channels,”
IEEE INFOCOM, April 2006. [50]

[5] S. S. Karande and H. Radha, “Hybrid Erasure-Error 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 MAC-to-MAC 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, “Linear-Complexity Models for Wireless MAC-to-
MAC Channels,” ACM/Kluwer Wireless Networks (WINET) Journal - Special Issue on Se-
lected Papers from MSWiM’O3, vol. 11, no. 5, pp. 543-555, September 2005.

Syed Ali Khayam, Selin Aviyente, and Hayder Radha, “On Long-Range Dependence in
High-Bitrate 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 Receiver-based 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, “Rate-Constrained 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, “Markov-based 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 High-Bitrate Real-Time Multimedia,”
EURASIP Signal Processing: Image Communication, vol.18, no.7, pp. 575-595, August
2003.

Syed Ali Khayam, Shirish S. Karande, Michael Krappel, and Hayder Radha, ”Cross-Layer
Protocol Design for Real-Time 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 Link-Layer,” 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
Power-Law 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 LT-codes 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 Finite-State 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. “Link-level 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.11-1999, New
York, 1999.

[30] ISO/IEC 8802-11:1999(E), “Part 11: Wireless LAN Medium Access Control (MAC) and
Physical Layer (PHY) Specifications,” August 1999.

[31] IEEE Std 802.11b-1999, “Part 11: Wireless LAN Medium Access Control (MAC) and Phys-
ical Layer (PHY) Specifications: Higher-Speed 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. COM-25, no. 5, pp. 473.479, May 1977.

[34] S. S. Chakraborty, E. Yli-Juuti, 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, “Receiver-based 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 post-reception 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. Yli-Juuti, 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 (CODEC-O4), 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 Hybird-ARQ 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: Prentice-Hall, 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 modified selective-repeat type-H hybrid ARQ system and its perfor-
mance analyses,” IEEE Transactions on Communications 31(5), pp. 124-133, 1983.

[51] G. Caire and D. Tuninetti, ”The throughput of Hybird-ARQ protocols for the Gaussion col-
lision channel”, IEEE Trans. Inform. Theory, 47: 1971 1988, July 2001.

[52] D. Chase, “Code-combining: A maximum likelihood decoding approach for combining
an arbitrary number of noisy packets,” IEEE Trans. Commun., vol. COMM-33, no. 5, pp.
385393, May 1985.

[53] J. C. Bolot, S. Fosse-Parisis, and D. Towsley, “Adaptive FEC-based 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. Rate-compatible puncturing of low-density parity-
check codes. IEEE Trans. Inform. Theory, 50:2824-2836, 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, ”Rate-compatible low-density parity-check 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, ”Rate-compatible puncturing of low-density 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 rate-compatible low-density
parity-check codes”, IEEE Commun. Lett., 8:159161, March 2004.

[62] J. Hagenauer, “Rate-compatible 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-
efficient turbo ARQ systems,” in IEEE Int. Symp. Information Theory, Washington, DC,
Jun.2001,p.213.

[64] V. Guruswami and M. Sudan. “Reflections on Improved Decoding of Reed-Solomon and
Algebraic-Geometric Codes”. IEEE Information Theory Society Newsletter, 52(1):612,
2002.

[65] J. Hagenauer and P. Hoecher. “A Viterbi Algorithm with Soft-Decision 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. IT-27, pp. 533-547, Sept. 1981.

[67] SB. Wicker and V.K. Bhargava. Reed-Solomon 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. IT-8, January 1962, pp. 21-28.

[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, “Efficient 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. Re-routing instability in IEEE 802.11 multi-hop ad-hoc networks.
IEEE LCN, pages 602-609, 2004.

[77] S. Biswas and R. Morris. “Opportunistic routing in multi-hop 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
multi-hop 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 multi-hop wireless ad hoc network routing protocols”, Proceedings of the 4th annual

ACM/IEEE international conference on Mobile computing and networking, p.85-97, Octo-
ber 25-30, 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):52-58, 2001.

[83] V. Jacobson. Congestion Avoidance and Control. In Proc. ACM Sigcomm’88, Aug. 1988,
pp- 314-329.

[84] Y. Tian, K. Xu, and N. Ansari. TCP in Wireless Environments: Problems and Solutions.
IEEE Radio Communication, 43(3): 827-832, March 2005.

[85] “IEEE Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer
(PHY) Specifications”, 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.
392-396.

[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
resource-sharing 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 real-time traffic 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 Profile 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, “Cross-Layer 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, “MPEG-4 Video Transmission over VVrreless: A
Link Level Performance Study,” ACM/Kluwer Journal of Wireless Networks, vol. 10, issue
2, March 2004, pp. 130-146.

[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 Traffic 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] “Reed-Solomon 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