Кіріспе
Компьютерлік желілердегі өнімділік кепілдіктерін талдаудың теориялық негізі. Желілік калькулус – "бір мезгілде жұмыс істейтін бағдарламалар, цифрлық тізбектер және коммуникациялық желілер сияқты адам жасаған жүйелер туралы түсінік беретін математикалық нәтижелер жиынтығы". Желілік калькулус компьютерлік желілердегі өнімділік кепілдіктерін талдау үшін теориялық базаны ұсынады. Трафик желі арқылы өтетін кезде, ол жүйе компоненттерінің тағайындаған шектеулеріне тап болады, мысалы:
* деректер байланысының сыйымдылығы
* трафик форматорлары (ағын реттегіштер)
* қанағаттандыруды басқару
* фондық трафик
Network calculus is "a set of mathematical results which give insights into man made systems such as concurrent programs, digital circuits and communication networks." Network calculus gives a theoretical framework for analysing performance guarantees in computer networks. As traffic flows through a network it is subject to constraints imposed by the system components, for example:
data link capacity
traffic shapers (leaky buckets)
congestion control
background traffic
These constraints can be expressed and analysed with network calculus methods. Constraint curves can be combined using convolution under min plus algebra. Network calculus can also be used to express traffic arrival and departure functions as well as service curves. The calculus uses "alternate algebras to transform complex non linear network systems into analytically tractable linear systems." Currently, there exists two branches in network calculus: one handling deterministic bounded, and one handling stochastic bounds.
Бұл шектеулерді желілік калькулус әдістерімен көрсетуге және талдауға болады. Шектеу қисықтарын min-плюс алгебрасы бойынша конволюция арқылы біріктіруге болады. Желілік калькулус трафик келу және кету функцияларын, сондай-ақ қызмет қисықтарын көрсету үшін де қолданылады. Калькулус "күрделі, сызықсыз желі жүйелерін аналитикалық түрде шешуге болатын сызықты жүйелерге түрлендіру үшін баламалы алгебраларды" пайдаланады. Қазіргі уақытта желілік калькулустың екі бағыты бар: біреуі детерминистік шектелген, ал екіншісі – стохастикалық шектелген.
Network calculus is "a set of mathematical results which give insights into man made systems such as concurrent programs, digital circuits and communication networks." Network calculus gives a theoretical framework for analysing performance guarantees in computer networks. As traffic flows through a network it is subject to constraints imposed by the system components, for example:
data link capacity
traffic shapers (leaky buckets)
congestion control
background traffic
These constraints can be expressed and analysed with network calculus methods. Constraint curves can be combined using convolution under min plus algebra. Network calculus can also be used to express traffic arrival and departure functions as well as service curves. The calculus uses "alternate algebras to transform complex non linear network systems into analytically tractable linear systems." Currently, there exists two branches in network calculus: one handling deterministic bounded, and one handling stochastic bounds.
Ағынды және серверді модельдеу
Желілік есепте, ағын A жиынтық функциясы ретінде модельделеді, мұнда A(t) [0, t) аралығында ағын жіберген дерек мөлшерін (мысалы, бит саны) көрсетеді. Мұндай функциялар теріс емес және өспейді. Уақыт домені көбінесе теріс емес нақты сандар жиынтығы болып табылады. Сервер – байланыс, жоспарлаушы, трафик қалыптастырушы немесе бүкіл желі болуы мүмкін. Ол жай ғана келу жиынтық қисығы A мен шығу жиынтық қисығы D арасындағы қатынас ретінде модельделеді. Деректердің шығуы оның келуінен бұрын болмайтынын модельдеу үшін A ≥ D болуы керек.
Модельдеудің артта қалуы мен кешігуі
Кейбір келу қисығы A және кету қисығы D берілген кезде, кез келген t уақытындағы қалдық, b(A,D,t) деп белгіленеді, A мен D арасындағы айырмашылық ретінде анықталады. t уақытындағы кешігу, d(A,D,t), – кету қисығы келу қисығына жететін ең аз уақыт ретінде анықталады. Ағындардың барлығын қарастырғанда, осы мәндердің жоғарғы шегі қолданылады. Әдетте, ағындар нақты белгілі емес, тек ағындар мен серверлерге қатысты кейбір шектеулер ғана белгілі (мысалы, белгілі бір кезеңде жіберілген пакеттердің максималды саны, пакеттердің максималды көлемі, ең төменгі байланыс ені). Желілік есептеудің мақсаты – осы шектеулерге сүйене отырып, кешігу мен қалдықтың жоғарғы шектерін есептеу. Осы үшін желілік есептеулер min-плюс алгебрасын пайдаланады.
Қызмет қисықтары
Трафик ағынына өнімділік кепілдемелерін ұсыну үшін сервердің ең төменгі өнімділігін анықтау қажет (желідегі резервтерге немесе жоспарлау саясатына байланысты және т.б.). Қызмет қисықтары ресурстардың қолжетімділігін бейнелеу тәсілін ұсынады. Әлсіз қатаң, өзгермелі сыйымдылық түйіні сияқты қызмет қисықтарының бірнеше түрі бар. Толық мәлімет алу үшін:
for an overview.
Қатаң минималды қызмет көрсету
A сервердің кірісіне келетін ағын болсын, ал D – шығыс нүктесінен кететін ағын. Артта қалған кезең – кез келген t ∈ I үшін A(t) > D(t) болатын I аралығы. Егер I артта қалған кезең болса, жүйе (A,B) жұбына қатаң минималды қызмет көрсету қисығы S-ті ұсынады. Егер сервер S қисығының қатаң минималды қызметін ұсынса, ол S қисығының қарапайым минималды қызметін де ұсынады.
If a server offers a strict minimal service of curve S, it also offers a simple minimal service of curve S.
Минималды-плюс есептеу
Минус-плюс алгебрасына арналған бірнеше құралдар мен кітапханалар бар. Желілік есептеу интерпретаторы – онлайн (минус,+) интерпретаторы. Нэнси – минус плюс және максимум плюс операцияларын іске асыратын C# кітапханасы. MIN plus ExpRession VErification (Minerve) – минус плюс операцияларының дұрыстығын тексеруге қолданылатын Coq кітапханасы. Барлық құралдар мен кітапханалар осы мақалада ұсынылған алгоритмдерге негізделген.
Оқиғалар
WoNeCa семинары – желілік есептеулер бойынша семинар. Ол екі жылда бір рет ұйымдастырылып, желілік есептеу теориясына қызығушылық танытқан зерттеушілерді, сондай-ақ қолданыстағы нәтижелерді жаңа қолданбаларға қолдануды қалағандарды біріктіреді. Семинар сонымен қатар желілік есептеу теориясын қолданбалы кезекші модельдерге қызығушылық танытқан зерттеушілерге насихаттауды қамтамасыз етеді. WoNeCa6, EPFL ұйымдастыруымен, 8 және 9 қыркүйекте 2022 жылы Швейцарияның Лозанна қаласында өтеді. Таныстыруларға шақыру осы жерде. WoNeCa5 2020 жылдың 9 қазанында COVID-19 пандемиясына байланысты онлайн форматта өтті. WoNeCa4 2018 жылдың 28 ақпанында Германияның Эрланген қаласында 19-шы Халықаралық GI/ITG конференциясымен бірге ұйымдастырылды. WoNeCa3 2016 жылдың 6 сәуірінде Германияның Мюстер қаласында MMB & DFT 2016 конференциясының бір бөлігі ретінде өтті. WoNeCa2 2014 жылдың 19 наурызында Германияның Бамберг қаласында MMB & DFT 2014 конференциясы аясында өтті. WoNeCa1 Кайзерслаутерн университетінде ұйымдастырылды және 2012 жылдың 21 наурызында Германияның Кайзерслаутерн қаласында MMB2012 аясында өтті. 2018 жылы Венада (Австрия) 30-шы Халықаралық телекоммуникациялық конгресс (ITC 30) аясында Желілік есептеулер және қолданбалар жөніндегі халықаралық семинар (NetCal 2018) өтті. 2024 жылы желілік есептеулер бойынша Dagstuhl семинары (24141) 1 сәуірден 4 сәуірге дейін Германияның Dagstuhl қаласында өтті.