CSIS 625 Week
6
LANs and MAC sublayer
Copyright 2001 and
2002 – Daniel R. Oelke
For use by students
of CSIS 625 for purposes of this class only.
I.
Overview
A.
MAC Layer
1.
Aloha
2.
CSMA
B.
LAN
1.
Ethernet Technology
2.
Lesser used LAN technologies
a)
Token Bus, Token Ring, FDDI,
Others
3.
Newer fields
a)
Wireless Ethernet, Resilient Packet Rings, Others
C.
Further reference
II.
MAC - Media Access Control
A.
Need for MAC layer
1.
When there are multiple nodes that can all transmit on a given
link, a means of controlling them is necessary
2.
The MAC layer is a sub-layer of data link layer in these
situations.
3.
The Logical Link Control (LLC) Layer is the other sub-layer
4.
MAC is the lower sub-layer, LLC is the upper sub-layer
B.
MAC assumptions
1.
Station Model
a)
There are N
independent stations (aka nodes) that
generates frames of data for transmission
2.
Single Communications Channel
3.
Collision detection
a)
All stations can detect collisions
4.
Time frame
a)
Continuous time - any frames starts at any time
b)
Slotted time - Time divides into discrete slots
5.
Carrier sense (or not)
a)
The nodes can detect if the channel is busy
C.
ALOHA protocol
1.
Ground based radio broadcasting
2.
Developed at University of Hawaii
3.
Pure ALOHA
a)
Any node starts transmitting at any time
b)
Receiving node detects if a collision occurs
(1)
Same if partially or completely clobbered
c)
If data not properly received, the transmitter waits a random
amount of time and resends.
4.
Slotted ALOHA
a)
A special node emits a “pip” at the start of each interval.
b)
All frames start at the beginning of an interval
5.
Load capabilities
a)
Both Pure ALOHA and Slotted ALOHA have a point at which adding
more traffic results in worse throughput
b)
The collisions keep piling up and causing more and more
collisions
c)
Slotted ALOHA will take about 2x as much load as Pure ALOHA
D.
Carrier Sense Multiple Access (CSMA) Protocols
1.
Nodes listen to see if someone else is transmitting before
they send their packet.
a)
Better performance than ALOHA
2.
1-Persistent CSMA
a)
Transmitter waits until the the line is idle and sends
immediately
3.
Nonpersistent CSMA
a)
Transmitter waits random time time if the line isn’t idle
b)
Leads to better utilization AND longer delays
4.
p-Persistent CSMA
a)
Uses slotted channels - If slot is idle there is a probability
of p that transmitter will use the channel.
E.
CSMA/CD - Carrier Sense Multiple Access with Collision
Detection
1.
Extend the idea so that if two nodes detect a collision they
stop transmitting immediately
2.
Quickly terminating the transmission saves time and bandwidth
3.
To detect collision, need to transmit for 2x the maximum
propagation time.
a)
Time for signal to transmit from one end to the other
b)
PLUS Time for colliding signal to transmit from far end back
F.
Wireless Protocols
1.
Typically nodes are all trying to talk with a central (wired)
hub
2.
Sometimes (but not always) the nodes can “hear” one another
3.
Hidden station problem
a)
When one node can’t hear another and tromps on transmission to
a third node
4.
Exposed station problem
a)
When one node hears another node and so won’t transmit to a
third, even through it could.
5.
Wireless Protocols and CSMA
a)
CSMA tells the transmitter if there is activity near, but you
want to know if there is activity by the receiver.
b)
MACA - Multiple Access with Collision Avoidance.
c)
MACAW - MACA with refinements
d)
CSMA/CA - another name for MACA like system
(1)
Carrier Sense Multiple Access with Collision Avoidance
6.
MACAW basics - A sending to B
a)
A sends B an RTS (Request to Send) frame with length
b)
B sends A a CTS (Clear to Send) frame with length
c)
A sends B the data frame
d)
Other nodes that hear CTS know to be quiet for that time
period (based on length)
III.
LAN technology
A.
Ethernet - IEEE 802 Standards for LANs
1.
IEEE has produced many standards for LANs (and MANs)
2.
The 802 standards include
a)
CSMA/CD (Ethernet)
b)
Token bus
c)
Token ring
3.
The 802 standards include a lot of different physical and MAC
layer, but are compatible at the data link layer
4.
802.3 Standard
a)
This is basically the Ethernet standard
b)
Ethernet started as a 2.94Mbps over a 1km coaxial cable at
Xerox PARC - modeled after ALOHA system
c)
Xerox, DEC and Intel created 10Mbps Ethernet that became the
802.3 standard.
d)
1-persistent
CSMA/CD LAN
5.
802.3 Cabling
a)
10Base5 - Thick Coax - 400m segment - 100 nodes
b)
10Base2 - Thin Coax - 200m segment - 30 nodes
c)
10Broad36 - Thin coax - 1800m segment - uses RF modulation
d)
10Base-T - twisted pair - 100m segment - 1024 nodes
e)
10Base-F - fiber optics - 2000m segment - 1024 nodes
f)
100Base-T - twisted pair - 100m segment - uses 2 pair Cat 5
cabling - full duplex
g)
100Base-T4 - twisted pair - 100m segment - uses 4 pair Cat 3
cabling (not used)
h)
100Base-FX - fiber - 2000m segment - full duplex
i)
1000Base-T - twisted pair - 100m segment - uses 4 pair Cat 5
6.
802.3 MAC sublayer
a)
Preamble - 7 bytes of 10101010 so that receiver’s clock can
synchronize with the senders clock
b)
Start of frame delimiter - 1 byte of 10101011
c)
Destination Address - 6 byte unique address
d)
Source Address - 6 byte unique address
e)
Length - 2 bytes (At least 46 bytes)
f)
Data - 0-1500 bytes
g)
Pad - 0-46 bytes
h)
CRC - 4 bytes
7.
Addresses
a)
High order bit is 0 for ordinary, 1 for multicast addresses
b)
An address of all 1’s is for broadcast
c)
bit 46 (next to high order bit) is local/global administration
d)
2^46 = 70,368,744,177,664 addresses
e)
IEEE sells blocks where manufacturer is given the first 3
bytes, and then the manufacturer is responsible for the last 3 bytes.
8.
The length of a frame must be at least 64 bytes
a)
This is a 46 byte data/pad field + 18 bytes for header and CRC
b)
A 10Mbps Ethernet with 2500m of cable and 4 repeaters (from
the standard) has a transmission time of 25.6usec
c)
2x this time is 51.2usec which corresponds to 64 bytes
9.
Binary Exponential Backoff Algorithm
a)
When collision - each station waits a number of time slots
before trying again
(1)
A time slot is defined as 51.2usec
b)
After a collision each station waits for 0 or 1 slot times
before trying again
c)
After the second collision -
0 - 3 slot times
d)
After each subsequent collision each station waits 0 to 2n
- 1 time slots
e)
After 10 collisions, the value for n is frozen
f)
After 16 collisions the controller throws away frame
10.
Full-Duplex Ethernet
a)
Used on point-to-point links with Ethernet switches.
b)
Requires that the medium support a full-duplex connection
c)
Removes CSMA/CD - can always transmit at will
d)
Because no collision detection is necessary, the length of a
segment can be much longer (100Base-FX is 2km)
e)
Introduces the concept of a Pause frame where one node tells
the other to stop transmitting
11.
Ethernet terminology
a)
Runt - a frame that is less than 64 bytes long
b)
Capture effect - the tendency of a station to keep the segment
because others keep backing off more and more
c)
BLAM - Binary logarithmic arbitration method - an alternative
to Binary exponential backoff that reduces capture effect
d)
Collision Domain – the group of nodes that are using CSMA/CD
between them.
e)
Bridge – a device which connects 2 or more networks at layer
2.
f)
Switch = Bridge - works at L2 (data link) layer
(1)
Switch is newer name - faster & done in HW.
(2)
Bridges are older and often done in SW
(3)
Allows use of full-duplex links
g)
Hub = Repeater - works at physical layer
(1)
Regenerates signal
(2)
Must be a half-duplex link connected to these
h)
Baseband – use of digital signals
i)
Broadband – use of RF modulated signals
12.
Ethernet Auto negotiation
a)
This is a technology introduced with 100Base-T to allow a
hub/switch and an Ethernet end station to automatically determine each other’s
capabilities.
b)
Allows two ends to negotiate
(1)
10Mbps, 100Mbps, 1000Mbps
(2)
Half-duplex, Full-duplex,
(3)
Ability to handle Pause frames, etc.
c)
Problems commonly occur with some types of cards and some
types of switches
(1)
This causes many network administrators to turn off
autonegotiation and force all stations to a particular setting (usually
100Mbps, Full-duplex)
13.
Ethernet Physical
Layer
a)
10BaseT Ethernet - 2 pair Cat 3
(1)
Uses Manchester encoding
(a)
This results in 10 to 20 million transitions per second on the
line
(b)
Spectrum is in the 5-10Mhz range
b)
100BaseFx Ethernet
(1)
Uses 4b5b-NRZI on fiber
(a)
This increases the bits sent to 125Mbps
c)
100BaseT Ethernet - 2 pair Cat 5
(1)
Uses 4b5b MLT-3 on twisted pair
d)
1000BaseX Ethernet -
(1)
Uses 8b10b NRZ @ 1.25Gbaud
(2)
8b10b Ensures 50% ones density
e)
1000BaseT Ethernet - 4 pair Cat 5
(1)
Uses PAM5 (Pulse Amplitude Modulation)
(a)
Provides 2 bits, plus extra symbol for FEC, special codes,
transition density.
(2)
Each pair is used in both directions with echo cancellation
(3)
The use of PAM5 is a
6dB hit, but made up for with FEC.
f)
10G Ethernet
(1)
Use of PAM5 on Fiber?
(2)
Use of SONET framing?
(3)
Wait and see
g)
All 100Base & 1000Base
(1)
Send idle codes when line is not in use.
(2)
Keeps clocks in sync.
(3)
Lets connections know when cable is broken
h)
10BaseX
(1)
Had link pulse to keep nodes aware of connection status, but
that isn’t used now that everything is point to point.
14.
4b5b - Why
a)
only 16 of the 32 5b symbols needed for data.
(1)
Plus a few for control
b)
Ensures that transitions still present on line for clock
recovery
(1)
No more than 3 zeros in a row
c)
More efficient than Manchester
15.
MLT-3 - Multi Level Transmit
a)
Transition on a 1, no transition on a 0
b)
Goes +1, 0, -1, 0, +1, 0, -1, 0, etc.
c)
Reduces bandwidth to 31.25Mhz
16.
Ethernet MLT-3 & PAM-5
a)
Eye diagrams for MLT-3 from 100BaseT and PAM-5 from 1000BaseT
b)
100Base-T2 also uses PAM5
17.
Collision Domain
a)
10BaseX
(1)
512 bit times => about 2km
b)
100BaseX
(1)
512 bit times => about 200m
c)
1000BaseX
(1)
512 byte times => about 200m
(2)
Have to extend short frames to 512 byte times
(a)
Didn’t want to expand minimum frame size because of mixed
environments.
(b)
Some methods exist to send multiple frames so the bandwidth
isn’t wasted
d)
With xBaseT standards, the hub sends the incoming signal to
everyone but the sender.
(1)
The Sender knows a collision occurred if it receives anything
while transmitting.
e)
With Switched Ethernet, the collision domain doesn’t matter
much.
f)
With full duplex collisions do not exist
IV.
Less common LAN Technologies
A.
Token Bus – 802.4
1.
Since CDMA/CD leads to unknown amount of delay before a packet
is transmitted – Token passing architectures were developed.
2.
Token bus uses coaxial cable with broadband (RF)
modulation.
3.
1, 5, & 10 Mbps possible
4.
Token Bus allows for 4 priorities of traffic at each node.
5.
Frame format slightly different from 802.3
B.
Token bus - Token Passing
1.
Each node gets a Token
2.
Node has the right to transmit for some time period.
3.
When done, Node transmits the Token to the next node
4.
Periodically, a node solicits bids from new nodes wanting to
join the ring.
a)
If one responds – it is inserted into the ring and placed in
order after the solicitor
b)
If two respond – a collision occurs and a
5.
To leave the ring, a node tells it’s predecessor who it’s
successor is
6.
If transmission failure in token passing
a)
Retry of sending token
b)
Then, sending broadcast to find out who’s next and giving them
token
C.
Token ring – 802.5
1.
Cabling of each node having two connections – one to each of
it’s neighbors.
2.
Shielded twisted pair
3.
1, 4 or 16Mbps using differential Manchester
4.
Typically wired in a star shaped ring
a)
All spokes plug into MAU that has relays that allow isolation
of failed spokes.
b)
MAU –
Multi-Station Access Unit
5.
Each bit arriving at an interface is copied into a 1-bit buffer
and then copied out onto the ring again.
a)
Each interface creates a 1-bit delay
6.
Each node can prioritize traffic
D.
Token Ring – Token passing
1.
A token circulates the ring when it is idle.
2.
Station wanting to transmit grabs the token and transmits data
frame.
3.
When done with the frame, and the frame has come back around –
node transmits a token again.
4.
As frames go by – there is a priority field that a node may
modify if it has higher priority traffic
a)
Other nodes that have lower priority traffic will then pass on
the token until the requesting node gets it.
E.
FDDI - Fiber Distributed Data Interface
1.
100Mbps over Fiber optic lines – 2000m max
2.
Uses a token passing architecture similar to Token ring
3.
Typically is not set up with a star-shaped ring, but
physically as a ring
F.
Token vs. CSMA/CD
1.
Token passing architectures allow for prioritization of
traffic and guarantees that this traffic will get through in a fixed amount of
time.
a)
Even if heavily loaded – high priority traffic gets through
2.
CSMA/CD architecture allows for lower latencies when the LAN
is lightly loaded
a)
A node doesn’t have to wait for a token.
3.
CSMA/CD implementations tend to be simpler (and therefore
cheaper)
G.
ATM LANs
1.
They’re dead Jim
2.
ATM allows for prioritization of traffic, mixing very time
critical traffic with non-time critical traffic
3.
Protocol elegance has been overpowered by cheap silicon.
4.
Has nice idea of being able to use same protocols from WANs,
MANs, and LANs – voice, video and data.
5.
In MANs/WANs ATM is over SONET links
a)
OC-3, OC-12, OC-48 (155Mbps, 622Mbps, 2.4Gbps)
6.
In LANs, ATM is over twisted pair
a)
25Mbps, or 51Mbps
H.
Fibre Channel
1.
A high speed protocol over fiber optics that is tailored to
use for computer interfaces.
2.
Looks similar to SCSI from a software perspective.
3.
Very common in Storage Area Networks (SANs)
4.
1.06 Gbps
5.
Up to 10km over single mode fiber
I.
HIPPI – HIgh Performance Parallel Interface
1.
800 or 1600Mbps using 50 or 100 twisted pairs.
2.
Developed in late 80’s when LAN was 10Mbps ethernet
3.
Used for supercomputer interfaces
4.
Was relatively cheap to create as it used parts from other
technologies
V.
Upcoming LAN technologies
A.
VLANs
1.
VLAN - Virtual LAN
a)
This is not the same as VPN – Virtual Private Network
2.
VLANs are a configuration on some switches that group multiple
ports together as one LAN or broadcast domain.
3.
Different VLANs must be bridged using a router
a)
Often this router functionality is in the same box.
4.
VLANs can span switches, by adding a field to the Ethernet
frame that has a VLAN number in it.
a)
All switches must be configured with the same set of numbers
B.
Ethernet In First Mile
1.
A newer IEEE group
2.
Looking at ways to use Ethernet to connect to your home.
3.
Currently three areas being developed.
a)
Point to point over copper
b)
Point to point over fiber
c)
PON technology – Passive Optical Network.
(1)
Use of optical splitter/combiners that don’t require any
electronics.
d)
PON technology requires 2 “tricky” things
(1)
Ranging of nodes
(2)
Contention for the upstream bandwidth.
C.
802.11 - Wireless Ethernet
1.
Started out as 1 or 2Mbps using RF or infra-red links.
2.
RF uses frequencies around 2.4GHz
a)
This is the same range used by microwave ovens
b)
Water absorbs this energy very well making hard to use for
long distances.
3.
802.11b
a)
Up to 11Mbps, using 2.4Ghz spectrum
4.
802.11a
a)
Up to 54Mbps, using 5Ghz spectrum
5.
802.11g
a)
22 – 54 Mbps in the 2.4Ghz spectrum
b)
Just being standardized
c)
May run into regulatory problems due to excessive bandwidth
usage.
6.
802.11i
a)
Improved Security for wireless LANs
b)
WEP – Wired Equivalency Protocol
(1)
Current security protocol that was found to be very weak and
easily broken.
7.
802.11 – For last mile
a)
Since this is unlicensed spectrum, people have started to use
this with directional antennas for Internet Access.
b)
Unlicensed spectrum – RF bandwidth that you don’t need to buy
a license from the government to use
c)
To overcome the problems with water absorption, the link has
to be carefully set up
(1)
Line of site links
(2)
No trees in the way
d)
Typically will run at less than peak rates
8.
Additional wireless links
b)
http://www.wlana.com/
c)
http://www.midcoast.net/wirelessfaq.html
D.
RPR - Resilient Packet Rings – 802.17
1.
Another new technology – just starting out in the IEEE
2.
Idea is to provide good protection that Sonet rings enjoy,
using packet technology (most likely gig-Ethernet)
3.
Sonet Rings are circuit switch oriented, and reserve 50% of
the bandwidth on the ring for protection purposes.
a)
A Sonet protection switch occurs within 60ms
4.
Packet rings or meshs today rely on the routing protocols to
converge when a failure occurs
a)
This will often take minutes
5.
RPR goal is to protection switch as fast as Sonet
a)
60ms from start of an outage until service is restored.