Losing Opportunism: Evaluating Service Integration in an Opportunistic Wireless System. Hongseok Kim, Gustavo de Veciana, to appear in Proc. of IEEE Infocom'07.
The Infocom'07 program has been announced and you can find some of the papers here and there is you google around. I read this one, as I have been interested in opportunism and its benefit. I believe that the main function of opportunism stays in its ability to accommodate mobility: by having a flexible list of potential suitors to relay your packet, you can adapt the list to the topology dynamically. This paper somewhat pokes holes in the other benefit of opportunism: bandwidth gain.
The idea of the paper (and I will not go in the technical details, which are, unlike the intuition behind them, rather complicated) is that there is a benefit to use opportunistic mechanism, which has been quantified in a single hop, cellular-like wireless system. Basically, by picking the user with the best instantaneous condition, that user will be out-doing its average rate, and you will increase the capacity of the system. You can quantify how much this is true.
However, this comes at the cost of fairness: picking the best guy at some time, also means not picking some guy, potentially for extended periods of time. This is where Proportional Fairness for instance comes in. This is also where this paper come in, but from a different angle: it asks the question, not how to provide fairness to the users, but what if a user demands some type of service: a user with a certain level of QoS.
Users with QoS require the channel to be allocated to them whether or not a better (best effort) transmission candidate exists. The paper provides some analytical model to describe this, and some simulation results (based on their analysis). Basically, it shows that the stability region is reduced by QoS users (in the extreme, you cannot provide more than your average capacity C to a QoS user because it depends on other users being there; so if you have N channels, the capacity is CN with N QoS users, instead of the much greater capacity of an opportunistic system.
It is very intuitive that providing strict QoS requirement will cause a loss in flexibility in the choice of the node to communicate with, and thus a degradation in the performance that this flexibility provide. It is good to have an analytical framework to quantify this. I would say it is best paper award territory (based on my very partial view of the Infocom'07 paper stack).
It is particularly important to have this kind of intuition described clearly: the impact of a single QoS user is a great degradation in the system performance. One application of wireless mesh networks is to replace broadband services and to provide VoIP over these networks (say as a way for a city to repay the wireless network investment by switching its phone bill away from cellular operator to VoIP over the handset). Well, if your scheduling algorithm in the backhaul uses some similar kind of opportunism, the effect this paper describes starts to kick in: either you have higher priority to your VoIP flows, and then you lose the opportunistic effect; or you don't, and then you do get unreliable performance for your VoIP call. It boils down to a network design issue, but seems to say that you cannot put opportunism gain in the bank too much. Something to keep in mind.