Information security is of paramount importance in this digital era. While businesses strive to adopt industry-accepted system-hardening standards such as benchmarks recommended by the Center for Internet Security (CIS) to combat threats, they are confronted with an additional challenge of ever-evolving regulations that address security concerns. These create additional requirements, which must be incorporated into software systems. In this paper, we present a generic approach towards automating different activities of the Security Compliance Value Chain (SCVC) in organizations. We discuss the approach in the context of the Payment Card Industry Data Security Standard (PCI-DSS) regulations. Specifically, we present automation of (1) interpretation of PCI-DSS regulations to infer system requirements, (2) traceability of the inferred system requirements to CIS security controls (3) implementation of appropriate security controls, and finally, (4) verification and reporting of compliance.

Modern day enterprises have a large IT infrastructure comprising thousands of applications running on servers housed in tens of data centers geographically spread out. These enterprises periodically perform a transformation of their entire IT infrastructure to simplify, decrease operational costs and enable easier management. However, the large number of different kinds of applications and data centers involved and the variety of constraints make the task of data center transformation challenging. The state-of-the-art technique for performing this transformation is simplistic, often unable to account for all but the simplest of constraints. We present eTransform, a system for generating a transformation and consolidation plan for the IT infrastructure of large scale enterprises. We devise a linear programming based approach that simultaneously optimizes all the costs involved in enterprise data centers taking into account the constraints of applications groups. Our algorithm handles the various idiosyncrasies of enterprise data centers like volume discounts in pricing, wide-area network costs, traffic matrices, latency constraints, distribution of users accessing the data etc. We include a disaster recovery (DR) plan, so that eTransform, thus provides an integrated disaster recovery and consolidation plan to transform the enterprise IT infrastructure. We use eTransform to perform case studies based on real data from three different large scale enterprises. In our experiments, eTransform is able to suggest a plan to reduce the operational costs by more than 50% from the "as-is" state of these enterprise to the consolidated enterprise IT environment. Even including the DR capability, eTransform is still able to reduce the operational costs by more than 25% from the simple "as-is" state. In our experiments, eTransform is able to simultaneously optimize multiple parameters and constraints and discover solutions that are 7x cheaper than other solutions.

The rising complexity of distributed server applications in Internet data centers has made the tasks of modeling and analyzing their behavior increasingly difficult. This article presents Modellus , a novel system for automated modeling of complex web-based data center applications using methods from queuing theory, data mining, and machine learning. Modellus uses queuing theory and statistical methods to automatically derive models to predict the resource usage of an application and the workload it triggers; these models can be composed to capture multiple dependencies between interacting applications. Model accuracy is maintained by fast, distributed testing, automated relearning of models when they change, and methods to bound prediction errors in composite models. We have implemented a prototype of Modellus, deployed it on a data center testbed, and evaluated its efficacy for modeling and analysis of several distributed multitier web applications. Our results show that this feature-based modeling technique is able to make predictions across several data center tiers, and maintain predictive accuracy (typically 95% or better) in the face of significant shifts in workload composition; we also demonstrate practical applications of the Modellus system to prediction and provisioning of real-world data center applications.

Multicast is attracting a resurgence of interest because it has a potential to address the explosively growing need for efficient streaming of large-volume Internet content. However, to realize the potential, large-scale multicast distribution requires effective congestion control. In this paper, we design SIM, a protocol that combines three distinct mechanisms (Selective participation, Intra-group transmission adjustment, and Menu adaptation) to provide a general solution for efficient fair scalable privacy-preserving multicast congestion control with heterogeneous receivers. Whereas the individual mechanisms have appeared in earlier multicast protocols, our main contribution lies in the cohesive integration of the techniques. SIM achieves such integration by operating the three mechanisms at different timescales and distributing the responsibility for control to different entities in the network. Besides, to instantiate and integrate the three control mechanisms, SIM employs several novel techniques of independent interest. Our extensive evaluation confirms the salient properties of SIM in diverse settings where receiving capabilities are highly heterogeneous, bottleneck capacities fluctuate, bottlenecks migrate, and session membership is dynamic.

Sophisticated middlebox services-such as network monitoring and intrusion detection, DDoS mitigation, worm scanning, XML parsing and protocol transformation-are becoming increasingly popular in today's Internet. To support high- throughput, these services are often deployed on distributed memory, multi-processor (DM-MP) hardware platforms such as a cluster of network processors. Scaling the throughput of such platforms, however, is challenging because of the difficulties and overheads of accessing persistent, shared state maintained by the services. In this paper, we describe the design and implementation of Oboe, a run-time system for DM-MP platforms that addresses the above challenge through two foundations: (1) category-specific management of shared state, and (2) adaptive flow- level load distribution for addressing persistent processor overload. Our simulations demonstrate that Oboe can achieve performance within 0-5% of an ideal adaptive system. Our prototype implementation of Oboe on a cluster of IXP2400 network processors, demonstrates the scalability achieved with increasing number of processors, number of flows and state size.

The emergence of multi -processor, multi-threaded architectures (referred to as multi-* architectures) facilitates the design of high-throughput request processing systems (e.g., multiservice routers for GENI, intrusion detection systems, graphics and gaming systems, as well as high-throughput web servers and transaction processing systems). Because of the challenges in programming such architectures, realizing this promise has proved to be difficult. In this paper, we describe the design of Lagniappe, a programming environment that simplifies the design of portable, high-throughput applications on multi-* architectures. Lagniappe uses a hybrid programming model: it combines a procedural specification (e.g., in C++) of the basic operators for processing requests with a declarative specification - expressed using a model-driven development framework - of the various features of the operators and the target hardware platform. Using the declarative specification, the Lagniappe programming environment automates the mapping of applications onto the multi-* platform, performs dynamic allocation of resources to operators, and ensures efficient and coherent accesses to persistent, shared state.

Certain emerging network applications involve dynamically allocating shared resources to a variety of services to provide QoS guarantees for each service. Motivated by such applications, we address the following online scheduling problem belonging to the recently introduced class of reconfigurable resource scheduling problems: unit jobs of different categories arrive over time and need to be completed within category-specific delay bounds, or else they are dropped at a unit drop cost; processors can be reconfigured to process jobs of a certain category at a fixed reconfiguration cost; the goal is to minimize the total cost. We study this problem in the framework of competitive analysis. Through a novel combination of the EDF and LRU scheduling principles, we obtain an online algorithm that is constant competitive when given a constant factor resource advantage over an optimal offline algorithm.

Challenges in addressing the memory bottleneck have made it difficult to design a packet processing platform that simultaneously achieves both ease-of-programming and high performance. Today's commercial processors support two architectural mechanisms - namely, hardware multithreading and caching - to overcome the memory bottleneck. The configurations of these mechanisms (e.g., cache capacity, number of threads per processor core) are fixed at processor-design time. The relative effectiveness of these mechanisms, however, varies significantly with application, traffic, and system characteristics. Thus, programmers often struggle to achieve high performance from a processor that is not well-suited to a particular deployment.

In this paper, we describe the design and evaluation of a scheduler (referred to as Everest) for allocating processors to services in high performance, multi-service routers. A scheduler for such routers is required to maximize the number of packets processed within a given delay tolerance, while isolating the performance of services from each other. The design of such a scheduler is novel and challenging because of three domain-specific characteristics: (1) difficult-to-predict and high packet arrival rates, (2) small delay tolerances of packets, and (3) significant overheads for switching allocation of processors from one service to another. These characteristics require that the scheduler be agile and wary simultaneously. Whereas agility enables the scheduler to react quickly to fluctuations in packet arrival rates, wariness prevents the scheduler from wasting computational resources in unnecessary context switches. We demonstrate that by balancing agility and wariness, Everest, as compared to conventional schedulers, reduces by more than an order of magnitude the average delay and the percentage of packets that experience delays greater than their tolerance. We describe a prototype implementation of Everest on Intel's IXP2400 network processor

We consider a class of scheduling problems that we refer to as reconfigurable resource scheduling. This class of problems is motivated by emerging applications that involve dynamically allocating a large number of shared resources to a variety of services. We design efficient online algorithms for certain problems in this class. Our goal is to obtain constant competitive online algorithms where the online algorithm is given a constant factor advantage in terms of the number of resources. The main problem considered in this paper is as follows. The input is a sequence of requests, each of which is a set of unit jobs. Each job has a category, and needs to be processed within a fixed delay bound from its arrival, or else it is dropped and we incur a category-specific drop cost. A job of a given category can only be executed on a resource configured for that category. A resource can be reconfigured at any time at a fixed reconfiguration cost. Our main result is a constant competitive online algorithm for this problem, which is obtained by the following layered approach. First, we reduce our main problem to the special case in which all jobs arrive at integral multiples of the delay bound. Second, we reduce the latter problem to the special case of unit delay. Third, we reduce the unit-delay problem to a caching problem that we refer to as file caching with remote reads. Our solution to this caching problem generalizes certain existing work in the area of file caching.

Overhead of memory accesses limits the performance of packet processing applications. To overcome this bottleneck, today's network processors can utilize a wide-range of mechanisms-such as multi-level memory hierarchy, wide-word accesses, special-purpose result-caches, asynchronous memory, and hardware multi-threading. However, supporting all of these mechanisms complicates programmability and hardware design, and wastes systemresources. In this paper, we address the following fundamental question: what minimal set of hardware mechanisms must a network processor support to achieve the twin goals of simplified programmability and high packet throughput? We show that no single mechanism sufficies; the minimal set must include data-caches and multi-threading. Data-caches and multi-threading are complementary; whereas data-caches exploit locality to reduce the number of context-switches and the off-chip memory bandwidth requirement, multi-threading exploits parallelism to hide long cache-miss latencies.

No abstract available.

In this study, we refute the popular belief [1,2] that packet processing does not benefit from data-caching. We show that a small data-cache of 8KB can bring down the packet processing time by much as 50-90%, while reducing the off-chip memory bandwidth usage by about 60-95%. We also show that, unlike general-purpose computing, packet processing, due to its memory-intensive nature, cannot rely exclusively on data-caching to eliminate the memory bottleneck completely.

The Java programming language was designed for portability and safe code distribution, not for fault-tolerance. We modify the Sun JDK1.2 to provide transparent fault-tolerance for many Java applications under the crash failure model. Our approach is to log non-deterministic events at the JVM interface using a primary-backup architecture. In particular, we identify the sources of non-determinism in the JVM due to asynchronous exceptions and multi-threaded access to shared data, as well as the non-determinism present at the native method interface. We analyze the overhead introduced in our system by each of these sources of non-determinism and compare the performance of dierent techniques for handling multi-threading.

End-to-end throughput guarantee is an important service semantics that network providers would like to offer to their customers. A network provider can offer such service semantics by deploying a network where each router employs a fair packet scheduling algorithm. Unfortunately, these scheduling algorithms require every router to maintain per-flow state and perform per-packet flow classification; these requirements limit the scalability of the routers. In this paper, we propose the Core-stateless Guaranteed Throughput (CSGT) network architecture-the first work-conserving architecture that, without maintaining per-flow state or performing per-packet flow classification in core routers, provides to flows throughput guarantees that are within an additive constant of what is attained by a network of core-stateful fair routers.

Group subscription is a useful mechanism for multicast congestion control: RLM, RLC, FLID-DL, and WEBRC form a promising line of multi-group protocols where receivers provide no feedback to the sender but control congestion via group membership regulation. Unfortunately, the group subscription mechanism also o#ers receivers an opportunity to elicit self-beneficial bandwidth allocations. In particular, a misbehaving receiver can ignore guidelines for group subscription and choose an unfairly high subscription level in a multi-group multicast session. This poses a serious threat to fairness of bandwidth allocation. In this paper, we present the first solution for the problem of inflated subscription. Our design guards access to multicast groups with dynamic keys and consists of two independent components: DELTA (Distribution of ELigibility To Access) -- a novel method for in-band distribution of group keys to receivers that are eligible to access the groups according to the congestion control protocol, and SIGMA (Secure Internet Group Management Architecture) -- a generic architecture for key-based group access at edge routers.

No abstract available.

We present half-pipe anchoring, a technique that enables multiple connection handoff mechanisms that are efficient and easy to implement. In a server cluster, these mechanisms result in better resource utilization and improved scalability. More importantly, half-pipe anchoring supports the only connection handoff mechanism that operates efficiently in heterogeneous clusters composed of specialized nodes. The key idea behind our approach is to decouple the two unidirectional half-pipes that make up a TCP connection between a client and a cluster. We anchor the unidirectional half-pipe from the client to the cluster at a designated server while allowing the half-pipe from the cluster to the client to migrate on a per-request basis to an optimal server where the request is best serviced We describe the design and implementation of a multiple connection handoff mechanism in the Linux kernel that demonstrates the benefits of our technique.

In this paper, we present the first end-to-end fairness analysis of a network of fair servers. We argue that it is difficult to extend existing single-node fairness analysis to an end-to-end analysis of a network where each node may employ a different fair scheduling algorithm. We then present a two-step approach for end-to-end fairness analysis of heterogeneous networks. First, we define a class of scheduling algorithms, referred to as the fair throughput (FT) class, and prove that most known fair scheduling algorithms belong to this class. Second, we develop an analysis methodology for deriving the end-to-end fairness bounds for a network of FT servers. Our analysis is general and can be applied to heterogeneous networks where different nodes employ different scheduling algorithms from the FT class.

The objective of this project is to design a domain-independent framework that allows rapid development of applications customized for specific user needs. We see three major components in the design: (1) persistent storage management, (2) computational logic and execution environment, and (3) methods for orchestrating computations. Recent developments in industry and academia have made available solutions for persistent storage management and distributed execution of computational tasks (e.g., the .NET and the Websphere infrastructures). This project builds upon these efforts; it permits the specification and instantiation of scripts for orchestrating the execution of several computational tasks. The orchestration script specifies what computations to perform and when; but no information on how to perform the computations.

Many per-flow scheduling algorithms have been proposed to provide rate and delay guarantees to flows. It is often argued that the need for maintaining per-flow state and performing per-packet classification seriously limits the scalability of routers that employ such per-flow scheduling algorithms. Consequently, design of algorithms that can provide per-flow rate and delay guarantees without requiring per-flow functionality in the network core routers has become an active area of research. We propose a methodology to transform any guaranteed rate (GR) per-flow scheduling algorithm into a version that does not require per-flow state to be maintained in the core routers. We prove that a network of such core-stateless servers provides the same delay guarantee as a corresponding network of GR servers.

Abstract — Layered multicast is a common approach for dissemination of audio and video in heterogeneous network environments. Layered multicast schemes can be classified into two categories – feedback-based and feedback-free – depending on whether or not the scheme delivers feedback to the sender of the multicast session. Advocates of feedback-based schemes claim that the feedback is necessary to match the heterogeneous receiver capabilities efficiently. Supporters of feedbackfree schemes believe that feedback introduces significant complexity and that a moderate amount of additional layers can balance any benefit the feedback provides. Surprisingly, there has been no systematic evaluation of these claims. This paper compares feedback-based and feedback-free schemes quantitatively with respect to their abilities to align the provided service to the capabilities of the heterogeneous receivers. We believe that such an evaluation supplies valuable insights and guidelines to the designers of future multicast congestion control protocols. 1

We believe that a network, to be survivable, must be heterogeneous. Just like a species that draws on a small gene pool can succumb to a single environmental threat, so a homogeneous network is vulnerable to a malicious attack that exploits a single weakness common to all of its components. In contrast, in a network in which each critical functionality is provided by a diverse set of protocols and implementations, attacks that focus on a weakness of one such protocol or implementation will not be able to bring down the entire network, even though all elements are not be bulletproof and even if some of components are compromised.Following this survivability through heterogeneity philosophy, we propose a new survivability paradigm, called heterogeneous networking, for improving a network's defense capabilities. Rather than following the current trend of converging towards single solutions to provide the desired functionality at every element of the network architecture, this methodology calls for systematically increasing the network's heterogeneity without sacrificing its interoperability.

In this paper, we argue that conventional operating systems need to be enhanced with predictable resource management mechanisms to meet the diverse performance requirements of emerging multimedia and web applications. We present QLinux—a multimedia operating system based on the Linux kernel that meets this requirement. QLinux employs hierarchical schedulers for fair, predictable allocation of processor, disk and network bandwidth, and accounting mechanisms for appropriate charging of resource usage. We experimentally evaluate the efficacy of these mechanisms using benchmarks and real-world applications. Our experimental results show that (i) emerging applications can indeed benefit from predictable allocation of resources, and (ii) the overheads imposed by the resource allocation mechanisms in QLinux are small. For instance, we show that the QLinux CPU scheduler can provide predictable performance guarantees to applications such as web servers and MPEG players, albeit at the expense of increasing the scheduling overhead. We conclude from our experiments that the benefits due to the resource management mechanisms in QLinux outweigh their increased overheads, making them a practical choice for conventional operating systems.

Past research in message logging has focused on studying the relative overhead imposed by pessimistic, optimistic and causal protocols during failure-free executions. In this paper, we give the first experimental evaluation of the performance of these protocols during recovery. Our results suggest that applications face a complex tradeoff when choosing a message logging protocol for fault tolerance. On the one hand, optimistic protocols can provide fast failure-free execution and good performance during recovery, but are complex to implement and can create orphan processes. On the other hand, orphan-free protocols either risk being slow during recovery (e.g. sender-based pessimistic and causal protocols) or incur a substantial overhead during failure-free execution (e.g. receiver-based pessimistic protocols). To address this tradeoff, we propose hybrid logging protocols, which are a new class of orphan-free protocols. We show that hybrid protocols perform within 2% of causal logging during failure-free execution and within 2% of receiver-based logging during recovery.

We describe the design and implementation of an integrated architecture for cache systems that scale to hundreds or thousands of caches with thousands to millions of users. Rather than simply try to maximize hit rates, we take an end-to-end approach to improving response time by also considering hit times and miss times. We begin by studying several Internet caches and workloads, and we derive three core design principles for large scale distributed caches: minimize the number of hops to locate and access data on both hits and misses; share data among many users and scale to many caches; and cache data close to clients. Our strategies for addressing these issues are built around a scalable, high-performance data-location service that tracks where objects are replicated. We describe how to construct such a service and how to use this service to provide direct access to remote data and push-based data replication. We evaluate our system through trace-driven simulation and find that these strategies together provide response time speedups of 1.27 to 2.43 compared to a traditional three-level cache hierarchy for a range of trace workloads and simulated environments.

We evaluate two architectural alternatives—partitioned and integrated—for designing next generation file systems. Whereas a partitioned server employs a separate file system for each application class, an integrated file server multiplexes its resources among all application classes; we evaluate the performance of the two architectures with respect to sharing of disk bandwidth among the application classes. We show that although the problem of sharing disk bandwidth in integrated file systems is conceptually similar to that of sharing network link bandwidth in integrated services networks, the arguments that demonstrate the superiority of integrated services networks over separate networks are not applicable to file systems. Furthermore, we show that: (i) an integrated server outperforms the partitioned server in a large operating region and has slightly worse performance in the remaining region, (ii) the capacity of an integrated server is larger than that of the partitioned server, and (iii) an integrated server outperforms the partitioned server by up to a factor of 6 in the presence of bursty workloads.

We quantify the adverse effect of file sharing on the performance of reliable distributed applications. We demonstrate that file sharing incurs significant overhead, which is likely to triple over the next five years. We present a novel approach that eliminates this overhead. Our approach: tracks causal dependencies resulting from file sharing using determinants; efficiently replicates the determinants in the volatile memory of agents to ensure their availability during recovery; and reproduces during recovery the interactions with the file server as well as the file data lost in a failure. Our approach allows agents to exchange files directly without first saving the files on disks at the server. As a consequence, the costs of supporting file sharing and message passing in a reliable distributed application become virtually identical. The result is a simple, uniform approach, which can provide low-overhead fault tolerance to applications in which communication is performed through message passing, file sharing, or a combination of the two.

In this paper we derive a statistical delay guarantee of the generalized virtual clock scheduling algorithm. We define the concept of an equivalent fluid and packet source and prove a theorem that relates the departure time of a packet in a fluid FCFS multiplexor to its departure time in a packet multiplexor that uses generalized Virtual Clock algorithm for scheduling packets. This theorem enables us to use extant analyses of fluid FCFS multiplexors for providing statistical QoS guarantees in a network that employs the generalized Virtual Clock algorithm. We utilize the extant analysis of FCFS fluid multiplexors serving two-stare on-off sources with exponentially distributed on and off durations to evaluate the increase in utilization yielded by our analysis technique. Our experiments demonstrate that for one of the source models employed in the literature, our technique can increase utilization by up to 400% compared to previously know statistical analysis methods.

In this paper, we present the Cello disk scheduling framework for meeting the diverse service requirements of applications. Cello employs a two-level disk scheduling architecture, consisting of a class-independent scheduler and a set of class-specific schedulers. The two levels of the framework allocate disk bandwidth at two time-scales: the class-independent scheduler governs the coarse-grain allocation of bandwidth to application classes, while the class-specific schedulers control the fine-grain interleaving of requests. The two levels of the architecture separate application-independent mechanisms from application-specific scheduling policies, and thereby facilitate the co-existence of multiple class-specific schedulers. We demonstrate that Cello is suitable for next generation operating systems since: (i) it aligns the service provided with the application requirements, (ii) it protects application classes from one another, (iii) it is work-conserving and can adapt to changes in work-load, (iv) it minimizes the seek time and rotational latency overhead incurred during access, and (v) it is computationally efficient.

Past research in message logging has focused on studying the relative overhead imposed by pessimistic, optimistic, and causal protocols during failure-free executions. We give the first experimental evaluation of the performance of these protocols during recovery. We discover that, if a single failure is to be tolerated, pessimistic and causal protocols perform best, because they avoid rollbacks of correct processes. For multiple failures, however, the dominant factor in determining performance becomes where the recovery information is logged (i.e. at the sender, at the receiver, or replicated at a subset of the processes in the system) rather than when this information is logged (i.e. if logging is synchronous or asynchronous).

In this paper, we define a class of generalized guaranteed rate (GR) scheduling algorithms that includes algorithms which allocate a variable rate to the packets of a flow. We define work-conserving generalized virtual clock, packet-by-packet generalized processor sharing, and self-clocked fair queueing scheduling algorithms that can allocate a variable rate to the packets of a flow. We also define scheduling algorithms suitable for servers where packet fragmentation may occur. We demonstrate that if a class of rate controllers is employed for a flow in conjunction with any scheduling algorithm in GR, then the resulting non-work-conserving algorithm also belongs to GR. This leads to the definition of several non-work-conserving algorithms. We then present a method for deriving the delay guarantee of a network of servers when: (1) different rates are allocated to packets of a flow at different servers along the path and the bottleneck server for each packet may be different, and (2) packet fragmentation and/or reassembly may occur. This delay guarantee enables a network to provide various service guarantees to flows conforming to any specification. We illustrate this by utilizing delay guarantee to derive delay bounds for flows conforming to leaky bucket, exponentially bounded burstiness, and flow specification. Our method for determining these bounds is valid in internetworks and leads to tighter results.

We present a start-time fair queueing (SFQ) algorithm that is computationally efficient and achieves fairness regardless of variation in a server capacity. We analyze its single server and end-to-end deadline guarantee for variable rate fluctuation constrained (FC) and exponentially bounded fluctuation (EBF) servers. To support heterogeneous services and multiple protocol families in integrated services networks, we present a hierarchical SFQ scheduler and derive its performance bounds. Our analysis demonstrates that SFQ is suitable for integrated services networks since it: (1) achieves low average as well as maximum delay for low-throughput applications (e.g., interactive audio, telnet, etc.); (2) provides fairness which is desirable for VBR video; (3) provides fairness, regardless of variation in server capacity, for throughput-intensive, flow-controlled data applications; (4) enables hierarchical link sharing which is desirable for managing heterogeneity; and (5) is computationally efficient.

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.

We present a network service specifically designed for multimedia servers. It uses a histogram based traffic characterization and an overload control protocol to the eliminate packet losses in the network while providing heterogeneous statistical QoS. The key contribution of our protocol lies in combining open-loop and feedback-based control to: (1) provide heterogeneous QoS to clients in networking environments consisting of switches that may not have any scheduling support; and (2) migrate the functionality of discarding packets, in the event of congestion, to the sources which understand the semantics of the data. The protocol is efficient, makes very few assumptions about the underlying network, is realizable on current switching hardware (supporting FCFS scheduling), and is completely integrated with the architecture of a multimedia server.

We present an adaptive network layer protocol for VBR video transport. It: (1) minimizes the buffer requirement in the network while guaranteeing that packets of VBR encoded video flows will not be lost, and (2) minimizes the end-to-end delay and jitter of frames. To achieve the former objective, we utilize a receiver-oriented adaptive credit-based flow control algorithm, and derive the necessary and sufficient number of buffers that should be reserved for ensuring its reliability. To minimize the end-to-end delay and jitter for VBR encoded video streams, we: (1) present bandwidth estimation techniques which exploit the structure of the video traffic, and (2) define a new fairness criteria for buffer allocation and then present a fair buffer/bandwidth allocation algorithm. We experimentally evaluate this protocol for a wide range of parameters and many network configurations, and demonstrate its adaptability. We also compare the performance of the protocol with numerous other schemes and demonstrate its suitability for video transport.

No abstract available.

We present Start-time Fair Queuing (SFQ) algorithm that is computationally efficient, achieves fairness regardless of variation in a server capacity, and has the smallest fairness measure among all known fair scheduling algorithms. We analyze its throughput, single server delay, and end-to-end delay guarantee for variable rate Fluctuation Constrained (FC) and Exponentially Bounded Fluctuation (EBF) servers. We show that SFQ is better suited than Weighted Fair Queuing for integrated services networks and it is strictly better than Self Clocked Fair Queuing. To support heterogeneous services and multiple protocol families in integrated services networks, we present a hierarchical SFQ scheduler and derive its performance bounds. Our analysis demonstrates that SFQ is suitable for integrated services networks since it: (1) achieves low average as well as maximum delay for low-throughput applications (e.g., interactive audio, telnet, etc.); (2) provides fairness which is desirable for VBR video; (3) provides fairness, regardless of variation in a server capacity, for throughput-intensive, flow-controlled data applications; (4) enables hierarchical link sharing which is desirable for managing heterogeneity; and (5) is computationally efficient.

In this paper, we present an algorithm that integrates scalable compression techniques with placement algorithms for disk arrays to efficiently support interactive scan operations (i.e., fast-forward and rewind) in video servers. We demonstrate that by suitably exploiting the characteristics of video streams and human perceptual tolerances, the overhead of such interactive operations can be substantially reduced. We present an analytical model for evaluating the impact of the fast-forward operation on the performance of disk-array-based servers. We validate the model through extensive simulations and analyze our results. 1 Introduction Recent advances in computing and communication technologies promise to create an infrastructure in which computer systems will support a wide range of interactive multimedia services in a variety of commercial and entertainment domains (e.g., advertising, online news, customer support, video on-demand, etc.). In its simplest configuration, such services...

A large-scale multimedia server, in practice, has to service a large number of clients simultaneously. Given the real-time requirements of each client and the fixed data transfer bandwidth of disks, a multimedia server must employ admission control algorithms to decide whether a new client can be admitted for service without violating the requirements of the clients already being serviced. In this paper, we present an admission control algorithm for multimedia servers which: (1) exploits the variation in access times of media blocks from disk as well as the variation in client load induced by variable rate compression schemes, and (2) provides statistical service guarantees to each client. The effectiveness of the algorithm is demonstrated through trace-driven simulations.

Effectiveness of managing collaborations directly impacts the productivity of a group, and can be significantly improved through computer supported tools made available by the advent of high speed networks and multimedia computer systems. In this paper, we propose a framework for characterizing the requirements of person-to-person (e.g. telephony), person-to-person (e.g., collaboration with software agents), and service-to-service collaborations (e.g., business workflow applications). The framework defines a hierarchy of three abstractions, at the lowest level of which are conferences which characterize the access rights of participants involved in a collaborative endeavor. The higher two levels are activities, which represent a collection of semantically related conferences, and collaborations, which represent temporally ordered sequences of activities. We describe the mechanisms for establishing and controlling the progress of a wide variety of multimedia collaborations. The framework for modelling collaborations and the mechanisms for their instantiation described in this paper form the basis of DiCE—a DistributedCollaborative Environment being developed at the IBM T.J. Watson Research Center.

The authors present a quantitative study of designing a multiuser HDTV server, and they present efficient techniques for storing multiple HDTV videos on disk and servicing multiple subscriber requests simultaneously, both under the constraint of guaranteeing HDTV playback rates. They develop a model that relates disk and device characteristics to the HDTV playback rate and derive a storage pattern for HDTV video streams that guarantees their real-time retrieval. Given multiple HDTV streams, mechanisms for merging their individual storage patterns are developed. Merging algorithms that yield a large improvement in space utilization over storing each of the streams independently are proposed. Policies such as round robin and quality proportional for servicing multiple subscribers simultaneously are studied. These studies provide a quantitative demonstration of the technological feasibility and economic viability of HDTV-on-demand servers on metropolitan area networks (MANs).>

The problem of collocational storage of media strands, which are sequences of continuously recorded audio samples or video frames, on disk to support the integration of storage and transmission of multimedia data with computing is examined. A model that relates disk and device characteristics to the playback rates of media strands and derives storage patterns so as to guarantee continuous retrieval of media strands is presented. To efficiently utilize the disk space, mechanisms for merging storage patterns of multiple media strands by filling the gaps between media blocks of one strand with media blocks of other strands are developed. Both an online algorithm suitable for merging a new media strand into a set of already stored strands and an offline merging algorithm that can be applied a priori to the storage of a set of media strands before any of them have been stored on disk are proposed. As a consequence of merging, storage patterns of media strands may become perturbed slightly. To compensate for this read-ahead and buffering are required so that continuity of retrieval remains satisfied are also presented.>

The problem of media mixing that arises in teleconferencing applications such as teleorchestra is addressed. The mixing algorithm presented minimizes the difference between generation times of the media packets that are being mixed together in the absence of globally synchronized clocks, but in the presence of jitter in communication delays on packet switched networks. In order to support applications, such as teleorchestra, that involve a large number of participants, hierarchical mixing architectures are proposed, and it is shown that they are an order of magnitude more scalable than purely centralized or distributed architectures. Furthermore, mechanisms for minimizing the delays incurred by mixing in various communication architectures are presented. The mixing algorithms are implemented on a network of workstations connected by Ethernets, and the performance of various mixing architectures is experimentally evaluated. The results reveal the maximum number of participants that can be supported in a conference.>

Future advances in networking and storage will enable a wide spectrum of computer mediated structured collaborations among individuals. In this paper, we present a model that can capture diverse types of structured collaborations. The model combines both efficiency and power via a hierarchy of three abstractions, at the lowest level of which are streams for media communication modulated by access rights of participants within collaborations. The higher two levels of abstractions are sessions, which represent collections of semantically related media streams, and conferences, which represent temporally related sequences of sessions. Using these abstractions, the model supports unification of both synchronous and asynchronous collaborations, sophisticated access control, and intra-group and inter-group collaborations, yielding a powerful set of building blocks for constructing multimedia applications and a rich environment for carrying out structured multimedia collaborations. KEYWORDS ...

The design of techniques and protocols for media mixing and communication architectures that optimize the performance of media mixing are discussed. The performance of monostage and multistage techniques for mixing are compared. Centralized and distributed architectures are analyzed for their suitability to both monostage and multistage media mixing, and hierarchical architectures that significantly reduce bandwidth consumption are presented. Algorithms for designing hierarchies that optimize real-time end-to-end delays and a packet train protocol in which the routing nodes can be used as mixers are proposed.>

We address the unique requirements of a multimedia file system such as continuous storage and retrieval of media, maintenance of synchronization between multiple media streams, and efficient manipulation of huge media objects. We present a model that relates disk and device characteristics to the recording rate, and derive storage granularity and scattering parameters that guarantee continuous access. In order for the file system to support multiple concurrent requests, we develop admission control algorithms for determining whether a new request can be accepted without violating the realtime constraints of any of the requests.We define a strand as an immutable sequence of continuously recorded media samples, and then present a multimedia rope abstraction which is a collection of individual media strands tied together by synchronization information. We devise operations for efficient manipulation of multi-stranded ropes, and develop an algorithm for maintaining the scattering parameter during editing so as to guarantee continuous playback of edited ropes.We have implemented a prototype multimedia file system, which serves as a testbed for experimenting with policies and algorithms for multimedia storage. We present our initial experiences with using the file system.

In the worst care, useless computations which are infinite may tie up machine resources and prevent program termination [CuI85,