Modeling Network Coded TCP Throughput: A Simple Model …

1 Modeling Network Coded TCP Throughput: A Simple Model and its ValidationMinJi KimMITC ambridge, MA M dardMITC ambridge, MA o BarrosUniversity of PortoPorto, analyze the performance of TCP and TCP with net-work coding (TCP/NC) in lossy wireless networks. We buildupon the Simple framework introduced by Padhyeet characterize the throughput behavior of classical TCPas well as TCP/NC as a function of erasure rate, round-trip time, maximum window size, and duration of the con-nection. Our analytical results show that Network codingmasks random erasures from TCP, thus preventing TCP sperformance degradation in lossy networks ( wirelessnetworks). It is further seen that TCP/NC has signifi-cant throughput gains over TCP. Our analysis and simu-lation results show very close concordance and support thatTCP/NC is robust against erasures. TCP/NC is not onlyable to increase its window size faster but also to maintain alarge window size despite the random losses, whereas TCPexperiences window closing because losses are mistakenlyattributed to congestion.

2 Note that Network coding onlymasks random erasures, and allows TCP to react to conges-tion; thus, when there are correlated losses, TCP/NC alsocloses its Transmission Control Protocol (TCP) is one of thecore protocols of today s Internet Protocol Suite. TCP wasdesigned for reliable transmission over wired networks, inwhich losses are generally indication of congestion. This isnot the case in wireless networks, where losses are often dueto fading, interference, and other physical phenomena. Inwireless networks, TCP often incorrectly assumes that thereis congestion within the Network and unnecessarily reducesits transmission rate, when it should have actually transmit-ted continuously to overcome the lossy links. Consequently,TCP s performance in wireless networks is poor when com-pared to the wired counterparts as shown in [1,2]. Therehas been extensive research to combat these harmful effectsof erasures and failures; however, TCP even with modifi-cations does not achieve significant improvement.

3 For ex-ample, there has been suggestions to allow TCP sender tomaintain a large transmission window to overcome the ran-dom losses within the Network . However, as we shall showin this paper, just keeping the window open does not leadto improvements in TCP s performance. Even if the trans-mission window is kept open, the sender can not transmitadditional packets into the Network without receiving ac-knowledgments. References [3, 4] give an overview and acomparison of various TCP versions over wireless relief may come from Network coding [5], which hasbeen introduced as a potential paradigm to operate commu-nication networks, in particular wireless networks. Networkcoding allows and encourages mixing of data at intermediatenodes, which has been shown to increase throughput and ro-bustness against failures and erasures [6]. There are severalpractical protocols that take advantage of Network coding inwireless networks [7 10].In order to combine the benefits of TCP and Network cod-ing, [11] proposes a new protocol called TCP/NC.

4 TCP/NCmodifies TCP s acknowledgment (ACK) scheme such that itacknowledgesdegrees of freedominstead of individual pack-ets, as shown in Figure 1. This is done so by using the con-cept of seen packets in which the number of degrees offreedom received is translated to the number of consecutivepackets this paper, we present a performance evaluation ofTCP as well as TCP/NC in lossy networks. We adopt thesame TCP Model as in [2] consider standard TCPwith Go-Back-N pipelining. Thus, the standard TCP dis-cards packets that are out-of-order. We analytically showthe throughput gains of TCP/NC over standard TCP, andpresent simulations results that support this analysis. Wecharacterize the steady state throughput behavior of bothTCP and TCP/NC as a function of erasure rate, round-triptime (RTT), and maximum window size. Our work thusextends the work of [2] for TCP and TCP/NC in lossy wire-less networks. Furthermore, we use NS-2 ( Network Sim-ulator [12]) to verify our analytical results for TCP andTCP/NC.

5 Our analysis and simulations show that TCP/NCis robust against erasures and failures. TCP/NC is not onlyable to increase its window size faster but also maintain alarge window size despite losses within the Network . Thus,TCP/NC is well suited for reliable communication in lossynetworks. In contrast, standard TCP experiences windowclosing as losses are mistaken to be has been extensive research on Modeling and ana-lyzing TCP s performance [13 18]. Our goal is to present ananalysis for TCP/NC, and to provide a comparison of TCPand TCP/NC in a lossy wireless environment. We adoptPadhyeet al. s Model [2] as their Model provides a simpleyet good Model to predict the performance of TCP. It wouldbe interesting to extend and analyze TCP/NC in other TCPmodels in the paper is organized as follows. In Section 2, we providea brief overview of TCP/NC. In Section 3, we introduceour communication Model . In Section 4, we provide theintuition behind the benefit of using Network coding withTCP.

6 Then, we provide throughput analysis for TCP andTCP/NC in Sections 5 and 6, respectively. In Section 7, weprovide simulation results to verify our analytical results inSections 5 and 6. Finally, we conclude in Section OVERVIEW OF TCP/NCReference [11] introduces a newnetwork codinglayer be-p1p2p3 LostACK(p1)ACK(p1)p1+p2+p3 Lostseen(p1)seen(p2)p1+2p2+p3p1+2p2+2p3 TCPE2E-TCP/NCFigure 1: Example of TCP and TCP/NC. In the case ofTCP, the TCP sender receives duplicate ACKs for packetp1, which may wrongly indicate congestion. However, forTCP/NC, the TCP sender receives ACKs for packetsp1andp2; thus, the TCP sender perceives a longer round-triptime (RTT) but does not mistake the loss to be the TCP and IP in the protocol stack. The networkcoding layer intercepts and modifies TCP s acknowledgment(ACK) scheme such that random erasures does not affectthe transport layer s performance. To do so, theencoder,the Network coding unit under the sender TCP, transmitsRrandom linear combinations of the buffered packets for everytransmitted packet from TCP sender.

7 The parameterRistheredundancy factor. Redundancy factor helps TCP/NCto recover from random losses; however, it cannot mask cor-related losses, which are usually due to congestion. Thedecoder, the Network coding unit under the receiver TCP,acknowledgesdegrees of freedominstead of individual pack-ets, as shown in Figure 1. Once enough degrees of freedomsare received at the decoder, the decoder solves the set oflinear equations to decode the original data transmitted bythe TCP sender, and delivers the data to the TCP briefly note the overhead associated with Network cod-ing. The main overhead associated with Network coding canbe considered in two parts: 1) the coding vector (or coeffi-cients) that has to be included in the header; 2) the encod-ing/decoding complexity. For receiver to decode a networkcoded packet, the packet needs to indicate the coding coeffi-cients used to generate the linear combination of the originaldata packets. The overhead associated with the coefficientsdepend on the field size used for coding as well as the numberof original packets combined.

8 It has been shown that evena very small field size ofF256( bits = 1 byte per coef-ficient) can provide a good performance [11,19]. Therefore,even if we combine 50 original packets, the coding coeffi-cients amount to 50 bytes over all. Note that a packet istypically around 1500 bytes. Therefore, the overhead as-sociated with coding vector is not substantial. The secondoverhead associated with Network coding is the encoding anddecoding complexity, and the delay associated with the cod-ing operations. Note that to affect TCP s performance, thedecoding/encoding operations must take substantial amountof time to affect the round-trip time estimate of the TCPsender and receiver. However, we note that the delay causedthe coding operations is negligible compared to the networkround-trip time. For example, the Network round-trip timeis often in milliseconds (if not in hundreds of milliseconds),while a encoding/decoding operations involve a matrix mul-tiplication/inversion inF256which can be performed in afew [11], the authors present two versions of TCP/NC one that adheres to the end-to-end philosophy of TCP, inwhich coding operations are only performed at the sourceand destination; another that takes advantage of networkcoding even further by allowing any subset of intermediatenodes to re-encode.

9 Note that re-encoding at the interme-diate nodes is an optional feature, and is not required forTCP/NC to work. Here, we focus on TCP/NC with end-to-end Network coding, which we denote E2E-TCP/NC (or inshort E2E). However, a similar analysis applies to TCP/NCwith A Model FOR CONGESTION CONTROLWe focus on TCP s congestion avoidance mechanism, wherethe congestion control window sizeWis incremented by1/Weach time an ACK is received. Thus, when everypacket in the congestion control window is ACKed, the win-dow sizeWis increased toW+ 1. On the other hand, thewindow sizeWis reduced whenever an erasure/congestionis Model TCP s behavior in terms ofrounds[2]. WedenoteWito be the size of TCP s congestion control windowsize at the beginning of roundi. The sender transmitWipackets in its congestion window at the start of roundi, andonce allWipackets have been sent, it defers transmittingany other packets until at least one ACK for theWipacketsare received. The ACK reception ends the current round,and starts roundi+ simplicity, we assume that the duration of each roundis equal to a round trip time (RT T), independent assumes that the time needed to transmit a packet ismuch smaller than the round trip time.

10 This implies the fol-lowing sequence of events for each roundi: first,Wipacketsare transmitted. Some packets may be lost. The receivertransmits ACKs for the received packets. (Note that TCPuses cumulative ACKs. Therefore, if the packets 1,2,3,5,6arrive at the receiver in sequence, then the receiver ACKspackets 1,2,3,3,3. This signals that it has not yet receivedpacket 4.) Some of the ACKs may also be lost. Once thesender receives the ACKs, it updates its window size. As-sume thataipackets are acknowledged in roundi. Then,Wi+1 Wi+ reduces the window size for congestion control usingthe following two )Triple-duplicate (TD):When the sender receives fourACKs with the same sequence number, thenWi+1 )Time-out (TO):If the sender does not hear from thereceiver for a predefined time period, called the time-out period (which isTorounds long), then the sender closes itstransmission window,Wi+1 1. At this point, the senderupdates its TO period to 2 Torounds, and transmits onepacket.