|Politecnico di Torino|
|Academic Year 2017/18|
Switching technologies for data centers
Master of science-level of the Bologna process in Communications And Computer Networks Engineering - Torino
The class is mainly focused on the packet switching technologies for data centers. Data centers are the technological engines that run modern applications such as cloud computing and big data analysis. Two main elements operate in a data center: the servers, which provide computing and storage resources, and the interconnection network, which provides connectivity among the server and towards the Internet. This course will specifically focus on the interconnection network present in large data centers.
Aim of the course is to learn how to design the network for a data center, from the overall architecture to the single switching device. The main topic of the course is faced under a manifold standpoint:
- theoretical, to understand the theory of modular design of interconnection networks and to understand the performance of packet switching networks;
- algorithmic, to devise the control algorithms needed to optimize the network performance;
- practical, to design the hardware for high speed switches.
Expected learning outcomes
At the end of the course, the student will be able to design (i) the interconnection network of a data center, (ii) the architecture of high-speed packet switches, (iii) the hardware implementing the data path of a packet switch.
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
• Knowledge of packet queueing architectures and packet scheduling algorithms
• Knowledge of theoretical tools for performance analysis
• Knowledge of algorithms and data structures for fast packet processing
• Knowledge of SDN switching paradigm
• Knowledge of functional verification through CAD tools
• Knowledge of implementation on FPGA and/or integrated circuits
• Knowledge of digital electronic components used in packet switch architectures for computation, lookup, and storage
• Ability to design multistage and self-routing switching networks and the corresponding routing algorithms
• Ability to design the interconnection network for large data centers
• Ability to describe digital circuits through VHDL language
• Ability to evaluate performance (speed/area/power) through CAD tools
Prerequisites / Assumed knowledge
- Probability theory: random variable and its moments, statistical independence, Bernoulli and Poisson processes, discrete distributions (geometric, binomial, Poisson)
- Fundamentals of queueing theory
- Computer networks based on Internet protocols
- IP addressing and longest prefix matching
- Digital electronic circuits
- Behavior and structure of a computing system
- High-level programming languages (e.g. C)
The class is divided in two parts, the first on the theory of packet switching architectures and interconnection networks (5 credits) and the second one on the hardware implementation (3 credits).
Lectures topics and corresponding credits:
• General concepts: data center networks, data plane and control plane. Multistage switching architectures based on Clos theory (2cr)
• Input queued switches and packet scheduling algorithms. Output queued switches, combined input-output switches. (1.5cr)
• Clos-based design of data centers. Software Defined Networking (SDN) paradigm. (0.5cr)
• Data structures for fast packet processing. Hash tables. Fingerprinting. Bloom filters. Cuckoo filters. Patricia tries. (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)
The class includes lectures and exercises in classroom and lab practical exercises. Exercises in lab aim to develop, synthesize and implement 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 Politecnico courses web portal and is sufficient to cover all the topics taught in the class. In addition, a very large number of previous exams will be available on the website with the solutions.
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, "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 grading criteria are related to the correctness of the proposed solution, to the creativity to solve problems of design and to the capability of using the relevant technical language.
The final exam is written, without the help of any teaching material, and covers all topics taught during the course. It is divided in two parts:
• one part (70 minutes, 3 open questions) on the theory of packet switching architectures and on the design of data center networks.
• one part (60 minutes, 1 open question and a set of multiple choice questions) on the hardware implementation of packet switching architectures
The second part of the exam starts at the end of the first one. The two parts of the exam can be taken independently during one exam and their evaluation is kept valid until the end of the academic year (usually September).
Given that V1 is the grade of the first part of the exam and V2 is the grade of the second part, the final grade Y of the exam will be computed as follows:
X=(5/8*V1+3/8*V2) (i.e., X is credit-weighted average of the two parts)
Y=18+13/12*(X-18) (i.e., the final evaluation is obtained by an extra-bonus on X)
Both V1 and V2 must be >=18 to be considered valid. The final grade will be the nearest integer to Y.
Programma definitivo per l'A.A.2017/18