Ауыр трафикті жуықтау - Heavy traffic approximation

Жылы кезек теориясы, математика шеңберіндегі тәртіп ықтималдық теориясы, а трафиктің тығыздығы (кейде үлкен қозғалыс шектеу теоремасы^[1] немесе диффузиялық жуықтау) кезек моделінің сәйкес келуі диффузиялық процесс кейбірінің астында шектеу модель параметрлері бойынша шарттар. Алғашқы осындай нәтиже жариялады Джон Кингмен an параметрін пайдалану параметрі кім екенін көрсетті M / M / 1 кезегі 1-ге жақын болса, кезектің ұзындық процесінің масштабталған нұсқасын a жуықтауы мүмкін броундық қозғалыс көрініс тапты.^[2]

Қозғалыстың ауыр жағдайы

Әдетте процесс үшін ауыр трафиктің жуықтамалары белгіленеді X(т) уақыттағы жүйенің тұтынушыларының санын сипаттау т. Олар модельдің кейбір параметрлерінің шекті мәндері бойынша модельді ескере отырып келеді, сондықтан нәтиже шектеулі болу үшін модель коэффициент арқылы өзгертілуі керек n, деп белгіленді^[3]:490

${ displaystyle { hat {X}} _ {n} (t) = { frac {X (nt) - mathbb {E} (X (nt))}} { sqrt {n}}}}$

және бұл процестің шегі ретінде қарастырылады n → ∞.

Әдетте мұндай жуықтаулар қарастырылатын үш режим режимі бар.

1. Серверлер саны бекітіліп, трафиктің қарқындылығы 1-ге дейін (төменнен) көбейтіледі. Кезектің ұзындығын жуықтау - a броундық қозғалыс көрініс тапты.^[4][5][6]
2. Трафиктің қарқындылығы бекітіліп, серверлер саны мен келу жылдамдығы шексіздікке дейін көбейтіледі. Мұнда кезек ұзындығының шегі келесіге жақындайды қалыпты таралу.^[7][8][9]
3. Шама β қайда бекітілген

${ displaystyle beta = (1- rho) { sqrt {s}}}$

бірге ρ қозғалыс қарқындылығын білдіретін және с серверлер саны. Трафиктің қарқындылығы және серверлер саны шексіздікке дейін көбейтіледі және шектеу процесі жоғарыда келтірілген нәтижелердің буданы болып табылады. Хальфин мен Уитт алғаш рет жариялаған бұл іс көбінесе Халфин-Уитт режимі деп аталады^[1][10][11] немесе сапа мен тиімділікке негізделген (QED) режимі.^[12]

G / G / 1 кезегінің нәтижелері

Теорема 1. ^[13] Тізбегін қарастырайық G / G / 1 кезектері индекстелген ${ displaystyle j}$.
Кезек үшін ${ displaystyle j}$
рұқсат етіңіз ${ displaystyle T_ {j}}$ кездейсоқ келу уақытын белгілеу, ${ displaystyle S_ {j}}$ кездейсоқ қызмет көрсету уақытын белгілеңіз; рұқсат етіңіз ${ displaystyle rho _ {j} = { frac { lambda _ {j}} { mu _ {j}}}}$ трафиктің қарқындылығын ${ displaystyle { frac {1} { lambda _ {j}}} = E (T_ {j})}$ және ${ displaystyle { frac {1} { mu _ {j}}} = E (S_ {j})}$; рұқсат етіңіз ${ displaystyle W_ {q, j}}$ тұрақты күйде тұтынушыны кезекте күту уақытын белгілеу; Келіңіздер ${ displaystyle alpha _ {j} = - E [S_ {j} -T_ {j}]}$ және ${ displaystyle beta _ {j} ^ {2} = operatorname {var} [S_ {j} -T_ {j}];}$

Айталық ${ displaystyle T_ {j} { xrightarrow {d}} T}$, ${ displaystyle S_ {j} { xrightarrow {d}} S}$, және ${ displaystyle rho _ {j} rightarrow 1}$. содан кейін

${ displaystyle { frac {2 alpha _ {j}} { beta _ {j} ^ {2}}} W_ {q, j} { xrightarrow {d}} exp (1)}$

егер:

(а) ${ displaystyle operatorname {Var} [S-T]> 0}$

(b) кейбіреулер үшін ${ displaystyle delta> 0}$, ${ displaystyle E [S_ {j} ^ {2+ delta}]}$ және ${ displaystyle E [T_ {j} ^ {2+ delta}]}$ екеуі де кейбір тұрақтыдан аз ${ displaystyle C}$ барлығына ${ displaystyle j}$.

Эвристикалық дәлел

• Кезекте күту уақыты

Келіңіздер ${ displaystyle U ^ {(n)} = S ^ {(n)} - T ^ {(n)}}$ n-ші қызмет уақыты мен n-ші келу уақыты арасындағы айырмашылық болсын; ${ displaystyle W_ {q} ^ {(n)}}$ үшінші тұтынушының кезегінде күту уақыты;

Содан кейін анықтама бойынша:

${ displaystyle W_ {q} ^ {(n)} = max (W_ {q} ^ {(n-1)} + U ^ {(n-1)}, 0)}$

Рекурсивті есептеуден кейін бізде:

${ displaystyle W_ {q} ^ {(n)} = max (U ^ {(1)} + cdots + U ^ {(n-1)}, U ^ {(2)} + cdots + U ^ {(n-1)}, ldots, U ^ {(n-1)}, 0)}$

• Кездейсоқ жүру

Келіңіздер ${ displaystyle P ^ {(k)} = sum _ {i = 1} ^ {k} U ^ {(n-i)}}$, бірге ${ displaystyle U ^ {(i)}}$ i.i.d болып табылады; Анықтаңыз ${ displaystyle alpha = -E [U ^ {(i)}]}$ және ${ displaystyle beta ^ {2} = operatorname {var} [U ^ {(i)}]}$;

Сонда бізде бар

${ displaystyle E [P ^ {(k)}] = - k альфа}$

${ displaystyle operatorname {var} [P ^ {(k)}] = k beta ^ {2}}$

${ displaystyle W_ {q} ^ {(n)} = max _ {n-1 geq k geq 0} P ^ {(k)};}$

Біз алып жатырмыз ${ displaystyle W_ {q} ^ {( infty)} = sup _ {k geq 0} P ^ {(k)}}$ шектеуді қабылдау арқылы ${ displaystyle n}$.

Осылайша үшінші тұтынушының кезегінде күту уақыты ${ displaystyle W_ {q} ^ {(n)}}$ а-ның супремумы болып табылады кездейсоқ серуендеу теріс дрейфпен.

• Броундық қозғалысқа жуықтау

Кездейсоқ жүру жуықтауы мүмкін Броундық қозғалыс секіру өлшемдері 0-ге жақындағанда және секіру арасындағы уақыттар 0-ге жақындағанда.

Бізде бар ${ displaystyle P ^ {(0)} = 0}$ және ${ displaystyle P ^ {(k)}}$ тәуелсіз және стационарлық өсулерге ие. Қозғалыс қарқындылығы кезінде ${ displaystyle rho}$ тәсілдері 1 және ${ displaystyle k}$ ұмтылады ${ displaystyle infty}$, Бізде бар ${ displaystyle P ^ {(t)} sim mathbb {N} (- alpha t, beta ^ {2} t)}$ ауыстырылғаннан кейін ${ displaystyle k}$ үздіксіз мәнімен ${ displaystyle t}$ сәйкес функционалдық орталық шегі теоремасы.^[14]:110 Осылайша кезекте күту уақыты ${ displaystyle n}$тұтынушыны а супремумы бойынша жуықтауға болады Броундық қозғалыс теріс дрейфпен.

• Броундық қозғалыс супремумы

Теорема 2.^[15]:130 Келіңіздер ${ displaystyle X}$ болуы а Броундық қозғалыс дрейфпен ${ displaystyle mu}$ және стандартты ауытқу ${ displaystyle sigma}$ шыққан жерінен бастап, рұқсат етіңіз ${ displaystyle M_ {t} = sup _ {0 leq s leq t} X (s)}$

егер ${ displaystyle mu leq 0}$

${ displaystyle lim _ {t rightarrow infty} P (M_ {t}> x) = exp (2 mu x / sigma ^ {2}), x geq 0;}$

басқаша

${ displaystyle lim _ {t rightarrow infty} P (M_ {t} geq x) = 1, x geq 0.}$

Қорытынды

${ displaystyle W_ {q} ^ {( infty)} thicksim exp left ({ frac {2 alpha} { beta ^ {2}}} right)}$ қозғалыс жағдайында

Осылайша, трафиктің үлкен шегі туралы теорема (Теорема 1) эвристикалық түрде дәлелденеді. Ресми дәлелдемелер әдетте басқа тәсілге сүйенеді, оған қатысты сипаттамалық функциялар.^[4][16]

Мысал

Қарастырайық M / G / 1 кезегі келу жылдамдығымен ${ displaystyle lambda}$, қызмет көрсету уақытының орташа мәні ${ displaystyle E [S] = { frac {1} { mu}}}$, және қызмет көрсету уақытының ауытқуы ${ displaystyle operatorname {var} [S] = sigma _ {B} ^ {2}}$. Кезекте күтудің орташа уақыты қанша тұрақты мемлекет ?

Кезекте күтудің нақты орташа уақыты тұрақты мемлекет береді:

${ displaystyle W_ {q} = { frac { rho ^ {2} + lambda ^ {2} sigma _ {B} ^ {2}} {2 lambda (1- rho)}}}$

Тиісті ауыр трафиктің жуықтауы:

${ displaystyle W_ {q} ^ {(H)} = { frac { lambda ({ frac {1} { lambda ^ {2}}} + sigma _ {B} ^ {2})}} 2 (1- rho)}}.}$

Ауыр трафиктің жуықтауының салыстырмалы қателігі:

${ displaystyle { frac {W_ {q} ^ {(H)} - W_ {q}} {W_ {q}}} = { frac {1- rho ^ {2}} { rho ^ {2 } + lambda ^ {2} sigma _ {B} ^ {2}}}}$

Осылайша қашан ${ displaystyle rho rightarrow 1}$, Бізде бар :

${ displaystyle { frac {W_ {q} ^ {(H)} - W_ {q}} {W_ {q}}} rightarrow 0.}$

Сыртқы сілтемелер

• G / G / 1 кезегі Сергей Фосс

Әдебиеттер тізімі