# Improving End-To-End Latency Fairness Using a Reinforcement-Learning-Based Network Scheduler
## 2 Materials and Methods
### Scheduler Using Metadata  
It is difficult to compare the performance of existing schedulers that increase latency fairness because they have different problems to solve. For example, in the case of PPLR [8], the maximum E2E latency cannot be fixed because it is probability-based transmission, and in HBMQ [22], it is difficult to see a difference in performance from RR because nodes in the assumed environment consist of queues for each input port. Largest delay first (LDF) [16] determines the service order by finding the sum of the queuing delays of all packets in the queue at the node without using the number of hops information. Unlike PPLR [8], less probability is applied and the method is robust against starvation because the queue to be served is determined using latency information. However, since the number of hops information is not used, packets passing through different routes cannot be serviced. In addition, since the node calculates and uses the queuing delay, it does not have information on the delay time that the packet experienced before, and thus its performance deteriorates in a multi-hop environment. For comparison with the RL-based scheduler, we propose two heuristic algorithms that can achieve the minimization of maximum E2E latency. The first heuristic algorithm is a network-arrival-time-based heuristic algorithm (NAT-HA). Algorithm 2 explains the operation of NAT-HA. NAT in Algorithm 2 stands for network arrival time. By recording the network arrival time in the packet as metadata, the queue with the smallest network arrival time of the head of the queue (HoQ) is serviced. If the network arrival time of the HoQ is the same, service is provided randomly among these queues. The network arrival time indicates the time spent in the network. Since the E2E latency increases as much as the time spent in the network, the packet that has stayed in the network for a long time, that is, the packet that entered the network first, is served first to reduce the maximum E2E latency in a single network. NAT-HA has the same performance as FIFO in a single-node network. Even in a network with multiple nodes, the operation of the ingress node is the same as that of FIFO. Therefore, the worst-case performance of NAT-HA is the same as the worst-case performance of FIFO. In terms of average performance, NAT-HA shows better performance than FIFO because it can provide services in the direction of reducing E2E latency in the core node. NAT-HA is similar to LDF in that it records the queuing delay in packets as metadata. The difference lies in the method used to estimate the delay time. NAT-HA estimates the delay time up to the present using the packet creation time, whereas LDF continuously adds queuing delay at the node. The delay time that the packet has experienced so far calculated by the node differs depending on the path of the packet, allowing for the reflection of the difference based on the number of hops. However, not all nodes can know this information, so a heuristic algorithm that uses the number of hops along with the delay time is also required. ```
M = number of the input port Queue[1..M]  min_NAT = Inf idx = 0 while true for i in 1..M: if Queue[i] is not empty if min_NAT > Queue[i].head.NAT idx = i min_NAT = Queue[i].head.NAT send(Queue[idx].head) Queue[idx].dequeue
```  
**Algorithm 2** NAT-HA in the output port module. The second heuristic algorithm is a scheduling algorithm that uses the estimated delay in the same way as the RL-based scheduler. The metadata also uses the remaining hop countand packet-generated time in the same way. This algorithm calculates the estimated delay of all packets in the queue and serves the queue containing the packet with the maximum estimated delay. This is called the maximum-estimated-delay-based heuristic algorithm (MED-HA). The method for obtaining estimated delay and maximum estimated delay in MED-HA is described in Algorithm 3. If there are several packets with the maximum estimated delay, the queue is serviced randomly among the queues with them.