- ARF - Original WaveLAN-II (Lucent) algorithm, circa 1996 - def: packet is new data, may have several transmissions. - state: current bit rate, # consecutive successful transmissions - start at highest - maintain okay_transmit_count - step down if no ack - step up if 10 consecutive transmissions with no retxmits occur (probe) - what would ARF do on the steep links? ++ - ..gradual links? -- (get stuck at high rate sometimes, don't step down until complete failure) - ..lossy links? -- (Once you step down, don't step up - get stuck at low rate sometimes) - Adaptive ARF: even on steep, sends probes. Adapt step-up parameter, double every time increase bitrate and subsequent packet fails. - Will AARF do better on gradual? (no) Lossy? (no) - ONOE - Atsushi Onoe (engineer at Sony/Japan) - Highest bitrate with < 50% loss - makes sense in 802.11b: 11/2=5.5; 5.5/2 ~= 2; 2/2=1, less sense in 802.11a (36,24,18,12,9,6) - credits to increase the bit rate - what would ONOE do on the steep links? + 1st sec. 11 2nd sec. 5.5 3rd sec. 5.5 ... 10th sec. 11 11th sec 5.5 12th sec 5.5 - What would ONOE do on a steep link that drops off after 1? (Would take 4 sec to stabilize. (-)) - what would ONOE do on the gradual links? + 1st sec. 11 2nd sec. 5.5 (line 3) 3rd sec. 5.5 NO probe up to 11 periodically every 10 sec. (credits don't accum) - what would ONOE do on the lossy links? (onepager) -- 1st sec 11 2nd sec 5.5 3rd sec 2 4th sec 1 - Measuring time to send a packet - Any problems with this? - What about backoff time before transmissions apart from the last one. - What about intervening transmissions from other nodes. - SampleRate in operation - notation: packets(transmissions)@rate - upper dest: fails at rate = 11, perfect at rate = 5.5 - 4(16)@11, switch to 5.5, 100(100)@5.5 - why won't it try rate = 2, 1? (lossless@2,1 > ave@5.5) - when will it next try rate = 11? (10 sec, after remove_stale_results() runs) - lower dest: one retry at rate = 11, 90% 0 retries, 10% 1 retry at rate = 5.5 - 9(18)@11, 1(1)@5.5, switch to 5.5, 9(10)@5.5, 1(2)@11, 9(10)@5.5, ... - why probe 5.5? (b/c 2976 < 3761) - why switch to 5.5? (b/c 3235 (avg. xmit time) < 3761) - why probe 11? (b/c 1873 < 3235) - ARF mostly chooses correct bit rate - x-axis: static-best throughput - y-axis: **hypothetical** -- take the bitrate that ARF chose most often, plot throughput of static-best for that bitrate - conclusion: ARF chose right bitrate most of the time! - Probing overhead of ARF: - (flip back to "Measring time to send a packet") Baseline rates ============== - 1 Mbit pkt time = 1500 bytes * 8 bits/byte / 1 Mbits/s = 12 ms - 2 Mbit pkt time = ... = 6 ms - 48 Mbit pkt time = ... = 250 us - 54 Mbit pkt time = ... = 125 us ARF === - assume: move up every 10, fail at next bitrate, with 4 retxmits - backoff time for 4 retxmits = 155+315+635+1275 us ~= 2.4 ms - 1 Mbit: packet time for 4 retxmits > 6 ms * 4 = 24 ms amortized --"-- = 2.6 ms / packet resulting time = 12 ms + 2.6 ms = 15 ms/packet (20% slowdown) - 48 Mbit: packet time for 4 retxmits @ 54 Mbits = 125 us = 0.5 ms backoff: 2.4 ms amortized --"-- = 290 us/packet resulting time = 540 us/packet (half rate) - 802.11b throughput distribution - sure enough 802.11b ARF gap is narrower - 802.11a throughput distribution - Onoe gap: Bicket attributes to lossy links - Explaining the Onoe gap - Nice example of an operating principle of systems research: ask why, then dig deeper in the data and present to your audience why. - Thruput vs bit rate chosen - each line = one link in the network - Left: Onoe chooses the best bitrate - Right: Onoe chooses lowest bitrate, can see what it should have chosen - The price of delivery confirmation - broadcast throughput: no acks - attributes it to 24 mbits/s acks on 36 mbits/s links