# An Analytical Model for Optimum Byte-Level and Packet-Level FEC Assignment Using Buffer Dynamics

Authors: Azfar Moid; Abraham O. Fapojuwo
Journal: Research Letters in Communications
 (2008)

---

## Abstract

This letter presents an analytical model that jointly exploits the buffer dynamics of both the
sending and receiving nodes to find the optimum number of byte-level and packet-level forward error
correction (FEC) units for real-time multimedia transmission over wireless networks. The
proposed analytical model first provides an optimum number of FEC units required at the byte-level, and then chooses the number of FEC units at the packet-level based on current channel and
network conditions. The accuracy of the proposed model is dependent on two parameters: the
variable deadline-time at the byte-level and fixed round-trip time (RTT) delay at the packet-level.
Numerical results demonstrate the effectiveness of the model in reducing the unrecoverable error
probability, which is achieved when the byte-level FEC scheme is supplemented by the packet-level
FEC scheme.


---

## Body

## 1. Introduction

In this letter, the  problem of selecting the byte-level and
packet-level forward error   correction (FEC) combinations that increase the
overall system efficiency and video quality is presented as a 0-1 knapsack
optimization problem. We propose a dynamic programming  (DP) based algorithm
for selecting the byte-level and packet-level FEC units to minimize the effect of
error-prone wireless channel and network losses. This approach is different
from that of [1] by calculating the cost/throughout ratio (CTR) at both the
byte and packet levels, instead of a single level considered in [1]. Moreover,
unlike in [1] where the time parameter is kept constant, here we adopt a
methodology that incorporates the variable time parameter in calculating CTR,
which is a more realistic approach. The work presented in this letter also
supplements the work in [2] by presenting an analytical model that proves the
effectiveness of using packet-level FEC in conjunction with byte-level FEC
schemes. The main contribution of this letter is the presentation of a DP-based
model that utilizes the queuing dynamics of both the sending and receiving
nodes of a wireless network in calculating the number of FEC redundancy units
at both the byte and packet levels, in the context of video transmission over a
wireless network.


## 2. Problem Formulation and Proposed Solution

Suppose thatmb and Mp are the particular FEC combinations chosen at the byte-level and packet-level,
respectively, such that mb=(n,kb)
and  Mp=(Np,K). Here, n is the
total number of bytes per packet after redundancy is added to a packet and kb is the original number of bytes per packet, such that n=kb+b,
and b (0≤b≤n−1) is the number of redundancy bytes added to
a packet. Similarly, Np is the total number of packets in a
video block after redundancy is added and K represents the original
number of packets in a video block, such that Np=K+p,
and p (0≤p≤K) is the number of redundant packets added to
a video block.


## 2.1. The Optimization Problem

Formally, the optimization problem is casted as a 0-1
knapsack problem, and is formulated as  follows:(1)min(0≤b≤n−1)(0≤p≤K)⁡(E[D(mb,Mp)])subject to(1)∑Bvid(mb,Mp)≤(Bmax⁡−Bother),(2)T(mb,Mp)≤Td,   where E [D(⋅,⋅)] is the expectation of a block distortion. In (1), Bvid(⋅,⋅)
represents the number of video packets that contribute to the buffer occupancy,
whereas Bmax⁡ and Bother
are, respectively,
the maximum buffer size and number of nonvideo packets in the buffer at any
given time. On the other hand, T(⋅,⋅) and Td
are the
time to transmit a video block and total time to render the block on a video
player, respectively.The expectation of the block
distortionE [D(⋅,⋅)] can be calculated using the mean square
error (MSE) between originally transmitted and received blocks: (2)E[D(mb,Mp)]=∑i=1KE[di]=∑i=1KE[1u∑j=1u{fj,i−f˜j,i}2],where E [di] is the expectation of the packet distortion, u is the total number of pixels in a packet, and j is the pixel index of
the current packet. In (2), f denotes the original image and f˜ represents the reconstructed image.The IEEE 802.11 medium access control (MAC) standard defines
an automatic repeat request (ARQ) mechanism where acknowledgments and timeouts
are used to achieve reliable data transmission. If the maximum number of ARQ
retries is set toRmax⁡, the perceived error-free probability
at the application layer is given by (3)δcorrect=∑r=1Rmax⁡(1−δ)δr−1=1−δRmax⁡, where δ is the probability of error for
transmitted packets over the lossy wireless channel, and r is the index
of number of retries. The value of Rmax⁡ is limited for
practical purposes, so that the packet transmission delay will not exceed the
tolerable delay limit for a video packet. The average number of transmission
attempts until a packet is successfully transmitted is given by (4)E[R]=∑r=1Rmax⁡r(1−δ)δr−1.If round-trip time (RTT) is denoted by TRTT,
and packet transmission time is denoted by Tp, the total time
to transmit a video block is then calculated by (5)T(mb,Mp)=N[TRTT(E[R]−1)+Tp].


## 2.2. Dynamic Programming (DP-) Based Solution

Because of the NP-hardness of 0-1 knapsack optimization
problems [3], suboptimal solutions can be found using DP-based techniques. The
time complexity of the DP algorithms is pseudopolynomial, which is acceptable
even for real-time multimedia streaming applications [4]. The computation time
can be minimized by limiting the size of a packet and the maximum number of
packets in a video block. The first step of DP-based algorithm is to calculate
the number of redundant FEC bytes per packet that can minimize the CTR.LetH(i) denote the number of packets in the
playback buffer of the receiving node, right after the playback of the ith
video packet, where i=1,2,…. To avoid underflow of the playback buffer,
we define a deadline-time (Tc) within which the next video
packet should arrive. Tc can be written as (6)Tc(i)=H(i)hfp, where h is the average number of packets in a video frame, and fp denotes the video frame rate in frames/second. By extending the work of [1] to
the byte-level FEC, the CTR for a packet transmission is defined as (7)CTR(i)=qTc−1(i)+rnw(n,kb).Here, q (0≤q≤1) is the cost-time product of transmitting a packet and r (0≤r≤1) is the cost per transmitted byte. In (7), w(n,kb)
is the score of the FEC combination (n,kb). Assuming
that the channel remains stationary during the transmission of one packet, the
score is defined as the total goodput of a selected (n,kb)
strategy. Now, the CTR can be written as (8)CTR(i)=qTc−1(i)+rnkbPr⁡(n,kb), where
Pr(n,kb) is the probability that an (n,kb)
code is successful (i.e., at most n-kb
bytes are in
error). Let ε denote the bit error rate (BER) of the channel and,
assuming bit error occurs randomly and independently, the byte error rate (ρ)
can be calculated as ρ=1−(1−ε)8. Finally, Pr(n,kb)
is calculated by (9)Pr(n,kb)≜∑i=kbn(ni)(1−ρ)iρn−i. For a
given packet size n , and the current channel conditions, a search is
made to find the minimum number of FEC bytes required per packet for which the
throughput is maximized (i.e., minimize the CTR). The search is stopped when
the minimum point of CTR is reached.The second step of the DP-based algorithm is to calculatep,
the optimum number of redundant FEC packets required for each video block with
combination Mp. At the packet-level FEC, a fixed RTT is
considered in [1], but there is a requirement for a variable RTT because the
network loading changes in real-time and channel conditions are not known a priori.
As the video packet arrival rate V(t) at the sending node is
known and, for a given channel rate C(t), the buffer occupancy Bfull(t)
of the sending node can be determined as  (10)Bfull(t)=∫0t{V(τ)−C(τ)}dτ. Here,
we postulate that the number of redundant FEC packets can be calculated  as  (11)p(t)=⌊K{1−e(Bfull(t))/ηeBmax⁡/η}⌋. An
exponential function is assumed here such that the number of redundant packets
decreases exponentially with time to prevent network congestion due to too many
FEC packets, where η is the control parameter. These redundant FEC
packets are added to the video block if and only if the second constraint in
(1) is met, that is, T(mb,Mp)≤Td.
Otherwise, the algorithm sequentially takes the values of p−1,p−2,… until the second constraint is met. This shows that the optimum number of FEC
packets is not constant but time-dependent, which is critical for real-time
applications.A packet arriving at the network can be lost due to two
independent reasons: first, it is dropped due to limited buffer capacity at the
sending node; or second,  the packet cannot be recovered by the byte-level FEC
combination (i.e., more thann-kb
bytes are in error).
The lost packets can be recovered by the packet-level FEC scheme, if the number
of lost packets is no more than Np−K, otherwise the
video block is said to be lost. Let Pd
denote the probability
of a packet drop due to limited buffer capacity, the probability of
unrecoverable error (i.e., the video block is permanently lost), denoted by PER,
is then given as (12)PER=∑i=Np−K+1Np(Npi)[Pr(n,kb)⋅(1−Pd)]Np−i⋅[1−Pr⁡(n,kb)⋅(1−Pd)]i, where
Pr(n,kb) is defined in (9). In (12), i represents the erroneous packets which are not recoverable by packet-level FEC
and contribute to the permanent loss of a video block.


## 3. Numerical Results

Figure1 shows the number of redundant FEC bytes required for
each packet when the channel condition varies from bad to good (i.e., BER
varies from 10−1 to 10−5). Three packet sizes are
considered (i.e., n=500, 1000, 2000 bytes) because the IEEE 802.11
standard allows variable packet sizes with the maximum MAC service data unit
(MSDU) size of 2304 bytes. Without loss of generality, we set q=1 and r=1
in (7). The frame rate is set to 30 frames/sec (to emulate the television
quality video) and we assume that, on the average, the video frame size is of 5
packets (i.e., h=5), to include the effects of all I-, P-, and B-type
video frames. To achieve the desired delay objective for video packets, the
maximum number of retries (Rmax⁡) is set to 4. The number of
redundant FEC bytes for which the CTR value is minimized in (8) is determined.
By comparing different channel conditions in Figure 1, it is evident that the
number of redundant FEC bytes required under bad channel conditions is much
higher than that required under good channel conditions, as expected.Figure 1
Number of FEC bytes required to minimize
the CTR.To further  show the effectiveness of using FEC combinations
at both the byte-level and   packet-level, consider a scenario where the channel is bad (i.e.,BER=10−2),
and the   packet
loss due to sending side’s buffer overflow is not very significant (i.e., Pd=10−3).
This is a typical scenario where the sending node has enough buffer capacity
but unable to transmit packets due to bad channel condition. Figure 2 shows the
comparison of byte-level and packet-level FEC combinations (individually and
jointly) for reducing the  probability of unrecoverable error. Here, we have
considered one video block of 8 video packets, that is,   K=8, and the
packet size is fixed at 500 bytes. As determined from Figure 1, when BER=10−2,
the number of redundancy bytes required to minimize the CTR is 54, hence
(500, 446) combination is selected at the byte-level. The probability of
unrecoverable error can be further reduced from 5.1×10−2 at
packet-level combination (8, 8) to 3.3×10−5 at packet-level
combination (10, 8), as shown in Figure 2, by selecting the optimum packet-level
FEC combination allowed by the second constraint in (1). Figure 2 confirms that
implementing the FEC at only one level is not good enough for error correction
and hence should be supplemented by the FEC implementation at the other level.Figure 2
PER for different packet-level FEC
combinations.The probability of unrecoverable error for the DP-based
algorithm proposed in this letter was compared with the corresponding result
for the algorithm presented in [2], assuming n=500, BER=10−2, Pd=10−3, and K=8. It is seen from Figure 3
that, under the different packet combinations considered, the probability of
unrecoverable error for the DP-based algorithm is lower than that of the
algorithm presented in [2]. The CTR model used in the DP-based algorithm
introduces a lower bound on the number of FEC bytes, this translates to a
better error recovery at the packet-level, thus resulting in lower probability
of unrecoverable  error.Figure 3
Comparison of thePER of the proposed DP(-based) algorithm and the algorithm presented in [2].


## 4. Conclusion

It is concluded that optimum byte-level  and packet-level FEC
assignment in conjunction with buffer dynamics results in lower probability of unrecoverable
error. This translates to high-transmission quality, a desirable requirement
for both wireless service subscribers and providers.



---

*Source: 546184-2008-04-13.xml*