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.