A. Balasubramanian, R. Mahajan, A. Venkataramani, B. N. Levine, J. Zahorjan, “Interactive WiFi Connectivity For Moving Vehicles”, ACM SIGCOMM Conference, (August 2008). [PDF]

Summary

Current WiFi handoff methods, where a client remains connected to a single basestation (BS), lead to frequent disruptions in connectivity in highly mobile vehicular networks. This paper proposes ViFi, a protocol that opportunistically exploits BS diversity to minimize disruptions and can support interactive applications (e.g., Web browsing, VoIP). ViFi opportunistically connects a mobile client device to multiple BSes, and coordinates between those BSes using a distributed and lightweight probabilistic algorithm, to obviate hard handoffs.

Observations

The authors performed experiments on two testbeds (VanLan and DieselNet) with 6 handoff protocols (practical as well as optimal) to come up with the following conclusions that led to the ViFi design:

• With a reasonable density BS deployment, a vehicle is often in range of multiple BSes. Existing handoff mechanisms do not take advantage of this property.
• Packet loss, in each vehicle-BS connection, is independent and bursty. A BS that failed to receive something is more likely to fail in close temporal proximity than another BS which also overheard the same transmission.

ViFi Design

In its core, ViFi allows overhearing BSes to carry on a transmission towards the destination even though the intended BS failed to receive or acknowledge it. The main challenge here is to coordinate between BSes with minimal overhead and latency and with little to no disruption as BS set changes. To this end, ViFi designates one of the BS as the anchor and the rest as auxiliary BSes within the range of the sender based on some metric. Through periodic Beacons from the vehicle, BSes get to know each other (who is anchor etc.) as well as the sender vehicle. The operations of ViFi is symmetric in both directions (src and dst) and given in the following:

1. src transmits the packet P.
2. If dst receives P, it broadcasts an ACK.
3. If an auxiliary BS hears P but not the ACK within a time period, it probabilistically relays P. (Note: Relaying takes place in the inter-BS backplane)
4. If dst receives relayed P and yet to broadcast an ACK, it does so now.
5. src retransmits when retransmission timer goes out. (Note: Retransmission timer is adaptively set based on how fast a vehicle receive ACKs)

Probability of relaying or not relaying is computed locally in each BS based on the accumulated information from overhearing and Beacons. The invariant in this probability calculation used by the authors is that the expected number of packets relayed across all auxiliary BSes is equal to 1 (which also makes sure that a packets is relayed at most once by a BS). There can be false positives and false negatives due to the independent calculation methods, but the authors postulate that that will be very low.

ViFi also supports salvaging, i.e., whenever a vehicle moves out of the range of an anchor, the new anchor contacts the previous anchor to take care of the un-forwarded packets to the vehicle. This ensures that TCP won’t assume congestion, when there is none.

Evaluation Results

• Link layer performance of ViFi closely approximates the ideal solution in the testbeds.
• Both Web and VoIP traffic enjoys better goodput and session connectivity using ViFi. Percentage gain varies based on testbed though. Salvaging gives 10% boost, but its not very useful for VoIP.
• Medium usage/efficiency is usage is roughly the same for the increased performance.
• Coordination mechanism has low false positives than naive approaches and higher, still small, false negatives.

Critique

The whole design and concept is intriguing; but they are all based on two controlled testbeds with dense BSes and only one vehicle. What will be the overhead on the backplane or the number of signal collisions, if there are many connections going on at the same time? To give credit to the authors, previous work on opportunistic algorithms also avoided this aspect as much as possible, even in stationary scenarios.

The authors point out the possible problems with a high number of equidistant auxiliary BSes, that might increase overhead and make selection process harder (now they select all, but selecting some out of many BSes as auxiliary will intrinsically introduce more errors). Deployment of enough BSes to make ViFi perform better than others is another problem. Such dense deployment is easier in urban areas, but will be much harder elsewhere.

Some parts of the work presented and the problem itself had been present in the context of cellular networks and addressed there to some extent. The authors sporadically mention that too, but never actually go deep into discussion or comparison.  A better comparison, even if qualitative, would have been nice in the relative work section.