TKK | Tietoverkkolaboratorio | Opetus

Luento: ruuhka

S-38.188 Tietoliikenneverkot Luento 9: Liikenteenhallinta
Historiaa Internet reitittimien ruuhkanhallinta sai alkunsa Ford yhtymän sisäisen verkon ongelmista. Nämä ongelmat ilmenivät, koska silloinen ARPANET perustui identtisiin linkkeihin, joita hallittiin erillisellä vuonohjauksella. Näin mitään ruuhkatilanteita ei ollut päässyt syntymään, ainakaan siinä määrin, että niihin olisi reagoitu. Fordin verkko vastaavasti oli heterogeeninen, yhdistäen useita tuotantolaitoksia eri puolilla USAta sekä sateliitin kautta laitoksen Englannissa. Heterogeenisuus syntyi siitä, että laitoksien sisällä käytettiin ethernet verkkoa ja laitoksien välillä vuokrajohtoja, joilla liikennöintinopeus oli alhaisimmillaan 1,2kbit/s.
Historiaa Mitä ongelmia havaittiin ? Ensimmäiset ongelmat liittyivät TCP:n sisäiseen vuonhallintaan. Pienet paketit, joita syntyy esimerkiksi merkkipohjaisessa tiedonsiirrossa, 40 tavua otsikkoa ja yksi tavu hyötykuormaa, johti verkkojen ylikuormittumiseen turhalla informaatiolla. Toinen ongelmatiikka syntyi, kun verkkojen käyttö kasvoi ja aiheutti mahdollisuuden yhteyden äkillisiin viiveiden kasvuihin; mikäli yhteyden kiertoaikaviive kasvaa nopeammin kuin lähettävän TCP-prosessin mittaama kiertoaikaviive, syntyy uudelleen lähetyksiä, jotka vastaavasti kuormittavat lisää reitittimiä aiheuttaen yhä pitemmän kiertoaikaviiveen.
Historiaa Ongelmiin pyrittiin ratkaisemaan TCP-prosessin modifioinnilla sekä ns 'Source Quench' toiminnolla, jossa ruuhkautunut reititin pyytää edellistä reititintä pakottamaan lähdettä pienentämään nopeutta. Tämä informointi tapahtuu vastavuohon aina lähteeseen saakka, joka riippuen riippuen toteutuksesta pienentää nopeuttaan tai ei. Kuten saattaa arvata lähderiippuvat ratkaisut reitittimen ruuhkanhallintaan ovat aina ehdollisia; mikäli lähde ei noudata reitittimen ohjeita mitään ei tapahdu. Näin ollen kehitys johti reitittimien sisäisiin ruuhkanhallintamekanismeihin.
Mitä ja Miksi liikenteenhallintaa Reitittimet jakavat yhteisiä resursseja Verkon siirtokapasiteettia Reitittimen puskurointikapasiteettia Reitittimen prosessointikapasiteettia Resurssit ovat rajallisia ja yhdenkin loppuminen johtaa toiminnan rajoittumiseen
Contend vs Congest Contend, viivästyminen Kun verkon siirtokapasiteetti hetkellisesti ylittyy ja paketit asetellaan jonoon, josta ne palvellaan ajallaan. Congest, ruuhkautuminen Kun verkon siirtokapasiteetti ylitetään tarpeeksi pitkän aikaa, vuotaa puskurit yli ja paketteja katoaa
Resurssien jako ja ruuhkanhallinta Kolikon kaksi puolta Resurssienjako: Yhteydelle määritellään ennaltakäsin rajoja Ruuhkanhallinta: Yhteydelle määritellään rajoja ruuhkautumisen tapahduttua Ääripäissä Ei ruuhkanhallintaa --> resurssit on jaettu ennaltakäsin (vrt puhelinverkko) Ei resurssienjakoa --> yhteydet kilpailevat samasta kaistasta ja ruuhkatlanteissa 'algoritmi' ratkaisee resurssien jaon
Liikenteenhallinta Liikenteenhallinta on laajempi kokonaisuus kuin pelkkä resurssienjako ja ruuhkanhallinta mutta sisältää käsitteenä molemmat osa-alueet. Liikenteenhallinta on monisäikeistä (hajautettua): verkossa on useita laitteita laitteiden toiminnot on jaettu useille protokollakerroksille usiden laitteiden sisäiset resurssit on jaettu
Liikenteen hallinnan aikatasoja
Ruuhkanhallinta vs vuonhallinta Ruuhkanhallinta pyrkii estämään lähdettä ylittämästä verkon resursseja Vuonhallinta pyrkii estämään lähdettä ylittämästä vastaanottajan resursseja
Vuo (eri kuin vuonhallinta) Yhteydellinen kytkentä, jokainen paketti kulkee ennalta määrättyä reittiä Yhteydetön kytkentä, jokainen paketti reititetään omana kokonaisuutena Käytännössä paketit kulkevat samoja reittejä pitkin ja muodostavat siten VUON. Vuo ei ole kongreettinen reunaehto vaan abstractio, joka helpottaa liikenteenhallintaa
Vuon tila Ei tilaa: puhdas yhteydetön kytkentä Pehmeä tila: reititin ylläpitää tietoa kyseisen yhteyden kytkennästä välimuistissa jonkinlaista tietoa yhteyden puskurointiviiveestä jonkinlaista tietoa yhteyden resurssitarpeesta Kova tila: reititin ylläpitää tarkkaa tietoa yhteyden kytkennästä yhteyden resurssitarpeesta yhteyden olemassaolosta
Palvelumalli Best Effort Ei takuuta kaistasta Ei takuuta viiveestä Ei takuuta hukasta Taattu palvelu Takuu kaistan tietylle arvolle Rajoitettu viive Taattu hukka tietyllä aikavälillä Harmaa alue
Lähteen käyttäytyminen Erilaisilla sovelluksilla on ominaisuuksia, jotka määrittelevät millaista palvelua niiden tulisi verkosta saada
Palvelun hyödyllisyys Palvelulla täytyy olla tiettyjä reunaehtoja mikäli nykyisiä sovelluksia halutaa onnestuneesti käyttää.
Lähestymistapoja liikenteenhallintaan Reititin - lähde keskeinen Varaus - vaste pohjainen Ikkuna - nopeus pohjainen
Reititin - lähde keskeinen Reititin keskeiset menetelmät perustuvat reitittimen tekemään päätökseen, mitkä paketit saavaat palvelua ja mitkä eivät Lähde keskeisissä menetelmissä lähteet sopeutuvat verkon tilaan lähettämällä 'sopivan määrän' informaatiota verkkoon Nämä kaksi menetelmää eivät ole toisiaan poissulkevia Vaikka reititin suorittaa pakettien karsintaa tarvitaan lähdepohjaista hallintaa mukautumaan verkon tilaan Vaikka lähde kontrolloisikin liikennettä tarvitaan reitittimiin mekanismeja turvaamaan niiden toimintaa ruuhkatilanteissa
Varaus - vaste pohjainen Varauspohjaisissa järjestelmissä lähde pyytää verkolta tiettyä määrää resursseja yhteyden ajaksi. Jokainen reititin täyttää tämän pyynnön tai hylkää yhteyden. Vastepohjaisissa järjestelmissä lähteet aloittavat lähettämisen heti ja säätävät nopeuttaa saamansa vasteen perusteella. Ekspilisiittisesti; reititin informoi lähdettä Implisiittisesti; lähde havainnoi verkon tilaa uudelleen lähetyspyyntöjen kautta HUOM !!! Varauspohjainen toiminta edellyttää reititin keskeistä toimintaa
Ikkuna - nopeus pohjainen Lähteelle kerrotaan kuinka paljon informaatiota lähde saa lähettää Tietyssä aikaikkunassa (purskeinen) Millä nopeudella (tasainen) Nopeuspohjainen lähestymistapa soveltuu varauspohjaisiin järjestelmiin
Internet Best effort verkko Vastepohjainen toiminta (ei varausta) Lähdepohjainen toimintatapa Käyttää ikkunapohjaista lähteenhallintaa Tulevaisuudessa taattuja palveluita Varauspohjaisia palveluita Vaatii paljon reitittimiltä Luonnostaan nopeuspohjainen lähteenhallinta
Liikenteenhallinnan vertailumenetelmiä Liikenteenhallinnan menetelmiä vertaillaan usein niiden suhteessa Verkon resurssien hyödyntämiseen Lähteiden reiluun käsittelyyn
Resurssiteho Resurssiteho optimoi kahta keskeistä parametria läpäisyä viivettä Optimoinnin tavoite on saada mahdollisimman suuri läpäisy mahdollisimman pienellä viiveellä
Reiluus Reiluus on määritelmä sille, miten oikeudenmukaisesti eri yhteyksiä kohdellaan ruuhkautuvassa reitittimessä.
Sosialistinen näkökanta Kaikkia palvellaan tasapuolisest Kaikki resurssit ovat kaikkien vapaasti hyödynntettävissä Kaikilta odotetaan kunnioitusta toisia kohtaan.
Kapitalistinen näkökanta Yhteyksiä käsitellään perustuen maksukykyyn, eli sen kulutat mistä maksat. Sosiokapitalistisessa järjestelmässä uudet yhteydet pääsevät mukaan ja vanhat yhteydet saatavat kärsiä siitä ('vakio palveluaika') Puhtaassa kapitalistisessa järjestelmässä olemassa olevien yhteyksien tilaan ei puututa mitenkään
TCP-ruuhkanhallinta Tehtävä on määrittää kuinka paljon verkossa on kapasiteettia vapaana Toimii itseohjautuvasti Kellotus vastesanomilla (ACK) Kello on kiertoaikaviive (RTT), joka kertoo ajan, joka kuluu paketin lähettämisestä sen vastaanottamiseen.
TCP-ruuhkanhallinta Ruuhkaikkuna vastaa vuonhallinnan ilmoitettuaikkunaa Ikkuna on minimiresurssi rajoitettu Maksimissaan: Käytännössä: KYSYMYS: Kuinka ruuhkaikkuna tiedetään ? Lähde suorittaa itseohjautuvaa verkon tilan seurantaa perustuen vastesanomiin (ACK) ja kadonneisiin paketteihin
TCP-ruuhkanhallinta Lineaarinen kasvu Jokainen onnistuneesti lähetetty ruuhkaikkunallinen kasvattaa ruuhkaikkunaa yhdellä paketilla: Käytännössä jokainen vastesanoma kasvattaa ikkunaa omalta osaltaan:
TCP-ruuhkanhallinta Perusversion käyttäytyminen Pitkät hitaat kasvamiset Nopeat pudotukset
TCP-ruuhkanhallinta Lähteen nopeuden kasvattaminen on alussa liian hidasta Tarvitaan tehokkaampi mekanismi ensi alkuun Ruuhkaikkuna tuplataan jokaisella vastesanomalla SLOW START on mekanismi, jossa Ruuhkaikkunaa kasvatetaan 1:stä paketista tuplaamalla jokaisen paketin kohdalla ikkunan arvo Se estää laitetta lähettämästä täyttä ikkunaa paketteja niissä tapauksissa, joissa se vastaanottaa useita ACK-paketteja
TCP-ruuhkanhallinta Alussa lähteen ruuhkaikkunan loputon tuplaaminen johtaa pakettien suureen katoamiseen mittaa verkon kapasiteetin tulevan toiminnan varalle Ajastimen laukeamisen jälkeen tuplaamista käytetään ainoastaan siihen asti, että saavutetaan edellinen validi ruuhkaikkunan koko tämän jälkeen jatketaan normaalia toimintaa (lineaarinen kasvu)
TCP-Ruuhkanhallinta Slow Start käyttäytyminen Nopeat nopeuden kasvattamiset Pitkät kuolleet hetket
TCP-Ruuhkanhallinta Miten poistaa pitkät hiljaiset hetket yksittäisen paketin kaoamisen jälkeen ? Fast Recovery and Fast Retransmit on menetelmä siihen OLETUS: Verkossa katoaa useimmiten vain yksi paketti !!!
TCP-Ruuhkanhallinta Jokainen yksittäinen kadonnut tai viivästynyt paketti vahvistetaan edellisellä oikealla ACK sanomalla. Kolme peräkkäistä samaa ACK sanomaa laukaisee uudelleen lähetyksen. Mikäli uudelleen lähetys ei tuo kuittausta jokaiseen pakettiin odotetaan ajastimen laukeamista.
TCP-Ruuhkanhallinta Nopea vaste useimmissa tapauksissa
Reitittimet Ruuhkatila reitittimessä syntyy, kun resurssien tarve reitittimessä ylittää tarjolla olevan resurssien määrän. Reititin suojautuu resurssien vajetta vastaan erilaisilla jonotusalgoritmeilla, joilla jaetaan verkon kapasiteettia jaetaan puskurimuistin määrää ruuhkan aikana poistetaan oikeat paketit
Reitittimet Ruuhkanhallinnan menetelmät voidaan jakaa kahteen luokkaan: ruuhkatilaa ennustaviin ruuhkatilaan reagoiviin
Reitittimet Ennustavat menetelmät pyrkivät pitämään verkon/reitittimen toimintapisteen resurssiteho maksimissa Reagoivat menetelmät pyrkivät palauttamaan toimintapisteen optimiin, mikäli se sen ylittää.
Reitittimet Toimiakseen menetelmät tarvitsevat erilaisia suoritusarvoja: Jonon keskimääräinen pituus Kiertoaikaviive Mikäli suoritusarvoja mitataan ja ennustetaan perustuen liian tiheään tai harvaan näytteenottoon ilmenee tuloksissa väistämättä virheitä, jotka johtuvat internet-liikenteen dynamiikasta.
Reitittimet Kiertoaikaviive voidaan määrittää jonon regeneroitumisprosessista. Periaate on hyödyntää dominoivan liikenteen dynamiikkaa. Dominoiva kiertoaikaviive voidaan määrittää tarkkailemalla jonon täyttymis- ja tyhjentymisprosessia. Mikäli prosessi on deterministinen, voidaan syklin pituudesta määrittää kiertoaikaviive.
Reitittimet Puskurinhallintaan on erilaisia mekanismeja Tail Drop (häntäkarsinta) Random Drop (Satunnaiskarsinta) Random Early Detection (Ennakoiva satunnaiskarsinta) Weighted Fair Queueing (Reilujonotus)
Tail Drop Tail Drop eli häntäkarsinta on yksinkertaisin puskurinhallintamekanismi. Siinä rajallinen puskuri, jota palvellaan FIFO-periaatteella, ylivuotaa pitäen siten liikenteen kurissa.
Tail Dropin ongelmia Pienellä puskurilla: TCP:llä hankaluuksia päästä 'slow-startista' Heikko vaste verkon transienteille Suurella puskurilla: Reaaliaikaiselle liikenteelle kohtuuttoman suuri viive Verkossa ei etene hetken päästä ollenkaan liikennettä, mikäli linkin nopeus on pieni.
Tail Dropin ongelmia Globaali synkronisaatio seuraa siitä, että jonon täyttyessä kaikki yhteydet kokevat pakettihukkaa miltei yhtäaikaisesti ja joutuvat siten slow startiin. Selkeä painotus tasaiselle liikenteelle, koska jonon ollessa kasvussa todennäköisyys, että purskeiselle yhteydelle riittää puskurikapasiteettia pienenee.
Random Drop Perustuu olettamukseen, että paketti, joka valitaan satunnaisesti kuuluu lähteelle N todennäköisyydellä, joka on suoraan verrannollinen lähteen keskinopeuteen. Paketti valitaan tällä kertaa koko jonosta tasajakaumaan perustuvulla satunnaisprosessilla.
Random Drop Voidaan käyttää sekä ruuhkaa ennakoivana että ruuhkaan reagoivana menetelmänä. Reagointi perustuu paketin karsintaan jokaisen uuden paketin saapuessa Ennakoinnissa jokainen tuleva paketti aiheuttaa karsintatodennäköisyyden laskemisen ja sen perusteella toimimisen.
Random Early Detection REDissä hyödynnetään puskurin keskimääräistä tilaa karsinta todennäköisyyden laskemiseen. Keskimääräinen puskurin täyttöaste lasketaan keskiarvo-suodattimella
REDin edut Ei aiheuta globaalia synkronoitumista Toiminta perustuu eston havainnointiin jo ennen kuin sitä edes esiintyy. Takaa puskuriin kapasiteettia purkeiden varalle Purskeen todennäköisyys tulla karsituksi ei kasva lineaarisesti; sillä purske ei aikaansaa keskiarvon välitöntä nousua (EWMA).
Fair Queuing Menetelmä, jossa ryhmälle yhteyksiä muodostetaan rinnakkaiset jonot Nämä rinnakkaiset jonot ovat tietyssä mielessä autonomisia, eli niillä ei ole suoraa interaktiota keskenään
Fair Queuing metodit Palvelua jaetaan kiertävällä periaattella perustuen: Tasapuolisesti Paketti kerrallaan Bitti kerrallaan Painotetusti Paketti kerrallaan Bitti kerrallaan
Entä jos ATM ATM:ssä toimitaan 48-tavun hyötykuorman omaavassa pakettiverkossa. IP-paketit, joudutaan paloittelemaan useaan ATM-soluun siten, että yksittäinen paketti voi jakaantua jopa 200:n soluun. Perinteiset protokollat eivät kykene paketin osittaisiin uudelleen lähteyksiin ja siksi yhden solun hukkaaminen johtaakin koko protokollakehyksen (10-200 -solua) poistamiseen.
Kuinka parantaa hyötysuhdetta Valikoivia liikenteen karsintamenetelmiä ovat: EPD (Early Packet Discard) PPD (Partial Packet Discard) EPD on estoa ennakoiva menetelmä. Se hyödyntää tietoa jonon pituudesta. Mikäli jonon pituus ylittää aseteltavan rajan hylätään saapuva AAL5 -kehys. PPD on vastaavasti reaktiivinen toimintamalli, jossa täyttynyt jono on aiheuttanut ylivuodon puskurissa ja näin ollen aikaansaanut AAL5 -kehyksen vikaantumisen. PPD poistaa jäljelle jääneet solut jonosta ja näin vapauttaa tilaa tuleville soluille.
Miten nämä vaikuttavat verkkoon EPD ja PPD johtavat helposti globaaliin synkronisaatioon, mikä on verkon toiminnan kannalta epäedullinen tilanne. Mikä ratkaisuksi FBA (Fair Buffer Allocation) parantaa EPD:tä lisäämällä pehmeän käyttäytymisen raja-alueella C-RED (Cell Random Early Detection) Yhdistää REDin ja koko kehyksen poiston soluverkkoon
Lisälukemista Opetusmonisteissa tulee kaksi artikkelia, jotka käsittelee ruuhkanhallintaa ja ATM:n tuomia ongelmia IETF:n työsuositus 'Recommendation on Queue Management and Congestion Avoidance in the Internet' Omar Elloumi & Hossan Afifi 'RED Algorithm in ATM Networks'
Lisäpähkinä Jotta mielenne pysyisi virkeänä ja saisitte tutkiskella asiaa tarkemmin vuorossa on tehtävät Kirjasta kappaleen 8 tehtävät 5 ja 6 Tehtävillä voi korvata tentin huonoimman tehtävän pisteet.

Tietoverkkolaboratorio on nyt osa Tietoliikenne- ja tietoverkkotekniikan laitosta. Tällä sivulla oleva tieto voi olla vanhentunutta.

Kurssien ajantasainen tieto on MyCourses-palvelussa.

Tämän sivun sisällöstä vastaavat ja Webmaster. Sivua on viimeksi päivitetty 21.11.1997 12:03. URI: http://www.netlab.tkk.fi/opetus/s38188/1997/luento09/index.shtml [ TKK > Sähkö- ja tietoliikennetekniikan osasto > Tietoverkkolaboratorio > Opetus ]

Kysy

Anna palautetta!