Matching Theory Application for Efficient Allocation of Indivisible Testbed Resources

Abstract

In this paper, we examine the problem of the efficient allocation of resources in networking testbeds, which cannot be shared among the experimenters. We highlight the similarities with the housing market where indivisible network resources play the role of houses, while experimenters the role of owners. We adopt the Top-Trading-Cycles (TTC) algorithm for providing Pareto efficient allocations and we compare this approach with the current mechanism of the simple First-Come-First-Served (FCFS) approach used in most networking testbeds. A formulation of the problem is provided where we describe the average utility of the system as a function of the desired testbed resources of the experimenters and the final allocation of the resources to them. In the performance evaluation we observe that TTC outperforms FCFS in all the examined scenarios and achieves almost 95% better average utility in certain cases. © 2020 IEEE.