Transcript CSC 335 Data Communications and Networking I

CSC 336
Data Communications
and
Networking
Lecture 7b: Local Area Networking
(Token Ring – 802.5)
Dr. Cheer-Sun Yang
Spring 2001
offices
offices
Topologies
• Bus: A single communication line, typically
a twisted pair, coaxial cable, or optical fiber,
represents the primary medium.
• Ring: packets can only be passed from one
node to it’s neighbor.
• Star: A hub or a computer is used to connect
to all other computers.
• Tree: no loop exists (logical connection).
Token Passing
• Token Ring (802.5) : P. 183, Section 6.3
• Token Bus (802.4) : P. 186, Section 6.4
Token Passing
• The difficulty with many networks is that
no central control or authority makes
decisions on who sends when.
• Token passing is designed to deal with this
issue and hopefully the link utilization can
be increased.
Token Passing
• In order to send, a station must obtain an
admission pass, called a token.
• In a token ring, the token is passed from one
station to another.
• When a station does not need it, it simply passes it
on.
• Token ring network must pass the token orderly to
it’s neighbor.
• Token bus network can pass a token to any other
station directly.
Token Passing
• However, a token bus network cannot be
added as simply as with the CSMA/CD bus.
• All stations must know who and where its
neighbor is in a token bus.
6.3 Token Ring: IEEE 802.5
• Each repeater connects to two others via
unidirectional transmission links
• Single closed path
• Data transferred bit by bit from one repeater to the
next
• Repeater regenerates and retransmits each bit
• Repeater performs data insertion, data reception,
data removal
• Repeater acts as attachment point
• Packet removed by transmitter after one trip round
ring
Token Ring (802.5)
• MAC protocol
–
–
–
–
–
Small frame (token) circulates when idle
Station waits for token
Changes one bit in token to make it SOF for data frame
Append rest of data frame
Frame makes round trip and is absorbed by transmitting
station
– Station then inserts new token when transmission has
finished and leading edge of returning frame arrives
– Under light loads, some inefficiency
– Under heavy loads, round robin
Dedicated Token Ring
•
•
•
•
•
1997 update to IEEE 802.5
Central hub
Acts as switch
Full duplex point to point link
Concentrator acts as frame level repeater
with immediate access possible
• No token passing if using a switch to
connect all stations
802.5 Physical Layer
•
•
•
•
•
Data Rate
4
16
100
Medium
UTP,STP,Fiber
Signaling
Differential Manchester
Max Frame
4550
18200
18200
Access Control TP or DTR TP or DTR DTR
• Note: 1Gbit in development
Ring Repeater States
Listen State Functions
• Scan passing bit stream for patterns
– Address of attached station
– Token permission to transmit
• Copy incoming bit and send to attached
station, while forwarding each bit
• Modify bit as it passes
– e.g. to indicate a packet has been copied (ACK)
Transmit State Functions
• Station has data
• Repeater has permission
• May receive incoming bits
– If ring bit length shorter than packet
• Pass back to station for checking (ACK)
– May be more than one packet on ring
• Buffer for retransmission later
Bypass State
• Signals propagate past repeater with no
delay (other than propagation delay)
• Partial solution to reliability problem (the
failure of one station can cause the network
failure).
• Improved performance
Ring Media
•
•
•
•
Twisted pair
Baseband coaxial
Fiber optic
Not broadband coaxial
– Would have to receive and transmit on multiple
channels, asynchronously
Two observations
1. 1. Ring contention is more orderly than
2.
with an Ethernet. No wasted bandwidth.
Two observations
2. The failure of one station can cause
network failure. More discussion will be
provided in next slide.
Advantage of Token Ring
• The flexible control over access that it
provides.
• The access is fair.
• It is easy to provide priority and guaranteed
bandwidth services.
Disadvantage of Token Ring
• Token maintenance requires extra work.
• Loss of token prevents further utilization of
the ring.
• Duplication token can disrupt the operation.
• A monitor station is required. It becomes a
crucial point for a single point failure.
Potential Ring Problems
• Break in any link disables network
• Repeater failure disables network
• Installation of new repeater to attach new station
requires identification of two topologically
adjacent repeaters
• Method of removing circulating packets required
– With backup in case of errors
• Mostly solved with star-ring architecture (the wire
center approach).
Network Failure Problem
The failure of one station can cause network
failure: This problem can be solved by using a
wire center (Fig. 6.11). Instead of connecting
neighboring stations directly, they all
communicate through a wire center. The wire
center contains a bypass relay. If a station fails,
the bypass relay will allow a frame to bypass the
station.
This architecture is called a Star Ring
Architecture.
Star Ring Architecture
• Feed all inter-repeater links to single site
–
–
–
–
–
–
–
–
Concentrator
Provides central access to signal on every link
Easier to find faults
Can launch message into ring and see how far it gets
Faulty segment can be disconnected and repaired later
New repeater can be added easily
Bypass relay can be moved to concentrator
Can lead to long cable runs
• Can connect multiple rings using bridges
Timing Jitter
• Clocking included with signal
– e.g. differential Manchester encoding
– Clock recovered by repeaters
• To know when to sample signal and recover bits
• Use clocking for retransmission
– Clock recovery deviates from midbit transmission
randomly
• Noise
• Imperfections in circuitry
• Retransmission without distortion but with timing
error
• Cumulative effect is that bit length varies
• Limits number of repeaters on ring
Solving Timing Jitter Limitations
• Repeater uses phase locked loop
– Minimize deviation from one bit to the next
• Use buffer at one or more repeaters
– Hold a certain number of bits
– Expand and contract to keep bit length of ring
constant
• Significant increase in maximum ring size
A Closer Look on Token Passing
• 20 stations, each separated by 10 meters, for
a total ring length of 200 meters
• Transmission at 4Mbps, or one bit every
0.25 sec
• Propagation speed of 2*108 m/s
• How long does it take to travel around the
ring once? - 1 sec
• How many bits can a station send in 1 sec?
A Closer Look on Token Passing
• A: 4 bits.
• To get more bits on the ring, each station
delays one bit-time allowing it to examine
each bit before deciding whether to copy it
or repeat it. (one bit-time = 0.25 sec)
• How many bits can a station send then?
Token and Frame Formats
• Start Delimiter (SD), End Delimiter (ED): 1 octet
• Access Control (AC) : 1 octet, 3 priority bits, 1
token bit, 1 monitor bit, 3 reserved bits.
• Token bit determines the frame type, i.e. token
frame or data frame.
• Priority bit can be used to set the token’s priority.
• Monitor bit and reserved bits are used for ring
maintenance.
Token and Frame Formats
• Frame Control (FC): used to distinguish control
frame from data frame.
• Frame Status(FS): 1 octet (acxxacxx) a: address
recognized bit, c: frame copied bit, x: undefined
bit.
– a = 0, c = 0: dest not present or not power up
– a = 1, c = 0: dest present but frame is not accepted
– a = 1, c = 1: dest present and frame copied.
Token Ring
Operation
Priority Scheme
1. A station having a higher priority frame to
transmit than the current frame can reserve the
next token for its priority level as the frame
passes by.
2. When the next token is issued at a station A, it
will be at the reserved priority level. The station
reserving the token can use this token to transmit
data frame.
3. The station A is responsible to down-grade the
priority of the token later.
Priority Scheme
• A sends a frame to B at priority 0.
• When the frame passes by D, D makes a
reservation at priority 3.
• When the token is sent back to A, A changes the
priority to 3 and issues a new token.
• D can use this token to send a frame to any station.
• After the data is seized by the destination and the
token is passed back to A, A is responsible for
changing the priority back to 0. (Why A?)
Priority Scheme
• In this case, station A is called a stacking station.
• When it generates a new token with a higher
priority, it also keeps the old priority in a stack
locally.
• Thus, a stacking station is the only station in
which the old priority is kept.
Reserving and Claiming Tokens
A
token
B
C
D
Reserving and Claiming Tokens
A
B
Station A requests
the token and sends
its data to D
C
D
Reserving and Claiming Tokens
A
B
C
D
Station C can reserve the next open token
By entering its priority code in the AC field.
Reserving and Claiming Tokens
A
C
B
Station D copies the
frame and sends the
data back to the
ring.
D
Reserving and Claiming Tokens
A
B
Station A receives
the frame and
releases the token
C
D
Reserving and Claiming Tokens
A
B
C
Station C can send
its data now.
D
Priority
Scheme
Time Limits
• Token holding time: the time duration a
station is allowed to hold the token
• Token rotation time: the total time a token is
allowed to rotate around the ring.
• TRT >= N * THT
Ring Maintenance
Things can go wrong. For example:
1. A station sends a short frame over a long ring
and subsequently crashes. It is not able to drain
the token. This frame is called an orphan frame.
2. A station receives a frame or token crashes
before it can send it. Now there is no token
circulating.
3. Line noise damages a frame.
Ring Maintenance
Some problems can be handled by giving one of the
stations a few different responsibilities and
designating it a monitor station.
1. When a monitor station receives a frame, it sets
the monitor bit to 1. If the frame is received the
second time and the monitor bit is still set to 1,
the monitor station deletes the frame.
Ring Maintenance
2. The monitor station also detect a lost token using a
built-in timer which is determined based on the
length of the ring, number of stations, and
maximum frame size. Whenever the monitor
sends a frame or token, it starts the timer. If the
monitor does not receive another frame or token
before the timer expires, it assumes that the
token is lost. It then creates another one.
Ring Maintenance
Some problems cannot be solved even
with a monitor station. For example, what
if the malfunction station is the monitor
station? What if a break in the ring causes
a lack of tokens? Sending new ones does
nothing to correct the problem. These
problems are handled using control
frames.
Ring Maintenance
Some example control frames:
• Claim token frame – for submitting bids to elect
a monitor station.
• Active monitor present (AMP) frame – to notify
others that a monitor station has been produced.
• Standby monitor present (SMP) – frame.
• Beacon frame – to inform stations that a
problem has occurred and the token-passing
protocol has stopped.
Ring Efficiency
T1 = time to send a frame
T2 = time to send a token
T1
U
 100%
T1  T2
Other Ring Networks: FDDI
• 100Mbps
• LAN and MAN applications
• Token Ring
Encoding Schemes
• 4B/5B-NRZI
• MLT-3
FDDI MAC Frame Format
FDDI MAC Protocol
• As for 802.5 except:
• Station seizes token by aborting token
transmission
• Once token captured, one or more data
frames transmitted
• New token released as soon as transmission
finished (early token release in 802.5)
FDDI
Operation
FDDI Physical Layer
• Medium
Pair
• Data rate
• Signaling
• Max repeaters
• Between repeaters
Optical Fiber Twisted
100
4B/5B/NRZI
100
2km
100
MLT-3
100
100m
LAN Generations
• First
– CSMA/CD and token ring
– Terminal to host and client server
– Moderate data rates
• Second
– FDDI, FDDI II
– Backbone
– High performance workstations
• Third
– ATM
– Aggregate throughput and real time support for
multimedia applications
Third Generation LANs
• Support for multiple guaranteed classes of
service
– Live video may need 2Mbps
– File transfer can use background class
• Scalable throughput
– Both aggregate and per host
• Facilitate LAN/WAN internetworking
ATM LANs
•
•
•
•
•
Asynchronous Transfer Mode
Virtual paths and virtual channels
Preconfigured or switched
Gateway to ATM WAN
Backbone ATM switch
– Single ATM switch or local network of ATM switches
• Workgroup ATM
– End systems connected directly to ATM switch
• Mixed system
Example ATM LAN
ATM LAN HUB
Compatibility
• Interaction between end system on ATM
and end system on legacy LAN
• Interaction between stations on legacy
LANs of same type
• Interaction between stations on legacy
LANs of different types
Fiber Channel - Background
• I/O channel
–
–
–
–
–
Direct point to point or multipoint comms link
Hardware based
High Speed
Very short distance
User data moved from source buffer to destiation buffer
• Network connection
–
–
–
–
Interconnected access points
Software based protocol
Flow control, error detection &recovery
End systems connections
Fiber Channel
• Best of both technologies
• Channel oriented
– Data type qualifiers for routing frame payload
– Link level constructs associated with I/O ops
– Protocol interface specifications to support existing I/O
architectures
• e.g. SCSI
• Network oriented
– Full multiplexing between multiple destinations
– Peer to peer connectivity
– Internetworking to other connection technologies
Fiber Channel Elements
• End systems - Nodes
• Switched elements - the network or fabric
• Communication across point to point links
Fiber Channel Network
Fiber Channel Protocol
Architecture (1)
• FC-0 Physical Media
– Optical fiber for long distance
– coaxial cable for high speed short distance
– STP for lower speed short distance
• FC-1 Transmission Protocol
– 8B/10B signal encoding
• FC-2 Framing Protocol
–
–
–
–
Topologies
Framing formats
Flow and error control
Sequences and exchanges (logical grouping of frames)
Fiber Channel Protocol
Architecture (2)
• FC-3 Common Services
– Including multicasting
• FC-4 Mapping
– Mapping of channel and network services onto
fiber channel
• e.g. IEEE 802, ATM, IP, SCSI
Wireless LANs
• IEEE 802.11
• Basic service set (cell)
–
–
–
–
Set of stations using same MAC protocol
Competing to access shared medium
May be isolated
May connect to backbone via access point (bridge)
• Extended service set
– Two or more BSS connected by distributed system
– Appears as single logic LAN to LLC level
Types of station
• No transition
– Stationary or moves within direct communication range
of single BSS
• BSS transition
– Moves between BSS within single ESS
• ESS transition
– From a BSS in one ESS to a BSS in another ESS
– Disruption of service likely
Wireless LAN - Physical
• Infrared
– 1Mbps and 2Mbps
– Wavelength 850-950nm
• Direct sequence spread spectrum
– 2.4GHz ISM band
– Up to 7 channels
– Each 1Mbps or 2Mbps
• Frequency hopping spread spectrum
– 2.4GHz ISM band
– 1Mbps or 2Mbps
• Others under development
Media Access Control
• Distributed wireless foundation MAC
(DWFMAC)
• Distributed coordination function (DCF)
– CSMA
– No collision detection
• Point coordination function (PCF)
– Polling of central master
802.11 MAC Timing
Reading
• Chapter 6: 6.1-6.5