A Theory of QoS for Wireless
I-Hong Hou (University of Illinois at Urbana-Champaign, US); Vivek Borkar (Tata Institute of Fundamental Research, IN); P. R. Kumar (University of Illinois at Urbana-Champaign, US)
This paper claimed to propose a tractable and relevant framework for analyzing the quality of service in a network. In particular, the model should capture deadlines, delivery ratios, and channel reliability while providing guarantees for admission control and scheduling. The model presented was rather simple: there are clients trying to access a single access point in slotted time. The clients generate packets periodically with period and each packet has a deadline of . The channel quality is captured by a client-dependent success probability for the uplink; the downlink always succeeds. For the uplink, the access point selects a transmitter via polling and the client sends the packet until it is received. The questions are then to ask whether a set of clients and rates is feasible and what policy can achieve these rates. The paper presents an outer bound and two policies based on notion of workload , where is the delivery ratio of user . Policies based on largest “debt” first are shown to be optimal, where “debt” can be the difference of and the fraction of time given to user or a weighted delivery ratio.

Computing the Capacity Region of a Wireless Network
Ramakrishna Gummadi (University of Illinois at Urbana-Champaign, US); Kyomin Jung (Massachusetts Institute of Technology, US); Devavrat Shah (Massachusetts Institute of Technology, US); Ramavarapu Sreenivas (University of Illinois at Urbana-Champaign, US)
This looked at wireless networks under the protocol model of Gupta and Kumar and asks the following question : if I give you a vector of rates is there a way to tell if is in the capacity region of the network? Previous work had looked at polynomial time algorithms for scheduling, but apparently in the wireless setting the scheduling problem is NP hard. The question they look at instead is testing if there exists a routing scheme which leads to feasible link rates. This can be reduced to approximating “max-weight independent set” (MWIS), which I am not so familiar with. I think it relates to the backpressure algorithm. In any case, they find a polynomial time approximation assuming the communication graph has polynomial growth, which holds for many nice graphs (like random geometric graphs with standard connectivity assumptions).

The Multicast Capacity Region of Large Wireless Networks
Urs Niesen (Massachusetts Institute of Technology, US); Piyush Gupta (Bell Labs, Alcatel-Lucent, US); Devavrat Shah (Massachusetts Institute of Technology, US)
The network model is users placed uniformly in the square . This looks at the capacity region assuming arbitrary multicast demands between users. So each node in the network has a set of receivers to which it would like to multicast its message. What traffic demands are admissible? The framework is one of scaling laws as the number of nodes goes to infinity, under the protocol model and enforcing multi-hop routing. The main result is that the capacity region is equal to the cutset region within an multiplicative factor (on both the upper and lower bounds), and furthermore the cutset region can be evaluated with fewer constraints. The achievable scheme involves building a “multiresolution tree” of sorts and then showing that routing in the original problem is the same as routing in the tree. The tree structure gives the constraint reduction for the cutset bound. To actually route the traffic, they develop a “message concentration” scheme that is reminiscent of other hierarchical cooperation schemes but I guess is a bit different.