Nash Bargaining Solution Allocation is Not Suitable for Datacenter Jobs

Research output: Contribution to journalArticleScientificpeer-review

Researchers

Research units

  • St. Petersburg National Research University of Information Technologies, Mechanics and Optics (ITMO)
  • Linköping University

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.

Details

Original languageEnglish
Article number1750001
Number of pages22
JournalInternational Game Theory Review
Volume19
Issue number1
Publication statusPublished - 1 Mar 2017
MoE publication typeA1 Journal article-refereed

    Research areas

  • Dominant Resource Fairness, Game theory, Nash Bargaining Solution, resource allocation

ID: 13633625