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 Giaccone’s part (2021/22):

  • 0. Solved exercises on switching architectures, data centers and fast packet processing (Download)
  • 1. Introduction to data centers (Download)
  • 2. Slides on multistage switching architectures (Download)
  • 3. The design of data center networks (DCN)¬† (Download)
  • 4. SDN and the design of high-performance programmable switches (Download)
  • 5. Slides on programming scheduling algorithms for input queued switches (Download)
  • 6. Probabilistic data structures and fast packet processing (Download)

Bibliography for the first part

Circuit switching

  • Joseph Y.Hui, “Switching and traffic theory for integrated broadband networks”, Kluwer, Boston, 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 work 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