Устройство для определения места максимального потока в сети связи

Полезная модель относится к измерительной технике и может быть использована для исследования параметров систем, описываемых графами, в частности в информационно-вычислительных сетях или сетях связи. Технический результат состоит в повышении достоверности при определении места максимального потока, которое является местом потенциального нарушения или серьезного затруднения связи в сети. Устройство содержит блок 1 управления и синхронизации, блок 2 задания матрицы, блок 3 формирования дуг графа, регистр 4, блок 5 регистрации, блок 6 определения минимума и блок 7 сравнения. 1 илл.

Полезная модель относится к измерительной технике и может быть использована для исследования параметров систем, описываемых графами, в частности в информационно-вычислительных сетях или сетях связи.

Известно устройство определения путей распространения сигналов в системах, описываемых графами (например, патент РФ №2111533, кл. G06F 15/173, опубл. 1998 г), включающее блок задания матрицы, соединенный с блоком управления и синхронизации, блок формирования дуг графа, соединенный с блоком регистрации, регистр.

Известное устройство не позволяет находить место максимального потока в сети связи.

Задачей настоящей полезной модели является разработка устройства для определения места максимального потока, которое является местом потенциального нарушения или серьезного затруднения связи в сети.

Технический результат состоит в повышении достоверности при определении места максимального потока.

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

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

Блок-схема устройства приведена на чертеже. Устройство содержит блок 1 управления и синхронизации, блок 2 задания матрицы, блок 3 формирования дуг графа, регистр 4, блок 5 регистрации, блок 6 определения минимума и блок 7 сравнения.

Устройство работает следующим образом. Блок 1 выполняет управление и синхронизацию работы устройства. Он может быть выполнен на микропроцессоре. В блоке 2 формируются элементы матрицы графа сети. Он может быть выполнен в виде блока памяти. В этот блок поступает в качестве исходных данных набор всех вершин графа и набор всех дуг графа. Набор дуг представляет собой совокупность двух вершин: исходной и конечной для дуги графа. Все вершины должны быть пронумерованы и каждая дуга задается набором двух чисел - номеров соответствующих вершин: исходной и конечной, которые связывает конкретная дуга. Процесс нумерации вершин является заданием исходных данных и выполняется заранее и вне данного устройства. На вход данного устройства подаются только заранее сформированные наборы чисел. Нумерация вершин производится таким образом, что два полюса между которыми необходимо найти минимальный разрез (максимальный поток) получают минимальное (1) и максимальное (N) значения. Где N - количество вершин графа. Все остальные вершины нумеруются по мере удаления от полюсов графа. Мерой удаленности является минимальный путь по количеству дуг начиная с полюса графа и до конкретной вершины. Наиболее близкими являются вершины непосредственно связанные одной дугой с соответствующим полюсом и им присваиваются ближайшие к этому полюсу номера. Нумерация равноудаленных вершин производится в произвольном порядке. Каждая вершина нумеруется только один раз. Таким образом, в блоке 2

хранятся два набора: 1) номера (числа) вершин графа и 2) пары чисел (номеров вершин), определяющие дуги графа.

Блок 3 определяет наличие связей для каждой вершины графа -формирует (задает значения) элементы прямоугольной подматрицы в матрице графа связи. На основании информации, хранящейся в блоке 2, из соответствующих набора (вершин) чисел и набора (дуг) пар чисел в блоке 3 формируется нижнетреугольная матрица (в которой выше главной диагонали расположены только нули) графа сети связи. Размерность этой матрицы соответствует количеству вершин графа (т.е. максимальному номеру вершины графа). Изначально все клетки нижнетреугольной матрицы получают значение "ноль" (т.е. в них записывается ноль). Далее для каждой дуги выполняют следующее. Если дуга связывает две вершины, то в клетке нижнетреугольной матрицы, расположенной на пересечении столбца и строки с соответствующими номерами вершин графа, записывается единица. Так как матрица является нижнетреугольной, то каждой дуге может соответствовать только одна клетка матрицы. После выполнения записывания единицы для каждой дуги графа получаем требуемую нижнетреугольную матрицу для проведения дальнейших действий.

В Регистр 4 записывают минимально допустимое число, при котором сеть может работать с заданным уровнем надежности, при этом "О" (ноль) - это признак разрыва сети. Уровень надежности может быть равен единице или более.

Блок 5 выполняет регистрацию (суммирование единиц) связей в каждой прямоугольной подматрице матрицы графа связи из блока 3 и может выполняться в виде сумматора.

Блок 6 выполняет выбор минимальных чисел из зарегистрированных в блоке 5 и может быть выполнен в виде блока суммирования. Блок 7 выполняет сравнение установки в регистре 4 и минимального числа из блока 6, т.е. определение места максимального потока, которое является местом потенциального нарушения (возможности обрыва в сети) или

серьезного затруднения связи в сети. При указании единицы в регистре 4 такое место практически строго определено.

Таким образом, устройство позволяет достоверно определить место максимального потока, которое является местом потенциального нарушения или серьезного затруднения связи в сети

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