# Minimizing the In-Cloud Bandwidth for On-Demand Reactive and Proactive Streaming Applications
## 4 Optimizing Cloud-Based Streaming Internal Bandwidth: Case of Popular Video
### Linear Program Formulation for a Fixed Time Horizon  
Let \(C\) be the fixed broadcasting time horizon and \(N\) be the total number of equally sized segments of the media. Generally, \(C\) is equal to \(n*N\) with (\(n>1\)). Let \(x_{ij}\) be a Boolean variable indicating whether or not segment \(i\) can be scheduled within time slot \(j\) (\(x_{ij}=1\)) (\(x_{ij}=0\)) and \(B\) be the total number of broadcasting network channels, which is the total consumed bandwidth (expressed in number of channels) used by NOPP.  
Our Linear Program (LP) can be stated as follows:  
\[\text{Minimize }B \tag{29}\] \[\text{Subject to }:\] \[\sum_{j=1}^{N}x_{jt}\leq B,t\in\{1,2,\ldots,C\}\] (30) \[\sum_{k=t}^{t+j-1}x_{jk}\geq 1,j\in\{1,2,\ldots,N\}\] \[\text{and }t\in\{1,2,\ldots,C-j+1\}\] (31) \[\sum_{i=1}^{N}\frac{1}{i}\leq B\leq N\] (32) \[x_{j,t}\in\{0,1\},j\in\{1,2,\ldots,N\}\] \[\text{and }t\in\{1,2,\ldots,C\}\] (33) \[B\in\mathbb{N}^{*} \tag{34}\]  
Constraint (30) means that the number of scheduled segments for any time slot cannot exceed the total number of channels. Constraint (31) means that each segment \(i\) must be scheduled at least once for any time window of size \(i\) slots. The lower bound used in constraint (32) has been determined in [18,50].  
Solving the LP using the Gurobi solver [53] for \(N=C,N\in\{2,3,\ldots,50\}\) gives the results summarized in Table 2. Note that the solver was installed on a 16 processors Linux workstation with 2.4 GHz speed each.  
The main drawback with fixed time horizon scheduling is the obligation to stop serving SN requests before a period of time equal to the size of a video instance (only the SN arriving within \(C\)-\(N\) are served). Indeed, the requests coming during the streaming time of the last instance of the video will not be able to download the entire segments. As shown in Figure 8, a request coming during the third time slot will miss segment 10. An additional time slot is therefore needed to schedule it (segment 10). We need to add an increasing number of time slots to schedule as many missed segments as we have new requests during this last instance of the media.  
Figure 8: An example of an optimal scheduling for \(N=C=10\) and \(B^{*}=3\). The request arrival slot is illustrated in black. The green video segments are successfully downloaded. The red video segment is missed.  
Unfortunately, this is not obvious, as the repetition of the same optimal schedule does not guarantee a feasible schedule.  
As we can see in Figure 9, the distance between two successive occurrences of each of the segments 6, 7, 8 and 9 is equal to 10 (one occurrence is counted in the distance), which violates the playback property where segment \(i\) must be scheduled at least once in any \(i\) successive slots. As portrayed in the figure, only 3 segments among 4 could be scheduled in the free places (in green), which means that the obtained scheduling is not feasible.  
To overcome this problem, we propose in the next subsection a new LP model that allows us to obtain an optimal schedule that could be repeated as many times as we have new requests without violating the playback propriety.