Nash Bargaining Solution Allocation is Not Suitable for Datacenter Jobs

Ilya Nikolaevskiy, Andrey Lukyanenko and Andrei Gurtov
Additional contact information
Ilya Nikolaevskiy: Aalto University, Finland2IDA, Linköping University and ITMO University
Andrey Lukyanenko: Aalto University, Finland2IDA, Linköping University and ITMO University
Andrei Gurtov: Aalto University, Finland2IDA, Linköping University and ITMO University

International Game Theory Review (IGTR), 2017, vol. 19, issue 01, 1-22

Abstract: The Nash Bargaining Solution (NBS) has been broadly suggested as an effective solution for the problem of fair allocation of multiple resources, namely bandwidth allocation in datacenters. In spite of being thoroughly studied, and provably strategy-proof for most scenarios, NBS-based allocation methods lack research on the strategic behavior of tenants in the case of proportionality of resource demands, which is common in datacenter workloads. We found that misbehavior is beneficial: by lying about bandwidth demands tenants can improve their allocations. We show that a sequence of selfish improvements leads to trivial demand vectors for all tenants. It essentially removes sharing incentives which are very important for datacenter networks. In this paper, we analytically prove that tenants can misbehave in 2- and 3- tenants cases. We show that misbehavior is possible in one recently proposed NBS-based allocation system if proportionality of demands is taken into account. Monte Carlo simulations were done for 2–15 tenants to show a misbehavior possibility and its impact on aggregated bandwidth. We propose to use another game-theoretic approach, namely Dominant Resource Fairness (DRF) to allocate bandwidth in the case of proportional demands. We show that this method performs significantly better than NBS after misbehavior.

Keywords: Game theory; Nash Bargaining Solution; Dominant Resource Fairness; resource allocation (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219198917500013
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:igtrxx:v:19:y:2017:i:01:n:s0219198917500013

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219198917500013

Access Statistics for this article

International Game Theory Review (IGTR) is currently edited by David W K Yeung

More articles in International Game Theory Review (IGTR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().