Scheduling algorithms for wireless networks and data centers have been studied primarily from the perspective of throughput optimality. Delay optimality, on the other hand, is often difficult to establish, except for special network topologies. An alternative is to study the delay performance of an algorithm in the so-called heavy-traffic regime. Typically heavy-traffic optimality is studied using fluid and reflected Brownian motion limits. In this talk, we will present an alternative technique based on the following simple observation: the drift of appropriately chosen functions of queue lengths is equal to zero in steady-state. Using the drift technique, we resolve an open conjecture regarding the delay performance of scheduling algorithms in large networks. Joint work with Atilla Eryilmaz, Siva Theja Maguluri, and Sai Kiran Burle.

In almost anything in life, including in the transmissions in wireless networks, scheduling is a cornerstone for order and performance. Specifically in wireless networking, scheduling has been among the first problems to be studied in depth. It is in fact amazing how the problem unfolds and reveals its multiple facets as we try to formulate it and solve it. After a brief primer on what we know about scheduling, this talk will focus on one most interesting version which combines the multiple access, networking, and physical layers in a tractable way, and, furthermore, can serve as a building block for more ambitious and complex scheduling problems. This version has to do with emptying the contents of the buffers of all the nodes that share a common channel in minimum time. After reviewing recent progress on this problem we propose and develop a formulation that characterizes fully the optimal solution. Attention: optimal, not only in the sense of deciding which nodes transmit and for how long, but also at what bit-rate for given power levels and channel characteristics. The resulting solution is simple to describe but still complex to realize.

One of the fundamental problems in a cognitive radio network, known as the multichannel rendezvous problem, is for two secondary users to find a common channel that is not blocked by primary users. A common approach for solving such a problem in the literature is for the two users to select their own channel hopping sequences and then rendezvous when they both hop to a common unblocked channel at the same time. In this talk, we give an overview of various lower bounds on the time-to-rendezvous of the multichannel rendezvous problem in various settings. We also give intuitive explanations for various channel hopping sequences to be optimal in various settings. These include the classical wait-for-mommy strategy in the asymmetric setting, the walks on finite projective planes in the symmetric and synchronous setting, and the sawtooth sequences and difference-set-based hopping sequences in the symmetric and asynchronous setting. We also discuss how unique ID and available channel set can be used for speeding up the rendezvous process in the multichannel rendezvous problem.