Advanced Computer Networks: Lecture 11 - Dr. Amir Qayyum
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (530.22 KB, 26 trang )
CS716
Advanced Computer Networks
By Dr. Amir Qayyum
1
1
Lecture No. 11
2
Review Lecture 10
•
•
•
•
•
•
•
•
CSMA/CD MAC algorithm
Constraints on collision detection
Min frame size – RTT 51.2us
Retries after collision
Binary exp backoff: Min value unique
Frame reception: acceptable frames
Bus and Hub topology: CD handle
Exp: nodes, dist, RTT, 30% load, largeframe
3
Review Lecture 10
•
•
•
•
•
•
•
•
Token Ring
MAN backbone
IBM, 802.5 token ring, FDDI
Rationale: emulate shared med p2p links
Directional data flow
Shared med: see all frames, distr MAC algo
Token – special bit pattern
Capture and release – round robin service
4
Physical Properties
• A node is connected into the ring using a relay
– Relay is open as long as the station is alive (a)
– Relay closes and bypasses the station if it is dead (b)
Host
From previous
host
Host
To next
host
From previous
host
Relay
(a)
To next
host
Relay
(b)
5
Physical Properties
• Several relays are packed into a
single box: multi Station Access
Unit (MSAU)
– Stations can be added/removed by
plugging/unplugging
– IBM token ring requires MSAU but
802.5 does not
6
MSAU
Host
MSAU
Host
Host
From previous
MSAU
To next
MSAU
Host
7
Physical Properties
• Data rate can be 4 Mbps or 16 Mbps
• Encoding of bits uses differential
Manchester
• Ring may have up to 250 (802.5) or
260 (IBM) nodes
• Physical medium is twisted pair (IBM
Token Ring)
8
Token Ring MAC
• Network adaptor contains receiver,
transmitter and some storage of bits between
them
• Token circulates if no station has anything to
send
– Ring must have enough capacity to store entire
token
– At least 24 stations with 1bit storage for 24bit
long token (if propagation delay is negligible)
9
– This situation is avoided by designating a
Token Ring MAC
• Any station that has a data to send can
seize token
• In 802.5, simply 1 bit in second byte
token is modified
• First two bytes of modified token
become preamble for the next frame
10
Token Ring MAC
• The station is then allowed to send
one or more frames
• Destination address may be a
multicast or a broadcast address
• Intended recipient copies the
frame into a buffer
11
Token Ring MAC
• Sender is responsible for removing
these frames
• Frame longer than the capacity of
ring is drained by the sender while
still transmitting its later part
12
Frame Format
• “Illegal” Manchester codes in the start and
end delimiters
• Frame priority and reservation bits in
access control byte
• Demux key in frame control byte
• A and C bits for reliable delivery, in status
byte
8
8
8
48
48
Start
delimiter
Access
control
Frame
control
Dest
addr
Src
addr
Variable
Body
32
8
8
CRC
End
delimiter
Frame
status
13
Token Ring MAC Issue
• A node captures the token and sends as
much data as it has …
– A node could keep the token for
arbitrarily long time, and other nodes are
not given the turn
– Favors nodes with large data over nodes
having a small message to send
• How much data a node is allowed to
transmit each time it capture the token ?
14
Timed Token Algorithm
• Token Holding Time (THT)
– Upper limit on how long a station can
hold the token
– A node checks before putting each frame
on ring that its transmit time would not
cause THT to exceed
– Long THT achieves better utilization
with few senders
– Short THT helps when multiple nodes
15
have data to send
Timed Token Algorithm
• Token Rotation Time (TRT)
– How long it takes the token to
traverse the ring.
–TRT <= ActiveNodes x THT
+ RingLatency
16
Reliable Delivery
• The A and C bit in the packet
trailer for reliability
• Both bits are initially set to 0
• Destination sets A bit if it sees
the frame and sets C bit if it
copies the frame into its adaptor
17
Reliable Delivery
• If sender receives bit A=0, it
assumes destination is absent (not
functioning)
• If A bit is set but not bit C, it
means destination is unable to
accept the frame
– Sender retransmits this frame later
18
Token Ring Packet Priorities
• Token contains 3bit priority
field
• Token priority changes over
time by using reservation bits
in the frame header
19
Token Ring Packet Priorities
• A station willing to send priority n
packet can set reservation bits to n, if
this makes it lower in value
– it captures the token when the current
sender releases it with priority set to n
• Strict priority scheme: no lower
priority packets get sent when higher
priority packets are waiting 20
Token Maintenance
• Token rings have a designated monitor
node
• Any station can become the monitor
according to a well defined procedure
• Monitor is elected when the ring is
first connected, or when the current
monitor fails
21
Token Maintenance
• Monitor periodically announces its
presence
• Claim token sent by a station seeing
no monitor
– if the sender receives back the claim
token, it becomes monitor
– if another station is also contending for
monitor, some rule defines the monitor
22
Monitor’s Role
• May add additional delay into the
ring
• Assures that a valid token is
present in the ring because token
may be lost:
– No token when initializing the ring
– Bit error corrupts token pattern
– Node holding the token crashes
23
Monitor’s Role
• Maintains a timer to detect the missing
token
– Timer = NumStations x THT +
RingLatency
– When times expires, it creates a new
token
• Checks for corrupted frames
– checksum error, invalid format, may
circulate forever
24
Monitor’s Role
• Checks for orphaned frames
– sending station died before removing the
frame
– “Monitor” bit is used to detect orphaned
frames
– Initially 0, and set to 1 when a frame
passes the monitor
– If the monitor sees a frame with this bit set,
25
it drains it off
