Switching technologies for data centers

Professors: Paolo Giaccone

Official description of the course: here

The class is divided in two parts:

  • Theory on the design of switching architectures and fast packet processing (prof. Paolo Giaccone)
  • Hardware implementation (prof. Marco Vacca)

Support material for the first part (2018/19):

  • Introduction to data centers Download 
  • Slides on multistage switching architectures Download
  • Exercises on switching architectures, data centers and fast packet processing, with solutions Download
  • The design of data center networks (DCN) Download   
  • Slides on router architectures and scheduling algorithms Download
  • 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 SDN and the design of OpenFlow switches Download   
  • Notes on IP processing Download from Portale della Didattica

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

Note: all the corresponding exercises till 2018 appear already in the exercise handouts available above. Eventual typos have been corrected only in the excercise handouts, thus it is better to study and work on the exercise 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% 2×2, 68% 3×3 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)