With all its history of reliable performance, the TCP protocol is known to break down in a situation with high loss and high RTT. A known solution is "Split TCP", where one or a few proxies (helper boxes) are used to break the end-to-end TCP connection into a few (almost) independent legs. Each leg has its own feedback, congestion control, error control mechanism, etc. The main contributions of our work are the design and implementation of "Split TCP" using Netfilter Hooks in the Linux kernel, and the use of IP over IP for transport. The kernel implementation reduces overhead. The implementation used leaves TCP packets and flags intact, thus allowing use of Telnet (etc) over a Split TCP connection. The primary area of use is for Internet connections, irrespective of the user application. Connections can be split into legs having high RTT or high loss, preferably not both. The use of IP over IP allows use of many helper boxes in a connection and makes it easier to achieve transparency for the original end-hosts.

We propose a forward resource reservation (FRR) scheme to reduce the data burst delay at edge nodes in optical burst switching (OBS) systems. We also explore algorithms to implement the various intrinsic features of the FRR scheme. Linear predictive filter (LPF)-based methods are investigated and demonstrated to be effective for dynamic burst-length prediction. An aggressive resource reservation algorithm is proposed to deliver a significant performance improvement with controllable bandwidth cost. By reserving resources in an aggressive manner, an FRR system can reduce both the signaling retransmission probability and the bandwidth wastage as compared with a system without the aggressive reservation. An FRR-based QoS strategy is also proposed to achieve burst delay differentiation for different classes of traffic. Theoretical analysis and simulation results verify the feasibility of the proposed algorithms and show that our FRR scheme yields a significant delay reduction for time-critical traffic without incurring a deleterious bandwidth overhead.

The paper analyzes how using a longer memory of the past queue occupancy in computing the average queue occupancy affects the stability and variability of a RED queue. Extensive simulation studies with both persistent and Web TCP sources are used to study the variance of the RED queue as a function of the memory of the averaging process. Our results show that there is very little performance improvement (and in fact, possibly significant performance degradation) if the length of memory is increased beyond a very small value. Contrary to current practice, our results show that a longer memory reduces the negative correlation typically observed among the windows of the constituent TCP flows, and hence, suggest the use of the instantaneous queue occupancy in practical RED queues.

To model possible suggested changes in TCP window adaptation in response to randomized feedback, such as ECN (explicit congestion notification), we formulate a generalized version of the TCP congestion avoidance algorithm. We first consider multiple such generalized TCP flows sharing a bottleneck buffer under the assured service model and use a fixed point technique to obtain the mean window sizes and throughputs for the TCP flows, To further study how changes in the adaptation algorithm affect the variability in the throughput, we use an analytical-cum-numerical technique to derive the window distribution (and related statistics) of a single generalized flow under state-dependent randomized congestion feedback.

This paper analyzes the stationary behavior of the TCP congestion window performing ideal congestion avoidance when the packet loss probability is not constant, but varies as a function of the window size. By neglecting the detailed window behavior during fast recovery, we are able to derive a Markov process that is then approximated by a continuous-time, continuous state space process. The stationary distribution of this process is analyzed and derived numerically and then extrapolated to obtain the stationary distribution of the TCP window. This numerical analysis enables us to predict the behavior of the TCP congestion window when interacting with a router port performing early random drop (or random early detection) where the loss probability varies with the queue occupancy.

This paper describes a mechanism we call "SRED" (stabilized random early drop). Like RED (random early detection) SRED pre-emptively discards packets with a load-dependent probability when a buffer in a router in the Internet or an intranet seems congested. SRED has an additional feature that over a wide range of load levels helps it stabilize its buffer occupation at a level independent of the number of active connections. SRED does this by estimating the number of active connections or flows. This estimate is obtained without collecting or analyzing state information on individual flows. The same mechanism can be used to identify flows that may be misbehaving, i.e. are taking more than their fair share of bandwidth. Since the mechanism is statistical in nature, the next step must be to collect state information of the candidates for "misbehaving", and to analyze that information. We show that candidate rows thus identified indeed have a high posterior probability of taking a larger than average amount of bandwidth.

This paper reports on a simulation study of the relative performances of the ATM ABR and UBR service categories in transporting TCP/IP flows through an ATM Network. The objective is two-fold: (i) to understand the interaction between the window - based end-to-end flowcontrol TCP and the rate based flowcontrol ABR which is restricted to the ATM part of the network, and (ii) to decide whether the greater complexity of ABR (than UBR) pays off in better performance of ABR (than UBR).The most important conclusion is that there does not seem to be strong evidence that for TCP/IP workloads the greater complexity of ABR pays off in better performance.

This paper proposes the use of a "drop from front" scheme for improving TCP performance in high bandwidth-delay product networks. In particular, for "TCP over ATM" we compare the performance when drop from front is used at the output port of ATM switches with the performance under tail drop, its variations, and with variations of random early detection (RED). In drop from front, when a cell arrives at a full buffer, the cell closest to being transmitted is dropped, thus creating space for the arriving cell. This policy causes duplicate acknowledgements to be sent one whole buffer drain time earlier than is the case under tail drop. These quicker duplicate acknowledgements cause TCP with fast retransmit to recognize losses faster and invoke congestion control actions earlier than would be the case under tail drop. This earlier reaction translates into considerable performance improvement. Hence, drop from front successfully utilizes the ability of TCP with fast retransmit to quickly recognize and react to congestion information (at the third repeat acknowledgement, as opposed to time-out). Roughly, the earlier action by the sources causes the congestion not to grow quite as severe, which prevents later over-reaction by the sources, and thus increases throughput.

No abstract available.

The authors present a scheme for smoothing delay-sensitive traffic offered to an asynchronous transfer mode (ATM) network. They outline such a smoothing scheme, which, when applied to variable bit rate (VBR) coded video traffic, is both optimal and avoids violation of delay constraints. The scheme is based on the assumption that recent behavior of the traffic stream can be used to predict the behavior of the input stream in the near future. The effectiveness of the scheme was evaluated by simulation. The conclusion is that even with a rudimentary forecasting rule, smoothing can lower cell losses and increase the effectiveness of VBR schemes for video transmission.>

LetX1,...,Xn be pairwise independent random variables of known (but not necessarily identical) distribution; we wish to select a subset of these whose sum will be as close as possible to some known target value T. Conditions described below force the selections to be made by a primitive distributed system (similar to one considered by Papadimitriou and Yannakakis [2] in PODC '91); here we are able to obtain a surprising amount of information about optimal solutions.The conditions are that each variable must be “programmed” in advance, joining the selected set according to its own value. Thus, for example, one variable might be programmed to join just if its value lies between a and b, while another is told to join regardless of its value. Our object is to find a strategy, that is, a collection of programs, which minimizes the mean square error in approximating T. Typical applications involve producing a steady flow of some commodity when supply is controlled at a multiplicity of random sources.It turns out that there is always an optimal strategy in which each Xi is programmed to join if its value is between 0 and ti, for appropriate choice of thresholds ti. When the variables are identically distributed, we examine conditions under which the ti's must be equal. The case of uniform distributions on [0,1], for which the above conditions are not satisfied, is analyzed in detail, showing the rather bizarre behavior of the ti's which may take place in general as the target value is gradually changed.Next, we analyze the problem in which the variables are permitted to contribute any part of themselves to the sum; here it turns out that in an optimal strategy each program will be of the form “contribute the minimum of Xi and ei” with all the ei's equal in the i.i.d. case.Finally, we show how the original target shooting problem can be generalized to a kind of load balancing, where variables are assigned to different buckets, each with its own target, and the penalty is a weighted sum of squared errors. The surprising result here is that when the weights are equal, an optimal solution assigns variables only according to their signs.

Let K ( m ) denote the smallest number with the property that every m -state finite automaton can be built as a neural net using K ( m ) or fewer neurons. A counting argument shows that K ( m ) is at least Ω(( m log m ) 1/3 ), and a construction shows that K ( m ) is at most O ( m 3/4 ). The counting argument and the construction allow neural nets with arbitrarily complex local structure and thus may require neurons that themselves amount to complicated networks. Mild, and in practical situations almost necessary, constraints on the local structure of the network give, again by a counting argument and a construction, lower and upper bounds for K ( m ) that are both linear in m .

Dynamic load balancing in a system of loosely-coupled homogeneous processors may employ both judicious initial placement of processes and migration of existing processes to processors with fewer resident processes. In order to predict the possible benefits of these dynamic assignment techniques, we analyzed the behavior (CPU, disk, and memory use) of 9.5 million Unix* processes during normal use. The observed process behavior was then used to drive simulation studies of particular dynamic assignment heuristics.Let F(·) be the probability distribution of the amount of CPU time used by an arbitrary process. In the environment studied we found: (1-F(x)) n rx-c, 1.05