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

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
    0h

    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.