AutoSAC: automatic scaling and admission control of forwarding graphs

There are a number of works considering the problem of controlling virtual resources within data centers, and specifically for virtual network functions. However, many of them focus on orchestration, i.e., how the virtual resources should be mapped onto the physical hardware. Shen et al. [3] develop a management framework, vConductor, for realizing end-to-end virtual network services. In [4], Moens and De Turk develop a formal model for resource allocation of virtual network functions. A slightly different approach is taken by Mehraghdam et al. [5] where they define a model for formalizing the chaining of forwarding graphs using a context-free language. They solve the mapping of the forwarding graphs onto the hardware by posing it as a MIQCP.

Scaling of virtual network functions is however studied by Mao et al. [6] where they develop a mechanism for auto-scaling resources in order to meet some user specified performance goal. Recently, Wang et al. [7] developed a fast online algorithm for scaling and provisioning VNFs in a data center. However, they are not considering timing-sensitive applications with deadlines for the packets moving through the chain, which is done by Li et al. [8] where they present a design and implementation of NFV-RT that aims at controlling NFVs with soft real-time guarantees, allowing packets to have deadlines.

The enforcement of an end-to-end deadline for a sequence of jobs is however addressed by several works, possibly under different terminologies. Di Natale and Stankovic [9] propose to split the E2E deadline proportionally to the local computation time or to divide equally the slack time. Later, Jiang [10] used time slices to decouple the schedulability analysis of each node, reducing the complexity of the analysis. Such an approach improves the robustness of the schedule, and allows to analyze each pipeline in isolation. Serreli et al. [11, 12] proposed to assign local deadlines to minimize a linear upper bound of the resulting local demand bound functions. More recently, Hong et al. [13] formulated the local deadline assignment problem as a MILP with the goal of maximizing the slack time.

An alternate analysis was proposed by Jayachandran and Abdelzaher [14], who developed several transformations to reduce the analysis of a distributed system to the single processor case. Or in [15] where Henriksson et al. proposed a feedforward/feedback controller to adjust the processing speed to match a given delay target.

Every packet that enters the service-chain must be processed by all of the functions in the chain within a certain end-to-end (E2E) deadline, denoted D ^{m a x} . This deadline can be split into local deadlines D _i (t), one for each function in the chain, such that the packet should not spend more than D _i (t) time-units in the i th function. Should a packet miss its E2E deadline, it is considered useless. It is thus favorable to use admission control to drop packets that have a high probability of missing their deadline in order to make room for following packets. The goal of the admission controller is to guarantee that the packets that make it through the service-chain do meet their E2E deadline. It is assumed to be possible to do admission control at the entry of every function in the chain.

Packets are admitted into the buffer of function F _i based on the admittance flag α _i (t) ∈{0,1}. If α _i (t) = 1 incoming packets are admitted into the buffer, and if α _i (t) = 0 they are rejected. We define the residual rate ρ _i (t) to be the rate by which packets are admitted into the buffer:

At any time instance, function F _i has \(m_{i}(t) \in \mathbb {Z}^{+}\) instances up and running. Each instance is capable of processing packets and corresponds to a virtual machine, a container, or a process running in the OS. It is possible to control the number of running instances by sending a reference signal \(m_{i}^{\text {ref}}(t) \in \mathbb {Z}^{+}\) to the service controller. However, as explained in Section 1, it takes some time to start/stop instances since an instantiation of the service is always needed. We denote this as the time overhead Δ _i . Hence, the number of instances running in the i’th function at time t is The time-overhead is assumed to be symmetric here, but in the real-world it is usually faster to start an instance than it is to stop one. However, for increased readability they are considered equal in this work. It should be noted that it is straight forward to extend the theory to account for an asymmetric time-overhead.

An instance is expected to be able to process packets at an expected service rate of \({\bar {s}_{i}}\) pps. However, as described in Section 1, the true capacity of the instance will differ from the expected one since there might be other loads running on the infrastructure (i.e., the physical machine). Hence, the true capacity of the j th instance in the i th function is given by where ξ _i,j (t) is the machine uncertainty for the j th instance in the i th function. It is given by where \({{\xi }_{i}^{\text {lb}}}\) and \({{\xi }_{i}^{\text {ub}}}\) are lower and upper bounds of this machine uncertainty, assumed to be known. The machine uncertainty is also assumed to be fairly constant during the lifetime of the instance. Using this, one can express the true capacity of the i th function in the service-chain as which together with the average machine uncertainty can be written as \({s^{\text {cap}}_{i}}(t) = m_{i}(t)\times ({\bar {s}_{i}} + {\hat {\xi }_{i}}(t))\). Note that it would be natural to allow the time-overhead Δ _i to also have some uncertainty. However, such uncertainty can be translated into a machine uncertainty.

The packets in the buffer are stored and processed in a FIFO manner. Once a packet reaches the head of the queue the load balancer will distribute it to one of the instances in the function. Note that this is done continuously due to the fluid approximation. The rate by which the load balancer is distributing packets, and thus by which the function is processing packets, is defined as the service rate where ρ _i (t) is residual rate given by Eq. 1 and q _i (t) is the number of packets in the buffer: where \(P_{i}(t) = {{\int }_{0}^{t}} \rho _{i}(x) {\mathrm {d}x}\) is the total amount of packets that has been admitted into function F _i , and \(S_{i}(t) = {{\int }_{0}^{t}}s_{i}(x) {\mathrm {d}x}\) is the total amount of packets that has been served by function F _i . Furthermore, the total amount of packets that has reached the i th function is given by \(R_{i}(t) = {{\int }_{0}^{t}}r_{i}(x) {\mathrm {d}x}\).

The time that a packet that exits function F _i at time t has spent inside that function is denoted the function delay d _i (t): The expected time that a packet entering the i th function at time t will spend in the function before exiting is defined as the expected function-delay \({\bar {d}_{i}}(t)\) Equation 8 can be interpreted as finding the minimum time τ ≥ 0 such that S _i (t + τ) = P _i (t), or in other words such that at time t + τ the function will have processed all the packets that have entered the function at time t.

Computing the expected function-delay \({\bar {d}_{i}}(t)\) requires information about m _i (t) and \({\hat {\xi }_{i}}(t)\) for the future, whereas computing the expected function delay \({{d}_{i}^{\text {ub}}}(t)\) requires information about m _i (t) for the future. Information about m _i (t) up until time t +Δ _i is always known since \(m_{i}(t+{\Delta }_{i})=m_{i}^{ref}(t)\) and \(m_{i}^{ref}(x)\) is known for x ∈ [0, t]. It is therefore possible to compute the expected function delay \({\bar {d}_{i}}(t)\) whenever it is shorter than the time-overhead Δ _i (which will be used later in Section 3 when deriving the admission controller and the service controller).

Note that the (expected) function delay does not distinguish between queueing delay and processing delay. In [17], Google profiled where the latency in a data center occurred and showed that 99% of the latency (≈85 μs) occurred somewhere in the kernel, the switches, the memory, or the application. It is very difficult to say exactly which of this 99% is due to processing or queueing, hence they are considered together as the function delay.

The n functions in the service-chain are concatenated with the assumption of no loss of packets in the communication channel between them. Therefore, the input of function F _i is exactly the output of function F _i−1: Finally, no communication latency between the functions is assumed. However, it is possible to account for it, and would be necessary should the different functions reside in different locations, i.e. different data centers. However, adding a communication latency is straightforward, and if such a communication latency (say C) were to be constant between the functions one could easily account for it by properly decrementing the end-to-end deadline: \(\tilde {D}^{\max }= {D^{\max }} - C\), and then use the framework developed in this paper.

The goal of this paper is to derive a service-controller and an admission-controller that guarantees that packets that pass through the service-chain meet their E2E deadline. This should be done using as few resources as possible while still achieving as high throughput as possible. This is captured in a simple, yet intuitive utility function u _i (t). Later in Section 3, the utility function is used to derive an automatic service- and admission controller, denoted AutoSAC.

Every request that enters the service chain has an end-to-end deadline \({D^{\max }}\). It has to pass through every function in the chain within this time. Furthermore, each function can impose a local deadline D _i (t) for the packet entering the i th function at time t. One can therefore use either the local deadline to do a decentralized admission control at the entry of each of the functions in the chain, or the global deadline for a centralized admission control. In this work, we will use a decentralized approach, shown below, but will also derive a policy for a centralized admission control in Section 3.2.1; however, only the decentralized policy will be evaluated in Section 4.

For the decentralized admission control, each function can compare the local deadline with the upper bound of the expected delay \({{d}_{i}^{\text {ub}}}(t)\) it will take a new packet to pass through the function. If the worst-case expected delay is larger than the local deadline the admission controller should drop the packet. This results in the following policy for the admittance-flag α _i (t): where the upper bound on the expected function delay \({{d}_{i}^{\text {ub}}}(t)\) is given by This is the worst case of the expected delay given by Eq. 8, i.e., when every instance is processing packets at the lower bound of its possible service-rate, hence leading to the upper bound on the expected delay. One should note here that in order to compute the upper bound (15) one need information about m _i (x) for x ∈ [t, t + τ]. However, as mentioned earlier, as long as τ ≤Δ _i this information is available since the number of instances running at time t is decided by the control signal computed Δ _i time units ago, i.e. \(m_{i}(t) = m_{i}^{ref}(t-{\Delta }_{i})\), implying that m _i (x) is known for x ∈ [0,t +Δ _i ]. This is illustrated in Fig. 6 where P _i (t) shows the cumulative amount of packets that has been let into the function, and S _i (t) the cumulative amount of served packets up until time t. From time t until t +Δ _i , it shows a shaded blue region, highlighting that the exact service is uncertain in this area. However, it is possible to compute an upper bound \(S_{i}^{\mathsf {ub}}(t) = S_{i}(t) + {\int }_{t}^{t+\tau } m_{i}(x)\times ({\bar {s}_{i}} + {{\xi }_{i}^{\text {ub}}}) dx\) and a lower bound \(S_{i}^{\mathsf {lb}}(t) = S_{i}(t) + {\int }_{t}^{t+\tau } m_{i}(x)\times ({\bar {s}_{i}} + {{\xi }_{i}^{\text {lb}}}) dx\) of this uncertainty region and hence a lower bound and an upper bound on the expected delay.

The goal for the service-controller is to find \(m_{i}^{ref}(t)\) such that the utility function is maximized once the reference signal is realized in Δ _i time-units, i.e., such that u _i (t +Δ _i ) is maximized. In this section, it will be assumed that the utility function used is the one defined in Eq. 11; later in Section 3.3.1, it will be derived for the alternative utility function (13). Recall that the utility function (11) is given by As explained in the introduction of this section, the input load is assumed to change relatively slowly over a time interval of a few milliseconds. Hence, one can approximate since the goal of both the admission controller and the service controller is to keep d _i (t) in the order of milliseconds or less. Therefore, it is possible to approximate the utility function with Furthermore, the service rate s _i (t) can be approximated to be either at the capacity of the function, \({s^{\text {cap}}_{i}}(t)\), or at the input rate r _i (t) where the \(\min \) is used since the function cannot process packets at a faster rate than what they are entering the function for a prolonged period of time. Likewise, it cannot process packets at a rate higher than the capacity of the function when the input were to be higher than this. This leads to the utility function being approximated as With \({s^{\text {cap}}_{i}}(t)\) given by Eq. 3 and the average machine uncertainty \({\hat {\xi }_{i}}(t)\) given by Eq. 4 the utility function can finally be approximated as

Since the goal is to find \(m_{i}^{ref}(t)\) in order to maximize u _i (t +Δ _i ), one needs knowledge of \({\hat {\xi }_{i}}(t+{\Delta }_{i})\) and r _i (t +Δ _i ) which is not available. However, one can assume that the machine uncertainty will be fairly constant during Δ _i time-units such that \({\hat {\xi }_{i}}(t+{\Delta }_{i}) \approx {\hat {\xi }_{i}}(t)\). Furthermore, one has to estimate the future input-rate to the function. For the first function, F ₁, this can be done by using the derivative of the (preferably low-pass filtered) input-rate: For the succeeding functions, i = 2,…,n, the input-rate will change in a step-wise fashion and can therefore not approximate it with the expression above. However, since r _i (t) = s _i−1(t) and m _i−1(x) is known for x ∈ [0, t +Δ _i−1] (with t being the current time), one could estimate the future input-rate \({\hat {r}_{i}}(t)\) with Note that \({s^{\text {cap}}_{i-1}}(t+{\Delta }_{i-1})\) is used here, instead of \({s^{\text {cap}}_{i-1}}(t+{\Delta }_{i})\). The reason is that if Δ _i >Δ _i−1 one does not have enough information to compute \({s^{\text {cap}}_{i-1}}(t+{\Delta }_{i-1})\). However, one can use the assumption that Δ _i ≈Δ _i−1. Furthermore, since one can summarize the predicted input \({\hat {r}_{i}}(t)\) as

With this, one can define \(\kappa _{i}(t) \in \mathbb {R}^{+}\) to be the real number of instances needed to exactly match the predicted incoming rate:

The control signal, i.e., the number of instances that should be started, \(m_{i}^{ref}(t)\) can then be found by solving where \(x\in \mathbb {Z}^{+}\) is the number of instances and κ _i (t) given by Eq. 24. Here, one can see that the first case of the above equation is maximized when x is as large as possible, but since this case is only valid when x ≤ κ _i (t) it leads to x = ⌊κ _i (t)⌋. Similarly, the second case is maximized when x is as small as possible, and since this case is valid for x ≥ κ _i (t) it leads to x = ⌈κ _i (t)⌉, leading to the final control-law: where again \(\kappa _{i}(t) = \frac {{\hat {r}_{i}}(t)}{{\bar {s}_{i}}+{\hat {\xi }_{i}}(t)}\) is the real number of machines that is necessary to exactly match the predicted incoming traffic.

There are several interesting properties captured by the admission controller and service controller presented in this section. First of all, the admission controller (14) ensures, by design, that every packet that is admitted into a function, and thus exits the function, meets its deadline. Therefore, no packets that exit the service-chain will miss their end-to-end deadline.

The service-controller given by Eq. 25 captures both the feedback used from the true performance of the instances (when computing \({\hat {\xi }_{i}}(t)\)) as well as feedforward information about future input coming from functions earlier in the service-chain (when computing \({\hat {r}_{i}}(t)\)). This makes it robust against machine uncertainties but also ensures that it reacts fast to sudden changes in the input. For instance, given a service-chain of six functions, function F ₅ will know that in Δ₄ time-units, F ₄ will have \({m^{\text {ref}}_{4}}(t)\) instances running and can thus start as many instances as needed to process this new load.

For this example, a service chain with three functions where the E2E deadline was set to 30 ms, which in turn was split into local deadlines of 10 ms for each function. The other parameters (i.e., \({\bar {s}_{i}}\), Δ _i , \({{\xi }_{i}^{\text {lb}}}\), and \({{\xi }_{i}^{\text {ub}}}\)) for every function in the service-chain are generated randomly. The expected service-rate \({\bar {s}_{i}}\) was chosen uniformly at random from the interval [100,000, 200,000] pps. The time-overhead Δ _i was drawn uniformly at random from the interval [30, 120] seconds. The machine uncertainty was chosen to be in the range of ± 30% of the expected service-rate \(\bar {s}_{i}\). The lower bound of the machine uncertainty was drawn from the interval \([-0.3{\bar {s}_{i}},\,0]\) pps and likewise, the upper bound was drawn from \([0,\,0.3{\bar {s}_{i}}]\) pps.

In Fig. 7, one can see how the service chain scales the number of instances up/down in order to react to the input load. In Fig. 8, one can see how the average utility changes over the course of the simulation. One thing to notice is that the average utility over the service chain remains stable above 0.95 despite large variations in the input.

In this section, we will evaluate AutoSAC through a Monte Carlo simulation with 15 ⋅ 10⁴ runs where it is compared against two state-of-the-art methods for auto-scaling VMs in industry; dynamic auto-scaling (DAS) and dynamic over-provisioning (DOP). However, since these two methods do not use any admission control, they are also augmented with the admission controller presented in Section 3.1. The two augmented methods are denoted by “DAS with AC” and “DOP with AC.” Hence, in total, the method presented in Section 3 is compared with four other methods.