University Institute of Engineering

DEPARTMENT OF COMPUTER SCIENCE

& ENGINEERING
Bachelor of Engineering (Computer Science & Engineering)
Subject Name: Computer Network
Subject Code:21CSH-256/21ITH-256

DISCOVER . LEARN . EMPOWER

 Syllabus
UNIT-I
Introduction: Introduction to network, types of transmission technologies, Network Categories: LAN, MAN, WAN (Wireless /Wired),
Network Software: Concept of Layers, Protocols, interfaces and services. Reference Models: OSI, TCP/IP and comparison, Concept of
Topologies.
Physical Layer: Bit rate, Baud rate, Bandwidth, Transmission Impairments: Attenuation, Distortion, Noise; Data rate limits: Nyquist formula,
Shannon Formula, Modulation & modems; Transmission Modes, Multiplexing: Frequency Division, Time Division, Wavelength Division
Transmission Media and Switching: Twisted pair, coaxial, fiber optics, Wireless Transmission (radio, microwave & infrared);Message
switching, Circuit Switching & Packet Switching.

UNIT-II
Data Link Layer(Flow and Error Control): Design issues, Error Detection & Correction; Flow control & Error Control; Sliding Window
Protocols, ARQ: Stop & Wait , Go Back n, Selective Repeat ; Examples of DLL protocols – HDLC, PPP;
Data Link Layer (Medium Access Sub layer) Channel Allocation; Random Access: ALOHA, CSMA protocols; Controlled Access: Polling,
Reservation, Token Passing; Examples of IEEE standards(802.2,802.3,802.4, 802.5), Basics of Wi-Fi(802.11).
Network Layer: Design issues, Logical Addressing: IPv4 & IPv6; Packet Formats & their comparison IPv4 & IPv6; Routing Algorithms:
Distance Vector, Link State

UNIT-III
Network Layer(Continue): Congestion Control: Principles of congestion control; Congestion prevention policies, Leaky bucket & Token
Bucket Algorithms.
Transport Layer: Services provided to upper layers, Elements of Transport protocols. Addressing, Flow Control & buffering; Example
Transport protocols: TCP, SCTCP & UDP.
Application Layer and Network Security: Domain Name System, Simple Network Management Protocol, Electronic Mail, World Wide
Web, Basics of authentication, Public and Private Key Cryptography, Digital Signatures and Certificates, Firewalls.
 Course Objectives
CO1 Interpret the building block of network and its architecture

CO2 Demonstrate the services of all the layers of network models

CO3 Identify and analyze error and control flow mechanism.

CO4 Explain various routing protocols of network models to ensure robust delivery of messages

CO5 Exemplify the securities of computer network

 Data Link Layer
(FLOW AND ERROR CONTROL)
FLOW AND ERROR CONTROL

The most important responsibilities of the data link

layer are flow control and error control. Collectively,
these functions are known as data link control.

Topics discussed in this section:

Flow Control
Error Control
 Flow Control
• Flow control coordinates the amount of data that can be sent before receiving
acknowledgement
• It is one of the most important functions of data link layer.
• Flow control is a set of procedures that tells the sender how much data it can
transmit before it must wait for an acknowledgement from the receiver.
• Receiver has a limited speed at which it can process incoming data and a
limited amount of memory in which to store incoming data.
• Receiver must inform the sender before the limits are reached and request that
the transmitter to send fewer frames or stop temporarily.
• Since the rate of processing is often slower than the rate of transmission,
receiver has a block of memory (buffer) for storing incoming data until they
are processed.
Error Control
• Error control includes both error detection and error correction.
• It allows the receiver to inform the sender if a frame is lost or
damaged during transmission and coordinates the
retransmission of those frames by the sender.
• Error control in the data link layer is based on automatic repeat
request (ARQ). Whenever an error is detected, specified frames
are retransmitted.
Figure 11.5 Taxonomy of protocols discussed in this chapter
 Protocol for Noiseless Channel
Let us first assume we have an ideal channel in which no frames are
lost, duplicated, or corrupted. We introduce two protocols for this type
of channel.

•Simplest Protocol
•Stop-and-Wait Protocol

11.9
 Simplest Protocol
This Diagram shows an example of
communication using this protocol. It
is very simple. The sender sends a
sequence of frames without even
thinking about the receiver. To send
three frames, three events occur at
the sender site and three events at the
receiver site. Note that the data
frames are shown by tilted boxes; the
height of the box defines the
transmission time difference between
the first bit and the last bit in the
frame.
Error and Flow Control Mechanisms
• Stop-and-Wait
• Go-Back-N ARQ
• Selective-Repeat ARQ
 ▪ Sender keeps a copy of the last frame until it receives an
Stop-and-Wait acknowledgement.
▪ For identification, both data frames and acknowledgements
(ACK) frames are numbered alternatively 0 and 1.
▪ Sender has a control variable (S) that holds the number of
the recently sent frame. (0 or 1)
▪ Receiver has a control variable ® that holds the number of
the next frame expected (0 or 1).
▪ Sender starts a timer when it sends a frame. If an ACK is not
received within a allocated time period, the sender
assumes that the frame was lost or damaged and resends it
▪ Receiver send only positive ACK if the frame is intact.
▪ ACK number always defines the number of the next
expected frame
Stop-and-Wait ARQ, lost ACK frame

• When a receiver receives a

damaged frame, it discards it and
keeps its value of R.
• After the timer at the sender
expires, another copy of frame 1
is sent.
Stop-and-Wait, lost ACK frame

• If the sender receives a

damaged ACK, it discards it.
• When the timer of the
sender expires, the sender
retransmits frame 1.
• Receiver has already
received frame 1 and
expecting to receive frame 0
(R=0). Therefore it discards
the second copy of frame 1.
Stop-and-Wait, delayed ACK frame
• The ACK can be delayed at
the receiver or due to some
problem
• It is received after the timer
for frame 0 has expired.
• Sender retransmitted a copy
of frame 0. However, R =1
means receiver expects to
see frame 1. Receiver
discards the duplicate frame
0.
• Sender receives 2 ACKs, it
discards the second ACK.
Piggybacking
• A method to combine a data
frame with ACK.
• Station A and B both have
data to send.
• Instead of sending
separately, station A sends a
data frame that includes an
ACK.
• Station B does the same
thing.
• Piggybacking saves
bandwidth.
Disadvantage of Stop-and-Wait
• In stop-and-wait, at any point in time, there is only one frame that is
sent and waiting to be acknowledged.
• This is not a good use of transmission medium.
• To improve efficiency, multiple frames should be in transition while
waiting for ACK.
• Two protocol use the above concept,
– Go-Back-N ARQ
– Selective Repeat ARQ
Go-Back-N ARQ
• We can send up to W frames before worrying about ACKs.
• We keep a copy of these frames until the ACKs arrive.
• This procedure requires additional features to be added to Stop-and-
Wait ARQ.
Sequence Numbers
• Frames from a sender are numbered sequentially.
• We need to set a limit since we need to include the sequence number
of each frame in the header.
• If the header of the frame allows m bits for sequence number, the
sequence numbers range from 0 to 2 m – 1. for m = 3, sequence
numbers are: 1, 2, 3, 4, 5, 6, 7.
• We can repeat the sequence number.
• Sequence numbers are:
0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, …
 Sender Sliding Window
• At the sending site, to hold the
outstanding frames until they are
acknowledged, we use the
concept of a window.
• The size of the window is at most
2m -1 where m is the number of
bits for the sequence number.
• Size of the window can be
variable, e.g. TCP.
• The window slides to include new
unsent frames when the correct
ACKs are received
 Receiver Sliding Window
• Size of the window at the
receiving site is always 1 in this
protocol.
• Receiver is always looking for a
specific frame to arrive in a
specific order.
• Any frame arriving out of order
is discarded and needs to be
resent.
• Receiver window slides as
shown in fig. Receiver is
waiting for frame 0 in part a.
 Control Variables
• Sender has 3 variables: S, SF, and SL
• S holds the sequence number of recently sent frame
• SF holds the sequence number of the first frame
• SL holds the sequence number of the last frame
• Receiver only has the one variable, R, that holds the sequence number of the frame it
expects to receive. If the seq. no. is the same as the value of R, the frame is accepted,
otherwise rejected.
 Acknowledgement
• Receiver sends positive ACK if a frame arrived safe and in order.
• If the frames are damaged/out of order, receiver is silent and discard all subsequent
frames until it receives the one it is expecting.
• The silence of the receiver causes the timer of the unacknowledged frame to expire.
• Then the sender resends all frames, beginning with the one with the expired timer.
• For example, suppose the sender has sent frame 6, but the timer for frame 3 expires
(i.e. frame 3 has not been acknowledged), then the sender goes back and sends frames
3, 4, 5, 6 again. Thus it is called Go-Back-N-ARQ
• The receiver does not have to acknowledge each frame received, it can send one
cumulative ACK for several frames.
 Go-Back-N ARQ, normal operation
• The sender keeps track of the outstanding frames and updates the
variables and windows as the ACKs arrive.
Go-Back-N ARQ, lost frame
• Frame 2 is lost
• When the receiver
receives frame 3, it
discards frame 3 as it is
expecting frame 2
(according to window).
• After the timer for
frame 2 expires at the
sender site, the sender
sends frame 2 and 3.
(go back to 2)
 Go-Back-N ARQ, damaged/lost/delayed ACK

• If an ACK is damaged/lost, we can have two situations:

• If the next ACK arrives before the expiration of any timer, there is no need for
retransmission of frames because ACKs are cumulative in this protocol.
• If ACK1, ACK2, and ACk3 are lost, ACK4 covers them if it arrives before the
timer expires.
• If ACK4 arrives after time-out, the last frame and all the frames after that are
resent.
• Receiver never resends an ACK.
• A delayed ACK also triggers the resending of frames
 Go-Back-N ARQ, sender window size
• Size of the sender window must be less than 2 m. Size of the receiver is always 1. If m = 2, window size
= 2 m – 1 = 3.
• Fig compares a window size of 3 and 4.

Accepts as the
1st frame in
the next cycle-
an error
 Selective Repeat ARQ, sender and receiver windows
• Go-Back-N ARQ simplifies the process at the receiver site. Receiver only keeps track of only one
variable, and there is no need to buffer out-of-order frames, they are simply discarded.
• However, Go-Back-N ARQ protocol is inefficient for noisy link. It bandwidth inefficient and slows down
the transmission.
• In Selective Repeat ARQ, only the damaged frame is resent. More bandwidth efficient but more
complex processing at receiver.
• It defines a negative ACK (NAK) to report the sequence number of a damaged frame before the timer
expires.
Selective Repeat ARQ, lost frame • Frames 0 and 1 are
accepted when
received because they
are in the range
specified by the
receiver window. Same
for frame 3.
• Receiver sends a NAK2
to show that frame 2
has not been received
and then sender
resends only frame 2
and it is accepted as it
is in the range of the
window.
 Selective Repeat ARQ, sender window size
• Size of the sender and receiver windows must be at most one-half of 2 m. If m = 2, window size
should be 2 m /2 = 2. Fig compares a window size of 2 with a window size of 3. Window size is 3 and
all ACKs are lost, sender sends duplicate of frame 0, window of the receiver expect to receive frame
0 (part of the window), so accepts frame 0, as the 1st frame of the next cycle – an error.
References
• [Link]
/chapter11/powerpoint_slides.html
• [Link]
work/data_link_control_and_protocols.htm
• Data Communications and Networking by Behrouz A. Forouzan
• [Link]/Forouzan