Service-curve based algorithms for scheduling with quality-of-service guarantees in packet-switched networks and switches

In this dissertation, we design and analyze scheduling algorithms that provide quality-of-service (QoS) guarantees on the network level as well as on the switch level. All algorithms considered here are based on the framework of the service curve proposed by Cruz [12]. The goal is to develop practical and scalable algorithms that reduce the complexity of the underlying switch and at the same time provide deterministic QoS guarantees comparable to those of the efficient scheduling policy Service Curve Earliest Deadline first (SCED) of [28].; On the network level, we propose a general framework for scheduling using rate-based schemes such that provable deterministic QoS guarantees are achieved. Sufficient properties for this approach to emulate the performance of the SCED policy were identified. Novel specific algorithms were designed and analyzed as examples of the approach.; On the switch level, we propose an algorithm for scheduling cells in Combined Input and Output Queued (CIOQ) switches. With this algorithm, it is shown using a service curve formulation, that an N x N CIOQ switch with any “speedup” s ≥ 2, independent of N, may “exactly emulate” the ideal performance of a counterpart Output Queued (OQ) switch, which requires a “speedup” of s ≥ N.; Finally, we consider the configuration delays of a server serving M packet-streams. Specifically, whenever the server is serving a packet from stream i and the next packet to be served (according to some scheduling policy, e.g., the SCED) is from stream j, where j ≠ i, the server must go on a vacation of β seconds before serving this next packet. It is shown that the SCED policy under this constraint can guarantee that no packet misses its deadline by more than D_max = max{lcub}$LmaxC$, β{rcub}, where L_max is the maximum packet length in bits from all streams and C is the capacity of the server in bits per second. Unfortunately, this was achieved at the expense of the throughput of the server. Therefore, a throughput oriented scheduling algorithm based on the SCED policy is proposed that achieves high throughput, and at the same time guarantees a delay bound for each packet.