Aulas 17 & 18
Comutação Rápida a Pacote
Eytan Modiano
MIT
1
Comutador a Pacote
Etiqueta
•
•
Um comutador a pacote consiste de uma máquina de roteamento (table lookup), um escalonador e uma máquina de comutação.
A máquina de roteamento procura pelos endereços dos pacotes na tabela de
roteamento e determina para qual porta de saída enviar o pacote.
– O pacote é etiquetado com o número da porta.
– O comutador utiliza a etiqueta para enviar o pacote para a devida porta de
saída.
2
Comutadores de Primeira Geração
• Computador com múltiplas interfaces;
– CPU interroga a interface.
• Simples mas o desempenho é limitado pela velocidade do processador
e do barramento.
• Exemplos: Pontes Ethernet.
3
Comutadores de Segunda Geração
LC - Interfaces
•
•
•
•
A maioria do processamento é feito na interface,
– Procura nas tabelas de roteamento, etc;
– Armazenamento doa pacotes;
– A interface envia os pacotes para as saídas apropriadas.
Vantagens: CPU e Memória Principal não são mais os gargalos.
Desvantagens: Desempenho limitado pela velocidade do barramento.
– A largura de faixa do barramento precisa ser N vezes a velocidade da interface (N
portas).
Exemplo: Roteador CISCO 7500.
4
Comutadores de Terceira Geração
• Substitui o barramento compartilhado por uma máquina de comutação.
• O desempenho depende da máquina de comutação, que pode
potencialmente aliviar o gargalo do barramento.
5
Arquiteturas dos Comutadores
• Buffer distribuído
• Buffer de saída
• Buffer de entrada
6
Buffer Distribuído
• Arquitetura modular
Módulo básico é um comutador 2x2, que pode estar tanto em posição
através como cruzada.
• Buffers do comutador: nenhum, na entrada, ou na saída de cada
módulo.
A máquina de comutação consiste de vários módulos 2x2.
7
Interconexão de Redes
•
•
N entradas
Log(N) estágios com N/2 módulos por estágio;
Exemplo: Omega (rede de troca misturada).
•
Observe que a ordem das entradas em um estágio é uma mistura das saídas do
estágio prévio: (0, 4, 1, 5, 2, 6, 3, 7).
Facilmente estendido para outros estágios
Qualquer saída pode ser alcançada a partir de qualquer entrada, setando
apropriadamente a comutação:
– Nem todas as rotas podem ser feitas simultaneamente;
– Exatamente uma rota entre cada par fonte-destino;
– Rede self-routing.
•
•
8
Auto Roteamento
• Use uma etiqueta: seqüência de n bit um bit por estágio da rede:
– Por ex.: Tag = b3 b2 b1 da etiqueta (bi), e envia o pacote para cima
se bi=0 e para baixo se bi=1.
• Em uma rede Omega, para portas de destino com endereço binário abc
a etiqueta é cba,
– Exemplo: saída 100 => etiqueta = 001;
– Observe que não importando a porta de entrada, a etiqueta 001
levará para a saída 100.
9
Rede de Base
• Um outro exemplo de uma rede multi-estágio de interconexão.
• Construída usando um módulo comutado básico.
• Construção recursiva,
– Construa um comutador N por N usando comutadores N/2 por N/2
e um novo estágio do N/2 básico módulo (2x2);
– Comutador N por N tem L(N) estágios cada com N/2 módulos
(2x2) básicos.
10
Contenção
• Dois pacotes podem querer usar o mesmo enlace ao mesmo
tempo (mesma porta de saída de um módulo).
• Efeito Hot Spot
• Solução: Armazenamento.
11
Análise da Vazão da Interconexão de Redes
• Suponha que não haja armazenamento nos comutadores.
• Se dois pacotes querem usar a mesma porta um deles é descartado.
• Suponha que o comutador tenha m estágios.
• Tempo de transmissão de um pacote = 1 slot (entre estágios).
• Chegada de um novo pacote na entrada, em todos os intervalos de
tempo,
– Análise da saturação (para máxima vazão);
– Distribuição uniforme dos destinos independente de um pacote para
outro pacote.
12
Vazão da Interconexão, continuação
• Seja P(m) a probabilidade de um pacote ser transmitido no enlace do
estágio m P(m)
• P(0) = 1
• P(m+1) = 1 – P (nenhum pacote no enlace do estágio m+1 (enlace c))
= 1 – P (nenhuma entrada para o estágio m+1 escolhe esta saída)
• Cada entrada tem um pacote com uma probabilidade P(m) e o pacote
irá escolher o enlace com probabilidade 1/2. Portanto,
 1

P (m + 1) = 1 − 1 − P ( m) 
 2

2
• Agora podemos determinar P(m) recursivamente.
• Para uma rede de m estágios, a vazão (por enlace de saída) é P(m), que
é a probabilidade que existe um pacote na saída.
13
Vazão
Vazão da Interconexão, continuação
• A vazão pode ser significantemente aumentada adicionando buffers
nos estágios.
– Buffers aumentam o atraso;
– Há um compromisso entre atraso e vazão.
14
Vantagens / Desvantagens da Arquitetura Multi-Estágio
• Vantagens
– Modular
– Escalável
– Barramento (enlaces) somente precisam ser tão rápidos quanto as
interfaces.
• Desvantagens
– Atraso devido à passagem por vários estágios.
• Cut-through possível quando os buffers estão vazios.
– Decréscimo da vazão devido ao bloqueio interno.
• Alternativas: Buffers externos a máquina de comutação.
– Buffers de saída
– Buffers de entrada
15
Arquitetura do Buffer de Saída
• Tão logo o pacote chega, é transferido para um buffer de saída
apropriado.
• Suponha um sistema que aloca fatias de tempo para o processamento.
• Durante cada fatia de tempo à máquina de comutação transfere um
pacote de cada entrada (se disponível) para a saída apropriada.
– Deve ser hábil em transferir N pacotes em cada fatia de tempo;
– A velocidade do barramento deve ser N vezes a taxa da linha;
– Não há filas nos buffers de entrada no máximo um pacote na
entrada para uma fatia de tempo.
16
Análise das Filas
• Se as chegadas em cada entrada são Poisson (taxa média A ), cada fila
de saída comporta-se como uma fila M/D/1.
– a duração de um pacote é igual a uma fatia do tempo X = X 2 = 1 .
• O número médio de pacotes em cada saída é dado por (M/G/1
fórmula):
2 A − ( A)2
NQ =
2(1 − A )
• Observe que o único atraso é devido à fila nas saídas e não a máquina
de comutação.
17
Vantagens /Desvantagens da Arquitetura
com Buffer de Saída
• Vantagem
– Não há atraso ou bloqueio dentro do comutador.
• Desvantagens
– A velocidade do barramento deve ser N vezes a velocidade da
linha.
– Impõe limites práticos no tamanho e capacidade do comutador.
• Buffers de saída compartilhados:
Buffers de saída são implementados em memória compartilhada
usando listas concatenadas.
– Requer menos memória (devido a multiplexação estatística).
– a memória deve ser rápida.
18
Arquitetura com Buffer de Entrada I
•
Pacotes armazenados na entrada em vez da saída.
– A máquina de comutação não deve ser tão rápida.
•
Durante cada intervalo de tempo, o escalonador estabelece as conexões crossbar para
transferir os pacotes da entrada para a saída.
– Máximo de um pacote a partir de cada entrada.
– Máximo de um pacote para cada saída.
Bloqueio do pacote na cabeça da fila (HOL - Head Of Line blocking) quando o pacote
na cabeça de duas ou mais filas é destinado para a mesma saída, somente um pode ser
transferido e os outros são bloqueados.
•
19
Análise da Vazão dos Comutadores Com Filas na Entrada
• Bloqueio HOL limita a vazão pois algumas entradas
(conseqüentemente saídas) são mantidas não ativas durante um
intervalo de tempo mesmo quando existam pacotes em suas filas para
serem enviados.
• Considere um comutador NxN e suponha que as entradas são saturadas
(sempre tem um pacote para enviar).
• Tráfego uniforme ⇒ cada pacote é destinado para cada saída com igual
probabilidade (1/N).
• Agora, considere somente aqueles pacotes na cabeça de suas filas
(existem N deles!).
20
Análise da Vazão, continuação
i
• Seja Qm o número de pacotes HOL destinados ao nó I no fim do mth
intervalo de tempo.
Qmi = max(0, Qmi −1 + Ami − 1)
• Onde
Ami = número de novas mensagens HOL endereçadas ao nó I que chegam
HOL durante o intervalo m. Agora,
l
C
−l


P ( Ami = l ) =  C m −1 (1 N ) (1 − 1 N ) M −1
 l 
• Onde
Cm −1 = número de mensagens HOL que saem durante o intervalo m-1 =
número de novas chegadas HOL.
• Quando N se aproxima de infinito, Ami torna-se Poisson com taxa C/N
onde C é o número médio de saídas por intervalo de tempo.
21
Análise da Vazão, continuação
• No estado estável Qi comporta-se como uma M/D/1 e portanto.
2
2
A
−
(
A
)
Qi =
2(1 − A )
• Observe contudo que o número total de pacotes endereçados para as
saídas é N (numero de pacotes HOL) e portanto,
N
i
Q
∑ =N
i =1
⇒
2
2
A
−
(
A
)
Qi =
2(1 − A )
Utilizando a forma quadrática:
A = utilização 2 − 2 ≈ 0,58
22
Resumo dos Comutadores Com Fila na Entrada
• A vazão máxima de um comutador com fila na entrada, é limitada pelo
bloqueio HOL a 58% (para N grande).
• Vantagens da fila na entrada:
– Simples
– Taxa no barramento = Taxa na linha
• Desvantagem
– Limitação na vazão
23
Evitando o Bloqueio HOL
• Se as entradas tiverem a permissão de transferir os pacotes que não
estão na cabeça de suas filas, a vazão pode ser bastante melhorada (não
FCFS).
• Exemplo:
• Como, o escalonador faz sua decisão de que entrada transferir para
qual saída?
24
Matriz de Backlog
•
•
Cada entrada na matriz de backlog representa o número de pacotes na fila de
entrada i que estão destinados à saída j.
Durante cda intervalo o escalonador pode transferir no máximo um pacote de
cada entrada para cada saída.
– O escalonador escolhe o pacote a partir de cada linha, e coluna da matriz
de backlog.
– Isto pode ser feito a partir de um algoritmo gráfico de casamento bipartite.
– O gráfico bi-partite consiste de N nós representando as entradas e N nós
representando as saídas.
25
Representação do Gráfico Bi-Partite
•
Existe um limite no gráfico de uma entrada para uma saída se existe um
pacote na matriz de backlog que deve ser transferido a partir daquela entrada
para a aquela saída.
– Para a matriz de backlog anterior o gráfico bi-partite é:
•
Definição: Um casamento é um conjunto de limites, tal que nenhum par de
limites compartilhe um nó.
– Achar um casamento no gráfico bi-partite é equivalente a encontrar um
conjunto de pacotes tal que nenhum par de pacotes compartilha uma linha
ou coluna na matriz de backlog.
Definição: Um casamento máximo é um casamento com o máximo possível
de limites.
– Achar um casamento máximo é equivalente a achar o maior conjunto de
pacotes que podem ser transferidos simultaneamente.
•
26
Casamentos Máximos
• Algoritmos para achar casamentos máximos existem.
• O algoritmo mais conhecido faz O(N2.5) operações.
– Muito longo para N grande.
• Alternativas
– Soluções sub-ótimas
– Casamento máximo: Um casamento que não pode ser feito maior
ainda para uma dada matriz de backlog.
– Para o exemplo anterior:
(1-1, 3-3) é máximo.
Fato: O número de limites num casamento máx ≥ 1/2 o número de
limites num casamento máximo.
27
Obtendo 100% de Vazão Em Um Comutador
Com Fila na Entrada
• Achando um casamento máximo durante cada intervalo de tempo não
elimina o efeito do bloqueio HOL.
– Deve olhar além dos intervalos no momento a tomar uma decisão
de escalonamento.
• Definição: Um gráfico bi-partite com pesos é um gráfico bi-partite com
custos associados a cada limiar.
• Definição: U casamento máximo com pesos é um casamento com os
limiares de maior peso.
• Teorema: Um escalonador que escolhe durante cada intervalo o
máximo casamento com pesos onde o peso do enlace (i, j) é igual ao
comprimento da fila (i,j) obtém uma utilização plena (100% da vazão).
– Prova: veja “Achieving 100% throughput in an input queued
switch” by N. McKeown, et. al., IEEE Transactions on
Communications, Aug. 1999.
28