Redes de computadores:
Tecnologia de Comutação
Prof. Dr. Amine BERQIA
[email protected]
http://w3.ualg.pt/~bamine /
Sumário
Comutação de Circuitos
 Comutação de Mensagens
 Comutação de Pacotes
– Comutação de pacotes Datagrama
– Comutação de pacotes por circuito
virtual

Porque Comutação?
CPU
Conecte 1
Conecte 2
Mem
principal.
Conecte 3
Barramento de I/O
• Assuma a estação de trabalho com DMA é usado como comutador
para mover dados; Desempenho é limitado: Cada pacote cruza o bus de
I/O duas vezes e é lido e escrito na memoria uma vez;
• Para evitar este problema, utilizamos uma grande malha de tecido de
comutação para reduzir a contenção fornecer uma grande fluidez.
Tecnologia de Comutação
• Recursos são reservados nas redes de comutação de
circuitos de comutação de circuitos.
Semelhante a um restaurante que aceita reservas.
Uma rede de telefones é uma rede de comutação de circuitos.
• Recursos não são reservados para redes de comutação de
pacotes.
Semelhante a um restaurante que não aceita reservas.
A Internet é uma rede de comutação de pacotes.
•Não todas as redes podem ser classificadas como puras redes
de comutação de pacotes ou circuitos.
• Redes baseadas em ATM associam conceitos de comutação
de circuitos e de pacotes
Comutação de Circuitos
Comutador
office
Físico
cobre
Quando você / seu computador faz uma cahamada, o
equipamento de comutação dentro do sistema de telefone
procura um caminho físico de cobre desde o seu telefone até o
telefone de destino. Esta técnica é chamada de comutação de
circuitos.
Operação de Comutação de
Circuitos (1)
C
A
7
1
D
4
2
B
6
3
5
E
Comutação de Circuitos envolve três fases:
1. Estabelecimento de circuito
2. Transferência de Dados
3. Terminação do circuito
Operação de Comutação de
Circuitos(2)
C
A
7
1
D
4
2
B
6
3
5
E
"Sinal de ocupado" se capacidade para um circuito não disponível
Propriedades de Comutação de
Circuitos
• Um caminho de comunicação dedicado é estabelecido
entre duas estações através dos nós da rede.
• O caminho dedicado é chamado uma conexão comutada
por circuito ou circuito.
• Um circuito ocupa uma capacidade fixa de cada ligação
durante o tempo da conexão. A capacidade não utilizada pelo
circuito NÂO PODE ser usado por outros circuitos.
• Dados não se atrasam nos comutadores.
Temporização na Comutação de
Circuitos
Salto 1
Estabelecimento
do Circuito
Atraso
Trans.
Dados
Terminação
Circuito
Salto 2
Salto 3
Atraso de
Propagação
por salto
Atraso de
Propagação
entre duas
estações
Atraso de fim-a-fim de Comutação
Circuitos
Tc = S + D + UM
Neste caso,
S = tempo de inicio de chamada
D = tempo de entrega de mensagem
= atraso propagação + tempo transmissão
= Nx Dn + L/B
Em que,
N = Numero de saltos entre as duas estações
Dp = Atraso de Propagação por salto
L = Tamanho de Dados
B = Taxa de Dados
Um = tempo de Reconhecimento
So : Tc = S + NDp + L/B + A
Vantagens e Desvantagens de
Comutação de Circuitos
Vantagens:
1.Largura da banda fixa, capacidade garantida (nenhuma
congestão).
2.Variação do atraso de ponta-a-ponta biaxo (atraso é quase
constante).
Desvantagens:
1. Iniciar e Terminar conexões introduz overhead.
2. Utilizador paga circuito, mesmo quando não utiliza.
3. Outros utilizadores não podem usar o circuito nem sequer se
estiver livre de tráfego.
4. Tráfego entre computadores é frequentemente desigual, deixando
a conexão ociosa a maior parte do tempo.
5. Remetente e receptor precisam enviar e receber a mesma taxa.
6. Quando circuito está ocupado, ou no max. da capacidade, as
conexões estão bloqueadas.
Operação de Comutação por
Mensagens
Não é estabelecida uma ligação fisica de cobre entre emissor
e receptor
Cada bloco é recebido por inteiro, inspeccionado por erros, e
depois retransmitido, chamado store-and-forward.
Nenhum limite no tamanho da mensagem. Cabe aos Routers
fazer buffer de mensagens longas utilizando discos.
Pode conter uma ligação de router-router durante minutos.
Inútil para tráfego interactivo.
Atraso de ponta-a-ponta de
Comutação por Mensagens
Tm = N. Md + Pd
Neste caso,
N = Número de saltos entre duas estações
Md = tempo de entrega de Mensagem por salto
= atraso propagação + atraso transmissão
= Dp + L/B
Pd = Atraso Processamento entre dois saltos
Tm = N(Dp + L/B) + (N - 1)  Pd
Comutação por Pacotes
Mensagem
Pacotes
Ola, Amigo,
H1
Ola,
H2 Amigo
• Uma mensagem não é enviada como uma única unidade, mas dividida em
pacotes pequenos que são transmitidos individualmente.
• Cada pacote tem cabeçalho que contém a origem, destino e numero de
sequencia; Pacotes podem viajar em rotas diferentes, ou podem chegar no
destino for a de ordem. A rede reúne os pacotes, utilizando a informação
contida em cada pacote relativo ao número de sequência.
• Comutador tem que receber o pacote inteiro antes de possa começar a
transmitir o primeiro bit do pacote sobre a ligação de saída.
• Dois métodos: Pacote de Datagrama e Pacote de Circuito Virtual (VC).
Comutação por Pacote
Datagrama
1. Não há atraso de ida-e-volta por ter de esperar pela inicialização duma
conexão; Uma estação pode enviar dados assim que esteja pronta.
2. Quando uma estação enviar um pacote, não existe forma de saber se a
rede é capaz de entregar ou se a estação de destino esta disponível.
3. Cada pacote (de mesma mensagem) pode viajar por caminhos
diferentes; É necessário voltar a colocar a sequência.
4. Como todos os pacotes têm que levar o endereço de destino completo,
o overhead por pacote é maior que para o método orientado a conexão.
Operação de Comutação por
Pacote Datagrama (1)
C
A
7
1
D
4
2
B
6
3
5
E
Analogia: sistema postal; Por vezes designado modelo sem
conexão;
Cada comutador mantém uma tabela de encaminhamento
(routing).
Operação de Comutação por
Pacote Datagrama (2)
C
Um
7
1
D
4
2
B
6
3
5
E
Operação de Comutação por
Pacote Datagrama (3)
C
A
7
1
D
4
2
B
6
3
5
E
Operação de Comutação por
Pacote Datagrama (4)
C
A
7
1
D
4
2
B
6
3
5
E
Operação de Comutação por
Pacote Datagrama (5)
C
Um
7
1
D
4
2
B
6
3
5
E
Operação de Comutação por
Pacote Datagrama (6)
C
A
7
1
D
4
2
B
6
3
5
E
Operação de Comutação por
Pacote Datagrama (7)
C
Um
7
1
D
4
2
B
6
3
5
E
Operação de Comutação por
Pacote Datagrama (8)
C
A
7
1
D
4
2
B
6
3
5
E
Operação de Comutação por
Pacote Datagrama (9)
C
A
7
1
D
4
2
B
6
3
5
E
Operação de Comutação por
Pacote Datagrama (10)
C
A
7
1
D
4
2
B
6
3
5
E
Exemplo de Comutação por
Pacote Datagrama
3
Host C
0 Comutador 1
1
3
2 Comutador 2
1
Host F
2
0
Host A
Tabela de encaminhamento
para comutador 2
Destino
A
B
D
F
Porta Com.
3
0
0
1
1
Host D
0 Comutador 3
3
2
Host H
Host B
Atraso de ponta-a-ponta de Pacote
de Datagrama
Td = D1 + D2 + D3
Neste caso,
D1 = tempo para transmitir e entregar todos os pacotes ao primeiro salto
D2 = tempo de entrega de ultimo pacote ao segundo salto
D3 = tempo de entrega de último pacote ao terceiro salto
Que seja, NP =  L/(P-H)  = numero de pacotes
em que, L = comprimento de mensagem, P = tamanho de pacote,
H = tamanho de cabeçalho t = tempo de transmissão por pacote = P/B,
B = taxa de dados
Dp = atraso de propagação por salto
N = Numero de saltos entre estações
D1 = Np (P/B) + Dp
D2 = D3 = t + Dp = P / B + Dp
Td = D1 + D2 + D3
= Np(P/B) + Dp + (N –1 )(P/B + Dp)
= (Np+N -1)(P/B) + NDp
Comutação por Pacotes de Circuito
Virtual
Comutação por pacotes VC é um híbrido de comutação de circuitos e
comutação por pacotes:
Todo os dados são transmitidos como pacotes
Todos os pacotes de uma mensagem são enviados junto num
caminho preestabelecido (circuito virtual)
Comunicação com circuitos virtuais (VC) acontece em três fases:
1. Estabelecimento de VC
2. Transferência Dados
3. Disconexão VC
È garantida a entrega de pacotes em sequência.
Contudo , pacotes de VCs diferentes podem ser intercalados.
Exemplo de Circuito Virtual
0 Comutador 1
1
3
3
5
5
5
2
11
2 Comutador 2
1
Host D
0
Host A
5
7
1
0 Comutador 3
3
Segmento de tabela de VC Com. 1
Porta
Nº VC
Entrada Entrada
2
1
2
4
2
5
2
6
Porta
Saída
2
0
1
0
Nº VC
Saída
4
3
11
4
2
Host C
5
4
Host B
Atraso de ponta-a-ponta de Comutação
por Pacotes de Circuito Virtual
Tv = V1 + V2 + A
Neste caso,
V1 = tempo de inic. de ligação, S,
V2 = tempo de comutação de pacote de datagrama, Td,
A = Tempo de reconhecimento
Tv = S + Td + A
= S+ (Np+N -1)(P/B) + NDp + A
Vantagens Comutação por Pacotes
1.Comutação por pacotes utiliza recursos mais eficientemente;
2.Tempo de iniciar e terminar ligações muito pequeno;
3.É mais flexível (i.e. não se preocupa muito com o que é enviou,
desde que seja possível colocar em formato pacote);
4. Emissor e receptor podem transmitir a taxas diferentes;
5. Tipos diferentes de computadores podem comunicar em rede de
comutação por pacotes;
6. Redes de comutação por pacotes não recusam uma conexão; no
máximo, atrasam a ligação até que o pacote possa ser transmitido;
7. Comutação por pacotes consegue gerir tráfego impulsivo (bursty).
É mais usado nas redes de computadores;
Desvantagens de Comutação por
Pacotes
1. Nenhuma garantia nos atrasos;
2. Algoritmos são mais complexos;
3. Demasiados pacotes poderão conduzir a uma congestão da rede
comutada por pacotes: pacotes que não são guardados ou
entregues podem ser descartados;
4. Pacotes podem chegar a tempos diferentes e numa ordem
diferente de aquela em que foram enviados: problemático para
uma conversa telefónica.
Estrutura Comutador ATM
Tecido Comutação
Comutadores ATM são elementos de rede que apoiam o
controle de conexão, transporte de célula, e administração
das funções das redes ATM.
Comutadores Crossbar
1. Para Crossbar NxN, tem 2N
barramentos, N2 cruzamentos, que estão
On ou Off;
2. Um buffer em cada cruzamento;
3. De acordo com árbitro, entre N
buffers, um buffer será escolhido em
cada fatia de tempo;
4. Estrutura simples e não-bloqueante;
E
N
T
R
A
D
A
S
5. Precisa de mecanismo arbitragem
complexa;
6. Buffers não são compartilhados;
7. No max. N de N2 são usados.
SAÍDAS
Comutadores Knockout
N barramentos separados para cada
par E/S.
1
2
3
4
Duas possibilidades: 1. Celulas
Concentradormúltiplas vão para mesma porta
N
L
1234
de saída; 2. Uma celula é multicast
a várias portas de saída.
A memória tem que funcionar N
vezes a taxa de entrada que é
impossível para comutadores
grandes. Assim um concentrador e
buffers são necessários para
Filteros
reduzir a exigência de veloc. De
Endereços memoria.
Concentrador selecciona L (N)
Buffers
para buffer. Todas as celulas L
seleccionados entram no filtro de
endereços. Filtro de endereços os
distribui uniformemente por
buffres de saída que utilizando um
testemunho para manter registro
de qual buffer vai a seguir.
Retry or
Discard
Elemento de Comutação (SE)



2x 2 elementos de comutação;
Regra de encaminhamento: se o bit da porta de saída for 0,
envie célula a saída superior, senão saída inferior; Se ambas as
células vão para mesma saída, ou põe uma em buffer ou
descarta uma;
Utilizando este SE simples, podemos construir tecidos
complicados.
Banyan Switches
0
1




000
001
SE
2
3
010
011
4
5
100
101
6
7
110
111
fase 2
fase 1
fase 0
Uma família de comutadores auto-encaminhantes, informação de routing contida no cabeçalho
de célula,;
Estrutura paralela, podem ser processadas várias células em caminhos diferentes
simultaneamente;
Mais adequado para construir grandes comutadores;
Dois grandes problemas.
Banyan Switch Bloqueado
Internamente
0
1
000
001
2
3
010
011
4
5
100
101
6
7
110
111
fase 2
fase 1
fase 0
Problema 1: Bloqueado internamente, até mesmo as saídas estão disponíveis.
Soluções:
1. Usar M xM (M>2) SEs (Clos);
2. Utilizar buffers dentro de cada SE (WUGS-20);
3. Usar Rede de Distribuição para distribuir células de entrada tão uniformemente quanto possível.
Banyan Switches saída
Bloqueada
0
1
000
001
2
3
010
011
4
5
100
101
6
7
110
111
organize 2 fase 1 fase 0
Problem2: Saída Bloqueada. Duas ou mais células apontam à mesma linha de saída.
Solução: Usar Redes Batcher Banyan Switching.
Comutadores com Entrada Buffered
t4 t3 t2 t1 t0
0
1
32
0
0
1
2
02
3
1
SF
2
3
AE
Células destinadas a saídas inactivas não podem ser servidas por causa de
Bloqueamento Head-Of-Line(HOL) .