Tietoliikenne II, syksy 2002

Harjoitus 4 (15.-17.10.2002)

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ä verkon topologia kuvan mukainen. A, B ja C ovat verkko-operaattoreiden (ISP) runkoverkkoja ja x, y ja z tavallisia yritysverkkoja. Verkkojen välisessä reitityksessä on käytössä BGP-protokolla.

Vaikka verkko x on yhteydessä kahteen eri operaattoriin, se ei missään nimessä halua välittää mitään läpikulkuliikennettä. Verkko-operaattorit suostuvat välittämään toisen operaattorin liikennettä vain omille asiakkailleen. Esimerkiksi verkko B välittää kyllä A:lta tulevaa liikennettä verkkoon x, mutta ei suostu välittämään A:lta tulevaa liikennettä C:lle ja sen asiakkaalle y:lle.

a) Millaista polkuinformaatiota näiden verkkojen välillä vaihdetaan eli mitä reittejä verkkojen BGP-reitittimet paljastavat toisilleen?

b) Millainen on kunkin yritysverkon x, y ja z näkemys koko verkon topologiasta?

3. 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ä?

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