Link Layer Review

Eleftheria Psilou
psilou@[Link]
Switched LANs
1. Operate at the Link Layer

2. Switch link-layer frames

3. Use link-layer addresses to forward

frames

Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis

MAC Addresses
Globally unique

Flat structure (not hierarchical like IP)

Constant

Necessary for communication on a local area network (LAN).

Devices use the Address Resolution Protocol to acquire the MAC address of
another device.

Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis

Sending a frame
1. Insert the destination MAC address into
the frame
2. Send the frame into the LAN

Receiving a frame
Is the destination address my own MAC address?
Yes: Extract datagram and pass it up the protocol stack.
No: Discard frame

Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis

 How do the hosts know the MAC address to which to send the frame?

The ARP Table!

Each host has an ARP table in its memory
(MAC) (TTL)

Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis

Address Resolution Protocol - Filling the ARP table
BROADCAST

Physical address
of node with IP
[Link]

Request

Reply

UNICAST

A4:6E:F4:59:83:AB
Link-Layer Switches
They receive incoming link-layer frames and forward them onto outgoing links.

They are transparent to the hosts and routers in the subnet.

For scenarios of very high rate of frames arrival, switch output interfaces have
buffers.

Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis

Switch Operation
Filtering:
Drop or forward frame?

Forwarding:
Which interface should a frame be directed to?

These are achieved with a switch table, which contains:

● MAC address (switches don’t use IP!*)

● switch interface → MAC address
● time of entry
Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis
Switch Operation
A Frame with destination address DD-DD-DD-DD-DD-DD arrives at the switch on
interface 1.
There is an entry in the There is an entry in the
table, associating table, associating
There is no entry in the table DD-DD-DD-DD-DD-DD DD-DD-DD-DD-DD-DD
for DD-DD-DD-DD-DD-DD: with interface 1: with interface y≠1:

The switch broadcasts the frame No need to forward. The switch puts the frame in an
The switch discards the frame. output buffer that precedes
interface y
Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis
Switch Self-Learning
The switch table is built automatically
and dynamically!

1. The switch table is initially empty.

2. For each incoming frame received on an interface, the switch stores in its
table:
a. the MAC address in the frame’s source address field
b. the interface from which the frame arrived
c. the current time.

3. The switch deletes an address in the table if no frames are received with that
address as the source address after some period of time (the aging time)
Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis
[Link]
 Switches VS Routers

Switches → small networks:

localize traffic, increase aggregate throughput without requiring any configuration
of IP addresses
Routers → larger networks (in addition to switches):
Routers provide a more robust isolation of traffic, control broadcast storms, and
use more “intelligent” routes among the hosts in the network.
Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis
Multiple Access Links
If there is no dedicated link between sender and receiver, multiple stations can
access the channel simultaneously.

Multiple Access Control is required to decrease collision and avoid crosstalk

-> Multiple Access Protocols
[Link]
Random Access Protocols
They allow multiple devices to access a shared communication channel or
medium in random or arbitrary order.

- No fixed time for sending data

- No fixed sequence of devices sending data
Pure ALOHA
● Each node sends a frame whenever one is available
● Receivers send acknowledgements to the senders when they receive a frame
The senders wait for a time-out period before retransmission

Only one channel and many nodes -> chance of collision

● If there is a collision, each node

has to back off before it tries to
retransmit
● The backoff is a random amount
of time (to avoid further collisions)
Slotted ALOHA
Improvement on pure ALOHA

● The channel is divided into small, fixed-length time slots

● Users are only allowed to transmit data at the beginning of each time slot
● The data transmitted must fit in the
time slot

Synchronizing the transmissions

reduces the chances of collisions
Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis
Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis
Pure ALOHA efficiency

“Efficiency” - the probability of a node transmitting successfully

In our case:

So, the efficiency in general is: N p(1-p)N

where N is the number of nodes in the network

CSMA
The node is required to first sense the medium before transmitting data

- Channel is idle: begin transmission

- Channel is busy: wait until channel is idle

Still a chance of collision

due to propagation delay!

[Link]
CSMA/CD
CSMA variant, “Collision Detection”

Stations can terminate transmission of data if collision is detected.

While transmitting, if the adapter senses other transmissions in the channel other
than its own, it sends a jam signal and aborts the transmission.

It backs off for a random amount of time and then senses the channel again.
CSMA/CD - Exponential Backoff
The backoff period is selected at random (uniformly), from the set {0, 1, …, 2 K -1},
where K is the number of failed attempts to send a particular frame.

Example:
Attempt 1: Collision -> K=1
Backoff selected from {0, 1}
Attempt 2: Collision -> K=2
Backoff selected from {0, 1, 2, 3}
Attempt 3: Collision -> K=3
Backoff selected from {0, 1, 2, 3, 4, 5, 6, 7}
…
Error Detection and Correction
Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis
Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis
 1 0 1 0 1 1

1 1 1 1 0 0

0 1 1 1 0 1

0 0 1 0 1 0
1 0 1 0 1 1

1 0 1 1 0 0

0 1 1 1 0 1

0 0 1 0 1 0
Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis
Which one has the error?
Can we identify it?

1 0 1 0 1 1 1 0 1 0 1 1

1 1 1 1 0 0 1 0 1 1 0 0

0 1 1 1 0 1 0 1 1 1 0 1

0 0 1 0 1 0 0 0 1 0 1 0

Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis

Which one has the error?
Can we identify it?

1 0 1 0 1 1 1 0 1 0 1 1

1 1 1 1 0 0 1 0 1 1 0 0

0 1 1 1 0 1 0 1 1 1 0 1

0 0 1 0 1 0 0 0 1 0 1 0

Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis

Which one has the error?
Can we identify it?

1 0 1 0 1 1 1 0 1 0 1 1

1 1 1 1 0 0 1 0 1 1 0 0

0 1 1 1 0 1 0 1 1 1 0 1

0 0 1 0 1 0 0 0 1 0 1 0

Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis

Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis
Adapted from HY335a: Link Layer Workshop 2023 by Ioannis Fotis