Wireless systems, and mobile ad hoc networks in particular, are more likely to experience transmission and routing errors than their wired counterpart. Factors like the lack of infrastructure, node mobility, and rando...
详细信息
Wireless systems, and mobile ad hoc networks in particular, are more likely to experience transmission and routing errors than their wired counterpart. Factors like the lack of infrastructure, node mobility, and random radio link quality can contribute to significantly higher error rates in these networks. In addition, errors have a more serious impact on the network's resources, due to limitations in bandwidth and battery power inherent to the wireless ad hoc environment. This further complicates the task of designing scalable routing protocols, since larger networks are likely to experience even more errors, which may lead to slower convergence, longer end-to-end delay and unnacceptably high number of retransmissions. In this paper, we focus on the impact of error prevention and recovery on the scaling properties of on-demand protocols for ad hoc networks. Our analytical study, based on the evaluation of the Witness Aided Routing (WAR) and the Dynamic Source Routing (DSR) protocols, shows that the lack of localized intervention in handling errors translates eventually into lack of scalability, both in terms of performance and resource consumption. As route length increases, the performance of DSR degrades dramatically, especially in the presence of fluctuating wireless link quality. Even for small routes, DSR's lack of an error handling mechanism leads to very low probability of success when there is a non-zero probability that links are not bidirectional. On the other hand, WAR remains relatively insensitive both to the length of the route and to variations in mobility and call rates, and has a higher tolerance to radio link instability. This indicates that lacalized error correction can increase route effectiveness and alleviate the effects of short-lived radio link problems to an extent that allows the protocol to scale with the network size.
New algorithms for computing the discrete Fourier transform (DFT) spectra along different directions are derived and implemented. For computing the DFT spectrum along any given direction (containing N DFT frequencies)...
详细信息
New algorithms for computing the discrete Fourier transform (DFT) spectra along different directions are derived and implemented. For computing the DFT spectrum along any given direction (containing N DFT frequencies), a new algorithm is presented that requires N(N-1) additions and a single 1-D FFT. As expected, for a single direction, the directional FFT algorithm is significantly faster than standard 2-D FFT algorithms that compute the entire spectrum (all results are compared against FFTW and FFTPACK). A scalable extension of the unidirectional algorithm for computing the entire DFT spectrum is also derived and implemented. The three most promising features of the new algorithm are that: (i) computation scales nearly linearly with the number of DFT frequencies computed, (ii) the algorithm uses a reduced number of multiplications (yet uses more additions), and (iii) it is more accurate.
We present novel algorithms for efficient scheduling of synchronizing threads on multiprogrammed SMPs. The algorithms are based on intra-application priority control of synchronizing threads. We refer to such algorith...
详细信息
We present novel algorithms for efficient scheduling of synchronizing threads on multiprogrammed SMPs. The algorithms are based on intra-application priority control of synchronizing threads. We refer to such algorithms with the term "informing algorithms". Prerequisite for informing algorithms is the use of an efficient communication medium between the user- and kernel-level and the existence of in-kernel mechanisms that allow the applications to cooperate with the OS scheduler. The applications are given the opportunity to influence, in a non-intrusive manner, the scheduling decisions concerning their threads. We compare the performance of our informing algorithms with the performance of corresponding scheduler-oblivious algorithms under multiprogramming. We experimented on a small-scale, Intel x86-based SMP, running Linux, using both microbenchmarks and applications from the Splash-2 benchmark suite. The results substantiate the superiority of our approach and indicate that the philosophy of informing algorithms may be applicable in a wide range of algorithms and architectures.
Loop tiling is an effective way to improve the cache hit ratio. However, while eliminating self-interference misses, tiling may produce small tiling factors for the cases of some arrays. In order to obtain stable and ...
Loop tiling is an effective way to improve the cache hit ratio. However, while eliminating self-interference misses, tiling may produce small tiling factors for the cases of some arrays. In order to obtain stable and ...
详细信息
ISBN:
(纸本)0769505892
Loop tiling is an effective way to improve the cache hit ratio. However, while eliminating self-interference misses, tiling may produce small tiling factors for the cases of some arrays. In order to obtain stable and proper tiling factors, a new method that automatically generates tiling factors is proposed in this paper. These tiling factors are independent of arrays and can completely eliminate self-interference misses and can also significantly reduce cross-interference misses.
We show that the efficient minus (resp., signed) domination problem is NP-complete for chordal graphs, chordal bipartite graphs, planar bipartite graphs and planar graphs of maximum degree 4 (resp., for chordal graphs...
详细信息
Parallel programmers typically assume that all resources required for a program's execution are dedicated to that purpose. However, in local and wide area networks, contention for shared networks, CPUs, and I/O sy...
详细信息
Distributed applications can fail in subtle ways that depend on the state of multiple parts of a system. This complicates the validation of such systems via fault injection, since it suggests that faults should be inj...
详细信息
Distributed applications can fail in subtle ways that depend on the state of multiple parts of a system. This complicates the validation of such systems via fault injection, since it suggests that faults should be injected based on the global state of the system. In Loki, fault injection is performed based on a partial view of the global state of a distributed system, i.e. faults injected in one node of the system can depend on the state of other nodes. Once faults are injected, a post-runtime analysis, using off-line clock synchronization, is used to place events and injections on a single global timeline and to determine whether the intended faults were properly injected. Finally, experiments containing successful fault injections are used to estimate the specified measures. In addition to briefly reviewing the concepts behind Loki and its organization, we detail Loki's user interface. In particular, we describe the graphical user interfaces for specifying state machines and faults, for executing a campaign and for verifying whether the faults were properly injected.
暂无评论