ALOHAnet - ALOHAnet

ALOHAnet , também conhecido como Sistema ALOHA , ou simplesmente ALOHA , foi um sistema de rede de computadores pioneiro desenvolvido na Universidade do Havaí . ALOHAnet tornou-se operacional em junho de 1971, fornecendo a primeira demonstração pública de uma rede de dados por pacote sem fio. ALOHA originalmente significava Additive Links On-line Hawaii Area.

A ALOHAnet utilizou um novo método de acesso médio (acesso aleatório ALOHA) e ultra-alta frequência experimental (UHF) para sua operação, uma vez que as atribuições de frequência para comunicações de e para um computador não estavam disponíveis para aplicações comerciais na década de 1970. Mas mesmo antes de tais frequências serem atribuídas, havia duas outras mídias disponíveis para a aplicação de um canal ALOHA - cabos e satélites. Na década de 1970, o acesso aleatório ALOHA foi empregado na nascente rede baseada em cabo Ethernet e depois na rede de satélites Marisat (agora Inmarsat ).

No início da década de 1980, as frequências para redes móveis tornaram-se disponíveis e, em 1985, as frequências adequadas para o que ficou conhecido como Wi-Fi foram alocadas nos Estados Unidos. Estes desenvolvimentos regulatórios possibilitaram a utilização das técnicas de acesso aleatório ALOHA tanto em redes Wi-Fi como em redes de telefonia móvel.

Os canais ALOHA foram usados ​​de forma limitada na década de 1980 em telefones celulares 1G para fins de sinalização e controle. No final da década de 1980, o grupo europeu de padronização GSM que trabalhou no sistema de comunicação móvel digital pan-europeu GSM expandiu muito o uso de canais ALOHA para acesso a canais de rádio na telefonia móvel. Além disso, o envio de mensagens de texto SMS foi implementado em telefones móveis 2G. No início dos anos 2000, canais ALOHA adicionais foram adicionados aos telefones celulares 2,5G e 3G com a introdução generalizada de GPRS , usando um canal de acesso aleatório ALOHA com fenda combinado com uma versão do esquema de reserva ALOHA analisado pela primeira vez por um grupo da BBN Technologies .

Visão geral

Um dos primeiros projetos de rede de computadores, o desenvolvimento da rede ALOHA foi iniciado em setembro de 1968 na Universidade do Havaí sob a liderança de Norman Abramson junto com Thomas Gaarder, Franklin Kuo, Shu Lin, Wesley Peterson e Edward ("Ned") Weldon . O objetivo era usar equipamento de rádio comercial de baixo custo para conectar usuários em Oahu e em outras ilhas havaianas com um computador central de compartilhamento de tempo no campus principal de Oahu. A primeira unidade de transmissão de pacotes entrou em operação em junho de 1971. Os terminais foram conectados a uma "unidade de conexão de terminal" para fins especiais usando RS-232 a 9600 bit / s.

O objetivo inicial do Sistema ALOHA era fornecer uma interação de designer sistematicamente diferente para comunicações de rádio. Este método alternativo permite que o sistema determine quando e onde as comunicações de rádio são "preferíveis" às comunicações com fio. Tornou meios de comunicação práticos e tornou plausível a acessibilidade de diferentes redes.

A versão original do ALOHA usava duas frequências distintas em uma configuração de hub, com a máquina do hub transmitindo pacotes para todos no canal "de saída" e as várias máquinas clientes enviando pacotes de dados para o hub no canal de "entrada". Se os dados foram recebidos corretamente no hub, um pacote curto de confirmação foi enviado ao cliente; se uma confirmação não fosse recebida por uma máquina cliente após um curto tempo de espera, ela retransmitiria automaticamente o pacote de dados após aguardar um intervalo de tempo selecionado aleatoriamente. Este mecanismo de confirmação foi usado para detectar e corrigir "colisões" criadas quando duas máquinas clientes tentavam enviar um pacote ao mesmo tempo.

A importância primária da ALOHAnet era o uso de um meio compartilhado para as transmissões do cliente. Ao contrário da ARPANET, em que cada nó só pode falar diretamente com um nó na outra extremidade de um fio ou circuito de satélite, no ALOHAnet todos os nós clientes se comunicam com o hub na mesma frequência. Isso significava que algum tipo de mecanismo era necessário para controlar quem poderia falar a que horas. A solução ALOHAnet era permitir que cada cliente enviasse seus dados sem controlar quando eles eram enviados, com um esquema de reconhecimento / retransmissão usado para lidar com as colisões. Essa abordagem reduziu radicalmente a complexidade do protocolo e do hardware de rede, uma vez que os nós não precisam negociar "quem" tem permissão para falar.

Esta solução tornou-se conhecida como ALOHA puro, ou canal de acesso aleatório, e foi a base para o desenvolvimento subsequente de Ethernet e redes Wi-Fi posteriores . Várias versões do protocolo ALOHA (como Slotted ALOHA) também apareceram mais tarde nas comunicações por satélite e foram usadas em redes de dados sem fio como ARDIS , Mobitex , CDPD e GSM .

Também importante foi o uso do canal hub de saída pela ALOHAnet para transmitir pacotes diretamente a todos os clientes em uma segunda frequência compartilhada, usando um endereço em cada pacote para permitir o recebimento seletivo em cada nó cliente. Duas frequências foram usadas para que um dispositivo pudesse receber confirmações independentemente das transmissões. A rede Aloha introduziu o mecanismo de acesso múltiplo aleatório, que resolveu as colisões de transmissão do dispositivo transmitindo um pacote imediatamente se nenhuma confirmação estiver presente e, se nenhuma confirmação for recebida, a transmissão será repetida após um tempo de espera aleatório.

Protocolo ALOHA

ALOHA puro

Gráfico de frames sendo enviados de 4 estações diferentes de acordo com o protocolo ALOHA puro em relação ao tempo, com frames sobrepostos sombreados para denotar colisão.
Protocolo ALOHA puro. As caixas indicam molduras. As caixas sombreadas indicam os quadros que colidiram.

A versão do protocolo (agora chamado de "Puro ALOHA", e aquele implementado em ALOHAnet) era bastante simples:

  • Se você tiver dados para enviar, envie os dados
  • Se, durante a transmissão de dados, você receber dados de outra estação, houve uma colisão de mensagens. Todas as estações transmissoras precisarão tentar reenviar "mais tarde".

Observe que a primeira etapa implica que o Pure ALOHA não verifica se o canal está ocupado antes de transmitir. Uma vez que podem ocorrer colisões e os dados podem ter que ser enviados novamente, o ALOHA não pode usar 100% da capacidade do canal de comunicação. O tempo que uma estação espera até transmitir e a probabilidade de ocorrer uma colisão estão inter-relacionados e ambos afetam a eficiência com que o canal pode ser usado. Isso significa que o conceito de "transmitir mais tarde" é um aspecto crítico: a qualidade do esquema de backoff escolhido influencia significativamente a eficiência do protocolo, a capacidade final do canal e a previsibilidade de seu comportamento.

Para avaliar o Puro ALOHA, é necessário prever sua taxa de transferência, a taxa de transmissão (bem-sucedida) de quadros. (Esta discussão sobre o desempenho do Pure ALOHA segue Tanenbaum.) Primeiro, vamos fazer algumas suposições simplificadoras:

  • Todos os quadros têm o mesmo comprimento.
  • As estações não podem gerar um quadro enquanto transmitem ou tentam transmitir. (Ou seja, se uma estação continuar tentando enviar um quadro, ela não poderá gerar mais quadros para enviar.)
  • A população de estações tenta transmitir (tanto novos quadros quanto antigos que colidiram) de acordo com uma distribuição de Poisson .

Vamos " T " referem-se ao tempo necessário para transmitir um quadro no canal, e vamos definir "frame-time" como uma unidade de tempo igual ao T . Suponha que " G " se refira à média usada na distribuição de Poisson sobre as quantidades de tentativas de transmissão: isto é, em média, existem G tentativas de transmissão por tempo de quadro.

Gráfico de 3 quadros em relação ao tempo.  O quadro verde anterior se sobrepõe ao quadro amarelo enviado no momento t0, que se sobrepõe ao quadro roxo posterior.
Quadros sobrepostos no protocolo ALOHA puro. O tempo de quadro é igual a 1 para todos os quadros.

Considere o que precisa acontecer para que um quadro seja transmitido com êxito. Deixe " t " referir-se ao momento em que se pretende enviar um quadro. É preferível usar o canal para um tempo de quadro começando em t , e todas as outras estações para evitar a transmissão durante esse tempo.

Para qualquer frame-time, a probabilidade de haver k tentativas de transmissão durante esse frame-time é:

Taxa de transferência versus carga de tráfego de Pure Aloha e Slotted Aloha.
Comparação de Pure Aloha e Slotted Aloha mostrado no gráfico Throughput vs. Traffic Load.

A quantidade média de transmissão de tentativas para 2 frame-vezes consecutivas é 2 L . Portanto, para qualquer par de tempos de quadro consecutivos, a probabilidade de haver k tentativas de transmissão durante esses dois tempos de quadro é:

Portanto, a probabilidade ( ) de haver zero tentativas de transmissão entre tT e t + T (e, portanto, de uma transmissão bem-sucedida para nós) é:

A taxa de transferência pode ser calculada como a taxa de tentativas de transmissão multiplicada pela probabilidade de sucesso, e pode-se concluir que a taxa de transferência ( ) é:

Tempo vulnerável = 2T.

A taxa de transferência máxima é de 0,5 / e quadros por tempo de quadro (alcançado quando G = 0,5), que é de aproximadamente 0,184 quadros por tempo de quadro. Isso significa que, no Pure ALOHA, apenas cerca de 18,4% do tempo é usado para transmissões bem-sucedidas.

Outra maneira simples de estabelecer a equação para a taxa de transferência no Puro ALOHA (e no Slotted ALOHA) é a seguinte:

Considere o que precisa acontecer para que os quadros sejam transmitidos com êxito. Deixe T representar o tempo de moldura. Para simplificar, assume-se que a contenção começa em t = 0. Então, se exatamente um nó enviar durante o intervalo t = 0 a t = T e nenhum outro nó tentar entre t = T a t = 2T, então o quadro será transmitido com sucesso. Da mesma forma, durante todos os próximos intervalos de tempo t = 2nT a t = (2n + 1) T, exatamente um nó envia e durante t = (2n + 1) T a t = (2n + 2) T nenhum nó tenta enviar onde n = 1,2,3, ..., então os quadros são transmitidos com sucesso. Mas no ALOHA puro, os nós começam a transmissão sempre que desejam, sem verificar o que os outros nós estão fazendo naquele momento. Assim, os quadros de envio são eventos independentes, ou seja, a transmissão por qualquer nó em particular não afeta nem é afetada pelo tempo de início da transmissão por outros nós. Seja G o número médio de nós que começam a transmissão dentro do período T (o tempo de quadro). Se um grande número de nós está tentando transmitir, então usando a distribuição de Poisson, a probabilidade de que exatamente x nós comecem a transmissão durante o período T é

Portanto, a probabilidade de que durante qualquer período particular de t = 2nT a t = (2n + 1) T, (ou seja, para qualquer valor inteiro diferente de zero de n) exatamente um nó começará a transmissão é

E a probabilidade de que durante qualquer período particular t = (2n + 1) T a t = (2n + 2) T, nenhum nó iniciará a transmissão é

Mas, para a transmissão bem-sucedida de um quadro, ambos os eventos devem ocorrer simultaneamente. Isto é, durante o período t = 2nT a t = (2n + 1) T, exatamente um nó começa a transmissão e durante t = (2n + 1) T a t = (2n + 2) T nenhum nó começa a transmissão. Portanto, a probabilidade de que ambos os eventos independentes ocorram simultaneamente é

Esta é a taxa de transferência. A taxa de transferência se destina a significar a probabilidade de transmissão bem-sucedida durante o período mínimo possível. Portanto, a taxa de transferência em ALOHA puro,

Suponha:

1) Existem N nós tentando enviar dados no tempo T.
2) A probabilidade de transmissão bem-sucedida de um nó é .

Então, a probabilidade de transmissão bem-sucedida da seguinte forma:

Da mesma forma, para ALOHA com intervalo, um quadro será transmitido com êxito, se exatamente um nó iniciar a transmissão no início de qualquer intervalo de tempo específico (igual ao tempo de quadro T). Mas a probabilidade de que um nó começará durante qualquer intervalo de tempo particular é

Esta é a taxa de transferência em ALOHA com fenda. Assim,

Desvantagens do Puro ALOHA:

1) Tempo é desperdiçado
2) Dados são perdidos

ALOHA com fenda

Gráfico de quadros sendo enviados de 8 estações diferentes de acordo com o protocolo ALOHA com intervalo em relação ao tempo, com quadros nos mesmos slots sombreados para denotar colisão.
Protocolo ALOHA com fenda. As caixas indicam molduras. As caixas sombreadas indicam quadros que estão nos mesmos slots.

Uma melhoria no protocolo ALOHA original foi "Slotted ALOHA", que introduziu timeslots discretos e aumentou o rendimento máximo. Uma estação pode iniciar uma transmissão apenas no início de um intervalo de tempo e, portanto, as colisões são reduzidas. Nesse caso, apenas as tentativas de transmissão em 1 tempo de quadro e não em 2 tempos de quadro consecutivos precisam ser consideradas, uma vez que as colisões só podem ocorrer durante cada intervalo de tempo. Assim, a probabilidade de haver zero tentativas de transmissão por outras estações em um único timeslot é:

a probabilidade de uma transmissão exigir exatamente k tentativas é (k-1 colisões e 1 sucesso):

A taxa de transferência é:

A taxa de transferência máxima é de 1 / e quadros por tempo de quadro (alcançado quando G = 1), que é de aproximadamente 0,368 quadros por tempo de quadro, ou 36,8%.

Slotted ALOHA é usado em redes de comunicações táticas por satélite de baixa taxa de dados por forças militares, em redes de comunicações por satélite baseadas em assinantes, configuração de chamadas de telefonia móvel, comunicações de decodificadores e tecnologias RFID sem contato .

Outros protocolos

O uso de um canal de acesso aleatório no ALOHAnet levou ao desenvolvimento do acesso múltiplo com detecção de portadora (CSMA), um protocolo de acesso aleatório "ouvir antes de enviar" que pode ser usado quando todos os nós enviam e recebem no mesmo canal. A primeira implementação do CSMA foi Ethernet . O CSMA em canais de rádio foi amplamente modelado. O protocolo de rádio de pacote AX.25 é baseado na abordagem CSMA com recuperação de colisão, com base na experiência adquirida com ALOHAnet.

ALOHA e os outros protocolos de acesso aleatório têm uma variabilidade inerente em suas características de desempenho de rendimento e atraso. Por esse motivo, os aplicativos que precisam de um comportamento de carga altamente determinístico às vezes usavam esquemas de sondagem ou passagem de token (como Token Ring ) em vez de sistemas de contenção . Por exemplo, ARCNET era popular em aplicativos de dados incorporados na rede de 1980.

Projeto

Arquitetura de rede

Duas escolhas fundamentais que ditaram muito do projeto ALOHAnet foram a configuração em estrela de dois canais da rede e o uso de acesso aleatório para as transmissões do usuário.

A configuração de dois canais foi escolhida principalmente para permitir a transmissão eficiente do fluxo de tráfego total relativamente denso que está sendo retornado aos usuários pelo computador central de compartilhamento de tempo. Uma razão adicional para a configuração em estrela foi o desejo de centralizar tantas funções de comunicação quanto possível no nó central da rede (o Menehune), minimizando o custo da unidade de controle de terminal de hardware (TCU) original em cada nó de usuário.

O canal de acesso aleatório para comunicação entre os usuários e o Menehune foi projetado especificamente para as características de tráfego da computação interativa. Em um sistema de comunicação convencional, um usuário pode ser atribuído a uma parte do canal em uma base de acesso múltiplo por divisão de frequência (FDMA) ou acesso múltiplo por divisão de tempo (TDMA). Como era bem sabido que em sistemas de compartilhamento de tempo [por volta de 1970], os dados do computador e do usuário são intermitentes, essas atribuições fixas geralmente perdem largura de banda devido às altas taxas de dados de pico à média que caracterizam o tráfego.

Para obter um uso mais eficiente da largura de banda para tráfego em rajadas, a ALOHAnet desenvolveu o método de comutação de pacotes de acesso aleatório que passou a ser conhecido como canal ALOHA puro . Essa abordagem aloca de forma dinâmica e eficaz a largura de banda imediatamente para um usuário que tem dados para enviar, usando o mecanismo de confirmação / retransmissão descrito anteriormente para lidar com colisões de acesso ocasionais. Embora a carga média do canal deva ser mantida abaixo de cerca de 10% para manter uma taxa de colisão baixa, isso ainda resulta em melhor eficiência de largura de banda do que quando alocações fixas são usadas em um contexto de tráfego em rajadas.

Dois canais de 100 kHz na banda UHF experimental foram usados ​​no sistema implementado, um para o canal de acesso aleatório usuário-computador e outro para o canal de transmissão computador-a-usuário. O sistema foi configurado como uma rede estrela, permitindo apenas o nó central receber as transmissões no canal de acesso aleatório. Todos os TCUs do usuário receberam cada transmissão feita pelo nó central no canal de transmissão. Todas as transmissões foram feitas em rajadas a 9600 bit / s, com dados e informações de controle encapsuladas em pacotes.

Cada pacote consistia em um cabeçalho de 32 bits e uma palavra de verificação de paridade de cabeçalho de 16 bits, seguida por até 80 bytes de dados e uma palavra de verificação de paridade de 16 bits para os dados. O cabeçalho continha informações de endereço identificando um determinado usuário, de modo que, quando o Menehune transmitisse um pacote, apenas o nó do usuário pretendido o aceitaria.

Menehune

O processador de comunicação do nó central era um minicomputador HP 2100 chamado Menehune, que é a palavra havaiana para "imp", ou povo anão, e foi nomeado por sua função semelhante ao ARPANET Interface Message Processor (IMP) original que estava sendo implantado quase ao mesmo tempo. No sistema original, o Menehune encaminhava os dados do usuário corretamente recebidos para o computador central do UH, um sistema de compartilhamento de tempo IBM System 360/65 . As mensagens de saída do 360 foram convertidas em pacotes pelo Menehune, que foram enfileirados e transmitidos aos usuários remotos a uma taxa de dados de 9600 bits / s. Ao contrário dos rádios half-duplex nos TCUs do usuário, o Menehune fazia interface com os canais de rádio com equipamento de rádio full-duplex.

Unidades remotas

A interface de usuário original desenvolvida para o sistema era uma unidade de hardware chamada ALOHAnet Terminal Control Unit (TCU), e era a única peça do equipamento necessária para conectar um terminal ao canal ALOHA. O TCU era composto por antena UHF, transceptor, modem, buffer e unidade de controle. O buffer foi projetado para um comprimento de linha completo de 80 caracteres, o que permitiu o manuseio de pacotes de comprimento fixo de 40 e 80 caracteres definidos para o sistema. O terminal de usuário típico no sistema original consistia em um Teletipo Modelo 33 ou um terminal de usuário CRT burro conectado ao TCU usando uma interface RS-232C padrão. Logo após a rede ALOHA original entrar em operação, o TCU foi redesenhado com um dos primeiros microprocessadores Intel, e a atualização resultante foi chamada de PCU (Unidade de Controle Programável).

Funções básicas adicionais executadas pelos TCU's e PCU's foram a geração de um vetor de código de verificação de paridade cíclica e decodificação de pacotes recebidos para fins de detecção de erros de pacotes e geração de retransmissões de pacotes usando um gerador de intervalo aleatório simples. Se uma confirmação não fosse recebida do Menehune após o número prescrito de retransmissões automáticas, uma luz piscante era usada como um indicador para o usuário humano. Além disso, como os TCU's e PCU's não enviaram confirmações ao Menehune, uma luz de alerta constante foi exibida para o usuário humano quando um erro foi detectado em um pacote recebido. Assim, pode-se perceber que houve considerável simplificação tanto no desenho inicial do TCU quanto no da PCU, aproveitando-se do fato de estar fazendo a interface de um usuário humano na rede.

Desenvolvimentos posteriores

Em versões posteriores do sistema, relés de rádio simples foram colocados em operação para conectar a rede principal na ilha de Oahu a outras ilhas do Havaí, e as capacidades de roteamento de Menehune foram expandidas para permitir que nós de usuário troquem pacotes com outros nós de usuário, a ARPANET e uma rede de satélites experimental. Mais detalhes estão disponíveis nos relatórios técnicos listados na seção Leituras Adicionais abaixo.

Referências

Leitura adicional

  • Stallings, William (1988). Comunicações de dados e computador (2ª ed.). MacMillan. pp. 296-302. ISBN 978-0-02-415451-4.
  • R. Metcalfe, memorando do Xerox PARC, de Bob Metcalfe para Alto Aloha Distribution on Ether Acquisition, 22 de maio de 1973.
  • R. Binder, Protocolos ALOHAnet, Relatório Técnico do Sistema ALOHA, Faculdade de Engenharia, Universidade do Havaí, setembro de 1974.
  • R. Binder, WS Lai e M. Wilson, The ALOHAnet Menehune - Versão II, Relatório Técnico do Sistema ALOHA, Faculdade de Engenharia, Universidade do Havaí, setembro de 1974.
  • N. Abramson, Relatório Técnico Final do Sistema ALOHA, Agência de Projetos de Pesquisa Avançada, Número do Contrato NAS2-6700, 11 de outubro de 1974.
  • N. Abramson "The Throughput of Packet Broadcasting Channels", IEEE Transactions on Communications, Vol 25 No 1, pp117–128, janeiro de 1977.
  • M. Schwartz, Mobile Wireless Communications, Cambridge Univ. Press, 2005.
  • KJ Negus e A. Petrick, História das Redes Locais Sem Fio (WLANs) nas Bandas Não Licenciadas, Conferência da Escola de Direito da Universidade George Mason, Projeto de Economia da Informação, Arlington, VA., EUA, 4 de abril de 2008.
  • H. Wu; C. Zhu; RJ La; X. Liu; Y. Zhang. "FASA: S-ALOHA acelerado usando histórico de acesso para comunicações M2M baseadas em eventos" (PDF) . IEEE / ACM Transactions on Networking, 2013.

links externos