# Request Expectation Index Based Cache Replacement Algorithm for Streaming Content Delivery over ICN
## 3 Request Expectation Index Based Cache Replacement Algorithm
### Request Expectation Index \(Rxi(i,j)\)
#### 3.1.3. Chunk-Level Internal Request Expectation Index \(IRXI_{f_{i}}(j)\)  
Since we assume that users will request the streaming chunks according to the sequence number, the subsequent chunks will have a relatively high probability of being requested in the following time interval. For instance, if an ICN router receives a request for chunk \(C_{2,4}\), the subsequent chunks, such as \(C_{2,5}\) and \(C_{2,6}\), are likely to be requested later. Therefore, if any of these subsequent chunks have already been cached, they will have higher access probability. \(IRXI_{f_{i}}(j)\) is estimated according to the chunk-level internal probability \(P_{f_{i}}(j)\) and the current request status of file \(f_{i}\) at this router. We record \(IRXI_{f_{i}}(j)\) for every cached chunk in the ICN router and _Update/Recover_ it promptly. When a chunk is initially cached, the \(IRXI_{f_{i}}(j)\) of the chunk is equal to the \(P_{f_{i}}(j)\), as shown in Equation (5):  
\[IRXI_{f_{i}}(j)=P_{f_{i}}(j). \tag{5}\]  
\(IRXI_{f_{i}}(j)\) is updated when the ICN router receives additional requests for the same streaming file \(f_{i}\). According to the linear request feature of streaming content delivery, a received request implies that some cached subsequent chunks will likely be requested in the future; thus, the \(IRXI_{f_{i}}(j)\) of the cached chunks is updated under the following constraints:  
1. \(C_{i,j}\) has been cached in the cache space of the ICN router. 2. \(IRXI_{f_{i}}(j)\) updating only occurs when this ICN router receives a request for chunk \(C_{i,g}\) of the same file \(f_{i}\). 3. The sequence numbers \(j\) of the cached chunks are larger than the sequence number of the received request, i.e., \(j>g\). The \(IRXI_{f_{i}}(j)\) value is updated on the basis of the \(P_{f_{i}}(j)\) gap between the just-received request \(C_{i,g}\) and the first chunk of file \(f_{i}\), as shown in Equation (6):  
\[IRXI_{f_{i}}(j) =P_{f_{i}}(j)+\Delta\mu,\;\;\;j>g, \tag{6}\] \[\textit{where}\;\;\;\;\Delta\mu =P_{f_{i}}(1)-P_{f_{i}}(g).\]  
\(\Delta\mu\) is calculated according to the following considerations. First of all, if there are no new users requesting file \(f_{i}\), the chunk \(C_{i,g}\) having just been requested refers to the next subsequent chunk \(C_{i,g+1}\) temporarily having the highest internal request probability. Because those chunks whose sequence number are less than or equal to \(g\) will never be requested again by the same user. Therefore, we increase \(IRXI_{f_{i}}(g+1)\) by \(P_{f_{i}}(1)-P_{f_{i}}(g)\) so that \(IRXI_{f_{i}}(g+1)\) is the highest one currently. Secondly, the \(IRXI_{f_{i}}(j)\) of the cached subsequent chunks will be added the same value \(\Delta\mu\) so that the same request probability tendency remains compared with the chunk-level internal request probability \(P_{f_{i}}(j)\). Finally, if there is a new user request for file \(f_{i}\), which refers to the first chunk \(C_{i,1}\) being requested, according to Equation (6), the \(IRXI_{f_{i}}(j)\) of chunks in file \(f_{i}\) will return back to the initial value and equal to \(P_{f_{i}}(j)\). When a request for \(C_{i,g}\) is received, the subsequent chunks of file \(f_{i}\) will likely be requested later. Therefore, the \(IRXI_{f_{i}}(j)\) of the subsequent chunks is temporarily increased by \(\Delta\mu\), that is, if any of these chunks are cached in the router, they will have high probability of being requested soon and should not be easily replaced by the cache replacement algorithm, as shown in Figure 4.  
The temporarily increased \(IRXI_{f_{i}}(j)\) of the subsequent chunks should be recovered to \(P_{f_{i}}(j)\) after being requested, and, based on Equations (5) and (6), the calculation of \(IRXI_{f_{i}}(j)\) is summarized in Equation (7). \[IRXI_{f_{i}}(j)=\left\{ \begin{aligned} & P_{f_{i}}(j),& C_{i,j} \text{ is initially cached;}\\ & P_{f_{i}}(j)+\Delta\mu,& C_{i,g}\text{ is requested, }(j>g);\\ & P_{f_{i}}(j),& C_{i,j}\text{ is requested.} \end{aligned} \right. \tag{7}\]  
The Update/Recover procedure is presented in Algorithm 1.