• zadaci mrežnog sloja:
  • osiguravanje usluge za prijenosni sloj (transport)
  • poznavanje organizacije podmreže
  • usmjeravanje paketa
  • upravljanje zakrčivanjem podmreže
    • biranje optimalnih puteva kako neki ne bi bili preopterećeni, a drugi bez prometa
  • povezivanje mreža - vođenje računa o problemima kada su stanice u različitim mrežama
     

Osnovne funkcije:

1. Usmjeravanje (routing)

• najvažnija funkcija
• algoritmi za usmjeravanje su dio softvera mrežnog nivoa i odgovorni su za donošenje odluke po kojoj će se izlaznoj liniji paketi prenositi

2. Kontrola zakrčenja (congestion control)

• zakrčivanje podmreže javlje se kada je dolazeći promet veći od kapaciteta izlaznih linija, pa je u podmreži previše paketa i neki se počinju gubiti
• razlikuje se od kontrole toka (sloj prijenosa podataka) gdje brzi pošiljaoc šalje podatke sporom primaocu; ovdje se gleda ukupni promet na mreži
• kontrola zakrčivanja povezana je sa usmjeravanjem jer je glavni razlog zakrčivanja loše usmjeravanjem

3. Povezivanje mreža (Internetworking)

• izvorišna i odredišna stanica su u različitim mrežama, pa je potrebano usmjeravanje kroz međumreže, a sve te mreže mogu koristiti različite protokole (treba vršiti pretvaranje paketa koji prelaze iz mreže u mrežu)

1.1 Usluge za prijenosni sloj 

• sučelje (interface) između prijenosnog i mrežnog sloja predstavlja granicu podmreže, tj. to je sučelje između korisnika i prijenosnika (carrier) i mora biti posebno dobro definirano
• najčešće se usluga mreže naplaćuje
• ciljevi pri dizajnu usluga mrežnog sloja su:

1. usluge moraju biti neovisne o tehnologiji podmreže
2. na prijenosni sloj ne smije utjecati broj, tip, i topologija podmreža
3. mrežne adrese za prijenosni sloj moraju imati jedinstveni način označavanja i kroz LAN i kroz WAN

• temeljno pitanje je gdje impelmentirati složenost: u podmrežu (mrežni sloj) ili hostove (prijenosni sloj):
  • pristaše hostova: ističu da sve jeftinija i jača računala mogu vršiti potrebne funkcije; brzina i primjena u stvarnom vremenu im je važnija od točnosti (na pr. za digitalni govor)
  • pristaše podmreže: ističu kako korisnici ne žele da se složeni protokoli prijenosnog sloja izvršavaju na njihovim računalima; žele pouzdanu uslugu

• 2 pristupa organizacije podmreže, to jest 2 tipa usluga:

1. pouzdana spojna (connection-oriented) servis - mrežni sloj tj. podmreža osigurava pouzdani prijenos (ATM mreže, telefonske kompanije)
2. nepouzdana bespojna (connectionless) - provjeru greški i toka vrši prijenosni sloj tj. krajnje stanice ili hostovi (Internet - besplatna bespojna usluga)

1.2 Unutrašnja organizacija mrežnog sloja (podmreže)

• 2 različite filozofije za organizaciju podmreže:
  • virtualna veza (virtual circut): veza kod spojne organizacije 

    - kod uspostavljanja veze izabire se jedna ruta od pošiljaoca prema primaocu i ona se koristi za cijelo vrijeme trajanja veze
     

  • datagramska podmreža: slanje paketa kod nespojne organizacije

    - svaki paket šalje se posebno i može imati drugačiju rutu

    - podmreža ima više posla, ali se lakše prilagođava ispadima i zakrčenjima
     

• usporedba datagramske podmreže i podmreže s virtualnim vezama:

• kompromisi:

- između memorijskog prostora čvora i propusnosti mreže (kod datagrama adrese polazišta i odredišta su sadržane u paketima, a kod virtualnih veza u tablici u ruterima)

- između vremena uspostavljanja veze i provjeravanja adrese paketa (duže uspostavljanje virtualne veze, ali kraće upućivanje na odredište; obrnuto kod datagrama)

• bez obzira da li se ruta bira posebno za svaki paket ili samo jednom kod uspostavljanja veze, algoritam usmjeravanja mora biti točan, jednostavan, stabilan, robustan (da izdrži sve promjene u topologiji i prometu), nepristran (da svi imaju priliku za slanje) i optimalan (da broj skokova paketa bude što manji jer se tako smanjuje kašnjenje i isto povećava i propusnost)
• algoritmi se dijele u dvije glavne grupe:

1. Neadaptivni (nonadaptive) algoritmi (statičko usmjeravanje) - ne donose svoju odluku na osnovu mjerenja ili procjene prometa i topologije, nego stazu biraju unaprijed (off-line) i šalju je svim čvorovima kod podizanja mreže
2. Adaptivni (adaptive) algoritmi  (dinamičko usmjeravanje) - kod donošenja odluke prilagođavaju se promjenama u prometu i topologiji, a razlikuju se po tome:
   • gdje prikupljaju informacije (od susjednih čvorova ili od svih)
   • kada mijenjeju stazu (svakih T sekundi, kada se mijenja promet ili topologija)
   • koja mjera se uzima za optimizaciju (udaljenost, broj skokova, procijenjeno vrijeme prijenosa,...)

Princip optimalnosti 

• "ako je čvor J na optimalnoj stazi od čvora I prema K, onda je i optimalna staza od J prema K na toj istoj stazi":

I ------ J ------ K

• posljedica principa: skup optimalnih staza od svih izvora prema danom odredištu čini stablo sa korijenom u odredištu - sink tree (ne mora biti jedinstveno)
• cilj svih algoritama za usmjeravanje je pronaći i koristiti stablo za sve čvorove jer će se po njemu svaki paket dostaviti u konačnom broju skokova (stablo -> nema petlji)

Slika: Podmreža i stablo čvora B (Tanenbaum, 1996)

Statički algoritmi 

2.1 Usmjeravanje po najkraćem putu (Shortest Path Routing) 

Primjer:

• ako je mjera broj skokova, staze ABC i ABE su jednako duge
• ako je mjera udaljenost u km, ABC je duža od ABE

Slika: Primjer za usmjeravanje po najkraćem putu (Tanenbaum, 1996)

• računa se najkraća staza od A do D (mjera je udaljenost)

• udaljenost se mjeri od "radnog" čvora

• uz svaki čvor se navodi udaljenost i čvor od kojeg se vršilo označavanje - na kraju se može rekonstruirati najkraća staza

• rezultat: A - B - E - F - H - D

2.2 Plavni algoritam (Flooding) 

• svaki dolazeći paket šalje se po svakoj izlazećoj liniji osim po onoj po kojoj je došao
• tako je uvijek izabran i najkraći put, ali je veliki broj dupliciranih paketa
• selektivni flooding - paketi se ne šalju po svim linijama nego samo po onima koje idu približno u pravom smjeru
• prednost: robustan algoritam (lako izdrži sve promjene u topologiji i prometu) - na pr. za vojnu primjenu

2.3 Ruting na osnovu toka (Flow-Based Routing) 

• statički algoritam koji uzima u obzir i topologiju mreže i promet po njoj jer je u nekim mrežama prosječni tok podataka između svakog para čvorova relativno stalan i predvidiv
• osnovna ideja pri analizi: ako se zna kapacitet i prosječni tok linije, moguće je izračunati prosječni zastoj paketa na osnovu teorije stoga (queueing theory); na taj se način lako izračuna prosječni zastoj cijele podmreže i traži se algoritam koji proizvodi tu vrijednost minimalniom
• moraju se unaprijed poznavati: topologija podmreže, matrica prometa, matrica kapaciteta linije, algoritam koji će se koristiti
• za računanje se može koristiti program koji isprobava sve moguće rute, potrebno je dosta vremena ali se može vršiti off-line

Dinamički algoritmi 

2.4 Usmjeravanje vektorom udaljenosti (Distance Vector Routing) 

• Bellman-Ford ili Ford-Fulkerson algoritam, originalni algoritam u ARPANET
• ideja čvorovi periodično izmjenjuju informacije o usmjeravanju sa susjedima
• svaki čvor održava tablicu (vektor) indeksiranu po svakom čvoru podmreže (ima po jedan ulaz za svako odredište)
• ulaz se sastoji od 2 dijela:
  • izlazna linija prema odredištu
  • procjenjena mjera udaljenosti do odredišta (vrijeme, ili udaljenost u km, kašnjenje, ukupan broj paketa na stazi,...)
• pretpostavlja se da čvor zna mjeru do svog susjeda (na pr. ako je mjera broj skokova, vrijednost je 1)
• tablice se stalno ažuriraju i razmjenjuju sa susjedima
• izvođenjem računanja za tablicu svakog susjeda, čvor može pronaći koju liniju je najbolje koristiti

Primjer:

• mjera je kašnjenje (zastoj)
• svake T msec svaki čvor J šalje svakom svom susjedu listu procijenjenih kašnjenje za svako odredište (ujedno i prima takve liste od susjeda)
• J ažurira tablicu:
  • susjed X poslao tablicu u kojoj X_i označava procjenu kašnjenja od X prema čvoru i
  • ako je m kašnjenje od J do X, onda je m + X_i kašnjenje od J prema čvoru i
  • ako je vrijeme m + X_i manje od onog koje već u tablici od J piše za i, stavlja se novo vrijeme

Slika: Primjer za usmjeravanje vektorom udaljenosti (Tanenbaum, 1996)

2.5 Usmjeravanje stanjem veza (Link State Routing) 

• ARPANET od 1979. zamjenjuje usmjeravanje vektorom udaljenosti ovim algoritmom
• razlozi toj zamjeni su što su u početku sve linije bile istog kapaciteta od 56 kbps (nije bilo potrebno uzeti u obzir propusnost) te sporost distance vector routinga
• kod link state usmjeravanja svaki čvor mora:

1. otkriti svoje susjede i naučiti njihove adrese - slanjem HALLO paketa po svakoj point-to-point liniji
2. izmjeriti zastoj do svakog susjeda - slanjem ECHO paketa kojeg druga strana vraća odmah čim ga primi
3. napraviti paket pomoću kojeg će reći ostalima što je saznao - to vrši periodički ili kad se pojavi neki značajni događaj (npr. pad nekog čvora)
4. poslati taj paket svim ostalim čvorovima - na kraju svaki čvor ima čitav skup link state paketa
5. izračunati najkraći put do svakog drugog čvora - nekim algoritmom se računa najkraći put za sva moguća odredišta (na pr. Dijkstra)

• za podmrežu s n čvorova od kojih svaki ima k susjeda, memorija potrebna za spremanje podataka proporcionalna je s nk

2.6 Hijerarhijsko usmjeravanje (Hierarchical Routing) 

• usmjeravanje se vrši hijerarhijski kada je mreža toliko velika da svaki čvor ne može imati podatke za svaki drugi čvor, pa se čvori grupiraju u regije
• svaki čvor zna kako proslijediti paket unutar svoje regije, ali ne zna unutrašnju strukturu drugih regija
• svaka takva regija promatra se kao 1 čvor , pa u tablici postoje reci koji odgovaraju drugim čvorima u istoj grupi i drugim regijama
• za velike mreže vrši se hijerarhija na više nivoa

Primjer:

Slika: Primjer za hijerarhijsko usmjeravanje (Tanenbaum, 1996)

2.7 Usmjeravanje za pokretne (mobile) hostove 

• da bi se proslijedio paket pokretnom hostu, mreža ga prvo mora naći
• pokretni korisnik ima svoju stalnu kućnu lokaciju i adresu koja se koristi za slanje paketa
• geografska podjela na područja od kojih svako ima svog forein agent koji pazi na pokretne korisnike koji ulaze u to područje, te home agent koji paze na korisnike koji inače pripadaju tom području, ali su trenutno van njega
• pokretni host se mora registrirati kod forein agent područja u kojem se nalazi, a on uspostavlja vezu sa home agent područja u kojem je kućna lokacija hosta

2.8 Broadcast usmjeravanje 

• koristi se kada je potrebno da se paket istovremeno pošalje na više ili na sva odredišta
• može se vršiti na više načina:

- svima se šalje druga kopija paketa

- plavljenje (flooding)

- usmjeravanje na više odredišta (multidestination routing): svaki paket ima listu odredišta, kad stigne u čvor, provjerava se lista i čvor određuje skup potrebnih izlaznih linija (tj. onih koje su najbolja staza za barem 1 odredište); čvorovi šalju dalje po tim linijama kopije paketa čija lista odredišta sadrži samo one prema kojima linija vodi; na kraju ostaje samo jedno odredište (kopija kao obični paket)

- koristi se spanning tree - podskup podmreže koji uključuje sve čvorove, ali je bez petlji; čvor kopira pakete po svim linijama koje pripadaju tom stablu, osim po onoj po kojoj je paket došao, a za obilaženje stabla mogu se koristiti različiti algoritmi

2.9 Multicast usmjeravanje  

• multicasting je slanje poruka grupama čvorova koje su same po sebi velike, ali su u odnosu na čitavu mrežu male
• čvorovi moraju znati u kojoj su grupi njihovi hostovi i te podatke šalju čvorovima-susjedima, pa se tako te informacije šire kroz podmrežu
• kod ovog usmjeravanje svaki čvor računa spanning tree za sve ostale čvorove u podmreži
• kad se pošalje multicast paket za neku grupu, čvor makne linkove u stablu koji vode do čvor koji nisu u grupi

Slika: Primjer multicast usmjeravanje (Tanenbaum, 1996)

• zakrčenje (congestion) - u mreži je previše paketa što degradira performanse

Slika:  Previše prometa u mreži dovodi do zakrčnja (Tanenbaum, 1996)

• dok je prijenos manji od prijenosnog kapaciteta podmreže, broj dostavljenih paketa proporcionalan je broju poslanih
• kod prejakog prometa dio poslanih paketa se gubi
• kod vrlo jakog prometa skoro niti jedan paket nije dostavljen (zakrčenje)

• razlozi zakrčenja:
  • paketi stižu s nekoliko ulaznih linija, a moraju se dostaviti po istoj izlaznoj liniji
  • spori procesori čvorova
  • linije s malom propusnošću (potrebno izbalansirati sve komponente sustava)

   

• zakrčenje ima tendenciju da se sve više i više pojačava:
  • ako čvor nema slobodnih buffera, ignorira dolazeće pakete
  • čvor koji ih šalje ponavlja slanje (nije dobio povrdu)
  • spreminci čvora koji šalju ostaju puni, pa se tako zakrčenje vraća unatrag
• kontrola zakrčenja se razlikuje od kontrole toka gdje brzi pošiljaoc šalje podatke sporom primaocu (gleda se point-to-point promet); ovdje se gleda ukupni promet na mreži

3.1 Općeniti principi kod kontrole zakrčenja 

• načini kontrole se mogu podijeliti u dvije grupe: kontrola s otvorenom petljom (open loop) i s zatvorenom petljom (close loop)

Kontrola s otvorenom petljom (upravljanje)

• problem se nastoji riješiti tako da se dobrim dizajnom unaprijed osigura da do njega ni ne dođe
• odluka se donosi bez obzira na trenutno stanje mreže
• planira se: kada će se prihvatiti novi paketi, pa kada odbaciti, koji će se paketi odbaciti, kako će se vršiti raspoređivanje u raznim točkama mreže

Kontrola sa zatvorenom petljom (regulacija)

• kad dođe do problema, poduzimaju se koraci za njegovo rješavanje što se kod kontrole zakrčenja sastoji od 3 koraka:

1. promatra se sistem da se ustanovi kada i gdje se javilo zakrčenje - različite mjere za promatranje podmreže i otkrivanje zakrčenja: postotak odbačenih paketa, prosječna duljina redova (queue), broj paketa koji se šalju ponovo jer je vrijeme isteklo, prosječno kašnjenje paketa
2. te informacije se šalju na mjesta gdje će se poduzeti akcija - može se poslati posebni paket s obavijesti, uključiti u posebno polje običnih paketa, periodički slati posebni probni paket koji ispituje zakrčenje
3. prilagoditi će se sistem tako da se problem riješi - hostovi poduzimaju određene akcije da reduciraju zakrčenje

• algoritmi za kontrolu isto se dijele na algoritme s otvorenom i zatvorenom petljom

Algoritmi s otvorenom petljom

• djeluju kod pošiljaoca
• djeluju kod primaoca

Algoritmi sa zatvorenom petljom

• eksplicitna povratna informacija (feedback) - paketi se šalju natrag od točke zakrčenja da se upozori pošiljaoc,
• implicitna povratna informacija (feedback) - pošiljaoc sam, vlastitim opažanjem (na pr. kašnjenja potvrde) ustanovi da je došlo do zasićenja

• 2 rješenja kod zakrčenje:
• povećati resurse - koristiti dodatnu propusnost, druge rute, rutere koji se inače koriste za backup...
• smanjiti promet - nekim korisnicima otkazati ili smanjiti neke usluge...

3.2 Oblikovanje prometa (Traffic Shaping) 

• jedan od glavnih uzroka zagušenja je promet u “rafalima” (bursty traffic)
• oblikovanje prometa želi regulirati i ujednačiti tok prometa
• kod postavljanja virtualnih kanala korisnik i prijenosnik (carrier) dogovaraju oblik prometa, kasnije se treba promatrati da li se korisnik drži dogovora i poduzeti određene akcije ako se ne drži
• lakše se realizira kod virtualne veze nego kod datagramske

Algoritam “kabao koji propušta” (Leaky Bucket Algorithm) 

• algoritam otvorene petlje
• svaki host je povezan na mrežu preko sučelja koje sadrži stog konačne veličine (kabao)
• kad paket stigne dodaje se na stog, osim ako stigne na već puni stog (tada se odbacuje)
• izlazni tok je konstantan bez obzira koliko je vode u kabelu (tj. paketa u stogu)

Slika:  Algoritam “kabao koji propušta” (Tanenbaum, 1996)

• algoritam kabla koji propušta: sustav stoga s jednim poslužiteljem i konstantnim vremenom posluživanja
• ako su paketi jednake duljine, host periodički postavlja po jedan paket na mrežu
• ako su paketi različite duljine, periodički se šalje fiksni broj bytova

Algoritam "kabao sa znakovima" ( Token Bucket Algorithm) 

• algoritam otvorene petlje
• fleksibilniji algoritam od prethodnog koji dozvoljava da se izlaz nešto ubrza kad je promet jači (dozvoljava “rafale” do neke maksimalne dužine), sprečava i gubitak podataka
• kabao sadrži znakove (token) koji se periodički generiraju jedan po jedan (nakon svakog određenog broja sekundi)
• da bi se paket proslijedio, mora uhvatiti i uništiti jedan znak: 1 znak je dozvola za slanje 1 paketa (varijanta: 1 znak je dozvola za slanje k bytova)
• algoritam dozvoljava da se skupi veći broj znakova i tako pošalje veći snop paketa (do maksimalne veličine kabela)
• ovaj algoritam nikada ne odbacuje pakete, kada se kabao popuni, bacaju se tokeni
• implementacija:
  • varijabla koja broji znakove
  • brojač se povećava za 1 svakih ∆T i smanjuje za 1 svaki put kad se paket pošalje
  • ako je brojač 0, ne može se poslati niti jedan paket

Slika:  Algoritam “kabao sa znakovima” (Tanenbaum, 1996)

3.3 Specifikacija toka (Flow Specification) 

• specifikacija toka je dogovor pošiljaoca, primaoca i podmreže o točnoj specifikaciji oblika prometa - određuju se karakteristike prometa i kvaliteta usluga potrebnih za aplikacije
• ideja: prije nego što se uspostavi veza (ili počne slati niz datagrama) izvor traži od podmreže da odobri specifikaciju)
• podmreža prihvaća, odbija ili daje drugi prijedlog

3.4 Kontrola zasićenja kod podmreža s virtualnim vezama 

• algoritam zatvorene petlje
• kontrola pristupa (admission control) - kad se ustanovi zasićenje, ne uspostavljaju se novi virtualni kanali dok se problem ne riješi
• sličan je način kada se dozvoljavaju novi kanali, ali se vode dalje od problematičnih mjesta:

Slika:  Kontrola pristupa (Tanenbaum, 1996)

• još jedna strategija kod virtualnih veza:
  • prije uspostavljanja virtualnih kanala host i mreža se dogovaraju o količini i obliku prometa, kvaliteti usluga i o ostalim parametrima
  • resursi se unaprijed rezerviraju i izbjegava se zasićenje
  • dogovaranje se najčešće vrši kad je podmreža već zakrčena

3.5 Prigušeni paketi (Choke Packets) 

• pristup koji se koristi i za podmreže sa virtualnim vezama i za datagramske podmreže
• čvor promatra postotak iskoristivosti izlaznih linija i u slučaju opterećenja šalje prigušeni (choke) paket natrag izvoru koji reducira slanje paketa prema tom čvoru za određeni postotak
• čvor može svakoj izlaznoj liniji pridružiti vrijednost u između 0 i 1 koja opisuje iskoristivost linije, u se računa prema unaprijed odabranim formulama, a ovisi o karakteristikama čvora i linija
• ako je u veće od nekog zadanog praga, linija je u stanju alarma i tada šalje prigušeni paket prema izvoru
• originalni paket se označava (kako ne bi ponovo generirao prigušen paket) te se prosljeđuje dalje
• kad izvor dobije prigušeni paket, smanjuje promet prema naznačenom čvoru
• neko vrijeme ignorira ostale prigušene pakete od tog čvora
• zatim osluškuje ponovo da li mu je stigao prigušeni paket, ako nije može opet povećati tok paketa prema čvoru

• varijante algoritma:
• pošteno stavljanje u red (fair queueing)
  • koristi se kako bi se osiguralo da svi hostovi koji šalju podatke prema čvoru ravnopravno smanje slanje paketa
  • čvorovi imaju više stogova za svaku izlaznu liniju (po jedan stog za svaki izvor)
  • kad linija postane mirna, čvor ciklički obilazi stogove i uzima prvi paket sa slijedećeg stoga - ciklički se dodjeljuje izlazna linija za slanje po jednog paketa
• prigušeni paketi po skokovima (hop-by-hop choke packets)
  • kod velikih udaljenosti slanje prigušenih paketa nema efekta zbog prespore reakcije
  • koriste se prigušeni paketi po skokovima tj. svi hostovi na putu između izvora i hosta kod kojeg je došlo do zagušenja isto primaju prigušeni paket i reduciraju slanje

3.6 Odbacivanje (Load Shedding) 

• čvorovi odbacuju pakete koje ne mogu primiti, koje će pakete odbaciti ovisi o aplikacijama koje se izvršavaju
• aplikacije moraju označiti svoje pakete klasama prioriteta, tako da se prvo odbacuju paketi u najnižoj klasi (najmanje važni)