Jagannathan, KrishnaMarkakis, Mihalis G.Modiano, EytanTsitsiklis, John N.2019-01-092019-01-092014Jagannathan K, Markakis MG, Modiano E, Tsitsiklis JN. Throughput optimal scheduling over time-varying channels in the presence of heavy-tailed traffic. IEEE Trans Inf Theory. 2014 May;60(5):2896-909. DOI: 10.1109/tit.2014.23111250018-9448http://hdl.handle.net/10230/36225We study the problem of scheduling over time-varying links in a network that serves both heavytailed and light-tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic (the “heavy queue”), and the other receives lighttailed traffic (the “light queue”). The queues are connected to the server through time-varying ON/OFF links, which model fading wireless channels. We first show that the policy that gives complete priority to the light-tailed traffic guarantees the best possible tail behavior of both queue backlog distributions, whenever the queues are stable. However, the priority policy is not throughput maximizing, and can cause undesirable instability effects in the heavy queue. Next, we study the class of throughput optimal max-weight scheduling policies. We discover a threshold phenomenon, and show that the steady-state light queue backlog distribution is heavy-tailed for arrival rates above a threshold value, and light-tailed otherwise. We also obtain the exact ‘tail coefficient’ of the light queue backlog distribution under maxweight scheduling. Finally, we analyze a log-max-weight (LMW) scheduling policy, and show that in addition to being throughput optimal, the LMW policy ensures that the light queue backlog distribution is light-tailed.application/pdfeng© 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The final published article can be found at http://dx.doi.org/10.1109/tit.2014.2311125info:eu-repo/semantics/articlehttp://dx.doi.org/10.1109/tit.2014.2311125SchedulingQueuing AnalysisHeavy-tailed trafficinfo:eu-repo/semantics/openAccess