Intro

• Community wireless networks share a few wires connections amongst a large group of users
  • two approaches
    • carefully construct multi-hop network with nodes in special locations
    • hot-spot loosely connected nodes
  • ambitious – combine best of both network types
    • little central planning, but still have wide coverage
• evaluation of:
  • unconstrained node placement
  • omni-directional antennas
  • multi-hop routing
  • optimization of routing for throughput in slowly changing network
• RoofNet analysis (37 nodes in a city)

RoofNet Design

• deployed over 4 sq km (cambridge, MA)
• antenna locations not random, but not planned either
• Each node is a PC, 802.11b card and roof-mounted omni-directional antenna.
• 8dBi omni-antenna. 3dB vertical beam @ 20 deg.
• slightly modified pseudo-IBSS mode to prevent network partitioning
• each node essentially acts as the router when a device plugs into it
• software needs to automatically solve a number of problems:
  • addressing
    • roofnet sends ip packets inside its own header format and routing protocol
    • nodes must be able to assign address automatically without explicit configuration, use part of ethernet address and class-A IP block
    • use NAT
  • Gateways and internet access
    • each node attempts to configure itself as a gateway, first and marks itself so if possible
    • gateway itself acts as NAT for connection from RoofNet to the internet
      • (2-layer NAT)
    • if a new gateway is chosen during a TCP connection, the TCP connection may fail
• Routing protocol
  • named srcr - find highest throughput route between any pair of roofnet nodes
  • use dijkstra’s to find routes, maintains metrics on links
  • if no route found, send a flood packet to gather route information
  • flood queries often don’t follow the best route
• routing metric
  • uses a metric called “ETT” - estimated transmission time
  • predict total time to send data packet along a particular route
  • predicts highest throughput bit rate is the bit rate with highest product of delivery probability and bit-rate
  • ETT for a given link is the expected time to send a 1500-byte packet at a link’s highest throughput bit-rate
• bit-rate selection
  • transmit rates of 1, 2, 5.5, 11mbit/s
  • avoids bit rates with high loss
  • sampleRate algorithm adjusts the bit-rate as it sends data packets over a link

Evaluation

• performance
  • mediam throughput is 400kbit/s, mean is 627
  • distribution of speeds generally correlated with hop count
  • rootnet one-hop routes operate at average speed consistent with 5.5mbit transmission rate.
  • long routes suffer from inter-hop collisions
  • still reasonable speeds (4 hops at 379kbit/s)
• link quality+distance
  • most links only capable of ~500kbit/s at best from 500-1300m
  • shorter distances seems to increase link speed
  • fast short hops best policy
• density effects
  • network approaches all pairs connected at ~20 pairs
• mesh robustness
  • only a few poorly connected nodes
  • performance likely drops if links get eliminated
  • best links have high impact on network throughput
• architectural alternatives
  • 5 gateways requires to connect all roofnet nodes
  • multi-hop forwarding provides higher average throughput
  • for single-hop network, 25 gateways would be requires. 90% with 10 gateways
  • for 5 or fewer gateways, random gateway assignment is better even than single-hop
  • for more than 5, careful gateway assignment can increase throughput