Translated from Azerbaijani to Uzbek

Mark zanjirlari

U shbu katta mavzuda bir nechta paragraflarni yoritib bo'lmaydi, lekin men harakat qilaman. Markovning zanjirlari oxirgi mashinaga ehtimoliy nuqtai nazar bilan qarashga imkon beradi. Buning uchun mashinaning holatini o'zgartiruvchi hodisalar tasodifan va mashina shunchaki ma'lum ehtimollik bilan holatlar o'rtasida o'tadi deb taxmin qilinadi. Ommaviy xizmat ko'rsatish nazariyasi uchun holati tizimdagi so'rovlar soni bo'lgan mashinadan foydalaning. "Yangi so'rov" hodisasi mashinani keyingi holatga o'tkazadi va "xizmatni tugatish" hodisasi teskari bo'ladi. Savol tug'iladi: agar siz bunday mashinani etarli vaqt bilan ta'minlasangiz nima bo'ladi? Tan olish kerakki, bunday mashinalarning ko'pchiligi parallel ravishda mavjud (agar qulay bo'lsa, mashinalar ansambli) va ular mustaqil va tasodifiy ravishda bir holatdan ikkinchisiga suzadi. Endi qandaydir holatni ko'rib chiqamiz, masalan, chizmadagi 0 holati. boshqa davlatlardagi o'tish tezligi bilan muvozanatlangan edi . Shunday qilib, biz bir xil darajada, qancha va noma'lum - davlatlar soni bo'yicha olamiz. Keyin biz tizimni aniqlaymiz va teng taqsimlanish deb ataladigan narsani topamiz. Har bir bo'lim mashinasi uchun bu taqsimot vaqtning qaysi qismida mavjudligini aytadi. Belgilarning qisqa jonglyorligi M / M / 1 natijaga olib keladi , qayerda - bu serverdan foydalanish. Tarixning oxiri. Yo'lda men bir nechta taxminlarni o'tkazib yubordim va bir nechta almashtirishlarni amalga oshirdim, lekin umid qilamanki, bundan zarar ko'rmadim.

Bunday yondashuv, agar mashinaning hozirgi holati uning keyingi xatti-harakatlarini to'liq aniqlasa va u bu vaziyatga tushib qolgani haqidagi hikoya muhim emasligini tushunish muhimdir. Mashinaning borishini har kuni tushunish uchun uning o'zi tushuniladi - oxir-oqibat, bu holat. Va bu erda stokastik jarayon uchun barcha taqsimotlar eksponent bo'lishi kerak, ammo ular xotiraga ega bo'lmasalar ham - doimiy ishlamay qolish tezligiga ega.

S huni ham aytish kerakki, agar biz adolatli taqsimlashni bilsak, tizim haqida qolgan barcha ma'lumotlarni olish oson. Tizimdagi so'rovlarning o'rtacha soni ushbu taqsimotning o'rtacha qiymati hisoblanadi. O'rtacha javob vaqtini bilish uchun so'rovlar soniga Littla teoremasini qo'llang. Vaqtinchalik javoblarni taqsimlash biroz qiyinroq, ammo qancha harakat borligini bilish ham mumkin. va javobning o'rtacha vaqti qancha .

Cheksiz vaqt javob

Ushbu taqsimotga ko'ra, siz javobning istalgan foizini topishingiz mumkin va yuzinchi foiz cheksizlikka teng ekanligi ma'lum bo'ladi. Boshqacha qilib aytadigan bo'lsak, javobning eng yomon vaqti tepalik bilan chegaralanmaydi. Umuman olganda, bu ajablanarli emas, chunki biz Puasson oqimidan foydalanganmiz. Ammo amalda bunday xatti-harakat hech qachon uchramaydi. Shubhasiz, serverga so'rovlarni kiritish oqimi cheklangan, garchi bu serverga keng tarmoq kanali va navbat uzunligi - ushbu serverdagi xotira bo'lishi mumkin. Puasson oqimi esa nolga teng bo'lmagan ehtimollik bilan imkon qadar ko'proq katta portlashlar paydo bo'lishini kafolatlaydi. Shuning uchun, men tizimni loyihalashda, agar siz yuqori foiz stavkalariga qiziqsangiz va yuklash tizimi juda yuqori bo'lsa, Puasson kirish oqimining taxminidan chiqishni tavsiya etmayman. Trafikning boshqa modellaridan foydalanish yaxshiroq, ular haqida men boshqa vaqt aytaman,

Masshtablilik va kafolat

E ndi, bizning tartibimizda tahlil tizimining etarlicha kuchli usuli mavjud bo'lganda, siz uni turli vazifalarga qo'llashga harakat qilib, mevalarni yig'ib olishingiz mumkin. Taxminan ommaviy xizmat nazariyasi XX asrning ikkinchi yarmida ishlab chiqilgan. Keling, nimaga erishilganini tushunishga harakat qilaylik. Boshlash uchun men Erlang qaror qilgan vazifalarga qaytaman. Bu M / M / k / k va M / M / k vazifalari bo'lib, ularda biz muvaffaqiyatsizlik ehtimolini cheklashni xohlaymiz. Ma'lum bo'lishicha, ular uchun Markov zanjirini qurish oson. Farqi shundaki, vazifani qo'shish orqali teskari o'tish ehtimoli ortadi, shuning uchun vazifa parallel ravishda ishlay boshlaydi, lekin vazifalar soni serverlar soniga teng bo'lganda, to'yinganlik mavjud. Keyinchalik M / M / k / k uchun tarmoq tugaydi, mashina, albatta, o'zgaradi va oxirgi holatda kelgan barcha so'rovlar muvaffaqiyatsizlikka uchraydi.

M / M / k uchun ish yanada murakkab, so'rovlar navbatda kutilmoqda, yangi shartlar paydo bo'ladi, ammo teskari o'tish ehtimoli oshmaydi - barcha serverlar allaqachon ishlamoqda. Tarmoq M / M / 1 kabi cheksiz bo'ladi. Aytgancha, agar tizimdagi so'rovlar soni cheklangan bo'lsa, unda zanjir har doim oxirgi holatlar soniga ega bo'ladi va shunga o'xshash yoki boshqacha qaror qabul qilinadi, siz cheksiz zanjir haqida gapirmaysiz. Yopiq tizimlarda zanjir har doim oxiri hisoblanadi. M / M / k / k va M / M / k uchun tavsiflangan zanjirlarni hal qilib, biz kelamizformula Bvaformula CErlanning so'zlariga ko'ra. Ular juda og'ir, men ularni haydamayman, lekin ularning yordami bilan men intuitiv natijalarni rivojlantirish uchun qiziqarli bo'lishim mumkin, bu kvadrat ildiz kadrlar qoidasi deb ataladi. To'g'ri, M / M / k tizimi mavjud l sekundiga qandaydir kirish oqimi so'rovlari. Faraz qilaylik, ertaga yukni ikki marta oshirish kerak. Savol tug'iladi: javob vaqti oldin qolgan bo'lishi uchun serverlar sonini qanday oshirish kerak? Serverlar sonini ikki baravar oshirish kerak, to'g'rimi? Ma'lum bo'lishicha, umuman emas. Biz allaqachon ko'rganimizni eslaymiz: agar siz vaqtni (serverlar va kirishlar) ikkiga tezlashtirsangiz, javobning o'rtacha vaqti ikkiga kamayadi. Bir nechta sekin va bitta tezkor serverlar mavjud - bu bitta va bir xil emas, lekin bu bitta kompyuterning yagona hisoblash kuchi emas. Xususan, M / M / 1 uchun, masalan, javob vaqti "erkin sig'im" hajmiga teskari proportsionaldir. va faqat shu hajm bilan belgilanadi. Oqimni va ikkalasining hisoblash quvvatini oshirganda, tizimning bo'sh sig'imi ikki barobar ortadi: . Vazifani hal qilish uchun shunchaki bo'sh quvvatni tejash kerakdek tuyulishi mumkin, ammo M / M / k da javob berish muddati allaqachon murakkabroq Erlanga formulasi bilan belgilanadi. Ma'lum bo'lishicha, javob berishdan oldin vaqtni tejash uchun bo'sh sig'imni "ishg'ol qilingan serverlar" kvadrat ildiziga mutanosib ravishda qo'llab-quvvatlash kerak. "Ishg'ol qilingan serverlar" soni serverlarning umumiy sonidan foydalanishga ko'paytiriladi: bu serverlar sonining barqaror ishlashi uchun zarur bo'lgan minimaldir.

Ushbu qoidadan foydalanib, ba'zida ular klasterni serverlar bilan qanday kengaytirishni oqlashga harakat qilishadi. Ammo har qanday klaster M / M / k tizimi ekanligi haqidagi illyuziyalarni oziqlantirish shart emas. Misol uchun, agar siz kirishda serverdagi navbatlarga so'rov yuboradigan balanseringiz bo'lsa - bu endi M / M / k emas, chunki M / M / k serverlar so'rovlarni qabul qiladigan umumiy navbatni nazarda tutadi, qachon so'rash kerak. Ammo bu model, masalan, umumiy FIFO navbati bo'lgan yugurish yo'laklari uchun javob beradi. Biroq, bu holatda ham, bu qoida ko'p savdolar bo'lganda, bu holat uchun taxminiylik ekanligini esga olish kerak. Haqiqatan ham, agar sizda 10 dan ortiq savdo bo'lsa, ularning ko'pligiga ishonch bilan ishonishingiz mumkin. Xo'sh, biz har tomonlama eksponensial taqsimotlar haqida unutmaymiz: barcha taqsimotlarning eksponensial taqsimotini qabul qilmasdan, qoida ham ishlamaydi.

Tarmoqqa javob berish vaqti keldi

Albatta, qiziqish M / M / k tarmog'i bo'lib, hech bo'lmaganda zanjirda bog'langan, biz taqsimlangan tizimlar kabi. Tarmoqni o'rganish uchun dizaynerga ega bo'lishni xohladim: ma'lum elementlarni blokda ulashning oddiy va aniq qoidalari. Boshqarish nazariyasida, masalan, ketma-ket yoki parallel ulanishlarda konseptual tarzda birlashtirilgan uzatish funktsiyalari mavjud. Bu erda har qanday tugundan chiqish oqimi juda murakkab taqsimotga ega, M / M / k bundan mustasno, ma'lumBurk teoremasimustaqil Puasson oqimini chiqaradi. Bu istisno, taxmin qilish mumkinki, printsipial jihatdan va ishlatilgan.

Ikki Puasson oqimining ulanishi - Puasson oqimi. Puasson oqimining ikkiga bo'linishi - yana ikkita Puasson oqimini beradi. Bularning barchasi tizimdagi barcha navbatlarning mustaqil bo'lishiga olib keladi va ular rasmiy tilda ifodalanishi mumkin.mahsulot shaklidagi yechim. Ya'ni navbatlar uzunligini birgalikda taqsimlash mavjud bo'lib, oddiygina barcha navbatlar uzunligi taqsimotining mahsuloti bo'lib, ular alohida ko'rib chiqiladi - ya'ni ehtimollar nazariyasida mustaqillik ifodalanadi. Biz oddiygina barcha tugunlardagi kirish oqimlarini topamiz va har bir tugun uchun formulalardan mustaqil ravishda foydalanamiz. Bir qator cheklovlar mavjud:

1. 
   Ehtimollik marshrutlash algoritmi. Tugun tomonidan xizmat ko'rsatadigan so'rov ma'lum ehtimollik bilan keyingi holatni tanlaydi. Bu unchalik yomon emas, ko'rinishi mumkin, chunki "so'rovlar sinfi" dan foydalanish imkoniyati mavjud: Vasi barcha so'rovlar №1 serverga, keyin №2 serverga keladi va keyin serverdan chiqib ketadi. tarmoq 2 va tarmoqni so'rang va keyin teng ehtimollik bilan №1 yoki №3 serverga tashrif buyuring va qoldiring. Ya'ni, barcha o'tishlar tasodifiy bo'lishi shart emas, ba'zilari yoki hatto barchasi 100% ehtimolga ega bo'lishi mumkin.
   
2. 
   Klaynrokning mustaqillik haqidagi taxmini. So'rovni qayta ishlash vaqti so'rovning tarixi yoki sinfiga bog'liq bo'lishi mumkin emas va faqat server tomonidan belgilanadi va so'rovni bitta va bir xil server orqali takrorlashda har safar tasodifiy tanlanadi. Aslida, turli serverlarda ishlatilgan so'rov hajmini belgilash imkoniyati mavjud va xizmat ko'rsatish vaqti faqat serverning o'zi tomonidan belgilanadi. Ushbu cheklovni chetlab o'tishga harakat qilish ham mumkin. Buning uchun ular odatda ehtimoliy marshrutlashdan foydalanadilar va ma'lum bir ehtimollik bilan bir xil serverga qaytish uchun tsiklni yaratadilar - go'yo ular so'rovni qayta ishga tushiradilar. Menimcha, bu g'alati g'alati hiyla-nayrang, chunki bunday so'rov o'z navbatida takrorlanadi va darhol bajarilmaydi, lekin ba'zi vazifalar uchun bu muhim emas.
   
3. 
   Puassonning kiruvchi trafik va barcha tugunlar uchun eksponensial xizmat vaqti.
   

Jeksonning tarmoq misoli.

Shuni ta'kidlash kerakki, ulanishni teskari o'tkazishda Puasson oqimi YO'Q, shuning uchun oqim o'zaro bog'liqdir. Teskari ulanish bilan tutashgan joydan chiqishda ham Nepuassonov oqimini oladi va oxirida barcha oqim Nepuassonov oqimiga aylanadi. Biroq, hayratlanarlisi shundaki, bu avstral bo'lmagan oqimlarning barchasi ularni Puassonian sektalari bilan bir xil yo'lga olib boradi (oh, bu ehtimollar nazariyasi), agar yuqoridagi cheklovlar bajarilsa. Va keyin biz yana mahsulot shaklidagi yechimni olamiz. Bunday tarmoqlarning nomi borJekson tarmoqlari, ular mumkin bo'lgan fikr-mulohazaga ega va shuning uchun har qanday serverga bir necha marta tashrif buyurishadi. Ko'proq hajmlarga imkon beradigan boshqa tarmoqlar mavjud, ammo natijada tarmoqlarga nisbatan ommaviy xizmat ko'rsatish nazariyasining barcha eng muhim analitik yutuqlari mahsulotga kirish va yaratish va boshqa nazariyalarning echimini ishlab chiqish uchun Puasson oqimlarini ta'minlaydi. , shuning uchun va uni o'rganish uchun, nima tarqatish uchun, albatta, zarur va ular bilan qanday ishlash kerak.

Jeksonning barcha tarmoq nazariyalarining muhim qo'llanilishi IP tarmoqlari va ATM tarmoqlarida paketli modellashtirishdir. Model etarlicha adekvat: paketlarning o'lchami kuchli o'zgartirilmaydi va original paketga bog'liq emas, faqat kanalning kengligidan, shuning uchun xizmat ko'rsatish vaqti paketni kanalga o'tkazish vaqtiga to'g'ri keladi. . Tasodifiy jo'nash vaqti, vahshiy bo'lib tuyulsa ham, aslida unchalik o'zgaruvchanlikka ega emas. Bundan tashqari, ma'lum bo'lishicha, ma'lum vaqtga ega bo'lgan tarmoqda xizmat ko'rsatishning kechikishi Jeksonning analog tarmog'idagidan ko'p bo'lishi mumkin emas, shuning uchun bunday tarmoqlar javob vaqtini baholash uchun dadil foydalanishi mumkin.

Eksponensial bo'lmagan taqsimotlar

Men aytgan barcha natijalar eksponensial taqsimotlarga tegishli edi, lekin men haqiqiy taqsimotlar boshqacha ekanligini ham aytib o'tdim. Bu butun nazariya foydasiz ekanligini his qiladi. Bu umuman bunday emas. Ushbu matematik apparatda va boshqa taqsimotlarda, bundan tashqari, deyarli har qanday tarqatishda qurishning bir usuli bor, ammo bu bizga qimmatga tushadi. Bir nechta qiziqarli holatlar bundan mustasno, aniq ko'rinishda yechim olish mumkin, mahsulot shaklidagi yechim yo'qoladi va dizayner bilan birgalikda: har bir vazifani Markov zanjiri yordamida nol bilan hal qilish kerak. Nazariya uchun bu katta muammo, lekin amalda bu shunchaki raqamli usullarni qo'llashni anglatadi va vazifa qanchalik murakkab va haqiqatga yaqinroq ekanligini aniqlash imkoniyatini beradi.