In this paper, we study scheduling of a queueing system with zero knowledge of instantaneous network conditions. We consider a one-hop single-server queueing system consisting of$K$queues, each with time-varying and non-stationary arrival and service rates. Our scheduling approach builds on an innovative combination of adversarial bandit learning and Lyapunov drift minimization, without knowledge of the instantaneous network state (the arrival and service rates) of each queue. We then present two novel algorithms SoftMW (SoftMaxWeight) and SSMW (Sliding-window SoftMaxWeight), both capable of stabilizing systems that can be stabilized by some (possibly unknown) sequence of randomized policies whose time-variation satisfies a mild condition. We further generalize our results to the setting where arrivals and departures only have bounded moments instead of being deterministically bounded and propose SoftMW+ and SSMW+ that are capable of stabilizing the system. As a building block of our new algorithms, we also extend the classical EXP3.S algorithm for multi-armed bandits to handle unboundedly large feedback signals, which can be of independent interest.

Due to the proliferation of inference tasks on mobile devices, state-of-the-art neural architectures are typically designed using Neural Architecture Search (NAS) to achieve good tradeoffs between machine learning accuracy and inference latency. While measuring inference latency of a huge set of candidate architectures during NAS is not feasible, latency prediction for mobile devices is challenging, because of hardware heterogeneity, optimizations applied by machine learning frameworks, and diversity of neural architectures. Motivated by these challenges, we first quantitatively assess the characteristics of neural architectures and mobile devices that have significant effects on inference latency. Based on this assessment, we propose an operation-wise framework which addresses these challenges by developing operation-wise latency predictors and achieves high accuracy in end-to-end latency predictions, as shown by our comprehensive evaluations on multiple mobile devices using multicore CPUs and GPUs. To illustrate that our approach does not require expensive data collection, we also show that accurate predictions can be achieved on real-world neural architectures using only small amounts of profiling data.

Hybrid cloud architectures, where private clouds or data centers forward part of their workload to public cloud providers to satisfy quality of service (QoS) requirements, are increasingly common due to the availability of on-demand cloud resources that can be provisioned automatically through programming APIs. In this paper, we analyze performance and revenue in federations of hybrid clouds, where private clouds agree to share part of their local computing resources with other members of the federation. Through resource sharing, underprovisioned members can save on public cloud costs, while overprovisioned members can put their idle resources to work. To reward all hybrid clouds for their contributions (computing resources or workload), public cloud savings due to the federation are distributed among members according to Shapley value.We model this cloud architecture with a continuous-time Markov chain and prove that, if all hybrid clouds have the same QoS requirements, their profits are maximized when they join the federation and share all resources. We also show that this result does not hold when hybrid clouds have different QoS requirements, and we provide a solution to evaluate profit for different resource sharing decisions. Finally, our experimental evaluation compares the distribution of public cloud savings according to Shapley value with alternative approaches, illustrating its ability to discourage free riders of the federation.

Federated learning allows multiple users to collaboratively train a shared classification model while preserving data privacy. This approach, where model updates are aggregated by a central server, was shown to be vulnerable to poisoning backdoor attacks : a malicious user can alter the shared model to arbitrarily classify specific inputs from a given class. In this article, we analyze the effects of backdoor attacks on federated meta-learning , where users train a model that can be adapted to different sets of output classes using only a few examples. While the ability to adapt could, in principle, make federated learning frameworks more robust to backdoor attacks (when new training examples are benign), we find that even one-shot attacks can be very successful and persist after additional training. To address these vulnerabilities, we propose a defense mechanism inspired by matching networks , where the class of an input is predicted from the similarity of its features with a support set of labeled examples. By removing the decision logic from the model shared with the federation, the success and persistence of backdoor attacks are greatly reduced.

Training jobs of deep neural networks (DNNs) can be accelerated through distributed variants of stochastic gradient descent (SGD), where multiple nodes process training examples and exchange updates. The total throughput of the nodes depends not only on their computing power, but also on their networking speeds and coordination mechanism (synchronous or asynchronous, centralized or decentralized), since communication bottlenecks and stragglers can result in sublinear scaling when additional nodes are provisioned. In this paper, we propose two classes of performance models to predict throughput of distributed SGD:fine-grained models, representing many elementary computation/communication operations and their dependencies; andcoarse-grained models, where SGD steps at each node are represented as a sequence of high-level phases without parallelism between computation and communication. Using a PyTorch implementation, real-world DNN models and different cloud environments, our experimental evaluation illustrates that, while fine-grained models are more accurate and can be easily adapted to new variants of distributed SGD, coarse-grained models can provide similarly accurate predictions when augmented with ad hoc heuristics, and their parameters can be estimated with profiling information that is easier to collect.

Small ‘boutique’ clouds challenging the big three (AWS, Azure, Google Cloud) on speed, cost, flexibility, on-prem, and hybrid cloud options are slowly on the rise. This paper comments on the work by Palet al., in 2020, in relation to the efficiency of practical federated small cloud (SC) resource (e.g., VMs) sharing market structures at a market equilibrium. While the work by Palet al., in 2020, guarantees a unique, stable, and efficient sharing equilibrium, it falls short of providing a microscopic view into practically likely sharing network structures (graphs) among SC providers in the market and their effect on market efficiency. Consequently, we envision a graphical federated cloud sharing market and comment on its efficiency guarantee at the market equilibrium. While a symmetric graphical small cloud resource sharing economy is pure-strategy efficient (like in the work by Palet al., in 2020) an asymmetric one generates inefficiencies that improves with an increased number of SCs in the sharing market.

Modern machine learning frameworks can train neural networks using multiple nodes in parallel, each computing parameter updates with stochastic gradient descent (SGD) and sharing them asynchronously through a central parameter server. Due to communication overhead and bottlenecks, the total throughput of SGD updates in a cluster scales sublinearly, saturating as the number of nodes increases. In this paper, we present a solution to predicting training throughput from profiling traces collected from a single-node configuration. Our approach is able to model the interaction of multiple nodes and the scheduling of concurrent transmissions between the parameter server and each node. By accounting for the dependencies between received parts and pending computations, we predict overlaps between computation and communication and generate synthetic execution traces for configurations with multiple nodes. We validate our approach on TensorFlow training jobs for popular image classification neural networks, on AWS and on our in-house cluster, using nodes equipped with GPUs or only with CPUs. We also investigate the effects of data transmission policies used in TensorFlow and the accuracy of our approach when combined with optimizations of the transmission schedule.

The recent emergence of the small cloud (SC), both in concept and in practice, has been driven mainly by issues related to service cost and complexity of commercial cloud providers (e.g., Amazon) employing massive data centers. However, the resource inelasticity problem faced by the SCs due to their relatively scarce resources might lead to a potential degradation of customer QoS and loss of revenue. A proposed solution to this problem recommends the federated sharing of resources between competing SCs to alleviate the resource inelasticity issues that might arise. Based on this idea, a recent effort proposed SC-Share, a performance-driven static market model for competitive small cloud environments that results in an efficient market equilibrium jointly optimizing customer QoS satisfaction and SC revenue generation. However, an important question with a non-obvious answer still remains to be answered, without which SC sharing markets may not be guaranteed to sustain in the long-run - is it still possible to achieve a stable market efficient state when the supply of SC resources is dynamic in nature?. In this article, we take a first step to addressing the problem of efficient market design for single SC resource sharing in dynamic environments. We answer our previous question in the affirmative through the use of Arrow and Hurwicz's disequilibrium process in economics, and the gradient play technique in game theory that allows us to iteratively converge upon efficient and stable market equilibria.

Millimeter Wave (Mm Wave) massive multiple-input multiple-output (MIMO) has become an advantageous technology for gigabit-per-second data transmission in 5G wireless communication. To achieve low-cost and energy-efficient hardware components, one-bit quantized massive MIMO systems have been proposed for the receiver hardware architecture. The main focus of this work is leveraging the advantages of a state of the art one-bit quantized massive MIMO system for design of an adaptive-bit massive MIMO system. Hence, in this work, by leveraging the benefits of variational approximate message passing (VAMP), a novel MMSE-based VAMP algorithm is proposed for the adaptive-bit quantized massive MIMO system. That is, two novel modules, i.e., an adaptive ADC bit allocation method and an MMSE-based VAMP, are proposed for mm Wave communications of the hybrid MIMO receiver architecture. With the MMSE-based VAMP, our adaptive ADC bit allocation method is able to decrease the quantization of signals distortion by improving the flexible resolutions of ADC. Through simulations, compared with existing works, our proposed adaptive ADC bit allocation algorithm, together with MMSE-based VAMP, is able to achieve higher capacity, sum rate, and energy efficiency in most communication architectures.

In today`s networks, middleboxes, typically deployed as standalone devices with no standardized access, play an important role in providing services such as firewalls and NATs as well as load balancing. These networks resort to Software-Defined Networking (SDN) for management that can provide a centralized, programmable environment to direct traffic through a desired service chain. However, even if the SDN Controller is able to determine the best path to a certain middlebox, not having prior knowledge of its policies may lead to traffic bottlenecks, degrading overall network performance. By jointly considering the characteristics of middleboxes and SDN, we design a Lightweight, cost-effective, and middlebox policy-aware routing method to address this challenge. That is, a middlebox-translator module is added to the SDN architecture to help middleboxes give the controller routing“hints” in the REST (Representational State Transfer) API format so that better routing decisions can be made. A performance study using emulations of Mininet, shows that, compared to existing methods, our middlebox-aware design results in better performance in SDN-enabled systems, e.g., greater network bandwidth savings in firewall systems, or reduced response time as well as higher throughput in load-balancing systems.

With the rapid development of V2X communications, how to guarantee per-vehicle rate and robustness of V2X communications has become important issue for the intelligent transportation systems. When there is distortion in CSI exchange under a real (e.g., noisy) environment, the performance of the precoder feedback method will seriously degrade due to transmission latency and quantization error. In this work, we propose Finsler manifolds codebook feedback scheme for V2X massive MIMO systems, where the vehicles exchange their CSI information via V2V communications, estimate the direction from a propagating wave in the precoder of antenna transceivers, and transmit their CSIs back to the Roadside Unit (RSU). That is, with the minimizing the iterative weighted minimum mean squared estimation (IWMMSE) of the received signals, we could cope with the optimization problem of the precoder feedback scheme on Finsler manifolds for maximizing the received signal power. Moreover, we are able to properly manage the optimal precoder bit allocation in mmWave massive MIMO systems. Simulation results show that, with the IWMMSE-based estimation, our Finsler manifolds codebook feedback scheme outperforms existing approaches in terms of per vehicle rate as well as the interference mitigation, i.e., our massive MIMO system could obtain higher adaptability and stability for V2X communications.

The work of cooperative perception realized by mmWave Vehicle to everything (V2X) [3] has pointed out that vehicles require much network bandwidth to exchange sensor information for safe automated driving; e.g., they require higher than 1Gbps V2V bandwidth to ensure safe velocity of 70 km/h. On the other hand, some research works have shown that channel state information (CSI) feedback is able to mitigate interference for 5G frequency division duplexing (FDD) mmWave massive MIMO systems. Existing approaches either do not consider the characteristics of FDD mmWave V2X systems or assume all channels are ideal, i.e., uncorrelated and identical. To achieve higher throughput and low overhead for FDD mmWave V2X systems, there are two major issues: (1) how to acquire an accurate CSI under the environment of non-identical channels, and (2) how to effectively use such information to improve overall system throughput. Our idea is to jointly consider the characteristics of the angle of arrival (AoA) method and K̈hler manifolds to design of codebook feedback approach for mmWave V2X massive systems. That is, to get an accurate CSI, we leverage the measurement method with the idea of the AoA approach. With this AoA measurement, we propose a novel K̈hler manifolds codebook feedback approach and determine an optimal bit allotment over each mmWave V2X link for achieving better interference reduction as well as lower overhead for V2X CSI exchange. In addition, our analytic results validate that proposed AoA K̈hler manifolds codebook feedback scheme is more adequate than the traditional CSI feedback with regard to interference reduction. Simulations show that the proposed AoA K̈hler manifolds codebook feedback scheme can significantly improve the vehicle rate and reduce the overhead for V2V CSI exchange.

The millimeter wave (mmWave) technology is considered as the potential candidate for high speed telecommunications service in 5G wireless communication, as it offers a ten times larger spectrum than existing cellular systems. The generalized spatial modulation (GenSM) aided millimeter wave multiple input multiple-output (mm-wave MIMO) concept have attracted substantial research interest, as it could lead to significant performance enhancement of mm-wave MIMO while maintaining the antennas with reduced number of active chains. However, current solvers either get stuck in a local minimum or have much computational complexity of GenSM-aided mm-wave MIMO schemes because the non-convex nature of the hybrid precoding design incurs significant performance degradation. To address this problem, we employ the Riemannian Optimization (RO) algorithms for the design of a hybrid precoder for GenSM-aided mm-wave MIMOs in order to enhance the spectral efficiency (SE). That is, we first re-design the hybrid precoding structures, i.e., by integrating the RF chain power constraints into the objective function; this allows the original optimized problem with constraints to be transformed into an unconstrained optimization problem on a nonlinear search space. Next, by considering the characteristics of a digital precoder, we are able to construct a proper manifold, in which we could effectively apply the RO iterative gradient descent method for computing a better solution. Our simulation results show that the proposed RO-based hybrid precoder is able to (a) outperform traditional GenSM-aided mm-wave MIMOs schemes, and (b) achieve comparable SE performance, when compared with modern mm-wave MIMO schemes.

Despite the promising potential of network risk management services (e.g., cyber-insurance) to improve information security, their deployment is relatively scarce, primarily due to such service companies being unable to guarantee profitability. As a novel approach to making cyber-insurance services more viable, we explore a symbiotic relationship between security vendors (e.g., Symantec) capable of price differentiating their clients, and cyber-insurance agencies having possession of information related to the security investments of their clients. The goal of this relationship is to (i) allow security vendors to price differentiate their clients based on security investment information from insurance agencies, (ii) allow the vendors to make more profit than in homogeneous pricing settings, and (iii) subsequently transfer some of the extra profit to cyber-insurance agencies to make insurance services more viable. In this paper, we perform a theoretical study of a market for differentiated security product pricing, primarily with a view to ensuring that security vendors (SVs) make more profit in the differentiated pricing case as compared to the case of non-differentiated pricing. In order to practically realize such pricing markets, we propose novel andcomputationally efficientconsumer differentiated pricing mechanisms for SVs based on (i) the market structure, (ii) the communication network structure of SV consumers captured via a consumer'sBonacich centralityin the network, and (iii) security investment amounts made by SV consumers. We validate our analytical model via extensive simulations conducted on practical SV client network topologies; main results show (through those simulations) that (a) amonopolySV could improve its profit margin by upto$\approx$25 percent (based on the simulation setting) by accounting for clients’ investment information and network locations, whereas in anoligopolysetting, SVs could improve their profit margins by upto$\approx$18 percent, and (b) differentiated security pricing mechanisms are fair among SV consumers with respect to the total investment made by a consumer. To the best of knowledge, the proposed differentiated pricing framework is the first of its kind in the security products domain, and is generally applicable to usecases beyond the one investigated in this work.

Running data-parallel jobs across geo-distributed sites has emerged as a promising direction due to the growing need for geo-distributed cluster deployment. A key difference between geo-distributed and intra-cluster jobs is the heterogeneous (and often constrained) nature of compute and network resources across the sites. We propose Tetrium, a system for multi-resource allocation in geo-distributed clusters, that jointly considers both compute and network resources for task placement and job scheduling. Tetrium significantly reduces job response time, while incorporating several other performance goals with simple control knobs. Our EC2 deployment and trace-driven simulations suggest that Tetrium improves the average job response time by up to 78% compared to existing data-locality-based solutions, and up to 55% compared to Iridium, the recently proposed geo-distributed analytics system.

The success of Deep Neural Networks (DNNs) has created significant interest in the development of software tools, hardware architectures, and cloud systems to meet the huge computational demand of their training jobs. A common approach to speeding up an individual job is to distribute training data and computation among multiple nodes, periodically exchanging intermediate results. In this paper, we address two important problems for the application of this strategy to large-scale clusters and multiple, heterogeneous jobs. First, we propose and validate a queueing model to estimate the throughput of a training job as a function of the number of nodes assigned to the job; this model targets asynchronous Stochastic Gradient Descent (SGD), a popular strategy for distributed training, and requires only data from quick, two-node profiling in addition to job characteristics (number of requested training epochs, mini-batch size, size of DNN parameters, assigned bandwidth). Throughput estimations are then used to explore several classes of scheduling heuristics to reduce response time in a scenario where heterogeneous jobs are continuously submitted to a large-scale cluster. These scheduling algorithms dynamically select which jobs to run and how many nodes to assign to each job, based on different trade-offs between service time reduction and efficiency (e.g., speedup per additional node). Heuristics are evaluated through extensive simulations of realistic DNN workloads, also investigating the effects of early termination, a common scenario for DNN training jobs.

Effective channel state information (CSI) feedback design is difficult for massive multiple-input multiple-output (MIMO) downlink transmissions in 5G frequency division duplexing (FDD) bands, where partial CSI could be directly exchanged between users through device-to-device (D2D) communications. In this work, we propose Direction of Arrival (DoA) adaptive codebook feedback, where the users exchange their CSI knowledge through D2D communications, estimate the precoder, and transmit it back to the base station (BS). That is, we first formulate an optimization problem of the feedback and precoding strategy on a Grassmann manifold. Using that, we are able to determine an optimal bit allocation of the precoder and the throughput of mmWave massive MIMO systems. Using simulations, we show that, compared with existing schemes, our proposed DoA adaptive codebook feedback scheme is able to achieve much higher throughput, and improve robustness and compatibility.

Small-scale clouds (SCs) often suffer from resource under-provisioning during peak demand, leading to inability to satisfy service level agreements (SLAs) and consequent loss of customers. One approach to address this problem is for a set of autonomous SCs to share resources among themselves in a cost-induced cooperative fashion, thereby increasing their individual capacities (when needed) without having to significantly invest in more resources. In this context, a central problem is how to properly share resources for a price in order to achieve profitable service, while maintaining customer SLAs. To address this problem, we propose the SC-Share framework that utilizes two interacting models: (i) a stochastic performance model that estimates the achieved performance characteristics under given SLA requirements, and (ii) a market-based game-theoretic model that (as shown empirically) converges to efficient resource sharing decisions at market equilibrium. Our results include extensive evaluations that illustrate the utility of the proposed framework.

Consistent (pause-free) quality of service is required in peer-to-peer (P2P) video streaming systems. In this paper, we aim to eliminate the problem of playback pauses in such systems via the use of positive incentives for peers to contribute high upload rates. We model our problem as a market, where the market stakeholders consist of multiple content providers, advertisement providers, and network peers; the positive incentives for peers in the market are reduced advertisement (ad) viewing durations. From a system design perspective, one of our primary goals is to compute the market equilibria that include appropriate ad viewing durations, offering sufficient incentives for network peers to continue contributing. Our simulation-based studies demonstrate that we mitigate the “playback pause” problem for peers by up to 80% as compared to existing approaches, generate sufficient utility for advertisers to be part of the market, and enable content providers to achieve their desired utility by providing sufficient incentives for all peers to stay in the system without violating ad provider agreements.

With growing data volumes generated and stored across geo-distributed datacenters, it is becoming increasingly inefficient to aggregate all data required for computation at a single datacenter. Instead, a recent trend is to distribute computation to take advantage of data locality, thus reducing the resource (e.g., bandwidth) costs while improving performance. In this trend, new challenges are emerging in job scheduling, which requires coordination among the datacenters as each job runs across geo-distributed sites. In this paper, we propose novel job scheduling algorithms that coordinate job scheduling across datacenters with low overhead, while achieving near-optimal performance. Our extensive simulation study with realistic job traces shows that the proposed scheduling algorithms result in up to 50% improvement in average job completion time over the Shortest Remaining Processing Time (SRPT) based approaches.

Inconsistent quality of service is a significant problem in P2P-based video streaming systems. Pauses in playback are common for low capacity peers as they often upload relatively little compared to high capacity peers, and thus suffer from the `lack of reciprocity' problem. In this work, we propose an Ad-driven Streaming P2p ECosysTem (ASPECT) that aims to eliminate the problem of playback pauses by adopting `reduced advertisement viewing duration' as a positive incentive for peers to provide high upload rates. ASPECT rewards high capacity peers by reducing their advertisement viewing duration, when they provide more opportunities for lower capacity peers to download data. We build our research problem on a utility-theoretic market-based model, where the market stakeholders consist of a content provider, an advertisement provider, and network peers. Using concepts from game theory, we determine the system parameters to reach market efficiency, and study the practical implications of equilibria on the satisfaction of stakeholders' interests. From a system design perspective, one of our primary goals is to compute the equilibria advertisement viewing durations, that offer sufficient incentives for network peers to continue contributing. We evaluate ASPECT through an extensive simulation-based study. The results demonstrate that ASPECT mitigates the `playback pause' problem for peers by at least 80% compared to existing approaches, results in appropriate advertisement viewing durations for all peers based on their contributions, and at the same time generates sufficient profit for the advertiser to be part of the market.

This special issue of Performance Evaluation contains the proceedings of the Performance 2015 conference, held in Sydney, Australia on October 19–21, 2015. Performance is the flagship conference of the IFIP Working Group 7.3 on Computer Performance Modeling and Analysis. [..]

This comment points out several mathematical errors in the proof of Therorem 3, and gives the correct expression of B3.

Recent work in security has illustrated that solutions aimed at detection and elimination of security threats alone are unlikely to result in a robust cyberspace. As an orthogonal approach to mitigating security problems, some have pursued the use of cyber-insurance as a suitable risk management technique. Such an approach has the potential to jointly align with the incentives of security vendors (e.g., Symantec, Microsoft, etc.), cyber-insurers (e.g., ISPs, cloud providers, security vendors, etc.), regulatory agencies (e.g., government), and network users (individuals and organizations), in turn paving the way for comprehensive and robust cyber-security mechanisms. To this end, in this work, we are motivated by the following important question: can cyber-insurance really improve the security in a network? To address this question, we adopt a market-based approach. Specifically, we analyze regulated monopolistic and competitive cyber-insurance markets, where the market elements consist of risk-averse cyber-insurers, risk-averse network users, a regulatory agency, and security vendors. Our results show that (i) without contract discrimination amongst users, there always exists a unique market equilibrium for both market types, but the equilibrium is inefficient and does not improve network security, and (ii) in monopoly markets, contract discrimination amongst users results in a unique market equilibrium that is efficient, which in turn results in network security improvement - however, the cyber-insurer can make zero expected profits. The latter fact is often sufficient to de-incentivize the insurer to be a part of a market, and will eventually lead to its collapse. This fact also emphasizes the need for designing mechanisms that incentivize the insurer to permanently be part of the market.

This paper considers a stochastic optimization approach for job scheduling and server management in large-scale, geographically distributed data centers. Randomly arriving jobs are routed to a choice of servers. The number of active servers depends on server activation decisions that are updated at a slow time scale, and the service rates of the servers are controlled by power scaling decisions that are made at a faster time scale. We develop a two-time-scale decision strategy that offers provable power cost and delay guarantees. The performance and robustness of the approach is illustrated through simulations.

Computing-as-a-service has been evolving steadily. Today, private clouds (e.g., Google's internal shared computing cluster) as well as public clouds (e.g., Amazon's web services (AWS), Microsoft's Azure) provide computing abstractions at various levels: bare virtual machines, specialized languages and runtimes (e.g., for massively-parallel data processing---MapReduce, Dryad), web services. For example, Amazon offers bare virtual machines as well as MapReduce clusters.

Frequently, ISPs charge for Internet use not based on peak bandwidth usage, but according to a percentile (often the 95th percentile) cost model. In other words, the time slots with the top 5 percent (in the case of 95th percentile) of data transmission volume do not affect the cost of transmission. Instead, we are charged based on the volume of traffic sent in the 95th percentile slot. In such an environment, by allowing a short delay in transmission of some data, we may be able to reduce our cost considerably. We provide an optimal solution to the offline version of this problem (in which the job arrivals are known), for any delay D > 0. The algorithm works for any choice of percentile. We also show that there is no efficient deterministic online algorithm for this problem. However, for a slightly different problem, where the maximum amount of data transmitted is used for cost accounting, we provide an online algorithm with a competitive ratio of 2D+1/D+1. Furthermore, we prove that no online algorithm can achieve a competitive ratio better than 2D+1/D+F(D) where F(D) = Σi=1D+1i/D+i for any D > 0 in an adversarial setting. We also provide a heuristic that can be used in an online setting where the network traffic has a strong correlation over consecutive accounting cycles, based on the solution to the offline percentile problem. Experimental results are used to illustrate the performance of the algorithms proposed in this work.

In Amazon's spot instance (SI) market, the volatility of the two important parameters, namely spot price (SP) and inter-price time (IPT), affects not only the market's profit, but also its service reliability. Thus, it is important for the cloud service provider to understand how SP and IPT impact the profit-reliability trade-off in the SI market. To the best of our knowledge, such a trade-off has not been studied in existing liter-ature. In this paper, we model Amazon's SI market as a modified repeated single-price auction and study the profit maximization problem using a graph model. We prove the NP-Completeness of the corresponding offline decision problem. Moreover, we propose an order-statistics based online pricing (OSOP) algorithm that can effectively evaluate and tune the profit-reliability trade-off by on-the-fly adapting SP and IPT. In our approach, SP and IPT are determined in real time based on the order statistics of the latest historical bids and the profit-reliability trade-off desired by the service providers. Our experiments show that the proposed OSOP mechanism (on average) achieves as high as ≈19% profit gain as compared to the current algorithm, with negligible reliability loss. Moreover, the mechanism also achieves a favorable trade-off between profit and service reliability, at which point our mechanism (on average) achieves ≈ 12% profit gain and ≈ 8% reduction in unexpected service interruption penalty as compared to the current algorithm.

Data centers are typically over-provisioned, in order to meet certain service level agreements (SLAs) under worst-case scenarios (e.g., peak loads). Selling unused instances at discounted prices thus is a reasonable approach for data center providers to off-set the maintenance and operation costs. Spot market models are widely used for pricing and allocating unused instances. In this paper, we focus on mechanism design for a data center spot market (DCSM). Particularly, we propose a mechanism based on a repeated uniform price auction, and prove its truthfulness. In the mechanism, to achieve better quality of service, the flexibility of adjusting bids during job execution is provided, and a bidding adjustment model is also discussed. Four metrics are used to evaluate the mechanism: in addition to the commonly used metrics in auction theory, namely, revenue, efficiency, slowdown and waste are defined to capture the Quality of Service (QoS) provided by DCSMs. We prove that a uniform price action achieves optimal efficiency among all single-price auctions in DCSMs. We also conduct comprehensive simulations to explore the performance of the resulting DCSM. The result show that (1) the bidding adjustment model helps increase the revenue by an average of 5%, and decrease the slowdown and waste by average of 5% and 6%, respectively, (2) our model with repeated uniform price auction outperforms the current Amazon Spot Market by an average of 14% in revenue, 24% in efficiency, 13% in slowdown, and by 14% in waste. Parameter tuning studies are also performed to refine the performance of our mechanism.

Network virtualization can potentially overcome Internet ossification. This technology lets multiple virtual networks run on a shared physical infrastructure. A key step lies in mapping a virtual network request to a resource allocation in the network substrate. Previous approaches to this network embedding problem assumed the request will ask for specific resources, such as network capacity or computing power. However, the end-user is more interested in performance. This paper therefore considers a different request format, namely a request will ask for a certain quality of service (QoS). The infrastructure provider must then determine the resource allocation necessary for this QoS. In particular, the provider must take into account user reaction to perceived performance and adjust the allocation dynamically. To this end, we propose an estimation mechanism that is based on analyzing the interaction between user behavior and network performance. This approach can dynamically adjust resource estimations when QoS requirements change. Our simulation-based experiments demonstrate that the proposed approach can satisfy user performance requirements through appropriate resource estimation. Moreover, our approach can adjust resource estimations efficiently and accurately.

In this work we focus on a stochastic optimization based approach to make distributed routing and server management decisions in the context of large-scale, geographically distributed data centers, which offers significant potential for exploring power cost reductions. Our approach considers such decisions at different time scales and offers provable power cost and delay characteristics. The utility of our approach and its robustness are also illustrated through simulation-based experiments under delay tolerant workloads.

Peer-to-Peer (P2P) streaming systems, such as PPLive, have become a popular service with the widespread deployment of broadband networks. However, P2P streaming systems still face free-riding problems, similar to those that have been observed in P2P file sharing systems. Thus, one important problem in providing streaming services is that of providing appropriate incentives for peers to contribute their upload capacity. To this end, we propose the use of advertisements as an incentive for peers to contribute upload capacity. In the proposed framework, peers enjoy the same quality of streamed media, with the difference in quality of service being achieved through different amounts of advertisements viewed, based on the resource contributions to the system. A simulation-based study is performed, which demonstrates that our approach provides appropriate incentives for peers to contribute their resources.

Stringent requirements on modern software systems dictate evaluation of dependability qualities, such as reliability, as early as possible in a system's life cycle. A primary shortcoming of the existing design-time reliability prediction approaches is their lack of support for modeling and analyzing concurrency in a scalable way. To address the scalability challenge, we propose SHARP, an architecture-level reliability prediction framework that analyzes a hierarchical scenario-based specification of system behavior. It achieves scalability by utilizing the scenario relations embodied in this hierarchy. SHARP first constructs and solves models of basic scenarios, and combines the obtained results based on the defined scenario dependencies; the dependencies we handle are sequential and parallel execution of multiple scenarios. This process iteratively continues through the scenario hierarchy until finally obtaining the system reliability estimate. Our evaluations performed on real-world specifications indicate that SHARP is (a) almost as accurate as a traditional non-hierarchical method, and (b) more scalable than other existing techniques.

We consider a peer-to-peer network where nodes can send and receive files amongst their peers. File requests are generated randomly, and each new file can correspond to a different subset of peers that already have the file and hence can assist in the download. Nodes that help others are rewarded by being able to download more. The goal is to design a control algorithm that allocates requests and schedules transmissions to maximize overall throughput-utility, subject to meeting “tit-for-tat” constraints that incentivize participation. Our algorithm is shown to operate efficiently on networks with arbitrary traffic and channel sample paths, including wireless networks whose capacity can be significantly extended by the peer-to-peer functionality.

The Web service (WS) paradigm is an emerging approach to building Web applications, in which software designers typically build new WSs by leveraging existing, third-party WSs. Understanding performance characteristics of third party WSs is critical to the overall system performance. Although such performance evaluation can be done through testing of third party WSs, it is quite an expensive process. This is especially the case when testing at high workloads, because performance degradations are likely to occur, which may render the WS under testing unusable during the tests' duration. Avoiding testing at high workloads by applying standard extrapolation approaches from data collected at low workloads (e.g., using regression analysis) results in a lack of accuracy. To address this challenge, in this paper, we propose a framework that utilizes the benefits of queueing models to guide the extrapolation process, while achieving accuracy in both regimes ¡V low and high workloads. Our extensive experiments show that our approach gives accurate results as compared to standard techniques (i.e., use of regression analysis alone).

With the development of innovative network infrastructure and increasing bandwidth availability, live video streaming is emerging as an attractive application for end users and the industry. Due to the heterogeneity in user resources as well as bandwidth fluctuations, we argue that, to provide high quality-of-service, it is desirable to tailor (on-the-fly) the bit rate of video streams, according to user download bandwidth availability. We believe that at least two benefits can be obtained by such an approach: (1) delay avoidance when a user's bandwidth drops below the (current) video playback rate; (2) provision of better quality of video streams, when a user's bandwidth increases, e.g., if a video stream with a matching bit rate is unavailable at the server. To this end, we propose a user-oriented video streaming system, uLive, that can on-the-fly adjust the streaming bit rate in order to match available user bandwidth. Our experimental results indicate that uLive is adaptive to user heterogeneity and robust to bandwidth fluctuations, with the goal of maximizing quality of the video received by the user.

Internet users such as individuals and organizations are subject to different types of epidemic risks such as worms, viruses, and botnets. To reduce the probability of risk, an Internet user generally invests in self-defense mechanisms like antivirus and antispam software. However, such software does not completely eliminate risk. Recent works have considered the problem of residual risk elimination by proposing the idea of cyber-insurance. In this regard, an important decision for Internet users is their amount of investment in self-defense mechanisms when insurance solutions are offered. In this paper, we investigate the problem of self-defense investments in the Internet, under full and partial cyber-insurance coverage models. By the term `self-defense investment', we mean the monetary-cum-precautionary cost that each user needs to invest in employing risk mitigating self-defense mechanisms, given that it is fully or partially insured by the Internet insurance agencies. We propose a general mathematical framework by which co-operative and non-co-operative Internet users can decide whether or not to invest in self-defense for ensuring both, individual and social welfare. Our results show that (1) co-operation amongst users results in more efficient self-defense investments than those in a non-cooperative setting, under a full insurance coverage model and (2) partial insurance coverage motivates non-cooperative Internet users to invest more efficiently in self-defense mechanisms when compared to full insurance coverage.

In recent years a number of research efforts have focused on effective use of P2P-based systems in providing large scale video streaming services. In particular, live streaming and Video-on-Demand (VoD) systems have attracted much interest. While previous efforts mainly focused on the common challenges faced by both types of applications, there are still a number of fundamental open questions in designing P2P-based VoD systems, which is the focus of our effort. Specifically, in this paper, we consider a BitTorrent-like VoD system and focus on the following questions: (1) how the lack of load balance, which typically exists in a P2P- based VoD system, affects the performance and what steps can be taken to remedy that, and (2) is a FCFS approach to serving requests at a peer sufficient or whether a Deadline-Aware Scheduling (DAS) approach can lead to performance improvements. Given the deadline considerations that exist in VoD systems, we also investigate approaches to avoiding unnecessary queueing time. For each of these questions, we first illustrate deficiencies of current approaches in adequately meeting streaming quality of service requirements. Motivated by this, we propose several practical schemes aimed at addressing these questions. To illustrate the benefits of our approach, we present an extensive simulation-based performance study.

Various sensor network measurement studies have reported instances of transient faults in sensor readings. In this work, we seek to answer a simple question: How often are such faults observed in real deployments? We focus on three types of transient faults, caused by faulty sensor readings that appear abnormal. To understand the prevalence of such faults, we first explore and characterize four qualitatively different classes of fault detection methods. Rule-based methods leverage domain knowledge to develop heuristic rules for detecting and identifying faults. Estimation methods predict “normal” sensor behavior by leveraging sensor correlations, flagging anomalous sensor readings as faults. Time-series-analysis-based methods start with an a priori model for sensor readings. A sensor measurement is compared against its predicted value computed using time series forecasting to determine if it is faulty. Learning-based methods infer a model for the “normal” sensor readings using training data, and then statistically detect and identify classes of faults. We find that these four classes of methods sit at different points on the accuracy/robustness spectrum. Rule-based methods can be highly accurate, but their accuracy depends critically on the choice of parameters. Learning methods can be cumbersome to train, but can accurately detect and classify faults. Estimation methods are accurate, but cannot classify faults. Time-series-analysis-based methods are more effective for detecting short duration faults than long duration ones, and incur more false positives than the other methods. We apply these techniques to four real-world sensor datasets and find that the prevalence of faults as well as their type varies with datasets. All four methods are qualitatively consistent in identifying sensor faults, lending credence to our observations. Our work is a first step towards automated online fault detection and classification.

Increasingly, peer-to-peer (P2P) network users expect to be able to search objects by semantic attributes based on their preferences for multimedia content. Partial match search (i.e., search through the use of multimedia content semantic information) has become an essential service in P2P systems. In this paper, we propose SocioNet, a social-based overlay that clusters peers based on their preference relationships as a small-world network. In SocioNet, peers mimic how people form a social network and how they query, by preference, their friends or acquaintances. Hence, SocioNet benefits from two desirable features of a social network: interest-based clustering and small-world properties (i.e., high cluster coefficient among all peers yet short path lengths between any two peers). To realize an interest-based small-world SocioNet, we also investigate the following practical design issues: 1) similarity estimation: we define a quantifiable similarity measure that enables clustering of similar peers in SocioNet; 2) distributed small-world overlay adaptation: peers maintain a small-world overlay under network dynamics; and 3) query strategy under the small-world overlay: we analyze appropriate settings for the Time-to-Live (TTL) value, for TTL-limited flooding, that provides a satisfactory success ratio and avoids redundant message overhead. We use simulations and a real database called AudioScrobbler [CHECK END OF SENTENCE], which tracks users' listening habits, to evaluate the performance of SocioNet. The results show that SocioNet assists peers in locating content at peers with similar interests through short path lengths, and hence, achieves a higher success ratio (than nonsmall-world interest-based overlays and noninterest-based small-world overlays) while reducing message overhead significantly.

Peer-to-peer (P2P) systems in general, and BitTorrent (BT) specifically, have been of significant interest to researchers and Internet users alike. Existing models of BT abstract away certain characteristics of the protocol that are important, which we address in this work. We present a simple yet accurate and easily extensible model of BT. The model's accuracy is validated through a rigorous simulation-based study and its extensibility is illustrated by incorporating recently proposed approaches to protocol changes in BT.

We consider the following basic question: a source node wishes to stream an ordered sequence of packets to a collection of receivers, which are distributed among a number of clusters. A node may send a packet to another node in its own cluster in one time step, whereas sending a packet to a node in a different cluster takes longer than one time step. Each cluster has two special nodes. We assume that the source and the special nodes in each cluster have a higher capacity and thus can send multiple packets at each step, while all other nodes can both send and receive a packet at each step. We construct two (intra-cluster) data communication schemes, one based on multi-trees (using a collection of interior-disjoint trees) and the other based on hypercubes. We use these approaches to explore the resulting playback delay, buffer space, and communication requirements.

We study an optimization problem that arises in the context of data placement in a multimedia storage system. We are given a collection of M multimedia objects (data objects) that need to be assigned to a storage system consisting of N disks d 1 , d 2 …, d N . We are also given sets U 1 , U 2 ,…, U M such that U i is the set of clients seeking the i th data object. Each disk d j is characterized by two parameters, namely, its storage capacity C j which indicates the maximum number of data objects that may be assigned to it, and a load capacity L j which indicates the maximum number of clients that it can serve. The goal is to find a placement of data objects to disks and an assignment of clients to disks so as to maximize the total number of clients served, subject to the capacity constraints of the storage system. We study this data placement problem for two natural classes of storage systems, namely, homogeneous and uniform ratio . We show that an algorithm developed by Shachnai and Tamir [2000a] for data placement achieves the best possible absolute bound regarding the number of clients that can always be satisfied. We also show how to implement the algorithm so that it has a running time of O (( N + M ) log( N + M )). In addition, we design a polynomial-time approximation scheme, solving an open problem posed in the same paper.

The ability to predict the reliability of a software system early in its development, e.g., during architectural design, can help to improve the system's quality in a cost-effective manner. Existing architecture-level reliability prediction approaches focus on system-level reliability and assume that the reliabilities of individual components are known. In general, this assumption is unreasonable, making component reliability prediction an important missing ingredient in the current literature. Early prediction of component reliability is a challenging problem because of many uncertainties associated with components under development. In this paper we address these challenges in developing a software component reliability prediction framework. We do this by exploiting architectural models and associated analysis techniques, stochastic modeling approaches, and information sources available early in the development lifecycle. We extensively evaluate our framework to illustrate its utility as an early reliability prediction approach.

Assessing reliability at early stages of software development, such as at the level of software architecture, is desirable and can provide a cost-effective way of improving a software system's quality. However, predicting a component's reliability at the architectural level is challenging because of uncertainties associated with the system and its individual components due to the lack of information. This paper discusses representative uncertainties which we have identified at the level of a system's components, and illustrates how to represent them in our reliability modeling framework. Our preliminary evaluation indicates promising results in our framework's ability to handle such uncertainties.

1 Introduction The “How much information?” study produced by the school of information management and systems at the University of California at Berkeley [10], estimates that about 5 exabytes of new information was produced in 2002. It estimates that the amount of stored information doubled in the period between 1999 and 2002. It is believed that more data will be created in the next five years than in the history of the world. Clearly we live in an era of data explosion. This data explosion necessitates the use of large storage systems. Storage Area Networks (or SANs) are the leading [13] infrastructure for enterprise storage.

Software reliability techniques are aimed at reducing or eliminat-ing failures in software systems. Reliability in software systems istypically measured during or after system implementation. How-ever, software engineering methodology lays stress on doing the"correct things" early on in the software development lifecycle inorder to curb development and maintenance costs. In this paper, wepropose a framework for reliability estimation of software compo-nents at the level of software architecture.

Software reliability techniques are aimed at reducing or eliminating failures in software systems. Reliability in software systems has traditionally been measured during or after system implementation. However, software engineering methodology lays stress on doing the "correct things" early on in the software development lifecycle in order to curb development and maintenance costs. In this paper, we argue that reliability of a software system should be assessed throughout the system's life span, starting with the software architecture level. Our research goal is to estimate the reliability of software systems in early design stages, which we believe involves the ability to reason about numerous uncertainties that exist in this stage, including uncertainty due to lack of execution artifacts. Our proposed approach is to develop techniques that will couple software architectural models with a suite of stochastic reliability estimation models and allow us to reason about these uncertainties. In this paper, we present our recent results using our technique for reliability estimation of software components at the level of software architecture. Another important part of this paper is the discussion of our ongoing research efforts and open research problems in this area.

We consider the problem of collecting a large amount of data from several different hosts to a single destination in a wide-area network. This problem is important since improvements in data collection times in many applications such as wide-area upload applications, high-performance computing applications, and data mining applications are crucial to performance of those applications. Often, due to congestion conditions, the paths chosen by the network may have poor throughput. By choosing an alternate route at the application level, we may be able to obtain substantially faster completion time. This data collection problem is a nontrivial one because the issue is not only to avoid congested link(s), but to devise a coordinated transfer schedule which would afford maximum possible utilization of available network resources. Our approach for computing coordinated data collection schedules makes no assumptions about knowledge of the topology of the network or the capacity available on individual links of the network. This approach provides significant performance improvements under various degrees and types of network congestions. To show this, we give a comprehensive comparison study of the various approaches to the data collection problem which considers performance, robustness, and adaptation characteristics of the different data collection methods. The adaptation to network conditions characteristics are important as the above applications are long lasting, i.e., it is likely changes in network conditions will occur during the data transfer process. In general, our approach can be used for solving arbitrary data movement problems over the Internet. We use the Bistro platform to illustrate one application of our techniques.

In this paper we consider the problem of collecting a large amount of data from several different hosts to a single destination in a wide-area network. Often, due to congestion conditions, the paths chosen by the network may have poor throughput. By choosing an alternate route at the application level, we may be able to obtain substantially faster completion time. This data collection problem is a nontrivial one because the issue is not only to avoid congested link(s), but to devise a coordinated transfer schedule which would afford maximum possible utilization of available network resources. In this paper we present an approach for computing coordinated data collection schedules, which can result in significant performance improvements. We make no assumptions about knowledge of the topology of the network or the capacity available on individual links of the network, i.e., we only use end-to-end information. Finally, we also study the shortcomings of this approach in terms of the gap between the theoretical formulation and the resulting data transfers in wide-area networks. In general, our approach can be used for solving arbitrary data movement problems over the Internet. We use the Bistro platform to illustrate one application of our techniques.

Gesture recognition techniques often suffer from being highly device-dependent and hard to extend. If a system is trained using data from a specific glove input device, that system is typically unusable with any other input device. The set of gestures that a system is trained to recognize is typically not extensible, without retraining the entire system. We propose a novel gesture recognition framework to address these problems. This framework is based on a multi-layered view of gesture recognition. Only the lowest layer is device dependent, it converts raw sensor values produced by the glove to a glove-independent semantic description of the hand. The higher layers of our framework can be reused across gloves, and are easily extensible to include new gestures. We have experimentally evaluated our framework and found that it yields comparable performance to conventional techniques, while substantiating our claims of device independence and extensibility.

Considers a K-server threshold-based queuing system with hysteresis in which the number of active servers is governed by a forward threshold vector F = (F/sub 1/, F/sub 2/, ..., F/sub K-1/), where F/sub 1/<F/sub 2/</spl middot//spl middot//spl middot/<F/sub K-1/, and a reverse threshold vector R = (R/sub 1/, R/sub 2/, ..., R/sub K-1/), where R/sub 1/<R/sub 2/</spl middot//spl middot//spl middot/

In designing cost-effective video-on-demand (VOD) servers, efficient resource management and proper system sizing are of great importance. In addition to large storage and I/O bandwidth requirements, support of interactive VCR functionality imposes additional resource requirements on the VOD system in terms of storage space, as well as disk and network bandwidth. Previous works have used data sharing techniques (such as batching, buffering, and adaptive piggybacking) to reduce the I/O demand on the storage server. However, such data sharing techniques complicate the provision of VCR functions and diminish the amount of benefit that can be obtained from data sharing techniques. The main contribution of this paper is a simple, yet powerful, analytical modeling approach which allows for analysis, system sizing, resource allocation, and parameter setting for a fairly general class of data sharing techniques which are used in conjunction with the providing of VCR-type functionality. Using this mathematical model, we can determine the proper amount of resources to be allocated for normal playback as well as for service of VCR functionality requests while satisfying predefined system performance requirements. To illustrate the usefulness of our model, we focus on a specific data sharing scheme which combines the use of batching, buffering, and adaptive piggybacking, as well as allows for the use of VCR functions. We show how to utilize this mathematical model for system sizing and resource allocation purposes.

Recent technological advances in digital signal processing, data compression techniques, and high-speed communication networks have made Video-on-Demand (VOD) servers feasible. A challenging task in such systems is servicing multiple clients simultaneously while satisfying real-time requirements of continuous delivery of objects at specified rates. To accomplish these tasks and realize economies of scale associated with servicing a large user population, a VOD server requires a large disk subsystem. Although a single disk is fairly reliable, a large disk farm can have an unacceptably high probability of disk failure. Furthermore, due to real-time constraints, the reliability requirements of VOD systems are even more stringent than those of traditional information systems. Traditional RAID solutions are inadequate due to poor resource usage. Thus, in this paper, we present alternative schemes which provide a high degree of reliability at low disk storage, bandwidth, and memory costs for on-demand multimedia servers. Moreover, we discuss some of the main issues and trade-offs associated with providing fault tolerance in multidisk VOD systems. We would like to impress upon the reader that one of the main points of this paper is the exposition of trade-offs and issues associated with designing fault-tolerant VOD servers. It is not the case that one fault tolerance scheme is absolutely better than another, but rather that one must understand the trade-offs as well as one's system constraints and then choose a fault tolerance scheme accordingly.

Multimedia applications place high demands for QoS, performance, and reliability on storage servers and communication networks. These, often stringent requirements, make design of cost-effective and scalable continuous media (CM) servers difficult. In particular, the choice of data placement techniques can have a significant effect on the scalability of the CM server and its ability to utilize resources efficiently. In the recent past, a great deal of work has focused on "wide" data striping. Another approach to dealing with load imbalance problems is replication. The appropriate compromise between the degree of striping and the degree of replication is key do the design of scalable CM servers. Thus, the main focus of the paper is a study of scalability characteristics of CM servers as a function of tradeoffs between striping and replication.

The stringent requirements of multimedia applications make design of cost-effective and scalable systems difficult; thus, efficient adaptive and dynamic resource management techniques can be of great help in improving performance and scalability characteristics of such systems. In this paper we focus on threshold-based policies for dynamic resource management in the context of continuous media (CM) servers; we do this without any knowledge of data access patterns and with provisions for full use of VCR functionality. We propose a mathematical model of user behavior and show through a performance study, that not only does the use of this model in conjunction with dynamic resource management policies improves the system's performance but that it also facilitates significantly reduced sensitivity to changes in: (a) system architecture, (b) workload characteristics, (c) skewness of data access patterns, (d) frequency of changes in data access patterns, and (e) choice of threshold values. We believe that not only is this a desirable property for a CM server, in general, but that furthermore, it suggests the usefulness of these techniques across a wide range of continuous media applications.

Our main goal in this work is to develop an efficient method for solving such models and computing the corresponding performance measures of interest, which can subsequently be used in evaluating designs of threshold-based systems.

There have been many proposals on how media-on-demand servers can effectively allow clients to share resources. In this paper, given a set of clients, we show how these clients may be partitioned into "sync-classes" sets of clients who can be serviced through allocation of a single set of resources. As a set of clients may be partitioned into sync-classes in many different ways, we show that a very large class of cost functions may be used to determine which partition to choose. We provide algorithms to compute such optimal splits. Our framework is very generic in the following ways: the system may plug-in any cost function whatsoever, as long as it satisfies four common-sense axioms that evaluate costs; and the system may evaluate the future anticipated requests of a user using any user model (e.g., a Markovian model) that has a specified I/O interface. Thus, a wide variety of predictive methods (of what the user will do) and a wide variety of costing methods may be used within our framework.

Presents a performance-based methodology for designing a high-bandwidth radar application on commodity platforms. Unlike many real-time systems, our approach works for commodity processors running commodity operating systems. Our technique is innovative because it uses stochastic models of the processing time at each step in the process to allow for the variabilities of running on a non-real-time operating system. We show how our system synthesizes the runtime parameters for a synthetic aperture radar application under a variety of loading conditions.

No abstract available.

Recent technological advances in digital signal processing, data compression techniques, and high speed communication networks have made distributed multimedia information systems feasible.Already, multimedia systems play a major role in educational applications, entertainment technology, and library information systems.Designing and developing multimedia information systems involves a multitude of aspects including: acquisition, compression, storage, access, presentation, and communication.The papers collected in this issue address some of these topics, namely: storage, authoring and presentation, and communication and supporting operating systems.Before introducing these papers, we briefly discuss trends in multimedia systems as well as characteristics of multimedia applications.The main characteristics of multimedia applications that lead to difficulties Ž .Ž .and challenges in efficient design of a storage systems, b authoring systems, Ž .Ž .c communication protocols, and d the corresponding operating system sup-Ž .Ž .port are that they have 1 large bandwidth and storage requirements, 2 low Ž .communication latency requirements, and 3 synchronization requirements of various multimedia sources, all of which are often coupled with real-time constraints.Furthermore, in designing and building large high performance multimedia storage and communication systems, one must consider a whole spectrum of applications, from relatively low bandwidth, high throughput, and ''just-in-time'' delivery of video-on-demand servers to very high bandwidth, relatively low volume, and ''ASAP'' delivery of supercomputing᎐scientific applications.Thus, such systems must be able to accommodate the various storage, performance, and reliability requirements of the different types of media and applications.Efficient use of resources and proper design choices are key to achieving high performability and low cost multimedia information systems.Below, we briefly discuss some of these issues and tradeoffs in more detail, particularly those pertaining to the topics of the papers included in this issue. Ž.

To design a cost effective VOD server, it is important to carefully manage the system resources so that the number of concurrent viewers can be maximized. Previous research results use data sharing techniques, such as batching, buffering, and piggybacking, to reduce the demand for I/O resources In a VOD system. However, these techniques still suffer from the problem that additional I/O resources are needed in the system for providing VCR functionality-without careful resource management, the benefits of these data sharing techniques can be lost. In this paper, we first introduce a model for determining the amount of resources required for supporting both normal playback and VCR functionality to satisfy predefined performance characteristics. Consequently, this model allows us to maximize the benefits of data sharing techniques. Furthermore, one important application of this model is its use in making system sizing decisions. Proper system sizing will result in a more cost-effective VOD system.

AbstractÐIn this paper, we consider a K-server threshold-based queuing system with hysteresis in which the number of active servers is governed by a forward threshold vector F ˆ…F1;F2;...;FK 1 † (where F1 <F2 < <FK 1) and a reverse threshold vector R ˆ…R1;R2;...;RK 1 † (where R1 <R2 <

Recent technological advances have made multimedia on-demand services, such as home entertainment and home-shopping, important to the consumer market. One of the most challenging aspects of this type of service is providing access either instantaneously or within a small and reasonable latency upon request. In this paper, we discuss a novel approach, termed adaptive piggybacking, which can be used to provide on-demand or nearly-on-demand service and at the same time reduce the I/O demand on the multimedia storage server.

Recent technological advances have made multimedia on-demand servers feasible. Two challenging tasks in such systems are: a) satisfying the real-time requirement for continuous delivery of objects at specified bandwidths and b) efficiently servicing multiple clients simultaneously. To accomplish these tasks and realize economies of scale associated with servicing a large user population, the multimedia server can require a large disk subsystem. Although a single disk is fairly reliable, a large disk farm can have an unacceptably high probability of disk failure. Further, due to the real-time constraint, the reliability and availability requirements of multimedia systems are very stringent. In this paper we investigate techniques for providing a high degree of reliability and availability, at low disk storage, bandwidth, and memory costs for on-demand multimedia servers. 1 Introduction Recent technological advances in digital signal processing, data compression techniques, and high spe...

Allocation and reallocation techniques for resources in a distributed database (DDB) system are discussed. An abstract model of the DDB, which partitions data among a set of nodes in a network, is presented. Initial resource allocation and demand driven borrowing policies are investigated using the model. It is shown that a single token borrowing policy which attempts to correct the greatest waste of resources in the system, achieves a cost within several percent of the unachievable lower bound, and multiple token borrowing polices, which anticipate future need and keep the system balanced with respect to the remaining number of tokens, perform much better than those that only borrow the needed amount.>