Glava 4: Mrežni nivo - Ivan Drakic · 4.5 Algoritmi rutiranja Link state Distance Vector...

1

Mrežni nivo 4-30

Glava 4: Mrežni nivo

4. 1 Uvod4.2 Mreže sa virtuelnim kolima i datagramima4.3 Šta je unutar rutera?4.4 IP: Internet Protokol

Format datagramaIPv4 adresiranjeICMPIPv6

4.5 Algoritmi rutiranjaLink stateDistance VectorHijerarhijsko rutiranje

4.6 Rutiranje naInternetu

RIPOSPFBGP

Mrežni nivo 4-31

Internet mrežni nivo

Tabelaprosleđivanja

Host, ruter funkcije mrežnog nivoa:

Protokoli rutiranja•Izbor puta•RIP, OSPF, BGP

IP protokol•Adresne konvencije•Format datagrama•Konvencije o obradi paketa

ICMP protokol•Objava greške•“signalizacija” rutera

Transportni nivo: TCP, UDP

Nivo linka

Fizički nivo

Mrežninivo

2

Mrežni nivo 4-32






RIPOSPFBGP

Mrežni nivo 4-33

Format IP datagrama

ver length

32 bita

data (varijabilne veličine,

tipično TCP ili UDP segment)

16-bit identifierInternetchecksum

time tolive

32 bit source IP address

Verzija IP protokola

Veličina zaglavlja(u bajtima)

Maksimalan brojpreostalih hopova(dekrementira seu svakom ruteru)

zafragmentaciju/defragmentaciju

Ukupna veličinadatagrama (u bajt.)

Protokol višeg nivoa kometreba predati podatke

TCP 6, UDP 17

head.len

type ofservice

“tip” podataka flgs fragmentoffset

upperlayer

32 bit destination IP address

Options (if any) Npr. “timestamp”Definisanje rute,specificira listurutera koje

treba posjetiti.

Koliko zaglavlje sa TCP?20 bajtova TCP-a20 bajtova IP-a= 40 bajtova + zaglavlje nivoa apl.

Samo za zaglavlje

3

Mrežni nivo 4-34

IP Fragmentacija & DefragmentacijaMrežni linkovi imaju MTU (max.transfer size) – najveći mogući okvir nivoa linka.

Različiti tipovi linkova, različiti MTU-ovi

veliki IP datagram se dijeli (“fragmentira”) u okviru mreže

jedan datagram postaje više datagrama“defragmentira” se samo na konačnoj destinacijiIP biti zaglavlja se koriste za identifikaciju redosleda vezanog za fragment

fragmentacija: u: jedan veliki datagramiz: 3 mala datagrama

defragmentacija

Mrežni nivo 4-35

IP fragmentacija i defragmentacijaID=x

ofset=0

fragflag=0

Velič.=4000

ID=x

ofset=0

fragflag=1

Velič.=1500

ID=x

ofset=185

fragflag=1

Velič.=1500

ID=x

ofset=370

fragflag=0

Velič.=1040

Jedan veliki datagram postajeviše manjih datagrama

PrimjerDatagram od 4000 bajtaMTU = 1500 bajta

1480B u poljupodataka

offset =1480/8

4

Mrežni nivo 4-36






RIPOSPFBGP

Mrežni nivo 4-37

IP Adresiranje: uvodIP adresa: 32-bitniidentifikator za hostili ruter interfejsinterfejs: veza između host/rutera i fizičkog linka

ruteri tipično imaju više interfejsovaI host može imati više interfejsovaIP adrese su vezane za svaki interfejs

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

223.1.1.1 = 11011111 00000001 00000001 00000001

223 1 11

5

Mrežni nivo 4-38

IP AdresiranjeIP adresiranje:

Mrežni dio (biti višeg reda)Dio hosta (biti nižeg reda)

Šta je mreža? (iz perspektive IP adrese)

Interfejsi uređaja sa istim mrežnim dijelom IP adresemogu fizički dosegnuti jedni druge bez učešća rutera

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

Mreža se sastoji od 3 IP podmreže(prvih 24 bita su mrežna adresa)

LAN

Mrežni nivo 4-39

Podmreža 223.1.1.0/24 223.1.2.0/24

223.1.3.0/24

NapomenaDa bi odredili podmreže, treba razdvojiti svaki interfejs od njegovog hosta ili rutera, kreirajući ostrva izolovanih mreža. Svaka izolovana mreža se zove podmreža. Maska podmreže: /24

6

Mrežni nivo 4-40

PodmrežeKoliko ih je? 223.1.1.1

223.1.1.3

223.1.1.4

223.1.2.2223.1.2.1

223.1.2.6

223.1.3.2223.1.3.1

223.1.3.27

223.1.1.2

223.1.7.0

223.1.7.1223.1.8.0223.1.8.1

223.1.9.1

223.1.9.2

Mrežni nivo 4-41

IP adresiranje: CIDRCIDR: Classless InterDomain Routing

Podmrežni dio adrese je proizvoljne veličineFormat adrese: a.b.c.d/x, gdje je x broj bita u mrežnom dijelu adrese

11001000 00010111 00010000 00000000

Podmrežni dio Host dio

200.23.16.0/23

7

Mrežni nivo 4-42

IP adrese: kako dobiti IP adresu?

P: Kako host dobija IP adresu?

“hard-coded” od strane sistem administratora u fajlu

Winl: control-panel->network->configuration->tcp/ip->propertiesUNIX: /etc/rc.config

DHCP: Dynamic Host Configuration Protocol: dinamički dobija adresu sa servera

“plug-and-play”

Mrežni nivo 4-43

DHCP: Dynamic Host Configuration Protocol

Cilj: omogućiti hostu dinamičko dobijanje adresa sa mrežnog servera kada se poveže na mrežuMože obnoviti adresu koju je već koristioOmogućava “reuse” adresa (host zadržava adresu sok je

uključen)Olakšava pristup mobilnim korisnicima koji se pridružuju mreži

Pregled DHCP:host svima šalje “DHCP discover” poruku (UDP segment na port 67)DHCP server odgovara “DHCP offer” porukomhost zahtijeva IP adresu: “DHCP request” porukomDHCP server šalje adresu: “DHCP ack” porukom

8

Mrežni nivo 4-44

DHCP klijent-server scenario

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

A

BE

DHCP server

DHCP klijent koji dolazizahtijeva adresuu mreži

Mrežni nivo 4-45

DHCP klijent-server scenarioDHCP server: 223.1.2.5 Novi klijent

time

DHCP discover

src : 0.0.0.0, 68 dest.: 255.255.255.255,67yiaddr: 0.0.0.0transaction ID: 654

DHCP offersrc: 223.1.2.5, 67 dest: 255.255.255.255, 68yiaddrr: 223.1.2.4transaction ID: 654Lifetime: 3600 secs

DHCP request

src: 0.0.0.0, 68 dest:: 223.1.2.5, 67yiaddrr: 223.1.2.4transaction ID: 655Lifetime: 3600 secs

DHCP ACKsrc: 223.1.2.5, 67 dest: 255.255.255.255, 68yiaddrr: 223.1.2.4transaction ID: 655Lifetime: 3600 secs

9

Mrežni nivo 4-46

IP adrese: kako dobiti IP adresu?P: Kako mreža dobija podmrežni dio IP adrese?

ISP-ov blok 11001000 00010111 00010000 00000000 200.23.16.0/20

Organizacija 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organizacija 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organizacija 2 11001000 00010111 00010100 00000000 200.23.20.0/23

... ….. …. ….Organizacija 7 11001000 00010111 00011110 00000000 200.23.30.0/23

Mrežni nivo 4-47

Hijerarhijsko adresiranje: agregacija ruta

“Pošalji mi bilo štasa adresom koja počinje sa200.23.16.0/20”

200.23.16.0/23

200.23.18.0/23

200.23.30.0/23

Fly-By-Night-ISP

Organizacija 0

Organizatcija 7Internet

Organizacija 1

ISPs-R-Us “Pošalji mi bilo štasa adresom koja počinje sa199.31.0.0/16”

200.23.20.0/23Organizatcija 2

...

...

Hijerarhijsko adresiranje dozvoljava efikasno oglašavanje informacijepotrebne za rutiranje:

10

Mrežni nivo 4-48

Hijerarhijsko adresiranje: specifičnije rute

ISPs-R-Us ima više specifičnih ruta do Organizacije 1

“Pošalji mi bilo štasa adresom koja počinje sa200.23.16.0/20”

200.23.16.0/23

200.23.18.0/23

200.23.30.0/23

Fly-By-Night-ISP

Organizacija 0

Organizacija 7Internet

Organizacija 1

ISPs-R-Us “Pošalji mi bilo štasa adresama kojepočinju sa 199.31.0.0/16ili 200.23.18.0/23”

200.23.20.0/23Organizacija 2

...

...

Mrežni nivo 4-49

IP adresiranje: poslednja riječ...

P: Kako ISP dobija svoj blok adresa?O: ICANN: Internet Corporation for Assigned

Names and NumbersDodjeljuje adreseUpravlja DNSDodjeljuje imena domena, razrješava sporoveDodjeljuje adrese lokalnim regionalnim Internet registrima (ARIN, RIPE, APNIC i LACNIC)

11

Mrežni nivo 4-50

NAT: Network Address Translation

10.0.0.1

10.0.0.2

10.0.0.3

10.0.0.4

138.76.29.7

Lokalna mreža(npr., kućna mreža)

10.0.0.0/24

Ostatak Interneta

Datagrami sa izvorima ilidestinacijama u ovoj mreži

imaju 10.0.0.0/24 adresu zaizvor, destinaciju (kao što

je uobičajeno)

Svi datagrami napuštaju lokalnumrežu imajući istu jedinstvenu

izvorišnu adresu NAT IP: 138.76.29.7,

Različiti brojevi izvorišnih portova

Mrežni nivo 4-51


Motivacija: lokalna mreža koristi samo jednu IP adresu:Nema potrebe za dodjelu opsega adresa od straneISP (samo jedna IP adresa se koristi za sve uređaje)Mogu mijenjati adrese uređaja u lokalnim mrežama bez obavještenja “ostatku svijeta”Mogu mijenjati ISP bez mijenjanja adresa uređaja u lokalnim mrežamaUređaji unutar mreže se eksplicitno ne adresiraju, na vidljiv način “ostatku svijeta” (plus u smislu zaštite).

12

Mrežni nivo 4-52

NAT: Network Address TranslationImplementacija: NAT ruter mora:

odlazni datagrami: zamijeniti (izvorišnu IP adresu, broj port) svakog odlaznog datagrama sa (NAT IP adresom, novim brojemporta)

. . . udaljeni klijenti/serveri će odgovoriti korišćenjem (NAT IP adrese, novi broj porta) kao adrese destinacije.

zapamtiti (u NAT tabeli translacija) svaki (izvorišna IP adresa, broj porta) i (NAT IP adresa, novi broj porta) u vidu translaticionog para

dolazeći datagrami: zamijeniti (NAT IP adresu, novi broj porta) u polju destinacije svakog dolaznog datagrama sa odgovarajućim(izvorišna IP adresa, broj porta) smještenim u NAT tabeli

Mrežni nivo 4-53


10.0.0.1

10.0.0.2

10.0.0.3

I: 10.0.0.1, 3345D: 128.119.40.186, 80

110.0.0.4

138.76.29.7

1: host 10.0.0.1 šalje datagram 128.119.40.186, 80

NAT tabela translacijaAdr. WAN strane Adr. LAN str.138.76.29.7, 5001 10.0.0.1, 3345…… ……

I: 128.119.40.186, 80 D: 10.0.0.1, 3345 4

I: 138.76.29.7, 5001D: 128.119.40.186, 802

2: NAT rutermijenja izvorišnu adresu datagramaiz 10.0.0.1, 3345 u138.76.29.7, 5001,ažurira tabelu

I: 128.119.40.186, 80 D: 138.76.29.7, 5001 3

3: Odgovor stižedestinacionoj adresi:138.76.29.7, 5001

4: NAT rutermijenja destinacionuadresu datagramaiz 138.76.29.7, 5001 u 10.0.0.1, 3345

13

Mrežni nivo 4-54


16-bitno polje broja porta: 65536 simultanih veza sa jednom adresom sa LAN strane!

NAT je kontraverzan:Ruteri bi trebali vršiti obradu samo do nivoa 3Narušava prirodu od kraja do kraja

• NAT mora biti uzet u obzir od strane dizajnera aplikacija, npr., P2P aplikacija

Oskudica adresa se može ublažiti i prije upotrebe IPv6Broj porta se posredno koristi za adresiranje računara

Mrežni nivo 4-55

NAT problem sa serveromklijent želi da se poveže na server čija je adresa10.0.0.1

Adresa servera 10.0.0.1 je lokalna adresa na LAN mreži(klijent je ne smije koristiti kao destinacionu adresu)Jedina globalno vidljiva adresa je: 138.76.29.7

Rješenje 1: statički konfigurisati NAT tako da dolazne zahtjeve prosleđuje na željeni port servera

npr., (138.76.29.7, port 2500) se uvijek prosleđuje na 10.0.0.1 port 25000

10.0.0.1

10.0.0.4

NAT router

138.76.29.7

Klijent?

14

Mrežni nivo 4-56

NAT problem sa serveromRješenje 2: Univerzalni Plug and Play

(UPnP) Internet Gateway Device (IGD) protokol. Dozvoljava serveru iza NAT-a da:

Sazna javnu IP adresu(138.76.29.7)sazna postojeća mapiranja portovadodaje/uklanja mapiranja portova(sa vremenima iznajmljivanja)

npr., automatska statička konfiguracija NAT mapiranja portova

10.0.0.1

10.0.0.4

NAT router

138.76.29.7

IGD

Mrežni nivo 4-57

NAT problem sa serveromRješenje 3: “relaying” (koristi se kod Skype)

NAT-ovani server uspostavlja konekciju sa Skype relay uređajemspoljnji klijent se povezuje na skype relayrelay prosleđuje pakete između konekcija

10.0.0.1

NAT router

138.76.29.7Klijent

1. Konekcija sa relay uređajem uspostavljena od strane hosta

2. Klijent inicijalizuje vezu prema relay

3. Uspostavljenorelaying

15

Mrežni nivo 4-58






RIPOSPFBGP

Mrežni nivo 4-59

ICMP: Internet Control Message Protocol

koriste hostovi, ruteri, “gateway” za prenos informacija nivoa mreže

obavještenje o greški: nedostižan host, mreža, port, protokolecho zahtjev/odgovor(koristi ga ping)

Mrežni nivo “iznad” IP:ICMP poruke se nose u IP datagramima

ICMP poruke: tip, kod i prvih 8 bajtova IP datagrama koji je izazvao grešku

Tip Kod Opis0 0 echo reply (ping)3 0 dest. network unreachable3 1 dest host unreachable3 2 dest protocol unreachable3 3 dest port unreachable3 6 dest network unknown3 7 dest host unknown4 0 source quench (congestion

control - not used)8 0 echo request (ping)9 0 route advertisement10 0 router discovery11 0 TTL expired12 0 bad IP header

16

Mrežni nivo 4-60

Traceroute i ICMP

Izvor šalje serije UDP segmenata do destinacije

Prvi ima TTL =1Drugi ima TTL=2, itd.Nepoželjni broj porta

Kada n-ti datagram stigne na n-ti router:

ruter odbacuje datagramšalje izvoru ICMP poruku(tip 11, kod 0)poruka uključuje imerutera & IP adresu

Kada ICMP poruka stigne, izvor izračunava RTTTraceroute to ponavlja 3 puta

Kriterijum zaustavljanjaUDP segment eventualno stigne do destinacionog hostaDestinacija vraća ICMP “port unreachable” paket(tip 3, kod 3)Kada izvor dobije ovajICMP, zaustavlja se.

Mrežni nivo 4-61






RIPOSPFBGP

17

Mrežni nivo 4-62

IPv6Inicijalna motivacija: 32-bitni adresni prostor će vrlo brzo u potpunosti biti dodijeljen. Dodatna motivacija:

Format zaglavlja pomaže obradi/prosleđivanjuPromjene zaglavlja uključuju QoS

IPv6 format datagrama:Zaglavlje fiksne-dužine od 40BNije dozvoljena fragmentacija

Mrežni nivo 4-63

IPv6 zaglavlje (nastavak)Priority: identifikuje prioritet između datagrama u “toku”Flow Label: identifikuje datagrame u istom “toku”.

(koncept “toka” nije precizno definisan).Next header: identifikuje protokola višeg nivoa za podatke

18

Mrežni nivo 4-64

Druge izmjene u odnosu na IPv4

Checksum: potpuno uklonjena kako bi se smanjila obrada na svakom hopuOptions: dozvoljene, ali van zaglavlja, indicirano sa “Next Header” poljemICMPv6: nova verzija ICMP

dodatni tipovi poruka, npr. “Packet Too Big”funkcija upravljanja multicast grupama

Mrežni nivo 4-65

Tranzicija od IPv4 do IPv6

Ne mogu svi ruteri biti simultano nadograđeniNema “dana D”Kako će funkcionisati mreža sa kombinacijom IPv4 iIPv6 rutera?

Tunelovanje: IPv6 datagram se može prenositi kao sadržaj u IPv4 datagramu preko IPv4 rutera

19

Mrežni nivo 4-66

TunelovanjeA B E F

IPv6 IPv6 IPv6 IPv6

tunelLogički pogled:

Fizički pogled:A B E F

IPv6 IPv6 IPv6 IPv6IPv4 IPv4

Mrežni nivo 4-67

TunelovanjeA B E F

IPv6 IPv6 IPv6 IPv6

tunelLogički izgled:

Fizički izgled:A B E F

IPv6 IPv6 IPv6 IPv6

C D

IPv4 IPv4

Tok: XIzv: ADest: F

podaci

Tok: XIzv: ADest: F

podaci

Tok: XIzv: ADest: F

podaci

Izv:BDest: E

Tok: XIzv: ADest: F

podaci

Izv:BDest: E

A-do-B:IPv6

E-do-F:IPv6B-do-C:

IPv6 unutarIPv4

B-do-C:IPv6 unutar

IPv4

20

Mrežni nivo 4-68






RIPOSPFBGP

Mrežni nivo 4-69

1

23

0111

Vrijednost u zaglavljudolaznog paketa

Algoritam rutiranja

Tabela lokalnog prosleđivanja

Vrij. Zagl. izlazni link0100010101111001

3221

Međuveza prosleđivanja i rutiranja

21

Mrežni nivo 4-70

u

yx

wv

z2

21

3

1

1

2

53

5

Graf: G = (N,E)

N = skup rutera = { u, v, w, x, y, z }

E = skup linkova ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }

Abstrakcija pomoću grafa

Napomena: Abstrakcija pomoću grafa je korisna i u drugim mrežnim kontekstima.Primjer: P2P, gdje je N skup peer-ova, a E skup TCP konekcija

Mrežni nivo 4-71

Abstrakcija pomoću grafa: troškovi

u

yx

wv

z2

21

3

1

1

2

53

5 • c(x,x’) = težinski faktor (cost) linka (x,x’)

- npr., c(w,z) = 5

• težinski faktor može biti uvijek 1, ilirecipročan protoku, ili recipročan zagušenju

Težinski faktor puta (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)

Pitanje: Koji je put sa najmanjim težinskim faktorom između u i z ?

Algoritam rutiranja: algoritam koji pronalazi put sanajmanjim težinskim faktorom

22

Mrežni nivo 4-72

Klasifikacija algoritama rutiranjaGlobalna ili decentralizovana

informacija?Globalna:

svi ruteri posjeduju kompletnu topologiju mreže sa informacijama o težinskim faktorima linkova“link state” algoritmi

Decentralizovani:ruter poznaje fizički povezane susjede i težinske faktore linkova do susjedaiterativni proces izračunavanja, razmjena informacija sa susjedima“distance vector” algoritmi

Statički ili dinamički?Statički:

Rute se sporo mijenjajuDinamički:

Rute se mijenjaju mnogo brže

periodični updatekao odgovor na promjene težinskih faktora linkova

Mrežni nivo 4-73






RIPOSPFBGP

23

Mrežni nivo 4-74

“Link-State” Algoritam RutiranjaDijkstra algoritam

Mrežna topologija, težinski faktori linkova poznati svim čvorištima

Dobijeno preko “link state broadcast”Sva čvorišta imaju istu informaciju

Proračunava puteve najmanjih težinskih faktora od jednog čvorišta (“izvor”) do svih ostalih čvorova

generiše tabelu rutiranjaza to čvorište

iterativni: poslije k iteracija, poznat je put sa najmanjim težinskim faktorom do k destinacija

Notacija:c(A,B): težinski faktor linka od čvorišta x do y su beskonačni ukoliko čvorišta nijesu susjediD(A): trenutna vrijednost težinskog faktora puta od izvorišta do destinacije Ap(A): sledeće čvorište dužputa od izvorišta do čvorišta A, koje je susjed AN’: skup čvorišta čiji su najniži težinski faktori puta poznati

Mrežni nivo 4-75

Dijsktra Algoritam (na čvoru u)1 Inicijalizacija:2 N’ = {u} 3 Za sva čvorišta A4 Ako je A susjedno čvorište u5 tada D(A) = c(u,A) 6 else D(A) = ∞7 8 Petlja9 Pronaći B koje nije u N’ tako da je D(B) minimalno10 dodati B skupu N’11 update D(A) za sve A susjede B koji nijesu u N’: 12 D(A) = min( D(A), D(B) + c(B,A) ) 13 /* novi težinski faktori za A su ili stari težinski faktori za A ili su poznati14 najmanji težinski faktori puta do B plus težinski faktori od B do A */15 dok sva čvorišta ne budu u N’

u

yx

wv

z2

21

3

1

1

2

53

5

24

Mrežni nivo 4-76

Dijkstra algoritam: primjerčvorište U

Korak012345

N'u

D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)

u

yx

wv

z2

21

3

1

1

2

53

5

2,u2,u2,u

5,u4,x3,y3,y

1,u2,x∞ ∞

4,y∞

4,y4,y

uxuxy

uxyvuxyvw

uxyvwz

Mrežni nivo 4-77

Dijkstra algoritam: primjer (2)

u

yx

wv

z

Rezultujuća shortest-path topologija iz čvorišta u:

vxywz

(u,v)(u,x)(u,x)(u,x)(u,x)

destinacija link

Rezultujuća tabela prosleđivanja u čvorištu u:

25

Mrežni nivo 4-78

Dijkstra’s algoritam, diskusijaKompleksnost algoritma: n čvorišta

Svaka iteracija: potrebno da provjeri sva čvorišta, B, koja nijesu u N’n*(n-1)/2 komparacija: O(n2)Moguće su efikasnije implementacije: O(nlogn)

Moguće su oscilacije:npr., težinski faktor linka = količina prenešenog saobraćaja

AD

CB

1 1+e

e0

e1 1

0 0

AD

CB

2+e 0

001+e 1

AD

CB

0 2+e

1+e10 0

AD

CB

2+e 0

e01+e 1

inicijalno … novi proračun

… novi proračun

… novi proračun

1 1 1 1 1 1e e e

Mrežni nivo 4-79






RIPOSPFBGP

26

Mrežni nivo 4-80

Distance Vector Algoritam (1)

Bellman-Ford jednačina (dinamičko programiranje)Definišimodx(y) := težinski faktor puta sa najmanjim troškovima od x do y

Tada

dx(y) = minv {c(x,v) + dv(y) }

Gdje se minv uzima u odnosu na sve susjede x

Mrežni nivo 4-81

Bellman-Ford primjer (2)

u

yx

wv

z2

21

3

1

1

2

53

5Jasno, dv(z) = 5, dx(z) = 3, dw(z) = 3

du(z) = min { c(u,v) + dv(z),c(u,x) + dx(z),c(u,w) + dw(z) }

= min {2 + 5,1 + 3,5 + 3} = 4

Čvorište koje dostigne minimum je sledećikorak (hop) u najkraćem putu ➜ tabela prosleđivanja

B-F jednačina kaže:

27

Mrežni nivo 4-82

Distance Vector Algoritam (3)

Dx(y) = estimira najmanji težinski faktor od x do yDistance vector: Dx = [Dx(y): y є N ]Čvorište x poznaje težinske faktore do svakog svog susjeda v: c(x,v)Čvorište x nadzire Dx = [Dx(y): y є N ]Čvorište x takođe nadzire distance vector-e svojih susjeda

Za svakog susjeda v, x nadzireDv = [Dv(y): y є N ]

Mrežni nivo 4-83

Distance vector algoritam (4)

Osnovna ideja:Svako čvorište periodično šalje estimaciju svog distance vector-a svojim susjedimaKada čvorište x primi novu DV estimaciju od svog susjeda, update-je svoj sopstveni DV korišćenjemB-F jednačine:

Dx(y) ← minv{c(x,v) + Dv(y)} za svako čvorište y ∊ N

U većem broju slučajeva, pod normalnim okolnostima, estimat Dx(y) konvergira stvarnom najmanjem težinskom faktoru dx(y)

28

Mrežni nivo 4-84

Distance Vector Algoritam (5)Iterativni, asinhron: svaka lokalna iteracija je

uzrokovana: lokalni težinskim faktorimalinka koji su promjenljiviporukama od susjeda: najmanji težinski faktori puta su promijenjeni

Distribuiran:svako čvorište obavještava susjeda samo kada se njegov put sa najmanjim težinskim faktorom promijeni

susjedi informišu susjede ako je to potrebno

čeka za (poruku susjeda o promjeni težinskih faktora linka)

preračunava “distance”tabelu

Ako se najmanji težinski faktori puta do bilo koje destinacije promijene, obavještava susjede

Svako čvorište:

Mrežni nivo 4-85

x y zxyz

0 2 7∞∞ ∞∞∞ ∞

od

Tež. fakt. do

odod

x y zxyz

0 2 3

od

Tež. fakt. dox y z

xyz

0 2 3

od

Tež. fakt. do

x y zxyz

∞ ∞

∞∞ ∞

Tež. fakt. dox y z

xyz

0 2 7

od

Tež. fakt. dox y z

xyz

0 2 3

od

Tež. fakt. do

x y zxyz

0 2 3

od

Tež. fakt. dox y z

xyz

0 2 7

od

Tež. fakt. dox y z

xyz

∞∞ ∞7 1 0

Tež. fakt. do

∞2 0 1

∞ ∞ ∞

2 0 17 1 0

2 0 17 1 0

2 0 13 1 0

2 0 13 1 0

2 0 1

3 1 02 0 1

3 1 0

vrijeme

x z11

2

y

Tabela čvorišta x

Tabela čvorišta y

Tabela čvorišta z

Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2

Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)}

= min{2+1 , 7+0} = 3

29

Mrežni nivo 4-86

“Distance Vector”: promjene težinskih faktora linka

Promjene težinskih faktora linka:Čvorište detektuje lokalne promjene težinskih faktora linkaažuriranje “distance” tabele Ako se težinski faktori promijene u putu sa najmanjim težinskim faktorom, obavijesti susjede

X Z14

50

Y1

“dobrevijestibrzoputuju”

U trenutku t0, y detektuje promjenu težinskog faktora linka, ažurira njegov DV, i informiše susjede.

U trenutku t1, z prima update od y i update-je svoju tabelu. Izračunava novi najmanji težinski faktor do x i šalje svojim susjedima svoj DV.

U trenutku t2, y prima z-ove update i ažurira svoju distance tabelu. Y-ov najmanji težinski faktor se ne mijenja i stoga y ne šalje nikakvu poruku ruteru z.

Mrežni nivo 4-87

“Distance Vector”: promjene težinskih faktora linka

X Z14

50

Y60

Promjene troškova linka:dobre vijesti se brže prenoseloše vijesti se sporije prenose – problem “brojanje do ∞”!44 iteracije do stabilizacije algoritma

Tehnika split-horizonUpdate ruta šalje težinske faktore ruta koje se mogu doseći preko drugih portova.

Poissoned reverse (lažno rastojanje):Ako Z rutira preko Y do X :

Z govori Y da je njegova (Z-ova) udaljenost do X beskonačna (tako da Y ne bi rutirala do X preko Z)

Da li će to riješiti problem brojanja do beskonačnosti?

30

Mrežni nivo 4-88

Upoređenje LS i DV algoritama

Kompleksnost porukeLS: sa n čvorišta, E linkova, O(nE) poruka šalje svaki čvorDV: razmjena samo između susjeda

Konvergencija varira u vremenu

Brzina konvergencijaLS: O(n2) algoritam zahtijevaO(nE) poruka

Mogu imati oscilacijeDV: konvergencija varira u vremenu

Može biti petljiProblem brojanja do ∞

Robustnost: šta se dešava kada ruter otkaže?

LS:Čvorište može objaviti težinski faktor neispravnoglinkaSvako čvorište proračunava svoju sopstvenu tabelu

DV:DV čvorište može objaviti težinski faktor neispravnoglinkaTabelu svakog čvorišta koriste drugi

• Greška se prenosi kroz mrežu

Mrežni nivo 4-89






RIPOSPFBGP

31

Mrežni nivo 4-90

Hijerarhijsko rutiranje

veličina: nekoliko stotina milionadestinacija:ne mogu se sve destinacije smjestiti u tabele rutiranja!razmjena tabela rutiranje može oboriti linkove!LS može izazvati potiskivanje saobraćaja na račun broadcasta tabelaDV teško može konvergirati

administrativna autonomijainternet = mreža svih mrežasvaki mrežni administrator želi

kontrolu rutiranja u svojoj sopstvenoj mrežiSakriti mrežnu organizaciju od ostalih

Prethodna analiza je bila - idealizacijaSvi ruteri su identični“flat” mreža

… praksa je drugačija

Mrežni nivo 4-91

Hijerarhijsko rutiranje

grupiše rutere u regione,“autonomni sistemi” (AS)ruteri u istom AS izvršavaju isti protokol rutiranja

“intra-AS” protokol rutiranja se slično ponaša objašnjenim idealizovanim modelimaruteri u različitim AS mogu izvršavati različite intra-AS protokole rutiranja

Gateway ruterProsleđuje datagrame van AS

32

Mrežni nivo 4-92

3b

1d

3a

1c2aAS3

AS1AS2

1a

2c2b

1b

Intra-ASAlgoritamrutiranja

Inter-ASAlgoritamrutiranja

Tabelaprosleđivanja

3c

Međupovezivanje AS-ma

Tabela prosleđivanja se konfiguriše i saintra- i sa-AS algoritmom rutiranja

Intra-AS setuje sadržaje za interne destinacijeInter-AS & Intra-As setuje sadržaje za eksterne destinacije

Mrežni nivo 4-93

3b

1d

3a

1c2aAS3

AS1AS2

1a

2c2b

1b

3c

Inter-AS zadaciPretpostavimo da ruter u AS1 primidatagram za koji je destinacija van AS1

Ruter bi trebao proslijediti paket prema gateway ruteru ali kojem?

AS1 treba:1. Da nauči koje su

destinacije dostižne preko AS2, a koje preko AS3

2. Da proslijedi tu informaciju o mogućnosti dosezanja do svih rutera u AS1

Posao inter-AS rutiranja!

33

Mrežni nivo 4-94

Primjer: Setovanje tabele prosleđivanja u ruteru 1d

Pretpostaviti da AS1 uči od inter-AS protokola da je podmreža x dostižna preko AS3 (gateway 1c) ali ne i prekoAS2.Inter-AS protokol šalje informaciju o mogućnosti dostizanja do svih internih rutera.Ruter 1d odlučuje na bazi intra-AS informacije rutiranja da je njegov interfejs I na putu sa najmanjim troškovima do 1c.

Upisuje u tabelu prosleđivanja sledeći sadržaj (x,I).

3b

1d

3a

1c2aAS3

AS1AS2

1a

2c2b

1b

3cx…

Mrežni nivo 4-95

Primjer: Izbor između više AS-maPretpostavimo da AS1 uči od inter-AS protokola da se podmreža x može doseći i od AS3 i od AS2.Da bi konfigurisao tabelu prosleđivanja, ruter 1d mora odlučiti prema kojem gateway bi trebala proslijediti pakete za destinaciju x. Ovo je takođe posao inter-AS protokola rutiranja!Rutiranje “vrući krompir”: slanje paketa prema najbližim ruterima.

3b

1d

3a

1c2aAS3

AS1AS2

1a

2c2b

1b

3cx… …

34

Mrežni nivo 4-96




4.5 Algoritmi rutiranjaLink stateDistance VectorHierarhijsko rutiranje


RIPOSPFBGP

Mrežni nivo 4-97

Intra-AS Rutiranje

Poznato kao Interior Gateway Protocols (IGP)Najpozantiji Intra-AS protokoli rutiranja:

RIP: Routing Information Protocol

OSPF: Open Shortest Path First

IGRP: Interior Gateway Routing Protocol (vlasništvo kompanije Cisco)IS-IS: Intermediate system to intermediate system

35

Mrežni nivo 4-98






RIPOSPFBGP

Mrežni nivo 4-99

RIP ( Routing Information Protocol)

“Distance vector” algoritamUključen u BSD-UNIX od 1982Metrika rastojanja: broj hopova (maksimalno = 15)

Možete li pogoditi zašto?

DC

BA

u vw

x

yz

destinacija hopoviu 1v 2w 2x 3y 3z 2

Od rutera A do podmreža

36

Mrežni nivo 4-100

RIP oglašavanja

“Distance vector”-i: razmjenjuju se između susjeda svakih 30s preko “Response Message” (poznate kao oglašavanje)Svako oglašavanje: daje listu do 25 destinacionih mreža u okviru AS

Mrežni nivo 4-101

RIP: primjer

Destinac. mreža Sledeći ruter Broj hopova do dest.w A 2y B 2z B 7x -- 1…. …. ....

w x y

z

A

C

D B

Tabela rutiranja u D

37

Mrežni nivo 4-102

RIP: primjer

Destinac. mreža Sled. ruter Broj hopova do dest.w A 2y B 2z B A 7 5x -- 1…. …. ....

Tabela rutiranja u D

w x y

z

A

C

D B

Dest Sl. hopovaw - -x - -z C 4…. … ...

Oglašavanje od A do D

Mrežni nivo 4-103

RIP: Ispad linka i oporavakAko nema oglašavanja posle 180 s --> susjed/link se deklariše kao “mrtav”

Rute preko toga susjeda su nevalidneNova oglašavanja se šaljudrugim susjedimaSusjedi vraćaju nova oglašavanja (ako se tabele mijenjaju)Informacija o ispadu linka se brzo prenosi čitavom mrežom“poison reverse” se koriste za prevenciju ping-pong petlji (beskonačno rastojanje = 16 hopova)

38

Mrežni nivo 4-104

RIP tabele rutiranja

RIP tabelama rutiranja se upravlja procesomnivoa-aplikacije nazvanim route-d (daemon)Oglašavanja se šalju UDP segmentima (port 520),koji se periodično ponavljaju

fizičkilink

Mreža tabela(IP) prosleđ.

Transport(UDP)

Route-d

fizičkilink

Mreža(IP)

Transport(UDP)

Route-d

tabelaprosleđ.

Mrežni nivo 4-105

RIP: verzije

RIPv1 (classfull adresiranje, bez autentifikacije rutera, broadcast update ruta)RIPv2 (1994, CIDR, autentifikacija rutera,multicast update ruta)RIPng (RIPv2 sa podrškom IPv6, IPsec autentifikacija, ...)

39

Mrežni nivo 4-106






RIPOSPF i IS-ISBGP

Mrežni nivo 4-107

OSPF (Open Shortest Path First)Interior Gateway Protocol (IGP)“open”: javno dostupanVerzija 2 (RFC 2328) iz 1998Verzija 3 (RFC2740) iz 1999 podržava IPv4 i IPv6Koristi se u velikim kompanijskim mrežama zbog brze konvergencije, rješavanja problema petlji i balansiranja saobraćaja, dok operatori koriste IS-IS koji je pogodan za stabilne mrežeKoristi “Link State” algoritam

LS širenje paketaMapa topologije na svakom čvorištuProračun rute korišćenjem Dijkstra algoritmaBroadcast svakih 30min

OSPF oglašavanja nose po jednu informaciju po susjednom ruteruŠirenje oglašavanja preko čitavog AS (“flooding”)

Nose se u OSPF porukama direktno preko IP ( a ne preko TCP ili UDP) pri čemu potrebne kontrole obavlja OSPF

Radi smanjenja saobraćaja može se koristiti koncept DR (designated router) i multicasta tabele.

40

Mrežni nivo 4-108

OSPF “advanced” karakteristike (ne u RIP)

Sigurnost: za sve OSPF poruke se mora znati izvor(prevencija malicioznih aktivnosti) pri čemi se koriste lozinke ili MD5 kodiranjeViše puteva sa istim troškovima je dozvoljeno (samo jedan put u RIP)Za svaki link, više metrika troškova za različiti TOS (npr., troškovi satelitskog linka su podešeni na “nisko”za best effort; visoko za servis u realnom vremenu)Integrisana uni- i multicast podrška:

Multicast OSPF (MOSPF) koristi istu bazu podataka o topologiji kao OSPF

Hijerarhijski OSPF u velikim domenima.

Mrežni nivo 4-109

Hijerarhijski OSPF

Oblast 1Oblast 2

Oblast 3

Okosnica

Ruter na okosnici Granični ruter

Interniruteri

Graničnioblasni ruteri

41

Mrežni nivo 4-110

Hijerarhijski OSPF

Hijerarhija u dva nivoa: lokalna mreža i okosnica.Oglašavanja o stanju linka samo u lokalnoj mrežiSvako čvorište ima detaljnu topologiju mreže; samo poznaje najkraći put do mreža u drugim mrežama.

Ruter na granici lokalne mreže: “sumira” rastojanja do mreža u sopstvenoj zoni odgovornosti i to oglašava drugim ruterima na granicama lokalnih mreža.Ruteri okosnice: izvršavaju OSPF rutiranje samo naokosnici.Granični ruteri: povezivanje na druge AS.

Mrežni nivo 4-111

IS-IS (Intermediate system to intermediate system )

Interior Gateway Protocol (IGP)Koristi “Link State” algoritam

LS širenje paketaMapa topologije na svakom čvorištuProračun rute korišćenjem Dijkstra algoritma

OSI referentni model (protokol mrežnog nivoa)Poslednjih nekoliko godina je potisnuo OSPF iz operatorskih mrežaMulticast prenos LSACIDR adresiranje Ne koristi usluge IP tako da je samim tim indiferentan u odnosu na verzije IP protokolaZbog jednostavnosti generiše manji saobraćaj od OSPF tako da je pogodan za velike mrežeIntegrated IS-IS je predložen u TCP/IP arhitekturiIS-IS ruter pripada samo jednoj oblasti (Level 1, Level 2 i Level1-2)Nema okosnice

42

Mrežni nivo 4-112






RIPOSPFi IS-ISBGP

Mrežni nivo 4-113

Internet inter-AS rutiranje: BGP

BGP (Border Gateway Protocol): de facto standardVerzija 4 (RFC1771) iz 1994 je doživjela preko 20 korekcija, pri čemu je zadnja RFC4271 (iz 2006)CIDR i agregacija rutaNaslijedio EGP čime je napravljena potpuna decentralizacija InternetaMogu ga koristiti i kompanije kada OSPF nije dovoljno dobar i kada se radi o multihomed mreži (bolja redundansa).BGP omogućava svakom AS:1. Dobijanje informacije o dostižnosti sa susjednih AS-ova.2. Prosleđivanje prethodne informacije svim ruterima u okviru AS.3. Utvrđivanje “dobre” rute do podmreža baziranih na informaciji

o dostižnosti i politici.Dozvoljava podmreži oglašavanje svog prisustva ostatku Interneta: “Ovdje sam”

43

Mrežni nivo 4-114

BGP osnoveParovi rutera (BGP peer-ovi) razmjenjuju informaciju rutiranja preko semi-permanentne TCP konekcije (port 179): BGP sesijeSvakih 60s šalje keep alive porukuNapomena: BGP sesije ne odgovaraju fizičkim linkovima.Kada AS2 oglasi prefiks do AS1, AS2 obećava da će proslijediti bilo koji datagram koji je adresiran do tog prefiksa preko sebe.

AS2 može agregirati prefikse u oglašavanjima

3b

1d

3a

1c2aAS3

AS1

AS21a

2c

2b

1b

3c

eBGP sesija

iBGP sesija

Mrežni nivo 4-115

Distribuirana informacija o dostižnostiSa eBGP sesijom između 3a i 1c, AS3 šalje informaciju o dostižnosti prefiksa do AS1.1c može tada koristiti iBGP za distribuciju ove nove informacije o dostizanju prefiksa do svih rutera u AS11b može tada ponovo oglasiti novu informaciju o dostizanju do AS2 preko 1b-2a eBGP sesijeKada ruter stekne znanje o novom prefiksu, kreira sadržaj za taj prefiks u tabeli rutiranja.

3b

1d

3a

1c2aAS3

AS1

AS21a

2c

2b

1b

3c

eBGP sesija

iBGP sesija

Border router

44

Mrežni nivo 4-116

Atributi puta & BGP rute

Kada oglašava prefiks, oglašavanje uključuje BGP atribute.

prefix + atributi = “ruta”Dva važna atributa:

AS-PATH: sadrži AS-ove preko kojih je oglašavanje prefiksa prošlo: AS 67 AS 17 NEXT-HOP: Indicira specifični interni-AS ruter do next-hop AS. (Može biti više linkova od trenutne AS do next-hop-AS.)

Kada gateway ruter primi oglašavanje rute, koristipolitiku importovanja za potvrdu/odbijanje.

Mrežni nivo 4-117

BGP izbor rute

Ruter može naučiti više od jedne rute do istog prefiksa. Ruter mora odabrati rutu.Pravila eliminacije:

1. Vrijednost atributa lokalne reference: odluka politike

2. Najkraći AS-PATH 3. Najbliži NEXT-HOP ruter: “vrući krompir”

rutiranje4. Dodatni kriterijum

45

Mrežni nivo 4-118

BGP poruke

BGP poruke se razmjenjuju preko TCP.BGP poruke:

OPEN: otvara TCP vezu sa peer i vrši identifikaciju pošiljaocaUPDATE: oglašava novi put (ili odbacuje stari)KEEPALIVE održava vezu u odsustvu UPDATE-ova; takođe potvrđuje OPEN zahtjevNOTIFICATION: izvještava o greškama u prethodnoj poruci; takođe se koristi za raskidanje veze

Mrežni nivo 4-119

BGP politika rutiranja

Figure 4.5-BGPnew: a simple BGP scenario

A

B

C

W X

Y

legenda:

Mreža korisnika:

Mreža provajdera

A,B,C su mreže provajderax,w,y su korisnici (mreža provajdera)x je “dual-homed”: povezan na dvije mreže

x ne želi da se saobraćaj rutira od B preko x do C.. tako x neće oglašavati B rutu do C

46

Mrežni nivo 4-120

BGP: kontroliše ko rutira do tebe

Figure 4.5-BGPnew: a simple BGP scenario

A

B

C

W X

Y

legenda:

Mreža korisnika:

Mreža provajdera

A oglašava B put AwB oglašava X put BAwDali će B oglašavati C put BAw?

Nema šanse! B ne dobija “profit” za rutiranje CBAw pošto w i C nisu B-ovi korisniciB želi da prinudi C da rutira do w preko AB želi da rutira samo do/od njegovih korisnika!

Mrežni nivo 4-121

Zašto različito Intra- i Inter-AS rutiranje ?

Politika:Inter-AS: administrator želi kontrolu nad načinom rutiranja saobraćaja i time ko rutira kroz njegovu mrežu. Intra-AS: jedan administrator, nema potrebe za političkim odlukama

Veličina:hijerarhijsko rutiranje čuva veličinu tabele, smanjuje saobraćaj koji se odnosi na ažuriranje

Performanse:Intra-AS: može se fokusirati na performanseInter-AS: politika može dominirati u odnosu na performanse

Glava 4: Mrežni nivo - Ivan Drakic · 4.5 Algoritmi rutiranja Link state Distance Vector...

Documents

Transcript of Glava 4: Mrežni nivo - Ivan Drakic · 4.5 Algoritmi rutiranja Link state Distance Vector...