PDF de programación - Cálculo de bloqueo en la RTB

ARQUITECTURA DE REDES, SISTEMAS Y SERVICIOS

Área de Ingeniería Telemática

Cálculo de bloqueo en la RTB

Area de Ingeniería Telemática

http://www.tlm.unavarra.es



Arquitectura de Redes, Sistemas y Servicios

Grado en Ingeniería en Tecnologías de

Telecomunicación, 2º


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Temario

Introducción

1. 
2.  Arquitecturas de conmutación y protocolos
3. 
4.  Control de acceso al medio
5.  Conmutación de circuitos

Introducción a las tecnologías de red

La Red Telefónica Básica

1. 
2.  Modelado de usuarios
3.  Cálculos de bloqueo

6.  Transporte fiable
7.  Encaminamiento
8.  Programación para redes y servicios


Objetivos

•  Conocer y aplicar el cálculo de probabilidades de

bloqueo empleando la Erlang-B


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Probabilidad de bloqueo
•  Llegadas según proceso de Poisson de tasa λ
•  Duración exponencial de media s
•  Número de servidores ocupados en cada instante de

tiempo es aleatorio (I)


s
o
d
a
p
u
c
o

#

I líneas ocupadas

Llegadas
Poisson

…!

tiempo

Duración
exponencial

Probabilidad de bloqueo
•  Normalmente dispondremos de recursos finitos (capacidad)
•  Cuando la variable I toma valor = número de servidores, el

sistema está en BLOQUEO

•  ¿ Cuál es la probabilidad de que el sistema esté en situación de

bloqueo ?


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Todos los servidores
ocupados = BLOQUEO


s
o
d
a
p
u
c
o

#

tiempo

Si llegan llamadas durante el
tiempo de bloqueo son rechazadas


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I



I

I

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Problemas de interés

•  ¿ Cuál es la probabilidad de que una llamada

encuentre el sistema ocupado ?

•  ¿ Cuál es el número de líneas necesarias para una

probabilidad objetivo ?

•  ¿ Cuál es el tráfico que atraviesa ese sistema y

forma la carga del siguiente sistema ?


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I



I

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Probabilidad de bloqueo

•  En un sistema con
–  Llegadas Poisson(λ)
–  Duraciones Exp(1/s)
–  Tráfico de entrada A = λs
–  k servidores
–  Las llamadas que llegan al sistema bloqueado se pierden
–  Probabilidad de bloqueo: ¿Cuál es P[I=n]? (…)

•  P[I=n] = B(a,k)
•  B(a,k) es conocida como función B de Erlang (o

•  Válida con cualquier distribución de tiempo de

ErlangB)

servicio (i.i.d.)

B de Erlang


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

•  Fórmula:

B(A,k) =

Ak
k!
Ai

k
∑
i= 0

i!

•  Cálculo recursivo:

B(A,0) =1
B(A, j) =

A ⋅ B(A, j −1)
A ⋅ B(A, j −1) + j

€


o
e
u
q
o
l
b

e
d

d
a
d

i
l
i

b
a
b
o
r
P

€

€

K=5

K=10

K=15

K=20

K=25

K=30

A (intensidad de tráfico, Erlangs)


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I



I

I

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Ejemplo

entrar a una centralita

•  1000 líneas llegan a un concentrador que selecciona 50 para
•  Los usuarios generan un tráfico de 40 Erlangs
•  ¿ Cuál es la probabilidad de bloqueo ?

1000 líneas

40 Erlangs

50 líneas

…!

…!


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Ejemplo

entrar a una centralita

•  1000 líneas llegan a un concentrador que selecciona 50 para
•  Los usuarios generan un tráfico de 40 Erlangs
•  ¿ Cuál es la probabilidad de bloqueo ?

1000 líneas

40 Erlangs

50 líneas

…!

…!

•  La probabilidad de bloqueo es

Pb=B(40, 50) = 0.0187 casi un 2%


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Tráfico cursado

•  Si un conjunto k de líneas tiene un tráfico ofrecido de I Erlangs
y una probabilidad de bloqueo, ¿cuánto tráfico atraviesa las
líneas?
Esto será el tráfico cursado y será a su vez el tráfico ofrecido
al siguiente sistema al que lleguen las líneas
Ic = Iin (1 - Pb)= Iin (1-B( Iin , k ))

Ic : tráfico cursado
Iin : tráfico ofrecido o de entrada




,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Tráfico de desbordamiento

•  No puede ser cursado por el camino principal (por bloqueo)
•  Se “desborda” (overflow) a una ruta secundaria
•  Un proceso de Poisson del que se eliminan aleatoriamente (iid) muestras con

probabilidad p sigue siendo un proceso de Poisson, pero con menor tasa (pλ)

•  En nuestro caso las llamadas desbordadas suelen ir en bloques
•  Eso da mayores probabilidades de bloqueo que con un proceso de Poisson de

igual media

•  Se aproxima con un proceso de Poisson de mayor tasa
• 

(En los problemas en caso de no disponer de las tablas emplearemos Poisson
de igual tasa, aunque esto es subdimensionar)


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Ejemplo

•  En la centralita A de la figura las llamadas con destino a B se
encaminan si es posible por el enlace directo a B y en caso de
estar ocupado a través de la central primaria

•  ¿ Cuál es el tráfico que cursa el enlace A-C y cuál es la

probabilidad de bloqueo de una llamada de un abonado de A a
uno de B ?

20 líneas

10 líneas

A

C

20 líneas

5 líneas

B

Demanda en Erlangs
Origen
De A
De B
Exterior

a A
2
3
2

a B Al exterior
4.5
4.5
3.2
5
-
2


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Ejemplo

•  Las 5 líneas entre A-B soportan un tráfico de 3+4.5=7.5 Erlangs
•  Al ser 5 líneas la probabilidad de bloqueo es p1 = B(7.5,5) ≈ 0.45

!  Casi la mitad de las llamadas no puede ir por la sección directa
!  Eso genera que un 45% del trafico que iba por ahí acabe yendo por C
!  Definimos: q1 = 1-p1 = 0.55

20 líneas

10 líneas

A

C

20 líneas

7.5 erlangs!

5 líneas

B

Demanda en Erlangs
Origen
De A
De B
Exterior

a A
2
3
2

a B Al exterior
4.5
4.5
3.2
5
-
2


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Ejemplo

•  El enlace entre A-C soporta un tráfico de:

–  Llamadas entre A y el exterior: 4.5 + 2 = 6.5 Erlangs
–  Llamadas entre A y B que no pueden ir directamente: 7.5 x 0.45 = 3.375 E
–  Total 9.875 Erlangs (aproximamos que es Poisson)

•  10 líneas con 9.875 Erlangs de demanda tienen una probabilidad de

bloqueo de p2 = B(9.875,10) ≈ 0.21 (21%) (q2=1-p2=0.79)

•  El enlace A-C tiene una probabilidad de bloqueo en torno al 21%

20 líneas

C
9.875 erlangs!

5 líneas

10 líneas

20 líneas

A

B

Demanda en Erlangs
a B
Origen
4.5
De A
De B
3.2
2
Exterior

a A
2
3
2

Al exterior
4.5
5
-


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Ejemplo

•  El enlace B-C soporta un tráfico de:

–  Llamadas entre B y el exterior: 5 + 2 = 7 Erlangs
–  Llamadas entre A y B que no pueden ir directamente: 7.5 x 0.45 = 3.375 E
–  Total 10.375 Erlangs (aproximamos que es Poisson)

•  20 líneas con 10.375 Erlangs de demanda tienen una probabilidad de

bloqueo de p3 = B(10.375,20) ≈ 0.0027 (0.27%)

•  Prácticamente despreciable (q3 = 1-p3 ≈ 1 comparado con el resto)

20 líneas

10 líneas

A

C

20 líneas

10.375 erlangs!

5 líneas

B

Demanda en Erlangs
a B
Origen
4.5
De A
De B
3.2
2
Exterior

a A
2
3
2

Al exterior
4.5
5
-


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Ejemplo

•  Probabilidades de bloqueo en cada enlace: p1, p2 y p3
•  Asumimos independencia
•  Probabilidad de bloqueo de llamadas entre A y B: que ambos caminos se

bloqueen (A-B y A-C-B)

•  Probabilidad de que se bloquee el camino A-C-B = probabilidad de que se
bloquee al menos uno de los dos (A-C y/o A-C-B) = 1 – probabilidad de que
ninguno de los dos se bloquee

PbloqA−B = p1(1−(1− p2)(1− p3)) = p1(1−q2q3) ≈ p1p2



€

p2

A

C



p3

p1

q2=1-p2, q3=1-p3≈1

B

Demanda en Erlangs
a B
Origen
4.5
De A
De B
3.2
2
Exterior

a A
2
3
2

Al exterior
4.5
5
-


a
c
i
t



,



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

I

I

I



S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Ejemplo

•  Tráfico cursado por el enlace A-C:

!  Ofrecido a A-C-B (el desbordado de A-B) que es cursado: 3.375 x q2q3
!  + tráfico de A con el exterior que es cursado: 6.5 x q2
!  = 3.375 x (1-0.21)(1-