| dc.contributor |
Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
|
| dc.contributor |
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
|
| dc.contributor |
Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
|
| dc.contributor |
Modiano, Eytan H |
|
| dc.contributor |
Tsitsiklis, John N |
|
| dc.creator |
Markakis, Mihalis G. |
|
| dc.creator |
Modiano, Eytan H |
|
| dc.creator |
Tsitsiklis, John N |
|
| dc.date |
2018-04-05T18:38:09Z |
|
| dc.date |
2018-04-05T18:38:09Z |
|
| dc.date |
2017-10 |
|
| dc.date |
2016-10 |
|
| dc.date |
2018-04-05T18:18:17Z |
|
| dc.date.accessioned |
2023-03-01T18:08:54Z |
|
| dc.date.available |
2023-03-01T18:08:54Z |
|
| dc.identifier |
0364-765X |
|
| dc.identifier |
1526-5471 |
|
| dc.identifier |
http://hdl.handle.net/1721.1/114573 |
|
| dc.identifier |
Markakis, Mihalis G. et al. “Delay Analysis of the Max-Weight Policy Under Heavy-Tailed Traffic via Fluid Approximations.” Mathematics of Operations Research (October 2017): 1-35 © 2017 INFORMS |
|
| dc.identifier |
https://orcid.org/0000-0001-8238-8130 |
|
| dc.identifier |
https://orcid.org/0000-0003-2658-8239 |
|
| dc.identifier.uri |
http://localhost:8080/xmlui/handle/CUHPOERS/278929 |
|
| dc.description |
We consider switched queueing networks with a mix of heavy-tailed (i.e., arrival processes with infinite variance) and exponential-type traffic and study the delay performance of the max-weight policy, known for its throughput optimality and asymptotic delay optimality properties. Our focus is on the impact of heavy-tailed traffic on exponential-type queues/flows, which may manifest itself in the form of subtle rate-dependent phenomena. We introduce a novel class of Lyapunov functions (piecewise linear and nonincreasing in the length of heavy-tailed queues), whose drift analysis provides exponentially decaying upper bounds to queue-length tail asymptotics despite the presence of heavy tails. To facilitate a drift analysis, we employ fluid approximations, proving that if a continuous and piecewise linear function is also a “Lyapunov function” for the fluid model, then the same function is a “Lyapunov function” for the original stochastic system. Furthermore, we use fluid approximations and renewal theory in order to prove delay instability results, i.e., infinite expected delays in steady state. We illustrate the benefits of the proposed approach in two ways: (i) analytically, by studying the delay stability regions of single-hop switched queueing networks with disjoint schedules, providing a precise characterization of these regions for certain queues and inner and outer bounds for the rest. As a side result, we prove monotonicity properties for the service rates of different schedules that, in turn, allow us to identify “critical configurations” toward which the state of the system is driven, and that determine to a large extent delay stability; (ii) computationally, through a bottleneck identification algorithm, which identifies (some) delay unstable queues/flows in complex switched queueing networks by solving the fluid model from certain initial conditions. Keywords: switched queueing networks; max-weight policy; heavy-tailed traffic; fluid approximations; piecewise linear Lyapunov functions |
|
| dc.description |
National Science Foundation (U.S.) (Grant CNS-1217048) |
|
| dc.description |
National Science Foundation (U.S.) (Grant CMMI-1234062) |
|
| dc.description |
United States. Office of Naval Research (Grant N00014-12-1-0064) |
|
| dc.description |
United States. Army Research Office (Grant W911NF-08-1-0238) |
|
| dc.format |
application/pdf |
|
| dc.publisher |
Institute for Operations Research and the Management Sciences (INFORMS) |
|
| dc.relation |
http://dx.doi.org/10.1287/MOOR.2017.0867 |
|
| dc.relation |
Mathematics of Operations Research |
|
| dc.rights |
Creative Commons Attribution-Noncommercial-Share Alike |
|
| dc.rights |
http://creativecommons.org/licenses/by-nc-sa/4.0/ |
|
| dc.source |
MIT Web Domain |
|
| dc.title |
Delay Analysis of the Max-Weight Policy Under Heavy-Tailed Traffic via Fluid Approximations |
|
| dc.type |
Article |
|
| dc.type |
http://purl.org/eprint/type/JournalArticle |
|