Aula8 2013

Prévia do material em texto

1 
Protocolos de Camada de Enlace: 
1- Tipos de Enlaces 
Dois tipos : 
� ponto-a-ponto 
� Consiste em único remetente em uma extremidade do enlace 
e um único receptor na outra extremidade (meio não 
compartilhado, ex. PPP, SLIP, HDLC) 
� Broadcast (Multiponto) (meio compartilhado; ex, Ethernet) 
� Vários nós remetentes e receptores, todos conectados ao 
mesmo canal de transmissão único e compartilhado. 
� Necessidade de acesso múltiplo 
� Como controlar o acesso dos múltiplos nós remetentes e 
receptores 
� solução: protocolos de acesso múltiplo 
 
 2 
2 – Protocolos de Acesso Múltiplo 
Consideracões iniciais 
� Canal de comunicação único e compartilhado. 
� Muitos nós querem transmitir quadros frequentemente. 
� Muitas transmissões vão resultar em colisões e grande parte 
da largura de banda do canal broadcast será desperdiçada. 
� Duas ou mais transmissões pelos nós: interferência 
� apenas um nó pode transmitir com sucesso num dado 
instante de tempo. 
� Necessidade de coordenar as transmissões. 
� Coordenação é de responsabilidade do protocolo de acesso 
múltiplo. 
2.1 -Classificação dos protocolos de Acesso Múltiplo: 
� Protocolos de divisão de canal 
� Protocolos de acesso aleatório 
� Protocolos de revezamento. 
� Características desejáveis de um protocolo de Acesso 
Múltiplo (velocidade de R bps em um canal broadcast com N 
nós): 
� Se apenas um nó tem dados para enviar, esse nó deverá 
ter uma produtividade de R bps. 
� Se N nós tem dados para enviar, cada um desses nós 
deverá ter uma produtividade de R/N bps (velocidade 
média de transmissão durante um período de tempo) 
 3 
� Protocolo descentralizado (sem nós mestres que possam 
falhar e derrubar o sistema inteiro) 
� Protocolo simples (implementação barata) 
2.1.1- Protocolos de Divisão de Canal 
� TDM (Multiplexação por Divisão de Tempo) 
� FDM (Multiplexação por Divisão de Frequência) 
� CDMA (Acesso Múltiplo por Divisão de Código) 
TDM: Multilpexação por Divisão de Tempo 
� Divide o tempo em quadros temporais. 
� Divide cada quadro temporal em N compartimentos. 
� Cada compartimento é atribuído a um dos N nós. 
� Cada nó (estação) controla um compartimento (“slot”) de 
tamanho fixo (tamanho = tempo de transmissão de pacote) 
em cada compartimento. 
� Vantagens: 
� Elimina colisões (cada nó transmite dentro do seu 
compartimento). 
� Cada nó ganha uma velocidade de transmissão dedicada 
de R/N bps durante cada quadro temporal. 
� Desvantagens: 
� Um nó fica limitado a uma velocidade média de R/N bps 
(mesmo sendo o único nó com quadros para enviar). 
� Um nó deve sempre esperar sua vez na seqüência de 
transmissão (atraso no tempo para transmitir). 
� compartimentos não usados são desperdiçados. 
 4 
� exemplo: rede local com 6 estações: 1,3,4 têm 
pacotes, compartimentos 2,5,6 ficam vazios 
 
 
 
FDM: Multiplexação por Divisão de Frequência 
� o espectro do canal (velocidade do canal = R bps), é dividido 
em bandas de freqüência 
� cada nó (estação) recebe uma banda de freqüência (canais 
menores de R/N bps, N = nº de nós) 
� FDM cria N canais menores de R/N bps a partir de um único 
canal maior de R bps 
� Vantagens: 
� Elimina colisões(cada nó transmite dentro da sua banda 
de freqüência). 
� Cada nó ganha uma velocidade de transmissão dedicada 
de R/N bps dentro da respectiva banda de freqüência. 
� Desvantagens: 
� Um nó fica limitado a uma velocidade média de R/N bps 
(mesmo sendo o único nó com quadros para enviar). 
� Período de transmissão ocioso significa banda de 
freqüência desperdiçada. 
� exemplo: rede local com 6 estações: 1,3,4 têm 
pacotes, as bandas de freqüência 2,5,6 ficam vazias. 
 
 5 
 
 
 
 
 
 
 
 
CDMA:Acesso Múltiplo por Divisão de Código 
� Um código único é atribuído a cada nó, isto é, o código define 
o particionamento. 
� Muito usado em canais broadcast, sem-fio (celular, satélite, 
etc) 
� Todos os usuários usam a mesma freqüência, mas cada 
usuário tem a sua própria maneira de codificar os dados. 
� Esta codificação é definida pelo código que o usuário recebe 
(“chipping sequence”) 
� sinal codificado = (dados originais) X (chipping sequence). 
� decodificação: seqüência inversa no receptor. 
� permite que múltiplos usuários “coexistam” e transmitam 
simultaneamente e que seus receptores respectivos recebam 
corretamente os bits codificados pelo remetente com mínima 
interferência. 
Vantagens: 
1 
 
 
2 
 
3 
 
4 
 
 
5 
 
6 
bandas 
de 
freqüência 
tempo 
 6 
 - Um nó transmitindo alcança R bps(Taxa de transmissão 
conforme o congestionamento da rede). 
 - Descentralizado 
- Desvantagens: 
- Complexidade para decifrar e extrair mensagens dos 
sinais recebidos (não é simples) 
2.1.2- Protocolos de Acesso Aleatório 
� Quando o nó tem um pacote a enviar: 
� transmite com toda a taxa total do canal (R). 
� não há uma regra de coordenação a priori entre os nós 
� Dois ou mais nós transmitindo -> “colisão” 
� Quando há uma colisão, cada nó envolvido nela transmite seu 
quadro até que este passe sem colisão. 
� Quando ocorre uma colisão o nó não retransmite o quadro 
imediatamente => espera um tempo aleatório antes de 
retransmitir o quadro. 
� Protocolos de acesso aleatório que serão vistos: 
� ALOHA 
� slotted ALOHA 
� CSMA e CSMA/CD 
� ALOHA 
� Características: 
� Quando uma estação tem dados a enviar, ela 
simplesmente faz a transmissão. Quando a central recebe 
os dados corretamente, ela envia uma mensagem de 
 7 
confirmação para a estação. Se a estação não recebe tal 
confirmação dentro de um intervalo de tempo 
predefinido, ela faz a retransmissão dos dados. 
� Transmite com toda a taxa total do canal (R). 
� Não requer que haja sincronismo entre os nós de modo 
que cada nó saiba onde os intervalos começam. 
� É descentralizado => 1- cada nó controla colisões e 
decide independentemente quando retransmitir. 2- não 
existe nó central para controlar transmissões e 
retransmissões. 
 
 
 
� Operação em cada nó: 
� Quando o nó tem um novo quadro para enviar, o 
transmite em sua total integridade ao canal broadcast. 
� Se não houver colisão, o nó espera por um tempo de 
transmissão de quadro. Após essa espera, ele transmite o 
quadro com probabilidade p. 
 8 
� Se houver colisão com uma ou mais transmissões, o nó 
retransmitirá imediatamente com probabilidade p, após 
a transmissão total do quadro colidido. 
� Eficiência com múltiplos nós ativos: 
� Ao final a eficiência cai: 
� Eficiência máxima do protocolo = 1/2e = 0,37 /2 
� grande número de nós tem muitos quadros a transmitir 
=> então apenas 0,37/2 % dos intervalos realiza um 
trabalho útil => taxa efetiva de transmissão do canal será 
(0,37/2)*R bps. 
 
� Slloted ALOHA 
� Características do slloted ALOHA: 
� permite que um único nó ativo (quadro a enviar) 
transmita quadros de maneira contínua à taxa total. 
� É descentralizado => cada nó controla colisões e decide 
independentemente quando retransmitir. 
� Requer que haja sincronismo entre os nós de modo que 
cada nó saiba onde os intervalos começam. 
� Operação em cada nó: 
� Quando o nó tem um novo quadro para enviar, espera até 
o início do próximo intervalo e transmite o quadro inteiro 
no intervalo. 
� Se não houver colisão, o nó transmite seu quadro sem 
considerar a necessidade de retransmissão. 
 9 
� Se houver colisão, o nó a detecta antes do final do 
intervalo. Ele retransmite seu quadro em cada intervalo 
subseqüente com probabilidade p até que o quadro seja 
transmitido sem colisão. 
 
 
Compartimentos: Sucesso (S), Colisão (C), Vazio (E) 
 
� Eficiência com múltiplos nós ativos(transmitindo): 
� Uma certa fração de intervalos terá colisões e, portanto, 
será desperdiçada. 
� Outra porção dos intervalos estará vazia (desperdiçado) 
porque os nós ativos poderão não transmitir conforme a 
política de transmissão adotada. 
� Ao final a eficiência cai: 
� Eficiência máxima do protocolo = 1/e = 0,37� grande número de nós tem muitos quadros a 
transmitir => então apenas 0,37% dos intervalos 
realiza um trabalho útil => taxa efetiva de 
transmissão do canal será 0,37*R bps. 
� Exemplo: 
 10 
� Administrador de rede decide por usar um sistema 
slloted ALOHA de 100 Mbps para um grande 
número de usuários, esperando uma taxa de no 
mínimo 80 Mbps. 
� No final a vazão que se consegue com esse canal é 
de menos de 37 Mbps. 
� CSMA (Acesso múltiplo com detecção de portadora) 
� Os protocolos ALOHA se parecem muito com um convidado 
mal-educado em uma festa que continua a tagarelar mesmo 
quando outras pessoas estão falando. 
� Existem, portanto, duas regras que regem uma conversação 
educada entre seres humanos: 
� Ouça antes de falar – se uma pessoa estiver falando, 
espere até que ela tenha terminado, para falar. No mundo das 
redes, isso é denominado detecção de portadora. 
� Se alguém começar a falar ao mesmo tempo que você, 
pare de falar. No mundo das redes, isso é denominado de 
detecção de colisão. 
� Características: 
� CSMA: escuta antes de transmitir (Carrier Sense-
Detecção de Portadora): 
� Se o canal parece vazio: transmite o pacote 
� Se o canal está ocupado, adia a transmissão 
� Considerações: 
 11 
� Se todos os nós realizam detecção de portadora, 
porque ocorrem colisões? 
� Considere a figura abaixo: 
 
CSMA com colisão de transmissões 
� Vemos que o nó B encontra o canal vazio e transmite, 
mas o tempo de propagação do sinal de B até D tem um 
atraso (delay), que faz com que D ao escutar o canal não 
detecte outro sinal no meio, transmitindo seu sinal e em 
pouco tempo haverá um colisão. Esse atraso é conhecido 
como “atraso de propagação fim-a-fim de canal”. 
� Claramente adicionar detecção de colisão a um 
protocolo de acesso múltiplo ajudará o desempenho do 
protocolo por não transmitir inteiramente um quadro 
inútil, cujo conteúdo esta corrompido. Ao incluir a 
 12 
detecção de colisão no CSMA, passou a ser chamado de 
CSMA/CD (Carrier Sense Multiple Access with 
Collision Detection). 
� CSMA/CD: detecção de portadora, deferência como no 
CSMA 
� Faz o mesmo que o CSMA (ouve o meio) e, também, 
detecta colisão. 
� Detecção de colisão => um nó que está transmitindo 
ouve o canal enquanto transmite. Se ele detectar que 
outro nó está transmitindo um quadro interferente, 
ele parará de transmitir. 
� Transmissões com colisões são interrompidas, 
reduzindo o desperdício do canal. 
� 
CSMA com detecção de colisão 
 13 
2.3 – Protocolos de Revezamento 
� Propriedades desejáveis de um protocolo de acesso 
múltiplo: 
1- quando apenas um nó está ativo, então cada nó ativo tem 
uma vazão de R bps. 
2- quando N nós estão ativos, então cada nó ativo tem uma 
vazão média de R/N bps. 
� Os protocolos ALOHA e CSMA tem a primeira 
propriedade, mas não a segunda. 
� A necessidade de atender a propriedade 2, levou à 
pesquisa de outro protocolo => protocolo de 
revezamento. 
� Tipos de protocolos de revezamento: 
�Protocolo de polling 
�Protocolo de passagem de permissão 
 
� Protocolo de Polling 
� Requer que um dos nós seja designado como mestre. 
� O nó mestre escolhe o nó para transmissão de forma 
lógica e circular. 
� O nó mestre trabalha como a seguir: 
� envia uma mensagem ao nó 1 dizendo que ele pode 
transmitir até algum número máximo de quadros. 
 14 
� Após o nó 1 ter transmitido alguns quadros , o nó 
mestre diz ao nó 2 que ele pode transmitir até um 
número máximo de quadros. 
� O procedimento continua dessa forma com cada um 
dos nós e de maneira cíclica. 
� Vantagens: 
� Elimina as colisões e os intervalos vazios que 
atormentam os protocolos de acesso aleatório. 
� Permite uma eficiência maior por eliminar colisões. 
� Desvantagens: 
� Introduz um atraso de escolha => período de tempo 
requerido para notificar um nó que ele pode 
transmitir. 
� Se o nó mestre falhar, o canal inteiro fica inoperante. 
 
� Protocolo de Passagem de Permissão ou Token 
� Não há nó mestre. 
� Um pequeno quadro de finalidade especial conhecido 
como permissão ou token é passado entre os nós 
obedecendo uma ordem fixa. 
� Quando um nó recebe a permissão, ele a segura somente 
se tiver quadros para transferir. 
� Caso contrário passa a permissão para o nó seguinte. 
� Vantagens: 
� A passagem de permissão é descentralizada. 
 15 
� Permite alta eficiência pois elimina as colisões. 
� Desvantagens: 
� A falha de um nó pode derrubar o canal inteiro. 
� Se ocorre alguma falha na passagem do token por um 
nó, o sistema falhará.