UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Modeling, analysis and enhancement of transmission control protocol Bao, Wei 2011

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
24-ubc_2011_fall_bao_wei.pdf [ 936.68kB ]
Metadata
JSON: 24-1.0105062.json
JSON-LD: 24-1.0105062-ld.json
RDF/XML (Pretty): 24-1.0105062-rdf.xml
RDF/JSON: 24-1.0105062-rdf.json
Turtle: 24-1.0105062-turtle.txt
N-Triples: 24-1.0105062-rdf-ntriples.txt
Original Record: 24-1.0105062-source.json
Full Text
24-1.0105062-fulltext.txt
Citation
24-1.0105062.ris

Full Text

Modeling, Analysis and Enhancement of Transmission Control Protocol by Wei Bao B.E., Beijing University of Posts and Telecommunications, China, 2009 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) August 2011 c
 Wei Bao, 2011 ii Abstract Transmission control protocol (TCP) is one of the core protocols of the Internet protocol (IP) suite, which provides congestion control and reliable end-to-end connections in the Internet. In wireless environment, due to the random packet loss, many previous TCP variants primarily designed for wired networks may not perform well. In this thesis, we rst analyze the impact of random packet loss on the throughput performance of TCP CUBIC. Then, by incorporating online network coding, we propose a new TCP variant called TCP Vegas with online network coding (TCP VON), which can be eciently applied in wireless networks. In the rst part of this thesis, we propose a Markov chain model to determine the steady state throughput of TCP CUBIC in wireless environment. The proposed model considers both congestion loss and random packet loss caused by the wireless environ- ment. We derive the stationary distribution of the Markov chain and obtain the average throughput based on the stationary distribution. Simulations are carried out to validate the analytical model. In the second part of this thesis, we propose TCP Vegas with online network coding (TCP VON), which incorporates online network coding into TCP. TCP VON includes Abstract iii two mechanisms, namely congestion control and online network coding control. The congestion control is extended from TCP Vegas. For the online network coding control, the sender transmits redundant coded packets when packet losses happen. Otherwise, it transmits innovative coded packets. As a result, all the packets can be decoded consec- utively and the average decoding delay is small. We establish a Markov chain model to compute the analytical delay performance of TCP VON. We also conduct ns-2 simula- tions to validate the proposed analytical models. Finally, we compare the average delay and throughput performance of TCP VON and automatic repeat request (ARQ) network coding based TCP (TCP ARQNC) for dierent topologies. Results show that TCP VON outperforms TCP ARQNC. iv Preface A version of Chapter 2 has been published. Wei Bao, Vincent W.S. Wong, and Victor C.M. Leung, \A model for steady state throughput of TCP CUBIC," in Proc. of IEEE Global Communications Conference (Globecom), Miami, Florida, December 2010. I was responsible for designing the analytical model of TCP CUBIC. I also conducted simula- tions. Prof. Vincent Wong checked the system model and gave important suggestions. The paper was originally prepared by me, and further revised by all the co-authors. Chapter 3 has been nished under the guidance of Mr. Vahid Shah-Mansouri, Prof. Vincent Wong, and Prof. Victor Leung. I was responsible for algorithm proposal, an- alytical model establishment and simulations. Mr. Vahid Shah-Mansouri checked the analytical model and the simulation codes. Prof. Vincent Wong gave important sugges- tions on the presentation of the chapter. The chapter was originally prepared by me, and further revised by Mr. Vahid Shah-Mansouri, Prof. Vincent Wong, and Prof. Victor Leung. vTable of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix List of Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Transmission Control Protocol (TCP) . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Transmission Control Protocol (TCP) Basics . . . . . . . . . . . . 1 1.1.2 TCP Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.3 TCP in Wireless Networks . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Online Network Coding Based TCP . . . . . . . . . . . . . . . . . . . . . 8 Table of Contents vi 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 List of Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 A Model for Steady State Throughput of TCP CUBIC . . . . . . . . 15 2.1 System Model for TCP CUBIC . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1 Congestion Loss and Random Packet Loss . . . . . . . . . . . . . 16 2.1.2 Congestion Control for TCP CUBIC . . . . . . . . . . . . . . . . 17 2.1.3 Markov Chain Formulation . . . . . . . . . . . . . . . . . . . . . . 18 2.1.4 State Transition Probability . . . . . . . . . . . . . . . . . . . . . 20 2.1.5 Stationary Distribution and Throughput . . . . . . . . . . . . . . 23 2.2 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.1 Analytical Model Validation via Simulation . . . . . . . . . . . . 26 2.2.2 Throughput Performance of TCP CUBIC . . . . . . . . . . . . . 28 2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3 TCP VON: Online Network Coding Based TCP . . . . . . . . . . . . . 32 3.1 Preliminaries and Basic Denitions . . . . . . . . . . . . . . . . . . . . . 33 3.1.1 Packet Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.1.2 Preliminaries of Coded Packets . . . . . . . . . . . . . . . . . . . 36 3.1.3 Acknowledgement (ACK) . . . . . . . . . . . . . . . . . . . . . . 38 3.2 TCP VON Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Table of Contents vii 3.2.1 Sender Side Operation (R = 0 Case) . . . . . . . . . . . . . . . . 40 Congestion and Flow Control . . . . . . . . . . . . . . . . . . . . 41 Online Network Coding Control . . . . . . . . . . . . . . . . . . . 42 Algorithm of Sender Side Operation . . . . . . . . . . . . . . . . . 45 3.2.2 Receiver Side Operation . . . . . . . . . . . . . . . . . . . . . . . 47 3.2.3 Reliable Data Transfer . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.4 Example of the Algorithm of TCP VON with R = 0 . . . . . . . . 49 3.2.5 Tunable Parameter R in the Sender Side Operation . . . . . . . . 50 3.3 Decoding Delay Analysis of TCP VON . . . . . . . . . . . . . . . . . . . 52 3.3.1 System Model for R = 0 Case . . . . . . . . . . . . . . . . . . . . 55 3.3.2 System Model for the R > 0 Case . . . . . . . . . . . . . . . . . . 61 3.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.4.1 Performance Validation . . . . . . . . . . . . . . . . . . . . . . . . 65 3.4.2 Performance Comparison . . . . . . . . . . . . . . . . . . . . . . . 67 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 viii List of Tables 2.1 Denitions of xk, exk and Xk. . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 Denitions of Variables Used for Online Network Coding Control. . . . . 42 ix List of Figures 1.1 Finite state machine of TCP Reno [1]. . . . . . . . . . . . . . . . . . . . 4 2.1 Transition probability and average throughput calculation. . . . . . . . . 21 2.2 Markov chain example. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Root mean square (RMS) error versus total simulation time. . . . . . . . 27 2.4 Analytical and simulated average normalized throughput under dierent loss rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.5 The normalized average TCP CUBIC throughput under dierent bandwidth- delay product C RTT and loss rate . . . . . . . . . . . . . . . . . . . . 29 2.6 The normalized average throughput of TCP CUBIC under dierent win- dow growth factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.7 The normalized average throughput of TCP CUBIC under dierent . . 31 3.1 Decoding matrix at the receiver. . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 The two types of coded packets and ACK. . . . . . . . . . . . . . . . . . 39 3.3 Example of real gap and expected gap. . . . . . . . . . . . . . . . . . . . 49 3.4 Example of decoding delay. . . . . . . . . . . . . . . . . . . . . . . . . . . 52 List of Figures x 3.5 Examples of groups of packets with dierent number of corrupted packets. 55 3.6 Markov state transition for redundant factor R = 0. . . . . . . . . . . . . 58 3.7 Example of the expected decoding time with redundant factor R > 0. . . 61 3.8 Estimated Markov state transition for redundant factor R > 0. . . . . . . 62 3.9 Analytical and simulation results of average decoding delay for dierent values of loss probability p for R = 0, T0 = 5 ms, and L = 1250 bytes. . . 66 3.10 Analytical and simulation results of average decoding delay for dierent values of redundant factor R for p = 0:1, T0 = 5 ms, and L = 1250 bytes. 67 3.11 Simulation topology 1: Multihop tandem topology. . . . . . . . . . . . . 68 3.12 Simulation topology 2: Cross trac topology. . . . . . . . . . . . . . . . 68 3.13 Performance comparison for multihop tandem topology under dierent values of loss probability p. . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.14 Performance comparison for cross trac topology under dierent values of loss probability p. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.15 Performance comparison for cross trac topology under dierent values of redundant factor R. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 xi List of Acronyms 3GPP 3rd Generation Partnership Project ACK Acknowledgment AIMD Additive Increase Multiplicative Decrease ARQ Automatic Repeat-request CDF Cumulative Distribution Function ECN Explicit Congestion Notication FTP File Transfer Protocol HSTCP High Speed Transmission Control Protocol IETF Internet Engineering Task Force IP Internet Protocol LTE Long Term Evolution MAC Medium Access Control List of Acronyms xii MIMD Multiplicative Increase Multiplicative Decrease pdf probability density function RFC Request for Comments RMS Root Mean Square RTT Round Trip Time SACK Selective Acknowledgment STCP Scalable Transmission Control Protocol TCP Transmission Control Protocol TCP ARQNC Automatic Repeat Request Network Coding based TCP TCP VON TCP Vegas with Online Network Coding TDD Time Division Duplexing WiMAX Worldwide Interoperability for Microwave Access xiii Acknowledgements First, I would like to express my deepest gratitude to my supervisors, Prof. Vincent Wong and Prof. Victor Leung, for their patient guidance, constant encouragement, and excellent advice throughout my graduate study. Without their invaluable help, this work would not be possible. A special thanks goes to my colleague, Vahid Shah-Mansouri, who provided me with precious assistance during the completion of this thesis. I am also thankful to all my col- leagues in Prof. Wong's group: Vahid Shah-Mansouri, Man Hon Cheung, Keivan Ronasi, Pedram Samadi, Binglai Niu, Wenbo Shi, Xiaolei Hao, Jinbiao Xu and Shaobo Mao as well as other friends in the data communications group, for sharing their experiences and knowledge during the time of my study. Finally, I take this opportunity to express my profound gratitude to my beloved parents for their understanding, support, and endless love during my study in Canada. To them I dedicate this thesis. This research is supported by the Natural Sciences and Engineering Research Coun- cil (NSERC) of Canada and the British Columbia Innovation Council (BCIC) Natural Resources and Applied Sciences (NRAS) grant. 1Chapter 1 Introduction 1.1 Transmission Control Protocol (TCP) 1.1.1 Transmission Control Protocol (TCP) Basics The transmission control protocol (TCP) is one of the core protocols of the Internet protocol (IP) suite. It is a transport layer protocol and it supports congestion control and reliable end-to-end connections in the Internet [1]. The basic requirement, format and functions of TCP are dened in Internet Engineering Task Force (IETF) Request for Comments (RFCs) [2{4]. TCP connection is established by the three-way handshake process [1, 2]. Once the connection has been setup, the sender and receiver start to communicate with each other. At the sender side, the data is viewed as an ordered stream of bytes. It is divided into segments. Each segment is labeled by the number of the rst byte in the segment, which is called the sequence number. Then the segments are placed into the network in order. As the receiver accepts TCP segments, it sends acknowledgement (ACK) segments, indicating which byte it is expecting next in the ACK number eld. Chapter 1. Introduction 2 Two important mechanisms, namely 
ow control and congestion control are included in TCP [1, 2, 5]. The purpose of 
ow control is to properly control the transmission rate of sender in order to avoid the buer over
ow at the receiver. To achieve the 
ow control, a variable called the receive window (rwnd) is maintained, which indicates the free buer space available at the receiver. Another key component of TCP is the congestion control, which is used to avoid too many segments injected in the network. By congestion control, the sender limits the transmission rate it sends into the network if it perceives that there might be congestion along the path to the receiver. The sender maintains a variable called congestion window (cwnd), constraining the transmission rate. In summary, by taking both the 
ow control and congestion control into consideration, the unacknowledged amount of data at the sender cannot exceed either cwnd or rwnd LastByteSent LastByteAcked  min(cwnd; rwnd); (1.1) where LastByteSent is the sequence number of the last byte sent and LastByteAcked is the sequence number of the last byte ACKed. In most literature, in order to focus on congestion control mechanism, the buer at the receiver is assumed to be large enough. Thus, the rwnd constraint can be ignored and the unacknowledged amount of data is only limited by the value cwnd. Let RTT denote the average round trip time (RTT). The transmission rate can be roughly computed by cwnd=RTT . The sender can adjust the transmission rate by changing the value of cwnd, which can be regarded as the core of TCP congestion control mechanism. We brie
y review the congestion control mechanism of TCP Reno, a traditional TCP Chapter 1. Introduction 3 version. A nite state machine is used to describe of the congestion control of TCP Reno, as shown in Fig. 1.1 [1]. There are namely three states: slow start, congestion avoidance and fast recovery. When a TCP connection begins, the slow start phase initializes a congestion window to 1 segment. When ACKs are returned, the congestion window increases by one segment for each ACK. The value of cwnd roughly doubles every RTT during the slow start phase. A threshold value Threshold is maintained to determine the window size at which slow start ends. The sender leaves slow start and enters congestion avoidance if cwnd > Threshold. In the congestion avoidance phase, cwnd is increased by 1 segment every RTT if there is no loss event. If there is a loss event, it is regarded as indication of network congestion and the sender will decrease cwnd. If the loss event indicated by three duplicate ACKs, the state enters fast recovery and cwnd is halved (dupACKcount is the counter to record the number of duplicate ACKs). If there is a loss indicated by timeout, the state will go to the slow start state and Threshold is set to be half of the cwnd. Note that in most cases when the networks are not heavily congested, loss events are indicated by three duplicate ACKs rather than timeout. Therefore, cwnd is additively increased if there is no congestion and is multiplicatively decreased if the sender detects a loss event. This congestion control algorithm is referred to as the additive increase, multiplicative decrease (AIMD) algorithm. Chapter 1. Introduction 4 Slow Start Congestion Avoidance Fast Recovery cwnd > Threshold Timeout Threshold = cwnd/2 cwnd = 1 segment dupACKcount = 0 new ACK cwnd = cwnd+1 dupACKcount = 0 duplicate ACK dupACKcount++ timeout Threshold = cwnd/2 cwnd = 1 segment dupACKcount = 0 new ACK cwnd = cwnd+1/cwnd dupACKcount = 0 dupACKcount = 3 Threshold = cwnd/2 cwnd = Threshold+3 New ACK cwnd = Threshold dupACKcount = 0 Timeout Threshold = cwnd/2 cwnd = 1 segment dupACKcount = 0 dupACKcount = 3 Threshold = cwnd/2 cwnd = Threshold+3 Duplicate ACK dupACKcount ++ Threshold = 64 KB cwnd = 1 segment dupACKcount = 0 Figure 1.1: Finite state machine of TCP Reno [1]. 1.1.2 TCP Variants Besides TCP Reno, there are many variations of TCP proposed in the literature. The TCP variants which have been deployed in the current Internet include selective acknowl- edgment (SACK) [6] and New Reno [7]. SACK improves TCP congestion control algorithm in the face of multiple packet losses within a short time. With SACK, the receiver can inform the sender about the sequence numbers of all the lost packets, so that the sender can retransmit only the packets that Chapter 1. Introduction 5 have actually been lost. TCP New Reno made modications based on TCP Reno. In the situation that SACK is not available, it improves retransmission process during the fast recovery phase so that the multiple packet losses within a short time can be recovered more eciently. There are some other important TCP variants, such as Scalable TCP (STCP) [8], TCP Vegas [9], and CUBIC [10]. STCP [8] is designed specically for long-distance, high-speed links, which employs multiplicative increase multiplicative decrease (MIMD) congestion control algorithm. The congestion window size will grow a constant value for each new ACK, and it will multiplicative decrease when there is a loss event. TCP Vegas [9] congestion control algorithm is delay-based, which emphasizes packet delay, rather than packet loss, as a signal to determine the rate at which to send packets. The transmission rate is adjusted based on the measured round trip RTT and the base RTT BaseRTT . BaseRTT is set to be the minimum of all measured RTT s and it is commonly the RTT of the rst packet in the TCP connection. There are also two predetermined threshold values a and b, a < b. The default setting is a = 1 packet and b = 3 packets. The congestion window size cwnd is adjusted as follows. If  cwnd BaseRTT  cwnd RTT  BaseRTT < a, then cwnd is linearly increased. If  cwnd BaseRTT  cwnd RTT   BaseRTT > b, then cwnd is linearly decreased. TCP CUBIC [10] is implemented and used by default in Linux kernels 2.6.19 version. It is designed for long-distance, high latency links. It combines additive increase and binary search increase to achieve good scalability as well as RTT fairness. TCP CUBIC Chapter 1. Introduction 6 performs well in wired networks with large bandwidth-delay product. In addition, the window growth function of TCP CUBIC is dened in real-time instead of RTT, so that the window growth rate is independent of RTT, which guarantees the RTT fairness. In this thesis, we focus on the performance analysis of TCP CUBIC in wireless networks in Chapter 2. For TCP CUBIC congestion control algorithm, the congestion window size is a cubic function of time since the last loss event. Let  denote the elapsed time from the last window reduction. The window size just before the last window reduction is denoted by x. The constant  denotes the window growth factor. A large value of  implies faster window growth rate. The constant  represents the multiplicative decrease factor. The window reduces to x at the time of the last reduction. Let w(x; ) denote the window size as a function of x and  . The congestion window of CUBIC is determined by [10]1 w(x; ) =    3 p (1 )x= 3 + x: (1.2) Despite the fact that TCP CUBIC has been implemented in Linux operating systems (OS), analytical models for the performance of TCP CUBIC are few. The previous study of TCP CUBIC are mainly conducted via simulations and experiments. Leith et al. performed experimental evaluation for TCP CUBIC in [11] and Bateman et al. presented a simulation based study of BIC, CUBIC, scalable TCP (STCP), and high- speed TCP (HSTCP) in [12]. Moreover, most of the previous analysis of TCP CUBIC 1The  in (2.4) corresponds to (1  ) of (1) in [10]. As a result w(x; 0) = x, meaning that the window reduces to x at the time of last reduction. Chapter 1. Introduction 7 [10{12] focus on wired networks. There are very few related work on the performance of TCP CUBIC for wireless networks. In Chapter 2 of this thesis, we propose an analytical model to analyze the performance of TCP CUBIC in wireless networks. 1.1.3 TCP in Wireless Networks With the development of wireless communication technology, more and more hosts access the Internet through wireless mode. However, traditional TCP variants were primarily designed for wired networks and they may not be ecient in wireless scenarios. As dis- cussed in literature, in wireless networks, if we directly apply TCP variants designed for wired networks (e.g., TCP Reno, Vegas and STCP), it may result in degraded end-to-end performance [13{16]. Our study in Chapter 2 also shows that random packet loss reduces the normalized average throughput of TCP CUBIC, especially for end-to-end 
ow with large bandwidth-delay product. In wired networks, it is assumed that random packet loss is negligible and packet losses are mainly caused by congestion (i.e., some buers in the route of transmission are full and some packets are discarded). In wireless net- work, packet losses are probably caused by the lossy nature of wireless links (e.g. deep fading and temporary disconnections due to hando). Traditional TCP congestion con- trol algorithms misinterpret random packet losses as congestion losses, causing degraded performance. There are many TCP variants proposed to adapt the features of wireless networks. For satellite networks, TCP-Peach [17] was proposed to tackle the problem of long propaga- Chapter 1. Introduction 8 tion delay of satellite link. For ad-hoc networks, ATCP [18] was designed as an end-to-end solution to improve TCP throughput. It relies on explicit congestion notication (ECN) to distinguish congestion losses from random packet losses. For mixed wired and wireless networks, split TCP variants such as I-TCP [19] and M-TCP [20] were proposed, they separate the end-to-end connections into two split TCP connections, one in the wired part and the other in the wireless part. Other TCP variants, such as Freeze-TCP [21], TCP Veno [22], TCP Westwood [23] and TCP Jersey [24] are also proposed for wireless networks. In this thesis, we also propose a new TCP algorithm, TCP VON, to deal with both congestion losses and random packet losses eciently. It is expected to perform well in mixed wired and wireless networks. Dierent from the previous designs, we incorporate the online network coding technique into our new TCP algorithm. The online network coding technique will be introduced in Section 1.2 and the TCP VON will be presented in Chapter 3. 1.2 Online Network Coding Based TCP Network coding was introduced by Ahlswede et al. in [25]. It has been shown that network coding can increase the throughput and improve the reliability of the end-to-end communication [25{27]. There are several related works for network coding in a practical setting. Chou et al. [28] proposed that the coecients used for linear combination of the packets be stored in the packet header. Katti et al. [29] proposed COPE which uses Chapter 1. Introduction 9 opportunistic coding to increase the throughput. Chachulski et al. [30] proposed MORE which uses opportunistic routing to further improve the throughput performance. For the schemes presented in [28{30], the source divides native data packets into generations or blocks. Network coding is performed within the same generation at the source and intermediate nodes. The source starts to transmit the next generation of the packets only after being acknowledged by the destination that the current generation of the packets have been decoded. It is shown in [31] that for generation based network coding, the max-
ow min-cut capacity for the end-to-end communication can be achieved if the generation size is suciently large. However, the decoding delay can be large since the destination has to receive enough independent coded packets before decoding a generation. CodeOR was proposed in [32] to overcome the problem of long decoding delay by allowing multiple generations to be transmitted together. The concept of online network coding was proposed by Sundararajan et al. in [33] and discussed further in [34{36]. For online network coding, at the source, each native packet is ready to be combined and transmitted as soon as it is created. At the destination, by performing linear operations on the received packets, the packets can be decoded consecutively instead of generation by generation. In [34], an online network coding scheme was proposed to maximize the throughput for a packet erasure broadcast channel. In [35], a new encoding rule was proposed to guarantee small decoding delay by recovering packet losses within reasonable time. In [36], the performance of online random linear network coding approach for time division duplexing channels under Poisson arrivals was Chapter 1. Introduction 10 studied. SlideOR [37] is an online network coding scheme, which uses a moving sliding window at the source to determine the set of native packets to be coded. Some of the previous works on online network coding are limited in dierent aspects. The work in [34] only analyzed the multicast case with one source and three receivers. The work in [35] assumed zero feedback delay, which is not the case in real networks. In [36], although the scheme is called online network coding, it is fundamentally generation based network coding with an improved online feedback mechanism. In [37], the network coding scheme is tailored for wireless mesh networks. For a network with a mixed wired and wireless network nodes, since the broadcast nature of wireless channels is not available in the wired part, the opportunistic routing based scheme has no advantage over routing. Recently, the joint problem of network coding and transport layer design has received much attention. The work in [38] and [39] showed that the combination of network coding in medium access control (MAC) or network layer and TCP can have signicant impact on the throughput, fairness and delay performance of wireless networks. Hassayoun et al. [40] analyzed the performance of TCP in coded wireless mesh networks with random packet loss. However, only the butter
y topology was considered and the model cannot be extended for general network topologies. Chen et al. [41] proposed a distributed rate control algorithm for network coding based on the utility maximization model. To implement the algorithm in real networks, a complex interface between network coding and TCP is required. It is because the proposed algorithm does not support sliding window and is not compatible with current TCP. In [42], a congestion control algorithm Chapter 1. Introduction 11 for unicast 
ows over coded packet networks using COPE [29] was proposed based on network utility maximization. Although an interface between COPE and transport layer was presented in [42], it can only improve throughput performance by increasing the coding opportunity. Moreover, the decoding delay was not studied in [42]. An automatic repeat request (ARQ) network coding based TCP protocol (which is referred to as TCP ARQNC in this thesis) was proposed in [43] and extended in [44]. This approach gives a new solution for the sliding window based TCP algorithm. However, packets of one generation are decoded when the receiver receives enough independent coded packets. This can potentially lead to a large decoding delay. In [45], an analytical model was established to evaluate the throughput performance of network coded TCP proposed in [43]. However, the delay performance was not studied. Our goal in Chapter 3 is to design an online network coding based TCP for real time applications (e.g., VoIP, video conferencing) such that the packets can be decoded with a small decoding delay. The proposed protocol should be able to distinguish between random packet loss and congestion loss for wireless links. To settle these issues, our proposed algorithm includes congestion control and online network coding control. For congestion control, we use TCP Vegas [9]. We can distinguish random packet losses from the congestion losses using the dierence between the time that a packet is transmitted and the time that the sender is notied the packet is lost. The online network coding control is used to address the eect of random packet loss for wireless links. The sender chooses to transmit either a packet with new information or a redundant packet according Chapter 1. Introduction 12 to the feedback information. Meanwhile, packets are decoded consecutively instead of generation by generation so that the average decoding delay is small. Another advantage of our protocol which makes it practical is that there is no need to change the protocol stack at the intermediate nodes. We only need to modify TCP in the transport layer at the sender and receiver. Since we use TCP Vegas as the congestion control algorithm, the TCP friendly feature is also guaranteed. 1.3 Contributions This thesis covers several aspects of modeling, analysis and enhancement of transmission control protocol. The results are divided into two chapters. In Chapter 2, we propose an analytical model to determine the steady state throughput of TCP CUBIC in wireless environment. In Chapter 3, we propose a new mechanism that incorporates online network coding into TCP. The contributions in each chapter are as follows:  In Chapter 2, we formulate an analytical model to analyze the performance of TCP CUBIC in wireless networks. We propose a Markovian model to determine the steady state throughput of TCP CUBIC. The model takes into account both buer router and fading in the wireless environment by considering both congestion loss and random packet loss. Then, we derive the stationary distribution of the Markov chain and obtain the average TCP throughput. The analytical model is Chapter 1. Introduction 13 validated via simulations. Finally, we evaluate the throughput performance of TCP CUBIC. Results show that random packet loss reduces the normalized average throughput more for end-to-end 
ow with large bandwidth-delay product. We propose an improvement to increase the throughput performance of TCP CUBIC by moderately increasing the window growth factor and the multiplicative decrease factor.  In Chapter 3, we propose TCP Vegas with online network coding (TCP VON), which is a combination of TCP Vegas and online network coding with low decoding delay. We establish an analytical framework to model the TCP VON and derive the average decoding delay using Markov chain. We also conduct ns-2 simulations to validate the analytical model. We compare the average decoding delay and through- put performance of TCP VON with TCP ARQNC [43] under dierent topologies. The results show that for a xed network throughput, TCP ARQNC has a larger average decoding delay than TCP VON. Under the same decoding delay constraint, our proposed protocol provides a higher throughput than the TCP ARQNC. 1.4 List of Publications The following publications have been completed based on the work in this thesis.  Wei Bao, Vincent W.S. Wong, and Victor C.M. Leung, \A model for steady state throughput of TCP CUBIC," in Proc. of IEEE Global Communications Conference Chapter 1. Introduction 14 (Globecom), Miami, Florida, December 2010. 1.5 Structure of the Thesis The rest of this thesis is organized as follows. In Chapter 2, we present the analytical model of the throughput performance of TCP CUBIC in wireless networks. In Chapter 3, we present the algorithm design, analytical model and the simulation results of TCP VON. Finally, conclusions and future work are given in Chapter 4. 15 Chapter 2 A Model for Steady State Throughput of TCP CUBIC In the transport layer, CUBIC is a TCP-friendly high-speed variant, in which the window size is a cubic function of time since the last loss event. TCP CUBIC is implemented in Linux operating systems and performs well in wired networks with large bandwidth- delay product. Most of the evaluations of TCP CUBIC are conducted via simulations or experiments. Analytical models for TCP CUBIC are few. In this chapter, we propose a Markovian model to determine the steady state throughput of TCP CUBIC in wireless environment. The proposed model considers both congestion loss and random packet loss due to fading. We derive the stationary distribution of the Markov chain and obtain the average throughput based on the stationary distribution. Then, we conduct simulations to validate our analytical model. Finally, we analyze the throughput performance of TCP CUBIC based on our model. The publication [46] has been completed based on the work in this chapter. Chapter 2. A Model for Steady State Throughput of TCP CUBIC 16 2.1 System Model for TCP CUBIC In this section, we rst present the network model and state the assumptions of the system model. We then describe the window behavior of TCP CUBIC as a Markov chain. After that, we derive the stationary distribution of the Markov chain and obtain the steady state throughput based on the stationary distribution. 2.1.1 Congestion Loss and Random Packet Loss Consider the network where the bottleneck link is the last hop wireless link. This wireless bottleneck link has a capacity of C bits/sec and is smaller than the capacities of other intermediate links between the source and destination pair. This scenario is applicable to the scenario as in 3GPP (Third Generation Partnership Project) LTE (Long Term Evolution) or WiMAX (Worldwide Interoperability for Microwave Access). The source has a large le to send to the destination. We assume that packet losses are caused by two factors: congestion loss and random packet loss. Congestion loss happens when the transmission rate attains the maximum capacity C of the bottleneck link. We assume that the average RTT is a constant, which is a common assumption in loss-based TCP analytical modeling (e.g., [47]). Thus, the maximize congestion window size W is W = C RTT: (2.1) Equivalently, congestion loss happens when window size attains the maximum window Chapter 2. A Model for Steady State Throughput of TCP CUBIC 17 size W . Random packet loss is caused by fading or interference in the wireless link. We assume that random packet loss experiences a random Poisson process with rate . This assumption has also been made in [40]. Given a time instant t0, the time duration loss from time t0 to the next loss event is a random variable with an exponential distribution. The probability density function (pdf) of loss is f(loss) =  exp (loss); loss > 0: (2.2) Given the time instant t0, the probability that the next loss event happens within the time interval (t0 + T1; t0 + T2] is P (T1 < loss  T2) = exp (T1) exp (T2): (2.3) 2.1.2 Congestion Control for TCP CUBIC As discussed in Section 1.1, for TCP CUBIC, the window size is a cubic function of time since the last loss event. w(x; ) =    3 p (1 )x= 3 + x: (2.4) where  denotes the elapsed time from the last window reduction; the window size just before the last window reduction is denoted by x; the constant  denotes the window growth factor; the constant  represents the multiplicative decrease factor; w(x; ) de- notes the window size as a function of x and  . Chapter 2. A Model for Steady State Throughput of TCP CUBIC 18 The congestion window reduction occurs due to either congestion loss or random packet loss event. When window reduction happens, the window size reduces to  times the window size just before the loss event. After that, it grows according to (2.4). Let D(x; y) denote the time duration in which the window size grows from x to y without encountering another loss event, after the last window reduction happened at the value of x. We have D(x; y) = 3 r y  x  + 3 r (1 )x  : (2.5) 2.1.3 Markov Chain Formulation We now present our proposed Markovian model. The range of congestion window size (0;W ] is partitioned into N equal-sized intervals. The ith interval is ((i1)W=N; iW=N ]. If the congestion window size is in the ith interval, we regard the window size to be the midpoint of the interval, with value (i  0:5)W=N , denoted by ai. This is similar to quantization: we map a continuous range of values (0;W ] to a nite set of values fa1; a2; :::; aNg. The number of intervals N can also be regarded as quantization precision: when N increases, the mapping becomes more precise. The quantization is an essential step of the Markov chain formulation: the nite set of values derived through quantization corresponds to the Markov chain with N states. The Markov chain is observed at each time instant when there is a window reduction (i.e., loss event). The kth time instant, where k = 1; 2; : : :, corresponds to the kth window reduction. For a TCP CUBIC session, when the kth window reduction is just about to Chapter 2. A Model for Steady State Throughput of TCP CUBIC 19 happen, the congestion window size is denoted by xk. xk is in one of the N intervals, and is mapped to exk, exk 2 fa1; a2; :::; aNg. When exk = ai, the state of the TCP CUBIC session is in the ith state at the time instant k. Let Xk denote the state at the time instant k. We have Xk = i and exk = ai if xk 2 ((i 1)W=N; iW=N ]. Table 2.1 shows the denition of xk, exk and Xk. Let random variable k denote the time duration between the time instant k (i.e., the kth window reduction) and the time instant (k+1) (i.e., the (k+1)th window reduction). Given xk, the maximum value of congestion window size is W . The maximum value of k is D(xk;W ). Consider the state sequence X1; X2; : : : ; Xk. From (2.4), the congestion window size at the next loss event after time instant k is only related to xk and k. That is xk+1 = w(xk; k) =  k  3 r (1 )xk  !3 + xk; k  D(xk;W ): (2.6) Thus, xk+1 is independent of x1; x2; : : : ; xk1. We have P (xk+1 j xk; xk1; : : : ; x1) = P (xk+1 j xk): (2.7) Furthermore, the conditional probabilities of exk+1 and Xk+1 are as follows: P (exk+1 j exk; exk1; : : : ; ex1) = P (exk+1 j exk); (2.8) and P (Xk+1 j Xk; Xk1; : : : ; X1) = P (Xk+1 j Xk): (2.9) Chapter 2. A Model for Steady State Throughput of TCP CUBIC 20 Table 2.1: Denitions of xk, exk and Xk. Symbol Denition xk When the kth window reduction is just about to happen, the congestion window size is xk, xk 2 (0;W ]. The mapped value of xk at the time instant k, exk if (i 1)W=N < xk  iW=N , then exk = ai = (i 0:5)W=N . Xk The state at the time instant k, if (i 1)W=N < xk  iW=N , then Xk = i, Xk 2 f1; 2; : : : ; Ng. Therefore, the state sequence, X1; X2; : : :, is a Markov chain. 2.1.4 State Transition Probability Fig. 2.1 shows the process when the state transits from the ith state at the time instant k to jth (j 6= N) state at the time instant (k + 1) (i.e., Xk = i and Xk+1 = j). At time instant k, the loss event occurs, the congestion window size is reduced from ai to ai. After that, the congestion window size grows within the interval of ((j1)W=N; jW=N ]. Chapter 2. A Model for Steady State Throughput of TCP CUBIC 21 0 W Xk=i Xk+1=j Loss happens here. jW/N (j-1)W/N k k+1 ȕai time Window size sij iW/N (i-1)W/N .. . min ijW max ijW ijW lossW 1k jx a  1kx  k ix a  Figure 2.1: Transition probability and average throughput calculation. At the time instant (k + 1), the congestion cannot happen below the value ai.Thus, Pij = 0; if jW=N < ai: (2.10) Since ai = (i 0:5)W=N , when the inequality jW=N < ai holds, it is equivalent to state j < (i 0:5). When the state transits from the ith state to the jth state, it is in the interval ((j  1)W=N; jW=N ] that a loss event happens. We have minij < loss  maxij ; (2.11) where minij is the minimum time duration that the state transits from the ith state to the jth state; it is the time that the congestion window size grows from ai to (j  1)W=N Chapter 2. A Model for Steady State Throughput of TCP CUBIC 22 after the window reduction happened at the value of ai. minij = (D(ai; (j  1)W=N))+ (2.12) =  3 r (j  1)W=N  ai  + 3 r (1 )ai  !+ ; where (a)+ = max(a; 0). maxij is the maximum time duration that the state transits from the ith state to the jth state. It is given by maxij = D(ai; jW=N) (2.13) = 3 r jW=N  ai  + 3 r (1 )ai  : Thus, according to (2.3), if jW=N  ai (i.e., j  (i  0:5)) and j 6= N , then the state transition probability is Pij = P  (D(ai; (j  1)W=N))+ < loss  D(ai; jW=N)  = exp    D  ai; (j  1)W N +! (2.14)  exp  D  ai; jW N  = exp    3 r (j  1)W=N  ai  + 3 r (1 )ai  !+!  exp    3 r jW=N  ai  + 3 r (1 )ai  !! : When state j is equal to N (i.e., j = N), we have PiN = 1 N1X j=1 Pij: (2.15) Fig. 2.2 shows an example of the Markov chain when N = 5 and  = 0:5. According to (2.10), (2.14) and (2.15), the ith state can transit to the jth state if j  (i 0:5). Chapter 2. A Model for Steady State Throughput of TCP CUBIC 23 1 2 3 4 5 Figure 2.2: Markov chain example. 2.1.5 Stationary Distribution and Throughput Let (1; 2; : : : ; N) denote the stationary distribution of the Markov chain, in which i is the stationary probability of the ith state. Given the state transition probabilities from (2.10), (2.14) and (2.15), we can derive the stationary distribution (1; 2; : : : ; N) by solving NX i=1 iPij = j; j 2 f1; 2; : : : ; Ng; (2.16) and NX i=1 i = 1: (2.17) The duration that the state transits from the ith state to the jth state is a random variable in the interval of  (D(ai; (j1)W=N))+; D(ai; jW=N)  . WhenN is large enough, we can regard ij = (D(ai; (j  0:5)W=N))+; (2.18) as the average time duration that the state transits from the ith state to the jth state. Chapter 2. A Model for Steady State Throughput of TCP CUBIC 24 Let sij = R ij 0 w(ai; t)dt, which is the shaded area in Fig. 2.1. sij = Z ij 0 w(ai; t)d = Z ij 0 0@ t 3r(1 )ai  !3 + ai 1A d = aiij +  4  (ij  LC)4  L4C  ; (2.19) where LC = 3 q (1)ai  . Let rij denote the total transmission amount while the state transits from the ith state to the jth state. From (2.19), we have rij = Z ij 0 w(ai; t) RTT d = sij RTT : (2.20) Let t denote the total transmission time and r(t) denote the total transmission amount during t. Mij(t) denotes the occurrence times of the ith state transition to the jth state during t. When t is large, by the law of large numbers, the limit lim t!1 Mij(t)PN i=1 PN j=1Mij(t) is equal to the occurrence probability of the ith state transition to the jth state. Thus, the Chapter 2. A Model for Steady State Throughput of TCP CUBIC 25 average normalized TCP CUBIC throughput is x = lim t!1 r(t) t C = RTT W lim t!1 NP i=1 NP j=1 Mij(t)rij NP i=1 NP j=1 Mij(t)ij = 1 W lim t!1 NP i=1 NP j=1 Mij(t)(rij RTT ) NP i=1 NP j=1 Mij(t)ij = 1 W lim t!1 NP i=1 NP j=1 Mij(t)sij NP i=1 NP j=1 Mij(t)ij = 1 W lim t!1 NP i=1 NP j=1  Mij(t)= NP p=1 NP q=1 Mpq(t)  sij  NP i=1 NP j=1  Mij(t)= NP p=1 NP q=1 Mpq(t)  ij  = 1 W lim k!1 NP i=1 NP j=1 P (Xk+1 = j;Xk = i)sij NP i=1 NP j=1 P (Xk+1 = j;Xk = i)ij = 1 W NP i=1 NP j=1 iPijsij NP i=1 NP j=1 iPijij : (2.21) 2.2 Performance Evaluation In this section, we rst validate our proposed analytical model via simulation. We then present the TCP throughput results under dierent parameters. Chapter 2. A Model for Steady State Throughput of TCP CUBIC 26 2.2.1 Analytical Model Validation via Simulation We develop a discrete-event simulator to validate the accuracy of our proposed analytical model. Let Mi, where i 2 f1; 2; : : : ; Ng, denote the counter of the ith state, K denote the total simulation time. We rst initialize W;N; ;  and set Mi to be equal to 0 at the beginning; x1 is randomly generated in (0;W ]. We simulate the behavior of TCP CUBIC starting from the time instant k = 1 to k = K. The simulation at each time instant is performed as follows: At each time instant k, we rst calculate exk and Xk according to xk and update the state counter (i.e., increase MXk by 1). Then, we simulate k, which is the time duration from the time instant k to the next loss event. The value of k is set to be equal to min(loss; D(xk;W )), in which loss is randomly generated according to its pdf in (2.2). Based on xk and k, the window size at the next window reduction xk+1 = w(xk; k) can be calculated. The stationary distribution as well as the average TCP CUBIC throughput can then be determined. For performance metric, we consider the root mean square (RMS) error, which is dened as RMS = sPN i=1(i  ei)2 N ; (2.22) where i and ei are obtained via analytical model and simulation, respectively. The RMS error re
ects the gap between the analytical results and the simulation results. Fig. 2.3 shows the RMS error under dierent simulation time. The parameters are as follows: C = 100 Mb/s, RTT = 100 ms,  = 1 Mb/s,  = 0:5,  = 1 s1. The two curves show that when the N is increased, the RMS error will decrease. This illustrates that an Chapter 2. A Model for Steady State Throughput of TCP CUBIC 27 10 3 10 4 10 5 10 -4 10 -3 10 -2 10 -1 Simulation time R o o t m e a n  s q u a re  e rr o r N = 20 N = 100 Figure 2.3: Root mean square (RMS) error versus total simulation time. increase in simulation time leads to the simulation results being closer to the analytical results. In addition, we notice that when the number of intervals N increases, the RMS error becomes smaller. This illustrates that larger N will lead to more accurate analytical results. Fig. 2.4 shows the analytical and simulated average throughput under dierent loss rate . The parameters chosen are as follows: C = 100 Mb/s, RTT = 100 ms,  = 1 Mb/s, and  = 0:5. This gure shows that the analytical results and simulation results agree with each other. Chapter 2. A Model for Steady State Throughput of TCP CUBIC 28 10 -2 10 -1 10 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Loss rate O  (s-1) N o rm a li z e d  t h ro u g h p u t Analytical results Simulation results Figure 2.4: Analytical and simulated average normalized throughput under dierent loss rate . 2.2.2 Throughput Performance of TCP CUBIC We now present the throughput results of TCP CUBIC based on our proposed Markovian model. Fig. 2.5 shows the throughput performance of TCP CUBIC under dierent bandwidth- delay product C  RTT and loss rate , when  = 1 Mb/s and  = 0:5. The number of intervals N is set to 100. Results show that even when  is very small, the normalized av- erage throughput will not attain 1. This is because even when there is no random packet loss, there are still congestion losses, causing multiplicative decrease when the window size is equal to W . Fig. 2.5 also shows that if C RTT increases, the normalized average throughput decreases. Random packet loss reduces the normalized average throughput Chapter 2. A Model for Steady State Throughput of TCP CUBIC 29 10 -2 10 -1 10 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Loss rate O (s-1) N o rm a li z e d  t h ro u g h p u t C˜ RTT = 1 Mb C˜ RTT = 10 Mb C˜ RTT = 100 Mb Figure 2.5: The normalized average TCP CUBIC throughput under dierent bandwidth-delay product C RTT and loss rate . of large bandwidth-delay product links more. Our analytical results show that, for i; j 2 f1; 2; : : : ; Ng, Pij; i; sijW and ij depend on the value of CRTT  (i.e., bandwidth-delay product over window growth factor). Therefore, the normalized throughput depends on the value of CRTT  . The eect of an increase of bandwidth-delay product is equivalent to a decrease of the window growth factor, leading to a decrease of the normalized throughput. Therefore, in contrast to the wired cases, large bandwidth-delay product will decrease the normalized throughput of TCP CUBIC in wireless scenarios due to the random packet loss. Fig. 2.6 shows the normalized average throughput under dierent window growth factor  with C = 100 Mb/s, RTT = 100 ms, N = 100, and  = 0:5. Results show Chapter 2. A Model for Steady State Throughput of TCP CUBIC 30 10 -1 10 0 10 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 D  (Mb/s) N o rm a li z e d  t h ro u g h p u t O = 0.01 s-1 O = 0.1 s-1 O = 0.5 s-1 O = 1 s-1 Figure 2.6: The normalized average throughput of TCP CUBIC under dierent window growth factor . that by moderately increasing , the throughput performance will improve. When  = 1 s1, the average normalized throughput increases by about 806% when  grows from 0:1 Mb/s to 10 Mb/s. When  is small, increasing  will bring less throughput gain. In the gure, when  = 0:01 s1, the normalized average throughput is not improved much. Fig. 2.7 shows the normalized average throughput under dierent  with C = 100 Mb/s, RTT = 100 ms, N = 100, and  = 1 Mb/s. Results show that by moderately increasing , the throughput performance will improve. When  = 1 s1, the average normalized throughput increases by about 137% when  grows from 0:5 to 0:9. When  is small (e.g.,  = 0:01 s1), increasing  will bring less throughput gain. Chapter 2. A Model for Steady State Throughput of TCP CUBIC 31 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 E N o rm a li z e d  t h ro u g h p u t O  = 0.01 s-1 O  = 0.1 s-1 O  = 0.5 s-1 O  = 1 s-1 Figure 2.7: The normalized average throughput of TCP CUBIC under dierent . 2.3 Summary In this chapter, we proposed an analytical model to determine the steady state throughput of TCP CUBIC in wireless environment. We considered both congestion loss and random packet loss and established a Markov model. We derived the stationary distribution of the Markov chain and obtained the average throughput based on the stationary distribution. The accuracy of the model was validated via simulation. Based on our proposed model, we evaluated the throughput performance of TCP CUBIC. Results showed that random packet loss reduces the normalized average throughput more for end-to-end 
ow with large bandwidth-delay product. In wireless environment, we showed that the throughput of TCP CUBIC can be improved by moderately increasing the window growth factor and the multiplicative decrease factor . 32 Chapter 3 TCP VON: Online Network Coding Based TCP In this chapter, we propose TCP Vegas with online network coding (TCP VON), which incorporates online network coding into TCP and it can be eciently applied in mixed wired and wireless networks. The scheme requires minor modications to the curren- t protocol stack at the sender and the receiver. TCP VON includes two mechanisms, namely congestion control and online network coding control. The congestion control is extended from TCP Vegas so that congestion losses become rare and all the packet losses can be regarded as random packet losses. For the online network coding control, the sender transmits redundant coded packets when packet losses happen. Otherwise, it transmits innovative coded packets. As a result, all the packets can be decoded consec- utively instead of generation by generation and the average delay from sending a packet at the sender to decoding it at the receiver is small. We establish a Markov chain model to compute the analytical delay performance of TCP VON. We also conduct ns-2 sim- ulations to validate the proposed analytical models. Finally, we compare the delay and throughput performance of TCP VON and TCP ARQNC for dierent topologies. Results Chapter 3. TCP VON: Online Network Coding Based TCP 33 show that TCP VON outperforms TCP ARQNC. 3.1 Preliminaries and Basic Denitions In this section, we present the preliminaries and basic denitions of TCP VON. We rst dene dierent types of packets and then present the basic idea of how packets are coded in an online feature. 3.1.1 Packet Types According to the previous works in [28, 29, 32, 43], there are two types of data packets in the network, namely native packets and coded packets. Native packets are the original packets generated by the sender, which are treated as vectors over a nite eld Fq of size q. Each native packet has a unique index number k corresponding to the order it is generated. Let pk denote the kth native packet. In this chapter, the native packets are with the same size (shorter packets are padded with zeros). A coded packet is a linear combination of several native packets. For example, if a coded packet q is a linear combination of packets p1;p2; : : : ;pm, then q = Pm i=1 ipi, where i is a non-zero multiplicative coecient randomly selected from the eld Fq. The native packets can be divided into dierent categories. A native packet pk is called a sent packet when the sender has transmitted a coded packet q = kpk +P l 6=k lpl. That is, pk is combined in a coded packet q, and q is transmitted by the sender. In this chapter, we use the term transmit for coded packets and the term send Chapter 3. TCP VON: Online Network Coding Based TCP 34 for native packets. A native packet pk is sensed when the receiver has received a coded packet q = kpk + P l 6=k lpl. That is, pk is combined in a coded packet q, and q is received at the receiver. Otherwise, pk is unsensed. Packet pk is acknowledged as sensed when the sender receives an ACK indicating that pk has been sensed at the receiver. As discussed in [43], a native packet pk is dened as seen, when the receiver has enough information to compute a linear combination of the form (pk+rk), where rk = P i>k ipi and i 2 Fq. Otherwise, pk is unseen. A native packet is acknowledged as seen when the sender receives an ACK indicating that pk has been seen at the receiver. A native packet pk is called decoded when the receiver has enough information to decode pk. Otherwise, pk is undecoded. As an example, when the receiver receives coded packets p1 + p2, p1 + 2p2 and p1 + p2 + p3 + p4, packets p1 and p2 can be decoded. A packet pk is acknowledged as decoded when the sender receives an acknowledgement (ACK) indicating that pk has been decoded at the receiver. In this chapter, the decoding mechanism at the destination is based on Gaussian e- limination, which has also been applied in [37, 43, 44]. If we consider the native packets as unknown variables, then the set of received packets composes a system of linear equa- tions. The decoding process is equivalent to solving a set of linear equations. The receiver can form a decoding matrix using the coecients of coded packets. Gaussian elimination can be applied to convert this matrix to a reduced row echelon form and solve the linear equations. In the reduced row echelon form, the non all zero columns correspond to the Chapter 3. TCP VON: Online Network Coding Based TCP 35 p1 p2 p3 p4 p5 p6 2   0   0   0   0   0 3   5   0   0   0   0 0   4   6   0   0   0 0   0   5   1   4   5 0   0   0   1   3   4 Decoded Seen Sensed p1 p2 p3 p4 p5 p6 1   0   0   0   0   0 0   1   0   0   0   0 0   0   1   0   0   0 0   0   0   1   0   1 0   0   0   0   1   1 (a) Decoding matrix before Gaussian elimination (b) Decoding matrix after Gaussian elimination Figure 3.1: Decoding matrix at the receiver. sensed packets. The rows with leading coecient 1 correspond to the seen packets. The rows with only one non-zero entry (i.e., the leading coecient 1) correspond to the de- coded packets. The rank of the matrix is equal to the number of seen packets. We notice that if all the native packets are seen, then the matrix has full rank and thus all the native packets can be decoded. Fig. 3.1 shows a sample of a decoding matrix before and after Gaussian elimination. The receiver has received 5 linear combinations of packets p1;p2; : : : ;p6. After the Gaussian elimination, packets p1;p2;p3 are decoded, packets p1;p2; : : : ;p5 are seen, and packets p1;p2; : : : ;p6 are sensed. Native packets with index larger than 6 have not been sensed at the receiver. Chapter 3. TCP VON: Online Network Coding Based TCP 36 3.1.2 Preliminaries of Coded Packets At the sender side, let ip, iq and ir denote the smallest index among the packets that have not been acknowledged as decoded, seen, and sensed, respectively. Let is denote the smallest index of the packet that has not been sent. We notice that ip  iq  ir  is. To transmit a new coded packet, the sender combines native packets with consecutive indices within a coding window. Let imin and imax denote the minimum and maximum index of the native packets combined in the new coded packet, where the coding window begins at packet imin and ends at imax. For a new coded packet to be transmitted from the sender, it is required that imin = iq and imax can be equal to either is  1 or is. The reason is as follows: First, it is not necessary to have imin < iq. Even if packet pl for l < iq is combined in the coded packet, since pl has already been seen at the receiver, the Gaussian elimination will eliminate the term of pl. Because piq may not be seen at the receiver, the sender must combine piq in the new coded packet. Therefore, imin = iq. In this chapter, the packet with index iq is called the code base1. Second, if imax > is, the transmitted packet contains at least two new variables (i.e., pis and pis+1) for the receiver. However, it adds only one equation to the system of linear equations at the receiver. Therefore, to provide decoding opportunity at the receiver, imax  is. Because packet pis1 has already been sent, imax  is  1. 1In conventional TCP, the send base is the rst byte which has not been acknowledged, or the rst byte in the congestion window. Similarly, the code base is the rst packet which has not been acknowledged as seen, or the rst packet in the coding window. Chapter 3. TCP VON: Online Network Coding Based TCP 37 Therefore, imax can be equal to either is  1 or is. We use subscript and superscript to distinguish the coded packets transmitted by the sender. The subscript shows the last packet of the coding window. The superscript shows the number of times coded packets with same coding window is transmitted. For the new coded packet transmitted by the sender, if imax = is, then the transmitted packet contains information of a new native packet for the receiver and increases the number of variables at the receiver by one. We call such a packet an innovative packet with index is, which has the form q (0) is = isX k=iq is;0;kpk; (3.1) where is;0;k is a randomly generated coecient of pk. If imax = is  1, then the coded packet is a linear combination of native packets piq ; : : : ;pis1, q (j) is1 = is1X k=iq is1;j;kpk; (3.2) which is called the jth redundant packet with index is  1. We use j to denote the number of times coded packets with linear combination of the same set of native packets piq ; : : : ;pis1 is generated. is1;j;k is a randomly generated coecient of pk combined in the jth redundant packet. In this chapter, when the index of a coded packet (either an innovative or a redundant packet) is not important, we use q to denote a coded packet, k to denote the randomly generated coecient of pk combined in q. When the index of a coded packet is important, we use the notations q (j) is and is;j;k. For the case that there is no packet loss, the receiver can decode one native packet each Chapter 3. TCP VON: Online Network Coding Based TCP 38 time it receives an innovative packet. For example, when the sender transmits innovative packets q (0) 1 = 1;0;1p1, q (0) 2 = 2;0;1p1+2;0;2p2, and q (0) 3 = 3;0;1p1+3;0;2p2+3;0;3p3 consecutively, the receiver can decode packet p1 when q (0) 1 arrives, decode packet p2 when q (0) 2 arrives, and decode packet p3 when q (0) 3 arrives. For the case that there are packet losses in the network, the sender should transmit redundant packets to compensate the eect of packet losses. Postponing the transmission of redundant packets in this case can delay the decoding process. As an example, if the sender transmits M innovative packets back to back and x of them (where x < M) are lost, then those M packets can be decoded only if x redundant packets are subsequently received successfully at the receiver. 3.1.3 Acknowledgement (ACK) Let Ip, Iq and Ir denote the index of the next packet to be decoded, seen and sensed at the receiver, respectively. These indices imply that the packets with indices smaller than Ip are decoded, the packets with indices smaller than Iq are seen, and the packets with indices smaller than Ir are sensed. Each ACK packet includes all of the three indices, in order to inform the sender which packets are decoded, seen and sensed. Note that ip, iq and ir are variables at the sender while Ip, Iq and Ir are variables at the receiver and in the ACK packets. When an ACK packet arrives at the sender, ip, iq and ir are then updated by the values of Ip, Iq and Ir, respectively. Fig. 3.2 shows an example of packet coding according to an ACK packet received at Chapter 3. TCP VON: Online Network Coding Based TCP 39 Ip = 4 Iq = 6 Ir = 8 (a) ACK packet (c) Innovative packet: Į6p6 + Į7p7 + Į8p8 + Į9p9 + Į10p10 + Į11p11 + Į12p12 ip Coding window 1      2      3       4       5      6      7      8      9     10     11   12    13 iriq is imin imax Code base Next  sensed Next  sentNext  decoded ip Coding window 1      2      3       4       5      6      7      8      9     10     11   12    13 iriq is imin imax Code base Next  sensed Next  sentNext  decoded (b) Redundant packet: Į6p6 + Į7p7 + Į8p8 + Į9p9 + Į10p10 + Į11p11 decoded seen but not decoded sensed but not seen sent Figure 3.2: The two types of coded packets and ACK. the sender. At the beginning, native packets p1;p2;p3; : : : ;p11 are sent back to back by the sender. Then, the sender receives an ACK packet which indicates Ip = 4, Iq = 6 and Ir = 8, as shown in Fig. 3.2 (a). The sender then updates ip = 4, iq = 6 and ir = 8. Packets p1;p2;p3 are decoded, packets p1;p2;p3; :::;p5 are seen and packets p1;p2;p3; : : : ;p7 are sensed. Then, the sender can transmit either a redundant packet (a linear combination of packets p6; : : : ;p11, shown in Fig. 3.2 (b)) or an innovative Chapter 3. TCP VON: Online Network Coding Based TCP 40 packet (a linear combination of packets p6; : : : ;p12, shown in Fig. 3.2 (c)). In the next section, we will show how to make the decision to transmit an innovative packet or a redundant packet. 3.2 TCP VON Algorithm The algorithm of TCP VON includes the sender side operation and the receiver side operation. The sender side operation is presented in Algorithm 1 and the receiver side operation is in Algorithm 2. At the sender, a nonnegative integer R is used as a tunable parameter. We call R the redundant factor. A higher value of R allows the the sender to transmit more redundant packets to compensate the detected packet losses. In networks with high loss probability, it is of interest to select higher values of R to reduce the decoding delay. Nevertheless, a higher value for R decreases the network throughput and there is an inherent tradeo in choosing the value of R. In this section, we rst present the sender side operation for the case that R = 0 along with the receiver side operation. Then, we introduce the sender side operation for R > 0. 3.2.1 Sender Side Operation (R = 0 Case) TCP is responsible for reliable end-to-end data transmission. When network coding is merged in the transport layer, this layer needs to perform the coding operations as well as congestion control and 
ow control. We rst explain the congestion and 
ow control Chapter 3. TCP VON: Online Network Coding Based TCP 41 part. Then, we introduce the online network coding control. Congestion and Flow Control For the congestion and 
ow control, we follow the TCP Vegas algorithm [9]. The sender maintains several variables including congestion window size cwnd, measured round trip time RTT , the minimum of all measured round trip times BaseRTT , standard deviation of the measured round trip time , and the receive window size rwnd. The number of packets on the 
ight is approximated by the number of sent but unseen packets (i.e., is  iq), which is limited by the congestion window size cwnd and receive window size rwnd is  iq  minfcwnd; rwndg: (3.3) In order to focus on congestion control, we assume that the buer size at the receiver is large enough so that the eect of the receive window rwnd can be ignored [1, 9, 47]. The congestion window size cwnd is adjusted according to the algorithm from TCP Vegas [9]. We set two predetermined threshold values a and b, a < b. If  cwnd BaseRTT  cwnd RTT   BaseRTT < a, then cwnd is linearly increased. If  cwnd BaseRTT  cwnd RTT   BaseRTT > b, then cwnd is linearly decreased. In our algorithm, we select the default values of a = 1 packet and b = 3 packets. Chapter 3. TCP VON: Online Network Coding Based TCP 42 Table 3.1: Denitions of Variables Used for Online Network Coding Control. Variable name Denition Variable type Initial value Update condition The number of RealGap native packets Nonnegative 0 The sender receives sensed but unseen. integer an ACK. RealGap = ir  iq. The previous Nonnegative Just before OldRealGap value of integer 0 RealGap is RealGap. being updated. The dierence between RealGap Right after RealGapDiff and OldRealGap. Nonnegative 0 RealGap has RealGapDiff = integer been updated. RealGap OldRealGap. The maximum A redundant packet number of lost Nonnegative is transmitted. ExpGap packets can integer 0 RealGap is be tolerated decreased at the sender. (RealGapDiff > 0). A variable Either If RealGap to instruct REDUN > ExpGap, whether the DANT INNOV State = State next packet to or ATIV E REDUNDANT , transmit is INNOV otherwise, redundant or ATIV E State = innovative. INNOV ATIV E. Online Network Coding Control The core of our online network coding control is to decide whether to transmit an inno- vative packet or a redundant packet such that the receiver can decode the packets with small decoding delay. The online network coding control maintains dierent variables including the real gap RealGap, the old real gap OldRealGap, the real gap dierence RealGapDiff , the expected gap ExpGap, and the state State. Table 3.1 shows the denitions and properties of the variables. The real gap RealGap is the number of native Chapter 3. TCP VON: Online Network Coding Based TCP 43 packets sensed but unseen at the sender. That is, RealGap = ir  iq. The value of RealGap is updated whenever the sender receives an ACK packet. RealGap shows the number of lost innovative packets. If the RealGap is zero, it indicates that all packets have been decoded at the receiver. If the RealGap is greater than zero, it implies that there are packet losses in the system. The old real gap OldRealGap is the variable to store the previous value of RealGap. Whenever an ACK is received, OldRealGap is set to be the value of RealGap just before RealGap is being updated. RealGapDiff is the dier- ence between RealGap and OldRealGap (i.e., RealGapDiff = RealGapOldRealGap), which shows the decrease in real gap upon receiving an ACK packet. RealGapDiff is calculated right after RealGap has been updated. The ExpGap is the maximum number of lost packets which can be tolerated at the sender. It is updated whenever a redun- dant packet is transmitted or RealGap is decreased, which will be discussed in details later. State is a variable taking either REDUNDANT or INNOV ATIV E to instruc- t whether the next packet to transmit is a redundant packet or an innovative one. If RealGap > ExpGap, then the number of lost packets exceeds the maximum number that the sender can tolerate and the State will change into REDUNDANT . The sender transmits a redundant packet in this case. Otherwise (i.e., RealGap  ExpGap), the State is INNOV ATIV E and the sender transmits an innovative packet. We now explain the use of ExpGap. At the beginning, both RealGap and ExpGap are set to zero. During operation, the RealGap is equal to one, which indicates a packet loss. The sender transmits a redundant packet to compensate the packet loss and ExpGap is Chapter 3. TCP VON: Online Network Coding Based TCP 44 increased by one. It causes RealGap to be equal to ExpGap, and the sender does not transmit more redundant packets during the period when RealGap is equal to ExpGap. If the transmitted redundant packet gets lost in the network, the sender should be able to detect the loss of the redundant packet. Therefore, as soon as the sender transmits a redundant packet, it starts a timer with value RTT +4 (where 4 is used to provide some time margin). When the seder receives an ACK indicating that the redundant packet is successfully received by the receiver, the RealGap is decreased by one before the timer expires. If RealGap has not been decreased when the timer expires, it indicates that the redundant packet has got lost. In this case, the sender decreases ExpGap by one, which causes RealGap to be greater than ExpGap, so that the sender transmits another redundant packet. Note that in our algorithm, one timer starts whenever a redundant packet is transmitted, and each redundant packet has its own timer. If the transmitted redundant packet is received successfully at the receiver, then the sender is informed by an ACK packet indicating the decrease of RealGap by one (i.e., RealGapDiff = 1). In this case, the sender decreases ExpGap accordingly. The timer corresponding to the transmission of the redundant packet is stopped. RealGapDiff can be larger than one, which indicates that more than one redundant packets have been received at the receiver. In this case, ExpGap is decreased by RealGapDiff , and the RealGapDiff oldest timers are stopped. Chapter 3. TCP VON: Online Network Coding Based TCP 45 Algorithm of Sender Side Operation Algorithm 1 shows the algorithm of TCP VON at the sender. Line 1 shows the input of the tunable variable R. We rst present the R = 0 case. The R > 0 case will be discussed in Section 3.2.5. Lines 2 to 4 are used to initialize the variables. Let im denote the total number of native packets created. As shown in Lines 6 to 9, if new data with X bytes arrives from upper layer, ns = dXL e native packets are created, each with length of L bytes (the last packet is padded with 0 if necessary). At the same time, the total number of native packets is increased by ns. Lines 10 to 37 show the online network coding algorithm. When RealGap is greater than ExpGap, a redundant packet is transmitted, ExpGap is increased by one, and a timer is started. Otherwise, an innovative packet is transmitted. Lines 38 to 53 present the operations when an ACK packet is received. The sender updates BaseRTT , , ip, iq and ir (Lines 39 to 40). Then, it calculates the value of OldRealGap, RealGap and RealGapDiff (Lines 41 to 43). If the RealGapDiff is larger than zero, the sender will decrease ExpGap accordingly and RealGapDiff timers will be stopped. Then, the congestion control is performed in Lines 48 to 52. Lines 54 to 56 show the timeout event. The ExpGap will be decreased by one when a timeout event occurs. Chapter 3. TCP VON: Online Network Coding Based TCP 46 Algorithm 1 Algorithm of TCP VON at the Sender. 1: Input: R 2: Set ip := 1, iq := 1, ir := 1, is := 1, imin := 1, imax := 1, im := 0 3: Set RealGap := 0, OldRealGap := 0, RealGapDiff := 0, ExpGap := 0 4: Set State := INNOV ATIV E, cwnd := 1 5: while the TCP connection is established 6: if data with length X bytes is received from upper layer 7: Segment data into ns := dXL e packets: pim+1; pim+2; : : : ; pim+ns 8: Set im := im + ns 9: end if 10: while is  iq  cwnd and imax  im 11: if R = 0 12: if RealGap > ExpGap 13: Set State := REDUNDANT 14: else 15: Set State := INNOV ATIV E 16: end if 17: elseif R > 0 18: if RealGap+R > ExpGap and RealGap > 0 19: Set State := REDUNDANT 20: else 21: Set State := INNOV ATIV E 22: end if 23: end if 24: if State = INNOV ATIV E 25: Set imin := iq, imax := is, is := imax + 1 26: Create coded packet q = Pimax j=imin jpj using random coding coecients 27: Include imin, imax and imin ; : : : ; imax in the packet header 28: Transmit the coded packet 29: elseif State = REDUNDANT 30: Set imin := iq, imax := is  1 31: Create redundant coded packet q = Pimax j=imin jpj using random coecients 32: Include imin, imax and imin ; : : : ; imax in the packet header 33: Transmit the coded packet 34: Set ExpGap := ExpGap+ 1 35: Start a new countdown timer with value RTT + 4 36: end if 37: end while 38: if an ACK is received 39: Set ip := Ip, iq := Iq, ir := Ir 40: Compute BaseRTT and  41: Set OldRealGap := RealGap 42: Set RealGap := ir  iq 43: Set RealGapDiff := RealGapOldRealGap 44: if RealGapDiff > 0 45: Set ExpGap := ExpGapRealGapDiff 46: Stop RealGapDiff oldest timers. 47: end if 48: if  cwnd BaseRTT  cwndRTT BaseRTT > 3 49: Set cwnd := cwnd 1 in the next RTT 50: elseif  cwnd BaseRTT  cwndRTT BaseRTT < 1 51: Set cwnd := cwnd+ 1 in the next RTT 52: end if 53: end if 54: if a timer timeouts 55: ExpGap := ExpGap 1 56: end if 57: end while Chapter 3. TCP VON: Online Network Coding Based TCP 47 3.2.2 Receiver Side Operation Algorithm 2 shows the algorithm of TCP VON at the receiver. Ip, Iq and Ir are initialized with value 1 (Line 1). D is the decoding matrix (Line 2). When the receiver receives an uncorrupted coded packet (Line 5), it rst checks the packet header and retrieves imin, imax and the coding coecients of native packets combined. Then, the coecients are added as a new row to the decoding matrix and Gaussian elimination is executed (Lines 6 to 8). Then, operations corresponding to the Gaussian elimination are performed on the received packets so far (Lines 9 to 11). Then, the receiver will nd the next packet to be decoded using the while loop in Lines 14 to 17. The sender increases the value of Ip by one until it nds that the native packet with index Ip is not decoded. Thus, Ip is equal to the index of the rst undecoded packet when the while loop is terminated. Similarly, the receiver will nd the rst packet unseen in Lines 18 to 20, and the rst packet unsensed in Lines 21 to 23. Finally, an ACK packet indicating the indices Ip, Iq and Ir is generated and sent at the receiver (Line 24). Chapter 3. TCP VON: Online Network Coding Based TCP 48 Algorithm 2 Algorithm of TCP VON at the Receiver. 1: Set Ip := 1, Iq := 1, Ir := 1 2: Decoding matrix D := [ ] 3: while TCP connection is established 4: if a packet is received 5: if packet is not corrupted 6: Retrieve imin and imax and the coding coecients imin ; : : : ; imax 7: Add coding coecients as a new row to matrix D 8: Perform Gaussian elimination on D 9: if an all-zero row appears 10: Discard the packet 11: Eliminate the all-zero row in D 12: else 13: Perform linear operations to packets corresponding to the Gaussian elimination 14: while native packet with index Ip is decoded 15: Deliver data in pIp to upper layer 16: Ip := Ip + 1 17: end while 18: while native packet with index Iq is seen 19: Iq := Iq + 1 20: end while 21: while native packet with index Ir is sensed 22: Ir := Ir + 1 23: end while 24: Send an ACK packet indicating Ip, Iq and Ir 25: end if 26: else 27: Discard the corrupted packet 28: end if 29: end if 30: end while 3.2.3 Reliable Data Transfer TCP VON is able to provide reliable data transfer and handle with packet loss, corruption, duplication and reordering. If a coded packet is either lost or corrupted, redundant packets will be transmitted to compensate the loss or corruption. If a coded packet is duplicated, an all-zero row will appear after the Gaussian elimination. The receiver will nd that it is not linearly independent and discard the redundant packet. If packet reordering occurs, it is corresponding to row exchange in the decoding matrix and the Chapter 3. TCP VON: Online Network Coding Based TCP 49 TIMER(2) TIMER(1) Packet loss RealGap is increased Redundant packet is transmitted, and ExpGap is increased Timer times out, and ExpGap is decreased RealGap is decreased, timer is canceled, and ExpGap is decreased time time TIMER(4)TIMER(3) RTT RTT RTT RTT t1,L t1,D t1,R t1,F t2,L t2,D t2,R t2,F t3,L t3,D t3,R t3,T t4,L t4,R t4,F The redundant packet is lost time Sender Receiver RealGap 1 2 1 1 time 1 2 ExpGap 1 2 1 1 1 time 1 2 I(RealGap>ExpGap) 1 1 1 1 1 ... ... ... ... ... ... ... ... ... Innovative packet ACK packet Redundant packet Figure 3.3: Example of real gap and expected gap. decoding results do not change. 3.2.4 Example of the Algorithm of TCP VON with R = 0 Fig. 3.3 provides an example for the algorithm when R = 0. I(RealGap > ExpGap) is an indicator function, having the value 1 if RealGap > ExpGap, and 0 otherwise. At the beginning, both RealGap and ExpGap are equal to 0. At time t1;L, one packet is lost. The packet following the lost packet is received by the receiver and an ACK indicating that Ir  Iq = 1 is sent by the receiver. At time t1;D, the sender receives the ACK and updates ir and iq by the values of Ir and Iq, respectively. Then, the RealGap = iriq = 1 is calculated. Since RealGap is greater than ExpGap, at time t1;R, a redundant packet Chapter 3. TCP VON: Online Network Coding Based TCP 50 is transmitted, ExpGap is set to 1, and timer TIMER(1) is set. Similarly, the second packet is lost at time t2;L, and the sender receives an ACK packet indicating RealGap to be equal to 2 at time t2;D. At time t2;R, another redundant packet is transmitted, ExpGap is set to 2, and timer TIMER(2) is set. At time t1;F , the sender is informed by an ACK that the rst redundant packet is received successfully at the receiver and RealGap becomes 1. TIMER(1) is stopped and ExpGap is reduced to 1. Similarly, at time t2;F , the sender is informed by an ACK that the second redundant packet is received successfully and RealGap becomes 0. TIMER(2) is stopped and ExpGap is set to 0. At time t3;L, a third packet is lost. At time t3;D, RealGap becomes 1. At time t3;R, a redundant packet is transmitted, ExpGap becomes 1, and timer TIMER(3) is set. However, the redundant packet transmitted is also lost at time t4;L. Therefore, the RealGap does not decrease until time t3;T when TIMER(3) times out and ExpGap becomes 0. Then RealGap is greater than ExpGap again and the fourth redundant packet is transmitted at time t4;R. Finally, the fourth redundant packet is received successfully. At time t4;F , RealGap becomes 0, timer TIMER(4) is stopped, and ExpGap is set to 0. 3.2.5 Tunable Parameter R in the Sender Side Operation We now present the use of the tunable parameter (redundant factor) R in the sender side operation. For networks with high loss probability, we may set R > 0 to allow the the sender to transmit more redundant packets to compensate the detected packet losses. Consider the scenario that RealGap is increased from 0 to 1 when ExpGap is equal Chapter 3. TCP VON: Online Network Coding Based TCP 51 to 0, due to the high loss probability, it is possible that there are more than one packet losses and only the rst one is indicated by the ACK packet. In this case, the receiver cannot decode the packets even if it receives one redundant packet, and the decoding delay may become quite large. Thus, sending only one redundant packet may not be enough when RealGap is increased from 0 to 1 and ExpGap is equal to 0. With the redundant factor R greater than 0, the sender transmits R+1 redundant packets in this situation. As shown in Algorithm 1, if R > 0, the sender decides whether to transmit an innovative packet or a redundant packet according to Lines 18 to 22. It transmits redundant packets if RealGap+R > ExpGap and RealGap > 0, otherwise, it transmits innovative packets. The reasons are as follows: First, when the sender detects the rst packet loss (i.e., RealGap is increased from 0 to 1 when ExpGap = 0), the sender transmits R+1 redundant packets until ExpGap = R+1 and RealGap+R is no larger than ExpGap. Second, if the sender detects x more packet losses (i.e., RealGap = x+1), the sender transmits xmore redundant packet until ExpGap = R+x+1 and RealGap+R is no larger than ExpGap. Third, when RealGap = 0, which means that all the packets can be decoded at the receiver, the sender does not transmit redundant packets. After transmitting R + 1 redundant packets, even if there are up to R more packet losses following the rst packet loss, the receiver will still be able to decode all the packets when it receives the R+1 redundant packets. As a result, the decoding delay is expected to be smaller compared to the case when R is equal to 0. Higher values of R can provide better decoding delay performance for networks with Chapter 3. TCP VON: Online Network Coding Based TCP 52 p1+p2+p3 p1 p2, p3 decoded time IJ0=2 ms p1+p2+2p3 p1 decoded Sender Receiver 6 ms 8 ms 6 ms Figure 3.4: Example of decoding delay. high loss probability, while it may deteriorate the throughput eciency of the end-to-end communication for networks with low loss probability. We recommend to set R to 0 for wired networks and set R to 2 for wireless networks. Through the analytical methods in Section 3.3 and simulations in Section 3.4, we further study the delay-throughput tradeo in choosing the tunable parameter R. 3.3 Decoding Delay Analysis of TCP VON In this section, we establish a system model to analyze the decoding delay of TCP VON. First, we present a Markov chain model for the case R = 0. Then, we develop a method to estimate the performance when R is greater than zero. The decoding delay is dened as the dierence between the time that a packet is transmitted by the sender and the time at which that packet is decoded at the receiver. In this section, we determine the average decoding delay of all the packets to evaluate Chapter 3. TCP VON: Online Network Coding Based TCP 53 the decoding delay performance. For example, as shown in Fig. 3.4, the end-to-end delay from the sender to the receiver is 6 ms, the time duration between the two consecutive packets 0 is 2 ms. The decoding delay of q1, q2 and q3 are 6 ms, 8 ms and 6 ms, respectively. Thus, the average decoding delay is 20=3 ms. For the delay analysis, we consider a single TCP session running in the network, where the last hop is a wireless link. This wireless link has a capacity of C bits/sec which is smaller than the capacity of all other intermediate links between the sender and the receiver. Therefore, this wireless link is the bottleneck link for the end-to-end communication. We assume that the sender has a large le to send. The packet size is L bits. Due to the congestion control mechanism of TCP Vegas, we assume that the trans- mission rate at the sender attains the capacity of the bottleneck link C, and there is no congestion loss at the network. The propagation delay from the sender to the receiver is T0, which is a given value. The time to transmit a packet 0 is equal to L=C. Due to the property of TCP Vegas, there are on average two packets in the buers along the path from the sender to the receiver and the average queuing delay is 2L=C [9]. Thus, the end-to-end delay from the sender to the receiver is T1 = T0 + 3L=C. Because the length of each ACK packet is small, the end-to-end delay from the receiver to the sender T2 is approximately equal to the propagation delay T2 = T0. Finally, the round trip time RTT is equal to T1+T2 = 2T0+3L=C. Because there is no cross trac, we assume that T1, T2 and RTT are constants and  is 0. The transmission rate at the sender is C=L Chapter 3. TCP VON: Online Network Coding Based TCP 54 packets/sec. Each packet experiences random loss at the wireless link independently with proba- bility p. In the model, we can equivalently assume that each packet is corrupted inde- pendently with probability p. Since the receiver discards corrupted packets and keeps the correctly received packets, the case that a packet is lost is equivalent to the case that a packet is corrupted. Let qk denote the kth coded packet transmitted by the sender, or equivalently, the kth coded packet received by the receiver (either innovative or re- dundant, either correct or corrupted). The time duration between the arrivals of the two consecutive packets (i.e., qk and qk+1 for any k = 1; 2; : : :) at the receiver is also 0. Chapter 3. TCP VON: Online Network Coding Based TCP 55 No corruption, decoding delay is T1 Redundant Packet IJ0 ... One corrupted packet, expected decoding time is delayed to RTT+IJ0 = (K+1)IJ0 Redundant Packet One group One group īx= (K+1)IJ0 īx+1 = KIJ0 īx+2 = (Kí1)IJ0 īx+5 = (K+1)IJ0 qx+5 (a) Zero or one packet corruption in one group. Redundant Packet One group (b) Multiple packet corruptions in one group. qx+2 qx+1 qx Sx= K+1 Sx+1 = K Sx+2 = Kí1 Sx+5 = K+1 ... ... ... ... ... ... ... ... ... ... ... ... time time RealGap = 0, ExpGap = 0 RealGap = 0, ExpGap = 0 RealGap = 0, ExpGap = 0 RealGap = 1, ExpGap = 1 ... ... ... RealGap = 0, ExpGap = 0 RealGap = 0, ExpGap = 0 RealGap = 0, ExpGap = 0 RealGap = 1, ExpGap = 1 RealGap = 2, ExpGap = 2 RealGap = 1, ExpGap = 1 RealGap = 0, ExpGap = 0 ... ... ... qx qy Figure 3.5: Examples of groups of packets with dierent number of corrupted packets. 3.3.1 System Model for R = 0 Case A group of packets is referred to as a set of packets which can be decoded together. Figs. 3.5 (a) and (b) show some samples of group of packets. If there are no corrupted Chapter 3. TCP VON: Online Network Coding Based TCP 56 packet arrivals at the receiver, each packet can be decoded immediately when it arrives at the receiver, with decoding delay T1. There will be only one packet in each group in this case. If a corrupted packet arrives at the receiver, the consecutive innovative packets cannot be decoded until a redundant packet arrives at the receiver. In this case, there will be several packets in one group. We dene the expected decoding time of a packet qx as the dierence between the arrival time of qx and the time packet qx is expected to be decoded if no further packet corruptions happen. Let x denote the expected decoding time of packet qx. As shown in Fig. 3.5 (a), if there are no corrupted packet arrivals before qx and qx is correctly received, x is equal to 0 because qx can be decoded immediately when it arrives at the receiver. If qy is corrupted, the receiver receives qy+1 0 seconds later, then it sends back an ACK indicating that RealGap = 1, which will arrive at the sender in T2 seconds. Then, the sender will transmit an redundant packet and set ExpGap = 1. Finally, the redundant packet will arrive at the receiver in T1 seconds. In summary, the receiver can decode qy, until it receives the redundant packet which is expected to arrive 0+T2+T1 (i.e., RTT + 0) seconds after the arrival of qy. Thus, the expected decoding time of qy (y) is delayed up to RTT + 0. We use K to denote the ratio of RTT over 0. We approximate this value with dRTT=0e. Since RTT is much larger than 0, the error of approximation is negligible. After the receiver receives the redundant packet, it sends back another ACK, to set the RealGap and ExpGap to be 0 at the sender. As another example, consider Fig. 3.5 (b). When a corrupted packet qx arrives Chapter 3. TCP VON: Online Network Coding Based TCP 57 at the receiver, RealGap is set to be 1 after 0 + T2 seconds, and redundant packet is transmitted and ExpGap = 1. The redundant packet is expected to arrive at the receiver RTT + 0 = (K+1)0 seconds after qx arrives at the receiver and the expected decoding time of qx is RTT + 0 = (K + 1)0. When a correctly received packet (e.g., packet qx+1 or qx+2) arrives, the expected decoding time will be decreased by 0. If there is another corrupted packet qx+5, RealGap = 2 and ExpGap = 2 at the sender and another redundant packet is transmitted. Thus, the expected decoding time of qx+5 becomes (K + 1)0 again. For any k, the expected decoding time k = 0; 0; 20; : : : ; (K + 1)0. For the sequence of the packets q1; : : : ;qk+1, the sequence of expected decoding times is 1; : : : ;k+1. The expected decoding time k+1 is determined based on k and whether qk+1 is corrupted or correct. Thus k+1 is independent of k1; : : : ;1 P (k+1 j k;k1; : : : ;1) = P (k+1 j k); k = 0; 0; 20; : : : ; (K + 1)0: (3.4) We use Sk to denote the ratio of k to 0 (i.e., Sk = k 0 ). Packet qk is expected to be decoded right after Sk following packets arrives at the receiver, if none of the Sk packets is corrupted. We also have P (Sk+1 j Sk; Sk1; : : : ; S1) = P (Sk+1 j Sk); Sk = 0; 1; : : : ; K + 1: (3.5) The sequence S1; S2; : : : constructs a discrete Markov chain. If a corrupted packet arrives, the expected decoding time becomes (K+1)0 and the state becomes K+1. If a packet is correctly received, the expected decoding time is decreased by 0 and the state decreases by 1. Fig. 3.6 shows the state transition of the Markov chain. LetM denote the transition Chapter 3. TCP VON: Online Network Coding Based TCP 58 1 2 3 4 K K+10 p p p p p p 1íp 1íp 1íp 1íp 1íp 1íp 1íp 1íp p    Figure 3.6: Markov state transition for redundant factor R = 0. probability matrix of the Markov chain, M = 0BBBBBBBBBB@ m00 m01 : : : m0(K+1) m10 m11 : : : m1(K+1) ... ... . . . ... m(K+1)0 m(K+1)1 : : : m(K+1)(K+1) 1CCCCCCCCCCA = 0BBBBBBBBBBBBBB@ 1 p 0 : : : 0 p 1 p 0 : : : 0 p 0 1 p : : : 0 p ... ... . . . ... ... 0 0 : : : 1 p p 1CCCCCCCCCCCCCCA ; (3.6) where mj(K+1) = p (j = 0; 1; : : : ; K + 1), m(j+1)j = 1 p (j = 0; 1; : : : ; K), m00 = 1 p and all the other entries of M are 0. When the Markov chain enters state 0, all the packets can be decoded. If there are i packets in one group, there will be i transitions between two consecutive visits of state 0 in the Markov chain accordingly. Let Pi denote the probability that there are i packets in one group (or equivalently, the probability that there are i transitions between two consecutive visits of state 0 in the Markov chain). Chapter 3. TCP VON: Online Network Coding Based TCP 59 We determine Pi as follows: M can be divided into four submatrices M = 0BB@ M00 M01 M10 M11 1CCA (3.7) = 0BBBBBBBBBB@ m00 m01 : : : m0(K+1) m10 m11 : : : m1(K+1) ... ... . . . ... m(K+1)0 m(K+1)1 : : : m(K+1)(K+1) 1CCCCCCCCCCA : We have P1 = m00 and P2 = PK+1 j=1 m0jmj0 = M01M10, respectively. In general, we have Pi = K+1X j1=1 K+1X j2=1 : : : K+1X ji1=1 m0j1mj1j2 : : :mji2ji1mji10 = M01M i2 11 M10; i  3: (3.8) The decoding delay of the ith (last) packet in the group with i packets is equal to the propagation delay T1. The decoding delay of the (i 1)th packet in the group is T1+ 0. The decoding delay of the (ij)th (j = 0; 1; : : : ; i1) the packet in the group is T1+j0. The average decoding delay of a group with i packets is i = Pi1 j=0 (T1 + j0) i = T1 + (i 1)0=2; i  1: (3.9) Let t denote the total transmission time, T (t) denote the total decoding delay of all the packets during time t and N(t) denote the total number of packets transmitted Chapter 3. TCP VON: Online Network Coding Based TCP 60 during time t. The average decoding delay can be computed as  = lim t!1 T (t) N(t) : (3.10) We use ni(t) to denote the number of groups with i packets in total during time t. We have N(t) = 1P i=1 ini(t) and T (t) = 1P i=1 ini(t)i. Thus,  = lim t!1 1P i=1 ini(t)i 1P i=1 ini(t) : (3.11) The nominator and denominator of (3.11) can be divided by 1P j=1 nj(t) at the same time,  = lim t!1 1P i=1 i  ni(t)=  1P j=1 nj(t) !! i 1P i=1 i  ni(t)=  1P j=1 nj(t) !! = 1P i=1 i  lim t!1 ni(t)=  1P j=1 nj(t) !! i 1P i=1 i  lim t!1 ni(t)=  1P j=1 nj(t) !! : (3.12) For large values of t, by the law of large numbers, the limit of ni(t)= P1 j=1 nj(t) approaches Pi, the probability that there are i packets in one group. Thus,  = 1P i=1 iPii 1P i=1 iPi : (3.13) Therefore, the average decoding delay can be computed. Chapter 3. TCP VON: Online Network Coding Based TCP 61 (R+1) redundant packets ... Expected decoding time is (K+R+1)IJ0 Decoding of the packets qx K innovative packets ... ... qy RealGap = 0, ExpGap = 0 RealGap = 0, ExpGap = 0 RealGap = 0, ExpGap = 0 RealGap = 1, ExpGap = 1 RealGap = 1, ExpGap = 2 RealGap = 1, ExpGap = R+1 RealGap = 0, ExpGap = 0 ... ... time qx-1 RealGap = 0, ExpGap = 0 Figure 3.7: Example of the expected decoding time with redundant factor R > 0. 3.3.2 System Model for the R > 0 Case When the redundant factor R is greater than zero, the source transmits R+1 redundant packets if a packet loss occurs and the real gap is zero. In this case, whether a packet can be decoded depends on many factors including the number of redundant packets transmitted before the transmission of the packet and which packets have been lost before the transmission of the packet by the sender. It is complicated to establish an accurate model. We develop a method to estimate the delay performance for R > 0 case in this subsection. Fig. 3.7 shows an example of R > 0 case. At the beginning, RealGap = 0, ExpGap = 0, and no packets are corrupted. qx1 can be decoded as soon as it arrives at the receiver, the expected decoding time of qx1 (x1) is 0. If the receiver receives one corrupted Chapter 3. TCP VON: Online Network Coding Based TCP 62 (R+1) redundant packets ... Expected decoding time is (K+R+1)IJ0 ... ... time K innovative packets qx (0) Figure 3.8: Estimated Markov state transition for redundant factor R > 0. packet qx, it sends an ACK indicating RealGap = 1. Then, the sender is expected to transmit R+1 redundant packets, until RealGap = 1 and ExpGap = R+1. The packets are expected to be decoded when the redundant packets arrive at the receiver. Thus, the expected decoding time of qx (x) is (K + R + 1)0. After that, the expected decoding time will be decreased by 0 each time a coded packet is correctly received by the receiver. In the case that R > 0, k+1 is determined based on k and whether qk+1 is corrupted or not in the following conditions: (a) If k = 0 and qk+1 is corrupted, k+1 = (K +R + 1)0; (b) If k = 0 and qk+1 is not corrupted, k+1 = 0; (c) If k > 0 and qk+1 is not corrupted, k+1 = k  0. k+1 is not only determined based on k and whether qk+1 is corrupted or not in the following condition: (d) If k > 0 and qk+1 is corrupted. The occurrence of conditions (a) (b) and (c) is much more than that of condi- Chapter 3. TCP VON: Online Network Coding Based TCP 63 tion (d) when p is not large (e.g., p  0:1). We approximately assume that k+1 is determined based on k and whether qk+1 is corrupted or not. Therefore, we have P (k+1 j k;k1; : : : ;1) = P (k+1 j k) and consequently P (Sk+1 j Sk; Sk1; : : : ; S1) = P (Sk+1 j Sk). As discussed in Section 3.3.1, the state is the expected decoding time divided by 0. Therefore, in the estimated Markov chain model, the state space is f0; 1; 2; : : : ; K+R+1g. The state 0 corresponds to the packets decoded immediately when they arrive at the receiver. The state K +R+ 1 corresponds to the corrupted packet causing the expected decoding time delayed up to (K + R + 1)0. The transition probability from state 0 to state K +R + 1 is equal to p. Let pe denote the transition probability from any state j = 1; 2; : : : ; K+R+1 to state K+R+1. pe is a value smaller than p. The reason is as follows: Due to the redundancy introduced by R, if a packet is corrupted, the expected decoding time may not become (K+R+1)0 and the state may not transit into stateK+R+1. For example, in Fig. 3.7, if qy is also corrupted, qy can be decoded when the receiver receives the redundant packets, and the expected decoding time of qy does not become (K +R+ 1)0. Thus, transition probability from state j (j = 1; 2; : : : ; K +R + 1) to state K +R + 1 is smaller than p. Let  denote the probability that there are K +R+2 packets in one group. It is also the probability that there are K + R + 2 transitions between two consecutive visits of state 0. As shown in the example of Fig. 3.7, the rst packet qx of the group is corrupted. Then, after receiving packet qx at the receiver, K+R+1 packets, including K innovative Chapter 3. TCP VON: Online Network Coding Based TCP 64 packets and R + 1 redundant packets, will arrive. If up to R of the K + R + 1 packets are corrupted, these packets can still be decoded when the last redundant packet arrives (K +R+ 1)0 seconds after the arrival of qx. In this situation, there will be K +R+ 2 packets in the group. The probability that qx is corrupted is p and the probability that up to R of theK+R+1 following packets are corrupted is PR i=0  K+R+1 i  (1p)K+R+1ipi. Thus, the probability that there are K +R+2 packets in one group can be computed as  = p  RX i=0  K +R + 1 i  (1 p)K+R+1ipi ! : (3.14) When there are K +R+2 transitions between two consecutive visits of state 0, the only state transition pattern is 0 ! K + R + 1 ! K + R ! : : : ! 1 ! 0 . Thus,  can also be computed as  = p(1 pe)K+R+1: (3.15) We can compute the value of pe using equations (3.14) and (3.15) as pe = 1  RX i=0  K +R + 1 i  (1 p)K+R+1ipi ! 1 K+R+1 : (3.16) We now show that pe < p as follows pe = 1  RX i=0  K +R + 1 i  (1 p)K+R+1ipi ! 1 K+R+1 = 1  (1 p) + RX i=1  K +R + 1 i  (1 p)K+R+1ipi ! 1 K+R+1 < 1 (1 p) 1K+R+1 < 1 (1 p) = p: (3.17) Finally, given the value of pe, we can write the transition probability matrixM based Chapter 3. TCP VON: Online Network Coding Based TCP 65 on Fig. 3.8. Following the steps from equations (3.7) - (3.13), the estimated decoding delay can be computed similarly. 3.4 Performance Analysis In this section, we analyze the performance of TCP VON via ns-2 simulations [48]. We rst validate our analytical models by comparing the analytical and simulation results. Then, we compare the throughput and delay performance of TCP VON and TCP AR- QNC [43, 44]. Unless stated otherwise, the packet size L is set to 1250 bytes. The results are average on 50 simulation runs and each simulation lasts 100 seconds. 3.4.1 Performance Validation We rst consider a single-hop wireless network with one sender and one receiver. C is the capacity of the wireless link. Fig. 3.9 shows the comparison between the analytical and simulation results for R = 0 under dierent loss probabilities p. The propagation delay from the sender to the receiver T0 is 5 ms. The packet loss probability varies from 0 to 0:1 with step size 0:01. The results show that when the loss probability increases, the average decoding delay increases. In addition, when C increases, the average decoding delay increases as well. This is because when C increases, 0 = L=C decreases and the number of packets transmitted within one RTT is increased. Thus, the number of transmitted but unacknowledged packets becomes larger. In this case, it is more likely that there are packet losses among the transmitted but unacknowledged packets. This Chapter 3. TCP VON: Online Network Coding Based TCP 66 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 Loss probability  p A v e ra g e  d e c o d in g  d e la y  ( s) Analytical,  C = 30 Mb/s Simulation,  C = 30 Mb/s Analytical,  C = 20 Mb/s Simulation,  C = 20 Mb/s Analytical,  C = 10 Mb/s Simulation,  C = 10 Mb/s Figure 3.9: Analytical and simulation results of average decoding delay for dierent values of loss probability p for R = 0, T0 = 5 ms, and L = 1250 bytes. accordingly increases the decoding delay. Fig. 3.10 shows the comparison between the analytical and simulation results under dierent values of R where T0 is 5 ms and p is 0:1. The results show that a higher value of R decreases the decoding delay. In the analytical model, we assume that there is no cross trac, RTT is a constant, and  = 0. In the simulation, the topology is single-hop topology and there is only one TCP session. Thus, the round trip time does not change much and  is small in the simulation, which is quite close to the assumptions in the analytical model. Therefore, the simulation results match the analytical results in Figs. 3.9 and 3.10. Chapter 3. TCP VON: Online Network Coding Based TCP 67 0 1 2 3 4 5 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1  R A v e ra g e  d e c o d in g  d e la y  ( s) Analytical,  C = 30 Mb/s Simulation,  C = 30 Mb/s Analytical,  C = 20 Mb/s Simulation,  C = 20 Mb/s Analytical,  C = 10 Mb/s Simulation,  C = 10 Mb/s Figure 3.10: Analytical and simulation results of average decoding delay for dierent values of redundant factor R for p = 0:1, T0 = 5 ms, and L = 1250 bytes. 3.4.2 Performance Comparison Next, we compare the performance of TCP ARQNC [43, 44] and TCP VON. For TCP ARQNC, the coded packets are transmitted in a generation by generation fashion. There are N0 native packets in one generation and each coded packet is a linear combination of the N0 native packets. For each generation, the sender rst transmits NG = N0 + R0 coded packets, where R0 is the redundant factor. The receiver can decode all the native packets if N0 or more coded packets are successfully received at the receiver. If more than R0 packets are lost, the sender has to transmit more linear combinations until the receiver receives enough independent coded packets. We use two dierent network topologies for performance comparison described as follows. The multihop tandem topology is shown in Fig. 3.11. The rst two hops are wired Chapter 3. TCP VON: Online Network Coding Based TCP 68 C = 10 Mb/s Loss probability p 50 Mb/s 50 Mb/s 5 ms 5 ms 2 ms Source Destination Figure 3.11: Simulation topology 1: Multihop tandem topology. Loss probability p 10 Mb/s 2 ms 10 Mb/s 2 ms 50 Mb/s 5 ms 50 Mb/s 5 ms Loss probability p 50 Mb/s 3 ms 50 Mb/s 3 ms 50 Mb/s 3 ms 50 Mb/s 3 ms Source 1 Source 2 Destination 1 Destination 2 Figure 3.12: Simulation topology 2: Cross trac topology. links with capacity of 50 Mb/s, and propagation delay of 5 ms. The last hop is wireless link with capacity of 10 Mb/s and the propagation delay of 2 ms. One TCP session is established from Source to Destination. The cross trac topology is shown in Fig. 3.12. All the links are wired links except the last link to the destinations which are wireless links. Each wired link has a capacity of 50 Mb/s and propagation delay of 3 ms. The wireless links have a capacity of 10 Mb/s and propagation delay of 2 ms. We assume that both of the links have random packet loss probability p. Two TCP sessions are established; one from Source 1 to Destination 1 and the other one from Source 2 to Destination 2. We investigate the joint throughput and delay performance of dierent TCP schemes using ns-2 simulation. Figs. 3.13 and 3.14 show the throughput and delay performance of TCP VON and TCP ARQNC when p changes from 0 to 0:1 with step 0:01 in multihop tandem topology and cross trac topology, respectively. For TCP ARQNC, When N0 and R0 are small, although the delay is low, the throughput performance is poor. When N0 and R0 are increased, the throughput is improved but the delay performance degrades. Chapter 3. TCP VON: Online Network Coding Based TCP 69 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0 1 2 3 4 5 6 7 8 9 10 Average delay (s) A v e ra g e  t h ro u g h p u t (M b /s ) TCP VON, R = 0 TCP VON, R = 1 TCP VON, R = 2 TCP ARQNC, N 0  = 200, R 0  = 20 TCP ARQNC, N 0  = 100, R 0  = 10 TCP ARQNC, N 0  = 20, R 0  = 2 TCP ARQNC, N 0  = 10, R 0  = 1 p = 0 p = 0.1 p = 0.1 Figure 3.13: Performance comparison for multihop tandem topology under dierent values of loss probability p. This is because the sender starts to transmit the next generation of the packets only after being acknowledged that the current generation of the packets have been decoded. For each generation, the sender is idle when it has transmitted N0 + R0 packets but the ACK indicating the decoding of the generation of packets has not been received. Smaller generation size (i.e., N0 and R0 are small) leads to more frequent idle of the sender, causing the waste of bandwidth and throughput. When the generation size is large (i.e., N0 and R0 are large), the receiver needs to wait for a long time to decode a generation of the packets, causing large decoding delay. For TCP VON, its throughput outperforms that of TCP ARQNC. When p is large (p > 0:05), we can moderately increase the redundant factor R to decrease the decoding delay while maintaining the throughput performance. Chapter 3. TCP VON: Online Network Coding Based TCP 70 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0 1 2 3 4 5 6 7 8 9 10 Average delay (s) A v e ra g e  t h ro u g h p u t (M b /s ) TCP VON, R = 0 TCP VON, R = 1 TCP VON, R = 2 TCP ARQNC, N 0  = 200, R 0  = 20 TCP ARQNC, N 0  = 100, R 0  = 10 TCP ARQNC, N 0  = 20, R 0  = 2  p = 0.1  p = 0  p = 0.1 Figure 3.14: Performance comparison for cross trac topology under dierent values of loss probability p. Fig. 3.15 shows the throughput and delay performance of TCP VON and TCP AR- QNC when p = 0:05. For TCP VON, the redundant factor R varies from 0 to 5 with step 1. For TCP ARQNC, we choose dierent values of N0 and R0. For N0 equals to 5000, 500, and 50, we vary R0 from 0 to 1000 with step 500, from 0 to 100 with step 50, and from 0 to 10 with step 5, respectively. The results show that for TCP VON, we can moderately increase R to decrease the decoding delay. However, if we choose a high value of R (e.g., R  4), the throughput performance degrades without giving acceptable delay improvement. This is because the decoding delay is approaching the minimum value (the end-to-end delay) and it cannot be further improved even we continuous to increase R. If we choose a proper value of R (e.g., R = 2), both the throughput and delay performance of TCP VON are better than that of TCP ARQNC. Chapter 3. TCP VON: Online Network Coding Based TCP 71 10 -2 10 -1 10 0 10 1 0 1 2 3 4 5 6 7 8 9 10 Average delay (s) A v e ra g e  t h ro u g h p u t (M b /s ) TCP VON TCP ARQNC, N 0  = 5000 TCP ARQNC, N 0  = 500 TCP ARQNC, N 0  = 50 R = 0 R = 5 R 0  = 0 R 0  = 1000 R 0  = 100 R 0  = 0 R 0  = 0 R 0  = 10 Figure 3.15: Performance comparison for cross trac topology under dierent values of redundant factor R. 3.5 Summary In this chapter, we proposed TCP VON, a new mechanism that incorporates online network coding into TCP, which can be eciently applied in mixed wired and wireless networks. The scheme introduces minor changes to the current protocol stack only at the sender and the receiver. TCP VON mainly includes two mechanisms, congestion control and online network coding control. Congestion control is extended from TCP Vegas so that congestion loss becomes rare and all the packet losses can be regarded as random packet loss. In the online network coding control, the sender transmits redundant coded packets when packet losses are indicated from ACK packets, otherwise it transmits inno- vative packets. As a result, packets can be decoded consecutively instead of generation Chapter 3. TCP VON: Online Network Coding Based TCP 72 by generation and the delay from the sending a packet at the sender to decoding it at the receiver receiver is small, without reducing the throughput performance signicantly. In networks with high loss probability, we introduce a redundant factor R > 0 so that the sender transmits more redundant packets when packet losses are detected. Then, we established a precise Markov chain model to compute the analytical delay performance of TCP VON for R = 0 case. This model has also been extended to a closely approximated model for R > 0 case. We also conducted ns-2 simulations to validate the correctness of our analytical models for both R = 0 case and R > 0 case. Finally, we compared the delay and throughput performance of TCP VON and TCP ARQNC in multihop tandem topology and cross trac topology. Results showed that TCP VON outperforms TCP ARQNC. 73 Chapter 4 Conclusions and Future Work In this chapter, we conclude the thesis by summarizing our contributions. We also suggest several topics for further research. 4.1 Conclusions This thesis covered several aspects of modeling, analysis and enhancement of TCP. The main results were divided into two chapters. In Chapter 2, we proposed a analytical model to determine the steady state throughput of TCP CUBIC in wireless environment. In Chapter 3, we studied a new mechanism that incorporates online network coding into TCP. In Chapter 2, we proposed an analytical model to determine the steady state through- put of TCP CUBIC in wireless environment. We considered both congestion loss and random packet loss and established a Markov model. We derived the stationary distribu- tion of the Markov chain and obtained the average throughput based on the stationary distribution. The accuracy of the model was validated via simulation. Based on our pro- posed model, we evaluated the throughput performance of TCP CUBIC. Results showed Chapter 4. Conclusions and Future Work 74 that random packet loss reduces the normalized average throughput more for end-to- end 
ow with large bandwidth-delay product. In wireless environment, we showed that the throughput of TCP CUBIC can be improved by moderately increasing the window growth factor and the multiplicative decrease factor. In Chapter 3, we proposed TCP VON, a new mechanism that incorporates online network coding into TCP, which can be eciently applied in mixed wired and wireless networks. The scheme introduces minor changes to the current protocol stack only at the sender and the receiver. TCP VON mainly includes two mechanisms, congestion control and online network coding control. Congestion control is extended from TCP Vegas so that congestion loss becomes rare and all the packet losses can be regarded as random packet loss. In the online network coding control, the sender transmits redundant coded packets when packet losses are indicated from ACK packets, otherwise it transmits inno- vative packets. As a result, packets can be decoded consecutively instead of generation by generation and the delay from the sending a packet at the sender to decoding it at the receiver receiver is small, without reducing the throughput performance signicantly. In networks with high loss probability, we introduce a redundant factor R > 0 so that the sender transmits more redundant packets when packet losses are detected. Then, we established a precise Markov chain model to compute the analytical delay performance of TCP VON for R = 0 case. This model has also been extended to a closely approximated model for R > 0 case. We also conducted ns-2 simulations to validate the correctness of our analytical models for both R = 0 case and R > 0 case. Finally, we compared the Chapter 4. Conclusions and Future Work 75 delay and throughput performance of TCP VON and TCP ARQNC in multihop tandem topology and cross trac topology. Results showed that TCP VON outperforms TCP ARQNC. 4.2 Future Work For future work, we can consider several potential extensions of the current work. Empirical study of TCP variants and online network coding based TCP in real networks. We consider carrying out empirical study of dierent TCP variants and network coding based TCP in real networks. By running dierent applications (e.g., FTP, VoIP, video conferencing), we can measure the throughput and delay performance of dierent TCP variants, as well as evaluate whether these TCP variants can eciently support for these applications. Establishment of congestion control models for network coding based on network utility maximization (NUM). We also consider establishing NUM models for network coding based networks. Suitable utility functions will be chosen to formulate the objective function and constraints related to the characteristics of network topology and the attributes of network will be listed. Then, some transformations of the objec- tive function and constraints will be made in order to convert the problem to a convex optimization problem. Finally, the convex optimization problem will be solved in a dis- tributed manner, which can then be interpreted as a network management schemes, such as congestion control, network price feedback and queue management schemes. Chapter 4. Conclusions and Future Work 76 Decoding delay and throughput tradeo for online network coding. For on- line network coding, higher values of the redundant factor R will provide better decoding delay performance, while it may deteriorate the throughput eciency of the end-to-end communication. We are interested in establishing mathematical models to further study the delay throughput tradeo. 77 Bibliography [1] J. F. Kurose and K. W. Ross, Computer Networking: A Top-down Approach, 5th ed. Addison-Wesley, 2010. [2] J. Postel, \Transmission control protocol," IETF RFC 793, Sept. 1981. [3] R. Braden, \Requirements for Internet hosts - communication layers," RFC 1122, Oct. 1989. [4] V. Jacobson, R. Braden, and D. Borman, \TCP extensions for high performance," IETF RFC 1323, May 1992. [5] TCP congestion control. [Online]. Available: http://condor.depaul.edu/jkristof/technotes/congestion.pdf [6] M. Mathis, J. Mahdavi, S. Floyd, and A. Romanow, \TCP selective acknowledgment options," IETF RFC 2018, Oct. 1996. [7] S. Floyd, T. Henderson, and A. Gurtov, \The NewReno modication to TCP's fast recovery algorithm," IETF RFC 3782, Apr. 2004. Bibliography 78 [8] T. Kelly, \Scalable TCP: Improving performance in highspeed wide area networks," ACM SIGCOMM Computer Communication Review, vol. 33, no. 2, pp. 83{91, Apr. 2003. [9] L. Brakmo and L. Peterson, \TCP Vegas: End-to-end congestion avoidance on a global Internet," IEEE Journal on Selected Areas in Communication, vol. 13, no. 8, pp. 1465{1480, Oct. 1995. [10] I. Rhee and L. Xu, \A new TCP-friendly high-speed TCP variant," in Proc. PFLD- Net'05, Lyon, France, Feb. 2005. [11] G. D. J. Leith and R. N. Shorten, \Experimental evaluation of Cubic-TCP," in Proc. PFLDNet'07, Los Angeles, CA, Feb. 2007. [12] M. Bateman, S. Bhatti, G. Bigwood, D. Rehunathan, C. Allison, and T. Henderson, \A comparison of TCP behaviour at high speeds using ns-2 and Linux," in Proc. of Communications and Networking Simulation, Ottawa, Canada, Apr. 2008. [13] A. DeSimone, M. C. Chuah, and O.-C. Yue, \Throughput performance of transport- layer protocols over wireless LANs," in Proc. of IEEE GLOBECOM, Houston, TX, Dec. 1993. [14] G. Xylomenos, G. Polyzos, P. Mahonen, and M. Saaranen, \TCP performance issues over wireless links," IEEE Communications Magazine, vol. 31, no. 4, pp. 52{58, Apr. 2001. Bibliography 79 [15] S. Xu and T. Saadawi, \Performance evaluation of TCP algorithms in multi-hop wireless packet networks," Wireless Communications and Mobile Computing, vol. 2, no. 1, pp. 85{100, Feb. 2002. [16] T. V. Lakshman and U. Madhow, \The performance of TCP/IP for networks with high bandwidth-delay products and random loss," IEEE/ACM Trans. on Network- ing, vol. 5, no. 3, pp. 336{350, Jun. 1997. [17] I. F. Akyildiz, G. Morabito, and S. Palazzo, \TCP-Peach: A new congestion control scheme for satellite IP networks," IEEE/ACM Trans. on Networking, vol. 9, no. 3, pp. 307{321, June 2001. [18] J. Liu and S. Singh, \ATCP: TCP for mobile ad hoc networks," IEEE Journal on Selected Areas in Communications, vol. 19, no. 7, pp. 1300{1315, July 2002. [19] A. Bakre and B. R. Badrinath, \I-TCP: Indirect TCP for mobile hosts," in Proc. ICDCS'95, Vancouver, Canada, May 1995. [20] K. Brown and S. Singh, \M-TCP: TCP for mobile cellular networks," ACM SIG- COMM Computer Communication Review, vol. 27, no. 5, pp. 19{43, Oct. 1997. [21] H. Balakrishnan, S. Seshan, and R. H. Katz, \Freeze-TCP: A true end-to-end TCP enhancement mechanism for mobile environments," in Proc. of IEEE INFOCOM, Tel-Aviv, Israel, Mar. 2000. Bibliography 80 [22] C. P. Fu and S. C. Liew, \TCP Veno: TCP enhancement for transmission over wire- less access networks," IEEE Journal on Selected Areas in Communications, vol. 21, no. 2, pp. 216{228, Feb. 2003. [23] C. Casetti, M. Gerla, S. Mascolo, M. Y. Sanadidi, and R. Wang, \TCP Westwood: Bandwidth estimation for enhanced transport over wireless links," in Proc. of ACM Mobicom, Rome, Italy, July 2001. [24] K. Xu, Y. Tian, and N. Ansari, \TCP-Jersey for wireless IP communications," IEEE Journal on Selected Areas in Communications, vol. 22, no. 4, pp. 747{756, May 2004. [25] R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung, \Network information 
ow," IEEE Trans. on Information Theory, vol. 46, no. 4, pp. 1204{1216, Jul. 2000. [26] S. Y. R. Li, R. W. Yeung, and N. Cai, \Linear network coding," IEEE Trans. on Information Theory, vol. 49, no. 2, pp. 371{381, Feb. 2003. [27] R. Koetter and M. Medard, \An algebraic approach to network coding," IEEE/ACM Trans. on Networking, vol. 11, no. 5, pp. 371{381, Oct. 2003. [28] P. A. Chou, Y. Wu, and K. Jain, \Practical network coding," in Proc. of 41st Allerton Annual Conference on Communication, Control, and Computing, Urbana- Champaign, IL, Oct. 2003. Bibliography 81 [29] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, \XORs in the air: Practical wireless network coding," IEEE/ACM Trans. on Networking, vol. 16, no. 3, pp. 497{510, June 2008. [30] S. Chachulski, M. Jennings, S. Katti, and D. Katabi, \Trading structure for ran- domness in wireless opportunistic routing," in Proc. of ACM SIGCOMM, Kyoto, Japan, Aug. 2007. [31] D. S. Lun, M. Medard, R. Koetter, and M. Eros, \On coding for reliable communi- cation over packet networks," Physical Communication, vol. 1, no. 1, pp. 3{20, Mar. 2008. [32] Y. Lin, B. Li, and B. Liang, \CodeOR: Opportunistic routing in wireless mesh net- works with segmented network coding," in Proc. of IEEE International Conference on Network Protocols (ICNP), Orlando, FL, Oct. 2008. [33] J. K. Sundararajan, D. Shah, and M. Medard, \ARQ for network coding," in Proc. of IEEE International Symposium on Information Theory, Toronto, Canada, Jul. 2008. [34] ||, \Online network coding for optimal throughput and delay - The three-receiver case," in Proc. of International Symposium on Information Theory and Its Applica- tions (ISITA), Auckland, New Zealand, Dec. 2008. Bibliography 82 [35] J. Barros, R. A. Costa, D. Munaretto, and J. Widmer, \Eective delay control in online network coding," in Proc. of IEEE INFOCOM, Rio de Janeiro, Brazil, Apr. 2009. [36] D. E. Lucani, M. Medard, and M. Stojanovic, \Online network coding for time- division duplexing," in Proc. of IEEE GLOBECOM, Miami, FL, Dec. 2010. [37] Y. Lin, B. Liang, and B. Li, \SlideOR: Online opportunistic network coding in wireless mesh networks," in Proc. of IEEE INFOCOM, San Diego, CA, Mar. 2010. [38] P. S. David and A. Kumar, \Network coding for TCP throughput enhancement over a multi-hop wireless network," in Proc. of International Conference on Communi- cation Systems Software and Middleware and Workshops, Bangalore, India, Jan. 2008. [39] Z. Liu and S. Jin, \Diagnosing the limitations of network coding at transport lay- er," in Proc. of IEEE International Symposium on Wireless Pervasive Computing (ISWPC), Modena, Italy, May 2010. [40] S. Hassayoun, P. Maille, and D. Ros, \On the impact of random losses on TCP performance in coded wireless mesh networks," in Proc. of IEEE INFOCOM, San Diego, CA, Mar. 2010. [41] L. Chen, T. Ho, S. H. Low, M. Chiang, and J. C. Doyle, \Optimization based rate control for multicast with network coding," in Proc. of IEEE INFOCOM, Anchorage, AK, May 2007. Bibliography 83 [42] H. Seferoglu and A. Markopoulou, \Network coding-aware queue management for unicast 
ows over coded wireless networks," in Proc. of IEEE International Sympo- sium on Network Coding (NetCod), Toronto, Canada, June 2010. [43] J. K. Sundararajan, D. Shah, M. Medard, M. Mitzenmacher, and J. Barros, \Net- work coding meets TCP," in Proc. of IEEE INFOCOM, Rio de Janeiro, Brazil, Apr. 2009. [44] J. K. Sundararajan, D. Shah, M. Medard, S. Jakubczak, M. Mitzenmacher, and J. Barros, \Network coding meets TCP: Theory and implementation," Proceedings of the IEEE, vol. 99, no. 3, pp. 490{512, Mar. 2011. [45] M. Kim, M. Medard, and J. Barros, \Modeling network coded TCP throughput: A simple model and its validation," in Proc. of International Conference on Perfor- mance Evaluation Methodologies and Tools, Cachan, France, May 2011. [46] W. Bao and V. Wong, \A model for steady state throughput of TCP CUBIC," in Proc. of IEEE GLOBECOM, Miami, FL, Dec. 2010. [47] J. Padhye, V. Firoiu, D. Towsley, and J. Kurose, \Modeling TCP throughput: A simple model and its empirical validation," in Proc. of ACM SIGCOMM, Vancouver, Canada, Sept. 1998. [48] The network simulator - ns-2. [Online]. Available: http://www.isi.edu/nsnam/ns/

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0105062/manifest

Comment

Related Items