Recent changes in data temperatures and storage device characteristics, both mechanical disk-drives (HDDs) and solid-state drives (SSDs), expand the set of deployment options for exascale storage. Until recently, exascale storage systems followed a pattern of placing most data on HDDs with smaller amounts of SSD storage used for caching and performance-critical workloads. Exascale storage provisioning and dataset placement trade-offs have now changed.

Digital payment systems have revolutionized financial transactions, offering unparalleled convenience and accessibility to users worldwide. However, the increasing popularity of these platforms has also attracted malicious actors seeking to exploit their vulnerabilities for financial gain. To address this challenge, robust and adaptable scam detection mechanisms are crucial for maintaining the trust and safety of digital payment ecosystems. This paper presents a comprehensive approach to scam detection, focusing on the Unified Payments Interface (UPI) in India, Google Pay (GPay) as a specific use case. The approach leverages Large Language Models (LLMs) to enhance scam classification accuracy and designs a digital assistant to aid human reviewers in identifying and mitigating fraudulent activities. The results demonstrate the potential of LLMs in augmenting existing machine learning models and improving the efficiency, accuracy, quality, and consistency of scam reviews, ultimately contributing to a safer and more secure digital payment landscape. Our evaluation of the Gemini Ultra model on curated transaction data showed a 93.33% accuracy in scam classification. Furthermore, the model demonstrated 89% accuracy in generating reasoning for these classifications. A promising fact, the model identified 32% new accurate reasons for suspected scams that human reviewers had not included in the review notes.

Many data services tune and change redundancy configurations of files over their lifetimes to address changes in data temperature and latency requirements. Unfortunately, changing redundancy configs (transcode) is IO-intensive. The Morph cluster file system introduces new transcode-efficient redundancy schemes to minimize overheads as files progress through lifetime phases. For newly ingested data, commonly stored via 3-way replication, Morph introduces a hybrid redundancy scheme that combines a replica with an erasure-coded (EC) stripe, reducing both ingest IO and capacity overheads while enabling free transcode to EC by deleting replicas. For subsequent transcodes to wider, more space-efficient EC configs, Morph exploits Convertible Codes, which minimize data read for EC transcode, and introduces new block placement policies to maximize their effectiveness.

Most of the data in large-scale storage clusters is erasure coded. At exascale, optimizing erasure codes for low storage overhead, efficient reconstruction, and easy deployment is of critical importance. Locally recoverable codes (LRCs) have deservedly gained central importance in this field, because they can balance many of these requirements. In our work, we study wide LRCs; LRCs with large number of blocks per stripe and low storage overhead. These codes are a natural next step for practitioners to unlock higher storage savings, but they come with their own challenges. Of particular interest is their reliability , since wider stripes are prone to more simultaneous failures. We conduct a practically minded analysis of several popular and novel LRCs. We find that wide LRC reliability is a subtle phenomenon that is sensitive to several design choices, some of which are overlooked by theoreticians, and others by practitioners. Based on these insights, we construct novel LRCs called Uniform Cauchy LRCs , which show excellent performance in simulations and a 33% improvement in reliability on unavailability events observed by a wide LRC deployed in a Google storage cluster. We also show that these codes are easy to deploy in a manner that improves their robustness to common maintenance events. Along the way, we also give a remarkably simple and novel construction of distance-optimal LRCs (other constructions are also known), which may be of interest to theory-minded readers.

This article describes the algorithm, implementation, and deployment experience of CacheSack, the admission algorithm for Google datacenter flash caches. CacheSack minimizes the dominant costs of Google’s datacenter flash caches: disk IO and flash footprint. CacheSack partitions cache traffic into disjoint categories, analyzes the observed cache benefit of each subset, and formulates a knapsack problem to assign the optimal admission policy to each subset. Prior to this work, Google datacenter flash cache admission policies were optimized manually, with most caches using the Lazy Adaptive Replacement Cache algorithm. Production experiments showed that CacheSack significantly outperforms the prior static admission policies for a 7.7% improvement of the total cost of ownership, as well as significant improvements in disk reads (9.5% reduction) and flash wearout (17.8% reduction).

We design and implement LEGOStore, an erasure coding (EC) based linearizable data store over geo-distributed public cloud data centers (DCs). For such a data store, the confluence of the following factors opens up opportunities for EC to be latency-competitive with replication: (a) the necessity of communicating with remote DCs to tolerate entire DC failures and implement linearizability; and (b) the emergence of DCs near most large population centers. LEGOStore employs an optimization framework that, for a given object, carefully chooses among replication and EC, as well as among various DC placements to minimize overall costs. To handle workload dynamism, LEGOStore employs a novel agile reconfiguration protocol. Our evaluation using a LEGOStore prototype spanning 9 Google Cloud Platform DCs demonstrates the efficacy of our ideas. We observe cost savings ranging from moderate (5-20%) to significant (60%) over baselines representing the state of the art while meeting tail latency SLOs. Our reconfiguration protocol is able to transition key placements in 3 to 4 inter-DC RTTs (< 1s in our experiments), allowing for agile adaptation to dynamic conditions.

No abstract available.

Cloud data centers use enormous amounts of storage, and it is critical to monitor, manage, and optimize the storage autonomically configuring storage is difficult because storage workloads are very diverse and change over time. Data centers measure running workloads, but this measurement data stream is itself quite large. We present some real world case studies in the use of big data techniques, sampling, and optimization to manage storage in data centers.

Solid-state drives (SSDs) based on NAND flash are making deep inroads into data centers as well as the consumer market. In 2016, manufacturers shipped more than 130 million units totaling around 50 Exabytes of storage capacity. As the amount of data stored on solid state drives keeps increasing, it is important to understand the reliability characteristics of these devices. For a long time, our knowledge about flash reliability was derived from controlled experiments in lab environments under synthetic workloads, often using methods for accelerated testing. However, within the last two years, three large-scale field studies have been published that report on the failure behavior of flash devices in production environments subjected to real workloads and operating conditions. The goal of this paper is to provide an overview of what we have learned about flash reliability in production, and where appropriate contrasting it with prior studies performing controlled experiments.

The configuration of a distributed storage system typically includes, among other parameters, the set of servers and their roles in the replication protocol. Although mechanisms for changing the configuration at runtime exist, it is usually left to system administrators to manually determine the "best" configuration and periodically reconfigure the system, often by trial and error. This paper describes a new workload-driven optimization framework that dynamically determines the optimal configuration at run-time. We focus on optimizing leader and quorum based replication schemes and divide the framework into three optimization tiers, dynamically optimizing different configuration aspects: 1) leader placement, 2) roles of different servers in the replication protocol, and 3) replica locations. We showcase our optimization framework by applying it to a large-scale distributed storage system used internally in Google and demonstrate that most client applications significantly benefit from using our framework, reducing average operation latency by up to 94%.

Recent architectural trends---cheap, fast solid-state storage, inexpensive DRAM, and multi-core CPUs---provide an opportunity to rethink the interface between applications and persistent storage. To leverage these advances, we propose a new system architecture called Hathi that provides an in-memory transactional heap made persistent using high-speed flash drives. With Hathi, programmers can make consistent concurrent updates to in-memory data structures that survive system failures.

Supporting QoS control mechanisms in shared storage arrays is constrained by the well-justified fear of impacting the system efficiency. This motivates our study of the trade off between fairness and efficiency in shared storage systems. We propose two adaptations that can be applied to existing IO scheduling mechanisms: the concurrency bound and the batch size. Although these knobs are well known, their impact on system performance and automatic adaptation based on current workload characteristics have not been studied before. Using synthetic benchmarks and trace workloads, we show that the adaptive proportional share algorithm achieves over 90% IO efficiency while maintaining the specified QoS requirements.

Cloud computing demands cheap, always-on, and reliable storage. We describe Pahoehoe, a key-value cloud storage system we designed to store large objects cost-effectively with high availability. Pahoehoe stores objects across multiple data centers and provides eventual consistency so to be available during network partitions. Pahoehoe uses erasure codes to store objects with high reliability at low cost. Its use of erasure codes distinguishes Pahoehoe from other cloud storage systems, and presents a challenge for efficiently providing eventual consistency. We describe Pahoehoe's put, get, and convergence protocols-convergence being the decentralized protocol that ensures eventual consistency. We use simulated executions of Pahoehoe to evaluate the efficiency of convergence, in terms of message count and message bytes sent, for failure-free and expected failure scenarios (e.g., partitions and server unavailability). We describe and evaluate optimizations to the naïve convergence protocol that reduce the cost of convergence in all scenarios.

We propose a prefetch cache sizing module for use with any sequential prefetching scheme and evaluate its impact on the hit rate. Disk array caches perform sequential prefetching by loading data contiguous to I/O request data into the array cache. If the I/O workload has sequential locality, then data prefetched in response to sequential accesses in the workload will receive hits. Different schemes prefetch different data, so the prefetch cache size requirement varies. Moreover, the proportion of sequential and random requests in the workload and their interleaving pattern affects the size requirement. If the cache is too small, then prefetched data would get evicted from the cache before a request for the data arrives, thus lowering the hit rate. If the cache is too large, then valuable cache space is wasted. We present a simple sizing module that can be added to any prefetching scheme to ensure that the prefetch cache size is adequately matched to the requirement of the prefetching scheme on a dynamic workload comprising multiple streams. We analytically compute the maximal hit rate achievable by popular prefetching schemes and through simulations, show that our sizing module maintains the prefetch cache at a size that nearly achieves this maximal hit rate.

The costs of data loss and unavailability can be large, so businesses use many data protection techniques such as remote mirroring, snapshots, and backups to guard against failures. Choosing an appropriate combination of techniques is difficult because there are numerous approaches for protecting data and allocating resources. Storage system architects typically use ad hoc techniques, often resulting in overengineered expensive solutions or underprovisioned inadequate ones. In contrast, this paper presents a principled automated approach for designing dependable storage solutions for multiple applications in shared environments. Our contributions include search heuristics for intelligent exploration of the large design space and modeling techniques for capturing interactions between applications during recovery. Using realistic storage system requirements, we show that our design tool produces designs that cost up to two times less in initial outlays and expected data penalties than the designs produced by an emulated human design process. Additionally, we compare our design tool to a random search heuristic and a genetic algorithm metaheuristic, and show that our approach consistently produces better designs for the cases we have studied. Finally, we study the sensitivity of our design tool to several input parameters.

Virtualized data centers enable sharing of resources among hosted applications. However, it is difficult to satisfy service-level objectives(SLOs) of applications on shared infrastructure, as application workloads and resource consumption patterns change over time. In this paper, we present AutoControl, a resource control system that automatically adapts to dynamic workload changes to achieve application SLOs. AutoControl is a combination of an online model estimator and a novel multi-input, multi-output (MIMO) resource controller. The model estimator captures the complex relationship between application performance and resource allocations, while the MIMO controller allocates the right amount of multiple virtualized resources to achieve application SLOs. Our experimental evaluation with RUBiS and TPC-W benchmarks along with production-trace-driven workloads indicates that AutoControl can detect and mitigate CPU and disk I/O bottlenecks that occur over time and across multiple nodes by allocating each resource accordingly. We also show that AutoControl can be used to provide service differentiation according to the application priorities during resource contention.

We propose a new paradigm for building scalable distributed systems. Our approach does not require dealing with message-passing protocols, a major complication in existing distributed systems. Instead, developers just design and manipulate data structures within our service called Sinfonia. Sinfonia keeps data for applications on a set of memory nodes, each exporting a linear address space. At the core of Sinfonia is a new minitransaction primitive that enables efficient and consistent access to data, while hiding the complexities that arise from concurrency and failures. Using Sinfonia, we implemented two very different and complex applications in a few months: a cluster file system and a group communication service. Our implementations perform well and scale to hundreds of machines.

Enterprise storage systems typically contain multiple storage tiers, each having its own performance, reliability, and recoverability. The primary motivation for this multi-tier organization is cost, as storage tier costs vary considerably. In this paper, we describe a file system called TierFS that stores files at multiple storage tiers while providing high recoverability at all tiers. To achieve this goal, TierFS uses several novel techniques that leverage coupling between multiple tiers to reduce data loss, take consistent snapshots across tiers, provide continuous data protection, and improve recovery time. We evaluate TierFS with analytical models, showing that TierFS can provide better recoverability than a conventional design of similar cost.

Data centers are often under-utilized due to over-provisioning as well as time-varying resource demands of typical enterprise applications. One approach to increase resource utilization is to consolidate applications in a shared infrastructure using virtualization. Meeting application-level quality of service (QoS) goals becomes a challenge in a consolidated environment as application resource needs differ. Furthermore, for multi-tier applications, the amount of resources needed to achieve their QoS goals might be different at each tier and may also depend on availability of resources in other tiers. In this paper, we develop an adaptive resource control system that dynamically adjusts the resource shares to individual tiers in order to meet application-level QoS goals while achieving high resource utilization in the data center. Our control system is developed using classical control theory, and we used a black-box system modeling approach to overcome the absence of first principle models for complex enterprise applications and systems. To evaluate our controllers, we built a testbed simulating a virtual data center using Xen virtual machines. We experimented with two multi-tier applications in this virtual data center: a two-tier implementation of RUBiS, an online auction site, and a two-tier Java implementation of TPC-W. Our results indicate that the proposed control system is able to maintain high resource utilization and meets QoS goals in spite of varying resource demands from the applications.

We examine the problem of providing fair bandwidth allocation in distributed storage systems similar to the research prototypes HP FAB and IBM Intelligent Bricks. The problem poses significant new challenges beyond those encountered in network and storage QoS scheduling. Specifically, resources are heterogeneous i.e. an IO request can only be serviced by a particular server, and service is both requested and provided in a distributed manner with no centralized controller. We provide a distributed algorithm, d-Clock, that runs locally on each of the servers and provides global fairness guarantees without causing resource-specific starvation, with minimal synchronization overhead.

Storage consolidation is becoming an attractive paradigm for data organization because of the economies of sharing and the ease of centralized management. However, sharing of resources is viable only if applications can be isolated from each other. This work targets the problem of providing performance guarantees to an application irrespective of the behavior of other workloads. Application requirements are represented in terms of the average throughput, latency and maximum burst size. Most earlier schemes only do weighted bandwidth allocation; schemes that provide control of latency either cannot handle bursts or penalize applications for their own prior behavior, such as using spare capacity.

We propose a new paradigm for building scalable distributed systems. Our approach does not require dealing with message-passing protocols -- a major complication in existing distributed systems. Instead, developers just design and manipulate data structures within our service called Sinfonia. Sinfonia keeps data for applications on a set of memory nodes, each exporting a linear address space. At the core of Sinfonia is a novel minitransaction primitive that enables efficient and consistent access to data, while hiding the complexities that arise from concurrency and failures. Using Sinfonia, we implemented two very different and complex applications in a few months: a cluster file system and a group communication service. Our implementations perform well and scale to hundreds of machines.

In this paper we extend the state-of-the-art in utilizing background knowledge for supervised classification by exploiting the semantic relationships between terms explicated in Ontologies. Preliminary evaluations indicate that the new approach generally improves precision and recall, more so for hard to classify cases and reveals patterns indicating the usefulness of such background knowledge.

The costs of data loss and unavailability can be large, so businesses use many data protection techniques, such as remote mirroring, snapshots and backups, to guard against failures. Choosing an appropriate combination of techniques is difficult because there are numerous approaches for protecting data and allocating resources. Storage system designers typically use ad hoc techniques, often resulting in over-engineered, expensive solutions or under-provisioned, inadequate ones. In contrast, this paper presents a principled, automated approach for designing dependable storage solutions for multiple applications in shared environments. Our contributions include search heuristics for intelligently exploring the large design space and modeling techniques for capturing interactions between applications during recovery. Using realistic storage system requirements, we show that our design tool can produce designs that cost up to 3X less in initial outlays and expected data penalties than the designs produced by an emulated human design process

Restoring data operations after a disaster is a daunting task: how should recovery be performed to minimize data loss and application downtime? Administrators are under considerable pressure to recover quickly, so they lack time to make good scheduling decisions. They schedule recovery based on rules of thumb, or on pre-determined orders that might not be best for the failure occurrence. With multiple workloads and recovery techniques, the number of possibilities is large, so the decision process is not trivial.This paper makes several contributions to the area of data recovery scheduling. First, we formalize the description of potential recovery processes by defining recovery graphs. Recovery graphs explicitly capture alternative approaches for recovering workloads, including their recovery tasks, operational states, timing information and precedence relationships. Second, we formulate the data recovery scheduling problem as an optimization problem, where the goal is to find the schedule that minimizes the financial penalties due to downtime, data loss and vulnerability to subsequent failures. Third, we present several methods for finding optimal or near-optimal solutions, including priority-based, randomized and genetic algorithm-guided ad hoc heuristics. We quantitatively evaluate these methods using realistic storage system designs and workloads, and compare the quality of the algorithms' solutions to optimal solutions provided by a math programming formulation and to the solutions from a simple heuristic that emulates the choices made by human administrators. We find that our heuristics' solutions improve on the administrator heuristic's solutions, often approaching or achieving optimality.

This paper describes the design, implementation, and evaluation of a Federated Array of Bricks (FAB), a distributed disk array that provides the reliability of traditional enterprise arrays with lower cost and better scalability. FAB is built from a collection of bricks, small storage appliances containing commodity disks, CPU, NVRAM, and network interface cards. FAB deploys a new majority-voting-based algorithm to replicate or erasure-code logical blocks across bricks and a reconfiguration algorithm to move data in the background when bricks are added or decommissioned. We argue that voting is practical and necessary for reliable, high-throughput storage systems such as FAB. We have implemented a FAB prototype on a 22-node Linux cluster. This prototype sustains 85MB/second of throughput for a database workload, and 270MB/second for a bulk-read workload. In addition, it can outperform traditional master-slave replication through performance decoupling and can handle brick failures and recoveries smoothly without disturbing client requests.

A federated array of bricks is a scalable distributed storage system composed from inexpensive storage bricks. It achieves high reliability with low cost by using erasure coding across the bricks to maintain data reliability in the face of brick failures. Erasure coding generates n encoded blocks from m data blocks (n > m) and permits the data blocks to be reconstructed from any m of these encoded blocks. We present a new fully decentralized erasure-coding algorithm for an asynchronous distributed system. Our algorithm provides fully linearizable read-write access to erasure-coded data and supports concurrent I/O controllers that may crash and recover. Our algorithm relies on a novel quorum construction where any two quorums intersect in m processes.

Designing storage systems to provide business continuity in the face of failures requires the use of various data protection techniques, such as backup, remote mirroring, point-in-time copies and vaulting, often in concert. Predicting the dependability provided by such compositions of techniques is difficult, yet necessary for dependable system design. We present a framework for evaluating the dependability of data storage systems, including both individual data protection techniques and their compositions. Our models estimate storage system recovery time, data loss, normal mode system utilization and operational costs under a variety of failure scenarios. We demonstrate the effectiveness of these modeling techniques through a case study using real-world storage system designs and workloads.

The performance modeling and analysis of disk arrays is challenging due to the presence of multiple disks, large array caches, and sophisticated array controllers. Moreover, storage manufacturers may not reveal the internal algorithms implemented in their devices, so real disk arrays are effectively black-boxes. We use standard performance techniques to develop an integrated performance model that incorporates some of the complexities of real disk arrays. We show how measurement data and baseline performance models can be used to extract information about the various features implemented in a disk array. In this process, we identify areas for future research in the performance analysis of real disk arrays.

Enterprise-scale storage systems, which can contain hundreds of host computers and storage devices and up to tens of thousands of disks and logical volumes, are difficult to design. The volume of choices that need to be made is massive, and many choices have unforeseen interactions. Storage system design is tedious and complicated to do by hand, usually leading to solutions that are grossly over-provisioned, substantially under-performing or, in the worst case, both.To solve the configuration nightmare, we present minerva: a suite of tools for designing storage systems automatically. Minerva uses declarative specifications of application requirements and device capabilities; constraint-based formulations of the various sub-problems; and optimization techniques to explore the search space of possible solutions.This paper also explores and evaluates the design decisions that went into Minerva, using specialized micro- and macro-benchmarks. We show that Minerva can successfully handle a workload with substantial complexity (a decision-support database benchmark). Minerva created a 16-disk design in only a few minutes that achieved the same performance as a 30-disk system manually designed by human experts. Of equal importance, Minerva was able to predict the resulting system's performance before it was built.

Modern disk drives read-ahead data and reorder incoming requests in a workload-dependent fashion. This improves their performance, but makes simple analytical models of them inadequate for performance prediction, capacity planning, workload balancing, and so on. To address this problem we have developed a new analytic model for disk drives that do readahead and request reordering. We did so by developing performance models of the disk drive components (queues, caches, and the disk mechanism) and a workload transformation technique for composing them. Our model includes the effects of workload-specific parameters such as request size and spatial locality. The result is capable of predicting the behavior of a variety of real-world devices to within 17% across a variety of workloads and disk drives.

One limitation on the operating speed of electronic circuits is the rate at which the packaging can dissipate heat. In CMOS technology, the heat generated by a processor is approximately proportional to its clock rate. The paper examines the idea of using a variable speed processor (VSP) that can be operated at a high clock speed, and then slowed down to a lower speed before heat accumulation destroys the circuit. Under a workload consisting of bursts of work alternating with idle periods (corresponding to cache misses or other delays), this results in a higher average operating speed. The paper shows the optimality of a bang bang control for the clock rate. It also examines an easier to implement policy that estimates the junction temperature through an upper bound, and uses this to control the clock rate. Closed form expressions are derived for the mean rate of instructions executed by a VSP using each control method. Numerical studies show that both policies give substantial improvements in performance over a single speed processor. Furthermore, the studies suggest that a VSP with a maximum clock rate of 2-4 times that of the single speed processor would suffice to obtain the bulk of the performance improvement. In many cases, the average throughput gain is on the order of 40-60%, without exceeding thermal limits.

A Redundant Array of Independent Disks (RAID) of G disks provides protection against single disk failures by adding one parity block for each G-1 data blocks. In a clustered RAID, the G data/parity blocks are distributed over a cluster of C disks (C>G), thus reducing the additional load on each disk due to a single disk failure. However, most methods proposed for implementing such a mapping do not work for general C and G values. In this paper, we describe a fast mapping algorithm based on almost-random permutations. An analytical model is constructed, based on the queue with a permanent customer, to predict recovery time and read/write performance. The accuracy of the results derived from this model is validated by comparing with simulations. Our analysis shows that clustered RAID is significantly more tolerant of disk failure than the basic RAID scheme. Both recovery time and performance degradation during recovery are substantially reduced in clustered RAID; moreover, these gains can be achieved using fairly small C/G ratios.

Dynamic finite versioning (DFV) schemes are an effective approach to concurrent transaction and query processing, where a finite number of consistent, but maybe slightly out-of-date, logical snapshots of the database can be dynamically derived for query access. In DFV, the storage overhead for keeping additional versions of changed data to support the logical snapshots and the amount of obsolescence faced by queries are two major performance issues. We analyze the performance of DFV, with emphasis on the trade-offs between the storage cost and obsolescence. We develop analytical models based on a renewal process approximation to evaluate the performance of DFV using M/spl ges/2 snapshots. Asymptotic closed form results for high query arrival rates are given for the case of two snapshots. Simulation is used to validate the analytical models and to evaluate the tradeoffs between various strategies for advancing snapshots when M>2. The results show that (1) the analytical models match closely with simulation; (2) storage cost and obsolescence are sensitive to the snapshot advancing strategies, and (3) usually, increasing the number of snapshots demonstrates a trade-off between storage overhead and query obsolescence. For cases with skewed accessor low update rates, a small increase in the number of snapshots beyond two can substantially reduce the obsolescence. Such a reduction in obsolescence is more significant as the coefficient of variation of the query length distribution becomes larger. Moreover, for very low update rates, a large number of snapshots can be used to reduce the obsolescence to almost zero without increasing the storage overhead.

Data replication has been widely used as a means of increasing the data availability for critical applications in the event of disk failure. There are different ways of organizing the two copies of the data across a disk array. This paper compares strategies for striping data of the two copies in the context of database applications. By keeping both copies active, we explore strategies that can take advantage of the additional copy to improve not only availability, but also performance during both normal and failure modes. We consider the effects of small and large stripe sizes on the performance of disk arrays with two active copies of data under a mixed workload of queries and transactions with a skewed access pattern. We propose a dual (hybrid) striping strategy which uses different stripe sizes for the two copies and a disk queuing policy designed to exploit this organization for optimal performance. An analytical model is devised for this scheme, by treating the individual disks as independent, and applying an M/G/1 queuing model. Disks on which a large query scan is running are modeled by a variation of the queue with permanent customers, which leads to an iterative functional equation for the query scan delay distribution. A solution for this equation is given. The results are validated against simulations. And are shown to match well. Comparison with uniform striping strategies show that the dual striping scheme yields the most stable performance in a variety of workloads, out-performing the uniform striping strategy using either mirrored or chained dc-clustering under both normal and failure mode operations.>

Considers a problem of network design of personal communication services (PCS). The problem is to assign cells to the switches of a PCS network in an optimum manner. The authors consider two types of costs. One is the cost of handoffs between cells. The other is the cost of cabling (or trunking) between a cell site and its associated switch. The problem is constrained by the call volume that each switch can handle. The authors formulate the problem exactly as an integer programming problem. They also propose a heuristic solution for this problem and show that it performs extremely well.>

Considers a problem of network design of personal communication services (PCS). The problem is to assign cells to the switches of a PCS network in an optimum manner. The authors consider two types of costs. One is the cost of handoffs between cells. The other is the cost of cabling (or trunking) between a cell site and its associated switch. The problem is constrained by the call volume that each switch can handle. They formulate the problem exactly as an integer programming problem. They also propose three heuristic solutions for this problem and show that two of them perform extremely well.>

We present in this paper an analytical model of a multistage combining Banyan network with output buffered switches, in hot-sport traffic. In a combining network, packets bound for the same destination are combined into one if they meet at a switch; this alleviates the problem of tree-saturation caused by hot-spot traffic. We model the flow processes in the network as Markov chains and recursively approximate the departure processes of each stage of the network in terms of the departure processes of the preceding stage. This model is used to predict the throughput of the combining network, and comparison with simulation results shows the prediction to be accurate.A modified combining scheme based on low priorites for hot packets is proposed and analyzed. It is shown that this scheme yields substantial improvements in throughput over the standard combining scheme.

In this paper, we analyze the performance of dynamic finite versioning (DFV) schemes for concurrent transaction and query processing, where a finite number of consistent snapshots can be derived for query access. We develop analytical models based on a renewal process approximation to evaluate the performance of DFV using M ≥ 2 snapshots. The storage overhead and obsolescence faced by queries are measured. Simulation is used to validate the analytical models and to evaluate the trade-offs between various starategies for advancing snapshots when M > 2.

This paper analyzes the delay suffered by messages in a clocked, packet-switched, square Banyan network with k x k output-buffered switches by approximating the flow processes in the network with Markov chains. We recursively approximate the departure process of buffers of the nth stage in terms of thqt at the n -- lst stage. We show how to construct the transition matrix for the Markov chain at each stage of the network and how to solve for the stationary distribution of the delay in the queues of that stage. The analytical results are compared with simulation results for several cases. Finally, we give a method based on this approximation and the technique of coupling to compute upper bounds on the time for the system to approach steady state.