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.
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.