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 (2019/20):

  • 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 (new slides 17-24)
  • SDN and the design of high-performance programmable switches 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 IP processing Download from Portale della Didattica

Bibliography for the first part

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 for the first part

Note: all the below exams appear already in the exercise handouts available above. Eventual typos have been corrected only in the exercise handouts, thus it is better to study on the exercise handouts.

Topics for the first part

  • 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)
  • Data center architectures
    • cloud computing
    • L2/L3 addressing and routing
    • BGP in a datacenter
    • Clos-based topologies: leaf-spine and multi-layer
    • Google Jupiter topology
  • Software Defined Networking (SDN) and programmable data planes
    • Openflow protocol
    • Design of Openflow switches
    • PISA architecture and P4 language
  • Packet processing
    • Hash tables and cuckoo tables
    • Bloom and cuckoo filters
    • Forwarding algorithms – table lookup
      • Binary trie (non-compressed and Patricia trie)
  • 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