Unbounded growth in the number of active flows can lead to severe service quality degradation to existing flows in a network . To guarantee minimum service quality for individual flows, specially for multimedia traffic, it is necessary to estimate and bound the number of active flows in the network. Prior work on estimating the number of active flows has been difficult without maintaining per-flow state. In this paper, we propose a light weight (not requiring per flow state) mechanism to estimate the number of active flows. This estimate is then used to determine the probability of admitting a new flow into the network with the goal of preventing extreme degradation of throughput to existing flows. The key idea here is that the number of active flows can be inferred from the frequency at which a newly arriving packet is part of the same flow as a randomly selected packet in the buffer. Since this scheme relies on information already available in the buffer, no per-flow state is maintained in the network. This mechanism requires very little per-packet processing, even less than a forwarding table lookup. Simulation results show that the proposed scheme can stabilize an overloaded network by bounding the number of active flows without significantly impairing link utilization. This scheme also gives good performance when buffer sizes are small and when the network has a mix of TCP and UDP traffic.

The issue of router buffer sizing is still open and significant. Previous work either considers open-loop traffic or only analyzes persistent TCP flows. This paper differs in two ways. First, it considers the more realistic case of non-persistent TCP flows with heavy-tailed size distribution. Second, instead of only looking at link metrics, we focus on the impact of buffer sizing on TCP performance. Specifically, our goal is to find the buffer size that maximizes the average per-flow TCP throughput. Through a combination of testbed experiments, simulation, and analysis, we reach the following conclusions. The output/input capacity ratio at a network link largely determines the required buffer size. If that ratio is larger than one, the loss rate drops exponentially with the buffer size and the optimal buffer size is close to zero. Otherwise, if the output/input capacity ratio is lower than one, the loss rate follows a power-law reduction with the buffer size and significant buffering is needed, especially with flows that are mostly in congestion-avoidance. Smaller transfers, which are mostly in slow-start, require significantly smaller buffers. We conclude by revisiting the ongoing debate on "small versus large" buffers from a new perspective.

Valiant's concept of randomized load balancing (RLB), also promoted under the name 'two-phase routing', has previously been shown to provide a cost-effective way of implementing overlay networks that are robust to dynamically changing demand patterns. RLB is accomplished in two steps; in the first step, traffic is randomly distributed across the network, and in the second step traffic is routed to the final destination. One of the benefits of RLB is that packets experience only a single stage of routing, thus reducing queueing delays associated with multi-hop architectures. In this paper, we study the queuing performance of RLB, both through analytical methods and packet-level simulations using ns2 on three representative carrier networks. We show that purely random traffic splitting in the randomization step of RLB leads to higher queuing delays than pseudo-random splitting using, e.g., a round-robin schedule. Furthermore, we show that, for pseudo-random scheduling, queuing delays depend significantly on the degree of uniformity of the offered demand patterns, with uniform demand matrices representing a provably worst-case scenario. These results are independent of whether RLB employs priority mechanisms between traffic from step one over step two. A comparison with multi-hop shortest-path routing reveals that RLB eliminates the occurrence of demand-specific hot spots in the network.

Tools such as pathchar, clink, and pchar attempt to measure the capacity of every layer-3 (L3) hop in a network path. These tools use the same underlying measurement methodology, which we refer to as Variable Packet Size (VPS) probing. The key assumption in VPS is that each L3 hop along a path increases the delay of a packet by a "serialization latency", which is the ratio of the packet size over that hop's capacity. Unfortunately, the capacity estimates of VPS tools are sometimes wrong. In this paper, we investigate the source of these errors, and show that the presence of layer-2 (L2) store-and-forward devices, such as Ethernet switches, have a detrimental effect on the accuracy of VPS tools. Specifically, each L2 store-and-forward device introduces an additional serialization latency in a packet's delay, which results in consistent underestimation of that L3 hop's capacity. We analyze this negative effect, deriving the measured capacity of an L3 hop as a function of the L2 link capacities at that hop. Experimental results in local, campus, and ISP networks verify the model, illustrating that L2 devices should be expected in networks of diverse type and size. Finally, we characterize some other sources of error in VPS tools, such as queueing delays, limited clock resolution, variation in ICMP generation delays, and error propagation along the measured path.

No abstract available.