Misbehavior in Nash Bargaining Solution Allocation

Thumbnail Image

URL

Journal Title

Journal ISSN

Volume Title

School of Science | B3 Vertaisarvioimaton artikkeli konferenssijulkaisussa

Date

2015

Major/Subject

Mcode

Degree programme

Language

en

Pages

9

Series

Abstract

Nash Bargaining Solution (NBS) has been broadlysuggested as an efficient solution for problem of fair allocation ofmultiple resources, namely bandwidth allocation in datacenters.In spite of being thoroughly studied, and provably strategyprooffor most scenarios, NBS-based allocation methods lack researchon strategic behavior of tenants in case of proportionalityof resource demands, which is common in datacenter workloads.We found that misbehavior is beneficial: by lying aboutbandwidth demands tenants can improve their allocations. Weshow that the sequence of selfish improvements leads to trivialdemand vectors for all tenants. It essentially breaks sharingincentives which are very important for datacenter networks.We analytically prove that tenants can misbehave for 2 and 3tenants cases.We show that misbehavior is possible in one recently proposedNBS-based allocation system if demands proportionality is takeninto account. Monte-Carlo simulations were done for 2 --- 15tenants to show a misbehavior possibility and its impact onaggregated bandwidth.We propose to use another game-theoretic approach to allocatebandwidth in case of proportional demands. That method performssignificantly better on average than NBS after misbehavior.

Description

Keywords

networking, datacenters, bandwidth allocation, Nash bargaining solution, misbehavior, game theory

Other note

Citation

Nikolaevskiy, Ilya. 2015. Misbehavior in Nash Bargaining Solution Allocation.