Recent advances in networked systems and wireless communications have set the stage for applications with wide-ranging benefits. Perhaps the most natural problem in such systems is the ¿efficient¿ propagatio...
详细信息
Recent advances in networked systems and wireless communications have set the stage for applications with wide-ranging benefits. Perhaps the most natural problem in such systems is the ¿efficient¿ propagation of locally stored data. In order to address this problem, the notion of greedy embedding was defined by Papadimitriou and Ratajczak, where the authors conjectured that every 3-connected planar graph has a greedy embedding (possibly planar and convex) in the Euclidean plane. Recently, the greedy embedding conjecture was proved by Leighton and Moitra. However, their algorithm does not result in a drawing that is planar and convex in the Euclidean plane for all 3-connected planar graphs. Here we consider the planar convex greedy embedding conjecture and give a probabilistic proof for the existence of such embeddings. In addition, we discuss a second proof which is almost immediate in the case of an embedding into the 3-dimensional sphere.
TCP, the facto standard used in today's Internet, has been found to perform poorly in Mobile Ad Hoc networks (MANETs). This is exacerbated by contention with increasing UDP-based high priority multimedia traffic a...
详细信息
TCP, the facto standard used in today's Internet, has been found to perform poorly in Mobile Ad Hoc networks (MANETs). This is exacerbated by contention with increasing UDP-based high priority multimedia traffic and the class differentiation introduced in current QoS protocols, which results into TCP starvation and increased spurious timeouts. In this paper, we propose a cross-layer TCP enhancement (E-TCP) that makes use of TCP bidirectionality to avoid TCP traffic starvation and spurious retransmissions in presence of high priority traffic. E-TCP is based on prioritizing TCP acknowledgement packets and on adjusting TCP retransmission timer based on the medium contention. Our simulation results reveal considerable improvements in TCP performance in terms of gooput, delay and retransmission efficiency, while the better channel utilization results into even better high priority traffic performance.
The recursive dual-net is a newly proposed interconnection network for of massive parallel computers. The recursive dual-net is based on a recursive dual-construction of a base network. A k-level dual-construction for...
详细信息
The recursive dual-net is a newly proposed interconnection network for of massive parallel computers. The recursive dual-net is based on a recursive dual-construction of a base network. A k-level dual-construction for k > 0 creates a network containing (2n 0 ) 2 k nodes with node-degree d 0 + k, where no and do are the number of nodes and the node-degree of the base network, respectively. The recursive dual-net is node and edge symmetric and can contain huge number of nodes with small node-degree and short diameter. Disjoint-paths routing and fault-tolerant routing are fundamental and critical issues for the performance of an interconnection network. In this paper, we propose efficient algorithms for disjoint-paths and fault-tolerant routings on the recursive dual-net.
Most Software Transactional Memory (STM) research has focused on multi-core processors and small SMP machines; limited research has been aimed at the clusters, leaving the area of big SMP machines unexplored. Big SMP ...
详细信息
Most Software Transactional Memory (STM) research has focused on multi-core processors and small SMP machines; limited research has been aimed at the clusters, leaving the area of big SMP machines unexplored. Big SMP machine usually use Non-Uniform Memory Access (NUMA) to unburden the overloading between CPUs and the memory. In this paper, we evaluate several STM implementations on big SMP machine with cache coherent NUMA (ccNUMA). We found the remote memory access latency is the key factor influencing the STM performance. We also analyze the different design choices of RSTM. Finally, we conclude a specific design to achieve high performance in this domain.
In information dissemination problem on interconnection networks, problems of broadcasting and gossiping have been widely studied. In this paper, we study the other problem, called multi-source broadcasting, defined a...
详细信息
In information dissemination problem on interconnection networks, problems of broadcasting and gossiping have been widely studied. In this paper, we study the other problem, called multi-source broadcasting, defined as follows: there are some (but not all) vertices each of which has the unique item of information and needs to disseminate to every other vertex. This problem is located at an intermediate position between broadcasting and gossiping. We analyze the multi-source broadcasting problem on the cycle-rooted tree and the de Bruijn digraph as an interconnection network.
Supporting high-performance computing pipelines in wide-area networks is crucial to enabling large-scale distributed scientific applications that require minimizing end-to-end delay for fast user interaction or maximi...
详细信息
Supporting high-performance computing pipelines in wide-area networks is crucial to enabling large-scale distributed scientific applications that require minimizing end-to-end delay for fast user interaction or maximizing frame rate for smooth data flow. We formulate and categorize the linear pipeline configuration problems into six classes with two mapping objectives, i.e. minimum end-to-end delay and maximum frame rate, and three network constraints, i.e. no, contiguous, and arbitrary node reuse. We design a dynamic programming-based optimal solution to the problem of minimum end-to-end delay with arbitrary node reuse and prove the NP-completeness of the rest five problems, for each of which, a heuristic algorithm based on a similar optimization procedure is proposed. These heuristics are implemented and tested on a large set of simulated networks of various scales and their performance superiorities are illustrated by extensive experimental results in comparison with existing methods.
This paper presents how it is possible to increase the genetic programming (GP) computing power (CP) for free, via volunteer computing (VC), using the well known framework BOINC plus a new ``virtualization'' l...
详细信息
This paper presents how it is possible to increase the genetic programming (GP) computing power (CP) for free, via volunteer computing (VC), using the well known framework BOINC plus a new ``virtualization'' layer which adds all the benefits from the virtualization paradigm. Two different experiments, employing a standard GP tool and a complex GP system, are performed -with distributed PCs over several cities- to show the free achieved CP by means of VC, without the necessity of modifying or adapting the original GP source code. The methodology can be easily extended to evolutionary algorithms (EAs).
This paper attempt to develop the technique of maximizing the degree of concurrency and consistency in distributedparallel processing environment by using Ricart and Agrawala's algorithm, which developed an algor...
详细信息
This paper attempt to develop the technique of maximizing the degree of concurrency and consistency in distributedparallel processing environment by using Ricart and Agrawala's algorithm, which developed an algorithm to implement mutual exclusion between processes that is based upon multicast. This will support the mutual exclusion system in client/server distributed environment and avoid the deadlock between the system spawned client threads. Additionally, it will promote the effective starvation solving system and to implement the timing control between the mutually running processes. Application of such algorithm in implementing client/server distributed library system is discussed.
暂无评论