# An LP with Integrality Gap $1+\epsilon$ for Multidimensional Knapsack

David Pritchard111École Polytechnique Fédérale de Lausanne and partially
supported by an NSERC post-doctoral fellowship.

###### Abstract

In this note we study packing or covering integer programs with at most $k$
constraints, which are also known as _$k$ -dimensional knapsack problems_. For
integer $k>0$ and real $\epsilon>0$, we observe there is a polynomial-sized LP
for the $k$-dimensional knapsack problem with integrality gap at most
$1+\epsilon$. The variables may be unbounded or have arbitrary upper bounds.
In the (classical) packing case, we can also remove the dependence of the LP
on the cost-function, yielding a polyhedral approximation of the integer hull.
This generalizes a recent result of Bienstock [3] on the classical knapsack
problem.

##  1 Introduction

The classical _knapsack problem_ is the following: given a collection of items
each with a value and a weight, and given a weight limit, find a subset of
items whose total weight is at most the weight limit, and whose value is
maximized. If $n$ denotes the number of items, this can be formulated as the
integer program $\\{\max\sum_{i=1}^{n}x_{i}v_{i}\mid
x\in\\{0,1\\}^{n},\sum_{i=1}^{n}x_{i}w_{i}\leq\ell\\}$ where $n$ denotes the
number of items, $v_{i}$ denotes the value of item $i$, $w_{i}$ denotes the
weight of item $i$, and $\ell$ denotes the weight limit.

In the more general _$k$ -dimensional knapsack_ (or $k$-constrained knapsack)
problem, there are $k$ different kinds of “weight” and a limit for each kind.
An example for $k=3$ would be a robber who is separately constrained by the
total mass, volume, and noisiness of the items he is choosing to steal. An
orthogonal generalization is that the robber could take multiple copies of
each item $i$, up to some prescribed limit of $d_{i}$ available copies. We
therefore model the $k$-dimensional knapsack problem as

$\\{\max cx\mid x\in\mathbb{Z}^{n},0\leq x\leq d,Ax\leq b\\}$ (1)

where $A$ is a $k$-by-$n$ matrix, $b$ is a vector of length $k$, and $d$ is a
vector of length $n$, all non-negative and integral. Two special cases are
common: if $d=\mathbf{1}$ we call it the _$0\textrm{-}1$ knapsack problem_; if
$d=+\infty$, we call it the _unbounded knapsack problem_.

Another natural generalization is the _$k$ -dimensional knapsack-cover
problem_,

$\\{\min cx\mid x\in\mathbb{Z}^{n},0\leq x\leq d,Ax\geq b\\}$

which has analogous unbounded and 0-1 special cases. We sometimes call this
version the _covering version_ and likewise (1) is the _packing version_.

On the positive side, for any fixed $k$, all above variants admit a simple
pseudo-polynomial-time dynamic programming solution. Chandra et al. [9] gave
the first PTAS (polynomial-time approximation scheme) for $k$-dimensional
knapsack in 1976, and later an LP-based scheme was given by Frieze and Clarke
[13]. See the book by Kellerer et al. [18, §9.4.2] for a more comprehensive
literature review. The case $k=1$ also admits a fully polynomial-time
approximation scheme (FPTAS), but for $k\geq 2$ there is no FPTAS unless
$\mathsf{P}$=$\mathsf{NP}$. This was originally shown for 0-1 $k$-dimensional
knapsack by Gens & Levner [15] and Korte & Schrader [20] (see also [18]) and
subsequently for arbitrary $d$ by Magazine & Chern [24].

Our main result is the following:

######  Theorem 1.

Let $k$ and $\epsilon$ be fixed. Given a $k$-dimensional knapsack (resp.
knapsack-cover) instance $\mathcal{K}$, there is a polynomial-sized extended
LP relaxation $\mathcal{L}$ of $\mathcal{P}$ with
$\mathrm{OPT}(\mathcal{P})\geq(1-\epsilon)\mathrm{OPT}(\mathcal{L})$ (resp.
with $\mathrm{OPT}(\mathcal{P})\leq(1+\epsilon)\mathrm{OPT}(\mathcal{L})$).

Here “polynomial-sized extended LP relaxation” means the following. First,
$\mathcal{P}$ has $n$ variables. Then $\mathcal{L}$ must have those $n$
variables plus a polynomial number of other ones. The projection
$\mathcal{L}^{\prime}$ of $\mathcal{L}$ onto the first $n$ variables must
contain the same integral solutions as $\mathcal{P}$. Finally, $\mathcal{L}$
and $\mathcal{P}$ must have the same objective function, i.e. the objective
function should ignore the extended variables.

In the proof, we will see that the LP can be constructed in polynomial time,
and that a near-optimal integral solution can be obtained from an optimal
extreme point fractional solution just by rounding down (resp. up). The number
of variables in the LP is $n^{O(k/\epsilon)}$ and the number of constraints is
$kn^{O(k/\epsilon)}$. The _integrality gap_ of an IP is the worst-case ratio
between the fractional and integral optimum and therefore Theorem 1 can be
equivalent stated as saying that $\mathcal{P}$ has integrality gap at most
$1+\epsilon$.

Our result and the techniques we use are a generalization of a recent result
of Bienstock [3], which dealt with the packing version for $k=1$. The key
observation we contribute is that his “filtering” approach was also
traditionally used to get a PTAS for multi-dimensional knapsack; in
_filtering_ we exhaustively guess the $\gamma$ max-cost items in the knapsack
for some constant $\gamma$.

The construction of $\mathcal{L}$ in Theorem 1 turns out to depend on the cost
function $c$. A more interesting and challenging problem is to find an
$\mathcal{L}$ which is independent of the cost-function, since this gives a
_polyhedral approximation_ $\mathcal{L}^{\prime}$ of $\mathcal{P}$ e.g. in the
packing case, it implies
$\mathcal{L}^{\prime}\supset\mathcal{P}\supset(1-\epsilon)\mathcal{L}^{\prime}$.
Bienstock’s result [3] actually gives an LP which does not depend on the item
cost/profits $c$. We will show (in Section 4) that in the packing case, our
approach can be similarly revised:

######  Theorem 2.

Let $k$ and $\epsilon$ be fixed. Given a $k$-dimensional knapsack instance
$\mathcal{K}$, there is a polynomial-sized extended LP relaxation
$\mathcal{L}$ of $\mathcal{P}$ with
$\mathrm{OPT}(\mathcal{P})\geq(1-\epsilon)\mathrm{OPT}(\mathcal{L})$, such
that $\mathcal{L}$ does not depend on $c$.

This comes as the cost of an increase in size to $kn^{O(k^{2}/\epsilon)}$. For
the covering case performing the same (a polynomial-sized extended LP
relaxation independent of $c$ with integrality gap $\leq 1+\epsilon$) is an
interesting open problem; we elaborate at the end.

###  1.1 Related Work

Knapsack (whether packing or covering) has an FPTAS by dynamic programming,
and it is well-known that dynamic programs of such a form can be solved as a
shortest-path problem, which has an LP formulation. Nonetheless, there is no
evident way to combine these steps to get an LP for knapsack with integrality
gap $1+\epsilon$. The problem (say, for packing, which is simpler) is that
last step in the FPTAS is not merely to return the last entry of the DP table,
but rather it finds the maximum scaled profit such that the minimum volume to
obtain it fits inside the knapsack (and then recovers the actual solution).
The naive fix is adding this volume constraint to the LP but it makes the LP
non-integral and then it is not clear how to proceed.

Bienstock & McClosky [4] extend the work of Bienstock [3] to covering problems
and other settings, and also give an LP of size
$n^{2}(1/\epsilon)^{\frac{1}{\epsilon}\log\frac{1}{\epsilon}}$ with
integrality gap $1+\epsilon$ for 1-dimensional, 0-1 covering knapsack.222They
use a disjunctive program; in essence, the LP guesses the most costly item in
the knapsack, then for
$i=1,\dotsc,O(\frac{1}{\epsilon}\log\frac{1}{\epsilon})$ it guesses the number
of items whose costs are $(1+\frac{1}{\epsilon})^{-(i,i+1]}$ times that cost,
with all guesses $>\frac{1}{\epsilon}$ deemed equivalent. In particular the LP
depends on the cost function. We remark that the method does not readily
extend to $k$-dimensional knapsack.  There is some current work [5] on
obtaining primal-dual algorithms (that is, not needing the ellipsoid method or
interior-point subroutines) for knapsack-type covering problems with good
approximation ratio and [4] reports that the methods of [5] extend to a
combinatorial LP-based approximation scheme for 1-dimensional covering
knapsack.

Answering an open question of Bienstock [4] about the efficacy of automatic
relaxations for the knapsack problem, Karlin et al. [17] recently found that
the “Laserre hierarchy” of semidefinite programming relaxations, when applied
to the 1-dimensional 0-1 packing knapsack problem, gives an SDP with
integrality gap $1+\epsilon$ after $O(1/\epsilon^{2})$ rounds.

Knapsack problems have a couple of interesting basic properties. The first
contrasts with Lenstra’s result [22] that for any fixed $k$, integer programs
with $k$ constraints can be solved in polynomial time; in comparison, if we
have nonnegativity constraints for every variable plus _one other constraint_
, we get the unbounded (1-dimensional) knapsack problem, which is
$\mathsf{NP}$-hard [23]. Second, recall that for any optimization problem
whose objective is integral, and whose optimal value is polynomial in the
input size, any FPTAS can be used to get a pseudopolynomial-time algorithm. In
contrast, 0-1 2-dimensional knapsack shows the converse is false: it has a
pseudopolynomial-time algorithm, but getting an FPTAS is $\mathsf{NP}$-hard
even when each profit $c_{i}$ is 1, e.g. see [18, Thm. 9.4.1].

There is a line of work on maximizing constrained submodular functions. For
non-monotone submodular maximization subject to $k$ linear packing
constraints, the state of the art is by Lee et al. [21] who give a
$(5+\epsilon)$-approximation algorithm. For monotone submodular maximization
the state of the art is by Chekuri & Vondrák [10] who give a
$(e/(e-1)+\epsilon)$-approximation subject to $k$ knapsack constraints and a
matroid constraint. We note it is $\mathsf{NP}$-hard to obtain any factor
better than $e/(e-1)$ for monotone submodular maximization over a matroid
[12], so in this setting knapsack constraints only affect the best ratio by
$\epsilon$, just like in our setting of LP-relative approximation.

###  1.2 Overview

First, we review rounding and filtering. Rounding is a standard approach to
turn an optimal fractional solution into a nearly-optimal integral one, and
here we lose up to $k$ times the maximum per-item profit. Filtering works well
with rounding because it reduces the maximum per-item profit; the power of
these ideas is already enough to get an LP-based approximation scheme [13],
but it uses a separate LP for each “guess” made in filtering. Therefore, like
Bienstock [4], we use disjunctive programming [2] to combine all the separate
LPs into a single one. The approach has some similarity to the knapsack-cover
inequalities of Carr et al. [6].

##  2 Rounding and Filtering

We now explain the approach. A knapsack instance (1) is determined by the
parameters $(A,b,c,d)$. The naïve LP relaxation of the knapsack problem is

$\\{\max cx\mid x\in\mathbb{R}^{n},0\leq x\leq d,Ax\leq b\\}.$
$\mathcal{K}(A,b,c,d)$

In the following, _fractional_ means non-integral. The following lemma is
standard.

######  Lemma 3.

Let $x^{*}$ be an extreme point solution to the linear program
($\mathcal{K}(A,b,c,d)$). Then $x^{*}$ is fractional in at most $k$
coordinates.

###### Proof.

It follows from elementary LP theory that $x^{*}\in\mathbb{R}^{n}$ satisfies
$n$ (linearly independent) constraints with equality. There are $k$
constraints of the form $A_{j}x\leq b_{j}$; all other constraints are of the
form $x_{i}\geq 0$ or $x_{i}\leq d_{i}$, so at least $n-k$ of them hold with
equality. Clearly $x_{i}\geq 0$ and $x_{i}\leq d_{i}$ cannot both hold with
equality for the same $i$, so $x^{*}_{i}\in\\{0,d_{i}\\}$ for at least $n-k$
distinct $i$, which gives the result. ∎

Therefore, we obtain the following primitive guarantee on a rounding strategy.
Let $\lfloor\cdot\rfloor$ applied to a vector mean component-wise floor and
let $c_{\max}:=\max_{i}c_{i}$.

######  Corollary 4.

Let $x^{*}$ be an extreme point solution to the linear program
($\mathcal{K}(A,b,c,d)$). Then $c\lfloor x^{*}\rfloor\geq cx^{*}-kc_{\max}$.

Now the idea is to take $x^{*}$ to be an optimal fractional solution, and use
filtering (exhaustive guessing) to turn the additive guarantee into a
multiplicative factor of $1+\epsilon$. Let $\gamma$ denote a parameter, which
represents the size of a multi-set we will guess. For a non-negative vector
$z$ let the notation $\lVert z\rVert_{1}$ mean $\sum_{i}z_{i}$. A _guess_ is
an integral vector $g$ with $0\leq g\leq d,Ag\leq b$ and $\lVert
g\rVert_{1}\leq\gamma$. It is easy to see the number of possible guesses is
bounded by $(n+1)^{\gamma}$, and that for any constant $\gamma$ we can iterate
through all guesses in polynomial time.

From now on we assume without loss of generality (by reordering items if
necessary) that $c_{1}\leq c_{2}\leq\dotsb\leq c_{n}$. For a guess $g$ with
$\lVert g\rVert_{1}=\gamma$ we now define the _residual knapsack problem_ for
$g$. The residual problem models how to optimally select the remaining objects
_under the restriction_ that the $\gamma$ most profitable333To simplify the
description, even if $c_{i+1}=c_{i}$ we think of item $i+1$ as more profitable
than item $i$. items chosen (counting multiplicity) are $g$. Let $\mu(g)$
denote $\min\\{i\mid g_{i}>0\\}$. Define $d^{g}$ to be the first $\mu(g)$
coordinates of $d-g$ followed by $n-\mu(g)$ zeroes, and $b^{g}=b-Ag$. The
_residual knapsack problem_ for $g$ is $(A,b^{g},c,d^{g})$. The residual
problem for $g$ does not permit taking items with index more than $\mu(g)$ and
so its $c_{\max}$ value may be thought of as $c_{\mu(g)}$ or less, which is at
most $c\cdot g/\lVert g\rVert_{1}=c\cdot g/\gamma$.

If a guess $g$ has $\lVert g\rVert_{1}<\gamma$, define $b^{g}$ and $d^{g}$ to
be all-zero. Then Corollary 4 gives the following.

######  Corollary 5.

Let $x_{\mathrm{OPT}}$ be an optimal integral knapsack solution for
$(A,b,c,d)$. Let $g$ be the $\gamma$ most profitable items in
$x_{\mathrm{OPT}}$ (or all, if there are less than $\gamma$). Let $x^{*}$ be
an optimal extreme point solution to $\mathcal{K}(A,b^{g},c,d^{g})$. Then
$g+\lfloor x^{*}\rfloor$ is a feasible knapsack solution for $(A,b,c,d)$ with
value at least $1-k/\gamma$ times optimal.

###### Proof.

We use $\mathrm{OPT}$ to denote $c\cdot x_{\mathrm{OPT}}$. Note that
$x_{\mathrm{OPT}}-g$ is feasible for the residual problem for $g$. Therefore
$c\cdot x^{*}\geq\mathrm{OPT}-c\cdot g$. Moreover $c_{\max}$ in the residual
problem for $g$ is not more than $c\cdot
g/\gamma\leq\frac{\mathrm{OPT}}{\gamma}$, so Corollary 4 shows that

$c\cdot\lfloor x^{*}\rfloor\geq c\cdot
x^{*}-k\frac{\mathrm{OPT}}{\gamma}\geq\mathrm{OPT}-c\cdot
g-k\frac{\mathrm{OPT}}{\gamma}$

and consequently $\lfloor x^{*}\rfloor+g$ is a solution with value at least
$\mathrm{OPT}(1-\frac{k}{\gamma})$, as needed. ∎

By taking $\gamma=k/\epsilon$ and solving $\mathcal{K}(A,b^{g},c,d^{g})$ for
all possible $g$ we get the previously known PTAS for $k$-dimensional
knapsack; we now refine the approach to get a single LP.

##  3 Disjunctive Programming

We now review some disjunctive programming tools [2]. The only result we need
is that it is possible to write a compact LP for the convex hull of the union
of several polytopes, provided that we we have compact LPs for each one.

Suppose we have polyhedra $P^{1}=\\{x\in\mathbb{R}^{n}\mid A^{1}x\leq
b^{1}\\}$ and $P^{2}=\\{x\in\mathbb{R}^{n}\mid A^{2}x\leq b^{2}\\}$. Both of
these sets are convex and it is therefore easy to see that the convex hull of
their union is the set

$\textrm{conv.hull}(P^{1}\cup P^{2})=\\{x\in\mathbb{R}^{n}\mid x=\lambda
x^{1}+(1-\lambda)x^{2},0\leq\lambda\leq 1,A^{1}x^{1}\leq b^{1},A^{1}x^{2}\leq
b^{2}\\}.$

However, this is not a _linear_ program, e.g. since we multiply the variable
$\lambda$ by the variables $x^{1}$. Nonetheless, it is not hard to see that
the following is a linear formulation of the same set:

$\textrm{conv.hull}(P^{1}\cup P^{2})=\\{x\in\mathbb{R}^{n}\mid
x=x^{1}+x^{2},0\leq\lambda\leq 1,A^{1}x^{1}\leq\lambda
b^{1},A^{1}x^{2}\leq(1-\lambda)b^{2}\\}.$

A similar construction gives the convex hull of the union of any number of
polyhedra; we now apply this to the knapsack setting.

The LP $\mathcal{K}(A,b^{g},c,d^{g})$ was constructed to mean the left-over
problem after making a guess $g$ of the $\gamma$ most profitable items; we
similarly shift this LP to get $\\{y=x+g\mid x\in\mathbb{R}^{n},0\leq x\leq
d^{g},Ax\leq b^{g}\\}$ which is the same set, after the guessed part is added
back in.

Let $\mathcal{G}$ denote the set of all possible guesses $g$. Then the convex
hull of the union of the shifted polyhedra is given by the feasible region of
the following polyhedron:

$\Bigl{\\{}y\mid
y=\sum_{g\in\mathcal{G}}y^{g};\sum_{g\in\mathcal{G}}\lambda^{g}=1;\lambda\geq\mathbf{0};\forall
g:y^{g}=x^{g}+\lambda^{g}g,\mathbf{0}\leq
x^{g}\leq\lambda^{g}d^{g},Ay^{g}\leq\lambda^{g}b^{g}\Bigr{\\}}.$
($\mathcal{L}$)

We attach objective $\max c\cdot y$ to ($\mathcal{L}$) to make it into an LP,
and use it to prove Theorem 1.

###### Proof of Theorem 1, packing version.

Let $y$ be an optimal extreme point solution for ($\mathcal{L}$). It is
straightforward to argue that any extreme point solution has
$\lambda^{g^{*}}=1$ for some particular $g^{*}$, and $\lambda^{g}=0$ for all
other $g$. Hence $y=x^{g^{*}}+g^{*}$ where $x^{g^{*}}$ is an optimal extreme
point solution to $\mathcal{K}(A,b^{g^{*}},c,d^{g^{*}})$. We now show that
$\lfloor y\rfloor$ is a $(1-\epsilon)$-approximately optimal solution, re-
using the previous arguments.

If $\lVert g^{*}\rVert_{1}<\gamma$, then $x^{g^{*}}=0$ so $y$ is integral,
hence $y$ is an optimal knapsack solution. Otherwise, if $\lVert
g^{*}\rVert_{1}=\gamma$, then Corollary 4 shows that

$c\cdot\lfloor y\rfloor=c\cdot\lfloor x^{g^{*}}\rfloor+c\cdot g^{*}\geq c\cdot
x^{g^{*}}-k\frac{c\cdot g^{*}}{\gamma}+c\cdot g^{*}=c\cdot y-k\frac{c\cdot
g^{*}}{\gamma}\geq(1-\epsilon)c\cdot y,$

which completes the proof. ∎

The corresponding result for the covering version is very similar. One
difference is that we round up instead of down. The other is that some guesses
become inadmissible. Let $g$ be an integral vector with $0\leq g\leq d,\lVert
g\rVert_{1}\leq\gamma$; we define $\mu(g),d^{g}$ as before and call $g$ a
_guess_ only if $A(g+d^{g})\geq b$, in which case we set $b^{g}$ to be the
component-wise maximum of $\mathbf{0}$ and $b-Ag$.

##  4 Removing the Dependence on $c$ for Packing Problems

In the LPs described above, for each guess $g$, we treated that guess as the
set of most _profitable_ items. In particular, $b^{g}$ and $d^{g}$ are defined
in a way that depends on $c$. We now show in the packing case, how to write a
somewhat larger LP, still with integrality gap $1+\epsilon$, which is defined
independently of $c$. This exactly follows the approach of Bienstock [3]; what
we will do is guess the _biggest_ items for each constraint, rather than the
most profitable items. The technique does not seem to have an easy analogue
for covering problems.

In detail, previously, we guessed the multiset $g$ of $\gamma$ most profitable
items in the solution. Instead, let us guess a $k$-tuple
$(g^{1},g^{2},\dotsc,g^{k})$ where for each $k$, $g^{i}$ is the set of
$\gamma$ items in the solution which have largest coefficients with respect to
the $i$th constraint (breaking ties in each constraint in any consistent way).
What we need is that any extreme feasible solution with at most $k$ fractional
values can be rounded to an integral feasible solution at a relative cost
factor of at most $\epsilon$. Let the original extreme point LP solution be
$x$. We round each fractional value up to the closest integer, which causes
the solution to become an infeasible one, call it $y=\lceil x\rceil$. Then, to
retain feasibility, we go through each of the $k$ constraints, pick the
$c$-smallest set of $k$ items from $y$ whose deletion causes the constraint to
again become satisfied; and we delete the union of these sets from $y$,
obtaining $z$. Each set has $c$-cost at most $\frac{k}{\gamma}c(y)$ since for
each constraint $i$, any $k$ elements from $g^{i}$ form an eligible set for
deletion, and $y\subset g^{i}$ consists of at least $\gamma$ items. Thus
$c(z)\geq c(y)-k\frac{k}{\gamma}c(y)=(1-k^{2}/\gamma)c(x)$. Taking
$\gamma=k^{2}/\epsilon$ (compared to the previous $k/\epsilon$), we get the
desired result.

##  5 Discussion

We believe that the main result is a nice theoretical illustration of
techniques (filtering, rounding, disjunctive programming). However, it remains
to be seen if it could be given useful applications. The disjunctive
programming trick is definitely senseless sometimes: if we want to write an
LP-based computer program to $(1+\epsilon)$-approximately solve
multidimensional knapsack instances, it is more efficient to consider the LP
corresponding to each guess separately (as in [13]) rather than solve the
gigantic LP obtained by merging them together. Sometimes an LP-relative [19]
(or Lagrangian-preserving [11, 1]) approximation algorithm can be used as a
subroutine in ways that a non-LP-relative one could not. However, at least in
[11, 19, 1], the analysis relied on LP-relative or Lagrangian-preserving
analysis of the naïve LP, and an arbitrary LP would not have fared as well,
and the LP we build here seems not to be useful in this way.

Finding a compact formulation for $k$-dimensional covering knapsack with small
integrality gap and such that the LP does _not_ depend on the objective
function is an interesting open problem. For example, we are not aware of any
polynomial-sized extended LP for 1-dimensional covering knapsack with constant
integrality gap, in sharp contrast to the packing case. A partial result for
$k$-dimensional covering knapsack is the knapsack-cover LP [6] (see also [25,
8, 7] for applications); it has integrality gap at most $2k$, and while it is
not polynomial size, it can be $(1+\epsilon)$-approximately separated [6] and
hence $(1+\epsilon)$-approximately optimized [14, 16] in polynomial time.

From a theoretical perspective, it also seems challenging to find an LP for
2-dimensional (packing) knapsack where the size of the LP is a function of
$1/\epsilon$ times a polynomial in $n$, as was done in [4] for the
1-dimensional version.

### Acknowledgments

We thank Laura Sanità for helpful discussions on this topic.

## References

  * [1] A. Archer, M. Bateni, M. T. Hajiaghayi, and H. J. Karloff.  Improved approximation algorithms for prize-collecting Steiner tree and TSP.  In Proc. 50th FOCS, pages 427–436, 2009.
  * [2] E. Balas.  Disjunctive programming.  In Discrete Optimization II (Proc. Advanced Research Institute on Discrete Optimization and Systems Applications, Banff, Alta., 1977), volume 5 of Annals of Discrete Mathematics, pages 3–51. North-Holland, 1979\.
  * [3] D. Bienstock.  Approximate formulations for 0-1 knapsack sets.  Oper. Res. Lett., 36(3):317–320, 2008.
  * [4] D. Bienstock and B. McClosky.  Tightening simple mixed-integer sets with guaranteed bounds.  Manuscript, July 2008.
  * [5] T. Carnes and D. B. Shmoys.  Primal-dual schema for capacitated covering problems.  In Proc. 13th IPCO, pages 288–302, 2008.
  * [6] R. D. Carr, L. Fleischer, V. J. Leung, and C. A. Phillips.  Strengthening integrality gaps for capacitated network design and covering problems.  In Proc. 11th SODA, pages 106–115, 2000.
  * [7] D. Chakrabarty, C. Chekuri, S. Khanna, and N. Korula.  Approximability of capacitated network design.  arXiv:1009.5734, to appear at 15th IPCO, 2011.
  * [8] D. Chakrabarty, E. Grant, and J. K nemann.  On column-restricted and priority covering integer programs.  In F. Eisenbrand and F. Shepherd, editors, Integer Programming and Combinatorial Optimization, volume 6080 of Lecture Notes in Computer Science, pages 355–368. Springer Berlin / Heidelberg, 2010.
  * [9] A. Chandra, D. Hirschberg, and C. Wong.  Approximate algorithms for some generalized knapsack problems.  Theoretical Computer Science, 3(3):293–304, 1976.
  * [10] C. Chekuri and J. Vondrák.  Randomized pipage rounding for matroid polytopes.  arXiv:0909.4348, September 2009.
  * [11] F. A. Chudak, T. Roughgarden, and D. P. Williamson.  Approximate $k$-MSTs and $k$-Steiner trees via the primal-dual method and Lagrangean relaxation.  Mathematical Programming, 100:411–421, 2004.  Preliminary version appeared in _Proc. 8th IPCO_ , pages 60–70, 2001\.
  * [12] U. Feige.  A threshold of $\ln n$ for approximating set cover.  J. ACM, 45, 1998.  Preliminary version appeared in _Proc. 28th STOC_ , pages 314–318, 1996.
  * [13] A. M. Frieze and M. R. B. Clarke.  Approximation algorithms for the $m$-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses.  European Journal of Operational Research, 15(1):100–109, January 1984.
  * [14] N. Garg and J. Könemann.  Faster and simpler algorithms for multicommodity flow and other fractional packing problems.  SIAM J. Comput., 37:630–652, May 2007.  Preliminary version appeared in Proc. 39th FOCS, pages 300–309, 1998\.
  * [15] G. V. Gens and E. V. Levner.  Complexity and approximation algorithms for combinatorial problems: A survey.  Technical report, Central Economic and Mathematical Institute, Academy of Sciences of the USSR, Moscow, 1979.
  * [16] M. Grötschel, L. Lovász, and A. Schrijver.  Geometric Algorithms and Combinatorial Optimization.  Springer-Verlag, Berlin, 1988.
  * [17] A. R. Karlin, C. Mathieu, and C. T. Nguyen.  Integrality gaps of linear and semi-definite programming relaxations for knapsack.  arXiv:1007.1283, to appear at 15th IPCO, 2011.
  * [18] H. Kellerer, U. Pferschy, and D. Pisinger.  Knapsack Problems.  Springer, 2004.
  * [19] J. Könemann, O. Parekh, and D. Pritchard.  Multicommodity flow in trees: Packing via covering and iterated relaxation.  Manuscript. Preliminary version appeared as _Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees_ in Proc. 6th WAOA, pages 1–14, 2008.
  * [20] B. Korte and R. Schrader.  On the existence of fast approximation schemes.  In Proc. 4th Symp., Madison, Wisc., volume 4 of Nonlinear Programming, pages 415–437. Academic Press, 1980.
  * [21] J. Lee, V. S. Mirrokni, V. Nagarajan, and M. Sviridenko.  Non-monotone submodular maximization under matroid and knapsack constraints.  In Proc. 41st STOC, pages 323–332, 2009.
  * [22] H. Lenstra.  Integer programming with a fixed number of variables.  Math. Oper. Res., 8:538–548, 1983.
  * [23] G. S. Lueker.  Two NP-complete problems in nonnegative integer programming.  Technical Report 178, Computer Science Laboratory, Princeton University, 1975.
  * [24] M. J. Magazine and M.-S. Chern.  A note on approximation schemes for multidimensional knapsack problems.  Math. of Oper. Research, 9(2):244–247, 1984.
  * [25] D. Pritchard and D. Chakrabarty.  Approximability of sparse integer programs.  Algorithmica, 2010.  In press. Preliminary versions at arXiv:0904.0859 and in Proc. 17th ESA, pages 83–94, 2009.


# Three Shades of Partial Protection in Elastic Optical Networks

Dao Thanh Hai  Post and Telecommunications Institute of Technology, Hanoi
100000, Vietnam<EMAIL_ADDRESS>
###### Abstract

Gone have been the days when the allocation of spectrum resources for a demand
is over-provisioned due to the transmission quality of the worst-case demand
in a network and the optical transmission technologies are based on the fixed
spectral grid, modulation format and/or line-rate schemes. Elastic optical
networks technologies featuring adaptive spectrum allocation mechanisms have
been becoming the architecture and technology of choice for future core
networks to meet explosive traffic growths in a cost and energy-efficient
manner. Partial protection strategies based on the observation that in failure
events, a service can tolerate a certain amount of degradation and therefore
by reducing the protection traffic in the network, better spectrum utilization
could be attained. Such concept has been widely studied in the traditional WDM
context and yet has been somehow faded due to the fact that fixed transmission
technologies allow small room for spectral improvement. This paper aims to
renew the interest in partial protection and re-adapt it to the context of
elastic optical networks. The evolutionary perspective we lay out in this
paper identifies a new route for achieving greater spectral efficiency in a
pragmatic way by simply differentiating the protection services for each
demand rather than the uniform treatment for all demands. In doing so, we
present a new research problem entitled, routing, modulation level, spectrum
and protection service assignment which is an extension of the well-
established one, that is, routing, modulation level, and spectrum assignment
as the (partial) protection service for each demand is taken into account and
optimized. Three variants of that problem reflecting shades of applying
partial protection are covered in details. Specifically, the first one
considers the intuitive case as the relative amount of protection traffic for
each demand is given as the input to the network planning process while the
second one is dedicated to the special case of enforcing the same figure of
partial protection for all demands. More interesting is brought in the third
variant where given the service level agreement for the total network traffic,
we provide the optimal solution that determine the protection service for each
individual demand so as to minimize the spectral occupancy. Extensive
numerical simulations have been applied to the realistic COST239 network
topology and it has been revealed that a remarkable spectral saving could be
achieved thanks to introducing partial protection services.

###### keywords:

Elastic optical network , dedicated protection , fiber-optic communications ,
elastic transponders , partial protection , routing and spectrum assignment ,
network optimization , integer linear programming

††journal: X

##  1 Introduction

The era of Artificial Intelligence and Big Data Analytics have been coming
into play, marking a new revolution, widely referred as the Fourth Industrial
Revolution (IR 4.0) [1]. On one hand, the physical world have been
progressively evolving towards digitization thanks to the convergence of
several technological advances including notably sensor technologies and
ubiquitous access to the Internet. Such digital transformation therefore
heralds for an always-connected world in which the digital shadow of the
physical world has been practically created. On the other hand, the
introduction of novel and bandwidth-hungry services such as tele-presence
holography and tactile control of robotics have been accelerating in an
unprecedented manner. Such two driving forces have been push-pulling the scale
of challenges posed by global consumption of data and the explosive growth of
Internet traffic [2]. According to the recently released report from Cisco
[3], annual global IP traffic will reach 4.8 ZB per year by 2022, exhibiting a
three-fold increase over a span of 5-year and such multiplicative growth has
shown no signs of stopping. In this context, optical core networks forming the
backbone of Internet infrastructure have been under the critical pressure for
a radical re-consideration across different phases ranging from designing, and
planning to operation and management to achieve greater capital and
operational efficiency. Indeed, the ultimate goal is to transfer more
information at a lower cost on less spectrum resources and doing so helps to
produce low-latency and high-throughput backbone networks, enabling the so-
called global connectivity at scale.

In facing with the unprecedented traffic growth, optical transport networks
have been advancing accordingly. On one hand, from the architectural
perspective, core optical networks have been evolving from the opaque mode to
translucent and eventually fully transparent operation. Thanks to the enormous
advancements in optical components, transmission technologies and photonic
switching, the vision of all-optical/transparent core networks have been
experimentally and practically realized, bringing in significant savings of
cost, footprint, and power by eliminating unnecessary O-E-O regenerations [4,
5, 6]. On the other hand, driven by the fact that the spectrum is limited and
therefore, the capacity limit of conventional fiber might soon be reached
(i.e., fiber capacity crunch), elastic optical networks technologies have been
proposed and developed with the objective of using fiber capacity more
efficiently. In particular, thanks to significant progress in optical
transmission technologies, rate-adaptive optics has been emerging as promising
solution to meet ever growing bandwidth demands and simultaneously reduce
network cost. In EONs, the spectrum is divided into slices, breaking the
traditional rigid frequency grid in WDM networks and hence, paving the way for
adaptive spectrum provisioning tailoring to specific demand including its
bandwidth requirement and transmission quality [7, 8, 9]. On another front, as
optical transport networks have been the key enabler for information society,
the issue of resilience has become of greater importance [10]. In practice,
securing the core networks against single link failures have been an integral
part of network planning process and among survivability schemes, dedicated
path protection has been widely deployed thanks to its rapid recovery speed
and ease of operations [11, 12].

Planning EONs with survivability requirements has been the focus of extensive
research works, covering a wide range of protection schemes [13, 14, 15]. It
is evident that as far as protection services are provided, a certain amount
of redundant capacity must be required and to optimize such redundancy,
network coding has been used recently for protection purposes [16, 17, 18].
The majorities of these work have nevertheless relied on the conventional
concept of full protection service for all demands. However, in practice, such
over-provisioning appears to miss the heterogeneous nature of services.
Indeed, it is well-known that roughly $25\%$ traffic traveling in optical
fiber belongs to premium class while $75\%$ remaining are best-effort type and
hence can be temporarily discarded on occasion of failures [19, 20, 21].
Moreover, it appears that link failures are typically fixed quickly and the
customers may be willing to tolerate a decreased rate if it is accompanied by
reduced cost. This means that instead of providing full protection, just some
part of the traffic could be delivered to receivers upon failure events and by
reducing the amount of protection requirement, less spare resources might be
needed and this brings to the reduction of power consumption and cost as well
[19]. This background sets the stage for the arrival of a concept, entitled,
partial protection (PP) in which the differentiation of protection level for
demands are taken into account to further improve network performances.
Partial protection had been raised in the context of traditional WDM networks
with pioneering works from [22, 23]. In [22], the authors examined the
throughput gain when applying partial protection in optical WDM Networks. In
[23], partial protection was examined to guarantees a minimum grade of service
upon a link failure by utilizing backup capacity sharing between demands and
such application resulted in a remarkable reductions (e.g., $83\%$) in
protection resources. The scenario of traffic grooming with sub-wavelength
capacity connection was studied by leveraging partial protection and it was
shown in [24] that applying PP brought out lower blocking probability and
lower network costs. Multi-path routing was suitable with PP strategies and
the works in [25] proposed an effective multi-path algorithm attempting to
provision bandwidth requests and simultaneously guaranteeing the maximum
partial-protection possible. A related scheme, called partial path protection
were covered in [26, 27] where a collection of backup path were used to
protect an active path. Partial protection was furthermore studied in the
context of disaster-survivable networks with a pioneering work from [28]. The
use of partial protection for mixed line rates networks were investigated in
[29] and the authors took advantage of multipath routing and volume discount
of higher-line-rate transponders for maximizing the network performances.
However, due to the fixed nature of WDM networks, there has been little room
for further improvement with partial protection and consequently the concept
of partial protection had been somehow faded. The development of elastic
optical networks (EONs) with adaptive resource allocation according to
specific traffic requirement and/or transmission qualities opens up therefore
new opportunities for a re-consideration of partial protection. In fact, a
closely related strategy is called, quality-of-service provisioning, in EONs
have been studied in [30, 31, 32]. In [33], an effective machine learning-
based algorithm for identifying the most probable cause of failure impacting a
given service and a re-optimization algorithm to re-route affected demands
with the objective of minimizing Service Level Agreement (SLA) were proposed.
Multi-path allocation has been proposed as a simple way to achieve traffic
protection in different networking domains and in EONs, it was shown in [34]
that dual-path allocation assuming dynamic offered traffic outperformed
traditional techniques. The works in [21] exploited the observation that
traffic traveling in fiber could be classified into the premium and best-
effort type and currently premium traffic made up approximately $25\%$ total
traffic, better spectrum allocation could be offered. In leveraging this idea,
in our recent works [35, 36], the framework for adaptive provisioning
satisfying the quality-of-service of individual demands have been addressed.
Our works developed an optimal network design formulation taking into account
the protection level of each demand as an input to the design process and it
was shown that by varying the quality-of-service provisioning, greater
spectrum efficiency could be achieved. Existing works in the literature
nevertheless have largely focused on the direction that the level of
protection traffic is specified in advance for each demand and hence provided
non-optimal solution for the network design with partial protection. Different
from this perspective, we are interested in a more realistic scenario as the
protection level for each demand should be considered as variables of network
design process and the task is to determine the optimum protection level for
each demand so as to the overall service level agreement is met while
minimizing the spectrum occupancy. To the best of our knowledge, this is the
first time such issue has been raised and investigated.

This paper marks a departure from conventional full protection provisioning in
elastic optical networks with a concept of partial protection scheme in order
to achieve greater spectrum efficiency. Leveraging partial protection offers a
new perspective to re-design EONs taking into account the diversity of
protection services that a traffic demand can request instead of treating all
demands with same service. To this end, we present a new research problem
entitled, routing, modulation level, spectrum and protection service
assignment which is an extension of the well-established one, that is,
routing, modulation level, and spectrum assignment as the (partial) protection
service for each demand is taken into account and optimized. Our proposal of
partial protection strategies in EONs is illustrated and discussed
comprehensively in Section 2. In order to optimally determine the protection
service for each demand, we develop the network planning framework based on
mixed integer linear programming formulation in Section 3. The important point
of this formulation is the consideration of protection level for each demand
as a design variable to be optimized so as to meet the overall SLA requirement
and to minimize the spectrum resources. To assess the efficacy of our partial
protection proposal, extensive numerical simulations have been applied on the
realistic topology COST239 covering diverse scenarios and the result is
reported in Section 4. Finally, the conclusion of the paper and perspectives
for extension is addressed in Section 5.

##  2 The Three Shades of Partial Protection versus Full Protection

In this part, the concept of partial protection is introduced in the context
of EONs. We also highlight various shades when it comes to adapting partial
protection to EONs context and compare them to the conventional full
protection. In backing up our proposal for partial protection in EONs, we
propose a simple cost-efficient optical node architecture for practical
realization of such partial protection mechanism.

Let us consider a conventional network planning case with full dedicated
protection as illustrated clearly in Fig. 1. In this illustrative example,
supposing that there are only two traffic demands in the network, that is, the
first demand is from node $A$ to node $Z$ with 100 Gbps while the second
demand is from node $B$ to node $Z$ with 175 Gbps requirement. Provisioning
such two demands in the context of elastic optical networks means that we must
select the routing, modulation format and spectrum allocation tailored to the
transmission condition of each demand. Assuming that for the first demand,
both its working path and protection path have almost the same transmission
quality and therefore, make use of the same modulation format (PM) 16-QAM. For
a spectrum slot of $6.25$ GHz, it hence requires two spectrum slots for both
working and protection signal to support $100$ Gbps traffic (i.e., each
spectrum slot with PM-16-QAM modulation is capable of carrying 50 Gbps). With
respect to the second demand, supposing that due to the considerable
transmission length difference between its working and protection path, its
working signal and protection signal operate at different modulation formats.
Specifically, its working route is shorter and hence, its working signal can
be modulated on higher-order modulation format (e.g., 64-QAM) than its
protection signal (e.g., 8-QAM). In order to support $175$ Gbps of the second
demand, three spectrum slots are needed for the working path while the
protection path have to utilize five spectrum slots. A comprehensive routing,
modulation format selection and spectrum assignment for the full protection is
shown in Fig. 1. The spectral cost for such full protection provisioning is
$7$ spectrum slots for the entire network and $31$ units of spectrum link
usage.

Figure 1: The traditional approach: full protection

In an attempt to reduce the spectrum occupancy, we consider a different
approach for offering protection service, that is, partial protection. Instead
of providing full protection for all demands, let us here assume that
different demands require different amount of protection traffic and that
specific amount is negotiated a priori and thus becomes the inputs to the
network planning process. Figure 2 illustrates the first case of partial
protection where each demand is specified in advance the amount of protected
traffic. Specifically, in this case, the first demand requires $50\%$ traffic
upon protection mode while demand 2 needs $75\%$ amount of traffic for
protection. It has been shown in Fig. 2 that doing so clearly brings about
spectral savings. As far as the spectral cost is evaluated, only $5$ spectrum
slots, in contrast to $7$ slots for full protection, are required for the
whole network and the spectrum link usage have been reduced accordingly from
$31$ units in full protection to $25$ units thanks to the reduction of
protection traffic for both two demands.

Figure 2: Partial Protection: Conventional approach

Let us turn the attention to a different variant of partial protection
strategy where instead of specifying the protection level for each demand a
priori, network operators receive the service level agreement (SLA) for the
entire traffic. For example, one such SLA could be that (at least ) $75\%$ of
the total traffic must be protected in case of failures. In satisfying such
requirement, network operators could rely basically on two approaches. The
first one is naive when all demands are treated with the same figure of
protection level required by SLA. For example, given the SLA of $75\%$, all
demands are offered uniformly $75\%$ amount of protection traffic. Figure 3
reveals comprehensively the application of such naive approach and it can be
seen that $one$ spectrum slot is saved for the entire network compared to the
full protection case. It is important to note that while shrinking from 175
Gbps to 131.25 Gbps results in $one$ spectrum slice saving for the second
demand, a reduction from 100 Gbps to 75 Gbps is not significant enough to
produce spectral saving for the first demand. Indeed, for demand 1, providing
full protection and $75\%$ protection does not make any difference from
spectral occupancy perspectives. It is observed that although the one-size-
fits-all approach is intuitive, its spectral benefit is limited and hence it
leads to a question of whether it exists a more spectrally efficient way to
meet SLA requirement.

Figure 3: Partial Protection: One-size-fits-all approach

Considering the case that SLA of $75\%$, let us propose an alternative
approach shown in Fig. 4. Instead of treating uniformly all demands with the
same amount of protection level, we now vary the protection level specifically
for each demand so as to the overall SLA is met. One such provisioning is
illustrated in Fig. 4 as protection traffic of demand 1 is reduced by half
from 100 Gbps to 50 Gbps and protection traffic of demand 2 is shrinked from
175 Gbps to 106.25 Gbps to meet SLA of $75\%$ for the entire network traffic.
Overall, an amount of $75\%$ of entire traffic is secured as protection
traffic. For this demand-wise approach, it is easy to verify from Fig. 4 that,
$3$ spectrum slots saving could be achieved compared to the full protection
scenario in Fig. 1. Moreover, it is highlighted that the demand-wise approach
could generate greater spectral efficiency than the one-size-fits-all one.

Figure 4: Partial Protection: Demand-wise approach

In supporting our proposed partial protection scheme, the optical node
architecture has to be taken into account. Here we propose a cost-effective
architecture leveraging the usage of a shared elastic transponder for both
working and protection mode. The elastic transponder is capable of providing
multiple modulation formats and/or baud-rate in order to support a wide range
of traffic demands. The transponder is directed to the working path in the
normal condition and upon the detection of failure event, the optical-layer
switch is reconfigured to re-direct the transponder to the protection path. It
is important to note that during this transition, the transponder might be
reconfigured itself to operate at a different baud-rate and/or different
modulation format to support partial protection operation. Such transition
from working mode to protection mode with this node architecture has been
experimentally demonstrated and it has been revealed that the overall
reconfiguration could be rapidly taken place, being kept within a few tens of
milliseconds satisfying the requirements of many operators [37, 38, 39].

Figure 5: The optical node architecture supporting partial protection schemes

The illustration provided in this part demonstrates a new venue for improving
spectrum efficiency of optical networks by relying on the idea of reducing
protection traffic with partial protection strategies. In general, network
operators are interested in the question that given the SLA requirement for
the entire network traffic, what would be the optimal assignment of protection
level for each demand so that the spectral occupancy is minimized while
satisfying SLA. We aim to tackle this issue in this paper and the next part
provides a framework for optimal network planning with partial protection

##  3 Mathematical Formulation for Routing, Modulation Level, Spectrum and
Protection Service Assignment Problem

In order to realize the spectral benefits of introducing partial protection in
elastic optical networks, we present a mathematical formulation for optimal
network dimensioning. The formulation takes the fiber network topology, set of
traffic demands and service level agreement for protection traffic as the key
inputs and returns the optimum routing, modulation level, spectrum assignment
for each demand together with the partial protection coefficient so as to
minimize the spectrum occupancy while satisfying SLA requirement. In our
formulation, the spectrum assignment with continuity and contiguity
constraints are processed with the concept of pre-calculated channels [40] as
it was proven highly computational efficient.

Raw Input Data:

  * 1.

$G(V,E)$: The given physical topology with $|V|$ nodes and $|E|$ fiber links

  * 2.

$S$: Set of available spectrum slices in each fiber link, indexed by $s$

  * 3.

$D$: Set of all traffic demands and each demand $d\in D$ requires $t^{d}$ Gbps

  * 4.

$M$: Set of supportable modulation formats, indexed by $m$

  * 5.

A function relates optical reach to modulation format and bit-rate operation
$L=145.741+(n-14.0344)\times(60.2196\times ln(BR)-465.82)$: L $[km]$, n
$[bit/s/Hz]$ and bit rate (BR) $[Gbps]$ [41]

  * 6.

$K$: Set of allowable protection services, indexed by $k$. For example, $k=1$
may refer to the amount of protection of $25\%$ while $k=2$ represents to an
agreement of $50\%$ protection traffic

  * 7.

$SLA$: Service Level Agreement specifies the overall minimum protection
traffic for entire network

Additional Input Data obtained from Pre-processing Process:

  * 1.

$P^{d}$: Set of $k$ pairs of link-disjoint routes for a demand $d$, each route
pair $p^{d}$ of a demand $d$ consists of a working route and a protection
route for that demand

  * 2.

$P=\cup_{{d\in D}}{P^{d}}$: Set of all pairs of link-disjoint routes for all
demands in the network

  * 3.

$\beta_{p,k}^{d}$: a coefficient equals to 1 if a pair of routes $p\in P$ is
feasible for demand $d\in D$ at protection index $k$, 0 otherwise. The pair of
routes $p\in P^{d}$ for demand $d$ is considered to be feasible at protection
service $k$ if there is at least one feasible modulation format carrying
$t^{d}$ $Gbps$ traffic on the working path and there is at least one feasible
modulation format carrying a partial amount of $t_{d}$ $Gbps$ corresponding to
the protection service $k$ on protection route.

  * 4.

$h_{p,w}^{d}$: the most spectrum-efficient (highest-order) modulation format
for working path belonging to a route pair $p\in P^{d}$ of demand $d\in D$

  * 5.

$h_{p,b}^{d,k}$: the most spectrum-efficient (highest-order) modulation format
for backup path belonging to a route pair $p\in P^{d}$ of demand $d\in D$ with
respect to protection service $k$

  * 6.

$C_{p,w}^{d}$: Set of admissible spectrum channels for working path of a route
pair $p\in P^{d}$

  * 7.

$C_{p,b}^{d,k}$: Set of admissible spectrum channels for backup path of of a
route pair $p\in P^{d}$ with respect to protection service $k$

  * 8.

$C=\cup_{{p\in P^{d},d\in D}}{(C_{p,w}^{d}\cup C_{p,b}^{d,k})}$: Set of all
possible spectrum channels

  * 9.

$\alpha_{c,s}$: a coefficient equals to 1 if the slice $s\in S$ belongs to
channel $c\in C$, 0 otherwise

  * 10.

$\gamma_{p,e}$: a coefficient equals to 1 if link $e\in E$ belongs to the
working path of a route pair $p\in P$, 0 otherwise

  * 11.

$\delta_{p,e}$: a coefficient equals to 1 if link $e\in E$ belongs to the
backup path of a route pair $p\in P$, 0 otherwise

Variables:

  * 1.

$x_{p,c}^{d}\in\\{0,1\\}$: equals to 1 if demand $d$ is provisioned by finding
a pair of routes $p\in P^{d}$ and a spectrum channel $c\in C_{p,w}^{d}$ for
working path

  * 2.

$y_{p,c}^{d,k}\in\\{0,1\\}$: equals to 1 if demand $d$ is provisioned by
finding a pair of routes $p\in P^{d}$ and a spectrum channel $c\in
C_{p,b}^{d,k}$ for protection path with respect to protection service $k$

  * 3.

$z_{k}^{d}\in\\{0,1\\}$: equals to 1 if demand $d$ if demand $d$ is provided
the protection service $k$, 0 otherwise

  * 4.

$r_{e,s}\in\\{0,1\\}$: equals to 1 if the spectrum slice $s\in S$ is occupied
in link $e\in E$

  * 5.

$\theta_{s}\in\\{0,1\\}$: equals to 1 if the spectrum slice $s\in S$ is
utilized in the network, 0 otherwise

Objective:

$\textit{Minimize}\;\phi=\sum_{s\in S}{\theta_{s}}$ (1)

Subject to the following constraints:

$\sum_{k\in K}z^{d}_{k}=1\qquad\forall d\in D$ (2)

$\sum_{p\in{P^{d}}:\beta_{p}^{d,k}=1}\sum_{c\in
C_{p,b}^{d,k}}y_{p,c}^{d,k}=z^{d}_{k}\qquad\forall k\in K$ (3)

$\sum_{c\in C_{p,w}^{d}}x_{p,c}^{d}=\sum_{k\in K}\sum_{c\in
C_{p,b}^{d,k}}y_{p,c}^{d,k}\qquad\forall d\in D,p\in P^{d}:\beta_{p}^{d,k}=1$
(4)

$\sum_{d\in D}\sum_{k\in K}z^{d}_{k}\times t^{d}\geq SLA\times\sum_{d\in
D}t^{d}\qquad\forall d\in D$ (5)

$\sum_{d\in D}\sum_{k\in K}\sum_{p\in{P^{d}}}\beta_{p}^{d,k}(\sum_{c\in
C_{p,w}^{d}}x_{p,c}^{d}\times\gamma_{p,e}\times\alpha_{c,s}+\sum_{c\in
C_{p,b}^{d,k}}y_{p,c}^{d,k}\times\delta_{p,e}\times\alpha_{c,s})=r_{e,s}\qquad\forall
e\in E,s\in S$ (6)

$\sum_{e\in E}{r_{e,s}}\leq|E|\theta_{s}\qquad\forall s\in S$ (7)

The objective in Eq. 1 aims at minimizing the spectrum usage measured in terms
of number of spectrum slices to support all traffic demands so as to meet the
protection service level agreement for the entire traffic. Constraints in Eq.
2 guarantees that each demand must select one and only one protection service.
The constraints in Eq. 3 say that for the selected protection service of a
demand $d$, a protection route and a protection channel must be found to
support that demand. The coherence between the working route and protection of
a demand is expressed by the constraints in Eq. 4. The constraints in Eq. 5
are to satisfy the service level agreement for protection. The traditional
constraints involving the unique usage for a spectrum slice is ensured by Eq.
6. Finally, the definition of using a spectrum slice in the network, that is,
a spectrum slice is considered to be used if it is occupied in any link of the
network, is provided by Eq. 7.

##  4 Numerical Results

This section is dedicated to evaluate our proposal of partial protection on
the realistic network topology COST239 as shown in Fig. 6. This network is
composed of 11 nodes and 52 fiber links whose length are ranged from $\approx$
200 km to $\approx$ 1000 km. Such diversity in link length is a good match for
the differentiation of transmission properties between the working and
protection path where working signal and protection signal could be modulated
at different modulation format rather than having the same one based on the
worse case. For traffic generation, we assume that $50\%$ of node-pairs having
the traffic and the traffic between each node pair is randomly generated
between 100 Gbps and 200 Gbps with a step of 25 Gbps. Ten traffic instances
are generated and six modulation formats are considered as shown in Table 1.
The number of pairs of route per demand $k$ is 4 and we make use of a variant
of Suurballe algorithm to find such 4 shortest pairs for a demand. The mixed
integer linear programming formulation in Section 3 is applied and CPLEX
solver with an academic version [42] is used to obtain optimal results.

Descriptive Features
---
Nodes | 11
Links | 52
Average nodal degree | 4.7
Shortest link distance | $\approx 200km$
Longest link distance | $\approx 1000km$

Figure 6: COST239 network with link distance in $km$ Table 1: Bit-rate Operation per $6.25$ $GHz$ Spectrum Slot for different Modulation Formats Modulation Formats | Bit-rate per Spectrum Slot
---|---
PM-BPSK | 12.5 Gbps
PM-QPSK | 25 Gbps
PM-8QAM | 37.5 Gbps
PM-16QAM | 50 Gbps
PM-32QAM | 62.5 Gbps
PM-64QAM | 75 Gbps

For benchmarking, in the first scenario, we compare the traditional full
protection design with the partial protection design where the relative amount
of protection traffic for each demand is randomly selected among $25\%$,
$50\%$ and $75\%$ and provided as input to the design process. Figure 7 shows
the comparison of such two designs in terms of used spectrum slices. As
expected, by reducing the amount of protection traffic, less spectrum slots
are required to accommodate the traffic. In this simulation scenario, the
result reveals that instead of over-provisioning with full protection traffic
for all demands, remarkable spectral saving could be achieved, up to $32\%$
for partial protection approach

Figure 7: Full protection versus Partial Protection in terms of used spectrum
slices

Let us move to the second scenario of applying partial protection. For this
case, all demands are enforced to have the same protection services specified
by the SLA for the entire network. Three kind of SLA protection services are
considered, that is, $25\%$, $50\%$ and $75\%$. Figure 8 reports the impact of
spectral occupancy as the amount of protection traffic is varied from $75\%$
to $25\%$ in comparison with the full protection. It is clearly shown that
shrinking the protection trafffic generates spectral savings and specifically
such saving could be up to $26\%$ for $75\%$ partial protection, $46\%$ for
$50\%$ partial protection and $55\%$ for $25\%$ partial protection. It can
also be observed that the spectral saving does not move proportinally to the
reduction of protection traffic. In our studied case, shrinking protection
traffic up to $50\%$ tends to achieve the best revenue while going beyond
$50\%$ brings about relatively small impact.

Figure 8: Full protection versus Partial Protection $25\%$, $50\%$ and $75\%$

We turn the attention to third scenario where the relative amount of
protection traffic for each demand becomes a design variable and it has to be
optimized to meet the SLA of entire network. We reconsider the second scenario
but now instead of enforcing the same amount of protection traffic for all
demands, each demand can select the protection services among three types
$25\%$, $50\%$ and $75\%$ according to the optimization model in Section 3.
Figure 9 compares the one-size-fits-all approach and the demand-wise one when
the SLA is $50\%$. It can be clearly seen that by optimizing the selection of
protection service for each demand, better spectrum usage can be realized. In
our simulation of ten traffic instances, 8 out 10 cases results in greater
spectrum efficiency with the demand-wise approach compared to the one-size-
fits-all one and in the most favorable case, the demand-wise approach could be
$25\%$ more efficient than its counterpart.

Figure 9: One-size-fits-all partial protection versus Demand-wise partial
protection

.

##  5 Conclusions

In an attempt to achieve greater capacity efficiency for optical core
networks, this paper proposed the concept of partial protection to be applied
in elastic optical networks, that is, instead of providing full protection for
all traffic demands, the assignment of (partial) protection traffic for each
demand is taken into account and optimized. We examined various scenarios that
applying partial protection could potentially generate spectral savings and
introduced the network design framework incorporating partial protection. A
new problem, entitled, routing, modulation level, spectrum and protection
service assignment was developed for optimal network designs based on mixed
integer linear programming formulation. In verifying the efficacy of our
proposal, extensive simulation on the realistic network topology COST239 was
carried out and our findings indicated that significant savings of spectrum
resources could be achieved by reducing the protection traffic. Moreover, our
results demonstrated that the demand-wise approach far outperformed the one-
size-fits-all and the difference could be up to $25\%$ in our studied cases.

## Conflict of interest

The authors declare that they have no conflict of interest.

## References

  * [1] R. Sabella, P. Iovanna, G. Bottari, F. Cavaliere, Optical transport for industry 4.0, J. Opt. Commun. Netw. 12 (8) (2020) 264–276.  doi:10.1364/JOCN.390701.
URL http://jocn.osa.org/abstract.cfm?URI=jocn-12-8-264

  * [2] A. D. Ellis, N. M. Suibhne, D. Saad, D. N. Payne, Communication networks beyond the capacity crunch, Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 374 (2062).  doi:10.1098/rsta.2015.0191.
URL http://rsta.royalsocietypublishing.org/content/374/2062/20150191

  * [3] Cisco, Cisco annual internet report (2020).
  * [4] A. Saleh, J. M. Simmons, All-optical networking: Evolution, benefits, challenges, and future vision, Proceedings of the IEEE 100 (5) (2012) 1105–1117.  doi:10.1109/JPROC.2011.2182589.
  * [5] A. Saleh, J. M. Simmons, Technology and architecture to enable the explosive growth of the internet, Communications Magazine, IEEE 49 (1) (2011) 126–132.  doi:10.1109/MCOM.2011.5681026.
  * [6] P. J. Winzer, D. T. Neilson, A. R. Chraplyvy, Fiber-optic transmission and networking: the previous 20 and the next 20 years, Opt. Express 26 (18) (2018) 24190–24239.  doi:10.1364/OE.26.024190.
URL http://www.opticsexpress.org/abstract.cfm?URI=oe-26-18-24190

  * [7] A. Lord, Y. R. Zhou, R. Jensen, A. Morea, M. Ruiz, Evolution from Wavelength-Switched to Flex-Grid Optical Networks, Springer International Publishing, Cham, 2016, pp. 7–30.
  * [8] P. Layec, A. Morea, F. Vacondio, O. Rival, J. Antona, Elastic optical networks: The global evolution to software configurable optical networks, Bell Labs Technical Journal 18 (3) (2013) 133–151.  doi:10.1002/bltj.21631.
  * [9] A. Dupas, P. Layec, E. Dutisseuil, S. Belotti, S. Bigo, E. H. Salas, G. Zervas, D. Simeonidou, Elastic optical interface with variable baudrate: Architecture and proof-of-concept, IEEE/OSA Journal of Optical Communications and Networking 9 (2) (2017) A170–A175.  doi:10.1364/JOCN.9.00A170.
  * [10] Amazon multi-million dollar server outage caused by it worker typo, https://www.rt.com/news/379398-amazon-server-outage-typo/, accessed: 2017-04-30.
  * [11] H. Dao Thanh, M. Morvan, P. Gravey, On the usage of flexible transponder in survivable transparent flex-grid optical network, in: 2014 9th International Symposium on Communication Systems, Networks Digital Sign (CSNDSP), 2014, pp. 1123–1127.  doi:10.1109/CSNDSP.2014.6923998.
  * [12] Z. Xu, E. Archambault, C. Tremblay, J. Chen, L. Wosinska, M. P. Belanger, P. Littlewood, 1+1 dedicated optical-layer protection strategy for filterless optical networks, IEEE Communications Letters 18 (1) (2014) 98–101.  doi:10.1109/LCOMM.2013.111113.132000.
  * [13] P. Gravey, D. Hai, M. Morvan, On the advantages of co-ofdm transponder in network-side protection, in: Advanced Photonics for Communications, Optical Society of America, 2014, p. PW1B.3.  doi:10.1364/PS.2014.PW1B.3.
URL http://www.osapublishing.org/abstract.cfm?URI=PS-2014-PW1B.3

  * [14] H. Dao, M. Morvan, P. Gravey, An efficient network-side path protection scheme in ofdm-based elastic optical networks, International Journal of Communication Systems 31 (1) e3410, e3410 dac.3410.  arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/dac.3410, doi:10.1002/dac.3410.
URL https://onlinelibrary.wiley.com/doi/abs/10.1002/dac.3410

  * [15] Routing and spectrum allocation algorithms for elastic optical networks with dedicated path protection, Optical Switching and Networking 13 (2014) 63 – 75\.
  * [16] G. Savva, K. Manousakis, G. Ellinas, Confidentiality meets protection in elastic optical networks, Optical Switching and Networking (2021) 100620doi:https://doi.org/10.1016/j.osn.2021.100620.
URL https://www.sciencedirect.com/science/article/pii/S1573427721000175

  * [17] D. T. Hai, Leveraging the survivable all-optical wdm network design with network coding assignment, IEEE Communications Letters 21 (10) (2017) 2190–2193.  doi:10.1109/LCOMM.2017.2720661.
  * [18] D. T. Hai, L. H. Chau, N. T. Hung, A priority-based multiobjective design for routing, spectrum, and network coding assignment problem in network-coding-enabled elastic optical networks, IEEE Systems Journal 14 (2) (2020) 2358–2369.  doi:10.1109/JSYST.2019.2938590.
  * [19] A. Agrawal, U. Vyas, V. Bhatia, S. Prakash, Sla-aware differentiated qos in elastic optical networks, Optical Fiber Technology 36 (2017) 41–50.  doi:https://doi.org/10.1016/j.yofte.2017.01.012.
URL https://www.sciencedirect.com/science/article/pii/S1068520017300536

  * [20] P. Layec, A. Dupas, A. Bisson, S. Bigo, Qos-aware protection in flexgrid optical networks, J. Opt. Commun. Netw. 10 (1) (2018) A43–A50.  doi:10.1364/JOCN.10.000A43.
URL http://jocn.osa.org/abstract.cfm?URI=jocn-10-1-A43

  * [21] P. Layec, A. Dupas, A. Bisson, S. Bigo, Qos-aware protection in flexgrid optical networks, in: 2017 Optical Fiber Communications Conference and Exhibition (OFC), 2017, pp. 1–3.
  * [22] M. Sivakumar, K. M. Sivalingam, A. K. Somani, Partial protection in optical wdm networks: Enhanced support for dynamic traffic, in: 2006 3rd International Conference on Broadband Communications, Networks and Systems, 2006, pp. 1–8.  doi:10.1109/BROADNETS.2006.4374328.
  * [23] G. Kuperman, E. Modiano, A. Narula-Tam, Partial protection in networks with backup capacity sharing, in: National Fiber Optic Engineers Conference, Optical Society of America, 2012, p. NW3K.4.  doi:10.1364/NFOEC.2012.NW3K.4.
URL http://www.osapublishing.org/abstract.cfm?URI=NFOEC-2012-NW3K.4

  * [24] M. Sivakumar, A. K. Somani, J. Fang, K. M. Sivalingam, On partial protection in groomed optical wdm mesh networks, in: Proceedings. 2005 International Conference on Dependable Systems and Networks, IEEE Computer Society, Los Alamitos, CA, USA, 2005, pp. 228–237.  doi:10.1109/DSN.2005.73.
URL https://doi.ieeecomputersociety.org/10.1109/DSN.2005.73

  * [25] A. Das, C. U. Martel, B. Mukherjee, A partial-protection approach using multipath provisioning, in: 2009 IEEE International Conference on Communications, 2009, pp. 1–5.  doi:10.1109/ICC.2009.5198655.
  * [26] T. W. K. T. Guoliang Xue, Weiyi Zhang, On the partial path protection scheme for wdm optical networks and polynomial time computability of primary and secondary paths, Journal of Industrial & Management Optimization 3 (4) (2007) 625–643.
  * [27] H. Wang, E. Modiano, M. Medard, Partial path protection for wdm networks: end-to-end recovery using local failure information, in: Proceedings ISCC 2002 Seventh International Symposium on Computers and Communications, 2002, pp. 719–725.  doi:10.1109/ISCC.2002.1021753.
  * [28] S. S. Savas, C. Ma, M. Tornatore, B. Mukherjee, Backup reprovisioning with partial protection for disaster-survivable software-defined optical networks 31 (2).  doi:10.1007/s11107-015-0563-6.
URL https://doi.org/10.1007/s11107-015-0563-6

  * [29] C. S. K. Vadrevu, R. Wang, M. Tornatore, C. U. Martel, B. Mukherjee, Degraded service provisioning in mixed-line-rate wdm backbone networks using multipath routing, IEEE/ACM Transactions on Networking 22 (3) (2014) 840–849.  doi:10.1109/TNET.2013.2259638.
  * [30] Z. Zhong, J. Li, N. Hua, G. B. Figueiredo, Y. Li, X. Zheng, B. Mukherjee, On qos-assured degraded provisioning in service-differentiated multi-layer elastic optical networks, in: 2016 IEEE Global Communications Conference (GLOBECOM), 2016, pp. 1–5.  doi:10.1109/GLOCOM.2016.7842043.
  * [31] B. O. Nassar, T. Tachibana, Degraded provisioning of spectrum and holding time with qos assurance in elastic optical networks, in: 2019 24th OptoElectronics and Communications Conference (OECC) and 2019 International Conference on Photonics in Switching and Computing (PSC), 2019, pp. 1–3.  doi:10.23919/PS.2019.8817760.
  * [32] F. Lisboa, K. V. O. Fonseca, L. C. Vieira, P. Monti, G. B. Figueiredo, J. de Santi, Restoration based on bandwidth degradation and service restoration delay for optical cloud networks, in: GLOBECOM 2017 - 2017 IEEE Global Communications Conference, 2017, pp. 1–6.  doi:10.1109/GLOCOM.2017.8254773.
  * [33] A. P. Vela, M. Ruiz, F. Cugini, L. Velasco, Combining a machine learning and optimization for early pre-fec ber degradation to meet committed qos, in: 2017 19th International Conference on Transparent Optical Networks (ICTON), 2017, pp. 1–4.  doi:10.1109/ICTON.2017.8025009.
  * [34] G. Junyent, J. Comellas, Using dual-path allocation for partial traffic protection in elastic optical networks, in: 2017 19th International Conference on Transparent Optical Networks (ICTON), 2017, pp. 1–4.  doi:10.1109/ICTON.2017.8024849.
  * [35] D. T. Hai, H. T. Minh, L. H. Chau, Qos-aware protection in elastic optical networks with distance-adaptive and reconfigurable modulation formats, Optical Fiber Technology 61 (2021) 102364\.  doi:https://doi.org/10.1016/j.yofte.2020.102364.
URL https://www.sciencedirect.com/science/article/pii/S1068520020303540

  * [36] D. T. Hai, On the spectrum-efficiency of qos-aware protection in elastic optical networks, Optik 202 (2020) 163563.  doi:https://doi.org/10.1016/j.ijleo.2019.163563.
URL https://www.sciencedirect.com/science/article/pii/S0030402619314615

  * [37] P. Layec, A. Dupas, A. Bisson, S. Bigo, Qos-aware protection in flexgrid optical networks, in: 2017 Optical Fiber Communications Conference and Exhibition (OFC), 2017, pp. 1–3.
  * [38] A. Dupas, P. Layec, D. Verchère, S. Bigo, Bandwidth variable transmitter for software defined networks, in: 2017 Optical Fiber Communications Conference and Exhibition (OFC), 2017, pp. 1–3.
  * [39] A. Dupas, P. Layec, D. Verchère, S. Bigo, Bandwidth variable transmitter for software defined networks, in: 2017 Optical Fiber Communications Conference and Exhibition (OFC), 2017, pp. 1–3.
  * [40] L. Velasco, M. Klinkowski, M. Ruiz, J. Comellas, Modeling the routing and spectrum allocation problem for flexgrid optical networks, Photonic Netw. Commun. 24 (3) (2012) 177–186.
  * [41] C. Politi, V. Anagnostopoulos, C. Matrakidis, A. Stavdas, A. Lord, V. López, J. P. Fernández-Palacios, Dynamic operation of flexi-grid ofdm-based networks, in: OFC/NFOEC, 2012, pp. 1–3.
  * [42] I. I. CPLEX, High-performance mathematical programming engine (Dec. 2016).
URL http://www.ibm.com