Framing Techniques

1) character count

2) Flag bytes with byte stuffing

3) starting and ending flags, with bit stuffing

Error Detection techniques

1. Single parity check

2. Two dimensional parity check

3. Checksum

4. Cyclic redundancy check (CRC)

Error detection and correction with Hamming code

 Flow control

Elementary Data Link Protocols

and
Sliding window Protocols
Mechanisms of Flow control

Protocols

Noiseless
Noisy Channels
Channels

❑ Simplex ❑ Stop and wait ARQ

❑ Stop and wait ❑ Go-Back-N ARQ
❑ Selective Repeat ARQ
Sliding window
protocols
Elementary Data link Protocols
◼ Protocols:
❑ 1) Unrestricted simplex protocol
❑ 2) Stop-and-wait protocol
❑ 3) Simplex protocol for a Noisy Channel
Unrestricted Simplex protocol / Simplest
protocol
• Unidirectional Protocol
• No error control and flow control.
• The transmitting and receiving hosts are always ready
• No sequence numbers and Acknowledgements are used here.
• Processing time can be ignored
• Infinite buffer space is available
Stop and wait protocol
❖ Def : Protocol in which the sender sends one frame and then waits for
acknowledgement before proceeding is called stop-and-wait.
❖ Flow Diagram:
A B
Request
Frame
Arrival
Ack
Arrival
Frame
Request Ack
Arrival
Disadvantages
• Lost data
• Lost acknowledgement
• Delayed acknowledgement/data
A simplex protocol for a Noisy Channel
❖ The channel is noisy, frames may be damaged or lost
❖ Good scene : data frame reaches intact, ack sent back and received, next frame
sent
❖ Bad scene :

❖ Data frame damaged or lost ..hence no ack – sender times out and resends ..
No problem
❖ Data frame reaches intact but Ack lost .. Times out ..resends.. Receiver
receives duplicate frames. Problem
❖ Solution : Keep a sequence number for each frame to distinguish between the
new frame and a duplicate frame
Stop and wait ARQ
• After transmitting one frame, the sender waits for an
acknowledgement before transmitting the next frame.
• If the acknowledgement does not arrive after a certain
period of time, the sender times out and retransmits the
original frame.
• Stop-and-wait ARQ = Stop-and-wait + Timer out timer +
Sequence number
Go-Back-N ARQ
• Go-Back-N ARQ uses the concept of protocol pipelining i.e, the
sender can send multiple frames before receiving the
acknowledgements for the first frame.
• There are finite number of frames and the frames are numbered
in a sequential manner.
• The number of frames that can be sent depends on the window
size of the sender.
• It the acknowledgement of a frame is not received within an
agreed time period, all frames in the current window are
transmitted.
 Working of Go-Back-N ARQ
Sender Receiver
9 8 7 6 5 4 3 2 1 0 0
1
2 0
Window size : 4
3 1
2
9 8 7 6 5 4 3 2 1 0 3
4
5
X
9 8 7 6 5 4 3 2 1 0 2
3
4
5
Selective Repeat ARQ
• In Selective Repeat ARQ, only the erroneous or lost frames
are retransmitted, while correct frames are received and
buffered.
• The receiver while keeping track of the sequence numbers,
buffers the frames in memory and sends NACK for only
frame which is missing or damaged.
• The sender will send/retransmit packet for which NACK is
received.
 Working of Selective Repeat ARQ
Sender Receiver
9 8 7 6 5 4 3 2 1 0 0
1
2 0
Window size : 4
3 1
2
9 8 7 6 5 4 3 2 1 0 3
4
5
X 4
9 8 7 6 5 4 3 2 1 0 2 5

2
6
7
6
7
Problem on Go-back-N ARQ
• Station A needs to send a message consisting of 9 packets for station
B using a sliding window (window size 3) and go-back-N strategy. All
packets are ready and immediately available for transmission. If every
5th packet that A transmits gets lost (but no Acks from B ever get lost),
then what is the number of packets that A will transmit for sending
the message to B?
(a) 12 (b) 14 (c) 16 (d) 18
9 8 7 6 5 4 3 2 1

9 8 7 6 5 4 3 2 1 Sender Receiver

1 Window size : 3
9 8 7 6 5 4 3 2 1 2
3 1
2
9 8 7 6 5 4 3 2 1 4 3
5
6 4
9 8 7 6 5 4 3 2 1 X
7
5 X
6 X
9 8 7 6 5 4 3 2 1 5
7
6
8 X
9 8 7 6 5 4 3 2 1
9
7 X
9 8 7 6 5 4 3 2 1 8 X
9 7
8
9 8 7 6 5 4 3 2 1 X
9
9
Problem on Go-back-N ARQ
Host A wants to send 10 frames to Host B. The hosts agreed to go with
Go-back-4. How many number of frames are transmitted by Host A if
every 6th frame that is transmitted by host A is either corrupted or lost?
(a) 12 (b)16 (c)17 (d) 18
Problem on Selective Repeat
In SR protocol, suppose frames through 0 to 4 have been transmitted.
Now, imagine that 0 times out, 5 (a new frame) is transmitted, 1 times
out, 2 times out and 6 (another new frame) is transmitted. At this
point, what will be the outstanding packets in senders window?
a. 341526
b. 3405126
c. 0123456
d. 654321
e. 6215043
Compare Go-Back-4 ARQ and SR ARQ
Host A wants to send 10 frames to Host B. The hosts agreed to go with
Go-back-4. How many number of frames are transmitted by Host A if
every 6th frame that is transmitted by host A is either corrupted or lost?
Also compare the number of transmissions of SR ARQ with Go-Back-4
ARQ.
Piggy Backing
• Piggybacking
• Piggybacking is a method of attaching acknowledgment to the
outgoing data packet. The concept of piggybacking is explained as
follows
• Consider a two-way transmission between host A and host B. When
host A sends a data frame to B, then B does not send the
acknowledgment of the frame sent immediately. The
acknowledgment is delayed until the next data frame of host B is
available for transmission. The delayed acknowledgment is then
attached to the outgoing data frame of B. This process of delaying
acknowledgment so that it can be attached to the outgoing frame is
called piggybacking.
we can see in the figure with piggybacking, a single message (ACK + DATA) over the wire in place of
two separate messages. Piggybacking improves the efficiency of the bidirectional protocols.
 Datalink Layer

Medium Access Control Layer Logical Link Control Layer

(MAC Layer) (LLC Layer)

➢ MAC sublayer controls device interaction

➢ LLC sublayer deals with addressing and multiplexing
Networks can be divided into two categories.

1. Point-to-point connections
2. Broadcast connections

In any broadcast network, the key issue is how to determine who gets to use
channel when there is a competition for it.

Example: Telecommunication

Broadcast channels are sometimes referred to as multiaccess channels or

random access channels.
The Medium Access control sublayer
• Responsible for deciding who sends next on a multi-access link.

Transport

Network

Datalink
LLC

MAC Physical
• The protocols used to determine who goes next on a
multiaccess channel (that belong to a sublayer of the
datalink layer) is called Medium Access Control (MAC)
sublayer.

• Especially important in LAN’s (broadcast in nature)

and in wireless communication.

• WANs use point-to-point links with exception of

satellite links.
Channel Allocation Problem
➢Channel allocation is a process in which a single channel is divided
and allocated to multiple users in order to carry user specific tasks.
➢If there are N number of users then the channel is divided into N
equal-sized sub channels.
➢Each user is assigned one portion.
➢There are two types of channel allocation.
• Static Channel allocation
• Dynamic Channel allocation
Static channel allocation
• A fixed portion of the frequency channel is allotted to the user.
• There is no interference between the users since each user is
assigned with a fixed channel.
• Traditionally capacity of the channel is split among multiple
competing users. Eg: FDM
• However, when the number of senders is large and varying, or the
traffic is heavy FDM presents some problems.
• Dividing the channel into constant number of users of static sub
channels is inherently inefficient.
Dynamic channel allocation
• Frequency bands are not permanently assigned to the users. Instead
channels are allotted to users dynamically as needed, from a central
pool.
• The allocation is done considering a number of parameters so that
transmission interference is minimized.
Assumptions of dynamic channel allocation
• Station model
• Single channel assumption
• Collision assumption
• Continuous timer
• Slotted time
• Carrier sense
• No carrier sense
Multiple Access Protocols
• If there is a dedicated link between the sender and receiver then
datalink control layer is sufficient, however if there is no dedicated
link then multiple stations can access the channel simultaneously
which may lead to collision.
• Hence multiple access protocols are required to decrease collision
and avoid crosstalk.
ALOHA
• Abramsons Logic Of Hiring Access (ALOHA)
• It is designed for WLAN but also applicable for shared medium.
• Here multiple stations can transmit data at the same time and can hence
lead to collisions and data gets garbled.
• ALOHA divided into two types
• Pure ALOHA
• Slotted ALOHA
Pure ALOHA
• Pure ALOHA allows stations to transmit whenever they
have data to be sent.
• When a station sends data it waits for an
acknowledgement.
• If the acknowledgement doesn’t come within the allotted
time then the station waits for a random amount of time
called back-off time (Tb) and resends the data.
• Since different stations wait for different amount of time,
the probability of further collision decreases.
• Whenever two frames try to occupy the channel
at the same time, there will be a collision and
both will be garbled.

• If the first bit of a new frame overlaps with the

last bit of a frame which is almost finished, both
frames will be totally destroyed and both will
have to be transmitted later.
Slotted ALOHA

• It was developed to improve the efficiency of pure ALOHA as

the chances for collision in pure ALOHA is high.

• The time of the shared channel is divided into discrete time

intervals called slots.

• Sending of data is allowed only at the beginning of these

slots.
Carrier Sense Multiple Access (CSMA)
• To minimize the chance of collision and therefore increase the
performance, the CSMA was developed.
• Principle of CSMA: “sense before transmit” or “listen before talk”.
• Carrier busy=Transmission is taking place.
• Carrier idle=No transmission currently place.
• The possibility of collision still exists because of propagation delay;
station may sense the medium and find it idle, only because the first
bit sent by another station has not yet been received .
Types of CSMA
• 1- persistent CSMA
• Non- persistent CSMA
• P-persistent CSMA

• CSMA- CD (Collision Detection)

• CSMA- CA (Collision Avoidance)
1- Persistent CSMA
• Station first senses the channel before sending the data.
• If channel is idle, then the station transmits a frame.
• If busy, then it senses the transmission medium continuously until it
becomes idle.
• Since the station transmits the frame with the probability of 1 when
the carrier or channel is idle, this scheme of CSMA is called as 1-
Persistant CSMA.
• The propagation delay has an important effect on the performance of
the protocol.
Non –Persistent CSMA
• Before sending, a station senses the channel. If no one else is
sending, the station begins doing so itself.
• If the station is already in use, station does not continually sense the
channel.
• Instead it waits for random period of time and then repeats.
P –Persistent CSMA
• It applies to slotted channels
• When a station is ready to send, it senses the channel
• If channel is idle, it transmits with a probability P.
• With a probability Q=1-P, it defers until the next slot.
• If that slot is also idle, it either transmits or defers again, with
probabilities P and Q.
• This process is repeated until either the frame has been transmitted
or another station has begun transmitting.
CSMA/CD
[Link] CSMA/CD CSMA/CA

Whereas CSMA / CA is effective before a

1. CSMA / CD is effective after a collision.
collision.

Whereas CSMA / CA is commonly used in

2. CSMA / CD is used in wired networks.
wireless networks.

Whereas CSMA/ CA minimizes the possibility

3. It only reduces the recovery time.
of collision.

CSMA / CD resends the data frame whenever Whereas CSMA / CA will first transmit the
4.
a conflict occurs. intent to send for data transmission.

5. CSMA / CD is used in 802.3 standard. While CSMA / CA is used in 802.11 standard.

It is more efficient than simple CSMA(Carrier While it is similar to simple CSMA(Carrier

6.
Sense Multiple Access). Sense Multiple Access).
Collision free protocols
1. Bit map protocol
2. Binary count down protocol
Ethernet
• Ethernet is the traditional technology for connecting
devices in a wired local area network (LAN).

• It enables devices to communicate with each other via a

protocol, which is a set of rules or common network language.
Ethernet cabling
Ethernet topology
Manchester Encoding
Ethernet MAC Sublayer Protocol
 CSMA/CD with Binary Exponential Backoff
• Back-off algorithm is a collision resolution mechanism which is used in
random access MAC protocols (CSMA/CD).
• This algorithm is generally used in Ethernet to schedule retransmissions
after collisions.
Advantage –
•Collision probability decreases exponentially.
Disadvantages –
•Capture effect: Station who wins ones keeps on winning.
•Works only for 2 stations or hosts.
Ethernet performance

F- Frame length
B- bandwidth
L- cable length
C- signal propagation
E- optimal case e contention slots per frame

E=1/(1+2BLe/CF)
Switched Ethernet
Ethernet Evolution
Fast Ethernet
Gigabit Ethernet
10-Gigabit Ethernet
Retrospective on Ethernet
• No serious competitors
• Reason for its long life is, ethernet is simple and flexible.
• Cheaper and easy to maintain
• High speed
Datalink layer switching
• A switch is a small hardware device which is used to join multiple
computers together with one local area network (LAN).

• Network switches operate at layer 2 (Data link layer) in the OSI model.

• Switches are used to forward the packets based on MAC addresses.

• Switching in data link layer is done by network devices called

bridges.
Local internetworking