Scalability and traffic control in IP networks

title: Multiple Time Scale Congestion Control for Self-Similar Network Traffic
abstract: Analytical and empirical studies have shown that self-similar traffic can have a detrimental impact on network performance including amplified queuing delay and packet loss rate. Given the ubiquity of scale-invariant burstiness observed across diverse networking contexts, finding effective traffic control algorithms capable of detecting and managing self-similar traffic has become an important problem. In this paper, we study congestion control algorithms for improving network performance — in particular, throughput — under self-similar traffic conditions. Although scale-invariant burstiness implies the existence of concentrated periods of contention and idleness, the long-range dependence associated with self-similar traffic leaves open the possibility that correlation structure at larger time scales may be exploited for performance enhancement purposes. We construct a 2-level multiple time scale congestion control protocol that exercises congestion control concurrently across two time scales an order of magnitude apart. The first component — acting at the smaller time scale — is a generic linear increase/exponential decrease feedback congestion control that uses implicit prediction afforded by feedback to affect rate control sensitive to changes in network state at 20–200 ms time scales. The second component — acting at 2–5 s time scales — uses explicit prediction to detect persistent shifts in overall network contention and uses this information to modulate the aggressiveness exhibited by the first component. We show that cooperative interaction between the two congestion control modules acting on information at different time scales leads to improved performance vis-a-vis the case when the large time scale component is absent. We show that the improvement factor increases with long-range dependence and we show that as the number of flows engaging in multiple time scale congestion control (MTSC) increases, both fairness and efficiency are preserved.

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: 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: Towards communication-sensitive load balancing
abstract: Recent studies have shown that if the overhead associated with process migration is not high when compared to the estimated lifetime of processes, migrating isolated processes to underutilized workstations can improve system performance. However, if tightly-coupled processes from groups of communicating processes or other existing dependencies are separated, system performance can decrease due to increased communication cost. Current load balancers do not make effective use of communication dependencies in their algorithms. We have implemented a communication-sensitive load balancer for DUNES (Distributed UNix ExtenSion)-a user-level distributed operating system-that uses the run-time communication pattern between processes when balancing load. We examine communication-sensitive load balancing under different workload conditions and compare its performance against a load balancer that is not communication-aware. Our results show that a communication-sensitive load balancer performs substantially better than a load balancer that is not communication-aware under workloads that have a "good mix" of CPU-bound and I/O-bound processes.

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: Analysis and design of the virtual rate control algorithm for stabilizing queues in TCP networks
abstract: The virtual rate control (VRC) algorithm has been proposed for active queue management (AQM) in TCP networks. VRC, a rate-based control mechanism, responds quickly to traffic changes, thus allowing for high utilization and small loss. It can effectively stabilize both the input rate and the queue length around their target levels. In this paper, we analyze the stability of the VRC algorithm based on a linearized TCP model with time delay and provide a design guideline for parameter setting to make the overall system stable. Finally, we confirm the validity of our analysis and the effectiveness of VRC compared to RED, PI, REM, and AVQ through extensive ns-2 simulations.

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: A Work-Time Optimal Algorithm for Computing All String Covers
abstract: In recent study of repetitive structures of strings, generalized notions of periods have been introduced. A typical regularity, the period u of a given string x, grasps the repetitiveness of x since x is a prefix of a string constructed by concatenations of u. A substring w of x is called a cover of x if x can be constructed by concatenations and superpositions of w. The notion “cover” is a generalization of periods in the sense that superpositions as well as concatenations are considered to define it, whereas only concatenations are considered for periods. 
 
We consider the all-covers problem, i.e., that of computing all the covers of a given string of length n. We present an optimal O(log log n)-time CRCW PRAM algorithm for the all-covers problem. Since there is an Ω(log log n) lower bound on the time complexity of the all-covers problem, our algorithm is work-time optimal.

title: Securing Web Service by Automatic Robot Detection
abstract: Web sites are routinely visited by automated agents known as Web robots, that perform acts ranging from the beneficial, such as indexing for search engines, to the malicious, such as searching for vulnerabilities, attempting to crack passwords, or spamming bulletin boards. Previous work to identify malicious robots has relied on ad-hoc signature matching and has been performed on a per-site basis. As Web robots evolve and diversify, these techniques have not been scaling. 
 
We approach the problem as a special form of the Turing test and defend the system by inferring if the traffic source is human or robot. By extracting the implicit patterns of human Web browsing, we develop simple yet effective algorithms to detect human users. Our experiments with the CoDeeN content distribution network show that 95% of human users are detected within the first 57 requests, and 80% can be identified in only 20 requests, with a maximum false positive rate of 2.4%. In the time that this system has been deployed on CoDeeN, robot-related abuse complaints have dropped by a factor of 10.

title: Robust delay estimator for playout buffering in Internet audio applications
abstract: In this paper, we propose a robust delay estimation scheme for Internet multimedia applications. The proposed scheme adopts an autoregressive (AR) model for the delay process. The adopted AR model is a natural generalization of the Jacobson's algorithm in TCP retransmission timeout (RTO) estimation. However, unlike fixed parameter values in the Jacobson's algorithm, the parameters of the proposed scheme adapt themselves to the estimation error 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. As an application of the proposed algorithm, we consider the problem of delay prediction for audio playout buffering. We rigorously formulate the proposed scheme in the realm of multimedia audio mechanisms and give simulation result which shows its effectiveness.