Analytical model of distributed computing

Abstract


The major problems of the distributed computing technology development come from the interaction between software components spread over the network applications. The paper presents formal approaches to solve software components integration problem using Common Object Request Broker (CORBA) specifi cation. It introduces a system of functional models that allows us to study the interaction algorithms of the distributed system elements and make informed decisions about their planning. The article shows that the algorithm of software components distribution between the system’s processor modules can be based on a recurrent method of calculating the mutual data exchange frequency. The algorithm to distribute the minimum processing intervals of parallel executed requests is based on the forced suspension method. It identifi es the blocking states of processes and fi nds new implementation directions. The overhead reduction, determined by the methods of data exchange between distributed system elements, is ensured by the fragmentation of the whole set of system modules into disjoint areas. At the same time, network elements with the highest mutual exchange frequencies are included in each of the system fragments. The numerical results for the study were obtained with the standard tools of the Mathematica software package.

Full Text

Развитие систем промышленной автоматизации, телекоммуникаций, электронной коммерции, Интернета вещей, в которых отдельные элементы приложений должны быть распределены по сети и где уже находится огромное количество программных компонент типа Active-X, JavaBean, вызывает необходимость использования технологий создания и реализации распределенных приложений. Программные компоненты (ПК) распределённого по сети приложения, реализующего соответствующий бизнес-процесс, взаимодействуют друг с другом, создавая единый программный код. Основой такого взаимодействия в среде разнообразных аппаратных и программных платформ является, например, технология распределённых вычислений CORBA (Common Object Request Architecture) (см. рисунок 1 и [1-3]). Ядром технологии CORBA, обеспечивающим взаимодействие распределенных по сети ПК, является логическая шина ORB (Object RequestBroker) - брокер объектных запросов. ORB формирует механизмы выполнения и реализации запросов взаимодействующих ПК: поиск ПК разрабатываемого приложения, обмен необходимыми данными, объединение требуемых ресурсов, формирование распределенной системы, создание распределенного бизнес-приложения. Процесс-клиент инициирует операцию и через подсистему обмена производит вызов сообщения. ORB, используя широковещательную рассылку, находит требуемые ПК, активирует их, передает запрос и параметры, вызывает запрашиваемый метод и посредством брокера объектных запросов передает результаты вызываемому клиенту. При этом возникает необходимость количественной оценки данных алгоритмов интеграции ПК, исследования влияния процессов их взаимодействия на характеристики системы в целом. Задача исследования заключается в разработке и оценке моделей и методов построения системы интеграции ПК распределенных приложений на основе технологии CORBA [4-6]. Модели и методы системы интеграции программных компонент Модель взаимодействия ПК можно представить в виде замкнутой стохастической сети с центральным обслуживающим узлом (см. рисунок 2 и [1]). Брокер ORB формально представлен корневым узлом сети М, остальные М, остальные М () -1M узлов - компонентами физически распределенного по сети приложения, реализующего соответствующий бизнес-процесс. В такой системе ПК, связанные зависящими от соответствующих бизнес-процессов правилами, циркулируют между узлами сети, используя в качестве посредника центральный узел-брокер ORB. При этом переходные вероятности заявок класса можно описать следующей матрицей: ( ) ,1,1 ,1,2 ,1, ,2,1 ,2,2 ,2, , ,1 , ,2 , , ... ... . ... ... ... ... ... r r rM r r rMj ri r M r M rMM P P P P P P Pn P P P = (1) Здесь ( ) j ri Pn - вероятности перехода, j in - число заявок, перешедших из узла i в узел j. Считается, что в данной модели в каждом i-м узле сети время обслуживания распределено по экспоненциальному закону с параметром , iµ а взаимодействие ПК описывается многомерным случайным процессом ( ) ( ) { ( ) ( )} 12 , ,..., . R N t n t n t n t = Рисунок 1. Архитектура распределенных объектов технологии CORBA Рисунок 2. Формальная модель системы взаимодействия ПК Будем также считать, что интенсивность обработки запросов на обслуживание осуществляется в порядке поступления (FCFS) и не зависит от R. Процессоры узлов сети ORB независимы друг от друга, а вероятность того, что обработке подлежит к заявок класса r, равна P(k), где k), где k () Pk = ( ) ( ) ( ) 1122 , nn P k P k P k=  k = ( ) 12 , ,..., , n k k k i k = ( ) 12 , ,..., . i i ir k k k= Учитывая, что полученное распределение количества заявок в очередях процессоров представлено как произведение ( ) , i i r Pk и в сети создаётся пуассоновский поток реализованных запросов, данная сеть ORB соответствует требованием сети Джексона и может быть представлена в мультипликативном виде [3] 1 12 1 1 ( ) ( , ,..., ) , )(M Ri i P n G n n n Z n - == ∏ (2) где () Pn - вероятность нахождения узла в со - вероятность нахождения узла в со - стоянии n, ( ) 1 2. , ,..., , M n n n n = 1 2 () , ikN i R ki i PGn =  µ =  µ  ∑∏ (3) ( ) ( ) 1 ! 1 !1 ,ir R ni i i ir r r ir i R nZn l nR = = = µ ∏ ∏ (4) ( ) 1 , M ir ir ij i l l P r = =∑ 1, , iM = 1, . rR = (5) Отсюда согласно выводам, изложенным в [3; 9], получаем следующие показатели: - пропускную способность брокера ORB для заявки r-го класса ( ) ( ) 1 ( , ) , R k N ir ir R i R r i i n i n n P n N n n= λ = µ ∑ (6) - число заявок класса r в ORB r в ORB r ( ) ( ) 1 ,, R R N ir R i R R r n L N P n N n = = ∑ (7) - среднее время ожидания заявки r-го класса ( ) ( ) 11 .iRir r ir LN TN M +-  = (8) На практике значения данных показателей зависят от загрузки системы в момент поступления заявки. Очевидно, что возможно состояние ORB, блокирующее очередной вызов. В этом случае осуществляется его N-кратное повторение до соN-кратное повторение до соN стояний обслуживания или отказа. Вероятность успешного вызова ( ) ( ) ( ) ( ) ( ) ( )( )( ) 1 1 1 1 2 1 1 1 . óñï áëê îòê îòê îòê áëê N P N P P P P N P - = - - - - -   Вероятность отказа от вызова ( ) ( ) ( ) ( )( ) ( ) ( ) 11 1 2 1 1 . îòê áëê îòê îòê îòê N P N P P P P N = - × × - - - Исходя из результатов, полученных в (1), можно записать 1 11 ( ) (1 )(1 (1 ( ))),óñï áëê áëê îòê Ni i ij P N P P P j - = = = - + - ∑∏ 1 11 ( ) ( (1) ( ( 1) (1 ( )))). îòê áëê îòê áëê îòê îòê Ni i ij P N P P P P i P j - = = = + + + - ∑∏ Улучшения данных показателей можно добиться путем снижения системных затрат, связанных с процессами взаимодействия между ПК и ORB. Считаем, что распределенная система включает d процессорных модулей, а реализация d процессорных модулей, а реализация d бизнес-процесса обеспечивается совокупностью nd > ПК. В [1; 9; 13] показано, что эффективность реализации распределенного приложения связана с решением трех основных задач: - разделение n ПК на d групп таким образом, d групп таким образом, d чтобы в каждой из групп находились ПК с наибольшими частотами взаимодействия; - построение правил реализации запросов, устраняющих блокировки и тупиковые ситуации; - снижение системных затрат на интеграцию распределенных по сети ПК. При решении первой задачи предположим, что для взаимодействующих ПК i f и j f известна частота взаимных запросов. Разбиваем все n ПК на d групп d групп d Φ={ } 12 , ,..., , d F F F так, что 11 , nd ii ii fF = = =  ,kl FF = ∅ . kl ≠ При одновременном обращении вызовов к различным ПК, размещенным на одном из процессорных модулей, возникает конфликт. Частота возникновения конфликтов k C на k-м ПМ ( ) , ,,k ij C P i j =∑ а суммарная частота конфликтов в системе ( ) 1 1 , ,. dd k k k i j C C P i j = = = = ∑ ∑∑ Уменьшить значение C можно путём цикличеC можно путём цикличеC ских переносов ÏÊi из группы k в группу l; k, . ld ∈ При этом изменение C определяем по форC определяем по форC муле (5): ( ) ( ) ( ) ( ) ,, , , . ÏÌ ÏÌ k l i j C P i j P j i P i j P j i ∈ ∈ ∆ = + -   -+   ∑ ∑ 310 Мочалов В.П., Линец Г.И., Братченко Н.Ю., Говорова С.В. «Инфокоммуникационные технологии» Том 17, № 3, 2019, с. 307-313 Последовательное выполнение одинаково построенных шагов завершается, когда любой перенос ÏÊi из группы k в группу l не изменяет l не изменяет l . C∆ Вычисление C ∆ можем произвести удобным рекуррентным методом. Введем систему операторов R ={ } , 1, , 1, ,it R i n t d = = означающих перенос ÏÊi в классе . td ∈ Тогда ( ) ( ) ( ), it itC R C ∆ ϕ = ϕ - ϕ где ( ) it ∆ϕ - изменение частоты конфликтов. Обозначим через ( )iq it ∆ϕ приращение ( ) it ∆ϕ при переходе к разбиению ( ) . iq RR ϕ∈ Тогда ( ) ( ) ( ),iq it it iq it R ∆ ϕ = ∆ -∆ ϕ 1, ; in = 1, ; qd = ( ) ( ) ( ). iq it iq it it R ∆ ϕ = ∆ ϕ +∆ ϕ Данный рекуррентный метод позволяет произвести рациональное распределение n ПК по d ПМ, снизить непроизводительные затраты при реализации запросов на услуги связи. Вторая задача, связанная с построением расписания обработки запросов, сводится к нахождению такой последовательности их реализации, которая минимизирует общее время выполнения задания. Очевидно, что устранение блокировки запросов возможно при выполнении условия [5; 7] 1 , jiij p p L L t t Z Z + - > - 1, , Lk = где ip t - требование p i-го типа; 1 j pt + - требование ( 1) p+ j-го типа; , i LZ j LZ - время обслуживания требований процессором L; { } max . ij ij L L l Z Z = - Тогда подход к решению задачи сводится к следующему. Если (X следующему. Если (X следующему. Если ( , X, X U) - ориентированный U) - ориентированный U симметричный граф, в котором Х-множество Х-множество Х типов заявок, U-множество дуг, то необходимо U-множество дуг, то необходимо U выделить контур, связывающий требуемые вершины только один раз, при этом сумма длин дуг должна быть минимальной [8; 10; 11]. ,0 min, r ij ij ij lx = →∑ 00 , rr ij i ij xn = = =∑∑ 0, , ir = 0, . jr = Третья задача, связанная с минимизацией системных затрат интеграции распределенных по сети ПК, сводится к снижению частоты обмена данными между ПК и брокером ORB. Решение задачи производится за счет разбиения множества ПК на независимые фрагменты и обеспечения взаимодействия между данными фрагментами и ORB [12; 14; 15]. Данная фрагментация описывается матрицами , ,1 nm ik ik VV= = и ,1 ,nij ij Ll= = где 1, , 0, åñëèÏÊ âïðîòèâíîìñëó÷àå, jk ikV ∈ϕ =   1, , 0, . åñëèÏÊ âïðîòèâíîìñëó÷àå ik ijl ∈ϕ =   Если число выполнений i-го ПК равно , im а запрос к j-му ПК происходит с вероятностью ,ijP то число запросов из ÏÊi к ÏÊj будет равно 11 , nn i ij ik kj mpV = = ∑∑ где ik V - идентификатор наличия только тех ПК, которые входят в k-й фрагмент. Тогда среднее k-й фрагмент. Тогда среднее k число межфрагментных запросов при условии вхождения каждого ПК в состав только одного фрагмента соответствует ( ) 111 1 min. nnn i ij ik jk kij C mPV V = = = = -→ ∑∑∑ Данная задача решается стандартными средствами пакета программ Mathematica. Заключение Представленные формальные подходы к решению задачи интеграции программных компонент распределенного по сети приложения на основе брокера объектных запросов технологии распределенных вычислений CORBA, система функциональных моделей исследования алгоритмов взаимодействия элементов данной системы позволяют принимать обоснованные решения при построении распределенных систем. Решение задачи интеграции программных компонент сведено к реализации трех основных алгоритмов: рационального распределения программных компонент по процессорным модулям системы, построения расписания выполнения параллельных процессов минимальной длины, минимизации непроизводительных затрат, связанных с процессами обмена данными. Предложен комплекс аналитических моделей исследования системы интеграции распределенных приложений, позволяющий проводить количественную оценку алгоритмов взаимодействия ее элементов, оценивать влияние процессов взаимодействия на характеристики системы в целом. Работа выполнена при финансовой поддержке РФФИ в рамках научного проекта № 19-07-00856/19.

About the authors

V. P Mochalov

Department of Infocommunications, North-Caucasus Federal University

Stavropol, Russian Federation

G. I Linets

Department of Infocommunications, North-Caucasus Federal University

Stavropol, Russian Federation

N. Yu Bratchenko

Department of Infocommunications, North-Caucasus Federal University

Stavropol, Russian Federation

S. V Govorova

Department of Infocommunications, North-Caucasus Federal University

Stavropol, Russian Federation

References

  1. Mochalov V., Bratchenko N. Call management model in telecommunications control system // Scientifi c Enquiry in the Contemporary World: Theoretical Basics and Innovative Approach. San Francisco: B&M Publishing, 2014. P. 143-151
  2. Man Y., Zhang G., Song M. Research of methodology of building modern service industry BI system based on NGOSS // Journal of China Universities of Posts and Telecommunications. 2008. Vol. 15. P. 84-87.
  3. Distributed management systems for infocommunication networks: a model based on tm forum frameworx / N. Bratchenko [et al.] // Computers. 2019. № 8. P. 45. URL: https://www. mdpi.com/2073-431X/8/2/45 (дата обращения: 30.05.2019).
  4. Vinoski S. CORBA: integrating diverse applications within distributed heterogeneous environments // IEEE Communications Magazine. 1997. Vol. 35. № 2. P. 46-55.
  5. Harrison T.H., Levine D.L., Schmidt D.C. The design and performance of a real-time CORBA event service // ACM SIGPLAN Notices. 1997. Vol. 32. № 10. P. 184-200.
  6. Schmidt D.G., Kuhns F. An overview of the realtime CORBA specifi cation // Computer. 2000. Vol. 33. № 6. P. 56-63.
  7. Whitt W. Performance of the queueing network analyzer // The Bell System Technical Journal. 1983. Vol. 62. № 9. P. 2817-2843.
  8. Fundamentals of queueing theory / D. Gross [et al.]. New York: John Wiley & Sons, 2008. 528 p.
  9. Mochalov V.P., Bratchenko N.Y., Yakovlev S.V. Analytical model of object request broker based on Corba standard // Journal of Physics: Conference Series. 2018. Vol. 1015(2). P. 022012-1-5. doi: 10.1088/1742-6596/1015/2/022012.
  10. Mochalov V.P., Bratchenko N.Y., Yakovlev S.V. Analytical model of integration system for program components of distributed object applications // 2018 International Russian Automation Conference (RusAutoCon). 2018. P. 8501806-1-4. DOI: 10.1109/ RUSAUTOCON.2018.8501806.
  11. Lechler T., Taylor B.J., Klingenberg B. The telecommunications carriers' dilemma: innovation vs. network operation // Management of Engineering and Technology, Portland International Center for, IEEE, Portland, OR, USA, 5-9 August 2007. P. 2940-2947. doi: 10.1109/PICMET.2007.4349638.
  12. Distributed management system for infocommunication networks based on TM Forum Framework / D.V. Gosteva [et al.] // CEUR Workshop Proceedings 2254. 2018. P. 81-93. URL: https:// www.scopus.com/inward/record.uri?eid=2-s2.085058625764&partnerID=40&md5=fbda7d30 75571d715088b8e72f1d6c5 (дата обращения: 30.05.2019).
  13. Lee E.A. The problem with threads // Computer. 2006. № 39. P. 33-42. DOI: 10.1109/ MC.2006.180.
  14. Sutter H., Larus J. Software and the concurrency revolution // Queue. 2005. № 3. P. 54-62. doi: 10.1145/1095408.1095421.
  15. Olszewski M., Ansel J., Amarasinghe S. Kendo: effi cient deterministic multithreading in software // ACM Sigplan Notices. 2009. № 44. P. 97-108. doi: 10.1145/1508284.1508256.

Statistics

Views

Abstract - 23

Cited-By


Article Metrics

Metrics Loading ...

PlumX

Dimensions


Copyright (c) 2019 Mochalov V.P., Linets G.I., Bratchenko N.Y., Govorova S.V.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies