Aulas 13 & 14. Acesso Múltiplo a Pacote: Protocolo Aloha. Eytan Modiano MIT - PDF
Aulas 13 & 14. Acesso Múltiplo a Pacote: Protocolo Aloha. Eytan Modiano MIT
Download "Aulas 13 & 14. Acesso Múltiplo a Pacote: Protocolo Aloha. Eytan Modiano MIT"
Nicolas Desconhecida Cipriano
1 Aulas 13 & 14 Acesso Múltiplo a Pacote: Protocolo Aloha Eytan Modiano MIT 1
2 Acesso Múltiplo Meio de transmissão compartilhado: um receptor pode escutar vários transmissores; um transmissor pode ser escutado por múltiplos receptores. O maior problema com o múltiplo acesso é a alocação do canal entre os usuários; os nós não sabem quando os outros nós tem dados para enviar. Necessidade de coordenar aa transmissões. 2
3 Exemplos de Canais de Acesso Múltiplo Redes Locais LANs Ethernet tradicional. Recentemente há uma tendência para LANs que não utilizam o acesso múltiplo. Canais via satélite Telefone multi-linhas multi drop Comunicações sem fio via rádio enlace Controle de Acesso ao Meio Medium Access Control - MAC. - Regula o acesso ao canal. Controle do enlace lógico Logical Link Control - LLC - Todas as outras funções DLC, NET, DLC, PHY, MAC, LLC. 3
4 Soluções para o Acesso Múltiplo Alocação Fixa TDMA, FDMA, CDMA A cada nó é alocado a uma fração fixa da largura de faixa. Equivalente á comutação por circuito. Muito ineficiente para tráfego tipo rajada. Sistemas de Alocação Dinâmica Polling interrogação. Reserva e escalonamento. Acesso aleatório. 4
5 Aloha Único receptor, muitos transmissores. Por ex.: sistema via satélite, comunicação sem fio. 5
6 Aloha Fatiado O tempo é dividido em fatias de duração de um pacote. Por ex.: pacotes de tamanho fixo. Quando um nó tem um pacote para enviar, espera até o início da próxima fatia de tempo para enviá-lo. Requer sincronização. Se nenhum outro nó tentar a transmissão durante esta fatia de tempo, a transmissão será bem sucedida. Caso contrário haverá uma colisão. Pacotes que colidiram serão retransmitidos após um atraso aleatório. 6
7 Hipóteses Sobre o Aloha Fatiado Chegadas de Poisson Não há captura Pacotes envolvidos em uma colisão são perdidos. Modelos de Captura também são possíveis. Realimentação imediata Não ativo 0, Sucesso 1, Colisão e. Se um novo pacote chega durante uma fatia, transmita na próxima. Se ocorre transmissão, o nó fica aguardando a retransmissão I; Enquanto fica aguardando para retransmitir, transmite em cada fatia com probabilidade q r até obter sucesso. Número de nós infinito onde cada pacote chega a um novo nó; Equivale a não ter armazenamento no nó tamanho da fila = 1; Hipótese pessimista fornece um baixo limitante para o desempenho do Aloha. 7
8 Cadeia de Markov Para o Aloha Fatiado Estado n do sistema é o número de nós que devem retransmitir: pi,i-1 = probabilidade de um dos nós com retransmissão tentar o acesso na ausência de novos pacotes. pi,i = probabilidade uma nova chegada sem tentativa de retransmitir pacotes anteriores ou de tentativa de retransmissão de pacotes antigos sem sucesso. pi,i+1= probabilidade de uma nova chegada e uma ou mais tentativas de retransmissão. pi,i+j = probabilidade de j novas chegadas e uma ou mais tentativas de retransmissão ou j+1 novas chegadas e nenhuma tentativa de retransmissão. Probabilidades do estado estacionário não existem: Retransmissões tendem para infinito sistema instável. Mais informações serão dadas adiante. 8
9 Aloha Fatiado Seja gn a taxa de tentativas o número esperado de pacotes transmitidos em uma fatia do tempo no estado n gn = λ + nq r O número de tentativas por fatia no estado n é aproximadamente uma variável aleatória de Poisson com gn Pm tentativas = gnme-gn/m! Pnão ativo = probabilidade de nenhuma tentativa na fatia de tempo = e-gn Psucesso = probabilidade de uma tentativa em uma fatia = gnegn Pcolisão = Pduas ou mais tentativas = 1-Pnão ativo-psucesso 9
10 10 Vazão do Aloha Fatiado A vazão é a fração de fatias que contem uma transmissão bem sucedida = Psucesso = gne-gn Quando o sistema é estável a vazão deve ser igual a taxa de chegada λ Qual valor de gn maximize a vazão? gn < 1 => muitas fatias de tempo não utilizadas gn > 1 =>muitas colisões Se gn pode ser feito próximo de 1, uma taxa de entrada de 1/e pacotes por fatia pode ser suportada 0,36 1/ 1 0 = = = = = e e n g success P n g e n g e e n g n dg d n g n g n g n g
11 Instabilidade do Aloha Fatiado Se o número de nós que devem retransmitir aumenta além do ponto de instabilidade então este número tende a crescer sem limite e a vazão vai para 0. Deslocamento no estado n, Dn é mudança esperada no número de nós com retransmissão sobre uma fatia de tempo. Dn = λ -Psucesso = λ -gne-gn 11
12 Estabilizando o Aloha Fatiado Escolhendo q r pequeno aumenta o número de retransmissões até que a instabilidade ocorre pois gn = λ + nq r, mas também aumenta o atraso pois o tempo médio para retransmitir é 1/q r. Solução: estime o número de nós com retransmissões n a partir da última realimentação. Com este estimador, escolha q r para ter gn = 1 Suponha que todas as chegadas sejam enfileiradas gn = nq r, Psucesso = nq r 1-q r n-1 Para maximizar Psucesso escolha q r = min{1,1/n} Quando o estimador de n é perfeito: fatias não usadas ocorrem com probabilidade 1/e, sucesso com 1/e, colisões com 1-2/e Quando o estimador é muito grande, muitas fatias não utilizadas ocorrem. Quando estimador é muito pequeno, muitas colisões ocorrem. Nós podemos usar a informação de realimentação 0,1,e para fazer a estimação Uma boa regra é aumentar o estimador de n a cada colisão, e descresse-lo a cada fatia não utilizada ou fatia com sucesso A. observe que o incremento na colisão poderá ser e-2-1 vezes maior quanto for o decréscimo nas fatias não utilizadas. 12
13 Aloha Fatiado Estabilizado Suponha que todas as chegadas sejam enfileiradas. gn = nq r = taxa de tentativas psucesso = nq r 1-q r n-1p Para máxima vazão faça gn = 1 q r = min{1,1/n } Onde n é o estimador de n. Seja n k = estimador do número de nós com retransmissão após a k th fatia. n k+1 = máx {λ, n k +λ-1} não ativo ou sucesso n k +λ+e-2-1 colisão Pode ser mostrado que é estável paraλ < 1/e. 13
14 TDM vs Aloha Fatiado Aloha tem baixos atrasos quando a taxa de chegada é baixa TDM apresenta um atraso muito grande com grande número de usuários, enquanto que o Aloha é independente do número de usuários. 14
15 Aloha Puro não fatiado - unslotted Novas chegadas são transmitidas imediatamente não existem fatia. Não precisa de sincronização. Não precisa de pacotes de comprimento fixo. Um pacote para ser retransmitido é submetido para transmissão após um atraso aleatório com distribuição exponencial cuja média é 1/x. O processo de chegada total é um processo de Poisson variante no tempo com taxa gn = λ + nx. n = número de estações com retransmissão, 1/x =tempo médio entre retransmissões. Observe que uma tentativa sofre colisão se a tentativa anterior ainda não foi finalizada t i -t i -1<1 ou a próxima tentativa inicia muito cedo t i+1 t i < 1. 15
16 Vazão do Aloha Uma tentativa é bem sucedida se os intervalos entre tentativas em ambos os lados excede 1 para pacotes de duração unitária. Psucesso = e-gn e-gn = e-2gn Problemas de estabilização são similares ao do aloha fatiado. Vantagens do aloha é a simplicidade e a possibilidade de pacotes de comprimento não igual. 16
17 Algoritmos de Divisão Procedimento mais eficiente para resolver as colisões. Realimentação simple 0,1,e Idéia básica: suponha que somente dois pacotes se envolvem em uma colisão assume. Suponha que todos os outros nós não tentam transmitir até que a colisão é resolvida, e cada um dos nós envolvidos na colisão transmite com probabilidade ½ até que um é bem sucedido. Na próxima fatia após este sucesso, o outro nó transmite. O número esperado de fatias para o primeiro sucesso é 2, portanto o número esperado de fatias para transmitir 2 pacotes é 3. A vazão sobre 3 fatias = 2/3. Na prática o algoritmo acima não é factível. Não se pode supor que somente dois usuários irão colidir. Algoritmos práticos devem permitir colisões envolvendo um número desconhecido de usuários. 17
18 Algoritmos Árvore Após uma colisão, todas as novas chegadas e todos os pacotes esperando retransmissão não envolvidos na colisão esperam. Cada pacote que colidiu se junta em um dos dois grupos grupos à esquerda e a direita. Lance um dado honesto O grupo da esquerda transmite na fatia seguinte enquanto que o grupo da direita espera. Se a colisão ocorre o grupo esquerdo dividese novamente algoritmo pilha. Grupo a direita espera até que a colisão na esquerda é resolvida. Quando o grupo a esquerda terminar o da direita pode transmitir. Observe que após a fatia não utilizada, a colisão entre 2,3 era previsível que iria acontecer e poderia ser evitada. Muitas variações e melhorias no algoritmo original da divisão. 18
19 Comparação da Vazão Aloha puro estável T = 0,184 = 1/2e Aloha fatiado estável T = 0,368 = 1/e Algoritmo em arvore básico T = 0,434 Variações mais conhecidas do algoritmo T = 0,4878 Limite superior sobre qualquer algoritmo de solução de conflito com realimentação 0,1,e T 0,568. TDM atinge a vazão de um pacote por fatia, mas o atraso aumenta linearmente com o número de nós. 19
João Baptista Bayão Ribeiro ALGORITMOS DE ACESSO
João Baptista Bayão Ribeiro ALGORITMOS DE ACESSO Rio de Janeiro 2015 2 Curriculum do Autor Currículo resumido do autor João Baptista Bayão Ribeiro é formado em Engenharia de Telecomunicações pela UFF (Universidade
Características dos Protocolos. Tipos de Protocolos. Protocolos de Acesso baseados em Contenção. Protocolos de de Acesso ao ao Meio
Departamento de Engenharia de elecomunicações - UFF Disciplina: Protocolos de de Acesso ao ao Meio Capacidade Características dos Protocolos Estabilidade em sobrecarga Justiça ( fairness ) Prioridade etardo
Redes sem Fio Redes Locais Wireless (WLANs) Ricardo Kléber. Ricardo Kléber
Redes sem Fio 2016.1 Redes Locais Wireless (WLANs) 802.11 Curso Superior de Tecnologia em Sistemas para Internet Turma: TEC.SIS.5M Redes sem Fio Conteúdo Programático Sistemas de comunicação wireless Redes
TÉCNICAS DE ACESSO PARA SISTEMAS DE COMUNICAÇÃO MÓVEL
TÉCNICAS DE ACESSO PARA SISTEMAS DE COMUNICAÇÃO MÓVEL Prof. Doutor Félix Singo Introdução Comunicações Móveis Para quê técnicas de acesso? Permitir o compartilhamento de uma determinada faixa de rádio
3 ALGORITMOS DE ENFILEIRAMENTO
3 ALGORITMOS DE ENFILEIRAMENTO Uma das maneiras que os elementos de redes (tipicamente roteadores) possuem para controlar as sobrecargas de pacotes nos buffers desses dispositivos de rede é através do