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

title: Multiple time scale redundancy control for QoS-sensitive transport of real-time traffic
abstract: End-to-end QoS control over best-effort and differentiated service networks which exhibit variability in their exported service properties looms as an important challenge. In previous work, we have shown how packet-level adaptive FEC can be used in dynamic networks to facilitate invariant user-specified QoS in an end-to-end manner. This paper addresses two important problems-self-similar burstiness and performance degradation of reactive controls subject to long feedback loops-complementing the stability/optimality considerations studied earlier. First, for adaptive redundancy control to be effective, its susceptibility to correlated packet drops and queueing delays stemming from self-similar burstiness must be fortified. Second, to preserve FEC's viability over ARQ when transporting real-time traffic in WAN, preactivity must be injected to offset the performance degradation of reactive feedback controls when subject to long RTT. In this paper, we use the recently advanced multiple-time-scale congestion control framework-first investigated in the throughput maximization context-to endow adaptive redundancy control with both selective protection against self-similar burstiness as well as preactivity to feedback redundancy control. We analyze, implement, and benchmark our protocol-AFEC-MT-in the context of transporting periodic real-time traffic, in particular, MPEG video.

title: On the performance characteristics of WLANs: revisited
abstract: Wide-spread deployment of infrastructure WLANs has made Wi-Fi an integral part of today's Internet access technology. Despite its crucial role in affecting end-to-end performance, past research has focused on MAC protocol enhancement, analysis and simulation-based performance evaluation without sufficient consideration for modeling inaccuracies stemming from inter-layer dependencies, including physical layer diversity, that significantly impact performance. We take a fresh look at IEEE 802.11 WLANs, and using a combination of experiment, simulation, and analysis demonstrate its surprisingly agile performance traits. Our main findings are two-fold. First, contention-based MAC throughput degrades gracefully under congested conditions, enabled by physical layer channel diversity that reduces the effective level of MAC contention. In contrast, fairness and jitter significantly degrade at a critical offered load. This duality obviates the need for link layer flow control for throughput improvement but necessitates traffic control for fairness and QoS. Second, TCP-over-WLAN achieves high throughput commensurate with that of wireline TCP under saturated conditions, challenging the widely held perception that TCP throughput fares poorly over WLANs when subject to heavy contention. We show that TCP-over-WLAN prowess is facilitated by the self-regulating actions of DCF and TCP congestion control that jointly drive the shared physical channel at an effective load of 2--3 wireless stations, even when the number of active stations is very large. Our results highlight subtle inter-layer dependencies including the mitigating influence of TCP-over-WLAN on dynamic rate shifting.

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

title: Scalability and traffic control in IP networks

title: Performance evaluation of multiple time scale TCP under self-similar traffic conditions
abstract: Measurements of network traffic have shown that self-similarity is a ubiquitous phenomenon spanning across diverse network environments. In previous work, we have explored the feasibility of exploiting long-range correlation structure in self-similar traffic for congestion control. We have advanced the framework of multiple time scale congestion control and shown its effectiveness at enhancing performance for rate-based feedback control. In this article, we extend the multiple time scale control framework to window-based congestion control, in particular, TCP. This is performed by interfacing TCP with a large time scale module that adjusts the aggressiveness of bandwidth consumpton behavior exhibited by TCP as a function of large time scale network state, that is, information that exceeds the time horizon of the feedback loop as determined by RTT. How to effectively utilize such information—due to its probabilistic nature, dispersion over multiple time scales, and realization on top of existing window-based congestion controls—is a nontrivial problem. First, we define a modular extension of TCP (a function call with a simple interface that applies to various flavors of TCP, e.g., Tahoe, Reno, and Vegas) and show that it significantly improves performance. Second, we show that multiple time scale TCP endows the underlying feedback control with proacativity by bridging the uncertainty gap associated with reactive controls which is exacerbated by the high delay-bandwidth product in broadband wide area networks. Third, we investigate the influence of three traffic control dimensions—tracking ability, connection duration, and fairness—on performance. Performance evaluation of multiple time scale TCP is facilitated by a simulation benchmark environment based on physical modeling of self-similar traffic. We explicate our methodology for disc

title: Robust Delay Estimation for Internet Multimedia Applications
abstract: Traffic estimation and modeling has been a crucial issue in many research areas of communication networks. For example, intermediate routers in networks estimate the rate of packet flows via queue size information in order to maximize throughput and provide fairness between flows. Also, many senders in the end system such as multi-media applications estimate end-to-end delay between a sender and a receiver to reduce dropping probability of packet. In this position paper, we propose a robust adaptive estimation scheme for Internet multimedia applications. The proposed scheme adopts an autoregressive (AR) model for the process and identifies the parameters of the AR process via a robust identification algorithm. This robust identification algorithm usually leads to better performance when the noise is correlated and/or non-stationary, and it is also more robust to modeling uncertainties. Here, we consider the problem of end-to-end delay estimation for audio playout mechanisms. We rigorously formulate the proposed scheme in the realm of audio playout mechanisms and give some preliminary simulation result which shows effectiveness of the proposed scheme. Even though we apply the proposed scheme to the estimation of end-to-end delay in audio applications, the scheme itself is very general and we expect that it can be applied to many other estimation problems in Internet multimedia applications.

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

title: Efficient Algorithms for Approximate String Matching with Swaps
abstract: Most research on the edit distance problem and thek-differences problem considered the set of edit operations consisting of changes, insertions, and deletions. In this paper we include theswapoperation that interchanges two adjacent characters into the set of allowable edit operations, and we present anO(tmin(m,n))-time algorithm for the extended edit distance problem, wheretis the edit distance between the given strings, and anO(kn)-time algorithm for the extendedk-differences problem. That is, we add swaps into the set of edit operations without increasing the time complexities of previous algorithms that consider only changes, insertions, and deletions for the edit distance andk-differences problems.

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

title: On the effectiveness of route-based packet filtering for distributed DoS attack prevention in power-law internets
abstract: Denial of service (DoS) attack on the Internet has become a pressing problem. In this paper, we describe and evaluate route-based distributed packet filtering (DPF), a novel approach to distributed DoS (DDoS) attack prevention. We show that DPF achieves proactiveness and scalability, and we show that there is an intimate relationship between the effectiveness of DPF at mitigating DDoS attack and power-law network topology.The salient features of this work are two-fold. First, we show that DPF is able to proactively filter out a significant fraction of spoofed packet flows and prevent attack packets from reaching their targets in the first place. The IP flows that cannot be proactively curtailed are extremely sparse so that their origin can be localized---i.e., IP traceback---to within a small, constant number of candidate sites. We show that the two proactive and reactive performance effects can be achieved by implementing route-based filtering on less than 20% of Internet autonomous system (AS) sites. Second, we show that the two complementary performance measures are dependent on the properties of the underlying AS graph. In particular, we show that the power-law structure of Internet AS topology leads to connectivity properties which are crucial in facilitating the observed performance effects.