Department of Computer Science, University of Crete, Greece

CS-534: Packet Switch Architecture

Spring 2013
Manolis Katevenis

Week 9: lecture on Monday 22 April only, then... have a nice Easter break...

Week 8: midterm exam on Monday 15 April; lectures on Wed. 17 April (room H208) and Friday 19 April (room H206), from 17:00 to 19:00 (5-7) on both days.

Bibliography.

Course Description [PDF]

Lectures of weeks 6 - 7: Mondays and Wednesdays, 1, 3, 8, and 10 April.
Lectures of weeks 4 - 5: Wednesdays and Fridays, 20, 22, 27, and 29 March --but on Fridays the time will be 11-1 and the room will be H206.
Lectures of weeks 1 - 3: Mon. 25/2 and Fri. 1/3; then Mondays and Wednesdays, 4, 6, 11, and 13 March.

Lecture Notes, Transparencies, Exercises:

This Year:

Chapter 1: Basic Concepts and Queueing Architectures

[Slides in PDF] [Slides Handout in PDF]
Exercises 1 (due 11 Mar 2013, week 3.1): Internal Blocking, Q'ing Arch. Throughput [HTML] [PDF]
[Older text for a portion of the above material: [Text in HTML] [Text in PDF] ]
[in 2006 and earlier, there has been a section on "Technology Outlook"]

Chapter 2: Link and Memory Architectures and Technology

2.1 Links, Throughput/Buffering, Multi-Access Overheads [Slides in PDF] [Slides Handout in PDF]
[to be done: move "cut-through" from 3.1 to 2.1. Older text for section 2.1.1: [Text in HTML] [Text in PDF] ]
Exercises 2 (due 20 Mar 2013, week 4.1): Transmission Rate and Throughput, Turn-Around Overhead [HTML] [PDF]
[note - to be fixed: exercise 2.4 is dulpicated as also exercise 4.2]
2.2 Memory Technologies: On-chip / Off-chip SRAM, DRAM [Slides in PDF] [Slides Handout in PDF] [answer to a question: QDR notes]
Exercises 3 (due 27 Mar 2013, week 5.2): Memory Access Rate, Variable-Size-Packet Segmentation [HTML] [PDF]
2.A Appendix: Elastic Buffers for Cross-Clock Communication [Slides in PDF] [Slides Handout in PDF]

Chapter 3: Time Switching, Multi-Queue Memories, Shared Buffers, Output Queueing Family

3.1 Time Division Multiplexing (TDM), Time Switching, Cut-Through [Slides in PDF] [Slides Handout in PDF]
Exercises 4 (due 29 Mar. 2013, week 5.3): Switch Generations, Cut-Through [HTML] [PDF]
[note - to be fixed: exercise 4.2 is the same as exercise 2.4]
3.2 Wide Memories for High Throughput, Segmentation Overhead [Slides in PDF] [Slides Handout in PDF]
[animation of the operation of the pipelined memory]
3.3, 3.4 Multiple Queues within a Buffer Memory, Queueing for Multicast Traffic [Slides in PDF] [Slides Handout in PDF]
[animated PPT for queue operations with free-block preallocation]
Exercises 5 (due 3 Apr. 2013, week 6.2): Linked-List Queue Management [HTML] [PDF]
3.5 Shared Buffering and the Output Queueing Family [Slides in PDF] [Slides Handout in PDF]
Exercises 6 (due 10 Apr. 2013, wk.7.2): Multi-Packet Queue Blocks, Multicast Queues [HTML] [PDF]

Chapter 4: Input Queueing (Time-Space Switching) and Combination Architectures

4.1 Introduction: Time-Space Switching, Single-Queue Input Queueing [Slides - PDF] [Slides Handout - PDF]
Exercises 7 (due 19 Apr. 2013, wk.8.3): Queueing Architectures SRAM Cost [HTML] [PDF]
4.2 Input Queueing with VOQ's: Crossbar Scheduling [Slides - PDF] [Slides Handout - PDF]
4.3 Advanced Topics: Pipelined, Packet-Mode, and Enveloppe Scheduling [Slides - PDF] [Slides Handout - PDF]
4.4, 4.5 Combined Input-Output Queueing (CIOQ), Combined Input-Crosspoint Queueing (CICQ) [Slides - PDF] [Slides Handout - PDF]
Exercises 8 (due 22 May 2013 -wk.11.2): Input Queueing, VOQ Crossbar Scheduling, and their Simulation [HTML] [PDF]
[in 2009 and earlier, this exercise concerned a simulation by hand, rather than in software, of a CIOQ switch with a speedup of 2: 2009 version (HTML)]

Chapter 5: Switching Fabrics, Inverse Multiplexing

[Slides - PDF] [Slides Handout - PDF]:
- 5.1 Byte Slicing, Inverse Multiplexing (Adaptive/Multipath Routing)
- 5.2 Scalable, Non-Blocking Switching Fabrics
- 5.3 What about Scalable Scheduling?
Exercises 9 (due 27 May 2013 - wk.12.1): TST and Clos Circuit Switch Scheduling [HTML] [PDF]
Exercises 10 (due 29 May 2013, week 12.2): Switching Fabric Topologies [HTML] [PDF]

Chapter 6: Flow Control in Buffered Switching Fabrics

6.1 Credit-Based Flow Control (Backpressure) [Slides - PDF] [Slides Handout - PDF]
6.2 Per-Flow Queueing and Flow Control [Slides - PDF] [Slides Handout - PDF]
6.3 Buffer Space versus Number of Flows [Slides - PDF] [Slides Handout - PDF]
[Alternative source, containing a subset of above material, mostly in a similar form --in a few cases formatted slightly better: ACACES 2007 (Third International Summer School on Advanced Computer Architecture and Compilation for Embedded Systems) - Slides for the course on "Queue and Flow Control Architectures for Interconnection Switches", by Manolis Katevenis, Part 4 of 4, in PDF: [Slides] [Handouts] Flow and Congestion Control in Switching Fabrics]

Previous Years (Spring 2011 and older):
Exercises 11 (due 27 May 2011, week 13.3): Flow control, per-flow queueing [HTML] [PDF]

Chapter 7: Output Scheduling for Quality-of-Service (QoS) Guarantees

7.1 Output Scheduling for QoS [Slides - PDF] [Slides Handout - PDF]
Exercises 12(old 13) (due 8 June 2011, week F): Output Scheduling for QoS [HTML] [PDF]

Other Topics: Please refer to the bibliography pointed below (2003 and older)

Routing Table Lookup and Flow Classification Hardware [references]
Cluster, Storage, System, and smaller Area Networks [references]
Network Processors [references]
Optical Switching [references]

Previous Years:

Spring 2011; Spring 2009; Spring 2008; Spring 2007; Spring 2006.

Spring 2005 (last year with slides in HTML - GIF - JPEG format); Sp. 2004; Sp. 2003; Fall 2001; Sp. 2000; Sp. 1998.