Skip to main content

Packet switch architectures

The class is divided in two parts:

  • Theory on switching architectures (prof. Paolo Giaccone)
  • Hardware implementation (prof. Mario Casu)

 

Support material for the first part (2015/16):

  • Slides on multistage switching architectures Download
  • Exercises with solutions Download 
  • Slides on router architecture and scheduling algorithms Download 1, 3, 6 slides per sheet (skip slides 83-104)
  • Notes on Performance Evaluation of Packet Switches Download   
  • Notes on Scalability of Delays in Input Queued Switches Download (not needed for the class)
  • Library to draw generic Clos networks
  • Notes on Hash tables, Cuckoo tables/filters, Bloom filters Download 
  • Notes on data centers Download   
  • Notes on SDN and the design of OpenFlow switches Download (added slides 15-16)
  • Notes on IP processing Download NEW

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

Past exams

Previous exams with solutions (wait before downloading)

Note: all the corresponding exercises till 2015 appear already in the exercise handouts. Possible typos have been corrected only in the excercise handouts.

Topics for the first part of the class

  • 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
    • Multistage switching networks
      • Graph representation
      • Two stages
      • Three stages
        • Clos networks
        • Clos and Slepian theorems
        • Configuration algorithms (Paull)
      • Recursive construction
        • Benes networks
        • Looping algorithm
      • 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
    • Data center architectures
      • Clos based toplologies
      • Google Jupiter topology
    • Software Defined Networking (SDN)
      • Openflow
      • Design of openflow switches
    • Packet processing
      • Hash tables and cuckoo tables
      • Bloom and cuckoo filters
      • Forwarding algorithms - table lookup
        • Binary trie (non-compressed and Patricia trie)