BC/NW 2016 № 1 (28):4.2

РАЗРАБОТКА АЛГОРИТМА ПОСТРОЕНИЯ ЛОГИЧЕСКОЙ МАТРИЦЫ ИЗ ТОПОЛОГИЧЕСКОЙ МАТРИЦЫ ДЛЯ ОПРЕДЕЛЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ

Абросимов Л.И., Тагирова М.А.

Этапы методологии

Кратко рассмотрим состав и последовательность выполняемых действий (компьютеризированных процедур) при разработке и модернизации региональных и/или корпоративных ВС.

Подготовительные процедуры.

1. Формирование базы данных технических и программных средств (БДС), в результате которого получают:

· Классификации устройств (У), линий связи (ЛС) и программного обеспечения (ПО);

· Технические характеристики У, Л, и ПО;

· Экономические характеристики У, Л, и ПО.

2. Формирование базы данных трафика (БДТ), в результате которого получают:

· классификации клиентов и серверов;

· схема взаимодействия клиентов и серверов;

· информационные характеристики взаимодействия;

Процедуры, выполняемые при разработке ВС.

3. Разработка принципиальной схемы соединения устройств посредством линий связи, с указанием идентификаторов (A.r), (B.k) и типов ω устройств, типов линий θ связи и каналов γ связи. Разработанная принципиальная схема ВС может быть представлена в виде визуального отображения на экране монитора разработчика и в виде списка соединений устройств линиями связи.

Для обеспечения изоморфизма топологической, логической и функциональной моделей при выполнении формирования и преобразования матричных представлений моделей используется массив М метаданных, который состоит из набора таблиц М1, М2, М3.

4. Формирование топологической матрицы Т, которое выполняется по соотношению (1) и отображает все физические элементы ВС, к которым относятся устройства множества У (рабочие станции, серверы, коммутирующие устройства) и множества Л (линий связи).

(2.1)

где ω - тип устройства, А и В - идентификатор, определяющий место-положение У ∈ У, R - количество разъемов в устройстве У, θ - тип линии связи Л ∈ Л (физическая реализация), γ - тип канала связи Л (дуплексный, полудуплексный, симплексный).

В таблице метаданных М1 каждому идентификатору A.k − B.r ставится в соответствие порядковый номер i.

5. Формирование логической матрицы L, которая предназначена для отображения узлов, соответствующих тем устройствам, представленным в матрице Т, которым в ВС присвоены логические имена, адреса и номера интерфейсов.

Множество узлов U, отображаемых в матрице L, является подмножеством устройств У (U ∈ У), описываемых в топологической матрице Т, поэтому каждому узлу UA соответствует устройство YA.

Для описания логического соединения узлов U, соответствующих ВС, используются дуги D, которые могут быть взвешены в соответствии с выбранной метрикой маршрутизации.

Основным параметром дуги D является тип γ канала связи, организованного между узлами UA и UB.

На основании матрицы Т, списков {U} и {D} можно сформировать матрицу L логической структуры, в которой:        

(2.2)

Благодаря тому, что логическое представление структуры ВС имеет дело с адресуемыми элементами, для двух любых сетевых устройств можно получить маршрут прохождения транзакций между ними.

В таблице метаданных М2 каждому идентификатору A ставится в соответствие порядковый номер i.

6. Решение задачи выбора кратчайших маршрутов, используя данные логической матрицы L и выбранный критерий эффективности. Результатом расчета является таблица маршрутизации между всеми адресуемыми устройствами ВС.

7. Формирование функциональной матрицы F, которая является основой математической модели ВС и предназначена для отображения функциональных элементов Е, соответствующих устройствам У и линиям Л, которые задерживают транзакции при обработке и оказывают существенное влияние на производительность ВС.

Каждый элемент Е описывается соотношениями моделей массового обслуживания, является ориентированным и имеет вход (1) и выход (2). Подмножество ЕУ⊂Е является подмножеством элементов отображающих У и каждый элемент ЕА подмножества ЕУ имеет идентификатор А, введенный при формировании топологической структуры. Для устройств и элементов используется одна и та же система индикаторов. Подмножество ЕК⊂Е является подмножеством элементов, отображающих каналы К и каждый элемент ЕК подмножества ЕК имеет идентификатор (А.k-B.r).

Для формирования матрицы F необходимо использовать множество ES переходов, отображающих соединение выходов (2) элементов подмножеств ЕУ с входами (1) элементов подмножества ЕК и соединение выходов (2) элементов подмножеств ЕК с входами (1) элементов подмножества ЕУ.

На основании матрицы Т, можно сформировать матрицу F функциональной структуры, в которой

(2.3)

где i и j – соответственно, строки и столбцы в матрице F, а r и k – разъемы устройств А и В.

В таблице метаданных М3 каждому идентификатору и каждому идентификатору линии связи A.k-B.k ставится в соответствие порядковый номер элемента Е, а каждому входу/выходу элемента Е ставится в соответствии порядковый номер i.

Описание топологической матрицы T

В качестве исходных данных разрабатываемого алгоритма используется Топологическая матрица. Объектом исследования является распределенная корпоративная вычислительная сеть (ВС), которая имеет в своем составе рабочие станции, серверы, коммуникационные устройства, аппаратуру передачи данных и линии связи. Использование математических методов для автоматизированного проектирования ВС, которые имеют размерность более 1000 узлов, затруднено ввиду отсутствия эффективных, формализованных способов представления и описания структуры ВС.

Структура – это расположение элементов и их взаимосвязи. Топологическая структура (ТС) ВС используется для решения задач, в которых учитывается метрическое пространство. Элементами ТС являются устройства, взаимосвязи определяют линии связи. ТС определяет местоположение устройств (серверов, коммуникационных устройств, рабочих станций), позволяет проверять выполнение технических ограничений на допустимую длину линий связи, определяет к какому коммуникационному устройству можно подключить новую группу рабочих станций и т.д. Реальные ВС могут содержать в своем составе сотни устройств.

Целью описания топологической структуры ВС является получение такого отображения устройств и линий связи, которое позволит:

· однозначно и с необходимой детальностью зафиксировать состав устройств и линий связи между ними, чтобы затем представить их в табличной, матричной, списочной и графической формах для последующей формализованной обработки;

· упорядочить все параметры, характеризующие устройства, которые входят в состав ВС и необходимы для моделирования и анализа производительности ВС.

Все многообразие устройств, входящих в исследуемую ВС, можно разделить на следующие классы: РУ – рабочие станции, ГУ – групповые устройства, СУ – серверы, КУ – коммутирующие устройства. Чтобы учитывать особенности функционирования устройств различных классов вводится параметр ω- тип устройства ВС. Полный перечень типов ω устройств составляется для каждой ВС и учитывает ее особенности.

При описании взаимосвязей исследуемой ВС используются два понятия: линия связи и канал связи (КС). Линия связи (ЛС) – это физические средства, обеспечивающее соединение двух разъемов устройств. В качестве примера линии связи можно рассматривать кабель, радиолинию. Канал связи (КС) – это набор функциональных средств, обеспечивающий обмен данными по линии связи в соответствии со средствами доступа и протоколом передачи. В зависимости от особенностей функционирования по линиям связи могут быть организованы каналы связи различных типов θ.

Типы q принимают следующие значения:

q = 1 - соответствует коаксиальному кабелю.

q = 2 - соответствует витой паре (полудуплексная).

q = 3 - соответствует витой паре (дуплексная).

q = 4 - соответствует оптоволокну.

Линии связи «многоразъемные» соединяют несколько разъемов различных устройств и составляют физическую основу локальной среды передачи данных, по которой могут быть организованы каналы связи различных типов γ. Полный идентификатор «многоразъемных» линий связи имеет вид: (А.k-B.r-С.n-..-Z.m),θ,γ.

А типы принимают γ следующие значения:

γ = 1 - соответствует симплексному каналу связи, который осуществляет передачу данных только в одном направлении от А к В

γ = 2 - соответствует полудуплексному каналу связи, который в один интервал времени осуществляет передачу данных в одном направлении (от А к В), а в другой интервал времени – в другом направлении (от В к А).

γ = 3 - соответствует дуплексному каналу связи, который одновременно осуществляет передачу данных как в одном направлении (от А к В), так и в другом направлении (от В к А).

γ = 4 - соответствует каналу двунаправленной шины по коаксиальному кабелю с заданным методом доступа, например, CSMA/CD.

γ = 5 - соответствует каналу маркерное кольцо с переприемом.

Присвоим устройству ВС, идентификатор А, тогда разъему k устройства А можно присвоить идентификатор А.k. В соответствии с принятыми идентификаторами устройств линия связи, соединяющая разъемы А.k и B.r двух устройств, должны иметь составной идентификатор: А.k-B.r. Полный идентификатор линий связи «разъем–разъем» учитывает тип канала связи и имеет вид: (А.k-B.r)θ.

Цель работы и схема исследования вычислительной сети

В состав исходных данных для определения функциональных характеристик ВС входят пары взаимодействующих устройств, например: клиент-сервер, терминал-терминал, сервер-сервер .

После инициализации взаимодействия данные, сформированные в виде пакетов, движутся по кратчайшему маршруту.

В настоящее время для выбора маршрута используют RIP и OSPF.

Протокол RIP (Routing Information Protocol), протокол маршрутной информации является наиболее простым протоколом динамической маршрутизации. Он относится к протоколам типа «вектор-расстояние».

Под вектором протокол RIP определяет IP-адреса сетей, а расстояние измеряется в переходах («хопах», hope) – количестве маршрутизаторов, которое должен пройти пакет, чтобы достичь указанной сети. Следует отметить, что максимальное значение расстояния для протокола RIP равно 15, значение 16 трактуется особым образом «сеть недостижима». Это определило основной недостаток протокола – он оказывается неприменимым в больших сетях, где Возможны маршруты, превышающие 15 переходов.

Протокол RIP версии 1 имеет ряд существенных для практического использования недостатков. К числу важных проблем относятся следующие:

· Оценка расстояния только с учетом числа переходов. Протокол RIP не учитывает реальную производительность каналов связи, что может оказаться неэффективным в гетерогенных сетях, т.е. сетях, объединяющих каналы связи различного устройства, производительности, в которых используются разные сетевые технологии.

· Проблема медленной конвергенции. Маршрутизаторы, спользующие протокол RIP. Рассылают маршрутную информацию каждые 30 с., причем их работа не синхронизирована. В ситуации, когда некоторый маршрутизатор обнаружит, что какая-либо сеть стала недоступной, то в худшем случае (если проблема была выявлена сразу после очередной рассылки) он сообщит об это соседям через 30 с. Для соседних маршрутизаторов все будет происходить также. Это означает, что информация о недоступности какой-либо сети может распространятся маршрутизаторам в достаточно долго, очевидно, что сеть при этом будет находиться в нестабильном состоянии.

· Широковещательная рассылка таблиц маршрутизации. Протокол RIP изначально предполагал, что маршрутизаторы рассылают информацию в широковещательном режиме. Это означает, что отправленный пакет вынуждены получить и проанализировать на канальном, сетевом и транспортном уровне все компьютеры сети, в которую он направлен.

Частично указанные проблемы решаются в версии 2 (RIP2).

Протокол OSPF (Routing (Open Shortest Path First, «открой кратчайший путь первым») является более новым протоколом динамической маршрутизации и относится к протоколам типа «состояние канала».

Функционирование протокола OSPF основано на использовании всеми маршрутизаторами единой базы данных, описывающей, как и с какими сетями связан каждый маршрутизатор. Описывая каждую связь, маршрутизаторы связывают с ней метрику – значение, характеризующее «качество» канала. Например, для сетей Ethernet со скоростью обмена 100 Мбит/с используется значение 1, а для коммутируемых соединений 56 Кбит/с – значение 1785. Это позволяет маршрутизаторам OSPF (в отличие от RIP, где все каналы равнозначны) учитывать реальную пропускную способность и выявлять эффективные маршруты. Важной особенностью протокола OSPF является то, что используется групповая, а не широковещательная рассылка.

Указанные особенности, такие как групповая рассылка вместо широковещательной, отсутствие ограничений на длину маршрута, периодический обмен только короткими сообщениями о состоянии, учет «качества» каналов связи позволяют использовать OSPF в больших сетях. Однако такое использование может породить серьезную проблему – большое количество циркулирующей в сети маршрутной информации и увеличение таблиц маршрутизации. А поскольку алгоритм поиска эффективных маршрутов является, с точки зрения объема вычислений, достаточно сложным, то в больших сетях могут потребоваться высокопроизводительные и, следовательно, дорогие маршрутизаторы. Поэтому возможность построения эффективных таблиц маршрутизации может рассматриваться и как достоинство, и как недостаток протокола OSPF.

Концепция построения логической матрицы

Необходимо по топологической матрице преобразовать логическую матрицу, т.к. L соответствует реальным сетям.

Топологическая матрица должна из себя представлять ту форму, которая, с одной стороны, воспринимается машиной для дальнейших преобразований, с другой стороны, полностью соответствует рис.1.2. Но для вычислений удобно отобразить номера устройств и узлов в виде соответствия с порядковыми номерами в таблице метаданных.

Логическая матрица отличается от топологической тем, что в логической матрице записываются только адресуемые элементы. Если в логической матрице выбросить неадресуемые элементы, значит нужно поставить некие эквивалентные замены. Те элементы, которые выбрасываются, нужно проследить на следующее: во-первых, выявить этот элемент можно по ω, где ω=3; с другой стороны, к этим же устройствам можно отнести ретрансляторы, которые в беспроводной связи, не имеющие сетевого адреса. Заменить выброшенные элементы на дополнительные связи.

Ниже приведены шаги преобразования Топологической матрицы в Логическую:

а) Из топологической матрицы Т убрать разъёмы.

б) Выяснить кто с кем должен быть соединён, для этого нужно сформировать список взаимодействующих устройств.

в) Убрать неадресуемые элементы.

г) Сформировать дополнительные связи в устройстве, т.е. дополнительными дугами, каждая из которых соответствует наличию логической связи между адресуемыми устройствами.

д) Использовать алгоритм кратчайшего маршрута для определения картежа номеров устройств, входящих в каждый кратчайший маршрут.

Для оценки производительности ВС необходимы модели, которые, во-первых, учитывают реальную размерность ВС и, во-вторых, базируются на аналитических соотношениях, которые позволяют оперативно и детально оценивать предельную производительность ВС. Таким требованиям удовлетворяет модели, построенные с использованием метода контуров [1], в котором последовательно выполняются: описание топологической структуры ВС; построение функциональной структуры ВС; формализованного детализированного описания потока заявок на обслуживание; составление и решение линейных и нелинейных уравнений для определения требуемых вероятностно-временных характеристик функционирования ВС.

Целью данной диссертации является исследование и разработка программы построения логической структуры и расчёта минимальных маршрутов между двумя разъёмами вычислительной сети по варьируемому параметру взвешенной длины. Это достигается в 2 этапа:

1) По заданной Топологической структуре ВС сформировать Логическую матрицу ВС.

2) По Логической матрице рассчитать кратчайший маршрут по метрике hop.

Основной задачей настоящего исследования является преобразование топологической матрицы Т в Логическую матрицу ЛМ.

При формировании таблицы маршрутизации протоколы RIP и OSPF используют устройства, имеющие сетевые адреса. Следовательно, необходимо на основании топологии ВС, для которой указаны адресуемые устройства и список пар устройств, взаимодействующих по технологии клиент-сервер, определить и построить в матричной форме логическую структуру, включающую только адресуемые элементы и связи между ними.

Разработка алгоритма построения логической матрицы из топологической матрицы

Алгоритм построения ЛМ из матрицы T

Описание модулей:

1) Начало. Исходные данные:

- список пар {В} взаимодействующих по технологии клиент-сервер,

- матрица Т: тип устройства, идентификатор, число разъёмов,

- перечень устройств, не имеющих адресацию (ω=3 – неадресуемое устройство).

2) Ввод матрицы Т. Топологическая матрица Т отображает все физические элементы ВС и формируется по соотношению (1).

3) Формирование таблицы М1. В таблице метаданных М1 каждому идентификатору устройств и линий связи (A.k – B.r) ставится в соответствии порядковый номер i.

4) Формирование первой вспомогательной логической матрицы L1. Логическая матрица L1 предназначена для отображения узлов, соответствующих тем устройствам и каналам связи, представленным в матрице Т, которым в ВС присвоены логические имена, адреса и номера интерфейсов и формируется по соотношению (2).

5) Формирование таблицы М2. В таблице метаданных М2 каждому идентификатору устройства (A.k – B.r) ставится в соответствии порядковый номер i, где , N₂ = N_a , где  N_a – количество адресуемых устройств.

6) Формирование второй вспомогательной логической матрицы L2.  Логическая матрица L2 формируется по пункту 4 алгоритма, но с вычеркнутыми неадресуемыми устройствами, то есть где ω_i=3 и дополнительными дугами, каждая из которых соответствует наличию логической связи между адресуемыми устройствами.

7) Использование алгоритма кратчайшего маршрута [cм. главу 3] для определения картежа номеров устройств, входящих в каждый кратчайший маршрут пары вВ.

8) Проверка диагоналей L1 (если ω_i≠3, то 9), (если ω_i=3, то 10). ω- тип устройства, 3-номер устройства. Поиск неадресуемого устройства с ω_i=3.

9) Оставляем без изменений, т.к. устройство адресуемое.

10) Вычёркиваем строку и столбец, где ω_i=3.

11)  Формирование таблицы М3. В таблице метаданных М3 каждому идентификатору А ставится в соответствии порядковый номер i.

12)  Формирование логической матрицы L3. Логическая матрица L3 соответствует матрице L2 (пункт 4 алгоритма) после удаления всех неадресуемых элементов, где ω_i=3 и дополнительными дугами, каждая из которых соответствует наличию логической связи между адресуемыми устройствами.

13)  Конец. Формирование таблиц маршрутизации для каждого адресуемого устройства.

Рис.3.1 Схема алгоритма построения ЛМ из матрицы T.

Рис.3.2 Схема алгоритма модуля 4: формирование логической матрицы L1.

Алгоритм построения матрицы L1.

1. Размер матрицы устанавливается равным размеру матрицы T.

2. i=1- номер строки

3. j=1- номер столбца

4. Если i = j, то присвоить элементу матрицы L1 с этими индексами первое значение из t_ij (ω), в противном случае — второе (γ).

5. Увеличить j на единицу.

6. Если j меньше либо равен размеру матрицы L1, перейти к пункту 4.

7. Увеличить I на единицу.

8. Если i меньше либо равен размеру матрицы L1, перейти к пункту 3.

Рис.3.3 Схема алгоритма модуля 6: формирование логической матрицы L2.

Алгоритм построения матрицы L2.

1. Размер матрицы устанавливается равным разнице между размером матрицы T и количеством разъёмов неадресуемых устройств.

2. i`=1

3. j`=1

4. i=1

5. Если устройство, к которому принадлежит разъём i — неадресуемое, к пункту 18.

6. Присвоить элементу матрицы L2_i` первое значение из t_ii(ω).

7. j`=i`+1

8. j=i + 1

9. Если устройство, к которому принадлежит разъём j - неадресуемое, к пункту 15.

10. Ищем кратчайший путь из разъёма i в разъём j и находим γ для этого пути.

11. Удаляем из пути все разъёмы неадресуемых устройств.

12. Если путь состоит более чем из двух вершин, к пункту 15.

13. Присвоить элементу матрицы L2 с индексами i` и j` γ пути.

14. Увеличить j` на единицу.

15. Увеличить j на единицу.

16. Если j меньше либо равен размеру матрицы T, перейти к пункту 9.

17. Увеличить i` на единицу.

18. i = i +1.

19. Если i меньше либо равен размеру матрицы T, перейти к пункту 5.

Рис.3.4 Схема алгоритма модуля 12: формирование логической матрицы L3.

Алгоритм построения матрицы L3.

1. Размер матрицы устанавливается равным количеству различных устройств.

2. i`=1

3. j`=1

4. i=1

5. Если устройство, к которому принадлежит разъём i — неадресуемое, к пункту 7.

6. Если устройство, к которому принадлежит разъём Iи устройство с разъёмом i-1 – одно и то же , к пункту 7.

7. Присвоить элементу матрицы L3_i`i` первое значение из t_ii(ω).

8. j`=i`+1

9. j=i + 1

10. Если устройство, к которому принадлежит разъём j - неадресуемое, к пункту 14.

11. Если устройство, к которому принадлежит разъём j и устройство с разъёмом j-1 – одно и то же, к пункту 14.

12. Ищем кратчайший путь из разъёма i в разъём j и находим γ для этого пути.

13. Удаляем из пути все разъёмы неадресуемых устройств.

14. Присвоить элементу матрицы L3 с индексами i` и j` γ пути.

15. Увеличить j` на единицу.

16. Увеличить j на единицу.

17. Если j меньше либо равен размеру матрицы T, перейти к пункту 7.

18. Увеличить i` на единицу.

20. i = i +1.

21. Если i меньше либо равен размеру матрицы T, перейти к пункту 3.

 Пример преобразования топологической матрицы Т в логическую матрицу L

В качестве примера рассмотрим изображенный на рис. 3.5 фрагмент принципиальной схемы корпоративной ВС, который состоит из 5-ти устройств: рабочих станций A = 1,2 (=1); сервера A = 5 (=2); адресуемого коммутатора A = 3 (=4); неуправляемого коммутатора A = 4 (=3). рабочей станции (=1), неуправляемого коммутатора (=3) и сервера (=2).

В диалоговом режиме взаимодействуют: рабочая станция (A = 1) и сервер (A = 5); рабочая станция (A = 2) и сервер (A = 5); рабочая станция (A = 1) и рабочая станция (A = 2).

В качестве Л, соединяющей У, используется витая пара ( =1), протокол передачи данных – дуплексный канал ( =1).

Рис.3.5 Фрагмент принципиальной схемы корпоративной ВС

В соответствии с п.3 алгоритма формируется таблица М1. В таблице метаданных М1 каждому идентификатору (A.k – B.r) ставится в соответствии порядковый номер i.

Таблица М1

(A,r)	1.1	1.2	2.1	3.1	3.2	4.1	4.2	4.3	5.1	5.2
i	1	2	3	4	5	6	7	8	9	10

Для формирования топологической матрицы T, (см. рис.3.6), используется соотношение (2.1).

		1	2	3	4	5	6	7	8	9	10
	1	1,2			1,1
	2		1,2				1,1
	3			1,1				1,1
	4	1,1			3,2,
Т=	5					3,2				1,1
	6		1,1				4,3
	7			1,1				4,3
	8								4,3		1,1
	9					1,1				2,2
	10								1,1		2,2

Рис. 3.6 Матрица T топологической  структуры ВС

В качестве примера на рис.3.7 изображена матрица L1 логической структуры для фрагмента корпоративной ВС, изображенного на рис.3.5. В соответствии с п.4 алгоритма формируется логическая матрица L1. Матрица L предназначена для отображения узлов, соответствующих тем устройствам, представленным в матрице Т, которым в ВС присвоены логические имена, адреса и номера интерфейсов.

Множество узлов U, отображаемых в матрице L, является подмножеством устройств У (U  У), описываемых в топологической матрице Т, поэтому каждому узлу U_A соответствует устройство У_А.

Для описания логического соединения узлов, соответствующих ВС, используются дуги D, которые могут быть взвешены в соответствии с выбранной метрикой маршрутизации. Маршрутизация между узлами в данной диссертации не рассматривается.

Основным параметром дуги D является тип γ канала связи, организованного между узлами U_A и U_В.

На основании матрицы Т, списков {U} и {D} можно сформировать матрицу L1 логической структуры по соотношению (2).

Выполнение п.п. 1 – 10 алгоритма, (см, рис.3.2), позволяет сформировать матрицу L1 (см. рис.3.7).

По п.5 алгоритма формируется таблица М2. В таблице метаданных М2 каждому идентификатору А ставится в соответствии порядковый номер i.

Таблица М2 

(A,r)	1	2	3	4	5	9	10
i	1	2	3	4	5	6	7

		1	2	3	4	5	6	7	8	9	10
	1	1			1
	2		1				1
	3			1				1
	4	1			4
L1=	5					4				1
	6		1				3
	7			1				3
	8								3		1
	9					1				2
	10								1		2

Рис.3.7  Матрица L1 логической структуры ВС

Выполнение п.п. 1 – 19 алгоритма, (см. рис.3.3), позволяет формировать логическую матрицу L2 (рис.3.9).  Логическая матрица L2 формируется по пункту 6 алгоритма, (см. рис.3.1), но с вычеркнутыми не адресуемыми устройствами (см. рис.3.8), где ω_i=3 и дополнительными дугами. По п.10 используется алгоритм кратчайшего маршрута. По п.11 алгоритма происходит поиск неадресуемого устройства с ω_i=3; удаляем из пути все разъёмы неадресуемых устройств, вычёркиваем строку и столбец, где ω_i=3 (см. рис.3.9).

На рис. 3.8  изображены дуги, отображающие наличие соединения между узлами 1 и 3, которые соответствуют устройствам 1(рабочей станции) и 3(серверу), изображенным на рис.3.5. Как видно из рис. 3.8, дуги отображают также наличие логических соединений между узлами 1 и 3, организованных по нескольким (двум) линиям связи, соединенным через коммутатор 4, который не вошел в состав логического описания ВС, так как он не имеет логического адреса.

Рис. 3.8 Дуги между узлами в логической структуре ВС

		1	2	3	4	5	6	7
	1	1			1
	2		1	1				1
	3		1	1				1
	4	1			4
L2=	5					4	1
	6					1	2
	7		1	1				2

Рис.3.9 Матрица L2 логической структуры ВС

По п. 11 алгоритма, (см. рис.3.1), формируется таблица М3. В таблице метаданных М3 каждому идентификатору А ставится в соответствии порядковый номер i.

Таблица М3

(A,r)	1,1	1,2	2,1	3,1	3,2	5,1	5,2
i	1		2	3		4

Выполнение п.п. 1 – 21 алгоритма, (см. рис.3.4), позволяет формировать логическую матрицу L3 (рис.3.10) с вычеркнутыми неадресуемыми устройствами, где ω_i=3 и дополнительными дугами.

		1	2	3	4
	1	1	1	1	1
L3=	2	1	1		1
	3	1		4	1
	4	1	1	1	2

Рис.3.10 Матрица L3 логической структуры ВС

В рассматриваемом примере в диалоговом режиме взаимодействуют устройства:

1 и 5 , что соответствует контуру q=1;

2 и 5 , что соответствует контуру q=2;

1 и 2 , что соответствует контуру q=;

Решение задачи выбора кратчайших маршрутов по матрице L позволяет определить состав устройств, участвующих в каждом маршруте:

      Таблица 3.1 Список кортежей

Номера контуров	Номера устройств, входящих кратчайший маршрут
q = 1	1 – 3 – 5 – 3 – 1
q = 2	2 – (4) – 5 – (4) – 2
q = 3	1 – (4) – 2 – (4) – 1