Automated geolocation of IP addresses has important applications to targeted delivery of local news, advertising and other content over the Internet. Previous measurement-based approaches to geolocation employ active probing to measure delays among a set of landmark nodes with known locations. The location of a target IP address can be approximated by that of the nearest landmark, as determined by the delay measurements. To improve geolocation accuracy, a variation of this approach uses multilateration with geographic distance constraints to obtain a continuous location space rather than the discrete set of landmark locations. Since the previous approaches are fundamentally deterministic, they can only provide relatively loose bounds on the true location of an IP address. We develop a statistical geolocation scheme based on applying kernel density estimation to delay measurements among a set of landmarks. An estimate of the target location is then obtained by maximizing the likelihood of the distances from the target to the landmarks, given the measured delays. This is achieved by an algorithm which combines gradient ascent and force-directed methods. We present experimental results on PlanetLab to demonstrate the superior accuracy of the proposed geolocation scheme compared to previous methods.

Presents a new strategy for performance-driven global routing. This strategy focuses on the creation of spanning trees whose properties are under the control of the designer. The authors use it to construct a spanning tree with simultaneous, provable performance guarantees on total length, single-source shortest path length, and bottleneck path length. For rectilinear problems on n terminals in the plane, such a tree can be constructed in O(n log n) time.>

A mechanism for scheduling communications in a network in which individuals exchange information periodically according to a fixed schedule is presented. A proper k edge-coloring of the network is considered to be a schedule of allowed communications such that an edge of color i can be used only at times i modulo k. Within this communication scheduling mechanism, the information exchange problem known as gossiping is considered. It is proved that there is a proper k edge-coloring such that gossip can be completed in a path of n edges in a certain time for n>or=k>or=1. Gossip can not be completed in such a path any earlier under any proper k edge-coloring. In any tree of bounded degree Delta and diameter d, gossip can be completed under a proper Delta edge-coloring in time ( Delta -1)d+1. In a k edge-colored cycle of n vertices, other time requirements of gossip are determined.>

Abstract We give a survey up to 1989 on the Steiner tree problems which include the four important cases of euclidean, rectilinear, graphic, phylogenetic and some of their generalizations. We also provide a rather comprehensive and up‐to‐date bibliography which covers more than three hundred items.

We have written two programs for searching biological sequence databases that run on Intel hypercube computers. PSCANLIB compares a single sequence against a sequence library, and PCOMPLIB compares all the entries in one sequence library against a second library. The programs provide a general framework for similarity searching; they include functions for reading in query sequences, search parameters and library entries, and reporting the results of a search. We have isolated the code for the specific function that calculates the similarity score between the query and library sequence; alternative searching algorithms can be implemented by editing two files. We have implemented the rapid FASTA sequence comparison algorithm and the more rigorous Smith-Waterman algorithm within this framework. The PSCANLIB program on a 16 node iPSC/2 80386-based hypercube can compare a 229 amino acid protein sequence with a 3.4 million residue sequence library in approximately 16 s with the FASTA algorithm. Using the Smith-Waterman algorithm, the same search takes 35 min. The PCOMPLIB program can compare a 0.8 million amino acid protein sequence library with itself in 5.3 min with FASTA on a third-generation 32 node Intel iPSC/860 hypercube.

Designing a VLSI floorplan calls for arranging a given set of modules in the plane to minimize the weighted sum of area and wire-length measures. A method of solving the floorplan design problem using distributed genetic algorithms is presented. Distributed genetic algorithms, based on the paleontological theory of punctuated equilibria, offer a conceptual modification to the traditional genetic algorithms. Experimental results on several problem instances demonstrate the efficacy of this method and indicate the advantages of this method over other methods, such as simulated annealing. The method has performed better than the simulated annealing approach, both in terms of the average cost of the solutions found and the best-found solution, in almost all the problem instances tried.>

Given a set of input points, the rectilinear Steiner tree problem is to find a minimal-length tree consisting of vertical and horizontal line segments that connects the input points, where it is possible to add new points to minimize the length of the tree. The restricted Steiner tree problem in which all the input points lie on the boundary of a rectangle frequently occurs in VLSI physical design. Since the fastest published algorithm is cubic in the size of the point set, VLSI designers have been forced to use heuristic approximations to the length of the Steiner tree for this problem. A simple, practical, linear-time exact algorithm for finding the Steiner tree for points lying on the boundary of a rectangle which obviates the need for some heuristic algorithms in VLSI design is presented. The analysis of the algorithm is based on the use of a tie-breaking rule that should prove useful for other Steiner tree problems.>

A distributed algorithm for solving the floorplan design problem, called a genetic algorithm with punctuated equilibria (GAPE), is presented. Implementation details and the results of empirical studies are presented. The experiments have demonstrated that GAPE performs consistently better than a recently published simulated annealing approach, with respect to both the average cost of the solutions found and the best solution found.>

The problem of finding the minimum-length rectilinear Steiner tree that connects a set of points on the boundary of a rectangle is considered. A linear time algorithm for this problem is presented. The algorithm was implemented in C and executed on a Sun3 workstation. Many examples were solved in a fraction of a second. An example with over 250 terminals took 6.5 s.>

Abstract Three generalizations of broadcasting and gossiping are considered: conference broadcasting in which broadcasting is done by conference calls, partial gossiping in which every gossip must learn at least k pieces of information, and set to set gossiping in which one subset of the members must learn all of the messages of another subset of the members.

The problem of routing wires between pairs of terminals over a two-dimensional grid is shown to be NP-complete. Actually, the stronger result of routing over any planar graph with no vertex having degree greater than 3 is shown to be NP-complete.