Routing Algorithm in Computer Networks
The Network Layer: Determining the Path
In computer networks, the network layer plays a crucial role in determining the path for a packet to be transmitted from the sender to the receiver. This process is known as routing. Routing is performed by network routers, which are strategically placed in the path to better determine the datagram (i.e., routing).
Default Gateway
A host is usually connected directly to a router, which serves as the default router for the host, also known as the default gateway. Whenever a host sends a packet to an external network, the packet is transmitted to its default gateway. The default gateway of the source host is called the source router, while the default gateway of the destination host is called the destination router.
Routing Problem
The issue of routing a packet from the source to the destination hosts is attributed to the routing problem, which involves finding the best path from the source router to the destination router. The target routing algorithm is simple: given a set of routers and links connecting the routers, the algorithm finds the best path from the source router to the destination router, usually the path with the lowest cost.
Graph Representation
FIG. G = (N, E) represents a set of N nodes and E edges, where each edge is a pair of nodes. In the routing network environment, the router nodes make packet forwarding decisions, while the connection nodes represent physical links between the routers. Each edge has a value expressing its cost. Typically, an edge cost reflects physical length, speed, or link costs associated with the link.
Cost Representation
For each edge E (xy), the cost between nodes x and y is represented by c (xy). Since the graph is undirected, the edge (xy) and the edge (yx) are the same and have equal cost. A neighbor node of x is also called node x.
Target Routing Algorithm
The natural target routing algorithm is to find the lowest cost path from the source to the destination. A path (Path) in FIG. G = (N, E) is a sequence of nodes such that each pair (x1, x2), (x2, x3), …, E is the edge. The path cost is the sum of all the edges along the path cost.
Classification of Routing Algorithms
We can classify routing algorithms based on whether they are global or distributed. The global routing algorithms:
- Calculate the lowest cost path from the source to the destination using complete, global information.
- Have a global state information, often referred to as link-state LS algorithm, because the algorithm must know the cost of each link in the network.
Distributed Routing Algorithms
Distributed routing algorithms:
- Calculate the lowest cost path using iterative, distributed methods.
- Exchange information with neighboring nodes to gradually calculate the lowest cost route.
Distance-Vector (DV) Algorithm
The DV algorithm is a distributed routing algorithm, where each node maintains the cost of all other nodes (distance vector network). The DV algorithm is an iterative algorithm for asynchronous, and distributed.
Bellman-Ford Equation
The Bellman-Ford equation is:
dx (y) = min {c (x, v) + dv (y)}
This equation means that the lowest cost path from node x to node y is the minimum cost of all neighbors of x, plus the cost of the destination node y.
Comparison of LS and DV Algorithms
The LS and DV algorithms use different methods to calculate the routing problem. The LS algorithm:
- Requires each node to know the cost of each link in the network, resulting in O (nE) messages.
- Converges quickly and does not suffer from routing loops.
- Is robust and does not spread incorrect information.
The DV algorithm:
- Converges slowly and may suffer from routing loops.
- May result in the count to infinity problem.
- Is not as robust as the LS algorithm.
Level Routing
Level routing policies are implemented through the router into AS (Autonomous System) to be implemented. Each router is typically part of a set of AS under the administrative control of the same composition (e.g., by the same operator or belong to the same ISP network company). Routers within the same AS run the same routing algorithm, while routers at the edge of the AS are responsible for forwarding packets to a destination outside the AS.
Autonomous System Routing Protocol
The routing algorithm running within an autonomous system is called the autonomous system internal routing protocol. This protocol is used to determine the best path for packets to be transmitted within the autonomous system.
Gateway Router
A gateway router is responsible for forwarding packets to a destination outside the autonomous system. This router is typically located at the edge of the autonomous system.
Comparison of LS, DV, and Level Routing Algorithms
The LS, DV, and level routing algorithms have different characteristics:
- LS algorithm: requires complete, global information, converges quickly, and is robust.
- DV algorithm: converges slowly, may suffer from routing loops, and is not as robust as the LS algorithm.
- Level routing: implemented through the router into AS, each router runs the same routing algorithm, and routers at the edge of the AS are responsible for forwarding packets to a destination outside the AS.
In conclusion, the routing algorithm in computer networks plays a crucial role in determining the path for packets to be transmitted from the sender to the receiver. The target routing algorithm is simple: given a set of routers and links connecting the routers, the algorithm finds the best path from the source router to the destination router, usually the path with the lowest cost. The LS and DV algorithms use different methods to calculate the routing problem, with the LS algorithm requiring complete, global information and converging quickly, while the DV algorithm converges slowly and may suffer from routing loops. The level routing algorithm is implemented through the router into AS, with each router running the same routing algorithm and routers at the edge of the AS responsible for forwarding packets to a destination outside the AS.