Modern Internet services generate massive volumes of observability data, yet identifying opportunities for business performance improvements remains elusive. In many cases, such insights manifest only within sub-populations defined by derived attributes that cannot be predefined, might evolve over time, and often cannot be exhaustively enumerated ahead of time. Unfortunately, existing commercial and research systems fall short in one or more aspects of generating such improvement opportunities: expressiveness, automation, and scalability. We present a vision for automatically surfacing opportunities for improvements to tackle these seemingly conflicting and intractable requirements. We highlight the early promise from a proof-of-concept system, showing evaluation on three real-world services and discuss open challenges for future work.

A key to video streaming systems is knowing how sensitive quality of experience (QoE) is to quality metrics (e.g., buffering ratio and average bitrate). In the conventional wisdom, such quality sensitivity should be profiled by offline user studies because QoE is equally sensitive to quality metrics everywhere for an entire genre of videos. However, recent studies show that quality sensitivity varies substantially both across videos and within a video, giving rise to a new potential for improving QoE and serving more users without using more bandwidth. Unfortunately, offline profiling cannot capture the variability of quality sensitivity within a new video (e.g., a new TV show episode or live sports event), if users join to watch it within a short time window.

Internet video providers rely on alerting workflows to identify and remedy incidents that can impact users (e.g., outages or buggy players). There is growing evidence for the need for viewership-based analytics---detecting and diagnosing incidents that manifest through changes in viewership patterns but not in other (e.g., QoE) metrics. However, both detection and diagnosis of viewership anomalies is challenging due to the contextual nature of anomalies, non-stationarity of viewership, and complex dependencies between the structure of events and how they impact different subpopulations of viewers. We present Proteas, an alerting framework for video viewership anomalies that tackles these challenges. Proteas builds on key spatiotemporal structural insights. First, across different sub-populations of viewers and days of the week, we find that the shape of the viewership curve remains invariant over multiple weeks, thus enabling anomaly detection. Second, we use the hierarchy of viewership groups to produce compact alerts. Finally, we find that common anomalies manifest with spatiotemporal signatures, which enables us to classify anomalies to produce actionable alerts. We evaluate Proteas using 3 months of real viewership data (including the onset of the COVID-19 pandemic) and show that Proteas is accurate with over 80% True Positive Rate, average precision of over 86% (i.e., few false positives) and doesn't miss any major events. In addition, we find that approximately half of Proteas's alerts refer to events not caught by other alerting workflows, thus adding value to operators' existing toolkit.

Recent years have witnessed much interest in Low Power Wide Area (LPWA) technologies, which are gaining unprecedented momentum and commercial interest towards the realisation of the Internet of Things (IoT). Long Range (LoRa), as a representative LPWA technology, has the potential to satisfy the growing demand for the longer range and larger amount connectivities in vehicular communication networks. In this paper, LoRa is firstly applied into two typical vehicular networks, namely Vehicle-to-Infrastructure (V2I)and Vehicle-to-Vehicle (V2V), and performance of LoRa schemes with different parameter configurations are evaluated and compared. Further, Monte Carlo simulations indicate that the schemes equipped with higher bandwidth or lower spreading factor exhibit significant advantages in combating the fast fading caused by Doppler effect in networks.

Most content providers are interested in providing good video delivery QoE for all users, not just on average. State-of-the-art ABR algorithms like BOLA and MPC rely on parameters that are sensitive to network conditions, so may perform poorly for some users and/or videos. In this paper, we propose a technique called Oboe to auto-tune these parameters to different network conditions. Oboe pre-computes, for a given ABR algorithm, the best possible parameters for different network conditions, then dynamically adapts the parameters at run-time for the current network conditions. Using testbed experiments, we show that Oboe significantly improves BOLA, MPC, and a commercially deployed ABR. Oboe also betters a recently proposed reinforcement learning based ABR, Pensieve, by 24% on average on a composite QoE metric, in part because it is able to better specialize ABR behavior across different network states.

Various trends are reshaping Internet video delivery: exponential growth in video traffic, rising expectations of high video quality of experience (QoE), and the proliferation of varied content delivery network (CDN) deployments (e.g., cloud computing-based, content provider-owned datacenters, and ISP-owned CDNs). More fundamentally though, content providers are shifting delivery from a single CDN to multiple CDNs, through the use of a content broker. Brokers have been shown to invalidate many traditional delivery assumptions (e.g., shifting traffic invalidates short- and long-term traffic prediction) by not communicating their decisions with CDNs. In this work, we analyze these problems using data from a CDN and a broker. We examine the design space of potential solutions, finding that a marketplace design (inspired by advertising exchanges) potentially provides interesting tradeoffs. A marketplace allows all CDNs to profit on video delivery through fine-grained pricing and optimization, where CDNs learn risk-adverse bidding strategies to aid in traffic prediction. We implement a marketplace-based system (which we dub Video Delivery eXchange or VDX) in CDN and broker data-driven simulation, finding significant improvements in cost and data-path distance.

Various trends are reshaping content delivery on the Internet: the explosive growth of traffic due to video, users' increasing expectations for higher quality of experience (QoE), and the proliferation of server capacity from a variety of sources (e.g., cloud computing, content provider-owned datacenters, and ISP-owned CDNs). In order to meet the scale and quality demands imposed by users, content providers have started to spread demand across a variety of CDNs using a broker. Brokers break many traditional CDN assumptions (e.g., unexpected traffic skew, significant variance in demand over short timescales, etc.). Through an analysis of data from a leading broker and a leading CDN, we show the potential challenges and opportunities that brokers impart on content delivery. We take the first steps towards improvement through a redesigned broker-CDN interface.

Interactive real-time streaming applications such as audio-video conferencing, online gaming and app streaming, place stringent requirements on the network in terms of delay, jitter, and packet loss. Many of these applications inherently involve client-to-client communication, which is particularly challenging since the performance requirements need to be met while traversing the public wide-area network (WAN). This is different from the typical situation of cloud-to-client communication, where the WAN can often be bypassed by moving a communication end-point to a cloud “edge”, close to the client. Can we nevertheless take advantage of cloud resources to improve the performance of real-time client-to-client streaming over the WAN?

Live video delivery is expected to reach a peak of 50 Tbps this year. This surging popularity is fundamentally changing the Internet video delivery landscape. CDNs must meet users' demands for fast join times, high bitrates, and low buffering ratios, while minimizing their own cost of delivery and responding to issues in real-time. Wide-area latency, loss, and failures, as well as varied workloads ("mega-events" to long-tail), make meeting these demands challenging.

There is a growing recognition among researchers, industry practitioners, and service providers of the need to optimize user-perceived application experience. Network infrastructure owners (i.e., ISPs) have traditionally been left out of this equation, leading to repeated tussles between content providers and ISPs. In parallel, application providers have to deploy complex workarounds that reverse engineer the network's impact on application-level metrics. In this work, we make the case for EONA, a new network paradigm where application providers and network providers can collaborate meaningfully to improve application experience. We observe a confluence of technology trends that are enablers for EONA: the ability to collect large volumes of client-side application measurements, the emergence of novel "big data" platforms for real-time analytics, and new control plane capabilities for ISPs (e.g., SDN, IXPs, NFV). We highlight the challenges and opportunities in designing suitable EONA interfaces between infrastructure and application providers and EONA-enhanced control loops that leverage these interfaces to optimize user experience.

We envision a real-time network traffic map for the Internet, where each network link is annotated with its capacity and its current utilization, with an interface that networked applications can query to inform their control decisions. While this goal is simple to state, it has been out of our reach due to concerns over measurement overhead and coverage. Our insight is that the rise of Internet video and the availability of measurements from video players present an unprecedented opportunity to address these issues. We outline a preliminary roadmap to build on this opportunity to realize a global traffic map.

User-created live video streaming is marking a fundamental shift in the workload of live video delivery. However, live-video-specific challenges and the viral nature of user-created content makes it difficult for current CDNs to deliver 1) high-quality, 2) highly-scalable, and 3) highly-responsive service. We present the design and implementation of VDN, a new control plane for CDNs designed to optimize the delivery of live streams within the CDN. VDN satisfies these requirements by using two approaches: 1) optimizing directly for video quality (not just throughput) and 2) combining centralized control with local control, allowing VDN to adapt to traffic dynamics and network failures at fine timescales.

This paper presents the design, implementation, and evaluation of TransCom, a virtual disk (Vdisk) based cloud computing platform that supports heterogeneous services of operating systems (OSes) and their applications in enterprise environments. In TransCom, clients store all data and software, including OS and application software, on Vdisks that correspond to disk images located on centralized servers, while computing tasks are carried out by the clients. Users can choose to boot any client for using the desired OS, including Windows, and access software and data services from Vdisks as usual without consideration of any other tasks, such as installation, maintenance, and management. By centralizing storage yet distributing computing tasks, TransCom can greatly reduce the potential system maintenance and management costs. We have implemented a multi-platform TransCom prototype that supports both Windows and Linux services. The extensive evaluation based on both test-bed experiments and real-usage experiments has demonstrated that TransCom is a feasible, scalable, and efficient solution for successful real-world use.

Modern video players today rely on bit-rate adaptation in order to respond to changing network conditions. Past measurement studies have identified issues with today's commercial players when multiple bit-rate-adaptive players share a bottleneck link with respect to three metrics: fairness, efficiency, and stability. Unfortunately, our current understanding of why these effects occur and how they can be mitigated is quite limited. In this paper, we present a principled understanding of bit-rate adaptation and analyze several commercial players through the lens of an abstract player model consisting of three main components: bandwidth estimation, bit-rate selection, and chunk scheduling. Using framework, we identify the root causes of several undesirable interactions that arise as a consequence of overlaying the video bit-rate adaptation over HTTP. Building on these insights, we develop a suite of techniques that can systematically guide the tradeoffs between stability, fairness, and efficiency and thus lead to a general framework for robust video adaptation. We pick one concrete instance from this design space and show that it significantly outperforms today's commercial players on all three key metrics across a range of experimental scenarios.

The key role that video quality plays in impacting user engagement, and consequently providers' revenues, has motivated recent efforts in improving the quality of Internet video. This includes work on adaptive bitrate selection, multi-CDN optimization, and global control plane architectures. Before we embark on deploying these designs, we need to first understand the nature of video of quality problems to see if this complexity is necessary, and if simpler approaches can yield comparable benefits.

Improving users' quality of experience (QoE) is crucial for sustaining the advertisement and subscription based revenue models that enable the growth of Internet video. Despite the rich literature on video and QoE measurement, our understanding of Internet video QoE is limited because of the shift from traditional methods of measuring video quality (e.g., Peak Signal-to-Noise Ratio) and user experience (e.g., opinion scores). These have been replaced by new quality metrics (e.g., rate of buffering, bitrate) and new engagement centric measures of user experience (e.g., viewing time and number of visits). The goal of this paper is to develop a predictive model of Internet video QoE. To this end, we identify two key requirements for the QoE model: (1) it has to be tied in to observable user engagement and (2) it should be actionable to guide practical system design decisions. Achieving this goal is challenging because the quality metrics are interdependent, they have complex and counter-intuitive relationships to engagement measures, and there are many external factors that confound the relationship between quality and engagement (e.g., type of video, user connectivity). To address these challenges, we present a data-driven approach to model the metric interdependencies and their complex relationships to engagement, and propose a systematic framework to identify and account for the confounding factors. We show that a delivery infrastructure that uses our proposed model to choose CDN and bitrates can achieve more than 20\% improvement in overall user engagement compared to strawman approaches.

Many commercial video players rely on bitrate adaptation logic to adapt the bitrate in response to changing network conditions. Past measurement studies have identified issues with today's commercial players with respect to three key metrics---efficiency, fairness, and stability---when multiple bitrate-adaptive players share a bottleneck link. Unfortunately, our current understanding of why these effects occur and how they can be mitigated is quite limited.

An imminent challenge that content providers, CDNs, third-party analytics and optimization services, and video player designers in the Internet video ecosystem face is the lack of a single "gold standard" to evaluate different competing solutions. Existing techniques that describe the quality of the encoded signal or controlled studies to measure opinion scores do not translate directly into user experience at scale. Recent work shows that measurable performance metrics such as buffering, startup time, bitrate, and number of bitrate switches impact user experience. However, converting these observations into a quantitative quality-of-experience metric turns out to be challenging since these metrics are interrelated in complex and sometimes counter-intuitive ways, and their relationship to user experience can be unpredictable. To further complicate things, many confounding factors are introduced by the nature of the content itself (e.g., user interest, genre). We believe that the issue of interdependency can be addressed by casting this as a machine learning problem to build a suitable predictive model from empirical observations. We also show that setting up the problem based on domain-specific and measurement-driven insights can minimize the impact of the various confounding factors to improve the prediction performance.

Video traffic already represents a significant fraction of today's traffic and is projected to exceed 90% in the next five years. In parallel, user expectations for a high quality viewing experience (e.g., low startup delays, low buffering, and high bitrates) are continuously increasing. Unlike traditional workloads that either require low latency (e.g., short web transfers) or high average throughput (e.g., large file transfers), a high quality video viewing experience requires sustained performance over extended periods of time (e.g., tens of minutes). This imposes fundamentally different demands on content delivery infrastructures than those envisioned for traditional traffic patterns. Our large-scale measurements over 200 million video sessions show that today's delivery infrastructure fails to meet these requirements: more than 20% of sessions have a rebuffering ratio ≥ 10% and more than 14% of sessions have a video startup delay ≥ 10s. Using measurement-driven insights, we make a case for a video control plane that can use a global view of client and network conditions to dynamically optimize the video delivery in order to provide a high quality viewing experience despite an unreliable delivery infrastructure. Our analysis shows that such a control plane can potentially improve the rebuffering ratio by up to 2× in the average case and by more than one order of magnitude under stress.

Route Aggregation (RA), the method to supersede a set of routes by a single, more general route, is a fundamental mechanism to the Internet scalability. Yet, despite its importance, it is poorly understood. We present the first systematic analysis of RA via both bottom-up experimental and top-down analytical approaches. We first conduct a set of experiments on RA behaviors of all major routing protocols as implemented by the two leading router vendors. Our experiments show that the RA behaviors vary significantly across routing protocols and vendors. We propose two router level primitives and incorporate them into a canonical router model. The new model captures the diversity of the observed behaviors. With aid of the model, we have advanced the fundamental understanding of RA on three fronts. First, we expose four new types of routing anomaly that can derive from RA. Configuring RA on one router interface can influence how routes are advertised on other interfaces of the same router, impacting network reachability in surprising ways. Second, we demonstrate that determining whether a RA configuration can result in persistent forwarding loops is NP-complete. Finally, we present sufficient conditions for RA primitives to guarantee routing safety, and explore clean-slate designs for RA.

As the distribution of the video over the Internet becomes main- stream and its consumption moves from the computer to the TV screen, user expectation for high quality is constantly increasing. In this context, it is crucial for content providers to understand if and how video quality affects user engagement and how to best invest their resources to optimize video quality. This paper is a first step towards addressing these questions. We use a unique dataset that spans different content types, including short video on demand (VoD), long VoD, and live content from popular video con- tent providers. Using client-side instrumentation, we measure quality metrics such as the join time, buffering ratio, average bitrate, rendering quality, and rate of buffering events.

Network management applications require accurate estimates of a wide range of flow-level traffic metrics. Given the inadequacy of current packet-sampling-based solutions, several application-specific monitoring algorithms have emerged. While these provide better accuracy for the specific applications they target, they increase router complexity and require vendors to commit to hardware primitives without knowing how useful they will be to meet the needs of future applications. In this paper, we show using trace-driven evaluations that such complexity and early commitment may not be necessary. We revisit the case for a "minimalist" approach in which a small number of simple yet generic router primitives collect flow-level data from which different traffic metrics can be estimated. We demonstrate the feasibility and promise of such a minimalist approach using flow sampling and sample-and-hold as sampling primitives and configuring these in a network-wide coordinated fashion using cSamp. We show that this proposal yields better accuracy across a collection of application-level metrics than dividing the same memory resources across metric-specific algorithms. Moreover, because a minimalist approach enables late binding to what application level metrics are important, it better insulates router implementations and deployments from changing monitoring needs.

Recent studies have shown that the current primitives for connecting multiple routing protocol instances (OSPF 1, OSPF 2, EIGRP 10, etc.) are pervasively deployed in enterprise networks and the Internet. Furthermore, these primitives are extremely vulnerable to routing anomalies (route oscillations, forwarding loops, etc.) and at the same time too rigid to support some of today's operational objectives. In this paper, we propose a new theory to reason about routing properties across multiple routing instances. The theory directly applies to both link-state and vector routing protocols. Each routing protocol still makes independent routing decisions and may consider a combination of routing metrics, including bandwidth, delay, cost, and reliability. While the theory permits a range of solutions, we focus on a design that requires no changes to existing routing protocols. Guided by the theory, we derive a new set of connecting primitives, which are not only provably safe but also more expressive than the current version. We have implemented and validated the new primitives using XORP. The results confirm that our design can support a large range of desirable operational goals, including those not achievable today, safely and with little manual configuration.

Networks cannot be managed without management plane communications among geographically distributed network devices and control agents. Unfortunately, the mechanisms used in commercial networks to support management plane communications are often hard to configure, insufficiently secured, and/or suboptimal in performance. This paper presents the design and implementation of the Meta-Management System (MMS), a network-layer subsystem that provides robust autonomic support for management plane communications. We demonstrate the practicality of the MMS via a fully functional implementation that runs on commodity hardware, and experimentally show that the MMS is efficient and scalable. The MMS software is freely available.

We present the design and deployment experiences with LiveSky , a commercial hybrid CDN-P2P live streaming system, which inherits the best of both CDN and P2P. We address several key challenges, including: 1) ease of integration with existing CDN infrastructure, 2) dynamic resource scaling while guaranteeing quality-of-service, 3) providing good user experience, ensuring network friendliness and upload fairness. LiveSky has been used for several large-scale live streaming events in China. Our evaluation results from real-world indicate that such a hybrid CDN-P2P system provides quality and performance comparable to a CDN and effectively scales the system capacity.

Remote desktop access is commonly used to remotely access a host in enterprise networks; however it also brings in security problems in supervision and auditing. In this paper, a novel proxy-based security audit system is designed and implemented in order to ensure security supervising and auditing remote desktop access. Our system effectively monitors all the accessing sessions of RDP, VNC, and X-window, and provides replay function by recording all the graphics operations from users. Our performance test result shows that for most of small business, just one proxy server is enough to handle all the routine auditing workload of RDP sessions.

In this paper, we consider the design of a policy-based routing system and the role that link state might play. Looking at the problem from a link-state perspective, we propose Centaur, a hybrid routing protocol combining the benefits of both link state and path vector. Through analytical and experimental studies, we demonstrate Centaur's potential in achieving rich policy expressiveness and high network availability. Our work shows that it is possible to combine link-state and path-vector approaches into a practical and efficient algorithm for policy-based routing.

The 2008 Beijing Olympics was an interesting event from a VoD perspective because it involved near real-time video delivery at massive scales over multiple days of a high-profile event. We present some measurement-driven insights into this event through a unique dataset obtained from ChinaCache, the largest CDN in China. The dataset is unique in three respects. First, it gives a "white-box" view into user access patterns which would otherwise be impossible. Second, since the CDN serves different content providers, it allows to compare and contrast the effects of different presentation models on end users. Third, the nature of the content itself is vastly different from traditional VoD systems in terms of the real-time and event-driven nature, which gives rise to unique effects. The dataset allows us to investigate a wide range of interesting issues: (1) how the live nature of the events causes differences in access patterns compared to traditional VoD and User-Generated Content (UGC) systems, (2) how the presentation models affect user behavior, and (3) flash-crowd phenomena. Based on these observations, we discuss implications for future live VoD systems.

We present our design and deployment experiences with LiveSky, a commercially deployed hybrid CDN-P2P live streaming system. CDNs and P2P systems are the common techniques used for live streaming, each having its own set of advantages and disadvantages. LiveSky inherits the best of both worlds: the quality control and reliability of a CDN and the inherent scalability of a P2P system. We address several key challenges in the system design and implementation including (a) dynamic resource scaling while guaranteeing stream quality, (b) providing low startup latency, (c) ease of integration with existing CDN infrastructure, and (d) ensuring network-friendliness and upload fairness in the P2P operation. LiveSky has been commercially deployed and used for several large-scale live streaming events serving more than ten million users in China. We evaluate the performance of LiveSky using data from these real-world deployments. Our results indicate that such a hybrid CDN-P2P system provides quality and user performance comparable to a CDN and effectively scales the system capacity when the user volume exceeds the CDN capacity.

A repository of router configuration files from production networks would provide the research community with a treasure trove of data about network topologies, routing designs, and security policies. However, configuration files have been largely unobtainable precisely because they provide detailed information that could be exploited by competitors and attackers. This paper describes a method for anonymizing router configuration files by removing all information that connects the data to the identity of the underlying network, while still preserving the structure of information that makes the data valuable to networking researchers. Anonymizing configuration files has unusual requirements, including preserving relationships between elements of data, anonymizing regular expressions, and robustly coping with more than 200 versions of the configuration language. Conventional tools and techniques are poorly suited to the problem. Our anonymization method has been validated with a major carrier, earning unprivileged researchers access to the configuration files of thousands of routers in hundreds of networks. Through example analysis, we demonstrate that the anonymized data retains the key properties of the network design. The paper sets out techniques that could be used in an attempt to break the anonymization, and it concludes our anonymization techniques are most applicable to enterprise networks, because the large number of enterprises and the difficulty of probing them from the outside make it hard to recognize an anonymized network based solely on publicly-available information about its topology or configuration. When applied to backbone networks, which are few in number and many of whose properties can be publicly measured, the anonymization might be broken by fingerprinting techniques described in this paper.

Today, a large body of research exists regarding the correctness of routing protocols. However, many reported global disruptions of Internet connectivity, e.g., inter-AS persistent loops, cannot be explained by looking at a single routing protocol at a time. In fact, these anomalies have long been suspected in the operator community to be caused by the interactions between routing protocols. The interactions between protocol instances are governed by two procedures at the border routers: route selection (RS) ranks routes from different protocol instances; and route redistribution (RR) exchanges routes between protocol instances. Prior studies hypothesized that RR may be responsible for a portion of the observed anomalies. In this paper, we provide analytical and experimental results to link RS, RR, and their interplay to anomalies discovered in operational networks. We show that RS by itself can cause route oscillations and loops, and that in all Cisco, Quagga, and XORP implementations, non-deterministic behaviors may occur because of their incorrect modeling of the dependencies between RS and RR. We identify the root cause for each of the instabilities and derive a configuration guideline as well as a functional model to eliminate them.

Entropy-based approaches for anomaly detection are appealing since they provide more fine-grained insights than traditional traffic volume analysis. While previous work has demonstrated the benefits of entropy-based anomaly detection, there has been little effort to comprehensively understand the detection power of using entropy-based analysis of multiple traffic distributions in conjunction with each other. We consider two classes of distributions: flow-header features (IP addresses, ports, and flow-sizes), and behavioral features (degree distributions measuring the number of distinct destination/source IPs that each host communicates with). We observe that the timeseries of entropy values of the address and port distributions are strongly correlated with each other and provide very similar anomaly detection capabilities. The behavioral and flow size distributions are less correlated and detect incidents that do not show up as anomalies in the port and address distributions. Further analysis using synthetically generated anomalies also suggests that the port and address distributions have limited utility in detecting scan and bandwidth flood anomalies. Based on our analysis, we discuss important implications for entropy-based anomaly detection.

Recent studies reveal that the routing structures of operational networks are much more complex than a simple BGP/IGP hierarchy, highlighted by the presence of many distinct instances of routing protocols. However, the glue (how routing protocol instances interact and exchange routes among themselves) is still little understood or studied. For example, although Route Redistribution (RR), the implementation of the glue in router software, has been used in the Internet for more than a decade, it was only recently shown that RR is extremely vulnerable to anomalies similar to the permanent route oscillations in BGP. This paper takes an important step toward understanding how RR is used and how fundamental the role RR plays in practice. We developed a complete model and associated tools for characterizing interconnections between routing instances based on analysis of router configuration data. We analyzed and characterized the RR usage in more than 1600 operational networks. The findings are: (i) RR is indeed widely used; (ii) operators use RR to achieve important design objectives not realizable with existing routing protocols alone; (iii) RR configurations can be very diverse and complex. These empirical discoveries not only confirm that the RR glue constitutes a critical component of the current Internet routing architecture, but also emphasize the urgent need for more research to improve its safety and flexibility to support important design objectives.

There have been tremendous efforts and many technical innovations in supporting real-time video streaming in the past two decades, but cost-effective large-scale video broadcast has remained an elusive goal. Internet protocol (IP) multicast represented an earlier attempt to tackle this problem but failed largely due to concerns regarding scalability, deployment, and support for higher level functionality. Recently, peer-to-peer based broadcast has emerged as a promising technique, which has been shown to be cost effective and easy to deploy. This new paradigm brings a number of unique advantages such as scalability, resilience, and effectiveness in coping with dynamics and heterogeneity. While peer-to-peer applications such as file download and voice-over-IP have gained tremendous popularity, video broadcast is still in its early stages, and its full potential remains to be seen. This paper reviews the state-of-the-art of peer-to-peer Internet video broadcast technologies. We describe the basic taxonomy of peer-to-peer broadcast and summarize the major issues associated with the design of broadcast overlays. We closely examine two approaches - tree-based and data-driven - and discuss their fundamental tradeoff and potential for large-scale deployment. Lastly, we outline the key challenges and open problems and highlight possible avenues for future directions.

Watching video online is becoming increasingly popular, and new video streaming technologies have the potential to transform video watching from a passive, isolating experience into an active, socially engaging experience. However, the viability of an active social experience is unclear: both chatting and watching video require attention, and may interfere with one another and detract from the experience. In this paper, we empirically examine the activity of chatting while watching video online. We examine how groups of friends and strangers interact, and find that chat has a positive influence on social relationships, and people chat despite being distracted. We discuss the benefits and opportunities provided by mixing chat and video, uncover some of the attentional and social challenges inherent in this combination of media, and provide guidance for structuring the viewing experience.

The oncoming prosperity of interactive multimedia application triggers significant challenge to current best-effort Internet because of the dynamic and unpredictable available bandwidth, end-to-end delay, and packet loss. Recently, overlay technique has emerged as an approach to help mitigating these problems. In order to understand the potential benefits of using multi-path provided by overlay network to interactive video, this paper examines the performance of two special multi-path deliver schemes dual-path mesh and dual-path round robin, and compares their metrics of round-trip delay, packet loss, one-way delay jitter to the direct Internet path by analyzing 7 days of data collected from 102 geographically diverse PlanetLab nodes. By mapping the collected data with MPEG-4 coded "Foreman" video sequence, the paper also presents multipath benefit on peak signal-to-noise ratio (PSNR).

Route redistribution (RR) has become an integral part of IP network design as the result of a growing need for disseminating certain routes across routing protocol boundaries. While RR is widely used and resembles BGP in several nontrivial aspects, surprisingly, the safety of RR has not been systematically studied by the networking community. This paper presents the first analytical model for understanding the effect of RR on network wide routing dynamics and evaluating the safety of a specific RR configuration. We first illustrate how easily inaccurate configurations of RR may cause severe routing instabilities, including route oscillations and persistent routing loops. At the same time, general observations regarding the root causes of these instabilities are provided. We then introduce a formal model based on the general observations to represent and study the safety of route redistribution. Using the model, we prove that given a RR configuration, determining whether the redistributions result in a cycle is NP-hard. Given this complexity, we present a sufficient condition, which can be checked in polynomial time with the proposed analytical model, for ensuring the safety of a RR configuration. Finally, the paper proposes potential changes to the current RR protocol to guarantee safety.

Given a large sparse graph, how can we find patterns and anomalies? Several important applications can be modeled as large sparse graphs, e.g., network traffic monitoring, research citation network analysis, social network analysis, and regulatory networks in genes. Low rank decompositions, such as SVD and CUR, are powerful techniques for revealing latent/hidden variables and associated patterns from high dimensional data. However, those methods often ignore the sparsity property of the graph, and hence usually incur too high memory and computational cost to be practical. We propose a novel method, the Compact Matrix Decomposition (CMD), to compute sparse low rank approximations. CMD dramatically reduces both the computation cost and the space requirements over existing decomposition methods (SVD, CUR). Using CMD as the key building block, we further propose procedures to efficiently construct and analyze dynamic graphs from real-time application data. We provide theoretical guarantee for our methods, and present results on two real, large datasets, one on network flow data (100GB trace of 22K hosts over one month) and one on DBLP (200MB over 25 years). We show that CMD is often an order of magnitude more efficient than the state of the art (SVD and CUR): it is over 10X faster, but requires less than 1/10 of the space, for the same reconstruction accuracy. Finally, we demonstrate how CMD is used for detecting anomalies and monitoring time-evolving graphs, in which it successfully detects worm-like hierarchical scanning patterns in real network data.

In recent years, there has been significant interest in adopting the peer-to-peer (P2P) technology for Internet live video streaming. There are primarily two reasons behind this development: the elimination of infrastructure support and the self-scaling property of P2P systems. The success of our system Coolstreaming represented one of the earliest large-scale P2P video streaming experiments. Since then, there have been several large-scale commercial deployments. With desirable content, these systems have the potential to scale orders of magnitude beyond the existing academic P2P prototypes. However, to transform this potential into reality, we need to understand the key design trade-offs and principles, as well as the design limitations of these systems. There are two main design decisions in a P2P streaming system: (i) How to form an overlay, and (ii) How to deliver the content. Coolstreaming adopts a gossiping protocol for overlay construction, and a swarm-based protocol for content delivery. While these protocols provide excellent flexibility and effectiveness in dealing with system dynamics and random failure, their impact on the performance and the system scalability remain less known. This paper takes an inside look at a commercial system based on the Coolstreaming, called Coolstreaming+. We explore its design choices and the impact of these choices on streaming performance. Specifically, by using internal traces generated by recent live broadcast events, we study the workload, performance, and dynamics of the system. Based on these traces, we show that (1) the churn is the most critical factor that affects the overall performance of the system, and (2) there is a highly skew resource distribution in P2P streaming systems, which has significant impact on resource allocation. We further discuss the impact of these observations on the system properties, and present solutions to deal with various design challenges. In particular, we suggest solutions to deal with the excessive start-up time and high failure rates during flash crowd, which are two of the main challenges any streaming system needs to address.

Despite the proliferation of detection and containment techniques in the worm defense literature, simple threshold-based methods remain the most widely deployed and most popular approach among practitioners. This popularity arises out of the simplistic appeal, ease of use, and independence from attack-specific properties such as scanning strategies and signatures. However, such approaches have known limitations: they either fail to detect low-rate attacks or incur very high false positive rates. We propose a multi-resolution approach to enhance the power of threshold-based detection and rate-limiting techniques. Using such an approach we can not only detect fast attacks with low latency, but also discover low-rate attacks - several orders of magnitude less aggressive than today’s fast propagating attacks with low false positive rates. We also outline a multi-resolution rate limiting mechanism for throttling the number of new connections a host can make, to contain the spread of worms. Our trace analysis and simulation experiments demonstrate the benefits of a multiresolution approach for worm defense.

The prosperity of various real-time applications triggers significant challenges for the Internet to meet the critical end-to-end delay requirements. This paper investigates the feasibility and practical issues of using overlay routing to improve end-to-end delay performance, with the analysis of round trip time data collected over three months by the all pairs pings project between each pair of hundreds of nodes on the Planet- Lab. The results show: 1) overlay routing has the potential to reduce the round trip time by 40 milliseconds and increase network connectivity by 7% on average; 2) even simple static overlay paths can reduce end-to-end delay, while the dynamic algorithm does better; 3) Over 80% of the shortest overlay paths have no more than 4 hops, and a simple algorithm leveraging only one relay node can efficiently take the advantages of overlay routing.

We present the design of a Network Forensic Alliance (NFA), to allow multiple administrative domains (ADs) to jointly locate the origin of epidemic spreading attacks. ADs in the NFA collaborate in a distributed protocol for post-mortem analysis of worm-like attacks. Information exchange between any two participating ADs is limited to traffic records that are known to both sides, maintaining the privacy of participants. Such an architecture is incentive-compatible - participants benefit by gaining better local investigative capabilities, even with partial deployment. Further, we show that by sharing local investigation results, ADs can achieve global investigative capabilities that are comparable to a centralized implementation with access to global traffic records. Our evaluation demonstrates that it is feasible for large-scale attack investigation to be incrementally deployed in an Internet-like federation.

While delay-critical applications typified by online multimedia communication are growing rapidly, the end-to-end (E2E) delay behavior in the Internet remains poorly understood. This paper proposes a stochastic process model, in which E2E delay alternations are classified into two categories, jump and perturbation, according to whether the statistical characterizations alter or not. As the chief type of majority delay alternations, perturbations generally occur continuously in a period, and can be analogous to an ergodic stationary process. The authenticity of the model is verified with real life delay measurements in the Internet collected by all pairs pings (APP) project through months from PlanetLab nodes. Based on the model, several delay estimation algorithms are comparatively analyzed, and the experimental results demonstrate that in terms of minimizing the mean squared error, the most accurate delay prediction is the minimum of the two most recent measurements.

Despite the existence of several secure BGP routing protocols, there has been little progress to date on actual adoption. Although feasibility for widespread adoption remains the greatest hurdle for BGP security, there has been little quantitative research into what properties contribute the most to the adoptability of a security scheme. In this paper, we provide a model for assessing the adoptability of a secure BGP routing protocol. We perform this evaluation by simulating incentives compatible adoption decisions of ISPs on the Internet under a variety of assumptions. Our results include: (a) the existence of a sharp threshold, where, if the cost of adoption is below the threshold, complete adoption takes place, while almost no adoption takes place above the threshold; (b) under a strong attacker model, adding a single hop of path authentication to origin authentication yields similar adoptability characteristics as a full path security scheme; (c) under a weaker attacker model, adding full path authentication (e.g., via S-BGP [9]) significantly improves the adoptability of BGP security over weaker path security schemes such as soBGP [16]. These results provide insight into the development of more adoptable secure BGP protocols and demonstrate the importance of studying adoptability of protocols.

The primary purpose of a network is to provide reachability between applications running on end hosts. In this paper, we describe how to compute the reachability a network provides from a snapshot of the configuration state from each of the routers. Our primary contribution is the precise definition of the potential reachability of a network and a substantial simplification of the problem through a unified modeling of packet filters and routing protocols. In the end, we reduce a complex, important practical problem to computing the transitive closure to set union and intersection operations on reachability set representations. We then extend our algorithm to model the influence of packet transformations (e.g., by NATs or ToS remapping) along the path. Our technique for static analysis of network reachability is valuable for verifying the intent of the network designer, troubleshooting reachability problems, and performing "what-if" analysis of failure scenarios.

We propose a novel technique that can determine both the host responsible for originating a propagating worm attack and the set of attack flows that make up the initial stages of the attack tree via which the worm infected successive generations of victims. We argue that knowledge of both is important for combating worms: knowledge of the origin supports law enforcement, and knowledge of the causal flows that advance the attack supports diagnosis of how network defenses were breached. Our technique exploits the "wide tree" shape of a worm propagation emanating from the source by performing random "moonwalks" backward in time along paths of flows. Correlating the repeated walks reveals the initial causal flows, thereby aiding in identifying the source. Using analysis, simulation, and experiments with real world traces, we show how the technique works against both today's fast propagating worms and stealthy worms that attempt to hide their attack flows among background traffic.

Internet video delivery has been motivating research in multicast routing, quality of service (QoS), and the service model of the Internet itself for the last 15 years. Multicast delivery has the potential to deliver a large amount of content that currently cannot be delivered through broadcast. IP and overlay multicast are two architectures proposed to provide multicast support. A large body of research has been done with IP multicast and QoS mechanisms for IP multicast since the late 1980s. In the past five years, overlay multicast research has gained momentum with a vision to accomplish ubiquitous multicast delivery that is efficient and scales in the dimensions of the number of groups, number of receivers, and number of senders. This work presents an overview of the issues facing both IP and overlay multicast and the approaches that researchers are taking to solve them. Many of these approaches take advantage of a rich interface, beyond a single rate video stream, between the coding and delivery mechanisms. The semantics of this interface is an important question for future research and we discuss this with insight from experience on delivery technologies.

A repository of router configuration files from production networks would provide the research community with a treasure trove of data about network topologies, routing designs, and security policies. However, configuration files have been largely unobtainable precisely because they provide detailed information that could be exploited by competitors and attackers. This paper describes a method for anonymizing router configuration files by removing all information that connects the data to the identity of the originating network, while still preserving the structure of information that makes the data valuable to networking researchers. Anonymizing configuration files has unusual requirements, including preserving relationships between elements of data, anonymizing regular expressions, and robustly coping with more than 200 versions of the configuration language, that mean conventional tools and techniques are poorly suited to the problem. Our anonymization method has been validated with a major carrier, earning unprivileged researchers access to the configuration files of more than 7600 routers in 31 networks. Through example analysis, we demonstrate that the anonymized data retains the key properties of the network design. We believe that applying our single-blind methodology to a large number of production networks from different sources would be of tremendous value to both the research and operations communities.

In this paper, we study the live streaming workload from a large content delivery network. Our data, collected over a 3 month period, contains over 70 million requests for 5,000 distinct URLs from clients in over 200 countries. To our knowledge, this is the most extensive data of live streaming on the Internet that has been studied to date. Our contributions are two-fold. First, we present a macroscopic analysis of the workload, characterizing popularity, arrival process, session duration, and transport protocol use. Our results show that popularity follows a 2-mode Zipf distribution, session interarrivals within small time-windows are exponential, session durations are heavy-tailed, and that UDP is far from having universal reach on the Internet. Second, we cover two additional characteristics that are more specific to the nature of live streaming applications: the diversity of clients in comparison to traditional broadcast media like radio and TV, and the phenomena that many clients regularly join recurring events. We find that Internet streaming does reach a wide audience, often spanning hundreds of AS domains and tens of countries. More interesting is that small streams also have a diverse audience. We also find that recurring users often have lifetimes of at least as long as one-third of the days in the event.

In peer-to-peer overlay or video broadcast, peers contribute a portion of the bandwidth to the overlay in return or the service. In the presence of network heterogeneity, it is not well understood how much bandwidth peers should contribute and receive in return. Existing protocols implicitly assume peers are either completely altruistic (which leads to airness concerns) or completely selfish (which leads to sub-optimal performance). In this paper, we argue that altruism should be explicitly considered. We propose a policy framework in which a wide range of altruism can be modeled and parameterized. The key findings are (i) the level of altruism has significant implication on the overall performance of the receivers; even a small degree of altruism goes a long way in improving their performance, and (ii) a wide range of altruism policy can be implemented efficiently in a distributed fashion. We validate these claims using simulation, with traces from real Internet broadcast events.

A large number of overlay multicast protocols have been developed, almost all of which assume universal connectivity between end hosts. However, in reality, this assumption is not valid with widespread use of Network Address Translators (NAT) and firewalls. The impact of NAT and firewall connectivity restrictions on overlay multicast, es-pecially in the application-endpoint setting, has not been seriously considered. In this paper, we argue that it is critical to consider con-nectivity restrictions because NAT and firewall hosts make up a large fraction of the endpoints, affecting proper functionality as well as performance of overlay multicast protocols. We present several de-sign enhancements that explicitly consider connectivity restrictions in overlay multicast and evaluate the design space and tradeoffs based on real Internet broadcasts and Internet testbed experiments.

While application end-point architectures have proven to be viable solutions for large-scale distributed applications such as distributed computing and file-sharing, there is little known about its feasibility for more bandwidth-demanding applications such as live streaming. Heterogeneity in bandwidth resources and dynamic group membership, inherent properties of application end-points, may adversely affect the construction of a usable and efficient overlay. At large scales, the problems become even more challenging. In this paper, we study one of the most prominent architectural issues in overlay multicast: the feasibility of supporting large-scale groups using an application end-point architecture. We look at three key requirements for feasibility: (i) are there enough resources to construct an overlay, (ii) can a stable and connected overlay be maintained in the presence of group dynamics, and (iii) can an efficient overlay be constructed? Using traces from a large content delivery network, we characterize the behavior of users watching live audio and video streams. We show that in many common real-world scenarios, all three requirements are satisfied. In addition, we evaluate the performance of several design alternatives and show that simple algorithms have the potential to meet these requirements in practice. Overall, our results argue for the feasibility of supporting large-scale live streaming using an application end-point architecture.

In any IP network, routing protocols provide the intelligence that takes a collection of physical links and transforms them into a network that enables packets to travel from one host to another. Though routing design is arguably the single most important design task for large IP networks, there has been very little systematic investigation into how routing protocols are actually used in production networks to implement the goals of network architects. We have developed a methodology for reverse engineering a coherent global view of a network's routing design from the static analysis of dumps of the local configuration state of each router. Starting with a set of 8,035 configuration files, we have applied this method to 31 production networks. In this paper we present a detailed examination of how routing protocols are used in operational networks. In particular, the results show the conventional model of interior and exterior gateway protocols is insufficient to describe the diverse set of mechanisms used by architects, and we provide examples of the more unusual designs and examine their trade-offs. We discuss the strengths and weaknesses of our methodology, and argue that it opens paths towards new understandings of network behavior and design.

Measurement-based optimization is one important strategy to improve the performance of bandwidth-demanding peer-to-peer systems. However, to date, we have little quantitative knowledge of how well basic lightweight measurement-based techniques such as RTT probing, 10KB TCP probing, and bottleneck bandwidth probing may work in practice in the peer-to-peer environment. By conducting trace-based analyses, we find that the basic techniques can help achieve 40 to 50% optimal performance. To deepen our understanding, we analyze some of the intrinsic properties of these techniques. Our analyses reveal the inherent difficulty of the peer selection problem due to the extreme heterogeneity in the peer-to-peer environment, and that the basic techniques are limited because their primary strength lies in eliminating the low-performance peers rather than reliably identifying the best-performing one. However, our analyses also reveal two key insights that can potentially be exploited by applications. First, for adaptive applications that can continuously change communication peers, the basic techniques are highly effective in guiding the adaption process. In our experiments, typically an 80% optimal peer can be found by trying less than 5 candidates. Secondly, we find that the basic techniques are highly complementary and can potentially be combined to better identify a high-performance peer, thus even applications that cannot adapt may benefit. Using media file sharing and overlay multicast streaming as case studies, we have systematically experimented with several simple combined peer selection techniques. Our results show that for the nonadaptive media file sharing application, a simple combined technique can boost performance to 60% optimal. In contrast, for the continuously adaptive overlay multicast application, we find that a basic technique with even low-fidelity network information is sufficient to ensure good performance. We believe our findings will help guide the future designs of high-performance peer-to-peer systems.

Locating content in decentralized peer-to-peer systems is a challenging problem. Gnutella, a popular file-sharing application, relies on flooding queries to all peers. Although flooding is simple and robust, it is not scalable. We explore how to retain the simplicity of Gnutella, while addressing its inherent weakness: scalability. We propose a content location solution in which peers loosely organize themselves into an interest-based structure on top of the existing Gnutella network. Our approach exploits a simple, yet powerful principle called interest-based locality, which posits that if a peer has a particular piece of content that one is interested in, it is very likely that it will have other items that one is interested in as well. When using our algorithm, called interest-based shortcuts, a significant amount of flooding can be avoided, making Gnutella a more competitive solution. In addition, shortcuts are modular and can be used to improve the performance of other content location mechanisms including distributed hash table schemes. We demonstrate the existence of interest-based locality in five diverse traces of content distribution applications, two of which are traces of popular peer-to-peer file-sharing applications. Simulation results show that interest-based shortcuts often resolve queries quickly in one peer-to-peer hop, while reducing the total load in the system by a factor of 3 to 7.

Router mechanisms designed to achieve fair bandwidth allocations, such as fair queueing, have many desirable properties for congestion control in the Internet. However, such mechanisms usually need to maintain state, manage buffers, and/or perform packet scheduling on a per-flow basis, and this complexity may prevent them from being cost-effectively implemented and widely deployed. We propose an architecture that significantly reduces this implementation complexity yet still achieves approximately fair bandwidth allocations. We apply this approach to an island of routers - that is, a contiguous region of the network - and we distinguish between edge routers and core routers. Edge routers maintain per-flow state; they estimate the incoming rate of each flow and insert a label into each packet based on this estimate. Core routers maintain no per-flow state; they use first-in-first-out packet scheduling augmented by a probabilistic dropping algorithm that uses the packet labels and an estimate of the aggregate traffic at the router. We call the scheme core-stateless fair queueing. We present simulations and analysis on the performance of this approach.

We propose using coordinates-based mechanisms in a peer-to-peer architecture to predict Internet network distance (i.e. round-trip propagation and transmission delay). We study two mechanisms. The first is a previously proposed scheme, called the triangulated heuristic, which is based on relative coordinates that are simply the distances from a host to some special network nodes. We propose the second mechanism, called global network positioning (GNP), which is based on absolute coordinates computed from modeling the Internet as a geometric space. Since end hosts maintain their own coordinates, these approaches allow end hosts to compute their inter-host distances as soon as they discover each other. Moreover, coordinates are very efficient in summarizing inter-host distances, making these approaches very scalable. By performing experiments using measured Internet distance data, we show that both coordinates-based schemes are more accurate than the existing state of the art system IDMaps, and the GNP approach achieves the highest accuracy and robustness among them.

Previously, a class of solutions including core-stateless fair queueing (CSFQ), rainbow fair queueing, and Diffserv have been proposed to address the scalability concerns that have plagued stateful architectures such as Intserv and fair queueing. However, despite some desirable properties, these solutions still have serious scalability, robustness, and deployment problems. Their scalability, suffers from the fact that the core cannot transcend trust boundaries (such as at ISP-ISP interconnects), and so the high-speed routers on these boundaries must maintain per flow or per aggregate state. The lack of robustness is because a single malfunctioning edge or core router could severely impact the performance of the entire network. The deployability is hampered because the set of routers must be carefully configured with a well-defined set of edge routers surrounding the core. In this paper, we propose an approach to address these limitations. The main idea is to use statistical verification to identify and contain the flows whose packets carry incorrect information. To demonstrate the applicability of this approach we develop an extension of CSFQ, called self-verifying CSFQ (SV-CSFQ). With SV-CSFQ, rate estimation is performed by sending hosts, and all routers statistically verify these rate estimates. Statistical verification allows routers to identify misbehaving flows and routers, and thereby protect other flows. This makes our approach robust and highly scalable as it eliminates the need for stateful routers at trust boundaries, and for the core-edge distinction. We present simulations and analysis of the performance of this approach, and discuss its general applicability to provide other scalable and robust network services.

The conventional wisdom has been that Internet protocol (IP) is the natural protocol layer for implementing multicast related functionality. However, more than a decade after its initial proposal, IP multicast is still plagued with concerns pertaining to scalability, network management, deployment, and support for higher layer functionality such as error, flow, and congestion control. We explore an alternative architecture that we term end system multicast, where end systems implement all multicast related functionality including membership management and packet replication. This shifting of multicast support from routers to end systems has the potential to address most problems associated with IP multicast. However, the key concern is the performance penalty associated with such a model. In particular, end system multicast introduces duplicate packets on physical links and incurs larger end-to-end delays than IP multicast. We study these performance concerns in the context of the Narada protocol. In Narada, end systems self-organize into an overlay structure using a fully distributed protocol. Further, end systems attempt to optimize the efficiency of the overlay by adapting to network dynamics and by considering application level performance. We present details of Narada and evaluate it using both simulation and Internet experiments. Our results indicate that the performance penalties are low both from the application and the network perspectives. We believe the potential benefits of transferring multicast functionality from end systems to routers significantly outweigh the performance penalty incurred.

RIO routers, initially proposed in the context of differentiated services networks, distinguish between two classes or packets - in-profile and out-profile - based on a one-bit marking in packet headers. Traditionally, packet-marking is performed by ingress routers according to a user-profile specified in terms of bandwidth. We consider an alternative strategy in which packets are marked based on the state of individual TCP flows. This marking scheme can be implemented either at the end systems or ingress routers (thus avoiding changes at end systems). In addition, we present a variant of our scheme that integrates the Diffserv style packet-marking based on the user-profile. By extensive simulations, we demonstrate that the proposed scheme can significantly reduce the completion time of TCP flows. In particular, the completion time of short TCP flows is halved. These results are consistent over different TCP variants and in the presence of ECN.

The current Web caching infrastructure, though it has a number of performance benefits for clients and network providers, does not meet publishers' requirements. We argue that to satisfy these requirements, caches should be enhanced in both the data and control planes. In the data plane, caches will dynamically generate content for clients by running code provided by publishers. In the control plane, caches will return logs of client accesses to publishers. In this paper, we introduce Gemini, a system which has both of these capabilities, and discuss two of its key components: security and incremental deployment. Since Gemini caches are deeply involved in content preparation and logging, ensuring that they perform correctly is vital. Traditional end-to-end security mechanisms are not sufficient to protect clients and publishers, so we introduce a new security model which consists of two pieces: an authorization mechanism and a verification mechanism. The former allows a publisher to authorize a set of caches to run its code and serve its content, while the latter allows clients and publishers to probabilistically verify that authorized caches are operating correctly. Because it is unrealistic to assume that Gemini caches will be deployed everywhere simultaneously, we have designed the system to be incrementally deployable and to coexist with legacy clients, caches, and servers. Finally, we describe our implementation of Gemini and present preliminary performance results.

In response to the serious scalability and deployment concerns with IP Multicast, we and other researchers have advocated an alternate architecture for supporting group communication applications over the Internet where all multicast functionality is pushed to the edge. We refer to such an architecture as End System Multicast. While End System Multicast has several potential advantages, a key concern is the performance penalty associated with such a design. While preliminary simulation results conducted in static environments are promising, they have yet to consider the challenging performance requirements of real world applications in a dynamic and heterogeneous Internet environment.In this paper, we explore how Internet environments and application requirements can influence End System Multicast design. We explore these issues in the context of audio and video conferencing: an important class of applications with stringent performance requirements. We conduct an extensive evaluation study of schemes for constructing overlay networks on a wide-area test-bed of about twenty hosts distributed around the Internet. Our results demonstrate that it is important to adapt to both latency and bandwidth while constructing overlays optimized for conferencing applications. Further, when relatively simple techniques are incorporated into current self-organizing protocols to enable dynamic adaptation to latency and bandwidth, the performance benefits are significant. Our results indicate that End System Multicast is a promising architecture for enabling performance-demanding conferencing applications in a dynamic and heterogeneous Internet environment.

We propose a new multicast protocol called REUNITE. The key idea of REUNITE is to use recursive unicast trees to implement multicast service. REUNITE does not use class D IP addresses. Instead, both group identification and data forwarding are based on unicast IP addresses. Compared with existing IP multicast protocols, REUNITE has several unique properties. First, only routers that are acting as multicast tree branching points for a group need to keep the multicast forwarding state of the group. All other non-branching-point routers simply forward data packets by unicast routing. In addition, REUNITE can be incrementally deployed in the sense that it works even if only a subset of the routers implement the protocol. Furthermore, REUNITE supports load balancing and graceful degradation such that when a router does not have resources (forwarding table entry, buffer space, processing power) to support additional multicast groups, the branching can be automatically migrated to other less-loaded routers. Finally, sender access control can be easily supported in REUNITE.

The traditional approach to implementing admission control, as exemplified by the Integrated Services proposal in the IETF, uses a signalling protocol to establish reservations at all routers along the path. While providing excellent quality-of-service, this approach has limited scalability because it requires routers to keep per-flow state and to process per-flow reservation messages. In an attempt to implement admission control without these scalability problems, several recent papers have proposed various forms of endpoint admission control. In these designs, the hosts (the endpoints) probe the network to detect the level of congestion; the host admits the flow only if the detected level of congestion is sufficiently low. This paper is devoted to the study of endpoint admission control. We first consider several architectural issues that guide (and constrain) the design of such systems. We then use simulations to evaluate the performance of endpoint admission control in various settings. The modest performance degradation between traditional router-based admission control and endpoint admission control suggests that a real-time service based on endpoint probing may be viable.

The conventional wisdom has been that IP is the natural protocol layer for implementing multicast related functionality. However, ten years after its initial proposal, IP Multicast is still plagued with concerns pertaining to scalability, network management, deployment and support for higher layer functionality such as error, flow and congestion control. In this paper, we explore an alternative architecture for small and sparse groups, where end systems implement all multicast related functionality including membership management and packet replication. We call such a scheme End System Multicast. This shifting of multicast support from routers to end systems has the potential to address most problems associated with IP Multicast. However, the key concern is the performance penalty associated with such a model. In particular, End System Multicast introduces duplicate packets on physical links and incurs larger end-to-end delay than IP Multicast. In this paper, we study this question in the context of the Narada protocol. In Narada, end systems self-organize into an overlay structure using a fully distributed protocol. In addition, Narada attempts to optimize the efficiency of the overlay based on end-to-end measurements. We present details of Narada and evaluate it using both simulation and Internet experiments. Preliminary results are encouraging. In most simulations and Internet experiments, the delay and bandwidth penalty are low. We believe the potential benefits of repartitioning multicast functionality between end systems and routers significantly outweigh the performance penalty incurred.

We study hierarchical resource management models and algorithms that support both link-sharing and guaranteed real-time services with priority (decoupled delay and bandwidth allocation). We extend the service curve based quality of service (QoS) model, which defines both delay and bandwidth requirements of a class in a hierarchy, to include fairness, which is important for the integration of real-time and hierarchical link-sharing services. The resulting fair service curve (FSC) link-sharing model formalizes the goals of link-sharing, real-time and priority services and exposes the fundamental trade-offs between these goals. In particular, with decoupled delay and bandwidth allocation, it is impossible to simultaneously provide guaranteed real-time service and achieve perfect link-sharing. We propose a novel scheduling algorithm called hierarchical fair service curve (H-FSC) that approximates the model closely and efficiently. The algorithm always guarantees the service curves of leaf classes, thus ensures real-time and priority services, while trying to minimize the discrepancy between the actual services provided to and the services defined by the FSC link-sharing model for the interior classes. We have implemented the H-FSC scheduler in NetBSD. By performing analyzes, simulations and measurement experiments, we evaluate the link-sharing and real-time performances of H-FSC, and determine the computation overhead.

As a growing number of Web sites introduce mirrors to increase throughput, the challenge for clients is determining which mirror will offer the best performance when a document is to be retrieved. We present findings from measuring 9 clients scattered throughout the United States retrieving over 490,000 documents from 47 production Web servers which mirror three different Web sites. We have several interesting findings that may aid in the design of protocols for choosing among mirror servers. Though server performance varies widely, we have observed that a server's performance relative to other servers is more stable and is independent of time scale. In addition, a change in an individual server's transfer time is not a strong indicator that its performance relative to other servers has changed. Finally, we have found that clients wishing to achieve near-optimal performance may only need to consider a small number of servers rather than all mirrors of a particular site.

Existing approaches for providing guarant.eed services re-quire routers to manage per fiow states and perform per flow operations [9, 211. Such a statefIr / network architecture is less scalable and robusl than stateless network architectures like the original IP and the recently proposed Diffserv [3]. However, services provided with current stateless solutions, Diffserv included, have lower flexibility, utilization, and/or assurance level as compared to the services that can be pro-vided with per flow mechanisms. In this paper, we propose techniques that do not require per flow management (either control or data planes) at core routers, but can implement guaranteed services with levels of flexibility, utilization, and assurance similar to those that can be provided with per flow mechanisms. In this way we can simultaneously achieve high quality of service, high scal-ability and robustness. The key technique we use is called Dynamic Packet State (DPS), which provides a lightweighl; and robust mechanism for routers to coordinate actions and implement distributed algorithms. We present an imple-mentation of the proposed algorithms that has minimum incompatibility with IPvI. 1

No abstract available.

We propose a third-party value-added services framework for enhancing the performance of reliable multicast protocols.In this framework, a value-added service provider will place servers called waypoints throughout ISPs' networks.Waypoints run a fully distributed, dynamic algorithm to determine which multicast groups to join.Having joined a group, a waypoint participates in the error recovery protocol, supplying repairs to receivers.From the application's perspective, waypoints appear to be additional application endpoints in the network.Waypoints seamlessly interoperate with current reliable multicast algorithms with only a minor change to receivers and no changes to routers.In our implementation, receivers and waypoints use STORM, a structure-based error recovery protocol.The waypoint recovery service is not limited to one error recovery protocol, and can be extended to enhance other reliable multicast protocols.Results from simulation experiments are presented to evaluate the potential benefits of theproposed scheme.We find that when multicast group members are isolated from each other, a waypoint recovery service can significantly enhance receivers' performance.

The fluid generalized processor sharing (GPS) algorithm has desirable properties for integrated services networks and many packet fair queueing (PFQ) algorithms have been proposed to approximate GPS. However, there have been few high-speed implementations of PFQ algorithms that can support a large number of sessions with diverse rate requirements and at the same time maintain all the important properties of GPS. The implementation cost of a PFQ algorithm is determined by: (1) computation of the system virtual time function; (2) maintenance of the relative ordering of the packets via their timestamps (scheduling); and (3) regulation of packets based on eligibility time, in some algorithms. While most of the recently proposed PFQ algorithms reduce the complexity of computing the system virtual time function, the complexity of scheduling and traffic regulation is still a function of the number of active sessions. In addition, while reducing the algorithmic or asymptotic complexity has been the focus of most analysis, it is also important to reduce the complexity of basic operations in order for the algorithm to run at high speed. We develop techniques to reduce both types of complexities for networks of both fixed and variable size packets. Regulation and scheduling are implemented in an integrated architecture that can be viewed as logically performing sorting in two dimensions simultaneously. By using a novel grouping architecture, we are able to perform this with an algorithmic complexity independent of the number of sessions in the system at the cost of a small controllable amount of relative error. To reduce the cost of basic operations, we propose a hardware-implementation framework and several novel techniques that reduce the on-chip memory size, off-chip memory bandwidth, and off-chip access latency. The proposed implementation techniques have been incorporated into commercial ATM switch and IP router products.

The Internet is rapidly changing from a set of wires and switches that carry packets into a sophisticated infrastructure that delivers a set of complex value-added services to end users. Services can range from bit transport all the way up to distributed value-added services like video teleconferencing, data mining, and distributed interactive simulations. Before such services can be supported in a general and dynamic manner we have to develop appropriate resource management mechanisms. These resource management mechanisms must make it possible to identify and allocate resources that meet service or application requirements, support both isolation and controlled dynamic sharing of resources across organizations sharing physical resources, and be customizable so services and applications can tailor resource usage to optimize their performance. The Darwin project is developing a set of customizable resource management mechanisms that support value-added services, In this paper we present these mechanisms, describe their implementation in a prototype system, and describe the results of a series of proof-of-concept experiments.

While packet fair queueing (PFQ) algorithms provide both bounded delay and fairness in wired networks, they cannot be applied directly to wireless networks. The key difficulty is that in wireless networks sessions can experience location-dependent channel errors. This may lead to situations in which a session receives significantly less service than it is supposed to, while another receives more. This results in large discrepancies between the sessions' virtual times, making it difficult to provide both delay-guarantees and fairness simultaneously. Our contribution is twofold. First, we identify a set of properties, called channel-condition independent fair (CIF), that a packet fair queueing algorithm should have in a wireless environment: (1) delay and throughput guarantees for error-free sessions, (2) long term fairness for error sessions, (3) short term fairness for error-free sessions, and (4) graceful degradation for sessions that have received excess service. Second, we present a methodology for adapting PFQ algorithms for wireless networks and we apply this methodology to derive a novel algorithm based on start-time fair queueing, called channel-condition independent packet fair queueing (CIF-Q), that achieves all the above properties. To evaluate the algorithm we provide both theoretical analysis and simulation results.

To support the Internet's growth, there is a need for cost effective switching technologies that can simultaneously provide high capacity switching and advanced QoS. Unfortunately, these two goals are largely believed to be contradictory in nature. To support QoS, sophisticated packet scheduling algorithms, such as fair queueing, are needed to manage queueing points. However, the bulk of current research in packet scheduling algorithms assumes an output buffered switch architecture, whereas most high performance switches are input buffered. While output buffered systems may have the desired QoS, they lack the necessary scalability. Input buffered systems, while scalable, lack the necessary QoS features. We propose the construction of switching systems that are both input and output buffered with the scalability of input buffered switches and the robust QoS of output buffered switches. We call the resulting architecture distributed packet fair queueing (D-PFQ) as it enables physically dispersed line cards to provide a service that closely approximates an output-buffered switch with fair queueing. By equalizing the growth of the virtual time functions across the switch system, most of the PFQ algorithms in the literature can be properly defined for distributed operation. We present our system using a cross bar for the switch core. Buffering techniques are used to enhance the system's latency tolerance, which enables the use of pipelining and variable packet sizes internally. We evaluate the delay and bandwidth sharing properties.

Router mechanisms designed to achieve fair bandwidth allocations, like Fair Queueing, have many desirable properties for congestion control in the Internet. However, such mechanisms usually need to maintain state, manage buffers, and/or perform packet scheduling on a per flow basis, and this complexity may prevent them from being cost-effectively implemented and widely deployed. In this paper, we propose an architecture that significantly reduces this implementation complexity yet still achieves approximately fair bandwidth allocations. We apply this approach to an island of routers --- that is, a contiguous region of the network --- and we distinguish between edge routers and core routers. Edge routers maintain per flow state; they estimate the incoming rate of each flow and insert a label into each packet header based on this estimate. Core routers maintain no per flow state; they use FIFO packet scheduling augmented by a probabilistic dropping algorithm that uses the packet labels and an estimate of the aggregate traffic at the router. We call the scheme Core-Stateless Fair Queueing. We present simulations and analysis on the performance of this approach, and discuss an alternate approach.

The fluid generalized processor sharing (GPS) algorithm has desirable properties for integrated services networks and many packet fair queueing (PFQ) algorithms have been proposed to approximate GPS. However, there have been few high speed implementations of PFQ algorithms that can support large number of sessions with diverse rate requirements and at the same time maintain all the important properties of GPS. The implementation cost of a PFQ algorithm is determined by two components: (1) computation of the system virtual time function and (2) maintaining the relative ordering of the packets via their timestamps in a priority queue mechanism. While most of the recently proposed PFQ algorithms reduce the complexity of computing the system virtual time function, the complexity of maintaining the priority queue, and therefore the overall complexity of implementing PFQ, is still a function of the number of active sessions. In addition, while reducing the algorithmic or asymptotic complexity has been the focus of most analysis, to run at high speed, it is also important to reduce the complexity of basic operations. In this paper, we develop techniques to reduce both types of complexities. In particular, we present a novel grouping architecture for implementing PFQ with an algorithmic complexity that is a function of the number of distinct rates supported, but independent of the number of sessions in the system.

In this paper, we study hierarchical resource management models and algorithms that support both link-sharing and guaranteed real-time services with decoupled delay (priority) and bandwidth allocation. We extend the service curve based QoS model, which defines both delay and bandwidth requirements of a class, to include fairness, which is important for the integration of real-time and hierarchical link-sharing services. The resulting Fair Service Curve link-sharing model formalizes the goals of link-sharing and real-time services and exposes the fundamental tradeoffs between these goals. In particular, with decoupled delay and band-width allocation, it is impossible to simultaneously provide guaranteed real-time service and achieve perfect link-sharing. We propose a novel scheduling algorithm called Hierarchical Fair Service Curve (H-FSC) that approximates the model closely and efficiently. The algorithm always guarantees the performance for leaf classes, thus ensures real-time services, while minimizing the discrepancy between the actual services provided to the interior classes and the services defined by the Fair Service Curve link-sharing model. We have implemented the H-FSC scheduler in the NetBSD environment. By performing simulation and measurement experiments, we evaluate the link-sharing and real-time performances of H-FSC, and determine the computation over-head.

We propose to use the idealized hierarchical generalized processor sharing (H-GPS) model to simultaneously support guaranteed real-time, rate-adaptive best-effort, and controlled link-sharing services. We design hierarchical packet fair queueing (H-PFQ) algorithms to approximate H-GPS by using one-level variable-rate PFQ servers as basic building blocks. By computing the system virtual time and per packet virtual start/finish times in unit of bits instead of seconds, most of the PFQ algorithms in the literature can be properly defined as variable-rate servers. We develop techniques to analyze delay and fairness properties of variable-rate and hierarchical PFQ servers. We demonstrate that in order to provide tight delay bounds with an H-PFQ server, it is essential for the one-level PFQ servers to have small worst-case fair indices (WFI). We propose a new PFQ algorithm called WF/sup 2/Q+ that is the first to have all the following three properties: (1) providing the tightest delay bound among all PFQ algorithms; (2) having the smallest WFI among all PFQ algorithms; and (3) having a relatively low asymptotic complexity of O(log N). Simulation results are presented to evaluate the delay and link-sharing properties of H-WF/sup 2/Q+, H-WFQ, H-SFQ, and H-SCFQ.

Variable bit-rate traffic that requires a bounded-delay network service is one of the most important types of traffic in future integrated services networks. We introduce a new deterministic traffic model called deterministic bounding interval-length dependent (D-BIND) to capture the important multiplexing properties of bursty streams. With the D-BIND model, clients specify their traffic to the network via multiple rate-interval pairs (R/sub k/, I/sub k/), where a rate R/sub k/ is a bounding or worst case rate over every interval of length I/sub k/. The model captures the intuitive property that, over longer interval lengths, a source may be bounded by a rate lower than its peak rate and closer to its long-term average rate. We analyze the new model in the context of a deterministic service, and we quantify its performance benefits using a set of experiments with traces of MPEG-compressed video. We show that D-BIND's more accurate characterization of traffic streams leads to substantial improvements in network utilization as compared to previous traffic models.

The generalized processor sharing (GPS) discipline is proven to have two desirable properties: (a) it can provide an end-to-end bounded-delay service to a session whose traffic is constrained by a leaky bucket; (b) it can ensure fair allocation of bandwidth among all back logged sessions regardless of whether or not their traffic is constrained. The former property is the basis for supporting guaranteed service traffic while the later property is important for supporting best-effort service traffic. Since GPS uses an idealized fluid model which cannot be realized in the real world, various packet approximation algorithms of the GPS have been proposed. Among these, weighted fair queueing (WFQ) also known as packet generalized processor sharing (PGPS) has been considered to be the best one in terms of accuracy. In particular, it has been proven that the delay bound provided by WFQ is within one packet transmission time of that provided by GPS. We show that, contrary to popular belief there could be large discrepancies between the services provided by the packet WFQ system and the fluid GPS system. We argue that such a discrepancy will adversely effect many congestion control algorithms that rely on services similar to those provided by GPS. A new packet approximation algorithm of GPS called worst-case fair weighted fair queueing (WF/sup 2/Q) is proposed. The service provided by WF/sup 2/Q is almost identical to that of GPS, differing no more than one maximum size packet.

Hierarchical Packet Fair Queueing (H-PFQ) algorithms have the potential to simultaneously support guaranteed real-time service, rate-adaptive best-effort, and controlled link-sharing service. In this paper, we design practical H-PFQ algorithms by using one-level Packet Fair Queueing (PFQ) servers as basic building blocks, and develop techniques to analyze delay and fairness properties of the resulted H-PFQ servers. We demonstrate that, in order to provide tight delay bounds in a H-PFQ server, it is essential for the one-level PFQ servers to have small Worst-case Fair Indices (WFI). We propose a new one-level PFQ algorithm called WF2Q+ that is the first to have all the following three properties: (a) providing the tightest delay bound among all PFQ algorithms; (b) having the smallest WFI among all PFQ algorithms; and (c) having a relatively low implementation complexity of O(log N). We show that practical H-PFQ algorithms can be implemented by using WF2Q+ as the basic building block and prove that the resulting H-WF2Q+ algorithms provide similar delay bounds and bandwidth distribution as those provided by a H-GPS server. Simulation experiments are presented to evaluate the proposed algorithm.

We study how to improve the throughput of high-bandwidth traffic such as large file transfers in a network where resources are fairly shared among connections. While it is possible to devise priority or reservation-based schemes that give high-bandwidth traffic preferential treatment at the expense of other connections, we focus on the use of routing algorithms that improve resource allocation while maintaining max-min fair share semantics. In our approach, routing is closely coupled with congestion control in the sense that congestion information, such as the rates allocated to existing connections, is used by the routing algorithm. To reduce the amount of routing information that must be distributed, an abstraction of the congestion information is introduced. Using an extensive set of simulation, we identify a link-cost or cost metric for "shortest-path" routing that performs uniformly better than the minimal-hop routing and shortest-widest path routing algorithms. To further improve throughput without reducing the fair share of single-path connections, we propose a novel prioritized multi-path routing algorithm in which low priority paths share the bandwidth left unused by higher priority paths. This leads to a conservative extension of max-min fairness called prioritized multi-level max-min fairness. Simulation results confirm the advantages of our multi-path routing algorithm.

Many future applications will require guarantees on network performance, such as bounds on throughput, delay, delay jitter, and reliability. To address this need, the authors have designed, simulated, and implemented a suite of network protocols to support real-time channels (network connections with mathematically provable performance guarantees). The protocols, which constitute the prototype Tenet real-time protocol suite (Suite 1), run on a packet-switching internetwork and can coexist with the popular Internet protocol suite. The authors rely on the use of connection-oriented communication, per-channel admission control, channel rate control, and priority scheduling. This protocol suite is the first set of transport and network-layer communication protocols that can transfer real-time streams with guaranteed quality in packet-switching internetworks. The authors have performed a number of experiments and demonstrations on multiple platforms using continuous-media loads (particularly video). The results show that the approach is both feasible and practical to build, and that it can successfully provide performance guarantees to real-time applications. The paper describes the design and implementation of, the suite, the experiments performed, and some of the lessons learned.

Compressed digital video is one of the most important traffic types in future integrated services networks. However, a network service that supports delay-sensitive video imposes many problems since compressed video sources are variable bit rate (VBR) with a high degree of burstiness. In this paper, we consider a network service that can provide deterministic guarantees on the minimum throughput and the maximum delay of VBR video traffic. A common belief is that due to the burstiness of VBR traffic, such a service will not be efficient and will necessarily result in low network utilization. We investigate the fundamental limits and trade-offs in providing deterministic performance guarantees to video and use a set of 10 to 30 min. long MPEG-compressed video traces for evaluation. Contrary to conventional wisdom, we are able to show that, in many cases, a deterministic service can be provided to video traffic while maintaining a reasonable level of network utilization. We first consider an ideal network environment that employs the most accurate deterministic, time-invariant video traffic characterizations, the optimal earliest-deadline-first packet schedulers, and exact admission control conditions. The utilization achievable in this situation provides the fundamental limits of a deterministic service. We then investigate the utilization limits in a network environment that takes into account practical constraints, such as the need for simple and efficient policing mechanisms, packet scheduling algorithms, and admission control tests.

The current model for multicast transmission of video over the Internet assumes that a fixed average bandwidth is uniformly present throughout the network. Consequently, sources limit their transmission rates to accommodate the lowest bandwidth links, even though high-bandwidth connectivity might be available to many of the participants. We propose an architecture where a video transmission can be decomposed into multiple sessions with different bandwidth requirements using an application-level gateway. Our video gateway transparently connects pairs of sessions into a single logical conference by manipulating the data and control information of the video streams. In particular, the gateway performs bandwidth adaptation through transcoding and rate-control. We describe an efficient algorithm for transcoding Motion-JPEG to H.261 that runs in real-time on standard workstations. By making the Real-time Transport Protocol (RTP) an integral component of our architecture, the video gateway in...

Compressed digital video is one of the most important traffic types in future integrated services networks. However, a network service that supports delay-sensitive video imposes many problems since compressed video sources are variable bit rate (VBR) with a high degree of burstiness. In this paper, we consider a network service that can provide deterministic guarantees on the minimum throughput and the maximum delay of VBR video traffic. A common belief is that due to the burstiness of VBR traffic, such a service will not be efficient and will necessarily result in low network utilization. We investigate the fundamental limits and tradeoffs in providing deterministic performance guarantees to video and use a set of 10 to 90 minute long MPEG-compressed video traces for evaluation. Contrary to conventional wisdom, we are able to show that, in many cases, a deterministic service can be provided to video traffic while maintaining a reasonable level of network utilization. We first consider an ideal network environment that employs the most accurate deterministic, time-invariant video traffic characterizations, Earliest-Deadline-First packet schedulers, and exact admission control conditions. The utilization achievable in this situation provides the fundamental limits of a deterministic service. We then investigate the utilization limits in a network environment that takes into account practical constraints, such as the need for fast policing mechanisms, simple packet scheduling algorithms, and efficient admission control tests.

Most of the solutions proposed to support real-time (i.e. guaranteed performance) communication services in packet-switching networks adopt a connection-oriented and reservation-oriented approach. In such an approach, resource allocation and route selection decisions are made before the start of the communication on the basis of resource availability and real-time network load at that time, and are usually kept for the duration of the communication. This rather static resource management approach has certain limitations: it does not take into account (a) the dynamicity of the communicating clients; (b) the dynamicity of the network state; and (c) the tradeoff between quality of service and network availability, thus affecting the availability and flexibility of the real-time network services. Availability is the ability of the network to accommodate as many real-time clients as possible, while flexibility is the ability to adapt the real-time services to changing network state and client demands. The authors present the dynamic connection management (DCM) scheme, which addresses these issues by providing the network with the capability to dynamically modify the performance parameters and the routes of any existing real-time connection. With these capabilities, DCM can be used to increase the availability and flexibility of the guaranteed performance service offered to the clients.>

Emerging distributed multimedia applications have stringent performance requirements in terms of bandwidth, delay, delay-jitter, and loss rate. The Tenet real-time protocol suite provides the services and mechanisms for delivering such performance guarantees, even during periods of high network load and congestion. The protocols achieve this by using resource management, connection admission control, and appropriate packet service disciplines inside the network. The Sequoia 2000 network employs the Tenet Protocol Suite at each of its hosts and routers making it one of the first wide area packet-switched networks to provide end-to-end per-connection performance guarantees. This paper presents experiments with the Tenet protocols on the Sequoia 2000 network including measurements of the performance of the protocols, the service recieved by real multimedia applications using the protocols, and comparisons with the service received by applications that use the Internet protocols (UDP/IP). We conclude that the Tenet protocols successfully protect the real-time channels from other traffic in the network, including other real-time channels, and allow channels to continue to meet their performance guarantees, even when the network is highly loaded.

This paper demonstrates a new, efficient, and general approach for providing end-to-end performance guarantees in integrated services networks. This is achieved by modeling a traffic source with a family of bounding interval-dependent (BIND) random variables and by using a rate-controlled service discipline inside the network. The traffic model stochastically bounds the number of bits sent over time intervals of different length. The model captures different source behavior over different time scales by making the bounding distribution an explicit function of the interval length. The service discipline, RCSP, has the priority queueing mechanisms necessary to provide performance guarantees in integrated services networks. In addition, RCSP provides the means for efficiently extending the results from a single switch to a network of arbitrary topology. These techniques are derived analytically and then demonstrated with numerical examples.

The authors propose a service discipline, called the rate-controlled static-priority (RCSP) queuing discipline, that provides throughput, delay, delay jitter, and loss free guarantees in a connection-oriented packet-switching network. The RCSP queuing discipline avoids both time-framing and sorted priority queues; it achieves flexibility in the allocation of delay and bandwidth, as well as simplicity of implementation. The key idea is to separate rate-control and delay-control functions in the design of the server. Applying this separation of functions results in a class of service disciplines of which RCSP is an instance.>

This paper compares six new queue service disciplines that can be implemented at the output queues of switches in a connection-oriented packet switched data network. These are Virtual Clock, Fair Queueing, Delay-Earliest-DueDate, Jitter-Earliest-Due-Date, Stop-and-Go and Hierarchical Round Robin. We describe their mechanisms, their similarities and differences, and some implementation strategies. In particular, we show why each discipline can or cannot provide bandwidth, delay and delay jitter guarantees. This leads to some interesting conclusions about the relative strengths and weaknesses of each approach. 1 Introduction High speed networking introduces opportunities for new applications that have stringent performance requirements in terms of throughput, delay, delay jitter 1 and loss rate [3]. Conventional packet switching data networks with windowbased flow control and first-come-first-served service discipline cannot provide services with strict performance guarantees. Thus, n...