Heavy-traffic behavior of the maxweight algorithm in a switch with uniform traffic

Siva Theja Maguluri, Rayadurgam Srikant

Research output: Contribution to journalConference article

Abstract

We consider a switch with uniform traffic operating under the MaxWeight scheduling algorithm. This traffic pattern is interesting to study in the heavy-traffic regime since the queue lengths exhibit a multi-dimensional state-space collapse. We use a Lyapunov-type drift technique to characterize the heavy-traffic behavior of the expectation of the sum queue lengths in steady-state. Specifically, in the case of Bernoulli arrivals, we show that the heavy-traffic scaled queue length is " n - 3 2 + 1 2n # . Our result implies that the MaxWeight algorithm has optimal queue-length scaling behavior in the heavy-traffic regime with respect to the size of a switch with a uniform traffic pattern. This settles the heavy-traffic version of an open conjecture.

Original languageEnglish (US)
Article number2825264
Pages (from-to)72-74
Number of pages3
JournalPerformance Evaluation Review
Volume43
Issue number2
DOIs
StatePublished - Sep 16 2015
Event33rd International Symposium on Computer Performance, Modeling, Measurement, and Evaluation, IFIP WG 7.3 Performance 2015 - Sydney, Australia
Duration: Oct 19 2015Oct 21 2015

Fingerprint

Switches
Scheduling algorithms

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Heavy-traffic behavior of the maxweight algorithm in a switch with uniform traffic. / Maguluri, Siva Theja; Srikant, Rayadurgam.

In: Performance Evaluation Review, Vol. 43, No. 2, 2825264, 16.09.2015, p. 72-74.

Research output: Contribution to journalConference article

@article{92fc0a4d3e514c36b393a473d52c5ff2,
title = "Heavy-traffic behavior of the maxweight algorithm in a switch with uniform traffic",
abstract = "We consider a switch with uniform traffic operating under the MaxWeight scheduling algorithm. This traffic pattern is interesting to study in the heavy-traffic regime since the queue lengths exhibit a multi-dimensional state-space collapse. We use a Lyapunov-type drift technique to characterize the heavy-traffic behavior of the expectation of the sum queue lengths in steady-state. Specifically, in the case of Bernoulli arrivals, we show that the heavy-traffic scaled queue length is {"} n - 3 2 + 1 2n # . Our result implies that the MaxWeight algorithm has optimal queue-length scaling behavior in the heavy-traffic regime with respect to the size of a switch with a uniform traffic pattern. This settles the heavy-traffic version of an open conjecture.",
author = "Maguluri, {Siva Theja} and Rayadurgam Srikant",
year = "2015",
month = "9",
day = "16",
doi = "10.1145/2825236.2825264",
language = "English (US)",
volume = "43",
pages = "72--74",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

TY - JOUR

T1 - Heavy-traffic behavior of the maxweight algorithm in a switch with uniform traffic

AU - Maguluri, Siva Theja

AU - Srikant, Rayadurgam

PY - 2015/9/16

Y1 - 2015/9/16

N2 - We consider a switch with uniform traffic operating under the MaxWeight scheduling algorithm. This traffic pattern is interesting to study in the heavy-traffic regime since the queue lengths exhibit a multi-dimensional state-space collapse. We use a Lyapunov-type drift technique to characterize the heavy-traffic behavior of the expectation of the sum queue lengths in steady-state. Specifically, in the case of Bernoulli arrivals, we show that the heavy-traffic scaled queue length is " n - 3 2 + 1 2n # . Our result implies that the MaxWeight algorithm has optimal queue-length scaling behavior in the heavy-traffic regime with respect to the size of a switch with a uniform traffic pattern. This settles the heavy-traffic version of an open conjecture.

AB - We consider a switch with uniform traffic operating under the MaxWeight scheduling algorithm. This traffic pattern is interesting to study in the heavy-traffic regime since the queue lengths exhibit a multi-dimensional state-space collapse. We use a Lyapunov-type drift technique to characterize the heavy-traffic behavior of the expectation of the sum queue lengths in steady-state. Specifically, in the case of Bernoulli arrivals, we show that the heavy-traffic scaled queue length is " n - 3 2 + 1 2n # . Our result implies that the MaxWeight algorithm has optimal queue-length scaling behavior in the heavy-traffic regime with respect to the size of a switch with a uniform traffic pattern. This settles the heavy-traffic version of an open conjecture.

UR - http://www.scopus.com/inward/record.url?scp=84978704744&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84978704744&partnerID=8YFLogxK

U2 - 10.1145/2825236.2825264

DO - 10.1145/2825236.2825264

M3 - Conference article

AN - SCOPUS:84978704744

VL - 43

SP - 72

EP - 74

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 2

M1 - 2825264

ER -