115-744: Computer NetworkingL-10 Wireless in the Real WorldWireless in the Real World• Real world deployment patterns• Mesh networks and deploymentspy• Assigned reading• Self-Management in Chaotic Wireless Deployments• Architecture and Evaluation of an Unplanned 802 11b Mesh Network802.11b Mesh Network2Wireless Challenges• Force us to rethink many assumptions• Need to share airwaves rather than wireD’tk htht i ld•Don’t know what hosts are involved• Host may not be using same link technology• Mobility• Other characteristics of wireless• Noisy Æ lots of losses•Slow3Slow• Interaction of multiple transmitters at receiver• Collisions, capture, interference• Multipath interferenceOverview• 802.11• Deployment patterns• Reaction to interference• Interference mitigation• Mesh networks4• Architecture• Measurements2Characterizing Current Deployments• Datasets• Place Lab: 28,000 APs,• MAC, ESSID, GPS• Selected US cities• www.placelab.org• Wifimaps: 300,000 APs• MAC, ESSID, Channel, GPS (derived)• wifimaps.com• Pittsburgh Wardrive: 667 APs• MAC, ESSID, Channel, Supported Rates, GPS5AP Stats, Degrees: Placelab(Placelab: 28000 APs, MAC, ESSID, GPS)Portland 8683 54San Diego 7934 76#APs Max.degree50 m6San Francisco3037 85Boston 2551 39121Degree Distribution: Place Lab7Unmanaged DevicesWifiMaps.com(300,000 APs, MAC, ESSID, Channel)• Most users don’t change default channel6 5111 21Channel %age8• Channel selection must be automated1 1410 43Growing Interference in Unlicensed Bands • Anecdotal evidence of problems, but how severe?• Characterize how 802.11 operates under interference in practiceOther 802.119What do we expect?• Throughput to decrease linearly with interference)ea y t te e e ce• There to be lots of options for 802.11 devices to tolerate interference• Bit-rate adaptation• Power control•FEChroughput (linear)• Packet size variation• Spread-spectrum processing• Transmission and reception diversity10Interferer power(log-scale)ThKey Questions• How damaging can a low-power and/or narrow-band interferer be?• How can today’s hardware tolerate interference well?• What 802.11 options work well, and why?11What we see• Effects of interference more severe in practicer)practice• Caused by hardware limitations of commodity cards, hi h th d ’throughput (linearwhich theory doesn’t model12Interferer power(log-scale)T4Experimental Setup802.11AccessPointUDP flow802.11 Interferer13Client802.11 Receiver PathMACPHYTimingAGCBarker CltDescramblerADCTo RF AmplifiersRF SignalData(includesDemodulatorPHYMACAnalog signalAmplifier controlRecoveryPreamble Detector/Header CRC-16 CheckerCorrelator6-bit samplesReceiver(includes beacons)signalSYNCSFD CRCPayload• Extend SINR model to capture these vulnerabilities• Interested in worst-case natural or adversarial interference• Have developed range of “attacks” that trigger these vulnerabilities14PHY headerTiming Recovery Interference• Interferer sends continuous SYNC pattern• Interferes with packet acquisition (PHY reception errors)reception errors)10100100010000ghput (kbps)60080010001200atencyoseconds)Throughput Weak interfererModerate interfererLog-scale150.1110−∞ -20 -12 -2 0 8 12 15 20Interferer Power (dBm)Throug0200400L(micrLatencyInterference Management• Interference will get worse• Density/device diversity is increasing• Unlicensed spectrum is not keeping up• Spectrum management• “Channel hopping” 802.11 effective at mitigating some performance problems [Sigcomm07]• Coordinated spectrum use – based on RF sensor network• Transmission power controlp• Enable spatial reuse of spectrum by controlling transmit power• Must also adapt carrier sense behavior to take advantage165Impact of frequency separation• Even small frequency separation (i.e., adjacent 802.11 channel) helps100100010000hput (kbps)10MHz separation15MHz separationSame channel(poor performance)5MHz separation(good performance)170.1110−∞ -20 -12 0 8 12 15 20Interferer Power (dBm)ThrougTransmission Power Control• Choose transmit power levels to maximizephysical spatial reuse• Tune MAC to ensure nodes transmit simultaneously when possible• Spatial reuse = network capacity / link capacity18AP1AP2Client1Client2AP1AP2Client1Client2Spatial Reuse = 1 Spatial Reuse = 2Concurrent transmissionsincrease spatial reuseTransmission Power Control in Practice• For simple scenario Æ easy to compute optimal transmit powerAP1compute optimal transmit power• May or may not enable simultaneous transmit• Protocol builds on iterative pair-wise optimization• Adjusting transmit power ÆAP1AP2Client2d11d22d12d21requires adjusting carrier sense thresholds• Echos, Alpha or eliminate carrier sense• Altrusitic Echos – eliminates starvation in Echos19Client1Details of Power Control• Hard to do per-packet with many NICs• Some even might have to re-init (many ms)•May have to balance power with rate•May have to balance power with rate• Reasonable goal: lowest power for max rate• But finding ths empirically is hard! Many {power, rate} combinations, and not always easy to predict how each will perform• Alternate goal: lowest power for max needed rate•But this interacts with other people because you use more•But this interacts with other people because you use more channel time to send the same data. Uh-oh.• Nice example of the difficulty of local vs. global optimization206Rate Adaptation• General idea:• Observe channel conditions like SNR (signal-to-noise ratio), bit errors, packet errors• Pick a transmission rate that will get best goodput• There are channel conditions when reducing the bitrate can greatly increase throughput – e.g., if a ½ decrease in bitrate gets you from 90% loss to 10%decrease in bitrate gets you from 90% loss to 10% loss.21Simple rate adaptation scheme• Watch packet error rate over window (K packets or T seconds)• If loss rate > threshhigh(or SNR <, etc)• Reduce Tx rate• If loss rate < threshlow• Increase Tx rate•Most devices support a discrete set of ratesMost devices support a discrete set of rates• 802.11 – 1, 2, 5.5, 11, etc.22Challenges in rate adaptation• Channel conditions change over time• Loss rates must be measured over a window• SNR estimates from the hardware are coarse, and don’t always predict loss rate• May be some overhead (time, transient interruptions, etc.) to
View Full Document