Ilara-teoria

Ilara-teoria sistema baten itxarote egoerak edo ilarak matematikoki aztertzen dituen arlo aplikatu bat da. Teoria honek hainbat faktore ikertzen ditu: ilaran dauden batezbesteko erabiltzaile kopurua eta batezbesteko itxarotea, ilara blokeatzeko probabilitatea...Sektore askotan aplikatu ahal den modelo bat da (merkataritza, industria, ingeniaritza, telekomunikazioak...). Ilarak eguneroko bizitzan aurki ditzakegu: banketxean, supermerkatuan, ospitalean...

Ingeniaritzaren kasua, teoria honek zerbitzu baten beharra duten erabiltzaile batez edo gehiagoz osotutako sistema bat modelatzea ahalbidetzen digu. Erabiltzaile hauek, zerbitzari berdinean elkartu egingo dira eta beraz atzerapenak sortu ahal dira, erabiltzailea sistemara heltzen denetik zerbitzua izaten hasten den arte. Beraz, telekomunikazio edo konputagailu-sare bateko kongestioa modelatzeko teoria oso baliagarria da.

Historia

1909 urtean, Agner Krarup Erlang (Danimarka, 1878 - 1929) matematikari daniarrak, Copenhagen Telephone Exchangen lan egiten ari zen bitartean, ilara-teoriari buruzko lehen artikulua argitaratu zuen.^[1]

Agner Krarup Erlang.

Artikulu honen helburua, Kopenhageko telefonia sisteman gertatzen zen trafiko kongestioa ikertzea zen.

Bere ikerkuntzek, teoria berri bat ekarri zuten, ilara-teoria alegia.

Helburuak

Teoria honen helburuak hurrengoak dira:

Kostua minimizatzen duen sistemaren gaitasun maila egokiena definitzea.
Sistemaren gaitasun maila hobetzeko egindako aldaketak kostu totalean izango zuten eragina aztertzea.
Ilaran edo itxarote ilaran egondako denborari arreta jartzea.

Ilara baten elementuak

Ilara baten modelo sinplea

Ilara baten parte hartzen duten hainbat elementu daude. Ilararen portaera egokia izateko, elementu hauek era egokian konfiguratzea derrigorrezkoa da, kongestioa ekiditeko.

Erabiltzaileen etorrera

Interpretazioa
- Nodo (edo lotura) batera heltzen diren paketeak (pakete konmutazioa).
- Zerbitzatuak izateko itxaroten ari diren deiak (zirkuituen konmutazioa).
Elkarren jarraian datozen bi erabiltzaileen etorreren arteko denbora tartea.
- Determinista. Erabiltzaileen etorreren arteko denbora konstantea da, hau da, beti da berdina.
- Probabilista (esponentziala). Kasu hau kasurik arruntena da. Paketeen etorreren arteko denbora ez da beti berdina. Adibidez, supermerkatu batean bezeroak nahi dutenean joaten dira ilarara.
Erabiltzaileen etorrera tasa

Denbora jakin batean ilarara heltzen den erabiltzaile kopurua adierazten duen parametroa da. λ izki grekoaz adierazten da.

Itxarote ilara

Zerbitzaria beste bezero batekin (pakete) okupatuta badago, datozen paketeak itxarote ilara baten (buffer) itxarongo dute. Zerbitzaria libre dagoenean, itxarote ilarako pakete bat zerbitzarira pasatuko da, ilararen diziplinaren arabera. Itxarote ilararen tamaina finitua edo infinitua izan daiteke. Normalean infinituak direla suposatuko da, hau da, erabiltzailea galdu egiten da edo berriz egiten du eskaera. Hainbat diziplina mota daude^[2]:

FIFO: Lehengo heldu dena lehengo ateratzen da.
LIFO: azkena heldu dena lehengoa ateratzen da.
Zerbitzu denbora txikiena lehengo ateratzen da.
Zerbitzu denbora handiena behar duena lehengo ateratzen da.

Zerbitzaria

Interpretazioa
- Lotura batek daukan transmisio gaitasuna (pakete konmutazioa).
- Denbora tarte batean burututako dei kopurua (zirkuitu konmutazioa).
Zerbitzari kopurua.

Ilara baten hainbat zerbitzari egon daitezke paraleloan. Hau da, zerbitzari bakar bat egon beharrean bat baino gehiago egon ahal dira. Honi esker, paketeak denbora gutxiago egongo dira itxarote ilaran, kongestioa minimizatuz. Zerbitzari hauek beraien artean independenteak izan ahal dira.

Zerbitzu denboren banaketa.
- Determinista (pakete guztiek denbora berdina iragaten dute zerbitzarian).
- Esponentziala (paketeek denbora ezberdinak iragaten dituzte zerbitzarian).
Erabiltzaileen zerbitzu tasa

Zerbitzariak denbora jakin batean zerbitzaturiko erabiltzaile kopurua da. μ izki grekoaz adierazten da eta honela definitzen da:

$\mu =C/l$ (pakete/segundo)

μ= Erabiltzaileen zerbitzu tasa.

C=Kanalaren gaitasuna, bit/seg edo karakt/seg neurtuta.

l=pakete baten batezbesteko luzera (bit/pakete).

Ilararen egoera

Ilaran dagoen erabiltzaile (edo pakete) kopurua da, zerbitzarian egon daitekeena barne. Ilara baten portaera aztertzeko, λ eta μ aldagaiak aztertu behar dira.

Erabiltzaileen etorrera tasa (λ) zerbitzu tasa(μ) baino handiagoa denean (edo berdina), ilaran portaera ezegonkorra emango da. Izan ere, zerbitzatzen diren baino pakete gehiago heltzen dira.

Ilararen tamaina finitua bada (benetako kasua) ilara bete egingo da eta geroago datozen erabiltzaileak blokeatu egingo dira. Ilararen tamaina infinitua bada (kasu ideala) atzerapenak handitu egingo dira.

Ondorioz, ilaran portaera egokia emateko, etorrera tasak zerbitzu tasak baino txikiagoak izan behar dira.

Kendall-en notazioa

David G. Kendallek, ilarak definitzeko A/B/C notazio bat sortu zuen 1953an.^[3] Notazio hau urteak igaro ahala, hedatzen joan da eta gaur egun 1/2/3/(4/5/6) moduan ezagutzen da. Zenbakiek hurrengoa esan nahi dute:

Etorreren arteko denboraren banaketa zehazten duen kodea da. Erabilitako kodeak hurrengoak dira:
- M (Markoviarra): Erabiltzaileen etorrera tasak Poissonen distribuzio bat jarraitzen du eta etorreren arteko denborak distribuzio esponentzial bat .
- D: Etorreren arteko denborak deterministak dira.
- G: Etorreren arteko denborak banaketa orokor bat jarraitzen dute (edozein izan daiteke).
Aurrekoaren berdina, baina kasu honetan zerbitzu denboretarako. Kodigo berdinak erabiltzen dira.
Sisteman paraleloan dauden zerbitzari kopurua.
Ilaran guztira egon daitezkeen erabiltzaile kopurua adierazten du (zerbitzariak barne).
Iturriaren tamaina adierazten du. Hau da, etorrerak zenbat toki ezberdinetatik datozen.
Ilararen diziplina adierazten du (FIFO, LIFO...).

Adibidez, M/M/1 ilarak, etorrera eta zerbitzu markoviarrak ditu eta zerbitzari bakar bat dauka. Erabiltzaile kopurua ez bada jartzen , infinitu kontsideratzen da.

Ohiko egiturak

Ohiko sistemak

Irudian ikus daitekeen lehenengo sistema, modelorik sinpleena da, hau da, zerbitzari batez eta ilara batez osatutako sistema bat.

Bigarrena, ilara bat eta zerbitzari anitz dituen sistema bat da. Hirugarren sisteman, zerbitzari bakoitzak banaketa ilara bat du. Azkenengo sistema, seriean dauden zerbitzariz osatutako sistema bat da.^[4]

Ilaretan neurtutako parametroak

Egoera probabilitateak

Egoera probabilitateak (Pn) , ilaran n erabiltzaile( zerbitzarietan daudenak barne) izateko probabilitatea da. Sistemak egoera egonkorrena lortzen duenean, egoera horretan dagoen erabiltzaileen probabilitatea denborarekin ez dela aldatzen suposatuko da. Sisteman erabiltzaile gabeko egoeratik (n=0) abiatzen bagara, denborarekin Pn balioak balio egonkorrenetara hurbilduko dira. Pn balio hauek, normalean, ilaran gertatu ahal daitezkeen kasu guztien egoera diagrama bat eginez lortzen dira.

Ilaran batezbesteko erabiltzaile kopurua

Ilaran dauden batezbesteko erabiltzaile (pakete) kopurua , En, hurrengo formularekin definitzen da:

$E(n)=\sum _{1}^{\infty }n*Pn$

Throughput

Throughputa, γ, zerbitzatutako batezbesteko erabiltzale kopurua denbora unitateko (pakete/segundo) da. Throughputa kalkulatzeko formula orokorra hurrengoa da:

$\gamma =\sum _{n=1}^{\infty }\mu _{n}*Pn$

Ilararen batezbesteko atzerapena

Ilararen batezbesteko atzerapen, E(T), pakete batek ilaran ematen duen denbora da, ilarara sartzen denetik zerbitzaritik irteten den arte. Segundotan ematen da. Bere balioa, Little-en formularen bidez kalkulatu dezakegu:

$E(n)=\gamma *E(T)$

Itxarote ilaran itxarote denbora

Itxarote ilaran itxarote denbora, paketeek ilarara heltzen direnetik, zerbitzarira pasatzen diren arte igarotako denbora adierazten du. Segundotan adierazten da.

$E(W)=E(T)-{\biggl (}1\div \mu {\biggr )}$

Hemen, parentesi arteko terminoa, paketeek zerbitzarian ematen duten batezbesteko denbora da.

Itxarote ilarako batezbesteko erabiltzaile kopurua

Itxarote ilaran dauden batezbesteko erabiltzaile kopurua, E(q), honela kalkulatzen da:

$E(q)=\gamma *E(w)$

Erreferentziak

↑ (Ingelesez) «Agner Krarup Erlang (1878 - 1929)» plus.maths.org 1997-05-01 (Noiz kontsultatua: 2019-11-16).
↑ «Características de un sistema de colas» www.um.es (Noiz kontsultatua: 2019-11-16).
↑ «Algorithmic Analysis of Queueing Models» A First Course in Stochastic Models (John Wiley & Sons, Ltd): 339–430. 2004-12-27 ISBN 9780470013632. (Noiz kontsultatua: 2019-11-16).
↑ Castañeda, Ing Andrea Bueno. «TEORÍA DE COLAS» INVESTIGACIÓN DE OPERACIONES (Noiz kontsultatua: 2019-11-17).

Ikus, gainera

Kanpo estekak

Datuak: Q847526
Multimedia: Queueing theory / Q847526

[1] (Ingelesez) «Agner Krarup Erlang (1878 - 1929)» plus.maths.org 1997-05-01 (Noiz kontsultatua: 2019-11-16).

[2] «Características de un sistema de colas» www.um.es (Noiz kontsultatua: 2019-11-16).

[3] «Algorithmic Analysis of Queueing Models» A First Course in Stochastic Models (John Wiley & Sons, Ltd): 339–430. 2004-12-27 ISBN 9780470013632. (Noiz kontsultatua: 2019-11-16).

[4] Castañeda, Ing Andrea Bueno. «TEORÍA DE COLAS» INVESTIGACIÓN DE OPERACIONES (Noiz kontsultatua: 2019-11-17).

[1]

[2]

[3]

[4]