O Nível Rede: Introdução Tipos de algoritmos de encaminhamento

Preocupa-se em “levar pacotes da origem para o destino” Algoritmos não adaptativos

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