A major challenge in network service providers is to provide adequate resources in service level agreements based on forecasts of future demands. In this paper, we address the problem of capacity provisioning in a network subject to demand uncertainty such that a network coded multicast is applied as the data delivery mechanism with limited budget to purchase extra capacity. We address some particular type of uncertainty sets that obtain a tractable constrained capacity provisioning problem. For this reason, we first formulate a mathematical model for the problem under uncertain demand. Then, a robust optimization model is proposed for the problem to optimize the worstcase system performance. The robustness and effectiveness of the developed model are demonstrated by numerical results. The robust solution achieves more than 10% reduction and is better than the deterministic solution in the worst case.
1. Introduction
N
etwork coding generalizes traditional routing paradigm in which nodes are allowed to perform arbitrary operation on information received to generate output. Recent developments in network technology have caused many content providers offering data dissemination services. One of the most important strategies for these content providers is to determine resource requirements with respect to uncertain demands. Overprovisioning leads to wasted resources and unnecessary payments, while underprovisioning results in potentially prohibitive additional charges. Hence, the content provider should consider a cost balancing procedure, based on forecasts of expected customer usage patterns and demands. As demand is not completely predetermined, the content provider should resort to forecast based on marketing reports or historical usage patterns when making decisions.
In this paper, we consider the capacity provisioning problem where (1) the content provider employs multicast network with coded packets as its underlying data dissemination method, (2) demand from receivers is uncertain, and (3) the total costs of extra capacity purchased should not exceed a given budget level. We present a robust optimization model for capacity planning when faced with uncertain demands. It is assumed that uncertain demands belong to a closed, convex, independent, and bounded uncertainty set. We address some particular type of uncertainty sets that obtain a tractable constrained capacity provisioning problem.
The structure of the paper is as follows: In the next section, after introducing notations used in this paper, the standard formulation for minimum cost multicast whit network coding is presented. In Section 3, we present the robust optimization model adapted for the constrained capacity provisioning problem. In addition, after considering types of uncertainty sets, conditions for solving the constrained capacity provisioning problem efficiently are identified. We present our numerical results in Section 4, and finally present concluding remarks.
2. Related Work
Network coding is a promising generalization of routing, which allows a network node to generate output messages by encoding its received messages to improve the throughput, robustness, and security. Ahlswede et al.
[1]
shown that network coding is able to achieve the maximum flow/ minimumcut bound on the multicast capacity. Li et al.
[2]
proved that linear coding achieves an optimal throughput of a multicast capacity, and later, Erez, et al.
[3]
proposed a distributed linear code construction for the deterministic wireless multicast relay network model. A new network coding signature scheme is proposed to solve vulnerable to pollution attacks where malicious node(s) can flood the network with invalid packets and prevent the receiver from the right decoding in
[4]
. Wu et al.
[5]
constructed a coding scheme to realize the maximum multicast transportation task. They proposed a dynamic coding and routing algorithm to route packets gradually from source node to destinations. Lun et al.
[6]
presented a linear optimization formulation to find a minimumcost multicast over coded packet networks. A set of distributed solutions for optimizing the configuration of network coding in both wireline and wireless networks is provided in
[7]
. Raayatpanah et al.
[8]
proposed a mixed integer linear programming to establish Minimum cost multiple multicast network coding with quantized rates. Moreover, the quality of service requirements with network coding considered works
[9

11]
.
One of the most issues for the content providers is determining resource requirements with respect to uncertain demands. The uncertainty of the future demand implies that forecasts of expected customer usage patterns and demands should be balanced against the cost for the initial provisioning process. Sen et al.
[12]
proposed a network planning mechanism with random demand. They employed a samplingbased algorithm for capacity planning in the face of uncertain demands. Gopinathan et al.
[13]
, presented a twostage stochastic optimization model for the capacity provisioning problem. They designed two approximation algorithms to solve the problem. A stochastic optimization method usually starts by assuming the uncertainty has a probabilistic description, while in most applications the distributions of uncertain parameters are not known due to insufficient information. There are several reasons for this situation, such as measurement and forecasting errors. A better strategy in the problems with uncertainty can be solutions that are not optimal for a given value of the parameters but are efficient for all possible uncertainty outcomes; that is, they are robust. The concept of robust optimization was first introduced by Soyster
[14]
. He discussed uncertain hard constraints in linear programming models. BenTal and Nemirovski
[15]
and El Ghaoui et al.
[16]
addressed this topic by allowing uncertainty sets for the data to be conic set, which includes bounded polyhedral and ellipsoid. Bertsimas and Sim
[17]
proposed a different approach to control the level of conservatism in a solution that leads to a linear optimization model.
3. Problem Definition
 3.1 Preliminary
A communication network is represented by a directed graph
G
= (
V
,
A
)=, where
V
is the set of nodes and
A
is the set of arcs in
G
. Each arc
e
= (
i
,
j
) represents a lossless pointtopoint arc from node
i
to node
j
. For arc
e
= (
i
,
j
) we will have head(e) = j and tail(e) = i. For node
i
∈
V
, terms
denote the set of arcs leaving node
i
(tail(e) = i) and entering node i (head(e) = i), respectively. Let
z_{e}
denote the rate in which coded packets are injected on arc
e
. Transmit cost
c_{e}
denotes the cost per unit rate of sending coded packets over arc
e
. The capacity of arc
e
is denoted by
u_{e}
and defined to be the number of packets that can be sent over arc
e
in one time unit. We assume that arc capacities are nonnegative integer numbers. A single session multicast is considered in this paper, where a source node,
s
∈
V
, must transmit an integer number of
R
packets per unit time to every terminal in a set of
T
= {
t
_{1}
,
t
_{2}
,...,
t_{r}
} ⊆
V
terminals. Let
K
= {1,2,...
r
} be the set index of
T
. Define
to be the flow of packets on arc
e
towards receiver
t_{k}
.
Employing network coding enables an optimal multicast flow to be computed in polynomial time
[6]
. A fundamental result of network coding states that a multicast rate of
R
is feasible if and only if it is a feasible unicast rate from source to each receiver separately
[1]
. A direct consequence is that efficient multicast can be viewed as the union of conceptual unicast flows from source to every receiver
[18]
. The minimum cost multicast with network coding is then given by the following optimization problem
[11]
:
where
Constraint (1.1) is the rate of coded packets on each arc ethat is the maximum of all flow packets using that arc i.e.,
Constraint (2.1) states the flow conservation in nodes that all multicast receivers should have a flow rate of
R
. Finally, the flow on each arc must respect capacity constraints, as stated in Constraint (3.1).
The above model can be written in matrix form as follows:
where
N
is the nodearc incidence matrix.
As an example, consider the network depicted in
Fig. 1
. All arcs have unit capacity and the cost per unit rate shown beside each link. The target of the deterministic multicast rate is 1 from
s
to two receivers,
t
_{1}
and
t
_{2}
. An optimal solution to Problem 1 for this network is shown in
Fig. 2
. We have the rate of coded packets on each arc (
i
,
j
),
, as we expect from the Constraint (1.1). The total cost multicast with network coding in this case is
. Without network coding, the cheapest routing scheme incurs a cost of 10, that shows routing using network coding incurs a cheaper cost in general than routing without network coding.
A network with multicast from s to {t_{1},t_{2}}. Each link is marked with its cost.
Each arc is marked with the triple
In next subsection, we formulate the minimum cost coding subgraph problem with the uncertain rate of
R
and a limited budget to purchase extra capacity.
 3.2 Robust Modeling
In this section, we formulate a model for the constrained capacity provisioning problem assuming that the transmit rate
R
belongs to a given uncertainty set. The total cost of extra capacity purchased is bounded by a certain amount of available budget,
D
. These assumptions lead to the following optimization problem under uncertainty transmit rate.
where
w_{e}
is the extra capacity purchased on arc
e
, and
d_{e}
is its unit cost. The uncertainty parameter
R
belongs to the closed bounded and convex uncertainty set
U_{R}
.
The robust solution is defined as the solution that achieves the best worstcase objective function value. Therefore, such solution can be obtained by solving the following robust counterpart problem:
The robust counterpart of the stochastic problem with recourse, is the socalled adjusted robust counterpart problem (ARC), introduced in
[19]
. Assume that set
U_{R}
is closed, convex, and bounded. Given such uncertainty, it is natural to separate decision variables
X ^{k}
,
Z
, and
W
make the decision on variables
W
prior to observing the traffic conditions (realizations of
R
), and finally, let the coded packet rate,
Z
, adapt to these conditions. Thus, our problem is a stochastic problemwith recourse and the adjusted robust counterpart problemis obtained by:
For the feasibility of the above problem, we have assumed that for all
R
∈
U_{R}
, there exists values of
Z
and
X
such that the constraints are satisfied. Note that ARC is an extension of RC and it is evident that
Z_{ARC}
≤
Z_{RC}
.
Lemma 1.
Adjusted robust counterpart problem, (5), is equivalent to Problem (6) below, and both problems have the same optimal solution
W
and
Z_{ARC}
=
Z_{R}
.
Proof.
For any vector
W
≥ 0 and
R
∈
U_{R}
let set
F
(
W
,
R
) be the set of feasible solutions as follows:
F
(
W
,
R
) = {
Z
 0 ≤
X^{k}
≤
Z
, ∀
k
∈
K
,
NX^{k}
=
σ^{k}
, ∀
k
∈
K
,
Z
≤
U
+
W
}. For all
R
∈
U_{R}
there exists
Z
∈
F
(
W
,
R
) and
CZ
≤
γ
. Equivalently, for all
R
∈
U_{R}
, we have
γ
≥ min
_{Z∈F(W,R)}
CZ
. In other words,
γ
≥ max
_{R}
min
_{Z∈F(W,R)}
CZ
, which concludes the proof.
■
In the next section, we concentrate on identifying the conditions on the uncertainty set that yield a tractable ARC for the problem.
 3.3 Proposed Solution
In this section, we present some particular type of uncertainty sets, which lead to a linear problem solvable in polynomial time. Depending on a given uncertainty set, we can obtain different robust counterpart problems. BenTal and Nemirovski
[15]
shown that the RC of a linear programming (LP) is equivalent to an LP when uncertainty set is a polyhedron and to a quadratically constrained convex program when uncertainty set is a bounded ellipsoidal set. The uncertainty sets in this work are defined as deviations from a nominal value of the uncertain parameter.
In first, we define
ψ
(
W
) as follows:
In the following subsections, we identify conditions on uncertainty set
U_{R}
under which we can evaluate
ψ
(
W
) efficiently.
First, we investigate difficulties faced in solving the problem. Let
Z
(
R
) = min{
CZ
 0 ≤
X^{k}
≤
Z
,
NX^{k}
=
σ^{k}
, ∀
k
∈
K
,
Z
≤
U
+
W
} which denote the value of this LP as a function of the righthandside parameter
R
. It is wellknown that the objective function
Z
(
R
) is a piecewise linear convex function of
R
on set
U_{R}
[20]
. Therefore, in general, the problem max
_{R∈UR}
Z
(
R
) is intractable since
U_{R}
is convex. However, as will be shown, the multicast problem with special structure of
U_{R}
is tractable.
Lets define
U_{R}
such that max
_{R∈UR}
Z
(
R
) is unique, and
R
^{0}
and
R^{l}
,
l
= 1,2,...,
L
denote the nominal data and basic shift, respectively.
Case 1.
U_{R}
= {
R

R
^{0}

δ_{l}
≤
R
≤
R
^{0}
+
δ_{u}
} where
δ_{l}
,
δ_{u}
≥ 0 and
R
^{0}

δ_{l}
≥ 0.
In this case,
R
^{0}
+
δ_{u}
is maximum element of
U_{R}
, so implies that
Case 2.
.
For each
R
∈
U_{R}
we got:
, so we have:
Case 3.
.
For each
R
∈
U_{R}
we got:
, so we have:
Let
be the optimal solution in cases 1, 2 and 3. Consequently
Therefore, we obtain the following linear model, which solved in polynomial time.
4. Experimental Classification Results and Analysis
In this section, we investigate the relative merit of the robust solution in comparison with deterministic solution through simulations. Also, the performance of our model was compared with the model proposed by Xi and Yeh
[7]
. Such comparison is based on the following parameters:

ZD: Optimal value of the deterministic solution

ZR: Optimal value of the robust solution

ZWC: Objective value of the deterministic solution under its worstcase scenario
ZD
is computed as the optimal value of the objective function of Problem (3) for the deterministic multicast rate
R
. Let
WD
be the optimal extra capacity purchased for the deterministic problem. The value
ZR
is obtained by solving the appropriate tractable characterization of Model (5), which is Model (8). Finally, the worstcase value
ZWC
is obtained by removing the budget constraint and replacing the extra capacity purchased
WD
.
The classic butterfly network is considered as the first scenario. The topology of the butterfly network with one source and two receivers is shown in
Fig. 3
. The nominal transmit cost and extra capacity cost are shown on the links of the butterfly network as shown in
Fig. 3
(a) and (b), respectively. The capacity of each link is assumed to be one unit and the nominal transmit rate is
R
^{0}
= 2 and set budget,
D
= 9.
Butterfly network
First, we consider an uncertainty set of transmit rate
R
changing in the interval [
R
^{0}

δ
,
R
^{0}
+
δ
] where
δ
∈ [0,1].
In
Fig. 4
, we plot
ZD
and
ZWC
for the Butterfly network. We consider
δ
∈ [0,1] in increments of 0.1. Note that the robust solution achieves more than 10% reduction in the worstcase value with a smaller than 2%increase in the value for the nominal data. Also, note that for
δ
≥ 1 model
ZWC
becomes infeasible, whereas model
ZR
is feasible.
Comparison of optimal value of the deterministic solution (ZR ) with the objective value of the deterministic solution under its worstcase scenario (ZWC )
We now compare the performance of the robust and deterministic solution for all cases through the following ratio:
The quantity
r_{wc}
is the relative improvement of the robust solution in the worst case. The ratio
r_{wc}
measures the maximum protection that a robust solution can provide against the worstcase realization of the uncertainty.
Note the relative improvement of the robust solution reduced with increase
δ
. Since
δ
close to 1, coded packet keeps increasing the benefit of the robust solution decreases, as it must route flow through the other path. The robust solution is better than the deterministic solution in the worst case. Here, we also observe that
r_{wc}
decreases for flows larger than a certain level and that this drop can be substantial.
In cases 2 and 3, we consider basic shift for
L
= 10 that shown
Table 1
. We consider rates in uncertain set
U_{R}
for cases 2 and 3 and obtain
r_{wc}
for each of them. The simulation results are summarized in
Table 2
. The results show that the robust solutions provide a sufficient protection in the worstcase scenario on the nominal data. These results also indicate that the robust strategy has a better performance in comparison to the deterministic one, in particular as the uncertainty increases.
Value of basic shift data
Value of basic shift data
Relative improvement of the robust solution in the worst case
Relative improvement of the robust solution in the worst case
Moreover, the performance of our model was compared with the model proposed by Xi and Yeh
[7]
to better understand performance evaluation of the procedure.
Xi and Yeh
[7]
presented the problem of finding a minimum cost multicast (MCM) over coded packet networks. It was shown that the solution to the problem can be computed using a linear optimization model and they provided a set of distributed solutions to solve it.
We ran the method on randomly generated graphs in order to resemble realworld networks using directed graph (RDG) method. RDG was generated according to the methodology proposed by Erdos and Renyi
[21]
, where it was assumed that there was a link from node i to node j with probability 0.5. Next, for each link, two uniform random numbers were generated from an interval, say [a, b], in order to represent the cost of link and extra capacity. In our experiments, we selected [a ,b] equal to [5,15]. Moreover, for each link, parameters
u_{e}
and
w_{e}
were randomly allocated an integer number between 1 and 3 according to a uniform probability distribution. The source node and the destinations were chosen randomly and uniformly among all of the nodes.
Two test problems with different sizes were considered and each size was performed under different multicast rate interval. Under each interval, the multicast rate,
R
, for the MCM model was randomly generated according to a discrete uniform distribution on the interval and for our model was generated according to approaches described in section (3.2). The results of experiments are reported in
Table 3
, where each simulation results corresponds to the average of 10 runs.
Simulated subgraph cost mean and standard deviation as a function of Multicast rate.
Simulated subgraph cost mean and standard deviation as a function of Multicast rate.
As the results show, the robust model obtained the solutions with both higher quality and lower standard deviations than the MCM model. In the most problems, the robust solution dominates the obtained solution of the MCM model with respect to the mean and standard deviation of objective function values. The gap between the two approaches appears to increase with the problem size correspond to performance measures, particularly for standard deviation.
Note that some networks in the MCM model for large multicast rate are infeasible which mean the capacity of arcs are insufficient and need to purchase extra capacity.
5. Conclusion
In this paper, we consider the minimumcost multicast transmission over coded packet networks where the receiver rates are not fixed. We formulated the problem using the best worstcase guaranteed robust optimization technique. Accordingly, a tractable problem for general uncertainty sets is formulated to compute the robust solution. Our computational results show that the robust solution significantly reduces the worstcase cost, in particular for higher uncertainty levels.
Acknowledgements
This research project has been supported by the office of vice chancellor for research of Islamic Azad University, Khorasgan(Isfahan) Branch. The author greatly appreciates this office for financial support.
BIO
Hossein Ghasvari received his B.S. and M.S. degrees in Electrical Engineering from Isfahan University Of Technology, Isfahan, Iran, in 2004 and 2006, respectively. In 2009, he also earned a Ph.D degree in Electrical Engineering from Islamic Azad University, Science and Research , Tehran, Iran. He is currently an Assistant Professor in the Department of Electrical Engineering, Islamic Azad University, Kashan, Isfahan, Iran. His research interests include Network Coding Optimization.
Mohammad Ali Raayatpanah received his B.Sc. degree from Kashan University, Esfahan, Iran, in 2004, and the M.Sc. degree from Tehran University, Tehran, Iran, in 2006, in Applied Mathematics. He also received his PhD degree in Applied Mathematics from the department of mathematics, statistics and computer science of the University of Tehran, in 2013. He is an assistant professor in the Department ofMathematical and Computer Sciences, Kharazmi University, Tehran, Iran. His current research focuses on the application of network coding in wired networks and wireless.
Ahlswede R.
,
Cai N.
,
Li S. Y. R.
,
Yeung R. W.
2000
“Network information flow,”
IEEE Trans. Inform. Theory
46
1204 
1216
DOI : 10.1109/18.850663
Erez E.
,
Kim M.
,
Xu Y.
,
Yeh E. M.
,
Médard M.
2014
“Deterministic network model revisited: An algebraic network coding approach,”
Information Theory, IEEE Transactions on
60
(8)
4867 
4879
DOI : 10.1109/TIT.2014.2329840
Zhang J.
,
Shao J.
,
Ling Y.
,
Ji M.
,
Wei G.
,
Ying B.
2014
“Efficient multiple sources network coding signature in the standard model,”
Concurrency and Computation: Practice and Experience
Wu L.
,
Curran K.
2012
“A practical network coding and routing scheme based on maximum flow combination,”
International Journal of Network Management
22
(5)
373 
396
DOI : 10.1002/nem.1797
Lun D. S.
,
Ratnakar N.
,
Médard M.
,
Koetter R.
,
Karger D. R.
,
Ho T.
,
Ahmed E.
,
Zhao F.
2006
“Minimumcost multicast over coded packet networks,”
Information Theory, IEEE Transactions on
52
(6)
2608 
2623
DOI : 10.1109/TIT.2006.874523
Xi Y.
,
Yeh EM.
2010
“Distributed algorithms for minimum cost multicast with network coding,”
IEEE/ACM Trans Netw
18
(2)
379 
392
DOI : 10.1109/TNET.2009.2026275
Raayatpanah MA.
,
Salehi Fathabadi H.
,
Khalaj BH.
,
Khodayifar S.
2012
“Minimum cost multiple multicast network coding with quantized rates,”
Computer Network
57
1113 
1123
DOI : 10.1016/j.comnet.2012.11.017
Raayatpanah MA.
,
Salehi Fathabadi H.
,
Bahramgiri H.
,
Pardalos P.M.
2013
“Optimalconstrained multicast subgraph over coded packet networks,”
Journal of Combinatorial Optimization
1 
16
Raayatpanah MA
,
Salehi Fathabadi H.
,
Khalaj BH.
,
Khodayifar S.
,
Pardalos P.M.
2014
“Bounds on endtoend statistical delay and jitter in multiple multicast coded packet networks,”
Journal of Network and Computer Applications
41
217 
227
DOI : 10.1016/j.jnca.2013.12.004
Sen S.
,
Doverspike R. D.
,
Cosares S.
1994
“Network planning with random demand,”
Telecommunication Systems
3
(1)
11 
30
DOI : 10.1007/BF02110042
Gopinathan A.
,
Li Z.
“Stochastic multicast with network coding,”
in Proc. of International Conference on Distributed Computing Systems
2009
no. 5158461
500 
509
Soyster A.L.
1973
“Convex programming with setinclusive constraints and applications to inexact linear programming,”
Operations Research
21
1154 
1157
DOI : 10.1287/opre.21.5.1154
BenTal A.
,
Nemirovski A.
2000
“Robust solutions of linear programming problems contaminated with uncertain data,”
Math. Programming
88
411 
424
DOI : 10.1007/PL00011380
Li Z.
,
Li B.
“Efficient and Distributed Computation of Maximum Multicast Rates,”
in Proc. of INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies
2005
vol. 3
BenTal A.
,
Goryashko A.
,
Guslitzer E.
,
Nemirovski A.
2004
“Adjustable robust solutions of uncertain linear programs,”
Math Program
99
351 
376
DOI : 10.1007/s101070030454y
Ahuja R.
,
Magnanti T.
,
Orlin J.
1993
“Network flows: theory, algorithms, and applications,”
Prentice Hall
Bollobás B.
2001
“Random graphs,” vol. 73
Cambridge University Press