59 pág.
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
