Computers: Tools for an Information Agefabio.nelson/arq/redes2/redes2_aula_11.pdf · Title: Computers: Tools for an Information Age Author: Tom Mckenzie Created Date: 10/8/2010 11:13:03

Prof. Fábio Nelson CECOMPColegiado de Engenharia de Computação Slide 1

Rede de Computadores II


Prof. Fábio Nelson CECOMP

Colegiado de Engenharia de Computação Slide 2


Teoria das FilasTeoria das 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.




Teoria das Filas - ObjetivoTeoria das Filas - Objetivo

Avaliar o comportamento de um sistema de filas e seus parâmetros, exemplos: 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




Elementos de uma FilaElementos de uma Fila




Características de uma FilaCaracterísticas de uma Fila

Clientes e tamanho da população População infinita => Chegadas independentes População finita => Chegadas interdependentes

Processo de Chegadas: Não basta fornecer valores médios, é necessário também

mostrar como os valores se distribuem em torno da média.λ = Ritmo de chegada

IC = Intervalo entre chegadas Obs: Intervalos regulares => processos altamente

automatizados





Processo de Atendimento O tempo gasto por cada cliente num computador é

chamado Tempo de Atendimento. É aceitável supor que os Tempos de Atendimento de

cada cliente sejam variáveis aleatórias. A distribuição mais utilizada para o Tempo de

Atendimento é a Distribuição Exponencial. μ = Ritmo de atendimento TA = Tempo de Atendimento





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.





Disciplinas das filas é o método de escolha da sequência de atendimento

dos clientes na fila As mais utilizadas são:

FIFO – First In First Out

LIFO – Last In First Out O atendimento pode ser priorizado em função de:

Tempo esperado de atendimento

Tamanho do cliente (pacote de mensagem)

Maior sensibilidade a atrasos





Disciplinas das filas





Tamanho médio da fila 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 longoNa maior parte dos sistemas, a capacidade da fila é limitada (finita)Em sistemas com filas de capacidade infinita, todos os clientes serão atendidosEm sistemas sem capacidade de espera ou com capacidade limitada, pode ocorrer rejeição de clientes





Tamanho médio da fila Se μ e λ são constantes => o tamanho da fila oscila

em torno de um valor médio. Se μ < λ a fila aumentará indefinidamente.

Tamanho máximo da fila Os clientes devem aguardar em uma área de espera

que deve ser dimensionada de acordo com o tamanho máximo esperado para a fila.





Tempo médio de espera: O tempo médio de espera depende dos processos de

chegada e atendimento.

TF = f (μ,λ)

Variáveis aleatórias O comportamento de uma variável aleatória pode ser

expresso pelo seu valor médio e a forma como os valores se distribuem em torno desta média.




Dinâmica de uma FilaDinâmica de uma Fila




Dinâmica de uma FilaDinâmica de uma Fila




Sistemas EstáveisSistemas Estáveis

Sistema estável é aquele em que μ e λ se mantêm constantes ao longo do tempo.

Se μ e λ não são estáveis, a análise do comportamento do sistema pela teoria das filas só é possível se retalharmos o período de tempo, o que torna a análise muito mais complexa.




Tamanho da AmostraTamanho da Amostra

Um estudo sobre um sistema estável, apresentará sempre os mesmos resultados desde que adequadamente analisado.O tamanho da amostra é fundamental.




Tipos de filasTipos de filas

1 fila e 1 servidor1 fila e n servidoresm filas e n servidoresfilas especiais (ex: caixas expressos de supermercados)filas que seguem uma alteração dinâmica do sistema de atendimento




Variáveis Aleatórias FundamentaisVariáveis Aleatórias Fundamentais

Variáveis referentes ao sistema TS = tempo médio de permanência no sistema NS = número médio de clientes no sistema

Variáveis referentes ao processo de chegada λ = ritmo médio de chegada IC = intervalo entre chegadas por definição: IC = 1/λ

Variáveis referentes à fila TF = tempo médio de permanência na fila NF = número médio de clientes na fila





Variáveis referentes ao processo de atendimento TA = tempo médio de atendimento ou serviço M = quantidade de atendentes ou servidores NA = número médio de clientes que estão sendo

atendidos μ = ritmo médio de atendimento de cada atendente por definição: TA = 1/μ





Relações básicas: NS = NF + NA TS = TF + TA Pode-se demonstrar também que: NS = NF + λ/μ = NF + TA/IC





Taxa de utilização dos atendentes para 1 fila e 1 servidor: ρ = λ/μ para 1 fila e M servidores: ρ = λ/(Mμ) Assim, ρ representa a fração média de tempo em que

cada servidor está ocupado. Para sistemas estáveis, tem-se que : ρ < 1





Intensidade de tráfego ou número mínimo de atendentes i = |λ/μ| = |TA/IC| i é o próximo valor inteiro que se obtém pela divisão

λ/μ . Assim, i representa o número mínimo de atendentes necessário para atender a um dado fluxo de tráfego.

Unidade de i = erlangs ( em homenagem a A. K. Erlang)





Fórmulas de Little (J. D. C. Little) NF = λ . TF NS = λ . TS





Postulados básicos:1.Em qualquer sistema estável, o fluxo que entra é

igual ao fluxo que sai.2.Em um sistema estável, o fluxo de entrada se

mantém nas diversas seções do sistema.3.Em um sistema estável, a junção de fluxos equivale

às suas somas.4.Em um sistema estável, o fluxo se desdobra

aritmeticamente.




QoSQoS

Quality of Service – Qualidade de ServiçoQualidade de Serviço é um requisito da(s) aplicação(ões) para a qual exige-se que determinados parâmetros (atrasos, vazão, perdas, …) estejam dentro de limites bem definidos (valor mínimo, valor máximo). Voz sobre IP (VoIP – Voice over IP) Vídeo sobre IP Aplicações Multimídia Aplicações de Tempo Real




QoS - RequisitosQoS - Requisitos

Fluxo é uma sequência de pacotes desde uma origem até um destino.Em uma rede sem conexões, eles podem seguir rotas diferentes. As necessidades de cada fluxo podem ser caracterizadas por quatro parâmetros principais, juntos, esses parâmetros definem a QoS que o fluxo exige. São eles: Confiabilidade, retardo, flutuação e largura de

banda.




QoS - RequisitosQoS - Requisitos




Técnicas para se alcançar boa Técnicas para se alcançar boa qualidade de serviçoqualidade de serviço

Superdimensionamento Uma solução prática é fornecer tanta capacidade de

roteadores, tanto de espaço de buffers e tanta largura de banda que os pacotes simplesmente são transmitidos com enorme facilidade. O problema com essa solução é seu custo. Com o passar do tempo e à medida que os projetistas adquirem uma ideia melhor da quantidade suficiente de recursos, essa técnica pode até mesmo se tornar prática.





Armazenamento em buffers Os fluxos podem ser armazenados em buffers no

lado receptor, antes de serem entregues. O armazenamento dos fluxos em buffers não afeta a

confiabilidade ou a largura de banda e aumenta o retardo mas, por outro lado, suaviza a flutuação.

No caso de áudio e vídeo por demanda, a flutuação é o principal problema e, portanto, essa técnica ajuda bastante.





Armazenamento em buffers





Moldagem de tráfego A moldagem de tráfego está relacionada à regulagem da

taxa média (e do volume) da transmissão de dados. Quando uma conexão é configurada, o usuário e a sub-

rede concordam com um determinado padrão de tráfego (ou seja, uma forma) para esse circuito. Às vezes, esse acordo é chamado acordo de nível de serviço.

O monitoramento de um fluxo de tráfego é chamado controle de tráfego.





O algoritmo de balde furado Cada host está conectado à rede por uma interface que

contém uma fila interna finita. Se um pacote chegar à fila quando ela estiver cheia, o pacote será descartado.

Essa disposição pode ser interna à interface de hardware ou simulada pelo sistema operacional do host.

Trata-se simplesmente de um sistema de enfileiramento de um único servidor com um tempo de serviço constante.





O algoritmo de balde furado





O algoritmo de balde de símbolos Em muitas aplicações, é melhor permitir que a saída

aumente um pouco sua velocidade quando chegarem rajadas maiores; assim, é necessário um algoritmo mais flexível, de preferência um que nunca perca dados.

O balde furado retém símbolos (ou tokens), gerados por um clock na velocidade de um símbolo a cada T segundos.





O algoritmo de balde de símbolos





O algoritmo de balde de símbolos O algoritmo de balde furado não deixa que hosts

inativos poupem permissões para enviar rajadas maiores posteriormente.

O algoritmo de balde de símbolos permite economia, até o tamanho máximo do balde, n. Essa propriedade significa que rajadas de até n pacotes podem ser enviadas simultaneamente, permitindo um certo volume no fluxo de saída e possibilitando uma resposta mais rápida a rajadas de entrada repentinas.





O algoritmo de balde de símbolos Outra diferença entre os dois algoritmos é que o

algoritmo de balde de símbolos joga símbolos fora (isto é, capacidade de transmissão) quando o balde enche, mas nunca descarta pacotes.

Em contrapartida, o algoritmo de balde furado descarta pacotes quando o balde fica cheio.

Basicamente, o que o balde de símbolos faz é permitir rajadas, mas apenas até uma duração máxima controlada.





O algoritmo de balde de símbolos Uma forma de obter um tráfego mais suave é inserir

um balde furado após o balde de símbolos. A taxa do balde furado deve ser maior que o valor do balde de símbolos, mas deve ser inferior à taxa máxima da rede.

Documents

Computers: Tools for an Information Agefabio.nelson/arq/redes2/redes2_aula_11.pdf · Title: Computers: Tools for an Information Age Author: Tom Mckenzie Created Date: 10/8/2010 11:13:03