Log-Structured Merge-Tree (LSM)-based key-value stores (LSM-KV stores) form the backbone of modern NoSQL systems due to their superior write performance. However, they are vulnerable to severe performance degradation including write stalls that can reduce throughput to nearly zero. Prior studies primarily investigate these issues under write-intensive workloads, attributing performance degradation to resource saturation or imbalances between foreground and background operations. Yet, their conclusions remain inconsistent, largely due to variations in hardware and system configurations. Moreover, real-world applications typically exhibit diverse read-write access patterns and workload intensity which are rarely examined in existing research. In this work, we conduct a comprehensive investigation of performance degradation across a broad spectrum of read-write mixed workloads, from write-dominant to read-intensive scenarios. We analyze how workload intensity, hardware resources, and key LSM-KV configuration parameters—such as background threads, block cache size, sub-compaction, and component-constraint mechanisms—jointly shape performance behaviors. Our study uncovers the root causes of degradation in both write-heavy and read-heavy regimes and highlights several underexamined factors whose interactions substantially influence system efficiency. These findings extend prior observations by revealing previously overlooked performance interactions and provide actionable guidance for configuring LSM-KV stores to mitigate degradation across diverse workloads.

As the volume of retained data continues to increase, it is important to design primary storage systems that efficiently respond to access requests while also providing strong sustainability by reducing carbon emissions. Just over two decades ago, the Massive Arrays of Idle Disks (MAID) architecture was introduced as an energy-efficient alternative to traditional HDD-based always-on storage, employing aggressive spin-down strategies to reduce power consumption. However, high access latencies and hardware limitations led to its decline. In this work, we propose a tiered SSD+MAID storage model that combines the low-latency advantages of SSDs with the energy and carbon efficiency of a MAID system, thus offering a modern alternative to MAID while achieving lower carbon emissions than all-SSD storage. To assess the sustainability impact of such a tiered storage system, we develop a comprehensive carbon emission model that incorporates access patterns, update behaviors, and HDD spin-up dynamics. This model captures both operational and embodied carbon costs, enabling evaluations of primary storage with sustainability in mind. Through real-world workloads, we evaluate the proposed SSD+MAID system and show that it can provide a good trade-off between performance, price, and sustainability.

As cloud-scale services and data-centric applications continue to generate massive volumes of data, the need for ultra-durable, energy-efficient, and cost-effective archival storage becomes increasingly urgent. Quartz glass has recently emerged as a promising archival medium, offering multi-century durability, radiation and thermal resistance, and support for three-dimensional data encoding using femtosecond laser writing. However, the hybrid mechanical-optical architecture of glass storage—requiring mechanical movement along the X and Y axes and optical focal tuning along the Z axis—introduces unique performance bottlenecks during data access, which conventional I/O scheduling strategies are not equipped to handle.In this work, we present GAIA, a Glass-Aware I/O middlewAre designed to optimize data access in quartz glass storage systems. GAIA features three coordinated strategies: (1) Zigzag Data Placement, which aligns data with the mechanical stage’s natural motion to minimize direction-switching latency; (2) Z-Axis First Placement, which prioritizes low-latency optical traversal along the depth dimension; and (3) Shortest Moving Time First (SMTF) scheduling, which selects I/O operations based on predicted movement time rather than geometric distance. Through trace-driven simulations using enterprise-scale workloads and various glass sizes, GAIA reduces data read latency by up to 82% compared to traditional baseline schedulers. These results demonstrate the critical importance of middleware-level co-design in unlocking the performance potential of next-generation glass-based storage systems.

DNA is a high-density long-lasting storage medium that has the potential to keep up with the ever-increasing data storage needs. However, DNA storage is incredibly error-prone. The more nucleotides stored in the DNA strand the greater the chance of data loss. Moreover, DNA storage faces a specific phenomenon called error propagation due to its encoding from binary to nucleotide, resulting in an even higher error rate. When the majority of relevant data is stored inside the DNA strand error propagation is limited to the single strand. Reducing the overall data stored in DNA allows for more error correction and error protection. In this paper, we propose an isolation and deduplication scheme called Pixel-DNA for images. PixelDNA uses specific properties of DNA and DNA strands to implement multiple levels of deduplication while maximizing the data isolation. Also, a data segmentation scheme is applied to further increase the density of DNA storage. Based on the experimental results, Pixel-DNA allows for increased robustness and recoverability of images while increasing the density of DNA storage capacity.

We present TieredKV, a novel tiered key-value store that seamlessly integrates a Log-Structured Merge (LSM) tree with a Learned Index to achieve superior read and write performance on storage systems. While existing approaches use learned indexes primarily as auxiliary components within LSM trees, TieredKV employs a two-tier design where the LSM tree handles recent write operations while a separate Learned Index accelerates read performance. Our design includes a non-blocking conversion mechanism that efficiently transforms LSM data into a Learned Index during garbage collection, maintaining high performance without interrupting operations. TieredKV dramatically reduces LSM size through this tiered approach, leading to significant performance gains in both reads and writes. Extensive evaluations across diverse workloads show that TieredKV outperforms state-of-the-art LSM-based solutions by up to 4.32x for read operations and 1.43x for writes, and achieves up to 7.9x better overall performance compared with on-storage Learned Index. The system demonstrates robust performance across different data distributions, access patterns, and storage media including both SSDs and HDDs.

Data deduplication relies on a chunk index to identify the redundancy of incoming chunks. As backup data scales, it is impractical to maintain the entire chunk index in memory. Consequently, an index lookup needs to search the portion of the on-storage index, causing a dramatic regression of index lookup throughput. Existing studies propose to search a subset of the whole index (partial index) to limit the storage I/Os and guarantee a high index lookup throughput. However, several core factors of designing partial indexing are not fully exploited. In this paper, we first comprehensively investigate the trade-offs of using different meta-groups, sampling methods, and meta-group selection policies for a partial index. We then propose a Collaborative Partial Index (CPI) which takes advantage of two meta-groups including recipe-segment and container-catalog to achieve more efficient and effective unique chunk identification. CPI further introduces a hook-entry sharing technology and a two-stage eviction policy to reduce memory usage without hurting the deduplication ratio. According to evaluation, with the same constraints of memory usage and storage I/O, CPI achieves a 1.21x-2.17x higher deduplication ratio than the state-of-the-art partial indexing schemes. Alternatively, CPI achieves 1.8X-4.98x higher index lookup throughput than others when the same deduplication ratio is achieved. Compared with full indexing, CPI's maximum deduplication ratio is only 4.07% lower but its throughput is 37.1x - 122.2x of that of full indexing depending on different storage I/O constraints in our evaluation cases.

As the volume of data is rapidly produced every day, there is a need for the storage media to keep up with the growth rate of digital data created. Despite emerging storage solutions that have been proposed such as Solid State Drive with quad-level cells or penta-level cells, Shingled Magnetic Recording, Linear Tape-Open, and so on, these technologies still fall short of meeting the demand for preserving huge amounts of available data. Moreover, current storage solutions have a limited lifespan, often lasting just a few years. To ensure long-term preservation, data must be continuously migrated to new storage drives. Therefore, there is a need for alternative storage technologies that not only offer high storage capacity but also long persistency. In contrast to existing storage devices, Synthetic Deoxyribonucleic Acid (DNA) storage emerges as a promising candidate for archival data storage, offering both high-density storage capacity and the potential for long-term data preservation. In this article, we will introduce DNA storage, discuss the capabilities of DNA storage based on the current biotechnologies, discuss possible improvements in DNA storage, and explore further improvements with future technologies. Currently, the limitations of DNA storage are due to its weaknesses including high error rates, long access latency, and so on. In this article, we will focus on possible DNA storage research issues based on its relevant bio and computer technologies. Also, we will provide potential solutions and forward-looking predictions about the development and the future of DNA storage. We will discuss DNA storage from the following five perspectives: (1) We will describe the basic background of DNA storage including the basic technologies of read/write DNA storage, data access processes such as Polymerase Chain Reaction-based random access, encoding schemes from digital data to DNA, and required DNA storage format. (2) We will describe the issues of DNA storage based on the current technologies including bio-constraints during the encoding process such as avoiding long homopolymers and containing certain GC contents, different types of errors in synthesis and sequencing processes, low practical capacity with the current technologies, slow read and write performance, and low encoding density for random accesses. (3) Based on the previously mentioned issues, we will summarize the current solutions for each issue, and also give and discuss the potential solutions based on the future technologies. (4) From a system perspective, we will discuss how the DNA storage system will look if the DNA storage becomes commercialized and is widely equipped in archive systems. Some questions will be discussed, including: (i) How do we efficiently index data in DNA storage? (ii) What is a good storage hierarchical storage system with DNA storage? (iii) What will DNA storage be like with the development of technology? (5) Finally, we will provide a comparison with other competitive technologies.

Deoxyribonucleic Acid (DNA), with its ultra-high storage density and long durability, is a promising long-term archival storage medium and is attracting much attention today. A DNA storage system encodes and stores digital data with synthetic DNA sequences and decodes DNA sequences back to digital data via sequencing. Many encoding schemes have been proposed to enlarge DNA storage capacity by increasing DNA encoding density. However, only increasing encoding density is insufficient because enhancing DNA storage capacity is a multifaceted problem.

Storage tiering (e.g., SSD+HDD) is designed to achieve a better tradeoff between performance and cost-effectiveness for storage systems. With the development of Shingled Magnetic Recording (SMR) drives, replacing conventional HDD with a higher density of SMR drives in tiered storage can further improve cost-effectiveness. However, with data tracks overlapped in SMR drives, the "non-sequential' writes in SMR drives cause explicit performance penalties, which is the most challenging issue of using SMR drives in storage tiering.In this paper, we present SMRTS, a file system for SSD-SMR tiered storage with data deduplication. First, SMRTS deduplicates the files being migrated from SSD to SMR to solve the non-sequential write issue of SMR drives and further optimize the space utilization. Second, to address the performance overhead caused by deduplication, we propose file recipe reuse and refresh, hints-based container allocations, and fast container validation to address the penalties caused by data fragmentations. We conduct experimental evaluations of SMRTS using both benchmarks and real-world workloads. The evaluation results show that compared with a compatible file system on SSD+HDD tiered storage, SMRTS achieves a similar performance but provides a much larger space (at least 1.25X). The proposed optimizations improve migration performance up to 17X.

Kubernetes (k8s) is a system for managing containerized applications across multiple hosts. It offers automatic deployment, maintenance, scaling, and resource management for applications. Applications in k8s usually have different storage requirements in the form of service-level objectives (SLOs). However, the current k8s storage management has several limitations which cause explicit performance and cost overhead. K8s administrators have to configure storage in advance manually, and users must know configurations and capabilities of provided storage. Users' storage SLOs can be easily violated in k8s.In this paper, we design and implement k8s Enhanced Storage (k8sES) which efficiently supports applications with various storage SLOs along with all other requirements in the Kubernetes environment. We design and incorporate storage scheduling as part of the node scheduling process in k8s. Applications will be scheduled onto the correct nodes and storage without intervention from either users or administrators. Proper storage resources will be dynamically carved based on users' storage SLOs. In addition, we provide a tool to monitor the I/O activities of both applications and storage devices in k8sES. The evaluation shows that k8sES can better meet users' storage SLOs along with other requirements. Also, k8sES can achieve higher resource utilization efficiency with overhead similar to that of the current k8s.

With the rapid increase of available digital data, Deoxyribonucleic Acid (DNA) storage is identified as such a promising candidate due to its long persistency and high areal density, especially for archival storage systems. However, due to biochemical constraints, currently the encoding densities of various DNA storage systems are much less than this upper bound. In this paper, we propose a new Digital Pattern-aware DNA encoding scheme, called DP-DNA, which satisfies the DNA biochemical constraints and efficiently stores digital data in DNA storage with high encoding density. To satisfy the biochemical constraints, our proposed scheme is based on several rotation codes. DP-DNA first analyzes the patterns of each short binary sequence, which will be encoded to a DNA strand, and then selects an appropriate code for encoding the target binary sequence to achieve a high encoding density. An additional encoding field is added to the DNA encoding format, which can distinguish the encoding scheme used for each DNA strand, and thus we can decode DNA data back to its original digital data. Moreover, a new 2bit-code with the highest encoding density (i.e., 2bits/nt) is proposed to add to the pool of code candidates to further increase the encoding density. In addition, a variable-length scheme is applied to increase the feasibility of using 2bit-code scheme. Finally, the experimental results indicate that the proposed DP-DNA achieves 5.9% - 103.5% higher encoding density than the existing encoding schemes with various datasets.

Emerging Nov-Volatile Memory (NVM) may replace DRAM as main memory in future computers. However, data will likely still be stored on storage due to the enormous large size of available data. We investigate how key-value stores can be efficiently designed and implemented in a hybrid system, called NVM-Storage system, consisting of NVM as memory and traditional storage. We first discuss the performance trade-offs among Put, Get, and Range Query of the existing designs. Then, we propose PMDB, a range-based key-value store on NVM-Storage systems. PMDB achieves good performance for Put, Get and Range Query at the same time by utilizing a range-based data management and deploying a light-weight index on NVM. We compare PMDB with the state-of-the-art schemes including SLM-DB [21] and MatrixKV [40] for hybrid NVM-storage systems. Evaluation results indicate that in workloads with mixed Put, Get and Range Queries, PMDB outperforms existing key-value stores by$1.16\times$–$2.49\times$.

As emerging memory technologies (e.g., non-volatile memory (NVM)) coming out and machine learning algorithms successfully applying to different fields, the potentials of cache replacement policy for NVM-based systems with the integration of machine learning algorithms are worthy of being exploited to improve the performance of computer systems. In this work, we proposed a machine learning based cache replacement algorithm, named ExpCache, to improve the system performance with NVM as the main memory. By considering the non-volatility characteristic of the NVM devices, we split the whole NVM into two caches, including a read cache and a write cache, for retaining different types of requests. The pages in each cache are managed by both LRU and LFU policies for balancing the recency and frequency of workloads. The online Expert machine learning algorithm is responsible for selecting a proper policy to evict a page from one of the caches based on the access patterns of workloads. In experimental results, the proposed ExpCache outperforms previous studies in terms of hit ratio and the number of dirty pages written back to storage.

With the storage's demand for high density and long-term preservation, Deoxyribonucleic Acid (DNA) has become a promising candidate to satisfy the requirement of archival storage for rapidly increased digital volume. However, due to the biochemical constraints, DNA storage faces critical issues of low practical capacity and robustness. In this paper, we target image applications and propose to apply approximation to DNA storage to improve the overall encoding density and robustness of DNA storage by using a hybrid lossy and lossless encoding scheme (called HL-DNA). Several lossy and lossless encoding schemes (lossy and lossless codes) are proposed and used to encode incoming binary sequences. These two types of codes are coordinated to balance the encoding density and errors. The lossless codes are used to limit the errors and the lossy codes are used to improve the encoding density. Moreover, the introduced approximation and newly proposed hybrid encoding schemes in one DNA strand can improve the robustness of DNA storage. Finally, the experimental results indicate that the proposed HL-DNA improves the encoding density of DNA storage and makes it much close to the ideal case. Also, HL-DNA achieves higher robustness to the injected errors than other DNA storage codes.

Hybrid storage systems are prevalent in most large-scale enterprise storage systems since they balance storage performance, storage capacity and cost. The goal of such systems is to serve the majority of the I/O requests from high-performance devices and store less frequently used data in low-performance devices. A large data migration volume between tiers can cause a huge overhead in practical hybrid storage systems. Therefore, how to balance the trade-off between the migration cost and potential performance gain is a challenging and critical issue in hybrid storage systems. In this paper, we focused on the data migration problem of hybrid storage systems with two classes of storage devices. A machine learning-based migration algorithm called K-Means assisted Support Vector Machine (K-SVM) migration algorithm is proposed. This algorithm is capable of more precisely classifying and efficiently migrating data between performance and capacity tiers. Moreover, this K-SVM migration algorithm involves a K-Means clustering algorithm to dynamically select a proper training dataset such that the proposed algorithm can significantly reduce the volume of migrating data. Finally, the real implementation results indicate that the ML-based algorithm reduces the migration data volume by about 40% and achieves 70% lower latency than other algorithms.

Active storage devices and in-storage computing are proposed and developed in recent years to effectively reduce the amount of required data traffic and to improve the overall application performance. They are especially preferred in the compute-storage disaggregated infrastructure. In both techniques, a simple computing module is added to storage devices/servers such that some stored data can be processed in the storage devices/servers before being transmitted to application servers. This can reduce the required network bandwidth and offload certain computing requirements from application servers to storage devices/servers. However, several challenges exist when designing an in-storage computing- based architecture for applications. These include what computing functions need to be offloaded, how to design the protocol between in-storage modules and application servers, and how to deal with the caching issue in application servers. HBase is an important and widely used distributed Key-Value Store. It stores and indexes key-value pairs in large files in a storage system like HDFS. However, its performance especially read performance, is impacted by the heavy traffics between HBase RegionServers and storage servers in the compute-storage disaggregated infrastructure when the available network bandwidth is limited. We propose an I n- S torage-based HBase architecture, called IS-HBase , to improve the overall performance and to address the aforementioned challenges. First, IS-HBase executes a data pre-processing module ( I n- S torage S can N er, called ISSN ) for some read queries and returns the requested key-value pairs to RegionServers instead of returning data blocks in HFile. IS-HBase carries out compactions in storage servers to reduce the large amount of data being transmitted through the network and thus the compaction execution time is effectively reduced. Second, a set of new protocols is proposed to address the communication and coordination between HBase RegionServers at computing nodes and ISSNs at storage nodes. Third, a new self-adaptive caching scheme is proposed to better serve the read queries with fewer I/O operations and less network traffic. According to our experiments, the IS-HBase can reduce up to 97% network traffic for read queries and the throughput (queries per second) is significantly less affected by the fluctuation of available network bandwidth. The execution time of compaction in IS-HBase is only about 6.31% – 41.84% of the execution time of legacy HBase. In general, IS-HBase demonstrates the potential of adopting in-storage computing for other data-intensive distributed applications to significantly improve performance in compute-storage disaggregated infrastructure.

To bridge the giant semantic gap between applications and modern storage systems, passing a piece of tiny and useful information, called I/O access hints, from upper layers to the storage layer may greatly improve application performance and ease data management in storage systems. This is especially true for heterogeneous storage systems that consist of multiple types of storage devices. Since ingesting external access hints will likely involve laborious modifications of legacy I/O stacks, it is very hard to evaluate the effect and take advantages of access hints. In this article, we design a generic and flexible framework, called HintStor, to quickly play with a set of I/O access hints and evaluate their impacts on heterogeneous storage systems. HintStor provides a new application/user-level interface, a file system plugin, and performs data management with a generic block storage data manager. We demonstrate the flexibility of HintStor by evaluating four types of access hints: file system data classification, stream ID, cloud prefetch, and I/O task scheduling on a Linux platform. The results show that HintStor can execute and evaluate various I/O access hints under different scenarios with minor modifications to the kernel and applications.

NAND-based flash memory has become a prevalent storage media due to its low access latency and high performance. By setting up different incremental step pulse programming (ISPP) values and threshold voltages, the tradeoffs between lifetime and access latency in NAND-based flash memory can be exploited. The existing studies that exploit the tradeoffs by using heuristic algorithms do not consider the dynamically changed access latency due to wearing-out, resulting in low access performance. In this paper, we proposed a new Elastic Flash Management scheme, called EFM, to manage data in hybrid flash memory, which consists of multiple physical regions with different read/write latencies according to their ISPP values and threshold voltages. EFM includes a Long-Term Classifier (LT-Classifier) and a Short-Term Classifier (ST-Classifier) to accurately track dynamically changed workloads by considering current quantitative differences of read/write latencies and workload access patterns. Moreover, a reduced effective wearing management is proposed to prolong the lifetime of flash memory by scheduling write-intensive workloads to the region with a reduced threshold voltage and the lowest write cost. Experimental results indicate that EFM reduces the average read/write latencies by about 54% - 296% and obtain 17.7% lifetime improvement on average compared to the existing studies.

Due to the intrinsic properties of Solid-State Drives (SSDs), invalid data remain in SSDs before erased by a garbage collection process, which increases the risk of being attacked by adversaries. Previous studies use erase and cryptography based schemes to purposely delete target data but face extremely large overhead. In this paper, we propose a Workload-Aware Secure Deletion scheme, called WAS-Deletion, to reduce the overhead of secure deletion by three major components. First, the WAS-Deletion scheme efficiently splits invalid and valid data into different blocks based on workload characteristics. Second, the WAS-Deletion scheme uses a new encryption allocation scheme, making the encryption follow the same direction as the write on multiple blocks and vertically encrypts pages with the same key in one block. Finally, a new adaptive scheduling scheme can dynamically change the configurations of different regions to further reduce secure deletion overhead based on the current workload. The experimental results indicate that the newly proposed WAS-Deletion scheme can reduce the secure deletion cost by about 1.2x to 12.9x compared to previous studies.

The power and flexibility of software-defined networks lead to a programmable network infrastructure in which in-network computation can help accelerating the performance of applications. This can be achieved by offloading some computational tasks to the network. In this paper, we propose TurboKV, an efficient distributed key-value store architecture that utilizes programmable switches as: 1) partition management nodes to store the key-value store partitions and replicas information; and 2) monitoring stations to measure and balance the load among storage nodes. We also propose a key-based routing protocol to route the queries of clients based on the requested keys to targeted storage nodes. Our experimental results of an initial prototype show that our proposed architecture improves the throughput and reduces the latency of distributed key-value stores when compared to the existing architectures.

Deoxyribonucleic Acid (DNA) as a storage medium with high density and long-term preservation properties can satisfy the requirement of archival storage for rapidly increased digital volume. The read and write processes of DNA storage are error-prone. Images widely used in social media have the properties of fault tolerance which are well fitted to the DNA storage. However, prior work simply investigated the feasibility of DNA storage storing different types of data and simply store images in DNA storage, which did not fully investigate the fault-tolerant potential of images in the DNA storage. In this paper, we proposed a new image-based DNA system called IMG-DNA, which can efficiently store images in DNA storage with improved DNA storage robustness. First, a new DNA architecture is proposed to fit JPEG-based images and improve the image's robustness in DNA storage. Moreover, barriers inserted in DNA sequences efficiently prevent error propagation in images of DNA storage. The experimental results indicate that the proposed IMG-DNA achieves much higher fault-tolerant than prior work.

Interlaced Magnetic Recording (IMR) is a promising technology which achieves higher data density and lower write amplification (WA) than Shingled Magnetic Recording (SMR). In IMR, top tracks and bottom tracks are interlaced so each bottom track is partially overlapped with two adjacent top tracks. Top tracks can be updated without any WA, but bottom track updates require reading and rewriting of affected valid data on the two neighboring top tracks. There are few published studies discussing WA in IMR drives. We propose TrackLace to reduce WA for IMR. TrackLace consists of three techniques: Z-Alloc allocates user data to the tracks in alternating directions and spreads unallocated tracks among allocated tracks; Top-Buffer opportunistically utilizes unallocated top tracks to buffer bottom track updates; and Block-Swap progressively swaps bottom track hot data with top track cold data during high space utilization. To further optimize TrackLace performance, we propose a virtual frame design that can keep the relocated block (due to Top-Buffer or Block-Swap) close to its original location and an adaptive buffering mechanism that can avoid unnecessary redirections depending on the write locality. Evaluations show that TrackLace can reduce WA by 45 percent and lower average latency by 31percent compared with baseline schemes.

In the cloud environment, most services are provided by virtual machines (VMs). Identifying storage requirements of VMs is challenging, but it is essential for good user experiences while optimizing use of storage resources. Determining the storage configuration necessary to support and satisfy VMs first requires an accurate description of the VM configurations, and the problem is further exacerbated by the diversity and special characteristics of the VMs. In this paper, we study Virtual Desktop Infrastructure (VDI), a prevalent and complicated VM application, to identify and characterize storage requirements of VMs and determine how to meet such requirements with minimal storage resources and cost. We first create a model to describe the behavior of VDI, and we collect real VDI traces to populate this model. The model allows us to identify the storage requirements of VDI and determine the potential bottlenecks of a given storage configuration. Based on this information, we can tell what capacity and minimum capability a storage configuration needs in order to support and satisfy given VDI configurations. We show that our model can describe more fine-grained VM behavior varying with time and virtual disk types compared with the rules of thumb currently used in industry.

Hybrid Shingled Magnetic Recording (H-SMR) drives are the most recently developed SMR drives, which allow dynamic conversion of the recording format between Conventional Magnetic Recording (CMR) and SMR on a single disk drive. We identify the unique opportunities of H-SMR drives to manage the tradeoffs between performance and capacity, including the possibility of adjusting the SMR area capacity based on storage usage and the flexibility of dynamic data swapping between the CMR area and SMR area. We design and implement FluidSMR, an adaptive management scheme for hybrid SMR Drives, to fully utilize H-SMR drives under different workloads and capacity usages. FluidSMR has a two-phase allocation scheme to support a growing usage of the H-SMR drive. The scheme can intelligently determine the sizes of the CMR and the SMR space in an H-SMR drive based on the dynamic changing of workloads. Moreover, FluidSMR uses a cache in the CMR region, managed by a proposed loop-back log policy, to reduce the overhead of updates to the SMR region. Evaluations using enterprise traces demonstrate that FluidSMR outperforms baseline schemes in various workloads by decreasing the average I/O latency and effectively reducing/controlling the performance impact of the format conversion between CMR and SMR.

Computer systems utilizing byte-addressable Non-Volatile Memory ( NVM ) as memory/storage can provide low-latency data persistence. The widely used key-value stores using Log-Structured Merge Tree ( LSM-Tree ) are still beneficial for NVM systems in aspects of the space and write efficiency. However, the significant write amplification introduced by the leveled compaction of LSM-Tree degrades the write performance of the key-value store and shortens the lifetime of the NVM devices. The existing studies propose new compaction methods to reduce write amplification. Unfortunately, they result in a relatively large read amplification. In this article, we propose NVLSM, a key-value store for NVM systems using LSM-Tree with new accumulative compaction. By fully utilizing the byte-addressability of NVM, accumulative compaction uses pointers to accumulate data into multiple floors in a logically sorted run to reduce the number of compactions required. We have also proposed a cascading searching scheme for reads among the multiple floors to reduce read amplification. Therefore, NVLSM reduces write amplification with small increases in read amplification. We compare NVLSM with key-value stores using LSM-Tree with two other compaction methods: leveled compaction and fragmented compaction. Our evaluations show that NVLSM reduces write amplification by up to 67% compared with LSM-Tree using leveled compaction without significantly increasing the read amplification. In write-intensive workloads, NVLSM reduces the average latency by 15.73%–41.2% compared to other key-value stores.

Host-Aware/Drive-Managed Shingled Magnetic Recording (SMR) drives can accept non-sequential writes using a buffer called media cache. Data in the media cache will be migrated to its designated location by a cleaning process if the buffer is full (blocking cleaning) or the drive is idle (idle cleaning). However, blocking cleanings can severely extend the I/O response time. Therefore, it is crucial to fully understand the cleaning process and find ways of mitigating the caused performance degradation. In this article we further evaluate the cleaning process and propose a potential remedy scheme called Idler on Host-Aware SMR drives. Idler adaptively induces idle cleanings based on dynamic workload characteristics and media cache usages to reduce the severity of blocking cleanings. Our evaluations show that in the workloads with a small non-sequential write ratio (about 10 percent), Idler can reduce the tail response time and the workload finish time by 56-88 and 10-23 percent, respectively, compared with those without such control. With the help of an external write buffer on an SSD, the tail response time of SMR drives with Idler can be closer to that of conventional disk drives.

With the increasing concerns of security, the secure deletion for SSDs becomes very costly due to its out-of-place update (i.e., an update is performed in a new location leaving the old data un-touched). Some previous studies used a combined erase-based and cryptography-based method to find a heuristic deletion scheme. However, the deletion overhead is still large since a key may be associated with too many pages. Therefore, how to reduce the secure deletion overhead further is becoming an interesting research issue. In this paper, a temperature-aware secure deletion scheme (TASecure) is proposed. Data with the same temperature are stored in the same region in order to reduce the overhead of secure deletion. The temperature of a data is referred to the frequency of the data is updated. Moreover, the regions based on their temperature are associated with different numbers of keys and are applied with different secure deletion schemes. Finally, the experimental results indicate that our proposed secure deletion scheme can reduce the secure deletion cost about 1.2x to 19x compared to previous studies.

Solid state drive (SSD) as a fast storage device has been playing an important role across many applications from mobile computing to large distributed systems in recent years. However, the performance of the SSD can be degraded tremendously due to the intrinsic properties of NAND-based flash memory including limited erase cycles and asymmetric write and erase operations. Previous works separated hot/cold data into different blocks in order to improve SSD performance. “Hotness” is typically defined as the cumulative update frequencies of pages. However, we believe that an additional new parameter, average update time interval, should also be considered into the “hotness” definition associated with the update frequency. Moreover, to adaptively classify hot/cold data, a machine learning algorithm is applied to better accommodate the dynamically changed I/O access patterns of traces. In this paper, a machine learning (ML) based SSD management called HAML-SSD is proposed. The purpose of applying the ML algorithm is to dynamically cluster the data with similar “hotness” based on a new definition of “hotness”. Thus, a two-dimension clustering algorithm is used for storing the pages categorized into the same cluster within the same block. Moreover, to obtain reasonable training time, a specific hardware component called HAML-unit is designed in the SSD. Finally, the experimental results indicate that the HAML-SSD decreases the response time around 26.3% - 57.7% compared to previous works with the evaluation of real traces.

This paper presents a Virtual Persistent Cache design to remedy the long latency behavior and to ultimately improve the write responsiveness of the Host-Aware Shingled Magnetic Recording (HA-SMR) drives. Our design keeps the cost-effective model of the existing HA-SMR drives, but at the same time asks the great help from the host system for adaptively providing some computing and management resources to improve the drive performance when needed. The technical contribution is to trick the HA-SMR drives by smartly reshaping the access patterns to HA-SMR drives, so as to avoid the occurrences of long latencies in most cases and thus to ultimately improve the drive performance and responsiveness. We conduct experiments on real Seagate 8 TB HA-SMR drives to demonstrate the advantages of Virtual Persistent Cache over the real workloads from Microsoft Research Cambridge. The results show that the proposed design can remedy most of the long latencies and improve the drive performance by at least 58.11 percent, under the evaluated workloads.

With the rapid increase in the amount of data produced and the development of new types of storage devices, storage tiering continues to be a popular way to achieve a good tradeoff between performance and cost-effectiveness. In a basic two-tier storage system, a storage tier with higher performance and typically higher cost (the fast tier) is used to store frequently-accessed (active) data while a large amount of less-active data are stored in the lower-performance and low-cost tier (the slow tier). Data are migrated between these two tiers according to their activity. In this article, we propose a Tier-aware Data Deduplication-based File System, called TDDFS, which can operate efficiently on top of a two-tier storage environment. Specifically, to achieve better performance, nearly all file operations are performed in the fast tier. To achieve higher cost-effectiveness, files are migrated from the fast tier to the slow tier if they are no longer active, and this migration is done with data deduplication. The distinctiveness of our design is that it maintains the non-redundant (unique) chunks produced by data deduplication in both tiers if possible. When a file is reloaded (called a reloaded file) from the slow tier to the fast tier, if some data chunks of the file already exist in the fast tier, then the data migration of these chunks from the slow tier can be avoided. Our evaluation shows that TDDFS achieves close to the best overall performance among various file-tiering designs for two-tier storage systems.

Integrating solid-state drives (SSDs) and host-aware shingled magnetic recording (HA-SMR) drives can potentially build a cost-effective high-performance storage system. However, existing SSD tiering and caching designs in such a hybrid system are not fully matched with the intrinsic properties of HA-SMR drives due to their lacking consideration of how to handle non-sequential writes (NSWs). We propose ZoneTier, a zone-based storage tiering and caching co-design, to effectively control all the NSWs by leveraging the host-aware property of HA-SMR drives. ZoneTier exploits real-time data layout of SMR zones to optimize zone placement, reshapes NSWs generated from zone demotions to SMR preferred sequential writes, and transforms the inevitable NSWs to cleaning-friendly write traffics for SMR zones. ZoneTier can be easily extended to match host-managed SMR drives using proactive cleaning policy. We implemented a prototype of ZoneTier with user space data management algorithms and real SSD and HA-SMR drives, which are manipulated by the functions provided by libzbc and libaio. Our experiments show that ZoneTier can reduce zone relocation overhead by 29.41% on average, shorten performance recovery time of HA-SMR drives from cleaning by up to 33.37%, and improve performance by up to 32.31% than existing hybrid storage designs.

The T10 DIF (Data Integrity Field) and DIX (Data Integrity Extension) specifications provide mechanisms to guarantee end-to-end data integrity and protection in the face of silent data corruption in modern storage systems. However, the Multiple Devices (MD) software RAID driver in Linux does not fully leverage these capabilities to provide such end-to-end guarantees with widely-used RAID modes such as 5 and 6, thereby causing an "integrity gap" in the Linux I/O stack. This paper describes the design and performance characteristics of a DIX-aware MD module that plugs this integrity gap with minimal overhead to client applications. A PI (Protection Information) operator is added in MD to handle the PI-related operations, and dedicated buffers for PI are allocated and managed in MD RAID-5/6 personality's stripe structures to generate, store, and verify the PI. This allows seamless exchange of PI information among end-applications running in user mode, file systems, the linux block layer, and PI-capable HBAs and drives. Our evaluations show that the DIX-aware MD module has the capability of detecting SDC with the tolerable performance penalty.

In multi-tier storage systems, moving data from one tier to the next can be inefficient. And because each type of storage device has its own idiosyncrasies with respect to the workloads that it can best support, unnecessary data movement might result. In this paper, we explore a fully connected storage architecture in which data can move from any storage pool to another. We propose a Chunk-level storage-aware workload Analyzer framework, abbreviated as ChewAnalyzer, to facilitate efficient data placement. Access patterns are characterized in a flexible way by a collection of I/O accesses to a data chunk. ChewAnalyzer employs a Hierarchical Classifier [1] to analyze the chunk patterns step by step. In each classification step, the Chunk Placement Recommender suggests new data placement policies according to the device properties. Based on the analysis of access pattern changes, the Storage Manager can adequately distribute or migrate the data chunks across different storage pools. Our experimental results show that ChewAnalyzer improves the initial data placement and that it migrates data into the proper pools directly and efficiently.

Meeting latency SLOs (Service Level Objectives) in a networked storage environment is essential while challenging. In this environment, a storage request has to go through client I/O stacks, dynamically changing networks, and the storage system attached to a server. Its response also has to traverse all the way back to the client. Along this long I/O path, any of these components can become congested. The behavior of one component may affect the performance of the others. Isolated control on each component is not effective to meet latency SLOs of storage requests. In this paper, we propose and implement JoiNS, a system trying to guarantee latency SLO for applications that access data on a remote networked storage. JoiNS carefully considers all the components along the I/O path and controls them in a coordinated fashion. JoiNS has both global network and storage visibilities with a logically centralized controller which keeps monitoring the status of each involved component. JoiNS coordinates these components and adjusts the priority of I/O packets in each component based on the latency SLO, network and storage status, time estimation, and characteristics of each I/O request. We integrate Software Defined Network(SDN) into our system to coordinate with storage. Our evaluation shows JoiNS can achieve up to 6X speedup in this networked storage environment with various loads of background traffic.

In this paper, we propose a spatio-temporal coordination-based media access control (STMAC) protocol for efficiently sharing driving safety information in urban vehicular networks. STMAC exploits a unique spatio-temporal feature characterized from a geometric relation among vehicles to form a line-of-collision graph, which shows the relationship among vehicles that may collide with each other. Based on this graph, we propose a contention-free channel access scheme to exchange safety messages simultaneously by employing directional antenna and transmission power control. Based on an urban road layout, we propose an optimized contention period schedule by considering the arrival rate of vehicles at an intersection in the communication range of a road-side unit to reduce vehicle registration time. Using theoretical analysis and extensive simulations, it is shown that STMAC outperforms legacy MAC protocols especially in a traffic congestion scenario. In the congestion case, STMAC can reduce the average superframe duration by 66.7%, packet end-to-end delay by 68.3%, and packet loss ratio by 88% in comparison with the existing MAC protocol for vehicle-to-infrastructure communication, based on the IEEE 802.11p.

This paper proposes an evolved Self-Adaptive Interactive Navigation Tool (SAINT+) to reduce the delivery time of emergency services and to improve navigation efficiency for the vehicles influenced by accidents. To the best of our knowledge, SAINT+ is the first attempt to optimize the delivery of emergency services as well as the navigation routes of vehicles around accident areas. Based on the congestion contribution model of SAINT and aggregated information from vehicles in the vehicular cloud, we propose a virtual path reservation strategy for emergency vehicles to guarantee a fast emergency service delivery. We also develop an accident area protection scheme based on an adjusted congestion contribution matrix and protection zones to evacuate vehicles in the accident area. To further reduce travel delay of neighbor vehicles in the accident area, we also present a dynamic traffic flow control model. Through extensive simulations with a real-world map, SAINT+ outperforms other state-of-the-art schemes for the travel delay of emergency vehicles. In scenarios with a high vehicle density, SAINT+ reduces the travel delay of emergency vehicles by 42.2%.

This paper presents a Virtual Persistent Cache design to remedy the long latency behavior of the Host-Aware Shingled Magnetic Recording (HA-SMR) drive. Our design keeps the cost-effective model of the existing HA-SMR drives, but at the same time asks the great help from the host system for adaptively providing some computing and management resources to improve the drive performance when needed. The technical contribution is to trick the HA-SMR drives by smartly reshaping the access patterns to HA-SMR drives, so as to avoid the occurrences of long latencies in most cases and thus to ultimately improve the drive performance and responsiveness. We conduct experiments on real Seagate 8 TB HA-SMR drives to demonstrate the advantages of Virtual Persistent Cache over the real workloads from Microsoft Research Cambridge. The results show that the proposed design can remedy most of the long latencies and improve the drive performance by at least 58.11%, under the evaluated workloads.

With the rise of cloud storage and many data intensive applications, there is an unprecedented growth in the volume of unstructured data. In response, key-value object storage is becoming more popular for the ease with which it can store, manage, and retrieve large amounts of this data. Seagate recently launched Kinetic direct-access-over-Ethernet hard drives which incorporate a LevelDB key-value store inside each drive. In this work, we evaluate these drives using micro as well as macro benchmarks to help understand the performance limits, trade-offs, and implications of replacing traditional hard drives with Kinetic drives in data centers and high performance systems. We perform in-depth throughput and latency benchmarking of these Kinetic drives (each acting as a tiny independent server) from a client machine connected to them via Ethernet. We compare these results to a SATA-based and a faster SAS-based traditional server running LevelDB. Our sample Kinetic drives are CPU-bound, but they still average sequential write throughput of 63 MB/sec and sequential read throughput of 78 MB/sec for 1 MB value sizes. They also demonstrate unique Kinetic features including direct disk-to-disk data transfer. Our macro benchmarking using the Yahoo Cloud Serving Benchmark (YCSB) shows that mid-range LevelDB servers outperform the Kinetic drives for several workloads; however, this is not always the case. For larger value sizes, even these first generation sample Kinetic drives outperform a full server for several different workloads.

Adopting a new technology, such as a new storage system, is a complicated process because the supporting ecosystems also have to be changed. As a result, any new technology requires exhaustive performance evaluation to justify the cost of switching. However, synthetic workloads or benchmarks typically cannot completely characterize the actual workload. On the other hand, the time and effort required to obtain an appropriate trace can be prohibitive. This work presents a block-level performance measurement tool for storage systems combined with a trace re- player, a trace characteristics analyzer, and a trace re-generator. This new tool is compatible with several different platforms, including Linux and AIX. The purpose of the tool is to evaluate system performance when executing a given application, and to help users determine which system best fits their specific application. Additionally, the trace analyzer can provide details about the characteristics of a given trace. Using the trace analysis results, the re- generator can produce arbitrarily long I/O traces to improve the accuracy of the performance evaluation. The tool also can be used to determine whether a particular system can be adapted to a specific application, and to make comparisons between systems.

Shingled Magnetic Recording (SMR) drives can benefit large-scale storage systems by reducing the Total Cost of Ownership (TCO) of dealing with explosive data growth. Among all existing SMR models, Host Aware SMR (HA-SMR) looks the most promising for its backward compatibility with legacy I/O stacks and its ability to use new SMR-specific APIs to support host I/O stack optimization. Building storage systems using HA-SMR drives calls for a deep understanding of the drive's performance characteristics. To accomplish this, we conduct in-depth performance evaluations on HA-SMR drives with a special emphasis on the performance implications of the SMR-specific APIs and how these drives can be deployed in large storage systems. We discover both favorable and adverse effects of using HA-SMR drives under various workloads. We also investigate the drive's performance under legacy production environments using real-world enterprise traces. Finally, we propose a novel host-controlled buffer that can help to reduce the severity of the decline in HA-SMR performance under our discovered unfavorable I/O access patterns. Without a detailed comprehensive design, we show the potential of the host-controlled buffer by a case study.

We introduce new methods to replay intensive block I/O workloads more accurately. These methods can be used to reproduce realistic workloads for benchmarking, performance validation, and tuning of a high-performance block storage device/system. In this article, we study several sources in the stock operating system that introduce uncertainty in the workload replay. Based on the remedies of these findings, we design and develop a new replay tool called hfplayer that replays intensive block I/O workloads in a similar unscaled environment with more accuracy. To replay a given workload trace in a scaled environment with faster storage or host server, the dependency between I/O requests becomes crucial since the timing and ordering of I/O requests is expected to change according to these dependencies. Therefore, we propose a heuristic way of speculating I/O dependencies in a block I/O trace. Using the generated dependency graph, hfplayer tries to propagate I/O related performance gains appropriately along the I/O dependency chains and mimics the original application behavior when it executes in a scaled environment with slower or faster storage system and servers. We evaluate hfplayer with a wide range of workloads using several accuracy metrics and find that it produces better accuracy when compared to other replay approaches.

In cloud environment, most services are provided by virtual machines (VMs). Providing storage quality of service (QoS) for VMs is essential to user experiences while challenging. It first requires an accurate estimate and description of VM requirements, however, people usually describe this via rules of thumb. The problems are exacerbated by the diversity and special characteristics of VMs in a computing environment. This paper chooses Virtual Desktop Infrastructure (VDI), a prevalent and complicated VM application, to characterize QoS requirements of VMs and to guarantee QoS with minimal required resources. We create a model to describe QoS requirements of VDI. We have collected real VDI traces from HP to validate the correctness of the model. Then we generate QoS requirements of VDI and determine bottlenecks. Based on this, we can tell what minimum capability a storage appliance needs in order to satisfy a given VDI configuration and QoS requirements. By comparing with industry experience, we validate our model. And our model can describe more fine-grained VM requirements varying with time and virtual disk types, and provide more confidence on sizing storage for VDI as well.

Network Redundancy Elimination (NRE) aims to improve network performance by identifying and removing repeated transmission of duplicate content from remote servers. Using a Content-Defined Chunking (CDC) policy, an inline NRE process can obtain a higher Redundancy Elimination (RE) ratio but may suffer from a considerably higher computational requirement than fixed-size chunking. Additionally, the existing work on NRE is either based on IP packet level redundancy elimination or rigidly adopting a CDC policy with a static empirically-decided expected chunk size. These approaches make it difficult for conventional NRE MiddleBoxes to achieve both high network throughput to match the increasing line speeds and a high RE ratio at the same time. In this paper we present a design and implementation of an inline NRE appliance which incorporates an improved FPGA-based scheme to speed up CDC processing to match the ever increasing network line speeds while simultaneously obtaining a high RE ratio. The overhead of Rabin fingerprinting, which is a key component of CDC, is greatly reduced through the use of a record table and registers in the FPGA. To efficiently utilize the hardware resources, the whole NRE process is handled by a Virtualized NRE (VNRE) controller. The uniqueness of this VNRE that we developed lies in its ability to exploit the redundancy patterns of different TCP flows and customize the chunking process to achieve a higher RE ratio. VNRE will first decide if the chunking policy should be either fixed-size chunking or CDC. Then VNRE decides the expected chunk size for the corresponding chunking policy based on the TCP flow patterns. Implemented in a partially reconfigurable FPGA card, our trace driven evaluation demonstrates that the chunking throughput for CDC in one FPGA processing unit outperforms chunking running in a virtual CPU by nearly 3X. Moreover, through the differentiation of chunking policies for each flow, the overall throughput of the VNRE appliance outperforms one with static NRE configurations by 6X to 57X while still guaranteeing a high RE ratio.

The demand for parallel I/O performance continues to grow. However, modelling and generating parallel I/O work-loads are challenging for several reasons including the large number of processes, I/O request dependencies and workload scalability. In this paper, we propose the PIONEER, a complete solution to Parallel I/O workload characterization and gEnERation. The core of PIONEER is a proposed generic workload path, which is essentially an abstract and dense representation of the parallel I/O patterns for all processes in a High Performance Computing (HPC) application. The generic workload path can be built via exploring the inter-processes correlations, I/O dependencies as well as file open session properties. We demonstrate the effectiveness of PIONEER by faithfully generating synthetic workloads for two popular HPC benchmarks and one real HPC application.

Although supporting Quality of Service (QoS) on the traditional Internet has been extremely challenging, QoS supports are still highly desirable for many real-time applications. While existing QoS schemes often show poor scalability, low efficiency, and limited QoS supports, the fast development of Software Define Networks (SDNs) provides new opportunities to address QoS support with its centralized network control. In this paper, we propose a synchronized architecture to exploit the unique features of SDNs without conducting static reservations. Assume all routers are synchronized in time, we can precisely determine the upstream delay of a packet at a router. Meanwhile, because we also know the fairly accurate resource availability on its downstream routers (from the SDN controller), we can determine the packet's service priority on its current router based on its end-to-end (e2e) delay requirement and the expected delay that the packet may experience in its downstream. In particular, we propose a synchronized multi-hop scheduling (SMS) scheme to exploit both upstream information and downstream resource availability to speed up or slow down a packet. This is completely different from all existing per-hop or multi-hop schemes that mostly utilize upstream information. Furthermore, we propose to selectively drop a packet that is unlikely to meet its deadline. Our simulation results show that the proposed scheme outperforms existing schemes in packet missing rates.

Most computer systems currently consist of DRAM as main memory and hard disk drives (HDDs) as storage devices. Due to the volatile nature of DRAM, the main memory may suffer from data loss in the event of power failures or system crashes. With rapid development of new types of non-volatile memory (NVRAM), such as PCM, Memristor, and STT-RAM, it becomes likely that one of these technologies will replace DRAM as main memory in the not-too-distant future. In an NVRAM based buffer cache, any updated pages can be kept longer without the urgency to be flushed to HDDs. This opens opportunities for designing new buffer cache policies that can achieve better storage performance. However, it is challenging to design a policy that can also increase the cache hit ratio. In this paper, we propose a buffer cache policy, named I/O-Cache, that regroups and synchronizes long sets of consecutive dirty pages to take advantage of HDDs' fast sequential access speed and the non-volatile property of NVRAM. In addition, our new policy can dynamically separate the whole cache into a dirty cache and a clean cache, according to the characteristics of the workload, to decrease storage writes. We evaluate our scheme with various traces. The experimental results show that I/O-Cache shortens I/O completion time, decreases the number of I/O requests, and improves the cache hit ratio compared with existing cache policies.

Continuous Data Protection (CDP) enables recoverability to any point in time (time travel) facilitated via journaling of every write made by a system to disk. Stringent storage performance and capacity requirements for journaling make CDP a very high cost solution leading to limited adoption. In this work we first explore the feasibility of building such a CDP function on top of cheap commodity storage exposed via cloud object stores. Based on this analysis, we propose cCDP - a Cloud Continuous Data Protection framework that efficiently combines cloud object stores with edge caching to address requirements of low cost, high capacity, low latency and high storage throughput. cCDP with careful tuning can not only meet but surpasses the write throughput and latency requirements of CDP with minimal buffer overheads (<; 1%). Recovery lookup performance (Identification & Ordering) of cCDP with hybrid data layout is within 28% of Btree based temporal data layout and is about 52.7% better than the naive data layout with name encoding with significantly lower edge buffer and write throughput overheads than the Btree based temporal data layout.

This paper proposes a deMOtion-based, fLash-awARe hybrid storage cache model, named MOLAR, to effectively integrate Flash-based Solid-State Disks (SSDs) into traditional dynamic random access memory (DRAM)-based memory storage systems where SSDs serve as the Tier-2 cache, while DRAM is considered as the Tier-1 cache. We found that conventional cache algorithms designed for DRAM perform poorly in SSDs due to the limited write cycles and asymmetric read/write performance of Flash memory. In MOLAR, a Flash-aware I/O path structure is designed to adapt the asymmetric read and write performance of SSDs and, moreover, to reduce useless write operations. A new control metric, demotion count, is validated to wisely select the evicted blocks from DRAM to reside in the SSD. Besides, for SSD can improve internal data placement from data access hints, the Logical Block Addresses in the SSD are grouped into the long-lived region and the short-lived region self-adaptively via a heuristic control algorithm based on the change of the block demotion count. Through trace-driven simulations, the overall hit ratio in MOLAR outperforms two traditional policies by 1.44–5.34%. The average access latency in SSDs is reduced by 3.5× to 4.5×. Moreover, write amplification is effectively reduced by ∼36% in two typical Flash address-mapping policies.

In this paper we propose a flexible and scalable distributed storage framework called flex Store that can adapt to variations in available or consumable power and demonstrate its performance in the context of reduplicated virtual machine disks. We propose and investigate smart control techniques in order to cope with the power constraints either introduced as a result of increasing node density in the storage arrays (consumable power constraints) or introduced when a mix of renewable (green) and conventional (brown) energy sources are used to power the data enter. The key component in the proposed storage framework is the policy engine which is a software layer that provides interfaces to define performance requirements of the applications (and also energy related policies). The policy engine enforces those policies in the storage system by adjusting the allocation of storage resources. The experimental results demonstrate the ability of the framework to dynamically adapt to the changes in workload and power constraints and minimize performance impacts. Our evaluation of the prototype shows that the adaptive replication mechanisms can reduce the IO latencies by around 65% during energy plenty situations and the impact of adaptation actions on IO latencies during energy constrained situations is reduced by more than 40% compared to the case without the adaptive replication and optimized adaptation mechanisms.

With the rapid development of new types of nonvolatile memory (NVM), one of these technologies may replace DRAM as the main memory in the near future. Some drawbacks of DRAM, such as data loss due to power failure or a system crash can be remedied by NVM's non-volatile nature. In the meantime, solid state drives (SSDs) are becoming widely deployed as storage devices for faster random access speed compared with traditional hard disk drives (HDDs). For applications demanding higher reliability and better performance, using NVM as the main memory and SSDs as storage devices becomes a promising architecture. Although SSDs have better performance than HDDs, SSDs cannot support in-place updates (i.e., an erase operation has to be performed before a page can be updated) and suffer from a low endurance problem that each unit will wear out after certain number of erase operations. In an NVM based main memory, any updated pages called dirty pages can be kept longer without the urgent need to be flushed to SSDs. This difference opens an opportunity to design new cache policies that help extend the lifespan of SSDs by wisely choosing cache eviction victims to decrease storage write traffic. However, it is very challenging to design a policy that can also increase the cache hit ratio for better system performance. Most existing DRAM-based cache policies have mainly concentrated on the recency or frequency status of a page. On the other hand, most existing NVM-based cache policies have mainly focused on the dirty or clean status of a page. In this paper, by extending the concept of the Adaptive Replacement Cache (ARC), we propose a Hierarchical Adaptive Replacement Cache (H-ARC) policy that considers all four factors of a page's status: dirty, clean, recency, and frequency. Specifically, at the higher level, H-ARC adaptively splits the whole cache space into a dirty-page cache and a clean-page cache. At the lower level, inside the dirty-page cache and the clean-page cache, H-ARC splits them into a recency-page cache and a frequency-page cache separately. During the page eviction process, all parts of the cache will be balanced towards to their desired sizes.

The resources of dedicated accelerators (e.g. FPGA) are still required to bridge the gap between software-based Middleboxs(MBs) and the commodity hardware. To consolidate various hardware resources in an elastic, programmable and reconfigurable manner, we design and build a flexible and consolidated framework, OpenANFV, to support virtualized accelerators for MBs in the cloud environment. OpenANFV is seamlessly and efficiently put into Openstack to provide high performance on top of commodity hardware to cope with various virtual function requirements. OpenANFV works as an independent component to manage and virtualize the acceleration resources (e.g. cinder manages block storage resources and nova manages computing resources). Specially, OpenANFV mainly has the following three features. (1)Automated Management. Provisioning for multiple Virtualized Network Functions (VNFs) is automated to meet the dynamic requirements of NFV environment. Such automation alleviates the time pressure of the complicated provisioning and configuration as well as reduces the probability of manually induced configuration errors. (2) Elasticity. VNFs are created, migrated, and destroyed on demand in real time. The reconfigurable hardware resources in pool can rapidly and flexibly offload the corresponding services to the accelerator platform in the dynamic NFV environment. (3) Coordinating with Openstack. The design and implementation of the OpenANFV APIs coordinate with the mechanisms in Openstack to support required virtualized MBs for multiple tenants.

With the development of wireless communication network, Vehicular Ad-hoc Network (VANET) has received considerable attentions. US Department of Transportation (USDOT) is piloting a deployment concept to encourage embedding and retrofitting vehicles with DSRC interface to support varieties of applications for both safety and non-safety purposes. In addition to traditional data service, many real-time video streaming applications are increasingly being developed over VANET. Although it is desirable to delivery the packets directly through single hop communications, such condition is not always available in the real environment. To support real-time video applications in VANET, we have to deeply understand their performance under multihop conditions and even with others' interference. To the best of our knowledge, no work has been done on measuring the multihop video streaming transmission performance with interference over real environment. In this paper, a DSRC device based test-bed is developed to investigate the performance of multihop real-time video streaming transmission and the impact of interference. To overcome the high packet loss rate which is a main shortage of video streaming transmission over VANET, we improve the application by adding retransmission and startup caching schemes. We also evaluate the performance of different retransmission strategies and analyze how to optimize the retransmission scheme for minimizing the number of collided and late packets based on the transmission rate of interference.

As a key approach to achieve energy efficiency in sensor networks, sensing coverage has been studied extensively in the literature. Researchers have designed many coverage protocols to provide various kinds of service guarantees on the network lifetime, coverage ratio and detection delay. While these protocols are effective, they are not flexible enough to meet multiple design goals simultaneously. In this paper, we propose a unified sensing coverage architecture for duty cycled wireless sensor networks, called uSense, which features three novel ideas: Asymmetric Architecture, Generic Switching and Global Scheduling. We propose asymmetric architecture based on the conceptual separation of switching from scheduling. Switching is efficiently supported in sensor nodes, while scheduling is done in a separated computational entity, where multiple scheduling algorithms are supported. As an instance, we propose a two-level global coverage algorithm, called uScan. At the first level, coverage is scheduled to activate different portions of an area. We propose an optimal scheduling algorithm to minimize area breach. At the second level, sets of nodes are selected to cover active portions. Importantly, we show the feasibility to obtain optimal set-cover results in linear time if the layout of areas satisfies certain conditions. Through extensive testbed and simulation evaluations, we demonstrate that uSense is a promising architecture to support flexible and efficient coverage in sensor networks.

This paper proposes a deMOtion-based, fLAsh-awaRe hybrid storage cache model, named MOLAR, to effectively integrate Flash-based Solid State Disks (SSDs) into traditional DRAM-based memory storage systems. In MOLAR, a flash-aware I/O path structure is designed to adapt the asymmetric read and write performance of SSD and moreover to reduce useless write operations. A new control metric, demotion count, is proposed to wisely select the evicted data blocks from DRAM to reside in SSD. Besides, for SSD can improve internal data placement from data access hints, the Logical Block Addresses (LBAs) in SSD are grouped into the long-lived region and the short-lived region self-adaptively via a heuristic control algorithm based on the change of data block demotion count. Through trace-driven simulations, the overall hit ratio in MOLAR outperforms two traditional policies from 1.44% to 5.34%. The average write latency in SSD is reduced by 3.5 X. Moreover, write amplification is effectively reduced by about 36% in two typical flash address mapping policies.

In recent years, reliability has become one critical issue in the designs of flash-memory file/storage systems, due to the growing unreliability of advanced flash-memory chips. In this paper, a version-based design is proposed to effectively and efficiently maintain the consistency among page versions of a file for potential recovery needs. In particular, a two-version one for a native file system is presented with the minimal overheads in version maintenance. A recovery scheme is then presented to restore a corrupted file back to the latest consistent version. The design is later extended to maintain multiple data versions with the considerations of the write constraints of multilevel-cell flash memory. It was shown that the proposed design could significantly improve the reliability of flash memory with limited management and space overheads.

Shingled write disk (SWD) is a magnetic hard disk drive that adopts the shingled magnetic recording (SMR) technology to overcome the areal density limit faced in conventional hard disk drives (HDDs). The SMR design enables SWDs to achieve two to three times higher areal density than the HDDs can reach, but it also makes SWDs unable to support random writes/in-place updates with no performance penalty. In particular, a SWD needs to concern about the random write/update interference, which indicates writing to one track overwrites the data previously stored on the subsequent tracks. Some research has been proposed to serve random write/update out-of-place to alleviate the performance degradation at the cost of bringing in the concept of garbage collection. However, none of these studies investigate SWDs based on the garbage collection performance. In this paper, we propose a SWD design called Hot data identification-based Shingled Write Disk (H-SWD). The H-SWD adopts a window-based hot data identification to effectively manage data in the hot bands and the cold bands such that it can significantly reduce the garbage collection overhead while preventing the random write/update interference. The experimental results with various realistic workloads demonstrates that H-SWD outperforms the Indirection System. Specifically, incorporating a simple hot data identification empowers the H-SWD design to remarkably improve garbage collection performance.

There are two types of NAND flash memory - MLC (Multi -- Level Cell) and SLC (Single -- Level Cell). Low endurance and slower write performance in MLC NAND flash memory is a limitation to its usage in large scale solid state drives. On the other hand SLC NAND flash memory which has higher endurance and faster write performance is much more expensive than MLC devices. Hybrid SLC-MLC devices bridge the gap between the two by providing improved reliability at a low cost. In this paper, we propose an efficient architecture called Hybrot that aims at providing improved performance in hybrid SLC -- MLC devices and at the same time ensures maximum lifetime for the flash blocks. We propose a gray box approach for managing the SLC and MLC blocks which achieves the target write performance irrespective of the underlying flash management algorithms.

Data deduplication has been widely adopted in contemporary backup storage systems. It not only saves storage space considerably, but also shortens the data backup time significantly. Since the major goal of the original data deduplication lies in saving storage space, its design has been focused primarily on improving write performance by removing as many duplicate data as possible from incoming data streams. Although fast recovery from a system crash relies mainly on read performance provided by deduplication storage, little investigation into read performance improvement has been made. In general, as the amount of deduplicated data increases, write performance improves accordingly, whereas associated read performance becomes worse. In this paper, we newly propose a deduplication scheme that assures demanded read performance of each data stream while achieving its write performance at a reasonable level, eventually being able to guarantee a target system recovery time. For this, we first propose an indicator called cache aware Chunk Fragmentation Level (CFL) that estimates degraded read performance on the fly by taking into account both incoming chunk information and read cache effects. We also show a strong correlation between this CFL and read performance in the backup datasets. In order to guarantee demanded read performance expressed in terms of a CFL value, we propose a read performance enhancement scheme called selective duplication that is activated whenever the current CFL becomes worse than the demanded one. The key idea is to judiciously write non-unique (shared) chunks into storage together with unique chunks unless the shared chunks exhibit good enough spatial locality. We quantify the spatial locality by using a selective duplication threshold value. Our experiments with the actual backup datasets demonstrate that the proposed scheme achieves demanded read performance in most cases at the reasonable cost of write performance.

Due to its better scalability, Key-Value (KV) store has superseded traditional relational databases for many applications, such as data deduplication, on-line multi-player gaming, and Internet services like Amazon and Facebook. The KV store efficiently supports two operations (key lookup and KV pair insertion) through an index structure that maps keys to their associated values. The KV store is also commonly used to implement the chunk index in data deduplication, where a chunk ID (SHA1 value computed based on the chunk's content) is a key and its associative chunk metadata (e.g., physical storage location, stream ID) is the value. For a deduplication system, typically the number of chunks is too large to store the KV store solely in RAM. Thus, the KV store maintains a large (hash-table based) index structure in RAM to index all KV pairs stored on secondary storage. Hence, its available RAM space limits the maximum number of KV pairs that can be stored. Moving the index data structure from RAM to flash can possibly overcome the space limitation. In this paper, we propose efficient KV store on flash with a Bloom Filter based index structure called BloomStore. The unique features of the BloomStore include (1) no index structure is required to be stored in RAM so that a small RAM space can support a large number of KV pairs and (2) both index structure and KV pairs are stored compactly on flash memory to improve its performance. Compared with the state-of-the-art KV store designs, the BloomStore achieves a significantly better key lookup performance and roughly the same insertion performance with multiple times less RAM usage based on our experiments with deduplication workloads.

The sustainability concerns of Information Technology (IT) go well beyond energy-efficient computing and require techniques for minimizing environmental impact of IT infrastructure over its entire life-cycle. Traditionally, IT infrastructure is overdesigned at all levels from chips to entire data centers and ecosystem; the paradigm explored in this article is to replace overdesign with rightsizing coupled with smarter control, henceforth referred to as Energy-Adaptive Computing or EAC. The article lays out the challenges of EAC in various environments in terms of the adaptation of the workload and the infrastructure to cope with energy and cooling deficiencies. The article then focuses on implementing EAC in a data center environment, and addresses the problem of simultaneous energy demand and energy supply regulation at multiple levels, work, from servers to the entire data center. The proposed control scheme adapts the assignments of tasks to servers in a way that can cope with the varying energy limitations. The article also presents some experimental results to show how the scheme can continue to meet Quality of Service (QoS) requirements of tasks under energy limitations.

This paper proposes Trajectory-based Statistical Forwarding (TSF) scheme, tailored for the multihop data delivery from infrastructure nodes (e.g., Internet access points) to moving vehicles in vehicular ad hoc networks. To our knowledge, this paper presents the first attempt to investigate how to effectively utilize the packet destination vehicle's trajectory for such an infrastructure-to-vehicle data delivery. This data delivery is performed through the computation of a target point based on the destination vehicle's trajectory that is an optimal rendezvous point of the packet and the destination vehicle. TSF forwards packets over multihop to a selected target point where the vehicle is expected to pass by. Such a target point is selected optimally to minimize the packet delivery delay while satisfying the required packet delivery probability. The optimality is achieved analytically by utilizing the packet's delivery delay distribution and the destination vehicle's travel delay distribution. Through theoretical analysis and extensive simulation, it is shown that our design provides an efficient data forwarding under a variety of vehicular traffic conditions.

In recent years, reliability has become one critical issue in the designs of flash file systems due to the growing unreliability of advanced flash-memory chips. In this paper, a version-based strategy with optimal space utilization is proposed to maintain the consistency among page versions of a file for potential recovery needs with the considerations of the write constraints of multi-level-cell flash memory. A series of experiments was conducted to show that the proposed strategy could improve the reliability of flash file systems with limited management and space overheads.

Non-repudiation is one of the challenges in smart grids. A malicious smart meter is capable of compromising the power readings without being detected since it may be the only device to measure the electricity service amount in local. This kind of attack can cause financial loss due to incorrect readings and bring dispute between the power provider and the subscriber. In this paper, we address the non-repudiation problem with respect to accountability in the neighborhood area smart grids. We propose a mutual inspection strategy which can detect problematic smart meters and prevent further financial loss. Our evaluation results show that this scheme can be effectively applied to smart grids.

Data deduplication has recently become commonplace in most secondary storage and even in some primary storage for the capacity optimization purpose. Aside from its write performance, read performance of the deduplication storage has been gaining in significance with a wide range of its deployments. In this paper, we emphasize the importance of read performance in reconstituting a data stream from its unique and shared chunks physically dispersed over deduplication storage. We newly introduce a read performance indicator called Chunk Fragmentation Level (CFL). We also validate that the CFL is very effective to indicate read performance of deduplication storage through a developed theoretical performance model and extensive experiments. Finally, we articulate further research issues.

The bloom filter is a probabilistic data structure that provides a compact representation of a set of elements. To keep false positive probabilities low, the size of the bloom filter must be dimensioned a priori to be linear in the maximum number of keys inserted, with the linearity constant ranging typically from one to few bytes. A bloom filter is most commonly used as an in memory data structure, hence its size is limited by the availability of RAM space on the machine. As datasets have grown over time to Internet scale, so have the RAM space requirements of bloom filters. If sufficient RAM space is not available, we advocate that flash memory may serve as a suitable medium for storing bloom filters, since it is about one-tenth the cost of RAM per GB while still providing access times orders of magnitude faster than hard disk. We present BLOOMFLASH, a bloom filter designed for flash memory based storage, that provides a new dimension of trade off with bloom filter access times to reduce RAM space usage (and hence system cost). The simple design of a single flat bloom filter on flash suffers from many performance bottlenecks, including in-place bit updates that are inefficient on flash and multiple reads and random writes spread out across many flash pages for a single lookup or insert operation. To mitigate these performance bottlenecks, BLOOMFLASH leverages two key design innovations: (i) buffering bit updates in RAM and applying them in bulk to flash that helps to reduce random writes to flash, and (ii) a hierarchical bloom filter design consisting of component bloom filters, stored one per flash page, that helps to localize reads and writes on flash. We use two real-world data traces taken from representative bloom filter applications to drive and evaluate our design. BLOOMFLASH achieves bloom filter access times in the range of few tens of microseconds, thus allowing up to order of tens of thousands operations per sec.

The increasing energy demand coupled with emerging sustainability concerns requires a re-examination of power/thermal issues in data centers from the perspective of short term energy deficiencies. Such energy deficient scenarios arise for a variety of reasons including variable energy supply from renewable sources and inadequate power, thermal and cooling capacities. In this paper we propose a hierarchical control scheme to adapt assignments of tasks to servers in a way that can cope with the varying energy limitations and still provide necessary QoS. The rescheduling of tasks on different servers has direct (migration related) and indirect (changed traffic patterns) network energy impacts that we also consider. We show the stability of our scheme and evaluate its performance via detailed simulations and experiments.

In this paper, we propose a Convertible Flash Translation Layer (CFTL) for NAND flash-based storage systems. CFTL is a novel hybrid flash translation layer adaptive to workloads so that it can dynamically switch its mapping scheme to either a page level mapping or a block level mapping scheme to fully exploit the benefits of them. Moreover, we propose an efficient caching strategy to further improve the CFTL performance. Consequently, both the convertible feature and the caching strategy empower CFTL to achieve good read performance as well as good write performance. Our experimental evaluation with various realistic workloads demonstrates that CFTL outweighs other FTL schemes. In particular, our new caching strategy remarkably improves cache hit ratios, by an average of 245%, and exhibits much higher hit ratios especially for randomly read intensive workloads.

Existing garbage collection algorithms for the flash-based storage use score-based heuristics to select victim blocks for reclaiming free space and wear leveling. The score for a block is estimated using metadata information such as age, block utilization, and erase count. To quickly find a victim block, these algorithms maintain a priority queue in the SRAM of the storage controller. This priority queue takes O(K) space, where K stands for flash storage capacity in total number of blocks. As the flash capacity scales to larger size, K also scales to larger value. However, due to higher price per byte, SRAM will not scale proportionately. In this case, due to SRAM scarcity, it will be challenging to implement a larger priority queue in the limited SRAM of a large-capacity flash storage. In addition to space issue, with any update in the metadata information, the priority queue needs to be continuously updated, which takes O(lg(K)) operations. This computation overhead also increases with the increase of flash capacity. In this paper, we have taken a novel approach to solve the garbage collection metadata management problem of a large-capacity flash storage. We propose a sampling-based approach to approximate existing garbage collection algorithms in the limited SRAM space. Since these algorithms are heuristic-based, our sampling-based algorithm will perform as good as unsampled (original) algorithm, if we choose good samples to make garbage collection decisions. We propose a very simple policy to choose samples. Our experimental results show that small number of samples are good enough to emulate existing garbage collection algorithms.

A Bloom Filter (BF) is a data structure based on probability to compactly represent/record a set of elements (keys). It has wide applications on efficiently identifying a key that has been seen before with minimum amount of recording space used. BF is heavily used in chunking based data de-duplication. Traditionally, a BF is implemented as in-RAM data structure; hence its size is limited by the available RAM space on the machine. For certain applications like data de-duplication that require a big BF beyond the size of available RAM space, it becomes necessary to store a BF into a secondary storage device. Since BF operations are inherently random in nature, magnetic disk provides worse performance for the random read and write operations. It will not be a good fit for storing the large BF. Flash memory based Solid State Drive (SSD) has been considered as an emerging storage device that has superior performance and can potentially replace disks as the preferred secondary storage devices. However, several special characteristics of flash memory make designing a flash memory based BF very challenging. In this paper, our goal is to design an efficient flash memory based BF that is fully aware of these physical characteristics. To this end, we propose a Forest-structured BF design (FBF). FBF uses a combination of RAM and flash memory to design a BF. BF is stored on the flash, while RAM helps to mitigate the impact of slow write performance of flash memory. In addition, in-flash BF is organized in a forest-like structure in order to improve the lookup performance. Our experimental results show that FBF design achieves 2 times faster processing speed with 50% less number of flash write operations when compared with the existing flash memory based BF designs.

NAND flash memory is fast replacing traditional magnetic storage media due to its better performance and low power requirements. However the endurance of flash memory is still a critical issue in using it for large scale enterprise applications. Rethinking the basic design of NAND flash memory is essential to realize its maximum potential in large scale storage. NAND flash memory is organized as blocks and blocks in turn have pages. A block can be erased reliably only for a limited number of times and frequent block erase operations to a few blocks reduce the lifetime of the flash memory. Wear leveling helps to prevent the early wear out of blocks in the flash memory. In order to achieve efficient wear leveling, data is moved around throughout the flash memory. The existing wear leveling algorithms do not scale for large scale NAND flash based SSDs. In this paper we propose a static wear leveling algorithm, named as Rejuvenator, for large scale NAND flash memory. Rejuvenator is adaptive to the changes in workloads and minimizes the cost of expensive data migrations. Our evaluation of Rejuvenator is based on detailed simulations with large scale enterprise workloads and synthetic micro benchmarks.

Hot data identification can be applied to a variety of fields. Particularly in flash memory, it has a critical impact on its performance (due to a garbage collection) as well as its life span (due to a wear leveling). Although the hot data identification is an issue of paramount importance in flash memory, little investigation has been made. Moreover, all existing schemes focus almost exclusively on a frequency viewpoint. However, recency also must be considered equally with the frequency for effective hot data identification. In this paper, we propose a novel hot data identification scheme adopting multiple bloom filters to efficiently capture finer-grained recency as well as frequency. In addition to this scheme, we propose a Window-based Direct Address Counting (WDAC) algorithm to approximate an ideal hot data identification as our baseline. Unlike the existing baseline algorithm that cannot appropriately capture recency information due to its exponential batch decay, our WDAC algorithm, using a sliding window concept, can capture very fine-grained recency information. Our experimental evaluation with diverse realistic workloads including real SSD traces demonstrates that our multiple bloom filter-based scheme outperforms the state-of-the-art scheme. In particular, ours not only consumes 50% less memory and requires less computational overhead up to 58%, but also improves its performance up to 65%.

Road networks are one of important surveillance areas in military scenarios. In these road networks, sensors will be sparsely deployed (hundreds of meters apart) for the cost-effective deployment. This makes the existing localization solutions based on the ranging ineffective. To address this issue, this paper introduces a novel approach based on the passive vehicular traffic measurement, called Autonomous Passive Localization (APL). Our work is inspired by the fact that vehicles move along routes with a known map. Using binary vehicle-detection time stamps, we can obtain distance estimates between any pair of sensors on roadways to construct a virtual graph composed of sensor identifications (i.e., vertices) and distance estimates (i.e., edges). The virtual graph is then matched with the topology of the road map, in order to identify where sensors are located on roadways. We evaluate our design outdoors on Minnesota roadways and show that our distance estimate method works well despite traffic noises. In addition, we show that our localization scheme is effective in a road network with 18 intersections, where we found no location matching error, even with a maximum sensor time synchronization error of 0.07 sec and a vehicle speed deviation of 10 km/h.

This paper proposes a Trajectory-Based Data (TBD) Forwarding scheme, tailored for the data forwarding for roadside reports in light-traffic vehicular ad hoc networks. State-of-the-art schemes have demonstrated the effectiveness of their data forwarding strategies by exploiting known vehicular traffic statistics (e.g., densities and speeds). These results are encouraging, however, further improvements can be made by taking advantage of the growing popularity of GPS-based navigation systems. This paper presents the first attempt to effectively utilize vehicles' trajectory information in a privacy-preserving manner. In our design, such trajectory information is combined with the vehicular traffic statistics for a better performance. In a distributed way, each individual vehicle computes its end-to-end expected delivery delay to the Internet access points based on its position on its vehicle trajectory and exchanges this delay with neighboring vehicles to determine the best next-hop vehicle. For the accurate end-to-end delay computation, this paper also proposes a link delay model to estimate the packet forwarding delay on a road segment. Through theoretical analysis and extensive simulation, it is shown that our link delay model provides the accurate link delay estimation and our forwarding design outperforms the existing scheme in terms of both the data delivery delay and packet delivery ratio.

This paper proposes a data forwarding scheme called Trajectory-based Statistical Forwarding (TSF), tailored for the data delivery from infrastructure nodes (e.g., Internet access points) to moving vehicles in vehicular networks. To our knowledge, this paper presents the first attempt to investigate how to effectively utilize the packet destination vehicle's trajectory for such an infrastructure-to-vehicle data delivery. This data delivery is performed through the computation of a target point based on the destination vehicle's trajectory that is an optimal rendezvous point of the packet and the destination vehicle. TSF forwards packets over multi-hop to a selected target point where the vehicle is expected to pass by. Such a target point is selected optimally to minimize the packet delivery delay while satisfying the required packet delivery probability. The optimality is achieved analytically by utilizing the packet's delivery delay distribution and the destination vehicle's travel delay distribution. Through theoretical analysis and extensive simulation, it is shown that our design provides an efficient data forwarding under a variety of vehicular traffic conditions.

Traffic safety applications using VANET can significantly improve road safety if safety packets can be delivered on time. Therefore, a MAC layer protocol for VANET that can guarantee timely delivery of data is critical. Currently, the MAC layer standard that is supporting inter-vehicular communication is IEEE 802.11 which is a contention based protocol where all the vehicles contend for one common channel. This protocol can not guarantee an upper bounded delay for delivery of safety messages. To resolve this issue, we first obtain the theoretical lower bound on the delay for delivery of safety messages. Then, we introduce a novel MAC layer protocol for inter-vehicular communication that guarantees the delivery of safety messages within a certain upper bound. This upper bound is only within a constant factor from the theoretical lower bound. Our protocol is distributed and dynamic and easily adjusts to the topological changes in the network. Through analytical modeling and simulation, we show that using our MAC layer protocol, the delay in transmission only grows linearly with the number of vehicles even in the dense networks where IEEE 802.11 protocol causes unpredictable delays.

A predominant portion of Internet services, like content delivery networks, news broadcasting, blogs sharing and social networks, etc., is data centric. A significant amount of new data is generated by these services each day. To efficiently store and maintain backups for such data is a challenging task for current data storage systems. Chunking based deduplication (dedup) methods are widely used to eliminate redundant data and hence reduce the required total storage space. In this paper, we propose a novel Frequency Based Chunking (FBC) algorithm. Unlike the most popular Content-Defined Chunking (CDC) algorithm which divides the data stream randomly according to the content, FBC explicitly utilizes the chunk frequency information in the data stream to enhance the data deduplication gain especially when the metadata overhead is taken into consideration. The FBC algorithm consists of two components, a statistical chunk frequency estimation algorithm for identifying the globally appeared frequent chunks, and a two-stage chunking algorithm which uses these chunk frequencies to obtain a better chunking result. To evaluate the effectiveness of the proposed FBC algorithm, we conducted extensive experiments on heterogeneous datasets. In all experiments, the FBC algorithm persistently outperforms the CDC algorithm in terms of achieving a better dedup gain or producing much less number of chunks. Particularly, our experiments show that FBC produces 2.5 ~ 4 times less number of chunks than that of a baseline CDC which achieving the same Duplicate Elimination Ratio (DER). Another benefit of FBC over CDC is that the FBC with average chunk size greater than or equal to that of CDC achieves up to 50% higher DER than that of a CDC algorithm.

The NAND flash memory based storage has faster read, higher power savings, and lower cooling cost compared to the conventional rotating magnetic disk drive. However, in case of flash memory, read and write operations are not symmetric. Write operations are much slower than read operations. Moreover, frequent update operations reduce the lifetime of the flash memory. Due to the faster read performance, flash-based storage is particularly attractive for the read-intensive database workloads, while it can produce poor performance when used for the update-intensive database workloads. This paper aims to improve write performance and lifetime of flash-based storage for the update-intensive workloads. In particular, we propose a new hierarchical approach named as deferred update methodology. Instead of directly updating the data records, first we buffer the changes due to update operations as logs in two intermediate in-flash layers. Next, we apply multiple update logs in bulk to the data records. Experimental results show that our proposed methodology significantly improves update processing overhead and longevity of the flash-based storages.

The flash translation layer (FTL) is a software/hardware in terface inside NAND flash memory. Since FTL has a critical impact on the performance of NAND flash-based devices, a variety of FTL schemes have been proposed to improve their performance. In this paper, we propose a novel hybrid FTL scheme named Convertible Flash Translation Layer (CFTL). Unlike other existing FTLs using static address mapping schemes, CFTL is adaptive to data access patterns so that it can dynamically switch its mapping scheme to either a read-optimized or a write-optimized mapping scheme. In addition to this convertible scheme, we propose an efficient caching strategy to further improve the CFTL performance with only a simple hint. Consequently, both the convertible feature and the caching strategy empower CFTL to achieve good read performance as well as good write performance.

The 11 papers in this special issue on mission critical networking are divided into three categories: quality of service issues (three papers); security issues (four papers); and configuration and data collection issues (four papers).

This paper proposes a VIrtual Scanning Algorithm (VISA), tailored and optimized for road network surveillance. Our design uniquely leverages upon the facts that 1) the movement of targets (e.g., vehicles) is confined within roadways and 2) the road network maps are normally known. We guarantee the detection of moving targets before they reach designated protection points (such as temporary base camps), while maximizing the lifetime of the sensor network. The main idea of this work is virtual scan-waves of sensing activities scheduled for road network protection. We provide design-space analysis on the performance of virtual scan in terms of lifetime and average detection delay. Importantly, to our knowledge, this is the first work to study how to guarantee target detection while sensor network deteriorates, using a novel hole handling technique. Through theoretical analysis and extensive simulation, it is shown that a surveillance system, using our design, sustains orders-of-magnitude longer lifetime than full coverage algorithms, and as much as 10 times longer than legacy duty cycling algorithms.

This paper proposes a trajectory-based data forwarding (TBD) scheme, tailored for the data forwarding in light- traffic vehicular ad-hoc networks. State-of-the-art schemes have demonstrated the effectiveness of their data forwarding strategies by exploiting known vehicular traffic statistics (e.g., densities and speeds) in these vehicular networks. These results are encouraging, however, further improvements can be made by taking advantage of the growing popularity of GPS-based navigation systems. This paper presents the first attempt to investigate how to effectively utilize vehicles" trajectory information in a privacy-preserving manner. In our design, the trajectory information is combined with the traffic statistics to improve the performance of data forwarding in road networks. Through theoretical analysis and extensive simulation, it is shown that our design outperforms the existing scheme.

This paper proposes a virtual scanning algorithm (VISA), tailored and optimized for road network surveillance. Our design uniquely leverages upon the facts that (i) the movement of targets (e.g., vehicles) is confined within roadways and (ii) the road network maps are normally known. We guarantee the detection of moving targets before they reach designated protection points (such as temporary base camps), while maximizing the lifetime of the sensor network. The main idea of this work is virtual scan - waves of sensing activities scheduled for road network protection. We provide design-space analysis on the performance of virtual scan in terms of lifetime and average detection delay. Importantly, to our knowledge, this is the first work to study how to guarantee target detection while sensor network deteriorates, using a novel hole handling technique. Through theoretical analysis and extensive simulation, it is shown that a surveillance system, using our design, sustains orders-of-magnitude longer lifetime than full coverage algorithms, and as much as ten times longer than legacy duty cycling algorithms.

Solid state disks (SSDs) using NAND flash memory are increasingly being adopted in the high-end servers of datacenters to improve performance of the I/O-intensive applications. Compared to the traditional enterprise class hard disks, SSDs provide faster read performance, lower cooling cost, and higher power efficiency. However, write performance of a flash based SSD can be up to an order of magnitude slower than its read performance. Furthermore, frequent write operations degrade the lifetime of flash memory. A nonvolatile cache can greatly help to solve these problems. Although a RAM cache is relative high in cost, it has successfully eliminated the performance gap between fast CPU and slow magnetic disk. Similarly, a nonvolatile cache in an SSD can alleviate the disparity between the flash memory's read and write performance. A small write cache that reduces the number of flash block erase operations, can lead to substantial performance gain for write-intensive applications and can extend the overall lifetime of flash based SSDs. This paper presents a novel write caching algorithm, the Large Block CLOCK (LB-CLOCK) algorithm, which considers `recency' and `block space utilization' metrics to make cache management decisions. LB-CLOCK dynamically varies the priority between these two metrics to adapt to changes in workload characteristics. Our simulation based experimental results show that LB-CLOCK outperforms the best known existing flash caching algorithms for a wide range of workloads.

Networked storage incorporates networking technology and storage technology, greatly extending the reach of the storage subsystem. In this paper, we present a novel Quality of Service (QoS) scheduling scheme to satisfy the requirements of different QoS requests for access to the networked storage system. Our key ideas include breaking down the requests into appropriate chunks of smaller sizes and taking the network characteristics into consideration such that 1) each session channel has smoother data access, 2) resource requirements such as buffer usage are reduced, and 3) more urgent requests can preempt a less urgent request. Our experimental results show that our scheme is effective in obtaining these goals.

A central problem in sensor network security is that sensors are susceptible to physical capture attacks. Once a sensor is compromised, the adversary can easily launch clone attacks by replicating the compromised node, distributing the clones throughout the network, and starting a variety of insider attacks. Previous works against clone attacks suffer from either a high communication/storage overhead or a poor detection accuracy. In this paper, we propose a novel scheme for detecting clone attacks in sensor networks, which computes for each sensor a social fingerprint by extracting the neighborhood characteristics, and verifies the legitimacy of the originator for each message by checking the enclosed fingerprint. The fingerprint generation is based on the superimposed s-disjunct code, which incurs a very light communication and computation overhead. The fingerprint verification is conducted at both the base station and the neighboring sensors, which ensures a high detection probability. The security and performance analysis indicate that our algorithm can identify clone attacks with a high detection probability at the cost of a low computation/communication/storage overhead. To our best knowledge, our scheme is the first to provide realtime detection of clone attacks in an effective and efficient way.

In road networks, sensors are deployed sparsely (hundreds of meters apart) to save costs. This makes the existing localization solutions based on the ranging be ineffective. To address this issue, this paper introduces an autonomous passive localization scheme, called APL. Our work is inspired by the fact that vehicles move along routes with a known map. Using binary vehicle-detection timestamps, we can obtain distance estimates between any pair of sensors on roadways to construct a virtual graph composed of sensor identifications (i.e., vertices) and distance estimates (i.e., edges). The virtual graph is then matched with the topology of road map, in order to identify where sensors are located in roadways. We evaluate our design outdoor in Minnesota roadways and show that our distance estimate method works well despite of traffic noises. In addition, we show that our localization scheme is effective in a road network with eighteen intersections, where we found no location matching error, even with a maximum sensor time synchronization error of 0.3 sec and the vehicle speed deviation of 10 km/h.

The rapid development of the Internet, fast drop of storage cost, and the great improvement of storage capacity have created an environment with an enormous amount of digital data. In addition to the traditional goals like performance, scalability, availability, and reliability, other challenges including manageability, searching for the desired information, energy efficiency, long-term data preservation, and data security become increasingly important for storage systems. We first present the evolution path of the past development of storage systems. The impact of the advancement of disk technology on fault tolerance is discussed next. The potential solutions and research issues of the new challenges are also briefly discussed.

Applications that create and consume unstructured data have grown both in scale of storage requirements and complexity of search primitives. We consider two such applications: exhaustive search and integration of structured and unstructured data. Current block-based storage systems are either incapable or inefficient to address the challenges bought forth by the above applications. We propose a storage framework to efficiently store and search unstructured and structured data while controlling storage management costs. Experimental results based on our prototype show that the proposed system can provide impressive performance and feature benefits.

As a key approach to achieve energy efficiency in sensor networks, sensing coverage has been studied extensively. Researchers have designed many coverage protocols to provide various kinds of service guarantees on the network lifetime, coverage ratio and detection delay. While these protocols are effective, they are not flexible enough to meet multiple design goals simultaneously. In this paper, we propose a unified sensing coverage architecture, called uSense, which features three novel ideas: asymmetric architecture, generic switching and global scheduling. We propose asymmetric architecture based on the conceptual separation of switching from scheduling. Switching is efficiently supported in sensor nodes, while scheduling is done in a separated computational entity, where multiple scheduling algorithms are supported. As an instance, we propose a two-level global coverage algorithm, called uScan. At the first level, coverage is scheduled to activate different portions of an area. We propose an optimal scheduling algorithm to minimize area breach. At the second level, sets of nodes are selected to cover active portions. Importantly, we show the feasibility to obtain optimal set-cover results in linear time if the layout of areas satisfies certain conditions. We evaluate our architecture with a network of 30 MicaZ motes, an extensive simulation with 10,000 nodes, as well as theoretical analysis. The results indicate that uSense is a promising architecture to support flexible and efficient coverage in sensor networks.

This paper proposes a minimal contour tracking algorithm (MCTA) that reduces energy consumption for tracking mobile targets in wireless sensor networks in terms of sensing and communication energy consumption. MCTA conserves energy by letting only a minimum number of sensor nodes participate in communication and perform sensing for target tracking. MCTA uses the minimal tracking area based on the vehicular kinematics. The modeling of target's kinematics allows for pruning out part of the tracking area that cannot be mechanically visited by the mobile target within scheduled time. So, MCTA sends the tracking area information to only the sensor nodes within minimal tracking area and wakes them up. Compared to the legacy scheme which uses circle-based tracking area, our proposed scheme uses less number of sensors for tracking in both communication and sensing without target missing. Through simulation, we show that MCTA outperforms the circle-based scheme with about 60% energy saving under certain ideal situations.

Providing quality of service (QoS) for Internet-based video streaming applications requires the server and/or client to be network-aware and adaptive. We present a dynamic rate and quality adaptation algorithm where the server varies its sending rate (without varying the quality level) to adapt to the network and client conditions and only as a last resort, does quality adaptation. We place the adaptation logic at the client since it has better knowledge about both the demand (buffer conditions, variable bit-rate requirements) and supply (network conditions). Our approach is unique because the server's sending rate is calculated based on the client's varying demand (consumption rate) and the network status. Also, we do not model the network as a black-box but instead augment endpoint observations with a feedback from the network to represent its status more precisely. To make an informed adaptation decision, the client requires sizes of all frames in the variable bit rate video. But the overhead involved in sending this metadata is significant. So we propose a lossy compression technique to reduce the amount of control information and consequently the overhead. We also present a scheduling algorithm, dynamic scheduling algorithm for reduced trace delivery (DART), to deliver the compressed control information to the client. This algorithm can be used to deliver any form of metadata (like subtitles, alerts, etc.), especially in applications like IP-TV. Simulations show that the proposed techniques can significantly improve user perceived QoS when compared to other popular adaptation methods.

High performance computing and enterprise data center require huge amount of data transfer between disk and tape. With the help of large capacity disk, writing to tape is less problematic than reading from tape. We are investigating how to use multiple tape libraries to build a parallel tape storage system with high aggregated data retrieval bandwidth. The challenge lies in that increasing data transfer parallelism may also increase tape switch time and data seek time that reduce the effective data retrieval bandwidth. We are proposing a novel scheme to place objects across tape drives based on object access pattern to reduce tape switch time and in the meanwhile increase data transfer parallelism. A multiple-tape-library simulator is built to study the proposed scheme. Simulation results show that our scheme outperforms other two previously proposed schemes with a better trade-off between tape switch time, data seek time and data transfer time

In this paper, we propose a Loopback approach in a two-level streaming architecture to exploit collaborative client/proxy buffers for improving the quality and efficiency of large-scale streaming applications. At the upper level we use a content delivery network (CDN) to deliver video from a central server to proxy servers. At the lower level a proxy server delivers video with the help of collaborative client caches. In particular, a proxy server and its clients in a local domain cache different portions of a video and form delivery loops. In each loop, a single video stream originates at the proxy, passes through a number of clients, and finally is passed back to the proxy. As a result, with limited bandwidth and storage space contributed by collaborative clients, we are able to significantly reduce the required network bandwidth, I/O bandwidth, and cache space of a proxy. Furthermore, we develop a local repair scheme to address the client failure issue for enhancing service quality and eliminating most required repairing load at the central server. For popular videos, our local repair scheme is able to handle most of single-client failures without service disruption and retransmissions from the central server. Our analysis and simulations have shown the effectiveness of the proposed scheme.

Universal multimedia access (UMA) refers to accessing multimedia content over a wide range of client terminals and network capacities. Scalable coding is a very popular technique to enable UMA for video. Overhead introduced by the scalable coding approach limits the number of layers that can be stored for each video. Therefore some clients may be served the closest available quality than the best-fit quality. This is a major drawback of scalable coding from the end-user perspective. We propose to employ transcoding to tailor content exactly to the client's best-fit quality when the required layer is not stored. Inserting a transcoder in the server-client path introduces new challenges in deciding the layering structure (number of layers, bandwidth per layer) of a video. The optimal layering structure should be decided based on factors like total I/O bandwidth penalty incurred due to layering and transcoding effort required to service the "non-layered" versions. The solution to this problem is further complicated by practical issues like diverse popularity of video objects and resource availability. Another issue that we address in this paper is reducing WAN bandwidth penalty incurred due to transport and coding overhead inherent to scalable coding. This particular problem applies to all schemes that use layered encoding to broadcast video. We map the above mentioned problems onto a 0-1 multiple choice knapsack structure and propose an algorithm to find a near-optimal solution. The uniqueness of our approach not only lies in the streaming model but also in the integrated manner in which we address a variety of issues put forth by layered coding.

To date, the systems approach to science, which emphasizes the connections among phenomena studied at different scales and by different disciplines, is causing dramatic changes in how scientific results are communicated. These changes drive a shift on how to propagate data with certain properties so that it can be used intelligently by others. In this work we elaborate on three major factors governing the propagation module of data provenance. The proposed propagation module provides an efficient solution for many critical problems in the management and provenance of scientific data. Unlike previous work, our work aims at realizing data provenance from models to storage. The natural representation of data as objects and its utility for capturing provenance has led us to consider a new storage architecture based on the object-based storage (OSD) technology. An outline of this framework is discussed.

Quality of service (QoS) is crucial for certain applications such as multimedia. As the object-based storage device (OSD) protocol emerges as the next generation storage technology, QoS provisioning for OSD-based systems has also received a great deal of attention. In this paper, we propose a QoS framework for OSD-based storage system that integrates both the network QoS and storage QoS. We examine the existing OSD specification and analyze the QoS requirements for applications on OSD clients. Based on the QoS requirements analysis, we propose a three-level QoS specification. We further elaborate on extensions to the existing OSD and iSCSI protocol to support our QoS specification. These extensions are then incorporated with the current OSD reference implementation. Finally, we discuss both the implementation structure and issues encountered as part of this study.

Position-based reactive routing is a scalable solution for routing in mobile ad hoc networks. The route discovery algorithm in position-based routing can be efficiently implemented only if the source knows the current address of the destination. In this paper, a quorum-based location management scheme is proposed. Location servers are selected using the minimum dominating set (MDS) approach, and are further organized into quorums for location update and location query. When a mobile node moves, it updates its location servers in the update quorum; when a node requests the location information of another node, it will send a query message to the location servers in the query quorum. We propose to use the position-based quorum system, which is easy to construct and guarantees that the update quorums always intersect with the query quorums so that at least one location server in the query quorum is aware of the most recent location of the mobile node. Clusters are introduced for large scale ad hoc networks for scalability. Experiment results show that the proposed scheme provides good scalability when network size increases. Copyright © 2005 John Wiley & Sons, Ltd.

Video streaming on a large scale can be expensive and resource demanding. Periodic broadcast reduces server I/O bandwidth usage for popular videos. While improving the scalability this mechanism increases considerably the WAN bandwidth usage and buffer space needed by a client. We address the resource demands on the client side with proxy caching. We show that prefix caching can lower WAN bandwidth usage and derive the lower limit, and that chunk caching can reduce buffer space requirements. We introduce periodic broadcast schemes designed to work with both types of caching and analyze their cost

Since the current Internet provides a best-effort service, timely delivery of data is not guaranteed for video streaming applications. Providing quality of service (QoS) in such a setting requires server and client to be network-aware and adaptive. We present a dynamic rate and quality adaptation scheme where the server varies its sending rate (without varying the quality) to adapt to the network and client conditions, and, only as a last resort, does quality adaptation. Our approach is unique because the server's sending rate is calculated based on the client's varying demand, and the network status. We do not model the network as a black-box but instead augment endpoint observations with feedback from the network and hence represent its status more precisely. We also propose a method to reduce the amount of control information needed to make adaptation decisions

Proxy servers have been used to cache web objects to alleviate the load of the web servers and to reduce network congestion on the Internet. In this paper, a central video server is connected to a proxy server via wide area networks (WANs) and the proxy server can reach many clients via local area networks (LANs). We assume a video can be either entirely or partially cached in the proxy to reduce WAN bandwidth consumption. Since the storage space and the sustained disk I/O bandwidth are limited resources in the proxy, how to efficiently utilize these resources to maximize the WAN bandwidth reduction is an important issue. We design a progressive video caching policy in which each video can be cached at several levels corresponding to cached data sizes and required WAN bandwidths. For a video, the proxy server determines to cache a smaller amount of data at a lower level or to gradually accumulate more data to reach a higher level. The proposed progressive caching policy allows the proxy to adjust caching amount for each video based on its resource condition and the user access pattern. We investigate the scenarios in which the access pattern is priorly known or unknown and the effectiveness of the caching policy is evaluated.

Bandwidth contention is still a challenging problem in providing efficient IP-based video-on-demand (VOD) service on broadband cable networks (BCNs), due to the lack of effective approaches to exploit the unique characteristics of BCNs. To address this issue, we have designed an optimal full-sharing (Dong Y et al., 2003) for VOD service over a single channel, which maximizes the number of simultaneous video sessions on the single channel. In this paper, we further extend our optimal scheduling for VOD service over multiple channels. We first analyze the expected session bandwidth of a video and then develop an efficient video assignment mechanism for maximizing the profit of a VOD system.

We present a data storage, retrieval, and communications system capable of supporting high-resolution image browsing on an inexpensive PC cluster based image-wall system. The data is first partitioned and then strategically written both onto a single hard disk and then across multiple hard disks. After presenting the data allocation scheme, we present schemes for retrieving the data from the hard disks and neighboring renderers. The optimality of the storage and retrieval mechanisms is proved and analytical results are presented for an initial implementation.

Due to the high bandwidth requirement and rate variability of compressed video, delivering video across wide area networks (WANs) is a challenging issue. Proxy servers have been used to reduce network congestion and improve client access time on the Internet by caching passing data. We investigate ways to store or stage partial video in proxy servers to reduce the network bandwidth requirement over WAN. A client needs to access a portion of the video from a proxy server over a local area network (LAN) and the rest from a central server across a WAN. Therefore, client buffer requirement and video synchronization are to be considered. We study the tradeoffs between client buffer, storage requirement on the proxy server, and bandwidth requirement over WAN. Given a video delivery rate for the WAN, we propose several frame staging selection algorithms to determine the video frames to be stored in the proxy server. A scheme called chunk algorithm, which partitions a video into different segments (chunks of frames) with alternating chunks stored in the proxy server, is shown to offer the best tradeoff. We also investigate an efficient way to utilize client buffer when the combination of video streams from WAN and LAN is considered.

Most of the QoS routing schemes proposed so far require periodic exchange of QoS state information among routers, imposing both communication overhead on the network and processing overhead on core routers. Furthermore, stale QoS state information causes the performance of these QoS routing schemes to degrade drastically. In order to circumvent these problems, we focus on localized QoS routing schemes where the edge routers make routing decisions using only local information and thus reducing the overhead at core routers. We first describe virtual capacity based routing (vcr), a theoretical scheme based on the notion of virtual capacity of a route. We then propose proportional sticky routing, an easily realizable approximation of vcr and analyze its performance. We demonstrate through extensive simulations that adaptive proportional routing is indeed a viable alternative to the global QoS routing approach.

This paper considers the problem of routing and wavelength assignment (RWA) in optical passive star networks with non-uniform traffic load. The problem can be considered as designing a logical topology over an optical passive star physical topology with a given non-uniform traffic. The approach uses the bipartite graphs and the concept of time and wavelength division multiplexing (TWDM) embedding process to discuss the problem. The non-uniformity of the traffic load makes the logical design computationally hard and requires heuristic algorithms. Then, a linear program can solve the routing. We present an algorithm for effectively assigning a limited number of wavelengths among the access nodes of a WDM multi-hop network, which are connected via a passive star topology. The RWA problem for such a network with non-uniform traffic load is discussed for the first time. The idea is based on reducing the maximum load on each wavelength by using more wavelengths available. The proposed algorithm is tested on several traffic models, and results are given to show the improvement in the performance of the network using our algorithm.

IP multicast is an important enabling service for the current and future Internet. With the explosive growth of the Internet, a challenging issue facing IP multicast is scalability, in particular, the problem of multicast forwarding state and control explosion. In this paper, we propose a new methodology to address the multicast scalability problem for backbone domains-multicast tunneling with branch filtering (MTBF). This multicast group aggregation scheme is designed on top of the inter-domain protocol architecture such as MASC/BGMF, and is independent of any underlying intra-domain multicast protocols. It aggregates multicast groups by constructing bolder router (BR)-based multicast routing trees and forwards data by using an encapsulation technique called multicast tunneling (MT). The feasibility and performance of our scheme is demonstrated through analysis and simulations.

The successful operation of mission critical systems requires a sophisticated control network which provides for the real-time delivery of data from a very large number of diverse sources such as sensors, audio/video surveillance, computational sources, etc., as well as remote monitoring and diagnosis sources. It is expected that many of the traffic sources will be in the form of periodic sources with real-time requirements. In this study, we propose fast scheduling algorithms for multiplexing periodic source flows with real-time delivery requirements. We assume a single switch environment with periodic source flows being supported over a constant bit rate (CBR) type circuit. We undertake a systematic study beginning from the simplest scenario where all traffic flows consist of data frames of the same size and with the same real-time delay requirement. In this case, we prove that the FCFS algorithm is optimal. We conclude with the most difficult case of examining CBR flows of variable bandwidth requirements and variable delay requirements. Algorithms and analysis are presented for all the cases. The simulation results show the substantial performance gains provided by the proposed algorithms.

Real-time distribution of stored video over wide-area networks (WANs) is a crucial component of many emerging distributed multimedia applications. The heterogeneity in the underlying network environments is an important factor that must be taken into consideration when designing an end-to-end video delivery system. We present a novel approach to the problem of end-to-end video delivery over WANs using proxy servers situated between local-area networks (LANs) and a backbone WAN. A major objective of our approach is to reduce the backbone WAN bandwidth requirement. Toward this end, we develop an effective video delivery technique called video staging via intelligent utilization of the disk bandwidth and storage space available at proxy servers. Using this video staging technique, only part of a video stream is retrieved directly from the central video server across the backbone WAN whereas the rest of the video stream is delivered to users locally from proxy servers attached to the LANs. In this manner, the WAN bandwidth requirement can be significantly reduced, particularly when a large number of users from the same LAN access the video data. We design several video staging methods and evaluate their effectiveness in trading the disk bandwidth of a proxy server for the backbone WAN bandwidth. We also develop two heuristic algorithms to solve the problem of designing a multiple video staging scheme for a proxy server with a given video access profile of a LAN. Our results demonstrate that the proposed proxy-server-based approach provides an effective and scalable solution to the problem of the end-to-end video delivery over WANs.

IP Multicast is an important enabling service for the current and future Internet. With the explosive, growth of the Internet, a challenging issue facing IP multicast is scalability, in particular, the problem of multicast forwarding state and control explosion. In this paper, we propose a new methodology to address the multicast scalability problem for backbone domains Multicast Tunneling with Branch Filtering (MTBF). This multicast group aggregation scheme is designed on top of the inter-domain protocol architecture such as MASC/BGMP, and is independent of any underlying intra-domain multicast protocols. It aggregates multicast groups by constructing Border Router (BR)-based multicast routing trees and forwards data by using an encapsulation technique called Multicast Tunneling (MT). To minimize excess traffic due to aggregate multicast address based data forwarding, an efficient Dynamic Filtering Point Selection (DFPS) algorithm is used. The feasibility and performance of our scheme is demonstrated through analysis and simulations.

Introduces the design, implementation and evaluation of a generic software architecture for on-demand video servers. We describe different key components for controlling the storage and network devices within the server. The interactive collaborations between these software components are also illustrated. The experimental results indicate a very promising direction in exploring the right combinations of these software components. The server is thus able to increase the number of concurrent video accesses with the same hardware configuration. For instance, with the right combinations, the system achieved about 80% of the storage system bandwidth of four disks, about 70% of the storage system bandwidth of six disks, and generally reached the maximal achieved SCSI bandwidth when eight disks are used over two SCSI buses. Our research and experimental results are based on video servers currently under construction across a variety of hardware platforms, including SMP, DMP and clusters of PCs or workstations. The most advanced prototype server is based on an SGI shared-memory multiprocessor with a mass storage system consisting of RAID-3 disk arrays. With all the enabling/management schemes, we were able to further investigate interesting research issues by considering the user's access profiles for taking advantage of popular video titles. The results were significant, with a range of 60% improvement given a 512 kByte block size. In addition to the experimental results, theoretical performance models were also developed that closely match to our collected experimental results.

Wavelength division multiplexing (WDM) has been widely used for studying the performance of optical networks, especially those employing optical passive star couplers. The current technology only allows the transceivers to be tunable in a small range, a fact ignored in previous studies. In this paper, we focus on the design of WDM optical passive star networks with tunable transmitters of limited tuning range and fixed wavelength receivers. The limited tuning range has effects on the maximum delay, the total number of wavelengths which can be used, and the topological embedding. Complete graphs, meshes and hypercubes are the three topologies studied in this paper. The relationship between the total number of wavelengths which can be utilized and the embedded topology is established. The bound for the maximum delay is analyzed. The optimal embedding algorithms are given for the systems embedded with one of the three topologies.

Current timing analysis tools deal with combinational circuit composed of primitive gates. In this paper, we are investigating ways to do timing analysis of combinational circuits with complex gates. Two possible approaches are proposed. The first approach is to design path sensitization criterion for circuits which is composed of complex gates. Another approach is first to transform complex gates to primitive gates and then using existing tools to perform timing analysis. A sensitization criterion is proposed for general complex gates where the functionality and delay information are given. Two commonly used complex gates, XOR and multiplexer, are examined and simplified sensitization criteria are generated. The gate expansion is performed on different delay models to show the compatibility between the original circuit and the transformed one. A general gate expansion algorithm is provided in this paper which can be used for general complex gates. From the experiment, we learned that the first approach can be performed in less computation time than the second one. The circuit delay obtained with the first approach is also smaller and more accurate than that obtained by the second approach.

A circuit's performance is usually measured by the delay of its longest path. A combinational circuit may contain cycles. We shall call these type of circuits "cyclic combinational circuits". In order to find the delay of a cyclic combinational circuit we need to find the delay of the longest simple path, however traditional longest path algorithms cannot be applied to circuits containing cycles. Finding the longest simple path in a cyclic combinational circuit has been shown to be NP-hard. In this paper we propose an optimal algorithm to solve this problem. The approach we use here is first to replace cycles with matched sub-circuits and then compute the longest simple path of the expanded circuit. The matched sub-circuits are carefully constructed to preserve the path information of the original cyclic combinational circuit. Since the problem is NP-hard, the proposed algorithm has exponential time complexity in the worst case. Nevertheless, the experimental results demonstrate the feasibility of the proposed algorithm.

In this paper we present a novel network-conscious approach to the problem of end-to-end video delivery over wide-area networks using proxy servers situated between local-area networks (LANs) and a backbone wide-area network (WAN). We develop a novel and effective video delivery technique called video staging via intelligent utilization of the disk bandwidth and storage space available at proxy servers. We also design several video staging methods and evaluate their effectiveness in reducing the backbone WAN bandwidth requirement. Our results demonstrate that the proposed proxy-server-based, network-conscious approach provides an effective and scalable solution to the problem of the end-to-end video delivery over wide-area networks.

Wavelength Division Multiplexing (WDM) has been widely used for studying the performance of optical networks, especially those employing optical passive star couplers. Many models have been proposed for WDM on an optical passive star coupler, such as each station equipped with a single tunable transmitter and a single fixed wavelength receiver, and each station with multiple tunable transmitters and multiple tunable receivers. The current technology only allows the transceivers to be tunable in a small range, a fact ignored in previous studies. In this paper, we focus on the design of WDM optical passive star networks with tunable transmitters of limited tuning range and fixed wavelength receivers. The limited tuning range has effects on the maximum delay, the total number of wavelengths which can be used, and the topological embedding. Complete graphs, meshes, and hypercubes are the three topologies studied in this paper. The relationship between the total number of wavelengths which can be utilized and the embedded topology is established. The bound for the maximum delay is analyzed. The optimal embedding algorithms are given for the systems embedded with one of the three topologies.

In the circuit model where outputs are latched and input vectors are successively applied at inputs, the gate resizing approach to reduce the delay of the critical path may not improve the performance. Since the clock period is determined by delays of both long and short paths in the combinational circuit, gates lying in sensitizable long and short paths can be selected for resizing. For feasible settings of the clock period, new algorithms and corresponding gate selection methods for resizing are proposed in this paper. Our algorithms are tested on ISCAS'85 benchmark circuits and experimental results show that the clock period can be optimized efficiently with our gate selection methods.

Both long- and short-path delays are used to determine the valid clocking for various complementary metal-organic-semiconductor (CMOS) circuits such as single phase latching, asynchronous, and wave pipelining. Therefore, accurate estimation of both long and short path delays is very crucial in the designing and testing of high speed CMOS circuits. Most of the previous approaches in detecting long and short sensitizable paths assume that the rising and falling of gate delays are either fixed or bounded. In fact the gate delay of CMOS circuits may also depend on how many and which inputs are rising or falling and the arrival times of those rising or falling inputs. For instance, the delay for a two-input CMOS NAND gate may vary as much as a factor of two based on whether one input or two inputs are changing. We shall refer a gate delay model which considers these factors as data dependent delay model. Gray et al. (1992) have proposed an approach based on simulation with event pruning to deal with this type of delay model. In this paper, we propose several algorithms to compute the longest and shortest sensitizable path delays based on a data dependent delay model. A proposed algorithm which is based on a combination of modified static (topological) timing analysis and path sensitization techniques seems to offer the best performance. The results obtained have shown to be more accurate than the traditional path sensitization approach based on bounded delay model.

The advances in storage, host I/O, and networks entice a variety of on-demand services. To effectively use these resources, we propose a Scalable and Extensible Architecture for Multimedia Entertainment (SESAME) to explore the modularity and scalability of a Karaoke-on-demand (KOD) service. Karaoke popularizes MTV-style entertainment to let viewers sing along. It is shown that hierarchical architecture for KOD scales well and is cost-effective in the network environment where latency is not a major concern. The modularity and scalability are achieved by: 1) distributing Karaoke data at different levels of storage based on popularity to leverage the cost of near-line and on-line storages, and alleviate hot spot access for popular titles, 2) modularizing the server design as well as service hierarchy, and 3) reducing the concurrent accesses to a server by expanding service levels such that an inexpensive computer can be a server. We illustrate live applications in a Karaoke house and in a campus-wide setting. The SESAME approach is being extended to some other areas of interests such as distance learning.

To extend the widespread use of the high performance parallel interface (HIPPI) as a networking solution for high-speed communications, the 25-meter distance limitation must be solved. Three options available for alleviating the problem of distance limitation are serial-HIPPI, HIPPI/SONET mapping or HIPPI-ATM mapping, and IP routing. Serial-HIPPI, HIPPI/SONET mapping and HIPPI-ATM mapping provide extended HIPPI connectivities at the physical layer, while IP routing forwards data between the HIPPI networks and other networks at the network layer. We study two feasible solutions of this problem, HIPPI tunneling (HIPPI-ATM mapping) and IP routing. We compare these two schemes in terms of network connectivities, protocol overhead, and flow control. The performance evaluation of one implementation of HIPPI tunneling and IP routing is presented. The experimental performance suggests that a high degree of bandwidth utilization was achieved by both HIPPI tunneling and IP routing in this implementation.

Future video-on-demand (VOD) servers will need to support many existing and emerging video data types. These data types include 15-fps (frames per second) animation, 30-fps NTSC (National Television Systems Committee) quality video and 80-fps HDTV (High Definition Television) video. The different display speeds and frame sizes of these various video types impose a major constraint on the design of VOD storage systems. This paper presents the results of an experimental study, conducted on a Silicon Graphics Inc. Onyx computer system, that investigated the impact of these video types on the design of a VOD storage system. The key issues involved in supporting these different video types in a VOD environment are: (1) the video allocation method, and (2) the proper block size (a block is a basic unit of several contiguous video frames that will be accessed from several disks each time a request is made) to use for data striping and retrieval. Two allocation schemes, logical volume striping and application level striping, along with varying frame and block sizes for each of the three different video data types are examined. The focus of our study is to determine the maximum number of concurrent accesses that can be supported with a guaranteed quality of service. The degree of scalability (i.e., striping data over more disk arrays) of the experimental VOD system used is also studied.

For many multimedia multicast applications, especially those requiring real-time traffic, it is important that the maximum delay bound requirement between any pair of group members be satisfied. Most studies on multicast routing have been based on a single multicast tree (a shortest path tree or a minimal Steiner tree) approach. By using only a single multicast tree for a multicast group, satisfying the maximum delay bound requirement is nearly impossible. To fulfill these requirement, we adopt the multiple multicast tree concept whose disadvantage is the high tree maintenance cost. Since the tree maintenance cost is proportional to the number of multicast trees for a multicast group, it is necessary to minimize the number of multicast trees. In this paper, we formulate the delay-bounded multicast tree (DBMT) problem whose main objectives are to satisfy an application's maximum delay bound among the group members and to minimize the number of multicast trees needed for a group communication. We categorize the DBMT problem according applications' needs into two subproblems, the shortest path tree-based DBMT (SPT DBMT) and the minimal Steiner tree-based DBMT (MST DBMT) problems. For the DBMT subproblems, we prove the NP-hardness and propose heuristic algorithms. For the performance analysis, simulations were performed.

An effective network-based learning environment provides synchronous and asynchronous education to learners who are physically, remote from or opt to telecommute to the base location of instruction. The environment provides content creation, user registration, course material storage, multiple delivery means, and end-user viewing tools. An intriguing aspect of the environment is how to model a lecture in terms of pre-, in-, and post-class information. We regard a lecture model collectively as an activity consisting of three elements: lecture materials, lecture presentation, and lecture interaction. We derive the synchronization specification for the media objects and define strong-weak networked hyperlink (SWNH) to represent the lecture structure and inter/intra media object reference in the distributed network environment. The specification and representation exhibit an object-oriented modular design. The presentation of the lecture embody both the event-driven and timeline-based presentation synchronization where the browsing and authoring tools developed earlier fit right into the learning environment, e.g. FLIPS and HQT by the authors, or are immediately available through other providers, e.g. Web browsers.

Lightwave networks can be built by embedding virtual topologies over physical topologies. The optical passive star enables such embeddings easily. The Shuffle-net and the De-Bruijn graph are two popular virtual topologies proposed in the past for lightwave networks. Both however suffer from a lack of flexibility in scaling network sizes. We present a generalization of the De-Bruijn network which overcomes the limitation of the strict relationships between the network size parameters seen in the Shuffle-net and the De-Bruijn networks. A generalization for the Shuffle-net is also possible with this idea. We emphasize the support of time and wavelength division multiplexed media access protocols for such architectures and present several properties of the proposed network with respect to the same.

Future video-on-demand (VoD) servers will need to support many existing and emerging video data types. These data types include 15-fps (frames per second) animation, 30-fps National Television Systems Committee (NTSC) quality video, and 60-fps high definition television (HDTV) video. The different display speeds and frame sizes of these various video types impose a major constraint on the design of VoD storage systems. This paper presents the results of an experimental study, conducted on a Silicon Graphics Inc. (SGI) Onyx computer system, that investigated the impact of these video types on the design of a VoD storage system. The key issues involved in supporting these different video types in a VoD environment are as follows: (1) the video allocation method and (2) the proper block size (a "block" is a basic unit of several contiguous video frames that will be accessed from several disks each time a request is made) to use for data striping and retrieval. Two allocation schemes, logical volume striping and application level striping, along with varying frame and block sizes for each of the three different video data types are examined. The focus of our study is to determine the maximum number of concurrent accesses that can be supported with a guaranteed quality-of-service (QoS). The degree of scalability (i.e., striping data over more disk arrays) of the experimental VoD system used is also studied. Based on our experimental results, application level striping demands smaller block sizes for all three video types, and more concurrent accesses can be distributed over the storage devices. The experimental results demonstrate that application level striping has excellent scalability for animation and NTSC videos.

Multimedia presentation technology has enormous potential for a myriad of applications including academic classrooms, industrial training, and business presentations. As presentation technology advances, it is possible to incorporate a wider range of media including variable duration media such as simulations and animations. At the same time, users are able to take more control over presentations by controlling the rate and selection of media being played. To make full use of these advances, multimedia systems must support flexible presentations that incorporate many variations in the way they are played. This paper identifies three requirements for flexible presentations and derives four requirements for synchronization of flexible presentations. The paper presents flexible interactive presentation synchronization (FLIPS), a model for specifying coarse synchronization for flexible presentations. FLIPS supports a wide range of temporal synchronization specifications. It also provides algorithms for attaining a consistent and coherent presentation state in response to user interaction (e.g. skipping to a different slide or selection) and other state-changing events. Applications of the FLIPS model are discussed.

This paper introduces the concept of time slot synchronization in time-wave division multiplexed (TWDM) multihop lightwave networks. It is shown that the time slot assignments of the intermediate nodes in a multihop path have significant effect on the end-to-end message delay. This is different from traditional notions in routing, where the hop count and congestion control are the primary concerns. Assuming a TWDM embedding of a given logical topology already exists, we formulate the optimal routing problem for arbitrary propagation delays. We propose a graph unfolding technique which converts this problem into the shortest path routing problem for weighted graphs with well known solutions. We show a method to estimate the buffering cost at the intermediate nodes (in multihop routing) to accommodate high-bandwidth traffic (e.g., video). Next, we address the question: given a logical topology what should the TWDM embedding be so that the routing delays are optimized P This leads us to an iterative approach for TWDM embedding. Given an initial embedding an optimal route is estimated for each pair of nodes. A weighted average of these optimal route distances is used as a metric to evaluate the TWDM embedding. Using a heuristic the TWDM embedding is modified and the process iterated to improve along this metric. Preliminary performance results illustrating the improvement in routing delay are provided. For example, for a 4-cube network on average delay minimization of 10% to 20% is observed.

Communication between processors has long been the bottleneck of distributed network computing. However, recent progress in switch-based high-speed local area networks (LANs) may be changing this situation. Asynchronous transfer mode (ATM) is one of the most widely-accepted and emerging high-speed network standards which can potentially satisfy the communication needs of distributed network computing. We investigate distributed network computing over local ATM networks. We first study the performance characteristics involving end-to-end communication in an environment that includes several types of workstations interconnected via a Fore Systems' ASX-100 ATM switch. We then compare the communication performance of four different application programming interfaces (APIs). The four APIs were Fore Systems' ATM API, the BSD socket programming interface, Sun's remote procedure call (RPC), and the parallel virtual machine (PVM) message passing library. Each API represents distributed programming at a different communication protocol layer. We evaluated two popular distributed applications, parallel matrix multiplication and parallel partial differential equations, over the local ATM network. The experimental results show that network computing is promising over local ATM networks, provided that the higher level protocols, device drivers, and network interfaces are improved.>

Both long and short path delays are used to determine the valid clocking for various CMOS circuits such as single phase latching, asynchronous and wave pipelining. Therefore, accurate estimation of both long and short path delays is very crucial in the designing and testing of high speed CMOS circuits. Most of the previous approaches in detecting long and short sensitizable paths assume that the rising and falling of gate delays are either fixed or bounded. We propose several algorithms to compute the longest and shortest sensitizable path delays based on a data dependent delay model. A proposed algorithm which is based on a combination of modified static (topological) timing analysis and path sensitization techniques seems to offer the best performance. The results obtained have shown to be more accurate than the traditional path sensitization approach based on the bounded delay model.>

We consider the problem of determining a valid clock setting for a combinational circuit. The performance of a circuit depends on its clock period. The shorter a valid clock period is, the better the performance is. We have proposed two new bounds for clock period by considering a type of paths called functionally sensitizable paths. Then these results are extended to wavepipelined circuits. We have compared the new bounds with the previously proposed bounds and it has been shown that these new bounds may have better performance for certain combinatorial circuits. We have also given an example to show that the path delays obtained by two-vector model may not be valid when used for clock setting. The bounds on clock period can alternatively be viewed as optimization objectives. We present some experimental results to show various bounds on clock period for ISCAS benchmark circuits and discuss the potential complexity of optimizing circuits with these bounds.>

Single-fault, multi-fault, 0-1 static sensitizable path, and robust path delay fault are often used to measure the testability of a circuit. We explore the relationships among these testabilities. In addition to the relationships discovered before, we prove that 100% single fault testability, 100% 0-1 static sensitizability are equivalent in two-level single-output circuits. We also prove that 100% 0-1 static sensitizability implies 100% multi-fault testability, and that 100% robust path delay fault testability implies 100% multi-fault testability in two-level circuits. Several new conditions for gate merging while keeping 100% single-fault testability are presented. We further prove that the three transformations D/sub 1,1,2/ (J. Rajski and J. Vasudevamurthy, 1992), extraction, De-Morgan keeping 100% single fault testability also preserve 100% multiple-fault testability, 100% multi-fault testability, 100% robust path delay fault testability. We answer the following two open questions: does 100% multi-fault testability in a multiple outputs circuit not require 100% 0-1 static sensitizability? Does 100% multi-fault testability in a single output circuit imply 100% 0-1 static sensitizability?.>

Recent progress in switch based high speed local area networks (LANs) makes distributed network computing promising. Three evolving switch based high speed networks are the High Performance Parallel Interface (HIPPI), Fiber Channel (FC), and Asynchronous Transfer Mode (ATM) standards. We study how high performance computing can be carried out over such networks. High performance computing can be characterized as follows: it includes multiple modules and each module is executed in a processor; its communication data flow forms a special application topology and usually such application topologies are regular; and it requires frequent communication between adjacent modules in the application topology. In order to reduce the amount of time required for a processor to set up a connection during the execution of an application, we propose a new communication protocol called the Virtual Permanent Connection (VPC). For a given application topology, a set of connections are set up and permanently maintained during the execution of the application. Communication between processors are via this group of connections. We study how a set of VPCs are chosen based on a given application topology (this process is called application topology embedding).

The paper examines the efficient layout of virtual paths (VPs) in an ATM network. The ATM network consists of ATM switches and their attached network end users, which may be gateways, routers, and hosts. The physical topology, the offered traffic, and call setup matrices of the network end users are assumed to be given. The problem is formulated as a flow-based optimization problem. A heuristic approach is presented which (i) establishes VPs according to physical network-specific and application-specific constraints and a cost function, (ii) provides multipaths between each source destination user pair to minimize the cell blocking probability and to increase network resilience, and (iii) uses a novel VP combining process which is guaranteed to always satisfy the switching constraints. Simulation results are presented for the proposed VP planning policy. Guidelines for the design of robust VP layouts and the efficient establishment of VCs are also presented.>

Emerging high-speed networks provide several hundred megabits per second to several gigabits per second of raw communication bandwidth. However, the maximum achievable throughput available to the end-user or application is quite limited. In order to fully utilize the network bandwidth and to improve the performance at the application level, a careful examination of I/O subsystems is essential. In this paper, we study one emerging high-speed network, the Fibre Channel network. The objectives of this study are: to understand how the I/O subsystem relates to network operations; to evaluate and analyze the performance of such a subsystem; and to propose possible approaches for improving the maximum achievable bandwidth. We show (by simply modifying device driver code) a 75% maximum achievable bandwidth improvement. Other ways of improving network performance are also discussed.>

Communication between processors has long been the bottleneck of distributed network computing. However recent progress in switch-based high-speed local area networks (LANs) may be changing the situation. Asynchronous transfer mode (ATM) is one of the most widely-accepted and emerging high-speed network standards which can potentially satisfy the communication needs of distributed network computing. We investigate distributed network computing over local ATM networks. We first study the performance characteristics involving end-to-end communication in an environment that includes several types of workstations interconnected via a Fore Systems' ASX-100 ATM Switch. We then compare the communication performance of four different application programming interfaces (APIs). The four APIs were Fore Systems ATM API, BSD socket programming interface, Sun's Remote Procedure Call (RPC), and the Parallel Virtual Machine (PVM) message passing library. Each API represents distributed programming at a different communication protocol layer. We evaluate parallel matrix multiplication over the local ATM network. The experimental results show that network computing is promising over local ATM networks.>

The IEEE 802.6 Standard/spl minus/Distributed Queue Dual Bus (DQDB)/sup 1//spl minus/for metropolitan area networks (MAN's) has been proposed. It is based on a unidirectional twin bus architecture. The DQDB protocol lays more emphasis on the overall channel utilization than the fair sharing of channel bandwidth by all the stations. In this paper, we first describe the unfairness problem in which the upstream stations occupy most of the channel bandwidth while the downstream stations get fewer chances to transmit their packets. Many proposed possible fixes are also discussed. We propose a protocol called Cycle Compensation Protocol (CCP), which ensures fairness regardless of the ratio of end-to-end propagation delay to the slot size and also achieves almost the same throughput and delay as those of DQDB. CCP also guarantees that the channel bandwidth acquired by a station is inversely proportional to the number of busy stations and will reach this state within a limited time delay.>

In this paper, we consider the problem of determining the smallest clock period for a combinational circuit. By considering both the long and short paths, we derive three independent bounds on the clock period. The first bound is the difference between the longest path delay and the shortest path delay. The other two take the functionality of the circuit into consideration and, therefore, are usually smaller than the first one. To bring in the functionality of the circuit, we make use of a new class of paths-called the shortest destabilizing paths-as well as the longest sensitizable paths. We also show that considering both the longest sensitizable path and the shortest destabilizing path together does not always give a valid bound. The bounds on the clock period can be alternatively viewed as optimization objectives. At the physical level, the complexity of optimization very much depends on the number of long and short paths present and the number of gates shared by them. We conducted preliminary experiments to study this.>

The estimation of signal stable ranges in a combinational circuit is an important issue for determining clock time in a synchronous system. An optimal clocking period time highly depends on the accuracy of the shortest path length as well as the longest path length in a combinational circuit. In this paper, a sensitization criterion for the short path is first proposed. Based on this sensitization criterion, an accurate model for calculation of signal stable range can be created. This will allow the output stable range of a gate to be the union of its inputs when the input leads hold a controlling value, rather than to be always the intersection. Then, an LS-algorithm for calculation of signal stable ranges is presented in which both the sensitizable shortest path and the sensitizable longest path are considered. It avoids the exhaustive search by tracing the path sensitization and eliminates some conservative restriction to get more accurate results in a more efficient way, compared to the previous approaches. The speedup and the improved accuracy of the proposed LS-algorithm showed promising experimental results.>

The problem of identifying one of the longest sensitizable paths in a circuit is called a critical path problem. Several critical path algorithms have been proposed in the last few years. However, due to the long computation time required to produce accurate results, these algorithms may not be able to generate any result for large designs with many long false paths unless the accuracy of the results is compromised. Parallel processing seems to be an appropriate way to speed up the required computation. In this paper, we study the parallel algorithms for critical path problem. We first present a sensitization criterion. Based on this sensitization criterion an algorithm called DT-algorithm, which is a variation of the D-algorithm with stable time range of signals also taken into consideration, is developed. The DT-algorithm is especially suitable and can be used to determine the sensitizability of a given path in a parallel processing environment. We also present an implementation of parallel DT-algorithm that can be executed on a shared memory multiprocessor. The experimental results show that a reasonable speed-up can be obtained.>

We study the problem of choosing gate implementations to reduce circuit area while retaining the circuit performance. To incorporate timing analysis into area reduction, we propose to utilize the information provided by a sensitization criterion in computing the slacks of the gates. Not all sensitization criteria can be adopted in our approach. Some conditions were imposed to define a class of sensitization criteria which can guarantee that the circuit performance will be preserved. A greedy area reduction heuristic is proposed, and then an improved version of the Brand-Iyengar and the static sensitization criteria are plugged into the heuristic to obtain results for comparison (D. Brand, V. Iyengar, 1986).>

The idea of providing reverse channels with minimal hardware costs in Shuffle-nets to reduce the network diameter improve mean delay, and provide other advantages is discussed. The reverse channel idea can be applied to any multistage network with wrapped around connections. The advantages of reverse channels are demonstrated by providing a simple reverse connection between adjacent stages of the Shuffle-net. It is shown how a time- and wavelength-division-multiplexed media access protocol for the Shuffle-net can be easily adapted for the reverse channel augmented Shuffle-net (RC-Shuffle-net). The performance of the RC-Shuffle-net and its advantages over the Shuffle-net are shown.>

The authors formulate and propose an algorithm for the LBMT (load-balancing multicast tree) problem whose main objective is to accomplish traffic load balance while minimizing the number of multicast trees for a group. In order to fulfill these objectives, the multiple multicast tree concept, whose only disadvantage is the high tree maintenance cost, is introduced. Since the tree maintenance cost is proportional to the number of multicast trees for a multicast group, it is necessary to minimize the number of multicast trees. The authors' LBMT algorithm is based on the minimal Steiner tree approach by using the information on the available capacities of the links. For the algorithm, several link cost functions which take the available capacities on both directions into account are proposed.

A heuristic algorithm is presented for efficiently embedding a virtual hypercube into an irregular wavelength division multiplexing (WDM) network so that the message propagation delay is minimized. Embedding a hypercube allows the communications of the many hypercube-base algorithms to map directly to the virtual network. The authors' algorithm optimizes the embedding by effective assignment of virtual addresses as well as the efficient routing of virtual connections. The three-step approach is first based on embedding the irregular graph in a hypercube so that the number of virtual edges that correspond to physical edges is minimized. The routing of the virtual connections and their assignment to logical channels is performed while minimizing the number of wavelengths that must be supported by the WDM system. Experiments with the proposed algorithm show it to produce embeddings with significantly shorter path lengths and requiring fewer wavelengths than previous methods for practical networks.

A media access protocol is presented for time- and wavelength-division multiplexed optical passive star networks. The protocol is based on a bus-mesh virtual topology. The network provides minimum latency and high throughput while requiring only a single fixed wavelength transmitter and receiver at each station. The use of nonagile, fixed wavelength devices, readily available with current technology, reduces costs, improves reliability and avoids tuning delays and limitations. The multihop access protocol operates effectively in an environment with lengthy propagation delays. The wavelength-division multiplexing system is required to support only a small, easily achievable number of wavelength channels.>

Wafer packing is a process of combining multiple chip designs on the same wafer such that the fabrication cost can be shared by several designs and hence reduced. This technique is widely used for designs that require a small number of dies or chips. It is essential to have computer algorithms to decide how to allocate designs to wafers in order to reduce the total fabrication cost. Based on different wafer fabrication techniques, two versions of the wafer packing problem are formulated. The authors study different variations for each version. They present algorithms to find optimal solutions for these variations which are polynomial-time solvable. They also present heuristic algorithms for those proven to be NP-hard. The effectiveness of the proposed algorithms is demonstrated by experimental results.>

An important aspect of the critical path problem is deciding whether a path is sensitizable. Three new path sensitization criteria are proposed in a general framework. Other path sensitization criteria can be presented in the same framework, enabling them to be compared with each other. An approximate criterion is also proposed and used to develop an efficient critical path algorithm for combinational circuits.>

The problem of selecting a set of paths to optimize the performance of a combinational circuit is studied, assuming that gate resizing and buffer insertion are the two possible optimizing techniques for reducing the delay of a circuit. The objective of the path selection problem is to select as small as possible a set of paths to ease the optimization processing to guarantee that the delay of the circuit is no longer than a given threshold tau if the delays of all the selected paths are no longer than tau . It is shown that the path selection is different from path sensitization. An input vector-oriented path selection algorithm is proposed. Because it may be infeasible for complex circuits with many primary inputs, a path-oriented algorithm is also developed and implemented. Experimental results on ISCAS85 benchmark circuits show a potentially big improvement for the optimization process.>

Many proposals of virtual regular topologies embedded in physical topologies for high-speed wavelength division multiplexing (WDM) optical networks do not consider the issue of allowing a variable number of nodes in the network. A solution for embedding a virtual unidirectional incomplete hypercube into a physical topology that does is presented. The proposed solution is a multichannel multihop network which has several elegant features: (a) it allows any number of nodes to be connected to the network, (b) it only requires a minor effort to reconfigure the new interconnection whenever a node is added or deleted for the network, (c) it supports a self-routing strategy, (d) the aggregate throughput of the network increases as more nodes are added, and (e) alternate paths are available which have a comparable distance to the destination as the primary path. The performance of the scheme is comparable to the performance of both the unidirectional hypercube and the bidirectional hypercube.>

In this paper we study the problem of selecting a set of paths to optimize the performance of a circuit.We assume that gate resizing is the optimizing technique used to reduce the delay of a circuit.That is, during the optimization process the topology of a circuit remains the same and the gate delays are reduced.The objective of the path selection problem is to select as few paths as possible so that when the delays of all selected paths are shortened, the delay of the optimized circuit is guaranteed to meet its performance requirement.We first propose an input vector oriented path selection algorithm.Due to the fact that the input vector oriented algorithm may be not feasible for complex designs with many input pins, we have designed and developed a path oriented algorithm.For some ISCAS circuits, less than 10% of the long paths are selected by our path oriented algorithm.

Article Free Access Share on An efficient parallel critical path algorithm Authors: Li-Ren Liu Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile , David H. C. Du Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile , Hsi-Chuan Chen Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 535–540https://doi.org/10.1145/127601.127728Published:01 June 1991Publication History 11citation431DownloadsMetricsTotal Citations11Total Downloads431Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Since the delay of a circuit is determined by the delay of its longest sensitizable paths (such paths are called critical paths), the problem of estimating the delay of a circuit is called critical path problem. One important aspect of the critical path problem is to decide whether a path is sensitizable. A framework which allows various previously proposed path sensitization criteria to be compared with each other in a unified way is presented. An exact path sensitization criterion and a looser path sensitization criterion based on the framework are also proposed.>

The estimation of signal stable ranges in combinational circuits is an important issue for setting clock time in a synchronous system. The authors first propose a sensitization criterion for the shortest path, and they then use a path-oriented approach to reduce search space. Considering the possible case where the signal stable range at the output of a gate could be the union of inputs, one can obtain more accurate results than with the intersection approach.>

The authors formulate and classify the various models of the wafer packing problem for the full mask exposure technique. Since the wafer packing problem is NP-hard, the authors propose a good heuristic for it. Their experiments, on real test data, indicate that this heuristic is very effective as it provides considerable cost reduction when compared with the traditional way of producing chips.>

The authors' research addresses some of the underlying design principles for a new class of metropolitan area networks (MANs) based on current lightwave technology, optically switched wavelength-division multiplexed (WDM) networks. A unique feature of WDM networks is their ability to create many different virtual topologies on top of the given physical topology. The authors describe problems associated with the design of optically switched WDM networks, study the embedding of regular virtual topologies into regular and irregular physical topologies, tabulate some characteristics of embedded regular virtual topologies and provide a procedure for computing the maximum number of wavelengths required for virtual topology embeddings.>

A dynamic hashing scheme based on extendible hashing is proposed whose directory can grow into a multilevel directory. The scheme is compared to the extendible hashing and the extendible hashing tree schemes. The simulation results reveal that the proposed scheme is superior than the other two with respect to directory space utilization, especially for files with nonuniform record distribution. This scheme can be easily extended to multikey file systems and also has good performance.>

A new approach to the performance-driven placement based on a window concept is presented. We first convert timing constraints to geometric shapes using the defined windows. A window represents a region in which all the modules along a given path can be placed without degrading the circuit performance. Then a constructive placement process uses the window information to select an unplaced module, and to find an appropriate position for the module. This approach represents a unified way to consider both timing and geometric constraints during the placement process. The experimental results show that the improvement of circuit performance can be achieved by the sufficient use of the window information.

The IEEE 802.6 standard distributed queue dual bus (DQDB) for metropolitan area networks (MANs) is considered. It is based on a unidirectional twin-bus architecture. The DQDB protocol lays more emphasis on the overall channel utilization than the fair sharing of channel bandwidth by all the stations. The resulting unfairness problem in which the upstream stations occupy most of the channel bandwidth while the downstream stations get fewer chances to transmit their packets is discussed. Many previously proposed possible fixes are also reviewed. However, these schemes either have a lower performance or cannot guarantee complete fairness when the ratio of end-to-end propagation delay to the slot-size is large. A cycle compensation protocol which ensures complete fairness regardless of the ratio of end-to-end propagation delay to the slot size is described. This proposed protocol also achieves almost the same performance as that of DQDB.>

Two unidirectional hypercube topologies are proposed. Both have short diameter, short average distance, efficient routing, and multiple paths characteristics, and can accommodate a large number of nodes. They simplify the communication port hardware from bidirectional to unidirectional, and hence allow one to build larger VLSI hypercubes as well as to implement hypercube-based MANs (metropolitan area networks) with optical fibers. Improvements to and optimizations of the proposed schemes are discussed.>

The false path problem is often referred to as the problem of detecting the longest sensitizable path (A path which is not a false path is a sensitizable path). The term “false path” is not clearly defined. In this paper, we first give a clear and precise definition of a false path. Then the general false path problem is formulated. The general false path problem is to detect whether a given path (not necessarily the longest one) is a false path. We present an efficient algorithm for solving the general false path problem. We also propose another algorithm which generates all the possible sensitizable paths with the delays greater than a given threshold T. The efficiency and effectiveness of the proposed algorithm are demonstrated by the experimental results.

We have developed a gate matrix layout synthesis tool which utilizes folding technique on both rows and columns. The conventional interval graph model and the recently proposed dynamic net-list representation can not fully depict circuit schematics such as inter-net connections. The incomplete representations may mislead the search process for an optimal solution during the layout partitioning and the gate ordering phases. We propose a new graph-based model called hierarchical dynamic net-list to improve the schematic representation. Based on the new model, the folded layout area in the partitioning phase can be more accurately estimated. The new gate ordering algorithm proposed by us also takes the advantages of the hierarchical dynamic net-list model to handle the gate placement in the folded layouts. The experimental results show 12% to 15% improvement in layout area for small circuits and 30% improvement for a large circuit.

Path extracting algorithms are a very important part of timing analysis approach. In this paper we designed and developed several algorithms which can generate the K most critical paths in a non-increasing order of their delays. The effectiveness of these algorithms is shown by some experimental results.

Multiple-channel architectures have been proposed for broadcasting-based local area networks to overcome the problem of deteriorating performance when a very high speed communication channel is used. Such networks are called multiple-channel local area networks (M-LANs). In a carrier-sense multiple-access with collision detection (CSMA/CD) protocol designed for M-LANs (M-CSMA/CD), a ready station selects only one channel to transmit its packet according to some channel selection mechanism. A new CSMA/CD protocol for M-LAN architecture is proposed by which a station may select and try to transmit the same packet on K channels (K>or=1). If it has been successfully transmitted on more than one channel after the end-to-end propagation delay, it randomly selects one channel to finish its transmission and immediately stops its transmission on the rest of the channels. This is called the multipacket multichannel CSMA/CD protocol (MM-CSMA/CD). The performance of the proposed MM-CSMA/CD protocol can be shown to be potentially better than that of the M-CSMA/CD protocol and the traditional CSMA/CD protocol.>

The authors obtain a tighter lower bound on the street congestion of optimal realizations. Then a heuristic algorithm based on necessary and sufficient conditions of optimality is proposed. Although it cannot be guaranteed that this algorithm always generates optimal realizations, it indeed generates optimal realizations for all the 60 test instances with which they experimented. This algorithm is also shown to be time efficient.>

Efficient, reservation-based CSMA/CD protocols for handling multiple-priority-class traffic are presented. The new protocols allow the transmission of a varying-length stream of packets with just a single reservation. Two protocols are proposed, one for a system in which the number of active users (contenders) in the currently highest priority class can be determined during the reservation period, and the other for a system in which this number cannot be determined. If the number of active users is known, then optimal p-persistence is used to transmit the packets; otherwise, a dynamically determined combination of one-persistant and p-persistent periods is used to transmit the packets in the reserved priority group and to prevent lower priority users from interrupting the reserved priority transmission stream. Preemptive and nonpreemptive versions of the protocols are described. A simple analytical model is developed and used to obtain channel efficiency as a function of priority group size. Using this model, it is shown that the new protocols allow higher channel utilization than previous, reservation-per-attempted-transmission protocols.>

A file system tailored to the general needs of the office environment is proposed. This system supports large numbers of a wide variety of documents and inexact fuzzy queries on the documents. The file system is based on a multilevel file structure that combines and extends multikey extendible hashing and signature files to create a document-retrieval system that is more time efficient than other previously proposed systems and is also space efficient.>

The authors propose basic access protocols for a twin-bus unidirectional bus system (UBS) implementation. The proposed protocols are fairly similar to that of Fasnet. However, the gaps between cycles have been considerably reduced. The savings will particularly increase with cable bandwidth. In fact, except for a few cases of light load traffic the proposed protocol achieves close to 100% channel utilization.>

The twin-bus architecture for voice/data integration is discussed and a hybrid protocol for the data bus that combines CSMA/CD (carrier sense multiple access with collision detection) and announcement reservation schemes is proposed. To improve the performance on data bus, part of the bandwidth on the voice bus is used as the control subchannel for announcement reservation on the data bus. Simulation results show that the proposed hybrid protocol outperforms both CSMA/CD and the announcement reservation scheme in all cases. Since announcement reservation has good performance when traffic load is heavy, the combined protocol becomes efficient for both light and heavy loads.>

The layer assignment problem for interconnect is the problem of determining which layers should be used for wiring the signal nets so that the number of vias is minimized. The problem is often referred to as the via minimization problem. The problem is considered for three-layer routing, concentrating on one version called the constrained via minimization (CVM3) problem. It is shown that the CVM3 problem is NP-complete and a heuristic algorithm is proposed. The experimental results show that the proposed algorithm is efficient and generates fairly good solutions.>

The authors study the via assignment problem when vias are allowed to appear rowwise as well as columnwise. Previously they proved that the problem belongs to the class of NP-hard problems and therefore it is unlikely that polynomial-time algorithms exist for solving the problem. Two heuristics (HEU1 and HEU2) to solve the problem were proposed. HEU1 splits the nets before any routing is done while HEU2 assigns the nets alternately to via rows and via columns. Here they modify HEU2 so that the side of the board to which the nets are assigned first for connection is selected according to a desired ratio of board width to height.>

Numerous solutions to the problem of detailed routing of wires on a chip have been proposed for two routing layers but few are general enough to also handle switchboxes, more than two layers, variable channel widths, or multiple-layer problems with stacked terminals (3-D routing) without extensive modifications. We propose a different routing approach that not only can solve the two layer problem but the other problems as well. The inherent parallelism of the approach lead to a coarse-grained parallel algorithm.

CAD databases have been used to store design data and to integrate design tools in IC/VLSI design systems. However, the requirements for a “good” CAD database are much more complex than those for a conventional database. Due to both the complexity of various design processes and the enormous amount of data involved in a practical CAD database, we believe that a two-level hierarchical database including a global database and a set of local databases is necessary. In this paper, we propose a framework for such CAD databases. We concentrate on the overall system architecture.

A file system tailored to the general needs of the office environment is proposed. This system supports large numbers of a wide variety of documents and inexact ‘fuzzy’ queries on the documents. The file system is based on a multilevel file structure; the structure combines and extends multikey extendible hashing and signature files to create a document retrieval system that is more time efficient than other previously proposed systems, and also space efficient.

A heuristic algorithm, based on the criterion of having nets with larger cut numbers assigned to inner tracks and nets with smaller cut numbers assigned to outer tracks, for single row routing problem has recently been proposed by Tarng et al. It has been reported that this algorithm has always been able to produce the optimal solutions for all the examples tested so far. In this paper, we have proved that algorithms based on the heuristic criterion of cut numbers produce optimal solutions for instances in which all nets cover at least one common node (i.e., form a single group). However, the algorithm proposed by Tarng et al. may not produce optimal solutions for instances of multiple net groups. Thus, several possible heuristic algorithms based on the same criterion, but also taking into consideration the net grouping situation have been proposed. The experimental results show that the proposed algorithms are faster and often generate better results than the one proposed by Tarng et al. A tighter lower bound on the number of tracks required is also obtained in this paper.

The layer assignment problem for interconnect is the problem of determining which layers should be used for wiring the signal nets. The objective of the layer assignment problem in general is to minimize the number of vias required. Thus, it is also referred to as the via minimization problem. In a via minimization problem, if the topology of the given layout is fixed, the problem is referred to as a constrained via minimization (CVM) problem. On the other hand, if both the topology of the layout and the layer assignment are to be decided, it is referred to as an unconstrained via minimization (UVM) problem. In this paper, both the CVM and UVM problems are studied. For the CVM problems, efficient algorithms which can be easily modified to take extra constraints into consideration are proposed. Experimental results show that the proposed algorithms for the CVM problem are time efficient compared with existing algorithms and generate better (near-optimal) results. For the UVM problems, a new heuristic approach is presented which generates better results but takes longer computing time. In the CVM problem, some vias are "essential" to the given layout. That is, they have to be selected and cannot be replaced by other possible vias. An efficient algorithm for identifying essential vias is also presented and discussed in this paper.

Previous studies of the single-row routing problem have been restricted to the minimization of the total number of horizontal tracks needed for the realization of a given set of nets. Therefore, it has been assumed that enough space exists between adjacent nodes to allow for the wiring. Due to this assumption, realizations obtained with previously proposed algorithms may require a large number of vertical tracks between adjacent nodes. In this paper, we study the single-row routing problem when the number of vertical tracks available between adjacent nodes is bounded by a positive integer called the crossover bound. We give some results concerning crossovers and prove that, for any given positive integer K, an instance can be constructed such that the vertical track requirement between adjacent nodes cannot be less than K. We develop a fast algorithm for the case when the number of horizontal tracks available as well as the number of vertical tracks available between adjacent nodes have been preset. We compare the performance of our algorithm to the performance of an algorithm (proposed in [6]) which is fast and does not consider the vertical track constraint. Our experiments show that, in all cases, the realizations found by our algorithm have the same street capacities as those obtained by the algorithm proposed in [6]. However, unlike the realizations found with the algorithm proposed in [6], the ones found by our algorithm have smaller crossover bounds. The computing time of our algorithm is, in general, no worse than the computing time of the algorithm proposed in [6].

In the study of data storage and retrieval involving secondary storage devices, for example, magnetic disks, a simplified model of storage that is often used is that each access takes a constant amount of time. However, if some information about the accesses is known, the model should take into consideration the inherent characteristics of the storage devices. In this paper, we assume a more refined model of storage that takes into consideration the seek time, the latency time, and the transmission time of disk accesses separately. We analyze the time required to randomly access a set of records residing on a set of consecutive cylinders on a magnetic disk a number of times, say n, for n ≥ 1. This problem may arise, for example, in the processing of queries that involve several relations in a relational database system. We also analyze the more general situations in which the n operations may represent retrievals, insertions, or deletions, or a combination of them. We assume that the dynamic file structure linear hashing is used for locating and organizing the records. A linear hashing file does not employ any directory and its primary data buckets are assumed to be contiguous, therefore the data area of a linear hashing file corresponds closely to the disk space on a set of consecutive cylinders.

The objective of the via minimization is to assign wire segments into different layers to minimize the number of vias required. Several algorithms have been proposed for the Constrained Via Minimization (CVM) problem where the topology of the given layout is fixed. In a CVM problem, some vias may be “essential” to the given layout. That is, they have to be selected and cannot be replaced by other vias. In this paper we present a procedure to find most of the essential vias. This procedure can be used as a preprocessor for the algorithms for CVM problems. Experimental results show that the procedure is efficient and can identify most of essential vias.

In this paper we present two n-layer channel routing algorithms that guarantee successful routing of the channel for n greater than three. The first is linear and optimal given a VHV …HV assignment of layers. The second, using an HVH…VH layer assignment, is quasilinear and performs optimally on examples from the literature. Except in pathological cases, we expect the latter router to perform within one row of optimal. For comparison with published examples we implemented the second router in five and three layers. The five-layer implementation routed all examples optimally while the three-layer implementation routed the examples with the same or fewer rows than the published examples. With its n-layer capability this channel router will allow channel routing to be used when more than three layers are available. This router can also be used to evaluate the utility of additional layers.

The routing problem for Printed-Circuit Boards (PCB's) is crucial in the fabrication of today's digital systems. Traditionally, this problem has been divided into two main sub-problems: layer assignment and routing. Considering these two problems apart from each other may cause uneven wire distribution both among the wiring layers and within each layer. Uneven wire distribution among the wiring layers could increase the number of wiring surfaces required for the routing. Uneven wire distribution within a layer could result in an unfeasible routing. We propose a new approach to deal with the routing of PCB's in technologies which allow short vias. The proposed methodology considers the layer assignment and routing problems in a unified fashion. Based on some global information, our algorithm first estimates the initial number of layers required for the routing. It then determines an ordering in which nets should be considered during the layer assignment process. The results of our experiments show that our algorithm is of practical use.

The general problem of concurrency control for database systems has been studied intensively. However, the studies often ignored the underlying file systems. A locking scheme for multi-key hashed file structures is presented in this paper. First, we define a transaction model for such file structures, then we present techniques for conflict detection as well as a new locking scheme. The locking scheme combines aspects of both physical and predicate locking schemes. It places locks on buckets while guaranteeing record-level access; this results in increased concurrency with minimal overhead.

Two new file organizations based on Linear Hashing are proposed for partial match retrieval. The first organization introduces a load-balancing scheme whereby overflow records are stored temporarily in other primary buckets so that the allocation of overflow buckets are deferred. The second organization defers the physical splitting of underflow buckets, so that the records belonging to underflow buckets can be retrieved together. These two techniques are then combined together to form a new variation of Linear Hashing. Compared with the original scheme, the performance of these organizations for partial match retrieval are improved, both in terms of storage utilization and retrieval time.

A new, fully-distributed protocol for integrated voice/data traffic in a local-area, random-access broadcast network is described. The protocol introduces a movable voice-data boundary to framed TDMA/CSMA and eliminates the requirement of system-wide synchronized clocks. The movable boundary is a major advantage in any system where fluctuations in voice and data loads are expected because assignment of idle capacity from one traffic class to the other increases the utilization of the channel. The protocol provides collision-free virtual circuits for voice and periods of non-persistent CSMA/CD for data traffic and call establishment, and can support multi-party calls as well as two-way conversations. The protocol allows variable-size voice packets that have very low overhead and variable-size data packets that may be much longer than voice packets. This is of significant practical advantage over previous work, which has required fixed-size voice and/or data packets, or voice packets with high overhead. A method of dynamically controlling the movable boundary to balance the voice and data traffic is also proposed.

A hashing-based dynamic file structure is introduced for partial match retrieval using overflow bucket sharing. The sharing of overflow buckets is dynamic in the sense that an overflow bucket is shared by a varying number of primary buckets according to the local conditions of the file. The use and sharing of overflow buckets defers splitting of the data buckets, thereby increasing the storage utilization. For the same reason, plus the fact that the sharing is dynamic, the growth of the directory is slowed down. Under the proposed organization, the records are stored more compactly in the data buckets, and for those partial match queries in which few attributes are specified, groups of neighboring directory entries have high probability of being referenced together, so that the retrieval costs for these types of partial match queries are reduced. This file organization is found to be space efficient and is also time efficient for queries in which the number of specified attributes is small.

In this correspondence, we study the performance of a multiprocessor in which a crossbar is employed to interconnect p processors to m commonly shared memory modules. A set of nonuniformly distributed probabilities including a probability P(0) which denotes the probability of a processor not generating any request is also employed to illustrate the program behavior, but no distinction is made between processors. Several relations between the average request completion time, the average processor utilization, and the effective memory bandwidth are obtained. One approximation method based on the idea of aggregation is proposed. Its solutions are compared to the exact solution.

In the past two decades, the increasing usage of databases and integrated information systems has encouraged the development of file structures suited for partial match retrieval. A partial match query is a query with some number of attributes specified and the rest of them unspecified. One interesting file structure proposed and heavily studied recently is called a multikey hashing scheme, but most of the previous results on designing optimal multikey hashing schemes ignored the record distribution of a file. In this paper we show that the problem of designing an optimal multikey hashing scheme taking into consideration the record distribution is computationally intractable (NP-hard). Therefore, a heuristic approach is necessary. In a multikey hashing scheme, although the directory is space efficient and the search algorithm is fast, due to the insufficient information in the directory some accessed buckets may not contain any record satisfying the given query. Thus, certain retrieval effort is wasted. A new class of file structures which combine a multikey hashing scheme and an indexed descriptor technique is introduced in this paper. By adding some extra information (either record descriptors or bucket descriptors) into the directory of a multikey hashing scheme, either only those buckets which contain at least one record satisfying the given query need to be accessed or the number of accessed buckets which do not contain any record satisfying the query is reduced.

In this paper we consider variations on the binary search algorithm when placed in the context of a multiprocessing environment. Several organizations are investigated covering the spectrum from total independence (or free competition for access to common resources) to cooperation as in SIMD architectures. It is assumed that the two main sources of overhead are memory interference and interprocessor synchronization. An organization combining interference-free access to memory by implicit synchronization and a small degree of cooperation yields the best results.

Cartesian product files have recently been shown to exhibit attractive properties for partial match queries. This paper considers the file allocation problem for Cartesian product files, which can be stated as follows: Given a k -attribute Cartesian product file and an m -disk system, allocate buckets among the m disks in such a way that, for all possible partial match queries, the concurrency of disk accesses is maximized. The Disk Modulo (DM) allocation method is described first, and it is shown to be strict optimal under many conditions commonly occurring in practice, including all possible partial match queries when the number of disks is 2 or 3. It is also shown that although it has good performance, the DM allocation method is not strict optimal for all possible partial match queries when the number of disks is greater than 3. The General Disk Modulo (GDM) allocation method is then described, and a sufficient but not necessary condition for strict optimality of the GDM method for all partial match queries and any number of disks is then derived. Simulation studies comparing the DM and random allocation methods in terms of the average number of disk accesses, in response to various classes of partial match queries, show the former to be significantly more effective even when the number of disks is greater than 3, that is, even in cases where the DM method is not strict optimal. The results that have been derived formally and shown by simulation can be used for more effective design of optimal file systems for partial match queries. When considering multiple-disk systems with independent access paths, it is important to ensure that similar records are clustered into the same or similar buckets, while similar buckets should be dispersed uniformly among the disks.

In this paper, we first introduced the concept of Cartesian product files. We then derived a formula for random files. A computer simulation experiment was performed to compare these two files. So far as shown by the experimental results, the Cartesian product file concept was indeed a good one. We also showed that the problem of designing an optimal Cartesian product file was partially related to the problem of finding a minimal N-tuple. A method to find minimal N-tuples was presented and its properties were discussed.

In this paper, we extend the binary Gray code to symbolic Gray code. We then show that this symbolic Gray code can be used as a multikey hashing function for storing symbolic records. The record stored at location k and the record stored at location k + 1 will be nearest neighbors if this hashing function is used. Thus, this symbolic Gray code hashing function exhibits some kind of clustering property which will group similar records together. This property is a desirable property for designing nearest neighbor searching (also called best match searching) systems. There are many other interesting properties of this hashing function. For instance, there exists an address-to-key transformation which can be used to determine the record stored at certain location k if this hashing function is used. Besides, if there are totally M records, we only have to reserve exactly M locations; there are no collisions and wasting of memory storage. At the end of this paper, it is shown that the resulting file exhibits the multiple-attribute tree structure.

This paper results from an attempt to unify several different file system design theories. We define a term "partial match pattern" and show that in order to produce file systems optimal with respect to partial match patterns, both the multikey hashing (MKH) method [16] and the multidimensional directory (MDD) method [11] must be in such a form that the number of subdivisions is the same for all domains of keys. We show the conditions for the string homomorphism hashing (SHH) method [15], the MKH method, and the MDD method to be equivalent to one another. We define the so-called Cartesian product files and show that if all records are present, the records in a Cartesian product file form a shortest spanning path in which the Hamming distance between every pair of consecutive records is 1. Thus the SHH method, the MKH method, the MDD method, and the multikey sorting (MKS) method [10] are linked together. Finally, we show that for both partial and best match queries, the file systems exhibit a common characteristic: similar records are grouped together.