Deadline Aware Packet Scheduling in Switches for Multimedia Streaming Applications

Abstract—We consider the problem of scheduling packets in an input queued switch with a focus on processing streamed multimedia data. In such applications, packets arrive with hard service deadlines; after the deadline for a packet has passed, it is no longer useful and does not get delivered- it is dropped. We seek policies to minimize the number of late packets, which are then dropped. The problem is formulated in a Dynamic Programming framework and shown to be intractable. The formulation is contrasted to the related crossbar switch scheduling problem, with an emphasis on the fact that we have a different objective function. A simplified probabilistic version of the streaming problem is used as motivation for a heuristic solution. Finally, we present results from a simulation in which a simple heuristic based on weighting queues according to the deadline of the leading packet consistently outperforms the well-known maximum weight matching (MWM) algorithm. Index Terms—scheduling; deadlines; crossbar switch; input-queued switch; maximum weight matching I