Research Projects

Delay Queue Scheduling

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 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 minimal as possible, or 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 the results known so far show the average delay bound of reciprocal form of 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 queue problem, we search for the optimality condition of queuing policy choice among tail-drop, head-drop or no-drop.

More information: http://www.eecs.berkeley.edu/~wlr