Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Distributed Dominant Resource Fairness using Gradient Overlay
KTH, School of Computer Science and Communication (CSC).
2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Resource management is an important component in many distributed clusters. A resource manager handles which server a task should run on and which user’s task that should be allocated. If a system has multiple users with similar demands, all users should have an equal share of the cluster, making the system fair. This is typically done today using a centralized server which has full knowledge of all servers in the cluster and the different users. Having a centralized server brings problems such as single point of failure, and vertical scaling on the resource manager.

This thesis focuses on fairness for users during task allocation with a decentralized resource manager. A solution called, Parallel Distributed Gradient-based Dominant Resource Fairness, is proposed. It allows servers to handle a subset of users and to allocate tasks in parallel, while maintaining fairness results close to a centralized server. The solution utilizes a gradient network topology overlay to sort the servers based on their users’ current usage and allows a server to know if it has the user with the currently lowest resource usage.

The solution is compared to pre-existing solutions, based on fairness and allocation time. The results show that the solution is more fair than the pre-existing solutions based on the gini-coefficient. The results also show that the allocation time scales based on the number of users in the cluster because it allows more parallel allocations by the servers. It does not scale as well though as existing distributed solutions. With 40 users and over 100 servers the solution has an equal time to a centralized solution and outperforms a centralized solution with more users.

Abstract [sv]

Resurshantering är en viktig komponent i många distribuerade kluster. En resurshanterare bestämmer vilken server som skall exekvera en uppgift, och vilken användares uppgift som skall allokeras. Om ett system har flera användare med liknande krav, bör resurserna tilldelas jämnlikt mellan användarna. Idag implementeras resurshanterare oftast som en centraliserad server som har information om alla servrar i klustret och de olika användarna. En centraliserad server skapar dock problem som driftstopp vid avbrott på ett enda ställe, även enbart vertikal skalning för resurshanteraren.

Denna uppsats fokuserar på jämnlikhet för användare med en decentraliserad resurshanterare. En lösning föreslås, Parallel Distributed Gradient-based Dominant Resource Fairness, som tillåter servrar att hantera en delmängd av användare i systemet, detta med en liknande jämnlikhet jämförande med en centraliserad server. Lösningen använder en så kallad gradient network topology overlay för att sortera servrarna baserat på deras användares resursanvändning och tillåter en server att veta om den har användaren med lägst resursanvändning i klustret.

Lösningen jämförs med existerande lösningar baserat på jämnlikhet och allokeringstid. Resultaten visar att lösningen ger en mer jämnlik allokering än existerande lösningar utifrån gini-koefficienten. Resultaten visar även att systemets skallbarhet angående allokeringstid är beroende på antalet användare i klustret eftersom det tillåter fler parallella allokeringar. Lösningen skalar inte lika bra dock som existerande distribuerade lösningar. Med 40 användare och över 100 servrar har lösningen liknande tid som en centraliserad server, och är snabbare med fler användare.

Place, publisher, year, edition, pages
2017.
Keywords [en]
Distributed, DRF, Dominant, Resource, Fairness, Gradient, Overlay
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-215275OAI: oai:DiVA.org:kth-215275DiVA, id: diva2:1147453
External cooperation
SICS
Subject / course
Computer Science
Educational program
Master of Science - Computer Science; Master of Science in Engineering - Information and Communication Technology
Supervisors
Examiners
Available from: 2017-10-19 Created: 2017-10-05 Last updated: 2017-10-19Bibliographically approved

Open Access in DiVA

fulltext(723 kB)53 downloads
File information
File name FULLTEXT01.pdfFile size 723 kBChecksum SHA-512
5e37864a643654622e500c2f61013a0e642eb793c18d2955db2967ebaf85e9570a2d3cc2bd1587789383b0bc2be310d1e68690e1de20b38ff52dbbd9dea6d49c
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 53 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 143 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf