A lightweight decentralized service placement policy for performance optimization in fog computing

1 Introduction

• IoT and cloud integration can increase service latency, a critical requirement for some e-health and gaming applications.Fog computing emerged to address these limitations while introducing other resource-management challenges.Source: §1 · p. 2
• Fog service orchestrators allocate services among fog devices to improve QoS and fog-layer usage while addressing scalability and dynamicity.They can create additional fog instances of services already available in the cloud.Source: §1 · p. 2
• Centralized Fog Service Placement Problem solutions face scalability, network-overhead, reliability, decision-latency, and heterogeneity drawbacks.The paper notes that IoT environments may contain thousands or millions of devices, clients, or services.Source: §1 · p. 2
• The decentralized policy places the most popular services as close to clients as possible, using hop distance to measure proximity.Each device makes local optimization decisions using its own resource and usage data.Source: §1 · pp. 2–3
• The paper frames two questions: whether decentralized local optimization can place popular services at smaller hop distances, and whether it improves latency or network usage.Source: §1 · p. 3
• The work contributes a brief survey of Fog Service Placement Problem research, a decentralized low-overhead proposal, and experimental validation using a microservice-based application.Source: §1 · p. 3

2 Related Work

• The survey covers service-management algorithms including heuristics, greedy methods, linear programming, and genetic algorithms across several IoT settings.The described management targets include placement, scheduling, allocation, provisioning, and mapping.Source: §2 · p. 3
• Table 1 organizes prior studies by IoT scope, objective functions, decision variables, broker centralization, algorithm, and validation technique or tool.Source: §2 · p. 3, Table 1 · p. 4
• Linear-programming examples address cost through resource and task decisions, while Velasquez et al. (2017) target service migrations and network latency.The survey also notes medical cyber-physical systems and fog computing in Gu et al. (2017).Source: §2 · p. 3

C MILP O

• Arkian 2017 is listed with scope C.Source: C MILP O · p. 4
• The listed objective for Arkian 2017 is cost.Source: C MILP O · p. 4
• The listed decision variables are client association, resource provisioning, task distribution, and VM placement.Source: C MILP O · p. 4

C ILP O

• Gu 2017 is listed with scope H and cost as its objective.Source: C ILP O · p. 4
• The listed decision variables for Gu 2017 include base-station association, task distribution, and VM placement.Source: C ILP O · p. 4
• Adjacent table entries list service placement, network latency and service migrations, and service merging and placement.Source: C ILP O · p. 4
• Huang 2014a and 2014b are associated with communication power consumption.Source: C ILP O · p. 4

C ILP, MWIS

• Integer and quadratic programming, MWIS, and mixed-cost flow formulations address power use, service latency, QoS, and task completion or placement objectives.Souza et al. model latency minimization with capacity requirements; Huang et al. address power consumption through co-location or MWIS.Source: D MILP O · p. 5

D MILP O

• Genetic-algorithm studies target response time, hierarchical placement across fog colonies, and adaptation to predicted future request distributions.Yang et al. compare greedy, linear-programming, and GA approaches.Source: D MILP O · p. 5
• Other approaches use Petri nets, MDPs, FogTorch, consensus, or predicted costs for task costs, operational costs, QoS-aware deployment, resource sharing, or provider costs.The reviewed work also includes decentralized video resource allocation and binary linear task allocation with heuristic and greedy cost reduction.Source: D MILP O · pp. 5–6
• Placement and allocation studies also address network and power efficiency, response time, delay, mobility-driven migration, and resource use through varied assignment and optimization methods.The review includes graph-based application models, convex optimization, ILP, Hungarian methods, and a three-phase benchmarking, evaluation, and testing methodology.Source: D MILP O · pp. 6–7
• Centralized approaches face scalability and computational-complexity concerns, while Edgewards is decentralized but uses general placement information; decentralized orchestration remains an open challenge.The proposed orchestrator aims to minimize hop count for the most requested services.Source: D MILP O · p. 7

3 Architecture Proposal

• The fog network comprises cloud, fog, and client layers, and the proposal targets placement for applications built from interoperating, stateless microservices.At least one instance of every service is assumed to run at the cloud provider.Source: §3 · pp. 7–8
• When resources are insufficient near clients, services are migrated along the shortest path toward the cloud, avoiding detours that increase the communication path.In the example, placing S2 off the shortest path adds one communication step compared with placing it in the next device on that path.Source: §3 · p. 8
• The placement priority rule keeps the most requested services closest to clients and moves less requested services upward when nearby devices lack free resources.Source: §3 · p. 8
• When a service moves upward, its interoperated services are also migrated to avoid device loops; moving S2 alone can add two communication steps to application makespan.Migrating S3 with S2 in the example keeps the application makespan unchanged.Source: §3 · p. 9
• Each device runs a broker whose local SPRM decides placement or migration, supported by monitors and a migration component, without exchanging performance data between devices.The broker receives service requests recursively as they shift upward; the decision uses locally monitored service rates and resource data.Source: §3 · p. 10

4.1 System Model

• Applications are directed graphs of interoperating services, and service instances may be allocated across multiple devices.Clients connect to leaf devices, while fog devices form a graph of network links and can host service modules.Source: §4.1 · pp. 11–12
• The model characterizes devices and services by resource capacity and consumption, but this study considers CPU alone and treats cloud capacity as unlimited.Device usage is calculated from allocated services’ resource consumption and request rates.Source: §4.1 · p. 12

4.2 Optimization Model

• When a device cannot accommodate a requested service, the policy considers migrating lower-request-rate service subsets toward an upper device on the path to the cloud.It migrates interoperated services together and selects candidate subsets in ascending request-rate order, deallocating them only when enough capacity is freed.Source: §4.2 · pp. 13–14
• A service is allocated when the device has sufficient free and total capacity; otherwise, its allocation request is passed to the upper father device.The policy considers a service allocation request only when that service is not already allocated on the device.Source: §4.2 · pp. 13–14
• Migration candidates are subsets formed from services allocated on the device and the transitive closure of a service, which comprises services needed when it is requested.For example, the candidate subsets can include an entire interoperated group or smaller subsets within it.Source: §4.1 · p. 11, §4.2 · p. 14
• The policy minimizes popularity-weighted hop distance, using service request rate as popularity and hop count as proximity to clients.Hop count is the number of fog devices a client request traverses to reach a service; the weighted average gives greater weight to services with higher request rates.Source: §4.2 · pp. 13–15

5 Evaluation

• The proposed policy is compared with iFogSim’s built-in Edgewards placement policy in simulations of a microservice-based application.The simulator’s ModulePlacement class was extended to implement the proposed policy.Source: §5 · p. 15
• Experiments vary the number of clients, applications, and fog devices, using tree topologies that vary in levels and children per device.Although the model permits graph topologies, iFogSim supports tree architectures in these experiments.Source: §5 · p. 15
• Fog-device placement is limited by CPU capacity, while memory and bandwidth are set high enough not to constrain service allocation.Cloud resources are set high enough to behave as unlimited.Source: §5 · p. 15
• The simulated application is Weaveworks and Container Solutions’ Socks Shop demo, replicated with different request rates across application instances.Its characterization and modeling parameters were obtained from previous research; Figure 6 depicts its application graph and service settings.Source: §5 · pp. 16–17, Figure 6 · p. 17

6 Results

• Results are reported as average hop count (Equation 6), network usage, and service latency; Equations 7 and 8 for the latter metrics came from iFogSim simulator2 source-code analysis.Network usage sums the usage generated by requests sent during the total simulation time. Service latency is the average time to execute an application edge loop, measured from the first service request’s arrival until the last service ends execution.Source: §6 · pp. 17–18
• Figures 7–10 cover variations in users per gateway, application count, fog-network levels, and children per device.Figure 9 reports latency for a representative edge–frontend–orders–accounts loop, including loops for the highest- and lowest-request-rate applications.Source: §6 · pp. 18–19, Figure 8 · p. 19, Figure 9 · p. 20
• Figure 7 compares weighted and arithmetic mean hop count, with the weighted measure indicating proximity for the most-requested services.The arithmetic mean indicates proximity across all services regardless of request ratios.Source: §6 · p. 18, Figure 7 · p. 19
• Figure 10 counts migrations, each defined for stateless services as removing an instance and downloading a new one from the cloud to its new device.Figures 11 and 12 describe device CPU usage and allocated service counts by hop distance; Figure 13 plots service placement distance against request rate.Source: §6 · pp. 19, 21, Figure 11 · p. 21, Figure 12 · p. 22

• The weighted average hop count is 12% lower overall than with Edgewards, while Edgewards has a lower arithmetic average hop count, indicating greater overall distance under our policy.The weighted measure reflects proximity for the most-requested services; the arithmetic measure covers all services regardless of request ratio.Source: §7 · p. 22
• The weighted-hop improvement for popular services comes with greater overall service distance; one-user cases place all services at gateways with a hop count of 1.0.Source: §7 · p. 22
• 23%–362% speedup in network usage, with a mean of 114%, compared with Edgewards.Source: §7 · p. 22
• Around 300% and 500% speedup is reported for the highest-request application, reaching 1300% in the second-last case of the user-count variations.The Pop (highest) series has the smallest values in Figure 9.Source: §7 · p. 23
• Latency improves for the highest-request application but can worsen for the lowest-request application in high-workload experiments, where Edgewards shows 60%–250% improvements.Our policy can perform better for low-request services when workload is low; degradation occurs mainly as the number of applications increases.Source: §7 · p. 23
• Our solution requires more service migrations or cloud deployments, increasing network usage during deployment; benefits offset this cost except with high application-deployment rates.Source: §7 · pp. 23–24
• Changing levels or children did not alter latency or hop count because services remained at the lowest levels; network usage changed with the number of connections.Source: §7 · p. 24
• In the 2-application, 2-user, 2-level experiment, hop-1 devices hold higher-rate services under our policy than Edgewards, while hop-2 devices hold lower-rate services.The policy also places less-requested services at hop distance 2 and most-requested services at 1, with lower usage in lower topology levels.Source: Figure 13 · p. 23, §7 · p. 24

• The algorithm runs locally on each fog device using only that device’s performance and usage data, and migrates lower-request services to upper devices as placements are needed.Source: §8 · p. 24
• Migration of a service also includes migration of all its consumed services, accounting for interoperability among services.Source: §8 · p. 25
• In iFogSim microservice-application experiments, the policy improved weighted average hop count, network usage, and latency for the most-requested services versus Edgewards, while increasing latency for less-requested services.Source: §8 · p. 25
• The results support decentralized placement optimization as a way to improve fog-system performance; the authors identify further work on decentralized managers to avoid centralized scaling problems.Source: §8 · p. 25