UNIT – 4

Network Layer
Topics:
 Network Layer Design Issues
 Routing Algorithms
 Congestion and Congestion Control
 Network layer in the internet
Network Layer Design Issues:
• Store and Forward Packet Switching
• Services Provided to the Transport layer
• Implementation of Connectionless Service
• Implementation of Connection Oriented Service
• Comparison of Virtual Circuit and Datagram Networks
Store and Forward Packet Switching:
A host with a packet to send transmits it to the nearest router, either on its own LAN or over a
point-to-point link to the [Link] packet is stored there until it has fully arrived and the link
has finished its processing by verifying the checksum. Then it is forwarded to the next router
along the path until it reaches the destination host, where it is delivered.

Services Provided to the Transport layer:

The network layer provides services to the transport layer at the network layer/transport layer
interface. An important question is precisely what kind of services the network layer provides
to the transport layer. The services need to be carefully designed with the following goals in
mind:
1. The services should be independent of the router technology.
2. The transport layer should be shielded from the number, type, and topology of the routers
present.
3. The network addresses made available to the transport layer should use a uniform
numbering plan, even across LANs and WANs.
Given these goals, the designers of the network layer have a lot of freedom in
writing detailed specifications of the services to be offered to the transport layer.
Implementation of Connectionless Service:

Let us assume for this example that the message is four times longer than the maximum
packet size, so the network layer has to break it into four packets, 1, 2, 3, and 4, and send
each of them in turn to router A using some point-to-point protocol, for example, PPP. At this
point the ISP takes over. Every router has an internal table telling it where to send packets for
each of the possible destinations. Each table entry is a pair consisting of a destination and the
outgoing line to use for that destination. Only directly connected lines can be used. For
example, in A has only two outgoing lines—to B and to C—so every incoming packet must
be sent to one of these routers, even if the ultimate destination is to some other router. A’s
initial routing table is shown in the figure under the label ‘‘initially.
At A, packets 1, 2, and 3 are stored briefly, having arrived on the incoming link and
had their checksums verified. Then each packet is forwarded according to A’s table, onto the
outgoing link to C within a new frame. Packet 1 is then forwarded to E and then to F. When it
gets to F, it is sent within a frame over the LAN to H2. Packets 2 and 3 follow the same
route.
However, something different happens to packet 4. When it gets to A it is sent to
router B, even though it is also destined for F. For some reason, A decided to send packet 4
via a different route than that of the first three packets. Perhaps it has learned of a traffic jam
somewhere along the ACE path and updated its routing table, as shown under the label
‘‘later.’’ The algorithm that manages the tables and makes the routing decisions is called the
routing algorithm.
Implementation of Connection Oriented Service:

For connection-oriented service, we need a virtual-circuit network. Let us see how

that works. The idea behind virtual circuits is to avoid having to choose a new route for every
packet sent, when a connection is established, a route from the source machine to the
destination machine is chosen as part of the connection setup and stored in tables inside the
routers. That route is used for all traffic flowing over the connection, exactly the same way
that the telephone system works. When the connection is released, the virtual circuit is also
terminated. With connection-oriented service, each packet carries an identifier telling which
virtual circuit it belongs to.
Host H1 has established connection 1 with host H2. This connection is remembered as
the first entry in each of the routing tables. The first line of A’s table says that if a packet
bearing connection identifier 1 comes in from H1, it is to be sent to router C and given
connection identifier 1. Similarly, the first entry at C routes the packet to E, also with
connection identifier 1.

Comparison of Virtual Circuit and Datagram Networks:

Inside the network, several trade-offs exist between virtual circuits and datagrams. One trade-
off is setup time versus address parsing time. Using virtual circuits requires a setup phase,
which takes time and consumes resources. However, once this price is paid, figuring out what
to do with a data packet in a virtual-circuit network is easy: the router just uses the circuit
number to index into a table to find out where the packet goes. In a datagram network, no
setup is needed but a more complicated lookup procedure is required to locate the entry for
the destination.
 Routing Algorithms:
 The main function of the network layer is routing packets from the source
machine to the destination machine.
 The routing algorithm is that part of the network layer software responsible
for deciding which output line an incoming packet should be transmitted on.
 Routing algorithms can be grouped into two major classes: nonadaptive and
adaptive.
 Nonadaptive algorithms do not base their routing decisions on any
measurements or estimates of the current topology and traffic. This procedure is
sometimes called static routing.
 Adaptive algorithms, in contrast, change their routing decisions to reflect
changes in the topology, and sometimes changes in the traffic as well. These
dynamic routing algorithms differ in where they get their information (e.g.,
locally, from adjacent routers, or from all routers), when they change the routes
and what metric is used for optimization (e.g., distance, number of hops, or
estimated transit time).
The Optimality Principle:
Before we get into specific algorithms, it may be helpful to note that one can make a
general statement about optimal routes without regard to network topology or traffic. This
statement is known as the optimality principle (Bellman,1957). It states that if router J is on
the optimal path from router I to router K, then the optimal path from J to K also falls along
the same route. To see this, call the part of the route from I to J r1 and the rest of the route r
2. If a route better than r 2 existed from J to K, it could be concatenated with r 1 to improve
the route from I to K, contradicting our statement that r 1 r 2 is optimal.
As a direct consequence of the optimality principle, we can see that the set of optimal routes
from all sources to a given destination form a tree rooted at the destination. Such a tree is
called a sink tree and is illustrated, where the distance metric is the number of hops. The goal
of all routing algorithms is to discover and use the sink trees for all routers.

Shortest Path Algorithm:

The concept of a shortest path deserves some explanation. One way of measuring path
length is the number of hops. Using this metric, the paths ABC and ABE are equally long.
Another metric is the geographic distance in kilometres, in which case ABC is clearly much
longer than ABE.
Several algorithms for computing the shortest path between two nodes of a graph are known.
This one is due to Dijkstra (1959) and finds the shortest paths between a source and all
destinations in the network. Each node is labelled (in parentheses) with its distance from the
source node along the best known path. The distances must be non-negative, as they will be if
they are based on real quantities like bandwidth and delay. Initially, no paths are known, so
all nodes are labeled with infinity. As the algorithm proceeds and paths are found, the labels
may change, reflecting better paths. A label may be either tentative or permanent. Initially, all
labels are tentative. When it is discovered that a label represents the shortest possible path
from the source to that node, it is made permanent and never changed thereafter.

Flooding:
When a routing algorithm is implemented, each router must make decisions based on local
knowledge, not the complete picture of the network. A simple local technique is flooding, in
which every incoming packet is sent out on every outgoing line except the one it arrived on.
Flooding obviously generates vast numbers of duplicate packets, in fact, an infinite
number unless some measures are taken to damp the process. One such measure is to have a
hop counter contained in the header of each packet that is decremented at each hop, with the
packet being discarded when the counter reaches zero. Ideally, the hop counter should be
initialized to the length of the path from source to destination. If the sender does not know
how long the path is, it can initialize the counter to the worst case, namely, the full diameter
of the network .
Flooding with a hop count can produce an exponential number of duplicate packets as
the hop count grows and routers duplicate packets they have seen before. A better technique
for damming the flood is to have routers keep track of which packets have been flooded, to
avoid sending them out a second time. One way to achieve this goal is to have the source
router put a sequence number in each packet it receives from its hosts. Each router then needs
a list per source router telling which sequence numbers originating at that source have already
been seen. If an incoming packet is on the list, it is not flooded.

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.
A 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 neighbours. Eventually,
every router knows the best link to reach each destination.
The distance vector routing algorithm is sometimes called by other names, most
commonly the distributed Bellman-Ford routing algorithm.
In distance vector routing, each router maintains a routing table indexed by, and containing
one entry for each router in the network. This entry has two parts: the preferred outgoing line
to use for that destination and an estimate of the distance to that destination. The distance
might be measured as the number of hops.

Link State Routing:

Distance vector routing was used in the ARPANET until 1979, when it was replaced by link
state routing. The idea behind link state routing is fairly simple and can be stated as five parts.
Each router must do the following things to make it work:
[Link] its neighbours and learn their network addresses.
2. Set the distance or cost metric to each of its neighbours.
3. Construct a packet telling all it has just learned.
4. Send this packet to and receive packets from all other routers.
5. Compute the shortest path to every other router.
Hierarchical Routing:
As networks grow in size, the router routing tables grow proportionally. Not only is router
memory consumed by ever-increasing tables, but more CPU time is needed to scan them and
more bandwidth is needed to send status reports about them. At a certain point, the network
may grow to the point where it is no longer feasible for every router to have an entry for
every other router, so the routing will have to be done hierarchically, as it is in the telephone
network.
When hierarchical routing is used, the routers are divided into what we will call
regions. Each router knows all the details about how to route packets to destinations within
its own region but knows nothing about the internal structure of other regions. When different
networks are interconnected, it is natural to regard each one as a separate region to free the
routers in one network from having to know the topological structure of the other ones.

Congestion Control:
 Too many packets present in (a part of) 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.
• Congestion control refers to techniques and mechanisms that can either prevent
congestion before it happens or remove congestion after it has happened.
• In general, we can divide congestion control mechanisms into two broad categories:
open-loop congestion control (prevention) and closed-loop congestion control
(removal).
Open-Loop Congestion Control:
In open-loop congestion control, policies are applied to prevent congestion before it
happens. In these mechanisms, congestion control is handled by either the source or the
destination. list of policies that can prevent congestion.
• Retransmission Policy
• Window Policy
 • Acknowledgment Policy
• Discarding Policy
• Admission Policy

Retransmission Policy:
Retransmission is sometimes unavoidable. If the sender feels that a sent packet is lost
or corrupted, the packet needs to be retransmitted. Retransmission in general may increase
congestion in the network. However, a good retransmission policy can prevent congestion.
The retransmission policy and the retransmission timers must be designed to optimize
efficiency and at the same time prevent congestion.

Window Policy:
The type of window at the sender may also affect congestion. The Selective Repeat
window is better than the Go-Back-N window for congestion control. In the Go-Back-N
window, when the timer for a packet times out, several packets may be resent, although some
may have arrived safe and sound at the receiver. This duplication may make the congestion
worse. The Selective Repeat window, on the other hand, tries to send the specific packets that
have been lost or corrupted.

Acknowledgment Policy:
The acknowledgment policy imposed by the receiver may also affect congestion. If
the receiver does not acknowledge every packet it receives, it may slow down the sender and
help prevent congestion.

Discarding Policy:
A good discarding policy by the routers may prevent congestion and at the same time
may not harm the integrity of the transmission. For example, in audio transmission, if the
policy is to discard less sensitive packets when congestion is likely to happen, the quality of
sound is still preserved and congestion is prevented or alleviated.

Admission Policy:
An admission policy, which is a quality-of-service mechanism, can also prevent
congestion in virtual-circuit networks. Switches in a flow first check the resource requirement
of a flow before admitting it to the network. A router can deny establishing a virtual-circuit
connection if there is congestion in the network or if there is a possibility of future
congestion.

Closed-Loop Congestion Control:

Closed-loop congestion control mechanisms try to alleviate congestion after it
happens. Several mechanisms have been used by different protocols.
• Backpressure
• Choke Packet
• Implicit Signaling
• Explicit Signaling
Backpressure:
The technique of backpressure refers to a congestion control mechanism in
which a congested node stops receiving data from the immediate upstream node or
 nodes. This may cause the upstream node or nodes to become congested, and they, in
turn, reject data from their upstream node or nodes, and so on. Backpressure is a node
to-node congestion control that starts with a node and propagates, in the opposite
direction of data flow, to the source. The backpressure technique can be applied only
to virtual circuit networks, in which each node knows the upstream node from which
a flow of data is coming.

Choke Packet:
A choke packet is a packet sent by a node to the source to inform it of congestion.
Note the difference between the backpressure and choke-packet methods. In backpressure,
the warning is from one node to its upstream node, although the warning may eventually
reach the source station. In the choke-packet method, warning is from the router, which has
encountered congestion, directly to the source station.

Implicit Signaling:
In implicit signaling, there is no communication between the congested node or
nodes and the source. The source guesses that there is congestion somewhere in the network
from other symptoms.

Explicit Signaling :
The node that experiences congestion can explicitly send a signal to the source or
destination. The explicit-signaling method, however, is different from the choke-packet
method.

Network layer in the internet :

IPV4 Header Format:
 The Version field keeps track of which version of the protocol the datagram belongs
to.
 The header length is not constant, a field in the header, IHL, is provided to tell how
long the header is, in 32-bit words. The minimum value is 5, which applies when no
options are present. The maximum value of this 4-bit field is 15, which limits the
header to 60 bytes, and thus the Options field to 40 bytes.
 The Differentiated services field is one of the few fields that has changed its meaning
(slightly) over the years. Originally, it was called the Type of service field.
 The Total length includes everything in the datagram—both header and data. The
maximum length is 65,535 bytes.
 The Identification field is needed to allow the destination host to determine which
packet a newly arrived fragment belongs to. All the fragments of a packet contain the
same Identification value.
 DF stands for Don’t Fragment. It is an order to the routers not to fragment the packet.
 MF stands for More Fragments. All fragments except the last one have this bit set. It
is needed to know when all fragments of a datagram have arrived.
 The Fragment offset tells where in the current packet this fragment belongs. All
fragments except the last one in a datagram must be a multiple of 8 bytes, the
elementary fragment unit.
 The TtL (Time to live) field is a counter used to limit packet lifetimes. It was
originally supposed to count time in seconds, allowing a maximum lifetime of 255
sec.
 The Protocol field tells it which transport process to give the packet to. TCP is one
possibility, but so are UDP and some others. The numbering of protocols is global
across the entire Internet.
 The header carries vital information such as addresses, it rates its own checksum for
protection, the Header checksum the Header checksum is assumed to be zero upon
arrival. Such a checksum is useful for detecting errors while the packet travels
through the network.
  The Source address and Destination address indicate the IP address of the source and
destination network interfaces.
 The Options field was designed to provide an escape to allow subsequent versions of
the protocol to include information not present in the original design, to permit
experimenters to try out new ideas, and to avoid allocating header bits to information
that is rarely needed.
IP addresses:
• IPv4 uses 32-bit addresses, which means that the address space is 232 or
4,294,967,296 (more than four billion).
• There are three common notations to show an IPv4 address: binary notation (base 2),
dotted-decimal notation (base 256), and hexadecimal notation (base 16).

Classful Addressing:
When the Internet started, an IPv4 address was designed with a fixed-length prefix,
but to accommodate both small and large networks, three fixed-length prefixes were designed
instead of one (n = 8, n = 16, and n = 24). The whole address space was divided into five
classes (class A, B, C, D, and E), This scheme is referred to as classful addressing.
In class A, the network length is 8 bits, but since the first bit, which is 0, defines the
class, we can have only seven bits as the network identifier. This means there are only 2 7 =
128 networks in the world that can have a class A address.
In class B, the network length is 16 bits, but since the first two bits, which are (10)2,
define the class, we can have only 14 bits as the network identifier. This means there are only
214 = 16,384 networks in the world that can have a class B address.
All addresses that start with (110)2 belong to class C. In class C, the network length is
24 bits, but since three bits define the class, we can have only 21 bits as the network
identifier. This means there are 221 = 2,097,152 networks in the world that can have a class C
address.
Subnetting and Super netting:
 In subnetting, a class A or class B block is divided into several subnets.
 Super netting was devised to combine several class C blocks into a larger block to be
attractive to organizations that need more than the 256 addresses available in a class C
block.

Supernetting:
• In super netting, an organization can combine several class C blocks to create a larger
range of addresses. In other words, several networks are combined to create a super
network.
• By doing this, an organization can apply for several class C blocks instead of just one.
• For example, an organization that needs 1000 addresses can be granted four class C
blocks.
Classless Addressing:
• Subnetting and super netting in classful addressing did not really solve the address
depletion problem.
• With the growth of the Internet, it was clear that a larger address space was needed as
a long-term solution.
• Although the long-range solution has already been devised and is called IPv6, a short-
term solution was also devised to use the same address space but to change the
distribution of addresses to provide a fair share to each organization.
• The short-term solution still uses IPv4 addresses, but it is called classless addressing.
• A small prefix means a larger network; a large prefix means a smaller network.
• The prefix length, n, is added to the address, separated by a slash.
• The notation is informally referred to as slash notation and formally as classless
interdomain routing or CIDR (pronounced cider) strategy.

IP Version 6:
• The main reason for migration from IPv4 to IPv6 is the small size of the address space
in IPv4.
• In this section, we show how the huge address space of IPv6 prevents address
depletion in the future.
Representation
• A computer normally stores the address in binary, but it is clear that 128 bits cannot
easily be handled by humans.
• Several notations have been proposed to represent IPv6 addresses when they are
handled by humans.
• Although an IPv6 address, even in hexadecimal format, is very long, many of the
digits are zeros. In this case, we can abbreviate the address.
• The leading zeros of a section can be omitted. Using this form of abbreviation, 0074
can be written as 74, 000F as F, and 0000 as 0.
 • Further abbreviation, often called zero compression, can be applied to colon hex
notation if there are consecutive sections consisting of zeros only. We can remove all
the zeros and replace them with a double semicolon.

The Main IPv6 Header:

Each packet is composed of a base header followed by the payload. The base header
occupies 40 bytes, whereas payload can be up to 65,535 bytes of information. The description
of fields follows.
Version:The 4-bit version field defines the version number of the IP. For IPv6, the value is 6.
Traffic class: The 8-bit traffic class field is used to distinguish different payloads with
different delivery requirements. It replaces the type-of-service field in IPv4.
Flow label: The flow label is a 20-bit field that is designed to provide special handling for a
particular flow of data. We will discuss this field later.
Payload length: The 2-byte payload length field defines the length of the IP datagram
excluding the header. Note that IPv4 defines two fields related to the length: header length
and total length. In IPv6, the length of the base header is fixed (40 bytes); only the length of
the payload needs to be defined.
Next header: The next header is an 8-bit field defining the type of the first extension header
(if present) or the type of the data that follows the base header in the datagram. This field is
similar to the protocol field in IPv4, but we talk more about it when we discuss the payload.
Hop limit: The 8-bit hop limit field serves the same purpose as the TTL field in IPv4.
Source and destination addresses: The source address field is a 16-byte (128-bit) Internet
address that identifies the original source of the datagram. The destination address field is a
16-byte (128-bit) Internet address that identifies the destination of the datagram.
Payload. Compared to IPv4, the payload field in IPv6 has a different format and meaning,
The payload in IPv6 means a combination of zero or more extension headers (options)
followed by the data from other protocols (UDP, TCP, and so on).
Extension Header:
An IPv6 packet is made of a base header and some extension headers. The length of the base
header is fixed at 40 bytes. However, to give more functionality to the IP datagram, the base
header can be followed by up to six extension headers. Many of these headers are options in
IPv4. Six types of extension headers have been defined.

Hop-by-Hop Option:
The hop-by-hop option is used when the source needs to pass information to all routers
visited by the datagram. For example, perhaps routers must be informed about certain
management, debugging, or control functions. Or, if the length of the datagram is more than
the usual 65,535 bytes, routers must have this information.
Destination Option:
The destination option is used when the source needs to pass information to the destination
only. Intermediate routers are not permitted access to this information.
Source Routing
The source routing extension header combines the concepts of the strict source route and the
loose source route options of IPv4.
Fragmentation:
The concept of fragmentation in IPv6 is the same as that in IPv4. However, the place where
fragmentation occurs differs. In IPv4, the source or a router is required to fragment if the size
of the datagram is larger than the MTU of the network over which the datagram travels. In
IPv6, only the original source can fragment. A source must use a Path MTU Discovery
technique to find the smallest MTU supported by any network on the path. The source then
fragments using this knowledge.
Authentication:
The authentication extension header has a dual purpose: it validates the message sender and
ensures the integrity of data.
Encrypted Security Payload:
The encrypted security payload (ESP) is an extension that provides confidentiality and
guards against eavesdropping.