This paper proposes an innovative Pipeline-based Maximal-sized Matching scheduling approach, called PMM, for input-buffered switches. It dramatically relaxes the limitation of a single time slot for completing a maximal matching into any number of time slots. In the PMM approach, arbitration is operated in a pipelined manner, where K subschedulers are used. Each subscheduler is allowed to take more than one time slot for its matching. Every time slot, one of the subschedulers provides the matching result. We adopt an extended version of Dual Round-Robin Matching (DRRM), called iterative DRRM (iDRRM), as a maximal matching algorithm in a subscheduler. PMM maximizes the efficiency of the adopted arbitration scheme by allowing sufficient time for the number of iterations. We show that PMM preserves 100% throughput under uniform traffic and fairness for best-effort traffic of the non-pipelined adopted algorithm, while ensuring that cells from the same virtual output queue (VOQ) are transmitted in sequence. In addition, we confirm that the delay performance of PMM is not significantly degraded by increasing the pipeline degree, or the number of subschedulers, when the number of outstanding requests for each subscheduler from a VOQ is limited to 1.

In this paper, we propose a packet-scheduling algorithm, called the Class-level Service Lagging (CSL) algorithm, that guarantees multiple delay bounds for multi-class traffic in packet networks. We derive the associated schedulability test conditions, which are used to determine call admission. We first introduce a novel implementation of priority control, which has a conventional and simple form. We show how the efforts to confirm the logical validity of that implementation are managed to reach the definition of the CSL algorithm. The priority control is realized by imposing class-level unfairness in service provisioning, while the underlying service mechanism is carried out using the notion of fair queueing. The adoption of fair queueing allows the capability to maintain the service quality of the well-behaving traffic even in the presence of misbehaving traffic. We call this the firewall property. Simulation results demonstrate the superiority of the CSL algorithm in both priority control and firewall functionality. We also describe how the CSL algorithm is implementable with a computational complexity of O(1). Those features as well as the enhanced scalability, which results from the class-level approach, confirm the adequacy of the CSL algorithm for the fast packet networks.