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 (new)
  • The design of data center networks (DCN) Download (new slides 17-24)
  • SDN and the design of high-performance programmable switches Download
  • Slides on fast packet processing Download
  • Slides on programming scheduling algorithms for input queued switches Download (new!)
  • Slides on router architectures and scheduling algorithms Download (not for 2019/20)
  • Notes on Performance Evaluation of Packet Switches Download (not for 2019/20)
  • Library to draw generic Clos networks

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, NFV and virtualization
    • 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
    •  Programming schedulers for input queued switches with VOQ