Institute for Systems Research Technical Reports

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.

Following the successful implementation of basic algorithms for each of these test cases (shortest path routing, hard handoff, beacon monitoring, file transfer, deterministic packet transmission, single-priority FIFO queueing), we are currently working on replacing the MAC protocol with the ATM suite. The advantages of this approach are two-fold: first, it allows usgreater flexibility in including multiple service classes, traffic types andpriority schemes. Also it creates a well-defined network/switching layer upon which TCP/IP and UDP/IP can be evaluated.

In this paper we compare the three materializationpolicies (materialized inside the DBMS, materialized at the web serverand virtual) analytically, through a detailed cost model, andquantitatively, through extensive experiments on an implementedsystem. Our results indicate that materializing at the web server is amore scalable solution and can facilitate an order of magnitude moreusers than the virtual and materialized inside the DBMS policies, evenunder high update workloads.

This is a mixture of the traditional prefix-routed scenario fo the fixed Internet, and the classical edge mobility scenario that is today supported by cellularnetworks, primarily as part of the cellular technology elements (GSM, GPRS, etc.).

We outline a general architecture for the support of such edge mobility, and present an approach to FMC routing that fits within this architecture. We then present initial simulation resultsillustrating the potential scalability and routing efficiency of this approach.

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.