RICERCA ITALIANA     

Research program

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

University Co-ordinator

Università degli Studi ROMA TRE - INFORMATICA E AUTOMAZIONE - ROMA(RM)

Research Unit Leader

Giuseppe DI BATTISTA

Description

The proposed research is described below for each task of the project involving this Research Unit.

Task 1.2 - Visualization Methodologies

IntroductionThe Internet graph and the Web graph are difficult to represent and to visually explore. First, they are huge; second, they contain both portions (subgraphs) with low density and portions with a very high density, and, finally when seen from a specific point of view, they show a hierarchical structure induced by the topological distance from that point. Within this task we investigate three different and complementary methodologies to cope with these difficulties: clustering techniques, visualization algorithms for graphs with different densities, and radial drawings.Clustering is a strategy that can be used to cope with the complexity of huge graphs, when specific sets of nodes are homogeneous with respect to some properties. These sets can be viewed as single units (called clusters). The relations between clusters can be considered as a high level view of the network, allowing if needed the exploration of the content of each cluster. In the Internet, clusters can be naturally derived from the widely adopted hierarchical routing, where routes to destinations are decided first at the Autonomous System level and then at the router level inside each AS. Web communities may be natural clusters for the Web graph.Suitable techniques to draw networks with heterogeneous density factor can arise from the study of k-dense trees, which are graphs whose density strongly depends on the parameter k. In particular, trees are 1-dense graphs, and some well studied classes of graphs such as k-trees are special subclasses of k-dense trees. In this task we will conceive efficient and effective algorithms to draw k-dense trees and k-trees in 2D and 3D space, and we will experiment their use for the visualization of networks coming from the Internet and the Web.Exploring the Web graph starting from one or more source nodes and following the direct links between pages, naturally induces a hierarchy among the explored nodes. From a visualization point of view, it could be desirable to place these nodes on different geometric levels, according to their hierarchy layers. In the past, geometric levels were mainly thought as straight lines, and several algorithms were designed for this drawing convention. Recently, the new "radial drawing" paradigm [BBF03,DD03] is gaining attention for the representation of layered graphs. In a radial drawing the layers are represented by concentric circles. This paradigm appears quite natural and enlarges the class of layered graphs that can be drawn without edge crossings with straight-line edges. In this task we will conceive efficient algorithms for computing drawings of layered graphs and networks within the radial drawing paradigm, and evaluate their effectiveness for Web maps visualization, by measuring some important aesthetic criteria of the computed drawings, like number of crossings, number of bends, area, and angular resolution.

Phase 1Clustering techniques. A c-planar drawing of a clustered graph is a drawing of the underlying graph such that each cluster can be surrounded by a boundary, and no two boundaries cross. The objective of Phase 1 is to investigate the computational complexity of some key problems related with clustered planarity. We consider the problems of determining whether a clustered graph admits a c-planar drawing and finding a c-planar representation of it. We will study classes of clustered graphs of increasing generality for which a c-planar drawing can be found in polynomial time. Since the search for a polynomial time algorithm to solve the problem in the general case was unsuccessful in the last ten years, it is possible that the problem is intractable. In such a case, provided that its hardness could not be proven, we would like at least to find exponential time algorithms able to decide the c-planarity of a clustered graph and to find a suitable representation of it. This would allow finding heuristics that could help in the practical cases.Visualization algorithms for graphs with different densities. In this Phase we will focus on methodological aspects concerning dense graphs. We will study the properties of k-dense trees and of k-trees, in order to design algorithms that draw them in small area and volume in 2D and 3D space, respectively. Since some effective drawing algorithms were already described for k-trees in the literature [DLM03,DW03], it seems to be promising to investigate the relationships between the classes of k-dense trees and j-trees (where j>=k), in order to extend to k-dense trees some structural properties of j-trees, like for example the "tree width" factor.Radial drawings. The main objective of this Phase is the design of efficient algorithms for computing radial drawings of graphs. We will take into account both drawings where edges are straight lines and drawings where edges can bend.

Expected Results of Phase 1- Classes of clustered graphs for which the 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.

Phase 2Clustering techniques. In Phase 2 we will design efficient c-planar drawing algorithms for the classes of clustered graphs for which the problem is tractable. For those classes for which the problem is intractable, we plan to conceive some effective and efficient heuristics.Visualization algorithms for graphs with different densities. Taking advantage of the study performed during Phase 1, we plan to conceive and implement new efficient and effective algorithms to draw k-dense trees and k-trees in 2D and 3D space. Also, we plan to test them in order to validate their use for the visualization of networks coming from the Internet and the Web.Radial drawings. In Phase 2 two different variants of the problem of computing radial drawings of graphs will be considered. In the first variant the layer of each vertex is part of the input and hence known in advance. In the second variant we are free to determine the layer to which each vertex will belong; in this case, if the input graph is planar, an important target of the drawing algorithm is the minimization of the number of total layers needed to draw the graph without edge crossings.We will measure the quality of the radial drawings computed by the algorithms designed in Phase 1 and Phase 2, by considering some important aesthetic criteria, like number of crossings, area, total edge length, and angular resolution.

Expected Results of Phase 2- Efficient c-planar drawing algorithms for the classes of clustered graphs for which the problem is tractable.- Efficient and effective algorithms to draw k-dense trees and k-trees in 2D and 3D space.- Polynomial time algorithms for computing planar radial drawings of graphs using the minimum number of levels.

Task 2.2 - Discovery and Visualization of the Internet

IntroductionNetwork discovery in the Internet is a more and more complex task, as in addition to the known overlay of different abstraction levels, for example that of the Autonomous Systems and that of the subnets and routers, the next generation Internet will also host two alternative network protocols. In fact, since the deployment of the IPv6 protocol, meant to replace the current IPv4, is expected to be very slow and complex, the two protocols will coexist for several years. The objective of this Task is the discovery and the visualization of the Internet topology at different abstraction levels, taking into account mixed IPv4-IPv6 environments. Also, since network discovery at the Autonomous Systems level is associated with the inference of their relationships and routing policies from Border Gateway Protocol (BGP) conversations, we aim at improving state of the art algorithms for interpreting and visualizing routing dynamics and instabilities in the light of such relationships.To design and implement the visualization tools of this task we trust to benefit from the models and algorithms conceived in Task 1.2.

Phase 1In Phase 1 we plan to design a platform for network discovery in mixed IPv4-IPv6 networks, composed by basic software modules able to execute the elementary operations used by network discovery tools in mixed networks [CDP04], like IPv4 spoofing, Path MTU discovery, parallel IPv4 and IPv6 DNS resolution, packet injection in remote IPv6-in-IPv4 tunnels etc. Second, we plan to conceive novel visualization models and drawing algorithms allowing the exploration of the IPv4 and IPv6 network layers and of their mutual relationships. Also, we aim at integrating information at the level of Autonomous Systems with that at the level of subnets and routers. In addition, we will take advantage of emulated environments to experiment the effects of remote instabilities on the BGP update collection process and we will conceive a model for the AS level routing dynamics able to capture the network evolution and stability conditions.

Expected Results of Phase 1- 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 from archives of BGP updates

Phase 2The aim of Phase 2 is the implementation and the experimentation of the techniques, the visualization algorithms, and the network discovery platforms designed in Phase 1. We plan to realize on-line services allowing the users to explore the Internet topology and to monitor Internet routing instabilities and dynamics.

Expected Results of Phase 2- Experiments of network discovery in a mixed IPv4-IPv6 environment with a new software library developed for this purpose, and reports on the IPv6 protocol deployment- A system for the visual exploration of the network showing both router and AS-level information- A system for monitoring the AS network in search for causes of instabilities

Task 3.2 - Discovery and Visualization of the Web

IntroductionIn the last five years several algorithms have been described for the discovery of Web Communities. Since a community groups nodes that are strongly related, inferring communities from the Web graph topology can represent an important step to understand how the information is distributed over the Web, and it seems to be a natural way to cluster the Web graph. However, neither effective systems nor services have been developed so far for the visualization of graphs representing topologies of Web Communities. In this task we will study methodologies and algorithms for the visualization and the browsing of Web Communities and we plan to realize systems and services that integrate tools for discovering, visualizing, and browsing Web Communities. We plan to experiment the radial drawing paradigm investigated in Task 1.2 for visualizing portions of Web Communities, while focusing on a particular source node.

Phase 1The objective of Phase 1 is the design of a system for the visualization and the browsing of Web Communities. The discovery will be mainly performed by implementing and integrating in the system well known algorithms described in the literature [FLG00,GKR98]. Concerning visualization, since a Web Community usually appears as a large and dense graph, we will design ad hoc 2D graph drawing and browsing strategies, which allow the user to explore the community at different detail levels. The system will first show to the user a high-level map of the community where all nodes belonging to the same domain (i.e., web server) are grouped. This map gives an idea of the skeleton of the community, by showing only its inter-domain links, and the user can interact with the map by repeatedly expanding or contracting domains. After each expansion or contraction operation the drawing algorithm will keep unchanged the user mental map as much as possible. Links between pairs of nodes belonging to different expanded domains of the current map will be shown, and the system will apply effective algorithms [BCPD03,BDDLTV00,BDLN01,BDLN02] to minimize the number of crossings, the number of bends, and the total area, also in the presence of vertex and edge labels.

Expected Results of Phase 1- New methodologies and algorithms for visualizing and browsing Web Communities.- A prototype system for the discovery, the visualization, and the browsing of Web Communities.

Phase 2In Phase 2 we plan to test and refine the prototype system for the discovery and the visualization of Web Communities developed in Phase 1. To test the system we will use huge data sets of nodes collected by other Research Units of this project. As a second objective, we plan to make the system as a Web service accessible on-line. This second task poses several engineering problems. For example, in a stand-alone system, the user can require for the exploration of a Web community that includes one or more source nodes. If a sufficiently large neighborhood of these nodes in the Web graph is already stored in a local data set (precomputed off-line) the system can quickly compute such a Web community by applying on the neighborhood a suitable exploration algorithm. However, if some of the source nodes are not present in the local data set, or if their known neighborhood is not sufficiently large, a new crawling of the Web graph starting from these nodes is required as a pre-processing step in order to enrich the information stored in the local data set. Clearly, this approach in not completely viable to design an on-line service architecture, because many user-requests can contemporary need a crawling operation, causing a saturation of the server bandwidth and of its computational resources. This means that new interaction modalities of the user with the service and new strategies to suitably enrich off-line the local data set should be designed, taking into account that the total hardware resources needed to compute and store the local data set should be kept as small as possible.

Expected Results of Phase 2- Identification of huge data sets of Web nodes that can be used to test the system.- A Web service for the discovery, the visualization, and the browsing of Web Communities.