Advanced
Robust Capacity Planning in Network Coding under Demand Uncertainty
Robust Capacity Planning in Network Coding under Demand Uncertainty
KSII Transactions on Internet and Information Systems (TIIS). 2015. Aug, 9(8): 2840-2853
Copyright © 2015, Korean Society For Internet Information
  • Received : January 28, 2015
  • Accepted : June 01, 2015
  • Published : August 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Hossien Ghasvari
Department of Electrical and Computer Engineering, Khorasgan(Isfahan) Branch, Islamic Azad University, Isfahan, Iran
Mohammad Ali Raayatpanah
Faculty of Mathematical Sciences and Computer, Kharazmi University, Tehran, Iran

Abstract
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 worst-case 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.
Keywords
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. Over-provisioning leads to wasted resources and unnecessary payments, while under-provisioning 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 pre-determined, 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/ minimum-cut 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 minimum-cost 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 sampling-based algorithm for capacity planning in the face of uncertain demands. Gopinathan et al. [13] , presented a two-stage 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. Ben-Tal 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 point-to-point 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
PPT Slide
Lager Image
denote the set of arcs leaving node i (tail(e) = i) and entering node i (head(e) = i), respectively. Let ze denote the rate in which coded packets are injected on arc e . Transmit cost ce denotes the cost per unit rate of sending coded packets over arc e . The capacity of arc e is denoted by ue 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 ,..., tr } ⊆ V terminals. Let K = {1,2,... r } be the set index of T . Define
PPT Slide
Lager Image
to be the flow of packets on arc e towards receiver tk .
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] :
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
where
PPT Slide
Lager Image
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.,
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
where N is the node-arc 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 ),
PPT Slide
Lager Image
, as we expect from the Constraint (1.1). The total cost multicast with network coding in this case is
PPT Slide
Lager Image
. 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.
PPT Slide
Lager Image
A network with multicast from s to {t1,t2}. Each link is marked with its cost.
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
where we is the extra capacity purchased on arc e , and de is its unit cost. The uncertainty parameter R belongs to the closed bounded and convex uncertainty set UR .
The robust solution is defined as the solution that achieves the best worst-case objective function value. Therefore, such solution can be obtained by solving the following robust counterpart problem:
PPT Slide
Lager Image
The robust counterpart of the stochastic problem with recourse, is the so-called adjusted robust counterpart problem (ARC), introduced in [19] . Assume that set UR 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:
PPT Slide
Lager Image
For the feasibility of the above problem, we have assumed that for all R UR , 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 ZARC ZRC .
Lemma 1. Adjusted robust counterpart problem, (5), is equivalent to Problem (6) below, and both problems have the same optimal solution W and ZARC = ZR .
PPT Slide
Lager Image
Proof. For any vector W ≥ 0 and R UR let set F ( W , R ) be the set of feasible solutions as follows:
F ( W , R ) = { Z | 0 ≤ Xk Z , ∀ k K , NXk = σk , ∀ k K , Z U + W }. For all R UR there exists Z F ( W , R ) and CZ γ . Equivalently, for all R UR , we have γ ≥ min ZF(W,R) CZ . In other words, γ ≥ max R min ZF(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. Ben-Tal 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:
PPT Slide
Lager Image
In the following subsections, we identify conditions on uncertainty set UR under which we can evaluate ψ ( W ) efficiently.
First, we investigate difficulties faced in solving the problem. Let Z ( R ) = min{ CZ | 0 ≤ Xk Z , NXk = σk , ∀ k K , Z U + W } which denote the value of this LP as a function of the right-hand-side parameter R . It is well-known that the objective function Z ( R ) is a piecewise linear convex function of R on set UR [20] . Therefore, in general, the problem max RUR Z ( R ) is intractable since UR is convex. However, as will be shown, the multicast problem with special structure of UR is tractable.
Lets define UR such that max RUR Z ( R ) is unique, and R 0 and Rl , l = 1,2,..., L denote the nominal data and basic shift, respectively.
Case 1. UR = { 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 UR , so implies that
PPT Slide
Lager Image
Case 2.
PPT Slide
Lager Image
.
For each R UR we got:
PPT Slide
Lager Image
, so we have:
PPT Slide
Lager Image
Case 3.
PPT Slide
Lager Image
.
For each R UR we got:
PPT Slide
Lager Image
, so we have:
PPT Slide
Lager Image
Let
PPT Slide
Lager Image
be the optimal solution in cases 1, 2 and 3. Consequently
PPT Slide
Lager Image
Therefore, we obtain the following linear model, which solved in polynomial time.
PPT Slide
Lager Image
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 worst-case 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 worst-case 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.
PPT Slide
Lager Image
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 worst-case 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.
PPT Slide
Lager Image
Comparison of optimal value of the deterministic solution (ZR ) with the objective value of the deterministic solution under its worst-case scenario (ZWC )
We now compare the performance of the robust and deterministic solution for all cases through the following ratio:
PPT Slide
Lager Image
The quantity rwc is the relative improvement of the robust solution in the worst case. The ratio rwc measures the maximum protection that a robust solution can provide against the worst-case 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 rwc 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 UR for cases 2 and 3 and obtain rwc 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 worst-case 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
PPT Slide
Lager Image
Value of basic shift data
Relative improvement of the robust solution in the worst case
PPT Slide
Lager Image
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 real-world 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 ue and we 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.
PPT Slide
Lager Image
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 minimum-cost multicast transmission over coded packet networks where the receiver rates are not fixed. We formulated the problem using the best worst-case 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 worst-case 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.
References
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
Li S. , Yeung R. , Cai N. 2003 “Linear network coding,” IEEE Trans Inf Theory 49 (2) 371 - 381    DOI : 10.1109/TIT.2002.807285
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 “Minimum-cost 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
Xuan Y. , Lea CT. 2011 “Network-coding multicast networks with QoS guarantees,” IEEE/ ACM Trans Netw 19 (1) 265 - 274    DOI : 10.1109/TNET.2010.2062533
Raayatpanah MA. , Salehi Fathabadi H. , Bahramgiri H. , Pardalos P.M. 2013 “Optimal-constrained multicast sub-graph 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 end-to-end 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 set-inclusive constraints and applications to inexact linear programming,” Operations Research 21 1154 - 1157    DOI : 10.1287/opre.21.5.1154
Ben-Tal A. , Nemirovski A. 2000 “Robust solutions of linear programming problems contaminated with uncertain data,” Math. Programming 88 411 - 424    DOI : 10.1007/PL00011380
El-Ghaoui L. , Oustry F. , Lebret H. 1998 “Robust solutions to uncertain semidefinite programs,” SIAM J. Optim. 9 33 - 52    DOI : 10.1137/S1052623496305717
Bertsimas D. , Sim M. 2004 “The price of robustness,” Operations Research 52 (1) 35 - 53    DOI : 10.1287/opre.1030.0065
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
Ben-Tal A. , Goryashko A. , Guslitzer E. , Nemirovski A. 2004 “Adjustable robust solutions of uncertain linear programs,” Math Program 99 351 - 376    DOI : 10.1007/s10107-003-0454-y
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