Устройство для определения пропускной способности сети

 

Изобретение относится к вычислительной технике и технике связи, в частности к устройствам для оценки пропускной способности сети. Цель изобретения - расширение области применения устройства за счет динамического назначения полюсов (вида сети) и пропускных способностей каналов сети. В наборном поле устройства реализована топология анализируемой сети. Для каждого канала сети с блока задания исходных данных задаются значение его пропускной способности, которое запоминается в соответствующем блоке памяти группы, а также информация о принадлежности начальной и конечной вершин канала к корреспонденту или абоненту сети, которая запоминается в соответствующих ячейках блоков памяти. Вершины, принадлежащие корреспондентам сети, с помощью одних коммутаторов объединяются в начальный фиктивный полюс, а вершины, принадлежащие абонентам сети, с помощью других коммутаторов - в конечный фиктивный полюс. Задача определения пропускной способности многополюсной сети решается путем нахождения методом перебора минимального сечения, отделяющего начальный фиктивный полюс от конечного фиктивного полюса. Минимальное сечение находится в режиме 1 работы устройства путем анализа всех возможных сочетаний каналов сети. Результат анализа выражается в единицах пропускной способности сети, а также номерах каналов, образующих первое минимальное сечение, и выводится на цифровой индикатор. Кроме того, на цифровой индикатор выводятся номера

5G 06F 15/353 в"прогнозирующий фильтр"московский авиационный институт им.серго орджоникидзекотов иван владимиров

„.Я0„„1539792

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (51)5 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) .4419743/24-24 (22) 03.05,88 (46) 30.01.90. Бюл. Р 4 (72) М.В.Буйневич, Ю.А.Волков, С.Е.Любичев и В.С.Новиков (53) 681.325(088.8) (56) Авторское свидетельство СССР

11 387369, кл. G 06 Р 15/20, 1972.

Авторское свидетельство СССР

Р 1249527, кл. С 06 F 15/20, 1984.

i (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПРОПУСКНОЙ СПОСОБНОСТИ СЕТИ (57) Изобретение относится к вычислительной технике и технике связи, в частности к устройствам для оценки пропускной способности сети. Цель изобретения — расширение области применения устройства за счет динамического назначения полюсов (вида се" ти) и пропускных способностей каналов сети. В наборном поле устройства реализована топология анализируемой сети, Для каждого канала сети с блока задания исходных данных задаются значение его пропускной. способности, которое запоминается в соответствующем блоке памяти группы, а также информация о принадлежности начальной и конечной вершин канала к корреспонденту или абоненту сети, которая заИзобретение относится к вычислительной технике и технике связи, s частности к решению на графах задач

1оценки пропускной способности сети связи

Цель изобретения — расширение области применения устройства за счет

2 поминается в соответствующих ячейках

Ф блоков памяти. Вершины, принадлежащие корреспондентам сети, с помощью одних коммутаторов объединяются в начальный фиктивный полюс, а вершины, принадлежащие абонентам сети, с помощью других коммутаторов — в конечный фиктивный полюс. Задача определения пропускной способности многополюсной ,сети решается путем нахождения методом перебора минимального сечения, отделяющего начальный фиктивный полюс от конечного фиктивного полюса.

Минимальное сечение находится в режиме I работы устройства путем анализа всех возможных сочетаний каналов се- с

Щ ти. Результат анализа выражается в единицах пропускной способности сети, а также номерах каналов, образующих первое минимальное сечение, и С выводится на цифровой индикатор. Крф; ме тога, на цифровой индикатор выводятся номера сочетаний, образующих сечения минимальной .пропускной способности. В режиме II работы устройства находятся номера каналов, ком" 1 р бинации которых образуют второе и последующие минимальные сечения (если такие в анализируемой многополюс- © ной сети имеются). 1 ил. b3 динамического назначения полюсов (вида сети) и пропускных способностей каналов сети.

На чертеже представлена структурная схема предлагаемого устройства.

Устройство для определения пропускной способности сети содержит блок

1539792

1 перебора сочетаний, триггеры 2 первой группы, первый ключ 3, счетчик 4, ключи 5 первой, 6 второй и 7 третьей групп, наборное поле 8, блок 9 сравнения, блоки 10 памяти группы, сумматор 11, первый регистр 12, второй регистр 13, триггеры 14 второй группы, первый блок 15 памяти, формирователь 16 импульсов, элемент ИЛИ 17, второй ключ 18, третий ключ 19, блок.

20 задания исходных данных, генератор

21 управляющих последовательностей, дешифратор 22 номера канала, дешифратор 23 начальных вершин, дешифратор

24 конечных вершин, второй 25, третий 26, четвертый 27 и пятый 28 блоки памяти, первый 29, второй 30, третий 31 и четвертый 32 коммутаторы, элемент 33 задержки и цифровой индикатор 34.

Устройство работает в двух режи мах.

В первом режиме определяются значение пропускной способности сети и комбинация каналов, образующих первое минимальное сечение, а во втором режиме — комбинации каналов, образуюп их второе и последующие минимальные сечения:.. (если такие.в сети имеются).

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

5, причем входы представляют начальные, а выходы — конечные вершины каналов.

Для анализа конкретной многополюсной сети на предмет определения значения пропускной способности и комъ-.бинации каналов ; образующей первое минимальное сечение, устанавливается первый режим работы устройства, для чего с блока 20 задания исходных данных выдается сигнал "Сброс", поступающий на вход генератора 21, который вырабатывает и выдает на первый выход . Фь соответствующую последовательность импульсов, закрывающую третий ключ

19, обнуляющую триггеры 2 и 14, блоки

11 12, 15 и записывающую единицы во все разряды блока 13. При этом ключи

5 и 6 открыты, остальные ключи закрыты.

С блока 20 задания исходных данных выдается сигнал Режим I и и поступающий на вход генератора 21, который вырабатывает и выдает на второй выход соответствующую последовательность импульсов, обнуляющую счетчик 4.

С блока 20 задания исходных дан5 ных последовательно задается для каждого канала К вЂ” порядковый номер канала (К=1,K), который поступает на дешифратор 22 номера канала, и С1 — значение его пропускной способности, которое поступает на группу блоков

10 памяти.

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

Вход

Выход

"0" — транзит

"1" — полюс

"0" — корреспондент и и

1 — або25 нент

0

0

0

0 0

0 0

1 0

0 1

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

Сигнал окончания набора информа40 ции о К-м канале поступает на вход генератора 21, который выдает на седьмой выход одиночный импульс, стробирующий срабатывание дешифратора 22 номера канала. Сигнал с К-ro

45, выхода дешифратора 22 номера канала поступает на входы записи -ro блока

10 памяти группы и всех К-х ячеек памяти блоков 25-28 памяти и разрешает запоминание информации, находящейся на их информационных

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

55 всех К каналом сети; в ячейках второго блока 25 памяти хранится информация о принадлежности начальных вершин корреспондентам сети;

153979

5 в ячейках третьего блока 26 памяти хранится информация о принадлежности начальных вершин абонентам сети; ! в ячейках четвертого блока 27 памяти хранится информация о принадлежности конечных вершин корреспондентам сети; в ячейках пятого блока 28 памяти хранится информация о принадлежности конечных вершин абонентам сети.

С блока 20 задания исходных данных выдается сигнал "Пуск", поступающий на вход генератора 21, который выдает на шестой выход пусковой импульс, 15 который поступает на стробирующие входы всех коммутаторов 29-32, которые в соответствии с сигналами на своих информационных входах осуществля-. ют физическую коммутацию фиктивных полюсов, при этом первый 29 и третий

31 коммутаторы срединяют К+1-й выход блока 1 перебора состояний с вершинами, являющимися корреспондентами сети, а второй 30 и четвертый 32 25 коммутаторы — управляющий вход первого ключа 3 с вершинами, являющимися абонентами сети. Коммутируемыми начальными вершинами К каналов являются информационные входы, а конеч- 30 ными — информационные выходы соответствующих ключей 5.

Пусковой сигнал, задержанный в элементе 33 задержки на время, необходимое для срабатывания коммутаторов 29-32, поступает на вход запуска блока 1 перебора сочетаний, который последовательно одно за другим, выдает на свои К выходов сочетания из К каналов сети по одному, 40 двум и т.д. в виде единичных сигналов, а также прямоугольный импульс на свой К+1-й выход при выдаче кажрого сочетания.

Прямоугольный импульс с K+1-Го 45 выхода блока 1 перебора сочетаний поступает на вход прямого счета счетчика 4, с выхода которого информация о его текущем состоянии подается на информационные входы второго 18 и третьего 19 ключей. При поступлении сигналов с выходов блока 1 перебора сочетаний на установочные входы, соответствующие триггеры 2 выдают единичные сигналы на управляющие входы 55 ключей 5, которые отключают информационные. входы от выходов и тем.самым разрывают связи между некоторыми вершинами.

Прямоугольный импульс, поступаю- - щий с К+1-го выхода блока 1 перебора сочетаний на управляющий вход первого 29 и третьего 31 коммутаторов, в случае связности начального и конечного фиктивных полюсов (т.е. текущее сочетание каналов не является сечением анализируемой многоголюсной сети) с управляющего выхода второго

30 и четвертого 32 коммутаторов проходит на управляющий вход первого ключа 3, отключая от выхода его информационный вход. Поэтому прямоС угольный импульс, поступающий с К+

+1-го выхода блока 1 перебора сочетаний на информационный вход первого ключа 3, на его выход не проходит.

Задним фронтом прямоугольного импульса, поступающего с К+1-го выхода блока 1 перебора сочетаний на первые входы сброса триггеров 2, они перебрасываются в исходное (нулевое) состояние.

Так устройство работает до момента, пока очередное сочетание каналов не образует сечение анализируемой многополюсной сети, вследствие чего прямоугольный импульс с К+1-ro выхода блока 1 перебора сочетаний не проходит на управляющий вход первого ключа 3 и .не отключает его информационный вход от выхода. Тогда прямоугольный импульс, поступающий с K+1-ro выхода блока 1 перебора сочетаний на информационный вход первого ключа 3, проходит через те ключи 6, которые открыты единичными сигналами триггеров 2, на входы считывания соответствующих блоков 10 памяти группы. Значения пропускных способностей каналов текущего сочетания с выходов соответствующих блоков 10 памяти группы поступают на входы сумматора 11. Суммарное значение пропускных способностей каналов данного сочетания, являющегося сечением анализируемой сети, поступает на вход первого регистра 12, в котором оно запоминается, и подается в параллельном коде на первый информационный вход блока 9 сравнения и на информационный вход второго регистра 13. Значение пропускной способности, хранящееся во втором регистре 13, поступает на второй "информационный вход блока 9 сравнения.

Сравнение значений пропускных способностей, поступающих на первый!

539792 и второй информационные входы блока

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

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

4 на вход первого блока 15 памяти, где она запоминается.

Если значение пропускной способности, поступающее на первый информационныи вход блока 9 сравнения, меньше значения, поступающего íà его второй информационный вход, то сигнал с выхода "Меньше" блока 9 сравнения через элемент ИЛИ 17 проходит на вход формирователя 16 импульсов. С выхода формирователя 16 импульсов прямоугольный импульс поступает на вход сброса первого блока 15 памяти и стирает всю хранящуюся там 25 информацию, а также на вход записи второго регистра 13, в котором запоминается значение пропускной способности, поступающее на его информационный вход с выхода первого ре- 30 гистра 12. Кроме того, прямоугольный импульс с выхода формирователя

16 поступает на первые входы сброса триггеров 14, переводя их в нулевое состояние, и на информационные входы ключей 7. Для реализации жесткой син-, хронизации работы устройства длительность прямоугольного импульса, выдаваемого формирователем 16, должна быть меньше длительности прямоугольного импульса, поступающего с

К+1-ro выхода блока 1 переброса сочетаний. Поэтому прямоугольный импульс с выхода формирователя 16 проходит через ключи 7, которые открыты единичными сигналами с выходов, .триггеров 2, соответствующих данному сочетанию, на установочные входы одноименных триггеров 14, задним фронтом перебрасывая их в единичное сос,, J тояние. НЬмера взведенных триггеров

14 выводятся на цифровой индикатор 34.:

Аналогично обрабатываются все обнаруженные в ходе работы устройства сечения.

После перебора всех сочетаний единичное состояние тех или иных. триггеров 14 определяет номера каналов первого минимального сечения, обнаруженного в ходе работы устройства (номера каналов при этом отображаются на цифровом индикаторе 34); записанные в первом блоке 15 памяти номера являются номерами сочетаний, образующих сечения такой же минимальной пропускной способности (если такие в анализируемой мнс ополюсной сети имеются). Записанное во втором регистре 13 значение пропускной способности сети отображается на цифровом индикаторе 34.

С блока 20 задания исходных данньтх выдается сигнал "Чтение", поступающий на вход генератора 21, который вырабатывает и вьщает на выход считывания соответствующую последовательность импульсов, управляющую выдачей информации о номерах сочетаний,» хранящихся в первом блоке 15 памяти, на цифровой индикатор 34. В результате на цифровом индикаторе 34 последовательно отображаются номера со четаний каналов, образующих второе и последующие минимальные сечения если такие в анализируемой многополюсной сети имеются ).

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

<В этом случае с блока 20 задания исходных данных выдается сигнал "Сброс и сигнал "Режим II, поступающий на вход генератора 21, который вырабатывает и выдает на четвертый выход соответствующую последовательность импульсов, открывающую третий ключ 19 и заносящую в счетчик 4 количество импульсов, равное его полной емкости.

С блока 20 задания исходных даняых вьдается информация об одном из номеров Н, отображенных на цифровом индикаторе 34 сочетаний, поступающая на вход генератора 21, который вырабатывает:и выдает на третий выход соответствующую последовательность из

Н импульсов. Эта последовательность подается на вход обратного счета счетчика 4 и устанавливает значение счетчика 4, равное его полной емкос- . ти минус Н.

С блока 20 задания исходных данных вьдается сигнал "Пуск".

После выдачи блоком 1 перебора сочетаний Н-ro сочетания счетчик 4 выдает импульс переполнения через от1539792 крытый третий ключ 19 и элемент ИЛИ

17 на вход формирователя 16, выдающего прямоугольный импульс, передний фронт которого обнуляет триггеры 14. Прямоугольный импульс с выхо5 да формирователя 16 проходит через ключи 7, которые открыты единичными сигналами с выходов триггеров 2, оказавшихся в единичном состоянии при выдаче Н-го сочетания, на установочные входы одноименных триггеров 14, задним фронтом перебрасывая их в единичное состояние. Номера взведенных триггеров 14, отображающиеся на цифровом индикаторе 34, соответствуют номерам каналов сечения, образованного их Н-м сочетанием.

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

Устройство для определения про- 25 пускной способности сети, содержащее ! блок перебора сочетаний, первую и вторую группы К триггеров, первый и второй ключи, счетчик, первую, вто-. рую и третью группы К ключей, наборное поле, блок сравнения, группу К блоков памяти, сумматор, первый и второй регистры, первый блок памяти, формирователь импульса, элемент ИЛИ,, причем К-й выход блока перебора сочетаний (К=1,...,К) подключен к устано35 вочному входу К-ro триггера первой группы, а (K+I)-й выход соединен с первыми входами сброса триггеров первой группы, информационным входом 4р первого ключа и входом прямого счета счетчика, выход К-го триггера первой группы подключен к управляющим входам

К-х ключей первой, второй и третьей групп, информационный вход и выход 45

-ro ключа первой группы подключен к К-му выходу и входу наборного поля соответственно, выход первого ключа соединен с информационными входами ключей второй группы и со стробирую- 5р щим входом блока сравнения, выход

К-го ключа второй группы подключен к входу считывания К-го блока памяти группы, выход которого соединен с

К-м информационным входом сумматора, выход которого подключен к информа. ционному входу первого регистра, выход которого соединен с информационным входом второго регистра и первым информационным входом блока сравнения, выход второго регистра соединен с вторым информационным входом блока сравнения, выход "Меньше" которого подключен к первому входу элемента

ИЛИ, выход которого соединен с входом формирователя импульса, выход которого подключен к первым входам сброса триггеров второй группы, информационным входам ключей третьей группы, первому входу сброса первого блока памяти и входу записи второго регистра, выход "Равно" блока сравненця подключен к управляющему входу второго ключа, выход которого соединен с информационным входом первого блока памяти, а вход подключен к выходу счетчика, выход К-го ключа третьей группы подключен к установочному входу К-го триггера второй группы, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения устройства за счет динамического назначения полюсов (вида сети) и пропускных способностей каналов сети, в него введены третий ключ, блок задания исходных данных, генератор управляющих последовательностей, дешифратор номера канала, начальных и конечных вершин, с второго по пятый блоки памяти, четыре коммутатора и элемент задержки, при этом выходы блока задания исходных данных подключены к соответствующим входам генератора управляющих последовательностей, информационным входам дешифраторов номера канала, начальных и конечных вершин, блоков памяти группы, первый выход генератора управляющих последовательностей соединен с вторыми входами сброса триггеров первой и второй групп, первым управляющим вхоpом третьего ключа, входами сброса сумматора и первого регистра, вторым входом сброса первого блока памяти и установочным входом второго регистра, второй и третий выходы генератора управляющих последовательностей подключены к входу сброса и входу обратного счета счетчика соответственно, четвертый выход генератора управляющих последовательностей соединен с входом предварительной записи счетчика и вторым управляющим входом третьего ключа, пятый выход генерато" ра управляющих последовательностей соединен с входом считывания первого

1539792

Составитель В.Сычев

Редактор А.Лежнина Техред М,Ходанич

Корректор -Лончакова

Заказ 220 Тираж 556 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 блока памяти, шестой выход генератора управляющих последовательностей соединен со стробирующими входами коммутаторов и через элемент задержки с входом запуска блока перебора сочетаний, седьмой выход генератора управляющих последовательностей подключен к стробирующему входу дешифратора номера канала, К-й выход которого соединен с входом записи К-rd блока памяти группы и К-ми адресными входами второго, третьего, четвертого и пятого блоков памяти, первый и второй выходы дешифратора начальных вершин подключены к информационным входам второго и третьего блоков памяти, соответственно, первый и второй выходы дешифратора конечных вершин подключены к информационным входам четвертого и пятого блоков памяти соответственно, выходы второго, третьего, четвертого и пятого блоков памяти соединены с соответствующими информационными, входами первого, второго, третьего и четвертого коммутаторов соответственно, управляющие входы первого и третьего коммутаторов соединены с (K+1)-м выходом блока перебора сочетаний, управляющие выхОды второго и четвертого коммутаторов

5 соединены с управляющим входом первого ключа, К-й информационный выход первого коммутатора подключен к К-му информационному входу второго коммутатора, информационному входу К-го ключа первой группы и К-му выходу наборного поля, К-й информационный вход четвертого коммутатора подключен к К-му информационному выходу третьего коммутатора, выходу К-го ключа первой группы и К-му входу наборного поля, выход счетчика соединен с информационным входом третьего ключа, выход которого соединен с вторым входом элемента ИЛИ, выход

-ro триггера второй группы являет- ся выходом номера канала устройства, а выходом номера сочетаний и выходом пропускной способности сети являются

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