Abstract: This paper addresses the problem of guaranteed delivery of messages with hard deadlines in a DQDB network. The authors present a cyclic reservation scheme capable of allocating bandwidth with any arbitrary granularity and provide deterministic delay guarantees. They propose two implementations of the allocation scheme within the framework of DQDB medium access control protocol. The proposed implementations are very simple, incur minimal overhead and require only minor changes in the adopted standard

Multi-rate traffic shaping and performance guarantees in ATM networks

Abstract: This paper proposes a traffic control scheme for integrated services ATM networks. The control strategy comprises of two components: a shaping mechanism at the network entry point and a frame based service discipline at the switches. The shaper enforces a short term peak rate, and a long term average rate. The multiplexing scheme at a switch allocates a guaranteed bandwidth to a connection. A connection may get more than the guaranteed amount, up to a connection specific maximum, if slack bandwidth is available. By imposing an upper bound on the allocated bandwidth, we secure a better handle on the delay jitter. Unlike most frame-based schemes, our scheme allows allocation of bandwidth at any arbitrary granularity. We suggest a simple admission control policy and derive deterministic bounds on end-to-end delay and jitter. An outline of a hardware realization of the scheme is also presented

Signature analysers based on additive cellular automata

Abstract: A novel scheme for signature analysis based on cellular automata (CA) is proposed. The state transition behavior of such signature analyzers has been modeled by Markov chain. It has been shown that a special class of such CAs achieves a steady-state aliasing probability lower than 1/2ⁿ (for an n -cell CA) for specific ranges of input probabilities of the incoming error pattern. The dynamic behavior of linear feedback shift registers (LFSRs) has also been compared with CAs with the same characteristic polynomials. This work establishes the fact that CA-based signature analyzers outperform those based on LFSRs as regards both steady-state and dynamic behavior

A video conferencing testbed on ATM: design, implementation and optimizations

Abstract: This paper describes our experiences with the design and implementation of a very high-end video conferencing testbed on an ATM network. Our system is built on an IBM RISC System/6000 equipped with prototype hardware for video and audio capture and compression, and an IBM 100 Mb/s ATM adapter. In our early experiments we used UDP/IP running over ATM Adaptation Layer 5 (AAL5) for data transfer between peers. Our initial experiences with the system indicated that the overall system performance did not match our expectations even though most of the video, audio, and network processing was performed in hardware. A thorough profiling of the system revealed that the protocol processing and data handling overheads in the end-host are responsible for the poor video/audio quality. Based on these observations, we have proposed and implemented changes to the protocol data path that can significantly improve the performance of the system. Although we discuss our solution in the context of a video conferencing application, our approach is general and can be applied to many other applications. It is particularly useful for applications that are required to handle large volumes of time-critical data, such as multimedia servers

Protocol architecture for multimedia applications over ATM networks

Abstract: At the data-link layer, ATM offers a number of features, such as high-bandwidth and per-session quality-of-service (QoS) guarantees, making it particularly attractive to multimedia applications. Unfortunately, many of these features are not visible to applications because of the inadequacies of existing higher-level protocol architectures. Although there is considerable effort underway to tune these protocols for ATM networks, we believe that a new ATM-specific protocol stack is essential to effectively exploit all the benefits of ATM. We describe the semantics of such a protocol stack, and discuss its advantages over traditional protocol architectures from the perspective of multimedia applications. The performance impact of the new protocol architecture is experimentally demonstrated on a video conferencing testbed built around IBM RS/6000's equipped with prototype hardware for video/audio processing, and connected via ATM links

An analysis of the average message overhead in replica control protocols

Abstract: Management of replicated data has received considerable attention in the last few years. Several replica control schemes have been proposed which work in the presence of both node and communication link failures. However, this resiliency to failure inflicts a performance penalty in terms of the communication overhead incurred. Though the issue of performance of these schemes from the standpoint of availability of the system has been well addressed, the issue of message overhead has been limited to the analysis of worst case and best case message bounds. In this paper we derive expressions for computing the average message overhead of several well known replica control protocols and provide a comparative study of the different protocols with respect to both average message overhead and system availabilities

An analysis of the average message overhead in replica control protocols

Abstract: Management of replicated data has received considerable attention in the last few years. Several replica control schemes have been proposed which work in the presence of both node and communication link failures. However, this resiliency to failure inflicts a performance penalty in terms of the communication overhead incurred. Though the issue of performance of these schemes from the standpoint of availability of the system has been well addressed, the issue of message overhead has been limited to the analysis of worst case and best case message bounds. In this paper we derive expressions for computing the average message overhead of several well known replica control protocols and provide a comparative study of the different protocols with respect to both average message overhead and system availabilities

Carry-over round robin: a simple cell scheduling mechanism for ATM networks

Abstract: We propose a work-conserving scheduling mechanism for providing deterministic performance guarantees in ATM networks. The most attractive feature of the proposed mechanism, which we call carry-over round robin (CORR), is its simplicity. It is an extension of weighted round robin scheduling. We have derived closed form bounds for worst case end-to-end delay when CORR is used in conjunction with the composite leaky bucket, and moving window regulators. Our results show that albeit its simplicity, CORR is very competitive with some of the more complex scheduling disciplines such as packet-by-packet generalised processor sharing and stop-and-go queueing

Multirate scheduling for guaranteed and predictive services in ATM networks

Abstract: We propose a multirate service mechanism that allows a network session to be served at different rates at different times. Applications generating bursty data, such as VBR video, can take advantage of multirate service by requesting a high rate of service for brief periods of bursty arrivals and a lower rate of service at other times. Consequently, an application can improve its delay performance without reserving high bandwidth for the entire duration of a session. Using MPEG video traces from a number of applications, we show that a multirate server outperforms single rate PGPS (packet-by-packet generalized processor sharing) servers in terms of number of connections admitted, while providing the same level of service guarantees. We also investigate the performance of multirate service when service quality need not be guaranteed. We refer to this as predictive service. We show that multirate servers are superior to single rate servers in providing predictive services

Multirate scheduling of VBR video traffic in ATM networks

Abstract: One of the major attractions of asynchronous transfer mode (ATM) networks for transporting bursty video traffic is its ability to exploit the multiplexing gains of packet switching while providing quality of service guarantees. Unfortunately, most of the multiplexing mechanisms proposed in the literature fail to exploit the multiplexing gains of ATM. We propose a multirate service mechanism that allows a session to be served at different rates at different times. Applications generating bursty data, such as variable bit-rate (VBR) video, can take advantage of multirate service by requesting a high rate of service for brief periods of bursty arrivals and a much lower rate of service for all other times. Consequently, the applications can improve their delay performance without reserving a high bandwidth for the entire duration of the sessions. Furthermore, the scheduler can multiplex the peaks and the lulls in service rates of different sessions and improve the utilization of the system. Using MPEG video traces from a number of applications, we show that multirate servers outperform single-rate PGPS (packet-by-packet generalized processor sharing) servers and CBR (constant bit-rate) servers in terms of number of connections admitted, while providing the same level of service guarantees. We also investigate the performance of multirate service when service quality need not be guaranteed. We refer to this as predictive service. We propose a measurement-based admission control procedure for predictive service, and show that it helps increase the size of the admissible region even further

Understanding TCP dynamics in an integrated services Internet

Abstract: A large number of Internet applications are sensitive to overload conditions in the network. While these applications have been designed to adapt somewhat to the varying conditions in the Internet, they can benefit greatly from an increased level of predictability in network services. We propose minor extensions to the packet queueing and discard mechanisms used in routers, coupled with simple control mechanisms at the source that enable the network to guarantee minimal levels of throughput to different network sessions while sharing the residual network capacity in a cooperative manner. The service realized by the proposed mechanisms is an interpretation of the controlled-load service being standardized by the IETF. Although controlled-load service can be used in conjunction with any transport protocol, our focus in this paper is on understanding its interaction with TCP. Specifically, we study the dynamics of TCP traffic in an integrated services network that simultaneously supports both best-effort and controlled-load sessions. In light of this study, we propose and experiment with several variations to TCP's control mechanisms with the objective of fine-tuning them for an integrated services environment. We then investigate the overheads associated with these enhancements and the benefits they provide. Finally, we show how the service mechanisms proposed here can be embedded within more elaborate packet and link scheduling frameworks in a fully-evolved integrated services Internet

Design and implementation of a QoS capable switch-router

Abstract: An important challenge for the future growth of the Internet is to design routers that can forward the exponentially increasing volume of traffic, and at the same time provide the service differentiation needed by new applications. In this paper, we describe the architecture, implementation, and initial experiences with a system designed to meet this challenge. This system, which we call a QoS capable switch-router (QSR), combines the salient features of switching and routing technologies to provide high throughput and support the different classes of service being defined by the IETF. It consists of a core (ATM) switch fabric connecting intelligent adapters, each capable of both routing and switching pockets. A control engine is responsible for routing, RSVP signalling, and resource management. We have built a prototype network of 3 systems connected to several UNIX hosts, and have conducted preliminary performance measurements on this network

Design and implementation of an RSVP-based quality of service architecture for integrated services Internet

Abstract: The paper presents the design and implementation of a quality of service architecture for the Internet. The architecture is based on the emerging standards for resource reservation in the Internet, namely the RSVP protocol and the associated service specifications defined by the Internet Engineering Task Force. Our architecture represents a major functional enhancement to the traditional sockets based communication subsystem, while preserving application programming interface and binary compatibility with existing applications. It is scalable and supports a variety of network interfaces ranging from legacy LAN interfaces, such as token ring and Ethernet, to high speed ATM interfaces. We also describe our initial experiences with the implementation of this architecture on the IBM AIX platform

Design and implementation of an RSVP-based quality of service architecture for an integrated services Internet

Abstract: The Internet Engineering Task Force (IETF) is currently in the process of overhauling the architecture of the Internet to meet new challenges and support new applications. One of the most important components of that venture is the enhancement of the Internet service model from a classless best effort service architecture to an integrated services architecture supporting a multitude of classes and types of services. This paper presents the design, implementation, and experiences with a protocol architecture for the integrated services Internet. It is based on the emerging standards for resource reservation in the Internet, namely, the RSVP protocol and the associated service specifications defined by the IETF. Our architecture represents a major functional enhancement to the traditional TCP/IP protocol stack. It is scalable in terms of performance and number of network sessions, and supports a wide variety of network interfaces ranging from legacy LAN interfaces, such as Token Ring and Ethernet, to high-speed ATM interfaces. The paper also describes the implementation of this architecture on the IBM AIX platform and our experiences with the system. We then present a performance analysis of the system which quantifies the overheads imposed by all components of the QoS support, such as traffic policing, traffic shaping, and buffer management

Carry-over round robin: a simple cell scheduling mechanism for ATM networks

Abstract: We propose a simple mechanism named carry-over round robin (CORR) for scheduling cells in asynchronous transfer mode networks. We quantify the operational complexity of CORR scheduling and show that it is comparable to that of a simple round-robin scheduler. We then show that, albeit its simplicity, CORR is very competitive with much more sophisticated and significantly more complex scheduling disciplines in terms of performance. We evaluate the performance of CORR using both analysis and simulation, We derive analytical bounds on the worst case end-to-end delay achieved by a CORR scheduler for different traffic arrival patterns. Using traffic traces from MPEG video streams, we compare the delay performance of CORR with that of packet-by-packet generalized processor sharing (PGPS) and stop-and-go (SG). Our results show that, in terms of delay performance, CORR compares favorably with both PGPS and SG. We also analyze the fairness properties of CORR and show that it achieves near perfect fairness

Understanding and improving TCP performance over networks with minimum rate guarantees

Abstract: A large number of Internet applications are sensitive to overload conditions in the network. While these applications have been designed to adapt somewhat to the varying conditions in the Internet, they can benefit greatly from an increased level of predictability in network services. We propose minor extensions to the packet queueing and discard mechanisms used in routers, coupled with simple control mechanisms at the source that enable the network to guarantee minimal levels of throughput to different sessions while sharing the residual network capacity in a cooperative manner. The service realized by the proposed mechanisms is an interpretation of the controlled-load service being standardized by the Internet Engineering Task Force. Although controlled-load service can be used in conjunction with any transport protocol, our focus in this paper is on understanding its interaction with Transmission Control Protocol (TCP). Specifically, we study the dynamics of TCP traffic in an integrated services network that simultaneously supports both best-effort and controlled-load sessions. In light of this study, we propose and experiment with modifications to TCP's congestion control mechanisms in order to improve its performance in networks where a minimum transmission rate is guaranteed. We then investigate the effect of network transients, such as changes in traffic load and in service levels, on the performance of controlled-load as well as best-effort connections. To capture the evolution of integrated services in the Internet, we also consider situations where only a selective set of routers are capable of providing service differentiation between best-effort and controlled-load traffic. Finally, we show how the service mechanisms proposed here can be embedded within other packet and link scheduling frameworks in a fully evolved integrated services Internet

Maintaining end-to-end throughput in a differentiated-services Internet

Abstract: This paper examines the use of adaptive priority marking for providing soft bandwidth guarantees in a differentiated-services Internet. In contrast to other proposals for achieving the same objective, the proposed scheme does not require resource reservation for individual connections and can be supported with minimal changes to the network infrastructure. It uses modest support from the network in the form of priority handling for appropriately marked packets, and relies on intelligent transmission control mechanisms at the edges of the network to achieve the desired throughput levels. This paper describes the control mechanisms and evaluates their behavior in various network environments. These mechanisms are show in to have several salient features which make them suitable for deployment in an evolving Internet

Maintaining end-to-end throughput in a differentiated-services Internet

Abstract: This paper examines the use of adaptive priority marking for providing soft bandwidth guarantees in a differentiated-services Internet. In contrast to other proposals for achieving the same objective, the proposed scheme does not require resource reservation for individual connections and can be supported with minimal changes to the network infrastructure. It uses modest support from the network in the form of priority handling for appropriately marked packets, and relies on intelligent transmission control mechanisms at the edges of the network to achieve the desired throughput levels. This paper describes the control mechanisms and evaluates their behavior in various network environments. These mechanisms are show in to have several salient features which make them suitable for deployment in an evolving Internet

Scalable flow control for multicast ABR services

Abstract: We propose a flow control scheme for multicast ABR services in ATM networks. At the heart of the proposed scheme is an optimal second-order rate control algorithm, called the α-control, designed to deal with the variation in RM-cell round-trip time (RTT) resulting from dynamic “drift” of the bottleneck in a multicast tree. Applying two-dimensional rate control, the proposed scheme makes the rate process converge to the available bandwidth of the connection's most congested link. It also confines the buffer occupancy to a target regime bounded by a finite buffer capacity. It works well irrespective of the topology of the multicast tree. Using the fluid approximation, we model the proposed scheme and analyze the system dynamics for multicast ABR traffic. We study the convergence properties and derive the optimal control conditions for the α-control. The analytical results show that the scheme is stable and efficient in the sense that both the source rate and bottleneck queue length rapidly converge to a small neighborhood of the designated operating point. We present simulation results which verify the analytical observations. The simulation results also demonstrate the effectiveness of the proposed scheme in dealing with RM-cell RTT and link-bandwidth variations, and in achieving fairness in both buffer and bandwidth occupancies

A self-configuring RED gateway

Abstract: The congestion control mechanisms used in TCP have been the focus of numerous studies and have undergone a number of enhancements. However, even with these enhancements, TCP connections still experience alarmingly high loss rates, especially during times of congestion. To alleviate this problem, the IETF is considering active queue management mechanisms, such as random early detection (RED), for deployment in the network. In this paper, we first show that the effectiveness of RED depends, to a large extent, on the appropriate parameterization of the RED queue. We then show that there is no single set of RED parameters that work well under different congestion scenarios. In light of this observation, we propose and experiment with more adaptive RED gateways which self-parameterize themselves based on the traffic mix. The results show that traffic cognizant parameterization of RED gateways can effectively reduce packet loss, while maintaining high link utilizations under a range of network loads

Securing electronic commerce: reducing the SSL overhead

Abstract: The last couple of years have seen a growing momentum toward using the Internet for conducting business. Web-based electronic commerce applications are one of the fastest growing segments of the Internet today. A key enabler for e-commerce applications is the ability to setup secure private channels over a public network. The Secure Sockets Layer protocol provides this capability and is the most widely used security protocol in the Internet. We take a close look at the working principles behind SSL with an eye on performance. We benchmark two of the popular Web servers in wide use in a number of large e-commerce sites. Our results show that the overheads due to SSL can make Web servers slower by a couple of orders of magnitude. We investigate the reason for this deficiency by instrumenting the SSL protocol stack with a detailed profiling of the protocol processing components. In light of our observations, we outline architectural guidelines for large e-commerce sites

Design, implementation and performance of a content-based switch

Abstract: In this paper, we share our experience in designing and building a content-based switch which we call L5. In addition to the layer 2-3-4 information available in the packet, a content-based switch uses application level information to route traffic in the network. Making routing decisions based on information contained in the payload is not a new idea. In fact application level proxies which are functionally equivalent to a content-based switch, have been around for years. Our contribution is in combining the functionalities of an application level proxy with the data handling capabilities of a switch into a single system. In this paper, we describe the architecture of the L5 system along with the details of how application level information can be efficiently processed in the switch hardware. We cover two specific application examples that we believe are ideal candidates for content-based switching: one is routing HTTP sessions based on uniform resource locators (URL) and the other is session-aware dispatching of secure socket layer (SSL) connections

Capacity performance of dynamic provisioning in optical networks

Abstract: This paper describes an architecture and analyzes the performance of dynamic provisioning of lightpaths in an optical network. In dynamic provisioning, a lightpath is set up in real-time without rearranging the working and protection routes of existing lightpaths, and without the knowledge of future lightpath provisioning events. This paper develops a general model of the physical topology of the optical network, and outlines routing approaches for dynamic provisioning of lightpaths. It analyzes via simulations the performance of dynamically provisioned unprotected, 1+1 protected and mesh-restored lightpaths. The analysis of the efficiency of network utilization of dynamic provisioning focuses on the spare capacity needed for protection, and in particular focuses on the impact of sharing of wavelength channels for mesh-restored lightpaths. The main conclusion from the performance studies is that significant capacity gains are achieved with sharing of wavelength-channels for mesh-restored lightpaths with dynamic provisioning even for sparse topologies, and even at moderate loads

Stochastic fair blue: a queue management algorithm for enforcing fairness

Abstract: This paper describes and evaluates stochastic fair blue (SFB), a novel technique for enforcing fairness among a large number of rows. SFB scalably detects and rate-limits non-responsive flows through the use of a marking probability derived from the blue queue management algorithm and a Bloom (1970) filter. Using analysis and simulation, SFB is shown to effectively handle non-responsive flows using an extremely small amount of state information

Scalable flow control for multicast ABR services in ATM networks

Abstract: We propose a flow-control scheme for multicast ABR services in ATM networks. At the heart of the proposed scheme is an optimal second-order rate control algorithm, called the α-control, designed to deal with the variation in RM-cell round-trip time (RTT) resulting from dynamic drift of the bottleneck in a multicast tree. Applying two-dimensional rate control, the proposed scheme makes the rate process converge to the available bandwidth of the connection's most congested link sensed by the traffic source. It also confines the buffer occupancy to a target regime bounded by a finite buffer capacity as the system enters the equilibrium state. It works well irrespective of the topology of the multicast tree. Using the fluid analysis, we model the proposed scheme and analyze the system dynamics for multicast ABR traffic. We study the convergence properties and derive the optimal-control conditions for the α-control. The analytical results show that the scheme is stable and efficient in the sense that both the source rate and bottleneck queue length rapidly converge to a small neighborhood of the designated operating point. We present simulation results which verify the analytical observations. The simulation experiments also demonstrate the superiority of the proposed scheme to the other schemes in dealing with RM-cell RTT and link-bandwidth variations, achieving fairness in both buffer and bandwidth occupancies, and enhancing average throughput

The BLUE active queue management algorithms

Abstract: In order to stem the increasing packet loss rates caused by an exponential increase in network traffic, the IETF has been considering the deployment of active queue management techniques such as RED (random early detection) (see Floyd, S. and Jacobson, V., IEEE/ACM Trans. Networking, vol.1, p.397-413, 1993). While active queue management can potentially reduce packet loss rates in the Internet, we show that current techniques are ineffective in preventing high loss rates. The inherent problem with these algorithms is that they use queue lengths as the indicator of the severity of congestion. In light of this observation, a fundamentally different active queue management algorithm, called BLUE, is proposed, implemented and evaluated. BLUE uses packet loss and link idle events to manage congestion. Using both simulation and controlled experiments, BLUE is shown to perform significantly better than RED, both in terms of packet loss rates and buffer size requirements in the network. As an extension to BLUE, a novel technique based on Bloom filters (see Bloom, B., Commun. ACM, vol.13, no.7, p.422-6, 1970) is described for enforcing fairness among a large number of flows. In particular, we propose and evaluate stochastic fair BLUE (SFB), a queue management algorithm which can identify and rate-limit nonresponsive flows using a very small amount of state information.

Analysis of enhanced OSPF for routing lightpaths in optical mesh networks

Abstract: We discuss enhancements to the OSPF (open shortest path first) protocol for routing and topology discovery in optical mesh networks. OSPF's opaque LSA (link state advertisement) mechanism is used to extend OSPF to disseminate optical resource related information through optical LSAs. Standard link-state database flooding mechanisms are used for distribution of optical LSAs. Each optical LSA carries optical resource information pertaining to a single optical link bundle between two adjacent OXCs (optical cross connects), allowing for fine granularity changes in topology to be incorporated in path computation algorithms. OSPF packets are carried over a single IP control channel between adjacent OXCs. We analyze the performance of OSPF with optical extensions. Specifically, we compute control channel bandwidth used due to LSA updates. We also estimate the amount of memory required to store the LSA database. Finally, we study CPU usage for computing primary and backup lightpaths. Our analysis shows that the control channel bandwidth usage, memory requirement, and CPU usage are small enough to not be limiting factors for designing optical networks with single OSPF areas consisting of a large number (more than 500) of OXCs.