# Adaptive DNN Surgery for Selfish Inference Acceleration with On-demand Edge
Resource

Xiang Yang, Dezhi Chen, Qi Qi, , Jingyu Wang, , Haifeng Sun, Jianxin Liao, and
Song Guo  Xiang Yang, Dezhi Chen, Qi Qi, Jingyu Wang, Haifeng Sun and Jianxin
Liao are with the State Key Laboratory of Networking and Switching Technology,
Beijing University of Posts and Telecommunications. E-mail: {yangxiang,
chendezhi, qiqi8266, wangjingyu, hfsun<EMAIL_ADDRESS>Song Guo is an
IEEE Fellow (Computer Society) and an ACM Distinguished Member with the
Department of Computing at The Hong Kong Polytechnic University. E-mail:
<EMAIL_ADDRESS>Qi Qi and Jingyu Wang are the corresponding
authors.

###### Abstract

Deep Neural Networks (DNNs) have significantly improved the accuracy of
intelligent applications on mobile devices. DNN surgery, which partitions DNN
processing between mobile devices and multi-access edge computing (MEC)
servers, can enable real-time inference despite the computational limitations
of mobile devices. However, DNN surgery faces a critical challenge:
determining the optimal computing resource demand from the server and the
corresponding partition strategy, while considering both inference latency and
MEC server usage costs. This problem is compounded by two factors: (1) the
finite computing capacity of the MEC server, which is shared among multiple
devices, leading to inter-dependent demands, and (2) the shift in modern DNN
architecture from chains to directed acyclic graphs (DAGs), which complicates
potential solutions.

In this paper, we introduce a novel Decentralized DNN Surgery (DDS) framework.
We formulate the partition strategy as a min-cut and propose a resource
allocation game to adaptively schedule the demands of mobile devices in an MEC
environment. We prove the existence of a Nash Equilibrium (NE), and develop an
iterative algorithm to efficiently reach the NE for each device. Our extensive
experiments demonstrate that DDS can effectively handle varying MEC scenarios,
achieving up to 1.25$\times$ acceleration compared to the state-of-the-art
algorithm.

###### Index Terms:

Article submission, IEEE, IEEEtran, journal, LaTeX, paper, template,
typesetting.

##  I Introduction

Over the past several years, a multitude of intelligent applications have
emerged on mobile devices, including unmanned aerial vehicles and wearable
devices. These developments are attributed to advances in deep neural network
(DNN) models [1, 2, 3, 4]. However, due to the computational limitations of
mobile devices, on-device DNN inference is often challenging. A common
workaround, referred to as DNN surgery, involves distributing the inference
task between the mobile device and a cloud server equipped with high-
performance GPUs [5, 6, 7, 8]. Under this scheme, mobile devices gather and
process raw data using early DNN layers to produce intermediate results
(_features_). These features are then forwarded to the cloud, which completes
the final computations and returns the inference results to the mobile device.

DNN surgery partitions the DNN model for deployment on both the edge and the
cloud, thereby capitalizing on the server’s computational resources. In
comparison to on-device inference [9, 10], DNN surgery accelerates the
inference task on mobile devices. Furthermore, when compared to directly
uploading raw data to the cloud [4], DNN surgery compresses and encrypts the
raw data via the processing of initial neural layers, thereby enhancing user
privacy.

However, DNN surgery does introduce communication costs between the mobile
device and the cloud, which can impact overall inference latency. Network
latency can be substantial between mobile devices and the cloud, and bandwidth
is often limited [11], leading to uncertainties in real-time inference.
Conversely, Multi-access Edge Computing (MEC) offers cloud computing
capabilities at the edge of the cellular network, thereby reducing latency and
providing high bandwidth. By moving services and applications closer to the
user, MEC improves user experiences, particularly for delay-sensitive
applications [12, 13, 14].

In this study, we enhance the DNN surgery technology by adapting it to the MEC
scenario to ensure real-time inference. Unlike an exclusively cloud-based
infrastructure, the key distinction is the highly _on-demand_ nature of MEC
server service. Given that the MEC server only caters to the computing needs
of nearby mobile devices, and the locations of these devices are uncertain, it
cannot continuously reserve idle resources for any specific device.
Consequently, the computing resources that the current MEC server can provide
for an inference request are unpredictable. However, prior research [5, 6, 7,
15, 16] has uniformly assumed a fixed amount of server-provided computing
resources for each mobile device, which is challenging to attain in the MEC
scenario.

Figure 1: Illustration of a typical MEC scenario where multiple independent
mobile devices collectively utilize the computing resources provided by a
single MEC server.

Fig. 1 depicts a typical MEC scenario where multiple independent mobile
devices are connected to the same MEC server, collectively utilizing its
computing resources. Each device executes a distinct inference task. For
instance, a virtual reality device may run YOLO [17] for object detection,
while a smartphone might employ ResNet [18] for junk mail classification.
These devices pay charges to leverage the MEC server’s computing resources and
accelerate their respective inference tasks based on specific requirements.
Each device aims to minimize its overall inference cost, including the
inference latency, associated cost of using the MEC server and so on. During
the inference process, while there is no direct interaction between devices,
their fluctuating demands (required computing resources) impact the
performance of other devices sharing the MEC server’s resources.

Implementing DNN surgery within the MEC scenario presents several challenges.
The mobile environment is characterized by a high level of complexity, with
devices utilizing various DNN models, a diversity of computing resources and
uplink rates, and ultimately, distinct demands. Moreover, each mobile device
only care about its overall inference cost, and can enter or exit the MEC
server’s service area unpredictably. (1) _The centralized scheduling of these
selfish mobile devices to accommodate their varying demands proves
challenging._ Preceding algorithms [6, 7] necessitate each mobile device to
have precise knowledge of the available computing resources that the server
can provide. However, the server’s workload fluctuates constantly due to the
dynamic demands of mobile devices. (2) _For mobile devices, making decisions
under unpredictable server workload conditions is difficult._ Further, the
varying required computing resources impact the choice of DNN partition
strategy, and vice versa. Additionally, the characteristics of DNN models used
in inference tasks pose further obstacles. Firstly, DNNs comprise a broad
variety of neural layers, each with distinct computational and communication
overheads. Secondly, contemporary DNN models are structured as directed
acyclic graphs (DAGs), not chains. Therefore, (3) _determining the optimal
required computing resources and partition strategy for a given mobile device
at the same time is complex._

We propose the _Decentralized DNN Surgery_ (DDS) framework to address these
challenges. DDS ascertains each mobile device’s demand through a resource
allocation game. In this game, each device requests a portion of computing
resources from the MEC server at a base price. If the total requested
resources surpass the MEC server’s capacity, the server raises its service
price for profit purposes. Consequently, each mobile device’s demand
influences others through the MEC server’s service price, necessitating a
compromise among devices. Each device’s DNN and corresponding partition
strategy are formulated as a DAG and an edge cut of the DAG, respectively. The
allocated computing resources from the MEC server are employed to identify the
best partition strategy by establishing a latency graph based on the original
DNN graph and applying a min-cut algorithm on the latency graph. This paper
demonstrates the equivalence between the minimum edge cut and the optimal
partition strategy. We deduce the existence of a unique Nash Equilibrium (NE)
for all mobile devices and propose an iterative algorithm executed on every
mobile device to efficiently converge to the NE.

DDS is a lightweight framework necessitating minimal communication among
mobile devices and virtually no computational overhead. Furthermore, DDS has
an $O(1)$ computational complexity as the number of mobile devices
participating in the resource allocation game increases. Thus, it can be
readily deployed in most real-world applications. We evaluate DDS on a
simulated cluster with up to 100 mobile devices. The experimental results
reveal that DDS improves throughput by $1.25\times$ compared to state-of-the-
art algorithms.

In summary, the following contributions are offered in this paper:

  * •

Adaptation of DNN surgery to MEC scenarios where multiple mobile devices share
computing resources, filling a gap in the current literature on DNN surgery
algorithms.

  * •

Formulation of DNN surgery with multiple devices as a resource allocation
game, from which the existence of a unique NE is deduced.

  * •

Development of the Decentralized DNN Surgery (DDS) framework which adaptively
selects the best demand for computing resources and the optimal partition
strategy for each mobile device.

  * •

Evaluation of the proposed DDS framework through extensive simulations,
demonstrating superior performance in comparison to existing algorithms.

##  II Background

In this section, we provide a brief overview of the essential concepts related
to the DNN model and DNN surgery.

###  II-A DNN as a Graph

Early DNNs, such as LeNet [19], AlexNet [20], and VGG [21], were composed of a
series of contiguous basic neural layers, including convolutional layers,
pooling layers, and fully connected layers. However, to achieve superior
performance, modern DNN architectures, including ResNet [18], Inception [22],
and Visual Transformer [23], are constructed from a sequence of meticulously
designed blocks, superseding the use of individual neural layers. As a result,
these model structures bear a greater resemblance to directed acyclic graphs
(DAGs) than to chains, as illustrated in Fig. 2. The left part of the figure
depicts the chain structure of VGG16, while the right side showcases the graph
structures of Inception [22]. Each neural layer in a chain structure has, at
most, one input and output layer. In contrast, layers in a graph structure can
connect to multiple input or output layers. As such, the number of potential
partition strategies for DNNs with graph structures significantly exceeds that
for DNNs with simple chain structures.

Figure 2: DNNs with chain and graph structures.

###  II-B DNN Surgery

Mobile devices can collect vast amounts of data but often lack sufficient
computational resources to execute real-time inference locally. Conversely,
uploading raw data to server introduces impractical network latency. DNN
surgery addresses this issue by offloading part of the DNN inference
computation to the mobile device. As raw data passes through neural layers,
features are extracted and become significantly smaller in size than the
original data [6, 24]. Therefore, uploading intermediate features incurs lower
network latency compared to raw data. Moreover, this approach reduces the
computational load on the MEC server and encrypts the original data within the
intermediate features, thereby preserving user privacy. However, modern DNN
structures are highly complex, and computation and communication overheads
vary across different neural layers. Given the diverse requirements of
numerous mobile devices, the main challenge lies in determining the optimal
DNN partition strategy.

##  III System Model

This section outlines the system model in three distinct steps: (1)
Formulating the cost function for the inference task when an optimal partition
strategy is given; (2) Representing the partition strategy as a cut and
identifying the optimal partition with a fixed allocation of computing
resources from the MEC server; (3) Proposing a resource allocation game to
determine the optimal resource demand for each mobile device.

###  III-A Cost Function for Inference

We utilize a directed acyclic graph (DAG), denoted as
$\mathcal{G}:<\mathcal{V},\mathcal{E}>$, to construct the DNN employed by the
mobile device. Here,
$\mathcal{V}:\left\\{v_{1},\cdots,v_{i},\cdots,v_{n}\right\\}$ represents the
neural layers within $\mathcal{G}$, with $v_{1}$ and $v_{n}$ symbolizing the
source and sink vertices, respectively. Furthermore,
$\mathcal{E}:\left\\{e:(u,v)|u,v\in\mathcal{V}\right\\}$ signifies the data
flow within $\mathcal{G}$, where an edge $(u,v)$ indicates that the output of
layer $u$ serves as the input for layer $v$.

DNN surgery involves formulating a partition strategy to identify an edge cut,
denoted as $\mathcal{C}$. Removing $\mathcal{C}$ splits the original graph
$\mathcal{G}$ into two disjoint segments. The segment containing the source
vertex is deployed on local mobile devices ($\mathcal{G}^{l}$), while the
segment containing the sink vertex is executed on the MEC server
($\mathcal{G}^{s}$). Note that $\mathcal{G}^{l}$ and $\mathcal{G}^{s}$ may be
empty, indicating that the entire DNN is executed either on the MEC server or
the local mobile device.

Upon receiving raw input data, the mobile device initially processes the data
locally through its partial DNN ($\mathcal{G}^{l}$), then forwards the
intermediate feature and partition strategy ($\mathcal{C}$) to the server. The
MEC server computes the final output of $\mathcal{G}$ using $\mathcal{G}^{s}$
and dispatches the result back to the mobile device. The total inference
latency ($T$) consists of three components: the local mobile device’s
inference latency ($T^{l}$), the transmission time of the intermediate feature
($T^{t}$), and the server-side inference latency ($T^{s}$). Analogous to [6,
24], we train a regression model for each device, considering both the
required computing resources of different layers and the computing capacity of
the device to predict the execution time.

These components are formulated as follows. Let
$\mathcal{D}:\left\\{d_{1},d_{2},\cdots,d_{n}\right\\}$ represent all mobile
devices utilizing the same MEC server ($s$). The term $E(d_{i})$, where
$E:\mathcal{D}\to R$, denotes the computing capacity of device $d_{i}$,
expressed in _FLOPS_ (Floating Operations Per Second). Additionally,
$f(v_{i})$, where $f:\mathcal{V}\to R$, signifies the required _FLOPs_
(Floating Operations) of a neural layer $v_{i}$. The edge computing latency
for device $d_{i}$ can be represented as:

$T^{l}(d_{i}):=\alpha_{i}\frac{\sum_{v_{j}\in\mathcal{G}^{l}}f(v_{j})}{E(d_{i})}$
(1)

where $\alpha_{i}$ is the parameter of the trained regression model.

In a similar vein, let $g(d_{i})$, where $g:\mathcal{D}\to{R}$, denote that
device $d_{i}$ has allocated $g(d_{i})$ computing resources from the MEC
server. The computing latency $T^{s}$ on the server is:

$T^{s}(d_{i},g(d_{i})):=\alpha_{s}\frac{\sum_{v_{j}\in\mathcal{G}^{s}}f(v_{j})}{g(d_{i})}.$
(2)

Here, $\alpha_{s}$ represents the regression model parameter on the server.

Regarding the transmission time $T^{t}$, it is expressed as follows:

$T^{t}(d_{i}):=\frac{\sum_{e_{i}\in\mathcal{C}_{i}}o(e_{i})}{b(d_{i})}$ (3)

where $o:\mathcal{E}\to R$ denotes the feature size of each edge $e_{i}$ and
$b:\mathcal{D}\to R$ is the bandwidth of device $d_{i}$.

The total inference latency $T$ under a specific partition strategy
$\mathcal{C}$ can be represented as $T:=T^{l}+T^{t}+T^{s}$. If $g(d_{i})$ is
fixed, there exists an optimal partition strategy $\mathcal{C}^{\star}$ which
minimizes the total inference latency $T$. We denote the minimum inference
latency as $T^{\star}$.

Due to the service of the MEC server, each mobile device also incurs a charge
for the service. Let $\beta(g(d_{i}))$ represent the charge if $g(d_{i})$
computing resources are used. The overall cost function of the inference task
for each mobile device can be formulated as:

$\mathcal{L}(d_{i},g(d_{i})):=T^{\star}(d_{i},g(d_{i}))+\gamma\beta(g(d_{i})),$
(4)

which comprises the optimal inference latency and the service charge. Here,
$\gamma$ is a hyperparameter.

###  III-B Defining the Partition Strategy as a Cut

Figure 3: Illustration of latency graph $\mathcal{\hat{G}}$. $t_{s}$
represents the server inference latency for layer $v_{i}$, while $t_{l}$
denotes the local inference latency on the mobile device. $t_{s}^{i}$ and
$t_{s}^{o}$ denote the transmission time of input data and inference result,
respectively.

Identifying the optimal inference latency $T^{\star}$ is equivalent to
determining the optimal partition strategy $\mathcal{C}^{\star}$. This can be
achieved by constructing a specific directed acyclic graph (DAG)
$\mathcal{\hat{G}}:<\mathcal{\hat{V}},\mathcal{\hat{E}},\phi>$ derived from
the original DAG $\mathcal{G}$, where $\phi:\mathcal{\hat{E}}\to R$ represents
the capacity of every edge. We refer to $\mathcal{\hat{G}}$ as the _latency
graph_ and construct it using the following steps:

  1. 1.

For each edge $e_{i}\in\mathcal{E}$, assign its capacity as
$\frac{o(e_{i})}{b(d_{i})}$, which corresponds to the network latency for
uploading the feature of edge $e_{i}$.

  2. 2.

For every vertex $v$ with multiple outgoing vertices, split $v$ into two
vertices $v^{\prime}$ and $v$. Add a new edge $(v^{\prime},v)$ and set its
capacity to $o((v,u))$. For each $(v,u)$, adjust its capacity to $\infty$.

  3. 3.

Introduce four virtual vertices $l$, $s$, $i$, and $o$. The vertices $l$ and
$s$ denote the local mobile device and the MEC server, respectively. The
vertices $i$ and $o$ are special vertices representing the captured raw data
and the final output, respectively.

  4. 4.

Add two edges $(l,i)$ and $(i,v_{1})$. The capacity of $(l,i)$ is the network
latency for uploading the entire raw data, and the capacity of $(i,v_{1})$ is
set to $\infty$. Add two edges $(l,o)$ and $(v_{n},o)$. The capacity of
$(l,o)$ is the network latency for sending the final inference result to the
mobile device, and the capacity of $(o,v_{n})$ is set to $\infty$.

  5. 5.

For each vertex $v_{i}\in\mathcal{G}$, add two edges $(l,v_{i})$ and
$(v_{i},s)$. The capacity of edge $(l,v_{i})$ is assigned to
$\alpha_{s}\frac{f(v_{i})}{g(d_{i})}$, representing the computing latency for
layer $v_{i}$ on server $s$. For edge $(v_{i},s)$, its capacity is assigned to
$\alpha_{i}\frac{f(v_{i})}{E(d_{i})}$, denoting the local computing latency.

It is worth noting that compared with [6], we add new vertices $i$, $o$ and
related edges. The vertex $i$ and edge $(i,v_{1})$, whose capacity is
$\infty$, ensure that the raw data is always captured in the mobile device.
Similarly, the edges $(l,o)$ and $(v_{n},o)$ ensure that the MEC server
returns the inference results once the final layer $v_{n}$ is deployed on the
MEC server. Furthermore, any vertex $v$ with multiple successors is replaced
with $(v,v^{\prime})$ to prevent redundant calculations during the estimation
of network transmission time for $v$. Without these constraints, the partition
strategy could be suboptimal.

The construction of a latency graph can be elucidated with a simple DNN graph
with four vertices, as depicted in Fig. 3. Vertices $v_{1}$ and $v_{4}$ act as
the source and sink, respectively. The blue edge cut in Fig. 3 represents a
partition strategy where $v_{1}$ are executed on the mobile device, while
$v_{2}$, $v_{3}$ and $v_{4}$ are processed on the server. The capacity of
$(v_{1},v_{1}^{\prime})$ equates to the network latency of the partition
strategy. Notably, we replace $v_{1}$ with $(v_{1},v_{1}^{\prime})$, differing
from the original DNN graph, to prevent the blue edge cut from passing through
$(v_{1},v_{2})$ and $(v_{1},v_{3})$. The cumulative capacity of these edges
would be twice the actual transmission. The edge cut includes edges
$(v_{1},s)$, whose capacity represents the local inference latency $T^{l}$.
The remaining edges, $(l,v_{2})$, $(l,v_{3})$ and $(l,v_{4})$, denote the
server latency. Hence, the inference latency $T$ can be expressed as a
summation of edge capacities:

$T(d_{i},g(d_{i}))=\sum_{e_{i}\in\mathcal{\hat{C}}}\phi(e_{i}),$ (5)

where $\mathcal{\hat{C}}$ is an edge cut of latency graph $\mathcal{\hat{G}}$.
The corresponding partition strategy $\mathcal{C}$ can be symbolized as
$\mathcal{\hat{C}}\cap(\mathcal{E}\cup{(i,v_{1})})$.

Each partition strategy $\mathcal{C}$ for model $\mathcal{G}$ corresponds to
an edge cut $\mathcal{\hat{C}}$ in the latency graph $\mathcal{\hat{G}}$. The
corresponding inference latency of $\mathcal{C}$ is the sum of the capacities
of edges in $\mathcal{\hat{C}}$. However, it cannot be assured that any edge
cut of latency graph $\mathcal{\hat{G}}$ is a valid partition for the original
graph $\mathcal{G}$. The edge cut represented by the red line in Fig. 3 also
segregates $\mathcal{\hat{G}}$ into two disjoint parts that contain either the
source or sink vertex, thus constituting a valid edge cut. However, for the
original graph $\mathcal{G}$, it places $v_{1}$ on the server but its
successor $v_{2}$ on the mobile devices. Such a partition strategy lacks
practical feasibility.

To address this, we introduce the concept of a valid cut:

######  Definition 1 (Valid Cut).

Let $\mathcal{\hat{C}}$ be an edge cut for the latency graph
$\mathcal{\hat{G}}$ that partitions the original DNN $\mathcal{G}$ into two
segments, $\mathcal{G}^{l}$ and $\mathcal{G}^{s}$. We deem $\mathcal{\hat{C}}$
a valid cut if $u\in\mathcal{G}^{s}\Rightarrow
v\in\mathcal{G}^{s},\forall(u,v)\in\mathcal{\hat{C}}\cap\mathcal{E}$.

Given that the objective of DNN surgery is to minimize inference latency, the
minimum edge cut $\mathcal{\hat{C}^{\star}}$ of graph $\mathcal{\hat{G}}$ is
the primary concern. Fortunately, we can establish that:

######  Theorem 1.

If $\mathcal{\hat{C}^{\star}}$ is the minimum edge cut of the latency graph
$\mathcal{\hat{G}}$, then it must also be a valid cut for the DNN graph
$\mathcal{G}$.

###### Proof.

A simple proof sketch is provided here. An important property of
$\mathcal{\hat{C}^{\star}}$ is that for all vertices $v_{i}\in\mathcal{G}$,
the ratio $\frac{\phi((l,v_{i}))}{\phi((v_{i},s))}$ equals
$\frac{\alpha_{i}E(d_{i})}{\alpha_{s}g(d_{i})}$. We examine this property in
two scenarios.

If $\alpha_{i}E(d_{i})\geq\alpha_{s}g(d_{i})$, the minimum edge cut is
equivalent to the set comprising all edges connected to $s$. This conforms to
our definition and implies that the entire graph is placed on the local
device.

If $\alpha_{i}E(d_{i})\geq\alpha_{s}g(d_{i})$, suppose
$\mathcal{\hat{C}^{\star}}$ is the minimum edge cut. If
$\mathcal{\hat{C}^{\star}}$ is not a valid cut, there must exist an edge
$(u,v)\in\mathcal{\hat{C}^{\star}}$ such that $u\in\mathcal{G}^{s}$ and
$v\in\mathcal{G}^{l}$ according to Definition 1. As $u,v\in\mathcal{V}$ and
$\mathcal{G}$ is a DAG, there must exist a path $p={v,\cdots,v_{n}}$ that
starts from $v$, with $v_{n}$ being the sink vertex of $\mathcal{G}$. This
path $p$ can be extended into a smaller DAG with $v$ as the source vertex,
which we denote as
$\mathcal{G}^{\prime}=<\mathcal{V}^{\prime},\mathcal{E}^{\prime}>$. Since
$v\in\mathcal{G}^{l}$, we let
$\Delta\mathcal{V}=\mathcal{V}^{\prime}\cap\mathcal{V}^{l}$ denote the
vertices that are part of both $\mathcal{G}^{\prime}$ and $\mathcal{G}^{l}$.
We then construct a new edge cut, $\mathcal{\hat{C}}^{\prime}$, by removing
$\Delta\mathcal{V}$ from $\mathcal{G}^{l}$ and adding it to $\mathcal{G}^{s}$.
The new edge cut $\mathcal{\hat{C}}^{\prime}$ adds edges $(l,v_{i})$ and
removes edges $(v_{i},v_{n})$ for all $v_{i}\in\Delta\mathcal{V}$. It also
removes edges that connect $\Delta\mathcal{V}$ to the remaining part of the
original graph $\mathcal{G}$, representing the additional network latency. As
$\alpha_{i}E(d_{i})\geq\alpha_{s}g(d_{i})$, the total capacity of the removed
edges exceeds that of the added edges. Consequently, the total capacity of
edges in $\mathcal{\hat{C}}^{\prime}$ is smaller than
$\mathcal{\hat{C}^{\star}}$. However, this conclusion contradicts our
assumption that $\mathcal{\hat{C}^{\star}}$ is the minimum edge cut.
Therefore, $\mathcal{\hat{C}^{\star}}$ must be a valid cut. ∎

In the light of Theorem 1, we can assure that executing a min-cut algorithm on
the latency graph $\mathcal{\hat{G}}$ derived from a given DNN $\mathcal{G}$
will yield a valid and optimal partition strategy that minimizes the inference
latency $T$ if $g(d_{i})$ is provided.

###  III-C DNN Surgery in the Presence of Competing Devices

In a practical MEC scenario, multiple non-cooperative mobile devices are
linked to the same MEC server, which possesses finite computing resources,
denoted by $S$. Each mobile device $d_{i}$ has an optimal demand
$g^{\star}(d_{i})$ of computing resources that minimizes its individual cost
function $\mathcal{L}(d_{i},\cdot)$. However, given the finite computing
capacity $S$ of the MEC, the demands $g^{\star}i(d_{i})$ may not be
satisfiable for all devices when
$S<\sum_{d_{i}\in\mathcal{D}}g^{\star}_{i}(d_{i})$. Economically, the MEC
server is inclined to increase the service price when demand surpasses supply,
primarily for profit maximization (for instance, the on-demand instance
provided by AWS).

Suppose the base unit price of computing resources provided by the MEC server
is $1$, and each mobile device $d_{i}$ has a budget $a_{i}$ for renting
computing resources. If the sum of $a_{i}$ from all devices surpasses the
limit $S$, the current MEC server’s corresponding business entity will
proportionally elevate the price to
$\frac{\sum_{a_{i}\in\mathcal{A}}a_{i}}{S}$. Here,
$\mathcal{A}=\left\\{a_{1},\cdots,a_{N}\right\\}$ constitutes the set of all
the budgets from mobile devices. Consequently, the actual allocated computing
resource $g(a_{i},\mathcal{A})$ for device $d_{i}$ from MEC server can be
expressed as follows:

${g}(a_{i},\mathcal{A}):=\left\\{\begin{array}[]{cl}\frac{a_{i}}{\sum_{a_{j}\in\mathcal{A}}a_{j}}S&\sum_{a_{j}\in\mathcal{A}}a_{j}>S\\\
a_{i}&otherwise.\end{array}\right.$ (6)

To simplify the following description, we denote $g(a_{i},\mathcal{A})$ as
$g_{i}$. The cost function Eq. (4) under the dynamic pricing scenario can be
rewritten as:

$\mathcal{L}(d_{i},a_{i},\mathcal{A}):=T^{\star}(d_{i},g_{i})+\gamma a_{i}.$
(7)

The charge function $\beta(\cdot)$ in Eq. (4) as a linear function in this
context.

Every mobile device is self-interested, aiming to minimize their cost function
$\mathcal{L}(d_{i},a_{i},\mathcal{A})$ without concerning the performance of
others. However, each self-centered mobile device has to find a compromise
with others when $S<\sum_{d_{i}\in\mathcal{D}}g^{\star}_{i}(d_{i})$, since the
selection of $a_{i}$ influences each other through $\mathcal{A}$.

For instance, the unit price $\frac{\sum_{a_{i}\in\mathcal{A}}a_{i}}{S}$ will
escalate if all devices opt to raise their budgets to acquire more computing
resources, consequently augmenting the cost for every mobile device. In such a
case, the problem evolves into a non-cooperative game involving $N$ players.

######  Definition 2 (Resource Allocation Game $\Gamma$).

$N$ players allocate resources from a limited source $S$. All players choose
their budgets $a_{i}$, and the final allocated resources $g_{i}$ for them
follow Eq. (6). Each player’s objective is to minimize its cost function
$\mathcal{L}(d_{i},a_{i},\mathcal{A})$.

Different mobile devices have varying $a_{i}$. Devices with lightweight DNNs
tend to utilize fewer computing resources to diminish service charges, while
others may allocate more resources to expedite inference tasks. A crucial
problem in game $\Gamma$ is the existence of a Nash Equilibrium that
accommodates the demands of heterogeneous mobile devices:

######  Definition 3 (Nash Equilibrium).

A strategy vector
$\mathcal{A}^{\star}=\left\\{a^{\star}_{1},\cdots,a^{\star}_{N}\right\\}$ is
considered a Nash Equilibrium (NE) of the defined game $\Gamma$ if
$a^{\star}_{i}$ is the optimal solution of the respective optimization problem
of (7), with $a_{j}$ fixed to $a_{j}^{\star}$ for all $a_{j}\neq a_{i}$.

##  IV Analysis

In this section, we establish the existence of a unique NE for the game
$\Gamma$ as defined in Definition 2.

###  IV-A Problem Overview

In practice, a large number $N$ of heterogeneous mobile devices connect to the
same MEC server to accelerate their inference tasks. These devices exhibit
significant disparities in terms of computing capacities $E(d_{i})$, network
uplink rates $b(d_{i})$, and inference tasks $\mathcal{G}_{i}$. As a result, a
direct analysis of the strategy vector $\mathcal{A}$ becomes challenging due
to _the curse of dimensionality_.

To mitigate this, we introduce a term
$A:=\frac{\sum_{a_{j}\in\mathcal{A}}a_{j}}{S}$, representing the current unit
price of MEC service when $A>1$. The resource allocation $g_{i}$ for mobile
device $d_{i}$ defined in Eq. (6) can be reformulated as:

${g}(a_{i};A):=\frac{a_{i}}{\max{(A,1)}}$ (8)

where $\max(A,1)$ signifies the current MEC service unit price. Each mobile
device’s optimization problem is thus to minimize its cost
$\mathcal{L}(d_{i},{a}_{i};A)$. The introduction of $A$ brings two significant
advantages: (1) _The existence of NE $\mathcal{A}^{\star}$ is equivalent to
the existence of the fixed point $A$, as $a^{\star}_{i}$ can be derived from
Eq. (6) and Eq. (7) once $A$ is known_, simplifying the mathematical analysis.
(2) _Compared to obtaining the strategy vector $\mathcal{A}$, acquiring the
value of $A$ from the server is more straightforward for a mobile device_,
hence making the practical implementation lightweight.

###  IV-B The Property of the Cost Function

We deploy a simple DNN with a structure identical to the one in Fig. 3,
containing four neural layers, to a mobile device connected to a MEC server.
Fig. 4 illustrates the cost function $\mathcal{L}(d_{i},a_{i};A)$ with an
increasing $\frac{a_{i}}{S}$. The blue line represents the inference latency
cost $T^{\star}(d_{i},g_{i})$, the orange line depicts the service charge
$\beta(a_{i})$, and the pink line indicates the overall cost
$\mathcal{L}(d_{i},{a}_{i};A)$. The blue and pink lines can be divided into
three segments, as shown in Fig. 4.

Each segment symbolizes a different partition strategy $\mathcal{C}$. Strategy
A (St. A) indicates that the entire DNN is executed locally, and
$\mathcal{C}=\left\\{(v,s)|\forall v\in\mathcal{G}\right\\}$. Since different
$a_{i}$ values only affect the value of $t_{c}$ (the blue lines in Fig. 3),
they do not impact the mincut value when devices perform local inference. As
$a_{i}$ increases, the inference latency of layers on the server decreases.
Segment St. B illustrates the cost when layers $v_{1}$ and $v_{2}$ are
executed locally and the remaining layers are executed on the server. The
corresponding partition strategy $\mathcal{C}$ is
$\\{(v_{1},v_{1}^{\prime})\\}$. As the allocated computing resource increases,
the inference latency continues to decrease. The overall cost also declines,
albeit at a slower rate, due to the increasing value of the charge function.
Segment St. C represents all layers being assigned to the server, and
$\mathcal{C}=\\{(l,v)|\forall v\in\mathcal{G}\\}$.

(a)

(b)

Figure 4: The properties of the cost function
$\mathcal{L}(d_{i},a_{i},\mathcal{A})$ with varying parameter $a_{i}$. The
x-axis displays the value of $\frac{a_{i}}{S}$. (a) The changing of service
charge $\gamma a_{i}$ and inference latency $T^{\star}(d_{i},g_{i})$ with
different parameter $a_{i}$. (b) The changing of the cost function value
$\mathcal{L}(d_{i},a_{i},\mathcal{A})$ with varying parameter $a_{i}$.

Here we focus on giving an accurate expression of cost function $\mathcal{L}$.
From the above observation, $\mathcal{L}(d_{i},a_{i};A)$ is non-convex and
non-smooth at these points that the optimal partition strategies switch. Since
the cost function $\mathcal{L}(d_{i},a_{i};A)$ is composed by the inference
latency function $T^{\star}(d_{i},a_{i})$ and the charge function
$\beta(a_{i})$. In Eq. (7), $\beta(a_{i})$ is set to be a linear function.
Therefore, we mainly discuss $T^{\star}(d_{i},a_{i})$ here, which returns the
minimum edge cut value of a latency graph $\mathcal{\widehat{G}}$ defined in
Section III-B.

For any graph $\mathcal{\hat{G}}:=<\mathcal{\hat{V}},\mathcal{\hat{E}},\phi>$,
the minimum edge cut problem can be formulated with the following integer
programming [25]:

$\begin{array}[]{cl}\lx@intercol\hfil\min\sum_{e\in\mathcal{\hat{E}}}\phi(e)z_{e}\hfil\lx@intercol\\\
\lx@intercol\hfil\text{ s.t. }\hfil\lx@intercol\\\ w_{v}+z_{e}=1&\forall
e:(s,v)\in\mathcal{\hat{E}}\\\ w_{v}-w_{u}+z_{e}=0&\forall
e:(u,v)\in\mathcal{\hat{E}},u\neq l,v\neq s\\\ -w_{u}+z_{e}=0&\forall
e:(u,t)\in\mathcal{\hat{E}}\end{array}$ (9)

where $\mathbf{w}:\\{w_{v}\\}\in R^{|\mathcal{\hat{V}}|-2}$ and
$\mathbf{z}:\\{z_{e}\\}\in R^{|\mathcal{\hat{E}}|}$ are two vectors that every
element $z_{e},w_{v}\in\left\\{0,1\right\\}$, and there is no $w_{l}$ or
$w_{s}$ for source or sink vertex in $\mathbf{w}$. If the edge $e$ in the edge
cut $\mathcal{\widehat{C}}$, we have $z_{e}=1$. Hence, every edge cut
$\mathcal{\widehat{C}}$ corresponds to a certain $\mathbf{z}$. Similarly,
$w_{v}=1$ indicates that vertex $v$ is in the same set with the sink $s$,
otherwise, it is with the source $l$.

Let $\mathcal{\hat{E}}^{\prime}:=\\{(l,v)|\forall v\in\mathcal{\hat{V}}\\}$
denote all the edges that represent the inference latency if layer $v$ is
deployed on the MEC server. The cost function $\mathcal{L}(d_{i},a_{i};A)$ can
be expressed as:

$\begin{array}[]{cl}\lx@intercol\hfil\min\left\\{\sum_{e_{i}\in\mathcal{\hat{E}}-\mathcal{\hat{E}}^{\prime}}\phi(e_{i})z_{e_{i}}+\sum_{e_{j}:(l,v)\in\mathcal{\hat{E}}^{\prime}}\frac{f(v)}{g(a_{i};A)}z_{e_{j}}\right\\}+\gamma
a_{i}\hfil\lx@intercol\\\ \lx@intercol\hfil\text{ s.t. }\hfil\lx@intercol\\\
w_{v}+z_{e}=1&\forall e:(s,v)\in\mathcal{\hat{E}}\\\
w_{v}-w_{u}+z_{e}=0&\forall e:(u,v)\in\mathcal{\hat{E}},u\neq l,v\neq s\\\
-w_{u}+z_{e}=0&\forall e:(u,t)\in\mathcal{\hat{E}}\text{.}\end{array}$ (10)

We will not attempt to directly solve the equation, as integer programming is
NP-complete. Eq. (10) is only used for mathematical analysis.

######  Lemma 1.

The optimal $a_{i}^{\star}$, which minimizes the cost function
$\mathcal{L}(d_{i},\cdot;A)$ with a fixed $A$, is given by
$a_{i}^{\star}=\sqrt{\frac{c_{i}^{\star}\max(A,1)}{\gamma}}$, where
$c_{i}^{\star}=\sum_{e:(l,v)\in\mathcal{\hat{E}}^{\prime}}f(v)z_{e}^{\star}$
and $z_{e}^{\star}\in\\{0,1\\}$ denotes whether $e$ is included in the minimum
edge cut.

###### Proof.

Since $\mathcal{L}(d_{i},a_{i};A)$ is a piecewise function and is
undifferentiable at the piecewise points, we first demonstrate that the
optimal $a_{i}^{\star}$ that minimizes $\mathcal{L}$ cannot be at these
differentiable points. If $a_{k}$ is a piecewise point that minimizes
$\mathcal{L}$, then the left derivative $\mathcal{L}^{\prime}({a}^{-}_{k})<0$
and right derivative $\mathcal{L}^{\prime}({a}^{+}_{k})>0$. Note that the
piecewise point also implies a switch in the optimal partition strategy
$\mathcal{C}^{\star}$. However, the first order derivative of
$\gamma\beta^{\prime}(\cdot)=\gamma>0$ holds for every $a_{i}$, hence
$T^{\star^{\prime}}(a^{-}_{k})<\beta^{\prime}(a_{k})<0$. If the partition
strategy $\mathcal{C}$ does not switch at $a_{k}$, there must exist a small
$\Delta a$ such that $T^{\star}(g(a_{k}+\Delta
a;A))>\widetilde{T}^{\star}(g(a_{k}+\Delta a;A))$, where $\widetilde{T}$
denotes the inference latency if the strategy $\mathcal{C}^{\star}$ does not
switch. Since $T^{\star}$ should return the minimum inference latency,
$a_{i}^{\star}$ cannot be the piecewise point. In addition, $a_{i}=0$ implies
that device $d_{i}$ does not participate in the game $\Gamma$ and makes no
contribution to $A$, and $a_{i}=S$ implies there is only one player in the
game. Both cases contradict our assumptions, thus the location of optimal
$a_{i}^{\star}$ must be differentiable.

For the optimal $a_{i}^{\star}$, the cost function
$\mathcal{L}(d_{i},{a}i^{\star};A)$ can be represented as
$\frac{c^{\star}_{i}}{g(a_{i}^{\star};A)}+k+\gamma a_{i}^{\star}$, where
$k=\sum_{e_{i}\in\mathcal{\hat{E}}-\mathcal{\hat{E}}^{\prime}}\phi(e_{i})z_{e_{i}}^{\star}$
is a constant. By setting $\mathcal{L}^{\prime}(d_{i},{a}_{i}^{\star};A)=0$,
we derive $a_{i}^{\star}=\sqrt{\frac{c_{i}^{\star}\max(A,1)}{\gamma}}$. ∎

###  IV-C Existence of a Unique Nash Equilibrium

The existence of a unique Nash Equilibrium (NE) in game $\Gamma$ can be
established by constructing a contraction mapping on $A$ and applying the
Banach fixed-point theorem [26]. We use a cumulative distribution function
$F:[0,1]\to[0,1]$ to describe the distribution of $a_{i}$. If all $d_{i}$ are
arranged in a specific order, such as sorted by descending local computing
resources, $F$ can be defined as $F(s;A):=\frac{\sum_{s}a(d_{i},A)}{AS}$,
where the indices of these devices $d_{i}$ are less than $sN$.

The interpretation of $F(s;A)$ is that a $s$ percentage of mobile devices
contributes a $F(s;A)$ percentage income to the MEC server when the current
unit price is $A$. With the cumulative distribution function $F$, we can
deduce that:

######  Lemma 2.

If $\gamma>\frac{c^{\star}}{4S^{2}}$, then $F(s;\cdot)$ is a contraction
mapping with respect to $A$, where $c^{\star}:=\max{c^{\star}_{i}}$.

###### Proof.

From the characterization of $a_{i}$ revealed by Lemma 1, we can consider
$a_{i}$ as a function of $a(d_{i},A)$. We begin by differentiating
$a(d_{i},A)$ with respect to $A$, and the first-order condition shows that
$\frac{\mathrm{d}a(d_{i},A)}{\mathrm{d}A}\leq\sqrt{\frac{c^{\star}_{i}}{4A\gamma}}<\sqrt{\frac{c^{\star}_{i}}{4\gamma}}<\sqrt{\frac{c^{\star}}{4\gamma}}$,
where $c^{\star}$ is a constant representing the maximum of all
$c^{\star}_{i}$. If we set $\gamma>\frac{c^{\star}}{4S^{2}}$, we obtain
$\frac{\mathrm{d}a(d_{i},A)}{\mathrm{d}AS}<\sqrt{\frac{c^{\star}}{4\gamma
S^{2}}}<1$ for every $d_{i}$. Hence, for every $A,s,h>0$ and
$0<k=\sqrt{\frac{c^{\star}}{4\gamma S^{2}}}<1$, we have:

$\begin{gathered}F(s;A\\!+\\!h)\\!-\\!F(s;A)\\!=\\!\frac{\sum_{s}{a(d_{i},A\\!+\\!h)}}{(A\\!+\\!h)S}-\\!\frac{\sum_{s}{a(d_{i},A)}}{AS}\leq
kh\text{.}\end{gathered}$

Thus, $F(s,\cdot)$ is a contraction mapping. ∎

Now, using Lemma 2 and the Banach fixed-point theorem [26], the existence of a
unique NE can be deduced:

######  Theorem 2 (Equilibrium of $A$).

There exists a unique Nash Equilibrium $A^{\star}$ for game $\Gamma$.

Theorem 2 indicates that mobile devices can agree on a unit service price
$A^{\star}$. Given the known cost function (10),
$a_{i}^{\star}=\arg\min(\mathcal{L}(d_{i},\cdot;A^{\star}))$ for each mobile
device. Therefore, we can obtain the corresponding strategy vector
$\mathcal{A}^{\star}$ for game $\Gamma$.

##  V Decentralized DNN Surgery

In this section, we present our proposed Decentralized DNN Surgery framework
which adaptively adjusts the demand of each mobile device and chooses the best
partition strategy in a decentralized manner.

###  V-A Analysis of Convergence Procedures

While Theorem 2 demonstrates the existence of a unique Nash Equilibrium (NE)
for mobile devices, finding procedures that converge to NE remains
challenging. Such procedures have been identified only for specific game
classes: potential games, 2-player zero-sum games, among a few others [27,
28]. However, numerous problems, including 2-player zero-sum, are generally
_hopelessly impractical to solve_ [29] due to their PPAD-hard nature [30, 31].
We analyze the resource allocation game $\Gamma$ proposed in this paper,
demonstrating its PPAD-hard characteristics.

######  Theorem 3.

The game $\Gamma$ proposed in this paper is PPAD-hard.

###### Proof.

The result can be easily inferred by showing that a degenerate version of game
$\Gamma$ resembles a 2-player general-sum game, which is established as PPAD-
hard [31]. A key property of a 2-player general-sum game is the uncertainty of
the total payoff. In other words, a player’s payoff does not necessarily bear
a direct or inverse proportion relationship with the other player’s payoff.
Suppose there are only two mobile devices in $\Gamma$. Given the complexity of
the DNN structure, the cost function of game $\Gamma$ is nonconvex. Thus, the
cumulative cost function values of these mobile devices are unpredictable. For
instance, if one device opts for a significant portion (99%) of computing
resources from the MEC server, both devices stand to lose due to the higher
price of the MEC service. Conversely, if one device chooses not to use MEC
service (0%), the payoff of this device could either increase or decrease,
depending on the specific DNN and device configuration. However, the other
device will invariably benefit from the decrease in service price. ∎

###  V-B Iterative Approximation Algorithm

1

Input: An initial $a_{i}^{0}$ for the mobile device $d_{i}$

2

3

4Function  _Optimization(__)_ :

5 Generate DAG $\mathcal{G}$ using given DNN;

6 Send $a_{i}^{0}$ to the server;

7 Query the server to get the value of $A^{0}$;

8 for  _$t\leftarrow[0\cdots T]$_ do

9 if  _$a_{i}^{t}=0$_ then

10 if  _perform locally inference for a while_ then

11 Query the server to get the value of $A^{t}$;

12 Run a grad search for $a_{i}^{t+1}$;

13

14 else

15 Estimate $g_{i}^{t}$ with Eq. (8);

16 Build the latency graph $\mathcal{\hat{G}}$;

17 Generate partition strategy $\mathcal{C}$ and $c_{i}(a_{i}^{t},A^{t})$ ;

18 if  _$c_{i}(a_{i}^{t},A^{t})=0$_ then

19 $a_{i}^{t+1}\leftarrow 0$;

20 Inference(_$\mathcal{C},0$_)

21 else

22 Update $a_{i}^{t+1}$ using Eq. (11) and Eq. (12);

23 $A^{t+1}\leftarrow$ Inference(_$\mathcal{C},a_{i}^{t+1}$_);

24

25Function  _Inference(_$\mathcal{C},a_{i}^{t+1}$_)_:

26 if  _$a^{t}_{i}=0$_ then

27 Executing inference task $\mathcal{G}$ locally;

28

29 else

30 $\mathcal{G}_{l}\leftarrow$ partition the model $\mathcal{G}$ using
$\mathcal{C}$;

31 Executing inference task using $\mathcal{G}_{l}$;

32 Upload $\mathcal{C}$, output of $\mathcal{G}_{l}$ and $a_{i}^{t+1}$ to
server;

33 Receive inference result and $A^{t+1}$ from server;

34

Algorithm 1 Iterative approximation algorithm on device $i$

Theorem 3 highlights the challenge of identifying an algorithm capable of
precisely determining the value of NE. Consequently, we adopt a gradient-based
iterative algorithm to approximate NE during inference. Beginning with an
initial $a_{i}^{0}$, the algorithm’s core concept involves each mobile device
$d_{i}$ updating its $a_{i}^{t}$ based on the term $A^{t}$ at iteration $t$.
The modification of $a_{i}^{t}$ subsequently triggers changes in $A^{t+1}$
during the next iteration. This process iterates until both $a_{i}$ and $A$
converge.

The choice of a gradient-based algorithm is justified for several reasons.
Firstly, gradient-based algorithms have showcased remarkable effectiveness
across a wide array of empirical challenges, encompassing machine learning,
deep learning, and game theory [32], all of which frequently present complex
optimization problems. Secondly, each part in $\mathcal{L}$ can be interpreted
as the sum of a reciprocal function and a linear function, as depicted in Eq.
(10) and Fig. 4. Thus, the cost function $\mathcal{L}$ is differentiable,
except at piecewise points. The proof procedure of Lemma 1 demonstrates that
these piecewise points cannot represent the optimal $a^{\star}$. Consequently,
we can assign a subgradient value to these piecewise points, an approach
extensively adopted within the deep learning community (e.g., ReLU [33]).
Thirdly, the computation cost for a gradient-based algorithm is minimal due to
the design where a mobile device receives a scalar $A^{t}$ from the server and
does not directly interact with others. All parameters in Eq. (10) are
scalars, not tensors, thereby rendering the gradient computation lightweight.

The gradient $\nabla a_{i}$ can be calculated from Eq. (10) as follows:

$\nabla
a_{i}=\frac{\mathrm{d}\mathcal{L}}{\mathrm{d}a_{i}}=\gamma-\frac{c_{i}(a_{i},A)}{\max(1,A){g_{i}}^{2}}.$
(11)

Here,
$c_{i}(a_{i},A):=\sum_{(l,v)\in(\mathcal{\hat{E}}^{\prime}\cup\mathcal{\hat{C}})}f(v)$
is analogous to $a_{i}^{\star}$ as defined in Lemma 1. $\mathcal{\hat{C}}$
represents the min-cut of $\mathcal{\hat{G}}$ when $a_{i}$ and $A$ are given.
$c_{i}(a_{i},A)$ physically signifies the sum of FLOPs required by the layers
deployed on the MEC server, calculated using an efficient minimum edge cut
algorithm. We discuss computational complexity later in Section V-C. The
execution time of DNN inference is relatively short. For instance, YOLOv2
inference takes roughly 2s and 0.24s on the mobile device and the cloud
server, respectively [6]. The gradient-based algorithm is efficient enough and
minimally impacts inference performance.

Since the cost function is non-convex, $a_{i}$ is updated with momentum in
order to jump over the local minimum point. The update formula is written as
follows:

$\begin{array}[]{cl}\nu^{t}&=\rho\nu^{t-1}+(1-\rho)\nabla a^{t}_{i}\\\
a_{i}^{t}&=a_{i}^{t-1}-\eta\nu^{t}\text{,}\end{array}$ (12)

where $\nu^{t}$ is the momentum at iteration $t$, $\rho$ is an exponential
decay factor and $\eta$ is the learning rate.

Only using the gradient-based algorithm to update $a_{i}$ can lead to an
incorrect result. When the current $A$ is large, $a_{i}$ will decrease as
$\nabla a>0$. After updating $a_{i}$, the corresponding partition strategy may
execute the entire DNN locally, namely $c_{i}(a_{i},A)=0$. Thus, $\nabla a$
will always equal to $\gamma>0$, and $a_{i}$ will reach $0$ in the end even
though $A$ has decreased in the following iterations.

Resource Sniff is proposed to deal with this problem. When $c_{i}(a_{i},A)=0$,
the mobile device $d_{i}$ do not use the computing resource and locally
execute the inference task, namely $a_{i}=0$. The mobile device $d_{i}$ will
periodically run a grid search for $a_{i}$ after every several iterations
until a better $a_{i}>0$ is found. Since there is only one parameter $a_{i}$
during the grid search, the sniff operation is also quite lightweight. The
full version of the iterative approximation algorithm is shown in Algorithm 1.
Note the term $A^{t+1}$ is received along with the current inference result
(Line 19), thus DDS introduces nearly zero additional communication
considering the size of the floating number $A$.

###  V-C Computational Complexity

In this section, we examine the computational complexity of the DDS framework.
The DDS workflow incorporates two additional computational costs beyond the
inference task. Firstly, the computation associated with estimating the
computing resources $\hat{a}_{i}^{t}$ (as per Line 11 in Algorithm 1) and
updating the requested computing resource $a_{i}^{t+1}$ for the subsequent
inference (Line 18 in Algorithm 1). Secondly, the computation of determining
the minimal edge cut $\mathcal{C}$, essentially the optimal partition
strategy, for DNN graph $\mathcal{G}$.

The first computational cost involves Eq. (8), (11), and (12). All parameters
including $a_{i}$, $A$, $\gamma$, and $c_{i}(a_{i},A)$ are scalars, not
vectors. This characteristic stems from DDS’s decentralized design: MEC server
aggregates the actions of all other devices (corresponding to $A$), and each
mobile device communicates solely with the MEC server. Thus, in comparison to
other $N$-Player games [32], the decision-making process of mobile devices in
DDS only interacts with $A$, provided by the MEC server. This feature suggests
that the computational complexity of the first cost is $O(E)$, remaining
constant as the number of mobile devices increases. Furthermore, the
calculations in Eq. (8), (11), and (12) involve only a few concise algebraic
operations, in contrast to a small fully-connected layer in a DNN, which could
necessitate millions of such operations. Therefore, the computational cost of
these equations can be considered negligible.

The second computational cost involves calculating the minimum cut of the
latency graph $\mathcal{\hat{G}}$ from the given DNN $\mathcal{G}$. As this
computation does not include other mobile devices, the complexity relates
solely to the properties of $\mathcal{G}$. The classic Boykov’s algorithm [34]
presents a complexity of $O\left((V+E)V^{2}\right)$, where $V$ and $E$ denote
the number of vertices and edges in the latency graph $\mathcal{\hat{G}}$
respectively. Due to the property of the DNN graph containing multiple cutting
vertices, which divide the DNN into several subgraphs (e.g., ResBlock,
InceptionBlock), the computational complexity has been reduced to
$O\left((k+1)(\hat{V}+\hat{E})\hat{V}^{2}\right)$, where $k$ represents the
number of cutting vertices in DNN $\mathcal{G}$. $\hat{V}$ and $\hat{E}$
signify the number of vertices and edges in these subgraphs. For a more
detailed exploration, we direct the reader to [7]. The decision time of the
optimized minimal edge cut algorithm is approximately 0.1 seconds even on
resource-limited devices like RaspberryPi [7].

In summary, the computational complexity of DDS framework is
$O\left(E+(k+1)(\hat{V}+\hat{E})\hat{V}^{2}\right)$ for DNN $\mathcal{G}$, and
$O(1)$ for the number of mobile devices $N$.

##  VI  Performance Evaluation

In this section, we evaluate the performance of DDS.

###  VI-A Environment Setup

TABLE I: Metrics Of Different DNNs  Model | VGG11 | ResNet34 | ResNet50 |  ViT
---|---|---|---|---
Vertices | 15 | 55 | 73 | 26
Edges | 14 | 57 | 75 | 32
GFLOPs | 7.63 | 3.68 | 4.12 | 3.47

####  VI-A1  Platform

The DDS framework is implemented using the PyTorch deep learning framework
[35]. gRPC [36] is utilized for efficient communication between mobile devices
and the MEC server. The source code of PyTorch is modified based on [37] to
automatically convert DNNs into a DAG structure. Evaluations of the DDS
convergence performance with a large scale (up to 100) of mobile devices are
simulated on a machine equipped with an Intel Xeon E5-2660 CPU and 256 GB
memory. The configurations of these mobile devices, such as bandwidth,
computing resource, and inference tasks, are randomly chosen from $5\sim 10$
Mbps, $10\sim 20$ GFLOPS, and several DNN models. The computing power of the
MEC server is set to 1.2 TFLOPS.

####  VI-A2 Tasks

We employ four real-world DNNs: VGG11 [21], ResNet34 [18], ResNet50 [18], and
the Visual Transformer (ViT) [23]. All input data for these models are sampled
from the ImageNet dataset [38]. The metrics of these DNNs, including the
number of vertices (neural layers), edges, and required GFLOPs, are listed in
Table I.

####  VI-A3 Baseline

Three baselines are used in the experiment:

  * •

Edge Only (EO): The entire DNN is executed locally on the mobile device.

  * •

Server Only (SO): All captured raw data are directly uploaded and the DNN is
executed on the MEC server.

  * •

Dynamic Adaptive DNN Surgery (DADS): A min-cut algorithm is used to find the
best partition strategy [6] for fixed computing resources.

The computing resource allocated to each mobile device for the three baselines
is set to $\frac{S}{N}$ during inference.

(a)

(b)

Figure 5: (a) The value of $A^{t}$ with different initial values $a_{0}$ at
different iterations from the perspective of a specific device. (b) The local
inference latency and inference latency after using the service of MEC server
for every mobile device.

###  VI-B Convergence Performance

To examine the convergence performance of our proposed iterative algorithm, we
simulate a scenario with 100 mobile devices, all sharing the same initial
budget $a^{0}$. Given the asynchronous nature of our algorithm across the
devices, we randomly select one device, $d_{i}$, and track the value of
$A^{t}$ as perceived by $d_{i}$ at varying iterations. We carry out
simulations under four distinct settings of the initial $a^{0}$ and plot the
results in Fig. 5a.

While gradient-based algorithms do not guarantee convergence to the unique NE,
our simulation demonstrates that mobile devices with differing initial $a^{0}$
values rapidly reach consensus on $A^{t}$ within a few iterations. In our
experiment, this consensus is the service price of $1.09$, which all mobile
devices accept. Notably, the convergence process is expedient; it requires
fewer than 25 iterations for convergence among 100 mobile devices when $a^{0}$
is set to $0$ or $0.01S$. Even when $a^{0}$ is assigned impractical values,
such as $0.05S$ and $0.1$, convergence is still achieved within 50 iterations.
These results underscore the efficacy of the proposed iterative approximation
algorithm.

When $a^{0}$ is initially set to $0.1S$ or $0.05S$, $A^{t}$ declines rapidly
at the onset of iterations due to the high charge, $\beta(a_{i}^{t})$. If
$a^{0}=0$, all mobile devices incrementally explore the MEC server’s computing
resources and select an appropriate $a_{i}^{t}$ for iteration, causing $A^{t}$
to gradually increase initially. It is worth noting that $A^{t}$ exhibits a
fluctuating pattern before finally reaching the NE during iterations, as the
momentum strategy is employed for updating $a^{t}_{i}$. This momentum strategy
expedites $A^{t}$ optimization when the optimization direction is unambiguous
(during the early stages of $0.1S$ and $0.05S$) and enhances convergence
performance by circumventing some local minima.

###  VI-C Resource Allocation Across Various Devices

Fig. 5b provides a detailed depiction of resource allocation within the DDS,
encompassing 100 heterogeneous mobile devices. Each point within the figure
represents a mobile device. Given the diversity in uplink bandwidths
$b(d_{i})$, local computing capacities $E(d_{i})$, and inference tasks
$\mathcal{G}_{i}$ among the devices, each point encapsulates multiple
dimensions of information. The color of each point indicates the DNN
$\mathcal{G}_{i}$ assigned to device $d_{i}$. The x-axis represents the
bandwidth $b(d_{i})$ of different devices, while the y-axis of the upper
figure illustrates the inference latency if $\mathcal{G}_{i}$ is executed
locally. The lower figure displays the inference latency post-utilization of
the MEC service. The variation in inference latency between the two figures
suggests the allocation of resources from the MEC server, responding to the
diverse demands of the mobile devices.

We can find that the execution time of mobile devices differs for the four
DNNs in the top figure. The inference of VGG11 is most time-consuming and
takes between 0.5s and 0.8s. The other DNNs (ResNet34, ResNet50, and ViT) take
around 0.3s as their required GFLOPs of them are similar. Meanwhile, the
inference latency of VGG11 reduces up to 0.5s after adopting DDS. The mobile
devices with VGG11 tasks are willing to reduce the high inference latency
$T^{\star}$ with some additional service charge. The inference latencies of
ResNet34, ResNet50, and ViT also decrease, but the reduction is not as obvious
as that of VGG16. Since the GFLOPs of these DNNs are smaller than VGG11, the
gain of reducing inference latency can not remedy the increase of charge. As a
result, they use smaller computing resources.

###  VI-D Average Inference Latency

(a) Inference Latency

(b) Server Latency

(c) Network Latency

(d) Device Latency

Figure 6: Average latency trends as the number of mobile devices increases.
(a): Overall inference latency $T$. (b): Server inference latency $T^{s}$.
(c): Network latency $T^{t}$ for feature uploading. (d): Local device
inference latency $T^{l}$ on the mobile device.

We evaluate the average inference performance involving multiple mobile
devices ranging from 5 to 100. Since the MEC server capacity is limited, the
server workloads grows as the number of mobile devices increases. We capture
the time cost at each inference stage. Figure 6 illustrates the trend of the
average latency for all mobile devices using four distinct algorithms as the
number of devices increases. Figure 6a displays the overall inference latency
$T^{\star}$, which encompasses all stages. The remaining figures depict the
server inference latency $T^{s}$, network latency $T^{t}$, and local device
inference latency $T^{l}$, respectively.

The inference latency grows when the number of mobile devices increases except
for EO. Since SO uploads all data to MEC server, the performance will quickly
decrease when the workload of server grows. The latency of SO grows with a
linear rate in Fig. 6a and is longer than EO when the number of devices
exceeds $65$. DADS and DDS can adaptively adjust the partition strategy
$\mathcal{C}$, thus the growth of inference latency is slower than SO. From
Fig. 6d and Fig. 6b we can find when the workload of MEC server becomes heavy
(with $50$ devices), both algorithms gradually reduce the computation on the
server and place more computation on the mobile devices. However, when the
number of devices reaches $100$, DADS degenerates to EO. From Fig. 6c we can
find the average network latency is close to zero, which means it hardly uses
the network and executes almost entire DNN locally. But DDS still benefits
from MEC server, since the demands of every mobile device can be adaptively
adjusted. Some devices with lightweight DNN and better local computing
resources tend to reduce their demands and save server resources for more
needed ones. Thus, it achieves a better latency performance than DADS (about
$1.25\times$).

##  VII  Related Work

###  VII-A DNN Surgery

DNN surgery offers an efficient means to reduce inference latency without
sacrificing accuracy. The concept was first introduced by Neurosurgeon [5],
which delegates parts of the DNN model to a more robust cloud platform. DADS
[6] concentrates on finding optimal partition strategies for DNNs with
Directed Acyclic Graph (DAG) structures, proposing a min-cut based algorithm.
QDMP [7] notes that applying the min-cut algorithm to the entire DNN can be
time-consuming and puts forth an improved algorithm to reduce time complexity
when finding the optimal strategy. However, these efforts only consider a
single mobile device and assume that the computing resources allocated from
the server remain fixed during optimization. Some researchers have employed
multiple cooperative mobile devices to accelerate inference [39, 24, 40]. For
example, CoEdge [39] deploys the full model on each device and divides the
intermediate features. PICO [24] organizes mobile devices into an inference
pipeline by partitioning both neural layers and features. Similarly, EdgeFlow
[40] aligns with [39] but can handle models with a graph structure. Despite
these advancements, there is a dearth of research on accelerating inference
for multiple uncooperative mobile devices.

###  VII-B Task Offloading

The offloading problem for general tasks involving multiple mobile devices has
been studied for years [41, 42, 43, 44]. The task models in [41, 43, 44] are
atomic and cannot be partitioned. [44] considers the offloading problem in a
Software Defined Networking (SDN) [45] environment, with the offloading
strategy determined by a central controller. However, since the inference
typically takes less than a second, the centralized algorithm would double the
network latency as the strategy must first be dispatched to mobile devices.
[42] considers ideal offloading tasks that can be split in any proportion and
provides an algorithm to find the Nash Equilibrium directly. However, many
real-world tasks, such as inference tasks, do not satisfy this assumption.
[43] employs an iterative algorithm to find the optimal threshold that, when
the number of waiting tasks exceeds the threshold, requires devices to upload
newly arrived tasks to the server. Moreover, the problems addressed in [41,
42, 43] are convex and easier to tackle.

##  VIII  Conclusion

Current algorithms fall short in the MEC environment where numerous self-
regulating mobile devices share the computing resources offered by an MEC
server. To tackle this issue, our study reformulates the optimal partition
strategy as a min-cut of a latency graph derived from the original DNN.
Concurrently, we design a resource allocation problem to determine the optimal
demand for each diverse mobile device and deduce the existence of the unique
NE within the proposed game.

We introduce the Decentralized DNN Surgery (DDS) framework to efficiently and
adaptively obtain the NE for every device in the MEC environment. The
lightweight nature of DDS allows it to be deployed on each mobile device
without introducing any additional communication overhead. Experimental
results demonstrate the efficiency of DDS under various settings, showing a
notable increase in average inference speed by 1.25 $\times$ compared to the
state-of-the-art algorithm. Consequently, our study paves the way for a
scalable and efficient solution for DNN inference in dynamic MEC scenarios.

## References

  * [1] D. Chen, Q. Qi, Z. Zhuang, J. Wang, J. Liao, and Z. Han, “Mean field deep reinforcement learning for fair and efficient uav control,” _IEEE Internet of Things Journal_ , vol. PP, pp. 1–1, 07 2020.
  * [2] W. Koch, R. Mancuso, R. West, and A. Bestavros, “Reinforcement learning for uav attitude control,” _ACM Transactions on Cyber-Physical Systems_ , vol. 3, no. 2, pp. 1–21, 2019.
  * [3] C. Badue, R. Guidolini, R. V. Carneiro, P. Azevedo, V. B. Cardoso, A. Forechi, L. Jesus, R. Berriel, T. M. Paixao, F. Mutz _et al._ , “Self-driving cars: A survey,” _Expert Systems with Applications_ , vol. 165, p. 113816, 2021.
  * [4] J. Ren, L. Gao, X. Wang, M. Ma, G. Qiu, H. Wang, J. Zheng, and Z. Wang, “Adaptive computation offloading for mobile augmented reality,” _Proc. ACM Interact. Mob. Wearable Ubiquitous Technol._ , vol. 5, no. 4, dec 2022. [Online]. Available: https://doi.org/10.1145/3494958
  * [5] Y. Kang, J. Hauswald, C. Gao, A. Rovinski, T. Mudge, J. Mars, and L. Tang, “Neurosurgeon: Collaborative intelligence between the cloud and mobile edge,” _ACM SIGARCH Computer Architecture News_ , vol. 45, no. 1, pp. 615–629, 2017.
  * [6] C. Hu, W. Bao, D. Wang, and F. Liu, “Dynamic adaptive dnn surgery for inference acceleration on the edge,” in _IEEE INFOCOM 2019-IEEE Conference on Computer Communications_. IEEE, 2019, pp. 1423–1431.
  * [7] S. Zhang, Y. Li, X. Liu, S. Guo, W. Wang, J. Wang, B. Ding, and D. Wu, “Towards real-time cooperative deep inference over the cloud and edge end devices,” _Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies_ , vol. 4, no. 2, pp. 1–24, 2020.
  * [8] T. Mohammed, C. Joe-Wong, R. Babbar, and M. D. Francesco, “Distributed inference acceleration with adaptive dnn partitioning and offloading,” in _IEEE INFOCOM 2020 - IEEE Conference on Computer Communications_ , 2020, pp. 854–863.
  * [9] Y.-H. Chen, J. Emer, and V. Sze, “Eyeriss: A spatial architecture for energy-efficient dataflow for convolutional neural networks,” _ACM SIGARCH computer architecture news_ , vol. 44, no. 3, pp. 367–379, 2016.
  * [10] T.-J. Yang, Y.-H. Chen, and V. Sze, “Designing energy-efficient convolutional neural networks using energy-aware pruning,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 5687–5695.
  * [11] Z. Zhou, X. Chen, E. Li, L. Zeng, K. Luo, and J. Zhang, “Edge intelligence: Paving the last mile of artificial intelligence with edge computing,” _Proceedings of the IEEE_ , vol. 107, no. 8, pp. 1738–1762, 2019.
  * [12] S. Kekki, W. Featherstone, Y. Fang, P. Kuure, A. Li, A. Ranjan, D. Purkayastha, F. Jiangping, D. Frydman, G. Verin _et al._ , “Mec in 5g networks,” _ETSI white paper_ , vol. 28, no. 28, pp. 1–28, 2018.
  * [13] Z. Zhou, X. Chen, E. Li, L. Zeng, K. Luo, and J. Zhang, “Edge intelligence: Paving the last mile of artificial intelligence with edge computing,” _Proceedings of the IEEE_ , vol. 107, no. 8, pp. 1738–1762, 2019.
  * [14] V. Va, T. Shimizu, G. Bansal, and R. W. Heath Jr, “Millimeter wave vehicular communications: A survey,” _Foundations and Trends® in Networking_ , vol. 10, no. 1, pp. 1–118, 2016.
  * [15] B. Lin, Y. Huang, J. Zhang, J. Hu, X. Chen, and J. Li, “Cost-driven off-loading for dnn-based applications over cloud, edge, and end devices,” _IEEE Transactions on Industrial Informatics_ , vol. 16, no. 8, pp. 5456–5466, 2020.
  * [16] D. Yao, L. Xiang, Z. Wang, J. Xu, C. Li, and X. Wang, “Context-aware compilation of dnn training pipelines across edge and cloud,” _Proc. ACM Interact. Mob. Wearable Ubiquitous Technol._ , vol. 5, no. 4, dec 2022. [Online]. Available: https://doi.org/10.1145/3494981
  * [17] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi, “You only look once: Unified, real-time object detection,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 779–788.
  * [18] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [19] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [20] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in _Advances in Neural Information Processing Systems_ , F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, Eds., vol. 25. Curran Associates, Inc., 2012. [Online]. Available: https://proceedings.neurips.cc/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf
  * [21] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” _arXiv preprint arXiv:1409.1556_ , 2014.
  * [22] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna, “Rethinking the inception architecture for computer vision,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 2818–2826.
  * [23] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly _et al._ , “An image is worth 16x16 words: Transformers for image recognition at scale,” _arXiv preprint arXiv:2010.11929_ , 2020.
  * [24] X. Yang, Q. Qi, J. Wang, S. Guo, and J. Liao, “Towards efficient inference: Adaptively cooperate in heterogeneous iot edge cluster,” in _2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS)_. IEEE, 2021, pp. 12–23.
  * [25] L. Trevisan, “The lp of maximum flow and its dual,” http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf, Feb 2011.
  * [26] K. Ciesielski, “On stefan banach and some of his results,” _Banach Journal of Mathematical Analysis_ , vol. 1, no. 1, pp. 1–10, 2007.
  * [27] J. Hu and M. P. Wellman, “Nash q-learning for general-sum stochastic games,” _Journal of machine learning research_ , vol. 4, no. Nov, pp. 1039–1069, 2003\.
  * [28] S. Hart and A. Mas-Colell, _Simple adaptive strategies: from regret-matching to uncoupled dynamics_. World Scientific, 2013, vol. 4.
  * [29] Y. Shoham and K. Leyton-Brown, _Multiagent systems: Algorithmic, game-theoretic, and logical foundations_. Cambridge University Press, 2008.
  * [30] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou, “The complexity of computing a nash equilibrium,” _Communications of the ACM_ , vol. 52, no. 2, pp. 89–97, 2009.
  * [31] R. Mehta, “Constant rank two-player games are ppad-hard,” _SIAM Journal on Computing_ , vol. 47, no. 5, pp. 1858–1887, 2018.
  * [32] D. Balduzzi, S. Racaniere, J. Martens, J. Foerster, K. Tuyls, and T. Graepel, “The mechanics of n-player differentiable games,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 354–363.
  * [33] A. F. Agarap, “Deep learning using rectified linear units (relu),” _arXiv preprint arXiv:1803.08375_ , 2018.
  * [34] Y. Boykov and V. Kolmogorov, “An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 26, no. 9, pp. 1124–1137, 2004\.
  * [35] A. Paszke, S. Gross, F. Massa, and L. et. al., “Pytorch: An imperative style, high-performance deep learning library,” in _Advances in Neural Information Processing Systems 32_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, Eds. Curran Associates, Inc., 2019, pp. 8024–8035.
  * [36] “grpc,” https://grpc.io/, accessed: 2010-09-30.
  * [37] D. Narayanan, A. Harlap, A. Phanishayee, V. Seshadri, N. R. Devanur, G. R. Ganger, P. B. Gibbons, and M. Zaharia, “Pipedream: generalized pipeline parallelism for dnn training,” in _Proceedings of the 27th ACM Symposium on Operating Systems Principles_ , 2019, pp. 1–15.
  * [38] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _2009 IEEE conference on computer vision and pattern recognition_. IEEE, 2009, pp. 248–255.
  * [39] L. Zeng, X. Chen, Z. Zhou, L. Yang, and J. Zhang, “Coedge: Cooperative dnn inference with adaptive workload partitioning over heterogeneous edge devices,” _IEEE/ACM Transactions on Networking_ , vol. 29, no. 2, pp. 595–608, 2020.
  * [40] C. Hu and B. Li, “Distributed inference with deep learning models across heterogeneous edge devices,” in _IEEE INFOCOM 2022-IEEE Conference on Computer Communications_. IEEE, 2022, pp. 330–339.
  * [41] X. Chen, “Decentralized computation offloading game for mobile cloud computing,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 26, no. 4, pp. 974–983, 2014.
  * [42] D. Nowak, T. Mahn, H. Al-Shatri, A. Schwartz, and A. Klein, “A generalized nash game for mobile edge computation offloading,” in _2018 6th IEEE International Conference on Mobile Cloud Computing, Services, and Engineering (MobileCloud)_. IEEE, 2018, pp. 95–102.
  * [43] X. Qin, B. Li, and L. Ying, “Distributed threshold-based offloading for large-scale mobile cloud computing,” in _IEEE INFOCOM 2021-IEEE Conference on Computer Communications_. IEEE, 2021, pp. 1–10.
  * [44] M. Chen and Y. Hao, “Task offloading for mobile edge computing in software defined ultra-dense network,” _IEEE Journal on Selected Areas in Communications_ , vol. 36, no. 3, pp. 587–597, 2018.
  * [45] D. Kreutz, F. M. V. Ramos, P. E. Veríssimo, C. E. Rothenberg, S. Azodolmolky, and S. Uhlig, “Software-defined networking: A comprehensive survey,” _Proceedings of the IEEE_ , vol. 103, no. 1, pp. 14–76, 2015.