VALUETOOLS 2008
PRELIMINARY 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 Sergiu Hart, “Dynamics,
Heuristics, and Equilibria: A Game-Theoretic Perspective” |
|
|
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 and Paolo
Cremonesi (
SESSION 9: SPORADIC
PAPER GROUP
Session Chair: Stavros Toumpis (UCY,
Time: Wednesday, 14:00-16: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, 14:00-16:30
A Diffusion Regime with Nondegenerate Slowdown (*)
Rami Atar (
Asymptotic Optimality
of the cì/è Priority Rule
Rami Atar, Chanit Giat, Nahum Shimkin (
Martin Boundary with Large Deviation
Technique for Partially Homogeneous Random Walks (*)
Irina Ignatiouk (
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.
Martin
boundary with large deviation technique for partially homogeneous random walks (*)
Irina
Ignatiouk (
To identify the Martin boundary for a transient Markov
chain having Green's function G(x; y) one have to identify all
possible limits lim_{n
-> \infty} G(x; yn)=G(x0;
yn) with yn
“tending to infinity”. For homogeneous random walks, these limits are
usually obtained from the exact asymptotics of the Green's function G(x;
y). For non-homogeneous random walks, the exact asymptotics of the Green's
function is an extremely difficult problem. We discuss several examples of
partially homogeneous random walks, where Martin boundary can be identified by
using large deviation technique. The minimal Martin boundary is in general not
connected and does not coincide with the full Martin boundary. The full Martin
compactification is in general not homeomorphic to the “radial”
compactification obtained by Ney and Spitzer for the homogeneous random walks
in Zd: convergence of a sequence of points yn to a point on the Martin
boundary does not imply convergence of the sequence yn/|
yn| on the unit sphere.
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.