1.1 Statička dodjela kanala u LAN i MAN

• tradicionalni način dodjele jednog kanala (npr. telefonski vod) većem broju korisnika je FDM (Frequency Division Multiplexing) - jednostavan i efikasan algoritam ako je riječ o malom, stalnom broju korisnika koji ostvaruju veliki promet; inače je ili dio spektra frekvencije neiskorišten, a dio korisnika mora čekati na dodjelu kanala (iako neki korisnici manje komuniciraju, ipak zauzimaju dio dodijeljene frekvencije)
• općenito je podjela jednog kanala u više podkanala neefikasna; prosječni zastoj pri FDM podjeli kanala na N podkanala je N puta veći nego da se koristila cijela širina kanala za slanje svih okvira koji su poslani po podkanalima
• slični problemi kako kod FDM vrijede i za TDM

1.2 Dinamička dodjela kanala u LAN i MAN

• pretpostavke:

1. Model sa stanicama (station model) - model se sastoji od N neovisinih stanica (računala, telefoni,...) od kojih svaka ima program ili korisnika koji generira okvire za slanje; kada se okvir izgenerira, stanica se blokira i ne radi ništa dok se okvir uspješno ne prenese

2. Jedan kanal (single channel) - sve stanice šalju i primaju okvire po samo jednom kanalu i sve su jednake što se tiče hardvera (softver im može dodijeliti prioritete)

3. Kolizija (collision) - događaj kod kojeg se dva okvir prenose istovremeno, pa se vremenski prekrivaju i rezultat je iskrivljeni signal; sve stanice mogu ustanoviti koliziju, a tako iskrivljeni okviri moraju se prenijeti ponovo

4.a. Neprekidno vrijeme (continuous time) - prijenos okvira može započeti bilo kada, ne postoji glavni sat koji dijeli vrijeme u diskretne intervale

4.b. Vrijeme u intervalima (slotted time) - prijenos okvira počinje uvijek na početku intervala; interval može sadržavati 0 okvira (miruje), 1 okvir (uspješan prijenos) ili više okvira (kolizija)

5.a. Može se ustanoviti carrier (carrier sense) - stanica može odrediti da li se kanal već koristi i tada neće pokušavati slati nego će čekati da se oslobodi (carrier - električni signal na kabelu)

5.b. Ne može se ustanoviti carrier (no carrier sense) - stanica šalje podatke iako se kanal već koristi, a tek će kasnije odrediti da li je prijenos bio uspješan ili ne

• t - vrijeme potrebno za prijenos okvira između dvaju najudaljenijih stanica A i B
• 2 t - vrijeme povrata (turnarround time): stanica A čeka 2 t, ukoliko u vremenu stigne potvrda OK, ako ne pokušava poslati okvir ponovo
• vrijeme povrata - potrebno kod otkrivanje kolizije, uzima se prilikom određivanje duljine vremenskog intervala kod algoritama za dodjeljivanje kanala za prijenos

 

 2.1 ALOHA 

• ALOHA sistem razvijen je 70-ih godina na Univerzitetu Hawaii kao radio mreža, ali je osnovna ideja primjenjiva i za bilo koje druge sisteme u kojima se korisnici natječu za korištenje jednog kanala kojeg svi dijele
• 2 verzije koje se razlikuju po tome da li je vrijeme podijeljeno u intervale ili nije: “čista” (pure) i s vremenskim intervalima (sloted) ALOHA

a) Pure ALOHA

Slika: Slanje okvira kod "čistog" ALOHA protokola (Tanenbaum, 1996)

• kolizija se javlja uvijek kada dva okvira žele koristiti kanal u isto vrijeme, čak i ako se samo jedan bit novog okvira prekrije sa samo zadnjim bitom okvira koji je gotovo stigao
• pitanje efikasnosti ALOHA kanala, tj. koliko prenesenih okvira izbjegne koliziju pod tim “kaotičnim” uvjetima? - maksimalno iskorištenje kanala je 18%, s većim prometom raste i broj sudara, a iskorištenje pada

Slika: ALOHA: iskorištenje kanala prema opterećenju kanala (Tanenbaum, 1996)

b) ALOHA s  vremenskim intervalima (sloted)

• metoda koja udvostručuje kapacitet ALOHA sistema
• vrijeme na kanalu je organizirano u jednake vremenske intervale (slots) čija je veličina jednaka vremenu prijenosa okvira; stanice sinhronizira glavni sat (ili neka druga tehnika)
• određeno je vrijeme kada se mogu slati okviri - prijenos može početi samo na početku slijedećeg intervala, pa će se okviri koji će se prekrivati, prekrivati potpuno
• iskorištenost kanala je 37%

2.2 CSMA Protokoli

• CSMA - Carrier Sense Multiple Access grupa protokola
• carrier sense protokoli - oni protokoli kod kojih stanice osluškuju medij za prijenos tj. što rade druge stanice i ovisno o tome šalju podatke ili ne

a) Uporni (persistent) i neuporni (nonpersistent) CSMA

• kod CSMA potreban je algoritam pomoću kojeg će se odrediti što da stanica učini ako je medij zauzet; razlikuju se 3 pristupa:

I. 1-persistent CSMA  

• stanica šalje okvir sa vjerojatnošću 1 kadgod ustanovi da je medij za slanje slobodan
• pravila:

1. ako je medij slobodan, šalje

2. ako je medij zauzet, nastavlja slušati dok se kanal ne oslobodi i onda odmah šalje

3. ako dođe do kolizije, čeka slučajni vremenski interval i ponavlja 1. korak

• efikasnost protokola ovisi o kašnjenju signala koji šalju stanice (jedna stanica može poslati okvir ako nije registrirala signal druge stanice o zauzetosti kanala) - dolazi do kolizije
• primjer kolizije: 2 stanice čekaju da treća završi, te istovremeno počnu slati (stanice ne provjeravaju da li neka stanica već čeka)
• manja kolizija nego kod ALOHA protokola

 

II. Nonpersistent CSMA

• manje “sebičan” od 1-persistent CSMA
• pravila:

  1. ako je medij slobodan, šalje

2. ako je medij zauzet, čeka slučajni vremenski interval i ponavlja 1. korak

• reducira se kolizija, ali je medij djelomično neiskorišten (čeka se iako se medij već oslobodio)

 

III. p-persistent CSMA

• kompromis koji želi reducirati i koliziju i neiskorištenost medija
• primjenjuje se na kanalima podijeljenim u vremenske intervale
• p = vjerojatnost slanja (p=1=100% tj. uvijek šalje)
• pravila:

1. ako je medij slobodan, šalje sa vjerojatnošću p (čeka tj. odgađa slanje za jedan vremenski interval (slot) sa vjerojatnošću (1-p) = q); interval je obično jednak 2 t

2. ako je medij zauzet, nastavlja slušati dok se kanal ne oslobodi i ponavlja 1.

• koji p uzeti -> što je p manji, stanice dulje čekaju na slanje, ali se kolizija reducira
• kod mreža s kolizijom efikasniji su neuporni protokoli

Slika: Usporedba iskorištenja kanala (Tanenbaum, 1996)

b) CSMA/CD (CSMA sa detekcijom kolizije - Collision Detection)

• poboljšani CSMA: stanice prekidaju prijenos čim ustanove da je došlo do kolizije čime se štedi i vrijeme i propusnost
• kolizija se može ustanoviti na pr. tako da se jačina primljenog signala usporedi s poslanim signalom
• često se koristi za LAN (npr. jednu verziju koristi Ethernet)
• pravila:

1. ako je medij slobodan, A odmah šalje
2. ako je medij zauzet, A nastavlja osluškivati medij i čim se oslobodi šalje
3. ako se ustanovi kolizija za vrijeme prijenosa, A šalje kratki signal kako bi sve ostale stanice saznale za koliziju
4. nakon slanja signala, čeka slučajan vremenski interval (naziva se period odustajanja - backoff) i ponavlja korak 1.

Slika: CSMA/CD stanja; borba za medij, slanje, mirovanje (Tanenbaum, 1996)

• model za CSMA/CD sastoji se od izmjenjivanja perioda borbe za medij (contention) i perioda prijenosa (transmission) s periodima mirovanja stanica (idle)
• osnovno pitanje je koliko dugo treba stanicama da ustanove da je došlo do kolizije (o tome ovisi dužina contention perioda, te propusnost)
• primjer 1:
  • t₀ - A šalje
  • t₁ - B i C su spremni za slanje, C šalje jer nije ustanovio da A šalje
  • t₂ - C ustanovio koliziju i prekinuo prijenos
  • t₃ - A ustanovio koliziju kad mu je stigao signal od C

Slika: CSMA/CD (Stallings, 2004)

Slika: utvrđivanje kolizije (Tanenbaum, 1996)

• važno pravilo za CSMA/CD sisteme: okviri moraju biti dovoljno dugački (tj. definira se min. dužina svih okvira) da se dozvoli otkrivanje kolizije prije kraja prijenosa tj. treba se osigurati da je vrijeme povrata za sve okvire 2t
• do kolizije može doći za vrijeme perioda natjecanja (contention), to nastoji riješiti slijedeća grupa protokola: nekolizijski (Collision-Free) protokoli

2.3 Nekolizijski (Collision-Free) protokoli

• rezervacijski protokol kod kojeg nakon faze prijenosa slijedi faza rezervacije, a ne borbe za medij
• vremenski gubitak je veći jer svaka stanica mora čekati na svoj red da bi izvršila rezervaciju
• primjeri: bit-map protokol, binary countdown

2.4 Protokoli sa ograničenim natjecanjem za medij (Limited-Contention) 

• 2 načina mjerenja performansi: zastoj (duži periodi čekanja) kod malog prometa i iskorištenje kanala (broj ponovnih slanja okvira zbog kolizije) kod velikog prometa
• natjecateljski (npr. ALOHA) su dobri kada je promet mali jer je tada manji zastoj (kraći periodi čekanja na slanje)
• nekolizijski su dobri kod velikog prometa jer je tada bolja iskorištenost kanala (manje kolizija)
• limited-contention protokoli su kombinacija natjecateljskih (contention) i nekolizijskih (collision-free) protokola
• stanice se dijele u grupe i kada je promet velik samo ih se nekoliko (ili čak samo 1 stanica) može natjecati za slanje podataka (ostale čekaju), a kada je promet mali može se natjecati više stanica