  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 be
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.
