Kokeen 6.6.2003 arvostelusta:
1. Opiskelija surffailee Internetissä ja klikkaa URL-linkkiä. Tuloksena opiskelijan koneen näytölle tulee näkyviin osoitetta vastaava sivu jostakin kaukana olevasta koneesta.
Mitä sovelluskerroksella tapahtuu? Mitä sovelluskerroksen toimintoja ja protokollia käytetään? Mitä sanomia sovelluskerroksella lähetetään? (8 p)
Tässä piti selostaa sekä IP-soitteen selvittämistä (DNS-protokolla) (4 p) että selaimen ja palvelimen välistä viestintää (HTTP-protokolla) klikatun sivun siirtämiseksi (4 p).
* DNS-protokollan yhteydessä:
miksi IP-osoitetta tarvitaan ja kuinka se selvitetään URL:sta (välimuisti, rekursiivinen kysely, iteratiivinen kysely)
DNS-sanomat: kysymys ja vastaussanomia
* GET-sanoma ja sen vastaukseksi pyydetty sivu
tarvittaessa lisäsivuja (esim. kuvia) pyydetään erikseen.
Ektrapisteitä on voinut saada välimuistin käytöstä, pistokeohjelmoinnista, tai siitä, että on selvittänyt DNS:n tai HTTP:n toimintaa tavallista perusteellisemmin.
b) Mitä tapahtuu kuljetuskerroksella? Mitä kuljetuskerroksen sanomia eli segmenttejä tarvitaan ja missä järjestyksessä segmentit lähetetään? (12 p)
* UDP:n toiminta lyhyesti (Kurose-Ross ss.196- 201) (2 p)
DNS käyttää, segmentti lähetetään heti, yksinkertainen virhetarkistus, ei
uudelleenlähetyksiä yms hienouksia, epäluotettava, mutta kevyt ja nopea
* TCP:n toiminta (Kurose-Ross ss. 228-253) (10 p)
yhteyden muodostus kolminkertaisella kättelyllä (2 p)
data (= sovelluskerroksen sanomat) lähetetään segmentteinä, joiden lähetyksessä pyritään luotettavuuteen ( maks 6-8 p)
segmenttien lähetyksessä virhetarkistus + uudelleenlähetys, jos kuittaus ei tule
ajoissa, (2 p)
vuonvalvonta, jossa lähettäjä ilmoittaa paljonko pystyy ottamaan vastaan (2 p)
ruuhkanvalvonta hitaalla aloituksella (etenkin WWW-sivun siirrossa) (2 p)
kuinka HTTP-sanomat siirretään TCP-segmenteissä (2 p)
yhteyden purku kolminkertaisella kättelyllä (2 p)
Maksimipisteet TCP:n toiminnasta on siis voinut saada vähän eri painotuksilla, kunhan on
selvittänyt TCP:n toiminnan tärkeitä piirteitä.
2 Paketit reititetään verkossa lähettäjän koneelta vastaanottajan koneelle.
Miten tämä tapahtuu? Mitä tietoja reitityksessä tarvitaan? (5 p)
Kurose-Ross: 4.2 ss. 301- 304
a) Tässä haluttiin perustietoja reitityksestä:
reititin / oletusreititin
reititystaulu, jossa on tiedot siitä mihin ulostuloon (= mille seuraavalle reitittimelle)
kunkin vastaanottajan paketti tulee ohjata
reititysalgoritmi päättää/määrää reitin lähettäjän reitittimeltä vastaanottajan
reitittimelle eli laskee 'parhaan tai riittävän hyvän' reitin (usein kustannuksiltaan pienin)
globaali algoritmi tuntee koko verkon topologian ja kaikkien linkkien kustannukset ja
osaa laskea näistä parhaat reitit koko verkon kaikkien solmujen välille
itse laskenta voidaan suorittaa joko hajautetusti tai keskitetysti
hajautettu algoritmi: millään solmulla ei ole kokonaiskuvaa koko verkosta, iteratiivinen laskenta: aluksi tiedetään vain kustannukset naapureihin, joita saadaan vähitellen lisätietoa koko verkosta
staattinen vai dynaaminen algoritmi (tietyin aikavälein tai kun tapahtuu muutos kustannuksissa. Dynaaminen voi aiheuttaa oskillointia.
Kuormasta riippuva vai riippumaton: vaikuttaako siihen linkin ruuhkaisuus
reititysprotokolla, jolla reitittimet vaihtavat keskenään tietoja eri reittiensä kustannuksista
paketeissa vastaanottajan osoite (IP-osoite)
Virtuaalipiiri: reititys vain ensimmäiselle paketille, datagrammi: reititys jokaiselle paketille
reititystoiminta:
Lähettäjän koneen oletusreititin huolehtii paketista, joka menossa muualle kuin lähettäjän omaan verkkoon. Reititin tutkii paketin vastaanottajan osoitteen.
Reitittimessä reititystaulu, joka kertoo, mihin ulostuloon eli mille seuraavalle reitittimelle (tai sitten jo vastaanottajalle) eri vastaanottajille (eri verkkoihin) matkalla olevat paketit ohjataan.
Reititystaulun tiedot saatu reititysprotokollan avulla vaihtaen tietoja muiden reitittimien kanssa . Käytetty reititysalgoritmi määrää, kuinka pakettien reitit lasketaan ja samalla määrää, mitä tietoja reittien laskemisessa tarvitaan (tulvitus ja 'hot potato' eivät tarvitse mitään tietoja verkosta, DV käyttää naapureiden välittämiä tietoja, LS vaatii tarkat tiedot verkon topologiasta ja kaikkien linkkien kustannukset).
paketissa vastaanottajan osoite sellaisessa muodossa, että reititin sen ymmärtää
reititystaulun tiedot: vastaanottaja tai vastaanottajan verkko, mille reitittimille (mihin ulosmenoon) paketti ohjataan, erilaisia kustannuksia reiteille
jotta reititystaulun tiedot voidaan laskea, niin tarvitaan tietoja eri linkkien kustannuksista
Arvostelusta:
Lähinnä jokaisesta reititystä oikein kuvaavasta asiasta on saanut yhden pisteen. Maksimi pistemäärään riitti siis viisi oikeaa reitityksen piirrettä.
b) Internetissä on yleisesti käytössä kaksi erilaista reititysprotokollaa: linkkitilareititys (link state routing) ja etäisyysvektorireititys (distance vector routing)? Mitä yhteisiä piirteitä näillä reititysprotokollilla on? Miten protokollat eroavat toisistaan? (15 p)
b) LS ja DV molemmat dynaamisia algoritmeja, jotka keräävät tietoa omien linkkiensä kustannuksista tietyin väliajoin tai kun havaitaan muutoksia linkkikustannuksissa
omat linkkikustannukset arvioidaan tai mitataan naapureille lähetetyistä sanomista
tietoja vaihdetaan muiden reitittimien kanssa
tietojen perusteella saadaan reititystaulun tiedot
LS: globaali
tarvitsee tietää koko verkon topologia ja kaikkien linkkien kustannukset
näiden perusteella pystytään laskemaan esim. Dijkstran algoritmilla parhaat reitit kaikkien lähettäjä-vastaanottaja parien välillä; isossa verkossa algoritmi vaatii paljon laskentatehoa.
laskenta voidaan suorittaa joko keskitetysti jolloin yksi solmu laskee parhaat reitit ja lähettää tiedot kaikille reitittimille, tai hajautetusti, jolloin kaikki tai useat solmut laskevat reitit; jos kaikki laskevat, niin tuloksena erittäin paljon laskentaa, mutta toisaalta lisää robustisuutta.
Reitittimen omasta ympäristöstään keräämät tiedot on lähetettävä kaikille muille reitittimille, samoin tieto muutoksesta on lähetettävä kaikille => paljon sanomia
Koska on tärkeää, että kaikilta on saatu oikeat tiedot, niin käytetään kuittauksia ja autentikointia
DV: hajautettu
tietää aluksi vain omien linkkiensä kustannukset
vaihtamalla tietoa naapureittensa kanssa saa näiltä tietoa muusta verkosta
mikään reititin ei tunne koko verkon topologiaa, kukin tietää vain millä kustannuksella muut reitittimet tavoitetaan sen eri naapureitten kautta
reititystaulun tietojen laskeminen melko yksinkertaista
tiedot muutoksista leviävät muille reitittimille melko hitaasti, hyvät tiedot eli tieto paremmasta yhteydestä etenee joka kierroksella yhden askeleen naapurilta naapurille; huonot tiedot etenevät vielä hitaammin 'count-to-infinity -ongelma
tästä voi aiheutua reitityssilmukoita
ei toimi hyvin kovin isossa verkossa
vähemmän sanomaliikennettä: sanomia vaihdetaan vain naapureiden kanssa ja naapurille ilmoitetaan vain, jos syntyy halvempi kustannus
robustisuus: vikaantunut tai muuten väärin toimiva reititin:
LS: reititin voi ilmoittaa väärin jonkin oman linkkinsä kustannuksen tai yrittämällä väärentää tai
hävittää sen kautta kulkevia muiden tilatietoja.
Kuitenkin koska jokainen laskee omat taulunsa, niin yhden väärin toimivan vaikutus on kohtalaisen pientä
DV:voi ilmoittaa väärät tiedot kaikille naapureille ('minun kauttani kustannukset 0 kaikkialle'),
jotka taas välittävät virheellistä tietoa eteenpäin Tämä voi vaikka kaataa koko verkon!
Erot voisivat olla esim. seuraavat: (Kurose-Ross: 4.2 ss. 301- 304)
tietämys verkon topologiasta ja linkkikustannuksista
LS: täydellinen kuva verkon topologiasta jokaisella reitittimellä
DV: ei täydellistä kuvaa, tietää vain mitä kustannukset ovat eri naapureitten kautta ja mille naapurille tulee lähettää
sanomien määrä
LS: paljon sanomia, tietyin väliajoin kaikille, myös jokaisesta muutoksesta linkkikustannuksissa ilmoitettava kaikille verkon reitittimille
DV: sanomia vähän; ilmoitettava vain naapureille ja muutoksista vain jos muutos linkkikustannuksissa muuttaa reititystä
laskennan määrä
LS: reittien laskeminen vaatii paljon laskentaa, mitä isompi verkko, sitä enemmän laskentaa algoritmi vaatii
DV: reittien laskeminen on melko yksinkertaista
Miten nopeasti tieto muutoksista saavuttaa muut reitittimet?
LS: lähes heti, koska muutoksen havainnut reititin lähettää tästä tiedon kaikille muille reitittimille
DV: melko hitaasti; parannukset etenevät askel kerrallaan (joka iterointikierroksella tieto siirtyy seuraavalle reitittimelle); huononnukset erittäin hitaasti ('count-to-infinity-ongelma, jota yritetty ratkaista niin, että sille naapurille, jonka kautta reitti kulkee, ilmoitetaan reitin kustannukseksi ääretön (poisoned reverse).
Miten pahasti yhden reitittimen vikaantuminen tai virheellinen toiminta vaikuttaa koko verkon reititykseen (robustisuus)?
LS: aika vähän. Vaikka reititin voi ilmoittaa väärät tiedot omien linkkiensä kustannuksista kaikille ja muuttaa tai hävittää sen kautta kulkevia muiden lähettämiä tilatietoja, niin vaikutus on melko pientä ja paikallista, koska jokainen reititin laskee omat reititystietonsa.
DV: Voi olla hyvinkin dramaattinen. Reititin voi ilmoittaa väärät tiedot kaikille naapureille ('minun kauttani kustannukset 0 kaikkialle'), jotka taas välittävät virheellistä tietoa eteenpäin Tämä voi vaikka kaataa koko verkon!
Arvostelusta:
Joka kohdasta 3 pistettä: yksi piste, jos kohta yleensä on mainittu ja piste kummankin reititystavan toiminnasta tältä osin.
Jos jokin kohta on selostettu erityisen hyvin, siitä on voinut saada lisäpisteen.
Maksimipistemäärä kuitenkin 15
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ää.