Feliz 2008

Quando comecei este blog não imaginei que duraria tanto, e em alguns momentos até pensei realmente em parar, mas volta e meia eu encontrava comentários aqui e ali de gente falando bem do que escrevo, e isso sempre me dava ganas de continuar.

2008 trará novos desafios para minha vida e graças a eles estou reorganizando minhas rotinas e meus estudos, e isto inclui a área de redes. Uma das minhas metas para este ano é manter um ritmo de estudos ainda maior, e por isso acredito que os posts aqui no blog se tornar mais freqüentes, batendo uma mínimo de 11 por mês.

Agradeço a todas pela atenção e pela audiência, e espero ter correspondido às suas expectativas.

Neste 31 de dezembro deixo aqui no Vovó Viu a Rede meu desejo de que todas as minhas leitoras tenham um 2008 de muitas realizações. Que o Senhor as abençoe durante todos os próximos 366 dias.

Protocolos CSMA livres de colisão

Já vimos no último artigo como funcionam os protocolos CSMA que permitem colisões de pacotes, e desta vez veremos outros que impedem que elas aconteçam. Continuaremos aqui com a metáfora da rodoviária.

Só para refrescar a sua memória, lembro que a metáfora é a seguinte: uma rodoviária que tinha caixas de som usadas para anunciar os ônibus que estavam saindo e chegando. Só que, ao invés de ter apenas uma pessoa responsável pelos anúncios, cada uma das 20 empresas tinha a sua própria mocinha com voz de veludo. Claro que elas não podiam falar ao mesmo tempo, para que os passageiros não se confundissem, e por isso adotaram um método de trabalho.

Depois de tentar três métodos, vistos no outro artigo, a administração da rodoviária tentou novos meios, que impediam que duas ou mais moças falassem ao mesmo tempo.

***


Na primeira tentativa, as cabines das 20 moças foram colocadas em um grande salão, uma ao lado da outra, formando uma fila. Além disso, o tempo de trabalho delas foi dividido em duas etapas, que se alternavam o dia inteiro: uma etapa de disputa e uma etapa de anúncios. Por fim, neste salão trabalhava com elas um sujeito que era o dono do microfone.

Na etapa de disputa, o sujeito ia de cabine em cabine, na ordem da fila, perguntando se as moças tinham algum anúncio a fazer. Se tinham, ele ia colocando uma bandeirola vermelha em frente à cabine. Depois de perguntar a todas as moças se elas tinham um anúncio a fazer, ele voltava ao início da fila de cabines e ia em cada uma daquelas que tinha um anúncio a fazer, na ordem da fila. Elas faziam o anúncio e ele retirava a bandeirola.

É um serviço um pouco burro, eu sei, mas pelo menos acabou com o problema de duas moças falarem ao mesmo tempo.

***


Infelizmente, este método trouxe a reclamação de algumas empresas. O que aconteceu é que enquanto algumas empresas tinham apenas poucos ônibus circulando, e por isso faziam poucos anúncios durante o dia, mesmo em momentos de alto movimento, outras tinham um número muito grande de ônibus circulando, e o tempo que se perdia nas etapas de disputa era para elas um grande desperdício.

Elas não estavam muito erradas, vejam só: das 20 empresas, cinco tinham um movimento intenso de ônibus, dez um movimento médio e outras cinco um movimento baixo. Daí que às vezes apenas as cinco com mais movimento tinham algo a dizer, e tinham que esperar as outras quinze se manifestarem, dizendo que não tinham nada a transmitir, para que finalmente pudessem dar o seu recado.

Por isso, foi adotado novo método: a fila foi reorganizada, colocando as moças na ordem das que mais tinham coisas a falar para as que menos tinham. Depois disso feito, o sujeito do microfone passou a trabalhar de um jeito diferente: ele ia ao início da fila e começava a perguntar a cada uma das moças se elas tinham algo a dizer. Assim que encontrava uma que tinha um anúncio a fazer ele liberava o microfone para ela. Terminado o recado ele voltava ao início da fila.

Fica claro que as primeiras da fila, que sempre tinham algo a dizer, se beneficiaram com isso, só que isso prejudicou, e muito, as últimas, que por muitas vezes esperavam muito tempo por uma oportunidade de fazer o seu anúncio. Era preciso que nenhuma das primeiras tivesse algo a dizer para que o microfone pudesse chegar até elas. Imagine o sofrimento da última da fila!

***


Como, então, dar espaço às moças que tinham poucos anúncios a fazer?

Foi adotado então um rodízio e a fila deixou de ser fixa: assim que uma moça terminava de falar, ela ia para o fim da fila e as que estavam atrás dela ganhavam uma posição. Graças a isso, as cabines passaram a ter um painel eletrônico que mostrava a sua posição na fila.

Ademais, o sujeito do microfone deixou de ir de cabine em cabine perguntando se as moças queriam falar algo. No lugar disso, as que tinham um anúncio para fazer apertavam um botão que fazia acender uma luz no painel de sua cabine. Havendo mais de uma querendo fazer o anúncio, a prioridade era dada àquela que estava mais na frente na fila.

Isso dava mais oportunidades às moças que falavam pouco: já que as que falavam mais ficavam sempre nos últimos lugares da fila, as mais caladas tinham sempre a maior prioridade na hora de dar o seu recado. Ao mesmo tempo, este método de trabalho não causava desperdício de tempo com disputas, já que o sujeito do microfone não tinha mais que ficar indo de cabine em cabine o tempo todo.

***


Se a leitora entendeu os meus exemplos, já entendeu por tabela os protocolos CSMA livres de colisão:

O primeiro é o mapa de bits: na etapa de disputa, cada uma dos equipamentos da rede informa que quer transmitir alguma coisa e em seguida, cada um por vez, transmite o seu pacote. Daí o processo recomeça com uma nova etapa de disputa.

O segundo é a contagem regressiva binária: cada máquina tem um número de ordem; as que querem transmitir alguma coisa informam seus números; a de maior número consegue a permissão de transmitir e transmite. O processo recomeça.

O terceiro é uma variação da contagem regressiva binária proposta por Mok e Ward: cada máquina ocupa uma posição em uma fila; as que querem transmitir emitem um sinal; a que estiver mais à frente na fila transmite, vai para o fim da fila e o processo recomeça.

Protocolos CSMA que permitem colisão

Existem três tipos de protocolos CSMA que permitem a existência de colisão na transmissão de dados, e para entendê-los vamos lançar mão do meu recurso mais manjado: uma metáfora.

***


Imagine então, querida leitora, que havia uma rodoviária que tinha caixas de som usadas para anunciar os ônibus que estavam saindo e chegando. Só que, ao invés de ter apenas uma pessoa responsável pelos anúncios, cada uma das 20 empresas tinha a sua própria mocinha com voz de veludo. Claro que elas não podiam falar ao mesmo tempo, para que os passageiros não se confundissem, e por isso adotaram um método de trabalho.

Antes de começar a dar o seu recado, elas reparavam se não havia nenhuma das outras falando. Se não houvesse nenhum anúncio sendo feito, elas faziam o seu na mesma hora. E se houvesse alguém falando, elas esperavam que a primeira terminasse para começar a falar assim que fosse possível. Simples e prático, mas com um problema muito comum: às vezes, duas, três ou até mais moças ficavam esperando uma terminar de falar e então começavam todas a falar juntas. Quando isso acontecia, todas paravam de falar e aguardavam um tempo aleatório para então tentar novamente.

Por que este tempo era aleatório? Fácil: se todas aguardassem o mesmo tempo, todas tentariam começar a falar na mesma hora, e falariam juntas ao mesmo tempo de novo, de novo, de novo. Com tempos aleatórios, uma esperaria, digamos, cinco segundos, outra onze e a terceira vinte, diminuindo os riscos de falarem juntas.

Quando haviam poucos ônibus circulando, este método funcionava com excelência, pois havia pouca concorrência entre as moças. Entretanto, em períodos de grande movimento, elas raramente conseguiam dar seus recados nas primeiras tentativas.

***


Por isso, a administração da rodoviária ficou insatisfeita com o rendimento deste rodízio e resolveu adotar um novo método. Neste novo método, a princípio tudo parecia igual: quando as moças tivessem alguma coisa para anunciar, elas reparavam se as outras estavam falando ou não. Caso não estivessem, o anúncio era feito na hora.

A diferença estava no caso de haver alguém falando. Neste segundo jeito de trabalhar, elas não ficavam esperando a primeira terminar de falar para começar logo em seguida. Ao contrário, elas esperariam um tempo aleatório. Depois que este tempo passasse, elas novamente reparariam se havia alguém falando, e o processo se repetia.

Um pequeno porém deste modelo é que, em momentos de baixo movimento, muitas vezes as moças esperavam mais do que o necessário para poder dar seus recados. Por que? Porque, por haver pouca "concorrência", eram pequenas as chances de duas começarem a falar ao mesmo tempo assim que outra terminasse, e o método de trabalho, mesmo assim, as fazia esperar um tempo aleatório, sempre maior que o tempo que a primeira levava pra terminar de falar.

Ademais, apesar de quase eliminar o número de colisões e melhorar consideravelmente o andamento do trabalho nos horários de pico, este método de trabalho trouxe um outro e sério problema: por várias vezes alguma das moças ficava um longo tempo tentando fazer o seu anúncio, sem sucesso, e às vezes o ônibus saída da rodoviária sem que ela conseguisse falar. Acontecia mais ou menos assim: a moça tinha um anúncio a fazer, mas já havia outra falando. Ela aguardava. Quando ia tentar falar, outra já tinha começado. Ela aguardava. Quando ia tentar falar, mais outra já tinha começado. E o processo se repetia uma vez atrás da outra.

***


Como forma de melhorar esta situação sem retroceder ao modelo anterior, a administração da rodoviária criou então um método misto, que tentava minimizar os dois problemas. Assim como no segundo método, ao verem que alguém já estava falando, as moças esperavam um tempo aleatório. A grande mudança trazida neste terceiro modelo foi na maneira que as moças agiam quando podiam falar.

O que acontecia, então? Quando viam que podiam dar o seu anúncio, elas jogavam um dado sobre a mesa. Se caísse 1, 2 ou 3, elas começavam a falar. Se caísse 4, 5 ou 6, elas esperariam um tempo aleatório para então ver novamente se outra estava falando, reiniciando o processo.

Trabalhando desta forma, mesmo que acontecessem casos de duas ou mais moças começarem a falar ao mesmo tempo, eram muito poucos e, ao mesmo tempo, houve uma diminuição grande nos casos de uma moça tentar falar várias vezes sem conseguir, e ninguém mais perdia seu ônibus.

Veja que, na verdade, havia 50% porcento de chances de as moças começarem a falar ou não, e que esta porcentagem poderia ser ajustada de acordo com o movimento da rodoviária.

Em momentos de baixo tráfego, em que era mais prático deixá-las falar assim que possível, poderia-se aumentar as chances de elas agirem assim simplesmente indicando que elas deveriam falar se o dado desse de 1 a 5, ou então não falariam se o dado desse 6. Do mesmo modo, em momentos de grande movimento, nos quais o segundo método é mais útil, poderia-se definir que elas não falassem se o dado desse de 2 a 6, ou então que falassem se desse 1.

A rodoviária passou a trabalhar assim, os problemas foram minimizados e todos foram felizes para sempre.

***


Pronto, se vocês entenderam esta história, entenderam os três tipos de protocolo CSMA que permitem colisão.

O CSMA 1-persistente é o primeiro: uma máquina, antes de transmitir, verifica se o canal de comunicação está sendo usado. Se não estiver sendo usado, transmite; caso contrário, fica esperando até que a outra transmissão termine para começar a sua logo em seguida.

O CSMA não-persistente é o segundo: uma máquina, antes de transmitir, verifica se o canal de comunicação está sendo usado. Se não estiver sendo usado, transmite; caso contrário, espera um tempo aleatório para tentar novamente.

O CSMA p-persistente é o terceiro: uma máquina, antes de transmitir, verifica se o canal de comunicação está sendo usado. Se estiver sendo usado, espera um tempo aleatório; caso contrário, baseada em um sorteio, ou ela transmite na mesma hora ou adia a transmissão, de acordo com um tempo aleatório.

***


Artigo do Vovó Viu a Rede: Entenda como funciona a escolha de tempo aleatório de espera

O que são protocolos CSMA (corrigido)

CSMA é a abreviação de Carrier Sense Multiple Access, ou Acesso Múltiplo e Detecção de Portadora, o que, em português para humanos, significa 'protocolos que conseguem saber se alguma máquina já está transmitindo'. Protocolos deste tipo permitem que uma máquina, antes de começar a transmitir, verifique o canal de comunicação para saber se alguma outra já está transmitindo, e o que diferencia os vários protocolos do gênero é a atitude que a máquina toma quando descobre que não pode transmitir imediatamente [correção: na verdade, há um método no qual a diferença está também no modo de agir quando pode transmitir].

Além disso, existem duas classes gerais de protocolos CSMA: os que impedem e os que não impedem a existência de colisões.

Ainda este ano colocarei aqui artigos explicando estas classes de protocolos CSMA. Primeiro veremos protocolos que permitem que colisões ocorram, e depois alguns protocolos livres de colisão.

O Protocolo Aloha

Um dos mais antigos protocolos da subcamada de acesso ao meio, nascido na década de 70, é o protocolo Aloha, que, veja só, foi criado em uma universidade havaiana. Ele não é muito confiável e por isso mesmo já quase não é mais usado hoje em dia, mas ainda assim vamos entrar em detalhes sobre ele.

De funcionamento muito simples, a primeira versão do protocolo Aloha, chamada de Aloha puro, permite que qualquer máquina da rede envie pacotes a qualquer momento e em caso de colisão avisa às máquinas transmissoras que o seus pacotes foram perdidos. Por fim, quando uma máquina recebe um aviso de colisão, ela aguarda um tempo aleatório para tentar enviar novamente. Simples assim.

Não é muito difícil perceber que este tipo de controle, ou poderíamos dizer falta de controle, gera um número enorme de colisões. Se uma máquina começar a transmitir um pacote quando um outro estiver sendo transmitido, os dois são perdidos, mesmo que só faltasse um mísero byte para terminar de transmitir o primeiro deles.

Como dito acima, ao receber um aviso de colisão as máquinas aguardam um tempo aleatório para começar a transmitir de novo. Este número deve ser aleatório, pois senão as duas máquinas esperariam o mesmo tempo e tentariam reenviar seus pacotes no mesmo momento, causando uma nova colisão, e outra, e outra, infinitamente.

Graças a tudo isso, e com base em umas contas feias que não vou mostrar a vocês como são, porque nem eu entendi como é que funcionam, obtemos um número alarmante sobre o protocolo Aloha: em média, menos de 20% dos pacotes são entregues sem problemas na transmissão.

Quando há poucas máquinas em uma rede que usa o protocolo Aloha, este número tende a aumentar, pois há menos concorrência pelo canal de transmissão, mas em redes com um número muito grande de máquinas, fica quase impossível enviar alguma coisa.

Como exemplo dessa ineficiência, veja o gráfico abaixo, que supõe que cada quadro leve quatro segundos para ser transmitido. Os quadros pintados de vermelho são os que não foram entregues por causa de colisões. Os verdes são os que puderam ser entregues corretamente.



(aproveito para lembrar que quatro segundos para transmitir um quadro é um tempo exageradamente grande se comparado à realidade, e eu uso este tempo apenas para efeitos didáticos)

***


Como forma de tentar melhorar este números, já nos anos 80 um grupo de estudiosos fez alterações no protocolo Aloha original e criaram o Slotted Aloha. Ele foi assim batizado porque utiliza o conceito de tempo fracionado (slotted).

Por acaso, a leitora do Vovó Viu a Rede já viu um metrônomo, destes usados pelos músicos para marcar o tempo das músicas? É exatamente assim que funciona o Slotted Aloha: as máquinas só podem transmitir no 'tique' do metrônomo. Além disso, o tempo não é dividido de forma aleatória: as divisões são exatamente o tempo necessário para que um pacote seja enviado corretamente.

Este avanço não impede que duas ou mais máquinas tentem transmitir pacotes no mesmo instante, mas pelo menos evita que um pacote que já começou a ser transmitido seja perdido porque outra máquina começou a transmitir alguma coisa. Com isto e com as contas cabeludas que comentei antes, a taxa de pacotes entregues com sucesso sobe um pouco, para cerca de 40%.

***


Artigo do Vovó Viu a Rede: Entenda como funciona a escolha de tempo aleatório de espera

O que fazem os protocolos da subcamada de controle de acesso ao meio?

A subcamada de controle de acesso ao meio está presente nos equipamentos das redes de difusão, cujo exemplo mais comum são as LAN's. Neste tipo de redes, há um único canal de comunicação que interliga todos os equipamentos. Os protocolos desta camada têm a tarefa de controlar o acesso dos equipamentos a este canal de comunicação (daí o nome "controle de acesso ao meio"). Este controle também é chamado mecanismo de arbitragem.

Já tratei sobre os tipos de mecanismos de arbitragem quando falei sobre as LAN's e recomendo às leitoras relerem aquele artigo para esquentar as turbinas para o que vem pela frente, que são os diversos protocolos criados para executar este trabalho espinhoso.

(Leia o artigo 'O que é LAN')