- Routing is the process of selecting paths in a network along which to send network traffic.
- The goals of routing are correctness, simplicity, Robustness, Stability, Fairness and Optimality.
- Routing is performed for many kinds of networks, including the telephone network, electronic data networks and transportation networks.
- Routing Algorithms can be classified based on the following:
- Static or Dynamic Routing,
- Distributed or Centralized,
- Single path or Multi-path,
- Flat or Hierarchical,
- Intra Domain or Inter-Domain,
- link State or Distance Vector.
- Algorithms may be static, the routing decisions are made ahead of time, with information about the network topology and capacity, then loaded into the routers.
- Algorithms may be dynamic, where the routers make decisions based on information they gather, and the routes change over time, adaptively.
- Routing can be grouped into two categories: Nonadaptive routing, and Adaptive routing.
- Once the pathway to destination has been selected, the router sends all packets for that destination along that one route.
- The routing decisions are not made based on the condition or topology of the network.
- Examples: Centralized, Isolated, and Distributed Algorithms
- A router may select a new route for each packet (even packets belonging to the same transmission) in response to changes in condition and topology of the networks.
- Examples: Flooding, and Random Walk.
Routing AlgorithmsShortest Path Routing:
- Links between routers have a cost associated with them. In general, it could be a function of distance, bandwidth, average traffic, communication cost, mean queue length, measured delay, router processing speed, etc.
- The shortest path algorithm just finds the least expensive path through the network, based on the cost function.
- Examples: Dijkstra's algorithm
Distance Vector Routing:
- In this routing scheme, each router periodically shares its knowledge about the entire network with its neighbours.
- Each router has a table with information about the network. These tables are updated by exchanging information with the immediate neighbours.
- It is also known as Belman-Ford or Ford-Fulkerson Algorithm.
- It is used in the original ARPANET, and in the Internet as RIP.
- Neighbouring nodes in the subnet exchange their tables periodically to update each other on the state of the subnet (which makes this a dynamic algorithm). If a neighbour claims to have a path to a node which is shorter than your path, you start using that neighbour as the route to that node.
- Distance vector protocols (a vector contains both distance and direction), such as RIP, determine the path to remote networks using hop count as the metric. A hop count is defined as the number of times a packet needs to pass through a router to reach a remote destination.
- For IP RIP, the maximum hop is 15. A hop count of 16 indicates an unreachable network. Two versions of RIP exist version 1 and version 2.
- IGRP is another example of a distance vector protocol with a higher hop count of 255 hops.
- Periodic updates are sent at a set interval. For IP RIP, this interval is 30 seconds.
- Updates are sent to the broadcast address 255.255.255.255. Only devices running routing algorithms listen to these updates.
- When an update is sent, the entire routing table is sent.
Link State Routing:
- The following sequence of steps can be executed in the Link State Routing.
- The basis of this advertising is a short packed called a Link State Packet (LSP).
- OSPF (Open shortest path first) and IS-IS are examples of Link state routing.
- Link State Packet(LSP) contains the following information:
- The ID of the node that created the LSP;
- A list of directly connected neighbours of that node, with the cost of the link to each one;
- A sequence number;
- A time to live(TTL) for this packet.
- When a router floods the network with information about its neighbourhood, it is said to be advertising.
- Discover your neighbours
- Measure delay to your neighbours
- Bundle all the information about your neighbours together
- Send this information to all other routers in the subnet
- Compute the shortest path to every router with the information you receive
- Each router finds out its own shortest paths to the other routers by using Dijkstra's algorithm.
- In link-state routing, each router shares its knowledge of its neighbourhood with all routers in the network.
- Link-state protocols implement an algorithm called the shortest path first (SPF, also known as Dijkstra's Algorithm) to determine the path to a remote destination.
- There is no hop-count limit. (For an IP datagram, the maximum time to live ensures that loops are avoided.)
- Only when changes occur, It sends all summary information every 30 minutes by default. Only devices running routing algorithms listen to these updates. Updates are sent to a multicast address.
- Updates are faster and convergence times are reduced. Higher CPU and memory requirements to maintain link-state databases.
- Link-state protocols maintain three separate tables:
- Neighbour table: It contains a list of all neighbours, and the interface each neighbour is connected off of. Neighbours are formed by sending Hello packets.
- Topology table (Link- State table): It contains a map of all links within an area, including each link’s status.
- Routing table: It contains the best routes to each particular destination
- It is a non-adaptive algorithm or static algorithm.
- When a router receives a packet, it sends a copy of the packet out on each line (except the one on which it arrived).
- To prevent from looping forever, each router decrements a hop count contained in the packet header.
- As soon as the hop count decrements to zero, the router discards the packet.
Flow-Based Routing Algorithm:
- It is a non-adaptive routing algorithm.
- It takes into account both the topology and the load in this routing algorithm;
- We can estimate the flow between all pairs of routers.
- From the known average amount of traffic and the average length of a packet, you can compute the mean packet delays using queuing theory.
- Flow-based routing then seeks to find a routing table to minimize the average packet delay through the subnet.
- Given the line capacity and the flow, we can determine the delay. It needs to use the formula for delay time T.
- Where, μ = Mean number of arrivals in packet/sec, 1/μ = The mean packet size in the bits, and c = Line capacity (bits/s).
The Optimality Principal: This simple states that if router J is on the optimal path form router I to router k, then the optimal path from J to K also falls along this same path.
You can follow the detailed champion study plan for GATE CS 2021 from the following link: