NETWORK LAYER

Introduction to Network Layer

Design issues of Network layer
Routing Algorithm: Shortest Path Routing, Dijkstra Algorithm
Flooding, Link State Routing
Count to Infinity problem
Congestion Control Algorithm
Quality of Services: Leaky Bucket Algorithm, Token Bucket Algorithm
 What is a network?
• A network is a group of two or more connected computing devices. Usually all devices in
the network are connected to a central hub — for instance, a router.
• A network can also include subnetworks, or smaller subdivisions of the network.
Subnetworking is how very large networks, such as those provided by ISPs, are able to
manage thousands of IP addresses and connected devices.
• Computers are connected to each other within networks, and these networks connect
to other networks. This enables these computers to connect with other computers both
near and far.
 What happens at the network layer?
• Anything that has to do with inter-network connections takes place at the network layer.
• This includes setting up the routes for data packets to take, checking to see if a server in
another network is up and running, and addressing and receiving IP packets from other
networks.
• This last process is perhaps the most important, as the vast majority of Internet traffic is
sent over IP.
 What is a packet?
• All data sent over the Internet is broken down into smaller chunks called "packets." When Bob
sends Alice a message, for instance, his message is broken down into smaller pieces and then
reassembled on Alice's computer.
• A packet has two parts: the header, which contains information about the packet itself, and the
body, which is the actual data being sent.
• A header contains information about the content, source, and destination of each packet
(somewhat like stamping an envelope with a destination and return address).
• For example, an IP header contains the destination IP address of each packet, the total size of
the packet, an indication of whether or not the packet has been fragmented (broken up into
still smaller pieces) in transit, and a count of how many networks the packet has traveled
through.
 What is the difference between the 'network' layer and the
'internet' layer?
• In the TCP/IP model, there is no "network" layer. The OSI model network layer roughly
corresponds to the TCP/IP model Internet layer. In the OSI model the network layer is
layer 3; in the TCP/IP model the Internet layer is layer 2.
• In other words, the network layer and the Internet layer are basically the same thing, but
they come from different models of how the Internet works.
 The main functions performed by the network layer are:

• Routing: When a packet reaches the router's input link, the router will move the packets to the
router's output link. For example, a packet from S1 to R1 must be forwarded to the next router on the
path to S2.

• Logical Addressing: The data link layer implements the physical addressing and network layer
implements the logical addressing. Logical addressing is also used to distinguish between source and
destination system. The network layer adds a header to the packet which includes the logical addresses of
both the sender and the receiver.

• Internetworking: This is the main role of the network layer that it provides the logical connection
between different types of networks.

• Fragmentation: The fragmentation is a process of breaking the packets into the smallest individual data
units that travel through different networks.
Packet Forwarding: Routers forward packets to the next hop using routing tables. Key device: Router

Congestion Control: Manages traffic to prevent network overload.

Design Issues of Network Layer

Store-and-Forward Packet Switching:

A host with a packet to transmit to the nearest router.
The packet is stored there until it has fully arrived so the checksum can be verified. Then
the packets are forwarded to the next router along the path until it reaches the destination
host.
This process is called store and forward
Services provided to the transport layer.
The network layer must fulfil the following requirements:
The service should be independent of the network topology.
The network addresses should be made available to the transport with a uniform
numbering plan
The transport layer should be shielded from the number, type and topology of the
routers present.
Implementation of Connectionless Services
Connectionless network services is also called as datagrams.
A datagram is self contained message unit which contains sufficient information to allow it
to be routed from source DTE to destination DTE.
Each packet is treated independently. The network layer simply accepts message from the
transport layer and sends out each one as an isolated unit.
Datagram system is analogous to postal system. Each packet contains the source and
destination address. Each packet follows a different route from source to destination and
they do not necessarily arrive in same order as they were transmitted.
Implementation of connection-oriented Service
It is also called virtual circuit. The process is completed in three main phases:
1. Establishment phase:
a. During setting up logical connection, the two users not only agree to setup a connection
between them but also decide upon the QoS associated with the connection. After this, the
sequence of packetized information are transmitted bidirectionally between the nodes. The
information is delivered to the receiver in the same order as transmitted by sender.
1.
2. Data transfer phase:
a. During this phase, it performs flow control and error control services. The error control
service ensures correct sequencing of packets and correct arrival of packets. Flow control
service ensures a slow receiver from being overwhelming with data from a faster
transmitter.
3. Connection release:
a. When the stations wish to close down the virtual circuit, one station canterminate the
connection with a clear request packet.
Routing Algorithm

The main function of the network layer is to route packets from source to destination. To
accomplish this, a route through the network must be selected. The selection of route is
generally baked on some performance criteria. The simplest criteria is to choose shortest
route through the network.
The shortest route means a route that passes through the least number of nodes. This
shortest route selection results in least number of hops per packet. A routing algorithm is
designed to perform this task. The routing algorithm is a part of network layer software.
Properties of routing algorithms:
1. Correctness and simplicity
2. Robustness: ability to cope with changes in the topology and traffic without requiring
all jobs in hosts to be aborted and network to be rebooted every time.
3. Stability: technique that react to changing conditions such as congestion. The network
must not react too slow or experience unstable swings from one extreme to another.
4. Some performance criteria may favour the exchange between distant stations. Some
compromise is needed between fairness and optimality.
Classification of Routing algorithm

Static (non-adaptive) routing algorithm: network topology determines the initial

paths. The precalculated paths are then loaded to the routing table and are fixed for a
longer period. Suitable for small network. It becomes cumbersome for bigger networks. It is
its inability to respond quickly to network failure.
Dynamic (adaptive) routing algorithm: Change their routing decision if there is
change in topology, traffic. Each router continuously checks the network status by
communicating with neighbours. Thus a change in network topologies eventually
propagated to all the routers. Based on this information gathered, each router computes
the suitable path to the destination. Complexity in the router.
Shortest Path Algorithm

The path length between each node is measured as a function of distance, bandwidth,
average traffic, communication cost, mean queue length, measured delay etc.
By changing the weighing function, the algorithm then computes the shortest path
measured according to any of the criteria or combination.
Two algorithm
Dijkstra’s Algorithm
Bellman-Ford algorithm
Dijkstra’s Algorithm

Each node is labelled with its distance from the source node along the best known path.
Initially no paths are known, so all nodes are labelled with infinity. The algorithm proceed in
stages. As the algorithm proceeds, the paths are found, the labels are changed, reflecting
better paths. Stepwise:
1. Source node is initialized and can be indicated as a filled circle.
2. Initial path cost to neighbouring nodes (adjacent nodes) or link cost is computed and
these nodes are relabelled considering source node.
3. Examine the all adjacent nodes and find the smallest label, make it permanent.
4. The smallest label node is now working node, then step-II and step-III are repeated till
the destination node reaches.
Flooding

This technique requires no network information.

A packet is sent by a source node to all its
adjacent nodes. At each node, every incoming
packet is retransmitted on every outgoing links,
except the link that it arrived from.
Types of Flooding

1. Uncontrolled Flooding
2. Controlled Flooding
3. Selective Flooding
Uncontrolled Flooding
Uncontrolled flooding is the simplest form of flooding.
Characteristics of Uncontrolled Flooding
● Every packet is forwarded to all neighbors
● No checks are applied
● No packet history is maintained
Problems with Uncontrolled Flooding
● Generates excessive duplicate packets
● Causes broadcast storms
● Consumes a large amount of bandwidth
● Can bring down the network
Controlled Flooding

Controlled flooding introduces rules to limit packet duplication. It improves efficiency while keeping the reliability of flooding.
There are two main controlled flooding techniques:

A. Sequence Number Controlled Flooding (SNCF)

In this method:
● Each packet contains a unique sequence number
● Each router stores recently received packets
● If a packet arrives again, it is discarded
This ensures that each packet is forwarded only once by a router.
Advantages of SNCF
● Reduces duplicate packets
● Prevents infinite looping
● Improves network efficiency
B. Reverse Path Forwarding (RPF)
Reverse Path Forwarding works based on the expected path of a packet.

How RPF Works

● A router forwards a packet only if it arrives on the correct incoming link

● If the packet arrives from the wrong direction, it is dropped
This ensures that packets move outward from the source without unnecessary loops.

Benefits of RPF

● Reduces network traffic

● Limits unnecessary forwarding
● Maintains reliability
Selective Flooding
Selective flooding is an improved version of flooding.

How Selective Flooding Works?

● Routers do not forward packets on all links

● Packets are sent only in the general direction of the destination
● Unnecessary paths are ignored
Advantages of Flooding
Flooding in computer networks offers several advantages:
1. Guaranteed delivery of packets
2. Automatically finds the shortest path
3. Highly reliable
4. Works even if some routers fail
5. Simple to implement
6. No routing tables needed
These advantages make flooding useful in special cases.

Disadvantages of Flooding
Flooding in computer networks also has serious disadvantages:
1. Generates duplicate packets
2. Wastes network bandwidth
3. Causes congestion
4. Inefficient for single destinations
5. Increases processing load on routers
6. Can be used for DoS attacks
Distance Vector Routing

In distance vector routing, the least-cost route between any two nodes is the route with
minimum distance. In this protocol each node maintains a vector (table) of minimum
distances to every node. The table at each node also guides the packets to the desired node
by showing the next stop in the route (next-hop routing). In distance vector routing, each
node shares its routing table with
Its immediate neighbors periodically
and when there is a change.
RIP

The Routing Information Protocol (RIP) is an intradomain routing protocol used inside an autonomous system. It is a very
simple protocol based on distance vector routing. RIP implements distance vector routing directly with some considerations:

1. In an autonomous system, we are dealing with routers and networks (links). The routers have routing tables; networks do
not.

2. The destination in a routing table is a network, which means the first column defines a network address.

3. The metric used by RIP is very simple; the distance is defined as the number of links (networks) to reach the destination.
For this reason, the metric in RIP is called a hop count.

4. Infinity is defined as 16, which means that any route in an autonomous system using RIP cannot have more than 15 hops.

5. The next-node column defines the address of the router to which the packet is to be sent to reach its destination.
Hop Count

Hop count is a routing metric that represents the total number of routers a data packet must pass
through to travel from the source device to the destination device.
● Each router crossed by a packet is counted as one hop.
● Used by routing protocols like RIP to determine the best path.
● RIP selects the route with the lowest hop count as the optimal route.
● The maximum hop count in RIP is 15; a hop count of 16 is considered unreachable.
● Limiting the hop count helps prevent routing loops.
● This limitation reduces RIP’s scalability, making it unsuitable for large networks.
How RIP Works

Routing Information Protocol (RIP) is a distance-vector routing protocol that determines the best path to a
destination network based on hop count.
● Each router maintains a routing table containing distances to all known networks.
● Routers periodically exchange routing information with neighboring routers.
● Every 30 seconds, routers broadcast or multicast their entire routing table.
● If a router learns a shorter path, it updates its routing table accordingly.
● If a route is not updated within 180 seconds, it is marked as invalid.
● If the route remains unused for 240 seconds, it is removed (flushed) from the routing table.
● These timers help maintain accurate routing information and prevent stale routes.
Link State Routing

if each node in the domain has the entire topology of the domain-the list of nodes and
links, how they are connected including the type, cost (metric), and condition of the links
(up or down)-the node can use Dijkstra's algorithm to build a routing table.
Each node uses the same topology to create a routing table, but the routing table for each
node is unique because the calculations are based on different interpretations of the
topology.
The topology must be dynamic, representing the latest state of each node and each link. If
there are changes in any point in the network (a link is down, for example), the topology
must be updated for each node.
Building Routing Tables
In link state routing, four sets of actions are required to ensure that each node has the
routing table showing the least-cost node to every other node.
1. Creation of the states of the links by each node, called the link state packet (LSP).
2. Dissemination of LSPs to every other router, called flooding, in an efficient and reliable
way.
3. Formation of a shortest path tree for each node.
4. Calculation of a routing table based on the shortest path tree.
A link state packet carries the node identity, the list of links, a sequence number, and age. The first two
are needed to make the topology. The third facilitates flooding and distinguishes new LSPs from old
ones. The fourth prevents old LSPs from remaining in the domain for a long time. LSPs are generated
on two occasions:
1. When there is a change in the topology of the domain. Triggering of LSP dissemination is the main
way of quickly informing any node in the domain to update its topology.
2. On a periodic basis. The period in this case is much longer compared to distance vector routing. As
a matter of fact, there is no actual need for this type of LSP dissemination. It is done to ensure that
old information is removed from the domain.
The timer set for periodic dissemination is normally in the range of 60 min or 2 h based on the
implementation. A longer period ensures that flooding does not create too much traffic on the
network.
Open Shortest Path First (OSPF)

Open Shortest Path First (OSPF) is a link-state routing protocol used to find the best path between routers
within an Autonomous System (AS). OSPF routers establish neighbor relationships to exchange routing
information, and these relationships play a crucial role in the formation of OSPF adjacencies. Understanding
the transitions between OSPF protocol states is essential for optimizing network performance and
troubleshooting.
● OSPF uses Hello packets for neighbor discovery and to establish communication between routers.
● Neighbor states are key in forming OSPF adjacencies, enabling efficient routing.
● OSPF requires specific parameters like matching Area IDs, authentication, MTU, and timers for
adjacencies to form.
● Distinguishing between OSPF neighbors and adjacent routers is critical for proper network operation.
● Proper management of OSPF states ensures stable and optimized packet routing.
Open Shortest Path First (OSPF) States

The device operating OSPF goes through certain states. These states are:

Down State

● No Hello packets have been received on the interface.

● This is the initial state before communication begins between routers. The OSPF adjacency process has not
started yet.

Init State

● The router receives a Hello packet from another router but is not yet listed in the neighbor’s Hello packet.
● The router has begun communication, but no bidirectional communication has been established yet.
two-Way State

● Bi-directional communication is confirmed when each router sees itself in the other's Hello packet.
● In broadcast or multi-access networks, this is the point at which the Designated Router (DR) and Backup Designated
Router (BDR) election takes place.

ExStart State

● The Master/Slave relationship is established for Database Description (DBD) exchange.

● Routers exchange initial DBD packets, which contain the sequence numbers, indicating the beginning of the exchange
phase. The router with the higher Router ID becomes the master, while the other becomes the slave.

Exchange State

● In this state, routers exchange full Database Description (DBD) packets, which contain the headers of Link State
Advertisements (LSAs).
● Routers create Link-State Request (LSR) lists to request missing LSAs that are not present in their own Link-State
Database (LSDB).
Loading State

● Routers send Link-State Request (LSR) packets to request missing LSAs.

● The routers respond with Link-State Update (LSU) packets, which contain the requested LSAs.
Count to infinity problem

The main issue with Distance Vector Routing (DVR) protocols is Routing Loops since
Bellman-Ford Algorithm cannot prevent loops. This routing loop in the DVR network
causes the Count to Infinity Problem. Routing loops usually occur when an interface goes
down or two routers send updates at the same time.
B will know that it can get to C at a cost of 1, and A will know that it can get to C via B at a cost of 2.
If the link between B and C is disconnected, then B will know that it can no longer
get to C via that link and will remove it from its table. Before it can send any updates
it's possible that it will receive an update from A which will be advertising that it can
get to C at a cost of 2. B can get to A at a cost of 1, so it will update a route to C via
A at a cost of 3. A will then receive updates from B later and update its cost to 4.
They will then go on feeding each other bad information toward infinity which is
called as Count to Infinity problem.
Solution for Count to Infinity problem:-

Route Poisoning:
When a route fails, distance vector protocols spread the bad news about a route
failure by poisoning the route. Route poisoning refers to the practice of
advertising a route, but with a special metric value called Infinity. Routers
consider routes advertised with an infinite metric to have failed. Each distance
vector routing protocol uses the concept of an actual metric value that
represents infinity. RIP defines infinity as 16. The main disadvantage of poison
reverse is that it can significantly increase the size of routing announcements in
certain fairly common network topologies.
Split horizon:
If the link between B and C goes down, and B had received a route from A, B could end
up using that route via A. A would send the packet right back to B, creating a loop. But
according to the Split horizon Rule, Node A does not advertise its route for C (namely A to
B to C) back to B. On the surface, this seems redundant since B will never route via node
A because the route costs more than the direct route from B to C.
Border Gateway Protocol (BGP)

Border Gateway Protocol (BGP) is an Exterior Gateway Protocol (EGP) used to connect
autonomous systems (AS) in any topology. Each AS must have at least one BGP-enabled
router connected to another AS’s BGP router. Its primary function is to exchange network
reachability information between BGP systems. It is a path-vector routing protocol (unlike
distance-vector or link-state protocols).
Characteristics of Border Gateway Protocol (BGP)

● Inter-Autonomous System Configuration: The main role of BGP is to provide communication between two
autonomous systems.
● BGP supports the Next-Hop Paradigm.
● Coordination among multiple BGP speakers within the AS (Autonomous System).
● Path Information: BGP advertisements also include path information, along with the reachable destination
and next destination pair.
● Policy Support: BGP can implement policies that can be configured by the administrator.
● Runs Over TCP.
● BGP conserves network Bandwidth.
● BGP supports CIDR.
● BGP also supports Security.
Importance of Border Gateway Protocol(BGP)
● Security: BGP is highly secure because it authenticates messages between routers using preconfigured
passwords through which unauthorized traffic is filtered out.
● Scalability: BGP is more scalable because it manages a vast number of routes and networks present on
the internet.
● Supports Multihoming: BGP allows multihoming means an organization can connect to multiple
networks simultaneously.
● Calculate the Best Path: As we know data packets is traveled across the internet from source to
destination every system in between the source and destination has to decide where the data packet
should go next
● TCP/IP Model: BGP is based on the TCP/IP model and it is used to control the network layer by using
transport layer protocol.
Elements of BGP

Some elements of BGP are assigned to each path and these elements help routers to select a path from
multiple paths. Here below are some elements of BGP:
● Weight: Weight is defined as a Cisco-specific attribute that tells a router which path is preferred.
The weight having a higher value is preferred.
● Originate: This tells how a router choose routes and adds to BGP itself.
● Local Preference: Local Preference is an element used to select the outbound routing path.
Greater local preference is preferred.
● Autonomous System Path: This element tells the router to select a path having a shorter length.
● Next Hop: To reach the destination the next hop elements specify the IP address that should be
used as the next hop.
Types of Border Gateway Protocol

1. External BGP: It is used to interchange

routing information between the routers in
different autonomous systems, it is also known
as eBGP(External Border Gateway Protocol).

2. Internal BGP: It is used to interchange

routing information between the routers in the
same autonomous system, it is also known as
iBGP(Internal Border Gateway Protocol).
Internal routers also ensure consistency among
routers for sharing routing information.
CONGESTION

Congestion in a network may occur if the load on the network-the number of packets sent to the
network-is greater than the capacity of the network-the number of packets a network can handle.
Congestion control refers to the mechanisms and techniques to control the congestion and keep the load
below the capacity.
Congestion in a network or internetwork occurs because routers and switches have queues-buffers that
hold the packets before and after processing. When a packet arrives at the incoming interface, it undergoes
three steps before departing,
1. The packet is put at the end of the input queue while waiting to be checked.
2. The processing module of the router removes the packet from the input queue once it reaches the front
of the queue and uses its routing table and the destination address to find the route.
3. The packet is put in the appropriate output queue and waits its tum to be sent.
Leaky Bucket

If a bucket has a small hole at the bottom, the water leaks from the bucket at a constant
rate as long as there is water in the bucket. The rate at which the water leaks does not
depend on the rate at which the water is input to the bucket unless the bucket is empty.
The input rate can vary, but the output rate remains constant. Similarly, in networking, a
technique called leaky bucket can smooth out bursty traffic. Bursty chunks are stored in the
bucket and sent out at an average rate.
A FIFO queue holds the packets. If the traffic consists of fixed-size packets (e.g., cells in
ATM networks), the process removes a fixed number of packets from the queue at each
tick of the clock. If the traffic consists of variable-length packets, the fixed output rate must
be based on the number of bytes or bits.
The following is an algorithm for variable-length packets:
1. Initialize a counter to n at the tick of the clock.
2. If n is greater than the size of the packet, send the packet and decrement the counter by
the packet size. Repeat this step until n is smaller than the packet size.
3. Reset the counter and go to step 1.
Token Bucket

The leaky bucket is very restrictive. It does not credit an idle host. For example, if a host is not
sending for a while, its bucket becomes empty. Now if the host has bursty data, the leaky bucket
allows only an average rate. The time when the host was idle is not taken into account. On the
other hand, the token bucket algorithm allows idle hosts to accumulate credit for the future in the
form of tokens. For each tick of the clock, the system sends n tokens to the bucket. The system
removes one token for every cell (or byte) of data sent. For example, if n is 100 and the host is idle
for 100 ticks, the bucket collects 10,000 tokens. Now the host can consume all these tokens in one
tick with 10,000 cells, or the host takes 1000 ticks with 10 cells per tick. In other words, the host
can send bursty data as long as the bucket is not empty. Figure 24.21 shows the idea.
The token bucket can easily be implemented with a counter. The token is initialized to zero. Each
time a token is added, the counter is incremented by 1. Each time a unit of data is sent, the counter
is decremented by 1. When the counter is zero, the host cannot send data.
Token Bucket
 Leaky Bucket Algorithm Token Bucket Algorithm

The output rate is fixed and constant. The output rate is variable.

It works well for constant bit rate traffic. It works well for variable bit rate traffic.

Packets are transmitted at fixed intervals. If tokens are available, packets are
transmitted immediately.

It is less flexible. It is more flexible compared to leaky bucket.

It has higher delay. It has less delay.

It is used for audio streaming and constant It is used for multimedia applications, cloud
video streaming. services, and APIs with rate limits.
Quality of Service

Flow Characteristics
Traditionally, four types of characteristics are attributed to a flow: reliability, delay, jitter, and bandwidth.
Reliability
Reliability is a characteristic that a flow needs. Lack of reliability means losing a packet or acknowledgment,
which entails retransmission. However, the sensitivity of application programs to reliability is not the same. For
example, it is more important that electronic mail, file transfer, and Internet access have reliable transmissions
than telephony or audio conferencing.
Delay
Source-to-destination delay is another flow characteristic. Again applications can tolerate delay in different
degrees. In this case, telephony, audio conferencing, video conferencing, and remote log-in need minimum delay,
while delay in file transfer or e-mail is less important.
Jitter
Jitter is the variation in delay for packets belonging to the same flow. For example, if four packets depart at
times 0, 1, 2, 3 and arrive at 20, 21, 22, 23, all have the same delay, 20 units of time. On the other hand, if the
above four packets arrive at 21, 23, 21, and 28, they will have different delays: 21,22, 19, and 24.
For applications such as audio and video, the first case is completely acceptable; the second case is not. For
these applications, it does not matter if the packets arrive with a short or long delay as long as the delay is
the same for all packets. For this application, the second case is not acceptable.
Jitter is defined as the variation in the packet delay. High jitter means the difference between delays is large;
low jitter means the variation is small.
Bandwidth
Different applications need different bandwidths. In video conferencing we need to send
millions of bits per second to refresh a color screen while the total number of bits in an
e-mail may not reach even a million.