UNIT-2
NETWORK LAYER DESIGN ISSUES
Contents
• Network layer design issues: Store and Forward
packet Switching, Services Provided to the
Transport Layer Implementation of
Connectionless Service, Implementation of
Connection Oriented Service,
• Comparison of Virtual Circuit and Datagram
Subnets; Routing algorithms: Shortest Path
Routing, Flooding,
• Distance Vector Routing, Link state Routing,
Hierarchical Routing Broadcast Routing, and
Multicast Routing.
Network Layer Design Issues
• Store-and-forward packet switching
• Services provided to transport layer
• Implementation of connectionless service
• Implementation of connection-oriented service
• Comparison of virtual-circuit and datagram networks
Store-and-Forward Packet Switching
ISP’s equipment
The environment of the network layer protocols.
Services Provided to the Transport
Layer
1. Services independent of router technology.
2. Transport layer shielded from number, type,
topology of routers.
3. Network addresses available to transport layer
use uniform numbering plan
– even across LANs and WANs
Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Implementation of Connectionless Service
ISP’s equipment
A’s table (initially) A’s table (later) C’s Table E’s Table
Routing within a datagram network
Implementation of
Connection-Oriented Service ISP’s equipment
A’s table C’s Table E’s Table
Routing within a virtual-circuit network
Comparison of Virtual-Circuit
and Datagram Networks
Comparison of datagram and virtual-circuit networks
Routing Algorithms
• Shortest path algorithm
• Flooding
• Distance vector routing
• Link state routing
• Hierarchical Routing
• Broadcast Routing
• Multicast Routing
Routing Algorithms
• Finding issue
• Multiple hops
• Algorithm, data structure
• Routing, Forwarding
• Properties of a routing algorithm: correctness,
simplicity, robustness, stability, fairness,
efficiency
Routing Algorithms
• Non-adaptive –static routing
• Adaptive-dynamic routing
information they collect
When route changes
Metric for route computation
Shortest Path Algorithm (1)
The first five steps used in computing the shortest path
from A to D. The arrows indicate the working node
Dijkstra’s Algorithm
• Create a set sptSet (shortest path tree set)
that keeps track of vertices included in the
shortest path tree, i.e., whose minimum
distance from the source is calculated and
finalized. Initially, this set is empty.
• Assign a distance value to all vertices in the
input graph. Initialize all distance values
as INFINITE. Assign the distance value as 0 for
the source vertex so that it is picked first.
Dijkstra’s Algorithm
• While sptSet doesn’t include all vertices
– Pick a vertex u that is not there in sptSet and has a
minimum distance value.
– Include u to sptSet.
– Then update the distance value of all adjacent vertices
of u.
• To update the distance values, iterate through all adjacent
vertices.
• For every adjacent vertex v, if the sum of the distance value
of u (from source) and weight of edge u-v, is less than the
distance value of v, then update the distance value of v.
Flooding
• Local technique
• Generates vast number of duplicate packets
• To control duplicates:
Use hop counter
Use sequence number
Uses of flooding
• In broadcasting
• Robustness
• Always chooses the shortest path
Distance Vector Routing
• Dynamic routing algorithms:
Distance Vector
Link state routing
• Also called Bellman-Ford algorithm
• ARPANET routing algorithm used in internet
under the name of RIP
Distance Vector Routing
• WORKING:
Each router maintains a table, containing one
entry for every router in the network
Two parts per entry: outgoing line, distance to
that destination
Distance: hops, delay(ECHO packets)
Distance Vector Routing
(a) A network.
(b) Input from A, I, H, K, and the new routing table for J.
Distance Vector routing
Distance Vector routing
Distance Vector routing
The Count-to-Infinity Problem
The count-to-infinity problem
