# Enhanced Routing Algorithm Based on Reinforcement Machine Learning--A Case of VoIP Service
## 2 Theoretical Review
### Reinforcement Learning Routing Protocol (RLRP)  
The RLRP is a reactive routing protocol for multi-hop ad-hoc networks. In general, the purpose of RLRP is to make a decision about the forwarding of packets to neighboring nodes based on estimated values. These values are dynamically updated through the rewards mechanism used by RL. The RLRP works on Linux systems with the TCP/IP stack providing routing for any data packets with either IPv4 or IPv6 addressing [40]. The routing process starts after initializing the routing daemon and runs on a created virtual interface.  
The RLRP as any other conventional protocol for ad-hoc multi-hop networks is based on two operational modes. The first one is path discovery, which occurs when a node needs to send a packet and has no routing information for a destination. The second is packet forwarding, which is when a protocol decides which route is the best to send the packet [40].  
In the first mode, the RLRP uses the reactive approach. Thus, a source node (A) sends a route request (RREQ) message to its direct neighbors and the neighbors in turn relay this RREQ to their neighbors. This manner, the RREQ message is forwarded to all network nodes until the transmission time-to-live (TTL) counter is reached or until a node that has already sent this RREQ receives the message again. All network nodes that participated in the RREQ relay get route information toward the source node and update their routing tables with that information. The destination node (B) receiving RREQ sends a route response message (RREP) that goes through the same relay process. Neighbor nodes of B and all node participating in RREP relay update their routing table with path information to reach node B. When the node A receives the RREP sent by the node B, all network nodes are already aware of the routes between A and B. Thus, the path discovery process ends and packet forwarding mode can be started.  
Conventional routing protocols have in their routing table a field with destination address information. Each route is associated to a cost that is calculated according to an specific metric, then the path which has the lowest cost is selected. In turn, RLRP uses RL to decide which path is the best.  
As explained in the Section 2.1 in RL there is an agent, a set of actions that the agent can do. Each agent's action generates a reward. To this end, there is a set of estimations for the actions. For better association Table 1 introduces a relationship between reinforcement learning and conventional routing protocols.  
The Table 1 shows the relationship between the routing mechanism/tasks and the Reinforcement Learning mechanisms. Through this relationship it is possible to apply the RL to the routing task. Thus, an X node of the network that uses the RLRP protocol can be considered an Agent.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**RL Task** & **Routing Task** \\ \hline Agent & Source node \\ Set of actions & Neighbors set \\ Set of estimation values (Q) & Routing table \\ Agent Action & Send a packet to neighbors \\ Agent receives a reward & Node receives an ACK message \\ \hline \hline \end{tabular}
\end{table}
Table 1: Relationship Between Reinforcement Learning (RL) and Conventional Routing Protocols.  
The set of actions is the set of nodes in the network on which X can send messages. Sending a packet to a given network node is an Agent Action. And when sending this packet, node X expects to receive an Acknowledgment Message (ACK), if this happens it means that the message reached the given node, that is, a reward was generated for having chosen this node to send the message. If the ACK is not received it means that the message has been lost and the route is bad; then, node X receives a punishment for the chosen action.  
Finally, the protocol routing table defines the best route to send a packet to a given destination. Similarly, an estimate set defines which action generates the best reward.