NETWORK LAYER

PRESENTED BY
MS. P ANUSHA,
ASST PROF, CSE(AIML)
 Network Layer Design Issues
 1. Store-and-forwardpacket switching
 2. Services provided to transport layer
 3. Implementation of connectionless service
 4. Implementation of connection-oriented
service
 5. Comparison of virtual-circuit and
datagram networks
Store-and-forward packet switching
 The host sends the packet to the nearest router, either on its
own LAN or over a point-to-point link to the ISP (Internet
Service Provider).
 This packet is stored there until it has fully arrived once
the link is fully processed by verifying the checksum then
it is forwarded to the next router till it reaches the
destination.
 This mechanism is called “Store and Forward packet
switching.”
Services provided to 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.
 Implementation of connectionless
service
 Packet are termed as “datagrams” and corresponding subnet as
“datagram subnets”. When the message size that has to be
transmitted is 4 times the size of the packet, then the network
layer divides into 4 packets and transmits each packet to router
via. a few protocol.
 Each data packet has destination address and is routed
independently irrespective of the packets.
 Implementation of connection
oriented service
 To use a connection-oriented service, first we establishes a
connection, use it and then release it with routers.
 Here, the data packets are delivered to the receiver in the same
order in which they have been sent by the sender.
 It can be done in either two ways :
1. Circuit Switched Connection
2. Virtual Circuit Switched Connection
Comparison of virtual-circuit and
datagram networks
 Routing Algorithms
 The main function is to route packets from the source machine to the
destination machine.
 Routing algorithm is software responsible for deciding which output line
an incoming packet should be transmitted on.
 Network connection services may be Datagram or Virtual Circuit
networking for transmission of information.
 Router is a networking device that forwards data packets and a Routing
Table is a set of rules, often viewed in table format, that is used to
determine where data packets traveling over an Internet Protocol (IP)
network will be directed.
 There are two processes inside router:
a) One of them handles each packet as it arrives, looking up the
outgoing line to use for it in the routing table (FORWARDING)
b) The other process is responsible for filling in and updating the
routing tables. That is where the routing algorithm comes into play
(ROUTING)
 Certain properties are desirable in a routing algorithm: correctness,
simplicity, robustness, stability, fairness, and efficiency.
Types of Routing
algorithms

Adaptive Routing Non- Adaptive Routing

algorithm algorithm
Difference between Routing, Forwarding &
Switching
 Adaptive Routing algorithms
• An adaptive routing algorithm is also known as dynamic routing
algorithm.
• This algorithm makes the routing decisions based on the topology
and network traffic.
• The main parameters related are hop count, distance and estimated
transit time.
• It constructs the routing table based on the network conditions.
• Categories - Centralized, isolation and distributed algorithm.
• Adaptive Routing algorithms are more complex.
Non-Adaptive Routing algorithms
 Non Adaptive routing algorithm is also known as a static routing
algorithm.
 When booting up the network, the routing information stores to the
routers.
 It do not take the routing decision based on the network topology or
network traffic.
 It constructs the static table to determine which node to send the packet.
 Categories - flooding and random walks.
 Non-Adaptive Routing algorithms are simple.
 Different Routing Algorithms
 Optimality principle
 Shortest path algorithm
 Flooding
 Distance vector routing
 Multicasting
 Broadcasting
 Link state routing
 Hierarchical Routing
 Optimality Principle
 One can make a general statement about optimal routes without regard
to network topology or traffic is known as the optimality principle.
 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.
 The goal of all routing algorithms is to discover and use the sink trees
for all routers.
 Shortest Path algorithm (Dijkstra’s)
 The most commonly known shortest-path algorithms i.e. Dijkstra’s
Shortest Path Algorithm which was developed by Dutch computer
scientist Edsger W. Dijkstra in 1956.
 The idea is to build a graph of the subnet, with each node of the graph
representing a router and each arc of the graph representing a
communication line or link.
 To choose a route between a given pair of routers, the algorithm just
finds the shortest path between them on the graph
 The need for Dijkstra’s algorithm arises in many applications where
finding the shortest path between two points is crucial because can work
on both directed graphs and undirected graphs.
 1. Start with the local node (router) as the root of the tree. Assign a
cost of 0 to this node and make it the first permanent node.
 2. Examine each neighbor of the node that was the last permanent
node.
 3. Assign a cumulative cost to each node and make it tentative
 4. Among the list of tentative nodes a. Find the node with the
smallest cost and make it Permanent b. If a node can be reached
from more than one route then select the route with the shortest
cumulative cost.
 5. Repeat steps 2 to 4 until every node becomes permanent
 Flooding
 It is a non-adaptive algorithm or static algorithm.
 When a router receives a packet, it sends a copy of the packet
out on each line (except the one on which it arrived).
 To prevent form looping forever, each router decrements a
hop count contained in the packet header.
 As soon as the hop count decrements to zero, the router
discards the packet.
 All possible routes between Source and Destination is tried.
 Hierarchical routing
 Hierarchical routing is an algorithm for routing packets hierarchically.
 Here the routers are divided into regions. Each router has complete
details about how to route packets to destinations within its own region.
 But it does not have any idea about the internal structure of other
regions.
 So, routers save one record in their table for every other region.
 HRPs are valuable for large networks, as they provide the capability of
organizing network information and reducing the amount of routing
information that should be exchanged between nodes.
Broadcast & Multicast Routing
 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.
 Two dynamic algorithms in particular, distance vector routing and link
state routing, are the most popular.
 Distance vector routing 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 neighbors.
Eventually, every router knows the best link to reach each destination.
 It was the original ARPANET routing algorithm and was also used in the
Internet under the name RIP.
Let's understand a few key points about the distance vector routing
protocol:
- Network Information
- Routing Pattern
- Data Sharing
Bellman-Ford algorithm is defined as:
 Routing table of A Routing table of B

Destination distant Hop Destination distant Hop

A 0 A A 8 A
B 8 B B 0 B
C infinity - C 2 C
D 5 D D infinity D
Routing table of C Routing table of D
Destination distant Hop Destination distant Hop

A infinity - A 5 A
B 2 B B infinity B
C 0 C C 3 C
D 3 D D 0 D
For Router A: neighboring routers B and D New Routing table of A
Destination Vector B Vector D Destination distant Hop
A 8 5 A A 0
B 0 infinity B B 8
C 2 3 C C 8
D infinity 0 D D 5
For Router B: neighboring routers A and C. New Routing table of B

Destination Vector A Vector C Destination distant Hop

A 0 infinity A 8 A
B 8 2 B 0 B
C infinity 0 C 2 C
D 5 3 D 5 C
For Router C: neighboring routers B and D New Routing table of C

Destination Vector B Vector D Destination distant Hop

A 8 5 A 8 D
B 0 infinity B 2 B
C 2 3 C 0 C
D infinity 0 D 3 D
For Router D: neighboring routers A and C New Routing table of D

Destination Vector A Vector C Destination distant Hop

A 0 infinity A 5 A
B 8 2 B 5 C
C infinity 0 C 3 C
D 5 3 D 0 D
Destination Vector B Vector D Destination distant Hop

A 8 5 A 0 A

B 0 5 B 8 B

C 2 3 C 8 D

D 5 0 D 5 D

Destination Vector A Vector C Destination distant Hop

A 0 8 A 8 A

B 8 2 B 0 B

C 8 0 C 2 C

D 5 3 D 5 C
Destination Vector B Vector D Destination distant Hop

A 8 5 A 8 D

B 0 5 B 2 B

C 2 3 C 0 C

D 5 0 D 3 D

Destination Vector A Vector C Destination distant Hop

A 0 8 A 1 A

B 8 2 B 3 C

C 8 0 C 6 C

D 5 3 D 0 D
Note:
• In the distance vector routing protocol, only distance vector information is
exchanged next-hop values are not exchanged.
• while creating a new routing table, only the distance vector information is
shared that to its neighbor which has a direct link. The old router tables are
not taken into consideration only newly updated router information is used.
• The process of updating the routing table keeps on repeating periodically to
update the shortest path in case the link goes down or there is a topology
change.
• Distance vector routing faces an account-to-infinity problem.
 Congestion Control
 Congestion is an important issue that can arise in packet switched
network.
 Too many packets present in the network causes packet delay and loss that
degrades performance. This situation is called Congestion.
 The network and transport layers share the responsibility for handling
congestion.
 Due to congestion, the network response time and performance decreases,
and increases time delay & retransmission.
 However, the most effective way to control congestion is to reduce the load
that the transport layer is placing on the network. This requires the network
and transport layers to work together.
 A system called congestion control regulates the flow of data packets into the
network, allowing for more efficient use of a shared network infrastructure
and preventing congestive collapse.
 Congestion Control Algorithm
 Congestion Control is a mechanism that controls the entry of
data packets into the network, enabling a better use of a shared
network infrastructure and avoiding congestive collapse.
 Congestive Control Algorithms are implemented at the TCP
layer as the mechanism to avoid congestive collapse in a
network.
 Congestive Control Algorithms are as follows –
Leaky Bucket Algorithm
Token Bucket Algorithm
 Leaky Bucket Algorithm
 The leaky bucket algorithm discovers its use in the context of network
traffic shaping or rate-limiting.
 With the help of this method, the network’s transmission rate may be
managed, and burst traffic can be turned into a constant stream.
 When compared to the leaky-bucket algorithm, the drawbacks include the
ineffective utilization of available network resources.
 The bandwidth and other extensive network resources are not being
utilized efficiently.
 If the bucket (buffer) overflows then packets are discarded.
Example:
 Think of a bucket that has a tiny hole in the bottom. No matter how quickly
water enters the bucket, the pace at which it exits remains constant. Water
that is added after the bucket is full flows over the edges and is lost.
 Token Bucket Algorithm
 The output architecture of the leaky bucket method is stiff at an average rate
irrespective of the bursty traffic.
 When there are significant bursts, certain applications allow the output to
accelerate.
 A token bucket approach is thus useful for rate-limiting or filtering network
traffic.
 Tokens are in the bucket. Each token designates a packet of a specific size. To
allow sharing of a packet, tokens in the bucket are erased.
 When tokens are displayed, a flow of transmit traffic also does so.
 If there is no token, no flow will send packets. As a result, a flow transfers
traffic in good tokens in the bucket up to its peak burst rate.
Effects of Congestion Control in Computer
Networks
 Improved Network Stability
 Reduced Latency and Packet Loss
 Enhanced Throughput
 Fairness in Resource Allocation
 Better User Experience
 Quality of Service (QoS)
 Quality of service mechanisms let a network with less capacity meet
application requirements just as well at a lower cost.
 An easy solution to provide good quality of service is to build a
network with enough capacity for whatever traffic will be thrown at
it known as overprovisioning.
 Four issues must be addressed to ensure quality of service:
 1. What applications need from the network.
 2. How to regulate the traffic that enters the network.
 3. How to reserve resources at routers to guarantee performance.
 4. Whether the network can safely accept more traffic
 A stream of packets from a source to a destination is called a flow.
 Flow can be connection oriented or connectionless network for
transmission of packets..
 The needs of each flow can be characterized by four primary
parameters: bandwidth, delay, jitter, and loss. Together, these
determine the QoS (Quality of Service) the flow requires.
 Reliability
If there is a lack of reliability then it simply means losing any packet or losing an
acknowledgement due to which retransmission is needed. Reliability becomes
more important for electronic mail, file transfer, and for internet access.
 Delay
Delay in transmission between the source and destination. During audio
conferencing, telephony, video conferencing, and remote conferencing there
should be a minimum delay.
 Jitter
Jitter is basically the variation in the delay for packets that belongs to the same
flow. Higher the value of jitter means there is a large delay and the low jitter
means the variation is small.
 Bandwidth
The different applications need different bandwidth.
 Internetworking
 Numerous protocols are in widespread use across different
networks(LAN, MAN, WAN) in every layer. Here we look at the
issues that arise when two or more networks are connected to form
an internetwork, or more simply an internet.
 The purpose of joining all these networks is to allow users on any of
them to communicate with users on all the other ones.
 When you pay an ISP(Internet Service Provider) for Internet
service, you may be charged depending on the bandwidth of your
line.
How Networks Differ?
 Networks can differ in many ways. Some of the differences, such as different
modulation techniques or frame formats, are internal to the physical and data link
layers.
 How Networks Can Be Connected?
Suppose that the source machine on the 802.11 network wants to send a packet to the
destination machine on the Ethernet network. Since these technologies are different, and
they are further separated by another kind of network MPLS (Multi Protocol Label
Switching), some added processing is needed at the boundaries between the networks
 Tunneling
 Handling the general case of making two different networks interwork is exceedingly
difficult.
 Consider a case ,where the source and destination hosts are on the same type of
network, but there is a different network in between.
 Packet Fragmentation
 Each network or link imposes some maximum size on its packets.
These limits have various causes, among them
1. Hardware (e.g., the size of an Ethernet frame).
2. Operating system (e.g., all buffers are 512 bytes).
3. Protocols (e.g., the number of bits in the packet length field).
4. Compliance with some (inter)national standard.
5. Desire to reduce error-induced retransmissions to some level.
6. Desire to prevent one packet from occupying the channel too long.
 Network layer in the Internet
 The glue that holds the whole Internet together is the network layer protocol, IP
(Internet Protocol).
 IP routers forward each packet through the Internet, along a path from one router
to the next, until the destination is reached.
 Internet Protocol address (IP address) is a set of rules and a method designed to
allow the device to access the internet and serve as a unique identification
medium. An IP address consists of two parts, i.e., the first one is a network
address, and the other one is a host address.
 Versions of IP Address
 To meet the increasing demand of the IP address for network devices, the
original IP version, i.e., IPv4 (IP address version type 4), will not be able to
cover the need of users, so to overcome the situation of IP address
unavailability, IPv6 (IP address version type 6) address were introduced.
 Subnets
 Subnet is the name given to piece of the broken network or can also be called
as the Substitute network is known as Subnet. Subnets are the legal small parts
of IP (Internet Protocol) Addressing process.
 Subnet can divide the network into different parts but all when put together
should perform the same task when done before splitting in to small parts.
 Subnets reduce the need for traffic to use unnecessary routes, which speeds up
the network. To help with the lack of IP addresses on the internet, subnets were
developed.
 Each subnet allows its connected devices to communicate with each other,
while routers are used to communicate between subnets.
 An IP address is divided into two fields: a Network Prefix (also
called the Network ID) and a Host ID. What separates the Network
Prefix and the Host ID depends on whether the address is a Class A,
B or C address.
 What is IPv4?
 It was introduced in 1981 by DARPA. IPv4 addresses are 32-bit integers that have
to be expressed in Decimal Notation.
 It is represented by 4 numbers separated by dots in the range of 0-255, which have
to be converted to 0 and 1, to be understood by Computers.
 Example: 192.168.2.33
IPv4 Header
 What is IPv6?
 IPv6 is based on IPv4 and stands for Internet Protocol version 6. It was first
introduced in December 1995 by Internet Engineering Task Force.
 IPv6 is written as a group of 8 hexadecimal numbers separated by colon (:). It
can be written as 128 bits of 0s and 1s.
 Example: FDEC:BA98:7654:3210:ADEC:BDFF:2990:FFFF
IPv6 Header
 Internet Control Protocols
 IMCP—The Internet Control Message Protocol
 ARP—The Address Resolution Protocol
 DHCP—The Dynamic Host Configuration Protocol
 OSPF—An Interior Gateway Routing Protocol
 BGP—An Exterior Gateway Routing Protocol