Distributed Service Placement in Fog Computing: An Iterative Combinatorial Auction Approach

A primary concern in fog computing is how to efficiently allocate limited fog resources to applications with diverse resource requirements. In fog computing, applications that consist of a set of interdependent microservices are mapped to computing and communication devices, referred to as fog nodes. While placement of microservices can be done centrally, the essentially decentralized infrastructure of participating end-user devices motivates the search for distributed solutions. In this paper, we present a distributed placement strategy that seeks to optimize energy consumption and communication costs. We devise a game-theoretic approximation method that is inspired by an iterative combinatorial auction. By properly restricting the types of bids that can be made in an auction, we can avoid the need for a centralized auctioneer. We devise a fully distributed service placement algorithm without central coordination or global state information. The algorithm operates in rounds, where the number of rounds is bounded by the number of applications and the total number of microservices. Numerical examples show that our placement algorithm outperforms existing heuristics in terms of efficiency and network utilization while achieving comparable utilization and load balancing.

I. Introduction

With the Internet-of-Things (IoT) proliferating, IoT devices are expected to generate massive amounts of data for immediate processing in a short time. The increased demand of distributed IoT applications for real-time, low-latency services is proving to be challenging for the traditional cloud computing framework. The fog computing paradigm addresses these challenges by locating devices for computing, storage, networking, and acceleration, called fog nodes, closer to users [1]. By adopting a microservice architecture [2], IoT applications are designed as a collection of loosely coupled modular services, called microservices, that communicate with each other over a network. Microser-vices are installed in lightweight and portable run time environments, so-called application containers. They allow fog nodes to take advantage of the shared pool of physical resources by providing a distributed and highly virtualized computing environment. Each fog node is connected to some other fog nodes by wireless or wired links forming a fog network. Fog nodes cooperate by forwarding data exchanged between any pair of fog nodes. Figure 1.

Placement of fog services.