Routing Protocols notes document .pptx.pdf

Notes on Routing

1. Routing

2. Introduction
●The main role of the network layer is to move packets from the source host to
the receiving host. This function is done by the routers. There are two
important network layer functions:
○Packet forwarding
○ Routing
●Packet Forwarding: the process of transferring packet from an incoming link to
an outgoing link within a single router
●Routing: The process of deciding the best paths that a packet should follow
from source to destination. The process is performed by routing protocols
which are within the router processor. The routing protocols are responsible
for calculating the best paths. The process involves interaction of many or all
network routers
2

3. Router Architecture
Router Architecture
3

4. Router Architecture
The router has four main components
1.Input ports: Performs the following functions
○terminates physical layer link at a router
○Performs look up. The lookup involves consultation of forwarding table to determine the output
port to which an incoming packet will be forwarded.
2.Switching fabric: The role of switching fabric is to connect input ports to output
ports. Example is crossbar switching fabric


4

5. Router Architecture
Crossbar switching fabric



5

6. Router Architecture
Output Ports: stores packet received from input ports through the switching
fabric and transmits these packets on the outgoing link by performing
necessary link layer and physical layer functions.
Routing processor: This part executes the routing protocols. It maintains
routing protocols, the link state information and computes forwarding tables
The routers input ports, output ports and the switching fabric together they implement
the forwarding function also known as router forwarding plane (Data plane). It is
implemented in hardware


6

7. Router Architecture
The router processor forms what is known the router control plane. Router
management functions are done in the routing processor. The control plane is
implemented inform of software

7

8. Forwarding
This is router local action of moving packets from an input link interface to the
appropriate output link interface. Every router has a forwarding table. Router
forwards packets by examining the value of a field in the arriving packet header
and the using this value to index into the router forwarding table. The value stored
in router forwarding table for that header indicates the link outgoing interface
where the packet will be forwarded
8

9. Routing
Routing is a network wide process that determines end to end paths that packets should follow from source to
destination. The routing functionality is executed in the routing processor. Since each router executes its own routing
functions, the control plane is decentralised. Ways to classify Routing Protocols

1. Dynamic versus static protocols
Dynamic algorithms change the routing paths as the network state changes, that is change in network traffic load,
topology change etc. With Static routing algorithms, the routes do not change or changes very slowly over time.
2. Linkstate versus distance vector routing protocol
Link state routing algorithms: These algorithms have complete information on the state of the network, that is, they
have complete knowledge on complete network topology and all link costs. NB: in routing every link as a weight we call
link cost. The cost depend on how good or bad the link is.

9

10. Link state routing
In link state routing, using complete topology of the network,each node develops a graph
and then the algorithm executes to find the best path (least cost paths). Example of link state
routing algorithm is Dijkstra’s Algorithm
Dijkstra’s Algorithm computes the least cost path in a graph from one node to all other
nodes in the network.
10

11. Dijkstra’s Algorithm
The algorithm is used for solving the shortest path problem in a graph or network
How it works
Step1
Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
Step2
Assign to every node a tentative distance value: set it to zero for our initial node and to infinity
for all other nodes. Set the initial node as current.




11

12. Dijkstra’s Algorithm
Step3
For the current node, consider all of its unvisited neighbours and calculate their tentative distances through
the current node. Compare the newly calculated tentative distance to the current assigned value and assign
the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it
with a neighbour B has length 2, then the distance to B through A will be 6 + 2 = 8. If B was previously marked
with a distance greater than 8 then change it to 8. Otherwise, the current value will be kept.
Step4
When we are done considering all of the unvisited neighbours of the current node, mark the current
node as visited and remove it from the unvisited set. A visited node will never be checked again.




12

13. Dijkstra’s Algorithm
Step5
If the destination node has been marked visited (when planning a route between two specific
nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when
planning a complete traversal; occurs when there is no connection between the initial node and
remaining unvisited nodes), then stop. The algorithm has finished.
Step6
Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the
new "current node", and go back to step 3.




13

14. Dijkstra’s Algorithm: Example




14

16. Dijkstra Animated Example

17. Dijkstra Animated Example

25. Distance Vector Routing Protocol
Distance routing protocol is a decentralised routing algorithm in which each node constructs a
one dimensional array (vector or table) containing distances to its neighbour. Through
broadcasting each node communicates its vector or table to others. These tables are
broadcasted periodically. The nodes compares their stored tables with received table with
received information from neighbours and make appropriate update. The Initial assumption of
the algorithm is that each node knows the cost of the link to each of its directly connected
neighbours. When a link goes down it is assigned infinity cost meaning that it is disconnected.

25

26. Distance Vector Routing Protocol
The minimum distance between any two nodes is computed using Bellman’s Ford Algorithm

d
x
(y) = min
v
{c(x,v) + d
v
(y)}, where d
x
(y) is the minimum distance from node x to node y

26

27. Example
Consider the network shown in the figure below with four nodes. Cost links are shown in the
diagram. Give the distance-vector routing tables for node C in the following two consecutive
steps.





●Step 0: C knows the distances to its immediate neighbours and
●Step 1: information from step 0 is exchanged as per the distance-vector
algorithm.




27

28. Example




28
B C D E
C 1 0 2 5
B C D E
C 1 0 2 3