Transcript - Muhazam

EEC4113
Data Communication &
Multimedia System
Chapter 6: Media Access Control
of Data Link Sub-Layer
by Muhazam Mustapha, October 2011
Learning Outcome
• By the end of this chapter, students are
expected to understand and able to
explain the various protocols and
technologies in MAC sub-layer
Chapter Content
•
•
•
•
•
•
•
•
MAC Sub-Layer Issues
ALOHA Protocols
CSMA Protocols
Collision-Free Protocols
Topology
IEEE 802.3 Ethernet
IEEE 802.11/15/16 Wireless Ethernet
IEEE 802.5 Token Ring
Media Access Control
Sub-Layer
CO1
Media Access Control
• Media Access Control is a sub-layer of
data link layer in OSI’s 7 layer model
• Provides access to the shared networking
medium in LAN or MAN
• The currently most popular technology that
provides MAC is the Ethernet technology
• Others are FDDI (Fiber Distributed Data
Interface), ARCNET and Token ring
CO1
Ethernet
• A family of frame-based
technology defining standards
for wiring and signaling
• Standardized in IEEE 802.3
document
• Combination of twisted wire pair
and optical fiber
• Characterized by the used of
8P8C connector
CO1
Shared Network Medium
• In shared environment, packets sent by one
sender will be received by all nodes, but only the
packet addressee will process it, the rest will
discard
packet
sent out
sender
recipient
CO1
Multiple Access Protocol
• Since the network medium is shared, there
is a need to resolve competition between
the nodes
• Two general schemes:
– Static
• Frequency / Time Division Multiplexing
(digital communication)
– Dynamic
• ALOHA, Carrier Sense Multiple Access
(data communication)
CO1
Channel Allocation Problem
• In shared medium, a user will first listen to
the channel for its availability, then sends
its frame
• COLLISION occurs when more than one
user start using the medium at the same
time
• At collision incidence, both user release
the medium and wait for random time
before re-sending
CO1
ALOHA Protocols
CO1
ALOHA Protocols
• Created in 1970s in the University of
Hawaii by Norman Abramson
• First ingenious method to resolve channel
allocation problem
• It was best for wireless communication
and the concept is still in used by modern
protocol like Wi-fi
CO1
Pure ALOHA
•
Basic ideas:
1. Anyone is allowed to transmit their data
whenever they have something to transmit,
without checking the channel availability first
2. After sending, the sender will listen to its
own frequency to tell whether its frame has
been destroyed due to collision or not
•
•
CO1
This is possible due to feedback property of
broadcasting channel, or
The sender will require an acknowledgement
Pure ALOHA
•
Basic ideas:
3. If there is no feedback, then there is collision
4. If collision occurs, the sender will wait for a
random amount of time, then re-send – this
called backoff
CO1
Pure ALOHA
User
A
B
C
D
E
Time
CO1
Slotted ALOHA
• Time is divided into slots, and users can
only transmit at start of slot
• Resulting advantage: Efficiency is doubled
(see graph)
• Disadvantages:
– Requires synchronization clock
– Still poor at high loads (see graph)
CO1
S (throughput per frame time)
Pure vs Slotted ALOHA
0.40
Slotted ALOHA: S = Ge-G
0.30
0.20
Pure ALOHA: S = Ge-2G
0.10
0.5
1.0
1.5
2.0
2.5
G (attempts per packet time)
CO1
3.0
Carrier Sense Multiple Access
Protocols
CO1
Carrier Sensing Protocols
• Network communication can be improved
greatly if the nodes can sense the
existence of any transmission signal inside
the transmission medium
• Implemented in Carrier Sense Multiple
Access (CSMA) and a few of its variations
• Improvement is due to the fact that
collisions is reduced since hosts will only
send data if medium is not in use
CO1
CSMA
• A host that needs to transmit data will first
listen into communication medium and
decide whether another host is using the
medium or not
• The host will only transmit its data if no
one is using the medium
• After finish sending the data frame, there
will be an interframe gap of 9.6μs idle
before any host can take the medium
CO1
Persistent and Non-persistent
CSMA
• CSMA is called persistent if:
– when sensing that a medium is being used,
the host waits and will definitely transmit once
the current transmission ends
• may cause collision if more than one host was
waiting
• And non-persistent if:
– the host waits for a random duration and resends only if no one using it
CO1
• results in less collision
CSMA/CD (Collision Detection)
• The system will be having 3 states:
transmission, contention and idle
• Transmission state is the state where one
host sends data.
• After that host finishes, more than one of
other hosts might be sending at the same
time – a collision
CO1
CSMA/CD (Collision Detection)
• On sensing a collision, all hosts involve
would release the medium and they send
a jamming signal to tell others that there is
collision happened
– so that everyone releases the medium
• Then they will wait for a random duration
and re-try
• The above two steps is the contention
state
CO1
CSMA/CD (Collision Detection)
• Once one of the competing host gains
control the system is in transmission state
again
• Idle state is just the state that no one is
using the medium
collisions
transmission
transmission
contention
CO1
transmission
contention
transmission
idle
CSMA/CA (Collision Avoidance)
• CSMA/CD is a persistence variation of
CSMA – it handles collision when it
happens
• CSMA/CA is a non-persistence variation
CSMA
• CSMA/CA avoids collision by
– not sending jamming signal
– instead, just wait for a random duration then
re-sends if no one is using
CO1
Collision-Free Protocol
CO1
Collision-Free Protocols
• In collision free protocols, instead of
sensing the medium, the hosts will tell if
they want to transmit
• There is a special frame called contention
frame whose content is contributed by all
hosts
CO1
Collision-Free Protocols
• Contention frame is slotted and the hosts
will take turns at a very precise timing to
write information into the frame
• A host sets a binary 1 at bit location
reserved for it in contention frame if it
wants to use the medium
CO1
Collision-Free Protocols
• Once all hosts write the binary bits
according to its intention, the actual
transmission will be granted to the
requesting hosts in sequence.
• Once all transmissions finish, the hosts will
then re-fill the contention frame
• This protocol is called basic bit-map
protocol
CO1
Collision-Free Protocols
8 contention
slots
8 contention
slots
0 1 2 3 4 5 6 7
1
1
1
0 1 2 3 4 5 6 7
1
3
frames
CO1
8 contention
slots
7
1
1
0 1 2 3 4 5 6 7
1
5
frames
1
2
frames
Ethernet Topology
CO1
Topology
Bus
Linear Bus
– 2 ends
Distributed
Bus – more
than 2 ends
CO1
Topology
Star
Ring
CO1
Topology
Mesh
Tree
CO1
Bus Topology
• Use of multipoint medium
• All stations attach directly to transmission
medium (bus) through appropriate
hardware interfacing known as tap
CO1
Bus Topology
• A transmission from any station
propagates the length of the medium in
both directions & can be received by all
other stations
• At each end of the bus is a terminator,
which absorbs any signal, removing it from
the bus
CO1
Tree Topology
• Use of multipoint medium
• Transmission medium is a branching cable
with no closed loops
• Tree layout begins at a point known as the
headend
CO1
Tree Topology
• One or more cables start at the headend,
and each of these may have branches
• The branches in turn may have additional
branches to allow quite complex layouts
• A transmission from any station
propagates throughout the medium & can
be received by all other stations
CO1
Ring Topology
• Repeaters joined by point-to-point links in
closed loop
– Receive data on one link and retransmit on
another
– Links are unidirectional
– Stations attached to repeaters
CO1
Ring Topology
• Data in frames
– Circulate past all stations
– Destination recognizes address and copies
frame
– Frame circulates back to source where it is
removed
• Medium access control determines when
station can insert frame
CO1
Star Topology
• Each station connected directly to central
node
– Usually via two point-to-point links
• Two alternatives operation of central node:
– Broadcast : Physical star, logical bus
– Frame-switching device : Only one station can
CO1 transmit at a time
Star Topology
• Broadcast
– A transmission of a frame from one station to
the central node is retransmitted on all of the
outgoing links
– Central node is referred as hub
• Frame-switching device
– Incoming frame is buffered in the node &
retransmitted on an outgoing link to the
destination station
CO1
IEEE 802.3 Standard of
Ethernet
CO1
IEEE 802.3 Standard
• Defines Ethernet as CSMA/CD protocol on
bus or ring topology
• Also defines the minimum frame length
• Also defines the cabling hardware
• Frame format:
Bytes
7
1
6
6
S
Preamble O Destination Source
address address
F
CO1
0-1500
Length
Data
0-46
Pad
4
Checksum
Frame Fields
• Preamble: 7 bytes of alternating 1-s and 0s for synchronization
• Start of Frame (SOF): Sequence of
10101011
• Destination Address: 6 bytes of MAC
address
• Source Address: 6 bytes of address
• Length: Total size of data and pad
CO1
Frame Fields
• Data: Packet from upper layer
• Pad: Series of 0-s to make up a minimum
total size of 46 bytes of data and pad – so
that the min frame size is 64 bits
• Checksum: 32 bit CRC
CO1
MAC Address
• Identifying each individual network card
uniquely
• 46 bits address in 48 bits string
• Binary 0 in MSB indicates ordinary
address
• Binary 1 in MSB indicates the 46 bits
address is a group address (for multicast)
CO1
MAC Address
• If all address bit are 1-s then it is a
broadcast (all nodes are getting the
message)
• If two MSB are 0-s then the 46 bits
address is a combination of source and
destination MAC address
CO1
MAC Address
• Examples of possible MAC addresses
include:
– 00-0C-F1-56-98-AD
– 00-11-F5-4B-20-56
• The first three bytes of this address
identify the manufacture of this network
device
– 00-0C-F1 for Intel
– Assigned by the IEEE and the database is
available online at IEEE OUI and Company_id
Assignments website
CO1
Need for Frame Minimum Size
• In CSMA/CD, if there is a collision, the first
node to detect it will send a jamming
signal
• We need to calculate the maximum delay
after a node sends a message until the
first jamming signal is heard by all nodes
• Then from there we can calculate what is
the minimum frame size so that NO nodes
will finish transmitting before it hears the
jamming signal
CO1
Need for Frame Minimum Size
• The diagram below shows that there is a
maximum of 2td delay before the first
jamming signal is heard by every node
(td = propagation delay)
A
B
A
B
At t ≈ td s, the frame
almost reach the
receiver
Frame sent at t = 0s
collision
A
At t ≈ td s, suddenly
the receiver sends
out frame
CO1
B
Jamming signal
sent out
A
Jamming signal
finishes propagating
at t = 2td s
B
Need for Frame Minimum Size
(compare this calculation to link utilization calculation)
• Hence max delay is a function of bit rate,
max distance allowed and velocity of
propagation
• Given:
– Ethernet bit rate: 10 Mbps (802.3 Standard for
10Base5 and 10Base-T)
– Max distance: 500m (802.3 Standard)
– Velocity of propagation: 2 × 108 ms−1
CO1
Need for Frame Minimum Size
(compare this calculation to link utilization calculation)
• Hence:
– td = 2.5μs, hence 2td = 5μs
– Bit duration = 0.1μs
– No. bits traveling in 2td time = 50
• Adding some gap for error, the best min
frame size chosen is 64 bits
• 802.3 Std sets 512 bits as min, because it
allows max distance of 2.5km with 4
passive repeaters
CO1
Ethernet Physical Standard
• 10Base5: 10 Mbps, Baseband
transmission, 500m cable length
• 10Base2: 10 Mbps, Baseband
transmission, 200m cable length
• 10Base-T: 10 Mbps, Baseband
transmission, 500m UTP cable
• 100Base-TX: 100 Mbps, Baseband
transmission, 200m UTP cable
CO1
Ethernet Physical Standard
• Wiring:
– Unshielded Twisted Pair (UTP)
– Bundle of eight wires (only uses four)
– Terminates in RJ-45 connector
CO1
Ethernet Physical Standard
• Hubs (10Base-T):
– A kind of passive
repeater
– Used to connects nodes
in bus topology
– Max length of UTP:
100m
– Max no. hubs in series:
4
– Hence, max distance
between farthest nodes:
500m
CO1
100m
10Base-T hubs
100m
100m
100m
100m
500m, 4 hubs
Repeaters
•
•
•
•
Regenerates signal
Used to extend the network coverage
Hubs are repeaters
There will be a limit to the length of the
farthest node due to physical signal
limitation
CO1
Bridges
• Used to join LANs
• Results in local internet
• May filter the data traffic
CO1
Switches
• More intelligent kind of bridges
• Must be arranged in hierarchical
arrangement – only one path from one
switch to another
• Due to its intelligent close to a small node,
there is no limit in number of switches in a
LAN – as opposed to hubs
CO1
Hubs vs Bridges vs Switches
• Hub
– Has many ports
– Redistributes data to all nodes
– It depends on the receiver to process the data
– Almost no intelligence
– Used to extend connection within standard
limit
CO1
Hubs vs Bridges vs Switches
• Bridge
– Only two ports
– Transfers data from one end to the other only
if the receiver address is at the other end
– Have intelligence to interpret MAC addresses
– Used to join two separate LANs
CO1
Hubs vs Bridges vs Switches
• Switch
– More than two ports
– Have intelligence to interpret MAC addresses
– Transfers data from one end to another only if
the receiver address is at that end
– Extends LAN unlimitedly, but must conform to
hierarchical (tree) structure
– Router:
CO1
• Switch that works on IP address instead of MAC
• For internet instead of LAN
• Smart enough to do protocol conversion
Hubs vs Bridges vs Switches
CO1
IEEE 802.11/15/16
Standards of
Wireless Ethernet
CO1
IEEE 802.11
• Uses CSMA/CA instead of CSMA/CD
• Could not detect collision due to hidden
nodes (target nodes beyond signal range)
• Sender listen to the medium (air) to see
whether it is busy or not
• After the medium is free for a period of
DIFS (Distributed Inter-Frame Space ~
128μs), the sender sends RTS (request to
send) signal to tell its intention, and others
will make way
CO1
IEEE 802.11a
•
•
•
•
Frequency = 5 GHz
Maximum Speed = 54 Mbps
Range = about 35 meters (varies)
Encoding Scheme = Orthogonal FDM
(closely located frequencies but far
enough not to interfere each other)
CO1
IEEE 802.11b
•
•
•
•
•
Frequency = 2.4 GHz
Maximum Speed = 11 Mbps
Range = about 38 meters (varies)
Encoding Scheme = DSSS
Modulation Technique = BPSK(1 Mbps),
QPSK(2 Mbps), CCK(5.5 Mbps,11Mbps)
CO1
IEEE 802.11g
•
•
•
•
Frequency = 2.4 GHz
Maximum Speed = 54 Mbps
Range = about 38 meters (varies)
Encoding Scheme = OFDM
CO1
IEEE 802.11n
•
•
•
•
•
•
Frequency = 5 GHz, 2.4 GHz
Modulation = OFDM
Maximum Speed = 150 Mbps
Range = about 70 meters (varies)
Encoding Scheme = OFDM
Addition of MIMO (Multiple Input Multiple
Output)
– sender and receiver have 2 antennas to send
and receive 2 signals (one is modified
CO1 redundancy) to improve performance
IEEE 802.16 – WiMAX
• WiMAX is 802.11/Wi-Fi networks with
coverage and cellular networks quality of
service
• Stands for "Worldwide Interoperability for
Microwave Access"
• Most of WiMAX physical layer definitions
and topology follows those of 802.11
• Provider in Malaysia: P1 & Yes
CO1
IEEE 802.16 – WiMAX
• Consists of two standards – Fixed &
Mobile
• Fixed WiMAX (IEEE 802.16d)
– Speed = up to 70 Mbps
– Range = up to 50 km
• Mobile WiMAX (IEEE 802.16e)
– Speed = up to 30 Mbps
– Range = up to 15 km
CO1
IEEE 802.15 – Bluetooth
• Open proprietary standard created by
Ericsson
• Not a direct descendent if 802.11
• Designed for communication between
electronics devices as alternative to
cabled RS-232
• Consisting of 1 master devices and up to 8
slaves
• Logo:
CO1
IEEE 802.15 – Bluetooth
•
•
•
•
Frequency = 2.4-2.8 GHz
Speed = 1 Mbps
Range = 10 meters
Encoding Scheme = FHSS with 79
channels at 1600 hops per second
• Most common uses: Mobile phone
headset, wireless mouse & keyboard
CO1
Token Based Protocol
CO1
IEEE 802.5 Token Ring
• The network is arranged in ring topology
• There is a special frame to be passed
around the nodes named TOKEN
• Whoever is having the token can transmit
data into transmission medium, otherwise
it passes the token to the next node
CO1
IEEE 802.5 Token Ring
CO1
IEEE 802.4 Token Bus
• The network is arranged in bus topology
• Just as token ring, there is a special frame
TOKEN used
• Whoever is having the token can transmit
data into transmission medium, otherwise
it passes the token to the next node
• The use of this type of protocol is shown
by the presence of coaxial cable connector
on the network card instead of 8P8C
CO1
FDDI
•
•
•
•
Fiber Distributed Data Interface
Data rate = 100Mbps
Used as a backbone
With multi-mode fiber any given ring
segment can be up to 200 km in length
• A total of 500 stations can be connected
with a maximum separation of 2 km
• Two complete rings to overcome failures
CO1
FDDI
CO1
FDDI Interface in High Speed LANs
CO1