# An On-Demand Fault-Tolerant Routing Strategy for Secure Key Distribution Network
## 4 Proposed Solution
### Path Discovery  
The process is mainly divided into two phases: route request and route response. At least one path (if any) free of faulty nodes is found by flooding routing packets.  
Each node will maintain a routing table, in which each table entry contains the following fields: destination address, egress port, relay list, and entry status. When the routing table entry for the destination is located is unavailable, it enters the route request phase.  
Figure 4: Overview of the proposed solution.  
The SKD node generates and broadcasts the route request message. the message has an incremented request sequence number and is signed by the source, so other nodes can identify the request. To ensure the privacy of routing messages, the messages need to be encrypted with a local key before broadcasting. Each relay will maintain a list that stores recent routing requests. As shown in Figure 5, if the received request message does not match, it will be broadcast to other ports, thereby reducing the overhead of routing messages and the consumption of local keys.  
When the route request message arrives at the destination, it enters the routing response phase. If the current request has not been processed, a routing response message containing the incremented response sequence number is broadcast. As shown in Figure 6, when the response list maintained by the relay cannot match, or it matches but the link status calculated based on the packet is better than the record in the table, the cumulative link status in the table is updated. Add the link status at the entrance of this node to the link status list in the packet, sign it, encrypt it, and forward it to other ports. If the source does not receive the route response message within a certain period, it simply resends the route request message. If there is at least one path between the source and the destination, the algorithm can discover the path and ensure the reachability of the route.  
If the path priority is measured by accumulating link status when propagating routing response messages, a path that cannot provide local key services may be selected. As shown in Figure 7, if A triggers path discovery, this mechanism will cause the network layer to select paths containing A, B, and C. The key supply capability of the logical link between B and C is poor, and the key transmission failure is more likely. We comprehensively consider the local key status and hop number of the link of the current message as the path status, and the larger one is selected:  
\[P=\operatorname*{arg\,max}_{i}\left(\frac{\min\left(S_{i0},S_{i1},\ldots,S_{ iH_{i}}\right)}{H_{i}}\right) \tag{2}\]  
Figure 5: Route request phase.  
Figure 6: Route response phase.  
where \(P\) represents the selected path sequence number and \(H_{i}\) represents the number of hops of path \(i\). The link status \(S\) in the formula is defined as:  
\[S=\left(\frac{K_{cur}}{K_{max}}\right)*K_{gen} \tag{3}\]  
The first factor weight represents the status of the key cache. \(K_{cur}\) and \(K_{max}\) here represent the amount of currently cached local key and storage limit, respectively. The second factor \(K_{gen}\) is the absolute net key generation rate of the current logical link. If the first factor is small, it implies that a significant number of communication keys have passed through the node in the past period, which requires time to recover. If \(K_{cur}\) is 0, it means that the current logical link cannot provide services.