The distributed p-median problem in computer networks

The exponential growth of the Internet over the last decades has led to a significant evolution of the network services and applications. One of the challenges is to provide better services scalability by placing service replica in appropriate network locations. Finding the optimal solution to the facility location problem is particularly complex and is not feasible for large scale systems. Locating facilities in near-optimal locations have been extensively studied in many works and for different application domains. This work investigates one of the most notable problems in facility location, i.e. the p-median problem, which locates p facilities with a minimum overall communication cost. All previous studies on the p-median problem used a centralised approach to find the near-optimal solution. In this case the required information needs to be collected in order to apply a sequential algorithm to find a solution. The centralised approach is infeasible in large-scale networks due to the time and space complexity of the sequential algorithms as well as the large communication cost and latency to aggregate the global information. Therefore, this work investigates the p-median problem in a distributed environment. To the best of the author’s knowledge, this is the first work to study the distributed pmedian problem for large-scale computer networks. Solving the p-median problem in a fully distributed way is a challenging task due to the lack of global knowledge and of a centralised coordinator. Two new approaches for solving the p-median problem in a distributed environment are proposed in this thesis. Both are designed to be executed without any centralised collection of the data in a single node. These methods apply an iterative heuristic approach to improve a random initial solution and to converge to a final solution with a local minimum of the cost. The first approach builds a global view of the system and improves the current solution by replacing a single facility at each iteration. The second approach, is designed according to the well-known k-medoids clustering algorithm. At each iteration a local view of each cluster is generated and all facilities can be updated to optimise the solution. Both approaches were implemented within the Java-based PeerSim network simulator for investigating the performance in large-scale systems and tested against different parameters such as the size of networks, number of facilities to be placed and different initial solutions. The results have shown that the first protocol is better at addressing locations for facilities since it converges to a lower total cost of the solution than the second protocol. However, the second one is faster in optimising the solution