CS-534 (Sp98) CONTENT & GRADING: 1. INTRODUCTION Three worlds: telephony, the internet, multiprocessor networks. Possible convergence factors, cell-based (ATM) networking, QoS. High-performance: point-to-point links versus shared media. Switching elements, switching fabrics, (sub-) networks. 2. BASIC SWITCHING NOTIONS Circuit versus packet switching. Output contention. Internal blocking. Sustained versus transient contention, buffering. FIFO queueing and head-of-line blocking. Store-and-forward, cut-through. Multiplexing, demultiplexing, inverse multiplexing; partitioned versus shared link capacity, statistical multiplexing. 3. SWITCH GENERATIONS & BUFFER MEMORY ARCHITECTURES Functions in a switch: datapath, control. First and second generation switch organization: processor, bus, memory, I/O cards. Third generation switches. High-throughput buffer memory: wide, interleaved, pipelined memory buffers. Single-queue vs multi-queue buffers, partitioned vs shared space. Fixed-size versus variable-size packet queues. 4. ATM, IP, SWITCHES, ROUTERS Virtual circuits vs datagrams; packet vs cell based networking. Definitions: repeaters, bridges, switches, routers, gateways. ATM networking. The internet. IP over ATM. IP switching, tag switching, MPLS, etc. 5. SWITCH QUEUEING ARCHITECTURES & PERFORMANCE Input queueing, input buffering, internal speed-up, crosspoint queueing, output queueing, knock-out, shared buffering. Scheduling for input buffered switches. Performance of the various organizations. 6. SWITCHING FABRIC TOPOLOGIES & ARCHITECTURES Crossbars, multi-stage networks. Hypercube, banyans, fat trees. Internal blocking, non-blocking, rearrangeably non-blocking fabrics. Static and adaptive routing, multi-path non-blocking fabrics. Sorting networks. Buffered versus bufferless fabrics. 7. OUTPUT SCHEDULING FOR QoS Priorities. Fairness. Per-connection queueing. Round-robin and weighted round-robin scheduling. Service guarantees. 8. FLOW CONTROL, SWITCHING FABRICS WITH INTERNAL BACKPRESSURE End-to-end versus hop-by-hop flow control. Rate-based versus credit-based flow control. Single-lane, multi-lane credit (backpressure) flow control. Wormhole routing, virtual channels (deadlock avoidance, performance) Credit flow control in ATM, buffer sharing, long links, QFC. Resource Allocation under Congestion. Switching fabrics with internal backpressure. Research in multi-path non-blocking switching fabrics with cell resequencing using backpressure. GRADING: * 10 % from the Exercises * 15 % from the presentations of a couple of papers * 35 % from the project * 40 % from the final exam