CCT0008_10

Prévia do material em texto

REDES DE COMPUTADORES - CCT0008
Semana Aula: 10
Roteamento: Algoritmos e Protocolos
Tema
Roteamento: Algoritmos e Protocolos
Palavras-chave
Objetivos
O aluno deverá ser capaz de:
 Explicar o conceito de tabelas de rotas;
 Comparar protocolos de roteamento estático e dinâmico;
 Diferenciar os tipos de protocolos de roteamento dinâmico;
 Interpretar como um pacote é transmitido, entre origem e destino, através das redes de 
computadores.
Estrutura de Conteúdo
Unidade 7 Roteamento: Algoritmos e Protocolos 
7.1. Fundamentos e Conceitos de Roteamento
7.2. Protocolo roteável e não roteável
7.3. Protocolos Roteamento estático x dinâmico
7.4. Cálculos de redes, sub-redes e super-redes
 
Os temas desta aula são fundamentais para compreendermos como uma informação pode ?fluir? por uma 
rede de computadores e não se perder. Brincadeiras a parte, a transmissão de dados através de uma 
intrincada rede como a internet, ou mesmo uma rede local de grandes dimensões, de forma a que essa 
transmissão seja bem sucedida, não é algo fácil de fazer;
No entanto, algoritmos de roteamento e os protocolos de roteamento que os utilizam são as maneiras de 
garantir essa transmissão;
Nesta aula, entenderemos o conceito de algoritmos e o funcionamento básico dos protocolos de 
roteamento. Porém, maiores detalhes sobre técnicas de roteamento serão estudadas em futuramente.
 
 
Suporte conceitual:
 
Unidade 7 - Roteamento: Algoritmos e Protocolos 
 
Roteamento
Normalmente uma máquina está ligada diretamente a um roteador, também chamado de roteador default 
ou roteador do primeiro salto. Sempre que uma máquina emitir um pacote, o pacote será transferido para 
seu roteador default e posteriormente para o roteador destino. 
Caso uma máquina de de uma LAN de São Paulo deseje transmitir uma mensagem para uma máquina 
numa LAN do Rio de Janeiro, a máquina de origem deverá primeiro enviar o pacote para o seu roteador 
default.
 
Temos aqui uma consideração, se houvesse um canal exclusivo para esta comunicação RJ ? SP não 
haveria necessidade de explorar a camada de rede. Conforme vimos na aula de enlaces: dentro de um 
domínio de broadcast a identificação de um host é feita exclusivamente pelo se endereço MAC (endereço 
de enlace). 
Numa situação destas o custo do estabelecimento e manutenção do canal é extremamente alto. A maioria 
das organizações emprega este canal exclusivo até um ISP em sua cidade e deixa a ligação entre cidades 
ocorrer na ?nuvem? da internet, como os canais são compartilhados é necessário um nível acima para o 
endereçamento, os pacotes IP.
 
Nosso foco de estudo será compreender como o roteador de origem transfere um pacote até o roteador de 
destino, já que a máquina destino também está diretamente ligada a um roteador, que neste caso é 
denominado de roteador destino. 
 
Para que um roteador seja capaz de realizar a transferência dos dados recebidos, ele precisa que algumas 
perguntas sejam respondidas: 
 
 Para onde vai o pacote?
 Como chegar lá?
 Qual o melhor caminho?
 
O endereço de destino recebido da origem diz ao roteador para onde o tráfego vai. Além desta informação 
ele irá precisar saber qual a direção, ou seja, o caminho a ser seguido. O melhor caminho ao destino deve 
ser determinado para que o roteador possa encaminhar os pacotes eficazmente. E neste caso os outros 
roteadores da rede podem providenciar esta resposta. Quanto mais nova for a informação melhor será o 
resultado final.
Portanto a finalidade de um do roteamento é simples: dado um conjunto de roteadores conectados por 
enlaces, um algoritmo de roteamento descobre um ?bom caminho? entre o roteador de origem e o roteador 
de destino. 
 
Como saber o que é um "bom caminho"?
Normalmente um "bom caminho" é aquele que tem o "menor custo". Por exemplo, dado que a rede de 
origem 172.20.0.0/23 (X) deseja transmitir pacotes para a rede destino 172.30.0.0/23 (Y), existem muitos 
caminhos entre as duas redes, e cada caminho tem um custo. Um ou mais destes caminhos podem ser um 
caminho de menor custo. 
 
Os custos relacionados a um caminho são representados:
- pelo tamanho físico do enlace 
- a velocidade ou 
- o custo monetário associado a este enlace.
 
7.1. Fundamentos e Conceitos de Roteamento
Segundo Kurose, os algoritmos de roteamento podem ser classificados de três maneiras:
 Algoritmo de roteamento global ou descentralizado;
 Algoritmo de roteamento estáticos ou dinâmico;
 Algoritmo de roteamento sensível à carga ou insensível á carga;
 
Algoritmo de roteamento global;
Os algoritmos de roteamento global calculam o caminho de menor custo entre a origem e um destino 
usando o conhecimento completo e global sobre a rede. Em outras palavras, o algoritmo considera como 
dados de cálculo a conectividade entre todos os nós e todos os custos dos enlaces. 
Isso exige que o algoritmo obtenha essas informações, de algum modo, antes de realmente realizar o 
cálculo. O cálculo em si pode ser executado em um local ou duplicado em vários locais. 
Estes tipos de algoritmos são frequentemente denominados de algoritmos de estado de enlace (link-state ? 
LS) 
Em um algoritmo de estado de enlace a topologia da rede e todos os custos de enlace são conhecidos, isto 
é, estão disponíveis como dados para o algoritmo de estado de enlace. Isto ocorre fazendo com que cada 
nó transmita pacotes de estado de enlace a todos os outros nós da rede, sendo que cada um destes 
pacotes contém as identidades e os custos dos enlaces ligados a ele.
 
Algoritmo de roteamento descentralizado;
No algoritmo de roteamento descentralizado, o cálculo do caminho de menor custo é realizado de modo 
interativo e distribuído. Nenhum nó tem informação completa sobre os custos de todos os enlaces da rede. 
Em vez disso, cada nó começa sabendo apenas os custos dos enlaces diretamente ligados a ele. 
Então por meio de um processo iterativo de cálculo e de troca de informações com seus nós vizinhos (nós 
que estão na outra extremidade dos enlaces aos quais ele próprio está ligado), um nó gradualmente calcula 
o caminho de menor custo até um destino ou um conjunto de destinos. 
Um exemplo de algoritmo de roteamento descentralizado é o algoritmo de vetor de distâncias (distance-
vector algorithm ? DV) porque cada nó mantém um vetor de estimativas de roteamento descrentralizados 
de custos (distâncias) de um nó até todos os outros nós da rede. 
Em um algoritmo de vetor de distância, cada nó recebe alguma informação de um ou mais vizinhos 
diretamente ligados a ele, realiza cálculos e em seguida distribui os resultados de seus cálculos para seus 
vizinhos. Este processo é repetido até que não nenhuma informação seja trocada entre vizinhos. 
 
Algoritmo de roteamento sensível à carga e insensível à carga
Os algoritmos de roteamento sensíveis à carga os custos de enlace variam dinamicamente para refletir o 
nível corrente de congestionamento no enlace subjacente. Caso haja um alto custo associado ao enlace 
congestionado, o algoritmo tenderá a escolher rotas que evitem esse enlace congestionado. Já os 
algoritmos de roteamento insensíveis à carga, atualmente utilizado na internet (RIP, OSPF e BGP) não 
levam em consideração o custo, pois o custo de um enlace não reflete explicitamente seu nível de 
congestionamento corrente. 
 
Protocolos de Roteamento
Um protocolo de roteamento é um protocolo utilizado para trocar informações entre computadores, de modo 
a permitir que eles montem e mantenham suas tabelas de roteamento. Quando novos caminhos são 
acrescentados ou quando os caminhos estão obstruídos e não podem ser utilizados são enviados 
mensagens entre computadores utilizando o protocolo de roteamento.
 
Roteamento na Internet
A Internet, na prática não é constituída de um conjunto homogêneo de roteadores,todos rodando o mesmo 
algoritmo de roteamento. Ela é constituída de várias redes interconectadas, onde cada organização pode 
executar o algoritmo de roteamento que desejar ou ainda, ocultar do público externo aspectos internos de 
rede da organização. Como forma de minimizar a complexidade da gestão administrativa e de autonomia 
destas redes, os roteadores foram agrupados formando um sistema autônomos (AS) com cada AS 
consistindo de um grupo de roteadores sob o mesmo controle administrativo, isto é , operado pelo mesmo 
ISP ou pertencente a uma mesma rede corporativa.
 
Em um Sistema Autônomo (AS) o algoritmo de roteamento que roda dentro do AS é denominado protocolo 
de roteamento intra-AS e ao conectarmos vários ASs entre si, um ou mais roteadores em um As terá a 
tarefa adicional de ficar responsável por transmitir pacotes a destinos externos ao AS. Este roteadores são 
denominados de roteadores de borda (gateway routers). 
 
Um outro ponto a observarmos é que ao ligarmos vários ASs entre si, será necessário obter informações 
sobre as condições de alcance dos As vizinhos e propagar estas informações entre todos os roteadores 
internos ao As. Estas ações são realizadas através do protocolo de roteamento inter-AS. Desta forma para 
que dois As troquem informações é necessário que estes dois As executem o mesmo protocolo de 
roteamento Inter-AS. 
 
Protocolo de roteamento intra-AS
Um protocolo de roteamento intra-AS é usado para determinar como é executado o roteamento dentro de 
im sistema Autônomo (AS). Os protocolos de roteamento intra-AS são também conhecidos como 
protocolos de roteadores internos (IGP):
- RIP (Routing Information Protocol): protocolo de roteamento dinâmico que utiliza algoritmo de vetr de 
distância. Geralmente é utilizado em redes menores.
- OSPF (Open shortest path first): protocolo de roteamento dinâmico que utiliza algoritmo de estado de 
enlace. Geralmente é utilizado na internet. É mais eficiente que o RIP.
- IS-IS (Internediate System to Intermediate System) protocolo de roteamento dinâmico que utiliza 
algoritmo de estado de enlace. Geralmente é utilizado em redes de grande porte.
- EIGRP (Enhanced Interior Gateway Routing Protocol) : protocolo de roteamento dinâmico que utiliza 
algoritmo de estado de enlace. Foi desenvolvido pela Cisco. 
 
Protocolo de roteamento Inter-AS
O protocolo de roteamento inter-AS é responsável pela determinação dos caminhos entre origem e destino 
que abrangem vários ASs. Atualmente o protocolo utilizado na Internet é o BGP (Border Gateway Protocol). 
O BGP é um protocolo de roteamento dinâmico que utiliza vetor à distância, para trocar informações de 
roteamento entre os sistemas autônomos. 
 
7.2. Protocolo roteável e não roteável
A expressão Protocolos não roteável se refere a pilhas de protocolos que não dão suporte ao roteamento 
por não implementarem mecanismos de endereçamento na camada de rede. Entre estas podemos citar o 
NetBEUI que permite a comunicação apenas dentro de um domínio de broadcast.
Outras pilhas de protocolos como TCP/IP e IPX/SPX podem ser roteados por possuírem suporte a 
endereçamento na camada de rede.
7.3. Protocolos Roteamento estático x dinâmico
Algoritmo de roteamento estático
Em algoritmos de roteamento estático, as rotas mudam muito lentamente o longo do tempo, muitas vezes 
como resultado de intervenção humana através da configuração manual de uma rota. Neste tipo de 
algoritmo todos os computadores ou roteadores na rede tomam suas próprias decisões de roteamento 
seguindo um protocolo formal de roteamento. Em MANs e WANs a tabela de roteamento para cada 
computador é desenvolvida individualmente pelo seu administrador de rede.
 
Algoritmo de roteamento dinâmico
Os algoritmos de roteamento dinâmico mudam os caminhos de roteamento à medida que mudam as cargas 
dos tráfegos ou a topologia de rede. Um algoritmo dinâmico pode ser rodado periodicamente ou como 
reação direta à mudança de topologia de rede ou de custos dos enlaces. Ao mesmo tempo em que são 
mais sensíveis às mudanças na rede, os algoritmos dinâmicos também são mais suscetíveis a problemas 
como loops de roteamento e oscilação de rotas. 
 
7.4. Cálculos de redes, sub-redes e super-redes
Exercício de fixação.
Estratégias de Aprendizagem
Indicação de Leitura Específica
Aplicação: articulação teoria e prática
Propor uma topologia de rede no simulador, convidar os alunos a escolher e configurar o roteamento. 
Preparar o arquivo do simulador com o roteamento escolhido, bem como relatório com a justificativa técnica 
para a escolha.
Considerações Adicionais
Na ausência de um simulador, propor duas topologias de redes, onde em uma a melhor opção seja 
roteamento estático e, na outra, a melhor opção seja o roteamento dinâmico. Solicitar um relatório aos 
alunos para que definam o melhor tipo de roteamento para as topologias apresentadas, com as respectivas 
justificativas técnicas.