Valuable Detours: Least-Cost Anypath Routing

Valuable Detours: Least-Cost Anypath Routing

Technology Used: Dot Net


In many networks, it is less costly to transmit a packet to any node in a set of neighbors than to one specific neighbor. This observation was previously exploited by opportunistic routing protocols by using single-path routing metrics to assign to each node a group of candidate relays for a particular destination. This paper addresses the least-cost anypath routing (LCAR) problem: how to assign a set of candidate relays at each node for a given destination such that the expected cost of forwarding a packet to the destination is minimized. The key is the following tradeoff: On one hand, increasing the number of candidate relays decreases the forwarding cost, but on the other, it increases the likelihood of “veering” away from the shortest-path route. Prior proposals based on single-path routing metrics or geographic coordinates do not explicitly consider this tradeoff and, as a result, do not always make optimal choices. The LCAR algorithm and its framework are general and can be applied to a variety of networks and cost models. We show how LCAR can incorporate different aspects of underlying coordination protocols, for example a link-layer protocol that randomly selects which receiving node will forward a packet, or the possibility that multiple nodes mistakenly forward a packet. In either case, the LCAR algorithm finds the optimal choice of candidate relays that takes into account these properties of the link layer. Finally, we apply LCAR to low-power, low-rate wireless communication and introduce a new wireless link-layer technique to decrease energy transmission costs in conjunction with anypath routing. Simulations show significant reductions in transmission cost to opportunistic routing using single-path metrics. Furthermore, LCAR routes are more robust and stable than those based on single-path distances due to the integrative nature of the LCAR’s route cost metric.

5 Thoughts to “Valuable Detours: Least-Cost Anypath Routing”

  1. karthick

    send base paper for this topic in 2011…

  2. Raveendra

    pls send me the basepaper of this abstract as earky as possible
    thanking u….

  3. rakesh prajapati

    pls send me basepaper of this abstract soon

  4. bala

    send base paper for the project…

  5. Dharmveer kumar

    pls send me basepaper and detailed abstract for this title soon

Leave a Reply