Video-on-demand optimization using an interior-point algorithm

Title: Video-On-Demand Optimization Using an Interiorpoint Algorithm Author: Luis Felipe Urquiza Aguiar Advisor: Jordi Castro Department: Statistics and Operations Research. University: Universitat Politècnica de Catalunya (UPC) Academic year: 2017/2018 Interuniversity Master in Statistics and Operations Research UPC-UB Universitat Polit`ecnica de Catalunya Facultat de Matem`atiques i Estad´ıstica Master Thesis Video-On-Demand Optimization Using an Interior-point Algorithm Luis Felipe Urquiza Aguiar Advisor: Jordi Castro Department of Statistics and Operations Research, Research Group GNOM (Group on Numerical Optimization and Modeling) To my daughter Nuria and my mom Yolanda. They are two angels in my life equally beautiful. Abstract Keywords: CDN, VoD, optimal placement, interior point methods, BlockIP MSC2000: 90-02, 90B15, 90B18 A Content Delivery Network (CDN) aims to provide efficient movement of massive digital content (multimedia and files) across the Internet. This is achieved by putting the content in servers closer to the costumer. Video-On-Demand service is an application of CDN where videos have to be located strategically to avoid network congestion and servers’ saturation. Therefore, the problem of optimal placement of videos arises. This problem has a block diagonal structure with linking constraints on links’ and servers’ capacities. In this project, we solve huge instances of a video placement problem over three real network topologies with a specialized interior point solver named BlockIP. The evaluated instances range from 7 to 300 millions of variables and the difficulty of the instances depends on the size of servers, links’ bandwidth and network topology. Our results: 1) verified characteristics of BlockIP like regularization and the intensive computation in the last iterations and 2) showed that BlockIP found optimal solution in all the evaluated instances with a good optimality gap. On the contrary, state-of-art CPLEX cannot reach an optimal, feasible solution in some difficult instances and needs almost twice the memory of BlockIP. However, CPLEX solved most of feasible instances at least twice faster than BlockIP Contents Chapter 1. Introduction 1 1. Interior Point Methods 2 1.1. Primal-dual path-following methods 2 2. BlockIP 5 2.1. Solving the normal equations by PCG 7 2.2. Improving the spectral radius 8 2.3. Estimating the spectral radius 9 2.4. Implementation details 9 3. Optimization for Content Delivery Networks 10 3.1. Content Delivery Networks Overview 10 3.2. Optimization models for Content Delivery Networks 12 Chapter 2. Optimal Placement for Video On Demand Systems 13 1. The problem formulation 13 1.1. Parameters and variables 13 1.2. The model 14 2. Input Instance 18 Chapter 3. Implementation and Results 27 1. Implementation Details 27 2. Results for small instances 28 2.1. Ebone 28 2.2. Sprintlink 31 2.3. Tiscali 34 3. Results for big instances 38 3.1. Ebone 38 3.2. Sprintlink 40 3.3. Tiscali 42 Chapter 4. Conclusions 45 References 47 iii 6 1. INTRODUCTION (15) min k X i=0 fi(xi) s. to      A1 ... Ak L1. . . LkI           x1 . . . xk x0      =     b1 . . . bk b0      0≤xi≤uii= 0, . . . , k. Matrices Ai∈Rmi×niand Li∈Rl×ni,i= 1, . . . , k define the block and linking constraints, respectively, kbeing the number of blocks. Vectors xi∈Rni, i = 1, . . . , k, are the variables for each block. x0∈Rlare the slacks of the linking constraints. bi∈Rmi, i = 1, . . . , k is the right-hand-side vector for each block of constraints, whereas b0∈Rlis for the linking constraints. The upper bounds for each group of variables are defined by ui, i = 0, . . . , k. Note that with this standard formulation linking constraints are of the form b0−u0≤Pk i=1 Lixi≤b0. Slacks of linking constraints play a significant role in the quality of the preconditioner, and they should not be removed. Equality linking constraints can be formulated by setting u0≈0. Functions fi:Rni→R,i= 0, . . . , k, are assumed to be convex. Although the specialized IPM to be described is valid for any fi, for the sake of efficiency we will restrict to separable functions, i.e., ∇2fi(xi) are (positive semidefinite) diagonal matrices. Note that any convex quadratic problem can be transformed into a separable equivalent one by the addition of extra variables and constraints Exploiting the structure of A, and appropriately partitioning Θ of (12), as follows A=     A1 ... Ak L1. . . LkI      Θ =      Θ1 ... Θk Θ0      , the matrix of system (13) can be recast as (16) AΘA>=          A1Θ1A> 1A1Θ1L> 1 .... . . AkΘkA> kAkΘkL> k L1Θ1A> 1. . . LkΘkA> kΘ0+Pk i=1 LiΘiL> i          =B C C>D, B∈R˜nטn(˜n=Pk i=1 ni), C∈R˜n×land D∈Rl×lbeing the blocks of AΘA>, and Θi,i= 0, . . . , k, the submatrices of Θ associated with the k+ 1 groups of variables in (15), i.e., Θi= (ZiX−1 i+WiS−1 i+∇2fi(xi))−1. Denoting by gthe right-hand- side of (13), and appropriately partitioning gand ∆λ, the normal equations can be 2. BLOCKIP 7 1. Algorithm PCG(S, M, ¯g, ∆λ20, ,imax) 2. // Solve S∆λ2= ¯gby PCG with preconditioner M 3. Initializations: i:= 0;r0:= ¯g−S∆λ20; 4. Solve Mz0=r0;p0:= z0; 5. while ||rk|| >  and i < imax do 6. qi:= Spi; 7. αi:= (z> iri)/(p> iqi); 8. ∆λ2i+1 := ∆λ2i+αipi; 9. ri+1 := ri−αiqi; 10. Solve Mzi+1 =ri+1; 11. βi:= (z> i+1ri+1)/(z> iri); 12. pi+1 := zi+1 +βipi; 13. i:= i+ 1; 14. end while 15. Return ∆λ2:= ∆λ2i; 16. End algorithm Fig. 1. The PCG algorithm for the solution of S∆λ2= ¯g≡g2− C>B−1g1with preconditioner M written as (17) B C CTD ∆λ1 ∆λ2=g1 g2. 2.1. Solving the normal equations by PCG. Eliminating ∆λ1from the first group of equations of (17), we obtain (D−C>B−1C)∆λ2= (g2−C>B−1g1)(18) B∆λ1= (g1−C∆y2).(19) System (19) is solved by performing kCholesky factorizations, one for each diagonal block AiΘiA> i, i = 1 . . . k, of B. System (18) with the Schur complement (20) S=D−C>B−1C, of dimension l—the number of linking constraints—, may exhibit a large fill-in, and it is prohibitive if computed by Cholesky factorization. It will be solved by a PCG, which is outlined in Figure 1. The preconditioner used in this work is from [12],[12]. It relies on the fact that (20) is a P-regular splitting, i.e., Sis symmetric and positive definite, Dis nonsingular and D+C>B−1Cis positive definite. Therefore, the spectral radios ρ(D−1(C>B−1C)) <1 is guaranteed by [6],[44, pp. 254–255] This allows us to compute the inverse of S[12, Prop. 4], as (21) (D−C>B−1C)−1= ∞ X i=0 (D−1(C>B−1C))i!D−1. The preconditioner M−1is an approximation of S−1obtained by truncating the infinite power series (21) at some term h. For instance, for h= 0 and h= 1 we have M−1=D−1if h= 0, M−1= (I+D−1(C>B−1C))D−1if h= 1. 8 1. INTRODUCTION 1. Algorithm Mz =r(D, C, B, r, h) 2. v:= D−1r; 3. z0:= v; 4. for j:= 1 to hdo 5. zj:= D−1(C>(B−1(Czj−1))) + v; 6. end for 7. Return z:= zh Fig. 2. Algorithm for computing z=M−1r The larger h, the better the approximation of the inverse. On the other hand, systems Mz =r(for some vectors zand r) have to be solved at each PCG iteration (step 10 of PCG algorithm of Figure 1), and any extra term in the series means an additional linear system solution with matrix B. This is clearly seen in the algorithm of Figure 2, which shows how Mz =ris iteratively computed in the specialized interior-point solver. Note that matrix C>B−1Cdoes not need to be built, and aside from the solution of systems with Band D, only matrix-vector products with Cand C>(i.e., with Li,L> i,Aiand A> i,i= 1, . . . , k) are required. This also applies to the PCG algorithm of Figure 1. It is thus possible to partially apply the matrix-free paradigm [29]. Efficient implementations of this matrixvector products for particular Aiand Li,i= 1, . . . , k, matrices can significantly speed the computational efficiency. It is worth noting that, although (21) is valid for any primal block-angular problem, the preconditioner is only useful in practice for separable problems; otherwise, nondiagonal Θimatrices make systems with B prohibitive. 2.2. Improving the spectral radius. The quality of the preconditioner depends on ρ, which is always in [0,1): the farther from 1, the closer M−1is to S−1. In practice it has been observed that ρcomes closer to 1 as we approach the optimal solution for most instances. However, as shown in [16], non-zero Hessians reduce ρ, and this opens the possibility for improving the preconditioner by the addition of a quadratic regularization term In practice, if the problem is linear or the Hessian is close to 0, a non-zero Hessian can be added by a quadratic regularization. The interior-point solver BlockIP implements two types of regularization: a proximal point and a quadratic regularization. The later is based on the addition of a quadratic term to the standard logarithmic barrier function B(x, µ) of (1) (22) B(x, µ),f(x) + µ − n X i=1 ln xi− n X i=1 ln(ui−xi)!, µ∈R+being the barrier parameter. In the quadratic regularization introduced in [16]B(x, µ) is replaced by (23) BQ(x, µ),f(x) + µ 1 2x>QRx− n X i=1 ln xi− n X i=1 ln(ui−xi)!, QRbeing a diagonal positive semidefinite matrix. The reduction of BQto 0 is controlled by µ, the standard barrier parameter. 2. BLOCKIP 9 Using either Bor BQonly changes the dual feasibility of KKT conditions and matrix Θ, defined in (2) and (12), respectively. Dual feasibility becomes A>λ+z−w=∇f(x) for B,and(24) A>λ+z−w=∇f(x) + µQRxfor BQ.(25) (25) is equivalent to (24) when µtends to zero (i.e., when we approach the optimal solution).The Θ matrices are Θ = (ZX−1+WS−1+∇2f(x))−1for B, and(26) Θ =(µQR+ZX−1+W S−1+∇2f(x))−1for BQ.(27) µQRtends to zero with µand therefore (27) approximates (26) when they are close to the optimal solution. 2.3. Estimating the spectral radius. Although knowing the spectral radius ρ of D−1(C>B−1C) would be instrumental to forecast the efficiency of the preconditioner, its computation is impractical. However, a procedure to estimate ρwas recently introduced in [11] for h= 0, i.e., M−1=D−1. By linear algebra, if σmin is the minimum eigenvalue of I−D−1(C>B−1C) then 1 −σmin is the spectral radius of D−1(C>B−1C). The minimum eigenvalue σmin of I−D−1(C>B−1C) can be estimated from the solution of (13) by PCG, using the Ritz values from the relation between PCG and Lanczos method (see [35], [33, Chapter 9],[38] for details). In general, the extreme eigenvalues of the preconditioned matrix (the ones we are interested in, for the estimation of the spectral radius) are well approximated already during early PCG iterations [38]. The estimation of σmin have been extended in [19] to consider any number h≥0 of terms in the power series preconditioner. For these cases ρcan be easily estimated as h+1 √1−˜σmin, where ˜σmin is the smallest Ritz value. 2.4. Implementation details. BlockIP is written in C++, using the object oriented paradigm. It is roughly about 14000 lines of source code, aside from the external package for Cholesky factorization. Actually, BlockIP is only linked to the Ng-Peyton block sparse Cholesky package [42], which only implements an approximate minimum degree ordering; other more recent Cholesky packages can be added in the future, which may likely improve the performance of the solver. The package can be obtained for research purposes from http://www-eio.upc. edu/˜jcastro/BlockIP.html. a reference manual and an example illustrating the use of the package. The main features that BlockIP includes are: (1) BlockIP may handle linear, quadratic and convex linearly constrained blockangular optimization problems. (2) BlockIP stops at the feasible point of iteration jwhen the relative gap between the primal and dual objectives, denoted by pjand dj, is below some optimality gap. The relative gap is computed as (pj−dj)/(1 + pj). (3) BlockIP implements two types of directions: the standard Newton direction and the second order heuristic direction of [37], which requires the solution of two systems (13) with different right-hand-sides. Both directions can be 10 1. INTRODUCTION computed by solving the normal equations by either a Cholesky factorization or by the PCG-based approach of Subsection 2.1. In general, the reduction of iterations caused by the second order direction is not worthwhile when using PCG, since, as far as we know, the solution of the first system can not be efficiently used as a warm-start for the second one. Indeed, from the results of [12] this strategy was not successful for multicommodity flows problems. (4) The solver implements quadratic regularizations presented in Subsection 2.2.Following [16], the quadratic regularization matrix QRof (23) is heuristically updated at each interior-point iteration ias QR:= δ·i·µi/µ0I, where µ0and µiare the barrier parameter at the starting and current point, and δis a (usually small) initial regularization value. The product by i, the iteration counter, is an attempt to compensate for the quick reduction of µi when the optimal solution is approached. (5) BlockIP may compute the Ritz values, and thus the spectral radius ρ, for any number hof terms in the preconditioner. (6) Problems can be provided in four different formats. (a) The most efficient way is using the BlockIP callable library, which provides routines to create problems from matrices and vectors. Particular matrix formats (network—oriented and nonoriented—, general rowwise or columnwise, diagonal, identity, etc.) can be exploited through the callable library. Nonlinear objective functions—including gradient and Hessian evaluations—have to be provided as C++ routines. (b) Problems can also be efficiently provided by an input file using a specific format for BlockIP. This format consists on a set of scalars, vectors and sparse matrices defining the problem parameters. (c) Input files can also be in structured MPS format, an extension of the well-known MPS format created for BlockIP. Standard packages can read structured MPS files without modification. (d) The last format is based on SML [22], a structure-conveying modeling language based on the popular AMPL [26] modeling language. In addition to hooking BlockIP to it, SML was extended to deal with nonlinear separable problems (see [34] for details). 3. Optimization for Content Delivery Networks This section introduces the main ideas about Content Delivery Networks (CDN) and how operational research has been used in this context. 3.1. Content Delivery Networks Overview. A CDN is a collection of network elements spanning the Internet, where content is replicated over mirrored servers (i.e., point of presence (PoP), edge or replica servers), located at the border of the Internet service providers’ (ISP’) networks to which end-users are connected [40]. A high level architecture of a CDN is depicted in Fig. 3. The idea is to put the most likely requested content from users in the PoPs closer to customers. In short, 3. OPTIMIZATION FOR CONTENT DELIVERY NETWORKS 11 a CDN mitigates that every request from users has to be served by the (usually distant) origin server. Fig. 3. High-level architecture of a CDN. [40] A CDN can be very useful to provide high quality, live streaming coverage of major events, distributing user generated content (e.g., YouTube), providing fast and efficient software downloads to customers, or enhancing the performance of an ecommerce website. A classical application, dealt in this thesis, is the Video on Demand distribution (VoD). VoD service can be seen as a virtual video rental store in which a user can choose and watch any program on request, at the convenience of their time. Video is a very sensitive application from packet losses, end-to-end delay or delay variation (jitter). Without a CDN, bandwidth is overused as each request for the same content is retransmitted over and over from origin server and video performance degrades (i.e., higher packet losses, delay and jitter), especially when the number of users increases. On the other hand, With a CDN, bandwidth usage of the content provider is optimized, as if a single end-user has requested unique content only once. No additional investment is required by the content provider to increase bandwidth capacity, as media content is packaged for delivery by the CDN infrastructure, once it has been placed in the PoPs. Two types of CDNs can be distinguished according the level of awareness of the underlying network [40] Pure-play CDN: CDNs that provide over-the-top (OTT) delivery of video and audio content without the ISPs being involved in the control and distribution of the content itself. Carrier/Telco CDN: Broadband providers and Telcos, that provide content delivery as a means to reduce the demands on the network backbone and reduce infrastructure investment A CDN can be useful for large-scale video streaming. Good Quality of Experience (QoE) in user for video services requires high network bandwidth and low network loading to avoid contention. Thus, centralized video server may obtain satisfactory performance with low video demands because of big Internet infrastructure between them. As demand grows, QoE gets increasingly worse. A CDN can improve content delivery by ensuring that network resources are utilized efficiently. On one hand, 12 1. INTRODUCTION Without a CDN, bandwidth is overused as each request for the same content is retransmitted over and over. On the other hand, with a CDN, bandwidth usage of the content provider is optimized as media content is packaged for delivery by the CDN infrastructure 3.2. Optimization models for Content Delivery Networks. Currently, stringent requirements on quality-of-service (QoS) mechanisms, ever-increasing amount of content to be distributed and the wild CDN market competition makes efficient use of available resources highly relevant. Therefore, in the deployment of a CDN arises optimization problems for resources management, allocation, and pricing. We will concentrate on resource management and allocations in CDNs. VoD applications primarily differ from other CDN services by their requirement of significant amounts of bandwidth. There are three main problems about managing and allocating resources in a CDN [48]: Proxy Server Location Problem: Consists of finding the number and location of a given number of proxy (also called cache or mirror) servers to be deployed, such that a predefined measure (e.g., traffic flow, total cost) is minimized. The mathematical models for this problem are based on or variations of, the uncapacitated p-median or facility location problems. Request Routing: Routing in a computer network refers to sending data from one or more sources to one or more destinations so as to minimize the total traffic flowing in the network. Request routing in a CDN is the process of guiding a client’s request to a suitable proxy server that is able to serve the corresponding request. The problem is formally defined as selecting a proxy server to address a request for an object such that a cost function is minimized. Object Placement: Most of the formulations for CDNs assume that the whole content is entirely replicated onto the caching servers. Unfortunately, this may not always be possible in situations where the objects are significantly large in size (i.e., multimedia files) or the number of objects is huge. In those cases only a partial replication can be performed due to the limited storage capacity of the caching servers (i.e., PoPs). Therefore, any caching server can only hold a subset of the content. Determining which objects should be placed at each caching server under storage capacity restrictions is known as the object placement problem. A good review of the optimization problems associated with CDNs can be found in [48] and the references therein. Mathematical models for resource allocation in CDNs has substantially grown and become more complex problems by including simultaneous consideration of one or more of the three main problems above. In this project, we deal with a combined problem of video placement and request routing. In addition, the problem to be solved considers a Carrier CDN because we use network topologies from three major Telecommunication companies. Therefore, the objective is to reduce the network load while guarantee that all videos are stored at some server and user demands are satisfied without exceeding carrier network capacities. Chapter 2 Optimal Placement for Video On Demand Systems This chapter presents the optimization model employed in this project to assign the videos to storage locations (i.e., PoP) across a CDN. The model was originally proposed in [4] and [3]. The objective of the model is to minimize the total data transfer between nodes to satisfy the video demand which are not available in the local repository. In addition, the chapter describes the topology networks and data used to test the model. 1. The problem formulation As we anticipated, the optimization problem aims to find the assignment strategy for videos to minimize the network load. To provide realism to the solution, the model considers a credible request pattern of videos for the peak hours of the weekend. Moreover, the model considers links and disk capacity constraints. In general, videos on CDN must be completely stored in a location. This makes the optimization model a Mixed Integer Problem (MIP) and therefore challenging because the solutions should not be fractional. Nonetheless, even with the relaxation of the integer variables, the problem remains difficult because of its huge number of variables and constraints. 1.1. Parameters and variables. Table 1 summarizes the input data and decisions variables used in the optimization model for location of videos in a CDN. Let Vdenote the set of CDN’s PoPs. To agree with the terminology of Applegate et al. [3], we refer to PoPs as Video Hub Offices (VHOs). The VHOs store videos to distribute them to the local clients. Lrepresent the set of links that connect the nodes with an associated capacity BlMbps. The library of videos to be optimally located among the VHO i∈Vis denoted by M. Every VHO ihas an storage capacity, also known as disk capacity, Di. Alike, each video m∈Mhas a size SmGB and needs a bitrate of rmMbps to be transmitted along the network. To communicate any two nodes i, j ∈V, they use the shortest directed path Pi,j ∈L, computed in advanced (i.e., the path is fixed in the model and does not change 13 14 2. OPTIMAL PLACEMENT FOR VIDEO ON DEMAND SYSTEMS Table 1. Parameters and Decision variables used in model for VoD placement. Parameter Value Vset of VHO (vertices) Lset of directed links Mset of videos Tset of times slices Didisk capacity at i∈V(in GB) Smsize of video m∈M(in GB) Pij set of links on path from i∈Vto serve request at j∈V Blcapacity of link l∈L(in Mbps) rmbitrate of video m∈M(in Mbps) am jaggregate number of request for video mat VHO j fm j(t) number of request for video mat VHO jactive at time t cij cost of transferring one GB from VHO ito VHO j Decision Variable Meaning ym ibinary variable indicating if video mis stored at VHO i xm ij fraction of request for video mat VHO jserved by VHO i regardless the traffic in the network). The path Pi,j is used to serve a request of a video min node jfrom a distant VHO i. Thus, if a video is served locally, the path is empty Pi,i =∅. The total demand of a video m∈Mfrom each VHO j∈Vfor the week is denoted by am j. Moreover, the simultaneous demand for videos fm j(t) from a node jat a peak hour t∈Tis used to ensure that the links l∈Lare not overloaded. Finally, cij refers the cost to transfer 1GB from node ito j. Recalling that to reach j, the data has to travel along the path Pij, authors that proposed the VHO location model suggest to use: (28) cij =α|Pij|+β, where |Pij|refers to the number of nodes that traverses the path between iand j, αis the cost of sending 1GB over any link in L, and βis a fixed cost for satisfying a request such as lookup operations or local delivery. Regarding the decision variables, xm ij is the fraction of requests of video mat VHO jthat are fulfilled from VHO i. Thus, xii is the portion of videos served locally.The other set variables ym iindicates if node istores the video m.ym iis a binary variable because a video cannot be stored partially. 1.2. The model. The objective of the model is to minimize the total cost of retrieving videos from remote locations during a period, subject to constraints of disk space and link bandwidth. The formulation of the linear relaxation of this MIP is as follows: 1. THE PROBLEM FORMULATION 15 min xm ij , ym iX m∈MX i,j∈V Smam jcijxm ij (29) s.t. X i∈V xm ij = 1,∀m∈M, j ∈V(30) xm ij ≤ym i,∀m∈M, i, j ∈V(31) X m∈M Smym i≤Di,∀i∈V(32) X m∈MX i,j∈V: l∈Pij rmfm j(t)xm ij ≤Bl,∀l∈L, ∀t∈T(33) xm ij ≥0,∀m∈M, i, j ∈V(34) ym i≥0,∀m∈M, i, j ∈V.(35) The objective function expressed by (29) is the total cost of transferring videos among VHOs to serve the total requests of videos am jfrom all j∈V. Constraint (30) guarantees that the total demand of video min any VHO jis satisfied by the sum of fractions xij served from the set of nodes i∈V. Therefore, xij have to be non-negative as constraint (34) states. Constraint (31) satisfies the fact that only a node that stores a video mcan deliver requests of it. Constraint (32) refers to the limited storage capacity of each VHO. Constraint (33) assures that the bandwidth of each link Blis not overflow during the rush hours of the weekend. Originally, since a whole video has to be located in a location, this ym imust be 0 or 1, however, in this project we focus on solving the linear relaxation expressed by constraint (35). Indeed the (optimal) solution of the binary formulation is beyond the limits of current technology. Solving the linear relaxation is already a hard task. After an inspection of the problem, reader can realize that variables xm ij and ym i from different values monly appears together in constraints (33) and (32), respectively. Hence, constraints (30) and (31) are arranged in |M|independent, separable, diagonally located blocks of equations. This is precisely, the structure of problems for which the specialized solver BlockIP was designed. Now, we carefully study the structure of one of these identical |M|blocks. To do this, we define xm j,ym,D(xm j) and D(ym) as: xm j=         xm 1j xm 2j . . . xm nj         ,ym=         ym 1 ym 2 . . . ym n         ,D(xm j) =         xm 1j0. . . 0 0xm 2j0 . . ..... . . 0 0 . . . xm nj         ,D(ym) =         ym 10. . . 0 0ym 20 . . ..... . . 0 0 . . . ym         . Then the block of constraints corresponding to video mis given by (36). 22 2. OPTIMAL PLACEMENT FOR VIDEO ON DEMAND SYSTEMS Table 3 shows the values of disk size and bandwidth used to build the problem instance for five video library sizes in the three network topologies. There are two additional sizes of libraries (i.e., 200k and 1000k videos). However, we do not test them because they are too large to be executed in our server. Table 3. Disk sizes and link capacities for instance generation of VHO problem. Sprintlink Tiscali Ebone Number of Disk Link Disk Link Disk Link Disk Link videos type type size BW size BW size BW (GB) (Mbps) (GB) (Mbps) (GB) (Mbps) small large 260 2000 180 3750 440 2000 5k large small 860 425 870 150 1000 900 large large 860 2000 870 3750 1000 2000 small large 540 3750 360 8000 880 4500 10k large small 1780 700 1760 300 2020 1700 large large 1780 3750 1760 8000 2020 4500 small large 1070 7500 720 16000 1740 8500 20k large small 3530 1500 3530 650 4000 3250 large large 3530 7500 3530 16000 4000 8500 small large 2700 19000 1810 37500 4380 21000 50k large small 8910 3750 8880 1500 10070 8500 large large 8910 19000 8880 37500 10070 21000 small large 5400 38000 3600 77500 8760 45000 100k large small 17800 7200 17600 3250 20140 17000 large large 17800 38000 17600 77500 20140 45000 To conclude this section we show the topologies of the three networks, i.e., Ebone, Sprintlink and Tiscali in Figs. 3, 4 and 5, respectively. These plots show the connectivity among VHOs, their comparative disk size and the link utilization. It is clear that they are difficult instance for the video placement problem because Links with number of shortest path through them are not necessarily connected to VHOs with big disk size. 2. INPUT INSTANCE 23 Links Use Disk Size Fig. 3. Ebone Network. 24 2. OPTIMAL PLACEMENT FOR VIDEO ON DEMAND SYSTEMS Link Use Disk Size Fig. 4. Sprintlink Network. 2. INPUT INSTANCE 25 Links Use Disk Size Fig. 5. Tiscali Network. Chapter 3 Implementation and Results This chapter presents the implementation details and results from testing the VHO instances in Ebone, Sprintlink and Tiscali networks with BlockIP solver. More precisely, we test the BlockIP’s solver options with the smallest instances (i.e., 5000 videos in the library) for these three networks. Afterwards, we only evaluate bigger instances with BlockIP set up that provided best results. We decided to follow this path because the time to solve an instance increases considerably with the number of variables. Afterwards, in order to compare the performance of BlockIP, we solve the same instances with CPLEX, properly configured to get a fair analysis. 1. Implementation Details To solve the optimal video location problem in network of Video Hub Offices, we used the BlockIP callable library. The first step was to read the problem information, which includes: transfer cost for videos, aggregate an peak hours demand, disk sizes, and paths among nodes. Then, with these data, we build block matrix 39 and linking matrices 40, After that, we create the problem with the routines provided by BlockIP library. The resulting program, written in C++ as BlockIP, as well as the input data can be download from http://www. lfurquiza.com/research/codes. The zip file includes an awl script to run a batch of problems and does not include BlockIP.BlockIP can be downloaded from http://www-eio.upc.edu/˜jcastro/BlockIP.html. The options of BlockIP that we will test are: Type of direction: BlockIP has two ways to compute the direction of movement: automatic and second order (predictor-corrector). The first one use the Newton direction. The latter can be more precise than the automatic option, nevertheless it comes at the cost of a greater number of conjugate gradient iterations because it solves two systems of equations. A value h= 0 was considered for the number of terms of the power series preconditioner. Infeasibility tolerance: BlockIP allow us to set the infeasibility tolerance of the solution provided by the solver. A high tolerance could lead to a shorter time for getting a solution. 27 28 3. IMPLEMENTATION AND RESULTS Quadratic Regularization factor: The quadratic regularization helps linear optimization problems to find an optimal solution faster than without regularization because quadratic regularization decreases the spectral radius and makes PCG more efficient. As the regularization factor increases the importance of quadratic terms in the objective function increases as well and this could modify the value of the objective function and the dual feasibility condition. We compare BlockIP results with state-of-the-art CPLEX 12.5 package. Regarding CPLEX, we set it to use only one thread because BlockIP do not exploit parallelism. In addition, we set the barrier algorithm 3 and the optimality gap equal to the obtained by BlockIP. The CPU time provided for CPLEX is only for the barrier iterations, without crossover. All runs were carried out on a server at 2.60 GHz Intel Xeon E5-2690 CPUs with 192 gigabytes of memory, under a GNU/Linux operating system (OpenSuse 13.2) 2. Results for small instances The smallest instance for the three different network topology are obtained by using the library of 5000 videos. So, the resulting problem has five thousand diagonal blocks. The actual number of variables into a block depends on the numbers of VHO in the network. Among the three networks, Tiscali will produce the largest problem and Ebone the smallest one. 2.1. Ebone. As we said, the smallest instances produce 5000 blocks. In the case of Ebone Network this number of blocks leads to a total number of variables of 7935175. The detailed information of variables and constraints are depicted in Table 1. Parameter Value Block Variables 1587 Block Constraints 1058 Linking constraints 175 Total Variables 7935175 Total constraints 5290175 Table 1. Descriptive information of smallest instance in Ebone network with a library of 5000 videos Table 2 shows the results of testing the aforementioned BlockIP options in the 5k instance of Ebone network. The fist two rows of each section of the Table 2 show the results of using automatic direction, none regularization factor (i.e., Q=0) and the infeasibility gaps of 1e-7 and 1e-2. These results indicates that a tight infeasibility gap do not affect the solution time. Hence, we test the other options combinations of BlockIP that uses automatic direction with an infeasibility of 1e-7. Regarding the option second order direction, we test this option with a infeasibility gap of 1e-2. Results show that the intensive computation operations that this 2. RESULTS FOR SMALL INSTANCES 29 options demands is not worthing for this particular problem because the optimality gap is not better than the obtained with automatic direction. Moreover, a more strict infeasibility gap of 1e-7 leads to the same results and increases even more the solution time as it can be seen for the instance with disks of 440GB and links of 2200 Mbps. The best results for the Ebone network for a library size of 5000 videos were obtained with automatic direction and a quadratic regularization factor. The best regularization factor depends on the disk size and link capacity of the instance at hand. For the small disks and large links (i.e., 440GB and 2200 Mbps) a regularization factor of 20 gets and optimality gap in the order of 1e-5 with smallest number of PCG iterations per BlockIP major iteration (See Fig. 1a) and therefore the greatest average number of BlockIP iterations per minute (Fig. 1b) and in the shortest time. 0 10 20 30 40 50 60 0,0 0,1 1,0 10,0 15,0 20,0 30,0 1000/2200 1000/900 440/2200 (a) PCG iterations per BlockIP iteration vs Quadratic regularization factor 0 1 2 3 4 5 6 7 0,0 0,1 1,0 10,0 15,0 20,0 30,0 1000/2200 1000/900 440/2200 (b) BlockIP iterations per minute vs Quadratic regularization factor Fig. 1. BlockIP performance for different values of quadratic regularization in Ebone network with a library of 5000 videos On the other hand, in the scenario with “big” disks and tight links capacities (1000 GB and 900 Mbps), a factor of 1.0 or 100 lead to 2% optimal solution. The more feasible instance (1000 GB and 2200 Mbps) needs a more conservative regularization factor of 0.1 or 1.0 to reach a 0.01% optimal solution. Notice that, the optimality gap improvement got in the latter instance due to the use of quadratic regularization is not as important as in the two previous, more challenging instances. Additionally, the use of a regularization factor comes at the cost of a slightly increment in the infeasibility of dual solutions, however it is not significant. We also include Fig. 2 to show the performance of BlockIP decreases while it approaches to the optimum solution, as it was pointed out in [19]. Results showed in Fig. 2 are from the most time demanding instance of “small” disks - “large” links. As in the reader can notice in the last 25% of iterations the estimated spectral radius of the inverse of (20) is 1 (See Fig. 2a) and therefore the number of PCG iterations needed in those cases increases considerable (Fig. 2b). From these results, it is reasonable to conclude that most of the solution time is due to the last iterations. However, for VHO problem is not possible to switch to full Cholesky factorization to overcome this issue, as [19] suggested, because of the size of the problem. 30 3. IMPLEMENTATION AND RESULTS Type Option BlockIP Primal Objective Dual Objective Opt. C. Grad. Time Dir. Feas. Reg. Iterat. Value Feas. Gap Value Feas. Gap Gap iterat. (min) 440/2200 auto 1e-7 0.0 201 3.053808e+07 3.44e-02 2.845779e+07 4.20e-16 6.81e-02 10128 119.69 440/2200 auto 1e-2 0.0 201 3.053808e+07 3.44e-02 2.845779e+07 4.20e-16 6.81e-02 10128 120.07 440/2200 S.O. 1e-7 0.0 86 3.756273e+07 9.05e-03 -1.733239e+07 3.30e-15 1.46e+00 16760 208.64 440/2200 S.O. 1e-2 0.0 86 3.756273e+07 9.05e-03 -1.733239e+07 3.30e-15 1.46e+00 16760 181.27 440/2200 auto 1e-7 0.1 199 3.054501e+07 3.43e-02 2.845959e+07 1.10e-06 6.83e-02 9896 121.49 440/2200 auto 1e-7 1.0 218 3.025824e+07 2.69e-02 2.875234e+07 1.19e-05 4.98e-02 12141 147.51 440/2200 auto 1e-7 10.0 225 2.991432e+07 1.76e-02 2.966640e+07 7.08e-05 8.29e-03 10589 130.41 440/2200 auto 1e-7 15.0 204 3.014656e+07 2.34e-02 3.004562e+07 1.05e-04 3.35e-03 7121 90.34 440/2200 auto 1e-7 20.0 182 3.045123e+07 3.11e-02 3.044938e+07 1.45e-04 6.09e-05 5038 79.30 440/2200 auto 1e-7 30.0 216 2.988471e+07 1.57e-02 3.071943e+07 1.56e-04 2.79e-02 8312 105.25 1000/900 auto 1e-7 0.0 123 1.008823e+07 2.90e-03 9.761668e+06 9.19e-06 3.24e-02 2294 33.42 1000/900 auto 1e-2 0.0 123 1.008823e+07 2.90e-03 9.761668e+06 9.19e-06 3.24e-02 2294 33.45 1000/900 S.O. 1e-2 0.0 95 1.082892e+07 5.86e-05 7.942960e+06 7.11e-06 2.67e-01 15691 172.30 1000/900 auto 1e-7 0.1 104 1.041669e+07 1.21e-02 9.433713e+06 6.26e-06 9.44e-02 1437 23.73 1000/900 auto 1e-7 1.0 121 1.010332e+07 3.43e-03 9.807502e+06 9.76e-06 2.93e-02 2131 32.76 1000/900 auto 1e-7 10.0 122 1.006919e+07 2.62e-03 1.027935e+07 4.73e-05 2.09e-02 2073 31.32 1000/900 auto 1e-7 15.0 128 1.007763e+07 2.83e-03 1.054288e+07 7.17e-05 4.62e-02 2151 32.49 1000/900 auto 1e-7 20.0 141 1.007381e+07 2.76e-03 1.074588e+07 8.64e-05 6.67e-02 2539 38.66 1000/900 auto 1e-7 30.0 156 1.006752e+07 2.17e-03 1.113910e+07 1.22e-04 1.06e-01 2982 44.22 1000/2200 auto 1e-7 0.0 154 9.689621e+06 6.77e-05 9.687891e+06 3.95e-08 1.79e-04 1613 28.84 1000/2200 auto 1e-2 0.0 154 9.689621e+06 6.77e-05 9.687891e+06 3.95e-08 1.79e-04 1613 28.53 1000/2200 S.O. 1e-2 0.0 71 9.824971e+06 2.26e-05 9.610221e+06 6.96e-07 2.19e-02 2846 37.07 1000/2200 auto 1e-7 0.1 150 9.688294e+06 7.73e-05 9.687697e+06 1.45e-07 6.17e-05 1469 26.26 1000/2200 auto 1e-7 1.0 145 9.688574e+06 5.49e-05 9.687784e+06 6.25e-07 8.16e-05 1257 24.16 1000/2200 auto 1e-7 10.0 154 9.689392e+06 4.93e-05 9.697077e+06 1.44e-06 7.93e-04 1386 26.43 1000/2200 auto 1e-7 15.0 154 9.687499e+06 6.41e-05 9.688836e+06 8.59e-08 1.38e-04 2451 39.55 1000/2200 auto 1e-7 20.0 193 9.688062e+06 8.01e-06 9.697415e+06 1.01e-06 9.65e-04 2406 40.43 1000/2200 auto 1e-7 30.0 239 9.688306e+06 4.69e-06 9.712916e+06 2.68e-06 2.54e-03 4108 65.95 Table 2. Results with BlockIP for Ebone network with a library of 5000 videos (diagonal blocks). This problem has 7935175 variables 2. RESULTS FOR SMALL INSTANCES 31 0,25 0,35 0,45 0,55 0,65 0,75 0,85 0,95 1,05 1 10 19 28 37 46 55 64 73 82 91 100 109 118 127 136 145 154 163 172 181 190 199 Q=0 Q=20 (a) Spectrum ratio vs BlockIP iterations 0 20 40 60 80 100 120 140 160 180 200 220 1 10 19 28 37 46 55 64 73 82 91 100 109 118 127 136 145 154 163 172 181 190 199 Q=20 Q=0 (b) PCG iterations vs BlockIP iterations Fig. 2. BlockIP performance along iterations in Ebone network with a library of 5000 videos. The results are from an instance with average disk size of 440GB and link’s bandwidth of 2200 Mbps The results obtained with CPLEX are shown in Table 3. CPLEX is faster than BlockIP for the VHO problem. Nevertheless, CPLEX is only able to find an optimal solution for the most feasible problem among the three evaluated instances. CPLEX was unable to find feasible primal solutions for the challenging combinations of small disks/large link capacities and big disks / small link capacities. Type Iter Primal Objective Dual Objective Opt. Time Value Feas. Gap Value Feas. Gap Gap (min) 440/2200∗241 3.0255e+07 5.14e-01 2.8462e+07 1.57e-6 5.92e-02 18.64 1000/900∗186 1.0163e+07 1.35e-01 9.8543e+06 4.31e-07 3.05e-02 14.88 1000/2200 157 9.6879e+06 2.98e-05 9.6879e+06 3.28e-07 1.55e-07 12.71 Table 3. Results with CPLEX for Ebone network with a library of 5000 videos. Non-optimal solutions are marked with ∗ For the small instance in the Ebone network we can conclude that BlockIP finds optimal and feasible solutions in very tight instances (i.e., problems with a small feasible region). However, when VHO instances are more feasible, CPLEX clearly outperforms BlockIP in terms of processing time. 2.2. Sprintlink. For the Sprintlink network the 5000 blocks reach a total number of 16335309 variables. The details are in Table 4. Table 5 shows the results of testing options of BlockIP options in the 5k instance of Sprintlink network. As for Ebone network, the fist two rows of each section of the table show the results of using automatic direction, none regularization factor (i.e., Q=0) and the infeasibility gaps of 1e-7 and 1e-2. These results agree with Ebone ones regarding that a relaxed infeasibility gap (i.e., 1e-2) does not degrade the solution but in these instances it reduces the solution time. Hence, we test the other options combinations of BlockIP that uses automatic direction with an infeasibility of 1e-2. Regarding the option second order direction, we test this option with a infeasibility gap of 1e-2. Results show that the intensive computation operations that this option demands 38 3. IMPLEMENTATION AND RESULTS other hand, CPLEX outperforms BlockIP in both processing time and optimality gap, only in the instance with big disks and large links’ bandwidth. It is important that, as happened in Sprintlink network, BlockIP with second-order direction it is a strong option to solve the problem with the third instance because it reach the optimum faster than with automatic direction. 3. Results for big instances In this section, we test the best BlockIP settings in the most feasible instances of the three networks with video libraries from 10000 to 200000 videos (blocks in the problem). Table 10 summarizes the options that we will try in the big disk, large link capacities instances. Network BlockIP options name Type of Feasibility Quadratic Direction Gap Regularization factor Ebone auto 1e-7 1.0 Sprintlink auto 1e-2 1.0 second-order 1e-2 0.0 Tiscali auto 1e-7 1.0 second-order 1e-2 0.0 Table 10. Best BlockIP settings for most feasible instances of VHO problem with a library of 5000 videos. 3.1. Ebone. For this network we present results considering the best setting (quadratic factor Q=1.0, feasibility gap of FG=1e-7) and with default setting (Q=0, FG=1e-7). We aim to get a better idea on how quadratic regularization help in these big instances. Table 11 reports the size of the video library, the total number of variables and constraints, the options used in BlockIP, the number of iterations, the value of the objective function, the total number PCG iterations and the solution time. The same table, also includes the corresponding values, if applicable, for the solutions obtained by CPLEX solver. Results show that as the library size doubles its size, BlockIP , in average, triples its solution time. On the contrary, CPLEX increases its solution time in the same proportion that the video library does. This fact can be seen in Fig. 7a. Fig. 7b shows the low consumption of RAM memory of BlockIP compared to CPLEX. In fact, BlockIP needed almost the half of memory than CPLEX for the VHO problems that have solved. This careful use of memory of BlockIP allowed to solve a very huge instance in Ebone network (200k videos, last result in Table 11) while CPLEX ran out of memory in the process. 3. RESULTS FOR BIG INSTANCES 39 Problem Info Option BlockIP Primal Objective Opt. C. Grad. Time Noblocks Variables Constraints Dir. Feas. Reg. Iterat. Value Feas Gap Gap iterat. (min) 5k 7935175 5290175 auto 1e-7 0.0 154 9.689621e+06 6.77e-05 1.79e-04 1613 28.84 auto 1e-7 1.0 145 9.688574e+06 5.49e-05 8.16e-05 1257 24.16 CPLEX 157 9.6879e+06 2.98e-05 1.55e-07 N/A 12.71 10k 15870175 10580175 auto 1e-7 0.0 182 1.919569e+07 1.85e-05 1.82e-04 2351 78.51 auto 1e-7 1.0 168 1.919669e+07 1.98e-05 2.21e-04 1717 75.17 CPLEX 178 1.919362e+07 4.47e-03 3.6e-06 N/A 30.96 20k 31740175 21160175 auto 1e-7 0.0 200 3.815495e+07 1.98e-05 1.08e-03 2179 151.24 auto 1e-7 1.0 200 3.814375e+07 1.68e-05 1.33e-04 2151 150.35 CPLEX 197 3.8140117e+07 1.66e-02 1.2e-05 N/A 63.2 50k 79350175 52900175 auto 1e-7 0.0 256 9.352068e+07 4.14e-05 3.30e-03 3985 600.55 auto 1e-7 1.0 248 9.351105e+07 3.60e-05 1.47e-03 3110 599.30 CPLEX non-optimal 242 9.3508341e+07 1.57e+00 1.2e-03 N/A 199.43 100k 158700175 105800175 auto 1e-7 0.0 339 1.914746e+08 2.44e-06 4.23e-04 6100 1811.05 auto 1e-7 1.0 323 1.915064e+08 3.99e-06 9.51e-05 5590 1669.76 CPLEX 218 1.9146171e+08 4.77e-02 2.0e-05 N/A 389.9 200k 317400175 21160175 auto 1e-7 0.0 399 3.804385e+08 3.24e-05 2.97e-03 7407 4521.5 Table 11. Results with BlockIP for Ebone network with video libraries from 5000 to 200000 videos (diagonal blocks). 40 3. IMPLEMENTATION AND RESULTS 4 16 64 256 1024 4096 0 2 5 50 75 1 00 12 5 150 175 2 00 BlockIP CPLEX (a) Solution Time (log scale) vs Library size (thousands of videos) 0 25 50 75 100 125 150 175 200 225 0 25 50 75 10 0 125 150 1 75 2 00 BlockIP CPLEX (b) RAM Memory (GB) vs Library size (thousands of videos) Fig. 7. Resource use comparison between BlockIP and CPLEX as function of the number of videos for Ebone network. Results are from the most feasible instance (big disks and high link capacity). Dashed lines and red points were drawn from estimations It is important to notice that, as happen in the small instances, sometimes CPLEX cannot find a feasible, optimal solution. This is the case of Ebone instance with 50000 videos. Although BlockIP is slower than CPLEX, BlockIP solves this instance satisfactorily. 3.2. Sprintlink. For this network we present results considering the best setting (quadratic factor Q=1.0, feasibility gap of FG=1e-2) and with default setting (Q=0, FG=1e-2). In addition, we have tested BlockIP with the second-order direction for the instance with 10000 videos. Table 12 reports the results for Sprintlink with the same format used for Ebone network. Notice that for a video library of 10000 videos, second-order direction does not improves solution time of automatic direction. Fig. 8a and Fig. 8b shows the same behavior observed in Ebone. As the video library doubles its size, the solution time of BlockIP , increases at 2.5 times. On the contrary, CPLEX increases its solution time at the same rate that the video library does. Regarding memory use, BlockIP clearly outperforms CPLEX. CPLEX needs almost twice the memory space than BlockIP. Due to the fact that BlockIP needs less memory than CPLEX, it solved an instance with 100000 videos satisfactorily –this instance has more 326 millions of variables– while CPLEX got out of memory. The last instance that CPLEX tried to solved was the one with a video library of 50000 videos. In this case, CPLEX did not reach an feasible primal solution and it ended with a feasibility gap of 8.54. In the same instance BlockIP reached a remarkable feasibility gap of 1e-4. 3. RESULTS FOR BIG INSTANCES 41 Problem Info Option BlockIP Primal Objective Opt. C. Grad. Time Noblocks Variables Constraints Dir. Feas. Reg. Iterat. Value Feas Gap Gap iterat. (min) 5k 16335309 10890309 auto 1e-2 0.0 238 9.465295e+06 3.86e-06 5.11e-04 7355 199.19 S.O 1e-2 0.0 117 9.466474e+06 5.79e-07 7.08e-04 6925 177.27 auto 1e-2 1.0 239 9.464049e+06 3.03e-06 1.13e-04 7804 209.73 CPLEX 200 9.46269e+06 3.8e-06 1.1e-08 N/A 41.73 10k 32670309 21780309 auto 1e-2 0.0 289 1.876374e+07 8.48e-06 1.53e-03 8854 529.49 S.O 1e-2 0.0 141 1.875593e+07 7.80e-07 4.47e-04 9533 484.68 auto 1e-2 1.0 279 1.875968e+07 5.32e-06 2.83e-04 7634 445.61 CPLEX 196 1.8750325e+07 3.00e-03 7.4e-07 N/A 86.91 20k 65340309 43560309 auto 1e-2 0.0 339 3.755364e+07 9.30e-06 1.68e-03 10847 1176.16 auto 1e-2 1.0 330 3.752920e+07 2.14e-06 9.66e-05 10981 1153.84 CPLEX 211 3.7519346e+07 1.36e-02 1.2e-07 N/A 197.43 50k 163350309 108900309 auto 1e-2 0.0 400 9.480438e+07 2.98e-04 2.71e-02 8269 2434.41 auto 1e-2 1.0 400 9.419190e+07 4.70e-05 1.46e-03 9126 2642.27 CPLEX non-optimal 272 9.3956454e+07 8.54e+00 1.3e-03 N/A 566.65 100k 326700309 217800309 auto 1e-2 1.0 400 1.884211e+08 2.44e-06 7.92e-03 6279 4191.52 Table 12. Results with BlockIP for Sprintlink network with video libraries from 5000 to 100000 videos (diagonal blocks). 42 3. IMPLEMENTATION AND RESULTS 4 16 64 256 1024 4096 0 25 50 7 5 100 BlockIP CPLEX (a) Solution Time (log scale) vs Library size (thousands of videos) 0 25 50 75 100 125 150 175 200 225 250 0 25 50 75 10 0 BlockIP CPLEX (b) RAM Memory (GB) vs Library size (thousands of videos) Fig. 8. Resource use comparison between BlockIP and CPLEX as function of the number of videos for Sprintlink network. Results are from the most feasible instance (big disks and high link capacity). Dashed lines and red points were drawn from estimations 3.3. Tiscali. Tiscali is the most complex and large network that we used in this project. Solve large instances of this network takes too much time. Therefore, we only analyzed the instance of 10000 videos and compared its results against the smallest instance of 5000 videos. For the instance with 10000 videos, we configure a optimality gap of 0.01% in an effort to reduce solving time. Even so, BlockIP lasted around 18 hours to solve this instance. The solution time ratio between BlockIP and CPLEX is around 5, which is similar to the obtained in the two previous network topologies. Finally, it is worth noting that the solution time difference between BlockIP with second-order direction and automatic direction is not as big in the 10000 videos instance as in the smallest one. We recall that the same behavior was also present in Sprintlink network. This empirical result could indicate that in this particular problem, second-order direction is more valuable in small-size instances. 3. RESULTS FOR BIG INSTANCES 43 Problem Info Option BlockIP Primal Objective Opt. C. Grad. Time Noblocks Variables Constraints Dir. Feas. Reg. Iterat. Value Feas Gap Gap iterat. (min) 5k 36015393 24010393 auto 1e-7 1.0 350 5.859179e+06 2.2e-06 5.42e-05 13090 766.18 S.O. 1e-2 0.0 145 5.859295e+06 2.74e-06 6.22e-05 6614 377.79 CPLEX 161 5.85910e+06 1.70e-3 9.55e-7 N/A 83.2 10k 72030393 48020393 auto 1e-7 1.0 373 1.221095e+07 1.18e-04 9.54e-03 7951 1093.68 S.O 1e-2 1.0 153 1.202256e+07 2.09e-07 9.20e-03 7512 1053.17 CPLEX 182 1.1953577e+07 4.65e-03 3.17e-06 N/A 188.31 Table 13. Results with BlockIP for Ebone network with video libraries from 5000 and 10000 videos (diagonal blocks). Chapter 4 Conclusions In this thesis, we have solved large instances of a problem of optimal placement of videos for the VoD service by using the specialized BlockIP, which was designed for problems with block diagonal structure. Results show that, given a fixed amount of memory, BlockIP can deal with problems that contain twice the number of variables compared to the problems that state-of-art CPLEX can solve. BlockIP was able to solve instances with more than 300 millions of variables with optimality and feasibility gaps around 10−3. However, this memory efficiency has a downside in the time needed by BlockIP to find an optimal solutions, which is two or three times slower than CPLEX. In addition, we corroborate the propositions in [19] about the degradation of BlockIP performance when it approaches to the optimum and how a quadratic regularization factor can speed up the solution time. Other interesting result is that BlockIP found feasible, optimal solutions in some complicate instances when CPLEX cannot reach feasibility. PCG performance is completely related with structure of linking constraints. In the video location problem of this thesis, the linking constraints depends on: size of disks, links capacities and network topology. The latter is particular important because solution time varies considerably from one topology to another although the instances have similar number of variables. The VoD service considered in this work, has huge video libraries, however, videos could be grouped if they have similar request pattern and/or size. This grouping strategy could make the problem easier to solve and should be tested. In this thesis, we used a Carrier CDN with very challenging topologies. On the other hand, overlay CDNs usually have much simpler topologies by connecting sites through paths from one to three hops. These straightforward topologies could potentially be favorable for the PCG computations. Finally, modifications in the problem model as the use of additional costs to extend links or disk capacities are relevant from a CDN’s management point of view and constitute future work. 45 References [1] A. Altman and J. Gondzio, Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization, Optimization Methods & Software 11 (1999), pp. 275–302. [2] E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney and D. Sorensen, LAPACK Users’ Guide, Third edition, SIAM, Philadelphia, PA, 1999. [3] D. Applegate, A. Archer, V. Gopalakrishnan, S. Lee, and K. K. Ramakrishnan, Optimal Content Placement for a Large-Scale VoD System, IEEE/ACM Transactions on Networking 24 (2016), no. 4, pp. 2114–2127. [4] D. Applegate, A. Archer, V. Gopalakrishnan, S. Lee, and K. K. Ramakrishnan, Optimal Content Placement for a Large-scale VoD System, Proceedings of the 6th International Conference (New York, NY, USA), Co-NEXT ’10, ACM, 2010, pp. 4:1–4:12. [5] S. Bellavia, J. Gondzio and B. Morini, A matrix-free preconditioner for sparse symmetric positive definite systems and least-squares problems, SIAM Journal on Scientific Computing 35 (2013), pp. A192-A211. [6] M. Benzi, Splittings of symmetric matrices and a question of Ortega, Linear Algebra and its Applications 429 (2008), pp. 2340-2343. [7] L. Bergamaschi, J. Gondzio and G. Zilli, Preconditioning indefinite systems in interior point methods for optimization, Computational Optimization and Applications 28 (2004), pp. 149– 171. [8] D. Bienstock, Potential Function Methods for Approximately Solving Linear Programming Problems. Theory and Practice, Kluwer: Boston, 2002. [9] D. Bienstock and O. Raskina, Asymptotic analysis of the flow deviation method for the maximum concurrent flow problem, Mathematical Programming 91 (2002), pp. 479–492. [10] R. E. Bixby, Solving real-world linear programs: a decade and more of progress, Operations Research, 50 (2002), pp. 3–15. [11] S. Bocanegra, J. Castro and A.R.L. Oliveira, Improving an interior-point approach for large block-angular problems by hybrid preconditioners, European Journal of Operational Research 231 (2013), pp. 263–273. [12] J. Castro, A specialized interior-point algorithm for multicommodity network flows, SIAM Journal on Optimization 10 (2000), pp. 852–877. [13] J. Castro, Solving difficult multicommodity problems through a specialized interior-point algorithm, Annals of Operations Research, 124 (2003), pp. 35–48. [14] J. Castro, An interior-point approach for primal block-angular problems, Computational Optimization and Applications 36 (2007), pp. 195–219. [15] J. Castro, Recent advances in optimization techniques for statistical tabular data protection, European Journal of Operational Research 216 (2012), pp. 257-269. [16] J. Castro and J. Cuesta, Quadratic regularizations in an interior-point method for primal block-angular problems, Mathematical Programming 130 (2011), pp. 415–445. [17] J. Castro, Interior Point Methods [Lecture Notes], (2014), pp. 1–36. [18] J. Castro, Primal-dual path-following methods [Lecture Notes], (2014), pp. 1–90. [19] J. Castro, Interior-point solver for convex separable block-angular problems, Optimization Methods and Software 31 (2016), no. 1, pp. 88–109. 47