Network Layer

Introduction
 The network layer is concerned with getting
packets from the source all the way to the
destination. [hops]
 The data link layer has modest goal of just
moving frames from one end of a wire to
the other.
 Network layer is the lowest layer that deals
with end-to-end transmission.
 Choosing appropriate path. [routing]
 Network Layer Design Issues
service to TL and internal design

1) Store-&-forward Pkt s/w:

2) Service Provided to the Transport
Layer:
The services need to be carefully designed with
the following goals in mind:
1. The services should be independent of the
router technology.
2. The transport layer should be shielded from the
number, type, and topology of the routers
present.
3. The network addresses made available to the
transport layer should use a uniform numbering
plan, even across LANs and WANs.
The network layer should provide
connection-oriented service or connection-
less service.
1. One champ (Internet): Connectionless
Router job is to just to move pkts; n/w is
unreliable; host should do error and flow
control.
2. Other champ (Telephone): Connection-Or
Reliable; QoS is dominant factor -> real-time
traffic such as voice and video.
 If connectionless service is offered, packets are
injected into the network individually and routed
independently of each other. No advance setup
is needed. In this context, the packets are
frequently called datagrams (in analogy with
telegrams) and the network is called a datagram
network.

 If connection-oriented service is used, a path

from the source router all the way to the
destination router must be established before
any data packets can be sent. This connection is
called a VC (virtual circuit), in analogy with
the physical circuits set up by the telephone
system, and the network is called a virtual-
circuit network
3) Implementation of Connectionless Service
4) Implementation of Connection-Or Service
Comparison
 Routing
 The main function of the network layer is routing
packets from the source machine to the destination
machine.
 The routing algorithm is that part of the network
layer software responsible for deciding which output line
an incoming packet should be transmitted on.
 If the network uses datagrams internally, this decision
must be made anew for every arriving data packet since
the best route may have changed since last time.
 If the network uses virtual circuits internally, routing
decisions are made only when a new virtual circuit is
being set up. Thereafter, data packets just follow the
already established route. The latter case is sometimes
called session routing because a route remains in
force for an entire session (e.g., while logged in over a
VPN).
 It is sometimes useful to make a distinction
between routing, which is making the
decision which routes to use, and
forwarding, which is what happens when a
packet arrives.
 One can think of a router as having two
processes inside it.
 One of them handles each packet as it
arrives, looking up the outgoing line to use
for it in the routing tables. This process is
forwarding.
 The other process is responsible for filling in
and updating the routing tables. That is
where the routing algorithm comes into play.
 Regardless of whether routes are chosen
independently for each packet sent or only
when new connections are established,
certain properties are desirable in a routing
algorithm:
 correctness, simplicity, robustness,
stability, fairness, and efficiency.
 Nonadaptive and Adaptive Routing
Algo

 Nonadaptive algorithms do not base their

routing decisions on any measurements or
estimates of the current topology and traffic.
Instead, the choice of the route to use to get from
I to J is computed in advance, offline, and
downloaded to the routers when the network
is booted. This procedure is sometimes called
static routing. Because it does not respond to
failures, static routing is mostly useful for
situations in which the routing choice is clear.
 Adaptive algorithms, in contrast, change
their routing decisions to reflect changes in
the topology, and sometimes changes in the
traffic as well.
 These dynamic routing algorithms differ in
◦ where they get their information (e.g., locally,
from adjacent routers, or from all routers),
◦ when they change the routes (e.g., when the
topology changes, or every ΔT seconds as the load
changes), and
◦ what metric is used for optimization (e.g.,
distance, number of hops, or estimated transit
time).
The Optimality Principle(Bellman,
1957)
 It states that if router J is on the optimal
path from router I to router K, then the
optimal path from J to K also falls along the
same route.
 As a direct consequence of the optimality
principle, we can see that the set of optimal
routes from all sources to a given
destination form a tree rooted at the
destination. Such a tree is called a sink
tree and is illustrated in Fig. (where the
distance metric is the number of hops. )
Shortest Path Algo
Flooding
 When a routing algorithm is implemented,
each router must make decisions based
on local knowledge, not the complete
picture of the network. A simple local
technique is flooding, in which every
incoming packet is sent out on every
outgoing line except the one it arrived on.
Distance Vector Routing
 Computer networks generally use dynamic
routing algorithms that are more complex
than flooding, but more efficient because
they find shortest paths for the current
topology.
 Static algo do not take the current n/w load
into account.
 Two dynamic algorithms in particular,
distance vector routing and link state routing,
are the most popular.
 A distance vector routing (distributed
Bellman-Ford) algorithm operates by
having each router maintain a table (i.e., a
vector) giving the best known distance to
each destination and which link to use to get
there. These tables are updated by
exchanging information with the neighbours.
Eventually, every router knows the best link
to reach each destination.
 In distance vector routing, each router
maintains a routing table indexed by, and
containing one entry for each router in the
network.
 This entry has two parts:
◦ the preferred outgoing line to use for that
destination and
◦ an estimate of the distance to that destination.

 The distance might be measured as the

number of hops or using another metric, as
we discussed for computing shortest paths.
 Principle: Each router periodically shares
its knowledge about neighbors or
internetworks with its neighbors only.
 It receives information from directly attached
neighbors only.
 Example from Tanenbaum
 Example from Forouzan
 Bellman ford and Distance vector
 Characteristics of Algorithms

 Distributed: as it receives and send back

information to neighbors
 Iterative: it updates table periodically
 Asynchronous: all routers need be
updated at the same time
Link State Routing
 Distance vector routing was used in the
ARPANET until 1979, when it was
replaced by link state routing. The primary
problem that caused its demise was that
the algorithm often took too long to
converge after the network topology
changed (due to the count-to-infinity
problem). Consequently, it was replaced by
an entirely new algorithm, now called link
state routing.
 Link State Routing Algorithm
 Distance : delay(time) or Traffic or security
 Principle: Each router shares it information
with all the routers in the networks.
 Algorithm:
 Discover the neighbor and learn network
address
 Measure the delay or cost
 Construct link state packet
 Send it to all routers in network
 Compute shortest distance path for all
routers using Dijkstra’s algorithm
 Step –I: Sends a special hello packet on
each point to point line and get the
information about network address.
 Step-II: Sends the echo packet to neighbors
and calculate the delay by RTT/2
 Step-III: Construct the link state packet for
each router
 Step-IV: Each router sends it link state
packet to all and hence all router will have
same link state database
 State V: Apply Dijkstra’s algorithm to find
shortest path tree for each router
 Note A To B cost is
01 and B To A cost
is 04

Router Network ID Cost Neighbor

A 14 1 B
A 78 3 F
A 23 2 E
B 14 4 A
B 55 2 C
C 55 5 B
C 56 2 D
D 66 5 C
D 08 3 E
E 23 3 A
E 08 2 D
F 78 2 A
F 92 3 -
 Finding Routing table for A using
Dijkstra’s algorithm
ARP and RARP
Operation
RARP
 RARP finds the logical address for a
machine that only knows its physical
address
 The RARP request packets are broadcast;
the RARP reply packets are unicast.
 Alternative solution to RARP
◦ BOOTP
◦ DHCP
IPv4
 Packet Size: 64 K

 IP packet of size 1400 bytes is to be

transferred over a link layer whose MTU is
1000 bytes. What will be values of fragment,
Offset and Flag related to fragmentation for
all the fragments produced.

 [1][0][1],
 [2][1000][0],