ROUTING ALGORITHMS
Mr. SARAVANAN S T
INTRODUCTION TO ROUTING
In which path packet should be transmitted to reach the destination.
ROUTING CLASSIFICATION
NON-ADAPTIVE ROUTING ALGORITHM
1. Also known as static routing
2. Routing process will designed in advance
3. All the routing process will be stored in routers when the
booting completes.
4. It doesn’t effect with change in network topology and
traffic
NON-ADAPTIVE ROUTING ALGORITHM
CLASSIFIED IN TWO WAYS
FLOODING : All incoming packets will be transmitted to all outgoing links
Multiple copies of packets.
RANDOM WALK : Income packet will be transmitted to the neighbor links randomly
Best for alternative paths.
INTRODUCTION TO ROUTING
ADAPTIVE ROUTING ALGORITHM
1. Dynamic routing Algorithm
2. Routing will change dynamically based on change in TOPOLOGY
and TRAFFIC
3. Main parameters – Hop count , Distance , Transmit Time.
CLASSIFIED IN THREE WAYS
Centralized
Isolation
Distributed
ADAPTIVE ROUTING ALGORITHM
Centralized Algorithm:
1. Global Routing Algorithm
2. Computes least cost path based on global information
Isolation Algorithm:
Routing will be decided based on local information rather than global
Information
Distributed Algorithm:
1. Computes least cost path based on iterative and distributed manner.
2. Decentralized algorithm.
INTRODUCTION TO ROUTING
1. NON ADAPTIVE ROUTING - STATIC
Shortest – Path
Flooding
Flow Based
2. ADAPTIVE ROUTING – DYNAMIC
Link State Routing – centralized routing
Distance Vector Routing – Distributed routing
3. Hierarchical Routing
4. Routing in mobile host
5. Broad cast routing
6. Multicast routing
SHORTEST – PATH ALGORITHM
► Finds the shortest path between a given pair of routers
► The cost of link may be a function of
Distance
Band width
Average Traffic
Communication cost
Delay
Time
SHORTEST PATH - DIJKSTRA’S ALGORITHM
FLOODING ALGORITHM
❖ Broadcast the packet
❖ Every incoming packets is sent out on every outgoing line except the one it
arrived on
❖ Vast number of duplicate packets are generated.
How to stop and eliminate duplicate packets:
1. Using a HOP counter
- Decrement in each router
- Discard packets if counter is 0
2. Sequence number in packet
- Avoid sending the same packet second time
- Keep in each router per source a list of packets already seen.
3. Selective Flooding
- Use only those lines that are going approximately in right direction.
FLOW BASED ROUTING ALGORITHM
► ROUTING IS DONE BASED ON
- SUBNET TOPOLOGY
- LOAD / TRAFFIC MATRIC
- LINE CAPACITY MATRIC (BANDWIDTH)
DISTANCE VECTOR ROUTING
❖ Least cost between two nodes
❖ Bellman - Ford Algorithm
❖ One routing table per node
Bellman - Ford Algorithm
Defines the distance at each node
dx(y) = cost of least cost path from x to y
update distances based on neighbours
dx(y) = min v {cost (x,v) + dis v(y)}
LINK STATE ROUTING
► OSPF (Open Shortest Path First) uses a link state routing
► learn their nearest neighbours & network addresses send
HELLO packets
► All the router shares their link state with each other by flooding
link state packets.
► Phases – Flooding, Routing Path
► Measure delay or cost to each of its neighbours
► Construct packet telling all it has learned
► Send this packet to all other routers
► Compute shortest path to every other router
► Age is used to avoid issues of network Updation.
LINK STATE ROUTING
LINK STATE ROUTING
HIERARCHICAL ROUTING
► In hierarchical routing, routers are classified in groups known as regions.
► Each router has only the information about the routers in its own region
and has no information about routers in other regions.
► Routers just save one record in their table for every other region.
► Routers only contains the record of their immediate neighbors in the
table.
► In three-level hierarchical routing, the network is classified into a
number of clusters.
► Each cluster is made up of a number of regions, and each region contains
a number or routers.
► In this method, it will route first to the region then to the IP prefix
within the region – hide details within a region from outside of the
region.
HIERARCHICAL ROUTING
BROADCAST ROUTING
Sending a packet to all the nodes on the network simultaneously is called broadcasting.
Ex : Weather Reports, Radio Program, Stock Market updates.
Methods:
1) Distinct point to point routing:
- This is a simply send a distinct packet to each destination.
- Hence it is waste of bandwidth but it also require complete list of all destination.
2) Flooding:
Every incoming packets is sent out on every outgoing line except the one it arrived
on
3) Multi destination routing:
❖ Here the packet contains either a list of destinations or a bit map indicating the
desired destination.
❖ When a packet received from broadcasting, it decides the number of output lines that
are needed by examined each destination
❖ Based on that router generate a new copy of packet to each output.
BROADCAST ROUTING
4) Use of Spanning Tree:
- Here we use sink tree for the router with to broadcast a packet
(use of spanning tree)
- Spanning tree is a subset of the subset that include all the routers but contains
the no loops.
5) Reverse path forwarding:
- Router checks whether broadcast packet arrived on interface that is used to send
source to broadcast.
- If so it’s likely that its following the best route.
- If not, packet is discarded as likely to be duplicate.
Broadcast : 6-1=5 Hops, 24 packets
Reverse path forwarding : 5-1=4 Hops, 15 packets
BROADCAST ROUTING
(a) A network. (b) A sink tree. (c) The tree built by reverse path forwarding.
MULTICAST ROUTING
► Sending a message to a group is called multicasting, and its
routing algorithm is called multicast routing
► Multicasting requires group management. Some way is needed
to create and destroy groups, and to allow processes to join
and leave groups
► To do multicast routing, each router computes a spanning tree
covering all other routers.
Multicast Routing Protocols
MULTICAST ROUTING
Multicast Routing Protocols
Unicast routing protocols use graphs while Multicast routing protocols
use trees, i.e. spanning tree to avoid loops. The optimal tree is
called shortest path spanning tree.
• DVMRP - Distance Vector Multicast Routing Protocol
• MOSPF - Multicast Open Shortest Path First
• CBT - Core Based Tree
• PIM - Protocol independent Multicast
Protocol Independent Multicast is commonly used now.
It has two flavors:
PIM Dense Mode
This mode uses source-based trees. It is used in dense environment
such as LAN.
PIM Sparse Mode
This mode uses shared trees. It is used in sparse environment such as
WAN.
MULTICAST ROUTING
(a) A network. (b) A spanning tree for the leftmost router. (c) A multicast tree for group 1.
(d) A multicast tree for group 2.
