Математичне та програмне забезпечення обчислювальних машин і систем

Abstract

The thesis deals with the substantial optimization of the distribution of information and computing resources among units of computer networks, developing mathematical models of resource allocation algorithms and finding the optimal or near optimal distributions. Mathematical models and algorithms sharing computing resources among nodes computing clusters are developed. A heuristic algorithm, the modified genetic algorithm and branch and bound algorithm for determining optimal or near optimal allocation of resources among units of computer networks are proposed. A mathematical model to optimize user access to Internet information servers, which take into account the probability distribution reference to pages server is developed. The ratio to find the parameters under which the expectation of the total time required to search for information, reaches a minimum is found. The software system on the basis of mathematical models mentioned, heuristics and genetic algorithms for finding the optimal distribution of files among distributed database of computer network nodes is developed. The first chapter deals with a review of existing means of optimization of computer networks, analyzis of the mathematical apparatus used. General problem of optimal information and computational resources among nodes networks is formulated. The choice of controlled variables and parameters of optimization is arguments. The interdependence between different numerical criteria used in the optimization of computer networks is investigated. The second chapter considers the development of following mathematical models: model of optimal distribution of copies of files among network nodes, where the optimality criterion selected amount of data that is sent via communication channels per unit time; model of optimal utilization of computing resources in network nodes (clusters, grid systems) where time of problems solving should be minimize; model of optimal information access on internet servers where the optimality criterion is the expectation of the total time required to search page. Mathematical models are developed regarding on a set of factors that affect the structure and functioning of the network. The third chapter discusses the algorithms for optimal or near optimal allocation of resources among units of computer networks such as heuristic, genetic and branch and bound algorithms. New heuristic algorithm on the basis of mathematical model determining the optimal number of copies of files and their distribution among the nodes of computer networks is proposed. The estimation complexity of the algorithm is made. The developed heuristic algorithm to find optimal or near optimal distribution of files among network nodes. The algorithm consists of two stages. In the first stage the initial distribution, which will be the best, if not take into account the restrictions imposed on the distribution is found. The second stage consists of several steps. With each step a file from crowded nodes so as to achieve the minimum objective function value increase. The second stage of the algorithm continues until it finds the optimal or close to the optimal distribution. The adaptation of branch and bound algorithm for solving generalized assignment problem is performed. A modification of the genetic algorithm, which, due to specially selected encoding reduces the chromosome length and takes into account the conditions imposed on the solutions of problems is proposed. Thus, the length of the binary image that represents a potential solution for the problem of optimization to shrink from to enabling significantly reduce the time needed for the genetic algorithm to complete the task. The fourth chapter the work of software system designed for optimal distribution of files among computer network nodes is described. The system collects statistical material on requests for files and correction messages, calculates the intensity of traffic and makes recommendations concerning the optimal allocation of files among computer network nodes. Диссертация посвящена исследованию оптимизации распределения информационных и вычислительных ресурсов среди узлов компьютерных сетей, разработке математических моделей распределения ресурсов и алгоритмов нахождения оптимальных или близких к оптимальным распределений. В диссертационной работе разработаны математические модели и алгоритмы нахождения оптимального распределения вычислительных ресурсов среди узлов вычислительных кластеров. Разработан эвристический алгоритм, предложен модифицированный генетический алгоритм и алгоритм веток і границ для определения оптимального или близкого к оптимальному распределения ресурсов среди узлов компьютерных сетей. Разработаны математические модели оптимизации доступа пользователей к информации интернет-серверов, которые учитывают распределение вероятностей обращения к страницам сервера, выведено соотношения для нахождения параметров, при которых математическое ожидание общего времени, необходимого для поиска информации, достигает минимума. Разработан программный комплекс, у котором использовано разработанные математические модели, эвристические и генетические алгоритмы отискания оптимального распределения файлов распределённой базы данных среди узлов компьютерной сети. Дисертація присвячена дослідженню оптимізації розподілу інформаційних та обчислювальних ресурсів серед вузлів комп’ютерних мереж, розробці математичних моделей розподілу ресурсів та алгоритмів знаходження оптимальних або близьких до оптимальних розподілів. Розроблено математичні моделі та алгоритми знаходження оптимального розподілу обчислювальних ресурсів серед вузлів обчислювальних кластерів. Запропоновано евристичний алгоритм, модифікований генетичний алгоритм та алгоритм гілок і меж для визначення оптимального або близького до оптимального розподілу ресурсів серед вузлів комп’ютерних мереж. Розроблено математичні моделі оптимізації доступу користувачів до інформації інтернет-серверів, які враховують розподіл ймовірностей звертання до сторінок серверу, виведено співвідношення для знаходження параметрів, за яких математичне сподівання загального часу, необхідного для пошуку інформації, досягає мінімуму. Розроблено програмний комплекс, у якому використано розроблені математичні моделі, евристичні і генетичні алгоритми відшукання оптимального розподілу файлів розподіленої бази даних серед вузлів комп’ютерної мережі.