The Chaotic Nature of TCP Congestion Control And& Veres Ericsson, Traffic Analysis and Network Performance Laboratory Budapest, Hungary e-mail : Andras .Veres @ 1 t.eth .ericsson. se Mikl6s Boda Ericsson Research Stockholm, Sweden e-mail: Miklos .Boda@ era-t.ericsson .se Abstract- In this paper we demonstrate how TCP congestion control can show chaotic behavior. We demonstrate the major features of chaotic systems in TCPlIP networks with examples. These features include un- predictability, extreme sensitivity to initial conditions and odd periodicity. Previous work has shown the fractal nature of aggregate TCPAP traffic and one explanation to this phenomenon was that traffic can be approxi- mated by a large number of ON/OFF sources where the random ON and/or OFF periods are of length described by a heavy tailed distribution. In this paper we show that this argument is not necessary to explain self- similarity, neither randomness is required. Rather, TCP itself as a deter- ministic process creates chaos, which generates self-similarity. This prop- erty is inherent in todays TCPlIP networks and it is independent of higher layer applications or protocols. The two causes: heavy tailed ONlOFF and chaotic TCP together contribute to the phenomena, called fractal nature of Internet traffic. Keywords-TCP congestion control, fractal traffic, chaotic models. I. INTRODUCTION Traffic models used to model current Internet traffic can be categorized into two major groups: linWsource and network level models. Link level models fit statistical models to mea- surements of traffic on network links or traffic sources for ex- ample a WWW server. Recently, the largest contribution in this area was the exploration of fractal and long-range depen- dent property of traffic, namely that the second order statis- tics of traffic volumes observed at different scales does not change. This resulted as a revolution in performance modeling and questioned previous models based on Markovian behavior (see Paxson and Floyd [ 121). We mention two major publica- tions in this area: Leland, Taqqu, Willinger and Wilson demon- strated through rigorous tests that Ethernet traffic is self-similar [8], Crovella and Bestavros proved how WWW as the major contributor to current Internet traffic can cause long-range de- pendence and self-similarity [4]. Chaotic-maps appeared as ef- ficient and parsimonious methods to generate packet traffic on the 1inWsource level, see for example the work by Erramilli and Singh [7] and the same authors with Pruthi [6]. The drawback of IinWsource level models is that they dis- regard one of the major properties of todays Internet, namely that the majority (80-90%) of traffic is generated and con- trolled by the TCP protocol, which is adaptive in nature. The consequence of adaptivity is that the source behavior cannot be disconnected from the network configuration (e.g., routing, scheduling, buffer management). Traffic statistics change if the network configuration changes, so a linkhource model is valid only for the configuration (and all other circumstances) 0-7803-5880-5/00/$10.00 (c) 2000 IEEE that were present at the time of model fitting. The recent paper of Arvidsson and Karlsson [I] demonstrates that the adaptive simulated traffic behaves significantly differently in the buffers as the link/source models. This problem called for network level models, which try to form a unified model taking into account the cooperation of all source and network mechanisms. Due to the complexity of this problem the models published in this area are still in early phase. Mathis, Semske, Mahdavi and Ott [9] published an analytic model about macroscopic behavior of TCP, Padhye, Firoiu, Towsley and Kurose [ 131 model the impact of the time- out mechanism on TCP throughput. The drawback of these models is that they assume that TCP congestion control always behaves in a nice periodic and predictable fashion. This is in contradiction with the measurements and simulations of TCP traffic. In this paper we bridge the two modeling approaches by modeling the network level behavior of aggregate TCP flows while reproducing the complexity found in 1inWsource level models. The key finding in this paper is that cooperating TCP congestion control processes together form a determinis- tic chaotic system which is able to produce periodic and non- periodic, predictable and non-predictable, short-range depen- dent and also self-similar behavior. We are going to demon- strate some of the key properties of chaotic systems present in the Internet. What is chaos? A system is called chaotic if it satisfies the following conditions [5]: nonlinearity; determinism; order in disorder; sensitivity to initial conditions or the "butterfly effect"; unpredictability. Nonlinearity means that the system is controlled through nonlinear functions. In case of TCP, nonlinear functions are used for round-trip time (R'IT) measurements, slow start and congestion avoidance. Determinism means that the system's future is fully de- scribed by the past. This is also true, as TCP works in a self- clocking way, no randomness is used, every event (e.g., sending of a packet or time-out) is completely determined by the past. We are not going to discuss the above two properties because they are obviously characteristic of TCP. However, the further 1715 IEEE INFOCOM 2000attributes need more insight and proof - these properties are discussed in detail in the paper. The present network level models for TCP/IP traffic assume periodic and stable behavior. Such behavior is demonstrated by simulations in Section 11, but in the next section we prove that this behavior is not universal by giving examples for more complex periodic and finally non-periodic patterns. In Section I11 we introduce the notion of attractors - hidden multidimensional trajectories of the TCP process, and give a method to efficiently visualize them, thus making it possible to examine the hidden order in an otherwise seemingly random process. A system satisfying the buttefly effect is extremely sensitive to small changes in the initial parameters or minute perturba- tions of the system. This property is the major landmark of chaotic systems. This property of TCP is demonstrated in Sec- tion V and we also quantify the sensitivity of the system by measuring the Lyapunov exponent of the system’s