Tietoliikenne II, kevät 2001 

Harjoitus 3 (tiistai 6.2.2001) 

1. Mikä on IP-osoitteen 192.31.63.8  verkko-osoite ja koneosoite
a) jos käytössä luokallinen osoitus,
b) luokaton osoitus (CIDR) 192.31.63.8/20,
c) luokaton osoitus ja lisäksi aliverkkomaski,jossa ensin 28 ykköstä ja loput 
nollia?

2. Kun yritys käyttää sekä luokatonta osoitusta että aliverkkoa, niin mitä 
tietoa yritysksen reittimien reititystaulussa tällöin on? Miten reititys 
tapahtuu?  

3. Etäisyysvektorireitityksessä halkaistu horisontti (Split horizon) auttaa,  
jos reitityssilmukoissa on vain kaksi reititintä. Kolme reitintä voi kuitenkin 
edelleen aiheuttaa "count-to-infinity" -ongelman. 
a) Esitä, miten tämä ongelma syntyy ja  miten se näkyy  tilanteessa, jossa 4 
reititintä on yhdistetty kuvan esittämällä tavalla.

      A ........  B
       .         .
        .      .  
          .   .
            C
            .
            .
            .
            D

b) Eräs ratkaisu kohdan a) ongelmaan on  esitetty alla.
"Triggered  updates simply add a rule that whenever a gateway changes the 
metric for a route, it is required to send update messages almost immediately, 
even if it is not yet time for one of the regular update message. (The timing 
details will differ from protocol to protocol. Some distance vector protocols, 
including RIP, specify a small time delay, in order to avoid having triggered 
updates generate excessive network traffic.) Note how this combines with the 
rules for computing new metrics. 
Suppose a gateway's route to destination N goes through gateway G. If an update 
arrives from G itself, the receiving gateway is required to believe the new 
information, whether the new metric is higher or lower than the old one. If 
the result is a change in metric, then the receiving gateway will send 
triggered updates to all the hosts and gateways directly connected to it. 
They in turn may each send updates to their neighbors. The result is a cascade 
of triggered updates. 

It is easy to show which gateways and hosts are involved in the cascade. Suppose a gateway G times out a route to destination N. G will send triggered updates to all of its neighbors. However, the only neighbors who will believe the new information are those whose routes for N go through G. The other gateways and hosts will see this as information about a new route that is worse than the one they are already using, and ignore it. The neighbors whose routes go through G will update their metrics and send triggered updates to all of their neighbors. Again, only those neighbors whose routes go through them will pay attention. Thus, the triggered updates will propagate backwards along all paths leading to gateway G, updating the metrics to infinity. This propagation will stop as soon as it reaches a portion of the network whose route to destination N takes some other path." 

Näytä, miten tämä ratkaisu toimisi a)-kohdan tapauksessa. Pystytäänkö sillä 
täysin estämään "count-to-infinity"-ongelma?

4. Käytössä on  etäisyysvektorialgoritmi. Oletetaan, että kuvan verkossa 
jokainen solmu aluksi tietää vain etäisyyden  naapureihinsa. Mikä on solmun 
E reititystaulun sisältö, kun solmu on vaihtanut etäisyystietoja naapuriensa 
kanssa?  

         1
A --------------- B
|              /  |
|          5 /    |
| 2        /      | 15
|        E        |
|     /     \     |
|   /2     10 \   |
| /             \ |
C --------------  D
        1


5. Reititystaulun alkiot on talletettu IP-osoitteen bittien mukaan 
puurakenteeksi, josta reititin etsimässä  niitä tutkimassa. Osoitteen 
etsinnässä kukin askel vaatii yhden muistista haun ja yhden muistihaun 
kesto on 40 nanos. Kuinka monta osoitehakua 32-bitin IP-osoitteita 
käsittelevä reititin pystyy korkeintaan suorittamaan sekunnissa? 
Entä 128-bitin osoitteita käsittelevä reititin?


6. Tutki Tanenbaumin kirjassa olevan kuvan 5.20 s.371 aliverkkoa. Olettaen, että linkkien kustannukset ovat samat, niin millainen "reverse path forwarding"-puu muodostuisi solmulle F?  Miten tämä puu syntyy? Kun F lähettää paketin, niin montako pakettia kaikkiaan aliverkossa lähetetään?