Quality of Service - IWQoS 2003: 11th International Workshop, Berkeley, CA, USA, June 2-4, 2003, Proceedings (Lecture Notes in Computer Science, 2707)

Quality of Service continues to be an active research eld, especially in the networking community. IWQoS is a successful series of workshops that aims to provide a forum for the presentation and discussion of new research and ideas onQoS.Traditionally,IWQoSworkshopsarecross-disciplinaryandwellfocused, with the emphasis on innovation. As a result, a considerable amount of time is devoted to informal discussion. In addition to the traditional QoS topics such as service guarantees and admission control, this year we aimed to expand the scope of the workshop by encouraging submissions o?ering research contributions related to robustness, resilience, security, and predictability in networking and distributed systems. As a result, the program included two sessions on availability, fault tolerance, and dependability. The other sessions covered routing, resource allocation, storage, Web services, incentives, and rate based QoS. A great deal of e?ort as gone into putting together a high-quality program. The quality of submissions was very high, and the program committee had a di?cult task to select 27 papers among many deserving papers. Special thanks to the program committee, and the outside reviewers, for their e?orts and hard work in the reviewing and selection process during such a short time frame. We thank all authors who submitted papers to IWQoS, and who ultimately made this program possible. We express our appreciation for our sponsors, NSF, the IEEE Communi- tions Society, IFIP WG 6.1, and ACM SIGCOMM & SIGMOBILE. Quality of Service – IWQoS 2003 Preface Table of Contents Network Characteristics: Modelling, Measurements, and Admission Control Introduction Statistical Models for Round Trip Delays Physical Assumptions on the Transmission Path Background Traffic Models Spare Capacity Estimation Measurement Model Maximum-Likelihood Estimation A General Class of Estimators Experimental Framework and Implementation Results Conclusion Appendix Proof of Theorem 1 Proof of Proposition 1 Proof of Proposition T @ref {proposition2} Statistical Characterization for Per-hop QoS Introduction Approach to Statistical Characterization Factors and Factor Levels Statistical Analysis Experimental Framework Framework Components Network Setup and Testbed Configurations Design of Experiments Results and Analysis Characterizing EF PHB Characterizing AF PHB Discussion Related Work Conclusions and Extensions Performance Analysis of Server Sharing Collectives for Content Distribution Introduction Related Work Collectives General Model Computing the Rejection Rate of a Collective Evaluation of Scenarios under Fixed-Rate Transfers Asymptotic Limits of Collectives: The $rho /k$ Factor Collectives for Elastic Transfers Numerical Evaluation Resource Bounding with Thresholds Analytical Evaluation of D1 Thresholding Comparison of Thresholding Techniques Adaptive Thresholding Conclusion An Approximation of the End-to-End Delay Distribution Introduction System Model Definitions Motivation Estimation of the End-to-End Delay Distribution MVA Approximation for Delay Measuring the Moments of $X(1,t)$ Numerical Experiments Approximation of the End-to-End Delay Application to Admission Control Properties of the End-to-End Capacity Equivalent Single-Queue Representation Properties of $c_p(t)$ The Relationship between ${@mathbb {P}}{W_p>x}$ and ${@mathbb {P}}{Q_p>mathaccent "7016relax c_p x}$ Discussion Related Work Direct Measurement of ${@mathbb {P}}{W_p>x}$ Conclusion Price-Based Resource Allocation inWireless Ad Hoc Networks* Introduction Related Work Network Model and Resource Constraints Pricing Model in Wireless Ad hoc Networks Optimal Resource Allocation: Problem Formulation Achieving Fairness among Multi-hop Flows Algorithm: Pricing and Resource Allocation Simulation Results Resource Allocation in Wireline and Wireless Networks: A Comparison Convergence of the Iterative Algorithm Concluding Remarks On Achieving Fairness in the Joint Allocation of Processing and Bandwidth Resources* Introduction Introduction and Motivation Contributions Organization System Model and Notation Notation for a Notion of Fairness System Model and Assumptions The FMRA Principle The Concept of the Prime Resource The FMRA Principle Fair Joint Allocation of Processing and Bandwidth Resources System Model Fluid-Flow Processor and Link Sharing Packet-by-Packet Processor and Link Sharing Fairness Analysis of PPLS Simulation Results and Analysis Concluding Remarks Distributed Admission Control for Heterogeneous Multicast with Bandwidth Guarantees Introduction Network Model Requirements for Admission Control Essential Properties Performance Criteria Admission Control Algorithm Resource Management Sharing Violation Signaling Determining Bandwidth Requirements Installing Forwarding State Atomicity Problems Leaving a Group Discussion Simulation Related Work Conclusion and Future Work Subjective Impression of Variations in Layer Encoded Videos 1.2 What Is the Relation between Objective and Subjective Quality? 1 Introduction 1.1 Motivation 1.2 What Is the Relation between Objective and Subjective Quality? 1.3 Outline 2 Related Work 2.1 Retransmission Scheduling 2.2 Video Quality 3 Test Environment 3.1 Layer Encoded Video Format -- SPEG 3.2 Test Generation -- Full Control 3.3 Measurement Method -- Stimulus Comparison 3.4 Test Application -- Enforcing Time Constraints 4 Experiment 4.1 Scenario 4.2 Candidates 4.3 Procedure 4.4 Layer Patterns 5 Results 5.1 Same Amount of Segments 5.2 Different Amount of Segments 5.3 Sequence Size and Quality 6 Conclusion A Moving Average Predictor for Playout Delay Control in VoIP Introduction Some Background Related Work Performance Measures Moving Average Prediction The Model The Moving Average Algorithm The Problem with Low $p$ Performance Comparison Bias and Transformation Performance Comparison A Hybrid Algorithm for Playout Delay Performance Comparison Delay Spikes Conclusions To Play or to Control: A Game-Based Control-Theoretic Approach to Peer-to-Peer Incentive Engineering Introduction Preliminaries Incentives: A Game-Theoretic Perspective The Cournot Oligopoly Game Designing the Payoff Function Game-Based Optimal Control Design of the Optimal Control System The Plant: System Identification Optimization Objective: The Game-Based Objective Function The Optimal Control System Performance Evaluation Simulation Settings Experimental Results Related Work Conclusions Improving Dependability of Real-Time Communication with Preplanned Backup Routes and Spare Resource Pool* Introduction Pool of Spare Resources Selection of Backup Routes The Protocol for a Hybrid Scheme Notation and Data Structures Establishing a Primary Channel and Selecting a Backup Route Maintaining BV Scalability and Deployment Performance Evaluation Load Index and Performance Metrics Topology Characteristics Comparison with the Reactive Schemes Comparison with the Proactive Scheme Related Work Conclusion Fault Tolerance in Networks with an Advance Reservation Service Introduction Related Work Advance Reservation Model Issues of Implementing Fault Tolerance Mechanisms in Advance Reservation Environments Properties Rerouting Process Rerouting Strategies Pre-failure Strategies Post-failure Strategies Evaluation Simulation Environment Performance of the Pre-failure Strategies Performance of the Post-failure Strategies Influence of the Downtime Calculation Conclusion Routing and Grooming in Two-Tier Survivable Optical Mesh Networks Introduction Optical Network Overview STS-48 and STS-1 Switches Transmission Links Restoration Network Architectures One-Tier STS-48 Network One-Tier STS-1 Network Two-Tier Network Partial Two-Tier Network Routing Routing in One-Tier STS-1 Network Routing in Partial Two-Tier Network Packing of Sub-rate Circuits Physical Routing of Primary and Backup Paths Selection of Grooming Nodes in Partial Two-Tier Network Performance Comparison One-Tier vs. Full Two-Tier Network Partial Two-Tier Network Conclusion Fast Network Re-optimization Schemes for MPLS and Optical Networks Introduction Outline and Assumptions Key Ideas for the Re-optimization Scheme Illustrative Example Basic Re-optimization Scheme Network Model Solution Approach Network Efficiency Measure before Re-optimization Network Re-optimization Benefit Measure Network Re-optimization Benefit Threshold Minimum Cost Re-routing LSP Rerouting Overall Scheme Efficient Implementation Simulation Concluding Remarks HMP: Hotspot Mitigation Protocol for Mobile Ad hoc Networks 1 Introduction 2 Hotspots 2.1 Hotspot Observations 2.2 Traffic Load 2.3 Overhead 2.4 Hotspot Regions 3 Related Work 4 Hotspot Mitigation Protocol 4.1 Protocol Operations 4.2 Congestion Levels 4.3 Energy Conservation 5 Performance Evaluation 5.1 Hotspot Detection 5.2 Throughput Analysis 5.3 Routing Overhead Analysis 5.4 Energy Analysis 5.5 Parameterization Sensitivity 6 Conclusion Acknowledgements. This work is supported in part by the Army Research Office (ARO) under Award DAAD19-99-1-0287 and with support from COMET Group industrial sponsors. The authors would like to thank Jiyoung Cho for her comments on this paper. References Failure Insensitive Routing for Ensuring Service Availability* Introduction Failure Insensitive Routing Forwarding under FIR Forwarding Table Computation Local Recomputation of Forwarding Tables Summary of the FIR Scheme Efficient FIR Algorithms Available Shortest Path First Incremental ASPF Algorithms Evaluation of the FIR Scheme Link Failure Model Service Downtime Path Length Stretch Forwarding Table Computation Complexity Related Work Conclusions and Future Work Network Availability Based Service Differentiation Introduction Service Definition and Implementation Legacy Service: Fully Available (FA) Degraded Service: Partially Available (PA) Implementation Issues Backbones: Design and Engineering Principles Network Topology Network Engineering Failures in Backbone Networks Service Level Agreements SLAs in Commercial Networks SLA: Enhanced Definition Capturing Backbone Properties Topology Traffic Failure Scenario Proof of Concept and Validation of Assumptions Experimental Design and Results Factors Evaluated Computation of the Response Variable Impact of the Different Factors on the Response Variable Analysis of the SLA for the Degraded Class of Service Related Work Conclusion Quality of Availability: Replica Placement for Widely Distributed Systems 1 Introduction 2 Availability Refinement and QoA Metrics 2.1 Traditional Definitions 2.2 Refining Availability Definition 2.3 The Concept of Quality of Availability (QoA) 3 Replica Placement in Widely Distributed Systems 3.1 System Model 3.2 Problem Statement 3.3 Replica Placement Algorithms 4 Simulation 4.1 Simulation Methodology 4.2 Improving QoA - Static Approach 4.3 Guaranteeing QoA - Static Approach 4.4 Improving QoA - Dynamic Approach 4.5 Discussion 5 Related Work 6 Conclusion Using Latency Quantiles to Engineer QoS Guarantees for Web Services Introduction Web Workload Modeling Characterization of Simulation Input Distribution of the Sample's Quantile Implications Characterization of Simulation Output Testing for Convergence to Normality Results Simulation Study Summary and Conclusion DotQoS – A QoS Extension for .NET Remoting Introduction Requirements and Related Work Related Work Overview of .NET The .NET Framework Custom Meta-data .NET Remoting Contexts DotQoS Architecture and Implementation QoS Specification in DotQoS Defining QoS-Enabled Components Handling Contracts in DotQoS Scope of Contracts DotQoS Request-Level Sinks DotQoS Message-Level Sinks and Transport Channels QoS Mechanisms in DotQoS Compostion of QoS Mechanisms Performance Experience Conclusions and Outlook Dynamic Resource Allocation for Shared Data Centers Using Online Measurements* Introduction Motivation Research Contributions Problem Formulation and System Model Resource Model Problem Definition Dynamic Resource Allocation Online Monitoring and Measurement Allocating Resource Shares to Applications Workload Prediction Techniques Experimental Evaluation Simulation Setup and Workload Characteristics Dynamic Resource Allocation Related Work Conclusions Providing Deterministic End-to-End Fairness Guarantees in Core-Stateless Networks Introduction Notation and Assumptions Problem Formulation The Design of Core-Stateless Guaranteed Fair Networks Providing Fairness Guarantees: Key Insights Realization: A CSGF Network Evaluation of a CSGF Network Proportionate Allocation Guarantees Throughput Guarantees Discussion Deployment Considerations Related Work Summary Proof of Theorem 1 CSGT Networks Do Not Guarantee Proportionate Allocation: An Example Per-domain Packet Scale Rate Guarantee for Expedited Forwarding Introduction Packet Scale Rate Guarantee Servers Previous Work Definition of LR-WSG PSRG by LR-WSG Server LR-WSG Schedulers An Example of PSRGs for EF PHB Per-domain PSRG without Flow Aggregation Network Model Per-domain PSRG Delay Bounds Per-domain PSRG with Flow Aggregation Impact of Flow Aggregation Packet Scale Fair Aggregator Per-domain PSRG in Presence of Flow Aggregation An Expedited Forwarding Per-domain Behavior Conclusion On AchievingWeighted Service Differentiation: An End-to-End Perspective* Introduction Goals and Scope Motivation Limitations of Weighted AIMD Limitations of Application Striping The pTCP Protocol Design Elements Protocol Performance Evaluation Single Link Configuration Multiple Link Configuration Testbed Results Discussion Scalability Limit Host Overhead Future Work and Conclusions Online Response Time Optimization of Apache Web Server Introduction Apache Architecture and Measurements Analytic Model Online Optimization Newton's Method Fuzzy Control Saturation-Based Heuristic Optimization Experimental Results Conclusions A Practical Learning-Based Approach for Dynamic Storage Bandwidth Allocation* Introduction Dynamic Storage Bandwidth Allocation: Problem Definition Background and System Model Key Requirements Problem Formulation A Learning-Based Approach Reinforcement Learning Background System State Allocation Space Cost and State Action Values A Simple Learning-Based Approach An Enhanced Learning-Based Approach Implementation in Linux Experimental Evaluation Simulation Methodology and Workload Effectiveness of Dynamic Bandwidth Allocation Comparison with Alternative Approaches Effect of Tunable Parameters Implementation Experiments Implementation Overheads Related Work Concluding Remarks and Future Work CacheCOW: QoS for Storage System Caches Introduction QoS Based Cache Allocation Caches in Storage Systems I/O Request Class Identification Cache Allocation Problem Offline Cache Allocation Online Algorithms for Dynamic Cache Allocation History Periodic Re-allocation Algorithm Continuous Allocation Algorithm Experimental Evaluation Methodology Shared and Partitioned Cache Providing QoS Support Maximizing Hit Rates Reads and Writes Feasibility Region Dynamic Adaptation Related Work Conclusions Author Index

This book constitutes the refereed proceedings of the 10th International Workshop on Quality of Service, IWQoS 2003, held in Berkeley, CA, USA, in June 2003.

The 27 revised full papers presented were carefully reviewed and selected from numerous submissions. The papers are organized in topical sections on analysis and modeling, resource allocation and admission control, multimedia and incentives, dependability and fault tolerance, routing, availability and dependability, Web services, rate-based QoS, and storage.