Mobile devices such as personal digital assistants (PDAs) and smartphones are widely used not only in our everyday lives but also in various industrial fields. Most of these mobile devices have multiple wireless network interfaces, such as Bluetooth, 3G, and Wi-Fi. A considerable amount of energy is consumed to transfer the data through wireless communication. Moreover, most of these mobile devices operate on limited battery power. In industrial environments, changes in the communication environment are severe due to significant noise sources and due to distortion in the transceiver circuitry of strong motors, static frequency changers, electrical discharge devices, and other devices. It is necessary to select the network interface efficiently in order to extend the lifetimes of mobile devices and their applications. Therefore, in this paper, we propose an energy-efficient adaptive wireless network interface-selection scheme (AWNIS). Our scheme is proposed based on the mathematical modeling of energy consumption and data transfer delay patterns. Our scheme selects the best wireless network interface in terms of energy consumption by considering the link quality and adapting a dynamic network interface-selection interval according to the network environment. The simulation results show that proposed scheme effectively improves the energy efficiency while guaranteeing a certain level of data transfer delay.

Flash memory solid-state disks (SSDs) are replacing hard disk drives (HDDs) in mobile computing systems because of their lower power consumption, faster random access, and greater shock resistance. We describe Hydra, a high-performance flash memory SSD architecture that translates the parallelism inherent in multiple flash memory chips into improved performance, by means of both bus-level and chip-level interleaving. Hydra has a prioritized structure of memory controllers, consisting of a single high-priority foreground unit, to deal with read requests, and multiple background units, all capable of autonomous execution of sequences of high-level flash memory operations. Hydra also employs an aggressive write buffering mechanism based on block mapping to ensure that multiple flash memory chips are used effectively, and also to expedite the processing of write requests. Performance evaluation of an FPGA implementation of the Hydra SSD architecture shows that its performance is more than 80 percent better than the best of the comparable HDDs and SSDs that we considered.

Wireless industrial sensor networks are wireless sensor networks which have been adapted to industrial applications. Most techniques for wireless sensor networks can be applied to wireless industrial sensor networks. However, for industrial applications of wireless industrial sensor networks, new requirements such as real-time, reliable delivery need to be considered. In this paper, we propose EARQ, which is a novel routing protocol for wireless industrial sensor networks. It provides real-time, reliable delivery of a packet, while considering energy awareness. In EARQ, a node estimates the energy cost, delay and reliability of a path to the sink node, based only on information from neighboring nodes. Then, it calculates the probability of selecting a path, using the estimates. When packet forwarding is required, it randomly selects the next node. A path with lower energy cost is likely to be selected, because the probability is inversely proportional to the energy cost to the sink node. To achieve real-time delivery, only paths that may deliver a packet in time are selected. To achieve reliability, it may send a redundant packet via an alternate path, but only if it is a source of a packet. Experimental results show that EARQ is suitable for industrial applications, due to its capability for energy efficient, real-time, reliable communications.

As telematics and infotainment services are becoming more and more prevalent on the roadway, modern vehicles need to be equipped to support various wireless communication standards. The conventional ways for implementing those standards are dependent on their dedicated hardware chips, and thus in order to add a new standard or change an obsolete standard, a new dedicated hardware chip should be installed. Software defined radio (SDR) technology enables software components running on a generic hardware platform to perform signal processing instead of hardware chips. Thus, it is possible to support multi-standard, multi-band and multi-mode solutions and easy to enhance and reconfigure wireless communication. In this paper, we propose an SDR-based wireless communication gateway for vehicle networks. It integrates multiple wireless devices into one single wireless gateway reducing maintenance costs of hardware chips and improving flexibility, adaptability and connectivity of wireless communication. In order to provide the proof of concept, we present its application to digital multimedia broadcasting service.

The energy is the most critical resource in wireless sensor networks. Many energy efficient techniques have been studied especially in communication protocol. Among these protocols, PEGASIS proposed by Lindsey is the most superior interms of energy efficiency. In PEGASIS, all sensor nodes aggregate and transmit data along the single chain. However, this single chain causes some problems such as delay, unexpected long transmission and non-directional transmission to the sink. To resolve delay problem, PEGASIS cuts the chain into several chains. In this way, the delay can be decreased but there is new problem, wireless interference. In this paper, we propose a new chain construction algorithm to resolve above problems. The proposed algorithm minimizes the delay without the wireless interferences and maximizes the energy efficiency by removing the non-directional transmission when transmitting packets to the sink node on wireless sensor networks. Our simulation results show that our proposed algorithm can minimize the delay without expense of energy consumption.

In wireless sensor networks each sensor node has very limited resources, and it is very difficult to find and collect them. For this reason, updating or adding programs in sensor nodes must be performed via a communication channel at run-time. Many code update protocols have been developed for sensor networks, ranging from function-level update to full-image replacement. However, they provide only a fixed level of code update protocols. These protocols require manual selection of an appropriate protocol because they do not consider a cost analysis of the update protocols. In addition, they do not consider real-time response while updating codes. In this paper, we present an adaptive multilevel code update protocol (AMCUP) for real-time sensor operating systems. AMCUP enables energy-efficient code update via support for multilevel protocols (i.e., full-image, module-level, function-level, and instruction-level). It adaptively selects a protocol which meets deadline of applications and consumes less energy based on a cost analysis of several protocols. Our simulation and experimental results show that AMCUP can reduce energy consumption and execution time compared with existing single-level code update protocols while meeting deadline of the running applications.

This paper reviews Flash memory technology and flash translation layer (FTL) that provides a block device interface out of flash memory. It also describes two implementations of FTL that represent two extreme points in the spectrum of cost-performance trade-offs in FTL implementation. After presenting results on the performance and energy- efficiency of the two FTLs, this paper argues for a configurable FTL to address the diversity of mobile embedded systems in terms of cost and performance requirements.

Validation methods for hard real-time jobs are usually performed based on the maximum execution time. The actual execution time of jobs are assumed to be known only when the jobs arrive or not known until they finish. A predictable algorithm must guarantee that it can generate a schedule for any set of jobs such that the finish time for the actual execution time is no later than the finish time for the maximum execution time. It is known that any job-level fixed priority algorithm (such as earliest deadline first) is predictable. However, job-level dynamic priority algorithms (such as least laxity first) may or may not. In this paper, we investigate the predictability of a job-level dynamic priority algorithm EDZL (earliest deadline zero laxity). We show that EDZL is predictable on the domain of integers regardless of the knowledge of the actual execution times. Based on this result, furthermore, we also show that EDZL can successfully schedule any periodic task set if the total utilization is not greater than (m + 1)/2, where m is the number of processors

A new buffer replacement scheme, called DEAR (detection-based adaptive replacement), is presented for effective caching of disk blocks in the operating system. The proposed DEAR scheme automatically detects block reference patterns of applications and applies different replacement policies to different applications depending on the detected reference pattern. The detection is made by a periodic process and is based on the relationship between block attribute values, such as backward distance and frequency gathered in a period, and the forward distance observed in the next period. This paper also describes an implementation and performance measurement of the DEAR scheme in FreeBSD. The results from performance measurements of several real applications show that, compared with the LRU scheme, the proposed scheme reduces the number of disk I/Os by up to 51 percent, and the response time by up to 35 percent in the case of single application executions. For multiple application executions, the results show that the proposed scheme reduces the number of disk I/Os by up to 20 percent and the overall response time by up to 18 percent.

One of the popular network security programs supporting host access control is the 'TCP Wrapper' (Venema, 1992). TCP Wrapper is a software-only system and many computers connected to the Internet are using it. However, TCP Wrapper does 'IP address-based' access control. The IP address is not such a reliable source when authenticating a host. We point out two possible attacks against the TCP Wrapper, propose a new way to prevent them, and describe the prototype implementation, Ethernet Wrapper. By adding an Ethernet address check, we augmented the TCP Wrapper. The test results showed that Ethernet Wrapper can prevent such attacks effectively.

This paper presents a new checkpoint scheme that utilizes the memory usage profile and time series analysis for low-overhead checkpoint. The proposed checkpoint scheme checks current and future checkpoint overhead based on the on the changes of the memory size and the expected checkpoint overhead using memory profile and adaptive time series analysis when it decides whether or not to take a checkpoint. Unlike the previous works that do not utilize the memory usage profile, it is possible to reduce the total overhead of the execution time. We also present experimental results which show that the checkpoint overhead of the proposed scheme is reduced compared with the previously developed checkpoint scheme.

Vonzur Gathen proposed an efficient parallel exponentiation algorithm in finite fields using normal basis representations. In this paper we present a processor-efficient parallel exponentiation algorithm in GF(2 n ) which improves upon von zur Gathen's algorithm. We also show that exponentiation in GF(2 n ) can be done in Ο(log n) time using n/(log n)2 processors. Hence we get processor x time bound Ο(n/log n), which is optimal. Finally, we present an on-line processor assignment scheme which was missing in von zur Gathen's algorithm, and show that its time complexity is negligible.

Efficient and effective buffering of disk blocks in main memory is critical for better file system performance due to a wide speed gap between main memory and hard disks. In such a buffering system, one of the most important design decisions is the block replacement policy that determines which disk block to replace when the buffer is full, In this paper, we show that there exists a spectrum of block replacement policies that subsumes the two seemingly unrelated and independent Least Recently Used (LRU) and Least Frequently Used (LFU) policies. The spectrum is called the LRFU (Least Recently/Frequently Used) policy and is formed by how much more weight we give to the recent history than to the older history. We also show that there is a spectrum of implementations of the LRFU that again subsumes the LRU and LFU implementations. This spectrum is again dictated by how much weight is given to recent and older histories and the time complexity of the implementations lies between O(1) (the time complexity of LRU) and O(log(2) n) (the time complexity of LFU), where n is the number of blocks in the buffer, Experimental results from trace-driven simulations show that the performance of the LRFU is at least competitive with that of previously known policies for the workloads we considered.

Addresses the problem of deciding the feasibility of hard real-time periodic tasks. It is known to be a co-NP problem to determine whether a task set is feasible on one processor when there exists a task with a relative deadline that is shorter than its period in the task set. For synchronous task sets, "processor demand analysis" (PDA) has been considered as a practical tool to solve the feasibility problem. PDA determines the feasibility of a task set by checking whether a deadline is missed in an interval of finite length; this time interval is called the "test interval". The efficiency of a feasibility test method depends on the length of the test interval. In this paper, we present a new method for the feasibility testing of hard real-time periodic tasks. We show theoretically that the length of the test interval in our algorithm is shorter than or equal to existing ones. We also present experimental results that show the length of the test interval in our algorithm is, on average, significantly shorter than existing ones.

Two contributions are made in this paper. First, we show that system level characterization of file block references is inadequate for maximizing buffer cache performance. We show that a finer-grained characterization approach is needed. Though application level characterization methods have been proposed, this is the first attempt, to the best of our knowledge, to consider file level characterizations. We propose an Application/File-level Characterization (AFC) scheme where we detect on-line the reference characteristics at the application level and then at the file level, if necessary. The results of this characterization are used to employ appropriate replacement policies in the buffer cache to maximize performance. The second contribution is in proposing an efficient and fair buffer allocation scheme. Application or file level resource management is infeasible unless there exists an allocation scheme that is efficient and fair. We propose the ΔHIT allocation scheme that takes away a block from the application/file where the removal results in the smallest reduction in the number of expected buffer cache hits. Both the AFC and ΔHIT schemes are on-line schemes that detect and allocate as applications execute. Experiments using trace-driven simulations show that substantial performance improvements can be made. For single application executions the hit ratio increased an average of 13 percentage points compared to the LRU policy, with a maximum increase of 59 percentage points, while for multiple application executions, the increase is an average of 12 percentage points, with a maximum of 32 percentage points for the workloads considered.

AbstractÐEfficient and effective buffering of disk blocks in main memory is critical for better file system performance due to a wide speed gap between main memory and hard disks. In such a buffering system, one of the most important design decisions is the block replacement policy that determines which disk block to replace when the buffer is full. In this paper, we show that there exists a spectrum of block replacement policies that subsumes the two seemingly unrelated and independent Least Recently Used (LRU) and Least Frequently Used (LFU) policies. The spectrum is called the LRFU (Least Recently/Frequently Used) policy and is formed by how much more weight we give to the recent history than to the older history. We also show that there is a spectrum of implementations of the LRFU that again subsumes the LRU and LFU implementations. This spectrum is again dictated by how much weight is given to recent and older histories and the time complexity of the implementations lies between O(1) (the time complexity of LRU) and O…log 2 n† (the time complexity of LFU), where n is the number of blocks in the buffer. Experimental results from trace-driven simulations show that the performance of the LRFU is at least competitive with that of previously known policies for the workloads we considered. Index TermsÐBuffer cache, LFU, LRU, replacement policy, trace-driven simulation. 1

Causal message logging has many good properties such as nonblocking message logging and no rollback propagation. However, it requires a large amount of information to be piggybacked on each message, which may incur severe performance degradation. This paper presents an efficient causal logging algorithm based on the new message log structure, LogOn, which represents the causal interprocess dependency relation with much smaller overhead compared to the existing algorithms. The proposed algorithm is efficient in the sense that it requires no additional information other than LogOn to be carried in each message, while the other algorithms require extra information other than the message log, to eliminate the duplicates in log entries. Moreover, in those algorithms, as more extra information is added into the message, more duplicates can be detected. However, the proposed algorithm achieves the same degree of efficiency using only the message log carried in each message, without any extra information.

We develop new parallel maximum matching algorithms in interval graphs by exploiting the characteristics of interval graphs. For general interval graphs, our algorithm requires O(log/sup 2/ v+(n log n)/v) time and O(nv/sup 2/+n/sup 2/) operations on the CREW PRAM, where n is the number of intervals and v/spl les/n is a parameter. By choosing v=/spl radic/n, we obtain an O(/spl radic/n log n)-time algorithm in O(n/sup 2/) operations. For v=n/log n, we have an O(log/sup 2/ n)-time algorithm with n/sup 3//log/sup 4/ n processors. The previously best known solution takes O(log/sup 2/ n) time with n/sup 3/ processors. For proper interval graphs, our algorithm runs in O(log n) time using n/log n processors if input intervals are sorted and using n processors otherwise on the EREW PRAM. Our algorithms are much simpler than the previous ones.

We present an efficient connection caching scheme in a distributed system where we divide the system into several host groups possibly overlapping and the connection between the hosts in the same group is kept prior to others. Every host group consists of hosts which have heavy intercommunication. We present performance evaluation of the proposed connection caching scheme in several aspects including group size, grouping and types of the group. Simulation results show that host grouping is effective in every performance criterion and that proper grouping of hosts enhances the performance. We also present a simple Markov process model of our scheme and give some analysis results which are consistent with the simulation results.

An algorithm to preemptively schedule n tasks on m uniform processors is presented.It is assumed that each task is available at time 0. Associated with each task is a due time by which it is to be completed.The algorithm schedules all tasks to complete by their due times whenever possible.The asymptotic time complexity of the algorithm is O(n log n + ran).It generates O(mn) preemptions in the worst case.An example of n tasks requiring O(mn) preemptions is also presented.The algorithm can also be used when all tasks have the same due times but different release times.

Bounds are derived for the worst case performance of list schedules relative to minimum finish time schedules for uniform processor systems. The tasks to be scheduled are assumed to be independent and only nonpreemptive schedules are considered.

An $O(m^2 n + mn\log n)$ nearly on line algorithm to preemptively schedule n independent tasks on m uniform processors is presented. It is assumed that there is a release time associated with each task. No task may be started before its release time. All tasks must be completed by a common due time (if possible). Our algorithm generates schedules having $O(nm)$ preemptions in the worst case. The algorithm can also be used to minimize maximum lateness even for the case when all jobs have the same release time but different due times.