RICERCA ITALIANA     

Algorithms for the Next Generation Internet and Web: Methodologies, Design, and Experiments

Università degli Studi di Roma "Tor Vergata"

Abstract

This research project brings together five leading groups in algorithmic research in Italy in a joint effort that aims at:

(1) Discovering new algorithmic techniques and methodologies;

(2) Identifying and solving key algorithmic problems in important applications; and

(3) Contributing to the accelerated transfer of advanced algorithmic technologies into tools, libraries and systems.

The main emphasis of the project will be on a novel combination of application-oriented research in two important domains (the next generation Internet and the Web) with innovative methodological work on algorithm engineering, information visualization and general algorithmic techniques. As a natural consequence of our methodological and application-oriented approach, the research plan is organized into three mutually related Work Parts (WP):

WP1 - Advanced Methodologies for Internet and the Web. We plan to identify and develop key algorithmic methodologies that arise from Internet and Web applications, which are general enough and thus widely applicable. Furthermore, we plan to produce also methodologies and testbeds for algorithmic engineering.

WP2 - Internet Algorithmics: Design and Experiments. In the next generation Internet, the capacity to optimize the use of the network resources will play a crucial role in order to save costs and to improve efficiency and reliability. We thus plan >>>

Principal Investigator

Giuseppe Francesco ITALIANO Università degli Studi di ROMA "Tor Vergata"

Research Objectives

Traditional algorithms and algorithm design methods seem to be inadequate for the algorithmic challenges of the near future. Massive data sets and sophisticated retrieval operations on these data arise in many important applications, such as Web Information Retrieval. In this framework, new algorithmic techniques, which better suit the architecture of real computing platforms, seem also deeply needed. The next generation Internet will pose new challenging algorithmic problems as well: communications patterns in networks are radically changing, and the very large and heterogenous networks of tomorrow must be controlled in a more efficient way than what is currently possible.

This project aims at discovering new algorithmic techniques and methodologies, identifying and solving key algorithmic problems in important applications, and contributing to the accelerated transfer of advanced algorithmic technologies into practical systems. In more detail, the main objectives of the project are:

(1) To contribute to the science and engineering of algorithms and data structures that, spurred by the above domains, will be enriched by new methodologies and techniques.

(2) To design and analyze new and efficient algorithms for tackling specific Internet and Web problems, in order to have an impact on key applications in these areas.

(3) To assess the effectiveness of our solutions not only by analytical means, but also by >>>

First Results

Below we list the main results expected for Phase 1, organized accordingly to the different tasks of the project.

Task 1.1 Models and Algorithmic Paradigms
- A first release of an open source algorithmic software library to handle massive graphs
- An Architecturally Parametrized Model of Computation (APMC)
- Design of novel fault-tolerant algorithms for fundamental combinatorial problems

Task 1.2 Visualization Methodologies
- Characterization of classes of clustered graphs for which c-planarity testing can be solved in polynomial time
- New results about properties and relationships of k-dense trees and k-trees
- Polynomial time algorithms for computing radial drawings of graphs with predefined vertex levels

Task 2.1 Algorithms for Internet Routing
- New algorithms for dynamic single-source shortest paths and dynamic t-spanners
- The theoretical and experimental study of Nash equilibria and price of anarchy of congestion management policies
- Fast IP lookup and classification methods

Task 2.2 Discovery and Visualization of the Internet
- Models and drawing algorithms for the visualization of the network at different abstraction levels
- Design of algorithms and a platform for IPv4-IPv6 network discovery
- Models of inter-domain routing dynamics and studies about routing instabilities and their inference >>>

Timescale

24 months

National and international background

Algorithmic technologies are playing a vital role in the spectacular growth of the Internet and of the Web: this is witnessed not only by a rich body of scientific literature which has been flourishing over this area, but also by a number of Internet companies (e.g., Akamai, Google, Yahoo), which have based a major part of their business success on new algorithmic ideas. This research project deals with the design of algorithms and data structures for applications arising from the Internet and the Web domains. In particular, we shall focus on advanced algorithmic methodologies, and on the design and experimentation of algorithmic technologies for the Internet and the Web. This state-of-the-art section will primarily refer to those areas, briefly surveying previous work which is at the basis of our research plan.

Advanced Methodologies for Internet and the Web

Most of the applications arising from the Internet and the Web, like Web searching, generate ever larger data sets, of the order of PetaBytes. In such a scenario, algorithms for massive data problems must take explicitly into account that the size of the internal memory is limited, and that access to external memory (e.g., hard disks) is currently about six order of magnitudes slower than access to internal memory. Furthermore, modern computing platforms have a quite complex memory hierarchy system, which basically rewards locality of reference, as data is transferred in blocks >>>