Routing Repetitive Messages in Content Networks

ABSTRACT: The contents of this dissertation fit in the field of computer science, more precisely in the area of computer systems, structures and networks, within which the dissertation deals with distributed search in content networks built on peer-to-peer architecture. Distributed contents are those that are not located on specialized servers only, but also on several end computers. The main research issues in systems with distributed contents are: enabling content accessibility without regard to its location; management and control over the contents during their existence in the system, and effective collaboration among the system users. The dissertation deals with query message routing in unstructured content networks with peer-to-peer architecture. Knowing that the quantity of repeated queries is considerable, it focuses predominantly on achieving lower number of redundant query transfers. The introduction outlines the main problems of distributed search and relates them to query message routing. The need for more effective content based routing in systems with high local autonomy is exposed. The second chapter describes content network properties, focusing on content placement and content aggregation. With regard to these two characteristics, the content networks are classified in four families. For each family, the level of query routing difficulty is assessed and syntactic content oblivious networks, shortly type A content networks, are found to be the most challenging. The third chapter reviews the characteristics of peer-to-peer architecture and its implementation areas. Especially those properties are emphasized that strongly affect the choice for or against the peer-to-peer architecture: decentralization, scalability, anonymity, dynamicity, self-organization, desired level of autonomy and security. The fourth chapter focuses on query routing in the selected type of network overlays. We analyze the overlay topology properties, namely power laws and small world property. Afterwards, we choose an algorithm suitable for generating artificial topologies with these properties, which we would use for the simulation purposes. We also present an overview of the most important research achievements concerning distributed search in unstructured peer-to-peer systems. In the fifth chapter, we first describe the basic routing mechanism – flooding. Then we suggest two improvements, based on the aforementioned topological properties and the fact that some queries are frequently repeated. We call the first improvement remembering past answers and the second one metadata exchange. Each node stores metadata about the answers that were passed to other nodes. When a node receives a subsequent query, it tries to find a match within the stored metadata. If a match is found, the query is not flooded to all of the node’s neighbors, but rather it is routed to the neighbor from whom the matching answer was obtained earlier. When using metadata exchange, the neighbor nodes exchange their metadata collections and build shortest paths towards the contents within their neighborhood in a distributed fashion. We have to stress that we are talking about content routing here, namely routing towards the desired contents, not towards a known destination node. In content routing, the destination address is not important since the query is satisfied as soon as the contents are found at any node. Contrary to the systems indexing all or a part of the system contents, information regarding the destination node is not stored - only routing information, i.e. information on the neighbor node is stored. We also describe how our routing scheme deals with network dynamicity and state our expectations regarding improved routing behavior. In the sixth chapter, we formally present a conceptual model of the described system, serving as a base for the simulation execution. We explain network topology, routing strategies, query distribution and replication, contents distribution and replication. The contents may be either equally or not equally popular. The queries may target the contents either uniformly or proportionally to their popularity. The contents may be either replicated uniformly or may the more popular contents have also more copies within the system. We have performed the simulation on four types of topologies: random graph, lattice, lattice with randomly reconnected links, and GLP topology, which follows the power law and small world requirements. We have also experimented with two topology sizes – in the bigger one, the reach of the query is less than the longest of shortest paths in the graph, while in the smaller one these two quantities are roughly the same. In the seventh chapter, we present model validation and verification and describe a couple of metrics used for interpretation of the simulation results. In the eighth chapter, we present the most important simulation results. We show that the suggested improvements can reduce the total number of query hops for up to two orders of magnitude, compared to the basic flooding, whereas from the user’s point of view, the quality of service remains the same. We present the differences in routing behavior over several combinations of system parameters and topology properties. We also evaluate the results by means of the metrics described earlier. At last, we give some suggestions for practical use of the presented routing improvements. In the conclusions, we evaluate our contributions again and suggest possible directions for further research of this interesting and quickly developing area. Our main contributions to science are: • We evaluated the behavior and topological properties of content networks with peer-to-peer architecture and considered their role in traffic reduction. • We suggested two improvements for routing of repeated queries, where the nodes consider previously forwarded answers and may also exchange these metadata with their neighbor nodes. • According to the simulation results and the analysis of suggested routing modifications we observed that in the modeled systems, it is advisable to upgrade the basic flooding with the suggested modifications