Encaminhamento

Diagramas de
Encaminhamento

No contexto das redes de computadores, o encaminhamento ^{(português europeu)} ou roteamento ^{(português brasileiro)} de pacotes (em inglês: routing) designa o processo de reencaminhamento de pacotes, que se baseia no endereço IP e máscara de rede dos mesmos. É, portanto, uma operação da terceira camada (camada de rede) do modelo OSI.

Este processo pressupõe uma tabela de encaminhamento (tabela de routing) em cada roteador que descreve o caminho percorrido por uma mensagem desde o ponto de origem até ao seu ponto de destino, parecida com a seguinte:

Rede	Máscara	Nexthop
192.168.20.0	255.255.255.0	192.168.0.254
*	-	213.12.123.133

Máscara de rede

A máscara de rede especifica a gama de IPs (domínio de colisão) que pode ser abrangida por um determinado endereço, e é especialmente necessária no processo de encaminhamento (routing). Ainda, com simples cálculos, pode-se gerir eficientemente o espaço de endereçamento disponível, o que nos primeiros tempos da existência da Internet era muito importante, já que os endereços eram alugados em grupos.

A notação formal de uma máscara de rede é o formato típico de um endereço IP e, aplicada com uma operação AND sobre um endereço IP, devolve a rede a que este pertence. Por exemplo,

  192.168. 20.5     =      11000000.10101000.00010100.00000101
& 255.255.255.0     =      11111111.11111111.11111111.00000000
  -------------            -----------------------------------
  192.168. 20.0     =      11000000.10101000.00010100.00000000

Ou seja, o IP 192.168.20.5 pertence, aparentemente, à rede 192.168.20.0. Para simplificar a representação, na notação CIDR a máscara de rede acompanha o IP especificando o número de bits '1' contíguos, separada por uma barra '/'. Por exemplo, a rede anterior podia ser representada como 192.168.20.0/24.

O espaço de endereçamento também é ditado pela máscara de rede, e é equivalente à negação dos seus bits a '0', excetuando o primeiro e último endereço (endereços de rede e broadcast, respectivamente). Por exemplo, uma máscara de 255.255.255.192 irá disponibilizar 62 endereços.

Gestão do espaço de endereçamento

A utilização da máscara de rede foi particularmente útil numa altura em que era comum alugar-se blocos de endereços IP. Os operadores tinham, assim, que distinguir nos seus routers cada um desses blocos, e isso era feito através da máscara de rede.

Suponha-se que dispomos dos seguintes endereços: de 192.168.10.0 a 192.168.10.255, e que existem 5 clientes interessados. Os requisitos de cada um deles são:

Cliente	Quantidade
A	65
B	24
C	4
D	6
E	12

Ora, pelas nossas contas, vamos precisar de 65+24+4+6+12=111 endereços, e vamos ter que organizar a nossa rede em função dos blocos associados.

Para A vamos precisar de 65 endereços. Como os blocos funcionam em potências de 2, iremos reservar uma rede de 128 endereços.
Para B será suficiente uma de 32.
Para C deverá ser uma rede de 8, já que os 4 oferecidos pelo bloco imediatamente inferior corresponderiam, na verdade, a 2 endereços utilizáveis.
Para D idem — uma rede de 8.
Para E seria necessário uma rede de 16 endereços.

Vamos verificar as contas: 128+32+8+8+16=192<256, pelo que podemos satisfazer todos os clientes com a nossa pequena rede. Em termos de divisão,

Rede A: 192.168.10.  0 / 25 = 255.255.255.128  (0-127)
Rede B: 192.168.10.128 / 27 = 255.255.255.224  (128-159)
Rede C: 192.168.10.160 / 29 = 255.255.255.248  (160-167)
Rede D: 192.168.10.168 / 29 = 255.255.255.248  (168-175)
Rede E: 192.168.10.176 / 28 = 255.255.255.240  (176-191)

Pelas contas anteriores e olhando para a nossa divisão, sabemos que o IP 192.168.10.163/29 iria pertencer ao cliente C. Vamos verificar:

  192.168. 10.163     =      11000000.10101000.00001010.10100011
& 255.255.255.248     =      11111111.11111111.11111111.11111000
  ---------------            -----------------------------------
  192.168. 10.160     =      11000000.10101000.00001010.10100000

e que o IP 192.168.10.169/29 iria pertencer ao cliente D:

  192.168. 10.169     =      11000000.10101000.00001010.10101001
& 255.255.255.248     =      11111111.11111111.11111111.11111000
  ---------------            -----------------------------------
  192.168. 10.168     =      11000000.10101000.00001010.10101000

E também podemos verificar que ainda nos sobra espaço para uma rede de 64 endereços. Esta rede é o subespaço que sobrou das contas anteriores: 192+64=256! Já agora, podemos facilmente deduzir que a rede seria 192.168.10.192/26

Roteamento estático

O roteamento estático normalmente é configurado quando uma tabela de roteamento estático é construída manualmente pelo administrador do sistema. Tabelas estáticas não se ajustam automaticamente à alterações na rede, portanto devem ser utilizadas somente onde as rotas não sofrerem alterações, preferencialmente em redes com poucos elementos de conexão e sem caminhos redundantes, configurar um roteamento estático em redes pequenas é relativamente fácil, mas realizar sua manutenção é difícil. Em redes grandes, o principal problema encontrado é a garantia da convergência da rede. O administrador da rede deve ter pleno conhecimento da topologia da rede ao montar a tabela de roteamento, a fim de garantir a convergência da rede. Algumas vantagens do roteamento estático são melhor controle e segurança obtida pela divulgação somente das rotas necessárias e também a redução do broadcast, multicast ou unicast flooding introduzidos na rede pela troca de mensagens dos protocolos de roteamento dinâmicos como OSPF, IS-IS, RIP e EIGRP.

Configuração de roteamento estático

Os passos para uma boa configuração de roteamento estático são:

1) Identificar todos os endereços envolvidos (redes e sub-redes);
2) Para cada roteador, identificar todos os links de dados não diretamente conectados a ele;
3) Para cada roteador, escrever o comando de configuração de rota para cada link não diretamente conectado a ele.

Obs: Para links diretamente conectados o passo (3) não é necessário pois os endereços e máscaras configurados nas interfaces do roteador são automaticamente gravados na tabela de rotas.

Roteamento dinâmico

A maioria dos sistemas usa um algoritmo determinístico roteamento dinâmico: Quando um dispositivo escolhe um caminho para um destino final específico, ele sempre escolhe o mesmo caminho para esse destino até receber informações que o façam pensar que outro caminho é melhor. Alguns algoritmos de roteamento não usam um algoritmo determinístico para encontrar o "melhor" link para um pacote ir da fonte original até o destino final.

Em vez disso, para evitar congestionamentos nos sistemas comutados ou pontos de acesso à rede nos sistemas de pacotes, alguns algoritmos usam um algoritmo aleatório - o paradigma de Valiant - que direciona o caminho para um destino intermediário escolhido aleatoriamente e daí para seu verdadeiro destino final.^[1]^[2]

Redes com mais de uma rota possível para o mesmo ponto devem utilizar roteamento dinâmico. Uma tabela de roteamento dinâmico é construída a partir de informações trocadas entre protocolos de roteamento, desenvolvidos para distribuir informações que ajustam rotas dinamicamente para refletir alterações nas condições da rede. Protocolos de roteamento podem resolver situações complexas de roteamento mais rápida e eficientemente que o administrador do sistema. Em redes onde existem várias alternativas de rotas para um destino, podem ainda trocar para uma rota alternativa quando a rota primária se torna inoperável e para decidir qual é a rota preferida para um destino.

Ver também

Referências

↑ Michael Mitzenmacher; Andréa W. Richa; Ramesh Sitaraman. "The Power of Two Random Choices: A Survey of Techniques and Results". Section "Randomized Protocols for Circuit Routing". p. 34.
↑ Stefan Haas. "The IEEE 1355 Standard: Developments, Performance and Application in High Energy Physics". 1998. p. 15. quote: "To eliminate network hot spots, ... a two phase routing algorithm. This involves every packet being first sent to a randomly chosen intermediate destination; from the intermediate destination it is forwarded to its final destination. This algorithm, referred to as Universal Routing, is designed to maximize capacity and minimize delay under conditions of heavy load."

Este artigo sobre redes de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.

[1] Michael Mitzenmacher; Andréa W. Richa; Ramesh Sitaraman. "The Power of Two Random Choices: A Survey of Techniques and Results". Section "Randomized Protocols for Circuit Routing". p. 34.

[2] Stefan Haas. "The IEEE 1355 Standard: Developments, Performance and Application in High Energy Physics". 1998. p. 15. quote: "To eliminate network hot spots, ... a two phase routing algorithm. This involves every packet being first sent to a randomly chosen intermediate destination; from the intermediate destination it is forwarded to its final destination. This algorithm, referred to as Universal Routing, is designed to maximize capacity and minimize delay under conditions of heavy load."

[1]

[2]