Основная модель мультисервисного узла доступа (мультисервисная модель Эрланга)

1 / 79 Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ 100 95 75 25 5 Ëåêöèÿ 3 Îñíîâíàÿ ìîäåëü ìóëüòèñåðâèñíîãî óçëà äîñòóïà (ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà) Ñòåïàíîâ Ñ. Í. Ìîñêîâñêèé òåõíè÷åñêèé óíèâåðñèòåò ñâÿçè è èíôîðìàòèêè êàôåäðà Ñåòè ñâÿçè è ñèñòåìû êîììóòàöèè Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà Ñîäåðæàíèå 1. Îñîáåííîñòè ïîñòðîåíèÿ ìîäåëåé ìóëüòèñåðâèñíûõ óçëîâ äîñòóïà 2. Ìóëüòèñåðâèñíûé òðàôèê â óçëàõ äîñòóïà ôèêñèðîâàííîé ñâÿçè 3. Ìóëüòèñåðâèñíûé òðàôèê â óçëàõ äîñòóïà ïîäâèæíîé ñâÿçè 4. Ñòðóêòóðà è ñâîéñòâà ìóëüòèñåðâèñíîé ìîäåëè Ýðëàíãà 5. Ìàðêîâñêèé ïðîöåññ è ïîêàçàòåëè îáñëóæèâàíèÿ çàÿâîê 6. Ñèñòåìà óðàâíåíèé ðàâíîâåñèÿ 7. Ñâîéñòâî ìóëüòèïëèêàòèâíîñòè 8. Ðåêóðñèâíûé àëãîðèòì îöåíêè âåðîÿòíîñòåé ñîñòîÿíèé 9. Ñâîéñòâî ïðîïîðöèîíàëüíîñòè è åãî èñïîëüçîâàíèå äëÿ îöåíêè õàðàêòåðèñòèê 10. Àíàëèç ìóëüòèïëåêñèðîâàíèÿ ìîíîñåðâèñíîãî òðàôèêà 11. Àíàëèç ìóëüòèïëåêñèðîâàíèÿ ìóëüòèñåðâèñíîãî òðàôèêà 12. Ðåêóðñèâíûé àëãîðèòì îöåíêè òðåáóåìîé ïî íàãðóçêå ñêîðîñòè ëèíèè 13. Îöåíêà ìàêñèìàëüíî äîïóñòèìîé âåëè÷èíû òðàôèêà 14. Çàäàíèÿ äëÿ ñàìîñòîÿòåëüíîé ðàáîòû. 2 / 79 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 3 / 79 Ìîäåëèðîâàíèå ìóëüòèñåðâèñíîãî òðàôèêà I Ðàçâèòèå ñåòåé ñâÿçè èä¼ò ïî ïóòè ðàñøèðåíèÿ ÷èñëà ñåðâèñîâ. Êàæäûé âèä óñëóã èìååò ñâîè îñîáåííîñòè, êîòîðûå ñëåäóåò ó÷èòûâàòü ïðè èõ ñîâìåñòíîì àíàëèçå. I  ïðîñòåéøåì ñëó÷àå ñåðâèñû ðàçëè÷àþòñÿ òîëüêî ïî îáú¼ìó òðåáóåìîãî ðåñóðñà ïåðåäà÷è èíôîðìàöèè. I  áîëåå ñëîæíûõ ñèòóàöèÿõ íåîáõîäèìî ó÷èòûâàòü îñîáåííîñòè ôîðìèðîâàíèÿ âõîäíûõ ïîòîêîâ çàÿâîê, óñëîâèÿ äîñòóïà â ñåòü, âîçìîæíîñòü ïåðåðàñïðåäåëåíèÿ ðåñóðñà â ïðîöåññå îáñëóæèâàíèÿ è ò.ä. I Ïåðå÷èñëåííûå îñîáåííîñòè ôóíêöèîíèðîâàíèÿ äåéñòâóþùèõ è ïåðñïåêòèâíûõ ñèñòåì ñâÿçè ó÷èòûâàþòñÿ â êëàññå òàê íàçûâàåìûõ ìóëüòèñåðâèñíûõ ìîäåëåé òåîðèè òåëåòðàôèêà. Îíè èìåþò áîëüøîå çíà÷åíèå äëÿ ïðàêòè÷åñêèõ ïðèëîæåíèé è ÿâëÿþòñÿ ïðåäìåòîì èíòåíñèâíûõ èññëåäîâàíèé ñïåöèàëèñòàìè â îáëàñòè ñâÿçè. I Ïîäîáíûå ìîäåëè áóäóò èññëåäîâàíû äëÿ îòäåëüíûõ óçëîâ äîñòóïà è äëÿ ñåòè öåëèêîì. Ñåòü ïðåäñòàâëÿåò ñîáîé ñîâîêóïíîñòü ñîåäèíèòåëüíûõ ëèíèé è óçëîâ ñ ôèêñèðîâàííûìè òîïîëîãèåé è ìàðøðóòàìè ñëåäîâàíèÿ èíôîðìàöèîííûõ ïîòîêîâ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 4 / 79 Ìîäåëè ìóëüòèñåðâèñíûõ óçëîâ äîñòóïà I Áàçîâàÿ ìîäåëü ìóëüòèñåðâèñíîãî óçëà äîñòóïà. Àíàëèçèðóåòñÿ çàíÿòèå ðåñóðñà ïåðåäà÷è èíôîðìàöèè ïðîèçâîëüíûì ÷èñëîì ïóàññîíîâñêèõ ïîòîêîâ çàÿâîê ñ ðàçíûìè èíòåíñèâíîñòüþ ïîñòóïëåíèÿ, îáúåìîì èñïîëüçóåìîãî ðåñóðñà è äëèòåëüíîñòüþ åãî çàíÿòèÿ. Ýòó ìîäåëü óçëà òàêæå íàçûâàþò ìóëüòèñåðâèñíîé ìîäåëüþ Ýðëàíãà. I Ìóëüòèñåðâèñíûé óçåë ñ îãðàíè÷åííûì äîñòóïîì. Ïðèåì çàÿâêè îñíîâàí íà àíàëèçå äàííûõ î ÷èñëå çàÿâîê ðàññìàòðèâàåìîãî ïîòîêà, íàõîäÿùèõñÿ íà îáñëóæèâàíèè. Ìîäåëü ïîçâîëÿåò ó÷åñòü îãðàíè÷åíèå ïî ïðè¼ìó çàÿâîê, îáóñëîâëåííîå èåðàðõè÷åñêèì ïðèíöèïîì ïîñòðîåíèÿ ñåòåé äîñòóïà. I Ìóëüòèñåðâèñíûé óçåë ñ îãðàíè÷åííûì ÷èñëîì ïîëüçîâàòåëåé óñëóã ñâÿçè. Èíòåðâàëû âðåìåíè ìåæäó ïîñòóïëåíèåì çàÿâîê èìåþò ýêñïîíåíöèàëüíîå ðàñïðåäåëåíèå ñ ïàðàìåòðîì, çàâèñÿùèì îò ÷èñëà îáñëóæèâàåìûõ çàÿâîê äàííîãî ïîòîêà. Ýòó ìîäåëü òàêæå íàçûâàþò ìóëüòèñåðâèñíîé ìîäåëüþ Ýíãñåòà I Ìóëüòèñåðâèñíûé óçåë ñ ðåçåðâèðîâàíèåì ðåñóðñà. Ïðèåì çàÿâêè îñíîâàí íà àíàëèçå çàíÿòîñòè ðåñóðñà ïåðåäà÷è èíôîðìàöèè. Ïðîöåäóðà ðåçåðâèðîâàíèÿ îáåñïå÷èâàåò ïîëüçîâàòåëÿ óñëóã ñâÿçè ãàðàíòèðîâàííûìè ïîêàçàòåëÿìè QoS. I Ïåðå÷åíü ìóëüòèñåðâèñíûõ ìîäåëåé óçëîâ äîñòóïà ìîæíî ðàñøèðèòü, åñëè ó÷åñòü âîçìîæíîñòü ãðóïïîâîãî ïîñòóïëåíèÿ çàÿâîê, íàëè÷èå ñâîéñòâà ýëàñòè÷íîñòè òðàôèêà äàííûõ, äîïóñòèìîñòü îæèäàíèÿ íà÷àëà îáñëóæèâàíèÿ, ïîâåäåíèå àáîíåíòà ïîñëå îòêàçà â îáñëóæèâàíèè è ò.ä. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 5 / 79 Ìóëüòèñåðâèñíûé óçåë äîñòóïà (1/4) I Ôóíêöèîíàëüíàÿ ìîäåëü îáñëóæèâàíèÿ ìóëüòèñåðâèñíîãî òðàôèêà íà ëèíèè êîíöåíòðàöèè àáîíåíòñêîé íàãðóçêè. Òðåáóåòñÿ íàéòè ñêîðîñòü ëèíèè. Çàäàíî îãðàíè÷åíèå íà äîëþ ïîòåðÿííûõ çàÿâîê. I Ðåñóðñ îáñëóæèâàíèÿ çàÿâîê  áèòîâàÿ ñêîðîñòü ïåðåäà÷è ëèíèè êîíöåíòðàöèè ìóëüòèñåðâèñíîãî òðàôèêà. Åäèíèöà ðåñóðñà (âèðòóàëüíûé êàíàë)  ìèíèìàëüíàÿ ïîòðåáíîñòü â ñêîðîñòè ïåðåäà÷è èíôîðìàöèè, íàïðèìåð, 64 êáèò/ñ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 6 / 79 Ìóëüòèñåðâèñíûé óçåë äîñòóïà (2/4) I Ìóëüòèñåðâèñíûé óçåë äîñòóïà óïðîùåííî ïðåäñòàâèì â âèäå ëèíèè ñî ñêîðîñòüþ ïåðåäà÷è èíôîðìàöèè C áèò/ñ. I Ëèíèÿ îáñëóæèâàåò ïóàññîíîâñêèé ïîòîê çàÿâîê îò n ñåðâèñíûõ ãðóïï. Ñ âåðîÿòíîñòüþ pk çàÿâêà ïðèíàäëåæèò k-é ãðóïïå, k = 1, . . . , n è òðåáóåò ck áèò/ñ. I Ïðèåì çàÿâêè k-ãî ïîòîêà îçíà÷àåò, ÷òî Pn s=1 is cs + ck ≤ C, ãäå is  ÷èñëî îáñëóæèâàåìûõ çàÿâîê s-ãî ïîòîêà. Поступающие заявки различаются требуемыми скоростью передачи и длительностью интервала времени обслуживания Скорость линии бит/с 1 I Äëÿ ïîñòðîåíèÿ ìîäåëè èìåþùèåñÿ è òðåáóåìûå ñêîðîñòè ïåðåäà÷è ïåðåâîäÿòñÿ â ôîðìàò åäèíèö ðåñóðñà ïåðåäà÷è (âèðòóàëüíûå êàíàëû, èñ÷èñëÿåìûå â êàíàëüíûõ åäèíèöàõ ê.å.) I Åäèíèöà ðåñóðñà c = ÍÎÄ(c1 , . . . , cn ). I Ñòðóêòóðíûå ïàðàìåòðû ëèíèè   lc m C k , bk = . v= c c Для обслуживания заявки -го потока требуется предоставить скорость k бит/с Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 7 / 79 Ìóëüòèñåðâèñíûé óçåë äîñòóïà (3/4) • Ïðèìåð îöåíêè åäèíèöû êàíàëüíîãî ðåñóðñà äëÿ ëèíèè êîíöåíòðàöèè ìóëüòèñåðâèñíîãî òðàôèêà ðåàëüíîãî âðåìåíè (Ñ=8 Ìáèò/c). Ñðåäíÿÿ. èíò. m (êáèò/c) 25 bk Ãîëîñîâàÿ ñâÿçü Ïèêîâàÿ èíò. h (êáèò/c) 64 (ê.å.) 1 Ýôôåêò. èíò. c (êáèò/c) 30 (ê.å.) 1 Âèäåî-êîíôåðåíöñâÿçü: MPEG-4 Âûñ. êà÷åñòâî MPEG-4 Íèçê. êà÷åñòâî H.263 Âûñ. êà÷åñòâî H.263 Ñðåä. êà÷åñòâî H.263 Íèçê. êà÷åñòâî 2000 1000 1400 320 84 400 90 256 64 16 32 16 22 5 2 1600 286 1000 105 20 54 10 34 4 1 k Óñëóãà 1 2 3 4 5 6 ×èñëî êàíàëîâ v 125 bk 266 • ×åì ìåíüøå çíà÷åíèå åäèíèöû êàíàëüíîãî ðåñóðñà, òåì òî÷íåå àïïðîêñèìàöèÿ ðåàëüíûõ ñêîðîñòåé ïåðåäà÷è èíôîðìàöèè.  ýòîé ñèòóàöèè â ìîäåëè ðàñòåò ÷èñëî êàíàëîâ, à, ñëåäîâàòåëüíî, è ñîñòîÿíèé, ÷òî óñëîæíÿåòñÿ åå ÷èñëåííûé àíàëèç. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 8 / 79 Ìóëüòèñåðâèñíûé óçåë äîñòóïà (4/4) I Ïîíÿòèå ýôôåêòèâíîé ñêîðîñòè ïåðåäà÷è èíôîðìàöèîííîãî ïîòîêà c ïîçâîëÿåò ðàññ÷èòàòü ìàêñèìàëüíî âîçìîæíîå ÷èñëî ñîåäèíåíèé îïðåäåë¼ííîãî âèäà ïðè ôèêñèðîâàííîé äîëå ïîòåðÿííûõ ïàêåòîâ. Âûïîëíÿåòñÿ ñîîòíîøåíèå: m ≤ c ≤ h. I Èñïîëüçóþòñÿ äâà ïîäõîäà ê îöåíêå ýòîé õàðàêòåðèñòèêè. Ïåðâûé  îñíîâàí íà ðåçóëüòàòàõ òåîðèè âåðîÿòíîñòåé. Îáîçíà÷èì ÷åðåç X(t) ñëó÷àéíûé ïðîöåññ ñî ñòàöèîíàðíûìè ïðèðàùåíèÿìè, êîòîðûé çàäà¼ò ÷èñëî ïàêåòîâ, ïîñòóïèâøèõ îò èñòî÷íèêà â èíòåðâàëå âðåìåíè [0, t]. Òîãäà c(s, t) = o n 1 log10 M es X(t) , st s > 0, t < ∞, ãäå s, t  ïàðàìåòðû èñòî÷íèêà èíôîðìàöèîííîé íàãðóçêè. I Âòîðîé ïîäõîä ýìïèðè÷åñêèé. Ïðèìåð åãî ðåàëèçàöèè ïðèâåäåí â òàáëèöå íà ñëàéäå 7. Îïðåäåëèì ïàðàìåòðû k1 , k2 èç ôîðìóë: k1 = − 2Ch log Ploss ; 1 k2 = 1 − 50 log Ploss . Òîãäà   
m h  k m 1 + 3 k 1 − , åñëè 3 k1 ≤ min(3, m );  1  2 h       
c= h k2 m 1 + 3 k12 1 − m , åñëè 3 < 3 k12 ≤ m ;   h       k2 h â îñòàëüíûõ ñëó÷àÿõ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 9 / 79 Ìóëüòèñåðâèñíûé òðàôèê â ñîòå ñåòè ñòàíäàðòà UMTS (1/4) I  îñíîâå ñåòåé ñòàíäàðòà UMTS ëåæèò èñïîëüçîâàíèå øèðîêîïîëîñíîãî ìíîæåñòâåííîãî äîñòóïà ñ êîäîâûì ðàçäåëåíèåì êàíàëîâ. I Çàÿâêà ïðèíèìàåòñÿ, åñëè ñóììàðíûé óðîâåíü ìîùíîñòè ñèãíàëîâ îò âñåõ àáîíåíòîâ ðàññìàòðèâàåìîé è ñîñåäíèõ ñîò, âêëþ÷àÿ òåïëîâîé øóì, à òàêæå ìîùíîñòü ñèãíàëà, íåîáõîäèìîãî äëÿ ïðåäîñòàâëåíèÿ çàêàçàííîãî ñåðâèñà, íå ïðåâûñÿò ïðåäåëüíî äîïóñòèìîãî óðîâíÿ, çàëîæåííîãî íà ñòàäèè ïðîåêòèðîâàíèÿ. I Èç ïðèâåäåííîãî îáñóæäåíèÿ ñëåäóåò, ÷òî äëÿ ñåòåé UMTS è äðóãèõ ïîäîáíûõ åé ñèñòåì ñîòîâîé ñâÿçè îáùèì ðåñóðñîì ÿâëÿåòñÿ ìàêñèìàëüíî âîçìîæíûé êîýôôèöèåíò çàãðóçêè ïåðåäàòî÷íîãî ðåñóðñà ñîòû àáîíåíòàìè äàííîé ñîòû è ñîñåäíèõ ñîò, îãðàíè÷åííûé óñëîâèåì äîñòîâåðíîñòè ïåðåäà÷è èíôîðìàöèè Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 10 / 79 Ìóëüòèñåðâèñíûé òðàôèê â ñîòå ñåòè ñòàíäàðòà UMTS (2/4) I  UMTS ïðîöåññ ïðåäîñòàâëåíèÿ k-ãî ñåðâèñà õàðàêòåðèçóåòñÿ âåëè÷èíîé (Eb /N0 )k , êîòîðóþ òðåáóåòñÿ ïîääåðæèâàòü äëÿ îáåñïå÷åíèÿ íåîáõîäèìîãî óðîâíÿ èíòåíñèâíîñòè ïîòåðÿííûõ áèò BER. I Ôîðìàëüíî ýòî îòíîøåíèå ýíåðãèè ñèãíàëà, ïðèõîäÿùåéñÿ íà îäèí áèò ïðèíèìàåìîãî èíôîðìàöèîííîãî ïîòîêà  (Eb ), ê ýíåðãåòè÷åñêîé ñïåêòðàëüíîé ïëîòíîñòè øóìà  (N0 )   Eb W Pk = · N0 k νk Rk It − Pk I Çäåñü: • W = 3,84 Ìchps  ñêîð. ïåðåäà÷è ýëåì. ñèìâîëîâ ðàäèîêàíàëà UMTS; • Pk  ñðåäíåå çíà÷åíèå óðîâíÿ ñèãíàëà îò òåðìèíàëà ïîëüçîâàòåëÿ, çàêàçàâøåãî k-é ñåðâèñ, èçìåðåííîãî íà áàçîâîé ñòàíöèè; • νk  êîýôô. àêòèâíîñòè ïîëüçîâàòåëÿ (äàííûå  νk = 1, ðå÷ü νk = 0,67); • Rk  òðåáóåìàÿ ñêîðîñòü ïåðåäà÷è èíôîðìàöèè (áèò/ñ); • It  ñóììàðíîå çíà÷åíèå óðîâíÿ ñèãíàëà, ïîëó÷åííîãî íà áàçîâîé ñòàíöèè. I Ïàðàìåòð (Eb /N0 )k èìååò áîëüøîå çíà÷åíèå ïðè ïëàíèðîâàíèè ðàäèîñåòåé, ïîñêîëüêó ñâÿçûâàåò õàðàêòåðèñòèêè óñòàíàâëèâàåìîãî ñîåäèíåíèÿ ñ ïîêàçàòåëÿìè ýôôåêòèâíîñòè ñîâìåñòíîé ïåðåäà÷è èíôîðìàöèè â ñîòå. Îí îöåíèâàåòñÿ íà îñíîâå äàííûõ èçìåðåíèé, èìèòàöèîííîãî ìîäåëèðîâàíèÿ è ðåêîìåíäàöèé 3GPP. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 11 / 79 Ìóëüòèñåðâèñíûé òðàôèê â ñîòå ñåòè ñòàíäàðòà UMTS (3/4) I Îáîçíà÷èì ÷åðåç ηk = Pk It äîëþ ñèãíàëà, ïîëó÷àåìîãî íà áàçîâîé ñòàíöèè, îò îäíîãî èç ïîëüçîâàòåëåé k-ãî ñåðâèñà. Äëÿ åå îáîçíà÷åíèÿ ïðèìåíÿåòñÿ òåðìèí êîýôôèöèåíò çàãðóçêè (àíãë. load factor). Èç îïðåäåëåíèÿ (Eb /N0 )k ïîëó÷àåì ñîîòíîøåíèå äëÿ îöåíêè ηk ÷åðåç çíà÷åíèÿ âõîäíûõ ïàðàìåòðîâ ηk = 1 1+  E W b N0 k ν k Rk I Îáîçíà÷èì ÷åðåç ηU L = 0,5 − 0,8 ìàêñèìàëüíî âîçìîæíûé êîýôôèöèåíò çàãðóçêè ïåðåäàòî÷íîãî ðåñóðñà P ñîòû âñåìè ïîëüçîâàòåëÿìè. Îãðàíè÷åíèå íà ïðèåì çàÿâêè k-ãî ïîòîêà èìååò âèä n s=1 is ηs + ηk ≤ ηU L . I  êà÷åñòâå åäèíèöû ðåñóðñà ïåðåäà÷è èíôîðìàöèè âûáåðåì çíà÷åíèå η = ÍÎÄ(η1 , . . . , ηn ). I Âåëè÷èíà êàíàëüíîãî ðåñóðñà ñîòû v è òðåáîâàíèå ê ÷èñëó êàíàëüíûõ åäèíèö äëÿ îáñëóæèâàíèÿ k-ãî ñåðâèñà bk îïðåäåëÿþòñÿ èç ñîîòíîøåíèé     ηU L ηk v= , bk = . η η Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 12 / 79 Ìóëüòèñåðâèñíûé òðàôèê â ñîòå ñåòè ñòàíäàðòà UMTS (4/4) • Ïðèìåð îöåíêè åäèíèöû êàíàëüíîãî ðåñóðñà îáðàòíîãî êàíàëà ñîòû ñåòè UMTS. Ïðåäïîëîæèì, ÷òî ηU L = 0,5. Òîãäà η = 0,00175; ηU L = 0,5; v = 285 ê.å. j Óñëóãà Rk νk (êáèò/c)  Eb N0  (äÁ) k  Eb N0  k ηk bk (ê.å.) 1 Ãîëîñ 7,95 0,67 4 2,51 0,0035 2 2 Ãîëîñ (ïîäâ.) 7,95 0,67 7 5,01 0,0069 4 3 Ãîëîñ 12,2 0,67 4 2,51 0,053 3 4 Äàííûå 16 1 3 2,00 0,0083 5 5 Äàííûå 32 1 3 2,00 0,016 10 6 Äàííûå 64 1 2 1,58 0,025 15 7 Äàííûå 144 1 1,5 1,41 0,050 30 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 13 / 79 Ïðèìåíåíèå ìîäåëè I Ìîäåëü ìóëüòèñåðâèñíîãî óçëà äîñòóïà èñïîëüçóåòñÿ: • äëÿ àíàëèçà çàâèñèìîñòè õàðàêòåðèñòèê êà÷åñòâà îáñëóæèâàíèÿ ïîñòóïàþùèõ çàÿâîê îò ïàðàìåòðîâ âîçíèêàþùèõ èíôîðìàöèîííûõ ïîòîêîâ è óñëîâèé äîïóñêà çàÿâîê ê çàíÿòèþ ðåñóðñà; • äëÿ àíàëèçà äåéñòâèÿ ðàçíîãî ðîäà ïðîöåäóð, íàïðàâëåííûõ íà ïîâûøåíèå ýôôåêòèâíîñòè èñïîëüçîâàíèÿ ðåñóðñà ïåðåäà÷è ëèíèè äîñòóïà (ïðèìåíåíèå ïàêåòíûõ òåõíîëîãèé ïåðåäà÷è èíôîðìàöèè, èñïîëüçîâàíèå ïðîöåäóðû ìóëüòèïëåêñèðîâàíèÿ è ò.ä.); • äëÿ îöåíêè òðåáóåìîé ïî íàãðóçêå è êà÷åñòâó îáñëóæèâàíèÿ ñêîðîñòè ëèíèè äîñòóïà è ðåøåíèÿ äðóãèõ ïîäîáíûõ ýòîé çàäà÷, íàïðèìåð, äëÿ îöåíêè ìàêñèìàëüíîãî îáúåìà òðàôèêà, êîòîðûé ìîæåò áûòü îáñëóæåí ñ òðåáóåìûì êà÷åñòâîì íà ëèíèè äîñòóïà ñ ôèêñèðîâàííîé ñêîðîñòüþ ïåðåäà÷è èíôîðìàöèè. I Äëÿ ïîñòðîåíèÿ ìóëüòèñåðâèñíîé ìîäåëè ëèíèè îñòàëîñü óêàçàòü ïðîöåäóðû ôîðìèðîâàíèÿ èíòåðâàëîâ âðåìåíè ìåæäó ïîñòóïëåíèåì çàÿâîê è äëèòåëüíîñòåé èõ îáñëóæèâàíèÿ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà Ñòðóêòóðà è ñâîéñòâà ìóëüòèñåðâèñíîé ìîäåëè Ýðëàíãà Передаточный ресурс линии в канальных единицах Потоки заявок на предоставление канального ресурса от бесконечных групп пользователей Характеристика поступления заявок 1, 1, 1/ Тип трафика 1 1 1 2 , n , 1/ Отличительные свойства Сервисы реального времени Тип модели Мультисервисный аналог модели Эрланга Область использования Расчёт пропускной способности мультисервисных линий концентрации абонентского трафика Ìîäåëü ïîñòóïëåíèÿ è îáñëóæèâàíèÿ çàÿâîê k-ãî ïîòîêà, k = 1, . . . , n: • ïîñòóïëåíèå çàÿâîê ïîä÷èíÿåòñÿ çàêîíó Ïóàññîíà ñ èíòåíñèâíîñòüþ λk ; • âðåìÿ îáñëóæèâàíèÿ çàÿâêè ðàñïðåäåëåíî ýêñïîíåíöèàëüíî ñî ñðåäíèì 1/µk ; • äëÿ îáñëóæèâàíèÿ çàÿâêè îäíîâðåìåííî òðåáóåòñÿ bk åäèíèö ðåñóðñà; • çàÿâêà ïðèíèìàåòñÿ ê îáñëóæèâàíèþ, åñëè i1 b1 + . . . + in bn + bk ≤ v . 14 / 79 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 15 / 79 Ìàðêîâñêèé ïðîöåññ, îïèñûâàþùèé ôóíêöèîíèðîâàíèå ìîäåëè I Ïðîñòðàíñòâî ñîñòîÿíèé. Äîñòàòî÷íîñòü ðåñóðñà ëèíèè îöåíèì äîëåé ïîòåðÿííûõ çàÿâîê, à ýôôåêòèâíîñòü åãî èñïîëüçîâàíèÿ  ñðåäíèì ÷èñëîì çàíÿòûõ åäèíèö ðåñóðñà. Äëÿ îöåíêè ýòèõ õàðàêòåðèñòèê äîñòàòî÷íî çíàòü äîëþ âðåìåíè ïðåáûâàíèÿ ëèíèè â ñîñòîÿíèè ñ èçâåñòíûì ÷èñëîì çàÿâîê êàæäîãî ïîòîêà, íàõîäÿùèõñÿ íà îáñëóæèâàíèè. Âûáîð õàðàêòåðèñòèê îïðåäåëÿåò ñîñòîÿíèå ìîäåëè â âèäå âåêòîðà (i1 , . . . , in ), ãäå ik  ÷èñëî îáñëóæèâàåìûõPçàÿâîê k-ãî ïîòîêà. Çíà÷åíèÿ ik îãðàíè÷åíû ïðîïóñêíîé ñïîñîáíîñòüþ ëèíèè n k=1 ik bk ≤ v. Âåêòîðû (i1 , . . . , in ), óäîâëåòâîðÿþùèå ïðèâåäåííîìó íåðàâåíñòâó, îïðåäåëÿþò ïðîñòðàíñòâî S ñîñòîÿíèé ìîäåëè. I Ìàðêîâñêèé ïðîöåññ. Äèíàìèêà èçìåíåíèÿ ñîñòîÿíèé ìîäåëè âî âðåìåíè îïèñûâàåòñÿ ñëó÷àéíûì ïðîöåññîì r(t) = (i1 (t), . . . , in (t)), ãäå ik (t)  ÷èñëî çàÿâîê k-ãî ïîòîêà, íàõîäÿùèõñÿ â ìîìåíò t íà îáñëóæèâàíèè. Ïðîöåññ r(t) áóäåò ìàðêîâñêèì, ïîñêîëüêó ïîñòðîåí â ñîîòâåòñòâèè ñ ïîëîæåíèÿìè êîíñòðóêòèâíîãî îïðåäåëåíèÿ ìàðêîâñêîãî ïðîöåññà. I Ãðàíèöû âñïîìîãàòåëüíûõ ìíîæåñòâ ñîñòîÿíèé. Îáîçíà÷èì ÷åðåç Uk ìíîæåñòâî ñîñòîÿíèé (i1 , . . . , in ) ∈ S , óäîâëåòâîðÿþùèõ óñëîâèþ i1 b1 + . . . + in bn + bk > v .  êàæäîì èç ñîñòîÿíèé ìíîæåñòâà Uk ïîñòóïèâøàÿ çàÿâêà k-ãî ïîòîêà ïîëó÷àåò îòêàç. Ïóñòü Si ⊂ S  ìíîæåñòâî ñîñòîÿíèé òàêèõ, ÷òî i1 b1 + . . . + in bn = i.  êàæäîì èç ñîñòîÿíèé ìíîæåñòâà Si çàíÿòî i åäèíèö ðåñóðñà. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 16 / 79 Ïðèìåð îöåíêè ñòðóêòóðíûõ ïàðàìåòðîâ ìîäåëè (1/8) I Íà ëèíèè ñî ñêîðîñòüþ C = 10 Ìáèò/ñ îðãàíèçîâàíà ñîâìåñòíàÿ ïåðåäà÷à äâóõ ïîòîêîâ âèäåîñîîáùåíèé: ñðåäíåãî è óëó÷øåííîãî êà÷åñòâà. Òðåáîâàíèÿ ê ñêîðîñòè ïåðåäà÷è ñîîòâåòñòâåííî c1 = 2 Ìáèò/ñ è c2 = 4 Ìáèò/ñ. i1 i2 Ç. ê. Ñâ. ê. 5 1 2 3 2 4 1 I Ñòðóêòóðíûå ïàðàìåòðû ìîäåëè: c = ÍÎÄ(2,4) = 2 Ìáèò/ñ; = 5 ê.å.; v = 10 2 n = 2; b1 = 1 ê.å.; b2 = 2 ê.å. 1 1 4 1 1 3 2 1 2 5 2 2 3 I Ïàðàìåòðû ïîñòóïëåíèÿ è 2 1 4 1 3 3 2 3 1 5 4 4 1 5 5 I Âûäåëåííûé ðåñóðñ íå ìåíÿåòñÿ çà âðåìÿ îáñëóæèâàíèÿ çàÿâêè. îáñëóæèâàíèÿ çàÿâîê: λ1 = 2 çàÿâ./åä.âð.; λ2 = 1 çàÿâ./åä.âð.; 1/µ1 = 1 åä.âð.; 1/µ2 = 1 åä.âð. I Ñîñòîÿíèÿ ïåðå÷èñëåíû â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå. Ñ ó÷åòîì îãðàíè÷åíèÿ íà îáùåå ÷èñëî êàíàëîâ îí çàäàåòñÿ ðåêóðñèåé j ki1 = 0, 1, . . . , 5; 1 i2 = 0, 1, . . . , 5−i . 2 U1 U2 + + + + + + + + + Si S0 S2 S4 S1 S3 S5 S2 S4 S3 S5 S4 S5 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 17 / 79 Ïðèìåð ïîñòðîåíèÿ âñïîìîãàòåëüíûõ ïîäìíîæåñòâ ñîñòîÿíèé (2/8) • Âèä è ñîîòíîøåíèå ìåæäó ìíîæåñòâàìè ñîñòîÿíèé S , U1 è U2 (ëåâàÿ ÷àñòü ðèñóíêà) è S , Si , i = 0, 1, 2, 4, 5 (ïðàâàÿ ÷àñòü ðèñóíêà). Ñâîéñòâà ìíîæåñòâ Uk I Ìíîæåñòâî Uk ôîðìèðóåòñÿ èç ñîñòîÿíèé (i1 , . . . , in ) ∈ S äëÿ âñåõ ìàêñèìàëüíî âîçìîæíûõ çíà÷åíèé ik ïðè ôèêñèðîâàííûõ çíà÷åíèÿõ îñòàëüíûõ êîìïîíåíò ñîñòîÿíèÿ i1 , . . . , ik−1 , ik+1 , . . . , in . I Ìíîæåñòâî Uk ìîæåò áûòü ïîëó÷åíî êàê îáúåäèíåíèå ìíîæåñòâ Si äëÿ S i = v − bk + 1, . . . , v .  ðàññìîòðåííîì ñëó÷àå U1 = S5 , U2 = S5 S4 . Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 18 / 79 Ïîêàçàòåëè êà÷åñòâà îáñëóæèâàíèÿ çàÿâîê I Îáîçíà÷èì ÷åðåç p(i1 , . . . , in ) ñòàöèîíàðíóþ âåðîÿòíîñòü ñîñòîÿíèÿ (i1 , . . . , in ). Îíà èìååò èíòåðïðåòàöèþ äîëè âðåìåíè ïðåáûâàíèÿ r(t) â (i1 , . . . , in ). Ýòî ñâîéñòâî ïîçâîëÿåò èñïîëüçîâàòü p(i1 , . . . , in ) äëÿ îöåíêè õàðàêòåðèñòèê ìîäåëè. I Êà÷åñòâî îáñëóæèâàíèÿ çàÿâîê k-ãî ïîòîêà îïðåäåëèì äîëåé ïîòåðÿííûõ çàÿâîê πk . Äëÿ âû÷èñëåíèå πk âîñïîëüçóåìñÿ ñâîéñòâîì PASTA, êîòîðîå ïîçâîëÿåò îöåíèòü πk ñ ïîìîùüþ âûðàæåíèÿ X πk = p(i1 , . . . , in ). (i1 ,...,in )∈Uk I Çàãðóçêó ðåñóðñà îáñëóæèâàíèåì çàÿâîê k-ãî ïîòîêà îöåíèì ñðåäíèì ÷èñëîì çàíÿòûõ êàíàëüíûõ åäèíèö mk . Ïî îïðåäåëåíèþ, X mk = p(i1 , . . . , in )ik bk . (i1 ,...,in )∈S I Îáîçíà÷èì ÷åðåç yk ñðåäíåå ÷èñëî çàÿâîê k-ãî ïîòîêà, íàõîäÿùèõñÿ íà îáñëóæèâàíèè. Ñïðàâåäëèâî ñîîòíîøåíèå yk = mk /bk . I Äëÿ îöåíêè ââåäåííûõ õàðàêòåðèñòèê íåîáõîäèìî ðàññ÷èòàòü âåðîÿòíîñòè ñòàöèîíàðíûõ ñîñòîÿíèé p(i1 , . . . , in ). Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 19 / 79 Ñèñòåìà óðàâíåíèé ðàâíîâåñèÿ (ÑÓÐ) I Âñå óðàâíåíèÿ ÑÓÐ ìàðêîâñêîé ìîäåëè ñ ïðîñòðàíñòâîì ñîñòîÿíèé S ìîãóò áûòü ïðåäñòàâëåíû â âèäå îäíîãî ñîîòíîøåíèÿ, ñïðàâåäëèâîãî äëÿ âñåõ (x) ∈ S X   Ïàðàìåòð ýêñï. ðàñïð. âðåìåíè äî îñóùåñòâëåíèÿ Ex × I Ex = P (x) Ïî âñåì ñîáûòèÿì Ex , ìåíÿþùèì ñîñòîÿíèå (x) = X (y)∈S\(x) X P (y)   Ïàðàìåòð ýêñï. ðàñïð. âðåìåíè äî îñóùåñòâëåíèÿ Ey ×I Ey . Ïî âñåì ñîáûòèÿì Ey , âåäóùèì ê ïåðåõîäó èç (y) â (x) I Äëÿ ìóëüòèñåðâèñíîé ìîäåëè Ýðëàíãà ýòî ïîëîæåíèå ïðèâîäèò ê ðàâåíñòâó: n   X P (i1 , . . . , in ) λk I(i + bk ≤ v) + ik µk I(ik > 0) = k=1 = + n X k=1 n X k=1 P (i1 , . . . , ik − 1, . . . , in )λk I(ik > 0)+ P (i1 , . . . , ik + 1, . . . , in )(ik + 1)µk I(i + bk ≤ v), ãäå (i1 , . . . , in ) ∈ S , çíà÷åíèå i = i1 b1 + . . . + in bn ïðåäñòàâëÿåò èç ñåáÿ ðåñóðñ, çàíÿòûé â ñîñòîÿíèè (i1 , . . . , in ), à I(·)  èíäèêàòîðíàÿ ôóíêöèÿ ñîáûòèÿ. Îíà îòñåèâàåò íåñóùåñòâóþùèå ñîñòîÿíèÿ è ñîáûòèÿ, êîòîðûå íå ïðèâîäÿò ê òðåáóåìûì èçìåíåíèÿì ñîñòîÿíèÿ. Âåðîÿòíîñòè P (i1 , . . . , in ) íîðìèðóþòñÿ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 20 / 79 Ïðèìåð ñîñòàâëåíèÿ äèàãðàììû ïåðåõîäîâ (3/8) 1 0,2 1,2 1 2 2 2 2 1 1,1 2,1 1 2 1 1 0,1 2 2 2 1 0,0 1 2 2 1 1,0 1 3,1 1 2 1 2,0 1 2 1 1 3,0 1 4,0 1 5,0 1 Îñîáåííîñòè ñîñòàâëåíèÿ ñèñòåìû óðàâíåíèé ðàâíîâåñèÿ I Èíòåíñèâíîñòü îêîí÷àíèÿ îáñëóæèâàíèÿ çàÿâîê îäíîãî ïîòîêà ïðîïîðöèîíàëüíà èõ ÷èñëó. I Ïîñòóïëåíèå çàÿâîê è èõ îáñëóæèâàíèå îáû÷íî ïðèâîäÿò ê âçàèìîîáðàòíûì ïåðåõîäàì. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 21 / 79 Ïðèìåð ñîñòàâëåíèÿ ñèñòåìû óðàâíåíèé ðàâíîâåñèÿ (4/8) I ÑÓÐ äëÿ ðàññìàòðèâàåìîãî ïðèìåðà ìóëüòèñåðâèñíîãî óçëà èìååò 12 óðàâíåíèé â ñîîòâåòñòâèè ñ ÷èñëîì ñîñòîÿíèé
P (0, 0) · λ1 + λ2 = P (1, 0) µ1 + P (0, 1) µ2 ;
P (0, 1) · λ1 + λ2 + µ2 = P (0, 0) λ2 + P (1, 1) µ1 + P (0, 2) 2 µ2 ;
P (0, 2) · λ1 + 2 µ2 = P (0, 1) λ2 + P (1, 2) µ1 ;
P (1, 0) · λ1 + λ2 + µ1 = P (0, 0) λ1 + P (2, 0) 2 µ1 + P (1, 1) µ2 ;
P (1, 1) · λ1 + λ2 + µ1 + µ2 = P (0, 1) λ1 + P (1, 0) λ2 + P (2, 1) 2 µ1 + P (1, 2) 2 µ2 ;
P (1, 2) · µ1 + 2 µ2 = P (0, 2) λ1 + P (1, 1) λ2 ;
P (2, 0) · λ1 + λ2 + 2 µ1 = P (1, 0) λ1 + P (3, 0) 3 µ1 + P (2, 1) µ2 ;
P (2, 1) · λ1 + 2 µ1 + µ2 = P (1, 1) λ1 + P (2, 0) λ2 + P (3, 1) 3 µ1 ;
P (3, 0) · λ1 + λ2 + 3 µ1 = P (2, 0) λ1 + P (4, 0) 4 µ1 + P (3, 1) µ2 ;
P (3, 1) · 3 µ1 + µ2 = P (2, 1) λ1 + P (3, 0) λ2 ;
P (4, 0) · λ1 + 4 µ1 = P (3, 0) λ1 + P (5, 0) 5 µ1 ; P (5, 0) · 5 µ1 = P (4, 0) λ1 . I Âûïîëíÿåòñÿ óñëîâèå íîðìèðîâêè P P (i1 , i2 ) = 1. (i1 ,i2 )∈S I Ñ ðîñòîì ÷èñëà ïîòîêîâ êîëè÷åñòâî óðàâíåíèé íà÷èíàåò ðàñòè áûñòðûìè òåìïàìè, ÷òî çàòðóäíÿåò ðåøåíèå ÑÓÐ ñòàíäàðòíûìè ÷èñëåííûìè ìåòîäàìè. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 22 / 79 Ñâîéñòâî ìóëüòèïëèêàòèâíîñòè I Äëÿ ìóëüòèñåðâèñíîé ìîäåëè Ýðëàíãà âûïîëíÿåòñÿ ñîîòíîøåíèå p(i1 , . . . , in ) = ai1 1 ainn × 1 ··· , N i1 ! in ! (i1 , . . . , in ) ∈ S. I  ïðèâåä¼ííîì ðàâåíñòâå ak = λk /µk  èíòåíñèâíîñòü ïðåäëîæåííîãî òðàôèêà k-ãî ïîòîêà. Îíà îïðåäåëÿåò ïîòåíöèàëüíîå ÷èñëî ñîåäèíåíèé ïðè îáñëóæèâàíèè çàÿâîê k-ãî ïîòîêà è èçìåðÿåòñÿ â ýðëàíãàõ. Èç âûðàæåíèÿ äëÿ ak òàêæå ñëåäóåò, ÷òî ak  ñðåäíåå ÷èñëî ïîñòóïëåíèé çàÿâîê k-ãî ïîòîêà çà ñðåäíåå âðåìÿ îáñëóæèâàíèÿ îäíîé çàÿâêè. Äàëåå ýòî âðåìÿ áóäåò ïðèíÿòî çà åäèíèöó è îòäåëüíî â ìîäåëè íå ðàññìàòðèâàåòñÿ. I Ñèìâîë N îáîçíà÷àåò íîðìèðîâî÷íóþ êîíñòàíòó N = i P (i1 ,...,in )∈S a11 i1 ! ··· ainn in ! . I Ìóëüòèïëèêàòèâíîå ñîîòíîøåíèå è ðåçóëüòàòû, ïîëó÷åííûå íà åãî îñíîâå, íå çàâèñÿò îò âèäà ôóíêöèè ðàñïðåäåëåíèÿ âðåìåíè îáñëóæèâàíèÿ çàÿâêè. Ýòî ñóùåñòâåííî ðàñøèðÿåò îáëàñòü ïðèìåíåíèÿ ïîëó÷åííûõ ðàñ÷åòíûõ âûðàæåíèé. I Äîêàçàòåëüñòâî ñôîðìóëèðîâàííîãî óòâåðæäåíèÿ îñóùåñòâëÿåòñÿ àïïðîêñèìàöèåé ôóíêöèè ðàñïðåäåëåíèÿ ñìåñüþ ýðëàíãîâñêèõ ðàñïðåäåëåíèé èëè ðàñïðåäåëåíèé ôàçîâîãî òèïà, à äëÿ íèõ ñïðàâåäëèâîñòü ìóëüòèïëèêàòèâíûõ ñîîòíîøåíèé äîêàçûâàåòñÿ ïðåîáðàçîâàíèåì ñèñòåìû óðàâíåíèé ðàâíîâåñèÿ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 23 / 79 Äîêàçàòåëüñòâî ñâîéñòâà ìóëüòèïëèêàòèâíîñòè (1/4) I Âíà÷àëå óñòàíîâèì ñâîéñòâî ìóëüòèïëèêàòèâíîñòè â ñèòóàöèè, êîãäà v = ∞. Ïóñòü ik (t)  ÷èñëî îáñëóæèâàåìûõ â ìîìåíò t çàÿâîê k-ãî ïîòîêà, k = 1, . . . , n; r̂(t) = (i1 (t), . . . , in (t))  ñëó÷àéíûé ïðîöåññ, îïèñûâàþùèé èçìåíåíèå ñîñòîÿíèé ìîäåëè, à p̂(i1 , . . . , in )  ñòàöèîíàðíûå âåðîÿòíîñòè (i1 , . . . , in ). Ïîñêîëüêó ðåñóðñ íåîãðàíè÷åí, òî ik (t) íå çàâèñÿò äðóã îò äðóãà è ìîãóò àíàëèçèðîâàòüñÿ îòäåëüíî. I Îáîçíà÷èì ÷åðåç Pk (ik ) ñòàöèîíàðíóþ âåðîÿòíîñòü ñîñòîÿíèÿ (ik ) ïðîöåññà ik (t). Çäåñü (ik )  ÷èñëî îáñëóæèâàåìûõ çàÿâîê k-ãî ïîòîêà. Íåòðóäíî ïîêàçàòü, ÷òî Pk (ik ) ñâÿçàíû òàê íàçûâàåìûìè ñîîòíîøåíèÿìè äåòàëüíîãî áàëàíñà Pk (ik ) λk = Pk (ik + 1) (ik + 1) µk , ik = 0, 1, . . . ; k = 1, . . . , n, èç êîòîðûõ ñëåäóþò ôîðìóëû äëÿ îöåíêè pk (ik ), èìåþùèå âèä: i pk (ik ) = e−ak × akk ik ! , ãäå ak = λk , ik = 0, 1, . . . ; µk k = 1, . . . , n. I Èç ýòîé ôîðìóëû ñëåäóåò ñâîéñòâî ìóëüòèïëèêàòèâíîñòè äëÿ ñòàöèîíàðíûõ âåðîÿòíîñòåé p̂(i1 , . . . , in ) ìîäåëè ñ íåîãðàíè÷åííûì ðåñóðñîì − p̂(i1 , . . . , in ) = p1 (i1 ) · · · pn (in ) = e ik = 0, 1, . . . ; k = 1, . . . , n. n P k=1 ak ai11 ainn ··· , i1 ! in ! Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 24 / 79 Äîêàçàòåëüñòâî ñâîéñòâà ìóëüòèïëèêàòèâíîñòè (2/4) I Óñòàíîâèì ñâîéñòâî ìóëüòèïëèêàòèâíîñòè â ñèòóàöèè, êîãäà v < ∞. Ðåøèòü ýòó çàäà÷ó ïîìîãóò ñâîéñòâà îáðàòèìûõ ìàðêîâñêèõ ïðîöåññîâ. Ñôîðìóëèðóåì íåñêîëüêî òåîðåòè÷åñêèõ ïîëîæåíèé, îòíîñÿùèõñÿ ê ýòè ïðîöåññàì. I Ìàðêîâñêèé ïðîöåññ îáëàäàåò ñâîéñòâîì îáðàòèìîñòè, åñëè äëÿ åãî ëþáûõ äâóõ ñîñòîÿíèé (i), (j) âûïîëíÿåòñÿ ñîîòíîøåíèå äåòàëüíîãî áàëàíñà πi λi,j = πj λj,i . I  ïðèâåäåííîì âûðàæåíèè πi  ñòàöèîíàðíàÿ âåðîÿòíîñòü ñîñòîÿíèÿ (i), λi,j  ïàðàìåòð ýêñïîíåíöèàëüíîãî ðàñïðåäåëåíèÿ âðåìåíè äî ïåðåõîäà èç ñîñòîÿíèÿ (i) â ñîñòîÿíèå (j), πi λi,j  ñðåäíåå ÷èñëî ïåðåõîäîâ â åäèíèöó âðåìåíè èç (i) â (j). I Ñïðàâåäëèâî óòâåðæäåíèå. Åñëè äëÿ ìàðêîâñêîãî ïðîöåññà êàêèì-òî îáðàçîì óäàëîñü íàéòè çíà÷åíèÿ πi , óäîâëåòâîðÿþùèå ñîîòíîøåíèÿì äåòàëüíîãî áàëàíñà, òî âåëè÷èíû πi òàêæå áóäóò è ñòàöèîíàðíûìè âåðîÿòíîñòÿìè ýòîãî ïðîöåññà. Óòâåðæäåíèå äîêàçûâàåòñÿ ïîäñòàíîâêîé ñîîòíîøåíèé äåòàëüíîãî áàëàíñà â ñèñòåìó óðàâíåíèé ðàâíîâåñèÿ è ïðîâåðêîé ïîëó÷àåìîãî òîæäåñòâà. I Ïðèìåíèì ñôîðìóëèðîâàííîå ïîëîæåíèå è óãàäàåì âèä ñòàöèîíàðíûõ âåðîÿòíîñòåé äëÿ èññëåäóåìîé ìîäåëè. Äëÿ ýòîãî äîñòàòî÷íî âîñïîëüçîâàòüñÿ ðåçóëüòàòàìè, ïîëó÷åííûìè äëÿ ìîäåëè ñ íåîãðàíè÷åííûì ðåñóðñîì. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà Äîêàçàòåëüñòâî ñâîéñòâà ìóëüòèïëèêàòèâíîñòè (3/4) I Èç ðåçóëüòàòîâ àíàëèçà ïðîöåññà r̂(t), îïèñûâàþùåãî ìîäåëü ñ íåîãðàíè÷åííûì ðåñóðñîì, ñëåäóåò, ÷òî îí îáëàäàåò ñâîéñòâîì îáðàòèìîñòè. , I Îáîçíà÷èì ÷åðåç Ω ïðîñòðàíñòâî ñîñòîÿíèé r̂(t) è ïðåäñòàâèì Ω â âèäå Ω = S + S̄ , ãäå S  ïðîñòðàíñòâî ñîñòîÿíèé ìîäåëè ñ îãðàíè÷åííûì ðåñóðñîì. I Ïåðåîïðåäåëèì ïðîöåññ r̂(t) ïîëîæèâ ðàâíûìè íóëþ èíòåíñèâíîñòè ïåðåõîäîâ èç ñîñòîÿíèé, ïðèíàäëåæàùèõ S â ñîñòîÿíèÿ, ïðèíàäëåæàùèå S̄ . I Ïîëó÷àåìûé òàêèì îáðàçîì ïðîöåññ ñîâïàäàåò ñ r(t). Ýòà îïåðàöèÿ íàçûâàåòñÿ óðåçàíèåì ïðîñòðàíñòâà ñîñòîÿíèé Ω, ïðèíèìàåìûõ r̂(t), äî ðàçìåðîâ S . Îíà ÷àñòî ïðèìåíÿåòñÿ â òåîðèè òåëåòðàôèêà. , , , 25 / 79 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 26 / 79 Äîêàçàòåëüñòâî ñâîéñòâà ìóëüòèïëèêàòèâíîñòè (4/4) I Ðàññìîòðèì âåëè÷èíû p̂(i1 , . . . , in ) P , p̂(i1 , . . . , in ) f (i1 , . . . , in ) = (i1 , . . . , in ) ∈ S. (i1 ,...,in )∈S I Íåòðóäíî ïðîâåðèòü, ÷òî äëÿ çíà÷åíèé f (i1 , . . . , in ) âûïîëíÿþòñÿ ñîîòíîøåíèÿ äåòàëüíîãî áàëàíñà, ñôîðìóëèðîâàííûå äëÿ ïðîöåññà r(t). Ñëåäîâàòåëüíî, äëÿ âñåõ (i1 , . . . , in ) ∈ S âûïîëíÿåòñÿ ðàâåíñòâî f (i1 , . . . , in ) = p(i1 , . . . , in ) è r(t) îáðàòèì. I Ïîäñòàâèâ â ôîðìóëó äëÿ f (i1 , . . . , in ) ïîëó÷åííîå ðàííåå âûðàæåíèå äëÿ p̂(i1 , . . . , in ), óáåæäàåìñÿ â íàëè÷èè ñâîéñòâà ìóëüòèïëèêàòèâíîñòè äëÿ ñòàöèîíàðíûõ âåðîÿòíîñòåé ñîñòîÿíèé ìóëüòèñåðâèñíîé ìîäåëè Ýðëàíãà p(i1 , . . . , in ) = ai1 ainn 1 × 1 ··· , N i1 ! in ! (i1 , . . . , in ) ∈ S. I Äëÿ ìîíîñåðâèñíîé ìîäåëè èç ñâîéñòâà ìóëüòèïëèêàòèâíîñòè ñëåäóåò ôîðìóëà Ýðëàíãà p(v) = 1 av × = N v! 1+a+ av v! a2 2! + ... + av v! = E(a, v). Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 27 / 79 Îöåíêà âåðîÿòíîñòåé ñ ïîìîùüþ ñâîéñòâà ìóëüòèïëèêàòèâíîñòè (5/8) I Ïóñòü v = 5 ê.å., n = 2, a1 = λ1 /µ1 = 2 Ýðë, a2 = λ2 /µ2 = 1 Ýðë, b1 = 1 ê.å., b2 = 2 ê.å. 2 Ненормированные значения вероятностей состояний 0,5 2 0,5 1 1 1 1 2 2 1,33 1 1 2 2 1,33 I Îäíîìåðíûå ðàñïðåäåëåíèÿ i a11 i1 ! i a22 i2 ! , i1 = 0, 1, 2, 3, 4, 5 è , 2 i2 = 0, 1, 2 ïðèâåäåíû â òàáëèöå ñîâìåñòíî ñ íåíîðìèðîâàííûìè çíà÷åíèÿìè âåðîÿòíîñòåé i P (i1 , i2 ) = a11 i1 ! i · a22 i2 ! , (i1 , i2 ) ∈ S 2! Одномерные распределения 0,67 1 2 3 4 1 2 2 1,33 0,67 0,27 5 0,27 1 1! I Äëÿ íåáîëüøîãî ÷èñëà êàíàëîâ è ïîòîêîâ òðàôèêà âåëè÷èíû ñòàöèîíàðíûõ âåðîÿòíîñòåé ñîñòîÿíèé ìîäåëè, íàéäåííûå ñ ïîìîùüþ ñâîéñòâà ìóëüòèïëèêàòèâíîñòè, ìîãóò áûòü íåïîñðåäñòâåííî èñïîëüçîâàíû äëÿ îöåíêè õàðàêòåðèñòèê êà÷åñòâà îáñëóæèâàíèÿ ïîñòóïàþùèõ çàÿâîê. Òàêèì îáðàçîì ðàññ÷èòûâàþòñÿ âåðîÿòíîñòè ñîñòîÿíèé â ìîäåëè Ýðëàíãà 1 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 28 / 79 Ïðèìåð îöåíêè õàðàêòåðèñòèê ñ ïîìîùüþ ìóëüòèïëèêàòèâíîñòè (5/8) I Çíà÷åíèÿ õàðàêòåðèñòèê íàõîäÿòñÿ ñ ïîìîùüþ èõ îïðåäåëåíèé ÷åðåç âåëè÷èíû ñòàöèîíàðíûõ âåðîÿòíîñòåé ìîäåëè   1 2,6 × P (1, 2) + P (3, 1) + P (5, 0) = = 0,172; N 15,1   1 × P (0, 2) + P (1, 2) + P (2, 1) + P (3, 1) + P (4, 0) + P (5, 0) = π2 = N 5,77 = = 0,382; 15,1 

1 m1 = × P (1, 0) + P (1, 1) + P (1, 2) · 1 + P (2, 0) + P (2, 1) · 2+ N  25,01
= 1,66 ê.å; + P (3, 0) + P (3, 1) · 3 + P (4, 0) · 4 + P (5, 0) · 5 = 15,1 
2 m2 = × P (0, 1) + P (1, 1) + P (2, 1) + P (3, 1) · 1+ N
 18,66 + P (0, 2) + P (1, 2) · 2 = = 1,24 ê.å., y1 = 1,66; y2 = 0,62. 15,1 π1 = I Çíà÷åíèÿ p(i1 , . . . , in ) ìîãóò òàêæå èñïîëüçîâàòüñÿ äëÿ îöåíêè äðóãèõ ïîêàçàòåëåé, íàïðèìåð, äîëè âðåìåíè, êîãäà íà îáñëóæèâàíèè íàõîäèòñÿ áîëüøå çàÿâîê k-ãî ïîòîêà íåæåëè j -ãî (k 6= j) è ò.ï.  îáùåì ñëó÷àå ÷èñëî p(i1 , . . . , in ) áûñòðî ðàñò¼ò ñ óâåëè÷åíèåì v è n è äëÿ ðàñ÷åòà õàðàêòåðèñòèê ïðèìåíÿþòñÿ äðóãèå àëãîðèòìû. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 29 / 79 Ðåêóðñèâíûé àëãîðèòì: ïðåäïîñûëêè I Ýôôåêòèâíûé àëãîðèòì îöåíêè πk , mk îñíîâàí íà èñïîëüçîâàíèè âåðîÿòíîñòåé ïðåáûâàíèÿ r(t) âî ìíîæåñòâå Si , ò.å. â ñîñòîÿíèÿõ (i1 , . . . , in ) ∈ S , óäîâëåòâîðÿþùèõ óñëîâèþ i1 b1 + . . . + in bn = i. I Îïðåäåëèì p(i) èç ðàâåíñòâà X p(i) = p(i1 , . . . , in ), i = 0, 1, . . . , v. (i1 ,...,in )∈Si I Âûðàçèì πk , k = 1, . . . , n ÷åðåç p(i) πk = X (i1 ,...,in )∈Uk p(i1 , . . . , in ) = v X X i=v−bk +1 (i1 ,...,in )∈Si p(i1 , . . . , in ) = v X p(i). i=v−bk +1 I Îöåíêà mk , k = 1, . . . , n ñ ïîìîùüþ p(i) ñëåäóåò èç ôîðìóëû Ëèòòëà Ws = Ls , λs îòíåñåííîé ê îáñëóæèâàíèþ çàÿâîê. Ñðåäíåå âðåìÿ îáñëóæèâàíèÿ çàÿâêè ïðèíÿòî çà åäèíèöó. Îòñþäà: Ws = 1. Ïî îïðåäåëåíèþ Ls = yk . Èç ñâîéñòâà PASTA ñëåäóåò λs = ak (1 − πk ).  ðåçóëüòàòå yk = ak (1 − πk ) èëè mk = ak bk (1 − πk ). I Ñîîòíîøåíèå yk = ak (1 − πk ) ìîæíî ïåðåïèñàòü â âèäå ak = ak πk + yk . Ïîëó÷åííîå ðàâåíñòâî ïðåäñòàâëÿåò èç ñåáÿ òàê íàçûâàåìûé çàêîí ñîõðàíåíèÿ, óòâåðæäàþùèé, ÷òî èíòåíñèâíîñòü k-ãî ïîòîêà çàÿâîê ðàâíà ñóììå èíòåíñèâíîñòåé ïîòîêîâ çàáëîêèðîâàííûõ è îáñëóæåííûõ çàÿâîê ðàññìàòðèâàåìîãî ïîòîêà. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 30 / 79 Ðåêóðñèâíûé àëãîðèòì: âûâîä îñíîâíîé ðåêóðñèè I Ñðåäíåå ÷èñëî çàÿâîê k-ãî ïîòîêà, íàõîäÿùèõñÿ íà îáñëóæèâàíèè ïðè çàíÿòîñòè i åäèíèö ðåñóðñà ëèíèè, îïðåäåëÿåòñÿ èç ñîîòíîøåíèÿ yk (i) = X p(i1 , . . . , in )ik . (i1 ,...,in )∈Si I Óðàâíåíèå äåòàëüíîãî áàëàíñà äëÿ ñîñòîÿíèÿ (i1 , . . . , in ) èìååò âèä: p(i1 , . . . , ik , . . . , in )ik = p(i1 , . . . , ik − 1, . . . , in )ak . I Ñóììèðóÿ óðàâíåíèÿ áàëàíñà ïî âñåì (i1 , . . . , in ) ∈ Si , ò.å. i1 b1 + . . . + in bn = i ïîëó÷àåì ðàâåíñòâî yk (i) = p(i − bk )ak , i = bk , bk + 1, . . . , v. I Óìíîæèì ýòî âûðàæåíèå íà bk è ïðîñóììèðóåì ïî k = 1, 2, . . . , n. Ïåðåñòàâèâ ñëåâà ïîðÿäîê ñóììèðîâàíèÿ, ïîëó÷àåì ðåêóðñèâíîå ñîîòíîøåíèå, ñâÿçûâàþùåå ïîñëåäîâàòåëüíûå çíà÷åíèÿ p(i) X (i1 ,...,in )∈Si p(i1 , . . . , in ) n X k=1 ik bk = p(i) i = n X k=1 ak bk p(i − bk ), i = 1, . . . , v. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 31 / 79 Ðåêóðñèâíûé àëãîðèòì: ïîñëåäîâàòåëüíîñòü ðåàëèçàöèè 1. Ïîëîæèì çíà÷åíèå P (0) = 1. 2. Âûðàçèì çíà÷åíèÿ P (i) ÷åðåç P (0), èñïîëüçóÿ ñîîòíîøåíèå P (i) = n X 1 × ak bk P (i − bk ) i k=1 è ïîñëåäîâàòåëüíî óâåëè÷èâàÿ i îò 1 äî v . Ïðè ôèêñèðîâàííîì i çíà÷åíèÿ P (i − bk ), k = 1, 2, . . . , n ëèáî óæå ïðåäñòàâëåíû ÷åðåç P (0) (äëÿ i − bk ≥ 0), ëèáî ðàâíû 0 (äëÿ i − bk < 0). Ðåêóðñèÿ ðåàëèçóåòñÿ äëÿ âñåõ i. 3. Íàõîäèì âåëè÷èíó íîðìèðîâî÷íîé êîíñòàíòû N = vi=0 P (i). 4. Îïðåäåëÿåì íîðìèðîâàííûå çíà÷åíèÿ âåðîÿòíîñòåé p(i) P p(i) = P (i) , N i = 0, 1, . . . , v. 5. Íàõîäèì âåëè÷èíû πk è mk äëÿ êàæäîãî èç n ïîòîêîâ πk = v X i=v−bk +1 p(i), mk = ak bk (1 − πk ), k = 1, . . . , n. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 32 / 79 Ïðèìåð ðåàëèçàöèè ðåêóðñèâíîãî àëãîðèòìà (6/8) I Èñõîäíûå äàííûå: v = 5 ê.å.; n = 2; b1 = 1 ê.å.; b2 = 2 ê.å.; a1 = 2 Ýðë; a2 = 1 Ýðë. I Ðàñ÷åòíîå âûðàæåíèå   P (i) = 2i × P (i − 1) + P (i − 2) , i = 1, 2, 3, 4, 5. I Ïîñëåäîâàòåëüíàÿ ðåàëèçàöèÿ ðåêóðñèè ïðèâîäèò ê ñëåäóþùèì çíà÷åíèÿì P (i) P (0) = 1; P (1) = 2 · P (0) = 2;

= 3,333; P (2) = 1 · P (1) + P (0) = 3; P (3) = 32 · P (2) + P (1) = 10 3

P (4) = 24 · P (3) + P (2) = 19 = 3,167; P (5) = 52 · P (4) + P (3) = 39 = 2,6. 6 15 I Íîðìèðîâî÷íàÿ êîíñòàíòà N = 15,1. Çíà÷åíèÿ õàðàêòåðèñòèê π1 = P (5) N = 0,172; π2 = P (4)+P (5) N m2 = 2 · (1 − 0,382) = 1,24 ê.å; = 0,382; m1 = 2 · (1 − 0,172) = 1,66 ê.å; y1 = 1,66; y2 = 0,62. I Ïðèìåð ïîêàçûâàåò, ÷òî ðåàëèçàöèÿ àëãîðèòìà íå âûçûâàåò çàòðóäíåíèé è ìîæåò áûòü âûïîëíåíà íà ïðîñòåéøèõ âû÷èñëèòåëüíûõ óñòðîéñòâàõ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 33 / 79 Ïðèìåíåíèå ìîäåëè I Ìîäåëü ìóëüòèñåðâèñíîãî óçëà äîñòóïà è àëãîðèòìû, ïîëó÷åííûå íà åå îñíîâå, èñïîëüçóåòñÿ: • äëÿ àíàëèçà çàâèñèìîñòè õàðàêòåðèñòèê êà÷åñòâà îáñëóæèâàíèÿ ïîñòóïàþùèõ çàÿâîê îò ïàðàìåòðîâ âîçíèêàþùèõ èíôîðìàöèîííûõ ïîòîêîâ è óñëîâèé äîïóñêà çàÿâîê ê çàíÿòèþ ðåñóðñà; • äëÿ àíàëèçà äåéñòâèÿ ðàçíîãî ðîäà ïðîöåäóð, íàïðàâëåííûõ íà ïîâûøåíèå ýôôåêòèâíîñòè èñïîëüçîâàíèÿ ðåñóðñà ïåðåäà÷è ëèíèè äîñòóïà (ïðèìåíåíèå ïàêåòíûõ òåõíîëîãèé ïåðåäà÷è èíôîðìàöèè, èñïîëüçîâàíèå ïðîöåäóðû ìóëüòèïëåêñèðîâàíèÿ è ò.ä.); • äëÿ îöåíêè òðåáóåìîé ïî íàãðóçêå è êà÷åñòâó îáñëóæèâàíèÿ ñêîðîñòè ëèíèè äîñòóïà è ðåøåíèÿ äðóãèõ ïîäîáíûõ ýòîé çàäà÷, íàïðèìåð, äëÿ îöåíêè ìàêñèìàëüíîãî îáúåìà òðàôèêà, êîòîðûé ìîæåò áûòü îáñëóæåí ñ òðåáóåìûì êà÷åñòâîì íà ëèíèè äîñòóïà ñ ôèêñèðîâàííîé ñêîðîñòüþ ïåðåäà÷è èíôîðìàöèè. I Íàëè÷èå ýôôåêòèâíûõ àëãîðèòìîâ îöåíêè õàðàêòåðèñòèê ìîäåëè óïðîùàåò ðåøåíèå ïåðå÷èñëåííûõ çàäà÷. Ðàññìîòðèì íåñêîëüêî ïðèìåðîâ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 34 / 79 Ñâîéñòâî ïðîïîðöèîíàëüíîñòè (1/9) π k к,о ява з х ы нн яр ет оп ляо Д 1 4 3 2 0,1 1 0,01 0,001 0,5 0,6 0,7 0,8 0,9 1 1,1 1,2 1,3 Интенсивность предложенного трафика на канальную единицу, 1,4 ρ • Èñõîäíûå äàííûå: v = 100 ê.å; n = 4; bk = 1, 5, 10, 20 ê.å. Îáîçíà÷èì ÷åðåç ρ = (a1 b1 + . . . + a4 b4 )/v  ïîòåíöèàëüíóþ çàãðóçêó êàíàëà. Ïðèìåì, ÷òî ak = vρ/nbk Ýðë. Îòñþäà ñëåäóåò, ÷òî ïîòåíöèàëüíàÿ çàãðóçêà ðåñóðñà ak bk ó âñåõ ïîòîêîâ îäèíàêîâà è ðàâíà vρ/n.  ñîîòâåòñòâèè ñ îïðåäåëåíèåì πk = p(v) + p(v − 1) + . . . + p(v − bk + 1). Òàêèì îáðàçîì, åñëè bi ≥ bj , òî πi ≥ πj . ×åì áîëüøå òðåáîâàíèå ê ðåñóðñà, òåì áîëüøå è ïîòåðè. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 35 / 79 Ñâîéñòâî ïðîïîðöèîíàëüíîñòè (2/9) k π ' ,а ср ус ер цеи ни ед к е ы нн ёд ев ир п, ир ет оП 0,04 1 2 0,035 3 4 0,03 0,025 0,02 4 0,015 1 2 Свойство пропорциональности: 3 πi≅πj ' ' 0,01 0,8 0,9 1 1,1 Интенсивность предложенного трафика на канальную единицу, ρ 1,2 • Äëÿ òåõ æå èñõîäíûõ äàííûõ ïîâåäåíèå πk ðàññìîòðåíî â ìåòðèêå πk0 = πk /bk . • Íàáëþäàåòñÿ ÿðêî âûðàæåííîå ñâîéñòâî ïðîïîðöèîíàëüíîñòè: â ñèòóàöèè, êîãäà ρ ≈ 1 (ò.å. A ≈ v ), òî πi /bi ≈ πj /bj . • Äîïîëíèòåëüíûå ðåçóëüòàòû: åñëè ρ < 1 è bi > bj , òî πi /bi > πj /bj ; åñëè ρ > 1 è bi > bj , òî πi /bi < πj /bj . Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 36 / 79 Ñâîéñòâî ïðîïîðöèîíàëüíîñòè (3/9) I Äàäèì ïîÿñíåíèå ñâîéñòâó ïðîïîðöèîíàëüíîñòè. Ñ ýòîé öåëüþ äëÿ òåõ æå èñõîäíûõ äàííûõ ðàññìîòðèì ïîâåäåíèå p(i) â çàâèñèìîñòè îò çíà÷åíèÿ i. Äëÿ áîëüøåé ÿñíîñòè îòíîðìèðóåì p(i) ïî èõ ìàêñèìàëüíîìó çíà÷åíèþ. I Êîãäà ρ ≈ 1, òî äëÿ ñòàöèîíàðíûõ âåðîÿòíîñòåé p(i), ó÷àñòâóþùèõ â ðàñ÷¼òå πk , âûïîëíÿåòñÿ ñîîòíîøåíèå p(i1 ) ≈ p(i2 ) ≈ p, ãäå i1 , i2 ïðèíèìàþò çíà÷åíèÿ îò v − bk + 1 äî v . I Ïîëó÷åííîå ñîîòíîøåíèå è ïðèâåäåííîå ðàíåå îïðåäåëåíèå äîëè ïîòåðÿííûõ çàÿâîê îáúÿñíÿþò ñâîéñòâî ïðîïîðöèîíàëüíîñòè ïîñêîëüêó èç ôîðìóëû äëÿ ðàñ÷åòà πk ñëåäóåò, ÷òî ïðè ρ ≈ 1 íåçàâèñèìî îò k âûïîëíÿåòñÿ ñîîòíîøåíèå πb k ≈ p. k i ,йP тес он тя ор ев иян еч ан з е ны ьл ет ис он т О ) ( 1 Диапазон изменения вероятностей, участвующих в оценке доли потерянных заявок 0,8 0,6 0,4 0,2 20 40 60 80 Число занятых канальных единиц, 100 i (к.е.) Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà Ñâîéñòâî ïðîïîðöèîíàëüíîñòè (4/9) I Êîãäà ρ > 1, òî äëÿ ñòàöèîíàðíûõ âåðîÿòíîñòåé p(i), ó÷àñòâóþùèõ â ðàñ÷¼òå πk , âûïîëíÿåòñÿ ñîîòíîøåíèå p(i1 ) > p(i2 ), i 1 > i2 . I Ñëåäîâàòåëüíî, ÷åì ìåíüøå âåðîÿòíîñòåé p(i) èñïîëüçóåòñÿ ïðè îöåíêå ïîòåðü òåì áîëüøå åå çíà÷åíèå. π Îòñþäà: πb i < b j , ρ > 1, bi > bj . i j I Êîãäà ρ < 1, òî äëÿ ñòàöèîíàðíûõ âåðîÿòíîñòåé p(i), ó÷àñòâóþùèõ â ðàñ÷¼òå πk , âûïîëíÿåòñÿ ñîîòíîøåíèå p(i1 ) < p(i2 ), i 1 > i2 . I Ñëåäîâàòåëüíî, ÷åì ìåíüøå âåðîÿòíîñòåé p(i) èñïîëüçóåòñÿ ïðè îöåíêå ïîòåðü òåì ìåíüøå åå çíà÷åíèå. π Îòñþäà: πb i > b j , ρ < 1, bi > bj . i j i P ,й ет со нт яо ре в яи не ча нз е ы нь ле ти со тн О ) ( 1 ρ = 0,8 1,2 0,8 Характер изменения значений вероятностей, исп ользуемых при оценке доли потерянных заявок 0,6 0,4 0,2 20 40 60 80 Число занятых канальных единиц, 100 i (к.е.) 37 / 79 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 38 / 79 Ñâîéñòâî ïðîïîðöèîíàëüíîñòè (5/9) I Ïðàêòè÷åñêîå èñïîëüçîâàíèå ñâîéñòâà ïðîïîðöèîíàëüíîñòè.  ìóëüòèñåðâèñíûõ ñåòÿõ ïî ïîñòðîåíèþ ðàññìàòðèâàåòñÿ ïðîöåññ ñîâìåñòíîãî îáñëóæèâàíèÿ íåñêîëüêèõ ïîòîêîâ òðàôèêà. Íàëè÷èå áîëüøîãî ÷èñëà ïîòîêîâ ñ ðàçíûìè õàðàêòåðèñòèêàìè óñëîæíÿåò çàäà÷ó ïëàíèðîâàíèÿ íåîáõîäèìîãî îáúåìà ðåñóðñà èç-çà íåîïðåäåëåííîñòè â âûáîðå íîðìàòèâíûõ ïîêàçàòåëåé. I Äëÿ ýòèõ öåëåé îáû÷íî ðàññìàòðèâàþò çíà÷åíèÿ èíòåãðàëüíûõ õàðàêòåðèñòèê.  èõ ÷èñëå: ìàêñèìàëüíàÿ äîëÿ ïîòåðÿííûõ çàÿâîê, äîëÿ ïîòåðÿííîãî òðàôèêà è ò.ä. Ïðè ýòîì êà÷åñòâî îáñëóæèâàíèÿ îòäåëüíûõ ïîòîêîâ íå îöåíèâàåòñÿ. Âîçíèêàþùèå òðóäíîñòè ìîæíî óñòðàíèòü, åñëè âîñïîëüçîâàòüñÿ ñâîéñòâîì ïðîïîðöèîíàëüíîñòè. I Îáû÷íî â çàäà÷àõ ïëàíèðîâàíèÿ ρ . 1. Ïðèìåì äàëåå ýòî äîïóùåíèå. I Ïðåäïîëîæèì, ÷òî äîñòàòî÷íîñòü ðåñóðñà ïëàíèðóåòñÿ èñõîäÿ èç îãðàíè÷åíèÿ íà ìàêñèìàëüíóþ äîëþ ïîòåðÿííûõ çàÿâîê max πk = πn ≤ πnorm . k I Èç ñâîéñòâà ïðîïîðöèîíàëüíîñòè äëÿ ρ . 1 íàõîäèì îöåíêè ñâåðõó äëÿ ïîòåðü çàÿâîê âñåõ ïîòîêîâ πk . πn bk bk = πnorm . bn bn Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 39 / 79 Ñâîéñòâî ïðîïîðöèîíàëüíîñòè (6/9) I Ïðåäïîëîæèì òåïåðü, ÷òî äîñòàòî÷íîñòü ðåñóðñà ïëàíèðóåòñÿ èñõîäÿ èç îãðàíè÷åíèÿ íà äîëþ ïîòåðÿííîãî òðàôèêà π` = a1 b1 π1 + . . . + an bn πn ≤ πnorm . a1 b1 + . . . + an bn I Èç ñâîéñòâà ïðîïîðöèîíàëüíîñòè äëÿ ρ . 1 ñëåäóåò, ÷òî πk . πn bk , bn k = 1, . . . , n. I Îòñþäà è îïðåäåëåíèÿ π` ñëåäóåò îöåíêà ñíèçó äëÿ πn πn & π` bn a1 b1 + . . . + an bn a1 b1 + . . . + an bn = πnorm bn . a1 b21 + . . . + an b2n a1 b21 + . . . + an b2n I Âîñïîëüçîâàâøèñü îöåíêàìè, ïîëó÷åííûìè íà ñëàéäå 38, íàõîäèì âûðàæåíèå äëÿ ïðèáëèæåííîãî ðàñ÷åòà πk πk ' πnorm bk a1 b1 + . . . + an bn . a1 b21 + . . . + an b2n Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 40 / 79 Ñâîéñòâî ïðîïîðöèîíàëüíîñòè (7/9) • Àíàëèç ïîãðåøíîñòè ïðèáëèæåííîãî ðàñ÷åòà ïîòåðü èñõîäÿ èç èçâåñòíîãî çíà÷åíèÿ ìàêñèìàëüíîé äîëè ïîòåðÿííûõ çàÿâîê 0,3 0,25 Верхняя оценка π k к,о вя аз х ы нн яр ет оп ял о Д 0,2 Точное значение 0,15 π3 0,1 π2 0,05 π1 50 90 130 170 Число канальных единиц, v 210 250 (к.е.) • Èñõîäíûå äàííûå: n = 4; bk = 1, 5, 10, 20 ê.å; ρ = 0,8; ak = vρ/nbk Ýðë; k = 1, 2, 3, 4. Íàãðóçêà íà êàíàë ρ = 0,8.  ñîîòâåòñòâèè ñî ñâîéñòâîì ïðîïîðöèîíàëüíîñòè âåëè÷èíà π̂k âåðõíåé îöåíêè äëÿ πk ðàññ÷èòûâàåòñÿ èç âûðàæåíèÿ π̂k . π4 bk /b4 . Ïîëó÷åííûå ïðèáëèæåííûå çíà÷åíèÿ ïîòåðü îòëè÷àþòñÿ âûñîêîé òî÷íîñòüþ, îñîáåííî äëÿ áîëüøèõ çíà÷åíèé ðåñóðñà ïåðåäà÷è èíôîðìàöèè. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 41 / 79 Ñâîéñòâî ïðîïîðöèîíàëüíîñòè (8/9) • Àíàëèç ïîãðåøíîñòè ïðèáëèæåííîãî ðàñ÷åòà ïîòåðü èñõîäÿ èç èçâåñòíîãî çíà÷åíèÿ ìàêñèìàëüíîé äîëè ïîòåðÿííûõ çàÿâîê v ê.å. 50 75 100 125 150 175 200 225 250 275 300 Òî÷íî 0,032851 0,027608 0,024304 0,021974 0,020215 0,018826 0,017693 0,016745 0,015936 0,015236 0,014622 π1 Ïðèáë. 0,033470 0,027955 0,024527 0,022133 0,020335 0,018922 0,017771 0,016810 0,015992 0,015285 0,014665 Òî÷íî 0,168562 0,140454 0,123112 0,111016 0,101953 0,094830 0,089039 0,084207 0,080096 0,076541 0,073427 π2 Ïðèáë. 0,167350 0,139776 0,122637 0,110663 0,101677 0,094608 0,088854 0,084051 0,079961 0,076424 0,073323 Òî÷íî 0,343196 0,284075 0,248265 0,223487 0,205010 0,190535 0,178793 0,169014 0,160704 0,153526 0,147243 π3 Ïðèáë. 0,334701 0,279552 0,245274 0,221325 0,203354 0,189215 0,177708 0,168102 0,159923 0,152847 0,146647 I Èñõîäíûå äàííûå: n = 4; bk = 1, 5, 10, 20 ê.å; ak = vρ Ýðë; k = 1, 2, 3, 4. Íàãðóçêà nbk íà êàíàë ρ = 1.  äàííûõ óñëîâèÿõ ïðèáëèæåííûé ìåòîä èìååò îñîáåííî âûñîêóþ òî÷íîñòü (ñì. ñëàéä 36).  ñîîòâåòñòâèè ñî ñâîéñòâîì ïðîïîðöèîíàëüíîñòè çíà÷åíèå π̂k îöåíêè äëÿ πk ðàññ÷èòûâàåòñÿ èç âûðàæåíèÿ π̂k ' π4 bk /b4 , k = 1, 2, 3. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 42 / 79 Ñâîéñòâî ïðîïîðöèîíàëüíîñòè (9/9) • Àíàëèç ïîãðåøíîñòè ïðèáëèæåííîãî ðàñ÷åòà ïîòåðü èñõîäÿ èç èçâåñòíîãî çíà÷åíèÿ äîëè ïîòåðÿííîãî òðàôèêà 0,3 Точное значение π k π4 0,25 ,к ов яа з х ы нн яр ет оп ял о Д Нижняя оценка 0,2 π3 0,15 Приближенное значение π2 0,1 0,05 π1 50 90 130 170 Число канальных единиц, v 210 250 (к.е.) • Èñõîäíûå äàííûå òå æå, ÷òî íà ïðåäûäóùåì ñëàéäå. Îöåíêè õàðàêòåðèñòèê ñëåäóþò èç ñâîéñòâà ïðîïîðöèîíàëüíîñòè (ñì. ñëàéä 39) π4 & π` b 4 a1 b1 + . . . + a4 b4 ; a1 b21 + . . . + a4 b24 πk ' π` bk a1 b1 + . . . + a4 b4 , a1 b21 + . . . + a4 b24 k = 1, 2, 3. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 43 / 79 Àíàëèç çàâèñèìîñòè õàðàêòåðèñòèê îò ðîñòà òðàôèêà (1/2) I Ñîâìåñòíîå îáñëóæèâàíèå ìóëüòèñåðâèñíîãî I Äèàãðàììû ïîêàçûâàþò çíà÷åíèÿ πk , k = 1, 2 â çàâèñèìîñòè îò óâåëè÷åíèÿ ρ çàãðóçêè åäèíèöû êàíàëüíîãî ðåñóðñà. I Âõîäíûå ïàðàìåòðû: v = 120 ê.å; n = 2; vρ Ýðë, k = 1, 2. b1 = 1 ê.å; b2 = 30 ê.å; ak = nb k I Êîëè÷åñòâî ëîêàëüíûõ ìèíèìóìîâ ó π1 ðàâíî j k v = 4. Ïåðâûé ìèíèìóì ó π1 ñëåäóåò èç òîãî, b k 1,00E+00 π òðàôèêà ñ ÿðêî âûðàæåííîé íåîäíîðîäíîñòüþ òðåáîâàíèé ê ðåñóðñó îòëè÷àåòñÿ ðÿäîì îñîáåííîñòåé, êîòîðûå íàäî ó÷èòûâàòü ïðè ðåøåíèè çàäà÷ ïëàíèðîâàíèÿ ñåòè. ,к воя аз х ы ння ре то п ял о Д 1,00E-01 1,00E-02 2 1 1,00E-03 1,00E-04 1,00E-05 1,00E-06 1,00E-07 2 ÷òî ñ ðîñòîì íàãðóçêè ñòàëî ïðàêòè÷åñêè íåâîçìîæíûì îäíîâðåìåííîå îáñëóæèâàíèå ÷åòûðåõ ðåñóðñîåìêèõ çàÿâîê. Çàÿâêè ñ ìàëûìè òðåáîâàíèÿìè ê ðåñóðñó ïîëó÷àþò äîïîëíèòåëüíûå âîçìîæíîñòè ê åãî èñïîëüçîâàíèþ. I Êàæäûé ñëåäóþùèé ìèíèìóì ó π1 îçíà÷àåò ïðàêòè÷åñêóþ íåâîçìîæíîñòü îäíîâðåìåííîãî îáñëóæèâàíèÿ 3, 2 è, íàêîíåö, óæå îäíîé ðåñóðñîåìêîé çàÿâêè. 1,00E-08 1,00E-09 1,00E-10 0,0 0,3 0,6 0,9 1,2 1,5 1,8 2,1 2,4 Загрузка канала, ρ Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 44 / 79 Àíàëèç çàâèñèìîñòè õàðàêòåðèñòèê îò ðîñòà òðàôèêà (2/2) I Íà ðèñóíêå äëÿ òåõ æå çíà÷åíèé ïàðàìåòðîâ, ÷òî áûëè èñïîëüçîâàíû íà ïðåäûäóùåì ñëàéäå, ïîêàçàíû ðåçóëüòàòû âû÷èñëåíèÿ mk , k = 1, 2 ñðåäíåãî ÷èñëà èñïîëüçóåìûõ åäèíèö êàíàëüíîãî ðåñóðñà â çàâèñèìîñòè îò óâåëè÷åíèÿ ρ. I Ïàðàìåòðû ïîäîáðàíû òàê, ÷òîáû äëÿ îáîèõ ïîòîêîâ ñòàëè ðàâíûìè çíà÷åíèÿ ïîòåíöèàëüíîé v = 60 ρ ÝðëÊ. çàãðóçêè ðåñóðñà ak bk = n I Êîãäà ïîòåðè çàÿâîê ìàëû, ñðåäíåå ÷èñëî çàíÿòûõ åäèíèö ðåñóðñà äëÿ îáîèõ ïîòîêîâ ïðèìåðíî ðàâíû. Ñ ðîñòîì ïîòåðü çàÿâêè ïåðâîãî ïîòîêà óæå äîìèíèðóþò â èñïîëüçîâàíèè ðåñóðñà ëèíèè. I Êàê âèäíî èç ïðåäñòàâëåííûõ äàííûõ çàÿâêè ñ ìàëûì èñïîëüçîâàíèåì ðåñóðñà ìîãóò ïðàêòè÷åñêè ïîëíîñòüþ âûòåñíèòü èç îáñëóæèâàíèÿ ðåñóðñîåìêèå çàÿâêè. Äëÿ áîðüáû ñ ýòèì ÿâëåíèåì èñïîëüçóåòñÿ ðàçäåëüíîå îáñëóæèâàíèå òðàôèêà, îãðàíè÷åíèå äîñòóïà çàÿâîê èëè ðåçåðâèðîâàíèå ðåñóðñà ïåðåäà÷è èíôîðìàöèè. Îñîáåííîñòè ïðèìåíåíèÿ ïåðå÷èñëåííûõ ïðîöåäóð áóäóò äàëåå ðàññìîòðåíû. 120 m k ,в ол 100 ан ак х ы ятн 80 аз ол си ч ее 60 нд ер С 1 40 2 20 0,0 0,3 0,6 0,9 1,2 1,5 1,8 Загрузка канала, 2,1 ρ 2,4 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 45 / 79 Àíàëèç îñîáåííîñòåé ïðèìåíåíèÿ ïàêåòíûõ òåõíîëîãèé I Ïðè ïåðåõîäå íà ïàêåòíûå òåõíîëîãèè âåëè÷èíà ck òðåáîâàíèÿ ê ñêîðîñòè ïåðåäà÷è äëÿ çàÿâîê k-ãî ïîòîêà ìîæåò êàê âîçðàñòè, òàê è óìåíüøèòüñÿ. • Íåîáõîäèìîñòü â óâåëè÷åíèè ck âîçíèêàåò â ñâÿçè ñ ó÷åòîì ñëóæåáíîé èíôîðìàöèè, ãëàâíûì îáðàçîì àäðåñíîé, êîòîðàÿ ïåðåäàåòñÿ ñîâìåñòíî ñ èíôîðìàöèåé, ïåðåñûëàåìîé ïîëüçîâàòåëåì óñëóã ñâÿçè. • Âåëè÷èíà ck óìåíüøàåòñÿ èç-çà ýôôåêòà ñòàòèñòè÷åñêîãî ìóëüòèïëåêñèðîâàíèÿ, âîçíèêàþùåãî ïðè ñîâìåñòíîé ïåðåäà÷å ïàêåòèçèðîâàííîé èíôîðìàöèè.  ðàññìàòðèâàåìîì ñëó÷àå òðåáîâàíèå ê ñêîðîñòè ïåðåäà÷è íîñèò íàçâàíèå ýôôåêòèâíîé ñêîðîñòè ïåðåäà÷è èíôîðìàöèîííîãî ïîòîêà. I Âíåñåíèå èçìåíåíèé â çíà÷åíèÿ ck ïðèâîäèò ê ïåðåñ÷åòó âõîäíûõ ïàðàìåòðîâ. Äàëåå îáû÷íûì îáðàçîì ðåøàåòñÿ çàäà÷à ïîèñêà òðåáóåìîé âåëè÷èíû ðåñóðñà. I Îñîáåííî ëåãêî ðåøèòü ýòó çàäà÷ó, åñëè ck ìåíÿþòñÿ â îäèíàêîâîé ïðîïîðöèè. Îáîçíà÷èì ÷åðåç C ñêîðîñòü ëèíèè, êîòîðàÿ îáåñïå÷èâàåò çàäàííûé óðîâåíü ìàêñèìàëüíûõ ïîòåðü çàÿâîê: C = ÍÎÄ(c1 , . . . , cn ) × v , ãäå çíà÷åíèå v íàéäåíî ñ èñïîëüçîâàíèåì îäíîãî èç ðåêóðñèâíûõ àëãîðèòìîâ, ðàññìîòðåííûõ íà ëåêöèè. Ïðåäïîëîæèì, ÷òî ck , k = 1, . . . , n, óâåëè÷èëèñü â z ðàç. Íåñëîæíî ïîêàçàòü ÷òî â ýòîé ñèòóàöèè âåëè÷èíû bk è íåîáõîäèìûé ïî íàãðóçêå è êà÷åñòâó îáñëóæèâàíèÿ îáúåì ðåñóðñà v íå ìåíÿþòñÿ. Òðåáóåìàÿ ñêîðîñòü ëèíèè C ∗ = z × C . Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 46 / 79 Ìóëüòèïëåêñèðîâàíèå àáîíåíòñêîãî òðàôèêà I Ïðè ïîñòðîåíèè ñåòåé ñâÿçè ÷àñòî èñïîëüçóåòñÿ ïðèíöèï êîíöåíòðàöèè ïîòîêîâ àáîíåíòñêîãî òðàôèêà. Корневой узел Уровни иерархии сети ïîñòðîåíèè ñåòåé äîñòóïà, â ÷àñòíîñòè èåðàðõè÷åñêèõ ñåòåé (ñì. ðèñóíîê). I Ïðåäïîëàãàåìàÿ ýôôåêòèâíîñòü äàííîãî ïîäõîäà îñíîâàíà íà îæèäàåìîì óìåíüøåíèè äîëè ïîòåðÿííûõ çàÿâîê è óâåëè÷åíèè åäèíèöû èñïîëüçîâàíèÿ ðåñóðñà ïðè îáúåäèíåíèè (ìóëüòèïëåêñèðîâàíèè) ïåðåäàòî÷íûõ âîçìîæíîñòåé îòäåëüíûõ ëèíèé. I Òåîðåòè÷åñêîå îáîñíîâàíèå ïðîöåäóðû ìóëüòèïëåêñèðîâàíèÿ çàêëþ÷àåòñÿ â ðàçðàáîòêå ìåòîäà îöåíêè ñêîðîñòè ëèíèè êîíöåíòðàöèè ìóëüòèñåðâèñíîãî òðàôèêà. Ýòà çàäà÷à ðåøàåòñÿ ñ ïîìîùüþ ìîäåëåé òåîðèè òåëåòðàôèêà è ñðåäñòâ èõ àíàëèçà. 4 14 I Îñîáåííî øèðîêî îí ïðèìåíÿåòñÿ ïðè 3 13 Этапы установления соединения 2 13 Линия 10 10 3 11 12 Узел 11 12 2 Концевой узел 1 1 1 1 2 3 4 5 6 2 3 4 5 6 2 3 4 5 7 7 6 7 8 9 8 9 8 Потоки заявок поступают в концевые узлы доступа 9 1 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 47 / 79 Àíàëèç ïðîöåäóðû ìóëüòèïëåêñèðîâàíèÿ òðàôèêà 1 I Äëÿ îöåíêè ýôôåêòèâíîñòè ìóëüòèïëåêñèðîâàíèÿ íåîáõîäèìî ñðàâíèòü ïîêàçàòåëè îáñëóæèâàíèÿ ïîòîêîâ çàÿâîê íà îòäåëüíûõ ëèíèÿõ ñ àíàëîãè÷íûìè ïîêàçàòåëÿìè îáñëóæèâàíèÿ îáúåäèíåííîãî ïîòîêà çàÿâîê íà îäíîé ëèíèè ñî ñêîðîñòüþ ðàâíîé èëè ìåíüøåé ñóììå ñêîðîñòåé ëèíèé, ó÷àñòâóþùèõ â ìóëüòèïëåêñèðîâàíèè. I Äëÿ ïðîâåäåíèÿ òåîðåòè÷åñêîãî èññëåäîâàíèÿ äîñòàòî÷íî îãðàíè÷èòüñÿ ðàññìîòðåíèåì ñëó÷àÿ äâóõ ëèíèé. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 48 / 79 Àíàëèç ìóëüòèïëåêñèðîâàíèÿ ìóëüòèñåðâèñíîãî òðàôèêà (1/6) I Ðàñ÷åò ïîêàçàòåëåé ñîâìåñòíîãî îáñëóæèâàíèÿ çàÿâîê âûïîëíÿåòñÿ ñ ïîìîùüþ ðåêóðñèâíîãî àëãîðèòìà, ïðèâåäåííîãî íà ñëàéäå 31. Ïóñòü ρ  èíòåíñèâíîñòü ïðåäëîæåííîãî òðàôèêà íà åäèíèöó ðåñóðñà, à δ  êîýôôèöèåíò èñïîëüçîâàíèÿ åäèíèöû ðåñóðñà. Ïî îïðåäåëåíèþ ρ= 1 (a1 b1 + . . . + an bn ); v δ= 1 (m1 + . . . + mn ). v I Ïðè ñóììèðîâàíèè âõîäíûõ ïîòîêîâ çàÿâîê è ïåðåäàòî÷íîãî ðåñóðñà äâóõ ëèíèé ñ ðàâíûìè çíà÷åíèÿìè ρ â îáúåäèíåííîé ñèñòåìå: • êàê ïðàâèëî äîëÿ ïîòåðÿííûõ çàÿâîê óìåíüøàåòñÿ, à êîýôôèöèåíò èñïîëüçîâàíèÿ åäèíèöû ðåñóðñà óâåëè÷èâàåòñÿ; • îäíàêî ñóùåñòâóþò è ïðîòèâîïîëîæíûå ïðèìåðû, êîãäà îæèäàåìûå ñâîéñòâà íå âûïîëíÿþòñÿ (îíè õàðàêòåðíû äëÿ ñîâìåñòíîãî îáñëóæèâàíèÿ òðàôèêà ñ ÿðêî âûðàæåííîé íåîäíîðîäíîñòüþ òðåáîâàíèé ê ðåñóðñó ïåðåäà÷è èíôîðìàöèè) è ýòî îáñòîÿòåëüñòâî íåîáõîäèìî ó÷èòûâàòü ïðè ïëàíèðîâàíèè ñåòåé ñâÿçè. I Îòìå÷åííûå âûøå ñâîéñòâà íàáëþäàþòñÿ òàêæå è ïðè ñóììèðîâàíèè âõîäíûõ ïîòîêîâ çàÿâîê è ïåðåäàòî÷íîãî ðåñóðñà äâóõ ëèíèé ñ ðàçíûìè çíà÷åíèÿìè ρ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 49 / 79 Àíàëèç ìóëüòèïëåêñèðîâàíèÿ ìóëüòèñåðâèñíîãî òðàôèêà (2/6) • Íà äèàãðàììàõ ïîêàçàíû çíà÷åíèÿ πk (ñëåâà) è δ (ñïðàâà) ïðè óâåëè÷åíèè ρ ïðè ðàçäåëüíîì v = 50 ê.å. è ñîâìåñòíîì v = 100 ê.å. çàíÿòèè ðåñóðñà äâóõ ëèíèé è îäèíàêîâîé çàãðóçêå êàíàëà. Ïàðàìåòðû: n = 4; bk = 1, 3, 5, 10 ê.å; ak = nvbρ Ýðë. k 1 π k δ 0,5 0,45 ,к воя 0,4 аз х ы нн 0,35 яр тео п 0,3 ял о Д 0,25 Раздельное использование ресурса Совместное использование ресурса 0,2 0,1 π2 π3 0,5 0,6 Раздельное использование ресурса 0,65 0,6 π1 0,05 Совместное использование ресурса 0,7 π4 0,15 0,95 ,а рсу се 0,9 р ы ци 0,85 ин д е каз 0,8 ур га З 0,75 0,8 Загрузка канала, 0,9 0,55 1,0 ρ 0,5 0,5 0,6 0,8 Загрузка канала, 0,9 1,0 ρ Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 50 / 79 Àíàëèç ìóëüòèïëåêñèðîâàíèÿ ìóëüòèñåðâèñíîãî òðàôèêà (3/6) • Íà äèàãðàììàõ ïîêàçàíû çíà÷åíèÿ πk (ñëåâà) è δ (ñïðàâà) â çàâèñèìîñòè îò óâåëè÷åíèÿ s ÷èñëà îáúåäèíÿåìûõ ïîòîêîâ çàÿâîê. Äëÿ êàæäîé èç ìóëüòèïëåêñèðóåìûõ ëèíèé: v = 50 ê.å, n = 4; bk = 1, 3, 5, 10 ê.å; ak = nvbρ Ýðë, ρ = 1. k 0,5 1 0,45 π δ k 0,4 ,к 0,35 ов яа 0,3 з х ы ння0,25 ре то 0,2 п ял о0,15 Д а,л ан ак 0,9 еи на во зь ло0,85 пс и ее нд ер 0,8 С π4 π3 π2 0,1 π1 0,05 1 2 3 4 5 6 7 0,95 8 9 Число объединенных потоков, s 10 0,75 1 2 3 4 5 6 7 8 9 Число объединенных потоков, s 10 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 51 / 79 Àíàëèç ìóëüòèïëåêñèðîâàíèÿ ìóëüòèñåðâèñíîãî òðàôèêà (4/6) I Ïðåäïîëîæèì, ÷òî îáúåäèíÿþòñÿ òðàôèê è ñêîðîñòè s ìóëüòèñåðâèñíûõ ëèíèé è êà÷åñòâî îáñëóæèâàíèÿ, çàäàííîå ìàêñèìàëüíûìè ïîòåðÿìè, óäîâëåòâîðÿåò òðåáóåìîé íîðìå. Ïîëîæèì, ÷òî ÷èñëî ïîòîêîâ, èíòåíñèâíîñòè òðàôèêà è ñêîðîñòè ëèíèé îäèíàêîâû è çàäàíû ïàðàìåòðàìè: v , n, ak , bk , k = 1, . . . , n. I Òîãäà, èñïîëüçóÿ îáùèå ñâîéñòâà ìóëüòèïëåê- ñèðîâàíèÿ, ìîæíî îæèäàòü, ÷òî ñêîðîñòü ëèíèè êîíöåíòðàöèè òðàôèêà ìîæíî óâåëè÷èòü â ìåíüøåå, ÷åì vs ÷èñëî ðàç äî çíà÷åíèÿ v ∗ , îáåñïå÷èâàþùåãî òðåáóåìûå ïîêàçàòåëè ïîòåðü. I Ðåàëèçàöèÿ ñôîðìóëèðîâàííîãî ïîëîæåíèÿ ïîêàçàíà íà ðèñóíêå ïðè ìóëüòèïëåêñèðîâàíèè s = 1, . . . , 10 îäèíàêîâûõ ìóëüòèñåðâèñíûõ ëèíèé ñ ïàðàìåòðàìè îòäåëüíîé ëèíèè: v = 100 ê.å; n = 10; ak = vρ/nbk Ýðë., bk = 1, 3, 5, 10 ê.å; k = 1, 2, 3, 4 ρ = 0,65; πmax = π4 = 0,052. I Èç ïðèâåäåííûõ äàííûõ âèäíî, ÷òî âûèãðûø â ÷èñëå êàíàëîâ ðàñòåò ëèíåéíî ñ ðîñòîì s, äîñòèãàÿ ïðè äàííûõ ïàðàìåòðàõ, âåëè÷èíû ïðèìåðíî 30% ïðè s = 10. ии ца м ро ф ин ич ад ер еп во ла на к ол си Ч 1000 900 Выигрыш в числе каналов 800 700 Общее число каналов: vs 600 500 400 300 200 Требуемое число каналов при фиксированных потерях: v* 100 1 2 3 4 5 6 7 8 9 Число объединенных потоков, s 10 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 52 / 79 Àíàëèç ìóëüòèïëåêñèðîâàíèÿ ìóëüòèñåðâèñíîãî òðàôèêà (5/6) I Ìóëüòèïëåêñèðîâàíèå òðàôèêà ñ ÿðêî âûðàæåííîé íåîäíîðîäíîñòüþ òðåáîâàíèé ê ðåñóðñó óõóäøàåò ïîêàçàòåëè îáñëóæèâàíèÿ ¾òÿæåëîãî¿ òðàôèêà. Ýòî ñâîéñòâî ïîêàçàíî äëÿ ìîäåëè ñ ïàðàìåòðàìè: v = 120 ê.å; n = 2; b1 = 1 ê.å; b2 = 30 ê.å; vρ ak = nb Ýðë, k = 1, 2.  èññëåäóåìîé ñèòóàöèè ðàçäåëüíîå çàíÿòèå ðåñóðñà k óñòðàíÿåò âîçìîæíîñòü ïðåèìóùåñòâåííîãî îáñëóæèâàíèÿ ¾ëåãêîãî¿ òðàôèêà. 1,00E+00 120 π k ,к ов яа з х ы нн яр ет оп ял о Д m k 1,00E-01 1,00E-02 1,00E-03 1,00E-04 Совместное использование ресурса 1,00E-05 1,00E-06 1,00E-07 Раздельное использование ресурса ,в 100 лоа на к х ы тя 80 на з ол си ч еен 60 де р С Совместное использование ресурса 40 Раздельное использование ресурса 1,00E-08 20 1,00E-09 1,00E-10 0,0 0,3 0,6 0,9 1,2 1,5 1,8 2,1 2,4 Загрузка канала, ρ 0,0 0,3 0,6 0,9 1,2 1,5 1,8 Загрузка канала, 2,1 ρ 2,4 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 53 / 79 Àíàëèç ìóëüòèïëåêñèðîâàíèÿ ìóëüòèñåðâèñíîãî òðàôèêà (6/6) I Íà ïðåäûäóùåì ñëàéäå áûëî ïîêàçàíî, ÷òî I  áîëüøèíñòâå ñëó÷àåâ ïðè ýòîì ïðîèñõîäèò óìåíüøåíèå êîýôôèöèåíòà çàíÿòèÿ åäèíèöû ðåñóðñà ïî ñðàâíåíèþ ñ ïåðåäà÷åé ïî îáùåé ñðåäå. I Âìåñòå ñ òåì, ìîæíî ïîäîáðàòü ñîîòíîøåíèå ìåæäó âõîäíûìè ïàðàìåòðàìè, ïðè êîòîðîì ðàçäåëüíîå èñïîëüçîâàíèå ðåñóðñà ïîâûøàåò çíà÷åíèå äàííîãî ïîêàçàòåëÿ. I Ýòîò ðåçóëüòàò ïîêàçàí íà äèàãðàììå äëÿ ìóëüòèñåðâèñíîé ìîäåëè Ýðëàíãà ñî çíà÷åíèÿìè ïàðàìåòðîâ: v = 120 ê.å; n = 2; b1 = 1 ê.å; b2 = 30 ê.å; vρ ak = nb Ýðë, k = 1, 2. k 1 Мультисервисная модель Эрланга δ ðàçäåëüíîå èñïîëüçîâàíèå ðåñóðñà óñòðàíÿåò âîçìîæíîñòü åãî ïåðåðàñïðåäåëåíèÿ â ïîëüçó îòäåëüíûõ âèäîâ òðàôèêà, åñëè ðå÷ü èäåò î ñîâìåñòíîé ïåðåäà÷å ìóëüòèìåäèéíûõ èíôîðìàöèîííûõ ïîòîêîâ ñ ÿðêî âûðàæåííîé íåîäíîðîäíîñòüþ. а,с ру се р ы ци ни де еи на во зь ло пс и ее нд ер С 0,9 0,8 Разделение ресурса 0,7 0,6 0,5 0,4 Разделение ресурса эффективнее, чем его совместное использование 0,3 0,2 0,1 0,85 0,0 0,3 0,6 0,9 1,26 1,2 1,5 1,8 Загрузка канала, 2,1 ρ 2,4 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 54 / 79 Àíàëèç ïðîöåäóðû äåìóëüòèïëåêñèðîâàíèÿ òðàôèêà (1/2) I  ðÿäå ñëó÷àåâ (íàïðèìåð, â ïðîöåññå ðåàëèçàöèè êîíöåïöèè Èíòåðíåòà âåùåé) âîçíèêàåò íåîáõîäèìîñòü ðàçäåëåíèÿ îáùåãî ðåñóðñà ïåðåäà÷è (ñëàéñèíã) äëÿ îáñëóæèâàíèÿ îòäåëüíûõ ïîòîêîâ ìóëüòèñåðâèñíîãî òðàôèêà. I Ïðè ýòîì ìîãóò äîñòèãàòüñÿ ðàçíûå öåëè: à) âûðàâíèâàíèå ïîòåðü; á) äîñòèæåíèå ìàêñèìàëüíîãî ýêîíîìè÷åñêîãî ýôôåêòà; â) ïðåäîñòàâëåíèå ãàðàíòèðîâàííûõ ïîêàçàòåëåé QoS. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 55 / 79 Àíàëèç ïðîöåäóðû äåìóëüòèïëåêñèðîâàíèÿ òðàôèêà (2/2) • Ïðèìåð ðåàëèçàöèè ïðîöåäóðû ñëàéñèíãà.Ïóñòü: v = 100 ê.å.; n = 2; bk = 1, 10 ê.å; ak bk = 40, 40 ÝðëÊ. Ñëåâà ðåñóðñ ðàçäåëåí äëÿ âûðàâíèâàíèÿ ïîòåðü. Îòâåò: vk = 40, 60 ê.å. Ñïðàâà  äëÿ ìàêñ. äîõîäà R = a1 b1 (1 − π1 ) · r1 + a2 b2 (1 − π2 ) · r2 , ãäå rk = 3, 1 ó.å. Îòâåò: vk = 50, 50 ê.å, R = 150 ó.å., k = 1, 2. Õàðàêòåðèñòèêè îáùåãî îáñëóæèâàíèÿ: π1 = 0,0126; π2 = 0,1521; R = 152,4 ó.å. ко ява з рье то п ы ни ичл е В 1 .е у. 0,8 д ох о д й ы н в о л сУ 0,6 150 140 130 120 110 100 90 1 80 2 70 0,4 60 50 40 0,2 30 0,116 20 10 20 40 60 80 100 Ресурс, используемый 1-м потоком, v1 (к.е.) 20 40 50 60 80 100 Ресурс, используемый 1-м потоком, v1 (к.е.) Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 56 / 79 Îöåíêà òðåáóåìîãî ïî íàãðóçêå ðåñóðñà: òðàäèöèîííûé àëãîðèòì 1. Çàäàþòñÿ íåîáõîäèìûå èñõîäíûå äàííûå. Ê íèì îòíîñÿòñÿ: • çíà÷åíèÿ âõîäíûõ ïàðàìåòðîâ ìîäåëè n, ak , bk , k = 1, . . . , n, ôèêñèðîâàííûå íà âðåìÿ ðåøåíèÿ çàäà÷è; • ôóíêöèîíàë, çàâèñÿùèé îò êà÷åñòâà îáñëóæèâàíèÿ è ñòîèìîñòè ðåøåíèÿ, ýòî ëèáî âåëè÷èíà π ìàêñèìàëüíûõ ïîòåðü, ëèáî çíà÷åíèå π` äîëè ïîòåðÿííîé çàãðóçêè ëèíèè: π = max πk ; 1≤k≤n π` = a1 b1 π1 + . . . + an bn πn . a1 b1 + . . . + an bn • òðåáóåìîå ðåãóëÿòîðîì íîðìàòèâíîå çíà÷åíèå ôóíêöèîíàëà; • íà÷àëüíîå çíà÷åíèå êàíàëüíîãî ðåñóðñà r0 (îáû÷íî öåëàÿ ÷àñòü ñðåäíåãî ÷èñëà ïîòåíöèàëüíûõ ñîåäèíåíèé, âûðàæåííûõ â êàíàëüíûõ åäèíèöàõ) ò.å. r0 = b n X ak bk c. k=1 2. Ïðîèçâîäèòñÿ ðàñ÷¼ò çíà÷åíèÿ ôóíêöèîíàëà ñ èñïîëüçîâàíèåì ðåêóðñèè. . 3. Çíà÷åíèå ôóíêöèîíàëà ñðàâíèâàåòñÿ ñ íîðìàòèâíîé âåëè÷èíîé. Îöåíêà òðåáóåìîãî ÷èñëà êàíàëîâ v çàêàí÷èâàåòñÿ èëè ïðîäîëæàåòñÿ. 4. Òðóäîåìêîñòü îöåíêè íåîáõîäèìîãî ÷èñëà êàíàëîâ îïðåäåëÿåòñÿ ÷èñëîì øàãîâ ïåðåáîðà ïîòåíöèàëüíûõ âàðèàíòîâ ðåøåíèÿ ñôîðìóëèðîâàííîé çàäà÷è Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 57 / 79 Ïðèìåð ðåàëèçàöèè òðàäèöèîííîãî àëãîðèòìà îöåíêè ðåñóðñà 0,4 π 4 ,к ов яа з ьр тео п ял од яа нь ла ми ск а М 0,35 0,3 0,25 0,2 Минимально необходимая величина канального ресурса 0,15 0,1 0,05 200 210 220 230 240 250 260 270 280 290 Значение канального ресурса линии, 300 v (к.е ) . I Èñõîäíûå äàííûå: n = 4, b1 = 1 ê.å, b2 = 5 ê.å, b3 = 10 ê.å, b4 = 20 ê.å, 200 ak = nb Ýðë, k = 1, 2, 3, 4. k I Óñëîâèå âûáîðà v : π = max πk = π4 ≤ πnorm = 0,05. 1≤k≤4 I Îòâåò: v = 280 ê.å. ×èñëî øàãîâ ïåðåáîðà 81, ò.å. 81 ðàç èñïîëüçîâàëñÿ ðåêóðñèâíûé àëãîðèòì äëÿ îöåíêè π4 . Äëÿ êàæäîãî v íàõîäèëèñü çíà÷åíèÿ P (i), i = 0, 1, . . . , v , êîòîðûå çàòåì íîðìèðîâàëèñü. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 58 / 79 Ðåêóðñèÿ ïî ÷èñëó êàíàëîâ. Ìîäåëü Ýðëàíãà (1/3) I Äëÿ ìîíîñåðâèñíîé ìîäåëè Ýðëàíãà ðåêóðñèâíîå âûðàæåíèå, ñâÿçûâàþùåå çíà÷åíèÿ P (i) (ñì. ñëàéä 31), ïðèîáðåòàåò âèä: P (i) = 1 P (i − 1)a, i i = 0, 1, . . . , v. I Âûðàçèì P (i), i = 0, 1, . . . , v , ÷åðåç P (0) P (i) = P (0) ai , i! i = 0, 1, . . . , v. I Âûïîëíèì íîðìèðîâêó è íàéäåì äîëþ ïîòåðÿííûõ çàÿâîê av v! p(v) = E(v, a) = 1+a+ a2 2! + ... + av v! . I Ïðè îöåíêå âåëè÷èíû òðåáóåìîãî ðåñóðñà çíà÷åíèå E(v, a) ñðàâíèâàåòñÿ ñ íîðìàòèâíûì ïîêàçàòåëåì. Åñëè íåîáõîäèìûé ðåçóëüòàò íå äîñòèãíóò, òî ðåñóðñ óâåëè÷èâàåòñÿ íà åäèíèöó è ðàñ÷åòû âûïîëíÿþòñÿ çàíîâî. I Ýòîò ìåòîä èìååò ðÿä íåäîñòàòêîâ, îñîáåííî ÿðêî âèäèìûõ ïðè áîëüøèõ v : • âåðîÿòíîñòü P (0) ïðèíèìàåò êðàéíå ìàëûå çíà÷åíèÿ, ÷òî äåëàåò íåñòàáèëüíîé ðåàëèçàöèþ àëãîðèòìà íà ñðåäñòâàõ âû÷èñëèòåëüíîé òåõíèêè. • äëÿ îöåíêè äîñòàòî÷íîñòè ðåñóðñà èñïîëüçóåòñÿ òîëüêî âåðîÿòíîñòü p(v), íî ïðè åå âû÷èñëåíèè íàõîäÿòñÿ çíà÷åíèÿ âñåõ p(i), i = 0, 1, . . . , v . Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 59 / 79 Ðåêóðñèÿ ïî ÷èñëó êàíàëîâ. Ìîäåëü Ýðëàíãà (2/3) I Äëÿ îöåíêè v , îáåñïå÷èâàþùåãî çàäàííîå êà÷åñòâî îáñëóæèâàíèÿ π , ôóíêöèÿ E(v, a) ïðèâîäèòñÿ ê âèäó E(v, a) = av v! 1 + a + ... + av v! = h av−1 (v−1)! ×a v i 1 + a + . . . + (v−1)! + av−1 av−1 (v−1)! × a v . I Ïîñëå äåëåíèÿ ÷èñëèòåëÿ è çíàìåíàòåëÿ íà âûðàæåíèå â [·] è çàìåíû v íà r ïîëó÷àåì ðåêóðñèþ äëÿ îöåíêè âåëè÷èíû E(v, a). Ðåêóðñèÿ âåäåòñÿ ïî ÷èñëó êàíàëîâ è ïðè åå ðåàëèçàöèè èñïîëüçóþòñÿ òîëüêî íîðìèðîâàííûå âåðîÿòíîñòè E(r, a) = aE(r − 1, a) , r + aE(r − 1, a) r = 1, . . . , v, (E(0, a) = 1). I Òðåáóåìîå ÷èñëî êàíàëîâ v íàõîäèòñÿ ïðè ïåðâîì âûïîëíåíèè íåðàâåíñòâà E(r, a) = aE(r − 1, a) ≤ π, r + aE(r − 1, a) r = 1, . . . I Äëÿ îöåíêè ïîòåðü è âûïîëíåíèÿ ñëåäóþùåãî øàãà ðåêóðñèè äîñòàòî÷íî êàæäûé ðàç çíàòü òîëüêî âåðîÿòíîñòü ñîñòîÿíèÿ ñ ìàêñèìàëüíûì ÷èñëîì çàíÿòûõ åäèíèö ðåñóðñà. Ðåêóðñèþ ìîæíî íà÷èíàòü è ñ ïðîìåæóòî÷íîãî çíà÷åíèÿ r < v , åñëè èçâåñòíî çíà÷åíèå E(r, a). Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 60 / 79 7 7 6 6 5 5 Состояния модели, участвующие в вычислениях 4 3 4 3 2 2 1 1 Состояния модели, участвующие в 8 7 7 Начало рекурсий с промежуточного значения числа единиц ресурса 6 6 = 5 5 5 4 4 3 3 2 2 1 1 8 вычислениях Состояния модели, не участвующие в вычислениях 8 Состояния модели 8 Состояния модели, не участвующие в вычислениях Состояния модели Ðåêóðñèÿ ïî ÷èñëó êàíàëîâ. Ìîäåëü Ýðëàíãà (3/3) 1 2 3 4 5 6 7 8 Переменное значение числа единиц ресурса 1 2 3 4 5 6 7 8 Переменное значение числа единиц ресурса I Ñëåâà ïîêàçàíà ðåàëèçàöèÿ ðåêóðñèè ñ íà÷àëüíîãî çíà÷åíèÿ r = 0. I Ñïðàâà ïîêàçàíà ðåàëèçàöèÿ ðåêóðñèè ñ íà÷àëüíîãî çíà÷åíèÿ r = 5. Âåëè÷èíà E(r, a) ëèáî èçâåñòíà çàðàíåå, ëèáî ðàññ÷èòûâàåòñÿ èç ñîîòíîøåíèé äåòàëüíîãî áàëàíñà (êàê íà ðèñóíêå). Âûáîð íà÷àëüíîãî óñëîâèÿ çàâèñèò îò èñõîäíûõ äàííûõ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 61 / 79 Ðåêóðñèÿ ïî ÷èñëó êàíàëîâ. Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà (1/6) I Îáîçíà÷èì äëÿ ìóëüòèñåðâèñíîé ìîäåëè Ýðëàíãà ÷åðåç Ps (i) íåíîðìèðîâàííóþ âåðîÿòíîñòü çàíÿòîñòè i åäèíèö ðåñóðñà ëèíèè ïðè èõ îáùåì ÷èñëå s. Ïóñòü b = max1≤k≤n bk  ìàêñèìàëüíîå òðåáîâàíèå çàÿâîê ê ðåñóðñó ïåðåäà÷è. I Íà÷àëüíûé øàã îðãàíèçàöèè ðåêóðñèè ïðè ÷èñëå åäèíèö ðåñóðñà, ðàâíîì r − 1. Âûðàçèì ñ ïîìîùüþ ôîðìóëû (ñì. ñëàéä 31) P (i) = n X 1 × ak bk P (i − bk ) i k=1 íåíîðìèðîâàííûå âåðîÿòíîñòè P (i) ÷åðåç P (0). Ïîëó÷àåì çíà÷åíèÿ Pr−1 (0), Pr−1 (1), . . . , Pr−1 (r − 1). Íîðìèðîâêà äà¼ò âåðîÿòíîñòè pr−1 (0), pr−1 (1), . . . , pr−1 (r − 1). Îíè òàêæå óäîâëåòâîðÿþò èñïîëüçîâàííîìó ñîîòíîøåíèþ. I Ñëåäóþùèé øàã ðåêóðñèè. Ðàññ÷èòûâàåì ïîòåðè. Åñëè àíàëèçèðóåìîãî ÷èñëà åäèíèö ðåñóðñà íåäîñòàòî÷íî, òî îíî óâåëè÷èâàåòñÿ íà åäèíèöó äî çíà÷åíèÿ r è ðàñ÷¼òû ïðîâîäÿòñÿ çàíîâî. Ïîêàæåì, ÷òî äëÿ äëÿ âû÷èñëåíèÿ ïîòåðü è ðåàëèçàöèè àëãîðèòìà ïðè îáùåì ÷èñëå åäèíèö ðåñóðñà r, r + 1 è ò.ä., äîñòàòî÷íî çíàòü çíà÷åíèÿ b ñòàöèîíàðíûõ âåðîÿòíîñòåé ñîñòîÿíèé ñ ìàêñèìàëüíûì ÷èñëîì çàíÿòûõ åäèíèö ðåñóðñà. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 62 / 79 Ðåêóðñèÿ ïî ÷èñëó êàíàëîâ. Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà (2/6) I Íàéäåì Pr (i), äëÿ i = 0, 1, . . . , r. Íà÷àëüíîå çíà÷åíèå ðåêóðñèè âûáåðåì èç âûðàæåíèÿ Pr (0) = pr−1 (0). Ïîñêîëüêó ðåêóðñèÿ íå èçìåíèëàñü, òî äëÿ èñïîëüçóåìîãî âûáîðà íà÷àëüíîãî óñëîâèÿ ïîëó÷àåì ñîîòíîøåíèÿ Pr (0) = pr−1 (0), Pr (1) = pr−1 (1), ... Pr (r − 1) = pr−1 (r − 1), Çíà÷åíèå Pr (r) ðàññ÷èòûâàåòñÿ ñ èñïîëüçîâàíèåì íàéäåííûõ âåðîÿòíîñòåé èç ðåêóðñèâíîé ôîðìóëû Pr (r) = n n 1X 1X ak bk Pr (r − bk ) = ak bk pr−1 (r − bk ). r k=1 r k=1 I Âûïîëíèì íîðìèðîâêó è íàéäåì pr (r) pr (r) = Pr (r) = Pr (0) + Pr (1) + · · · + Pr (r − 1) + Pr (r) = Pr (r) Pr (r) = . pr−1 (0) + pr−1 (1) + · · · + pr−1 (r − 1) + Pr (r) 1 + Pr (r) Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 63 / 79 Ðåêóðñèÿ ïî ÷èñëó êàíàëîâ. Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà (3/6) I Èñïîëüçóÿ íàéäåííîå âûðàæåíèå äëÿ Pr (r), ïîëó÷àåì ôîðìóëó äëÿ îöåíêè pr (r) ÷åðåç çíà÷åíèÿ b âåðîÿòíîñòåé pr−1 (i) ñ ìàêñèìàëüíûì çàíÿòûì ðåñóðñîì i 1 r pr (r) = 1+ n P ak bk pr−1 (r − bk ) k=1 n 1 P ak bk pr−1 (r − bk ) r k=1 . I Çíà÷åíèÿ âåðîÿòíîñòåé pr (r − 1), . . . , pr (r − b + 1) íàõîäÿòñÿ ïîñëå íîðìèðîâêè èç àíàëîãè÷íûõ ñîîòíîøåíèé pr−1 (i) pr (i) = 1+ 1 r n P , i = r−1, r−2, . . . , r−b+1 . ak bk pr−1 (r − bk ) k=1 I Íàáîð âåðîÿòíîñòåé pr (i), i = r, r − 1, . . . , r − b + 1 ïîçâîëÿåò îöåíèòü ïîòåðè. Åñëè èõ óðîâåíü íå äîñòèãíóò, òî r óâåëè÷èâàåòñÿ íà åäèíèöó. Äàëåå, èñïîëüçóÿ pr (i), i = r, r − 1, . . . , r − b + 1 ðàññ÷èòûâàåòñÿ íîðìèðîâî÷íàÿ êîíñòàíòà äëÿ ÷èñëà n êàíàëîâ r + 1 1 X ak bk pr (r + 1 − bk ) 1+ r + 1 k=1 è ñëåäóþùèé íàáîð èç b âåðîÿòíîñòåé pr+1 (i) ñ ìàêñèìàëüíûì ÷èñëîì çàíÿòûõ åäèíèö ðåñóðñà. Ýòè äåéñòâèÿ ïîâòîðÿþòñÿ äî òåõ ïîð ïîêà òðåáóåìûé îáúåì ðåñóðñà íå áóäåò ïîëó÷åí. Èçëîæèì ïåðå÷èñëåííûå äåéñòâèÿ â âèäå àëãîðèòìà. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 64 / 79 Ðåêóðñèÿ ïî ÷èñëó êàíàëîâ. Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà (4/6) 1. Ðåàëèçàöèÿ àëãîðèòìà ñ ïðîìåæóòî÷íîãî çíà÷åíèÿ ÷èñëà êàíàëîâ r − 1 ≥ b. 2. Ïîëîæèì Pr−1 (0) = 1 è âûðàçèì Pr−1 (i) ÷åðåç Pr−1 (0), èñïîëüçóÿ ñîîòíîøåíèå n X 1 × ak bk P (i − bk ), i = 1, 2, . . . , r − 1. i k=1 Ïîñëå íîðìèðîâêè íàõîäèì b âåðîÿòíîñòåé ñ ìàêñèìàëüíûì çàíÿòûì ðåñóðñîì pr−1 (r − 1), pr−1 (r − 2), . . . , pr−1 (r − b). P (i) = 3. Äàëåå îöåíèâàåòñÿ êà÷åñòâî îáñëóæèâàíèÿ (ñì. ï.4). Åñëè òðåáóåìûé óðîâåíü íå äîñòèãíóò, òî îáúåì ðåñóðñà óâåëè÷èâàåòñÿ äî r è íàõîäÿòñÿ b íîðìèðîâàííûõ âåðîÿòíîñòåé pr (i), i = r, r−1, . . . , r − b + 1 ñ ìàêñèìàëüíûì çàíÿòûì ðåñóðñîì. Äëÿ ýòîãî èñïîëüçóþòñÿ àíàëîãè÷íûå âåðîÿòíîñòè, ïîëó÷åííûå íà ïðåäûäóùåì øàãå. Âíà÷àëå íàõîäèòñÿ íîðìèðîâî÷íàÿ êîíñòàíòà 1+ n X 1 × ak bk pr−1 (r−bk ) = 1 + Sr−1 , r k=1 à çàòåì ñàìè âåðîÿòíîñòè pr (r) = Sr−1 , 1 + Sr−1 i = r; pr (i) = pr−1 (i) , 1 + Sr−1 i = r−1, r−2, . . . , r − b + 1. 4. Äàëåå íàõîäèòñÿ çíà÷åíèå ôóíêöèîíàëà, íàïðèìåð, ìàêñèìóì ïîòåðü çàÿâîê π = pr (r − b + 1) + pr (r − b) + . . . + pr (r). Âåëè÷èíà π ñðàâíèâàåòñÿ ñ åãî íîðìàòèâíûì çíà÷åíèåì è, åñëè òðåáóåìûé óðîâåíü ïîòåðü íå äîñòèãíóò, ÷èñëî êàíàëîâ óâåëè÷èâàåòñÿ íà åäèíèöó è ðàñ÷åòû ïîâòîðÿþòñÿ, íà÷èíàÿ ñ ï.3. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 65 / 79 Ðåêóðñèÿ ïî ÷èñëó êàíàëîâ. Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà (5/6) 1. Ðåàëèçàöèÿ àëãîðèòìà, íà÷èíàÿ ñ íóëåâîãî çíà÷åíèÿ ÷èñëà êàíàëîâ. 2. Ïîëîæèì p0 (0) = 1. 3. Äëÿ êàæäîãî ôèêñèðîâàííîãî r = 1, 2, . . . íàõîäèì min(b, r + 1) íîðìèðîâàííûõ âåðîÿòíîñòåé pr (i), i = r, r−1, . . . , max(r − b + 1, 0) ñ ìàêñèìàëüíûì çàíÿòûì ðåñóðñîì. Äëÿ ýòîãî èñïîëüçóþòñÿ àíàëîãè÷íûå âåðîÿòíîñòè, ïîëó÷åííûå íà ïðåäûäóùåì øàãå. Âíà÷àëå íàõîäèòñÿ íîðìèðîâî÷íàÿ êîíñòàíòà 1+ n X 1 × ak bk pr−1 (r−bk ) = 1 + Sr−1 , r k=1 à çàòåì ñàìè âåðîÿòíîñòè pr (r) = Sr−1 , 1 + Sr−1 i = r; pr (i) = pr−1 (i) , 1 + Sr−1 i = r−1, r−2, . . . , r − b + 1. 4. Äàëåå íàõîäèòñÿ çíà÷åíèå ôóíêöèîíàëà, íàïðèìåð, ìàêñèìóì ïîòåðü çàÿâîê π = pr (r − b + 1) + pr (r − b) + . . . + pr (r). Âåëè÷èíà π ñðàâíèâàåòñÿ ñ åãî íîðìàòèâíûì çíà÷åíèåì è, åñëè òðåáóåìûé óðîâåíü ïîòåðü íå äîñòèãíóò, òî ÷èñëî êàíàëîâ óâåëè÷èâàåòñÿ íà åäèíèöó è ðàñ÷åòû ïîâòîðÿþòñÿ, íà÷èíàÿ ñ ï.3. I Îáå âåðñèè àëãîðèòìà ïîçâîëÿþò âåñòè ðåêóðñèþ ïî ÷èñëó åäèíèö ðåñóðñà. Äëÿ ðàñ÷åòà õàðàêòåðèñòèê è âûïîëíåíèÿ ñëåäóþùåãî øàãà äîñòàòî÷íî çíàòü b âåðîÿòíîñòåé ñîñòîÿíèé ñ ìàêñèìàëüíûì çàíÿòûì ðåñóðñîì. Âûáîð àëãîðèòìà çàâèñèò îò íà÷àëüíûõ óñëîâèé. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 66 / 79 8 7 7 7 6 6 6 5 Начало рекурсий с промежуточного значения числа единиц ресурса 6 = 5 5 5 5 4 4 4 3 3 2 2 1 1 1 2 3 4 5 6 7 8 Переменное значение числа единиц ресурса 8 8 7 7 7 6 6 6 5 5 5 4 4 4 3 3 3 2 2 2 1 1 6 5 4 3 2 1 1 1 2 3 4 5 6 Состояния модели, не участвующие в вычислениях Состояния модели 8 Состояния модели, не участвующие в вычислениях Состояния модели Ðåêóðñèÿ ïî ÷èñëó êàíàëîâ. Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà (6/6) 7 8 Переменное значение числа единиц ресурса I Ñëåâà ïîêàçàíà ðåàëèçàöèÿ àëãîðèòìà ñ íà÷àëüíîãî çíà÷åíèÿ r = 5, ñïðàâà  ñ íà÷àëüíîãî çíà÷åíèÿ r = 0. Ïðåäïîëàãàåòñÿ, ÷òî b = 3. I Äëÿ îöåíêè ïîòåðü è âûïîëíåíèÿ ñëåäóþùåãî øàãà ðåêóðñèè äîñòàòî÷íî çíàòü âåðîÿòíîñòè òðåõ ñîñòîÿíèé ñ ìàêñèìàëüíûì ÷èñëîì çàíÿòûõ åäèíèö ðåñóðñà. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 67 / 79 Ïðèìåð ðåàëèçàöèè ðåêóðñèè ïî ÷èñëó êàíàëîâ (7/8) I Èñõîäíûå äàííûå: v = 5 ê.å, n = 2, b1 = 1 ê.å, b2 = 2 ê.å, a1 = 2 Ýðë, a2 = 1 Ýðë. Íàéä¼ì ÷èñëî êàíàëîâ, äîñòàòî÷íîå äëÿ îáñëóæèâàíèÿ ïîñòóïàþùèõ ïîòîêîâ çàÿâîê ñ äîëåé ïîòåðü, íå ïðåâûøàþùåé 0,05. Ìàêñèìàëüíûå ïîòåðè çàÿâîê áóäóò ó 2-ãî ïîòîêà: π2 = p(v) + p(v − 1). Íà÷íåì ðåêóðñèþ ñî çíà÷åíèÿ r = 0. I Ïåðâûé øàã àëãîðèòìà: p0 (0) = 1. I Ðåêóðñèâíûå âûðàæåíèÿ äëÿ îöåíêè pr (r) è pr (r − 1) äëÿ r, ïðèíèìàþùèõ ïîñëåäîâàòåëüíûå çíà÷åíèÿ 1, 2, . . ., ôîðìèðóþòñÿ ñëåäóþùèì îáðàçîì. Âíà÷àëå ñ èñïîëüçîâàíèåì àíàëîãè÷íûõ âåðîÿòíîñòåé, ïîëó÷åííûõ íà ïðåäûäóùåì øàãå, íàõîäèòñÿ íîðìèðîâî÷íàÿ êîíñòàíòà 1+  2  × pr−1 (r − 1) + pr−1 (r − 2) = 1 + Sr−1 . r à çàòåì ñàìè âåðîÿòíîñòè pr (r) = Sr−1 , 1 + Sr−1 pr (r − 1) = pr−1 (r − 1) . 1 + Sr−1 I Ðåàëèçàöèÿ ðåêóðñèé ïðèâîäèò ê òàêèì ðåçóëüòàòàì 2 1 = 0,667, p1 (0) = = 0,333, π2 = 1; 3 3 1 1 p2 (2) = = 0,5, p2 (1) = = 0,333, π2 = 0,833; 2 3 5 9 p3 (3) = = 0,357, p3 (2) = = 0,321, π2 = 0,678; 14 28 p1 (1) = Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 68 / 79 Ïðèìåð ðåàëèçàöèè ðåêóðñèè ïî ÷èñëó êàíàëîâ (8/8) I Ïðîäîëæåíèå ðåêóðñèâíîãî ñ÷åòà íîðìèðîâàííûõ âåðîÿòíîñòåé p4 (4) = p5 (5) = 0,339 = 0,253, 1,339 0,208 = 0,172, 1,208 p4 (3) = p5 (4) = 0,357 = 0,267, 1,339 0,253 = 0,209, 1,208 π2 = 0,520; π2 = 0,381; 0,127 0,172 = 0,113, p6 (5) = = 0,153, π2 = 0,266; 1,127 1,127 0,113 0,076 = 0,071, p7 (6) = = 0,105, π2 = 0,176; p7 (7) = 1,076 1,076 0,044 0,071 p8 (8) = = 0,042, p8 (7) = = 0,068, π2 = 0,110; 1,044 1,044 0,024 0,0421 p9 (9) = = 0,023, p9 (8) = = 0,041, π2 = 0,064. 1,024 1,024 0,0128 0,023 p10 (10) = = 0,013, p10 (9) = = 0,023, π2 = 0,036 1,0128 1,0128 p6 (6) = I Çíà÷åíèå π2 , íàéäåííîå ïðè r = 5, ñ òî÷íîñòüþ äî îêðóãëåíèÿ ñîâïàäàåò ñ âåëè÷èíîé π2 , ðàññ÷èòàííîé ñ èñïîëüçîâàíèåì äðóãèõ àëãîðèòìîâ (ñì. ñòð. 28,32). Ðåøåíèå çàäà÷è ïîëó÷åíî ïðè r = 10. Íà êàæäîì øàãå àëãîðèòìà íåçàâèñèìî îò r íàõîäÿòñÿ òîëüêî äâà çíà÷åíèÿ ñòàöèîíàðíûõ âåðîÿòíîñòåé. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 69 / 79 Ýôôåêòèâíîñòü îïòèìèçèðîâàííîãî àëãîðèòìà îöåíêè ðåñóðñà (1/2) I Âõîäíûå ïàðàìåòðû: n = 4, b1 = 1 ê.å, b2 = 3 ê.å, b3 = 5 ê.å, b4 = 10 ê.å, ak = nAb , k = 1, 2, 3, 4. k Óñëîâèå äîñòàòî÷íîñòè ðåñóðñà ïåðåäà÷è èíôîðìàöèè: max πk < 0,01. 1≤k≤n I  òàáëèöå ïðèâåäåíû ðåçóëüòàòû ñðàâíåíèÿ ÷èñëà îïåðàöèé, çàòðà÷åííûõ ïðè èñïîëüçîâàíèè òðàäèöèîííîãî è îïòèìèçèðîâàííîãî àëãîðèòìîâ ïðè îïðåäåëåíèè òðåáóåìîãî ïî íàãðóçêå ÷èñëà êàíàëîâ ìóëüòèñåðâèñíîãî óçëà äîñòóïà. Êîëè÷åñòâî îïåðàöèé ïðè èñïîëüçîâàíèè îïòèìèçèðîâàííîãî àëãîðèòìà ïðèíÿòî çà åäèíèöó. A (ÝðëÊ) 100 200 300 500 750 1000 2000 3000 5000 Êàíàëüíàÿ ¼ìêîñòü v (ê.å.) 161 277 389 607 873 1136 2171 3194 5225 Òðàäèöèîííàÿ ñõåìà 36,4 62,2 87,1 135,5 194,7 253,1 483,1 710,4 1161,8 Îïòèìèçèðîâàííàÿ ñõåìà 1 1 1 1 1 1 1 1 1 Çíà÷åíèå π4 0,00950 0,00994 0,00988 0,00974 0,00986 0,00983 0,00991 0,00994 0,00993 Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 70 / 79 Ýôôåêòèâíîñòü îïòèìèçèðîâàííîãî àëãîðèòìà îöåíêè ðåñóðñà (2/2) I Ïðè ïðîâåäåíèè âû÷èñëåíèé íå âîçíèêàåò ïðîáëåì ñ ïåðåïîëíåíèåì èëè èñ÷åçíîâåíèåì ïîðÿäêà, ïîñêîëüêó ðàñ÷¼òû âûïîëíÿþòñÿ òîëüêî ñ íîðìèðîâàííûìè çíà÷åíèÿìè âåðîÿòíîñòåé ñîñòîÿíèé ìîäåëè ñ ìàêñèìàëüíûì ÷èñëîì çàíÿòûõ åäèíèö ðåñóðñà. Ïî óñëîâèÿì àíàëèçà ìîäåëè îíè èìåþò íàèáîëüøèå îòíîñèòåëüíûå çíà÷åíèÿ. I Ïî ñðàâíåíèþ ñ òðàäèöèîííûì ìåòîäîì îïòèìèçèðîâàííûé àëãîðèòì ñîêðàùàåò ðàñ÷åòíóþ ðàáîòó ïðè îöåíêå òðåáóåìîãî ÷èñëà êàíàëîâ ìóëüòèñåðâèñíîãî óçëà äîñòóïà ïðèìåðíî â v/(2 + nb ) ðàç (ñì. òàáëèöó íà ñëàéäå 69). I Ðàññìîòðåííûé ïîäõîä ê ïîñòðîåíèþ ýôôåêòèâíûõ ðàñ÷åòíûõ àëãîðèòìîâ îöåíêè ÷èñëà êàíàëîâ ìîæåò áûòü òàêæå ðåàëèçîâàí è äëÿ äðóãèõ ìîäåëåé ìóëüòèñåðâèñíûõ óçëîâ, åñëè çíà÷åíèÿ ñòàöèîíàðíûõ âåðîÿòíîñòåé ñîñòîÿíèé ÷èñëà çàíÿòûõ êàíàëîâ ñâÿçàíû ðåêóðñèâíûìè ñîîòíîøåíèÿìè ñî ñâîéñòâàìè, ïîêàçàííûìè íà ñëàéäå 31. I Äëÿ áîëüøèõ çíà÷åíèé v îáëàñòü ñîñòîÿíèé ñ íàèáîëüøèìè çíà÷åíèÿìè âåðîÿòíîñòåé ëîêàëèçîâàíà â íåïîñðåäñòâåííîé áëèçîñòè îò ñîñòîÿíèÿ (v) (ñì. ñëàéäû 36 è 37).  ýòîé ñèòóàöèè äëÿ îöåíêè ïîòåðü ìîæíî èñïîëüçîâàòü òîëüêî ñîñòîÿíèÿ (`), (` + 1), . . . , (v), ãäå `  óðîâåíü óðåçàíèÿ èñïîëüçóåìîãî ïðîñòðàíñòâà ñîñòîÿíèé. Ðåêóðñèþ ïî ÷èñëó êàíàëîâ ìîæíî íà÷àòü ñ ñîñòîÿíèÿ (`) è äàëåå äåéñòâîâàòü â ñîîòâåòñòâèè ñ àëãîðèòìîì, ïîêàçàííûì íà ñëàéäå 65. Ðåçóëüòàò îöåíêè ÷èñëà êàíàëîâ áóäåò ïðèáëèæåííûì, íî îòëè÷àþùèìñÿ âûñîêîé òî÷íîñòüþ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 71 / 79 Îöåíêà ìàêñèìàëüíî äîïóñòèìîé âåëè÷èíû òðàôèêà (1/2) I Èñõîäíûå äàííûå: • ÷èñëî åäèíèö ðåñóðñà v è ÷èñëî ïîòîêîâ çàÿâîê n; • òðåáîâàíèÿ ê ðåñóðñó ïåðåäà÷è bk , k = 1, . . . , n; • ñîîòíîøåíèå ìåæäó èíòåíñèâíîñòÿìè ïðåäëîæåííîãî òðàôèêà îòäåëüíûõ ïîòîêîâ, âûðàæåííûìè â ýðëàíãî-êàíàëàõ, a1 b1 : a2 b2 : . . . : an bn = x1 : x2 : . . . : xn . I Çàäà÷à. Îïðåäåëèòü ìàêñèìàëüíûå çíà÷åíèÿ ïîòåíöèàëüíîãî òðàôèêà ak , k = 1, . . . , n ïðè êîòîðûõ ìàêñèìóì ïîòåðü çàÿâîê π íå áóäóò ïðåâîñõîäèòü πíîðì. I Ðåøåíèå. Îáîçíà÷èì ÷åðåç z êîýôôèöèåíò ïðîïîðöèîíàëüíîñòè â ñîîòíîøåíèÿõ ìåæäó ïðåäëîæåííûì òðàôèêîì. Òîãäà ak bk = zxk , k = 1, . . . , n. I Îáîçíà÷èì ÷åðåç ρ ïîòåíöèàëüíóþ çàãðóçêó ê.å. Ïî îïðåäåëåíèþ ρ= z(x1 + · · · + xn ) a1 b1 + . . . + an bn = v v I Èç ïîñëåäíèõ äâóõ ðàâåíñòâ ïîëó÷àåì èñêîìîå ñîîòíîøåíèå ak = vρxk , bk (x1 + · · · + xn ) k = 1, . . . , n. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 72 / 79 Îöåíêà ìàêñèìàëüíî äîïóñòèìîé âåëè÷èíû òðàôèêà (2/2) π 4 к,о вя аз ьр ет оп ял од яа нь ла ми кса М 0,3 0,25 Определение максимального объема трафика, который может быть обслужен на линии при заданных потерях и скорости передачи 0,2 0,15 0,1 Максимально возможная загрузка единицы ресурса 0,05 0,73 0,1 0,2 0,3 0,4 0,5 0,6 0,7 Загрузка единицы ресурса, 0,8 0,9 1,0 ρ I Âîçüìåì v = 300 (ê.å.), n = 4; b1 = 1, b2 = 5, b3 = 10, b4 = 20 (ê.å.); xk = 1, k = 1, 2, 3, 4. Ìåíÿÿ ρ âåëè÷èíó çàãðóçêè ê.å., íàõîäèì çíà÷åíèå ρ∗ = 0,73 Ýðëê., ïðè êîòîðîì äîñòèãàåòñÿ òðåáóåìûé óðîâåíü ïîòåðü çàÿâîê π4 = 0,05. Äàëåå ðàññ÷èòûâàþòñÿ âåëè÷èíû ïðåäëîæåííîãî òðàôèêà äëÿ êàæäîãî ïîòîêà ak = vρ∗ xk /(x1 + x2 + x3 + x4 ), k = 1, 2, 3, 4 . Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 73 / 79 Ýêîíîìè÷åñêèå àñïåêòû îöåíêè ñêîðîñòè ïåðåäà÷è I Èñõîäíûå äàííûå. Ïðåäïîëîæèì, ÷òî ñîçäàíèå è ïîääåðæêà â ðàáî÷åì ñîñòîÿíèè åäèíèöû ðåñóðñà (ïóñòü ýòî áóäåò 1 Ìáèò/c) ñòîèò îïåðàòîðó 1 ó.å./åä.âð. Àðåíäà åäèíèöû ðåñóðñà ïîëüçîâàòåëÿìè óñëóã ñâÿçè ïðèíîñèò äîõîä 2 ó.å./åä.âð. I Èç äàííûõ ìàðêåòèíãîâûõ èññëåäîâàíèé èçâåñòíû õàðàêòåðèñòèêè ñåðâèñîâ n = 2; c1 = 1 Ìáèò/c; c2 = 10 Ìáèò/c è îáúåìû ïîòåíöèàëüíîãî òðàôèêà: a1 = 25 Ýðë.; a2 = 2,5 Ýðë. I Çàäà÷à. Íàéòè âåëè÷èíó C ñêîðîñòè ëèíèè, ïðè êîòîðîé åå âëàäåëåö ïîëó÷èò ìàêñèìàëüíûé äîõîä â åäèíèöó âðåìåíè îò îáñëóæèâàíèÿ ïðåäëîæåííîãî òðàôèêà I Ðåøåíèå. Ïðè ôèêñèðîâàííîì C äîõîä R îïðåäåëÿåòñÿ èç ñîîòíîøåíèÿ R = 2 × c × (m1 + m2 ) − 1 × C (ó.å./åä.âð.). ßñíî, ÷òî R èìååò ìàêñèìóì. Åãî âåëè÷èíà îïðåäåëÿåòñÿ ìåòîäîì ïîñëåäîâàòåëüíîãî óâåëè÷åíèÿ C . I Ïðè C = 53 Ìáèò/c äîõîä ïðèíèìàåò ìàêñèìàëüíîå çíà÷åíèå R = 25,98 ó.å./åä.âð. Îäíàêî ïðè ýòîé ñêîðîñòè ïåðåäà÷è π = max(π1 , π2 ) = 0,38. Ýòî ãîâîðèò î ïëîõîì êà÷åñòâå äîñòóïà. Åñëè äîïîëíèòåëüíî ïîòðåáîâàòü âûïîëíåíèÿ ñîîòíîøåíèÿ π < 0,05, òî C = 85 Ìáèò/c, à R = 12,46 ó.å./åä.âð. 30 R ,а д ох о д наи чи л ев яа вно л с У 25,98 у.е. 25 20 15 10 5 53 Мбит/с 10 20 30 40 50 60 70 80 90 100 Скорость линии, C (Мбит/с) Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 74 / 79 Çàäàíèÿ äëÿ ñàìîñòîÿòåëüíîé ðàáîòû (1/3) Ëèíèÿ äîñòóïà, èìåþùàÿ ñêîðîñòü 12 Ìáèò/ñ, îáðàáàòûâàåò äâà ïîòîêà çàÿâîê íà ïåðåäà÷ó òðàôèêà âèäåîïðèëîæåíèé. Äëÿ îáñëóæèâàíèÿ çàÿâêè ïåðâîãî ïîòîêà òðåáóåòñÿ ñêîðîñòü 4 Ìáèò/ñ, âòîðîãî  6 Ìáèò/ñ. Ïîñòóïëåíèå çàÿâîê 1-ãî è 2-ãî ïîòîêîâ ïîä÷èíÿåòñÿ çàêîíó Ïóàññîíà ñ èíòåíñèâíîñòÿìè λ1 è λ2 ñîîòâåòñòâåííî, à äëèòåëüíîñòè çàíÿòèÿ ðåñóðñà ïåðåäà÷è èíôîðìàöèè èìåþò ýêñïîíåíöèàëüíîå ðàñïðåäåëåíèå ñ ïàðàìåòðàìè µ1 è µ2 ñîîòâåòñòâåííî. Âûïîëíèòü ñëåäóþùèå çàäàíèÿ, îòíîñÿùèåñÿ ê àíàëèçó ââåä¼ííîé ìîäåëè. 1. Îïðåäåëèòü ñîñòîÿíèå è êîìïîíåíòû ñëó÷àéíîãî ïðîöåññà r(t), êîòîðûé äàñò âîçìîæíîñòü îöåíèòü äëÿ êàæäîãî ïîòîêà äîëþ ïîòåðÿííûõ çàÿâîê è ñðåäíåå ÷èñëî çàíÿòûõ êàíàëüíûõ åäèíèö. Ïîÿñíèòü íàëè÷èå ìàðêîâñêîãî ñâîéñòâà ó ïðîöåññà r(t). 2. Èñïîëüçóÿ ëåêñèêîãðàôè÷åñêóþ íóìåðàöèþ, ïåðå÷èñëèòü è ðàçìåñòèòü â òàáëèöå ìíîæåñòâî S âîçìîæíûõ ñîñòîÿíèé ïðîöåññà r(t), óêàçàâ äëÿ êàæäîãî ñîñòîÿíèÿ êîëè÷åñòâî ñâîáîäíûõ è çàíÿòûõ êàíàëüíûõ åäèíèö, à òàêæå ïðèíàäëåæíîñòü ñîñòîÿíèÿ ê ïîäìíîæåñòâàì, êîãäà çàÿâêà 1-ãî èëè 2-ãî ïîòîêà ïîëó÷àåò îòêàç â îáñëóæèâàíèè. 3. Íà äâóìåðíîé ïëîñêîñòè èçîáðàçèòü ïðîñòðàíñòâî ñîñòîÿíèé S è óêàçàòü âñå ïåðåõîäû r(t) èç ñîñòîÿíèÿ â ñîñòîÿíèå. Îòìåòèòü ñîñòîÿíèÿ, êîãäà çàÿâêè 1-ãî èëè 2-ãî ïîòîêà ïîëó÷àþò îòêàç â îáñëóæèâàíèè. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 75 / 79 Çàäàíèÿ äëÿ ñàìîñòîÿòåëüíîé ðàáîòû (2/3) 4. Ñîñòàâèòü ñèñòåìó óðàâíåíèé ðàâíîâåñèÿ r(t) è îòâåòèòü íà âîïðîñ î íàëè÷èè èëè îòñóòñòâèè ñâîéñòâà ìóëüòèïëèêàòèâíîñòè ó ñòàöèîíàðíûõ âåðîÿòíîñòåé ñîñòîÿíèé ïðîöåññà. 5. Íàéòè äîëþ âðåìåíè, êîãäà ëèíèÿ ñâîáîäíà îò îáñëóæèâàíèÿ çàÿâîê 1-ãî ïîòîêà, åñëè λ1 = 2 çàÿâ./åä.âð. è λ2 = 1 çàÿâ./åä.âð.  êà÷åñòâå åäèíèöû âðåìåíè âûáðàíî ñðåäíåå âðåìÿ îáñëóæèâàíèÿ çàÿâêè 1-ãî ïîòîêà. Ñðåäíåå âðåìÿ îáñëóæèâàíèÿ çàÿâêè 2-ãî ïîòîêà â äâà ðàçà áîëüøå, ÷åì ó 1-ãî. 6. Âûïîëíèòü çàäàíèå 75 â ñèòóàöèè, êîãäà âðåìÿ îáñëóæèâàíèÿ çàÿâêè 1-ãî ïîòîêà ïîñòîÿííî ñ òåì æå ñðåäíèì çíà÷åíèåì. 7. Âûïîëíèòü çàäàíèå 75 â ñèòóàöèè, êîãäà âðåìÿ îáñëóæèâàíèÿ çàÿâêè 1-ãî ïîòîêà ïîñòîÿííî ñ òåì æå ñðåäíèì çíà÷åíèåì. 8. Äëÿ çíà÷åíèé âõîäíûõ ïàðàìåòðîâ, èñïîëüçîâàííûõ â çàäàíèè 75, íàéòè äîëè âðåìåíè, êîãäà ëèíèÿ ñâîáîäíà îò îáñëóæèâàíèÿ çàÿâîê è êîãäà çàíÿòû âñå èìåþùèåñÿ êàíàëüíûå åäèíèöû. 9. Äëÿ çíà÷åíèé âõîäíûõ ïàðàìåòðîâ, èñïîëüçîâàííûõ â çàäàíèè 75, íàéòè äëÿ âñåõ ïîòîêîâ äîëþ ïîòåðÿííûõ çàÿâîê è ñðåäíåå ÷èñëî çàÿâîê, íàõîäÿùèõñÿ íà îáñëóæèâàíèè. 10. Îòâåòèòü íà âîïðîñ, ÷òî ïðîèçîéä¼ò ñ äîëåé ïîòåðÿííûõ çàÿâîê 1-ãî ïîòîêà, åñëè äëÿ îäíîãî èëè äëÿ äâóõ ïîòîêîâ èíòåíñèâíîñòè ïîñòóïëåíèÿ çàÿâîê è ïàðàìåòðû ýêñïîíåíöèàëüíîãî ðàñïðåäåëåíèÿ âðåìåíè îáñëóæèâàíèÿ çàÿâîê îäíîâðåìåííî óâåëè÷àòñÿ èëè óìåíüøàòñÿ â äâà ðàçà? Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 76 / 79 Çàäàíèÿ äëÿ ñàìîñòîÿòåëüíîé ðàáîòû (3/3) 11. Äëÿ çíà÷åíèé âõîäíûõ ïàðàìåòðîâ, èñïîëüçîâàííûõ â çàäàíèè 75, íàéòè ìèíèìàëüíóþ ñêîðîñòü ëèíèè, äîñòàòî÷íóþ äëÿ îáñëóæèâàíèÿ çàÿâîê 1-ãî è 2-ãî ïîòîêîâ ñ äîëåé ïîòåðü, íå ïðåâîñõîäÿùåé 3 %. 12. Íà ëþáîì àëãîðèòìè÷åñêîì ÿçûêå1 ñîñòàâèòü ïðîãðàììó ðåøåíèÿ èòåðàöèîííûì ìåòîäîì ÃàóññàÇåéäåëÿ23 ñèñòåìû óðàâíåíèé ðàâíîâåñèÿ ìóëüòèñåðâèñíîé ìîäåëè Ýðëàíãà è ÷èñëåííî ïðîâåðèòü íàëè÷èå ñâîéñòâà ìóëüòèïëèêàòèâíîñòè ñòàöèîíàðíûõ âåðîÿòíîñòåé ñîñòîÿíèé ìîäåëè. 13. Íà ëþáîì àëãîðèòìè÷åñêîì ÿçûêå ñîñòàâèòü ïðîãðàììó ðàñ÷¼òà ïîêàçàòåëåé îáñëóæèâàíèÿ çàÿâîê ìóëüòèñåðâèñíîé ìîäåëè Ýðëàíãà è ÷èñëåííî ïîêàçàòü, ÷òî ïðè îïðåäåë¼ííûõ ñîîòíîøåíèÿõ ìåæäó âõîäíûìè ïàðàìåòðàìè ìîäåëè êîýôôèöèåíò èñïîëüçîâàíèÿ åäèíèöû êàíàëüíîãî ðåñóðñà ïðè ñîâìåñòíîì îáñëóæèâàíèè çàÿâîê ìîæåò áûòü ìåíüøå, ÷åì ïðè èõ ðàçäåëüíîì îáñëóæèâàíèè. Ñôîðìóëèðîâàòü ðåêîìåíäàöèè ïî ðàçäåëåíèþ ðåñóðñà ïåðåäà÷è èíôîðìàöèè ïðè ñîâìåñòíîì îáñëóæèâàíèè çàÿâîê. 14. Ïðîöåññ ïîñòóïëåíèÿ è îáñëóæèâàíèÿ çàÿâîê íà ëèíèè äîñòóïà îïèñûâàåòñÿ ìóëüòèñåðâèñíîé ìîäåëüþ Ýðëàíãà. Íà ëþáîì àëãîðèòìè÷åñêîì ÿçûêå ñîñòàâèòü ïðîãðàììó îöåíêè ìèíèìàëüíîé ñêîðîñòè ëèíèè, äîñòàòî÷íîé äëÿ îáñëóæèâàíèÿ ïîñòóïàþùèõ çàÿâîê ñ äîëåé ïîòåðü, íå ïðåâîñõîäÿùåé çàäàííîãî çíà÷åíèÿ p. 1 Êóðñèâîì íàáðàíû çàäà÷è ïîâûøåííîé ñëîæíîñòè. 2 Ñòåïàíîâ Ñ.Í. Îñíîâû òåëåòðàôèêà ìóëüòèñåðâèñíûõ ñåòåé.  Ì.: ÝêîÒðåíäç, 2010.  392 c. 3 Ñòåïàíîâ Ñ.Í. Òåîðèÿ òåëåòðàôèêà: êîíöåïöèè, ìîäåëè, ïðèëîæåíèÿ.  Ì.: Ãîðÿ÷àÿ ëèíèÿ - Òåëåêîì, 2015.  868 ñ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 77 / 79 Êóðñîâàÿ ðàáîòà: (1/3) Îáùàÿ ôîðìóëèðîâêà çàäà÷è Ëèíèÿ äîñòóïà, èìåþùàÿ ñêîðîñòü C Ìáèò/ñ, îáðàáàòûâàåò äâà ïîòîêà çàÿâîê íà ïåðåäà÷ó òðàôèêà âèäåîïðèëîæåíèé. Äëÿ îáñëóæèâàíèÿ çàÿâêè ïåðâîãî ïîòîêà òðåáóåòñÿ ñêîðîñòü c1 Ìáèò/ñ, âòîðîãî  c2 Ìáèò/ñ. Ïîñòóïëåíèå çàÿâîê 1-ãî è 2-ãî ïîòîêîâ ïîä÷èíÿåòñÿ çàêîíó Ïóàññîíà ñ èíòåíñèâíîñòÿìè λ1 è λ2 ñîîòâåòñòâåííî, à äëèòåëüíîñòè çàíÿòèÿ ðåñóðñà ïåðåäà÷è èíôîðìàöèè èìåþò ýêñïîíåíöèàëüíîå ðàñïðåäåëåíèå ñ ïàðàìåòðàìè µ1 è µ2 ñîîòâåòñòâåííî. Âûïîëíèòü ñëåäóþùèå çàäàíèÿ, îòíîñÿùèåñÿ ê àíàëèçó ââåä¼ííîé ìîäåëè. 1. Îïðåäåëèòü ñîñòîÿíèå è êîìïîíåíòû ñëó÷àéíîãî ïðîöåññà r(t), êîòîðûé äàñò âîçìîæíîñòü îöåíèòü äëÿ êàæäîãî ïîòîêà äîëþ ïîòåðÿííûõ çàÿâîê è ñðåäíåå ÷èñëî çàíÿòûõ êàíàëüíûõ åäèíèö. Ïîÿñíèòü íàëè÷èå ìàðêîâñêîãî ñâîéñòâà ó ïðîöåññà r(t). 2. Èñïîëüçóÿ ëåêñèêîãðàôè÷åñêóþ íóìåðàöèþ, ïåðå÷èñëèòü è ðàçìåñòèòü â òàáëèöå ìíîæåñòâî S âîçìîæíûõ ñîñòîÿíèé ïðîöåññà r(t), óêàçàâ äëÿ êàæäîãî ñîñòîÿíèÿ êîëè÷åñòâî ñâîáîäíûõ è çàíÿòûõ êàíàëüíûõ åäèíèö, à òàêæå ïðèíàäëåæíîñòü ñîñòîÿíèÿ ê ïîäìíîæåñòâàì, êîãäà çàÿâêà 1-ãî èëè 2-ãî ïîòîêà ïîëó÷àåò îòêàç â îáñëóæèâàíèè. 3. Íà äâóìåðíîé ïëîñêîñòè èçîáðàçèòü ïðîñòðàíñòâî ñîñòîÿíèé S è óêàçàòü âñå ïåðåõîäû r(t) èç ñîñòîÿíèÿ â ñîñòîÿíèå. Îòìåòèòü ñîñòîÿíèÿ, êîãäà çàÿâêè 1-ãî èëè 2-ãî ïîòîêà ïîëó÷àþò îòêàç â îáñëóæèâàíèè. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 78 / 79 Êóðñîâàÿ ðàáîòà: (2/3) 4. Ñîñòàâèòü ñèñòåìó óðàâíåíèé ðàâíîâåñèÿ r(t) è ïðîâåðèòü íàëè÷èå ñâîéñòâà ìóëüòèïëèêàòèâíîñòè ó ñòàöèîíàðíûõ âåðîÿòíîñòåé ñîñòîÿíèé ïðîöåññà. 5. Ðàññ÷èòàòü çíà÷åíèÿ äîëè ïîòåðÿííûõ çàÿâîê è ñðåäíåé âåëè÷èíû ðåñóðñà ëèíèè çàíÿòîé èõ îáñëóæèâàíèåì, èñïîëüçóÿ ìóëüòèïëèêàòèâíîå ïðåäñòàâëåíèå ñòàöèîíàðíûõ âåðîÿòíîñòåé. 6. Ðàññ÷èòàòü ñ ïîìîùüþ ðåêóðñèâíîãî (ïî ÷èñëó ñîâìåñòíî çàíÿòûõ åäèíèö ðåñóðñà) àëãîðèòìà çíà÷åíèÿ ñòàöèîíàðíûõ âåðîÿòíîñòåé ÷èñëà ñîâìåñòíî çàíÿòûõ åäèíèö ðåñóðñà ëèíèè è çíà÷åíèÿ õàðàêòåðèñòèê îáñëóæèâàíèÿ ïîñòóïàþùèõ çàÿâîê. 7. Íàéòè ñ ïîìîùüþ îïòèìèçèðîâàííîãî ðåêóðñèâíîãî (ïî ÷èñëó èñïîëüçóåìûõ åäèíèö ðåñóðñà) àëãîðèòìà íîðìèðîâàííûå çíà÷åíèÿ ñòàöèîíàðíûõ âåðîÿòíîñòåé ÷èñëà ñîâìåñòíî çàíÿòûõ åäèíèö ðåñóðñà ëèíèè è ðàññ÷èòàòü çíà÷åíèÿ äîëè ïîòåðÿííûõ çàÿâîê è ñðåäíþþ âåëè÷èíó ðåñóðñà ëèíèè çàíÿòóþ èõ îáñëóæèâàíèåì 8. Äëÿ ðàññìàòðèâàåìîé ìîäåëè íàéòè ìèíèìàëüíîå çíà÷åíèå ñêîðîñòè ëèíèè, ïðè êîòîðîé âõîäÿùèå ïîòîêè çàÿâîê áóäóò îáñëóæèâàòüñÿ ñ äîëåé ïîòåðü çàÿâîê íå áîëüøåé 0,03. Ðåçóëüòàòû ïðîìåæóòî÷íûõ âû÷èñëåíèé ïîòåðü ïðåäñòàâèòü ãðàôè÷åñêè4 . 4 Äëÿ ðåøåíèÿ çàäà÷ 810 èñïîëüçîâàòü ñðåäñòâà ïðîãðàììèðîâàíèÿ Basic, Matlab, MathCad è ò.ï. Ðåçóëüòàòû âû÷èñëåíèé ïðåäñòàâèòü â âèäå ãðàôèêîâ. Ñ.Í. Ñòåïàíîâ Ñïåöãëàâû òåîðèè ìàññîâîãî îáñëóæèâàíèÿ / Ìóëüòèñåðâèñíàÿ ìîäåëü Ýðëàíãà 79 / 79 Êóðñîâàÿ ðàáîòà: (3/3) 9. Çà àðåíäó ñêîðîñòè ëèíèè â 1 Ìáèò/c ïðîäàâåö êîíòåíòà ïëàòèò îïåðàòîðó 1 ó.å., à çà èñïîëüçîâàíèå ñêîðîñòè ëèíèè 1 Ìáèò/c ïîëó÷àåò ñ êëèåíòîâ 2 ó.å. Íàéòè âåëè÷èíó ñêîðîñòè ëèíèè, ïðè êîòîðîé äîõîä ïðîäàâöà óñëóã äîñòèãíåò ìàêñèìóìà. ×åìó â ýòèõ óñëîâèÿõ áóäóò ðàâíû õàðàêòåðèñòèêè îáñëóæèâàíèÿ ïîñòóïàþùèõ çàÿâîê. Ïîñòðîèòü çàâèñèìîñòü äîõîäà îò ñêîðîñòè ëèíèè. 10. Íàéòè ñîîòíîøåíèÿ ìåæäó âõîäíûìè ïàðàìåòðàìè ìîäåëè, ïðè êîòîðûõ êîýôôèöèåíò èñïîëüçîâàíèÿ åäèíèöû êàíàëüíîãî ðåñóðñà ïðè ñîâìåñòíîì îáñëóæèâàíèè çàÿâîê áóäåò ìåíüøå, ÷åì ïðè èõ ðàçäåëüíîì îáñëóæèâàíèè. Ñôîðìóëèðîâàòü ðåêîìåíäàöèè ïî ðàçäåëåíèþ ðåñóðñà ïåðåäà÷è èíôîðìàöèè ïðè ñîâìåñòíîì îáñëóæèâàíèè çàÿâîê. Èíäèâèäóàëüíûå çíà÷åíèÿ âõîäíûõ ïàðàìåòðîâ (ñêîðîñòè âûðàæåíû â Ìáèò/ñ, à èíòåíñèâíîñòè â åäèíèöó âðåìåíè) è äîïîëíèòåëüíûé âîïðîñ 1. 2. I C = 14, c1 = 2, c2 = 4, λ1 = 4, λ2 = 6, I Ðàññ÷èòàòü çíà÷åíèå äîëè âðåìåíè, êîãäà ëèíèÿ ñâîáîäíà îò îáñëóæèâàíèÿ çàÿâîê 1-ãî ïîòîêîâ I C = 16, c1 = 2, c2 = 4, λ1 = 4, λ2 = 12, I µ1 = 1, µ1 = 1, µ2 = 4 µ2 = 6 Ðàññ÷èòàòü çíà÷åíèå äîëè âðåìåíè, êîãäà íà ëèíèè çàíÿòî áîëüøå ïîëîâèíû ðåñóðñà ïåðåäà÷è èíôîðìàöèè