Transcript MAC Protocols, Ethernet, Token Ring

An Introduction
to
Computer Networks
Lecture 5: Direct Link Networks
University of Tehran
Dept. of EE and Computer Engineering
By:
Dr. Nasser Yazdani
1
Outline





Issues
ALOHA Network
Ethernet
Token Ring
Wireless
Univ. of Tehran
Introduction to computer Network
2
Main Issues


Local Area Network (LAN) : Three or more
machines are physically connected and
communicating.
Problems:

How to connect them? Topology



How to address each machine? Addressing
How to regulate accessing to the media?




Sharing links
MAC (Media Access method or protocol)
Collision!
Different technology address each problem in
different way.
Problems are not independent
Univ. of Tehran
Introduction to computer Network
3
LAN Technologies.
Session
Transport
Network
Link
Physical
The 7-layer OSI Model
TCP
TFTP
HTTP
NNTP
Presentation
Telnet
FTP
SMTP
Application
UDP
IP
LAN-LINK
The 4-layer Internet Model
Link layer can have two types of technologies;
• Point to point link like PPP where there are only 2 nodes.
• Broadcast link like Ethernet when there are more than 2
nodes.
Univ. of Tehran
Introduction to computer Network
4
Data link sublayers
Our focus will be on
MAC sublayer.
MAC = “Medium Access Control”
Multiplexing
Media Access (MAC)
Error Detection
Framing
• The link is shared among different sender and receivers.
• Since every frame is simultaneously accessed by different nodes;
•They are called multiaccess links.
•They are called broadcast links. (important)
•LAN because of limited area.
• We need some type of medium access rules to avoid collision.
• Multicast capability of LANs.
Univ. of Tehran
Introduction to computer Network
5
Ideal Multiple Access Protocol
Broadcast channel of rate R bps
1. When one node wants to transmit, it can
send at rate R.
2. When M nodes want to transmit, each can
send at average rate R/M
3. Fully decentralized:


no special node to coordinate transmissions
no synchronization of clocks, slots
4. Simple
Univ. of Tehran
Introduction to computer Network
6
Goals of MAC Protocols
MAC Protocols arbitrate access to a
common shared channel among a
population of nodes
Goals:
1.
2.
3.
4.
5.
Fair among users
High efficiency
Low delay
Fault tolerant
Easy to implement
Univ. of Tehran
Introduction to computer Network
7
Simple
Random
Examples of MAC Protocols
Packet-Switched Radio Network
Aloha
Carrier Sense Multiple Access/Collision Detection
Complex
Deterministic
Ethernet (IEEE 802.3)
Token Passing
Token Ring (IEEE 802.5)
Fiber Distributed Data Interface (FDDI)
Wireless
Univ. of Tehran
Introduction to computer Network
8
MAC Protocols
Three broad classes:
 Channel Partitioning



Random Access



channel not divided, allow collisions
“recover” from collisions
Taking turns


divide channel into smaller “pieces” (time slots,
frequency, code)
allocate piece to node for exclusive use
Nodes take turns, but nodes with more to send
can take longer turns
Channel Reservation
Univ. of Tehran
Introduction to computer Network
9
Channel Partitioning: TDMA
TDMA: time division multiple access





access to channel in "rounds"
each station gets fixed length slot (length = pkt trans
time) in each round
unused slots go idle
example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6 idle
TDM (Time Division Multiplexing): channel divided into N
time slots, one per user; inefficient with low duty cycle
Univ. of Tehran
Introduction to computer Network
10
Channel Partitioning: FDMA
FDMA: frequency division multiple access



channel spectrum divided into frequency bands
each station assigned fixed frequency band
unused transmission time in frequency bands go idle
example: 6-station LAN, 1,3,4 have pkt, frequency bands 2,5,6
idle
frequency bands

Univ. of Tehran
Introduction to computer Network
11
Random Access Protocols

When node has packet to send




two or more transmitting nodes ➜ “collision”,
random access MAC protocol specifies:



transmit at full channel data rate R.
no a priori coordination among nodes
how to detect collisions
how to recover from collisions (e.g., via delayed
retransmissions)
Examples of random access MAC protocols:



ALOHA
slotted ALOHA
CSMA,
CSMA/CD, CSMA/CA
Univ. of Tehran
Introduction to computer Network
12
Implemented Aloha
All nodes transmit on one freq.
Central Node
Central node relays packets on
the other frequency
f0
f1
If more than one node transmit at the same time
Collision!
If there is a collision, both nodes re-transmit packets
Univ. of Tehran
Introduction to computer Network
13
Pure (unslotted) ALOHA


unslotted Aloha: simpler, no synchronization
when frame first arrives


transmit immediately
collision probability increases:

frame sent at t0 collides with other frames sent in [t01,t0+1]
Univ. of Tehran
Introduction to computer Network
14
Slotted ALOHA
Assumptions





Operation
all frames same size
time is divided into equal
size slots, time to transmit
1 frame
nodes start to transmit
frames only at beginning of
slots
nodes are synchronized
if 2 or more nodes transmit
in slot, all nodes detect
collision
Univ. of Tehran



when node obtains fresh
frame, it transmits in next
slot
no collision, node can send
new frame in next slot
if collision, node retransmits
frame in each subsequent
slot with prob. p until
success
Introduction to computer Network
15
Slotted ALOHA
Pros



Cons
single active node can
continuously transmit at
full rate of channel
highly decentralized:
only slots in nodes need
to be in sync
simple
Univ. of Tehran




collisions, wasting slots
idle slots
nodes may be able to
detect collision in less
than time to transmit
packet
clock synchronization
Introduction to computer Network
16
Pure Aloha efficiency
P(success by given node) = P(node transmits) .
P(no other node transmits in [t0-1,t0] .
P(no other node transmits in [t0,t0 +1]
= p . (1-p)N-1 . (1-p)N-1
= p . (1-p)2(N-1)
… choosing optimum p and then letting n -> infty ...
Even worse !
Univ. of Tehran
= 1/(2e) = .18
Introduction to computer Network
17
Slotted Aloha efficiency
Efficiency is the long-run
fraction of successful slots
when there are many nodes,
each with many frames to send


Suppose N nodes with
many frames to send,
each transmits in slot
with probability p
prob that node 1 has
success in a slot
= p(1-p)N-1

prob that any node has
a success = Np(1-p)N-1
Univ. of Tehran


For max efficiency with
N nodes, find p* that
maximizes
Np(1-p)N-1
For many nodes, take
limit of Np*(1-p*)N-1 as
N goes to infinity, gives
1/e = .37
At best: channel
used for useful
transmissions 37%
of time!
Introduction to computer Network
18
How to improve ALOHA


Aloha is not efficient due to collisions.
How to reduce collision and increase
efficiency?


Do not send any data if somebody else is
already transmitting. Carrier Sense.
While sending if you recognized somebody
else is also transmitting, then, there is a
collision. Please stop. Collision Detection.
Univ. of Tehran
Introduction to computer Network
19
CSMA/CD Protocol
All nodes transmit & receive on one channel
Packets are of variable size.
1. Carrier Sense: Check if the line is idle before transmitting.
2. Collision Detection: If more than one node transmit.
Collision!
All nodes detect collision, wait for random delay. Goto 1.
binary exponential backoff
Univ. of Tehran
Introduction to computer Network
20
CSMA/CD Network Size Restriction
Node must be able to hear that there is
a collision before its packet is transmitted completely.
i.e. Packet Transmission Time > Round trip propagation time
i.e. TRANSP > 2.PROP
Univ. of Tehran
Introduction to computer Network
21
Performance of CSMA/CD
Assume time-slotted channel
1. Find  ( p): Probability that exactly one node transmits in
a given slot, where:
p = Prob{a node tries to transmit a packet in a time slot},
N = number of nodes
N
 ( p)    p(1  p) N 1
1 
d
 N (1  p ) N 1  pN ( N  1)(1  p ) N  2
dp
 max  36%  40%
when : p  1 / N
Univ. of Tehran
Introduction to computer Network
22
Ethernet Overview

History
developed by Xerox PARC in mid-1970s
 roots in Aloha packet-radio network
 standardized by Xerox, DEC, and Intel in 1978
 similar to IEEE 802.3 standard
Uses CSMA/CD technique for Media access.
Uses 10Mbps physical link originally and now
extended to 100Mbps, Fast Ethernet, and recently
to 1000Mbps, Gigabit Ethernet.
Uses variable frame length, 64-1500 bytes.




Univ. of Tehran
Introduction to computer Network
23
The Original Ethernet
Repeaters
every
500m
10Mb/s
l  1500m
PROPmax  l / c  1500 / 2.5 108  6s
Thick copper
coaxial cable
TRANSP  2 PROP  TRANSP  12s
 Packetsize  12s 10Mb / s  120bits
In practice, minimum packet size = 512 bits.
• allows for extra time to detect collisions.
• allows for “repeaters” that can boost signal.
Univ. of Tehran
Introduction to computer Network
24
The Original Ethernet
Original picture drawn by Bob Metcalfe,
inventor of Ethernet (1972 – Xerox PARC)
The Ethernet protocol is implemented in Contoroler (Adaptor)
Univ. of Tehran
Introduction to computer Network
25
The Original Ethernet
Original picture drawn by Bob Metcalfe,
inventor of Ethernet (1972 – Xerox PARC)
The Ethernet protocol is implemented in Contoroler (Adaptor)
Univ. of Tehran
Introduction to computer Network
26
Ethernet Frame Format
Bytes:
7
1
6
6
Preamble SFD
DA
SA
2
Type
0-1500
Data
0-46 4
Pad CRC
1. Preamble: trains clock-recovery circuits
2. Start of Frame Delimiter: indicates start of frame
3. Destination Address: 48-bit globally unique address
assigned by manufacturer.
1b: unicast/multicast
1b: local/global address
4. Type: Indicates protocol of encapsulated data (e.g. IP
= 0x0800)
5. Pad: Zeroes used to ensure minimum frame length
6. Cyclic Redundancy Check: check sequence to detect
of Tehran
Introduction to computer Network
27
bitUniv.
errors.
Ethernet Addresses






Unique, 6 bytes or 48-bit address assigned to each
adapter by manufacturer.
It is read in : notation, for example: 8:0:e4:b1:2
An address with all 1s is a broadcast address.
multicast: first bit is 1
In order to make the address unique, first 24 bits
are assigned to manufacturers and the last 24 bits
are assigned locally.
Each adaptor accept the packet if the destination
address is its own address, broadcast address or
multicast to which this adaptor belongs.
Univ. of Tehran
Introduction to computer Network
28
The 10Mb/s Ethernet Standard
IEEE 802.3
Ethernet MAC Protocol
10Base-5
Different
physical layer
options
10Base-2
10: 10Mbs
10Base-T
10Base-F
Base: baseband 5: 500 Meter
10Base-5: Original Ethernet: large thick coaxial cable.
10Base-2: Thin coaxial cable version.
10Base-T: Voice-grade unshielded twisted-pair
Category-3 telephone cable.
10Base-F: Two optical fibers in a single cable.
Univ. of Tehran
Introduction to computer Network
29
10Base-T
“Twisted pair Ethernet”
Repeater
“Hub”
100m max cable length
Router



Designed to run over existing voice-grade “Category3” twisted pair telephone wire.
Centralized management (“managed hubs”) lead to
more reliability.
Created a huge increase in Ethernet usage.
Univ. of Tehran
Introduction to computer Network
30
Transmit Algorithm
If line is idle…
send immediately
upper bound message size of 1500 bytes
must wait 9.6us between back-to-back frames
If line is busy…
wait until idle and transmit immediately
called 1-persistent (special case of p-persistent)
(sending with probability of p)
Univ. of Tehran
Introduction to computer Network
31
Algorithm (cont)
If collision…
jam for 32 bits, then stop transmitting frame
(minimum frame is 64 bytes (header + 46 bytes of data))
delay and try again
1st time: 0 or 51.2us
2nd time: 0, 51.2, or 102.4us
3rd time51.2, 102.4, or 153.6us
nth time: k x 51.2us, for randomly selected k=0..2n - 1
give up after several tries (usually 16)
exponential backoff
Univ. of Tehran
Introduction to computer Network
32
Increasing the data rate
Increasing the data rate create the following
Problem:
 E.g. CSMA/CD at 100Mb/s over 1500m of
TRANSP  2PROP
cable:
8
PROP  1500 / 2.5 10  6s
TRANSP  12s  Packetsize  1200bits

To overcome this two techniques used:


Cable length limited to 100m:
PROP  200 / 2.5 108  Packetsize  160bits
Increase the minimum packet length.
Univ. of Tehran
Introduction to computer Network
33
Ethernet Switch
Ethernet
Switch/Bridge
Router
• If
only one computer per port, no collisions can take
place (each cable is now a self-contained point-to-point
Ethernet link).
• Capacity is increased: the switch can forward multiple
frames to different computers at the same time.
• An Ethernet switch must contain buffers to hold
Univ. of Tehran
Introduction to computer Network
34
frames
during times of
congestion.
Extending LANs
Ethernet
Switch/Bridge
Router
Ethernet
Hub
• Combinations
of Hub, switch and router
•Broadcasts by Hub is sensed by switch
Univ. of Tehran
Introduction to computer Network
35
Token Ring
Listen:
Talk:
Data
l4
l1
l3
l2
Token/Data
PROP  i li / c  TRTmin
TRT=Token Rotation Time
Univ. of Tehran
Introduction to computer Network
36
Token Ring (cont)


It is like people talking in a ring in the round
robin manner.
Common features.




Frames flow in one direction: upstream to
downstream
special bit pattern (token) rotates around ring
must capture token before transmitting
release token after done transmitting




immediate release
delayed release
remove your frame when it comes back around
stations get round-robin service
Univ. of Tehran
Introduction to computer Network
37
Release After Reception (RAR)


Computer captures token, transmits data, waits for
data to successfully travel around ring, then releases
token again.
Allows computer to detect errored frames and
retransmit them.
Example time evolution in which host 1 and host 3 have packets to transmit:
TRANSP
PROP
TRANST
Data
Token
l1/c l2/c
Token arrives
at host 1
Univ. of Tehran
TRANST
lN/c
TRANSP
Data
Token
l1/c
l2/c
Token departs Token arrives
at host 3
from host 1
Token arrives
at host 2
Introduction to computer Network
l3/c
time
38
Release After Transmission
(RAT)


Computer captures token, transmits data, then
releases token again.
FDDI uses this technique.
Example time evolution in which host 1 and host 3 have packets to
transmit:
TRANSP
Data
TRANST TRANST
Token
l1/c
Token arrives
at host 1
Univ. of Tehran
Token departs
from host 1
Token
TRANSP
Data
l2/c
Token arrives
at host 3
Token
time
Token arrives
at host 2
Introduction to computer Network
39
Timed Token Algorithm

Token Holding Time (THT)


Token Rotation Time (TRT)


how long it takes the token to traverse the ring.
ActiveNodes x THT + RingLatency  TRT
Target Token Rotation Time (TTRT) (FDDI)


upper limit on how long a station can hold the token
agreed-upon upper bound on TRT
Each node measures TRT between successive
tokens


if measured-TRT > TTRT: token is late so don’t send
if measured-TRT < TTRT: token is early so OK to
send
Univ. of Tehran
Introduction to computer Network
40
Token Maintenance

Lost Token



no token when initializing ring
bit error corrupts token pattern
node holding token crashes
Solution- have a monitor

Monitor role in the link



Generating Tokens
Announces its presence periodically
Check for the corrupt or orphaned frames and
remove them from the ring. Orphaned frame are
those whose sending station have died. Sets the
monitor bit to 0 in sending and to 1 when pass
the monitor.
Univ. of Tehran
Introduction to computer Network
41
Token Maintenance (cont)


How about when the monitor dies? Or the network
just powered up?
Any station tries to become monitor



send a claim frame that includes the node’s TTRT bid
if your claim frame makes it all the way around the ring:
 Everyone has accepted you as the monitor
 everyone knows TTRT
 you insert new token
How about receiving another monitor claim at the
same time? Break the tie with



The lowest TTRT bid wins.
The highest address wins.
Etc.
Univ. of Tehran
Introduction to computer Network
42
Maintenance (cont)

Monitoring for a Valid Token



should periodically see valid transmission
(frame or token)
maximum gap = ring latency + max frame <
= 2.5ms
set timer at 2.5ms and send claim frame if it
fires
Univ. of Tehran
Introduction to computer Network
43
Frame format
Bytes 1
Start
Delimt.




1
Access
control
1
Frame
control
6
6
Dest.
Addr
Src.
Addr
Variable
Body
4
Checks
um
1
1
End
Delimt.
Frame
status
Access control is for priority.
Frame control is a Demux key for the higher layer
protocol.
Addresses are like Ethernet. They can also be 16 bit.
Frame Status include two A and C bits.


A, Active bit, is set by the receiver indicating the station is alive
and has seen the frame.
C, Copy bit, is also set by the receiver indicating the frame has
been copied.
Univ. of Tehran
Introduction to computer Network
44
FDDI: Fiber Distributed






It is a Dual counter-rotating ring for fault
tolerance. It can be also Single Attachment
(SAS- Single Attachment Station).
100 Mbps on optical fibers
Up to 500 nodes
Total length less than or equal to 200 km
Uses 4B/5B encoding.
Modulation: non-return to zero with inversion
(NRZI)
Univ. of Tehran
Introduction to computer Network
45
FDDI Timed Token Rotation
Protocol
1. All hosts agree on a common Target Token Rotation
Time (TTRT). They will aim to make the token rotate
around the network at least once per TTRT. Hence,
they can each expect to see the token once
TTRT.
2. Each host on the network maintains a timed token
Rotation (TRT) timer, that indicates when the token is
next expected to arrive.
3. If the token arrives before TRT expires, we say it is
“Early”. If the token arrives after TRT expires, we say
it is “Late”.
4. A host can only transmit if it receives the token, AND
the token is Early.
Univ. of Tehran
Introduction to computer Network
46
Network Adaptors

All functionalities are implemented in
Adaptors or network cards.
Each vender has it own adaptor.
Host I/o bus

Univ. of Tehran
Bus
interface
Link
Interface
Network
Adaptor
Introduction to computer Network
47
Network Adaptors (cont)




Adaptor, like other devices, are
programmed by CPU.
Adaptor has a Control Status Register
(CSR), usually located in the memory.
CPU communicate with Adaptor through
CSR.
Two methods for Communication, polling
and interrupt.
Univ. of Tehran
Introduction to computer Network
48
Network Adaptors (cont)



How to transfer data? Direct memory access
(DMA) and programmed I/O (PIO)
Device drivers are routines to connect OS
with the network hardware.
Memory is bottleneck. Each frame might be
written/read several times from the memory.

It has limited Bandwidth, usually 32 bit x 300
MHz, (around 10 Gbps), however, each packet
goes at least two time and there are overheads.
Univ. of Tehran
Introduction to computer Network
49