<p>There is a tremendous demand for Internet core nodes to provide quality-of-service (QoS) guarantees for multimedia services, and to provide high switching capacity that makes use of the virtually unlimited bandwidth of optical fibers. The Internet's Success depends on the deployment of high-speed switches and routers that meet these two demands. We address theoretical and practical aspects of packet switch scheduling in high-speed data networks.</p> <p>First, we address short-term fairness III QoS scheduling for input-queued (IQ) switches. We show that existing practical scheduling algorithms for Internet routers with IQ switches are unfair over short time scales and potentially lead to increased jitter. Subsequently, we present a scheduling policy based on credit-based fair queueing that provides better short-term fairness in QoS scheduling than existing solutions with comparable complexity. A flow-based iterative credit-based fair scheduler (iCBFS) is proposed for crossbar switches, that provides fair bandwidth distribution among flows at a fine granularity and achieves asymptotically 100% throughput, under uniform traffic. To reduce the implementation complexity of iCBFS, we present a port-based version of iCBFS that is tailored towards high-speed hardware implementation.</p> <p>Second, we address the problem of fair scheduling of packets in Internet routers with IQ switches and unity speedup. Scheduling in IQ switches is formulated as tracking the behaviour of an output-queued (OQ) switch that provides optimal performance. We present the notion of "lag" as a performance metric that measures the difference between a packet's departure time in an IQ switch over that provided by an OQ switch. We prove that per packet mean lag is bounded for a maximum weight matching scheduling policy that uses lag values for its weights and derive a bound on the mean lag value using a Lyapunov function technique. Furthermore, we propose a simple heuristic tracking scheduling policy and evaluate its performance by simulation.</p> <p>Finally, we present a novel distributed scheduling paradigm for Internet routers with IQ switches, called Cooperative Token-Ring (CTR) that provides significant performance improvement over existing scheduling schemes with comparable complexity. In classical token-ring based scheduling for IQ switches, a separate token ring (an arbiter) is used to resolve contention for each shared resource (i.e., an output port). Although classical token-ring based scheduling achieves fairness and high throughput for uniform traffic, under non-uniform traffic the performance degrades significantly. We show that by using a simple cooperative mechanism between the otherwise non-cooperative token rings (arbiters) the performance can be significantly improved and the scheduler is able to dynamically adapt to any non-uniform traffic pattern. To provide adequate support for rate guarantees in IQ switches, we present a Weighted Cooperative Token-Ring (WCTR), a simple hierarchical scheduling mechanism. Finally, we analyze the hardware complexity introduced by the proposed CTR scheduling and describe an optimal hardware implementation for an N x N switch implementing a CTR scheduler. We show that the hardware time complexity introduced by the proposed Cooperative mechanism is 8 (log N). iv</p> / Doctor of Philosophy (PhD)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/12726 |
| Date | 03 1900 |
| Creators | Gourgy, Amir |
| Contributors | Szymanski, Ted H., Electrical and Computer Engineering |
| Source Sets | McMaster University |
| Detected Language | English |
| Type | thesis |
Page generated in 0.002 seconds