M.Sc Thesis | |

M.Sc Student | Shalom Israel |
---|---|

Subject | Online Load-Distance Balancing |

Department | Department of Computer Science |

Supervisor | PROF. Joseph Naor |

Full Thesis text |

This work concerns online algorithms,
which receive their input sequentially. Decisions made by the online algorithm
regarding previous requests are *irrevocable*. The *competitive*
ratio of an online algorithm is the worst-case ratio between the cost of its
output and the cost of the optimum output for the same input.

Particularly, we consider online *assignment*
problems. These concern the assignment of requests to servers, and are relevant
to many practical problems; such as sharing computing resources. In the online
case, requests arrive one-by-one, and the online algorithm returns the handling
server.

Our cost model, Load-Distance Balancing (LDB), is made of two components: one is the distance cost, and the other is the latency cost. The first depends on the distance that is defined between any request/server pair, and the second depends on the latency function of the server as well as the load (number of served requests) on the server.

First, we show that with no further assumptions about latency functions, no online algorithm can guarantee any competitive ratio. We proceed to examining subclasses of latency functions: linear, concave, bounded-slope, polynomial and capacity functions. The last class is particularly useful, since it represents the bipartite matching problem with capacities. In the bipartite matching problem, there are no latencies - the goal is to minimize the total moving cost without exceeding server capacity.

For the first four classes we suggest
the *greedy* algorithm, which makes the locally optimal choice in every
step. We find that Greedy (or its
variation) is optimal up to a constant in all these subcases. Despite being
intuitive, the implementation of Greedy
proves difficult, since Greedy has
an infinite number of choices to choose from. We solve this problem by creating
WaterFill, which acts greedily and
works efficiently.

For capacity latencies the analysis
is entirely different. We see that the only subcase in which online algorithms
can perform well are metric distances, and splittable demands. For this case,
we suggest LocalMatch, based on
bipartite matching algorithms, and find that it is O(log^{2}k)-competitive.
We show a lower bound of Ω(log k) for the competitive ratio of *any*
online algorithm, where k is the number of servers.