Markov

Conceptes fonamentals de xarxes de computadors. Un enfocament analític.

Conceptes fonamentals de xarxes de computadors. Un enfocament analític.
J.M. Barceló, Ll. Cerdà, J. García.

Temario: • Cadenas de Markov y teoría de colas.
Ll. Cerdà, 9 horas.

• Traffic models.
J.M. Barceló , 6 horas.

• Complex Networks.
J.M. Barceló, 3 horas.

• No Markovian models.
J. García , 3 horas.• IP lookup and packet classification.
J. García , 3 horas.

• Output scheduling.
J. García , 3 horas.
1
Ll. Cerdà.

Conceptes fonamentals de xarxes de computadors. Un enfocament analític.

Tema 1: Cadenas de Markov y teoría de colas
• Cadenas de Markov en tiempo discreto. • Cadenas de Markov en tiempo continuo. • Teoría de colas.
–M/M/1. – M/G/1. – Reversibilidad en el tiempo(Burke). – Redes de Jackson y redes cerradas.

2
Ll. Cerdà.

Conceptes fonamentals de xarxes de computadors. Un enfocament analític.

Espacio de probabilidad
• Espacio muestral (Ω) = conjunto de todos los posibles sucesos (ω) • Evento aleatorio: conjunto de sucesos que cumplen una cierta condición (es un subconjunto de Ω). A = {ω ∈ Ω : ω cumple una cierta condición} • Espacio de probabilidad: esuna tripleta (Ω, F, P) donde: • F es una familia de eventos aleatorios. • P asigna una probabilidad a cada evento aleatorio de F.

3
Ll. Cerdà.

Conceptes fonamentals de xarxes de computadors. Un enfocament analític.

Familia de eventos y definición de probabilidad
• La familia de eventos aleatorios F ha de cumplir: • Tiene el evento Ω, • Si los eventos A y B son de F, també lo son A+B,AB, Ac,Bc. • Si los eventos Ai, i=1,2,… son de F, también lo son ΣAi i ΠAi • Las probabilidades asignadas a los eventos de F han de cumplir (definición axiomática de probabilidad): • P[A] ≥ 0 • P[Ω] = 1 • Si AiAj = ∅, i ≠ j, P[ΣAi] = Σ P[Ai] • Si Ai es una partición de A, P[A] = Σ P[Ai]
4
Ll. Cerdà.

Conceptes fonamentals de xarxes de computadors. Un enfocament analític.

Ejemplo
•Experimento: lanzar una moneda tres veces. • Espacio muestral: Ω = {CCC, CCX, CXC, CXX, XCC, XCX, XXC, XXX} • Ejemplos de posibles eventos: • A = {sale una cara} = {CXX, XCX, XXC} • B = {salen al menos dos caras} = {CCC, CCX, CXC, XCC} • Ejemplo de una familia de eventos: • F = {Ω , ∅, A, B, A+B, Ac,Bc, (Ac+B)c} • A menudo F no se da explícitamente porque se deduce del modelo.
5
Ll. Cerdà.

Conceptesfonamentals de xarxes de computadors. Un enfocament analític.

Variable aleatoria (VA)
• Es una función definida sobre el espacio muestral Ω de un espacio de probabilidad (Ω, F, P). • Asigna un número real X(ω) a cada posible suceso ω ∈ Ω. • Para cada número x, {ω | X(ω) ≤ x} es un evento de F. • Normalmente se suprime la dependencia funcional con ω y se escribe X en lugar de X(ω) y {X ≤ x} enlugar de {ω | X(ω) ≤ x}. • Una VA puede ser discreta o continua.

6
Ll. Cerdà.

Conceptes fonamentals de xarxes de computadors. Un enfocament analític.

Ejemplo
• Experimento: lanzar una moneda tres veces. • Espacio muestral: Ω = {CCC, CCX, CXC, CXX, XCC, XCX, XXC, XXX} • Definimos la VA X = nombre de caras en el primer y último lanzamiento: • {X = 0} = {XCX, XXX} • {X = 1} = {CXX, CCX,XXC, XCC} • {X = 2} = {CXC, CCC}

7
Ll. Cerdà.

Conceptes fonamentals de xarxes de computadors. Un enfocament analític.

Proceso estocastico
• Es un conjunto de VAs: {X(t) : t ∈ Γ} definidas en un mismo espacio de probabilidad. • Normalmente el índice t representa un tiempo y X(t) el estado del proceso estocástico en el instante t. • El proceso puede ser de tiempo discreto o continuo si Γés discreto o continuo. • Si el proceso es de tiempo discreto, usamos enteros para representar el índice: {X1, X2, ...}

8
Ll. Cerdà.

Conceptes fonamentals de xarxes de computadors. Un enfocament analític.

Ejemplo: cola con un único servidor
llegadas salidas

Podemos definir los procesos estocásticos: • A(t): número de llegadas hasta el instante t. • D(t): número de salidas hasta el...