Abstract on the theme of master's work
Table of contents
- Introduction
- 1. Theme urgency
- 2. Goal and tasks of the research
- 3. Expected scientific novelty
- 4. Analysis of existent researches and publications
- 5. Modeling and estimation of algorithms TCP Reno и TCP Vegas
- 5.1 Analysis of work of algorithms TCP Reno и TCP Vegas
- 5.2 Mathematical description of fluid flow model for algorithms TCP Reno и TCP Vegas
- 5.3 Modeling of work of algorithms TCP Reno и TCP Vegas and analysis of the got results
- Conclusion
- Note
- References
Introduction
Much of today’s Internet traffic is carried using the Transmission ControlProtocol (TCP), and consequently there has been a significant amount of research toward modeling and understanding the impact that this protocol has onle transmission times and network utilization. TCP has been and will continue to be an evolving protocol, and as such, one important task of these models is to facilitate comparisons between the different favors of TCP.
1. Theme urgency
The problem of overload in the networks of TCP/IP arises up in the case when the amount of transferrable information begins to approach the value of possible carrying capacity of network. The basic indexes of quality of service get worse thus. These worsenings can be expressed in the increase of number of the lost packages and time of delays. A management overloads is an actual task, as an amount of end users of global network, and, consequently, volumes of transferrable information, increased constantly. The stake of multimedia traffic of the real time grows also, influence of overloads on which especially critically. The task of mechanisms of management overloads consists in that, to support the amount of information, transferrable on a network, below than level at which the carrying capacity of network begins to slump, limiting the streams of incoming and outgoing traffic.
For the effective use of carrying capacity it is needed to choose an exactly that algorithm which will provide the maximal use of resources. Therefore there is a necessity to estimate efficiency of work of the chosen algorithm.
Master's degree work is devoted actual scientific task of estimation of algorithms for a fight against the overloads of protocols of a transport level of stack of TCP/IP. As mathematical a model the fluid flow model, which allows to take into account all features of work of algorithms, is used.
2. Goal and tasks of the research
A research purpose is Modeling and estimation of algorithms for a fight against the overloads of protocols of a transport level of stack of TCP/IP.
Main tasks of the research:
- Analysis of basic algorithms which are used in protocol of TCP for a fight against overloads.
- To develop realization of mathematical fluid flow model for the chosen algorithms.
- To conduct the design of work of the chosen algorithms at different entry parameters.
- On the basis of the got results to conduct an analysis and compare work of different algorithms in identical terms.
Research object:multiservice network
Research subject:algorithms for a fight against the overloads of protocols of a transport level of stack of TCP/IP
3. Expected scientific novelty
The scientific novelty of master's degree work consists of that the method of complex estimation of algorithms for a fight against the overloads of protocols of a transport level of stack of TCP/IP is offered.
4. Analysis of existent researches and publications
A problem of overload in ductings of connection of networks of TCP/IP is very actual now, plenty of works, essence of this problem, reasons of its origin and way of decision, opens up in which, is therefore devoted it [1, 2,7,8,9].
Research of work of a fight against the overloads of protocols of a transport level of stack of TCP/IP is described in works [3 - 5, 10].
The fluid flow model which got wide spreading resulted in-process [6].
5. Modeling and estimation of algorithms TCP Reno и TCP Vegas
At the moment, enough anti-overload algorithms are developed, but for research selected algorithms TCP Reno and TCP Vegas, because they are the most widespread implementations of the TCP algorithm to date.
5.1 Analysis of work of algorithms TCP Reno и TCP Vegas
TCP Reno has two stages of change of window extent:
1) slow start phase
2) congestions-avoidance phase
When a sender gets confirmation of delivery in the moment of time of t + tA [с] current value a window of overload of cwnd(t) extent will be transformed in cwnd(t + tA) concordantly (1):
where ssth(t) – value of threshold, at which TCP passes from the phase of slow start in the phase of avoidance of overload.
When because of timeout found out the losses of packages, value of cwnd(t) and ssth(t) brush up as follows:
When TCP finds out the losses of packages in obedience to the algorithm of rapid transmission, cwnd(t) and ssth(t) brush up differently:
TCP Reno after passes to the congestions-avoidance phase. On this stage a window extent is increased on one package, when turns out dublicate confirmation.
In the case of timeout of cwnd(t) and ssth(t) assume an air (2) [4].
TCP Vegas adopts a more sophisticated bandwidth estimation scheme. It uses the difference between expected and actual flows rates to estimate the available bandwidth in the network. The idea is that when the network is not congested, the actual flow rate will be close to the expected flow rate. Otherwise, the actual flow rate will be smaller than the expected flow rate. TCP Vegas,using this difference in flow rates, estimates the congestion level in the network and updates the window size accordingly. Note that this difference in the flow rates can be easily translated into the difference between the window size and the number of acknowledged packets during the round trip time, using the equation
where Expected is the expected rate, Actual is the actual rate, and BaseRTT is the minimum round trip time
The details of the algorithm are as follows:
1. First, the source computes the expected flow rate
where CWND – is the current window size.
2. Second, the source estimates the current flow rate by using the actual round trip time according
where RTT is the actual round trip time of a packet.
3. The source, using the expected and actual flow rates, computes the estimated backlog in the queue from (4)
4. Based on Diff, the source updates its window size as follows:
Figure 1 illustrates the behavior of TCP Vegas. Consider a simple network with one connection and one link with capacity C. Let BaseRTT be the minimum round trip delay. The throughput of this connection is window/(BaseRTT) when window < C * BaseRTT.
Figure 1 – Window control of TCP Vegas
In the figure 1, w corresponds to the window size where
5.2 Mathematical description of fluid flow model for algorithms TCP Reno и TCP Vegas
The model of consists of the following coupled nonlinear differential equations with timevarying delay:
where W(t) denotes the average of TCP windows size (packets), Q(t) is the average of queue length (packets), R(t)C is the queue capacity (packets/sec), N(t) is the number of TCP sessions and p(t)
The function of G(x) is described expression:
The first differential equation (8) and (9) describes the TCP window control dynamic. Indeed, the first term in (8) 1/R(t) describes the window’s additive increase phase, and the second term W(t)/2 the multiplicative decreasing phase (including the packet marking probability). The term of G(a-diff) in equalization (9) describes the increase of window extent on 1, and the second term of G(Diff-b) is diminishing of window extent on 1.
Equation (10) describes the bottleneck queue length as the difference between the packet arrival rate NW/R and the link capacity C, assuming that there are no internal dynamics in the bottleneck (roughly speaking, a simple integrator).
Using fluid flow models, Active Queue Management can be interpreted as a feedback control problem, where the control action consists of marking packets (with probability p) as a function of the measured queue length Q [6].
For the best understanding of principle of fluid flow model will present equalizations (8) and (10) by a chart which is resulted on a fig. 2
Figure 2 – Block-diagram of TCP’s congestion-avoidance flow-control mode for TCP Reno
Principle of fluid flow model model of stream for TCP Vegas resulted on a fig. 3.
Figure 3 – Block-diagram of TCP’s congestion-avoidance flow-control mode for TCP Vegas
5.3 Modeling of work of algorithms TCP Reno и TCP Vegas and analysis of the got results
For simulation the simplest model of a multiservice network – model with single bottleneck was selected. For this topology of model of a network all characteristics of telecommunication traffic of the integrated packet switched network, including its self-similitude and scale invariance are inherent.
On fig.4 the topology of such network is resulted.
Figure 4 – Topology of network with single bottleneck
(animation: 7 frames, 1 s delay, size 145 kB, an unlimited number of repetitions, made with gifovina.ru)
For a design use an application of MATLAB package.
Entry parameters of design: RTT R = 0,1 with, maximal length of turn of Qmax = 200 packages, the amount of senders of s changes dinamically.
Design results are resulted on fig. 5–6.
Figure 5 – Chart of dependence of window extent W(t)
Figure 6 – Chart of dependence of length of turn Q(t)
Analysing charts, resulted on fig.5–6, we will mark that middle window size TCP Vegas less than, than in TCP Reno, but due to less oscillation TCP Vegas passes the greater amount of information.
The fairness index for to provide the same throughput to all users [11]
The calculation of fairness index for the amount of the lost packages
where vli – amount of the lost packages for і-th user.
It is possible to draw conclusion on the basis of the got results, that at the use of TCP Reno distributing of carrying capacity between users is more uneven, than at the use of TCP Vegas. Because of such distributing of carrying capacity the algorithm of TCP Reno is a greater amount of losses of packages, what in a communication channel with the use of TCP Vegas.
Conclusion
Algorithms of transport layer of TCP/IP stack were researched, modeled and analyzed. Algorithms TCP Reno and TCP Vegas were selected for the research. The principles of operation of selected algorithms were reviewed. The window size in TCP Reno is changed cyclically in a normal situation. Window size increases during each cycle to packet loss. When is the packet loss, TCP Reno reduces the window size to half the current size. This is called additive increase and multipli-cative decrease. TCP Vegas adopts more complex evaluation capacity. It uses the difference between the expected and actual flow rate to estimate the network bandwidth. The idea is that when the network is not congested, the actual flow rate will be close to the expected. Otherwise, the actual flow rate will be less than the expected flow rate. TCP Vegas with this speed difference flow assesses the level of congestion in the network and accordingly updates the window size.
To simulate the fluid flow model used by what were considered features of the selected algorithms. Using fluid flow model active queue management can be interpreted as a feedback control problem where the control action consists of marking packets (with probability p), depending on the length of the measured queue Q.
For the study of anti-congestion algorithms were used simple model multiservice network – a model with a single bottleneck. For a given network topology model has all the characteristics of telecommunication traffic integrated packet-switched networks, including its self-similarity and scale invariance.
Based on these results the following conclusions were made: Simulation of algorithms protocols TCP Reno and TCP Vegas has shown that two-phase job of the first algorithm leads to significant fluctuations in network load more evenly and losses than the algorithm TCP Vegas. At the expense of a more complex control circuit bandwidth, achieved reduction of vibrations payload on the network and reducing losses.
Our simulations show that the algorithm of TCP Vegas more efficiently uses the bandwidth of the communication channel than TCP Reno due to the smaller window size fluctuations
Note
In the process of abstract writing the master's work hasn't been finished yet. Date of finish: December, 2013. The full thesis of master's work and materials according to the theme may be received from the author or his scientific advisor after the pointed date.
References
- Кучерявый Е.А. Управление трафиком и качество обслуживания в сети Интернет / Кучерявый Е.А. – СПб.: Наука и техника, 2004. – 336 с.
- Джамалипур А. Беспроводной мобильный Интернет. Архитектура, протоколы и сервисы/Джамалипур А. ; [пер.с англ. Ш. Салиев, В. Орлов] – М., Техносфера, 2009 – 496 с.
- Fall K. Simulation based comparisons of Tahoe, Reno and SACK TCP / K. Fall , S. Floyd – Computer Communications Review, , July 1996. —26(3):5-21.
- Analysis and comparison of TCP Reno and Vegas [Електронний ресурс] /Jeonghoon Mo, Richard J. La, Venkat Anantharam, Jean Walrand//INFOCOM – 1999 – Режим доступу до статті: http://www.eecs.berkeley.edu/~ananth/1999-2001/Richard/MoLaInfocom1999.pdf
- Bonald Thomas Comparison of TCP Reno and TCP Vegasvia Fluid Approximation [Електронний ресурс]/Bonald Thomas// RR3563, Unite de recherche INRIA Sophia Antipolis Cedex (France) – 1998 – 34 pages, режим доступу до статті: netlab.caltech.edu/FAST/references/bonald_comparison.pdf
- A control theoretic analysis of RED [Електронний ресурс] / C.V. Hollot, Vishal Misra, Don Towsley, Wei-Bo Gong//INFOCOM — – 2001 – Режим доступу до статті: ftp://gaia.cs.umass.edu/pub/MisraInfocom01-RED-Control.pdf
- Jacobson V. Congestion Avoidance and Control/ V. Jacobson – Proceedings, SIGCOMM '88, Computer Communication Review, August 1988; reprinted in Computer Communication Review – January 1995.
- Jacobson V. Modified TCP Congestion Avoidance Algorithm/ V. Jacobson - End2 end-interest mailing list, 20 – April 1990.
- Srikant, R. The Mathematics of Internet Congestion Control (Systems and Control: Foundations and Applications)/ Rayadurgam Srikant – Birkhauser Boston, 2004.
- Батыр С.С. Построение модели сети передачи данных для исследований технологии AQM/Батыр С.С., Хорхордин А.В. // Сборник научных трудов ДонИЖТ Выпуск:28 . – Донецк, 2011 с.108-116
- Jain R. A Quantitative Measure of fairness and discrimination for resource allocation in systems/ R. Jain ,D.M. Chiu ,W. Hawe – DEC TR-301, Littleton, MA: Digital Equipment Corporation, 1984.