Stochastic Network Modelling

You are here

Home » Studies » Masters » Master in Innovation and Research in Informatics » Curriculum » Syllabus » Stochastic Network Modelling
Credits
6
Types
Specialization compulsory (Computer Networks and Distributed Systems)
Requirements
This subject has not requirements, but it has got previous capacities
Department
AC
This course is an introduction to stochastic processes and their application to computer networks. Stochastic processes are described as a sequence of random variables that models the evolution of a system. The course will give a solid background in Markov chains, the most popular analytic tool to model stochastic processes. The course is intended to be as practical as possible, using toy problems to apply all theoretical results presented in the course. About half of the theoretical classes will be dedicated to solve problems. The aim is that through the solution of many insightful examples the students will learn the art of mathematical modeling using Markov chains.

Teachers

Person in charge

  • Llorenç Cerdà Alabern ( )

Weekly hours

Theory
2
Problems
2
Laboratory
0
Guided learning
0
Autonomous learning
0

Competences

Technical Competences of each Specialization

Computer networks and distributed systems

  • CEE2.1 - Capability to understand models, problems and algorithms related to distributed systems, and to design and evaluate algorithms and systems that process the distribution problems and provide distributed services.
  • CEE2.2 - Capability to understand models, problems and algorithms related to computer networks and to design and evaluate algorithms, protocols and systems that process the complexity of computer communications networks.
  • CEE2.3 - Capability to understand models, problems and mathematical tools to analyze, design and evaluate computer networks and distributed systems.

Generic Technical Competences

Generic

  • CG1 - Capability to apply the scientific method to study and analyse of phenomena and systems in any area of Computer Science, and in the conception, design and implementation of innovative and original solutions.
  • CG3 - Capacity for mathematical modeling, calculation and experimental designing in technology and companies engineering centers, particularly in research and innovation in all areas of Computer Science.

Transversal Competences

Reasoning

  • CTR6 - Capacity for critical, logical and mathematical reasoning. Capability to solve problems in their area of study. Capacity for abstraction: the capability to create and use models that reflect real situations. Capability to design and implement simple experiments, and analyze and interpret their results. Capacity for analysis, synthesis and evaluation.

Objectives

  1. Being able to model a process that evolves over time with a discrete and continuous time Markov chain
    Related competences: CTR6, CEE2.1, CEE2.2, CEE2.3, CG1, CG3,
  2. Being able to compute the steady state and transient solution of a Markov chain
    Related competences: CTR6,
  3. Being able to model processes that engage the formation of queues
    Related competences: CEE2.3, CTR6, CG3,
  4. Being able to resolve the basic queues: M/M/1, M/G/1, M/G/1/K
    Related competences: CTR6, CEE2.3,

Contents

  1. Introduction
    Concept of probability space, sequence of random variables and stochastic processes.
  2. Discrete Time Markov Chains (DTMC)
    Definition of a DTMC, Transient Solution, Classification of States, Steady State, Finite Absorbent Chains
  3. Continuous Time Markov Chains (CTMC)
    Definition of a CTMC, Transient Solution, Steady State, Semi-Markov Process and Embedded MC, Finite Absorbent Chains
  4. Queuing Theory
    Kendal Notation, Little Theorem, PASTA Theorem, The M/M/1 Queue, M/G/1 Queue, Reversed Chain, Reversible Queues, Networks of Queues, Chains with Matrix Geometric Solutions

Activities

Activity Evaluation act


Probability Review



Theory
4h
Problems
4h
Laboratory
0h
Guided learning
0h
Autonomous learning
12h

Discrete time Markov Chains


Objectives: 1 2 3
Theory
12h
Problems
12h
Laboratory
0h
Guided learning
0h
Autonomous learning
36h

First assessment



Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2h
Autonomous learning
10h

Continous time Markov chains


Objectives: 1 2 3
Theory
7h
Problems
4h
Laboratory
0h
Guided learning
0h
Autonomous learning
21h

Second assessment



Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2h
Autonomous learning
10h

Queueing theory


Objectives: 1 2 3 4
Theory
5h
Problems
6h
Laboratory
0h
Guided learning
0h
Autonomous learning
15h

Final exam


Objectives: 1 2 3 4
Week: 15
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
15h

Teaching methodology

There will be 4 hours per week, dedicated to theoretical classes to explain the theory and solve problems. The students' activities will consist of reading material and solving practical problems that will be proposed at each theoretical unit. The problems will be collected and corrected during the course. There will be research oriented problems to be solved using numerical tools as MATLAB.

Evaluation methodology

The theory mark will be calculated from the problems delivered by the student, assessment marks and a final exam mark. The formula for calculating the mark for the course is:

NF = 0.1 * NP + 0.15 * max{EF, C1} + 0.15 * max{EF, C2} + 0.60 * EF

where:
NF = final mark
EF = final theory exam
NP = Problems delivered by the students
C1,C2 = marks of midterm assessments

Bibliography

Basic:

Complementary:

Previous capacities

Probability, random variables and distribution (continuous and discrete) algebra: systems of equations, determinant, eigenvalues ​​and eigenvectors, diagonalization.