PaperlayerView exact revision on arXiv

Source-linked AI summary

Delay and Throughput Analysis of Computation Offloading in Mobile Edge Computing: A Queueing Network Approach

Amirparsa Bahrami, Farid Ashtiani

arXiv:2609.06021v1cs.NI

TL;DR

Tree-structured tasks in multi-tier MEC make static offloading a delay-optimization problem. The paper models and optimizes that routing, finding accurate delay estimates and better delay and throughput outcomes than the considered baselines.

  • Problem

    Mobile devices and IoT nodes have limited computation, energy, and memory, motivating offloading to reduce end-to-end response time for applications such as AR/VR and real-time inference.

    Source: §I · p. 1

  • Method

    A PFQN approximation with congestion correction models multi-tier MEC execution of tree-structured tasks, supporting recursive delay evaluation and differentiable optimization of static routing probabilities.

    Source: §I · p. 2

  • Results

    The optimized policy achieves the lowest delay within the stable operating region and improves empirical maximum stable throughput by 26.34%–39.46% over the strongest baseline across evaluated traffic scenarios.

    Source: §VII · p. 14, D. Empirical Maximum Stable Throughput · p. 14

  • Takeaways & Limitations

    For the evaluated traffic scenarios, the delay-optimized static policy offers a joint delay and empirical-throughput advantage over the considered baselines.

    Source: §VII · p. 14

Abstract

from arXiv · show

Mobile edge computing (MEC) enables mobile devices to offload computation to nearby edge servers and to the cloud in order to reduce end-to-end delay for applications such as AR/VR, real-time inference, and sensor-driven analytics. In this paper, we study static computation offloading when each task consists of multiple dependent subtasks represented by a rooted directed tree. We develop a product-form queueing-network (PFQN) model with an approximation to capture the computation and communication dynamics of tree-structured task execution in a multi-tier MEC system. Based on this model, we derive closed-form expressions for effective server utilizations and waiting times, and then construct a recursive algorithm for evaluating the average delay of general tree-structured tasks. We formulate the static offloading design problem as the minimization of the rate-weighted average task delay over the routing probabilities, and solve it through a differentiable optimization framework based on softmax parameterization, log-sum-exp smoothing, and a stability barrier on server utilizations. Numerical results show that the proposed PFQN approximation provides accurate delay estimates and that the delay-optimized static policy consistently outperforms the considered baseline algorithms in terms of both average task delay and empirical maximum stable throughput.

I. INTRODUCTION

The introduction motivates offloading as a way to manage end-to-end delay for resource-limited devices, then presents an analytical framework for static routing of tree-structured tasks. The system model represents servers with queueing abstractions and connectivity-constrained forwarding.

I. INTRODUCTION

  • The analysis focuses on rooted directed task trees, which represent branching and multi-stage applications while avoiding some of the complexity of general DAGs.Source: §I · p. 2
  • Dependent subtasks can trigger batches of downstream computation or communication, creating correlated, bursty internal traffic that existing queueing-based MEC models do not explicitly capture.The paper identifies this as the main gap it addresses.Source: §I · p. 2
  • The framework approximates tree-task execution with a PFQN and congestion correction, derives closed-form utilizations and waiting times, and recursively evaluates delay to optimize static routing probabilities.The optimization uses softmax parameterization, log-sum-exp smoothing, and a stability barrier on server utilizations.Source: §I · p. 2
  • The delay-optimized static policy consistently outperforms the considered baselines in average task delay and empirical maximum stable throughput.The approximation is reported accurate over a broad set of stable routing policies.Source: §I · p. 2

A. Computing Nodes

  • Servers may represent mobile users, MEC servers, or cloud servers, and each node can forward tasks only to servers within its connection zone.Source: A. Computing Nodes · pp. 2–3
  • Each server is modeled as a single-server FCFS queue with exponential service times.The abstraction can be extended to more general service-time distributions, at increased analytical and computational complexity.Source: A. Computing Nodes · p. 2

B. Task Model

Tasks are modeled as rooted directed trees whose edges encode precedence and data dependencies. Computation and communication are represented through discrete load and data units, with subtask placement determining where dependency data is sent.

B. Task Model

  • Each task type is a rooted directed tree: vertices are subtasks, and directed edges encode precedence and data dependencies.Source: B. Task Model · p. 3
  • Subtasks are indexed in breadth-first order, level by level from the root toward the leaves.Source: B. Task Model · p. 3, Figure 1 · p. 3
  • A subtask’s computation load is an integer number of independent load units, giving an Erlang total service time at a server.Source: B. Task Model · pp. 3–4
  • Dependency data units transfer from a parent’s server to the server assigned to its child; units on an edge follow that child’s server assignment rather than being routed independently.No transfer is required when parent and child execute at the same server.Source: B. Task Model · p. 4
  • Transmission time for multiple data units is modeled as a sum of independent exponential times, while leaf subtasks carry result data units delivered to the task origin.Source: B. Task Model · p. 4

C. Offloading Model and Task Completion Time

Tasks arrive independently as Poisson processes, and their rooted-tree subtasks may be processed locally, at edge servers, or in the cloud. The model fixes routing probabilities and accounts for communication and computation under distinct edge and cloud assumptions.

C. Offloading Model and Task Completion Time

  • Each task type arrives at each user as a Poisson process, and users and task types are independent.The rate is specified per user and task type.Source: C. Offloading Model and Task… · p. 4
  • Task completion delay runs from the root's start until the last subtask completes.In a rooted tree, the root is the earliest-starting subtask.Source: C. Offloading Model and Task… · p. 4
  • Intra-edge transmission delays are assumed negligible relative to computation, while cloud computation is effectively instantaneous and edge–cloud communication uses a cloud queue.The cloud queue is modeled as FCFS with an exponential service rate.Source: C. Offloading Model and Task… · p. 4
  • When a subtask is offloaded to a cloud server, its descendants remain there, and their required input and result data are aggregated into one cloud-queue workload.The aggregation includes dependency data from the parent or task origin and descendant result data that must return to the edge.Source: C. Offloading Model and Task… · pp. 4–5

D. Static Computation Offloading Policy

  • Static routing assigns fixed probabilities to root and child destinations without conditioning on instantaneous queue states.A child’s routing distribution can depend on the server where its parent completed; dynamic policies instead react to current system state.Source: D. Static Computation Offloading Policy · p. 5

III. QUEUEING-NETWORK MODEL FOR COMPUTATION OFFLOADING

Tree-structured tasks create correlated, back-to-back batches that do not directly satisfy the quasi-reversibility conditions needed for a product-form network. The paper approximates these flows with quasi-reversible M/M/1 queues and recursively computes batch-initiation rates through the task tree.

III. QUEUEING-NETWORK MODEL FOR COMPUTATION OFFLOADING

  • Subtask execution creates correlated batches, so the original system does not directly meet the independent Poisson-flow conditions required for a standard product-form queueing network.A subtask can generate multiple computation units or data units that arrive back-to-back at a queue.Source: §III · pp. 5–6

A. From Single-Queue Approximation to a Network of Queues

  • The approximation replaces each batch with a same-average-rate Poisson stream plus an independent redundant stream that recovers congestion from within-batch correlation.Applying this construction across queues yields a network of quasi-reversible M/M/1 nodes.Source: A. From Single-Queue Approximation to… · p. 6

B. Batch Types Created by Subtask Execution

  • A subtask creates a batch of computation load units at an edge server or aggregated data units at a cloud queue.The model tracks the rates at which these batches are initiated.Source: B. Batch Types Created by Subtask… · p. 6

C. Traffic Equations for Batch Initiations

  • For a non-root subtask, its initiation rate at a destination is the sum of parent-completion rates across edge servers weighted by the static routing probabilities.Because each tree node has one parent, these rates are computed recursively from root to leaves; cloud descendants are included in the aggregated cloud quantity.Source: C. Traffic Equations for Batch… · p. 6

D. Nominal Poisson Traffic at Each Server

The model first converts initiated batches into nominal Poisson traffic, then adds a correction for the extra congestion caused by back-to-back arrivals. It uses the resulting queue parameters to evaluate delay recursively, while recognizing that the approximation is less reliable near saturation.

D. Nominal Poisson Traffic at Each Server

  • Replacing batches with same-mean Poisson traffic alone would underestimate congestion because later units in a batch arrive immediately behind the first.The nominal arrival rate is the average rate of individual computation or data units reaching each server.Source: D. Nominal Poisson Traffic at Each… · p. 7

E. Congestion Correction

  • The congestion correction matches extra within-batch waiting with a triangular contribution of B(B −1)/2 per batch of size B.A redundant Poisson stream is set by matching the mean customer count of the original batched queue and the approximating dual queue.Source: E. Congestion Correction · p. 7

F. Waiting Time and Product-Form Approximation

G. Recursive Evaluation of Traffic and M/M/1 Parameters

  • Traffic rates are propagated from roots to leaves in topological order, after which server loads, corrections, utilizations, and waiting times are computed without a fixed-point iteration.The recursive evaluation is designed to be efficient inside the optimization procedure.Source: G. Recursive Evaluation of Traffic and… · p. 7
  • The approximation matches mean traffic and leading-order batch congestion, but does not preserve the full dependence structure and is expected to be less accurate near saturation.The stated reliability regime is stable low-to-moderate load.Source: G. Recursive Evaluation of Traffic and… · p. 7

IV. AVERAGE TASK DELAY DERIVATION

  • General task delay is evaluated by decomposing a tree into stars and folding their delays from leaves toward the root.The section derives delay parameters for a generic star as the building block.Source: §IV · pp. 7–8, Figure 2 · p. 8

A. Delay of a Star-Shaped Task

The star-delay calculation enumerates child-server assignments and estimates completion from server-wise queueing and processing contributions. A recursive algorithm applies this star calculation from the leaves toward the root of a general task tree.

A. Delay of a Star-Shaped Task

  • For a star, child subtasks are assigned to servers according to the static routing probabilities, and each child's mean processing time depends on its destination.Edge processing uses mean computation time; cloud processing uses the mean transmission time of the aggregated data batch.Source: A. Delay of a Star-Shaped Task · p. 8
  • The star's conditional completion delay is approximated by the maximum server-wise contribution, counting queueing delay once per used server and summing processing times for its children.The queueing delay is included only when at least one child is assigned to that server.Source: A. Delay of a Star-Shaped Task · p. 8

B. Recursive Delay Computation for a General Task

  • For a general tree, the algorithm evaluates children first, collapses each internal subtask's star into a server-dependent delay vector, then averages root delays using batch-initiation rates and adds root waiting time.Leaf subtasks return their mean execution-delay vectors directly.Source: B. Recursive Delay Computation for a… · pp. 8–9

C. Network-Wide Average Delay

The section defines network-wide average delay as an arrival-rate-weighted combination of task-type delays, then formulates static routing optimization using smooth routing and delay surrogates.

C. Network-Wide Average Delay

V. OPTIMIZATION OF THE STATIC OFFLOADING POLICY

  • Root routing depends on the task-generating user, while each non-root subtask’s routing depends on the server where its parent completes.These probabilities specify the static routing policy being optimized.Source: §V · p. 9

B. Softmax Parameterization of Routing Probabilities

  • Softmax mappings replace constrained routing probabilities with logits while keeping each routing vector on its probability simplex.The resulting queueing parameters become differentiable functions of the logits.Source: B. Softmax Parameterization of Routing… · p. 9

C. Smooth Approximation of Star Maxima

  • Log-sum-exp smoothing replaces the pointwise maximum in star-delay expressions to provide a differentiable surrogate.The approximation can be accurate for an appropriate smoothing parameter while keeping gradients numerically stable.Source: C. Smooth Approximation of Star Maxima · p. 10

D. Stability Barrier on Server Utilizations

The optimization adds a utilization barrier to maintain stability and applies gradient descent to the smooth objective; evaluation also measures approximation accuracy, delay, and stable throughput.

D. Stability Barrier on Server Utilizations

  • The logarithmic barrier grows without bound as any server utilization approaches the safety level ρmax, keeping gradient iterations inside the stability region.The example safety level is ρmax = 0.99.Source: D. Stability Barrier on Server… · p. 10

E. Gradient-Based Optimization Algorithm

VI. PERFORMANCE EVALUATION

  • The evaluation assesses queueing-approximation accuracy, optimized-policy delay against baselines, and empirical maximum stable throughput under mixed and single-class traffic.Source: §VI · p. 10

A. System Configuration and Evaluation Methodology

The experiments use a compact four-queue MEC topology and three tree-shaped task types, then compare approximation predictions with simulation across stable routing policies and loads.

A. System Configuration and Evaluation Methodology

  • The N = 4 configuration represents two user devices, a shared edge server, and a remote cloud queue in a limited, non-large-scale setting.Its compact topology supports comparison of analytical and simulated delays across routing policies without large-network topology effects.Source: A. System Configuration and Evaluation… · p. 10
  • The three task types are rooted directed trees representing shallow fork–join, hub-and-spoke, and deeper skewed patterns.Their computation loads, result loads, and inter-subtask data sizes are shown in Fig. 3.Source: A. System Configuration and Evaluation… · p. 10, Figure 3 · p. 11
  • The offered-load sweep spans light, moderate, and near-saturation queueing regimes across servers and total arrival rates.The regime coverage is reflected in simulated utilizations reported for the tested loads.Source: A. System Configuration and Evaluation… · p. 11

B. Accuracy of the Queueing Approximation

  • At Λsum = 0.05/0.10/0.15/0.20, corrected mean relative errors are 2.85%/4.57%/7.06%/8.37%, versus 8.20%/15.99%/26.12%/35.55% uncorrected.The correction improves accuracy systematically; the study concludes that the approximation is accurate over stable random policies in the low-to-moderate-load regime.Source: B. Accuracy of the Queueing… · p. 11
  • Approximation error increases as the system moves closer to saturation.The accuracy study retains 20 stable random routing policies at each tested load level.Source: B. Accuracy of the Queueing… · p. 11

C. Performance of the Optimized Static Policy

The optimized static policy delivers the lowest delay across the tested mixed-traffic load sweep and remains best when each task type is evaluated separately. Its routing shifts work away from vulnerable bottlenecks at high load.

C. Performance of the Optimized Static Policy

  • The PFQN-based policy consistently outperforms all baselines in rate-weighted average task delay over the displayed mixed-traffic load sweep.Its analytical delay curve tracks simulation closely over most of the tested range.Source: C. Performance of the Optimized Static… · p. 12, Figure 4 · p. 13
  • The optimized policy has lower simulated delay than every baseline at all reported arrival rates, with gains over ITAGS rising sharply at Λsum = 1.20.Its advantages over URO and PO grow as their queues approach saturation, and its improvement over EFO increases in the medium-to-heavy-load regime.Source: C. Performance of the Optimized Static… · p. 13, Table V · p. 13
  • The PFQN-based optimized policy remains the best-performing method when only type-1, type-2, or type-3 tasks arrive.This result holds over the tested load range for all three single-class scenarios.Source: C. Performance of the Optimized Static… · p. 13

D. Empirical Maximum Stable Throughput

The PFQN-based policy achieves the highest empirical maximum stable throughput in mixed and single-class traffic scenarios. The conclusion summarizes its analytical approach and identifies extension to DAG task graphs as future work.

D. Empirical Maximum Stable Throughput

VII. CONCLUSION AND FUTURE WORK

  • The framework uses Poissonization and a local congestion correction to model correlated batched internal traffic while yielding closed-form utilizations and waiting times.It also evaluates tree-task delay recursively and optimizes static routing probabilities through a differentiable formulation.Source: §VII · p. 14
  • The authors identify extension from rooted trees to DAGs as future work, requiring revised delay recursion and batch aggregation for shared descendants and multiple parents.They also propose adding dynamic or learning-based offloading decisions to the analytical framework.Source: §VII · p. 14

APPENDIX A DERIVATION OF THE CONGESTION CORRECTION TERM

The appendix derives the congestion correction by matching the mean customer count of an original batched queue to that of an approximating queue. Equal mean response times follow under the stated single-server FCFS and service-rate conditions.

A. Original Batched Queue

  • Each batch in the original queue contributes its full batch size, and later customers in a batch face additional customers ahead of them.The first customer sees the queue in steady state; subsequent customers have progressively longer response times.Source: A. Original Batched Queue · p. 15

B. Approximating Dual Queue

C. Matching the Two Queues

  • Matching mean customer counts also matches mean response times for the two queues because they share the same exponential service rate and FCFS discipline.Applying the derivation separately to each server yields the relations used in the main text.Source: C. Matching the Two Queues · pp. 15–16

Related papers

Loading 2609.06021v1…