Service Control Policies for Packet Switches with Target Output Traffic Profiles

Abstract — We address the problem of packet scheduling for traffic streams with target profiles through input queued switches, arising in real-time applications like multimedia streaming. The target profiles specify the ideal inter-departure times of packets in each stream from the switch (inter-packet deadlines). The goal of the scheduler is to dynamically select service configurations for the switch so that output traffic streams adhere to their associated target profiles as accurately as possible. We develop service controls/schedules to minimize deviation of output streams from their desirable targets for real-time multimedia services with tight delay and jitter requirements. We formulate the problem within a dynamic programming framework and establish key structural properties of the optimal schedules. We propose the notion of configuration subset based controls, which enables us to design simple scheduling algorithms amenable to implementation in high performance packet switches. The proposed algorithms deliver excellent performance at low computational complexity and are robust with respect to statistics of input traffic traces. While our focus is on the input queued switching architecture, the idea of service trace control to match target profiles is more widely applicable to any scenario involving delay and jitter sensitive communication over a packet switched network