Differential equations arrising in network problems

Add to your list(s) Download to your calendar using vCal

• N Vvedenskaya (Institute for Information Transmission Problems, Moscow)
• Wednesday 21 November 2007, 15:30-16:30
• MR4, CMS, Wilberforce Road, Cambridge, CB3 0WB.

If you have a question about this talk, please contact Speaker to be confirmed.

The talk focuses on large queueing systems and networks, with dependent queues. In particular, we are interested in the large-time performance and stationary distribution of such networks. Such problems are often rather complicated, and one of the ways to study them is via an asymptopical approach. In case where the network is guided by a Markov process and the number of its nodes $N$ is very large, the limiting situation, as $N\to \infty$, may be described by a system of differential equations. The solution to such asystem gives an accurate assessment of the network performance. I will present several examples where this aproach turnes to be successful. First, we consider fast Jackson networks with dynamic routing, then a random multiple access system with ALOHA -like protocol. The simplest system with dynamic routing was a system considered by Dobrushin, Karpelevich and Vvedenskaya (and independently, Mitzenmacher): it contains $N$ identical servers with IID exponential service times and a Poisson flow of tasks. Upon its arrival, each task randomly selects $m$ servers and is directed to the one with a shorter queue. The limiting situation is described by a rather simple (infinite) system of ODEs, with a unique globally attracting fixed point. The probability of long queus in the limiting system decreases superexponentially. Numerical simulations show that in the system with finite $N$ the queue length distribution is close to the limiting one. Later, Martin—Suhov and Suhov—Vvedenskaya considered open Jackson-type networks where each node contains $N$ identical servers and a task selects several servers (from one several nodes) and is directed to the one with a shorter queue.

Finally, in a random multiple access system with $N$ users and ALOHA -like protocol, each user tries to transmit its maessage with a friquency determined by its back-off stage (the stage is changed after each transmission atempt.) As $N\to \infty$, the system performance is described by a solution to a system of ODE with one or seevral fixed points. In case of several solutions the original system is treated as ‘metastable’.

This talk is part of the Optimization and Incentives Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge talks
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Economics and Computer Science Talks
• Hanchen DaDaDash
• Interested Talks
• MR4, CMS, Wilberforce Road, Cambridge, CB3 0WB
• Optimization and Incentives Seminar
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.