当前位置:首页 >> >>

Random Linear Network Coding For Time Division Duplexing When To Stop Talking And Start Lis


Random Linear Network Coding For Time Division Duplexing: When To Stop Talking And Start Listening
Daniel E. Lucani
RLE, MIT Cambridge, Massachusetts, 02139 Email: dlucani@mit.edu

Milica Stojanovic
Northeastern University Boston, Massachusetts, 02118 Email: millitsa@mit.edu

Muriel M? dard e
RLE, MIT Cambridge, Massachusetts, 02139 Email: medard@mit.edu

arXiv:0809.2350v1 [cs.IT] 13 Sep 2008

Abstract— A new random linear network coding scheme for reliable communications for time division duplexing channels is proposed. The setup assumes a packet erasure channel and that nodes cannot transmit and receive information simultaneously. The sender transmits coded data packets back-to-back before stopping to wait for the receiver to acknowledge (ACK) the number of degrees of freedom, if any, that are required to decode correctly the information. We provide an analysis of this problem to show that there is an optimal number of coded data packets, in terms of mean completion time, to be sent before stopping to listen. This number depends on the latency, probabilities of packet erasure and ACK erasure, and the number of degrees of freedom that the receiver requires to decode the data. This scheme is optimal in terms of the mean time to complete the transmission of a ?xed number of data packets. We show that its performance is very close to that of a full duplex system, while transmitting a different number of coded packets can cause large degradation in performance, especially if latency is high. Also, we study the throughput performance of our scheme and compare it to existing half-duplex Go-back-N and Selective Repeat ARQ schemes. Numerical results, obtained for different latencies, show that our scheme has similar performance to the Selective Repeat in most cases and considerable performance gain when latency and packet error probability is high.

I. I NTRODUCTION Network coding was introduced by Ahlswede et al [1]. This concept is also known as coded packet networks. Network coding considers the nodes to have a set of functions that operate upon received or generated data packets. Today’s networks would represent a subset of the coded packet networks, in which each node has two main functions: forwarding and replicating a packet. A classical network’s task is to transport packets provided by the source nodes unmodi?ed. In contrast, network coding considers information as an algebraic entity, on which one can operate. Network coding research originally studied throughput performance without delay considerations for the transmitted information. The seminal work by Ahlswede et al [1] considers a channel with no erasures and, therefore, no need for feedback. Work in [2] and [3] showed that linear codes over a network are suf?cient to implement any feasible multicast connection, again considering a channel with no erasures. Also, [3] provides an algebraic framework for studying this

subset of coded networks. In both of these cases, the nodes are considered to transmit a linear combination of the packets previously received. Work in [4] presents the idea of using linear codes generated randomly in a network and shows that it achieves multicast capacity in a non-erasure channel. For networks with packet erasures, two approaches have been used. The ?rst approach relies on rateless codes, i.e. transmitting coded data packets until the receiver sends an acknowledgement stating that all data packets have been decoded successfully. Reference [5] studies random linear network coding in lossy networks showing that it can achieve packet-level capacity for both single unicast and single multicast connections in wireline and wireless networks. Reference [6] presents network codes that preserve the communication ef?ciency of a random linear code, while achieving better computational ef?ciency. Reference [7] presented a random linear coding scheme for packet streams considering nodes with a ?xed, ?nite memory, establishing a trade-off between memory usage and achievable rate. In terms of practical issues and implementation, work in [8] presents MORE, a MACindependent opportunistic protocol for wireless networks, and provides experimental results with some emphasis on the throughput gains provided by network coding. The work in [9] and [10] has studied delay performance gains and their scaling laws for network coding with and without channel side information, respectively. They focus on transmission of large ?les in a rateless fashion. In [11] the delay performance of network coding for a tree-based multicast problem is studied and compared to various Automatic Repeat reQuest (ARQ) and Forward Error Correcting (FEC) techniques. For network coding, it assumes reliable and instantaneous feedback to acknowledge a correct decoding of all data packets. Note that the focus of these references has been on either throughput or delay performance, usually considering minimal feedback. Finally, the work in [12] couples the bene?t of network coding and ARQ by acknowledging degrees of freedom (dof), de?ned as linearly independent combinations of the data packets, instead of original data packets to show that queue size in a node follows degrees of freedom.

The second approach uses block transmissions. Reference [13] studies the problem in wireless networks and shows that linear codes achieve capacity in the network. In [14] a queueing model for random linear coding is presented, which codes data packets in a block-by-block fashion using acknowledgements to indicate successful transmission of each block. Interestingly, the coding block size depends on the number of packets available in the queue, up to some maximum block size. We study channels in which time division duplexing is necessary, i.e. when a node can only transmit or receive, but not both at the same time. This problem has not been considered in any of the previous network coding references or, to the best of our knowledge, for network coding before our work. This type of channel is usually called half-duplex in the literature, but we use the term time division duplexing (TDD) to emphasize that the transmitter and receiver do not use the channel half of the time each or in any pre-determined fashion. Important examples of time division duplexing channels are infrared devices (IrDA), which have motivated many TDD ARQ schemes [15] [16], and underwater acoustic communications [17]. Other important applications may be found in channels with very high latency, e.g. in satellite [18] [19], and deep space [20] communications. More speci?cally, we focus on the problem of transmitting M data packets through a link using random linear network coding. We consider that the sender can transmit random linear coded packets back-to-back before stopping to wait for an acknowledgement (ACK) packet. This ACK packet conveys the remaining dofs required at the receiver to decode all M data packets. We consider that the number of coded packets Ni to be transmitted before waiting for a new ACK packet depends on the number of dofs i needed at the receiver, as indicated by the last ACK packet received successfully. If it is the ?rst transmission, we consider that the required dofs is M . Figure 1 illustrates the communication process. The system transmits Ni coded packets (CP), and waits to receive an ACK packet that updates the value of i to j, at which point it will transmit Nj coded packets. The system will keep transmitting and stopping to update i, until i = 0. When i = 0, the transmitter can start with M new data packets, or simply stop. In Figure 1, CP (k, d) represents the k-th coded packet transmitted when we start transmission with d dofs needed at the receiver to decode the information. There is a natural trade off in the choice of the Ni ’s. Every time the system stops to wait for an ACK, it incurs in an additional delay, which can be large in high latency channels. In general, the system requires at least one stop to get con?rmation of complete transmission. However, we want to minimize the number of stops required to complete transmission of the M packets. Note that if the Ni ’s are too small given the channel conditions, the system will have to transmit more ACK packets to complete transmission of the block of M data packets, which will cause a larger delay. On the other hand, if the Ni ’s are too large, the receiver will have decoded the M packets, for example, before the transmitter

j ≤ i dofs needed to decode

2

CP (1,i) Tp

CP (2,i)



CP (Ni,i) Tw

ACK

Fig. 1.

Network coding TDD scheme

stops sending the ?rst NM coded packets. Since the block of M original packets is considered to be completely transmitted when the ACK requests no more dofs, the system causes unnecessary delay by transmitting too many coded packets by delaying transmission of the ACK by the receiver. In other words, the transmitter could have sent a smaller number of coded packets before stopping and still transmit the M packets successfully. We show that there exists an optimal number of coded data packets to be transmitted back-to-back before stopping to wait for an ACK packet from the receiver, in terms of mean completion time, i.e. mean time to decode the M original data packets at the receiver and get an ACK at the transmitter. In fact, the optimal number of coded data packets Ni depends on the number of dofs i that the receiver requires to decode the information, and also on the packet error probability and the latency, i.e. the number of bits in ?ight. Thus, we show that there is an optimal time for stop transmitting coded packets and start listening to an ACK packet from the receiver. Thus, our objective is to minimize the expected time to complete transmission of a block, i.e. the delay in block transmissions, using feedback. This delay to decode a block is different from the usual packet delay measure. Since coding is carried out on blocks of packets, the delay to decode a block successfully determines the delay of each of the packets in that block. We also show that minimizing the expected time to complete transmission of a block of M packets with a ?xed packet size also maximizes the throughput performance. However, we show that a correct choice of M and number of bits in the data packet can further improve throughput performance. Although both standard ARQ techniques and our scheme achieve reliability by detecting errors in received packets or packet erasures, and recover the information using a retransmission scheme, there are some important differences. First, we rely on transmission of coded packets, i.e. there is no need to specify a particular data packet to retransmit as in ARQ, but only a random linear combination. The ACK packet of our scheme thus differs from common ARQ techniques [21] in that it does not give acknowledgement to particular data packets [21], but to degrees of freedom needed at the receiver to decode the M original packets. Second, the number of coded packets transmitted in our scheme is not ?xed by design of the algorithm, but chosen given channel characteristics and information in the ACK packet. In fact, the information in the ACK packet of our algorithm can be used to update an

estimate of the probability of packet error and improve the overall performance. We present an analysis and numerical results that show that transmitting the optimal number of coded data packets sent before stopping to listen for an ACK provides performance very close to that of a network coding scheme operating in a full duplex channel, in terms of mean time to complete transmission of all packets. This is the case even in high latency channels. Choosing a number different from the optimum can cause a large degradation in performance, especially if latency is high. Since random linear network coding is used, the results of this paper can be extended to the case of a network, in which each node performs a random linear combination of packets received from different nodes. In this extension, each node transmitting through a link, or, more generally, a hyperarc (using the terminology in [22]) will have an optimal number of coded packets to transmit back-to-back before stopping to listen. The paper is organized as follows. In Section 2, we present the setup of the problem. In Section 3, we present the analysis of expected time to complete transmission of M data packets and the optimization required to determine the number of coded packets to transmit before stopping. Also, two network coding comparison schemes are presented. In Section 4, the throughput performance is analyzed. In Section 5, numerical results are presented comparing our TDD optimal network coding with several other schemes in terms of the mean time to complete transmission. We also present results that compare throughput performance of our scheme to that of typical ARQ schemes. Conclusions are summarized in the Section 6. II. R ANDOM N ETWORK C ODING FOR TDD CHANNELS A sender in a link wants to transmit M data packets at a given link data rate R. The channel is modeled as a packet erasure channel. Nodes can only transmit or receive, but not both at the same time. The sender uses random linear network coding [4] to generate coded data packets. Each coded data packet contains a linear combination of the M data packets of n bits each, as well as the random encoding coef?cients used in the linear combination. Each coef?cient is represented by g bits. For encoding over a ?eld size q, we have that g = log2 q bits. Also consider an information header of size h. Thus, the total number of bits per packet is h + n + gM . Figure 2 shows the structure of each coded packet consider in our scheme. The sender can transmit coded packets back-to-back before stopping to wait for the ACK packet. The ACK packet feeds back the number of degrees of freedom, that are still required to decode successfully the M data packets. Since random linear coding is used, there is some probability of choosing encoding vectors that are all zero for one coded packet or encoding vectors that are linearly dependent on vectors of previously received packets. Thus, using arguments similar to [9], the expected number of successfully received packets

3

Header h bits
Fig. 2.

Data n bits

Cod. Coeff. 1 g bits

Cod. Coeff. M

Structure of coded data packet

i=M

If M new packets are available

Transmit Ni

Receive ACK

No Yes i = 0?

Update i

Fig. 3. Algorithm of network coding for time division duplexing channels. i represents the remaining number of degrees of freedom to decode the packets, and Ni the corresponding number of coded packets transmitted before stopping to listen for a new ACK. The ACK packet has the information to update i

before having M linearly independent combinations, is
M k=1

1 (1 ? (1/q) )
k

≤M

q q?1

(1)

In the following analysis, we assume that the ?eld size q is large enough so that the expected number of successfully received packets at the receiver, in order to decode the original data packets, is approximately M . This is not a necessary assumption for our analysis. We could have included the probabilities of receiving linearly independent combinations into the transition probabilities. However, making this assumption simpli?es the expressions and provides a good approximation for large enough q. We are interested in determining the optimal number of coded packets that should be sent back-to-back before waiting for an ACK packet from the receiver in order to minimize the time for successfully transmitting the M data packets over the link. Note that if M packets are in the queue, at least M degrees of freedom have to be sent in the initial transmission, i.e. NM ≥ M coded packets. We are interested not only in the number of dof that are required at the ?rst transmission, but also at subsequent stages. Transmission begins with M information packets, which are encoded into NM random linear coded packets and transmitted. If all M packets are decoded successfully, the process is completed. Otherwise, the ACK informs the transmitter how many are missing, say

(1 ? Peack ) Pe N M + Peack

(1 ? Peack ) Pe N1 + Peack

?N ? (1 ? Peack ) ? M ? (1 ? Pe) Pe N M ?1 ? 1 ? M-1 M

1
(1 ? Peack )(1 ? Pe )
N1

For j = i the expression for the transition probability reduces to: Pi→i = (1 ? P eack )P eNi + P eack

4



1

0

(5)

? N ? (1 ? Peack ) ? M ? (1 ? Pe) M ?1 Pe N M ? M +1 ? M ? 1?

III. E XPECTED T IME FOR COMPLETING TRANSMISSION The expected time for completing the transmission of the M data packets constitutes the expected time of absorption, i.e. the time to reach state 0 for the ?rst time, given that the initial state is M . This can be expressed in terms of the expected time for completing the transmission given that the Markov Chain is in state is i, Ti , ?i = 0, 1, ..M ? 1. Let us denote the transmission time of a coded packet as Tp , and the waiting time to receive an ACK packet as Tw . For our scheme, Tp = h+n+gM and Tw = Trt + Tack , where Tack = nack /R, nack R is the number of bits in the ACK packet, R is the link data rate, and Trt is the round trip time. Note that T0 = 0. Then, for i > 1: Ni Tp + Tw (1 ? P eack )(1 ? P eNi ) (1 ? P e)i P eNi ?i +
j i?1 Pe j=1 f (i, j) 1?P e Tj 1 ? P eNi

Fig. 4. Markov chain representation of the scheme. State i represents that the receiver requires i more successfully received coded packets to decode the information

i. The transmitter then sends Ni coded packets, and so on, until all M packets have been decoded successfully. We are interested in the optimal number Ni of coded packets to be transmitted back-to-back in the next transmission to complete the remaining i dof’s. Figure 3 shows the communication process as a system transmits NM coded packets initially and awaits reception of an ACK packet that updates the value of i, at which point it will transmit Ni coded packets. The system will keep transmitting and stopping to update i, until i = 0. When i = 0, the transmitter can start with M new data packets or simply stop. In Figure 1, CP (k, d) represents the k-th coded packet transmitted when we start transmission with d dofs needed at the receiver to decode the information. The process can be modelled as a Markov Chain (Figure 4). The states are de?ned as the number of dof’s required at the receiver to decode successfully the M packets. Thus, these states range from M to 0. This is a Markov Chain with M transient states and one recurrent state (state 0). Let us de?ne Ni as the number of coded packets that are sent when i dof’s are required at the receiver in order to decode the information. Note that the time spent in each state depends on the state itself, because Ni = Nj , ?i = j in general. The transition probabilities from state i to state j (Pi→j ) have the following expression for 0 < j < i and Ni ≥ i: Pi→j = (1 ? P eack ) Ni (1 ? P e)i?j P eNi ?i+j i?j (2)

Ti

=

(6)

(7)

For example, for i = 1 we have that: T1 = N1 Tp + Tw (1 ? P eack )(1 ? P eN1 ) (8)

As it can be seen, the expected time for each state i depends on all the expected times for the previous states. Because of the Markov property, we can optimize the values of all Ni ’s in a recursive fashion, i.e. starting by N1 , then N2 and so on, until NM , in order to minimize the expected transmission time. We do so in the following subsection. A. Minimizing Expected Time for Completing Transmission Our objective is to minimize the value of the expected transmission time TM . Under the assumption that Ni ≥ i, we have: min TM =
NM Tp +Tw

where P e and P eack represents the erasure probability of a coded packet and of an ACK packet, respectively. More generally, the transition probability can be de?ned for any value of Ni ≥ 1 as follows: Pi→j = (1 ? P eack )f (i, j)(1 ? P e)i?j P eNi ?i+j where
Ni i?j

NM ,..,N1

NM ,..,N1 (1?P eack )(1?P eNM )

min

(9)

(3)

f (i, j) =

0

if Ni ≥ i, otherwise

(4)

PM ?1 NM “ P e ”j (1?P e)M P eNM ?M Tj j=1 (M ?j ) 1?P e + 1?P eNM NM Tp +Tw = min (10) NM (1?P eack )(1?P eNM ) “ ”j PM ?1 NM Pe (1?P e)M P eNM ?M minN ,..,N Tj j=1 (M ?j ) 1?P e 1 j + NM 1?P e

Without this assumption, we have that

NM ,..,N1

min min

TM =
NM Tp +Tw

NM ,..,N1 (1?P eack )(1?P eNM )


(11)

”j PM ?1 Pe (1?P e)M P eNM ?M f (M,j) Tj 1?P e j=1 + NM 1?P e NM Tp +Tw = min (12) NM (1?P eack )(1?P eNM ) “ ”j PM ?1 Pe (1?P e)M P eNM ?M f (M,j) minN ,..,N Tj 1?P e j=1 1 j + NM 1?P e

of freedom i required at the receiver to decode the information is i ≥ ω, the transmitter will transmit ω degrees of freedom. If i < ω, the transmitter will transmit i degrees of freedom. The model for the Markov Chain is derived from the previous case, by setting Ni = ω, ?i ≥ ω and Ni = i, ?i < ω. For i ≥ ω, we have that: Ti = + and for i < ω: Ti = + iTp + Tw (1 ? P eack )(1 ? P ei ) P ei?j (1 ? P e)j Ti?j (17) (16) ωTp + Tw (1 ? P eack )(1 ? P eω ) P eω?j (1 ? P e)j Ti?j 1 ? P eω (15) (14)

5

ω ω j=1 j

Hence, regardless of the assumption on Ni , the problem of minimizing TM in terms of the variables NM , .., N1 can be solved iteratively. First, we compute minN1 T1 , then use this results in the computation of minN2 ,N1 T2 , and so on. One approach to computing the optimal values of Ni is to ignore the constraint to integer values and take the derivative of Ti with respect to Ni and look for the value that sets it equal to zero. For our particular problem, this approach leads to solutions without a closed form, i.e. expressed as an implicit function. For M = 1, the optimal value of N1 can be expressed using a known implicit function (Lambert function), and it is given by
? N1

i i j=1 j

1 ? P ei C. Comparison Scheme 2: Optimal Full Duplex ARQ

1 + W ? exp ?1 + = ln P e

ln(P e)Tw Tp

?

Tw Tp

(13)

where W (·) is the Lambert W function [23]. The positive values are found for the branch W?1 , as denoted in reference [23]. The case of M = 1 can be thought as an optimized version of the uncoded Stop-and-Wait ARQ, which is similar to the idea presented in [18]. Instead of transmitting one packet and waiting for the ACK, our analysis suggests that there is an optimal number of back-to-back repetitions of the same data packet that should be transmitted before stopping to listen for an ACK packet. Instead of using the previous approach, we perform a search for the optimal values Ni , ?i ∈ {1, ...M }, using integer values. Thus, the optimal Ni ’s can be computed numerically for given P e, P eack , Tw and Tp . In particular, the search method for the optimal value can be made much simpler by exploiting the recursive characteristic of the problem, i.e. instead of making a M -dimensional search, we can perform M one-dimensional searches. Finally, these Ni ’s do not need to be computed in real time. They can be pre-computed and store in the receiver as look-up tables. This procedure reduces the computational load on the nodes at the time of transmission. B. Comparison Scheme 1: Fixed Maximum Window Let us consider the same setting, i.e. a ?xed number of packets M that have to be transmitted to the receiver, but with a ?xed, pre-determined maximal number of coded packets to be transmitted before stopping to listen. We de?ne this maximal value of coded packets as ω. If the number of degrees

This scheme assumes that nodes are capable of receiving and transmitting information simultaneously, and in that sense it is optimal in light of minimal delay. The sender transmits coded packets back-to-back until an ACK packet for correct decoding of all information (M information packets) has been received. This scheme can be modeled as a Markov Chain where, as before, the states represent the number of dofs received. The time spent in each state is the same (Tp ). Once the M packets have been decoded, i.e. M dofs have been received, the receiver transmits ACK packets back-toback, each of duration Tack . One ACK should suf?ce but this procedure minimizes the effect of a lost ACK packet. The mean time to complete the transmission and get and ACK is: M Tp Tack E[T ] = Trt + + (18) 1 ? P e 1 ? P eack where T is the time to complete transmission of M packets. IV. T HROUGHPUT The mean throughput is de?ned as E[ M n ], where T is T the time to complete transmission of M packets. For M n 1 deterministic we have M nE[ T ]. For the case of M = 1, i.e. the extended version of the Stop-and-Wait ARQ scheme, we can provide a simple expression for the mean throughput in terms of the transition probabilities P1→1 and P1→0 , 1 E[ ] T
P = P1→0
1→1

P1→1 k ∞ k=1 k(Tp +Tw )
k ∞ (1?P1→0 ) k=1 k

(19) (20) (21)

1→0 = P P(T +T ) w 1→1 p

= ?P

P1→0 1→1 (Tp +Tw )

ln(P1→0 )

We have used the Mercator series since |1 ? P1→0 | < 1 for all cases of interest. However, for M > 1 this expressions are complicated. Thus, we de?ne our measure of throughput η as the ratio between number of data bits transmitted (N ) and the

time it takes to transmit them. For the case of a block-by-block transmission, as described in Section III, η= Mn TM (22)

6

where TM is the expected time of completion de?ned previously. Note that the expected throughput and η are not equal. ln(1/P ) For the case of M = 1, note that E[ M n ] = η P 1→0 . T 1→1 1 More generally, using Jensen’s inequality, M nE[ T ] ≥ M n TM for T > 0. Therefore, η constitutes a lower bound to the mean throughput in our scheme. Another reason to consider this measure is to compare our network coding scheme with typical ARQ schemes that do not rely on coded packets since the analysis for most ARQ schemes is performed using η. Note that if M and n are ?xed, η is maximized as TM is minimized. Thus, by minimizing the mean time to complete transmitting of a block of M data packets with n bits each, we are also maximizing η for those values. However, we show that the maximal η should be obtained using M and n as arguments in our optimization. This is important for systems in which the data is streamed. In this case, searching for the optimal values of M and n, in terms of η, provides a way to optimally divide data into blocks of M packets with n bits each before starting communication using our scheme. A. Optimal Packet size and packets per block We have discussed throughput with a pre-determined choice of the number of data bits n and the number of data packets M in each block. However, expression 22 implies that the throughput η depends on both n and M . Hence, it is possible to choose these parameters so as to maximize the throughput. We can approach this problem is several ways. The ?rst approach is to look for the optimal n while keeping M ?xed: ηopt (M ) = arg max
n NM ,...,N1

Fig. 5. Expected time for transmitting M data packets successfully versus P e in a satellite example. The parameters used are M = 10, Trt = 250 ms, data rate 1.5 Mbps, nack = 100 bits, n = 10000 bits, g = 100 bits, h = 80 bits, P eack = 0.001

max

η

(23)

The second approach is to look for the optimal M while keeping n ?xed: ηopt (n) = arg max
M NM ,...,N1

max

η

(24)

More generally, we could consider the case in which both parameters are variable and we are interested in maximizing η: ηopt = arg max
n,M NM ,...,N1

max

η

(25)

V. N UMERICAL E XAMPLES This section provides numerical examples that compare the performance of the different network coding schemes we have discussed so far in TDD channels. The comparison is carried out in terms of the mean time to complete a transmission of M data packets through TDD channel under different block error probabilities. We also present results in terms of the

measure of throughput η to illustrate its dependence on the values of M and n for varying channel characteristics (erasure probabilities). We use the case of satellite communications as an example of high latency channels. Figure 5 studies the expected time to complete transmission of M = 10 data packets of size n = 10000 bits, with different packet error probabilities in a GEO satellite link with a propagation delay of 125 ms. We assume a link with parameters speci?ed in the ?gure. Note that our network coding scheme (TDD optimal) and the network coding full duplex optimal scheme have similar performance over a wide range of block error probabilities. In fact, for the worst case (P e = 0.8) presented in this ?gure, our scheme has an expected time of completion only 29 % above the full duplex scheme. This is surprising considering that the transmitter in the full duplex scheme sends coded packets non-stop until an ACK packet is received. The explanation for this behavior is that our scheme is sending enough coded packets, given the channel conditions, so that the number of stops to listen (which are very costly) is minimized. Thus, our scheme can have similar performance to that of full duplex optimal scheme, in the sense of expected time to completion. Most importantly, our scheme is very likely to have a much better performance in terms of energy consumption due to the long periods in which the transmitter stops to listen for the ACK packets. Figure 5 also shows the performance of the comparison scheme 1 presented in Section III. Note that when ω = 10, i.e. the transmitter sends at most 10 coded packets before stopping to listen, the performance is comparable to our optimal scheme

7

Fig. 6. Throughput measure η versus the number of bits n in a data packet for a symmetrical channel, for different values of M with parameters g = 100 bits, nack = 100 bits, h = 80 bits, data rate 100 Mbps, Trt = 250 ms, P ebit = 0.0001

Fig. 7. Throughput η versus n in a symmetrical channel considering different values of round-trip time Trt with parameters g = 100 bits, nack = 100 bits, h = 80 bits, data rate 1.5 Mbps, M = 10, P ebit = 0.0001

when the block error probability is low. This fact con?rms that for low block error probabilities the optimal choice of coded packets to transmit when i dof are required at the receiver (Ni ) is simply i. In other words, if M = 10 and the block error probability is low, the ?rst transmission contains 10 coded packets. Note that using ω = 9 already suffers from a considerable degradation in performance even for low P e because the transmitter cannot transmit the minimum number of coded packets (M ) necessary to decode the information after the ?rst transmission, and so it must transmit at least one more coded packet after the ?rst ACK. Note that the performance of ω = 5 and ω = 9 is similar for low block error probability because both of them require at least two stops to listen for ACK packets in order to relay all the information, and it is the stopping time that affects delay the most on a high latency channel. For the case of ω > 10 we would see a degradation for low P e, with respect to optimum, because more packets than necessary are transmitted. Finally, note that for the worst data error probability in Figure 5, all ?xed schemes (TDD with ?xed ω) take at least 5 times more time to complete transmission than the network coding full duplex optimal scheme. The case of ω = 1 can be interpreted as the performance of the Stop-and-Wait ARQ scheme under the same channel conditions, which is considerably worse than the other schemes. Let us turn our attention now to the problem of maximizing the parameter η, i.e. our mean throughput lower bound. Recall that for this setting we are streaming data which is subdivided into blocks that are transmitted them using our

scheme. Considering again a satellite link, given a ?xed bit error probability (P ebit = 0.0001) let us study the problem of computing the optimal number of bits n per packet given some value of M . In these examples, for the case of a symmetric channel with independent bits P e = 1 ? (1 ? P ebit )h+n+gM and P eack = 1 ? (1 ? P ebit )nack . Figure 6 illustrates the values of η in Mbps given different choices of M and n. First, note that for each value of M there exists an optimal value of n. Thus, an arbitrary choice of n can produce a considerable degradation in performance in terms of throughput. Secondly, there is a (M, n) pair that maximizes the value of η. Finally, the performance of the full duplex network coding and our TDD optimal scheme is comparable for different values of n and M . Figure 7 shows η in Mbps when we change the round-trip time Trt . As expected, a lower Trt allows more throughput in TDD. Again, we observe that our TDD optimal scheme has comparable performance to the full duplex scheme. Let us compare the performance of our optimal TDD network coding scheme with respect to typical TDD ARQ schemes: Go-back-N (GBN) and Selective Repeat (SR). For this comparison, we use the η factor for the half-duplex version’s of these schemes. Reference [15] studied both of these cases and proposed the utilization factor. In our notation, the equivalent η’s are given by ηGBN and ηSR for GBN and SR, respectively: n(1 ? P e) 1 ? (1 ? P e)W ηGBN = (W Tp + Tw )P e (26)

8

Fig. 8. η versus data packet error probability with two TDD non-network coding schemes (Go-Back-N and Selective Repeat) and our optimal TDD network coding scheme, with different R. We used as parameters g = 20 bits, nack = 100 bits, n = 10000 bits, h = 80 bits, Trt = 0.25 ms

Fig. 9. η versus data packet error probability with two TDD non-network coding schemes (Go-Back-N and Selective Repeat) and our optimal TDD network coding scheme, with different Trt values. We used as parameters g = 20 bits, nack = 100 bits, n = 10000 bits, h = 80 bits, R = 10 Mbps

and W n(1 ? P e) ηSR = W Tp + Tw (27)

where W is the window size. Figure 8 shows η for the satellite communications setting with a ?xed packet size of n = 10000 bits, nack = 100 bits, Trt = 250 ms, P eACK = 0 for all schemes, a window size of W = 10 for the ARQ schemes, and g = 20 bits and M = 10 for our network coding scheme. We use different data rates to illustrate different latency scenarios, where higher data rate is related to higher latency. Note that the performance of our scheme is the same as both GBN and SR at low data packet error probability, which is expected because the window size W is equal to the block size of our scheme M and we expect very few errors. Our scheme has a slightly lower η for low P e because each coded data packet includes gM additional bits that carry the random encoding vectors. This effect is less evident as latency increases. In general, our scheme has better performance than GBN. Figure 8 shows that for low latency (0.1 Mbps) η of our scheme is very close to that of the SR ARQ scheme for all values of P e, and better than the GBN scheme for high P e. These results are surprising, because our scheme constitutes a block-by-block transmission scheme which will not start transmission of a new set of M data packets until the previous ones have been received and acknowledged. Note also that, as latency increases, our scheme shows much better performance than the SR scheme for high P e. The case of 10 Mbps and

P e = 0.8 shows that η of our scheme is more than three (3) times greater than that of SR. Figure 9 shows η for a ?xed data rate of 10 Mbps and different Trt . We use a ?xed packet size of n = 10000 bits, nack = 100 bits, P eACK = 0 for all schemes, a window size of W = 10 for the ARQ schemes, and g = 20 bits and M = 10 for our network coding scheme. Note that the overhead of transmitting M coef?cients of g bits per coded packet is only 2%. Thus, this effect cannot be appreciated in the ?gures. Again, the performance of our scheme is the same as both GBN and SR at low data packet error probability. Since the data rate is kept ?xed, at higher Trt we get higher latency. The throughput performance is similar to that observed in Figure 8 if we carry our comparison in terms of latency. Another advantage of our scheme with respect to SR ARQ is that our scheme relies on transmitting successfully one block of M data packets before transmitting a new one. In fact, our scheme minimizes the delay of every block. In contrast, the SR ARQ does not provide any guarantee of delay for any data packet, e.g. the ?rst packet of a ?le to be transmitted could be the last one to be successfully received. In this sense, our comparison is not completely fair, as it favors the standard schemes. Nonetheless, our scheme is providing similar or better performance than SR but guaranteeing low transmission delays in individual data packets. VI. C ONCLUSION This paper proposes a new random linear network coding scheme for reliable communications for time division

duplexing channels. This scheme optimizes the mean time to complete transmission of a number of data packets by determining the number of coded data packet that the sender has to transmit back-to-back before stopping to wait for the receiver to acknowledge how many degrees of freedom, if any, are required to decode correctly the information. The optimal number of coded data packets, in terms of mean completion, to be sent back-to-back depends of the latency, probabilities of erasure of the coded packet and the ACK, and the number of degrees of freedom that the receiver requires to decode the data. While there is no closed form solution for the optimal number of packets, we can perform a search of the optimal values. In particular, the search method for the optimal value is simple by exploiting the recursive characteristic of the problem, i.e. instead of making a M -dimensional search, we perform M one-dimensional searches. Finally, these values do not need to be computed in real time. They can be precomputed and stored in the receiver as look-up tables. This procedure makes the computational load on the nodes to be negligible at the time of determining the optimal transmission time. We present means of analysis and numerical results to show that transmitting the optimal number of coded packets before stopping to listen for an ACK is very close to the performance of a full duplex system, while choosing a different number can cause considerable degradation in performance, especially if latency and packet error probability are high. Notably, our scheme also shows good potential to improve energy consumption. In terms of throughput performance, we compare our scheme to the standard half-duplex Go-back-N and Selective Repeat ARQ schemes. Numerical evaluation for different latency shows that our scheme has similar performance to the Selective Repeat in most cases, and considerable performance gain when latencies and packet error probability are high. Numerical results also show that our scheme is superior to Go-back-N when error probability is high for different latency. Future research will consider the problem of 1) energy consumption and associated optimization for this scheme, and 2) extension of the principles proposed (which were analyzed for one link in a network) to the general problem of wireless networks. ACKNOWLEDGMENT This work was supported in part by the National Science Foundation under grants No. 0520075, 0427502, and CNS0627021, by ONR MURI Grant No. N00014-07-1-0738, and subcontract # 060786 issued by BAE Systems National Security Solutions, Inc. and supported by the Defense Advanced Research Projects Agency (DARPA) and the Space and Naval Warfare System Center (SPAWARSYSCEN), San Diego under Contract No. N66001-06-C-2020 (CBMANET). R EFERENCES
[1] Ahlswede, R., Cai, N., Li, S. Y. R., Yeung, R. W., “Network Information Flow”, IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204-1216, Jul. 2000

9

[2] Li, S.Y.R., Yeung, R. W., Cai, N., “Linear Network Coding”, IEEE Trans. Inf. Theory, vol. 49, pp. 371, Feb. 2003 [3] Koetter, R., M? dard, M., “An algebraic Approach to network coding”, e IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 782-795, Oct. 2003 [4] Ho, T., Medard, M., Koetter, R., Karger, D.R., Effros, M., Shi, J., Leong, B.,“A Random Linear Network Coding Approach to Multicast”, Trans. Info. Theory, vol. 52, no. 10, pp.4413-4430, Oct. 2006 [5] Lun, D. S., M’edard, M., Koetter, R., Effros, M., “On coding for reliable communication over packet networks”, Physical Comm., Vol. 1, Issue 1, pp. 3-20, Mar. 2008 [6] Maymounkov, P., Harvey, N. J. A., Lun, D. S., “Methods for Ef?cient Network Coding”, In Proc. 44-th Allerton Conference’06 [7] Lun, D. S., Pakzad, P., Fragouli, C., M’edard, M., Koetter, R., “An Analysis of Finite-Memory Random Linear Coding on Packet Streams”, In Proc. WiOpt’06, Boston, MA, USA, Apr. 2006 [8] Chachulski, S., Jennings, M., Katti, S., Katabi, D., “Trading Structure for Randomness in Wireless Opportunistic Routing”, In Proc. COMM’07, pp. 169-180, Kyoto, Japan, Aug. 2007 [9] Eryilmaz, A., Ozdaglar, A., M? dard, M., “On Delay Performance Gains e from Network Coding”, In Proc. CISS’06, pp. 864-870, Princeton, NJ, USA, Mar. 2006 [10] Ahmed, E., Eryilmaz, A., M? dard, M., Ozdaglar, A., “On the Scaling e Law of Network Coding Gains in Wireless Networks”, In Proc. MILCOM’07, Orlando, FL, USA, Oct. 2007 [11] Ghaderi, M., Towsley, D., Kurose, J., “Network Coding Performance for Reliable Multicast”, In Proc. MILCOM’07, Orlando, FL, USA, Oct. 2007 [12] Sundararajan, J. K., Shah, D., M’edard, M., “ARQ for Network Coding”, In Proc. ISIT’08, pp. 1651-1655, Toronto, Canada, Jul. 2008 [13] Dana, A. F., Gowaikar, R., Palanki, R., Hassibi, B., Effros, M., “Capacity of wireless erasure networks”, IEEE Trans. on Info. Theory, vol. 52, no. 3, pp. 789-804, Mar. 2006 [14] Shrader, B., Ephremides, A., “A queueing model for random linear coding”, In Proc. MILCOM’07, Orlando, USA, Oct. 2007 [15] Ozugur, T., Naghshineh, M., Kermani, P., Copeland, J. A.,“On the performance of ARQ protocols in infrared networks”, Int. Jour. Commun. Syst., vol. 13, pp. 617-638, 2000 [16] Shah, A. M., Ara, S. S., Matsumoto, M.,“An improved selective-repeat ARQ scheme for IrDA links at high bit error rate”, In Proc. 4th int. conf. on Mobile and ubiquitous multimedia, Christchurch, New Zealand, pp. 37-42, 2005 [17] Stojanovic, M., “Optimization of a Data Link Protocol for an Underwater Acoustic Channel”, In Proc. Oceans 2005 - Europe, pp. 68- 73, Jun. 2005 [18] Sastry, A. R. K., “Improving Automatic Repeat-Request (ARQ) Performance on Satellite Channels Under High Error Rate Conditions”, IEEE Trans. on Comms., vol. 23, no. 4, pp. 436-439, Apr. 1975 [19] Yu, P., Lin, S., “An Ef?cient Selective-Repeat ARQ Scheme for Satellite Channels and Its Throughput Analysis”, IEEE Trans. on Comms., vol. 29, no. 3, pp. 353-363, Mar. 1981 [20] Akyildiz, I.F., Akan, O.B., Fang, J., “TCP-Planet: A reliable transport protocol for InterPlaNetary Internet”, JSAC, vol. 22, no 2, pp. 348361, 2004 [21] Lin, S., Costello, D. J., Miller, M. J.,“Automatic-repeat-request error control schemes”, IEEE Commun. Mag., vol. 22, n. 12, pp. 5-17, Dec. 1984 [22] Lun, D. S., Ratnakar, N., M? dard, M., Koetter, R., Karger, D. R., Ho, e T., Ahmed, E., Zhao, F., “Minimum-Cost Multicast Over Coded Packet Networks”, IEEE Trans. on Info. Theory, vol. 52, no. 6, pp.2608-2623, Jun.2006 [23] Chapeau-Blondeau, F., and Monir, A., “Numerical Evaluation of the Lambert W Function and Application to Generation of Generalized Gaussian Noise With Exponent 1/2”, IEEE Trans. on Signal Proc., Vol. 50, No. 9, Sept. 2002


相关文章:
更多相关标签: