Transcript Looking deeper into ARQ “frames”

TELE3118 extras
For week 3
Looking deeper into ARQ “frames”
• “Frame” vs “ack”:
– Both are frames (groups of bits); “Frame” means carrying
payload data
– Both ends might want to transmit data; more complicated.
– May be distinguished by a type field in packet header (and/or
time of transmission – e.g. WiFi acks)
• “Frame” & “ACK” both contain check fields
– Frame: To detect bit errors
– ACK: s.t. unlikely noise can produce a valid ACK
• Sequence number
– Definitely needed in data
– Avoidable in ACK for stop-and-wait over link?
• Necessary for general use: sliding window or network path.
Broadcast & flooding
• Videos seem to flip these terms
• Concepts:
– All devices (in an area) should receive the info
– Info should be sent on all links of network
• All receive => send everywhere, but
send everywhere !=> all receive
– e.g. switching to destination with unknown location
• Elsewhere
– “Broadcast addresses” (MAC & IP) – all receive [4-6.7]
– 802.1D (Spanning Tree) “floods” – send on all outputs
– Flooding link state advertisements [5-5]
Wifi retransmission & acks
• Ack quickly (0.06ms) when receiver is not broadcast.
• Retransmit (in 0.4 to 0.5 ms) if no ACK
• Quirks
• Frames 10-12: destination is broadcast, but not receiver
• Non-binary sequence # & retry flag. Perhaps to allow retransmission
of only errored fragments.
• See more: http://uluru.ee.unsw.edu.au/~tim/zoo/index.html#wifi_retx
5
CSMA collisions
spatial layout of nodes
collisions can still
occur:
propagation delay means
two nodes may not hear
each other’s transmission
collision:
entire packet
transmission
time wasted
note:
role of distance & propagation
delay in determining collision
probability
Slide from Kurose and Ross
Copyright © Jul-15, Tim Moors
6
CSMA with collision detection (CD)
Longer detection time gives more confidence interference is due to
collision rather than noise => should back off exponentially.
Need to ensure that all stations are aware of the collision
=> transmit a “jam signal” (32 or 48 arbitrary bits) after detecting the
collision to ensure that other nodes also detect it and back off.
=> non-zero abort time. Copyright © Jul-15, Tim MoorsFigure from Kurose and Ross
Ethernet frame size limits
• Shared media Ethernet is rare today, but 1970s
design choices persist in today’s frame sizes
• Minimum: Want to detect collision while
transmitting. (= Want to conclude transmission
with last bit) => 64B minimum
• Maximum: 1500B to limit size of expensive RAM
on Network Interface Cards
– Extended by later versions (“jumbograms”?) but path
MTU discovery rarely uses it
8
Derivation of minimum frame length
Consider the first IEEE standard: 10base5 Ethernet:
Calculate geographical span:
Maximum segment length = 500m
Concatenate segments by using repeaters.
Maximum span: 5 segments (passing through 4 repeaters)
=> Maximum LAN span = 2500m
Translate into round-trip time:
Signal propagates at c2/3 = 2E8m/s
Round-trip time = 5km/2E8 = 25s
Fudge factor: Double to account for repeater delays: 50s
Translate into frame length:
50s = time to transmit 500b
conservatively round up to 512b
=> minimum frame length = 64B
Assuming preamble is part of physical layer,
DA+SA+Type+Null Data+CRC=18B
=> pad null data with 46B
Copyright © 20/03/14, Tim Moors
Efficiency of contentionbased MAC
N nodes, each transmitting with probability p
P(successful transmission) = Np(1-p)N-1
Differentiate wrt p => optimal p = 1/N
• Transmission probability should vary with N!
lim (1-1/N)N-1 = 1/e
N→∞
i.e. 37% efficiency! (Pure Aloha only 18%!)
63% of time wasted in collisions or all nodes
waiting
Copyright © Jul-15, Tim Moors
9
10
Ambiguity
• Sender didn’t receive ACK.
o Was data frame lost?
o Was ACK lost?
o A: Don’t care. Add sequence # to enable receiver to
determine.
• MAC: Why didn’t my transmission work?
o Due to collision? => back-off
o Due to bit error? => just retransmit immediately
o Ethernet: sustain collision through jamming to
differentiate from probably transient noise
o Wifi: can’t differentiate
• TCP: Why didn’t my packet get through?
o Due to congestion? => slow down
o Due to bit error => retransmit immediately
o Critical on wireless networks; ECN might help before
congestion causes loss
Copyright © Jul-15, Tim Moors
Official 802.11 definition
• P. 829 (of 2793!) of 802.11-2012
NAV = Network Allocation Vector – indicates period when channel is known to be busy
IFS = InterFrame Space.
Short IFS (SIFS) separates ack from data, giving time for propagation & radio turnaround (tx<DCF (Distributed Coordination Function = random access) IFS (DIFS) is longer than SIFS
Exposed terminals hear CTS and defer.
Chipsets
vary
in
what
options
they
provide
Windows 8 on another machine
Windows Vista on one machine
Link layer addresses
• 48bit (usually)
– MAC / IEEE / Link layer address – Yes!
• EUI-64, Bluetooth etc
– Physical/hardware [ipconfig] – No!
– Network address [driver] – No!