Вступление
С «официальным» алгоритмом синтеза многосвязных сетей я лично не сталкивался ни в Интернете, ни в процессе обучения в техническом ВУЗе. Cуществуют скорее методики построения многосвязных сетей нежели зарегистрированные и запатентованные алгоритмы. Для тех кто ни разу не сталкивался с такой задачей хочется заметить, что она в основном возникает в процессе моделирования и проектирования телекоммуникационных сетей различных масштабов. Реализовывать полученный в процессе такого моделирования проект на практике или нет, зависит прежде всего от его целей. Если это курсовая работа студентов специальностей связанных с телекоммуникациями, то описанные ниже рекомендации для них вполне применимы. Организации занимающиеся проектированием сетей национальных или хотя бы городских масштабов используют свои практические методы построения многосвязных сетей, однако не исключено, что информация представленная в статье будет полезна и для них.
Алгоритм
В Донецком Национальном Техническом университете на специальности ТКС (Телекоммуникационные системы и сети) в рамках курса «Теория сетей» обучают следующей последовательности (алгоритму) построения многосвязной сети:
0) В качестве исходных данных есть матрица расстояний (L) между конечными объектами сети (на практике в качестве них могут выступать например маршрутизаторы). Матрица квадратная, где каждый элемент (Lij=Lji) равен расстоянию (метры, километры) между i-м и j-м узлом. Lii=Ljj=0 — расстояние от текущего узла до самого себя. На основание данной матрицы и выбрав среду передачи информации (пусть это будут кабельные линии связи) можем построить матрицу стоимости (С) умножив расстояния на условную или реальную единицу стоимости метра или километра кабеля.
1) Строим матрицу базовой топологии (Cb). В качестве базовых топологий предлагается использовать один из таких вариантов — оптимальное кольцо, минимальное остовное дерево, звезда. Для построения матрицы базовой топологии для каждого из этих вариантов существуют свои алгоритмы, которые в данной статье не затрагиваются. Скажем лишь, что принцип построения данных топологий одинаков — минимальное расстояние между узлами в пределах заданной топологии отличающейся каждая по своим основным свойствам. Для оптимального кольца такими свойством является существование двух различных путей между узлами, что обеспечивает дублирование, для звезды — это наличие центрального узла, через который проходят все информационные потоки, для минимального остовного дерева — отсутствие в топологии замкнутых путей (петель).
2) Собственно построение многосвязной сети путем введения в матрицу базовой топологии дополнительных ветвей в соответствии с какими-либо ограничивающими критериями, при достижении которых многосвязная сеть считается построенной. В качестве таких критериев выбираются кол-во промежуточных узлов (Kij) на пути между двумя выбранными узлами i и j (по-другому критерий можно назвать — «количество переприёмов») и стоимость ввода ветви в сеть. Таким образом, задав некоторое ограничение на параметр К, и путем выбора из матрицы (С) минимальных элементов на каждом шаге данного алгоритма, мы постепенно получаем многосвязную сеть занимающую промежуточное, но не оптимальное (!) место сравнительно с полносвязной сетью и сетью базовой топологии по стоимости и количеству переприемов информации между двумя узлами. Когда заданное ограничение по критерию (К) будет достигнуто для всех узлов сети, многосвязная сеть считается готовой.
Предлагаемое усовершенствование описанного выше алгоритма
Усовершенствование на первый взгляд простое. — Во втором пункте описанного выше метода предлагается выбирать из матрицы (С) на каждом шаге алгоритма не минимальное значение (Cвводимое=Сijmin), а вводить в многосвязную сеть узел соответствующий критерию minimum((Сij/Cmin)+(Wmax/Wij)), где Сij — проверяемый на соответствие критерию элемент матрицы (С), Сmin — минимальный на данном шаге алгоритма элемент матрицы стоимости (С), Wij — величина показывающая изменение количество переприёмов (параметра К) по сравнению с состоянием сети до ввода ветви Сij, Wmax — максимально возможное изменение параметра W для текущего состояния сети.
Для реализации данного усовершенствования на каждом шаге алгоритма происходит пересчёт текущего состояния сети, для построения матрицы W, отражающей изменение параметра К для всех элементов сети, при введении в неё элемента Сij, из которой собственно затем и берутся элементы Wij и Wmax. Шаги алгоритма разбиваются на подшаги, количество которых будет зависеть от величины сети.
Это лишь общее описание предлагаемого метода. Программная реализация включает в себя построение множества других промежуточных матриц и применения алгоритмов не указанных в статье — например алгоритма Флойда.
Данный метод построения многосвязной сети позволяет получить если не оптимальную сеть по критериям стоимости и количества промежуточных узлов, то сравнительно лучшую — это точно. Недостаток данного метода — сложность вычислений по сравнению с первым вариантом, без программной реализации применить его крайне трудно даже для сетей со сравнительно малым количеством узлов.
Текст распространяется под лицензией Creative Commons Attribution-Share Alike
С «официальным» алгоритмом синтеза многосвязных сетей я лично не сталкивался ни в Интернете, ни в процессе обучения в техническом ВУЗе. Cуществуют скорее методики построения многосвязных сетей нежели зарегистрированные и запатентованные алгоритмы. Для тех кто ни разу не сталкивался с такой задачей хочется заметить, что она в основном возникает в процессе моделирования и проектирования телекоммуникационных сетей различных масштабов. Реализовывать полученный в процессе такого моделирования проект на практике или нет, зависит прежде всего от его целей. Если это курсовая работа студентов специальностей связанных с телекоммуникациями, то описанные ниже рекомендации для них вполне применимы. Организации занимающиеся проектированием сетей национальных или хотя бы городских масштабов используют свои практические методы построения многосвязных сетей, однако не исключено, что информация представленная в статье будет полезна и для них.
Алгоритм
В Донецком Национальном Техническом университете на специальности ТКС (Телекоммуникационные системы и сети) в рамках курса «Теория сетей» обучают следующей последовательности (алгоритму) построения многосвязной сети:
0) В качестве исходных данных есть матрица расстояний (L) между конечными объектами сети (на практике в качестве них могут выступать например маршрутизаторы). Матрица квадратная, где каждый элемент (Lij=Lji) равен расстоянию (метры, километры) между i-м и j-м узлом. Lii=Ljj=0 — расстояние от текущего узла до самого себя. На основание данной матрицы и выбрав среду передачи информации (пусть это будут кабельные линии связи) можем построить матрицу стоимости (С) умножив расстояния на условную или реальную единицу стоимости метра или километра кабеля.
1) Строим матрицу базовой топологии (Cb). В качестве базовых топологий предлагается использовать один из таких вариантов — оптимальное кольцо, минимальное остовное дерево, звезда. Для построения матрицы базовой топологии для каждого из этих вариантов существуют свои алгоритмы, которые в данной статье не затрагиваются. Скажем лишь, что принцип построения данных топологий одинаков — минимальное расстояние между узлами в пределах заданной топологии отличающейся каждая по своим основным свойствам. Для оптимального кольца такими свойством является существование двух различных путей между узлами, что обеспечивает дублирование, для звезды — это наличие центрального узла, через который проходят все информационные потоки, для минимального остовного дерева — отсутствие в топологии замкнутых путей (петель).
2) Собственно построение многосвязной сети путем введения в матрицу базовой топологии дополнительных ветвей в соответствии с какими-либо ограничивающими критериями, при достижении которых многосвязная сеть считается построенной. В качестве таких критериев выбираются кол-во промежуточных узлов (Kij) на пути между двумя выбранными узлами i и j (по-другому критерий можно назвать — «количество переприёмов») и стоимость ввода ветви в сеть. Таким образом, задав некоторое ограничение на параметр К, и путем выбора из матрицы (С) минимальных элементов на каждом шаге данного алгоритма, мы постепенно получаем многосвязную сеть занимающую промежуточное, но не оптимальное (!) место сравнительно с полносвязной сетью и сетью базовой топологии по стоимости и количеству переприемов информации между двумя узлами. Когда заданное ограничение по критерию (К) будет достигнуто для всех узлов сети, многосвязная сеть считается готовой.
Предлагаемое усовершенствование описанного выше алгоритма
Усовершенствование на первый взгляд простое. — Во втором пункте описанного выше метода предлагается выбирать из матрицы (С) на каждом шаге алгоритма не минимальное значение (Cвводимое=Сijmin), а вводить в многосвязную сеть узел соответствующий критерию minimum((Сij/Cmin)+(Wmax/Wij)), где Сij — проверяемый на соответствие критерию элемент матрицы (С), Сmin — минимальный на данном шаге алгоритма элемент матрицы стоимости (С), Wij — величина показывающая изменение количество переприёмов (параметра К) по сравнению с состоянием сети до ввода ветви Сij, Wmax — максимально возможное изменение параметра W для текущего состояния сети.
Для реализации данного усовершенствования на каждом шаге алгоритма происходит пересчёт текущего состояния сети, для построения матрицы W, отражающей изменение параметра К для всех элементов сети, при введении в неё элемента Сij, из которой собственно затем и берутся элементы Wij и Wmax. Шаги алгоритма разбиваются на подшаги, количество которых будет зависеть от величины сети.
Это лишь общее описание предлагаемого метода. Программная реализация включает в себя построение множества других промежуточных матриц и применения алгоритмов не указанных в статье — например алгоритма Флойда.
Данный метод построения многосвязной сети позволяет получить если не оптимальную сеть по критериям стоимости и количества промежуточных узлов, то сравнительно лучшую — это точно. Недостаток данного метода — сложность вычислений по сравнению с первым вариантом, без программной реализации применить его крайне трудно даже для сетей со сравнительно малым количеством узлов.
Текст распространяется под лицензией Creative Commons Attribution-Share Alike
