Tietoliikenne, kevät 2000

<P>
<B>2.  välikoe 10.4.2000 arvostelusta </B>
<P>
<I>
1.  Esitä,   miten   vuoromerkkiväylä   (token  bus)   ja   
vuoromerkkirengas    (token  ring)   selviytyvät    tilanteesta, 
jossa   vuoromerkin omaava kone menettää yhteyden verkkoon? (4 p)
</I>
<P>
(Sampo Pyysalo)
<BR>
<P>

Vuoromerkkiväylä: Hajautettu kontrolli, kukin asema pitää yllä ajastinta 
joka nollataan joka kerta kun väylällä on liikennettä. Ajastimen lauetessa
asema pyrkii hankkimaan vuoromerkin lähettämällä CLAIM TOKEN -
kehyksen. Kilpailutilanteessa vuoromerkin saaja ratkaistaan kirjan sivulla
291 esitetyllä algoritmilla.
<P>
Vuoromerkkirengas: Keskitetty kontrolli, renkaassa on yksi valvova asema,
kullakin asemalla on valmius toimia valvovana asemana. Vuoromerkin omaavan
koneen menettäessä yhteyden verkkoon kaksi eri tapausta:
<P>
  Yhteyden menettänyt kone ei ollut valvova asema: Valvova asema havaitsee
ajastimella että renkaassa ei kierrä vuoromerkkiä, jolloin se tyhjentää
renkaan ja luo uuden vuoromerkin.
<p>
  Yhteyden menettänyt kone oli valvova asema: Valvova asema lähettää
säännöllisin väliajoin ACTIVE MONITOR PRESENT - kehyksiä. Kullakin
asemalla on ajastin joka laskee aikaa edellisestä tällaisesta
kehyksestä. Tämän ajastimen lauetessa asema päättelee valvovan aseman
kaatuneen ja pyrkii itse valvovaksi asemaksi lähettämällä
CLAIM TOKEN - kehyksen.
<P>
Lisäksi vuoromerkkiväylässä täytyy looginen rengas ja vuoromerkkirenkaassa
fyysinen rengas eheyttää aina jonkin renkaan koneen menettäessä yhteyden
verkkoon.
<pre>
Tehtävän 1 arvostelusta:

Vuoromerkkiväylä (MAX 2p): 
  - Hajautettu kontrolli (kaikki valvovat) 1p 
  - Ajastimien käyttö ja toipuminen 1p
  - (loogisen renkaan eheytys 1/2p)

Vuoromerkkirengas (MAX 2p):
  - Toipuminen valvovan aseman läsnäollessa 1p
  - Toipuminen valvovan aseman kaatumisesta 1p
  - (fyysisen renkaan eheytys 1/2p)

Vakavista epätarkkuuksista ja asiavirheistä tavallisesti -1/2p, ei
pisteitä jos asia selvästi ymmäretty väärin. 
</pre>
<I> 
2.  a) Kaliforniassa sijaitsevan vuoroväyläverkon A kone 1 lähettää  
paketteja  Helsingin yliopiston eetteriverkossa olevalle koneelle 2  
(katso alla olevaa kuvaa).  Verkon kaikki koneet  käyttävät IP-protokollaa 
ja Internetin muita verkkokerroksen protokollia.  Selvitä, kuinka  paketti  
 ohjataan  eli reititetään   maapallon toisella puolella olevaan  oikeaan 
 verkkoon. Käy läpi vaihe vaiheelta yhden paketin matka koneelta A.1 koneelle 
 B.2  ja kerro, mitä paketille kulloinkin tehdään, mitä tietoja reitityksessä 
 käytetään ja millä protokollalla ne kulloinkin saadaan.  (4 p)
b) Selvitä myös kyseisten reititysprotokollien toiminta pääpiirteissään. 
Kerro,  miten  kyseiset   reititysprotokollat  toimivat, mitä tietoja ne 
keräävät  ja  kuinka  ne päivittävät reititystietojaan. (4p)

<PRE>

Tässä oli  kuva 5.44 Tanenbaumin kirjasta sivulta  412.
</PRE>
</I>
(Sasu Tarkoma)
<br>
Internet koostuu joukosta autonomisia alueita, jotka on yhdistetty
toisiinsa.  Runkolinjat (backbone) toimivat hierarkian ylimpänä kerroksena,
 toisena ovat paikalliset alueet ja viimeisenä yritysten ja 
yhteisöjen verkot.   Autonomisten alueiden sisällä käytetään
 sisäistä reititysprotokollaa (interior gateway protocol), 
autonomisten alueiden välillä käytetään ulkoista protokollaa
 (exterior gateway protocol).  Aikaisemmin käytettiin 
linkkitilareititystä,  nykyään Internetissä käytetään 
OSPF:ää (Open Shortest Path First).  
<P>
IP-osoite ja soketin portti saadaan sovellukselta(sovellustaso 
tietää siis ne).  
<br>
Internet taso:  IP-paketti valmistetaan, 
IP-osoite, mietitään reititystä lähettäjäkoneelta reitittimeen. Oletuksena on,  
että tiedetään ettei kone ole samassa lähiverkossa, muuten 
katsotaan taulukoita tai tehdään ARP-kysely.  Paketti 
kapseloidaan Ethernet-kehykseen  ja lähetetään reitittimelle,
joka hoitaa lähiverkon yhteyksiä alueeseen.
<P>
Reititin purkaa ethernet-kapseloinnin ja katsoo IP-paketin
 osoitekenttää.  Koska kyseessä on sama alue, reititin tietää,
 minne ohjata pakettia.  Reitityksessä voidaan käyttää 
linkkitilareititystä tai OSPF:ää (katso b-kohta).  Reititys tapahtuu 
IP-osoitteen verkko-osan perusteella.  OSPF:ssä tiedossa on
taulukko lyhimmistä reiteistä.  
<P>
Reititin tietää, että paketti on menossa runkoalueelle ja ohjaa 
sen sopivimmalle rajareitittimelle (area border router).   
Reititin tietää siis mikä rajareititin on sopivin.  Rajareititin
 tietää kaikki runkoalueen reitittimet ja pystyy ohjaamaan paketin
 reitittimelle, joka hoitaa US backbonen ja European backbonen 
liikennettä.   Tämä AS Boundary Router käyttää BGP (Border 
Gateway Protocol) - protokollaa (katso b-kohta).  BGP perustuu 
etäisyysvektorialgoritmiin ja siinä on tiedossa kustannukset
 ja koko reitit lähtöreitittimeltä kohdereitittimelle.
<P>
Paketin saapuessa autonomiselle alueellem runkoalueen reitittimet
 tietävät mille alueelle se pitää ohjata.  Paketti ohjataan
 lähimmälle alueesta vastaavalle Area Border - reitittimelle, 
joka siirtää sen alueelle. Alueen sisällä on käytössä OSPF tai 
linkkitilareititys tai jotain muuta, ja paketti ohjautuu
kohdereitittimelle.
<P> 
Kohdereititin voi tietää kohdekoneen ethernet-osoitteen taulukoista, jos 
ei tiedä niin tehdään ARP-kysely.    Kohdereititin katsoo siis
ensimmäistä kertaa IP-osoitteen host-kenttää ja käyttää mahdollista 
alivekkomaskia (subnet-mask). 
 Reititin kapseloi IP-paketin ethernet-kehykseen   ja laittaa sen 
 kohdelähiverkkoon.  
<P>
Kohdekone poimii sille tarkoitetun ethernet-kehyksen ja poistaa
kapseloinnin.  
IP-paketti annetaan Internet-kerrokselle, joka tekee vaadittavat
tarkistukset.  
Viesti (tai osa alkuperäistä viestiä) päätyy viimein
kuljetuskerrokselle,
 joka käsittelee UDP-paketin.  UDP:ssa data voidaan mahdollisesti 
tarkistaa  tarkistussummalla (checksum) (optionaalista).  
<Pre>

Tiivistelmä:
1. Kohdekoneelta lähiverkon reitittimelle: ARP tai verkkokerroksen 
   taulukoista
2. Lähiverkon reitittimeltä rajareitittimelle: linkkitilareititys tai
   OSPF. Reititys IP-osoitteen verkkokentän perusteella.
3. Rajareitittimeltä runkoalueen  reitittimelle
4. Runkoalueen  reitittimeltä alueiden väliselle reitittimelle 
   (AS boundary router)
5. AS boundary router siirtää paketin oikealle autonomiselle alueelle,
   protokollana  on BGP
6. Paketti kuljetetaan runkoalueelta oikealle alueelle.
7. Alueen sisällä se siirtyy lähiverkon reittimelle (linkkitila tai OSPF)
8. Paketti kohdereittimeltä kohdekoneelle, lähiverkko-osoite saadaan
   ARP:lla  tai taulukosta.

Pisteytys maksimi (nämä ovat suuntaa antavia)  yhteensä 4 p

1   Sisäinen ja ulkoinen reititysprotokolla.  OSPF/linkkitila/tai 
    jotain muuta ja BGP.  Hieman selostusta sisäisestä protokollasta. 
    Reititys tapahtuu IP-osoitteen verkkokentän perusteella.
0.5 Lähtö- ja kohdekone tietävät, minne ohjata paketti taulukon 
    tai ARP-kyselyn avulla.
0.5 Lähiverkon reitittimeltä rajareitittimelle
0.5 backbonella AS Boudary Routerille
1   BGP:tä käyttäen toiselle autonomiselle alueelle, kerrotaan hieman
    BGP:stä
0.5 paketin kulku kohdekoneelle
</PRE>

<I>
b) Selvitä myös kyseisten reititysprotokollien toiminta pääpiirteissään. 
Kerro,  miten  kyseiset   reititysprotokollat  toimivat, mitä tietoja ne 
keräävät  ja  kuinka  ne päivittävät reititystietojaan. (4p)
</I>
<P>
(Sasu Tarkoma)
<BR>
<B>OSPF: 
</B>
<br>Verkon topologiasta saadaan suunnattu graafi, jossa kytkökset 
edustavat kustannuksia (etäisyys, hinta, viive).  Näiden kytkösten 
painon mukaan lasketaan lyhimmät reitit reitittimien välille. 
<P>
OSPF:ssä autonomiset alueet voidaan jakaa vielä numeroituihin 
alueisiin, joista yksi on AS:n runkoalue (backbone) (alue 0).  Alueet ovat 
yhteydessä AS:n runkoalueeseen.   Yhdellä tällaisella alueella on 
oma linkkitila-tietokanta ja reititysalgoritmi.  Kahden alueen 
yhdistävän reitittimen täytyy tietää kummankin alueen reititystilanne, 
joten reititin joutuu käyttämään tarvittaessa useampaa algoritmia. 
OSPF:ssä on siis kolmenlaisia reittejä:  alueen sisällä, AS:n sisällä,
 ja AS:n välillä.  
<p>
Alueen sisällä on helpointa reitittää, koska reitittimet tietävät 
alueen topologian ja lyhimmät etäisyydet kohdereitittimelle. 
<P>
Alueiden välillä reitittäminen tapahtuu lähtökoneelta ensin
runkoalueelle, josta sitten kohdealueelle.  Kohdealueen sisällä reititys
on suoraviivaista.
<pre>
Erilaisia reitittimiä:
1. Sisäiset reitittimet
2. Alueen rajareitittimet yhdistävät kaksi aluetta (area border router)
3. Runkoalueen reitittimet 
4. Autonomisten alueiden rajareittimet (boundary routers)
</PRE>
OSPF:ssä alueen reitittimet vaihtavat tietoja jonkin määrätyn
(designated) reitittimen kanssa.  Reitittimet tulvittavat tietonsa
näille määrätyille reitittimille, jotka kuittaavat paketit ja 
ylläpitävät ajantasaista listaa muista reitittimistä.  Jokaisella 
reitittimellä on siis ajantasainen lista, jota ne päivittävät 
"viereisten" (adjacent) reitittimien avulla.   Jokaisella reittimellä
on siis graafi alueesta ja tieto lyhimmistä reiteistä.  
<P>
Runkoalueen reitittimet hyväksyvät tietoa alueiden rajareitittimiltä 
(area border router), ja laskevat reitit runkoalueen  reitittimiltä 
jokaisen alueen reittimille.  Tämä tieto lähetetään takaisin alueiden
rajareitittimille (area 
border router), jotka mainostavat pääsyä runkoalueelle. Näin 
alueen sisällä oleva reititin tietää parhaimman tien ulos runkoalueelle.  
<B>
BGP
</B>
<br>
Autonomisten alueiden välillä käytetään BGP:tä (Border Gateway
Protocol), jossa keskitytään poliittisiin kysymyksiin.   
Käytännöt ohjelmoidaan
 reitittimiin, eivätkä ne ole osa protokollaa.   BGP perustuu 
etäisyysvektorointi-algoritmiin.  BGP pitää kirjaa paitsi etäisyydestä, 
myös polusta, jota pitkin paketit kulkevat kohdereitittimelle. 
BGP reitittimet jakavat paitsi kustannuksia kohteille, myös 
tarkkoja polkuja kohteille.  Näin reitittimet tietävät, millä 
reitittimillä on toisistaan riippumattomat tiet kohteelle.  Käytössä 
olevaa politiikkaa rikkova reitinkustannus merkitään algoritmissa
äärettömäksi.

<pre>
Pisteytys maksimi 4 p.
2	BGP:n toiminta
2	OSPF:n toiminta
Tai vaihtoehtoisesti
2	Linkkitilareitityksen toiminta
</pre>
Lisäksi ARP:n, RIP:n ja etäisyysvektoroinnin selvittämisestä sai myös
pisteitä.
<p>
<I> 
3.  a) Käytetään TCP-protokollaa, jossa  segmentin maksimi koko on  1 KB ja  
kynnysarvo (threshold) on  32 KB.  Vastaanottajan ikkuna on  35 KB.  Oletetaan 
lisäksi, että  yhteyden kiertoviive (round   trip time) on 20 ms. Esitä 
kaaviokuvana, kuinka lähettäjä lähettää yhteyden ensimmäiset  200 KB, kun  
kuittaukset lähetettyihin segmentteihin saapuvat ajoissa. (3p) 
</I>
<P>
(Liisa Marttinen)
<br>
Tässä riitti  kaaviokuva, jossa ensin 20 ms välein (eli aina kun kuittaus on 
saatu)
lähetetään   1 KB, 2 KB, 4 KB, 8 KB, 16 KB ja 32 KB. Siis hidas aloitus (slow
start), jossa aloitetaan segmentin maksimikoolla ja kasvatetaan aina kuitauksen
tultua lähetysmäärä kaksinkertaiseksi kynnysarvoon 32 KB asti. Tämän jälkeen
kasvatus on lineaarista eli lähetetään 33 KB, 34 KB, 35 KB. Seuraavaksi
ruuhkaikkuna kasvaa 36 KB, mutta koska vastaanottajan ikkuna on 35 KB, voidaan
lähettää vain 35 KB. Kun nämä on saatu lähetettyä => koko 200 KB on lähetetty.
<P>
Arvostelusta:
<PRE>
 1 p esponentiaalinen vaihe, 
 1 p joka taittuu kynnysarvossa lineaariseksi
 1 p kuitenkaan vastaanottajan ikkunaa enempää ei  lähetetä
-2 p kynnysarvon saavuttaminen käynnisti uudestaan hitaan aloituksen 1 KB:stä 
-1 p vastaanottajan ikkunaa ei lainkaan otettu huomioon
</PRE> 
<I>
  b)  Miten sitten jatketaan  lähetystä, kun  kuittausta viimeiseen 
  lähetykseen ei saada ollenkaan? (2p)

</I>
<p>
(Liisa Marttinen)
<br>
Jos kuittausta ei saada ajoissa => uudelleenlähetys, joka aiheuttaa
lähetyksen hidastamisen eli kynnysarvoksi puolet ruuhkan aiheuttaneesta
määrästä (17.5 KB) ja käynnistetään  uudelleen hidas aloitus. Siis lähetetään  
1 KB, 2 KB, 4 KB, 8 KB ja 16 KB ja sitten 17 KB, jos lähetettävää olisi. Tässä
riittää 4 KB. (Oletettavasti 17 KB, toinen vaihtoehto olisi 32 KB, riippuen
siitä, miten algoritmi oikeasti on toteutettu! Tällä
ei tässä tehtävässä ole väliä.)
<Pre>
Arvostelusta:
1 p  kun kertoi, että hidas aloitus aloitettiin uudelleen 1 KB:stä 
1 p  ja  uudeksikynnysarvoksi puolet ruuhkaa aiheuttaneen lähetyksen määrästä 

1/2p kun huomasi ylipäänsä, että kuittauksen puuttuminen merkki ruuhkasta,
     jolloin lähetysnopeutta  pienennetäån
     (tai ainakin mainitsi uudelleenlähettämisen)
-1/2p kynnysarvoksi puolet kynnysarvosta
-1/2 p jotain sekavaa ja/tai pientä virheellistä tietoa
-1   kynnysarvo puuttuu kokonaan     
0 p  selvitti aivan jotain muuta kuten yhteyden muodostamisen tai 
     purkamisen ongelmia (kolminkertaista kättelyä tms)

</pRe> 
 <I>
  c) Miksi  TCP-protokollassa   uudelleenlähetysajastimen arvon  oikea 
  asettaminen on niin tärkeää?  Millä tavalla uudelleenlähetysajastimelle 
  saadaan arvo? (3 p)
</I>
<p>
(Liisa Marttinen)
<BR>
TCP:n ruuhkanvalvonta nojaa  uudelleenlähetyksiin. Uudelleenlähetys tulkitaan
ruuhkan merkiksi, jolloin vähennetään lähettämistä. 
<BR>
Jos ajastimen arvo on liian lyhyt, kuittaukset eivät ehdi perille ja syntyy
paljon uudelleenlähetyksiä. Näiden seurauksena lähettämistä eli verkon
kuormitusta vähennetään, jotta oletettua ruuhkaa pienennetään. 
Tästä aiheutuu verkon turhaa alikuormittamista ja verkon resurssien tehotonta
käyttöä. 
<BR>
Jos ajastimen arvo on liian suuri, ruuhkaa ei huomata tarpeeksi nopeasti, vaan
odotellaan ja odotellaan kuittauksia.
<BR>
Jotta uudelleenlähetysajastimen laukeaminen  toimisi tehokkaasti ruuhkan indikaattorina, niin
uudelleenläheysajastimen arvon tulee siis olla oikein asetettu. 
Oikean arvon
löytäminen  on hankalaa. Käytössä on melko monimutkaisia dynaamisia
algoritmeja. 
<br>
Ajastimella on  dynaaminen, verkon sen hetkisestä suorituskyvystä riippuva
arvo.  
Jokaiselle yhteydelle lasketaan  jatkuvasti arviota yhteyden
kiertoviiveestä. Arvio saadaan mittaamalla  kuittauksiin kuluvaa
aikaa ja laskemalla niistä sopivasti  painotettua liukuvaa keskiarvoa.
Ajastimen arvoksi asetetaan sitten  tämän   
arvon monikerta tai arvo lisättynä poikkeaman monikerralla. 
<BR>

<P> Arvostelusta:
<pre>
 3 p sai, jos kertoi uudelleenlähetysajastimen merkityksen ruuhkanvalvonnalle
     ja sitä kautta koko verkon suorituskyvylle sekä paljasti ajastimen arvon 
     nojautuvan jatkuviin verkosta tehtäviin kuittauksiin perustuviin 
     kiertoviivearvioihin.
-2 p jos  kertoi vain yleisesti liian pienen arvon lisäävän turhia
     uudelleenlähetyksiä ja aiheuttavan ruuhkaa sekä liian suuren johtavan 
     turhiin odotuksiin ja tehottomuuteen.  Koska TCP:n ruuhkanhallinnan takia
     tilanne on täysin päinvastainen!
+1 p Jos selvitti oikein perusteellisesti ajastimen arvon laskemisen, sai yhden
     bonuspisteen, joka korvasi mahdollisesti menetettyä pisteitä. Maksimi
     kuitenkin c-kohdasta 3 pistettä.         

</PRE>


<I>
4.  (Sampo Pyysalo)
<br>
  a) Tuntumattomassa sillassa on portteja useihin lähiverkkoihin. Miten 
       silta oppii tietämään,
     mistä suunnasta eri koneet löytyvät? (1 p)
</I>
<br>
a) Backward learning. (Tanenbaum s. 311) (1p)
<p>
<I>     
b) Miksi etäisyysvektorireitityksessä hyvät tiedot etenevät nopeasti, 
mutta huonot hitaasti? Miten  tilanne voitaisiin korjata? (2 p)
</I>
<br>
Hyvät tiedot etenevät "lineaarisesti" (1/2p) (Tanenbaum kuva 5-11 (a))
   huonojen tietojen eteneminen kärsii count-to-infinity - ongelmasta (1p)
   (Tanenbaum s. 357). Ratkaisuja (1/2p) esim. split horizon (osittainen
   ratkaisu, Tanenbaum s. 358) tai käytettyjen reittien ilmoittaminen
   (BGP:n malli, Tanenbaum s. 430).
<P>
<I>
 c) Miksi palomuurissa on sekä reitittimiä että yhdyskäytävä? (1 p)
<BR>     
 </I>
 Reitittimet suodattavat pakettitasolla osoitteiden ja porttien
   perusteella, yhdyskäytävä sovellustasolla (esim. viestin sisällön
   perusteella). (Tanenbaum s. 410) (1p)
<P>
<I>    
     d) Mikä on jumbogrammi? Milloin ja missä sitä käytetään? (1p)
</I>
 <BR>
 IPv6 - datagrammi joka käyttää yli 64K kokoisten pakettien lähettämisen
   sallivaa laajennusotsaketta (1/2p), hyödyllinen nopeiden koneiden
   kommunikoinnissa laajakaistaisessa verkossa (1/2p) (Tanenbaum s. 444)
 <P>
 <I>   
     e) Mihin UDP:tä tarvitaan? Eikö riittäisi antaa käyttäjäprosessien 
     lähettää pelkkiä   IP-paketteja? (1 p)
</I>
<br>
UDP tarjoaa porttinumerot ja tarkistussumman (1/2p), pelkät IP-paketit
   eivät riitä koska IP-osoitteen perusteella pystytään tunnistamaan vain
   kone, ei prosessia (ohjelmaa) (1/2p)
<p>
Tehtävän 4 arvostelusta: 
<br>
Täsmälleen oikeita vastauksia ei vaadittu eikä lievistä epätarkkuuksista
otettu pisteitä. Kohdissa b), d) ja e) ei kaikkia vastauksen osia vaadittu, 
jos asia oli ymmärretty hyvin tai jokin osa oli esitetty erityisen
täsmällisesti.
<p>
Esitetyt arvosteluperusteet ovat suuntaa-antavia, eivät absoluuttisia.

<br>