2052039
Overlay Node Placement: Analysis, Algorithms and Impact on Applications
Overlay routing has emerged as a promising approach to improving performance and reliability of Internet paths. To fully realize the potential of overlay routing under the constraints of deployment costs in terms of hardware, network connectivity and human effort, it is critical to carefully place infrastructure overlay nodes to balance the trade-off between performance and resource constraints. In this paper, we investigate approaches to perform intelligent placement of overlay nodes to facilitate (i) resilient routing and (ii) TCP performance improvement. We formulate objective functions to accurately capture application behavior: reliability and TCP performance, and develop several placement algorithms, which offer a wide range of trade-offs in complexity and required knowledge of the client- server location and traffic load. Using simulations on synthetic and real Internet topologies, and PlanetLab experiments, we demonstrate the effectiveness of the placement algorithms and objective functions developed, respectively. We conclude that an approach, hybrid of random and greedy approaches, provides the best tradeoff between computational efficiency and accuracy. We also uncover the fundamental challenge in simultaneously optimizing for reliability and TCP performance, and propose a simple unified algorithm to achieve the same.
11274155
Minimum-Energy Broadcast Using Practical Directional Antennas in All-Wireless Networks
Energy-efficient broadcast communication is an important problem in wireless ad hoc networks. Previously, minimum-energy broadcast that exploits the broadcast nature of radio transmission has been studied and shown to be NP-complete for omnidirectional antennas. In this paper, we investigate the minimum-energy broadcast problem under a wide spectrum of directional antenna models, including sectored antennas with fixed sectors and beamwidth and antenna array-based smart antennas with varying degrees of beam orientation and beamwidth. We first propose the RF design and implementation of each model, which suggests the practical parameters of antennas under that model. We then show that the minimum-energy broadcast problem under each of the antenna models is NP-complete. Lastly, we present a heuristic algorithm based on BIP for the above problem under each directional antenna model and experimentally compare the energy efficiency of using different directional antennas using these heuristics. Our results show that using antennas with adjustable orientation and variable beamwidth gives the best results. For such antennas, the scanning angle is the dominant factor in improving the quality of the broadcast trees. The number of antennas per node is not that critical to obtaining a better broadcast tree as long as it is large enough to cover the entire 360◦ around a node so as to prevent network partitioning.
14665111
Oblivious Symmetric Alternation
We introduce a new class $\rm {O}^p_2$ as a subclass of the symmetric alternation class $\rm {S}^p_2$. An $\rm {O}^p_2$ proof system has the flavor of an $\rm {S}^p_2$ proof system, but it is more restrictive in nature. In an $\rm {S}^p_2$ proof system, we have two competing provers and a verifier such that for any input, the honest prover has an irrefutable certificate. In an $\rm {O}^p_2$ proof system, we require that the irrefutable certificates depend only on the length of the input, not on the input itself. In other words, the irrefutable proofs are oblivious of the input. For this reason, we call the new class oblivious symmetric alternation. While this might seem slightly contrived, it turns out that this class helps us improve some existing results. For instance, we show that if NP⊂P/poly then $\rm PH = {O}^p_2$, whereas the best known collapse under the same hypothesis was $\rm PH = {S}^p_2$. 
 
We also define classes $\rm Y{O}^p_2$ and $\rm N{O}^p_2$, bearing relations to $\rm {O}^p_2$ as NP and coNP are to P, and show that these along with $\rm {O}^p_2$ form a hierarchy, similar to the polynomial hierarchy. We investigate other inclusions involving these classes and strengthen some known results. For example, we show that $\rm MA \subseteq N{O}^p_2$ which sharpens the known result $\rm MA \subseteq {S}^p_2$ [16]. Another example is our result that $\rm AM \subseteq O_2 \cdot NP \subseteq {\prod}^p_2$, which is an improved upper bound on AM. Finally, we also prove better collapses for the 2-queries problem as discussed by [12,1,7]. We prove that $\rm P^{NP[1]} = P^{NP[2]} \Longrightarrow PH = {NO}^p_2 \cap Y{O}^p_2$.
9807325
A Fast Algorithm for Point Labeling Problem
In the map labeling problem, we are given a set P = {p1, p2, . . . , pn} of point sites distributed on a 2D map. The label of a point pi is an axis-parallel rectangle of specified size. The objective is to label maximum number of points on the map so that the placed labels are mutually non-overlapping. Here, we investigate a special class of map labeling problem where (i) the height of the label of each point is the same but its length may be different from the others, (ii) the label of a point pi touches the point at one of its four corners and (iii) it does not obscure any other point in P . We describe an efficient heuristic algorithm for this problem which runs in O(n √ n) time in the worst case. We run our algorithm as well as the algorithm proposed in [14] on the available benchmarks [13]. The results produced by our algorithm is same as that of [14] in most of the cases, and is one less in few cases. But the time taken by our algorithm is much less than [14].
14820946
A hierarchical monothetic document clustering algorithm for summarization and browsing search results
Organizing Web search results into a hierarchy of topics and sub-topics facilitates browsing the collection and locating results of interest. In this paper, we propose a new hierarchical monothetic clustering algorithm to build a topic hierarchy for a collection of search results retrieved in response to a query. At every level of the hierarchy, the new algorithm progressively identifies topics in a way that maximizes the coverage while maintaining distinctiveness of the topics. We refer the proposed algorithm to as DisCover. Evaluating the quality of a topic hierarchy is a non-trivial task, the ultimate test being user judgment. We use several objective measures such as coverage and reach time for an empirical comparison of the proposed algorithm with two other monothetic clustering algorithms to demonstrate its superiority. Even though our algorithm is slightly more computationally intensive than one of the algorithms, it generates better hierarchies. Our user studies also show that the proposed algorithm is superior to the other algorithms as a summarizing and browsing tool.
17398921
Design issues for a high-performance distributed shared memory on symmetrical multiprocessor clusters
Clusters of Symmetrical Multiprocessors (SMPs) have recently become the norm for high-performance economical computing solutions. Multiple nodes in a cluster can be used for parallel programming using a message passing library. An alternate approach is to use a software Distributed Shared Memory (DSM) to provide a view of shared memory to the application programmer. This paper describes Strings, a high performance distributed shared memory system designed for such SMP clusters. The distinguishing feature of this system is the use of a fully multi-threaded runtime system, using kernel level threads. Strings allows multiple application threads to be run on each node in a cluster. Since most modern UNIX systems can multiplex these threads on kernel level light weight processes, applications written using Strings can exploit multiple processors on a SMP machine. This paper describes some of the architectural details of the system and illustrates the performance improvements with benchmark programs from the SPLASH-2 suite, some computational kernels as well as a full fledged application. It is found that using multiple processes on SMP nodes provides good speedups only for a few of the programs. Multiple application threads can improve the performance in some cases, but other programs show a slowdown. If kernel threads are used additionally, the overall performance improves significantly in all programs tested. Other design decisions also have a beneficial impact, though to a lesser degree.
12929901
Completeness of Neighbourhood Logic
This paper presents a completeness result for a first-order interval temporal logic, called Neighbourhood Logic (NL) which has two neighbourhood modalities. NL can support the specification of liveness and fairness properties of computing systems as well as formalisation of many concepts of real analysis. These two modalities are also adequate in the sense that they can derive other important unary and binary modalities of interval temporal logic. We prove the completeness result for NL by giving a Kripke model semantics and then mapping the Kripke models to the interval models for NL.