Characterization of a Large Web Site Population with Implications for Content Delivery

This paper presents a systematic study of the properties of a large number of Web sites hosted by a major ISP. To our knowledge, ours is the first comprehensive study of a large server farm that contains thousands of commercial Web sites. We also perform a simulation analysis to estimate potential performance benefits of content delivery networks (CDNs) for these Web sites, and validate our analysis for several sites by replaying our trace through a real cache. We make several interesting observations about the current usage of Web technologies and Web site performance characteristics. First, compared with previous client workload studies, the Web server farm workload contains a much higher degree of uncacheable responses and responses that require mandatory cache validations. A significant reason for this is that cookie use is prevalent among our population, especially among more popular sites. We found an indication of widespread indiscriminate usage of cookies, which unnecessarily impedes the use of many content delivery optimizations. We also found that most Web sites do not utilize the cache-control features of the HTTP 1.1 protocol, resulting in suboptimal performance. Moreover, the implicit expiration time in client caches for responses is strongly constrained by the maximum values allowed in the Squid proxy. Thus, supplying explicit expiration information would significantly improve Web sites’ cacheability. Finally, our simulation results indicate that while most Web sites benefit from the use of a CDN, the amount of the benefit varies widely among the sites, which underscores the need for workload analysis tools. Bent, Rabinovich, and Xiao performed this work while at AT&T Labs-Research.     

Features of motion of dynamic systems with disturbances in the neighborhood of manifolds of switchings

The method of computation of control in real time of a linear system with disturbance is suggested. The system of linear algebraic equations is obtained, which links the deviations of phase coordinates to the deviations of initial conditions of the normalized conjugate system and to the deviation of the finite moment. The calculations reduce to the sequence of the solutions of systems of linear algebraic equations and the integration of a matrix differential equation over transfer intervals of the control switching moments and the finite moment of time. The correction of switching moments and the finite moment of control in the accompaniment of the phase trajectory of motion of a controllable object is considered. Simple constructive conditions of the origin of the sliding mode, motions of the representative point over manifolds of switchings, and changes of the control structure in accompanying the phase trajectory of the system motion are obtained. The convergence of the computational method is proved.     

An algebraic approach for $${\mathcal{H}}$$-matrix preconditioners

Hierarchical matrices ( -matrices) approximate matrices in a data-sparse way, and the approximate arithmetic for -matrices is almost optimal. In this paper we present an algebraic approach for constructing -matrices which combines multilevel clustering methods with -matrix arithmetic to compute the -inverse, -LU, and the -Cholesky factors of a matrix. Then the -inverse, -LU or -Cholesky factors can be used as preconditioners in iterative methods to solve systems of linear equations. The numerical results show that this method is efficient and greatly speeds up convergence compared to other approaches, such as JOR or AMG, for solving some large, sparse linear systems, and is comparable to other -matrix constructions based on Nested Dissection.     

Boolean models and planning methods for parallel abstract programs

For the parallel computer systems, a new formulation of the problem of constructing parallel asynchronous abstract programs of the desired length was proposed. The conditions for the problem of planning were represented as a system of Boolean equations (constraints) whose solutions define the feasible plans for activation of the program modules specified in the planner’s knowledge base. The constraints on the number of processors and time delays arising at execution of the program modules were taken into consideration.     

Exponential queuing system with negative customers and bunker for ousted customers

Consideration was given to the queuing system with Poisson flows of incoming positive and negative customers. For the positive customers, there is an infinite-capacity buffer. The arriving negative customer knocks out a positive customer queued in the buffer and moves it to an infinite-capacity buffer of ousted customers (bunker). If the buffer is empty, then the negative customer discharges the system without affecting it. After servicing the current customer, the server receives a customer from the buffer or, if the buffer is empty, the bunker. The customers arriving from both the buffer and bunker are distributed exponentially with the same parameter. Relations for calculation of the stationary distributions of the queues in the buffer and bunker were obtained.     

Decomposition of problems of optimal control and estimation for discrete systems with fast and slow variables

Consideration was given to the linear-quadratic problem of optimal control for the discrete linear system with fast and slow variables under incomplete information about system state. Decomposition of the discrete matrix Riccati equations was carried out. The proposed decomposition algorithm relies on a geometrical approach using the properties of the invariant manifolds of slow and fast motions of the nonlinear multirate discrete systems as basis. The splitting transformation was constructed in the form of asymptotic decomposition in the degrees of a small parameter.     

Optimality conditions of sliding modes and the maximum principle for control problems with the scalar argument

Various types of optimality criteria and conditions, which define the set of admissible solution, are brought to the canonical form. For the problem set in this form, the optimality conditions of sliding modes are stated. It is shown that the optimality conditions emerge from these conditions in the form of the maximum principle for problems with a scalar argument and an arbitrary combination of the optimality criterion and constraints.     

On instability of control systems for a certain class of objects and methods of its elimination

In practice of design of control systems, the cases occur when some of the roots of the transfer function of a controllable object are disposed on the imaginary axis of the complex plane. The optimal controller constructed for such objects, despite its realizability, will not afford the robustness properties in the system. The methods of removal of this phenomenon are given. The comparative estimate of the solution of this problem is provided both in the space of states and in the input-output relations (in the space of operators).     

Invariance for impulsive control systems

The conventional concepts of invariance are extended in this article to include impulsive control systems represented by measure driven differential inclusions. Invariance conditions and some of their main features are derived. The solution concept plays a critical role in the extension of the conditions for conventional problems to the impulsive control context.     

Two strong equilibria for game problems

The paper presents two new definitions of equilibrium for arbitrary game problems. The new definitions allow finding a unique solution for a significantly wider class of problems.     

Topological method for analysis of periodic canards

Singularly perturbed systems of ordinary differential equations are studied. A method for analysis of canard-type trajectories in such systems based on the topological degree theory is suggested. The method does not require smoothness of the right-hand side of the system. A result on the existence of periodic canards in systems with non-smooth perturbations is obtained. The trajectories located in this way are not necessarily Lyapunov stable, and appropriate control algorithms are required to stabilize them, e.g., feedback control.     

Modernization of one criterion for absolute stability

A new form of a partial frequency criterion of absolute stability for nonlinear automatic control systems is obtained basing on a quadratic transformation of the state vector. As is shown, the obtained criterion is stronger than V.M. Popov’s one. An alternative formulation of the criterion is given in terms excluding the notions of quadratic transformation.     

Conditional variational problems of control for distributed-parameter systems

Solved was a number of the classical variational problems of control of the distributed-parameter dynamic systems constrained also by nondifferential and differential equations. The corresponding rules of the Lagrange multipliers were formulated and proved. For the generalized diffusion and generalized wave processes, the results obtained were applied to the conditional variational problems of distributed optimal control. Derivation of the Euler-Poisson and Euler equations as applied to the designed control system was substantiated for these problems.     

The formula of the solution for some classes of initial boundary value problems for the hyperbolic equation with two independent variables

A new representation is proved of the solutions of initial boundary value problems for the equation of the form u _xx (x, t) + r(x)u _x (x, t) ? q(x)u(x, t) = u _tt (x, t) + μ(x)u _t (x, t) in the section (under boundary conditions of the 1st, 2nd, or 3rd type in any combination). This representation has the form of the Riemann integral dependent on the x and t over the given section.     

Estimation of non-stationary delay for a linear discrete dynamic plant

A nonlinear recurrent gradient-type algorithm is proposed for estimation of nonstationary delay arising in finite impulse response of a linear discrete dynamic plant. Convergence of the algorithm is investigated. Using linear matrix inequalities, its optimal functioning is investigated in order to provide for the maximal rate of convergence of the estimation error to zero.     

Polynomial modal control for sampled data systems with delay

The problem of modal sampled-data control for continuous-time linear time-invariant plant with delay is considered. The characteristic matrix of the system is constructed. An algorithm is given for generating the set of causal discrete-time controllers that place eigenvalues of the characteristic matrix at specified points of the complex plane.     

Discrete optimization with logical constraints for design of complex products

Consideration was given to the optimization problem arising at designing complex products. It was assumed that the products are formed of the components with allowance for certain conditions and criteria. To solve the problem, an approach relying on discrete optimization with logical constraints was developed. An algorithm to determine the precise solution on the basis of enumeration of L-classes was developed, and a computer-aided experiment carried out. The algorithm was incorporated in the software of the computer-aided clothing design system.