Politecnico di Torino
Politecnico di Torino
Politecnico di Torino
Academic Year 2016/17 (first time established in A.Y.2010/11)
Packet switch architectures
Master of science-level of the Bologna process in Computer And Communication Networks Engineering - Torino
Teacher Status SSD Les Ex Lab Years teaching
SSD CFU Activities Area context
F - Altre (art. 10, comma 1, lettera f)
B - Caratterizzanti
Abilitΰ informatiche e telematiche
Ingegneria delle telecomunicazioni
Subject fundamentals

The course focus is on the design of switching architectures for high-speed packet switches, providing complementary (theoretical and practical) approaches. The main reference scenarios are IP routers, Ethernet switches, Network-on-Chip, data centers and Software Defined Networking (SDN)-enabled switches. At the end of the class, the student will be able to design the architecture of a high-speed packet switch, analyze its performance and implement part of it in hardware.
Expected learning outcomes

The class provides the following:
• Knowledge of the main building blocks of a high-speed packet switching architecture
• Knowledge of complexity and performance evaluation of interconnection networks
• Ability to design multistage and self-routing switching networks and the corresponding routing algorithms
• Ability to design the interconnection network for large data centers
• Knowledge of packet queueing architectures and packet scheduling algorithms
• Knowledge of theoretical tools for performance analysis
• Knowledge of algorithms and data structures for address lookup and traffic classification
• Knowledge of SDN switching paradigm
• Knowledge of functional verification through CAD tools
• Ability to describe digital circuits through VHDL language
• Knowledge of implementation on FPGA and/or integrated circuits
• Ability to evaluate performance (speed/area/power) through CAD tools
• Knowledge of digital electronic components used in packet switch architectures for computation, lookup, and storage
Prerequisites / Assumed knowledge

- Probability theory: random variable and its moments, statistical independence, Bernoulli and Poisson processes, discrete distributions (geometric, binomial, Poisson)
- Basic graph theory and flow maximization algorithms on bipartite graphs
- Elements of discrete mathematics: recursive equations, factorial number and Stirling approximation, binomial coefficient, Landau notation
- Queueing theory: stability, M/G/1 queue
- Basic knowledge of telecommunication and computer networks
- IP addressing and longest prefix matching
- Basic digital electronic circuits
- Behavior and basic structure of a computing system
- High-level programming languages

The class is divided in two parts, the first on the theory of packet switching architectures (5 credits) and the second one on the hardware implementation (3 credits).

Lectures topics and corresponding credits:
• General concepts: data plane and control plane. Multistage switching architectures (2cr)
• Input queued switches and packet scheduling algorithms. Output queued switches, combined input-output switches. (2cr)
• IP lookup/classification. Data center design and SDN (1cr)
• Modeling of digital circuits through hardware description languages, description of combinatorial and sequential digital circuits (1cr)
• Implementation of building blocks of packet switching architectures: serializers, deserializers, queues, finite state machines, arbiters, switching fabrics (1cr)
• Programmable logic circuits (FPGA and PLD), application-specific integrated circuits (ASIC), network-processors, memory-blocks RAM/CAM (1cr)
Delivery modes

The class includes lectures and exercises in classroom and lab practical exercises.
Exercises in lab aim to development, synthesis and implementation of digital systems described through VHDL language.
Texts, readings, handouts and other learning resources

The teaching material (handouts) will be made available by the class teachers on the didattica web portal.
The following books are not required but are useful as a reference:
• 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", John Wiley & Sons, 1998
• 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
Assessment and grading criteria

The final exam is written and covers all topics taught during the course. It is divided in two parts:

• one part (70 minutes) on the theory of packet switching architectures
• one part (60 minutes) on the hardware implementation of packet switching architectures

The final grade of the exam will be obtained by the credit-based weighted average among the two parts.

Programma definitivo per l'A.A.2015/16

© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
WCAG 2.0 (Level AA)