# Cooperative Buffering Schemes for Time-Shifted Live Streaming of Distributed Appliances
## 3 Cooperative Buffering Schemes for Time-Shifted Live Streaming
### Computational Complexity  
In this subsection, we analyze the computational complexity of our proposed cooperative buffering schemes and present how to reduce it depending on computation loads and capacity of tracker servers. In both \(D\_DP\)- and \(R\_RC\)-based schemes, tracker servers should perform two tasks of determining the time ranges to be buffered when any PVRs start to playback live broadcast and periodically updating the aggregate buffermap information in the system. First, for the task to determine the target time ranges to be buffered, they should evaluate \(DD_{tr_{(i,b)}}\), \(PD_{tr_{(i,b)}}\), \(AR_{tr_{(i,b)}}\), and \(AC_{tr_{(i,b)}}\) per \(p_{i}\) while \(i\) varies from \(1\) to \(TP\). This indicates that the computational complexity of this task is \(O(TP)\), since we assume the tracker servers evaluate them for each period. However, the complexity can be reduced considerably, i.e., to \(O(\frac{TP}{p_{p_{p}}})\) simply by evaluating them every \(b\cdot r_{b}\) periods, not every single period. Note that \(r_{b}\) represents a partial ratio of \(b\). Moreover, if we employ more than one tracker server, the loads on each tracker server can be reduced to \(O(\frac{TP}{p_{p_{p}}N_{t_{b}}})\) where \(N_{t_{b}}\) represents the number of tracker servers in the system. Second, the tracker servers should also update the aggregate buffermap information in the system reflecting the current buffering status of all PVRs. The information is used to evaluate the criteria for determining the time ranges to be buffered in both \(D\_DP\) and \(R\_RC\)-based schemes. The computational complexity of this task is \(O(b)\) since \(b\) chunksare updated in the aggregate buffermap each time the track server receives one buffermap from PVRs. However, this complexity can be also reduced to \(O(\frac{b}{g})\) simply by making each period consist of a group of \(g\) chunks, not one chunk. We can further reduce the complexity by decreasing the total number of update operations per second. Let \(N_{p}\), \(a_{p}\), \(\lambda_{b}\), and \(I_{u}\) denote the total number of PVRs in the system, the availability of each PVR, the number of buffermap transmissions per PVR per second, and the aggregate buffermap update interval in multiples of \(\lambda_{b}\) in a tracker server, respectively. We can evaluate the average number of participating PVRs at a specific time by multiplying \(N_{p}\) by \(a_{p}\). Since the tracker server receives buffermaps at a rate of \(\lambda_{b}\) per PVR per second, the total number of buffermaps received from all participating PVRs for one second is \(\lambda_{b}\cdot N_{p}\cdot a_{p}\). To alleviate the loads for the tracker server to perform the aggregate buffermap update operations, it may not perform the operations each time it receives one buffermap. In addition, the loads can be distributed on more than one tracker server. We can eventually reduce the number of the update operations performed by one tracker server for one second to \(\frac{\lambda_{b}\cdot N_{p}\cdot a_{p}}{I_{u}\cdot N_{bs}}\). To support our time-shifted live streaming services in real time, we determine the number of tracker servers adaptively, depending on the request arrival rate in the system (\(\lambda_{a}\)) and the request service rate of each tracker server (\(\mu_{ts}\)). To accommodate all the requests without quality disruption, the number of tracker servers (\(N_{ts}\)) should be at least \(\lceil\frac{\lambda_{b}}{\mu_{ts}}\rceil\). Thus, our buffering schemes employ additional tracker servers or restrict the number of requests to be admitted as \(\lambda_{a}\) increases. Note that \(\mu_{ts}\) can be obtained by investigating the maximum number of requests being served while the average playback continuity of all the requests is over a predetermined percentage.