標題: Delay-Constrained Input-Queued Switch
作者: Deng, Lei
Wong, Wing Shing
Chen, Po-Ning
Han, Yunghsiang S.
Hou, Hanxu
電機工程學系
Department of Electrical and Computer Engineering
關鍵字: Input-queued switch;delay-constrained communication;timely throughput;capacity region;scheduling policy
公開日期: 1-Nov-2018
摘要: In this paper, we study the delay-constrained input-queued switch, where each packet has a deadline and it will expire if it is not delivered before its deadline. Such new scenario is motivated by the proliferation of real-time applications in multimedia communication systems, tactile Internet, networked controlled systems, and cyber-physical systems. The delay-constrained input-queued switch is completely different from the well-understood delay-unconstrained one and thus poses new challenges. We focus on three fundamental problems centering around the performance metric of timely throughput: (i) how to characterize the capacity region? (ii) how to design a feasibility/throughput-optimal scheduling policy? and (iii) how to design a network-utility-maximization scheduling policy? We use three different approaches to solve these three fundamental problems. The first approach is based on Markov Decision Process (MDP) theory, which can solve all three problems. However, it suffers from the curse of dimensionality. The second approach breaks the curse of dimensionality by exploiting the combinatorial features of the problem. It gives a new capacity region characterization with only a polynomial number of linear constraints. The third approach is based on the framework of Lyapunov optimization, where we design a polynomial-time maximum-weight T-disjoint-matching scheduling policy which is proved to he feasibility/throughput-optimal. Our three approaches apply to the frame-synchronized traffic pattern but our MDP-based approach can be extended to more general traffic patterns.
URI: http://dx.doi.org/10.1109/JSAC.2018.2874110
http://hdl.handle.net/11536/148559
ISSN: 0733-8716
DOI: 10.1109/JSAC.2018.2874110
期刊: IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS
Volume: 36
起始頁: 2464
結束頁: 2474
Appears in Collections:Articles