Faculdade de Engenharia
Departamento de Engenharia Eletrônica
e Telecomunicações
Rev.: Out - 2013
Teoria de Filas e Sistemas de
Comunicação
Prof. Gil Pinheiro
(revisão: Outubro/2013)
Prof. Gil Pinheiro
1
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
1
Programa
Rev.: Out - 2013
•
•
•
•
Revisão de Probabilidade e Estatística
Processos Estocásticos
Teoria de Filas
Os Sistemas de Filas M/M/1, M/M/m,
M/M/m/B, M/M/m/m, M/M/1/B, M/M/,
M/M/N/N/K, M/G/1
• Noções de Engenharia de Tráfego
• Redes de Filas
Prof. Gil Pinheiro
2
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
2
Rev.: Out - 2013
Revisão de Probabilidade e
Estatística
Prof. Gil Pinheiro
3
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
3
Variável Aleatória
•
•
•
•
Rev.: Out - 2013
•
r é um evento no Espaço
Amostral S, r  S
x é a probabilidade associada ao
evento r, onde x é um número
real (x  R) e x  [0 , 1]
A Variável Aleatória X mapeia os
eventos de S em x, assim: X(r) = x
Assim X tem uma distribuição de
probabilidade na reta dos reais
(x  R)
Espaço Amostral
S
r
X(r)
0
x
x
1
Função de Distribuição de Probabilidade (FDP):
A FDP de uma variável aleatória X, também conhecida como Função
de Distribuição Cumulativa é: F(x) = P[X  x] = Prob[r : X(r)  x ]
Prof. Gil Pinheiro
4
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
4
Cálculo da Probabilidade
•
Uma variável aleatória contínua X é descrita através de sua função
distribuição de probabilidade F(x) ou sua função densidade de
probabilidade f(x)
•
Função Distribuição de Probabilidade:
Pr[X  x] = F(x) , onde: F(-) = 0 e F() = 1
Rev.: Out - 2013
•
Função Densidade de Probabilidade:
dF ( x)
f ( x) 
dx
Prof. Gil Pinheiro
então:
F(x) =
x
f(y) dy
-
Sendo:
+
f(y) dy = 1
-
5
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
5
Rev.: Out - 2013
Processos Estocásticos
Prof. Gil Pinheiro
6
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
6
Rev.: Out - 2013
Processo Estocástico
• Processo Estocástico: função ou seqüência aleatória
tempo-dependente
• Seja, por exemplo, n(t) a quantidade de pacotes trafegando
em uma rede de computadores no instante t
• n(t) é uma Variável Aleatória
• n(t) pode ser descrita através de uma Função Distribuição
de Probabilidade
• O tempo de espera, w(t), em uma fila também é uma
Variável Aleatória
Prof. Gil Pinheiro
7
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
7
Processos Contínuos e Discretos
• Processo de Estados Discretos
Número de estados possíveis de um sistema é uma quantidade finita,
ou contável. Também conhecido como Cadeia Estocástica. Ex.:
quantidade de pessoas numa fila, quantidade de celulares conectados
a uma ERB
• Processo de Estados Contínuos
Rev.: Out - 2013
Número de estados possíveis de um sistema é uma quantidade infinita,
ou não contável. Ex.: tempo de conexão de um aparelho telefônico,
tempo de espera numa fila
Prof. Gil Pinheiro
8
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
8
Processos de Markov
• É um Processo Estocástico onde:
Rev.: Out - 2013
– Os estados futuros do processo são independentes dos estados
passados e dependentes apenas do presente
• Para analisar um Processo de Markov não é necessário
conhecer toda a trajetória de estados passados, apenas
o estado anterior (o sistema não possui memória)
• Nome em homenagem a A.A.Markov, que em 1907
definiu e analisou esses processos
• Um Processo de Markov de estados discretos é
chamado Cadeia de Markov
• Aplicação: modelagem de Sistemas de Filas
Prof. Gil Pinheiro
9
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
9
Processos de Nascimento e Morte
• São Cadeias de Markov onde as transições de estado são
restritas a estados vizinhos apenas
• É possível representar o estado através de um número
inteiro
• Exemplo:
nascimento ou chegada
Rev.: Out - 2013
Estado
(pessoas
na fila)
0
1
2

n-1
n
n+1

morte ou partida
Prof. Gil Pinheiro
10
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
10
Rev.: Out - 2013
Teoria de Filas
Prof. Gil Pinheiro
11
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
11
Rev.: Out - 2013
Teoria de Filas
• Ferramenta matemática para tratar de eventos
aleatórios
• É o estudo da espera em filas
• Proporciona uma maneira de definir o
ambiente de um sistema de filas
matematicamente
• Permite prever respostas prováveis e tempos de
espera
Prof. Gil Pinheiro
12
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
12
Teoria de Filas (Objetivo)
• Avaliar o comportamento de um sistema de
filas e seus parâmetros, exemplos:
Rev.: Out - 2013
–
–
–
–
Tempo de espera médio
Probabilidade de formação de fila
Porcentagem de clientes rejeitados pelo sistema
Probabilidade de um cliente esperar mais do que um
certo tempo
– Número médio de clientes na fila
– Probabilidade de que todos os servidores estejam
ociosos
Prof. Gil Pinheiro
13
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
13
Rev.: Out - 2013
Análise de Sistemas de Fila
• Os sistemas de filas diferem entre si de
acordo com as hipóteses que fazemos a
respeito dos padrões de chegada e das taxas
de serviço
• Na análise, precisamos adotar hipóteses
sobre o comportamento do sistema. Caso
contrário, não se tem por onde começar
Prof. Gil Pinheiro
14
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
14
Hipótese: Sobre o Padrão de
Chegada dos Usuários
• Chegam a intervalos regulares?
• Chegam em grupo?
Rev.: Out - 2013
• Chega um de cada vez?
Prof. Gil Pinheiro
15
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
15
Rev.: Out - 2013
Características de um
Sistema de Fila
(Ex.: Usuários de computadores de uso compartilhado)
Prof. Gil Pinheiro
16
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
16
Rev.: Out - 2013
Características de um
Sistema de Fila
1.
2.
3.
4.
5.
6.
Processo de Chegada
Distribuição de Tempo de Serviço
Quantidade de Servidores
Tamanho do Sistema de Fila
População de Clientes
Disciplina de Atendimento
Prof. Gil Pinheiro
17
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
17
Rev.: Out - 2013
1. Processo de Chegada
• Se os clientes chegam em instantes t1, t2, ..., tj a
variável randômica j = tj - tj-1 é chamada Tempo
Interchegadas
• Assume-se que os j formam uma seqüência de
variáveis aleatórias independentes identicamente
distribuídas (v.a. IID)
• O processo de chegada mais comum é o Processo
de Poisson. Isto significa que os Tempos
Interchegadas são exponencialmente distribuídos
• Outras distribuições podem ser utilizadas, tais como
a Hiperexponencial, Erlang e Geral
Prof. Gil Pinheiro
18
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
18
2. Distribuição de Tempo de
Serviço (Processo de Serviço)
Rev.: Out - 2013
• O tempo gasto por cada cliente num computador é
chamado Tempo de Serviço
• É aceitável supor que os Tempos de Serviço de cada
cliente sejam variáveis aleatórias IID
• A distribuição mais utilizada para o Tempo de Serviço é a
Distribuição Exponencial
• Outras distribuições podem ser utilizadas, tais como a
Hiperexponencial, Erlang e Geral
Prof. Gil Pinheiro
19
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
19
Rev.: Out - 2013
3. Quantidade de Servidores
• Single Server – atende a apenas um
cliente de cada vez
• Multi-Server – possui m servidores,
podendo atender m clientes
simultaneamente
• Infinite Server – cada cliente que
chega encontra sempre um servidor
disponível
Prof. Gil Pinheiro
20
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
20
3. Quantidade de Servidores
• Exemplo:
Rev.: Out - 2013
Uma sala de computadores pode possuir um ou
mais computadores idênticos (servidores) e
todos fazendo parte de um sistema de fila único.
Se os computadores não forem idênticos, eles
podem ser subdivididos em grupos de mesmo
tipo, com filas separadas para cada um deles.
Nesse caso, cada grupo é um sistema de fila.
Prof. Gil Pinheiro
21
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
21
Rev.: Out - 2013
4. Tamanho do Sistema
(Capacidade do Sistema)
• Capacidade do sistema = capacidade da fila de
espera + quantidade de servidores (posições de
serviço)
• A capacidade máxima de clientes no sistema poderá
ser limitada por questões de espaço, custo ou para
evitar um tempo de espera muito longo
• Na maior parte dos sistemas, a capacidade da fila é
limitada (finita)
• Em sistemas com filas de capacidade infinita, todos
os clientes serão atendidos
• Em sistemas sem capacidade de espera ou com
capacidade limitada, pode ocorrer rejeição de
clientes
Prof. Gil Pinheiro
22
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
22
Rev.: Out - 2013
5. População de Clientes
• É a quantidade de usuários em potencial que
pode, em algum momento, usar o sistema
(ex.: clientes de banco, programa de
computador, assinante de linha telefônica)
• Nos sistema reais a população é limitada
(finita)
• Quando a população é finita, a taxa de
chegada dependerá da população
• População Infinita – taxa de chegada
constante
• População Finita – taxa de chegada variável
Prof. Gil Pinheiro
23
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
23
6. Disciplina de Serviço
• De uma fila, é o método de escolha da seqüência de
atendimento dos clientes na fila
• A disciplina mais utilizada é a FCFS ou FIFO
(primeiro a chegar é o primeiro a sair da fila)
• Outras disciplinas: LCFS, SIRO, RR
• O atendimento pode ser priorizado em função de:
Rev.: Out - 2013
– Tempo esperado de atendimento, ex.: menos demorado
primeiro
– Tamanho do cliente (pacote de mensagem), ex.: maior
primeiro, menor primeiro
– Maior sensibilidade a atrasos, ex.: mais sensíveis primeiro
– Qualidade de serviço (QoS)
Prof. Gil Pinheiro
24
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
24
Disciplina de Atendimento
(de serviço)
Disciplina de
Serviço
FCFS/FIFO
LIFS/LIFO
SIRO
RD
Rev.: Out - 2013
GD
Descrição
First Come First to be Served
Last In First to be Served
Select In Random Order
Atendimento baseado em prioridade
Distribuição genérica
Ex: algumas centrais telefônicas utilizam SIRO, comutadores de rede
utilizam FIFO
Prof. Gil Pinheiro
25
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
25
Classificação de Sistema de Fila
• Um sistema de fila é classificado por suas
características
• Utiliza-se a Notação de Kendall
A/ S / m / B / K / DS
Rev.: Out - 2013
Onde:
A = Distribuição de tempo interchegada
S = Distribuição de tempo de serviço
m = Número de canais de serviço simultâneo (servidores)
B = Quantidade de Buffers ou capacidade do sistema
K = Tamanho da população
DS = Disciplina de serviço
Prof. Gil Pinheiro
26
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
26
Classificação de Sistemas de Fila Distribuições
• As distribuições utilizadas para o tempo
interchegada e tempo de serviço são
simbolizadas por uma letra, conforme a seguir:
Rev.: Out - 2013
M = Exponencial
Ek = Erlang, com parâmetro K
Hk = Hiperexponencial, com parâmetro K
D = Determinístico
G = Distribuição Genérica
• A distribuição exponencial é chamada
memoryless (M)
• Uma distribuição determinística (D) significa
tempo de chegada e tempo de serviço constante,
ou sem variância
Prof. Gil Pinheiro
27
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
27
Classificação de Sistemas de Fila Exemplo 1
M/M/3/20/1500/FCFS
•
•
•
•
Rev.: Out - 2013
•
•
Tempo interchegada exponencialmente distribuído
Tempo de serviço exponencialmente distribuído
Existem 3 servidores
A fila possui um total de 20 posições de buffer. Consistindo
em 3 buffers para cada servidor, 17 posições de espera
compartilhados entre os tres servidores. Se a quantidade de
clientes no sistema for 20, os clientes que chegam são
perdidos até que a fila diminua
Há uma população de 1500 clientes que podem ser
atendidos
A disciplina de serviço é FCFS (primeiro a chegar, primeiro a
ser servido)
Prof. Gil Pinheiro
28
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
28
Classificação de Sistemas de Fila Exemplo 2
M/M/1
•
Rev.: Out - 2013
•
•
•
•
•
Tempo interchegada exponencialmente distribuído ( =
processo de chegada do tipo Poisson)
Tempo de serviço exponencialmente distribuído
Existe 1 servidor
A fila possui quantidade ilimitada de buffer (default)
A população de clientes é infinita (default)
A disciplina de serviço é FCFS (primeiro a chegar, primeiro
a ser servido) - (default)
Prof. Gil Pinheiro
29
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
29
Classificação de Sistema de Fila outros exemplos
Rev.: Out - 2013
não utilizados
• M/M/1 => M/M/1/  /  / FCFS
- Desprezar os três últimos símbolos quando:
disciplina é FCFS, população infinita e tamanho da fila
infinito
• M/M/
• M/M/1/B
• M/G/1
• M/M/m
• M/D/1
• M/M/m/B
• M/M/m//k
• M/M/m/m
Prof. Gil Pinheiro
30
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
30
Processos de Chegada Processo de Poisson
Hipóteses
• Dois clientes nunca chegam simultaneamente
Rev.: Out - 2013
– O 1º cliente chega no instante t0, o 2º no instante t1
e assim por diante ( 0 < t0 < t1 ,, ... , < tn )
• Os tempos entre chegadas estão distribuídos
exponencialmente
• A taxa de chegada (1/) também terá
distribuição exponencial
Prof. Gil Pinheiro
31
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
31
Processo de Poisson
Número de
Chegadas
• Se a taxa de chegada possui distribuição exponencial,
a probabilidade de k clientes chegarem dentro de T
segundos pode ser modelada pela distribuição de
Poisson:
T T onde:  > 0, k = 0,1,2, ...
Pk (T ) 
e
k!
4
3
2
Rev.: Out - 2013
1
Chegadas
tc1
Prof. Gil Pinheiro
tc2
tc3
tc4
tempo
32
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
32
Processo de Poisson
•
Num sistema com  = 0,4 chegadas/s, em T = 8 s, ocorrerão 3,19959
chegadas aproximadamente. Em média: 0,4 x 8 = 3,2 chegadas
Rev.: Out - 2013
0,25
k
0
1
2
3
4
5
6
7
8
9
10
11
12
Soma =
Pk
0,04076
0,13044
0,20870
0,22262
0,17809
0,11398
0,06079
0,02779
0,01112
0,00395
0,00126
0,00037
0,00010
0,99997
k.Pk
0,00000
0,13044
0,41740
0,66785
0,71237
0,56990
0,36473
0,19452
0,08893
0,03557
0,01265
0,00405
0,00118
3,19959
Pk
Valor médio
0,20
0,15
0,10
0,05
0,00
1
Prof. Gil Pinheiro
2
3
4
5
6
7
8
9
10
11
33
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
12
13
33
k
Propriedades dos Processos de
Poisson
1
2
 =  i
3
A junção de fluxos de Poisson resulta num fluxo de Poisson
Rev.: Out - 2013

p1
p2
p3
1 =  pi
A partição de um fluxo de Poisson resulta em fluxos de Poisson
Prof. Gil Pinheiro
34
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
34
Propriedades dos Processos de
Poisson



>
Partidas de um sistema de fila M/M/1 é um fluxo de Poisson

1
2
Rev.: Out - 2013
3

 i >
Partidas de um sistema de fila M/M/m é um fluxo de Poisson
Prof. Gil Pinheiro
35
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
35
Distribuição Exponencial
•
Um método alternativo para descrever a distribuição de chegadas de clientes
é através do tempo decorrido entre chegadas sucessivas de clientes. A
distribuição de probabilidade F(t), em que o tempo interchegadas (ti) é
menor que t, para a distribuição discreta de Poisson de chegadas, é dada por
(Distribuição Exponencial):
P(tempo interchegadas t) = F(t) = 1 – e–t ,  > 0, t > 0
•
Graficamente, a distribuição
exponencial, de tempos
interchegadas, é mostrada ao
lado
Dado um tempo t no eixo
horizontal, o eixo vertical do
gráfico indica a probabilidade
de chegadas com ti < t
Rev.: Out - 2013
•
Prof. Gil Pinheiro
36
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
36
A Distribuição Exponencial
•
É importante no estudo das filas pois o tempo de serviço pode ser
modelado por uma distribuição exponencial. Exemplos:
– No tráfego telefônico, é a duração de uma ligação
– Numa rede de comutação de pacotes é o tempo de transmissão de um
pacote, que é proporcional ao seu comprimento
•
Rev.: Out - 2013
•
•
Não existe um embasamento matemático que justifique essa hipótese,
porém, a prática se aproxima bastante de uma distribuição exponencial
Além disso, essa hipótese simplifica o tratamento matemático
Do mesmo modo, a distribuição exponencial também pode ser
utilizada com boa aproximação na modelagem do tempo interchegada
Prof. Gil Pinheiro
37
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
37
A Distribuição Exponencial
•
•
Função Densidade de Probabilidade:
Função Probabilidade acumulada:
Rev.: Out - 2013
Densidade de
probabilidade
Prof. Gil Pinheiro
f(t) =
F(t) =
0
, se t < 0
 e–t , se t  0
0
, se t < 0
1 – e–t , se t  0
Probabilidade
acumulada
38
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
38
Propriedades da Distribuição
Exponencial
•
•
Média: E[X] = X =

y . f(y) dy
Variância: V2[X] =
-

y2 . f(y) dy
=1/
= 1 / 2
Rev.: Out - 2013
-
x = 1/
•
Desvio Padrão:
•
Essa distribuição é utilizada para modelar:
( é igual a Média!!! )
– O tempo de serviço em uma central telefônica, o tempo em que um cliente
fica conectado
– Numa rede de comunicação, o tempo de serviço é o tempo necessário para
transmissão de um pacote através de um link de rede
Prof. Gil Pinheiro
39
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
39
Rev.: Out - 2013
Aplicação da Distribuição
Exponencial
•
•
Gráficos do tamanho da fila para diferentes valores de desvio padrão
Quando: desvio/valor médio = 1, temos a Distribuição Exponencial
Prof. Gil Pinheiro
40
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
40
Rev.: Out - 2013
Aplicação da Distribuição
Exponencial
Tempo de residência para diversas relações de
utilização () e desvio padrão ()
Prof. Gil Pinheiro
41
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
41
Rev.: Out - 2013
Notação de Modelos de Fila
 = Tempo interchegada = tempo decorrido entre duas chegadas
sucessivas
Prof. Gil Pinheiro
42
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
42
Notação de Modelos de Fila
Quantidade de servidores idênticos.
Taxa média de chegada, de clientes (=1/E[]). Em alguns sistemas, poderá
depender do estado do sistema (quantidade de clientes).
s Tempo de serviço (de atendimento) de um cliente.

Taxa média de serviço por servidor (=1/E[s])). Para m servidores, a taxa
média de serviço é m
n
Quantidade total de clientes no sistema, também chamada tamanho da fila.
Inclui os clientes em espera por um servidor e os que estão sendo atendidos.
nq Quantidade de clientes aguardando atendimento. É sempre menor que n, pois
não inclui os clientes em serviço.
ns Quantidade de clientes em serviço.
r
Tempo de resposta do sistema. Ou tempo total de residência dos clientes
dentro do sistema de fila (tempo de espera + tempo de atendimento).
w
Tempo de espera para ser atendido. É o tempo decorrido entre a chegada e o
início do atendimento (serviço) do cliente.
Rev.: Out - 2013
m

Todas as variáveis, exceto  e , são variáveis aleatórias.
Prof. Gil Pinheiro
43
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
43
Notação de Modelos de Fila

Rev.: Out - 2013
B

Utilização do servidor (= / )
Tamanho da fila, quando esta for finita (tamanho do Buffer)
Tempo interchegadas (= 1/)
Prof. Gil Pinheiro
44
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
44
Rev.: Out - 2013
Estabilidade dos Sistemas de Filas
• Condição de Estabilidade: se a quantidade de clientes
no sistema aumenta, tendendo a infinito, o sistema é dito
Instável. Para haver estabilidade, a taxa média de
chegada deve ser menor que a taxa média de serviço (
< m). Esta regra não se aplica para população finita e
buffer finito (podem haver clientes rejeitados) – sistema
nunca fica instável
• Utilização de um servidor:  =  / 
 < 1, para Sistema de Fila ser Estável
• População no Sistema: n = nq + ns  E[n] = E[nq]+
E[ns]
• Tempo no Sistema: r = w + s  E[r] = E[w]+ E[s]
Prof. Gil Pinheiro
45
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
45
Equação de Little
• Permite calcular a quantidade de clientes (itens)
em qualquer Sistema de Fila. Resume-se a:
quantidade média = taxa de chegada x tempo médio
de resposta
• Esta relação se aplica a um Sistema Inteiro ou
parte de um Sistema de Fila
• Baseia-se numa visão tipo “Caixa Preta” do
Sistema de Fila
Rev.: Out - 2013
Chegada
s
Prof. Gil Pinheiro
Sistema de
Fila
(Caixa Preta)
Partidas
46
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
46
Equação de Little - Aplicação
• A equação de Little pode ser aplicada a um subsistema
ou todo o sistema de Fila.
Rev.: Out - 2013
Quantidade
Tempo
Prof. Gil Pinheiro
47
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
47
Equação de Little - Aplicação
• Aplicando a equação de Little num subsistema
ou em todo o sistema de Fila:
Rev.: Out - 2013
– Na fila de espera: nq =  . w
– No servidor:
ns =  . s =  / 
– No sistema inteiro: n =  . r
Prof. Gil Pinheiro
48
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
48
Equação de Little - Exemplo 1

Rev.: Out - 2013
(chegadas)
Buffer

(partidas)
Transmissor

(partidas)
Linha de
Transmissã
o
• Se  é a taxa de chegada numa linha de transmissão,
nq é a quantidade média de pacotes esperando no
buffer (não sendo transmitidos), e w é o tempo
médio gasto por um pacote no buffer. Então, pela
equação de Little:
nq =  . w
Prof. Gil Pinheiro
49
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
49
Rev.: Out - 2013
Equação de Little – Exemplo 2
• Numa sala de espera de um consultório, há 15
clientes em média e taxa de chegada é de 1 cliente
a cada 30 segundos. Calcule o tempo médio de
espera dos clientes na sala. Os clientes são
atendidos na ordem de chegada (FIFO).
Temos que:
nq =15  = 2 clientes/minuto
Aplicando a equação de Little na fila: nq =  . w
Tempo de espera na fila: w = 15 / 2 = 7,5 minutos
Prof. Gil Pinheiro
50
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
50
Rev.: Out - 2013
O Sistema de Fila M/M/1
Prof. Gil Pinheiro
51
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
51
O Sistema de Fila M/M/1
Rev.: Out - 2013
• Sistema de fila com um servidor –
Exemplo: clientes na fila do caixa eletrônico
Prof. Gil Pinheiro
52
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
52
Modelo do Sistema de Fila M/M/1
Modelo
Rev.: Out - 2013
Simbologia
Prof. Gil Pinheiro


53
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
53
Rev.: Out - 2013
Características do Sistema de
Fila M/M/1
• Processo de chegada tipo Poisson (M)
• Tempo de serviço - distribuição exponencial
(M)
• Quantidade de servidores (= 1)
• Infinitas posições na fila de espera (clientes não
são perdidos)
• Disciplina de serviço do tipo FIFO
• População de clientes é infinita (taxa de
chegada é constante)
Prof. Gil Pinheiro
54
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
54
Sistema de Fila M/M/1 Diagrama de Transição de Estados
0
Estado:
0
1
1
1
2

2
2
n-2
3
n-1
n–1
n-1
n
n
n
n+1
n+1
n+1

n+2
Rev.: Out - 2013
Estado = quantidade total de clientes no sistema
Para o sistema M/M/1, temos:
n =  (Cte), n = 0, 1, 2, .... (taxa de chegadas no sistema)
n =  (Cte), n = 1, 2, 3, .... (taxa de partidas do sistema)
Prof. Gil Pinheiro
55
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
55
Estados do Sistema M/M/1
Distribuição de
Poison na chegada
Tempo de serviço exponencial
com média 1


n
Estado
1 partida,
0 chegadas
0 partidas, 0 chegadas
ou
1 partida, 1 chegada
n+1
Rev.: Out - 2013
Mudanças de estado
possíveis entre os
instantes t e t + t
n
0 partidas,
1 chegada
n-1
t
Prof. Gil Pinheiro
t
t + t
Tempo
56
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
56
Rev.: Out - 2013
Estados do Sistema M/M/1
• Um sistema de fila M/M/1 será estudado a
seguir visando determinar seu equilíbrio, ou
seja, quando atinge a condição de regime
permanente
• Nessas condições, o sistema pode ser
identificado através de suas propriedades
estatísticas (tempo de espera, tempo de
residência, tamanho da fila, tempo de espera
na fila, etc)
• Esse estudo poderá ser estendido para
outros sistemas de fila (M/M/N, M/M/N/N, etc)
Prof. Gil Pinheiro
57
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
57
Cálculo do Estado do Sistema
.t
n–1
.t
n
.t
n+1
.t
As 4 condições para haver n clientes no sistema em t + t:
1.
2.
Rev.: Out - 2013
3.
4.
Haviam n+1 pacotes no sistema em t, no intervalo t houve 1 partida e
nenhuma chegada
Haviam n-1 pacote no sistema em t, no intervalo t houve 1 chegada e
nenhuma partida
Haviam n pacotes no sistema em t, no intervalo t não houve partida e
nem chegada
Haviam n pacotes no sistema em t, no intervalo t houve 1 partida e 1
chegada
Prof. Gil Pinheiro
58
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
58
Rev.: Out - 2013
Transições de Estado (resumo)
Estado Inicial
(Instante t)
Eventos Durante
t
Estado Final
(t+t)
n+1 clientes
1 partida + 0
chegada
n
n-1 clientes
0 partida + 1
chegada
n
n clientes
0 partida + 0
chegada
n
n clientes
1 partida + 1
chegada
n
Prof. Gil Pinheiro
59
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
59
Cálculo do Estado do Sistema
Relembrando que:
(1 chegada)
(T)k e- t
P(k=1) =
1!
( t)k e- t
P(k=1, T=t) =
1!
(.t)2+ .... ]
= .t [ 1 - .t +
2!
Então, para o processo de chegada:
Onde T = t , sendo t pequeno, logo:
P( k = 1 e com T = t ) =  t + 0(t )
0(t ) / .t
P( k = 0 e com T = t ) = 1   t + 0(t )
Rev.: Out - 2013
O tempo de serviço obedece a distribuição exponencial, assim as partidas
também seguem um processo de Poisson, então:
P(1 partida em t ) =  t + 0(t )
P(0 partida em t ) = 1   t + 0(t )
Prof. Gil Pinheiro
60
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
60
Cálculo do Estado do Sistema
Estado
1 partida,
0 chegadas
0 partidas, 0 chegadas
ou
1 partida, 1 chegada
n+1
n
0 partidas,
1 chegada
n-1
t
t
t + t
Tempo
pn(t+t) = pn(t).[1 – .t – 0(t)].[1 – .t – 0(t)]
+ pn(t).[.t + 0(t)].[.t + 0(t)]
Rev.: Out - 2013
+ pn+1(t).[1 – .t – 0(t)].[.t + 0(t)]
Expressão
A
Prof. Gil Pinheiro
+ pn-1(t).[.t + 0(t)].[1 – .t – 0(t)]
61
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
61
Cálculo do Estado do Sistema
Quando n=0:
p0 (t+ t) = p0 (t).[1 – . t – 0( t)].[1 – . t – 0( t)]
+ p0 (t).[ . t + 0( t)].[ . t + 0( t)]
Expressão B
+ p1 (t).[ . t + 0( t)].[ . t + 0( t)]
Da expressão B:
Lim
Rev.: Out - 2013
t 0
p0 (t – t) – p0 (t)
= – .p0 (t) + .p1 (t)
t
d p0 (t)
= – .p0 (t) + .p1 (t)
dt
Em regime permanente:
d p0 (t)
 – .p0 (t) + .p1 (t) = 0
= 0
dt
Prof. Gil Pinheiro
62
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
62
Cálculo do Estado do Sistema
Logo:
p1 = 

p0

Utilização:  =

Para n  1
Lim
Rev.: Out - 2013
t0
Teremos:
Prof. Gil Pinheiro
pn(t – t) – pn(t)
t
Ignorando os termos em t2
e de ordem superior
d pn(t)
= –.pn(t) – .pn(t) + .pn-1(t) + .pn+1(t)
dt
63
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
63
Cálculo do Estado do Sistema
Em regime permanente:
d pn (t)
= 0
dt
( + ).pn = .pn-1 + .pn+1
n 1
n=0
.p1 = .p0
Para a fila M/M/1:
pn =
Rev.: Out - 2013
Para:
> 1
N ∞
 n (1- )
1 -  n+1
= 

Para n  1:
pn =  n (1- )
Prof. Gil Pinheiro
64
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
64
Cálculo do Estado do Sistema
População média no sistema em regime permanente:


n.p
n =
E[n] =
n.n .(1- ) =
n=1
n=1



1–
Tempo de residência no sistema, utilizando a Lei de Little:
E[r] = E[n] /  =
/
1
(1 – )
1
=
.(1 – )
=
( – )
Rev.: Out - 2013
Tempo na fila de espera:
E[w] = E[r] – E[s] =
1
.(1 – )
Prof. Gil Pinheiro
–
1
=


( – )
65
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
65
Sistema de Fila M/M/1 Gráfico de Chegadas e Partidas
Número de
Chegadas/Partidas
6
5
C(t)
4
r4
3
r
2
r
3
P(t)
2
1
r1
Chegadas
Rev.: Out - 2013
n
tc1
tc2
tc3
tc4 tc5
tc6
tempo
Partidas
tp1
Prof. Gil Pinheiro
tp2
tp3
tp4
66
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
66
Sistema de Fila M/M/1 Quantidade de Clientes no Sistema
Clientes no Sistema
6
5
Estado Médio do Sistema (n)
4
3
2
1
Rev.: Out - 2013
Chegadas
tc1
tc2
tc3
tc4 tc5
tc6
tempo
Partidas
tp1
Prof. Gil Pinheiro
tp2
tp3
tp4
67
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
67
Rev.: Out - 2013
Tempo de Resposta
Sistema de Fila M/M/1 Tempo de Resposta do Sistema
Tempo de Resposta
Médio (r)
1
Prof. Gil Pinheiro
2
3
4
5
6
Número da Chegada
68
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
68
Sistema de Fila M/M/1 Cálculo do Estado do Sistema
 = Taxa de chegada (por unidade de tempo)
 = Taxa de serviço (por unidade de tempo)
2. Utilização do servidor (=intensidade de tráfego):    / 
3. Condição de Estabilidade:   1
4. Probabilidade de zero clientes no sistema: p0 = 1 – 
5. Probabilidade de n clientes no sistema:
pn = P[N = n] = (1 – )n , n = 0, 1, 2, ....
6. Probabilidade de haver mais que n clientes no sistema:
pn+ = P[R > n] = n
7. Quantidade média de clientes no sistema: n = /(1– )
8. Quantidade média de clientes na fila: nq = 2/(1– )
9. Tempo de residência (tempo de resposta) médio: r = 1 / [ (1 – )]
10. Probabilidade acumulada do tempo de residência:
P[ r  t ]= 1 – e–t(1)
Rev.: Out - 2013
1. Parâmetros:
Prof. Gil Pinheiro
69
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
69
Sistema de Fila M/M/1 -
Cálculo do Estado do Sistema
•
•
Rev.: Out - 2013
•
P(r < t) é a probabilidade do
tempo de residência ser menor
do que t
Do gráfico, para t = 1.2 rmédio ,
então P(t) = 0.7, é a
probabilidade de um cliente ter
seu tempo de residência menor
que 1.2 rmédio
Sendo rmédio o tempo médio de
residência = 1/(1–)
11. q-Percentil do tempo de residência: m(q) = r ln [ 100 / (100 – q) ]
m(q): é o tempo máximo de residência para q (%) de clientes
12. Tempo médio de espera na fila: w = nq /  = (2 /  ) / (1 - )
Prof. Gil Pinheiro
70
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
70
Rev.: Out - 2013
Sistema de Fila M/M/1 Exemplo 1
Um servidor de rede esta associado a 100 computadores através de uma
rede (LAN). O servidor mantêm um banco de dados para consultas dos
computadores. O tempo médio de resposta de uma consulta no servidor é
de 0,6 segundos e o desvio do tempo é igual a média. No horário de pico, a
taxa de consultas atinge a taxa de 20 consultas/minuto. Responda as
seguintes questões:
(1) Qual o tempo de resposta médio?
(2) Se o tempo de resposta máximo aceitável for 1,5 s (para 90% das
consultas), qual o percentual de aumento de tráfego?
(3) Com um acréscimo de 20% de tráfego, qual o aumento no tempo de
resposta?
Prof. Gil Pinheiro
71
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
71
Sistema de Fila M/M/1 Exemplo 1
s
Rev.: Out - 2013
c
c
c
...
c
Assumindo um modelo M/M/1 para o sistema servidor, rede e micros. Os
atrasos na rede (tempo de propagação) e as colisões) são ignorados.
(1) Tempo de Resposta Médio:
• Taxa de chegada:  = 20 / 60 = 1/3 clientes/segundo
• Taxa de atendimento:  = 1 / 0,6 = 10 / 6 clientes/segundo
• Intensidade de tráfego (=utilização do servidor):    /  = 1/3 x 6/10
= 0,2
• Tempo de Resposta do Sistema: r = 1 / [(1 – )]  0,6 / (1 – 0,2) =
0,75 s (=0,6 s no atendimento + 0,15 s na fila de espera do servidor)
Prof. Gil Pinheiro
72
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
72
Rev.: Out - 2013
Sistema de Fila M/M/1 Exemplo 1
(2) Aumento de tráfego:
• Acréscimo no Tráfego quando r = 1,5 s para 90 % das requisições:
1,5 = r x ln[100/(100 - 90)] então: r = 0,65
• Como r = (1/) / (1 – )  (1/1,667) / (1 – )  0,65
• Logo:   0,077
• Assim, a intensidade de tráfego () deve cair de 0,2 para 0,077 para
que o tempo de residência (r) caia de 0,75 para 0,65
(3) Acréscimo no tempo de resposta:
• A intensidade de tráfego (utilização) foi aumentada em 20%, então: 
= 0,2 + 0,2 = 0,4
• Logo: r = (1/) / (1 – )  (1/1,667) / (1 – 0,4) = 1,00 s
Prof. Gil Pinheiro
73
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
73
Rev.: Out - 2013
Sistema de Fila M/M/m
Prof. Gil Pinheiro
74
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
74
Rev.: Out - 2013
Sistema de Fila M/M/m
• Sistema com m servidores iguais
• Cada servidor possui uma taxa de serviço igual a 
• Sistema sem perdas - se todos os servidores estiverem
ocupados, novos clientes aguardam na fila de espera
Prof. Gil Pinheiro
75
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
75
Sistema de Fila M/M/m Diagrama de Transição de Estados

Estado:
0


1


2.

m–1
(m1). m.

m

m+1
m.

m.
Rev.: Out - 2013
Para o sistema M/M/m:
n =  , n = 0, 1, 2, ..., 
n =
Prof. Gil Pinheiro
n. , n = 1, 2, 3, ..., m-1
m., n = m, m+1, m+2, m+3, ..., 
76
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
76
Sistema de Fila M/M/m Cálculo do Estado do Sistema
1. Parâmetros:  = Taxa de chegada
 = Taxa de serviço
m = Quantidade de servidores
2. Utilização (intensidade de tráfego) média de um servidor:   (/m) / 
3. Condição de Estabilidade:   1
4. Intensidade de tráfego do sistema (dos m servidores): ’   / 
Rev.: Out - 2013
5. Tempo de residência médio:
Pq 
1
r  1 
  m(1   ) 
6. Quantidade média de clientes no sistema:
Prof. Gil Pinheiro
 .Pq
n  m. 
(1   )
77
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
77
Sistema de Fila M/M/m Cálculo do Estado do Sistema
7. Tempo de espera médio, sendo:
Rev.: Out - 2013
Logo:
w
Prof. Gil Pinheiro
sPq
m(1   )

sPq
Pq 

w  r  s  s 1 
s
 m(1   ) 
m A
78
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
78
Sistema de Fila M/M/m Cálculo do Estado do Sistema
Pq = probabilidade de todos os servidores estarem ocupados (ocorre
formação de fila). Onde:
(.m)m P0
Pq =
m! (1)
A equação anterior é conhecida como equação de Erlang-C. Tendo sido
tabulada e é bastante utilizada em sistemas de telefonia.
P0 = probabilidade do sistema estar vazio (sem clientes). Dada por:
Rev.: Out - 2013
m-1
P0 =

n=0
Prof. Gil Pinheiro
(.m)n
n!
(.m)m
+
1
m! (1)
79
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
79
Exemplo: Sistema M/M/2
1. Tempo de residência médio:
r=
1/
(12)
2. Quantidade média de clientes no sistema: n =
Rev.: Out - 2013
3. Probabilidade de formação de fila:
Prof. Gil Pinheiro
Pq =
2
12
22
1
80
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
80
Rev.: Out - 2013
Sistema de Fila M/M/
Prof. Gil Pinheiro
81
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
81
Rev.: Out - 2013
Sistema de Fila M/M/
• Sistema com quantidade infinita de servidores
• Todo o cliente que chega ao sistema encontra um
servidor livre e é imediatamente atendido
• Taxas de chegada e de serviço possuem distribuição
exponencial
• Não existe fila de espera, o comprimento da fila e o
tempo de espera são nulos
• É um sistema que introduz apenas um atraso
equivalente ao tempo de serviço
• Utiliza as equações do sistema M/M/m na situação
limite, quando m = 
Prof. Gil Pinheiro
82
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
82
Sistema de Fila M/M/

• Probabilidade de sistema vazio: p0  e 
• Probabilidade de n clientes no sistema:
n

Rev.: Out - 2013
 e 
pn   
   n!
Para n > 0
• Quantidade de clientes no sistema:
1
r

• Tempo médio de residência: 
Prof. Gil Pinheiro
n 
83
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
83


Rev.: Out - 2013
Sistema de Fila M/M/m/B
Prof. Gil Pinheiro
84
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
84
Sistema de Fila M/M/m/B
Rev.: Out - 2013
•
•
•
•
•
Distribuição do tempo entre chegadas: Exponencial
Distribuição do tempo de serviço: Exponencial
Quantidade de Servidor(es): m
Capacidade do Sistema: B
Trata-se de um sistema com m servidores e B buffers,
onde B  m (cada servidor possui uma posição de
buffer)
• Se as B posições estiverem ocupadas, os clientes
subseqüentes são perdidos
Prof. Gil Pinheiro
85
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
85
Sistema de Fila M/M/m/B Diagrama de Transição de Estados
0
Estado:
0
m-2

1
1
Rev.: Out - 2013
1
2
m-1
m–1
m-1
m
m
m
m+1
m+1
k-1

m+1 m+2
B
b
Estado = quantidade de clientes no sistema
Para o sistema M/M/m/B , onde B  m
n =  , n = 0, 1, 2, ..., B-1 e n = 0, para n  B
n = n. , n = 1, 2, 3, ..., m
e n = m., para n > B
Prof. Gil Pinheiro
86
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
86
Sistema de Fila M/M/m/B Diagrama de Transição de Estados

Estado:
0


1

Rev.: Out - 2013

2.

m–1
(m1). m.

m

m+1
m.
m.


B
m.
Estado = quantidade de clientes no sistema
Sistema M/M/m/B , onde: B(buffers)  m(servers)
Prof. Gil Pinheiro
87
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
87
Sistema de Fila M/M/m/B
• Probabilidade do sistema estar vazio, nenhum servidor
ocupado:
m
n 1
B  m 1
m1
(
)
 1 
(
(
m )
m ) 
p0  1 


(
)
m
!
1


n
!
n

1


Rev.: Out - 2013
• Probabilidade de haverem n clientes no sistema:
n
(
m )

Para n < m:
pn
Para m ≤ n ≤ B:
mm  n
pn 
p0
m!
Prof. Gil Pinheiro
n!
p0
88
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
88
Sistema de Fila M/M/m/B
• Probabilidade do sistema estar vazio, nenhum servidor
ocupado:
1
(
)
 1   Bm1 (m )m m1 (m )n 
p0  1 


(
)
m
!
1


n
!
n 1


Rev.: Out - 2013
• Probabilidade de haverem n clientes no sistema:
n
(
m )

Para n < m:
pn
Para m ≤ n ≤ B:
mm  n
pn 
p0
m!
Prof. Gil Pinheiro
n!
p0
89
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
89
Sistema de Fila M/M/m/B
• Quantidade de clientes na fila:
Rev.: Out - 2013
• Tempo de espera na fila: w 
Prof. Gil Pinheiro
nq 
B
 (n  m) p
n  m 1
n
nq
'
90
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
90
Casos Particulares
do Sistema M/M/m/B
Rev.: Out - 2013
• O sistema M/M/m/B pode originar dois
tipos de sistemas de fila:
– Sistema M/M/m/m, onde m=B, que é aplicável a
sistemas de capacidade m e quantidade de
servidores m, sem espaço de espera. Cada um dos
m servidores comporta um cliente
– Sistema M/M/1/B, onde m=1, que é aplicável a
sistemas de capacidade B e 1 servidor. Ou seja, B1 posições de espera
Prof. Gil Pinheiro
91
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
91
Rev.: Out - 2013
Sistema de Fila M/M/m/m
Prof. Gil Pinheiro
92
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
92
Sistema de Fila M/M/m/m
Rev.: Out - 2013
•
•
•
•
•
Distribuição do tempo entre chegadas: Exponencial
Distribuição do tempo de serviço: Exponencial
Quantidade de Servidor(es): m
Capacidade do Sistema: m
Trata-se de um sistema com m servidores e de
capacidade m (1 posição por servidor), sem espaço de
espera
• Se os m servidores estiverem ocupados, os clientes
subseqüentes são perdidos (ocorre bloqueio do
sistema)
Prof. Gil Pinheiro
93
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
93
Sistema de Fila M/M/m/m
1.
Sistema M/M/m/m, sem espaço de espera
2. Número de posições em serviço =
número de servidores (não há fila de espera)
3.
Chamadas que chegam: 
’
1

2


3

Rev.: Out - 2013
4.
Chamadas bloqueadas: .Pb
5.
Chamadas não bloqueadas: ‘ .(1Pb)
6.
Pb = probabilidade dos m servidores
(linhas) estarem bloqueados (ocupadas)
Prof. Gil Pinheiro
.Pb
(Bloqueio)
m

94
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
94
Sistema de Fila M/M/m/m
 (m ) 
p

Probabilidade de nenhum cliente no sistema: 0 

n
!
n

0


n
m
Probabilidade de n clientes no sistema:
pn
n
(
m )

n!
1
p0
(m )m
Rev.: Out - 2013
Probabilidade de bloqueio do sistema P[n=m]:
Prof. Gil Pinheiro
pb 
m!
m
(m )n

n!
n 0
95
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
95
Sistema de Fila M/M/m/m
Número médio de clientes no sistema: n 
m
 np
n 1
n
Taxa de chegada efetiva (clientes não rejeitados):
m1
m1
n 0
n 0
 '   pn    pn   (1  pb )
Rev.: Out - 2013
Tempo de residência: r  n  s
'
Prof. Gil Pinheiro
96
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
96
Sistema de Fila M/M/m/m
• Quando n=m, todas as linhas estão
ocupadas, as próximas requisições serão
bloqueadas
• A probabilidade de bloqueio será:
Pb =
(m)m / m!
onde:
=/
m
 (m) / i!
i
Rev.: Out - 2013
i=0
A equação anterior também é conhecida como distribuição Erlang-B de bloqueio, distribuição
de Erlang ou equação de perdas de Erlang do tipo B
Prof. Gil Pinheiro
97
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
97
Rev.: Out - 2013
Sistema de Fila M/M/1/B
Prof. Gil Pinheiro
98
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
98
Rev.: Out - 2013
Sistema de Fila M/M/1/B
• Sistema com 1 servidor e B-1 posições de
espera
• Caso particular do sistema M/M/m/B, onde
m=1
• Fila de espera possui tamanho finito, então
podem haver clientes perdidos, ou rejeitados
(bloqueio do sistema)
• Como todo o sistema com capacidade de fila
limitada, é sempre estável (<).
Prof. Gil Pinheiro
99
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
99
Sistema de Fila M/M/1/B
• Probabilidade de sistema vazio:
p0 
1 
1   B 1
p0 
para  ≠ 1
1
B 1
para  = 1
• Probabilidade de n clientes no sistema:
pn  p0  n 
1 
n

1   B 1
para 0 ≤ n ≤ B
• Probabilidade de bloqueio:
Rev.: Out - 2013
pb  PB]  p0  B 
Prof. Gil Pinheiro
1 
B

1   B1
100
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
100
Sistema de Fila M/M/1/B
• Número de clientes no sistema:
( B  1)  B 1
n

1 
1   B 1
Rev.: Out - 2013

Prof. Gil Pinheiro
101
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
101
Rev.: Out - 2013
Sistema de Fila M/M/N/N/K
Prof. Gil Pinheiro
102
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
102
Sistema de Fila M/M/N/N/K
• Sistema representado esquematicamente conforme a
figura:


1
2
1
2
Rev.: Out - 2013

K
N


T  n.

• Sistema com N servidores, população K finita (onde: K
 N). Sem espaço de espera
• A taxa de serviço  possui distribuição exponencial
• Em dado instante, existirão n clientes (onde: 0 ≤ n ≤ N)
e cada um será atendido por um único servidor
• Se n > N, pode haver rejeição de clientes (bloqueio)
Prof. Gil Pinheiro
103
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
103
Sistema de Fila M/M/N/N/K
• Pode ser utilizado para modelar:
Rev.: Out - 2013
– Uma central telefônica com K assinantes
entradas e N troncos de saída
– Uma ERB com K usuários e N freqüências
de RF (canais)
Prof. Gil Pinheiro
104
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
104
Rev.: Out - 2013
Sistema de Fila M/G/1
Prof. Gil Pinheiro
105
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
105
Sistema de Fila M/G/1
Rev.: Out - 2013
• Sistema de fila onde a taxa de serviço
atende a distribuição Geral
• Pode ser utilizado, por exemplo, para
modelar o tráfego em:
– Sistemas com prioridade não preemptivos
– Sistemas onde o tempo de serviço está
dividido em classes conhecidas
Prof. Gil Pinheiro
106
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
106
Sistema de Fila M/G/1
• Quantidade de clientes no sistema:
   

1  1   2 2 
n  

 1    2
• Tempo de residência no sistema:
 1   

1  1   2 2 
 
  1    2

• Tempo de espera na fila:
r
(
n
(
)
)
w r s
Rev.: Out - 2013
• Um caso particular do sistema M/G/1 é o M/D/1
(sistema determinístico), onde: =0
Prof. Gil Pinheiro
107
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
107
Rev.: Out - 2013
Noções de Engenharia
de Tráfego
Prof. Gil Pinheiro
108
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
108
Comutação de Circuitos
•
1
2
1
Central de
Comutação
M
2
•
•
N
Rev.: Out - 2013
•
Prof. Gil Pinheiro
Numa central de comutação de
circuitos podem haver M circuitos
de entrada e N circuitos de saída
Cada circuito pode ser um canal
do tipo full-duplex
Cada circuito de entrada estará
conectado a uma saída durante
um certo tempo (tempo de
conexão)
Se M>N, uma entrada poderá
não ter uma saída disponível,
num determinado instante de
tempo, se os N circuitos de saída
estiverem ocupados, ocorrendo
um bloqueio
109
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
109
Central Telefônica
•
1
2
1
2
Central
Telefônica
•
•
M
N
•
AN / N!
Pb =
•
N

Ai / i!
•
Rev.: Out - 2013
i=0
Onde:
A = (N.) /  = N.
Prof. Gil Pinheiro
Uma central telefônica típica utiliza
uma central de comutação de circuitos
Possui M assinantes e N linhas tronco
(trunk), onde: M >> N
Não há espera por linha livre, então a
central pode ser modelada por um
sistema de fila do tipo M/M/m/m, onde
m=N
A taxa de chegada de chamadas para
as N linhas tronco é: N.
A intensidade de tráfego total,
oferecida para as N linhas tronco, é
dada pela letra A
A probabilidade de perdas (ligações
rejeitadas) é calculada utilizando a
equação de perdas do tipo B de Erlang
110
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
110
Tráfego Telefônico
•
•
Rev.: Out - 2013
•
A equação de perdas Erlang-B pode ser usada para
dimensionar sistemas telefônicos. Fornecendo uma estimativa
da probabilidade de ocupação (bloqueio) dos troncos (linhas), a
partir da demanda (tráfego) e da quantidade de linhas (troncos).
Erlang – É uma unidade de tráfego telefônico, definida como a
quantidade de tempo, em horas (ou minutos), gasta para
atender todas as ligações que entram num sistema durante
uma hora (ou um minuto) de funcionamento.
EXEMPLO:
– Numa central telefônica com 100 linhas, qual a demanda produzida
se cada linha recebe, em média, 2 chamadas / hora e essas têm
duração média de 3 minutos?
Solução:
chegam à central 100 x 2 = 200 chamadas por hora, que ocupam
200 x 3 = 600 minutos = 10 horas. Conseqüentemente, o tráfego é
de 10 horas por hora, ou seja: 10 erlang.
Prof. Gil Pinheiro
111
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
111
Tráfego Telefônico
•
•
•
•
Rev.: Out - 2013
•
A central telefônica possui N linhas, que podem operar
simultaneamente
Cada linha possui uma ocupação média de s unidades de
tempo (segundos, minutos, ... ), que é a duração média de uma
chamada
A demanda da central telefônica é de N. chamadas por
unidade de tempo
Cada linha possui uma intensidade de tráfego igual a , onde:
– Duração média de uma ligação: s
– Taxa de serviço por linha:  = 1/s
– Intensidade média de tráfego por linha:  = /
A intensidade de tráfego total é simbolizada pela letra A e o
tráfego total (de todas as linhas) oferecido à central será:
– A = N. = N./
Prof. Gil Pinheiro
112
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
112
Tráfego Telefônico
•
Rev.: Out - 2013
Pb = Probabilidade de Bloqueio
1
0.9
0.8
•
0.7
•
0.6
0.5
0.4
0.3
•
0.2
0.1
0
0
2
4
6
8
10
Quando aumenta-se a
quantidade de linhas da
central, o tráfego por linha
diminui
Resultando na diminuição da
probabilidade de bloqueio
Quando a quantidade de
linhas é maior que a
intensidade de tráfego (N >
A), resulta  < 1, ocorrendo
uma quede brusca na
probabilidade de bloqueio
O gráfico ao lado mostra que
Pb cai bruscamente quando
A/N =  < 1
12
A/N
Prof. Gil Pinheiro
113
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
113
Rev.: Out - 2013
Dimensionamento de Centrais
Telefônicas
• Dada uma certa intensidade de tráfego (em
Erlangs)
• Avalia-se a probabilidade de bloqueio (ou de
perda) para diferentes quantidades de
troncos da central
• Ver gráfico Probabilidade de Bloqueio x
Quantidade de Troncos (linhas)
• O gráfico é obtido a partir da equação de
perdas de Erlang-B
Prof. Gil Pinheiro
114
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
114
Probabilidade de Bloqueio
x Quantidade de Linhas
1
Probabilidade de Bloqueio
0.9
0.8
0.7
0.6
0.5
0.4
30
0.3
25
0.2
Rev.: Out - 2013
0.1
0
0
5
A=5
10
10
15
15
20
20
25
30
35
Quantidade de Linhas (N)
Prof. Gil Pinheiro
115
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
115
Exemplo - 1
1
•
Probabilidade de Bloqueio
0.9
0.8
0.7
0.6
•
0.5
0.4
0.3
A=10
0.2
•
Rev.: Out - 2013
0.1
0
0
5
10
15
20
25
Quantidade de Linhas (N)
Prof. Gil Pinheiro
30
35
Dada uma intensidade de tráfego
máxima de 10 erlangs, avalia-se
a quantidade de troncos
necessária para uma
probabilidade de bloqueio
No gráfico, verifica-se a
quantidade de linhas necessárias
para uma probabilidade de
bloqueio (ou perda) esperada
Para o cálculo também se utiliza:
calculadora programável, tabela
de Erlang, programa de
microcomputador
116
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
116
Rev.: Out - 2013
Tabela de Erlang do tipo B
Exemplo: Sistema do tipo M/M/N/N com A=2.158 Erlangs, N=7 linhas. Probabilidade
de bloqueio: Pb=0,005 (B= 0,5%)
Prof. Gil Pinheiro
117
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
117
Exemplo - 2
• Determinar a quantidade de linhas de
saída de uma central onde:
Rev.: Out - 2013
– Probabilidade de perdas: 0,5 %
– Quantidade de chamadas (m.): 31 por
minuto
– Duração média das chamadas: 3 minutos
Prof. Gil Pinheiro
118
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
118
Exemplo - 2
• Tráfego oferecido: A (m./) = 31x3 = 93
erlangs
• Achar N, tal que: Pb (A,N) < 0,005
• Calculando iterativamente:
–
–
–
–
Pb(93,115)=0,0034
Pb(93,114)=0,0042
Pb(93,113)=0,0051
N=114
Rev.: Out - 2013
• A central deve possuir 114 troncos de saída
Prof. Gil Pinheiro
119
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
119
Verificar o Dimensionamento
de uma Central Telefônica
Rev.: Out - 2013
• Avaliar o desempenho de uma central
telefônica com N troncos
• Um parâmetro de desempenho de uma
central telefônica é a probabilidade de
bloqueio para diversas intensidades de
tráfego (A)
Prof. Gil Pinheiro
120
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
120
Probabilidade de Bloqueio
x Tráfego
1
Probabilidade de Bloqueio
0.9
0.8
0.7
N=5
0.6
10
15
0.5
20
0.4
25
30
0.3
0.2
Rev.: Out - 2013
0.1
0
0
10
20
30
40
50
60
Intensidade de Tráfego (A - Erlangs)
Prof. Gil Pinheiro
121
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
121
Avaliação de uma Central
• Dada uma central com
– N=100 linhas
– s = 5 minutos / ligação
– Pb < 0,4 %
Rev.: Out - 2013
• Determinar
– Máxima intensidade de tráfego admissível
– A máxima taxa de chegada de ligações
para não ocorrer bloqueio
Prof. Gil Pinheiro
122
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
122
Rev.: Out - 2013
Avaliação de uma Central
• Tráfego oferecido: A = ?
• Probabilidade de perda: Pb(A,100) < 0,004
• Calculando iterativamente:
– Pb(79,100) = 0,003074
– Pb(80,100) = 0,003992
– Pb(81,100) = 0,00511
• Amax = 80 erlangs
• Sendo: A = m. = m./ = m..s
• Logo: max = 80/(100x5) = 0,16 chamadas/min.
Prof. Gil Pinheiro
123
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
123
Análise de um Concentrador
Rev.: Out - 2013
• 10 terminais estão conectados a um concentrador de
terminais
• Cada terminal gera um pacote a cada 8 segundos
• Pacotes têm 960 bits de comprimento em média
• Linha de saída com capacidade de 2400 b/s
• Tamanho do pacote e tempo entre chegadas de
pacotes com distribuição exponencial
• Determinar:
– Ocupação média do buffer
– Atraso médio no sistema
– Tempo médio de espera na fila
Prof. Gil Pinheiro
124
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
124
Sistema com Espera
Rev.: Out - 2013
• Quando as requisições podem esperar uma
linha livre, haverá fila de espera.
• Se a capacidade da fila for muito grande, não
haverá rejeição de clientes.
• O modelo M/M/m (sem perdas) pode ser
utilizado
• Central PABX com espera
–m = 8 linhas de saída.
–A = 4,5 Erlangs
–Calcular a probabilidade de espera
Prof. Gil Pinheiro
125
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
125
Sistema com Espera
Rev.: Out - 2013
• Os sistemas com espera e capacidade
infinita (muito elevada) são modelados
pelo sistema M/M/m
• Sendo a intensidade de tráfego A=(m.)/
• A probabilidade de espera (fila) será dada
pela equação de Erlang-C:
Pq =
Am
P0
m! (1A/m)
Prof. Gil Pinheiro
m-1
Onde:
P0 =

n=0
An
n!
Am
+
1
m! (1)
126
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
126
Sistema com Espera
• PBX
Rev.: Out - 2013
–Capacidade 40 ramais
–Cada ramal realiza diariamente, em média,
54 ligações
–A duração de cada ligação é, em média, 3
minutos
• Qual é o número de troncos de saída
necessários para uma probabilidade 5%
de espera?
• Qual o tempo de espera?
Prof. Gil Pinheiro
127
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
127
Rev.: Out - 2013
Sistemas com Prioridade
• Em sistemas com prioridade, os clientes são
atendidos pelo servidor conforme a
prioridade
• Num sistema com prioridade, cada classe de
prioridade é alocada em uma fila. Existirão
tantas filas quanto as classes pré-definidas.
• Normalmente, o servidor é alocado à fila de
menor prioridade, passando a atender outra
fila ao chegar um cliente de maior prioridade
Prof. Gil Pinheiro
128
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
128
Rev.: Out - 2013
QoS – Qualidade de Serviço
• A qualidade de serviço é necessária para adequar o
desempenho da rede ao atraso admissível para uma
determinada aplicação
• Um dos problemas do tráfego de redes é a latência, que
é decorrente da espera em filas de switches (FIFOs), do
desempenho aleatório do tráfego da rede, etc.
• Aplicações de multimídia requerem baixa latência, da
ordem de dezenas de milissegundos
• São definidas classes para os fluxos de dados, ao
passarem pelos switches, os fluxos de maior prioridade
são enviados primeiro num segmento de rede. Para
isso, são criadas filas de saída por classe de tráfego,
para cada segmento de rede.
Prof. Gil Pinheiro
129
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
129
Arquitetura de um Switch
Ethernet
Rev.: Out - 2013
Filas de
saída
Prof. Gil Pinheiro
130
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
130
Tipo de Serviço e Prioridade
- Exemplos
Prioridade do
Datagrama IP
Rev.: Out - 2013
Prioridade do Quadro
(VLAN)
Prof. Gil Pinheiro
131
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
131
Rev.: Out - 2013
QoS - Classes de Prioridade
(Conforme a IEEE 802.1D)
Prof. Gil Pinheiro
132
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
132
Rev.: Out - 2013
Comparação dos Sistemas STDM
x TDM Determinísticos e não
Determinísticos
Prof. Gil Pinheiro
133
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
133
Rev.: Out - 2013
Comparação dos Sistemas
TDM e STDM
• Serão avaliados os sistemas de transmissão do tipo
TDM (Time Division Multiplexing) e STDM (Statistical
Time Division Multiplexing) não determinísticos ou com
algum grau de determinismo
• O determinismo geralmente é utilizado em sistemas
onde o Jitter elevado é um fator restritivo no projeto do
sistema de transmissão, por exemplo, em sistemas de
voz ou vídeo em tempo real
• Na transmissão de dados, onde os atrasos não são
críticos, os sistemas não determinísticos são mais
eficientes
• O determinismo será considerado em dois aspectos, na
taxa de chegada e na taxa de serviço da informação a
ser transmitida
• Para simplificar a análise, serão avaliados sistemas com
134 de informação
apenas
dois
fluxos
134
Prof. Gil Pinheiro
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
Rev.: Out - 2013
Sistemas TDM e STDM não
determinísticos
Prof. Gil Pinheiro
135
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
135
Rev.: Out - 2013
Sistema TDM
• O sistema TDM reserva o uso do canal de maneira
determinística. Ou seja, para cada fluxo de
informação há uma fração exata da capacidade do
canal
• Porém, o TDM deixa de ser eficiente quando aloca
um canal a um fluxo que não possui informação para
transmitir (a informação não chegou ao MUX,
multiplexador) ou não chegou totalmente durante a
reserva do canal)
• Os pacotes de informação de cada fluxo possuem
taxas de chegadas e de atendimento com distribuição
exponencial
Prof. Gil Pinheiro
136
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
136
Rev.: Out - 2013
Sistema TDM
• A capacidade disponível no canal (μ) é
dividida entre os 2 fluxos de informação no
domínio do tempo
• Teremos então, dois canais dedicados com
capacidade (μ/2) cada um
• Se cada fluxo possui taxa de chegada λ/2
• Como as taxas de chegada e de serviço
possuem distribuição exponencial, cada fluxo
é um sistema tipo M/M/1 com tempo de
resposta: r  1  2  2s
1

2
Prof. Gil Pinheiro


 
(1   )
2
137
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
137
Sistema STDM
Rev.: Out - 2013
• Diferente do TDM, que reserva parte do
canal, haja ou não informação disponível
• O sistema STDM reserva o uso do canal de
maneira não determinística, alocando toda a
capacidade do canal ao fluxo que estiver
pronto para ser enviado
• Considerando que os pacotes de informação
da cada fluxo cheguem com uma taxa
distribuição exponencial
Prof. Gil Pinheiro
138
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
138
Rev.: Out - 2013
Sistema STDM
• A capacidade disponível no canal (μ) é
alocada totalmente, sob demanda, a cada
fluxo
• Teremos então um canal de alta capacidade
(μ) alocado a cada fluxo
• Se todos os fluxos associados possuem taxa
de chegada λ
• Como as taxas de chegada e de serviço
possuem distribuição exponencial, o canal
todo é um sistema tipo M/M/1 com tempo de
resposta:
1
s
r2 
Prof. Gil Pinheiro
 

(1   )
139
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
139
Rev.: Out - 2013
Comparação TDM x STDM
• Comparando os tempos de residência: r1  2.r2
• Indicando que o STDM é 2 vezes mais eficiente
• O sistema STDM reserva o uso do canal de maneira
não determinística, alocando toda a capacidade do
canal ao fluxo que estiver pronto para ser enviado
• A comparação só é valida se os pacotes de
informação da cada fluxo chegarem com uma taxa
distribuição exponencial e as taxa de serviços forem
também exponenciais
• Esta situação ocorre em sistemas orientados a
pacotes (transmissão de dados), onde o tempo de
atraso variável (Jitter) não é crítico
Prof. Gil Pinheiro
140
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
140
Rev.: Out - 2013
Sistemas TDM e STDM com
Determinismo
Prof. Gil Pinheiro
141
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
141
Sistemas com Determinismo
Rev.: Out - 2013
• Os sistemas de transmissão analisados
até aqui assumiram modelos do tipo
M/M/1, sem nenhum determinismo
• No caso de haver determinismo, ou
desvio padrão nulo, os seguintes
sistemas são possíveis:
– M/D/1
– D/M/1
– D/D/1
Prof. Gil Pinheiro
142
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
142
Sistema TDM tipo M/D/1
Rev.: Out - 2013
• Nesse sistema, o tempo de serviço é fixo e a taxa de
chegada possui distribuição exponencial
• A capacidade disponível no canal (μ) é dividida entre os
2 fluxos de informação no domínio do tempo
• Teremos então, dois canais dedicados com capacidade
(μ/2) cada um
• Se cada fluxo possui taxa de chegada λ/2
• Como apenas as taxas de chegada possuem
distribuição exponencial, cada fluxo é um sistema tipo
M/D/1 com tempo de resposta:
2 
r1 
2
Prof. Gil Pinheiro

2
(1   )

(2   ) s
(1   )
143
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
143
Sistema STDM tipo M/D/1
Rev.: Out - 2013
• Nesse sistema, o tempo de serviço é fixo e a taxa
de chegada possui distribuição exponencial
• A capacidade disponível no canal (μ) é alocada
totalmente, sob demanda, a cada fluxo
• Teremos então um canal de alta capacidade (μ)
alocado a cada fluxo
• Se todos os fluxos associados possuem taxa de
chegada λ
• Como apenas as taxas de chegada e de serviço
possuem distribuição exponencial, o canal todo é
um sistema tipo M/D/1 com tempo de resposta:
r2 
Prof. Gil Pinheiro
2 
(2   )( s / 2)

2 (1   )
(1   )
144
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
144
Sistemas Totalmente
Determinísticos - D/D/1
Rev.: Out - 2013
• Nesse sistema, o tempo de serviço é fixo e a
taxa de chegada é fixa
• Como é um sistema estável, logo:
– λ / μ é fixo e menor do que 1
– Então: λ < μ
• É um sistema sem espera e sem perdas
• Como não há espera, o tempo de residência é
o próprio tempo de serviço:
r2  s
Prof. Gil Pinheiro
145
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
145
Resumo - Tempos de Residência
Rev.: Out - 2013
Sistema TDM
Sistema STDM
Não
determinísticos
(M/M/1)
2s
(1   )
s
(1   )
Determinísticos
(M/D/1)
(2   ) s
(1   )
(2   )( s / 2)
(1   )
Prof. Gil Pinheiro
146
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
146
Tempo de Residência
com Baixo Tráfego
Rev.: Out - 2013
ρ quase nulo
Sistema TDM
Sistema STDM
Não
determinísticos
(M/M/1)
2s
s
Determinísticos
(M/D/1)
2s
s
147
Prof. Gil Pinheiro
Melhor DETEL – Depto. de Engenharia
Pior Eletrônica e Telecomunicações
147
Tempo de Residência
com Tráfego Intenso
Rev.: Out - 2013
ρ quase unitário
Sistema TDM
Sistema STDM
Não
determinísticos
(M/M/1)
2s
(1   )
s
(1   )
Determinísticos
(M/D/1)
s
(1   )
( s / 2)
(1   )
148
Prof. Gil Pinheiro
Melhor DETEL – Depto. de Engenharia
Pior Eletrônica e Telecomunicações
148
Comparação Gráfica
Tempo de Resposta
12,000
10,000
TDM
(M/M/1)
8,000
STDM
(M/M/1)
6,000
4,000
TDM
(M/D/1)
2,000
STDM
(M/D/1)
0,000
Rev.: Out - 2013
0
0,2
0,4
0,6
Intensidade de Tráfego
Prof. Gil Pinheiro
0,8
1
TDM
(D/D/1)
149
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
149
Rev.: Out - 2013
Conclusão
• A inclusão do determinismo no tempo de serviço
permitiu quadruplicar o desempenho em relação
ao sistema TDM não determinístico
• O sistema de multiplexação estatística teve
sempre melhor desempenho que o não
estatístico
• Para baixas intensidades de tráfego, o sistema
determinístico D/D/1 é menos eficiente que o
M/D/1
• O sistema D/D/1 possui desempenho constante,
sendo o mais eficiente para intensidades de
tráfego elevadas
(> 67%)
150
Prof. Gil Pinheiro
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
150
Rev.: Out - 2013
Redes de Filas
Prof. Gil Pinheiro
151
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
151
Redes de Filas
Rede Paralela
Rev.: Out - 2013
Rede em série com re-alimentação
A existência de re-alimentação anula a característica
de distribuição de
152Poisson na rede.
Prof. Gil Pinheiro
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
152
Rev.: Out - 2013
Redes de Filas Propriedades Importantes
Prof. Gil Pinheiro
153
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
153
Teorema de Jackson
Rev.: Out - 2013
•
É utilizado para analisar redes de Filas. O
Teorema de Jackson estabelece o seguinte:
1. Uma rede de filas possui m nós, cada nó fornece
um serviço independente com distribuição
exponencial
2. Todos os itens que entram na rede de filas (de
fora) possuem distribuição de Poisson
3. Qualquer item que sai de um nó, vai
imediatamente para o próximo nó, com uma
probabilidade k, ou sai do sistema
Prof. Gil Pinheiro
154
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
154
Redes de Filas
Teorema de Jackson
s2
d2
Nó 1
Nó 2
Nó 5
Rev.: Out - 2013
Nó 4
d4
s1
Prof. Gil Pinheiro
155
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
155
Redes de Filas Modelo de Rede de Fila
Servidor
Terminal
de Origem
2
1
3
Rev.: Out - 2013
Terminal
de Origem
5
4
Rede de Comutação
de Pacotes (roteadores)
Prof. Gil Pinheiro
Servidor
156
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
156
Redes de Filas Modelo de Rede de Fila
s2
d2
1
2
3
5
Rev.: Out - 2013
4
d4
s1
Prof. Gil Pinheiro
157
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
157
Redes de Filas Modelo de Rede de Fila
Análise do Nó (Roteador) 1:

Probabilidades de Roteamento:  pi = 1
sistema M/M/1
Balanço de Fluxo:  –  ki pi = 0
p1
link 1
p1.
1
M
p2
p2.
Tempo de Residência (pacote percorre
M nós roteadores):
E[r] = 
link 2
i=1
1
i – i
M
1 / i
i=1
1 – i
= 
p3
p3.
Rev.: Out - 2013
Entrada  Link 1 :
link 3
Prof. Gil Pinheiro
E[r] =
1
1 – p1 
158
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
158
Redes de Filas Exemplo: Rede de 5 Nós
2 = 2
Probabilidade
de Roteamento
1 = 2
1
1/4
2
1/3
3/4
1/2
?
2/3
3
5 = 2
5
1/2
4
?
Capacidade de Transmissão de cada link = 3 pacotes/s
Rev.: Out - 2013
T1,3 (Tempo de resposta entre nós 1 e 3, rota 1-2-3) = ?
T1,4 (Tempo de resposta entre nós 1 e 4, rota 1-5-4) = ?
T1,4 (Tempo de resposta entre nós 1 e 4, rota 1-5-2-4) = ?
Prof. Gil Pinheiro
159
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
159
Redes de Filas Exemplo: Rede de 5 Nós
2 = 2
1 = 2
1
3/4
5 = 2
1/4
2
(1/2)
1/3
(17/12)
(3/2)
5
1/2
1/2
(7/4)
2/3
(17/6)
17/12
3
4
Rev.: Out - 2013
55/12
Valores associados a cada link
Fora do parênteses: probabilidades
Entre parênteses: fluxo de informação
Prof. Gil Pinheiro
160
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
160
Redes de Filas Exemplo: Rede de 5 Nós
Tempos de Resposta:
T1,3 (rota 1-2-3) =
T1,4 (rota 1-5-4) =
Rev.: Out - 2013
T1,4 (rota 1-5-2-4) =
Prof. Gil Pinheiro
1
3 – 1/2
1
3 – 3/2
1
3 – 3/2
+
1
3 – 17/12
1
+
3 – 7/4
+
1
3 – 7/4
= 1,031 s
= 1,467 s
+
1
3 – 17/6
= 7,467 s
161
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
161
Calculando o Estado da Rede
População média no sistema em regime permanente:




n.pn =
n.n .(1- ) =
E[n] =
n=1
n=1
Onde:
=

1–


Tempo de residência no sistema, utilizando a Equação de Little:
Rev.: Out - 2013
E[r] = E[n] /  =
Prof. Gil Pinheiro
/
(1 – )
1
=
.(1 – )
162
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
162
Redes Abertas e Fechadas
• Uma rede aberta possui chegadas e saídas
para o meio externo


Rev.: Out - 2013
• Uma rede fechada não possui chegadas ou
partidas para o meio externo
Prof. Gil Pinheiro
163
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
163
Referências Bibliográficas
Rev.: Out - 2013
[1] Bertsekas, D., Gallager, R. - Data Networks, Prentice Hall, 1992.
[2] Giozza, W.F. (et al.) - Redes Locais de Computadores: Protocolos de Alto Nível e
Avaliação de Desempenho, McGraw-Hill / Embratel, 1986.
[3] Jain, Raj - The Art of Computer Systems Performance Analysis, John Wiley & Sons,
1991.
[4] Kleinrock, Leonard - Queueing Systems - Volume I, John Wiley & Sons, 1975.
[5] Rappaport, Theodore S. Wireless Communications, Prentice Hall, 2nd. Edition
[6] Schwartz, Mischa - Telecommunication Networks, Addison-Wesley, 1988.
[7] Stallings, William - Data and Computer Communications, Maxwell Macmillan, 1991.
[8] Stallings, William - Queueing Analysis, Apostila, 2000
(http://www.WilliamStallings.com/DCC6e.html).
[9] Teoria do Tráfego Telefônico, SIEMENS A.G., 1975
[10] http://athena.mat.ufrgs.br/~portos/erlang.html
Prof. Gil Pinheiro
164
DETEL – Depto. de Engenharia Eletrônica e Telecomunicações
164