Algoritmo é melhorado e fluxo da internet pode crescer até 100 vezes

postado em 06/10/2010 08:00

As letras e imagens que aparecem na tela do seu computador quando você acessa o site do Correio Braziliense, por exemplo, só estão lá graças ao trabalho dedicado de muitos fãs da matemática. Gente que passa horas debruçada sobre gráficos, matrizes e modelos teóricos que podem deixar a computação ainda mais rápida nos próximos anos. Na busca de uma internet ultraeficiente, pesquisadores do Instituto de Tecnologia de Massachusetts (MIT) e das universidades de Yale e da Califórnia, nos Estados Unidos, apresentaram um novo algoritmo (1) que melhora ; pelo menos teoricamente ; um dos problemas básicos da web. Na verdade, não só da web. O chamado ;problema de fluxo máximo; pode existir em qualquer área: da internet à rede de computadores de uma pequena empresa, passando pelo transporte coletivo, pelo abastecimento de água e pela aviação civil. O max-flow problem (como é conhecido entre os cientistas) diz respeito ao tráfego de qualquer dado, coisa ou pessoa. ;O max-flow ocorre quando preciso deslocar algo de um lugar para o outro e tenho um meio limitado de transporte;, explica Alessandro Leite, mestre em sistemas distribuídos pela Universidade de Brasília (UnB) e doutorando na mesma universidade. Alessandro Leite, mestre em sistemas distribuídos pela UnB, explica a importância dos estudos de max-flow Assim, máquinas que coordenam o tráfego de informações, de coisas e de pessoas precisam de instruções detalhadas sobre como agir diante de uma grande demanda. Em um aeroporto, por exemplo, o sistema não pode enviar para o mesmo controlador de voo um número exagerado de aeronaves. Também não é possível autorizar uma quantidade absurda de pousos e decolagens, o que sobrecarregaria o aeroporto e as vias aéreas. No caso da internet, o limite é dado pelo fio de transmissão. O cabeamento da rede tem uma capacidade máxima, medida em bits por segundo. Para coordenar essas atividades de tráfego intenso, existem os algoritmos de fluxo máximo, que, grosso modo, buscam o melhor caminho para o envio de dados. Esse ;melhor caminho; é orientado a partir do próprio problema. Uma transportadora pode escolher como critério o menor custo para o envio de mercadorias aos clientes. Na rede de computadores, a opção pode ser pelo caminho que passe pela menor quantidade de pontos (servidores) possível. ;Isso faria com que um e-mail chegasse mais rápido e com menor risco de violação de conteúdo;, esclarece Alessandro Leite. Os algoritmos de fluxo máximo são estudados pela ciência da computação há décadas, mas os pesquisadores não conseguiam desenvolver nenhuma melhoria nessas instruções desde o ano 2000. Se isso parece pouco, considere que, de lá para cá, o acesso a computadores e à internet cresceu muito. Com mais gente na rede, há mais informações circulando e o desafio de enviá-las de forma segura e rápida se torna ainda maior. Modelo Para tentar resolver esse problema, a equipe do MIT e das universidades de Yale e da Califórnia investiu muitos anos de estudo na criação de um modelo teórico para um novo algoritmo. ;O mais interessante dessa pesquisa é que nós introduzimos um conjunto de técnicas bastante diferentes das que são utilizadas por algoritmos anteriores;, destacou ao Correio, por e-mail, Jonathan Kelner, pesquisador do MIT e um dos autores da pesquisa. Grosso modo, funciona assim: redes de transmissão são representadas matematicamente através de matrizes, que cruzam informações sobre o ponto de partida e chegada dos dados e a capacidade máxima de cada possível rota. Com isso, o sistema consegue ;decidir; qual o melhor caminho. O problema é que, até hoje, a análise dos caminhos disponíveis é feita uma a uma para que, depois desse processo, o algoritmo defina a melhor solução. Os pesquisadores norte-americanos investiram justamente nessa parte da escolha. Com a ajuda de técnicas de álgebra linear, eles desenvolveram um jeito de entender a matriz como um todo. Para entender melhor, imagine que você e sua família querem viajar de carro de Brasília a João Pessoa, na Paraíba. Há centenas de caminhos disponíveis, passando por muitas cidades. Você fará a escolha da rota com base em três critérios: a menor distância, a qualidade das pistas e a fluência do trânsito. Para avaliar cada uma das opções de estrada e suas características, você terá que resolver uma equação matemática. Com o modelo desenvolvido nos Estados Unidos, todas as equações das inúmeras possibilidades de rota estão colocadas em uma única equação. Mais complexa que as outras, é claro, mas que também dá o resultado de forma mais rápida. A nova solução ainda não tem nome e precisa passar por muitos testes antes de ser colocada em prática. A estimativa, contudo, é que, se aplicada em uma rede complexa como a internet, o algoritmo poderia tornar o processo 100 vezes mais rápido do que ele é hoje. Antes de comprovar a real eficácia do trabalho, porém, o professor Kelner pretende melhorar o parte teórica ;Temos que ver se o algoritmo em si pode ser ainda mais aperfeiçoado. Depois, vamos tentar aplicar a mesma ideia que usamos para solução de outros problemas. Finalmente, eu gostaria de trabalhar na implementação cuidadosa desse algoritmo, para que a gente possa avaliar seu desempenho empiricamente;, contou ele ao Correio. Apesar de parecer algo tão distante da realidade, Alessandro Leite, doutorando da UnB, lembra que a busca pelo algoritmo ideal sempre vai ocorrer ; ainda mais com o crescente uso de outros dispositivos que permitem o acesso à internet, como smarthphones e tablets. ;O melhor seria que os meios de transmissão tivessem capacidade infinita, ninguém ia ter que se preocupar com o fluxo máximo. Mas isso nunca vai acontecer, porque o meios ; os cabos da internet ; são uma coisa física, eles têm limitações.; 1 - Ordens em bits Os algoritmos são como instruções detalhadas sobre como atingir um objetivo. É o passo a passo que orienta quem vai aplicar uma nova técnica. Também servem para ;dizer; à máquina o que ela deve fazer diante de cada situação.