Modern cloud-based applications have complex inter-dependencies on both distributed application components as well as network infrastructure, making it difficult to reason about their performance. As a result, a rich body of work seeks to automate performance diagnosis of enterprise networks and such cloud applications. However, existing methods either ignore inter-dependencies which results in poor accuracy, or require causal acyclic dependencies which cannot model common enterprise environments.

Our work addresses how a cloud provider can offer Network Functions (NF) as a Service, or NFaaS, using the emerging serverless computing paradigm. Serverless computing has the right NFaaS building blocks - usage-based billing, event-driven programming model and elastic scaling. But we identify two core limitations of existing serverless platforms that undermine support for NFaaS - coupling of the billing and work assignment granularities, and state sharing via an external store. Our framework, SNF, overcomes these limitations via two ideas. SNF allocates work at the granularity of flowlets observed in network traffic, whereas billing and programming occur at a finer level. SNF embellishes serverless platforms with ephemeral local state that lasts for the flowlet duration and supports high performance state operations. We demonstrate that our SNF prototype matches utilization closely with demand and reduces tail packet processing latency substantially compared to alternatives.

Existing network policy abstractions handle basic group based reachability and access control list based security policies. However, QoS policies as well as dynamic policies are also important and not representing them in the high level policy abstraction poses serious limitations. At the same time, efficiently configuring and composing group based QoS and dynamic policies present significant technical challenges, such as (a) maintaining group granularity during configuration, (b) dealing with network-bandwidth contention among policies from distinct writers and (c) dealing with multiple path changes corresponding to dynamically changing policies, group membership and end-point mobility. In this paper we propose Janus, a system which makes two major contributions. First, we extend the prior policy graph abstraction model to represent complex QoS and dynamic tateful/temporal policies. Second, we convert the policy configuration problem into an optimization problem with the goal of maximizing the number of satisfied and configured policies, and minimizing the number of path changes under dynamic environments. To solve this, Janus presents several novel heuristic algorithms. We evaluate our system using a diverse set of bandwidth policies and network topologies. Our experiments demonstrate that Janus can achieve near-optimal solutions in a reasonable amount of time.

Computing/infrastructure as a service continues to evolve with bare metal, virtual machines, containers and now serverless granular computing service offerings. Granular computing enables developers to decompose their applications into smaller logical units or functions, and run them on small, low cost and short lived computation containers without having to worry about setting up servers - hence the term serverless computing. While serverless environments can be used very cost effectively for large scale parallel processing data analytics applications, it is less clear if network intensive packet processing applications can also benefit from these new computing services as they do not share the same characteristics. This paper examines the architectural constraints as well as current serverless implementations to develop a position on this topic and influence the next generation of computing services. We support our position through measurement and experimentation on Amazon's AWS Lambda service with a few popular network functions.

Today's cloud infrastructure is often overwhelmed by inputs from multiple users and administrators for enforcing the policies on which to run cloud services, and infrastructure administrators need to configure policies on different resource types such as compute, network, etc. Such complex policy enforcement decisions from multiple users could result in errors and conflicts. To mitigate such complexities in managing cloud infrastructure, there is a strong push towards decoupling high level intents (“what” should be done) from the underlying infrastructure implementations (“how” to do it). Unlike existing solutions which resolve conflicts at low level during run-time, intent-based systems aim to resolve potential conflicts at the intent specification level. To efficiently handle large scale cloud environments, we propose a Label Management Service (LMS) which provides meaningful abstractions and their relationships by analyzing target cloud infrastructure. It helps the cloud administrators to model their policy requirements efficiently by decoupling the intents from underlying specifics. LMS scales to large dynamic cloud environments and manages the life cycle of label-based intent and enforcement.

Network verification has been recently proposed to detect network misconfigurations. Existing work focuses on the reachability. This paper proposes a framework that verifies the Service Level Agreement (SLA) compliance of the network using static verification. This work proposes a quantitative model and a set of algorithms for verifying performance properties of a network with switches and middleboxes, i.e., service chains. We develop SLA-Verifier and evaluate its efficiency using simulation on real-world data and testbed experiments. To improve the SLA violation detection accuracy, our system uses verification results to optimize online monitoring.

Network functions (NFs), like firewall, NAT, IDS, have been widely deployed in today’s modern networks. However, currently there is no standard specification or modeling language that can accurately describe the complexity and diversity of different NFs. Recently there have been research efforts to propose NF models. However, they are often generated manually and thus error-prone. This paper proposes a method to automatically synthesize NF models via program analysis. We develop a tool called NFactor, which conducts code refactoring and program slicing on NF source code, in order to generate its forwarding model. We demonstrate its usefulness on two NFs and evaluate its correctness. A few applications of NFactor are described, including network verification.

Software Defined Networking (SDN) and cloud automation enable a large number of diverse parties (network operators, application admins, tenants/end-users) and control programs (SDN Apps, network services) to generate network policies independently and dynamically. Yet existing policy abstractions and frameworks do not support natural expression and automatic composition of high-level policies from diverse sources. We tackle the open problem of automatic, correct and fast composition of multiple independently specified network policies. We first develop a high-level Policy Graph Abstraction (PGA) that allows network policies to be expressed simply and independently, and leverage the graph structure to detect and resolve policy conflicts efficiently. Besides supporting ACL policies, PGA also models and composes service chaining policies, i.e., the sequence of middleboxes to be traversed, by merging multiple service chain requirements into conflict-free composed chains. Our system validation using a large enterprise network policy dataset demonstrates practical composition times even for very large inputs, with only sub-millisecond runtime latencies.

Resource conflicts are inevitable on any shared infrastructure. In Software-Defined Networks (SDNs), different controller modules with diverse objectives may be installed on the SDN controller. Each module independently generates resource requests that may conflict with the objectives of a different module. For example, a controller module for maintaining high availability may want resource allocations that require too much core network bandwidth and thus conflict with another module that aims to minimize core bandwidth usage. In such a situation, it is imperative to identify and install resource allocations that achieve network wide global objectives that may not be known to individual modules, e.g., high availability with acceptable bandwidth usage. This problem has received only limited attention, with most prior work focused on detecting, avoiding, and resolving rule-level conflicts in the context of OpenFlow.

Providing bandwidth guarantees to specific applications is becoming increasingly important as applications compete for shared cloud network resources. We present CloudMirror, a solution that provides bandwidth guarantees to cloud applications based on a new network abstraction and workload placement algorithm. An effective network abstraction should enable applications to easily and accurately specify their requirements, while simultaneously enabling the infrastructure to provision resources efficiently for deployed applications. Prior research has approached the bandwidth guarantee specification by using abstractions that resemble physical network topologies. We present a contrasting approach of deriving a network abstraction based on application communication structure, called Tenant Application Graph or TAG. CloudMirror also incorporates a new workload placement algorithm that efficiently meets bandwidth requirements specified by TAGs while factoring in high availability considerations. Extensive simulations using real application traces and datacenter topologies show that CloudMirror can handle 40% more bandwidth demand than the state of the art (e.g., the Oktopus system), while improving high availability from 20% to 70%.

Software-Defined Networking (SDN) promises to enable vigorous innovation, through separation of the control plane from the data plane, and to enable novel forms of network management, through a controller that uses a global view to make globally-valid decisions. The design of SDN controllers creates novel challenges; much previous work has focused on making them scalable, reliable, and efficient.

While cloud computing providers offer guaranteed allocations for resources such as CPU and memory, they do not offer any guarantees for network resources. The lack of network guarantees prevents tenants from predicting lower bounds on the performance of their applications. The research community has recognized this limitation but, unfortunately, prior solutions have significant limitations: either they are inefficient, because they are not work-conserving, or they are impractical, because they require expensive switch support or congestion-free network cores.

The energy consumed by networks is growing and while it is not the dominant contributor to IT energy spend, the absolute power consumption numbers are staggeringly large. As servers and cooling within data centers and enterprises becomes more energy-efficient, it is critical that we address the energy management for networking devices now and make these devices energy efficient as well as energy proportional. Network device, topology and route control based on configurations, traffic demands and performance requirements can be leveraged for reducing network energy consumption. In this paper we present NEEM (Network Energy Efficiency Manager), a network energy management solution for automating the policy driven analysis for energy efficiency and implementing the network changes that can result in significant savings by adapting to the network traffic dynamics and requirements. Our initial results on an enterprise network, based on offline analysis show that NEEM can save over 30% of network energy consumption. NEEM is a vendor-neutral, standards-based solution.

OpenFlow is a great concept, but its original design imposes excessive overheads. It can simplify network and traffic management in enterprise and data center environments, because it enables flow-level control over Ethernet switching and provides global visibility of the flows in the network. However, such fine-grained control and visibility comes with costs: the switch-implementation costs of involving the switch's control-plane too often and the distributed-system costs of involving the OpenFlow controller too frequently, both on flow setups and especially for statistics-gathering.

In this paper, we consider migration of virtual machines in a data center to minimize network power consumption. Network power is consumed when switches are turned on, and conserved when they are turned off; the optimization problem then is to site virtual machines within the data center to achieve connectivity and desired bandwidth while turning on as few switches as possible. Depending upon specifics of the permissible optimization, and topology considerations within the data center, this optimization problem can be easy, or hard. We fully taxonomize the suite of optimization problems in this general space, showing that the most complex problem (placement and routing of virtual machines in a topologically-rich data center network) is NP- hard. We offer a placement technique based on a classic VLSI placement algorithm, and demonstrate efficacy on a trace set derived from a production data center.

Recently, there has been a tremendous growth in the number of installed distributed computing platforms such as those for content distribution networks, cloud computing infrastructures, and distributed data centers. Such distributed platforms need a scalable end-to-end (e2e) network monitoring component to provide Quality of Service (QoS) guarantees to the services and improve the overall performance. An important challenge for a network monitoring infrastructure is the periodicity of the measurements as this aspect trades off the monitoring overheads with staleness of the results. In the Network Genome project, we explore the relationships between different e2e network metrics with the aim of leveraging such relationships for reducing monitoring costs while maintaining measurement accuracy. We perform our analysis using long range network measurements from PlanetLab, where we have been collecting e2e network data (route, number of hops, capacity bandwidth and available bandwidth) as part of the S3 system since January 2006. In this paper, we focus on the correlation between the Capacity and Available Bandwidth metrics between host pairs in the PlanetLab testbed. Our analysis shows that the ranking of hosts with respect to their Capacity to/from a set of nodes is a good indicator of the ranking of hosts with respect to their Available Bandwidth to/from the same set of nodes.

The OpenFlow framework enables flow-level control over Ethernet switching, as well as centralized visibility of the flows in the network. OpenFlow's coupling of these features comes with costs, however: the distributed-system costs of involving the OpenFlow controller on flow setups, and the switch-implementation costs of involving the switch's control plane too often.

Peak Signal-to-Noise Ratio (PSNR) is the simplest and the most widely used video quality evaluation methodology. However, traditional PSNR calculations do not take the packet loss into account. This shortcoming, which is amplified in wireless networks, contributes to the inaccuracy in evaluating video streaming quality in wireless communications. Such inaccuracy in PSNR calculations adversely affects the development of video communications in wireless networks. This paper proposes a novel video quality evaluation methodology. As it not only considers the PSNR of a video, but also with modifications to handle the packet loss issue, we name this evaluation method MPSNR. MPSNR rectifies the inaccuracies in traditional PSNR computation, and helps us to approximate subjective video quality, Mean Opinion Score (MOS), more accurately. Using PSNR values calculated from MPSNR and simple network measurements, we apply linear regression techniques to derive two specific objective video quality metrics, PSNR-based Objective MOS (POMOS) and Rates-based Objective MOS (ROMOS). Through extensive experiments and human subjective tests, we show that the two metrics demonstrate high correlation with MOS. POMOS takes the averaged PSNR value of a video calculated from MPSNR as the only input. Despite its simplicity, it has a Pearson correlation of 0.8664 with the MOS. By adding a few other simple network measurements, such as the proportion of distorted frames in a video, ROMOS achieves an even higher Pearson correlation (0.9350) with the MOS. Compared with the PSNR metric from the traditional PSNR calculations, our metrics evaluate video streaming quality in wireless networks with a much higher accuracy while retaining the simplicity of PSNR calculation.

Traditionally, in-network services like firewall, proxy, cache, and transcoders have been provided by dedicated hardware middleboxes. A recent trend has been to remove the middleboxes by deploying the network services into switch/router-integrated computing modules or separate server/blade machines. In this abstract, by using a web Ad-insertion application as an example, we demonstrate our in-network processing (INP) framework that orchestrates various computing resources and network devices and enables seamless and efficient deployments of network services.

There is a growing need to support real-time applications over the Internet. Real-time interactive applications often have multiple quality-of-service (QoS) requirements which are application specific. Traditional provisioning of QoS in the Internet through IP routing - Intserv or Diffserv - faces many technical challenges, and is also deterred by the huge deployment issues. As an alternative, application providers often build their own application-specific overlay networks to meet their QoS requirements. In this paper, we present a unified framework which can serve diverse applications with multiple QoS constraints. Our scalable flow route management architecture, called MCQoS, employs a hybrid approach using a path vector protocol to disseminate aggregated path information combined with on-demand path discovery to find paths that match the diverse QoS requirements. It uses a distributed algorithm to dynamically adapt to an alternate path when the current path fails to satisfy the required QoS constraints. We do large-scale simulation and analysis to show that our approach is both efficient and scalable, and that it substantially outperforms the state of the art protocols in accuracy. Our simulation results show that MCQoS can reduce the false negative percentage to less than 1% compared with 5-10% in other approaches, and eliminates false positives, whereas other schemes have false positive rates of 10-20% with minimal increase in protocol overhead. Finally, we implemented and deployed our system on the Planetlab testbed for evaluation in a real network environment.

Interference among concurrent transmissions complicates QoS provisioning for multimedia applications in wireless mesh networks. In this paper we propose MARIA (mesh admission control and QoS routing with interference awareness), a scheme towards enhancing QoS support for multimedia in wireless mesh networks. We characterize interference in wireless networks using a conflict graph based model. Nodes exchange their flow information periodically and compute their available residual bandwidth based on the local maximal clique constraints. Admission decision is made based on the residual bandwidth at each node. We implement an on-demand routing scheme that explicitly incorporates the interference model in the route discovery process. It directs routing message propagations and avoids "hot-spots" with severe interference. Simulation results demonstrate that by taking interference into account MARIA outperforms the conventional approach. It finds routes with less interference and enhances the performance significantly. We use video as an example application and MARIA improves the quality of delivered videos, with up to 7.3 dB average PSNR gain.

In the absence of end-to-end quality of service (QoS), overlay routing has been used as an alternative to the default best effort Internet routing. Using end-to-end network measurement, the problematic parts of the path can be bypassed, resulting in improving the resiliency and robustness to failures. Studies have shown that overlay paths can give better latency, loss rate, and TCP throughput. Overlay routing also offers flexibility as different routes can be used based on application needs. There have been very few proposals of using bandwidth as the main metric of interest, which is of great concern in media applications. We introduce our scheme BARON (Bandwidth-Aware Routing in Overlay Networks) that utilizes capacity between the end hosts to identify viable overlay paths and measures available bandwidth to select the best route. We propose our path selection approaches, and using the measurements between 174 PlanetLab nodes and over 13,189 paths, we evaluate the usefulness of overlay routes in terms of bandwidth gain. Our results show that among 658,526 overlay paths, 25% have larger bandwidth than their native IP routes, and over 86% of (source, destination) pairs have at least one overlay route with larger bandwidth than the default IP routes. We also present the effectiveness of BARON in preserving the bandwidth requirement over time for a few selected Internet paths.

Knowledge of the network path properties such as latency, hop count, loss and bandwidth is key to the performance of overlay networks, grids and P2P applications. Network operators also use these metrics for managing and diagnosing problems in their networks. However, the size of the Internet makes the task of measuring these metrics immensely difficult. A more scalable approach of inference and estimation of these metrics based on partial measurements has been recently adopted. Current inference approaches do not adapt to different network topologies and the evolution of the network over time. In this paper, we propose a novel learning based approach, called Minerva, for the inferencing of inter-node properties. Minerva uses partial measurements to create signature-like profiles for the participating nodes. These signatures are later used as input to a trained Bayesian network module to estimate the different network properties. We have built a system based on our approach and present performance results from real network measurements obtained from the Planet-Lab testbed. The sensitivity of the system to different parameters including training set, measurement overhead, and size of network have also been studied in this paper.

Supporting multimedia services in wireless mesh networks is receiving more attention from the research community. While wired networks have mature infrastructure and protocols providing QoS for multimedia, supporting multimedia in multihop wireless mesh networks faces greater technical challenges. The unreliable nature and shared media of multihop communications make the deployment of multimedia applications in wireless mesh networks a difficult task. To identify and understand the issues and problems of providing multimedia in multihop wireless mesh networks, we take video streaming as an example, setting up a real testbed to conduct extensive experiments in various scenarios and analyze its performance. In contrast to simulation or network-layer statistics based studies, our investigation is directly focused on video quality in multihop scenarios. The results better represent real networks and reveal interesting aspects of video performance in multihop wireless mesh networks, which we believe is helpful in designing efficient QoS solutions for multimedia services in the wireless mesh networks.

Service overlay networking is an emerging approach, which employs overlay nodes to provide advanced services by dynamically composing it from basic services available on overlay nodes. Advanced service request from users can have different and multiple quality-of-service (QoS) requirements and findi

Abstract — Estimation of network proximity among nodes is an important building block in several applications like service selection and composition, multicast tree formation, and overlay construction. Recently, scalable techniques have been proposed to estimate inter-node latencies, including network coordinate systems like GNP and Vivaldi. However, existing mechanisms for querying such information do not scale well to a very large number of nodes, when one wants to accurately find a set of nodes globally closest to a given node. In this paper we are concerned with distributing the position data among a set of infrastructure nodes, and propose ways of partitioning and querying this data. The trade-offs between accuracy and overhead in this distributed infrastructure are explored. We evaluate our solution through simulations with real and synthetic network measurement data. I.

Abstract — As the academic world moves away from physical journals and proceedings towards online document repositories, the ability to efficiently locate work of interest among the torrent of newly-generated papers will become increasingly important. To aid in this endeavor, we designed SmartSeer, a system that allows users to register personalized continuous queries over the CiteSeer database of technical documents. Users are then alerted whenever papers that match their queries are put online. SmartSeer has two main design requirements. First, to allow effective information retrieval, it should support rich continuous queries (as opposed to simple keyword searches). Second, to make effective use of donated infrastructure, it should be capable of running on a loosely maintained group of unreliable machines spread across multiple organizations (as opposed to assuming a reliable and tightly coupled distributed system). Existing work on distributed continuous query systems fails at least one of these requirements. Our design for SmartSeer is based on Distributed Hash Tables (DHTs), and thereby leverages previous work on DHT-based query systems. A prototype of SmartSeer has been implemented and evaluated on Planetlab. Though we evaluate our design only for the SmartSeer application, we believe it also provides useful insights into other distributed and rich continuous query systems (web alerts, news alerts etc). I.

In this paper, QoS-guaranteed path selection algorithm for service composition is described. A heuristic algorithm, K-closest pruning (KCP), is used to solve the problem of multi-constraint service path selection for SON in polynomial time. The main feature of this algorithm is that the path selected by this algorithm meets all the QoS requirements specified by the user/application. The main idea in this approach is to leverage network proximity information to reduce search space, i.e. to reduce the number of qualified overlay nodes/links, for service path selection for a given request. This paper demonstrates the two distinct objectives reuse and load balancing and their use in modifying the path selection of KCP algorithm to achieve the objectives with affecting performance of KCP algorithm

Efficient resource discovery based on dynamic attributes such as CPU utilization and available bandwidth is a crucial problem in the deployment of computing grids. Existing solutions are either centralized or unable to answer advanced resource queries (e.g., range queries) efficiently. We present the design of NodeWiz, a grid information service (CIS) that allows multi-attribute range queries to be performed efficiently in a distributed manner. This is obtained by aggregating the directory services of individual organizations in a peer-to-peer information service.

Estimation of network proximity among nodes is an important building block in several applications like service selection and composition, multicast tree formation, and overlay construction. Recently, scalable techniques have been proposed to estimate inter-node latencies, including network coordinate systems like GNP and Vivaldi. However, existing mechanisms for querying such information do not scale well to a very large number of nodes, when one wants to accurately find a set of nodes globally closest to a given node. In this paper we are concerned with distributing the position data among a set of infrastructure nodes, and propose ways of partitioning and querying this data. The trade-offs between accuracy and overhead in this distributed infrastructure are explored. We evaluate our solution through simulations with real and synthetic network measurement data.

This paper presents the use of adaptive bandwidth control (ABC) for a quantitative packet loss rate guarantee to aggregate traffic in packet switched networks. ABC starts with some initial amount of bandwidth allocated to a queue and adjusts it over time based on online measurements of system states to ensure that the allocated bandwidth is just enough to attain the specified loss requirement. Consequently, no a priori detailed traffic information is required, making ABC more suitable for efficient aggregate quality of service (QoS) provisioning. We propose an ABC algorithm called augmented Fuzzy (A-Fuzzy) control, whereby fuzzy logic control is used to keep an average queue length at an appropriate target value, and the measured packet loss rate is used to augment the standard control to achieve better performance. An extensive simulation study based on both theoretical traffic models and real traffic traces under a wide range of system configurations demonstrates that the A-Fuzzy control itself is highly robust, yields high bandwidth utilization, and is indeed a viable alternative and improvement to static bandwidth allocation (SBA) and existing adaptive bandwidth allocation schemes. Additionally, we develop a simple and efficient measurement-based admission control procedure which limits the amount of input traffic in order to maintain the performance of the A-Fuzzy control at an acceptable level.

Overlay multicast protocols should adapt to the dynamic network environment to maintain application performance. We show how end-to-end network metrics can be used in the dynamic adaptation and thus improve the performance of the direct-tree overlay multicast protocols while providing good tree quality. We propose the adaptive overlay multicast (AOM) approach that provides good tree quality and efficient adaptation. We compare AOM with a typical direct-tree protocol like HMTP (host multicast tree protocol). The simulation results show that AOM builds high-quality trees, adapts better to network conditions and is efficient.

The increasing deployment of unresponsive streaming applications has triggered the design of a number of new mechanisms and protocols to reduce the potential risk of unfairness and congestion collapse in the Internet. Fair non-per flow active queue management (AQM) schemes, such as BLACK, have recently been proposed to maintain fairness when unresponsive constant bit rate UDP flows share a bottleneck link with responsive TCP traffic. Similarly, TCP-friendly protocols have been developed to provide smooth congestion control that is suitable for multimedia applications while still being compatible with TCP. However, the performance of these fair AQM mechanisms has not been evaluated when different TCP-friendly flows compete against TCP versions. As TCP-friendly protocols react to packet drops differently from TCP, the various AQM schemes might punish some flows unfairly. However, this aspect has not been studied yet. The paper provides two key contributions. First, it provides the first comprehensive evaluation of fair AQM schemes under the presence of various types of TCP friendly traffic. From experimental results, we found that a fair AQM scheme must be chosen not only based on its performance or capability to deal with unresponsive flows as is usually done, but also considering its performance when other types of flows are included, such as TCP-friendly sources. Second, the paper presents an enhanced version of BLACK that outperforms all of the other fair non per-flow state information AQM schemes.

In this paper, the adaptive overlay multicast (AOM) protocol is presented, which is specially beneficial to long-lasting, large data distribution applications with large receiver sets. AOM distinguishes itself from the previous research with the following characteristics: (1) scalable overlay multicast tree construction method and a scoping technique to decrease overhead, (2) active adaptation to dynamic network conditions, and (3) efficient loss measurement and adaptation algorithms. We present extensive simulations of AOM including real Internet data and compare it with a HMTP-like protocol. The results show that AOM builds high-quality trees and adapts well to the network conditions while incurring low overhead.

Several distributed QoS mechanisms have been proposed to augment the existing distributed coordination function of the IEEE 802.11 MAC protocol to provide QoS support for QoS-sensitive applications. These mechanisms use well-known QoS enabling techniques such as priority assignment and fair scheduling within existing 802.11 MAC parameters. Although these mechanisms provide differentiated throughput for different classes of traffic, they cannot provide both relative and absolute throughput support simultaneously.In this paper, we propose a new mechanism called A-DRAFT that supports both absolute and relative throughput in an adaptive and a fully distributed manner. This paper describes an adaptive mechanism that supports absolute throughput as long as the total demand from this class is below the effective channel capacity. The proposed mechanism also provides relative or fair throughput support with low variation and a high degree of fairness even in a saturated network with a large number of MSs. We make use of deficit round robin scheduling with different levels of quantum rate to provide fairness, and different weights to provide absolute and relative throughput. We evaluate the performance of the proposed mechanism via mathematical analysis and confirm this analysis with simulations.

Streaming media transfers over the Internet are expected to behave in a TCP-friendly manner while reacting slower to congestion than TCP. For this purpose, a number of slowly-responsive congestion control protocols have been developed. In this paper, we present our study on the media-friendliness of TFRC, one of the recently developed slowly-responsive congestion control mechanisms. With both simulation and Internet experiments, we show that TFRC is not necessarily smooth enough to be "media-friendly". We also discuss our approach to improve a congestion control mechanism's media-friendliness.

It is well known that the distributed coordination function (DCF) of the IEEE 802.11 MAC protocol is not suitable for supporting multimedia and QoS-sensitive applications because of its inherent lack of QoS support and fairness. Recently, several distributed QoS mechanisms have been proposed which translate user QoS requirements into typically a single parameter of the DCF protocol. In this paper, we compare the pros and cons of the major distributed QoS mechanisms, and propose a new mechanism that provides superior performance and supports two different QoS models. The proposed mechanism is based on deficit round robin scheduling and translates the user throughput requirements into the 802.11 MAC interframe space and backoff interval parameters. We show via simulations that the proposed mechanism provides low variability of throughput and delay and has the advantage of low complexity.

In this paper, we present the BLACK scheme that aims to prevent the unfairness problem generated by high bandwidth unresponsive flows. The scheme needs to store only a small amount of state information to maintain and exercise its fairness mechanism and utilizes a packet sampling technique that estimates both the flow's buffer occupancy fraction and the number of active flows. When working in conjunction with RED, BLACK has shown not only to be able to handle unresponsive traffic, but also improve the fairness among TCP connections with different round-trip delays in some scenarios.

In this paper, the problem of predicting the quality of MPEG video streams received over a best effort network is studied. The objective of the study is to develop and validate methods to accurately predict the video quality from network level quality of service (QoS) measurements to the application layer QoS. This involves QoS mapping between the various protocol layers as well as accounting for the frame dependencies in the MPEG video compression scheme. The validation is conducted using simulation with real video traces.

An important aspect of improving streaming application performance is the streaming quality evaluation process. In this paper we introduce a set of alternative objective streaming video quality metrics, which are suitable for large scale deployment. Derived from an existent media application, our metrics are designed to capture the application behaviors disrupting the streaming video quality. We also present a set of experiments to demonstrate the effectiveness of these metrics.

Application-level multicast networks overlaid on unicast IP networks are increasingly gaining in importance. While there have been several proposals for overlay multicast networks, very few of them focus on the stringent requirements of real-time applications such as streaming media. We propose RITA (Receiver Initiated Timely Adaptation) framework for an efficient overlay multicast infrastructure. RITA is based on a combination of landmark clustering and RTT measurements, and is particularly suitable for multimedia real-time applications. Our goal is to balance the network-oriented goals of building an efficient multicast tree with the application-oriented goals of providing good QoS with minimal disruptions. Using accurate global soft state information tables, our approach promptly constructs and reconfigures high quality trees. A distinguishing feature of our approach is that the tree reconfiguration is initiated just-in-time by the application client at the receiver when the media quality falls below a specific threshold. The goal is to achieve dynamic tree reconfiguration with very low switching delay such that end users do not perceive any application performance degradation.

Class-based traffic treatment frameworks such as differentiated service (DiffServ) have been proposed to resolve the poor scalability problem in the flow-based approach. Although the performance is differentiated in a class-based basis, the performance seen by individual flows in the same class may differ from that seen by the class and has not been well understood. We investigate this issue by simulation in a single node under FIFO, static priority, waiting time priority, and weighted fair queueing scheduling schemes. Our results indicate that such performance discrepancy occurs especially when flows joining the same class are heterogeneous, which is not uncommon considering that the same type of applications can generate traffic having very different statistical behaviors such as video traffic with different activity levels, or voice traffic with different compression schemes. We found that per-flow delay statistics, including the average and the 99/sup th/ percentile delay, can be very different from the corresponding class delay statistics, depending on flow burstiness, overall traffic load, as well as the queue discipline. We also propose a solution to reduce the mean delay variance experienced by flows in the same class.

The paper proposes an adaptive bandwidth control algorithm that efficiently provides an aggregate loss guarantee to resolve the problem of inefficient bandwidth allocation due to incomplete, inaccurate traffic descriptors supplied by users. Because the control attempts to allocate only just enough bandwidth to meet the QoS requirement, the amount of bandwidth saving compared to static allocation can be substantial. Another distinct advantage of our control algorithm is that no a priori information on the traffic characteristics of the aggregate is required. From the simulation study, the proposed control can maintain the packet loss QoS while attaining very high utilization, and is robust against different system configurations and controller parameters.

We propose a multicast feedback control mechanism that dynamically groups the receivers into several areas according to their loss patterns. Each area has an area representative (AR) that provides quick feedback messages and suppresses other receivers in the area. When the AR cannot correctly represent other receivers, deterministic suppression is executed among the non-representative receivers. The scheme is stable and robust. It does not need special network support, but can be optimized if available. Simulation results show that this scheme is suppressive, responsive and scalable.

Reliable multicast applications use feedback messages to report receiving status of receivers. This results in the well-known feedback implosion and scalability problems. Also, quick loss response from receivers and low multicast overhead, e.g. control messages and session messages, are desired. We present a feedback implosion control mechanism that groups the multicast members into areas, with each area having an area representative (AR). The AR provides immediate feedback messages and suppresses the superfluous feedback messages from other receivers in its area. The mechanism does not need any support from underlying networks except correct multicast packet routing. No network topology or multicast group membership information is needed. Each receiver selects its AR independently; areas are formed or dismissed automatically and dynamically when network situation changes. Preliminary simulation results show that our mechanism has good feedback suppression, fast loss response and is scalable with the group size.

Because of the channel's characteristics the use of TCP over wireless may result in poor performance. Significant throughput degradation occurs when TCP interprets high bit error rate and mobile host disconnections as congestion in the network. We address this problem and focus our research on the study of how to improve the TCP's performance over wireless. We study TCP communications between mobile hosts communicating with each other using an infrastructure network. We introduce a new scheme, called MAITE(Mobility Awareness Incorporated as TCP Enhancement) that consists of an implementation of link layer messages that inform the TCP of high BER and disconnection conditions. By the use of simulations we compare the results obtained with MAITE with other previously proposed schemes. Our scheme provides us with improvements in transfer time of 30% over other schemes.

Digital libraries are concerned with the creation and management of information sources, the movement of information across global networks, and the effective use of this information by a wide range of users. A digital library is a vast collection of objects that are of multimedia nature, e.g. text, video, images, and audio. Users wishing to access the digital library objects may possess varying capabilities, preferences, domain expertise, and may use different information appliances. Facilitating access to complex multimedia digital library objects that suits the users' requirements is known as universal access. We present an object manifestation approach in which digital library objects automatically manifest themselves to cater to the users' capabilities and characteristics. We provide a formal framework, based on Petri nets, to represent the various components of the digital library objects, their modality and fidelity, and the playback synchronization relationships among them. We develop methodologies for object delivery without any deadtime under network delays.

In spite of the availability of sophisticated network quality of service (QoS) guaranteeing mechanisms, it is apparent that a large number of applications will continue using the best effort service class. The main reason for this is that the QoS guaranteeing mechanisms are complex and many applications are not capable of using these complex services. At the same time, the standard best effort service is rather unpredictable and hence insufficient for many applications. Thus augmenting best effort services to an appropriate standard without incurring a high level of complexity is a necessary. In this paper two such augmentations are described in the context of the UBR service ATM networks. Selective packet discarding is used to achieve the necessary goals.

The performance analyses of selective packet dropping policies have usually been performed using homogeneous traffic sources and under one node scenarios. In this paper we focus our attention not only on heterogeneous sources but also heterogeneous environments. We present simulation results of application level performance for heterogeneous traffic sources under three different packet dropping schemes: partial packet discard (PPD), early packet discard (EPD), and preemptive partial packet discard (pPPD). In addition, we also present simulation results for homogeneous sources over multi-hop networks with heterogeneous packet dropping policies.

Packet scheduling disciplines play an important role in providing quality of service (QoS) guarantees to applications traffic in high speed networks. Several scheduling disciplines have emerged in the literature that are capable of providing guarantees on various QoS parameters, such as packet delay, jitter, loss and throughput, while maintaining fairness among various connections. However, there is a trade-off between the performance and the simplicity of operation and implementation performance of the scheduling schemes. Thus the first-come-first-serve (FCFS) scheduling discipline has remained popular due to its overriding simplicity in spite of its poor capabilities in providing QoS guarantees. In previous work it has been shown that a practical worst case bound can be obtained for a deterministic delay guarantee in networks using the FCFS discipline, by imposing a source rate condition on each connection, that restricts the overall network utilization. In this paper, a modified source rate condition is proposed that can significantly increase the bandwidth utilization, while still maintaining the deterministic delay guarantee.

Selective packet dropping policies have been used to reduce congestion and transmission of traffic that would inevitably be retransmitted in ATM networks. Common dropping policies proposed are drop-tail, partial packet discard (PPD), early packet discard (EPD) and their recent variations. However, depending on various circumstances, particularly in multi-hop networking environments, application throughput may be quite poor and newer schemes are necessary. In this paper, we first study the performance of existing dropping schemes and identify their shortcomings. Then we propose a new dropping policy called preemptive PPD (pPPD) that exhibits superior performance.

The advent of high-speed networks will enable the deployment of data-server systems (currently used in LANs) over WANs. The users of these systems will have the same high expectations with respect to performance parameters (such as the transaction throughput, response time and system reliability) as in the case of LANs. Thus, it is important to study the performance of existing distributed database protocols in the new networking environment, identify the performance bottlenecks and develop protocols that are capable of taking advantage of the high-speed networking technology. As a first step, in this paper, we examine the scalability of the server-based two-phase locking (s-2PL) protocol, and discuss three optimizations which allow the s-2PL protocol to be tailored for high-speed WAN environments where the size of the message is less of a concern than the number of rounds of message passing. These optimizations, collectively called the group two-phase locking (g-2PL) protocol, reduce the number of rounds of message passing by grouping lock grants, client-end caching and data migration. In a simulation study, 20-25% improvement in the response time of the g-2PL protocol over that of the s-2PL protocol was observed.

It has been well established that high speed networks will be based on cell relay technology, an important feature of which is small fixed size packets. However, application data is rarely small of fixed size, and hence it is important to study the impact on message-level performance in a cell based system. This paper presents a simulation study of application level performance and studies various trade-offs in requesting specific cell level QoS parameters to satisfy the application requirements.

Eliminating interference between concurrently executing activities through mutual exclusion is one of the most fundamental problems in computer systems. The problem of mutual exclusion in a distributed system is especially interesting owing to the lack of global knowledge in the presence of variable communication delays. In this paper, a new token-based distributed mutual exclusion algorithm is proposed. The algorithm incurs approximately three messages at high loads, irrespective of the number of nodes N in the system. At low loads, it requires approximately N messages. The paper also addresses failure recovery issues, such as token loss.

Evaluation of the behavior of queues with nonstationary arrival processes is of importance in several applications including communication networks. However, the analysis of nonstationary queues is in general computationally complex and seldom produces closed form expressions. Thus approximation methods may be more appropriate. The pointwise stationary fluid flow approximation (PSFFA) for determining the mean queue length of nonstationary queues is presented. The PSFFA combines steady state queueing results with a simple fluid flow model to develop a single nonlinear differential equation model of the queue. Numerical integration techniques are used to solve the PSFFA model and the method is illustrated by several examples. The power of this approach is that it can handle very general queueing systems.

Major advances in optical fiber transmission and switching technology have enabled the development of very high speed networks with data rates of the order of gigabits per second. It is anticipated that in the future, wide area gigabit networks will interconnect database servers around the globe creating extremely powerful distributed information systems. In this paper, we examine the implications of such a high speed network on data access and sharing techniques and propose a lock-based concurrency control protocol and a log-based recovery protocol that ensures data consistency in gigabit-networked databases. Both protocols exploit the characteristics of a gigabit network to enhance the performance of the database system and, in particular, the fact that the size of the message is less of a concern than the number of sequential phases of message passing.

The issues involved in developing a distributed database system (DDBS) in a high-speed environment are discussed. The inadequacy of existing database protocols in utilizing the gigabit network is described. A concurrency control protocol that performs better than traditional DDBSs in high-speed networks is developed. Both analytical and simulation results are presented. The focus is on the concurrency control aspect of DDBS since this protocol is at the heart of the overall functioning of the distributed system.>

The analysis of the data accessing mechanism is of importance to the analytical performance evaluation of any data processing system. So far, most such analyses have been done under the assumption of a uniform data access model. This is not true in the real world and some attempts at modeling nonuniform data access have been made. The authors develop a new, improved model, which is believed to be capable of describing the real-world scenario fairly accurately. They also develop the general formula and properties of an important performance parameter, namely, the probability of conflict.>