Спосіб багатошляхової маршрутизації в комп’ютерних мережах великої розмірності

Скорочена інформація про документ
dc.contributor.authorДіброва, Михайло Олександрович
dc.contributor.degreedepartmentОбчислювальної технікиuk
dc.contributor.degreefacultyІнформатики та обчислювальної технікиuk
dc.contributor.degreegrantorНаціональний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»uk
dc.date.accessioned2017-03-27T08:46:54Z
dc.date.available2017-03-27T08:46:54Z
dc.date.issued2017
dc.description.abstractenA thesis shows the theoretical substantiation and obtained a new solution of forming maximum possible number of non-intersecting paths. The modified wave formation method of maximum non-intersecting paths set, with taking into account their metrics, was suggested. The algorithm for simultaneous formation the set of paths from one node to several, which can significantly reduce the time complexity of the virtual computer network formation was developed. A method is proposed and an algorithm for multi-path routing in distributed data centers is presented, which, due to the self-similarity and mutual accommodation of computing nodes, significantly reduces the routing time. A method for forming a virtual grid-system structure with multipath data transmission channels is proposed.uk
dc.description.abstractruВ диссертационной работе приведено теоретическое обоснование и получено новое решение задачи формирования максимально возможного множества непересекающихся путей. Приведен анализ существующих методов многопутевой маршрутизации и алгоритмов формирования путей между абонентами вычислительной сети. На основе теории графов сформулированы критерии наличия максимального количества непересекающихся путей между двумя узлами сети, позволяющие оптимизировать процедуру маршрутизации. Временная сложность формирования многоканального виртуального пути, состоящего из q физических каналов с помощью комбинаторных алгоритмов, например, алгоритма Дейкстры равна О(qN2). Уменьшить временную сложность можно за счет исключения операции перебора вариантов на основе метод а «ветвей и границ», однако данный алгоритм не позволяет учитывать метрики пути при организации многопутевой маршрутизации. В связи с этим, в работе предложен модифицированный волновой способ формирования максимального множества непересекающихся путей с учетом их метрик. Предложено и обосновано условие формирования очередного непересекающегося пути: 1. Формирование пути Pi с минимальным значением внешней степени (Sok) для текущей вершины в k. 2. При равных значениях внешней степени выбирается путь с минимальной метрикой пути. 3. В качестве очередной вершины пути выбирается смежная с вершиной в k вершина вm∉В1с минимальной внешней степенью Som. Предложен волновой алгоритм маршрутизации, позволяющий существенно сократить временную сложность формирования множества непересекающихся путей компьютерной сети большой размерности. Данный алгоритм позволяет сформировать множество непересекающихся путей, незначительно отличающихся по своей длине. На основе модифицированного волнового способа формирования множества непересекающихся путей разработан алгоритм одновременного формирования множества путей от одного узла к нескольким узлам, позволяющий существенно уменьшить временную сложность формирования виртуальной компьютерной сети. Впервые предложен и обоснован способ формирования непересекающихся путей до вершин минимальной области сочленения подграфов, позволяющий существенно уменьшить временную сложность алгоритма формирования непересекающихся и частично пересекающихся путей. Предложен и разработан способ формирования непересекающихся путей на основе сочленения деревьев с корневыми вершинами, между которыми формируются непересекающиеся пути. За счет одновременного формирования этих деревьев сокращается время и область поиска множества непересекающихся путей. На основе данного способа разработан алгоритм «встречной волны», позволяющий сократить время и область поиска множества непересекающихся путей. Предложен способ формирования таблиц меток для организации многопутевой маршрутизации в сетях MPLS. Данный способ позволяет одновременно формировать все множество непересекающихся путей между двумя граничными маршрутизаторами LERi и LERj. В данном случае временная сложность формирования таблиц меток маршрутов существенно не зависит от количества множества сформированных каналов передачи и определяется величиной О(N+M+L), где: N – число маршрутизаторов LSRi, M – число каналов связи, L – общая длина всех сформированных путей между маршрутизаторами LERi и LERj Это существенно меньше, чем временная сложность О(qN2) последовательного формирования q путей с помощью алгоритма Дейкстры. Данный способ также позволяет сформировать множество непересекающихся каналов от одного граничного маршрутизатора к заданному множеству других граничных маршрутизаторов, образовав виртуальную сеть поверх сети MPLS. Предложен способ многопутевой маршрутизации в распределенных центрах данных, позволяющий за счет свойства самоподобия и учета взаимного расположения вычислительных узлов, существенным образом сократить время маршрутизации. Предложенный алгоритм максимально учитывает особенности сетевой топологии Fat tree, что способствует более эффективному поиску множества путей передачи данных. Для ускорения перехода между уровнями в модифицированном алгоритме вводится глобальная переменная next, которая указывает направление обхода узлов сети. Это обеспечить линейную временную сложность формирования множества путей и лучшую балансировку нагрузки. Предложен способ формирования виртуальной структуры Grid систем с многопутевыми каналами передачи данных.uk
dc.description.abstractukБагатошляхова маршрутизація характеризується великою часовою складністю пошуку множини шляхів, що не перетинаються. Часова складність знаходження найкоротшого шляху по алгоритму Дейкстри представляє собою величину O(kN2). При знаходженні k-шляхів часова складність збільшується відповідно в k раз. В зв’язку з цим, для пошуку множини шляхів, що не перетинаються, в рамках цієї роботи був запропонований модифікований метод «гілок та границь». Це досягається за рахунок виключення операцій перебору варіантів формування кожного шляху. В процесі роботи алгоритму у відповідності з методом «гілок та границь» будується дерево рішень, коренем якого є початкова вершина, а листями є вершини, суміжні з кінцевою вершиною.uk
dc.format.page22 с.uk
dc.identifier.citationДіброва, М. О. Спосіб багатошляхової маршрутизації в комп’ютерних мережах великої розмірності : автореф. дис. … канд. техн. наук : 05.13.05 – комп'ютерні системи та компоненти / Діброва Михайло Олександрович. – Київ, 2017. – 22 с.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/19105
dc.language.isoukuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.status.pubpublisheduk
dc.subjectбагатошляхова маршрутизаціяuk
dc.subjectшляхи, що не перетинаютьсяuk
dc.subjectметод «гілок та меж»uk
dc.subjectалгоритм зустрічної хвиліuk
dc.subjectmultipath routingen
dc.subjectthe non-intersecting pathsen
dc.subjectmethod of «branch and bound»en
dc.subjectoncoming wave algorithmen
dc.subjectмногопутевая маршрутизацияru
dc.subjectнепересекающиеся путиru
dc.subjectметод «ветвей и границ»ru
dc.subjectалгоритм встречной волныru
dc.subject.udc[004.7:004.715]:[519.1:519.854](043.3)uk
dc.titleСпосіб багатошляхової маршрутизації в комп’ютерних мережах великої розмірностіuk
dc.typeThesisuk
thesis.degree.levelcandidateuk
thesis.degree.nameкандидат технічних наукuk
thesis.degree.speciality05.13.05 – комп'ютерні системи та компонентиuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Dibrova_aref.pdf
Розмір:
1.09 MB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
7.8 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Автореферати (ОТ)
Автореферати (вільний доступ)