The Stability of Longest-Queue-First Scheduling With Variable Packet Sizes

Maguluri, Siva Theja

Permalink

https://hdl.handle.net/2142/26514 Copy

Description

Title

The Stability of Longest-Queue-First Scheduling With Variable Packet Sizes

Author(s)

Maguluri, Siva Theja

Contributor(s)

• Hajek, Bruce
• Srikant, R.

Issue Date

2011-04

Keyword(s)

• Wireless Scheduling
• throughput optimality
• Lyapunov analysis

Abstract

It is well known that the MaxWeight scheduling algorithm is throughput-optimal in wireless networks. However, its complexity is exponential in the number of links in an ad hoc network. In this work, we consider a greedy variant of the MaxWeight algorithm, called Longest Queue First (LQF). A synchronous version of LQF is known to be throughput optimal under a topological condition called local pooling. Here we study an asynchronous version of LQF which is suitable for implementation in networks with variable packet sizes.We show that asynchronous LQF is also throughput-optimal under the local pooling condition.

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/26514

Sponsor(s)/Grant Number(s)

AFOSR Grant FA-9550-08-1-0432, ARO MURI W911NF-08-1-0233, ARO MURI W911NF-07-1-0287, and AFOSR MURI FA9550-10-1-0573.

Owning Collections