21098955
Topological Peeling and Implementation
We present a new approach, called topological peeling, and its implementation for traversing a portion AR of the arrangement formed by n lines within a convex region R on the plane. Topological peeling visits the cells of AR in a fashion of propagating a "wave" of a special shape (called a double-wriggle curve) starting at a single source point. This special traversal fashion enables us to solve several problems (e.g., computing shortest paths) on planar arrangements to which previously best known arrangement traversal techniques such as topological sweep and topological walkm ay not be directly applicable. Our topological peeling algorithm takes O(K + n log(n + r)) time and O(n + r) space, where K is the number of cells in AR and r is the number of boundary vertices of R. Comparing with topological walk, topological peeling uses a simpler and more efficient way to sweep different types of lines, and relies heavily on exploring small local structures, rather than a much larger global structure. Experiments show that, on average, topological peeling outperforms topological walkb y 10 - 15% in execution time.
5727433
An Experimental Study and Comparison of Topological Peeling and Topological Walk
In this paper, we present an experimental study comparing two algorithms, topological peeling and topological walk, for traversing arrangements of planar lines. Given a set H of n lines and a convex region R on a plane, both topological peeling and topological walk sweep the portion AR of the arrangement of H inside R in O(K + n log(n + r)) time and O(n + r) space, where K is the number of cells of AR and r is the number of boundary vertices of R. In our study, we robustly implemented these two algorithms using the LEDA library. Based on the implementation, we carried out experiments to conduct several comparisons, such as the arrangement traversal fashions, memory consumption, and execution time. In general, topological peeling exhibits a better control on the propagation of its sweeping curve (called the wavefront). For memory consumption, two types of measures, logical and physical memory, were examined. Our experiments showed that although both algorithms use nearly the same amount of logical memory, topological peeling could use twice as much physical memory as topological walk. For execution time, experiments revealed an interesting phenomenon that topological peeling has a 10% to 25% faster execution time than topological walk in most cases. Our analysis of this phenomenon indicates that the execution times of topological peeling and topological walk are both sensitive to the ratio of the lower input lines to all input lines. When the ratio of the lower lines to all input lines is around 85%, the two algorithms have roughly the same amount of execution time. Under this ratio, topological peeling considerably outperforms topological walk; above this ratio, topological walk slightly outperforms topological peeling.
29728094
Graph Bandwidth of Weighted Caterpillars
Graph bandwidth minimization (GBM) is a classical and challenging problem in graph algorithms and combinatorial optimization. Most of existing researches on this problem have focused on unweighted graphs. In this paper, we study the bandwidth minimization problem of weighted caterpillars, and propose several algorithms for solving various types of caterpillars and general graphs. More specifically, we show that the GBM problem on caterpillars with hair-length at most 2 and the GBM problem on star-shape caterpillars are NP-complete, and give a lower bound of the graph bandwidth for general weighted graphs. For caterpillars with hair-length at most 1, we present an O(n log n log(nwmax))-time algorithm to compute an optimal bandwidth layout, where n is the total number of vertices in the graph and wmax is the maximum wedge weight. For caterpillars with hair-length at most k, we give a k-approximation algorithm. For arbitrary caterpillars and general graphs, we give a heuristic algorithm and some experimental results. Experiments show that the solutions obtained by our heuristic algorithm are roughly within a factor of c log(n) of the lower bound for a small number c, which is consistent with the inapproximability results of this problem (i.e., no constant approximation for the GBM problem unless P = NP). © 2006 Published by Elsevier B.V.
14297439
Geometric permutations of high dimensional spheres
We prove the maximum number of geometric permutations, induced by line transversals to a set of <i>n</i> pairwise disjoint congruent spheres in <i>R<sup>d</sup></i> with <i>d</i> ⪈ 3, is no more than 4 when <i>n</i> is sufficiently large, achieving the best known upper bound for this problem. We also prove the maximum number of geometric permutations of a set of <i>n</i> noncongruent spheres of bounded radius ratio in R<sup>d</sup>, <i>d</i> ⪈ 3, is at most 2<sup>[√2<i>M</i>]+1</sup>, where <i>M</i> is the ratio or the largest radius and the smallest radius. Our result settles a conjecture in combinatorial geometry.
6260724
Finding an optimal path without growing the tree
For problems on computing an optimal path as well as its length in a certain setting, the "standard" approach for finding an actual optimal path is by building (or "growing") a single-source optimal path tree. In this paper, we study a class of optimal path problems with the following phenomenon: The space complexity of the algorithms for reporting the lengths of single-source optimal paths for these problems is asymptotically smaller than the space complexity of the "standard" tree-growing algorithms for finding actual optimal paths. We present a general and efficient algorithmic paradigm for finding an actual optimal path for such problems without having to grow a single-source optimal path tree. Our paradigm is based on the "marriage-before-conquer" strategy, the prune-and-search technique, and a new data structure called clipped trees. The paradigm enables us to compute an actual path for a number of optimal path problems and dynamic programming problems in computational geometry, graph theory, and combinatorial optimization. Our algorithmic solutions improve the space bounds (in certain cases, the time bounds as well) of the previously best known algorithms, and settle some open problems. Our techniques are likely to be applicable to other problems.
30458595
Finding an Optimal Path without Growing the Tree
In this paper, we study a class of optimal path problems with the following phenomenon: The space complexity of the algorithms for reporting the lengths of single-source optimal paths for these problems is asymptotically smaller than the space complexity of the "standard" treegrowing algorithms for finding actual optimal paths. We present a general and efficient algorithmic paradigm for finding an actual optimal path for such problems without having to grow a single-source optimal path tree. Our paradigm is based on the "marriage-before-conquer" strategy, the prune-and-search technique, and a data structure called clipped trees. The paradigm enables us to compute an actual path for a number of optimal path problems and dynamic programming problems in computational geometry, graph theory, and combinatorial optimization. Our algorithmic solutions improve the space bounds (in certain cases, the time bounds as well) of the previously best known algorithms, and settle some open problems. Our techniques are likely to be applicable to other problems.
16173548
Robust traffic matrix estimation with imperfect information: making use of multiple data sources
Estimation of traffic matrices, which provide critical input for network capacity planning and traffic engineering, has recently been recognized as an important research problem. Most of the previous approaches infer traffic matrix from either SNMP link loads or sampled NetFlow records. In this work, we design novel inference techniques that, by statistically correlating SNMP link loads and sampled NetFlow records, allow for much more accurate estimation of traffic matrices than obtainable from either information source alone, even when sampled NetFlow records are available at only a subset of ingress. Our techniques are practically important and useful since both SNMP and NetFlow are now widely supported by vendors and deployed in most of the operational IP networks. More importantly, this research leads us to a new insight that SNMP link loads and sampled NetFlow records can serve as "error correction codes" to each other. This insight helps us to solve a challenging open problem in traffic matrix estimation, "How to deal with dirty data (SNMP and NetFlow measurement errors due to hardware/software/transmission problems)?" We design techniques that, by comparing notes between the above two information sources, identify and remove dirty data, and therefore allow for accurate estimation of the traffic matrices with the cleaned dat.We conducted experiments on real measurement data obtained from a large tier-1 ISP backbone network. We show that, when full deployment of NetFlow is not available, our algorithm can improve estimation accuracy significantly even with a small fraction of NetFlow data. More importantly, we show that dirty data can contaminate a traffic matrix, and identifying and removing them can reduce errors in traffic matrix estimation by up to an order of magnitude. Routing changes is another a key factor that affects estimation accuracy. We show that using them as the a priori, the traffic matrices can be estimated much more accurately than those omitting the routing change. To the best of our knowledge, this work is the first to offer a comprehensive solution which fully takes advantage of using multiple readily available data sources. Our results provide valuable insights on the effectiveness of combining flow measurement and link load measurement.
53246204
Design of a high-performance ATM firewall
A router-based packet-filtering firewall is an effective way of protecting an enterprise network from unauthorized access. However, it will not work efficiently in an ATM network because it requires the termination of end-to-end ATM connections at a packet-filtering router, which incurs huge overhead of SAR (Segmentation and Reassembly). Very few approaches to this problem have been proposed in the literature, and none is completely satisfactory. In this paper we present the hardware design of a high-speed ATM firewall that does not require the termination of an end-to-end connection in the middle. We propose a novel firewall design philosophy, called Quality of Firewalling (QoF), that applies security measures of different strength to traffic with different risk levels and show how it can be implemented in our firewall. Compared with the traditional firewalls, this ATM firewall performs exactly the same packet-level filtering without compromising the performance and has the same "look and feel" by sitting at the chokepoint between the trusted ATM LAN and untrusted ATM WAN. It is also easy to manage and flexible to use.
12382521
On the design and performance of prefix-preserving IP traffic trace anonymization
Even though real-world Internet traffic traces are crucial for network research, only a tiny percentage of traffic traces collected are made public. One major reason why traffic trace owners hesitate to make the traces publicly available is the concern that the confidential and private information may be inferred from the trace. In this paper we focus on the problem of anonymizing IP addresses in a trace. More specifically, we are interested in prefixpreserving anonymization in which the prefix relationship among IP addresses is preserved in the anonymized trace, making such a trace usable in situations where such prefix relationships are important. The goal of our work is two fold. First, we are interested in analyzing the security properties inherent in prefix-preserving IP address anonymization. Through the analysis of IP traffic traces, we investigate the effect of some types of attacks on the security of the prefix-preserving anonymization process. We also derive results for the optimum manner in which an attack should proceed which provides a bound on the performance of attacks in general. Second, we observe that an existing scheme used for prefix-preserving anonymization, TCPdpriv, has some drawbacks that limit its use in a large-scale, distributed setting. We develop an alternative cryptography-based, prefixpreserving anonymization technique to address these drawbacks while maintaining the same level of anonymity as TCPdpriv.
15892344
Design of a novel statistics counter architecture with optimal space and time efficiency
The problem of how to efficiently maintain a large number (say millions) of statistics counters that need to be incremented at very high speed has received considerable research attention recently. This problem arises in a variety of router management algorithms and data streaming algorithms, where a large array of counters is used to track various network statistics and to implement various counting sketches respectively. While fitting these counters entirely in SRAM meets the access speed requirement, a large amount of SRAM may be needed with a typical counter size of 32 or 64 bits, and hence the high cost. Solutions proposed in recent works have used hybrid architectures where small counters in SRAM are incremented at high speed, and occasionally written back ("flushed") to larger counters in DRAM. Previous solutions have used complex schedulers with tree-like or heap data structures to pick which counters in SRAM are about to overflow, and flush them to the corresponding DRAM counters.In this work, we present a novel hybrid SRAM/DRAM counter architecture that consumes much less SRAM and has a much simpler design of the scheduler than previous approaches. We show, in fact, that our design is optimal in the sense that for a given speed difference between SRAM and DRAM, our design uses the theoretically minimum number of bits per counter in SRAM. Our design uses a small write-back buffer (in SRAM) that stores indices of the overflowed counters (to be flushed to DRAM) and an extremely simple randomized algorithm to statistically guarantee that SRAM counters do not overflow in bursts large enough to fill up the write-back buffer even in the worst case. The statistical guarantee of the algorithm is proven using a combination of worst case analysis for characterizing the worst case counter increment sequence and a new tail bound theorem for bounding the probability of filling up the write-back buffer. Experiments with real Internet traffic traces show that the buffer size required in practice is significantly smaller than needed in the worst case.
207162632
Utility-based anonymization for privacy preservation with less information loss
Privacy becomes a more and more serious concern in applications involving microdata. Recently, efficient anonymization has attracted much research work. Most of the previous methods use global recoding, which maps the domains of the quasi-identifier attributes to generalized or changed values. However, global recoding may not always achieve effective anonymization in terms of discernability and query answering accuracy using the anonymized data. Moreover, anonymized data is often used for analysis. As well accepted in many analytical applications, different attributes in a data set may have different utility in the analysis. The utility of attributes has not been considered in the previous methods.
 In this paper, we study the problem of utility-based anonymization. First, we propose a simple framework to specify utility of attributes. The framework covers both numeric and categorical data. Second, we develop two simple yet efficient heuristic local recoding methods for utility-based anonymization. Our extensive performance study using both real data sets and synthetic data sets shows that our methods outperform the state-of-the-art multidimensional global recoding methods in both discernability and query answering accuracy. Furthermore, our utility-based method can boost the quality of analysis using the anonymized data.