A Probability Model for TCP Slow Start

This paper presents one approach to modeling of TCP connection during the slow start phase. Such modeling can be used for TCP connection analysis with reduced computation complexity compared to the packet-level simulators. Proposed model is validated by comparing the results obtained from ns-2 simulations. Introduction Application protocols mainly used on the Internet, such as HTTP or SMTP, use TCP protocol for reliable transport. TCP connection performance analysis can be carried out in two different ways. First one is simulation of TCP connection at the packet-level. This approach leads to accurate results but also requires long simulation time. Alternative approach is to model the TCP behaviour analytically, significantly reducing simulation time while simultaneously keeping accuracy at an acceptable level. This paper reviews models available in the literature and proposes an alternative analytical TCP model during the slow-start phase. TCP behavior can be described with different models. Packet-level models are the most accurate since they employ full TCP stack implementation. However, when analyzing large-scale networks or simple networks with high throughputs, packetlevel simulators are impractical due to long simulation time. An alternative approach is to use mathematical abstractions to model the TCP behavior. One way to abstract the TCP behavior through mathematical tools is to use differential equations. Another approach is based on probability analysis. In this approach, statistical formulas are used to describe TCP behaviour in different stages. Aggregating these models, the full TCP behavior could be obtained. In this paper, a probability model for the slow-start TCP stage is derived. The derived model is validated by comparing the results with the packet-level simulation tool ns-2 [7]. Finally, future directions for employment of probability models of other TCP stages are given. 1 TCP Protocol TCP is a reliable connection-oriented transport protocol for packet-switched networks. Reliability is achieved by employing acknowledgements (ACKs) [2]. Using ACKs and sequence numbers, the transmitter keeps the track of packets that are successfully delivered to the receiver. TCP operates in different stages: Slow Start, Congestion Avoidance, Fast Retransmit, Fast Recovery and Timeout. Transition between stages is determined by packet loss or acknowledgement of predefined number of packets. The window size determines the maximum number of packets that a transmitter may send before receiving the first acknowledgement. In the Slow Start phase, window size is incremented with every received ACK. Time interval, from departure of the first packet to the last packet in a window, represents round. The window size varies with the rate of the packet loss in the network. Hence, the packet loss probability increases with the number of sent packets due to the congestion in the network. Generally, window size wi grows in rounds and can be expressed as: 1 0 1 1 1 1 1 1 1 − − − − − ⋅ = ⋅ = + ⋅ = + = i i i i i i w w b w w b w w γ γ (1) where b is number of packets acknowledge by one ACK, and i is the round number and w0 is the initial window size. Total number of packets sent in slow start including the round i is 1 1 0 0 1 2 0 0 − − ⋅ = ⋅ + + + ⋅ + = − γ γ γ γ γ i i i w w w w ssdata (2) When a packet loss occurs during the slow start stage, there are two mechanisms to detect it. The first mechanism detects packet loss by using timeouts (TO). The second mechanism detects packet loss upon receiving three duplicate ACKs. SNE Simulation Notes Europe – Print ISSN 2305-9974 | Online ISSN 2306-0271 SNE 21(1), 2011, 45-48 | doi: 10.11128/sne.21.sn.10047 A Gogic et al. Probability Model for TCP Slow Start 46 SNE 21(1) – 4/2011 TN 2 Approaches for Modelling the Packet Switched Networks There are several approaches for modeling packet switched networks. The most accurate network models are packet-level models that keep track of individual packets. These models are implemented in network simulators, such as ns-2 [7]. The main drawback of packet-level model is a large computational effort required to keep track of each virtual packet in large scale simulations. Analytical models are based on idea to model the TCP network mathematically in order to reduce complexity involved in simulations [1, 6]. These models do not consider the network dynamics. They assume that round-trip time and loss probability are constant and there are no interactions between TCP flows. Fluid models are intended for simulation of packet networks. They overcome network scalability problem by keeping track of average quantities for relevant network parameters [5, 4]. Additionally, they use assumption that the bit rates are piecewise constant. Hybrid models use continuous time state variables with discrete time events [3]. Hybrid simulations require significantly less computational resources than packet level simulators. However, solution of hybrid equations is still necessary in order to simulate networks. 3 Probability Model for TCP Slowstart Stage There are two approaches for creating probability models of TCP behaviour. The source centric model assumes that packets leave the source with a certain loss probability [1]. The assumption taken by the second model is that the network generates loss probabilities for each packet [5]. Thus, the arrival process is represented by Poisson random process. In this paper we use the first approach with the further assumptions: the packet losses in two successive rounds are not correlated, packet loss occurs only in the forward direction; packet losses are independent of window size. Model detects packet losses by triple duplicates and TOs. Based on the source-centric model [1,6], we derived the expected value of number of packets sent in the slow start phase as a function of packet loss probability p, the initial size of congestion window wi and the number of packets acknowledged by one ACK. We further distinguish two boundary cases related to the position where packet was lost. The first case is characterized by the packet loss occurring at the beginning of the round (Figure 1). For the second case, the packet loss occurs at the end of the round (Figure 2). Figure 1. Slow-start phase, packet drop occurred at beginning of the round i. Figure 1 shows the number of acknowledge packets -1. Taking into consideration equation (2), we can write