Routing Algorithm Introduction
Dr. Kiran Manjappa
IT Dept., NITK
Previous Session
● IPv6
● How to compress the v6 addresses
● Consecutive groups of v6 address containing zeros are replaced with : :
○ It applies only for zeros
● IPv4 address in IPv6
● Routing Algorithms
○ Correct, Robust, Quick and Fair enough.
@ Time t
X Y
@ Time t + n
X Y
D
@ Time t + m
A C
X Y
B D
● Adaptive
● Non Adaptive
Two types of routing algorithm
● Non Adaptive
○ Static Routing algorithm
○ Once the Optimal route is setup, the routing layer’s job is done.
○ If congestion happens during the transmission, path will break up, then another path will be
discovered.
○ Results in
■ Re-Route rediscovery latency, pause in data transmission, retransmission, waste of
resources, waiting time.
■ Performance degradation.
● Adaptive
○ Dynamic Routing algorithm.
○ Can sense the danger, and can adapt accordingly.
○ Before path breaks up due to congestion, a new path will be chosen
○ No transmission hiccups.
○ Better performance.
Non Adaptive
B E
A C F H
D G
A is source and H is the destination. Packets Start @ A
Non Adaptive
B E
A C F H
D G
A is source and H is the destination. Packets Start @ A
Non Adaptive
B E
A C F H
D G
Non Adaptive
B E
A C F H
D G
Adaptive
B E
A C F H
D G
A is source and H is the destination. Start with A
Adaptive
B E
A C F H
D G
Adaptive
B E
A C F H
D G
Before condition worsens, new path will be chosen and will be activated.
Adaptive
B E
A C F H
D G
Before condition worsens, new path will be chosen and will be activated.
Based on Routing Table Updates
● Based on the Routing Table Update
○ Reactive Routing Algorithms
■ When packet comes, a fresh routing table entries are made
■ No prior topology information - Current topology information is collected
■ Adv: ??
■ Dis. Adv: ??
○ Proactive Routing Algorithms
■ Keeps the routing table entry intact.
■ When a packet arrives, an optimal path will be found from the existing table entries
■ Adv: ??
■ Dis. Adv: ??
Previous Session
● V6 and V4 in real world
○ V4 to v6 conversion
○ Dual stack
○ Tunneling
● Routing Algorithm
○ Simple and Fast, efficient, fair enough, robust
○ Adaptive and Non Adaptive
○ Proactive and Reactive
Routing Algorithm Classification Based on Paths
● Single Path
○ Only one path will be maintained between the source and the destination
● Multipath
○ Multiple paths will be maintained between the source and the destination.
B E
Primary Path
A C F H
D Backup Path G
Multipath Routing Algorithms
● Multipath
○ How many paths should be maintained between the source and the destination?
● Routing Parameters (Metrics)
○ Average Traffic
○ Bandwidth
○ E-2-E delay
○ Queue Status
● Performance Parameters.
○ Throughput, E-2-E delay, routing overhead, (re) route discovery latency,
● Shortest Path may not work always.
Topology - Graph
● Most of the real world problems are mapped to graphs for the optimization
● The topology are also represented in terms of graphs
● Once graphs are constructed finding shortest paths will be easy
● Each edge of a graph will have a weight
○ Each link in a topology will have a resource value
B D B D
3 3
C C
A E 5 2
A E
Dijkstra Algorithm (1959)
● Single Source Shortest Path
● Each link will be labelled.
● Initially No Paths will be known.
○ Hence, all nodes are labelled with infinity.
○ Label value will change over the time.
7
B E
2 3
2 3
1
A C F H
3 2
6 2
D 4 G
A is source and H is the destination. Start with A
(∞ , -) (∞ , -)
B E
(∞ , -)
A C F (∞ , -) H
D G
(∞ , -) (∞ , -)
(2 , A)
(∞ , -)
B E
2
(∞ , -)
A 2<6 C F (∞ , -) H
D G
(6 , A) (∞ , -)
For A, neighbors (adjacent nodes) are B (2) and D(6).
Re Label Them.
(2 , A)
(∞ , -)
B E
2
(∞ , -)
A 2<6 C F (∞ , -) H
D G
(6 , A) (∞ , -)
(2 , A)
(∞ , -)
7
B E
2
2 (∞ , -)
A C F (∞ , -) H
D G
(6 , A) (∞ , -)
For B, neighbors (adjacent nodes) are E (7) and C(2).
7+2
(2 , A) (9,B)
7
B E
4<9
2
2
(4 , B) 2+2
A C F (∞ , -) H
D G
(6 , A) (∞ , -)
For B, neighbors (adjacent nodes) are E (7) and C(2).
(2 , A) (9,B)
7
B E
4<9
2
2
(4 , B)
A C F (∞ , -) H
D G
(6 , A) (∞ , -)
For B, neighbors (adjacent nodes) are E (7) and C(2).
(2 , A) (8,B)
B E
2
2
(4 , B)
1
A C F (∞ , -) H
D G
(6 , A) (∞ , -)
For C, neighbors (adjacent nodes) are D (3) and F(1).
(2 , A) (9,B)
B E
2
2
(4 , B)
1 (5,C)
A C F H
3 5<6
D G
(6 , A) (∞ , -)
For C, neighbors (adjacent nodes) are D (3) and F(1).
(2 , A) (9,B)
B E
2
2
(4 , B)
1 (5,C)
A C F H
3 5<6
D G
(6 , A) (∞ , -)
For C, neighbors (adjacent nodes) are D (3) and F(1).
(2 , A) (8,F)
B E
2
2 3
(4 , B)
1 (5,C)
A C F H
D G
(6 , A) (7 , F)
For F, neighbors (adjacent nodes) are E (3) and G(2).
(2 , A) (8,F)
B E
2
2 3
(4 , B)
1 (5,C)
A C F H
7<8
2
D G
(6 , A) (7 , F)
For F, neighbors (adjacent nodes) are E (3) and G(2).
(2 , A) (8,F)
B E
2
2
(4 , B)
1 (5,C)
A C F H
2 (9 , G)
2
D 4 G
(6 , A) (7 , F)
For G, neighbors (adjacent nodes) are D (4) and H (2).
(2 , A) (8,F)
B E
2
2
(4 , B)
1 (5,C)
A C F H
2 (9 , G)
2
D 4 G
(6 , A) (7 , F)
For G, neighbors (adjacent nodes) are D (4) and H (2).
(2 , A) (8,F)
B E
2
2
(4 , B)
1 (5,C)
A C F H
2 (9 , G)
2
D G
(6 , A) (7 , F)
Path From A to H ( Data Structure)
Path From H to A (Reverse Route )
A - > B -> C-> F -> G -> H.
H - > G -> F-> C -> B -> A.
Total Cost 2 + 2 + 1 + 2 + 2 = 9
Total Cost 2 + 2 + 1 + 2 + 2 = 9
(7, C)
7
B E
2 3
2 3
(5 , F)
1 (4,G)
A C F H
(9 , B) 3 2
6 2
D 4 G
(2 , H)
Path From A to H ( Data Structure)
Path From H to A (In CN Route is opposite )
H - > G -> F-> C -> B -> A.
A - > B -> C -> F -> G -> H.
Total Cost 2 + 2 + 1 + 2 + 2 = 9
Total Cost 2 + 2 + 1 + 2 + 2 = 9
Find the shortest path from node A to D
9 E
F
14
2 6
A
9
C 11
D
7 10
15
B
Find the shortest path from node D to all other nodes
5
B E
3 2
4 1
3
A C F H
7 4
2 1
D 1 G
A is source and H is the destination. Start with A
Dijkstra's Algorithm Application
Guess ??
Google Map