{'fraction_non_alphanumeric': 0.04621697501979699, 'fraction_numerical': 0.010726369591822042, 'mean_word_length': 4.65039658328249, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimal Cloud Network Control with Strict Latency Constraints

The timely delivery of resource-intensive and latency-sensitive services (e.g., industrial automation, augmented reality) over distributed computing networks (e.g., mobile edge computing) is drawing increasing attention. Motivated by the insufficiency of average delay performance guarantees provided by existing studies, we focus on the critical goal of delivering next generation real-time services ahead of corresponding deadlines on a per-packet basis, while minimizing overall cloud network resource cost. We introduce a novel queuing system that is able to track data packets' lifetime and formalize the optimal cloud network control problem with strict deadline constraints. After illustrating the main challenges in delivering packets to their destinations before getting dropped due to lifetime expiry, we construct an equivalent formulation, where relaxed flow conservation allows leveraging Lyapunov optimization to derive a provably near-optimal fully distributed algorithm for the original problem. Numerical results validate the theoretical analysis and show the superior performance of the proposed control policy compared with state-of-the-art cloud network control.


I. INTRODUCTION
The past decade has seen a proliferation of resource-and interaction-intensive applications, such as real-time computer vision, autonomous transportation, machine control in Industry 4.0, multiuser video conferencing, and augmented/virtual reality [3], [4], which we collectively refer to as augmented information (AgI) services. In addition to the communication resources needed for the delivery of data streams to corresponding destinations, AgI services also require a significant amount of computation resources for the real-time processing of source data streams. In contrast, user equipments (UEs) are evolving towards increasingly small, portable devices (and inevitably, with constrained power and computing capabilities), pushing the need to offload many computing tasks to the cloud, especially those running advanced architectures such as fog and mobile edge computing (MEC), which deploy computation resources closer to the end users in order to strike a better balance between access delay and resource efficiency.
Delay and cost are thus two essential metrics when evaluating the performance of AgI service delivery. From the consumers' perspective, excessive end-to-end delays can significantly impact quality of experience (QoE), especially for delay-sensitive AgI applications where packets must be delivered by a strict deadline in order to be effective. In this context, An extended version of this paper is submitted to the IEEE Transactions on Communications [2]. timely throughput, which measures the rate of effective packet delivery (i.e., within-deadline packet delivery rate), becomes the appropriate performance metric [5]. In contrast, network operators care about the overall resource (e.g., computation, communication) consumption (and associated cost) needed to support the dynamic service requests raised by end users, which are dictated by the decision of route selection, function execution, and the corresponding resource allocation [6].
Previous studies have shown that the cloud network control problem [7]- [12], involving packet routing and processing decisions over a distributed computing network, can be connected to the packet routing problem in traditional communication networks via a properly constructed cloudaugmented or layered-graph formulation [13]. For packet routing, many dynamic control policies have been developed aimed at maximizing network throughput, including the celebrated back-pressure (BP) algorithm [14] and its extension, the Lyapunov drift-plus-penalty (LDP) control approach [15] that, in addition, optimizes network resource cost (e.g., energy expenditure). While having the remarkable advantage of achieving throughput optimal performance via simple local policies without requiring any knowledge of network topology and traffic demands, both BP and LDP approaches can suffer from poor (average) delay performance, especially in low congestion scenarios, where packets can take unnecessary long and sometimes even cyclic paths. In an attempt to address this problem, [16] proposed a combination BP and shortest-path routing; while [17] designed a centralized source routing approach, referred to as UMW, which reduces the average delay by dynamically selecting an acyclic route for each incoming packet, however requiring global network information.
Going beyond average delay and analyzing per-packet delay performance is a much more challenging problem with much fewer known results. In [18], a variant of the BP algorithm is developed that provides worst-case delay guarantees by allowing packet drops, leading to a tradeoff between delay and achievable throughput; however, the relationship is not tight enough for practical purposes. In [19], the authors formulate the problem of timely throughput maximization as a constrained Markov decision process (CMDP), and address it by solving the single-packet routing problem separately for each packet; yet, its computational complexity is prohibitive for practical implementation. A more comprehensive literature review is presented in [2].
In this paper, we investigate the problem of multi-hop distributed cloud network control with the goal of delivering multiple AgI services with strict deadline constraints on a per-packet basis, while minimizing overall resource cost. Our contributions can be summarized as follows: 1) We characterize the delay-constrained network capacity region leveraging a novel lifetime-driven generalized flow conservation law. 2) We develop a fully distributed control algorithm for the delivery of delay-sensitive services, shown to achieve timely-throughput optimality while minimizing overall resource cost. 3) We present numerical results illustrating the delayconstrained network capacity region and the superior delay-cost performance tradeoff of the proposed policy.

II. SYSTEM MODEL
Due to space limitations, in this paper we describe the proposed approach for the packet routing problem and refer the reader to the longer version in [2] for its cloud network control generalization. 1 Nonetheless, we do use the general cloud network control model for the numerical results in Section V.
Consider the packet routing network modeled by a directed graph G = (V, E), with V and E denoting the node and edge set, respectively. The nodes can transmit packets via the links (i, j) ∈ E between them, and we denote by δ − i and δ + i the incoming and outgoing sets of node i, respectively.
Time is slotted, and we quantify the available communication resource and the associated cost as [7] • C ij : the average transmission capacity, 2 i.e., the maximum average transmission rate of link (i, j); • e ij : the transmission cost, i.e., the cost of transmitting one unit size of data, on link (i, j). The problem of interest is to deliver the packets to their destinations ahead of corresponding deadlines, to which data packets' lifetime is closely related, defined as the number of time slots before the information contained in the packet becomes useless. A packet is called effective if its remaining lifetime l > 0, and outdated otherwise. We assume that only the delivery of effective packets counts (i.e., outdatedness is as bad as packet loss); the associated metric, timely throughput, i.e., the rate of effective packets delivery, is employed to characterize the capability of the communications network.

A. Request Model
For ease of exposition, we formulate the problem for a single destination-based commodity described by a destination node (or user) d ∈ V that requests of a given application, with the straightforward extension to multiple commodities given in [7]. We assume that the input packets of the given commodity 1 The generalization is based on the layered-graph technique [13]. 2 As an extension to this work, the problem formulated under a more realistic scenario with peak link capacity constraint is also studied in [2]. The solution closely follows the principle of the methodology presented in this paper. can originate at any node i ∈ V \ {d} (restriction of a specific source node set is straightforward) and that the source of each packet is aware of its lifetime l ∈ L {1, · · · , L} at birth, where L denotes the maximal lifetime. We denote by a (l) i (t) the number of lifetime-l packets arriving at node i on time slot t, which is assumed to be i.i.d. over time (with an upper bound of A max ); besides, the mean arrival rate is defined as λ

B. Queuing System
We construct a queuing system Q(t) that includes distinct queues for packets of different current lifetimes l ∈ L, and denote by Q Each time slot is divided into two phases. In the decision phase, the nodes make and accomplish the transmission decisions (which packets are sent out, to which neighboring node); in the receiving phase, the incoming packets, including those from neighboring nodes and the exogenous packets, are collected and loaded into the queuing system. Let x (l) ij (t) be the number of lifetime l packets that are sent from node i to j in time slot t; we refer to it as flow variable.
In general, the queuing dynamics are given by 3 ij (t) denote the total incoming and outgoing packets of node i.
In addition, we make the following assumptions: 1) outdated packets (not contribute to timely throughput) are dropped, i.e., and 2) for the destination node d, any effective packet is consumed as soon as it arrives, and therefore

C. Admissible Policy Space
The considered control policies make decisions on packet routing and scheduling in each time slot, 4 which are specified by the flow variables We restrict to the space of admissible control policies with the decided flow variables satisfying the following conditions: 1) non-negativity constraint, i.e., 2) average capacity constraint, i.e., ij (t), and {z(t)} denotes the expected long-term average operation, defined as 3) availability constraint, which requires the number of scheduled outgoing packets not to exceed those in the current queuing system, i.e., where γ is named the reliability level, and λ 1 is the total arrival rate of the application. The reliability constraint quantifies the extent to which the considered application can tolerate packet loss. It implies that a percentage of up to (1 − γ) of the incoming packets can be dropped without causing a significant performance loss.
The instantaneous cost of the decision x(t) is given by where ·, · denotes the inner product of the two vectors. Remark 1: In the existing literature of stochastic network optimization, the assigned flow has gained widespread use (e.g., [7], [14], [15], [18]), which is different from the actual flow in that it does not take the availability constraint (6) into account, and thus the decision space in each time slot does not depend on the current queuing status. Dummy packets are created when there are not sufficient packets in the queue to support the decision. The formulation is not suitable for the considered problem, because the reliability constraint (7) is imposed on actual packets received by the destination node d; while in the previous formulation, the flow variables x (l) can include dummy packets.

D. Problem Formulation
The goal of this work is to develop an admissible control policy that guarantees reliable packet delivery, while minimizing network resource cost. Formally, we aim to find the policy that makes decisions {x(t) : t ≥ 0} satisfying We emphasize that the above problem cannot be addressed by the LDP approach, because (i) the queuing system (9e) allows packet drops by (2), and (ii) we employ the actual flow as the decision variable, i.e., constraint (9d), which are different from the standard formulation.
In general, (9) can be interpreted as a CMDP problem [19]. However, we emphasize that the related state vector Q(t) and action vector x(t) are network-wide, which leads to a dramatically increasing state-action space, and the complexity of the standard solution [20] is prohibitive for practical implementation.

III. THE EQUIVALENT PROBLEM
In this section, we present a new problem P 2 , which is referred to as the virtual network. We prove the equivalence of the two problems in terms of flow space and capacity region, and use P 2 as a stepping-stone to find the solution to P 1 .

A. The Equivalent Problem
The new problem is cast as where the superscript (≥ l) indicates that the term includes all the lifetimes ℓ satisfying ℓ ≥ l, e.g., x (≥l) ij (t). 1) Virtual Queues: The crucial difference in deriving P 2 is to eliminate (i) the unconventional queuing system (9e) and (ii) (9d) that makes x(t) dependent on Q(t), i.e., the two factors prohibiting direct application of the LDP approach. Instead, we introduce the relaxed causality constraint (10d) (see Proposition 1) to state the fact that the lifetime of the packets must decrease as they traverse any node i.
Although there is no explicit queuing system involved in P 2 , it consists of long-term average objective and constraints, which can be addressed by the LDP approach via the use of virtual queues [15] (we denote the solution by ν(t)). More concretely, ensuring constraints (10b) and (10d) is equivalent to stabilize the following virtual queues: is the total amount of packets arriving at the network in time slot t. 5 We refer to (11a) and (11b) as the virtual queues at node d and i, respectively.
2) Physical Interpretations: P 2 describes a virtual network modeling each node as a data-reservoir, which has access to abundant (virtual) packets of any lifetime. As neighboring nodes request packets from node i, it supplies the needs by using the virtual packets from the reservoir in advance, which are compensated when the node receives incoming packets of the same lifetime. The virtual queues can be roughly explained as the accumulated data deficits (outgoing flow minus incoming flow) of the corresponding data-reservoirs; specially, in (11a), the destination reservoir sends out γA(t) packets to the end user (as is required by the reliability constraint), while receiving ν →d (t) in return. When (10d) is satisfied, node i no longer embezzles the virtual packets from its reservoir; and if it is true for all nodes, the data streams in the network include only actual packets. The resulting flow assignment (defined in next subsection) can instruct the packets to find their paths in the actual network.
B. Relationships Between P 1 and P 2 Similar to Section II-C, for a given pair of (λ, γ), we define a policy p to be admissible for P 2 if it satisfies (10b) -(10d). In addition, suppose an admissible policy p ∈ A n (n = 1, 2) makes decisions x p (t) = x (l) ij (t) : (i, j) ∈ E, l ∈ L, t ≥ 0 , then the associated flow assignment is defined as x p = {E {x p (t)}}, which collects the transmission rates of all links.
Definition 1: For given (λ, γ), the admissible policy space A n is defined as the collection of all admissible control policies for problem P n (n = 1, 2).
Definition 2: The network capacity region Λ n is defined as the set of (λ, γ) pairs, under which the admissible policy space A n is non-empty (n = 1, 2).
Definition 3: For given (λ, γ) ∈ Λ n , the flow space is defined as the set of all flow assignments that can be achieved by the admissible policies, i.e., Γ n = x p : p ∈ A n (n = 1, 2).
Next, we present the relationships between the two problems, in terms of the above quantities.
A pair (λ, γ) is within the capacity region Λ n (n = 1, 2) if and only if there exist flow variables x = {x (l) ij ≥ 0 : ∀ (i, j) ∈ E, l ∈ L}, such that ∀ i ∈ V, (i, j) ∈ E, l ∈ L, (12d) Furthermore, for any point within the capacity region, there exists a randomized policy * to support it while attaining optimal cost performance.
Proof: All proofs can be found in [2]. In Proposition 2, given x satisfying (12), the feasible randomized policy * (for P 1 ) operates as follows: in each time slot, any packet of lifetime l ∈ L at node i ∈ V has a probability α (l) to be sent to node j, and stay in node i otherwise; and the policy * achieves the flow assignment x.
The previous propositions can be explained as follows: by Proposition 1, in general, the admissible policy spaces A 1 A 2 and A 2 A 1 ; Proposition 2 suggests that they lead to the same capacity regions by presenting an explicit identical characterization (12), where (12c) is interpreted as the generalized flow conservation law when considering the packets' lifetime; Proposition 3 further shows that P 1 and P 2 share the same flow space for any (λ, γ), which is a crucial property for the considered problem, where the two metrics of interest, i.e., timely throughput (7) and resource cost (8), are both linear functions of the flow assignment.
Corollary 1: P 1 and P 2 have the same optimal value. Proof: Because they have the same flow space.

IV. PROPOSED CONTROL POLICY
In this section, we provide a solution for P 2 leveraging Lyapunov optimization theory, and take advantage of Propositions 2 and 3 to develop an algorithm for P 1 based on it.

A. Solution to the Virtual Network Problem
We define the Lyapunov function as L(t) = U (t) 2 2 /2, and Lyapunov drift ∆(U (t)) = L(t + 1) − L(t). The LDP approach advocates to minimize a linear combination of the Lyapunov drift (see [2]) and the cost function weighted by a tunable parameter V (which controls the tradeoff between network congestion and operational cost), i.e., B is a constant, and the weights w(t) are given by where the superscript (≤l) refers to the operation of l ℓ=1 . To sum up, the developed algorithm aims to solve the following problem in each time slot The solution is in the max-weight fashion. More concretely, for each link (i, j), we first find the lifetime l ⋆ with the largest weight, and spend all the transmission resource to transmit packets of this lifetime if the associated weight is positive. To sum up, the optimal flow assignment is where the optimal lifetime choice is l ⋆ = arg max l∈L w (l) ij (t), and I{·} denotes the indicator function, which equals 1 when the two events in the bracket are both true.
Due to the additive form of the objective function, which is composed of sub-problems that can be completed in each individual node, the algorithm can be implemented in a fully distributed manner.

B. Performance Analysis
In this part, we present a proposition analyzing the performance of the proposed control policy related to the timely throughput (for reliability constraint (7)) and resource cost.

Definition 4 (ε-Convergence Time):
The ε-convergence time t ε is the first time index, such that the achieved reliability level is within a gap of ε from the desired value ever after, i.e., Proposition 4: For any point in the interior of the capacity region, under the proposed algorithm, the virtual queues are mean rate stable with a convergence time t ε ∼ O(V ) for any ε > 0, and the achieved cost performance satisfies where h ⋆ 2 (λ, γ) denotes the optimal cost performance that can be achieved under (λ, γ) in P 2 .
Proof: See [2]. From the above proposition, we find that by pushing the parameter V → ∞, the achieved cost performance approaches the optimal cost (since the gap B/V vanishes), while compromising the convergence time.

C. Flow Matching
In this section, we develop a near-optimal control policy for P 1 . According to Proposition 3 and Corollary 1, there exists a randomized policy (specified by probability values α) to be optimal, and we aim to find the solution to P 1 in this categoty. Instead of find α directly (not straightforward), the proposed approach will leverage (13) and calculate the parameters therein using empirical virtual flow decisions. In the following, we denote the decided flow for P 1 on time slot t by µ(t) = {µ (l) ij (t)} (to distinguish it from ν(t)). The goal of the designed policy is to conform with the constraints in P 1 (i.e., satisfying (9b) -(9d)), while pursuing the goal of flow matching, i.e., {µ(t)} = {ν(t)}. The reason to set the above goal is two-fold. (i) It ensures that the two algorithms attain the same throughput and cost performance (as mentioned earlier, both metrics are linear functions of the flow assignment); therefore, {µ(t)} satisfies the reliability constraint and achieves the same (and thus near-optimal by Corollary 1) cost performance as {ν(t)}. (ii) The existence of the policy is guaranteed (as a result of identical flow spaces). Actually, given a feasible flow assignment x satisfying (12) (specifically, {ν(t)}), we are already aware of the construction procedure of the randomized policy * to achieve it (see Proof to Proposition 2 in Section III-B).
While we do not wait until the exact value of {ν(t)} is obtained (actually it takes forever) to construct the randomized policy * ; as an alternative, its empirical values are employed. In each time slot, we first calculate the probability values α(t) according to (13), using the finite-horizon averageν(t) = 1 t t−1 τ =0 ν(τ ) as the flow assignment x, and estimating λ from the empirical arrivals byλ τ ); then node i transmits packets of lifetime l to node j according to the obtained distribution. It leads to a time-varying randomized policy, but we stress thatν(t) converges to {ν(t)} asymptotically, which no longer changes over time. 6 In addition to deciding the virtual flow by the algorithm in Section IV-A, the developed randomized policy requires each node to record its own incoming and outgoing flows to calculate the probability values by (13), which can be completed locally. Therefore, the proposed design can operate in a fully distributed manner.
Proposition 5: For any point in the interior of the capacity region, the proposed control policy is admissible, while achieving the near-optimal cost performance of h({ν(t)}).

V. NUMERICAL EXPERIMENTS
In this section, we carry out several numerical experiments to evaluate the performance of the proposed design, based on the Abilene US continental network in Fig. 1.
We take a simple AgI service for example, 7 which requires the source data-stream to be processed by one function, and we assume that each node (representing a data center) in the network can host the given service function. To describe the function's computation resource requirement, we assume that a CPU (a measure of computing resource) is capable of processing the incoming data-stream at a rate of 50 Mbps, and the output data-stream has the same size as the input.
The available network resource and the associated cost is described in the following: each node in the network has a an average resource consumption budget of 2 CPUs and the associated cost is 1 /CPU at i ∈ {5, 6}, and 2 /CPU at other data centers; each link exhibits the same average transmission rate of 1 Gbps, with a cost of 1 /Gb.
There are two clients, i.e., (source, destination) pairs, requesting the service, i.e., (1,9) and (3,11), both at the reliability level of γ = 90%. The packets arrive at the source nodes according to independent Poisson processes of parameter λ. The lifetime of all packets at birth equals to the maximum lifetime L (≥ 5, including 4 time slots for transmission via the shortest path, and 1 time slot for processing).

A. Network Capacity Region
We first study the network capacity regions achieved by the proposed algorithm, assuming different maximum lifetimes L. We run the proposed algorithm (with V = 0) on the network for 1 × 10 6 time slots, recording the queue backlog of the virtual network, and the 0.005-convergence time for the actual network (i.e., when achieved reliability level ≥ 89.5%).
The results are shown in Fig. 2, and we make the following observations. First, for fixed L, both the virtual queue (solid   lines) and the convergence time (dashed lines) blow up after the arrival rate exceeds a critical point, which is interpreted as the boundary of the capacity region. The result verifies that the virtual and the actual network have the same capacity regions (as stated in Proposition 2). Second, by increasing the value of L, the capacity region enlarges, since the packets can detour to farther network locations for extra computing resources, while still arriving at the destinations within the deadline. When L = 5, the packets must follow the shortest paths to the destinations, and the two clients must share the constrained computing resource at the common nodes on the paths (data centers 3,6,8,9); when L = 6, client (3, 11) can detour along 3 → 6 → 5 → 7 → 10 → 11 for extra computing resource, boosting the capacity region; when L ≥ 7, the computing resources of the entire network are fully exploited.

B. Effects of Parameter V
Next, we study the convergence time and the resource cost achieved by the proposed algorithm under various V (using L = 7 and λ = 100 Mbps). In addition, we compare the results with the state-of-the-art min-cost max-throughput algorithm, referred to as DCNC [7].
The result is depicted in Fig. 3. First, we focus on the performance of the proposed algorithm (solid lines), which exhibits the [O(V ), O(1/V )] tradeoff between the convergence time and the resource cost, as is presented in Proposition 4. Second, for the DCNC algorithm, we observe from the experiment that the achieved timely throughput is around 10 Mbps (i.e., a reliability level of 10%, see next section for more results), failing the reliability constraint (resulting in a convergence time of ∞). For the cost performance, when V ≤ 1 × 10 6 , it leads to a much higher resource cost (≥ 15) than the proposed algorithm, since the packets can take cyclic paths to the destination, incurring extra cost; as V grows, the cost reduces, while it is still higher than the proposed algorithm because it delivers all the packets (even the outdated ones).

C. Effects of Lifetime L
Finally, we present the timely throughput and the resource cost achieved by the proposed and the DCNC algorithms, under various maximum lifetimes (λ = 100 Mbps, and a large V = 5 × 10 7 is selected to ensure near-optimal resource cost).
As we can observe from Fig. 4, the proposed algorithm attains a (sum) timely throughput of 180 Mbps, i.e., a reliability level of 90% for each client, where the reliability constraint holds with equality (the existence of the .01convergence time in the previous experiment also supports the result). In contrast, the DCNC algorithm achieves much lower timely throughput, e.g., 20 Mbps when L = 15, where the packets are provided 10 extra time slots for transmission. Finally, we point out that the resource cost of the proposed algorithm significantly improves when L turns 6, where the two clients can follow the network paths (i) client 1: 1 → 3 → 6 (processing) → 8 → 9, (ii) client 2: 3 → 6 → 5 (processing) → 7 → 10 → 11 to benefit from cheap computation resources at node 5 and 6.

VI. CONCLUSION
In this paper, we investigated the problem of optimal cloud network control with strict deadline constraints. We established a new queuing system to keep track of the data packets' lifetimes, on which basis we formalized the problem P 1 . An equivalent problem P 2 was derived, for which we provided a solution leveraging Lyapunov optimization theory. We then took advantage of their close relationship (identical capacity region, flow space, and optimal cost value), to develop a provably near-optimal, fully distributed algorithm for P 1 , from the empirical decisions made for P 2 . Numerical results validated the theoretical analysis and the performance gain of the proposed design over the state-of-the-art algorithm.