Throughput-Optimal Control of Distributed Computing Networks for Service DAGs

1

Throughput-Optimal Control of Distributed Computing Networks for Service DAGs

arXiv:2611.05007v1 [cs.NI] 3 Nov 2026

Peng Li, Graduate Student Member, IEEE, Jianan Zhang, Member, IEEE, Jaime Llorca, Senior Member, IEEE, Xinzhe Fu, Xiang Cheng, Fellow, IEEE, and Chen Chen, Senior Member, IEEE Abstract—Executing service workflows with directed acyclic graph (DAG) dependencies over wireless distributed computing networks requires joint control of function placement, routing, and scheduling, together with synchronization of inputs from the same request at merge points. We study throughput-optimal control of these networks under stochastic request arrivals, time-varying wireless links, and interference constraints. We use a valid mapping abstraction that assigns each service function to a computation node and each DAG dependency to a routing path. Using this abstraction, we characterize the network capacity region to support service DAGs, and prove that synchronizing the packets of a request at merge points does not shrink the region. We develop Dynamic Computing Network Control for service DAGs (DCNC-DAG), a dynamic control policy that selects queue-aware valid mappings and schedules service DAG execution by nearest-to-origin (NTO) while enforcing input synchronization at merge points. With exact minimum-cost valid mappings, DCNC-DAG is throughput-optimal and ensures rate stability of the physical queues under bounded arrivals. These guarantees hold for any fixed finite interval between mapping updates, even when mapping decisions rely on boundedly stale queue length information. For larger service DAGs, we develop DCNC-DAG-H, which replaces exact mapping optimization with a queue-aware heuristic. Simulations show that DCNC-DAG supports 2.7×–5.5× the throughput of queue-blind baselines, while DCNC-DAG-H achieves up to 2.68× those of the corresponding baselines on larger workflow and AI service DAGs. Index Terms—Service DAG, distributed computing network, throughput optimality, mobile edge computing, Lyapunov optimization, stochastic network control, cross-layer optimization.

✦

1

I NTRODUCTION

E

MERGING mobile and edge services increasingly execute workflows whose functions are coupled by data dependencies. Examples include embodied artificial intelligence (AI) [1], connected and autonomous driving [2], and distributed mixture-of-experts (MoE) serving, which spreads experts across devices [3], [4]. A request may collect several raw inputs, execute interdependent functions, split intermediate results across branches, and later merge them. A directed acyclic graph (DAG) represents this structure, with service functions as vertices and dependency relations as edges. We refer to such a dependency graph as a service DAG. When no single device can execute the complete request, both the functions and their dependency flow must be distributed across wireless access, backhaul, and edge computing resources. We study a distributed computing network serving stochastic request arrivals over time-varying wireless links with interference constraints. For each service request, the controller decides execution nodes for service functions and routes for dependencies. Across requests, it schedules computation and wireless transmissions subject to the interference constraints. The objective is to support the largest set of request arrival rates—equivalently, to obtain throughputoptimal control for service DAGs. In a general service DAG, different dependency edges

•

Peng Li, Jianan Zhang, Xiang Cheng, and Chen Chen are with the State Key Laboratory of Photonics and Communications, School of Electronics, Peking University, Beijing, China. Jaime Llorca is with the Centre Tecnològic de Telecomunicacions de Catalunya, Spain, and with New York University, USA. Xinzhe Fu is with Five Rings Capital, NY, USA. E-mail: zhangjianan@pku.edu.cn (corresponding author: Jianan Zhang).

may carry different data, and a downstream function can execute only after all required inputs of the same request have arrived. A capacity region characterization must therefore capture the coupling between function placement decisions and the routing decisions for different dependencies. The controller must also stabilize the synchronization backlog that accumulates at merge points when required inputs arrive at different times, in addition to the communication and computation queues. Existing throughput-optimal control algorithms address service function chains in cloud networks [5], [6], mixed-cast service flows [7], generalized network flow problems [8], and DAG jobs with precedence constraints on multiple servers [9]. Synchronization models typically assume fixed placement and routing [10], [11]. Neither line of work jointly addresses function placement, per-dependency routing, wireless scheduling under interference constraints, and request synchronization in the service DAG setting. We address this gap through a valid mapping [12], which assigns each service function to a computation node and each dependency to a network path. The resulting communication and computation load vectors provide the basis for a state-averaged linear programming (LP) characterization of the capacity region. Our Dynamic Computing Network Control for service DAGs (DCNC-DAG) selects mappings using virtual queue lengths as congestion prices and activates wireless links by a max-weight rule. The selected mappings are executed in the physical system using nearestto-origin (NTO) scheduling [13] for transmissions and computations, together with per-request waiting pools that synchronize inputs at merge points. Since exact minimum-cost

2

valid mapping is NP-hard for general service DAGs [14], we also develop DCNC-DAG-H, a queue-aware heuristic for larger service DAGs. The main contributions of this paper are summarized as follows. •

•

•

•

2

We characterize the capacity region of distributed computing networks serving arbitrary service DAGs under i.i.d. wireless states and interference constraints on link activation. By decomposing each completed request into valid mappings that preserve its function placements, we derive a state-averaged LP whose interior remains achievable despite request synchronization at merge points. We develop DCNC-DAG, a frame-based dynamic control policy that makes queue-aware function placement and routing decisions. It schedules wireless transmissions and computations while synchronizing inputs of the same request at merge points. We further develop DCNC-DAG-H, a queue-aware heuristic variant for larger service DAGs. For any finite frame length and bounded i.i.d. request arrivals, we prove that DCNC-DAG with exact minimum-cost valid mappings is throughputoptimal: the virtual queues are strongly stable, while the physical queues and synchronization waiting pools are rate stable. A key step in the physical stability proof is to bound the number of packets waiting at merge points. The same guarantees hold with boundedly stale queue prices. DCNC-DAG is evaluated on four wireless networks and achieves 2.7×–5.5× the throughput of queueblind baselines, while DCNC-DAG-H is evaluated on workflow and AI service DAGs with 20–31 functions and achieves up to 2.68× the throughput of the baselines in the corresponding experiments.

R ELATED W ORK

Throughput-optimal network control. Dynamic cloud network control (DCNC) [5], [6] establishes throughput-optimal control for service chains, UCNC [7] extends joint placement and routing to mixed unicast and multicast traffic, and UMW [8] accommodates time-varying links and general feasible activation sets. Their path, tree, or generalized flow representations do not capture service DAGs requiring inputs from multiple upstream functions to be synchronized within each request. Extensions address software-defined networking and network function virtualization integration [15], reconfiguration costs [16], and fixed data-intensive pipelines with multi-hop routing and identity queues [17], but retain this structural limitation. Throughput-optimal scheduling for DAG jobs [9] handles precedence and synchronization on multiple servers without multi-hop routing or wireless dynamics. Dispersed computing [18] extends scheduling of serial tasks to DAGs with input joins under broadcast communication, but does not address perdependency multi-hop routing or wireless link activation under interference constraints. Synchronization with fixed placement and routing. Maximum-pressure control for stochastic processing networks [10] and stability models for acyclic fork-join

networks [11] account for processing dependencies and merge synchronization under fixed task locations and routing relations. They do not jointly choose function placement and per-dependency routing or handle transmissions coupled by wireless interference. Placement and routing decisions determine when the inputs of each request arrive at a merge point, and the resulting waiting backlog must also be stabilized. DAG placement and wireless computing. Workflow scheduling [19], cooperative DAG offloading [20], and mobilityaware offloading [21] primarily use offline or one-shot formulations. DAG orchestration over the compute continuum [22] and Jupiter [23] address DAG execution without throughput-optimal online control under stochastic arrivals and network conditions. Virtual network embedding [12], [14] provides offline placement and routing methods; we use DynVMP within our online controller. Learning-based device placement [24] focuses on placement. Wireless computing control [25], dense cell offloading [26], and dynamic service provisioning [27] incorporate wireless or resource dynamics, but their guarantees do not cover the joint placement, per-dependency routing, and input synchronization considered here. Delayed and infrequent control information. Throughput can be preserved under delayed network state [28], framebased decisions [29], [30], and reconfiguration delay [31]. Most closely related is [32], which separates slowly updated queue information from fast channel scheduling. In DCNCDAG, the slow decision is a valid mapping, so the analysis must bound the effect of stale prices across all communication and computation resources it uses. To the best of our knowledge, DCNC-DAG is the first policy with a throughput optimality guarantee for service DAGs that jointly handles function placement, perdependency multi-hop routing, per-request input synchronization, and wireless transmission under time-varying link states and interference constraints. Table 1 summarizes the differences from closely related work.

3

S YSTEM M ODEL

In this section, we introduce the network, service DAG, and traffic models and define the dynamic control problem. 3.1

Distributed Computing Network Model

We model the distributed computing network as a directed graph G = (V, E), where V is the node set and E is the set of directed wireless links. Each node can forward packets and host one or more service functions. Time is slotted with slots indexed by t ∈ {0, 1, 2, . . .}. Let µu denote the computation capacity of node u ∈ V , and let µuv denote the communication capacity of link (u, v) ∈ E when it is available. Let σuv (t) ∈ {0, 1} denote the wireless state of link (u, v) in slot t, where σuv (t) = 1 indicates the link is ON and σuv (t) = 0 indicates the link is OFF. The instantaneous communication capacity is µuv (t) = µuv σuv (t). Let σ(t) = {σuv (t), (u, v) ∈ E} denote the wireless state vector. For a network node u, let δ + (u) and δ − (u) denote its outgoing and incoming neighbors in G , respectively. To model wireless interference, let A ⊆ {0, 1}|E| be the set of feasible link activation vectors. For s(t) ∈ A,

3

TABLE 1 Comparison of closely related works. Reference

Service structure

Multi-hop routing

Wireless & interference

Input matching

Stability / throughput guarantee

DCNC [5], [6] UCNC [7] UMW [8] Processing networks [10] Fork-join networks [11] DAG job scheduling [9] Dispersed computing [18] Data-intensive pipelines [17] This paper

chain / tree chain – processing network DAG DAG chain / DAG chain / tree DAG

yes yes yes no fixed no no yes yes

no no yes no no no no no yes

by type none none by type by request by request by request by request by request

throughput-optimal throughput-optimal throughput-optimal throughput-optimal stability analysis throughput-optimal throughput-optimal throughput-optimal throughput-optimal

“fixed” denotes predetermined routes. Input matching is by input type or by request identity, including job identity; “none” denotes no multi-input matching. “–” indicates that computation is not modeled.

suv (t) = 1 indicates that link (u, v) is activated in slot t. Combining the observed ON/OFF states with the interference constraints, the feasible activation set is A(σ(t)) ≜ {s ∈ A : suv ≤ σuv (t), ∀(u, v) ∈ E} . If s(t) ∈ A(σ(t)) is selected in slot t, link (u, v) can serve up to µuv (t)suv (t) workload units in slot t. Assumption 1. The wireless state vectors {σ(t)}t≥0 are i.i.d. over time. Remark 1. The feasible activation set A accommodates general link interference constraints. Specifically, under the primary interference model, each node can be incident to at most one activated link in a slot:     X X suv + svu ≤ 1, ∀u ∈ V . Apri = s ∈ {0, 1}|E| :   − + v∈δ (u)

3.2

v∈δ (u)

Service DAG Model

A service DAG is represented by a directed acyclic graph ϕ = (V ϕ , E ϕ ), where V ϕ contains service functions and E ϕ contains dependency relations. A directed edge (Aϕ , B ϕ ) indicates that processing B ϕ requires the output produced by Aϕ . For each service function Aϕ , let VAϕ ⊆ V denote its qualified node set, i.e., the computation nodes that host an implementation of Aϕ and hence can execute it. We use the same notation δ + (Aϕ ) and δ − (Aϕ ) for the successor and predecessor functions of Aϕ in ϕ, respectively. Source functions have no predecessor functions in the service DAG and take raw inputs, whereas sink functions ϕ produce outputs that leave the network. Let Vsϕ and Vd denote the sets of source and sink functions, respectively. For each source function Aϕ ∈ Vsϕ , introduce an auxiliary ϕ ϕ service source SA ; similarly, for each sink function Aϕ ∈ Vd , ϕ introduce an auxiliary service sink DA . Define

For each augmented dependency edge (Aϕ , B ϕ ) ∈ Ē ϕ , ϕ ϕ let ξ (A ,B ) > 0 denote the communication workload carried from Aϕ to B ϕ per request. For each service function ϕ Aϕ ∈ V ϕ , let rA > 0 denote the computation workload required to execute the function. For each request, define ϕ ϕ ϕ ϕ ξ ϕs = {ξ (SA ,A ) : Aϕ ∈ Vsϕ } and ξϕd = {ξ (A ,DA ) : Aϕ ∈ Vdϕ } as the input workloads required by the source functions and the output workloads delivered by the sink functions, respectively. For modeling simplicity, each request is an atomic unit: every service function is executed exactly once at one qualified node, without splitting that execution across nodes. A flow comprises multiple such requests, which may assign the same service function to different qualified nodes and execute concurrently. Execution starts only after all of its required inputs have arrived at that node. After execution, the function produces its outputs once and sends them toward its successor functions. Merging and execution consume at most one copy of each required packet, so duplicate packets cannot create additional usable outputs. Data associated with different dependency edges are distinct and routed separately; in particular, outputs for different successor functions differ in content and therefore cannot benefit from multicast. Fig. 1 illustrates the model through an autonomous driving task with image, LiDAR, and IMU inputs, perception, localization, tracking, and planning functions, and control command outputs. The example illustrates input merging, output splitting, and workload scaling across dependencies. 3.3

Traffic Model

ϕ ϕ Esϕ = {(SA , Aϕ ) : Aϕ ∈ Vsϕ }, Edϕ = {(Aϕ , DA ) : Aϕ ∈ Vdϕ }.

A commodity (c, ϕ) is specified by a service DAG ϕ and its (c,ϕ) endpoints in the computing network: ρs : S ϕ → V and (c,ϕ) ρd : Dϕ → V . Let K denote the finite commodity set, (c,ϕ) (c,ϕ) ϕ ϕ c c ≜ ρd (DA ). A request is and write SA ≜ ρs (SA ), DA completed once all sink outputs have been fully delivered to their corresponding network endpoints. Let A(c,ϕ) (t) denote the number of commodity-(c, ϕ) requests arriving in slot t. A request may inject source packets at multiple service sources.

The augmented service DAG has node set V̄ ϕ = V ϕ ∪ S ϕ ∪ Dϕ and edge set Ē ϕ = E ϕ ∪ Esϕ ∪ Edϕ .

Assumption
2 (Proportional request arrivals). Let A(t) ≜ A(c,ϕ) (t) (c,ϕ)∈K . The process {A(t)}t≥0 is i.i.d. across slots

ϕ S ϕ = {SA : Aϕ ∈ Vsϕ },

ϕ Dϕ = {DA : Aϕ ∈ Vdϕ },

with

4 "!

𝜉 (,# ," = 1.5

𝑟" ! = 2 𝐴!! image processing

!

𝑆" ! "

(,$ ! ,#"! )

𝜉 =2 ! 𝑆# !

"

"

𝜉 (" ! ,& ! ) " = 1.5 𝑟& ! = 3 𝐸 !! perception

" 𝑟# ! = 2

𝐵!! LiDAR processing

"

(,% ! ,$ "! )

𝜉 = 0.5 ! 𝑆$ !

capacities µuv (t)suv (t), and the node capacities µu .

"

"! )

"

"

"

𝜉 (# ! ,& ! ) = 1.5 "

" 𝑟 ( ! = 1.5

"

"

𝜉 (& ! ,( ! ) =2

"

𝑟% ! = 2 𝐺 !! 𝐻!! ! tracking and 𝐷% ! planning " " "! "! prediction 𝜉 (( ! ,% ! ) 𝜉 (% ,-& ) =1 =1

"

𝜉 (# ! ,' ! ) = 1.5 " 𝑟 ' ! = 1.5 𝐹 !! localization

𝑟$ ! = 1 𝐶 !! "! "! IMU processing 𝜉 ($ ,' ) = 0.5

"

"

𝜉 (' ! ,% ! ) = 1

𝜉 ('

"! ,-"! ) '

=1

!

𝐷' !

(a) Dependency structure. splitting

!

𝑆" !

2

𝐵!! LiDAR processing 2

𝐸 !! perception

1.5

1.5 merging

1 ! 𝑆# !

0.5

𝐹 !! localization

𝐶 !! IMU processing 0.5

(b) Merging, splitting, and workload scaling. Fig. 1. Service DAG of an autonomous driving task. A request merges multiple raw inputs, splits intermediate outputs across successor functions, and may change the workload along different dependencies; the numerical values are illustrative.

The controller is logically centralized. In each slot, it observes the request arrivals A(t) and wireless state σ(t), and maintains virtual queue lengths as congestion prices from these observations and its previous decisions. Mapping decisions use the prices observed at the beginning of each frame, while link activation uses the current prices and wireless state every slot. Sections 5 and 6 specify these rules and their physical execution.

4

In this section, we use the valid mapping of [12] to represent the placement and routing decisions of one request and characterize the network capacity region by a state-averaged LP under wireless interference and time-varying link states. 4.1

Assumption 3 (Bounded request arrivals). For each com(c,ϕ) modity (c, ϕ), there exists a finite constant Amax such that (c,ϕ) A(c,ϕ) (t) ≤ Amax for all t, almost surely. Definition 1 (Dynamic control problem for service DAGs). Consider a network G with node capacities {µu }, link capacities {µuv }, wireless state process {σ(t)}, feasible activation set A, and commodity set K. The dynamic control problem for service DAGs is to choose processing locations, dependency routes, link activations, and schedules in each slot. The objective is to support the largest set of request arrival rates, subject to the service DAG dependencies, the wireless constraints s(t) ∈ A(σ(t)), the link

Valid Mapping

Definition 2 (Valid mapping [12]). A valid mapping of com(c,ϕ) (c,ϕ) (c,ϕ) modity (c, ϕ) is a tuple m(c,ϕ) = (mV , mE ), where mV maps nodes of the augmented service DAG to computation nodes (c,ϕ) in G and mE maps dependency edges to simple paths in G . The qualified node sets VAϕ are those of Section 3.2; auxiliary sources c c and sinks have singleton candidate sets {SA } and {DA }. The mapping must satisfy:

and independent of the wireless state process {σ(t)}t≥0 . For each commodity, E[A(c,ϕ) (t)] = λ(c,ϕ) , and the workload vector contributed by its source functions in slot t is A(c,ϕ) (t)ξ ϕ s , with mean λ(c,ϕ) ξ ϕ s. This model assumes that all source packets of a request are generated in the same slot, as when sensors are triggered by a common hardware clock. The assumption can be relaxed to allow for uniformly bounded differences in the arrival times of source packets belonging to the same request, and inputs belonging to the same request can be merged. Under asynchronous arrivals, the source packets belonging to the same request are held until all inputs arrive and are then released together into the network. Under bounded request arrivals, the number of requests awaiting release remains uniformly bounded, preserving the same stability and throughput optimality guarantees. The vector ξ ϕ s specifies the number of source packets required by one request. Unequal raw input rates can be accommodated by forming requests from the required source inputs and discarding surplus inputs that cannot contribute to additional request completions.

C APACITY R EGION

• •

(c,ϕ)

Node mapping: for each Aϕ ∈ V̄ ϕ , mV (Aϕ ) ∈ VAϕ ; Edge mapping: for each (Aϕ , B ϕ ) ∈ Ē ϕ such that (c,ϕ) (c,ϕ) (c,ϕ) mV (Aϕ ) ̸= mV (B ϕ ), mE (Aϕ , B ϕ ) is a simple (c,ϕ) (c,ϕ) ϕ path in G from mV (A ) to mV (B ϕ ); co-located dependencies map to the empty path and consume no link capacity.

Let M(c,ϕ) denote the finite set of valid mappings of commodity (c, ϕ). We retain only mappings that use available resources, i.e., computation nodes u with µu > 0 and links that can be activated with positive probability under some feasible wireless state and activation. Removing all other mappings does not affect the capacity region. We assume that the resulting set M(c,ϕ) is nonempty. (c,ϕ) For a valid mapping mk , define the corresponding per-request load vector by n o X ϕ ϕ (c,ϕ) (c,ϕ) Mk,uv = ξ (A ,B ) I (u, v) ∈ mk,E (Aϕ , B ϕ ) , (Aϕ ,B ϕ )∈Ē ϕ (c,ϕ) Mk,u =

X

ϕ

(c,ϕ)

rA I{u = mk,V (Aϕ )}.

Aϕ ∈V ϕ

A valid mapping specifies the placement and routing decisions for one request. It is the per-request control action used by DCNC-DAG, and its load vector is the basic accounting unit of the capacity region characterization developed below. 4.2

Policy Space

To connect packet-level routing with the communication workload model, we use a normalized packet unit. We assume that the communication workloads are rational numbers; since the commodity set is finite, the unit can be chosen so that every augmented dependency edge carries

5

an integer number of normalized packets per request. We measure communication workloads in normalized packet units and link capacities in the corresponding units per slot. Thus, transmitting one normalized packet over one link requires one unit of transmission service. Definition 3 (Admissible policy). An admissible dynamic control policy π controls two actions: (i) routing and processing: for each request, choose one qualified execution node for every service function and route the packets associated with every dependency edge; (ii) scheduling: in every slot t, choose s(t) ∈ A(σ(t)) and schedule transmissions and processing under capacities µuv (t)suv (t) and µu . Let Π denote the set of admissible policies and, for π ∈ Π, let κ(c,ϕ),π (t) denote the number of commodity(c, ϕ) requests completed by time t under policy π , where completion is determined for each request according to the rule in Section 3.3. Outputs belonging to different requests cannot be combined to form a completion. A policy π ∈ Π is said to support an arrival rate vector Λ = {λ(c,ϕ) } if lim inf t→∞ κ(c,ϕ),π (t)/t = λ(c,ϕ) w.p. 1 for every (c, ϕ) ∈ K. Definition 4 (Capacity region). The capacity region Γ(G, K) is the set of arrival rate vectors Λ supported by some admissible policy π ∈ Π. A policy is throughput-optimal if it supports every arrival rate vector in int(Γ(G, K)). Under interference, the long-term communication capacities of different links are coupled. For each wireless state σ , let pσ = Pr{σ(t) = σ}. For each s ∈ A(σ), let ασ,s ≥ 0 denote the fraction of slots with state σ in which activation s is selected. The state-averaged communication service region is n X |E| C = c̄ ∈ R+ : ∃ ασ,s ≥ 0, ασ,s ≤ 1, ∀σ, s∈A(σ)

c̄uv ≤

X

pσ ασ,s µuv σuv suv ,

Lemma 1 preserves this consistency while keeping the computation loads unchanged and not increasing the communication loads. The complete proof is given in Appendix A. Let ΓLP be the set of arrival rate vectors Λ for which (c,ϕ) there exist rates {fk ≥ 0} of valid mappings and c̄ ∈ C with X (c,ϕ) λ(c,ϕ) = fk , ∀(c, ϕ) ∈ K, (1) k

X

(c,ϕ) (c,ϕ) fk Mk,uv ≤ c̄uv ,

∀(u, v) ∈ E,

(c,ϕ),k (c,ϕ)

X

fk

(c,ϕ)

Mk,u ≤ µu ,

∀u ∈ V.

(c,ϕ),k

(2) (3)

The next theorem identifies the resource constraints that limit achievable throughput. Every supportable arrival rate must satisfy the LP, and every rate strictly inside its feasible region is achievable under bounded arrivals, despite synchronization at merge points. Theorem 1 (Capacity region characterization). Under Assumptions 1–2, every arrival rate vector supportable by an admissible policy belongs to ΓLP . If Assumption 3 also holds, every vector in int(ΓLP ) is supportable. Consequently, ΓLP characterizes the capacity region Γ(G, K) up to a possible difference on their boundaries, and

int(Γ(G, K)) = int(ΓLP ). Appendix A proves necessity by applying Lemma 1 to completed requests and taking limits of the empirical mapping rates. The constructive sufficiency direction follows from the virtual queue and physical queue stability results below and Corollary 2. The LP serves as an analytical characterization of the capacity region. The online policy developed next does not solve this LP and requires no knowledge of the arrival rates {λ(c,ϕ) } or the wireless state distribution {pσ }.

σ, s∈A(σ)

o ∀(u, v) ∈ E . 4.3

Capacity Region

The admissible policy space is more general than policies that explicitly select valid mappings. The following lemma connects arbitrary completed executions to the valid mapping load representation used in the capacity characterization. Lemma 1 (Valid mapping decomposition of a completed request). For every completed request, there exists a convex combination of valid mappings that all place each service function at the node where it was executed for that request. The communication load induced by this combination on each link does not exceed the load actually incurred by the request on that link, whereas the induced computation load on each node equals the request’s actual computation load on that node. The construction extends the efficient route reduction used in UCNC [7]. For a service DAG, the path decompositions of different dependencies must additionally remain consistent with the same function placements of a request;

5 DYNAMIC R OUTING P OLICY FOR A V IRTUAL S YSTEM This section introduces the virtual queues and frame-based mapping policy, establishes virtual queue stability under current or boundedly stale mapping prices, and describes a heuristic for larger service DAGs. 5.1

Virtual Queueing System

Virtual queues are auxiliary workload counters used for control and stability analysis; they are distinct from the actual system queues. Each link (u, v) has a virtual come uv , and each node u a virtual communication queue Q e putation queue Qu . When a request arrives and a valid mapping is selected, the virtual system immediately charges the full communication and computation workloads induced by that mapping to the corresponding virtual queues, without accounting for the sequential order of the physical transmissions and computations. Let k (c,ϕ),π (t) denote the index of the mapping selected by policy π for commodity (c, ϕ) in slot t. The resulting virtual arrivals (c,ϕ) e(c,ϕ),π e(c,ϕ),π are A (t) = A(c,ϕ) (t)Mk(c,ϕ),π (t),uv and A (t) = uv u

6 (c,ϕ) A(c,ϕ) (t)Mk(c,ϕ),π (t),u , summed over commodities eπ (t), A eπ (t). The virtual queues evolve as A uv u



e uv (t + 1) = Q e uv (t) + A eπ (t) − µuv (t)sπ (t) Q uv uv

to give

+

 + e u (t + 1) = Q e u (t) + A eπ (t) − µu Q , u

,

(4) (5)

where (a)+ = max(a, 0) and sπ (t) ∈ A(σ(t)). 5.2

Fix a positive integer F and partition time into frames b e n) Tn = {nF, . . . , nF +F −1}. Let τn = nF and Q(n) = Q(τ be the virtual queue lengths observed at the beginning of frame n and used for mapping. Virtual queues continue to evolve within each frame, and link activation uses the current queue prices and wireless state every slot. Definition 5 (Routing policy π v,F ). At the beginning of frame n, the policy initializes an empty mapping table. In each slot t ∈ Tn : (i) for each commodity (c, ϕ) with A(c,ϕ) (t) > 0 and no stored mapping in frame n, compute " X (c,ϕ) b b uv (n)M(c,ϕ) k ∈ arg min Q (c,ϕ)

k: mk

∈M(c,ϕ) (u,v)∈E

k,uv

(6)

#

+

X

Virtual Queue Stability

As virtual queues evolve within a frame, the stored mapping may cease to minimize the current queue-weighted cost. For commodity (c, ϕ), define the cost of valid mapping k under the current virtual queues as X X (c,ϕ) e uv (t)M(c,ϕ) + e u (t)M(c,ϕ) . Ψt (k) ≜ Q Q k,uv k,u u∈V

(u,v)∈E

Frame-Based Routing Policy

n

5.3

b u (n)M(c,ϕ) Q k,u

,

u∈V

store it, and assign all commodity-(c, ϕ) arrivals within the frame to it; (ii) choose the link activation by the max-weight rule X e uv (t)µuv (t)suv . s∗ (t) ∈ arg max Q (7) s∈A(σ(t)) (u,v)∈E

Under the primary interference model of Remark 1, (7) reduces to a maximum-weight matching over the currently ON links. b When F = 1, Q(n) equals the current virtual queue vector, so (6) reduces to the minimum-cost valid mapping under the current virtual queues. To solve (6) exactly, we apply DynVMP [12] to the augmented service DAG. Each function uses its qualified node set as the candidate set, while each auxiliary source or sink has a singleton candidate set. For dependency (Aϕ , B ϕ ), physical link (u, v) is ϕ ϕ b uv (n), and placing Aϕ at node u assigned weight ξ (A ,B ) Q Aϕ b incurs weight r Qu (n). A dependency whose endpoints are placed at the same node uses the empty path with zero cost. DynVMP solves this problem in O(|V ϕ |3 |V|2τ +3 ) time [12], where τ is the width of a tree decomposition for the undirected graph underlying the augmented service DAG. Thus, exact mapping is polynomial when the treewidth is bounded by a constant. For DCNC-DAG, using a frame length F > 1 further amortizes the mapping computation cost by reusing each computed mapping for subsequent arrivals of the same commodity within the frame. However, minimumcost valid mapping remains NP-hard for general service DAGs even without capacity constraints [14]. DCNC-DAGH reduces the cost of each mapping computation by replacing the exact solver with a queue-aware heuristic, as described in Section 5.4.

For F > 1, the following proposition holds under Assumption 3; for F = 1, the mapping uses current queue prices and no such assumption is required. The proposition bounds the resulting cost increase. Proposition 1 (Per-slot additive mapping gap). Fix F ≥ 1. For every commodity (c, ϕ), there exists a finite deterministic (c,ϕ) constant CF such that, for every frame n and every slot t ∈ Tn with A(c,ϕ) (t) > 0,   (c,ϕ) b(c,ϕ) ≤ A(c,ϕ) (t)Ψt kn

A(c,ϕ) (t)

min

(c,ϕ)

k: mk

∈M(c,ϕ)

(c,ϕ)

Ψt

(c,ϕ)

(k) + CF

.

The bound holds uniformly over all slots, queue states, and sample (c,ϕ) (c,ϕ) = 0 and CF = O(F − 1) for each paths. Moreover, C1 commodity. The complete proof is given in Appendix B. The next theorem shows that reusing a mapping for any fixed finite frame preserves strong stability of the virtual queues: the expected total backlog averaged over time remains finite for arrival rates in the interior of the capacity region. Theorem 2 (Virtual queue stability). Suppose Assumptions 1 and 2 hold and each A(c,ϕ) (t) has finite second moment. Fix F ≥ 1. If F > 1, additionally let Assumption 3 hold. Then π v,F makes all virtual link and node queues strongly stable for every arrival rate vector in int(ΓLP ): " # T −1 i h i X h X 1 X e e lim sup E Qu (t) < ∞. E Quv (t) + T →∞ T t=0 u∈V (u,v)∈E

The proof uses the standard quadratic Lyapunov comparison with a stationary randomized policy [33], as in UMW [8] and UCNC [7]. Proposition 1 contributes only a finite additive term to the drift and therefore changes the backlog bound without changing the negative backlog term that establishes strong stability. The complete proof is given in Appendix B. Each commodity requires at most one DynVMP call per frame. Increasing F reduces the frequency of mapping computation but may increase the additive mapping gap and virtual queue backlog bound. Under Assumptions 1– 3, the same analysis accommodates mapping prices with bounded staleness. Corollary 1 (Stale mapping prices). Suppose that (6) uses virtual queue lengths sampled at most d ≤ F slots before the beginning of each frame, where d is fixed. The sampled prices are then at most F + d − 1 slots old. Under bounded arrivals, virtual queue changes per slot are bounded, so the argument of Proposition 1 yields another finite additive mapping gap. This changes only the constant in the Lyapunov drift bound, and the conclusion of Theorem 2 remains valid.

7

5.4

Heuristic Valid Mapping Solver

DCNC-DAG-H sets F = 1 and replaces the exact cost minimization in (6) with a queue-aware heuristic. The virtual queue updates, max-weight link activation, and NTO scheduling are unchanged. The heuristic is inspired by RW-MaxMatch [34] and first selects execution nodes and then routes the resulting dependencies. It processes the service functions in a fixed topological order. For each function Aϕ , it selects the qualified node that minimizes the sum of its computation ϕ e u (t) and the shortest path costs from its already price rA Q placed predecessors, where dependency e assigns link (u, v) e uv (t). After all functions are placed, each the price ξ e Q dependency is routed on a minimum-cost path, while a colocated dependency uses the empty path. When all selected dependency endpoints are connected by such paths, the construction yields a valid mapping.

6

DYNAMIC C ONTROL OF THE P HYSICAL N ET-

WORK

This section describes the physical queueing system and request execution under DCNC-DAG and establishes physical queue rate stability and throughput optimality. 6.1

Physical Queueing System

The physical system follows the same valid mappings and link activations used by the virtual system, but its workloads are realized progressively as transmissions and computations are completed. Let Quv (t) and Qu (t) denote the unfinished transmission workload on link (u, v) and the unfinished computation workload at node u, respectively. Each physical workload queue includes the remaining workload currently in service. Transmission on activated links and computation at nodes are work-conserving and nonpreemptive. Waiting pools. Each computation node maintains a waiting pool to synchronize the inputs required by service functions mapped to that node. The pool consists of waiting components, each associated with a specific request and service function. A waiting component stores the input packets of its request until all inputs required by the corresponding function Aϕ have arrived. These packets are then consumed ϕ to form a processing job of workload rA , which enters (c,ϕ) Qu (t) at the mapped node u. Let Wu (t) denote the total number of packets stored in waiting components of commodity (c, ϕ) at node u. A processing job releases its outputs only after completion, and the outputs follow the paths prescribed by the request’s mapping. Hop grades and NTO. Let hop(x) denote the hop grade of a packet, processing job, or waiting component x. Each source packet has grade zero, and completing a link transmission increases the packet grade by one. A function execution also contributes one hop. If a processing job j is formed from the input packet set Bj , then hop(j) = maxb∈Bj hop(b), and each output packet b′ of j has grade hop(b′ ) = hop(j) + 1. Transmissions along empty paths do not change the grade. An incomplete waiting component takes the grade of the processing job it will form. Given the request’s valid mapping, these recursive rules

uniquely determine the grade of each object throughout its execution, and grades remain unchanged while objects wait or receive service. Because service DAGs are finite and mapped paths are simple, all hop grades are bounded. Whenever an activated link or computation node is ready to start a new service, NTO scheduling [13] selects an eligible packet or processing job with the smallest grade. Service is nonpreemptive, so the selected packet or job remains in service until completion; consequently, at most one partially served packet or job remains at each link or node across a slot boundary. At the beginning of slot t, newly arrived requests and any packets or jobs released at the end of slot t − 1 become eligible for service. Transfers over empty paths are resolved before service begins. Activated links and computation nodes serve eligible packets and processing jobs under NTO, subject to their capacities in slot t. Successors generated by service completions during slot t are released at the end of the slot and become eligible in slot t + 1. Algorithm 1 presents the DCNC-DAG algorithm. Mapping computation and reuse follow Section 5.2. Setting F = 1 and replacing the exact mapping solver with the heuristic of Section 5.4 yields DCNC-DAG-H. Algorithm 1 DCNC-DAG 1: Initialize all virtual queues, physical queues, and waiting pools to zero. 2: for each slot t do 3: Let n = ⌊t/F ⌋. 4: Valid mapping. For each commodity (c, ϕ) with bn(c,ϕ) from (6) if no mapping A(c,ϕ) (t) > 0, compute k is stored for frame n; otherwise reuse the stored mapping. Assign the arriving requests accordingly, form the virtual queue arrivals, and generate the source packets. 5: Link activation. Select s∗ (t) according to (7). 6: Physical scheduling. Serve eligible packets on link (u, v) with capacity µuv (t)s∗uv (t) and eligible processing jobs at node u with capacity µu , using nonpreemptive NTO. Successors released by completed service become eligible in slot t + 1. 7: Virtual queue update. Update the virtual queues according to (4)–(5) using the selected mappings and s∗ (t).

6.2

Physical Network Stability

Virtual workloads are charged at request arrival but realized progressively in the physical system, so virtual queue stability does not directly imply physical queue rate stability. We build on the NTO hop induction in [13] and the virtual to physical arguments in UMW [8] and UCNC [7], which control progressively released transmission and computation work by induction over hop grades. For service DAGs, the additional difficulty is that packets can remain in waiting components without contributing to a link or computation queue, and a missing input may itself depend on an incomplete upstream merge. Let Qhr (t) be the physical workload of grade h at resource r, let P Qh (t) = r Qhr (t), and let W h (t) count packets in waiting

8

components of grade h. Superscripts ≤ h and < h denote sums over the corresponding grades, and Hmax bounds all grades. The following lemma incorporates this synchronization backlog into the induction. Lemma 2 (Waiting pool bound). For every h < Hmax , one missing input of each nonempty waiting component of grade h + 1 can be traced backward within the same request to either an unfinished packet or processing job of grade at most h, or an upstream waiting component of grade at most h. The traces can be chosen so that the number terminating at any one such object is bounded by a constant independent of t. Consequently, for some finite ηw independent of t,
W h+1 (t) ≤ ηw 1 + Q≤h (t) + W ≤h (t) . The proof traces one missing input of each waiting component backward within the same request. If the packet has already been generated, an unfinished transmission on its prescribed path provides a lower grade object. Otherwise, the packet is an intermediate output, and the trace moves to the predecessor function that produces it. If the corresponding processing job has formed and remains unfinished, the trace stops at that job. Otherwise, it stops at the function’s nonempty waiting component or continues through one of its missing inputs. Each continuation moves to a predecessor function, so acyclicity and the availability of all source packets at admission guarantee termination. Because the trace never leaves the request and each request contains only a bounded number of waiting components and packets, only a bounded number of such traces can terminate at the same unfinished object. This recursive tracing bounds the waiting backlog at merge points, allowing the physical stability analysis to account for merge synchronization. Appendix C gives the complete argument. The next theorem establishes that, under NTO scheduling, both unfinished workloads and packets waiting for synchronization grow sublinearly with time, ensuring rate stability of the physical queues and waiting pools. Theorem 3 (Physical network rate stability). Fix F ≥ 1 and suppose Assumptions 1–3 hold. Under DCNC-DAG, for every Λ ∈ int(ΓLP ), with probability one,

Quv (t) = 0 ∀(u, v) ∈ E, t Qu (t) = 0 ∀u ∈ V, lim t→∞ t (c,ϕ) Wu (t) lim = 0 ∀u ∈ V, (c, ϕ) ∈ K. t→∞ t lim

t→∞

Appendix C first obtains almost sure rate stability of the virtual queues and then applies the standard interval workload and NTO busy period arguments to bound physical work of each grade. The physical queue arrival bound accounts for unfinished work and waiting packets present at the beginning of an interval, while Lemma 2 bounds the waiting backlog at the next hop grade. Alternating these two bounds over the finitely many hop grades establishes Theorem 3.

Corollary 2 (Throughput optimality). Under the conditions of Theorem 3, let I(t) be the number of admitted but incomplete I(t) requests. Then, with probability one, limt→∞ t = 0 and

κ(c,ϕ) (t) = λ(c,ϕ) t→∞ t for every commodity. Hence, for every fixed F , DCNC-DAG supports every arrival rate vector in int(ΓLP ) and is throughputoptimal. lim

The complete proof is given in Appendix C.5. Although ΓLP contains no explicit synchronization constraints, Corollary 2 shows that every arrival rate vector in its interior is achievable while the waiting backlog at every node remains rate stable. Thus synchronization does not shrink the achievable capacity region. The proof relies on NTO’s priority for smaller hop grades. Section 7.4.2 illustrates its effect on a re-entrant instance, where NTO keeps the backlog of incomplete requests small while FIFO exhibits sustained backlog growth under identical arrivals, implying instability.

7

S IMULATION R ESULTS

We compare completed throughput with the LP capacity boundary, evaluate queue-aware mapping across wireless topologies and larger service DAGs, and examine the effects of frame length and scheduling. The simulation code and experimental data are publicly available.1 7.1

Simulation Setup

Networks, service DAGs, and traffic. Table 2 lists the four wireless network topologies. Node and link capacities are drawn independently and uniformly from {2, . . . , 10} and then fixed. Each undirected link gives two directed arcs. Dynamic arcs are independently ON with probability 0.8 in each slot and direction; all others remain ON. The wireless experiments use primary interference. Compared policies share the same arrival and wireless sample paths. The LP capacity boundary experiment uses bounded arrivals, whereas the mapping policy and frame length experiments use Poisson arrivals. Appendix D provides the remaining simulation configurations. TABLE 2 Wireless network topologies used in the experiments.

Topology |V| Links Milan [35] 30 35 Random 50 50 RoofNet [36] 38 131 FlockLab [37] 26 171

Qualified Dynamic nodes links 11 4 16 6 10 35 10 66

Link counts are undirected. The numbers of qualified nodes refer to the three random service DAG experiments; candidate sets for other experiments are specified in Appendix D.

Compared policies. We compare DCNC-DAG with F = 1 unless stated otherwise, DCNC-DAG-H, Closest-to-Source (CTS), and Randomized. CTS processes functions in topological order and places each function at a qualified node 1. https://github.com/Peng0802490/dcnc-dag-reproducibility/ releases/tag/v0.1.1

9

minimizing the sum of hop distances from its already placed predecessors; each dependency then follows a shortest path. Randomized first selects a qualified computation node for each service function uniformly at random, and then routes each dependency along a shortest path between the selected nodes. These policies use the same admission, link activation, and NTO scheduling and differ only in the valid mapping computation rule. The MoE experiments on larger service DAGs use two additional placement baselines defined in Section 7.3.2. Performance metrics. We measure request completion delay from arrival until all sink outputs are delivered and average it over completed requests. The empirical supported rate λ̂ is the largest tested rate for which the mean completion ratio across simulation seeds is at least 0.95. For each simulation seed, the completion ratio is the total number of completed requests divided by the total number of arrived requests across all commodities over the simulation horizon. This criterion may accept slightly overloaded rates. Conversely, requests that remain incomplete at time T reduce the completion ratio and may lower λ̂. Thus, λ̂ is an empirical measure subject to rate-grid and finite-horizon effects, and is a proxy for the stability boundary.

ρ 0.95 0.98 0.99 1.01 1.03 1.05 1.10

λout 0.950 0.980 0.990 1.000 1.000 1.000 1.000

Comp. ratio 1.000 1.000 1.000 0.990 0.970 0.952 0.909

Share m1 0.507 0.504 0.502 0.500 0.500 0.500 0.500

λout denotes completed throughput, and Share m1 denotes the fraction of arrivals assigned to m1 . Values are means over five seeds; all standard errors are below 5 × 10−4 .

respectively, compared with 0.30 and 0.19 for the better queue-blind baseline. DCNC-DAG-H reaches 0.73 and 0.43, which are approximately 88% and 84% of the corresponding values achieved by DCNC-DAG. The delay differences therefore reflect mapping decisions: DCNC-DAG and DCNC-DAG-H use virtual queue length information to avoid congested resources, whereas CTS and Randomized do not.

We first compare completed throughput with the LP capacity boundary on a wireless fork-join instance for which all valid mappings and wireless states can be enumerated. Instance and LP boundary. The service DAG is Aϕ → ϕ B , Aϕ → C ϕ , B ϕ → Dϕ , C ϕ → Dϕ , so the job at Dϕ must synchronize the two branches. Function C ϕ has unit computation workload and may execute at either of two nodes with capacity 0.5, while the remaining functions have fixed execution nodes and do not constrain the capacity boundary. Hence there are exactly two valid mappings, m1 and m2 , according to the placement of C ϕ . Either mapping alone supports at most 0.5 requests per slot. Enumerating both mappings, all 24 wireless states, and all feasible activations gives λ⋆ = 1, attained only by fm1 = fm2 = 0.5. Appendix D gives the complete instance configuration. Results. Table 3 reports DCNC-DAG over 105 slots. Below the LP boundary, completed throughput closely follows the offered rate. Above the boundary, completed throughput saturates at 1 and the completion ratio decreases. Restricting the policy to a single mapping limits completed throughput to 0.5 requests per slot. These results show that completed throughput remains consistent with the LP capacity boundary despite synchronization at the merge and that achieving the boundary requires a convex combination of valid mappings, implemented by assigning half of the requests to each mapping in the long run. 7.3

Performance of DCNC-DAG and DCNC-DAG-H

7.3.1

Comparison With Queue-Blind Mapping Policies

Autonomous driving service DAG. Fig. 2 evaluates the autonomous driving service DAG of Fig. 1 on the Milan and Random topologies under the wireless mapping configuration with a simulation horizon of 2 × 104 slots. DCNCDAG achieves empirical supported rates of 0.83 and 0.52,

DCNC-DAG (F=1) CTS

Randomized DCNC-DAG-H

8000 6000 4000 2000 0 0.00

0.25

0.50

0.75

Arrival rate

1.00

(a) Milan topology.

Avg. completion delay (slots)

Comparison With the LP Capacity Boundary Avg. completion delay (slots)

7.2

TABLE 3 Completed throughput and realized mapping share on the fork-join instance with LP capacity boundary λ⋆ = 1. The offered arrival rate is ρ requests/slot.

DCNC-DAG (F=1) CTS

Randomized DCNC-DAG-H

8000 6000 4000 2000 0 0.0

0.2

0.4

Arrival rate

0.6

(b) Random topology.

Fig. 2. Completion delay for the autonomous driving service DAG.

Random service DAGs and wireless topologies. Table 4 and Fig. 3 evaluate three six-function service DAGs across all four topologies. DCNC-DAG achieves empirical supported rates 2.7×–5.5× those of the better queue-blind baseline. DCNC-DAG-H achieves approximately 68% and 86% of the corresponding DCNC-DAG values on Milan and the Random topology, while the two queue-aware policies are closer on the denser topologies. These results show the benefit of queue-aware mapping and the additional gain from exact cost minimization, particularly when path diversity is limited. TABLE 4 Empirical supported rates λ̂ (requests/slot) for three random service DAGs across the four wireless topologies. Topology Milan Random RoofNet FlockLab

DCNC-DAG 1.22 0.65 1.97 3.43

Better queue-blind policy 0.46 0.15 0.47 0.62

4000 2000 0 0.0

0.5

1.0

1.5

Arrival rate

6000 4000 2000 0 0.00

DCNC-DAG (F=1) CTS

Randomized DCNC-DAG-H

6000

4000

2000

0

0

1

Arrival rate

0.50

0.75

Arrival rate

1.00

(b) Random topology.

2

(c) RoofNet topology.

Avg. completion delay (slots)

Avg. completion delay (slots)

(a) Milan topology.

0.25

DCNC-DAG (F=1) CTS

Randomized DCNC-DAG-H

6000 4000

shows the corresponding delay curves. Appendix D gives the workload construction, candidate sets, and simulation configuration. Scientific data analytics workflows. SRA-Search-22 and SIPHT-31 are bioinformatics workflows based on published WfCommons/Pegasus instances [42]. These workflows provide larger DAGs with branching and merging dependencies for evaluating DCNC-DAG-H. Table 5 shows that DCNC-DAG-H achieves an empirical supported rate 1.27× that of the better queue-blind baseline on SRA-Search22. On SIPHT-31, DCNC-DAG-H and CTS both support 0.30 requests per slot. Fig. 4(c)–(d) compares their request completion delays. At λ = 0.30 on SIPHT-31, the mean completed-request delay is 510.30 slots for DCNC-DAGH and 1098.67 slots for CTS, a reduction of approximately 53.6%. Appendix D gives the network, workload conversion, and simulation configuration.

2000 0

0

1

2

3

Arrival rate

4

(d) FlockLab topology.

Fig. 3. Completion delay for three random service DAGs across the four wireless topologies.

7.3.2 Performance of DCNC-DAG-H on Large Service DAGs The following experiments evaluate DCNC-DAG-H on MoE and workflow service DAGs with 20–31 functions. The MoE experiments use the Milan topology, while the workflow experiments use the Random topology. Table 5 summarizes the corresponding empirical supported rates. TABLE 5 Empirical supported rates λ̂ for the large service DAGs. Setting DCNC-DAG-H Lazarus FlexMoE Gain Skewed MoE service DAGs MoE Mixtral 1.16 0.38 0.44 2.64× MoE Llama 1.02 0.30 0.38 2.68× Setting DCNC-DAG-H CTS Randomized Gain Workflow service DAGs SRA-Search-22 0.14 0.11 0.03 1.27× SIPHT-31 0.30 0.30 0.07 1.00×

DCNC-DAG-H Lazarus-inspired

FlexMoE-inspired

4000

2000

0 0.00

×10

0.25

0.50

0.75

Arrival rate

1.00

Avg. completion delay (slots)

6000

Randomized DCNC-DAG-H

DCNC-DAG-H Lazarus-inspired

FlexMoE-inspired

2000

1000

0 0.00

0.25

0.50

0.75

Arrival rate

(a) Mixtral-skewed.

(b) Llama-skewed.

DCNC-DAG-H CTS

DCNC-DAG-H CTS

4

Randomized

1.5 1.0 0.5 0.0 0.00

0.05

0.10

Arrival rate

0.15

Avg. completion delay (slots)

8000

DCNC-DAG (F=1) CTS

Avg. completion delay (slots)

Randomized DCNC-DAG-H

Avg. completion delay (slots)

DCNC-DAG (F=1) CTS

Avg. completion delay (slots)

Avg. completion delay (slots)

10

1.00

Randomized

6000 4000 2000 0 0.0

(c) SRA-Search-22.

0.1

0.2

Arrival rate

0.3

(d) SIPHT-31.

Fig. 4. Completion delay for the skewed MoE and workflow-derived service DAGs.

Gain is relative to the better baseline in each row. Lazarus and FlexMoE denote the corresponding inspired placement rules used in the MoE experiments.

7.4

MoE service DAGs. Each expert family is modeled as one service function with several qualified GPU locations, and each request executes the function once. The workloads are derived from representative Mixtral 8×7B [38] and Llama4-Maverick [39] operator magnitudes with skewed expert demand. The qualified computation nodes in the Milan topology are treated as edge servers equipped with GPUs. The Lazarus-inspired baseline [40] selects the qualified GPU with the smallest physical backlog, while the FlexMoEinspired baseline [41] uses a fixed rotating order; after placement, both use the same minimum-cost dependency routing rule and NTO scheduling as DCNC-DAG-H. Table 5 shows that DCNC-DAG-H achieves empirical supported rates 2.64× and 2.68× those of the better MoE-inspired baseline for Mixtral and Llama, respectively. Fig. 4(a)–(b)

7.4.1 Effect of the Frame Length F We vary F ∈ {1, 4, 16, 64, 256} for DCNC-DAG with exact mappings on the autonomous driving service DAG, using the Milan and Random topologies considered in Section 7.3.1. Appendix D gives the simulation configuration and common rate grids. Table 6 reports the empirical supported rate λ̂ and exact mapping overhead, and Fig. 5 reports the corresponding delay curves. As F increases from 1 to 256, the number of exact mapping calls per commodity decreases by 98.9% on Milan and 98.5% on the Random topology, while the amortized mapping computation time per slot decreases by 98.8% and 98.1%, respectively. Since any fixed finite F preserves throughput optimality, increasing the frame length does not change the supported throughput region. The measured

Frame Length and Scheduling

11

TABLE 6 Effect of frame length on the empirical supported rate and exact mapping overhead. Random

F

λ̂

Map. calls

Map. time/ slot (s)

λ̂

Map. calls

Map. time/ slot (s)

1 4 16 64 256

0.89 0.89 0.89 0.84 0.78

36302.9 18365.0 5944.1 1562.5 391.0

2.825 1.626 0.528 0.139 0.0349

0.55 0.55 0.55 0.55 0.48

25432.3 16273.9 5931.1 1562.5 391.0

11.028 7.254 2.991 0.852 0.209

1.5

4

F=256

3 2 1 0 0.00

0.25

0.50

0.75

Arrival rate

(a) Milan topology.

1.00

Avg. completion delay (slots)

Avg. completion delay (slots)

×10

F=16 F=64

×10

4

F=1 F=4

F=16 F=64

20 0 0

5

10

1.0

0.5

NTO FIFO

0.0

λ̂ uses the threshold/delay rate grids. Map. calls is the number of exact mapping invocations per commodity over 105 slots; Map. time/slot is their cumulative wall-clock time divided by that horizon. Both overhead measures are averaged over three seeds on separate five-point rate grids (Appendix D.2).

F=1 F=4

40 I(t)

Incomplete requests I(t) (×106)

Milan

NTO (zoom)

2.0

0

2

4

6

8

10

Time t (×106 slots)

Fig. 6. Backlog of incomplete requests under NTO and FIFO on the re-entrant line at λ = 0.80 < λ⋆ . Curves are means over ten seeds; shading gives 95% confidence intervals of the mean; the inset enlarges NTO.

F=256

2

8

1

0 0.0

0.2

0.4

Arrival rate

0.6

(b) Random topology.

Fig. 5. Completion delay for F ∈ {1, 4, 16, 64, 256} on the autonomous driving service DAG. Curves show means over three seeds; shaded bands indicate one standard error and are visually subtle due to their narrow widths.

λ̂ differs slightly across frame lengths, primarily due to finite-horizon effects. Completion delay increases with F , particularly at high offered rates. Thus, frame reuse reduces mapping computation at the cost of increased completion delay, without changing the supported throughput region. 7.4.2 Comparison of FIFO and NTO Scheduling Re-entrant instance and configuration. To examine the role of NTO, we embed the classical re-entrant line with two stations [43] as a six-function service chain on two computation nodes, each with unit capacity. The per-request computation loads are 1.00 at u1 and 1.02 at v1 , so λ⋆ = 1/1.02 ≈ 0.9804. We use Bernoulli arrivals at λ = 0.80, start empty, and compare FIFO with NTO under identical arrivals, mappings, capacities, and nonpreemptive work-conserving service; only the service order differs. Results and scope. Fig. 6 shows the backlog I(t) of incomplete requests. NTO keeps it on the order of tens of requests, whereas FIFO accumulates about 1.9 × 106 by 107 slots despite λ < λ⋆ ; the inset enlarges the NTO trajectory. Thus, scheduling can lead to large differences in incomplete request backlog over the simulated horizon in this re-entrant system.

C ONCLUSION

We characterize the capacity region of wireless distributed computing networks serving service DAGs through the valid mapping abstraction and show, through the waiting pool analysis, that merge synchronization does not shrink this capacity region. We develop DCNC-DAG and prove that, with exact mappings and bounded arrivals, it is throughput-optimal for every fixed frame length, including when mapping prices are boundedly stale. We also develop DCNC-DAG-H, which applies queue-aware mapping to larger workflow and AI service DAGs. Our experiments show consistency with the LP boundary, demonstrate gains over queue-blind and domain-specific baselines, quantify the tradeoff between mapping computation and delay under frame reuse, and illustrate the effect of scheduling on re-entrant execution.

A PPENDIX A C APACITY R EGION C HARACTERIZATION A.1

Valid Mapping Decomposition

Proof of Lemma 1. Fix a completed request q of commodity (c, ϕ). Let Lquv and Lqu denote the communication and computation workloads of q served before completion. Since every service function is executed exactly once, the realized q execution defines a node map mV , with auxiliary sources and sinks mapped to their fixed network endpoints. Every valid mapping with this node map has the same node computation load Lqu . For each augmented dependency e, trace the copy of every required packet that is consumed by the downstream function or delivered to the auxiliary sink, and remove cycles from the resulting walk. This gives a simple path between the prescribed endpoints, or the empty path for q co-located endpoints. Let we,p be the workload assigned to path p. Then X X X q q we,p = ξe, we,p I{(u, v) ∈ p} ≤ Lquv . p

e∈Ē ϕ p

12

Select one path for each dependency with product weight q Y we,p e . ω q (p) = ξe ϕ e∈Ē

q

Together with mV , every tuple with positive weight q defines a valid mapping. Let θk be the resulting weight of mapping k . The weights sum to one and have path q marginals we,p /ξ e ; hence X q (c,ϕ) X q θk Mk,uv = we,p I{(u, v) ∈ p} ≤ Lquv , e,p

k

A PPENDIX B A DDITIVE M APPING G AP AND V IRTUAL Q UEUE S TABILITY Throughout this appendix, r indexes a link or computation (c,ϕ) node, and Mk,r denotes the corresponding mapping load.

B.1

Proof of Proposition 1

Proof. Let

X q (c,ϕ) θk Mk,u = Lqu .

(c,ϕ) Rmax = max k

k

The path reduction follows the efficient route idea used in UCNC [7]. The additional issue for service DAGs is that the path choices of different dependencies must remain consistent with the same function placements of a request; the product construction above preserves this consistency. A.2

Necessity of the LP Characterization

Proof of necessity in Theorem 1. Fix an admissible policy π that supports Λ, on a sample path where the support condition and the arrival and wireless state strong laws hold. The support condition and the arrival strong law imply that, for every commodity,

X

(c,ϕ)

Mk,r < ∞.

r

For F = 1, the mapping uses the current prices and the gap is zero. For F > 1, Assumption 3 and the virtual queue recursions give e r (t + 1) − Q e r (t) ≤ ∆max , Q X (c,ϕ) ∆max = A(c,ϕ) max Rmax + µmax , (c,ϕ)

where µmax is the largest node or link capacity. Thus, for t ∈ Tn , e r (t) − Q b r (n) ≤ GF , Q

GF = (F − 1)∆max .

(c,ϕ),π

(T ) = λ(c,ϕ) . T Define the empirical mapping rate for commodity (c, ϕ) by X 1 (c,ϕ) fk (T ) = θkq . T lim

κ

T →∞

(c,ϕ)

b n (k) denotes the mapping cost under the frame If Ψ head prices, then (c,ϕ)

Ψt

q of commodity (c,ϕ) completed by T

P (c,ϕ) Then limT →∞ k fk (T ) = λ(c,ϕ) . Summing Lemma 1 over completed requests and using the physical resource constraints gives T −1

X

(c,ϕ)

(T )Mk,uv ≤

(c,ϕ)

(T )Mk,u ≤ µu .

(c,ϕ),k

X

fk

Applying the preceding bound to the stored mapping gives (c,ϕ)

Ψt



   b(c,ϕ) ≤ Ψ b(c,ϕ) b (c,ϕ) k k n n n

1 X µuv σuv (t)sπuv (t), T t=0

(c,ϕ)

fk

b (c,ϕ) (k) ≤ GF R(c,ϕ) . (k) − Ψ n max

(c,ϕ) + GF Rmax b (c,ϕ) (k) + GF R(c,ϕ) , = min Ψ k

(c,ϕ)

(c,ϕ),k

The empirical mapping rates and the joint frequencies of wireless states and activations are bounded, and there are finitely many of them. Hence, we can choose a common subsequence of time horizons along which they all (c,ϕ) converge. Let fk denote the limiting mapping rates. For each state σ with pσ > 0, let ασ,s denote the limiting fraction of those slots in which activation s is selected. Set ασ,s = 0 when pσ = 0. By the strong law, state σ occurs with limiting frequency pσ . Since exactly one feasible activation is selected in each slot, X ασ,s = 1, pσ > 0. s∈A(σ)

The resulting average link service vector belongs to C . Passing to the limit along the common subsequence gives all flow and resource constraints defining ΓLP . Hence Λ ∈ ΓLP , which proves the necessity direction.

n

max

where the equality follows from the optimality of the stored mapping under the frame-head prices. Applying the same bound to every valid mapping and taking the minimum gives (c,ϕ)

b (c,ϕ) (k) ≤ min Ψ min Ψ t n k

k

(c,ϕ) (k) + GF Rmax .

Combining the two bounds yields (c,ϕ)

Ψt

  b(c,ϕ) ≤ min Ψ(c,ϕ) (k) + 2GF R(c,ϕ) . k t n max k

(c,ϕ)

Multiplying by A(c,ϕ) (t) ≤ Amax proves Proposition 1 with (c,ϕ)

(c,ϕ) = 2A(c,ϕ) max GF Rmax .

(c,ϕ)

= 0 and CF

CF In particular, C1

(c,ϕ)

= O(F − 1).

13

B.2

Proof of Theorem 2

We use a quadratic Lyapunov drift argument, with Proposition 1 accounting for the additional cost of frame-based mapping. Let R+ be the resources used by at least one valid mapping, and write X (c,ϕ) (c,ϕ) loadr (f ) = fk Mk,r . (c,ϕ),k

Queues outside R+ receive no virtual arrivals and are nonincreasing. Uniform slack. For every Λ ∈ int(ΓLP ), there exist feasible mapping rates f , an average service vector c̄ ∈ C , and ϵ > 0 P (c,ϕ) such that k fk = λ(c,ϕ) and

loadr (f ) ≤ s̄r − ϵ,

r ∈ R+ ,

where s̄uv = c̄uv and s̄u = µu . Since Λ is an interior point, a slightly larger arrival rate vector is feasible. Scaling the corresponding mapping rates down creates positive slack on resources with nonzero load. By convexity of C , positive service can also be allocated to the remaining usable links without losing this slack. Since R+ is finite, a common ϵ > 0 exists. Condition on the history before the current arrivals and wireless state are revealed, and write Et [·] for the corresponding conditional expectation. Let X e 2 (t). L(t) = Q r r∈R+

Finite arrival second moments and bounded mapping loads give a finite drift constant B . A randomized map(c,ϕ) ping that selects k with probability fk /λ(c,ϕ) has mean resource load loadr (f ). Proposition 1 bounds the queueweighted arrival cost of the frame policy by that of this P (c,ϕ) comparison policy plus CFslot = , while max(c,ϕ) CF weight activation provides at least the queue-weighted link service of c̄. Therefore, Et [L(t + 1) − L(t)] ≤ B + 2CFslot X
e r (t) loadr (f ) − s̄r Q +2

Fix such a sample path and write π = π v,F . We use the hop grades and slot timing of Section 6.1. C.1

Notation and Virtual Interval Bound

For a link, define the cumulative service allocated over [t0 , t) by t−1 X π Cuv (t0 , t) ≜ µuv (τ )sπuv (τ ), τ =t0

eπ (t0 , t) be the and for a node let Cuπ (t0 , t) = µu (t − t0 ). Let A r cumulative virtual queue arrivals to resource r . The running maximum e r (s) M0 (t) ≜ max max Q 0≤s≤t

r

is o(t). Summing the virtual queue recursion gives, uniformly over 0 ≤ t0 ≤ t, eπ (t0 , t) ≤ C π (t0 , t) + Q e r (t) − Q e r (t0 ) A r r π ≤ Cr (t0 , t) + M0 (t).

(8)

Let Breq uniformly bound the total number of mapped packet transmissions, processing jobs, waiting components, and packets stored in waiting components of any one request. Such a bound exists because the commodity and valid mapping sets are finite. Each packet transmission has unit workload, and the finitely many positive function workloads are uniformly bounded above and away from zero. Thus, each unstarted packet transmission or processing job has a uniform positive workload lower bound. At any slot boundary, each link or computation node has at most one partially served object. Hence, for a finite constant ηN , the number N≤h (t) of packets with unfinished transmissions and unfinished processing jobs of grade at most h satisfies
N≤h (t) ≤ ηN 1 + Q≤h (t) , (9) and the same bound holds with strict grade inequalities. Since every nonempty waiting component contains at least one packet, the number of such components of grade at most h is bounded by W ≤h (t).

r∈R+

≤ B + 2CFslot − 2ϵ

X

e r (t). Q

r∈R+

Taking expectations and telescoping yields   T −1 B + 2CFslot E[L(0)] 1 X  X e E Qr (t) ≤ + . T t=0 2ϵ 2ϵT r∈R

C.2

Physical Arrival Bound

Let Ar,≤h (t0 , t) be the physical workload of grade at most h that becomes eligible at resource r during [t0 , t). The following bound is the counterpart of the virtual to physical workload step used in UMW [8] and UCNC [7], with the waiting term accounting for merge synchronization.

+

Hence the active virtual queues are strongly stable. This proves Theorem 2. □

Lemma 3 (Physical arrival bound). There exists a finite constant ηmax , independent of t0 , t, h, r, such that eπ (t0 , t) Ar,≤h (t0 , t) ≤ A r

A PPENDIX C P HYSICAL N ETWORK S TABILITY Under Assumption 3, virtual queue arrivals and service are bounded. Theorem 2 and the standard implication from strong stability to rate stability [8], [33] therefore give, with probability one, e r (t) Q =0 t→∞ t

lim

for all virtual resources r.

+ ηmax 1 + Q<h (t0 ) + W ≤h (t0 ) .

(10)

Proof. Partition the physical arrivals according to whether their requests were admitted during [t0 , t) or before t0 . For a request admitted during the interval, the virtual system charges the complete selected mapping at admission and the physical system executes that same mapping. Its physical work released at resource r is therefore bounded by the corresponding virtual workload.

14

Under bounded source delays, requests admitted before t0 but not yet released into the physical system at t0 contribute only a uniformly bounded amount of additional workload, which can be absorbed into ηmax . Now consider a grade g ≤ h item from a request released before t0 . Trace one prerequisite backward toward time t0 . Along a mapped route, move to the preceding transmission; before the first link, move to the predecessor function that produces the packet. If its processing job was present and unfinished at t0 , stop at that job. If the job had not formed, stop at the function’s waiting component when that component was nonempty at t0 , and otherwise continue through an input that was missing at t0 . Stop upon reaching a packet or processing job that was present and unfinished at t0 . The trace remains within the request and terminates because mapped routes are finite and the service DAG is acyclic. Except for a uniformly bounded boundary contribution, a terminal packet or processing job has grade strictly below g , whereas a terminal waiting component has grade at most g . Each terminal object belongs to one request, and that request contains at most Breq mapped work items at resource r, each with uniformly bounded workload. Thus the work generated by requests admitted before t0 is at most a constant times

N<h (t0 ) + W ≤h (t0 ) + 1.

are available before its physical execution begins. Move to the predecessor function that produces this packet. If its processing job has formed, the job must remain unfinished and has grade at most h, since output generation increases the grade by one. The trace then stops at that job. If the job has not formed, its waiting component has grade at most h. The trace stops if this component is nonempty; otherwise, it continues through one of the function’s missing inputs. Each continuation moves to a predecessor function, so acyclicity and the availability of source packets guarantee termination in one of the three cases. All traces remain within their originating requests. Since each terminal object belongs to one request, at most Breq waiting packets of grade h + 1 can be associated with it. Traces ending at unfinished packets or processing jobs account for at most Breq N≤h (t) waiting packets. Those ending at nonempty upstream waiting components account for at most Breq W ≤h (t) waiting packets, since each such component contains at least one packet. Using (9), we obtain
W h+1 (t) ≤ Breq N≤h (t) + W ≤h (t)   ≤ Breq ηN (1 + Q≤h (t)) + W ≤h (t)
≤ ηw 1 + Q≤h (t) + W ≤h (t) , where ηw = Breq max{1, ηN }. This proves Lemma 2.

Using (9) gives (10). C.4 C.3

Proof of Lemma 2

Proof of Theorem 3. Combining Lemma 3 with (8) gives

" 𝑆!

𝐴"

𝐶"

"

𝐵"

𝐸"

𝑆$

NTO Service and Hop Grade Induction

Ar,≤h (t0 , t) ≤ Crπ (t0 , t) + M0 (t)

missing input

𝐹" 𝐺"

𝐻"

𝐼"

"

𝐷#

+ ηmax 1 + Q<h (t0 ) + W ≤h (t0 ) .

(11)

Backward tracing

Start: nonempty waiting component 𝒳 at function 𝐻! (grade ℎ + 1) Select a missing input of the current function and check its packet status.

Continue tracing through a missing input of the upstream function.

No

Has the missing packet been generated?

Case 1: unfinished transmission

Yes

No

Has the upstream processing job formed?

Case 2: unfinished processing job

Yes

No

Is the upstream waiting component nonempty?

Yes

Case 3: upstream nonempty waiting component

Fix r, h, t with Q≤h r (t) > 0, and let θ be the beginning of the slot containing the last instant before t at which this workload was empty, taking θ = 0 if necessary. Thereafter, NTO starts no object of grade greater than h while work of grade at most h is waiting. At most one higher grade object can already be in service; its residual workload together with the boundary slot discrepancy is bounded by a constant br . Queue accounting and (11) therefore give

Q≤h r (t) ≤ M0 (t) + br Fig. 7. Backward tracing in the proof of Lemma 2. Starting from a nonempty waiting component X of grade h+1, the trace follows missing inputs through predecessor functions within the same request until reaching one of the three terminal cases, each of grade at most h.

Proof. We first associate each nonempty waiting component of grade h + 1 with an unfinished packet, an unfinished processing job, or a nonempty upstream waiting component of grade at most h (Fig. 7). We then bound the number of waiting packets associated with each such object. Consider a nonempty waiting component X of grade h + 1, and select one of its missing input packets. If the corresponding packet has been generated, then at least one transmission on its remaining mapped path is unfinished. The packet therefore has grade at most h. If the packet has not been generated, it must be an intermediate output, since all source packets of the request

+ ηmax 1 + Q<h (θ) + W ≤h (θ) .

(12)

The same inequality is immediate when Q≤h r (t) = 0. All source packets of a request are released together into the physical system, and empty paths are resolved before service, so W 0 (t) = 0. With Q<0 (t) = 0, (12) gives Q0 (t) = o(t), and Lemma 2 gives W 1 (t) = o(t). Inductively, suppose Q<h (t) = o(t) and W ≤h (t) = o(t). Their running maximum is sublinear, so (12) gives Qh (t) = o(t); Lemma 2 then gives W h+1 (t) = o(t) whenever h < Hmax . Since there are finitely many grades and resources, all physical queues and waiting pools are rate stable on the fixed sample path, and hence almost surely. The same physical stability argument applies with boundedly stale mapping prices, since Corollary 1 preserves virtual queue stability.

15

C.5

Proof of Corollary 2

Proof. Every incomplete request has an unfinished packet or processing job, or a packet in a waiting component. The preceding bounds imply that the number I(t) of incomplete requests is bounded by a constant multiple of the total unfinished physical workload and the number of packets in waiting components, plus a constant. Theorem 3 therefore implies I(t) = o(t). For each commodity, the difference between the cumulative numbers of admitted and completed requests is at most I(t) = o(t). Dividing by t and applying the arrival strong law gives

κ(c,ϕ) (t) = λ(c,ϕ) t→∞ t lim

Tables 7 and 8 specify the wireless instances and workloads under the common capacity and channel model of Section 7.1. Source and sink nodes, qualified node sets, and dynamic links are fixed for each instance and shared by all compared policies. Within each commodity, raw inputs share one source node and sink outputs share one destination node, except for the autonomous driving DAG on the Random topology, which uses two source nodes. TABLE 7 Wireless network simulation instances. Dynamic Qualified nodes links 11 4 8 per function 6 11 4 16 6 10 35 10 66

Network sizes are given in Table 2. Qualified node sets are common to all functions except for autonomous driving on the Random topology. Dynamic link counts are undirected. On RoofNet and FlockLab, all links incident to commodity endpoints are dynamic.

D.2

TABLE 9 Simulation configurations used in Section 7. Experiment LP boundary

MoE DAGs

Wireless Networks and Workloads

Service DAGs Autonomous driving Autonomous driving D 1 , D2 , D3 D1 , D2 , D3 D 1 , D2 , D3 D1 , D2 , D3

Letters denote service functions in the autonomous driving DAG; s1 , . . . , s6 denote those in D1 , D2 , D3 , in the order used for r .

Wireless mapping Workflow DAGs

A PPENDIX D S IMULATION C ONFIGURATION

Network Milan Random Milan Random RoofNet FlockLab

Autonomous driving r : A 2, B 2, C 1, E 3, F 1.5, G 1.5, H 2; in/out: A 1.5, B 2, C 0.5/F 1, H 1; ξ : A → E 1.5, B → E 1.5, B → F 1.5, C → F 0.5, E → G 2, G → H 1, F → H 1 D1 r = (2, 5, 1, 3, 4, 2); in/out: s1 4/s6 5; ξ : s1 → s2 3, s1 → s3 5, s2 → s4 2, s3 → s4 4, s3 → s5 1, s4 → s6 5, s5 → s6 2 D2 r = (4, 1, 5, 2, 3, 4); in/out: s1 2, s2 3/s6 1; ξ : s1 → s3 2, s2 → s3 4, s1 → s4 5, s3 → s5 1, s4 → s5 3, s3 → s6 2, s5 → s6 5 D3 r = (5, 2, 4, 1, 3, 5); in/out: s1 1/s5 4, s6 2; ξ : s1 → s2 4, s1 → s3 1, s2 → s4 3, s3 → s4 5, s2 → s5 2, s4 → s5 4, s4 → s6 1

w.p. 1.

Thus every vector in int(ΓLP ) is supportable. Together with Appendix A, this completes the proof of Theorem 1.

D.1

TABLE 8 Workloads for the service DAGs.

Simulation Configurations

LP capacity-boundary instance. The fork-join DAG of Secϕ ϕ ϕ ϕ tion 7.2 has rA = rB = rD = 0.1, rC = 1, dependency workloads 1 on the C branch and 0.2 on the B branch, and input/output workload 0.2. Functions A, B, D are pinned to nodes uA , uB , uD , while C may execute at uC1 or uC2 . The two candidate nodes have capacity 0.5; the other three computation nodes have capacity 5. All links have capacity 2; the four links on the C branch are independently ON with probability 0.85, and the others remain ON under primary interference. Removing the computation

Frame length FIFO / NTO

Run configuration bounded i.i.d.; 105 slots; seeds {0, 1, 2, 3, 4} Poisson; 2 × 104 slots; seeds {1, 2, 3} Poisson; 5 × 104 slots; seeds {0, 1, 2} Poisson; 105 slots; seeds {0, 1, 2} Poisson; 105 slots; seeds {1, 2, 3} Bernoulli; 107 slots; ten seeds

Main configuration F = 1; offered multipliers ρ ∈ {0.95, 0.98, 0.99, 1.01, 1.03, 1.05, 1.10} policy-specific rate grids workflow rate grids refined near λ̂ MoE rate grids refined near λ̂ F ∈ {1, 4, 16, 64, 256}; common grid within each topology λ = 0.80, empty start; same arrivals, mapping, and capacities; service order differs

constraints gives wireless capacity about 1.43. Arrivals are ⌊λ⌋ + Bernoulli(λ − ⌊λ⌋). Frame-length threshold and delay. The 105 -slot runs use the following offered-rate grids for the empirical supported rates in Table 6 and the delay curves in Fig. 5: Milan: {0.049, 0.1176, 0.2058, 0.3038,

0.4116, 0.5194, 0.6174, 0.7056, 0.784, 0.8428, 0.8918, 0.931, 0.9702, 1.0094, 1.0584, 1.1074}, Random: {0.03, 0.072, 0.126, 0.186, 0.252, 0.318, 0.378, 0.432, 0.48, 0.516, 0.546, 0.57, 0.594, 0.618, 0.648, 0.678}. Fig. 5 shows the completed-request delay curves over the full rate grids for every frame length; the supported-rate estimates use these same grids. Frame-length mapping overhead. Calls and wall-clock timing use separate five-point rate grids: {0.1, 0.2, 0.5, 0.8, 0.9} on Milan and {0.1, 0.2, 0.3, 0.42, 0.5} on Random. Timing was measured on an AMD EPYC 7763 server. FIFO/NTO instance. The six functions visit two unitcapacity nodes u1 and v1 . The first and last functions execute at u1 with workloads 0.01 and 0.99; the four intermediate functions execute at v1 with workloads 0.99, 0.01, 0.01, 0.01. All links are always ON and have sufficiently large capacities so that they do not limit throughput. The perrequest loads are 1.00 at u1 and 1.02 at v1 , giving λ⋆ = min{1/1.00, 1/1.02} = 1/1.02 ≈ 0.9804. We use Bernoulli

16

arrivals with λ = 0.80, start from an empty system, and simulate 107 slots over ten seeds. For each seed, FIFO and NTO use the same arrival sample path. FIFO orders jobs by their arrival time at the current node, including returning jobs, whereas NTO serves the smallest hop grade first. Exact mappings were computed by dynamic programming, and the state-averaged LP was verified using SciPy/HiGHS. D.3

Large Service DAG Configuration

The MoE workloads are synthetic models based on operator magnitudes, whereas the workflow DAGs are derived from published application instances. TABLE 10 MoE and workflow configurations used in Section 7.3.2. MoE serving Service DAG

Mixtral: 20 functions, 27 dependencies; Llama: 25 functions, 34 dependencies Operators Mixtral 8×7B: attention ≈ 2.2 TFLOPs, each expert ≈ 1.45 TFLOPs, edges ≈ 64 MB; Llama-4-Maverick: attention ≈ 2.4 TFLOPs, dense feedforward ≈ 1.4 TFLOPs, each expert ≈ 0.7 TFLOPs, edges 64–128 MB; FP32, 8K-token inputs Weights attention 1.25γ ; expert (0.55 + 3.25wk )γ ; merge 0.28γ , with γ = 2.00 (Mixtral) and γ = 1.84 (Llama) Network Milan (30, 35); its 11 qualified computation nodes are treated as edge servers equipped with GPUs and are qualified for all service functions Wireless Same Milan wireless model as in Section 7.1 Tenants two tenants with distinct fixed source and sink pairs; aggregate rate split 0.60/0.40; expert-family demand skew 0.70/0.18/0.12, with different families hot Workflow service DAGs SRA-Search-22 22 functions, 30 dependencies; WfCommons chameleon-10a SIPHT-31 31 functions, 34 dependencies; Pegasus SIPHT Network Random (50, 50); all 50 nodes qualified for every function Workloads published execution costs and data sizes converted to rational computation and communication workloads

The computation requirements are proportional to the operator magnitudes in Table 10 and are used without integer rounding. Here, k ∈ {A, B, C} indexes the three expert families, wk is the fixed tenant-specific token share of family k , and γ is the dimensionless model scale. In family order (A, B, C), the code and chat tenants use (0.70, 0.18, 0.12) and (0.18, 0.70, 0.12) for Mixtral, and (0.12, 0.70, 0.18) and (0.12, 0.18, 0.70) for Llama, respectively. These shares sum to one and are used without further normalization; they also determine the workloads of the corresponding expert branches. Attention includes query, key, value, and output projections; expert costs assume uniform token splitting among activated experts. The placement rules in Section 7.3.2 share the same DAGs, capacities, candidate sets, tenant arrivals, routing, and physical scheduling configuration.

R EFERENCES [1]

Y. Liu, W. Chen, Y. Bai, X. Liang, G. Li, W. Gao, and L. Lin, “Aligning cyber space with physical world: A comprehensive survey on embodied AI,” IEEE/ASME Trans. Mechatron., vol. 30, no. 6, pp. 7253–7274, 2025.

[2]

E. Yurtsever, J. Lambert, A. Carballo, and K. Takeda, “A survey of autonomous driving: Common practices and emerging technologies,” IEEE Access, vol. 8, pp. 58 443–58 469, 2020. [3] R. Zhu, Z. Jiang, C. Jin, P. Wu, C. A. Stuardo, D. Wang, X. Zhang, H. Zhou, H. Wei, Y. Cheng, J. Xiao, X. Zhang, L. Liu, H. Lin, L.-W. Chang, J. Ye, X. Yu, X. Liu, X. Jin, and X. Liu, “MegaScale-Infer: Efficient mixture-of-experts model serving with disaggregated expert parallelism,” in Proc. ACM SIGCOMM Conf., 2025, pp. 592– 608. [4] X.-P. Nguyen, S. Pandit, A. Xu, C. Xiong, and S. Joty, “Leastloaded expert parallelism: Load balancing an imbalanced mixtureof-experts,” in Proc. Int. Conf. Mach. Learn. (ICML), ser. Proc. Mach. Learn. Res., vol. 306, 2026, pp. 92 659–92 673. [5] H. Feng, J. Llorca, A. M. Tulino, and A. F. Molisch, “Dynamic network service optimization in distributed cloud networks,” in Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM) Workshops, 2016, pp. 300–305. [6] ——, “Optimal dynamic cloud network control,” IEEE/ACM Trans. Netw., vol. 26, no. 5, pp. 2118–2131, 2018. [7] J. Zhang, A. Sinha, J. Llorca, A. M. Tulino, and E. Modiano, “Optimal control of distributed computing networks with mixedcast traffic flows,” IEEE/ACM Trans. Netw., vol. 29, no. 4, pp. 1760– 1773, 2021. [8] A. Sinha and E. Modiano, “Optimal control for generalized network-flow problems,” IEEE/ACM Trans. Netw., vol. 26, no. 1, pp. 506–519, 2018. [9] R. Pedarsani, J. Walrand, and Y. Zhong, “Scheduling tasks with precedence constraints on multiple servers,” in Proc. 52nd Annu. Allerton Conf. Commun., Control, Comput., 2014, pp. 1196–1203. [10] J. G. Dai and W. Lin, “Maximum pressure policies in stochastic processing networks,” Operations Research, vol. 53, no. 2, pp. 197– 218, 2005. [11] F. Baccelli, W. A. Massey, and D. Towsley, “Acyclic fork-join queuing networks,” J. ACM, vol. 36, no. 3, pp. 615–642, 1989. [12] M. Rost, E. Döhne, and S. Schmid, “Parametrized complexity of virtual network embeddings: Dynamic & linear programming approximations,” ACM SIGCOMM Comput. Commun. Rev., vol. 49, no. 1, pp. 3–10, 2019. [13] D. Gamarnik, “Stability of adaptive and non-adaptive packet routing policies in adversarial queueing networks,” in Proc. ACM Symp. Theory Comput. (STOC), 1999, pp. 206–214. [14] M. Rost and S. Schmid, “On the hardness and inapproximability of virtual network embeddings,” IEEE/ACM Trans. Netw., vol. 28, no. 2, pp. 791–803, 2020. [15] Y. Kim, J. Kwak, H.-W. Lee, and S. Chong, “Dynamic computation and network chaining in integrated SDN/NFV cloud infrastructure,” IEEE Trans. Cloud Comput., vol. 11, no. 1, pp. 367–382, 2023. [16] C.-H. Wang, J. Llorca, A. M. Tulino, and T. Javidi, “Dynamic cloud network control under reconfiguration delay and cost,” IEEE/ACM Trans. Netw., vol. 27, no. 2, pp. 491–504, 2019. [17] Y. Cai, J. Llorca, A. M. Tulino, and A. F. Molisch, “Joint computecaching-communication control for online data-intensive service delivery,” IEEE Trans. Mobile Comput., vol. 23, no. 5, pp. 4617–4633, 2024. [18] C.-S. Yang, R. Pedarsani, and A. S. Avestimehr, “Communicationaware scheduling of serial tasks for dispersed computing,” IEEE/ACM Trans. Netw., vol. 27, no. 4, pp. 1330–1343, 2019. [19] Y. Zhang, “Resource scheduling and delay analysis for workflow in wireless small cloud,” IEEE Trans. Mobile Comput., vol. 17, no. 3, pp. 675–687, 2018. [20] X. Zhou, S. Ge, P. Liu, and T. Qiu, “DAG-based dependent tasks offloading in MEC-enabled IoT with soft cooperation,” IEEE Trans. Mobile Comput., vol. 23, no. 6, pp. 6908–6920, 2024. [21] X. Chen, J. Cao, Y. Sahni, M. Zhang, Z. Liang, and L. Yang, “Mobility-aware dependent task offloading in edge computing: A digital twin-assisted reinforcement learning approach,” IEEE Trans. Mobile Comput., vol. 24, no. 4, pp. 2979–2994, 2025. [22] A. Mauro, A. M. Tulino, and J. Llorca, “End-to-end orchestration of NextG media services over the distributed compute continuum,” IEEE Trans. Mobile Comput., vol. 25, no. 3, pp. 3068–3086, 2026. [23] X. Zhao, D. Hu, and B. Krishnamachari, “Design and experimental evaluation of algorithms for optimizing the throughput of dispersed computing,” J. Parallel Distrib. Comput., vol. 196, p. 104999, 2025. [24] Y. Hu, C. Zhang, E. Andert, H. Singh, A. Shrivastava, J. Laudon, Y. Zhou, B. Iannucci, and C. Joe-Wong, “GiPH: Generalizable

17

placement learning for adaptive heterogeneous computing,” in Proc. Mach. Learn. Syst. (MLSys), 2023, pp. 164–185. [25] H. Feng, J. Llorca, A. M. Tulino, and A. F. Molisch, “Optimal control of wireless computing networks,” IEEE Trans. Wireless Commun., vol. 17, no. 12, pp. 8283–8298, 2018. [26] F. Guo, H. Zhang, H. Ji, X. Li, and V. C. M. Leung, “An efficient computation offloading management scheme in the densely deployed small cell networks with mobile edge computing,” IEEE/ACM Trans. Netw., vol. 26, no. 6, pp. 2651–2664, 2018. [27] I. Cohen, C.-F. Chiasserini, P. Giaccone, and G. Scalosub, “Dynamic service provisioning in the edge-cloud continuum with bounded resources,” IEEE/ACM Trans. Netw., vol. 31, no. 6, pp. 3096–3111, 2023. [28] L. Ying and S. Shakkottai, “On throughput optimality with delayed network-state information,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5116–5132, 2011. [29] M. J. Neely, J. Sun, and E. Modiano, “Delay and complexity tradeoffs for dynamic routing and power allocation in a wireless network,” in Proc. Allerton Conf. Commun., Control, Comput., 2002. [30] M. J. Neely, “Dynamic optimization and learning for renewal systems,” IEEE Trans. Autom. Control, vol. 58, no. 1, pp. 32–46, 2013. [31] C.-H. Wang and T. Javidi, “Adaptive policies for scheduling with reconfiguration delay: An end-to-end solution for all-optical data centers,” IEEE/ACM Trans. Netw., vol. 25, no. 3, pp. 1555–1568, 2017. [32] A. Gopalan, C. Caramanis, and S. Shakkottai, “On the value of coordination and delayed queue information in multicellular scheduling,” IEEE Trans. Autom. Control, vol. 58, no. 6, pp. 1443– 1456, 2013. [33] M. J. Neely, Stochastic Network Optimization with Application to Communication and Queueing Systems, ser. Synthesis Lectures on Communication Networks. Morgan & Claypool, 2010. [34] X. Cheng, S. Su, Z. Zhang, H. Wang, F. Yang, Y. Luo, and J. Wang, “Virtual network embedding through topology-aware node ranking,” ACM SIGCOMM Comput. Commun. Rev., vol. 41, no. 2, pp. 38–47, 2011. [35] B. Xiang, J. Elias, F. Martignon, and E. Di Nitto, “A dataset for mobile edge computing network topologies,” Data in Brief, vol. 39, p. 107557, 2021. [36] J. Bicket, D. Aguayo, S. Biswas, and R. Morris, “Architecture and evaluation of an unplanned 802.11b mesh network,” in Proc. 11th Annu. Int. Conf. Mobile Comput. Netw. (MobiCom), 2005, pp. 31–42. [37] R. Jacob, R. Da Forno, R. Trüb, A. Biri, and L. Thiele, “Dataset: Wireless link quality estimation on FlockLab – and beyond,” in Proc. 2nd Workshop on Data Acquisition to Analysis (DATA), 2019, pp. 57–60. [38] A. Q. Jiang, A. Sablayrolles, A. Roux, A. Mensch, B. Savary, C. Bamford, D. S. Chaplot, D. de las Casas, E. Bou Hanna, F. Bressand, G. Lengyel, G. Bour, G. Lample, L. R. Lavaud, L. Saulnier, M.-A. Lachaux, P. Stock, S. Subramanian, S. Yang, S. Antoniak, T. Le Scao, T. Gervet, T. Lavril, T. Wang, T. Lacroix, and W. El Sayed, “Mixtral of experts,” arXiv preprint arXiv:2401.04088, 2024. [39] Meta AI, “Llama-4-Maverick-17B-128E-Instruct: Model Card,” https://huggingface.co/meta-llama/ Llama-4-Maverick-17B-128E-Instruct, Apr. 2025, accessed: 2026-07-16. [40] Y. Wu, W. Qu, T. Tao, Z. Wang, W. Bai, Z. Li, Y. Tian, J. Zhang, M. Lentz, and D. Zhuo, “Lazarus: Resilient and elastic training of mixture-of-experts models with adaptive expert placement,” arXiv preprint arXiv:2407.04656, 2024. [41] X. Nie, X. Miao, Z. Wang, Z. Yang, J. Xue, L. Ma, G. Cao, and B. Cui, “FlexMoE: Scaling large-scale sparse pre-trained model training via dynamic device placement,” Proc. ACM Manag. Data, vol. 1, no. 1, pp. 1–19, 2023. [42] T. Coleman, H. Casanova, L. Pottier, M. Kaushik, E. Deelman, and R. F. da Silva, “WfCommons: A framework for enabling scientific workflow research and development,” Future Gener. Comput. Syst., vol. 128, pp. 16–27, 2022. [43] M. Bramson, “Instability of FIFO queueing networks,” Ann. Appl. Probab., vol. 4, no. 2, pp. 414–431, 1994.

Related documents

• Almost sure one-endedness of a random graph model of distributed ledgers#798535
• Almost sure one-endedness of a random graph model of distributed ledgers#797122
• Optimal Operation Method for Computing Power-Electric Power Coordination Considering End-to-End Completion Latency of Computing Tasks#1061232
• The Coordination Tax and the Heterogeneity Dividend: Break-Even Conditions for Multi-Agent LLM Pipelines#1488492
• Sharpedo: Dual-Mode Uncertified DAG-Based Consensus Protocol#972635