Ch 5- Network Layer

• Introduction:
• Design Issues
• Inter connecting devices, IP protocols & subnets
• Routing Algorithms
• Routing Classification
• Goal of Routing Algorithm
• Shortest path routing, Flooding, Optimality principles
• Distance vector routing, Link state routing
• Broadcast, multicast, anycast routing
• Congestion Control
• Quality of service
• Internetworking, Addressing
• n/w layer protocols, IPv4 and IPv6

​

Computer Networks

Distance Vector Routing

• Introduction:
• All Router s & n/w as Graph
• Bellman Ford Algo.
• Find shortest path between nodes in graph based on given distance between them
• Least cost between two nodes
• One routing table per node
• Distance at each node (Algo.)
• dx(y) = cost of { least cost path from S to D }
• Update distance based on neighbour

dx(y) = min { cost (x,v) + dv(y) }

Computer Networks

Distance Vector Routing

• For e.g. A to B A🡪 B =1 A🡪C🡪B = 8
• For e.g. B to (A,C,E,D) DVR table for B

B to A Dest. Cost NextHop

B🡪 A = 1 A 1 A

B🡪C🡪A = 8 C 3 C

B🡪E🡪D🡪C🡪A = 20 E 9 E

D 7 C

Computer Networks

• Distance vector is a distributed routing algorithm
• Shortest path computation is split across nodes
• Algorithm:
• Each node knows distance of links to its neighbors
• Each node advertises vector of lowest known distances to all neighbors
• Each node uses received vectors to update its own
• Repeat periodically

Computer Networks

Distance Vector Routing

• DVR (parameter for matrices)
• Nr. Of Hop’s
• Distance
• Propagation delay ( Xi + m )

Source 🡪 Destination (via intermediate nodes)

For e.g. S 🡪A🡪D

S to A called Xi & A to D called m

Computer Networks

Distance Vector Routing

Computer Networks

Distance Vector Routing

• Distance vector is a distributed routing algorithm
• Shortest path computation is split across nodes
• Algorithm:
• Each node knows distance of links to its neighbors
• Each node advertises vector of lowest known distances to all neighbors
• Each node uses received vectors to update its own
• Repeat periodically

Computer Networks

Distance Vector Routing

Computer Networks

Count to Infinity Problem

Computer Networks

Count to Infinity Problem

X

A

B

X

X

1

1

1

2

A

B

3

4

A

-

Link state Routing

• Introduction:
• Link state is an alternative to distance vector
• More computation but simpler dynamics
• Widely used in the Internet (OSPF, ISIS network)
• (building routing table)
• Creation of the state of the links by each node called LSP (link state packet)
• Dissemination of LSP’s to every router called flooding
• Formation of shortest path tree for each node
• Calculation of routing table based on shortest path tree

From S to (Desti. Cost NextHop/router)

​

Computer Networks

Link state Routing

Computer Networks

Link state Routing

• Routing Table for node A

Desti. Cost NextHop

A 0 -

B 2 -

C 7 B

D 3 -

E 6 B

F 8 B

G 9 B

Computer Networks

• whole topology can be compiled from partial knowledge of each node
• Create sink tree for router A

​

Link state Routing

Computer Networks

Topology/ Graph

Sink tree for Source A

Link state-learning about the neighbors

Computer Networks

Link state Routing

Computer Networks

LSP for each node

Hierarchical Routing: Cluster, Zone, Group, Region

Computer Networks

Computer Networks

Computer Networks

Computer Networks

Computer Networks

Computer Networks

• Basic terms:
• Sender to Receiver : Cost or metric (passing n/w)
• Cost (should be minimum)
• Static: Manual entries….follow it
• Dynamic: Entries are updated automatically , when there is any change
• Routing Protocols: (Follows Rules & procedures)

“change in route info- inform to all router”

• Interior (intra domain) routing : DVR RIP, LSP OSPF
• Exterior (inter domain) routing: path vector BGP
• Internet is divided in to Autonomous systems (AS) which is groups of n/w & routers

Computer Networks

​

​

End of Part-2 (Ch-5 Network layer)

​

?

Thanks.

By Hitesh Barot

​

​