EP3340 Stokastiska modeller och köteori 9,0 hp

Stochastic Models and the Theory of Queues

Kursen behandlar grunderna i stokastisk modellering och köteori, inklusive fördjupad diskussion av grundläggande teoretisk resultater och med fokus på tillämpning inom området för kommunikationsnät. Kursen riktar sig till doktorander med forskning inom ICT området, som hade inga master nivå kurser i detta ämne.

 Kursen följer föreläsningar och övningar för EP2200, med ytterligare seminarier, hemuppgifter och små projekt, avsedda för doktorander.

  • Utbildningsnivå

    Forskarnivå
  • Huvudområde

  • Betygsskala

    P, F

Kurstillfällen/kursomgångar

VT19 för programstuderande

  • Perioder

    VT19 P3 (9,0 hp)

  • Anmälningskod

    61173

  • Kursen startar

    2019-01-15

  • Kursen slutar

    2019-03-15

  • Undervisningsspråk

    Engelska

  • Studielokalisering

    KTH Campus

  • Undervisningstid

    Dagtid

  • Undervisningsform

    Normal

  • Antal platser

    Ingen begränsning

Information för forskarstuderande om när kursen ges

oftast går P3.

Lärandemål

Efter kursen ska studenterna kunna:

  • Diskutera och tillämpa teorin av Markov-processer i diskret och kontinuerlig tid för att beskriva komplexa stokastiska system. Derivera de viktigaste satser som behandlar Markov-processer i transient och steady tillstånd.
  • Diskutera, ta fram och tillämpa teorin om Markovian och enklare icke-Markovian kösystem och nätverk. Använd genererande funktioner för att analysera system med stor eller komplicerad tillståndsdiagram. Härled analytiska modeller av icke-Markovisk kösystem med användning av inbäddade Markovkedjor.
  • Ta fram viktigaste teoretiska resultat för modellering av nätverk av köer. Diskutera beräknings frågor och lösningsmetoder.
  • Analysera kommunikation, kommunikationsnät och nätverksbaserade styrproblem med verktyg för Markov-processer och kömodeller.
  •  Diskutera senaste resultaten av teletrafikteori i relation till nätverksforskning.
  • Ta fram nya teoretiska resultat med tillämpning av eget forskningsområde.

Kursens huvudsakliga innehåll

Grundläggande material, täckt tillsammans med masterstudenter:

1.      Stochastic processer överblick. Stationära och ergodiska processer. Poissonprocessen och exponentiella interarrival tider. Minnesfri distributioner. De viktigaste egenskaperna för Poisson processen.

2.      Markov process, Markovkedjor och Markovian egenskap. Kortfattad diskussion av de tid-diskreta Markovkedjor. Detaljerad diskussion av tid-kontinuerlig Markovkedjor. Hålltider i tid-kontinuerlig Markovkedjor. Övergående och stationärt tillstånd fördelning.

3.      Använda Markovkedjor för att modellera och analysera stokastiska system. Konstruktion av abstrakta modeller och numeriska exempel.

4.      Ren födelse, ren dödsprocess och relation till Poissonprocessen. Födelsen-dödsprocess. Markov-kedjor och kösystem.

5.      Markovian kösystem med enkla och multipla servrar, obegränsad, begränsad lagringskapacitet, och obegränsad, begränsad population. Härledning av analytiska uttryck för genomsnittliga prestationsmått och väntetid distributioner.

6.      Mot icke-Markovian kösystem: icke-Exponentiella servicetider med i serie- och parallellkopplade servrar, genomsnittlig prestanda i steady state.

7.      Analys av Markovian kösystem som är uvidningar av de grundläggande system som omfattas i klassen. Använda Markovian kösystem för att modellera kommunikationsrelaterade problem. Konstruktion av abstrakta modeller och numeriska exempel.

8.      Icke-Markovian kösystem: köer med allmän servicetids-fördelning. Härledning av analytiska uttryck för medelprestandamått (Pollaczek-Khinchin mean formler). Användning av transient former (Pollaczek-Khinchin transient ekvationer). Prioriteringar och service med semester.

9.      Problem inklusive icke-exponentiell servicetids-fördelning. Modell konstruktion och numeriska exempel.

10.  Könät. Öppna och slutna könät. Detaljerad analys av öppna könät. Förekomsten av produktform lösning, och dess motivering.

11.  Konstruktion av könät modeller och numeriska exempel på nätverksrelaterade problem.

Avancerat material, som endast omfattas av doktorander:

A1.Poisson Process: ekvivalenta definitioner av Poissonprocessen, byggandet av en Poisson-process, förhållande till geometrisk fördelning och Uniform fördelning. Heterogen process och högre dimensioner. Användning av Poissonprocessen i forskningslitteraturen.
Analys av både diskret och kontinuerlig tid MCs i transient tillstånd. Ergodicitet och stabilitet, bevis på villkoren för dessa. Tillstånd aggregering i stora Markovkedjor.

A2.Användning av genererande funktioner för att härleda stationära egenskaper. Från M / M / 1 till M / E_r / 1 till phase-type servicetid distributioner.

A3.Icke Markovian kösystem, förnyelse teori, inbäddade Markovkedjor. Härledningen av Pollaczek-Khinchin transient ekvationer med hjälp av inbyggda Markovkedjor. Exempel på liknande härledningar från nätverkslitteraturen.

A4.Könät: bevis på förekomsten av produktform lösningen. Lösningmetoder för slutna könät. Begränsningarna av  könet modeller.

A5.Outlook: Palm kalkylen, Large Deviation Theory, senaste trenderna inom stokastisk modellering.
Små projekt: teletrafikteori modellformulering (och om möjligt, lösning av modell) av ett problem nära relaterat till doktorandens forskning.

Kursupplägg

Föreläsningar, övningar, seminarier med studentpresentation, hemuppgifter, mindre projekt och tentamen.

Behörighet

Rekommenderade förkunskaper

Matematisk statistik; sannonlikhetstheori, stochastiska processer

Litteratur

D. Gross and C. M. Harris, Fundamentals of Queueing Theory, Wiley

Original publikationer av några klassiska ämnen.

Examination

  • EXA1 - Examination, 9,0, betygsskala: P, F

Krav för slutbetyg

Aktivt deltagande på seminarier

30 min presentation på ett av seminarierna

80% på hemuppgifter

Godkänt projekt med anknytning till den egna forskningen

70% på tentamen

Ges av

EECS/Nätverk och systemteknik

Kontaktperson

Viktoria Fodor

Examinator

Viktoria Fodor <vjfodor@kth.se>

Övrig information

Del av kursen ges tilsammans med EP2200.

Påbyggnad

EP3210

Versionsinformation

Kursplan gäller från och med VT2019.
Examinationsinformation gäller från och med VT2019.