Department of Computer Science, University of Crete, Greece

CS-534: Packet Switch Architecture

Spring 2004
Manolis Katevenis
  • Bibliography.
  • Course Description - Schedule
    Lecture Notes, Transparencies, Exercises:
    Chapter 0: Introduction
  • 0.1 Technology Outlook: Switches and Interconnects [PDF]
  • 0.2 Central Issues in Packet Switching: an Overview [PDF]
  • 0.3 (next year) Multiplexing, Time Switching, Space Switching
  • 0.4 (next year) Buffering, Statistical Multiplexing, Output Contention
  • Chapter 1: Transmission Links, Multiplexing
  • 1.1 Parallel and Serial Links, Transmission Rate and Throughput [PDF]
  • 1.2 Inter-Clock Domain Communication: Elastic Buffers
  • 1.3 Multiplexing, Demultiplexing, Statistical Multiplexing, Output Contention
  • 1.4 Multiplexor Implementation: Point-to-Point versus Buses
  • Exercises 1 (due 3 Mar): Transmission Rate, Throughput [PDF]
  • Exercises 2 (due 10 Mar): Turn-Around [PDF]
  • Chapter 2: Time Switching, Buffer Memory Technology
  • 2.1Time-Division Multiplexing (TDM), Time Switching, Cut-Through
  • 2.2 On-Chip SRAM and Power Consumption
  • 2.3 Off-Chip Memory Technologies
  • 2.4 High-Throughput Memories for Time-Switching Shared Buffers
  • Exercises 2 (due 10 Mar): Cut-Through, Memory Access Rate [PDF]
  • Exercises 3 (due 19 Mar): Variable-Size-Packet Segmentation Overhead [PDF]
  • Chapter 3: Multi-Queue Memory Management for Shared-Buffer Switching
  • 3.1 Queueing Architectures and Head-of-Line (HOL) Blocking
  • 3.2 Multi-Queue Data Structures
  • 3.3 Queueing for Multicast Traffic
  • 3.4 The Output-Queueing Family of Switch Architectures
  • Exercises 4 (due 26 Mar): Linked-List Queue Management [PDF]
  • Exercises 5 (due 2 Apr): Advanced Queue Management [PDF]
  • Chapter 4: Time-Space Switching - Input Queueing
  • 4.1 Space (Crossbar) and Time-Space-Time Circuit Switching
  • 4.2 The Input Queueing Family
  • 4.3 On-Line Crossbar Scheduling with VOQ Input Queueing
  • 4.4 Variable-Size Packets, Crossbars with Reconfiguration Overhead
  • 4.5 Combined Input-Output Queueing (CIOQ) - Internal Speedup
  • 4.6 The Big Picture: Switch Queueing Architectures
  • Exercises 6 (due 21 Apr): TST Circuit Switch Scheduling [PDF]
  • Exercises 7 (due 28 Apr): Input Queueing and Crossbar Scheduling [PDF]
  • Exercises 8 (due 5 May): Queueing Architecture SRAM Cost [PDF]
  • Chapter 5: Switching Fabrics, Inverse Multiplexing
  • 5.1 Byte-Sliced Crossbar Switches
  • 5.2 Benes, Clos, and Fat Trees - Inverse Multiplexing
  • 5.3 Bufferless versus Buffered Switching Fabrics
  • Exercises 9 (due 12 May): Internal Blocking in Switching Fabrics [PDF]
  • Exercises 10 (due 21 May): Switching Fabric Topologies [PDF]
  • Chapter 6: Flow Control in Buffered Switching Fabrics
  • 6.1 Flow Control Fundamentals
  • 6.2 Credit-Based Flow Control
  • 6.3 Per-Flow versus Indiscriminate Flow Control
  • 6.4 Backpressure in Buffered Switching Fabrics
  • Exercises 11 (due 28 May): Flow control, per-flow queueing [PDF]
  • Chapter 7: Output Scheduling for QoS
  • 7.1 Conservation Law, Hierarchical Schedulers
  • 7.2 Strict (Static) Priority Scheduling
  • 7.3 Round Robin Scheduling
  • 7.4 Weighted Round Robin (WFQ) Scheduling
  • Exercises 12 (due 11 June): Output Scheduling for QoS [PDF]
  • Reading Assignments: papers to be read and orally presented in class by individual students.
  • Previous Years:

  • Previous Year Home Pages: Sp. 2003 - Fall 2001 - Sp. 2000 and older.

    Last Year Lecture Notes and Transparencies:

    Chapter 2: Basic Switching Notions
  • 2.1 Output Contention, Internal Blocking, HOL Blocking
  • 2.2 Statistical Multiplexing, Inverse Multiplexing
  • 2.3 Switch Architecture Generations, Cut-Through
  • Chapter 4: Switch Queueing Architectures and Crossbar Scheduling
  • 4.1 The Output Queueing / Shared Buffer Family
  • Chapter 8: Other Topics
    [Please refer to the bibliography pointed below:]
  • 8.1 Routing Table Lookup and Flow Classification Hardware
  • 8.2 Cluster, Storage, System, and smaller Area Networks
  • 8.3 Network Processors
  • 8.4 Optical Switching

  • © copyright University of Crete, Greece. Last updated: 27 May 2004 by M. Katevenis.