Univerza v Ljubljani
Fakulteta za raˇ cunalniˇstvo in informatiko
Jurij Kolenik
Analiza porazdelitev medprihodnih ˇ casov paketov pri sprejemu pretakanja
videoposnetka
diplomsko delo
univerzitetni ˇstudijski program prve stopnje raˇcunalniˇstvo in informatika
prof. dr. Miha Mraz mentor asist. dr. Miha Janeˇz
somentor
©2021, Univerza v Ljubljani, Fakulteta za raˇcunalniˇstvo in informatiko
Rezultati diplomskega dela so intelektualna lastnina Fakultete za raˇcunalniˇstvo in informatiko Univerze v Ljubljani. Za objavljanje ali izkoriˇsˇcanje rezultatov diplomskega dela je potrebno pisno
Tematika naloge:
Kandidat naj v svojem delu vzpostavi dva tipa merilnih eksperimentov za merjenje medprihodnih ˇ
casov IP paketov pri sprejemu pretakanja video vsebin. V prvem primeru naj bo oddajna naprava v domaˇcem okolju, v drugem primeru pa v oblaˇcni infrastrukturi. V obeh primerih naj bo sprejemna naprava locirana v domaˇcem okolju. Kandidat naj v nadaljevanju opravi analizo medprihodnih ˇcasov v domeni primerjave s hipotetiˇcno sorodno umetno eksponento in umetno Paretovo porazdelitvijo
izjava o avtorstvu diplomskega dela
Spodaj podpisani izjavljam, da sem avtor dela, da slednje ne vsebuje materiala, ki bi ga kdorkoli predhodno ˇze objavil ali oddal v obravnavo za pridobitev naziva na univerzi ali drugem visokoˇsolskem zavodu, razen v primerih kjer so navedeni viri.
S svojim podpisom zagotavljam, da:
sem delo izdelal samostojno pod mentorstvom prof. dr. Mihe Mraza in somentor- stvom asist. dr. Mihe Janeˇza,
so elektronska oblika dela, naslov (slov., angl.), povzetek (slov., angl.) ter kljuˇcne besede (slov., angl.) identiˇcni s tiskano obliko in
soglaˇsam z javno objavo elektronske oblike dela v zbirki “Dela FRI”.
povzetek
Univerza v Ljubljani
Fakulteta za raˇcunalniˇstvo in informatiko Jurij Kolenik
Analiza porazdelitev medprihodnih ˇ casov paketov pri sprejemu pretakanja videoposnetka
V dobi klasiˇcnih telefonskih omreˇzij je bilo porajanje prometa porazdeljeno po Poissonovi porazdelitvi. V sodobnih omreˇzjih, kot je internet z zanj tipiˇcnim raznolikim prometom, pa to ne drˇzi veˇc. Vse bolj se zdi, da je dolgorepa ali Paretova porazdelitev tista, po kateri se porazdeljujejo medprihodni ˇcasi paketov.
V okviru delovne hipoteze se spraˇsujemo, kako se porazdeljujejo medprihodni ˇcasi paketov video prometa, ki se pretaka po omreˇzju. Doloˇciti ˇzelimo, ali je porazdelitev medprihodnih ˇcasov bolj podobna eksponenti porazdelitvi, ali pa Paretovi porazdelitvi.
V diplomski nalogi analiziramo eksperimentalno pridobljeni spletni promet med iz- vorom in ponorom in poskuˇsamo ugotoviti kateri porazdelitvi je porazdelitev medpri- hodnih ˇcasov bolj podobna. V okviru diplomske naloge smo postavili dva tipa eks- perimentov, pri ˇcemer je v obeh prisoten video streˇznik, ki oddaja video promet (od- dajna naprava) in raˇcunalnik, ki promet sprejema (sprejemna naprava). Eksperimenta se razlikujeta v fiziˇcni lokaciji oddajne naprave. V prvem tipu eksperimenta se od- dajna naprava nahaja v domaˇcem omreˇzju, v drugem tipu eksperimenta pa v Zdruˇzenih drˇzavah Amerike. Analiza je potekala tako, da smo generirali takˇsno umetno Paretovo porazdelitev in takˇsno umetno eksponentno porazdelitev, ki sta najbolj podobni eks- perimentalno pridobljeni porazdelitvi. Nato smo vsako umetno generirano porazdelitev primerjali z eksperimentalno pridobljeno porazdelitvijo s pomoˇcjo Jensen-Shannonove divergence. Koda vseh skript, ki smo jih kreirali za pomoˇc pri analizi, je dostopna na naslovu https://github.com/JeznaSpianca/diploma_skripte. Rezultati, ki smo jih pridobili, potrjujejo naˇso hipotezo o porazdelitvi omreˇznega prometa.
Kljuˇcne besede:porazdelitev prometa, Poissonova porazdelitev, Paretova porazdelitev, eksperiment, eksponentna porazdelitev, Jensen-Shannonova divergenca
abstract
University of Ljubljana
Faculty of Computer and Information Science Jurij Kolenik
Analysis of packet interarrival times distribution in video streaming traffic
In the age of classical telephone networks, the generation of traffic was distributed accord- ing to the Poisson distribution. In modern networks, such as the Internet with its typical diverse traffic, this is not the case. Increasingly, the long-tailed or Pareto distribution seems to be the one by which the inter-arrival times of packets are distributed.
In the context of working hypotheses, we wonder how the inter-arrival times of video traffic packets flowing across the network are distributed. We want to determine whether the inter-arrival time distribution is more similar to the exponential distribution or to the Pareto distribution.
In this thesis we analyze the experimentally obtained web traffic with source and sink and try to determine which distribution is more similar to the distribution of inter-arrival times. As part of this thesis, we set up two types of experiments, both of which have a video server that transmits video traffic (transmitting device) and a computer that receives (receiving device). The experiment differs in the physical lo- cation of the transmitting devices. In the first type of experiment, the transmitting device is located in the home network, and in the second type of experiment, in the United States. The analysis was performed by generating such an artificial Pareto dis- tribution and such an artificial exponential distribution that is most suitable for the experimentally obtained distribution. We then compared each artificially generated dis- tribution with the experimentally obtained distribution using the Jensen-Shannon diver- gence. The code of all the scripts we created to help with the analysis is available at https://github.com/JeznaSpianca/diploma_skripte. The results we obtained con- firm our hypothesis about the distribution of network traffic.
Key words:traffic distribution, Poisson distribution, Pareto distribution, experiment, exponential distribution, Jensen-Shannon divergence
zahvala
Zahvaljujem se prof. dr. Mihi Mrazu in asist. dr. Mihi Janeˇzu za vso pomoˇc, komentarje in vloˇzen ˇcas. Zahvaljujem se tudi svoji druˇzini in prijateljem za podporo.
— Jurij Kolenik, Kamnik, september 2021.
kazalo
Povzetek i
Abstract iii
Zahvala v
1 Uvod 1
2 Opis merilnih eksperimentov 5
2.1 Oddajna naprava v domaˇcem omreˇzju . . . 5
2.2 Oddajna naprava v ZDA . . . 6
2.3 Uporabljene tehnologije . . . 6
2.3.1 Postavitev eksperimenta na domaˇci lokaciji . . . 7
2.3.2 Postavitev eksperimenta na oddaljeni lokaciji . . . 7
2.3.3 Zajem prometa . . . 7
2.3.4 Analiza rezultatov . . . 8
2.3.5 Uporabljena video datoteka . . . 8
3 Izvedba meritev 9 3.1 Pridobitev medprihodnih ˇcasov iz datoteke prometa . . . 9
3.2 Prikaz podatkov . . . 10
3.3 Postopek analize podatkov . . . 10
4 Analiza rezultatov 15 4.1 Analiza eksperimenta z oddajno napravo v domaˇcem omreˇzju . . . 15
4.1.1 Primerjava z umetno eksponentno porazdelitvijo . . . 17
4.1.2 Primerjava z umetno Paretovo porazdelitvijo . . . 18
viii Kazalo
4.1.3 Zakljuˇcni komentar . . . 18
4.2 Analiza eksperimenta z oddajno napravo na oddaljeni lokaciji . . . 20
4.2.1 Primerjava z umetno eksponentno porazdelitvijo . . . 20
4.2.2 Primerjava z umetno Paretovo porazdelitvijo . . . 22
4.2.3 Zakljuˇcni komentar . . . 23
4.3 Komentar o natanˇcnosti izraˇcunov . . . 25
5 Zakljuˇcek 27
1 Uvod
Leta 1909 je A. K. Erlang postavil temelje teorije ˇcakalnih vrst, kjer je matematiˇcno dokazal, da se v telefonskem omreˇzju klici porajajo po Poissonovi porazdelitvi [8], kar pomeni da je njihovo porajanje nakljuˇcno. Njegove ugotovitve so se kmalu zaˇcele upora- bljati v mnogih podjetjih za organizacijo operaterjev telefonskih linij s ciljem optimiza- cije telefonskih centrov. S pojavom interneta smo dobili omreˇzje po katerem se pretaka veˇc vrst prometa, kot so prenos zvoka, videa in interaktivnih podatkov v realnem ˇcasu.
Vpraˇsanje, ki se nam postavlja je, ali je moˇzno uporabiti izsledke iz raziskovanja prometa v telefonskem omreˇzju in teorijo A. K. Erlang-a tudi pri analiziranju prometa v internetu.
Izkaˇze se, da obstajajo nekatera dejstva iz Erlang-ove teorije, ki veljajo tudi za internetni promet. Vir [13] priporoˇca uporabo teorije, kajti izkaˇze se, da je porajanje zahtev po prenosih podatkov katerekoli vrste v internetu porazdeljeno po Poissonovi porazdelitvi.
Omenjeno trditev potrdi tudi vir [14], ki analizira porazdelitev zahtev uporabnikov po TELNET in FTP sejah, ter ugotovi, da je le te moˇzno modelirati s Poissonovo porazdeli- tvijo. ˇCas prihoda zahteve za sejo posameznega uporabnika je torej nakljuˇcen in sovpada z matematiˇcno teorijo A. K. Erlang-a. Vendar pa se je pri analizi paketnega prometa
2 1 Uvod
vzpostavljenih sej izkazalo, da mnogokrat Poissonova porazdelitev ni najbolj primerna [12,14]. V internetu ter ostalih sodobnih omreˇzjih promet poteka paketno. Ko govorimo o porajanju prometa, govorimo o porazdelitvi medprihodnih ˇcasov med posameznimi pa- keti. Medprihodni ˇcas je ˇcas med prihodoma dveh zaporednih paketov. Izkaˇze se, da je za paketni promet znaˇcilno, da prihajajo paketi v skupinah in da prihaja do izbru- hov (angl. burstiness), kjer v zelo kratkem ˇcasu do ponora pride veˇcje ˇstevilo paketov.
Vir [12] predlaga vlakovni model porajanja paketov v omreˇzjih, kjer skupino paketov od izvora do ponora predstavijo kot vlak, kjer posameznen vagon predstavlja posamezen paket iz skupine. Tako se upoˇsteva izbruhe ter skupinske prihode. Upoˇstevajoˇc navedena dejstva se zdi, da nam v praksi takˇsno porazdelitev prometa najbolje opiˇse Paretova ali dolgorepa porazdelitev. Vir [7] na simuliranem omreˇznem prometu, ki upoˇsteva izbruhe paketov, pokaˇze, da se Paretova porazdelitev sprejemljivo dobro prilagaja simuliranemu prometu. Vir [14] tudi potrdi primernost Paretove porazdelitve pri analizi paketnega prometa v TELNET in FTP sejah.
Naˇsa delovna hipoteza obsega doloˇcitev porazdelitve omreˇznega prometa. Konkre- tneje skuˇsamo potrditi hipotezo, da se omreˇzni promet, ki nosi podatke video vsebine, porazdeljuje po Paretovi porazdelitvi.
V priˇcujoˇcem diplomskem delu analiziramo rezultate dveh tipov eksperimentov. V obeh tipih eksperimentov na domaˇcem raˇcunalniku zajemamo video, ki se nahaja na video streˇzniku. Povedano drugaˇce zajemamo pakete, ki prihajajo v naˇs raˇcunalnik. V prvem tipu eksperimenta se video streˇznik nahaja v domaˇcem omreˇzju, v drugem tipu eksperimenta pa se streˇznik nahaja na oddaljeni lokaciji v Zdruˇzenih drˇzavah Amerike.
Medprihodne ˇcase paketov v obeh primerih nato analiziramo in za vsak tip eksperimenta pridobljeno eksperimentalno porazdelitev primerjamo z umetno1 generirano eksponen- tno2 porazdelitvijo in umetno generirano Paretovo porazdelitvijo. Cilj primerjave je doloˇcitev umetne porazdelitve, ki bolje pokriva eksperimentalno pridobljene medpriho- dne ˇcase. Koda vseh skript, ki smo jih kreirali za pomoˇc pri analizi, je dostopna na naslovuhttps://github.com/JeznaSpianca/diploma_skripte.
V drugem poglavju sta opisana oba tipa eksperimentov. V tretjem poglavju opiˇsemo postopek zajema omreˇznega prometa in postopek analize zajetih podatkov. V ˇcetrtem
1Umetna porazdelitev - porazdelitev, ki je matematiˇcno enoliˇcno izrazljiva.
2Ce je ˇˇ stevilo porojenih paketov v ˇcasovnem intervalu porazdeljeno po Poissonu, potem so medpri- hodni ˇcasi porazdeljeni eksponentno. Zato mi generiramo eksponentno porazdelitev.
3 poglavju analiziramo promet in prikaˇzemo rezultate ter jih komentiramo. V petem po- glavju povzamemo ugotovitve diplomskega dela in navedemo moˇzne dodatne raziskave na tem podroˇcju.
2 Opis merilnih eksperimentov
Promet v obeh tipih eksperimentov predstavlja pretakanje video vsebine. Eksperimenta se razlikujeta v lokaciji streˇznika z video vsebino. V prvem primeru je bila oddajna naprava postavljena v domaˇcem omreˇzju na lokaciji v Kamniku, v drugem primeru pa v Zdruˇzenih drˇzavah Amerike pri ponudniku oblaˇcnih storitev. V obeh primerih je bila sprejemna naprava na domaˇci lokaciji avtorja diplome v Kamniku.
2.1 Oddajna naprava v domaˇ cem omreˇ zju
Slika2.1prikazuje shemo eksperimenta izvedenega v celoti v domaˇcem omreˇzju. Shema prikazuje osebni raˇcunalnik, s katerim smo zajemali promet, Raspberry Pi, na katerem se nahaja spletni streˇznikApache[1] in predstavlja oddajno napravo ter stikalo, na katerega sta obe napravi povezani. Stikalo omogoˇca hitrost prenosa podatkov do 1000 Mbps (angl.
Megabits per second).
6 2 Opis merilnih eksperimentov
Slika 2.1Shema eksperimenta izvedenega v celoti v domaˇcem omreˇzju.
2.2 Oddajna naprava v ZDA
Slika2.2prikazuje shemo eksperimenta izvedenega z oddaljene lokacije. Raˇcunalnik, ki je zajemal promet, je povezan na stikalo, to pa je povezano na usmerjevalnik, ki deluje kot privzeti prehod v internet. Povezava teˇce do oddaljenega spletnega streˇznika ponudnika GoogieHost. ˇCe IP naslov streˇznika vnesemo v spletni straniip2location.com[2], nam ta vrne podatke o lokaciji streˇznika. Iz podatkov lahko razberemo, da se streˇznik nahaja v Zdruˇzenih drˇzavah Amerike, bolj natanˇcno v mestu New Jersey s pribliˇznimi koordi- natami 40.790013 zemljepisne ˇsirine in -74.062078 zemljepisne dolˇzine. ˇCe s pomoˇcjo Google Maps [3] naredimo aproksimacijo razdalje med raˇcunalnikom, ki zajema promet in se nahaja v Kamniku, ter med lokacijo streˇznika, ki oddaja video vsebino, dobimo razdaljo 6790 kilometrov.
2.3 Uporabljene tehnologije
Za postavitev eksperimentov smo uporabili orodja in tehnologije, ki so nam bile poznane in smo jih spoznali tekom ˇstudija.
2.3 Uporabljene tehnologije 7
Slika 2.2Shema eksperimenta iz oddaljene lokacije.
2.3.1 Postavitev eksperimenta na domaˇci lokaciji
Za postavitev eksperimenta v domaˇcem omreˇzju smo za oddajnik uporabili mikroraˇcunalnik Raspberry Pi [4], na katerega smo postavili spletni streˇznik. Za programsko opremo spletnega streˇznika smo uporabili odprtokodno reˇsitev Apache, ki nam je omogoˇcila po- stavitev enostavne spletne strani. V spletni strani smo uporabili html gradnik <video
>, ki nam je omogoˇcil vstavitev naˇse video datoteke v formatump4.
2.3.2 Postavitev eksperimenta na oddaljeni lokaciji
Za postavitev eksperimenta na oddaljeni lokaciji smo uporabili ponudnika spletnega go- stovanjaGoogieHost[5], kjer smo dobili domenodiploma.cu.mana ip naslovu 66.45.229.178.
Za vzpostavitev strani smo morali na streˇznik platforme naloˇziti naˇs video in kodo za sple- tno stran, kjer smo uporabili enako datoteko, kot pri eksperimentu v domaˇcem omreˇzju.
2.3.3 Zajem prometa
Za zajem prometa na sprejemni napravi smo uporabili odprtokodno programsko opremo Wireshark [6]. Orodje smo si izbrali zato, ker omogoˇca enostavno filtriranje in izvoz
8 2 Opis merilnih eksperimentov v tekstovno datoteko in nato priˇceli z njihovo obdelavo.
2.3.4 Analiza rezultatov
Za pisanje skript za analizo podatkov smo izbrali visokonivojski programski jezikPython.
Zanj smo se odloˇcili, ker ga poznamo in ima na razpolago veliko knjiˇznic, ki so nam olajˇsale in pohitrile delo. Za izraˇcun histogramov smo uporabili knjiˇznici Numpy in Scipy, za prikaz histogramov pa smo uporabili knjiˇznicoMatplotlib.
2.3.5 Uporabljena video datoteka
Video, ki smo ga naloˇzili na video streˇznik, je dostopen na naslovu https://www.
youtube.com/watch?v=OvRe01ya_io&ab_channel=AlarmTimer([Nazadnje dostopano: 29.
8. 2021]). Video je v formatu MP4, velik 633 MB, v loˇcljivosti 1920 x 1080 in je dolg 8 ur ter 25 sekund.
3 Izvedba meritev
Podatke o prometu posameznega eksperimenta smo pridobili po vnaprej doloˇcenih kora- kih, ki so opisani v naslednjih razdelkih. Pri doloˇcanju postopka analize podatkov nam je bil v pomoˇc vir [18].
3.1 Pridobitev medprihodnih ˇ casov iz datoteke prometa
Iz datoteke zajetega prometa, ki smo jo dobili z uporabo orodjaWireshark, smo morali pridobiti medprihodne ˇcase paketov, ki so bili povezani z naˇso video vsebino. Najprej smo morali promet filtrirati, kar smo dosegli tako, da smo v orodjuWireshark uporabili filterip.src == ip_streˇznika. Ta filter smo potrebovali, ker je v ˇcasu zajema prometa v raˇcunalnik prihajal tudi omreˇzni promet, ki ni bil povezan z naˇsim eksperimentom in pakete tega prometa smo izpustili. Nato smo v Wireshark-u nastavili prikaz stolpca Time delta from previous displayed frame, ki prikazuje medprihodni ˇcas med pri- kazanima okvirjema v katerih se nahajajo paketi. Tako smo pridobili medprihodne ˇcase paketov, ki so priˇsli od oddajne naprave v ˇcasu prenosa video vsebine. Na koncu smo uporabili moˇznost za izvoz podatkov v navadno tekstovno datoteko, kjer smo izbrali
10 3 Izvedba meritev
opcijo, naj se izvozijo le prikazani podatki. Tako smo v tekstovno datoteko dobili po vrsticah loˇcene medprihodne ˇcase paketov.
3.2 Prikaz podatkov
Za prikaz podatkov smo napisali program s programskim jezikom Python. Program deluje tako, da najprej prebere vsebino tekstovne datoteke z medprihodnimi ˇcasi v tabelo.
Nato uporabi metodo histogram_bin_edges() za izraˇcun meja razredov histograma.
Funkciji posreduje tabelo z medprihodnimi ˇcasi in pa parameter bins="sturges", ki veleva, da za izraˇcun ˇstevila razredov uporabi Sturgesovo pravilo z enaˇcbo
nh= log2n+ 1, (3.1)
kjernh predstavlja ˇstevilo razredov,n pa ˇstevilo podatkov v tabeli. Po izraˇcunu meja razredov metoda uporabi funkcijo histogram(), ki iz tabele podatkov izraˇcuna histo- gram. Od ostalih parametrov, ki jih metoda sprejme, smo ji posredovali tudi parameter bins="sturges", s katerim doloˇcimo, da bo metoda za izraˇcun ˇstevila razredov upora- bila Sturgesovo pravilo. Med vrednostmi, ki jih metoda vrne, je tudi tabela, ki za vsak izraˇcunan razred vsebuje ˇstevilo medprihodnih ˇcasov, ki vanj spadajo. To tabelo nato uporabimo, da izraˇcunamo relativno frekvenco medprihodnih ˇcasov v vsakem razredu.
Za izris histograma metoda izvede vrstici hist(array,bins), ki izraˇcuna histogram, nato pashow()za prikaz histograma.
3.3 Postopek analize podatkov
Naˇs cilj je, da najdemo takˇsno matematiˇcno izrazljivo porazdelitev, ki se najbolje prilega naˇsi eksperimentalni porazdelitvi medprihodnih ˇcasov. Tako smo naˇso porazdelitev pri- merjali z eksponentno in Paretovo porazdelitvijo. Za pomoˇc pri doloˇcitvi porazdelitve, ki se najbolje pribliˇza naˇsi porazdelitvi medprihodnih ˇcasov, smo napisali tudi program v programskem jeziku Python. Program v tabelo prebere podatke o medprihodnih ˇcasih iz tekstovne datoteke. Nato generira umetno eksponentno porazdelitev, kjer vsak umeten medprihodni ˇcas1 generira po enaˇcbi
tinterbirth=−1
λ∗ln(1−p), (3.2)
1Umeten medprihodni ˇcas je medprihodni ˇcas, ki je matematiˇcno enoliˇcno izrazljiv.
3.3 Postopek analize podatkov 11 povzeti po viru [11], kjer ppredstavlja nakljuˇcno izbrano vrednost iz intervala [0,1], λ1 pa povpreˇcni ˇcas med rojstvoma dveh zahtev ali paketov. V programu za generiranje parameterapuporabimo funkcijorandom.random(). Ker ˇzelimo, da bi se vrednosti ek- sperimentalne in eksponentne porazdelitve ˇcimbolj ujemale, moramo pravilno definirati parameterλ1, ki ga lahko oznaˇcimo tudi st. Za kriterij, katerega bomo izbrali za ocenjeva- nje ujemanja, bomo vzeli ˇsirino razreda v frekvenˇcni porazdelitvi. Za pridobitev najbolj optimalnegatin poslediˇcno optimalne eksponentne porazdelitve, bomo tako v zanki ge- nerirali eksponentne porazdelitve z razliˇcnimi vrednostmi parametra t in za optimalno vzeli tisto, ki bo imela najmanjˇso razliko v ˇsirini razreda v primerjavi z naˇso porazdeli- tvijo. Razlog za uporabo kriterija razlike v ˇsirini razreda histograma je v tem, da razliˇcni parametritgenerirajo porazdelitve z razliˇcnimi frekvenˇcnimi porazdelitvami histograma.
Poslediˇcno je histogram eksperimentalne porazdelitve in histogram umetno generirane porazdelitve vizualno drugaˇcen. Za primerjavo naˇse porazdelitve in umetno generirane porazdelitve smo se po pregledu vira [16] odloˇcili za uporabo Jensen-Shannonove diver- gence, ki izmeri podobnost dveh porazdelitev. Izraˇcun divergence nam omogoˇca knjiˇznica scipyz funkcijojensenshannon(). Funkcija divergenco izraˇcuna po enaˇcbi
DJ S=
rD(p||m) +D(q||m)
2 , (3.3)
kjer sta pin q tabeli porazdelitev, m povpreˇcje tabel porazdelitev, D pa je Kullback- Leiblerjeva divergenca [10], ki se izraˇcuna po enaˇcbi
DKL(P||Q) =X
x
p(x)log2
p(x)
q(x), (3.4)
kjer stap(x) inq(x) verjetnostni porazdelitvi sluˇcajne spremenljivkex2. Opisan postopek generiranja umetne eksponentne porazdelitve in naˇse porazdelitve je z izsekom Python kode predstavljena v zapisu3.1.
Listing 3.1Koda generiranja eksponentne porazdelitve in primerjava.
1
2 #p r i p r a v a t a b e l i n s p r e m e n l j i v k
3 e k s p p o r a z d e l i t e v = [ ]
4 o p t i m a l e n e k s p = [ ]
5 m i n i m a l n a r a z l i k a = 0
2Vrednost, ki smo jo oznaˇcili zDJ Sje dejansko Jensen-Shannonova distanca. ˇCe bi izraz izraˇcunali brez korena, bi vrednost bila divergenca. V nadaljevanju bomo zaradi laˇzjega razumevanje za vrednost
12 3 Izvedba meritev
6 s p o d n j a m e j a = f l o a t( s y s . a r g v [ 1 ] )
7 t m i n i m a l e n = s p o d n j a m e j a
8 t t r e n u t n i = t m i n i m a l e n
9
10 #na z a c e t k u s e z a n a j b o l j o p t i m a l n o e k s p o n e n t n o p o r a z d e l i t e v g e n e r i r a k a r p r v o po v r s t i
11 f o r i i n r a n g e( 0 , l e n( n a s a p o r a z d e l i t e v ) ) :
12 t m e d p r i h o d n i =−t ∗ numpy . l o g (f l o a t( 1 ) − random . random ( ) )
13 e k s p p o r a z d e l i t e v . append ( t m e d p r i h o d n i )
14 r o b o v i e k s p = numpy . h i s t o g r a m b i n e d g e s ( eksp , l e n( r o b o v i n a s e p o r a z d e l i t v e )
− 1 )
15 r a z l i k a r o b o v i e k s p = r o b o v i e k s p [ 1 ] − r o b o v i e k s p [ 0 ]
16 m i n i m a l n a r a z l i k a = a b s( r a z l i k a r o b o v i e k s p − r a z l i k a r o b o v i o r i g i n a l n a )
17 o p t i m a l e n e k s p = e k s p p o r a z d e l i t e v
18
19 #zanka , k i g e n e r i r a umetne e k s p o n e n t n e p o r a z d e l i t v e i n i s c e n a j b o l j o p t i m a l n o
20 f o r t i n numpyp . a r a n g e ( s p o d n j a m e j a + 0 . 0 1 , z g o r n j a m e j a , 0 . 0 1 ) :
21 e k s p p o r a z d e l i t e v = [ ]
22
23 #g e n e r i r a n j e nove p o r a z d e l i t v e
24 f o r i i n r a n g e( 0 , l e n( n a s a p o r a z d e l i t e v ) ) :
25 t m e d p r i h o d n i =−t ∗ numpyp . l o g (f l o a t( 1 ) − random . random ( ) )
26 e k s p p o r a z d e l i t e v . append ( t med )
27
28 #i z r a c u n r a z l i k e r o b o v nove g e n e r i r a n e e k s p o n e n t n e p o r a z d e l i t v e t e r p r i m e r j a n j e z t r e n u t n o n a j b o l j o p t i m a l n o g e n e r i r a n o
p o r a z d e l i t v i j o
29 r o b o v i e k s p = np . h i s t o g r a m b i n e d g e s ( e k s p p o r a z d e l i t e v ,l e n( r o b o v i n a s e p o r a z d e l i t v e ) − 1 )
30 r a z l i k a r o b o v i e k s p = r o b o v i e k s p [ 1 ] − r o b o v i e k s p [ 0 ]
31 i f m i n i m a l n a r a z l i k a > a b s( r a z l i k a r o b o v i e k s p − r a z l i k a r o b o v i o r i g i n a l n a ) :
32 m i n i m a l n a r a z l i k a = a b s( r a z l i k a r o b o v i e k s p − r a z l i k a r o b o v i o r i g i n a l n a )
33 o p t i m a l e n e k s p = e k s p p o r a z d e l i t e v
34 t m i n i m a l e n = t
35 36
37 d i v e r g e n c a = d i s t a n c e . j e n s e n s h a n n o n ( n a s a p o r a z d e l i t e v , o p t i m a l e n e k s p )
Poleg eksponentne porazdelitve smo naˇso porazdelitev primerjali tudi s Paretovo po-
3.3 Postopek analize podatkov 13 razdelitvijo. Izraˇcun medprihodnega ˇcasa umetne Paretove porazdelitve program izvede po enaˇcbi [11]
tinterbirth= xm
(1−p)α1, (3.5)
kjer p predstavlja nakljuˇcno izbrano ˇstevilo iz intervala [0,1], α predstavlja parameter oblike in xm predstavlja lokacijski parameter. Pri primerjanju s Paretovo distribucijo ne poznamo parametrov αin xm, zato smo ju pridobili s preizkuˇsanjem. Tako kot pri eksponentni porazdelitvi smo ˇzeleli dobiti umetno porazdelitev, ki se bo najbolj prilaga- jala naˇsi. Za kriterij prilagajanja smo zopet vzeli ˇsirino razreda histograma. Program predstavljen v izpisu3.2v dvojni zanki preizkuˇsa razliˇcne vrednostiαin xm, ter vzame tisto kombinacijo, pri kateri ima porazdelitev najbolj podobno ˇsirino razreda.
Listing 3.2Koda generiranja Paretove porazdelitve in primerjava.
1
2 #p r i p r a v a t a b e l i n s p r e m e n l j i v k
3 a l f a = f l o a t( s y s . a r g v [ 1 ] )
4 b e t a = f l o a t( s y s . a r g v [ 2 ] )
5 p a r e t o p o r a z d e l i t e v = [ ]
6 p a r e t o o p t i m a l e n = [ ]
7 m i n i m a l n a r a z l i k a = 0
8
9 #na z a c e t k u s e z a n a j b o l j o p t i m a l n o P a r e t o v o p o r a z d e l i t e v g e n e r i r a k a r p r v o po v r s t i
10 f o r i i n r a n g e( 0 , l e n( n a s a p o r a z d e l i t e v ) ) :
11 e k s p o n e n t = 1 . 0 / a l f a
12 baza = 1−random . random ( )
13 p o t e n c a = pow( r , e )
14 t m e d p r i h o d n i = b e t a / p o t e n c a
15 p a r e t o p o r a z d e l i t e v . append ( t m e d p r i h o d n i )
16 r o b o v i p a r e t o = numpy . h i s t o g r a m b i n e d g e s ( p a r e t o p o r a z d e l i t e v ,l e n( r o b o v i n a s e p o r a z d e l i t v e ) − 1 )
17 r a z l i k a r o b o v i p a r e t o = r o b o v i p a r e t o [ 1 ] − r o b o v i p a r e t o [ 0 ]
18 m i n i m a l n a r a z l i k a = a b s( r a z l i k a r o b o v i p a r e t o − r a z l i k a r o b o v i o r i g i n a l n a )
19 p a r e t o o p t i m a l e n = p a r e t o p o r a z d e l i t e v
20 o p t i m a l n a a l f a = a l f a
21 o p t i m a l n a b e t a = b e t a
22
23 #g e n e r i r a n j e P a r e t o v i h p o r a z d e l i t e v i n i s k a n j e n a j b o l j o p t i m a l n e
24 f o r b t i n numpyp . a r a n g e ( b e t a , z g o r n j a m e j a , 0 . 1 ) :
14 3 Izvedba meritev
26 p a r e t o p o r a z d e l i t e v = [ ]
27
28 f o r i i n r a n g e( 0 , l e n( n a s a p o r a z d e l i t e v ) ) :
29 e k s p o n e n t = 1/ a l
30 baza = 1 − random . random ( )
31 p o t e n c a = pow( r , e )
32 t m e d p r i h o d n i = b t / p o t e n c a
33 p a r e t o p o r a z d e l i t e v . append ( t m e d p r i h o d n i )
34
35 r o b o v i p a r e t o = numpy . h i s t o g r a m b i n e d g e s (
p a r e t o p o r a z d e l i t e v , l e n( r o b o v i n a s e p o r a z d e l i t v e ) − 1 )
36 r a z l i k a r o b o v i p a r e t o = r o b o v i p a r e t o [ 1 ] − r o b o v i p a r e t o [ 0 ]
37 i f m i n i m a l n a r a z l i k a > a b s( r a z l i k a p a r e t o r o b o v i − r a z l i k a r o b o v i o r i g i n a l n a ) :
38 m i n i m a l n a r a z l i k a = a b s( r a z l i k a p a r e t o r o b o v i − r a z l i k a r o b o v i o r i g i n a l n a )
39 o p t i m a l n a a l f a = a l
40 o p t i m a l n a b e t a = b t
41 p a r e t o o p t i m a l e n = p a r e t o−p o r a z d e l i t e v
42
43 d i v e r g e n c a = d i s t a n c e . j e n s e n s h a n n o n ( n a s a p o r a z d e l i t e v , p a r e t o o p t i m a l e n )
4 Analiza rezultatov
Rezultate smo analizirali po postopku opisanem v razdelku 3.3, kjer smo se najprej lotili izvedbe in analiziranja eksperimenta z oddajnikom v domaˇcem omreˇzju, nato pa eksperimenta z oddajnikom na oddaljeni lokaciji.
4.1 Analiza eksperimenta z oddajno napravo v domaˇ cem omreˇ zju
Po filtriranju datoteke prometa eksperimenta v domaˇcem omreˇzju smo pridobili datoteko z 277.130 medprihodnimi ˇcasi. Najkrajˇsi medprihodni ˇcas je bil 0.000000075 sekund, najdaljˇsi 115.302908658 sekund, povpreˇcni pa 0.104 sekund. Program po Sturgesovemu pravilu izraˇcuna 20 razredov. Slika4.1prikazuje histogram medprihodnih ˇcasov. Tabela 4.1 prikazuje tabelo z razredi histograma, ˇstevilom ˇcasov v vsakem razredu in relativno frekvenco ˇcasov v vsakem razredu. Medprihodni ˇcasi so zaokroˇzeni na 9 decimalk, od- stotki relativnih frekvenc pa na 5 decimalk.
16 4 Analiza rezultatov
Razred Spodnja meja (s) Zgornja meja (s) ˇSt ˇcasov Rel. frekvenca (%)
1 0.000000075 5.765145504 275333 99.352
2 5.765145504 11.530290933 664 0.2396
3 11.530290933 17.295436362 1029 0.3713
4 17.295436362 23.060581792 99 0.0357
5 23.060581792 28.825727221 0 0.0000
6 28.825727221 34.590872650 3 0.0011
7 34.590872650 40.356018079 0 0.0000
8 40.356018079 46.121163508 0 0.0000
9 46.121163508 51.886308937 0 0.0000
10 51.886308937 57.651454367 0 0.0000
11 57.651454367 63.416599796 0 0.0000
12 63.416599796 69.181745225 1 0.0003
13 69.181745225 74.946890654 0 0.0000
14 74.946890654 80.712036083 0 0.0000
15 80.712036083 86.477181512 0 0.0000
16 86.477181512 92.242326941 0 0.0000
17 92.242326941 98.007472371 0 0.0000
18 98.007472371 103.772617800 0 0.0000
19 103.772617800 109.537763229 0 0.0000
20 109.537763229 115.302908658 1 0.0003
Tabela 4.1Tabela razredov histograma s ˇstevilom medprihodnih ˇcasov v vsakem razredu in relativno frekvenco medprihodnih ˇ
casov v razredu.
4.1 Analiza eksperimenta z oddajno napravo v domaˇcem omreˇzju 17
Slika 4.1Histogram medprihodnih ˇcasov eksperimenta v domaˇcem omreˇzju.
4.1.1 Primerjava z umetno eksponentno porazdelitvijo
Tabelo eksponentne porazdelitve smo generirali po postopku opisanem v razdelku 3.3.
Parameter 1λ smo dobili tako, da smo v zanki, ki je tekla od 1 do 10 s korakom 0.1 generirali umetne eksponentne porazdelitve. Medprihodne ˇcase smo generirali po enaˇcbi (3.2), generirali pa smo toliko ˇcasov, kot jih je bilo v naˇsi zajeti porazdelitvi. Za vsako smo izraˇcunali razliko v ˇsirini razreda histograma v primerjavi z naˇso porazdelitvijo. Na koncu smo vzeli tak parameter λ1 z najmanjˇso razliko v ˇsirini razreda. Tak postopek smo zaradi moˇznih statistiˇcnih napak ponovili petkrat, ter vzeli vrednost parametra
1
λ z najmanjˇso razliko v ˇsirini razreda histograma. Ta parameter ima vrednost 9.32 sekunde in nam generira umetno eksponentno porazdelitev, ki je najbolj podobna naˇsi porazdelitvi. Razlika med ˇsirinami razredov naˇse porazdelitve in umetne eksponentne je v rangu 0.001 sekunde, kar vzamemo kot sprejemljivo napako. Slika 4.2 prikazuje histogram umetne eksponentne porazdelitve. Funkcija jensenshannon() vrne razdaljo med eksperimentalno pridobljeno in eksponentno porazdelitvijoDJ S = 0.809. Vrednost je zaokroˇzena na 3 decimalke. Priˇsli smo tudi do ugotovitve, da je bila v vseh petih primerih generiranja najbolj optimalne eksponentne porazdelitve vrednost DJ S vedno
18 4 Analiza rezultatov
Slika 4.2Histogram medprihodnih ˇcasov umetne eksponentne porazdelitve v domaˇcem omreˇzju.
4.1.2 Primerjava z umetno Paretovo porazdelitvijo
Tabelo Paretove porazdelitve smo generirali po postopku, opisanem v razdelku3.3. Pa- rametraαinxmsmo dobili tako, da smo v vgnezdeni zanki, kjer sta parametra tekla od 0.1 do 10 z korakom 0.1, generirali umetne Paretove porazdelitve. Za vsako generirano porazdelitev smo primerjali razliko v ˇsirini razreda med umetno porazdelitvijo in naˇso eksperimentalno pridobljeno porazdelitvijo. Za sprejemljivo umetno porazdelitev smo vzeli tisto z najmanjˇso razliko v ˇsirini razreda. Generiranje porazdelitev smo ponovili petkrat in izbrali tisto, kjer je bila razlika med ˇsirinami razreda najmanjˇsa. Porazdelitev z najmanjˇso razliko v ˇsirini razreda smo dobili pri vrednostihα= 3.7 inxm= 4.7, kjer je razlika med ˇsirinami razredov v rangu 0.0001 sekunde. Slika4.3prikazuje histogram ume- tne Paretove porazdelitve. Funkcijajensenshannon()nam vrne razdaljoDJ S= 0.807.
Vrednost je zaokroˇzena na 3 decimalke. Tako kot pri generiranju umetne eksponentne po- razdelitve, smo tudi tukaj pri veˇc ponovitvah generiranja umetne Paretove porazdelitve opazili isto vrednostDJ S.
4.1.3 Zakljuˇcni komentar
Iz primerjave eksperimentalno pridobljene porazdelitve z umetno eksponentno in Pare- tovo porazdelitvijo smo opazili, da je naˇsa porazdelitev bolj podobna Paretovi porazdeli- tvi. Vendar pa sta obe vrednosti Jensen-Shannonove divergence zmerno veliki in je razlika
4.1 Analiza eksperimenta z oddajno napravo v domaˇcem omreˇzju 19
Slika 4.3Histogram medprihodnih ˇcasov umetne Paretove porazdelitve v domaˇcem omreˇzju.
med vrednostmi zelo majhna. Opazili smo, da je to posledica nekaterih medprihodnih ˇ
casov v naˇsi porazdelitvi, ki so nadpovpreˇcni in predstavljajo anomalije v omreˇzju. ˇCe na primer odstranimo iz naˇse porazdelitve najveˇcjih 100.000 medprihodnih ˇcasov, torej jih imamo 177.130, nam primerjavi s Paretovo in eksponentno porazdelitvijo pokaˇzeta ve- liko manjˇse vrednostiDJ S. Primerjava z eksponentno porazdelitvijo nam vrne vrednost DJ S = 0.345, primerjava s Paretovo porazdelitvijo pa DJ S = 0.131. ˇCe pa odstranimo 2771 medprihodnih ˇcasov, kar je pribliˇzno 1%, pa med vrednostmi ˇse ne opazimo velike razlike. Optimalna eksponentna porazdelitev ima divergenco DJ S = 0.811, optimalna Paretova porazdelitev paDJ S = 0.808. Nato smo procent odstranjenjih ˇcasov poveˇcali za 1. Tako smo odstranili 2% ali 5542 medprihodnih ˇcasov. ˇZe ob 1% veˇc odstranjenih najveˇcjih medprihodnih ˇcasov, smo dobili zelo veliko razliko v DJ S. Pri eksponentni porazdelitvi smo izraˇcunaliDJ S= 0.592, pri Paretovi porazdelitvi paDJ S = 0.539.
Eksperiment smo zaradi moˇznih statistiˇcnih napak ponovili ˇse enkrat. Dobili smo po- razdelitev z 261.573 medprihodnimi ˇcasi, z minimalnim ˇcasom 0.000000077 sekund, ma- ksimalnim ˇcasom 232.630938300 sekund in povpreˇcnim ˇcasom 0.111138095 sekund. Veli- kost razreda je 12.243733591 sekund. Optimalna eksponentna porazdelitev z najmanjˇso razliko v ˇsirini razreda je tista s parametrom t = 18.52 sekunde z Jensen-Shannonovo divergenco DJ S = 0.808. Optimalna Paretova porazdelitev z najmanjˇso razliko v ˇsirini
20 4 Analiza rezultatov
Slika 4.4Histogram medprihodnih ˇcasov eksperimenta z oddaljene lokacije.
DJ S= 0.805.
4.2 Analiza eksperimenta z oddajno napravo na oddaljeni lokaciji
Po filtriranju datoteke prometa eksperimenta z oddaljene lokacije, smo pridobili dato- teko z 785.451 medprihodnimi ˇcasi. V primerjavi z eksperimentom v domaˇcem omreˇzju je paketov veˇc zato, ker so se morali prenaˇsati paketi manjˇsih velikosti. Najkrajˇsi med- prihodni ˇcas je bil 0.000000071 sekund, najdaljˇsi 282.747838101 sekund, povpreˇcni pa je 0.0367 sekund. Program nam po Sturgesovemu pravilu izraˇcuna 21 razredov s ˇsirino razreda 13.464182763 sekunde. Meritev smo zaˇceli v ponedeljek, 16. 8. 2021, ob 8.00.
Slika4.4prikazuje histogram medprihodnih ˇcasov. Tabela4.2prikazuje tabelo z razredi histograma, ˇstevilom ˇcasov v vsakem razredu in relativno frekvenco ˇcasov v vsakem ra- zredu eksperimenta z oddaljene lokacije. Medprihodni ˇcasi so zaokroˇzeni na 9 decimalk, odstotki relativnih frekvenc pa na 5 decimalk.
4.2.1 Primerjava z umetno eksponentno porazdelitvijo
Postopek primerjave naˇse porazdelitve z umetno eksponentno porazdelitvijo smo naredili na enak naˇcin kot v razdelku4.1.1. Ko smo nekajkrat generirali eksponentno porazdeli- tev, smo opazili, da parametert, ki je tekel od 1 do 10 sekund, ni dovolj velik, zato smo se odloˇcili, da meje zanke prestavimo od 10 do 20 sekund. Tako generirane eksponentne po-
4.2 Analiza eksperimenta z oddajno napravo na oddaljeni lokaciji 21
Razred Spodnja meja (s) Zgornja meja (s) St ˇˇ casov Rel. frekvenca (%)
1 0.000000071 13.464182834 783935 99.8069
2 13.464182834 26.928365598 1391 0.17711
3 26.928365598 40.392548361 91 0.01159
4 40.392548361 53.856731124 20 0.00255
5 53.856731124 67.320913888 5 0.00064
6 67.320913888 80.785096651 1 0.00013
7 80.785096651 94.249279414 0 0.00000
8 94.249279414 107.713462178 0 0.00000
9 107.713462178 121.177644941 0 0.00000
10 121.177644941 134.641827704 1 0.00013
11 134.641827704 148.106010468 0 0.00000
12 148.106010468 161.570193231 0 0.00000
13 161.570193231 175.034375994 0 0.00000
14 175.034375994 188.498558758 6 0.00076
15 188.498558758 201.962741521 0 0.00000
16 201.962741521 215.426924284 0 0.00000
17 215.426924284 228.891107048 0 0.00000
18 228.891107048 242.355289811 0 0.00000
19 242.355289811 255.819472574 0 0.00000
20 255.819472574 269.283655338 0 0.00000
21 269.283655338 282.747838101 1 0.00013
22 4 Analiza rezultatov
Slika 4.5Histogram medprihodnih ˇcasov umetne eksponentne porazdelitve z oddaljene lokacije.
razdelitve so nam dale boljˇse rezultate. Porazdelitev z najmanjˇso razliko v ˇsirini razreda histograma smo dobili pri parametru λ1 = 18.63 sekunde, kjer je razlika v ˇsirini razredov v rangu 0.002 sekunde, kar je za nas spremenljivo. Slika4.5prikazuje histogram umetne eksponentne porazdelitve. Funkcijajensenshannon() nam vrne razdaljoDJ S = 0.809.
Vrednost je zaokroˇzena na 3 decimalke. VrednostDJ S se je v vseh poskusih generiranja najbolj optimalne eksponentne porazdelitve gibala med 0.808 in 0.809.
4.2.2 Primerjava z umetno Paretovo porazdelitvijo
Tabelo Paretove porazdelitve smo generirali po postopku opisanem v razdelku4.1.2. Ge- neriranje porazdelitev smo ponovili petkrat in izbrali tisto, pri kateri je bila razlika med ˇsirinami razreda najmanjˇsa. Porazdelitev z najmanjˇso razliko v ˇsirini razreda smo do- bili pri vrednostih α= 3.8 in xm = 8.4, kjer je razlika med ˇsirinami razredov v rangu 0.01 sekunde. Slika 4.6 prikazuje histogram umetne Paretove porazdelitve. Funkcija jensenshannon()nam vrne razdaljo DJ S = 0.806. Vrednost je zaokroˇzena na 3 deci- malke. Tako kot pri generiranju umetne eksponentne porazdelitve, smo tudi tukaj pri veˇc ponovitvah generiranja umetne Paretove porazdelitve opazili isto vrednostDJ S.
4.2 Analiza eksperimenta z oddajno napravo na oddaljeni lokaciji 23
Slika 4.6Histogram medprihodnih ˇcasov umetne Paretove porazdelitve z oddaljene lokacije.
4.2.3 Zakljuˇcni komentar
Iz primerjave eksperimentalno pridobljene porazdelitve z umetno eksponentno in Pare- tovo porazdelitvijo smo opazili, da je naˇsa porazdelitev bolj podobna Paretovi poraz- delitvi. Tako kot v razdelku 4.1.3 smo opazili, da sta vrednosti DJ S zmerno veliki in se razlikujeta le v tretji decimalki. Zopet smo iz tekstovne datoteke odstranili 100.000 najveˇcjih medprihodnih ˇcasov in poskusili ponovno generirati obe umetni porazdelitvi in jih ponovno primerjali z naˇso porazdelitvijo. Primerjava z eksponentno porazdelitvijo nam vrne vrednostDJ S = 0.686, primerjava s Paretovo porazdelitvijo paDJ S = 0.635.
Kot opazimo, sta vrednosti primerjav obeh porazdelitev ˇze bolj razliˇcni, kar pomeni, da je naˇsa porazdelitev vedno bolj podobna Paretovi in to potrjuje naˇso delovno hipotezo.
Eksperiment smo ponovili ˇse dvakrat v razliˇcnih ˇcasih. Opravili smo ga ˇse v sredo, 18.
8. 2021, ob 16.00 in v soboto, 21. 8. 2021, ob 24.00. Tabela 4.3prikazuje strnjene po- datke o eksperimentih. Iz tabele vidimo, da se rezultati nekoliko razlikujejo, vendar niso presenetljivi, kajti vseeno kaˇzejo na to, da je eksperimentalno pridobljena porazdelitev
24 4 Analiza rezultatov
Eksperiment v sredo Eksperiment v soboto
Stevilo medprihodnih ˇˇ casov 616877 715702
Minimalni medprihodni ˇcas (s) 0.000000074 0.000000076 Maksimalni medprihodni ˇcas (s) 497.578570565 1223.456871568 Povpreˇcni medprihodni ˇcas (s) 0.046752640 0.040302520 Velikost razreda histograma (s) 23.694217642 58.259851023 Parameter optimalne umetne ekspo-
nentne porazdelitve (s)
37.92 66.05
Jensen-Shannonova divergenca opti- malne eksponentne porazdelitve
0.807 0.817
Alfa parameter optimalne umetne Paretove porazdelitve
2.8 2.8
xmparameter optimalne umetne Pa- retove porazdelitve
3.4 9.2
Jensen-Shannonova divergenca opti- malne Paretove porazdelitve
0.804 0.814
Tabela 4.3Tabela podatkov ponovno izvedenih eksperimentov z oddaljeno lokacijo.
4.3 Komentar o natanˇcnosti izraˇcunov 25
4.3 Komentar o natanˇ cnosti izraˇ cunov
Izraˇcuni medprihodnih ˇcasov umetno generiranih porazdelitev, ki jih generiramo v naˇsi analizi, zahtevajo uporabo generatorjev nakljuˇcnih ˇstevil. Kot je opisano v razdelku3.3, naˇsa skripta pri doloˇcanju parametra, ki nam vrne najbolj optimalno umetno generirano porazdelitev, bodisi eksponentno, bodisi Paretovo, vsakiˇc znova generira porazdelitev s parametrom, ki se v tistem trenutku preverja za najbolj optimalno. Generiranje poraz- delitve pa vkljuˇcuje generator nakljuˇcnih ˇstevil, kajti tako zahtevajo enaˇcbe, ki doloˇcijo naˇcin izraˇcuna medprihodnega ˇcasa za porazdelitev. ˇCe za primer vzamemo generiranje umetne eksponentne porazdelitve v razdelku4.1.1eksperimenta v domaˇcem omreˇzju, kjer smo za optimalno eksponentno porazdelitev dobili tako s parametromt= 9.32 sekunde opazimo, da nam zaradi narave samih izraˇcunov lahko ponovno generiranje eksponen- tne porazdelitve z istim parametrom, rezultira v porazdelitev, ki je nekoliko drugaˇcna od tiste, ki je bila za nas v ˇcasu analize najbolj optimalna. Ta druga generirana po- razdelitev z istim parametrom ima lahko zaradi uporabe nakljuˇcnih ˇstevil v izraˇcunih medprihodnih ˇcasov drugaˇcne medprihodne ˇcase. Poslediˇcno ima porazdelitev lahko tudi drugaˇcno ˇsirino razreda histograma kot prvotna porazdelitev. Na primer, pri eks- perimentu v domaˇcem omreˇzju smo kot optimalno eksponentno porazdelitev vzeli tisto s parametromt= 9.32 in razliko med ˇsirinami razreda v rangu 0.001 sekunde. ˇCe z istim parametrom zopet poizkusimo nekajkrat generirati eksponentno porazdelitev, vidimo, da se razlika v ˇsirini razreda histograma z eksperimentalno pridobljeno porazdelitvijo spre- minja, kjer je razlika lahko velika tudi do 1 sekunde. Z istim parametrom lahko torej generiramo porazdelitve z razliˇcnimi ˇsirinami razredov histograma. Razlika v Jensen- Shannonovi divergenci je minimalna in je zaokroˇzena vrednost vsakiˇc 0.809. Vrednost parametra, ki nam vrne najbolj optimalno porazdelitev se torej nahaja v nekem inter- valu. Velikost intervala pa je v naˇsem primeru odvisna od doloˇcitve velikosti razlike v ˇsirini razreda eksperimentalno pridobljene porazdelitve in umetno generirane poraz- delitve. Prevelika razlika v ˇsirini razreda namreˇc pomeni, da si porazdelitvi nista zelo podobni in poslediˇcno je tudi Jensen-Shannonova divergenca zato veˇcja. Kriterija diver- gence in razlike med ˇsirinami razredov sta torej do neke mere sorazmerna, kajti umetno generirana porazdelitev z veˇcjo razliko v ˇsirini razreda v primerjavi z eksperimentalno pridobljeno porazdelitvijo ji bo manj podobna in zato bo vrednost divergence veˇcja. Pri
26 4 Analiza rezultatov
tistem trenutku imela najbolj optimalne parametre z najmanjˇso razliko v ˇsirini razreda med umetno generirano porazdelitvijo in eksperimentalno pridobljeno porazdelitvijo. Za doloˇcanje pribliˇznega intervala kot reˇsitve, pa bi bilo potrebno doloˇciti dovoljena odsto- panja v vrednostih Jensen-Shannonove divergence in v vrednostih razlik med ˇsirinami razredov eksperimentalno pridobljene porazdelitve in umetno generiranih porazdelitev.
5 Zakljuˇcek
Porazdelitve porajanja omreˇznega prometa so predmet raziskav ˇze od 20. stoletja. A.
K. Erlang je postavil matematiˇcno teorijo porajanja prometa v telefonskih omreˇzjih. V praksi so lahko z znanjem o porajanju prometa telefonski centri optimizirali ˇstevilo ope- raterjev, ki so jih potrebovali za normalno delovanje omreˇzja. V sodobnih raˇcunalniˇskih omreˇzjih z raznolikim prometom za doloˇcanje porazdelitve prometa spremljamo medpri- hodne ˇcase posameznih prispelih paketov. Z doloˇcanjem zakonitosti porazdelitve sodob- nega omreˇznega prometa, bi lahko upravljalci omreˇzij to znanje uporabili za izboljˇsanje kakovosti storitev, doloˇcanje ozkih grl v omreˇzju in tudi za pomoˇc pri forenziki nezahte- vanega in nepriˇcakovanega prispelega prometa [9,15,17].
Dosedanje preiskovanje internetnega prometa nam je pokazalo, da za paketni promet veljajo izbruhi paketov in prihajanje v skupinah. Upoˇstevajoˇc ta dejstva se zdi, da po- razdelitev takega prometa najbolj opiˇse dolgorepa ali Paretova porazdelitev in ne ekspo- nentna porazdelitev.V priˇcujoˇcem diplomskem delu smo si zastavili nalogo za doloˇcitev porazdelitve omreˇznega prometa za primer pretoˇcnih videovsebin. Skuˇsali smo potrditi, da se omreˇzni promet, ki nosi podatke video vsebine, porazdeljuje po Paretovi porazdeli-
28 5 Zakljuˇcek
tvi, kot nakazujejo rezultati nekaterih ˇze opravljenih raziskav, kjer so obravnavali promet TELNET in FTP sej [14].
Za potrebo preverjanja hipoteze smo postavili dva tipa eksperimenta. V vsakem tipu eksperimenta smo imeli oddajni video streˇznik, do katerega smo dostopali z raˇcunalnikom.
Na raˇcunalniku smo predvajali video vsebino in hkrati zajemali omreˇzni promet, ki pri- haja v raˇcunalnik. Razlika med tipoma eksperimenta je v lokaciji oddajne naprave. V prvem tipu eksperimenta je bila oddajna naprava postavljena v domaˇcem omreˇzju, v drugem tipu eksperimenta pa pri ponudniku oblaˇcnih storitev v Zdruˇzenih drˇzavah ame- rike. Zajeti promet smo analizirali s pomoˇcjo skript, ki smo jih napisali v programskem jeziku Python. Analiza je potekala tako, da smo generirali umetno Paretovo porazdelitev in umetno eksponentno porazdelitev, ki je najbolj podobna eksperimentalno pridobljeni porazdelitvi. Nato smo vsako umetno generirano porazdelitev primerjali z eksperimen- talno pridobljeno porazdelitvijo s pomoˇcjo Jensen-Shannonove divergence. V obeh tipih eksperimentov smo ugotovili, da je eksperimentalno pridobljena porazdelitev bolj po- dobna Paretovi porazdelitvi.
V prihodnje se bi lahko lotili izvajanja obeh tipov eksperimentov v veˇcjem obsegu.
V obeh tipih bi lahko promet zajemali ves ˇcas skozi celoten teden. Poleg doloˇcanja po- razdelitve tako obseˇznega prometa, bi se lahko posvetili tudi anomalijam, ki se pojavijo v medprihodnih ˇcasih. Za vsako anomalijo bi lahko pregledali dejanske pakete in posku- sili doloˇciti razlog za nastanek takega medprihodnega ˇcasa. Poleg omreˇznega prometa bi lahko spremljali zasedenost doloˇcenih resursov tako raˇcunalnika kot tudi streˇznika, stikala in usmerjevalnika. Tako bi si lahko pri ugotavljanju razloga za anomalije tudi dodatno pomagali. Moˇzna izboljˇsava bi bila tudi doloˇcanje dodatnih ali boljˇsih kriterijev za iskanje optimalne umetno generirane porazdelitve. Tako bi lahko ˇse z veˇcjo gotovo- stjo potrdili primernost Paretove porazdelitve. Po vzoru iz vira [17] bi lahko postavili eksperiment s streˇznikom, ki je dostopen preko javnega IP naslova in ki je del veˇcjega omreˇzja. Streˇznik bi deloval kot tako imenovan ’lonec medu’ (angl. honeypot). Ker je v internetu prisotnega veliko prometa, katerega naslovnik ni zahteval, bi naˇs streˇznik po nekem ˇcasu imel zajetega veliko prometa med katerim bi bil tudi zlonameren promet, ki izvira iz raznih ˇcrvov in botnetov. Medprihodne ˇcase prometa bi lahko analizirali in iz njih izluˇsˇcili anomalije.
Literatura
[1] The Apache HTTP Server Project, Dosegljivo: https://httpd.apache.org, [Do- stopano: 5. 8. 2021] (2021).
[2] IP2Location, Dosegljivo: https://www.ip2location.com/, [Dostopano: 1. 8. 2021]
(2021).
[3] Google Maps, Dosegljivo: https://www.google.com/maps/, [Dostopano: 6. 8.
2021] (2021).
[4] Raspberry Pi - Wikipedija, prosta enciklopedija, Dosegljivo: https://sl.
wikipedia.org/wiki/Raspberry_Pi, [Dostopano: 27. 7. 2021] (2021).
[5] GoogieHost, Dosegljivo: https://googiehost.com/, [Dostopano: 27. 7. 2021]
(2021).
[6] Wireshark, Dosegljivo: https://www.wireshark.org/, [Dostopano: 25. 7. 2021]
(2021).
[7] B. Benjamin, H. Alakiri, O. Florence, O. C, O. Folasade, The Desirability of Pareto Distribution for Modeling Modern Internet Traffic Characteristics, International Jo- urnal of Novel Research in Engineering and Applied Sciences 1.
[8] A. K. Erlang, The theory of probabilities and telephone conversations, Nyt Tidsskrift for Matematik 20 (1909) 33–39.
[9] S. Femmam, Building Wireless Sensor Networks, ISTE Press - Elsevier, Amester- dam, 2018.
[10] S. Kullback, R. A. Leibler, On Information and Sufficiency, The Annals of Mathe- matical Statistics 22 (1) (1951) 79 – 86.
30 LITERATURA
[11] M. Mraz, M. Moˇskon, Modeliranje raˇcunalniˇskih omreˇzij, Ljubljana, 2020.
url: https://ucilnica.fri.uni-lj.si/pluginfile.php/11776/mod label/intro/3 poglavje.pdf [12] S. R. R. Jain, Packet Trains–Measurements and a New Model for Computer Network
Traffic, IEEE Journal on Selected Areas in Communications 4 (6) (1986) 986–995.
[13] J. W. Roberts, Traffic theory and the Internet, IEEE Communications Magazine 39 (1) (2001) 94–99.
[14] S. F. V. Paxson, Wide area traffic: The failure of Poisson modeling, IEEE/ACM Transactions on Networking 3 (3) (1995) 226–244.
[15] P. Varga, Analyzing Packet Interarrival Times Distribution to Detect Network Bot- tlenecks, in: EUNICE 2005: Networks and Applications Towards a Ubiquitously Connected World, 2006, pp. 17–29.
[16] E. G. Z. Wajahat, Yele, Distribution Fitting and Performance Modeling for Storage Traces, IEEE (2019) 138–151.
[17] J. Zimmermann, A. Clark, G. Mohay, F. Pouget, M. Dacier, The use of packet inter- arrival times for investigating unsolicited Internet traffic, in: First International Workshop on Systematic Approaches to Digital Forensic Engineering (SADFE’05), 2005, pp. 89–104.
[18] L. ˇSkufca, Analiza bremena in zmogljivosti vzorˇcnega e-zdravstvenega sistema, MSc thesis, University of Ljubljana Faculty of Computer and Information Science, Veˇcna pot 113, 1000 Ljubljana (2020).
