Optimal choice of FEC parameters to protect
against queueing losses in wireless networks
Claus Bauer, Wenyu Jiang, Dolby Laboratories, San Francisco, USA, {cb,wzj}@dolby.com

for packet losses of type 2, a change of the FEC parameters
leads to a change in the overall sending rate of the multimedia
traffic that in turn leads to a different occupancy of the AP
queue and thus influences the frequency at which losses of type2 occur. Consequently, we see that the algorithms described inprevious papers only predict the effectiveness of FEC codes
correctly for losses of type 1, but not of type 2.
The effectiveness of FEC parameters in view of losses oftype 2 was investigated in [2],[7], [8], and [12]. However, inthese papers, the sending pattern of the multimedia traffic ismodeled as a Poisson traffic, which does not model accurately
the common practice of sending multimedia traffic over communication networks at a constant bit rate.
In this paper we consider the problem of determining theefficiency of FEC parameters (n, k) in view of losses oftype 2. In contrast to [8], we use a discrete time model thatallows us to both exactly model the dynamics of a constant
bit rate sending process and derive a shorter mathematicalderivation than in [8]. In our approach, the current packet
loss probability is not used explicitly as an input parameterfor the algorithm to determine the FEC parameters. Instead,we develop a model of the network that takes explicitly into
account the arrival patterns of all traffic streams in the network,
the size of the buffer at the access point, and the reliability of
the wireless channel. We note that in [2],[7], and [12] only one
traffic stream is considered, whereas we distinguish between
a primary multimedia traffic and competing traffic streams.
Technically, we first develop and solve a Markov based
steady state model for the queue occupancy using a singularvalue decomposition. Then, we develop an iterative procedure
to calculate the loss probability of multimedia packets after
FEC recovery in dependence of the FEC parameters (n, k).
Because this procedure to calculate the effectiveness of
FEC codes is computationally too complex for a real-time
application, we also propose an approximation algorithm thatallows to determine an optimal choice of the parameters(n, k) under the real-time constraints of a typical multimedia
application. The reduction of the complexity is achieved byconsidering only a subset of the steady state model without
significantly compromising the accuracy of the calculations.
We describe the considered network model in section II. In
section III, we specify a sending scheme for multimedia CBR
traffic protected by an FEC code. In section IV, we develop
an algorithm to determine the loss probability for multimedia
packet after FEC recovery. We describe an approximation
algorithm in section V. We provide numerical evidence forthe correctness of the algorithms developed in section VI and
we conclude in section VII.

Abstract— This paper proposes algorithms to determine an
optimal choice of the FEC parameters (n, k) to mitigate against
the effects of packet loss due to buffer overflow at a wirelessbase station on multimedia traffic. To solve this problem, wedevelop analytic models of the considered network scenariosthat take into account traffic the arrival rates, the channel loss
characteristics, and the size of the buffer at the wireless basestation. We develop an iterative procedure to compute the packet
loss probabilities after FEC recovery and verify the analyticalresults via simulation.

I. I NTRODUCTION
The delivery of real-time multimedia traffic over wirelessnetworks will be a significant application in future wirelessnetworks. The perceptual quality of service received by theuser suffers from packet loss, delay, and delay jitter. Packet
loss in wireless networks is due to two causes:
1. Packets might get lost or arrive corrupted at the receiver
when they are transported over the lossy medium air. Thiscan be the result of a low signal to noise ratio or a collision
with packets sent from neighboring base stations.
2. Packets are dropped from the queue of the wireless accesspoint (AP) if the queue is full.
Throughout this paper, we will refer to packet losses due tothe reasons 1 and 2 as losses of type 1 and 2 respectively.
Forward Error Correction (FEC) codes have been extensively researched as a method to improve QoS [1], [4], [11].
They have proved to be very efficient if packet losses are not
too bursty. A FEC block code is characterized by the parameterset (n, k) : Each code takes a codeword of k data packets andgenerates n − k additional parity packets and transmits all npackets over the network. If at least k out of these n packets
are received at the receiver, then all k multimedia packets arerecovered. Otherwise, only the received multimedia packets
are recovered. In the sequel, we denote k multimedia packets
and the (n − k) FEC packets protecting them as a multimedia
sequence. Adaptive FEC protections schemes that dynamicallychange the FEC parameters (n, k) in view of rapidly changing
network conditions have been researched in [5], [6].
The papers listed above do not distinguish between packet
losses of type 1 and 2. Also, the effectiveness of a new FEC
parameter set is calculated using the current loss probabilityof the considered traffic stream, i.e., it is assumed that the loss
probability of the channel is not influenced by a change in thesending rate of the multimedia traffic due to a change in theset of FEC parameters. For losses of type 1 this assumption isroughly correct, if one assumes that the channel has enoughbandwidth to send the original multimedia packets as wellas the new FEC packets at the same bit rate it was operating
before changing the actual FEC parameters (n, k). In contrast,
1

1-4244-0000-7/05/$20.00 ©2005 IEEE.

2Free time slot

(1)

Multimedia packet≤ k(m − 1).

Free time slotn−kFree time slot

we assume a discrete, slotted time model. For simplicity, we
assume that both the arrival of a packet to the AP from asender and the successful departure of a packet from the AP
over the wireless channel take one time slot. We assume thata multimedia packet is sent every m time slots. The sending
scheme of the FEC packets is specified in section III. We
assume that the arrival rate of unspecified competing traffic
is distributed according to a Bernoulli distribution with aparameter pC < 1 and qC = 1 − pC . We define pD as theprobability that in a time slot a packet is sent successfully fromthe AP queue over the wireless channel and qD = 1 − pD .
pD presents the rate at which packets leave the AP buffer.
It does not include the rate at which retransmission or MAC
layer FEC packets are sent over the wireless channel if any ofthese technologies is implemented in the wireless network.
For the analysis, we split a time slot in three phases: thepacket arrival phase, the packet dropping phase, and the packet
sending phase which occur in the same chronological order:
1. Packet arrival phase: Packets are sent from the multimedia
sender to the AP according to a predefined sending scheme
explained in the section III. Competing packets are sent fromthe competing senders with probability pC to the AP. If packets
are sent from both the multimedia and senders, we assume

Free time slot

Network modelMultimedia packet

Fig. 1.

Free time slot

Wired connections
Wireless connection

Free time slot

Multimedia senderFree time slot

Multimedia receiverMultimedia packet

Competing sender
Queue

Free time slot

Competing receiver

FEC packet

Wireless access point

In this section, we define a sending scheme for CBR
multimedia traffic that is protected using an FEC code. We
say that a CBR multimedia stream is sent with a periodicity
of m ≥ 2 if a multimedia packet is sent every m timeslots whereas no multimedia packet is sent during the m − 1intermediate time slots. We further assume the deployment
of FEC codes with a parameter set (n, k), i.e, k- original
multimedia packets and n − k additional FEC packets are sent
to the queue from the multimedia sender. Assuming a sending
periodicity m for the k multimedia packets, the n − k FEC
packets are sent as follows: After the last of the k multimedia
packets of a current multimedia sequence has been sent, the(n − k) FEC packets of this multimedia sequence are sent in
the next n − k free time slots, i.e., the time slots not used by
the k - multimedia packets of the next multimedia sequence(see an example in fig. 2). To guarantee the feasibility of thissending scheme, we only allow parameter sets (n, k) such thatthe number of FEC packets n − k is less then than the numberof free time slots between the next k multimedia packets, i.e.,

FEC packet

Competing sender

PROTECTION

Multimedia packet

Competing receiverIII. S ENDING SCHEME FOR CBR TRAFFIC WITH FEC

FEC packet

We consider a network (fig. 1) that consists of a multimedia
sender and a multimedia receiver, a number of competing
senders and a number of competing receivers, and a wirelessaccess point (AP). The multimedia sender sends multimedia
packets and the competing senders send unspecified packets
over wired connections to the AP. The AP forwards all packets
to the multimedia or competing receivers. For simplicity, we
assume that all packets are of fixed, equal size.
Packets that arrive at the AP from the senders are either
directly sent to the wireless interface of the AP or are queued
in a buffer within the AP. The AP-queue has a maximum
length T which corresponds to the maximum number ofpackets that can be buffered at the AP. Any packets that
arrive when the queue is full are dropped from the queue.
In this paper, we only consider AP-queues that apply a FIFO
queueing discipline. The first packet of a queue is sent over
the wireless channel if the channel is available. The wirelesstechnology might implement its own QoS technologies asretransmission or MAC layer FEC. Throughout this paper,that each of the two packets arrives before the other packet
with equal probability 12 . The queue length is increased by the
number of arriving packets a ∈ {0, 1, 2}.
2. Packet dropping phase: If, after the packet arrival phase,
there are T + d, d ∈ {1, 2} packets in the AP-queue, the lastd packets are dropped from the queue.
3. Packet sending phase: With probability pD the first packetof the AP-queue is sent over the wireless channel. If the queueis empty, no packet is sent. The queue length is decreased by
the number of departing packets d ∈ {0, 1}.
The scope of this paper is to calculate the loss probability
after FEC recovery for given parameters m, pC , pD , T, n,
and k.

FEC packet

II. N ETWORK MODEL AND TERMINOLOGY

m=4, n=8,k=4, w=5, q=3, f=1,p=2

Fig. 2.

Multimedia and FEC packet sending scheme

IV. PACKET LOSS PROBABILITY AFTER FEC RECOVERY
A. Analytical approach
For the calculation of the loss probability, we assume thatthe dropping behavior of the first packet of any multimedia
sequence which is sent to the AP is independent of the dropping behavior of any previous packet. For any of the remainingn − 1 packets of a multimedia sequence, we will calculate its
dropping probability in dependence of the dropping behavior

3of the multimedia or FEC packet which was most recently sent
to the AP. This procedure is motivated by the fact that after amultimedia or FEC packet is lost, an analysis of our model insection II shows the queue length is at least T − 1. This highoccupancy of the queue influences the queue occupancy of
the time slot when the next multimedia or FEC arrives which
in turn influences the loss probability of the next arriving
multimedia or FEC packet.
B. Transition matrix
The calculation of the loss probability after FEC recovery
will require the calculation of the transition matrix P t whose
entries are the transition probabilities between the different
states of the queue occupancy in consecutive time slots. Wetdenote the transition matrix as P t and define as Pa,b
,0 ≤a, b ≤ T, the probability that the queue length changes froma to b between consecutive time slots where the queue lengthis measured after the packet sending phase. For any fixed timeslot, we define a quantity pA as the probability that either amultimedia or an FEC packet arrives in the next time slot. As
we use a deterministic sending scheme for the sending of themultimedia and FEC packets, there is pA ∈ {0, 1} for any timeslot. Throughout this paper, we denote the transition matrix P t
as F = P t if pA = 1 and as G = P t if pA = 0. We obtainfrom the model described in section II and fig. 3,tP0,0t
Pk−2,kt
Pk−1,kt
Pk,kt
Pk+1,kPTt −1,T −1
PTt −1,T
t
PT,T
−1
t
PT,T
t
Pa,b

= qA qC + qA pC pD + pA qC pD ,= pA pC qD , 2 ≤ k ≤ T,

Pk−1

D. Loss probability after FEC recovery= qA qC qD + qA pC pD + pA qC pD + pA pC pD ,= pA qC qD + qA pC qD + pA pC qD ,= pD ,= qD ,= 0 f or all other a and b.
pA pC q D

q A q C q D + q A pC pD +pA q C pD

Pk

Pk +1

Pk +2

pA pC pD + pA q C q D + q A pC q D

Transition probabilities from Pk
pA q C q D + q A pC q D + pA pC q D
q Aq C+ q A pC pD +pA q C pD

P0

q A q C q D + q A pC pD +pA q C pD + pA pC pD

qD

PT −1

The calculation of the loss probability after FEC recovery will require knowledge of the steady state vector S =(Sk )0≤k≤T where Sk expresses the probability that the AP
queue contains k packets at the end of the sending phaseof the time slot before the first packet of a multimedia
sequence arrives. We now calculate the vector S. We set
w = b((m/(m − 1)) ∗ (n − k))c . Then, by the definition of
the sending scheme in section III, a multimedia or FEC packet
is sent during each of the first w of the considered k ∗ m timeslots. In particular, all the n − k FEC packets of the previous
multimedia sequence and - if m ≤ w - some of the multimedia
packets of the current multimedia sequence will be sent during
the first w time slots. (We note that by (1), there is w ≤ k∗m.)
We set u ≡ w(mod m), 0 ≤ u ≤ m − 1, and q = m − u.
Then, q − 1 equals the number of time slots between the w-thtime slot and the next time slot in which a multimedia or FEC
packet is sent. Further, we define p via k ∗m−w −f ∗q = mpand set f = min(u, 1). Now, we can write the steady state
equations for the vector S. We distinguish the cases m−1 < w(fig. 2) and m−1 > w (We note that due to (1) there is always
w 6≡ m − 1(mod m). Then, according to the definition of thesending process in section III:¡¢TS = F w−m+1 (Gq−1 F )f (Gm−1 F )p F m−1 S,
if m − 1 < w,³
´TS =F (Gm−1 F )p F w G(q−1) S, if m − 1 > w.
We solve theseP
equations for S via a singular value decomposition and use i Si = 1.

= pA pC pD + pA qC qD + qA pC qD ,1 ≤ k ≤ T − 1,
= qA qC qD + qA pC pD + pA qC pD
1 ≤ k ≤ T − 2,
= qA qC pD , 0 ≤ k ≤ T − 1,q A q C pD

C. Steady state vector of queue occupancy

PTpTransition probabilities
at P0
Transition probabilities
between PT−1 and PT
D

Fig. 3. The transition probabilities for the AP queue occupancy. (Pk denotes
the probability that the queue occupancy is equal to k.)

The calculation of the loss probability after FEC recovery
is performed in five steps. In the first step, we calculate thej−1conditional probability Rg,h, 2 ≤ j ≤ n that the queue is oflength h at the end of the time slot before the j-th multimedia
packet arrives given that the queue was of length g at the endof the time slot when the j − 1-th multimedia or FEC packet
arrived. From the definitions of w, u, and q in section IV-C,
and noting that q 6= 1 as always w 6≡ m − 1(mod m), we findwc,
(F m−1 )g,h ,2 ≤ j ≤ bm






w

c + 1, u ≥ 1, q ≥ 2,  (F u Gq−1 )g,h , j = b mj−1
w(Gm−1 )g,h ,j = bmc + 1, u = 0,
Rg,h =
w

c + 1 < j ≤ k,bm
 (Gm−1 )g,h ,





δg,h ,
k + 1 ≤ j ≤ n,
where δg,h = 1 for g = h and δg,h = 0 else. We recall that thej−1
term Rg,his only defined for 2 ≤ j ≤ n. Thus, if j 6∈ [2, n]
j−1
in any of the conditions of the right side of definition of Rg,h,then the case described by this condition does not occur.
In the second step, we consider the conditional probability
that an arriving multimedia or FEC packet of a multimedia
sequence is not dropped if the AP queue is of length h at theend of the time slot before the considered multimedia or FEC
packet arrives. The arriving multimedia packet is not lost if
h ≤ T − 2 or if h = T − 1, k = T − 2. If h = k = T − 1,then the arriving packet is not dropped if either no competing

4

packet arrives and a packet is sent from the queue - withprobability qC pD - or when a competing packet arrives after
the multimedia packet and a packet is sent from the queue- with probability 12 pC pD . If h = T − 1, k = T, thenthe arriving packet is not dropped if either no competing
packet arrives and no packet is sent from the queue - withprobability qC qD - or when a competing packet arrives after
the multimedia packet and no packet is sent from the queue- with probability 12 pC qD . If h = T, the arriving multimedia
packet is dropped.
Thus, given the arrival of a multimedia or FEC packet in
the current time slot and given a queue occupancy of h at theend of the previous time slot, the conditional probability thatthe queue length is equal to k at the end of the sending phaseof the current time slot and that the arriving multimedia or
FEC packet is not dropped, is equal to Eh,k whereFh,k ,h ≤ T − 2, or








h = T − 1, k ≤ T − 2, 
1
qC pD + 2 pC pD , h = k = T − 1,
Eh,k =
.


1


q
q
+
p
q
,
h
=
T
−
1,
k
=
T,


C
D
C
D
2




0,
all other h and k.
Similarly, given the arrival of a multimedia or FEC packet
in the current time slot and given a queue occupancy of h at
the end of the previous time slot, the conditional probability
that the queue length is equal to k at the end of the sending
phase of the current time slot and that the arriving multimedia∗
or FEC packet is dropped, is equal to Eh,k
where

 1
pC pD , h = k = T − 1,


2




 1 pC qD , h = T − 1, k = T, 


2
∗
pD ,
h = T, k = T − 1,
Eh,k
=
.




q
,
h
=
k
=
T,


D




0,
all other h and k.
In the third step, we calculate the conditional probability
Ak,g,j that given a queue length g at the end of the time slot in
which the j − 1-th multimedia or FEC packet of a multimedia
sequence arrives, the queue is of length k at the end of thesending phase of the time slot in which the j-th multimedia or
FEC packet of the multimedia sequence arrives and the j-th
multimedia or FEC packet is not dropped during the dropping
phase. We obtain
Ag,k,j

=

T
X

j−1
Rg,h
Eh,k , 0 ≤ g, k ≤ T, 2 ≤ j ≤ n.

h=0

Analogously, we calculate the conditional probability Bk,g,jthat given a queue length g at the end of time slot in which thej − 1-th multimedia or FEC packet of a multimedia sequence
arrives, the queue is of length k at the end of the sending phaseof the time slot in which the j-th multimedia or FEC packetof the multimedia sequence arrives and the j-th multimedia or
FEC packet is dropped during the dropping phase. Thus,
Bg,k,j

=

T
X

j−1 ∗
Rg,h
Eh,k , 0 ≤ g, k ≤ T, 2 ≤ j ≤ n.

a, 1 ≤ a ≤ n multimedia or FEC packets and to have a queue
occupancy d at the end of the sending phase of the time slot
in which the a-th packet arrives. For a = 1 the T (a, ·, ·) are
functions of the steady state vector S, whereas for a > 1, we
define the T (a, ·, ·) recursively using the expressions Ag,k,j
and Bg,k,j . We obtain
T (1, 0, 0) = S0 qC pD ,T (1, 0, 1) = S0 (qC qD + pC pD ) + S1 qC pD ,T (1, 0, k) = Sk−2 pC qD + Sk−1 (qC qD+ pC pD ) + Sk qC pD ,2 ≤ k ≤ T − 2,
T (1, 0, T − 1) = ST −3 pC qD + ST −2 (qC qD + pC pD )1
+ ST −1 (qC pD + pC pD ),2
1
T (1, 0, T ) = ST −2 pC qD + ST −1 (qC qD + pC qD ),2
T (1, 1, k) = 0,0 ≤ k ≤ T − 2,
1
T (1, 1, T − 1) = ST −1 pC pD + ST pD ,2
1
T (1, 1, T ) = ST −1 pC qD + ST qD ,2TX
T (a, 0, d) =T (a − 1, 0, c)Ac,d,a , 2 ≤ a ≤ n,c=0

T (a, b, d)

=
+

c=0
T
X

T (a − 1, b, c)Ac,d,a ,T (a − 1, b − 1, c)Bc,d,a ,

c=0

T (a, a, d)

2 ≤ a ≤ n, 1 ≤ b ≤ a − 1,TX=
T (a − 1, a − 1, c)Bc,d,a , 2 ≤ a ≤ n.
c=0

In the fifth step, we calculate S(a, b, d, v), 1 ≤ a ≤ n−k, 0 ≤b ≤ a, 0 ≤ v ≤ k, which we define as the probability to losev out of k multimedia packets, to lose b FEC packets out of
the first a FEC packets and to have a queue length d at theend of the sending phase of the time slot in which the a-th
FEC packet arrives. We calculate the expressions S(1, ·, ·, ·) asfunctions of the T (k, · ·) and the Ag,k,j and Bg,k,j , whereas
for a > 1 we define S(a, ·, ·, ·) recursively from S(a−1, ·, ·, ·),Ag,k,j and Bg,k,j . We findS(1, 0, d, v)
S(1, 1, d, v)
S(a, 0, d, v)

=
=
=

T
X
c=0
T
X
c=0
T
X

T (k, v, c)A(c, d, k + 1),
T (k, v, c)B(c, d, k + 1),
S(a − 1, 0, c, v)A(c, d, a + k),c=0

S(a, b, d, v)

2 ≤ a ≤ n − k,TX=
S(a − 1, b, c, v)A(c, d, a + k),

h=0

In the fourth step, we determine T (a, b, d), which we define
as the probability to lose 0 ≤ b ≤ a packets out of the first

T
X

+

c=0
T
X
c=0

S(a − 1, b − 1, c, v)B(c, d, a + k),

5

TABLE IE XECUTION TIME OF THE ALGORITHM

2 ≤ a ≤ n − k, 1 ≤ b ≤ a − 1,
T
X

S(a, a, d, v) =S(a − 1, a − 1, c, v)B(c, d, a + k),

c=0

2 ≤ a ≤ n − k.
Thus, the probability H(k, n, v, w) to lose v out of k original
multimedia packets and w out of n − k FEC packets isH(k, n, v, w)=

TX

S(n − k, w, d, v).

(2)

d=0

The average number of lost multimedia packets Eloss equals
Eloss

=

1−
½

where R(v, w) =

k n−k
X
X

H(k, n, v, w)R(v, w),

v=0 w=0k,
v + w ≤ n − k,k − v, else.

(3)

¾
.

V. A PPROXIMATION A LGORITHMS OF LOW COMPLEXITYTO CALCULATE Erec
A. Complexity of the algorithm
In this section, we examine the computational complexity
to calculate Eloss as defined in (3) and compare it with thelatency requirements of a multimedia real-time application.
The calculation of Eloss first requires mk matrix multiplications and a singular value decomposition of a (T +1) × (T + 1) matrix. These calculations have a complexityof O(mkT 3 ). The calculation of the probabilities T (a, b, d)
and S(a, b, c, d) requires O(k 2 T ) and O((n − k)2 kT 2 ) steps,
respectively.
¡ Thus, the overall complexity¢ of the exact algorithm is mkT 3 + k 2 T + ((n − k)2 kT 2 . Table I shows how
long it took to calculate Eloss using a C-implementation on a
3.4 Gigahertz pentium PC for different queue lengths. As an
example for the real time requirements of a typical multimedia
application, we note that the payload of a Dolby AC-3 audio
packet at a sample rate of 48 kbps is equal to 32 ms ofaudio content [3]. In a realtime scenario, the exact algorithm
calculates Eloss for different values of n and k in order tofind a parameter setting (n, k) that minimizes the multimedia
packet loss after recovery. The execution time of the algorithm
and the latency requirements of the Dolby AC-3 codec showthat the adaption of the FEC parameters (n, k) based on the
result delivered by the exact algorithm can happen only several
tens of audio packets after the algorithm has received its input
parameters pA , pC and pD . Thus, the algorithm is too slow todynamically adapt the FEC parameters.
B. Collapsed state model and approximation algorithm
In this section, we define an approximation algorithm tocalculate Eloss in formula (3) in realtime. An adaptive FEC
scheme will only apply FEC codes when packets are lost
due to buffer overflow. The AP queue overflows when theaccumulative arrival rate of both competing and multimedia
traffic at the AP is higher than the departure rate from the AP.
In such a situation, one expects that the AP queue is always
full or nearly full, i.e., one expects that the entries Sk of theQueue size T
400
300
200
100
50

Time in ms
1558
623
155
15
<1

steady state vector S are nearly zero for all but a few valuesof k which are very close to T.
Our numerical experiments confirm these expectations. The
fig. 4 shows the distributions of the steady state probabilities
for different competing traffic rates pC . We simulated CBRtraffic with a sending rate m = 4 and set n = 6, k = 5, pD =0.8. We note that the sum of the arrival rates pA + pC isequal to pD for pC = 0.5. For pC = 0.52, i.e., pC is slightly
higher than the equilibrium rate pC = 0.5, the steady state
probabilities Sk rise sharply with increasing k, however steadystate probabilities larger than 0.01 can be found for k > 95.
When increasing the competing traffic rate pC to 0.6 such thatthe accumulative arrival rate pA +pC is significantly larger thanthe departure rate pD , we find that the steady state probabilities
Sk are all close to zero unless k is very close to T.
Any state with steady state probability Sk = 0 has no
significant impact on the dynamics of the steady state modelas the system is virtually never in this state. Consequently, one
can expect that these states can be neglected entirely for the
calculation of Eloss without changing the result significantly.
Based on the above observation, we now propose anapproximation algorithm to calculate Eloss that only takes
into account the steady states for which Sk > ², where ² is a
pre-defined, small threshold value. We assume that Sk ≤ ² fork ≤ T0 , and we consider a ”collapsed steady space vector”
S c with T − T0 + 1 spaces: We collapse all states for whichk ≤ T0 into the state S0c and consider the states for whichk > T0 , individually. In the collapsed steady state model, wecrename these Sk as Sk−T
, T0 ≤ k ≤ T.
0
For 0 ≤ a, b ≤ T − T0 , we define the transition probabilitytbetween the states Sac and Sbc as Pa+T
. We note that
0 ,b+T0
according to the model in section II, the transition matrixt
Pi+T
exactly describes the dynamics of the AP queue
0 ,j+T0
occupancy for the collapsed steady state model S c if i, j > 0,
whereas it only approximately describes them if either i = 0
or j = 0. However, as we assume that the collapsed state S0c
only occurs with a probability ≤ ²T0 , we anticipate that for a
sufficiently small ² the numerical inaccuracy due to the usageof only approximatively correct transition probabilities to andfrom the state S0c will not significantly influence the calculation of the values of Skc for 1 ≤ k ≤ T − T0 . Specifically, we
expect that the absolute difference |Skc − Sk+T0 | is very small
for 1 ≤ k ≤ T − T0 .
We calculate Eloss as in section IV using S c instead of S
and T −T0 instead of T. This leads to a reduced computational
complexity of O(mk(T − T0 )3 ). Table I shows that for T0
close to T the approximation algorithm satisfies the latency
requirements of a realtime application such as Dolby AC-3.
In practice, the algorithm must first determine the value T0
in order to calculate the S c . Our experiments described in the60.3
pC =0.6
pC =0.52
0.25

Steady state probability

0.2

0.15

0.1

0
10 Steady states
20 Steady states
100 Steday states

Packet loss probability after FEC recovery − logaritmic scale

next section have shown that whenever pA + pC > pD + 0.1,
T0 can be chosen as small as T0 = 10.

−5

−10

−15

−20

−25

−30

−35

−40

0.05

0

0.1

0.2

0.3
0.4
0.5
Rate of competing traffic

0.6

0.7

0.8

0

−0.05

Fig. 4.

0

20

40

60
80
Index of steady state

100

120

140

Distribution of steady states for T=130, pD =0.8, m=4, n=6, k=5

VI. N UMERICAL RESULTS
In this section, we present network simulation results toverify the accuracy of the exact and approximation algorithms
to calculate Eloss . We used the C programming language
to build a model of the network and simulated 10.000.000
consecutive time slots.
Fig. 5 shows the change of the multimedia packet loss rate
after FEC recovery as a function of the FEC parameter k fora given n = 14. The difference between the analytical and thesimulation results is within the expected statistical variance ofthe simulation results and is so fine that the respective values
cannot be distinguished in a graph.
Fig. 6 compares the exact algorithm with the results
0.7
m=5, Loss rate channel =0.5
m=6, Loss rate channel =0.4

Loss probability Eloss after FEC recovery

0.6

0.5

0.4

0.3

0.2

0.1

0

3

4

5

6

7

8
k

9

10

11

12

13

Fig. 5. The loss probability Eloss using FEC for changing k with T=130,
pC =0.72, n=15.

of the approximation algorithm. We choose T = 100 and
T − T0 = 10 and 20, respectively. We note that as pD = 0.8
k= 0.44, the accumulative arrival rate equals theand nmdeparture rate for pC = 0.355. We conclude from fig. 6that for pA + pC > pD , the approximation delivers resultsthat are numerically very close to the results delivered by theexact algorithm. For pA + pC ≤ pD , we see that the twoalgorithms give very different results. This is due to the factthat the approximation algorithm is based on the assumptionthat the queue length is nearly always in states Sk with kclose to T. As this is only true in the range pA + pC >pD , the approximation algorithm only approximates the exact
algorithm in this range. For our application, this behavior of
the approximation algorithm is sufficient as FEC protection is
only required if pA + pC > pD .

Fig. 6. Comparison of exact algorithm for T = 100 with the approximation
algorithm for T = 10, 20 with pD =0.8, m=3, n=4, k=3VII. C ONCLUSIONSThis paper presents algorithms to determine the optimal
choice of FEC parameters (n, k) to protect a constant rate
multimedia stream sent over a wireless network from packet
losses due to packet dropping at the queue of the wireless AP.
We develop a mathematical model of the wireless network thattakes into account the exact arrival pattern of the multimedia
stream, the accumulative arrival rate of all other traffic arriving
at the wireless base station, the loss model of the wirelesschannel, and the queue size of the buffer of the wireless
AP. We solve the underlying Markov model of the queue
occupancy and develop an iterative procedure to calculate theeffectiveness of the FEC parameters (n, k).
In order to apply this mathematical framework in practice,
we propose an approximation algorithm of low complexity thatallows to determine the optimal parameter settings of (n, k)
for CBR multimedia traffic under real-time constraints. The
accuracy of the algorithms is verified via network simulations.
R EFERENCES[1] Blahut, R., Theory and Practice of Error control codes, Addison-Wesley,
1993.
[2] Cidon, I.; Khamisy, A.; Sidi, M.; Analysis of packet loss processes inhigh speed networks,. IEEE Trans. on Inform. Theory, vol. 39, no.1, p.
98 108, 1993.
[3] Fielder, L. D. et al., AC-2 and AC-3: Low-Complexity Transform-Based
Audio Coding, Collected Papers on Digital Audio Bit-Rate Reduction(AES, New York, 1996), pp. 54-72.
[4] Frossard, P., FEC Performances in Multimedia Streaming Pascal, IEEE
Communications Letters, vol.5, no 3, March 2001, 122-124.
[5] Frossard, P., Verscheure, O., Joint Source/FEC Rate Selection for
Quality-Optimal MPEG-2 Video Delivery, IEEE Transactions on Image
Processing, vol.10, no.12, 2001.
[6] Libman, L.; Orda, A., Optimal FEC Strategies in Connections with
Large Delay-Bandwidth Products, IEEE ICC 2004.
[7] Gurewitz, O.; Sidi, M.; Cidon, I., The ballot theorem strikes again:
Packet loss process distribution, IEEE Trans. on Inform. Theory, vol.
46, no.7,p. 2599 2595, 2000.
[8] Ait-Hellal, O.; Altman, E.; Jean-Marie, A.; Kurkova, I., On loss probabilities in presence of redundant packets and several traffic sources,
Performance Evaluation, 36 - 37 (1999), 485 - 518.
[9] Kousa, M.A.; Elhakem, A.K., Yang, H., Performance of ATM networks
under hybrid ARQ/FEC error control scheme, IEEE/ACM Transactions
on Networking, 917 - 925, Volume 7 , Issue 6.
[10] Nguyen, T.; Zakhor, A., Distributed Video Streaming with Forward Error
Correction, Packet Video Workshop 2002, Pittsburg, PA, 2002.
[11] Rizzo, L., Effective erasure codes for reliable computer communication
protocols, ACM Comp. Comm. Review, vol. 27, no. 2, 2436, Apr. 1997.
[12] Takine, T.; et al., Cell Loss and Output Process Analyses of a FiniteBuffer Discrete-Time ATM Queueing System with Correlated Arrivals,
IEEE Trans. on Comm., vol.43, pp.1022-1037, 1995.