Subsections in the current document:

• 4.1 Output Queueing Family
• 4.2 Input Queueing Family
  Appendices for optional study: performance analysis transparencies by prof. George Stamoulis, Spring 2000 semester:
  • Spring 2000 sec. 4.6: Input Queueing Throughput Analysis
  • Spring 2000 sec. 4.7: Input Queueing Delay Analysis and Variants
  • Spring 2000 sec. 4.8: Output Queueing Performance Analysis
• 4.3 Combinations and Variations
• 4.4 Queueing Architecture Summary and Comparisons
• 4.5 Shared Buffer Implementation: Wide Memory, Pipelined Memory
• 4.6 Crossbar Scheduling with (Per-Input) Virtual-Output Queues
• 4.7 Speedup Required to Emulate Output Queueing

Introduction

4.1 Output Queueing Family

Buffer Space Requirements: When the incoming traffic consists of fixed-size packets from independent, identically distributed (i.i.d.) Bernoulli processes, with uniformly-distributed destination (output) ports, analysis and simulation have yielded the results plotted below --primarily from the Hluchyj and Karol JSAC paper of December 1988 referenced below (© copyright IEEE).
Attention: results derived for i.i.d. Bernoulli (non-bursty) arrivals, with uniformly-distributed destinations (no overloaded hot-spots), are only useful for gaining a rough, first insight into the behavior of systems, but are often not representative of the real behavior of systems under real traffic!...

© copyright IEEE --primarily from the Hluchyj and Karol JSAC paper of December 1988 referenced below.

4.2 Input Queueing Family

Throughput and Delay under Input Queueing with Head-of-Line (HOL) Blocking: When the incoming traffic consists of fixed-size packets from independent, identically distributed (i.i.d.) Bernoulli processes, with uniformly-distributed destination (output) ports, analysis and simulation have yielded the results plotted below --primarily from the Hluchyj and Karol JSAC paper of December 1988 referenced below (© copyright IEEE).
Attention: results derived for i.i.d. Bernoulli (non-bursty) arrivals, with uniformly-distributed destinations (no overloaded hot-spots), are only useful for gaining a rough, first insight into the behavior of systems, but are often not representative of the real behavior of systems under real traffic!...

References:

• 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.
• Input and output queueing performance analysis transparencies by prof. George Stamoulis, CS-534, Spring 2000 semester:
  • Spring 2000 sec. 4.6: Input Queueing Throughput Analysis
  • Spring 2000 sec. 4.7: Input Queueing Delay Analysis and Variants
  • Spring 2000 sec. 4.8: Output Queueing Performance Analysis
• Other References:
  • 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.
  • 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.3 Combinations and Variations

4.4 Queueing Architecture Summary and Comparisons

4.5 Shared Buffer Implementation: Wide Memory, Pipelined Memory

Animated Illustration of the Pipelined Memory Operation [click here]

Reference:
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; http://archvlsi.ics.forth.gr/sw_arch/pipeMem.html . FORTH, Crete, Greece (1994): USA patent number 5,774,653 of 30 June 1998.

4.6 Crossbar Scheduling with (Per-Input) Virtual-Output Queues

Bibliographic references: click here

4.7 Speedup Required to Emulate Output Queueing

Bibliographic references: click here