Infrastructure-as-a-Service (IaaS) cloud computing is emerging as a viable alternative to the acquisition and management of physical resources. The new main feature of IaaS cloud computing is the virtual machine (VM) technology which improves the flexibility of resource management. VMs use virtual machine images that are preconfigured and ready to run. Typically, VM image management uses local file copy and distribution via a network file system (NFS). This potentially means that a more efficient method can be used for VM image distribution. For efficient VM image management, we have designed and implemented a BitTorrent-based network block device (namely, BitNBD) for provisioning VM images in IaaS clouds. The BitNBD mainly provides a 'split read/write mechanism' to deal with concurrent VM instances where the same pieces of a VM are shared. With respect to the legacy BitTorrent protocol, the BitNBD enhances the piece picker policy and energy-saving mode. It is very effective in minimizing VM startup delays and providing a hibernating capability.

We consider the problem of placing resources in a distributed computing system so that certain performance requirements may be met while minimizing the number of resource copies needed. Resources include special I/O processors, expensive peripheral devices, or such software modules as compilers, library routines, and data files. Due to the delay in accessing each of these resources, system performance degrades as the distance between each processor and its nearest resource copy increases. Thus, every processor must be within a given distance k1 of at least one resource copy, which is called the k-bounded placement problem. The structure of a distributed computing system is represented by a graph. The k-bounded placement problem is first transformed into the problem of finding smallest k-dominating sets in a graph. Searching for smallest k-dominating sets is formulated as a state-space search problem. We derive heuristic information to speed up the search, which is then used to solve the problem with the well-known A* algorithm. An illustrative example and some experimental results are presented to demonstrate the effectiveness of the heuristic search.

In recent years, there has been a rapid and widespread proliferation of non-traditional embedded computing platforms such as digital camcorders, cellular phones, and portable medical devices. As applications become increasingly sophisticated and processing power increases, the application designer has to rely on the services provided by the real-time operating systems (RTOSs). These RTOSs must not only provide predictable services but must also be efficient and small in size. Kernel services should also be deterministic by specifying how long each service call will take to execute. Having this information allows the application designers to better plan their real-time application software so as not to miss the deadline of each task. In this paper, we propose a generalized deterministic scheduling algorithm that makes the task scheduling time constant irrespective of the number of tasks created in an application. The proposed algorithm eliminates the restriction on the maximum number of task priorities imposed on the existing ones, without additional memory overhead.

This paper deals with the problem of assigning tasks to the processors of a multiprocessor system such that the sum of execution and communication costs is minimized. If the number of processors is two, this problem can be solved efficiently using the network flow approach pioneered by Stone. This problem is, however, known to be NP-complete in the general case, and thus intractable for systems with a large number of processors. In this paper, we propose a network flow approach for the task assignment problem in homogeneous hypercube networks, i.e., hypercube networks with functionally identical processors. The task assignment problem for an n-dimensional homogeneous hypercube network of N (=2n) processors and M tasks is first transformed into n two-terminal network flow problems, and then solved in time no worse than O(M3 log N) by applying the Goldberg-Tarjan's maximum flow algorithm on each two-terminal network flow problem.

The diffraction problem of a Gaussian beam by finite number of periodic slots in a parallel-plate waveguide filled with a homogeneous dielectric is considered. The integro-differential equation for the unknown equivalent surface magnetic current density over the slots is derived and solved by the method of moments (piecewise sinusoidal Galerkin method). From some theoretical results for the angular diffraction pattern, the present geometry is observed to simulate well the previous rectangular groove geometry from the viewpoint of scattering behaviour. In addition, two types (resonance and non-resonance types) of Bragg blazing phenomena are discussed. Simultaneous Bragg and off-Bragg blazing is also demonstrated.

This letter deals with the problem of assigning tasks to the processors of a distributed computing system such that the sum of execution and communication costs is minimized. If the number of processors is two, this problem can be solved efficiently using the network flow approach pioneered by Stone. This problem is, however, known to be NP-complete in the general case, and thus intractable for systems with a large number of processors. Recently, an optimal algorithm with the time complexity of O(n2m3 log n) has been suggested for the problem of assigning m interacting tasks to a linear array of n processors. They solved the problem by using the two-terminal network flow approach. In this letter, we propose a multiterminal network flow approach for the task assignment problem in homogeneous linear array networks. The task assignment problem for a homogeneous linear array network of n processors is first transformed into (n-1) two-terminal network flow problems, and then solved in time no worse than O(nm3) by applying the Goldberg-Tarjan's network flow algorithm for each two-terminal network flow problem.

The n-dimensional hypercube is a highly concurrent loosely coupled multiprocessor based on the binary n-cube topology. This paper is concerned with the following basic graph-theoretic question: given a graph G = (V, E), is it an exact n-cube? We propose an O (|E|) hypercube recognition algorithm using some new topological properties of the hypercube graph.

We propose a dynamic voltage scaling algorithm to exploit the temporal locality called TLDVS (Temporal Locality DVS) that can achieve significant energy savings while simultaneously preserving timeliness guarantees made by real-time scheduling. Traditionally hard real-time scheduling algorithms assume that the actual computation requirement of tasks would be varied continuously from time to time, but most real-time tasks have a limited number of operational modes changing with temporal locality. Such temporal locality can be exploited for energy savings by scaling down the operating frequency and the supply voltage accordingly. The proposed algorithm does not assume task periodicity, and requires only previous execution time among a priori information on the task set to schedule. Simulation results show that TLDVS achieves up to 25% energy savings compared with OLDVS, and up to 42% over the non-DVS scheduling.

For battery based real-time embedded systems, high performance to meet their real-time constraints and energy efficiency to extend battery life are both essential. Real-Time Dynamic Voltage Scaling (RT-DVS) has been a key technique to satisfy both requirements. This paper presents EccEDF (Enhanced ccEDF), an efficient algorithm based on ccEDF. ccEDF is one of the most simple but efficient RT-DVS algorithms. Its simple structure enables it to be easily and intuitively coupled with a real-time operating system without incurring any significant cost. ccEDF, however, overlooks an important factor in calculating the available slacks for reducing the operating frequency. It calculates the saved utilization simply by dividing the slack by the period without considering the time needed to run the task. If the elapsed time is considered, the maximum utilization saved by the slack on completion of the task can be found. The proposed EccEDF can precisely calculate the maximum unused utilization with consideration of the elapsed time while keeping the structural simplicity of ccEDF. Further, we analytically establish the feasibility of EccEDF using the fluid scheduling model. Our simulation results show that the proposed algorithm outperforms ccEDF in all simulations. A simulation shows that EccEDF consumes 27% less energy than ccEDF.

Wi-Fi P2P has been deployed extensively in mobile devices. However, Wi-Fi P2P is not efficient because it requires an IP layer connection for transmitting even short messages to nearby devices, especially in high density or highly mobile environments owing to the fact that a user on the move has difficulty selecting service-available devices, and a user device has to frequently connect to and be released from nearby devices. This paper proposes a new messaging framework that enables application-level messages to be exchanged between nearby devices with no IP layer connectivity over Wi-Fi P2P. The pre-association messaging framework (PAMF) supports both broadcast and unicast transmission to maximize the delivery success rate, considering the number of peers and messages. Evaluations of PAMF conducted under real scenarios show that application-level messages can be exchanged within a few seconds, with high success rate. PAMF provides high portability and extensibility because it does not breach the Wi-Fi P2P standard. Moreover, the demonstrations show that PAMF is practical for new proximity services such as local marketing and urgent messaging.