Transcript Bandwidth sets the maximum Baud rate

Layer 2
Datalink / Media Access
• This layer is responsible for allowing the devices
to access the media.
• Creates connections between devices
• If more than one device on the physical link:
–
–
–
–
–
Requires some kind of address
MAC Address, Ethernet
DLCI, Frame Relay
VPI/VCI, ATM
LABEL, MPLS
Simplest case
• Point to Point link
• HDLC – High level data link control
• The physical might be T1, FiberChannel, SONET
…
• Note the layer 2 data technologies CO-EXIST on
Layer 1 technologies:
– Ethernet often runs over a T1 line.
– PPP over RS232
– Etc.
Bit oriented (Peterson)
• HDLC, High-Level Data Link Control
– Standardized version of SDLC (IBM)
• Also uses the 0x7E control sequence to delineate
beginning and end of frames
– If 0x7E appears in the body of the message, special provisions
must be made via an “escape sequence”
Byte Oriented
• PPP, Point to Point Protocol
–
–
–
–
Follow on from SLIP
Simple method of placing IP in Layer2
Byte oriented
Protocol field determines what’s in the payload.
• Byte oriented means the frame frame contains an
integer number of bytes.
• LCP/NCP are sister protocols used for setting up
PPP session
– Negotiate Frame size, IP address, etc.
PPP Frame Format (TCP/IP, Stevens)
Typical layer 2 requirements
• CRC Cylical Redundancy Check
– Checks to make sure there are no errors in the frame.
• May include FEC Forward Error Correction
– Can detect and correct effort
• Flag telling which Layer 3 protocol should process
the frame
– Ethernet can carry several protocols simultaneously (IP,
IPX, NetBEUI, etc)
• Sequence numbers
– So frames can be ordered and missing ones resent
CRC vs. FEC
• Simple parity case is similar to (CRC)
– 00,01,10,11 possible patterns to be sent
– 000, 011,101,110 actually sent (bit 3 is parity)
– If receiver sees 111, it knows there’s a problem
• Error correction codes are more complicated
– When problem is seen, error can be used to determine
proper sequence that was sent
– Will be discussed later this course
From:
Peterson and
Davie
If ACK not
received in
time, frame is
retransmitted.
Flow control
• Need to make sure packets are getting to where
they are being sent.
• General concepts:
– If message gets there, send another message
– If they are getting lost, try again
– If trying again and again doesn’t solve the problem
• Give up and notify upper protocol layer
• Continuing to dump duplicate messages degrades
the network performance dramatically.
– Most protocols “time-out”
Stop and wait flow control
U=
tframe
Data
=
tprop
Data
Ack
tframe
2tprop+tframe
1
2 + 1
U

Ack
=
tprop
tframe
Distance/Speed of Signal
=
Frame size /Bit rate
Distance  Bit rate
=
Frame size Speed of Signal
Light in vacuum
= 300 m/s
Light in fiber
= 200 m/s
Electricity
= 250 m/s
Window based flow control
U=
tframe
Data
Ntframe
2tprop+tframe
N
tprop
=
Ack
2+1
1 if N>2+1
Sharing a Medium
Pure ALOHA
In pure ALOHA, frames are transmitted at
completely arbitrary times.
Pure ALOHA (2)
Vulnerable period for the shaded frame.
Pure ALOHA (3)
Throughput versus offered traffic for ALOHA
systems.
Best case 18% utilization pure Aloha, 36.8% for
slotted Aloha.
Slotted requires a clock source, only transmit at
frame boundaries
Protocols that listen before
transmitting
• Station listens to network, if busy
– Wait till net available then transmit: if collision then,
• Back off for some time then send again if channel available.
• If the stations always retransmits when the network
becomes available
– CSMA 1 persistant
• If the station gradually becomes less aggressive about
siezing the network when it’s busy:
– CSMA nonpersistent
• If the station attempts to retransmit with some probability p
less than 1
– CSMA p-persistent
Persistent and Nonpersistent CSMA
Comparison of the channel utilization versus load for
various random access protocols.
CSMA with Collision Detection
CSMA/CD can be in one of three states:
contention, transmission, or idle.
Collision-Free Protocols
• The basic bit-map protocol.
– Station asserts the bit in it’s slot if it wants to
transmit.
– Stations then transmit in turn.
– Reservation based, no chance of collision
Collision-Free Protocols (2)
• Binary countdown
protocol
• More efficient than
bit-map protocol
– Bits in the stations
addresses determine
when they access the
channel
– Reduces overhead
compared to bit-map
Limited-Contention Protocols
Acquisition probability for a symmetric contention
channel.
Ethernet overview
Channel Capacity (C)
• Bandwidth, Bit Rate, SNR, and BER related
• Channel Capacity defines relationship
C = Maximum reliable bit rate
C = W*Log2(1 + SNR) bps
Bandwidth sets the maximum Baud rate
Channel Capacity (C)
• Bandwidth, Bit Rate, SNR, and BER related
• Channel Capacity defines relationship
C = Maximum reliable bit rate
C = W*Log2(1 + SNR) bps
Bandwidth sets the maximum Baud rate
SNR sets the maximum number of
different symbols (the "M" in M-ary)
Normalized Propagation Delay
• NPD = End-to-End Propagation Delay
Average time to inject a Packet
• NPD > 1 implies “High Speed Network”
1 or more packets can simultaneously be in transit
• NPD < 1 implies “Slow Speed Network”
Packet front end hits far side before back end transmitted
Transmitter
High Speed
Low Speed
Receiver
Types of Traffic...
• Computer Data
Bursty
Highly sensitive to errors
Not as time sensitive as voice or video
• Interactive Voice/Video
Fixed Rate (if not compressed)
*Not sensitive to errors
Fixed or Variable Rate (if compressed)
*Sensitive to errors
Time Sensitive
IEEE 802.3 Ethernet
•
•
•
•
•
Based on late 1970’s technology
Covers OSI Layers 1 & 2
10 Mbps Line Speed
Logical Bus
Designed to move Computer Data
Serial Bit Stream: NRZ Coding
Logic
One
Logic
Zero
0
0
Coax Cable
T
volts
+1
Called ‘Non Return to Zero’
because voltage never dwells
on zero volts.
0
time
-1
T
Ethernet Uses Manchester Coding
Logic
One
Logic
Zero
0
0
volts
+1
All symbols
have a transition
in the middle.
0
time
-1
T
Ethernet Uses Manchester Coding
volts
+1
0
time
-1
T
High Pass Filters Emphasize Change
High Pass Filter Output
+1
0
time
-1
Rectify (Absolute Value)
+1
0
T
time
-1
Result always has pulses T seconds apart.
Useful for receiver synchronization.
What is CSMA/CD?
• Polite Conversation
– One node active at a time
– No deliberate interruptions
– Collisions sometimes occur after a
break
802.3 Back-Off Algorithm
• choose random number
1st Collision
0, 1
2nd Collision
0, 1, 2, 3
3rd Collision
0, 1, ..., 6, 7
4th Collision
0, 1, ..., 14, 15
10th Collision
0, 1, ..., 1022, 1023
15th Collision 0, 1, ..., 1022, 1023
16th Collision Punt
• Wait (Random Number*.0000512) seconds
802.3 Flow Chart
No
Packet to
Send?
Drop Packet.
Notify Higher Layer
Yes
Set Collision Counter
=0
Traffic on
Network?
No
Back-Off
Yes
16th Collision?
Yes
Bump Collision
Counter by +1
No
Send Packet
Yes
Collision?
No
Jam
Major Drawbacks of
CSMA/CD...
• Worst case waiting time equals infinity
(No guaranteed Bandwidth)
• No Priorities
These make Ethernet the worst LAN
protocol to use for Multimedia Traffic
802.3 Packet Format
Bytes: 7
Pre
1
6
6
SFD
Destination
Address
Source
Address
46-1500
Data + Padding
2
Len
4
CRC
Preamble
Logic
One
0
Logic
Zero
0
volts
+1
Series of pulses
generated at
receiver T seconds
apart & in middle
of each symbol.
0
time
-1
T
Transmitting a File
• Broken into smaller packets
• Initial packets from Layer 5
Open Logical Connection
• Packets from Layer 7
“Data” Contains Layer 7 traffic
“Data” Contains Layer 3-5 info
• Packets from Layer 4
Acknowledgements
• Final packets from Layer 5
Close Logical Connection
10Base5 & 10Base2 (Obsolete)
Coax Cable
PC
PC
Printer
Logical & Physical Bus
All nodes monitor traffic
3 Nodes share 10 Mbps
10BaseT & Shared Hub
PC
Twisted Pair
PC
Hub
PC
PC
Logical Bus & Physical Star
Shared hub (OSI Level 1) copies input bits to all outputs.
All nodes monitor traffic. 4 nodes share 10 Mbps.
10BaseT & Switched Hub
PC
PC
Switched
Hub
PC
PC
Logical Bus & Physical Star
Switched Hub (OSI Level 1 & 2) copies packet to proper output.
Only the destination monitors traffic.
10BaseT & Switched Hub
PC
PC
Switched
Hub
PC
PC
Logical Bus & Physical Star
This example system can move up to 20 Mbps
10BaseT & Switched Hub
PC
PC
Switched
Hub
PC
PC
Logical Bus & Physical Star
Each node shares 10 Mbps
with the Switched Hub.
10BaseT & Switched Hub
PC
reception is
screwed up
PC
PC
Switched
Hub
PC
Using Half Duplex 10BaseT,
a collision occurs if PC & Switched Hub
simultaneously transmit.
IEEE 802.3u
100 Mbps Fast Ethernet
• Preserves CSMA/CD
• Preserves Packet Format
• Maximum End-to-End Lengths (a.k.a.
Collision Domain) reduced to keep
Normalized Propagation Delay low
• Sales are pretty good
Full Duplex System
PC
PC
Switched
Hub
PC
PC
Most 1 Gbps (& many 100 Mbps) systems are Full Duplex.
NIC’s are designed to simultaneously transmit & receive.
Line no longer shared. No Collisions. No need for CSMA/CD.
1995
• Two 100 Mbps ‘Ethernets’ introduced
• Version A
– CSMA/CD MAC, Ethernet Frames
• Version B
– Demand Priority MAC, Ethernet Frames
• IEEE said Version A is Ethernet
– IEEE 802.3u Fast Ethernet
• IEEE said Version B is not Ethernet
– IEEE 802.12 100VG-AnyLAN
• 802.12 is currently Dead
IEEE 802.3z
1 Gbps Ethernet
• Uses an extended version of CSMA/CD, including
‘Frame Bursting’
• Best performance uses full duplex connections &
switched hubs
– CSMA/CD included so it can be called Ethernet
•
•
•
•
Collision Domain same as Fast Ethernet
Preserves Packet Format
Good Sales
More on GigE later
IEEE 802.1p Priority Tags
• 8 priorities
• MAC protocols remain unchanged
• Used by 802.1p enabled switches
– Allows interactive voice or video to receive
preferential treatment on an Ethernet LAN
IEEE 802.5 Token Ring
•
•
•
•
•
Based on early 1980’s technology
Covers OSI Layers 1 & 2
4 or 16 Mbps Line Speed
Logical Ring
A ‘Token’ is passed around the ring
Node must have the Token to transmit
• Guaranteed Bandwidth
• Has Priorities
802.5 Token Format
Bytes: 1
1
1
SD
AC
ED
Starting Delimiter: Token/Frame starts here
Access Control: Indicates whether Token or Frame, Priority
Ending Delimiter: End of Token/Frame
802.5 Packet Format
Bytes: 1
1
SD AC
1
6
6
FC
Destination
Address
Source
Address
Modified Token
a.k.a
Starting Frame
Delimiter
>0
Data
4
CRC
1
1
ED FS
Frame Control: Ring Status
Frame Status: Receiver indicates whether received OK
IEEE 802.5 Token Ring
• Technically Superior to Ethernet
• 2nd most widely used LAN protocol
• Similar evolution to Ethernet
– Logical & Physical Ring
– Logical Ring, Shared Physical Star
– Logical Ring, Switched Physical Star
• 100 Mbps products available since ’98
• Sales sharply declining. Heading for LAN
graveyard.
Layer 2 Switching
• Why??
• Bridges
• Spanning Tree Algorithm