Unit-3 Network Layer

Network Layer - design issues

The network layer or layer 3 of the OSI (Open Systems Interconnection) model is
concerned delivery of data packets from the source to the destination across multiple
hops or links. It is the lowest layer that is concerned with end − to − end transmission.
The designers who are concerned with designing this layer needs to cater to certain
issues. These issues encompasses the services provided to the upper layers as well as
internal design of the layer.
The design issues can be elaborated under four heads −
 Store − and − Forward Packet Switching
 Services to Transport Layer
 Providing Connection Oriented Service
 Providing Connectionless Service

Store − and − Forward Packet Switching

The network layer operates in an environment that uses store and forward packet
switching. The node which has a packet to send, delivers it to the nearest router. The
packet is stored in the router until it has fully arrived and its checksum is verified for error
detection. Once, this is done, the packet is forwarded to the next router. Since, each
router needs to store the entire packet before it can forward it to the next hop, the
mechanism is called store − and − forward switching.

Services to Transport Layer

The network layer provides service its immediate upper layer, namely transport layer,
through the network − transport layer interface. The two types of services provided are −
 Connection − Oriented Service − In this service, a path is setup between the source
and the destination, and all the data packets belonging to a message are routed
along this path.
 Connectionless Service − In this service, each packet of the message is
considered as an independent entity and is individually routed from the source to
the destination.
The objectives of the network layer while providing these services are −
 The services should not be dependent upon the router technology.
 The router configuration details should not be of a concern to the transport layer.
  A uniform addressing plan should be made available to the transport layer, whether
the network is a LAN, MAN or WAN.

Providing Connection Oriented Service

In connection − oriented services, a path or route called a virtual circuit is setup between
the source and the destination nodes before the transmission starts. All the packets in the
message are sent along this route. Each packet contains an identifier that denotes the
virtual circuit to which it belongs to. When all the packets are transmitted, the virtual circuit
is terminated and the connection is released. An example of connection − oriented service
is MultiProtocol Label Switching (MPLS).

Providing Connectionless Service

In connectionless service, since each packet is transmitted independently, each packet
contains its routing information and is termed as datagram. The network using datagrams
for transmission is called datagram networks or datagram subnets. No prior setup of
routes are needed before transmitting a message. Each datagram belong to the message
follows its own individual route from the source to the destination. An example of
connectionless service is Internet Protocol or IP.

Example Protocols (IPv4)

The network layer is responsible for carrying data from one host to another. It provides
means to allocate logical addresses to hosts, and identify them uniquely using the same.
Network layer takes data units from Transport Layer and cuts them in to smaller unit
called Data Packet.
Network layer defines the data path, the packets should follow to reach the destination.
Routers work on this layer and provides mechanism to route data to its destination.
A majority of the internet uses a protocol suite called the Internet Protocol Suite also known as
the TCP/IP protocol suite. This suite is a combination of protocols which encompasses a number
of different protocols for different purpose and need. Because the two major protocols in this
suites are TCP (Transmission Control Protocol) and IP (Internet Protocol), this is commonly
termed as TCP/IP Protocol suite. This protocol suite has its own reference model which it follows
over the internet.

Internet Protocol Version 4 (IPv4)

Internet Protocol is one of the major protocols in the TCP/IP protocols suite. This protocol
works at the network layer of the OSI model and at the Internet layer of the TCP/IP
model. Thus this protocol has the responsibility of identifying hosts based upon their
logical addresses and to route data among them over the underlying network.
IP provides a mechanism to uniquely identify hosts by an IP addressing scheme. IP uses
best effort delivery, i.e. it does not guarantee that packets would be delivered to the
destined host, but it will do its best to reach the destination. Internet Protocol version 4
uses 32-bit logical address.

IPv4 - Packet Structure

Internet Protocol being a layer-3 protocol (OSI) takes data Segments from layer-4
(Transport) and divides it into packets. IP packet encapsulates data unit received from
above layer and add to its own header information.
(Transport) and divides it into packets. IP packet encapsulates data unit received from
above layer and add to its own header information.
The encapsulated data is referred to as IP Payload. IP header contains all the necessary
information to deliver the packet at the other end.

 Version − Version no. of Internet Protocol used (e.g. IPv4).

 IHL − Internet Header Length; Length of entire IP header.
 DSCP − Differentiated Services Code Point; this is Type of Service.
 ECN − Explicit Congestion Notification; It carries information about the congestion
seen in the route.
 Total Length − Length of entire IP Packet (including IP header and IP Payload).
 Identification − If IP packet is fragmented during the transmission, all the
fragments contain same identification number. to identify original IP packet they
belong to.
 Flags − As required by the network resources, if IP Packet is too large to handle,
these ‘flags’ tells if they can be fragmented or not. In this 3-bit flag, the MSB is
always set to ‘0’.
 Fragment Offset − This offset tells the exact position of the fragment in the
original IP Packet.
 Time to Live − To avoid looping in the network, every packet is sent with some
TTL value set, which tells the network how many routers (hops) this packet can
cross. At each hop, its value is decremented by one and when the value reaches
zero, the packet is discarded.
 Protocol − Tells the Network layer at the destination host, to which Protocol this
packet belongs to, i.e. the next level Protocol. For example protocol number of
ICMP is 1, TCP is 6 and UDP is 17.
 Header Checksum − This field is used to keep checksum value of entire header
which is then used to check if the packet is received error-free.
 Source Address − 32-bit address of the Sender (or source) of the packet.
 Destination Address − 32-bit address of the Receiver (or destination) of the
packet.
 Options − This is optional field, which is used if the value of IHL is greater than 5.
These options may contain values for options such as Security, Record Route,
Time Stamp, etc.
Routing -
principles/issues

 Routing
 The process of moving a packet of data from source to destination in network
is called routing.
 Routing is usually performed by a dedicated device called a router, Routing is
a key feature of the Internet because it enables messages to pass from one
computer to another and hence reach the destination.
 Each intermediary computer performs routing by passing along the message
to the next computer.
 It also analyze routing table to determine the best path.
 Routing occurs at a higher level where the software component is involved. So
routing performs more complex analysis to determine the best path for the
packet.
 The primary function of a router is to forward a packet toward its destination
network, which is the destination IP address of the packet.
 To do this, a router needs to search the routing information stored in its routing
table. Routing table and routing protocols are key elements for routing.
 A routing table is a data table stored in a router or a networked computer that
lists the routes to particular network destinations.
 The routing table contains information about the topology of the network
immediately around it.
 The construction of routing tables is the primary goal of routing protocols.
 A routing table is a data file in RAM that store route information about directly
connected and remote networks.
 The routing table contains network/next hop associations,
 A directly connected network is a network that is directly attached to one of the
router interfaces.
 A remote network is a network that is not directly connected to the router. In
other words, a remote network is a network that can only be reached by
sending the packet to another router.
 The routing table can be either static or dynamic.
 Static routes are entered manually. A static routing table can be used in an
internet that does not change very often, or in an experimental internet for
troubleshooting. It is poor strategy to use a static routing table in a big internet
such as the internet.
 Dynamic routes are automatically entered as the data packets arrive. The
routers in a big internet such as the Internet need to be updated dynamically
for efficient delivery of the IP packets.
 Routing protocols
 To fulfill the demand of dynamic routing for today's internet, routing protocols
have en created.
 A routing protocol is a combination of rules and procedures that let routers in
the internet inform each other of changes. They also combine information
received from other routers.
Routing protocol is divided into the two part unicast protocol and multicast protocol

 Unicasting Protocol
There are three unicast protocol.
1. Distance vector Routing. (RIP)
2. Link state Routing (OSPF).
3. Path vector Routing (BGP).
1. Distance vector Routing. (RIP)
 Distance vector routing is the routing technique in which the least-cost route
between any two nodes is the route with minimum distance.
 Each node maintains a table of minimum distances to every node.
 Distance vector routing algorithms operate by having each router maintain a
table giving the best known distance to each destination and which line to use
to get there.
 At the beginning, each node can know only the distance between itself and its
immediate neighbours.
 But the table is updated by exchanging information with the neighbours.
 Each node shares its routing table with its immediate neighbours periodically
and when there is a change (triggered).
 Updating rule:
 Choose the smaller cost. If it is same then keep old one.
 It the next-node entry is the same, the receiving node chooses the new row.
 Distance vector routing works in theory, but has a serious drawback in practice.
Although it converges to the correct answer, it may be done slowly.
 It has a count-to-Infinity problem. No router ever has a value more than one
higher than the minimum of all its neighbours.
 Gradually, all the routers work their way up to Infinity, but the number of
exchanges required depends on the numerical value used for infinity.
 One of the solutions to this problem is split horizon algorithm.
 Split horizon: Instead of flooding the table through each interface, each node
sends only part of its table through each interface. Node B eliminates the last
line of its routing table before it sends it to A.
 Routing Information Protocol (RIP)
 The Routing Information Protocol (RIP) is an intra-domain (interior) routing
protocol.
 It is a very simple protocol based on distance vector routing.
  RIP implements distance vector routing directly with some considerations.
 Metric is simple, a hop count. The distance is defined as the number of links to
reach the destination.

Figure 5.5.1 RIP

(Image Source: [Link] )
 The RIP routing table contain 3 pieces of information.
 Network address of destination, the shortest distance to reach the destination
in hop count and the IP address of the next hop to which the packet should be
forwarded to reach its destination.
2. Link state Routing (OSPF)
 Link state routing has a different philosophy from that of distance vector routing In
link state routing, each node has the entire topology of the domain the list of nodes
and links, how they are connected including type, cost, and condition of the links
(up or down).
 The node can use the Dijkstra algorithm to build a routing table.
 Each rod has partial knowledge: it knows the state (type, condition, and cost) of its
links.

 The whole topology can be compiled from the partial knowledge of each node.
Figure

 Open Shortest Path First (OSPF)

 The Open Shortest Path First (OSPF) protocol is an intra-domain routing
protocol Based on link state routing.
 To handle routing efficiently and in a timely manner, OSPF divides an
autonomous system into area.
 Area is a collection of network, hosts, and routers al contained within an AS.
 AS can also be divided into many different areas.
 Each area has an Area ID.
 Among the areas inside an AS there is a special area called the backbone.
 The backbone serves as a Primary Area, and other Areas as Secondary Areas.
All of u Areas inside an AS must be connected to the backbone.
 The Routers inside the backbone are called Backbone Routers. If, due to some
problem, the connectivity between a backbone and an area is broken, a Virtual
Link between Routers must be created by the Administrator to allow the
continuity of the function.
 Each area has an At Identification. The Area ID of the back bone is "Zero".
 The OSPF Protocol allows the Administrator to assign a cost, called the
METRIC, to each ROUTE based on the type of service required (for example
BW, minimum delay maximum throughput etc.).
 In fact a Router can have multiple routing tables based on different TOS (Types
of Service) required.
  OSPF defines four types of links (networks): point-to-point, transient, stub, and
virtual.
 There are five types of OSPF packets: Hello, database description, Link state
request, Link state update and Link state acknowledge.

Distance Vector Algorithm

In distance-vector routing (DVR), each router is required to inform the topology changes
to its neighboring routers periodically. Historically it is known as the old ARPNET routing
algorithm or Bellman-Ford algorithm.

How the DVR Protocol Works

 In DVR, each router maintains a routing table. It contains only one entry for each router.
It contains two parts − a preferred outgoing line to use for that destination and an
estimate of time (delay). Tables are updated by exchanging the information with the
neighbor’s nodes.
 Each router knows the delay in reaching its neighbors (Ex − send echo request).
 Routers periodically exchange routing tables with each of their neighbors.
 It compares the delay in its local table with the delay in the neighbor’s table and the cost
of reaching that neighbor.
 If the path via the neighbor has a lower cost, then the router updates its local table to
forward packets to the neighbor.
Example − Distance Vector Router Protocol
In the network shown below, there are three routers, A, B, and C, with the following
weights − AB =2, BC =3 and CA =5.
Step 1 − In this DVR network, each router shares its routing table with every neighbor.
For example, A will share its routing table with neighbors B and C and neighbors B and
C will share their routing table with A.
Form A A B C

A 0 2 3

Form B A B C

B 2 0 1

Form C A B C

C 3 1 0
Step 2 − If the path via a neighbor has a lower cost, then the router updates its local table
to forward packets to the neighbor. In this table, the router updates the lower cost for A
and C by updating the new weight from 4 to 3 in router A and from 4 to 3 in router C.

Form A A B C

A 0 2 3

Form B A B C

B 2 0 1

Form C A B C

C 3 1 0
Step 3 − The final updated routing table with lower cost distance vector routing protocol
for all routers A, B, and C is given below −
Router A
Form A A B C

A 0 2 3

B 2 0 1

C 3 1 0

Router B
Form B A B C

A 0 2 3

B 2 0 1

C 3 1 0

Router C
Form C A B C

A 0 2 3

B 2 0 1

C 3 1 0

[Link]
Link State Routing
Link state routing is a technique in which each router shares the knowledge of its
neighborhood with every other router in the internetwork.

The three keys to understand the Link State Routing algorithm:

o Knowledge about the neighborhood: Instead of sending its routing table, a router sends
the information about its neighborhood only. A router broadcast its identities and cost of
the directly attached links to other routers.
o Flooding: Each router sends the information to every other router on the internetwork
except its neighbors. This process is known as Flooding. Every router that receives the
packet sends the copies to all its neighbors. Finally, each and every router receives a copy
of the same information.
o Information sharing: A router sends the information to every other router only when the
change occurs in the information.

Link State Routing has two phases:

Reliable Flooding
o Initial state: Each node knows the cost of its neighbors.
o Final state: Each node knows the entire graph.

Route Calculation
Each node uses Dijkstra's algorithm on the graph to calculate the optimal routes to all
nodes.

o The Link state routing algorithm is also known as Dijkstra's algorithm which is used to find
the shortest path from one node to every other node in the network.
o The Dijkstra's algorithm is an iterative, and it has the property that after kth iteration of the
algorithm, the least cost paths are well known for k destination nodes.

Let's describe some notations:

 o c( i , j): Link cost from node i to node j. If i and j nodes are not directly linked, then c(i , j)
= ∞.
o D(v): It defines the cost of the path from source code to destination v that has the least
cost currently.
o P(v): It defines the previous node (neighbor of v) along with current least cost path from
source to v.
o N: It is the total number of nodes available in the network.

Algorithm
Initialization
N = {A} // A is a root node.
for all nodes v
if v adjacent to A
then D(v) = c(A,v)
else D(v) = infinity
loop
find w not in N such that D(w) is a minimum.
Add w to N
Update D(v) for all v adjacent to w and not in N:
D(v) = min(D(v) , D(w) + c(w,v))
Until all nodes in N

In the above algorithm, an initialization step is followed by the loop. The number of times
the loop is executed is equal to the total number of nodes available in the network.

32.3M

740

Features of Java - Javatpoint

Let's understand through an example:

In the above figure, source vertex is A.

Step 1:

The first step is an initialization step. The currently known least cost path from A to its
directly attached neighbors, B, C, D are 2,5,1 respectively. The cost from A to B is set to 2,
from A to D is set to 1 and from A to C is set to 5. The cost from A to E and F are set to
infinity as they are not directly linked to A.

Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)

1 A 2,A 5,A 1,A ∞ ∞

Step 2:

In the above table, we observe that vertex D contains the least cost path in step 1.
Therefore, it is added in N. Now, we need to determine a least-cost path through D vertex.

a) Calculating shortest path from A to B

1. v = B, w = D
2. D(B) = min( D(B) , D(D) + c(D,B) )
3. = min( 2, 1+2)>
4. = min( 2, 3)
5. The minimum value is 2. Therefore, the currently shortest path from A to B is 2.

b) Calculating shortest path from A to C

1. v = C, w = D
2. D(B) = min( D(C) , D(D) + c(D,C) )
3. = min( 5, 1+3)
4. = min( 5, 4)
5. The minimum value is 4. Therefore, the currently shortest path from A to C is 4.</p>

c) Calculating shortest path from A to E

1. v = E, w = D
2. D(B) = min( D(E) , D(D) + c(D,E) )
3. = min( ∞, 1+1)
4. = min(∞, 2)
5. The minimum value is 2. Therefore, the currently shortest path from A to E is 2.
Note: The vertex D has no direct link to vertex E. Therefore, the value of D(F) is infinity.

Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

Step 3:

In the above table, we observe that both E and B have the least cost path in step 2. Let's
consider the E vertex. Now, we determine the least cost path of remaining vertices through
E.

a) Calculating the shortest path from A to B.

1. v = B, w = E
2. D(B) = min( D(B) , D(E) + c(E,B) )
3. = min( 2 , 2+ ∞ )
4. = min( 2, ∞)
5. The minimum value is 2. Therefore, the currently shortest path from A to B is 2.

b) Calculating the shortest path from A to C.

1. v = C, w = E
2. D(B) = min( D(C) , D(E) + c(E,C) )
3. = min( 4 , 2+1 )
4. = min( 4,3)
5. The minimum value is 3. Therefore, the currently shortest path from A to C is 3.

c) Calculating the shortest path from A to F.

1. v = F, w = E
2. D(B) = min( D(F) , D(E) + c(E,F) )
3. = min( ∞ , 2+2 )
4. = min(∞ ,4)
5. The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

Step 4:

In the above table, we observe that B vertex has the least cost path in step 3. Therefore, it
is added in N. Now, we determine the least cost path of remaining vertices through B.

a) Calculating the shortest path from A to C.

1. v = C, w = B
2. D(B) = min( D(C) , D(B) + c(B,C) )
3. = min( 3 , 2+3 )
4. = min( 3,5)
5. The minimum value is 3. Therefore, the currently shortest path from A to C is 3.

b) Calculating the shortest path from A to F.

1. v = F, w = B
2. D(B) = min( D(F) , D(B) + c(B,F) )
3. = min( 4, ∞)
4. = min(4, ∞)
5. The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

4 ADEB 3,E 4,E

 Step 5:

In the above table, we observe that C vertex has the least cost path in step 4. Therefore,
it is added in N. Now, we determine the least cost path of remaining vertices through C.

a) Calculating the shortest path from A to F.

1. v = F, w = C
2. D(B) = min( D(F) , D(C) + c(C,F) )
3. = min( 4, 3+5)
4. = min(4,8)
5. The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

4 ADEB 3,E 4,E

5 ADEBC 4,E
Final table:
Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

4 ADEB 3,E 4,E

5 ADEBC 4,E

6 ADEBCF

Disadvantage:
Heavy traffic is created in Line state routing due to Flooding. Flooding can cause an infinite
looping, this problem can be solved by using Time-to-leave field