admash's library 108 articles

Abstract

A biologically inspired algorithm is presented to route messages in mobile wireless ad-hoc networks. The principles of swarm intelligence are used to define a probabilistic algorithm for which routing through paths of maximum throughput is an emergent property. This adaptive algorithm, dubbed termite, uses stigmergy to reduce the amount of control traffic needed to maintain a high data goodput. Stigmergy is a process by which information is indirectly communicated between individuals through their environment The termite environment is the contents of ...

Abstract

We consider the problem of incorporating security mechanisms into routing protocols for ad hoc networks. Canned security solutions like IPSec are not applicable. We look at AODV[21] in detail and develop a security mechanism to protect its routing information. We also briefly discuss whether our techniques would also be applicable to other similar routing protocols and about how a key management scheme could be used in conjunction with the solution that we provide. ...

Abstract

A mobile ad hoc network is a collection of wireless mobile devices which dynamically form a temporary network, without using any existing network infrastructure or centralised administration. Each node in the network effectively becomes a router, and forwards packets towards the packet’s destination node. Ad hoc networks are characterized by frequently changing network topology, multi-hop wireless connections and the need for dynamic, efficient routing protocols. * The overarching requirement for low power consumption, as ...

Abstract

A common technique used by routing protocols for ad hoc wireless networks is to establish the routing paths on-demand, as opposed to continually maintaining a complete routing table. Since in an ad hoc network nodes not in direct range communicate via intermediate nodes, a significant concern is the ability to route in the presence of Byzantine failures which include nodes that drop, fabricate, modify, or mis-route packets in an attempt to disrupt the routing service. ...

Abstract

We present a systematic analysis of insider attacks against mobile ad-hoc routing protocols, using the Ad hoc On-Demand Distance Vector (AODV) protocol as an example. It identifies a number of attack goals and then studies how to achieve these goals through misuses of the routing messages. To facilitate the analysis, we classify the insider attacks into two categories: atomic misuses and compound misuses. Atomic misuses are performed by manipulating a single routing message, which cannot be further divided; compound misuses are ...

Abstract

The RFAM database defines families of ncRNAs by means of sequence similarities that are sufficient to establish homology. In some cases, such as microRNAs and box H/ACA snoRNAs, functional commonalities define classes of RNAs that are characterized by structural similarities, and typically consist of multiple RNA families. Recent advances in high-throughput transcriptomics and comparative genomics have produced very large sets of putative noncoding RNAs and regulatory RNA signals. For many of them, evidence for stabilizing selection acting on their secondary structures ...

Abstract

There is growing recognition that mammalian cells produce many thousands of large intergenic transcripts1, 2, 3, 4. However, the functional significance of these transcripts has been particularly controversial. Although there are some well-characterized examples, most (>95%) show little evidence of evolutionary conservation and have been suggested to represent transcriptional noise5, 6. Here we report a new approach to identifying large non-coding RNAs using chromatin-state maps to discover discrete transcriptional units intervening known protein-coding loci. Our approach identified 1,600 large multi-exonic RNAs ...

Abstract

Bowtie is an ultrafast, memory-efficient alignment program for aligning short DNA sequence reads to large genomes. For the human genome, Burrows-Wheeler indexing allows Bowtie to align more than 25 million reads per CPU hour with a memory footprint of approximately 1.3 gigabytes. Bowtie extends previous Burrows-Wheeler techniques with a novel quality-aware backtracking algorithm that permits mismatches. Multiple processor cores can be used simultaneously to achieve even greater alignment speeds. Bowtie is open source (http://bowtie.cbcb.umd.edu). ...

Abstract

The 68040 processor includes an instruction memory system, a data memory system, and a synchronous bus. These resources are controlled by three autonomous machines, the instruction memory controller (IMEMC), the data memory controller (DMEMC), and the bus controller (BC). The structure of the data paths, the main caches, the address-translation caches, and the controllers are presented, including a discussion of the methodologies used in the development ...

Abstract

The central CPU for the 68040 processor is the integer unit (IU). The IU contains multiple 32-bit data and address paths with heavily pipelined instruction execution control for improved performance. Frequently used instructions and addressing modes have been optimized for single cycle execution. Additionally, independent control for each pipe state yields increased throughput. Implementation of control structures for increased performance is presented, with emphasis on design trade-offs for automated logic synthesis versus full custom, hand crafted circuits. The impact of the ...

Abstract

The integer, floating-point, and on-chip memory subsystems of the Motorola 68040 microprocessor operate in parallel to achieve four times the performance of a 68020 microprocessor and ten times the performance of a 68882 floating-point coprocessor. The integer and floating-point units are described in terms of their performance, internal architecture, and methods used to obtain this performance. The 68040 integer unit (IU) is optimized to execute the most common instructions in a single cycle while maintaining user code compatibly with the 68000 ...

Abstract

For pt.1 see ibid., February (1990). The memory subsystem, the external bus, chip and board testing, and design-verification methods for the 68040, a third-generation, full-32-bit microprocessor in the Motorola 68000 family, are discussed. The internal caches and memory management are examined at length. The external bus protocol, arbitration, snooping, and timing specifications are addressed. The MOVE16 instruction, which moves a cache line from one address (which may reside in the data cache) to another address outside the cache is described. User ...

Abstract

A 32-b single-chip processor has been developed that is user object-code compatible with members of the 68000 processor family. The 14-4-mm×15.5-mm device contains over 1.2 million transistors and is fabricated with a double-layer-metal CMOS process. The processor integrates three major functional units: an integer processor: a floating-point processor; and a Harvard-style memory unit. Each major unit is described, and the implementation techniques that were employed and selected circuit issues that were confronted in the design are discussed ...

Abstract

The first implementation of a new microprocessor architecture promises to narrow the gap between the power of very small and very large computers. ...

Abstract

The design of the 68040, a third-generation, full-32-b microprocessor in the Motorola 68000 family, is presented. The 68040 integrates over 1.2 million transistors on one chip and can execute the complete 68020 microprocessor and 68882 floating-point coprocessor instruction sets. Pipelined integer and floating-point execution units that operate concurrently with separate internal memory controllers and an autonomous bus controller contribute to its high performance level. Physical caches of 4 kB each for instruction and data reside on chip. Separate address-translation caches of ...

Abstract

As the newest member of the 68000 microprocessor family, the MC68060 microprocessor offers a cost-effective, power-thrifty solution for high-performance embedded processing applications. This article focuses on its microarchitectural features, such as superscalar pipeline implementation, that enable it to achieve its high-performance objectives while maintaining 68000 user-code compatability. Running at 50 and 66 MHz, the first 3.3V implementations achieve 103 Dhrystone MIPS performance at 66 MHz ...

Abstract

LT-codes are a new class of codes introduced by Luby for the purpose of scalable and fault-tolerant distribution of data over computer networks. In this paper, we introduce Raptor codes, an extension of LT-codes with linear time encoding and decoding. We will exhibit a class of universal Raptor codes: for a given integer k and any real epsiv>0, Raptor codes in this class produce a potentially infinite stream of symbols such that any subset of symbols of size k(1+epsiv) is sufficient ...

Abstract

We present decentralized algorithms that compute minimum-cost subgraphs for establishing multicast connections in networks that use coding. These algorithms, coupled with existing decentralized schemes for constructing network codes, constitute a fully decentralized approach for achieving minimum-cost multicast. Our approach is in sharp contrast to the prevailing approach based on approximation algorithms for the directed Steiner tree problem, which is suboptimal and generally assumes centralized computation with full network knowledge. We also give extensions beyond the basic problem of fixed-rate multicast in ...

Abstract

Recent advances in information theory show that the throughput of a multicast session can be improved using network coding. In overlay networks, the available bandwidth between sender and different receivers are different. In this paper, we propose a solution to improve the throughput of an overlay multicast session with heterogeneous receivers by organizing the receivers into layered data distribution meshes and sending substreams to each mesh using layered coding. Our solutions utilize alternative paths and network coding in each mesh. We ...

Abstract

This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content of each transmission. We show that intelligently mixing packets increases network throughput. Our design is rooted in the theory of network coding. Prior work on network coding is mainly theoretical and focuses on multicast traffic. This paper aims to bridge theory with practice; it addresses the common case of unicast traffic, dynamic ...

Abstract

An ad hoc mobile network is a collection of mobile nodes that are dynamically and arbitrarily located in such a manner that the interconnections between nodes are capable of changing on a continual basis. In order to facilitate communication within the network, a routing protocol is used to discover routes between nodes. The primary goal of such an ad hoc network routing protocol is correct and efficient route establishment between a pair of nodes so that messages may be delivered in ...

Abstract

We study the problem of reducing data overhead of mesh-based multicast ad hoc routing protocols by reducing the number of forwarding nodes. We show that minimizing the number of forwarding nodes is equivalent to the problem of finding the minimal cost multicast tree. In addition, we demonstrate the problem to be NP-complete by a transformation to the Steiner tree problem. We propose a distributed heuristic algorithm based on the epidemic propagation of the number of forwarding nodes. Our simulation results show ...

Abstract

Current ad hoc multicast routing protocols have been designed to build and maintain a tree or mesh in the face of a mobile environment, with fast reaction to network changes in order to minimize packet loss. However, the performance of these protocols has not been adequately examined under realistic scenarios. Existing performance studies generally use a single, simple mobility model, with low density and often very low traffic rates. We explore the performance of ad hoc multicast routing protocols under scenarios ...

Abstract

The stationary nature of nodes in a mesh network has shifted the main design goal of routing protocols from maintaining connectivity between source and destination nodes to finding high-throughput paths between them. In recent years, numerous link-quality-based routing metrics have been proposed for choosing high-throughput paths for unicast protocols. In this paper we study routing metrics for high-throughput tree or mesh construction in multicast protocols. We show that there is a fundamental difference between unicast and multicast routing in how data ...

Abstract

In this paper, we address the problem of real-time video communication over wireless ad hoc networks. For the unicast case, we propose a robust, multipath source routing protocol for both interactive and video on-demand applications. Simulations show that our proposed scheme enhances the quality of video applications as compared to the existing protocols. For the multicast case, we propose multiple tree multicast streaming as a way to provide robustness for video multicast applications. Specifically, we propose a distributed double disjoint tree ...

Abstract

This paper explores the idea of exploiting the mobility of data collection points (sinks) for the purpose of increasing the lifetime of a wireless sensor network with energy-constrained nodes. We give a novel linear programming formulation for the joint problems of determining the movement of the sink and the sojourn time at different points in the network that induce the maximum network lifetime. Differently from previous solutions, our objective function maximizes the overall network lifetime (here defined as the time till ...

Abstract

We focus on one critical issue in mobile ad hoc networks that is multicast routing. Advantages and limitations of existing routing protocols are illustrated. Optimal routes, stable links, power conservation, loop freedom, and reduced channel overhead are the main features to be addressed in a more efficient mechanism. In this paper, we propose a new on-demand multicast routing protocol, named Source Routing-based Multicast Protocol (SRMP). Our proposition addresses two important issues in solving routing problems: (i) path availability concept, and (ii) ...

Abstract

Preemptive route maintenance allows a routing algorithm to maintain connectivity by preemptively switching to a path of higher quality when the quality of the currently used path is deemed questionable. Preemptive routing initiates recovery actions early by detecting that a link is likely to be broken soon and searching for a new path before the current path actually breaks. Preemptive route maintenance has been used for unicast (point-to-point) communications in wired networks and in mobile ad-hoc networks (MANETs) to minimize the ...

Abstract

We examine on-demand multicasting in ad hoc networks. We study a wide range of simulation scenarios and identify key limitations of MAODV. Based on our findings, we propose a number of changes in MAODV, and call the resulting protocol robust multicasting in ad hoc networks using trees (ROMANT). We compare ROMANT to MAODV and ODMRP, for a wide range of simulation scenarios. Our results indicate that ROMANT effectively eliminates the limitations of MAODV. Moreover, it provides comparable or better packet delivery ...

Abstract

In this paper, we propose and investigate a bandwidth-efficient multicast routing protocol for ad-hoc networks. The proposed protocol achieves low communication overhead, namely, it requires a small number of control packet transmissions for route setup and maintenance. The proposed protocol also achieves high multicast efficiency, namely, it delivers multicast packets to receivers with a small number of transmissions. In order to achieve low communication overhead and high multicast efficiency, the proposed protocol employs the following mechanisms: (1) on-demand invocation of the ...

Abstract

The conceptual shift in the expectations of the wireless users from voice towards multimedia, from availability towards acceptable quality, and from stand-alone towards group-oriented computing has a significant impact on today's networks in terms of the need for mobility, quality of service (QoS) and multicasting. Ad hoc networks, being independent of any fixed infrastructure, can provide mobile users with these features, if necessary QoS multicasting strategies are developed. The aim of this article is to define the building blocks of such ...

Abstract

Multicast has emerged as a very desirable feature in communication networks. With multicast, data can be distributed to multiple recipients in an efficient and economical manner. We present a performance evaluation of a novel multicast routing strategy for a mobile ad hoc network environment, which is characterized by a highly-dynamic topology with constrained bandwidth and limited power. The associativity-based ad hoc multicast (ABAM) protocol establishes multicast session on demand and utilizes an association stability concept, which is introduced in the ABR ...

Abstract

The Adaptive Demand-Driven Multicast Routing protocol (ADMR) has been designed specifically for use in the ad hoc network environment. Multicast routing state in ADMR is dynamically established and maintained only for groups that have at least one receiver and one active sender in the network. Each multicast data packet is forwarded along the shortest-delay path with multicast forwarding state, from the sender to the receivers. Senders are ...

Abstract

There is increasing research interest in solving routing problems in sensor networks subject to constraints such as data correlation, link reliability and energy conservation. Since information concerning these constraints are unknown in an environment, a reinforcement learning approach is proposed to solve this problem. To this end, we deploy a Bayesian method to offer good balance between exploitation and exploration. It estimates the benefit of exploration by value of information therefore avoids the error-prone process of parameter tuning which usually requires ...

Abstract

One of the main challenges of securing multicast communication is source authentication, or enabling receivers of multicast data to verify that the received data originated with the claimed source and was not modified enroute. The problem becomes more complex in common settings where other receivers of the data are not trusted, and where lost packets are not retransmitted. ...

Abstract

An ad hoc network is a group of wireless mobile computers (or nodes), in which individual nodes cooperate by forwarding packets for each other to allow nodes to communicate beyond direct wireless transmission range. Prior research in ad hoc networking has generally studied the routing problem in a non-adversarial setting, assuming a trusted environment. In this paper, we present attacks against routing in ad hoc networks, and we present the design and performance evaluation of a new secure on-demand ad hoc ...