Video on Demand (VoD) Network/Compute Optimization Formulation

In Figure 1, we show a number of data centers used to serve clients located in a number of end user regions. For concreteness, suppose that the data centers are serving video on demand (VoD) streaming services to client regions.

Figure 1. General Video on Demand network.

Suppose we had S data centers, \(D{C_s}\), and that each can stream a maximum quantity \({Q_s}\) of video. We have R users regions,\({U_r}\), that have demands \({D_r}\) for video that must be satisfied. Each \(D{C_s}\) has a cost of \(c{d_s}\) to stream a unit of video \(Q\). In addition, the communication of video from to across the network is subject to network costs and capacity constraints. Let \({q_{sr}}\) be the total bandwidth of video produced at \(D{C_s}\) for \({U_r}\). The objective is to minimize the total cost (data center and network): \[\begin{equation}\sum\limits_s {c{d_s}{q_s}} + \sum\limits_{s,r} {networkCost({q_{sr}})} \end{equation}\] Subject to the network capacity constraints as well as: Data center capacity constraints: \[\begin{equation}\sum\limits_r {{q_{sr}}} \le {Q_s}\quad \forall s \end{equation}\] And user demands: \[\begin{equation}\sum\limits_s {{q_{sr}}} = {d_r}\quad \forall r \end{equation}\]

To fully specify this network/compute optimization problem we need to include the network costs and constraints from one of our two different multi-commodity flow formulations.

VoD Network/Compute Optimization Example.

In Figure 2 we show a simple example network for our VoD optimization. The user regions are denoted by R0-R3, and the data centers by DC0-DC2. The demands for the user regions, the cost and capacities of the data centers, and the link costs and capacities are embedded in the JSON representation of the network and can be viewed by clicking the following button: and then looking at the node and link tabs within the dialog that is shown.

In this example we combined the above formulation with our multi-commodity flow arbitrary paths formulation. This resulted in an optimization problem consisting of 1320 variables and 1774 constraints. The time to solve this on my laptop with an open source solver an no other optimization was 0.819 seconds of which 0.766 seconds were used to load the data (0.053 seconds of number crunching). The optimal pairings between data centers and user regions along with the corresponding "optimal" paths are shown in the information dialog. Click a path (or control click multiple paths) to see them displayed on the network graph.

Figure 2. Example VoD network for optimization. Link, node, and path info