4. Monilähetysreititys

Paketti lähetetään usealle vastaanottajalle

Miksi?

Monet sovellukset hyötyvät

ohjelmistopäivitykset

WWW-välimuistien päivitykset

etäopetus, virtuaalikoulu

videoiden, äänitteiden lähetys

interaktiiviset pelit

Mitä hyötyä?

Nopeus, tehokkuus

paketti monelle vastaanottajalle

useita kaksipistelähetyksiä: kaikille oma paketti

tulvitus

multidestination routing: kohteet lueteltu paketissa, reititin kopioi kaikkiin tarpeellisiin ulosmenoihin

lähettäjän virittävä puu (spanning tree)

ei silmukoita

yhteinen tai jokaiselle lähettäjälle oma puu

reverse path -algoritmi (käänteinen polku)

estimoi virittävää puuta

Monilähetys

Monilähetysryhmä

ryhmäosoite (Luokan D osoite)

vastaanottajaryhmän hallinta

ryhmien muodostus, poistaminen

vastaanottajien lisääminen, poistaminen

Monilähetyksen reitittäminen

reitittimet tietävät ketkä kuuluvat mihinkin ryhmään

laskevat lyhimmät reitit vastaanottajiin

ohjaavat reititystaulujensa avulla paketit vastaanottajille

4.1. IGMP (Internet Group Management Protocol) (RFC 2236)

Monilähetysryhmien hallinta

IGMP isäntäkoneen ja sen lähimmän reitittimen välillä

isäntäkone ilmoittaa itsensä jäseneksi tiettyyn ryhmään

isäntäkone poistaa itsensä ryhmästä

monilähetysreititysalgoritmi

reitittimien välillä monilähetysten koordinoimiseksi

esim. PIM, DVMRP, MOSPF

huom! ryhmän isäntäkoneiden välillä ei ole mitään protokollaa

eivät tiedä, ketkä muut kuuluvat ryhmään

D-osoitteet

monilähetykset D-osoitetta käyttäen

perilletoimitus ‘best effort’

28 bittiä => yli 250 miljoonaa ryhmäosoitetta

224.0.0.0 – 239.255.255.255.

224.0.0.0 - 224.0.0.255 reititysprotokollille yms

pysyviä ryhmiä

224.0.0.1 kaikki lähiverkossa

224.0.0.2 kaikki reitittimet lähiverkossa

224.0.0.5 kaikki OSPF-reitittimet lähiverkossa

224.0.0.6 kaikki ‘designated’ OSPF-reitittimet

lähiverkossa

tilapäisiä ryhmiä

IGMP:n toimintaperiaate

kysely/vastaus

monilähetysreitittimet kyselevät

noin minuutin välein kysyvät kaikilta koneiltaan, mihin ryhmiin kuuluvat

224.0.0.1-osoitteella

koneet vastaavat

ilmoittamalla kaikkien niiden ryhmien D-osoitteet, joihin jokin niiden sovellus on liittynyt

host

router

kysely

vastaus

IGMP-sanomat

Membership query

general: mihin ryhmiin kuuluvia?

specific: onko tiettyyn ryhmään kuuluvia?

Kyselyillä maksimivastausaika

Membership report

kone haluaa liittyä tai on liittynyt ilmoitettuun ryhmään

Leave group

kone ilmoittaa poistuvansa ryhmästä

vapaaehtoinen!

Jos ei vastaa kyselyihin, ei ole enää mukana

=> jäsenyyden voimassaololle aikaraja

IGMP-sanoma

Type max. response checksum

time

Multicast Group Address

Type = mikä sanoma kyseessä

max. response time = maksimivastausaika kyselyissä

Checksum = taskistussumma

Multicast Group Address = monilähetysryhmän osoite

Maksimivastausaika?

Optimointia varten, esim. LAN-verkoissa, joissa kaikki kuulevat kaikki sanomat

reititin haluaa tietää vain onko kukaan sen LANin koneista kiinnostunut tietystä ryhmästä

ei sitä ketkä koneista haluavat ryhmän jäseniksi

ei edes montako sen koneista on tietyn ryhmän jäseninä

koneet vastaavat satunnaisen ajan kuluttua

jos joku muu kone jo vastannut, ei enää vastaa

=> vastausten määrä pienenee

Internetin monilähetyspalvelumalli

Kone ilmoittaa omalle reitittimelleen haluavansa liittyvä tiettyyn ryhmään

IGMP:n membership_report-sanomalla

Reitittimet alkavat välittää koneelle tämän ryhmän viestejä

vastaanottajavetoinen (receiver-driven)

Lähettäjä ei pidä kirjaa ryhmän jäsenistä eikä tiedä kenelle kaikille viesti menee.

Kuka tahansa voi toimia lähettäjänä

eri lähettäjien sanomat tulevat sekaisin

Monilähetysosoitteita ei koordinoida verkkotasolla

eri ryhmille voidaan valita sama osoite

IGMP ja IPv6?

IGMP käyttää 32 bitin osoitetta

Ei erillistä IGMP-protokollaa IPv6:lle, vaan toiminnot liitetty ICMPv6:een (RFC 2710)

Multicast Listener Query

Yleinen kysely: millä monilähetysosoitteilla on 'kuuntelijoita'

Tietyn monilähetysosoitteen kuuntelijat

Multicast Listener Report

Multicast Listener Done

4.2 Monilähetysreititys (multicast routing)

Ongelma:

Reitittimien on kyettävä rakentamaan ‘optimaaliset’ reitit ryhmän kaikille vastaanottajille

kun mikä tahansa kone voi toimia lähettäjänä

ryhmään voi kuulua eri määrä vastaanottajia

lähes kaikki isäntäkoneet

vain muutama isäntäkone

ryhmän jäsennyys voi olla hyvin dynaamista

Tavoitteena on löytää mahdollisimman optimaalinen linkkipuu, joka yhdistää kaikki ryhmän jäsenet

sanomien reititys puun linkkejä pitkin

A

B

C

D

F

E

A, B, E ja F: reitittimillä ryhmän jäseniä

C ja D: reitittimillä ei ole ryhmän jäseniä

Monireitityspuun rakentaminen

Kaksi erilaista lähestymistapaa

yksi puu koko ryhmälle (group shared tree)

kuka tahansa toimii lähettäjänä, niin reitityksessä käytetään samaa puuta

jokaiselle lähettäjälle oma puu (source-based tree)

jos ryhmässä on n jäsentä, niin muodostetaan n eri puuta

jokaisen lähettäjän sanomat reititetään sen oman linkkipuun avulla

Yksi puu koko ryhmälle

A

B

C

D

F

E

A, B, E ja F: reitittimillä ryhmän jäseniä

C ja D: reitittimillä ei ole ryhmän jäseniä

reitityslinkki

Eri lähettäjille omat puut

A

B

C

D

F

E

A, B, E ja F :reitittimillä ryhmän jäseniä

C ja D: reitittimillä ei ole ryhmän jäseniä

A:n lähettäessä

B:n lähettäessä

Reititys käyttäen yhtä puuta koko ryhmälle

Löydettävä puu, joka yhdistää kaikki ryhmän reitittimet

mukana myös muita reitittimiä

puun kustannus on sen linkkien kustannusten summa

pienimmän kustannuksen puu

NP-täydellinen ongelma (Steiner tree problem)

suht.koht. hyviä heuristisia ratkaisuja on

ei ole käytössä Internetissä

tiedettävä kaikki kaikki linkkikustannukset

kustannusten muuttuessa laskettava uudelleen

jo muutenkin laskettujen kustannusten hyödyntäminen

Pienimmän kustannuksen monilähetyspuu

A

B

C

D

F

E

A, B, E ja F: reitittimillä ryhmän jäseniä

C ja D: reitittimillä ei ole ryhmän jäseniä

3

4

1

1

2

2

1

2

Keskuspohjainen reititys (Center-based routing)

Ryhmän puun keskuksena on jokin solmu, johon muut myöhemmin liittyvät

ensin saadaan selville keskussolmu

muut liittyvät siihen JOIN-sanomilla

yksilähetyksiä keskussolmulle

Miten keskussolmu valitaan?

Valitaan siten, että puu on melko lähellä optimia

Keskuspohjainen monilähetyspuu

A

B

C

D

F

E

A, B, E ja F: reitittimillä ryhmän jäseniä

C ja D: reitittimillä ei ole ryhmän jäseniä

3

4

1

1

2

2

1

2

G

1.

2.

3.

Ratkaisevaa on keskussolmun järkevä valinta

Jokaiselle lähettäjälle oma puu

Tavallisessa reitityksessä jo yleensä lasketaan pienimmän kustannuksen puu lähettäjältä muihin solmuihin

Dijkstra => reititystaulu

least unicast-cost path tree = näiden polkujen yhdistelmä

Reverse path forwarding

“Älä turhaan lähetä tänne” (pruning)

paljon puita

N lähettäjää => N puuta

reitityksessä käytetty puu valitaan lähettäjän mukaan

Reverse path forwarding -algoritmi

idea

tuliko paketti portista, josta normaalisti lähetetään paketin aloittaneelle solmulle?

jos tuli, paketti kopioidaan kaikkiin muihin portteihin

jos ei tullut paketti tuhotaan kaksoiskappaleena

edut

tehokas ja helppo toteuttaa

ei tarvitse tuntea virittävää puuta

ei ylim. yleisrasitetta (kohdelista, lisäbittejä)

tulvitus päättyy itsestään

ryhmän jäsen

ei ole jäsen

A

C

B

F

E

D

G

lähettäjä

pruning: ’Älä turhaan lähetä tänne!’

Monilähetysreititys Internetissä

DVMRP (Distance Vector Multicast Routing Protocol) (RFC 1075)

kullekin lähteelle oma puu

käyttäen ‘reverse path forwarding’-menetelmää ja karsimista (pruning) ja lisäämistä (graft)

etäisyysvektorialgoritmin avulla kukin reititin laskee lyhyimmän polun jokaiseen mahdolliseen lähteeseen ja tallettaa linkin (next hop)

tieto puussa ‘alavirtaan’ sijaitsevista reitittimistä, jotta tiedetään, milloin haara voidaan kokonaan karsia

kun kaikki reitittimet ilmoittavat, etteivät enää ole kiinnostuneita

Muita

MOSPF (Multicast Open Shortest Path First) (RFC 1584)

OSPF:ää käyttävissä AS:issä

linkkitilailmoituksissa myös tieto monilähetysryhmien jäsennyydestä

kaikki reitittimet tietävät, mihin monilähetysryhmiin muiden reittimien isäntäkoneet kuuluvat

voivat laskea kullekin lähteelle oman ennaltakarsitun lyhyimmän polun puun kullekin monilähetysryhmälle

Muita monilähetysprotokollia: CBT

CBT (Core-based Trees) (RFC 2201, RFC 2189)

kaksisuuntainen yhteiskäyttöinen puu, jossa yksi keskus

sanomia

JOIN_REQUEST keskussolmulle, kun haluaa liittyä ryhmään

JOIN_ACK keskussolmu tai lähin jo ryhmässä oleva reititin

ECHO_REQUEST vieläkö mukana ryhmässä

ECHO_REPLY vielä mukana

FLUSH_TREE poistetaan ryhmästä

Muita: PIM

PIM (Protocol Independent Multicast) (RFC 2362)

dense mode ~ DVMRP

tulvita ja karsi sopii hyvin, jos vastaanottajia on ‘tiheään’

sparse mode ~ CBT

JOIN-sanomia, jotka ohjataan yksilähetyksenä keskussolmuun

polulla olevat reitittimet monilähetysmoodiin

keskussolmu lähettää monilähetyksenä muille

yksi puu <=> lähettäjälle oma puu

5. Mobile IP

IP-reititys IP-osoitteen perusteella

koneen osoite riippuu verkosta, jossa kone sijaitsee

kun kone siirtyy toiseen verkkoon tilapäisesti, osoite ei ole enää voimassa

koneelle uusi osoite tässä verkossa?

Tieto uudesta osoitteesta muille?

TCP-yhteys katkeaa

saumaton siirtyminen tuntumattomasti ei ole mahdollinen

kaikille koneille verkosta riippumaton osoite?

Liikkuvien isäntäkoneiden reititys

liikkuva kone (mobile host)

kotiosoite (home address, home location)

kotiagentti (home agent)

tietää, missä omat liikkuvat ovat

kun ilmaantuu vieraalle alueelle, se rekisteröityy

vierasagentti (foreign agent)

hoitaa alueelle tulleet vieraat liikkuvat

Liikkuvien isäntäkoneiden reititys

liikkuva kone (mobile host)

kotiosoite (home address, home location)

pysyvä osoite omassa verkossa,

aina tavoitettavissa tällä osoitteella

kotiagentti (home agent)

tietää, missä omat liikkuvat ovat

jos ei liikkuva kone ei ole kotiverkossa, kotiagentti osaa ohjata sille tulevat sanomat liikkuvan uuteen osoitteeseen

kun liikkuva kone ilmaantuu vieraalle alueelle, se rekisteröityy alueen

vierasagentille (foreign agent)

joka hoitaa alueelle tulleet vieraat liikkuvat

antaa niille osoitteen (care of address)

tämän verkon osoite

tarkistaa vieraan tiedot sen kotiagentilta

ilmoittaa kotiagentille koneen uuden osoitteen

näin kotiagentti tietää uuden sijainnin

Uudelle alueelle rekisteröinti

Vieras-agentti

Koti-agentti

Rekisteröinti-pyyntö

Pyynnön välitys

Sallii tai kieltää

vastaus

Vastaus koneelle

Käsittelee pyynnön ja vastauksen

Rekisteröintipyyntö sisältää:

sanoman tyypin (1)

lippuja, mm. haluttu tunnelointitapa

rekisteröinnin keston

koneen kotiosoitteen, kotiagentin osoitteen ja koneen vierasverkon osoitteen

rekisteröintipyynnön tunnisteen

laajennuksia, mm. autentikointilaajennus

Rekisteröintivastauksessa:

Sanoman tyyppi (3)

hyväksyttiinkö vai hylättiinkö rekisteröintipyyntö, kuka hylkäsi kotiagentti vai vierasgentti

hyväksytty rekisteröinnin kesto

pyynnön tunniste

liittää vastauksen pyyntöön

laajennusosia mm. autentikointi

Rekisteröinnissä ongelma on turvallisuus

Tekeytyminen vierasagentiksi

haluaa kaapata koneen liikenteen

tehokas autentikointi estää

autentikoinnin laajennusosa

MN -->FA, MN --> HA, FA --> HA

vanhojen rekisteröintipyyntöjen lähettäminen kotiagentille

kotiagentille väärä osoite => koneelle ei voi lähettää kotiosoitteella

pyyntöihin aikaleimat

Agentin löytäminen verkosta

Agentit ilmoittelevat itsestään säännöllisin välein

ilmoituksissa

reitittimen osoite

rekisteröinnin kesto

joukko lippuja: toimiiko vieras- vai kotiagenttina, onko kiireinen, millaista kapselointia kykenee käyttämään

vierasosoitteita, vähintään yksi

ilmoitusten avulla kone havaitsee siirtyneensä toiseen verkkoon

agentin osoite vaihtuu => uudelleenrekisteröinti

kotiverkossa, kun saa ilmoituksia omalta kotiagentiltaan

peruutettava rekisteröinti

Liikkuva kone kysyy itse agenttia

huomaa liikkuneensa toiseen verkkoon, kun alkaa saada sanomia toisella taajuudella

lähettää verkkoon kyselypyynnön, johon agentti vastaa ilmoituksella suoraan kyselevälle koneelle

Sanoman reititys vieraassa verkossa olevalle koneelle

Vieras-verkko

FA

MN

HA

Kotiverkko

CN

Normaali IP-reititys

tunnelointi

Vastaus suoraan

FA vierasagentti HA kotiagentti MN liikkuva kone CN kommunikoiva kone

Kotiagentti välittäjänä

Kun paketti lähetetään liikkuvalle,

se ohjautuu IP-osoitteen perusteella kotiverkkoon.

Kotiagentti ottaa paketin itselleen. Se tietää vastaanottajan nykyisen sijainnin ja ohjaa paketin sinne.

Käytetään IP-tunnelointia

uusi osoite COA on usein FA:n valvoma osoite

Uusi IP-otsake alkuperäinen IP-paketti

TCP-otsake + data

Lähde = CD, Kohde =MN Protocol = TCP

Lähde=HA, Kohde= COA, protocol= IP in IP (4)

Toiminta eetteriverkossa

CN

R

HA

MN

CN

R

HA

MN

Normaali reititys

Kotiagentti tunneloi sanoman MN:lle

Kun joku lähettää liikkuvalle paketin

se tulee ensin reitittimelle

reititin kysyy vastaanottajan LAN-osoitetta ARP:illa

jos liikkuva on kotiverkossaan, se vastaa ja ilmoittaa oman koneosoitteensa

muuten kotiagentti vastaa omalla osoitteellaan ja saa paketin

kotiagentti lähettää tunneloinnilla vierasosoitteeseen (yleensä vierasagentin oma osoite)

vierasagentti kysyy ARP:lla vierailijan LAN-osoitetta (‘koneosoitetta’)

Ja lähettää sanoman vierailevalle koneelle.

Ongelma:

CN

R

HA

MN

??

??

On vasta siirtymässä uuteen paikkaan eikä ole vielä ehtinyt ilmoittaa uutta osoitettaan

Vastaanottajaa ei ole enää tässä verkossa => paketit katoavat

FA

Entä jos vierasverkossa ei ole FA:ta?

MN saa tilapäisen IP-osoitteen verkkoon PPP- tai DHCP-protokollalla

käyttäen tätä osoitetta COA-osoitteena se voi itse toimia omana FA:na

Ongelmia:

tunnelointi lisää yleisarasitetta (ylim. IP-otsake) ja viimeinen linkki on hidas radiolinkki

liikkuvat tarvitsevat paljon tilapäisiä IP-osoitteita => osoitteet voivat loppua

poistuva kone ei aina ilmoita lähdöstään

kun kone poistuu, FA katoaa ja matkalla olevat paketit varmasti katoavat

Monilähetys vierasverkossa olevalle koneelle

HA ohjaa yksitellen kaikki lähetykset

tehotonta, voi aiheuttaa turhaa kuormitusta

voi aiheuttaa turhaa monilähetystä

tai sitten sanomaa ei toimiteta MN:lle

FA

MN

HA

Yleislähetys kotiverkossa

tunnelointi

Yleislähetys vierasverkossa

Monilähetys vierasverkossa olevalle koneelle

Jos käytössä verkon FA:aa, niin käytetään kaksoiskapselointia:

HA tietää rekisteröintitiedoista, käyttääkö MN FA:ta vai toimiiko itse oman FA:naan

Source=HA, Dest=COA, Protocol= encaps

Source=HA, Dest=MN, Protocol= encaps

Source=CN, Dest =broadcast, Protocol=UDP

UDP header + data

Uusi IP-otsake kaksoiskapselointi alkuperäinen monilähetys

Järkevämpää tosin olisi rekisteröityä monilähetysryhmään

uudelleen vierasverkossa!!

Mobile IPv6

Osoitteita riittää

vierailijat tarvitsevat IP-osoitteita vierailunsa aikana

Ei tarvita erityistä vierasagenttia

MN toimii yleensä itse omana vierasagenttinaan

neighbor discovery

stateless address autoconfiguration

Paremmat turvallisuuspiirteet

mm. estämään väärennetyt osoitemuutokset ja toistohyökkäykset (replay attack)

Reitin optimointi

turvalaajennoksen avulla MN voi ilmoittaa oman uuden osoitteensa suoraan lähettäjille

binding updates/acks/requests

kolmioreititystä ei tarvitse turvattomuuden takia käyttää

Route Optimization

Tehokkaampi kotiagentin löytäminen

Dynamic Home Agent Discovery

lähetetään Binding Update-sanoma kotiagenteille anycast-osoitteella, jolloin vain yksi ehkä useasta kotiagentista vastaa.

Kotiagentin osoite voi olla muuttunut poissaolon aikana

lähdereititysotsakkeen avulla saadaan tehokas kapselointi

two-hop source route

Filteroivien palomuurien läpäisy

5. Ruuhkan valvonta

yleistä ruuhkan valvonnasta

ruuhkan estäminen

liikenteen tasoittaminen

vuotava ämpäri, vuoromerkkiämpäri

liikennevirran määrittely

ruuhkan säätely

kuorman rajoittaminen

pääsyvalvonta, hidastuspaketit

kuorman purkaminen

pakettien tuhoaminen

Yleistä ruuhkasta

suorituskyvyn rajat

palvelijaketju (reititin, linkki, reititin, …)

ketjun maksimiteho korkeintaan hitaimman palvelijan teho

suoritusteho: sanoma/aikayksikkö

hitain palvelija on pullonkaula

jos hitainta tehostetaan => missä / mikä on uusi pullonkaula?

==>

==>

C1

C2

C4

C3









=> ruuhkaa

jos

ruuhkan valvonta <=> vuon valvonta

ruuhkanvalvonta

verkon selvittävä tarjotusta kuormasta

globaali ongelma

monta lähettäjää, monta vastaanottajaa

vuonvalvonta

lähettäjä ei saa lähettää enempää kuin vastaanottaja pystyy käsittelemään

kaksipisteyhteys

suora palaute vastaanottajalta lähettäjälle

‘open-loop’ control

järjestelmä suunnitellaan sellaiseksi, ettei ruuhkaa synny

uuden asiakkaan hyväksyminen

pakettien hävittäminen

skedulointiperiaatteet

järjestelmän tila ei vaikuta päätöksentekoon

‘closed-loop’ control

palautesilmukka (feed back loop)

seurataan järjestelmän tilaa

puskurien täyttöaste

uudelleenlähetysten lukumäärät, viipeet, viipeiden vaihtelu

ongelman havaitsija ilmoittaa

pakettien alkuperäiselle lähettäjälle, kaikille

reitittimet aktiivisesti kyselevät

nopeampi reagointi mahdollista

lähetyskäyttäytymisen muuttaminen ruuhkan vähentämiseksi

liian hidas reagointi => ruuhka kasvaa

liian nopea reagointi => heiluriliikettä

Toiminnan säätö ruuhkatilanteessa

lisää kapasiteettia

kiintiön nostaminen

varajärjestelmän käyttö

vähennä kuormaa

ei uusia käyttäjiä, huonompi palvelu, jne

sopii hyvin virtuaalipiireihin

virtuaalipiirit =>verkkokerroksella

datasähkeet => kuljetuskerroksella

Ruuhkanvälttämispolitiikat

siirtoyhteyskerros

uudelleenlähetyspolitiikka

epäjärjestyksessä saapuneiden talletuspolitiikka

kuittauspolitiikka,

vuon valvontapolitiikka,

verkkokerros

virtuaalipiiri <=> tietosähke

pakettien jonotuspolitiikka

pakettien poistamispolitiikka

reititysalgoritmi

pakettien elinikä

kuljetuskerros

uudelleenlähetyspolitiikka

epäjärjestyksessä saapuneiden talletuspolitiikka

kuittauspolitiikka

vuon valvontapolitiikka

ajastinaikojen asetukset

Päästäpäähän ruuhkanvalvonta (end-to-end)

TCP käyttää

Kaikki tieto lähettäjän ja vastaanottajan välillä

Verkkokerros ei anna mitään lisätietoa eikä avusta ruuhkanvalvonnassa

IP-kerros ei välitä ruuhkainformaatiota

Poikkeuksena ehdotettu ECN ja RED-jono

Verkonavustama ruuhkanvalvonta

Reitittimet antavat lähettäjille tietoa verkon ruuhkautumisesta

Yksittäinen bitti kertoo ruuhkasta linkissä

Reititin kertoo, millä nopeudella linkillä voi lähettää

Tieto voidaan lähettää suoraan lähettäjälle

Hillintäpaketti (Choke packet)

tai liittää se vastaanottajalle menevään pakettiin

ECN-ehdotus

Hitaaampi tapa

Atm ABR ruuhkanvalvonta

ABR (available bit rate)

Atm-soluja (‘pieniä paketteja’) kuljetetaan lähettäjältä vastaanottajalle useiden kytkimien (‘reitittimien’) läpi.

Soluvirrassa on datasolujen lisäksi erityisiä hallintasoluja RM-soluja

Välittävät mm. ruuhkaan liittyviä tietoja reitittimien ja isäntäkoneiden välillä

Tieto ensin vastaanottajalle

RM

RM

RM

RM

RM

RM

RM

RM

RM

Tieto suoraan lähettäjälle

RM

RM

RM

Lähetysnopeuteen perustuva

sovitaan tietystä lähetysmäärästä

vastaanottajalle tietoa ruuhkasta

EFCI-bitti (explicit forward congestion indication bit)

ilmoittaa vastaanottajlle ruuhkasta;

ruuhkautunut reititin asettaa

vastaanottaja lähettää ruuhkasta kertovan RM-solun lähettäjälle

(CI-bitti (congestion indication) asetettuna)

RM-solun CI -ja NI -bitit (no increase)

reititin asettaa: NI-bitti = lievä ruuhka

CI-bitti = vakava ruuhka

vasataanottaja palauttaa RM-solun lähettäjälle

RM-solun ER-kenttä kertoo todellisen siirtonopeuden ruuhkainen reititin voi asettaa kentän arvon pienemmäksi

kaikille rreitin reitittimille alempimarvo

Liikenteen tasoitus (traffic shaping)

liikenne tyypillisesti purskeista

juuri purskeisuus aiheuttaa ruuhkaisuutta

tasoitetaan liikennevirtaa puskurilla

puskuri toimii jonona

vuotava ämpäri

vuoromerkkiämpäri

liikennevirran määrittely

määrittelee asiakkaan oikeudet ja velvollisuudet

Vuotava ämpäri (leaky bucket)

purskeisuutta tasoittaa iso puskuri, josta liikenne valuu tasaisesti

‘vuotava ämpäri’

yksi tavu / yksi paketti lähtee jossain aikayksikössä, jos on lähetettävää

jos datapurske mahtuu puskuriin, se aikanaan pääsee matkaan

äärellinen jono

yläraja saapumistiheydelle

Vuoromerkkiämpäri (Token bucket)

lähettäminen vaatii vuoromerkin

vuoromerkkejä generoituu tasaisella nopeudella

jos ei lähetettävää, merkkejä jää säästöön

korkeintaan niin paljon kuin ämpäriin mahtuu

=> sallii rajoitetut ‘minipurskeet’

joustavampi kuin vuotava ämpäri

purskeet voivat aiheuttaa ruuhkaa => vuotava ämpäri vuoromerkkiämpärin perään

Liikenteen määrittely (flow specification)

sovitaan liikennevirrasta yhteyttä muodostettaessa

asiakas esittää kuorma- ja palvelutoiveet

palvelija: ok/ ei käy/ vastaehdotus

pyydetty palvelu

pakettien katoamisen sietokyky (loss sensitivity): missä määrin asiakas sietää pakettien tuhoamista

viiveherkkyys (delay, delay variation)

takuu: onko toive vai ehdoton vaatimus

asiakas ei aina tiedä mitä todella haluaa

Virtuaalikanavan ruuhkanvalvonta

pääsynvalvonta (admission control)

jos ruuhkaa, ei uusia virtuaalikanavia

uusi kanava ok, jos kiertää ruuhka-alueen

virtuaalikanavaa avattaessa

sovitaan liikennekuormituksesta ja palvelun laadusta

verkosta varataan tarvittavat resurssit

resurssien varaus

milloin varataan, paljonko varataan

liikenne on purskeista

turha varaus tuhlaa resursseja

hidastuspaketti (choke packet)

voidaan käyttää kaikenlaisissa verkoissa

reititin tarkkailee kuormitusta

ulosmenolinjojen käyttöastetta

jonopituuksia

esim

Unew = aUold + (1-a)f

a kuinka nopeasti aikaisempi historia unohtuu

f kuormitettu vai ei ( o tai 1)

jos liikaa kuormaa, reititin huolestuu

lähettäjälle hidastuspaketti

lähettäjä hidastaa lähetystään

vähentää ensin puoleen

ja sitten taas puoleen

perustuu vapaaehtoisuuteen

reilu jonotus

useita kynnysarvoja

lievä, vakava, erittäin vakava varoitus

muita ruuhkan ‘mittoja’

jonon pituus

puskurikäyttö

Hidastuspaketin ongelmia:

lähettäjän hidastus vapaaehtoista

reilu jonotus:

kullakin lähettäjällä oma jono jokaiseen ulosmenolinjaan

A

B

C

Lähetetään vuorotellen eri jonoista.

Hidastuspaketin vaikutuksen hitaus pitkillä linjoilla

Ratkaisu:

ei pelkästään lähettäjälle

myös välissä olevat reitittimet alkavat hidastaa

Kuorman kevennys (Load Shedding)

tuhotaan paketteja => kuorma kevenee

reititin täyttyy:

mitä paketteja tuhotaan?

11

10

9

8

reititin

7

6

13

12

FTP: tuhotaan 8 => paketit 8-11 uudelleen

tuhotaan 11 => paketti 11 uudelleen

video: ?

riippuu sovelluksesta

viini: vanha parempi kuin uusi

maito: uusi parempi kuin vanha

eriarvoiset paketit

perusdata/muutokset

teksti / kuva

käyttäjä ilmoittaa prioriteetin

arvokkaita ei tuhota

prioriteetin käytön valvonta: hinta/sallitun lähetysmäärän ylittävät paketit

paketti tuhottu, entä sanoma

mitä tehdään ko. sanomalle

Vuopohjainen reititys (Flow-Based Routing)

viive = jonotusaika + siirtoaika

etsitään pienin mahdollinen viive koko verkolle

tunnettava

verkon topologia

kapasiteettimatriisi

eri linkkien kapasiteetti

liikennematriisi

eri solmujen välinen liikenne

alustava reititys

lasketaan

kunkin linjan kuormitus i

keskim. pakettien määrä kullakin linjalla Ci

keskim. pakettikoko = 1/esim. 800 bittiä)

keskim viive kullekin linjalle

T = 1/( C - ) (jonoteoriasta)

1/ = keskim. paketin koko bitteinä

C = kapasiteetti bps

 = keskim. pakettivirta (kuormitus)

paketteina sekunnissa

koko verkon viive

painotettu keskiarvo eri linkkien viipeistä

painotuksena linkin osuus koko liikenteestä

eri reititysalgoritmien vertailu

lasketaan erikseen kaikille reititysvaihtoehdoille

mahdollinen, vaikka raskas

valitaan ‘paras’

edellyttää kuormituksen pysyvän melko samanlaisena

ei oikein sovellu koko ajan muuttuvaan verkkoon

Piirikytkentäisten verkkojen reititys

lyhyin polku (Shortest path first) (ABD tai ACD)

vähiten kuormitettu polku (Least loaded path) (ABCD)

eniten vapaita piirejä omaava polku (Maximum free circuit)

(ABD)

35/70

5/20

19/20

1/19

6/20

B

D

A

C

A/B

B = linkin kapasiteetti

A= siitä käytössä

oleva osuus,

esim. piirien määränä

Piirikytkentäisissä verkoissa

kaikki reitittimet tietävät kaikkien linkkien tilan

linkkitilatyyppinen reititys

tietojen oikeellisuus ja ajantasaisuus tärkeää

37/70

5/20

19/20

2/19

6/20

B

D

A

C

10/10

3.7. Internetin reititysprotokollista

AS (autonomous system)

reititys AS:n sisällä (Interior routing protocols)

RIP (Routing Information Protocol), RIP2, RIPng

etäisryysvektorireititysprotokolla

OSPF (Open Shortest Path First)

linkkitilareititysprorokolla

reititys AS:ien välillä (Exterior gateway protocols)

BGP (Border Gateway Protocol)

Reititys (Routing)

Verkkokerroksen tehtävänä on toimittaa data (paketit) lähettäjän koneelta vastaanottajan koneelle

Välissä voi olla hyvin monimutkainen monista erilaisista aliverkoista koostuva verkko.

Internet, jossa miljoonia reitittimiä ja yli sata miljoonaa konetta, eri yritysten omistuksessa

2.11.2000: 100. miljoonas ‘host’

Miten tämä saadaan aikaiseksi?

Autonominen järjestelmä (AS)

Internet on kokoelma ‘itsenäisiä’ aliverkkoja eli autonomisia järjestelmiä (AS, Autonomous System)

yli 700 AS:ää 1994

joita yhdistää runkolinjat

AS:n sisällä IGP (Interior Gateway Protocol)

OSPF tai RIP

alueiden välillä EGP (Exterior Gateway Protocol)

BGP (Border Gateway Protocol)

AS 1

AS 2

AS 3

AS 4

AS 5

AS 0

Internet koostuu autonomisista systeemeistä AS (autonomous system), jotka yhdistetty runkolinja-alueella.

Hierarkkinen reititys

reitityksen skaalautuvuus

isossa verkossa runsaasti reitittimiä

reititystaulut suuria

reittien laskeminen raskasta

tietopaketit kuluttavat linjakapasiteettia

hierarkiaa

jaetaan verkko ja sen reitittimet autonomisiin osiin

AS (autonomous system)

yritysten ja organisaatioiden omat verkot

“A set of routers and networks under the same administration.”

Kullakin AS:llä on oma 16-bittinen AS-numero.

Yhden AS:n sisällä

reitittimet käyttävät samaa reititysprotokollaa

OSPF, RIP,…

Tärkeää on tehokkuus

kukin reititin tuntee kaikki muut tämän AS:n reitittimet ja saa niiltä reititystietoja

tietää mikä reititin tai mitkä reitittimet (gateway router) hoitavat liikenteen muihin AS:iin

AS:n yhdysreitittimet

AS:ien välillä

yhdysreitittimet vaihtavat reititystietoja eri AS:ien välillä

käyttäen toisenlaista reititysprotokollaa

esim. BGP (Border Gateway Protocol)

Muut seikat kuin tehokkuus ovat tärkeämpiä

Toimintapolitiikkaan liittyvät

Luotettavuus ja turvallisuus

Lait ja määräykset

kustannukset

AS:ien alueet

Monet AS:t ovat usein hyvin laajoja

=> voidaan jakaa alueiksi (areas)

verkko tai verkkojoukko

alueen ulkopuolella sen topologia ei näy

jokainen alue laskee omat reititystietonsa

sama algoritmi, mutta eri kopio ja eri tilatiedot

jokaisessa AS:ssä runkolinja-alue

alue 0

kaikki alueet kiinni runkolinjassa ja liikenne alueelta toiselle käy aina runkolinjan kautta

AS 1

AS 2

AS 3

AS 4

AS 5

AS 0

Iso AS voi koostua useasta alueesta.

Erilaisia reititintyyppejä

sisäinen reititin

alueen sisäisiä

alueen reunareititin

sekä alueessa että runkolinjassa

runkolinjareititin

runkolinjaan kuuluvia

AS:n yhdysreititin

runkolinjan reitin, joka on yhteydessä muiden AS:ien reitittimiin

Area 1

Area 2

Area 3

Alueiden sisäisiä reitittimiä

Alueen reunareititin

Runkolinjareitittimiä

AS-yhdysreititin

Reitittimien toiminta

Alueen sisällä kaikilla reitittimillä

sama linkkitilatietokanta

sama lyhimmän polun algoritmi

reititin laskee lyhimmän polun kaikkiin muihin alueen reitittimiin

Alueiden välillä

reitittimillä on useita kopioita samasta reititysalgoritmista

yksi kutakin aluettaan varten

AS:ien välillä

AS:eissä voidaan käyttää erilaisia reititysprotokollia

linkkitilareititystä tai etäisyysvektorireititystä

eri metriikat

erilaiset tavat kerätä ja vaihtaa tietoja

tarvitaan jokin yhteinen reititysptotokolla, jolla yhdysreitittimet voivat vaihtaa reititystietoja

esim. BGP

Reitittimien toiminta

reititin

tulvittamalla tai vaihtamalla tietoja naapureittensa muiden välittää alueensa kaikille muille reitittimille

naapurinsa

kustannustiedot (monta erilaista)

joko suoraan tai välittäjäreitittimien avulla

muodostaa etäisyysverkon ja laskee lyhimmät reitit

alueensa /alueittensa sisällä

runkoverkon reititin lisäksi

saa alueiden reunareitittimiltä tietoja, joista laskee parhaat reitit runkoverkon reitittimistä kaikkiin muihin reitittimiin

palauttaa tiedot reunareitittimille, jotka levittävät ne alueensa sisäisille reitittimille

alueen sisäinen reititin

reititys alueen sisällä

alueiden välillä => sopiva runkoverkon reititin

AS:n rajareititin

vaihtaa reititystietoja muiden AS:ien rajareitittimien kanssa

välittää muille reitittimille

AS:ien välillä käyttää BGP-reititystä

A

B

C

D

A, B, C ja D

välittäjäreittimiä

L1

L2

L3

A:n viereiset reitittimet:

kaikki L1: n reitittimet, B ja D

Hierarkkinen

reititystietojen

vaihto

B:n viereiset reitittimet: kaikki L2:n

reitittimet, A ja C

C: osa L3:n reititti-

mistä, D ja B

D: loput L3:n reitittimistä, C ja A

A

B

C

D

L1

L2

L3

ra

rb

rc

rd

re

ra mittaa etäisyydet naapureihinsa

rb:hen ja rd:hen ja lähettää tiedot

A:lle

A saa tiedot etäisyyksistä

kaikilta L1:n reitittimiltä

ja välittää tiedot

muille =>

ra osaa laskea

etäisyydet muihin

L1:n reitittimiin

A saa myös tiedot

muiden alueiden

etäisyyksistä B:ltä

ja D:ltä

==> ra:lle =>

ra tietää kumpaa

reititintä rb vai rd

tulee kulloinkin

käyttää

E

E on AS-yhdysreititin, joka tietää reitit muihin AS:iin

tarvitaan kolmenlaisia reittejä

alueen sisäisiä

reititin itse tietää lyhyimmän reitin

alueiden välisiä

alueiden väliset reitit kulkevat aina runkolinjaa pitkin

reititin tietää lyhyimmän reitin runkolinjaan alueeseen

AS:ien välisiä

Näistä huolehtivat AS-yhdysreitittimet

esim. BGP-protokollalla

AS-yhdysreitittimet tietävät reitin muihin AS:iin

yleensä AS-runkolinjan kautta

Yleisesti käytetyt reititysalgoritmit

Etäisyysvektorireititys (Distance Vector Routing)

ARPA-verkon alkuperäinen reititysalgoritmi

Internetin RIP-algoritmi

Ciscon IGRP ja EIGRP (mm. useita eri kustannusmittoja)

linkkitilareititys (Link State Routing)

ARPA-verkon reititysalgoritmi vuodesta 1979

Internetin OSPF-algoritmi

ISO:n IS-IS (Intermediate System to Intermediate System)

“IS-IS = 0”

Etäisyysvektorireititys

Solmut vaihtavat informaatiota vain naapuriensa kanssa

Eri solmuilla eri näkemys verkosta

hyvät uutiset etenevät nopeasti, huonot hitaasti

count- to-infinity,

simple split horizon : ei ilmoita naapurille sen kautta meneviä parhaita reittejä

Split horizon with poisoned reverse" ilmoittaa, mutta merkitsee ne äärettömiksi.

ratkaisu ei toimi aina

A

B

C

D

Linkki CD katkeaa,

A ja B ilmoittavat C:lle

ettei D:hen pääse

C päättelee, että D:tä ei

voi saavuttaa

Kuitenkin A kuulee B:ltä,

että sillä on etäisyys 2 D:hen => oma etäisyys 3

x

RIP-reititysprotokollia

RIP

etäisyysvektorireititys

autonomisen alueen sisäinen protokolla

naapurit vaihtavat reititystietoja keskenään

Counting to Infitity

Split Horizon

Triggered Updates

RIPv1

RIPv2

RIPng

RIP-1 (RFC 1058)

joka linkillä kustannus 1

hyppyjä: 1-15 hyppyä

maksimi 15 => korkeintaan 15 hypyn matka mahdollinen

reititystietojen vaihto naapureiden kanssa

RIP response message (advertisement)

yleislähetyksenä (broadcast), jos mahdollista

n. 30 s välein. Jos naapuri ei lähettele 180 s sisällä, linkin oletetaan olevan poikki.

UDP-protokollaa käyttäen

RIP on toteutettu sovelluskerroksen prosessina ja siis sovelluskerroksen protokolla, joka käyttää UDP-porttia 520 sanomien lähettämiseen ja vastaanottoon

RIP-sanoman muoto

Command version 0

Address family identif. = 2 0

IP address

0

0

metric

0 …..… … 8…………… 16 … … 31

Command = sanoman tyyppi: 1= pyyntö (request), 2 = vastaus (response) Address family identifier = peruja UNIX-BSD:ssä käytetystä osoitustavasta; ajatuksena toteuttaa RIP muihin osoitusmuotoihin (esim. X.25, XNS) metric = kustannus hyppyinä ; max. = 16 eli ääretön

RIP-entry

RIP:n toiminta

Normaalisti lähetetään vastauksia

30 sekunnin välein

kun omassa taulussa muutoksia

peräkkäisetei muutokset vasta 1-5 sekunnin kuluttua, jotta ei syntyisi ‘päivitystulvaa’

Reititin käsittelee saamansa vastaukset yhden kerrallaan

Kohteen osoite etäisyysmitta seuraava reititin äsken päivitetty useita ajastimia

192.55.2.5 10 193.46.4.8 U(ppdated) 26, 12, …… ….. …… …... …..

Yhdessä sanomassa korkeintaan 25 alkion tiedot (512 tavua)

tarvittaessa useita peräkkäisiä sanomia

Reititystietopyyntö, kun reititin aloittaa toimintansa

koko reititystaulun sisältö

0.0.0.0 osoitteena (default osoite) ja kustannuksena ‘ääretön’

normaali operaatio

tietyt reitit

kyselyssä ilmoitettuihin osoitteisiin

lähinnä vikojen selvittämisessä

RIP-2 (RFC 2453)

tehokkaampi koodaus

ei turhien nollakenttien lähettämistä

aliverkkoreititys

RIP-1: aliverkot eivät näy ulospäin

RIP-2: aliverkkomaski osoitteen mukana => CIDR

autentikointi

RIP-1 luotti porttiin 520, jota sai käyttää vain etuoikeutettu käyttäjä

RIP-2: ensimmäinen alkio voi olla autentikointisegementti

Next Hop, monilähetys

RIP-1: yleislähetys

RIP-2-sanoman otsake

Command version 0

Address family identif. Route Tag

IP address

Subnet Mask

Next Hop

metric

0 …..… … 8…………… 16 … … 31

RIP-entry

….

- Subnet Mask = aliverkkojen käsittelyyn verkon ulkopuolella

Next Hop -kenttä

A B C

D E F

Ethernet-kaapeli tms.

AS X

AS Y

Ongelma: A:lta paketti F:lle: - ensin D:lle - joka siirtää F:lle eli paketti kulkee kaksi kertaa samaa kaapelia!

Ratkaisu: D ilmoittaa kustannuksen lisäksi suoraan seuraavan kohteen (next hop)

(‘Kustannus D:n kautta F:ään on xyz, mutta paras lähettää suoraan E:lle.’)

RIP-2: sanoman autentikointisegmentti

Command version Routing Domain

0xFFFF AuthenticationType

Autentikointidataa

0 …..… … 8…………… 16 … … 31

1. RIP-entry

….

salasana selväkielisenä tai salakirjoitettuna (RFC 2082)

myös tehokkaampia suojauksia

RIPng (RFC 2080) ja muita parannuksia

RIP-protokollan käyttö IPv6:n kanssa

parannetut turvapiirteet

Käytössä IPv6 turvapiirteet

päivitystahdistumisen estäminen

päivitysten kuittaukset => vähemmän lähettämistä

useiden eri kustannusmittojen käyttö

“count-to-infinity”-ongelma

‘source-tracing’-algoritmi, joka etsii silmukat iteratiivisesti

‘turhaa hyvän ja yksinkertaisen protokollan monimutkaistamista?’

Linkkitilareititys

Globaali reititysalgoritmi

Kullakin reitittimellä käytössään koko verkon informaatio

tästä lasketaan hajautetusti tai keskitetysti parhaat reitit

monimutkainen algoritmi

=> paljon laajempi standardi

Linkkitilareititys (Link State Routing)

reitittimen tehtävät

selvitettävä naapurit ja niiden osoitteet

mitattava etäisyys / kustannus naapureihin

koottava tietopaketti ko. tiedoista

lähetttävä tietopaketti kaikille reitittimille

laskettava lyhin reitti kaikkiin muihin reitittimiin

kyseessä maailman laajuinen verkko

kaikki häiriöt sattuvat

joskus ja jossain

vikasietoisuus

ongelmia

väärin toimiva reititin

kertoo vääriä tietoja

ei välitä tietopaketteja

väärentää tietopaketteja

laskee reitit väärin

isossa verkossa aina joku toimii väärin

tavoitteena rajata ongelmat pienelle alueelle

OSPF (Open Shortest Path First)

linkkitilaprotokolla

tavoitteet:

avoin (eli julkinen)

erilaisia eäisyysmittoja

dynaaminen algoritmi

myös palvelutyyppiin (TOS) perustava reititys

kyettävä kuorman tasoittamiseen ja usean reitin käyttämiseen

hierarkkinen reititys

suojauspiirteitä

myös tunneloinnilla yhdistetyt reitittimet

eri reitit voivat olla ‘yhtä pitkiä’

=> liikenne voidaan reitittää usean reitin yli

=> kuormituksen tasapainoitus

eikä välttämättä kaikkia paketteja lähetetä samaa reittiä

osa parasta reittiä

osa toiseksi parasta

lopputulos voi olla parempi

OSPF:n käyttöalueet:

kahden reitittimen välinen kaksipisteyhteys

monen reitittimen yleislähetysverkot

esim. useimmat lähiverkot (LAN)

monen reitittimen verkot, joissa ei ole yleislähetystä

useimmat laajaverkot (WAN)

Verkosta tehdään malli (suunnattu verkko)

reitittimet ja verkot solmuina, niiden väliset linjat kaarina

kaarilla kustannuksina etäisyys, kustannus, luotettavuus

multiaccess-verkkoa vastaa oma solmu, josta kustannus reitittimeen on nolla

mallilla lasketaan lyhyin reitti kaikkien reititinparien välille

eri etäisyysmitoille omat reitit

OSPF:n toiminta

reititystietojen vaihto

linkkitilaviestejä säännöllisin väliajoin ja topologian muuttuessa

viestit tulvitetaan, viestit numeroidaan, viestit kuitataan

viestit ohjataan valitulle (designed) välittäjäreitittimelle

kommunikoi LAN:n tai alueen muiden reitittimien kanssa; kerää tiedot ja välittää ne eteenpäin

jokainen reititin ei lähetä jokaiselle, vaan omalle välittäjäreitittimelleen

vähentää viestien määrää: n(n-1)/2 ==> 2(n-1), jos n =20, niin 20*19/2 = 190 ja 2*19 = 38!

Välittäjäreititin

Välittäjä valitaan Hello-protokollalla

välittäjäreititin vähentää tulvituspaketteja

riittää ensin lähettää monilähetyksenä välittäjäreitittimille

osoite 224.0.0.6=> kaikille välittäjäreitittimille

tarvittaessa välittäjäreititin monilähettää kaikille OSPF-reitittimille (224.0.0.5)

Entä, kun välittäjäreititin kaatuu?

valitaan myös varavälittäjä, joka vastaanottaa monilähetyspaketteja, mutta ei vastaa mihinkään

välittäjän kaatuminen havaitaan Hello-protokollalla

OSPF-sanomat

hello

naapurien selvillesaaminen

link state update

omien linkkikustannusten lähettäminen

link state ack

vastaanotettujen linkkikustannusten kuittaus

database description

tietokannan ajantasaisuuden selvittäminen

link state request

toisen linkkikustannusten kysyminen

OSPF-paketin otsake

Versio # type packet length

Router ID

Area ID

Authentication

Authentication

Checksum Autype (= Autentikointialgoritmi)

Hello-paketti

OSPF packet header, type = 1 (hello)

Network mask

Hello interval options priority

Dead interval

Designated router

Backup designated router

Neighbor

Neighbor

Hello-paketin kentät

Network mask = liitäntäkortin aliverkkomaski

Hello interval = hello-sanomien lähetysväli

Options:

T-bitti => TOS-reitityskykyinen

E-bitti = ulkoisten reittien vastaanotto ja lähetys

Priority: reitittimen prioriteetti 0-255

välittäjäksi korkeimman prioriteetin reititin;

jos sama arvo usealla, niin suurin ID-numero valitaan

Dead interval

jos tässä ajassa ei tule hello-sanomaa, merkitään ‘kuolleiden’ listaan

Hello-paketin kentät jatkuvat

Designated router

Backup desigated router

reititin ilmoittaa haluavansa toimia välittäjäreitittimenä tai varavälittäjäreitittimenä

valintaa suoritetaan jatkuvasti ja joka hello-sanomassa

reititin muistaa, ketkä ilmoittautuneet välittäjiksi

BGP (Border Gateway Protocol) (RFC 1771)

AS:ien välillä

otettava huomioon eri AS:ien politiikat

AS:ien sisällä tärkeintä tehokkuus

AS:ien välillä toimintapolitiikka

kieltoja tai suosituksia reitittää tiettyjen AS:ien kautta

politiikat manuaalisesti BGP-reitittimiin

hyvin erilaisia sääntöjä: politiikka, turvallisuus, taloudellisuus

‘Kanadasta Kanadaan ei saa lähettää USA:n kautta.’

‘AS xyz ei hyväksy transit-liikennettä.’

‘Pentagonista lähteviä paketteja ei reititetä Irakin kautta.’

‘Viikonloppuisin käytetään reittiä abc.’

BGP (jatkuu)

pohjimmiltaan etäisyysvektoriprotokolla

polkuvektori

tallettaa kunkin reitin koko polun

ei kustannustietoja, vaan polulla olevat AS:t

havaitaan mahdolliset silmukat!

kertoo naapureilleen käyttämänsä reitin

hylkää itsensä kautta kulkevat reitit, jotta ei synny silmukoita

keino välittää reitti-informaatioita

ei määrää, kuinka reiteistä valitaan oikea reitti

kukin AS voi valita reittinsä, miten haluaa

BGP näkee verkon joukkona AS:iä

jokaisella AS:lla oma tunnus (ASN)

reitittimellä on reititystaulussaan reittejä sen tuntemiin AS:iin

esim. AS X:ään , Y:hyn ja Z:aan

B D F X

B G I K X

F C A H P Y

S Y

E C A Z

BGP:n toiminta

reitti-ilmoitusten vastaanottaminen naapureilta (’lupauksia’)

silmukoiden poistaminen

ei-toivotut AS:t

reitin valinta

reititysmekanismi  reitityspolitiikka

politiikkaratkaisut hallinnon asia

Reitti-ilmoitusten lähettäminen naapureille

Mitä kellekin ilmoitetaan

Reittien salaaminen

M

H

J

J

M ei kerro H:lle reittiä itsensä kautta

M kertoo kyllä J:lle

ja J kertoo H:lle

BGP-sanomat

OPEN

‘esittelysanoma’: tunnus + autentikointitiedot (vrt. OSPF:n Hello) ja ajastintietoja

KEEPALIVE

lähettäjä ‘elossa’, mutta sillä ei ole mitään lähetettävää

toimii myös kuittauksena OPEN-sanomalle

UPDATE

ilmoitetaan uusia reittejä ja poistetaan vanhoja

NOTIFICATION

ilmoitus virheestä

ilmoitus BGP-istunnon lopettamisesta

Sanomien lähettämiseen käytetään TCP:tä

ruuhkavalvonta, hidas aloitus

sanomille korkea prioriteetti

muutospäivitykset = lähetetään vain muutokset

Reittien valinta

arvioidaan reitit: ‘local preferance’ -metric

kielletyt AS:t

epävarmat tai saavuttamattomat yhteydet

polun AS:ien määrä jne.

valitaan sopivin reitti

ilmoitetaan paras reitti AS:n muille reitittimille

I-BGP

Edellä esitelty E-BGP (External-BGP)

Tarvitaan myös I-BGP (Internal-BGP)

Kertoo AS:n sisällä reitit muihin AS:iin

Voidaan toteuttaa myös oletusreiteillä

I-BGP:t AS:n sisällä toistensa ‘naapureita’

= vaihtavat tietoja keskenään

Rajoituksia sille, mitä reittejä saa ilmoitella muille

4.2 Monilähetysreititys

Paketti lähetetään usealle vastaanottajalle

Miksi?

Monet sovellukset hyötyvät

ohjelmistopäivitykset

WWW-välimuistien päivitykset

etäopetus, virtuaalikoulu

videoiden, äänitteiden lähetys

interaktiiviset pelit

Mitä hyötyä?

Nopeus, tehokkuus

paketti monelle vastaanottajalle

useita kaksipistelähetyksiä: kaikille oma paketti

tulvitus

multidestination routing: kohteet lueteltu paketissa, reititin kopioi kaikkiin tarpeellisiin ulosmenoihin

lähettäjän virittävä puu (spanning tree)

ei silmukoita

yhteinen tai jokaiselle lähettäjälle oma puu

reverse path -algoritmi (käänteinen polku)

estimoi virittävää puuta

Monilähetys

Monilähetysryhmä

ryhmäosoite (Luokan D osoite)

vastaanottajaryhmän hallinta

ryhmien muodostus, poistaminen

vastaanottajien lisääminen, poistaminen

Monilähetyksen reitittäminen

reitittimet tietävät ketkä kuuluvat mihinkin ryhmään

laskevat lyhimmät reitit vastaanottajiin

ohjaavat reititystaulujensa avulla paketit vastaanottajille

IGMP (Internet Group Management Protocol) (RFC 2236)

Monilähetysryhmien hallinta

IGMP isäntäkoneen ja sen lähimmän reitittimen välillä

isäntäkone ilmoittaa itsensä jäseneksi tiettyyn ryhmään

isäntäkone poistaa itsensä ryhmästä

monilähetysreititysalgoritmi

reitittimien välillä monilähetysten koordinoimiseksi

esim. PIM, DVMRP, MOSPF

huom! ryhmän isäntäkoneiden välillä ei ole mitään protokollaa

eivät tiedä, ketkä muut kuuluvat ryhmään

D-osoitteet

monilähetykset D-osoitetta käyttäen

28 bittiä => yli 250 miljoonaa ryhmäosoitetta

perilletoimitus ‘best effort’

pysyviä ryhmiä

224.0.0.1 kaikki lähiverkossa

224.0.0.2 kaikki reitittimet lähiverkossa

224.0.0.5 kaikki OSPF-reitittimet lähiverkossa

224.0.0.6 kaikki ‘designated’ OSPF-reitittimet

lähiverkossa

tilapäisiä ryhmiä

IGMP:n toimintaperiaate

kysely/vastaus

monilähetysreitittimet kyselevät

noin minuutin välein kysyvät kaikilta koneiltaan, mihin ryhmiin kuuluvat

224.0.0.1-osoitteella

koneet vastaavat

ilmoittamalla kaikkien niiden ryhmien D-osoitteet, joihin jokin niiden sovellus on liittynyt

host

router

kysely

vastaus

IGMP-sanomat

Membership query

general: mihin ryhmiin kuuluvia?

specific: onko tiettyyn ryhmään kuuluvia?

Kyselyillä maksimivastausaika

Membership report

kone haluaa liittyä tai on liittynyt ilmoitettuun ryhmään

Leave group

kone ilmoittaa poistuvansa ryhmästä

vapaaehtoinen!

Jos ei vastaa kyselyihin, ei ole enää mukana

=> jäsenyyden voimassaololle aikaraja

IGMP-sanoma

Type max. response checksum

time

Multicast Group Address

Type = mikä sanoma kyseessä

max. response time = maksimivastausaika kyselyissä

Checksum = taskistussumma

Multicast Group Address = monilähetysryhmän osoite

Maksimivastausaika?

Optimointia varten, esim. LAN-verkoissa, joissa kaikki kuulevat kaikki sanomat

reititin haluaa tietää vain onko kukaan sen LANin koneista kiinnostunut tietystä ryhmästä

ei sitä ketkä koneista haluavat ryhmän jäseniksi

ei edes montako sen koneista on tietyn ryhmän jäseninä

koneet vastaavat satunnaisen ajan kuluttua

jos joku muu kone jo vastannut, ei enää vastaa

=> vastausten määrä pienenee

Internetin monilähetyspalvelumalli

Kone ilmoittaa omalle reitittimelleen haluavansa liittyvä tiettyyn ryhmään

IGMP:n membership_report-sanomalla

Reitittimet alkavat välittää koneelle tämän ryhmän viestejä

vastaanottajavetoinen (receiver-driven)

Lähettäjä ei pidä kirjaa ryhmän jäsenistä eikä tiedä kenelle kaikille viesti menee.

Kuka tahansa voi toimia lähettäjänä

eri lähettäjien sanomat tulevat sekaisin

Monilähetysosoitteita ei koordinoida verkkotasolla

eri ryhmille voidaan valita sama osoite

Monilähetysreititys (multicast routing)

Ongelma:

Reitittimien on kyettävä rakentamaan ‘optimaaliset’ reitit ryhmän kaikille vastaanottajille

kun mikä tahansa kone voi toimia lähettäjänä

ryhmään voi kuulua eri määrä vastaanottajia

lähes kaikki isäntäkoneet

vain muutama isäntäkone

ryhmän jäsennyys voi olla hyvin dynaamista

Tavoitteena on löytää mahdollisimman optimaalinen linkkipuu, joka yhdistää kaikki ryhmän jäsenet

sanomien reititys puun linkkejä pitkin

A

B

C

D

F

E

A, B, E ja F: reitittimillä ryhmän jäseniä

C ja D: reitittimillä ei ole ryhmän jäseniä

Monireitityspuun rakentaminen

Kaksi erilaista lähestymistapaa

yksi puu koko ryhmälle (group shared tree)

kuka tahansa toimii lähettäjänä, niin reitityksessä käytetään samaa puuta

jokaiselle lähettäjälle oma puu (source-based tree)

jos ryhmässä on n jäsentä, niin muodostetaan n eri puuta

jokaisen lähettäjän sanomat reititetään sen oman linkkipuun avulla

Yksi puu koko ryhmälle

A

B

C

D

F

E

A, B, E ja F: reitittimillä ryhmän jäseniä

C ja D: reitittimillä ei ole ryhmän jäseniä

reitityslinkki

Eri lähettäjille omat puut

A

B

C

D

F

E

A, B, E ja F :reitittimillä ryhmän jäseniä

C ja D: reitittimillä ei ole ryhmän jäseniä

A:n lähettäessä

B:n lähettäessä

Reititys käyttäen yhtä puuta koko ryhmälle

Löydettävä puu, joka yhdistää kaikki ryhmän reitittimet

mukana myös muita reitittimiä

puun kustannus on sen linkkien kustannusten summa

pienimmän kustannuksen puu

NP-täydellinen ongelma (Steiner tree problem)

suht.koht. hyviä heuristisia ratkaisuja on

ei ole käytössä Internetissä

tiedettävä kaikki kaikki linkkikustannukset

kustannusten muuttuessa laskettava uudelleen

jo muutenkin laskettujen kustannusten hyödyntäminen

Pienimmän kustannuksen monilähetyspuu

A

B

C

D

F

E

A, B, E ja F: reitittimillä ryhmän jäseniä

C ja D: reitittimillä ei ole ryhmän jäseniä

3

4

1

1

2

2

1

2

Keskuspohjainen reititys (Center-based routing)

Ryhmän puun keskuksena on jokin solmu, johon muut myöhemmin liittyvät

ensin saadaan selville keskussolmu

muut liittyvät siihen JOIN-sanomilla

yksilähetyksiä keskussolmulle

Miten keskussolmu valitaan?

Valitaan siten, että puu on melko lähellä optimia

Keskuspohjainen monilähetyspuu

A

B

C

D

F

E

A, B, E ja F: reitittimillä ryhmän jäseniä

C ja D: reitittimillä ei ole ryhmän jäseniä

3

4

1

1

2

2

1

2

G

1.

2.

3.

Ratkaisevaa on keskussolmun järkevä valinta

Jokaiselle lähettäjälle oma puu

Tavallisessa reitityksessä jo yleensä lasketaan pienimmän kustannuksen puu lähettäjältä muihin solmuihin

Dijkstra => reititystaulu

least unicast-cost path tree = näiden polkujen yhdistelmä

Reverse path forwarding

“Älä turhaan lähetä tänne” (pruning)

paljon puita

N lähettäjää => N puuta

reitityksessä käytetty puu valitaan lähettäjän mukaan

Reverse path forwarding -algoritmi

idea

tuliko paketti portista, josta normaalisti lähetetään paketin aloittaneelle solmulle?

jos tuli, paketti kopioidaan kaikkiin muihin portteihin

jos ei tullut paketti tuhotaan kaksoiskappaleena

edut

tehokas ja helppo toteuttaa

ei tarvitse tuntea virittävää puuta

ei ylim. yleisrasitetta (kohdelista, lisäbittejä)

tulvitus päättyy itsestään

ryhmän jäsen

ei ole jäsen

A

C

B

F

E

D

G

lähettäjä

pruning: ’Älä turhaan lähetä tänne!’

Monilähetysreititys Internetissä

DVMRP (Distance Vector Multicast Routing Protocol) (RFC 1075)

kullekin lähteelle oma puu

käyttäen ‘reverse path forwarding’-menetelmää ja karsimista (pruning) ja lisäämistä (graft)

etäisyysvetrorialgoritmin avulla kukin reititin laskee lyhyimmän polun jokaiseen mahdolliseen lähteeseen ja tallettaa linkin (next hop)

tieto puussa ‘alavirtaan’ sijaitsevista reitittimistä, jotta tiedetään, milloin haara voidaan karsia

kun kaikki reitittimet ilmoittavat, etteivät enää ole kiinnostuneita

Muita

MOSPF (Multicast Open Shortest Path First) (RFC 1584)

OSPF:ää käyttävissä AS:issä

linkkitilailmoituksissa myös tieto monilähetysryhmien jäsennyydestä

kaikki reitittimet tietävät, mihin monilähetysryhmiin muiden reittimien isäntäkoneet kuuluvat

voivat laskea kullekin lähteelle oman ennaltakarsitun lyhyimmän polun puun kullekin monilähetysryhmälle

Muita monilähetysprotokollia: CBT

CBT (Core-based Trees) (RFC 2201, RFC 2189)

kaksisuuntainen yhteiskäyttöinen puu, jossa yksi keskus

sanomia

JOIN_REQUEST keskussolmulle, kun haluaa liittyä ryhmään

JOIN_ACK keskussolmu tai lähin jo ryhmässä oleva reititin

ECHO_REQUEST vieläkö mukana ryhmässä

ECHO_REPLY vielä mukana

FLUSH_TREE poistetaan ryhmästä

Muita: PIM

PIM (Protocol Independent Multicast) (RFC 2362)

dense mode ~ DVMRP

tulvita ja karsi sopii hyvin, jos vastaanottajia on ‘tiheään’

sparse mode ~ CBT

JOIN-sanomia, jotka ohjataan yksilähetyksenä keskussolmuun

polulla olevat reitittimet monilähetysmoodiin

keskussolmu lähettää monilähetyksenä muille

yksi puu <=> lähettäjälle oma puu

4.3 Mobile IP

IP-reititys IP-osoitteen perusteella

koneen osoite riippuu verkosta, jossa kone sijaitsee

kun kone siirtyy toiseen verkkoon tilapäisesti, osoite ei ole enää voimassa

koneelle uusi osoite tässä verkossa?

Tieto uudesta osoitteesta muille?

TCP-yhteys katkeaa

saumaton siirtyminen tuntumattomasti ei ole mahdollinen

kaikille koneille verkosta riippumaton osoite?

Liikkuvien isäntäkoneiden reititys

liikkuva kone (mobile host)

kotiosoite (home address, home location)

kotiagentti (home agent)

tietää, missä omat liikkuvat ovat

kun ilmaantuu vieraalle alueelle, se rekisteröityy

vierasagentti (foreign agent)

hoitaa alueelle tulleet vieraat liikkuvat

Liikkuvien isäntäkoneiden reititys

liikkuva kone (mobile host)

kotiosoite (home address, home location)

pysyvä osoite omassa verkossa,

aina tavoitettavissa tällä osoitteella

kotiagentti (home agent)

tietää, missä omat liikkuvat ovat

jos ei liikkuva kone ei ole kotiverkossa, kotiagentti osaa ohjata sille tulevat sanomat liikkuvan uuteen osoitteeseen

kun liikkuva kone ilmaantuu vieraalle alueelle, se rekisteröityy alueen

vierasagentille (foreign agent)

joka hoitaa alueelle tulleet vieraat liikkuvat

antaa niille osoitteen (care of address)

tämän verkon osoite

tarkistaa vieraan tiedot sen kotiagentilta

ilmoittaa kotiagentille koneen uuden osoitteen

näin kotiagentti tietää uuden sijainnin

Uudelle alueelle rekisteröinti

Vieras-agentti

Koti-agentti

Rekisteröinti-pyyntö

Pyynnön välitys

Sallii tai kieltää

vastaus

Vastaus koneelle

Käsittelee pyynnön ja vastauksen

Rekisteröintipyyntö sisältää:

sanoman tyypin (1)

lippuja, mm. haluttu tunnelointitapa

rekisteröinnin keston

koneen kotiosoitteen, kotiagentin osoitteen ja koneen vierasverkon osoitteen

rekisteröintipyynnön tunnisteen

laajennuksia, mm. autentikointilaajennus

Rekisteröintivastauksessa:

Sanoman tyyppi (3)

hyväksyttiinkö vai hylättiinkö rekisteröintipyyntö, kuka hylkäsi kotiagentti vai vierasgentti

hyväksytty rekisteröinnin kesto

pyynnön tunniste

liittää vastauksen pyyntöön

laajennusosia mm. autentikointi

Rekisteröinnissä ongelma on turvallisuus

Tekeytyminen vierasagentiksi

haluaa kaapata koneen liikenteen

tehokas autentikointi estää

autentikoinnin laajennusosa

MN -->FA, MN --> HA, FA --> HA

vanhojen rekisteröintipyyntöjen lähettäminen kotiagentille

kotiagentille väärä osoite => koneelle ei voi lähettää kotiosoitteella

pyyntöihin aikaleimat

Agentin löytäminen verkosta

Agentit ilmoittelevat itsestään säännöllisin välein

ilmoituksissa

reitittimen osoite

rekisteröinnin kesto

joukko lippuja: toimiiko vieras- vai kotiagenttina, onko kiireinen, millaista kapselointia kykenee käyttämään

vierasosoitteita, vähintään yksi

ilmoitusten avulla kone havaitsee siirtyneensä toiseen verkkoon

agentin osoite vaihtuu => uudelleenrekisteröinti

kotiverkossa, kun saa ilmoituksia omalta kotiagentiltaan

peruutettava rekisteröinti

Liikkuva kone kysyy itse agenttia

huomaa liikkuneensa toiseen verkkoon, kun alkaa saada sanomia toisella taajuudella

lähettää verkkoon kyselypyynnön, johon agentti vastaa ilmoituksella suoraan kyselevälle koneelle

Sanoman reititys vieraassa verkossa olevalle koneelle

Vieras-verkko

FA

MN

HA

Kotiverkko

CN

Normaali IP-reititys

tunnelointi

Vastaus suoraan

FA vierasagentti HA kotiagentti MN liikkuva kone CN kommunikoiva kone

Kotiagentti välittäjänä

Kun paketti lähetetään liikkuvalle,

se ohjautuu IP-osoitteen perusteella kotiverkkoon.

Kotiagentti ottaa paketin itselleen. Se tietää vastaanottajan nykyisen sijainnin ja ohjaa paketin sinne.

Käytetään IP-tunnelointia

uusi osoite COA on usein FA:n valvoma osoite

Uusi IP-otsake alkuperäinen IP-paketti

TCP-otsake + data

Lähde = CD, Kohde =MN Protocol = TCP

Lähde=HA, Kohde= COA, protocol= IP in IP (4)

Toiminta eetteriverkossa

CN

R

HA

MN

CN

R

HA

MN

Normaali reititys

Kotiagentti tunneloi sanoman MN:lle

Kun joku lähettää liikkuvalle paketin

se tulee ensin reitittimelle

reititin kysyy vastaanottajan LAN-osoitetta ARP:illa

jos liikkuva on kotiverkossaan, se vastaa ja ilmoittaa oman koneosoitteensa

muuten kotiagentti vastaa omalla osoitteellaan ja saa paketin

kotiagentti lähettää tunneloinnilla vierasosoitteeseen (yleensä vierasagentin oma osoite)

vierasagentti kysyy ARP:lla vierailijan LAN-osoitetta (‘koneosoitetta’)

Ja lähettää sanoman vierailevalle koneelle.

Ongelma:

CN

R

HA

MN

??

??

On vasta siirtymässä uuteen paikkaan eikä ole vielä ehtinyt ilmoittaa uutta osoitettaan

Vastaanottajaa ei ole enää tässä verkossa => paketit katoavat

FA

Entä jos vierasverkossa ei ole FA:ta?

MN saa tilapäisen IP-osoitteen verkkoon PPP- tai DHCP-protokollalla

käyttäen tätä osoitetta COA-osoitteena se voi itse toimia omana FA:na

Ongelmia:

tunnelointi lisää yleisarasitetta (ylim. IP-otsake) ja viimeinen linkki on hidas radiolinkki

liikkuvat tarvitsevat paljon tilapäisiä IP-osoitteita => osoitteet voivat loppua

poistuva kone ei aina ilmoita lähdöstään

kun kone poistuu, FA katoaa ja matkalla olevat paketit varmasti katoavat

Monilähetys vierasverkossa olevalle koneelle

HA ohjaa yksitellen kaikki lähetykset

tehotonta, voi aiheuttaa turhaa kuormitusta

voi aiheuttaa turhaa monilähetystä

tai sitten sanomaa ei toimiteta MN:lle

FA

MN

HA

Yleislähetys kotiverkossa

tunnelointi

Yleislähetys vierasverkossa

Monilähetys vierasverkossa olevalle koneelle

Jos käytössä verkon FA:aa, niin käytetään kaksoiskapselointia:

HA tietää rekisteröintitiedoista, käyttääkö MN FA:ta vai toimiiko itse oman FA:naan

Source=HA, Dest=COA, Protocol= encaps

Source=HA, Dest=MN, Protocol= encaps

Source=CN, Dest =broadcast, Protocol=UDP

UDP header + data

Uusi IP-otsake kaksoiskapselointi alkuperäinen monilähetys

Järkevämpää tosin olisi rekisteröityä monilähetysryhmään

uudelleen vierasverkossa!!

Mobile IPv6

Osoitteita riittää

vierailijat tarvitsevat IP-osoitteita vierailunsa aikana

Ei tarvita erityistä vierasagenttia

MN toimii yleensä itse omana vierasagenttinaan

neighbor discovery

stateless address autoconfiguration

Paremmat turvallisuuspiirteet

mm. estämään väärennetyt osoitemuutokset ja toistohyökkäykset (replay attack)

Reitin optimointi

turvalaajennoksen avulla MN voi ilmoittaa oman uuden osoitteensa suoraan lähettäjille

binding updates/acks/requests

kolmioreititystä ei tarvitse turvattomuuden takia käyttää

Route Optimization

Tehokkaampi kotiagentin löytäminen

Dynamic Home Agent Discovery

lähetetään Binding Update-sanoma kotiagenteille anycast-osoitteella, jolloin vain yksi ehkä useasta kotiagentista vastaa.

Kotiagentin osoite voi olla muuttunut poissaolon aikana

lähdereititysotsakkeen avulla saadaan tehokas kapselointi

two-hop source route

Filteroivien palomuurien läpäisy

5. Ruuhkan valvonta

yleistä ruuhkan valvonnasta

ruuhkan estäminen

liikenteen tasoittaminen

vuotava ämpäri, vuoromerkkiämpäri

liikennevirran määrittely

ruuhkan säätely

kuorman rajoittaminen

pääsyvalvonta, hidastuspaketit

kuorman purkaminen

pakettien tuhoaminen

Yleistä ruuhkasta

suorituskyvyn rajat

palvelijaketju (reititin, linkki, reititin, …)

ketjun maksimiteho korkeintaan hitaimman palvelijan teho

suoritusteho: sanoma/aikayksikkö

hitain palvelija on pullonkaula

jos hitainta tehostetaan => missä / mikä on uusi pullonkaula?

==>

==>

C1

C2

C4

C3









=> ruuhkaa

jos

ruuhkan valvonta <=> vuon valvonta

ruuhkanvalvonta

verkon selvittävä tarjotusta kuormasta

globaali ongelma

monta lähettäjää, monta vastaanottajaa

vuonvalvonta

lähettäjä ei saa lähettää enempää kuin vastaanottaja pystyy käsittelemään

kaksipisteyhteys

suora palaute vastaanottajalta lähettäjälle

‘open-loop’ control

järjestelmä suunnitellaan sellaiseksi, ettei ruuhkaa synny

uuden asiakkaan hyväksyminen

pakettien hävittäminen

skedulointiperiaatteet

järjestelmän tila ei vaikuta päätöksentekoon

‘closed-loop’ control

palautesilmukka (feed back loop)

seurataan järjestelmän tilaa

puskurien täyttöaste

uudelleenlähetysten lukumäärät, viipeet, viipeiden vaihtelu

ongelman havaitsija ilmoittaa

pakettien alkuperäiselle lähettäjälle, kaikille

reitittimet aktiivisesti kyselevät

nopeampi reagointi mahdollista

lähetyskäyttäytymisen muuttaminen ruuhkan vähentämiseksi

liian hidas reagointi => ruuhka kasvaa

liian nopea reagointi => heiluriliikettä

Toiminnan säätö ruuhkatilanteessa

lisää kapasiteettia

kiintiön nostaminen

varajärjestelmän käyttö

vähennä kuormaa

ei uusia käyttäjiä, huonompi palvelu, jne

sopii hyvin virtuaalipiireihin

virtuaalipiirit =>verkkokerroksella

datasähkeet => kuljetuskerroksella

Ruuhkanvälttämispolitiikat

siirtoyhteyskerros

uudelleenlähetyspolitiikka

epäjärjestyksessä saapuneiden talletuspolitiikka

kuittauspolitiikka,

vuon valvontapolitiikka,

verkkokerros

virtuaalipiiri <=> tietosähke

pakettien jonotuspolitiikka

pakettien poistamispolitiikka

reititysalgoritmi

pakettien elinikä

kuljetuskerros

uudelleenlähetyspolitiikka

epäjärjestyksessä saapuneiden talletuspolitiikka

kuittauspolitiikka

vuon valvontapolitiikka

ajastinaikojen asetukset

Päästäpäähän ruuhkanvalvonta (end-to-end)

TCP käyttää

Kaikki tieto lähettäjän ja vastaanottajan välillä

Verkkokerros ei anna mitään lisätietoa eikä avusta ruuhkanvalvonnassa

IP-kerros ei välitä ruuhkainformaatiota

Poikkeuksena ehdotettu ECN ja RED-jono

Verkonavustama ruuhkanvalvonta

Reitittimet antavat lähettäjille tietoa verkon ruuhkautumisesta

Yksittäinen bitti kertoo ruuhkasta linkissä

Reititin kertoo, millä nopeudella linkillä voi lähettää

Tieto voidaan lähettää suoraan lähettäjälle

Hillintäpaketti (Choke packet)

tai liittää se vastaanottajalle menevään pakettiin

ECN-ehdotus

Hitaaampi tapa

Atm ABR ruuhkanvalvonta

ABR (available bit rate)

Atm-soluja (‘pieniä paketteja’) kuljetetaan lähettäjältä vastaanottajalle useiden kytkimien (‘reitittimien’) läpi.

Soluvirrassa on datasolujen lisäksi erityisiä hallintasoluja RM-soluja

Välittävät mm. ruuhkaan liittyviä tietoja reitittimien ja isäntäkoneiden välillä

Tieto ensin vastaanottajalle

RM

RM

RM

RM

RM

RM

RM

RM

RM

Tieto suoraan lähettäjälle

RM

RM

RM

Lähetysnopeuteen perustuva

sovitaan tietystä lähetysmäärästä

vastaanottajalle tietoa ruuhkasta

EFCI-bitti (explicit forward congestion indication bit)

ilmoittaa vastaanottajlle ruuhkasta;

ruuhkautunut reititin asettaa

vastaanottaja lähettää ruuhkasta kertovan RM-solun lähettäjälle

(CI-bitti (congestion indication) asetettuna)

RM-solun CI -ja NI -bitit (no increase)

reititin asettaa: NI-bitti = lievä ruuhka

CI-bitti = vakava ruuhka

vasataanottaja palauttaa RM-solun lähettäjälle

RM-solun ER-kenttä kertoo todellisen siirtonopeuden ruuhkainen reititin voi asettaa kentän arvon pienemmäksi

kaikille rreitin reitittimille alempimarvo

Liikenteen tasoitus (traffic shaping)

liikenne tyypillisesti purskeista

juuri purskeisuus aiheuttaa ruuhkaisuutta

tasoitetaan liikennevirtaa puskurilla

puskuri toimii jonona

vuotava ämpäri

vuoromerkkiämpäri

liikennevirran määrittely

määrittelee asiakkaan oikeudet ja velvollisuudet

Vuotava ämpäri (leaky bucket)

purskeisuutta tasoittaa iso puskuri, josta liikenne valuu tasaisesti

‘vuotava ämpäri’

yksi tavu / yksi paketti lähtee jossain aikayksikössä, jos on lähetettävää

jos datapurske mahtuu puskuriin, se aikanaan pääsee matkaan

äärellinen jono

yläraja saapumistiheydelle

Vuoromerkkiämpäri (Token bucket)

lähettäminen vaatii vuoromerkin

vuoromerkkejä generoituu tasaisella nopeudella

jos ei lähetettävää, merkkejä jää säästöön

korkeintaan niin paljon kuin ämpäriin mahtuu

=> sallii rajoitetut ‘minipurskeet’

joustavampi kuin vuotava ämpäri

purskeet voivat aiheuttaa ruuhkaa => vuotava ämpäri vuoromerkkiämpärin perään

Liikenteen määrittely (flow specification)

sovitaan liikennevirrasta yhteyttä muodostettaessa

asiakas esittää kuorma- ja palvelutoiveet

palvelija: ok/ ei käy/ vastaehdotus

pyydetty palvelu

pakettien katoamisen sietokyky (loss sensitivity): missä määrin asiakas sietää pakettien tuhoamista

viiveherkkyys (delay, delay variation)

takuu: onko toive vai ehdoton vaatimus

asiakas ei aina tiedä mitä todella haluaa

Virtuaalikanavan ruuhkanvalvonta

pääsynvalvonta (admission control)

jos ruuhkaa, ei uusia virtuaalikanavia

uusi kanava ok, jos kiertää ruuhka-alueen

virtuaalikanavaa avattaessa

sovitaan liikennekuormituksesta ja palvelun laadusta

verkosta varataan tarvittavat resurssit

resurssien varaus

milloin varataan, paljonko varataan

liikenne on purskeista

turha varaus tuhlaa resursseja

hidastuspaketti (choke packet)

voidaan käyttää kaikenlaisissa verkoissa

reititin tarkkailee kuormitusta

ulosmenolinjojen käyttöastetta

jonopituuksia

esim

Unew = aUold + (1-a)f

a kuinka nopeasti aikaisempi historia unohtuu

f kuormitettu vai ei ( o tai 1)

jos liikaa kuormaa, reititin huolestuu

lähettäjälle hidastuspaketti

lähettäjä hidastaa lähetystään

vähentää ensin puoleen

ja sitten taas puoleen

perustuu vapaaehtoisuuteen

reilu jonotus

useita kynnysarvoja

lievä, vakava, erittäin vakava varoitus

muita ruuhkan ‘mittoja’

jonon pituus

puskurikäyttö

Hidastuspaketin ongelmia:

lähettäjän hidastus vapaaehtoista

reilu jonotus:

kullakin lähettäjällä oma jono jokaiseen ulosmenolinjaan

A

B

C

Lähetetään vuorotellen eri jonoista.

Hidastuspaketin vaikutuksen hitaus pitkillä linjoilla

Ratkaisu:

ei pelkästään lähettäjälle

myös välissä olevat reitittimet alkavat hidastaa

Kuorman kevennys (Load Shedding)

tuhotaan paketteja => kuorma kevenee

reititin täyttyy:

mitä paketteja tuhotaan?

11

10

9

8

reititin

7

6

13

12

FTP: tuhotaan 8 => paketit 8-11 uudelleen

tuhotaan 11 => paketti 11 uudelleen

video: ?

riippuu sovelluksesta

viini: vanha parempi kuin uusi

maito: uusi parempi kuin vanha

eriarvoiset paketit

perusdata/muutokset

teksti / kuva

käyttäjä ilmoittaa prioriteetin

arvokkaita ei tuhota

prioriteetin käytön valvonta: hinta/sallitun lähetysmäärän ylittävät paketit

paketti tuhottu, entä sanoma

mitä tehdään ko. sanomalle

Vuopohjainen reititys (Flow-Based Routing)

viive = jonotusaika + siirtoaika

etsitään pienin mahdollinen viive koko verkolle

tunnettava

verkon topologia

kapasiteettimatriisi

eri linkkien kapasiteetti

liikennematriisi

eri solmujen välinen liikenne

alustava reititys

lasketaan

kunkin linjan kuormitus i

keskim. pakettien määrä kullakin linjalla Ci

keskim. pakettikoko = 1/esim. 800 bittiä)

keskim viive kullekin linjalle

T = 1/( C - ) (jonoteoriasta)

1/ = keskim. paketin koko bitteinä

C = kapasiteetti bps

 = keskim. pakettivirta (kuormitus)

paketteina sekunnissa

koko verkon viive

painotettu keskiarvo eri linkkien viipeistä

painotuksena linkin osuus koko liikenteestä

eri reititysalgoritmien vertailu

lasketaan erikseen kaikille reititysvaihtoehdoille

mahdollinen, vaikka raskas

valitaan ‘paras’

edellyttää kuormituksen pysyvän melko samanlaisena

ei oikein sovellu koko ajan muuttuvaan verkkoon

Piirikytkentäisten verkkojen reititys

lyhyin polku (Shortest path first) (ABD tai ACD)

vähiten kuormitettu polku (Least loaded path) (ABCD)

eniten vapaita piirejä omaava polku (Maximum free circuit)

(ABD)

35/70

5/20

19/20

1/19

6/20

B

D

A

C

A/B

B = linkin kapasiteetti

A= siitä käytössä

oleva osuus,

esim. piirien määränä

Piirikytkentäisissä verkoissa

kaikki reitittimet tietävät kaikkien linkkien tilan

linkkitilatyyppinen reititys

tietojen oikeellisuus ja ajantasaisuus tärkeää

37/70

5/20

19/20

2/19

6/20

B

D

A

C

10/10

IPv6-protokolla

2004-09-29T12:50:21