We present a user modeling system that serves as the foundation of a personal assistant. The system ingests web search history for signed-in users, and identifies coherent contexts that correspond to tasks, interests, and habits. Unlike past work which focused on either in-session tasks or tasks over a few days, we look at several months of history in order to identify not just short-term tasks, but also long-term interests and habits. The features we use for identifying coherent contexts yield substantially higher precision and recall than past work. We also present an algorithm for identifying contexts that is 8 to 30 times faster than previous algorithms. The user modeling system has been deployed in production. It runs over hundreds of millions of users, and updates the models with a 10-minute latency. The contexts identified by the system serve as the foundation for generating recommendations in Google Now.

Routing protocols for multihop wireless networks have traditionally used shortest path routing to obtain paths to destinations and do not consider traffic load or delay as an explicit factor in the choice of routes. We focus on static mesh networks and formally establish that if the number of sources is not too large, then it is possible to construct a perfect flow-avoiding routing, which can boost the throughput provided to each user over that of the shortest path routing by a factor of four when carrier sensing can be disabled or a factor of 3.2 otherwise. So motivated, we address the issue of designing a multipath, load adaptive routing protocol that is generally applicable even when there are more sources. We develop a protocol that adaptively equalizes the mean delay along all utilized routes from a source to destination and does not utilize any routes that have greater mean delay. This is the property satisfied by a system in Wardrop equilibrium. We also address the architectural challenges confronted in the software implementation of a multipath, delay-feedback-based, probabilistic routing algorithm. Our routing protocol is 1) completely distributed, 2) automatically load balances flows, 3) uses multiple paths whenever beneficial, 4) guarantees loop-free paths at every time instant even while the algorithm is suntil converging, and 5) amenable to clean implementation. An ns-2 simulation study indicates that the protocol is able to automatically route flows to "avoid" each other, consistently out-performing shortest path protocols in a variety of scenarios. The protocol has been implemented in user space with a small amount of forwarding mechanism in a modified Linux 2.4.20 kernel. Finally, we discuss a proof-of-concept measurement study of the implementation on a six node testbed.

Motivated by the increasing usage of wireless broadcast networks for multicast real-time applications like video, this paper considers a canonical real-time multicast scheduling problem for a wireless broadcast LAN. A wireless access point (AP) has N latency-sensitive flows, each associated with a deadline and a multicast group of receivers that desire to receive all the packets successfully by their corresponding deadlines. We consider periodic and one-shot models of real-time arrivals. The channel from the AP to each receiver is a wireless erasure channel, independent across users and slots. We wish to find a communication strategy that minimizes the total deadlines missed across all receivers, where a receiver counts a miss if it does not receive a packet by its deadline. We cast this problem as a restless bandit in stochastic control. We use Whittle's relaxation framework for restless bandits to establish Whittle-indexability for multicast realtime scheduling under the assumption of complete feedback from all receivers in every slot. For the Whittle relaxation, we show that for each flow, the AP's decision between transmitting in a slot and idling has a threshold structure. For the homogeneous case where the erasure channel to each receiver is identically distributed with parameter p, the Whittle index of a flow is xi(1 - p) , where xiis the number of receivers who have yet to receive the current packet of flow i. For the general heterogeneous case in which the erasure channel to receiver j has loss probability pj, the Whittle index corresponding to each flow is Sigmaj(1- pj), where the sum is over all multicast receivers who are yet to receive the packet. We bound the performance of the optimal Whittle relaxation with respect to the optimal wireless multicast real-time scheduler. The heuristic index policy that schedules the flow with the maximum Whittle index in each slot is simple. To relax the complete feedback assumption, we design a scalable mechanism based on statistical estimation theory that obtains the required feedback from all the receivers using a single ACK per packet transmission. The resultant policy is amenable to low-complexity implementation.

Wireless networks are increasingly being used for latency-sensitive applications that require data delivery to be timely, efficient and reliable. This trend is primarily driven by the proliferation of wireless networks of real-time data-gathering sensor-actuator devices. This has led to a strong need to bring real-time concerns to the forefront of an integrated research thrust into wireless real-time systems. In this paper, we introduce and analyze a specific instance of the rich set of problems in this domain. We consider a wireless network serving real-time flows in which the underlying physical layer provides multiple transmission rates. Higher rates have more stringent SINR requirements and thus represent a trade-off between raw transmission speed and packet error rate. We adopt a first principles approach to the design of optimal real-time scheduling algorithms for such a multi-rate wireless network. We illustrate the inherent complexities of the problem through examples and obtain provably optimal structural results. We then characterize the optimal policy for an approximate model. Our theoretical analysis provides guidelines for heuristic scheduler design. Our initial work indicates that this is a rich problem domain with the potential for a unifying theory that integrates real-time requirements into multi-rate wireless network design.

The conventional function of the medium access control (MAC) layer in wireless networks is interference management. We show how the MAC can also be used to mitigate the effect of fading. We begin by providing experimental data to demonstrate that multipath fading effects are seen at the MAC layer. These effects appear at timescales on the same order of the IEEE 802.11 protocol and therefore, interact negatively with the RTS-CTS-DATA-ACK handshake. We identify two types of MAC diversities to jointly combat fading and interference, called multi-receiver diversity and multi-channel diversity respectively, through canonical scenarios. In order to harness these MAC layer diversities, we propose a simple dynamic-binding multichannel MAC (DB-MCMAC) protocol that is backward compatible with IEEE 802.11. DB-MCMAC exploits MAC diversities by opportunistically acquiring the floor for the best receiver on each channel, and dynamically binding data transmissions after the floor has been acquired. We employ a simple continuous time Markov chain model to analyze the expected performance of the DB-MCMAC protocol. A comprehensive performance evaluation of DB-MCMAC using ns-2 shows that it can successfully harness multi-receiver and multi-channel fading and interference diversities to provide considerable improvements over a baseline multi-channel MAC in several situations.

One of the triumphs of wireline network research of the last decade has been the casting of the Internet congestion control problem within an optimization framework based on utility functions. Such an approach provides a sound understanding of the underlying stability and fairness issues, as well as a post-facto justification of TCP-like additiveincrease multiplicative-decrease (AIMD) algorithms. This paper provides a counter-example showing that the same result cannot be extended to wireless networks, at least not in a straightforward manner. The fundamental difference is that wireless networks are of a broadcast nature. There is no strict notion of a “link,” since transmissions from nearby nodes interfere with each other. Using a simple model of interference in wireless networks, a counter-example of a wireless network is presented in which the congestion control mechanism has an unstable equilibrium point at the desired fair solution. Further, ns-2 simulations of this counter-example manifest an oscillatory behavior. Surprisingly, this oscillatory behavior appears to be fairly typical in wireless networks, with most randomly chosen network examples manifesting it. This loss of stability suggests a possible need for the re-design of wireless TCP and wireless queue management to explicitly account for the wireless nature of the effects of interference.