01KRUHR  Switching architectures
Teachers: Paolo
Giaccone and Massimo Ruo Roch
Messages
Topics
 Introduction to router architectures and to switching functionalities
 Control and data plane in a switch
 Circuit switching
 Non blocking networks (strictly and rearrangeable)
 Complexity of a switching network
 Time switching
 TSI (implementation)
 Spacetime conversion
 Timemultiplexed space switch
 Multistage switching networks
 Graph representation
 Two stages
 Three stages
 Clos networks
 Clos and Slepian theorems
 Configuration algorithms (Paull)
 Recursive construction
 Benes networks
 Looping algorithm
 Cantor networks
 Selfrouting (Banyan)
 Lee approximation (known also as Pigraphs method)
 Packet switching
 Data plane
 Output queued switches (OQ)
 Average delay and maximum throughput
 Knockout switch: loss probability
 Switches without queues
 Maximum throughput under uniform traffic
 Input queued switches (IQ)
 Head of line blocking
 Switches with single FIFO per input
 Uniform traffic: max throughput 75% 2x2, 68% 3x3 e 58% NxN
 Correlated traffic: max throughput 1/N
 Optimal scheduling and heuristics
 MWM: optimality proof
 MSM: counterexample to show throughput degradation
 TDM for uniform traffic
 Heuristic algorithms: PIM (logN iterations, 63% throughput for single iteration),
RRM (50% throughput for single iteration), iSLIP, iLQF.
 Combined input and output queued switch (CIOQ)
 OQ emulation with speedup 4: MUCF
 QO emulation with speedup 2
 Work conservation with speedup 2: LOOFA
 QoS support with IQ switches
 Frame scheduling
 Birchkoff von Neumann decomposition
 Equivalence with Clos networks
 Multicast support
 Optimal queueing
 Unicast integration
 TATRA
 Forwarding algorithms  table lookup
 Binary trie (noncompressed and Patricia trie)
Support material (A.A.2011/12):
Slides on multistage switching architectures  Part I
 English

Slides on multistage switching architectures  Part II
 English

Exercises with solutions
 English (Revised Fig.1.10)

Slides on router architecture and scheduling algorithms

Download 6
or 3 slides per sheet

Past exams
 here

Notes on Performance Evaluation
of Packet Switches  Download

Notes on Scalability of Delays in Input Queued Switches
 Download

Bibliography
 Circuit switching
 Joseph Y.Hui, "Switching and traffic theory for integrated broadband networks",Kluwer, Boston, copyr. 1990 (chapters: 2.5, 2.6, 3, 5.4, 5.5)
 Achille Pattavina, "Reti di telecomunicazione", I Ed., Mc Graw Hill (chapter: 6)
 Achille
Pattavina, "Switching theory : architectures and performance in
broadband ATM networks", Chichester : Wiley, copyr. 1998
 Packet switching
 H.J. Chao, C.H. Lam, E. Oki,
"Broadband packet switching technologies", New York, Wiley, 2001
 W.J.Dally, B.Towles,
"Principles and practice of interconnection networks", Elsevier, Morgan Kaufman, 2004
 G. Varghese,
"Network algorithmics", Elsevier, Morgan Kaufmann,
2005

What you can find here 
Course description 
Support material 
