Transcript PPT
Wireless Capacity A lot of hype Self-organizing sensor networks reporting on everything everywhere Bluetooth personal networks connecting devices City wide 802.11 networks run by individuals and companies No more Cat5 in homes/businesses Capacity As systems researchers, the most glaring question is “Does this scale?” What do we mean by scaling? What is the aggregate network capacity? What is the per-node capacity for nodeoriginated data Observed capacity Das et al. simulation of 100 nodes 2Mbps base throughput 7 simultaneous transmissions Per-node bandwidth few kbps Others see similar capacity Physical limit Competition for physical bandwidth Signal power degrades with distance as 1/ra for some a>2 Pi | X i X j |a Pk N a | X X | ktransmitting k j As an order of magnitude, in ns transmission range ~250 meters, interference ~550 meters Network capacity Upper bound total capacity,arbitrary destination (Wn ) Why? Intuitively, assuming constant density: total area/capacity ~n, diameter/average path length ~n Global scheduling can achieve: 1 ( ) n log( n) What is the limit? As density increases, the number of nodes a packet interferes with increases Constant power, nodes per unit area larger Lower power/more hops, total transmissions increase 802.11 Chain propagation (simulation) Achieve 1/7 of maximum 1.7Mbps Expected ¼ of maximum 1.7Mbps MAC inefficiency? 802.11 works until offered load exceeds capacity Waste bandwidth at first node Waste time backed off Simulation vs. Reality Solutions? Smaller networks? Add extra repeater nodes Requires exorbitant number of nodes Factor of k repeaters, k extra per-node capacity Local communication patterns? Suggested in papers Only helpful if lower overall use Widespread base stations Local data processing Be sneaky Traffic pattern Power law traffic pattern p( x) = xa A t a dt Per-node capacity a<2 Approaches constant a=2 O(1/log(n)): GLS uses this a>1 O(1/n) Be sneaky If we achieve three properties, we should be able to get scalability All direct communication is local Message paths are short (preferably O(1)) Squander no opportunities to send Can we still achieve full connectivity? Maybe: Mobility Mobility Nodes move randomly Persistent communication patterns Ergodic (uniform space filling) motion No proof that this is NECESSARY Random source/destination patterns Unlimited data Buffering Nodes can buffer data Mobility To achieve scalability, we want three properties All direct communication is local Send messages only to nearest neighbor Distant communication depends on chance movement Message paths are short (preferably O(1)) Squander no opportunities Mobility To achieve scalability, we want three properties All direct communication is local Message paths are short (preferably O(1)) Never forward along paths longer than 2 hops Squander no opportunities Mobility To achieve scalability, we want three properties All direct communication is local Message paths are short (preferably O(1)) Squander no opportunities Send data through everyone Whenever you are near any node, give it a (new) packet for the destination. On average should have data for every possible destination Requirements Know closest node/range Schedule local transmissions They found the standard MAC may be ok Buffering Scales with radio bandwidth? Scales with expected time to see a destination node? Model Is this useful? Potentially very long time to delivery Potentially wide variance in delivery times Unknown dependence on movement model Space filling unrealistic(destructive to homes) Another submission claims that travel along random line segments also works Unclear generalization to multiple hops Static population model/bounded movement model unrealistic for many random movement models Existing applications seem unlikely consumers What next? Radio people MAC layers tuned to ad hoc mode Wasn’t clear from results presented this is more than a moderate constant factor Systems/applications people Communication patterns with good locality Take advantage of external sources of bandwidth (fiber optics or station wagons of tapes)