Discussion on Routing Algorithm Computer Science YouTube Lecture Handouts

Doorsteptutor material for GATE is prepared by world's top subject experts: Get detailed illustrated notes covering entire syllabus: point-by-point for high retention.

Discussion on Routing Algorithm

Complete notes and preparation module at

doorsteptutor. com

  • What is a router?
  • Why Routers?
  • Router՚s two process.
  • Properties of Routing Algorithm.
  • Types of Routing Algorithm.
  • Adaptive Routing Algorithm.
    • Centralized Algorithm.
    • Isolation Algorithm.
    • Distributed Algorithm.

Discussion on Routing Algorithm

  • Non-Adaptive Routing Algorithm.
    • Flooding.
    • Random Walk.
  • Distance Vector Routing.
  • MCQ

Router

  • Router is basically designed to receive, analyse and forward the data packets between computer networks.
  • It also uses the routing protocols for transferring the data packets across a network.
  • it՚s more expensive than switches, hubs etc.
  • Router automatically choices the best path for transferring the data packets to the network.

Why Routers?

  • Router analyse destination IP address of the packet that arrives to it and compares it with the routing table then decides the path where packet has to be transmitted.
  • It is also more capable than any other network such as hubs, switches etc.
  • Hub has only forwarding capability i.e.. it does not analyse or modify anything with the transferring data.
  • But, router can analyse, modify the data.

Two Processes

  • Router basically performs two tasks or process.
  • Forwarding: Firstly it will receive each packet that arrives, after that looking up the outgoing line i.e.. used in the routing tables. This process is called Forwarding.
  • Second process is responsible for filling in and updating the routing tables. From this process routing algorithm comes into play.
Two Processes

Properties in Routing Algorithm

  • Routing Definition: Routing is the process of forwarding the packet in a network i.e.. from source to destination but the best route from which the packet is transmitted is decided by Routing Algorithm. So that it can reaches its intended destination.
    • Routing algorithm comes under in the network layer.
  • Properties:
    • Correctness: Routing should be done correctly so that packet reaches its proper destination. If it՚s not done properly, we can՚t send the data to the person.
    • Simplicity: Routing should be done in a simple manner which means complex path is not efficient way in routing algorithm. Shortest path is the example of simplicity.
    • Robustness: Ability to deliver the packet in case of failures.
    • Stability: The algorithm should be stable in the face of changing conditions i.e.. . under all circumstances in the network.
    • Fairness: Every node connected to the network get atleast a fair chance of transmitted their packets.
    • Optimality: It includes throughput and minimizing which means minimum packet delays.

Types of Routing Algorithm

Types of Routing Algorithm
  • Adaptive Routing Algorithm: is also known as dynamic routing algorithm.
    • Routing will change or make the decision dynamically based on changes occur in Topology and network traffic.
  • The main parameters are:
    • Hop count: Hop represents the path between source and destination, while hop count is the measurement of distance (i.e.. . Measures the distance from source to destination) .
    • Distance
    • Transmit time

Classification of Adaptive Routing

An Adaptive routing can be classified into three ways or parts:

  • Centralized Algorithm: is also called as global routing algorithm. Here it computes least-cost path based upon the global information about the network.
  • Link state algorithm is the example of centralized algorithm as it aware the cost of each link connected in the network.
  • For ex:
Classification of Adaptive Routing

Here in the above diagram we can see sending the packet from A ⇾ C through least cost path is:

A ⇾ C … 10

A ⇾ B ⇾ C … 8 is least cost path.

  • Isolation algorithm: In this routing is decided by using local information rather than global information.
  • Distributed Algorithm: It computes least cost path based on iterative and distributed manner from source to destination.
    • It is also known as decentralized algorithm.
    • Distance Vector algorithm is the example of decentralized algorithm.
    • Initially the current node knows only the information about its own directly attached links, based on iterative process it computes least cost path to the destination.

Non-Adaptive Routing Algorithm

  • Non- Adaptive routing: Its also known as static routing algorithm.
  • Routing process will be designed in advance. The way in which the packet reaches to the destination is set in advance in routing process.
  • When the booting completes all the routing process will be stored in routers, so the router will blindly follows this routing process. In between the transmission the router does not change their routing process.
  • It is not based on Topology or network traffic. So any changes occur in network traffic or topology does not effect on routing process.

Classification of Non-Adaptive Routing

Classified in two ways:

Flooding: In this all the incoming packets will be transmitted to all the outgoing links except the router or the link which it՚s received. So the multiple copies of the packet can be made to the node.

For ex:

Classification of Non-Adaptive Routing

In this when 1 packet arrives to the router it will send it automatically to all the outgoing routers or links.

  • Random Walks: In case of random walks, all the incoming packets will be transmitted to the neighbour links randomly. So, it will not send every packet to the outgoing link.
  • This process is best for setting alternative path.
  • Random Walk is efficient than flooding.

Distance Vector Routing

  • The distance vector routing is an adaptive or dynamic algorithm. It is also known as Bellman-Ford or Distributed Bellman-Ford Routing Algorithm.
  • It nature is iterative, distributed and asynchronous.
  • Each and every Router maintains a table i.e.. Known as “VECTOR” . Tables basically contains either a distance (Hop-Hop) or delay.
  • The main key points is:
    • Knowledge about the whole network: The router sends whole of its knowledge to its neighbours.
    • Routing only to neighbours: Tables update their information with the help of exchanging information with the routers (neighbours) . The router sends its information to only those routers who have direct links.
    • Information sharing to regular intervals: Every router sends information to the neighbouring links (routers) in few seconds of interval.
    • Every router knows the best distance to reach the another router.

Routing Table

Routing table contains two process:

  • Creating table
  • Updating table

Creating Table: It has three parts

  • Network Id: It defines the destination of the packet.
  • Cost: Cost should be minimum and no. of intermediate nodes should be minimum.
  • Next hop: Next hop contains information about the router to which packet must be delivered.

Updating table: means how the packet should go to the one hop to next (router to router) .

Updating Table
DestinationCostNext hop

MCQs

Q1. In … routing, the routing table hold the address of just the next hop instead of complete route information.

1. next-hop

2. host-specific

3. network-specific

4. Default

Answer: 1

Q2. The Enhanced Interior Gateway Routing Protocol (EIGRP) is categorized as a …

1. Distance vector routing protocols

2. Link state routing protocols

3. Hybrid routing protocols

4. Automatic state routing protocols

Answer: 3

Charters:

0: 00 Routing Algorithm

1: 15 What is a Router?

2: 37 Why Routers?

3: 50 Two Processes of Router

4: 57 Properties in Routing Algorithm

7: 00 Types of Routing Algorithm

8: 17 Classification of Adaptive Routing

9: 53 Non Adaptive Routing Algorithm

10: 33 Classification of Non-Adaptive Routing

11: 37 Distance Vector Routing

12: 48 Routing Table

13: 15 MCQ about Routing Algorithm

Developed by: