Institute for Systems Research Technical Reports

In this dissertation, we consider the behavior of generalized TCP congestion avoidance when subject to randomized congestion feedback, such as RED and ECN. The window distribution of individual flows under a variable packet loss/marking probability is established and studied to demonstrate the desirability of specifying a less drastic reduction in the window size in response to ECN-based congestion feedback.

A fixed-point based analysis is also presented to derive the mean TCP window sizes (and throughputs) and the mean queue occupancy when multiple such generalized TCP flows interact with a single bottleneck queue performing randomized congestion feedback.

Recommendations on the use of memory (use of weighted averages of the past queue occupancy) and on the use of "drop biasing" (minimum separation between consecutive drops) are provided to reduce the variability of the queue occupancy.

Finally, the interaction of TCP congestion avoidance with randomized feedback is related to a framework for global optimization of network costs. Such a relation is used to provide the theory behind the shape of the marking (dropping) functions used in a randomized feedback buffer.

We examine the question of how to model HSTN traffic for network dimensioning and performance prediction, and in particular, how far ahead into the future a traffic model can be expected to accurately function. We investigate these issues by directly comparing four of the most likely candidate statistical distributionshe exponential, log-normal, Weibull and Pareto. These distributions are fit to two key traffic parameters from real HSTN traffic traces (connection interarrival times and downloaded bytes), and their relative fits are compared using statistical techniques. We further compare traffic models built using these distributions in a simulated environment; comparing performance predictions (over a number of metrics) obtained from these models to the actual results from our real-world traffic traces.

Ourfirst contribution is the use of Fair Queueing in conjunction withProbabilistic Fair Drop, a new buffer management policy to allocatebandwidth and buffer space in the gateway, to ensure that all TCPflows threading the gateway achieve high end-to-end throughput andfair service.

Our second contribution is to introduce the concept ofbuffer dimensioning to alleviate the inherent bias of the TCPalgorithm towards connections with large Round Trip Time.

In supportof each of these contributions, we report on extensive simulationresults. Our scheme outperforms other resource allocation schemesreported in the literature and in particular, demonstrates significantimprovements in fairness to long RTT connections in the hybrid networkframework.

Existing theory is expanded intwo directions: the semi-Markov case is considered, and non-irreduciblechains are considered. In particular, the analysis of the non-irreduciblecase is a significant addition to the literature, since many real-worldsystems do not exhibit irreducibility under all stationary Markov policies. Extension of existing results to the semi-Markovcase is significant because it requires the definition of a newdynamic programming equation and a technically challenging adaptation of the Perron-Frobeniuseigenvalue from the discrete time case.

In order to determine an optimal policy, new concepts in the classificationof Markov chains need to be introduced. This is because in thenon-irreducible case, the average risk sensitive cost objective function permits extremely unlikely events to exert a controlling influence on costs. We define equivalence classes of statescalled `strongly communicating classes' and formulate in terms of thema new characterization of the underlying structureof Markov Decision Problems and Markov chains.

In the risk sensitive case, the expected cost incurred prior to a stopping time with finite expected valuecan be infinite. For this reason, we introduce an assumption: reachability with finite cost. This is the fundamental assumptionrequired to achieve the major results of this thesis.

We explore existence conditions for an optimal policy, optimality equations,and behavior for large and small risk sensitivity parameter. (Onlynon-negative risk parameters are discussed in this thesis -- i.e. the risk averse and risk neutral cases, not the risk seeking case.) Ramificationsfor the risk neutral objective function are also analyzed.Furthermore, a simple solution technique we call `recursive computation'to find an optimal policy that isapplicable to small state spaces is described through examples.

The countable state space case is explored, and results that hold only for a finite state space are also presented. Other, relatedobjective functions such as sample path cost are analyzed and discussed.

We also explore finite time horizon semi-Markov problems, and present a general technique for solving them.We define a new objective function, the minimization of which is calledthe `deadline problem'. This is a problem in which the probability of reaching the goal state in a set period of time is maximized. We transform thedeadline problem objective function into an equivalent finite-horizonrisk sensitive objective function.

Stochastic optimization is a direct application of the above root finding problem if the SA is driven by a gradient estimate of steady state performance. We study the convergence properties of an SA driven by agradient estimator which observes an increasing number of samples from the Markov chain at each step of the SA's recursion. To show almost sure convergence to the optimizer, a framework of verifiable conditions is introduced which builds on the general SA conditions proposed for the root finding problem.

We also consider a difficulty sometimes encountered in applicationswhen selecting the set used in the projection operator of the SA algorithm.Suppose there exists a well-behaved positive recurrent region of the state process parameter space where the convergence conditions are satisfied; this being the ideal set to project on. Unfortunately, the boundaries of this projection set are not known a priori when implementing the SA. Therefore, we consider the convergence properties when the projection set is chosen to include regions outside the well-behaved region. Specifically, we consider an SA applied to an M/M/1 which adjusts the service rate parameter when the projection set includes parameters that cause the queue to be transient.

Finally, we consider an alternative SA where the recursion is driven by a sample average of observations. We develop conditions implying convergence for this algorithm which are based on a uniform large deviation upper bound and we present specialized conditions implyingthis property for finite state Markov chains.

In an effort to understand the dynamics of a system supporting$M|G|infty$ traffic, we study the large buffer asymptotics of amultiplexer driven by an $M|G|infty$ input process. Using the largedeviations framework developed by Duffield and O'Connell, weinvestigate the tail probabilities for the steady-state buffercontent. The key step in this approach is the identification of theappropriate large deviations scaling. This scaling is shown to beclosely related to the forward recurrence time of the service timedistribution, and a closed form expression is derived for thecorresponding limiting log-moment generating functionassociated with the input process. Three different regimes areidentified.

The results are then applied to obtain the large bufferasymptotics under a variety of service time distributions. In eachcase, the derived asymptotics are compared with simulation results.

While the general functional form of buffer asymptotics may be derivedvia large deviations techniques, direct arguments often provide a moreprecise description when the input traffic is heavily correlated.Even so, several significant inferences may be drawn from thefunctional dependencies of the tail buffer probabilities. Theasymptotics already indicate a sub-exponential behavior in the caseof heavily-correlated traffic, in sharp contrast to the geometricdecay usually observed for Markovian input streams. This difference,along with a shift in the explicit dependence of the asymptotics onthe input and output rates $r_{in}$ and $c$, from $ ho=r_{in}/c$ when$G$ is exponential, to $Delta = c - r_{in}$ when $G$ issub--exponential, clearly delineates the heavy and light tailed cases.Finally, comparison with similar asymptotics for a different class ofinput processes indicates that buffer sizing cannot be adequatelydetermined by appealing solely to the short versus long-rangedependence characterization of the input model used.

In the first part of this thesis, we analyze theimplementation feasibility and overhead of these schemes to determinewhether this overhead represents an obstacle to deployment. To this end,we employ a novel approach with real traffic traces from the Internet anda passive gateway simulator.

Having established the feasibility of suchalgorithms, we turn our attention to buffer management techniques in thepresence of fair resource allocation. Our specific focus is on developingan effective buffer management technique for satellite networks. Thelimitations of existing schemes lead us to propose a new buffer managementscheme designed with our problem space in mind.

Finally, we look at aclass of satellite enhanced gateways, termed as connectionsplitting or spoofing gateways, proposed for implementing highperformance satellite systems. The specific design issues peculiar tothis class of gateways are analyzed. A novel architecture for fair resourceallocation in spoofing gateways is then proposed. The efficacy of ourarchitecture in providing fairness and protecting adaptive flows againstmisbehaved and non-adaptive flows is demonstrated by means of simulation.

We first present an analyticaltechnique to obtain the 'mean' queue occupancy and the 'mean' of the individual TCP windows. Armed with this estimate of the means, wethen derive the window distribution of each individual TCPconnection. Extensive simulation experiments indicate that, under a wide variety of operating conditions, our analytical method is quite accurate in predicting the 'mean' as well asthe distributions. The derivation of the individual distributions is based upon a numerical analysis presented which considers the case of a single TCP flow subject to variable state-dependent packet loss.