


Politecnico di Torino  
Academic Year 2016/17 (first time established in A.Y.2010/11)  
01QFJOC Packet switch architectures 

Master of sciencelevel of the Bologna process in Computer And Communication Networks Engineering  Torino 





Esclusioni: 01NQT 
Subject fundamentals The course focus is on the design of switching architectures for highspeed packet switches, providing complementary (theoretical and practical) approaches. The main reference scenarios are IP routers, Ethernet switches, NetworkonChip, 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 highspeed 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 highspeed packet switching architecture Knowledge of complexity and performance evaluation of interconnection networks Ability to design multistage and selfrouting 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  Highlevel programming languages 
Contents 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 inputoutput 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), applicationspecific integrated circuits (ASIC), networkprocessors, memoryblocks 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 creditbased weighted average among the two parts. 
