Redes Integradas de Telecomunicações I
Mestrado Integrado em Engenharia Electrotécnica e Computadores
Luis Bernardo
Problemas para a aula de 12 de Outubro de 2015
1. Admita que para a rede representada à direita é utilizado o algoritmo de estado
5
15
1
de linha para gerar as tabelas de encaminhamento. A rede é constituída por
A
B
U1
U2
quatro encaminhadores (A-D) e três redes passivas (U1-U3).
1
8
3
5
a) Calcule a tabela de encaminhamento para o encaminhador A, aplicando o
1
algoritmo de Dijkstra. Justifique a sua resposta apresentando todos os passos
2
1
intermédios.
C
D
U3
b) Qual seria o valor de TTL mínimo que teria de usar no processo de difusão dos
pacotes para garantir o correcto funcionamento do algoritmo de estado de
linha? Justifique a sua resposta, admitindo que o período de envio é de 30 unidades de tempo.
c) Imagine agora que a rede representada faz parte de uma rede de redes (internet), e pretende que qualquer nó possa
comunicar com todos os outros nós. O encaminhador A também corre o protocolo de estado de linha a nível da
internet, tendo como vizinhos (na internet) os encaminhadores R1 e R2. Quantas entradas tem o pacote com o
estado de linha de A inundado nos encaminhadores da internet, e quais são os destinos contidos nesse pacote?
Como é que o encaminhador B pode ficar a conhecer as rotas recebidas por A a partir do protocolo de
encaminhamento na internet?
2. Na rede representada ao lado é usado o algoritmo de estado de linha para realizar o encaminhamento. Na
distribuição dos pacotes de estado de linha, cada nó retém os pacotes recebidos durante 4
3
B
segundos antes de os enviar para o próximo nó, correspondendo o atraso em segundos em A
1
1
8
cada linha ao valor da distância representada no grafo. Calcule quais vão ser os pacotes
1
efectivamente enviados durante a disseminação do estado de linha de A por todos os
outros encaminhadores. Indique em que instante é que cada nó recebe o estado de linha C
5
D 3
E
de A, quando é que cada um dos nós envia o estado de linha, e por que linhas. Justifique
a sua resposta.
3. Considere que é usado um protocolo de vectores de distâncias (com separação de
horizontes) para realizar o encaminhamento dinâmico na rede representada na figura ao
lado, e que a rede está estável.
a) Qual é o conteúdo dos vectores de distâncias que o nó B envia para os vizinhos?
b) Admita que falha uma das cinco ligações na rede. Será que vai haver problemas de
convergência para infinito? O que se poderia fazer para garantir que não há problemas
de convergência para infinito?
1
A
1
B
1
C
5
2
1
8
1
3
3
D
E
4. Admita que se usa o algoritmo de vector de distâncias para calcular as tabelas de encaminhamento para a rede
representada à direita. No instante 0 são ligados todos os encaminhadores, que
A
C
1 B
2
começam a trocar mensagens de controlo sincronizadamente, em instantes
1
1
1
5
múltiplos de T. Ao fim de quanto tempo é que o encaminhador A conhece toda a
1
4
1
8
2
1
rede? Justifique a sua resposta, descrevendo qual é a dimensão do vector enviado
1
2
pelo encaminhador A em cada instante, começando do instante 0 (quando é
1
F
D
E 1
ligado) até ao nT onde o encaminhador A conhece a totalidade da rede.
5. O algoritmo de estado de linha também pode ser usado para realizar encaminhamento
multicast. O que é necessário calcular e memorizar em cada encaminhador para suportar
encaminhamento multicast? Justifique, exemplificando para a rede representada ao lado, e
admitindo que existem três endereços de grupo: α (com os nós A, B e C), β (com os nós D
e E) e γ (com os nós D, C e E). Não se pretende que realize os cálculos.
6. Pretende-se realizar difusão de pacotes na rede representada ao lado para um grupo G
composto pelos nós A, B, e D. Será que era possível usar encaminhamento inverso com
poda de ramos (reverse path forwarding com prunning) para criar a tabela de
encaminhamento nos nós? Caso seja usado o algoritmo de estado de linha para realizar o
encaminhamento unicast, qual seria o algoritmo mais eficiente para criar as tabelas de
encaminhamento? Justifique detalhadamente a sua resposta.
3
A
1
B
1
8
1
5
C
3
A
1
3
D
E
B
1
8
1
C
5
D
3
E