Network Slicing for Service-Oriented Networks with Flexible Routing and Guaranteed E2E Latency^††thanks: ​​​Corresponding author: Ya-Feng Liu.

Consider a communication network $\mathcal{G}=\{\mathcal{I},\mathcal{L}\}$, where $\mathcal{I}=\{i\}$ is the set of nodes and $\mathcal{L}=\{(i,j)\}$ is the set of links. The network supports a set of flows $\mathcal{K}=\{k\}$. We assume that each link $(i,j)$ has an expected delay $d_{ij}$ [9], and a total data rate upper bounded by the capacity $C_{ij}$. Let $\mathcal{V}$ be a subset of $\mathcal{I}$ denoting the set of the cloud nodes. Each cloud node $v$ has a computational capacity $\mu_{v}$ and we assume as in [4] that processing one unit of data rate requires one unit of (normalized) computational capacity. Let $S(k)$ and $D(k)$ be the source and destination of flow $k$, respectively, and suppose that $S(k),D(k)\notin\mathcal{V}$. Each flow $k$ relates to a distinct service, which is given by a SFC consisting of $\ell_{k}$ functions that have to be performed in sequence by the network:

As required in [4, 6], and [9], to minimize the coordination overhead, each function must be instantiated at exactly one cloud node. If function $f^{k}_{s}$, $s\in\mathcal{F}(k):=\{1,\ldots,\ell_{k}\}$, is processed by node $v$ in $\mathcal{V}$, we assume the expected NFV delay is known as $d_{v,s}(k)$ which includes both processing delay and queuing delay, as in [9]. For flow $k$, denote $\lambda_{0}(k)$ and $\lambda_{s}(k)$ as the service function rates before receiving any function and after receiving function $f^{k}_{s}$, respectively. Each flow $k$ is required to have an E2E latency guarantee, denoted as $\Theta_{k}$.

The network slicing problem is to determine functional instantiation of all flows and the routes and associated data rates of all flows on the routes while satisfying the SFC requirements, the E2E delay requirements, and the capacity constraints on all cloud nodes and links. In this section, we shall provide a new problem formulation of the network slicing problem which takes practical factors like coordination overhead, flexible routing, and E2E latency requirements into consideration; see Eq. (21) further ahead.

Our proposed formulation builds upon those in two closely related works [9] and [4] but takes further steps. More specifically, in sharp contrast to the formulation in [9] where only a single path is allowed to route the traffic flow of each service (between two cloud nodes processing two adjacent functions of a service), our proposed formulation allows the traffic flow of each service to transmit on (possibly) multiple paths and hence fully exploits the flexibility of traffic routing; different from that in [4], our formulation guarantees the E2E delay of all services, which consists of two types of delays: total communication delay on the links and total NFV delay on the cloud nodes. Next, we describe the constraints and objective function of our formulation in details.

We introduce the binary variable $x_{v,s}(k),~{}s=1,\ldots,\ell_{k}$, to indicate whether or not node $v$ in $\mathcal{V}$ processes function $f^{k}_{s}$, i.e.,

For simplicity of presentation as in [4], we require that each cloud node processes at most one function for each flow:

For each flow $k$, we require that each service function in the chain $\mathcal{F}(k)$ is served by exactly one cloud node, i.e.,

Since processing one unit of data rate consumes one unit of (normalized) computational capacity, we can get the node capacity constraints as follows:

Let $y_{v}\in\{0,1\}$ represent the activation of cloud node $v$, i.e., if $y_{v}=1$, node $v$ is activated and powered on; otherwise, it is powered off. Thus

We assume that there are at most $P$ paths between any pair of cloud nodes that processes two adjacent functions of a flow. In general, such an assumption on the number of paths may affect the solution’s quality. Indeed, the choice of $P$ offers a tradeoff between the flexibility of routing in the problem formulation and the computational complexity of solving it: the larger the parameter $P$ is, the more flexibility of routing and the higher the computational complexity.

Denote $\mathcal{P}=\{1,\ldots,P\}$. If cloud nodes $v_{s}$ and $v_{s+1}$ are used to host the $s$-th and $(s+1)$-th functions of flow $k$ (i.e., functions $f^{k}_{s}$ and $f^{k}_{s+1}$), respectively, and path $p$ is used to route the traffic flow, let $r(k,s,v_{s},v_{s+1},p)$ be the associated amount of the data rate. We need to introduce this variable in our formulation, as the traffic flow of each service in our formulation is allowed to transmit on (possibly) multiple paths in order to exploit the flexibility of traffic routing. In particular, if $s=0$, we assume $v_{s}=S(k)$ and if $s=\ell_{k}$, we assume $v_{s+1}=D(k)$. Notice that by (3) and the fact that $S(k),D(k)\notin\mathcal{V}$, we must have $v_{s}\neq v_{s+1}$. For each $k\in\mathcal{K}$, from the definitions of $x_{v_{s},s}(k)$, $x_{v_{s+1},s+1}(k)$, and $r(k,s,v_{s},v_{s+1},p)$, we have

Constraint (7) indicates that if the $s$-th and $(s+1)$-th functions of flow $k$ (i.e., functions $f_{s}^{k}$ and $f_{s+1}^{k}$) are hosted at cloud nodes $v_{s}$ and $v_{s+1}$, respectively, then the sum of all the data rates sent from $v_{s}$ to $v_{s+1}$ must be equal to $\lambda_{s}(k)$. We then use $z_{ij}(k,s,v_{s},v_{s+1},p)=1$ to denote that the $s$-th and $(s+1)$-th functions of flow $k$ (i.e., functions $f_{s}^{k}$ and $f_{s+1}^{k}$) are processed by cloud nodes $v_{s}$ and $v_{s+1}$, respectively, path $p$ is used to route the associated traffic flow, and link $(i,j)$ is on path $p$; otherwise, $z_{ij}(k,s,v_{s},v_{s+1},p)=0$. By definition, for all $k\in\mathcal{K}$, $p\in\mathcal{P}$, and $(i,j)\in\mathcal{{{L}}}$, we have

If $z_{ij}(k,s,v_{s},v_{s+1},p)=1$, let $r_{ij}(k,s,v_{s},v_{s+1},p)$ denote the associated amount of data rate. By definition, for each $k\in\mathcal{K}$, $p\in\mathcal{P}$, and $(i,j)\in\mathcal{{{L}}}$, we have the following coupling constraints:

The total data rates on link $(i,j)$ is upper bounded by capacity $C_{ij}$:

To ensure the functions of each flow are followed in the prespecified order as in (1), we need to introduce several constraints below. For each $k\in\mathcal{K}$, $p\in\mathcal{P}$, $v_{s},v_{s+1}\in\mathcal{{{V}}}$ with $s\in\mathcal{F}(k)\backslash\{\ell_{k}\}$, and $i\in\mathcal{{{I}}}$, we have

First, note that constraints (11), (12), and (13) are flow conservation constraints for the data rate. Second, we need another three flow conservation constraints (14), (15), and (16). To be more precise, for each pair of cloud nodes $v_{s}$ and $v_{s+1}$, considering constraints (14), (15), and (16), we only need to look at the case that $x_{v_{s},s}(k)=1$ and $x_{v_{s+1},s+1}(k)=1$ since otherwise from constraint (8), all the variables $z_{ij}(k,s,v_{s},v_{s+1},p)$ in (14), (15), and (16) must be equal to zero. Constraint (15) enforces that for every node that does not host functions $f_{s}^{k}$ and $f_{s+1}^{k}$, if one of its incoming links is used to route the flow from node $v_{s}$ to node $v_{s+1}$ on path $p$, then one of its outgoing links is also assigned for this path. Similarly, constraints (14) and (16) imply that, if function $f_{s}^{k}$ is hosted at node $v_{s}$, one of the outgoing links of node $v_{s}$ must be assigned for path $p$ and, if function $f_{s+1}^{k}$ is hosted at node $v_{s+1}$, one of the incoming links of node $v_{s+1}$ must be assigned for path $p$, respectively.

Next, we consider the delay constraints. Let $\theta(k,s,{s+1})$ be the variable denoting the communication delay due to the traffic flow from the cloud node hosting function $f^{k}_{s}$ to the cloud node hosting function $f^{k}_{s+1}$. Then, $\theta(k,s,{s+1})$ should be the largest one among the $P$ paths, i.e.,

Hence the total communication delay on the links of flow $k$, denoted as $\Theta_{L}(k)$, can be written as

Now for each flow $k$, we consider the total NFV delay on the nodes, denoted as $\Theta_{N}(k)$. This can be written as

The E2E delay of flow $k$ is the sum of total communication delay $\Theta_{L}(k)$ and total NFV delay $\Theta_{N}(k)$. The following delay constraint ensures that flow $k$’s E2E delay is less than or equal to its threshold $\Theta_{k}$:

The power consumption of a cloud node is the combination of the dynamic load-dependent power consumption (that increases linearly with the load) and the static power consumption [12]. Our objective is to minimize the total power consumption of the whole network:

In the above, the parameters $\beta_{1}$ and $\beta_{2}$ are the power consumptions of each activated cloud node and inactivated cloud node, respectively, satisfying $\beta_{1}>\beta_{2}$; the parameter $\Delta$ is the power consumption of processing one unit of data rate. From (4), the above objective function can be simplified as $(\beta_{1}-\beta_{2})\sum_{v\in\mathcal{V}}y_{v}+c,$ where $c=\beta_{2}|\mathcal{V}|+{\Delta}\sum_{k\in\mathcal{K}}\sum_{s\in\mathcal{F}(k)}\lambda_{s}(k)$ is a constant. Hence, minimizing the total power consumption is equivalent to minimizing the total number of activated cloud nodes. Based on the above analysis, we obtain the following problem formulation:

We now present some analysis results of problem (21) (without proofs due to the space reason). First, problem (21) is a MBLP (with both numbers of binary variables and linear constraints being ${\cal O}({|\mathcal{V}|}^{2}|\mathcal{L}||\mathcal{P}|\sum_{k\in\mathcal{K}}\ell_{k})$) since the bilinear terms of binary variables $x_{v_{s},s}(k)x_{v_{s+1},{s+1}}(k)$ in (7), (8), (15), and (16) can be equivalently linearized. More specifically, we can replace the bilinear term $x_{v_{s},s}(k)x_{v_{s+1},{s+1}}(k)$ by introducing an auxiliary binary variable $\omega_{v_{s},v_{s+1}}(k)$ and add the following linear constraints: $\omega_{v_{s},v_{s+1}}(k)\leq x_{v_{s},s}(k)$, $\omega_{v_{s},v_{s+1}}(k)\leq x_{v_{s+1},{s+1}}(k)$, and $\omega_{v_{s},v_{s+1}}(k)\geq x_{v_{s},s}(k)+x_{v_{s+1},{s+1}}(k)-1$. Note that the linearity of all variables in problem (21) is vital, which allows to leverage the efficient integer programming solver such as Gurobi [11] to solve the problem to global optimality. Second, problem (21) is strongly NP-hard. Therefore, the above approach can only solve problem (21) associated with small size networks. In future works, we shall develop polynomial-time heuristic algorithms for solving problem (21) to achieve the tradeoff between the performance and time complexity. Third, if we set $P=1$ in (21), then our proposed formulation reduces to that in [9]. In particular, the variables $\bm{r}_{ij}$ in (10) can be replaced by those in the right-hand side of (9) and all constraints related to the variables $\bm{r}$ (e.g., (7), (9), (11), (12), (13)) can be removed. Our proposed formulation with $P>1$ allows the traffic flows to transmit over possibly multiple paths and fully exploits the flexibility of traffic routing.

In this subsection, we show the performance of the proposed formulation by using an illustrative example.

Consider the example in Fig. 1. There are two different functions available, i.e., $f^{1}$ and $f^{2}$. Cloud node C can only process function $f^{2}$, while cloud node E can process both functions $f^{1}$ and $f^{2}$. Suppose there are two services where service I is from node A to node D with the E2E delay threshold $\Theta_{1}=4$ and service II is from node A to node B with the E2E delay threshold $\Theta_{2}=3$. Functions $f^{1}$ and $f^{2}$ need to be processed for services I and II, respectively; for each service $k$, the service function rates $\lambda_{0}(k)$ and $\lambda_{1}(k)$ are $1$; the NFV delays of both functions at (possible) cloud node C and cloud node E are $1$. Solving problem (21) with $P=2$ gives the following solution: $\begin{array}[]{l}\text{Service I}:\text{A}\rightarrow\text{B}\rightarrow\text{E~{}{(providing function $f^{1}$)}}\rightarrow\text{D},\\ \text{Service II}:\text{A}\rightarrow\text{C~{}{(providing function $f^{2}$)}}\rightarrow\text{B}.\end{array}$
Note that since the communication delay on each link $(i,j)$ is $d_{ij}=1$ (as shown in Fig. 1), and the NFV delay of each function is $1$ at cloud node C or cloud node E, the E2E delays of service I and service II in the above solution are $4$ and $3$, respectively, which satisfy the E2E latency requirements of both services.

Now, consider the case that where there is no E2E latency constraints, i.e., removing constraints (17)-(20) from problem (21). Notice that this reduces to the formulation considered in [4]. Since the objective is to minimize the number of activated cloud nodes, the obtained solution is that both functions are processed by cloud node E:
$\begin{array}[]{l}\text{Service I}:\text{A}\rightarrow\text{B}\rightarrow\text{E~{}{(providing function $f^{1}$)}}\rightarrow\text{D},\\ \text{Service II}:\text{A}\rightarrow\text{C}\rightarrow\text{E~{}{(providing function $f^{2}$)}}\rightarrow\text{D}\rightarrow\text{B}.\\ \end{array}$
For service II, it traverses $4$ links from node A to node B with a communication delay being $4$, which, pluses the NFV delay $1$, obviously violates its E2E latency constraint.

Next, suppose that there is only one service from node A to node D with the E2E delay threshold being $\Theta_{1}=4$. The considered service contains function $f^{1}$ and both of the service function rates $\lambda_{0}(1)$ and $\lambda_{1}(1)$ are $4$. If only a single path is allowed to transmit the traffic flow as in [9], no solution exists for this example due to the limited link capacity. However, in sharp contrast, using our formulation (21) with $P=2$, the traffic flow can be flexibly transmitted on multiple paths, which gives us a feasible solution as follows: first use paths $\text{A}\rightarrow\text{B}\rightarrow\text{E}$ and $\text{A}\rightarrow\text{C}\rightarrow\text{E}$ to route the flow from A to E where the data rates on both paths are $2$; after function $f^{1}$ being processed by cloud node E, route the flow to the destination node D using the link $\text{E}\rightarrow\text{D}$. This toy example clearly shows the benefit of flexible routing in our proposed formulation (21), i.e., it has a lower requirement on the link capacities of the network to support the services.

In this subsection, we present more simulation results to illustrate the effectiveness of the proposed formulation compared to those in [4] and [9].

We randomly generate a network consisting of $6$ nodes on a $100\times 100$ region in the Euclidean plane including $3$ cloud nodes. We generate link $(i,j)$ for each pair of nodes $i$ and $j$ with the probability of $0.6$. The communication delay on link $(i,j)$ is calculated by the distance of link $(i,j)$ over $\bar{d}$, where $\bar{d}$ is the average length of all shortest paths between every pair of nodes. The cloud node and link capacities are randomly chosen in $[6,12]$ and $[0.5,3.5]$, respectively. There are in total $5$ different service functions: $\{f^{1},\ldots,f^{5}\}$. Among the $3$ cloud nodes, $2$ cloud nodes are randomly chosen to process $2$ service functions of $\{f^{1},\ldots,f^{5}\}$ and the remaining one is chosen to process all the service functions. The processing delay of each function in each cloud node is randomly chosen in $[0.8,1.2]$. For each service $k$, nodes $S(k)$ and $D(k)$ are randomly chosen from the available network nodes excluding the cloud nodes; SFC $\mathcal{F}(k)$ is an ordered sequence of functions randomly chosen from $\{f^{1},\ldots,f^{5}\}$ with $|\mathcal{F}(k)=3|$; the service function rates $\lambda_{s}(k)$ are all set to $1$; and the E2E delay threshold $\Theta_{k}$ is set to $3+(6*\text{dist}_{k}/\bar{d}+\alpha)$ where $\text{dist}_{k}$ is the length of the shortest path between nodes $S(k)$ and $D(k)$ and $\alpha$ is randomly chosen in $[0,2]$. The above parameters are carefully chosen such that the constraints of problem (21) are neither too tight nor too loose.

In our simulations, we randomly generate 100 problem instances for each fixed number of services and the results presented below are based on statistics from all these 100 instances. In problem (21), we choose $P=2$. We use Gurobi 9.0.1 [11] to solve all MBLP problems.

Since the formulation in [4] does not explicitly take the latency constraints into consideration, the blue curve in Fig. (2) is obtained as follows. We solve the formulation in [4] by changing its objective into minimizing the number of activated cloud nodes and then substitute the obtained solution into the latency constraints in (20): if the solution satisfies all latency constraints, we count the corresponding problem instance feasible; otherwise it is infeasible. We can see from Fig. 2 that the number of feasible problem instances of solving our proposed formulation (21) is significantly larger than that of solving the formulation in [4]. This clearly shows the advantage of our proposed formulation (i.e., it has a guaranteed E2E Latency) over that in [4]. In addition, the flexibility of traffic routing in our proposed formulation (21) enables it to also solve a larger number of problem instances than that can be solved by using the formulation in [9]. These results further illustrate the effectiveness of our proposed formulation (21) (as compared to those in [4] and [9]).

We now show the performance of problem (21) versus the number of services. Fig. 3 is obtained by averaging the results over all feasible problem instances. We can observe from Fig. 3 that: as the number of services increases, more cloud nodes need to be activated; the average NFV delay almost keeps unchanged. The later is due to the fact that the number of functions in all services is fixed (to be 3) and the difference of NFV delays on different cloud nodes is small. However, the average communication delay (and the average total delay) increases rapidly. This is mainly due to the limited link capacity. More specifically, as the network traffic gets heavier, a traffic flow may use a path with a larger communication delay as some link’s capacity (in a path with a smaller communication delay) is not enough for the data rate.