PaperlayerView exact revision on arXiv

Source-linked AI summary

Multirate Anypath Routing in Wireless Mesh Networks

Rafael Laufer, Leonard Kleinrock

arXiv:0809.1681v1cs.NIcs.DS

TL;DR

Wireless mesh routing lacks a theory for jointly choosing next-hop sets and transmission rates, despite rate-dependent changes in connectivity and delivery probability. The paper introduces an optimal polynomial-time multirate anypath algorithm with shortest-path running time. In an 802.11b testbed, it improves end-to-end expected transmission time over fixed-rate routing, including an 80% average and 6.4× maximum gain versus 11 Mbps.

  • Problem

    Existing anypath routing does not jointly optimize forwarding sets and transmission rates, even though higher rates alter loss probabilities, radio range, connectivity, and path diversity.

  • Method

    The paper introduces the EATT metric and a polynomial-time algorithm that generalizes Dijkstra’s algorithm and proves its optimality for shortest multirate anypath routing.

  • Results

    Multirate anypath routing improves end-to-end expected transmission time by 80% on average and up to 6.4× versus 11-Mbps single-rate routing, while maintaining connectivity.

  • Takeaways & Limitations

    Optimal rates are distributed across multiple possibilities, supporting rate selection per node rather than restricting the network to one fixed transmission rate.

Abstract

from arXiv · show

In this paper, we present a new routing paradigm that generalizes opportunistic routing in wireless mesh networks. In multirate anypath routing, each node uses both a set of next hops and a selected transmission rate to reach a destination. Using this rate, a packet is broadcast to the nodes in the set and one of them forwards the packet on to the destination. To date, there is no theory capable of jointly optimizing both the set of next hops and the transmission rate used by each node. We bridge this gap by introducing a polynomial-time algorithm to this problem and provide the proof of its optimality. The proposed algorithm runs in the same running time as regular shortest-path algorithms and is therefore suitable for deployment in link-state routing protocols. We conducted experiments in a 802.11b testbed network, and our results show that multirate anypath routing performs on average 80% and up to 6.4 times better than anypath routing with a fixed rate of 11 Mbps. If the rate is fixed at 1 Mbps instead, performance improves by up to one order of magnitude.

I. INTRODUCTION

Wireless mesh routing must handle lossy, dynamic links and the tradeoff between transmission rate, connectivity, and path diversity. The paper formulates shortest multirate anypath routing, gives an optimal polynomial-time algorithm, and evaluates its gains over fixed-rate routing.

  • I. INTRODUCTION: Anypath routing broadcasts to multiple next hops, allowing a receiver other than the poorly performing neighbor to forward the packet.Packets can follow different paths because forwarding depends on which nodes successfully receive each transmission.
  • I. INTRODUCTION: Higher transmission rates shorten radio range and increase loss, so single-rate routing can disconnect the network and must use low rates for connectivity.In the testbed, 1 Mbps was the only fixed rate yielding full connectivity among the tested rates.
  • I. INTRODUCTION: The shortest multirate anypath problem jointly selects each node’s forwarding set and transmission rate to minimize distance to a destination.The paper identifies this joint optimization as an open problem and calls its formulation the shortest multirate anypath problem.
  • I. INTRODUCTION: The proposed algorithm generalizes Dijkstra’s algorithm, proves optimality, and has the same running time as the corresponding shortest-path algorithm.This makes the approach suitable for link-state routing protocols and current wireless routers.
  • I. INTRODUCTION: 80% average and up to 6.4× improvement over 11-Mbps single-rate anypath routing while maintaining connectivity.Against 1-Mbps routing, the average gain is 5.4× and the maximum gain is 11.3×.

C. Anypath Cost

Anypath cost combines the cost of reaching a forwarding set with the expected remaining cost to the destination. Adding a neighbor can lower transmission cost yet increase downstream cost, so larger forwarding sets are not always better.

  • C. Anypath Cost: Anypath cost is the sum of hyperlink cost to a forwarding set and the forwarding set’s remaining-anypath cost.The formulation is D_i = d_iJ + D_J.
  • C. Anypath Cost: ETX assigns each link an expected transmission cost equal to the inverse of its delivery probability, while EATX extends this idea to forwarding sets.For a forwarding set J, the hyperlink distance is defined as d_iJ = 1/p_iJ.
  • C. Anypath Cost: The remaining cost of a forwarding set is a weighted average of member distances, with weights determined by each node’s probability of becoming the relay.A node relays when it receives the packet and all higher-priority, closer nodes fail to receive it.
  • C. Anypath Cost: Adding a neighbor is not always beneficial because its lower hyperlink cost can be outweighed by a higher remaining-anypath cost.The example gives D_i = 1.8 + 4.6 = 6.4 for the expanded forwarding set.
  • C. Anypath Cost: The shortest anypath has cost no greater than the shortest single path because a single path is itself a possible anypath.Figure 2 illustrates that one forwarding-set choice can have lower anypath cost than another.

III. MULTIRATE ANYPATH ROUTING

Multirate anypath routing jointly selects forwarding sets and transmission rates, accounting for rate-dependent delivery probabilities, transmission times, and connectivity. Its EATT metric extends single-rate EATX, while the resulting cost is no worse than shortest single-path or fixed-rate anypath routing.

  • Multirate Anypath Routing: Multirate anypath routing selects both a forwarding set and a potentially different transmission rate at each node, so packets may follow different paths and rates.A packet is broadcast to a node's selected neighbors, and the successful receiver forwards it toward the destination.
  • Multirate Anypath Routing: The EATT metric generalizes EATX by combining rate-dependent hyperlink transmission time with delivery probability for each available bit rate.The hyperlink distance represents transmitting a packet of size s at rate r over a lossy link with delivery probability p(r)_iJ.
  • Multirate Anypath Routing: Higher rates reduce packet transmission time but usually increase losses and shorten radio range, creating rate-specific connectivity graphs and a throughput trade-off.Lower rates provide more neighbors for forwarding-set inclusion, whereas higher rates can reduce density and connectivity.
  • Multirate Anypath Routing: The shortest multirate anypath problem minimizes each node's cost by jointly choosing its forwarding set and transmission rate.Its optimal cost is equal to or lower than both the shortest single path and any shortest anypath using one fixed transmission rate.

IV. FINDING THE SHORTEST MULTIRATE ANYPATH

The paper develops shortest-anypath algorithms that settle nodes by increasing distance and update forwarding sets from incoming edges. With suitable state maintenance, the algorithm achieves Dijkstra-equivalent complexity.

  • The Multirate Case: SMAF generalizes SAF to multiple transmission rates and has the same running time as a shortest single-path algorithm for multirate.The paper proves SMAF optimality, which also implies SAF optimality.
  • The Single-Rate Case: Figure 4 depicts SAF's initialization, successive iterations, and final state after the last node is settled, with node values showing distances and bold arrows showing shortest anypaths.Double-circled nodes are the settled set S.
  • The Single-Rate Case: SAF initializes infinite distance estimates and empty forwarding sets, then repeatedly extracts the minimum-distance unsettled node and settles it.For each incoming edge, it adds the settled node to a forwarding set and updates the predecessor's distance when beneficial.
  • Finding the Shortest Multirate Anypath: The Shortest Anypath First algorithm has complexity O(V log V + E), matching Dijkstra's algorithm when a Fibonacci heap is used.Additional state reduces the distance calculation for a forwarding-set update to constant time.

B. The Multirate Case

The multirate algorithm maintains rate-specific distance and forwarding-set estimates alongside each node's best overall estimate and selected transmission rate.

  • The Multirate Case: SMAF keeps a distance estimate D(r)_i and forwarding set F(r)_i for every node i and transmission rate r.D(r)_i upper-bounds the shortest anypath distance from i to the destination using rate r, while F(r)_i stores its next hops.
  • The Multirate Case: For each node, SMAF also stores the minimum distance across rates, its corresponding forwarding set, and the optimal transmission rate T_i.These rate-agnostic values identify the node's best multirate route to the destination.

SHORTEST-MULTIRATE-ANYPATH-FIRST(G, d)

SMAF generalizes Dijkstra’s algorithm to jointly optimize each node’s forwarding set and transmission rate, with a proof of optimality and shortest-path-level running time.

  • SHORTEST-MULTIRATE-ANYPATH-FIRST(G, d): SMAF maintains an independent distance estimate for each rate and settles the node with the minimum overall estimate, updating rate-specific forwarding sets.The minimum across rate-specific estimates becomes each node’s distance.
  • SHORTEST-MULTIRATE-ANYPATH-FIRST(G, d): Its total running time is O(V log V + ER), matching the shortest single-path algorithm for multiple rates.The bound assumes all nodes can reach the destination and uses optimized distance calculations.
  • SHORTEST-MULTIRATE-ANYPATH-FIRST(G, d): For a fixed rate, adding a neighbor with no shorter distance than the current forwarding-set members improves distance exactly when the current distance is at least that neighbor’s distance.This lemma supports the forwarding-set comparisons used by SAF and SMAF.
  • SHORTEST-MULTIRATE-ANYPATH-FIRST(G, d): At most n prefix forwarding sets need evaluation for n neighbors, reducing the search from 2^n −1 possibilities to polynomial time.The optimal set is always a prefix of neighbors ordered by shortest distance.
  • SHORTEST-MULTIRATE-ANYPATH-FIRST(G, d): The algorithm is optimal: when each node is settled, its estimated distance equals the shortest multirate anypath distance.The proof establishes that nodes are settled in ascending distance order.

V. EXPERIMENTAL RESULTS

Experiments in an 18-node 802.11b testbed show that increasing transmission rate reduces link availability and path diversity, while multirate routing exploits the resulting tradeoff across rates.

  • V. EXPERIMENTAL RESULTS: The evaluation uses an 18-node 802.11b indoor testbed with nodes arranged in an approximate 2x9 grid.The setup uses embedded Linux devices and attenuated wireless links to emulate multiple hops.
  • V. EXPERIMENTAL RESULTS: Links with delivery probability above 50% decrease from 151 at 1 Mbps to 47 at 11 Mbps, reducing path diversity as rate increases.The testbed measured delivery probabilities across 1, 2, 5.5, and 11 Mbps.
  • V. EXPERIMENTAL RESULTS: At 11 Mbps, multirate anypath routing achieves a gain up to 6.4, with an average gain of 80%, over single-rate anypath routing.The gain compares single-rate to multirate end-to-end transmission time.
  • V. EXPERIMENTAL RESULTS: At 1 Mbps, multirate anypath routing is at least 50% and up to 11.3 times shorter in end-to-end transmission time, with an average gain of 5.4.For higher fixed rates, some node pairs are disconnected, producing infinite gain.
  • V. EXPERIMENTAL RESULTS: Optimal rates vary across node pairs: 10.8% use 1 Mbps, 41% use 5.5 Mbps, and 47% use 11 Mbps, while none use 2 Mbps.The distributed choices explain why multirate and single-rate routing can have different costs.

VI. RELATED WORK

Prior anypath work largely assumes a single transmission rate, while related multirate formulations address broader optimization problems that are NP-hard. This paper instead provides an optimal multirate forwarding-set and rate-selection algorithm.

  • Prior anypath schemes generally use a single transmission rate and often select forwarding sets heuristically rather than systematically.Single-rate operation can underuse bandwidth or disconnect the network at higher rates, while ETX does not correctly represent anypath distance.
  • The paper extends optimal shortest-anypath routing to multiple rates, allowing each node to choose both a transmission rate and forwarding set.The authors also provide a proof of optimality, while prior single-rate algorithms were limited to fixed-rate networks.
  • Existing multirate opportunistic-routing formulations jointly address routing, scheduling, or rate adaptation but solve NP-hard problems using heuristics.

VII. CONCLUSIONS

The paper introduces multirate anypath routing and solves its joint rate-and-forwarding-set optimization problem with the optimal SMAF algorithm. Testbed experiments show substantial gains over fixed-rate anypath routing while preserving connectivity.

  • The paper introduces the EATT metric and SMAF algorithm, proves SMAF optimal, and gives it the same complexity as Dijkstra’s algorithm for multirate single-path routing.
  • Fixed-rate routing may disconnect the network because some links do not work at the selected rate, whereas multirate routing maintains connectivity in the reported comparison.
  • Multirate anypath routing outperforms 11-Mbps anypath routing by 80% on average and up to a factor of 6.4 while maintaining full connectivity.
  • Multirate anypath routing outperforms 1-Mbps anypath routing by a factor of 5.4 on average and up to a factor of 11.3.

APPENDIX A PROOFS OF THE LEMMAS

The appendix proves structural properties of optimal forwarding sets and uses them to justify the lemma-based shortest multirate anypath algorithm. The proofs show when forwarding-set extensions improve distance and when links are redundant.

  • Adding a neighbor with no larger distance can reduce or preserve the route distance because the remaining cost is a weighted average and the delivery cost does not increase.
  • The full neighbor set at a fixed rate yields the shortest distance among prefix forwarding sets, providing the basis for the optimal-set argument.
  • In an optimal forwarding set, every included neighbor has distance no greater than the forwarding node’s distance to the destination.
  • A neighbor is redundant when its distance equals the source node’s shortest distance, so removing that link leaves the route distance unchanged.
  • For a fixed rate, an optimal forwarding set consists of the closest neighbors in distance order, forming a prefix {1, 2, ..., k}.
Loading 0809.1681v1…