Controlo de Acesso ao Meio (MAC)As implementações mais correntes de redes locais não utilizam comutação, existe um meio de transmissão que é partilhado por todos os nós. Quando um nó emite dados, todos os outros nós recebem esses dados, cabe a cada nó analisar o endereço de destino para determinar se os dados lhe são destinados.Pelo facto de todos os nós receberem os dados, este tipo de redes são conhecidas por redes de "broadcast" ou multiponto. Como o meio de transmissão é partilhado, apenas um nó pode emitir em cada instante, é necessário por isso estabelecer uma técnica para coordenar o acesso ao meio. Com este objectivo existe nestes casos, na parte inferior do nível 2 (camada de ligação lógica) uma sub-camada designada por MAC ("Medium Access Control"). Devido à partilha do meio de transmissão, os nós não podem emitir "tramas" sempre que necessitam, isto traduz-se em que o tempo efectivamente necessário a emissão de uma "trama" é composto por um tempo de espera pela disponibilidade do meio de transmissão mais o tempo efectivamente gasto de transmissão da "trama". O tempo de transmissão da trama Tt depende do comprimento da trama (L em bits) e da taxa de transmissão nominal (R em bits/seg.) sendo então Tt = L / R O tempo total necessário à emissão de uma trama será : Te = Tw + Tt O débito de dados efectivo (S) é o número real de bits/s que é possível emitir entrando em consideração com Tw. Obviamente S < R. Normalizando o débito efectivo de dados relativamente à taxa de transmissão nominal obtemos a taxa de utilização do meio de transmissão (U = S/R) que é uma medida da eficiência do MAC. Por exemplo uma taxa de utilização de 80% com uma taxa nominal de 10 Mbit/s conduz a um débito de dados de 8 Mbit/s. Em lugar de determinar o débito efectivo de dados podemos calcular U através de: Ligações ponto-a-ponto "half-duplex"O caso mais simples de necessidade de controlo de acesso ao meio surge numa ligação dedicada entre dois nós, que apenas suporta "half-duplex", ou seja não é possivel ambos os nós emitirem simultaneamente.Uma vez que apenas existem dois nós envolvidos o procedimento mais comum consiste no envio de um pedido para emitir, tudo se passa do seguinte modo:
CSMAAs inicias CSMA significam “Carrier Sense Multiple Access”, trata-se de um protocolo que permite a partilha do meio de transmissão baseando-se na detecção da existência de uma transmissão em curso (“Carrier Sense”).Quando um nó pretende emitir dados, verifica se o meio de transmissão está livre, se for esse o caso procede à emissão. Se o meio de transmissão está ocupado, existem vários algoritmos possíveis:
CSMA/CDAs iniciais CD significam “Collision Detection”, quando surge uma colisão na emissão de pacotes de dados, o meio de transmissão fica inutilizado durante toda a transmissão dos mesmos.Tipicamente a técnica CSMA/CD utiliza um algoritmo 1-persistente que é o mais eficiente sob o ponto de vista da utilização do meio de transmissão, em lugar de minimizar o número de colisões, tenta-se reduzir as suas consequências. Nas implementações CSMA anteriores, quando ocorria uma colisão o meio de transmissão ficava inutilizado por um periodo de tempo igual ao tempo de transmissão de cada uma das tramas. O mecanismo CD obriga a que os nós escutem a rede enquanto emitem dados, razão pela qual o CSMA/CD é também conhecido por “Listen While Talk” (LWT). Como o nó emissor também escuta a rede, pode detectar a colisão, nesse caso cessa imediatamente a emissão do pacote e emite um sinal ("jam") de 48 bits que notifica todas as estações de que ocorreu uma colisão. Depois da colisão o nó espera um periodo de tempo aleatório e volta a tentar. Para evitar colisões sucessivas utiliza-se uma técnica conhecida por "binary exponential backoff" em que os tempos aleatórios de espera são sempre duplicados por cada colisão que ocorre. Existe um aspecto importante a considerar para que as colisões sejam detectadas com sucesso, o tamanho mínimo dos pacotes deve ser tal que o seu tempo de transmissão seja superior ao dobro do atraso de propagação. Se isto não acontecer uma estação pode completar a emissão do pacote sem que o sinal produzido pela colisão chegue a tempo. Por outras palavras o atraso de propagação normalizado deve ser inferior a 0,5 ( a < 0,5). Por exemplo no caso das redes Ethernet (802.3) o tamanho mínimo dos pacotes é de 64 bytes. A figura seguinte ilustra a situação descrita:  O método de acesso CSMA/CD é altamente não deterministico, isto quer dizer que não é possivel prever com exactidão o seu comportamento. Podemos contudo ser optimistas e calcular a eficiência máxima deste método de acesso obdecendo a determinados pressupostos. Supondo uma rede CSMA/CD com n nós activos, se todos eles pretenderem emitir as colisões sucedem-se, vamos por isso supôr que cada nó emite com probabilidade p. É conveniente dividindo o tempo em "slots" com duração igual ao dobro do atraso de propagação porque trata-se do tempo necessário à detecção de uma colisão, logo será o tempo desperdiçado sempre que ocorre uma colisão. O valor de Tt pode ser representado por 1/2a "slots" (a é o atraso de propagação
normalizado). Por cada 1/2a "slots" em que se efectua a transmissão existe um conjunto de "slots" inutilizados correspondentes a ausências de transmissão ou colisões, este intervalo de tempo designa-se por intervalo de contenção. Pode-se obter que a probabilidade de uma estação adquirir o meio num dado "slot" (tentar emitir sem que nenhuma das outras o tente) é dada por: A = n x p x (1-p)n-1 O valor máximo desta expressão obtem-se para p = 1/n Verifica-se também que o intervalo médio de contenção em "slots" é dado por (1 - A)/A Podemos agora determinar a taxa de utilização máxima para o CSMA/CD que será: , ou : U = 1 / ( 1 + 2a(1-A)/A) “Token-passing"Esta técnica usa um pacote de controlo conhecido como “token” que dá o direito de emitir. É então necessário assegurar que apenas um nó possui o “token” em cada instante, e que por outro lado o “token” circula entre todas os nós para que todos possam emitir dados.Cada nó possui um número de ordem, o “token” circula de nó em nó segundo esta ordem, o nó de número de ordem mais elevado envia o “token” para o de ordem mais baixa. Devido a esta circulação do token, em termos lógicos os nós estão dispostos em anel (“ring”). Em termos físicos a disposição dos nós pode ser a mais diversa, mas raramente forma efectivamente um anel. Quando um nó não necessita do “token” envia-o para o nó seguinte. Para evitar uma má distribuição da utilização do meio de transmissão, geralmente os nós têm uma limitação de tempo de detenção do “token”. O grande problema desta técnica é complexidade dos algoritmos que são necessários nos nós:
Um das vantagens da técnica “token” é ser determinista, isto significa que é possível conhecer previamente o tempo máximo para transmitir uma determinada quantidade de dados. Por outro lado é fácil estabelecer prioridades, por exemplo permitindo que diferentes nós detenham o “token” durante períodos de tempo maiores ou menores. Note-se que a técnica CSMA/CD não garante sequer que um dado nó tenha alguma vez oportunidade de emitir. Pelo facto de ser deterministica, é possivel calcular a taxa de utilização máxima da técnica "token-passing" com maior exactidão, por uma questão de simplificação vamos supõr determinadas condições que existem em algumas implementações, mas não em todas:
Temos de adicionar ao tempo de retenção (Tret):
Devido à condição 2, o valor de Tret depende da relação entre Tt e Tprop, ou seja a:
O tempo de rotação do "token" (o tempo que demora a dar a "volta" ao anel) é: Trot = n x Ttot A eficiência do método de acesso é: U = Tt / Ttot Um muitos casos o tamanho do "token" (Ltk) é muito reduzido e podemos ignorar a parcela Ltk/R, é então possível obter expressões mais simples para a eficiência do método de acesso:
"CSMA/CD" vs. "Token-Passing"A técnica “token” é vantajosa sob tráfego elevado pois não existem perdas de tempo com colisões, contudo sob baixo tráfego o CSMA/CD têm a vantagem de evitar perdas de tempo com a circulação do “token” por nós que não pretendem emitir. Mas o grande problema da técnica “token” continua a ser a sua complexidade. Podemos verificar o que acontece quando aumentamos o número de estações, calculado os limitas das expressões de U quando n tende para infinito:
|