Delay Reduction for Adaptive Scheduling in Wireless Networks and Aggregated Equilibrium for Resource Sharing Games

Add to your list(s) Download to your calendar using vCal

• Loc Bui, Stanford University
• Wednesday 13 April 2011, 10:00-11:00
• Large lecture theatre, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge.

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

This talk consists of two parts:

In the first part, I will talk about delay reduction for the back-pressure algorithm. The back-pressure algorithm is a well-known adaptive scheduling and routing algorithm that achieves maximum throughput in wireless networks. However, its delay performance may be quite poor even when the traffic load is not close to network capacity due to the following two reasons. First, each node has to maintain a separate queue for each commodity in the network (per-flow or per-node queues), and only one queue is served at a time. Second, the back-pressure routing algorithm may route some packets along very long routes. We present solutions to address the above issues, and hence, dramatically improve its delay performance. The suggested solutions also allow each node to maintain only per-neighbor queues. This is joint work with E. Athanasopoulou, T. Ji, R. Srikant, and A. Stolyar.

In the second part, I will talk about the concept of aggregated equilibrium for resource sharing games. We study a priority service model where a single server allocates its capacity to agents in proportion to their payment to the system, and users act to minimize the sum of their cost for processing delay and payment. Calculation of exact Nash equilibrium proves to be difficult, because both the queueing and strategic interactions introduce significant complexity into characterization of agents’ processing times. To overcome this complexity, we first develop a novel approximation to the processing time of an agent that is provably optimal when the system is in heavy traffic, and performs well even away from heavy traffic. Then, using this approximation, we introduce a novel notion of equilibrium that we call aggregated equilibrium (AE). In an AE, a single user optimizes against an aggregate representation of the rest of the population; a consistency check then requires that this aggregate representation arises from individual users’ decisions. We show that AE can be found in closed form, and serves as a good approximation to Nash equilibrium behavior. This is joint work with R. Johari and Y. Wu.

This talk is part of the Microsoft Research Cambridge, public talks series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• Large lecture theatre, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge
• Microsoft Research Cambridge, public talks
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.