Towards communication-sensitive load balancing
Recent studies have shown that if the overhead associated with process migration is not high when compared to the estimated lifetime of processes, migrating isolated processes to underutilized workstations can improve system performance. However, if tightly-coupled processes from groups of communicating processes or other existing dependencies are separated, system performance can decrease due to increased communication cost. Current load balancers do not make effective use of communication dependencies in their algorithms. We have implemented a communication-sensitive load balancer for DUNES (Distributed UNix ExtenSion)-a user-level distributed operating system-that uses the run-time communication pattern between processes when balancing load. We examine communication-sensitive load balancing under different workload conditions and compare its performance against a load balancer that is not communication-aware. Our results show that a communication-sensitive load balancer performs substantially better than a load balancer that is not communication-aware under workloads that have a "good mix" of CPU-bound and I/O-bound processes.

title: A distributed protocol for multi-class QoS provision in noncooperative many-switch systems
abstract: This paper presents an architecture for multi-class quality of service (QoS) provision in wide area networks. Users or applications are assumed to be selfish and end-to-end QoS is determined by the service levels received by an application traffic flow at each router or switch along a path. In previous work, we have given a comprehensive analysis of the noncooperative multi-class QoS provision game for single-switch systems showing when Nash equilibria exist and under what conditions they are Pareto and/or system optimal. In this paper, we propose a specific network architecture for facilitating noncooperative and of provision in many-switch systems such as the Internet with emphasis on realizability. We shield the user from having to choose the service classes on the switches along a route-a hard combinatorial optimization problem even assuming perfect knowledge about network state-while preserving the basic premise of selfishness. This is achieved by employing a set of QoS agents installed at routers which act on behalf of an user's traffic flow. The QoS agent intercepts packets entering a switch implementing generalized processor sharing (GPS) packet scheduling-and using only constant space packet header overhead and zero per-connection state at the routers-determines which service class to assign the packet to to satisfy the user's end-to-end QoS requirement at minimum cost. We present simulation results which show that our architecture is able to provide stable, stratified services to application traffic with diverse QoS requirements.

title: Efficient Shaping of User-Specified QoS Using Aggregate-Flow Control
abstract: Architecting networks capable of providing scalable, efficient, and fair services to users with diverse QoS requirements is a pressing problem. The two principal issues are: design of "good" per-hop behavior and edge control. In previous work [2,3], we studied aggregate-flow QoS control from a noncooperative resource provisioning context. In [20], the framework was generalized by, one, solving an optimal aggregate-flow per-hop behavior problem, and two, showing how it can be used coupled with end-to-end label control to facilitate scalable and fair QoS when driven by selfish users and service providers. In this paper, we focus on optimal aggregate-flow per-hop control and complement analysis by experimental performance evaluation. We show that user-specified, diverse QoS is efficiently facilitated over the optimal per-hop behavior network substrate using adaptive label control end-to-end.

title: Performance evaluation of optimal aggregate-flow scheduling: a simulation study
abstract: Providing scalable QoS-sensitive services to applications with varying degrees of elasticity using aggregate-flow scheduling is a challenging problem. In a previous paper , we advanced a theoretical framework where an optimal differentiated services provisioning problem is formulated and solved to yield solutions for optimal per-hop control. In this paper, we extend our previous work by investigating performance evaluation and implementation issues associated with the induced optimal differentiated services architecture. We design a system that realizes the optimal per-hop control coupled with end-to-end adaptive QoS control, and implement a practical enhancement by introducing a scaling function which is applied to the TOS field label value in the IP header at each router. The scaling function allows the service provider to configure the per-hop control so as to export customized QoS separation-essential when shaping end-to-end absolute QoS over per-hop relative QoS-commensurate with the QoS profiles of the service provider's user base. We use simulation to study the structural and dynamical properties of differentiated services as affected by optimal aggregate-flow per-hop control.

title: An architecture for noncooperative QoS provision in many-switch systems
abstract: With the proliferation of high-speed networks and networked services, provisioning differentiated services to a diverse user base with heterogeneous QoS requirements has become an important problem. The traditional approach of resource reservation and admission control provides both guarantees and graded services, however, at the cost of potentially underutilized resources and limited scalability. We describe a WAN QoS provision architecture that adaptively organizes best-effort bandwidth into stratified services with graded QoS properties such that the QoS needs of a diverse user base can be effectively met. This architecture-SBS (stratified best-effort service)-promotes a simple user/simple network realization where neither the user nor the network is burdened with complex computational responsibilities. SBS is scalable, efficient, and adaptive, and it complements the guaranteed service architecture, sharing a common network substrate comprised of GPS routers. It is also a functional complement, provisioning QoS efficiently commensurate with user needs, albeit at the cost of weaker protection. SBS is suited to noncooperative network environments where users behave selfishly and resource contention resolution is mediated by the principle of competitive interaction. A principal feature of SBS is the transformation of user-centric QoS provision mechanisms-a defining characteristic of competitive interaction entailing intimate user control of internal network resources-into network-centric mechanisms while preserving the former's resource allocation paradigm. End-to-end QoS control is facilitated by decentralized control based on Lagrangian optimization-achieve a target end-to-end QoS at minimum cost or resource usage-which, in turn, is amenable to distributed implementation. SBS achieves per-flow QoS control with zero per-flow state at routers and a packet header whose size is independent of hop count. SBS, in spite of foregoing both resource reservation and admission control, is able to provision stable, graded QoS.

title: QoS-sensitive transport of real-time MPEG video using adaptive redundancy control
abstract: This paper presents an adaptive end-to-end protocol for quality of service (QoS)-sensitive transport of real-time MPEG video using packet-level forward error correction in dynamic networks. The objective is to facilitate a user-specified QoS end-to-end - i.e. without special network support - for real-time MPEG video whose timing constraints rule out the use of retransmission-based congestion control and QoS provisioning schemes. The degree of redundancy - overcode in forward error correction - injected into the network is adjusted as a function of network state, decreasing when the network is well-behaved to minimize unnecessary network resource consumption, and increasing when it is not to compensate for adverse network effects so as to maintain an invariant level of end-to-end QoS. We describe an adaptive packet-level forward error correction protocol called AFEC and analyze its properties with respect to optimality and stability. The optimal control problem is nontrivial due to the fact that increased redundancy, beyond a certain point, can backfire resulting in self-induced congestion which impedes the timely recovery of information - MPEG video frames - at the receiver. We experimentally evaluate the efficacy of our end-to-end QoS control by implementing and customizing AFEC to the transport of real-time MPEG video. We realize the system as a transport/application layer protocol running on UNIX workstations, and measure its performance over controlled network environments. We show that AFEC is able to effectively hide potentially adverse network effects such as packet drops and delays stemming from traffic burstiness and nonstationary structural changes using adaptive redundancy control, exporting a constant QoS service commensurate with user-specified QoS.

title: Scale and Performance in the CoBlitz Large-File Distribution Service
abstract: Scalable distribution of large files has been the area of much research and commercial interest in the past few years. In this paper, we describe the CoBlitz system, which efficiently distributes large files using a content distribution network (CDN) designed for HTTP. As a result, CoBlitz is able to serve large files without requiring any modifications to standard Web servers and clients, making it an interesting option both for end users as well as infrastructure services. Over the 18 months that CoBlitz and its partner service, CoDeploy, have been running on PlanetLab, we have had the opportunity to observe its algorithms in practice, and to evolve its design. These changes stem not only from observations on its use, but also from a better understanding of their behavior in real-world conditions. This utilitarian approach has led us to better understand the effects of scale, peering policies, replication behavior, and congestion, giving us new insights into how to better improve their performance. With these changes, CoBlitz is able to deliver in excess of 1 Gbps on PlanetLab, and to outperform a range of systems, including research systems as well as the widely-used BitTorrent.

title: A Comparative Study of Genetic Search
abstract: We present a comparative study of genetic algorithms and their search properties when treated as a combinatorial optimization technique. This is done in the context of the NP-hard problem MAX-SAT, the comparison being relative to the Metropolis process, and by extension, simulated annealing. Our contribution is twofold. First, we show that for large and diicult MAX-SAT instances, the contribution of cross-over to the search process is marginal. Little is lost if it is dispensed altogether, running mutation and selection as an enlarged Metropolis process. Second, we show that for these problem instances , genetic search consistently performs worse than simulated annealing when subject to similar resource bounds. The correspondence between the two algorithms is made more precise via a decomposition argument, and provides a framework for interpreting our results.

title: A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming

title: Robust playout mechanism for Internet audio applications
abstract: In Internet audio applications, delay and delay jitter affect mostly the applications' quality of service. Since packet delays are different and changing over time, the receiver needs to buffer some amount of packets before playout. Therefore, the amount of buffered packets and the timing of playout are very important for the performance of applications. We adopt an autoregressive (AR) model for estimation of packet delay and deploy a robust identification algorithm for adjustment of the parameters of the AR process. In our preliminary experiments, this robust algorithm leads to better performance when the noise is correlated and/or non-stationary, and also it is robust to model uncertainties.

title: On the relationship between file sizes, transport protocols, and self-similar network traffic
abstract: Measurements of LAN and WAN traffic show that network traffic exhibits variability on different scales. We examine a mechanism that gives rise to self-similar network traffic and discuss performance. The mechanism we study is the transfer of files or messages whose size is drawn from a heavy-tailed distribution. In a realistic client/server network the degree to which file sizes are heavy-tailed can directly determine the degree of traffic self-similarity at the link level. This causal relationship is robust relative to changes in network resources, network topology, the influence of cross-traffic, and the distribution of interarrival times. Properties of the transport layer play an important role in preserving and modulating this relationship. The reliable transmission and flow control mechanisms of TCP serve to maintain the long-range dependency structure induced by heavy-tailed file size distributions. In contrast, if a non-flow-controlled and unreliable (UDP-based) transport protocol is used, the resulting traffic shows little self-similarity: although still bursty at short time scales, it has little long-range dependence. Performance implications of self-similarity are discussed as represented by various performance measures. Increased self-similarity as expected, results in degradation of performance. Queueing delay, in particular is discussed. Throughput-related measures such as packet loss and retransmission rate, however increase only gradually with increasing traffic self-similarity as long as reliable, flow-controlled transport protocol is used.