Congestion Control and Active Queue Management During Flow Startup

Show full item record

Permalink

http://urn.fi/URN:ISBN:978-951-51-5586-3
Title: Congestion Control and Active Queue Management During Flow Startup
Author: Järvinen, Ilpo
Contributor: University of Helsinki, Faculty of Science, Department of Computer Science
Doctoral Programme in Computer Science
Publisher: Helsingin yliopisto
Date: 2019-11-14
Belongs to series: Series of publications A / Department of Computer Science, University of Helsinki - URN:ISSN:1238-8645
URI: http://urn.fi/URN:ISBN:978-951-51-5586-3
http://hdl.handle.net/10138/306423
Thesis level: Doctoral dissertation (article-based)
Abstract: Transmission Control Protocol (TCP) has served as the workhorse to transmit Internet traffic for several decades already. Its built-in congestion control mechanism has proved reliable to ensure the stability of the Internet, and congestion control algorithms borrowed from TCP are being applied largely also by other transport protocols. TCP congestion control has two main phases for increasing sending rate. Slow Start is responsible for starting up a flow by seeking the sending rate the flow should use. Congestion Avoidance then takes over to manage the sending rate for flows that last long enough. In addition, the flow is booted up by sending the Initial Window of packets prior to Slow Start. There is a large difference in the magnitude of sending rate increase during Slow Start and Congestion Avoidance. Slow Start increases the sending rate exponentially, whereas with Congestion Avoidance the increase is linear. If congestion is detected, a standard TCP sender reduces the sending rate heavily. It is well known that most of the Internet flows are short. It implies that flow startup is a rather frequent phenomenon.  Also, many traffic types exhibit an ON-OFF pattern with senders remaining idle for varying periods of time. As the flow startup under Slow Start causes exponential sending rate increase, the link load is often subject to exponential load transients that escalate in a few round trips into overload, if not controlled properly. It is true especially near the network edge where traffic aggregation is limited to a few users. Traditionally much of the congestion control research has focused on behavior during Congestion Avoidance and uses large aggregates during testing. To control router load, Active Queue Management (AQM) is recommended. The state-of-the-art AQM algorithms, however, are designed with little attention to Slow Start. This thesis focuses on congestion control and AQM during the flow startup. We explore what effect the Initial Window has to competing latency-sensitive traffic during a flow startup consisting of multiple parallel flows typical to Web traffic and investigate the impact of increasing Initial Window from three to ten TCP segments. We also highlight what the shortcomings are in the state-of-the-art AQM algorithms and formulate the challenges AQM algorithms must address to properly handle flow startup and exponential load transients. These challenges include the horizon problem, RTT (round-trip time) uncertainty and rapidly changing load. None of the existing AQM algorithms are prepared to handle these challenges. Therefore we explore whether an existing AQM algorithm called Random Early Detection (RED) can be altered to control exponential load transients effectively and propose necessary changes to RED. We also propose an entirely new AQM algorithm called Predict. It is the first AQM algorithm designed primarily for handling exponential load transients. Our evaluation shows that because of shortcomings in handling exponential load transients, the state-of-the-art AQM algorithms often respond too slowly or too fast depending on the actual RTT of the traffic. In contrast, the Predict AQM algorithm performs timely congestion indication without compromising throughput or latency unnecessarily, yielding low latency over a large range of RTTs. In addition, the load estimation in Predict is designed to be fully compatible with pacing and the timely congestion indication allows relaxing the large sending rate reduction on congestion detection.Ruuhkanhallinta on yksi keskeisimpiä Internetin sujuvan dataliikenteen turvaavia toimintoja. Ilman toimivaa ruuhkanhallintaa Internet ylikuormittuisi ja tulisi käyttökelvottomaksi. TCP-protokollaa (Transmission Control Protocol) on käytetty siirtämään tietoa Internetissä jo vuosia. Sen sisäänrakennettu ruuhkanhallinta on osoittautunut tehokkaaksi estämään pitkäkestoista verkon ylikuormittumista. TCP:n keskeiset ruuhkanhallinta-algoritmit ovat hidas aloitus (Slow Start) ja ruuhkan välttely (Congestion Avoidance). Hidasta aloitusta käytetään vallitsevan verkkotilanteen salliman lähetysnopeuden selvittämiseen. Kun sopiva lähetysnopeus on saavutettu, TCP siirtyy käyttämään ruuhkan välttely -algoritmia. Hitaan aloituksen ja ruuhkan välttelyn käyttämät algoritmit eroavat merkittävästi toisistaan. Hidas aloitus kasvattaa lähetysnopeutta eksponentiaalisesti, kun taas ruuhkan välttelyn aikana lähetysnopeus kasvaa lineaarisesti. Koska Internetissä yhden tiedonsiirtoyhteyden yli siirrettävä tietomäärä on tyypillisesti vähäinen ja uusien yhteyksien tiheä avaaminen sekä lähetystauot ovat erittäin yleisiä, aiheutuu hitaan aloituksen käyttämisestä usein toistuvia kuormapiikkejä, joiden aikana kuorman kasvu verkossa on eksponentiaalista. Verkon reuna-alueella lähellä käyttäjän laitetta verkon kuorma koostuu tyypillisesti vain yhden tai muutaman käyttäjän liikenteestä, jolloin kuormatason vaihtelu on suurta ja siirtyminen matalasta kuormasta ylikuormaan tapahtuu hitaan aloituksen käyttämisen takia erittäin nopeasti. Standardinmukaisen TCP:n hidas aloitus -algoritmi edellyttää ruuhkasignaalia joltakin verkkopolun liikennettä välittävältä reitittimeltä ennen kuin hidas aloitus lopetetaan ja siirrytään ruuhkan välttely -algoritmin käyttöön. Valtaosa aiemmasta ruuhkanhallintaan kohdistuvasta tietoliikennetutkimuksesta on sivuuttanut hitaan aloituksen ja on keskittynyt huomioimaan pelkästään ruuhkan välttely -algoritmille ominaisen toiminnan. Tämä väitöstyö sen sijaan keskittyy ongelmiin, joita aiheutuu uusien yhteyksien avaamisesta ja hitaan aloituksen käyttämisestä. Tämä väitöstyö osoittaa etteivät reitittimissä toimivat jononhallinta-algoritmit (Active Queue Management), jotka säätelevät ruuhkasignaaleja, yleensä reagoi riittävän nopeasti hitaaseen aloitukseen. Siksi hidas aloitus pääsee kiihdyttämään lähetysnopeutta huomattavasti yli verkkotilanteen mukaisesti määrittyvän sopivan lähetysnopeuden. Tämä ylitys siirtyy yleensä suoraan siirtoviiveeseen kasvattaen sitä, mikä myös osoitetaan tapahtuvan hitaan aloituksen aikana nykyaikaisia jononhallinta-algoritmeja käytettäessä. Toisaalta samat algoritmit voivat reagoida myös liian nopeasti, jos kiertoviive on pitkä, koska monet algoritmit perustuvat oletettuun maksimikiertoviiveeseen (yleensä 100 millisekunttia). Tämä väitöstyö valottaa kuinka jononhallinta-algoritmin on haasteellista selvittää todellinen kuormataso tutkimalla reitittimellä olevaa jonoa. Kyse on eräänlaisesta "horisontista", joka estää näkemästä kuormaa aiheuttavia tietoliikennepaketteja muilta verkkopolun osilta. Myös pidempikestoinen kuormamittaus on haasteellista, koska reitittimellä ei yleensä ole tietoa kuinka pitkää ajanjaksoa tulisi käyttää mittauksessa. Lisäksi hitaan aloituksen aikana nopeasti muuttuva kuormataso johtaa kuormamittaustulosten vanhenemiseen ennenaikaisesti. Jotta ruuhkasignaali voitaisiin lähettää ajoissa, täytyy jononhallinta-algoritmin huomioida kaikki kolme yllämainittua haastetta. Tämän väitöstyön osana suunniteltiin Predict-niminen jononhallinta-algoritmi, joka osaa havaita hitaan aloituksen ja reagoi siihen oikeaan aikaan estäen tehokkaasti hitaasta aloituksesta johtuvan ylikuormituksen ja siitä johtuvat suuret viivepiikit. Näin ollen Predict välttää muille algoritmeille ongelmalliset reagointinopeuden sudenkuopat. Lisäksi työssä selvitettiin kuinka uusien yhteyksien avaamista tulisi hallita, jotta samanaikaisesti mahdollisesti käynnissä olevalle interaktiiviselle tiedonsiirrolle ei aiheuteta ongelmia.
Subject: Computer Science
Rights: This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.


Files in this item

Total number of downloads: Loading...

Files Size Format View
Congesti.pdf 560.0Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record