Magnetic tape provides a cost-effective way to retain the exponentially increasing volumes of data being created in recent years. The low cost per terabyte combined with tape’s low energy consumption make it an appealing option for storing infrequently accessed data and has resulted in a resurgence in use of the technology. Magnetic tape as a digital data storage technology was first commercialized in the early 1950’s and has evolved continuously since then. Despite its long history, tape has significant potential for continued capacity and data rate scaling. This article strives to provide an overview of linear magnetic tape technology, usage, history, and future outlook. After a short introduction, the article delves into the details of how modern tape drives and media operate, including the basic mechanism and physics of magnetic recording, current tape media technology, state-of-the-art tape head technology, tape layout and encoding, data retrieval, timing-based servo and mechatronics of a tape drive, and the capabilities of current drives. This is followed by a discussion of tape libraries, an overview of tape library performance modeling research, operating system-level and application-level tape support, tape use cases, and the future scaling potential and outlook of tape. The article concludes with a history of tape hardware, media, usage and software.

Magnetic tape is a digital data storage technology that has evolved continuously over the last seven decades. It provides a cost-effective way to retain the rapidly increasing volumes of data being created in recent years. The low cost per terabyte combined with tape’s low energy consumption make it an appealing option for storing infrequently accessed data and has resulted in a resurgence in use of the technology. Power and operational failures may damage tapes and lead to data loss. To protect stored data against loss and achieve high data reliability, an erasure coding scheme is employed. A theoretical model capturing the effect of tape failures and latent errors on system reliability is developed. Closed-form expressions are derived for the the Mean Time to Data Loss (MTTDL) and the Expected Annual Fraction of Effective Data Loss (EAFEDL) reliability metric, which assesses losses at the file, object, or block, level. The results obtained demonstrate that, for realistic values of bit error rates, reliability is unaffected by the presence of latent errors. The theoretical results derived can be used to dimension and provision tape libraries to provide desired levels of durability.

Large-scale storage systems employ erasure-coding redundancy schemes to protect against device failures. The adverse effect of latent sector errors on the Mean Time to Data Loss (MTTDL) and the Expected Annual Fraction of Data Loss (EAFDL) reliability metrics is evaluated. A theoretical model capturing the effect of latent errors and device failures is developed, and closed-form expressions for the metrics of interest are derived. The MTTDL and EAFDL of erasure-coded systems are obtained analytically for (i) the entire range of bit error rates; (ii) the symmetric, clustered, and declustered data placement schemes; and (iii) arbitrary device failure and rebuild time distributions under network rebuild bandwidth constraints. The range of error rates that deteriorate system reliability is derived analytically. For realistic values of sector error rates, the results obtained demonstrate that MTTDL degrades, whereas, for moderate erasure codes, EAFDL remains practically unaffected. It is demonstrated that, in the range of typical sector error rates and for very powerful erasure codes, EAFDL degrades as well. It is also shown that the declustered data placement scheme offers superior reliability.

Magnetic tape provides a cost-effective way to retain the exponentially increasing volumes of data. The low cost per gigabyte and the low energy consumption render tape a preferred option over hard disk drives and flash for infrequently accessed data. Assessing the performance of tape library systems is central to achieving appropriate storage provisioning and dimensioning. Performance is affected by the number and the operational characteristics of the tape drives and the robotic arms, and the mount and unmount policies deployed. In this paper, we develop a novel analytical model that accurately captures the principal aspects of tape library operation. Several relevant performance measures including the mean waiting time and the mount/unmount rates are derived. The model provides useful insights into the behavior of the tape library mechanisms and yields results, which enable a better understanding of the design tradeoffs. The validity of the model developed is confirmed by demonstrating a good agreement of the predicted performance with that obtained by simulation across various configurations.

Many important big data use cases do not require data to be instantly available. Examples are video recordings in TV and film industry, surveillance videos and data from scientific experiments. Archiving such data to high-latency media storage, such as tape and optical disk libraries, results in significant cost savings. In this context, data is accessed by first staging it to low-latency media. However, archiving and staging operations incur additional device and bandwidth costs for both the active and archiving tiers, and might impact user data access performance. For instance, in terms of cost and performance, it is often suboptimal to archive all the data. This paper presents ExaPlan Archive, a scheme to determine the data placement and number of devices required in each tier of a multitiered storage system comprised of archival and active tiers that minimize the latency of the active tiers under budget and staging-time constraints. The efficiency of the proposed optimized archiving scheme is compared with an existing scheme that optimizes multitier storage with only direct-access tiers. The two schemes are evaluated using a staging workload of LOFAR radio telescopes long-term archive for astronomical observation data.

Multi-tiered storage, where each tier consists of one type of storage device (e.g., SSD, HDD, or disk arrays), is a commonly used approach to achieve both high performance and cost efficiency in large-scale systems that need to store data with vastly different access characteristics. By aligning the access characteristics of the data, either fixed-sized extents or variable-sized files, to the characteristics of the storage devices, a higher performance can be achieved for any given cost. This article presents ExaPlan, a method to determine both the data-to-tier assignment and the number of devices in each tier that minimize the system’s mean response time for a given budget and workload. In contrast to other methods that constrain or minimize the system load, ExaPlan directly minimizes the system’s mean response time estimated by a queueing model. Minimizing the mean response time is typically intractable as the resulting optimization problem is both nonconvex and combinatorial in nature. ExaPlan circumvents this intractability by introducing a parameterized data placement approach that makes it a highly scalable method that can be easily applied to exascale systems. Through experiments that use parameters from real-world storage systems, such as CERN and LOFAR, it is demonstrated that ExaPlan provides solutions that yield lower mean response times than previous works. It supports standalone SSDs and HDDs as well as disk arrays as storage tiers, and although it uses a static workload representation, we provide empirical evidence that underlying dynamic workloads have invariant properties that can be deemed static for the purpose of provisioning a storage system. ExaPlan is also effective as a load-balancing tool used for placing data across devices within a tier, resulting in an up to 3.6-fold reduction of response time compared with a traditional load-balancing algorithm, such as the Longest Processing Time heuristic.

Data with vastly different access characteristics is efficiently stored in multi-tiered storage systems. A cost-effective way to retain large volumes of infrequently accessed data is to store it on tape. Steady developments in tape technology deliver ever increasing storage capacities at low cost. This has established tape as a viable solution to cope with the extreme data growth in the context of Big Data. Assessing the performance of the various tiers is central to achieving appropriate tier dimensioning and storage provisioning. To that end, we develop an analytical model to evaluate the performance of a tape library system that considers various relevant aspects, such as the number of cartridges and tape drives as well as different mount/unmount policies. Closed-form expressions for the corresponding mean waiting times are derived. The validity of the model developed is confirmed by demonstrating that the predicted performance matches well with that obtained by simulation across a wide range of system parameter values.

Multi-tiered storage, where each tier comprises one type of storage device, e.g., SSD, HDD, is a commonly used approach to achieve both high performance and cost efficiency in large-scale systems that need to store data with vastly different access characteristics. By aligning the access characteristics of the data to the characteristics of the storage devices, higher performance can be achieved for any given cost. This article presents ExaPlan, a method to determine both the data-to-tier assignment and the number of devices in each tier that minimize the system's mean response time for a given budget and workload. In contrast to other methods that constrain or minimize the system load, ExaPlan directly minimizes the system's mean response time estimated by a queueing model. Minimizing the mean response time is typically intractable as the resulting optimization problem is both non-convex and combinatorial in nature. ExaPlan circumvents this intractability by introducing a parameterized data-placement approach that makes it a highly scalable method that can be easily applied to exascale systems. Through experiments that use parameters from real-world storage systems, such as CERN and LOFAR, it is demonstrated that ExaPlan provides solutions that yield lower mean response times than previous works. It is also capable of determining a data-to-tier assignment both at the level of files and at the level of fixed-size extents. For some of the workloads evaluated, file-level placement exhibited a significant performance improvement over extent-level placement.

A recent article on the reliability of RAID-6 storage systems overlooks certain relevant prior work published in the past 20 years and concludes that the widely used mean time to data loss (MTTDL) metric does not provide accurate results. In this note, we refute this position by invoking uncited relevant prior work and demonstrating that the MTTDL remains a useful metric.

Several redundancy and recovery schemes have been developed to enhance the reliability of storage systems. The effectiveness of these schemes has predominately been evaluated based on the mean time to data loss (MTTDL) metric, which has been proven useful for assessing tradeoffs, for comparing schemes, and for estimating the effect of the various parameters on system reliability. In the context of distributed and cloud storage systems, for economical reasons, it is of great importance to also consider the magnitude along with the frequency of data loss. We focus on the following reliability metric: the expected annual fraction of data loss (EAFDL), that is, the fraction of stored data that is expected to be lost by the system annually. We present a general methodology to obtain the EAFDL metric analytically, in conjunction with the MTTDL metric, for various redundancy schemes and for a large class of failure time distributions that also includes real-world distributions like Weibull and gamma. As a demonstration, we subsequently apply this methodology to derive these metrics analytically and to assess the reliability of a replication-based storage system under clustered, declustered, and symmetric data placement schemes. We show that the declustered placement scheme offers superior reliability in terms of both metrics. Previous work has used simulation to evaluate the magnitude of data loss, but this is the first work to analytically assess it, and the first to present a general theoretical framework for this context.

Network bandwidth between sites is typically more scarce than bandwidth within a site in geo-replicated cloud storage systems, and can potentially be a bottleneck for recovery operations. We study the reliability of geo-replicated cloud storage systems taking into account different bandwidths within a site and between sites. We consider a new recovery scheme called staged rebuild and compare it with both a direct scheme and a scheme known as intelligent rebuild. To assess the reliability gains achieved by these schemes, we develop an analytical model that incorporates various relevant aspects of storage systems, such as bandwidths, latent sector errors, and failure distributions. The model applies in the context of Open Stack Swift, a widely deployed cloud storage system. Under certain practical system configurations, we establish that order of magnitude improvements in mean time to data loss (MTTDL) can be achieved using these schemes.

The reliability of data storage systems is adversely affected by the presence of latent sector errors. As the number of occurrences of such errors increases with the storage capacity, latent sector errors have become more prevalent in today's high capacity storage devices. Such errors are typically not detected until an attempt is made to read the affected sectors. When a latent sector error is detected, the redundant data corresponding to the affected sector is used to recover its data. However, if no such redundant data is available, then the data of the affected sector is irrecoverably lost from the storage system. Therefore, the reliability of data storage systems is affected by both the complete failure of storage nodes and the latent sector errors within them. In this article, closed-form expressions for the mean time to data loss (MTTDL) of erasure coded storage systems in the presence of latent errors are derived. The effect of latent errors on systems with various types of redundancy, data placement, and sector error probabilities is studied. For small latent sector error probabilities, it is shown that the MTTDL is reduced by a factor that is independent of the number of parities in the data redundancy scheme as well as the number of nodes in the system. However, for large latent sector error probabilities, the MTTDL is similar to that of a system using a data redundancy scheme with one parity less. The reduction of the MTTDL in the latter case is more pronounced than in the former one.

In this paper, we study the performance of solid-state drives that employ flash technology as storage medium. Our prime objective is to understand how the scheduling of the user-generated read and write commands and the read, write, and erase operations induced by the garbage-collection process affect the basic performance measures throughput and latency. We demonstrate that the most straightforward scheduling that prioritizes the processing of garbage-collection-related commands over user-related commands suffers from severe latency deficiencies. These problems can be overcome by using a more sophisticated priority scheme that minimizes the user-perceived latency without throughput penalty or deadlock exposure. Using both analysis and simulation, we investigate how these schemes perform under a variety of system design parameters and workloads. Our results can be directly applied to the engineering of a performance-optimized solid-state-drive system.

To improve the reliability of data storage systems, certain data placement schemes spread replicas corresponding to data stored on each node across several other nodes. When node failures occur, this enables parallelizing the rebuild process which in turn results in reducing the rebuild times. However, the underlying assumption is that the parallel rebuild process is facilitated by sufficient availability of network bandwidth to transfer data across nodes at full speed. In a large-scale data storage system where the network bandwidth for rebuild is constrained, such placement schemes will not be as effective. In this paper, it is shown through analysis and simulation how the spread of replicas across nodes affects system reliability under a network bandwidth constraint. Efficient placement schemes that can achieve high reliability in the presence of bandwidth constraints are proposed. Furthermore, in a dynamically changing storage system, in which the number of nodes and the network rebuild bandwidth can change over time, the data placement can be accordingly adapted to maintain a high level of reliability.

The placement of replicas across storage nodes in a replication-based storage system is known to affect rebuild times and therefore system reliability. Earlier work has shown that, for a replication factor of two, the reliability is essentially unaffected by the replica placement scheme because all placement schemes have mean times to data loss (MTTDLs) within a factor of two for practical values of the failure rate, storage capacity, and rebuild bandwidth of a storage node. However, for higher replication factors, simulation results reveal that this no longer holds. Moreover, an analytical derivation of MTTDL becomes intractable for general placement schemes. In this paper, we develop a theoretical model that is applicable for any replication factor and provides a good approximation of the MTTDL for small failure rates. This model characterizes the system behavior by using an analytically tractable measure of reliability: the probability of the shortest path to data loss following the first node failure. It is shown that, for highly reliable systems, this measure approximates well the probability of all paths to data loss after the first node failure and prior to the completion of rebuild, and leads to a rough estimation of the MTTDL. The results obtained are of theoretical and practical importance and are confirmed by means of simulations. As our results show, the declustered placement scheme, contrary to intuition, offers a reliability for replication factors greater than two that does not decrease as the number of nodes in the system increases.

Two schemes proposed to cope with unrecoverable or latent media errors and enhance the reliability of RAID systems are examined. The first scheme is the established, widely used, disk scrubbing scheme, which operates by periodically accessing disk drives to detect media-related unrecoverable errors. These errors are subsequently corrected by rebuilding the sectors affected. The second scheme is the recently proposed intradisk redundancy scheme, which uses a further level of redundancy inside each disk, in addition to the RAID redundancy across multiple disks. A new model is developed to evaluate the extent to which disk scrubbing reduces the unrecoverable sector errors. The probability of encountering unrecoverable sector errors is derived analytically under very general conditions regarding the characteristics of the read/write process of uniformly distributed random workloads and for a broad spectrum of disk scrubbing schemes, which includes the deterministic and random scrubbing schemes. We show that the deterministic scrubbing scheme is the most efficient one. We also derive closed-form expressions for the percentage of unrecoverable sector errors that the scrubbing scheme detects and corrects, the throughput performance, and the minimum scrubbing period achievable under operation with random, uniformly distributed I/O requests. Our results demonstrate that the reliability improvement due to disk scrubbing depends on the scrubbing frequency and the load of the system, and, for heavy-write workloads, may not reach the reliability level achieved by a simple interleaved parity-check (IPC)-based intradisk redundancy scheme, which is insensitive to the load. In fact, for small unrecoverable sector error probabilities, the IPC-based intradisk redundancy scheme achieves essentially the same reliability as that of a system operating without unrecoverable sector errors. For heavy loads, the reliability achieved by the scrubbing scheme can be orders of magnitude less than that of the intradisk redundancy scheme. Finally, the I/O and throughput performances are evaluated by means of analysis and event-driven simulation.

Replication is a widely used method to protect large-scale data storage systems from data loss when storage nodes fail. It is well known that the placement of replicas of the different data blocks across the nodes affects the time to rebuild. Several systems described in the literature are designed based on the premise that minimizing the rebuild times maximizes the system reliability. Our results however indicate that the reliability is essentially unaffected by the replica placement scheme. We show that, for a replication factor of two, all possible placement schemes have mean times to data loss (MTTDLs) within a factor of two for practical values of the failure rate, storage capacity, and rebuild bandwidth of a storage node. The theoretical results are confirmed by means of event-driven simulation. For higher replication factors, an analytical derivation of MTTDL becomes intractable for a general placement scheme. We therefore use one of the alternate measures of reliability that have been proposed in the literature, namely, the probability of data loss during rebuild in the critical mode of the system. Whereas for a replication factor of two this measure can be directly translated into MTTDL, it is only speculative of the MTTDL behavior for higher replication factors. This measure of reliability is shown to lie within a factor of two for all possible placement schemes and any replication factor. We also show that for any replication factor, the clustered placement scheme has the lowest probability of data loss during rebuild in critical mode among all possible placement schemes, whereas the declustered placement scheme has the highest probability. Simulation results reveal however that these properties do not hold for the corresponding MTTDLs for a replication factor greater than two. This indicates that some alternate measures of reliability may not be appropriate for comparing the MTTDL of different placement schemes.

The reliability of disk storage systems is adversely affected by the presence of latent sector errors. Disk scrubbing and intradisk redundancy are two schemes proposed to cope with unrecoverable or latent media errors and enhance the reliability of RAID storage systems. Two recent studies have investigated the effectiveness of these schemes, but they have reached opposing conclusions. These studies were conducted using two different modeling approaches. We present a detailed investigation which reveals that this discrepancy originates from the difference in the approach adopted, and the level of detail incorporated by the two models. We show that, as a consequence, these models provide reliability results which may differ by orders of magnitude therefore leading to contradicting conclusions. We develop a common analytical framework within which we investigate the details, merits, weaknesses, and applicability of each model. We resolve this discrepancy by deriving enhanced models that incorporate inherent characteristics of the latent-error process and provide realistic reliability results that are in good agreement. We subsequently reassess the reliability results and conclusions presented in previous studies regarding the disk scrubbing and the intradisk redundancy scheme.

Write amplification is a critical factor limiting the random write performance and write endurance in storage devices based on NAND-flash memories such as solid-state drives (SSD). The impact of garbage collection on write amplification is influenced by the level of over-provisioning and the choice of reclaiming policy. In this paper, we present a novel probabilistic model of write amplification for log-structured flash-based SSDs. Specifically, we quantify the impact of over-provisioning on write amplification analytically and by simulation assuming workloads of uniformly-distributed random short writes. Moreover, we propose modified versions of the greedy garbage-collection reclaiming policy and compare their performance. Finally, we analytically evaluate the benefits of separating static and dynamic data in reducing write amplification, and how to address endurance with proper wear leveling.

Two schemes proposed to cope with unrecoverable or latent media errors and enhance the reliability of RAID systems are examined. The first scheme is the established, widely used disk scrubbing scheme, which operates by periodically accessing disk drives to detect media-related unrecoverable errors. These errors are subsequently corrected by rebuilding the sectors affected. The second scheme is the recently proposed intradisk redundancy scheme which uses a further level of redundancy inside each disk, in addition to the RAID redundancy across multiple disks. Analytic results are obtained assuming Poisson arrivals of random I/O requests. Our results demonstrate that the reliability improvement due to disk scrubbing depends on the scrubbing frequency and the workload of the system, and may not reach the reliability level achieved by a simple IPC-based intra-disk redundancy scheme, which is insensitive to the workload. In fact, the IPC-based intra-disk redundancy scheme achieves essentially the same reliability as that of a system operating without unrecoverable sector errors. For heavy workloads, the reliability achieved by the scrubbing scheme can be orders of magnitude less than that of the intra-disk redundancy scheme.

Today's data storage systems are increasingly adopting low-cost disk drives that have higher capacity but lower reliability, leading to more frequent rebuilds and to a higher risk of unrecoverable media errors. We propose an efficient intradisk redundancy scheme to enhance the reliability of RAID systems. This scheme introduces an additional level of redundancy inside each disk, on top of the RAID redundancy across multiple disks. The RAID parity provides protection against disk failures, whereas the proposed scheme aims to protect against media-related unrecoverable errors. In particular, we consider an intradisk redundancy architecture that is based on an interleaved parity-check coding scheme, which incurs only negligible I/O performance degradation. A comparison between this coding scheme and schemes based on traditional Reed--Solomon codes and single-parity-check codes is conducted by analytical means. A new model is developed to capture the effect of correlated unrecoverable sector errors. The probability of an unrecoverable failure associated with these schemes is derived for the new correlated model, as well as for the simpler independent error model. We also derive closed-form expressions for the mean time to data loss of RAID-5 and RAID-6 systems in the presence of unrecoverable errors and disk failures. We then combine these results to characterize the reliability of RAID systems that incorporate the intradisk redundancy scheme. Our results show that in the practical case of correlated errors, the interleaved parity-check scheme provides the same reliability as the optimum, albeit more complex, Reed--Solomon coding scheme. Finally, the I/O and throughput performances are evaluated by means of analysis and event-driven simulation.

The data vortex photonic packet-switching architecture features an all-optical transparent data path, highly distributed control, low latency, and a high degree of scalability. These characteristics make it attractive as a routing fabric in future photonic packet switches. We analyze the performance of the data vortex architecture as a function of its height and angle dimensions, H and A. The investigation is based on two performance measures: the average delay and the maximum throughput of the switch. We present an analytical model assuming uniform traffic and derive closed-form expressions for these measures. Our results obtained demonstrate that as H increases, the saturation throughput decreases and approaches2/9= 0.22 when A is small and H is large. Furthermore, for fixed switch size, the saturation throughput is maximized when A is minimal. We also present simulation results for the maximum throughput under uniform and nonuniform traffic, as well as for the mean number of hops and the mean input-queue packet delay as a function of input load, and address the issue of resequencing delay. The results obtained advocate that to support more ports, it is preferable to increase the height dimension and to keep the angle dimension as small as possible.

This paper considers a general parallel buffered packet switch (PBPS) architecture which is based on multiple packet switches operating independently and in parallel. A load-balancing mechanism is used at each input to distribute the traffic to the parallel switches. The buffer structure of each of the parallel packet switches is based on either a dedicated, a shared, or a buffered-crosspoint output-queued architecture. As in such PBPS multipath switches, packets may get out of order when they travel independently in parallel through these switches, a resequencing mechanism is necessary at the output side. This paper addresses the issue of evaluating the minimum resequence-queue size required for a deadlock-free lossless operation. An analytical method is presented for the exact evaluation of the worst-case resequencing delay and the worst-case resequence-queue size. The results obtained reveal their relation, and demonstrate the impact of the various system parameters on resequencing

Heuristic, parallel, iterative matching algorithms for input-queued cell switches with virtual output queuing require O(log N) iterations to achieve good performance. If the hardware implementation of the number of iterations required is not feasible within the cell duration, the matching process can be pipelined to obtain a matching in every cell time slot. However, existing approaches incur a substantial latency penalty due to the way the pipelining is performed, which renders them unattractive in latency-sensitive applications such as parallel computer interconnects. We introduce a new class of pipelined matching algorithms that can be based on any existing iterative matching algorithm, makes the minimum latency independent of the pipeline depth, and is highly amenable to distributed implementation. Our simulation results confirm that specific instances of this class achieve significantly lower average latency throughout the load range than existing schemes do. We also propose an instantiation of the scheme that, in addition, significantly improves the performance with nonuniform traffic.

In a hierarchical network, groups of nodes are represented by logical nodes for the purposes of simplifying routing. Each group has a set of ingress-egress nodes, and routing information is conveyed to the outside world in the form of a transition matrix that gives the cost of traversing the network between each ingress-egress node pair. In this paper, we present a minimal logical node representation that has sufficient descriptive power to enable path selection in support of connection admission control for services that have both path (restrictive) and link (additive) constraints. For example, the representation can be used to find a path that maximizes bandwidth subject to a delay constraint or minimizes delay subject to a bandwidth constraint. We present our solution in the form of a matrix whose elements are vectors, each of which specifies the efficient frontier of the solution space, and we specify an efficient procedure for constructing the efficient frontier. We present the least upper bound on the number of elements that must be present in the efficient frontier. We provide numerical examples that illustrate construction of the efficient frontier.

The private network-to-network interface (PNNI) protocol, which specifies how topology information is to be distributed in an ATM network, allows ATM switches to be aggregated into clusters called peer groups. Outside of a peer group its topology is aggregated into a single logical node. This method can be applied recursively so that PNNI can hierarchically aggregate network topology state information. To provide good accuracy in choosing optimal paths in a PNNI network, the PNNI standard provides a way to represent a peer group with a structure called the complex node representation. It allows the cost of traversing the peer group between any ingress and egress to be advertised in a compact form. Complex node representations using a small number of links result in a correspondingly short path computation time and therefore in good performance. It is, therefore, desirable that the complex node representation contains as few links as possible. This paper considers the class of complex node representations for which the path computation time is minimal. It assumes that the path selection is based on restrictive costs, such as bandwidth, and considers the symmetric case. It presents a method for constructing the set of the optimal complex node representations in the sense that they use the minimum possible number of links. Central to the development of this method is the establishment of the optimal substructure property of the optimal complex node representations.

In earlier work, a new mechanism was introduced that belongs to the class of feedback control schemes which ensure no data losses and operate based on simple `stop' and `start' signals. This algorithm can operate with the theoretically smallest possible buffer size and it also has the capability of controlling the amount of overhead generated by the protocol signals. In the present paper, an analytical performance study of the minimal and maximal overheads as well as the corresponding throughputs is presented. The results obtained demonstrate the impact of the distance and other relevant parameters.

This paper presents a new feedback congestion control mechanism for the flow control of the best-effort available bit rate (ABR) traffic in ATM networks. This new mechanism belongs to the class of feedback control schemes that ensure no data losses and operate based on simple 'stop' and 'start' signals. A novelty presented by this paper is a methodology which, for a given set of desired properties, leads to the specification of the corresponding control algorithm. For the case of a single connection, the algorithm can operate with the theoretically minimum possible buffer size. Interestingly, the algorithm obtained has a different structure than the previous schemes; it does not operate based on fixed high and low thresholds. A new congestion control mechanism is subsequently derived for the flow control of multiple connections. The new scheme is exercised hop-by-hop and on a per-connection basis. This scheme allows connections to share memory and bandwidth resources efficiently within the network. The performance of the new scheme is also presented, and its statistical multiplexing efficiency is demonstrated. The measures investigated include buffer occupancy, average delay, overhead due to the protocol signals, and sustained throughput. In the case of long propagation delays, the buffer savings achieved by the new scheme are substantial.>

A single-stage nonblocking N*N packet switch with both output and input queuing is considered. The limited queuing at the output ports resolves output port contention partially. Overflow at the output queues is prevented by a backpressure mechanism and additional queuing at the input ports. The impact of the backpressure effect on the switch performance for arbitrary output buffer sizes and for N to infinity is studied. Two different switch models are considered: an asynchronous model with Poisson arrivals and a synchronous model with Bernoulli arrivals. The investigation is based on the average delay and the maximum throughput of the switch. Closed-form expressions for these performance measures are derived for operation with fixed size packets. The results demonstrate that a modest amount of output queuing, in conjunction with appropriate switch speedup, provides significant delay and throughput improvements over pure input queuing. The maximum throughput is the same for the synchronous and the asynchronous switch model, although the delay is different. >

A heterogeneous M/M/2/L queueing system in which two servers may work at different rates is considered. A class of threshold type scheduling policies, called fixed position policies (FPPs), is introduced. If first-in first-out (FIFO) delivery is required, departures must wait at the receiving node to be put back into proper sequence. Therefore, they incur resequencing delay in addition to whatever previous delays they experienced. A new approach, based on an imbedded Markov chain model for obtaining the resequencing delay characteristics of FPPs is developed. Closed-form expressions for the distribution and the mean of the resequencing delay are derived. For a given threshold value, the choice of the preferred FPP depends on which optimization criterion issued, such as the mean resequencing delay or the expected resequence buffer occupancy. It is shown that the selection rule for the preferred policy depends only on the ratio of the service rates. However, the optimal policy which minimizes the total delay also depends on the threshold. Application examples of these optimization procedures are presented.>

High performance in advanced packet switches can be achieved by providing queuing both at the input and the output ports. The author studies the performance of this class of switches under nonuniform traffic. Two different output queuing arrangements are considered, namely, the case where dedicated queues are provided at each output port, and the case where the output queuing space is shared among all the output ports. An analytical approach is presented for the performance study of these two schemes in the case of operation with fixed-size packets and under various degrees of traffic imbalance at the inputs or the outputs. The measures investigated include the average delay, the maximum throughput of the switch in the case of output traffic imbalance, and the saturation load in the case of input traffic imbalance. Analytical results for these measures are derived for the case of a switch with a large number of input and output ports. Numerical results for the maximum throughput and the saturation load are presented. It is demonstrated that the scheme of output sharing performs better than the scheme of dedicated output queuing.>

The resequencing problem is considered in a distributed system environment with multiple classes. A system consisting of two parallel heterogeneous M/M/1 queues shared by C different arrival classes is presented and analyzed. Arriving customers are distributed among the two queues according to a probability distribution which depends upon their class. If customers belong to the same class must depart from the server at the same order as they arrived, they incur additional delay called resequencing delay. A recursive solution technique is first introduced to obtain the exact expression for the expected resequencing delay for a single-class case. The result is then extended to the case of a single class with interfering traffic. Some numerical examples are presented to illustrate changes of resequencing delay as a function of distributed loads to servers.>

In service centers with multiple-parallel servers, jobs may complete their service in a different order from the one in which they enter the center. In order to reestablish the original order, resequencing protocols need to be implemented. It is shown that under a threshold-type policy, the resequencing delay depends on the strategy by which customers are selected and dispatched to the servers. Two selection strategies are developed, and the delay characteristics corresponding to the two strategies are studied. Existing methods for finding the sequencing delay are extended to cover the threshold-type policy. Closed-form solutions for the resequencing delay distributions under both selection policies are derived. To characterize the performance of the system under the two policies, two optimization criteria are introduced, namely, the fraction of customers that experience resequencing delay and the mean resequencing delay. These quantities are calculated explicitly, and their comparison reveals that the optimal decision is independent of the load on the system. The selection of the optimal policy under the first criterion depends only on the service rates, whereas for the second criterion the optimal selection depends on the threshold value and the ratio of the service rates.>