Baixe o app para aproveitar ainda mais
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 n10-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
Compartilhar