2 Design process
2.3 Rapid prototyping
Com o mecanismo de congestion avoidance, o TCP garante uma divisão justa entre todos os fluxos com demandas por recursos da rede. Porém, ao administrar uma rede compartilhada por diversos serviços com diferentes características de tráfego de diferen- tes necessidades, também é importante que o administrador possa definir prioridades para diferentes tipos de tráfego.
4
Na prática, a janela não dobra em um só instante, mas esse crescimento é distribuído a cada ACK recebido. Esse comportamento, de dobrar a janela a cada vez, leva a um crescimento exponencial, que está longe de ser considerado “lento”. Entretanto, por permitir um crescimento gradativo, ao invés de iniciar com um valor arbitrariamente alto, considera-se o nome slow start apropriado nesse caso.
Alguns dos exemplos mais comuns de aplicações que apresentam necessidades específicas são aplicações interativas, como telnet ou navegadores Web, e aplicações de tempo real. A alocação diferenciada de recursos de rede também pode ser vista do ponto de vista comercial. Em uma infraestrutura de um provedor de recursos computacionais por exemplo, um dos clientes pode estar disposto a realizar um investimento maior para ter um serviço diferenciado. Como um outro exemplo, um provedor de Internet residencial pode querer oferecer diversos planos com diferentes garantias de banda para seus clientes.
Esse tipo de alocação diferenciada exige uma visão mais abrangente da situação da rede e por isso devem considerar sua implementação dentro da rede, nos elementos de chaveamento. Nesse caso é possível considerar soluções baseadas na reserva de recursos e no estabelecimento explícito de garantias de taxas de transmissão. Como mencionado anteriormente, soluções implementadas dentro da rede normalmente são definidas por algoritmos de controle das filas dos roteadores e switches da rede que permitam maior controle sobre a alocação de banda.
Esses algoritmos, também chamados de disciplinas de fila (queuing discipline) são compostos por uma disciplina de escalonamento (scheduling discipline) e uma política de descartes (drop policy). Essas tem a função de controlar tanto a largura de banda de cada fluxo quanto o seu uso do espaço para armazenamento temporário, respecti- vamente. O controle da largura de banda é feita através das decisões de quais pacotes que devem esperar na fila ou serem transmitidos e as regras para o uso do armaze- namento temporário definem quais pacotes devem ser descartados ao invés de serem armazenados.
A disciplina de fila mais simples é a FIFO (first-in, first-out). As regras envolvidas nessa disciplina definem que novos pacotes sempre entram no fim da fila e que o próximo pacote a ser enviado é sempre aquele no início da fila. Essa disciplina também é conhecida como “FIFO com descartes da calda” (FIFO with tail drop), onde FIFO é a sua disciplina de escalonamento e descartes da calda a política de descartes. Por ser muito simples e necessitar de poucos recursos de hardware, quase todos os roteadores da Internet possuem uma implementação dessa disciplina [45]. No entanto, essa disciplina não oferece qualquer diferenciação de serviço entre fluxos de apresentam diferentes prioridades.
Qualquer disciplina capaz de tratar de forma diferenciada os diferentes fluxos depende da capacidade de identificação desses fluxos. Isto é, cada pacote recebido pelo elemento de chaveamento deve poder ser associado ao fluxo a que pertence. Isso é normalmente feito pela identificação de um padrão nos cabeçalhos do pacote, como endereços de origem e destino. Uma vez que um pacote seja associado ao seu fluxo,
o algoritmo de processamento da fila pode decidir como tratar esse pacote em relação aos demais em função do estado anterior associado ao fluxo que foi identificado.
Uma variação da politica FIFO para que ela seja capaz de diferenciar fluxos de diferentes prioridades é chamada fila de prioridades (priority queuing). Essa variação consiste em utilizar várias filas com disciplina FIFO de forma que fluxos de tráfego com diferentes prioridades são encaminhados para diferentes filas. A disciplina de escalonamento define que enquanto uma fila de maior prioridade não estiver vazia fila ela é sempre atendida antes das outras de menor prioridade. Essa ideia pode ser considerada um simples passo além da disciplina FIFO e não pode ser considerada uma boa solução para diferenciação de tráfego. O problema com a fila de prioridades é a possibilidade de starvation das filas de menor prioridade caso um determinado fluxo de tráfego esteja sempre presente no roteador.
Um problema que afeta tanto a disciplina de fila de prioridades quanto a FIFO é que pacotes que são alocados para a mesma fila são tratados igualmente, sem qualquer distinção entre pacotes de fluxos diferentes. Um fluxo com maior volume de tráfego pode consumir uma maior parcela dos recursos de rede, restringindo a divisão justa dos recursos disponíveis. Uma disciplina de fila que tenta resolver esse problema é a disciplina Fair Queuing (FQ).
A ideia de FQ é dividir diferentes fluxos de mesma prioridade em diversas filas, utilizando para isso os endereços fonte e/ou destino de cada um. Os pacotes dessas filas seriam então transmitidos seguindo um algoritmo round-robin. Quando um fluxo com grande volume de tráfego utiliza todos os recursos disponíveis da sua respectiva fila, seus pacotes começam a ser descartados. Assim como nas outras disciplinas de fila, o descarte de pacotes é utilizado como forma de informar indiretamente o servidor que os recursos da rede se esgotaram e que o controle de congestionamento implementado nos servidores deve ser ativado.
Uma importante variação da disciplina FQ é a Weighted Fair Queuing (WFQ). Essa disciplina herda quase todas as características da FQ, porém ela oferece a possi- bilidade de atribuir pesos a cada uma das filas que serão atendidas com o algoritmo de round-robin. Utilizando essa disciplina é possível, por exemplo, dividir os recursos do roteador de forma que um dos usuários utilize duas vezes mais recursos que os outros. Uma propriedade comum às duas disciplinas, FQ e WFQ, é que elas são capazes de realizar um escalonamento com conservação de trabalho (work-conserving). Isso significa que caso uma das filas não esteja utilizando os recursos de rede da interface, a disciplina pode repassar esses recursos automaticamente para alguma outra fila que apresente demandas por recursos. Dessa forma o escalonamento com conservação de trabalho pode melhorar a utilização média da rede mantendo a divisão de acordo com
as regras definidas pelo operador da rede quando todas as filas apresentam demanda por recursos.
Até aqui apresentamos disciplinas de fila que podem ser utilizadas para priorizar tráfego e dividir os recursos de cada roteador de forma justa. Uma outra forma de realizar o controle de tráfego é através da especificação de uma largura fixa de banda para cada fluxo. Um dos algoritmos que podem ser utilizados para controlar o tráfego especificando uma velocidade de transmissão é o token bucket. A ideia do algoritmo é apresentada na figura 2.6. Cada fluxo é associado a uma fila e cada fila deve manter um balde que é preenchido com tokens à uma taxa constante. A medida que novos pacotes chegam à fila para serem transmitidos, a fila verifica se existem tokens disponíveis no balde. Caso a resposta seja positiva, o pacotes é encaminhado e a quantidade de tokens referente ao tamanho do pacote transmitido é removida do balde. Caso não existam tokens disponíveis no balde de tokens, o pacote é mantido na fila caso exista espaço disponível para seu armazenamento ou é descartado, caso a fila já esteja cheia.
Pacotes
Tokens Disponíveis? Transmite e Remove tokens do balde Pacote aguarda na fila até que novos tokens sejam adicionadosSim
Não Tokens adicionados
a uma taxa constante
Fila
Figura 2.6. Funcionamento do algoritmo Token Bucket
Uma característica importante do algoritmo token bucket é relacionada à sua ca- pacidade de armazenar buckets no balde enquanto não há tráfego para ser enviado. Isso permite que pacotes pertencentes a fluxos com padrões de tráfego de rajadas (bursts) de alta velocidade, como é o tráfego da Internet, não sejam descartados imediatamente. O tamanho do balde é uma forma de ajustar qual é a duração da rajada permitida pelo algoritmo token bucket. A robustez do algoritmo tornou-o o algoritmo mais utilizado para controle de tráfego baseado em larguras de banda.