Stochastic Network Modeling

You are here

Credits
6
Department
AC
Types
Specialization compulsory (Computer Networks and Distributed Systems)
Requirements
This subject has not requirements
The goal of this course is giving the student a background in stochastic processes and their application to computer networks. This is a methodological course that forms the student in mathematical stochastic modeling.

Teachers

Person in charge

  • Llorenç Cerdà Alabern ( )

Weekly hours

Theory
4
Problems
0
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: CG1, CG3, CEE2.2, CEE2.3, CEE2.1, CTR6,
  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: CG3, CEE2.3, CTR6,
  4. Being able to resolve the basic queues: M/M/1, M/G/1, M/G/1/K
    Related competences: CEE2.3, CTR6,

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

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.30 * max{EF, C} + 0.60 * EF

where:
NF = final mark
EF = final theory exam
NP = Problems delivered by the students
C = average test mark: C = 0.5*C1 + 0.5*C2

Bibliografy

Basic:

  • stochastic processes, and queuing theory: the mathematics of computer performance modeling - Randolph Nelson, Springer , 1995. ISBN:
  • Finite markov chains - J.G. Kemeny and J.L. Snell, Springer , 1960. ISBN:
  • Probability and statistics with reliability, queuing, and computer science applications - K.S. Trivedi, Prentice-hall , . ISBN:

Complementary:

  • An introduction to probability theory and its applications, Volume I - W. Feller, Wiley , . ISBN:

Previous capacities

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