Teleinformática e Redes 1 - Teoria de Filas em Redes

Prévia do material em texto

Teleinformática e 
Redes I 
Teoria de Filas em Redes 
Aula 15 
 Profa. Priscila Solís Barreto 
 
Conceitos: 
Taxa de Chegada, Ocupação, Tempo 
no Sistema 
• Sistema de Filas 
– Uma rede de dados, onde os pacotes chegam, esperam em várias 
filas, recebem serviços em vários pontes e saiem depois de um 
tempo 
• Taxa de chegada 
– Número ao longo do tempo de chegadas por unidade de tempo 
• Ocupação 
– Número de pacotes no sistema (média em um período longo) 
• Tempo no sistema(atraso) 
– Tempo desde a entrada do pacote até a sua saída (valor médio 
sobre muitos pacotes) 
O Atraso é causado por 
Interferencia de Pacotes 
• Se as chegadas são regulares ou bem 
espaçadas, não ocorre atraso por enfileiramento 
Tráfego Regular 
Irregular mas com 
espaçamentos iguais 
A explosividade causa 
Interferencia 
• Observar que as partidas são menos 
explosivas 
Explosividade do Tráfego 
Diferentes Níveis na mesma taxa de pacotes 
Source: Fei Xue and S. J. Ben Yoo, UCDavis, “On the Generation and Shaping Self-similar Traffic in Optical Packet-switched Networks”, OPNETWORK 2002 
A variação no Tamanho do 
pacote causa interferência 
Chegadas regulares, tamanhos irregulares de 
pacotes 
Alta utilização aumenta a 
interferência 
Conforme a relação (taxa de chegada de pacotes 
* tamanho do pacote) aumenta, a interferência 
tende a aumentar 
Time
Queuing Delays
Teorema de Litte 
• Para uma taxa de chegada, o tempo no sistema é 
proporcional ao número de pacotes no sistema 
 N =  T 
 onde: 
 N: número médio de pacotes no sistema 
 : taxa de chegada de pacotes (por unidade de 
tempo ) 
 T: atraso médio (tempo no sistema) por pacote 
• Exemplos: 
– Em dias chuvosos, ruas e estradas são mais cheios 
– Restaurantes de comida rápida precisam de salas menores que 
os restaurantes normais com a mesma taxa de chegada 
– Grandes buffers com altas taxas de chegada causam atrasos 
longos 
9 
Métodos Gráficos 
• Diagramas de acumulação, mostram o 
número total de objetos que entraram e 
saíram de um sistema do momento de 
início da análise até um tempo t. 
Formalmente se objetos entraram no 
sistema nos tempos a1, a2,.... então a 
função cumulativa de chegada é dada por 
A (t) = número de aj com j  t. A definição 
de função de partida D(t) é similar. Por 
exemplo, no diagrama abaixo mostra as 
chegadas e saídas de um sistema 
hipotético 
 
10 
 
Contagem 8 - 
Cumulativa 
 7 - 
 
 6 - 
 
 5 - 
 
 4 - 
 A(t) D(t) 
 3 - 
 
 2 - 
 
 1 - 
 
 Tempo 1 2 3 4 5 6 7 
 
11 
• A curva superior, A(t), mostra o processo de 
chegadas, a inferior D(t), as partidas. 
• O afastamento vertical entre as curvas 
mostra a diferença entre o número total de 
objetos que entraram e os que saíram do 
sistema a qualquer momento, ou seja, a 
população do sistema. 
• O afastamento horizontal entre as curvas 
mostra a diferença entre o horário de saída e 
de entrada de um objeto, ou seja, o tempo de 
permanência do objeto no sistema desde que 
o tempo seja FIFO). 
 
12 
• Portanto, basta examinar o diagrama para 
determinar informações como: 
– a população máxima e mínima do sistema e 
quando estas populações ocorreram; 
– tempos de permanência máximos e mínimos; 
– a área entre as duas curvas permite a 
determinação de populações e tempos de 
permanência médios de objetos no sistema. 
 Esse tipo de análise permite a solução de 
problemas em que a teoria clássica de filas 
não pode ser usada (porque trata 
basicamente de sistemas em equilíbrio). 
 
13 
Teoria de Filas: Sistemas em 
Equilíbrio 
• Sistemas em equilíbrio são aqueles cujo 
estado independe do instante de tempo 
em que análise é feita. Isso não quer dizer 
que o estado do sistema não se 
modifique; ele pode flutuar 
randomicamente, mas seu comportamento 
pode ser descrito sem levar em 
consideração o horário. 
 
14 
• Sistemas em equilíbrio são aqueles em que 
as condições operacionais (taxas de 
chegada e de serviço) são constantes 
durante todo o tempo ao menos durante um 
longo tempo em comparação a tempos de 
serviços típicos. 
• No estudo de sistemas de filas em equílibrio, 
as chegadas de clientes e os tempos de 
processamento são normalmente descritos 
por distribuições probabilísticas ea disciplina 
pode ser FIFO (first-in first-out), LIFO ( last-in 
first-out), randômica, ou de acordo com um 
sistema de prioridades. 
Estabilidade e Estado de 
Equilíbrio 
• Uma fila é estável se a taxa de chegada de 
pacotes < capacidade de transmissão do 
sistema 
• Para uma fila, a relaçao chegada de pacotes 
/capacidade de transmissão do sistema é 
chamado de fator de utilização, ou seja, 
descreve a carga da fila 
• Em um sistema instável, os pacotes se 
acumulam em várias filas ou são perdidos 
• Para sistemas instáveis com buffers grandes, os 
atrasos são muito grandes 
16 
Teoria de Filas 
• Técnicas matemáticas utilizadas para 
analisar o fluxo de itens através de uma 
rede; 
• A rede contém um ou mais locais onde 
existem restrições quanto aos tempos ou 
freqüências com que os objetos podem 
passar; 
• Princípio da conservação: objetos não 
podem se materializar ou desintegrar; 
 
 
1 
2 
m 
Fila 
Servidores 
Chegadas 
ao 
sistema 
Saídas do 
sistema 
sistema 
Representação de uma fila 
18 
Teoria de Filas 
• Objetos bloqueados pelas restrições são 
armazenados em um local ( uma fila) até 
passarem pela restrição; 
• Enquanto houver objetos em uma fila , 
eles serão processados tão rapidamente 
quanto a restrição permitir; 
• Principais elementos de uma fila são os 
clientes, os servidores e a disciplina 
 
19 
Teoria de Filas 
• Filas se desenvolvem a medida que 
clientes chegam ao sistema e entram em 
uma fila para aguardar processamento; 
• Os servidores escolhem clientes dentre os 
que estão na fila de acordo com uma 
disciplina, efetuam o processamento e 
despacham os cliente; 
20 
Teoria de Filas 
• Se o sistema estiver em equilíbrio, há um 
extenso ferramental analítico que pode ser 
usado para analisá-lo; 
• Quando o sistema não está em equilíbrio 
( por exemplo, aumento de fluxo em horas 
de pico) o problema deve ser analisado 
por outros métodos, tais como métodos 
gráficos e simulações. 
21 
Teoria de Filas: Notação 
Formato (a/b/c): (d/e/f), onde 
• a é a distribuição da chegada dos clientes; 
• b é a distribuição dos tempos de serviço ( 
ou partidas); 
• c é o número de servidores em paralelo; 
• d é a disciplina de serviço ( FIFO, 
LIFO,...); 
• e é o número máximo de clientes 
permitidos no sistema ( fila + serviço); 
• f é o número máximo de clientes que 
podem usar o sistema. 
 
22 
Além disto, a notação padronizada utiliza os 
seguintes símbolos para descrever as 
atribuições de chegada e serviço dos 
clientes: 
• M processo Poisson, com intervalos 
exponenciais ( M de Markov) 
• D Determinístico 
• Ek processo Erlangiano, com intervalosgama (k) 
• GI Distribuição Geral com chegadas 
independentes 
• G Distribuição Geral 
 
23 
• Os três últimos símbolos são geralmente 
omitidos quando a disciplina é FIFO e não 
há restrições quanto ao número de 
clientes. Por exemplo o sistemas de filas 
mais simples é o M/M/1, ou seja, 
chegadas e serviços Poisson, um servidor 
apenas e sem restrições quanto ao 
tamanho máximo da fila, ou ao número 
máximo de clientes que possam utilizar o 
sistema. 
 
24 
Distribuição Exponencial 
As características da dinâmica de um 
Sistema de Filas são determinadas em 
grande parte por duas propriedades 
estatísticas: 
• Função distribuição de probabilidade das 
chegadas; 
• Função distribuição de probabilidade dos 
tempos de serviço. 
25 
 Função Distribuição de 
Probabilidade 
Seja a variável aleatória T que representa ou 
intervalos entre chegadas ou tempos de 
serviço. 
Esta variável é dita como tendo Distribuição 
Exponencial com parâmetro  se sua 
função densidade de probabilidade é 
 
 para t>= 0 
 
 
 para t <0 
 
 
 
 
 
fT(t)  { e
t
0
26 
 Probabilidade Cumulativa 
P { T  t } = 1 – e -t 
P { T > t } = e -t (t  0) 
 
 
 f
T
(t) 
 
  
 
 
 
 
 
 E(T) = 1/  t 
 
 E(T) = 1/  e var(T) = 1/  2 
27 
Propriedades da Distribuição 
Exponencial 
• fT(t) é uma função estritamente decrescente 
de t ( t  0): 
– P{0  T  t} > P{0  T  1 + t}, qq. t e t > 0 
• Perda de memória: 
– P{ T > t + t | T > t} = P{T > t}, qq. t e t > 0 
 
A distribuição da probabilidade do tempo de 
permanência até que o evento ( finalização 
chegada ou serviço) ocorra sempre é a 
mesma, indiferente de quanto tempo (t) já 
tenha passado. 
 
O processo esquece a sua história 
28 
 
Explicação deste fenômeno: 
P{ T > t + t | T > t} = P{ T > t, T > t + 
t} 
 P{ T > t} 
 = P{ T > t + t} 
 P{ T > t} 
 = e- ( t + t) 
 e-  t 
 = e -  t 
 
 
 
29 
Conclusões 
Tempos entre chegadas: o tempo até a 
próxima chegada não sofre nenhuma 
influência da última chegada ocorrida; 
Tempo de serviço: serviços diferentes. 
30 
 • O mínimo de várias variáveis randômicas 
exponencialmente independentes terá uma 
distribuição exponencial: 
– Tempos de chegada: admitindo que existem (n) 
diferentes clientes chegando ao sistema e que o 
intervalo de tempo entre as chegadas para cada 
cliente (i) tem distribuição exponencial com 
parâmetro i (i =1,2,...,n). Pela segunda 
propriedade, o tempo restante a partir de qualquer 
instante até a próxima chegada tem a mesma 
distribuição. Portanto, pode-se ignorar o fato que 
os clientes são diferentes e ainda teremos tempos 
com distribuição exponencial entre as chegadas 
para o sistema de filas. 
Processo de Poisson com Taxa  
• Tempos de interchegada são independentes e 
exponencialmente distribuidos 
• Um modelo do tráfego acumulado de fontes independentes 
• O tempo médio de interchegadas é 1/  (seg/pacote), então 
 é a taxa de chegada (pacotes/segundo) 
32 
Teoria de Filas: Estrutura 
Básica 
• Clientes demandando serviço são 
inseridos no sistema por uma fonte 
(geração em relação ao tempo). 
• Os clientes entram no Sistema da Fila e 
entram em uma fila. 
• Em um dado momento, um membro da fila 
é selecionado para receber um serviço, 
conforme uma regra conhecida : disciplina 
da fila. 
 
33 
 
• O serviço é realizado pelo prestador do 
serviço 
• Após a realização do serviço o cliente 
deixa o Sistema da Fila 
 
 
Fonte Clientes Fila Serviço Clientes 
Atendidos 
 
 
 
 Sistema de Fila 
34 
 Fonte: Processo de Chegadas 
 
• A chegada de clientes ao sistema ocorre, na 
maioria das vezes, de forma aleatória; 
 
• Caracterizado por uma função de distribuição 
de probabilidades; 
 
 
 
 
35 
Serviço 
• Formado por uma ou mais facilidades; 
• Cada facilidade contém um ou mais 
servidores em paralelo, chamados de 
servidores; 
• O tempo de realização do serviço é 
denominado de tempo de serviço; 
• Uma função de distribuição de 
probabilidade especifica o tempo de 
serviço. 
36 
 Fila 
• Assumir fila de tamanho finito; 
• Disciplina: 
– Maneira de como os membros da fila são 
selecionados para o serviço: FIFO, LIFO, 
RANDON ou outra prioridade. Se nada for dito 
considera-se FIFO. 
 
Unico Servidor FIFO 
• Única linha de transmissão servindo pacotes na forma FIFO (First-
In-First-Out) 
• Cada pacote deve esperar que todos os pacotes no sistema 
completem a transmissão, antes de começar a transmitir 
– Departure Time = Arrival Time + Workload Found in the System + 
 Transmission time 
• Pacotes que chegam em um buffer cheio são descartados 
Arrivals
Transmission 
Line
Fila FIFO 
• Os pacotes são colocados em um enlace de saida em ordem FIFO 
 
Vários Servidores 
• Vários pacotes são transmitidos simultaneamente on 
várias linhas/servidores 
• Os pacotes esperam na fila FIFO e quando um servidor 
está livre, o primeiro pacote é servido 
 
Servidores de Prioridade 
• Os pacotes formam classes de prioridade 
• Uma fila FIFO separada para cada classe de prioridade 
• Os pacotes de baixa prioridade começam a transmissão somente 
se um pacote de prioridade mais alta não está esperando 
Filas de Prioridade 
• Pacotes classificados em filas separadas 
• Todos os pacotes com alta prioridade são servidos antes dos 
pacotes de prioridades mais baixas 
42 
Filas:Terminologia e Notação 
• Estado do Sistema: número de clientes no sistema; 
• Tamanho da Fila: número de clientes esperando por 
serviço ( estado do sistema menos o número de 
clientes sendo atendidos); 
• N(t) = número de clientes no sistema no tempo t (t 
>= 0); 
• Pn(t) = probabilidade de exatamente n clientes 
estarem no sistema no tempo t, dado um número 
para o tempo zero; 
• S = número de servos (paralelos) no sistema ; 
 
43 
Filas:Terminologia e Notação 
• = taxa média de chegada ( número 
esperado de chegadas por unidade de tempo) 
de novos clientes quando n clientes estão no 
sistema; 
 
• = taxa média de serviço ( número 
esperado de clientes atendidos por unidade 
de tempo) quando n clientes estão no sistema; 
• Quando é constante para todo n é 
representado por ; 
 
 
 
n
n
 
n

44 
 
• Quando a taxa média de serviço por 
servidor ocupado é constante para todo n 
>= 1, está constante é representada por µ. 
 
•  =/(s) é a taxa de utilização do sistema 
: fração de tempo esperada dos servosem que eles estão ocupados 
 
Sistema M/M/1 
• Nomenclature: M significa “Memoryless” (propriedade de 
uma distribuição exponencial) 
– M/M/1 processo de chegada Poisson 
– M/M/1 tempos de transmissão exponencialmente distribuidos 
• Pressupostos: 
– O processo de chegada com  pacotes/sec 
– A transmissão de pacotes tem tempos exponencialmente distribuidos 
com média igual a 1/ 
– Um servidor 
– Tempos de interchegada e tempos de transmissão independentes 
• Tempo de transmissão é proporcional ao tamanho do pacote 
• Fator de utilização:  = / (sistema estável se   1) 
 
Cálculo do Atraso 
• Seja 
 Q = tempo médio gasto esperando na fila 
 T = Atraso médio de pacotes (transmissão mais 
enfileiramento 
• Observar que T = 1/ + Q 
• E pelo Teorema de Little N =  T e Nq =  Q 
onde 
 Nq = Número médio esperando na fila 
• A análise mostra as probabilides para o 
número de pacotes na fila ou em transmissão 
• P{n pacotes} = n(1-) onde  = / 
• Do anterior, podem se calcular as médias: 
 N = /(1 - ) 
 T = N/ = /(1 - ) = 1/( - ) 
 
Resultados de um modelo M/M/1 
Exemplo: a escala do atraso 
em relação à largura de banda 
• Formulas de ocupação e atraso 
 N = /(1 - ) T = 1/( - )  = / 
• Assumir que : 
– A taxa de chegada de tráfego  duplica 
– A capacidade de transmissão do sistema  duplica 
• Então: 
– Os tamanhos das filas se mantém no mesmo nível ( se 
mantém igual) 
– Atraso do pacote é a metade ( e  são duplicados 
• Conclusão: Em redes de alta velocidade 
– Propagação do atraso tem um impacto importante em relação 
ao atraso 
– Tamanho do buffer e perda de pacotes podem ser problemas 
Sistemas M/M/m, M/M/ 
• Igual ao M/M/1, com m (ou ) servidores 
• No M/M/m, o pacote no ínicio da fila é atendido 
quando um servidor está livre 
• Resultado qualitativo 
– Atraso aumento para  conforme  = /m se se 
aproxima de 1 
• Existem equações analíticas para as 
probabilidades de ocupação e atraso médio 
nestes sistemas 
Sistemas de Buffer Finito: M/M/m/k 
• O sistema M/M/m/k 
– Igual ao M/M/m, con espaço de buffer para k pacotes. 
Pacotes que chegam quando o buffer está cheio são 
descartados 
• O sistema M/M/m/m é usado para planificar 
sistema telefonico ou de comutação de circuitos 
 
Sistema M/G/1 
• Igual que o M/M/1 mas a transmissão de 
pacotes segue uma distribuição geral, com 
média 1/ e variancia s2 
• Fator de utilização  =  / 
• Equação de Pollaczek-Kinchine 
Tempo médio na fila = (s2 + 1/2)/2(1- ) 
Atraso médio = 1/ + (s2 + 1/2)/2(1- ) 
• Conforme s2 aumenta, o atraso aumenta 
Demo: M/G/1 
Tempo de interchegada de 
pacotes 
exponencial (0.02) sec 
Capacidade 
1 Mbps 
Tamanho do pacote 
1250 bytes 
(10000 bits) 
 
 
Distribuição da chegada 
de pacotes 
exponencial 
constante 
lognormal 
 
What is the average delay and queue size ? 
 
Resultados Analíticos da M/G/1 
Distribuição 
Tamanho Pacote 
Atraso T (seg) 
Tamanho da Fila 
(pacotes) 
Exponential 
média = 10000 
 variancia = 1.0 *108 
 
0.02 
 
1.0 
Constant 
média = 10000 
variancia = N/A 
 
0.015 
 
0.75 
Lognormal 
média = 10000 
variancia = 9.0 *108 
 
0.06 
 
3.0 
Demo: Resultados da Simulação 
M/G/1 
Atraso médio (sec) Tamanho médio da fila 
(pacotes) 
Demo: M/G/1 Limitações 
Mistura do tráfego sem memória curta 
 
• Video 
» constant packet inter-arrivals 
• Http 
» bursty traffic 
Delay 
 
P-K formula 
 
Simulation 
5
6 
Exemplo de uma Fila M/M/1 
• Gateway de rede, 4 Mbps, tamanho do 
pacote 1000 bytes, taxa de chegada 125 
pacotes/segundo 
– Qual é a probabilidade de overflow com 12 
buffers? 
– Quantos buffers são necessários para manter a 
perda de pacotes na relação de 1 para 
1,000,000? 
5
7 
Cálculos 
• Taxa de chegada =125 
pps 
• Taxa de serviço: 
4000000/8 
 = 500000 Mbytes/sec 
500000/1000 = 500 pps 
Então, =500 pps 
• Fator de utilização: 
 = / = 125/500 = .25 
• Número de pacotes em 
média no gateway: 
/(1-) = .25/.75 = .33 
• Probabilidade de n pacotes no 
gateway 
Pr(n) = (1-)n=.75(.25)n 
• Tempo médio no gateway: 
(1/) / (1-) 
= (1/500)/(1-.25) = 2.66ms 
• Prob de overlflow = Pr(13+) 
= 13 = .2513 = 1.49x10-8 
 15 packets/bilhão 
• Limitar para menos de 10-6 
n10-6, 
n > log(10-6)/log(.25) 
 > 9.96, então 10 buffers 
5
8 
Outro Exemplo de M/M/1 
• Servidor Web: tempo entre pedidos é 
exponencial com tempo médio de 8 ms. 
Tempo de processamento é exponencial com 
tempo médio de serviço de 5 ms. 
A) Qual é o tempo médio de resposta? 
B) Quanto mais rápido o servidor deve ser para 
baixar pela metade o tempo de resposta? 
C) Qual o tamanho do buffer para perder 1 em 
1,000,000,000 requesições? 
5
9 
Cálculos 
• Taxa de requesição 
 = 1000 / 8 = 0.125 
requesições por ms 
• Taxa de serviço 
 = 1000 / 5 = 0.2 
requesições por ms 
• Utilização 
 = /= .125/.2 = .625 
– Então, 62.5% da 
capacidade 
A) Tempo médio de resposta 
(1/) / (1-) 
 = (1/.2)/(1-.625) 
 = 13.33 ms 
• Para abaixar pela metade: 
 (1/) / (1-) = 6.665 
– Supor  fixa, mudar  
 = 1/6.665 + 0.125 = .257 
B) Então (.275-.2)/.2 * 100 
 = 37.5% mais rápido 
• 1 em 1 bilhão 
– Tamanho do Buffer k: 
 Pr(k)  10-9 
 k  10-9 
C) Então, 
 k > log(10-9) / log(.625) 
 k  44