ROUTING PROTOCOLS

(Algorithms)

Unit-III

Dr. Shankar Thawkar

 Questions

• What is count to infinity problem (5 Marks)

• What is unicast routing. Discuss unicast routing protocols. (10 Marks)

• What is meant by unicast and multicast routing,

explain with suitable example.

• What is adaptive routing algorithm. Explain various types of adaptive routing

algorithms (5Marks)
 ROUTING PROTOCOLS (Algorithms)
• The main part of network layer is routing packets from source machine to destination
machine.

• Routing algorithm is a part of network layer software.

• A routing protocol is a combination of rules and procedures that lets routers in the
Internet inform each other of changes.

• Routing algorithms are responsible for selecting route for routing packets

• Router perform following functions-

• Selection of route with the use of routing table
• Updating of routing tables
• There are two types of routing protocols-
1. Unicast Routing
2. Multicast Routing

• Unicast Routing algorithms are grouped into two types-

1. Non-Adaptive (static)
a. Shortest path routing
b. Flooding
2. Adaptive (Dynamic)
a. Distance vector Routing
b. Link state routing
c. Path vector routing
1. In Non-adaptive algorithm , route for the packet is computed in advance, off-line and
downloaded to the router when the network is booted. This procedure is some time called
static routing
2. Adaptive algorithms, in contrast , change their routing decisions to reflect changes in the
topology and usually the traffic as well. This procedure is sometimes called dynamic
routing

• Unicast protocols are also classified as-

• An autonomous system is collection networks and routers under the authority of
a single administrator.

• Routing within the autonomous system is called intradomain routing and routing
between two autonomous system is called inter-domain routing.
Unicast Routing
Static Routing- Shortest Path Routing Algorithm
• It is a static routing algorithm
• In this method, subnet is converted into graph where each node represent a router and each
edge of a graph represent a communication link.

• An Algorithm find shortest path between pair of routers.

• The cost of link may be a function of –

• Distance
• Bandwidth
• Average traffic
• Communication cost
• Delays etc.

• Dijkstra’s algorithm is used to find the shortest path

Following figure illustrate the working of shortest path routing using Dijkstra’s
algorithm. ( In fig-b at node B the value (2,A) indicate cost of node B is 2 when
going from node A i.e. (2,A) )
 Static routing- Flooding Algorithm
• It is a static routing algorithm
• In this every incoming packet is sent out on every outgoing line except the one it arrived on

• So flooding generate vast number of dummy packets

• Following methods are used to stop and eliminate duplicate packets
i. Using Hop counter
• Decrement counter at each router
• Discard packet if counter is ‘0’ “(zero)
ii. Using sequence number
• use sequence number to each packet. This will avoid sending same packet at same time.
• Each router maintain list of packets already seen.
iii. Selective flooding- transmit packet on selected links only
• Applications-
• Military application ( base station to All)
• In distributed database applications (update all database)
• In wireless network
Distance Vector Routing Algorithm
• It is a dynamic routing algorithm
• It take decisions based on current load of the network.
• In this method each router maintain a vector (table) of minimum distance to every router.
• It is some time called Bellman-Ford routing.
• It was the original ARPANET routing algorithm and used in Internet with name RIP (Routing Information
Protocol)
• In this method each node share its routing table to its immediate neighbors. (periodically or change in
topology)
• Each router update its routing table according to received vector from neighbors
• Following figure shows how node A update its routing table after receiving partial table from node C

Rules for updation- compare table A-old and A-

modified as-
• If next node entry is different in both tables then
consider row with smaller cost.
• If next-node entry is same then use new row.
 RIP
• Routing information protocol (RIP) is an intradomain routing protocol used
inside an autonomous system based on distance vector routing protocol.
• RIP implement distance vector routing as-
• The destination in a routing table is a network.
• The metric used by RIP is very simple; the distance is defined as number
of links ( networks) to reach the destination. For this reason metric in RIP
is called as hop-count.
• RIP used maximum 16 hop-counts (networks) to reach the destination.
Count to Infinity Problem
• One of the main issue in distance vector routing is- routing loops

• The problem occurs when an link between routers goes down and two nodes send update to each
other at the same time.

A 1 B 1 C
A's Routing Table B's Routing Table

to via cost to via cost

(next hop) (next hop)
C B 2 C C 1
now link B-C goes down
This problem continue as infinite
C B 2 C - oo loop, called count to infinity
C 2 C oo problem.
C - oo C A 3

C oo C 3 This problem can be solved

C B 4 C - oo using split horizon. It says, that
C 4 C oo
router never advertised the cost
of destination back to its next
hop. ( as it learn from it)
 Link state routing Algorithm
• It is a unicast routing algorithm based on dynamic routing.
• Distance vector routing was used in ARPANET until 1979, when it was replaced by link state
routing.
• Node use Dijkstra’s Algorithm to build routing table
• Each node uses same topology to build routing table
• Topology Must be dynamic
Link state Knowledge
• How can a Common Topology be dynamic?
• Each Node have a partial knowledge about topology, but does not have global knowledge
• The whole topology is compiled from the partial knowledge of each node

•Since Node A knows that, it is connected to node B with metric 5, to C by 2 and so on. This partial
knowledge is used to create whole topology.
Building Routing Table

Each router must do the following-

1. Create a link state packet (LSP)
2. Send this packet to all other routers
3. Compute shortest path to every other router
4. Calculation of routing table based on shortest path

1. LINK STATE PACKET (LSP)

• A LSP carry following information-
•Node identity,
•list of links,
•seq_no and age
• Node identity and list is used to create topology, While Seq_nos are used for flooding and differentiate old
LSP from new LSP and Age is used to discard old LSP.
• LSPs are generate if there is a change in topology or periodically
2. Send LSP to all other Routers (flooding)
• Once the router prepared an LSP, it must be send to all other routers
• A router that receive an LSP , it compare with old LSP, if new copy is older then discard new LSP
( based on Seq_no ), otherwise
• Discard old and keep new
• It send this copy to all routers

3. Compute shortest path- use Dijkstra’s algorithm

Consider the following graph

4. The shortest path computed for node A using above shortest path tree is given below

• Link state routing is widely used in actual networks.

• It is implemented as-
•OSPF protocol (open shortest path first)
•IS-IS (Intermediate system-Intermediate system)
 Path Vector Routing Algorithm
➢ Since Distance vector (DVR) and Link state routing (LSR ) are intradomain routing
protocols.
➢ These two are not suitable for Inter-domain routing because of scalability.
➢ Path Vector routing is suitable for inter-domain routing
➢ It is similar to distance vector routing
➢ In this , each AS contain a special node , called speaker node.
➢ Speaker node in each AS create a routing table and share with its neighboring ASs (
share path)
➢ Figure shows initial routing table in path vector routing
Sharing of Tables :
➢ Like Distance vector routing, in path vector routing speaker in AS (autonomous system) share routing
table to its neighbors
➢ The Speaker node share the path instead of metric to neighboring speaker node

Example – A1 share with B1 and C1, B1 share with A1 and C1…..

Updating of Routing tables :
➢ Once the speaker receive table from neighbor it update its routing table by adding the nodes that are not
in its table along with its own AS and sender AS
BGP- Border gateway (BGP)
• It is an inter-domain routing protocol.
• It uses path vector routing.
• Design for huge network like internet
• Border Gateway Protocol (BGP) refers to a gateway protocol that enables the internet to
exchange routing information between autonomous systems (AS). -- ---networks managed by a single
enterprise or service provider

• BGP has default

mechanism for detecting
loops.
MULTICAST ROUTING PROTOCOLS
Q. Explain Unicast and Multicast routing with suitable example.

Unicast Routing :
➢ In Unicast there is one source and one destination
➢ The relation between source and destination is one-to-one
➢ In unicast routing both source and destination contain unicast
address.
➢ In Unicast routing router forward the packet through only one of
its interface.
Multicast Routing :
➢ In Multicast routing there is one source and group of destination
➢ The relation between source and destinations is one-to-many
➢ In multicast routing , source address is unicast but destination address is multicast.
➢ In Multicast routing router may forward the packet through many interface.
➢ As shown in following figure, Multicast packet start from S1 and goes to all destinations of G1
Broadcast Routing :
➢ In broadcast communication , the relationship between source to destination is one-to-all. There is only one
source , but all other host are destinations.
➢ The Internet does not explicitly support broadcasting because of the huge amount of traffic it would create and
because of bandwidth it would needed.

Multicasting versus multiple unicasting :

➢ Multicasting start with single packet

that is duplicated by router
➢ In multiple routing , several
packets start from source
➢ See figure for multicasting vs multiple unicasting
Q.1 Which layer is responsible for data translation
a. Application
b. Network
c. Presentation
d. Data link

Q2. Host – to host connectivity is provided by-

a. Network layer
b. Session layer
c. Presentation
d. Transport layer

Q3. In OSI model, which of the following layer transform information from machine format
into user understandable format-
a. Application
b. Presentation
c. Session
d. physical
Q.4 Which layer of OSI determine the interface of the system with user
a. Network
b. Application
c. Data link
d. session

Q5. OSI model consist of -----layers

a. Three
b. five
c. seven
d. Eight

Q6. The ------layer decide the location of the synchronization points.

a. Transport
b. Session
c. Presentation
d. Application
Q.7 End-to-end delivery of the entire message is the responsibility of-
a. Network
b. Transport
c. Session
d. Presentation

Q8. The -----layer closest to the transmission medium

a. physical
b. Data link
c. network
d. transport

Q9. In the---- layer data unit is called frame

a. Physical
b. Data link
c. Network
d. transport
Q.10 dialog control is the function of --
a. physical layer
b. Data link
c. Presentation
d. session

Q11. Decryption and encryption of data is the responsibility of—

a. physical
b. Data link
c. presentation
d. session

Q12. Mail system and directory services are available to network users through the--- layer
a. Data link
b. Session
c. Transport
d. application
Q.13 Node-to-node delivery of data units is the responsibility of --
a. physical layer
b. Data link
c. Transport
d. Network

Q14. As the data packets moves from lower to upper layer , headers are---
a. added
b. subtracted
c. rearranged
d. modified

Q15. When data is transmitted from device A to device B, the headers from A’s layer 5 is read
by B’s -------
a. physical
b. Transport
c. session
d. presentation
Q.16 Which topology is a point-to-point line configuration
a. mesh
b. bus
c. star
d. All

Q17. In a link only traffic is between the two connected devices

a. secondary
b. primary
c. dedicated
d. None

Q18. In a network with 25 computers, which topology require extensive cabling

a. mesh
b. star
c. bus
d. ring
 Additional Topic
Hierarchical Routing
• The routers are divided into what we will call regions, with each router
knowing all the details about how to route packets to destinations within its
own region, but knowing nothing about the internal structure of other
regions.
• For huge networks, a two-level hierarchy may be insufficient; it may be
necessary to group the regions into clusters, the clusters into zones, the
zones into groups, and so on, until we run out of names for aggregations.

• Following Figure (a) gives a quantitative example of routing in a two-level

hierarchy with five regions.
• The full routing table for router 1A has 17 entries, as shown in Fig.-b.
• When routing is done hierarchically, as in Fig. (c), there are entries for all the local routers as
before, but all other regions have been condensed into a single router, so all traffic for region 2
goes via the 1B -2A line, but the rest of the remote traffic goes via the 1C -3B line.

• Hierarchical routing has reduced the table from 17 to 7 entries. As the ratio of the number of
regions to the number of routers per region grows, the savings in table space increase.