20.500.12556/RUL-100557 Analiza problema k-strežnikov Analysis of the k-server problem Problem k-strežnikov je optimizacijski problem, preproste in intuitivne narave. V tem problemu mora algoritem nadzorovati premike množice k strežnikov, ki so predstavljeni kot točke metričnega prostora in strežbo zahtev, ki so tudi v obliki točk prostora. Ob vsaki novi zahtevi mora algoritem izbrati ustrezni strežnik in ga premakniti na mesto zahteve. Glavni cilj algoritma je torej minimizirati skupno prepotovano razdaljo s strani strežnikov ob obdelavi zahtev. Zahteve se pojavljajo ena za drugo, zato je algoritmu vidna le trenutna zahteva, ki jo mora v tistem koraku obdelati. Z njim se srečamo vsakič, ko moramo obdelovati zahteve v prostoru. Na primer pri podjetjih za dovažanje, policijskih upravah in v računalništvu pri omrežjih za posredovanje vsebin. Cilj diplomskega dela je preizkusiti učinkovitost najpopularnejših rešitev problema in jih primerjati. Pri tem smo uporabljali metode ocenjevanja, ki jih uporabljajo raziskovalci na tem področju in vsak algoritem tudi implementirali in testirali v programskem jeziku Java. V delu smo pri testiranju uporabljali realne podatke, česar ni bilo mogoče zaslediti pri ostalih podobnih študijah problema. Na koncu smo dobili zanimivo sliko slabosti in vrlin posameznih rešitev problema. The k-server problem is an optimization problem of a relatively simple and intuitive nature. In this problem the algorithm must control the movements of a set of k servers, represented as points of a metric space, to service a set of requests, also represented by points of a metric space. As a new request arrives the algorithm must choose an appropriate server and move it to the requests location for servicing. The main goal of the algorithm is to minimize the total distance travelled by all the servers. Requests appear in a sequential manner so the algorithm only sees the current request at any one time. In practice it appears many times in the fields of servicing different kinds of requests. For example it is a common problem of delivery companies, police precincts and in the field of computer science by content delivery networks. The main goal of the thesis was to test the efficiency of the most popular solutions to the problem and make a comparison between these. To achieve this goal we made use of evaluation methods practiced by seasoned researches on this topic. We also implemented and tested each algorithm in the Java programming language. Noteworthy was also our usage of real data in contrast to similar studies which only utilized randomly generated data for testing. In the end we manage to get an interesting picture of the strong and weak points of the most popular solutions to the problem. optimizacija k-strežnikov algoritmi metrični prostor Java testiranje zahteve optimization k-servers algorithms metric space Java testing requests true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2018-03-27 15:05:04 2018-03-27 15:05:08 2022-08-14 03:40:59 0000-00-00 00:00:00 2018 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 20517 Maraz_Danijel_-_Analiza_problema_k-streznikov.pdf Maraz_Danijel_-_Analiza_problema_k-streznikov.pdf 1 93D42B8E5E84FA9E4AF272BC43910E2B 9139c69fcfbb5680b5e59809a667934644855215272f65b734e6b32178266648 be4a362a-a1b4-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=110333 Fakulteta za računalništvo in informatiko 0 0 0