# Interest Forwarding in Named Data Networking Using Reinforcement Learning
## 4 NDN Forwarding with Reinforcement Learning Using the RNN  
We present NDNFS-RLRNN that uses reinforcement learning (RL) with the RNN for the strategy module per prefix in the NDN architecture, which operates with a form of smart Opportunistic Communication [48], supported by a name-based routing protocol with online measurements from the state recorded in the PIT. Our goal is to exploit the convergence properties of the RL with RNN algorithm which have been well studied in [17; 49] algorithm to effectively search for local content store hits. In NDNFS-RLRNN, an RNN is created for a prefix in the FIB and its creation is triggered by a new Interest for the corresponding prefix. In its initial state, the RNN only knows of the routing preferences for its prefix and is yet to be updated by packet delivery measurements. Here, NDNFS-RLRNN's forwarding decision will be to use the best interface according to the routing layer. Each RNN per prefix at the CR has as many neurons as the number \(k\) of outgoing links of the router, and the RNN has \(k^{2}\) weights, and if the router has \(n_{D}\) active destinations, the router will have a total of \(n_{D}\) RNNs to handle each of the destinations, or a total of \(n_{D}\times k^{2}\) entries. A conventional routing table at the NDN router will have \(n_{S}\times n_{D}\times k\) entries for \(n_{S}\) active sources. Thus when \(n_{S}>k\), our scheme uses a smaller data structure per router than a conventional NDN scheme [50]. On the arrival of a Data packet, a reward value is computed for the arrival interface and used to update the RNN as illustrated in Algorithm 1. The goal of our distributed reinforcement learning is to minimise the delay for retrieving contents, so we estimate reward using the RTT values. Let \(T^{j}{}_{I}\) be the time an NDN router forwards an Interest along an interface \(j\) and \(T^{j}{}_{D}\) be the arrival time of the Data packet satisfying the Interest which also arrives on the same interface, we can estimate the reward, \(R^{j}\) as the inverse of the RTT using  
\[R^{j}=(T^{j}{}_{D}-T^{j}{}_{I})^{-1} \tag{6}\]  
For an updated RNN, the forwarding decision of NDNFS-RLRNN is, excluding the arrival interface, with a high probability \(p\) only the interface corresponding to the most excited neuron is used or with probability \((1-p)\) a probing decision is made. We refer to \(p\) as the _probe parameter_. Before explaining the probing process, we first introduce the idea of marking an Interest packet for probing. This means an Interest can be identified at the CRs as either a \"normal\" Interest or a probe Interest. The probing process involves sending two packets: the original Interest which is sent along the best known interface and a copy which is sent as a probe Interest on a randomly selected interface. We impose that a CR only forwards a probe Interest along the best known interface. The motivation for this probing process is to control exploration in order to reduce the possibility of unnecessarily using longer paths to retrieve contents and to manage overhead. In Figure 1 we use a simple flowchart to summarise the Interest forwarding and probing process of NDNFS-RLRNN. We have also adopted the use of Interest NACKS as in the current NDN in our approach. When a CR can neither satisfy nor forward an Interest, it responds using an Interest NACK. Clearly, the reward estimation is explicit when an Interest is satisfied. However, this is not the case when an Interest NACK is returned or when no response is received before the Interest times out. In such cases, the reward can be estimated as:  
\[R^{j}=[c(T-T^{j}{}_{I})]^{-1}, \tag{7}\]  
where \(T\) is the current time and \(c\) is a constant large enough such that a negative reinforcement is applied. Therefore, before deleting a PIT entry, all the interfaces that failed to return data will receive negative reinforcement based on the reward computed in Equation (7).