Source-linked AI summary
Optimal Edge User Allocation in Edge Computing with Variable Sized Vector Bin Packing
Phu Lai, Qiang He, Mohamed Abdelrazek, Feifei Chen, John Hosking, John Grundy, Yun Yang
TL;DR
The paper addresses edge user allocation under heterogeneous server capacities, multidimensional workloads, and geographic coverage constraints. It models EUA as VSVBP and solves it with prioritized Lexicographic Goal Programming. Across experiments, the approach allocates users comparably to or better than the baselines while using fewer edge servers, although baseline choice and synthetic data limit generalizability.
Problem
EUA requires maximizing allocated end-users and minimizing hired edge servers while satisfying quality-of-service, capacity, workload, and proximity constraints.
Method
The paper models EUA as Variable Sized Vector Bin Packing and applies Lexicographic Goal Programming with user allocation prioritized over server minimization.
Results
Across three experiment sets, the approach significantly outperforms random and greedy baselines, allocating all users in one set and using around 32% of available servers versus up to around 87.04% for baselines.
Takeaways & Limitations
The experiments support the proposed approach as an effective way to serve users while reducing the number of hired edge servers.
Takeaways & Limitations
Validity is limited by comparisons with simple random and greedy baselines and by evaluation on a synthesized generic dataset without real-world EUA data.
Abstract
from arXiv · showhide
In mobile edge computing, edge servers are geographically distributed around base stations placed near end-users to provide highly accessible and efficient computing capacities and services. In the mobile edge computing environment, a service provider can deploy its service on hired edge servers to reduce end-to-end service delays experienced by its end-users allocated to those edge servers. An optimal deployment must maximize the number of allocated end-users and minimize the number of hired edge servers while ensuring the required quality of service for end-users. In this paper, we model the edge user allocation (EUA) problem as a bin packing problem, and introduce a novel, optimal approach to solving the EUA problem based on the Lexicographic Goal Programming technique. We have conducted three series of experiments to evaluate the proposed approach against two representative baseline approaches. Experimental results show that our approach significantly outperforms the other two approaches.
1 Introduction
The paper frames edge user allocation as a largely uninvestigated optimization problem requiring reliable, low-latency service while balancing allocated users and hired edge servers. It models EUA as VSVBP and proposes an optimal Lexicographic Goal Programming approach evaluated against random and greedy baselines.
- Motivation: Edge computing moves computation, storage, and networking closer to end-devices to support lower latency and scalability than centralized cloud computing.The motivation includes latency-sensitive applications such as autonomous traffic systems, health care, and cloud gaming.
- Problem: The EUA objective is to maximize allocated users while minimizing hired edge servers under edge-capacity, workload, coverage, and proximity constraints.Minimizing hired servers matters because pay-as-you-go pricing can increase costs as more servers are used.
- Problem: EUA is modeled as a variable sized vector bin packing problem because edge servers differ in remaining capacities and users require multiple resource dimensions.The edge architecture and dynamic constraints distinguish EUA from centralized-cloud task allocation.
- Contributions: The paper develops an optimal EUA approach using Lexicographic Goal Programming and evaluates it against random and greedy baseline approaches.The objectives are prioritized rather than treated as interchangeable.
- Evaluation: The paper evaluates the proposed approach through extensive experiments and reports that it outperforms the two representative baselines.The paper organizes its presentation around motivation, VSVBP background, the proposed approach, evaluation, related work, and conclusions.
2 Motivating Example
The motivating example uses large-scale mobile gaming to show why processing should move from distant cloud servers to nearby edge servers. User allocation must jointly respect geographic coverage and multidimensional capacity while reducing hired-server cost.
- Application: Large-scale mobile gaming can suffer substantial network delay under centralized cloud processing because players are far from cloud servers.Edge computing is presented as a promising way to place game processing closer to players.
- Constraints: Each edge server covers a geographic area, so users outside that coverage cannot connect to it.For example, user u4 cannot use servers s1 or s4 and must be allocated to s2 or s3.
- Constraints: Edge servers have limited multidimensional capacities covering resources such as CPU cores, memory, VRAM, and bandwidth.Assignments must account for capacity constraints in addition to proximity.
- Illustration: Assigning users u1, u2, and u4 to s2, u3 and u6 to s3, and u5 to s4 eliminates s1 while serving the most users without violating constraints.This allocation satisfies the stated proximity and resource constraints and reduces the number of hired servers.
3 Background
The background develops bin-packing variants relevant to EUA: classical bin packing uses identical scalar-capacity bins, while VSBP allows varied bin sizes and VBP represents multidimensional item and bin capacities. EUA combines the latter two characteristics.
- Classical BP: Classical bin packing packs scalar-sized items into identical bins without exceeding capacity while minimizing the number of bins.Its optimization formulation is NP-hard.
- VSBP: Variable Sized Bin Packing permits a limited collection of bin sizes and minimizes the total size of bins required.This objective differs from classical bin packing’s minimum-bin-count objective.
- VBP: Vector Bin Packing represents each item and bin capacity as d-dimensional vectors and requires summed item resources not to exceed capacity in every dimension.It is also known as multi-capacity bin packing.
- EUA mapping: In EUA, bins represent edge servers with different remaining capacities, while items represent users’ multidimensional computing workloads.The service-provider model assumes all application users generate the same amount of workload, while servers can have different remaining resources.
4 Our Approach
The approach models EUA as VSVBP and solves it with Lexicographic Goal Programming, prioritizing user allocation before server minimization. Feasible assignments must satisfy capacity and proximity constraints, with each user assigned to at most one edge server.
- Model: EUA combines variable server capacities with multidimensional user workloads, so it is modeled as Variable Sized Vector Bin Packing.The two objectives are maximizing allocated users and minimizing hired edge servers.
- Allocation policy: Users that cannot reach an available edge server because of coverage or capacity are connected directly to the provider’s central cloud.Covered users are allocated to an edge server unless all accessible servers have reached maximum capacity.
- Capacity constraint: The model enforces that aggregate workload on each server does not exceed its remaining capacity in any resource dimension.For example, users u5 and u11 form a valid assignment to s4 because their aggregate workload fits its remaining capacity.
- Proximity constraint: The proximity constraint restricts each user to edge servers whose coverage contains the user, including multiple options in overlapping coverage areas.Server s4, for example, can serve only users u5 and u11 in the motivating instance.
- Optimization: Lexicographic Goal Programming ranks maximizing allocated users above minimizing hired servers, while binary variables encode user-server assignments and server hiring.Each user can be assigned to at most one edge server or the provider’s cloud.
5 Experimental Evaluation
The evaluation compares the proposed approach with random and greedy baselines across three experiment sets that vary users, available servers, and remaining capacity. Across these settings, the proposed approach allocates all users while using fewer servers, but requires substantially more computation time and faces baseline-comparison and validity limitations.
- Experimental setup: Experiments used random and greedy user-to-server assignment baselines on Melbourne CBD data, with server and user locations derived from ACMA and APNIC sources.The evaluation varied three parameters: end-user count, available edge servers, and remaining server capacity.
- Experimental setup: Three experiment sets varied one parameter at a time while holding the other two fixed: users, available servers, or remaining server capacity.Each end-user-count setting used 100 randomly selected user distributions to reduce the influence of extreme density patterns.
- Allocation and server usage: 32% of available edge servers were used by the proposed approach from 32 to 512 users, 2.7 times fewer than greedy allocation.In the capacity experiment, proposed server usage fell from 96.4% to 31.6% as combined workload capacity increased from 100% to 300%, while greedy usage remained around 90%.
- Efficiency: 23.1 seconds were required by the proposed approach for 512 users, compared with approximately 1.5 seconds for both greedy and random methods.Computation time increased as any of the three experimental parameters increased, consistent with the EUA problem being NP-hard.
- Allocation and server usage: All users were allocated by the proposed and greedy approaches, whereas random allocation assigned only around 20% of users in the experiments.The random approach sometimes used fewer servers, but this reflected its extremely small number of allocated users.
- Threats to validity: The evaluation may overstate effectiveness because random and greedy were simple baselines, and its synthesized dataset may not generalize across edge-computing application domains.The authors also identify the lack of statistical tests as the biggest threat to conclusion validity, despite averaging results over 100 runs.
6 Related Work
Prior edge-computing research addressed offloading, coverage, latency, energy, and related objectives, but this work targets multi-server EUA with multidimensional capacities and proximity constraints. The authors present it as the first such treatment and distinguish it from centralized-cloud task allocation.
- Cloud resource-management research has extensively studied load balancing, virtual-machine placement, provisioning, and server or task allocation.
- EUA differs from cloud task allocation because edge computing is geographically distributed and includes distinctive constraints and dynamic information.
- Edge-computing studies have addressed offloading, energy consumption, latency, coverage, and task completion, but with objectives differing from EUA.
- The paper claims to be the first to address EUA with multiple edge servers, multi-dimensional computing capacities, proximity constraints, and objectives to maximize allocated users while minimizing hired servers.
7 Conclusion
The paper formulates EUA as an NP-hard variable sized vector bin-packing problem and solves it with Lexicographic Goal Programming. Experiments report more allocated users with substantially fewer servers than the baselines, while future work broadens the modeled conditions.
- The EUA formulation uses variable sized vector bin packing and two objectives: maximize allocated users and minimize hired edge servers.
- The proposed approach significantly outperforms greedy and random baselines, allocating the most end-users with nearly three times fewer servers than greedy as the problem scales.
- Future work will incorporate user mobility, dynamic computation tasks, network latency, service availability, pricing, and security alongside proximity and capacity constraints.