1
Delay and Throughput Analysis of Computation Offloading in Mobile Edge Computing: A Queueing Network Approach
arXiv:2609.06021v1 [cs.NI] 5 Sep 2026
Amirparsa Bahrami, Farid Ashtiani, Senior Member, IEEE
Abstract—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 closedform 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. Index Terms—Mobile edge computing, computation offloading, product-form queueing networks, static routing, delay optimization, queue stability, maximum stable throughput.
I. I NTRODUCTION
L
Ow latency is essential for many emerging mobile applications, including AR/VR, real-time inference, video analytics, and sensor-driven analytics. In such systems, user experience depends on end-to-end response time rather than only on raw computing power [1], [3]. However, mobile devices and IoT nodes are often limited in computation capability, energy, and memory. This has made computation offloading a crucial design mechanism: instead of processing every task locally, a device may execute part or all of its workload on a nearby edge server or in the cloud [2], [4], [15]. Mobile edge computing (MEC) provides the architectural support for this paradigm by placing computing resources close to users while still allowing access to remote cloud resources when needed [1]–[3]. In a typical MEC system, the offloading decision affects multiple interacting components of delay, including communication delay, queueing delay, and computation delay. These components become strongly coupled when multiple users share the same edge server or cloud access link. Therefore, accurate delay modeling is important for designing effective offloading policies. The authors are with the Department of Electrical Engineering, Sharif University of Technology, Tehran 14588-89694, Iran (e-mail: [email protected]; [email protected])
A large body of prior work has studied computation offloading in MEC from the viewpoints of delay minimization, energy efficiency, resource allocation, robustness, and learning-based adaptation [4], [5], [7], [15]–[19], [23]. In particular, queueing-theoretic analysis has long been used in MEC to capture congestion effects and derive latencyaware offloading rules. Existing queueing-based MEC studies, however, mainly fall into three groups. First, several works use relatively simple queueing models to represent one bottleneck or one stage of the offloading path, and then optimize task assignment or server selection on top of that model. For example, Xue et al. study task allocation in a 5G heterogeneous MEC network using a queueing-theoretic model, while Katayama and Tachibana derive delay expressions for a MEC platform with a dedicated MEC server, a shared MEC server, and a cloud server, where the shared server is modeled as a queueing bottleneck [11], [12]. These works demonstrate that queueing models are useful for latency-aware offloading, but they mainly treat tasks as monolithic jobs and focus on server-level congestion rather than the internal traffic dependencies created by structured applications. Second, another line of work uses queueing models to derive delay-related or QoS-oriented performance measures in multi-tier offloading systems. For example, queue-lengthbased offloading rules have been proposed for delay-sensitive applications in federated cloud-edge-fog systems by explicitly targeting the probability of QoS violation, and Markovian queueing models have been used for end-to-end delay analysis in computation offloading systems [13], [14]. These works are analytically valuable, but the traffic they study is still generated by single-stage tasks or independent requests, rather than by structured task execution in which one completed component may trigger multiple downstream operations. Third, some recent MEC studies adopt richer stochastic or queue-aware models, often together with learning-based control, in order to better capture congestion and dynamic system behavior. Recent works include QoE-oriented deep reinforcement learning for distributed MEC offloading, as well as more recent dependency-aware deep reinforcement learning approaches that explicitly consider task graphs in MEC environments [5], [6]. These approaches improve adaptivity, but they are primarily algorithmic and simulation-driven, and they do not provide an analytical delay model for dependent task graphs. On the other hand, modern MEC applications are rarely monolithic. Instead, they often consist of multiple dependent subtasks, where the output of one subtask is needed before another can start. Task graphs provide a natural representation for such workloads, and several MEC and edge-computing studies have used directed acyclic graph (DAG)-based models
2
to express subtask precedence, placement, and offloading decisions [6], [8], [10], [20]–[22]. In this paper, we focus on the important special case in which the task graph is a rooted directed tree. This structure still captures branching and multi-stage applications, while avoiding some of the combinatorial complexity of general DAGs. The key difficulty is that task dependencies fundamentally change the traffic seen by the servers. Even if external task arrivals are Poisson, the completion of one subtask may immediately trigger a batch of computation load units or data units for its children. Hence, the internal traffic is correlated and bursty rather than independent. Existing queueing-based MEC papers typically model congestion caused by multiple users sharing computing servers or communication bottlenecks, and they use these models to derive delay-aware offloading rules. However, to the best of our knowledge, they do not explicitly capture the additional correlation created when the completion of one subtask initiates a batch of downstream computation or communication operations. This is the main gap addressed in this work. To bridge this gap, we develop an analytical framework for static computation offloading in multi-tier MEC systems with tree-structured task graphs. Our approach models the system through a product-form queueing-network (PFQN) approximation with a congestion-correction step that preserves tractability while capturing the additional delay induced by correlated batched internal traffic. Using the resulting closedform utilizations and waiting times, we derive a recursive delay-evaluation algorithm for general task trees and optimize the routing probabilities of a static offloading policy through a differentiable formulation. Compared with recent learning-based MEC offloading works, our framework provides an interpretable analytical surrogate for delay evaluation and policy optimization. Compared with existing queueing-based MEC studies, it explicitly links dependent subtask execution, the correlated internal traffic created by task progression, and end-to-end task delay under a static routing policy. This makes the framework particularly suitable for fast performance evaluation and static policy design in structured MEC workloads. The main contributions of this work are summarized as follows: • We develop a PFQN-based analytical framework for multi-tier MEC systems with tree-structured task graphs, including a congestion-correction mechanism that captures the delay effect of correlated batched internal traffic and yields closed-form expressions for effective utilizations and waiting times. • We derive a recursive algorithm for evaluating the average delay of general tree-structured tasks and formulate the static offloading problem as the minimization of the rateweighted average task delay over the routing probabilities. • We solve the resulting optimization problem through a differentiable framework based on softmax parameterization, log-sum-exp smoothing, and a stability barrier on server utilizations.
Through numerical experiments, we show that the proposed approximation remains accurate over a broad set of stable routing policies, and that the delay-optimized static policy consistently outperforms the considered baseline algorithms in both average task delay and empirical maximum stable throughput. The rest of the paper is organized as follows. Section II presents the system and task models. Section III develops the PFQN-based queueing approximation and the congestioncorrection step. Section IV derives the average task-delay metric and presents the recursive delay-evaluation algorithm. Section V formulates and solves the static offloading optimization problem. Section VI reports numerical validation and compares the optimized policy with baseline algorithms. Table I summarizes the main notation used throughout the paper. •
II. S YSTEM M ODEL In this section, we describe the communication–computation infrastructure, the task structure, the offloading mechanism, and the definition of task completion delay. A. Computing Nodes We consider a heterogeneous computing system consisting of N servers, indexed by {S1 , S2 , . . . , SN }, which may represent mobile devices, mobile edge computing (MEC) servers, or mobile cloud computing (MCC) servers [1], [2]. We denote by Nuser , Nedge , and Ncloud the numbers of mobile users, edge servers, and cloud servers, respectively, so that N = Nuser + Nedge + Ncloud . We explicitly distinguish between servers located at the edge of the network (mobile devices and MEC servers) and servers hosted in remote data centers, because these two categories have markedly different latency and computational characteristics; this edge–cloud hierarchy is standard in MEC and mobile cloud computing architectures [1], [3]. The edge set contains all mobile users and MEC servers, i.e., E = Sn 1 ≤ n ≤ Nuser + Nedge , (1) while the cloud set contains all MCC servers, i.e., C = Sn N − Ncloud < n ≤ N .
(2)
Each server Sn is modeled as a single-server first come first served (FCFS) queue with exponential service time. The mean service time at Sn is 1/µn , where µn is the (computational or transmission) service rate. This M/M/1-type abstraction is widely used in queueing-theoretic studies of MEC and task offloading [1], [11]. Although the framework can be extended to more general service time distributions at the cost of increased analytical and computational complexity.
3
TABLE I S UMMARY OF M AIN N OTATION Symbol N Nuser , Nedge , Ncloud Zn
Description Symbol Total number of computing and communication servers Sn Numbers of user devices, MEC servers, and cloud E, C servers Connection zone of server Sn µn , µ′n
Tk C(vkm ) lkm d(ki,kj) (n) λk
Task of type k Mk , vkm Set of children of subtask vkm FC(vkm ) Number of computation load units of subtask vkm rkm Dependency-data units transferred from vki to vkj d(out,k1) External arrival rate of type-k tasks generated by user λk Sn
(n ,n)
Rk10 R
Bkm,n Λn (R) αn (R) Wn (R) Pn (a) Tj (a)
Probability of routing the root of a task generated at Sn0 to Sn Collection of all static routing probabilities Batch size generated when subtask vkm is assigned to Sn Nominal arrival rate of individual computation or data units at Sn Rate of the redundant Poisson stream added at Sn Average queueing waiting time at server Sn
(n ,n)
Rki p
Service rate of edge server Sn and transmission rate of cloud queue Sn Number of subtasks in Tk and its mth subtask Child of vkm having the smallest BFS index Number of result-data units produced by subtask vkm Input-data units required to initiate the root subtask Aggregate external arrival rate of type-k tasks
γkm,n (R)
Probability of routing child vki from its parent server Snp to Sn Aggregated data workload when vkm and its descendants are assigned to cloud server Sn Initiation rate of subtask vkm at server Sn
Cn (R)
Batch-correlation congestion-correction term at Sn
ρn (R) (a2 , . . . , aD )
Batch-corrected utilization of server Sn Execution-server scenario for the children of a starshaped task Mean processing or transmission time of child vki at server Sj Recursively evaluated delay of the subtree rooted at vkm when its root is processed at Sn Network-wide rate-weighted average task delay
cloud Dkm,n
(ki)
Probability of scenario a conditioned on completion of xj the parent at Sn (n) Delay contribution of server Sj under scenario a ETkm (R)
TaskET(Tk , R) Average completion delay of task type k
Description Server indexed by n Sets of edge and cloud servers, respectively
Ttot (R)
Servers may offload subtasks to other servers within their connection zone. The connection zone of server Sn is denoted by Zn = Si Si is in the connection zone of Sn , (3) and we always have Sn ∈ Zn for 1 ≤ n ≤ N . This connectivity-constrained offloading model, where each node can only forward tasks to a subset of servers, also appears in recent MEC task-allocation formulations [11]. B. Task Model Each mobile user generates computation tasks that can be decomposed into a set of dependent subtasks. We explicitly model the dependencies among subtasks using a directed rooted tree, as is standard in task-graph based offloading for MEC and mobile cloud systems [8]. There are K task types in the system. A task of type k is denoted by Tk and represented as Tk = V (Tk ), E(Tk ) , where V (Tk ) is the set of vertices (subtasks) and E(Tk ) is the set of directed edges (precedence constraints). We write V (Tk ) = {vk1 , vk2 , . . . , vkMk },
(4)
where Mk is the number of subtasks of type-k tasks. The directed edges encode data dependencies: E(Tk ) = (vki , vkj ) there is an edge from vki to vkj . (5)
vk1
vk2
vk4
vk3
vk5
vk6
Fig. 1. Example of BFS indexing for a task tree.
An edge (vki , vkj ) indicates that part of the output produced by subtask vki is needed as input to subtask vkj , and therefore vkj can start only after vki has completed and its result is available at the server where vkj is executed. Vertices are indexed according to a breadth-first search (BFS) traversal starting from the root of the tree. Specifically, we scan the tree level by level, from the root to the leaves, and assign indices in the order in which the subtasks are visited [9]. For each subtask vkm of task Tk , we denote by C(vkm ) = vki (vkm , vki ) ∈ E(Tk )
(6)
its set of children in the task tree. When needed, we refer to the child in C(vkm ) with the smallest BFS index as the first child and denote it by FC(vkm ). Computation load units. We model the computation associated with each subtask at a finer granularity by introducing the notion of a computation load unit. A load unit is the smallest
4
amount of computation that can be processed by a server. A larger or more complex subtask is modeled as the aggregation of multiple load units, following standard queueing-theoretic modeling of phase-type service times [31]. Specifically, the computation load of subtask vkm is described by a positive integer lkm , meaning that computing vkm consists of processing lkm independent load units. When the subtask is executed at server Sn , each load unit experiences an exponential service time with mean 1/µn . Hence, the total computation time of vkm at Sn is the sum of lkm i.i.d. exponential random variables, i.e., an Erlang distribution [31]. Dependency and result data units. We model communication at a similar level of granularity. A data unit is the smallest indivisible amount of data that can be transmitted over a link. For each edge (vki , vkj ) ∈ E(Tk ), we let d(ki,kj) denote the number of dependency data units that must be transferred from the server executing vki to the server executing vkj so that vkj can start. These dependency data units are formed from (part of) the result produced by subtask vki and contain the information needed to initiate the computation of vkj . We also define d(out,k1) as the number of data units that must be transmitted from the originating mobile user to the server that executes the root subtask vk1 , in order to provide the input data required to initiate vk1 . Each subtask produces a certain amount of result data that must eventually be delivered back to the task origin when the task completes. We denote by rkm the number of result data units associated with subtask vkm . If vkm is not a leaf in the task tree, we set rkm = 0. The time required to transmit a single data unit over a given communication link is modeled as an exponential random variable. This memoryless approximation captures the service time variability introduced by wireless channel fluctuations, packet errors, and possible retransmissions [32]. Hence, the time to transmit d data units over that link is the sum of d independent exponential random variables, i.e., an Erlang distribution, which is consistent with classical queueing models [31]. Illustrative example. Consider a parent subtask vk1 that completes at server S1 and has two children, vk2 and vk3 , with d(k1,k2) = 3 and d(k1,k3) = 2. Suppose that vk2 is assigned to server S2 , while vk3 is assigned to the same server S1 as its parent. In this case, the three dependency data units associated with the edge (vk1 , vk2 ) are transmitted from S1 to S2 , whereas no data transmission is required for the edge (vk1 , vk3 ). Thus, routing decisions are made at the subtask level: all dependency data units associated with an edge follow the server assignment of the corresponding child subtask and are not routed independently. C. Offloading Model and Task Completion Time Task arrivals. Mobile user Sn , 1 ≤ n ≤ Nuser , generates tasks of type k ∈ {1, . . . , K} according to a Poisson process (n) with rate λk . Different users and task types are independent, which is a standard assumption in queueing-based models of MEC and mobile cloud offloading [1], [4].
Execution of subtasks. When a new type-k task is generated at user Sn , its root subtask vk1 can either be processed locally at Sn or offloaded to some server Sj ∈ Zn . Offloading vk1 incurs a transmission delay that depends on the number of input data units d(out,k1) and the communication rate between Sn and Sj . More generally, suppose subtask vkm is executed at server Sn . For each child vki ∈ C(vkm ) there are two options: (i) compute vki at the same server Sn , or (ii) offload vki to some Sj ∈ Zn . If vki is offloaded from Sn to Sj , the dependency data consisting of d(km,ki) units (derived from the result of vkm ) must be transmitted from Sn to Sj , incurring an additional transmission delay. If vki is processed locally at Sn , no dependency transmission delay arises for that edge. We denote by startkm and endkm the time instants at which processing of vkm starts and completes (including both communication and computation for that subtask), respectively. Task completion delay. The completion time of an entire type-k task is defined as the time elapsed between the start of the first subtask and the completion of the last subtask: Dk =
max
1≤m≤Mk
endkm −
min
1≤m≤Mk
startkm .
(7)
Since the task graph is a rooted tree, the earliest-starting subtask is always the root vk1 . Hence Dk =
max
1≤m≤Mk
endkm − startk1 .
(8)
Edge–cloud tradeoffs. At the edge of the network (mobile users and MEC servers), the main bottleneck is the limited computational power, while communication between nearby nodes is relatively fast. Because of this, we assume that, for intra-edge offloading (e.g., between a user and an MEC server or between two MEC servers), the transmission delays of dependency and result data are negligible compared to the computation delays. In other words, for offloading decisions that remain inside E, the dominant contribution to delay is computation, in line with standard MEC system models [1]. Cloud servers in C reside in remote data centers. They typically offer much larger computational capacity than edge servers, but communication to and from them incurs higher latency than local communication. To capture this tradeoff, we model computation at cloud servers as effectively instantaneous (we take µn = ∞ for Sn ∈ C), while communication between the edge and each cloud server Sn ∈ C is represented by a dedicated FCFS queue (the cloud queue) with exponential service rate µ′n , which corresponds to the available data rate on the edge–cloud link [1], [2]. Thus, when a subtask (or a group of subtasks) is offloaded to cloud server Sn , we only model the time spent in the cloud queue of Sn ; once the required data have reached the cloud, the computation is assumed to complete essentially instantaneously. A key modeling assumption is that, once a subtask is offloaded to the cloud, all of its descendant subtasks in the task tree are also executed in the same cloud server. This reflects the following practical considerations: after paying the cost of sending the intermediate result from the edge to the
5
cloud, it is usually preferable to keep subsequent processing in the cloud, where computational resources are abundant; moreover, moving intermediate results repeatedly between edge and cloud would incur additional end-to-end delay and extra data transfer overhead, which is typically undesirable for latency sensitive applications [8]. Under this assumption, when subtask vkm is offloaded to cloud server Sn ∈ C, we aggregate the dependency data needed to start vkm (either from the task origin if m = 1, or from its parent subtask if m ≥ 2) together with all result data produced by the descendants of vkm , which must eventually be returned to the edge when the task completes, into a single cloud-queue workload. Formally, we define the total number of data units injected into the cloud queue of Sn as cloud Dkm,n = d(out,km) 1(m = 1) + rkm
+ d(kj,km) 1 2 ≤ m ≤ Mk , vkm ∈ C(vkj ) X + rki ,
(9)
vki ∈descendants of vkm
where d(out,km) and d(kj,km) are defined as in the previous subsection, 1(·) is the indicator function, and the summation is taken over all descendants vki of vkm in the task tree. D. Static Computation Offloading Policy Given the task and system models above, the main design degree of freedom is where each subtask is executed. We focus on static computation offloading policies: offloading decisions are expressed as fixed routing probabilities that do not depend on instantaneous queue states. In general, two broad classes of offloading policies can be distinguished: static policies, in which the server–allocation decisions for subtasks are specified by fixed probabilities and do not depend on instantaneous queue lengths or other fast-varying system state; and dynamic policies, in which offloading decisions are updated at each decision epoch based on the current state of the system (e.g., queue lengths, estimated delays). This classification is widely used in the MEC offloading literature [1], [4]. Dynamic policies can in principle react to congestion in real time, but they incur significant signaling and coordination overhead, especially when the number of servers and users is large. In contrast, static policies only require statistical information about arrival rates and service capabilities, and the offloading decisions can be precomputed and stored as routing tables at the servers. In this work, we adopt a static policy and optimize its routing probabilities to minimize the average task completion delay. Routing of root subtasks. Consider a task of type k ∈ {1, . . . , K} generated by mobile user Sn0 , where 1 ≤ n0 ≤ Nuser . The root subtask of this task is vk1 . When the task is generated, the system decides whether vk1 is processed locally at Sn0 or offloaded to some server Sn in the connection zone Zn0 . We denote by (n ,n) Rk10 (10)
the probability that the root subtask vk1 of a type-k task generated at user Sn0 is sent for execution to server Sn . These root-routing probabilities satisfy: X (n ,n) Rk10 = 1, 1 ≤ k ≤ K, 1 ≤ n0 ≤ Nuser , (11) n∈Zn0 (n ,n)
Rk10
n∈ / Z n0 .
= 0,
(12)
Hence, the root of each arriving task is always sent to one of the servers in the user’s connection zone, according to a fixed probability distribution. Routing of child subtasks. Now consider a generic subtask vkm of a type-k task. For each child vki ∈ C(vkm ), we define the routing probabilities (n ,n)
Rki p
,
Sn ∈ Znp ,
(13)
as the probability that child subtask vki is assigned to server Sn when its parent subtask vkm has just completed at server Snp . These probabilities satisfy X (n ,n) Rki p = 1, (14) Sn ∈Znp (n ,n)
Rki p
= 0,
Sn ∈ / Znp ,
(15)
for all task types k, subtask indices m and i with vki ∈ C(vkm ), and all possible parent-completion servers Snp ∈ E. Thus, for every edge (vkm , vki ) in the task tree and every possible parent-completion server Snp , the static policy specifies a probability distribution over the servers in Znp that may execute vki . Policy representation. The static computation offloading policy of the whole network is the collection of all routing probability variables: (n ,n) (n ,n) R = Rk10 , Rki p all feasible k, m, i, n0 , np , n . (16) Here, n0 denotes the index of the user that generates the task, whereas np denotes the index of the server at which the parent of a non-root subtask completes. For root-routing variables, feasibility requires Sn ∈ Zn0 . For child-routing variables, feasibility requires Snp ∈ E, Sn ∈ Znp , and vki ∈ C(vkm ). Routing probabilities corresponding to destinations outside the relevant connection zone are fixed to zero and are not treated as decision variables. III. Q UEUEING -N ETWORK M ODEL FOR C OMPUTATION O FFLOADING In this section, we develop a product-form queueingnetwork (PFQN) approximation for the computation offloading model of Section II. Here, PFQN refers to a queueing network with a product-form steady-state distribution, which allows the network to be analyzed through per-server effective arrival rates, utilizations, and waiting times. The main difficulty is that when a subtask is initiated at a server, it does not contribute a single unit to the corresponding queue. Rather, it creates a batch of units: either several computation load units at an edge server or several data units at a cloud queue. Therefore, the traffic generated by task execution is
6
correlated and appears in back-to-back bursts. This effect must be captured in the queueing model in order to obtain accurate waiting-time expressions. In the classical productform setting, the network nodes must satisfy quasi-reversibility conditions, which in particular require that the effective traffic exchanged among queues be compatible with independent Poisson-type flows [24]–[27]. The original offloading system studied here does not satisfy this condition directly. Indeed, when a subtask is initiated at a server, it creates a batch of computation load units or data units that arrive back-toback at the corresponding queue. Hence, the internal traffic is correlated and is not naturally of the form required by standard product-form queueing-network results. For this reason, the PFQN used in this paper should be understood as an approximation rather than an exact representation of the original system. The purpose of the approximation is to replace each correlated batch by an equivalent Poisson flow. After this transformation, each server is modeled as a quasi-reversible M/M/1 node, and the resulting approximating network admits a product-form interpretation. A. From Single-Queue Approximation to a Network of Queues In [28], a redundant-arrival approximation is developed for a single M/M/1 queue with batches of size two. In this work, we generalize this construction to arbitrary deterministic batch sizes and then extend it to a network of queues. Consider an M/M/1 queue fed by Poisson arrivals of batches. Suppose that a batch of type b arrives with rate λb and contains exactly Lb customers. In the original queue, the first customer of the batch arrives as an ordinary Poisson arrival and therefore sees the queue in steady state. However, the remaining Lb − 1 customers arrive immediately after the first one and thus do not see the queue in steady state; instead, each of them sees at least the customers that arrived before it in the same batch, and hence experiences more congestion than an independent Poisson arrival with the same average rate. Motivated by the size-two construction in [28], our generalized approximation replaces an arbitrary batch of size Lb by a dual quasi-reversible M/M/1 queue with two ingredients: 1) a Poisson stream of individual customers with rate Lb λb , which represents the same average offered load; 2) an additional independent Poisson stream of redundant customers, whose role is only to reproduce the extra congestion caused by the within-batch correlation. Because the resulting queue is quasi-reversible, its departures are Poisson, and the same idea can be used again if the output of one queue starts a new batch somewhere else. Having generalized the single queue construction to arbitrary batch sizes, we further extend it from a single queue to a network of queues. Whenever a subtask initiates a batch at some queue, we first replace that batch by an equivalent Poisson stream of individual units with the same average rate. Then we add an extra independent Poisson stream whose rate is chosen so as to recover the congestion lost by this Poissonization. Since the completion of one batch may initiate another batch at the same queue or at another queue, the same construction is applied repeatedly throughout the task
graph. In this way, the entire computation offloading system is approximated by a network of quasi-reversible M/M/1 queues. B. Batch Types Created by Subtask Execution For every task type Tk and every subtask vkm , define the batch size created when vkm is assigned to server Sn as ( lkm , Sn ∈ E, Bkm,n = (17) cloud Dkm,n , Sn ∈ C. Thus, if vkm is processed at an edge server, the corresponding batch consists of its lkm computation load units; if it is offloaded to a cloud server, the corresponding batch consists of the aggregated number of data units that must traverse the cloud queue. The approximation keeps track of the rate at which such batches are initiated. Once these batch-initiation rates are known, the queueing approximation of each server follows directly. C. Traffic Equations for Batch Initiations We now derive the traffic equations. Since the task graph is a rooted tree, every subtask has exactly one parent except the root. Therefore, the rate at which a subtask is initiated can be computed recursively from the initiation rate of its parent. Let γkm,n (R) denote the steady-state rate at which subtask vkm is initiated at server Sn under routing policy R. Equivalently, this is the rate of the first unit of the batch associated with vkm at server Sn . For the root subtask vk1 , the initiation rate at server Sn is γk1,n (R) =
N user X
(u)
(u,n)
λk Rk1
,
1 ≤ n ≤ N,
(18)
u=1
since a type-k task generated by user Su sends its root subtask (u,n) to server Sn with probability Rk1 . Now consider a non-root subtask vki whose parent is vkm . If the parent completes at an edge server Sj ∈ E, then child (j,n) vki is sent to server Sn with probability Rki . Hence, for every child vki ∈ C(vkm ), X (j,n) γki,n (R) = γkm,j (R) Rki , 1 ≤ n ≤ N. (19) Sj ∈E
Equation (19) is the fundamental traffic equation of the model. It states that the batch-initiation rate of a child at a destination server is obtained by summing its parent-completion rates at the different edge servers, each multiplied by the corresponding static routing probability. Observe that descendants of a subtask sent to the cloud are cloud already included in the aggregated quantity Dkm,n . Therefore, once a subtask is assigned to a cloud server, no additional downstream routing equations are needed for its descendants.
7
D. Nominal Poisson Traffic at Each Server Applying the first step of the approximation to every initiated batch, the total nominal arrival rate of individual units to server Sn is Λn (R) =
Mk K X X
Bkm,n γkm,n (R).
(20)
k=1 m=1
This is the total average rate of computation units or data units that reach server Sn after replacing each batch by a Poisson stream with the same mean rate. If one uses only (20), then each node becomes an ordinary M/M/1 queue. However, this would ignore the fact that, in the original system, the units within a batch arrive immediately one after another. Therefore, such a model would underestimate congestion. E. Congestion Correction To account for the additional congestion created by the fact that the customers after the first one in each batch do not see the queue in steady state, we add an independent Poisson stream of redundant customers at each server. The role of this extra stream is only to reproduce the average congestion effect of the original batched traffic while keeping the queue quasireversible. Hence, when a redundant load completes service, it leaves the system immediately and does not initiate any subtask, does not generate any downstream batch, and does not contribute to the traffic equations of subsequent queues. The correction term is obtained by extending the singlequeue argument in [28]. For a batch of size B, the first unit behaves as the reference Poisson arrival, while the remaining B − 1 units arrive behind it and create additional waiting. Averaging the extra delay over all positions inside the batch produces the triangular contribution B(B − 1)/2. Summing this over all batch types that feed server Sn , we define Mk K X X Bkm,n Bkm,n − 1 γkm,n (R). (21) Cn (R) = 2 m=1 k=1
Let αn (R) denote the rate of the redundant Poisson stream added to server Sn . Its value is obtained by matching the mean number of customers in the original batched queue and in the approximating dual queue. The full derivation is given in Appendix A. Here we only state the resulting relation: αn (R) = 1−ρn (R) Cn (R),
ρn (R) =
Λn (R) + αn (R) . µn (22)
Solving (22) gives ρn (R) = and
Λn (R) + Cn (R) , µn + Cn (R)
Cn (R) µn − Λn (R) αn (R) = . µn + Cn (R)
(23)
F. Waiting Time and Product-Form Approximation After the above transformation, all servers are modeled as quasi-reversible M/M/1 nodes driven by independent Poisson streams. Therefore, the whole system is approximated by a product-form queueing network. The average waiting time at server Sn is then ρn (R) . (25) Wn (R) = µn 1 − ρn (R) G. Recursive Evaluation of Traffic and M/M/1 Parameters The traffic equations are solved in a topological order over the task tree. 1) For each task type k and each possible destination server Sn , compute the root initiation rates γk1,n (R) from (18). 2) Traverse the subtasks of Tk in BFS order (or any topological order from parent to children). Whenever the rates γkm,j (R) of a parent vkm are known, compute the rates of each child vki ∈ C(vkm ) from (19). 3) After all γkm,n (R) are obtained, compute for each server Sn the nominal offered load Λn (R) from (20) and the batch-correction term Cn (R) from (21). 4) Finally, obtain ρn (R), αn (R), and Wn (R) from (23), (24), and (25). Because the task graph is acyclic, no iterative fixed-point procedure is needed for the subtask traffic itself: the rates γkm,n (R) are obtained recursively from the root toward the leaves. Therefore, the full queueing-network approximation is computationally light and can be evaluated efficiently inside the optimization procedure. It is important to interpret the proposed construction as a local moment-matching approximation applied consistently across the network. At each server, the original batched arrival process is replaced by an equivalent Poisson flow with the same mean rate, together with an additional Poisson as the flow whose rate is chosen to recover the average congestion created by the customers that arrive back-to-back within the same batch. Because each approximating node is quasi-reversible, its departure process is Poisson, which allows the same transformation to be propagated to subsequent queues without destroying tractability. In this sense, the network model is built by matching, queue by queue, the mean traffic intensity and the leading-order congestion effect of batch correlation. Accordingly, the approximation is not claimed to preserve the full dependence structure of the original batched network exactly. Its purpose is instead to capture the dominant delay distortion induced by correlated internal batches while retaining a product-form representation that can be evaluated and optimized efficiently. For this reason, the approximation is expected to be most reliable in the stable low-to-moderate load regime, whereas some loss of accuracy is natural near saturation, where higher-order dependence becomes more pronounced. The numerical results in Section VI confirm this behavior.
(24)
Therefore, each server is approximated by an M/M/1 queue with service rate µn and effective arrival rate Λn (R)+αn (R).
IV. AVERAGE TASK D ELAY D ERIVATION Our goal in this section is to express the average completion delay of each task type in terms of the PFQN parameters
8
(ki)
k8 kD k4
k7
. . .
k6
k4
k1 k3
k5
k1 k3
k2
k2
(a)
(b)
+
Fig. 2. Star-based representation of task Tk and its recursive decomposition: (a) decomposition of the task into stars and folding of their delays; (b) generic star used to define the delay parameters.
derived earlier (initiation rates, utilizations and waiting times). We first focus on a star-shaped task whose graph has one root and several children. Then we show how a general task tree can be decomposed into stars and evaluated recursively. Fig. 2 illustrates this construction: we show how a task is decomposed into stars and collapsed from the leaves to the root, and a generic star used to define the parameters in this section. A. Delay of a Star-Shaped Task Consider a single star of task Tk whose root is subtask vk1 and whose children are vk2 , . . . , vkD . We assume that the root vk1 has just completed at server Sn , with Sn ∈ E. The children may be executed at different servers depending on the static offloading policy R. Offloading scenarios. We enumerate all possible execution patterns for vk2 , . . . , vkD through the scenario set A = a = (a2 , . . . , aD ) ai ∈ {1, . . . , N } , (26) where ai denotes the index of the server that executes subtask vki . Under the static routing policy R, the probability that scenario a ∈ A occurs given that the parent vk1 has been completed at Sn is Pn (a) =
D Y
(n,ai )
Rki
,
(27)
i=2
because the children are routed independently according to the probabilities in (14). Edge and cloud processing times. For later use we group the average processing times of the children into vectors. Define x = x(k2) , . . . , x(kD) , (28) where for each child vki we set (ki)
x(ki) = x1
(ki)
(ki)
(ki)
, . . . , xNuser +Nedge , xN −Ncloud +1 , . . . , xN
with components lki 1 ≤ j ≤ Nuser + Nedge , µ , j (ki) xj = Dcloud ki,j , N − Ncloud + 1 ≤ j ≤ N. µ′j
The j-th element xj represents the mean time spent at server Sj if vki is processed there: for edge servers it is the average computation time lki /µj , and for cloud servers it is the mean cloud transmission time of the aggregated data batch Dki,j defined in (9). Contribution of a server in a given scenario. Given scenario a = (a2 , . . . , aD ), the average time that the star spends at server Sj , 1 ≤ j ≤ N , before all children are completed can be written as Tj (a) = Wj (R) 1(∃ i ∈ {2, . . . , D} : ai = j)
, (29)
(30)
D X
(ki)
xj
1(ai = j),
(31)
i=2
where Wj (R) is the mean waiting time in the M/M/1 queue at Sj , and 1(·) is the indicator function. The first term accounts for the queueing delay and is included only if at least one child is assigned to Sj in scenario a. When several children of the same star are assigned to Sj , they arrive as a single consecutive group and therefore incur this queueing delay only once. The second term sums the mean processing times of all children executed at Sj in that scenario. Average star delay conditioned on the root server. The overall delay for completing the children vk2 , . . . , vkD in scenario a is governed by the server that becomes the bottleneck. Since Tj (a) is constructed from mean queueing and processing times, we approximate the conditional mean completion delay of the star by the maximum of these mean server-wise delay contributions. Accordingly, when the root vk1 is completed at server Sn , the approximated star delay is lk1 X max Tj (a) Pn (a), Sn ∈ E, µn + 1≤j≤N (n) a∈A ETk1 (R) = Dcloud k1,n , Sn ∈ C, µ′n (32) where lk1 /µn is the mean computation time of the root when it cloud is processed at an edge server Sn , and Dk1,n /µ′n is the mean delay in the cloud queue when the root and all its descendants are offloaded to cloud server Sn . For convenience we define the vector-valued mapping (1) (N ) StarET(k1, R, x) = ETk1 (R), . . . , ETk1 (R) , (33) which returns the star delay for all possible servers of the root, given the routing policy R and the per-child vectors x in (29). B. Recursive Delay Computation for a General Task We now extend the star analysis to a general task Tk whose computation graph is a rooted tree. Algorithm 1 evaluates the task tree from the leaves toward the root. For a leaf subtask, it returns the vector of its mean execution delays over all possible servers. For an internal subtask, it first evaluates all of its children and then uses StarET to collapse the corresponding star into a single serverdependent delay vector. Repeating this procedure recursively yields the delay vector of the root subtask. Finally, the algorithm averages the root delays over its possible execution servers using the corresponding batch-initiation rates and adds the waiting time at the root server.
9
Algorithm 1 TaskET(Tk , R): average delay of task Tk 1: function SubtaskETk (m) 2: if C(vkm ) = ∅ then 3: { vkm is a leaf } 4: construct x(km) as in (29) 5: return x(km) 6: else 7: for each child vki ∈ C(vkm ) do 8: x(ki) ← SubtaskETk (i) 9: end for 10: x ← x(ki) : vki ∈ C(vkm ) 11: return StarET(km, R, x) 12: end if 13: end function
task delay: min Ttot (R) R
s.t.
ρn (R) < 1, X (n ,n) Rk10 = 1,
1 ≤ n ≤ N, ∀ k, 1 ≤ n0 ≤ Nuser ,
Sn ∈Zn0 (n ,n)
Rk10
≥ 0,
∀ k, n0 , Sn ∈ Zn0 ,
(n ,n) Rk10 = 0, X (n ,n) Rkmp = 1, Sn ∈Znp
∀ k, n0 , Sn ∈ / Zn0 ,
(n ,n)
Rkmp
≥ 0,
∀ k, 2 ≤ m ≤ Mk , Snp ∈ E, ∀ k, 2 ≤ m ≤ Mk , Snp ∈ E, Sn ∈ Znp ,
14: (1) (N ) 15: (ETk1 , . . . , ETk1 ) ← SubtaskET k (1)
(n ,n)
Rkmp = 0, ∀ k, 2 ≤ m ≤ Mk , Snp ∈ E, (n) γ (R) W (R) + ET (R) S / Znp . k1,n n n ∈ n=1 k1 (35) PNuser (u) u=1 λk Here ρ (R) is the batch-corrected utilization of server S ,
PN
16: TaskET(Tk , R) ←
n
n
obtained from the queueing approximation in Section III: ρn (R) =
C. Network-Wide Average Delay Finally, we obtain the average delay across all task types by weighting the per-type delays TaskET(Tk , R) with their PNuser (n) aggregate arrival rates. Let λk = be the total n=1 λk arrival rate of type-k tasks. The global metric is K X
Ttot (R) =
Λn (R) + αn (R) , µn
where Λn (R) is the nominal Poisson traffic at server Sn , and αn (R) is the additional Poisson correction term that captures the congestion effect of back-to-back arrivals within the batches. B. Softmax Parameterization of Routing Probabilities
λk TaskET(Tk , R)
k=1 K X
.
(34)
λk
k=1
This is the objective that will be minimized in the next section by appropriately selecting the static routing probabilities in R.
V. O PTIMIZATION OF THE S TATIC O FFLOADING P OLICY
The routing decision for a root subtask is encoded by (n ,n) Rk10 , where Sn0 is the user that generates the task. For a (n ,n) non-root subtask, the routing decision is encoded by Rkmp , where Snp is the server at which its parent subtask completes.
A. Problem Formulation Using the delay metric derived in Section IV, we seek the static routing policy that minimizes the network-wide average
Instead of enforcing the probability constraints in (35) directly, we introduce unconstrained logit variables and express the routing probabilities through softmax mappings. For each root-routing tuple (k, n0 ), we define (n ,n) exp θk10 , Sn ∈ Zn0 , P (n ,n) (n0 ,j) Rk10 (θ) = (36) exp θ Sj ∈Zn0 k1 0, S ∈ /Z . n
n0
For each non-root routing tuple (k, m, Snp ), where 2 ≤ m ≤ Mk and Snp ∈ E, we define (n ,n) exp θkmp , Sn ∈ Znp , P (n ,n) (n ,j) Rkmp (θ) = (37) exp θkmp S ∈Z j n p 0, Sn ∈ / Znp . By construction, both the root-routing and child-routing probability vectors lie on their corresponding probability simplices, so all routing constraints are automatically satisfied. All queueing parameters derived in Section III, namely γkm,n (θ), Λn (θ), Cn (θ), αn (θ), ρn (θ), and Wn (θ), become differentiable functions of θ. We denote the resulting objective by Ttot (θ) = Ttot R(θ) , and seek to minimize it over θ.
10
Algorithm 2 Gradient-based optimization of static offloading
C. Smooth Approximation of Star Maxima The star delay expression (32) contains the pointwise maximum maxj Tj (a), which makes Ttot (θ) non-smooth. To obtain a differentiable surrogate we replace this maximum by a logsum-exp (LSE) smoothing [29]. For a fixed scenario a and parameter τ > 0 we define N X 1 LSEτ T1 (a), . . . , TN (a) = log exp τ Tj (a) , τ j=1 (38) which satisfies max Tj (a) ≤ LSEτ (·) ≤ max Tj (a) + j
j
log N . τ
Replacing maxj Tj (a) by LSEτ in (32) yields a smooth (n) f k1 (θ) and, through Algorithm 1, smooth approximation ET e ^ approximations TaskET(T k , θ) and Ttot (θ) to the original delay metrics. For an appropriate τ this approximation is accurate while keeping the gradients numerically stable, in line with standard smooth-max techniques in convex optimization [29], [30].
τ > 0, step-size rule {η (t) }t≥0 , and tolerance ε > 0 3: t ← 0 4: repeat 5: build routing matrix R(θ(t) ) using (36) and (37) 6: solve the recursive traffic equations to obtain γkm,n (θ(t) ) 7: compute Λn (θ(t) ) from (20) and Cn (θ(t) ) from (21) 8: compute αn (θ(t) ) from (24), ρn (θ(t) ) from (23), and Wn (θ(t) ) from (25) (n) g km (θ(t) ) using (31) 9: evaluate smoothed star delays ET and (38) 10: run Algorithm 1 with the smoothed star delays to obtain Tetot (θ(t) ) 11: compute the barrier term B(θ(t) ) using (39) b 12: form total objective Tetot (θ(t) ) ← Tetot (θ(t) ) + B(θ(t) ) (t) b (θ(t) ) 13: compute gradient G ← ∇θ Tetot (t+1) (t) (t) (t) 14: update logits θ ←θ −η G 15: t←t+1 b b etot (θ(t−1) ) ≤ ε (θ(t) ) − Tetot 16: until T 17: R⋆ ← R(θ (t) )
D. Stability Barrier on Server Utilizations To enforce the stability constraints ρn (R) < 1 after the softmax reparameterization, we add a logarithmic barrier on the server utilizations computed by the queueing model. Let ρn (θ) be the utilization of server Sn under routing R(θ), and fix a safety level ρmax < 1 (e.g., ρmax = 0.99). We define N X ρ B(θ) = κ b ρn (θ) , b(ρ) = − log 1 − , ρmax n=1 (39) with weight κ > 0. The term B(θ) grows to +∞ as any ρn (θ) approaches ρmax , so gradient iterations remain in the interior of the stability region. This construction follows standard barrier and interior-point methods for constrained optimization [29], [30]. The objective used in the numerical optimization is therefore b Tetot (θ) = Tetot (θ) + B(θ),
1: choose initial logits θ (0) 2: choose smoothing parameter
(40)
which is smooth in θ as long as ρn (θ) < ρmax for all n. E. Gradient-Based Optimization Algorithm b Given the smooth, barrier-augmented objective Tetot (θ), we apply a standard gradient-descent scheme [30] to obtain a locally optimal static offloading policy, as summarized in Algorithm 2.
VI. P ERFORMANCE E VALUATION In this section, we evaluate the proposed framework from three complementary perspectives. First, we assess the accuracy of the queueing-network approximation. Second, we compare the delay performance of the optimized policy with the baseline algorithms. Third, we evaluate their empirical maximum stable throughput under mixed and single-class traffic.
A. System Configuration and Evaluation Methodology We emulate a canonical MEC deployment in which a set of resource-constrained user devices share a powerful edge server and a remote cloud queue. Concretely, we consider N = 4 single-server FCFS queues, indexed by S = {S1 , S2 , S3 , S4 }, and interpreted as two user devices (S1 , S2 ), one edge/MEC server (S3 ), and one cloud server (S4 ). The service rates are µ = (µ1 , µ2 , µ3 , µ′4 ) = (0.6, 0.7, 3.7, 2.2).
(41)
The connection zones are Z1 = {1, 2, 3, 4}, Z2 = {1, 2, 3}, Z3 = {1, 2, 3, 4}, Z4 = {4}. The purpose of this configuration is not to emulate a largescale deployment, but to provide a limited setting that contains all essential tiers of the considered MEC architecture: mobile user devices, a shared edge server, and a remote cloud queue. The choice N = 4 is the smallest nontrivial topology that simultaneously captures local execution, edge offloading, cloud offloading, heterogeneous service rates, and constrained connectivity. This compact setting also makes it possible to isolate the effect of the proposed batch-corrected queueing approximation and to compare analytical and simulated delays over many routing policies and offered-load values without confounding the results with large-network topology effects. We consider three task types T1 , T2 , T3 , each modeled as a rooted directed tree. The three trees are chosen to capture a shallow fork–join pattern, a hub–and–spoke pattern, and a deeper skewed tree system [8]. All loads (ℓm , rm ) and data sizes d(m,m′ ) are shown in Fig. 3.
11
ℓ12 = 3
11
,12
) =
1
d(out,21) = 1
d(
d (22
,2 2
) =
12
5)
,2
21
1
2
25
r25 = 1
22
d( ℓ24 = 4 22 ℓ22 = 3 ,24) = 1 24
r12 = 1
d(out,31) = 2 1
=
=
21
ℓ32 = 2
32
ℓ25 = 2
r23 = 1
d (21
d(31,32) = 1
)
d(
)
,23
ℓ21 = 2
r13 = 1
31
2, 33
13
23
(3
11 d(out,11) = 1
=2
d (1
=3
d
3)
1,1
ℓ11 = 2
ℓ31 = 1
ℓ23 = 2
ℓ13 = 2
r24 = 1
33
d(33,34) = 1
ℓ33 = 3
ℓ34 = 4
34 r34 = 1
Fig. 3. Task graphs used in the numerical experiments, with computation loads ℓm , result loads rm , and inter-subtask data sizes d(m,m′ ) for each edge.
Let Λsum denote the total external arrival rate of tasks. For the mixed-traffic delay experiment, it is swept over Λsum ∈ {0.10, 0.20, 0.30, . . . , 1.20} tasks/s.
(42)
For each value of Λsum , the three task types are generated according to independent Poisson processes with equal rates Λsum , k ∈ {1, 2, 3}. (43) 3 The aggregate type-k rate is split equally between the two mobile users, i.e., λk (1) (2) λk = λk = . 2 The offered-load sweep in (42) is designed to evaluate the model over a wide range of queueing regimes. As reported later in Table IV, the resulting simulated utilizations ρn span light-load, moderate-load, and near-saturation operating points across different servers and total arrival rates. Therefore, the experiments do not test the proposed approximation only at a single lightly loaded point; they expose it to a broad set of utilization levels and bottleneck patterns. For each experiment, the analytical parameters are obtained from the PFQN approximation developed in Section IV, and the corresponding ground-truth delays and utilizations are obtained by discrete-event simulation. λk =
Table II reports the resulting delay-prediction errors. In Table II, “corr.” denotes the approximation with congestion correction, while “uncorr.” denotes the approximation without congestion correction. The approximation with congestion correction remains reasonably accurate over the stable randompolicy set. Its mean relative error is 2.85% at Λsum = 0.05, 4.57% at Λsum = 0.10, 7.06% at Λsum = 0.15, and 8.37% at Λsum = 0.20. In contrast, the approximation without congestion correction is substantially less accurate, with mean relative errors of 8.20%, 15.99%, 26.12%, and 35.55% at the same load levels. Hence, the congestion-correction step provides a clear and systematic improvement over the pure Poissonized approximation. To put these errors in context, Table III reports the average simulated utilizations over the same stable random-policy set. As expected, the approximation error increases as the system moves closer to saturation. Overall, these results support two conclusions. First, the proposed queueing-network approximation remains accurate over a broad set of stable random routing policies in the lowto-moderate load regime. Second, the congestion-correction step is essential: without it, the analytical model substantially underestimates the delay induced by the within-batch dependence.
B. Accuracy of the Queueing Approximation
C. Performance of the Optimized Static Policy
We first assess the accuracy of the proposed queueingnetwork approximation independently of the optimization procedure. To this end, we generate 20 feasible static routing policies by randomizing the routing probabilities over the admissible connection zones. We then retain only those policies whose simulated maximum server utilization satisfies
Having validated the analytical approximation over a broad family of stable routing policies, we now evaluate the optimized static offloading policy obtained from Section V. We compare it against four baselines:
max ρsim n < 0.98. n
This yields a stable random-policy ensemble over which the analytical delay predictions can be compared with discreteevent simulation. Under this stability criterion, all 20 sampled policies are retained for Λsum ∈ {0.05, 0.10, 0.15, 0.20}. Thus, the approximation-accuracy study below uses the same number of stable policies at every tested load level.
•
URO (Uniform Random Offloading): For a non-root subtask, each feasible destination in the connection zone of the parent-completion server is chosen with equal probability. Thus, 1 , Sn ∈ Zn , p URO,(np ,n) 2 ≤ m ≤ Mk . Rkm = |Znp | 0, Sn ∈ / Znp , (44) For a root subtask generated at user Sn0 , the same rule is applied using the connection zone Zn0 . Hence, URO ignores both server speed and congestion, and only respects the connectivity constraint.
12
TABLE II A PPROXIMATION ACCURACY OVER STABLE RANDOM ROUTING POLICIES . Λsum 0.05 0.10 0.15 0.20
Mean delay (sim.) 8.6432 10.5975 14.8552 25.9426
Mean delay (corr.) 8.3944 10.1086 13.7782 23.8703
Mean delay (uncorr.) 7.9284 8.8857 10.8679 16.2526
TABLE III AVERAGE SIMULATED UTILIZATIONS OVER STABLE RANDOM ROUTING POLICIES . Λsum 0.05 0.10 0.15 0.20
ρ1 0.1853 0.3814 0.5922 0.7493
ρ2 0.1664 0.3251 0.4812 0.6863
ρ3 0.0301 0.0631 0.0920 0.1265
ρ4 0.0331 0.0648 0.0972 0.1290
Mean rel. err. (corr.) 0.0285 0.0457 0.0706 0.0837
Var. rel. err. (corr.) (×10−4 ) 0.449 0.846 2.822 5.244
offloading policy [21]. When a type-k task arrives at user Sn0 at time t, each feasible destination Sn ∈ Zn0 is evaluated through the task-level metric b EFO (n, t) = W cn (t) + B tot , C k k,n
(50)
cn (t) is the current queueing-delay estimate and where W tot Bk,n is the total workload of task Tk if the whole task is assigned to server Sn . The selected destination is
bkEFO (n, t), PO (Proportional-to-capacity Offloading): For a nonn⋆k (t) = arg min C (51) n∈Zn0 root subtask, each feasible destination is selected with probability proportional to its service rate. Thus, and all subtasks of the task are then executed at that same server: µn P , Sn ∈ Znp , PO,(np ,n) µ EFO,(n0 ,n) Sj ∈Znp j Rkm = 2 ≤ m ≤ Mk . Rkm (t) = 1(n = n⋆k (t)) , 1 ≤ m ≤ Mk . 0, Sn ∈ / Znp , (52) (45) Hence, EFO is dynamic at the task level, but does not For a root subtask generated at user Sn0 , the same rule is revise the decision as the task progresses through its applied using the connection zone Zn0 . Therefore, PO is dependency tree. still static, but biases the routing decisions toward faster Having defined the baseline policies, we now compare servers. them with the PFQN-based optimized static policy. In the • ITAGS (Incremental Task-Aware Greedy Scheduling): optimization step, we use a softmax parameterization with This baseline is implemented as a dynamic greedy sched- smoothing parameter τ = 10.0, learning rate 0.05, 250 optiuler [20]. When a child subtask vki becomes ready at time mization epochs, utilization cap ρ max = 0.999, penalty weight t after the completion of its parent at server Snp , every 500.0, and entropy regularization is included to discourage feasible destination Sn ∈ Znp is evaluated through the prematurely concentrated routing distributions and improve estimated completion-time metric the numerical behavior of softmax-based policy optimization ITAGS b c Cki (n, t) = Wn (t) + bki,n , (46) [33], [34]. For each arrival-rate point, the PFQN-based policy and each baseline are evaluated by 25 independent simulation cn (t) is the current queueing-delay estimate at runs. where W server Sn derived from its instantaneous queue length in Figure 4 reports the rate-weighted average task delay as the simulator, and a function of the total arrival rate Λsum in the mixed-traffic setting, where all three task types are active simultaneously. lki Sn ∈ E, For the PFQN-based policy, we show both the analytical µ , n (47) prediction and the simulated delay. The analytical curve tracks bki,n = Dcloud the simulated curve closely over most of the tested load range ki,n , Sn ∈ C. µ′n and captures the correct growth trend as the system approaches heavy load. At the same time, the optimized policy consistently The subtask is then routed greedily to outperforms all baseline methods, even dynamic ones, over the ITAGS bki n⋆ki (t) = arg min C (n, t), (48) displayed load sweep. Sn ∈Znp Table IV reports the simulated server utilizations under the that is, compared policies. The results show that the main bottlenecks ITAGS,(np ,n) Rki (t) = 1(n = n⋆ki (t)) . (49) under URO are the slower user-device queues, which approach saturation very early. PO distributes the load more evenly Thus, ITAGS makes a new routing decision whenever but its first three queues become nearly saturated as the a subtask becomes ready, using the instantaneous queue arrival rate approaches 0.90. Under ITAGS and EFO, the edge state. server S3 becomes the dominant bottleneck. In contrast, the • EFO (Expected Flow-Optimal Offloading): This basePFQN-based optimized policy shifts work away from the most line is implemented as a dynamic one-shot task-level vulnerable bottlenecks and uses the edge and cloud resources •
13
TABLE IV S ERVER UTILIZATIONS ρn VERSUS TOTAL ARRIVAL RATE Λsum UNDER DIFFERENT ROUTING POLICIES . Λsum
Rate-weighted average task delay (s)
0.10 0.20 0.30 0.40 0.50 0.60 0.70 0.80 0.90 1.00 1.10 1.20
ρ1
URO ρ2 ρ3
PO ρ4
ρ1
ρ2
ρ3
ρ4
ρ1
ITAGS ρ2 ρ3
ρ4
ρ1
EFO ρ2 ρ3
ρ4
ρ1
PFQN-based ρ2 ρ3
ρ4
0.384 0.328 0.062 0.066 0.115 0.116 0.115 0.092 0.000 0.000 0.191 0.063 0.000 0.000 0.137 0.074 0.001 0.001 0.046 0.122 0.761 0.659 0.124 0.132 0.230 0.228 0.230 0.182 0.000 0.004 0.363 0.133 0.000 0.000 0.277 0.145 0.000 0.000 0.122 0.229 0.998 0.945 0.180 0.188 0.347 0.346 0.345 0.274 0.002 0.017 0.513 0.213 0.000 0.000 0.420 0.216 0.000 0.000 0.206 0.312 0.999 0.999 0.213 0.235 0.460 0.463 0.457 0.366 0.009 0.045 0.644 0.299 0.000 0.000 0.568 0.284 0.000 0.000 0.291 0.382 0.999 0.999 0.242 0.276 0.572 0.573 0.572 0.459 0.029 0.096 0.746 0.398 0.001 0.005 0.711 0.356 0.000 0.000 0.393 0.455 0.999 1.000 0.271 0.316 0.689 0.692 0.693 0.551 0.073 0.181 0.835 0.503 0.009 0.033 0.843 0.430 0.000 0.000 0.492 0.534 1.000 1.000 0.299 0.357 0.802 0.797 0.801 0.640 0.160 0.303 0.897 0.611 0.071 0.161 0.943 0.510 0.000 0.000 0.587 0.619 1.000 1.000 0.326 0.397 0.910 0.908 0.917 0.735 0.306 0.463 0.943 0.724 0.250 0.413 0.987 0.593 0.000 0.000 0.680 0.696 1.000 1.000 0.353 0.438 0.977 0.979 0.993 0.801 0.513 0.650 0.974 0.831 0.545 0.699 0.998 0.676 0.000 0.000 0.767 0.776 1.000 1.000 0.377 0.476 0.993 0.993 0.997 0.853 0.803 0.869 0.993 0.940 0.890 0.938 0.999 0.755 0.401 0.438 0.757 0.833 1.000 1.000 0.404 0.518 0.996 0.996 0.999 0.902 0.991 0.994 1.000 0.997 0.983 0.988 0.999 0.833 0.649 0.671 0.844 0.866 1.000 1.000 0.426 0.554 0.997 0.997 0.999 0.940 0.994 0.996 1.000 0.998 0.987 0.991 1.000 0.910 0.810 0.838 0.916 0.928
TABLE V P ERCENTAGE DELAY REDUCTION OF THE OPTIMIZED PFQN- BASED POLICY RELATIVE TO THE BASELINE METHODS AT REPRESENTATIVE TOTAL ARRIVAL RATES .
103
102
101
100 0.1
0.3
0.5
0.7
0.9
1.1
1.2
Total arrival rate Λsum
PFQN-based (simulation) ITAGS PO
PFQN-based (analytical) EFO URO
Fig. 4. Rate-weighted average task delay versus total arrival rate Λsum = P k λk for the three-task MEC system. The PFQN-based policy is shown with both its analytical prediction and simulated performance, and is compared against random routing (URO), proportional-to-µ routing (PO), ITAGS, and EFO.
more effectively. At Λsum = 1.20, its utilization vector is (0.810, 0.838, 0.916, 0.928), while the other methods have at least one nearly saturated queue. This explains the large delay reductions observed in Fig. 4. To quantify the gain of the optimized policy relative to the baselines, we report the percentage delay reduction defined by Talg (Λsum ) − TPFQN (Λsum ) ∆alg (Λsum ) = 100 , Talg (Λsum )
Λsum
vs. URO
vs. PO
vs. ITAGS
vs. EFO
0.10 0.20 0.50 0.70 0.90 1.20
84.41% 91.58% 99.90% 99.87% 99.76% 99.06%
61.69% 62.18% 67.12% 75.92% 96.31% 97.31%
34.07% 32.45% 27.67% 21.95% 25.19% 94.76%
27.51% 28.73% 42.75% 63.21% 70.38% 92.05%
as their queues approach saturation. The improvement over EFO also increases substantially in the medium-to-heavy load regime. Although the improvement over ITAGS is more moderate at lower arrival rates, it increases sharply at Λsum = 1.20. For completeness, all available finite-horizon simulation results are included in Table V. Some high-load entries correspond to baseline methods operating beyond their empirical maximum stable throughput. To further examine the robustness of the optimized policy with respect to task-graph structure, we also consider three single-class traffic scenarios in which only one task type is active at a time. Figure 5 reports the resulting average delay when the arrival stream consists solely of type-1, type-2, or type-3 tasks, respectively. In all three cases, the PFQNbased optimized policy remains the best-performing method over the tested load range. This shows that the gain of the proposed policy is not merely a consequence of averaging across heterogeneous traffic classes, but persists even when each task type is studied in isolation. D. Empirical Maximum Stable Throughput
(53)
where TPFQN (Λsum ) denotes the simulated rate-weighted average task delay of the optimized PFQN-based policy, and Talg (Λsum ) denotes the corresponding simulated delay of the baseline method. As Table V shows, the PFQN-based policy achieves a lower simulated delay than every baseline at all reported arrival rates. Its advantage over URO and PO becomes particularly large
In queueing-network theory, the stability region is commonly defined as the set of arrival-rate vectors for which the network queues can be stabilized, and the maximum achievable throughput is characterized by the boundary of this region [35], [36]. Queue stability has also been explicitly considered in computation-offloading systems with stochastic task arrivals [37]. Motivated by these definitions, we use the empirical maximum stable throughput to describe the stability boundary observed in our simulations.
14
Average task delay (s)
Only T1 active
Only T2 active
Only T3 active
103
103
103
102
102
102
101
101
101
100 0.15
0.45
0.75
1.05 1.2
100 0.15
Arrival rate (tasks/s)
0.3
0.45
0.6
0.75
0.9
100 0.15
Arrival rate (tasks/s) PFQN simulation EFO
0.45
0.75
1.05 1.2
Arrival rate (tasks/s)
PFQN analytical PO
ITAGS URO
Fig. 5. Average task delay under single-class traffic scenarios: (left) only type-1 tasks arrive; (middle) only type-2 tasks arrive; (right) only type-3 tasks arrive. In all three cases, the PFQN-based optimized policy achieves the lowest delay over the tested load range. TABLE VI E MPIRICAL MAXIMUM STABLE THROUGHPUT INTERVALS IN TASKS / S . E ACH ENTRY IS REPORTED AS [Λstable , Λunstable ), WHERE Λstable IS THE LARGEST TESTED EMPIRICALLY STABLE ARRIVAL RATE AND Λunstable IS THE FIRST TESTED UNSTABLE ARRIVAL RATE . Scenario
PFQN-based
URO
PO
ITAGS
EFO
PFQN gain
Mixed Only T1 Only T2 Only T3
[1.240, 1.243) [1.400, 1.403) [0.884, 0.887) [1.446, 1.450)
[0.246, 0.250) [0.318, 0.321) [0.200, 0.203) [0.281, 0.284)
[0.843, 0.846) [0.978, 0.981) [0.637, 0.640) [1.000, 1.003)
[0.906, 0.909) [1.087, 1.090) [0.700, 0.703) [1.037, 1.040)
[0.746, 0.750) [1.053, 1.056) [0.559, 0.562) [0.737, 0.740)
36.90% 28.74% 26.34% 39.46%
Since the stability boundary is estimated through finiteduration simulations with finite search resolution, it is reported as [Λstable , Λunstable ) ,
(54)
where Λstable is the largest tested arrival rate that satisfies the empirical stability criterion and Λunstable is the first tested arrival rate that does not satisfy it. Thus, the reported interval provides an empirical estimate of the stability boundary rather than an analytical guarantee. Table VI reports the empirical maximum stable throughput intervals under mixed traffic and the three single-class traffic scenarios. The final column reports the improvement of the PFQN-based policy over the strongest baseline, calculated using the largest empirically stable rates. As shown in Table VI and Fig. 6, the PFQN-based policy achieves the largest empirical maximum stable throughput in all four traffic scenarios. Under mixed traffic, the largest empirically stable rate of the PFQN-based policy is 1.240 tasks/s, compared with 0.906 tasks/s for ITAGS, the strongest baseline. This corresponds to an improvement of 36.90%. In the T1 , T2 , and T3 single-class scenarios, the corresponding improvements over the strongest baseline are 28.74%, 26.34%, and 39.46%, respectively. These results indicate that the PFQN-based policy not only reduces average task delay within the stable operating region, but also enables the MEC system to accommodate higher aggregate task-arrival rates than the considered baseline policies.
VII. C ONCLUSION AND F UTURE W ORK In this paper, we developed an analytical framework for static computation offloading in multi-tier MEC systems with tree-structured task graphs. To capture the correlated and batched internal traffic generated by dependent subtasks, we proposed a product-form queueing-network approximation based on Poissonization and a local congestion-correction term. This yields tractable closed-form expressions for effective utilizations and waiting times. Building on these queueing parameters, we derived a recursive delay evaluation algorithm for tree-structured tasks and used it to optimize the static routing probabilities through a differentiable formulation based on softmax parameterization, log-sum-exp smoothing, and a stability barrier. Numerical results demonstrate that the proposed approximation accurately predicts average task delay over a broad family of stable routing policies. The delay-optimized static policy also achieves the lowest delay within the stable operating region and increases the empirical maximum stable throughput by 26.34%–39.46% relative to the strongest baseline across the evaluated traffic scenarios. A natural direction for future work is to extend the framework from rooted trees to more general directed acyclic graphs (DAGs). This would require revisiting both the delay recursion and the batch aggregation rules in order to handle shared descendants and subtasks with multiple parents. Another direction is to incorporate dynamic or learning-based offloading decisions on top of the present analytical framework.
15
Maximum stable throughput (tasks/s)
1.6 1.4 1.2 1 0.8 0.6 0.4 0.2 0 Mixed
T1
T2
PFQN-based
URO
PO
T3
ITAGS
EFO
Fig. 6. Empirical maximum stable throughput under mixed traffic and the three single-class traffic scenarios. Each bar shows the largest tested arrival rate satisfying the empirical stability criterion for the corresponding routing policy. The complete stability-boundary intervals are reported in Table VI.
A PPENDIX A D ERIVATION OF THE C ONGESTION C ORRECTION T ERM In this appendix, we derive the correction term used in (21)–(24). We consider a single server Sn , so for notational simplicity we omit the index n. Suppose that the server receives several types of batches. A batch of type (k, m) arrives with initiation rate γkm (R) and contains exactly Bkm customers. We compare two systems with the same exponential service rate µ and FCFS discipline.
B. Approximating Dual Queue In the approximating queue, each batch of size Bkm is replaced by a Poisson stream of individual customers with rate Bkm γkm (R). In addition, we insert an independent Poisson stream of redundant customers with rate α(R). Let Td denote the mean response time in this approximating M/M/1 queue. Then the mean number of customers in the approximating queue is ! Mk K X X Nd = Bkm γkm (R) + α(R) Td . (57) k=1 m=1
A. Original Batched Queue In the original queue, every initiated batch of type (k, m) contributes Bkm customers. Let Tp denote the average response time seen by the first customer of a batch. Then the second customer in that batch sees one extra customer ahead of it and has average response time Tp + µ1 , the third customer has average response time Tp + µ2 , and so on, up to the last customer whose average response time is Tp +
Bkm − 1 . µ
Hence, by Little’s law, the total average number of customers contributed by type (k, m) batches is γkm (R)
Bkm X−1
C. Matching the Two Queues The correction rate α(R) is chosen so that the two queues have the same average number of customers: Np = Nd .
Since both queues are single-server FCFS queues with the same exponential service rate, equality of the average number of customers implies equality of the response time seen by a Poisson arrival. Therefore, Tp = Td . Using (56), (57), and Tp = Td , we obtain
r = µ r=0 Bkm (Bkm − 1) γkm (R) Bkm Tp + . 2µ Tp +
α(R)Td =
Mk K X X k=1
γkm (R)
Bkm (Bkm − 1) γkm (R) Bkm Tp + . (56) 2µ m=1
Bkm (Bkm − 1) . 2µ
Define
Summing over all batch types, the mean number of customers in the original queue is Np =
Mk K X X k=1 m=1
(55)
(58)
C(R) =
Mk K X X Bkm (Bkm − 1) k=1 m=1
Then α(R)Td =
2 C(R) . µ
γkm (R).
(59)
16
Since the approximating queue is M/M/1 with utilization Λ(R) + α(R) , µ
ρ(R) = its mean response time is Td =
1 . µ(1 − ρ(R))
Substituting this into the previous equation yields α(R) = 1 − ρ(R) C(R). Therefore, α(R) = 1 − ρ(R) C(R),
ρ(R) =
Λ(R) + α(R) , (60) µ
which is exactly the relation used in Section III. Solving (60) gives C(R) µ − Λ(R) Λ(R) + C(R) ρ(R) = , α(R) = . µ + C(R) µ + C(R) Applying this derivation separately to each server Sn yields (23) and (24). R EFERENCES [1] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication perspective,” IEEE Commun. Surveys Tuts., vol. 19, no. 4, pp. 2322–2358, 2017. [2] T. T. Dinh, C. Lee, D. Niyato, and P. Wang, “A survey of mobile cloud computing: Architecture, applications, and approaches,” Wireless Commun. Mobile Comput., vol. 13, no. 18, pp. 1587–1611, Dec. 2013. [3] M. Satyanarayanan, “The emergence of edge computing,” Computer, vol. 50, no. 1, pp. 30–39, Jan. 2017. [4] X. Chen, L. Jiao, W. Li, and X. Fu, “Efficient multi-user computation offloading for mobile-edge cloud computing,” IEEE/ACM Trans. Netw., vol. 24, no. 5, pp. 2795–2808, Oct. 2016. [5] I. Rahmaty, H. Shah-Mansouri, and A. Movaghar, “QECO: A QoEoriented computation offloading algorithm based on deep reinforcement learning for mobile edge computing,” IEEE Trans. Netw. Sci. Eng., vol. 12, no. 4, pp. 3118–3130, Jul.–Aug. 2025, doi: 10.1109/TNSE.2025.3556809. [6] R. Guo, L. Zhou, L. Li, Y. Song, and X. Xie, “Dependent task graph offloading model based on deep reinforcement learning in mobile edge computing,” Electronics, vol. 14, no. 16, Art. no. 3184, Aug. 2025, doi: 10.3390/electronics14163184. [7] S. Sardellitti, G. Scutari, and S. Barbarossa, “Joint optimization of radio and computational resources for multicell mobile-edge computing,” IEEE Trans. Signal Inf. Process. Netw., vol. 1, no. 2, pp. 89–103, Jun. 2015. [8] J. Yan, S. Bi, and Y.-J. A. Zhang, “Offloading and resource allocation with general task graph in mobile edge computing: A deep reinforcement learning approach,” IEEE Trans. Wireless Commun., vol. 19, no. 8, pp. 5404–5419, Aug. 2020. [9] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA, USA: MIT Press, 2009. [10] X. Li, M. Abdallah, S. Suryavansh, M. Chiang, K. T. Kim, and S. Bagchi, “DAG-based task orchestration for edge computing,” in Proc. 41st IEEE Int. Symp. Reliable Distributed Systems (SRDS), 2022, pp. 23–34, doi: 10.1109/SRDS55811.2022.00013. [11] J. Xue, Z. Wang, Y. Zhang, and L. Wang, “Task Allocation Optimization Scheme Based on Queuing Theory for Mobile Edge Computing,” Mobile Information Systems, vol. 2020, Art. ID 1501403, May 2020, doi: 10.1155/2020/1501403. [12] Y. Katayama and T. Tachibana, “Optimal Task Allocation Algorithm Based on Queueing Theory for Future Internet Application in Mobile Edge Computing Platform,” Sensors, vol. 22, no. 13, Art. no. 4825, 2022, doi: 10.3390/s22134825. [13] D.-Y. Hwang, K.-F. Lai, and K.-Y. Lin, “Queue-Length-Based Offloading for Delay Sensitive Applications in Federated CloudEdge-Fog Systems,” in Proc. IEEE CCNC, 2024, pp. 406–411, doi: 10.1109/CCNC51644.2024.10454812.
[14] Z. Xie, X. Zhao, D. Han, L. Gao, Z. Jiang, J. Zhu, X. She, and P. Chen, “A Markovian queueing model for end-to-end delay analysis in computation offloading system,” IEEE Commun. Lett., vol. 27, no. 10, pp. 2687–2691, Oct. 2023, doi: 10.1109/LCOMM.2023.3307876. [15] S. Dong et al., “Task offloading strategies for mobile edge computing: A survey,” Computer Networks, vol. 254, Art. no. 110791, 2024, doi: 10.1016/j.comnet.2024.110791. [16] H. Wang, H. Xu, H. Huang, M. Chen, and S. Chen, “Robust task offloading in dynamic edge computing,” IEEE Trans. Mobile Comput., vol. 22, no. 1, pp. 500–514, Jan. 2023. [17] Y. Qu, H. Dai, F. Wu, D. Lu, C. Dong, S. Tang, and G. Chen, “Robust offloading scheduling for mobile edge computing,” IEEE Trans. Mobile Comput., vol. 21, no. 7, pp. 2581–2595, Jul. 2022. [18] S. Li, C. Li, Y. Huang, B. A. Jalaian, Y. T. Hou, and W. Lou, “Enhancing resilience in mobile edge computing under processing uncertainty,” IEEE J. Sel. Areas Commun., vol. 41, no. 3, pp. 659–674, Mar. 2023. [19] S. Jiao, H. Wang, and J. Luo, “SRA-E-ABCO: Terminal task offloading for cloud-edge-end environments,” J. Cloud Computing, vol. 13, no. 1, Art. no. 58, 2024, doi: 10.1186/s13677-024-00622-y. [20] S. Sundar and B. Liang, “Offloading Dependent Tasks with Communication Delay and Deadline Constraint,” in Proc. IEEE INFOCOM, Apr. 2018, pp. 37–45, doi: 10.1109/INFOCOM.2018.8486305. [21] C. Shu, Z. Zhao, Y. Han, G. Min, and H. Duan, “Multi-user offloading for edge computing networks: A dependency-aware and latency-optimal approach,” IEEE Internet of Things Journal, vol. 7, no. 3, pp. 1678– 1689, Mar. 2020, doi: 10.1109/JIOT.2019.2943373. [22] Z. Cao, X. Deng, S. Yue, P. Jiang, J. Ren, and J. Gui, “Dependent task offloading in edge computing using GNN and deep reinforcement learning,” IEEE Internet Things J., vol. 11, no. 12, pp. 21632–21646, Jun. 2024, doi: 10.1109/JIOT.2024.3374969. [23] L. Ale, N. Zhang, X. Fang, X. Chen, S. Wu, and L. Li, “Delay-aware and energy-efficient computation offloading in mobile-edge computing using deep reinforcement learning,” IEEE Transactions on Cognitive Communications and Networking, vol. 7, no. 3, pp. 881–892, Sep. 2021, doi: 10.1109/TCCN.2021.3066619. [24] F. Baskett, K. M. Chandy, R. R. Muntz, and F. G. Palacios, “Open, closed, and mixed networks of queues with different classes of customers,” J. ACM, vol. 22, no. 2, pp. 248–260, 1975. [25] F. P. Kelly, Reversibility and Stochastic Networks. Chichester, U.K.: Wiley, 1979. [26] R. Serfozo, Introduction to Stochastic Networks. Berlin, Germany: Springer, 1999. [27] E. Gelenbe and G. Pujolle, Introduction to Queueing Networks, 2nd ed. Chichester, U.K.: Wiley, 1998. [28] M. Rahnamania and F. Ashtiani, “A new analytical approach for delay analysis in the presence of correlated arrivals,” in Proc. Iran Workshop Commun. Inf. Theory (IWCIT), 2024, pp. 1–6, doi: 10.1109/IWCIT62550.2024.10553217. [29] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, U.K.: Cambridge Univ. Press, 2004. [30] D. P. Bertsekas, Nonlinear Programming, 2nd ed. Belmont, MA, USA: Athena Scientific, 1999. [31] L. Kleinrock, Queueing Systems, Volume I: Theory. New York, NY, USA: Wiley, 1975. [32] Y. Zhang, Y. Jiang, and S. Fu, “Service modeling and delay analysis of packet delivery over a wireless link,” in Proc. IEEE 28th Int. Workshop Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), Edinburgh, U.K., Nov. 2023, pp. 296–301, doi: 10.1109/CAMAD59638.2023.10478419. [33] Z. Ahmed, N. Le Roux, M. Norouzi, and D. Schuurmans, “Understanding the impact of entropy on policy optimization,” in Proc. 36th Int. Conf. Mach. Learn. (ICML), vol. 97, pp. 151–160, 2019. [34] J. Mei, C. Xiao, C. Szepesvári, and D. Schuurmans, “On the global convergence rates of softmax policy gradient methods,” in Proc. 37th Int. Conf. Mach. Learn. (ICML), vol. 119, pp. 6820–6829, 2020. [35] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936–1948, Dec. 1992, doi: 10.1109/9.182479. [36] M. J. Neely, Stochastic Network Optimization with Application to Communication and Queueing Systems. San Rafael, CA, USA: Morgan & Claypool, 2010, doi: 10.2200/S00271ED1V01Y201006CNT007. [37] S. Bi, L. Huang, H. Wang, and Y.-J. A. Zhang, “Lyapunovguided deep reinforcement learning for stable online computation offloading in mobile-edge computing networks,” IEEE Trans. Wireless Commun., vol. 20, no. 11, pp. 7519–7537, Nov. 2021, doi: 10.1109/TWC.2021.3085319.