Transcrição do áudio
Vimos então algoritmos muito simples, fáceis de ser implementados, naturalmente nada muito complexo. Agora, nós vamos começar a ver algoritmos de roteamento mais complexo. Um deles, por exemplo, é o estado de enlace. O estado de enlace é um algoritmo muito estudado com o vetor de distância. É raro você falar de roteamento hierárquico, falar Fluding. Geralmente você ouve falar nesses treinamentos, nesses cursos de vetor de distância e estado de enlace, como se fossem competindo. Eles não vão competir, já vou falar para vocês. Vamos lá, primeiro vou explicar isso aqui. A arpanete se preocupava em um substituto para o vetor de distância, pela demora em convergir. O vetor de distância tem um problema que não é a contágio infinito, o pior dos problemas. Vamos colocar assim. O pior dos problemas é demorar para convergir. Esse é o pior dos problemas. Acontece que tem redes que não precisam, só que você tem que entender que na ideia da arpanete, todos as universidades, centros de comando nos Estados Unidos estariam interligadas. Imagine você uma grande rede de um país inteiro. É lógico que o vetor de distância vai demorar para convergir nessas grandes redes. Nós vimos agora em pouco um exemplo de o que, seis roteadores. Agora imagina 200, 300 roteadores. Aí demoraria muito mais. Esse é um problema. Mas redes pequenas com vetor de distância são muito eficientes. Redes pequenas, pouco instáveis são muito eficientes com vetor de distância. Você está entendendo? Por isso que eu vejo, o livro embora coloca um substituto, o vetor de distância é usado até hoje. E até hoje ele não foi eliminado. Porque nós vamos ver que o estado de enlace vai pagar um preço alto para tudo isso, o que ele vai fazer agora. Que seria manter um estado da topologia da rede, ter uma resposta rápida de um router para o outro, e ele vai pagar um preço. E é processamento e memória. Entendeu? E o vetor de distância já não tem esse preço a pagar. O problema do vetor de distância é o tempo para convergir. Só isso. Bom, o estado de enlace, ele converge mais rápido. O estado de enlace converge mais rápido que o vetor de distância. Embora não seja necessário em todas as redes. Conforme eu falei pequenas, instáveis, o vetor de distância é muito bom. Variantes do roteamento de estado de enlace hoje usamos aonde dá a interconexão das grandes redes na internet. Ou seja, na internet da internet. Na internet da internet. Internet com imaiúsculo é interconexão. E a internet com imaiúsculo é um serviço como um todo. Então, daqui até o Japão, com certeza, há muitas redes. É natural que haverá muitas internetes com imaiúsculo. Para acessar o serviço web que está na internet com imaiúsculo. Eu acho que isso aí daria para reprová uma meia dúzia de alunos. Estão zoando. É brincadeira. Esses algoritmos são o IS e IS, muito usados mesmo. E o OSPF, que são algoritmos que são variantes do estado de enlace. Ou seja, pegaram a ideia do estado de enlace como funciona e deram uma bela de uma melhorada. E são usados até hoje. Basicamente, como tem que acontecer esse algoritmo desse roteamento? Simples. O primeiro é o roteador acorda. Até aí, todos os outros estavam fazendo isso. O roteador ligava. Ele descobre seus vizinhos e aprende sobre seus vizinhos. Bom, aqui é uma diferença, vou falar, para o vetor de distância. O vetor de distância aprende sobre a existência de um vizinho. Aqui não. Ele aprende sobre como é o vizinho. Por exemplo, a Cisco utiliza atraso de internet work, tipo de mídia. Você pode utilizar latência de congestionamento. Você pode usar vários índices. E isso, esses vários índices jogam numa equação e viram um número. Preste atenção. Esses vários índices que você escolhe, entram numa equação, que você pode imaginar uma equação que você quiser agora, não importa para nós, que o resultado vai ser um número. Esse número é chamado de peso. Peso. Esse número. E aí, nós vamos medir a distância e o custo para isso, ou seja, o peso disso para os vizinhos. Vamos criar um pacote que informa tudo o que nós acabamos de aprender até aí. Ah, o vetor de distância faz isso. Como é que até aí o vetor de distância faz? Criar, ele cria também. Só que, dessa vez, o pacote não é a rede que está ligado e a quantos saltos. É tudo o que ele sabe dos vizinhos. Tudo, tudo que ele puder. Lógico, né? De uma lista de parâmetros. E aí, eu pego, envio esse pacote para todos os outros roteadores. Hum, uma diferença do vetor de distância. O vetor de distância manda para os vizinhos, né? Esse aqui, ele manda tudo que ele aprendeu para um monte de roteadores à sua volta. Então, não só os vizinhos, mas os vizinhos dos vizinhos. E assim vai. E aí, há um problema. Até aonde nós vamos? E aí, nós vamos ver que nós temos um tal de TTL, que é o tempo de vida. Para cada salto, eu vou decrementando. Quando chega a zero, eu vou excluir. Então, digamos que o meu TTL é 15. Ele avança no raio de 15 roteadores. E aí, morre o meu pacote. Com tudo que eu aprendi. Ou seja, cara, 15 roteadores é coisa pra caramba, meu amigo. 15 roteadores para frente. Só para você ter uma noção, se você der um ping agora no Google, dos Estados Unidos, vai dar em torno de 16 saltos. 14 e 16 saltos nessa faixa. Estão entendendo? Só que, lógico, uma S é mais fechadinha. Mas só para você ter uma noção, não de distância, porque você cai num router, de uma fibra ótica, e a transocerânica, lógico, ela vai 3.000, 4.000 km para chegar num outro router. Essa questão também. Os routers podem estar mais próximos. E aí, ele calcula o caminho mais curto. Então, vamos ver como funciona isso aqui com mais detalhes. Bom, então, a primeira coisa, ele acorda. Ele acorda e ele manda um pacote. Um pacote chamado Hello, pros vizinhos diretamente. Só pros vizinhos. O vizinho recebe o Hello, ele imediatamente responde pela porta que chegou. Ele não passa pelo congestionamento. Beleza? Por que eu estou falando isso? Porque o pacote Echo, o pacote Echo passa pelo congestionamento. E então, a resposta. Olha a diferença do Hello para o Echo. O Hello bate e volta. O Echo ele bate, entra na fila de processamento, é processado e volta. Então, dá para você medir o congestionamento de um roteador assim. Manda o Hello, que seria o caso ótimo. Mediria só o tronco. Quanto foi o tempo de transmissão, divida por dois, você sabe. E o Echo, ele passa pelo mesmo tronco, só que ele pega o congestionamento. Então, você consegue tirar essa diferença. Bom, tem um problema no estado de in lá. Se você achou que todo o universo é resolvido com uma solução mágica, uma equação unificadora de todas as físicas. Tá bem assim, meu coleguinha. E broadcast. Puta merda, fodeu. E como é que funciona o estado de in lá assim, broadcast? Por que? Ele foi projetado para a Arpanete, meu coleguinha. Na Arpanete, nós tínhamos o cabo coaxial. O cabo coaxial é um broadcast. É que em A, eu coloquei em vermelho, coloquei esse broadcast em vermelho, porque não está no livro, está no texto, não está na imagem. Eu coloquei para você diferenciar a minha mudança e na imagem. Se você olhar, coleguinha, e aí, como é que eu faço o broadcast? Por que não é de A para C? Na verdade, é de A para C e F. Os caras tiveram que criar o art... Eita, saiu meu mouse lá, cara. Olha o meu mouse. Saiu o meu mouse da imagem, cara. Quando eu mexeu o mouse agora, eu estava olhando para ele, tentei abaixar, mas estava aqui no outro mouse. Ai, cara. Vai virar piada esse mouse aí, as minhas aulas. Ele vai criar um servidor... Desculpe, um router, um servidor, router virtual aqui, ó. Aqui, ó, esse N é virtual. Ele não existe, ele é criado. Ele é criado e interpretado dessa forma para transformar uma broadcast em um grafo. Então, sempre que você tiver que transformar um broadcast em um grafo, você vai ter que criar esse... esse roteador, esse servidor virtualizado ali. Isso é uma gambiarra que os caras tiveram que fazer para o negócio funcionar direitinho em qualquer tipo de rede, tá? Bom, algoritmo de roteamento de estado de enlace exige que cada enlace tenha uma medida de distância, um custo para encontrar o caminho mais curto por esse custo. E não é o número de saltos, como nós vimos do vetor de distância. São parâmetros, como eu falei, atraso de internet work, chamado de congestionamento, pode ser o tempo de rede, você pode ter também o tipo, tecnologia de rede, pode ter vários itens. Aqui, no caso, o próprio livro do Turnable traz assim, se é gigabit internet, tem o peso 1 e internet tem o peso 10. É o exemplo dele. Só que, lógico, não se trabalha somente com um custo. Você pode trabalhar com isso e mais uma outra coisa. Entenderam? A Cisco trabalha com 4 índices, por exemplo. Se você for fazer a prova da Cisco, você tem que saber esses índices, que ele utiliza lá para fazer o cálculo dele. A forma mais simples de determinar esse atraso é você mandar um eco, e, naturalmente, pegar a resposta. Lembrando novamente que o Hello pega o tempo do link, e o Eco pega o tempo do link mais o tempo de processamento, que é o congestionamento. Opa, e aí dá para você saber. Legal? Bom, então, uma vez obtido todas as informações, estamos prontos para trocar. Lógico, né? Próxima etapa é trocar. E para isso, então, cada roteador, aqui o exemplo do roteador A, ele cria um pacote que é mais ou menos assim. O seu label, o seu nome, que é o único, tem que ser o único. Um número de sequência que nós vamos ver a importância desse número de sequência. Mas já vou te falar que o A, ele pode cria o primeiro, depois daqui 15 segundos ele cria a sequência 2, daqui 15 segundos ele cria a sequência 3, daqui 15 segundos ele cria a sequência 4. Entenderam? E assim ele vai criando essa sequência. Tt, ele é o tempo de vida, se eu colocar 15, essa carta só vai avançar 15 níveis de roteadores e vai morrer. E naturalmente, o A está ligado ao B e o custo número 4. Não sei que métrico ele usou e não nos importa. O A está ligado ao E e tem um custo de 5, o peso. Então, também não me importa como ele chegou nesses números, porque ele tem que entregar um número, que pode ser naturalmente uma equação de muitas características desses links. Bom, vamos lá. Então, olha só como ficou. O A, 4 e 5, b4, 6 e 2. 4, 6 e 2, daqui. Ah, repara que é muito mais complexo agora o protocolo. Eu costumo dizer para os meus alunos que o seguinte, presta atenção, você que é programador, você vai entender. Você tem duas variáveis no seu código. Tem um nível de complexidade. Você tem 50 variáveis no seu código. Porra, é outro nível de complexidade. Eu costumo dizer que a complexidade é visível pelo número de campos e variáveis que você tem. E a complexidade pesa no processamento, meu amiguinho. Não é só na memória. O problema não é só na memória. O problema é no processamento. Tem mais condições de processamento. E isso é algo pesado. Isso que eu estou dizendo que eu não estava de enlace se comparado com vetor de distância. Quase que eu não completei a piada agora. A parte mais complicada do algoritmo agora é distribuir os pacotes. Agora vem um problema. Porque eu tenho que distribuir esses pacotes 15 saltos. Imagina que eu usei o TTL 15 aqui. Eu já estou usando esse exemplo há um tempo. Aqui é 15. Passou por aqui, 14. 13. 12. Entendeu? Então ele vai avançando e vai decrementando o tempo total de vida. Vai sendo eliminado. Quando chega em zero, acabou. O pacote não avança mais. O roteado não segue com ele para frente. Ou seja, você já viu esse algoritmo antes, não viu? Inundação. Veja que o estado de enlace tem que usar o algoritmo de inundação para garantir que todos vão receber a mensagem. E essa mensagem então vai inundar uma subreddit. Essas coisas têm um limite, meu coleguinha. Já falei isso com vocês sobre as unidades autônomas e serviço. Um grupo de roteadores que estão interligados e estão lá para atender uma grande região. Todos os roteadores precisam obter todos os pacotes. E tem que ser rápido e tem que ser confiável. Qual algoritmo é o mais confiável? Com certeza é o inundação. E a inundação já falei para vocês. E ele vai encontrar sempre a melhor rota, desgramada. Mas lembra que eu falei para vocês que o algoritmo de inundação pesa na rede toda? O estado de enlace vai pesar a rede toda se você usar ele. Se você usar o vetor de distância, ele vai ser mais, como eu posso dizer assim, leve na rede. Para manter, conforme eu falei, eu preciso do algoritmo de inundação. E esse número de sequência vai garantir que eu excluo a duplicidade. O número de sequência eu excluo a duplicidade. E pelo tempo de vida, eu garanto que ele não vai muito longe. Ele vai trabalhar dentro do meu alcance. E eu defino meu alcance e já estou definindo que o meu alcance será por exemplo o 15 saltos. Bom, mas ele não sai processando ainda não. Calma aí, calma aí. Então ele vai pegar os pacotes que estão recém chegando no roteador. E eles vão utilizar uma estrutura de dados. Eu sei que você é foda em estrutura de dados. Se você é de redes, se você é programador, não importa. Você tem que saber estrutura de dados. Ponto final. Estamos aqui então com um trecho da memória do roteador B. E repare, ele recebeu de A... A toa. De A, o número de sequência que o A mandou para mim desse pacote, 21, tempo de vida 60, ele vai ser reenviado para a interface CIF. Ele vai ser enviado para CIF aqui, porque ele chegou de A. Então A está a 0, CIF está 1, legal. E eu recebi o Wacknoled, que é a confirmação desse pacote, que eu recebi pelo A. E aqui teriam os dados. Então ele vai enfilerar. Por que ele não vai processar tudo de uma vez assim, chegando e processando? Ele tem que trabalhar com uma árvore. Só que ele não pode customizar a árvore em tempo de execução. Mas isso aqui não, o gráfico é... Chega o gráfico, eu tenho que transformar o gráfico em uma árvore. Então ele vai receber uma massa de dados gigantes por 3, 4 segundos. 3, 4 segundos. Recebe uma massa gigantes e guarda uma estrutura de dados em lista. Aqui é uma lista, tá galera? Aí o que vai acontecer? Isso também vai impedir que chegue duplicatas para mim em tempos atrasados. Quando chegar uma duplicata para mim com tempo de vida, tipo 56, número de sequência 21, de A, eu descarto. Olha como é que é o meu algoritmo de descarto. Chegou uma informação de A, número de sequência 21, já tinha 21, só que o tempo de vida era diferente. Era inferior, então o descarto que chegou. Simples assim. Aí depois que eu recebo, guardo um tempinho, descarta a duplicidade, aí eu trabalho gerando, então, uma árvore. Então uma vez que o rodeador tenha acumulado o conjunto completo de dados de pacote nessa lista encadeada, ele poderá criar, então, um grafo da rede. E ele compreenderá que a rede é assim. Então, um algoritmo do digis... Extra... Não, não, não. Ele vai ser um filandês lá, chamado João, porque tem um problema para eles. Então, vai ter esse algoritmo que é muito usado. Se você fez o comigo de estrutura de dados, fez curso comigo de estrutura de dados em Java, você viu que nós usamos esse algoritmo. Você trabalhou com uma matriz ponderada, não foi meu filho. É, garoto. E a ideia é trabalhar no grafo com uma matriz ponderada. Como assim uma matriz ponderada? Um grafo você pode trabalhar assim. Você faz ele através de listas, as ligações, tipo assim, o A tem uma lista e que tem um, dois, três elementos. Coisa horrível, tá? Ou você pode trabalhar com a matriz. A desvantagem da matriz é que é muito rápido, você consome pouca memória. Você calcula muito rápido, fácil. A desvantagem da matriz é você adicionar um novo elemento aqui. Adicionar um novo elemento é um custo computacional muito elevado. Já a lista encadeada, você adicionar um novo elemento, tem um custo computacional muito mais baixo. Simples assim. Então digamos assim, o A para o B. Do A para o B, peso 10. Do A para o D, peso 30. Do A para o E, peso 100. Então, com isso, eu reparei que eu consegui fazer uma referência entre os elementos. Deixa só dar uma olhada do B para o A. Olha só, essa matriz aqui, galera, é uma matriz ponderada, ponderada, de sentido único. Se tivesse aqui, B para A, 10, seria bidirecional. Bom, lógico que eu vou ter que a boca mostrar o material para vocês. E aí, a ideia é que eu conheça a topologia do grafo. E da topologia do grafo, de tempos em tempos muito rápido, eu recalculo as rotas em um grafo. Eliminando o que? Eliminando duplicidade. Como que eu elimino duplicidade? Digamos que eu quero eliminar uma duplicidade. Por exemplo, vamos lá, eu vou de A para B. Então, eu cheguei aqui. Aí, eu vou de B para C. É isso? Ah, caramba, aqui tudo tem sentido. Se não tivesse sentido, eu conseguiria eliminar aqui na matriz o grafo. Eu transformaria, transformaria, transformaria o grafo em matriz, transformaria o grafo em uma árvore. Confusão lascado, o que eu fiz agora na minha cabeça. É que estou com músico que me enche na paciência. Eu transformo o grafo em uma árvore, simplesmente matando a redundância nessa matriz. De caminho, simplesmente metendo o infinito. Em Java, eu mando a galera fazer isso, colocando zero. Para lá nisso, esse é o material em Java. Lá você tem o capítulo de grafo. E aí eu falo sobre vértices, eu falo sobre a adjacência. E aí eu falo sobre os pesos e tudo mais. Inclusive, esse exercício é o exercício que eu cobro lá. Eu cobro esse exercício lá. Próximo vídeo, vou falar sobre roteamento hierárquico, para que naturalmente roteadores não tenham que conhecer todas as rotas para todos os roteadores do mundo. Olha que louco, podemos fazer roteamento hierárquico. Por exemplo, eu quero bloquear todos os routers que têm conexão na Rússia. Não tem nada a ver com a guerra da Rússia. É porque a Rússia é um campo fértil para um mundo ráquia. Falar nisso, eu tenho um curso ráquio aí, que você pode acompanhar também. E aí, naturalmente, eu quero bloquear aquilo. Então, a Iana me fornece essas zonas, são trechos de endereços IPs, que eu consigo fazer um roteamento por parte do endereço IP. Puts, eu não falei ainda que que é o endereço IP, né? Mas, para frente, eu vou lhes ensinar, calcular o número IP, nós vamos ver os octetos e tudo mais. Ah, vou lhe ensinar, fazer até a divisão de rede. Até o nosso próximo vídeo. Até mais, tchau.