《计算机网络》课程教学资源（参考文献）Architecture and Evaluation of an Unplanned 802.11b Mesh Network

Architecture and evaluation of an Unplanned 802.11b Mesh Network John Bicket, Daniel Aguayo, Sanjit Biswas, Robert Morris M.I.T. Computer Science and Artificial Intelligence Laboratory jbicket, aguayo, biswas, rtm @csail. mit.edu ABSTRACT General terms This paper evaluates the ability of a wireless mesh archi- Design, Experimentation, Measurement, Performance tecture to provide high perfo Internet access while demanding little deployment planning or operational man- Keywords agement. The architecture considered in this paper has ur planned node placement (rather than planned topology) Mesh networks, Multi-hop wireless networks, Ad hoc net- omni-directional antennas(rather than directional links), works, Wireless routing, Route metrics and multi-hop routing(rather than single-hop base stations These design decisions contribute to ease of deployment an important requirement for community wireless networks. However. this architecture carries the risk that lack of pl 1. INTRODUCTION ing might render the network's performance unusably low Community wireless networks typically share a few wired For example, it might be necessary to place nodes carefull Internet connections among many users spread over an ur- to ensure connectivity; the omni-directional antennas might ban area. Two approaches to constructing community net- rovide uselessly short radio ranges; or the inefficiency of works are common. The first approach is to carefully con- multi-hop forwarding might leave some users effectively dis- struct a multi-hop network with nodes in chosen locations connected and directional antennas aimed to engineer high-quality ra- with a case study of the Roofnet 802. 11b mesh network Roofnet consists of 37 nodes spread over four square kilo- kilo. groups with technical expertise, but result in high throlla o The paper evaluates this unplanned mesh architecture dio links 31, 8, 29; these networks require well-coordinat ut and good connectivity. The second approach consists meters of an urban area. The network provides users with of individuals operating hot-spot "access points to which usable performance despite lack of planning: the average clients directly connect 5, 4. These access points often inter-node throughput is 627 kbits/second, even though the operate independently and are loosely connected, if at all average route has three hops Access-point networks do not require much coordination to The paper evaluates multiple aspects of the architecture: deploy and operate, but usually do not provide as much the effect of node density on connectivity and throughput; coverage per wired connection as multi-hop networks the characteristics of the links that the routing protocol A more ambitious vision for community networks would elects to use: the usefulness of the highly connected mesh combine the best characteristics of both network types, oper- afforded by omni-directional antennas for robustness and ating without extensive planning or central management but hroughput; and the potential performance of a single-hop still providing wide coverage and acceptable performance network using the same nodes as Roofnet This paper provides an evaluation of such an architecture. consisting of the following design decisions: Categories and subject Descriptors 1. Unconstrained node placement, rather than a topology planned for coverage or performance. The network C.2.1 Computer-Communication Networks]: Network should work well even if the topology is determined Architecture and Design-Wireless communication: C.2.2 omputer-Communication Networks: Network Pro- tocols--Routing protocols 2. Omni-directional antennas. rather than directional an- annas used to form particular high-quality links. Users should be able to install an antenna without know- ing in advance what nodes the antenna might talk to Permission or hard copies of all or part of this work for Nodes should be able to route data through whatever is granted without fee provided that copies are neighbors they happen to find not made o ommercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise 3. Multi-hop routing, rather than single-hop base publish, to post on servers or to redistribute to lists, requires prior specifie tions or access points. Multi-hop routing can Copyright2005ACM1-59593-020-5050060mam MobiCom 05, August 28-September 2, 2005, Cologne coverage and performance despite lack of planning lack of specifically engineered links

Architecture and Evaluation of an Unplanned 802.11b Mesh Network John Bicket, Daniel Aguayo, Sanjit Biswas, Robert Morris M.I.T. Computer Science and Artificial Intelligence Laboratory jbicket, aguayo, biswas, rtm @csail.mit.edu ABSTRACT This paper evaluates the ability of a wireless mesh archi￾tecture to provide high performance Internet access while demanding little deployment planning or operational man￾agement. The architecture considered in this paper has un￾planned node placement (rather than planned topology), omni-directional antennas (rather than directional links), and multi-hop routing (rather than single-hop base stations). These design decisions contribute to ease of deployment, an important requirement for community wireless networks. However, this architecture carries the risk that lack of plan￾ning might render the network’s performance unusably low. For example, it might be necessary to place nodes carefully to ensure connectivity; the omni-directional antennas might provide uselessly short radio ranges; or the inefficiency of multi-hop forwarding might leave some users effectively dis￾connected. The paper evaluates this unplanned mesh architecture with a case study of the Roofnet 802.11b mesh network. Roofnet consists of 37 nodes spread over four square kilo￾meters of an urban area. The network provides users with usable performance despite lack of planning: the average inter-node throughput is 627 kbits/second, even though the average route has three hops. The paper evaluates multiple aspects of the architecture: the effect of node density on connectivity and throughput; the characteristics of the links that the routing protocol elects to use; the usefulness of the highly connected mesh afforded by omni-directional antennas for robustness and throughput; and the potential performance of a single-hop network using the same nodes as Roofnet. Categories and Subject Descriptors C.2.1 [Computer-Communication Networks]: Network Architecture and Design—Wireless communication; C.2.2 [Computer-Communication Networks]: Network Pro￾tocols—Routing protocols Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. MobiCom’05, August 28–September 2, 2005, Cologne, Germany. Copyright 2005 ACM 1-59593-020-5/05/0008 ...$5.00. General Terms Design, Experimentation, Measurement, Performance Keywords Mesh networks, Multi-hop wireless networks, Ad hoc net￾works, Wireless routing, Route metrics 1. INTRODUCTION Community wireless networks typically share a few wired Internet connections among many users spread over an ur￾ban area. Two approaches to constructing community net￾works are common. The first approach is to carefully con￾struct a multi-hop network with nodes in chosen locations and directional antennas aimed to engineer high-quality ra￾dio links [31, 8, 29]; these networks require well-coordinated groups with technical expertise, but result in high through￾put and good connectivity. The second approach consists of individuals operating “hot-spot” access points to which clients directly connect [5, 4]. These access points often operate independently and are loosely connected, if at all. Access-point networks do not require much coordination to deploy and operate, but usually do not provide as much coverage per wired connection as multi-hop networks. A more ambitious vision for community networks would combine the best characteristics of both network types, oper￾ating without extensive planning or central management but still providing wide coverage and acceptable performance. This paper provides an evaluation of such an architecture, consisting of the following design decisions: 1. Unconstrained node placement, rather than a topology planned for coverage or performance. The network should work well even if the topology is determined solely by where participants happen to live. 2. Omni-directional antennas, rather than directional an￾tennas used to form particular high-quality links. Users should be able to install an antenna without know￾ing in advance what nodes the antenna might talk to. Nodes should be able to route data through whatever neighbors they happen to find. 3. Multi-hop routing, rather than single-hop base sta￾tions or access points. Multi-hop routing can improve coverage and performance despite lack of planning and lack of specifically engineered links

4. Optimization of routing for throughput in a slowly. changing network with many links of intermediate qual- ty, rather than for route repair in a mobile network These decisions ease deployment, but they also risk re- duced network performance. For example, radio ranges might too short to connect some nodes; many links might be low quality; nodes might interfere with each other and cau persistent packet loss; standard TCP might interact poorly with low-quality radio links; or the outdoor omni-directional antennas might pick up unacceptable levels of interference from other ISM-band users throughout the city. While none of the individual elements of the unplanned mesh architecture outlined above are new [1, 3, 2, 6, there has been no systematic evaluation of whether the architec- ure as a whole can achieve its goals. Prior evaluations o similar mesh networks have focused on routing metrics [14 and the radio-level causes of packet loss 7. MANETs have been extensively studied [10, 19, 12), but their routing proto- col design is focused on coping with rapid topology change This paper evaluates the unplanned mesh architecture Figure 1: A map of Roofnet. Each dot represents with a case study of Roofnet. Roofnet is a multi-hop 802.11b a wireless node. The map covers the south-east nternet access network consisting of 37 nodes spread over portion of Cambridge, Massachusetts. The Charles bout four square kilometers of a city. While previous worl River curves along the lower boundary of the map, MIT is at the lower right, and Harvard is at the ivestigated the physical-layer causes of packet loss in Roof- upper left net 7], this paper describes Roofnet's end-to-end character- The paper's conclusions are as follows. The unplanned most Roofnet nodes are located in such buildings, but eight re in taller buildings. Line-of-sight signal propagation be- users see throughput and delay comparable to DSL links and tween nodes is often obstructed the average throughput between nodes is 627 kbits/ second Throughput decreases with number of hops, but even eight Each Roofnet node is hosted by a volunteer user. Vol- hop routes average 160 kbits/second. Single-flow through unteers were solicited by a combination of word of mouth put increases with node density, since the routing protocol posters distributed in and near the network's coverage area, makes use of short links and drives them at high bit-rates. and links to a Web sign-up page. Each volunteer installed The majority of the radio links are between 500 and 1300 is or her own node, including the roof-mounted antenna. The resulting node locations are neither truly random nor meters long, though the links that prove the most useful to selected according to any particular plan the routing protocol are a relatively small number of shor high-throughput links. While Roofnet includes a few nodes 2.1 Hardware positioned on the tops of tall buildings, its performance and obustness do not greatly depend on any small set of nodes Each Roofnet node consists of a PC, an 802.11b card, and it is a true mesh. Finally, while a single-hop base-station a roof-mounted omni-directional antenna. The pc is small d quiet so that it is suitable for residential use. The PCs architecture would have been possible for Roofnet. for any Ethernet port provides Internet service to the user. Each given number of wired access points, Roofnet's multi-ho forwarding improves coverage and throughput PC has a hard drive for collecting traces and a Cd rea Some areas that this paper does not investigate include case an over-the-network upgrade fails. An entire Roofnet the effect of multiple concurrent flows, network and protocol kit(PC, antenna, mounting hardware, and cable) can be scalability, the detailed design of routing protocols, change carried by network performance over time, and the long-term evolu- Each 8 dBi omni-directional antenna has a 3-dB vertical tion of the network as users join and depart beam width of 20 degrees. The wide beam sacrifices gain The next section outlines Roofnet's design. Section 3 is but means the antenna need not be perfectly vertical. The of the paper, presenting measurements and dis- ntenna is connected to its node with coaxial cable which in- cussing what they imply about the unplanned mesh archi- troduces 6 to 10 dB of attenuation. Three nodes located on tecture. Section 4 presents a snapshot of user traffic on the roofs of tall buildings, have 12 dBi Yagi directional an- Roofnet. Section 5 reviews related work and Section 6 con- ennas with 45-degree horizontal and vertical beam widths. cludes Each node is equipped with an 802. 11b wireless card based on the Intersil Prism 2.5 chip-set. The radios transmit 200 2. ROOFNET DESIGN milliwatts of power, operate with RTS/CTS disabled, and all share the same 802.11b channel. The cards use a non- Roofnet is deployed over an area of about four square kilo- standard"pseudo-IBSS"mode that is similar to standard meters in Cambridge, Massachusetts. Figure 1 shows a map 802. 11b IBSS (or "ad hoc")mode, in tha f the network. This area is urban and densely populated cate directly without access points. Pseudo-IBSS omits Most buildings are three- or four-story apartment buildings; 802.11s beacons and BSSID(network ID)mechanism, solv-

4. Optimization of routing for throughput in a slowly￾changing network with many links of intermediate qual￾ity, rather than for route repair in a mobile network. These decisions ease deployment, but they also risk re￾duced network performance. For example, radio ranges might be too short to connect some nodes; many links might be low quality; nodes might interfere with each other and cause persistent packet loss; standard TCP might interact poorly with low-quality radio links; or the outdoor omni-directional antennas might pick up unacceptable levels of interference from other ISM-band users throughout the city. While none of the individual elements of the unplanned mesh architecture outlined above are new [1, 3, 2, 6], there has been no systematic evaluation of whether the architec￾ture as a whole can achieve its goals. Prior evaluations of similar mesh networks have focused on routing metrics [14] and the radio-level causes of packet loss [7]. MANETs have been extensively studied [10, 19, 12], but their routing proto￾col design is focused on coping with rapid topology changes due to mobility. This paper evaluates the unplanned mesh architecture with a case study of Roofnet. Roofnet is a multi-hop 802.11b Internet access network consisting of 37 nodes spread over about four square kilometers of a city. While previous work investigated the physical-layer causes of packet loss in Roof￾net [7], this paper describes Roofnet’s end-to-end character￾istics. The paper’s conclusions are as follows. The unplanned mesh architecture of Roofnet works: with few exceptions, users see throughput and delay comparable to DSL links and the average throughput between nodes is 627 kbits/second. Throughput decreases with number of hops, but even eight￾hop routes average 160 kbits/second. Single-flow through￾put increases with node density, since the routing protocol makes use of short links and drives them at high bit-rates. The majority of the radio links are between 500 and 1300 meters long, though the links that prove the most useful to the routing protocol are a relatively small number of short high-throughput links. While Roofnet includes a few nodes positioned on the tops of tall buildings, its performance and robustness do not greatly depend on any small set of nodes; it is a true mesh. Finally, while a single-hop base-station architecture would have been possible for Roofnet, for any given number of wired access points, Roofnet’s multi-hop forwarding improves coverage and throughput. Some areas that this paper does not investigate include the effect of multiple concurrent flows, network and protocol scalability, the detailed design of routing protocols, change in network performance over time, and the long-term evolu￾tion of the network as users join and depart. The next section outlines Roofnet’s design. Section 3 is the core of the paper, presenting measurements and dis￾cussing what they imply about the unplanned mesh archi￾tecture. Section 4 presents a snapshot of user traffic on Roofnet. Section 5 reviews related work, and Section 6 con￾cludes. 2. ROOFNET DESIGN Roofnet is deployed over an area of about four square kilo￾meters in Cambridge, Massachusetts. Figure 1 shows a map of the network. This area is urban and densely populated. Most buildings are three- or four-story apartment buildings; Figure 1: A map of Roofnet. Each dot represents a wireless node. The map covers the south-east portion of Cambridge, Massachusetts. The Charles River curves along the lower boundary of the map, MIT is at the lower right, and Harvard is at the upper left. most Roofnet nodes are located in such buildings, but eight are in taller buildings. Line-of-sight signal propagation be￾tween nodes is often obstructed. Each Roofnet node is hosted by a volunteer user. Vol￾unteers were solicited by a combination of word of mouth, posters distributed in and near the network’s coverage area, and links to a Web sign-up page. Each volunteer installed his or her own node, including the roof-mounted antenna. The resulting node locations are neither truly random nor selected according to any particular plan. 2.1 Hardware Each Roofnet node consists of a PC, an 802.11b card, and a roof-mounted omni-directional antenna. The PC is small and quiet so that it is suitable for residential use. The PC’s Ethernet port provides Internet service to the user. Each PC has a hard drive for collecting traces and a CD reader in case an over-the-network upgrade fails. An entire Roofnet kit (PC, antenna, mounting hardware, and cable) can be carried by one person. Each 8 dBi omni-directional antenna has a 3-dB vertical beam width of 20 degrees. The wide beam sacrifices gain but means the antenna need not be perfectly vertical. The antenna is connected to its node with coaxial cable which in￾troduces 6 to 10 dB of attenuation. Three nodes, located on the roofs of tall buildings, have 12 dBi Yagi directional an￾tennas with 45-degree horizontal and vertical beam widths. Each node is equipped with an 802.11b wireless card based on the Intersil Prism 2.5 chip-set. The radios transmit 200 milliwatts of power, operate with RTS/CTS disabled, and all share the same 802.11b channel. The cards use a non￾standard “pseudo-IBSS” mode that is similar to standard 802.11b IBSS (or “ad hoc”) mode, in that nodes commu￾nicate directly without access points. Pseudo-IBSS omits 802.11’s beacons and BSSID (network ID) mechanism, solv-

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 lower

ing 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

Metric, it will forward the query again wi st 2.5 Bit-Rate selection route. In practice, most nodes forward a onlv once or twice. A larger or denser network than Roofnet has its own algorithm to choose among the 802. 11b transmit bit-rates of 1, 2, 5.5, and 11 megabits/ second. The nodes send data to many destinations might require a algorithm included in the Prism firmware tends to avoid us- scalable query mechanism ing bit-rates with significant loss-rates, a policy which per- Link conditions may change so that an active route is no forms badly on Roofnet. The highest-throughput routes of- longer the best route. If a link on an active route stops for- ten involve links with relatively high link-level loss rates warding packets altogether, the upstream node will send a since a single-hop route with 40% loss can deliver more data notification back to each failed packet's source. If a link or than a two-hop route with perfect links. In addition, be an active route merely degrades, sources using that link will cause the 802. 11b bit-rates are at roughly power-of-two in- learn of the links new metric from forwarded data pack tervals, a high bit-rate with up to 50% loss is preferable to ets. A source re-runs Dijkstra's algorithm on its database the next-lowest bit-rate whenever it learns of a changed link metric, so the source Roofnet's algorithm, called SampleRate 9, adjusts the will switch routes if it knows about a better one. if a link bit-rate as it sends data packets over a link. Like ETT, anges to have a better metric, sources that might want SampleRate judges which bit-rate will provide the highest o use that link can learn about it either through dummy throughput based on delivery probabilities measured at the queries from gateways, or by a mechanism in which nodes different bit-rates. Unlike ETT, SampleRate bases its deci- forwarding data packets include unsolicited link metric in- sions on actual data transmissions rather than on periodic formation about nearby links 2. 4 Routing metric SampleRate sends most data packets at the bit-rate it Srcr chooses routes with an "estimated transmission time currently believes will provide the highest throughput. Sam- (ETT) metric, derived from estimated transmission count pleRate periodically sends a data packet at some other bit- (ETX)[13]. ETT predicts the total amount of time it would rate in order to update a record of each bit-rate's deliv take to send a data packet along a route, taking into account ery probability. SampleRate switches to a different bit- each link's highest-throughput transmit bit-rate and its de- rate if the throughput estimate based on that bit-ra rery probability at that bit-rate. Srcr chooses the route recorded delivery probability is higher than the current bit- with the lowest ETT, since that route is likely to be able to rate's throughput deliver the most packets per unit time. Each Roofnet node sends periodic 1500-byte broadcast at each available 802.11 bit-rate, and periodic minimum- size broadcasts at one megabit /second. Nodes keep track of 3. EVALUATION the fraction of these broadcasts that they receive from each This section prizes the end-to-end performance of neighbor, and report the statistics back to each neighbor. Roofnet and the impact of some of its architectural choices Srcr predicts that a link's highest-throughput bit-rate is the Section 3.2 presents basic measurements of throughput bit-rate with the highest product of delivery probability and and latency over the network. Over all pairs, throughput bit-rate. Delivery probability at a bit-rate is the product averages 627 kbits/second, and round-trip latency averages of the fraction of 1500-byte broadcasts delivered and the 39 milliseconds. Transfers from the Internet gateways ran fraction of 60-byte one megabit/ second broadcasts delivered at an average of 1395 kbits/second, with an average latency in the reverse direction, to account for lost 802.11 ACKs of 22 milliseconds successfully send a 1500-byte packet at that link's highest. Next the paper investigates the effects of three choices The ETT metric for a given link is the expected time to the unplanned mesh architecture. Section 3.3 studies throughput bit-rate, including the time for the number of how Srer makes use of the large number of links afforded transmissions predicted by the measured delivery proba- by omni-directional antennas. Most links are between 500 bilities. The ett metric for a route is the sum of the etts d 1500 meters long and have throughputs of less than 500 for each of the routes links. That is. Srcr assumes the fol kbits/second; however, Srcr largely ignores them and uses a lowing relation between the throughputs ti of a route's hops relatively small number of shorter links that run at two or and the route' s end-to-end throughput t more megabits/second. The median link-level loss rate of the links Srcr chooses is 20%. Section 3.4 explores the effect of node density on connectivity and throughput, by evaluat- ing different-size subsets of the Roofnet nodes. These data provide a feel for how well other mesh deployments with dif- This relation is reasonably accurate for short routes where ferent node densities might work. Sect at most one hop can send at a time 24]. It underesti Roofnet takes advantage of a highly connected mesh. Most mates throughput for longer routes in which distant hops Roofnet nodes route through many neighbors. The mesh can send concurrently without interfering, and overestimates is robust in the sense that no small set of links contributes throughput when transmissions on different hops collide and disproportionately to overall throughput re lost. Section 3.7 examines the accuracy of Equation 1 Section 3.6 compares multi-hop routing with a single-hop ETT is similar to WCETT [15. ETT uses broadcast architecture that resembles an access-point network. With robes to predict transmission time, while WcetT directly only single-hop forwarding, five well-placed gateways would neasures ETT using unicast packets between each pair of be required to cover all roofnet nodes, and even more would nodes. ETT is likely to be less accurate than WCETT, but be required to match the average throughput that multi-hop has lower measurement overhead Roofnet provides

metric, it will forward the query again with the new best route. In practice, most nodes forward a query only once or twice. A larger or denser network than Roofnet in which nodes send data to many destinations might require a more scalable query mechanism. Link conditions may change so that an active route is no longer the best route. If a link on an active route stops for￾warding packets altogether, the upstream node will send a notification back to each failed packet’s source. If a link on an active route merely degrades, sources using that link will learn of the link’s new metric from forwarded data pack￾ets. A source re-runs Dijkstra’s algorithm on its database whenever it learns of a changed link metric, so the source will switch routes if it knows about a better one. If a link changes to have a better metric, sources that might want to use that link can learn about it either through dummy queries from gateways, or by a mechanism in which nodes forwarding data packets include unsolicited link metric in￾formation about nearby links. 2.4 Routing Metric Srcr chooses routes with an “estimated transmission time” (ETT) metric, derived from estimated transmission count (ETX) [13]. ETT predicts the total amount of time it would take to send a data packet along a route, taking into account each link’s highest-throughput transmit bit-rate and its de￾livery probability at that bit-rate. Srcr chooses the route with the lowest ETT, since that route is likely to be able to deliver the most packets per unit time. Each Roofnet node sends periodic 1500-byte broadcasts at each available 802.11 bit-rate, and periodic minimum￾size broadcasts at one megabit/second. Nodes keep track of the fraction of these broadcasts that they receive from each neighbor, and report the statistics back to each neighbor. Srcr predicts that a link’s highest-throughput bit-rate is the bit-rate with the highest product of delivery probability and bit-rate. Delivery probability at a bit-rate is the product of the fraction of 1500-byte broadcasts delivered and the fraction of 60-byte one megabit/second broadcasts delivered in the reverse direction, to account for lost 802.11 ACKs. The ETT metric for a given link is the expected time to successfully send a 1500-byte packet at that link’s highest￾throughput bit-rate, including the time for the number of retransmissions predicted by the measured delivery proba￾bilities. The ETT metric for a route is the sum of the ETTs for each of the route’s links. That is, Srcr assumes the fol￾lowing relation between the throughputs ti of a route’s hops and the route’s end-to-end throughput t: t = 1 P i 1 ti (1) This relation is reasonably accurate for short routes where at most one hop can send at a time [24]. It underesti￾mates throughput for longer routes in which distant hops can send concurrently without interfering, and overestimates throughput when transmissions on different hops collide and are lost. Section 3.7 examines the accuracy of Equation 1. ETT is similar to WCETT [15]. ETT uses broadcast probes to predict transmission time, while WCETT directly measures ETT using unicast packets between each pair of nodes. ETT is likely to be less accurate than WCETT, but has lower measurement overhead. 2.5 Bit-Rate Selection Roofnet has its own algorithm to choose among the 802.11b transmit bit-rates of 1, 2, 5.5, and 11 megabits/second. The algorithm included in the Prism firmware tends to avoid us￾ing bit-rates with significant loss-rates, a policy which per￾forms badly on Roofnet. The highest-throughput routes of￾ten involve links with relatively high link-level loss rates, since a single-hop route with 40% loss can deliver more data than a two-hop route with perfect links. In addition, be￾cause the 802.11b bit-rates are at roughly power-of-two in￾tervals, a high bit-rate with up to 50% loss is preferable to the next-lowest bit-rate. Roofnet’s algorithm, called SampleRate [9], adjusts the bit-rate as it sends data packets over a link. Like ETT, SampleRate judges which bit-rate will provide the highest throughput based on delivery probabilities measured at the different bit-rates. Unlike ETT, SampleRate bases its deci￾sions on actual data transmissions rather than on periodic broadcast probes. As a result SampleRate can adjust its choice more quickly and accurately than ETT. SampleRate sends most data packets at the bit-rate it currently believes will provide the highest throughput. Sam￾pleRate periodically sends a data packet at some other bit￾rate in order to update a record of each bit-rate’s deliv￾ery probability. SampleRate switches to a different bit￾rate if the throughput estimate based on that bit-rate’s recorded delivery probability is higher than the current bit￾rate’s throughput. 3. EVALUATION This section characterizes the end-to-end performance of Roofnet and the impact of some of its architectural choices. Section 3.2 presents basic measurements of throughput and latency over the network. Over all pairs, throughput averages 627 kbits/second, and round-trip latency averages 39 milliseconds. Transfers from the Internet gateways ran at an average of 1395 kbits/second, with an average latency of 22 milliseconds. Next the paper investigates the effects of three choices in the unplanned mesh architecture. Section 3.3 studies how Srcr makes use of the large number of links afforded by omni-directional antennas. Most links are between 500 and 1500 meters long and have throughputs of less than 500 kbits/second; however, Srcr largely ignores them and uses a relatively small number of shorter links that run at two or more megabits/second. The median link-level loss rate of the links Srcr chooses is 20%. Section 3.4 explores the effect of node density on connectivity and throughput, by evaluat￾ing different-size subsets of the Roofnet nodes. These data provide a feel for how well other mesh deployments with dif￾ferent node densities might work. Section 3.5 assesses how Roofnet takes advantage of a highly connected mesh. Most Roofnet nodes route through many neighbors. The mesh is robust in the sense that no small set of links contributes disproportionately to overall throughput. Section 3.6 compares multi-hop routing with a single-hop architecture that resembles an access-point network. With only single-hop forwarding, five well-placed gateways would be required to cover all Roofnet nodes, and even more would be required to match the average throughput that multi-hop Roofnet provides

Finally, Section 3.7 presents measurements suggesting that inter-hop collisions are a major limiting factor in multi-hop throughput 0.8 3.1 Method The results presented here are derived from four sets of 0.6 measurements on roone 1. The " multi-hop TCP data-set is the result of a 15- second one-way bulk TCP transfer between each pair of Roofnet nodes. Throughput is measured by the number of data bytes delivered to the receiving appli- cation. Each transfer is preceded by a 30-second quiet interval and then ten seconds in which the sender sends 05001000150020002500300035004000 84-byte pings once per second to establish the route and measure latency. The throughput result and the TCP Throughput(kilobits/second) median round-trip ping time are recorded along with the route in use at the end of the transfer The mea- Figure 2: CDF of the TCP throughput between each surements are taken with RTS/CTS disabled; mea- pair of nodes in the network.(multi-hop TCP) surements with RTS/CTS enabled are presented in Section 3.7 Hops Number of ThroughputLatency About 10% of pairs failed to find a working route in Pairs(kbits/sec)( the multi-hop TCP measurements. The reason for this is that flooded routing queries sometimes do not reach distant nodes due to link losses: the query packets are broadcast without link-layer retransmission. Srer re- 23 210 foods every five seconds if needed, but in many cases even this was not enough. The failed pairs are included in the throughput results with throughputs of zer 33 181 14 119 2. The"single-hop TCP data-set is the result of mea- 4 suring the TCP throughput on the direct radio link no route between each pair of nodes 3. The "loss matrix data-set is the result of measur- ing the loss rate between each pair of nodes using 1500-byte broadcasts at each 802.11b transmit bit Table 1: Average TCP throughput and round-trip rate. These loss rates reflect underlying link losses ping latency between each pair in the network, ar since 802.11 does not retransmit broadcast packets ranged by the number of hops in a typical path be- tween the pair (multi-hop TCP) 4. The"multi-hop density" data-set measures multi-hop TCP throughput between a fixed set of four nodes while varying the number of Roofnet nodes that are 3.2 Basic Performance Figure 2 shows the distribution of TCP throughputs amon all pairs of Roofnet nodes. The median is 400 kbits/second Some of the analyses involve simulated route through- and the average is 627. put calculated from the single-hop TCP data-set and Equa- The distribution of throughputs is explained largely by ion 1. This technique allows us to estimate the throughput hop-count, as successive nodes in a multi-hop route usually of paths that were not used by the all-pairs TCP measure must defer to each others'transmissions. Table 1 arranges the throughput data by hop-count in order to illustrate this Each graphs caption ends with the data-set from which point. The routes with low hop-count have much higher the graph was derived, in parentheses, and says "Simulate throughput than those with many hops when appropriate. For comparison, Table 2 shows the theoretical maximum Roofnet ordinarily des internet access to its users throughput for various bit-rates over multiple lossless hops and this service was not disabled during these experiments. This table is computed with Equation 1. Per-link through Thus the experiments may be affected by Roofnet traffic as puts include transmission time, inter-frame gaps, and link well as other uses of the 2. 4 gigahertz ISM band level acknowledgments Most of the results presented below include all pairs of Tables 1 and 2 suggest that Roofnet's one-hop routes op- Roofnet nodes, rather than just communication with the verage speed consistent with the 5.5 megabi ateways. This is because the Internet performance Roofnet transmission rate, but that longer routes are disproportion ly dependent on the specifics of Roofnet's ately slower. Section 3.7 suggests that multi-hop routes Internet gateways, which in a community network would suffer from inter-hop collisions and have lower performance robably be randomly placed than predicted by Equation 1

Finally, Section 3.7 presents measurements suggesting that inter-hop collisions are a major limiting factor in multi-hop throughput. 3.1 Method The results presented here are derived from four sets of measurements on Roofnet: 1. The “multi-hop TCP” data-set is the result of a 15- second one-way bulk TCP transfer between each pair of Roofnet nodes. Throughput is measured by the number of data bytes delivered to the receiving appli￾cation. Each transfer is preceded by a 30-second quiet interval and then ten seconds in which the sender sends 84-byte pings once per second to establish the route and measure latency. The throughput result and the median round-trip ping time are recorded along with the route in use at the end of the transfer. The mea￾surements are taken with RTS/CTS disabled; mea￾surements with RTS/CTS enabled are presented in Section 3.7. About 10% of pairs failed to find a working route in the multi-hop TCP measurements. The reason for this is that flooded routing queries sometimes do not reach distant nodes due to link losses: the query packets are broadcast without link-layer retransmission. Srcr re- floods every five seconds if needed, but in many cases even this was not enough. The failed pairs are included in the throughput results with throughputs of zero. 2. The “single-hop TCP” data-set is the result of mea￾suring the TCP throughput on the direct radio link between each pair of nodes. 3. The “loss matrix” data-set is the result of measur￾ing the loss rate between each pair of nodes using 1500-byte broadcasts at each 802.11b transmit bit￾rate. These loss rates reflect underlying link losses, since 802.11 does not retransmit broadcast packets. 4. The “multi-hop density” data-set measures multi-hop TCP throughput between a fixed set of four nodes, while varying the number of Roofnet nodes that are participating in routing. Some of the analyses involve simulated route through￾put calculated from the single-hop TCP data-set and Equa￾tion 1. This technique allows us to estimate the throughput of paths that were not used by the all-pairs TCP measure￾ments. Each graph’s caption ends with the data-set from which the graph was derived, in parentheses, and says “Simulated” when appropriate. Roofnet ordinarily provides Internet access to its users, and this service was not disabled during these experiments. Thus the experiments may be affected by Roofnet traffic as well as other uses of the 2.4 gigahertz ISM band. Most of the results presented below include all pairs of Roofnet nodes, rather than just communication with the gateways. This is because the Internet performance Roofnet users see is highly dependent on the specifics of Roofnet’s Internet gateways, which in a community network would probably be randomly placed. 0 0.2 0.4 0.6 0.8 1 0 500 1000 1500 2000 2500 3000 3500 4000 Cumulative Fraction of Pairs TCP Throughput (kilobits/second) Figure 2: CDF of the TCP throughput between each pair of nodes in the network. (multi-hop TCP) Hops Number of Throughput Latency Pairs (kbits/sec) (ms) 1 158 2451 14 2 303 771 26 3 301 362 45 4 223 266 50 5 120 210 60 6 43 272 100 7 33 181 83 8 14 159 119 9 4 175 182 10 1 182 218 no route 132 0 – Avg: 2.9 Total: 1332 Avg: 627 Avg: 39 Table 1: Average TCP throughput and round-trip ping latency between each pair in the network, ar￾ranged by the number of hops in a typical path be￾tween the pair. (multi-hop TCP) 3.2 Basic Performance Figure 2 shows the distribution of TCP throughputs among all pairs of Roofnet nodes. The median is 400 kbits/second, and the average is 627. The distribution of throughputs is explained largely by hop-count, as successive nodes in a multi-hop route usually must defer to each others’ transmissions. Table 1 arranges the throughput data by hop-count in order to illustrate this point. The routes with low hop-count have much higher throughput than those with many hops. For comparison, Table 2 shows the theoretical maximum throughput for various bit-rates over multiple lossless hops. This table is computed with Equation 1. Per-link through￾puts include transmission time, inter-frame gaps, and link￾level acknowledgments. Tables 1 and 2 suggest that Roofnet’s one-hop routes op￾erate at an average speed consistent with the 5.5 megabit transmission rate, but that longer routes are disproportion￾ately slower. Section 3.7 suggests that multi-hop routes suffer from inter-hop collisions and have lower performance than predicted by Equation 1