Auction-Based Task Assignment in Fog Computing Architectures with Publish-Subscribe Messaging Patterns

Abstract

Denne masteroppgaven beskriver et desentralisert system for å delegere forespørsler ved hjelp av auksjoner. Metoden er designet for MQTT protokollen og har fog computing nettverk som tenkt bruksområde. Formålet med metoden er å videreføre forespørsler fra en edge klient til en fog node som er en god kandidat for å utføre den aktuelle tjenesten. Auksjonsmetoden fungerer slik at når en node får en forespørsel som den ikke burde utføre selv så inviterer den sine nabonoder til en auksjon. Naboene byr på forespørselen i henhold til deres evne til å håndtere forespørselen. Ved å videresende ansvaret for forespørselen til de høystbydende naboene så sørger auksjonsmetoden for at de best mulige valgene blir tatt ut ifra den tilgjengelige informasjonen som er innbakt i budene. Den praktiske gjennomførbarheten ved auksjonsmetoden ble vist ved å lage et fungerende demonstrasjonsprogram. Ytelsen til auksjonsmetoden ble testet opp imot en modifisert utgave av Battistoni et al. sitt verk i [1] og en tilfeldig tilnærming til delegering. En mangel ved demonstrasjonsprogrammet er at størrelsen på budene er utregnet med et uttrykk som utelukkende tar i betraktning nodenes evne til å utføre den forespurte tjenesten. Auksjonsmetoden er igjennom eksempler vist til å yte bedre når den også tar hensyn til de forventede budene fra nodene som vil være en del av neste budrunde. Bidraget er gitt ved å fremlegge denne selektive metoden for å delegere meldinger i et MQTT nettverk som inneholder flere brokere ved hjelp avautonomt samarbeid.

This thesis presents a decentralised task assignment method that uses auctioning mechanisms to propagate requests. It is designed to be implemented on top of the MQTT protocol and to be used in a fog computing network. The use-case is to route a request from an edge client to a fog node that is suitable for processing the requested service. The auction-based task assignment method behaves such that a node that is incapable of handling a requested service invites its neighbouring fog nodes to participate in auctions. The neighbours place a bid in the auction that is proportional to their capabilities of providing the service. By propagating the request to the highest bidders, this approach finds the most optimal next step in the propagation based on the information that is contained in the bid. The feasibility of the method was proven by implementing a working demonstration program. The performance of the program was tested against two other methods, a modified version of the system outlined by Battistoni et al. in [1] and a random approach to request propagation. A limitation of the demonstration program is that the sizing of the bids was based on an expression that solely considers the immediate processing capability of the node in question. The method was shown to have better performance for some examples where the capabilities of nodes that would be part of a re-auction were included as a component in the bid. The main contribution of this thesis is this selective method for propagating messages in an MQTT network that contains multiple brokers based on autonomous collaboration.