{'fraction_non_alphanumeric': 0.0424407235394769, 'fraction_numerical': 0.006935956978733806, 'mean_word_length': 4.502521856086079, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Result and Congestion Aware Optimal Routing and Partial Offloading in Collaborative Edge Computing

Collaborative edge computing (CEC) is an emerging paradigm where heterogeneous edge devices (stakeholders) collaborate to fulfill computation tasks, such as model training or video processing, by sharing communication and computation resources. Nevertheless, the optimal data/result routing and computation offloading strategy in CEC with arbitrary topology still remains an open problem. In this paper, we formulate a partial-offloading and multi-hop routing model for arbitrarily divisible tasks. Each node individually decides the computation of the received data and the forwarding of data/result traffic. In contrast to most existing works, our model applies to tasks with non-negligible result size, and enables separable data sources and result destinations. We propose a network-wide cost minimization problem with congestion-aware cost to jointly optimize routing and computation offloading. This problem covers various performance metrics and constraints, such as average queueing delay with limited processor capacity. Although the problem is non-convex, we provide non-trivial necessary and sufficient conditions for the global-optimal solution, and devise a fully distributed algorithm that converges to the optimum in polynomial time, allows asynchronous individual updating, and is adaptive to changes in network topology or task pattern. Numerical evaluation shows that our proposed method significantly outperforms other baseline algorithms in multiple network instances, especially in congested scenarios.


I. INTRODUCTION
In recent years, we are experiencing an explosive increment in the number of mobile and IoT devices. Our daily life is increasingly involved with new mobile applications for work, entertainment, social networking, health care, etc. Many of them are computation-intensive and time-critical, such as AR/VR and autonomous driving. Meanwhile, mobile devices running these applications generate a huge amount of data traffic which is predicted to reach 288EB per month in 2027 [1]. It becomes impractical to direct all computation requests and their data to central cloud due to limited backhaul bandwidth and high latency. Edge computing is then proposed as a promising solution to provide computation resources and cloud-like services in close proximity to the mobile devices.
In edge computing, requesters offload their computation to the edge servers. A new concept, extending this idea, is the so-called collaborative edge computing (CEC). Besides pointto-point offloading, CEC let multiple stakeholders (mobile devices, IoT devices, edge servers, or cloud) collaborate with each other by sharing data, communication resources, and computation resources to finish computation tasks [2]. On the one hand, CEC improves the utilization efficiency of resources so that computation-intensive and time-critical services can be better completed at the edge. Mobile devices equipped with computation capabilities can collaborate with each other through D2D communication [3]. Edge servers can also collaborate with each other for load balancing or further with central cloud to offload demands that they cannot accommodate [4]. On the other hand, CEC is needed when there is no direct connection between devices and edge servers. Consider unmanned aerial vehicle (UAV) swarms or autonomous cars in rural areas, computation-intensive tasks of UAVs or cars far away from the wireless access point should be collaborated computed or offloaded through multi-hop routing to the edge server with the help of other devices [3], [5].
We wish to study a general framework of CEC which enables varies types of collaboration among stakeholders. In particular, we consider a multi-hop network with arbitrary topology, where the nodes collaboratively finish multiple computation tasks. Nodes have heterogeneous computation capabilities and some are also data sources (sensors and mobile users) that generate data for computation tasks. Each task has a requester node for the computation result. We allow partial offloading, where the computation of a task can be partitioned and conducted by multiple nodes, by considering data-driven and divisible tasks, i.e., a task can be divided arbitrarily into sub-tasks that compute different parts of the input data. Finishing a task requires the routing of data from possibly multiple data sources to multiple nodes for computation and the routing of results to the requester. We aim for a joint routing (how to route the data/result) and computation offloading (where to compute) strategy for all tasks that minimizes the total communication and computation costs. This problem is non-trivial, but we are able to find the optimal joint routing and computation strategy in the proposed framework: In particular, we provide the necessary and sufficient conditions for the global optimum and propose an distributed and adaptive algorithm that converges to the global optimum with small information exchange overhead.
Compared with existing edge computing and CEC studies, our work is distinct in several aspects. First, while most works study only offloading-type computation where requesters offload their data for computation [5]- [7], we allow data sources and requesters be different nodes to cover computation that requires fetching data from other nodes (like sensors) besides the requester itself. Sahni et al. [3], [8] also consider arbitrary data sources, but are restricted to fully connected networks or predefined routing protocols. Second, while we study routing for both data and result flows, most existing works ignore the cost for transmitting results [2], [9], [10] and simply let results transmitted along the reverse path of data [11], [12]. However, the size of computation result is not negligible in many applications. For example, the communication cost of intermediate results is one major concern in federated or distributed machine learning [13], and result size can even be larger than data size in applications like decompression and image enhancement. Third, we model congestion in our framework by considering non-linear communication and comuputation costs instead of linear costs as in [5], [14]. Finally, the existence of optimal solution, and distributed and adaptive algorithm makes our framework possible to be implemented in practical distributed edge networks with provable performance guarantee and robustness to network condition changes.
Our detailed contributions are as follows: • To the best of our knowledge, we formulate the fist framework that jointly studies partial offloading and routing for both data and result in arbitrary CEC networks with congestible links. • We provide the global optimal routing and offloading strategy for this non-convex problem, by studying the necessary and sufficient optimality condition. • We devise a distributed, asynchronous, and adaptive algorithm that converges to the global optimum. • By extensive experiments, we show the advantages of the proposed algorithm over several baselines in different network topologies. The remainder of this paper is organized as follows. We present our model of a CEC network and formulate the optimization problem in Section II. The necessary and sufficient optimality conditions are discussed in Section III, while the proposed algorithm is presented in Section IV. We summarize our experiment results in Section V and finally conclude in Section VI.

II. NETWORK MODEL AND PROBLEM FORMULATION
We begin by presenting our formal model of a collaborative edge computing network where multiple stakeholders collaborate to finish computation tasks. Such network is motivated by several real-word applications such as IoT networks, connected vehicles and UAV swarms. An example system that involves IoT network on the edge is shown in Fig. 1.

A. Network model
We consider a quasi-static network, represented by a directed and strongly connected graph G = (V, E) where V is the set of nodes (devices with either task, data or computation resource to share) and E is the set of links. For nodes i, j ∈ V , there exists link (i, j) ∈ E if a feasible connection from i to j is available for data or result forwarding. Denote I(i) the set of all incoming nodes j ∈ V of i such that (j, i) ∈ E, and O(i) the set of outgoing nodes j ∈ V of i such that (i, j) ∈ E.
We consider general computation tasks that map input data to result of non-negligible size, including image/video com- Flow assigned to computation of (d, m) at i am Result size per unit input data of computation m Vector of computation input for all task types at i D ij (F ij ) Communication cost (e.g. queueing delay) on (i, j) Computation cost (e.g. CPU time) at node i D Sum of all communication and computation costs pression, message encoding/decoding, model training 1 , etc. A task involves the computation of data generated by multiple data sources and the computation results being forwarded to a given destination (the requester). Specifically, we assume the computation performed in the network are of M different types, and denote S the set of all task. A task is represented by a pair (d, m) ∈ S, where d ∈ V is the result destination and m ∈ [M ] is a specified computation type 2 . Let r i (d, m) ≥ 0 be the exogenous input rates of the data corresponding to task (d, m) at data source node i ∈ V . With this model we enable multi-source-single-destination tasks, namely multiple nodes i with r i (d, m) > 0 are allowed for a task (d, m), e.g., a monitor process involving multiple sensors. The input rate r d (d, m) at destination could also be positive, incorporating applications with locally provided data and computation offloading.

B. Routing and computation strategy
The injecting data flows of each task are routed to nodes with computation resources to be computed. After computation, result flows are generated and routed to corresponding destination nodes. Since data and computation result are simultaneously forwarded in the network, we distinguish them by superscript − and +, respectively.
Data and result flows. We consider a hop-by-hop routing scheme: Let f − ij (d, m) ≥ 0 denote the data flow of task (d, m) on link (i, j) and f + ij (d, m) ≥ 0 denote the result flow on the same link. Let g i (d, m) ≥ 0 denote the computation flow at node i corresponding to task (d, m), i.e., the data flow forwarded to the processor of node i for computation. We consider that the result flow generated by computation for type m is a non-decreasing function γ m (·) of the corresponding computation flow, given as In particular, we assume that γ m (·) is a non-negative weighted sum of a linear function and a sign function. Let where a m ≥ 0 is the ratio of result size versus data, b ≥ 0 is a fixed overhead due to task partition or the nature of computation. In this paper, we focus on case b = 0. Such assumption fits most of the computation required in modern applications with usually a m ≤ 1. Whereas we also allow a m > 1, representing special types of computation with result size larger than the input data size, e.g., video rendering, image super-resolution or file decompression. 3 Let t − i (d, m) denote the total data traffic of task (d, m) forwarded and injected to node i, and t + i (d, m) denote the total result traffic forwarded to and generated at node i, given by the following Routing and computation strategy. To describe the computation and forwarding scheme in a distributed fashion, we assume that each node has two virtual router, one for data flow and one for result flow, as shown in Fig be the fraction of data or result flow of task (d, m) at node i forwarded to node j. For a coherent notation, we also use φ − i0 (d, m) ∈ [0, 1] to denote the fraction of computation flow at node i, and use to represent the system-wide routing and computation strategy. To ensure all tasks are fulfilled, all injected data must be computed and the result must be delivered to the destination, given by the following flow conservation: for all (d, m) ∈ S and i ∈ V , the data traffic is either computed or forwarded, and for the result traffic, the destination is a sink:

C. Communication and computation cost
For mathematical formulation, we ignore the request messages sent by the requester to data sources, as the size of such messages are typically negligible compared to data or result, and could be delivered using a separate channel.
Instead of sharp bandwidth or computation capacity constraint in [15] or linear costs in [16], we assign convex costs for D2D communication and local computation depending on corresponding flow rate, a more general assumption reflecting network congestion status. In particular, define the total flow on link (i, j) ∈ E as where D ij (·) is increasing, continuously differentiable and convex. Similarly, denote G i the data rate vector of the amount of computation for each type performed at node i, i.e., where g m i is the total computation amount of type m, g m i = d:(d,m)∈S g i (d, m). We denote C i (G i ) the cost for node i to fulfill the computation load G i , where function C i (·) is an increasing, continuously differentiable and convex multivariable function, i.e., increasing on every coordinate and jointly convex in g 1 i , · · · , g M i . Such assumption of cost functions incorporates a variety of existing performance metrics. For example, gives the average number of packets waiting for or under transmission at link (i, j), provided that µ ij is the service rate in an M/M/1 queue model [17] and F ij < µ ij . One could also approximate the sharp capacity constraint F ij ≤ C ij (e.g., in [15]) by a smooth convex function that goes to infinity when approaching to capacity limit C ij .
Note that we measure the computation cost C i (G i ) as a function of data rate, which is adopted in network function virtualization (NFV) studies [18], but most previous computation offloading researches [5] [19] assign data amount and computation workload separately for a task. Our formulation can be reduced to the latter if choose certain cost function. For instance, consider the scenario where users make requests with input data size d m (bits) and computation workload c m (CPU cycles). By setting C i (G i ) = m∈[M ] c m g m i /d m , we measure CPU cycles as cost. Or by setting v m i to be the computation speed of type m at i and , we measure CPU runtime as cost. Note that for a network with heterogeneous computation resources, our formulation is even more flexible than that in [2] [19], where there a task always assigns the same computation workload wherever it is computed. In fact, our model captures the fact that in practical network edge, the workload for a certain task may be very different depending on where to perform it, e.g., some parallelizable computation is easier at nodes equipping GPU, but slower at others.

D. Joint routing and computation offloading problem
In this paper, we aim at minimizing the overall cost of edges and devices for both communication and computation, such that (1) to (7) hold Note that problem (8) is not convex in φ. We will demonstrate by example that standard gradient-based methods solving for KKT points highly likely generate sub-optimal solutions.

III. SUFFICIENT OPTIMALITY CONDITION
In this section, we provide necessary and sufficient conditions for the global optimum of problem (8). Our analysis follows [20], while we make non-trivial extensions for considering both data and result flows, as well as in-network computation. Remind that we focus on the case with b = 0, where the size of computation result is in proportion to the data size, i.e., γ m (g i (d, m)) = a m g i (d, m).
We start by giving closed-form expressions to the derivatives of the total cost D. For an increment of exogenous data flow r i (d, m), the increase of D (i.e. the marginal cost) is caused by two aspects, (1) the cost of forwarding extra data flow to i's outgoing neighbors j ∈ O(j), and (2) the cost of assigning extra computation load at i's computation unit. Note that the first aspect could be further decomposed into two terms, the extra cost on the out-link (i, j) and the extra cost at the nexthop j, and similarly could the second aspect. Thus formally, the marginal cost at node i is given as where ∂D/∂t + i (d, m) denotes the marginal cost corresponding to an increment of result traffic at i. Similarly to (9), this marginal of the result traffic is a weighted sum of extra costs at out-links and at next-hope nodes, given as Note that (9) and (10) can be calculated recursively, whereas we defer the detailed mechanism to Section IV. Meanwhile, with an increment of φ − ij or φ + ij , the extra cost could also be decomposed in the similar way as in (9) or (10), respectively.
Then we could solve (8) by minimizing the Lagrangian subject to the constraints φ − ij (d, m) ≥ 0 and φ + ij (d, m) ≥ 0. By setting the derivative of L to 0, a KKT necessary condition of the global minimizer to (8) is given by Lemma 1.
Note that the condition in Lemma 1 is not a sufficient condition for optimality. A toy example for such non-sufficiency is provided in Fig.3: The only task is (4, m) with input data only occur at node 1,the routing/offloading strategy and marginal costs are shown on figure. It is easy to verify that condition in Lemma 1 is satisfied. However, by increasing φ − 24 and decreasing φ − 23 , the input marginal ∂D/∂r 2 will decrease and thus ∂D/∂φ − 12 will decrease. In this case, the objective D could be improved by increasing φ − 12 and decreasing φ − 14 . The underlying intuition for such non-sufficiency is that the condition in Lemma 1 automatically holds if t − i (d, m) = 0 and t + i (d, m) = 0, no matter what the routing/computation strategy is. Nevertheless, given t − i (d, m) and t + i (d, m) exist identically in (11) and (12) respectively for all j, we remove them and devise an augmented condition specified in Theorem 1, which instead is shown to be sufficient for global optimality.
Proof. See Appendix. Theorem 1 is the main theoretical result of this paper, and in fact a practical criterion for algorithm implementation. As a simple illustration of the difference between Theorem 1 and Lemma 1, we further assume the network in Fig. 3 has linear communication costs. It turns out that for any routing scheme satisfying Theorem 1, we must have φ − 12 (4, m) = 1 and φ − 24 (4, m) = 1, which precisely indicates the shortest path 1 → 2 → 4 for data flow.

IV. DISTRIBUTED AND ADAPTIVE ALGORITHM
In this section, we introduce a distributed and adaptive algorithm that converges to the global optimal solution of (8) specified by Theorem 1, based on scaled gradient projection. We allow nodes update their routing-computation strategies in an autonomous and asynchronous manner, and adapt to the changes of input rate and network topology. Our method follows Xi and Yeh [21], and further distinguishes data and result flows by improving control messages exchanging protocol.

A. Algorithm overview and loop-free property
We first introduce the loop-free property of a global strategy φ. For a task (d, m), there is a data path from node i to node j (j = i) if there is a sequence of node n 1 , · · · , n L such that (n l , n l+1 ) ∈ E and φ − n l n l+1 (d, m) > 0 for l = 1, · · · , L − 1, with n 1 = i and n L = j, where L is the hop number for this data path. We say φ has a data loop if there exists task (d, m) and node i, j such that i has a data path to j, and vice versa. Similarly, we can define result path and result loop for result flows. Then, we say strategy φ is loop-free if it has neither data loop nor result loop. Loop-free is a fundamental requirement for φ to be feasible and is guaranteed throughout the algorithm. Because given a slight increase in input rate, a loop may cause the on-loop flow to build up to infinity. 4 We denote respectively by φ − i (d, m) and φ + i (d, m) node i's strategy vector φ − ij (d, m) j∈{0}∪O(i) and φ + ij (d, m) j∈O(i) , and by δ − i (d, m) and δ + i (d, m) the vectors of augmented marginals (defined in (14)), δ − ij (d, m) j∈{0}∪O(i) and δ + ij (d, m) j∈O(i) . We assume the network starts with a feasible and loop-free state φ 0 . At t-th iteration, each node i updates its strategy corresponding to task (d, m) with the following scaled gradient projection variant and φ + i (d, m) t+1 is updated similarly with "−" replaced by "+", where M − i (d, m) t , M + i (d, m) t are symmetric and positive semi-definite scaling matrices designed to achieve good convergence properties.
are the blocked nodes of i relevant to data and result of task (d, m) to guarantee the feasibility and loop-free property. We next describe in detail the estimation of marginals, and how to obtain matrices We emphasis that our proposed algorithm is not pure gradient-based, as the gradients are replaced by the augmented marginals δ − i (d, m) and δ + i (d, m), corresponding to Theorem 1.

B. Marginal cost estimation by broadcast
Each node i needs to compute its augmented marginal cost vectors δ − i (d, m) and δ + i (d, m) following (14). Node i can directly estimate D ij (F ij ) and C i (G i ) while sending and receiving any message on link (i, j) or performing computation at local computation unit. To obtain ∂D ∂ri(d,m) and  (10) and broadcasts this to all upstream nodes k ∈ I(i) such that φ + ki (d, m) > 0. 2) For the ∂D ∂ri(d,m) , a similar procedure is used to compute and broadcast ∂D ∂ri(d,m) according to (9). Note that node i must obtain ∂D ∂t + i (d,m) before calculating and broadcasting ∂D ∂ri(d,m) . 4 We allow loops concatenated by a data path and a result path of the same task, which occurs in scenarios where the destination is the data source.
With the loop-free property held, such broadcast starting at destination d (with ∂D ∂t + d (d,m) = 0) is guaranteed to traverse throughout the network. Though data flows have no explicit (and fixed) sink, the loop-free property guarantees the broadcast of stage 2) could successfully start with the last node of each data path.

C. Blocked nodes and scaling matrices
To achieve the feasibility and loop-free property, we con- to nodes in which node i is forbidden to forward data or result of task (d, m), respectively. By Theorem 1 combined with expression (9) and (10), at a global optimal strategy, the input marginals ∂D ∂ri (d,m) or ∂D ∂t + i (d,m) should be monotonically decreasing along any data-path or result-path. We thus mandate that node i should not increase flow rate to a neighbor j that either (1) has higher input marginal, or (2) could form a data/result-path containing some link (p, q) and q has higher input marginal than p. We denote by  ) . Then, the loopfree property is maintained throughout the algorithm if sets of block nodes are practiced in each iteration. The feasibility is also guaranteed since when current state approaches a link/processor capacity, the corresponding marginal will grow to infinity, preventing any flow increase. The readers are referred to [20] for detail.
The scaling matrices M − i (d, m) t and M + i (d, m) t are introduced to improve the convergence speed while guaranteeing convergence from arbitrary initial points [21]. Specifically, where D 0 is the overall cost at initial state, h + j (d, m) t is the maximum hop number among all existing result paths from j to destination d, operator diag forms a diagonal matrix, and m) t is almost a repetition as above, but in terms of the data flow.

D. Asynchronous convergence and complexity
Our algorithm allows nodes to update their variables asynchronously, or with a non-perfect synchronization due to practical constraints such as the broadcast delay in a largescale network. To formulate this asynchrony, we assume that at t-th iteration, only one node i updates either its φ − i (d, m) or φ + i (d, m) for one task (d, m) ∈ S, and let m) at iteration t , and similarly as T φ + i (d,m) , then Theorem 2 holds. Theorem 2: Assume b = 0 and the network is static, if then the constructed sequence φ t t→∞ converges to a point φ * , where φ * is feasible and loop-free, and the condition in Theorem 1 holds (proof see [21]).
We assume that the variables of all nodes are updated one round every time slot of duration T , and every broadcast message described in Section IV-B is sent once in a slot. There are 2|E| transmissions of control messages corresponding to a task in one slot, and thus totally 2|S||E| transmissions, with on average 2|S|/T per link/second and at most 2d|S| for each node, whered is the largest out-degree, and a singe broadcast message has O(1) size. Moreover, leth be the maximum path hop, and t c be the maximum time for control message transmission, the broadcast procedure yields a delay of at most 2ht c . The variable size for individual node optimization problem is at most 2d|S|, where each problem, although is a scaled gradient projection, could be efficiently solved by various commercial solvers since the scaling matrix is PSD and diagonal, and the constraint set is simplex.

V. NUMERICAL EVALUATION
In this section, we evaluate the scaled gradient projection algorithm, i.e., SGP proposed in Section IV by simulation. We implement several baseline algorithms and compare the performance of those against SGP over different networks and parameter settings. Note that we set b = 0 in all experiments.  We summarize the simulation scenarios in Table II. We evaluate the algorithms in the following different network topologies: Connected-ER is a connectivity-guaranteed Erdős-Rényi graph, generated by uniformly-randomly creating links with probability p = 0.1 on a linear network concatenating all nodes. Balanced-tree is a complete binary tree. Fog is a sample topology for fog-computing, where nodes on the same layer are linearly linked in a balance tree [22]. Abilene is the topology of the predecessor of Internet2 Network [23]. GEANT is a pan-European data network for the research and education community [23]. SW (small-world) is a ring-like graph with additional short-range and long-range edges [24].
Table II also summarizes the number of nodes |V | and edges |E|, as well as the number of tasks |S| in each network. We set a m to be exponential with mean value 0.5 and truncated into interval [0. 1,5], considering that most computations have a m smaller that 1, but special types like video rendering have relatively larger a m . Each task is randomly assigned with one computation type and one destination node, along with |R| random active data source (i.e. r i (d, m) > 0). The input  We implement the following baseline algorithms. Since this paper is the first to study joint routing and computation partial offloading in arbitrary network topologies with congestiondependent cost and non-negligible result size, we make adaptation to these baselines to fit our model. GP(Gradient Projection): similar to SGP but with the scaling matrices M − i (d, m) and M + i (d, m) being identity matrix multiplied by universal stepsize 0.1. GP and SGP lead to the same global strategy but with different convergence speed. SPOO(Shortest Path Optimal Offloading): fixes the routing variables φ − ij ,φ + ij with j = 0 to the shortest path (measured with marginal cost at F ij = 0, accounting for the propagation delay without queueing effect), and studies the optimal offloading along these paths. Similar strategy is considered in [11] with linear-topology and partial offloading. Note that when destination and data source are the same node, SPOO is restricted to local computation. LCOR(Local Computation Optimal Routing): computes at the data sources (or with minimum offloading if pure local computation is not feasible), optimally route the result to destinations using scaled gradient projection in [25]. LPR(Linear Program Rounded): the joint path-routing and offloading method by [6], which does not consider partial offloading, congestible links and result flow. To adapt LPR's linear link costs to our schemes, we use the marginal cost at zero flow. To ensure sufficient communication resources for the result flow, we assign a saturate-factor of 0.7 for queueing delay costs, i.e., the data flow could not exceed 0.7 times real capacity. Shortest path routing is used for result flow. Fig.4 compares the total cost D of different algorithms at the steady state over networks in Table II (we omit GP as it has the same steady state performance with SGP), where the bar heights of each scenario are normalized according to the worst algorithm. We test both linear cost and queueing delay with other parameters fixed in topology SW, labeled as SW-linear and SW-queue. Our proposed algorithm SGP significantly outperforms other baselines in all simulated scenarios, with more than 30% improvement on average over LPR, which also jointly optimizes routing and task offloading but does not consider partial offloading and congestible links. The difference of case SW-linear and SW-queue suggests that our proposed algorithm promises a considerable improvement to SOTA especially when the networks are congestible. Note that LCOR and SPOO reflects the optimal objective for routing and offloading subproblems, respectively. The gain of jointly optimizing over both strategies could be inferred by comparing SGP against LCOR and SPOO. For example, LCOR performs extremely bad in topology Balanced-tree, because no routing could be optimized in a tree topology.
We also perform refined experiments in Connected-ER, with the network topology and capacity shown in Fig.5a. There are 4 major servers as labeled, and we assume server S1 fails (communication and computation capability disabled, stop sending data or making requests) at the 100-th iteration. We compare the convergence speed of GP and SGP in Fig.5b subject to such server failure. SGP takes much less iterations to converge and adapt to topology change, showing the advantages of the sophisticatedly designed scaling matrices. Fig.5c shows the change of total cost subject to universally scaled input rates r i (d, m), with other parameters fixed. The performance advantage of SGP has a rapid growth as the network getting more congested, especially against LPR.
To further illustrate why SGP outperforms baselines significantly with congestion-dependent cost, we define L data and L result as the average travel distance (hop number) of data packages from input to computation, and that of result packages from generation to being delivered, respectively.
In Fig. 5d, we compare L data , L result for SGP over different universal a m with other parameters fixed. The trajectories suggest that the average computation offloading distance grows with a m . Namely, for tasks generating more result with unit input data, SGP tends to compute them nearer to the destination. Considering that when a m 1, the network is highly congested mainly due to the result flow, thus the optimal strategy is to offload computation closer to destinations in order to reduce the result transmission distance and mitigate such congestion, in which case L data is large and L result is small. Note that the trajectories also imply that the speed of growth of L data and descent of L result are low when a m is small. This is because when little result flow is generated, the network is lightly congested and the computation cost dominates the total cost, our algorithm tends to offload large portion of computation to the servers. However when a m is sufficiently large, the transmission cost overwhelms computation cost, then SGP speeds up shifting computation sites closer to destination. The above behavior demonstrates the underlying optimality of our proposed method, namely reaching a "balance" among the cost for data forwarding, result forwarding and computation, and therefore optimizes the overall cost. As a comparison, LPR does not consider these aspects, the solution hardly changes with a m , implying the cost of forwarding results could grow extremely high with large a m .

VI. CONCLUSION
We propose a novel joint routing and computation offloading model incorporating the result flow, partial offloading and multi-hop routing for both data and result. This is also the first flow model analysis of computation offloading adopting congestion-dependent link cost and arbitrary network topology.We propose a total cost minimization problem to decide optimal routing-computation strategy. We optimally solve this non-convex problem by providing necessary and sufficient optimality conditions, and devise a fully distributed and scalable algorithm that reaches the global optimal.