Estimating Bandwidth of Mobile UsersSept 2003Rohit KapoorCSD, UCLAEstimating Bandwidth of Mobile Users•Mobile, Wireless User–Different possible wireless interfaces•Bluetooth, 802.11, 1xRTT, GPRS etc•Different bandwidths•Last hop bandwidth can change with handoff•Determine bandwidth of mobile user–Useful to application servers: Video, TCP–Useful to ISPsCapacity Estimation•Fundamental Problem: Estimate bottleneck capacity in an Internet path–Physical capacity different from available bandwidth•Estimation should work end-to-end–Assume no help from routersPacket Dispersion•Previous work mostly based on packet dispersion •Packet Dispersion (pairs or trains)Previous Work•Packet Pairs–Select highest mode of capacity distribution derived from PP samples (Crovella)•Assumes that distribution will give capacity in correspondence to highest mode–Lai’s potential bandwidth filtering –Both of these techniques assume unimodaldistribution•Paxson showed distribution can be multimodal•Packet tailgating•Pathchar–Calculates capacity for every linkPrevious Work•Dovrolis’ Work–Explained under/over estimation of capacity–Methodology•First send packet pairs•If multimodal, send packet trains•Still no satisfactory solution!!!–Most techniques too complicated, time/bw-consuming, inaccurate and prone to choice of parameters–Never tested on wirelessProblems due to Cross-Traffic•Cross-traffic (CT) serviced between PP packets–Smaller CT packet size => More likely•This leads to under-estimation of CapacityNarrow LinkCross TrafficTT’ > TProblems (cont)•Compression of the packet pair–Larger CT packet size => More likely•Over-estimation of CapacityPost Narrow (20Mbps)Narrow Link (10Mbps)Packet QueuedPacket Not QueuedTTT’ < TFundamental Queuing Observation•Observation–When PP dispersion over-estimates capacity•First packet of PP must queue after a bottleneck link•First packet of PP must experience Cross Traffic (CT) induced queuing delay–When PP dispersion under-estimates capacity•Packets from cross-traffic are serviced between the two PP packets•Second packet of PP must experience CT induced queuing delayFundamental Observation•Observation (also proved)–When PP dispersion over-estimates capacity•First packet of PP must queue after a bottleneck link–When PP dispersion under-estimates capacity•Packets of cross-traffic are serviced between the two PP packets•Second packet of PP must experience CT induced queuing delay–Both expansion and compression of dispersion involve queuingObservation (cont)•Expansion or Compression–Sum of delays of PP packets > Minimum sum of delays•When Minimum sum of delays?–Both packets do not suffer CT induced queuing•If we can get one sample with no CT induced queuing–Dispersion is not distorted, gives “right” capacity–Sample can easily be identified since the sum of delays is the minimumOur Methodology: CapProbe• PP really has two pieces of information–Dispersion of packets–Delay of packets• Combines both pieces of information–Calculate delay sum for each packet pair sample–Dispersion at minimum delay sum reflects capacityCapacity 00.00050.0010.00150.0020.00250.0030.00350.0040.00450.0050 1.6 3.2 4.8 6.4 8Bandwidth Estimates (Mbps)Minimum Delay Sum (sec)Requirements•Sufficient but not necessary requirement–At least one PP sample where both packets experience no CT induced queuing delay.•How realistic is this requirement?–Internet is reactive (mostly TCP): high chance of some probe packets not being queued–To validate, we performed extensive experiments•Simulations and measurements•Only cases where such samples are not obtained is when cross-traffic is UDP and very intensive (>75%)CapProbe•Strength of CapProbe–Only one sample not affected by queuing is needed•Simplicity of CapProbe–Only 2 values (minimum delay sum and dispersion) need storage–One simple comparison operation per sample–Even simplest of earlier schemes (highest mode) requires much more storage and processingExperiments• Simulations, Internet, Internet2 (Abilene), Wireless• Cross-traffic options: TCP (responsive), CBR (non-responsive), LRD (Pareto)• Wireless technologies tested: Bluetooth, IEEE 802.11, 1xRTT• Persistent, non-persistent cross-traffic(a)(b)Simulations•6-hop path: capacities {10, 7.5, 5.5, 4, 6, 8} Mbps•PP pkt size = 200 bytes, CT pkt size = 1000 bytes•Persistent TCP Cross-Traffic00.10.20.30.40.50.60.70.80.910 1.6 3.2 4.8 6.4 8Bandwidth Estimate (Mbps)Frequency1Mbps2Mbps4MbpsOver-Estimation Cross Traffic RateBandwidth Estimate Frequency00.0010.0020.0030.0040.0050.0060.0070.0080.0090.010 1.6 3.2 4.8 6.4 8Bandwidth Estimate (Mbps)Min Delay Sums (sec)1Mbps2Mbps4MbpsCross Traffic RateMinimum Delay SumsSimulations•PP pkt size = 500 bytes, CT pkt size = 500 bytes•Non-Persistent TCP Cross-Traffic00.00210.00420.00630 1.6 3.2 4.8 6.4 8Bandwidth Estimate (Mbps)Min Delay Sum (sec)1Mbps3MbpsMinimum Delay Sums00.10.20.30.40.50.60.70.80.910 1.6 3.2 4.8 6.4 8Bandwidth Estimate (Mbps)Frequency1Mbps3MbpsUnder-Estimation Bandwidth Estimate FrequencySimulations•Non-Persistent UDP CBR Cross-Traffic•Only case where CapProbe does not work–UDP (non-responsive), extremely intensive–No correct samples are obtained00.0020.0040.0060.0080.010.0120.0140 1.6 3.2 4.8 6.4 8Bandwidth Estimate (Mbps)Min Delay Sums (sec)1Mbps2Mbps3Mbps4Mbps00.10.20.30.40.50.60.70.80.910 1.6 3.2 4.8 6.4 8Bandwidth Estimate (Mbps)Frequency1Mbps2Mbps3Mbps4MbpsMinimum Delay SumsBandwidth Estimate FrequencyInternet Measurements• Each experiment–500 PP at 0.5s intervals• 100 experiments for each {Internet path, nature of CT, narrow link capacity}• OS also induces inaccuracyLaptop3 Dummy NetLaptop1 PING Source/DestinationInternetLaptop2Cross-Traffic DummyNet Capacity % Measurements Within 5% of Capacity % Measurements Within 10% of Capacity % Measurements Within 20% of Capacity 500 kbps Yahoo 100 100 100 1 mbps Yahoo 95 95 100 5 mbps Yahoo 100 100 100 10 mbps Yahoo 60 100 100 20 mbps Yahoo 75 100 100 500 kbps Google 100 100 100 1 mbps Google 100 100 100 5 mbps Google 95 100 100 10 mbps Google 80 95 100 20 mbps Google 65 100 100Wireless Measurements• Experiments for 802.11b, Bluetooth, 1xRTT• Clean, noisy channels– Bad channel è retransmissionèlarger dispersions èlower estimated capacity802.11bAccess PointLaptop1 PING
View Full Document
Unlocking...