Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2009 Research Summary

Delay Queue Scheduling

View Current Project Information

Jean Walrand and Jiwoong Lee

Army Research Office

The nature of traffic source, human interaction, and underlying timer-based protocol behavior all impose the latency constraints on the travel time of a packet from source to destination over the network. Throughput-based performance does not capture this latency requirement. Capacity-achieving schemes such as back-pressure algorithm or maximum-weight matching obtain their goal often at the cost of infinite capacity queue and very long delay in it. In the real world, there is neither such an infinite queue nor such a tolerant user.

In many cases, throughput is not the sole goal of a good network. Rather, latency, resilience, and reliability can be more important factors. Of course, for any network, one can always minimize the delay by forcing throughput as minimally as possible, or at almost zero. Apparently this cannot be the goal we pursue. In the meantime, there is a research trend to find a delay bound of capacity-achieving queuing schemes. In general, all of the results known so far show the average delay bound of the reciprocal form of the difference of service rate and arrival rate.

We explore the right model for delay sensitive traffic and optimal queue scheduling and user control problems. For the queue problem, we search for the optimal condition of queuing policy choice among tail-drop, head-drop, or no-drop.