We study online convex optimization (OCO) with switching costs and ramp constraints, which has become an important tool for modeling many classes of practical decision problems with uncertainty, including machine learning [1], networking [2], cloud computing [3] and cyber-physical systems [4]. In the type of OCO problem that we are interested in, at each time t, the environment (or adversary) reveals the input A(t). The decision maker then must choose the decision X(t) from a convex set and incurs a linear cost C t (X(t), A(t)). Additionally, there is a switching cost that penalizes the change |X(t) -X(t -1)| for each time t and/or a ramp constraint on the magnitude of the change X(t) -X(t -1). The goal is to minimize the overall cost, which is non-linear (and convex) due to the switching cost. Further, since future inputs, i.e., A(t + 1), A(t + 2), ..., A(T ), are not revealed at time t, this problem becomes an online decision problem. Clearly, this formulation is general and can model many important online decision problems. For example, in the Network Functions Virtualization (NFV) orchestration and scaling problem [5], a data center operator must decide where to instantiate Virtualized Network Functions (VNFs) on virtual machines (VMs) or containers such as Docker [6] running on servers in order to process incoming traffic. Here, A(t) represents the traffic load, which can be uncertain before time t; X(t) represents the mapping from VNFs to VMs or containers; the linear cost C t (X(t), A(t)) represents VM/container cost and/or distance cost (e.g., latency) [7]. Finally, the switching cost captures the overhead for migrating demand/state among different VNF instances and the cost of instantiating and tearing down VNF instances. As another example, in the real-time dispatch problem in power systems [8], the system operator needs to decide how to adjust the power level of the generators to balance the electricity demand. Here, A(t) represents the uncertain demand and renewable supply revealed on different buses at time t; X(t) represents the dispatch decisions of the generators; the linear cost C t (X(t), A(t)) represents the generation cost of the dispatch decisions. Finally, generators have ramp constraints so that their power output level can at most change by a given value each time.
In this paper, we aim to develop online algorithms with low competitive ratios for this type of OCO problem. Here, the competitive ratio is the maximum ratio of the cost of an online algorithm to that of the offline optimal solution (the latter assuming that all inputs are known in advance), taken over all possible input sequences. Despite the importance of OCO, there are limited results in the literature on the corresponding competitive online algorithms. Most studies of OCO focus on the regret [1], [9], [10], which is the difference between the cost of the online algorithm and the cost of the optimal static decision chosen in advance. Such a static decision, however, does not respond to inputs dynamically, and thus is not a useful reference for comparison in application scenarios such as NFV and power systems. Among those that study competitive performance against the dynamic offline optimal solution, the references [11] and [12] show that the competitive difference of their proposed algorithms are upper bounded, which implies that the competitive ratio may also be upper bounded under certain conditions. However, they do not provide a way to optimize the competitive ratio, and thus the resulting competitive ratio may still be fairly large. To the best of our knowledge, there is no systematic framework to optimize the competitive ratio of online algorithms for the type of OCO problems that this paper studies.
To address this open question, our first contribution (in Sec. III) is to develop a general and tractable framework that allow us to find online algorithms with optimized competitive ratios for this type of OCO problem. Capitalizing on the ideas from robust optimization [13], we consider the case where the future uncertain inputs, A(1), A(2), ..., A(T ), are from an uncertainty set U . In practice, such an uncertainty set U can be obtained from imprecise forecasts and historical data [8], [14]. Yet, searching among all possible online decisions appears to be intractable. Instead, in order to obtain simpler policies with reasonably good performance, we focus on affine policies, where the decision X(t) at time t is an affine function of the input A(t), i.e., X(t) = η(t) + H(t)A(t). Thus, designing an online algorithm boils down to designing the parameters η(t) and H(t) (which depends only on the uncertainty set U but not the actual inputs). Through this restriction to affine policies, we can formulate the problem of optimizing the competitive ratio as a minmax optimization problem. We call the resulting online algorithm the Robust Affine Policy (RAP). Since this optimization problem is still non-convex, we propose approximations that effectively convexify the problem and make it tractable. In this way, our proposed computational framework can be used to design online algorithms with optimized competitive ratios for OCO problems with fairly complex structures and constraints. We note that the idea of affine policies has been used in adjustable robust optimization [15] to minimize the worst-case cost. In contrast, our approach applies affine policies to minimize the competitive ratio. This approach has not been studied before and gives rise to new technical difficulties as we discuss in Sec. III.
A key feature of our proposed approach is that it can gracefully handle situations where infeasibility may arise due to hard feasibility constraints in the OCO problem. By "hard feasibility constraints," we refer to situations where, after the input A(t) is revealed at time t, no feasible decision X(t) can be found. This situation usually arises when there are both ramp constraints and demand-supply balance constraints. Specifically, due to the ramp constraint, the decision X(t) at time t cannot differ too much from X(t -1). Thus, when the demand is too high at time t, but X(t -1) was not properly chosen, there may not exist any X(t) that can meet the demand. Such a problem can occur in both power systems and NFV. In contrast, the studies in [11] and [12] do not consider such hard feasibility constraints because they do not simultaneously enforce ramp constraints and demand-supply balance constraints. As a result, their competitive guarantees would not hold when there were hard feasibility constraints. To the best of our knowledge, our proposed approach is the first to give online algorithms with optimized competitive ratios with or without such constraints.
Our second key contribution (in Sec. IV) is to resolve a dilemma between the worst-case and average-case performance. Note that while our proposed Robust Affine Policy (RAP) is optimized for the worst-case competitive ratio, it may be too conservative and thus incur high costs for average-case inputs. Other heuristic algorithms (such as RHC, i.e., Receding Horizon Control [12], discussed in Sec. V) may perform well for the average case, but produce inferior competitive ratios for worst-case scenarios. Thus, an open question is whether one can get the best of both worlds. We address this dilemma by providing a "robustification" procedure. Given any online algorithm π 0 that is perceived to have good average-case performance, we intelligently combine π 0 with RAP to produce a new online algorithm with the same worst-case competitive ratio as RAP while still attaining comparable average-case performance to π 0 . We note that this "robustification" idea was first introduced in our earlier work [14]. However, our OCO problem formulation is much more general, requiring a new robustification procedure to be developed. We use Network Functions Virtualization (NFV) [5] as a case study and simulate the robustified version of RHC. Our simulation results in Sec. V show that the robustified-RHC algorithm performs close to RHC when the uncertainty is low. When the uncertainty is high, the robustified-RHC algorithm performs significantly better, especially for worst-case inputs.
As discussed above, our work is related to robust optimization [13], [15], but differs in that we focus on a different objective of competitive ratios rather than worstcase costs. Our NFV case study is also related to the literature of NFV orchestration and scaling. However, most existing studies either assume a static model [7], [16]- [18], or provide heuristic online algorithms without any performance guarantees [19], [20]. The references [21] and [22] study online NFV orchestration and scaling, although they do not consider the distance cost (e.g., latency), which is an important cost component, especially when optimizing over multiple data centers. More recently, the reference [23] uses the regularization method to develop online algorithms for NFV orchestration and scaling over multiple data-centers. One of the key differences of our work is that we utilize partial future knowledge, i.e., in the form of an uncertainty set U , to obtain potentially smaller competitive ratios. In contrast, it is unclear how to generalize the approaches in [21]- [23] to utilize such partial future knowledge. Further, in deriving their competitive ratios, the studies in [21] and [23] do not consider constraints on the number of servers available or ramp constraints on the rerouting decisions. NFV orchestration and scaling is also related to the FL (facility location) [24] and GAP (generalized assignment problem) [25], for which competitive online algorithms have been developed. However, in NFV, the demand fluctuates (both increases and decreases) over time in both the online and offline settings. In contrast, online FL and GAP problems usually assume that new demand is sequentially added over time towards a final offline setting where all demand is present. Further, the cost constraints of OCO problems are usually more general, e.g., involving switching costs and ramp constraints. Thus, it is unclear how to apply the competitive results from this literature to OCO and online NFV orchestration and scaling problems.
We now present our model for online convex optimization (OCO) problems with linear in-stage costs, switching costs and ramp constraints.
In the OCO problem that we consider, there are T rounds of decisions, t = 1, 2, ..., T . There is a cost-function C t (X(t), A(t)) for each time t, which is a function of the input A(t) ∈ R M (e.g., traffic load) revealed by the environment at time t, and the action X(t) ∈ R N taken by the decision maker (e.g., system administrator) at time t. Throughout this paper, we assume that C t (•, •) is a linear function of (X(t), A(t)). Further, there is a switching cost β|X(t) -X(t -1)| that penalizes the change of decision at time t (hence the transpose of β is a given vector in R N ). The action X(t) must be chosen to satisfy certain constraints. We assume that one set of constraints X t (A(t)), which may depend on the input A(t), can be written as a linear inequality in (X(t), A(t)), i.e.,
where the transposes of D 1 and D 2 are in R N and R M , respectively. (As in Real Analysis, we use "∀" for "for all", and use "∃" for "there exists".) Further, there may be ramp constraints
where X n is the n-th element of X. As we will illustrate with a case study, this construction can model several types of costs and constraints. Let A(t 1 :t 2 ) denote the input sequence A(t)
At each time t, the environment reveals A(t) first. Then the decision maker picks the action X(t) and incurs the in-stage cost C t (X(t), A(t)) and the switching cost β|X(t)-X(t-1)|. Note that although C t (•, •) is linear, the switching cost still makes the whole problem convex. Further, this problem is an online problem because the decision maker does not know the future values of A(t + 1), A(t + 2), ..., A(T ) when she makes the decision X(t).
As we discussed in the introduction, the combination of the linear constraint (1) and the ramp constraint (2) may lead to infeasibility. If X(t -1) is not properly chosen, the ramp constraint limits how far X(t) can deviate from X(t -1). Then, there may not exist a feasible point that simultaneously satisfies (1) and (2). For example, this infeasibility can occur when the demand increases suddenly and the traffic cannot be rerouted as quickly to serve the demand. Thus, a key contribution of our work is to be able to deal with cases with or without such "hard infeasibility constraints."
Recall that the input A(t) is unknown to the online algorithm until time t. Intuitively, if A(t) can vary in arbitrary ways, one may have to take the most conservative decisions to avoid future infeasibility. Thus, in order to make the online decision problem practically more interesting, we introduce an uncertainty set to model the set of uncertain inputs that we care about. Specifically, we assume that the trajectory A(1), A(2), ..., A(T ) chosen by the environment must be from an uncertainty set U . We expect that this uncertainty set U can be constructed from prediction and historical data [8], [14]. Next, we describe three ways (that can be used in combination) to formulate the uncertainty set U .
(i) Day-ahead prediction: Let A DAP (1:T ) denote a predicted trajectory of A(1:T ). We may assume that the real trajectory A(1:T ) must be within a neighborhood around A DAP (1:T ),
where the upper/lower bounds are given by
and m (t) is the uncertainty level for time t.
(ii) Demand changing speed: Often, demand (e.g., traffic or renewable energy) may not change arbitrarily fast. We can model such knowledge by imposing
(iii) The different elements of A(t) may not hit the upper or lower bounds in (3) simultaneously. Thus, we can impose the following constraint (known as the "budget" constraint in the robust optimization literature [13, p. 47
Clearly, if Γ = 0, the uncertainty set only contains the dayahead prediction A DAP (1:T ). Thus, the model becomes deterministic. As Γ increases, more uncertainty will be considered.
The uncertainty set U that we use in this paper is specified by a combination of the above constraints. We note that the constraint (6) introduces temporal coupling of the inputs, which can be used to refine the near-term future uncertainty. Specifically, at any time t, A(1:t) has already been revealed to the online algorithm. Thus, the future uncertainty remaining in the interval [t + 1, T ] can be written as
As we discussed earlier, the total cost incurred by the decision maker is given by
For an online algorithm π, at each time t the decision X(t) can only be based on the already-known inputs A(1:t) and knowledge about the future uncertainty given by (8). Let C π (A(1:T )) be the total cost of algorithm π. We compare it with an offline solution that is assumed to know the entire input A(1:T ) ahead of time. We denote the cost of the optimal offline solution as C OPT (A(1:T )), which is the optimal value of the following optimization problem, min X(0:T ):(1),( 2)
Then, the competitive ratio of algorithm π, given by
is the worst-case ratio between the online cost and the offline optimal cost, over all possible inputs from the uncertainty set. We are thus interested in online solutions to OCO with small competitive ratios. Although the notions of uncertainty sets and affine policies (used later) are from the robust optimization literature [13], our objective in ( 11) is quite different. In the robust optimization literature, the objective is usually to minimize the worst-case (absolute) cost, i.e., max
Our objective of the competitive ratio, which is commonly used in the CS literature, instead focuses on a relative ratio comparing with the offline optimal solution. This difference leads to new technical difficulties in the optimization problem. In some way, competitive ratios can be viewed as less conservative than robust optimization because we do not only care about the worst-case cost.
We now use the Network Functions Virtualization (NFV) orchestration and scaling problem [5] as a case study to illustrate how our model can be used to study practical costs and constraints. We will also use it in our numerical evaluation in Sec. V. Nonetheless, the computational framework that we present later can be used for other problems, such as in power system operation [8].
We first follow the simplified NFV model in [7] (without precedence constraints). The network is modeled as a graph G(V, E). There are S servers, each of capacity W s occupying some node in V , s = 1, 2, ..., S. There are L clients, l = 1, 2, ..., L, each of which generates traffic at some node in V . Each client requires one or more Virtualized Network Functions (VNFs), e.g., firewalls, intrusion detection systems, caches and load balancers. Each VNF is indexed by a positive integer f in the set F = {1, 2, ..., F }. We use a f l (t) to denote the processing need for function f at time t due to the traffic generated by client l. Note that we can set a f l (t) = 0 if client l does not need function f . Decisions and constraints: The NFV system administrator maps the VNFs to physical servers to serve the incoming demand. Let y f s (t) denote the size (resource requirements) of VNF f at server s at time t. Let x f l,s (t) denote the amount of demand from client l that is routed to server s for processing of function f at time t. The decision X(t) in our general OCO model then corresponds to a vector [x f l,s (t), y f s (t)]. These actions must satisfy the following constraints. First, all the arriving demand needs to be served. Therefore, we must have
Second, when the demand arrives at the server s, the size of the corresponding functions that are placed on server s must be able to meet the demand. Assume that each unit-size function can serve one unit-size demand. Thus, we must satisfy
Third, resources on each server s must be able to support all functions placed there [26]. Assume that each unit-size function f needs w f s amount of resources at server s. Thus, we have
The above constraints form the linear constraint set X t (A(t)).
In-stage Costs: There are costs for resource consumption of VNFs, and distance costs for routing the demand of clients, i.e.,
) where p f s is the cost of hosting a unit of virtualized function f on server s, and d l,s is the distance (e.g., latency) cost of routing a unit of traffic load from client l to server s.
The model so far is similar to [7], which focuses on each snapshot in time, and assumes perfect knowledge of demand. In contrast, in this paper we wish to model decisions under uncertain and dynamic demand. Thus, we use an uncertainty set U as in Sec. II-B to model demand uncertainty. Note that a key benefit of NFV is that virtualized functions can be instantiated and torn down on-demand, and service can be moved across VNF instances as needed. However, such changes still incur non-negligible overhead. Specifically, because most VNFs are stateful, rerouting traffic from one VNF instance to another requires state migration [27]. Further, instantiating and tearing down VNFs incurs significant overhead. Therefore, we introduce the following additional costs and constraints.
Ramp Constraints: We may impose ramp constraints on the changes in routing decisions. If a certain amount of network bandwidth is reserved for state migration, rerouting cannot occur too fast. Such a constraint can be written as
Switching/Migration Costs: There is overhead for state migration and changes in instantiation, i.e.,
where β f 1,l,s and β f 2,s are cost parameters for state migration in rerouting and for the overhead in instantiating and tearingdown VNF instances, respectively. (Note that the absolute values |x| may also be replaced by max{x, 0} and one can still apply the proposed methodology in this paper.)
Hence, in our online NFV orchestration and scaling problem, the cost function is the sum of ( 15) and (17). Note that our model is more general than [21]- [23] because we simultaneously consider the distance costs, constraints on the available server capacity, and the ramp constraints, when we study the competitive performance.
In this section, we introduce a computationally tractable framework to attain small competitive ratios for general OCO problems with linear in-stage costs, switching costs and ramp constraints. Note that a key benefit for online decisions is that the decision at time t can be adjusted based on the new input A(t) just revealed. Thus, they can be more efficient than classical robust optimization where all decisions must be made ahead of time. This adjustability is similar to the adjustable robust optimization [13, p. 355], [15], where some decisions are made in a "wait-and-see" manner. However, searching among all possible online decisions is usually an intractable problem: each action X(t) can be an arbitrary function of the past A(1:t), and searching over such a functional space is very difficult when the problem size is large [13, p. 363], [15]. Instead, next we will borrow the idea of affine policies from [13, p.368] and [15] in order to obtain a computationally tractable framework.
Specifically, in our proposed robust affine policy (RAP), we restrict X(t) to be an affine function of A(t), i.e.,
where η(t) ∈ R N and H(t) ∈ R N ×M are determined before hand. Note that once η(t) and H(t) are determined, the online decision (18) becomes extremely simple. Instead, the complexity moves to the pre-calculation of η(t) and H(t) based on the knowledge of the uncertainty set U . Given η(t) and H(t), the cost of the online decisions can be readily calculated as
where X(1:T ) is given by (18). However, the online decisions must still satisfy both (1) and (2). In other words, we need that (1), ( 2) hold for all A(1:T ) ∈ U, given (18).
(
We can thus formulate the optimization problem for minimizing the competitive ratio as
Although affine policies have been used in [13, p. 368] and [15], using a similar approach as in the optimization problem (20) introduces new technical difficulties. Note that for each A(1:T ) ∈ U, the ratio CRAP(A(1:T )|X(0),η,H)
is convex in η, H and X(0). Thus, the inner maximization produces a convex objective in η, H, X(0) for outer minimization. However, it is unclear how to solve the inner maximization problem itself because it involves a ratio of convex functions. Next, we will show step-by-step how to optimize an upper bound of (20) via a tractable convex optimization problem.
Step-1: Even without considering the ratio, the numerator C RAP (A(1:T )|X(0), η, H) in ( 20) is convex in A(1:T ). Maximizing a convex function is in general intractable. We resolve this issue by introducing a linear upper bound on C RAP (A(1:T )|X(0), η, H) (see also [28, p. 228]). Specifically, note that the only non-linearity in C RAP (A(1:T )|X(0), η, H) is from the switching cost β|X(t) -X(t -1)| = β|η(t) + H(t)A(t)η(t -1) -H(t -1)A(t -1)|. We now introduce a new variable µ(t) ∈ R N that upper-bounds each element of this switching cost for all A(1:T ) ∈ U, i.e.,
Let CRAP (A(1:T )|η, H, µ) = T t=1 {C t (X(t), A(t)) + µ(t)}, where X(t) is given by (18). Then, C RAP (A(1:T )|X(0), η, H) ≤ CRAP (A(1:T )|η, H, µ) for all A(1:T ) ∈ U. Hence, we can obtain an upper bound of (20) by solving the following optimization problem instead min
Note that the numerator is now a linear function in A(1:T ).
Step-2: The ratio in the inner maximization problem in ( 22) is usually not a concave function of A(1:T ). Thus, it is still not obvious how to maximize the ratio. Using the following lemma from our earlier work [14], we now show that this inner maximization problem can be converted to an equivalent convex problem. Then, sup
x,y
A detailed proof is given in [29]. Note that the second supremum is a convex problem because uf ( x u ) is a convex function whenever f (x) is convex [30, p. 89]. The result of this lemma is somewhat similar to the convex transformation of linear-fractional program [30, p. 89]. However, here the denominator is non-linear, and thus Lemma 1 is more general.
We now verify that the conditions of Lemma 1 hold for (22). For condition (a), we note that C OPT (A(1:T )) is the minimum of a convex function C(X(0), X(1:T ), A(1:T )) over X(0:T ) in a convex set. Thus, C OPT (A(1:T )) is a convex function of A(1:T ) [30, p. 87]. For conditions (b) and (c), C OPT (A(1:T )) and CRAP (A(1:T )|η, H, µ) are both positive, so these conditions trivially hold. Hence, based on Lemma 1, we can convert the inner maximization of ( 22) to an equivalent convex optimization problem. We note that although this transformation has been used in [14], the step-1 from ( 20) to ( 22) is also crucial because otherwise the numerator of ( 20) is not linear and thus Lemma 1 cannot be applied.
Step-3: Note that the inner maximization of ( 22) can be converted to a convex program, we can then focus on the outer minimization. As we discussed earlier, the objective of the outer minimization is convex in η, H and X(0). It remains to check its constraints. These constraints are of the form that some inequalities must hold for all A(1:T ) ∈ U . It turns out that these constraints are also convex in η, H and X(0), and can be converted to linear constraints (See [15] for related techniques). We take one part of the constraint (19) as an example. Note that by (19), the linear inequality (1) must hold for all A(1:T ) ∈ U. For any η, H, the inequality (1) for each t becomes,
Note that A(1:T ) ∈ U can be written as a set of linear constraintsfoot_0 , thus the left-hand-side of ( 23) is of the form max C T A, subject to EA ≤ b where A corresponds to A(1:T ), and η, H enter into the matrix C. By duality [30],
where C T , b T , E T are the transposes of C, b, E, respectively. Thus, ( 23) is equivalent to: there exists λ such that
which is a convex constraint in λ, η(t) and C (i.e., η, H).
(See our technical report [29] for further details.) In summary, through the above three steps, we have obtained a convex problem (22), which can be effectively solved to obtain η and H. (See our technical report [29] for details of the optimization algorithms that we used.) Let CR be the optimal value of (22). Then, the competitive ratio of RAP (18) based on the optimal η and H is no larger than CR.
Remark: Although the solution approach in this section assumes continuous decision variables, it can be generalized to deal with certain integer constraints. Due to page limits, we refer readers to [29] for details.
In Sec. III, we developed a tractable computational framework to calculate an optimized competitive ratio CR among the class of affine policies. Let the corresponding robust affine policy (RAP) be denoted by π * RAP , which will attain a competitive ratio no larger than CR. However, as is often the case with competitive online algorithms in the literature, the policy π * RAP may be too conservative in nature. For example, consider the scenario where the uncertainty set U is given by a predicted input trajectory plus/minus possible errors. In order for π * RAP to attain the competitive ratio CR, it must "defend" against the worst case where the input is far away from the prediction. Specifically, it may have to over-provision resources. As a result, if the input is actually very close to the prediction (which usually corresponds to a larger probability mass on average), π * RAP may incur a higher cost than necessary. In contrast, a popular method in the literature to deal with sequential decisions under uncertainty is RHC (Receding Horizon Control) [12]. At each time t, RHC assumes that the future demand is exactly the same as the most-recent near-term prediction, which is based on revealed demand, day-ahead prediction and possible constraints, e.g., (3), ( 6), (7). Then, RHC minimizes the cost over the entire future horizon and commits to the first decision X(t). Intuitively, if the input is close to the prediction (which we refer to as the average case), RHC may actually perform very well. The problem, of course, is that RHC cannot guarantee as low a competitive ratio as CR. In summary, we see a dilemma between worst-case and average-case performance. In this section, we will address this dilemma by significantly generalizing the "robustification" procedure of our earlier work [14] to obtain good performance for both worst-case and average-case inputs.
In our proposed robustification procedure, we begin with an online algorithm π 0 that is believed to achieve good averagecase performance (e.g., π 0 could be a variant of RHC from [12]). We are also given the competitive ratio CR, which is optimized among the class of affine policies as in Sec. III. We aim to produce a new online policy π that attains comparable average-case performance as π 0 , but at the same time the worst-case competitive ratio CR. Our basic idea for this new policy π is to follow the decisions of π 0 as much as possible, unless doing so will violate the competitive ratio CR. Our first step is thus to develop a way to check whether the decision of π 0 will violate the competitive ratio CR.
Toward this end, let us focus on a time t. Note that the decisions of this algorithm π before time t have already been made. The algorithm π 0 now produces a decision X π0 (t) for time t. In order to verify whether this new decision will still attain CR, we need to check whether the following holds:
where U A(1:t) is given in (8). Let C π (A(1 : t -1)) denote the past cost of the online algorithm π from time 1 to t -1, excluding the switching cost from time t -1 to t. (Again, this cost is known at time t, regardless of whether or not π has followed π 0 before time t.) Based on the decision X π0 (t) of algorithm π 0 , let C π0 (A(t)) = C t (X π0 (t), A(t))+β|X π0 (t)-X π (t -1)|. Further, let C π (A(t + 1 : T )) denote the future cost from time t + 1 to time T (including the switching cost from X π0 (t) to X π (t + 1)). Then, because we want to follow the decision X π0 (t), ( 26) is equivalent to checking
However, the difficulty of checking (27) is that not only the future input has not been revealed yet, we do not even know what decision the algorithm π will take on these future inputs! To circumvent this difficulty, we estimate C π (A(t + 1 : T )) based on affine policies. In this case, the affine policy can be written as X(t ) = η(t ) + H(t )A(t ), t = t + 1, t + 2, ..., T. (28) Note that in general this pair of (η, H) may be different from those calculated in the previous section. Let C RAP (A(t + 1 : T )|η, H) denote the future cost C π (A(t + 1 : T )) if π follows the affine policy (28). We can then formulate the following optimization problem:
Step-1 of Sec. III, (29) may be intractable because the maximization part is a non-convex problem. Nonetheless, we can use the technique in Step-1 of Sec. III [see (21)] to introduce a new set of variables µ that upper-bounds the switching costs in (29). In this way, we can obtain an upper bound of ζ
where CRAP (A(t+1:T )|η, H, µ)= T t =t+1 {C t (X(t ), A(t ))+ µ(t )}, X(t ) is given by (28), and the additional constraint (31) is given below by
Thus, if ζ 1,t ≤ 0, we can be assured that following the decision of algorithm π 0 at time t will retain the same competitive ratio CR.
We still need to determine what to do if ζ 1,t > 0. In that case, we no longer follow the decision of algorithm π 0 at time t. Instead, we find X(t) as well as a different affine policy based on the following optimization problem Intuitively, if we can show that ζ 2,t ≤ 0 at all time t, then Algorithm 1 will attain the same competitive ratio CR. This can be shown by induction: if at the previous time we already verify ζ 1,t-1 ≤ 0, it implies that the corresponding affine policy should make the objective of (32) ≤ 0. Thus, optimizing (32) will only produce an even lower ζ 2,t ≤ 0. We then obtain the following result.
Theorem 1: Algorithm π is CR-competitive, that is, for all A(1 : T ) ∈ U,
The proof is available in our technical report [29].
In this section, we use the NFV orchestration and scaling problem in Sec. II-D as a case study to evaluate the performance of our proposed competitive online algorithm. Since there is little public data on NFV topologies and traces, we use synthetic scenarios. There are 100 clients (L = 100), 10 servers (S = 10), and 10 different VNFs (F = 10). Other parameters are listed in Table I. 2 In Table I, We will compare our proposed online algorithm π with both the offline optimal solution and RHC (Receding Horizon Control). Note that [11] proposes an extended enhanced version of RHC, called AFHC (Averaging Fixed Horizon Control), which is shown to attain a bounded competitive difference. However, AFHC assumes a perfect look-ahead window with size ω, i.e, at each time t, the immediate future inputs in a window of size ω is assumed to be known. In practice such a perfect look-ahead window is often not available. Hence, we do not compare with AFHC with ω > 1. On the other hand, RHC may be viewed as a special case of AFHC with ω = 1. RHC is often found to exhibit good average-case performance [12]. Thus, we can use it as the online algorithm π 0 , which we will robustify as in Sec. IV.
In order to evaluate these solutions, we generate random demand as follows. First, we generate the predicted trajectory A DAP (1:T ). For each time t, A DAP (1:T ) is uniformly distributed in a given set (see [29] for details). Second, we generate the uncertain demand A real (1:T ) around A DAP (1:T ) by adding i.i.d white Gaussian noise with variance σ
, where we call ρ the "variability" of the demand sequence. When ρ is large, the demand sequence fluctuates more significantly in time and is more likely to hit the extreme cases in the uncertainty set U . On the other hand, the uncertainty set U is given independent of ρ, and hence the value of CR is also independent of ρ. Thus, the demand trajectory A real (1:T ) may not always obey the constraints imposed on the uncertainty set U , including (3), (6), (7). Hence, we further adjust it to obtain the "real" demand iteratively in time. Specifically, for each t, if A real (t) (along with A real (t -1)) does not satisfy the constraints of U , we change it to the closest value that satisfies the constraints of U . (See our technical report [29] for details.)
Note that the offline optimal solution is assumed to know A real (1:T ) in advance. In contrast, at each time t, our proposed policies and RHC only know the real demand up to time t, as well as the predicted demand for t + 1, ..., T . As we mentioned in Sec. I, RHC may cause infeasibility due to the hard feasibility constraints. Here, whenever RHC finds no feasible solution at time t, we allow it to violate the ramp constraint (2) by paying another high penalty of 10 3 for each unit of violation of the ramp constraint. Note that our proposed algorithms never pay this penalty because they always respect the ramp constraints.
In Fig. 1, we report the competitive ratio CR of our proposed robust affine policy π * RAP . As we vary the uncertainty level of U , the competitive ratio increases almost linearly. Note that even when = 0.6, i.e., the real demand may vary 60% from the predicted value, the competitive ratio is around 2.5, which is relatively small. The value of CR reported above is the theoretical upper bound of the competitive ratio over all inputs. We also collect the empirical competitive ratio (ECR) under the random demand trajectory that we generated, which is the ratio of the total cost of an online algorithm π to that of the optimal offline solution for each generated trajectory. We plot in Fig. 2 the empirical CDF (Cumulative Distribution Function) of the value of ECR over 20 trials, where ECR RAP , ECR RHC and ECR Robustified-RHC correspond to RAP, RHC and the robustified version of RHC, respectively. We first observe that at all values of variability ρ, the ECR of our proposed robustified-RHC algorithm never exceeds the value of CR (which is 1.2786 when = 0.2). In contrast, the ECR of RHC increases as ρ increases, and it exceeds CR for a significant fraction of trials when ρ = 1 and ρ = 20. Clearly, RHC fails to control the worst-case competitive ratio when the future demand is highly variable. Specifically, due to the ramp constraint, such high variability may lead to infeasibility for RHC, which produces the high online costs. On the other hand, π * RAP incurs much higher ECR than both robustified-RHC and RHC when ρ = 1 30 . This suggests that RAP is too conservative when the prediction turns out to be quite accurate. In summary, what is particularly appealing for our proposed robustified-RHC policy is that it not only attains much smaller ECR than RHC when ρ is large, but also attains almost the same performance as RHC when ρ is small.
In Fig. 3, we plot how CR varies with the magnitude of switching costs. Intuitively, when the parameter β of the switching cost is large, the online decisions become more difficult, and thus the competitive ratio will increase. This is shown in Fig. 3. For example, when β = 10, Fig. 3a shows that the total amount of switching cost (17) is almost 60% of the in-stage cost (15). From Fig. 3b, the corresponding competitive ratio increases to about 3. However, when β further increases, the switching cost dominates (See Fig. 3a), and our competitive ratio further increases. We note that for certain online problems (e.g., [31]), constant competitive ratios may be obtained even when the switching cost is arbitrarily high. This suggests that there may be room to improve our online algorithms, e.g., by integrating ideas from ski-rental problems [2], [31], to obtain even better competitive ratios.
We study competitive online algorithms for OCO problems with linear in-stage costs, switching costs and ramp constraints. First, we present a powerful computational framework to obtain an optimized competitive ratio given an uncertainty set. Second, we provide a robustification procedure to obtain robustified online algorithms with both good average-case performance and an optimized competitive ratio. We demonstrate the power of our proposed approach through a case study for NFV. The robustified version of a popular heuristic algorithm RHC is shown to attain good performance for both averagecase and worst-case inputs. For future work, we plan to study matching lower bounds for the optimal competitive ratio and compare that with ours. For NFV, we are also interested in generalizing our methodology to incorporate precedence constraints [21], [22].
Note that U may involve absolute values, but can still be converted to a linear form (see[29] for details).
Note that with container technology (such as Docker [6]), the granularity of VNF resource allocation is much finer [6] than with VMs. Hence, we use a large value of Ws for the server capacity.