[ Up to the Home Page of CS-534 ]
© copyright University of Crete, Greece.
Dept. of Computer Science, University of Crete.
CS-534: Packet Switch Architecture

4. Switch Queueing Architectures & Performance

Subsections in the current document:


Switch Queueing Architectures

4.1 Output Queueing Family

Output Queueing and Variations

Output Queueing: The Reference Arcitecture

Knock-Out Switch

Crosspoint (Distributed) Queueing

Shared Buffer: Top Performance at Low Cost for small N

Block-Crosspoint Queueing: Distributed Shared Buffers

4.2 Shared Buffer Implementation: Wide Memory, Pipelined Memory

Multiplexing the Switch Ports onto a single Memory Port

Time-Multiplexing the Switch Ports on a Wide Memory Port

See the paper: M. Katevenis, P. Vatsolaki, A. Efthymiou: Pipelined Memory Shared Buffer for VLSI Switches, Proceedings of the ACM SIGCOMM '95 Conference, Cambridge, MA USA, 30 August - 1 Sep. 1995, pp. 39-48; USA patent number 5,774,653.

4.3 Input Queueing Family

Input Queueing Family

Advanced Input Queueing (Buffering) - Virtual Output Queues

Input Queueing is NOT the Dual of Output Queueing

4.4 Combinations and Variations

Internal Speed-Up: Combination of Input and Output Queueing

Sorting Networks with Distributed Control

Switching Fabrics with Internal Buffering and Backpressure

4.5 Queueing Architecture Summary and Comparisons

Summary of MxN Switch Architectures

4.6 Input Queueing Throughput Analysis

InQ Throughput Analysis 1

InQ Throughput Analysis 2

InQ Throughput Analysis 3

InQ Throughput Analysis 4

InQ Throughput Analysis 5

InQ Throughput Analysis 6

See the papers:

M. Karol, M. Hluchyj, S. Morgan: "Input versus Output Queueing on a Space-Division Packet Switch", IEEE Trans. on Communications, vol. 35, no. 12, Dec. 1987, pp. 1347-1356.

M. Hluchyj, M. Karol: "Queueing in High-Performance Packet Switching", IEEE Journal on Sel. Areas in Commun. (JSAC), vol. 6, no. 9, Dec. 1988, pp. 1587-1597.

4.7 Input Queueing Delay Analysis and Variants

InQ Delay Analysis

InQ Delay Plots

Input Queueing Variants

Hui/Arthurs Approximation 1

Hui/Arthurs Approximation 2

Hui/Arthurs Approximation 3

See the paper: J. Hui, E. Arthurs: "A Broadband Packet Switch for Integrated Transport", IEEE Journal on Sel. Areas in Commun. (JSAC), vol. 5, no. 8, Oct. 1987, pp. 1264-1273.

4.8 Output Queueing Performance Analysis

Output Queue Size Analysis 1

Output Queue Size Analysis 2

Output Queue Delay Analysis 1

Output Queue Delay Analysis 2

Delay, Loss Probability Plots 1

Delay, Loss Probability Plots 2


4.9 Scheduling for Input Buffered Switches

See papers number 3 through 7 in the Reading List.

[ Up to the Home Page of CS-534 ]
© copyright University of Crete, Greece.
Last updated: April 2000, by M. Katevenis.
Sections 4.6 through 4.8 by G. Stamoulis.