A maior rede de estudos do Brasil

Grátis
59 pág.
Teleinformática e Redes 1 - Teoria de Filas em Redes

Pré-visualização | Página 1 de 3

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 intervalos