Catene di Markov e sistemi di code

Questo elaborato vuole esporre le basi teoriche di particolari processi stocastici chiamati catene di Markov e successivamente discutere la loro applicazione, tramite la teoria delle code, ai sistemi client/server. Un sistema client/server è composto da una struttura che eroga un determinato servizio e dagli utenti che arrivano per poterne usufruire, i quali attenderanno in coda se il server è già occupato. Per poter studiare e modellare un sistema sì fatto è necessario considerare diversi parametri, tra cui variabili aleatorie quali i tempi di arrivo dei clienti, di attesa in coda, di servizio. Per questo motivo inizieremo con la trattazione delle catene di Markov a tempo discreto: processi stocastici in cui, sapendo che la catena si trova in un particolare stato in un determinato istante di tempo, la probabilità di transizione verso un altro stato all’istante di tempo successivo è indipendente dai valori assunti negli istanti passati. Tale proprietà, detta markoviana, caratterizza anche le catene di Markov a tempo continuo e i processi di Poisson, che saranno centrali per la trattazione dei sistemi di code in quanto modellano gli arrivi degli utenti (e quindi anche i tempi tra un arrivo e il successivo) come una serie di eventi indipendenti. Ci soffermeremo in primis sui sistemi di code detti M/M/1, con tempi di interarrivo e servizio esponenziali (ovvero che godono della proprietà markoviana, detta anche “assenza di memoria”) e un solo server, per poi passare alla loro generalizzazione: sistemi con molteplici server o con processi generici di arrivo e servizio.