CS-534: Packet Switch Architecture
Spring 2005		 Department of Computer Science
© copyright: University of Crete, Greece

4.2   The Input Queueing Family

[Up - Table of Contents]
[Prev: 4.1 Space Switching]
[4.3 Crossbar Scheduling - Next]

4.2.1   The Input Queueing Family

Input Queueing Family

Input Queueing is NOT the Dual of Output Queueing

4.2.2   Old-Style (Single-Queue) Input Queueing - Head-of-Line Blocking

Head-of-Line Blocking under Single-Queue per Input

Output Schedulers are Independent under Single-Queue per Input

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. Sources (© copyright IEEE):
  • 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.
  • 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.
    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!...

    Input queueing saturation throughput

    Input queueing delay Output queueing delay

    Delay comparison for output versus input queueing

    © copyright IEEE

    Appendices for optional study:
    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

    4.2.3   Advanced Input Queueing (Buffering) - Virtual Output Queues (VOQ)

    Advanced Input Queueing (Buffering) - Virtual Output Queues

    [Up - Table of Contents]
    [Prev: 4.1 Space Switching]
    [4.3 Crossbar Scheduling - Next]
    Up to the Home Page of CS-534
         		 © copyright University of Crete, Greece.
    Last updated: 17 Apr. 2005, by M. Katevenis.