Unit - 2

WIRELESS TRANSMISSION
Wireless transmission is a form of unguided media. It involves no physical link
between devices, communicating wirelessly.
An unguided transmission transmits the electromagnetic waves without using any
physical medium. Therefore it is also known as wireless transmission.
Wireless signals are spread over in the air and are received and interpreted by
appropriate antennas. Antennas convert the digital data into wireless signals and spread all
over within its frequency range.
In unguided media, air is the media through which the electromagnetic energy can
flow easily.
2.3.1 Electromagnetic spectrum
When electrons move, they create electromagnetic waves that can propagate through
space (even in a vacuum).
These waves were predicted by the British physicist James Clerk Maxwell in 1865
and first observed by the German physicist Heinrich Hertz in 1887.
The number of oscillations per second of a wave is called its frequency, f, and is
measured in Hz (Hertz).
The distance between two consecutive maxima (or minima) is called the wavelength,
which is designated by the Greek letter λ (lambda).
A part of electromagnetic spectrum can be used for wireless transmission

Electromagnetic spectrum
The radio, microwave, infrared, and visible light portions of the spectrum can all be
used for transmitting information by modulating the amplitude, frequency, or phase of the
waves.
Ultraviolet light, X-rays, and gamma rays would be better, due to their higher
frequencies, but they are hard to produce and modulate, do not propagate well through
buildings, and are dangerous to living things.
Unguided transmission is broadly classified as:
 Radio waves
 Microwaves
 Infrared Transmission
 Light Transmission
Radio waves
Transmission of data using radio frequencies is called radio-wave transmission.
Radio stations transmit radio waves using transmitters, which are received by the
receiver.
Both transmitters and receivers use antennas to radiate or capture radio signals.
These radio frequencies can also be used for direct voice communication within
the allocated range. This range is usually 10 miles.
 Radio waves are the electromagnetic waves that are transmitted in all the directions
of free space.
 Radio waves are omnidirectional, i.e., the signals are propagated in all the directions.
 The frequency range of radio waves is from 3Khz to 1 khz.
 In the case of radio waves, the sending and receiving antenna are not aligned, i.e.,
the wave sent by the sending antenna can be received by any receiving antenna.
 An example of the radio wave is FM radio.
 Radio frequency (RF) waves are easy to generate, can travel long distances, and can
penetrate buildings easily, so they are widely used for communication, both indoors
and outdoors.

(a) In the VLF, LF, and MF bands, radio waves follow the curvature of the earth. (b)
In the HF band, they bounce off the ionosphere.
In the VLF, LF, and MF bands, radio waves follow the ground.
Radio waves of high frequencies are prone to be absorbed by rain and other
obstacles. They use Ionosphere of earth atmosphere. High frequency radio waves such as
HF and VHF bands are spread upwards. When they reach Ionosphere, they are refracted
back to the earth.
The military also communicate in the HF and VHF bands.
Applications of Radio waves
 A Radio wave is useful for multicasting when there is one sender and many
receivers.
 An FM radio, television, cordless phones are examples of a radio wave.
Advantages of Radio transmission
 Radio transmission is mainly used for wide area networks and mobile cellular
phones.
 Radio waves cover a large area, and they can penetrate the walls.
 Radio transmission provides a higher transmission rate.
 Inexpensive mode of information exchange
 No land needs to be acquired for laying cables
 Installation and maintenance of devices is cheap
Disadvantages of Radio Wave
 Insecure communication medium
 Prone to weather changes like rain, thunderstorms, etc.
Microwaves
Electromagnetic waves above 100 MHz tend to travel in a straight line and signals
over them can be sent by beaming those waves towards one particular station.
Because Microwaves travel in straight lines, both sender and receiver must be
aligned to be strictly in line-of-sight.
Microwaves can have wavelength ranging from 1 mm – 1 meter and frequency
ranging from 300 MHz to 300 GHz.

Microwave transmission
Microwave antennas concentrate the waves making a beam of it. As shown in
picture above, multiple antennas can be aligned to reach farther.
Microwaves have higher frequencies and do not penetrate wall like obstacles.
Microwave transmission highly depends upon the weather conditions and the
frequency it uses.
Types of Microwave Transmission

Terrestrial Microwave Transmission

 Terrestrial Microwave transmission is a technology that transmits the focused beam
of a radio signal from one ground-based microwave transmission antenna to another.
  Microwaves are the electromagnetic waves having the frequency in the range from
1GHz to 1000 GHz.
 Microwaves are unidirectional as the sending and receiving antenna is to be aligned.
 In this case, antennas are mounted on the towers to send a beam to another antenna
which is km away.
 It works on the line of sight transmission, i.e., the antennas mounted on the towers
are the direct sight of each other.
Characteristics of Microwave
 Frequency range: The frequency range of terrestrial microwave is from 4-6 GHz to
21-23 GHz.
 Bandwidth: It supports the bandwidth from 1 to 10 Mbps.
 Short distance: It is inexpensive for short distance.
 Long distance: It is expensive as it requires a higher tower for a longer distance.
 Attenuation: Attenuation means loss of signal. It is affected by environmental
conditions and antenna size.
Advantages of Microwave
 Microwave transmission is cheaper than using cables.
 It is free from land acquisition as it does not require any land for the installation of
cables.
 Microwave transmission provides an easy communication.
 Communication over oceans can be achieved by using microwave transmission.
Disadvantages of Microwave transmission:
 Eavesdropping: An eavesdropping creates insecure communication. Any malicious
user can catch the signal in the air by using its own antenna.
 Out of phase signal: A signal can be moved out of phase by using microwave
transmission.
 Susceptible to weather condition: A microwave transmission is susceptible to
weather condition. This means that any environmental change such as rain, wind can
distort the signal.
 Bandwidth limited: Allocation of bandwidth is limited in the case of microwave
transmission.
Satellite Microwave Communication
 A satellite is a physical object that revolves around the earth at a known height.
 Satellite communication is more reliable nowadays as it offers more flexibility than
cable and fibre optic systems.
 We can communicate with any point on the globe by using satellite communication.
How Does Satellite work?
The satellite accepts the signal that is transmitted from the earth station, and it
amplifies the signal. The amplified signal is retransmitted to another earth station.
Advantages of Satellite Microwave Communication
 The coverage area of a satellite microwave is more than the terrestrial microwave.
 The transmission cost of the satellite is independent of the distance from the centre
of the coverage area.
 Satellite communication is used in mobile and wireless communication applications.
 It is easy to install.
 It is used in a wide variety of applications such as weather forecasting, radio/TV
signal broadcasting, mobile communication, etc.
Disadvantages of Satellite Microwave Communication
 Satellite designing and development requires more time and higher cost.
 The Satellite needs to be monitored and controlled on regular periods so that it
remains in orbit.
 The life of the satellite is about 12-15 years. Due to this reason, another launch of the
satellite has to be planned.
Infrared Transmission
An infrared transmission is a wireless technology used for short range
communication.
The frequency of the infrared in the range from 300 GHz to 400 THz.
Infrared wave lies in between visible light spectrum and microwaves. The remote
controls used for televisions, VCRs, and stereos all use infrared communication.
They are relatively directional, cheap, and easy to build but have a major drawback:
they do not pass through solid objects.
Security of infrared systems against eavesdropping is better than radio systems.
No government license is needed to operate an infrared system, in contrast to radio
systems, which must be licensed outside the ISM bands.
Infrared communication has a limited use on the desktop, for example, to connect
notebook computers and printers with the IrDA (Infrared Data Association) standard.
Light Transmission
Highest most electromagnetic spectrum which can be used for data transmission is
light or optical signaling. This is achieved by means of LASER.
Because of frequency light uses, it tends to travel strictly in straight line. Hence the
sender and receiver must be in the line-of-sight.
 Because laser transmission is unidirectional, at both ends of communication the laser
and the photo-detector need to be installed.
Laser beam is generally 1mm wide hence it is a work of precision to align two far
receptors each pointing to lasers source.

Convection currents can interfere with laser communication systems. A

bidirectional system with two lasers is pictured here.
Laser works as Tx (transmitter) and photo-detectors works as Rx (receiver).
Lasers cannot penetrate obstacles such as walls, rain, and thick fog. Additionally,
laser beam is distorted by wind, atmosphere temperature, or variation in temperature in the
path.
Laser is safe for data transmission as it is very difficult to tap 1mm wide laser
without interrupting the communication channel.
COMMUNICATION SATELLITES
Communication satellite is an artificial satellite that acts as a large repeater in the
sky. It receives signals from the source transmitter, amplifies using transponders, and relays
them to the receiver.
Communication satellites may be owned by government or private organizations.
Presently, there are more than 2000 communication satellites in the sky. Some of its uses are
 Internet
 Military operations
 Television
 Telephone
 Radio
Communication satellites are broadly categorized into three types depending upon
the orbit in which they are placed.
 Geostationary Satellite (GEO) − They are at 36,000 km from the earth‘s surface.
They have same orbital period as earth‘s rotation. So they appear to be still in the
sky. At least 3 GEOs are needed for global coverage.
  Medium Earth Orbit Satellite (MEO) − They are placed between the two Van
Allen belts, at a distance between 2,000 km to 36,000 km from the earth‘s surface.
At least 10 MEOs are needed for global coverage.
 Low Earth Orbit Satellite (LEO) − They are situated below the Lower Van Allen
belt. Their orbital altitude is 160 km to 2000 km. For global coverage, as high as 50
LEOs are required.

Communication satellites and some of their properties

Geostationary Satellite
 GEO satellites have a distance of almost 36,000 km to the earth surface.
 Complete rotation exactly one day, satellite is synchronous to earth rotation.
 If a satellite should appear fixed in the sky, it requires a period of 24 hours.
 Fix antenna positions, no adjusting necessary.
 The first geostationary satellites had a single spatial beam that illuminated about 1/3
of the earth‘s surface, called its footprint . Satellites usually have a large footprint (up
to 34%).
 High transmit power needed and High latency due to long distance.
 GEO‘s lifetime 20-30 years
 Examples are almost all TV and radio broadcast satellites, many weather satellites
and satellites operating as backbones for the telephone network.
 Not useful for global coverage for small mobile phones and data transmission.

Medium Earth Orbit Satellite

 MEOs operates at a distance of about 10000-20000 km above of the earth.
 Visibility of a satellite is 2-4 hours.
 MEO will have lifetime of 10-15 years.
 Global radio coverage possible
 Latency comparable with terrestrial long distance.
 Connections 5 - 10 msec
  Smaller footprints, better frequency reuse
 Many satellites necessary for global coverage
 More complex systems due to moving satellites
Examples:
 Iridium ( 66 satellites)
 Global star ( 48 satellites)
 GPS
Low Earth Orbit Satellite
 Orbit 5000 - 12000 km above earth surface
 Comparison with MEO systems:
o Slower moving satellites
o Less satellites needed
o Simpler system design
 For many connections no hand-over needed
 LEO provides service to remote places on the earth.
 Higher latency 70 - 80 msec and Higher sending power needed
 Special antennas for small footprints needed
Example:
 ICO (Intermediate Circular Orbit, Inmersed) start 2000
 Teledesic system.

PUBLIC SWITCHED TELEPHONE NETWORK

Public Switched Telephone Network (PSTN) is a collection of an interconnected
network of telephone lines owned by both governments as well as commercial
organizations.
PSTN is the world‘s collection of interconnected voice-oriented public telephone
networks.
 PSTN stands for public circuit-switched telephone network, or the traditional circuit-
switched telephone network.
PTSN comprises all the switched telephone networks around the world that are
operated by local, national or international carriers. These networks provide
the infrastructure and the services for public telecommunication.
Properties of PSTN
 It is also known as Plain Old Telephone Service (POTS)
 The individual networks can be owned by national government, regional government
or private telephone operators.
 Its main objective is to transmit human voice in a recognizable form.
 Originally, it was an entirely analog network laid with copper cables and switches.
 Presently, most part of PSTN networks is digitized and comprises of a wide variety
communicating devices.
 The present PSTNs comprises of copper telephone lines, fibre optic cables,
communication satellites, microwave transmission links and undersea telephone
lines. It is also linked to the cellular networks.
 Present telephone systems are tightly coupled with WANs (Wide Area Networks)
and are used for both data and voice communications.
 The operation of PSTN networks follows the ITU-T standards.
Structure of the Telephone System
The telephone was patented by Graham Bell in 1876. Initially, the telephones were
sold in pairs and it was up to customer to string a single wire between them. The electrons
returned through the earth.
Bell formed also the Bell Telephone Company which opened its first switching
office in New Haven, Connecticut, in 1878.
The model of connecting every telephone to every other telephone, was not going to
work.
To make a call, the customer would crank the phone to ring in the telephone
company office where the operator manually connected the caller to the callee using a
jumper cable.
Later, the switching offices had to be connected to make long-distance calls possible.
Therefore second-level switching offices became necessary and successively the hierarchy
grew to five levels. This scheme remained essentially intact for over 100 years.

(a) Fully interconnected network. (b) Centralized switch. (c) Two-level hierarchy
 A telephone network consisting only of telephones (the small dots), end offices (the
large dots), and toll offices (the squares).
By 1890, the three major parts of the telephone system were in place: the switching
offices, the wires between the customers and the switching offices, and the long-distance
connections between the switching offices.
The telephone system model is organized as a highly redundant, multilevel
hierarchy.
It comprises of the following components:
 Telephone of the subscriber or end user
 End office − Local central office directly connected to end user at a distance of 1 –
10km.
 Local loop − A two-way connection between the telephone and the end office.
 Toll office − switching centres which are called tandem offices when located within
the same local area.
 Toll connecting trunk − Lines that connect end offices with toll offices.
 Intermediate switching offices − Interconnected non-hierarchical switching offices
for connecting toll offices.
 Inter toll trunk − Very high bandwidth channels that connect either two toll offices
via intermediate switching offices.
Long-distance connection might be routed as follows

Circuit route for a long-distance call

In the past, signaling throughout the telephone system was analog. Now, all the long-
distance trunks within the telephone system are rapidly being converted to digital using
optical fibers. It has the following reasons:
 Digital signal can pass through arbitrary number of regenerators with no information
loss. In contrast, analog signals always suffer some information loss when amplified,
and this loss is cumulative.
 Voice, data, music and images can be interspersed to make more efficient use of the
circuits and equipment.
 Much higher data rates are possible.
  Digital transmission is much cheaper than analog, since it is not necessary to
accurately reproduce an analog waveform through potentially hundreds of amplifiers
on a transcontinental call.
 Maintenance of digital system is easier. A transmitted bit is either received correctly
or not.
The telephone system consists of three major components:
1. Local loops (analog twisted pairs going to houses and businesses).
2. Trunks (digital fiber optic links connecting the switching offices).
3. Switching offices (where calls are moved from one trunk to another).
The Local Loop: Modems, ADSL, and Fiber
A local two-wire loop that comes from the phone desk and offices. The local loop is
also frequently referred to as the ‗‗last mile,‘‘ although the length can be up to several
miles. It has carried analog information for over 100 years and due to the high cost of
converting to digital.
Telephone modems send digital data between computers over the narrow channel the
telephone network provides for a voice call.
They were once widely used, but have been largely displaced by broadband
technologies such as ADSL.
Both modems and ADSL must deal with the limitations of old local loops: relatively
narrow bandwidth, attenuation and distortion of signals, and susceptibility to electrical noise
such as crosstalk.
The following local loops are considered important:
 Telephone modems
 Digital subscriber lines
 Fiber to the home
Telephone Modems
Telephone modems are used to transfer bits between two computers on a voice
phone line, rather than for a conversation, which usually occupies the line.
The main difficulty is that the voice telephone line is limited to 3,100 Hz, which is
enough for a conversation. This bandwidth is more than four orders of magnitude less than
the bandwidth used for Ethernet or 802.11(WiFi).
As expected, data rates for telephone modems are also four orders of magnitude
lower than Ethernet and 802.11.
A device that converts a stream of digital bits and an analog signal that represents
bits is called a modem, which is an abbreviation for ―modulator-demodulator‖.
 Modems are of different types: telephone modems, DSL modems, cable modems,
wireless modems, and so on.
The modem can be integrated with a computer (common to telephone modems) or
be a separate unit (common to both DSL and cable modems).
Logically, a modem is inserted between the computer (digital) and the telephone
system (analog), as shown in the Figure.

The use of both analog and digital transmission for a computer-to-computer call.
Conversion is done by the modems and
codecs Digital Subscriber Lines
DSL (Digital Subscriber Line) is a modem technology that uses existing telephone
lines to transport high-bandwidth data, such as multimedia and video, to service subscribers.
DSL provides dedicated, point-to-point, public network access.
Services with more bandwidth than standard telephone services are sometimes called
broadband.
The capacity of the local loop decreases rapidly with the distance from the end
office, as the signal deteriorates along the cable. It also depends on the thickness and overall
quality of the twisted pair.
The graph of potential bandwidth versus distance is shown in the following Figure.

Bandwidth versus distance over Category 3 UTP for DSL

The international ADSL standard, known as [Link], was approved in 1999.

It provides speed up to 8 Mbps downlink and 1 Mbps uplink. It was replaced by the
second generation in 2002, called ADSL2.
 Some enhancements have been made to achieve speeds of up to 12 Mbps downlink
and 1 Mbps uplink.
We now have ADSL2+, which doubles the downstream speed to 24 Mbps, doubling
the bandwidth to use 2.2 MHz on a twisted pair.
Fiber to the Home
In general, fiber houses are combined so that only one fiber reaches the final office
per group of 100 houses.
In the downward direction, the optical dividers divide the final desktop signal so that
it reaches all the homes.
Encryption is necessary for security if only one house can decode a signal.
This architecture is called PON (Passive Optical Network).
In general, for all downlink channels, the total wavelength is used for transmission in
the downstream direction and another wavelength is used for transmission in the upstream
direction.

Passive optical network for Fiber to the Home

Trunks and Multiplexing

 Trunk is a line or link designed to handle many signals
simultaneously and that connect major switching centers or nodes in
a communication system.
 Trunks in the telephone network are much faster than the local
loops.
 The telephone network carries digital information, not analog
information; that is, bits not voice.
 The trunks carry thousands, even millions, of calls simultaneously. It
is accomplished with versions of TDM and FDM multiplexing.

Multiplexing

 It is sending multiple signals or streams of information on a carrier

at the same time in the form of single, complex signal.
  It is of two types.
 Frequency Division Multiplexing (FDM)
 Time Division Multiplexing (TDM)
Frequency Division Multiplexing (FDM)
 FDM is a scheme in which numerous signals are combined for
transmission on a single communication line or channel.
 Each signal is assigned a different frequency (subchannel) within the
main channel.
 In FDM, the total bandwidth is divided to a set of frequency bands
that do not overlap.
 Each of these bands is a carrier of a different signal that is generated
and modulated by one of the sending devices.

Time Division Multiplexing (TDM)

 Time division multiplexing (FDM) is a technique, where the users are
allowed the available bandwidth on time sharing basis.
 Here the time domain is divided into several slots of fixed length, and
each signal is allotted a time slot on a round-robin basis.

The T1 carrier (1.544 Mbps)

 The T1 carrier consists of 24 voice channels multiplexed together.
Each of the 24 channels, in turn, gets to insert 8 bits into the output
stream.
  A frame consists of 24 x 8 = 192 bits plus one extra bit for control
purposes, yielding 193 bits every 125 μsec. This gives a gross data
rate of 1.544 Mbps, of which 8 kbps is for signaling.
Digitizing Voice Signals
 The analog signals are digitized in the end office by a device called a
codec (short for ‗‗coder-decoder‘‘).
 The codec makes 8000 samples per second (125 μsec/sample). Each
sample of the amplitude of the signal is quantized to an 8-bit
number.
 This technique is called PCM (Pulse Code Modulation). It forms the
heart of the modern telephone system.
SONET/SDH
 SONET is a standard for transmitting data over optical medium.
 SONET is a transport protocol which defines the structure of WAN
and how information passes in WAN.
 SONET is a packet switching technology. It uses different frame sizes
based on the bandwidth.
Wavelength Division Multiplexing (WDM)
 WDM is a number of optical carrier signals onto a single optical fiber
by using different wavelength.

Wavelength division multiplexing

 In the figure, four fibers come together at an optical combiner, each
with its energy present at a different wavelength.
 The four beams are combined onto a single shared fiber for
transmission to a distant destination.
 At the end, the beam is split up over as many fibers as there were on
the input side.
 SWITCHING
Switching is the technique by which nodes control or switch data to
transmit it between specific points on a network.
Two different switching techniques are used by the network nowadays:
 Circuit switching
 Packet switching.
Circuit Switching
 The traditional telephone system is based on circuit switching.
 An important property of circuit switching is the need to set up an
end-to-end path before any data can be sent.
 The elapsed time between the end of dialing and the start of ringing
can easily be 10 sec, more on long-distance or international calls.
 During this time interval, the telephone system is hunting for a path.
 In the figure, each of the six rectangles represents a carrier switching
office (end office, toll office, etc.).
 In this example, each office has three incoming lines and three
outgoing lines.
 When a call passes through a switching office, a physical connection
is (conceptually) established between the line on which the call came
in and one of the output lines, as shown by the dotted lines.
 As a consequence of the reserved path between the calling parties,
once the setup has been completed, the only delay for data is the
propagation time for the electromagnetic signal, about 5 msec per
1000 km.
 Also as a consequence of the established path, there is no danger of
congestion—that is, once the call has been put through, you never
get busy signals.

(a) Circuit switching (b) Packet switching

Packet Switching

 The alternative to circuit switching is packet switching.

 There is no need to set up a dedicated path in advance, unlike with
circuit switching.
 The routers store-and-forward each packet on its way to the
destination.
 In packet switching there is no fixed path, so different packets can
follow different paths, depending on network conditions at the time
they are sent.
 No bandwidth is reserved with packet switching; packets may have to
wait to be forwarded.

Timing of events in (a) circuit switching (b) packet switching

Item Circuit switched Packet switched

Call setup Required Not needed

Dedicated physical path Yes No

Each packet follows the same route Yes No

Packets arrive in order Yes No

Is a switch crash fatal Yes No

 Bandwidth available Fixed Dynamic

Time of possible congestion At setup time On every packet

Potentially wasted bandwidth Yes No

Store-and-forward transmission No Yes

Charging Per minute Per packet

 This introduces queuing delay and congestion if many packets are

sent at the same time.
 On the other hand, there is no danger of getting a busy signal and
being unable to use the network.
 If a circuit has been reserved for a particular user and there is no
traffic, its bandwidth is wasted. It cannot be used for other traffic.
DATA LINK LAYER
The Data Link Layer is the second layer in the OSI model, above the Physical Layer,
which ensures that the error free data is transferred between the adjacent nodes in the
network.
It breaks the datagram passed down by above layers and converts them into frames
ready for transfer. This is called Framing.
It provides two main functionalities
 Reliable data transfer service between two peer network layers
 Flow Control mechanism which regulates the flow of frames such that data
congestion is not there at slow receivers due to fast senders.
DATA LINK LAYER DESIGN ISSUES
The data link layer uses the services of the physical layer to send and receive bits
over communication channels.
It has a number of functions, including:
1. Providing a well-defined service interface to the network layer.
2. Dealing with transmission errors.
3. Regulating the flow of data so that slow receivers are not swamped by fast
senders.
To accomplish these goals, the data link layer takes the packets it gets from the
network layer and encapsulates them into frames for transmission.
Each frame contains
 Frame header
 Payload field for holding the packet
 Frame trailer
 Relationship between packets and frames

Frame management forms the heart of what the data link layer does.
Services Provided to the Network Layer
The primary function of the data link layer is to provide a well-defined service
interface to the network layer above it.
Virtual Communication versus Actual Communication
The main service provided is to transfer data packets from the network layer on the
source machine to the network layer on the destination machine.
Data link layer of the sending machine accepts data from the network layer and
sends them to the data link layer of the destination machine which hands them to the
network layer there.
In actual communication, the data link layer transmits bits via the physical layers and
physical medium.
However virtually, this can be visualized as the two data link layers communicating
with each other using a data link protocol.

Virtual communication Vs Actual communication

Types of Services
The data link layer can be designed to offer various services. The actual services that
are offered vary from protocol to protocol.
The data link layer offers three types of services.
1. Unacknowledged connectionless service
2. Acknowledged connectionless service
3. Acknowledged connection-oriented service
Unacknowledged connectionless service
 Here, the data link layer of the sending machine sends independent frames to the
data link layer of the receiving machine.
 The receiving machine does not acknowledge receiving the frame.
 No logical connection is set up between the host machines.
 Error and data loss is not handled in this service.
 This is applicable in Ethernet services and voice communications.
Acknowledged connectionless service
 Here, no logical connection is set up between the host machines, but each frame sent
by the source machine is acknowledged by the destination machine on receiving.
 If the source does not receive the acknowledgment within a stipulated time, then it
resends the frame.
 This is used in Wifi (IEEE 802.11) services.
Acknowledged connection-oriented service
 This is the best service that the data link layer can offer to the network layer.
 A logical connection is set up between the two machines and the data is transmitted
along this logical path.
 The frames are numbered, that keeps track of loss of frames and also ensures that
frames are received in correct order.
The service has three distinct phases
 Set up of connection – A logical path is set up between the source and the
destination machines. Buffers and counters are initialized to keep track of
frames.
 Sending frames – The frames are transmitted.
 Release connection – The connection is released, buffers and other resources are
released.
 It is appropriate for satellite communications and long-distance telephone circuits.
Framing
Framing is breaking or grouping the bit streams into frames.
 To provide service to the network layer, the data link layer must use the service
provided to it by the physical layer.
Physical layer is accepting a raw bit stream and deliver it to the destination. The bit
stream received by the data link layer is not guaranteed to be error free. Some bits may have
different values and the number of bits received may be less than, equal to, or more than the
number of bits transmitted.
It is up to the data link layer to detect and, if necessary, correct errors.
The usual approach is to break up the bit stream into discrete frames, compute a
short token called a checksum for each frame, and include the checksum in the frame when
it is transmitted.
When a frame arrives at the destination, the checksum is recomputed. If the newly
computed checksum is different from the one contained in the frame, the data link layer
knows that an error has occurred and takes steps to deal with it.
Four Framing methods:
 Byte count
 Flag bytes with byte stuffing
 Flag bits with bit stuffing
 Physical layer coding violations
Byte count
The first framing method uses a field in the header to specify the number of bytes in
the frame.
When the data link layer at the destination sees the byte count, it knows how many
bytes follow and hence where the end of the frame is.
This technique is shown four small example frames of sizes 5, 5, 8, and 8 bytes,
respectively.

A byte stream. (a) Without errors. (b) With one error.

 The trouble with this algorithm is that the count can be garbled by a transmission
error.

For example, if the byte count of 5 in the second frame becomes a 7, the destination
will get out of synchronization and will be unable to locate the start of the next frame.
Even if the checksum is incorrect so the destination knows that the frame is bad, it
still has no way of telling where the next frame starts.
The disadvantage is that if the count is garbled by a transmission error, the
destination will lose synchronization and will be unable to locate the start of the next frame.
So, this method is rarely used.
Flag bytes with byte stuffing
The second framing method gets around the problem of resynchronization after an
error by having each frame start and end with special bytes called a flag byte, is used as
both the starting and ending delimiter.

(a) A frame delimited by flag bytes

(b) Four examples of byte sequences before and after byte stuffing

Two consecutive flag bytes indicate the end of one frame and the start of the next.
Thus, if the receiver ever loses synchronization it can just search for two flag bytes to find
the end of the current frame and the start of the next frame.
However, there is still a problem to solve. It may happen that the flag byte occurs in
the data, especially when binary data such as photographs or songs are being transmitted.
This situation would interfere with the framing.
One way to solve this problem is to have the sender‘s data link layer insert a special
escape byte (ESC) just before each ‗‗accidental‘‘ flag byte in the data. Thus, a framing flag
byte can be distinguished from one in the data by the absence or presence of an escape byte
before it.
 The data link layer on the receiving end removes the escape bytes before giving the
data to the network layer. This technique is called byte stuffing.
This framing method is only applicable in 8-bit byte codes which are closely
associated with 8-bit characters and this is a major hurdle in transmitting arbitrary sized
characters.
Flag bits with bit stuffing
The third method of delimiting the bit stream gets around a disadvantage of byte
stuffing, which is that it is tied to the use of 8-bit bytes.
Framing can also be done at the bit level, so frames can contain an arbitrary number
of bits.
Each frame begins and ends with a special bit pattern, 01111110 called a flag byte.
When five consecutive 1‘s are encountered in the data, it automatically stuffs a ‗0‘ bit into
the outgoing bit stream. This technique is called bit stuffing.
When the receiver sees five consecutive incoming 1 bits, followed by a 0 bit, it
automatically destuffs (i.e., deletes) the 0 bit.
The boundary between two frames can be determined by locating the flag pattern.
Bit Stuffing is completely transparent to network layer as byte stuffing.
If the user data contain the flag pattern, 01111110, this flag is transmitted as
011111010 but stored in the receiver‘s memory as 01111110.

Bit stuffing
Physical layer coding violations
The final framing method is physical layer coding violations and is applicable to
networks in which the encoding on the physical medium contains some redundancy.
In such cases normally, a 1 bit is a high-low pair and a 0 bit is a low-high pair.
The combinations of low-low and high-high which are not used for data may be used
for marking frame boundaries.
Error Control
Error control in data link layer is the process of detecting and correcting data frames
that have been corrupted or lost during transmission.
 In case of lost or corrupted frames, the receiver does not receive the correct data-
frame and sender is ignorant about the loss.
Data link layer follows a technique to detect transit errors and take necessary
actions, which is retransmission of frames whenever error is detected or frame is lost. The
process is called Automatic Repeat Request (ARQ).
Phases in Error Control
The error control mechanism in data link layer involves the following phases:
 Detection of Error − Transmission error, if any, is detected by either the sender or
the receiver.
 Acknowledgment − acknowledgment may be positive or negative.
 Positive ACK − If the sender receives a positive acknowledgement about a
frame, it knows the frame has arrived safely
 Negative ACK − negative acknowledgement means that something has gone
wrong and the frame must be transmitted again.
 Retransmission − The sender maintains a clock and sets a timeout period. If an
acknowledgment of a data-frame previously transmitted does not arrive before the
timeout, or a negative acknowledgment is received, the sender retransmits the frame.
Error Control Techniques
 Stop and Wait ARQ
 Go-Back-N ARQ
 Selective Repeat
ARQ Flow Control
Another important design issue that occurs in the data link layer is what to do with a
sender that systematically wants to transmit frames faster than the receiver can accept them.
This situation can occur when the sender is running on a fast, powerful computer and
the receiver is running on a slow, low-end machine.
Flow control is a technique that allows two stations working at different speeds to
communicate with each other.
It is a set of measures taken to regulate the amount of data that a sender sends so that
a fast sender does not overwhelm a slow receiver.
In data link layer, flow control restricts the number of frames the sender can send
before it waits for an acknowledgment from the receiver.
Approaches of Flow Control
Two approaches are commonly used:
  Feedback based Flow Control - In these protocols, the sender sends frames after it
has received acknowledgments from the user. This is used in the data link layer.
 Rate based Flow Control - These protocols have built to restrict the rate of
transmission of data without requiring acknowledgment (feedback) from the
receiver. This is used in the network layer and the transport layer.

ERROR DETECTION AND CORRECTION

Most of the applications would not function expectedly if they receive erroneous
data.
Data-link layer uses some error control mechanism to ensure that frames (data bit
streams) are transmitted with certain level of accuracy.
Networks must be able to transform data from once device to another with complete
accuracy. While the transmission data is corrupted, for reliable communication, errors must
be detected and corrected.
Types of Errors
There may be three types of errors:
Single bit error
In a frame, there is only one bit, anywhere which is corrupt.
The term single-bit error means that only one bit of given data unit (such as a byte,
character, or data unit) is changed from 1 to 0 or from 0 to 1.

Multiple bits error

Frame is received with more than one bit in corrupted state.

Burst error
Frame contains more than1 consecutive bits corrupted.

Strategies for dealing error

Network designers have developed two basic strategies for dealing with errors.
 Error correcting codes
 Error Detecting Codes
Error correcting codes
The codes which are used for both error detecting and error correction are called as
―Error Correction Codes‖. The error correction techniques are of two types. They are,
 Single bit error correction: The process or method of correcting single bit
errors.
 Burst error correction: The method of detecting and correcting burst errors
in the data sequence.
Hamming code or Hamming Distance Code is the best error correcting code used in
most of the communication network and digital systems.
Error Correction can be handled in two ways:
 Backward error correction: Once the error is discovered, the receiver requests the
sender to retransmit the entire data unit.
 Forward error correction: In this case, the receiver uses the error-correcting code
which automatically corrects the errors.
Common Error Correcting Codes
Four different error-correcting codes are
 Hamming codes
 Binary convolution codes
 Reed-Solomon codes
 Low-Density Parity Check codes
Hamming Codes
Hamming code is a set of error-correction codes that can be used to detect and
correct the errors that can occur when the data is moved or stored from the sender to the
receiver.
It is technique developed by R.W. Hamming for error detection and correction.
Redundant bits
Redundant bits are extra binary bits that are generated and added to the information-
to ensure that no bits were lost during the data transfer.
Redundancy means ―The difference between number of bits of the actual data
sequence and the transmitted bits‖. These redundancy bits are used in communication
system to detect and correct the errors, if any.
In Hamming code, the redundancy bits are placed at certain calculated positions in
order to eliminate errors. The distance between the two redundancy bits is called
―Hamming distance‖.
Working Mechanism of Hamming Code
Algorithm of Hamming code to encode a message:
The procedure used by the sender to encode the message encompasses the following steps
 Step 1 − Calculation of the number of redundant bits.
 Step 2 − Positioning the redundant bits.
 Step 3 − Calculating the values of each redundant bit.
Once the redundant bits are embedded within the message, this is sent to the user.
Number of parity bits
The number of parity bits to be added to a data string depends upon the number of
information bits of the data string which is to be transmitted. Number of parity bits will be
calculated by using the data bits. This relation is given below.
2P >= n + P +1
Here, n represents the number of bits in the data string.
P represents number of parity bits.
For example, if we have 4 bit data string 1010, i.e. n = 4, then the number of parity
bits to be added can be found by using trial and error method.
Let‘s take P = 2, then
2P = 22 = 4 and n + P + 1 = 4 + 2 + 1 = 7
This violates the actual expression.
So let‘s try P = 3, then
2P = 23 = 8 and n + P + 1 = 4 + 3 + 1 = 8
So we can say that 3 parity bits are required to transfer the 4 bit data with single bit
error correction.
Determining the position of the Parity bits
After calculating the number of parity bits required, we should know the appropriate
positions to place them in the information string, to provide single bit error correction.
In the above considered example, we have 4 data bits and 3 parity bits. So the total
codeword to be transmitted is of 7 bits (4 + 3). We generally represent the data sequence
from right to left.
The number of redundant bits is 3. The three bits are represented by r1, r2, r4. The
position of the redundant bits is calculated with corresponds to the raised power of 2.
Therefore, their corresponding positions are 1, 21, 22.
The position of r1 = 1
The position of r2 = 2
The position of r4 = 4
Determining the Parity bits

 With bit position of r1-> 1, 3, 5, 7 i.e. 0, 1, 1: The total number of 1 at bit positions
corresponding to r1 is even, therefore, the value of the r1 bit is 0.
 With bit position of r2-> 2, 3, 6, 7 i.e. 0, 0, 1: The total number of 1 at bit positions
corresponding to r2 is odd, therefore, the value of the r2 bit is 1.
 With bit position of r4-> 4, 5, 6, 7 i.e. 1, 0, 1: The total number of 1 at bit positions
corresponding to r4 is even, therefore, the value of the r4 bit is 0.
Hence, by inserting the parity bits at their respective positions, codeword can be
formed and is transmitted is 1 0 1 0 0 1 0.

Data Transferred
Algorithm to decoding a message in Hamming Code:
Once the receiver gets an incoming message, it performs recalculations to detect
errors and correct them. The steps for recalculation are
 Step 1 − Calculation of the number of redundant bits.
 Step 2 − Positioning the redundant bits.
 Step 3 − Parity checking.
 Step 4 − Error detection and correction
Suppose the 4th bit is changed from 0 to 1 at the receiving end, then parity bits are
recalculated.

Calculating, positioning redundant bits and checking parity bits are done using same
formula and rules as encoding.
Parity checking
The bit positions of the r1 -> 1,3,5,7 held binary representations 1100. So the total number
of 1s appearing in the r1 bit is an even. Therefore, the value of r1 is 0.
The bit positions of r2 bit are 2,3,6,7 held binary representations 1001. So the total number
of 1s appearing in the r2 bit is an even. Therefore, the value of r2 is 0.
The bit positions of r4 bit are 4,5,6,7 held binary representations 1011. S0 the total number
of 1s in the r4 bit is an odd. Therefore, the value of r4 is 1.
Error detection and correction
The decimal equivalent of the parity bits binary values is calculated. If it is 0, there is
no error. Otherwise, the decimal value gives the bit position which has error.
The binary representation of redundant bits, i.e., r4 r2 r1 is 100, and its
corresponding decimal value is 4. Therefore, the error occurs in a 4 th bit position. The bit
value must be changed from 1 to 0 to correct the error.

Binary Convolution Code

In a convolutional code, an encoder processes a sequence of input bits and generates
a sequence of output bits.
There is no natural message size or encoding boundary as in a block code. The
output depends on the current and previous input bits. That is, the encoder has memory.
The number of previous bits on which the output depends is called the constraint
length of the code.
Convolutional codes are specified in terms of their rate and constraint length.
Convolutional codes are widely used in deployed networks, for example, as part of
the GSM mobile phone system, in satellite communications, and in 802.11.
Reed - Solomon Code
Reed-Solomon codes are linear block codes that are capable of correcting burst
errors in the received data block.
Reed - Solomon error correcting codes are one of the oldest codes that were
introduced in 1960s by Irving S.
A Reed - Solomon encoder accepts a block of data and adds redundant bits (parity
bits) before transmitting it over noisy channels. On receiving the data, a decoder corrects the
error depending upon the code characteristics.
 Reed - Solomon Code
Application Areas of Reed-Solomon Codes
 Storage areas like CDs, DVDs, Blu-ray Discs
 High speed data transmission technologies such as DSL and WiMAX
 High speed modems
 QR Codes
 Broadcast systems such as satellite communications
 Storage systems such as RAID6
Reed-Solomon codes are often used in combination with other codes such as a
convolutional code.
Convolutional codes are effective at handling isolated bit errors, but they will fail,
likely with a burst of errors, if there are too many errors in the received bit stream. By
adding a Reed-Solomon code within the convolutional code, the Reed-Solomon decoding
can mop up the error bursts. The overall code then provides good protection against both
single and burst errors.
Low-Density Parity Check Code
It is a linear block code specified by a parity-check matrix containing a low density
of 1s. They are suitable for large block sizes in very noisy channels.
LDPC codes were invented by Robert Gallagher in his doctoral thesis (1962) and
reinvented in 1995 when advances in computing power had made them practical.
In an LDPC code, each output bit is formed from only a fraction of the input bits.
This leads to a matrix representation of the code that has a low density of 1s.
The received codewords are decoded with an approximation algorithm that
iteratively improves on a best fit of the received data to a legal codeword. This corrects
errors.
LDPC codes are practical for large block sizes and have excellent error-correction
abilities.
Applications of LDPC code
 Digital video broadcasting
 10 Gbps Ethernet
 Power-line networks
 The latest version of 802.11.
Error-detecting codes
Error detection is a technique that is used to check if any error occurred in the data
during the transmission.
Whenever a message is transmitted, it may get scrambled by noise or data may get
corrupted. To avoid this, we use error-detecting codes which are additional data added to a
given digital message to help us detect if any error has occurred during transmission of the
message.
Basic approach used for error detection is the use of redundancy bits, where
additional bits are added to facilitate detection of errors.
Without error-correcting codes, it would be hard to get anything through. However,
over fiber or high-quality copper, the error rate is much lower, so error detection and
retransmission is usually more efficient for dealing with the occasional error.
Some popular techniques for error detection are
 Parity check
 Checksum
 Cyclic redundancy check
Parity check
Single Parity Check
The first error-detecting code in which a single parity bit is appended to the data.
The parity bit is chosen so that the number of 1 bit in the codeword is even or odd.
Parity checking is the simple mechanism and inexpensive to detect the errors.
In this technique, a redundant bit is also known as a parity bit which is appended at
the end of the data unit.
Blocks of data from the source are subjected to a check bit or parity bit generator
form, where a parity of
 1 is added to the block if it contains odd number of 1‘s, and
 0 is added if it contains even number of 1‘s
At the receiving end, the parity bit is calculated from the received data bits and
compared with the received parity bit.
This scheme makes the total number of 1‘s even, that is why it is called even parity
checking.
Drawbacks of Single Parity Checking
 It can only detect single-bit errors which are very rare.
 If two bits are interchanged, then it cannot detect the errors.

Two Dimensional Parity Check

Performance can be improved by using Two-Dimensional Parity Check which
organizes the data in the form of a table.
Interleaving is a general technique to convert a code that detects (or corrects)
isolated errors into a code that detects (or corrects) burst errors.
Parity check bits are computed for each row, which is equivalent to the single-parity
check.
In Two-Dimensional Parity check, a block of bits is divided into rows, and the
redundant row of bits is added to the whole block.
At the receiving end, the parity bits are compared with the parity bits computed from
the received data.

Interleaving of parity bits to detect a burst error

Checksum
A Checksum is an error detection technique based on the concept of redundancy.
In checksum error detection scheme, the data is divided into k segments each of m
bits.
In the sender‘s end, the segments are added together using 1‘s complement to get the
sum. The sum is complemented to get the checksum.
The checksum segment is sent along with the original data segments.
At the receiver‘s end, all received segments are added along with checksum using
1‘s complement to get the sum. The sum is complemented.
If the result is zero, the received data is accepted; otherwise discarded.
Example
Suppose that the sender wants to send 4 frames each of 8 bits, where the frames are
11001100, 10101010, 11110000 and 11000011.
The sender adds the bits using 1s complement arithmetic. While adding two numbers
using 1s complement, if there is a carry over, it is added to the sum.
After adding all the 4 frames, the sender complements the sum to get the checksum,
11010011, and sends it along with the data frames.
The receiver performs 1s complement arithmetic sum of all the frames including the
checksum. The result is complemented and found to be 0. Hence, the receiver assumes that
no error has occurred.

Example of Checksum method of error detection

Cyclic redundancy check (CRC)
The CRC (Cyclic Redundancy Check), also known as a polynomial
code.
CRC is based on binary division.
In CRC, called cyclic redundancy check bits are appended to the end of
data unit.
At the destination, the incoming data unit is divided by the same
number.
At sender side
Assume that, frame is 10110, code generator is 1101.
Solution:
 The generator polynomial 𝐺(𝑥) = 𝑥3 + 𝑥2 + 1is encoded as 1101.
 Clearly, the generator polynomial consists of 4 bits.
 So, a string of 3 zeroes is appended to the bit stream to be
transmitted.
 The resulting bit stream is 10110000.

Cyclic redundancy check is 101. Thus, the sender sends 10110101

to the receiver.
At Receiver Side
 Receiver has same generator G(x).
 Receiver divides received data (data + CRC) with generator.
 If remainder is zero, data is correctly received.
 Else, there is error.
Assume the received message is 10110110.
 The CRC bits are different. Thus, there is an error detected.

Polynomial codes
 A pattern of Os and 1s can be represented as a polynomial with
coefficient of o and 1.

 Here, the power of each term shows the position of the bit and the
coefficient shows the values of the bit.

 For example, if binary pattern is 100101, its corresponding

polynomial representation is 𝑥5 + 𝑥2 + 1.

UNIT – III

Protocols in the data link layer are designed so that this layer can perform its
basic functions: framing, error control and flow control. Framing is the process of
dividing bit - streams from physical layer into data frames whose size ranges
from a few hundred to a few thousand bytes. Error control mechanisms deals
with transmission errors and retransmission of corrupted and lost frames. Flow
control regulates speed of delivery and so that a fast sender does not drown a
slow receiver.

Types of Data Link Protocols

Data link protocols can be broadly divided into two categories, depending on
whether the transmission channel is noiseless or noisy.
Simplex Protocol
The Simplex protocol is hypothetical protocol designed for unidirectional data
transmission over an ideal channel, i.e. a channel through which transmission
can never go wrong. It has distinct procedures for sender and receiver. The
sender simply sends all its data available onto the channel as soon as they are
available its buffer. The receiver is assumed to process all incoming data
instantly. It is hypothetical since it does not handle flow control or error control.

Stop - and - Wait Protocol

Stop - and - Wait protocol is for noiseless channel too. It provides unidirectional
data transmission without any error control facilities. However, it provides for
flow control so that a fast sender does not drown a slow receiver. The receiver
has a finite buffer size with finite processing speed. The sender can send a frame
only when it has received indication from the receiver that it is available for
further data processing.

Stop - and - Wait ARQ

Stop - and - wait Automatic Repeat Request (Stop - and - Wait ARQ) is a variation
of the above protocol with added error control mechanisms, appropriate for noisy
channels. The sender keeps a copy of the sent frame. It then waits for a finite
time to receive a positive acknowledgement from receiver. If the timer expires or
a negative acknowledgement is received, the frame is retransmitted. If a positive
acknowledgement is received then the next frame is sent.

Go - Back - N ARQ
Go - Back - N ARQ provides for sending multiple frames before receiving the
acknowledgement for the first frame. It uses the concept of sliding window, and
so is also called sliding window protocol. The frames are sequentially numbered
and a finite number of frames are sent. If the acknowledgement of a frame is not
received within the time period, all frames starting from that frame are
retransmitted.

Selective Repeat ARQ

This protocol also provides for sending multiple frames before receiving the
acknowledgement for the first frame. However, here only the erroneous or lost
frames are retransmitted, while the good frames are received and buffered.

Elementary Data Link protocols are classified into three categories, as given
below
 Protocol 1 − Unrestricted simplex protocol
 Protocol 2 − Simplex stop and wait protocol
 Protocol 3 − Simplex protocol for noisy channels.
Let us discuss each protocol one by one.

Unrestricted Simplex Protocol

Data transmitting is carried out in one direction only. The transmission (Tx)
and receiving (Rx) are always ready and the processing time can be ignored. In
this protocol, infinite buffer space is available, and no errors are occurring that is
no damage frames and no lost frames.
The Unrestricted Simplex Protocol is diagrammatically represented as follows −
Simplex Stop and Wait protocol

In this protocol we assume that data is transmitted in one direction only.

No error occurs; the receiver can only process the received information at finite
rate. These assumptions imply that the transmitter cannot send frames at rate
faster than the receiver can process them.
The main problem here is how to prevent the sender from flooding the receiver.
The general solution for this problem is to have the receiver send some sort of
feedback to sender, the process is as follows −
Step1 − The receiver send the acknowledgement frame back to the sender
telling the sender that the last received frame has been processed and passed to
the host.
Step 2 − Permission to send the next frame is granted.
Step 3 − The sender after sending the sent frame has to wait for an
acknowledge frame from the receiver before sending another frame.
This protocol is called Simplex Stop and wait protocol, the sender sends one
frame and waits for feedback from the receiver. When the ACK arrives, the
sender sends the next frame.
The Simplex Stop and Wait Protocol is diagrammatically represented as follows −

Simplex Protocol for Noisy Channel

Data transfer is only in one direction, consider separate sender and
receiver, finite processing capacity and speed at the receiver, since it is a noisy
channel, errors in data frames or acknowledgement frames are expected. Every
frame has a unique sequence number.
After a frame has been transmitted, the timer is started for a finite time. Before
the timer expires, if the acknowledgement is not received , the frame gets
retransmitted, when the acknowledgement gets corrupted or sent data frames
gets damaged, how long the sender should wait to transmit the next frame is
infinite.
The Simplex Protocol for Noisy Channel is diagrammatically represented as
follows −

SLIDING WINDOW PROTOCOLS

 A One-Bit Sliding Window Protocol
 A Protocol Using Go-Back-N
 A Protocol Using Selective Repeat

 Sliding window protocols are data link layer protocols for reliable and
sequential delivery of data frames.

 The sliding window is also used in Transmission Control Protocol.

 In this protocol, multiple frames can be sent by a sender at a time

before receiving an acknowledgment from the receiver.
  Sliding window method is also known as windowing.

Piggybacking

 When a data frame arrives, instead of immediately sending a

separate control frame, the receiver restrains itself and waits until
the network layer passes it the next packet.
 The acknowledgement is attached to the outgoing data frame (using
the ack field in the frame header).
 In effect, the acknowledgement gets a free ride on the next outgoing
data frame.
 The technique of temporarily delaying outgoing acknowledgements so
that they can be hooked onto the next outgoing data frame is known
as piggybacking.
A One-Bit Sliding Window Protocol

 One bit sliding window protocol is also called Stop-And-Wait protocol.

 In this protocol, the sender sends out one frame, waits for
acknowledgment before sending next frame.
 Problem with Stop-And-Wait protocol is that it is very inefficient.
 The sender will have to wait at least one round trip time before
sending next.

Two scenarios for protocol 4. (a) Normal case. (b) Abnormal case. The
notation is (seq, ack, packet number). An asterisk indicates where a
network layer accepts a packet
 A Protocol Using Go-Back-N

 Go – Back – N ARQ provides for sending multiple frames before

receiving the acknowledgment for the first frame. It uses the concept
of sliding window.
 The frames are sequentially numbered and a finite number of frames
are sent.
 If the acknowledgment of a frame is not received within the time
period, all frames starting from that frame are retransmitted.
Example: Consider MAX SEQ = 7

1. The sender sends frames 0 through 7.

2. A piggybacked acknowledgement for 7 comes back to the sender.
3. The sender sends another eight frames, again with sequence
numbers 0 through 7.
4. Now another piggybacked acknowledgement for frame 7 comes in.
A protocol using Selective Repeat
 This protocol also provides for sending multiple frames before
receiving the acknowledgment for the first frame.
 Here only the erroneous or lost frames are retransmitted, while the
good frames are received and buffered.
Data link layer in the Internet
The Data Link Layer, which is the second layer in the OSI (Open Systems
Interconnection) model, is responsible for node-to-node data transfer and error detection and
correction. In the context of the Internet, it deals with protocols that ensure that data sent from the
physical layer of a device is properly formatted for network communication. Two notable
protocols used at this layer are SLIP (Serial Line Internet Protocol) and PPP (Point-to-Point
Protocol).

SLIP (Serial Line Internet Protocol)

Overview:

 Purpose: SLIP is an older protocol used for encapsulating IP packets over serial connections,
such as telephone lines and serial cables.
 Functionality: It provides a simple framing method for transmitting data packets.
 Limitations:
o No Error Detection: SLIP does not provide error detection or correction. Any errors must be
handled by higher layers.
o No Compression: SLIP lacks any compression mechanisms.
o No Authentication: There is no built-in mechanism for authenticating the endpoints of the
connection.
How it Works:

 SLIP frames are essentially IP packets with a special byte (typically 0xC0) to signal the start and
end of each packet.
 If this special byte appears within the data, it is “escaped” using a sequence of bytes to ensure it is
not misinterpreted as a packet boundary.
Usage:

 SLIP was widely used in the early days of the Internet for connecting computers over serial lines,
but it has largely been replaced by more robust protocols like PPP.
PPP (Point-to-Point Protocol)

Overview:

 Purpose: PPP is designed for point-to-point links and provides a more comprehensive and
versatile solution than SLIP.
 Functionality: It encapsulates network layer protocol information, provides error detection,
supports authentication, and allows for link configuration and management.
 Advantages over SLIP:
o Error Detection: PPP includes mechanisms for detecting and correcting errors in transmission.
o Compression: It supports data compression to improve transmission efficiency.
o Authentication: PPP supports authentication protocols like PAP (Password Authentication
Protocol) and CHAP (Challenge Handshake Authentication Protocol).
How it Works:

 Frame Structure: PPP frames include a framing byte, address field, control field, protocol field,
data, and a Frame Check Sequence (FCS) for error detection.
 Link Control Protocol (LCP): Manages the establishment, configuration, and testing of the
data-link connection.
 Network Control Protocol (NCP): Allows for the configuration of various network layer
protocols (e.g., IP, IPX).
Usage:
 PPP is extensively used for dial-up Internet access, DSL connections, and VPNs (Virtual Private
Networks). It is versatile and can be used over various physical media, including serial cables,
phone lines, cellular connections, and fiber optic links.
Key Differences Between SLIP and PPP

1. Error Handling:
o SLIP: No error detection/correction.
o PPP: Includes error detection and correction mechanisms.
2. Authentication:
o SLIP: No authentication.
o PPP: Supports multiple authentication protocols (PAP, CHAP).
3. Compression:
o SLIP: Does not support compression.
o PPP: Supports data compression.
4. Flexibility and Extensibility:
o SLIP: Simple and limited.
o PPP: More complex but highly extensible and configurable.

CHANNEL ALLOCATION PROBLEM

 Static Channel Allocation

 Assumptions for Dynamic Channel Allocation

 Channel allocation is a process in which a single channel is divided

and allotted to multiple users in order to carry user specific tasks.
 The channel might be a portion of the wireless spectrum in a
geographic region, or a single wire or optical fiber to which multiple
nodes are connected.
  If there are N number of users and channel is divided into N equal-
sized sub channels, Each user is assigned one portion.
 Channel allocation problem can be solved by two schemes: Static
Channel Allocation in LANs and MANs, and Dynamic Channel
Allocation.

Static Channel Allocation

 It is the classical or traditional approach of allocating a single

channel among multiple competing users such as FDM (Frequency
Division Multiplexing).
 If there are N users, the bandwidth is divided into N equal-sized
portions, with each user being assigned one portion.
 Since each user has a private frequency band, there is now no
interference among users.
 A wireless example is FM radio stations. Each station gets a portion
of the FM band and uses it most of the time to broadcast its signal.
 If the spectrum is cut up into N regions and fewer than N users are
communicating, a large piece of spectrum will be wasted.
 If more than N users want to communicate, some of them will be
denied permission for lack of bandwidth.
 The basic problem is that when some users are inactive, their
bandwidth is simply lost. They are not using it, and no one else is
allowed to use it either.

1
 Standard queuing theory result is,

𝑇
= 𝝁𝐶 −
Where, 𝛌
T = mean time delay,
C = capacity of channel,
λ = arrival rate of
frames,
1
𝜇
= bits/frame.
Assumptions for Dynamic Channel Allocation
1. Independent Traffic
 The model consists of N independent stations (e.g.,
computers, telephones), each generates frames for
transmission.
  The expected number of frames generated in an interval of
length Δt is λΔt, where λ is a constant (the arrival rate of
new frames).
 Once a frame has been generated, the station is blocked
and does nothing until the frame has been successfully
transmitted.
2. Single Channel
 A single channel is available for all communication.
 All stations can transmit on it and all can receive from it.
 The stations are assumed to be equally capable, though
protocols may assign them different roles (e.g., priorities).
3. Observable Collisions
 If two frames are transmitted simultaneously, they overlap
in time and the resulting signal is garbled. This event is
called a collision.
 All stations can detect that a collision has occurred. A
collided frame must be transmitted again later.
4. Continuous or Slotted Time
 Time may be assumed continuous, in which frame
transmission can begin at any instant.
 Alternatively, time may be slotted or divided into discrete
intervals (called slots).
 Frame transmissions must then begin at the start of a slot
5. Carrier Sense or No Carrier Sense
 With the carrier sense assumption, stations can tell if the
channel is in use before trying to use it.
 No station will attempt to use the channel while it is sensed
as busy.
 If there is no carrier sense, stations cannot sense the
channel before trying to use it. They just go ahead and
transmit.
 Only later can they determine whether the transmission
was successful.
Protocol Assumption
 N independent stations.
 A station is blocked until its generated frame is transmitted.
 Only a single Channel available.
 Time can be either: Continuous or slotted.
 Carrier Sense: A station can sense if a channel is already busy
before transmission.
 No Carrier Sense: Time out used to sense loss data.
MULTIPLE ACCESS PROTOCOLS

 ALOHA
 Carrier Sense Multiple Access Protocols
 Collision-Free Protocols
 Limited-Contention Protocols
  If there is a dedicated link between the sender and the receiver then
data link control layer is sufficient.
 If there is no dedicated link present then multiple stations can access
the channel simultaneously. Hence multiple access protocols are
required to decrease collision.
ALOHA
 There are two different versions of ALOHA:
 Pure ALOHA
 Slotted ALOHA
Pure ALOHA
 Users transmit whenever they have data to be sent.
 There will be collisions, and the colliding frames will be damaged.
 In the ALOHA system, after each station has sent its frame to the
central computer, this computer rebroadcasts the frame to all of the
stations.
 A sending station listens for the broadcast from the hub to see if its
frame has gotten through.
 If the frame was destroyed, the sender just waits a random amount of
time and sends it again.
 The waiting time must be random or the same frames will collide over
and over.
 Systems in which multiple users share a common channel in a way
that can lead to conflicts are known as contention systems.
 Whenever two frames try to occupy the channel at the same time,
there will be a collision.
 Let us consider an infinite collection of users typing at their terminals
(stations).

 A user is always in one of two states: typing or waiting. Initially, all

users are in the typing state.
 When a line is finished, the user stops typing, waiting for a response.
The station then transmits a frame and checks the channel to see if
it was successful.
 If so, the user sees the reply and goes back to typing.
 If not, the user continues to wait while the station retransmits the
frame until it has been successfully sent.

Slotted ALOHA
 A station is not permitted to send whenever the user types a line.
Instead, it is required to wait for the beginning of the next slot.
Carrier Sense Multiple Access Protocols
 Protocols in which stations listen for a carrier (i.e., a transmission)
and act accordingly are called carrier sense protocols.
 There Are Three Different Type of CSMA Protocols
1. 1-persistent CSMA
2. Non- Persistent CSMA
3. p-persistent CSMA

Persistent CSMA
 When a station has data to send, it first listens to the channel to see
if anyone else is transmitting at that moment. If the channel is idle,
the station sends its data.
  Otherwise, if the channel is busy, the station just waits until it
becomes idle. Then the station transmits a frame.
 If a collision occurs, the station waits a random amount of time and
starts again.
 The protocol is called 1-persistent because the station transmits with
a probability of 1 when it finds the channel idle.
Nonpersistent CSMA
 A station senses the channel when it wants to send a frame, and if
no one else is sending, the station sends the frame.
 If the channel is already in use, the station does not continually
sense it.
 Instead, it waits a random period of time and then repeats the
algorithm.
P-persistent CSMA
 It applies to slotted channels.
 When a station becomes ready to send, it senses the channel. If it is
idle, it transmits with a probability p.
 With a probability (1 – p), the channel waits for next time slot. If the
next time slot is idle, it again transmits with a probability p and waits
with a probability (1 – p).
CSMA with Collision Detection
 When a frame is ready, the transmitting station checks whether the
channel is idle or busy.
 If the channel is busy, the station waits until the channel becomes
idle.
 If the channel is idle, the station starts transmitting and continually
monitors the channel to detect collision.
 If a collision is detected, the station stops transmitting, sends a jam
signal, and then waits for a random time interval before
retransmission.
Collision-Free Protocols
Bit – map Protocol
 In bit map protocol, the contention period is divided into N slots,
where N is the total number of stations sharing the channel.
 If a station has a frame to send, it sets the corresponding bit in the
slot.
 So, before transmission, each station knows whether the other
stations want to transmit.
  Collisions are avoided by mutual agreement among the contending
stations on who gets the channel.
 Protocols in which the desire to transmit is broadcast before the
actual transmission are called reservation protocols because they
reserve channel ownership in advance and prevent collisions.

Token Passing
 In token passing scheme, the stations are connected logically to
each other in form of ring.
 A token is a special bit pattern or a small message, which circulate
from one station to the next in predefined order.
 In Token ring, token is passed from one station to another adjacent
station in the ring.

 Token represents permission to send. If a station has a frame

queued for transmission when it receives the token, it can send that
frame before it passes the token to the next station. If it has no
queued frame, it passes the token simply.
 After sending a frame, each station must wait for all N stations to
send the token to their neighbors.
Binary Countdown
 Binary addresses of equal lengths are assigned to each station.
 For example, if there are 6 stations, they may be assigned the binary
addresses 001, 010, 011, 100, 101 and 110.
 All stations wanting to communicate broadcast their addresses.
 The station with higher address gets the higher priority for
transmitting.
Limited Contention Protocols
 These protocols combines the advantages of collision based protocols
and collision free protocols.
 Under light load, they behave like ALOHA scheme. Under heavy load,
they behave like bitmap protocols.
Adaptive Tree Walk Protocol
 In adaptive tree walk protocol, the stations or nodes are arranged in
the form of a binary tree.

 Initially all nodes (A, B ……. G, H) are permitted to compete for the
channel.
 If a node is successful in acquiring the channel, it transmits its
frame.
 In case of collision, the nodes are divided into two groups (A, B, C, D
in one group and E, F, G, H in another group).
 Nodes belonging to only one of them is permitted for competing. This
process continues until successful transmission occurs.
Wireless LAN Protocols
 Wireless LAN (WLAN) connects the local area network with a wireless
connection.
 A station on a wireless LAN may not be able to transmit frames to or
receive frames from all other stations because of the limited radio
range of the stations.
 Eg: consider where four wireless stations. The radio range is such that A
and B are within each other‘s range can interfere with one another. C can
also interfere with both B and D, but not with A.

(a) A and C are hidden terminals when transmitting to B

(b) B and C are exposed terminals when transmitting to A and D

 The problem of a station not able to detect a competitor for the

medium because the competitor is too far away is called the hidden
terminal problem.
 When the node is within the range of a node that is transmitting and
it cannot be transmitted to any node is called Exposed terminal
problem.
Multiple Access with Collision Avoidance (MACA)

 Multiple Access with Collision Avoidance (MACA) is a medium access

control (MAC) layer protocol used in wireless networks to solve the
hidden terminal problem.
 It also provides solution to the exposed terminal problem.

(a) A sending an RTS to B (b) B responding with a CTS to A

A transmitting station A has data frame to send to a receiving station B.
 Station A sends a RTS frame to the receiving station.
 On receiving the RTS, station B replies by sending a CTS frame.
 On receipt of CTS frame, station A begins transmitting its data frame.
 After successful receipt of the data frame, station B sends an ACK
frame (acknowledgement frame).
BLUETOOTH:
Bluetooth is used for short-range wireless voice and data communication. It is a
Wireless Personal Area Network (WPAN) technology and is used for data communications
over smaller distances. This generation changed into being invented via Ericson in 1994. It
operates within the unlicensed, business, scientific, and clinical (ISM) bands from 2.4 GHz to
2.485 GHz.
Bluetooth stages up to 10 meters. Depending upon the version, it presents information up to at
least 1 Mbps or 3 Mbps. The spreading method that it uses is FHSS (Frequency-hopping unfold
spectrum). A Bluetooth network is called a piconet and a group of interconnected piconets is
called a scatter net.
Bluetooth
Bluetooth is a wireless technology that lets devices like phones, tablets, and headphones
connect to each other and share information without needing cables. Bluetooth simply follows
the principle of transmitting and receiving data using radio waves. It can be paired with the
other device which has also Bluetooth but it should be within the estimated communication
range to connect. When two devices start to share data, they form a network called piconet
which can further accommodate more than five devices.
Key Features of Bluetooth
 The transmission capacity of Bluetooth is 720 kbps.
 Bluetooth is a wireless technology.
 Bluetooth is a Low-cost and short-distance radio communications standard.
 Bluetooth is robust and flexible.
 The basic architecture unit of Bluetooth is a piconet.
Architecture of Bluetooth
The architecture of Bluetooth defines two types of networks:
Piconet
Piconet is a type of Bluetooth network that contains one primary node called the master node
and seven active secondary nodes called slave nodes. Thus, we can say that there is a total of 8
active nodes which are present at a distance of 10 meters. The communication between the
primary and secondary nodes can be one-to-one or one-to-many. Possible communication is
only between the master and slave; Slave-slave communication is not possible. It also has 255
parked nodes, these are secondary nodes and cannot take participation in communication unless
it gets converted to the active state.

Scatternet
It is formed by using various piconets. A slave that is present in one piconet can act as
master or we can say primary in another piconet. This kind of node can receive a message from
a master in one piconet and deliver the message to its slave in the other piconet where it is
acting as a master. This type of node is referred to as a bridge node. A station cannot be
mastered in two piconets.

Bluetooth Protocol Stack

 Radio (RF) Layer: It specifies the details of the air interface, including frequency, the use
of frequency hopping and transmit power. It performs modulation/demodulation of the data
into RF signals. It defines the physical characteristics of Bluetooth transceivers. It defines
two types of physical links: connection-less and connection-oriented.
 Baseband Link Layer: The baseband is the digital engine of a Bluetooth system and is
equivalent to the MAC sublayer in LANs. It performs the connection establishment within
a piconet, addressing, packet format, timing and power control.
 Link Manager Protocol Layer: It performs the management of the already established
links which includes authentication and encryption processes. It is responsible for creating
the links, monitoring their health, and terminating them gracefully upon command or
failure.
 Logical Link Control and Adaption (L2CAP) Protocol Layer: It is also known as the
heart of the Bluetooth protocol stack. It allows the communication between upper and lower
layers of the Bluetooth protocol stack. It packages the data packets received from upper
layers into the form expected by lower layers. It also performs segmentation
and multiplexing.
 Service Discovery Protocol (SDP) Layer: It is short for Service Discovery Protocol. It
allows discovering the services available on another Bluetooth-enabled device.
 RF Comm Layer: It is a cabal replacement protocol. It is short for Radio Frontend
Component. It provides a serial interface with WAP and OBEX. It also provides emulation
of serial ports over the logical link control and adaption protocol(L2CAP). The protocol is
based on the ETSI standard TS 07.10.
 OBEX: It is short for Object Exchange. It is a communication protocol to exchange objects
between 2 devices.
 WAP: It is short for Wireless Access Protocol. It is used for internet access.
 TCS: It is short for Telephony Control Protocol . It provides telephony service. The basic
function of this layer is call control (setup & release) and group management for the
gateway serving multiple devices.
 Application Layer: It enables the user to interact with the application.
Types of Bluetooth
Various types of Bluetooth are available in the market nowadays. Let us look at them.
 In-Car Headset: One can make calls from the car speaker system without the use of mobile
phones.
 Stereo Headset: To listen to music in car or in music players at home.
 Webcam: One can link the camera with the help of Bluetooth with their laptop or phone.
 Bluetooth-Equipped Printer: The printer can be used when connected via Bluetooth with
mobile phone or laptop.
 Bluetooth Global Positioning System (GPS): To use Global Positioning System (GPS) in
cars, one can connect their phone with car system via Bluetooth to fetch the directions of
the address.

UNIT - 4
NETWORK
LAYER
 The network layer is concerned with getting packets from the source
all the way to the destination with minimal cost.
 The network layer is the lowest layer that deals with end-to-end
transmission.
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 ISP.
 The 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.
 This mechanism is store-and-forward packet switching.

Services Provided to the Transport Layer

 The network layer provides services to the transport layer at the

network layer/transport layer interface.
 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

 If connectionless service is offered, packets are injected into the

network individually and routed independently of each other.
 No advance setup is needed.
 In this context, the packets are called datagrams and the network is
called a datagram network.
 If connection-oriented service is used, a path from the source router
to the destination router must be established before any data packets
can be sent. Similar to the physical circuits set up by the telephone
system.
 This connection is called a VC (virtual circuit), and the network is
called a virtual-circuit network.
  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.
 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.

 A connection is established from the source machine to the
destination machine.
 That route is used for all traffic flowing over the connection, exactly
the same way that the telephone system works.
 With connection-oriented service, each packet carries an identifier
telling which virtual circuit it belongs to.
 This process is called label switching.
 MPLS (MultiProtocol Label Switching)
 MPLS is close to circuit switching.
 It adds a label in front of each packet and forwarding is
based on the label rather than the destination address.




 Comparison of Virtual-Circuit and Datagram Networks


Issue Datagram network Virtual-circuit network

Circuit setup Not needed Required

Addressing Each packet contains the Each packet contains a

full source and short VC number
destination address
 State Routers do not hold state Each VC requires router
information information about table space per
connections connection

Routing Each packet is routed Route chosen when VC is

independently set up; all packets follow
it

Effect of router None, except for packets All VCs that passed
failures lost during the crash through the failed router
are terminated
Quality of Difficult Easy if enough resources
service can be allocated in
advance for each VC

Congestion Difficult Easy if enough resources

control can be allocated in
advance for each VC

ROUTING ALGORITHMS
 The Optimality Principle
 Shortest Path Algorithm
 Flooding
 Distance Vector Routing
 Link State Routing
 Hierarchical Routing
 Broadcast Routing
 Multicast Routing
 Anycast Routing
 Routing for Mobile Hosts
 Routing in Ad Hoc Networks

 The routing algorithm is the part of the network layer software

responsible for deciding which output line an incoming packet
should be transmitted on.
 If the network uses datagrams internally, the routing decision must
be made for each datagram.
 If the network uses virtual circuits internally, routing decisions are
made only when a new virtual circuit is being set up.
 Thereafter, data packets just follow the already established route.
This is sometimes called session routing because a route remains in
force for an entire session.
Types of routing algorithm
 Routing algorithms can be grouped into two major classes:
1. Nonadaptive routing and
 2. Adaptive routing
Nonadaptive routing
 This algorithm is also known as static routing algorithm.
 The Non-Adaptive Routing algorithm is an algorithm that constructs
the static table to determine which node to send the packet.
Adaptive routing
 This algorithm is also known as dynamic routing algorithm.
 Adaptive Routing algorithm is an algorithm that constructs the
routing table based on the network conditions.
The Optimality Principle

 The set of optimal routes from all sources to a given destination form
a tree. Such a tree is called a sink tree.

(a) A network (b) A sink tree for router B

 If we allow all of the possible paths to be chosen, the tree becomes a
more general structure called a DAG (Directed Acyclic Graph).
DAGs have no loops.
Hierarchical Routing

 The network is divided into different routers called 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.

Broadcast Routing
  In some applications, hosts need to send messages to many or all
other hosts.
 For example, a service distributing weather reports, stock market
updates, or live radio programs might work best by sending to all
machines and letting those that are interested read the data.
 Sending a packet to all destinations simultaneously is called
broadcasting.
 Multidestination routing: In multi destination routing, each packet
contains either a list of destinations or a bit map indicating the
desired destinations.
 When a packet arrives at a router, the router checks all the
destinations to determine the set of output lines.
 The router generates a new copy of the packet for each output lines.
Multicast Routing
 Some applications, such as a multiplayer game or live video of a
sports event streamed to many viewing locations, send packets to
multiple receivers.
 Most receivers are not interested in the message. Thus, we need a
way to send messages to well-defined groups.
 Sending a message to such a group is called multicasting, and the
routing algorithm used is called multicast routing.
 Each group is identified by a multicast address and the routers know
the groups to which they belong.
 DVMRP (Distance Vector Multicast Routing Protocol) is an
example of a multicast routing protocol.
Anycast Routing
 In anycast, a packet is delivered to the nearest member of a group.
Schemes that find these paths are called anycast routing.
 Distance vector and link state routing can produce anycast routes.

Routing for Mobile Hosts

 The mobile host is assumed to have a permanent IP address, called

its home address.
 All hosts are assumed to have a permanent home location that
never changes.
 Each host also has a permanent home address.
  The routing with mobile hosts is to make it possible to send packets
to mobile hosts using their fixed home addresses.
 A router on a mobile node's home network allows the movement of
datagrams to the mobile node when it is away from home is called
home agent.
 The local address is called a care of address. Once the mobile host
has this address, it can tell its home agent where it is now.
 Next, the sender sends a data packet to the mobile host using its
permanent address.
 The home agent intercepts the packet. It then wraps or encapsulates
the packet with a new header and sends to the care of address. This
mechanism is called tunneling.
Routing in Ad Hoc Networks
 Ad hoc network or MANETs (Mobile Ad hoc NETworks) is a chain
of devices that are connected each other instead of connecting to a
central access point such as server or router.
 Example: AODV (Ad hoc On-demand Distance Vector)
 Ad Hoc On-Demand Distance Vector, AODV is a routing protocol for
ad hoc mobile networks with large numbers of mobile nodes.
 The protocol's algorithm creates routes between nodes only when the
routes are requested by the source nodes.

ROUTING ALGORITHMS
SHORTEST PATH ALGORITHM
 Shortest path routing, the path length between each node is
measured as a function of the distance, bandwidth, average traffic,
communication cost, measured delay, and other factors.
 The algorithm then computes the ‗‗shortest‘‘ path according to any
one of a number of criteria or to a combination of criteria.
 Algorithms for computing the shortest path between two nodes of a
graph:
 Dijkstra algorithm
 Bellman Ford algorithm
Dijkstra algorithm / Link State routing

 It finds the shortest paths between a source and all destinations in

the network.
 Each node is labeled with its distance from the source node along the
best known path.
 The distances must be non-negative; they are based on real
quantities like bandwidth and delay.
 Initially, no paths are known, so all nodes are labeled with infinity.
 As the 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 found that a label represents the shortest possible path, it
is made permanent and never changed thereafter.

 In the above graph, the weights represent the distance. We want to

find the shortest path from A to D. We start out by marking node A
as permanent, indicated by a filled-in circle.
 Then we examine, each of the nodes adjacent to A, relabeling each
one with the distance to A.

 After examining each of the nodes adjacent to A, the tentative node

with smallest distance is made permanent.
 We now start at B and examine all nodes adjacent to it.
 If the sum of the label on B and the distance from B to the node is
less than the label on that node, the node is relabeled.
 The algorithm is repeated until the destination is reached.

Bellman Ford algorithm

 The Bellman–Ford algorithm is an algorithm that computes shortest

paths from source to destination in a weighted digraph.
 Bellman-Ford is capable of handling graphs that contain negative
edge weights.
 If a graph contains a "negative cycle" that is reachable from the
source and is the cheapest path.
ROUTING ALGORITHM

FLOODING
 Flooding is a static routing algorithm. In this algorithm, every
incoming packet is sent out on every outgoing line except the line on
which it is arrived on.
 One major problem of this algorithm is that it generates a large
number of duplicate packets on the network.
 Several measures are taken to stop the duplication of packets. They
are:
 To include a hop counter in the header of each packet. This
counter is decremented at each hop along the path. When this
counter reaches zero, the packet is discarded. Ideally, the hop
counter should become zero at the destination. Indicating that the
destination is reached.
 To keep the track of the packets, those have been flooded to avoid
sending them second time. For this, the source router put a
sequence number in each packet.
 Another solution is selective flooding. In selective flooding, the
routers do not send every incoming packet out on every output
lines. Instead, packet is sent only on those lines which are
approximately going in the right direction.
Unicast routing
 Unicast means the transmission from a single sender to a single
receiver.
 It is a point to point communication between sender and receiver.
 There are various unicast protocols such as TCP, HTTP, etc.

Broadcast routing

 In broadcast routing, packets are sent to all nodes.

 A broadcast message is destined to all network devices.
 A router creates a data packet and then sends it to each host one
by one.
 In this case, the router creates multiple copies of single data
packet with different destination addresses.
Anycast routing
 In anycast, a packet is delivered to the nearest member of a group.
Schemes that find these paths are called anycast routing.
 Distance vector and link state routing can produce anycast routes.
 ROUTING ALGORITHMS
DISTANCE VECTOR ROUTING
 In distance vector routing algorithm, each router maintain a table
(i.e., a vector) giving the best known distance to each destination and
which link to use.
 These tables are updated by exchanging information with the
neighbors.
 The distance vector routing algorithm is sometimes called distributed
Bellman-Ford routing algorithm.
How DVR Works
 Each router prepares its routing table. By their local knowledge.
 Each router knows about
 All the routers present in the network
 Distance to its neighboring routers
 Each router exchanges its distance vector with its neighboring
routers.
 Each router prepares a new routing table using the distance vectors
it has obtained from its neighbors.
 After this, routing tables converge / become stable.
Example:
Consider-
 There is a network consisting of 4 routers.
 The weights are mentioned on the edges.
 Weights could be distances or costs or delays.

∞
Routing table for the network. B 2 B
C -
A’s table
D 1 D
Destination Distance Next hop
C’s table
A 0 A
B’s Table
Destination Distance Next hop
A 2 A
B 0 B
C 3 C
D 7 D

D’s Table
 ∞
Destination Distance Next hop Destination Distance Next hop
A - A 1 A
B 3 B B 7 B
C 0 C C 11 C
D 11 D D 0 D

 Now, the router exchanges its obtained distance vector with its
neighbors.
 After exchanging the distance vectors, each router prepares a new
routing table.
 Router A receives distance vectors from its neighbors B and D.
 Router A prepares a new routing table as-

Cost of reaching destination B from router A = min { 2+0 , 1+7 } = 2 via B.

Cost of reaching destination C from router A = min { 2+3 , 1+11 } = 5 via B.

Cost of reaching destination D from router A = min { 2+7 , 1+0 } = 1 via D.

Thus, the new routing table at router A is-

A’s table

Destination Distance Next hop

A 0 A
B 2 B
C 5 B
D 1 D

 In Dynamic vector routing, each route shares the information between

the neighbors.
Sharing process
 Periodic update
o A node sends its table, normally every 30s, in a periodic update.
 Triggered update
o A node sends its two-column routing table to its neighbors
anytime, when there is a change in its routing table.
Count to infinity problem
  One of the important issues in Distance Vector Routing is County of
Infinity Problem.
 Counting to infinity is just another name for a routing loop.
 In distance vector routing, routing loops usually occur when an
interface goes down.
 It can also occur when two routers send updates to each other at the
same time.
CONGESTION CONTROL ALGORITHM
 Approaches to Congestion Control
 Traffic-Aware Routing
 Admission Control
 Traffic Throttling
 Load Shedding

 Too many packets present in the network cause packet delay and loss
that degrades performance. This situation is called congestion.
 The network and transport layers share the responsibility for handling
congestion.
 When the number of packets send into the network is more than the
carrying capacity, is called the congestion collapse.
Approaches to Congestion Control
 The presence of congestion means that the load is greater than the
resources can handle.
 Two solutions: increase the resources or decrease the load.

Approaches to congestion control

Network provisioning
 Network provisioning adds and upgrades resources to handle traffic.
 Provisioning is the process of providing new services to its users by
the network.
 Network provisioning is mostly used in the telecommunication
industry.
Traffic-Aware Routing
 These schemes adapted to changes in topology, but not to changes in
load. When computing routes, traffic should be shifted away from
hotspots.
 In the image below, the network is divided into two parts, East and
West, connected by two links, CF and EI.
 Suppose that most of the traffic between East and West is using link
CF, and as a result, this link is heavily loaded with long delays.
  After the new routing tables have been installed, most of the East-
West traffic will now go over EI, loading this link.
 Consequently, in the next update, CF will appear to be the shortest
path.
 Adjustments are made outside the routing protocol by slowly
changing its inputs. This is called traffic engineering.

Admission Control
 Only admit traffic when the network can handle it without congestion.
 Once congestion has been signaled, no more virtual circuits are set up
until the problem has gone away.
 Example: In the telephone system, when a switch gets overloaded it
practices admission control by not giving dial tones.

 Suppose that a host attached to router A wants to set up a connection

to a host attached to router B.
 Normally, this connection would pass through one of the congested
routers.
 To avoid this situation, we can redraw the subnet by omitting the
congested routers and all of their lines.
 The dashed line shows a possible route for the virtual circuit that
avoids the congested routers.
 Traffic is often described as rate and shape. Traffic Shaping is a
mechanism to control the amount and the rate of the traffic sent to
the network.
 There are 2 types of traffic shaping algorithms:
1. Leaky Bucket
2. Token Bucket
 Leaky bucket can smooth out bursty traffic. Bursty chunks are
stored in the bucket and sent out at an average rate.
 It can be used to check that data transmissions, in the form
of packets, conform to defined limits on bandwidth and burstiness.
Traffic Throttling
 When too much traffic causes congestion, cut back (or throttle) the
traffic is called traffic throttling.
 Routers monitor network conditions and draw conclusions.
 Observable conditions include output link utilization, buffer or queue
length.
 EWMA: The Exponentially Weighted Moving Average is a statistic
for monitoring the process that averages the data and gives less
weight to data.
Choke Packets
 A router nearing or in congestion sends choke packets back to
senders.
 When the source host gets the choke packet, it is required to reduce
the traffic sent to the specified destination.
Explicit Congestion Notification
 A router can tag any packet it forwards (by setting a bit in the packet‘s
header) to signal that it is experiencing congestion.
 When the network delivers the packet, the destination can note that
there is congestion and inform the sender when it sends a reply
packet.
Hop-by-Hop Backpressure
 At high speeds or over long distances, many new packets may be
transmitted after congestion has been signaled because of the delay
before the signal takes effect.
 An alternative approach is to have the choke packet take effect at
every hop it passes through.

Load Shedding
 When none of the above methods make the congestion disappear,
routers can bring out the load shedding.
 When routers are unable to handle the packets they just throw them
away to avoid overloading the system and making it unavailable for all
users.
 The idea is to ignore some requests rather than crashing a system and
making it fail to serve any request.
Random Early Detection
  Dealing with congestion when it first starts is more effective than
letting it gum up the works and then trying to deal with it.
 The algorithm for doing this is called Random Early Detection (RED).
IP Version 4 Protocol (or) Internet Protocol
An IPv4 datagram consists of a header part and a body or payload part. The header
has a 20-byte fixed part and a variable-length optional part.

IPv4 (Internet Protocol) header

Version
The Version field keeps track of which version of the protocol the datagram belongs
to (currently a transmission between IPv4 and IPv6 is going on).
IHL
The IHL field contains the size of the IPv4 header; it has 4 bits that specify the
number of 32-bit words in the header. The minimum value for this field is 5, which indicates
a length of 5 × 32 bits = 160 bits = 20 bytes. As a 4-bit field, the maximum value is 15; this
means that the maximum size of the IPv4 header is 15 × 32 bits = 480 bits = 60 bytes.
Differentiated services
The Differentiated services field is intended to distinguish between different classes
of service.
Various combinations of reliability and speed are possible. For digitized voice, fast
delivery beats accurate delivery. For file transfer, error-free transmission is more important
than fast transmission.
Total length
The Total length includes everything in the datagram—both header and data. The
maximum length is 65,535 bytes.
Identification
The Identification field is needed to allow the destination host.
Two 1-bit fields related to fragmentation.
 DF stands for Don‘t Fragment. It is an order to the routers not to fragment the packet.
By marking the datagram with the DF bit, the sender knows it will either arrive in one
piece, or an error message will be returned to the sender.
 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.
Fragment offset
The Fragment offset tells where in the current packet this fragment belongs (8192
fragments per datagram).
Time to live
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.
It must be decremented on each hop and is supposed to be decremented multiple times
when a packet is queued for a long time in a router. When it hits zero, the packet is discarded
and a warning packet is sent back to the source host.
Protocol
The Protocol field tells which transport process to give the packet to. TCP and UDP
are some protocols. The numbering of protocols is global across the entire Internet. Protocols
and other assigned numbers were formerly listed in RFC 1700.
Header checksum
Header Checksum verifies the header only. Such a checksum is useful for detecting
errors generated by bad memory words inside a router.
Source address and Destination address
The Source address and Destination address indicate the IP address of the source and
destination network interfaces.
Source address and destination address indicate the network number and host number.
Options
Option is a field whose size varies from 0 bytes to 40 bytes.
This field is used for several purposes such as-
 Record route
 Source routing
 Padding
Some of the IP options

IP Addresses
Every host and router on the Internet has an IP address which encodes its network
number and host number.
An IP address does not actually refer to a host. It really refers to a network interface,
so if a host is on two networks, it must have two IP addresses.
However, most hosts are on one network and thus have one IP address. In contrast,
routers have multiple interfaces and thus multiple IP addresses.
All IP addresses are 32 bits long and are used in the source address and destination
address fields of IP packets.
Prefixes
IP addresses are hierarchical. Each 32-bit address is comprised of a variable-length
network portion in the top bits and a host portion in the bottom bits.
The network portion has the same value for all hosts on a single network, such as an
Ethernet LAN. This means that a network corresponds to a contiguous block of IP address
space. This block is called a prefix.
IP addresses are written in dotted decimal notation. In this format, each of the 4 bytes
is written in decimal, from 0 to 255.
For example, the 32-bit hexadecimal address 80D00297 is written as [Link].
Subnet mask
 A subnet mask is a 32-bit number created by setting host bits to all 0s and setting
network bits to all 1s. In this way, the subnet mask separates the IP address into the network
and host addresses.
The subnet mask splits the IP address into the host and network addresses, by defining
which part of the IP address belongs to the device and which part belongs to the network.
The ―255‖ address is always assigned to a broadcast address, and the ―0‖ address is
always assigned to a network address.

An IP prefix and a subnet mask

Subnetting and Subnet
The block of addresses are split into several parts for internal use as multiple
networks, while still acting like a single network to the outside world. This is called
subnetting and the networks (such as Ethernet LANs) that result from dividing up a larger
network are called subnets.
In this case, half of the block is allocated to the Computer Science Dept., a quarter is
allocated to the Electrical Engineering Dept., and one eighth to the Art Dept. The remaining
eighth is unallocated.

Splitting an IP prefix into separate networks with subnetting

CIDR – Classless InterDomain Routing
Classless Inter-Domain Routing (CIDR) is a method of IP address allocation and IP
routing that allows for more efficient use of IP addresses.
CIDR is based on the idea that IP addresses can be allocated and routed based on their
network prefix rather than their class.
CIDR addresses are represented using a slash notation, which specifies the number of
bits in the network prefix.
 Example: An IP address of [Link] with a prefix length of 24 would be
represented as [Link]/24.
This notation indicates that the first 24 bits of the IP address are the network prefix
and the remaining 8 bits are the host identifier.
Classful and Special Addressing
IP addresses were divided into the five categories. This allocation is called as classful
addresing.

IP Address Formats

CLASS A format allows for up to 128 networks with 16 million hosts each, B -
16,384 networks with up to 64K hosts, C - 2 million networks (e.g., LANs) with up to 256
hosts each (although a few of these are special), and D is multicast, in which a datagram is
directed to multiple hosts.
Addresses beginning with 1111 are reserved for future use.
Over 500,000 networks are now connected to the Internet, and the number grows
every year.
Network numbers are managed by a nonprofit corporation called ICANN (Internet
Corporation for Assigned Names and Numbers) to avoid conflicts.
Network addresses, which are 32-bit numbers, are usually written in Dotted Decimal
Notation.
In this format, each of the 4 bytes is written in decimal, from 0 to 255.
The lowest IP address is [Link] and the highest is [Link].

Special IP Addresses
 The values 0 and 1 have special meanings.
The value 0 means this network or this host.
The value of 1 is used as a broadcast address to mean all hosts on the indicated
network.
NAT—Network Address Translation
To access the Internet, one public IP address is needed, but we can use a private IP
address in our private network.
NAT allows multiple devices to access the Internet through a single public address.
To achieve this, the translation of a private IP address to a public IP address is
required.
Network Address Translation (NAT) is a process in which one or more local IP
address is translated into one or more Global IP address and vice versa.
The basic idea behind NAT is to assign each company a single IP address for Internet
traffic.
Within the company, every computer gets a unique IP address, which is used for
routing intramural traffic.
However, when a packet exits the company and goes to the ISP, an address translation
takes place.
To make this scheme possible, three ranges of IP addresses have been declared as
private. Companies may use them internally.
The three reserved ranges are:
 [Link] –[Link]/8 (16,777,216 hosts)
 [Link] – [Link]/12 (1,048,576 h.)
 [Link] – [Link]/16 (65,536 h.)

Placement and Operation of a NAT Box

 Internet Control Protocol
In addition to IP, which is used for data transfer, the internet has several control
protocols used in the network layer, including ICMP, ARP, RARP, BOOTP, and DHCP.
IMCP - Internet Control Message Protocol
The operation of the Internet is monitored closely by the routers.
When something unexpected occurs during packet processing at a router, the event is
reported to the sender by the ICMP (Internet Control Message Protocol).
ICMP is also used to test the Internet. About a dozen types of ICMP messages are
defined. Each ICMP message type is carried encapsulated in an IP packet.

The principal ICMP message

types Each ICMP message type is encapsulated in an IP
packet. In addition to this message, others have been
defined.
ARP - Address Resolution Protocol
Address Resolution Protocol (ARP) is a communication protocol used to find the
MAC (Media Access Control) address of a device from its IP address.
This protocol is used when a device wants to communicate with another device on a
Local Area Network or Ethernet.
Types of ARP
There are four types of Address Resolution Protocol:
 Proxy ARP
 Gratuitous ARP
 Reverse ARP (RARP)
 Inverse ARP
Proxy ARP - Proxy ARP is a method through which a Layer 3 devices may respond to ARP
requests in a different network from the sender. When devices are not in same data link layer
network but are in the same IP network.
Gratuitous ARP - Gratuitous ARP is an ARP request of the host that helps to identify the
duplicate IP address
Reverse ARP (RARP) - It is a networking protocol used by the client system in a local area
network (LAN) to request its IPv4 address from the ARP gateway router table.
Inverse ARP (InARP) - Inverse ARP is inverse of the ARP, and it is used to find the IP
addresses of the nodes from the data link layer addresses (MAC Addresses).

This process is as follows

 When a host tries to interact with another host, an ARP request is initiated. If the IP
address is for the local network, the source host checks its ARP cache to find out the
hardware address of the destination computer.
 If the correspondence hardware address is not found, ARP broadcasts the request to
all the local hosts.
 All hosts receive the broadcast and check their own IP address. If no match is
discovered, the request is ignored.
 The destination host that finds the matching IP address sends an ARP reply to the
source host along with its hardware address, thus establishing the communication.
The ARP cache is then updated with the hardware address of the destination host.

Address Resolution
Protocol DHCP - Dynamic Host Configuration Protocol
Dynamic Host Configuration Protocol (DHCP) is a network management protocol
used to dynamically assign an IP address to any device, or node, on a network. So they can
communicate using IP (Internet Protocol).
DHCP automates and centrally manages these configurations.
DHCP can be implemented on local networks as well as large enterprise networks.
DHCP is the default protocol used by the most routers and networking equipment.
DHCP is also called RFC (Request for comments) 2131.
DHCP does the following:
 DHCP manages all the nodes or devices added or dropped from the network.
 DHCP maintains the unique IP address of the host using a DHCP server.
  It sends a request to the DHCP server whenever a client/node/device, which is
configured to work with DHCP, connects to a network. The server acknowledges by
providing an IP address to the client/node/device.
DHCP is also used to configure the proper subnet mask, default gateway and DNS
server information on the node or device.
Many versions of DCHP are available for use in IPV4 (Internet Protocol Version 4)
and IPV6 (Internet Protocol Version 6).
How DHCP works
DHCP runs at the application layer of the TCP/IP protocol stack to dynamically
assign IP addresses to DHCP clients/nodes and to allocate TCP/IP configuration information
to the DHCP clients. Information includes subnet mask information, default gateway, IP
addresses and domain name system addresses.
DHCP is based on client-server protocol in which servers manage a pool of unique IP
addresses, as well as information about client configuration parameters, and assign addresses
out of those address pools.
The DHCP lease process works as follows:
 First of all, a client (network device) must be connected to the internet.
 DHCP clients request an IP address. Typically, client broadcasts a query for this
information.
 DHCP server responds to the client request by providing IP server address and other
configuration information. This configuration information also includes time period,
called a lease, for which the allocation is valid.
 When refreshing an assignment, a DHCP client requests the same parameters, but the
DHCP server may assign a new IP address. This is based on the policies set by the
administrator.
Benefits of DHCP

 Centralized administration of IP configuration

 Dynamic host configuration
 Seamless IP host configuration
 Flexibility and scalability

UNIT – V

Transport Layer Services

The transport Layer is the second layer in the TCP/IP model and the fourth layer in the OSI
model. It is an end-to-end layer used to deliver messages to a host. It is termed an end-to-end
layer because it provides a point-to-point connection rather than hop-to-hop, between the source
host and destination host to deliver the services reliably. The unit of data encapsulation in the
Transport Layer is a segment.
Services Offered by Transport Layer
The transport layer provides reliable data transfer services such as segmentation, flow
control, error detection, and retransmission, end-to-end communication between devices.

[Link]-to-end Connection between Hosts

The transport layer is also responsible for creating the end-to-end Connection between hosts for
which it mainly uses TCP and UDP. TCP is a secure, connection-orientated protocol that uses a
handshake protocol to establish a robust connection between two end hosts. TCP ensures the
reliable delivery of messages and is used in various applications. UDP, on the other hand, is a
stateless and unreliable protocol that ensures best-effort delivery. It is suitable for applications
that have little concern with flow or error control and requires sending the bulk of data like
video conferencing. It is often used in multicasting protocols.

End-to-End
Connection
[Link] Control
The transport layer provides a flow control mechanism between the adjacent layers of
the TCP/IP model. TCP also prevents data loss due to a fast sender and slow receiver by
imposing some flow control techniques. It uses the method of sliding window protocol which is
accomplished by the receiver by sending a window back to the sender informing the size of data
it can receive.
3. Multiplexing and Demultiplexing
Multiplexing(many to one) is when data is acquired from several processes from the
sender and merged into one packet along with headers and sent as a single packet. Multiplexing
allows the simultaneous use of different processes over a network that is running on a host.
The processes are differentiated by their port numbers. Similarly, Demultiplexing(one to many)
is required at the receiver side when the message is distributed into different processes.
Transport receives the segments of data from the network layer distributes and delivers it to the
appropriate process running on the receiver’s machine.
Multiplexing and Demultiplexing
[Link] Establishment
When two devices in a network wants to establish a connection using TCP, it is done through 3-
Way Handshake Process.

 The first computer connects to the second computer by sending a SYN packet to a specified
port number.
 If the second computer is listening, it will respond with a SYN/ACK.
 When the first computer receives the SYN/ACK, it replies with an ACK packet.
 After this, the two devices can communicate normally.
[Link] Termination
In a TCP connection, we have two types of termination mechanisms:
1. In the Graceful connection release, the connection is open until both parties have closed
their sides of the connection.
2. In an Abrupt connection release, either one TCP entity is forced to close the connection or
one user closes both directions of data transfer.
6. Reliable Data Delivery
The transport layer checks for errors in the messages coming from the application layer by
using error detection codes, and computing checksums, it checks whether the received data is
not corrupted and uses the ACK and NACK services to inform the sender if the data has arrived
or not and checks for the integrity of data.

connection management
 Connection management refers to establishing, maintaining, and terminating network
connections between devices or systems to enable reliable data transfer. In protocols like TCP, it
manages logical associations using a three-way handshake for connection establishment, ensuring
synchronization of sequence numbers. It handles flow control via sliding windows, error
correction through checksums and acknowledgments, and congestion control. Connection states
(e.g., SYN, ESTABLISHED, FIN-WAIT) are tracked, along with resource allocation, ensuring
efficient communication and mitigating issues like packet loss or retransmission.

Connection management process include:

 Connection Establishment: The process begins with initiating a request from one party
(client) to another (server). This typically involve protocols such as TCP (Transmission
Control Protocol) or UDP (User Datagram Protocol) for establishing connections between
hosts in a network, or protocols like HTTP (Hypertext Transfer Protocol) for establishing
communication between clients and servers in web applications.
 Handshake: Once the connection request is received, the server validates the request and
responds with a handshake message to acknowledge and establish the connection. During
the handshake, both parties may exchange additional information required for secure
communication, such as cryptographic keys.
 Data Transfer: With the connection established, data can be transmitted between the
client and server. This may involve multiple rounds of data exchange, depending on the
communication protocol and application requirements.
 Data Transmission Monitoring: Throughout the lifespan of the connection, both parties
monitor its status to ensure continued reliability and performance. This may involve
periodic checks, heartbeats, or other mechanisms to detect and handle failures or timeouts.
 Connection Termination: when the data exchange is complete or either party wishes to
end the connection, a termination sequence is initiated. This involves sending a
termination request or notification, followed by the ACK: acknowledgment of closure.
 Resource Management: efficient allocation and utilization of resources, such as network
bandwidth, memory, and processing power, to support multiple concurrent connections
without compromising performance or stability.
 Error Handling and Recovery: communication protocols and networking software
implement error detection, correction, and recovery mechanisms to handle various issues
that may arise during connection establishment or data transfer, such as packet loss,
network congestion, or hardware failures.
 Connection management in the transport layer
Connection management in the transport layer is a critical function that ensures reliable
data transfer between devices over a network. This process includes establishing, maintaining,
and terminating data transfers, primarily handled by the Transmission Control Protocol (TCP).

1. Connection Establishment
Three-Way Handshake: The process of establishing a connection in TCP and other
communication protocols involves a three-way handshake:
1. SYN (Synchronize) The client sends a SYN packet to the server to initiate a connection. This
packet includes an initial sequence number (ISN) chosen by the client.
2. SYN-ACK (Synchronize-Acknowledge) The server responds with a SYN-ACK packet. The
SYN part contains the server's initial sequence number. The ACK part acknowledges the client's
SYN packet by incrementing the client's ISN by one.
3. ACK (Acknowledge) The client sends an ACK packet back to the server. This acknowledges the
server's SYN-ACK by incrementing the server's ISN by one.
After the three-way handshake, a connection is established, and data transfer can begin.

2. Data Transfer Procedures

Sequencing TCP assigns sequence numbers to each byte of data to ensure correct order delivery.
Acknowledgments (ACKs) The receiver acknowledges received data by sending ACKs back to
the sender.
Flow Control TCP uses a sliding window protocol to manage the amount of data that can be sent
before receiving an acknowledgment.
Error Detection and Retransmission If a segment is lost or corrupted, the sender retransmits
the data after a timeout or upon receiving duplicate ACKs.
Congestion Control TCP implements algorithms like Slow Start, Congestion Avoidance, Fast
Retransmit, and Fast Recovery to manage network congestion and optimize throughput.

3. Connection Termination
Four-Way Handshake: The process of terminating a TCP connection involves a four-way
handshake:
1. FIN (Finish) The client or server sends a FIN packet to terminate its side of the connection.
2. ACK (Acknowledge) The receiving end acknowledges the FIN packet with an ACK packet.
3. FIN (Finish) The receiver sends a FIN packet to close its side of the connection.
4. ACK (Acknowledge) The initiator of the termination acknowledges the receiver's FIN packet
with an ACK.
After these steps, the connection is fully terminated.

4. Resetting Connections
RST (Reset Command): A TCP connection can be reset using the RST packet, which
immediately terminates the connection. This is typically used to handle errors or when one side
wants to abort the connection abruptly.

Key Concepts in Connection Management:

Full-Duplex Communication: Both ends can send and receive data simultaneously.
Half-Open Connections: If one side terminates or crashes, the other side may still think the
connection is open. TCP handles such scenarios with timeouts and retransmission mechanisms.
State Management: Both the client and server maintain states (e.g., SYN_SENT,
ESTABLISHED, FIN_WAIT) to manage the connection lifecycle.
Timeouts and Retransmissions: TCP uses timeouts to detect lost packets and triggers
retransmissions to ensure reliable delivery.
Addressing
 When an application (e.g., a user) wishes to set up a connection to a
remote application process, it must specify which one to connect to.
 The method used is to define transport addresses to which processes
can listen for connection requests.
 In the Internet, these endpoints are called ports.
 There are two types of access points.
o TSAP (Transport Service Access Point) to mean a specific
endpoint in the transport layer.
o NSAPs (Network Service Access Points) IP addresses are
examples of NSAPs.
 Application processes, both clients and servers, can attach themselves
 to a local TSAP to establish a connection to a remote TSAP.
 These connections run through NSAPs on each host.
A possible scenario for a transport connection is as follows:
1. A mail server process attaches itself to TSAP 1522 on host 2 to wait
for an incoming call.
2. An application process on host 1 wants to send an email message, so
it attaches itself to TSAP 1208 and issues a CONNECT request. The
request specifies TSAP 1208 on host 1 as the source and TSAP 1522
on host 2 as the destination.
3. The application process sends over the mail message.
4. The mail server responds to say that it will deliver the message.
5. The transport connection is released.

TSAP and NSAP network connection

Connection Establishment
To establish a connection, TCP uses a three-way handshake.
1. Restricted network design.
2. Putting a hop counter in each packet.
3. Timestamping each packet.
Normal operation

Host 1 chooses a sequence number X and send a CONNECTION

REQUEST TPDU to host 2.

Host 2 replies with an ACK TPDU acknowledging X and announcing

its own initial sequence number.
Old duplicate CONNECTION REQUEST
The TPDU is a delayed duplicate CONNECTION REQUEST from an
old connection. This TPDU arrives at host 2 without host 1 knowledge.
Host 2 reacts to this TPDU by sending host 1 an ACK TPDU, in effect
asking for verification.
When host 1 rejects host 2 attempts to establish a connection, host 2
realizes that it was tricked by a delayed duplicate and abandons the
connection. A delayed duplicate does no damage.
Duplicate CONNECTION REQUEST and duplicate ACK

Host 2 gets a delayed CONNECTION REQUEST and replies to it.

Host 2 has proposed using Y as initial sequence number to host 1.
Host 1 traffic knows that no TPDU containing sequence number Y or
acknowledgement to Y are still in existence.
When the second delayed TPDU arrives at host 2, the fact that Z has
been acknowledged rather than Y tells host 2 too is an old duplicate.
Connection release
There are two styles of terminating a connection:
1) Asymmetric release and
2) Symmetric release.
Asymmetric release
 Asymmetric release is the way the telephone system works: when one
party hangs up, the connection is broken.
 It is abrupt disconnection and may result in data loss.
Symmetric release
 Symmetric release treats the connection as two separate
unidirectional connections and requires each one to be released
separately.

Connection releasing methods

i. Normal
ii. Final ACK lost
iii. Response lost
iv. Response lost and subsequent DRs lost

Normal

One of the users sends a DR request to initiate the connection release.

When it arrives, the recipient sends back a DR segment and starts a

timer. When this DR arrives, the original sender sends back an ACK
segment and releases the connection.
Final ACK lost

If the final ACK segment is lost, the situation is saved by the timer. When
the timer expires, the connection is released anyway.

Response lost

Consider the case of the second DR being lost. The user initiating the
disconnection will not receive the expected response, will time out, and will
start all over again.

The second time no segments are lost and all segments are delivered
correctly and on time.

Response lost and subsequent DRs lost

All the repeated attempts to retransmit the DR also fail due to lost
segments.
After N retries, the sender just gives up and releases the connection.
Meanwhile, the receiver times out and also exits.
 INTERNET TRANSPORT PROTOCOL: UDP
 Introduction to UDP
 Remote Procedure Call
 Real-Time Transport Protocols
 The Internet has two main protocols in the transport layer. They are:
 connectionless protocol
 connection-oriented protocol
 The connectionless protocol is UDP. It does almost nothing beyond
sending packets between applications, letting applications build their
own protocols as needed.
 The connection-oriented protocol is TCP. It does almost everything. It
makes connections along with flow control and congestion control, on
behalf of the applications that use it.
 Since UDP is a transport layer protocol that runs in the operating
system.
 The protocols that use UDP run in user space.
Introduction to UDP
 The Internet protocol suite supports a connectionless transport
protocol called UDP (User Datagram Protocol).
 UDP provides the applications to send encapsulated IP datagrams
without establishing a connection.
  UDP transmits segments consisting of an 8-byte header followed by
the pay-load.
 The two ports serve to identify the end-points within the source and
destination machines.
 When a UDP packet arrives, its payload is handed to the destination
port.
 This attachment occurs when the BIND primitive is used.
 Without the port fields, the transport layer would not know what to
do with each incoming packet. With them, it delivers the embedded
segment to the correct application.

 Source port, destination port: Identifies the end points within the
source and destination machines.
 UDP length: Includes 8-byte header and the data. Minimum length is
8 bytes and the maximum length is 65,515 bytes.
 UDP checksum: Includes the UDP header, the UDP data padded out
to an even number of bytes if needed. It is an optional field
Remote Procedure Call
 Sending a message to a remote host and getting a reply back is like
making a function call in a programming language. This is to arrange
request-reply interactions on networks.
 Example, just imagine a procedure named get IP address (host name)
that works by sending a UDP packet to a DNS server and waiting or
the reply.
 RPC is used to call remote programs using the procedural call. When
a procedure on machine 1 calls a procedure on machine 2, the calling
process on 1 is suspended and execution of the called procedure takes
place on 2.
 To call a remote procedure, the client program must be bound with a
procedure, called the client stub, that represents the server
procedure in the client‘s address space. It is a normal local call.
 Similarly, the server is bound with a procedure called the server stub.
The sequence of events in a remote procedure call
Step 1: The client calls the client stub. This call is a local procedure
call.
Step 2: The client stub packs the parameters into a message and
makes system call to send the message. Packing the parameters is
called marshaling.
Step 3: The operating system sends the message from the client
machine to the server machine.
Step 4: The parameters are removed from the message by the server
stub. (Unmarshaling)
Step 5: Then, the server procedure is called by the server stub.
The reply traces the same path in the other direction.
Real-Time Transport Protocols
 The Real-time Transport Protocol is a network protocol used to deliver
streaming audio and video media over the internet.
Real-Time Transport Control Protocol
 RTCP provides control information for the RTP session.
 It doesn't actually transport any media data, but helps with quality
control.
INTERNET TRANSPORT PROTOCOL: TCP
 Introduction to TCP
 The TCP Service Model
 The TCP Protocol
 The TCP Segment Header
 TCP Connection Establishment
 TCP Connection Release
 TCP Connection Management Modeling
 TCP Sliding Window
 TCP Timer Management
 TCP Congestion Control

 It was specifically designed to provide a reliable end-to end byte

stream over an unreliable network.
 It was designed to adapt the properties of the inter network and to be
robust in the face of many kinds of failures.
 Each machine supporting TCP has a TCP transport entity, which
accepts user data streams from local processes, breaks them up into
pieces not exceeding 64 kbytes and sends each piece as a separate IP
datagram.
 When these datagrams arrive at a machine, they are given to TCP
entity, which reconstructs the original byte streams.
  TCP retransmits and also reassembles datagrams into messages in
proper sequence.
The different issues to be considered are:
 The TCP Service Model
 The TCP Protocol
 The TCP Segment Header
 The Connection Management
 TCP Transmission Policy
 TCP Congestion Control
 TCP Timer Management
The TCP Service Model
 TCP service is obtained by having both the sender and receiver create
end points called SOCKETS.
 Each socket has a socket number (address) consisting of the IP
address of the host, called a ―PORT‖. A port is the TCP name for a
TSAP.
 To obtain TCP service a connection must be explicitly established
between a socket on the sending machine and a socket on the
receiving machine.
 All TCP connections are full duplex and point to point i.e.,
multicasting or broadcasting is not supported.
 A TCP connection is a byte stream, not a message stream i.e., the data
is delivered as chunks

Sockets:
 A socket may be used for multiple connections at the same time. In
other words, 2 or more connections may terminate at same socket.
 Connections are identified by socket identifiers at both ends. Some of
the sockets are listed below:

Ports: Port numbers below 1024 are called Well- known ports and are
reserved for standard services.
Eg:

PORT-21 To establish a connection to a host to transfer a file

PORT-23 To establish a remote login session using TELNET

The TCP Protocol

 Every byte on a TCP connection has its own 32-bit sequence number.
 The basic protocol used by TCP entities is the sliding window protocol.
 When a sender transmits a segment, it also starts a timer.
 When the segment arrives at the destination, the receiving TCP entity
sends back a segment (with data if any exist, otherwise without data)
bearing an acknowledgement number equal to the next sequence
number.
 If the sender's timer goes off before the acknowledgement is received,
the sender transmits the segment again.
The TCP Segment Header
 Every segment begins with a fixed-format, 20-byte header.
 The fixed header may be followed by header options.
 After the options, if any, up to 65,535 - 20 - 20 = 65,495 data bytes
may follow, where the first 20 refer to the IP header and the second to
the TCP header.
 Segments without any data are commonly used for acknowledgements
and control messages.

Source Port, Destination Port : Identify local end points of the

connections
Sequence number: Specifies the sequence number of the segment
Acknowledgement Number: Specifies the next byte expected.
 TCP header length: Tells how many 32-bit words are contained in TCP
header
URG: It is set to 1, if URGENT pointer is in use, which indicates start of
urgent data.
ACK: It is set to 1 to indicate that the acknowledgement number is valid.
PSH: Indicates pushed data
RST: It is used to reset a connection that has become confused due to
reject an invalid segment or refuse an attempt to open a connection.
FIN: Used to release a connection.
SYN: Used to establish connections.
TCP Connection Establishment
 To establish a connection, one side, the server, waits for an incoming
connection by executing the LISTEN and ACCEPT primitives.
 Other side, the client, executes a CONNECT primitive, specifying the
IP address and port to which it wants to connect, the maximum TCP
segment size it is willing to accept.
 The CONNECT primitive sends a TCP segment with the SYN bit on
and ACK bit off and waits for a response.

(a) TCP connection establishment in the normal case.

(b) Simultaneous connection establishment on both

sides. TCP Connection Release

 Although TCP connections are full duplex, it is best to think them as a

pair of simplex connections.
 Each simplex connection is released independently. To release a
connection, either party can send a TCP segment with the FIN bit set,
which means that it has no more data to transmit.
  When the FIN is acknowledged, that direction is shut down for new
data.
 When both directions have been shut down, the connection is
released.
TCP Connection Management Modeling

 The steps required establishing and release connections can be

represented in a finite state machine with the 11.
 In each state, certain events are legal. When a legal event happens,
some action may be taken. If some other event happens, an error is
reported.

 The server does a LISTEN and to see who turns up.

 When a SYN comes in, the server acknowledges it and goes to the SYN
RCVD state

 When the servers SYN is acknowledged, the server goes to the

ESTABLISHED state. Data transfer can now occur.

 When the client has had enough, it does a close, which causes a FIN
to arrive at the server.

 The server is then signaled.

 When it too, does a CLOSE, a FIN is sent to the client.

 When the client‘s acknowledgement shows up, the server releases the
connection and deletes the connection record.
TCP Sliding Window

1. In the above example, the receiver has 4096-byte buffer.

2. If the sender transmits a 2048-byte segment that is correctly received, the
receiver will acknowledge the segment.
3. Now the receiver will advertise a window of 2048 as it has only 2048 of
buffer space, now.
4. Now the sender transmits another 2048 bytes which are acknowledged,
but the advertised window is ‘0‘.
5. The sender must stop until the application process on the receiving host
has removed some data from the buffer, at which time TCP can advertise
a layer window.
Silly Window Syndrome
 This is one of the problems that ruin the TCP performance, which
occurs when data are passed to the sending TCP entity in large
blocks, but an interactive application on the receiving side reads 1
byte at a time.

 Initially the TCP buffer on the receiving side is full and the sender
knows this (win=0). Then the interactive application reads 1
character from TCP stream.
 Now, the receiving TCP sends a window update to the sender saying
that it is all right to send 1 byte. The sender obligates and sends 1
byte.
 The buffer is now full, and so the receiver acknowledges the 1 byte
segment but sets window to zero. This behavior can go on forever.
TCP Congestion Control
 TCP tries to prevent the congestion from occurring in the first place in
the following way:
 When a connection is established, a suitable window size is chosen
and the receiver specifies a window based on its buffer size.
 If the sender sticks to this window size, problems will not occur
due to buffer overflow at the receiving end.
  But they may still occur due to internal congestion within the
network. Let‘s see this problem occurs.

In fig (a): We see a thick pipe leading to a small- capacity receiver. As

long as the sender does not send more water than the bucket can
contain, no water will be lost.
In fig (b): The limiting factor is not the bucket capacity, but the internal
carrying capacity of the n/w. If too much water comes in too fast, it will
backup and some will be lost.
TCP Timer Management
 TCP uses 3 kinds of timers:
1. Retransmission timer
2. Persistence timer
3. Keep-Alive timer.
Retransmission timer
 When a segment is sent, a timer is started. If the segment is
acknowledged before the timer expires, the timer is stopped.
 On the other hand, the timer goes off before the acknowledgement
comes in, the segment is retransmitted and the timer is started again.
Persistence timer
 It is designed to prevent the following deadlock:
 The receiver sends an acknowledgement with a window size of
‗0‘ telling the sender to wait, the receiver updates the window.
 But the packet with the update is lost, now both the sender and
receiver are waiting for each other to do something.
 When the persistence timer goes off, the sender transmits a
probe to the receiver.
 The response to the probe gives the window size. If it is still
zero, the persistence timer is set again and the cycle repeats if it
is non zero, data can now be sent.
Keep-Alive timer
 When a connection has been idle for a long time, this timer may
go off to cause one side to check if other side is still there. If it
fails to respond, the connection is terminated.
 NETWORK SECURITY
Network security consists of the policies and practices to prevent and
monitor unauthorized access, misuse, modification or denial of a computer
network and network-accessible resources.
CRYPTOGRAPHY

 Cryptography is the study of secret (crypto) writing (graphy).

 The principles and methods of transforming an intelligible message
into an unintelligible message and then retransforming that message
back to its original form.
 The art of breaking ciphers known as cryptanalysis and the art of
devising them collectively known as cryptology.

Some of the encryption schemes are:

PLAINTEXT: This is the original intelligible message.
CIPHERTEXT: Transformed message.
ENCRYPTION ALGORITHMS: The encryption algorithm
performs various substitutions and transformations on the
plaintext.
SECRET KEY: Some critical information used by the cipher knows
only to sender and receiver.
ENCIPHER (ENCODE): The process of converting plaintext to
ciphertext.
DECIPHER (DECODE): The process of converting ciphertext back into
plaintext.
Cryptography systems are characterized into three
1) The type of operation used for transforming plaintext to ciphertext
Two general principles
 Substitution cipher
 Transposition cipher
Substitution cipher

In which each element in the plaintext (bit, letter, group of letters is

mapped into another element.
Transposition cipher
In which elements in plaintext are rearranged.
2) The number of keys used
Both sender and receiver use same key as

 Symmetric or Single key Secret key or conventional

encryption.
Both sender and receiver use different key

 Asymmetric, two key or public key encryption.

3) The way in which plaintext is processed
A Block cipher: processes the input one block of elements at a time,
producing an output block for each input block. (i.e. Encrypt one
bit/character at a time)
Eg: THIS IS EASY KEY
(3) WKLV LV HDVB.

A stream cipher: processes the input elements continuously,

producing output one element at a time. (i.e. Break plaintext message
in equal size blocks and encrypt each block as a unit).
Eg: THIS IS EASY KEY (135)
THI SIS EAS Y…
UKN JWN ….
 The messages to be encrypted, the plaintext is transformed by a
function that is parameterized by a key.
 The output of the encryption process, known as the ciphertext, is then
transmitted, by messenger or radio.
 We assume that the enemy, or intruder, hears and accurately copies
down the ciphertext.
 However, he does not know what the decryption key is and so cannot
decrypt the ciphertext easily.
  Sometimes the intruder can not only listen to the communication
channel (passive intruder) but can also record messages and play
them back later, inject his own messages, or modify legitimate
messages before they get to the receiver(active intruder).
Caesar Cipher
 The Caesar cipher involves replacing each letter of alphabets with the
letter standing three places further down the alphabets.
Eg:
plaintext: meet me after the toga party.

Ciphertext: PHHW PH DIWHU WKH WRJD SDUWB.

The letter following Z to A.

Plaintext: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Ciphertext: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Kherchoff’s Principle
Kherchoff‘s principle states that, all algorithms about the system must
be public except the keys. The keys should be secret.
Monoalphabetic Cipher
 The general system of symbol for symbol substitution cipher.
 With the key being 26 letter string corresponding to the full alphabet.
Eg: A->X, B->Y, C->Z, D->A…….Z->W
 In English, for example, e is the most common letter, followed by t, o,
a, n, i, etc.
 The most common two-letter combinations, or digrams, are th, in, er,
re, and an.
 The most common three-letter combinations, or trigrams, are the,
ing, and, and ion.
Transposition Techniques
 A different kind of mapping is achieved by performing some sort of
permutation on plaintext letters.
 This technique is referred as transposition cipher.
 The letters of the plaintext are written alternating between rows and
the rows and then read sequentially to give cipher.
WE ARE DISCOVERED SAVE YOURSELF would be written

 To write the message in rectangle row by row and read the message
column by column but permute the order of column.
  The order of column then becomes keyword AUTHOR and order the
column by lexicographic order of the letters in the keyword.

Gives the cipher

One-Time pad
 Each new message requires a new key of the same length as the new
message. Such a scheme is known as a one-time pad.
 It is unbreakable.
 It produces a random output that bears no statistical relationship to
the plaintext.
Example

H E L L O message

7 (H) 4 (E) 11 (L) 11 (L) 14 (O) message

+23 (X) 12 (M) 2 (C) 10 (K) 11 (L) key

= 30 16 13 21 25 message + key

= 4(E) 16 (Q) 13 (N) 21 (V) 25 (Z) message + key

E Q N V Z → ciphertext
Fundamental Cryptographic Principles
• Redundancy
– All encrypted messages must contain some redundancy, that
is, information not needed to understand the message.
• Freshness
– Some measures must be taken to ensure that each message
received can be verified as being fresh, that is, sent very
recently.
Redundancy Motivation
• Consider a mail-order company, The Couch Potato (TCP), with 60,000
products.
• Ordering messages consist of a 16-byte customer name followed by
a 3-byte data field.
 • The last 3 bytes are to be encrypted using a very long key known
only by the customer and TCP.
• Suppose that a recently-fired employee wants to punish TCP.
• Just before leaving, he takes the customer list with him.
• He writes a program to generate fictitious orders using real customer
names.
• Since he does not have the list of keys, he just puts random numbers
in the last 3 bytes, and sends hundreds of orders.
• When these messages arrive, TCP's computer uses the customer's
name to locate the key and decrypt the message.
• Unfortunately for TCP, almost every 3-byte message is valid, so
the computer begins printing out shipping instructions.
• In this way an active intruder can cause a massive amount of trouble.
• This problem can be solved by the addition of redundancy to all
messages.
• For example, if order messages are extended to 12 bytes, the first 9 of
which must be zeros, then this attack no longer works because the ex-
employee can no longer generate a large stream of valid messages.
All messages must contain considerable redundancy so that active
intruders cannot send random junk and have it be interpreted as a valid
message
Freshness
• This measure is needed to prevent active intruders from playing back
old messages.
• If no such measures were taken, our ex-employee could
keep repeating previously sent valid messages.
• Some method is needed to foil replay attacks
• A solution is to include in every message a timestamp valid only
for, say, 10 seconds.
• The receiver can then just keep messages around for 10 seconds.
Messages older than 10 seconds can be thrown out.