Markov

Solo disponible en BuenasTareas
  • Páginas : 17 (4183 palabras )
  • Descarga(s) : 0
  • Publicado : 3 de mayo de 2011
Leer documento completo
Vista previa del texto
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...
tracking img