Estratégias de participação para a optimização da descarga distribuída da Web

Abstract

Face à imensidão de informação na Web, a descarga de páginas utilizada, por exemplo, em motores de pesquisa, sugere a criação de um sistema de agentes distribuídos (robôs) que descarreguem vários servidores em simultâneo. Porém, quando procuramos optimizar os mecanismos de descargas somos confrontados, pela necessidade de obedecer às actuais políticas de delicadeza que obrigam à existência de um intervalo de tempo mínimo entre dois pedidos de descarga, ao mesmo servidor. Uma outra dificuldade resulta da forma como as páginas estão distribuídas, uma vez que a maior percentagem está alojada em apenas um pequeno número de servidores, provocando um desnivelamento significativo entre servidores com poucas páginas e servidores (mais densos) com elevado número de páginas. O aumento do desempenho de cada agente é alcançável através da diminuição do intervalo de descarga, do aumento do número de conexões http persistentes e/ou repartindo as páginas existentes pelos servidores Web mais densos por vários robôs. No entanto, se considerarmos que o valor daquele intervalo deve permanecer constante, para o universo de todos os servidores, a tentativa de usar qualquer uma daquelas opções conduz necessariamente à violação das políticas de delicadeza. Todavia, sendo razoável esperar que a capacidade de processamento e comunicação de um servidor cresça na razão directa da respectiva densidade, podemos considerar que o intervalo de descarga pode ser reduzido na proporção inversa. Isto é, podemos fazer variar o tempo de delicadeza nos pedidos de descarga a um servidor no sentido de adaptar o intervalo à respectiva densidade. Esta dissertação surge como uma alternativa aos processos tradicionais da descarga da Web, capaz de reduzir o tempo total de descarga de páginas e minimizar a sobrecarga de comunicação necessária à sincronização de uma colecção de agentes distribuídos. Subjacente está uma infra-estrutura de comunicações e uma arquitectura de descarga que comporta a existência de entidades dedicadas ao particionamento do espaço Web e a sua alocação a um conjunto de robôs distribuídos, organizados hierarquicamente através da definição de entidades lógicas. Durante o processo de descarga das páginas é recolhida informação para gerar configurações de divisão da Web, através da aplicação de algoritmos de partição de grafos, baseados em modelos da Internet obtidos por aproximação calculada por caminhos mais curtos no grafo gerado.

The hugeness of the Web suggests the creation of distributed agent systems (crawlers) to download several sites simultaneously, for instance, in search engine crawling operations. However, the optimization of crawling download operations faces the need to comply with current politeness policies which require a minimum period of time between two consecutive requests to same server. Another difficulty arises from the distribution of the number of pages on the servers, where a large percentage is hosted in a small number of servers, causing a significant unevenness between servers with few pages and dense servers with a lot of pages. On each crawler performance increase may be achieved through the reduction of the politeness time interval, increase of the number of http persistent connections and/or subdividing dense servers by several crawlers. Nevertheless, considering that the politeness interval should remain constant, for the universe of all the servers, any attempt to use any of the remaining options, leads, inevitably, to the violation of the politeness policies. However, considering the expectation that the density of a server grows proportional to its processing and communication capabilities, it is feasible to consider a reduction in the politeness interval inversely proportional. In other words, politeness interval may be adjusted during download requests to a server based on its density. This dissertation appears as an alternative to the traditional download processes, able to reduce the total page download time and to minimize the communication overhead required to synchronize the collection of distributed crawlers. Underneath the crawling’s operations lays a communication infrastructure and a download architecture embracing the existence of dedicated Web space partitioning entities and its allocation to the distributed crawler set, organized hierarchically through logical entities. Throughout the download process additional information is gathered to generate the resulting division of the Web through the application of graph partitioning algorithms based on models of the Internet obtained by approximation by shortest paths on the generated graph.