Duties of the network layer

Internetworking Addressing Routing Packetizing Fragmenting

Fig.5.2 Duties ofthe network layer
1. Internetworking
This is the main duty of network layer. It provides the logical connection between different
types of network.

2 Addressing
Addressing is necessary to identify each device on the Internet uniquely. This is similar to a
telephone system. The addresses used in the network layer should uniquely and universally define
the connection of a computer.

3Routing
na network, there are multiple roots available from a source to a destination and one of them is
to be chosen. The network layer decides the root to be taken. This is called as routing and it depends
on various criterions.

4. Packetizing
As discussed earlier, the network layer encapsulates the packets received from upper layer
protocol and makes new packets. This is called as packetizing. It is done by a network laver protocol
called IP (Internetworking protocol).
S. Fragmenting
The datagram can travel through different networks. Each router decapsulates the IP datagram
from the received frame. Then the datagram is processed and encapsulated in another trame.
6. Other issues
The other issues which are not directly related to the duties of network laver but need to be
discussed are as under:
(i) Address resolution.
(i) Multicasting.
(i) Routing protocols.
 De ula choose appropriate
idie op
Uperation of others should chosen in such a choose
be way that appropriate paths for
5 2, 1SSUES avoided. overloading of some routers and
nd
RELATED TO NETWORK
LAYER DESIGN
The important network
the internal design of layer design issues include the
subnet. service provided to the
The network
layer has been designed with transport layer and
1) The services the
provided should be
following goals:
service need not be
aware of the independent of the
underlying technology. Users of the
their physical
messages could be transported via implementation of the network
when we consider carrier pigeon. This -for all they know,
networks in
the great design
variety of networks in operation. In thegoal great importance
has
in underdeveloped countries are
the countries like nowhere near the
area of Public
networks,
() The design of the
the U.S. or Ireland. technological prowess of those
layer must not disable
technologies. us from connecting to networks of different
it) The transport layer (that is the host
and different computer) should be shielded from the number,
topologies of the subnets
communication link, it need not know howuser uses. That is, all
that type
that link is made. transport layer wants is a
(iv) Finally, there is a need for some uniform
() With these goals in addressing scheme for network addresses.
mind, two different types of services
(a) Connection oriented Network Services emerged as follows:
(b) Connectionless Network Services.
A connection-oriented service is one in which the
user is
To communicate, the user requests a connection, then uses given a reliable end to end connection.
then closes the the connection to his hearts content, and
connection. A
telephone call is the classic
In a connectionless service, the user simply bundles his example of a connection oriented service.
and then sends it off, in the information together, puts an address on it,
hope that it will reach its destination. There
bundle will arrive. Therefore, a connectionless is no
service is one reminiscent of theguarantee
that the
letter is sent, that is,' put in the
post box. It is then in the post network where it postal system. A
gets bounced
hopefully will leave the network in the correct place, that is, in the addressee's letter box. We and
never be totally sure that the letter will can
arrive, but we know that there is a high
will, and so we place our trust in the postal network. probability that it

5.2.1. Services Provided to the Transport Layer

The network layer services are designed to achieve the
following goals
(i) The services should be independent of the subnet technology.
(i) Transport layer should be shielded from the rnumber, type and topology of the subnet
(i) The network address which is made available to the transport layer must use a uniform
nubmerging plan.
 N U N J

HHHI

N
N w Un
 248 Computer Networks

Each packet has a physical device address as well as DOYOU

KNOw?
data.
logical network address. The network address allows routers With a datagram subnet, the
to calculate the optimal push to a workstation or computer congestion avoidance is more
routes
Koute discovery is the process of finding the possibletables to difficult.
through the înternetwork and then building routing
store that information. The two methods of route discovery
are as under:
) Distance vector routing
ii) Link state routing.

Bus

Router
Router
Ring Ring

I Router

Router Ring
Bus

Fig. 5.3 (6) Routers in an Internet

Important Point:
Routers work at the network layer of the OSI model. The cost of a route can be defined in several terms:
a time estimate, a distance estimate or an estimate that includes monetary terms. In distance vector
routing, each router advertises the presence periodically to other routers on the network. Link state
routers broadcast their complete routing tables only at startup and at certain intervals. Dynamic route
selection permits routers to constantly adjust o changing network conditions. With static route selection,
packets alwaysfollow apre-determined path.
5.4. ROUTING ALGORITHMS
(Expected)
One of the important functions of the network layer is to route the
to the destination machine. The major area of network layer
packets from the source machirne
choose the routes and the data structures which are used.
design includes the algorithms which
Routing algorithm
laver software. It is responsible for deciding the output line over which
is a
a packet is part
of network
to be sent. Sucn
a decision is dependent on whether the subnet is a virtual
circuit or it is datagram switching.
5.4.1. Desired Properties of a Routing Algorithm
There are certain desirable properties of a routing algorithm as under:
) Correctness. (ii) Robustness.
(ii) Stability. (iv) Fairness and
(o) Optimality.
 249
Network Layer
DO YOU KNOW?
54.2. Types of Routing Algorithms
Routing algorithms can be divided into two groups as
The routing algorithm is
that part
software
under:
of the network layer
which
1. Nonadaptive algorithms responsible for deciding
2. Adaptive algorithms. output line an incoming packet
should be transmitted on.
1. Nonadaptive algorithms
measure-ment or estimation
For this type of algorithms, the routing decision is not based on the
off line and it is
of current traftic and topology. However, the choice of the route is done in advance,
downloaded to the routers. This is called as static routing.

2. Adaptive algorithms
For these algorithms, the routing decision can be changed if there are any changes in topology
discuss various staticC
or traffic etc. This is called as dynamic routing. In the following sections, let us
and dynainic algorithms.
3.Optimality principle
A general statement about optimality is called as optimality principle. It states thatif router/in
also falls along the
on the optimal path from router I to router K, then the optimal path from J to K
route as r2.
same route. This be elaborated as, call the part of the route from I to J as r1 and rest of
can
with r1 to improve the route
Ifa route better than r2 existed from J to K, it could be concatenated
from I to K, contradicting our statement that r1 r2 is optimal.
4. Sink tree
called sink tree and
A set of optimal routes from all the sources to a given destination form a tree
it is shown in figure 5.4. Note that a sink tree need not be unique. Other trees with the same path
are supposed to discover and use the sink trees
for
lengths may also exist. All the routing algorithms
all routers. In the sink tree of figure 5.4, the distance metric is the numbers of hops. In figure 5.4 (b),
a sink tree for router B has been shown. The paths from B to every router with minimum member of

hops.

G G
H
(a) A subnet (b) A sink tree for router B
Fig. 5.4.

5.5. STATIC ALGORITHMS (uP. Tech, Sem. Exam, 2005-06) (10 marks)

The examples of static algorithms may be listed as under

() Shortest path routing. (i) Flooding.
(ii) Flow based routing.

5.5.1. Shortest Path Routing

1. Definition
This algorithm is based on the simplest and most widely used principle. How a graph of subnet
 250
Computer Networks
is built in which each node
representing the router and each DOYOU KNOW?
arc representing a link or a communication line. Hence, as to
choose a path between a The routing algorithm should be
pair of routers, this algorithm simply
finds the shortest path between them. able to cope with changes in the
topology and traffic without
2. How to Decide the Shortest Path
requiring all jobs in all hosts to be
One
way of measuring the path length is the number of aborted aand the network to be
hops. Another way (metric) is the geographical distance in rebooted everytime some router
kilometres. Some other metrics are also possible. For example, crashes.
we can label each arc (link) with the mean queueing and
transmission delay and obtain the shortest path as the fastest path.
3. Labels on the Arcs
The labels on the arcs can be compared as a function of distance bandwidth, average traffic,
mean queue length, cost of communication, measured delays etc. The algorithm weighs various
parameters and computes the shortest path, based on any one or combination of criterions stated
above.
4. Various Shortest Path Algorithms
There are many algorithms for computing the shortest path between two nodes. One of them is
Dijkstra algorithm. The other one is Bellman-Ford algorithm.
5.5.2. Dijkstra's Shortest Path Algorithm
The algorithmic translation of physical process is called Dijkstra's shortest path algorithm.
The algorithm is based on the following observations:
a)The distance from ball1 to ball n cannot decrease after ball n rises from the floor.
(6) Consequently, if we keep track of an estimated distance from ball 1 to ball n, we know that
this estimated distance eventually setles to the shortest distance and that this happens
when the ball rises from the floor.
. Now, here how do we know which ball rises next ? Say that the ball k rises and let d to the
distance from ball 1 to ball k. We update the estimates of the distance from ball 1 to the balls attached
to ball k.
2. If some ball j is not jump yet and is attached to ballk with a string of length s, we replace the
current estimated distance x from 1 to j by the minimum of x and d + s.
3. When we have updated all the neighbours of ball k, we must find the ball that will rise next.
That ball is ball on the floor, say ball p, with the current smallest estimated distance away from ball
1. We can then continue the process with ball p.
4. We find explain the algorithm on the simple network shown in
figure 5.5. The objective is to
find the shortest path from A to all the other nodes. The lengths of the individual links are marked
next to them.
5. On this small network, a simple inspection shows that the shortest path from A to bottom
node has length 5 and goes through the right middle node. Dijkstra's algorithm is systematic
procedure for discovering such a shortest path even in a large network. Next to each node, we mark
the current estimate of the length of the shortest path from A to that node. The symbol o means that
the no path to that node has been found yet.
6. The algorithm starts by considering the node with the smallest label, in this case A. The
algorithm explores the links going out of that node. The left link leads to the left middle node which
can then be reached fromA with a path of length 3,. Accordingly, we reduce thelabel of that node
 Network Layer 251
Geom oo 3. Since, the label is reduced
to
by using that left link out of A, we mark the link as being the
current candidate for the shortest pathto the left middle node.
7.A similar step is performed for the
right link
Out of A. We then shade node A to indicate that A
we have examined all its
outgoing links. At the 3
next step, we examine the unshaded node with
the current smallest label. That node is the left 3
middle node. We examine the outgoing link of that
node and find a candidate shortest path to the
3 Reay
bottom node with length 3 +3 =6. We shade that
node and then examine the unshaded node with B B
the smallest label; the right middle node.
8. With the link out of that node, we find a
shortest path to the bottom node.
Accordingly, we
unmark the link from the left middle node to the
bottom node because we know that the link is not
3
(po)C po)
(Reay
on the shortest
path to the bottom node.
9. In addition, we mark the link from the
right
(pe)
middle node to the bottom node. Since the bottomn
node has no outgoing link, the B Os
algorithm Fig. 5.5 Steps to Dijkstra's algorithm
terminates. The marked links define the shortest
paths from A to the nodes.
10. Next we illustrate Dijkstra's shortest path algorithm with the example shown in figure 5.5.
We start with node A as the source and we mark each node with an estimated distancefrom A to the
are infinite, except that of node A which is 0. The first node to rise from
node. The initial estimates
the floor is node A.
11. We shade that node A to remember that it is off the floor and we update the estimates of all
the neighbours B, C, D of A. For instance, we replace the current infinite estimate of B by the sum of
the estimate of node A (equal to 0) plus the length 4 of the link from A to B.
12. The new estimate (4,3, 2) are underlined in the second part of the figure 5.6. At that point, we
determine the unshaded node with the smallest estimate. That node is node D and is therefore the
next node to rise from the floor. We shade that node D.
Note that all the links from node A to its neighbours are colored red to remember that these are
candidates for shortest paths from A to other nodes since these links have provided us with the
smallest estimates of distances to the nodes B, C, D so far.
13. In the third part of the figure 5.6, we explore the neighbours of node D and we update their
estimates and color the links from D to these neighbours red.
14. In the fourth part of the figure 5.6 we have located node C as the unshaded node with the
smallest estimate; we shade C and we explore its neighbours and update their estimates.
Note that the link CF produces a smaller estimate (5) for node F. Accordingly, we change the link
DF from red to black we colour the link CF as red.
15. In the last part of the figure 5.6, we locate the unshaded node B with the smallest estimate;
we shade node B and update the estimates of its neighbours. Note that the link fromB to D does not
reduce the estimate of node D because 4 +4>2. However the link from B to E reduces the estimate
of E because 4 +1 <6.
 4

4 4
B

2 6
8
4
/2 2

2 6
4

Fig.5.6 Illustration of Dijkstra's algorithm

16. Consequently, reflect this reduced estimate, we color the link from B to E green and we
change the link from D to E from red to black. Indeed, the link from D to E cannot be on a shortest
path fromA to E since it yields a longer path than a path that reaches E via link BE. The left most part
of the figure 5.6 shows the shortest paths.

5.5.3. Flooding
1. Basic Concepts
DO YOU KNOW?
This is another static algorithm.
In this algorithm, every Flooding always chooses the
incoming packet is sent out an every outgoing line except the shortest path because it chooses
line on which it has arrived. One disadvantage of floodingis every possible path in parallel.
that it generate a large number of duplicate packets. In fact, it Consequently, on other algorithm
produces infinite number of duplicate packets unless we can produce a shorter delay if we
somehow damp the process. There are various damping ignore the overhead generated by
techniques as under: the flooding process itself.

i) Usinga hop counter

i) To keep a track of which packets have been flooded.
(ii) Selective flooding.
 o perverd endiess copws of packets circulating ndefinitely through the network a hop count
e ued to supprese onw ards transemission of packets after a number of hops exceeding the
eworh diarreter Te destination must be prepared to receive multipie copies of an ncoming paket
fudirg, has two interesting characteristics that arise irom the fact that all possible routes are tred
As
kog, as there ts a route from source to destination, the delivery of the packet is guaranteed
() r e copy of the packet will arrive by the quickest possible route

2Selective Fooding
Thae is slaghty more practical variation of flooding. in this algorithm, every incoming Packet ts
nd sent out on every output line Infact. packet is sent only on those lines which are approximately
going, in the night direction
Applicationsof Flooding
where
Flooding does have much practical applications. But, it is useful in military applications
a large number of routers are blown into pieces at anv
instant. In such applications, robustness of

flooding is very much desirable

chooses the
Special application is in the distributed database applications Flooding always
shortest path so it produces the shortest possible delay

5.5.4. Flow Based Routing

for deciding a route.
This is a static algorithm which uses topology and load condition (traffic)
For example in figure 5.7, there
is always a huge traffic from A
to B. Then, the traffic from A to Take the route
AGEFC
C should not be routed through po instead of ABC
B. Instead route it through ^
AGEFC though it is
even a

longer path than ABC. This

is

called as a flow based routing

It is possible to optimise the Fig. 5.7 Flow based routing
data
routing by analysing the node to the other is known in
it the average traffic from one
flow mathematically. This is possible
in time. The mathematical analysis
advance and it is constant DOYOU KNOW?
Isa d on a given line if
idea that tor the
capcity the and
average
is not practical in most
data flow are known, then. it is possible to calculate
mean Flooding
applications, but it does have
packet delay using the Queuing theory. some uses. For example, in
lines, it is possible to
From the mean delays on all the
tor the whole subnet. To use military applications, where large
cakulate the mean packet delay numbers of routers may be blown
the following information
the technique ot tlow based routing, to bits at any instant, the
should be known in advance: tremendous robustness of
() Subnet topologv. flooding is highly desirable.
() Tratfic matrix.
which specifies capacity ofeach
line.
(2)
Line capacity matrix
ALGORITHMS (u.P. Tech, Sem. Exam, 2005-06)(10 marks)
5.6. DYNAMIC ROUTING
use the
algorithms. But modern computer networks normally
e have disussed the routing static
distance vector routing and
Two dynamic routing algorithms namely
rama routing algorithms.
mA state routing are Popular.
 5.6.1. Distance Vector Routing Algorithm
1. Basic Concepts
in this algorithm, each router maintains a table called vector, such a table gives the best known
alstance to each destination and the information about which line to be used to reach there.

The algorithm is sometimes called by other names such as,

1. Distributed Bellman-Ford routing algorithm
2. Ford-Fulkerson algorithm.
In distance vector routing, each router maintains a routing Kou
table. It contains one entry for each router is the subnet.
This entry has two parts: E G

9 The first part shows the preferred outgoing line to be

used to reach the destination and
(7) Second part gives an estimate of the time or distance
to the destination. Fig. 5.8 A subnet
The metric used can be one of the following:
() Number of hops
(i) Time delay.
(ii) Number of packets in a queue etc.
2. Example of a Subnet
The example of a subnet is shown in figure 5.8 and the routing tables are shown in figure 5,9.
New estimated delay
TO from router I
This shows H Delay Via
that the delay vectors
from A to B is 20 A 8
10 ms
B10 31 B 18
8 10 = 18 ms
c 24 19 31 H
38 8 D
This shows
that the delay
E 12 30 E Two
from A to D is
38ms possible
24 19 F paths
G 16 6 19
G 18 H A
H 19 H

9 8+24 1219
=31 ms
IA
32 ms
IH 2
Delay is Delay is
8 12 Entry corresponds
to shorter delay of
New routing the two
Vectors received table for router I
from 's two
neighbours
Fig. 5.9 Routing tables
The entries in router tables of figure 5.9 are the
boxes of figure 5.9. The entry in the first shaded box
delay vectors. For example, consider the shaded
shows that the delay from A to B is 10 m sec,
whereas the entry in the other shaded box indicates that
the delay from A to D is 38 msec. Let us
consider how router I computes its new route to router G.
between I and G. Figure 5.10 shows the two possible routes
 This is due to a problem called count-to-infinity problem.
(ii) This problem can be solved by using the split horizon algorithm.
(ii) Another problem is that this algorithm does not take the line bandwidth into consideration
when choosing root.
(i) This is a serious problem which led to the replacement of this algorithm by the Link State
Routing algorithm.
5.6.2. Count to Infinity Problem* (u.P. Tech, Sem. Exam, 2006-07, 2007-08) (10 marks)
The distance vector routing works properly theoretically but practically it has a serious
problem.
Although we get a correct answer, we get it slowly. In other words it reacts quickly to good news but
does so leisurely to bad news. Let us consider a router whose best route
A
todestination Xis large. If
on the next
exchange neighbour suddenly reports a short delay X,to the router will switch over
and start using the line to A for sending the traffic to destination X. Thus, in one vector
exchange, the
good news is processed. Let us see how fast does a good news propagate. Let us consider a liner
subnet of figure 5.11 which has five nodes. The delay metric used is the number of
hops. Assume
that A is initially down and that all the other routes know this. Hence, all the routers have recorded
that the delay to A is infinity. When A becomes OK, the other routers come to know about it via the
vector exchanges. Then suddenly a vector exchange at all the routers will take
At the time of first vector
place simultaneously.
exchange, B comes to know that its left neighbour has a zero delay to A. So
as shown in
figure 5.11, B makes an entry in its routing table that A is one hop away to the left. All the
 256
Computer Networks
other routers still think that Ais down. So in the second row of figure 5.11, the entries below
CDE
are , On the second vector
exchange, C comes to know that B has a path of 1 hop length to A, so C
updates its routing table and indicates a path of 2 hop length. But, D and E do not change their table
entries.

A is
down This shows that delay to A is
Initially (or A is oo hops away to left)

These o After 1 exchange

are number
of hops
A is one hop 1
away to left co After 2 exchanges
-A is 2 hops away to left
2 3 o After 3 exchanges

1 2 3 4 After 4 exchanges

Fig.5.11.

1 2 3 4 Intially 4+All routers are initially ok

3 3 4 After 1 exchange

3 3 4 After 2 exchanges

5 4 After 3 exchanges

5 6 After 4 exchanges

7 6 7 6 After 5 exchanges

8 8 After 6 exchanges

Fig. 5.12.
So, after the second vector exchange the entries in the third row of figure 5.11 are:

B C D

1 2 0 After 2 exchanges
We
Similarly, D and E will update their routing tables after 3 and 4 exchanges respectively. So,
conclude that the good news of A has recovered has spread at a rate of one hop per exchange

Explanation of figure 5.12

and E have
Now, let us consider figure 5.12. Here initially all routers are OK. The routers B, C, D
distances of 1, 2,3 and 4 respectively to A. So, the first row of figure 5.12 is as follows:

1 2 3 4 Initially - First row of figure 6.12

These are distances

of B,C.D,E to A
 Network Layer 257
Now. let us
imagine that suddenly A
nacket exchange B does not hear goes down or line
between A and B is cut. At the first
anything
iength toA. poor B does not understand that
2 But from A (because A is
down). But C says "Ihave a path of
reach A with this path is through B itself. So, B thinks that it can
via
C a
path length 3. (B to Cl
routing table. hop and Cto A 2
their entries. So, the hops)
But, D and E do not so
it accordingly upaates it
follows update second row of
figure 5.12 lookS as
C
3 4 Initially
2 4 After 1 exchange

Updated No change
entry
On the second
exchange,
C realizes that both its
neighbours
(B and D) claim to have a path ot
length 3 to A. So, picks one of them at random and
it
makes its
in row 3 of new distance to A as 4. This is shown
figure
5.12. It is repeated below:
B

2 4

3 3 After 2 exchanges

C
changes its entry
Similarly, the other routers keep updating their tables after every exchange. It is expected that
finally we should get in the router tables of B, C, D and E indicating that A is down. We do reach
o

this state at the end in figure 5.12 but after a

very long time. The conclusion is bad news propagates
slowly. This problem is called as count-to-infinity problem. The solution to this
the
split horizon algorithm. problem is to use
The Split Horizon Algorithm
This algorithm works the same way as distance vector
not reported on the line that packets for X are sent on.
routing, except that the distance to X is
5.6.3. Link State Routing
1. Definition
Distance vector routing was used in ARPANET upto 1979. After that it was replaced by the link
state routing. Variants of this algorithm are now widely used. The link state routing is simple and
each operations
routerhas
to perform the following five
2. Router operations
)Each router should discover its neighbours and obtain their networkaaddresses.
(i7) Then it should measure the delay or cost to each ofthese neighbours.
(u) It should construct a packet containing the network address and the delays of all the
neighbours.
(ir) Send this packet to all other routers.
()Computethe shortest path to every otherrouter.