Otp - 8-topologija

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije A. TELEKOMUNIKACIJSKE MREŽE, TOPOLOGIJA I SISTEMI POSLUŽIVANJA A.1 Mreže, modeli i tokovi 1. Kapaciteti i tokovi u mreži U telekomunikacijskim i informacijskim mrežama je bitno poznavati kapacitete između definisanih tačaka ili kapacitet cjelokupne mreže. Kapacitet je, po definiciji, jednak iznosu maksimalnog toka koji može proticati između posmatranih tačaka mreže. ¾ serijska struktura

C1T(1)

C2T(2)

CMT(M) N

1 Slika 1. Serijski kapacitet

Kapacitet serijske strukture sastavljene od M različitih kapaciteta (slika 1.), određen je najmanjim u nizu tj. C1N = min {C i }

(1)

i =1,..., M

Informacijska jedinica prolaskom kroz serijski slijed kapaciteta zadržava se na svakom od njih T(i) vremenskih jedinica, i = 1, 2, ..., M , tako da je:

T (i ) =

1 Ci

[s ]

(2)

vrijeme potrebno da se obavi zadana operacija i-tog elementa na promatranoj informacijskoj jedinici. Neka je T (i ) konstantno za svaku informacijsku jedinicu. Ukupno vrijeme prolaza jedne informacijske jedinice kroz sistem iznosi: M

T1 = ∑ T (i ) = ∑ i =1

i

1 Ci

(3)

Za informacijski tok od L informacijskih jedinica vrijeme prolaza kroz sistem biće: T = ∑ T (i ) + (L − 1) max{Ti }

(4)

i

Osnove telekomunikacija 1

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

jer nakon prolaza čela informacijskog toka za koje je potrebno vrijeme T1 nastupa gomolanje na onom elementu sa maksimalnim vremenom potrebnim za obavljanje operacije: 1 max{Ti } = Tmax = (5) Cmin Maksimalna propusnost sistema za L jedinica se izražava kao: PR(L )max =

L L = T T1 + (L − 1) ⋅ Tmax

(6)

Za beskonačni slijed jedinica, koje čine neprekinuti tok, L → ∞ , a T1 je mnogo manje od L ⋅ Tmax , pa izraz (6) prelazi u oblik: PR1 max =

L 1 ⎡ erl ⎤ = L ⋅ Tmax Tmax ⎢⎣ s ⎥⎦

(7)

Ako je prosječna dužina informacijske jedinice b bita, slijedi kapacitet serijskog niza: C1N = b ⋅ PR1 max =

b ⎡ erl ⎤ = min {C i } ⎢ ⎥ , Tmax ⎣ s ⎦ i

(8)

a što je i bilo pretpostavljeno izrazom (1). ⎡ erl ⎤ Neka je intenzitet nailazaka informacijskih jedinica γ ⎢ ⎥ kao srednja vrijednost ⎣ s ⎦ slučajnog procesa, tada propusnost za informacijske jedinice možemo izraziti kao: ⎧ 1 ⎫ PR1 = min ⎨γ , ⎬, ⎩ Tmax ⎭

(9)

odnosno propusnost za informacijski tok: PR = min{b γ , C}

(10)

Osnove telekomunikacija 2

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije ¾ paralelna struktura

C1 C2

1

2

CM C, T

Slika 2. Paralelni kapacitet Za paralelnu strukturu, slika 2, ukupni kapacitet je jednak zbiru svih paralelnih iznosa: M

C12 = ∑ C i . i =1

¾ složena struktura

Za strukturu prema slici 3., koja ima oblik jednostavne mreže, kapacitet između tačaka 1 i 4 nije moguće odrediti u opštem obliku. C1(200)

ϕ ul = 250

C4(100) f4=100

f1=150

C3(50) f3=150

1 C2(100)

ϕ izl = 250 4

C5(200)

f2=100

f5=150 C

Slika 3. Složena struktura Za ovaj slučaj će nam poslužiti pravilo minimalnog reza – maksimalnog toka, koje je osnovno pravilo u analizi i sintezi informacijskih mreža. Osnove telekomunikacija 3

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

Ovo pravilo glasi: -

Kapacitet između izvorišne i odredišne tačke neke mreže jednak je kapacitetu minimalnog reza.

Minimalni je rez, uklanjanje onih elemenata iz mreže koje će uzrokovati potpuni prekid između izvorišne i odredišne tačke, a da zbir uklonjenih elemenata bude minimalan. Iznos maksimalnog toka od izvorišne do odredišne tačke jednak je kapacitetu minimalnog reza. Za mrežu sa slike 3., kapacitet će biti određen kao: C14 = min{C1 + C 2 , C1 + C 3 + C 5 , C 2 + C 3 + C 4 , C 4 + C 5 } Iz navedenog slijedi da je za određivanje kapaciteta između dvaju tačaka j i k mreže potrebno poznavati vrijednosti pojedinih kapaciteta i provesti traženje minimalnog reza: C jk = min rez{C i }, i = 1, 2, ..., M .

Primjer: Kapaciteti. C1 + C 3 + C 5 = 450 C 2 + C 3 + C 4 = 250 , C 4 + C 5 = 250 C1 + C 2 = 300 ,

C14 = min rez{300, 450, 250, 250} , C14 = 250 = C 2 + C 3 + C 4 .

Vrijednost kapaciteta Ci i raspored unutrašnjih tokova fi za slučaj maksimalnog toka prikazani su na istoj slici. Zaključak:

Ukupni tok se kreće 0 ≤ ϕ ul ≤ C14 = 250 (b / s ) . U području 0 ≤ ϕ ul ≤ 100 tok se najkraćim putem može prenijeti preko kapaciteta C2 i C5 ili C1 i C4. Za područje 100 ≤ ϕ ul ≤ 200 treba upotrijebiti C2 i C5 i C1 i C4, a u području 200 ≤ ϕ ul ≤ 250 , treba upotrijebiti i put C1, C3, C5. Ovje je važno istaći i važnost spojnih tačaka. U telekomunikacijskoj mreži spojne tačke imaju funkciju prikupljanja i sabiranja tokova i njihova usmjeravanja prema Osnove telekomunikacija 4

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

neiskorištenim kapacitetima. Te tačke nazivamo komutacijskim čvorištima mreže, a njihova je funkcija usmjeravanje ili komutacija informacijskih tokova. Pretpostavićemo da je kapacitet komutacijskih čvorova zasad neograničen. Sa slike je vidljivo da je uz veličinu ulaznog toka vezan raspored unutrašnjih tokova f1 - f5, koji teku kroz pojedine kapacitete. Uz ovakve odnose može se uvesti pojam zasićenja kapaciteta u slučaju kada je C i − f i = 0 . Za slučaj maksimalnog toka, kapaciteti koji ulaze u min. rez su zasićeni. Međutim, izvan minimalnog reza postoji još preostalog kapaciteta. Ovo dovodi do zaključka da se i preostali kapacitet može iskoristiti za prihvatanje tokova u drugim smjerovima, npr. 1 - 2, 3 - 4 za naš primjer. Tako će u opštem slučaju telekomunikacijske mreže unutrašnji tokovi biti višekomponentni, sastavljeni od dijelova koji pripadaju tokovima različitih izvorišta i odredišta, pa će postupak nalaženja minimalnog reza - maksimalnog toka biti potrebno provoditi za sve parove čvorišta.

Osnove telekomunikacija 5

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije A.2. Telekomunikacijski sistem kao informacijska mreža. 1. Mreže i algoritmi Telekomunikacijska mreža po svojoj formalnoj strukturi može se razmatrati kao općenita mrežna struktura sastavljena od skupine čvorova i grana. Primjena mrežnih modela omogućuje prikaz slijeda događaja, odražava tehnološku šemu, kao i organizaciju strukture. Modeliranje pomoću tokova u mreži ima širu primjenu i ovdje ćemo se koristiti onim modelima i metodama koji su prikladni za analizu i sintezu mreža. Kod toga ćemo stohastički karakter informacijskih tokova, nakon što ustanovimo njihova svojstva nadomjestiti determinističkim parametrima, kao što su srednje vrijednosti pojedinih veličina, varijanse i momenti višeg reda. Na ovaj način će biti moguće primijeniti neke rezultate dobivene analizom determiniranih mreža, ali imajući u vidu stohastički karakter pojave. Metode koje rješavaju probleme optimalne raspodjele tokova u mreži, dio su područja matematičkog programiranja i nazivamo ih metodom mrežnog programiranja.

Za primjenu u telekomunikacijskim mrežama najznačajnija su rješenja dvaju problema: • •

problem najkraćeg puta, i problem maksimalnog toka.

Kod problema najkraćeg puta, iz mreže izdvajamo dva čvora: • •

izvorišni i odredišni.

Težinsku vrijednost pojedine grane razmatramo kao njezinu duljinu. Između izvorišnog i odredišnog čvora mogu postojati različiti putevi, sastavljeni od serijskog niza grana. Put koji ima najmanju duljinu (ukupna je cijena najmanja) nazivamo najkraćim putem. Kod problema maksimalnog toka kao jedinstveni parametar uzimamo kapacitet grane. Problem se sastoji u tome da nađemo maksimalni tok koji može protjecati mrežom između nekog izvorišnog i nekog odredišnog čvora. Navedena dva problema se kompliciraju u mrežama zbog toga što obično treba naći najkraće puteve između svih parova čvorova, a jednako tako i maksimalne tokove. Rješenja tih problema dovode do toga da pojedine grane ulaze u sastav više puteva i da kroz jednu granu teku viševrsni tokovi (tokovi koji pripadaju različitim parovima izvor – odredište), što onda nazivamo problemima rješavanja multitokova u mreži. Tri su osnovna projektna parametra koji udređuju svojstva telekomunikacijske mreže: • • •

topologija, tokovi i kapaciteti. Osnove telekomunikacija 6

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije ¾ topologija mreže Topologija mreže je određena skupom čvorova i skupom grana koje povezuju čvorove. Čvor j element je skupa čvorova V = {1, 2, ... , j , ... , N } . Granu možeo odrediti kao uređeni par čvorova ( j , k ) odnosno kao element i iz skupa grana E = {1, 2, ... , i, ... , M } .

Možemo govoriti i o usmjerenoj grani i ( j , k ) kao grani u kojoj je izvorišni čvor j, a odredišni k. Grani može biti pridodana težinska vrijednost koju nazivamo duljina grane l jk ili li . Za mrežu u cjelosti možemo formirati skupove izvorišnih i odredišnih čvorova: S = {S1 , S 2 , ... , S N } , O = {O1 , O2 , ... , O N } , gdje su S i i Oi odgovarajući izvorišni i odredišni čvor i-te grane. Topologija se može zadati i [ j , k ] matricom veličine NxN , čiji elementi prikazuju indekse grana koje povezuju j-k čvorove ili kapacitet ili težine tih grana. ¾ tokovi u mreži Tok u grani je osnovna numerička varijabla koja se pojavljuje u većini projektnih i optimizacijskih problema vezanih za mreže. Tokove u granama označavamo skupom brojeva f i , i = 1, 2, ..., M . Tok u i ( j , k ) grani ćemo označavati kao f i ili f jk . Pri opisu tokova u mrežama osnovni

je uslov o očuvanju toka u čvoru, tj. zbir veličina svih tokova koji ulaze u neki čvor mreže mora biti jednak zbiru veličina svih tokova koji izlaze iz čvora. Cjelokupnost tokova mreže opisujemo vektorom f = f1 , f 2 , ... , f M . ¾ kapacitet mreže Veličinu Ci , koja ograničava maksimalnu veličinu toka u i-toj grani, nazivamo kapacitetom:

f i ≤ Ci . Kapacitet cjelokupne mreže opisujemo vektorom: C = C1 , C 2 , ... , C M ,

i moguće ga je primijeniti za formiranje skupa ograničenja f ≤ C , koja se pojavljuju kod postupaka optimizacije. Kada bude potrebno koristit ćemo se i oznakom C jk za kapacitet

( j, k ) grane.

Osnove telekomunikacija 7

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije ¾ traženje minimalnog stabla

Problem nalaženja minimalnog stabla predstavlja se tako da u mreži određene topologije, gdje se grane mogu označiti određenim svojstvom dužine, treba pronaći povezanu strukturu s minimalnim brojem grana i minimalnom ukupnom dužinom. Razmotriće se dva algoritma za pronalaženje minimalnog stabla: • •

Prim-Dijkstrin algoritam, koji pronalazi minimalno stablo za N2 koraka; Kruskalov algoritam, koji zahtijeva MldM koraka.

a) najkraći putevi u mreži Veliki broj optimizacijskih problema moguće je svesti na problem traženja najkraćeg puta. Postoji više tipova različitih problema koji pripadaju spomenutoj klasi, a mogu se podijeliti na slijedeće:

-

najkraći put između dvaju specificiranih čvorova (Dijkstrin algoritam); najkraći put između svih parova čvorova (Floydov algoritam); najkraći putevi od specificiranog početnog čvora do svih ostalih (gotovo je istovjetan Dijkstrinom algoritmu); najkraći put između dvaju čvorova koji prolazi kroz neke označene; drugi, treći, ..., k - ti najkraći put.

Općenito ćemo put između čvorova j i k označavati sa Π jk. Pokazaćemo neke algoritme za rješavanje ovih problema. b) minimalni rez, maksimalni tok Jedan od najvažnijih problema pri mrežnom programiranju je nalaženje maksimalnog toka koji može protjecati kroz mrežu od zadanog izvornog čvora s do odredišnog čvora t. Taj se problem može rješiti pomoću teoreme o minimalnom rezu i maksimalnom toku: Maksimalni tok koji može mreža prenositi između nekog izvora s i odredišta t jednak je veličini kapaciteta minimalnog reza s – t. Bilo koji rez s – t u mreži jeste uklanjanje bilo kojeg skupa grana, takvog da se u potpunosti prekida protjecanje toka od izvora s do odredišta t. Kapacitet reza je jednak sumi kapaciteta uklonjenih grana. Minimalni rez je onaj koji ima najmanji kapacitet, a to je upravo veličina maksimalnog toka koji može teći od s prema t.

Osnove telekomunikacija 8

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije A.3 Rutiranje u mreži Polazeći od općeg modela telekomunikacijske mreže i tehničke izvedbe njenih elemenata, analizirati će se model prema slici 1.

1

2

j

k

N

cj 1

Komutacija-obrada

λj cjk

2

Transmisija ckj M

γjk γk

γj

Korisnička ravan

Slika 1. Opći model telekomunikacijske mreže Telekomunikacijska mreža sastavljena je od N čvorišta u kojima se obavlja komutacija, a u nekima i obrada. Čvorišta su međusobno povezana posredstvom M jednosmjernih transmisijskih grana, koje prenose informacione tokove između njih. Kapacitet j-k transmisijske grane označićemo sa cjk i pretpostaviti ćemo potpuno pouzdane veze i bez utjecaja smetnji. Za čvorišta ćemo pretpostaviti da zadane funkcije potpuno pouzdano obavljaju bez pogrešaka uz maksimalnu brzinu cj (b/s). Ulazni tok u mrežu koji dolazi od vanjskih izvora (korisnika) ima osobine Poissonova ⎡ erl ⎤ toka informacijskih jedinica sa srednjom vrijednošću γ jk ⎢ ⎥ i odnosi se na one ⎣ s ⎦ telekomunikacijske jedinice koje ulaze iz korisničkog područja u j-ti čvor, a određene su da u korisničko područje izađu iz čvora k. Ukupni vanjski promet koji ulazi u razmatranu mrežu možemo prikazati relacijom: N

N

γ = ∑∑ γ jk j =1 k =1

⎡ erl ⎤ ⎢ s ⎥ ⎣ ⎦

(1) Osnove telekomunikacija 9

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

Ako u mreži nema gubitaka niti novih izvora, tada isti promet prikazan relacijom (1) napušta mrežu prema korisničkom području. Ukupni ulazni promet u j-to čvorište, bez obzira na odredište, iznosi: ⎡ erl ⎤ ⎢⎣ s ⎥⎦

N

γ j = ∑ γ jk k =1

(2)

Za unutrašnji tok svakog čvora vrijede ovi odnosi: N

λ j = γ j + ∑ λi rij i =1

⎡ erl ⎤ ⎢⎣ s ⎥⎦

(3)

gdje λ j prikazuje unutrašnji tok informacijskih jedinica u j-tom čvoru, a rij koeficijenti su usmjeravanja koji pokazuju koliki se dio unutrašnjeg toka čvora i, λi , usmjerava prema čvoru j. Iz toga slijedi da će tok i, j grane iznositi: ⎡ erl ⎤ ⎢⎣ s ⎥⎦

λij = λ j rij

(3)

Svi koeficijenti rij koji se odnose na mrežu u cjelosti čine matricu usmjeravanja R prema slijedećem izrazu:

R = rij =

r11

r12 " r1N

r21

r22 " r2 N

#

#

#

rN 1

rN 2 " rNN

(5)

Osnove telekomunikacija 10

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

cj

j λ1r1j

λj

λjrj1

λ2r2j

λjrj2

λNrNj

λjrjN γj N λj × ⎛⎜1 − ∑ r ji ⎞⎟ i =1 ⎝ ⎠

Slika 2. Unutrašnji tok čvora telekomunikacijske mreže Vrijednosti koeficijenata su 0 ≤ rij ≤ 1 , ali tako da vrijedi: N

∑r i =1

ji

≤1

(6)

Matrica (5) prikazuje na određeni način topologiju veza između čvorova. Ako je r ji ≠ 0 , znači da postoji izravna komunikacijska veza između čvorova i-j, koja ima kapacitet c ji > 0 , dovoljno velik da može prihvatiti tok λ ji = λ j r ji .

Prema tome, matrica (5) sadrži neke podatke o načinu usmjeravanja (rutiranja) tokova: -

Ako su vrijednosti matrice konstantne, govorimo o fiksnom rutiranju; Ako su vrijednosti matrice promjenjive, radi se o određenoj vrsti adaptivnog usmjeravanja tokova u mreži.

Unutrašnji tok čvora λj, označava tok zahtijeva za obavljanje operacije komutacije, odnosno obrade u čvoru. Da bismo mogli ustanoviti međusobne odnose tog parametra i unutrašnjih parametara, koji obilježavaju programsku i sklopovsku strukturu čvora, potrebno je provesti razlaganje čvora na mikrostrukturu. Razmotrićemo opće probleme vezane za analizu i sintezu telekomunikacijskih sistema. Vrednovanje svojstava telekomunikacijske mreže važan je aspekt postupaka analize i sinteze, jer nam pomaže da procijenimo informacijska svojstva u odnosu na primijenjene postupke manipulacije informacijskim tokovima, da bismo podesili parametre mreže tako da se optimiziraju njena svojstva, te da uporedimo informacijska svojstva dviju ili više različitih rješenja u kvantitativnom smislu. Osnove telekomunikacija 11

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

Kriterijumi za vrednovanje telekomunikacijskih mreža mogu varirati od slučaja do slučaja, ovisno o cilju sa kojim se vrednovanje provodi. Također, vrednovanje sa jednog stajališta može biti u kontradikciji u odnosu na vrednovanje sa drugog stajališta. Primjer je slučaj korisnika i vlasnika telekomunikacijske mreže. Korisnik želi da njegovo traženje bude zadovoljeno u što kraćem vremenu, a vlasnik mreže istodobno želi veću iskorištenost mreže. Iz navedenog razloga je korisno kriterijume za vrednovanje svojstava mreže grupisati u tri cjeline: • • •

Kriterijumi sa stajališta korisnika; Kriterijumi sa stajališta vlasnika mreže; Kriterijumi sa stajališta projektanta mreže.

Sa stajališta korisnika, najopćenitiji kriterijum za vrednovanje svojstava mreže jeste vrijeme za koje korisnik dobije traženu uslugu ili vjerovatnoća da se tražena usluga ne može uopće dobiti: • •

prosječno vrijeme prenošenja informacija između izvora i odredišta; vjerovatnoća da veza između dva korisnika ne bude ostvarena i sl.

Korisnik traži kompromis između osobina i cjene. Sa stajališta vlasnika sistema/mreže, kompromis između osobina i cijene mreže znači ostvariti veći profit uz manja ulaganja. Ovaj zahtjev će biti u suprotnosti sa jednakopravnim dostupom svih korisnika svim resursima. Da bi korisnik bio zadovoljan uslugom, potrebno je uz nastojanje da se poveća propusnost, a time i profit, kriterijume sa stajališta korisnika držati na prihvatljivoj razini. Kriterijumi sa aspekta projektanta treba da uzmu u obzir i zahtjeve korisnika i vlasnika mreže. Projektant provodi dimenzionisanje pojedinih elementa sistema u fazi planiranja tako da se zadovolje kriterijumi što su ih postavili korisnik i vlasnik. U postupcima analize i sinteze telekomunikacijskih sistema i mreža se primjenjuju različiti postupci i metode od kojih su najvažnije: • analitičke, • algoritamske, • simulacijske, • mjerenje na realnim sistemima. Promjena informacijskih osobina mreže je neposredno vezana uz raspored i količinu resursa. Zbog toga je sloboda promjene sve manja polazeći od faze planiranja preko uređenja do faze korištenja, odnosno, prolazeći kroz te faze, cijena promjena raste što potencira važnost prethodne analize svojstava mreže. Osnove telekomunikacija 12

cijena promjene

sloboda promjene

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

vrijeme Slika 3. Cijena i sloboda promjene parametara mreže

Postojeći parametri

Telekomunikacijska mreža

+

Informacijske osobine

Potrebna podešavanja Obrada izmjenjenih parametara Slika 4. Podešavanje parametara telekomunikacijske mreže

Osnove telekomunikacija 13

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

A.4 Sistem masovnog posluživanja 1. Uvod Tok informacijskih jedinica, ovisno o postupku komunikacija, ima određeno značenje: - u postupku komutacije kanala, to je tok poziva; - u postupku komutacije paketa (poruka), to je tok paketa (poruka). Bez obzira na to kakva je vrsta komunikacija u pitanju, informacijskim jedinicama pridružujemo značajku prosječne dužine b . Primjer: Za telefonski poziv prosječnog trajanja 120 s preko digitalnog kanala 64 kbit/s, prosječna dužina će iznositi b = 7,68 Mbit (64 kbit/s x 120 s = 7,68 Mbit).

U mrežama koje pokrivaju velika geografska područja potrebno je uzeti u obzir vrijeme propagacije signala Tpi , koje je potrebno da se energija kojom je predstavljen binarni element informacije prenese duž i-tog prenosnog puta. Označimo brzinu energije sa v (km/s), koja je ovisna o tipu prenosnog puta, tada je: Tpi =

li (s) v

Dalje slijedi da će, ako informacijska jedinica ima srednju dužinu b , vrijeme zauzimanja i-te prenosne veze kapaciteta ci biti:

Tsi = Tpi +

b (s). ci

Veličina Tpi se često zanemaruje, ali katkada čini znatan udio u kašnjenju. Napomenimo da vrijeme Tsi označava srednju vrijednost slučajnog vremena tsi koje nastaje zbog slučajne dužine informacijske jedinice b, dok su Tpi i ci determinističkog karaktera. Varijable Tsi će imati slučajni karakter kao i dužine informacijskih jedinica b. Definicija kriterijuma po kojem provodimo vrednovanje svojstava komunikacijske mreže ovisi o primjenjenom postupku komutacije. Kriterij za vrednovanje svojstava definiramo sa stajališta korisnika. Ako se radi o komunikaciji postupkom komutacije kanala, kriterij se može iskazati:

Osnove telekomunikacija 14

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

* Ako pozivajući korisnik (izvorište), priključen na neki čvor mreže, želi uspostaviti vezu sa pozvanim korisnikom (odredište), priključenim na neki drugi čvor mreže, ta se želja signalizacijskim porukama predaje upravljajućem dijelu mreže. Najčešće primjenjivan kriterij za vrednovanje svojstava mreže sa komutacijom kanala jeste srednja vrijednost gubitaka u mreži ili vjerovatnoća blokiranja PB. PB = {vjerovatnoća da pozivajući korisnik ne dobije vezu sa pozvanim korisnikom} Ova vjerovatnoća ovisi o mnogim faktorima, posebno o topologiji mreže, ulaznom prometu, kapacitetu grana i o primjenjenom načinu preusmjeravanja (rutiranja). * U komunikaciji postupkom komutacije paketa komuniciranje se obavlja na slijedeći način: Radi komunikacije na izvorištu se formiraju paketi informacija kojim se dodaje adresa odredišta. Paketi se prenose etapno od čvorišta do čvorišta mreže zauzimajući pritom istodobno vezu samo između dvaju čvorišta, koja je na najpovoljnijem putu prema odredištu u datom trenutku. Ako bilo gdje na putu napredovanja prema odredištu nema slobodnog kapaciteta, paketi čekaju spremljeni u memoriji dok se potreban kapacitet ne oslobodi. U ovom slučaju najčešće primjenjivani kriterij za vrednovanje svojstava mreže je srednja vrijednost vremena kašnjenja u mreži, T. T = {srednje vrijeme zadržavanja informacijskih jedinica u mreži} Vrijeme kašnjenja općenito zavisi o mnogo različitih faktora: o topologiji mreže, ulaznom prometu, kapacitetima grana i o načinu preusmjeravanja. Ne ulazeći sada u kvantificiranje utjecaja pojedinih parametara mreže, razmotrimo kvalitativno utjecaj vanjskog toka na vjerovatnoću gubitaka i vrijeme kašnjenja, uz ostale konstantne parametre. Na narednoj slici su prikazane spomenute funkcije. Pb

T

Pbmax

Tmax

0

γ*

γ

0

Osnove telekomunikacija 15

γ*

γ

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

Kriteriji vrednovanja se zadaju u obliku maksimalnih vrijednosti vjerovatnoće gubitaka Pbmax ili vremena kašnjenja Tmax čime je ograničen maksimalni ulazni tok γ* koji se uz postavljene kriterije mreže može prenijeti mrežom. U daljem razmatranju će se uzeti u obzir tri osnovna moguća skupa slobodnih parametara: -

prvi skup, kapaciteti prenosnih grana {ci}, i = 1, 2, ..., M drugi skup, unutrašnji tokovi {λi}, i = 1, 2, ..., M treći skup, grane koje određuju topologiju mreže

2. Procesi u sistemu posluživanja a) Teorija repova i informacijske mreže Oslikavanje repa opća je pojava koja se javlja uvijek kada trenutna veličina zahtijeva za posluživanjem prelazi kapacitet posluživanja. U informacijskim mrežama to se događa na bilo kojem elementu mreže kada trenutni informacijski tok prelazi veličinu kapaciteta posmatranog elementa, npr. poruke koje čekaju na prenos kanalom, pozivi koji čekaju da budu spojeni kroz komutaciju itd. Pri ovome se kao korisnici pojavljuju informacijske jedinice (paket, poruka, poziv), a poslužitelji su elementi mreže (kanal, komutacija, memorija, procesorska jedinica itd).

Zbog toga ćemo u nastavku razmotriti teoriju repova, kao matematičko sredstvo za analizu različitih situacija čekanja, koja se može primijeniti za analizu i sintezu mreža. Situacija čekanja nastupa kada neki korisnik dolazi do poslužitelja i ustanovi da je on zauzet. Korisnik je prisiljen čekati na svoj red dok ne bude primljen na posluživanje. U sistemu sa čekanjem možemo identificirati tri pojave koje nastupaju u toku posluživanja (Slika 1.): - ulazak u sistem; - čekanje; - posluživanje;

Osnove telekomunikacija 16

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

ULAZAK skup promet. jedinica korisnici

ČEKANJE

POSLUŽIVANJE

Li-1 Li ta

tw tq

Slika 1. Proces posluživanja Analiza osobina sistema sa čekanjem se svodi na nalaženje međusobnih odnosa tih triju pojava. Označimo sa Li i-tog korisnika koji ulazi u sistem posluživanja. Slučajne varijable koje pridružujemo korisniku Li, su: ti – dolazno vrijeme korisnika Li; tai = ti – ti-1 – međudolazno vrijeme između korisnika Li i Li-1; tsi – vrijeme posluživanja korisnika Li; Slijed slučajnih varijabli tai i tsi zapravo pokreće mehanizam čekanja. Funkcija α (t ) prikazuje kumulativan broj korisnika koji ulaze u sistem posluživanja u toku posmatranog vremenskog intervala uz prije spomenut karakter međudolaznog vremena tai. Funkcija β (t ) prikazuje broj korisnika koji izlaze iz sistema posluživanja u toku istog vremenskog intervala uz slučajnu veličinu vremena posluživanja tsi. Slučajne varijable međudolaznog vremena i vremena posluživanja (ta, ts) međusobno su neovisne zbog čega možemo ustanoviti da će u nekom razdoblju doći do gomilanja korisnika ispred posluživanja (stvaranje repa), da bi opet u nekom drugom razdoblju došlo do razrjeđivanja i do potpunog pražnjenja repa. Te pojave možemo opisati funkcijom:

δ (t ) = α (t ) − β (t ) , koja prikazuje trenutni broj korisnika u sistemu. U slijedećim razmatranjima ćemo uvesti daljnja poopćenja. Osim međusobne neovisnosti slučajnih varijabli međudolaznog vremena i vremena posluživanja, one se mogu posmatrati i neovisno o korisniku, pa općenito možemo definisati: ta – međudolazno vrijeme; ts – vrijeme posluživanja; kao slučajne varijable kojima će se pridružiti funkcije raspodjele vjerovatnoće: F (t ) = P{t a ≤ t} i H (t ) = P{t s ≤ t} ; Osnove telekomunikacija 17

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

i funkcije gustine vjerovatnoće: f (t ) =

dF (t ) dH (t ) i h(t ) = . dt dt

Uvešćemo uobičajene oznake koje se primjenjuju u teoriji repova (Kendall-ove notacije). Uvodimo opis sa tri oznake u obliku F/H/m, što označava sistem posluživanja sa m poslužitelja, F opisuje raspodjelu vjerovatnoće međudolaznim vremenom, a H raspodjelu vjerovatnoće vremenom posluživanja. F i H će imati slijedeća značenja ovisno o vrsti funkcije raspodjele vjerovatnoće: M – eksponencijalna; Er – Erlangova r-tog stepena; Hr – hipereksponencijalna R-tog stepena; D – deterministička; G – općenita;

Tako će npr. oznaka M/M/1 prikazivati sistem sa jednim poslužiteljem i eksponencijalnim raspodjelama vjerovatnoće međudolaznog vremena i vremena posluživanja.

Osnove telekomunikacija 18

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije A.5 Modeli I analitički opisi procesa u sistemu posluživanja a.) ulazak u sistem posluživanja Kao polaznu tačku za definisanje ulaska u sistem posluživanja uzimamo skup prometnih jedinica (korisnika) koje nazivamo ulazni izvor. Jedna od značajki toga izvora jeste njegova veličina, tj. ukupan broj mogućih korisnika, koji može biti konačan ili beskonačan. Ako je skup korisnika velik, ulazak jednog korisnika u sistem ne utiče bitno na intenzitet ulaska dok u slučaju malog skupa korisnika, ulazak jednog korisnika bitno utiče na intenzitet ulazaka. U ekstremnom slučaju, kod vrlo malog skupa, svi će korisnici biti u sistemu.

Slijedeća osobina ulazaka korisnika jeste stohastičko ponašanje u vremenu. Moglo bi se smatrati da je najjednostavnije ponašanje determinističkih ulazaka: Korisnici ulaze u sistem u jednakim vremenskim odsječcima Ta = const . Za taj slučaj 1 konstantna. Međutim, pretpostavka da će bila bi i gustoća (brzina ulazaka) λ = Ta međudolazno vrijeme biti konstantno ne samo da je nestvarna u većini slučajeva, već je i teško provesti matematičku analizu ovih sistema. Za našu primjenu najjednostavniji i najpraktičniji potpuno slučajan proces ponašanja ulazaka predstavlja Poisson-ov proces. Analiziraćemo ovaj proces kao osnovni model ulazaka u sistem posluživanja. Posmatrajmo konačni vremenski interval (0, t) i nađimo funkciju raspodjele vjerovatnoće broja korisnika koji ulaze u sistem posluživanja za vrijeme posmatranog intervala. U tu ćemo svrhu interval (0, t) podijeliti na x podintervala t jednake dužine h = , kao na slici 5. x

0

h

2h

3h

xh = t

t

Slika 5. Podjela intervala Neka je λ srednji broj ulazaka u jedinici vremena. Za svaki podinterval možemo napisati vjerovatnoće:

λ (h ) + o(h ) - vjerovatnoća ulaska jednog korisnika; o(h ) - vjerovatnoća ulaska dvaju ili više korisnika; 1 − λh + o(h ) - vjerovatnoća da se nije pojavio nijedan korisnik.

Osnove telekomunikacija 19

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

Ovdje smo simbolom o(h ) označili funkciju koja se približava nuli brže od h kada h teži 0 npr. o(h ) = 2h 2 . Za potpuno slučajan ili Poisson-ov proces vrijedi neovisnost događaja: Sve što se događa u bilo kojem podintervalu potpuno je neovisno o događajima u bilo kojem intervalu koji ne pokriva promatrani interval. Na taj način ako uzmemo da je ulazak korisnika ishod Bernoulli-jeva događaja, tada slijed ulazaka za razdoblje t = xh možemo posmatrati kao rezultat slijeda od x Bernoulli-jevih događaja.Otuda slijedi da je vjerovatnoća da se u x podintervala pojavi upravo h korisnika približno jednaka binomnoj raspodjeli: n x−n ⎛ x⎞ ⎜ ⎟ ( λ h + o ( h ) ) (1 − λ h + o ( h ) ) . ⎝ n⎠

(5)

Graničnim prelazom kada h → 0 i x → ∞ uz zadržavanje xh = const , dobivamo da će se u intervalu (0, t) naći ukupno h korisnika. Pn ( t )

( λt ) =

n

x! ⎛ λt ⎞ lim n lim ⎜ 1 − ⎟ n! x ( x − n )! x⎠ ⎝

x−n

( λt ) = n!

n

e − λt

(6)

što označava Poisson-ov zakon raspodjele vjerovatnoće koji smo intuitivno pretpostavili. Determinisana je veličina λ , dakle, konstanta i ona izražava srednji intenzitet ulazaka u sistem u jedinici vremena (brzina ulazaka). Proizvod λ t srednji je broj ulazaka za vrijeme t i naziva se intenzitetom ulaznog prometa u posmatranom intervalu. Drugi način opisivanja Poisson-ovog procesa se zasniva na proteklom vremenu između ulazaka (međudolazno vrijeme). Neka je ta interval od vremenskog ishodišta (proizvoljno odabranog) do trenutka pojave prvog korisnika. Slučaj da se u intervalu ( 0, t ) ne pojavi niti jedan korisnik dogodiće se samo ako je ta > t odnosno

P {ta > t} = P {n ( t )} = 0

(7)

gdje je n ( t ) broj ulazaka za vrijeme t vremenskih jedinica. Koristeći se izrazom (6) nalazimo da je

P {n ( t ) = 0} = e − λt

(8)

Iz gornjeg slijedi funkcija raspodjele vjerovatnoće međudolaznih vremena: F ( t ) = P {ta ≤ t} = 1 − e − λt

(9)

Budući da je ishodište odabrano proizvoljno, gornja raspodjela važi za bilo koje mjesto na vremenskoj osi. Funkcija gustine vjerovatnoće dobije se kao:

Osnove telekomunikacija 20

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

f (t ) =

dF ( t ) dt

= λ e − λt

t≥0

(10)

b.) posluživanje Slijedeća bitna komponenta sistema posluživanja jeste opis količine usluga koju traži pojedini korisnik tj. trajanje usluge koju poslužitelj daje korisniku. Jedinica nad kojom se izvodi usluga mora biti različita, ovisno o vrsti korisnika i poslužitelja. Primjerice, ako je poslužitelj prenosni kanal, a korisnici su poruke ili paketi podataka, jedinica usluge će biti oktet ili bit.

U većini slučajeva se pretpostavlja da je skup korisnika homogen, što uvjetuje da raspodjela dužina usluga koju poslužitelj daje korisnicima bude istovjetna i zajednička za sve korisnike. Ponašanje ulazaka i dužina usluge nisu dovoljne da se opišu značajke cijelog sistema posluživanja. Zbog toga se uvodi kapacitet poslužitelja (ili brzina posluživanja), odnosno označava se kojom brzinom poslužitelj obavlja posao. Kapacitet posluživanja označićemo sa C, a njegova jedinica ovisi o vrsti usluge (ako je poslužitelj govorni kanal, jedinica kapaciteta će biti b/s. Označimo općenito dužinu usluge sa b (jedinica) i odgovarajući kapacitet poslužitelja sa C (jedinica u sekundi). Odnos tih dvaju veličina je vrijeme posluživanja. ts =

b (s) C

(11)

što je slučajna veličina zbog slučajne raspodjele dužine usluge. Srednje vrijeme posluživanja iznosi:

Ts =

b C

(12)

gdje je b srednja dužina usluge. Recipročna vrijednost srednjeg vremena posluživanja se naziva intenzitet posluživanja i označava kao:

β=

1 C = = μC Ts b

(13)

Osnove telekomunikacija 21

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

gdje je μ =

1 . b

U sistemima posluživanja nerijetko se susrećemo sa potrebom varijabilne promjene kapaciteta ovisno o stepenu gomilanja korisnika. Takav primjer nalazimo u sistemima sa više istovršnih poslužitelja, gdje sistem čine m paralelnih poslužitelja, koji prihvataju korisnike iz zajedničkog repa (Slika 7.).

Ck (lq) 1 2

mC

...

2C C

lq

m

Slika 7. Sistem sa m poslužitelja Ako je kapacitet svakog poslužitelja jednak C, a lq broj korisnika u sistemu (u repu i na posluživanju), popunjeni kapacitet sistema ovisi o broju korisnika u sistemu i iznosi:

Ck ( lq ) = min {lq , m} ⋅ C

(14)

što se vidi na slici 7. Ovaj zaključak nas navodi da je moguće dinamičko pridruživanje veličine ukupnog kapaciteta u zavisnosti o intenzitetu nailazaka zahtjeva. Za detaljniju analizu sistema posluživanja potrebno je poznavati pojedine funkcije raspodjele dužine usluge, odnosno vremena posluživanja: H (t ) = P{t s ≤ t}

(15)

i odgovarajuće funkcije gustoće vjerovatnoće h (t ) =

dH ( t ) dt

.

(16)

Osnove telekomunikacija 22

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije ¾ eksponencijalna funkcija posluživanja H ( t ) = 1 − e− β t

(17)

h ( t ) = β e− β t

(18)

Srednja vrijednost vremena posluživanja: Ts =

1

β

=

1 μC

(19)

i varijansa

σ 2 (Ts ) =

1

β

2

= Ts 2

(20)

¾ Erlangova raspodjela U mrežama nailazimo na modele u kojima raspodjela vremena posluživanja nije ni eksponencijalna niti konstantna, već leži između tih zakona. Ta raspodjela se u teoriji posluživanja naziva Erlangova raspodjela (poznata iz telefonskog prometa) karakterisana parametrom r. Za neko srednje vrijeme posluživanja Ts vjerovatnost da vrijeme posluživanja bude manje od određenog vremena t ili jednako njemu izražava se funkcijom Er ( t ) . Kada je r = 1 , funkcija Er ( t ) predstavlja eksponencijalnu raspodjelu.

Kada r → ∞ funkcija postaje konstanta. Za vrijednosti r između spomenutih dvaju ekstrema, funkcija Er ( t ) leži između navedenih dvaju funkcija. Što je veće r, to je veće grupisanje raspodjele oko srednje vrijednosti .. r −1

H (t ) = E r (t ) = P{t s ≤ t} = 1 − e − rβt ∑ i =0

h ( t ) = er ( t ) =

rβ (rβ t )

( r − 1)!

e−r β t

(rβ )i t i i!

(21)

(22)

2

⎛ T ⎞ Ovdje je r = ⎜ s ⎟ ranije uveden parametar Erlangove funkcije raspodjele, ⎜ σT ⎟ ⎝ s⎠ σ Ts standardna devijacija vremena posluživanja.

Osnove telekomunikacija 23

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije ¾ hipereksponencijalna raspodjela U praksi je čest slučaj da se raspodjela vremena posluživanja može prikazati sumom eksponencijalnih funkcija. Neka u takav sistem ulazi k vrsta korisnika i neka se svaka vrsta pojavljuje sa vjerovatnoćom pi , i = 1, 2, ... , k , te svaki korisnik t-te vrste ima vrijeme posluživanja eksponencijalno raspodijeljeno sa srednjom vrijednosti 1 , i = 1, 2, ... , k .

βi

Funkcija raspodjele vremena posluživanja biće: k

(

)

k

H ( t ) = ∑ pi 1 − e − βit = 1 − ∑ pi e − βit 1=1

(23)

i =1

k

h ( t ) = ∑ pi β i e − βit

(24)

i =1

Srednja vrijednost vremena posluživanja iznosi: k

Ts = ∑ i =1

pi

βi

=

1

(25)

β

i varijansa: ⎛ 1 1 ⎞ σ Ts = 2 + ∑∑ pi p j ⎜ − ⎟ ⎜ βi β j ⎟ β i =1 j =1 ⎝ ⎠ 1

k

k

2

(26)

eksponencijalna 1

hipereksponencijalna 0

t

Osnove telekomunikacija 24

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije c.) čekanje Svojstva repa čekanja biće ovisna o raspodjeli vjerovatnoće ulazaka u sistem i raspodjeli vremena posluživanja. Situacije prilikom posluživanja u stvarnim sistemima mogu biti vrlo složene. Biće razmotren model ”prvi ulazi, prvi poslužen”, ako ne bude drukčije naznačeno. Da bismo opisali svojstva posluživanja, treba definisati neke slučajne veličine koje proizilaze iz pojave čekanja. To su: lq ( t ) - broj korisnika u sistemu u trenutku t;

tw - slučajno vrijeme čekanja korisnika u repu: tq - slučajno vrijeme zadržavanja korisnika u sistemu; lw ( t ) - broj korisnika u repu u trenutku t.

Funkcija raspodjele vremena čekanja: W ( t ) = P {tw ≤ t} i gustoća:

w (t ) =

dW ( t ) dt

.

Funkcija čekanja izražava vjerovatnoću da korisnik neće u posluživanju čekati više od t vremena. Funkcija čekanja za t = 0 pokazuje vjerovatnoću W ( 0 ) da je poslužitelj slobodan u trenutku ulaska korisnika. Srednje vrijeme čekanja možemo izračunati pomoću funkcije čekanja kao ∞

TW = ∫ tdW (t )

(27)

0

i varijansu ∞

2

σ T = ∫ ( t − Tw ) dw ( t ) w

(28)

0

Izgled funkcije čekanja ovisi o tome kakve su funkcije ulazaka i posluživanja, pa se analiza čekanja treba provesti za konkretne slučajeve.

Osnove telekomunikacija 25

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije d) parametri i osobine sistema posluživanja Osnovni je razlog predstavljanja matematičkog modela sistema posluživanja da se dobije mogućnost vrednovanja prema određenim mjerama za ocjenu karakteristika. Kod sistema posluživanja jedna od pojava koja može biti mjera kvaliteta jeste veličina gomilanja korisnika pred posluživanjem.

Najjednostavnije se veličina gomilanja mjeri pomoću prometnog intenziteta ili tzv. ponuđenog prometa i definiše:

prometni intenzitet =

srednje vrijeme posluživanja ; srednje međudolazno vrijeme

Pretpostavimo model sa beskonačnim skupom korisnika, te primijenimo ranije uvedene 1 1 oznake za intenzitet ulazaka λ = i intenzitet posluživanja β = , a prometni Ta Ts intenzitet označimo sa A iz čega slijedi:

A=

Ts λ λ = = [erl ] Ta β μ C

Ako je prometni intenzitet veći od jedinice to znači da korisnici nailaze brže nego što mogu biti posluženi od jednog poslužitelja, a što bi izazvalo nepopravljivo gomilanje u sistemu. Budući da su λ i μ parametri ovisni o korisnicima, jedina mogućnost da se u sistemu spriječi gomilanje jeste prikupljanje više poslužitelja. Tako će m paralelnih poslužitelja prihvaćati

λ

korisnika u jedinici vremena, pa se m pravilnim izborom vrijednosti m sprečava gomilanje. Slijedeća mjera kvaliteta, koja je vrlo slična prometnom intenzitetu jeste faktor opterećenja poslužitelja ili faktor iskorištenosti. Ta veličina koju ćemo označavati sa ρ , pokazuje koji je dio vremena poslužitelj zauzet od ukupnog vremena promatranja. Uzmimo dovoljno dugi interval T. U sistemu sa m paralelnih poslužitelja očekujemo da u λT korisnika po poslužitelju uz pretpostavku ravnomjerne vremenu T dolazi u prosjeku m raspodjele prometa na sve poslužitelje. Svaki korisnik treba u prosjeku vrijeme posluživanja Ts = vrijeme za koje će poslužitelj biti zauzet iznosi

1

β

, tako da ukupno očekivano

λT . Budući da je fizički nemoguće da mβ

jedan poslužitelj bude zauzet više od 100% vremena, faktor opterećenja fizikalno ne može biti veći od jedinice. Otuda slijedi izraz za opterećenje poslužitelja: Osnove telekomunikacija 26

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

⎧ λ ⎫ opterećenje = ρ = min ⎨ ,1⎬ [ erl ] ; ⎩ mβ ⎭ Za sistem sa jednim poslužiteljem opterećenje je ρ =

λ ≤ 1 i jednako je prometnom β

intenzitetu. Za mjeru kvaliteta možemo uzeti i propusnost sistema posluživanja. Ta se veličina definiše kao srednji broj korisnika koji su prošli kroz sistem u jedinici vremena (obavljene usluge). U sistemu sa m poslužitelja biće posluženo m ⋅ ρ ⋅ β korisnika u svakoj jedinici vremena iz čega slijedi:

⎡ erl ⎤ propusnost = PR = m ⋅ ρ ⋅ β = min {λ , mβ } ⎢ ⎥ . ⎣ s ⎦ Tako možemo zaključiti da će propusnost biti jednaka intenzitetu ulazaka, dok je taj intenzitet manji od maksimalnog intenziteta posluživanja m ⋅ β , nakon čega se propusnost zaustavlja na toj maksimalnoj vrijednosti m ⋅ β . Sa stajališta korisnika najznačajnija mjera kvaliteta jeste vrijeme koje on provodi čekajući u repu na posluživanje ili zadržavajući se u sistemu. Vrijeme čekanja i-tog korisnika, tw i , vrijeme je što ga korisnik troši čekajući u repu, a vrijeme zadržavanja, tqi , ukupno je vrijeme koje i-ti korisnik boravi u sistemu. Bez obzira na pojedine korisnike, općenito vrijedi relacija:

tq = t w + t s , gdje su tw , t s i tq slučajne varijable. Kao mjera navedenih slučajnih veličina uzimaju se srednje vrijednosti navedenih slučajnih veličina: Tw , Ts i Tq , za koje također vrijedi relacija Tq = Tw + Ts . Za ocjenu kvaliteta sistema posluživanja, također je važno određivanje dužine repa (broj korisnika koji čeka u repu). Označimo sa lw ( t ) broj korisnika u repu u vremenu t, sa lq ( t ) broj korisnika u sistemu u istom vremenu. Za sistem sa m poslužitelja možemo

napisati relaciju:

lw ( t ) = max {0, lq − m} . Navedena relacija je jako važna za dimenzionisanje sistema čekanja. Poznajući slučajne procese lw ( t ) i lq ( t ) , možemo ustanoviti i njihove srednje vrijednosti: Osnove telekomunikacija 27

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

Lw - srednji broj korisnika u repu; Lq - srednji broj korisnika u sistemu. Između navedenih veličina sistema posluživanja vrijedi jednostavna relacija:

Lw = λTw poznata pod nazivom Little-ova formula (teorema) koja nam omogućuje izračunavanje vrijednosti parametara koji opisuju osobine sistema posluživanja. Srednje vrijeme zadržavanja u sistemu tada iznosi:

Tq = Tw + Ts , a srednji broj korisnika u sistemu iznosi:

Lq = λTq = ρ + Lw .đ Poseban slučaj sistema posluživanja su sistemi sa gubicima. U takvim sistemima nema mogućnosti stvaranja repa, pa se u slučaju nastanka gomilanja, ne može obaviti posluživanje nagomilanih jedinica. U tom slučaju nastupa gubitak. Za sisteme sa gubicima kriterij za opis osobina je vjerovatnoća gubitaka. Gubitak nastupa kada su u sistemu sa m poslužitelja, svi poslužitelji zauzeti, a mogućnosti čekanja minimalne. Može se definisati vjerovatnoća gubitaka:

vjerovatnoća gubitaka = PB = P ( l q > m ) . Vjerovatnoća gubitaka je u općem slučaju funkcija ponuđenog prometa i broja poslužitelja: PB = F ( A, m ) .

Svi dosada definisani parametri sistema posluživanja i njihovi međusobni odnosi vrijede bez obzira na vrstu funkcija vjerovatnoće koje opisuju karakteristiku ulazaka i posluživanja. Za konkretne modele potrebno je poznavati funkciju čekanja W ( t ) , pomoću koje se, primjenom navedenih relacija izračunavaju parametri osobina razmatranog sistema. Kod rješenja ovog problema polazi se od toga da je sistem posluživanja difuzijski proces i da funkcija W ( t ,τ ) mora zdovoljavati Fokker – Planck – ovu jednačinu protjecanja:

∂W ∂W 1 2 ∂ 2W = −v + σ , ∂τ ∂t 2 ∂t 2 Osnove telekomunikacija 28

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

gdje v i σ 2 imaju vrijednosti :

σ 2 = λ ts2 = λ (σ T2 + Ts2 ) .

v = ρ − 1 = λTs − 1 ,

s

Srednje vrijeme čekanja sa dobije kao: ∞

TW = ∫ tw ( t )dt = − 0

σ2 2v

= λ ts2 / 2 (1 − ρ ) ,

gdje je w ( t ) funkcija gustine vjerovatnoće data kao w ( t ) =

dW ( t ) dt

=−

2v

σ2

2v

e

σ2

.

Izraz za Tw vrijedi općenito i isti se koristi u analizi pojedinih modela. Izraz je poznat kao Pollaczek - Khinchin – ova formula i služi kao rješenje modela M / G /1 . A.6. Modeli sistema posluživanja Postoji više modela sistema posluživanja:

-

M M M M M

/ M /1 / D /1 / Er /1 / M / m sa čekanjem / M / m sa gubicima

Ovi modeli su obrađeni u literaturi, dok će u nastavku biti obrađene Markovljeve mreže repova. ¾ Markovljeve mreže repova Razmotrićemo sistem posluživanja u kojem korisnici prolaze kroz niz posluživanja povezanih u određenu strukturu u obliku mreže. Korisnici ulaze i izlaze iz pojedinih dijelova mreže i prolaze kroz mrežu na slučajan način, dok na kraju ne napuste sistem.

Posmatraćemo mrežu od N čvorova u kojoj se i-ti čvor sastoji od sistema posluživanja sa mi poslužitelja, a vrijeme posluživanja ima eksponencijalnu raspodjelu sa srednjom 1 vrijednosti (slika 1.).

βi

U i-ti čvor ulazi slijed prometnih jedinica sa svojstvima Poisson-ovog izvora intenziteta ⎡ erl ⎤ nailazaka λi ⎢ ⎥ . Kada je korisnik poslužen u i-tom čvoru, on će sa vjerovatnoćom rij ⎣ s ⎦ preći u čvor j i tako korisnik postaje unutrašnji ulazak u čvor j. Sa vjerovatnoćom Osnove telekomunikacija 29

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije 1 − ∑ rij korisnik će nakon što bude poslužen u i-tom čvoru napustiti mrežu. Grananje

tokova u čvorovima prikazujemo NxN matricom R, koja sadrži prelazne vjerovatnoće rij .

2 1

N

i

λ1 r1i

λi ri 1 1

λi

2

λ N rNi

λi λi riN

m

γi ⎛

N

⎞

⎝

j =1

⎠

λi ⎜⎜1 − ∑ rij ⎟⎟ Slika 1. Markovljeva mreža Označimo li ukupni ulazni tok u mrežu vektorom γ = γ 1 , γ 2 , ... , γ N i ukupni unutrašnji tok u čvorove vektorom λ = λ1 , λ 2 , ... , λ N dobijamo matričnu jednačinu:

λ = γ + λR

(29)

odnosno, drukčije rečeno, ukupni ulazni intenzitet u i-ti čvor se sastoji od vanjskih r11

r12

r1N

R = rij = r21

r22

r2 N

rN 2

rNN

rN 1

Osnove telekomunikacija 30

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

i unutrašnjih ulazaka. Skup jednačina koje definiraju λi dat je izrazom: N

λi = γ i + ∑ λ j r j i

(30)

j =1

Ako bismo općenito željeli opisati takvu mrežu, trebalo bi poznavati vjerovatnoće istodobne pojave l1 korisnika u čvoru 1, l 2 korisnika u čvoru 2 itd., tj. složenu vjerovatnoću P(l1 , l 2 , ..., l N ) . Postupak izračunavanja spomenute vjerovatnoće za općeniti slučaj vrlo je složen i teško se provodi za veći broj čvorova. Zbog toga se služimo jednostavnim modelom koji pretpostavlja da su pojave u pojedinim čvorovima međusobno neovisne, te se za vjerovatnoću može napisati:

P(l1 , l 2 , ..., l N ) = P1 (l1 ) ⋅ P2 (l 2 ) ... PN (l N )

(31)

Proizvod vjerovatnoće na desnoj strani navedenog izraza govori o spomenutoj nezavisnosti. Svaki faktor u izrazu (31), Pi (li ) , rješenje je izoliranog sistema posluživanja M / M / mi sa intenzitetom ulazaka λi . Rješenje za Pi (li ) se može izračunati za sistem sa i bez gubitaka.

•

Sistem M / M / m sa čekanjem ⎧ (mρ )n ⎪⎪ P0 n! ( ) P lq = n = ⎨ n n ⎪P ρ m ⎪⎩ 0 m!

⎫ n ≤ m⎪ ⎪ ⎬ n ≥ m⎪ ⎪⎭

i

⎫ ⎧ m −1 (mρ )i (mρ )n (1 − ρ )⎬ P0 = ⎨∑ + n! ⎭ ⎩ i =0 i!

i

ρ=

•

Sistem M / M / m sa gubicima

−1

λ λ A = = - faktor opterećenja poslužitelja βm μCm m

⎧ (mρ )n P (l q = n ) = ⎨ P0 n! ⎩

⎫ n ≤ m⎬ ⎭ Osnove telekomunikacija 31

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

⎧ m −1 (mρ )i ⎫ P0 = ⎨∑ ⎬ ⎩ i =0 i! ⎭ Ovako mrežu možemo posmatrati kao N zasebnih posluživanja M / M / m (Jackson - ova teorema). Posebnu klasu Markovljevih mreža repova čine mreže iz kojih korisnici ne smiju izlaziti. Pretpostavimo da je L korisnika ušlo u mrežu u početku posmatranja, potom se oni kreću od čvora do čvora, ali ne izlaze. Ovo znači da je 1 − ∑ rij = 0 za sve i. Ovakva zatvorena mreža ima slijedeće rješenje za raspodjelu vjerovatnoća određenog broja korisnika u pojedinim čvorovima: P(l1 , l 2 , ..., l N ) =

1 N xili ∏ G (L ) i =1 α i (li )

(32)

Skup brojeva {xi } mora zadovoljiti slijedeće linearne jednačine: N

β i xi = ∑ β j x j rij

i = 1, 2, ..., N

(33)

j =1

Funkcija G (L ) ima oblik: N

G (L ) = ∑∏ xili / α i (l i )

(34)

i∈ A i =1

gdje je l = l1 , l 2 , ..., l N , a A je skup vektora l za koje je l1 + l 2 + ... + l N = L , a funkcija

α i (li ) glasi:

⎪⎧li ! ⎪⎩mi !mi li − mi

α i (li ) = ⎨

li ≤ mi ⎫⎪ ⎬. l i > mi ⎪⎭

A.7 Mreže sa komutacijom paketa 1. Analiza kašnjenja Kod mreža sa komutacijom paketa (poruka) osnovni kriterij za vrednovanje svojstava jeste prosječno kašnjenje informacijskih jedinica prolaskom kroz komunikacijsku mrežu. Definirajmo kašnjenje informacijske jedinice kao ukupno vrijeme zadržavanja u mreži prolazom od izvora do odredišta. Jasno je da je to slučajna veličina, pa će za analizu biti zanimljiva njena srednja vrijednost.

T = {srednja vrijednost zadržavanja informacijske jedinice u mreži}

Osnove telekomunikacija 32

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

Taj parametar ćemo uzeti kao osnovnu mjeru za ocjenu svojstava mreže. Uvedimo veličinu kašnjenja informacijske jedinice na putu Π jk , sa: zjk = {srednje vrijeme kašnjenja informacijskih jedinica na j-k putu} pa se za ukupno kašnjenje može napisati: N

N

T = ∑∑ z jk γ j =1 k =1

jk

/γ ,

(35)

budući da će dio γjk/γ ukupnog prometa imati kašnjenje zjk. Posljednja relacija prikazuje mogućnosti razlaganja mreže na osnovi parova izvorišni čvor – odredišni čvor. Pretpostavimo da je primjenjena procedurafiksnog uspostavljanja puta kroz mrežu (γjk promet ide uvijek istim putem od j ka k). Označimo put informacijske jedinice koja izvire u čvoru j i koja je usmjerena prema odredištu k (j-k promet) sa Π jk . j

u

v

k

ci, λi,Ti

Π jk

i ci

λi zjk

Ti

γjk

Slika: Kašnjenje informacijskih jedinica na grani Utvrdićemo da je i-ta grana, koja ima kapacitet Ci, uključena u put Π jk , ako informacijska jedinica na svojem putu prolazi kroz tu granu. U tom slučaju upotrebljavamo označavanje sa C i ∈ Π jk . Jasno iz tog proizlazi da srednja vrijednost toka informacijskih jedinica (intenzitet nailazaka) λi u i-toj grani mora biti jednaka sumi srednjih vrijednosti tokova svih puteva koji prolaze posmatranom granom:

λi = ∑∑ γ jk j

j,k: C i ∈ Π jk ;

(36)

k

Osnove telekomunikacija 33

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

Također primjećujemo da je zjk suma prosječnih kašnjenja dobivenih promatranjem prolaza informacijskih jedinica kroz različite grane na putu Π jk . Pojedine su komponente u toj sumi pojedinačna kašnjenja u granama definirana kao: Ti ={prosječno potrošeno vrijeme za čekanje i prijenos na i-toj grani} Tako, Ti možemo smatrati kao prosječno vrijeme zadržavanja u sistemu posluživanja, pri čemu pod sistemom smatramo i-tu prenosnu granu (kao poslužitelj) i privremenu memoriju za spremanje informacijskih jedinica ispred prenosne grane (kao rep). Prolaskom kroz mrežu informacijska jedinica će se određeno vrijeme zadržati na svakoj grani koja je na njenom putu, tako da možemo napisati da je: z jk = ∑ Ti i: C i ∈ Π jk ;

(37)

i

Dalje slijedi da je: N

N

T = ∑∑ z jk γ j =1 k =1

jk

/γ =

⎛γ

⎞ ⎟⎟∑ Ti j =1 k =1 ⎝ γ ⎠ i N

N

∑∑ ⎜⎜

jk

i: C i ∈ Π jk ;

(38)

Promjenimo redoslije sumiranja uz promjenu uslova postavljenih na i u uvjete za j,k što je uobičajeno kada mijenjamo redoslijed sumiranja, pa izlazi: M

T = ∑ (Ti / γ )∑∑ γ i =1

j

jk

j,k: C i ∈ Π jk ;

(39)

k

što primjenom izraza za λi daje: M

T = ∑ Ti λi / γ ;

(40)

i =1

Ovim smo proveli raščlanjivanje prosječnog vremena kašnjenja na komponente koje pripadaju pojedinim prenosnim granama. Posljednja jednačina u potpunosti je općenita i naš će se dalji postupak u nastavku svesti na određivanje Tij vličine vezane za i-tu granu. Kod toga ćemo se koristiti sljedećom pretpostavkom neovisnosti: U trenutku prijenosa informacijske jedinice u čvoru, neovisno se generira nova dužina b, prema funkciji gustine vjerovatnoće: b

1 − 1 p(b ) = e b = μ ⋅ e − μb , μ = ; b b

(41)

Osnove telekomunikacija 34

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

što znači da je primjenjena eksponencijalna raspodjela za generisanje dužina informacijskih jedinica u čvorovima. Gornja pretpostavka nije, dakako, sasvim korektna, jer bi to značilo da informacijske jedinice mijenjaju dužinu prolaskom kroz mrežu. No pokazuje se da uticaj nekorektnosti navedene pretpostavke na ukupni T možemo zanemariti u većini slučajeva, pa tu pretpostavku možemo primjeniti. Uz prihvaćenu pretpostavku nezavisnosti možemo postaviti nezavisni model posluživanja za i-tu granu kao M/M/1 sistem posluživanja sa čekanjem koji ima Poissonov ulaz intenziteta nailazaka λi i eksponencijalnu raspodjelu vremena posluživanja srednje 1 . Srednje vrijeme zadržavanja takvog sistema upravo odgovara vrijednosti μ ⋅ ci srednjem vremenu kašnjenja Ti informacijske jedinice na i-toj grani, tako da možemo primjeniti relaciju za model M/M/1 Ti =

TS =

1 μci − λi 1

β

=

1 μci

b 1 c 1 [ Ts = ; β = = = μc, μ = ] c Ts b b

Ovaj izraz uvršten u relaciju (40) daje konačno rješenje za ukupno prosječno vrijeme kašnjenja informacijske jedinice kroz mrežu: M

T =∑ i =1

λi

γ (μci − λi )

(42)

Relacija (42) je osnova za analizu osobina telekomunikacijske mreže sa komutacijom paketa. U ovoj relaciji je zanemareno nekoliko faktora: -

pretpostavka da su vremena obrade u čvorovima i vremena propagacije signala jednaka nuli; zanemarena je činjenica da se u stvarnim mrežama uz izvorne informacije nalaze i upravljačke informacije koje dodatno opterećuju mrežu.

Rezultat M/M/1 modela daje kašnjenje izvornog prometa informacijskih jedinica za pojedinačni kanal. Kao što je ustanovljeno ranije, pri analizi sistema posluživanja, to se kašnjenje sastoji od dva dijela: -

vremena čekanja u repu; vremena posluživanja.

Osnove telekomunikacija 35

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

Vrijeme posluživanja ima srednju vrijednost koja je srazmjerna dužini informacijske b jedinice TSi = , a kao usluga ovdje se javlja prenos informacijske jedinice između μc i čvorova koje povezuje i-ta grana. Vrijeme čekanja TWi =

b ⋅ ρi , međutim, ovisno je o ci (1 − ρ i )

spomenutom opterećenju i-te grane. Na narednoj slici je prikazana karakteristika kašnjenja pomoću parametra T0 konstantnog kašnjenja informacijske jedinice u stabilnom području opterećenja mreže (γ < γ*) i γ* opterećenja zasićenja mreže kod kojeg T postaje ∞ .

M/M/1 T0

γ*

T0 se jednostavno računa kao kašnjenje ''neopterećene'' mreže i to tako da je vanjsko opterećenje γ → 0 . Uz ovakve granične uslove se dobije:

λi i =1 γμc i M

T0 = ∑

(43)

Uvedimo i značenje dužine puta prema definiciji: njk = {dužina puta Π jk }={broj grana uključenih u Π jk }. Ta je dužina različita za pojedine j,k i uz to prenos pojedinih komponenti na ukupnoj dužini ovisi o prometnom opterećenju puta, tako da možemo izračunati prosječnu dužinu puta za mrežu u cjelosti prema relaciji: N

N

n = ∑∑ j =1 k =1

n jk γ jk

γ

(44)

Doprinos γjk prometa ukupnom unutrašnjem prometu λ biće jednak njkγjk zbog toga što γjk načini njk ''skokova'' kroz mrežu i svaki put da svoj doprinos unutrašnjem prometu. Osnove telekomunikacija 36

ELEKTROTEHNIČKI FAKULTET UNIVERZITETA U SARAJEVU Odsjek za telekomunikacije

Na osnovu provedenog razmatranja možemo napisati: M

N

N

i =1

j =1 k =1

λ = ∑ λi = ∑∑ n jk γ jk

(45)

Jednačine (44) i (45) jednostavno određuju srednju dužinu puta: n=

λ γ

(46)

Koristeći se srednjom dužinom puta i izrazom (43) možemo napisati izraz za kašnjenje neopterećene mreže: M

T0 = n∑ i =1

λi / λ μc i

(47)

λi ostaje konstantan i funkcija je samo puteva usmjeravanja λ vanjskog toka kroz mrežu. Napomenimo da odnos

Opterećenje zasićenja mreže γ* izračunava se ispitivanjem mjesta u mreži na kojem je ''usko grlo'', jer opterećenje zasićenja odgovara najmanjoj vrijednosti γ kod koje postaje kritična grupa i0 zasićena, tok jednak kapacitetu,

μc i 0 = λ i 0

Osnove telekomunikacija 37