Calendar

Total Flow Analysis (TFA) is a method for conducting the worst-case analysis of time sensitive networks without cyclic dependencies. In networks with cyclic dependencies, Fixed-Point TFA introduces artificial cuts, analyses the resulting cycle-free network with TFA, and iterates. If it converges, it does provide valid performance bounds. We show that the choice of the specific cuts used by Fixed-Point TFA does not affect its convergence nor the obtained performance bounds, and that it can be replaced by an alternative algorithm that does not use any cut at all, while still applying to cyclic dependencies.

Room: 206

Solutions of Poisson's equation for first-policy improvement in parallel queueing systems

This talk addresses the problem of (state-aware) job dispatching at minimum long-run average cost in a parallel queueing system with Poisson arrivals. Policy iteration is a technique for approaching optimality through improvement of an initial dispatching policy. Its implementation rests on the computation of value functions. In this context, we will consider the M/G/1-FCFS queue endowed with an arbitrary cost function for the waiting times of the incoming jobs. The associated relative value function is a solution of Poisson's equation for Markov chains, which I propose to solve in the Laplace transform domain by considering an ancillary stochastic process extended to (imaginary) negative backlog states. This construction enables us to issue closed-form solutions for simple cost functions (polynomial, exponential, and their piecewise compositions), in turn permitting the derivation of interval bounds for the relative value functions to more general cost functions. Such bounds allow for an exact implementation of the first improvement step of policy iteration in a parallel queueing system.

One objective of the talk is to identify the main obstacles to the implementation of the policy iteration algorithm in parallel queueing systems; the purpose then to discuss the new directions that transform domain analysis might offer beyond first policy improvement.

Further reading: Olivier Bilenne. Dispatching to parallel servers: solutions of Poisson's equation for first-policy improvement. Queueing Systems, Springer Verlag, 2021, Queueing Systems, 99 (3), pp.199-230. https://hal.archives-ouvertes.fr/hal-02925284