S-38.188 Tietoliikenneverkot
Luento 4: Kytkentä ja reititys
Miksi kytketään
- Suoraan yhteyteen perustuvat verkot asettavat rajoituksia sille, kuinka monta päätelaitetta voi olla kytkettynä verkkoon
- Suoraan yhteyteen perustuvat verkot ovat
maantieteellisesti rajallisia (pitkät linkit eivät kata
aluetta niiden välillä).
- Ethernet-verkon pituutta rajoittaa paketin päästä päähän kulkuaika
OSI-malli
Välitys ja kytkeminen OSI-mallissa
OSI-mallin mukaan tapahtumat, joissa yhdeltä linkiltä toiselle siirretään informaatiota tapahtuu kerroksella kolme (L3) eli verkkokerroksella.
L1-välitin
- L1-välitin on toistin
- Toistimessa regeneroidaan siirtotien signaali, etäisyyden kasvattamiseksi
L2-välitin
- L2-välitin on pakettikytkin
- L2 pakettikytkin tietää tarkasti
osoitteen, josta paketti tulee ja minne sen kuuluu mennä.
- Osoite relaatio muodostaa, joko
- sanomavälityksellä
- linjaa tarkkailemalla
- Osoite relaatio muodostaa, joko
- Tyypillisiä laitteita ovat:
- Silta
- Ethernet kytkin
- ATM-kytkin
- SDH/SONET ristikytkentälaitteet
L3-välitin
- L3-välitin on pakettikytkin
- L3-pakettikytkimellä ei ole selkeää kuvaa tarkasta yhteydestä vaan se käsittelee kokoomatietoa (verkkotason informaatiota)
- Verkkotason informaation saadaan
- käsin syöttämällä
- reititysprotokollilla
Terminologiaa
- Reititys (routing) on prosessi, jossa rakennetaan tietokanta kohdeosoitteen ja lähtöjohdon välille.
- Välitys (forwarding) on prosessi, jossa reititystietokannasta etsitään haluttua kohdeosoitetta vastaava lähtöjohto.
- Kytkentä (switching) on prosessi, jossa tulojohdolta kopioidaan informaatio lähtöjohdolle.
Pakettikytkin
- Sisältää normaalisti useita tulo- ja lähtöjohtoja
- Tehtävät:
- Muodostaa reititystaulukko muilta pakettikytkimiltä saamastaan informaatiosta sekä välittää omat tietonsa muille.
- Uuden paketin saapuessa suorittaa paketin välitys perustuen paketin osoitteeseen.
- Kytkeä paketti oikealle lähtöjohdolle
- Huolehtia eri johtojen sovituksesta (nopeus, protokolla jne)
Perusteita
- Pakettikytkin muodostaa yhdistettyjäverkkoja
liittämällä
- useita lähiverkkoja toisiinsa tähti topologialla.
- useita pakettikytkimiä toisiinsa ??? topologialla
Erilaiset pakettikytkentätavat
- Yhteydetön kytkentä ~ sanomanvälitys
- Yhteydellinen kytkentä ~ virtuaalikanavat
- Lähdereititys, itsereititys
Lähdereititys
- Jokainen päätelaite tietää verkon rakenteen ja jokaisen verkon kytkimen lähtöjohdon nimen.
Lähdereititys
- Edut
- Yksinkertainen verkon laitteille
- Haitat
- Osoitteen pituus riippuvainen verkon / yhteyden syvyydestä
- Verkon topologian selvittämien ja varastointi jokaiseen päätelaitteeseen on kallista
- Eriallaisia näkemyksiä siitä mitä otsikossa tulee olla ja miten sitä tulee käsitellä
Virtuaalipiirikytkentä
- Yhteyden alussa muodostetaan virtuaalinen yhteys läpi verkon
Virtuaalipiirikytkentä
- Etuja
- Osoite kiinteän mittainen ja pienempi
- Välitys mahdollista toteuttaa raudalla
- Haittoja
- Yhteyden pystyttäminen vaatii RTT:n mittaista aikaa ennen kuin varsinainen datan siirto voi alkaa
- Jos jokin verkon komponenteista vioittuu (virhetila), joudutaan yhteys pystyttämään uudestaa
Sanomakytkentä
- Jokainen paketti reititetään erikseen verkon läpi
Sanomanvälitys
- Edut
- Ei viivettä yhteyden pystyttämisen ja informaation siirron välillä
- Haitat
- Jokainen paketti reititetään omana tietoyksikkönään
- Isommat osoitteet (globaali osoite)
- Päätelaite ei tiedä verkon tilaa lähettäessään dataa verkkoon
Reititys
- Tehtävä muodostaa reititystaulukko tai päivittää olemassa olevaa taulukkoa
- Haetaan halvinta (lyhintä) polkua kahden päätelaitteen välillä
- Algoritmit perustuvat graafiteoriaan
Levitys
- Yksinkertaisin tapa reitittää informaatiota
- Perustuu informaation kopioimiseen jokaiselle lähtöjohdolle paitsi sille mistä informaatio saapui.
- Ei vaadi reititystaulukkoa
Levitys
- Jokainen kytkin tietää vain verkon
lokaalin topologian
- Vain naapuri kytkimet ja päätelaitteet
- Soveltuu verkkoihin, joiden
- Topologia muuttuu usein (mobiiliverkko)
- Johdot ovat epäluotettavia (sotilasverkot)
- Reititysinformaatio täytyy välittää kaikille kytkimille
Virittäväpuu
- Virityspuu on menetelmä, jossa levitysmenetelmään
perustuvaa reititystä optimoidaan
- poistamaan turhaa liikennettä
- poistamaan silmukoita verkosta
Virittäväpuu
Virittäväpuu
- Valitaan juuri (kytkin, jolla on
pienin tunniste)
- Alussa kaikki kytkimet kuvittelevat olevansa juuria ja kertovat olemassa olostaan kaikkialle pituudella nolla (0)
- Kaikki kytkimet päivittävät tietojaan sitä mukaan kun ne vastaanottavat tietoja muilta kytkimiltä
- Kun verkko stabiloituu etenee verkossa tieto juuresta ja etäisyys juureen.
Lyhimmän polun algoritmit
- Kaikki lyhimmän polun algoritmit perustuvat siihen että lyhin polku on rekursiivisesti määriteltävissä.
Bellmanin algoritmi
- Lyhimmän polun algoritmi, jossa
- on erillinen jono johon muutoksia kokeneet kytkimet sijoitetaan
- jonosta käsitellään FIFO-tyyppisesti kytkimiä
- jo kertaalleen jonossa olevia ei sijoiteta uudestaan
Bellmanin algoritmi
Bellmanin algoritmi
Bellmanin algoritmi
Bellmanin algoritmi
Bellmanin algoritmi
Bellmanin algoritmi
Bellmanin algoritmi
Bellmanin algoritmi
Bellmanin algoritmi
Bellmanin algoritmi
Bellmanin algoritmi
Bellmannin algoritmi
Bellman-Ford algoritmi on
Bellman-Ford algoritmi on
Miten käytännössä
Miten käytännössä
Miten käytännössä
Miten käytännössä
Miten käytännössä
Linkin katkeaminen aiheuttaa päivityskierroksen
Linkkitila
- Linkintilaan perustuvat reititys menetelmät ylläpitävät verkon topologiakarttaa.
- Topologiakartta perustuu ajatukseen, että
- jokainen kytkin tietää sen välittömän naapurin ja välisen johdon tilan
- jokainen kytkin kertoo naapurilleen oman käsityksensä naapureistaan ja niihin johtavista johdoista
Linkkitilakartta
Dijkstran algoritmi
Dijkstran algoritmi
Dijkstran algoritmi
Dijkstran algoritmi
Dijkstran algoritmi
Dijkstran algoritmi
Dijkstran algoritmi
Dijkstran algoritmi
Kustannusfunktio
- Edellä esitetyissä vaihtoehdoissa
on kustannus eri johdoilla ollut
- 1 (minimi kytkentä reititys)
- vakio (minimi kustannus reititys)
- Kustannusfunktio voi olla myös riippuvainen
verkon tilasta ja erilaisten johtojen ominaisuuksista
- Verkon kuormituksen huomiointi
- Operaattorin huomiointi
- Johdon siirtoviiveen huomiointi
- Johdon kapasiteetin huomiointi
Kustannusfunktion dynamiikka
- Mikäli kustannusfunktion reagoi verkon
viiveisiin ja kurotitukseen
- täytyy reagoinnin perustua keskiarvoistukseen
- hetkellinen muutos ei saa olla liian suuri (oskilointi)
- kuormitusta ei saa huomioida pienillä kuormitusasteilla
