O Nível Rede: Introdução cada vez que falha algo. 4. Estabilidade.

Se nunca convergir para o equilíbrio não

Preocupa-se em “levar pacotes da origem para o destino” toma decisões ideais. 5. Justiça. 6. Otimização.
Haverá hops (troços de rede), ao contrário do nível Lógico 5. e 6. podem estar em confronto uma com a outra. O que é que se quer
De algum modo, neste nível é onde a preocupação destino a destino se faz otimizar? Minimizar o atraso medio de um pacote? Maximizar o debito geral da
primeiro sentir. Vai ter de: Conhecer a topologia para melhor a usar; Evitar zonas rede? Mas até estes estão em conflito!!! Minimizar o número de saltos ( hops) que
superlotadas; Compatibilizar redes diferentes pelo caminho. um pacote dá de algum modo melhora o atraso e não desperdiça largura de
Aspetos do Desenho: banda.
Comutação de Pacotes Store-and-Forward: Serviços prestados
ao nível Transporte. Tipos de algoritmos de encaminhamento
A interface Rede – Algoritmos não adaptativos
Transporte é importante Os encaminhadores têm a informação na altura do seu arranque;
pois é também Encaminhamento estático.
a interface entre a Algoritmos adaptativos
operadora e o utilizador, Mudam as suas decisões em função da topologia;
e define a fronteira da Como obtêm a informação? por si, pelos vizinhos, por todos;
sub-rede. Quando a obtêm? ΔT, carga muda, topologia muda;
Objetivos para os Que métrica usam? distância, hops, tempo de trânsito.
serviços prestados ao nível Transporte: 1. Devem ser independentes da O princípio da rota ótima: Princípio geral independente da topologia ou do
tecnologia da sub-rede; tráfego: Se J está no caminho ótimo de I para K, o caminho ótimo de J para K é
2. O Nível de Transporte coincidente com a parte do anterior.
deve ser escudado do Se houvesse outro
número, tipo e topologia caminho entre J e K,
das sub-redes usadas; 3. também seria
Os endereços rede aproveitado entre I e
usados pelo Transporte K. O conjunto de
devem obedecer a um caminhos ótimos de
plano de numeração todas as origens para
uniforme mesmo usando um destino forma
LANs e WANs. O Serviço uma árvore.
Rede pode ser orientado
Pode haver mais do que uma arvore com um custo igual …
a ligação ou ser sem ligação (datagramas).
Se todos os caminhos possíveis de menor custo puderem ser usados, a arvore
Realização do serviço Rede sem ligação
transforma-se num grafo acíclico dirigido (DAG – Directed Acyclic Graph).
Rede de datagramas – os pacotes são injetados e encaminhados na rede
Não existem laços e os pacotes são sempre entregues depois de um número
individualmente.
finito e limitado de saltos. Ao se
considerar a possibilidade de elementos
falharem, a visão que os encaminhadores
têm da rede pode ser diferente, levando a
problemas.
Encaminhamento pelo Caminho Mais
Curto: Construir um grafo da rede
(estático): os encaminhadores são nós, as
linhas são arcos. Encontrar o caminho
mais curto entre dois pontos em número
de saltos, distância em quilómetros, atraso
na fila de espera, largura de banda, custo de comunicação, ou qualquer outra
Realização do serviço Rede com ligação
métrica aditiva.
Rede de circuitos virtuais - é estabelecido um caminho da origem ao destino
Algoritmo de Dijkstra: Selecionar os nós sequencialmente por custo crescente.
durante o
Após selecionar um nó, explorar todos os novos caminhos, substituindo os
estabelecimento da ligação (VC - Circuito Virtual); pacotes contêm identificador
caminhos provisórios de maior custo conhecidos.
de VC.
Porque funciona?… Acabou de se fazer E permanente, com ABE. Se houvesse
outro caminho para E mais barato, AXYZE, das duas uma: - Z já é permanente
(o E já tinha sido calculado, a seguir a Z ser permanente, portanto a rota ABE
nunca seria escolhida); - Z ainda não é permanente (ou Z é maior do que E, e
nesse caso AXYZE não pode ser mais barata; ou Z é menor do que E e devia ser
feito permanente em vez de E).
Encaminhamento por Inundação: Estático!
Cada pacote que entra é enviado por todas as
outras linhas de saída. Gera imensos pacotes,
mesmo infinitos se a rede tem ciclos. Para
controlar esse número pode-se agir sobre o
número de saltos, com um contador inicializado
Comparação entre redes de datagramas e redes de com a “distância” ao destino e ter um registo
de pacotes já vistos (n.º de sequência)
Inundação seletiva (selective flooding): Os pacotes são enviados para as
linhas que vão mais ou menos no sentido correto. Para que é útil? Fins
militares – muito robusto; Aplicações de bases de dados distribuídas –
atualização concorrente; Como métrica de comparação – mais curto, menos
atraso (mas também o mais longo porque envia por todos).
Encaminhamento por Vetores de Distâncias: Dinâmico! Foi o primeiro
algoritmo usado na Internet, mas tem graves problemas e foi substituído. É o
mais popular juntamente com o Estado de Linha. Cada encaminhador tem
circuitos virtuais: uma tabela (de encaminhamento) com a melhor distância para todos os nós da
Compromissos entre redes de datagramas e redes de circuitos virtuais rede e por onde se deve sair.
O serviço oferecido é um Trocando-se informação com os vizinhos, atualiza-se a tabela:
assunto separado da estrutura Em cada T seg cada
interna da rede e.g. IP sobre encaminhador envia ao seu
MPLS; tráfego VPN sobre IP. vizinho uma lista de
estimativas de tempos de
Algoritmos de atraso para todos os
Encaminhamento: destinos … e recebe outras
O encaminhamento e o assunto dos seus vizinhos. Ao
mais importante do nível. O receber uma lista de X, e
algoritmo de encaminhamento e a parte do software do nível rede responsável sabendo que demora m seg
por decidir por quais das linhas de saída o pacote deve ir. a chegar a X, é possível
por pacote; por ligação – encaminhamento de sessão. saber quanto demora a
Propriedades: 1. Simplicidade. 2. Correção. 3. Robustez. Uma rede chegar aos destinos por X.
deve trabalhar sem falhas globais. Vão existir falhas locais, com mudanças de Ao comparar as várias
topologia. O algoritmo deve adaptar-se sem necessitar de um arranque global tabelas, sem utilizar a
 sua, fica a saber as melhores saídas. Forma, então, uma versão atualizada da curto para cada destino e instala-se na tabela de encaminhamento. Problemas:
sua que entrega aos vizinhos. Um encaminhador não diz que tem uma linha, ou diz que tem uma linha
O problema da contagem para infinito: A principal desvantagem do algoritmo é imaginária. Um encaminhador deixa de reenviar pacotes, ou envia-os
convergir lentamente perante falhas. Reage “rapidamente” a “boas” notícias - 1 incorretamente. Exemplos práticos de usos deste algoritmo: OSPF – usado na
salto por troca de vetores; Reage lentamente a “más” notícias - quando a Internet; IS-IS – desenhado pela DEC; norma ISO para OSI CLNP, IP, etc.; suporta
ligação A-B falha, C ainda oferece uma rota para A! diversos tipos de endereços do nível Rede.
A “solução” da Separação de horizontes com envenenamento da rota inversa Encaminhamento Hierárquico: Redes Grandes > grandes tabelas de
para o problema da contagem para infinito: A distância para o destino X não é encaminhamento: Memória; Tempo de CPU; Largura de banda (tráfego
anunciada pela linha por onde se vai para X (é reportada como “infinito”). e.g. sinalização). Chega a um ponto em que um encaminhador não pode ter uma
rota para A. Se A falha, B vê que a linha foi abaixo e C reporta infinito – logo B entrada para cada outro encaminhador. Divide-se a rede em regiões em que o
deteta que A não está disponível. Na próxima rodada, B reporta infinito – C encaminhador sabe encaminhar pacotes na sua região e não sabe nada da
também deteta que A falhou. As más notícias já se propagam um salto por estrutura interna das outras regiões.
rodada. MAS, às vezes falha!!! e.g. quando a topologia tem circuitos fechados. Quando a rede é muito grande, podem-se criar sub-hierarquias: agrupam-se
A “solução” de Hold down para o problema da contagem para infinito: Quando a regiões em clusters; agrupam-se clusters em zonas; agrupam-se zonas em
melhor rota selecionada anteriormente desaparece (falha de nós ou de linhas), grupos; agrupam-se grupos em turmas; agrupam-se turmas em (…); Até onde se
o encaminhador bloqueia o valor de ∞ para essa rota durante um TEMPO DE deve ir? 720 encaminhadores: 1 nível - 720 entradas; 24 regiões com 30
HOLD DOWN. Só após o fim do tempo, volta a funcionar normalmente, encaminhadores - 53 entradas; 8 clusters, 9 regiões, 10 encaminhadores - 25
procurando uma rota para esse destino. Perguntas: entradas. Kamoun e Kleinrock (1979) demonstraram que o número ótimo de
Será que funciona corretamente com uma rede com circuitos fechados? Quais níveis é ln N com um total de e ln N entradas, com um pequeno aumento do
são os problemas introduzidos pelo hold down? --- Otimização: Se durante o comprimento da rota. ln 720 ≈ 6.5 e ln 720 ≈ 17.8.
tempo de hold down for encontrada uma rota igual ou mais curta, interrompe-se Encaminhamento por Difusão (broadcast): Às vezes há necessidade de
o hold down! O algoritmo de vetores de distâncias deixou de ser o algoritmo da enviar o mesmo pacote para muitos ou todos os destinos. Informação
Internet em 1979. meteorológica, informação da bolsa, …. Vários métodos: 1. Inundação – não
Encaminhamento por Estado da Linha (Link State): Cada encaminhador adaptado a redes ponto-a-ponto (gera muitos pacotes e consome muita largura
deve fazer o seguinte: de banda). 2. Envio de pacote para todos os destinos – tem de se ter uma lista de
1. Descobrir os vizinhos e saber os seus endereços de rede; 2. Medir o atraso, ou todos os destinos, consome muita largura de banda. 3. Encaminhamento
o custo, para cada um dos vizinhos; 3. Construir um pacote a dizer tudo o que multidestino (multidestination routing). Cada pacote tem uma lista de destinos e
aprendeu; 4. Enviar este pacote a todos os encaminhadores; 5. Calcular o um mapa de bits indicando os destinos pretendidos. Quando o pacote chega é
caminho mais curto para cada encaminhador. visto para que linhas de saída ele deve ser enviado. Copia-se o pacote incluindo
Descobrir os vizinhos e saber os seus endereços de rede: Depois de vir acima, apenas a lista de endereços válidos para a linha onde vai ser enviado. No final
envia um pacote HELLO por cada linha que tem. Os encaminhadores do outro cada pacote terá apenas um endereço… Eficiência do encaminhamento
lado respondem, dizendo a sua identificação. Os nomes têm de ser únicos, multidestino?
pois um encaminhador distante que ouve que três encaminhadores estão todos Uso da spanning tree (árvore de difusão): Cada encaminhador copia o pacote
ligados a F, tem de saber que todos se referem ao mesmo F. Quando os para todas as linhas da spanning tree (árvore de difusão de custos mínimos).
encaminhadores estão ligados por LAN, a LAN é considerada como mais um nó, Gera o mínimo absoluto de pacotes, poupando largura de banda, mas exige
artificial. Poder-se ir de A para C pela LAN é representado pela rota ANC. conhecer-se a spanning tree a partir de todas as origens. Possível quando se usa
Medir o atraso, ou o custo, para cada um dos vizinhos: O custo de cada linha encaminhamento por estado de linha. Obriga a calcular as tabelas de
pode ser definido automaticamente, ou pelo operador de rede. e.g. Custo encaminhamento de todas as origens para todos os destinos, em todos os
inversamente proporcional ao débito da ligação. O atraso pode ser considerado encaminhadores. Cada nó mantém uma tabela de encaminhamento broadcast
para redes dispersas geograficamente. Envia-se um pacote ECO ao vizinho e este com: Endereço de origem; Linhas de saída.
responde logo de seguida (pode-se fazer uma média de vários pacotes para Uso do reverse path forwarding (envio pela rota inversa): Parecido com o
reduzir o erro). Deve-se considerar a carga? rota menos congestionada vs. anterior, mas sem exigir conhecer a spanning tree. Só da tabela de
oscilações … encaminhamento. Não é tão eficiente, mas… Quando um pacote é recebido,
Construir um pacote a dizer tudo o que aprendeu: O pacote começa com a verifica-se se ele veio pela linha que é normalmente usada para enviar para a
identificação do encaminhador, um número de sequência, a validade (age), origem desse pacote: Se sim, deve ter vindo pela melhor rota e é o primeiro;
seguido da lista de vizinhos com o custo associado a cada vizinho. Quando se faz-se a inundação para as outras linhas; Se não, descarta-se.
devem construir os pacotes? Periodicamente; Quando acontecem modificações Geraram-se 23 pacotes em vez do mínimo 14. É razoavelmente eficiente e fácil
significativas (link down, link up, etc.). de implementar.
Enviar este pacote a todos os Encaminhamento por Multicast (para grupos): Certas aplicações têm a
encaminhadores: A distribuição necessidade de contactar processos muito distantes entre si que formam um
tem de ser fiável. O grande grupo. Se o grupo for pequeno pode usar-se ponto-a-ponto; Se o universo da
problema é que quando rede for grande, broadcast é ineficiente. O encaminhamento necessário para
recebem os pacotes, os enviar pacotes para grupos “grandes”, mas pequenos comparados com a rede
encaminhadores vão alterando chama-se multicast. É preciso haver gestão de grupos: criar, destruir, inscrever-
as tabelas que também poderiam ser usadas para distribuir os pacotes… Para se, desistir-se. Os encaminhadores têm de saber que máquinas pertencem ao
distribuir os pacotes usa-se inundação, e um número de sequência para grupo. Dizem essa informação aos seus vizinhos, e a informação vai-se
distinguir os pacotes. Os encaminhadores guardam o (source router, seq) e propagando pela rede; ou inundam a informação na rede. O encaminhamento
verificam se o pacote já passou por ali: Se não, é enviado para todas as linhas multicast é semelhante ao encaminhamento broadcast, exceto que os pacotes
menos a que veio. Se sim (se a seq é menor ou igual), é descartado. Problemas: apenas devem ser enviados para os membros do grupo.
seq dar a volta; Reinicialização do encaminhador com perda do número de A melhor árvore de custo mínimo a usar depende da
sequência; Erros no campo seq. densidade de nós: - Redes densas, com muitos nós
Solução para problemas no seq: – colocar a validade (age) no pacote; – espalhados por toda a rede – spanning tree é um bom
decrementa-se a validade e quando chegar a zero descarta-se a informação ponto de partida; - Redes esparsas, onde a maior parte da
desse encaminhador; – a validade também é decrementada durante a inundação rede não pertence ao grupo, requer outra solução. Redes densas: Se a
do pacote; – o descarte da informação só deve acontecer quando o topologia da rede é conhecida é possível usar a spanning tree. Quando se envia
encaminhador estiver em baixo. Melhoramentos na distribuição dos pacotes: um pacote para cada grupo, o encaminhador examina a spanning tree e “limpa-
Todos os pacotes são reconhecidos (ACK). Quando se recebe um pacote aguarda- a” de todas as linhas que não vão dar a máquinas do grupo. Cria-se uma tabela
se um tempo antes de o voltar a enviar. Quando não há tráfego numa linha (ou
de encaminhamento por grupo e por endereço de origem. Usado em: MOSPF
após o tempo máximo de atraso), enviam-se os pacotes ou o reconhecimento.
Flags Send flags e ACK flags memorizam por onde o pacote deve ser enviado e (Multicast OSPF).
por onde deve ser enviado um ACK.
Usa-se o reverse path forwarding: Quando um encaminhador recebe um pacote
PERGUNTA: Se um pacote do estado de C chegar por F com seq=20, como muda
para um grupo a que não tenha máquinas que pertençam, nem tenha ligações a
o estado da
outros encaminhadores, envia de volta uma mensagem PRUNE para não lhe
tabela? As flags
serem enviados pacotes para aquele grupo. A sub-rede vai
associadas a C
ficando “limpa” a pouco e pouco. E se o no ficar
mudam para: 1
interessado em receber pacotes do grupo 2? Cria-se
0 0 0 1 1
uma tabela de encaminhamento por origem e por grupo
(enviar ACK para F).
com: Linhas para onde não se deve enviar os pacotes
Calcular o caminho mais
(prunned); Validade de cada PRUNE.
curto para cada
Usado no DVMRP (Distance Vector Multicast Routing Protocol). Não escala para
encaminhador: Quando já
grandes redes – guarda uma árvore para cada origem possível e para cada
tiver bastantes pacotes,
grupo!
pode construir o grafo. Cada
Redes esparsas: Cria-se uma única spanning tree para cada grupo centrada
linha é representada duas
num nó raiz – core-based tree. Todos os nós concordam num nó raiz e
vezes (pode fazer-se a
constroem a árvore enviando-lhe um pacote – a árvore é a união de todos os
média).
caminhos dos pacotes. Para enviar uma mensagem para o grupo, um nó envia a
Usa-se o algoritmo de
mensagem para a raiz (unicast); a mensagem é enviada por multicast a partir da
Dijkstra (ou equivalente),
calcula-se o caminho mais
raiz para o grupo. A árvore não é ótima para todas as fontes. Usada no PIM maiores requisitos de QoS. E para outros dados? Os algoritmos de janela
(Protocol Independent Multicast). deslizante limitam a quantidade de dados em transito de cada vez. Não limitam o
Encaminhamento por Anycast: Usa-se anycast quando um pacote deve ser ritmo a que são enviados.
Algoritmo do balde furado (leaky bucket): “Um balde com um furo”. A saída
enviado para o membro de um grupo a menor “distância”. Útil para servidores
e constante, não interessando a que ritmo entra no balde, se há água no balde.
replicados. Protocolo de encaminhamento vê os nós replicados como se fossem Quando o balde está vazio a saída e zero, ou igual a entrada se o débito for
um só! Podemos usar: vetores de distâncias? estado de linha? O que fazer a inferior ao débito de saída do balde. Se estiver muito cheio a água começa a sair
rotas que passam por um nó “1”? por cima, perdendo-se. Realizado com um sistema de filas de espera, com um só
Gestão de Tráfego no Nível servidor, e com serviço determinístico, com ritmo R. Os efeitos práticos e que
suaviza os bursts. Quando os pacotes têm tamanhos diferentes, a unidade de
Rede: Congestão: Degradação do
contagem deve ser o byte e não o pacote.
desempenho de uma rede quando o Algoritmo do balde de testemunhos (token bucket): “Tirar
número de pacotes é demasiado. água/testemunhos de um balde que se enche a um ritmo constante R”. Pode-se
Problema a lidar no nível transporte e tirar água/testemunhos a qualquer ritmo, enquanto o balde os tem. Se não tem
no nível rede Goodput – rácio de água/testemunhos, apenas se pode tirar ao ritmo R. Existe uma capacidade
pacotes úteis entregues pela rede. máxima de testemunhos B,
Podem existir muitos fatores para que se pode guardar. Para os
pacotes poderem
ocorrer um colapso por congestão:
seguir tem de
• Vários fatores podem contribuir para capturar e destruir
as filas de espera dos encaminhadores encherem: – Linhas de baixa largura de testemunhos que
banda; – Entrada de muitas linhas para uma única linha de saída; – estejam no balde.
Processadores lentos. Deixa passar alguns
• Mexer nos CPUs sem mexer nas linhas, ou mexer numa parte da rede não bursts
altera a situação controladamente, de
modo a melhorar a
• O problema da congestão e que se auto-realimenta: – Se não há memória livre
velocidade face ao
descarta-se o pacote, mas depois há a retransmissão; se o atraso aumenta muito leaky bucket. E se
também pode haver retransmissão; – Mais memória pode contribuir ainda mais B=0? Realizado com
para a congestão. um contador que é incrementado R/ΔT a cada ΔT seg. O contador e
Diferença entre congestão e controlo de fluxo: Congestão – a rede não consegue decrementado o no de bytes do pacote cada vez que é enviado um pacote.
transportar a carga oferecida (Problema global que envolve encaminhadores,
máquinas, etc.). Exemplo: computador produz até 1000Mbps = 125MByte/seg para um TB com
R= 200Mbps =
Controlo de fluxo – tráfego ponto-a-ponto entre um emissor e um recetor (Um 25MByte/seg, com um
emissor rápido não deve inundar um recetor lento). burst inicial com 16000KB
Capacidade da rede 100 Gbps (Supercomputador a transferir 1Gbps para um (=125*1024KB/
computador pessoal); Capacidade da rede 1 Gbps (500 computadores a seg*0,125seg). Se
enviarem 100 Mbps para outros 500). B=12800KByte, então
A melhor maneira de lidar com os 2 problemas é o emissor transmitir mais S= 125mseg.
devagar, por causa do recetor ou da rede …
Abordagens
para controlar Exemplo: computador produz até 125MByte/seg para um TB com R=
a congestão: 25MByte/seg. Se
B=9600KByte, então
S=94mseg.
O suavizador pode
descartar ou reduzir a
Aprovisionamento da rede – bom desenho da rede, adaptado ao tráfego. prioridade dos pacotes
Melhoramentos de linhas e encaminhadores, em zonas muito utilizadas (demora em excesso, que
meses); Encaminhamento considerando o tráfego – definir rotas que evitam excedem a
capacidade do balde.
zonas congestionadas. Rotas multi-caminho ajudam a minorar os problemas;
Controlo de admissão – com circuitos virtuais e possível evitar a congestão
rejeitando ligações; Estrangulamento de tráfego – avisar as fontes para
reduzir o tráfego: – Como identificar a fonte? Monitorizar carga média, filas de
espera, perda de pacotes, etc. – Como informar a fonte? Meio de comunicar com
a fonte, que minimize o tráfego extra. – Quando informar? A cada 2 pacotes? A
cada 30 minutos?
Derramamento de carga – se tudo falha, a rede tem de descartar pacotes.
Encaminhamento considerando o tráfego: Os algoritmos de
encaminhamento estudados focaram principalmente mudanças na topologia –
com custos de linha fixos. Mas podem considerar a carga no custo de linha.
Existe o perigo de instabilidade no encaminhamento quando se considera a
carga. Este perigo não existe se se considerar apenas a largura de banda e o
atraso. Duas técnicas podem contribuir para usar a carga: Encaminhamento
multi-caminho; Métodos de transferência de tráfego lento, de forma a permitir a Abordagens para
convergência. gestão de tráfego e
Na Internet não se ajusta o encaminhamento com a carga – engenharia de congestão – Gestão ativa
tráfego. de filas de espera:
Controlo de admissão: Se houver congestão, e enquanto houver não se Valido para circuitos
aceitam mais circuitos. E simples na rede telefónica; mas e mais complicada virtuais e para
numa rede de dados – o tráfego tem de vir caracterizado (e.g. ritmo e forma). datagramas. Os
Como decidir se aceita tráfego? Numa linha com 100 Mbps aceita-se 10 circuitos encaminhadores têm de
com máximo de 10Mbps? Depende da estatística do tráfego. Pode-se reservar ou saber quando a congestão se aproxima, monitorizando os recursos: Utilização
não os recursos para o circuito (buffers, etc.). O Controlo de admissão pode ser das linhas de saída (- não lida com burstiness); Número de pacotes perdidos por
combinado com o encaminhamento, evitando pontos críticos. falta de espaço no buffer (- deteta demasiado tarde); Atraso dos pacotes na fila
Derramamento de carga: Quando um encaminhador tem pacotes a mais, de espera no encaminhador (+ útil).
descarta-os! Pode fazê-lo aleatoriamente, mas pode ter a política do vinho (mais
antigo melhor) – transferência de ficheiros ou leite (mais recente melhor) –
multimédia. Melhor que isto, só se os emissores cooperarem. Certos pacotes são
mais importantes do que outros (encaminhamento, vídeo). As aplicações podem
marcar os pacotes segundo classes de prioridades. Por que motivo não marcar
tudo com a classe “MUITO IMPORTANTE – NUNCA DESCARTAR”? As classes
podem ter preços diferentes…
Técnicas para gestão de tráfego e obter boa qualidade de
serviço:
Suavização de tráfego (Traffic shaping): Os bursts são uma das maiores
causas de congestão
Tentar que a transmissão dos pacotes seja mais previsível.
Traffic shaping – regular o ritmo medio (e a burstiness) da transmissão. A ideia e
os hosts e a rede concordarem com um certo padrão de tráfego para o circuito.
Se o host cumprir, a rede entrega os dados de um modo pronto. Acordo de nível
de serviço (SLA / Service Level Agreement). Mas como e que a rede pode saber
que o host esta a cumprir aquilo que negociou? A monitorização do fluxo de
tráfego chama-se traffic policing. Importante para dados de tempo real, que tem
Estimativa do atraso, d, a partir do comprimento da fila de espera, s, com uma Antes de se estabelecer a ligação, o emissor da essa estrutura a rede para
EWMA (média aprovação. Aceite; Recusada; Negociada. Depois de haver acordo o recetor e
questionado para saber se concorda.
móvel com pesos exponenciais): d =α d +(1−α )s
new old ; Deteta-se o
Especificação de fluxo: Especificação do padrão de tráfego de um modo preciso
começo da congestão quando d ultrapassa um valor de limiar. Foram propostos usado nos serviços integrados (RFC 2210 e 2211). Define os parâmetros de um
vários métodos, descritos de seguida, para sinalizar a congestão aos emissores. Token Bucket:
Derramamento de carga: Mas lidar com a congestão quando começa e mais ritmo do testemunho – ritmo medio;
eficiente do que deixá-la instalar-se e lidar com o problema. A maioria das parâmetros balde testemunhos – pico
máquinas não recebe informação da congestão dos encaminhadores – apenas máximo de pacotes; tamanho mínimo –
deteta a perda de pacotes. Na Internet, o problema e resolvido pelo protocolo limitações de processamento de pacotes
TCP. Nas ligações sem fios, os erros têm de ser tratados pelo nível lógico. RED (nº pacotes máximo por segundo)
(Random Early Detection / Deteção Precoce Aleatória). O encaminhador mantém tamanho máximo – limitações da MTU da
a média móvel do comprimento da fila de espera se excede um valor de limiar, rede.
uma pequena fração dos pacotes e descartada aleatoriamente. ECN e preferível, O processamento de um pacote ocupa alguns ciclos de CPU. e.g. 1/μ = 1
se estiver disponível – e semelhante exceto que sinaliza a congestão. μseg/pacote = 10^-6 seg/pacote. A capacidade de processamento total do
Estrangulamento de tráfego: Pacotes de estrangulamento (Choke Packets): encaminhador não é μ porque vai haver flutuações na distribuição da carga no
Um encaminhador “saturado” seleciona pacotes aleatoriamente e envia um tempo, originando períodos de inatividade. Teoria das filas de espera (modelo
pacote choke para os emissores, ativando um bit para não gerar mais pacotes M/M/1). Se: a carga tiver um valor medio de λ pacotes/seg e as distribuições do
nos outros encaminhadores. O emissor deve reduzir o ritmo de envio de X%, tempo de processamento e do
ignorar os pacotes choke seguintes durante algum tempo; se não vierem mais intervalo de chegada dos pacotes
nenhuns deve retomar o ritmo. Se vierem deve descer ainda mais. e.g. ICMP foram processos de Poisson. Então
Source Quench na Internet, mas nunca foi muito usado. ECN (Explicit Congestion o tempo médio de espera de um
Notification / Notificação Explicita de Congestão): Transporta informação em bits pacote num encaminhador é:
de cabeçalho dos pacotes IP, em vez de ter outros pacotes. Pacotes são e.g. λ = 950 000 pacotes/seg
marcados se atravessam encaminhador com congestão; o recetor marca os μ = 1 000 000 pacotes/seg T= 20 μ seg.
pacotes de resposta com outro bit. Se forem 6 encaminhadores numa rota …
As técnicas de controlo de congestão procuram minimizar ou evitar a congestão. Método para associar recursos do encaminhador a especificações de fluxos:
Mas não oferecem garantias. Requisitos das aplicações: Necessidades de QoS Fontes de tráfego suavizadas por TB (R, B) e WFQ nos encaminhadores. Um fluxo
para fluxos de dados. com R= 106bps num encaminhador com C=10^9bps requer um peso superior a
1/1000 do total da Σ pesos de todos os fluxos. O número de buffers máximo e
Algoritmos de escalonamento de pacotes: Alocam largura de banda e outros função da duração máxima do pico de carga. O atraso máximo e função do buffer
recursos ao decidirem qual dos pacotes em buffer e enviado para a linha de atingir a capacidade máxima (D ≈ B/R). As garantias são robustas face a carga
saída. noutros feixes? As garantias são robustas face a uma rota que atravessa vários
FIFO (First-In First-Out) ou FCFS (First-Come First-serve): Escalonador mais encaminhadores?
simples – fila única de espera, em que a ordem de saída e igual a ordem de Serviços integrados (intserv): Desde a década de 90 que a IETF leva a cabo
entrada. Tail drop – quando a fila esta cheia, são descartados os novos pacotes; um esforço para desenvolver técnicas para oferecer garantias de qualidade de
RED e uma alternativa quando a fila cresce. serviço, de forma a transportar feixes multimédia (áudio e vídeo). Técnicas de
É bom para QoS? Um fluxo de dados muito intenso pode perturbar todos os reserva adiantada de largura de banda não funcionam, pois, os utilizadores
outros fluxos num encaminhador. podem sair e entrar nos grupos. Os serviços integrados foram desenvolvidos
WFQ (Weighted Fair Queueing / Fila de espera pesada e justa): As filas justas principalmente entre 1995 e 1997 pela IETF. Suportam a reserva de recursos
consistem em ter não uma, mas varias filas (uma por fluxo) para cada linha de baseada em fluxo. São alocados recursos para cada feixe multimédia, em todos
saída, que são servidas por “round robin” (uma de cada vez). Ordem FIFO dentro os encaminhadores atravessados. É usado o protocolo RSVP (Resource
de cada fila de espera. reSerVation Protocol) para reservar recursos.
por pacote – favorece fluxos com pacotes maiores; por byte – e simulado o round RSVP – Resource reSerVation Protocol: O protocolo usa spanning trees. É
robin byte a byte. Calcula-se o tempo virtual de saída de cada pacote, e enviam- atribuído um endereço de grupo a cada grupo, que e usado quando se quer
se os pacotes pela ordem transmitir para esse grupo. O algoritmo normal de multicast forma a spanning
virtual de terminação; Usando pesos distintos para cada fluxo distribuiu-se de tree cobrindo todos os membros do grupo.
forma não uniforme a largura de banda. -O RSVP coloca certa informação que é distribuída periodicamente ao grupo
O (pacote PATH), para dizer aos encaminhadores para manterem certas estruturas
de dados.
-Os recetores podem enviar uma mensagem de reserva (RESV) ao emissor (é
usado o caminho definido por pacotes de controlo (PATH), enviados
periodicamente pelo emissor).
-Cada encaminhador pelo caminho vai reservando largura de banda. Se não
houver suficiente reporta a falha ao emissor.
-Quando a mensagem chega ao emissor foi guardada largura de banda ao longo
da spanning tree.
Quando está a fazer uma reserva, o recetor pode especificar mais do que um
emissor. Se são fixos pela duração da reserva, ou pode mudar (só se partilham
rotas se eles não quiserem mudar) Assim consegue-se que se o recetor mudar de
emissor ainda pode usar parte da reserva que tenha interesse na nova rota.
Com intserv há garantias TOTAIS de não haver falha de QoS?
Serviços diferenciados (diffserv): A abordagem baseada na reserva de
WFQ e geralmente substituído pelo Deficit Round Robin, pois tem características recursos por fluxo não escala para grandes redes, com milhões de feixes ativos.
semelhantes Manutenção de estado em todos os encaminhadores no caminho de um fluxo.
mas tem uma realização muito mais simples. Falhas e complexidade dos encaminhadores. Desenvolvidos a partir de 1997, os
serviços diferenciados suportam a classificação do tráfego em classes,
PRIO (Priority Scheduling / Escalonador com prioridades): Os pacotes com maior
encaminhadas de forma distinta. Os recursos são reservados por classe de
prioridade são sempre enviados antes dos pacotes com menor prioridade. Ordem tráfego e não por feixe. Os serviços diferenciados oferecem uma abordagem mais
FIFO dentro da mesma prioridade. Problemas com um pico de carga de alta simples, com uma realização local aos encaminhadores, sem necessitarem de
prioridade … WFQ pode suportar prioridades usando-se pesos maiores para as informação sobre os feixes ativos. Os pacotes são classificados ao entrar na rede,
linhas de alta prioridade. Permite garantir uma largura de banda mínima para sendo marcados com o código da classe de tráfego no campo Differentiated
tráfego de baixa prioridade. Services (DS) dos cabeçalhos do IPv4 e do IPv6. Os comutadores da rede usam
Escalonador por tempo: Os pacotes carregam o tempo de saída desejado, e são estes campos para realizar o encaminhamento dos pacotes dos fluxos de cada
classe, de acordo com a especificação do nível de serviço. A divisão do tráfego por
transmitidos por essa ordem. Pacotes com atraso são servidos antes de pacotes
classes de tráfego permite atribuir diferentes prioridades ao tráfego,
com avanço no tempo. Vantagens? Complexidade? possivelmente com diferentes tarifários para os utilizadores. É definido um
Controlo de admissão: As garantias de QoS são estabelecidas através do controlo conjunto de tipos de serviço, com regras diferenciadas de encaminhamento.
de admissão: Atualmente estão definidos três tipos de serviço: envio expedito [RFC 3246]; envio
Usar os algoritmos anteriores para reservar recursos e oferecer garantias em assegurado [RFC 2597]; melhor esforço. Cada tipo de serviço pode definir várias
todos os classes de tráfego.
encaminhadores no caminho; A escolha da rota deve considerar a existência de Envio expedito: Pretende oferecer um serviço tipo circuito virtual, com uma
largura de banda garantida, taxa de descarte de pacotes baixa, atraso baixo e
recursos – QoS routing: Melhor caminho  Vários caminhos em paralelo.
jitter baixo. O utilizador contrata uma largura de banda de pico (validada por um
Antes de aceitar uma ligação, um encaminhador tem de saber se tem ou não suavizador de tráfego no encaminhador de entrada, que classifica os pacotes). Os
recursos para ela: encaminhadores suportam uma fila de espera para tráfego expedito, que tem
Não é simples saber os buffers e o CPU necessários para um fluxo (o debito e prioridade face ao restante, dentro da largura de banda reservada para a classe.
mais simples). As aplicações podem querer garantias fortes de QoS, ou tolerar Envio assegurado: Pretende oferecer um serviço em que os pacotes que não
alguns desvios. Algumas aplicações podem ajustar os parâmetros do fluxo (e.g. excedam um ritmo negociado são entregues com elevada prioridade, estando os
imagens por seg. num vídeo). A negociação de um fluxo envolve múltiplas partes restantes sujeitos a prioridades de descarte crescentes, ou mesmo do tráfego de
melhor esforço. O utilizador contrata uma largura de banda correspondente ao
(o emissor, os encaminhadores no caminho, o
ritmo medio, podendo especificar um ritmo de pico. Estão definidas quatro classes
recetor), tendo de ser descritas de uma forma precisa: especificação de fluxo de tráfego (com recursos privados) e três níveis de probabilidade de descarte para
(flow specification) cada classe. Os pacotes são classificados num dos quatro níveis de prioridade no
encaminhador de acesso a rede, ou no emissor. O campo DS do pacote (6 bits) e
marcado com o nível de prioridade correspondente (classe de tráfego). Os pacotes
são passados por um suavizador/descartador que pode marcar com diferentes
probabilidades de descarte os pacotes de forma a obedecer ao ritmo médio
negociado, penalizando os pacotes enviados durante os picos de debito. A
probabilidade de descarte pode ser usando em algoritmos, como o RED.
Melhor Esforço: Corresponde ao serviço já existente, sem quaisquer garantias, que
é selecionado por omissão. Com diffserv há garantias TOTAIS de não haver falha
de QoS?
Internetworking
Constatação: Não existe uma só rede, homogénea, com a mesma pilha de
protocolos em todas as máquinas, mas milhares de PANs, LANs, MANs, WANs,
sistemas proprietários e tipos de máquinas diferentes. Mas, será que estamos
perante uma situação definitiva, de caos, ou é apenas uma situação transitória,
numa mudança para um mundo maravilhoso e único? TCP/IPv4? TCP/IPv6?
OSI? O grande valor de
uma rede está no número
de ligações entre redes. É
necessário ligá-las para
formar uma super-rede
(internet, rede de redes).
e.g. Internet. Vai ser
necessário lidar com os
problemas de
heterogeneidade de
forma a escalar para
grandes dimensões.
Vamos estudar as soluções usadas nas redes IP. Como as redes diferem:
Como as redes podem ser ligadas: Há duas escolhas básicas para ligar redes
distintas na camada rede: Construir componentes (encaminhadores multi-
protocolo) que traduzem e convertem pacotes de cada tipo de rede; Definindo um
nível de protocolo comum a todas as redes, em cima das diferentes redes. Na
Internet, a camada IP funciona como uma camada comum.
Observe-se que o comportamento com encaminhadores é diferente do
comportamento com bridges ou comutadores: Com encaminhadores o pacote é
extraído e a decisão de encaminhamento é baseada no endereço IP; Com
comutadores a trama é retransmitida e a decisão de encaminhamento é baseada
no endereço MAC. O problema de interligação vai-se colocar sempre pois
coexistem vários protocolos IPv4, IPv6, IPX, SNA, AppleTalk, …
– Problema da conversão de endereços entre IPv6 (128 bits) e IPv4 (32 bits);
– Problema de conversão entre redes orientadas à ligação e sem ligação (e.g.
802.11, MPLS).
Os encaminhadores multi-protocolo podem: deixar as ligações para o nível de
cima (e.g. TCP), mas assim, não se suporta tráfego de tempo real; traduzir os
protocolos, o que só resulta para protocolos semelhantes, as bridges também
falharam no objetivo de lidar com redes heterogéneas.
Tunneling: Existe um caso de internetworking bastante mais manejável do que o
caso normal: Quando ambas as redes terminais têm a mesma tecnologia, e são
ligadas por redes de outras. Tecnologias. A rede transportadora é como um
grande túnel. Não existe qualquer interação com esta rede, sendo os
encaminhadores os únicos responsáveis por estabelecer a ligação.
Rede overlay – disposta sobre a rede; no exemplo da figura “IPv6 over IPv4”.
Numa rede privada virtual (VPN – Virtual Private Network), os túneis são usados
para segurança.
Encaminhamento inter-domínio: Semelhante ao caso singular, com a agravante
que os encaminhadores na rede “internet” podem falar diretamente com qualquer
outro encaminhador que esteja ligado ao outro lado das redes a que eles estão
ligados. O encaminhamento da internet complica-se por problemas legais,
económicos, qualidade de serviço, etc. O algoritmo de encaminhamento na
internet tem dois níveis: Intra-domínio (IGP – Interior Gateway Protocol); Inter-
domínio (EGP – Exterior Gateway Protocol). Sistema Autónomo (AS) - Cada rede
que é operada independentemente de todas as outras. A rede de um ISP pode ter
um ou mais ASes...
Cada AS pode correr IGP diferentes, mas todos os ASes correm o mesmo EGP, BGP
(Border Gateway Protocol) no
caso da Internet. No nível de
encaminhamento inter-
domínio, pode-se definir um
grafo para a rede. A partir do
grafo podem-se usar
algoritmos como vetores de
distâncias, ou o caminho mais curto.
O BGP usa vetores de caminhos, um melhoramento face aos vetores de distâncias.
As métricas usadas encapsulam fatores não técnicos (restrições de tráfego legais
ou económicas), vulgarmente designadas de políticas de rotas (routing
policy).
Fragmentação de pacotes: Existem sempre limites para o comprimento máximo
dos pacotes: Hardware (e.g. tamanho da trama Ethernet); Sistema operativo (e.g.
buffers); Protocolo (e.g. número de bits no campo comprimento); Conformidade
com alguma recomendação (inter)nacional; Desejo de reduzir a taxa de erros;
Evitar que um pacote monopolize a rede. O tamanho da MTU (Maximum
Transfer Unit) varia muito: de 48 a 65515 bytes. O que acontece quando se tem
de atravessar uma rede com tamanho de pacotes menor? 1. Evitar passar, por
escolha de encaminhamento - Pode ser impossível (e.g. a rede de destino tem
pacotes máximos ou a rota muda dinamicamente). 2. Fragmentar o pacote - Lidar
com o problema da reconstrução do pacote original.
- Numeração dos pacotes: Objetivo – Identificar fim do pacote e posição do
fragmento no pacote.
Define-se um fragmento elementar (unidade de contagem): e.g. Byte
Fragmentação transparente: Fragmentar e reagrupar em cada rede; Os
encaminhadores têm de saber quando têm todos os pedaços; Só se pode usar um
encaminhador, que realiza uma tarefa mais complexa; Pior desempenho por se
estar sempre a reagrupar.
Fragmentação não-transparente: Fragmentar e reagrupar apenas no recetor. Os
encaminhadores são mais simples e pode usar-se qualquer encaminhador; Todos
os hosts têm de saber reagrupar; O número de pacotes na rede aumenta assim
como a taxa de perda de pacotes (basta 1 frag.).
O débito máximo só é atingível se não houver fragmentação nos
encaminhadores.