Since TCP Incast has been identified as a catastrophic problem in many typical data center applications, a lot of efforts have been made to analyze or solve it. The analysis work intends to model Incast problem from certain perspective, and the solutions try to solve the problem through designing enhanced mechanisms or algorithms. However, the proposed models are either closely coupled with particular protocol version or dependent on empirical observations, and the solutions cannot eliminate Incast problem entirely because the underlying issues are not identified completely. There is little work which attempts to close the gap between “analyzing” and “solving”, and present a comprehensive understanding. In this paper, we provide an in-depth understanding of how TCP Incast problem happens. We build up an interpretive model which emphasizes particularly on describing qualitatively how various factors, including system parameters and mechanism variables, affect network performances in Incast traffic pattern, but not on calculating the accurate throughput. With this model, we give plausible explanations why the various solutions for TCP Incast problem can help, but do not solve it entirely.

No abstract available.

Precomputation of the supported QoS is very important for internet routing. By constructing routing tables before a request arrives, a packet can be forwarded with a simple table lookup. When the QoS information is provided, a node can immediately know whether a certain request can be supported without launching the path finding process. Unfortunately, as the problem of finding a route satisfying two additive constraints is NP-complete, the supported QoS information can only be approximated using a polynomial time mechanism. A good approximation scheme should reduce the error in estimating the actual supported QoS. Nevertheless, existing approaches which determine this error may not truly reflect the performance on admission control, meaning whether a request can be correctly classified as feasible or infeasible. In this paper, we propose using a novel metric, known as distortion area , to evaluate the performance of precomputing the supported QoS. We then analyze the performance of the class of algorithms that approximate the supported QoS through discretizing link metrics. We demonstrate how the performance of these schemes can be enhanced without increasing complexity. Our results serve as a guideline on developing discretization-based approximation algorithms.

Bufferbloat is a phenomenon where excess buffers in the network cause high latency and jitter. As more and more interactive applications (e.g. voice over IP, real time video conferencing and financial transactions) run in the Internet, high latency and jitter degrade application performance. There is a pressing need to design intelligent queue management schemes that can control latency and jitter; and hence provide desirable quality of service to users. We present here a lightweight design, PIE (Proportional Integral controller Enhanced), that can effectively control the average queueing latency to a reference value. The design does not require per-packet extra processing, so it incurs very small overhead and is simple to implement in both hardware and software. In addition, the design parameters are self-tuning, and hence PIE is robust and optimized for various network scenarios. Simulation results, theoretical analysis and Linux testbed results show that PIE can ensure low latency and achieve high link utilization under various congestion situations.

Wireless Mesh Network (WMN) has become an important edge network to provide Internet access to remote areas and wireless connections in a metropolitan scale. In this paper, we study the problem of identifying the maximum available bandwidth path, a fundamental issue in supporting quality-of-service in WMNs. Due to interference among links, bandwidth, a well-known bottleneck metric in wired networks, is neither concave nor additive in wireless networks. We propose a new path weight which captures the available path bandwidth information. We formally prove that our hop-by-hop routing protocol based on the new path weight satisfies the consistency and loop-freeness requirements. The consistency property guarantees that each node makes a proper packet forwarding decision, so that a data packet does traverse over the intended path. Our extensive simulation experiments also show that our proposed path weight outperforms existing path metrics in identifying high-throughput paths.

This paper presents and develops a novel delay-based additive increase, multiplicative decrease (AIMD) congestion control algorithm. The main features of the proposed solution include: 1) low standing queues and delay in homogeneous environments (with delay-based flows only); 2) fair coexistence of delay- and loss-based flows in heterogeneous environments; 3) delay-based flows behave as loss-based flows when loss-based flows are present in the network; otherwise they revert to delay-based operation. It is also shown that these properties can be achieved without any appreciable increase in network loss rate over that which would be present in a comparable network of standard TCP flows (loss-based AIMD). To demonstrate the potential of the presented algorithm, both analytical and simulation results are provided in a range of different network scenarios. These include stability and convergence results in general multiple-bottleneck networks and a number of simulation scenarios to demonstrate the utility of the proposed scheme. In particular, we show that networks employing our algorithm have the features of networks in which RED AQM's are deployed. Furthermore, in a wide range of situations (including high-speed scenarios), we show that low delay is achieved irrespective of the queueing algorithm employed in the network, with only sender-side modification to the basic AIMD algorithm.

In this paper, we study the problem of computing the supported QoS from a source to a destination with multiple additive constraints. The problem has been shown to be NP-complete and many approximation algorithms have been developed. We propose a new approximation algorithm called multi-dimensional relaxation algorithm. We formally prove that our algorithm produces smaller approximation error than the existing algorithms. We further verify the performance by extensive simulations.

Finding the most likely path satisfying a requested additive Quality-of-Service (QoS) value, such as delay, when link metrics are defined as random variables by known probability distributions is NP-Hard. We transform the probability distributions into the Laplace domain, find the Laplace Transform of their convolutions and numerically inverse to find the distribution function in the time domain. Picard's iterative method of successive approximations is used to find the solution. To the best of our knowledge, ours is the first to propose a transform-based approach for the QoS routing problem of finding the most likely path. Simulations show that our stochastic approach (1) Selects correct paths more frequently, (2) Incurs less overhead with respect to the dissemination and processing of state information, and (3) Reduces the churn by selecting more stable paths.

Delay-based TCP variants continue to attract a large amount of attention in the networking community. Potentially, they offer the possibility to efficiently use network resources while at the same time achieving low queueing delay and virtually zero packet loss. One major impediment to the deployment of delay-based TCP variants is their inability to coexist fairly with standard loss-based TCP. In this paper we propose a simple strategy to make the fair coexistence possible and to ensure that delay-based flows will revert back to the delay-based operation when loss-based flows are no longer present. Analytical and ns-2 simulation results are presented to validate the proposed algorithm.

In this paper, we consider the problem of routing with two additive constraints in the hierarchical networks, such as the Internet. In order for scalability, the supported QoS information in the hierarchical networks has to be aggregated. We propose a novel method for aggregating the QoS information. To the best of our knowledge, our approach is the first study to use the area-minimization optimization, the de facto optimization problem of the QoS information aggregation. We use a set of real numbers to approximate the supported QoS between different domains. The size of the set is predefined so that advertisement overhead and the space requirement will not grow exponentially as the network size grows. The simulation results show that the proposed method outperforms the existing methods.

This paper presents a distributed polynomial algorithm for finding the maximum bandwidth path in Wireless Mesh Networks (WMNs). Our proposed algorithm can be applied for designing the proactive hop-by-hop routing protocol with bandwidth guarantee. To the best of our knowledge, our work is the first distributed path calculation algorithm in WMNs.

Routing is a process of finding a network path from a source node to a destination node. A good routing protocol should find the "best path" from a source to a destination. When there are independent constraints to be considered, the "best path" is not well-defined. In our previous work, we developed a line segment representation for Quality-of-Service routing with bandwidth and delay requirements. In this paper, we propose how to adopt the line segment when a request has two concave constraints. We have developed a series of operations for constructing routing tables under the distance-vector protocol. We evaluate the performance through extensive simulations.

Peer-to-peer (P2P) file sharing system such as BitTorrent performs better than traditional client-server system in "flash-crowd" scenario taking advantage of "perpendicular" bandwidth between peer nodes. However large amount of backbone bandwidth in the Internet is consumed by these ubiquitous P2P connections. In this paper, we propose centralized hierarchical peer-node assignment (CHPA) to globally manage P2P traffic by intentionally set up connections within local area network. Experiment result shows that: in our experiment environment, CHPA can achieve higher proportion of local area network traffic while download time of BT is not apparently affected.

The problem of finding a path that satisfies two additive constraints, such as delay and cost, has been proved to be NP-complete. Many heuristic and approximation algorithms have been developed to identify a path given a certain QoS request. Unfortunately, these algorithms cannot be applied directly in the Internet because routing in the Internet is based on table lookups and routing tables are computed before a request arrives. In this paper, we develop an approximation algorithm for computing the supported QoS going across a domain. We analyze the approximation error of our algorithm and formally prove that the approximation error of our proposed algorithm is smaller than those of the existing approaches. We further verify our performance using extensive simulations.

Network applications that are in need of some level of guarantees from the network to operate, such as multimedia programs, are not well served with the conventional best-effort service of the IP-based networks. The difficulty of finding preferential paths for those applications is compounded by the intrinsic inaccuracies of the network state information maintained by the nodes that have to make such decisions. We use a probabilistic modeling and a framework to select paths for applications that want more cooperation from the network to operate satisfactorily. The links are associated with additive link metrics. We represent the stochasticity of links by means of a new composite metric composed of an interval with a lower and upper bound and an associated probability. The interpretation and relevance of our metric is such that in the next decision time period the expected value of the resource is between the upper and the lower bound with the associated probability. Three simple and straightforward methods of computing our composite metric are presented. An algorithm, called Augmented-Dijkstra Additive Metric (ADAM), with the same complexity as the standard Dijkstra algorithm, provides an effective solution for statistical additive link metric (such as delay) guarantees. Simulation results conducted in ns2 evaluate and confirm the effectiveness of our approach.