VALUETOOLS 2008
TECHNICAL PROGRAM
VALUETOOLS AND ADJUNCT WORKSHOPS
|
MONDAY, 20 OCT. |
(Game Theory in Communication Networks) |
(Structured Markov Chains) |
|
TUESDAY, 21 OCT. |
TRACK 1 |
TRACK 2 |
|
WEDNESDAY, 22 OCT. |
TRACK 1 |
TRACK 2 |
|
THURSDAY, 23 OCT. |
|
(International Workshop on NS2) |
|
FRIDAY, 24 OCT. |
(Modeling and Design of Wireless Mesh Networks) |
(Interdisciplinary Systems Approach in Performance
Evaluation and Design of Computer & Communication Systems) |
VALUETOOLS PROGRAM AT A GLANCE
TUESDAY, 21 OCTOBER
|
9:00-10:00 |
Plenary Talk Jean Mairesse,
“Random Walks on Algebraic Structures and Discrete Event Systems” |
|
|
10:00-10:30 |
Coffee Break |
|
|
10:30-12:30 |
Session 1 Wireless Networks
I |
Session 2 Simulation |
|
12:30-14:00 |
Lunch |
|
|
14:00-16:00 |
Session 3 Wireless Networks
II |
Session 4
(Invited) Stochastic Models
in Physics I |
|
16:00-16:30 |
Coffee Break |
|
|
16:30-18:30 |
Session 5 Media Access |
Session 6 Polling |
WEDNESDAY, 22 OCTOBER
|
9:00-10:00 |
Plenary Talk John Tsitsiklis,
“Gossiping, Herding, Flocking, and Consensus” |
|
|
10:00-10:30 |
Coffee Break |
|
|
10:30-12:30 |
Session 7
(Invited) Stochastic Models
in Physics II |
Session 8 Queueing I |
|
12:30-14:00 |
Lunch |
|
|
14:00-15:00 |
Plenary Talk Aris Moustakas : (Title in expectation) |
|
|
15:00-15:30 |
Coffee Break |
|
|
15:30-17:30 |
Session 9 Sporadic Paper
Group |
Session 10
(Invited) Asymptotic
Methods in Queueing |
|
17:30-18:00 |
Coffee Break |
|
|
20:00- |
Banquet |
|
THURSDAY, 23 OCTOBER
|
9:00-10:00 |
Plenary Talk Avishai
Mandelbaum, “QED Queues: Quality and |
|
|
10:00-10:30 |
Coffee Break |
|
|
10:30-12:30 |
Session 11
(Invited) Recent Trends in
Markov Decision Processes |
|
|
12:30-13:30 |
Lunch |
|
|
13:30-15:30 |
Session 12 Queueing II |
WNS2 Tutorial (part I) (open to Valuetools participants) |
|
15:30-16:00 |
Coffee Break |
|
|
16:00-18:30 |
WNS2 Tutorial (part II) (open to Valuetools participants) |
|
SESSION 1:
WIRELESS NETWORKS I
Session Chair: Urtzi Ayesta (CNRS, France)
Time: Tuesday, 10:30-12:30
Access Network Design with
Capacity-dependent Costs
Olivier Brun, Anouar
Rachdi, and Jean-Marie Garcia (LAAS-CNRS, France)
An Efficient Analytical Method for
Dimensioning of CDMA Cellular Networks Serving Streaming Calls
Bartek Blaszczyszyn (INRIA,
Ecole Normal
Optimal Robust Policies for
Bandwidth Allocation and Admission Control in Wireless Networks
Vicent Pla (Univ.
Performance Evaluation of
Distance-Hop Proportionality on Geometric Graph Models of Dense Sensor Networks
Swaprava Nath and Anurag
Kumar (Indian
SESSION 2: SIMULATION
Session Chair: Jean Mairesse (CNRS, France)
Time: Tuesday, 10:30-12:30
Perfect Simulation and Non-monotone
Markovian Systems
Ana Busic (INRIA,
France), Bruno Gaujal (INRIA, France), and Jean-Marc Vincent (Université Joseph Fourier, France)
Control Variates as Screening
Functions
Sofia Kyriazopoulou-Panagiotopoulou (Athens University of Economics and Business, Greece), Ioannis Kontoyiannis (Athens University of Economics and
Business, Greece) and Sean Meyn (University of Illinois at Urbana-Champaign,
USA)
Oja's Algorithm for Graph Clustering
and Markov Spectral Decomposition
Vivek Borkar (Tata Institute of
Fundamental
Cross-Entropy Based Data Association
for Multi Target Tracking
Daniel Sigalov and Nahum
Shimkin (
SESSION 3:
WIRELESS NETWORKS II
Session Chair: Vicent Pla (Universidad
Time: Tuesday, 14:00-16:00
Performance Evaluation and Trade-offs
of Optimal Backoff Misbehavior Detection Schemes in Wireless Networks in the
Presence of Interference
Svetlana Radosavac and John
S. Baras (
Analytical Evaluation of Various
Frequency Reuse Schemes in Cellular OFDMA Networks
Philippe Godlewski, Masood
Maqbool, Marceau Coupechoux (TELECOM ParisTech & CNRS LTCI, France),
and Jean-Marc Kélif (
Fair Resources Allocation in
Wireless Networks in the Presence of a Jammer
Eitan Altman, Konstantin
Avrachenkov (INRIA
Comparison of Bandwidth-sharing
Policies in a Linear Network
Maaike Verloop (CWI,
The
SESSION 4: STOCHASTIC
MODELS IN PHYSICS I (INVITED SESSION)
Session Chair: Joseph Klafter (
Time: Tuesday, 14:00-16:00
First-passage Times in Confined Geometry (*)
Olivier
Bénichou (University
Pierre et Marie Curie, France) (joint work with Sylvain Condamin, Vincent
Tejedor, Raphaël Voituriez, and Joseph Klafter)
Lorenzian Analysis of Infinite Poissonian Populations and the Phenomena
of Paretian Ubiquity (*)
Iddo
Eliazar (Holon Institute of
Proteins: Coexistence of Stability and Flexibility (*)
Shlomi
Reuveni (
From Solar Flare Time Series to Fractional Dynamics (*)
Krzysztof
Burnecki and Aleksander
Weron (Wroklaw
SESSION 5: MEDIA
ACCESS
Session Chair: Stavros Toumpis (UCY,
Time: Tuesday, 16:30-18:30
IEEE802.16 Multi-class Capacity
including AMC scheme and QoS Differentiation for Initial and Bandwidth
Request Ranging
Thierry Peyre, Khalil
Ibrahimi, and Rachid El Azouzi (
Improved High Maximum Stable
Throughput FCFS Tree Algorithms with Interference Cancellation
Gino T. Peeters and Benny
Van Houdt (
SESSION 6: POLLING
Session Chair: Uri Yechiali (
Time: Tuesday, 16:30-18:30
Polling Systems with a
Gated/Exhaustive Discipline
Onno Boxma, A.C.C.
Van Wijk, and Ivo Adan (
End-to-end delays in Polling Tree Networks
Paul Beekhuizen (Philips
Research and Eurandom, The
A Two-Queue Polling Model with Two
Priority Levels in the First Queue
Marko Boon, Ivo Adan and Onno Boxma (
Analysis of a Polling System
Modeling QoS Differentiation in WLANs
Tom Coenen (
SESSION 7: STOCHASTIC
MODELS IN PHYSICS II (INVITED SESSION)
Session Chair: Aleksander Veron (
Time: Wednesday, 10:30-12:30
Nonergodicity Mimicking Inhomogeneity in Single Particle Tracking (*)
Igor Sokolov (Humboldt Universitat zu
Stochastic Representations of Anomalous Diffusion Processes - Subordination
Approach (*)
Marcin
Magdziarz (
Field-Induced Dispersion in Subdiffusion (*)
Joseph
Klafter (
Heavy Tailed Lévy Random Motions in Super- and Subharmonic
Potential Wells (*)
Alexei
Chechkin (Kharkov
Institute of Physics and
SESSION 8: QUEUEING
I
Session Chair: Konstantin Avrachenkov (INRIA,
France)
Time: Wednesday, 10:30-12:30
Stability of two Interfering
Processors with Load Balancing
Matthieu Jonckheere (
A Fast Algorithm for Optimal
Admission Control with Delay
Peter Jacko and José
Niño-Mora (Universidad Carlos
III
Optimal Scheduling of Jobs with a
DHR tail in the M/G/1 queue
Samuli Aalto (
A New Framework Supporting the
Bottleneck Analysis of Multiclass Queuing Networks
Jonatha Anselmi(
SESSION 9: SPORADIC
PAPER GROUP
Session Chair: Stavros Toumpis (UCY,
Time: Wednesday, 15:30-17:30
Distributed Resource Allocation
Algorithms for Peer-to-peer Networks
Response Time Distribution of Flash
Memory Accesses
Peter Harrison (
Fluid Semantics for Passive
Stochastic Process Algebra Cooperation
Richard Hayden and
Jeremy Bradley (
Non Deterministic Repairable Fault
Trees for Computing Optimal Repair Strategy Marco
Beccuti, Daniele Codetta-Raiteri,
Giuliana Franceschinis (Università del Piemonte Orientale,
Italy), and Serge Haddad (ENS Cachan, France).
SESSION 10: RECENT
ASYMPTOTIC METHODS IN QUEUEING (INVITED SESSION)
Session Chair: Rami Atar, Adam Schwartz (
Time: Wednesday, 15:30-17:30
A Diffusion Regime with
Nondegenerate Slowdown (*)
Rami Atar (
Asymptotic Optimality
of the cì/è Priority Rule
Rami Atar, Chanit Giat,
Nahum Shimkin (
Bounds and
Moments for Stationary Delay in GI/GI/s Queue (*)
Dmitry Korshunov (
Large Deviation
Properties of Constant Rate Data Streams Sharing a Buffer with Variable Rate
Cross Traffic
Kurt Majewski (Siemens AG,
SESSION 11: RECENT
TRENDS IN MARKOV DECISION PROCESSES (INVITED SESSION)
Session Chair: Nachum Shimkin (
Time: Thursday, 10:30-12:30
An Index Policy
for Multiarmed Multimode Restless Bandits
José Niño-Mora
(Universidad
Carlos III
Markov Decision
Evolutionary Games with Time Average Expected Fitness Criterion
Eitan Altman (INRIA, France), Yezekael Hayel (
Eventually
Stationary Policies for Markov Decision Models with non Constant Discounting
Yair Carmon and Adam Shwartz (
Efficient Reinforcement
Learning in Parameterized Models: Discrete Parameters (*)
Kirill Dyagilev (
SESSION 12: QUEUEING
II
Session Chair: Tijani Chahed (INT, France)
Time: Thursday, 14:00-16:00
Class Treatment in Queuing Systems:
Discrimination and Fairness Aspects
David Raz (Holon
Institute of
Positive Harris Recurrence and
Diffusion Scale Analysis of a Push Pull Queueing Network
Yoni Nazarathy and Gideon Weiss (
Estimating the Worst-case Delay in
FIFO Tandems Using Network Calculus
Luca Bisti, Luciano
Lenzini, Enzo Mingozzi, and Giovanni Stea (
Computation of a (min,+)
Multi-dimensional Convolution for end-to-end Performance analysis
Anne Bouillard (ENS
Cachan/IRISA, France), Laurent
Jouhet (ENS Lyon/IXXI, France),
and Eric Thierry (LIAFA&ENS Lyon/IXXI, France)
Asterisks in invited sessions (*) mean the talk
is not accompanied by a paper in the proceedings. Abstracts can be found below
ABSTRACTS OF INVITED TALKS
(Not accompanied by papers)
SESSION 4:
STOCHASTIC MODELS IN PHYSICS I (INVITED
SESSION)
Session Chair: Joseph Klafter (
Time: Tuesday, 14:00-16:00
First-passage times in confined geometry
Olivier
Bénichou (University
Pierre et Marie Curie, France) (joint work with Sylvain Condamin, Vincent
Tejedor, Raphaël Voituriez, and Joseph Klafter)
How
long does it take a random walker to reach a given target point? This quantity,
known as a first passage time (FPT), has led to a growing number of theoretical
investigations over the last decade. The importance of FPTs originates from the
crucial role played by first encounter properties in various real situations,
including transport in disordered media, spreading of diseases or target search
processes. Most methods to determine the FPT properties in confining domains
have been limited to effective 1D geometries, or for space dimensions larger
than one only to homogeneous media. I will propose here a general theory which
allows one to evaluate the mean FPT (MFPT) in complex media. This analytical
approach provides a universal scaling dependence of the MFPT on both the volume
of the confining domain and the source-target distance. This analysis is
applicable to representative models of transport in disordered media, fractals,
and anomalous diffusion.
Lorenzian analysis of infinite Poissonian populations and the phenomena
of Paretian ubiquity
Iddo
Eliazar (Holon
Institute of
The
Lorenz curve is a universally-calibrated statistical tool measuring
quantitatively the distribution of wealth within human populations. We consider
infinite random populations modeled by inhomogeneous Poisson processes defined
on the positive half-line – the randomly scattered process-points representing
the wealth of the population-members (or any other positive-valued measure of
interest such as size, mass, energy, etc.). For these populations the notion of
"macroscopic Lorenz curve" is defined and analyzed, and the notion of
"Lorenzian fractality" is defined and characterized. We show that the
only non-degenerate macroscopically observable Lorenz curves are power-laws
manifesting Paretian statistics – thus providing a universal "Lorenzian
explanation" to the ubiquitous appearance of Paretian probability laws in
nature.
Proteins: Coexistence of stability and flexibility
Shlomi
Reuveni (
We
introduce an equation for protein native topology based on recent analysis of
data from the Protein Data Bank and on a generalization of the Landau-Peierls
instability criterion for fractals. The equation relates the protein fractal
dimension df, the spectral dimension ds, and the number of amino acids N.
Deviations from the equation may render a protein unfolded. The fractal nature
of proteins is shown to bridge their seemingly conflicting properties of
stability and flexibility. Over 500 proteins have been analyzed (df, ds and N)
and found to obey this equation of state.
From solar flare time series to fractional dynamics (*)
Krzysztof
Burnecki and Aleksander
Weron (Wroklaw
We
demonstrate that continuous-time FARIMA processes with alpha-stable noise
provide a new stochastic tool for studying the solar flare phenomenon in the
framework of fractional Langevin equation. Simple computer tests to check the
origins of alpha-stability and self-similarity are implemented for empirical
time series describing the energy of solar flares. Based on observed physical
time series we solve the challenging problem of how to detect long-range
dependence from real data and how to model it via fractional dynamics (Langevin
or Fokker–Planck). We employ here codifference as a proper measure for
long-range dependence. It is applicable to empirical data from the distribution
lacking the second moment.
SESSION 7:
STOCHASTIC MODELS IN PHYSICS II (INVITED
SESSION)
Session Chair: Aleksander Veron (
Time: Wednesday, 10:30-12:30
Nonergodicity mimicking inhomogeneity in single particle tracking (*)
Igor Sokolov (Humboldt Universitat zu
Most
statistical theories of anomalous diffusion rely on ensemble-averaged
quantities such as the mean squared displacement. Recent single molecule
tracking measurements require, however, temporal averaging. We contrast the two
approaches in the case of continuous-time random walks with an asymptotic power
law distribution of waiting times lacking the mean. We show, that contrary to
what is expected, the mean squared displacement obtained as a moving temporal
average along the single trajectory, exhibits a simple diffusive behavior with
diffusion coefficients which strongly differ from one trajectory to another.
This finding mimics the inhomogeneous behavior as in an ensemble of random
walkers with different diffusion coefficients. The information about the
anomaly can be restored by an additional ensemble average over these diffusion
coefficients, which results in an effective diffusion-coefficient which depends
on the length of the trajectory T and on the exponent of the waiting time
distribution.
Stochastic representations of anomalous diffusion processes -
subordination
approach (*)
Marcin
Magdziarz (
We
introduce a subordination-based approach to modeling of anomalous diffusion
processes in time-dependent force fields. Using the concept of inverse
subordinators and the theory of Levy processes, we construct rigorously a
stochastic process, which corresponds to the fractional Fokker-Planck equation
with time-dependent force. Our model provides good physical insight through the
trajectories. Moreover, it allows to study different anomalous diffusion
processes both analytically and numerically.
Field-Induced dispersion in subdiffusion (*)
Joseph
Klafter (
We
discuss the response of continuous-time random walks to an oscillating external
field within the generalized master equation approach. We concentrate on the
time dependence of the two first moments of the walker’s displacement. We show
that for power-law waiting-time distributions with 0<á<1 corresponding to a semi-Markovian situation showing
nonstationarity, the mean particle position tends to a constant; namely, the
response to the external perturbation dies out. On the other hand, the
oscillating field leads to a new additional contribution to the dispersion of
the particle position, proportional to the square of its amplitude and growing
with time. These new effects, amenable to experimental observation, result
directly from the nonstationary property of the system.
Heavy tailed Lévy random motions in super- and subharmonic
potential wells (*)
Alexei
Chechkin (Kharkov
Institute of Physics and
The
Lévy motions (LMs) are random processes with stationary increments
having a long-tailed stable probability distribution with divergent variance.
As such, LMs are a natural generalization of the Brownian motion ensuing from
the generalized central limit theorem. Despite their broad field of
applications, LMs are far from being completely understood. Here, we consider
ordinary LMs, that is Markovian processes with independent increments, subjected
to an external non-linear potential force. The behavior is different for the
steep superharmonic potential wells with the index c > 2 and for the gently
sloping subharmonic ones, c < 2. For the superharmonic one-well potentials
we found that the stationary probability density function (PDF) features a
distinct bimodal shape and decays with the power-law tails which are steep
enough to give rise to a finite variance, in contrast to a “free” LM. During
the relaxation to stationarity the PDF exhibits unimodal-bimodal time
bifurcations. In anharmonic one-well potentials we observe unimodal-bimodal
bifurcations of the stationary PDF. For subharmonic one-well potentials the stationary solution does not exist if the
Lévy index is smaller than the index of the well.
For
the two-well potentials we found that the mean escape time is inversely
proportional to the intensity of the Lévy motion, in sharp contrast with
the known exponential behavior for the Brownian motion. Furthermore, we
consider the phenomenon of generating directed current by the LM in periodic
asymmetric potential and demonstrate how direction and magnitude of the current
can be manipulated by changing the asymmetry of the LM and the potential
asymmetry. These properties of the LMs are discussed on the basis of analytical
and numerical solutions of the corresponding stochastic nonlinear differential
equations as well as the kinetic equations with partial derivatives of
fractional order.
SESSION 10:
RECENT ASYMPTOTIC METHODS IN QUEUEING (INVITED SESSION)
Session Chair: Rami Atar, Adam Schwartz (
Time: Wednesday, 14:00-16:30
A diffusion
regime with nondegenerate slowdown (*)
Rami
Atar (
In both the conventional and the Halfin-Whitt heavy
traffic diffusion regimes, the slowdown (defined as the sojourn time/service
time ratio) experienced by a typical customer, degenerates in the limit, to
infinity and 1, respectively. In practice, however, it often occurs that delay
and service time are comparable. We study a diffusion regime in which delay and
service time are of the same order of magnitude. In a setting with many
heterogeneous, exponential servers, (possibly with abandonment), we find the
limiting joint law of these two processes.
Bounds and
Moments for Stationary Delay in GI/GI/s Queue (*)
Dmitry Korshunov (
Only a little is known about the tail properties of
the distribution of the stationary waiting time, or delay, in multi-server
queues with the FCFS service discipline, in the contrast with the
one-dimensional case. In the GI/G/1 queue, the ã-th moment of the stationary
delay is finite if and only if the (ã+1)-st moment of the service time
distribution is finite – this goes back to Kiefer and Wolfowitz. Under
subexponential-type conditions, the tail asymptotics for the stationary delay
are also known; they follow the tail of the distribution of the residual
service time. Recent results (W. Whitt, A. Scheller-Wolf and K. Sigman, A.
Scheller-Wolf and R. Vesilo, etc.) suggest that, in the multi-server queue, the
tail distribution of the stationary delay is not always as heavy as that of the
residual service time, and the conditions for the finiteness of the ã-th moment
differ from those in the single server queue. In our QUESTA paper (2006), we
studied the two-server queue GI/GI/2 and obtained sharp asymptotics for the
tail distribution of the stationary delay assuming the subexponentiality of the
distribution of the residual service time. In particular, these asymptotics
differ for different regions of the traffic load ñ. Now we present upper and
lower bounds for the distribution tail of the stationary delay in the GI/GI/s
queue, for any s ≥2. The derivation of these bounds requires new ideas and
techniques. In particular, in the case of (intermediate) regularly varying
service times these bounds are exact up to a constant. These bounds again
depend on the traffic load. They also allow obtaining conditions for the
existence of power moments, which are both necessary and sufficient.
SESSION 11:
RECENT TRENDS IN MARKOV DECISION PROCESSES (INVITED SESSION)
Session Chair: Nachum Shimkin (
Time: Thursday, 10:30-12:30
Efficient
Reinforcement Learning in Parameterized Models: Discrete Parameters (*)
Kirill
Dyagilev, Shie Mannor, and Nahum Shimkin (
We consider reinforcement learning in a parameterized
setup, where the controlled model is known to belong to a finite set of Markov
Decision Processes (MDPs) under the discounted return criteria. We propose an
on-line algorithm for learning in such parameterized models, called the
Parameter Elimination (PEL) algorithm, and analyze its performance in terms of
the the total mistake bound criterion, which upper-bounds the total number of
suboptimal actions performed by the algorithm over the infinite time horizon.
The proposed algorithm relies on Wald’s Sequential Probability Ratio Test to
eliminate unlikely parameters, and uses an optimistic policy for effective
exploration. We establish that, with high probability, the total mistake bound
for the algorithm is linear (up to a logarithmic term) in the cardinality |È|
of the parameter set, independently of the cardinality of the state and action
spaces. We further demonstrate that much better dependence |È| may be obtained
for this algorithm, depending on the specific information structure of the
problem.