Teoria cozilor - Queueing theory

Rețelele de cozi sunt sisteme în care cozile unice sunt conectate printr-o rețea de rutare. În această imagine, serverele sunt reprezentate prin cercuri, cozile printr-o serie de dreptunghiuri și rețeaua de rutare prin săgeți. În studiul rețelelor de coadă se încearcă de obicei obținerea distribuției de echilibru a rețelei, deși în multe aplicații studiul stării tranzitorii este fundamental.

Teoria cozilor este studiul matematic al liniilor de așteptare sau a cozilor . Un model de așteptare este construit astfel încât să poată fi prezise lungimile cozii și timpul de așteptare. Teoria cozilor este în general considerată o ramură a cercetării operaționale, deoarece rezultatele sunt adesea folosite atunci când se iau decizii de afaceri cu privire la resursele necesare pentru a furniza un serviciu.

Teoria cozilor își are originea în cercetările efectuate de Agner Krarup Erlang atunci când a creat modele pentru a descrie sistemul companiei Copenhagen Telephone Exchange, o companie daneză. Ideile au văzut de atunci aplicații, inclusiv telecomunicații , ingineria traficului , calcul și, în special în ingineria industrială , în proiectarea fabricilor, magazinelor, birourilor și spitalelor, precum și în managementul proiectelor.

Ortografie

Ortografia „coadă” peste „coadă” este întâlnită de obicei în domeniul cercetării academice. De fapt, una dintre revistele emblematice din domeniu este Queuing Systems .

Noduri de coadă unice

O coadă sau un nod de așteptare poate fi considerat aproape o cutie neagră . Locurile de muncă sau „clienții” ajung la coadă, probabil așteaptă ceva timp, se prelucrează ceva timp și apoi pleacă din coadă.

O cutie neagră. Locurile de muncă ajung și pleacă de la coadă.

Cu toate acestea, nodul de așteptare nu este o cutie neagră pură, deoarece este nevoie de unele informații despre interiorul nodului de așteptare. Coada are unul sau mai multe „servere” care pot fi fiecare asociate cu o lucrare de sosire până când aceasta pleacă, după care acel server va fi liber să fie asociat cu o altă lucrare de sosire.

Un nod de așteptare cu 3 servere. Serverul a este inactiv și, prin urmare, i se dă o sosire pentru procesare. Serverul b este ocupat în prezent și va dura ceva timp până să-și poată finaliza serviciul. Serverul c tocmai a finalizat serviciul unui job și astfel va fi următorul să primească un job care ajunge.

O analogie des utilizată este cea a casierului de la un supermarket. Există și alte modele, dar acesta este unul întâlnit frecvent în literatura de specialitate. Clienții sosesc, sunt prelucrați de casier și pleacă. Fiecare casier procesează câte un client la un moment dat și, prin urmare, acesta este un nod de așteptare cu un singur server. O setare în care un client va pleca imediat dacă casierul este ocupat la sosirea clientului, este denumită coadă fără tampon (sau fără „zonă de așteptare” sau termeni similari). O setare cu o zonă de așteptare pentru până la n clienți se numește coadă cu un tampon de dimensiunea n .

Procesul naștere-moarte

Comportamentul unei singure cozi (numit și „nod de așteptare”) poate fi descris printr-un proces de naștere-deces , care descrie sosirile și plecările din coadă, împreună cu numărul de locuri de muncă (numite și „clienți” sau „solicitări” ", sau orice alt număr de lucruri, în funcție de câmp) în prezent în sistem. O sosire crește numărul de locuri de muncă cu 1, iar o plecare (un loc de muncă care își îndeplinește serviciul) scade k cu 1.

Un proces de naștere-moarte. Valorile din cercuri reprezintă starea procesului naștere-moarte. Pentru un sistem de așteptare, k este numărul de lucrări din sistem (fie fiind deservite, fie în așteptare dacă coada are un tampon de lucrări în așteptare). Sistemul trece între valorile lui k prin „nașteri” și „decese” care apar la rate date de diferite valori ale lui λ _i și respectiv μ _i . Mai mult, pentru o coadă, tarifele de sosire și tarifele de plecare sunt considerate, în general, să nu varieze cu numărul de locuri de muncă în coadă, deci se presupune o singură rată medie de sosiri / plecări pe unitate de timp până la coadă. Sub această ipoteză, acest proces are o rată de sosire de λ = λ ₁ , λ ₂ , ..., λ _k și o rată de plecare de μ = μ ₁ , μ ₂ , ..., μ _k (a se vedea figura următoare).

O coadă cu 1 server, rata de sosire λ și rata de plecare μ .

Ecuații de echilibru

La starea de echilibru , ecuațiile pentru procesul de naștere și moarte, cunoscute sub numele de ecuațiile de echilibru , sunt după cum urmează. Aici denotă probabilitatea stării staționare de a fi în starea n . ${\ displaystyle P_ {n}}$

{\ displaystyle \ mu _ {1} P_ {1} = \ lambda _ {0} P_ {0}}

{\ displaystyle \ lambda _ {0} P_ {0} + \ mu _ {2} P_ {2} = (\ lambda _ {1} + \ mu _ {1}) P_ {1}}

{\ displaystyle \ lambda _ {n-1} P_ {n-1} + \ mu _ {n + 1} P_ {n + 1} = (\ lambda _ {n} + \ mu _ {n}) P_ { n}}

Primele două ecuații implică

{\ displaystyle P_ {1} = {\ frac {\ lambda _ {0}} {\ mu _ {1}}} P_ {0}}

și

{\ displaystyle P_ {2} = {\ frac {\ lambda _ {1}} {\ mu _ {2}}} P_ {1} + {\ frac {1} {\ mu _ {2}}} (\ mu _ {1} P_ {1} - \ lambda _ {0} P_ {0}) = {\ frac {\ lambda _ {1}} {\ mu _ {2}}} P_ {1} = {\ frac {\ lambda _ {1} \ lambda _ {0}} {\ mu _ {2} \ mu _ {1}}} P_ {0}.}

Prin inducție matematică,

{\ displaystyle P_ {n} = {\ frac {\ lambda _ {n-1} \ lambda _ {n-2} \ cdots \ lambda _ {0}} {\ mu _ {n} \ mu _ {n- 1} \ cdots \ mu _ {1}}} P_ {0} = P_ {0} \ prod _ {i = 0} ^ {n-1} {\ frac {\ lambda _ {i}} {\ mu _ {i + 1}}}.}

Condiția duce la: ${\ displaystyle \ sum _ {n = 0} ^ {\ infty} P_ {n} = P_ {0} + P_ {0} \ sum _ {n = 1} ^ {\ infty} \ prod _ {i = 0 } ^ {n-1} {\ frac {\ lambda _ {i}} {\ mu _ {i + 1}}} = 1}$

{\ displaystyle P_ {0} = {\ frac {1} {1+ \ sum _ {n = 1} ^ {\ infty} \ prod _ {i = 0} ^ {n-1} {\ frac {\ lambda _ {i}} {\ mu _ {i + 1}}}}},}

care, împreună cu ecuația pentru , descrie pe deplin probabilitățile stării de echilibru necesare. ${\ displaystyle P_ {n}}$ ${\ displaystyle (n \ geq 1)}$

Notația lui Kendall

Nodurile de coadă unice sunt de obicei descrise folosind notația Kendall sub forma A / S / c unde A descrie distribuția duratelor dintre fiecare sosire la coadă, S distribuirea timpilor de serviciu pentru joburi și c numărul de servere la nod. Pentru un exemplu de notație, coada M / M / 1 este un model simplu în care un singur server servește joburi care ajung în conformitate cu un proces Poisson (unde duratele de inter-sosire sunt distribuite exponențial ) și au timp de serviciu distribuit exponențial (M denotă un proces Markov ). Într-o coadă M / G / 1 , G înseamnă „general” și indică o distribuție de probabilitate arbitrară pentru timpii de serviciu.

Exemplu de analiză a unei cozi M / M / 1

Luați în considerare o coadă cu un singur server și următoarele caracteristici:

λ : rata de sosire (reciprocitatea timpului așteptat între fiecare client care ajunge, de exemplu, 10 clienți pe secundă);
μ : reciprocitatea timpului mediu de serviciu (numărul așteptat de completări consecutive ale serviciului pe aceeași unitate de timp, de exemplu, pe 30 de secunde);
n : parametrul care caracterizează numărul de clienți din sistem;
P _n : probabilitatea de a exista n clienți în sistem în stare de echilibru.

Mai mult, să reprezentăm E _n de câte ori sistemul intră în starea n , iar L _n reprezintă de câte ori sistemul părăsește starea n . Apoi pentru toate n , | E _n - L _n | ∈ {0, 1}. Adică, de câte ori sistemul părăsește o stare diferă cu cel mult 1 de câte ori intră în acea stare, deoarece fie va reveni în acea stare la un moment dat în viitor ( E _n = L _n ), fie nu (| E _n - L _n | = 1).

Când sistemul ajunge la o stare stabilă, rata de sosire trebuie să fie egală cu rata de plecare.

Astfel ecuațiile de echilibru

{\ displaystyle \ mu P_ {1} = \ lambda P_ {0}}

{\ displaystyle \ lambda P_ {0} + \ mu P_ {2} = (\ lambda + \ mu) P_ {1}}

{\ displaystyle \ lambda P_ {n-1} + \ mu P_ {n + 1} = (\ lambda + \ mu) P_ {n}}

implică

{\ displaystyle P_ {n} = {\ frac {\ lambda} {\ mu}} P_ {n-1}, \ n = 1,2, \ ldots}

Faptul care duce la formula de distribuție geometrică ${\ displaystyle P_ {0} + P_ {1} + \ cdots = 1}$

{\ displaystyle P_ {n} = (1- \ rho) \ rho ^ {n}}

Unde ${\ displaystyle \ rho = {\ frac {\ lambda} {\ mu}} <1.}$

Coadă simplă de două ecuații

Un sistem comun de așteptare de bază este atribuit lui Erlang și este o modificare a Legii lui Little . Având în vedere o rată de sosire λ , o rată de abandon σ și o rată de plecare μ , lungimea cozii L este definită ca:

{\ displaystyle L = {\ frac {\ lambda - \ sigma} {\ mu}}.}

Presupunând o distribuție exponențială pentru tarife, timpul de așteptare W poate fi definit ca proporția de sosiri care sunt deservite. Aceasta este egală cu rata de supraviețuire exponențială a celor care nu abandonează perioada de așteptare, oferind:

{\ displaystyle {\ frac {\ mu} {\ lambda}} = e ^ {- W {\ mu}}}

A doua ecuație este de obicei rescrisă ca:

{\ displaystyle W = {\ frac {1} {\ mu}} \ mathrm {ln} {\ frac {\ lambda} {\ mu}}}

Modelul în două etape cu o singură cutie este comun în epidemiologie.

Prezentare generală a dezvoltării teoriei

În 1909, Agner Krarup Erlang , un inginer danez care lucra pentru Centrul de telefonie din Copenhaga, a publicat prima lucrare despre ceea ce acum s-ar numi teoria cozilor. El a modelat numărul de apeluri telefonice care au ajuns la o centrală printr-un proces Poisson și a rezolvat coada M / D / 1 în 1917 și modelul de coadă M / D / k în 1920. În notația lui Kendall:

M înseamnă Markov sau fără memorie și înseamnă că sosirile au loc conform unui proces Poisson;
D înseamnă determinist și înseamnă locuri de muncă care ajung la coadă care necesită o cantitate fixă de serviciu;
k descrie numărul de servere la nodul de așteptare ( k = 1, 2, ...).

Dacă există mai multe joburi la nod decât servere, atunci joburile se vor aștepta la coadă și vor aștepta service

Coada M / G / 1 a fost rezolvată de Felix Pollaczek în 1930, o soluție reformată ulterior în termeni probabilistici de Aleksandr Khinchin și acum cunoscută sub numele de formula Pollaczek-Khinchine .

După anii 1940, teoria cozilor a devenit o zonă de interes pentru cercetători pentru matematicieni. În 1953, David George Kendall a rezolvat coada GI / M / k și a introdus notația modernă pentru cozi, cunoscută acum ca notația lui Kendall . În 1957, Pollaczek a studiat GI / G / 1 folosind o ecuație integrală . John Kingman a dat o formulă pentru timpul mediu de așteptare într-o coadă G / G / 1 : formula lui Kingman .

Leonard Kleinrock a lucrat la aplicarea teoriei cozilor la comutarea mesajelor la începutul anilor 1960 și la comutarea pachetelor la începutul anilor 1970. Contribuția sa inițială în acest domeniu a fost teza sa de doctorat la Massachusetts Institute of Technology în 1962, publicată sub formă de carte în 1964. Lucrarea sa teoretică publicată la începutul anilor 1970 a susținut utilizarea comutării pachetelor în ARPANET , un precursor al internetului.

Matricea metoda geometrică și matricea metode analitice au permis cozi cu tip de fază distribuită între sosire și distribuțiile timp de serviciu pentru a fi luate în considerare.

Sistemele cu orbite cuplate sunt o parte importantă în teoria cozilor în aplicația la rețelele fără fir și procesarea semnalului.

Probleme precum metricele de performanță pentru coada M / G / k rămân o problemă deschisă.

Disciplinele de serviciu

Exemplu de coadă First in first out (FIFO).

Diverse politici de planificare pot fi utilizate la nodurile de așteptare:

Prima în prima ieșire: Numit și primul venit, primul servit (FCFS), acest principiu afirmă că clienții sunt deserviți câte unul și că clientul care a așteptat cel mai mult este servit primul.

Ultima în prima ieșire: Acest principiu servește, de asemenea, clienții pe rând, dar clientul cu cel mai scurt timp de așteptare va fi servit mai întâi. Cunoscut și ca stivă .

Partajarea procesorului: Capacitatea serviciilor este împărțită în mod egal între clienți.

Prioritate: Clienții cu prioritate ridicată sunt primiți mai întâi. Cozile prioritare pot fi de două tipuri, non-preventive (în cazul în care un job în serviciu nu poate fi întrerupt) și preventive (în cazul în care un job în serviciu poate fi întrerupt de un job cu prioritate mai mare). Niciun model nu se pierde.

Cel mai scurt loc de muncă mai întâi: Următorul serviciu care urmează să fie servit este cel cu cea mai mică dimensiune

Cel mai scurt loc de muncă preventiv mai întâi: Următorul serviciu care urmează să fie servit este cel cu cea mai mică dimensiune originală

Cel mai scurt timp de procesare rămas: Următorul serviciu de servit este cel cu cea mai mică cerință de procesare rămasă.

Facilitatea de service

Server unic: clienții se aliniază și există un singur server
Mai multe servere paralele - Coadă unică: clienții se aliniază și există mai multe servere
Mai multe servere – Mai multe cozi: există multe contoare și clienții pot decide să meargă unde să facă coadă

Server nesigur

Eșecurile serverului apar în funcție de un proces stocastic (de obicei Poisson) și sunt urmate de perioadele de configurare în care serverul nu este disponibil. Clientul întrerupt rămâne în zona de servicii până când serverul este reparat.

Comportamentul de așteptare al clientului

Balking: clienții care decid să nu adere la coadă dacă este prea lung
Jockeying: clienții comută între cozi dacă cred că vor fi servite mai repede făcând acest lucru
Renegare: clienții părăsesc coada dacă au așteptat prea mult timp pentru service

Clienții sosiți care nu sunt deserviți (fie din cauza cozii care nu au tampon, fie din cauza refuzului sau renunțării de către client) sunt, de asemenea, cunoscuți ca abandon și rata medie a abandonului este un parametru semnificativ care descrie o coadă.

Rețele în așteptare

Rețelele de cozi sunt sisteme în care un număr de cozi sunt conectate prin ceea ce este cunoscut sub numele de rutare a clienților. Atunci când un client este deservit la un nod, acesta se poate alătura unui alt nod și poate face coadă pentru service sau poate părăsi rețeaua.

Pentru rețelele de m noduri, starea sistemului poate fi descrisă printr-un vector m- dimensional ( x ₁ , x ₂ , ..., x _m ) unde x _i reprezintă numărul de clienți la fiecare nod.

Cea mai simplă rețea non-trivială de cozi se numește cozi tandem . Primele rezultate semnificative în acest domeniu au fost rețelele Jackson , pentru care există o distribuție staționară eficientă sub formă de produs și analiza valorii medii care permite calcularea valorilor medii, cum ar fi randamentul și timpul de ședere. Dacă numărul total de clienți din rețea rămâne constant, rețeaua se numește rețea închisă și s-a demonstrat că are o distribuție staționară sub formă de produs în teorema Gordon-Newell . Acest rezultat a fost extins la rețeaua BCMP unde o rețea cu timp de serviciu foarte general, regimuri și direcționarea clienților prezintă o distribuție staționară sub formă de produs. Constanta de normalizare poate fi calculată cu algoritmul lui Buzen , propus în 1973.

Au fost cercetate, de asemenea, rețelele de clienți , rețelele Kelly în care clienții din clase diferite experimentează diferite niveluri de prioritate la diferite noduri de servicii. Un alt tip de rețea sunt rețelele G propuse pentru prima dată de Erol Gelenbe în 1993: aceste rețele nu presupun distribuții exponențiale de timp, precum clasica rețea Jackson.

Algoritmi de rutare

În rețelele discrete de timp în care există o constrângere pe care nodurile de serviciu pot fi active în orice moment, algoritmul de planificare a greutății maxime alege o politică de serviciu pentru a oferi un randament optim în cazul în care fiecare job vizită doar un singur nod de serviciu de persoană. În cazul mai general în care joburile pot vizita mai multe noduri, rutare de presiune inversă oferă un randament optim. Un programator de rețea trebuie să aleagă un algoritm de așteptare , care afectează caracteristicile rețelei mai mari. Consultați și Planificarea stochastică pentru mai multe despre planificarea sistemelor de așteptare.

Limite ale câmpului mediu

Modelele cu câmp mediu consideră comportamentul limitativ al măsurii empirice (proporția de cozi în diferite stări), deoarece numărul de cozi ( m deasupra) merge la infinit. Impactul altor cozi asupra oricărei cozi date din rețea este aproximat printr-o ecuație diferențială. Modelul determinist converge la aceeași distribuție staționară ca și modelul original.

Aproximări trafic intens / difuzie

Într-un sistem cu rate de ocupare ridicate (utilizare aproape de 1) se poate utiliza o aproximare a traficului intens pentru a aproxima procesul de lungime a cozii printr-o mișcare browniană reflectată , procesul Ornstein-Uhlenbeck sau un proces de difuzie mai general . Numărul de dimensiuni al procesului Brownian este egal cu numărul de noduri în coadă, cu difuziunea limitată la ortantul negativ .

Limite de lichid

Modelele de fluid sunt analogi deterministici continui ai rețelelor de așteptare obținute prin luarea limitei atunci când procesul este scalat în timp și spațiu, permițând obiecte eterogene. Această traiectorie la scară converge la o ecuație deterministă care permite dovedirea stabilității sistemului. Se știe că o rețea de așteptare poate fi stabilă, dar are o limită de fluid instabilă.

Servicii de rețea software

Atunci când folosim servicii de rețea softwarizate într-o rețea de așteptare, constatăm că măsurarea diferitelor perioade de răspuns ale rețelei noastre este un lucru important, deoarece ar putea afecta tot sistemul nostru. Cunoașterea acestor date și încercarea de a le corecta pe cele care pot provoca o eroare este o sarcină pe care trebuie să o rezolvăm.

Vezi si

Referințe

Lecturi suplimentare

Gross, Donald; Carl M. Harris (1998). Fundamentele teoriei cozii . Wiley. ISBN 978-0-471-32812-4. Pe net
Zukerman, Moshe (2013). Introducere în teoria cozii și a modelelor de teletrafic stochastic (PDF) . arXiv : 1307.2968 .
Deitel, Harvey M. (1984) [1982]. O introducere în sistemele de operare (revizuită prima ediție). Addison-Wesley. p. 673 . ISBN 978-0-201-14502-1. cap.15, pp. 380–412
Gelenbe, Erol; Isi Mitrani (2010). Analiza și sinteza sistemelor informatice . World Scientific 2nd Edition. ISBN 978-1-908978-42-4.
Newell, Gordron F. (1 iunie 1971). Aplicații ale teoriei cozii . Chapman și Hall.
Leonard Kleinrock, Information Flow in Large Communication Nets , (MIT, Cambridge, 31 mai 1961) Propunere pentru un doctorat. Teză
Leonard Kleinrock. Fluxul de informații în rețelele de comunicații mari (Raportul de progres trimestrial RLE, iulie 1961)
Leonard Kleinrock. Rețele de comunicare: fluxul și întârzierea mesajelor stochastice (McGraw-Hill, New York, 1964)
Kleinrock, Leonard (2 ianuarie 1975). Sisteme de așteptare: Volumul I - Teorie . New York: Wiley Interscience. pp. 417 . ISBN 978-0471491101.
Kleinrock, Leonard (22 aprilie 1976). Sisteme de așteptare: Volumul II - Aplicații pentru computer . New York: Wiley Interscience. p. 576 . ISBN 978-0471491118.
Lazowska, Edward D .; John Zahorjan; G. Scott Graham; Kenneth C. Sevcik (1984). Performanța cantitativă a sistemului: Analiza sistemului computerizat utilizând modele de rețea în coadă . Prentice-Hall, Inc. ISBN 978-0-13-746975-8.
Jon Kleinberg; Éva Tardos (30 iunie 2013). Proiectarea algoritmului . Pearson. ISBN 978-1-292-02394-6.

Languages

In other projects