Transcrição do áudio
Vamos para mais um vídeo aqui no nosso curso de redes de computadores. Vamos falar sobre algoritmos de roteamento. Então antes que qualquer mensagem seja roteado pelo meu router, o meu router naturalmente ele tem que conhecer uma forma de chegar a caminhos. Alguns outros routers possuem informações inclusive da topologia, por isso que eu não falei que tem que conhecer a topologia. Já outros routers sabem apenas qual o lado, ou seja, o sentido e quantos saltos. Então vamos dar uma olhada nesses algoritmos. Vamos lá. Então o algoritmo de roteamento é uma parte do software da camada de rede e ele é responsável pela decisão sobre qual interface será a interface de saída para um pacote dada a entrada deste pacote, ou seja, por qual porta este pacote entrou. Bom, e temos basicamente dois processos em um primeiro. Então nós temos o encaminhamento dos dados do usuário em si, que é o que nós enxergamos e é o que nós, como eu posso dizer, damos valor e naturalmente o processo de atualização de rotas para as tabelas que serão usadas como a base para tomada de decisão. Ok? Então vamos lá. Bom, vamos lá. O processo de encaminhamento trata-se então cada pacote de dados roteável, preste atenção nesta palavra, dados roteável que entra, seja naturalmente localizado a uma rota para ele seguir, ele ir embora, lembrando que temos que levar em consideração também a porta entrou. Isso tem que ser levado em consideração. Se for um datagrama, temos o endereço de destino, ponto final. Se for um circuito virtual, temos o número do circuito e por isso que é importante ele conhecer a porta que entrou. Ele entrou por essa porta porque ele está indo nesse sentido no circuito virtual. Se ele entrar pela outra porta, provavelmente ele vai seguir outro sentido no circuito virtual. Lembre-se que circuito virtual é muito semelhante a uma rodovia. Entenderam aquele esquema que eu ensinei para vocês? Bom, nós temos naturalmente algoritmos e protocolos de roteamento. Preste atenção. Roteável é uma coisa. Roteável aqui é alguma coisa. Roteável é uma coisa. Exemplo, IPX-Appletalk. Agora, derroteamento é outra coisa. É um grupo de algoritmos e protocolos que trabalham para atualizar as tabelas que serão usadas para essa tomada de realização. Então, o router tem dois trabalhos. Quer dizer que ele processa muito mais do que nós seres humanos estamos exigindo deles. Ou seja, eles ficam também responsáveis por atualizar essas rotas. Algo que seria muito difícil para nós seres humanos. Geralmente, nós pedimos uma página web e queremos uma página web. Bom, nós temos dois tipos de algoritmos, duas grandes classes de algoritmos. Esses são algoritmos não adaptativos e algoritmos adaptativos. Eu não coloquei aqui. Então, nós temos duas classes de algoritmos, não adaptativos e os mais grandes, nós temos adaptativos. Muito simples. Os não adaptativos, eles não baseiam suas decisões de roteamento em medidas ou estimativas do tráfico ou do estado da topologia atual. Ou seja, ele só leva em consideração que o alvo tem que seguir este caminho. Desculpe, o protocolo foi um alvo. Eu estou com outra ideia aqui na cabeça. Outro curso. O pacote tem que ir para lá. Ele só sabe disso. Ele não tem ideia do estado da topologia. Ele não tem ideia se é fibra, se tem atraso de internet work. Ele não sabe nada. Então, ele escolhe a rota utilizando, por exemplo, o sentido que de I para J, para todo I e para todo J, é previamente calculado uma rota offline, ou seja, como assim offline que o livro coloca, esse cálculo offline. Ele obtém os dados, compute os dados e ele acredita nos dados. Se realmente a rota ainda existe, ele não sabe. Entendeu? Por isso que o protocolo coloca essa palavra offline. Por um dado momento, ele passa a tomar a decisão offline, porque ele tem a tabela e ele acredita. Ele não vai verificar se a infraestrutura, essa topologia ainda existe. Entendeu? É isso que ele está falando. E aí, naturalmente, ele sai enviando os pacotes. São algoritmos não adaptativos. Já os algoritmos adaptativos, eles alteram as decisões de gestionamento para refletir mudanças na topologia e normalmente também no tráfego. Ou seja, ele é capaz de compreender, vou usar a palavra aqui, congestionamento. Não entenda como o trânsito, tá galera? A palavra congestionamento em um halter pode ser muito mais sério que um congestionamento de carro. O congestionamento de um halter pode levar, como eu posso dizer, a exclusão do halter nas tabelas de roteamento dos seus vizinhos, o que não aconteceria com a rua. Eu não consegui escolher uma rua por um dado por exemplo. Mas, digamos que se muitos halters fazem roteamento usando uma rota, essa rota vai ficar sobrecarregada. É o que a gente chama de congestionamento. E, naturalmente, os algoritmos adaptativos levam isso em consideração. E são considerados roteamentos dinâmicos, muito dinâmicos. Isso aqui é considerado roteamento mais estático por um certo período de tempo. Esses aqui já são mais dinâmicos. Eles se adaptam, se adaptam, se adaptam. Beleza? Bom, não acredito. Como eu coloco essa pergunta na prova e os meus alunos erram algo em torno de 90%? A taxa de erro quando coloca essa pergunta na prova é de algo em torno de 90%. Eu espero que com essa nova gravação desse curso eu possa reduzir esse número. Não é meu objetivo. Bom, o princípio da otimização funciona assim. Imagine que eu tenho esse princípio estabelezado que se o roteador J estiver no caminho ideal entre o roteador I e o roteador K, o caminho entre ideal entre J e K também será a mesma rota. Pô, parece J, então vamos lá. O roteador J está entre I e K. Você viu que eu coloquei uma imagem bem grande, né? É que é para reprová-la para os alunos. O J está entre I e K. Aqui, digamos que tem alguns outros roteadores que não nos importa. Vamos chamar de R1 e R2. Isso aqui é o R1, isso aqui é o R2. Beleza? Legal. Olha que interessante. Se for localizada uma rota melhor aqui em R2, ela também será a melhor rota entre I e K. Viu? Se eu localizo uma rota melhor aqui, é natural que também será a melhor rota entre J, desculpe, K e I. Simples, simples. Por que isso é importante? Imagine que eu não preciso de atualizar e ficar recalculando toda a rota. Eu posso calcular uma parte da rota devido a um congestionamento. Olha, existe um controle de admissão. É chamado controle de admissão. Quando o rote está sobrecarregado, ele pode deixar de existir, não aceitando novas rotas. Então, ele passa a ser uma rota ruim. O que é de ser uma rota boa? Passa a ser uma rota ruim. E uma nova rota melhor será criada. Então, seu troco justamente nesse ponto é isso que diz o princípio da otimização. É natural que também será a melhor rota até I. Cara, só isso. Por incrível que pareça. Então, vamos lá. Cada roteador vai fazer esse cálculo baseado no princípio da otimização e vai localizar a melhor rota. Quer dizer o seguinte? Que a melhor rota entre B e L é essa que está em vermelho. A melhor rota que está entre F e L é essa que está em vermelho. A melhor rota que está entre A e L é essa que está em vermelho. Simples. É isso que ele está falando. Que se tiver uma mudança nessa árvore, por exemplo, aqui, digamos que no futuro, passa a existir um outro router aqui no meio que vai ligar o L. E é uma rota melhor. É uma rota melhor. Então, essa rota vermelha, que é estrechinho, deixa de existir. Vai ter existir uma nova rota que vai ser também a melhor rota para B. É isso que ele está falando. E é natural que isso aqui é um mundo perfeito. Eu já falei. Cara, se você não sabe estrutura de dados e está num curso de tecnologia e você já passou pela disciplina de estrutura de dados na sua grátia e você não sabe estrutura de dados, cara, muda de curso ou volta e reaprende. Eu estou falando sério. Cara, tudo é baseado nas estruturas de dados. O comportamento das coisas é baseado na estrutura de dados e nós programamos pensando na estrutura de dados. Ou você acorda e refaz. Então, que dá seu jeito ou muda de curso. Vamos lá. Porque eu estou falando isso? Árvore seria um mundo perfeito. É lógico que nas redes de computadores nós temos o grafo aqui na letra A. Está vendo esse grafo? Isso aqui são as ligações. Isso aqui são as ligações. Só uma coisa, uma coisa é a noção. Olha as rotas que existem para L de a parte de B. A, F, K, L. Uma rota. Outra rota. B, A, D, G, L. Outra rota. B, A, caramba, mano. F, H, D, G, L. São todas rotas. Repare que são as rotas. E o pior de tudo, B, A, D, I, C. B, A, D, I, C, B. Entrando no loop infinito, caramba. Grafo é a melhor estrutura de dados para representar coisas complexas do real, do mundo real. Relação de pessoas. Ligação de roteadores. Relação de preço de coisas. Tudo, tudo, tudo nós conseguimos colocar nessa bolsa de grafo. Parece que o mundo é um grande grafo. Não tem a equação, a equação que o Einstein tanto procurou. Aqui é juntar tudo. A física com a física Quântico e Sikambal A4 que nunca chegou na computação, nós somos o grafo. Ele nunca chegou na fórmula dele, mas nós chegamos na estrutura que parece que representa tudo no mundo, cara. A bosta do grafo. Só que a bosta do grafo é a pior estrutura de dados para se fazer busca, tá no livro. Pode ler. Principalmente com a possibilidade de entrar num aço infinito. Se eu entro num aço infinito, eu vou perder processamento. Apenas se eu venho assim. Mas eu posso gravar por onde eu já passei. B, A, D, I, C, B. Já passei, parei aqui. Mas eu tenho que ter memória para guardar por onde eu passei. Inclusive é uma das formas, tá? Bom, só ver uma coisa aqui. Um salto, pretenção. Um salto, dois salto, três salto, quatro salto. Tá ok? Um salto, dois salto, três salto, quatro salto, cinco salto. Aqui foram cinco salto. Um, dois, três, quatro. Ah, não desculpe, quatro foi mal. Um, dois, três, quatro. Um, dois, três, quatro. Mas como assim? Então, o livro presta atenção. Ele é baseado em número de salto. O Roupes. Chamamos de Roupes. Mas poderia também ter aqui um peso na aresta, tá? Um peso na aresta. Nesse caso, por que que os dois têm quatro saltos e chegam aqui? Mas ele colocou esse caminho. Provavelmente o algoritmo que ele usou é assim. Da esquerda para a direita. Entendeu? Então, da esquerda para a direita para cá. Da esquerda para direita, o primeiro para cá. Da esquerda para o primeiro para cá, da esquerda para a direita para cá. Já achou o L. Depois ele iria para a direita aqui, ó. Tá? Agora ele iria para a direita. Então ele já chegaria no L e já existiria o L. No seu algoritmo, talvez dê diferença no seu código. Tá? Talvez porque você pegou da direita para a esquerda. Pense assim. Então, como eu posso dizer para você, o que o livro é importante é o número de saltos. Ok? Legal. Legal. Isso aqui é chamado de árvore de escoamento para o roteado B. Árvore de escoamento para o roteado B. Ele acabou pegando do grafo o cara que estava mais em cima. Dá a impressão que é uma raiz do grafo. Não, poa. Ele poderia ter pego A. Poderia ter pego A. Qual o problema? Por quê? Isso aqui é uma informação que todos os roteadores têm. Todas esses roteadores têm essa informação de topologia. Aqui ele pegou para o roteador B e fez árvore de escoamento. Então, meu amiguinho verde. Olha só. Meu amiguinho verde. Star Wars. Tem nada a ver com meu canal, não, tá? Essa é uma árvore de escoamento para o roteador B. E o C tem uma árvore de escoamento também. O A tem uma árvore de escoamento também. E pode ser que dê diferença. Pode ser que ele dê uma diferença. Porque nós não sabemos o momento em que foi gerado. Eu tenho que explicar para vocês que os dados de topologia eles não simplesmente acordam o roteador acorda e já está com os dados na mão. Ele vai ter que trocar essa informação entre os equipamentos. Isso demora um tempo. E pode ser que algum equipamento não esteja. Mas supondo que? Supondo que, naturalmente, supondo que esses roteadores têm toda a mesma informação, se eu colocasse o A, o A para o D seria melhor rota, o A para o F seria melhor rota, o F para o K seria melhor rota, o A para o F, o K para o L é o princípio da otimização. O princípio da otimização. Legal. Prática! Porra, eu quero isso aqui para os alunos. Ó, faço no papel uma árvore de escoamento usando a teoria do princípio da otimização para todos esses roteadores. Ah, eu pedi para o D, caramba! Queria sacanear os caras, hein? Para o D. Para o D, eu quero o princípio da, naturalmente, usando o princípio da otimização, fazer a árvore de escoamento. Tá ok? Use da esquerda para a direita, porque parece que ele usou da esquerda para a direita. Deixa eu ver. Ó, G, é exatamente. Da esquerda para a direita, desculpe. Tá? Bom, caminho mais curto. O caminho mais curto, olha esse algoritmo que dá hora. Cara, é muito... Deixa eu matar o mosquito, galera. Tá f... Cara, galera, curta e compartilha, tá? Porque o que eu gasto de SBP, tá? Eu estou fazendo propaganda. Meixãozinho. O que eu gasto de SBP aqui nesse estúdio é brincadeira. Compartilha esse canal aí, tá? Vamos lá. Parti de A para D. Olha esse algoritmo. Você que é programador. 2 ou 6? Qual é o menor? 2. Por que que ele colocou agora números? Ponderação. Se você ler o livro nesse ponto um pouquinho antes, os parágrafos antes, ele vai estar falando assim, ó, é no mundo real, não é o número de rapsalts que é utilizado, né? Eles utilizam uma métrica, não fala no livro, mas na Cisco são quatro números que geram uma métrica, tá? No livro da Cisco. É atraso de internet work, largura de banda... Pô, eu teria dificuldade na prova da Cisco agora, hein? Comgestionamento. Ah, o outro eu esqueci. Beleza? Mas chegaria muito próximo. O que que acontece? Então ele coloca isso aqui. Não é teoria de estrutura de dados, grafo com arestas ponderadas, é chamado de arestas ponderadas, tá? 2 e 6. Qual é o menor? Pra cá. Legal. Eu vou fazer o algoritmo sem mostrar as imagens. Legal. Pra ir pra frente, eu tenho 2 ou 7. Ah, 2 com certeza. Olha esse algoritmo. Legal. Agora eu tenho, pra ir pra frente, 7, 2 ou 1. 1. Eu vim pra cá. Legal. Agora eu tenho pra ir pra frente, 7, 2 e 4. Ah, com certeza pra cá. Pegou a jogada? Vou fazer de novo. Preste atenção. Aí é por isso na gravação, você pode voltar. P*** que pariu. Vamos lá. 2 ou 6? Pra ir pra frente, é 2. Legal. Agora eu tenho 7 ou 2? Qual é melhor? Ah cara, 2 pra cá. Legal. Agora eu tenho 7, 2 ou 1? Ah, com certeza é 1. Ele veio para aqui. Agora eu tenho 7, 2 e 4. P***, com certeza é 2. Entenderam? Agora eu tenho 7, 3 ou 2 ou 4. A com certeza é 2. Olha como é que eu tô navegando. Beleza. Agora eu tenho 7, eu tenho, p***, eu tenho... Eu tava aqui, né? Eu tava aqui. Desculpa. 3, 2, 2. Ah cara, eu tenho 2. Cheguei lá no D. Olha como que ele fez esse cálculo. Então vamos lá, ó. Ele veio pra cá conforme eu falei, porque é 2. Agora ele vai vir pra cá, porque é menor. Agora veja que ele decide voltar pra cá. Pra nós seres humanos, nós olhamos isso aqui, desclassificamos isso aqui. P***, ele tá voltando. É que nós somos seres humanos. O roteador, ele não tem essa visão. Ele vai conhecer o caminho. Ele tá conhecendo o caminho. Mas você viu o algoritmo que eu passei pra vocês, ó. Ele veio pra cá conforme eu falei, depois ele veio pra baixo conforme eu falei e depois só teria que chegar até o alvo final. Viram? Cara, eu fui descobrindo o caminho. Porque eu expliquei esse algoritmo como se fosse um algoritmo de computador. Ah, ah, ah, ah, ah. Então eu quero isso em ser mais mais. Se você tá na sala de aula comigo, eu quero isso em papel, porque você é programador, p***. Agora, se você tá no laboratório comigo, então você pode fazer isso em ser mais mais pra mim no computador. Eu quero esse algoritmo funcionando. E você pode inputar esse gráfico no seu algoritmo. Lembre-se de dividir em três camadas, né? Ou seja, o módulo, a controller e a view. Eu quero dividido. Módulo, controller, view. Eu quero estrutura de diretórios da sursy e eu quero um estrutura de diretórios com dist, tá? Com nosso compilado final. Você pode compilar com o G mais mais. Você pode, o G mais mais é interessante. Uma vez, não precisa de passar pelas quatro etapas de compilação não. Beleza? Comprado uma vez, negócio. Ah, ah, ah, ah, ah, ah. É isso aí, coleguinha.