Yn ddiweddar fe ges i fy mhapur academaidd cyntaf ei dderbyn ar gyfer cyhoeddiad, wedi’i ysgrifennu gyda fy ngoruchwylwyr PhD Prof. Paul Harper a Dr. Vincent Knight. Enw’r papur yw “Modelling Deadlock in Open Restricted Queueing Networks”, wedi’i gyhoeddi yn y cyfnodolyn European Journal of Operational Research.

Yn y papur yma rydym yn archwilio ffenomenon yn rhwydweithiau ciwio sydd heb cael llawer o sylw o’r blaen: llwyrglo. Yn gyntaf edrychwn ni ar efelychiadau cyfrifiadurol, a chyflwynwn ni dull o canfod pryd mae llwyrglo yn digwydd. Yna, gan gymryd mantais o’r dull yma, a trwy adeiladu modelau analytig o rhwydweithiau ciwio sy’n llwyrglo, rydym yn archwilio i mewn i beth sy’n effeithio ar yr amser nes cyrraedd llwyrglo.

Beth yw llwyrglo?

Mae’r llun o ‘gridlock’ isod yn drosiad gwych ar gyfer llwyrglo: mae’r ceir coch wedi’i flocio rhag parhau ar ei daith gan y ceir glas, mae’r ceir glas wedi’i flocio gan y ceir melyn, sydd wedi’i flocio gan y ceir gwyrdd, sydd wedi’i flocio gan y ceir coch. Mae’r ceir coch yn blocio eu hun!

Cysyniad sy’n ategu rhwydweithiau ciwio cyfyngedig yw blocio. Dyma le cwsmeriaid yn trio ymuno â nod arall ar ôl gorffen gwasanaeth, ond methu oherwydd bod y ciw yna yn llawn. Nawr mae angen iddynt aros gyda’i gweinydd (sydd methu gweini unrhyw gwsmer arall yn y cyfamser) nes bydd lle yn dod ar gael yn y gyrchfan bwriedig.

Mae’r rheolau blocio yma yn arwain at sefyllfa (a ddarluniwyd uchod) lle all fod dau neu mwy o gwsmeriaid yn blocio’i gilydd, ac yn aros i’r cwsmer arall symud cyn iddynt allu symud ei hunain. Mae’r cwsmeriaid yma yn blocio’i hun.

Mae’r sefyllfa yma yn rhewi’r system.

Canfod llwyrglo

Mae gadael efelychiadau ciwio i gyrraedd llwyrglo yn broblem. Heb y gallu i ganfod pryd mae llwyrglo yn digwydd mewn efelychiadau ciwio, fe all bod rhan fawr o’r amser efelychu heb ddigwyddiadau o gwbl, ac felly’n sgiwio’r mesuriadau perfformiad. Heb y gallu i ganfod pryd mae llwyrglo yn digwydd mewn efelychiadau ciwio, ni all gweithredu mecanweithiau i adfer y llwyrgloeon a ddigwyddiff mewn realiti.

Cyflwynwn ni canlyniad theori graff sy’n nodi pryd mae llwyrglo yn digwydd, gan diffinio digraff cyflwr \(D(t) = (V, E(t))\):

  • Mae’r set o fertigau \(V\) yn cyfateb a’r set o weinyddion y rhwydwaith ciwio.
  • Mae’r set o ymylon \(E(t)\) yn cyfateb a’r set o holl berthnasoedd blocio: Os yw cwsmer wrth y \(k^{\text{fed}}\) gweinydd y nod \(i\) wedi’i flocio rhag mynd i nod \(j\), yna mae yna ymyl cyfeiriedig o’r fertig sy’n cyfateb â \(k^{\text{fed}}\) gweinydd y nod \(i\) i bob fertig sy’n cyfateb a gweinyddion y nod \(j\).

Er enghraifft:

Nawr mae llwyrglo yn digwydd os ac yn unig os yw \(D(t)\) yn cynnwys cwlwm (set o fertigau ni all eu dianc). Yn yr enghraifft isod mae’r cwlwm a’r gweinyddion sydd ynghlwm y llwyrglo wedi’i uwcholeuo’n goch.

Fe fanteisiwyd ar y canlyniad yma fel mecanwaith canfod llwyrglo y llyfrgell Ciw, llyfrgell Python a chafodd ei datblygu a’i ddefnyddio yn y prosiect yma i efelychu rhwydweithiau ciwio.

Effeithiau ar yr amser nes cyrraedd llwyrglo

Gan ddefnyddio’r llyfrgell Ciw fe all recordio’r amser nes cyrraedd llwyrglo o system wag. Gan adeiladu modelau cadwynau Markov o rwydweithiau ciwio syml sy’n llwyrglo, fe all amcangyfrif yr amser disgwyliedig nes cyrraedd llwyrglo o system wag. Rhedon ni nifer o senarios i archwilio ar effaith newid rhai paramedrau’r rhwydwaith ar yr amser nes cyrraedd llwyrglo. Yn gryno:

  • Mae cynyddu cyfradd dyfodi’r system yn cynyddu’r amser i lwyrglo (mae cwsmeriaid yn cyrraedd yn gyflymach, felly mae’r ciw yn llenwi’n gyflymach).
  • Mae cynyddu’r cynhwysedd ciwio yn lleihau’r amser i lwyrglo (gall mwy o cwsmeriaid cyrraedd cyn i’r cynhwysedd llenwi).
  • Mae cynyddu’r nifer o weinyddion yn lleihau’r amser i lwyrglo (yn debyg i’r cynhwysedd ciwio, ond gydag effaith mwy).
  • Mae cynyddu’r tebygolrwyddau trosglwyddo yn cynyddu’r amser i lwyrglo (mae cwsmeriaid yn llai tebygol o adael y system, ac felly’n fwy tebygol o gael eu blocio).

Daeth yr effaith mwyaf diddorol trwy newid y gyfradd gwasanaeth \(\mu\). Fe wnaeth hwn cynhyrchu’r graff bowl a gweler isod.

Mae’n debyg bod yna rhyw drothwy cyfradd gwasanaeth \(\hat{\mu}\) sy’n cynhyrchu’r amser lleiaf i lwyrglo. Er bod hwn yn syndod ar y dechrau, mae hwn yn gwneud synnwyr, gan fod gwasanaethau yn effeithio ar gwsmeriaid yn ail-ymuno a’r ciw a chwsmeriaid yn gadael y system, sy’n cael effeithiau cyferbyn ar yr amser i lwyrglo:

  • Wrth i \(\mu \rightarrow 0\), mae’r amser gwasanaeth cymedrig yn tueddu i \(\infty\). Ni all llwyrglo digwydd oherwydd nad yw cwsmeriaid yn gallu gadael gwasanaeth i’w cael eu blocio, felly mae’r amser nes cyrraedd llwyrglo yn tueddu i \(\infty\).
  • Os yw \(\mu < \hat{\mu}\), yna mae’r cyfradd dyfodi yn gymharol fawr o cymharu a’r gyfradd gwasanaeth, felly mae’r system mwy na thebyg yn llawn. Fan hyn mae cynyddu’r gyfradd gwasanaeth yn cynyddu’r siawns bod cwsmer eisiau ail-ymuno a’r ciw, ac felly llwyrglo. Felly mae’r amser i lwyrglo yn lleihau wrth i \(\mu\) cynyddu.
  • Os yw \(\mu > \hat{\mu}\), yna mae’r gyfradd gwasanaeth digon mawr bod y system mwy na thebyg ddim yn llawn. Nawr mae cynyddu’r gyfradd gwasanaeth yn cynyddu’r siawns o gwsmer gadael y system, yn lleihau’r siawns bod cwsmer yn cael ei flocio (gan fod llai i cwsmeriaid yn y ciw). Felly mae’r amser nes cyrraedd llwyrglo yn cynyddu wrth i \(\mu\) cynyddu.
  • Wrth i \(\mu \rightarrow \infty\) mae’r amser gwasanaeth cymedrig yn tueddu i \(0\). Ni all ciw ddechrau gan fod neb yn treulio unrhyw amser mewn gwasanaeth, felly does dim cwsmeriaid yn cael eu blocio, ac mae’r amser i lwyrglo yn tueddu i \(\infty\).

Gair olaf

Hwn oedd fy mhrosiect ymchwil go iawn cyntaf i mi weithio arno, ac fe fwynheais i lot. Roeddwn yn enwedig yn hoff o sut daeth y broblem i ni yn y lle cyntaf: tra’n trio gweithredu mecanwaith blocio rhwydweithiau ciwio cyfyngedig yn ein meddalwedd efelychu ciwio (rhagflaenydd i Ciw), fe wnaeth ein cyfres o brofion awtomatig cadw methu.

Yn amlwg am gyfnod credon ni taw bugs yn ein cod oedd ar fai. Yna yn edrych bach yn agosach ar y profion, sylweddolon ni ein problem, roedd y paramedrau a dewision yn achosi’r efelychiad i fwrw llwyrglo (cysyniad nad oeddwn i wedi dod ar draws ar y pryd), ac felly’n sgiwio ein mesuriadau perfformiad. Fe arweiniodd hwn i brosiect ymchwil diddorol a ffrwythlon!