Dept. of Computer Science, University of Crete.
CS-534: Packet Switch Architecture

0. Course Overview

This course lies in between "hardware" and "networks". It deals with the architecture of packet switches and routers --the building blocks of modern high-speed networks. A significant part of this course is analogous to "computer architecture" (CS-425): we study the organization of the digital circuits that are used to implement switches, their interaction with software and with the messages that they route, their alternative architectures and the cost of each of them. We consider, in as unified a way as possible, the structure of the active parts of SAN, LAN, MAN, WAN networks, of the Internet, of digital telephony networks, and of multiprocessor interconnection networks, bringing out their common basis behind the apparently dissimilar communication technology of each. Note, though, that we only study networks consisting of unidirectional, point-to-point links; we do not study any shared medium networks.

Course Content:

Point-to-point links versus shared media. Serial links, parallel links, throughput calculation.
Circuit switching: time-division multiplexing, time/space switching, add-drop multiplexors, inverse multiplexing, introduction to multi-stage fabrics.
Packet switching - basic concepts: throughput on-demand, output contention, internal blocking, head-of-line blocking, buffering, cut-through versus store-and-forward, partitioned versus shared link capacity, statistical multiplexing, scheduling, flow control.
Switch generations: datapath, control; 1st & 2nd generation switches (processor, bus, memory, I/O cards); third generation switches.
Buffer memory architectures: wide, interleaved, pipelined memory; single-queue versus multi-queue buffers, partitioned versus shared space, fixed-size versus variable-size packet queues.
Queueing architectures: crosspoint/output queueing, knock-out, shared buffering; input queueing, input buffering, internal speed-up; performance; scheduling for input buffered switches.
Switching fabric architectures: crossbars, multi-stage networks; hypercube, banyans, fat trees; strictly or rearrangeably non-blocking fabrics, static and adaptive routing, multi-path fabrics; sorting networks, deflection routing, recirculation; bufferless versus buffered fabrics.
Flow control: static/dynamic, lossy/lossless, implicit/explicit, end-to-end/hop-by-hop, rate/credit, indiscriminate/per-flow; wormhole routing, QFC; switching fabrics w. internal backpressure.
Routing table lookup and flow classification hardware.
Scheduling for QoS: fairness, per-flow queueing, fast weighted round-robin schedulers.

Point-to-point links and switches

Output contention, buffering

Switch Architectures

Fabric topologies, flow control, scheduling

[ Up to the Home Page of CS-534 ]