DATA LINK LAYER

Unit 2

[Link] Access

PSG COLLEGE OF TECHNOLOGY

DEPARTMENT OF APPLIED MATHEMATICS AND COMPUTATIONAL SCIENCES
COMPUTER NETWORKS
20XC42 & 20XW42 COMPUTER NETWORKS
Data Communication @lestariningati

Multiple /Medium Access

• Data Link Layer divided into two
sublayers
• The upper sublayer is responsible for data link control

• The lower sublayer is responsible for resolving access to the

shared media
 Multiple Access
 Problem: When two or more nodes transmit at the same time, their
frames will collide and the link bandwidth is wasted during collision
 How to coordinate the access of multiple sending/receiving nodes
to the shared link???
 Solution: We need a protocol to coordinate the transmission of the
active nodes
 These protocols are called Medium or Multiple Access Control
(MAC) Protocols belong to a sublayer of the data link layer called
MAC (Medium Access Control)
 What is expected from Multiple Access Protocols:
 Main task is to minimize collisions in order to utilize the bandwidth by:
 Determining when a station can use the link (medium)
 what a station should do when the link is busy
 what the station should do when it is involved in collision
 Taxonomy of multiple-access protocols

For wireless

LANs and WANs

CSMA/CD for bus-
LANs Cellular Telephony
topology Ethernet LANs
and CSMA/CA for
WLANs.
 RANDOM ACCESS

•Random-access implies no
station is superior to another
station and none is assigned Pure ALOHA
control over another. Slotted ALOHA
•Stations use a procedure defined CSMA/CD
by the protocol on whether or not CSMA/CA
to send a message.
•This decision depends on the
state of the medium (idle or busy).
 1. ALOHA

ALOHA is the earliest random access method

developed at the University of Hawaii in early 1970.

ALOHA was designed for a radio (wireless) LAN, but

it can be used on any shared medium.
• ALOHA shares the medium between the stations.

• When a station sends data, another station may

attempt to do so at the same time.

• The data from the two stations collide and become

damaged.
 1. ALOHA
If two or more users send their packets at the same time, a
collision occurs and the packets are destroyed.
If there is a collision,
the sender waits a random amount of time and sends it again.
The waiting time must be random. Otherwise, the same
packets will collide again
No restriction to send. If a frame is there to send ,send
Transmission Time vs
Propagation Time
 Packet delay: four sources
transmission
A propagation

B
nodal
processing queueing

dnodal = dproc + dqueue + dtrans + dprop

dproc: nodal dqueue: queueing delay

processing  time waiting at output link for
transmission
 check bit errors
 depends on congestion level of
 determine output link
router
 typically < microsecs
• Link bandwidth (capacity): maximum rate (in bps) at which the sender
can send data along the link.
• Bandwidth refers to the speed of bit transmission in a channel or
link. Often referred to as Capacity
•
• Propagation delay: time it takes the signal to travel from source to
destination. This delay is the amount of time it takes for the head of the
signal (FIRST BIT) to travel from the sender to the receiver over a
medium.

• Transmission time: time it takes for the sender to transmit all bits of the
message.
• Time from the first bit until the last bit of a message has left the
transmitting node (sender).
 Propagation and Transmission Delay

• Propagation Delay = Distance/Propagation speed

• Transmission Delay = Message size/bandwidth bps

• Latency = Propagation delay + Transmission delay +

Queueing time + Processing time

3.12
Procedure for pure ALOHA protocol—sending one frame
 Vulnerable/Critical time time for pure ALOHA protocol

Tfr= Frame
Transmission time

If the frame transmission time is Tfr, then the vulnerable time is

= 2 Tfr.
This means no station should send during the Tfr before this
station starts transmission and no station should start sending
during the T-sec period that the current station is sending.
Example 3
A pure ALOHA throughput efficiency percentage is
computed using, S = G × e−2G
•In other words, if one-half a frame is generated during one
frame transmission time (in other words, one frame during two
frame transmission times), then 18.4 percent of these frames
reach their destination successfully.

•This is an expected result because the vulnerable time is 2

times the frame transmission time.

•Therefore, if a station generates only one frame in this

vulnerable time (and no other stations generate a frame
during this time), the frame will reach its destination
successfully.
 [Link] –Advantages &

Disadvantages
Advantage of ALOHA protocols

 A node that has frames to be transmitted can transmit

continuously at the full rate of channel (R bps) if it is the
only node with frames
 Simple to be implemented
 No master station is needed to control the medium
 Disadvantage

 If (M) nodes want to transmit, many collisions can occur and

the rate allocated for each node will not be on average R/M
bps
 This causes low channel utilization
 [Link] ALOHA
 Each station must be synchronized to send frames on a
frame duration interval.(specified time slot)
 Time is divided into slots equal to a frame transmission time
(Tfr)
 Entire channel is divided into certain number of time slots
 Sending of data is allowed only at the beginning of these
slots
 A central clock or station informs all stations about the start
of a each slot
 Global Synchronization the time slots among the stations-
Cost (Node different clock speeds)
Frames in a slotted ALOHA network
 Slotted ALOHA Vulnerability

In danger time for slotted ALOHA protocol

The vulnerability time is half of the pure ALOHA

Example 4
The slotted ALOHA throughput efficiency percentage is
computed using

S = G × e−G
•Smax = 36.8% occurs at G=1
•Smax = 30.3% occurs at G=1/2
•Smax = 19.5% occurs at G=1/4

•Slotted ALOHA reduces number of collisions of pure

ALOHA to half and doubles the efficiency of pure
ALOHA
 Comparison
BASIS FOR COMPARISON Pure ALOHA Slotted ALOHA

Frame Transmission The user can transmit the The user has to wait till the
data frame whenever the next time slot start, to
station has the data to be transmit the data frame.
transmitted.

Time In Pure ALOHA the time is In Slotted ALOHA the time is

continuous. discrete.

Throughput The maximum throughput The maximum throughput

occurs at G = 1/2 which is occurs at G = 1 which is 37%.
18%

Danger Time = 2 Tfr = Tfr

 [Link]
CSMA method was developed to reduce collisions.

The chance of collision can be reduced if a station senses

the medium before trying to use it.
• Carrier sense multiple access (CSMA) requires that each
station first listen to the medium (or check the state of
the medium) before sending.

• “no more than one station can “talk” at a time”

• CSMA/CD for 802.3 Ethernet

• “Sense before Transmit” networks

• CSMA/CA for 802.11 wireless
networks
If the channel is in use, it must wait. If the medium
is idle, it may transmit
 of its
signal, it means collision occurred
own
Space Time model of CSMA
Vulnerable time in CSMA
 Types of CSMA Protocols

Different CSMA protocols that determine:

 What a station should do when the medium is idle?
 What a station should do when the medium is busy?

1. Non-Persistent CSMA
2. 1-Persistent CSMA
3. p-Persistent CSMA
 Persistence Methods

• What should a station do if the channel is

busy? What should a station do if the channel
is idle?
 1) 1-persistent CSMA
 To avoid idle channel time, 1-persistent protocol used
 Station wishing to transmit listens to the medium:
1. If medium idle, transmit immediately;
2. If medium busy, continuously listen until medium becomes idle; then transmit
immediately with probability 1
 Performance
 1-persistent stations are selfish
 If two or more stations becomes ready at the same time, collision guaranteed
 2) Non-persistent CSMA
 A station with frames to be sent, should sense the medium:
1. If medium is idle, transmit; otherwise, go to 2
2. If medium is busy, (backoff) wait a random amount of time
and repeat 1
 Performance:
 Random delays reduces probability of collisions because two
stations with data to be transmitted will wait for different
amount of times.
 Bandwidth is wasted if waiting time (backoff) is large because
medium will remain idle following end of transmission even if
one or more stations have frames to send

Random Waiting
times

Wasted time
 3) P-persistent CSMA
 Time is divided to slots where each Time unit (slot) typically equals
maximum propagation delay
 Station wishing to transmit listens to the medium:
1. If medium idle,
 transmit with probability (p), OR
 wait one time unit (slot) with probability (1 – p), then repeat 1.
2. If medium busy, continuously listen until idle and repeat step 1
3. Performance
 Reduces the possibility of collisions like non-persistent
 Reduces channel idle time like 1-persistent
P-Persistant
 CSMA/CD (Collision Detection)
 CSMA (all previous methods) has an inefficiency:
 If a collision has occurred, the channel is unstable until

colliding packets have been fully transmitted

 CSMA/CD (Carrier Sense Multiple Access with Collision
Detection) overcomes this as follows:
 While transmitting, the sender is listening to medium for
collisions.
 Sender stops transmission if collision has occurred reducing

channel wastage .
 Wait random time before you attempt to resend
CSMA/CD is Widely used for bus topology LANs (IEEE 802.3,
Ethernet).
Used in coaxial cable. You do exponetial backoff
CSMA/CD
 CSMA/CD
• Question: How long does it take to detect a collision?
• Answer: In the worst case, twice the maximum propagation delay of
the medium
Note: a = maximum propagation delay
 CSMA/CD Protocol
• Use one of the CSMA persistence algorithm
(non-persistent, 1-persistent, p-persistent) for
transmission
• If a collision is detected by a station during its
transmission then it should do the following:
– Abort transmission and
– Transmit a jam signal to notify other stations of
collision so that they will discard the transmitted frame
also to make sure that the collision signal will stay until
detected by the furthest station
– After sending the jam signal, backoff (wait) for a
random amount of time, then
– Transmit the frame again
 CSMA/CD
 Restrictions of CSMA / CD:
 Packet transmission time should be at least as long as the time
needed to detect a collision (2 * maximum propagation delay +
jam sequence transmission time)
 Otherwise, CSMA/CD does not have an advantage over CSMA
CSMA with Collision Avoidance (CSMA/ CA)
• CSMA/CD was developed for wired networks
that have low attenuation.
• Therefore, the energy level during a collision
can easily be detected.
• In a wireless network much of the energy is
lost in transmission.
• Energy level not useful for effective collision
detection as in CSMA/CD.
• Therefore, CSMA/CA tries to avoid collisions
 Collision avoidance strategies
• CSMA/CA has three collision avoidance
strategies:
• 1. Interframe space (IFS)
• 2. Contention Window
• 3. Acknowledgment
 Interframe space

• A station does not send immediately after

finding the medium idle.
• Instead it waits a period of time, called
Interframe space (IFS), since a distant station
may have already started transmitting.
• If, after the IFS time the channel is still idle, the
station can send.
• Cannot detect collision but can avoid Collision
• Can perform some kind of priority
41
 Contention window

• The contention window is an amount of time

divided into slots.
• A station that is ready to send chooses a
random number of slots as its wait time.
• During the wait time, the station monitors the
channel. If the channel is found busy, the timer is
stopped and then restarted when the channel is
idle.

42
 Acknowledgments

When a station has sent a frame, there is a time-

out on the channel
During this time-out the receiving station sends
an ACK if the data is received correctly.
If the sending station has not received an ACK
within the time-out period, the data is assumed to
be lost (either due to collision or bit errors).

43
Hidden Problem
Hidden station Problem
IEEE 802.11 CSMA\CA
 IEEE 802.11 Wireless LAN
• 802.11b • 802.11a
– 2.4-5 GHz unlicensed radio – 5-6 GHz range
spectrum – up to 54 Mbps
– up to 11 Mbps • 802.11g
– widely deployed, using base
– 2.4-5 GHz range
stations
– up to 54 Mbps
• All use CSMA/CA for
multiple access
• All have base-station and
ad-hoc network versions