Aims and Learning outcomes

The course addresses the study of switching and routing systems through a methodological approach.

Fundamental concepts about the internal architectures of routers and switches are first given. The focus of the course is on the approaches and methodologies used to carry out the functions of switching and routing of traffic flows within that equipment. Efficient algorithms for packet-flow classification and buffering management are presented. Switching theory is explained to understand the most common interconnection structures.

The course also comprises hands-on experimental activity: the basic knowledge and tools required for this activity are presented and explained during the laboratory hours.

Syllabus

1 – Introduction

Architecture of the Internet. Router structure: design principles and expected performance.

2 – Rouitng of IP datagrams

Structure of IP addressing. Algorithms with tries. Algorithms based on trees and prefixes. Hardware algorithms.

3 – Packet classification and traffic handling

Classifiers. Classification based on tries. Geometric algorithms. Heuristic algorithms. Network services and quality-of-service parameters.

4 – Interconnection networks

Taxonomy of network interconnection: mono-stage and multi-stage networks, network equivalence and isomorphism. Multistage networks with partial and full interconnection. Banyan networks and network equivalences. Permutation networks: sorting and merging networks.

5 – Multi-stage networks

Three-stage networks. Paull and Slepian-Duguid theorem. Multi-stage networks with full interconnection: Clos theorem and recursive construction.

7 – Fundamentls of packet switching

Classification of switching systems. Buffering strategies. Input queueing, output queueing, shared queueing.

8 – Scheduling in input-queueing switches

Scheduling in VOQ switches. Algorithms for maximum matching and maximal matching.

Prerequisites

None

The verification of knowledge for the course content consists in a test at the end of the course and in the completion of a project activity. The test is an oral examination on the subjects covered in the course. For the experimental activity, students are required to team-work on projects in which they develop router functionalities by Software Defined Networking (SDN) techniques or software simulators to evaluate the performance of a switch/router. In case of negative evaluation the student is admitted to the following tests of the academic year.