logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2018/2019
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) - MI (263) MUSIC AND ACOUSTIC ENGINEERING*AZZZZ096120 - COMMUNICATION NETWORK DESIGN
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI*AZZZZ052481 - NETWORK DESIGN
096120 - COMMUNICATION 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 and plan communication networks. The first part of the course focuses on optical networks: different segments of networks (access, metro and core) are taken into consideration. Design approaches base on mathematical modeling (integer linear programming) and heuristic approaches are discussed. In the second part of the course, traffic theory will be developed for the design of circuit switching networks, and specifically to solve capacity and flow assignment problems and to investigate advanced methodologies for traffic modeling. Specific case studies will be developed to provide examples of the different design approaches.

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 learn the actual design and operation problems in a transport network
- Students choosing to focus on the project will learn how to carry on a research task in collaboration with the instructor

Communication skills

- Describe in written form complex network design solutions
- conduct an oral examination on complex technical aspects related to network design (non mandatory) 

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, Wavelength Division Multiplexing (WDM), WDM Evolution. Enabling Technologies: optical fiber, optical transmitters, optical receivers, optical amplifiers, switching elements.

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. 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 –  Design of circuit switching networks

Introduction: Network and communication services: network types and performance targets. Traffic modeling: definition and properties. Source model: single and multiple source. Analysis of multiple-server system with assumption LCC, LCH, LCR. Evaluation of congestion and statistics of carried/lost traffic. Voice network structure and routing techniques. Dimensioning of overflow trunk: 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 lecturer, can be used to substitute the oral examination. A laboratory activity using the software net2plan can be used to complement the final score. 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

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
62:00
93:00
Esercitazione
30:00
45:00
Laboratorio Informatico
8:00
12: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.6.5 / 1.6.5
Area Servizi ICT
11/08/2020