581333-1 Tietoliikenne I

Erilliskuulustelu 4.6.2004

Lähettäjän verkkoon lähettämät paketit voivat tulla perille virheellisinä tai kadota kokonaan.>
a) Mitkä tekijät aiheuttavat virheellisiä paketteja tai pakettien katoamisia? (4p)
b) Miten vastaanottaja havaitsee paketin virheelliseksi tai huomaa paketin puuttuvan? Mitä eri keinoja ja tapoja on käytettävissä? Miten tällaisesta virhetilanteesta toivutaan? (8 p)
c) Miten Internet-protokollat IP, UDP ja TCP suhtautuvat virheisiin ja virhetilanteesta toipumiseen? (8 p)

a) -kohdassa haluttiin seuraavia asioita:

• bittivirheet erityisesti langattomilla yhteyksillä muuttavat paketin bittejä ja ryöppyinä voivat hävittää koko paketin; reititin voi tuhota sopivasti vikaantuneet paketit

• ruuhka verkossa aiheuttaa reitittimien puskureiden ylivuotoa ja pakettien katoamisia

• huono reititys voi kierrättää pakettia liian pitkään verkossa, jolloin se hävitetään elinajan loppumisen takia

• vikaantuneet laitteet voivat hävittää ja vääristää paketteja

Arvostelussa: 1 piste joka kohdasta.

b)-kohdan vastauksessa haluttiin seuraavia asioita:

Virheen tai puuttuvan paketin havaitseminen

• Vastaanottaja voi havaita virheellisen paketin pakettiin liitettyjen tarkistusbittien avulla. (1 p)

• Käytössä on useita erilaisia menetelmiä, useimmilla vain havaitaan paketin bittien muuttuneen (2 p eli noin ½ p per menetelmä; jos on kirjoittanut menetelmästä tarkemmin, niin on voinut saada ½ pistettä lisää)

• pariteettibitti / pariteettibitit

• tarkistussumma 'checksum'

• CRC-tarkistus

• Hamming-tarkistusbitit, joiden avulla voidaan myös korjata yhden bitin virhe

• Välistä puuttuva paketti havaitaan pakettien numeroinnilla (1 p) (Vastaanottaja ei voi havaita viimeisen paketin puuttumista)

Paketin virheestä tai puuttumisesta toipuminen

• Yleensä virheestä toivutaan lähettämällä puuttuva tai virheellinen paketti uudestaan. Jos lähettäjä ei saa kuittausta (ack) lähettämästään paketista, niin paketin ajastin laukeaa ja paketti lähetetään uudestaan. Joskus käytetään myös NAK-kuittausta ilmoittamaan virheellisestä tai puuttuvasta paketista. (2 p)

• Voidaan myös käyttää virheen korjaavaa tarkistusta, jonka avulla vastaanottaja pystyy itse korjaamaan paketin. Joissakin tapauksissa virheestä toipumista kannata edes yrittää. (2 p)

Arvostelussa: Miten havaitaan virheellinen tai puuttuva paketti 4 p; miten toivutaan virheestä 4 p.

c)-kohdassa kysyttiin Internet-protokollien suhtautumisesta virheisiin ja virheestä toipumiseen.

IP (2 p)

• otsakkeen kattava tarkistussumma, joka lasketaan joka hypyllä

• virheestä ei yritetä toipua; yleensä virheellinen datagrammi vain tuhotaan

UDP (2 p)

• tarkistussumman (checksum) käyttö vapaaehtoista, tarkistussumma lasketaan koko UDP-segmentistä + pseudo-otsakkeesta.

• Ei kuittauksia eikä virheestä toipumista.

• Virheellinen paketti voidaan hävittää tai antaa sovelluskerrokselle varoituksen kera.

• Ei vuon- eikä ruuhkanvalvontaa pakettien 'turhan' häviämisen estämiseksi.

TCP pyrkii virheettömään tiedonsiirtoon: havaitsemaan virheet ja toipumaan niistä sekä vuonvalvonnalla että ruuhkanvalvonnalla huolehtimaan siitä, ettei turhaan hävitetä jo verkkoon lähetettyjä ja pitkälle siirrettyjä paketteja. (4 p)

• Checksum segmentille ja pseudo-otsakkeelle

• virheettömät ja oikeassa järjestyksessä vastaanotetut paketit kuitataan; numeroinnista sovitaan yhteyttä muodostettaessa

• jos kuittaus ei tule ajoissa, paketin ajastin laukeaa ja lähettäjä lähettää paketin uudelleen vastaanottajalle

• vuonvalvonta: vastaanottajan ikkunan koko joka kuittauksessa

• melko monimutkainen ruuhkanvalvonta, jotta paketteja ei tarvitsisi hävittää ruuhkan takia

2. Hidas aloitus (slow start) ja nopea toipuminen (fast recovery)

a) Mihin hidast aaloitusta käytetään? Mitä hyötyä siitä on? Voiko siitä olla haittaa? Jos on, niin missä tilanteissa? (6 p)

b) Käytetään hidasta aloitusta linjalla, jonka kiertoviive (round.trip time) on 100 ms. Linjalla ei ole ruuhkaa ja kuittaukset saapuvat ajoissa. Vastaanottajan ikkunan on 18 kilotavua ja kynnysarvo (threshold) on 30 kilotavua. Esitä kaaviona, kuinka 100 kitotavun tiedoston lähettäminen tapahtuu, kun se lähetetään 2 kilotavun segmentteinä. (8 p)

c) Oletetaan, että tiedoston segmentti 20 katoaa kokonaan ruuhkan takia. Miten lähettämistä jatketaan tämän jälkeen, jos käytössä on nopea toipuminen? (6 p)

a) Haluttiin seuraavia asioita:

• käytetään TCP-protokollassa ruuhkanvalvontaan

• hyöty:

• Internetin kuormitus vaihtelee paljon. Hitaalla aloituksella pystytään hyödyntämään verkon vapaa kapasiteetti tehokkaasti ja välttämään pahoja ruuhkia, jotka aiheuttavat hukkakäyttöä. Sillä löydetään melko nopeasti (eksponentiaalinen kasvatus) kuormitustilanteeseen sopiva kerralla verkkoon lähetettävä määrä. Kynnysarvo varoittaa aikaisemmin koetusta ruuhkasta, jolloin määrää kasvatetaan hitaammin. Ruuhkaa kokeneet yhteydet pudottavat lähetysmääränsä heti lähes nollille, joten pahoja ruuhkia ei pääse syntymään.

• Haittoja:

• tulkitsee virheellisen paketin ruuhkaksi => ongelmia heikkotasoisilla linjoilla kuten langattomat linjat

• suurikapasiteettiset, pitkän viipeen linjat (satelliitilinjat), jolloin linja on pitkään vajaakäytössä

• erittäin nopeat linjat (Gigabittilinjat), joiden kapsiteettia ei pystytä hyödyntämään

• monet sovellukset (ääni, kuva, neuvottelut, pelit) kärsivät

Arvostelusta: kukin pääkohta (käyttö, hyöty, haitat) 2 p

b)

Ei koskaan päästä kynnysarvoon ja lineaariseen kasvattamiseen, koska vastaanottajan ikkuna rajoittaa lähettämisen 9 segmenttiin (=18 kilotavua) kerralla.

Aika läh. määrä kok. määrä

0 1 = 2 kB 2 kB eksponentiaalinen kasvatus

100 2 = 4 kB 6 kB

200 4 = 8 kB 14 kB

300 8 =16 kB 30 kB

400 9 = 18 kB 48 kB ruuhkavalvonta => 32 kB, mutta vastaanottajan ikkuna = 18 kB

500 9 = 18 kB 66 kB

600 9 = 18 kB 84 kB

700 8 = 16 kB 100 kB ei ollut enempää lähetettävää!

Hitaalla aloituksella ruuhkaikkunaa kasvatetaan segmentin maksimikoosta (MSS) 2 kB aloittaen. Lähetettävää määrää aina kaksinkertaistetaan arvoon 16 kB asti. Seuraava arvo olisi 32 kB:tä, mutta vastaanottajan ikkunan koko on 18 kB ja tämä rajoittaa lähetyksen määrän.

Arvostelusta: vastaanottajan ikkunan merkitys 2 p

eksponentiaalinen kasvatus 3 p

selkeä ja ymmärrettävä kaavio 2 p

järkevät luvut ja ajat 1 p

c)

400 9 = 18 kB 48 kB segmentti 20 katoaa tästä lähetyksestä (15, 16,17,18,19 menevät ok)

500 4 = 8 kB 56 kB (20 , 21, 22, 23)

600 5 = 10 kB 66 kB

700 6 = 12 kB 78 kB

800 7 = 14 kB 82 kB

900 8 = 16 kB 98 kB

1000 5 = 10 kB 108 kB (koska 4 segmenttiä jouduttiin lähettämään uudestaan)

Koska käytössä on nopea toipuminen, niin jo kolme toistokuittausta segmentistä 19 (eli kaikkiaan 4 kuittausta ack 20) riittää käynnistämään segmentin 20 uudelleenlähetyksen. Ei siis välttämättä odoteta uudelleenlähetysajastimen laukeamista.

Jos 4. ack 19 -kuittaus tulee ennen ajastimen laukeamista, niin ruuhkaikkunan arvoksi tulee puolet sillä hetkellä käytetystä lähetysmäärästä = 9 DIV 2 = 4 segmenttiä. Myös uudeksi kynnysarvoksi tulee 4 segmenttiä. Lähetysmäärää kasvatetaan tämän jälkeen lineaarisesti eli ensin 4, 5, 6, 7, 8 ja5 segmenttiä. Tähän lähetys loppuukin, jos joudutaan lähettämään kaikki kadonneen jälkeiset segmenti (GBN) eikä muita ongelmia esiinny.

Jos ruuhka on niin paha ettei toistokuittauksia tule, niin joudutaan hitaaseen aloitukseen.

Arvostelusta: nopean toipumisen toiminta 3 p

toistokuittaukset 2 p

uudelleenlähetysajastin 1 p

Tässä ei tarvinnut piirtää kaaviota, sanallinen selostus riitti.

3. Yhteiskäyttöinen siirtokanava jaetaan eri tavoin monen käyttäjän kesken. Esimerkkejä eri tavoista ovat Ethernet-lähiverkossa käytetty CSMA/CD-protokolla ja langattomissa verkoissa käytetty CDMA.

a) Miksi tarvitaan yhteiskäyttöisen kanavan käytön sääntelyä? (3 p)

Yleensä yhteiskäyttöisenä kanavana pidetään eetteriverkkoa ja ilmatietä, mutta myös kanavoitua kaapelia ja johtoa voidaan pitää yhteiskäyttöisenä kanavana.

• Kanavaresurssin hyödyntäminen:

Jos useampi kuin yksi mahdollinen lähettäjä, niin voivat lähettää samaan aikaan ja lähetykset sotkeutuvat eikä mitään järkevää mene perille. Tämä on lähetyskapasiteetin hukkakäyttöä. Jotta näin ei pääsisi käymään, niin on jotenkin sovittava lähetysvuoroista tai lähetystavoista.

(PerusALOHAssa kukin sai lähettää, milloin halusi ja törmäystilanteessa odotettiin satunnainen aika => maksimaalinen kapasiteetin hyötykäyttö 18%) (3p)

• Tasapuolisuus, että kaikki haluavat pääsevät joskus lähettämään ja mahdollisten tärkeiden sanomien suosiminen (prioriteetti). ( tuotti 1 p)

b) Miten CSMA/CD toimii? Simuloi Ethernetin CSMA/CD-väylän toimintaa alkaen

tilanteesta, jossa

- asema A on lähettämässä,

- ja A:n lähetyksen aikana asemat B ja C haluavat ryhtyä lähettämään.

Mitä sitten tapahtuu? Miten B ja C toimivat? Kuinka B ja C saavat lähetettyä omat

kehyksensä? (8 p)

Lähettämään pyrkivä 'kuuntelee linjaa' ja havaitsee, jos kanava on varattu eli joku jo lähettää.

Jos kanava on vapaa, niin lähetetään.

Jos tulee törmäys (myös törmäys huomataan) eli useampi aloittaa lähettämisen samalla kertaa, kaikki törmänneet keskeyttävät lähettämisen ja suorittavat binääristä peruuttamista. Ne yrittävät uudestaan valitsemallaan hetkellä eli kuuntelevat ja jos ei kukaan lähetä, niin lähettävät ja törmäysvaara-ajan sisällä varmistuvat, ettei törmäystä ole tapahtunut.

A on lähettämässä

B haluaa lähettää, mutta huomaa kanavan olevan käytössä (havaitsee jännitettä) ja jää odottamaan

kanavan vapautumista

C haluaa lähettää, mutta huomaa kanavan olevan käytössä, joten jää odottamaan kanavan

vapautumista

.....

A lopettaa lähetyksensä ja kanava vapautuu,

B ja C havaitsevat kanavan vapaaksi ja kumpikin lähettää

B ja C huomaavat törmäyksen tapahtuneen (tavallista suurempi jännite) ja keskeyttävät lähetyksensä.

=> Binäärinen perääntyminen (Binary backoff):

B valitsee satunnaisesti kahdesta odotusajasta:

0 = ei odoteta, vaan aloitetaan lähetys heti, jos kanava on vapaa eli kukaan muu ei ole jo

lähettämässä

1 = odotetaan yksi aikaviipale ja sen jälkeen aloitetaan lähettäminen, jos kanava on vapaa

C toimii samoin

Lähetys onnistuu, jos toinen valitsee vaihtoehdon 0 odotusta ja toinen vaihtoehdon 1 aikaviipaleen odotus. Tällöin heti lähettävä pääsee lähettämään ja toinen halutessaan lähettää havaitsee kanavan jo varatuksi. Olettaen, ettei kukaan muu ( A tai joku D) ole ehtinyt aloittaa omaa lähetystään.

Jos molemmat valitsevat samoin, niin seuraa taas törmäys ja nyt kumpikin valitsee satunnaisesti 2**2 = 4 mahdollisuudesta itselleen sen aikaviipaleen, jolloin lähettää (odotusaika = 0, 1, 2 tai 3 aikaviipaletta) ja lähettää valitsemassaan aikaviipaleessa, jos kanava on silloin vapaa.

Jos törmäily yhä jatkuu, niin vaihtoehtojen määrää kasvatetaan, Törmäys i. kerran => vaihtoehtoja 2 ** i, kun i < tai = 10. Maksimissaan vaihtoehtoja 1024. Tällä yritetään vielä 6 kertaa ja sitten luovutaan ja ilmoitetaan virheestä ylemmälle kerrokselle.

Törmäys voi tapahtua jonkun muun lähettämään pyrkivän kuin pelkästään C:n ja B:n kesken.

Aikaviipale on valittu siten, että törmäys kaukaisimpienkin asemien välillä havaitaan yhdessä aikaviipaleessa.

Arvostelu:

• kuuntelu ja varatuksi havaitseminen => B ja C huomaavat A:n lähettävän (2 p)

• odottelu ja lähetys heti kanavan vapauduttua => B ja C lähettävät ja törmäävät (2 p)

• törmäyksen havaitseminen ja lähetyksen lopettaminen => B ja C havaitsevat törmäyksen ja lopettavat lähettämisen ja varaavat uuden (satunnaisen) lähetysajan käyttäen binääristä peruuttamista (2 p)

• binäärinen peruuttaminen => miten B ja C aina uudelleen törmätessään laajentavat törmäysaluetta ja näin pienentävät törmäystodennäköisyyttä (2 p)

c) Miten CDMA jakaa yhteiskäyttöisen kanavan eri käyttäjille? (5 p)

Kullakin asemalla on oma sirukoodinsa ykkösbittiä ja nollabittejä varten. Sirukoodin pituus on 128 bittiä ja ykkösbitin koodi on nollabitin komplementti.

Kun sirukoodit valitaan niin, että ne ovat kaikki keskenään ortogonaalisia, niin samanaikaiset lähetykset eivät häiritse toisiaan, vaan muodostavat yhteissignaalin, josta vastaanottaja pystyy erottamaan kunkin eri lähettäjän lähetyksen, kun tuntee tämän sirukoodin.

Lisäksi voi selittää tarkemmin vaikka esimerkin avulla, kuinka yhteissignaali syntyy ja kuinka siitä pystytään erottamaan kunkin samanaikaisen lähettäjän lähettämät bitit.

Arvostelu: Pisteitä sai suunnilleen seuraavista asioista

• usea samanaikainen lähetys samaa kanavaa pitkin ja silti vastaanottaja pystyy erottamaan (1 -2 p)

• sirukoodi:

• kullakin asemalla oma siruyhdistelmä ykkösbitille (1 p)

• ja samalla nollabitille (ykkösen komplementti) (½ p)

• sirukoodien valinta eli sirukoodien keskinäinen ortogonaalisuus, tekee erottamisen mahdolliseksi (2 p)

• sirukoodin pituus, yms yksityiskohtia (½ p)

• tarkempi selvitys toiminnasta tai esimerkki (1-2 p)

d) Mitä muita tapoja yhteiskäyttöisen siirtokanavan kapasiteetin hyödyntämiseen voidaan käyttää? (4 p)

d) Muita tapoja ovat TDM, FDM, tilastollinen aikajako, pollaus, erilaiset muut vuoronantomenetelmät (vuoromerkki), erilaiset varausmenetelmät.

Arvostelu: Näissä riitti pelkkä maininta ja muutaman sanan luonnehdinta, joka selvitti, että vastaaja tietää, mistä puhuu. Pisteitä sai yhden pisteen kustakin eri menetelmästä. Täydet 4 pistettä siis kertomalla neljä muuta menetelmää.