2 Noçoes de Algoritmos

Prévia do material em texto

�������������	
����
�������	�������������������������������������������������������	� !"��#����$�
	
�%����
��"�&"!���'
 !���()�����)�(*�"����
Revisão: 
 O equipamento que tem a função de realizar o roteamento é o ROTEADOR, que tem como função a utilizsua tarefa é encaminhar 
datagramas IP (IP forward) da origem até o destino passando por diversas redes através de nós intermediários(roteadores 
intermediários). 
Exemplo: 
 Rede 200.1.1.0/24, elipse laranja; 
 Rede 200.2.2.0/24, elipse verde; 
 Nuvem amarela representa a INTERNET; 
 
Quando o host 200.1.1.1 deseja enviar uma informação dentro de um datagrama IP para o host de destino 200.2.2.1, ocorre o seguinte 
passo-a-passo: 
1- o host 200.1.1.1, pertence à rede 200.1.1.0, necessita se comunicar com um host 200.2.2.1, pertencente a outra rede (200.2.2.0); 
2- como o destino não se encontra na mesma rede, necessita encaminhar o datagrama IP( pacote IP) ao equipamento que o interliga a 
outras redes, nesse caso o roteador A, conhecido como DEFAULT GATEWAY ou ROTEADOR DEFAULT etc. Resumindo o default gateway 
da 200.1.1.0/24 é o roteador A.Os endereços IP do datagrama são mantidos, tanto a origem host 200.1.1.1, quanto o destino host 
200.2.2.1, 
3- o roteador A ao receber o datagrama IP através da interface de entrada, vai analisar sua tabela de rotas, tomar uma decisão de 
roteamento e encaminhar para o roteador B, realizando sua tarefa que é o roteamento de datagramas IP ou pacotes IP. Ecaminha o 
datagrama IP para o próximo salto ou próximo roteador até que o datagrama IP chegue a seu destino (200.2.2.1); 
4- o roteador B da mesma forma, vai analisar sua tabela de rotas e encaminhar o datagrama IP para o roteador D; 
5- o roteador D por sua vez, vai analisar sua tabela de rotas e encaminhar o datagrama IP para o roteador E; 
6- o roteador E também vai analisar sua tabela de rotas e encaminhar o datagrama IP para o roteador F; 
7- o roteador F verifica que uma de suas interfaces se encontra na rede 200.2.2.0/24 entregando o datagrama ao 200.2.2.1. 
 
Decisão de roteamento: 
 O datagrama IP entra por uma interface do roteador, com base no ENDEREÇO IP DE DESTINO, define por qual interface de saída o 
datagrama IP deverá seguir viagem para alcançar seu destino. Esse ato de entrar por uma interface, tomar a decisão de roteamento e 
sair por outra interface também pode ser dito repasse entre as interfaces de entrada e saída. 
 
 
 
Roteamento estático X roteamento dinâmico 
 
Para manter as informações para essa decisão de roteamento podemos realizar de 2 formas distintas, Roteamento estático e 
roteamento dinâmico. 
 
Roteamento estático Roteamento dinâmico 
O administrador insere as rotas manualmente 
Os roteadores utilizam protocolos de roteamento para 
realizarem troca de mensagens e definirem suas tabelas de 
roteamento. 
Ideal para redes que sofrem poucas mudanças ou possuam 
um único caminho de saída para o mundo (INTERNET) 
Ideal para redes que podem sofrer mudanças e 
principalmente que possuam caminhos redundantes 
(ex: olhe a figura, para chegar ao destino 200.2.2.0/24 o 
roteador B poderia ter encaminhado através do roteador C 
ou D) 
Em caso de mudanças necessita da interferência do 
administrador 
Em caso de mudanças interage com os roteadores e atualiza 
suas tabelas de roteamento baseado em seu protocolo de 
roteamento 
 
 
Para o roteamento dinâmico existem, basicamente, 2 algoritmos de roteamento Estado de enlace (link state) e Vetor de distâncias 
(distance Vector). 
 A grande diferença do algoritmo estado de enlace é que todos os roteadores possuem informação de todos os roteadores que estão na 
mesma área que ele, ou seja, informação do estado de todos os enlaces de todos os roteadores da mesma área ou região. Já o vetor de 
distância, só possui o conhecimento da rede baseado na informação passada por seu vizinho, exemplo, o roteador A não sabe o 
caminho, por quais roteadores o datagrama passará até chegar à rede 200.2.2.0/24, porém o roteador B informou a ele que consegue 
chegar ao destino (200.2.2.0) com um determinado custo(distância), por exemplo se fosse protocolo RIP, o custo seria 4 saltos ou 4 
hops. 
 
 Exemplos de Protocolos de roteamento e seus respectivos algoritmos: 
 RIP - vetor de distância 
 IGRP - vetor de distância 
 OSPF - estado de enlace 
 IS-IS - estado de enlace 
 
 
 
 
 
�������������	
����
�������	�������������������������������������������������������	� !"��$����$�
	
�%����
��"�&"!���'
 !���()�����)�(*�"����
Sistema Autônomo (AS) 
 
Segundo a RFC 1930, um Sistema Autônomo é um conjunto de roteadores sob uma única administração técnica, usando um gateway 
interior protocolo (IGP) e métricas comuns para encaminhar pacotes dentro do AS, e usando um protocolo de gateway exterior (EGP) 
para rotear pacotes para outros ASs. Como tornou -se comum um único AS usar vários IGPs e por vezes, vários conjuntos de métricas 
dentro de um AS. Foi sucintamente reformulada como um AS sendo um grupo ou um prefixos IP, administrados por uma ou mais 
operadores de rede, que tem uma única e claramente definida política de roteamento. 
 
 
 Protocolos Intra-AS(interno ao Sistema Autônomo ou IGP) e Inter-AS(externo ao Sistema Autônomo ou EGP): 
 
 
Intra-AS (IGP): 
 RIP 
 OSPF 
 IS-IS 
 EIGRP 
 IGRP 
 
Inter-AS (EGP): 
 BGP