ROMER: Resilient Opportunistic Mesh Routing for Wireless Mesh Networks.

ROMER: Resilient Opportunistic Mesh Routing for Wireless Mesh Networks. Y. Yuan, H. Yang, S. Wong, S. Lu, W. Arbaugh, WiMesh workshop, IEEE SECON 2005.

This paper I saw being presented at the 1st WiMesh workshop in Santa Clara in 2005, but I just re-read it recently. I might even have chaired the session it was in. The workshop was consisting of invited papers I believe, and the chairs selected right.

Anyhow, the crux of the paper is: give a packet an amount of credit which is equal to the cost C(S) of transmission times a constant. The cost C(S) is the cost to route from the source S to the destination. At each hop, pick K relays to forward the packet, so that each relay satisfies a credit/cost, where credit is the updated credit (ie. credit minus the cost used up to this point) and cost is the remaining cost at the node to the destination.

The K relays ensure the resilience, as you have a lot of packets going forward. As for the opportunism, it comes in the form of picking the K best relays according to the current conditions, that is: among the potential candidates, pick the K ones with the hight instantaneous rate conditions.

There are some good ideas, and some stuff that I don't necessarily agree with. The credit-based system is simple, but needs nodes to have a cost to each destination, which seems a bit un-scalable. Actually, it depends on how you define the credit and the cost, as a hop-count-based cost is scalable in some situations.

The K-resiliency would seem to me a strange way to optimize the use of the air interface. For instance, the paper does not specify how the K candidates receive the packet. Is it K unicast communications? In which case it is pretty sub-optimal. If it is one broadcast, how do you indicate the K recipients. How do they acknowledge. It runs into the same issues as ExOR basically, without providing the answer.

And then, this K-relaying introduces some race conditions to compete with the channel, between the 2nd transmission of the packet to the 2nd best neighbor, and the 1st neighor transmission of the same packet, but one hop downward. Again, solutions have been proposed (staggered Acks and re-tx) but this would need to be solved explicitly before an actual implementation.

Anyway, this is an interesting read, it triggers lots of good questions and ideas. I did not expect much from the WiMesh workshop as it was a new meeting, but I now have been to the two editions, and it is pretty good everytime.