Search

Summary: Federated networks represent a remunerable operational way, allowing federated partners to increase their incomes through a sharing resource process. They have been primarily used in the context of cloud computing; nowadays, they are also used to provide connectivity services, like virtual private networks. However, providing such a service by using standard technologies in federated networks requires a nonnegligible effort from different points of view (e.g., configuration effort). In this paper, we propose an software‐defined network (SDN)–based framework aiming at overcoming limitations in currently adopted best practices to issue virtual private networks in federated networks. Relying on the SDN architecture, we propose a method allowing federated providers to quickly and easily create federated networks, reducing unneeded costs (e.g., new hardware), and a way for customers to fast‐access federated services, without any explicit actions from providers. We evaluate our framework by using SDNetkit. We focus on analyzing the impact of our implementation on both control and data plane, in terms of number of control messages exchanged in the network and size of the forwarding tables, respectively. [ABSTRACT FROM AUTHOR]

In this paper, we show a polynomial-time algorithm for testing c -planarity of embedded flat clustered graphs with at most two vertices per cluster on each face. Our result is based on a reduction to the planar set of spanning trees in topological multigraphs (pssttm) problem, which is defined as follows. Given a (non-planar) topological multigraph A with k connected components A 1 , ... , A k , do spanning trees of A 1 , ... , A k exist such that no two edges in any two spanning trees cross? Kratochvíl et al. [SIAM Journal on Discrete Mathematics, 4(2): 223–244, 1991] proved that the problem is NP-hard even if k = 1 ; on the other hand, Di Battista and Frati presented a linear-time algorithm to solve the pssttm problem for the case in which A is a 1 -planar topological multigraph [Journal of Graph Algorithms and Applications, 13(3): 349–378, 2009]. For any embedded flat clustered graph C , an instance A of the pssttm problem can be constructed in polynomial time such that C is c -planar if and only if A admits a solution. We show that, if C has at most two vertices per cluster on each face, then it can be tested in polynomial time whether the corresponding instance A of the pssttm problem is positive or negative. Our strategy for solving the pssttm problem on A is to repeatedly perform a sequence of tests, which might let us conclude that A is a negative instance, and simplifications, which might let us simplify A by removing or contracting some edges. Most of these tests and simplifications are performed "locally", by looking at the crossings involving a single edge or face of a connected component A i of A ; however, some tests and simplifications have to consider certain global structures in A , which we call α -donuts. If no test concludes that A is a negative instance of the pssttm problem, then the simplifications eventually transform A into an equivalent 1 -planar topological multigraph on which we can apply the cited linear-time algorithm by Di Battista and Frati. [ABSTRACT FROM AUTHOR]

Given a planar graph G and a partition of the neighbors of each vertex v in four sets v↗, v↖, v↙, and v↘, the problem Windrose Planarity asks to decide whether G admits a windrose-planar drawing, that is, a planar drawing in which (i) each neighbor u ∈ v↗v is above and to the right of v, (ii) each neighbor u ∈ v↖ is above and to the left of v, (iii) each neighbor u ∈ v↙ is below and to the left of v, (iv) each neighbor u ∈ v↘ is below and to the right of v, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow us to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a given combinatorial embedding. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph with n vertices that has a windrose-planar drawing, we can construct one with at most one bend per edge and with at most 2n-5 bends in total, which lies on the 3n × 3n grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area. [ABSTRACT FROM AUTHOR]

A graph is k-planar ]> ]> ( k ≥ 1 ) ]> if it can be drawn in the plane such that no edge is crossed ]> ]> k + 1 ]> times or more. A graph is k-quasi-planar ]> ]> ( k ≥ 2 ) ]> if it can be drawn in the plane with no k pairwise crossing edges. The families of k-planar and k-quasi-planar graphs have been widely studied in the literature, and several bounds have been proven on their edge density. Nonetheless, only trivial results are known about the relationship between these two graph families. In this paper we prove that, for ]> ]> k ≥ 3 ]> , every k-planar graph is ]> ]> ( k + 1 ) ]> -quasi-planar. [ABSTRACT FROM AUTHOR]

We study the following problem: given a planar graph G and a planar drawing (embedding) of a subgraph of G, can such a drawing be extended to a planar drawing of the entire graph G This problem fits the paradigm of extending a partial solution for a problem to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas, which show that the planarity of partially embedded graphs exhibits the 'TONCAS' behavior "the obvious necessary conditions for planarity are also sufficient." These conditions are expressed in terms of the interplay between (1) the rotation system and containment relationships between cycles and (2) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently. Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we make our algorithm run in linear time. Finally, we consider several generalizations of the problem, such as minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. We also apply our algorithm to the simultaneous graph drawing problem SIMULTANEOUS EMBEDDING WITH FIXED EDGES (SEFE). There we obtain a linear-time algorithm for the case that one of the input graphs or the common graph has a fixed planar embedding. [ABSTRACT FROM AUTHOR]

Internet service providers (ISPs) run the internal Border Gateway Protocol (iBGP) to distribute interdomain routing information among their BGP routers. Previous research consistently assumed that iBGP is always configured as a mere dispatcher of interdomain routes. However, router configuration languages offer operators the flexibility of fine-tuning iBGP. In this paper, we study the impact of deploying routing policies in iBGP. First, we devise a provably correct inference technique to pinpoint iBGP policies from public BGP data. We show that the majority of large transit providers and many small transit providers do apply policies in iBGP. Then, we discuss how iBGP policies can help achieve traffic engineering and routing objectives. We prove that, unfortunately, the presence of iBGP policies exacerbates the iBGP convergence problem and invalidates fundamental assumptions for previous results, affecting their applicability. Hence, we propose provably correct configuration guidelines to achieve traffic engineering goals with iBGP policies, without sacrificing BGP convergence guarantees. Finally, for the cases in which our guidelines are not applicable, we propose a novel technique to verify the correctness of an iBGP configuration with iBGP policies. We implement a prototype tool and show the feasibility of offline analyses of arbitrary policies on both real-world and in vitro configurations. [ABSTRACT FROM PUBLISHER]

We prove that planar graphs have O(log² n) queue number, thus improving upon the previous O(√n) upper bound. Consequently, planar graphs admit three-dimensional straight-line crossing-free grid drawings in O(n log8 n) volume, thus improving upon the previous O(n3/2) upper bound. [ABSTRACT FROM AUTHOR]

We show that every plane graph admits a planar straight-line drawing in which all faces with more than three vertices are nonconvex polygons. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study the time complexity of the problem Simultaneous Embedding with Fixed Edges (Sefe), that takes two planar graphs and as input and asks whether a planar drawing of and a planar drawing of exist such that: (i) each vertex is mapped to the same point in and in ; (ii) every edge is mapped to the same Jordan curve in and . First, we give a linear-time algorithm for Sefe when the intersection graph of and , that is the planar graph , is biconnected. Second, we show that Sefe, when is connected, is equivalent to a suitably-defined book embedding problem. Based on this equivalence and on recent results by Hong and Nagamochi, we show a linear-time algorithm for the Sefe problem when is a star. [Copyright &y& Elsevier]

Border Gateway Protocol (BGP) allows providers to express complex routing policies preserving high degrees of autonomy. However, unrestricted routing policies can adversely impact routing stability. A key concept to understand the interplay between autonomy and expressiveness on one side, and stability on the other side, is safety under filtering, i.e., guaranteed stability under autonomous usage of route filters. BGP route filters are used to selectively advertise specific routes to specific neighbors. In this paper, we provide a characterization of safety under filtering, filling the large gap between previously known necessary and sufficient conditions. Our characterization is based on the absence of a particular kind of dispute wheel, a structure involving circular dependencies among routing preferences. We exploit our result to show that networks admitting multiple stable states are provably unsafe under filtering, and the troublesome portion of the configuration can be pinpointed starting from the stable states alone. This is especially interesting from an operational point of view since networks with multiple stable states actually happen in practice (BGP wedgies). Finally, we show that adding filters to an existing configuration may lead to oscillations even if the configuration is safe under any link failure. Unexpectedly, we find policy configurations where misconfigured filters can do more harm than network faults. [ABSTRACT FROM PUBLISHER]

Abstract: The visualization of clustered graphs is a classical algorithmic topic that has several practical applications and is attracting increasing research interest. In this paper we deal with the visualization of clustered trees, a problem that is somehow foundational with respect to the one of visualizing a general clustered graph. We show many, in our opinion, surprising results that put in evidence how drawing clustered trees has many sharp differences with respect to drawing “plain” trees. We study a wide class of drawing standards, giving both negative and positive results. Namely, we show that there are clustered trees that do not have any drawing in certain standards and others that require exponential area. On the contrary, for many drawing conventions there are efficient algorithms that allow to draw clustered trees with polynomial asymptotically-optimal area. [Copyright &y& Elsevier]

In Europe, the aim of achieving a knowledge-based society makes the quality of training systems a topic of crucial importance. Italy is also interested in working out strategies and tools for improving its training supply. To this end the Ministry of Labour asked a public research institute, the Institute for the Development of Workers' Vocational Training (ISFOL), to design a self-assessment tool (SAT) for evaluating the quality of regional training systems. The article tracks the logical and chronological course undertaken to design the SAT, bearing in mind the current conditions of Italian public authorities responsible for the programming, management and evaluation of vocational education and training policies. The SAT methodological choices and its design are described, as well as its application by all Italian central and northern regions. The article concludes by mapping out ways in which the SAT can be used and pointing out some still unresolved issues. [ABSTRACT FROM AUTHOR]

We introduce an open-source, scalable, and distributed architecture, called Megalos, that supports the implementation of virtual network scenarios consisting of virtual devices (VDs) where each VD may have several Layer 2 interfaces assigned to virtual LANs. We rely on Docker containers to realize vendor-independent VDs and we leverage Kubernetes for the management of the nodes of a distributed cluster. Our architecture does not require platform-specific configurations and supports a seamless interconnection between the virtual environment and the physical one. Also, it guarantees the segregation of each virtual LAN traffic from the traffic of other LANs, from the cluster traffic, and from Internet traffic. Further, a packet is only sent to the cluster node containing the recipient VD. We produce several example applications where we emulate large network scenarios, with thousands of VDs and LANs. Finally, we experimentally show the scalability potential of Megalos by measuring the overhead of the distributed environment and of its signaling protocols. [ABSTRACT FROM AUTHOR]

We investigate the problem of computing the types of the relationships between Internet Autonomous Systems. We refer to the model introduced by Gao [IEEE/ACM TRANSACTIONS ON NETWORKING, 9(6):733-645, 2001] and Subramanian et al. (IEEE Infocom, 2002) that bases the discovery of such relationships on the analysis of the AS paths extracted from the BGP routing tables. We characterize the time complexity of the above problem, showing both NP-completeness results and efficient algorithms for solving specific cases. Motivated by the hardness of the general problem, we propose approximation algorithms and heuristics based on a novel paradigm and show their effectiveness against publicly available data sets. The experiments provide evidence that our algorithms perform significantly better than state-of-the-art heuristics. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line drawings such that if the proximity region of two points p and q representing vertices is devoid of other points representing vertices, then segment is allowed, but not forced, to appear in the drawing. This differs from the usual, strong, notion of proximity drawing in which such segments must appear in the drawing. Most previously studied proximity regions are associated with a parameter β, . For fixed β, weak β-drawability is at least as expressive as strong β-drawability, as a strong β-drawing is also a weak one. We give examples of graph families and β values where the two notions coincide, and a situation in which it is NP-hard to determine weak β-drawability. On the other hand, we give situations where weak proximity significantly increases the expressive power of β-drawability: we show that every graph has, for all sufficiently small β, a weak β-proximity drawing that is computable in linear time, and we show that every tree has, for every β less than 2, a weak β-drawing that is computable in linear time. [Copyright &y& Elsevier]

In this paper we consider the important class of directed acyclic graphs (DAGs), and present the results of a comparative study on four popular drawing algorithms specifically developed for them. The study has been performed within a general experimental setting consisting of two large test suites of DAGs and a set of quality measures. The focus of the experiments has been the practical behavior of the algorithms with a geometric foundation compared to that of the algorithms with a topological foundation. The four algorithms exhibit various trade-offs with respect to the quality measures considered, and none of them clearly outperforms the others. Our analysis has motivated the development of a new hybrid strategy for drawing DAGs that performs quite well in practice. [ABSTRACT FROM AUTHOR]

A diagram is a drawing on the plane that represents a graph-like structure, where nodes are represented by symbols and edges are represented by curves connecting pairs of symbols. An automatic layout facility is a tool that receives as input a graph-like structure and is able to produce a diagram that nicely represents such a structure. Many systems use diagrams in the interaction with the users; thus, automatic layout facilities and algorithms for graphs layout have been extensively studied in the last years. We present a new approach in designing an automatic layout facility. Our approach is based on a modular management of a large collection of algorithms and on a strategy that, given the requirements of an application, selects a suitable algorithm for such requirements. The proposed approach has been used for designing the automatic layout facility of Diagram Server, a network server that offers to its clients several facilities for managing diagrams. [ABSTRACT FROM AUTHOR]

The data dictionary contains the description of all types of data produced, managed, exchanged, and maintained in an organization. Data descriptions (very often hundreds of schemas) should be organized in such a way to allow all the users of the information system to understand the meaning of data and their relationships. In this paper, a new set of structuring primitives is presented for a dictionary of entity relationship data schemas. The formal properties of such structuring primitives ire investigated and the feasibility of their usage is shown by providing a methodology for dictionary design. [ABSTRACT FROM AUTHOR]

A digraph is upward planar if it has a planar drawing such that all the edges are monotone with respect to the vertical direction. Testing upward planarity and constructing upward planar drawings is important for displaying hierarchical network structures, which frequently arise in software engineering, project management, and visual languages. In this paper we investigate upward planarity testing of single-source digraphs; we provide a new combinatorial characterization of upward planarity and give an optimal algorithm for upward planarity testing. Our algorithm tests whether a single-source digraph with n vertices is upward planar in O(n) sequential time, and in O(log n) time on a CRCW PRAM with n log log n/log n processors, using O(n) space. The algorithm also constructs an upward planar drawing if the test is successful. The previously known best result is an O(n²)-time algorithm by Hutton and Lubiw [Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, pp. 203-211]. No efficient parallel algorithms for upward planarity testing were previously known. [ABSTRACT FROM AUTHOR]

In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding of a level graph on the surface of the rolling cylinder or on the surface of the torus, respectively known by the name of Cyclic Level Planarity and Torus Level Planarity , are polynomial-time solvable. Moreover, we show a complexity dichotomy for testing the Simultaneous Level Planarity of a set of level graphs, with respect to both the number of level graphs and the number of levels. [ABSTRACT FROM AUTHOR]

The four articles in this special section presents extended versions of several outstanding papers from the IEEE Pacific Visualization Symposium 2011 (PacificVis 2011) which was held in Hong Kong, China, on 1-4 March 2011. The objective of this annual symposium is to foster greater exchange between visualization researchers and practitioners, and to draw more researchers in the Asia-Pacific region to enter this fascinating and rapidly growing area of research. [ABSTRACT FROM AUTHOR]

This article introduces the articles in the special issue on visualization applications and design studies. The articles cover both traditional application domains such as visualization of scientific simulations and emerging ones such as visualization of text streams, image collections, trajectories, and political phenomena. [ABSTRACT FROM PUBLISHER]

Internet Service Providers can enforce a fine-grained control of Interdomain Routing by cleverly configuring the Border Gateway Protocol. However, the price to pay for the flexibility of BGP is the lack of convergence guarantees. The literature on network protocol design introduced several sufficient conditions that routing policies should satisfy to guarantee convergence. However, a methodology to systematically check BGP policies for convergence is still missing. This paper presents two fundamental contributions. First, we describe a heuristic algorithm that statically checks BGP configurations for guaranteed routing convergence. Our algorithm has several highly desirable properties: i) it exceeds state-of-the-art algorithms by correctly reporting more configurations as stable, ii) it can be implemented efficiently enough to analyze Internet-scale configurations, iii) it is free from false positives, namely never reports a potentially oscillating configuration as stable, and iv) it can help spot troublesome points in a detected oscillation. Second, we propose an architecture for a modular tool that exploits our algorithm to process native router configurations and report the presence of potential oscillations. Such a tool can effectively integrate syntactic checkers and assist operators in verifying configurations. We validate our approach using a prototype implementation and show that it scales well enough to enable Internet-scale convergence checks. [ABSTRACT FROM PUBLISHER]