Les séminaires du projet MISTRAL en année scolaire 97-98

Seminars of Project MISTRAL in the academic year 97-98

Pointeurs vers les autres annonces:

Résumés (Abstracts)

Bias Optimality in a Two-Class Queueing System
Hayriye Ayhan (Georgia Institute of Technology)

We consider a finite capacity queueing system with a Poisson arrival process and exponential service times. Arriving customers are of two types and offer a reward depending on their type. The server must then decide, based on the reward being offered and how much space is remaining, whether the arriving customer should be accepted. A traditional objective function is to maximize the gain; that is, the long run average reward. However, it is quite possible to have multiple gain optimal policies. Bias optimality is a more refined objective function which can distinguish among multiple gain optimal policies. This talk focuses on describing the structure of stationary, deterministic optimal policies and extending this optimality to distinguish between multiple gain optimal policies. We show that these policies are of trunk reservation type and must occur at consecutive trunk reservation levels. We then prove that we can distinguish among these gain optimal policies using the bias (transient reward).

This is a joint work with Robert D. Foley and Mark E. Lewis.

Optimal Control of Assignment of Jobs to Processors Under Heavy Traffic
Harold J. KUSHNER (Brown University, USA)

We treat many forms of the classical assignment problem. Jobs and their work rerquirements arrive at random. The jobs fall into two classes, dominant streams and streams which occur with less frequency. Only the latter are controlled, but the model is the basis for the general problem. They can be either queued or assigned immediately to a processor queue. There are several processors, differing in speeds, etc. The optimal control problems under heavy traffic converge to a limit optimal control problem, and good controls for the limit problem are also good for the physical problem, even under moderate traffic. There can be state dependence, batch arrivals, different information structures, and rather arbitrary cost functions.

Arrangements of points: asymptotical optimality.
Sergei Zouev (INRIA Sophia Antipolis)

Let F be a functional of configurations of N independently distributed in a phase space X. Let p_N(x) with the point density that minimizes the expectation of F. We present a new method based on the stochastic gradient tecnique for Poisson processes that allows in many cases to find the asymptotically optimal density p(x)=lim_N p_N(x).

On the Stable Behaviors of Window Flow Control
Thomas Bonald (INRIA Sophia Antipolis)

Flow control mechanisms are used in packet-switched networks to prevent routers from congestion, by regulating sending rate of the users. The most widely used mechanism is the window-based scheme, like that of TCP over the Internet. In such a scheme, the destination sends an acknowledgment to the source upon reception of a packet, and the window refers to the maximal number of unacknowledged packets in the network. The goal of this work is to evaluate the impact of the exogenous traffic generated by the other connections on the performance of the window flow control. Our approach consists in studying the stability of a model where the input flows are represented by stationary ergodic point processes. By establishing necessary and sufficient conditions for stability, we obtain bounds on the maximal throughput allowed by the flow control. These results are illustrated by several examples. Keywords: Window flow control, TCP, stability, stationary ergodic point process, (max,+)-linear system. This is a joint work with Francois Baccelli.

Random walks in random environment: martingale approach
M. Menshikov (Moscow State University)

We consider two examples of countable Markov chains in random environment using the Lyapunov functions approach: a one-dimensional random walk and a random string. In each case for typical configurations of the environment we obtain a full classification of the ergodic and transience behavior of the corresponding model.

Evénements Rares de Processus Stationnaires
Francois Baccelli (INRIA Sophia Antipolis)

Kielson (1979) et Aldous (1989) ont donné des expressions pour le comportement asymptotique du temps moyen jusqu'à l'occurrence d'un événement rare. Dans cet article, nous généralisons ces résultats du cadre markovien au cadre stationnaire grâce à la la théorie des processus ponctuels. Deux notions d'indépendance et d'exponentialité asymptotiques sont introduites qui permettent d'étudier le comportement asymptotique de ce temps moyen sous diverses lois de probabilité.

On the Time-Dependent Occupancy and Backlog Distributions for the GI/G/infinity Queue
Hayriye Ayhan (Georgia Institute of Technology)

We consider an infinite server queueing system. An examination of sample path dynamics allows a straightforward development of integral equations having solutions that give time-dependent occupancy (number of customers) and backlog (unfinished work) distributions (conditioned on the time of the first arrival) for the GI/G/\infty queue. These integral equations are amenable to numerical evaluation and can be generalized to characterize GI^X/G/\infy queue. Two examples are given that illustrate the results.

This is a joint work with J.Limon-Robles and M.A. Wortman.

From Optimal Search Theory to Sequential Paging in Cellular Networks
Armand M. Makowski (University of Maryland and INRIA Sophia Antipolis)

A more efficient use of limited wireless resources in emerging personal communication services (PCS) requires much smaller cells (micro-cells and picocells) than those used in conventional cellular networks. Tracking the mobile stations will become a challenging task as the cell sizes shrink and the number of cells increases.

In order to ensure reliable communication, a mobile station has to send/receive signaling messages from/to the base station. Depending on the system design, signaling messages serve various purposes such as frame synchronization, base station identification, mobility management, handoff decision making, etc. With the expansion of both the number of services available to users, and the number of mobile stations in service, the radio spectrum will become a scarce commodity. This calls for a reduction in the signaling load between the mobile station and the base station in order to make more bandwidth available for voice and data traffic. One way to reduce the signaling load associated with paging and location area updating is to deploy cellular networks with more intelligent mobile tracking and location management techniques.

In this talk, we propose a novel paging architecture that reduces the signaling load while expediting the paging process. The method is based on the theory of optimal search with discrete efforts, and exploits the observation that paging a mobile station resident in one of several cells is analoguous to searching an object hidden in one of a finite number of boxes. Building on this analogy, we integrate some well--known optimal search strategies into a novel paging technique. The proposed scheme requires minimal computational power in the base stations and switching centers, is fully compatible with standard mobility management techniques and does not require additional database resources to keep track of the movements of the mobile station within a location area. Moreover, through simulations, we show that the performance characteristics of this paging scheme are often superior to that of the conventional blanket paging algorithm.

Fixed Priority Preemptive Scheduling: Stochastic Response Times Bounds
Jorn MIGGE (INRIA Sophia Antipolis)

The main concern about real-time systems is the observance of deadlines, generally called feasibility. If this property is satisfied the integrity of the system is meant to be ensured.

To determine if a system is indeed feasible, it is necessary to find the worst case response times of tasks, for the given scheduling policy. However, deadlines are not always critical and thus it is not just necessary to know if a task completes in time or not. If longer response times are permitted, provided that they occur not to often, a less tight deadline could be chosen, increasing the chance of the hole task set to be feasible. Thus, it would be useful to know more about the distribution of response times.

For the fixed priority preemptive scheduling-policy, we have derived a bound on the tail of the response time distributions, in the case where inter-activation and execution times are assumed to be independent and bounded. We have studied their efficiency using simulations.

Some Scheduling Problems in the Web Search Engines
Zhen LIU et Jerome TALIM (INRIA Sophia Antipolis)

Robots are deployed by a Web search engine in order to maintain the currency of its data base of Web pages. In this talk we address some scheduling problems arising in these systems.

The first problem is concerned with the robot scheduling policies that minimize the fractions $r_i$ of time pages spend out-of-date, assuming independent Poisson page-change processes, and a general distribution for the page access time $X$. We show that, if $X$ is decreased in the increasing-convex ordering sense, then $r_i$ is decreased for all $i$ under any scheduling policy, and that, in order to minimize expected total obsolescence time of any page, the accesses to that page should be as evenly spaced in time as possible.

We then investigate the problem of scheduling to minimize the cost function $\sum c_i r_i,$ where the $c_i$ are given weights proportional to the page-change rates $\mu_i$. We give a tight bound on the performance of such a policy and prove that the optimal frequency at which the robot should access page $i$ is proportional to $\ln (h_i)^{-1}$, where $h_i := {\rm E}e^{-\mu_iX}.$ Note that this reduces to being proportional to $\mu_i$ when $X$ is a constant, but not, as one might expect, when $X$ has a general distribution.

Next, we evaluate randomized accessing policies whereby the choices of page access are determined by independent random samples from the distribution $\{f_i\}$. We show that when the weights $c_i$ in the cost function are proportional to $\mu_i$, the minimum cost is achieved when $f_i$ is proportional to $(h_i)^{-1} - 1$. We shall also present and analyze a heuristic policy that is especially suited to the asymptotic regime of large data bases.

Last, we discuss about the problem of determining the number of robots to be used in order to maximize the indexing throughput while keeping the communication and/or CPU overhead small. To solve this problem, we use a queueing system with a finite-capacity buffer to model the indexing engine. The cost function is defined as a combination of the probabilities of empty buffer and full buffer. Both dynamic and static policies are considered.

The first part of results is obtained jointly by Z. Liu and Ed. Coffman, and will be presented by Z. Liu. The last part of results is obtained by J. Talim, Z. Liu and P. Nain.

On the $\phi$-renovation
Serguei FOSS (INRIA et Univ. de Novossibirsk)

Let $X(n+1) = f(X(n), \xi_n)$ be a stochastic recursive sequence taking values in a state space ${\cal X}$, and $\phi : {\cal X} \to {\cal Y}$ be a measurable function. We discuss conditions for the sequence $Y(n)= \phi (X(n))$ to converge to a proper limit in the total variation norm.

On a Perfect Simulation of Stationary Distributions by Backwards Coupling.
Serguei FOSS (INRIA et Univ. de Novossibirsk)

Algorithms for perfect or exact simulation of random samples from the invariant measure of a Markov chain have received considerable recent attention following the introduction of the ``coupling-from-the-past'' technique of Propp and Wilson. 1. We place such algorithms in the context of backward coupling of stochastic recursive sequences. 2. We discuss also the problem how to eliminate the user- impatience bias. In fact, the running time of the Propp-Wilson algorithm (as well as that of similar ones) is a random variable with an unbounded support, whose order of magnitude is typically unknown a priori and which depends, in general, on the state sampled, so a user with limited patience has to introduce a systematic bias by aborting a long run.

How does functional and quantitative analysis of discrete event dynamic systems profit from Kronecker algebra?
Peter Kemper (Universitt Dortmund)

A variety of formalisms exists for the modeling and description of discrete event dynamic systems (DEDS), which typically allow for a distributed state description and local state transition rules. Petri nets are a well known example of this class. Deciding functional or quantitative properties of a model at the level of the modeling formalims itself is only possible in severly restricted cases. Hence most analysis methods map a model to an associated labeled transition system (LTS), e.g. a reachability graph, and analyze the LTS instead. Realworld applications of this technique yield extremely large LTS with obvious implications for computation times and space requirements. Kronecker representations of LTS result in a suitable data structure to reduce space requirements for the representation of an LTS significantly. This talk gives an overview of different matrix representations of LTS using Kronecker algebra. It focuses on the key ideas and observations to make analysis algorithms for functional and quantitative analysis work efficiently with Kronecker representations of LTS.

Calcul exact de taux de croissance pour des modeles de tas de pieces
Jean Mairesse (LIAFA)

On appelle modele de tas de pieces, un systeme constitue d'un ensemble fini de pieces (ou blocs solides ayant la forme de polyominos) et d'une operation de concatenation qui consiste a empiler les pieces suivant le mecanisme du jeu de Tetris. Dans le cas d'un modele aleatoire, on choisit de facon i.i.d. la suite de pieces a empiler.

On rappellera dans un premier temps comment la hauteur d'un empilement s'obtient a l'aide d'un systeme lineaire dans le semi-anneau (max,+). On demontre ensuite que la vitesse de croissance asymptotique des empilements est calculable a l'aide d'un automate fini: (i) pour le comportement optimal si les pieces sont a hauteurs entieres; (ii) pour le comportement en moyenne (cas aleatoire) si les pieces sont a hauteurs entieres et sont 2 a 2 non-commutantes. Le premier resultat se demontre a l'aide d'une generalisation des Formes Normales de Cartier-Foata, et le second par une operation dite de ``completion'' qui peut s'interpreter de facon algebrique comme une residuation matricielle dans le semi anneau (max,+).

C'est un travail commun avec Stephane Gaubert, Inria Rocquencourt.

The Fluid Approximation Approach: a Generalized Stability Criterion and its Application to a Polling System
Serguei FOSS (INRIA et Univ. de Novossibirsk)

Recently, the fluid approximation approach (introduced by P.R.Kumar, H.Chen and A.Mandelbaum, A.Rybko and A.Stolyar, J.Dai) became a very popular and useful tool for a stability study of queueing models. Verbally, one can explain the main idea of this approach as follows. For a Markov process X(t), t \geq 0 that characterizes a dynamical behavior of a system, (a) one introduces an appropriate linear scaling (the same in time and in space) where a scaling parameter is a norm |X(0)|= const at time 0, and (b) one considers a family of weak limits when |X(0)| \to \infty . Each such a limit \varphi (t); t \geq 0 is called a {\it fluid limit}, and the family of all fluid limits (or its weak closure) is called a {\it fluid model}. A fluid model is {\it stable} if there exist a finite constant T and a constant \varepsilon \in (0,1] such that |\varphi (T)| \leq 1 - \varepsilon a.s. for any fluid limit. It is known (J.Dai(95)) that if a fluid model is stable, then (under certain integrability assumptions) the underlying Markov process is positive recurrent. We introduce a more general notion of stability of fluid model: the fluid model is stable if there exist a constant \varepsion \in (0,1] and, for any fluid limit \varphi, a stopping time T_{\varphi} such that (a) {\bf E} |\varphi (T_{\varphi})| \leq 1 - \varepsion ; (b) random variables \{ T_{\varphi} \} are uniformly integrable. We show that the stability of fluid model in this more general sense implies the positive recurrence of Markov process as well. The example of two-server two-station polling model will be considered also. It will be shown that (i) the corresponding fluid model may be unstable in the ``pathwise'' sense but stable in our generalized one; (ii) under certain conditions, the total amount of fluid may tend to 0 even in the unstable case; (iii) some intriguing open problems will be discussed also.

A Pragmatic Approach for Guaranteeing QoS to Regulated Traffic in Networks.
Keith Ross (Eurecom)

Multimedia traffic can tolerate some loss but has rigid delay constraints. A natural QoS requirement for a multimedia connection is a prescribed bound on the the fraction of traffic that exceeds an end-to-end delay limit. To account for a diversity of traffic types, the end-to-end delay limit and the prescribed bound should be connection specific. In this talk we consider traffic management schemes that guarantee QoS to multimedia traffic while simultaneously permitting the network to have a large connection-carrying capacity. In order for the network to guarantee QoS, each connection's traffic is regulated. In order to support many connections, the links statistically multiplex the connections' traffic. We propose a pragmatic scheme for multimedia traffic which consists of (i) cascaded leaky-buckets for traffic regulation, (ii) smoothers at the network edges, and (iii) bufferless statistical multiplexers within the network. For this scheme we show that loss probabilities are minimized with simple one-buffer smoothers which operate at specific minimum rates. We also show that the worst--case input traffic is extremal on--off traffic for all connections. These two results lead to a straightforward scheme for guaranteeing QoS to regulated traffic. We argue that the connection-carrying capacity of our scheme is significantly larger than schemes which use shared-buffer multiplexers in conjunction with reshapers. Using MPEG video traces, we present numerical results which demonstrate the methodology. This is a joint work with Martin Reisslein and Srini Rajagopal.

Equité et Qualité de service pour le transfert de flux de trafic élastique.
Laurent Massoulie (CNET)

L'équité (au sens ``max-min'') d'une allocation de débits à des flux traversant un réseau est une notion classique dans les réseaux de données; on cherche généralement à allouer les ressources de capacité de façon équitable afin de satisfaire au mieux chaque usager. F.P. Kelly a récemment introduit la notion alternative d'équité ``proportionnelle'', et a montré que le protocole TCP aurait plus tendance à réaliser un partage équitable en ce second sens plutôt qu'au sens max-min. On montrera de quelle manière un algorithme de contrôle par fenêtres fixes est naturellement associé à l'une ou l'autre de ces notions d'équité, selon que la politique de service à chaque file est FIFO ou Fair Queueing. On présentera un algorithme stochastique, de type Métropolis, permettant la réalisation approchée de tel ou tel partage équitable des capacités. On s'intéressera ensuite à la performance en termes de temps moyen de transfert de messages associée au critère max-min ou au critère proportionnel, sous l'hypothèse qu'un protocole idéal réalise instantanément une allocation équitable de débits aux messages en cours.
Contact: Zhen Liu
Last modified: Wed Apr 1 09:55:30 MET DST