Architecture and Evaluation of an Unplanned 802 11b Mesh Network John Bicket Daniel Aguayo Sanjit Biswas and Robert Morris MIT CSAIL MobiCom 05 slides by Jong Kwon Lee presented by Fallon Chen May 17 2007 1 Community Wireless Networks 2 approaches to constructing community wireless networks Carefully constructed multi hop network with nodes in chosen locations directional antennas for high quality radio links Hot spot access points to which clients directly connect Do not require much coordination But not much coverage per wired connection as multi hop networks Combine the best characteristics of both approaches Unconstrained node placement No planning Omni directional antennas No specifically engineered links Multi hop routing Improve coverage performance Optimization of routing for throughput in a slowly changing networks rather than for route repair in a mobile networks 2 MIT Roofnet Roofnet Multi hop 802 11b Internet access network 37 nodes spread over 4 km2 of a city Goal of this paper Evaluation of the unplanned mesh architecture with a case study of Roofnet End to end characteristics of Roofnet c f Previous work by the authors was on the physical layer causes of packet loss SIGCOMM 04 3 Roofnet Design Urban and densely populated area Mostly 3 or 4 story buildings Each Roofnet node is hosted by a volunteer user 4 Hardware Roofnet node PC 802 11b card roof mounted omni directional antenna The PC s Ethernet port provides Internet service to the user 802 11b wireless card in each node Based on the Intersil prism 2 5 chip set The radios operate with RTS CTS disabled All share the same 802 11b channel Use Non standard pseudo IBSS mode Nodes communicate directly without access points 5 Node Software Node software Linux Routing S W DHCP server web server Roofnet Node PC User PC or Laptop From user s perspective the node acts like a cable DSL modem 6 Auto Configuration Addressing Roofnet carries IP packets inside its own header format and routing protocol Each Roofnet node has an unique internal IP address of the form 10 x x x meaningful only inside Roofnet The Roofnet S W assigns itself addresses automatically without requiring explicit configuration Low 24 bits low 24 bits of Ethernet address High 8 bits unused class A IP address block A Roofnet node allocates IP addresses via DHCP to user hosts attached to the node s Ethernet port From the reserved 192 168 1 x IP address block Uses NAT between Ethernet and Roofnet 192 168 1 x NAT 10 x x x 7 Auto Configuration Gateways and Internet Access Assumption A small fraction of Roofnet users share their wired Internet access links Identifying a Roofnet node as a gateway On start up each Roofnet node checks to see if it can reach the Internet through its Ethernet port Succeed advertise itself to Roofnet as an Internet gateway Fail acts as a DHCP server and default router for hosts on its Ethernet Each gateway uses NAT between Roofnet and Internet When a node sends traffic through Roofnet to the Internet the node selects the gateway to which it has the best route metric Roofnet currently has 4 Internet gateways 8 Routing Protocol Srcr Roofnet s routing protocol Tries to find the highest throughput route between any pair of Roofnet nodes Combination of link state and DSR style on demand querying Srcr source routes data packets like DSR in order to avoid routing loops when link metrics change Each Srcr node maintains a partial database of link metrics btw other pairs of nodes and uses Dijkstra s algorithm to find routes Each Roofnet gateway periodically floods a dummy query that allows all other nodes to learn about links on the way to that gateway 9 Routing Metric Estimated Transmission Time ETT metric ETT predicts the total amount of time it would take to send a data packet along a route Each Roofnet node sends periodic 1500 byte broadcasts at each available 802 11b bit rate and periodic minimum size 60 byte broadcasts at 1 Mbps overhead ETT for a given link expected time to successfully send a 1500byte packet at that link s highest throughput bit rate including the time for the number of retransmissions predicted by the measured delivery probabilities highest throughput bit rate bit rate with highest delivery prob X bit rate ETT for a route sum of ETTs for each of the route s links t 1 1 i t i t e2e throughput ti throughput of hops 10 Bit Rate Selection In 802 11b a high bit rate with up to 50 loss is preferable to the next lowest bit rate Higher throughput with relatively high loss rates SampleRate Roofnet s own algorithm to choose among the 802 11b transmit bit rates of 1 2 5 5 11 Mbps Adjusts the bit rate as it sends data packets over a link Like ETT it judges which bit rate will provide the highest throughput based on delivery probabilities measured at the different bit rates Unlike ETT its decision is based on actual data transmissions rather than on periodic broadcast probes It can adjust its choice more quickly and accurately 11 Evaluation Method 4 sets of measurements on Roofnet Multi hop TCP 15 sec 1 way bulk TCP transfer btw each pair of Roofnet nodes Single hop TCP TCP throughput measured on the direct radio link btw each pair of nodes Loss matrix loss rate measured btw each pair of nodes using 1500 byte broadcasts at each 802 11b bit rate Multi hop density multi hop TCP throughput measured btw a fixed set of 4 nodes while varying the number of Roofnet nodes participating in routing Some of the analyses involve simulated route throughput calculated from the single hop TCP 12 Evaluation end to end performance of Roofnet Basic Performance Link Quality and Distance How Roofnet takes advantage of a highly connected mesh Architectural Alternatives Effect of node density on connectivity and throughput Mesh Robustness Study of how Srcr makes use of links Effect of Density Basic measurements of throughput and latency over the network Comparison btw multi hop routing and a single hop architecture Inter hop Interference Inter hop collisions are a major limiting factor in multi hop throughput 13 Basic Performance 1 Distribution of throughput among all pairs of Roofnet nodes Largely related to hop count see Table 1 Med 400 kbps Avg 627 kbps 14 Basic Performance 2 TCP throughput to each node from its chosen Gateway No problem in interactive sessions 15 Link Quality and Distance 1 Throughput vs Distance of each available link top Only the links that Srcr uses in some route bottom Srcr uses almost all of the links faster than 2 Mbps Fast
View Full Document
Unlocking...