Routing algorithm

-

 

Routing algorithm

  • In order to transfer the packets from source to the destination, the network layer must determine the best route through which packets can be transmitted.
  • Whether the network layer provides datagram service or virtual circuit service, the main job of the network layer is to provide the best route. The routing protocol provides this job.
  • The routing protocol is a routing algorithm that provides the best path from the source to the destination. The best path is the path that has the "least-cost path" from source to the destination.
  • Routing is the process of forwarding the packets from source to the destination but the best route to send the packets is determined by the routing algorithm.

Classification of a Routing algorithm

The Routing algorithm is divided into two categories:

  • Adaptive Routing algorithm
  • Non-adaptive Routing algorithm
Routing algorithm

Adaptive Routing algorithm

  • An adaptive routing algorithm is also known as dynamic routing algorithm.
  • This algorithm makes the routing decisions based on the topology and network traffic.
  • The main parameters related to this algorithm are hop count, distance and estimated transit time.

An adaptive routing algorithm can be classified into three parts:

  • Centralized algorithm: It is also known as global routing algorithm as it computes the least-cost path between source and destination by using complete and global knowledge about the network. This algorithm takes the connectivity between the nodes and link cost as input, and this information is obtained before actually performing any calculation. Link state algorithm is referred to as a centralized algorithm since it is aware of the cost of each link in the network.
  • Isolation algorithm: It is an algorithm that obtains the routing information by using local information rather than gathering information from other nodes.
  • Distributed algorithm: It is also known as decentralized algorithm as it computes the least-cost path between source and destination in an iterative and distributed manner. In the decentralized algorithm, no node has the knowledge about the cost of all the network links. In the beginning, a node contains the information only about its own directly attached links and through an iterative process of calculation computes the least-cost path to the destination. A Distance vector algorithm is a decentralized algorithm as it never knows the complete path from source to the destination, instead it knows the direction through which the packet is to be forwarded along with the least cost path.

Distance Vector Routing Algorithm

  • The Distance vector algorithm is iterative, asynchronous and distributed.
    • Distributed: It is distributed in that each node receives information from one or more of its directly attached neighbors, performs calculation and then distributes the result back to its neighbors.
    • Iterative: It is iterative in that its process continues until no more information is available to be exchanged between neighbors.
    • Asynchronous: It does not require that all of its nodes operate in the lock step with each other.
  • The Distance vector algorithm is a dynamic algorithm.
  • It is mainly used in ARPANET, and RIP.
  • Each router maintains a distance table known as Vector.

Three Keys to understand the working of Distance Vector Routing Algorithm:

  • Knowledge about the whole network: Each router shares its knowledge through the entire network. The Router sends its collected knowledge about the network to its neighbors.
  • Routing only to neighbors: The router sends its knowledge about the network to only those routers which have direct links. The router sends whatever it has about the network through the ports. The information is received by the router and uses the information to update its own routing table.
  • Information sharing at regular intervals: Within 30 seconds, the router sends the information to the neighboring routers.

Link State Routing

Link state routing is a technique in which each router shares the knowledge of its neighborhood with every other router in the internetwork.

The three keys to understand the Link State Routing algorithm:

  • Knowledge about the neighborhood: Instead of sending its routing table, a router sends the information about its neighborhood only. A router broadcast its identities and cost of the directly attached links to other routers.
  • Flooding: Each router sends the information to every other router on the internetwork except its neighbors. This process is known as Flooding. Every router that receives the packet sends the copies to all its neighbors. Finally, each and every router receives a copy of the same information.
  • Information sharing: A router sends the information to every other router only when the change occurs in the information.

Link State Routing has two phases:

Reliable Flooding

  • Initial state: Each node knows the cost of its neighbors.
  • Final state: Each node knows the entire graph.

Route Calculation

Each node uses Dijkstra's algorithm on the graph to calculate the optimal routes to all nodes.

  • The Link state routing algorithm is also known as Dijkstra's algorithm which is used to find the shortest path from one node to every other node in the network.
  • The Dijkstra's algorithm is an iterative, and it has the property that after kth iteration of the algorithm, the least cost paths are well known for k destination nodes.

Comments

Post a Comment

Popular posts from this blog

Switching & Modes

-
Image
  Switching When a user accesses the internet or another computer network outside their immediate location, messages are sent through the network of transmission media. This technique of transferring the information from one computer network to another network is known as  switching . Switching in a computer network is achieved by using switches. A switch is a small hardware device which is used to join multiple computers together with one local area network (LAN). Network switches operate at layer 2 (Data link layer) in the OSI model. Switching is transparent to the user and does not require any configuration in the home network. Switches are used to forward the packets based on MAC addresses. A Switch is used to transfer the data only to the device that has been addressed. It verifies the destination address to route the packet appropriately. It is operated in full duplex mode. Packet collision is minimum as it directly communicates between source and destination. It does no...
Read more

Switch Vs. Router

-
Image
  Switch Vs. Router | Difference between Switch and Router The switch and router are the two essential components of a network. Although both are the connecting devices in a network, and sometimes people assume them as the same, both have different functionality. In this topic, we will see how the switch and  router are differentiated from each other. What is a Switch? A switch is a networking device, which provides the facility to share the information & resources by connecting different network devices,  such as  computers, printers, and servers,   within a small business network. With the help of a switch, the connected devices can share the data & information and communicate with each other. Without a switch, we cannot build a small business network and cannot connect devices within a building or campus. Types of Switch There are mainly two types of switches in the network, which are given below: Unmanaged Switches The unmanaged switches are mainly u...
Read more

IP Address Format and Table

-
Image
  IP Address Format and Table IP address is a short form of "Internet Protocol Address." It is a unique number provided to every device connected to the internet network, such as Android phone, laptop, Mac, etc. An IP address is represented in an integer number separated by a dot (.), for example, 192.167.12.46. Types of IP Address An IP address is categorized into two different types based on the number of IP address it contains. These are: IPv4 (Internet Protocol version 4) IPv6 (Internet Protocol version 6) What is IPv4? IPv4 is version 4 of IP. It is a current version and the most commonly used  IP  address. It is a 32-bit address written in four numbers separated by a dot (.), i.e., periods. This address is unique for each device. For example, 66.94.29.13 What is IPv6? IPv4 produces 4 billion addresses, and the developers think that these addresses are enough, but they were wrong. IPv6 is the next generation of IP addresses. The main difference between IPv4 and IPv6 ...
Read more