Thumbnail
Access Restriction
Open

Author Rajagopalan, S. ♦ Shah, D. ♦ Shin, J.
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Aloha Work ♦ Queueing Network ♦ Network Graph ♦ Scheduled Queue ♦ Various Researcher ♦ General Interest ♦ Novel Adiabatic-like Theorem ♦ Key Ingredient ♦ Algorithm Building ♦ Dynamical System ♦ Independent Set Constraint ♦ Multiple Entity ♦ Extreme Simplicity ♦ Common Resource ♦ Appropriate Function ♦ Wireless Multi-access Network ♦ Queue Size ♦ Distributed Nature ♦ Various Setup ♦ Example Application ♦ Metropolis-hastings Sampling Mechanism
Abstract The popularity of Aloha(-like) algorithms for resolution of contention between multiple entities accessing common resources is due to their extreme simplicity and distributed nature. Example applications of such an algorithm include Ethernet and recently emerging wireless multi-access networks. For more than four decades, various researchers have established the inefficiency of (the known versions of) such algorithms to varying degrees in various setups. However, the question that has remained unresolved is that of designing an algorithm that is essentially as simple and distributed as Aloha while being efficient. In this paper, we resolve this question successfully for a network of queues when contention is modeled through independent set constraints over the network graph. The work by Tassiulas and Ephremides (1992) suggests that an algorithm that schedules queues so that the summation of “weight ” of scheduled queues is maximized subject to constraints, is efficient. However, implementing such an algorithm using Aloha like mechanism has remained a mystery. We design such an algorithm building upon a Metropolis-Hastings sampling mechanism along with selection of “weight ” as an appropriate function of the queue size. The key ingredient in establishing the efficiency of the algorithm is a novel adiabatic-like theorem for the underlying queueing network, which may be of general interest in the context of dynamical systems.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Journal THE ANNALS OF APPLIED PROBABILITY