Cloud computing has evolved from just being perceived as a way to reduce and manage IT costs to becoming a key driver for enterprise transformation. The shift has been fueled by the confluence of social, mobile cloud, big-data and analytics technologies. In this paper, we introduce Industry Cloud as an aggregation of domain specific, workload optimized and value added capabilities supporting an industry and a foundation to drive the transformation. Enterprises are developing and deploying new types of solutions called System of Insight (SOI) solutions that connect enterprise data to customer engagement data with analytics to derive new insights. We discuss several examples of the solutions, and present a architecture pattern that we see emerging to support these solutions. We conclude the paper by highlighting some key research topics in cloud computing to support these emerging trends.

Summary form only given. For many years ED1 served as the dominant protocol for e-biz over private networks. Due to the rapid spread of the Internet, several new Business-to-Business (B2B) interaction protocols have become popular, e.g., Open Buying on the Internet (OBI), RosettaNet, and Vendor-defined protocols such as Ariba's Punchout process. We will describe these protocols, with an emphasis on their similarity and differences. B2B marketplaces are emerging as hubs through which suppliers connect to buyers. We outline the connectivity requirements between these marketplaces, and the Marketplace-to-Marketplace (M2M) protocols that are required. We show how all of these emerging protocols can be specified in XML using a trading partner agreement (TPA). The TPA specifies three layers in the B2B protocol: The transport, document exchange and business protocol layers. Essentially, the transport layer provides a choice of transport such as HTTP, SMTP, FTP, and specifies related information; the document exchange layer handles different message formats, transformations, application level security including authentication and non-repudiation, and provides services such as audit trails and document repositories; the business protocol layer specifies the sequence of the B2B interactions, responsiveness criteria, and error handling.

We study design alternatives for, and describe implementations and performance of, a scalable and highly available Web server accelerator. The accelerator runs under an embedded operating system and improves Web server performance by caching data. The basic design alternatives include a content router or a TCP router (without content routing) in front of a set of Web cache accelerator nodes, with the cache memory distributed across the accelerator nodes. Content based routing reduces cache node CPU cycles but can make the front-end router a bottleneck. With the TCP router, a request for a cached object may initially be sent to the wrong cache node; this results in larger cache node CPU cycles, but can provide a higher aggregate throughput, because the TCP router becomes a bottleneck at a higher throughput than the content router. Based on measurement of implementations, we quantify the throughput ranges in which different designs are preferable. We also examine a combination of content based and TCP routing techniques. We examine optimizations, such as different communication and data delivery methods, replication of hot objects, and cache replacement policies that take into account the fact that there might be different bottlenecks in the system at different times; depending upon which resource is likely to become a bottleneck, a different cache replacement algorithm is applied.

We describe the design, implementation and performance of a Web server accelerator which runs on an embedded operating system and improves Web server performance by caching data. The accelerator resides in front of one or more Web servers. Our accelerator can serve up to 5000 pages/second from its cache on a 200 MHz PowerPC 604. This throughput is an order of magnitude higher than that which would be achieved by a high-performance Web server running on similar hardware under a conventional operating system such as Unix or NT. The superior performance of our system results in part from its highly optimized communications stack. In order to maximize hit rates and maintain updated caches, our accelerator provides an API which allows application programs to explicitly add, delete, and update cached data. The API allows our accelerator to cache dynamic as well as static data, analyze the SPECweb96 benchmark, and show that the accelerator can provide high hit ratios and excellent performance for workloads similar to this benchmark.

Virtual malls allow consumers to shop and purchase products on the World Wide Web from multiple stores. The paper presents a virtual mall in which stores may be distributed across multiple Web sites. Stores participate in the virtual mall by communicating with a mall coordinator. The virtual mall allows shoppers to perform actions across multiple stores simultaneously such as viewing product availability. Multiple purchases across different stores can be coordinated using multi-phase commits. The mall coordinator can authenticate clients on all stores participating in the virtual mall while only requiring clients to provide authentication information once. State information is preserved using dynamic argument embedding which is compatible with all browsers and servers supporting HTTP and is less obtrusive than cookies. The distributed virtual mall concept and infrastructure can be applied to other distributed electronic commerce applications on the Web.

A distributed multiserver Web site can provide the scalability necessary to keep up with growing client demand at popular sites. Load balancing of these distributed Web-server systems, consisting of multiple, homogeneous Web servers for document retrieval and a Domain Name Server (DNS) for address resolution, opens interesting new problems. In this paper, we investigate the effects of using a more active DNS which, as an atypical centralized scheduler, applies some scheduling strategy in routing the requests to the most suitable Web server. Unlike traditional parallel/distributed systems in which a centralized scheduler has full control of the system, the DNS controls only a very small fraction of the requests reaching the multiserver Web site. This peculiarity, especially in the presence of highly skewed load, makes it very difficult to achieve acceptable load balancing and avoid overloading some Web servers. This paper adapts traditional scheduling algorithms to the DNS, proposes new policies, and examines their impact under different scenarios. Extensive simulation results show the advantage of strategies that make scheduling decisions on the basis of the domain that originates the client requests and limited server state information (e.g., whether a server is overloaded or not). An initially unexpected result is that using detailed server information, especially based on history, does not seem useful in predicting the future load and can often lead to degraded performance.

A distributed Web system, consisting of multiple servers for data retrieval and a Domain Name Server (DNS) for address resolution, can provide the scalability necessary to keep up with growing client demand at popular sites. However, balancing the requests among these atypical distributed servers opens interesting new challenges. Unlike traditional distributed systems in which a centralized scheduler has full control of the system, the DNS controls only a small fraction of the requests reaching the Web site. This makes it very difficult to avoid overloading situations among the multiple Web servers. We adapt traditional scheduling algorithms to the DNS, propose new policies, and examine their impact. Extensive simulation results show the advantage of using strategies that schedule requests on the basis of the origin of the clients and very limited state information, such as whether a server is overloaded or not. Conversely, algorithms that use detailed state information often exhibit the worst performance.

Clustered multimedia servers, consisting of interconnected nodes and disks, have been proposed for large-scale servers that are capable of supporting multiple concurrent streams which access the video objects stored in the server. As the number of disks and nodes in the cluster increases, so does the probability of a failure. With data striped across all disks in a cluster, the failure of a single disk or node results in the disruption of many or all streams in the system. Guaranteeing high availability in such a cluster becomes a primary requirement to ensure continuous service. In this paper, we study mirroring and software RAID schemes with different placement strategies that guarantee high availability in the event of disk and node failures while satisfying the real-time requirements of the streams. We examine various declustering techniques for spreading the redundant information across disks and nodes and show that random declustering has good real-time performance. Finally, we compare the overall cost per stream for different system configurations. We derive the parameter space where mirroring and software RAID apply, and determine optimal parity group sizes.

Clustering multiple computing nodes has become increasingly popular for reasons of capacity, availability and cost. One approach to clustering is the data sharing approach where a number of loosely coupled nodes share a common database. In this environment, a global shared buffer can be introduced to alleviate the multisystem invalidation effect either as a disk cache or shared intermediate memory. We develop an analytic model to evaluate different shared buffer management policies (SBMPs) which differ in their choice of data granules to be put into the shared buffer. The methodology analyzes all policies using a uniform framework by decomposing the input stream to the shared buffer into multiple (three) component streams based on their effects on the dependency between the private and shared buffer contents. This approach simplifies the problem of analyzing different SBMPs into 1) estimating the rate of each component stream, and 2) evaluating the impact of dependency on each type of component stream and hence the shared buffer hit probability. A detailed simulation model is also developed to validate the analytic model. We also illustrate how the analytic buffer model can be integrated with other system submodels to examine trade-offs between the SBMPs and to estimate optimal shared buffer allocations from a cost-performance point of view.>

Examines the effect of skewed database access on the transaction response time in a multisystem data sharing environment, where each computing node has access to shared data on disks, and has a local buffer of recently accessed granules. Skewness in data access can increase data contention since most accesses go to few data items. For the same reason, it can also increase the buffer hit probability. We quantify the resultant effect on the transaction response time, which depends not only on the various system parameters but also on the concurrency control (CC) protocol. Furthermore, the CC protocol can give rise to rerun transactions that have different buffer hit probabilities. In a multisystem environment, when a data block gets updated by a system, any copies of that block in other systems' local buffers are invalidated. Combining these effects, we find that higher skew does not necessarily lead to worse performance, and that with skewed access, optimistic CC is more robust than pessimistic CC. Examining the buffer hit probability as a function of the buffer size, we find that the effectiveness of additional buffer allocation can be broken down into multiple regions that depend on the access frequency distribution.>

Parallel processing is an attractive option for relational database systems. As in any parallel environment however, load balancing is a critical issue which affects overall performance. Load balancing for one common database operation in particular, the join of two relations, can be severely hampered for conventional parallel algorithms, due to a natural phenomenon known as data skew. In a pair of recent papers (J. Wolf et al., 1993; 1993), we described two new join algorithms designed to address the data skew problem. We propose significant improvements to both algorithms, increasing their effectiveness while simultaneously decreasing their execution times. The paper then focuses on the comparative performance of the improved algorithms and their more conventional counterparts. The new algorithms outperform their more conventional counterparts in the presence of just about any skew at all, dramatically so in cases of high skew.>

A simple analysis for the transient buffer hit probability for a system starting with an empty buffer is presented. The independent reference model (IRM) is used for buffer accesses. It is shown that the expected buffer hit probability when the buffer becomes full is virtually identical to the steady state buffer hit probability when the replacement policy is least recently used (LRU). The method is generalized to estimate the transient behavior of the LRU policy starting with a non-empty buffer. It is shown that this method can be used to estimate the effect of a load surge on the buffer hit probability. It is also shown that after a short load surge, it can take much longer than the surge duration for the buffer hit probability to return to its steady state value.>

The TPC-C benchmark is a new benchmark approved by the TPC council intended for comparing database platforms running a medium complexity transaction processing workload. Some key aspects in which this new benchmark differs from the TPC-A benchmark are in having several transaction types, some of which are more complex than that in TPC-A, and in having data access skew. In this paper we present results from a modelling study of the TPC-C benchmark for both single node and distributed database management systems. We simulate the TPC-C workload to determine expected buffer miss rates assuming an LRU buffer management policy. These miss rates are then used as inputs to a throughput model. From these models we show the following: (i) We quantify the data access skew as specified in the benchmark and show what fraction of the accesses go to what fraction of the data. (ii) We quantify the resulting buffer hit ratios for each relation as a function of buffer size. (iii) We show that close to linear scale-up (about 3% from the ideal) can be achieved in a distributed system, assuming replication of a read-only table. (iv) We examine the effect of packing hot tuples into pages and show that significant price/performance benefit can be thus achieved. (v) Finally, by coupling the buffer simulations with the throughput model, we examine typical disk/memory configurations that maximize the overall price/performance.

The Concurrency Control (CC) scheme employed can profoundly affect the performance of transaction-processing systems. In this paper, a simple unified approximate analysis methodology to model the effect on system performance of data contention under different CC schemes and for different system structures is developed. This paper concentrates on modeling data contention and then, as others have done in other papers, the solutions of the data contention model are coupled with a standard hardware resource contention model through an iteration. The methodology goes beyond previously published methods for analyzing CC schemes in terms of the generality of CC schemes and system structures that are handled. The methodology is applied to analyze the performance of centralized transaction processing systems using various optimistic- and pessimistic-type CC schemes and for both fixed-length and variable-length transactions. The accuracy of the analysis is demonstrated by comparison with simulations. It is also shown how the methodology can be applied to analyze the performance of distributed transaction-processing systems with replicated data.

A parallel sort-merge-join algorithm which uses a divide-and-conquer approach to address the data skew problem is proposed. The proposed algorithm adds an extra, low-cost scheduling phase to the usual sort, transfer, and join phases. During the scheduling phase, a parallelizable optimization algorithm, using the output of the sort phase, attempts to balance the load across the multiple processors in the subsequent join phase. The algorithm naturally identifies the largest skew elements, and assigns each of them to an optimal number of processors. Assuming a Zipf-like distribution of data skew, the algorithm is demonstrated to achieve very good load balancing for the join phase, and is shown to be very robust relative, among other things, to the degree of data skew and the total number of processors.>

Presents a parallel hash join algorithm that is based on the concept of hierarchical hashing, to address the problem of data skew. The proposed algorithm splits the usual hash phase into a hash phase and an explicit transfer phase, and adds an extra scheduling phase between these two. During the scheduling phase, a heuristic optimization algorithm, using the output of the hash phase, attempts to balance the load across the multiple processors in the subsequent join phase. The algorithm naturally identifies the hash partitions with the largest skew values and splits them as necessary, assigning each of them to an optimal number of processors. Assuming for concreteness a Zipf-like distribution of the values in the join column, a join phase which is CPU-bound, and a shared nothing environment, the algorithm is shown to achieve good join phase load balancing, and to be robust relative to the degree of data skew and the total number of processors. The overall speedup due to this algorithm is compared to some existing parallel hash join methods. The proposed method does considerably better in high skew situations.>

The concurrency control (CC) method employed can be critical to the performance of transaction processing systems. Conventional locking suffers from the blocking phenomenon, where waiting transactions continue to hold locks and block other transactions from progressing. In a high data contention environment, as an increasing number of transactions wait, a larger number of lock requests get blocked and fewer lock requests can get through. The proposed scheme reduces the blocking probability by deferring the blocking behavior of transactions to the later stages of their execution. By properly balancing the blocking and abort effects, the proposed scheme can lead to better performance than either the conventional locking or the optimistic concurrency control (OCC) schemes at all data and resource contention levels. We consider both static and dynamic approaches to determine when to switch from the nonblocking phase to the blocking phase. An analytical model is developed to estimate the performance of this scheme and determine the optimal operating or switching point. The accuracy of the analytic model is validated through a detailed simulation.>

The CLOCK algorithm is a popular buffer replacement algorithm because of its simplicity and its ability to approximate the performance of the Least Recently Used (LRU) replacement policy. The Generalized Clock (GCLOCK) buffer replacement policy uses a circular buffer and a weight associated with each page brought in buffer to decide on which page to replace. We develop an approximate analysis for the GCLOCK policy under the Independent Reference Model (IRM) that applies to many database transaction processing workloads. We validate the analysis for various workloads with data access skew. Comparison with simulations shows that in all cases examined the error is extremely small (less than 1%). To show the usefulness of the model we apply it to a Transaction Processing Council benchmark A (TPC-A) like workload. If knowledge of the different data partitions in this workload is assumed, the analysis shows that, with appropriate choice of weights, the performance of the GCLOCK algorithm can be better than the LRU policy. Performance very close to that for optimal (static) buffer allocation can be achieved by assigning sufficiently high weights, and can be implemented with a reasonably low overhead. Finally, we outline how the model can be extended to capture the effect of page invalidation in a multinode system.

A system structure and protocols for improving the performance of a distributed transaction processing system when there is some regional locality of data reference are presented. A distributed computer system is maintained at each region, and a central computer system with a replication of all databases at the distributed sites is introduced. It provides the advantage of distributed systems principally for local transactions, and has the advantage of centralized systems for transactions accessing nonlocal data. Specialized protocols keep the copies at the distributed and centralized systems consistent without incurring the overhead and delay of generalized protocols for fully replicated databases. The advantages achievable through this system structure and the tradeoffs between protocols for concurrency and coherency control of the duplicate copies of the databases are studied. An approximate analytic model is used to estimate the system performance. It is found that the performance is sensitive to the protocol and that substantial performance improvement can be obtained as compared with distributed systems.>

Analytical models are developed to study hybrid CC (concurrency control) schemes which employ a different CC scheme to handle rerun transactions, since their characteristics are different from the first run of transactions. These include switching to static or dynamic locking during rerun (referred to as static and dynamic hybrid OCC (optimistic concurrency control) schemes, respectively), and switching to broadcast OCC during rerun, while doing pure OCC for the first run. In a high data contention environment where locking is inferior to OCC, analysis shows that the performance can be substantially improved by using this hybrid approach and the authors study the tradeoff of the different hybrid CC schemes. The analytic models are based on a decomposition approach and use a mean-value-type analysis. The accuracy of the analysis is validated through simulations.>

The pure optimistic concurrency control (OCC) scheme, which only aborts a transaction at its commit time, can do better than aborting transactions as soon as conflict is detected (broadcast OCC). To further exploit this phenomenon, hybrid CC schemes are devised which use a different CC scheme to handle rerun transactions. These include switching to static or dynamic locking (static and dynamic hybrid OCC schemes, respectively) or to broadcast OCC during rerun, while doing pure OCC for the first run. In the high-data contention environment, where locking is inferior to OCC, it is found that the static and dynamic hybrid OCC can do better than OCC.>

A parallel hash join algorithm based on the concept of hierarchical hashing is proposed to address the problem data skew. The proposed algorithm adds an extra scheduling phase to the usual hash and join phases. During the scheduling phase, a heuristic optimization algorithm, using the output of the hash phase, attempts to balance the load across the multiple processors in the subsequent join phase. The algorithm naturally identifies the hash partitions with the largest skew elements, splits them up, and assigns each of them to an optimal number of processors. Assuming a Zipf-like distribution of the elements in the join column, the algorithm is shown to achieve good load balancing for the join phase in a CPU-bound environment, and it is shown to be fairly robust relative to the degree of data skew and the total number of processors. The overall speedup due to this algorithm is compared with conventional parallel hash join methods and the considerable advantage of the proposed method is demonstrated even when the additional scheduling phase is taken into account.>

In a data sharing environment, where a number of loosely coupled computing nodes share a common storage subsystem, the effectiveness of a private buffer at each node is limited due to the multi-system invalidation effect, particularly under a non-uniform data access pattern. A global shared buffer can be introduced to alleviate this problem either as a disk cache or shared memory. In this paper we developed an approximate analytic model to evaluate different shared buffer management policies (SBMPs) which differ in their choice of data granules to be put into the shared buffer. The analytic model can be used to study the trade-offs of different SBMPs and the impact of different buffer allocations between shared and private buffers. The effects of various parameters, such as, the probability of update, the number of nodes, the sizes of private and shared buffer, etc., on the performance of SBMPS are captured in the analytic model. A detailed simulation model is also developed to validate the analytic model. We show that dependency between the contents of the private and shared buffers can play an important role in determining the effectiveness of the shared buffer particularly for a small number of nodes.

An examination is made of a technique to derive the time-stamp or interval of time-stamps dynamically by using limited time-stamp history information to re-order transaction at commit time and to derive a back-shifted time-stamp for certification to reduce read-write conflicts. An analytic model to quantify the performance improvement by comparison with the basic time-stamp certification scheme is developed. Since the committed conflicting transaction may itself be back-shifted, the analytic model needs to estimate the distribution of the back-shift of the certification time-stamp in order to determine the probability of successfully back-shifting a transaction requesting commit. It is shown how this relatively complex protocol can be analyzed using a few simple approximations, validate the analysis through simulations, and the range of parameter values for which this approach is most beneficial is determined.>

A simple analytic buffer model for coupled systems sharing a common database is developed. When a data block gets updated by a system, copies of that block in other systems' buffers need to be invalidated. This cross-invalidation phenomenon makes the estimation of the buffer hit ratio interesting. The concurrency control (CC) scheme can also complicate the situation. Under the optimistic CC protocol, conflicting transactions can get aborted and need to be rerun. Rerun transactions tend to exhibit a higher hit ratio than first-run transactions since reference blocks, except those that were invalidated, are likely to continue to reside in the buffer. On the other hand, the buffer hit ratio affects not only the number of IOs but also the abort probability. The authors develop a buffer model to capture these effects and integrate it with a CC model to estimate the overall transaction response time Since the invalidation rate increases with buffer size, the advantage of a larger buffer size in the data-sharing environment becomes an issue. The model is then used to study this issue and estimates the maximum buffer that can be usefully employed in each system. The analysis is validated through simulations.>

An external parallel merge-sort and sort-merge join on tightly coupled processors is considered. The issue of whether significant speedup can be achieved with good CPU efficiency is addressed. A pure sort query and a five-relation join query using a sort-merge-join algorithm are examined. It is found that the external sort is readily parallelizable. In the absence of skew, a speedup, linear in the number of tightly coupled processors can be obtained. However, it is shown that skew can reduce the speedup significantly. An examination is made of how important types of skew can be handled to yield close to linear speedup. The effect on the speedup and CPU efficiency of the database size, memory constraints, CPU MIPS, query selectivity, I/O striping and skew is shown.>

The concurrency control method employed can be critical to the performance of transaction processing systems. The conventional locking scheme tends to suffer from the blocking phenomenon. The proposed scheme reduces the blocking probability by deferring the blocking behavior of transactions to the later stages of their execution. The transaction execution can then be divided into a nonblocking phase, in which transactions wait for locks but do not block other transactions, and a blocking phase, as in conventional locking. Data accessed during the nonblocking phase can lead to transaction abort. By properly balancing the blocking and abort effects, the proposed scheme can lead to better performance at all data and resource contention levels than either conventional locking or the optimistic concurrency control schemes. Both simulation and analytical models are used for estimating the performance of this scheme.>

The authors develop an approximate analytical model to study the tradeoffs of replicating data in a distributed database environment. Several concurrency control protocols are considered, including pessimistic, optimistic, and semi-optimistic protocols. The approximate analysis captures the effect of the protocol on hardware resource contention and data contention. The accuracy of the approximation is validated through detailed simulations. It is found that the benefit of replicating data and the optimal number of replicates are sensitive to the concurrency control protocol. Under the optimistic and semi-optimistic protocols, replications can significantly improve response time with an additional MIPS (million instructions per second) requirement to maintain consistency among the replicates. The optimal degree of replication is further affected by the transaction mix (e.g. the fraction of read-only transactions), the communications delay and overhead, the number of distributed sites, and the available MIPS. Sensitivity analyses have been carried out to examine how the optimal degree of replication changes with respect to these factors.>

A hybrid system structure comprised of distributed systems to take advantage of locality of reference and a central system to handle transactions that access non-local data is examined. Several transaction processing applications, such as reservation systems, insurance and banking have such regional locality of reference. A concurrency and coherency control protocol that maintains the integrity of the data and performs well for transactions that access local or non-local data is described. It is shown that the performance of the hybrid system is much less sensitive to the fraction of remote accesses than the distributed system and offers similar performance to the distributed system for local transactions.>

An examination is made of a system structure and protocols to improve the performance and availability of a distributed transaction processing (TP) system when there is some regional locality of data reference. Several TP applications, such as reservation systems, insurance, and banking, belong to this category. While maintaining a distributed system at each region, a central system is introduced with a replication of all databases at the distributed sites. Specialized protocols can be designed to keep the copies at the distributed and centralized systems consistent without incurring the overhead and delay of generalized protocols for fully replicated databases. The authors study the advantages of this system structure and the tradeoffs between protocols for concurrency and coherency control of the duplicate copies of the databases. An approximate analytic model is used to estimate the system performance and the method is validated through simulations.>

The authors propose an integrated control mechanism and analyze the performance gain due to its use. An extension to the data sharing system structure is examined in which a shared intermediate memory is used for buffering and for early commit processing. Read-write-synchronization and write-serialization problems arise. The authors show how the integrated concurrency protocol can be used to overcome both problems. A queueing model is used to quantify the performance improvement. Although using intermediate memory as a buffering device produces a moderate performance benefit, the analysis shows that more substantial gains can be realized when this technique is combined with the use of an integrated concurrency-coherency control protocol.>

A hybrid architecture is proposed that combines the approaches of a multisystem partitioned database system and a data-sharing multisystem approach offering the advantages of each. With this architecture some databases are shared between systems, while others are retained private by specific systems. The authors examine how to determine which databases to share, which to retain private, and how to route transactions and partition the private databases among systems so as to minimize response time or overheads while balancing the load among systems. A simulated annealing heuristic is used to solve this optimizing problem. Trace data from large mainframe systems running IBM's Information Management System database management system are used to illustrate the methodology and to demonstrate the advantages of the hybrid approach.>

In a hybrid distributed-centralized database system architecture, some transactions run at (geographically) distributed systems, and other transactions at a central computing complex. Static and dynamic load-sharing strategies are studied for such systems. The strategies take into account not only the difference in load at different sites, but also the effect of routing on data-contention and transaction-abort probabilities. Five dynamic strategies are examined and are compared with an optimal static strategy. A dynamic strategy that is based on analytical estimates of the effect of routing on all transactions in the system, rather than that on the incoming transaction alone, is found to be the best.>

Proposes and evaluates a hybrid architecture that combines the approaches, and offers the advantages of both data sharing and data partitioning. Some databases are shared between systems, while others are retained private by specific systems. The issue is to determine which databases to share, which to retain private, and how to route transactions and partition the private databases among systems so as to minimize response time or overheads, while balancing the load among systems. A simulated annealing heuristic is used to solve this optimization problem. Trace data from large mainframe systems running IBM's IMS database management system are used to illustrate the methodology and to demonstrate the advantage of the hybrid approach.>

A methodology is developed to determine the number of processors needed to satisfy transaction throughput and response time requirements for processors of different MIPS (sizes). The minimum MIPS per processor required to satisfy response time and throughput constraints in a transaction processing complex of N coupled systems is also determined. For realistic overhead assumptions, despite large assumed cost advantages on a per-MIPS basis, it is found that very small systems may not match up to the cost/performance of some larger systems, when required to meet the same throughput and response-time constraints. If transactions running on smaller systems were allowed a larger response-time constraint, then it may be possible to construct a lower-cost system from smaller and less expensive processors, generally with lower supportable maximum throughput. Besides the coupling degradation between multiprocessor systems, there is a small systems effect. The cost criterion indicates that there is an optimum processor size below which total system costs would increase appreciably.>

The demand for larger transaction rates and the inability of single-system-based transaction processors to keep up with demand have resulted in the growth of multi-processor-based database systems. The focus here is on coupling in a locally distributed system through multi-system data sharing in which all systems have direct access to the data. This paper addresses the following questions; i) How does a workload running on a single system today perform if migrated to a multi-system? ii) What are the multi-system locking design issues that limit multi-system performance and what is the maximum number of systems that may be effectively coupled? iii) Can alternative locking designs increase the number of systems that may be effectively coupled? Our analysis is based on traces from large mainframe systems running IBM's IMS database management system. We have developed a hierarchical modeling methodology that starts by synthesizing a multi-system IMS lock trace and a reference trace from single-system traces. The multisystem traces are used in trace-driven simulations to predict lock contention and database I/O increase in multi-system environment and to generate workload parameters. These parameters are used in event-driven simulation models to examine the overall performance under different system structures. Performance results are presented for realistic system parameters to determine the performance impact of various design parameters. Lock contention is found to be the critical factor in determining the coupling effectiveness and the effect of alternative locking design to reduce lock contention is studied. The limit on coupling is explored and the analysis indicates that, for this workload, on the order of 6 to 12 systems may be effectively coupled through data sharing, depending on system structure and locking design.

In a multi-system database system with a function request shipping approach, the databases are partitioned among the multiple systems and a facility is provided to support the shipping of database requests among the systems. This is in contrast to a data sharing multi-system approach in which all systems have direct access to the shared database. The performance of the function request shipping approach is examined and compared with the data sharing approach. The emphasis is on generic issues that affect the function shipping approach. Trace data from large mainframe systems running IBM's IMS database management system are used to illustrate the issues of partitioning. A methodology is presented for partitioning the databases and routing transactions among the systems so as to minimize the fraction of remote function calls, while balancing the load among systems. Estimates of the resulting remote function calls, mirror transaction setups, and multi-system two-phase commits, are obtained. A simulation model and approximate analysis are used to examine the overall system performance, to study the effect of various workload parameters and design alternatives and to compare the function shipping and data sharing approaches.

The prospect of coupling a large number of small inexpensive microprocessor based systems to deliver the performance of a large transaction processing system at lower cost has not been realized, to date. Inter-system interference, multi-system coupling protocol overhead and the increased processing time for smaller systems can cause considerable degradation. A methodology is developed to determine the number of processors needed to satisfy transaction throughput and response time requirements for processors of different MIPS (sizes). The minimum MIPS per processor required to satisfy response time, throughput and utilization constraints in a transaction processing complex of N coupled systems is also determined, by using an approximate analytical model driven by measured workload parameters. Despite large assumed cost advantages on a per MIPS basis we find that small systems do not match up to the cost/performance of some larger systems. Besides multi-system's coupling degradation, there is a small system effect. Because of the increased transaction execution time in smaller systems, transaction hold on to resources longer, thereby causing increased inter-system interference. Our cost criterion indicates that there is an optimum processor size below which total system costs would increase appreciably. Ways to reduce the inter-system interference and coupling protocol overheads are investigated and shown to shift this optimum.

In a multisystem database system with a function request shipping approach, the databases are partitioned among the multiple systems and a facility is provided to support the shipping of database requests among the systems. This is in contrast to a data sharing multisystem approach in which all systems have direct access to the shared database. The performance of the two approaches is compared, emphasizing generic issues that affect the function shipping approach. A methodology is presented for partitioning the databases and routing transactions among the systems so as to minimize the fraction of remote function calls, while balancing the load among systems. Estimates of the resulting remote function calls, mirror transaction setups, and multisystem two-phase commits are obtained. Results of simulation and approximate analysis are presented.

The performance of multiple systems sharing a common data base is analyzed for an architecture with concurrency control using a centralized lock engine. The workload is based on traces from large mainframe systems running IBM's IMS database management system. Based on IMS lock traces the lock contention probability and data base buffer invalidation effect in a multi-system environment is predicted. Workload parameters are generated for use in event-driven simulation models that examine the overall performance of multi-system data sharing, and to determine the performance impact of various system parameters and design alternatives. While performance results are presented for realistic system parameters, the emphasis is on the methodology, approximate analysis technique and on examining the factors that affect multi-system performance.

This correspondence investigates some methods for improving the performance of single-stage shuffle-exchange networks (SSN's) in a packet communication environment where the modules in a computer system communicate by sending fixed size packets. The three new switching strategies proposed use extra buffers to enhance performance, while preventing deadlocks. An intuitive criterion for determining the applicability of approximate analysis techniques is discussed.

This paper investigates some methods for improving the performance of Single Stage Shuffle Exchange Networks (SENs) and Multistage Interconnection Networks (MINs). The three new switching strategies proposed use extra buffers to enhance performance. Approximate analysis and simulation results indicate significant improvement in performance for both SENs and MINs. An intuitive method for determining the applicability of the approximate analysis is discussed and some performance measures, which should be useful in evaluating the performance of networks are defined.

The above paper1 claims to present an exact discrete time Markov chain model for interference analysis of shuffle exchange networks. We show that the solutions presented are inaccurate. This problem has also been considered in [1]–[3], where simpler and more general solutions are presented.

Delta networks are a class of multistage interconnection networks with gate complexity less than crossbar switches that are easy to control, and which include several networks that have been proposed in the literature as special cases. Buffered delta networks have queues of packets between the stages of the network. This paper presents analytic and simulation results for the performance of delta networks in a packet communication environment. The performance of buffered delta networks is compared with unbuffered delta networks and crossbar switches. It is demonstrated that buffering produces considerable improvement in the performance of these networks, making their performance comparable to that of crossbar switches.