Advanced Computer Networks: Lecture 10 - 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 (376.84 KB, 32 trang )
CS716
Advanced Computer Networks
By Dr. Amir Qayyum
1
Lecture No. 10
Ethernet MAC – CSMA/CD
• Multiple access
– Nodes send and receive frames over a
shared link
• Carrier sense
– Nodes can distinguish between an idle
and busy link
• Collision detection
– A node listens as it transmits to detect
collision
3
CSMA/CDMACAlgorithm
ã Iflineisidle(nocarriersensed)
Sendimmediately
Upperboundmessagesizeof~1500
bytes
Mustwait9.6àsbetweenbackưtoư
backframes
4
CSMA/CD MAC Algorithm
• If line is busy (carrier sensed) …
– Wait until the line becomes idle and
then transmit immediately
– Called 1persistent (special case of p
persistent)
• If collision detected
– Stop sending data and jam signal
– Try again later
5
Collision Detection
mymachine
yourmachine
start
transmission
at time 0
start
transmission
at time T
almost there
at time T
collision !!!
How to ensure that mymachine knows about the collision?
6
Constraints on Collision Detection
• In our example, consider
– mymachine’s message reaches your
machine at T
– yourmachine’s message reaches my
machine at 2T
• Thus, mymachine must still be
transmitting at 2T
7
Constraints on Collision Detection
• Specifics of IEEE 802.3
– bounds 2T to 51.2 microseconds
– packet must be at least 64B long
• Jam after the collision, for 32 bits, then
stop transmitting frame (runt frame of
96 bits)
– ensures that all hosts notice collision
8
Ethernet Min. Frame Size
• RTT on a maximally configured Ethernet
of 2500m, with 4 repeaters is about 51.2 μs
– 2500m / 2 x 108 m/s = 12.5 us
– 2 x 12.5 = 25 us + repeater delays
• 51.2 μs on 10 Mbps corresponds to 512 bits
(64 bytes)
• Therefore, the minimum frame length for
Ethernet is 64 bytes (header +46 bytes data)9
Collision Detection
mymachine
yourmachine
start
transmission
at time 0
start
transmission
at time T
almost there
at time T
collision
mymachine notices collision before transmission ends at 2T
10
Retry After the Collision
• How long should a host wait to
retry after a collision ?
– Binary exponential backoff
• maximum backoff doubles with
each failure (exponential)
• after N failures, pick an Nbit
number
• 2N discrete possibilities from 0 to
maximum
11
Retry After the Collision
• Delay and try again algorithm
– 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)
12
Binary Exponential Backoff
choices after
1 collision
0
Ts
choices after
2 collisions
2Ts
3Ts
time
time of last
collision
• Why used fixed time slots ?
• How long slots should be ?
13
Binary Exponential Backoff
• Ts is 51.2 microseconds for IEEE 802.3
• Consider that k hosts collide
– each picks random number from 0 to 2( N1)
– if minimum value is unique
• all other hosts see busy line
• remember that Ethernet RTT < 51.2
microseconds
14
Binary Exponential Backoff
• Consider that k hosts collide
– if minimum value is not unique
• hosts in minimum value slot
collide again
• following slot idle
• consider next smallest backoff
value
15
Ethernet Frame Reception
• Sender handles all access control
• Receiver simply pulls frames from
network
• Ethernet controller/card
– sees all frames
– selectively passes frames to host
processor
16
Ethernet Frame Reception
• Acceptable frames
– addressed to host, or;
– to multicast address to which host
belongs or;
– to a broadcast address
– anything if in promiscuous mode
(packet sniffing and tcpdump
requirement)
17
Ethernet Collision Detection
• Bus topology Ethernets
– Transceiver handles
• Carrier detection
• Collision detection
• Jamming after a collision
– Transceiver sees voltage sum
• Outgoing signal + Incoming signal
– Looks for voltages impossible for local alone
• Attenuation can prevent detection
• Limits segment length
18
Ethernet Collision Detection
• Hub topology Ethernets
– Controller/card handles carrier detection
– Hub handles
• Collision detection
• Jamming after a collision
– Detect transmission activity on each line
– If more than 1 line (host) active
• Assert collision to all lines
• Continue until no lines active
– Attenuation is less critical
19
Experience With Ethernet
• Number of hosts limited to 200 in
practice, standard allows 1024
• Range much shorter than 2.5 km
limit in standard
• Roundtrip time is typically 5 or 10
μs, not 50μs
20
Experience With Ethernet
• Higherlevel flow control (i.e., TCP) limits
load
– 30% maximum load recommended
– Large packets recommended
• Star topologies easier to administer than Bus
– Failure isolation, node addition w/o complex
topology
• (Backwards) Compatibility more important
than elegance or raw performance (1 > 0)
21
Token Ring
22
Token Ring Overview
• Token Ring network “was” a candidate to replace
Ethernet; used in some MAN backbones
– 16Mbps IEEE 802.5 (based on earlier 4Mbps IBM ring)
– 100Mbps Fiber Distributed Data Interface (FDDI)
23
Token Ring Rationale
• Why emulate a shared medium with point
topoint links?
• Why a shared medium?
– convenient broadcast capabilities
– switches are costly
• Why emulation?
– simpler MAC algorithm: only have 2 wires
– fairer access arbitration
– fully digital (802.3 collision detection requires 24
analog)
IBM Token Ring – IEEE 802.5
• Data flows in a particular
direction
– a node receives frames from its
upstream neighbor
– a node forwards frames to its
downstream neighbor
25
