Introdução8.1
Hoje você vai ver o que acontece quando a comunicação precisa sair de uma LAN e atravessar vários roteadores até chegar ao destino. Até aqui, estudamos como bits viram quadros, como o meio compartilhado é organizado e como switches encaminham tráfego dentro do enlace local. Agora o problema muda de escala. Já não basta decidir para qual porta um quadro sai. É preciso decidir por quais redes um pacote deve passar.
A camada de rede existe exatamente para isso. Ela cuida da entrega entre redes e precisa resolver duas perguntas centrais. Que serviço ela oferece para as camadas superiores e como ela escolhe o caminho até o destino.
A camada de rede transforma uma coleção de enlaces locais em uma comunicação fim a fim entre redes, e faz isso combinando encaminhamento de pacotes com algoritmos de roteamento.
Quando o problema deixa de ser local8.2
Imagine dois computadores em redes diferentes. O host de origem pode estar em um laboratório, o destino pode estar em outro prédio ou até em outra cidade. Entre eles, há vários roteadores intermediários.
Nesse cenário, o switch local já não resolve o problema completo. Ele sabe encaminhar quadros dentro da LAN observando endereços MAC. Mas o destino final pode estar fora daquela rede local. Alguém precisa olhar para a rede como um todo e decidir qual próximo salto aproxima o pacote do destino. Esse alguém é a camada de rede.
Se o endereço MAC resolve a entrega local no enlace atual, qual informação falta para continuar a viagem quando o destino está em outra rede?
Falta uma visão de caminho entre redes. É por isso que a unidade central desta camada deixa de ser o quadro Ethernet e passa a ser o pacote, que pode atravessar vários enlaces diferentes até chegar ao host correto.
O ambiente da camada de rede8.3
O Tanenbaum descreve a camada de rede como a primeira camada que realmente trata da transmissão de origem até destino. No meio do caminho podem existir vários roteadores, e cada um deles precisa receber um pacote, analisá-lo e encaminhá-lo adiante.
Esse funcionamento é chamado de store-and-forward. O pacote chega a um roteador, é armazenado temporariamente, verificado e só então é reenviado para o próximo salto.
Por que armazenar antes de encaminhar8.3.1
Esse detalhe parece pequeno, mas ele é importante. O roteador não age como um fio transparente que simplesmente repete sinais. Ele precisa receber o pacote de forma suficiente para verificar sua integridade e descobrir o que fazer com ele.
Isso também explica por que a camada de rede trabalha com filas, atrasos e decisões locais de encaminhamento. Cada roteador recebe pacotes de várias entradas, precisa decidir prioridades e então enviá-los pelas saídas adequadas.
Considere o caminho abaixo:
$$ Host\ A \rightarrow R_1 \rightarrow R_2 \rightarrow R_3 \rightarrow Host\ B $$
O pacote não sai de Host A e aparece instantaneamente em Host B. O que acontece é uma sequência de etapas locais.
Host Aentrega o pacote ao roteadorR_1.R_1recebe o pacote, identifica o destino e decide que o próximo salto éR_2.R_2repete o processo e encaminha paraR_3.R_3reconhece que a rede de destino está diretamente acessível e entrega o pacote ao host final.
O ponto importante é que cada roteador toma uma decisão local, mas o efeito combinado dessas decisões produz o caminho completo.
Que serviço a camada de rede oferece8.4
Antes de perguntar como rotear, precisamos perguntar o que exatamente a camada de rede promete à camada de transporte. O livro apresenta essa discussão como uma questão de projeto, e ela é importante porque define o comportamento esperado da rede.
O serviço ideal deve isolar a camada de transporte da tecnologia dos roteadores, da quantidade de roteadores existentes e da topologia interna da rede. Em outras palavras, a camada superior não deveria precisar saber se o caminho tem três ou quinze roteadores, nem se a rede usa um fabricante ou outro.
É aqui que surge a divisão clássica entre duas abordagens. Em uma delas, a rede trata cada pacote de forma independente. Na outra, ela estabelece um caminho lógico antes de começar a transferir os dados. Essas escolhas parecem próximas, mas levam a comportamentos internos bem diferentes.
Serviço não orientado a conexões8.4.1
Nessa abordagem, cada pacote é tratado independentemente. Ele carrega o endereço de destino e os roteadores decidem, pacote a pacote, por onde encaminhá-lo.
Essa é a lógica dos datagramas. A comparação mais comum é com o sistema postal. Cada carta tem o endereço completo e pode seguir um caminho diferente das cartas anteriores.
Serviço orientado a conexões8.4.2
Aqui, a rede estabelece previamente um caminho antes de os dados começarem a fluir. Depois disso, os pacotes seguem o circuito virtual criado.
A comparação clássica é com o sistema telefônico. Primeiro a conexão é estabelecida. Depois o tráfego flui por aquele caminho lógico. Quando a comunicação termina, a conexão é liberada.
A diferença de ideia entre os dois modelos8.4.3
Em vez de decorar nomes, vale observar a mudança de filosofia. No modelo de datagramas, a rede tenta ser simples e flexível. No modelo de circuitos virtuais, a rede assume mais responsabilidade sobre o caminho e o estado da comunicação.
Datagramas e circuitos virtuais por dentro8.5
Agora podemos olhar para a implementação interna dessas duas escolhas.
Rede de datagramas8.5.1
Em uma rede de datagramas, os pacotes são injetados individualmente e roteados de forma independente. Não há configuração antecipada obrigatória. Isso significa que dois pacotes da mesma comunicação podem, em princípio, seguir rotas diferentes.
Esse detalhe é mais importante do que parece. Ele significa que a rede pode reagir a mudanças de topologia ou congestionamento no meio da comunicação.
Imagine que H1 envie quatro pacotes para H2.
- Os pacotes 1, 2 e 3 chegam ao roteador
A. - A tabela de roteamento de
Adiz que o melhor próximo salto éC. - Esses três pacotes seguem por $A \rightarrow C \rightarrow E \rightarrow F$.
- Antes de o pacote 4 chegar,
Adetecta uma condição diferente na rede e atualiza sua tabela. - Agora
Adecide enviar o pacote 4 porB.
Resultado: os quatro pacotes pertencem à mesma comunicação, mas não necessariamente atravessam a mesma rota.
Isso é natural em uma rede de datagramas.
Rede de circuitos virtuais8.5.2
Em uma rede orientada a conexões, o caminho é estabelecido antes do envio dos dados. Cada roteador mantém uma entrada associando o identificador local do circuito à interface de saída correspondente.
Nesse caso, os pacotes não carregam o endereço completo a cada salto da mesma forma que em uma rede de datagramas. Em vez disso, eles carregam um identificador de circuito virtual, e os roteadores usam suas tabelas para trocar esse identificador e encaminhar o pacote corretamente.
Suponha que H1 estabeleça uma conexão com H2.
- O caminho lógico escolhido é $A \rightarrow C \rightarrow E \rightarrow F$.
- O roteador
Aregistra que pacotes da conexão 1 devem sair porC. - O roteador
Cregistra que pacotes dessa conexão devem sair porE. - O roteador
Eregistra que eles devem sair porF. - Enquanto a conexão existir, os pacotes seguem essa mesma rota lógica.
O ganho aqui é previsibilidade. O custo é que a rede precisa manter estado sobre a conexão.
Comparação direta8.5.3
| Aspecto | Datagramas | Circuitos virtuais |
|---|---|---|
| Preparação inicial | Não exige configuração prévia | Exige estabelecimento prévio |
| Estado na rede | Menor | Maior |
| Caminho | Pode variar por pacote | Tende a ficar fixo durante a conexão |
| Reação a mudanças | Mais flexível | Mais dependente do circuito criado |
| Qualidade de serviço | Mais difícil de garantir | Mais fácil de planejar |
Não confunda circuito virtual com circuito físico dedicado. O circuito virtual é lógico. Ele não significa, necessariamente, um fio exclusivo reservado entre origem e destino.
O problema do roteamento8.6
Depois de entender o serviço oferecido pela camada de rede, chega a pergunta principal da aula. Como os roteadores escolhem o caminho?
Essa pergunta é o centro dos algoritmos de roteamento. O objetivo deles é preencher e atualizar as tabelas de roteamento de modo que, quando um pacote chegue, o roteador saiba qual interface de saída usar.
Aqui vale separar duas ideias próximas.
- Encaminhamento é o ato de receber um pacote e enviá-lo para a interface correta.
- Roteamento é o processo de descobrir e manter as rotas que tornam esse encaminhamento possível.
O encaminhamento é a decisão operacional do momento. O roteamento é o cálculo que prepara essa decisão.
Se um roteador só conhece seus vizinhos diretos, como ele pode contribuir para uma rota que depende da topologia inteira da rede?
O princípio de otimização8.7
Antes de estudar algoritmos específicos, o Tanenbaum apresenta uma ideia muito importante chamada princípio de otimização. Ela diz o seguinte.
Se o roteador $J$ está no melhor caminho entre $I$ e $K$, então o melhor caminho de $J$ até $K$ também faz parte dessa mesma rota ótima.
Essa afirmação parece abstrata, mas ela tem uma consequência prática decisiva. Os melhores caminhos até um destino formam uma estrutura em árvore, com raiz no destino. Essa estrutura é chamada árvore de escoamento.
Por que essa ideia ajuda8.7.1
Ela ajuda porque mostra que os caminhos ótimos não são um conjunto aleatório de decisões sem relação entre si. Existe uma estrutura por trás. Os algoritmos de roteamento tentam justamente descobrir essa estrutura.
Roteamento pelo caminho mais curto8.8
O primeiro algoritmo concreto da aula é o roteamento pelo caminho mais curto. A ideia é representar a rede como um grafo. Cada roteador vira um nó, cada enlace vira uma aresta e cada aresta recebe um custo. Esse custo pode representar número de hops, atraso, distância física ou alguma combinação desses fatores. Depois disso, o problema de roteamento vira um problema de grafo: encontrar o caminho de menor custo entre dois nós.
O que significa “mais curto”8.8.1
Mais curto não significa necessariamente “menos quilômetros”. Também não significa sempre “menos roteadores”. Depende da métrica adotada.
Se o custo for o número de hops, o algoritmo favorece caminhos com menos saltos. Se o custo representar atraso, ele pode preferir um caminho com mais saltos, mas mais rápido.
Como o algoritmo de Dijkstra funciona8.8.2
Antes de acompanhar um exemplo maior, vale explicar a mecânica do algoritmo com calma. O Dijkstra não tenta adivinhar a rota final de uma vez. Ele vai construindo a resposta aos poucos, sempre a partir do que já é garantido.
Em cada instante, ele mantém dois grupos de nós. O primeiro grupo contém os nós cujo menor custo já foi confirmado. O segundo grupo contém os nós que ainda têm apenas um custo provisório. Vamos chamar o conjunto dos nós confirmados de $P$.
No início, a origem entra em $P$ com custo zero. Todos os demais começam com custo infinito. A partir daí, o algoritmo segue um ciclo muito regular. Ele olha para todos os nós provisórios, escolhe o de menor custo conhecido, torna esse nó permanente e usa esse novo nó permanente para tentar melhorar os custos dos seus vizinhos.
Essa tentativa de melhorar um caminho é o que normalmente se chama relaxar uma aresta. Relaxar significa comparar o custo que já tínhamos para chegar a um nó com o custo de chegar a ele passando pelo nó recém-fixado. Se o novo caminho for melhor, atualizamos a distância e também o predecessor.
O predecessor é importante porque o algoritmo não quer apenas saber o custo final. Ele também precisa guardar por onde o melhor caminho foi montado. No fim, é seguindo os predecessores de trás para frente que reconstruímos a rota completa.
O coração do algoritmo é este.
- Inicializar a origem com custo zero.
- Marcar todos os demais nós com custo infinito.
- Escolher o nó provisório de menor custo.
- Torná-lo permanente.
- Relaxar as arestas que saem dele.
- Repetir até alcançar o destino ou esgotar os nós.
O motivo de isso funcionar é sutil, mas importante. Quando um nó provisório é o de menor custo entre todos os provisórios, qualquer caminho alternativo até ele necessariamente passaria por um custo que não é menor. Por isso, naquele instante, seu valor pode ser fixado como definitivo.
Vamos começar com um caso pequeno para enxergar os conjuntos sendo preenchidos com clareza.
Queremos sair de $A$ e chegar a $E$.
Passo 0: inicialização8.0.0.1
Começamos pela origem.
$$ P = \{A\} $$
As distâncias ficam assim:
| Nó | Distância | Predecessor | Status |
|---|---|---|---|
| $A$ | $0$ | — | permanente |
| $B$ | $\infty$ | — | provisório |
| $C$ | $\infty$ | — | provisório |
| $D$ | $\infty$ | — | provisório |
| $E$ | $\infty$ | — | provisório |
Agora relaxamos as arestas que saem de $A$.
$$ \begin{aligned} d(B) &= 2 \\ d(C) &= 1 \end{aligned} $$
Isso produz:
| Nó | Distância | Predecessor | Status |
|---|---|---|---|
| $A$ | $0$ | — | permanente |
| $B$ | $2$ | $A$ | provisório |
| $C$ | $1$ | $A$ | provisório |
| $D$ | $\infty$ | — | provisório |
| $E$ | $\infty$ | — | provisório |
Passo 1: escolher o menor provisório8.0.0.2
Entre os provisórios, $C$ tem o menor custo conhecido. Então ele entra no conjunto permanente.
$$ P = \{A, C\} $$
Agora relaxamos as arestas que saem de $C$.
$$ \begin{aligned} d(D) &= \min(\infty, 1 + 5) = 6 \\ d(E) &= \min(\infty, 1 + 2) = 3 \end{aligned} $$
O estado passa a ser:
| Nó | Distância | Predecessor | Status |
|---|---|---|---|
| $A$ | $0$ | — | permanente |
| $B$ | $2$ | $A$ | provisório |
| $C$ | $1$ | $A$ | permanente |
| $D$ | $6$ | $C$ | provisório |
| $E$ | $3$ | $C$ | provisório |
Passo 2: novo menor provisório8.0.0.3
Agora o menor provisório é $B$, com custo 2. Então:
$$ P = \{A, C, B\} $$
Relaxamos a aresta de $B$ para $D$.
$$ d(D) = \min(6, 2 + 3) = 5 $$
O caminho até $D$ melhora, e seu predecessor passa a ser $B$.
| Nó | Distância | Predecessor | Status |
|---|---|---|---|
| $A$ | $0$ | — | permanente |
| $B$ | $2$ | $A$ | permanente |
| $C$ | $1$ | $A$ | permanente |
| $D$ | $5$ | $B$ | provisório |
| $E$ | $3$ | $C$ | provisório |
Passo 3: destino resolvido8.0.0.4
O próximo menor provisório é $E$, com custo 3.
$$ P = \{A, C, B, E\} $$
Como o destino entrou em $P$, o menor custo até ele está confirmado. Para reconstruir a rota, seguimos os predecessores de trás para frente.
$$ E \leftarrow C \leftarrow A $$
Invertendo a ordem, obtemos:
$$ A \rightarrow C \rightarrow E $$
com custo total:
$$ 1 + 2 = 3 $$
Esse exemplo pequeno mostra exatamente o que o algoritmo faz. O conjunto $P$ cresce passo a passo, as distâncias provisórias vão sendo refinadas e os predecessores guardam como o melhor caminho foi construído.
Agora que a mecânica ficou clara em um caso pequeno, vamos aplicar a mesma lógica em um grafo maior.
Queremos sair de $A$ e chegar a $D$.
Passo 18.0.0.1
Começamos marcando $A$ com distância 0.
$$ d(A) = 0 $$
Os demais nós começam com distância infinita.
$$ d(B)=d(C)=d(D)=d(E)=d(F)=d(G)=d(H)=\infty $$
Neste instante,
$$ P = \{A\} $$
Passo 28.0.0.2
Observamos os vizinhos imediatos de $A$.
$$ \begin{aligned} d(B) &= 0 + 2 = 2 \\ d(E) &= 0 + 1 = 1 \end{aligned} $$
Os predecessores registrados aqui são $pred(B)=A$ e $pred(E)=A$. Entre todos os nós provisórios, o menor valor agora é o de $E$. Por isso, ele se torna permanente.
$$ P = \{A, E\} $$
Passo 38.0.0.3
Expandimos a partir de $E$.
$$ \begin{aligned} d(F) &= d(E) + 2 = 1 + 2 = 3 \\ d(G) &= d(E) + 6 = 1 + 6 = 7 \end{aligned} $$
Surgem dois novos caminhos provisórios. O valor de $B$ continua 2 e ainda é o menor entre os provisórios. Por isso, o próximo nó permanente é $B$.
$$ P = \{A, E, B\} $$
Passo 48.0.0.4
Expandimos a partir de $B$.
$$ \begin{aligned} d(C) &= d(B) + 7 = 2 + 7 = 9 \\ d(F) &= \min(3, 2 + 3) = 3 \end{aligned} $$
Perceba o ponto importante. Já existia um caminho até $F$ com custo 3 e predecessor $E$. O caminho passando por $B$ daria 5, então $F$ não é atualizado. Já para $C$, aparece um primeiro caminho viável com custo 9 e predecessor $B$.
Passo 58.0.0.5
O próximo menor valor provisório é o de $F$, com custo 3. Agora expandimos a partir dele.
$$ \begin{aligned} d(C) &= \min(9, 3 + 4) = 7 \\ d(H) &= 3 + 2 = 5 \end{aligned} $$
Agora já temos um caminho melhor para $C$, que troca de predecessor e passa a depender de $F$. Além disso, surge um primeiro caminho para $H$, também com predecessor $F$.
$$ P = \{A, E, B, F\} $$
Passo 68.0.0.6
O próximo menor valor provisório é o de $H$, com custo 5. Expandimos a partir dele.
$$ \begin{aligned} d(D) &= 5 + 2 = 7 \\ d(G) &= \min(7, 5 + 1) = 6 \end{aligned} $$
Neste ponto, o destino $D$ aparece com custo 7 e predecessor $H$. Ao mesmo tempo, $G$ melhora de 7 para 6 e passa a depender de $H$.
$$ P = \{A, E, B, F, H\} $$
Passo 78.0.0.7
Como não existe nenhum caminho provisório menor que 7 para chegar a $D$, o custo ótimo foi encontrado.
Reconstruindo os predecessores, obtemos:
$$ A \rightarrow E \rightarrow F \rightarrow H \rightarrow D $$
com custo total:
$$ 1 + 2 + 2 + 2 = 7 $$
Neste caso maior, a lógica é a mesma do exemplo pequeno. O conjunto permanente cresce, os custos provisórios são revisados e os predecessores guardam a trilha do melhor caminho até o destino.
Flooding8.9
O próximo algoritmo parece, à primeira vista, exagerado. No flooding, cada pacote recebido é reenviado por todas as interfaces de saída, exceto por aquela de onde ele veio.
Essa técnica não é eficiente para o tráfego comum porque gera muitas cópias. Mesmo assim, ela é importante didaticamente por dois motivos. Primeiro, porque mostra uma forma extremamente robusta de espalhar informação. Segundo, porque ajuda a entender a necessidade de mecanismos para conter duplicação.
Por que o flooding funciona8.9.1
Ele funciona porque não depende de uma visão sofisticada da topologia. Se existir caminho até o destino, a inundação tende a alcançá-lo.
O que precisa impedir o caos8.9.2
Se não houver controle, o flooding produz cópias sem fim. Por isso, normalmente se combinam duas ideias. A primeira é limitar a vida útil do pacote com um contador de hops ou um campo TTL. A segunda é identificar o pacote com informações como origem e número de sequência. Assim, o roteador consegue reconhecer cópias repetidas e impedir que a inundação se transforme em circulação infinita.
Suponha que A envie um pacote para D e que a rede tenha três caminhos possíveis.
Aenvia o pacote aos seus vizinhos.- Cada vizinho o reenviará aos próximos, exceto para a interface de entrada.
- O destino
Dpode receber várias cópias. - O roteador ou host precisa aceitar uma cópia válida e ignorar as demais.
O flooding é ruim como rotina de tráfego normal, mas é excelente para perceber a diferença entre robustez e eficiência.
Roteamento por vetor de distância8.10
Agora entramos no primeiro algoritmo distribuído importante da aula. No roteamento por vetor de distância, cada roteador mantém uma tabela dizendo qual é a melhor distância conhecida até cada destino e por qual vizinho esse destino deve ser alcançado.
Em vez de cada roteador conhecer a topologia completa, ele troca estimativas com seus vizinhos. A partir dessas trocas, vai refinando sua própria tabela.
A lógica básica8.10.1
Se o roteador $J$ quer saber a melhor rota até um destino $X$, ele não enxerga a rede inteira. Então ele olha para os vizinhos imediatos e usa as estimativas que cada um anuncia. Em outras palavras, $J$ pergunta assim: "se eu entregar o pacote para este vizinho, quanto ele acha que ainda falta para chegar ao destino?".
Se um vizinho $V$ diz que chega a $X$ com custo 5, e $J$ sabe que o custo até $V$ é 2, então passar por $V$ gera um custo total 7.
Formalmente, a atualização segue a ideia:
$$ d_J(X) = \min_V \{ c(J,V) + d_V(X) \} $$
Essa fórmula pode ser lida assim:
- $d_J(X)$ é a melhor distância que o roteador $J$ conhece até o destino $X$
- $V$ representa um vizinho possível de $J$
- $c(J,V)$ é o custo para sair de $J$ e chegar ao vizinho $V$
- $d_V(X)$ é a distância que o vizinho $V$ anuncia até o destino $X$
- $\min_V$ significa que $J$ testa todos os vizinhos e fica com o menor valor encontrado
Portanto, o vetor de distância funciona somando duas partes.
- quanto custa sair de $J$ até um vizinho $V$
- quanto esse vizinho diz que ainda falta para chegar em $X$
Depois, $J$ compara os resultados e escolhe a menor soma.
Considere que o roteador $J$ tenha três vizinhos e queira calcular a melhor rota até o destino $G$.
Os custos locais são:
$$ \begin{aligned} c(J,A) &= 8 \\ c(J,I) &= 10 \\ c(J,H) &= 12 \end{aligned} $$
Os vizinhos anunciam as seguintes distâncias até $G$:
$$ \begin{aligned} d_A(G) &= 18 \\ d_I(G) &= 31 \\ d_H(G) &= 6 \end{aligned} $$
Então $J$ calcula:
$$ \begin{aligned} \text{via } A &: 8 + 18 = 26 \\ \text{via } I &: 10 + 31 = 41 \\ \text{via } H &: 12 + 6 = 18 \end{aligned} $$
O menor valor é 18. Logo, $J$ registra que o melhor caminho até $G$ passa por $H$.
O problema da contagem ao infinito8.10.2
O grande problema do vetor de distância aparece quando uma rota deixa de existir. As boas notícias se espalham rápido. As más notícias podem se espalhar muito devagar.
Considere novamente a linha:
$$ A - B - C - D $$
Inicialmente, todos sabem chegar a A.
$$ \begin{aligned} d_B(A) &= 1 \\ d_C(A) &= 2 \\ d_D(A) &= 3 \end{aligned} $$
Agora o enlace entre A e B falha.
Primeira reação8.0.0.1
B deixa de ver A, mas ouve C dizendo que ainda alcança A em 2 hops. Então B conclui:
$$ d_B(A) = 3 $$
Próxima rodada8.0.0.2
C ouve B dizendo que chega a A em 3 hops e conclui:
$$ d_C(A) = 4 $$
Rodadas seguintes8.0.0.3
Os valores continuam aumentando.
$$ 3, 4, 5, 6, \dots $$
Cada roteador acredita que o outro tem um caminho válido, e o erro vai crescendo até atingir o valor considerado infinito.
Esse é o problema da contagem ao infinito.
O problema do vetor de distância não é “fazer conta errada”. O problema é de informação incompleta. Cada roteador só enxerga o que os vizinhos anunciam e, por isso, pode acreditar em uma rota que na prática já não existe mais.
Questões8.11
1. Explique, com suas palavras, por que a camada de rede se torna necessária quando a comunicação precisa atravessar vários roteadores.
2. O que significa dizer que a transmissão na camada de rede é do tipo store-and-forward?
3. Diferencie encaminhamento e roteamento.
4. Diferencie serviço não orientado a conexões e serviço orientado a conexões na camada de rede.
5. Explique a diferença entre rede de datagramas e rede de circuitos virtuais.
6. Por que se diz que, em uma rede de datagramas, dois pacotes da mesma comunicação podem seguir rotas diferentes?
7. O que afirma o princípio de otimização e por que ele é útil no estudo de roteamento?
8. Em um algoritmo de caminho mais curto, o que significa dizer que um nó se tornou permanente?
9. Considere o trecho abaixo e calcule o custo total do caminho:
$$ A \rightarrow E \rightarrow F \rightarrow H \rightarrow D $$
com custos:
$$ AE = 1,\ EF = 2,\ FH = 2,\ HD = 2 $$
10. Explique por que o flooding é robusto, mas ineficiente.
11. Para que servem o contador de hops ou o TTL em um esquema de flooding?
12. No roteamento por vetor de distância, o que cada roteador mantém em sua tabela sobre cada destino?
13. No vetor de distância, se o custo até o vizinho $V$ é 3 e $V$ anuncia distância 4 até o destino $X$, qual custo total o roteador calculará para chegar a $X$ por $V$?
14. Explique o problema da contagem ao infinito.
15. Liste, na ordem correta, as cinco etapas do roteamento de estado de enlace.
16. Por que o estado de enlace costuma convergir melhor do que o vetor de distância?
17. Marque V ou F.
- ( ) Em circuitos virtuais, a rede precisa manter algum estado sobre a conexão.
- ( ) No flooding, um pacote deve ser reenviado também pela mesma interface por onde entrou.
- ( ) No vetor de distância, o roteador precisa conhecer a topologia completa da rede.
- ( ) No estado de enlace, cada roteador pode reconstruir o grafo da rede e depois executar Dijkstra localmente.
1. Porque a entrega deixa de ser apenas local. Quando o destino está em outra rede, é preciso decidir por quais roteadores e enlaces o pacote seguirá.
2. Significa que cada roteador recebe e armazena temporariamente o pacote, verifica o que precisa e só então o encaminha ao próximo salto.
3. Encaminhamento é a decisão operacional de enviar um pacote pela interface correta. Roteamento é o processo de calcular e manter as rotas que permitem esse encaminhamento.
4. No serviço não orientado a conexões, cada pacote é tratado independentemente. No orientado a conexões, um caminho lógico é estabelecido antes do envio dos dados.
5. Em datagramas, os pacotes são roteados independentemente e podem seguir caminhos diferentes. Em circuitos virtuais, a rede estabelece uma rota lógica e mantém estado para a conexão.
6. Porque a decisão de rota pode ser tomada pacote a pacote, de acordo com a tabela vigente no instante em que cada pacote chega ao roteador.
7. Ele afirma que, se um roteador está no melhor caminho entre dois outros, então o melhor caminho a partir dele até o destino também pertence a essa rota ótima. Isso ajuda a justificar a ideia de árvore de escoamento.
8. Significa que o menor custo até esse nó já foi determinado de forma definitiva dentro da execução do algoritmo.
9.
$$ 1 + 2 + 2 + 2 = 7 $$
10. Porque ele espalha o pacote por muitos caminhos e tende a alcançar o destino se houver caminho disponível, mas gera muitas cópias e desperdiça largura de banda.
11. Eles limitam a propagação das cópias e evitam que o flooding continue indefinidamente.
12. A melhor distância conhecida até o destino e o vizinho ou enlace preferido para alcançá-lo.
13.
$$ 3 + 4 = 7 $$
14. É o problema em que más notícias sobre a perda de uma rota se propagam lentamente, fazendo os roteadores aumentarem gradualmente os custos anunciados até chegar ao valor considerado infinito.
15. Descobrir os vizinhos, medir o custo até cada vizinho, montar o pacote de estado de enlace, distribuir esse pacote para todos os roteadores e calcular os menores caminhos.
16. Porque cada roteador passa a reconstruir a topologia da rede e calcular localmente as rotas, em vez de depender apenas das estimativas anunciadas pelos vizinhos.
17.
- ( V ) Em circuitos virtuais, a rede precisa manter algum estado sobre a conexão.
- ( F ) No flooding, um pacote deve ser reenviado também pela mesma interface por onde entrou.
- ( F ) No vetor de distância, o roteador precisa conhecer a topologia completa da rede.
- ( V ) No estado de enlace, cada roteador pode reconstruir o grafo da rede e depois executar Dijkstra localmente.
Próximos passos8.12
Na próxima aula, o passo natural é sair da lógica geral da camada de rede e entrar no protocolo que domina a Internet.
Você verá como o IP organiza endereçamento, formato de pacotes e interligação de redes, e como essas ideias concretizam na prática a camada de rede estudada hoje.