ing IBSS mode's tendency to form partitions which have dif- Each gateway acts as a NAt for connections from roof- ferent BSSIDs despite having the same network ID. These net to the Internet, rewriting the source address of packets partitions made it impossible to operate Roofnet reliably coming from Roofnet with the IP address of the gateway's with IBSS mode Ethernet interface When a node sends traffic through roofnet to the int 2.2 Software and Auto-Configuration net, the node selects the gateway to which it has the best Each Roofnet node runs identical turn-key software co route metric. The node keeps track of which gateway is be. isting of Linux, routing software implemented in Click (22 ing used for each open TCP connection, because the gate- a DHCP server. and a web server so users can monitor the way's use of NAf requires each connection to use a single network status. Most users pick up nodes from us at our gateway. If the routing protocol later decides that a dif- lab with software pre-installed. We regularly upgrade all ferent gateway has the best metric, the node continues to the nodes,software over Roofnet, and occasionally by mail- forward data on existing TCP connections to those connec- ing out installation CDs tions'original gateways From the user's perspective, the node acts like a cable or Each new TCP connection uses the gateway with the best DSL modem: the user connects a PC or laptop to the node metric when the connection starts. If a Roofnet gateway Ethernet interface, and the node automatically configures fails, existing TCP connections through that gateway will he user's computer via DHCP, listing the node itself as the fail(because of the NAT), but new connections will use a default ip router some users choose to connect the node to their ireless access poir Roofnet currently has four Internet gateways. Tv In order that roofnet nodes be completely self-configuring, located in ordinary residences, one is on the roof of a six- the software must automatically solve a number of problems story university building, and the last is in a ninth-story allocating addresses, finding a gateway between Roofnet and window of another university building the Internet, and choosing a good multi-hop route to that gateway. 2.3 Routing protocol 2.2.1 Addressing Roofnet's routing protocol, Srcr, tries to find the highest hroughput route between any pair of Roofnet nodes. Omni- Roofnet carries IP packets inside its own header forma directional antennas give Srcr many choices of links it could and routing protocol. Each Roofnet node needs a unique ad- use, but since most links are low-quality, Srcr must evaluate dress at the roofnet layer as well as an Ip address so that each link's usable throughput. Srcr's design is motivated IP applications work between Roofnet nodes. The Roofnet by recent measurement studies of real-world wireless behav software running on a node must be able to assign itself ior{25,18,32,13,7,14] addresses automatically, without requiring explicit config Srcr source-routes data packets, like DSR 20), in order ration. It does this by choosing an address whose low 24 to avoid routing loops when link metrics change. Each Srer bits are the low 24 bits of the node's Ethernet address, and node maintains a partial database of link metrics between whose high8 bits are an unused class-A IP address block. other pairs of nodes(see Section 2.4), and uses Dijkstra's The node uses the same address at both the roofnet and ip gorithm on that database to find routes. Nodes learn fresh layers. These sses are meaningful only inside Roofnet nk metrics in three ways. A node that forwards a packet they are not globally routable over a link includes the link's current metric in the packet's A Roofnet node must also allocate IP addresses via DHCP source route. so that other nodes on the route can see the to user hosts attached to the node's Ethernet port. Each metric. If a node needs to originate a packet but cannot find node allocates these addresses from the reserved 192. 168. 1. x a route with its current database contents. it sends a dsr IP address block. The node uses nat between the ethernet style flooded query and adds the link metrics learned from and Roofnet, so that connections from a user's host appear y responses to its database. Finally, nodes that overhear to the rest of Roofnet to have originated from the user's queries and responses add the metrics in those packets to node. This use of Nat allows nodes to allocate IP addresses their databases to users'hosts independently, but prevents these hosts from This combination of link-state and DSR-style on demand connecting to each other through roofnet querying was inspired by MCL [14. It is particularly effi 2.2.2 Gateways and Internet Access cient when most nodes talk only to a gateway. Each Roofnet gateway periodically floods a dummy query that allows all oofnet's d other nodes to learn about links on the way to tha net users will voluntarily share their wired Internet access way. When a node sends data to a gateway, the gateway links. Multiple consumer DSL ISPs in the Roofnet area( will learn(from the source routed data packets )about links Speakeasy and Cyberion) have Acceptable Use Policies that back to the node. Thus in ordinary operation nodes do not allow wireless sharing of Internet connections, so there is no ever need to send flooded queri ontractual difficulty. One problem with the above scheme is that flooded queri On start-up, each Roofnet node checks to see if it can often do not follow the best route[18. Srcr addresses this reach the Internet through its Ethernet port: it asks for an problem as follows. When a node receives a new query it first IP address DHCP client, and then tries to connect to adds the link metric information in the query's source route ome well-known Internet servers. If this succeeds, the node to its link database. Then the node utes the best route advertises itself to Roofnet as an Internet gateway. Oth- from the query's source, and replaces the querys source rwise the node acts as a DHCP server and default router route with that best route. Finally the node re-broadcasts for hosts on its Ethernet, and connects to the Internet via the query. If the node later receives another copy of the query and is able to compute a best route with a lowering IBSS mode’s tendency to form partitions which have dif￾ferent BSSIDs despite having the same network ID. These partitions made it impossible to operate Roofnet reliably with IBSS mode. 2.2 Software and Auto-Configuration Each Roofnet node runs identical turn-key software con￾sisting of Linux, routing software implemented in Click [22], a DHCP server, and a web server so users can monitor the network status. Most users pick up nodes from us at our lab with software pre-installed. We regularly upgrade all the nodes’ software over Roofnet, and occasionally by mail￾ing out installation CDs. From the user’s perspective, the node acts like a cable or DSL modem: the user connects a PC or laptop to the node’s Ethernet interface, and the node automatically configures the user’s computer via DHCP, listing the node itself as the default IP router. Some users choose to connect the node to their own wireless access point. In order that Roofnet nodes be completely self-configuring, the software must automatically solve a number of problems: allocating addresses, finding a gateway between Roofnet and the Internet, and choosing a good multi-hop route to that gateway. 2.2.1 Addressing Roofnet carries IP packets inside its own header format and routing protocol. Each Roofnet node needs a unique ad￾dress at the Roofnet layer, as well as an IP address so that IP applications work between Roofnet nodes. The Roofnet software running on a node must be able to assign itself addresses automatically, without requiring explicit configu￾ration. It does this by choosing an address whose low 24 bits are the low 24 bits of the node’s Ethernet address, and whose high 8 bits are an unused class-A IP address block. The node uses the same address at both the Roofnet and IP layers. These addresses are meaningful only inside Roofnet; they are not globally routable. A Roofnet node must also allocate IP addresses via DHCP to user hosts attached to the node’s Ethernet port. Each node allocates these addresses from the reserved 192.168.1.x IP address block. The node uses NAT between the Ethernet and Roofnet, so that connections from a user’s host appear to the rest of Roofnet to have originated from the user’s node. This use of NAT allows nodes to allocate IP addresses to users’ hosts independently, but prevents these hosts from connecting to each other through Roofnet. 2.2.2 Gateways and Internet Access Roofnet’s design assumes that a small fraction of Roof￾net users will voluntarily share their wired Internet access links. Multiple consumer DSL ISPs in the Roofnet area (e.g. Speakeasy and Cyberion) have Acceptable Use Policies that allow wireless sharing of Internet connections, so there is no contractual difficulty. On start-up, each Roofnet node checks to see if it can reach the Internet through its Ethernet port: it asks for an IP address as a DHCP client, and then tries to connect to some well-known Internet servers. If this succeeds, the node advertises itself to Roofnet as an Internet gateway. Oth￾erwise the node acts as a DHCP server and default router for hosts on its Ethernet, and connects to the Internet via Roofnet. Each gateway acts as a NAT for connections from Roof￾net to the Internet, rewriting the source address of packets coming from Roofnet with the IP address of the gateway’s Ethernet interface. When a node sends traffic through Roofnet to the Inter￾net, the node selects the gateway to which it has the best route metric. The node keeps track of which gateway is be￾ing used for each open TCP connection, because the gate￾way’s use of NAT requires each connection to use a single gateway. If the routing protocol later decides that a dif￾ferent gateway has the best metric, the node continues to forward data on existing TCP connections to those connec￾tions’ original gateways. Each new TCP connection uses the gateway with the best metric when the connection starts. If a Roofnet gateway fails, existing TCP connections through that gateway will fail (because of the NAT), but new connections will use a different gateway. Roofnet currently has four Internet gateways. Two are located in ordinary residences, one is on the roof of a six￾story university building, and the last is in a ninth-story window of another university building. 2.3 Routing Protocol Roofnet’s routing protocol, Srcr, tries to find the highest￾throughput route between any pair of Roofnet nodes. Omni￾directional antennas give Srcr many choices of links it could use, but since most links are low-quality, Srcr must evaluate each link’s usable throughput. Srcr’s design is motivated by recent measurement studies of real-world wireless behav￾ior [25, 18, 32, 13, 7, 14]. Srcr source-routes data packets, like DSR [20], in order to avoid routing loops when link metrics change. Each Srcr node maintains a partial database of link metrics between other pairs of nodes (see Section 2.4), and uses Dijkstra’s algorithm on that database to find routes. Nodes learn fresh link metrics in three ways. A node that forwards a packet over a link includes the link’s current metric in the packet’s source route, so that other nodes on the route can see the metric. If a node needs to originate a packet but cannot find a route with its current database contents, it sends a DSR￾style flooded query and adds the link metrics learned from any responses to its database. Finally, nodes that overhear queries and responses add the metrics in those packets to their databases. This combination of link-state and DSR-style on demand querying was inspired by MCL [14]. It is particularly effi- cient when most nodes talk only to a gateway. Each Roofnet gateway periodically floods a dummy query that allows all other nodes to learn about links on the way to that gate￾way. When a node sends data to a gateway, the gateway will learn (from the source routed data packets) about links back to the node. Thus in ordinary operation nodes do not ever need to send flooded queries. One problem with the above scheme is that flooded queries often do not follow the best route [18]. Srcr addresses this problem as follows. When a node receives a new query it first adds the link metric information in the query’s source route to its link database. Then the node computes the best route from the query’s source, and replaces the query’s source route with that best route. Finally the node re-broadcasts the query. If the node later receives another copy of the query and is able to compute a best route with a lower