A routing algorithm is a method used to determine the routing of packets among nodes. For each node in the network, the algorithm determines a routing table that matches the outgoing line at each destination. This algorithm should result in consistent routing, that is, no loops. This means that you should not route packets from one node to another node that can send packets back.
Definition: The process of establishing a route by following packets to their destination. It is a set of step-by-step processes used to efficiently direct traffic on the Internet. Once a packet leaves its source, several paths are available to its destination. This algorithm mainly determines the best lane mathematically.
There are different methods used in different routing algorithms to decide the best lane. For example, the distance vector algorithm analyzes the graph of all accessible routes through each node to determine the cost of travel for each immediate neighbor. This data can be collected for each node to generate a distance table to determine the best lane between any two nodes. In this approach, routing tables can be created to enter information about the routes that packets follow.
In the OSI model (Open Systems Interconnection), routing can exist above the network layer. This is the third layer in the OSI model. Therefore, it determines the best channel on the network to transport packets from source to destination.
What are the types of routing algorithms
There are three main types of routing algorithms:
distancevector(distancevectorrouting);
to link-state(link-state routing);
Path-to-vector (path-vector routing).
Distance Vector Routing Algorithm
The distance vector routing algorithm requires each node to exchange information between its neighbors, that is, directly connected nodes. Therefore, each node can keep the table updated by adding information about all its neighbors. This table shows the distance of each node and each network to be reached. What was first implemented in Arpanet is that when the number of nodes increases, this technology quickly becomes cumbersome because we have to carry a lot of information between nodes. RIP (Routing Information Protocol) is the best example of a protocol that uses distance vectors.
In this type of algorithm, each router broadcasts to its neighbors a vector that lists the relevant metric, or hop count, for each network it can reach. Therefore, each router can build a routing table using information received from its neighbors, but does not know the identity of the router on the selected route. Therefore, the use of this solution creates many problems for external routing protocols. In fact, it is assumed that all routers use the same metric, which may not be the case between autonomous systems. Furthermore, one autonomous system may have special reasons to behave differently from another autonomous system. In particular, if the autonomous system needs to determine how the autonomous system will deliver its messages, for example for security reasons, he does not know.
Link state algorithm
Link state algorithms were originally designed to overcome the shortcomings of distance vector routing. When a router is initialized, it must define the cost of each link connected to another node. The node then broadcasts the information to all nodes in the autonomous system and therefore not only to its neighbors. Based on all this information, nodes can perform their calculations to obtain a routing table indicating the cost of achieving each destination. When a router receives information that changes its routing table, it notifies all intervening routers in its configuration. Since each node has a network topology and a cost for each link, routing can be considered as the center of each node. This technology is implemented by OSPF (Open Shortest Path First), which is the second generation Internet protocol.
Link-state algorithms solve the external routing problem described above, but also raise other issues. Various autonomous systems may have different metrics and specific constraints, making a consistent route impossible. The dissemination of all information required by all autonomous systems can also quickly become unmanageable.
Path Vector Algorithm
The purpose of path vector algorithms is to overcome the shortcomings of the first two categories of algorithms by providing a metric and seeking to know which network can be reached by any node and autonomous system that must be crossed. This approach is very different from distance vectors because path vectors do not take distance or cost into account. Additionally, given the fact that each list routing information is an autonomous system that must be traversed to reach the destination router, the path vector approach favors external routing systems. BGP (Border Gateway Protocol) falls into this category.
OSPF (Open Shortest Path First)
Open Shortest Path First (OSPF) is a link state routing protocol developed for IP networks and is based on the Shortest Path First (SPF) algorithm. OSPF is an Interior Gateway Protocol (IGP).
In an OSPF network, routers or systems in the same area maintain the same link state database that describes the topology of the area. Each router or system in the area generates its link state database based on the link state advertisements (LSAs) it receives from all other routers or systems in the same area, as well as the LSAs it generates itself. LSAs are packets containing information about neighbors and path costs. Based on the link state database, each router or system uses the SPF algorithm to calculate a shortest path spanning tree rooted at itself.
OSPF is part of the second generation routing protocol. It is much more complex than RIP, but has higher performance, and it uses a distributed database that tracks link status. This information forms a description of the network topology and node status, and defines the routing algorithm by calculating the shortest path.
This algorithm allows OSPF to calculate the shortest path from a node and specify constraints in relation to each link. OSPF routers communicate with each other through the OSPF protocol that sits on top of IP. Now let’s look at the details of this agreement.
The assumption of the link-state protocol is that each node can detect the link status (up or down) with its neighbors and the cost of that link. We must give each node enough information to enable him to find the cheapest route to any destination. Each node must know its neighbors. If each node knows about other nodes, a complete network map can be built. Neighbor state-based algorithms require two mechanisms: propagation of reliable information about link states, and calculation of routes by summing accumulated knowledge of link states.
One solution is to provide a reliable torrent of information to ensure that each node receives a copy of its information from all other nodes. In fact, each node floods its neighbors, who in turn flood their neighbors. Specifically, each node creates its own update packet, called an LSP (Link State Packet), containing the following information:
The ID of the node where the LSP is created.
A list of neighboring nodes with associated link costs.
serial number.
The timer (time to live) for this message.
Route calculation is performed after receiving all information about the link. Based on the complete network map and link costs, the optimal route can be calculated. Calculation is performed using Dijkstra’s algorithm on the shortest path.
In the abbreviation OSPF (Open Shortest Path First) Open, the word means that the algorithm is open and supported by the IETF. Using the above mechanism, the OSPF protocol adds the following additional properties:
-
Authentication for routing messages. Failure can lead to disaster. For example, after receiving an error message intentionally or unintentionally, or after a forward message modifies its routing table, a node that calculates a routing table automatically receives all network packets in which all nodes can route it at zero cost. accomplish. These problems can be avoided by validating the issuer of the message. Earlier versions of OSPF authentication passwords were 8 bytes. The latest version has stronger authentication capabilities.
-
New hierarchy. This hierarchy allows for better scalability. OSPF introduces another hierarchy by dividing areas into eras (areas). This means that the routers within the domain do not need to know how to reach all the networks on site. It’s just that he knows how to reach the right age. This results in less information to be transmitted and stored.
There are several types of OSPF messages, but they all use the same header, as shown in the figure.
The current version is 2. Five types are defined with values – from 1 to 5. The source address represents the sender of the email. The identifier of the era indicates the era in which the sending node is located. The value of the authentication type is 0 if there is no authentication, 1 if the authentication password is used, or 2 if the authentication technology is implemented and described in the following 4 bytes.
These five types of messages regard the Hello message as Type 1.
This message is sent by a node to its neighbors to tell them that it is always present and uncorrupted. The other four types are used to send information such as inquiry, shipment or acquittal LSP messages. These messages mainly carry link status advertisements (LSA), that is, link status information. A message can contain multiple OSPF LSAs.
The figure shows an OSPF LSA type carrying message 1.
OSPF link state (LS) routing algorithm (C/C++ code implementation)
Implements the OSPF link state (LS) routing algorithm for a given set of nodes (routers). Nodes are represented by lowercase letters (a-z). Then, when given a source node, the project outputs the shortest path cost and path for each node. Therefore, the program will ask for the number of routers in the network, the letter representing the first node, and the letter of the source node. Nodes other than the first node are represented by consecutive letters of the alphabet. For example, if there are 5 routers and the first node is d, then the second, third, fourth, and fifth routers will be represented by the letters e, f, g, and h respectively. The program will also ask for a cost matrix containing the cost of each link between nodes. The cost of each link is a positive value greater than 1. If 0 exists in the cost matrix, it means that the cost of reaching that node for the same node is zero. If there is -1 in the cost matrix, it means there is no direct path between two nodes. The LS algorithm utilizes Dijkstra’s algorithm to find the shortest path between nodes. It also maintains a simple routing table to store this information. An example of a cost matrix is given below.
...
int main(int argc, char *argv[])
{<!-- -->
...
//Displaying cost matrix
Display_Cost_Matrix(cost_matrix, number_of_routers, first_node_character); //Calling Display_Cost_Matrix() function to display the cost matrix
//Displaying cost matrix
...
//Initializing for Dijkstra algorithm
starting_node = source_node - first_node_character + 1; ///Determining the starting node for the algorithm
for(i = 1; i <= number_of_routers; i + + ) //Initializig flags for all nodes
if(i == starting_node)
node_flag[i] = 1;
else
node_flag[i] = 0;
for(i = 0; i <= number_of_routers; i + + ) //Initializing link state table
{<!-- -->
for(j = 1; j <= number_of_routers; j + + )
link_state_table[i][j] = -1;
}
//Initializing for Dijkstra algorithm
...
//Dijkstra algorithm starting...
...
while(1)
{<!-- -->
for(j = 1; j <= number_of_routers; j + + )
{<!-- -->
if(!node_flag[j])
{<!-- -->
if(cost_matrix[previous_node][j] != -1)
{<!-- -->
if(link_state_table[i-1][j] > 0 & amp; & amp; link_state_table[i-1][j] < cost_matrix[previous_node][j] + previous_cost)
{<!-- -->
link_state_table[i][j] = link_state_table[i-1][j];
tracker[i][j].node_from = tracker[i-1][j].node_from;
tracker[i][j].i_from = i - 1;
tracker[i][j].j_from = j;
}
else
{<!-- -->
link_state_table[i][j] = cost_matrix[previous_node][j] + previous_cost;
tracker[i][j].node_from = first_node_character + previous_node - 1;
tracker[i][j].i_from = i - 1;
tracker[i][j].j_from = previous_node;
}
}
else if(link_state_table[i-1][j] > 0)
{<!-- -->
link_state_table[i][j] = link_state_table[i-1][j];
tracker[i][j].node_from = tracker[i-1][j].node_from;
tracker[i][j].i_from = i - 1;
tracker[i][j].j_from = j;
}
}
}
...
for(j = 1; j <= number_of_routers; j + + )
{<!-- -->
if(link_state_table[i][j] != -1)
{<!-- -->
previous_cost = link_state_table[i][j];
previous_node = j;
break;
}
}
for(j = 1; j <= number_of_routers; j + + ) ///Finding out minimum cost and node number for current node
{<!-- -->
if(link_state_table[i][j] != -1)
{<!-- -->
if(link_state_table[i][j] <= previous_cost)
{<!-- -->
previous_cost = link_state_table[i][j];
previous_node = j;
}
}
}
node_flag[previous_node] = 1;
i + + ;
}
step_number = i;
for(i = 1; i <= number_of_routers; i + + ) each iteration
{<!-- -->
path_cost[i] = 0;
k = 0;
if(i != starting_node)
{<!-- -->
path_taken[i][k] = first_node_character + i - 1;
k++;
for(j = 1; j <= step_number; j + + )
{<!-- -->
if(!path_cost[i] & amp; & amp; link_state_table[j][i] != -1)
{<!-- -->
path_cost[i] = link_state_table[j][i];
current_i = j;
current_j = i;
path_taken[i][k] = tracker[current_i][current_j].node_from;
}
else if(path_cost[i] & amp; & amp; link_state_table[j][i] != -1 & amp; & amp; link_state_table[j][i] < path_cost[i])
{<!-- -->
path_cost[i] = link_state_table[j][i]; cost
current_i = j;
current_j = i;
path_taken[i][k] = tracker[current_i][current_j].node_from;
}
}
k++;
while(current_i & amp; & amp; current_j)
{<!-- -->
if(path_taken[i][k-1] != tracker[current_i][current_j].node_from)
{<!-- -->
path_taken[i][k] = tracker[current_i][current_j].node_from;
k++;
}
temp_i = current_i;
temp_j = current_j;
current_i = tracker[temp_i][temp_j].i_from;
current_j = tracker[temp_i][temp_j].j_from;
}
}
else
{<!-- -->
path_taken[i][k] = source_node;
k++;
}
path_taken[i][k] = '\0';
}
///Dijkstra algorithm ending...
...
return 0;
}
operation result:
If you need the complete source code, please add the WeChat number (c17865354792)
Implements the OSPF link state (LS) routing algorithm for a given set of nodes (routers).
Summary
Routing algorithms are mainly used to improve network quality. By using this algorithm, the best route for the network can be determined. This algorithm is suitable for specific protocols. Different algorithmic methods can be used to calculate routes. Depending on the type of network and its application, each algorithm can be applied. The algorithm has many properties such as stability, correctness, efficiency, simplicity, fairness and robustness.
Routing algorithms play an important role in connecting different systems to communicate over a network. The main responsibility of a router is to identify each device, its structure, presence and transmit data packets. By using these algorithms, data can be transferred over the network in seconds, data can be transferred securely, and the quality of the data can be maintained.
Welcome to follow WeChat official account【Programmer Coding】
Reference: RFC 2328, RFC6549, RFC5709