logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2019/2020
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 052481 - NETWORK DESIGN
Docente Tornatore Massimo
Cfu 10.00 Tipo insegnamento Corso Integrato
Didattica innovativa L'insegnamento prevede  1.0  CFU erogati con Didattica Innovativa come segue:
  • Blended Learning & Flipped Classroom

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (Mag.)(ord. 270) - CR (263) MUSIC AND ACOUSTIC ENGINEERING*AZZZZ096120 - COMMUNICATION NETWORK DESIGN
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI*AZZZZ096120 - COMMUNICATION NETWORK DESIGN
052481 - NETWORK DESIGN
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA*AZZZZ096120 - COMMUNICATION NETWORK DESIGN

Obiettivi dell'insegnamento
The course is an intergrated course mixing 5 credits of  "Communication network design" and 5 credits of "Foundations of operations research". Both courses are intended to provide the theretical and mathematical basis needed for telecommunication network design.
While  "Foundation of operations research" is a more methodological course which emphasizes  the operations research tools to be employed in network design, "communication network design" offers an overview of different practical network design problems and of the application of mathematical tools for  their solution.

Communication network design

The course is intended to provide students with the knowledge and tools necessary to design communication networks. In the first part of the course the different segments of networks (access, metro and core), with the role of optical-network technologies. Practical network design problems will be solved thorugh mathematical formulations (integer linear programming) and heuristic approaches, also with the help of a laboratory activity based on the open-source software Net2Plan. Various techniques to ensure network survivability against failures will be described. In the second part of the course, fundamental concepts of queuing theory will be introduced to solve capacity planning an network dimensioning problems (based on, e.g., Erlang and Engset formulas) considering different users' behavior.

Foundations of operations research

Operations Research (O.R.) is the branch of applied mathematics dealing with quantitative methods to analyze and solve complex real-world decision-making problems. The course covers some of the fundamental
concepts and methods of O.R. pertaining to graph optimization, linear programming and integer linear programming. The emphasis is on optimization models and efficient algorithms with a wide range of important
applications in engineering and management.

In summary, the course has the following objective:

a) to analyze and design complex telecomunication systems;
b) to apply advanced technology currently implemented in telecom systems;
f) to analyze, comprehend and design optical and wireless communication system;
g) to design telecom networks;
h) to design Internet Engineering systems;


Risultati di apprendimento attesi

Communication network design

Knowledge and Understanding

- Students will learn how to:

-- Use Integer Linear Programming to solve routing and capacity assignment problems
-- Identify the right protection technique given the network characteristics
-- Master fundamental tele-traffic formulas as Erlang B, C and Engset 

 

Applying Knowledge and Understanding

Given specific network characteristics, students will be able to:

-- Model and implement network routing and capacity assignment problems
-- Apply fundamental tele-traffic formulas in realistic case-studies

 

Making judgements

Students will be able to:

-- understand the fundamental principles that govern the design of communication networks
-- identify which protection strategy shall be appied based on service and network characteristics
-- identify which tele-traffic fundamental formula shall be applied in practical capacity planning cases   

Communication

- Students will learn how to present to a network engineer, in written and oral form, the actual design and operation problem that is facing in a communication network

Foundations of operations research

Knowledge and understanding
The students will learn:
- the mathematical language of optimization models and some important classes of models
- the main properties and algorithms (including the worst case complexity) of/for the following graph optimization problems: minimum cost spanning tree, shortest path and maximum flow
- the critical path method for project scheduling
- the geometrical and algebraic aspects of Linear Programming (LP), and an LP algorithm
- the main properties of LP duality, including weak/strong duality and the complementary slackness optimality conditions
- the economical interpretation of the dual of some LP problems
- the main characteristics of Integer Linear Programming (ILP) problems
- the cutting plane method with fractional Gomory cuts
- the Branch-and-Bound method for ILP and other combinatorial optimization problems
- the concepts of recognition problems and reduction
- the definitions of the problem classes NP, P, and NP-complete
- the implications for a computational problem to be NP-complete or NP-hard.

Applying knowledge and understanding
The students will be able to:
- build optimization models starting from the decision problem descriptions, solve them using a mathematical modeling language and a state-of-the-art solver, and interpret the output.
- identify an appropriate graph optimization algorithm to tackle a given decision problem and apply it to small examples
- apply the LP method to textbook examples
- construct the dual of LP problems in explicit and parametric form
- apply the studied ILP methods (Branch-and-Bound method, cutting plane method with fractional Gomory cuts) to small examples
- leverage on the acquired theoretical and algorithmic knowledge to answer simple questions.

Making Judgements
- The students will learn how to tackle complex decision-making problems with a solid mathematical and algorithmic approach, which can be adapted and extended to deal with a variety of real-world problems.

Communication skills

- Write in symbolic form complex network-design mathematical models


Argomenti trattati

 

Communication network design

1 –  Introduction on Optical Networks

Optical networking principles and challenges: telecom network overview, business models, traffic engineering vs network engineering vs network design. Enabling Technologies: optical fiber, optical transmitters, optical receivers, optical amplifiers, switching elements, Wavelength Division Multiplexing (WDM).

2 – Exact and Heuristic (Optical Core) Network design methodologies

Network design based on mathematical modelling: flow formulation, route formulation. Modelling of network protection: dedicated protection, shared protection. Network design by heuristic approaches: greedy, local search. Lab activity with Net2Plan: a free and open-source Java tool for the design of communication networks

3 – Protection techniques

Network survivability: objectives and protection techniques. Single-layer and multi-layer protection techniques: protection at IP layer, protection at physical layer. Protection techniques in SONET/SDH: line and section protection, point-to-point and ring structures, dedicated and shared protection. Protection in the optical layer: solutions for ring networks and for mesh network, dedicated-vs-shared protection, ring cover and p-cycle techniques.

5 – Queueing theory primer

Markov, birth death and Poisson process. 

6 –  Capacity dimensioning in communication networks

Introduction on traffic modeling: single and multiple source model. Analysis of multiple-server systems with assumption BCC, BCH, BCD. Evaluation of congestion and statistics of carried/lost traffic (Erlang B and C, Engset).  Capacity dimensioning  with Wilkinson, Fredericks and Lindberger approaches.

 

 

Foundations of operations research

1. Introduction
Decision-making problems. Main steps of an O.R. study. Different types of optimization (mathematical programming) problems. Optimization models (decision variables, objective function, constraints) and modeling
techniques.
2. Graph and network optimization
Optimum spanning trees. Shortest path problems: algorithms for the main variants (including Dynamic programming for acyclic graphs). Application to project scheduling: critial path method and Gantt diagrams.
Maximum flows: Ford-Fulkerson algorithm and maximum flow-minimum cut theorem. Minimum cost flows, matching in bipartite graphs.
3. Basics of computational complexity
Recognition problems, classes P and NP, NP-complete and NP-hard problems. Traveling salesman problem, Integer Linear Programming and other examples.
4. Linear Programming (LP)
LP models. Geometric aspects (vertices of the feasible region) and algebraic aspects (basic feasible solutions). Fundamental properties of linear programming. The Simplex method. LP duality theory: pair of dual
problems, weak and strong duality, complementary slackness conditions. Economic interpretation. Sensitivity analysis. Special cases: assignment and transportation problems.
5. Integer Linear Programming (ILP)
ILP models for, among others, transportation, routing, scheduling and location problems. Formulations and linear programming relaxation. Exact methods: Branch-and-Bound algorithm, cutting plane method with
fractional Gomory cuts.
Time permitting: introduction to heuristic algorithms (greedy and local search).


Prerequisiti


CND: Basic courses of Computer Networks and Statistics.

FOR: Basic knowledge of Multivariate Calculus and Linear Algebra.


Modalità di valutazione

 

Communication network design

The verification of knowledge for the course content consists in a test at the end of the course that comprises a written test and, if required, an oral examination on the subjects covered in the course. Projects, to be defined with the professor, can be used to substitute the oral examination.

The written exam is based on numerical exercises (up to 5) and/or open question (1 or 2) on the topics such as protection, network design thorugh Integer Linear Programming and capacity dimensioning using queueing theory formulas. the written exam is used to assess the capability of the students to manage theoretical and technological tools to design communication networks. The laboratory activity using the software Net2Plan can be used to complement the final written score. 

The oral exam will be used by the instructor to verify student' understading of the fundamental concepts such as enabling technologies for networking, queuing theory behind formulas for capcity dimensioning, protection at different network layers.

In case of negative evaluation the student is admitted to the following tests of the academic year.

 

Foundations of operations research

A written exam which covers all the material presented in the lectures, the sessions devoted to the exercises, and the computer laboratory sessions and assignments. 
 
The exam consists of several questions aimed at evaluating the level of (applying) knowledge and understanding of the main concepts, models, results and methods covered in the course as specified in the expected learning outcomes. In particular, it includes modeling questions, the solution of numerical problems using appropriate algorithms, and theoretical questions related to the main concepts, methods and results.

Bibliografia

Software utilizzato
Nessun software richiesto

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
61:00
91:30
Esercitazione
29:00
43:30
Laboratorio Informatico
10:00
15:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 100:00 150:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Inglese
Disponibilità di materiale didattico/slides in lingua inglese
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.7.2 / 1.7.2
Area Servizi ICT
01/07/2022