《计算机网络》课程教学资源（参考文献）A High-Throughput Path Metric for Multi-Hop Wireless Routing

A High-Throughput path Metric for Multi-Hop Wireless Routing Douglas S.J. De Couto Daniel Aguayo John Bicket Robert Morris M.I.T. Computer Science and Artificial Intelligence Laboratory Idecouto, aguayo, jbicket, rtm)@csail. mit. edu http://www.pdos.Ics.mitedu/grid abstract 1. Introduction This paper presents the expected transmission count metric(ETX), which Much of the recent work in ad hoc routing protocols for wireless networks [25, 15, 26 has focused on coping with mobile nodes, es the expected total number of packet trans (including retrans ions) required to successfully deliver a packet to the ultimate destina apidly changing topologies, and scalability. Less attention has tion. The etX metric incorporates the effects of link loss ratios, asymmetry been paid to fi nding high-quality paths in the face of lossy wireless in the loss ratios between the two directions of each link, and interference links. This paper presents measurements of link loss characteris- the tics on a 29-node 802.1 1b test-bed. and uses these measurements netric chooses arbitrarily among the different paths of the same minimum to motivate the design of a new metric which accounts for lossy length, regardless of the often large differences in throughput among those links: expected transmission count(ETX) The metric most commonly used by existing ad hoc routing pro- describes the design and implementation of eTX as a metr tocols is minimum hop-count. These protocols typically use only for the DSDV and DSR routing protocols, as well as modifications to DSDV links that deliver routing probe packets(query packets, as in DSr and dSR which allow them ETX Measurements taken from a 29. or AODV, or routing updates, as in DSDV). This approach impl ode 802. 11b test-bed demonstrate the poor performance of minimum ho y assumes that links either work well or don' t work at all. whil ount, illustrate the causes of that poor nance and confirm that eTX often true in wired networks, this is not a reasonable approximation mproves performance. For long paths the throughput improvement is often a factor of two or more suggesting that etX will become more useful as in the wireless case: many wireless links have intermediate loss ra- networks grow larger and paths become longer. tios. A link that delivers only 50% of packets may not be useful for data, but might deliver enough routing update or query packets that Categories and Subject Descriptors the routing protocol uses it anyway Minimizing the hop-count maximizes the distance traveled by C 2.1 [ Computer-Communication Networks]: Network Al each hop, which is likely to minimize signal strength and maximize tecture and Design-Wireless communication; C 2.2 [Computer- the loss ratio. Even if the best route is a minimum hop-count route, Communication Networks ] Network Protocols-Routing proto- imum length, with widely varying qualities, the arbitrary choice made by most minimum hop-count metrics is not likely to select General Terms the best. One contribution of this paper is to quantify these effects Design, Experimentation, Measurement, Performance One approach to fi xing this problem is to mask transmission er- rors. For example, the 802. 11b ACK mechanism resends lost pad Keywords ets, making all but the worst 802 1 1b links appear loss-free. How- Multi-hop wireless networks, Ad hoc networks, Rooftop networks. ever, retransmission does not make lossy links desirable for use Wireless routing, Route metrics, 802.11b, DSR, DSDV, ETX in paths: the retransmissions reduce path throughput and interfere with other traffi c. Another approach might be to augment minimum hop-count routing with a threshold that ignores lossy links, but lossy link may be the only way to reach a certain node, and there might be signifi cant loss ratio differences This research was supported by grants from NTT Corporation ur der the NTT-MIT collaboration, and by MIT's Project Oxyge The solution proposed and evaluated in this paper is the etx metric. ETX fi nds paths with the fewest expected number of trans- missions(including retransmissions) required to deliver a packet all the way to its destination. The metric predicts the number of re- transmissions required using per-link measurements of packet loss not made or dis ommercial advantage and that copie ratios in both directions of each wireless link. The primary goal bear this notice and the full citation on the first page. To copy otherwise, t of the etX design is to fi nd In order to demonstrate that ETX is effective, this paper presents MobiCom 03, September 14-19, 2003, San Diego, California, USA. measurements taken from the test-bed network. These measure Copyright2003ACMl-58113-753-2/030009s5.00

A High-Throughput Path Metric for Multi-Hop Wireless Routing Douglas S. J. De Couto Daniel Aguayo John Bicket Robert Morris M.I.T. Computer Science and Artificial Intelligence Laboratory {decouto, aguayo, jbicket, rtm}@csail.mit.edu http://www.pdos.lcs.mit.edu/grid Abstract This paper presents the expected transmission count metric (ETX), which finds high-throughput paths on multi-hop wireless networks. ETX mini￾mizes the expected total number of packet transmissions (including retrans￾missions) required to successfully deliver a packet to the ultimate destina￾tion. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. In contrast, the minimum hop-count metric chooses arbitrarily among the different paths of the same minimum length, regardless of the often large differences in throughput among those paths, and ignoring the possibility that a longer path might offer higher throughput. This paper describes the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which allow them to use ETX. Measurements taken from a 29- node 802.11b test-bed demonstrate the poor performance of minimum hop￾count, illustrate the causes of that poor performance, and confirm that ETX improves performance. For long paths the throughput improvement is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer. Categories and Subject Descriptors C.2.1 [Computer-Communication Networks]: Network Archi￾tecture and Design—Wireless communication; C.2.2 [Computer￾Communication Networks]: Network Protocols—Routing proto￾cols General Terms Design, Experimentation, Measurement, Performance Keywords Multi-hop wireless networks, Ad hoc networks, Rooftop networks, Wireless routing, Route metrics, 802.11b, DSR, DSDV, ETX This research was supported by grants from NTT Corporation un￾der the NTT-MIT collaboration, and by MIT’s Project Oxygen. 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 ’03, September 14–19, 2003, San Diego, California, USA. Copyright 2003 ACM 1-58113-753-2/03/0009 ...$5.00. 1. Introduction Much of the recent work in ad hoc routing protocols for wireless networks [25, 15, 26] has focused on coping with mobile nodes, rapidly changing topologies, and scalability. Less attention has been paid to finding high-quality paths in the face of lossy wireless links. This paper presents measurements of link loss characteris￾tics on a 29-node 802.11b test-bed, and uses these measurements to motivate the design of a new metric which accounts for lossy links: expected transmission count (ETX). The metric most commonly used by existing ad hoc routing pro￾tocols is minimum hop-count. These protocols typically use only links that deliver routing probe packets (query packets, as in DSR or AODV, or routing updates, as in DSDV). This approach implic￾itly assumes that links either work well or don’t work at all. While often true in wired networks, this is not a reasonable approximation in the wireless case: many wireless links have intermediate loss ra￾tios. A link that delivers only 50% of packets may not be useful for data, but might deliver enough routing update or query packets that the routing protocol uses it anyway. Minimizing the hop-count maximizes the distance traveled by each hop, which is likely to minimize signal strength and maximize the loss ratio. Even if the best route is a minimum hop-count route, in a dense network there may be many routes of the same min￾imum length, with widely varying qualities; the arbitrary choice made by most minimum hop-count metrics is not likely to select the best. One contribution of this paper is to quantify these effects (Section 2). One approach to fixing this problem is to mask transmission er￾rors. For example, the 802.11b ACK mechanism resends lost pack￾ets, making all but the worst 802.11b links appear loss-free. How￾ever, retransmission does not make lossy links desirable for use in paths: the retransmissions reduce path throughput and interfere with other traffic. Another approach might be to augment minimum hop-count routing with a threshold that ignores lossy links, but a lossy link may be the only way to reach a certain node, and there might be significant loss ratio differences even among the above￾threshold links. The solution proposed and evaluated in this paper is the ETX metric. ETX finds paths with the fewest expected number of trans￾missions (including retransmissions) required to deliver a packet all the way to its destination. The metric predicts the number of re￾transmissions required using per-link measurements of packet loss ratios in both directions of each wireless link. The primary goal of the ETX design is to find paths with high throughput, despite losses. In order to demonstrate that ETX is effective, this paper presents measurements taken from the test-bed network. These measure-

画 四 L向e igure 1: A map of the test-bed. Each circle is a node; the large number is the node ID, and the superscript indicates which floor of the building the node is on. ments show that ETX improves the throughput of multi-hop routes placed in ofi ces on fi ve consecutive floors of an offi ce building by up to a factor of two over a minimum hop-count metric. etX Their positions are shown in Figur provides the most improvement for paths with two or more hops, The 802 1 1b cards are confi gured to send at one megabit per sec suggesting that transmission count offers increased benefi t as net nd(Mbps) with one milliwatt(mW) of transmit power. RTS/CTS works grow larger and paths become longer. is turned off, and the cards are set to "ad hoc"(BSS, DCF)mode This paper makes the following main contributions. First, it ex- Each data packet in the following measurements consists of 24 plores the details of the performance of minimum hop-count rout- bytes of 802.11b preamble, 31 bytes of 802 1 1b and Ethernet en- ing on a wireless test-bed, and explains why minimum hop-count capsulation header, 134 bytes of data payload, and 4 bytes of frame often fi nds routes with signifi cantly less throughput than the best check sequence: 193 bytes in total. An 802. 11b ACK packet takes available. Second, it presents the design, implementation, and eval 304 microseconds to transmit, the inter-frame gap is 60 microsec- ation of the etX metric. Third. it describes a set of detailed design onds, and the minimum expected mandatory back-off time is 310 changes to the DSDv [25] and DSr [15] protocols(to which ETX microseconds, resulting in a total time of 2, 218 microseconds per is an extension ), that enable them to more accurately choose routes data packet. This gives a maximum throughput of 451 unicast pack with the best metric This work is part of an effort to deploy a production-quality While the test-bed itself carried only the data and control traffi c multi-hop rooftop 802. 11b network. The initial version of that net involved in each experiment, interference of various kinds was in- work was almost unusable due to the effects detailed in section 2 evitably present. In particular, each floor of the building has four The larger goal of this work is to help make such networks a prad 802. 11b access points, on various different channels tical reality The DSDV implementation used in this paper is new, with mod- The paper proceeds in Section 2 with an analysis of the problems cations described in Section 4 of the new ETX metric, and Section 4 describes how ETX is imple- 2.2 Path Throughputs mented, including changes to DSDV and DSR. Section 5 evaluates Figure 2 compares the throughput of routes found with a min- ETX using experiments on the test-bed. Section 6 describes related imum hop-count metric to the throughput of the best routes that work, and Section 7 concludes the paper could be found. Each curve shows the throughput CDF (in pack ets per second) for 100 node pairs, the pairs are randomly selected 2. Performance of Minimum-Hop-Count from the 2928=812 total ordered pairs in the test-bed. A points Routing x value indicates throughput, in packets per second; the y value in- dicates what fraction of pairs had less throughput. The left curve This section shows that minimum hop-count routing typically is the throughput CDF achieved by routing data using DSDV with fi nds routes with signifi cantly lower throughput than the best avail- the minimum hop-count metric. The right curve is the throughput able. The evidence comes from measurements of dSdv on a test CDF for the best known route between each pair of nodes. Packets bed network. We explain why minimum hop-count does poorly by were only sent between one pair at a time. For each pair, the DSDv looking at the distribution of route throughputs and link loss ratios. and best-path tests were run immediately after one another, to limit variation in link conditions over time 2.1 Experimental Test-Bed The"best path between each pair of nodes was found by send- All the data in this paper are the result of measurements taken ing data along ten potential best paths, one at a time, and select on a 29-node wireless test-bed. Each node consists of a stationary ing the path with the highest throughput. Potential best paths were Linux pc with a Cisco/Aironet 340 PCi 802.1 lb card and an omni- routing algorithm, using as input directional 2.2 dBi dipole antenna(a"rubber duck"). The nodes are measurements of per-link loss ratios, similar to those in Section 2.4

5 19 185 5 10 6 37 5 23 22 5 6 15 6 25 135 5 17 6 14 6 6 20 24 5 21 6 26 1 5 Approx. 79 m Approx. 22 m 115 3 2 2 8 4 9 3 3 125 164 5 27 6 5 6 28 36 6 7 4 5 5 Figure 1: A map of the test-bed. Each circle is a node; the large number is the node ID, and the superscript indicates which floor of the building the node is on. ments show that ETX improves the throughput of multi-hop routes by up to a factor of two over a minimum hop-count metric. ETX provides the most improvement for paths with two or more hops, suggesting that transmission count offers increased benefit as net￾works grow larger and paths become longer. This paper makes the following main contributions. First, it ex￾plores the details of the performance of minimum hop-count rout￾ing on a wireless test-bed, and explains why minimum hop-count often finds routes with significantly less throughput than the best available. Second, it presents the design, implementation, and eval￾uation of the ETX metric. Third, it describes a set of detailed design changes to the DSDV [25] and DSR [15] protocols (to which ETX is an extension), that enable them to more accurately choose routes with the best metric. This work is part of an effort to deploy a production-quality multi-hop rooftop 802.11b network. The initial version of that net￾work was almost unusable due to the effects detailed in Section 2. The larger goal of this work is to help make such networks a prac￾tical reality. The paper proceeds in Section 2 with an analysis of the problems with minimum hop-count routing. Section 3 describes the design of the new ETX metric, and Section 4 describes how ETX is imple￾mented, including changes to DSDV and DSR. Section 5 evaluates ETX using experiments on the test-bed. Section 6 describes related work, and Section 7 concludes the paper. 2. Performance of Minimum-Hop-Count Routing This section shows that minimum hop-count routing typically finds routes with significantly lower throughput than the best avail￾able. The evidence comes from measurements of DSDV on a test￾bed network. We explain why minimum hop-count does poorly by looking at the distribution of route throughputs and link loss ratios. 2.1 Experimental Test-Bed All the data in this paper are the result of measurements taken on a 29-node wireless test-bed. Each node consists of a stationary Linux PC with a Cisco/Aironet 340 PCI 802.11b card and an omni￾directional 2.2 dBi dipole antenna (a “rubber duck”). The nodes are placed in offices on five consecutive floors of an office building. Their positions are shown in Figure 1. The 802.11b cards are configured to send at one megabit per sec￾ond (Mbps) with one milliwatt (mW) of transmit power. RTS/CTS is turned off, and the cards are set to “ad hoc” (IBSS, DCF) mode. Each data packet in the following measurements consists of 24 bytes of 802.11b preamble, 31 bytes of 802.11b and Ethernet en￾capsulation header, 134 bytes of data payload, and 4 bytes of frame check sequence: 193 bytes in total. An 802.11b ACK packet takes 304 microseconds to transmit, the inter-frame gap is 60 microsec￾onds, and the minimum expected mandatory back-off time is 310 microseconds, resulting in a total time of 2,218 microseconds per data packet. This gives a maximum throughput of 451 unicast pack￾ets per second over a loss-free link. While the test-bed itself carried only the data and control traffic involved in each experiment, interference of various kinds was in￾evitably present. In particular, each floor of the building has four 802.11b access points, on various different channels. The DSDV implementation used in this paper is new, with mod￾ifications described in Section 4. 2.2 Path Throughputs Figure 2 compares the throughput of routes found with a min￾imum hop-count metric to the throughput of the best routes that could be found. Each curve shows the throughput CDF (in pack￾ets per second) for 100 node pairs; the pairs are randomly selected from the 29×28 = 812 total ordered pairs in the test-bed. A point’s x value indicates throughput, in packets per second; the y value in￾dicates what fraction of pairs had less throughput. The left curve is the throughput CDF achieved by routing data using DSDV with the minimum hop-count metric. The right curve is the throughput CDF for the best known route between each pair of nodes. Packets were only sent between one pair at a time. For each pair, the DSDV and best-path tests were run immediately after one another, to limit variation in link conditions over time. The “best” path between each pair of nodes was found by send￾ing data along ten potential best paths, one at a time, and select￾ing the path with the highest throughput. Potential best paths were identified by running an off-line routing algorithm, using as input measurements of per-link loss ratios, similar to those in Section 2.4

Run RI: I mw, 134-byte packets Run R1: I mw, 134-byte packets 9200 150Mm3理 0.6 0 0.2 Figure 3: Throughput available between one pair of nodes, 23 36, tested. The shortest of the Best static route DSDV hopcount routes does not perform the best, and there are a number of 0 routes with the same number of hops that provide very differ- 50100150200250300350400450 ent thr Packets per second delivere about 100 packets per second. The minimum hop-count routes are igure 2: When using the minimum hop-count metric, DSDy slow because they include links with high loss ratios, which cause chooses paths with far less throughput than the best availabl bandwidth to be consumed by retransmissions domly selected node pairs. The left curve is the throughput 2.3 Distribution of Path Throughputs Figure 3 illustrates a typical case in which minimum hop-count the CDF of the best throughput between each pair, found by routing would not favor the highest-throughput route. The through trying a number of promising paths. The dotted vertical lines put of eight routes from node 23 to node 36 is shown. The routes mark the theoretical maximum throughput of routes of each are the eight best which were tested in the experiments described The graph shows that the shortest path, a two-hop route through de 19, does not yield the highest throughput. The best route and with a penalty to reflect the reduction in throughput caused by is three hops long, but there are a number of available three-hop interference between successive hops of multi-hop paths. New link routes which provide widely varying performance measurements were collected roughly every hour during the exper- A routing protocol that selects randomly from the shortest hop- lent; the best paths for each pair were generated using the most count routes is unlikely to make the best choice, particularly as the recently available loss data network grows and the number of possible paths between a given The values in Figure 2 are split into two main ranges, above and below 225 packets per second. The values above 225 correspond to pairs that communicated along single-hop paths; those at or below 2. 4 Distribution of link Loss ratios 225 correspond to multi-hop paths. A single-hop direct route can deliver up to about 450 packets per second, but the fastest two-hop fi nd. Each vertical bar corresponds to the direct radio link between route has only half that capacity. The halving is due to transmis a pair of nodes; the two ends of the bar mark the broadcast packet sions on the successive hops interfering with each other: the middle delivery ratio in the two directions between the nodes. To measure node cannot receive a packet from the fi rst node at the same time delivery ratios, each node took a turn sending a series of broadcast it is sending a packet to the fi nal node. Similar effects cause the packets for fi ve seconds, and counted the number of packets that fastest three-hop route to have a capacity of about 450/3= 150 the 802. 11b hardware reported as transmitted. Packets contained 134 bytes of 802 1 1b data payload. Every other node recorded the Minimum hop-count performs well whenever the shortest route number of packets received. The delivery ratio from node X to each is also the fastest route, especially when there is a one-hop link with node y is calculated by dividing the number of packets received by a low loss ratio. A one-hop link with a loss ratio of less than 50% y by the number sent by X. The loss ratio of a link is one minus will outperform any other route. This is the case for all the points its delivery ratio. We use the term"ratio"instead of"rate" to avoid in the right half of Figure 2. Note that the overhead of DSDV route confusion with throughput delivery rates, which are expressed in advertisements reduces the maximum link capacity by about 15 to 5 packets per second, which is clearly visible in this part of the Note that 802. 11b broadcasts don't involve acknowledgements graph. or retransmissions. Because 802 1 1b retransmits lost unicast pack- The left half of the graph shows what happens when minimum ets, the unicast packet loss ratio as seen by higher layers is far lower hop-count has a choice among a number of multi-hop routes. In than the underlying loss ratio( depending on the maximum number these cases, the hop-count metric usually picks a route signifi cantly of retransmissions allowed slower than the best known. The most extreme cases are the poin ee features of Figure 4 are important. First, a large fraction at the far left, in which minimum hop-count is getting a through- of the links have an intermediate delivery ratio in at least one di- put close to zero, and the best known route has a throughput of rection. That is, they are likely to deliver some routing protocol

0 0.2 0.4 0.6 0.8 1 0 50 100 150 200 250 300 350 400 450 Cumulative fraction of node pairs Packets per second delivered Run R1: 1 mW, 134-byte packets Max 4-hop throughput 3-hop 2-hop Best static route DSDV hopcount Figure 2: When using the minimum hop-count metric, DSDV chooses paths with far less throughput than the best available routes. Each line is a throughput CDF for the same 100 ran￾domly selected node pairs. The left curve is the throughput CDF of DSDV with minimum hop-count. The right curve is the CDF of the best throughput between each pair, found by trying a number of promising paths. The dotted vertical lines mark the theoretical maximum throughput of routes of each hop-count. and with a penalty to reflect the reduction in throughput caused by interference between successive hops of multi-hop paths. New link measurements were collected roughly every hour during the exper￾iment; the best paths for each pair were generated using the most recently available loss data. The values in Figure 2 are split into two main ranges, above and below 225 packets per second. The values above 225 correspond to pairs that communicated along single-hop paths; those at or below 225 correspond to multi-hop paths. A single-hop direct route can deliver up to about 450 packets per second, but the fastest two-hop route has only half that capacity. The halving is due to transmis￾sions on the successive hops interfering with each other: the middle node cannot receive a packet from the first node at the same time it is sending a packet to the final node. Similar effects cause the fastest three-hop route to have a capacity of about 450/3 = 150 packets per second. Minimum hop-count performs well whenever the shortest route is also the fastest route, especially when there is a one-hop link with a low loss ratio. A one-hop link with a loss ratio of less than 50% will outperform any other route. This is the case for all the points in the right half of Figure 2. Note that the overhead of DSDV route advertisements reduces the maximum link capacity by about 15 to 25 packets per second, which is clearly visible in this part of the graph. The left half of the graph shows what happens when minimum hop-count has a choice among a number of multi-hop routes. In these cases, the hop-count metric usually picks a route significantly slower than the best known. The most extreme cases are the points at the far left, in which minimum hop-count is getting a through￾put close to zero, and the best known route has a throughput of 0 50 100 150 200 23-19-24-36 23-37-24-36 23-37-19-36 23-12-19-36 23-19-11-36 23-19-36 23-19-20-36 23-19-7-36 Packets per second delivered Run R1: 1 mW, 134-byte packets Max 3-hop throughput Max 4-hop Figure 3: Throughput available between one pair of nodes, 23 and 36, along the best eight routes tested. The shortest of the routes does not perform the best, and there are a number of routes with the same number of hops that provide very differ￾ent throughput. about 100 packets per second. The minimum hop-count routes are slow because they include links with high loss ratios, which cause bandwidth to be consumed by retransmissions. 2.3 Distribution of Path Throughputs Figure 3 illustrates a typical case in which minimum hop-count routing would not favor the highest-throughput route. The through￾put of eight routes from node 23 to node 36 is shown. The routes are the eight best which were tested in the experiments described above. The graph shows that the shortest path, a two-hop route through node 19, does not yield the highest throughput. The best route is three hops long, but there are a number of available three-hop routes which provide widely varying performance. A routing protocol that selects randomly from the shortest hop￾count routes is unlikely to make the best choice, particularly as the network grows and the number of possible paths between a given pair increases. 2.4 Distribution of Link Loss Ratios Figure 4 helps explain why high-throughput paths are difficult to find. Each vertical bar corresponds to the direct radio link between a pair of nodes; the two ends of the bar mark the broadcast packet delivery ratio in the two directions between the nodes. To measure delivery ratios, each node took a turn sending a series of broadcast packets for five seconds, and counted the number of packets that the 802.11b hardware reported as transmitted. Packets contained 134 bytes of 802.11b data payload. Every other node recorded the number of packets received. The delivery ratio from node X to each node Y is calculated by dividing the number of packets received by Y by the number sent by X. The loss ratio of a link is one minus its delivery ratio. We use the term “ratio” instead of “rate” to avoid confusion with throughput delivery rates, which are expressed in packets per second. Note that 802.11b broadcasts don’t involve acknowledgements or retransmissions. Because 802.11b retransmits lost unicast pack￾ets, the unicast packet loss ratio as seen by higher layers is far lower than the underlying loss ratio (depending on the maximum number of retransmissions allowed). Three features of Figure 4 are important. First, a large fraction of the links have an intermediate delivery ratio in at least one di￾rection. That is, they are likely to deliver some routing protocol

(a) Pairwise delivery ratios at 1 mw 型0.75 0.5 0.25 200 400 Link number (b) Pairwise delivery ratios at 30 mW 0.75 025 200 300 400 Link number Figure 4: One-hop packet delivery ratios between each pair of hosts at I mw(above)and 30 mw(below). The top and bottom ends of each vertical line indicate the delivery ratios in the two directions; the bars in each graph are sorted by the minimum of the two directions, so the link numbers do not necessarily correspond. The packet size is 134 bytes of 802. 1lb data payload. Data for all 406 rs of hosts are shown. Many links are asymmetric and there is a wide range of loss ratios. ts, but would lose many packets if used for data. Second twice the throughput. The same objection applies to is a full spectrur delivery ratios, so some ful throughput of a paths bottleneck(highest-loss-ratio) link as the be expected from fi ne-grained choices betw ath's metric. ETX. however addresses each of these concerns when choosing paths any links have asymmetri End-to-end delay is another potential metric, but changes with network load as interface queue lengths vary; this can cause routes Of the 406 node pairs in Figure 4a(I mW), there are 124 with to oscillate away from a good path once the path is used. Our goal is links which delivered packets in at least one direction. Of those to design a metric that is independent of network load; load balanc- links, 28 are asymmetric, with forward and reverse delivery ratios ing can be performed with separate algorithms that use the infor- that differ by at least 25%. The 28 asymmetric links involve 22 mation provided by EtX. We have implemented ETX as a metric different nodes Because 802. 11b uses link-level ACKs to confi rm for the DSDV and DSR routing protocols delivery, both directions of a link must work well in order to avoid retransmissions. Since most nodes in the network are involved in at 3.1 The metric least one asymmetric link, routing protocols must cope with asym- The ETX of a link is the predicted number of data transmissions metry to be effective equired to send a packet over that link, including retransr The etX of a route is the sum of the etx for each lin 3. ETX Metric desig route. For example, the eTX of a three-hop route with perfe This section describes the design of the etx metric. The met is three, the eTX of a one-hop route with a 50% delivery ratio is goal is to choose routes with high end-to-end through- two rIc s 2 suggests that the metric must account for the follow- The EtX of a link is calculated using the forward and reverse delivery ratios of the link. The forward delivery ratio, d, is the measured probability that a data packet successfully arrives at the recipient; the reverse delivery ratio, dr, is the probability that the ACK packet is successfully received. These delivery ratios can The existence of links with asymmetric loss ratios. be measured as described below. The expected probability that a transmission is successfully received and acknowledged is d x dr The interference between successive hops of multi-hop paths. A sender will retransmit a packet that is not successfully acknowl- A number of superfi cially attractive metrics are not suitable. Us- edged. Because each attempt to transmit a packet can be considered ng hop-count as the metric while ignoring links with loss ratios a Bernoulli trial, the expected number of transmissions is above a certain threshold may cause some destinations to be un reachable. Using the product of the per-link delivery ratios as the path metric, in an attempt to maximize the end-to-end delivery probability, fails to account for inter-hop interference, this metric would view a perfect two-hop route as better than a one-hop route with a 10% loss ratio. when in fact the latter would have almost

0 0.25 0.5 0.75 1 0 100 200 300 400 Delivery Ratio Link number (b) Pairwise delivery ratios at 30 mW 0 0.25 0.5 0.75 1 0 100 200 300 400 Delivery Ratio Link number (a) Pairwise delivery ratios at 1 mW Figure 4: One-hop packet delivery ratios between each pair of hosts at 1 mW (above) and 30 mW (below). The top and bottom ends of each vertical line indicate the delivery ratios in the two directions; the bars in each graph are sorted by the minimum of the two directions, so the link numbers do not necessarily correspond. The packet size is 134 bytes of 802.11b data payload. Data for all 406 pairs of hosts are shown. Many links are asymmetric, and there is a wide range of loss ratios. packets, but would lose many packets if used for data. Second, there is a full spectrum of link delivery ratios, so some advantage can be expected from making fine-grained choices between links when choosing paths. Third, many links have asymmetric delivery ratios. Of the 406 node pairs in Figure 4a (1 mW), there are 124 with links which delivered packets in at least one direction. Of those links, 28 are asymmetric, with forward and reverse delivery ratios that differ by at least 25%. The 28 asymmetric links involve 22 different nodes. Because 802.11b uses link-level ACKs to confirm delivery, both directions of a link must work well in order to avoid retransmissions. Since most nodes in the network are involved in at least one asymmetric link, routing protocols must cope with asym￾metry to be effective. 3. ETX Metric Design This section describes the design of the ETX metric. The met￾ric’s overall goal is to choose routes with high end-to-end through￾put. Section 2 suggests that the metric must account for the follow￾ing issues: • The wide range of link loss ratios. • The existence of links with asymmetric loss ratios. • The interference between successive hops of multi-hop paths. A number of superficially attractive metrics are not suitable. Us￾ing hop-count as the metric while ignoring links with loss ratios above a certain threshold may cause some destinations to be un￾reachable. Using the product of the per-link delivery ratios as the path metric, in an attempt to maximize the end-to-end delivery probability, fails to account for inter-hop interference; this metric would view a perfect two-hop route as better than a one-hop route with a 10% loss ratio, when in fact the latter would have almost twice the throughput. The same objection applies to using the use￾ful throughput of a path’s bottleneck (highest-loss-ratio) link as the path’s metric. ETX, however, addresses each of these concerns. End-to-end delay is another potential metric, but changes with network load as interface queue lengths vary; this can cause routes to oscillate away from a good path once the path is used. Our goal is to design a metric that is independent of network load; load balanc￾ing can be performed with separate algorithms that use the infor￾mation provided by ETX. We have implemented ETX as a metric for the DSDV and DSR routing protocols. 3.1 The Metric The ETX of a link is the predicted number of data transmissions required to send a packet over that link, including retransmissions. The ETX of a route is the sum of the ETX for each link in the route. For example, the ETX of a three-hop route with perfect links is three; the ETX of a one-hop route with a 50% delivery ratio is two. The ETX of a link is calculated using the forward and reverse delivery ratios of the link. The forward delivery ratio, df , is the measured probability that a data packet successfully arrives at the recipient; the reverse delivery ratio, dr, is the probability that the ACK packet is successfully received. These delivery ratios can be measured as described below. The expected probability that a transmission is successfully received and acknowledged is df × dr. A sender will retransmit a packet that is not successfully acknowl￾edged. Because each attempt to transmit a packet can be considered a Bernoulli trial, the expected number of transmissions is: ETX = 1 df × dr (1)

ETX has several important characteristics its probes, causing its neighbors to believe that the reverse delivery ratio had become zero ETX is based on delivery ratios, which directly afect through- If the highest-throughput path has three or fewer hops, ETX is likely to choose it: the throughput of such paths is determined by the total number of transmissions, since all of the hops interfere ETX detects and appropriately handles asymmetry by incor- with each other[20]. If the best path has four or more hops, ETX porating loss ratios in each direction may choose a slower path that has fewer hops, since the increased ETX can use precise link loss ratio measurements to make number of transmissions required by extra hops does not slow down fi ne-grained decisions between routes etX does not specifi cally account for mobility. eTX may choose ETX penalizes routes with more hops, which have lower good paths despite mobility if the underlying routing protocol can throughput due to interference between different hops of the propagate route metrics quickly enough, and if accurate link mea- ame path[20] surements are available. There is a tradeoff between the accuracy of ETX tends to minimize spectrum use, which should maxi- link measurements and the protocols responsiveness to mobility mize overall system capacity. 4. Implementation In addition, ETX may decrease the energy consumed per packet The routing system in which ETX is implemented has four main as each transmission or retransmission may increase a nodes arts:the Click toolkit [19], and Click-based implementations of ergy consumption. DSDV, DSR, and the etX link measurement algorithms. The im- The delivery ratios d and dr are measured using dedicated link plement can run in user-space, but running in the kernel al- probe packets. Each node broadcasts link probes of a fi xed size n, ows use of the prion failure notifi cation from the 802.11 MAC queuing described below, as well as easy accidental synchronization, T is jittered by up to +0. lT per probe. css to transmissio n average period T(one second in the implementation). To avoid acces Because the probes are broadcast, 802 1 1b does not acknowledge The dsDV protocol is implemented following the description or retransmit them. Every node remembers the probes it receives by Perkins and bhagwat [25 th ambiguities resolved by con- during the last w seconds(ten seconds in our implementation), al sulting Broch et al. 5] and the rice/CMU implementation in the lowing it to calculate the delivery ratio from the sender at any time ns simulator [1, 27]. The DSR implementation follows the Iete Internet-Draft, version 9[161 r(o=count(I-w, t) 4.1 Operation of DSDV DSDV is a distance-vector protocol, which uses sequence num- bers to ensure freshness, and a settling time mechanism to avoid Count(t-w, n)is the number of probes received during the win- unnecessarily propagating routes with inferior metrics. We made dow w, and w/r is the number of probes that should have been four changes to the original dSDv design in order to ensure that it received. In the case of the link X-Y, this technique allows X uses the path with the best known metric. Before describing those to measure dr, and y to measure d/. Because y knows it should changes, we present an overview of how the published version of receive a probe from X every T seconds, y can correctly calculate the protocol selects routes the current loss ratio even if no probes arrive from X Every node has a routing table entry for each destination it knows Calculation of a link's ETX requires both dy and dr. Each probe about. This entry contains four fi elds: the destinations identifi er sent by a node X contains the number of probe packets received by (IP address), the next hop on the route to that destination, the latest X from each of its neighbors during the last w seconds. This allow sequence number heard for that destination, and the metric. A node each neighbor to calculate the d to x whenever it receives a probe forwards packets to the next hop specifi ed by the current contents rom x of its routing table The etX of a route is the sum of the link metrics. dSR and Every node periodically broadcasts a route advertisement packet DSDV accumulate the route metric as they forward updates and containing its complete routing table. This advertisement is known queries, respectively. a full dump, and occurs at the full dump period 3.2 Discussion Each node maintains a sequence number for itse elf which it incre- ments and includes in its own entry in every full dump it originates ETX makes at least two assumptions about the link layer. First, The node copies the sequence numbers for the other entries in the ETX only makes sense for networks with link-layer retransmis full dump from its routing table. The effect is that the sequence sion, such as 802. 11b. Second, ETX assumes that radios have a number fi eld in a routing table entry or advertisement entry reflects fi xed transmit power level. With variable power radios, it might be the age of that entry's routing information preferable to maximize hop-count, thereby decreasing interference When a node receives another node's route advertisement broad- and minimizing the energy used by each packet [29, 12, 18 cast, it updates its own route entries as follows. Suppose node X etX does not attempt to route around congested links, and thus receives an advertisement from y for destination D with metric m should not suffer from the oscillations that sometimes plague load and sequence number n. If n is newer than the sequence number adaptive routing metrics such as end-to-end delay. To a first Xs current entry for D, X replaces its current entry with the proximation, the loss measurements used by etx do not reflect new route through Y. X also accepts the new route if the sequence how busy a link is, a busy link may cause a probe broadcast to be number is the same, but m is better than the metric of the current deferred, but won t ordinarily cause it to be lost. This won't always route. If X has no route to D, it accepts the new route. Otherwise X be true. however since 802.1 1b broadcasts are vulnerable to coll ignores the advertised rout sions from hidden terminals and the 802.1 lb mac can be unfair Each route entry has an associated weighted seling time (Wst) under high load [4]. As a result, a node might never be able to send The settling time of a route entry with a given sequence number is

ETX has several important characteristics: • ETX is based on delivery ratios, which directly affect through￾put. • ETX detects and appropriately handles asymmetry by incor￾porating loss ratios in each direction. • ETX can use precise link loss ratio measurements to make fine-grained decisions between routes. • ETX penalizes routes with more hops, which have lower throughput due to interference between different hops of the same path [20]. • ETX tends to minimize spectrum use, which should maxi￾mize overall system capacity. In addition, ETX may decrease the energy consumed per packet, as each transmission or retransmission may increase a node’s en￾ergy consumption. The delivery ratios df and dr are measured using dedicated link probe packets. Each node broadcasts link probes of a fixed size, at an average period τ (one second in the implementation). To avoid accidental synchronization, τ is jittered by up to ±0.1τ per probe. Because the probes are broadcast, 802.11b does not acknowledge or retransmit them. Every node remembers the probes it receives during the last w seconds (ten seconds in our implementation), al￾lowing it to calculate the delivery ratio from the sender at any time t as: r(t) = count(t − w, t) w/τ Count(t − w, t) is the number of probes received during the win￾dow w, and w/τ is the number of probes that should have been received. In the case of the link X → Y , this technique allows X to measure dr, and Y to measure df . Because Y knows it should receive a probe from X every τ seconds, Y can correctly calculate the current loss ratio even if no probes arrive from X. Calculation of a link’s ETX requires both df and dr. Each probe sent by a node X contains the number of probe packets received by X from each of its neighbors during the last w seconds. This allows each neighbor to calculate the df to X whenever it receives a probe from X. The ETX of a route is the sum of the link metrics. DSR and DSDV accumulate the route metric as they forward updates and queries, respectively. 3.2 Discussion ETX makes at least two assumptions about the link layer. First, ETX only makes sense for networks with link-layer retransmis￾sion, such as 802.11b. Second, ETX assumes that radios have a fixed transmit power level. With variable power radios, it might be preferable to maximize hop-count, thereby decreasing interference and minimizing the energy used by each packet [29, 12, 18]. ETX does not attempt to route around congested links, and thus should not suffer from the oscillations that sometimes plague load￾adaptive routing metrics such as end-to-end delay. To a first ap￾proximation, the loss measurements used by ETX do not reflect how busy a link is; a busy link may cause a probe broadcast to be deferred, but won’t ordinarily cause it to be lost. This won’t always be true, however, since 802.11b broadcasts are vulnerable to colli￾sions from hidden terminals, and the 802.11b MAC can be unfair under high load [4]. As a result, a node might never be able to send its probes, causing its neighbors to believe that the reverse delivery ratio had become zero. If the highest-throughput path has three or fewer hops, ETX is likely to choose it: the throughput of such paths is determined by the total number of transmissions, since all of the hops interfere with each other [20]. If the best path has four or more hops, ETX may choose a slower path that has fewer hops, since the increased number of transmissions required by extra hops does not slow down throughput beyond three hops. ETX does not specifically account for mobility. ETX may choose good paths despite mobility if the underlying routing protocol can propagate route metrics quickly enough, and if accurate link mea￾surements are available. There is a tradeoff between the accuracy of link measurements and the protocol’s responsiveness to mobility. 4. Implementation The routing system in which ETX is implemented has four main parts: the Click toolkit [19], and Click-based implementations of DSDV, DSR, and the ETX link measurement algorithms. The im￾plementations can run in user-space, but running in the kernel al￾lows use of the priority queuing described below, as well as easy access to transmission failure notification from the 802.11 MAC layer. The DSDV protocol is implemented following the description by Perkins and Bhagwat [25], with ambiguities resolved by con￾sulting Broch et al. [5] and the Rice/CMU implementation in the ns simulator [1, 27]. The DSR implementation follows the IETF Internet-Draft, version 9 [16]. 4.1 Operation of DSDV DSDV is a distance-vector protocol, which uses sequence num￾bers to ensure freshness, and a settling time mechanism to avoid unnecessarily propagating routes with inferior metrics. We made four changes to the original DSDV design in order to ensure that it uses the path with the best known metric. Before describing those changes, we present an overview of how the published version of the protocol selects routes. Every node has a routing table entry for each destination it knows about. This entry contains four fields: the destination’s identifier (IP address), the next hop on the route to that destination, the latest sequence number heard for that destination, and the metric. A node forwards packets to the next hop specified by the current contents of its routing table. Every node periodically broadcasts a route advertisement packet containing its complete routing table. This advertisement is known as a full dump, and occurs at the full dump period. Each node maintains a sequence number for itself, which it incre￾ments and includes in its own entry in every full dump it originates. The node copies the sequence numbers for the other entries in the full dump from its routing table. The effect is that the sequence number field in a routing table entry or advertisement entry reflects the age of that entry’s routing information. When a node receives another node’s route advertisement broad￾cast, it updates its own route entries as follows. Suppose node X receives an advertisement from Y for destination D with metric m and sequence number n. If n is newer than the sequence number in X’s current entry for D, X replaces its current entry with the new route through Y . X also accepts the new route if the sequence number is the same, but m is better than the metric of the current route. If X has no route to D, it accepts the new route. Otherwise X ignores the advertised route. Each route entry has an associated weighted settling time (WST). The settling time of a route entry with a given sequence number is