Paolo Giaccone
Courses

HOME PAGE | people | workgroups | software | papers | theses




01KRUHR - Switching architectures
Teachers: Paolo Giaccone and Massimo Ruo Roch
Messages
  • Not present.

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)
      • Space-time conversion
      • Time-multiplexed 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
      • Self-routing (Banyan)
      • Lee approximation (known also as Pi-graphs 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 (non-compressed 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 SwitchesDownload
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 NEW NEW NEW (chapters: 2.5, 2.6, 3, 5.4, 5.5)
    • Achille Pattavina, "Reti di telecomunicazione", I Ed., Mc Graw Hill NEW NEW (chapter: 6)
    • Achille Pattavina, "Switching theory : architectures and performance in broadband ATM networks", Chichester : Wiley, copyr. 1998 NEW NEW
  • Packet switching
    • H.J. Chao, C.H. Lam, E. Oki, "Broadband packet switching technologies", New York, Wiley, 2001NEW
    • W.J.Dally, B.Towles, "Principles and practice of interconnection networks", Elsevier, Morgan Kaufman, 2004 NEWNEW
    • G. Varghese, "Network algorithmics", Elsevier, Morgan Kaufmann, 2005 NEWNEW
What you can find here
Course description
Support material

HOME PAGE | people | workgroups | software | papers | theses

© Networks Group - Politecnico di Torino