O nível ligação - NetLab

Transcrição

R d d C
Redes de Computadores
d
Nível Ligação
Nível Ligação
E ª Informática
Engª
I f
áti
2º Semestre 2010/11
Prof. José Rogado
jose dot rogado at ulusofona dot pt
Universidade Lusófona
5‐1
Nível Ligação
0 Nível Ligação
Objectivos:
Compreender
Compreender os princípios e serviços do Nível Ligação:
os princípios e serviços do Nível Ligação:
Partilha de um canal em broadcast: acesso múltiplo
Endereçamento no nível ligação
Detecção e correcção de erros
Exemplos e implementações de vários protocolos do nível ligação
í ll
5-2
Nível Ligação
Nível Ligação
Introdução e serviços
Hubs, switches e bridges
Protocolos de acesso Protocolo PPP
múltiplo
Endereçamento no nível li ã
ligação
Protocolo Ethernet
Virtualização de Ligações
ATM
5-3
Nível Ligação
Nível Ligação: Introdução
Terminologia:
Nós: hosts e routers
Ligações: meios físicos que interligam os nós adjacentes ao longo de um trajecto

Ligações por cabos
Ligações sem fios
LANs
O pacote de nível 2 (ligação) designa‐se por frame e encapsula o datagrama
O nível ligação transfere datagramas de um nó para o seguinte através do meio físico que os liga
que os liga
5‐4
Nível Ligação
Nível Ligação: contexto
Os datagramas podem ser transferidos por diferentes protocolos através de diferentes ligações ao longo de uma rota:

Ex: Ethernet na primeira ligação, atm em ligações intermédias e ç
802.11 no último troço
Cada protocolo de ligação fornece serviços de natureza distinta

Pode ou não fornecer controlo de dados fiável a nível da ligação
Analogia com transportes de passageiros
Viagem Lisboa‐Paris: táxi, avião, autocarro
Viagem Lisboa‐Paris: táxi avião autocarro
Cada troço utiliza meios físicos e modos de locomoção distintos
Colaboram com o objectivo de levar passageiros de um ponto a outro
5-5
Nível Ligação
Relação Rede <‐> Ligação
Transporte
Rede
Ligação
Físico
(a) Comunicação Virtual
(b) Comunicação Real
5-6
Nível Ligação
Serviços do Nível Ligação
Framing e Acesso ao meio:

Encapsulamento do datagrama numa frame (trama) adicionando o header (cabeçalho)
Se o meio for partilhado, gerir acesso ao canal, através de um protocolo de Medium Access Control (MAC)
protocolo de Medium Access Control (MAC)
Entrega fiável de dados entre nós adjacentes
Vimos como se implementa fiabilidade no nível transporte
p
p
Pouco utilizado em meios físicos com baixas taxas de erro (fibra, Shielded Twisted Pair)
Relevante em ligações sem fios com taxas de erro elevadas
R l
li õ
fi
d
l d
• Correcção ao nível ligação para evitar retransmissões
5-7
Nível Ligação
Framing no Nível Ligação
Relação entre Pacotes e Frames
5-8
Nível Ligação
Serviços do Nível Ligação (cont.)
Controle de Fluxo:
Sincronização de taxa de emissão em função das capacidades de receptor (frame buffering etc ) para evitar perca de tramas
receptor (frame buffering, etc..) para evitar perca de tramas
Detecção de Erros:
Erros causados pela atenuação do sinal e de ruído no canal
Erros causados pela atenuação do sinal e de ruído no canal
O receptor detecta a presença de erros e pode sinalizar o facto ao emissor para pedir retransmissão
Correcção de Erros:
O receptor identifica e corrige erros sem pedir retransmissão da frame
Full‐duplex e Half‐duplex
Emissão e recepção simultânea (ou não) de tramas
5-9
Nível Ligação
Comunicação entre adaptadores
O nível ligação é geralmente implementado num “adaptador”

Denominado placa de rede
d l
d
d
Ex.: Placas Ethernet, 802.11, …
O adaptador funciona de forma semi‐autónoma
Implementa os níveis ligação e físico
Emissor:

Encapsula o datagrama numa trama
Junta bits de detecção de erros, rdt, controle de fluxo, etc.
Receptor

Detecção de erros, rdt, controle de fluxo, etc
ç
, ,
,
Extrai o datagrama e passa‐o ao nó de recepção
5-10
Nível Ligação
Nível Ligação
múltiplo
Protocolo Ethernet
ATM
5-11
Nível Ligação
Ligações e Protocolos de Acesso Múltiplo
Existem dois tipos de “ligações”:
Ponto‐a‐ponto

Par único emissor receptor
Par único emissor‐receptor
• PPP em acesso comutado
Broadcast

Cabo ou meio partilhado por vários emissores e receptores
• Ethernet tradicional (IEEE 802.3) • LAN WiFi sem fios (IEEE 802.11)
5-12
Nível Ligação
Características do Acesso Múltiplo
Único canal de difusão partilhado Duas ou mais transmissões simultâneas pelos nós: interferências f ê

Existem colisões se o nó recebe dois ou mais sinais ao mesmo tempo
Necessidade de um protocolo de acesso ao meio (MAC)
N
id d d
t l d
i (MAC)
Algoritmo distribuído que determina como os nós partilham o canal i e quando um nó pode transmitir
canal, i.e. quando um nó pode transmitir
Comunicação acerca da partilha do canal deve utilizar o próprio canal

não existe canal “out‐of‐band” para coordenação
5-13
Nível Ligação
Protocolos MAC
MAC: Medium Access Control ‐ três classes genéricas:
Partilha do Canal

Divide‐se a capacidade do canal em fracções (slots de tempo, frequência, código)
Cada fracção é atribuída à comunicação exclusiva entre dois nós d f
ã é ib íd à
i ã
l i
d i ó
Acesso Aleatório
O canal não é dividido, sendo permitidas colisões de acesso
O canal não é dividido sendo permitidas colisões de acesso
É necessário um protocolo para gerir as colisões
Atribuição
Atribuição por Turnos
por Turnos
Os nós emitem por turnos
Os nós com mais dados para enviar podem tomar turnos mais longos.
5-14
Nível Ligação
Protocolos de Partilha de canal: TDMA
TDMA ti
TDMA: time division multiple access
di i i
lti l
Baseado em TDM (Time Division Multiplexing)

Acesso ao canal por “turnos"
Acesso ao canal por turnos Cada nó obtém um slot de comprimento fixo (comprimento = tempo de transmissão de pacotes) em cada turno Slots não utilizados vão vazios Exemplo: LAN com 6 nós: os slots 1,3,4 transmitem, os slots 2, 5 e 6 vão vazios
Protocolo justo pois atribui a mesma taxa a cada nó
Protocolo ineficiente com poucos nós e com carga ligeira.
l i fi i
ó
li i
5-15
Nível Ligação
Protocolos de Partilha de canal: FDMA
FDMA: frequency division multiple access
FDMA: frequency division multiple access
Baseado em FDM (Frequency Division Multiplexing)

Espectro do canal dividido em bandas de frequência
A cada nó é atribuída uma banda fixa de frequência
Bandas de frequência não utilizadas desperdiçadas
Exemplo: LAN com 6 nós: os slots 1,3,4 transmitem, os slots 2, 5 e 6 Exemplo: LAN com 6 nós: os slots 1,3,4 transmitem, os slots 2, 5 e 6
frequen
ncy bandss
vão vazios Mesmos comentários que no TDM relativamente à eficácia.
5-16
Nível Ligação
Protocolos de Acesso Aleatório
Quando um nó tem pacotes para enviar
Transmite dados à velocidade total R do canal.
Não existe coordenação à priori entre os nós
Dois ou mais nós a transmitir @ colisões
Um protocolo MAC de acesso aleatório especifica: Como detectar colisões
Como recuperar de colisões (i.e., através de retransmissões retardadas)
Exemplos
Exemplos de protocolos MAC de acesso aleatório:
de protocolos MAC de acesso aleatório:
slotted ALOHA
ALOHA
CSMA, CSMA/CD, CSMA/CA
5-17
Nível Ligação
Protocolo Slotted ALOHA
Pressupostos
Modo de Operação
Todas as frames têm o mesmo Quando um nó quer enviar uma

nova frame, transmite‐a no próximo tamanho
slot
O tempo é dividido em slots de Se não existir colisão, o nó pode igual comprimento,
igual comprimento, enviar nova frame no slot seguinte
correspondendo ao tempo de transmissão de 1 frame
Se existir colisão, o nó tenta retransmitir a frame em cada slot
retransmitir a frame em cada slot O ó i i i
Os nós iniciam a transmissão das t
i ã d
seguinte depois de um intervalo frames apenas no início dos slots
aleatório de tempo de paragem, até Os nós estão sincronizados
obter sucesso
Se 2 ou mais nós transmitem no Sendo diferente o intervalo para mesmo slot, todos os nós cada nó, existe uma probabilidade ,
p
detectam a colisão
detectam a colisão
baixa de haver colisão na frame seguinte
5-18
Nível Ligação
Slotted ALOHA
Prós
Um único nó activo pode transmitir continuamente a toda a velocidade
continuamente a toda a velocidade do canal
Descentralizado: os nós funcionam de forma independente Simples
Contras
Colisões: desperdício de slots
Slots vazios
Sl t
i
Os nós têm de detectar uma colisão num tempo inferior ao da transmissão de um pacote
Relógios síncronos para sincronização dos slots
sincronização dos slots
5-19
Nível Ligação
Protocolos CSMA
CSMA (Carrier Sense Multiple Access)
Modo de Operação:
Escutar antes de transmitir
Se o canal escutado está livre: transmitir toda a frame
Se o canal escutado estiver ocupado, retardar a transmissão um intervalo de tempo aleatório
Analogia Humana: Não interromper os outros!
5-20
Nível Ligação
Colisões no CSMA
spatial layout of nodes
Ainda podem existir colisões
O facto de existir atraso na
propagação do sinal implica que dois
nós podem não detectar as
transmissões um do outro a tempo
e começar a emitir, provocando
colisão
N t
Nota:
A probabilidade de colisão
depende
p
da distância entre nós e
do tempo de propagação
Em caso de colisão:
O tempo de transmissão de todo
o pacote é desperdiçado, pois os
nós não detectam a colisão
5-21
Nível Ligação
CSMA/CD (Collision Detection)
CSMA/CD: escuta a portadora, detecta colisões e volta a emitir passado um intervalo de tempo aleatório
passado um intervalo de tempo aleatório

As colisões podem ser detectadas num curto intervalo de tempo
As transmissões que colidem são imediatamente abortadas, reduzindo o desperdício da capacidade do canal Detecção de colisões:
Fácil em LANs
Fá il
LAN cabladas: mede‐se a intensidade do sinal, compara‐se bl d
d
i t id d d i l
o sinal transmitido com o recebido
Impossível em LANs
p
sem fios: o receptor fica inactivo enquanto o p
q
emissor transmite
Analogia humana : o interlocutor educado
5-22
Nível Ligação
CSMA/CD: Diagrama Temporal
5-23
Nível Ligação
Protocolos de Acesso por Turnos
Protocolos MAC de multiplexagem de canal :
Partilham o canal de forma eficiente e justa em situação de carga elevada
Ineficaz em baixa carga: atraso no acesso ao canal, só 1/N da largura de banda é utilizada mesmo se apenas um nó está activo! P t l MAC d
Protocolos MAC de acesso aleatório :
l tó i
Eficientes para cargas baixas: um único nó pode utilizar a largura de banda total do canal
a largura de banda total do canal
Carga elevada : excesso de colisões
Protocolos de Acesso por T rnos
Protocolos de Acesso por Turnos
Juntam as vantagens dos dois tipos anteriores
5-24
Nível Ligação
Tipos de Protocolos de Acesso por Turnos
Polling (amostragem):
Passagem de Token (testemunho):
Um nó (master) autoriza Um token de acesso é passado
os outros nós (slaves) a ó (l
)
sequencialmente
i l
d
de um nó
ó ao
transmitir no seu turno
seguinte.
Inconvenientes:
Inconvenientes
O token
t k n é uma
m frame
f m especial
sp i l
Overhead associado ao Inconvenientes :

p
polling g
Ponto único de falha (nó master)

Overhead associado ao token

Ponto único de falha (token)
Exemplos
Token Ring
g
FDDI
Exemplos
802.16
802 16 (WCOPP)
Wireless Connection Oriented
Polling Protocol
5-25
Nível Ligação
Resumo dos protocolos MAC
Como utilizar um meio partilhado?
Partilha do canal, no tempo, em frequência ou por código
,
p ,
q
p
g

Divisão de Tempo, Divisão de Frequência, Codificação
Partilha aleatória (dinâmica), ALOHA, S‐ALOHA, CSMA, CSMA/CD
Carrier Sensing: fácil em algumas tecnologias (cabos), difícil noutras (sem fios)
t (
fi )
CSMA/CD utilizado na Ethernet
CSMA/CA utilizado em 802.11
CS /C ut ado e 80
Acesso por Turnos
Polling a partir de um nó central
Passagem de token
5-26
Nível Ligação
MAC– Métodos de Acesso
5-27
Nível Ligação
IEEE 802.2: Logical Link Control
O Acesso do nível Rede ao nível MAC é feito por uma
camada intermédia que esconde as particularidades dos
diferentes protocolos de acesso

LLC - Logical Link Control
(b) Encapsulamento
(a) Posicionamento do LLC
5-28
Nível Ligação
Modelo para Redes Locais, Standard ISO IEC 8802
5-29
Nível Ligação
Standards IEEE 802
Os grupos de trabalho IEE 802: Os mais importantes estão assinalados com *. Os assinalados com È
Os assinalados com È estão em hibernação. estão em hibernação
Os assinalados com † estão extintos.
5-30
Nível Ligação
Nível Ligação
múltiplo
Protocolo Ethernet
ATM
5-31
Nível Ligação
Endereçamento no Nível Ligação
Endereço IP: 32‐bits

Endereçamento de nível rede
Endereçamento de nível rede

Necessário para encaminhar um datagrama à rede IP de destino Endereço MAC
E d
MAC (LAN, físico ou Ethernet):
(LAN fí i
Eth
t)

Endereçamento de nível ligação

Necessário para encaminhar a frame de uma interface para outra N
ái
i h
f
d
i t f
t
interface que lhe está ligada fisicamente na mesma rede

O endereço MAC tem 48 bits (na maioria das LANs) O
endereço MAC tem 48 bits (na maioria das LANs)
e está armazenado na ROM do adaptador

Notação hexadeximal: 6bytes com separador (– ou :)
• Ex: 58:23:D7:FA:20:B0
5-32
Nível Ligação
Características dos Endereços MAC
A atribuição de endereços MAC é administrada pela IEEE
Um fabricante compra uma parte do endereço MAC para assegurar a unicidade do mesmo
i id d d
Analogia:
(a) endereço MAC: N º Segurança Social
(a) endereço MAC: N.º Segurança Social
(b) endereço IP: endereço postal
O espaço de endereçamento MAC é linear O espaço de endereçamento MAC é linear @ garantia de garantia de
portabilidade
Pode‐se mover uma placa LAN de uma LAN para outra mantendo o mesmo endereço MAC
Os endereços IP hierárquicos NÃO são portáveis

Dependem da sub rede IP a que estão ligadas
Dependem da sub rede IP a que estão ligadas
Noção de localidade
5-33
Nível Ligação
Endereços MAC
Cada adaptador numa LAN tem um único endereço MAC
1A-2F-BB-76-09-AD
71-65-F7-2B-08-53
Endereço de Broadcast =
FF-FF-FF-FF-FF-FF
LAN
(wired or
wireless)
= adaptador
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
5-34
Nível Ligação
ARP: Address Resolution Protocol
Como determinar o endereço MAC
de um
m nó conhecendo o seu
endereço IP?
Todos os nós IP (Hosts, Routers) numa LAN têm uma tabela ARP
numa LAN têm uma tabela ARP
A tabela contém mapeamentos IP/MAC para alguns nós da rede
/
p
g
237 196 7 78
237.196.7.78
1A-2F-BB-76-09-AD
237.196.7.23
237 196 7 14
237.196.7.14
LAN
71-65-F7-2B-08-53
237.196.7.88
< IP address; MAC address; TTL>

TTL (Time To Live): tempo depois do qual o mapeamento de endereço será descartado (tipicamente 20 min)
(tipicamente
0 min)
58-23-D7-FA-20-B0
0C C4 11 6F E3 98
0C-C4-11-6F-E3-98
5-35
Nível Ligação
Funcionamento do ARP (na mesma LAN)
“A” quer enviar um datagrama a “A” guarda na sua tabela ARP a “B”, cujo endereço não está na sua correspondência IP‐MAC até esta tabela ARP
perder validade (time‐out)
perder validade (time
out)
“A” faz um pedido ARP em “soft state”: a informação que broadcast indicando que pretende o perde validade desaparece a menos end. de “B”
que seja reactualizada
j
li d
Quem tem o end. de “B”?
O ARP é “plug‐and‐play”:
Endereço MAC de destino = FF‐
FF‐FF‐FF‐FF‐FF
FF
FF FF FF FF
Os nós criam as suas tabelas ARP Os nós criam as suas tabelas ARP
sem a intervenção do Todos os máquinas nessa LAN recebem o pedido ARP administrador de rede
“B”
B recebe o pacote ARP, e recebe o pacote ARP e
responde a “A” indicando o seu endereço MAC

A frame enviada de B para A é A
frame enviada de B para A é
enviada apenas para o endereço MAC de A (unicast)
5-36
Nível Ligação
ARP com routing (LAN)
Enviar um datagrama de A para B através de R,
assumindo q
que A conhece o endereço IP de B
A
R
B
O router R gere duas tabelas ARP, uma para cada sub rede
5-37
Nível Ligação
Funcionamento
“A”
A gera um datagrama
gera um datagrama com origem com origem “A”
A e destino e destino “B”
B
“A" utiliza ARP para obter o endereço MAC de R na rede 111.111.111.0/24
“A” gera uma frame de nível ligação com esse endereço MAC de R no destino,

contendo um datagrama
contendo
um datagrama enviado
“A” envia a frame a R
R retira o datagrama da frame e verifica que se destina a B (routing)
R usa ARP para obter o endereço MAC de B na rede 222.222.222.0/24
R gera uma nova frame contendo o datagrama original e o endereço MAC de B no campo destino
p
R envia a frame a “B”
A
R
B
5-38
Nível Ligação
Nível Ligação
múltiplo
Protocolo Ethernet
Ligações virtuais: ATM e MPLS
5-39
Nível Ligação
Ethernet (IEEE 802.3)
Desenvolvida por B. Metcalfe
Desenvolvida
por B Metcalfe e D. Boggs
e D Boggs em 1970
em 1970
Tecnologia de LAN cablada mais utilizada !
Razões:
Barata (placa de rede de 100Mbs < €20)
Primeira tecnologia de LAN utilizada em larga escala
Mais simples e barata do que LANs
p
q
com tokens e ATM
Tem evoluído em performance: 10Mbs – 10 Gbps
Desenho inicial de Bob
Metcalfe representando a
configuração
g
ç da Ethernet
L resumo em: http://en.wikipedia.org/wiki/Ethernet
Ler
h
//
k d
/ k /E h
5-40
Nível Ligação
Toplogias de Redes Ethernet 802.3 ‐ I
Configuração inicial (1970-80):
(1970 80): 10Base5
Rede em Bus
Cabos coaxiais grossos (thick)
Transmissão em banda de Base
Até 500 metros por segmento
10 Mbit/s
5-41
Nível Ligação
Toplogias de Redes Ethernet 802.3 – II
Configuração posterior (1980-90): 10Base2
Rede em Bus
Cabos coaxiais finos (thin)
Até 200 metros
t
por segmento
t
10 Mbit/s
5-42
Nível Ligação
Toplogias de Redes Ethernet 802.3 – III
Configuração recente (>90): 10BaseT
T: Twisted Pair
Rede em estrela
Par
P telefónico
t l fó i entrançado
t
d (UTP) / (STP)
Até 100 metros por segmento a 100 Mbit/s
5-43
Nível Ligação
Topologia em Estrela
A topologia em Bus mantém‐se até meados dos anos 90
Actualmente a topologia utilizada é em estrela
A ligação é feita através de hub, switch ou router ‐ dependendo do particionamento da rede (ver + à frente)
Taxa de 10/100 Mbps / 1Gbps Taxa de 10/100 Mbps / 1Gbps ‐>> “fast
fast ethernet
ethernet”
twisted pair
switch
5-44
Nível Ligação
GigaBit Ethernet
Standard IEEE 802.3‐2008 usado a partir de 1999
Utiliza o formato de trama standard Ethernet
Utiliza o formato de trama standard Ethernet
Permite ligações ponto‐a‐ponto e canais de broadcast

partilhados
Em modo partilhado, utiliza CSMA/CD
Distâncias entre nós (~100m)
Distâncias entre nós (
100m) devem ser respeitadas para devem ser respeitadas para
garantir taxas elevadas
Full‐Duplex
Full
Duplex a 1
a 1‐10
10 Gbps
Gbps em ligações ponto
em ligações ponto‐a‐ponto
a ponto em em
cabos 5+ UTP
Pode usar cabo cobre (1000BASE‐T) ou fibra (1000BASE‐ZX) até 70Km
5-45
Nível Ligação
Estrutura da Trama Ethernet (i)
O adaptador que emite encapsula o datagrama do protocolo de rede numa trama Ethernet
de rede numa trama
Preambulo:
7 bytes com o padrão 10101010 seguido de 1 byte de Start Frame Delimiter (SFD) com o padrão 10101011
Utilizada para sincronizar a frequência dos relógios do emissor e receptor
Dados: 46 a 1500 bytes
Dados: 46 a 1500 bytes
No máximo uma trama tem 1526 bytes com os headers
5-46
Nível Ligação
Estrutura da Trama Ethernet (ii)
Endereços: 2 x 6 bytes
Se o adaptador recebe uma trama com o seu endereço ou com endereço de broadcast, passa os dados da trama para o protocolo do nível rede sobrejacente
do nível rede sobrejacente
Senão o adaptador descarta a trama
Tipo:
p 2 bytes
y
Indica o protocolo de rede responsável pelo envio (IP, Novell IPX, AppleTalk…)
CRC: 4 bytes
Verificado pelo receptor, em caso de detecção de erro a trama é simplesmente descartada
simplesmente descartada
5-47
Nível Ligação
Serviço não Fiável e sem Conecção
Sem conecção: Não existe handshaking entre o o emissor e receptor. p
Não fiável: o receptor não envia ACKs ao emissor para validar (ou invalidar) as tramas recebidas

O fluxo de datagramas passado aos protocolos de nível superior pode não conter todos os dados emitidos
A
A responsabilidade de completar os dados em falta compete ao bilid d d
l t
d d
f lt
t
protocolo de nível superior, por exemplo o TCP
• Senão as aplicações irão dar conta das falhas
5-48
Nível Ligação
Algoritmo CSMA/CD Ethernet
1. O adaptador recebe o datagrama do 5. Depois da interrupção o adaptador entra no estado de “retirada nível rede e constrói uma trama.
exponencial” (exponential backoff): exponencial
(exponential backoff):
2 S
2. Se o adaptador detecta que o canal d
d d
l
numa colisão de ordem n mod(10), o está livre, começa a transmitir a adaptador escolhe um valor K trama. Senão espera que fique livre.
aleatoriamente no conjunto
aleatoriamente no conjunto 3. Se o adaptador transmite a trama {0,1,2,…,2n‐1}, espera um tempo toda sem detectar uma colisão, a correspondente à transmissão de emissão termina.
emissão termina. Kx512 bits e volta ao passo 2.
4. Se o adaptador detecta uma colisão, interrompe a emissão e envia sinal d
de engarrafamento (jam signal).
f
t (j
i l)
5-49
Nível Ligação
CSMA/CD Ethernet
Jam Signal: 48 bits ‐ garante que todos os outros emissores se dão
todos os outros emissores se dão conta de que houve uma colisão
Tempo transmissão de 1 Bit:
p
0.1 microsec para Ethernet 10 Mbps; se K=1023, o tempo de espera máximo é de aproximadamente 50 msec
50 msec
Exponential Backoff:
Objectivo: adaptar as tentativas de j
p
retransmissão à carga da rede estimada do momento

Carga elevada: a espera aleatória é mais longa
mais longa
Primeira colisão: K é escolhido entre {0,1}; a espera é K· 512 tempo de transmissão de 1 bit
Depois da segunda colisão: K D
i d
d
li ã K
escolhido de {0,1,2,3}…
Depois da 10 colisões: K escolhido de {0,1,2,3, …, 1023}
{ , , , , ,
}
Ver a applet Java no site Web :
http://media.pearsoncmg.com/aw/aw_kurose_network_2/applets/csmacd/csmacd.html
5-50
Nível Ligação
Nível Ligação
múltiplo
Protocolo Ethernet
ATM
5-51
Nível Ligação
Interligação de Redes Locais
Em todas as instituições há a necessidade de adaptar a LAN aos aspectos organizacionais
p
p
g
Geralmente uma LAN é constituída por vários segmentos interligados entre si através de g
g
dispositivos permitem diversos graus de isolamento
Dispositivos mais utilizados:
Hubs
Switches
Routers
Bridges
Gateways
5-52
Nível Ligação
Hub
Dispositivo que actua no Nível 1 (físico)
Interligação de segmentos através de um Hub Central
Interligação de segmentos através de um Hub Central

Os Hubs permitem aumentar a máxima distância entre nós
Mas um Hub não isola os segmentos a nível das colisões

Todos os segmentos recebem todas as frames ‐> aumenta a probabilidade de colisão
Os Hubs não podem interligar 10BaseT & 100BaseT
p
g
5‐53
Nível Ligação
Switch
Dispositivo que actua no Nível 2 (ligação)

Armazena e encaminha frames Ethernet
Encaminha as frames selectivamente com base no endereço MAC de destino, Encaminha as frames selectivamente
com base no endereço MAC de destino
diminuindo o nível de colisão em cada segmento
Quando encaminha uma frame para um segmento, utiliza o protocolo CSMA/CD g
garantir o acesso
Dispositivo transparente

Os hosts não se apercebem da presença dos switches
Dispositivo plug‐and‐play, self‐learning
Dispositivo plug‐and‐play self‐learning

Os switches não precisam de ser configurados
5-54
Nível Ligação
Filtragem e Encaminhamento
1
3
2
Filtragem (Filtering)
Filtragem (Filtering)

Determinar se uma frame deve ou não ser encaminhada para um dado segmento
Encaminhamento (Forwarding)
Encaminhamento (Forwarding)

Determinar para que segmento da LAN se deve encaminhar uma frame
Semelhante ao problema de encaminhamento de datagramas
Semelhante ao problema de encaminhamento de datagramas que existe no nível 3 (rede)
5‐55
Nível Ligação
Auto Aprendizagem
Cada switch mantém uma switch table
Elemento da switch table: (Endereço MAC, Interface, Time Stamp)
O switch
O it h memoriza
i os endereços dos dispositivos que estão d
d di
iti
tã
ligados a cada uma das suas interfaces

Quando uma frame é recebida através de uma interface, o switch
Quando
uma frame é recebida através de uma interface o switch
memoriza o endereço de origem de cada frame
Regista o elemento (Endereço MAC, Interface, Instante de Chegada) na tabela de switching
Os elementos são eliminados da tabela quando não são recebidas frames dentro de um dado período (TTL até 60 min) p
(
)
5-56
Nível Ligação
Algoritmo de Aprendizagem
Quando um switch recebe uma trama:
EExtrai o endereço MAC de origem
t i
d
MAC d
i
d t
da trama
Procura esse endereço na tabela de switching
se encontrar um elemento com esse endereço
se encontrar um elemento com esse endereço
então no‐op
senão
cria um novo elemento com esse endereço, nº de interface por onde o recebeu, e o instante de chegada
5-57
Nível Ligação
Filtering/Forwarding
Quando um switch recebe uma trama:
EExtrai o endereço MAC de destino
t i
d
MAC d d ti da trama
d t
Procura esse endereço na tabela de switching
se encontrar uma linha com esse endereço
se encontrar uma linha com esse endereço
então
se o interface é o mesmo por onde a trama chegou
p
g
então descarta a trama
senão encaminha a trama para o interface associado
senão
Encaminha a trama para todos
propaga a trama
os interfaces excepto para
aquele de onde chegou
5-58
Nível Ligação
Exemplo de Switching
C envia uma trama a D
Switch Table
address
switch
h
1
3
2
hub
hub
hub
A
I
B
C
F
D
G
E
A
B
E
G
C
interface
1
1
2
3
1
H
O Switch recebe a trama de C
Memoriza na tabela que C está na interface 1
Como D não está na tabela, encaminha a trama nas interfaces 2 e 3
A trama é recebida por D A trama é recebida por D
5‐59
Nível Ligação
Exemplo de Switching
Supondo que D responde com uma trama para C:
Switch Table
switch
1
3
2
hub
hub
hub
A
address
I
B
C
F
D
E
G
H
interface
A
B
E
G
C
D
1
1
2
3
1
2
O switch recebe a trama de D
Memoriza na tabela que D está na interface 2
como C está na tabela, o switch encaminha a trama só para a C tá t b l
it h
i h t
ó
interface 1
A trama é recebida por C
A trama é recebida por C
5‐60
Nível Ligação
Switch: isolamento de tráfego
A instalação de um switch divide a LAN em segmentos
O switch filtra as tramas:
As tramas de um mesmo segmento não são encaminhadas para os outros
Os segmentos são domínios de colisão separados
switch
hub
Collision domain
hub
Collision domain
5-61
hub
C lli i domain
Collision
d
i
Nível Ligação
Rede Institucional Simples
Subnet IP
router
switch
switch
switch
switch
5‐62
Nível Ligação
Rede Institucional com Protecção
DMZ: Demilitarized Zone
5‐63
Nível Ligação
Rede do Laboratório
Equivalente a um
Router de 6 portas !
5-64
Nível Ligação
Switches e Routers
São ambos dispositivos “store‐and‐forward”

Routers: dispositivos do nível rede (examinam “headers” datagrama)

Switches: dispositivos do nível ligação (examinam “headers” trama)
Os routers mantém tabelas de routing e implementam algoritmos de routing.
routing
Os switches mantém tabelas de switching, implementam filtros e algoritmos de aprendizagem
de aprendizagem.
5-65
Nível Ligação
Sumário comparativo
hubs
switches
routers
Traffic isolation
no
yes
yes
g p y
Plug & play
yyes
yyes
no
Optimal routing
no
no
yes
C t th
Cut through
h
yes
yes
no
Estes 3 tipos de dispositivos só permitem interligar redes com Estes
3 tipos de dispositivos só permitem interligar redes com
características idênticas no nível 2 ‐ ligação de dados
5‐66
Nível Ligação
Interligação de Redes Diferentes
Bridge
5-67
Nível Ligação
Pontes (Bridges) e Switches
Bridge (Ponte)

Equipamento que liga várias redes diferentes no nível físico e/ou ligação, mas com o mesmo protocolo no nível de rede e/ou transporte, permitindo a criação uma rede homogénea.
Normalmente cada bridge tem uma tabela dinâmica que contém todos os endereços da rede que se situa de cada um dos lados da rede, só permitindo a passagem dos endereços que estão de cada um dos lados.
É possível através de filtros impedir a passagem de certos tipos de pacotes.
Actua no nível ligação (nível dois)
Switch

Equipamento que liga vários segmentos da uma rede com as mesmas q p
q
g
g
características no nível da ligação (nível 2).
Apenas permite a passagem das frames para o segmento onde se situa o endereço destino. Actua também no nível ligação.
Ver mais detalhes em:
http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/bridging.htm
5-68
Nível Ligação
Bridges
Operação de uma bridge entre LAN’s 802.11 e 802.3.
5-69
Nível Ligação
Bridges Locais e Remotas
(a) Bridges locais utilizadas para interligar várias LANs.
(a)
( ) Bridges remotas utilizadas para interligar LANs distantes.
B id
t
tili d
i t li
LAN di t t
5‐70
Nível Ligação
Bridges Redundantes
Quando existem várias bridges entre duas LANs pode haver duplicação de frames se não houver conhecimento e optimização da topologia de rede de forma a evitar ciclos
da topologia de rede de forma a evitar ciclos
‐> Spanning Tree Protocol
5‐71
Nível Ligação
O Protocolo Spanning Tree
O Spanning Tree Protocol (STP) é utilizado para permitir que várias bridges possam trabalhar em conjunto evitando ciclos de propagação
evitando ciclos de propagação
Cada bridge comunica com as outras para descobrir como estão interligadas
estão interligadas
Esta informação é depois utilizada para eliminar ciclos e permitir o encaminhamento óptimo das frames
O STP também providencia tolerância a falhas pois permite reconfigurar a topologia da rede no caso de falha de dispositivos
de dispositivos
5-72
Nível Ligação
Spanning Trees
Sub‐conjunto de uma rede que contém todos os nós mas só as ligações Sub conjunto de uma rede que contém todos os nós mas só as ligações
necessárias para assegurar a conectividade mínima

Evita ciclos na rede em situações de broadcast
Uma spanning tree é construída entre os nós que constituem uma rede Uma spanning tree é construída entre os nós que constituem uma rede
seguindo um algoritmo específico (Ex: ISO 802‐1B)
Define‐se um nó raíz (neste exemplo: A)
Cada nó envia uma mensagem de junção ao nó raíz
Cada nó envia uma mensagem de junção ao nó raíz

A mensagem é encaminhada até chegar à raiz ou a um nó que já faz parte da spanning tree
A
1
B
C
4
3
F
A
2
E
B
C
D
F
5
G
E
D
G
(b) Spannig tree resultante
(a) Construção da spanning tree
5-73
Nível Ligação
Bridges em Spanning Tree
(a) LANs interligadas. (b)
(a)
LANs interligadas (b) Uma spanning tree cobrindo as LANs. Uma spanning tree cobrindo as LANs
A representação (b) permite revelar melhor a spanning tree
As linhas tracejadas não pertencem à spanning tree
5-74
Nível Ligação
Hubs, Bridges, Switches
(a) Hub (b) Bridge (c) Switch
5-75
Nível Ligação
Gateways

Gateway ‐ Equipamento que liga várias redes de diferentes tipos convertendo os pacotes de um protocolo para outro e vice‐
versa.
versa
Actua nos 2 níveis superiores da pilha protocolar.
5-76
Nível Ligação
Nível Ligação
múltiplo
Protocolo Ethernet
Detecção e correcção de erros (mais tarde..)
ATM
5-77
Nível Ligação
Ligação de Dados Ponto a Ponto
Um emissor e um receptor: mais simples que numa ligação em broadcast

Não há necessidade de controle de acesso ao meio

Não é necessário endereçamento
• Exemplos: Dialup, RDIS, ADSL
Protocolos ponto a ponto mais utilizados

HDLC: High‐level Data Link Control (ISO Level 2 13239)
• http://en.wikipedia.org/wiki/High‐Level_Data_Link_Control

PPP: Point to Point
PPP: Point
to Point Protocol (IETF RFC 1661)
(IETF RFC 1661)
• http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/ppp.htm
5-78
Nível Ligação
Requisitos PPP [RFC 1557]
Formatação de pacotes: encapsulamento de datagramas do nível rede em frames do nível lógico
Capacidade de transportar dados do nível rede de qualquer protocolo do nível Capacidade
de transportar dados do nível rede de qualquer protocolo do nível
rede (não só IP) ao mesmo tempo
• Camada Network Control Protocols (NCP)

Capacidade estabelacer ligações multiplexadas pelas camadas superiores
p
g ç
p
p
p
• Camada Link Control Protocol (LCP) Transparência de transmissão: deve poder transmitir qualquer padrão de

p
bits no campo de dados
Detecção de erros: deve permitir detectar os erros de transmissão (não realiza correcção)
Ligação activa: detecção e sinalização de falha do sinal da ligação
Ligação activa:
detecção e sinalização de falha do sinal da ligação
Negociação do endereço do nível rede: os pontos terminais podem detectar e/ou configurar os respectivos endereços de nível rede
R
Recuperação de erros, controle de fluxo, re‐orderdenação de dados são ã d
l d fl
d d
ã d d d
ã
deixados para os níveis mais elevados
5-79
Nível Ligação
Formato da Frame PPP Formato semelhante ao do HDLC:
Flag: delimitador da frame ‐ 1 byte
Address: endereço de broadcast ‐
ç
1 bytes
y
Control: não utilizado; no futuro possibilidade de múltiplos campos de controle ‐ 1 byte
Protocolo: protocolo de nível superior ao qual a frame deve ser p
p
q
entregue (PPP‐LCP, IP, IPCP, etc) ‐ 1 ou 2 bytes.
Dados: dados transportados na frame até 1500 bytes
FCS: (Frame Checksum Sequence) teste de paridade cíclica para (
q
)
p
p
detecção de erros ‐ 2 ou 4 bytes
Closing Flag Sequence: sequência de bits que indica o fim da frame ‐ 1 byte
5-80
Nível Ligação
PPP Link Control Protocol (LCP)
Antes de poder trocar dados, os intervenientes na ligação de dados devem:
Configurar o link PPP (tamanho max. da frame, autenticação, etc..)
Detectar e configurar
f
parâmetros do nível rede

No caso de ser IP são trocadas d
ã
d
mensagens de IP Control Protocol (IPCP) msgs (protocol field: 8021) para detectar e configurar o endereços IP
5-81
Estados do Link Control Protocol
Nível Ligação
PPP Link Control Protocol (LCP)
Início
A simplified phase diagram to bring a line up and down.
5-82
Nível Ligação
Utilizações do PPP
O PPP é utilizado em cima de outros protocolos no serviço de acesso ADSL 5‐83
Nível Ligação
Transparência na Transmissão de Dados
A existência de padrões de limitação de frame levanta o problema da “transparência”
A transparência na transmissão de dados, consiste na possibilidade p
,
p
de transmissão de qualquer sequência de “0” e “1”, mesmo se idênticas ao do flag de delimitação:
sequência sequência <01111110>:
01111110 : dados ou o flag?
dados ou o flag?
Para distinguir, sempre que no interior dos dados aparece a sequência <01111110>, é inserida uma sequência identica adicional, que é depois retirada na recepção
que é depois retirada na recepção
Esta funcionalidade é designada por “byte stuffing”

Emissor: adiciona (“stuffs”) um byte extra < 01111110> depois de cada byte de dados com a configuração < 01111110>
byte de dados com a configuração < 01111110>
Receptor:
• dois <01111110> bytes de seguida: descarta o primeiro byte, e continua a recepção de dados
continua a recepção de dados
• único 01111110: detecção do byte de flag
5-84
Nível Ligação
Byte Stuffing
flag byte
g y
pattern
in data
to send
flag byte pattern plus
stuffed byte in transmitted
stuffed byte in transmitted data
5‐85
Nível Ligação
Bit Stuffing
Bit Stuffing (HDLC) ‐ o flag 01111110 é utilizada no início e no fim de cada bloco a transmitir.
Para que no interior de um bloco não seja detectada nenhuma flag é utilizado o mecanismo de bit‐stuffing, que consiste em inserir um 0 depois de cada cinco 1, que depois é it
i
i
0d
i d
d i
1
d
i é
retirado na recepção, ou seja ...
... para enviar ...11010111110111111101... ... é enviado
01111110...1101011111001111101101...01111110
FLAG Bit Stuffing
FLAG
5-86
Nível Ligação
Nível Ligação
múltiplo
Protocolo Ethernet
ATM
5-87
Nível Ligação
Virtualização do Nível Ligação
Nem sempre o nível ligação está directamente implementado em cima de um meio físico, como no caso do 802.3 (Ethernet) ou 802.11 (Wireless)
A ligação pode na realidade ser implementada por uma camada de protocolos que A ligação pode na realidade ser implementada por uma camada de protocolos que
abstrai o meio e pode ter uma arquitectura complexa
Essa camada apresenta um conjunto de serviços ao nível rede que simula ou virtualiza o nível ligação
Exemplo das redes públicas de dados

IP sobre X 25 Frame Relay ou ATM
IP sobre X.25, Frame Relay
ou ATM
5-88
Nível Ligação
ATM: Asynchronous Transfer Mode
O ATM é um standard dos anos 90 para alto débito (155 Mbps a 622 Mbps ou
Mbps
ou mais) desenvolvido pelo
mais) desenvolvido pelo ITU‐T no âmbito
ITU‐T no âmbito da arquitectura
da arquitectura B‐ISDN B‐ISDN
(Broadband Integrated Service Digital Network)
Objectivo: arquitectura integrada para transportar voz, vídeo e dados topo a topo.
Satisfazendo requisitos temporais e de QoS para voz e vídeo, em contraste com o modelo de “melhor
contraste com o modelo de melhor esforço
esforço” da Internet
da Internet
Considerado a nova geração para a telefonia, tem as suas origens no mundo das comunicações telefónicas
Tecnologia de comutação de pacotes de tamanho fixo (chamados células) utilizando circuitos virtuais
5-89
Nível Ligação
Arquitectura ATM
Constituído por 3 camadas ou níveis
Constituído
por 3 camadas ou níveis
AAL ‐ ATM Adaptation Layer: presente no sistema terminal que acede à rede ATM
Funcionalidades de segmentação e agregação de dados
Aproximadamente equivalente ao nível transporte da Internet
ATM layer:
y nível “rede”
Funcionalidades de comutação e encaminhamento de células
Nível Físico
5-90
Nível Ligação
O Modelo de Referência ATM
5-91
Nível Ligação
Correspondência ATM/OSI
Transmission Convergence
Physical Medium
Medium-Dependent
Dependent
Os níveis ATM e suas funcionalidades
5-92
Nível Ligação
ATM Adaptation Layer (AAL)
O ATM Adaptation Layer (AAL): “adapta” os níveis superiores (IP ou aplicações nativas níveis
superiores (IP ou aplicações nativas
ATM) ao nível inferior ATM
O nível AAL só está presente nos sistemas finais e não nos switches
e não nos switches
O segmento de nível AAL (campos header/trailer e dados) é fragmentado em múltiplas células ATM com 53 bytes de
múltiplas células ATM com 53 bytes de comprimento analogia: segmento TCP enviado em vários pacotes IP
ái
t IP
5-93
Nível Ligação
Tipos de AALs
Existem vários tipos de níveis AAL dependendo da classe de serviço ATM:
Existem vários tipos de níveis AAL dependendo da classe de serviço ATM:

AAL1: para serviços CBR (Constant Bit Rate), ex circuitos virtuais
AAL2: para serviços VBR (Variable Bit Rate), ex: MPEG video
AAL5: para serviços de dados ex: datagramas IP
Os dados utilizador são encapsulados dentro de um Protocol Data Unit que é fragmentado em várias células ATM
g

O formato dos headers e trailers depende do tipo de serviço
Application Data
Convergence Sublayer
AAL PDU
(Protocol Data Unit)
CS-PDU
Header
Convergence Sublayer
Protocol Data Unit
ATM
SAR
Header Header
SAR
Trailer
CS-PDU
Trailer
Segmentation and
Reassembly Sublayer
ATM
SAR
Header Header
SAR
Trailer
ATM Cell
C ll 2 (53 b
bytes)
t )
ATM Cell 1 (53 bytes)
5-94
Nível Ligação
Camada ATM : Circuitos Virtuais
Serviço: transporta celulas através da rede ATM

Análogo ao nível rede IP, mas fornece serviços muito diferentes
Transporte CV:
T
t CV as celulas
l l são transportadas da origem ao destino num ã t
t d d
i
d ti
Circuito Virtual

Estabelecimento de circuito antes de transferência de dados
Cada célula tem um identificador de circuito e não endereço destino
Todos switches ao longo da rota mantêm estado para cada circuito que os inclui
Recursos de switch e ligação (memória e largura de banda) são alocados ao circuito para garantir características de tipo circuito comutado
Circuitos Virtuais Permanentes (PVCs)
Circuitos Virtuais Permanentes (PVCs)
Conexões persistentes
Circuitos Virtuais Comutados (SVC):
(
)
Estabelecidos dinamicamente em cada ligação

5-95
Nível Ligação
Camada ATM: Célula ATM
Célula de 53 bytes de comprimento
Payload pequeno ‐> tempo de criação de célula curto para transporte de voz
célula curto para transporte de voz digitalizada
Diminuição do jitter (variância do atraso entre pacotes)
5 bytes
VPI/VCI: virtual channel ID
muda em cada ligação através da rede
PT: Payload type
Payload type

Tipo de payload transportado CLP: Cell Loss Priority bit
CLP = 1 implica uma célula de baixa CLP
1 implica uma célula de baixa
prioridade que pode ser descartada em caso de congestão.
HEC: Header Error Checksum
Teste de redundância cíclica

5-96
Nível Ligação
Nível Físico ATM
Dois sub‐níveis na camada física:
TC (Transmission Convergence): adapta o nível ATM ao subnível PMD subjacente
bj
t
Geração e verificação do checksum do header: CRC de 8 bits
Delimitação das células
Delimitação das células
Sincronização do envio das frames com a taxa de transmissão do meio
Adaptação da frame de transmissão ao meio físico
PMD (Physical Medium Dependent): gere o meio físico utilizado

Sincronização da emissão e recepção enviando informação temporal
da emissão e recepção enviando informação temporal
Especificação das interfaces e cablagem para cada meio físico
• SONET/SDH: Várias taxas: OC3 = 155.52 Mbps; OC12 = 622.08 Mbps; OC48 = 2.45 Gbps, OC192 = 9.6 Gbps
2
45 Gbps OC192 9 6 Gbps
• TI/T3: linhas telefónicas tradicionais: 1.5 Mbps/ 45 Mbps
• Multimode Fiber (MMF) e STP: 155 Mbps
5-97
Nível Ligação
IP‐Over‐ATM
IP b ATM
IP sobre ATM
IP clássico
Substitui‐se o segmento de rede 3 segmentos de redes
3 segmentos de redes
IP por uma rede ATM
p
Endereços ATM e IP
Endereços MAC e IP
Routers
IP/ATM
Ethernet
LANs
ATM
backbone
network
Ethernet
LANs
5‐98
Nível Ligação
Trajecto de um Datagrama numa rede IP sobre ATM
No router de entrada:
A camada IP mapeia o endereço IP de destino num endereço ATM utilizando
destino num endereço ATM utilizando ATM‐ARP (RFC 2225)
Passa o datagrama ao nível AAL5
AAL5 encapsula e fragmenta os dados, cria as células e passa‐as ao nível ATM A rede ATM: encaminha a célula através de um circuito virtual até ao router de destino
No router de destino:

AAL5 agrega as células formando o datagrama original
Se o CRC está correcto, o datagrama é entregue à camada IP
Os backbones ATM podem manter circuitos permanentes entre os vários pontos de entrada e saída
5-99
Nível Ligação
Bridging MAC-ATM com LAN Emulation
P
Protocolo
l LANE
L NE (LAN
(L N Emulation)
E l
)
Permite integração de interfaces ATM em hosts ou switches
criando funcionalidades de bridging com 802.3
802 3
Realiza a conversão de endereços MAC para ATM
5-100
Nível Ligação
Conclusão
Princípios dos Serviços da Camada Ligação:
Partilha de canal de broadcast: MAC
Endereçamento de nível ligação
Protocolos de conversão de endereços
Detecção e correcção de erros (ficou para RC II…)
D
ã
ã d
(fi
RC II )
Instanciação e implementação de algumas tecnologias da camada ligação
camada ligação

Ethernet
Dispositivos de ligação
p
g ç
PPP
Virtualização da camada ligação
Modelo ATM
5-101
Nível Ligação