# Minimizing the Number of Distrustful Nodes on the Path of IP Packet Transmission
## 2 Materials and Methods  
### Statement of Research  
One of the most common routing protocols used in the Internet Autonomous System is the OSPF protocol, described in [1]. Most router manufacturers support this protocol. The protocol is based on the link state analysis algorithm. Link state analysis algorithms provide each router with enough information to construct a network's link graph. All routers work based on the same graphs, which makes the routing process stable. Routers periodically exchange short service packets with their nearest neighbor routers. This traffic is broadcast, but it circulates only between neighbors and, therefore, clogs the network slightly. The OSPF protocol is based on the shortest path tree search algorithm. The set of shortest paths from a certain node to all known remote networks is the shortest path tree for this node. For each node of the Autonomous System, it is necessary to find a tree of shortest paths; [PERSON]'s algorithm is used to build them. Routing tables are formed based on the tree of the shortest paths. Routing tables are stored in the memory of routers and are used to select the next node (router) on the path of the packet to the destination. This node is called Gate Way (GW). Each intermediate router, after receiving a packet to be forwarded to a remote addressee, finds, in the routing table, the address of the next GW on the transmission path. The OSPF protocol ensures the transmission of packets along the shortest paths calculated, according to a certain single criterion. Channel capacity, the number of steps to the goal, packet delivery delay, the number of datagrams in the queue for transmission, channel loading, security requirements, and others can be used as this criterion. One of the typical criteria for finding the tree of shortest paths is the number of transitive nodes on the path between the source node and the destination node, called hops. Our work will also be based on this criterion. However, there are cases when not one criterion but two or more are important for choosing paths. Accordingly, there are recommendations for the simultaneous consideration of several criteria and their various combinations. Sometimes it is important to take into account not only the values of the metrics of various criteria, but also the ratio between them. For example, in studies [5; 9], the indicators of three criteria (throughput, hops, and delay) and their weight are taken into account. This task differs from the previous ones, considering one criterion, but, at the same time, an additional condition will be formulated. All nodes will be divided into two classes--trustful and distrustful--and the modified algorithm should minimize the number of untrusted nodes in the tree of shortest paths. A weighted graph corresponding to the network topology is used as the input data for [PERSON]'s algorithm. The algorithm treats each router as a node of the graph, each channel as its edge, and the weight of the edge as the value of the channel metric, a parameter used to estimate its cost. [PERSON]'s algorithm finds the shortest path tree from the source node (the root of the graph) to each destination node. The total cost of each path is calculated as the sum of the weights of the individual channels included in it. The path whose total cost is minimal is chosen for the transmission of packets. The subject of this research is the methods used to obtain the shortest path tree for construction routers' routing table in the networks with one or more distrustful nodes. To begin, we will formulate two requirements that must be provided using the modification of [PERSON]'s algorithm, as follows:  
1. It is necessary that the algorithm builds paths to bypass distrustful nodes, and the weight of the bypass path should be as minimal as possible;
2. If it is impossible to find a detour of distrustful nodes, the proposed route must pass through a minimum number of distrustful nodes. First, consider the problem of bypassing distrustful nodes.