Sprotna strežba s k-strežniki v ravnini

VOLČJAK, DOMEN (author), Hočevar, Tomaž (mentor)

Problem k-strežnikov obravnava dinamično dodeljevanje omejenega števila strežnikov za obdelavo zahtev v realnem času, pri čemer poskuša optimizirati premike strežnikov z namenom zmanjšanja skupne prepotovane razdalje. Ta računalniški izziv raziskuje strategije za učinkovito prilagajanje dinamičnim zahtevam, pri čemer se odločitve sprejemajo brez poznavanja prihodnjih zahtev. Cilj je razviti algoritme, ki dosegajo ravnotežje med odzivnostjo in optimalnostjo, ko so jim predstavljena nepredvidljiva zaporedja zahtev. Uspešnost algoritmov se preučuje s konkurenčnimi razmerji med sprotnimi algoritmi in optimalnim statičnim algoritmom. V okviru diplomskega dela sem implementiral (v pythonu) najbolj znane algoritme za reševanje problema k-strežnikov ter ocenil njihovo uspešnost. Za najuspešnejšega se je izkazal hitri algoritem delovne funkcije.

• Language: Slovenian
• Keywords: sprotni algoritmi, konkurenčna analiza, obdelava zahtev, optimizacija, python, pretoki v grafu, testiranje
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2024
• PID: 20.500.12556/RUL-155936
• COBISS.SI-ID: 189058819
• Publication date in RUL: 24.04.2024

VOLČJAK, DOMEN, 2024, Sprotna strežba s k-strežniki v ravnini [online]. Bachelor’s thesis. [Accessed 5 April 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=155936

Secondary language

• Language: English
• Title: The K-server problem in the plane

Abstract

The k-server problem deals with the dynamic allocation of a limited number of servers to process requests in real-time, aiming to optimize server movements to reduce the overall traveled distance. This computational challenge explores strategies for efficiently adapting to dynamic demands, making decisions without knowledge of future requests. The goal is to develop algorithms that strike a balance between responsiveness and optimality when presented with unpredictable sequences of requests. Algorithm performance is evaluated through competitive ratios between online algorithms and an optimal static algorithm. In this thesis, I implemented (in Python) the most well-known algorithms for solving the k-server problem and assessed their effectiveness. The Fast Work Function algorithm proved to be the most successful.

• Keywords: online algorithms, competitive analysis, request processing, optimization, Python, network flows, testing