Research program
Algorithms for the Next Generation Internet and Web: Methodologies, Design, and Experiments
University Co-ordinator
Università degli Studi di ROMA "Tor Vergata" -
INFORMATICA, SISTEMI E PRODUZIONE - ROMA(RM)
Research Unit Leader
Giuseppe Francesco ITALIANO
Description
The main objective of our research is to develop techniques and methods for the design of efficient algorithms and data structures on graphs, with an emphasis on their application in the context of next generation networks. In order to address the problems represented by the highly dynamical nature of such networks (exhibiting fast traffic variations and frequent topological changes, sometimes spurred by faults in the networking elements) coupled to the fault sensitivity of applications running over them, we plan to:1. Design new methodologies and algorithms for shortest path routing (Task 2.1);2. Design fault-tolerant algorithms for fundamental combinatorial problems related to basic problems arising in the design of search engines (Task 1.1).Since network problems, both at the design and at the operational level, can be better faced through a proper visualization of the network itself and of the applications running over it, we also plan to tackle the visualization problem, namely:3. Devise new visualization methodologies and implement Web-based tools that can be used in studying network-related aspects (Tasks 1.2 and 3.2).It is our intention to incorporate the algorithmic and visualization techniques to be developed in efficient and easy-to-use software tools. Most of our algorithms will be tested on open source platforms (such as Linux and/or BSD Unix), so as to assess and measure their competitiveness in practical scenarios. More in detail, the proposed research for our Unit is described below for each task of the project where the Unit is directly involved.
Task 1.1 Models and Algorithmic ParadigmsIntroductionAs observed in the state of the art description related to Task 1.1, search engines and other Web applications may greatly benefit from the design of algorithms tolerant to destructive memory faults. Although data replication is a natural approach to protect against this kind of faults, it can be very inefficient in a dynamic setting in which the objects to be managed are large and complex. It seems thus natural to ask whether it is possible to design fault-tolerant algorithms that do not exploit data replication in order to achieve resilience to memory faults. In this task, we plan to design fault-tolerant algorithms for fundamental combinatorial problems arising in the design and implementation of search engines (e.g., sorting and searching).
Phase 1We shall investigate the design of algorithms resilient to destructive memory faults. In particular, we plan to design algorithms able to cope with highly dynamic and unpredictable faults, that can happen at any memory place, possibly simultaneously. We shall focus on algorithms that do not wish to recover corrupted data, but simply to be correct on uncorrupted data, without incurring any time or space overhead.
Expected Results1) Design of novel fault-tolerant algorithms for fundamental combinatorial problems related to search engine design and implementation.
Phase 2Since memory faults occur most commonly in large, external memories, we plan to investigate whether the techniques designed during Phase 1 can be adapted to an external setting, with the goal of designing efficient fault-tolerant external memory algorithms.
Expected Results1) Design of fault-tolerant external memory models and algorithms.
Task 1.2 Visualization MethodologiesIntroductionStarting from our own experience with the visualization tools that we have developed together with other reserch units in this project, we plan to create new Java-based tools to support the realization of animated visualizations over the Web, which can be used for studying network related aspects. Based on the philosophy that an average programmer should not invest too much time in getting an actual animation of the behavior of a piece of code up and running, we aim at developing light and easy-to-use visualization tools. Furthermore, we shall try to exploit the potentialities offered by the Java language so as to make our tools highly independent of specific operating systems.
Phase 1During Phase 1 we plan to devise new approaches to automate (or at least to simplify) the software visualization process over the Web. In particular, we plan to develop light and easy-to-use Java-based tools to support the creation of animated visualizations by integrating editing capabilities with the traditional program-driven animation approach.
Expected Results1) Development of light and easy-to-use Java-based tools for software visualization over the Web.
Phase 2We shall evaluate the effectiveness of the software visualization systems developed during Phase 1, cooperating with other Research Units in the evaluation process.
Expected Results1) Evaluation and improvement of the software visualization tools developed during Phase 1.
Task 2.1 Algorithms for Internet RoutingIntroductionJointly with other research units in this project, we plan to design and engineer new algorithms for Internet routing, based on shortest path techniques, to be employed in networking software tools. Since the network dynamics are extremely fast (due to the traffic variability as well as to the variations in the network connectivity and in the availability of switching and transmission resources), the recomputation of the routing tables must be as fast. Following up on a very recent technique [DI03], which is substantially different from previous approaches, we plan to use novel combinatorial properties of graphs based on the well-known optimal-substructure property of shortest paths as the kernel for solving dynamic single-source shortest paths. We also plan to devise methods for dynamically maintaining the t-spanner of a graph, i.e., a subgraph where the original distances are approximate within a factor t. This is especially important for reducing the number of physical links in a communication network, which may be very expensive, without increasing too much the distances between routers.In order to develop an adequate testbed for the proposed routing algorithms, we plan to devise tools for generating network structures typical of Next Generation Internet. In particular, the aim of our research is to streamline the simulation process of network structures as defined by the models proposed in the literature. Particular attention will be paid to the following issues: a) the generation time; b) the relationship between the parameters typically employed to describe a network structure and those of the model; c) the dynamics of the simulated network structure. The final goal is to arrive at a multi-model generator for simulation purposes, capable of generating a set of network structures under a variety of requirements (e.g. connectivity, node degree, failure patterns, topology dynamics).
Phase 1We shall investigate new algorithmic techniques for maintaining dynamic single-source shortest paths. We emphasize that this is a very ambitious goal. Differently from other dynamic graph problems, such as for instance the dynamic maintenance of minimum spanning trees [HDT01], dynamic shortest path problems seem much harder to solve: indeed, despite the existence of some previous studies [RR96], finding a solution that is better than recomputing from scratch a shortest path tree has been an elusive goal for over four decades. To achieve better bounds, we plan to extend the latest results for dynamic all pairs shortest paths presented in [DI03]. We also plan to study methods for maintaining dynamically the t-spanner of a graph. Finally, we plan to evaluate the generation time of the models for network structure simulation proposed in the literature and to establish the relationships between the parameters used in the generation process and those which are typically used to describe a network structure.
Expected Results1) Design of new algorithms for dynamic single-source shortest paths and dynamic t-spanners.2) Comparison of different models of network structure simulation.
Phase 2We plan to evaluate experimentally the algorithmic techniques studied in Phase 1, developing new heuristics for improving the performances of the proposed algorithms in real environments, and testing them on open source platforms. We shall also tune and engineer known dynamic routing algorithms by extensively testing their performance on a suitable testbed generated according to specific models for next generation Internet and we shall design new ones based on the gained insight.
Expected Results1) Engineering of the algorithms devised in Phase 1 for Internet routing.2) Characterization of typical failure and topology evolution patterns in order to incorporate them in the structure simulation process. An implementation of the structure simulator will be realized.
Task 3.2 Discovery and Visualization of the WebIn the last decade many new techniques has been devised for constructing drawings of graph-like combinatorial structures. The representation of Web sites and communication networks can greatly benefit from these techniques. In some cases, software tools for the visualization of Web maps are used in conjunction with search engines and search agents so as to provide a direct representation of the Web graphs (see, e.g., systems such as Mappuccino and WebSphinx). However, it is typically difficult for the user to interact with the visualization tools in order to get a customized representation of some topic of interest. In this project, we aim at studying new visualization algorithms based both on focus plus context techniques and on appropriate map models. In particular, we shall give an XML-based description for data structures corresponding to query maps with applications to searching and caching algorithms for web database applications.
Phase 1During Phase 1 we shall study algorithmic problems related to tree visualization algorithms based on focus plus context techniques, so as to provide a graphical support for filtering redundant information and focusing on sites that are close to the topic of interest. Most relevant nodes should be selected as starting focal points, and visualization techniques like hyperbolic visualization should be applied so as to allow the user to perceive what part of the web graph matches the topics most relevant for the submitted query.
Expected Results1) Study of new algorithms and web graph data models for visualizing search data structures.
Phase 2We shall implement the algorithms designed in Phase 1, developing a prototypical visualization tool and tuning up existing ones using different XML-based graphical languages (GraphXML, SVG).
Expected Results1) Implementation, tuning, and application of the models and algorithms designed during Phase 1.
|
