Harjoitus 4 (tiistai 20.11.2001)

1. Oletetaan, että kaikki verkon reitittimet ja isännät toimivat oikein eivätkä tee mitään virheitä ja niissä oleva ohjelmisto on myös virheetöntä. Onko silti mahdollista, että paketti toimitetaan väärään kohteeseen?

2. Oletetaan, että on yksi lähettäjä ja 32 vastaanottajaa. Lähettäjä on binääripuun juurena ja vastaanottajat sen lehtinä ja muissa välissä olevissa solmuissa on aina reititin. Sanoma lähetetään lähetetään lähettäjältä reitittimien kautta vastaanottajille. Ensin sanoma siirtyy lähettäjältä reitittimelle, siitä seuraavalle reitittimelle jne, kunnes se viimein saavuttaa vastaanottajan.
   1. Montako lähetystä kaikkiaan tarvitaan, kun lähetetään sanoma jokaiselle vastaanottajalle erikseen?
   2. Montako lähetystä tarvitaan, kun sanoma lähetään monilähetyksenä?

3. Tulvitus on eräs tapa monilähettää paketteja. Missä tulvitusta käytetään? Tulvituksen yksi ongelma se, että lähetyksiä syntyy hyvin runsaasti ja paketit voivat jäädä verkon silmukoihin ikuisiksi kiertolaisiksi. Mitä erilaisia tapoja on vähentää pakettien määrää ja lopettaa tulvitus?

4. Oletetaan, että C on valittu oheiselle verkolle keskussolmuksi keskuspohjaisessa monilähetysreitityksessä. Jos jokainen monilähetyksessä mukana olevista reitittimistä A, B, E ja F liittyy keskussolmuun pienimmän kustannuksen polkua pitkin, niin millainen keskuspohjainen reitityspuu syntyy? Onko tuloksena oleva puu Steiner-puu?

            1             1
          B ------------ D ------------ E
          | .                          .|
          |  .                       .  |
          |   .                    .    |
          |    . 2             2 .      |
        4 |     .              .        | 1
          |      .           .          |
          |       .        .            |
          |        .     .              |
          |         .  .                |
          A -------- C ---------------  F            
               3             2
   
   

5. Oletetaan, että edellisen tehtävän verkon linkin BD linkkikustannus muuttuu kymmenkertaiseksi eli 10:ksi. Selvitä Steiner-puu, joka yhdistää kaikki ryhmään kuuluvat solmut A, B, E ja F. (Ei ole tarpeen käyttää Steiner-puun konstruoimisalgoritmia, vaan riittää tarkastella verkkoa ja löytää siitä Steiner-puu)

6. Tutki allaolevaa verkkoa. Olettaen, että linkkien kustannukset ovat samat, niin millainen "reverse path forwarding"-puu muodostuisi solmulle F? Miten tämä puu syntyy? Kun F lähettää yleislähetyspaketin, niin montako pakettia kaikkiaan aliverkossa lähetetään?

   
                B --------------------------------------------- C
                |                                               |
         E -----|---------------------------- A                 |
         |      |                             |                 |
         |      |                             |                 |  
         H -----|------------ I ------------- F --------------- D
         |      |             | .                               |
         |      L             |  .                              |
         |     .              |   .                             |
         |    .               |    .                            | 
         |   .                |     .                           |
         |  .                 |      .                          |
         | .                  |       .                         |
         |.                   |        .                        |
         K -------- M ------- N -- O -- J --------------------- G