Skip to main content

Switching technologies for data centers

The class is divided in two parts:

  • Theory on the design of switching architectures and fast packet preocessing (prof. Paolo Giaccone)
  • Hardware implementation (prof. Mario Casu)

 

Support material for the first part (2017/18):

  • Introduction to data centers Download  
  • Slides on multistage switching architectures Download  (NEW!)
  • Exercises with solutions Download      
  • Slides on router architectures and scheduling algorithms Download 1 or 6 slides per sheet
  • Notes on Performance Evaluation of Packet Switches Download  
  • 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  
  • Notes on IP processing 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

Past exams

Previous exams with solutions (wait before downloading)

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

Note that the complete list of old exams is available here

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: WFA, 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)