Методы и алгоритмы проектирования топологии терминальных сетей передачи данных

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

Вычислительная сеть представляет собой совокупность терри-ториально-распределенных центров обработки данных и терминалов пользователей, объединенных в единую систему сетью передачи данных (СЦЦ), и является важным классом систем сбора, передачи и обработки информации, совершенствование которых отмечено в ряду важнейших проблем в области технических наук, подлежащих решению в одиннадцатой пятилетке [ I ].

Проектирование и реализация крупномасштабных ВС ставят ряд сложных проблем, и в числе наиболее важных — определение оптимальной топологической структуры СЦЦ, поскольку именно топологическая структура СЦЦ главным образом определяет стоимость ВС [23]. От успешного решения этой проблемы зависит экономическая эффективность всей сети.

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

Важным классом СЦЦ являются терминальные сети передачи данных (ТСЦЦ) .предназначенные для подключения удаленных терминалов к сети ЭВМ (рис.В.1) [13].

Характерными особенностями ТСЦЦ является наличие большого числа (несколько сотен) оконечных пунктов сети — терминалов и одного центра (центра обработки данных или узла коммутации БСЦЦ), а также значительный удельный вес затрат на ТСЦЦ в общей сумме затрат на ВС.

По оценкам специалистов [12], затраты на организацию каналов ТСЦЦ составляют более 60% общих затрат на ВС. Поэтому актуальной является задача определения топологической структуры ТСЦЦ минимальной стоимости. Актуальность решения этой задачи возрастает в связи с тем, что затраты на передачу данных по каналам связи с течением времени уменьшаются относительно медленнее, чем затраты на их обработку и хранение, и это, в свою очередь. повышает требования к топологии ТСЦЦ.

В настоящее время существует два подхода к решению проблемы проектирования топологии СЦЦ. Первый подразумевает использование строгих математических методов оптимизации [9, 31, 58, 78, 83, 86, 102] и возможен лишь для расчета топологии сетей малой размерности из-за значительных трудностей вычислительного характера.

Поэтому наиболее перспективным направлением в настоящее время является подход, использующий приближенные (эвристические)ме-тоды оптимизации [2−4, 10, 17−21, 29, 34, 37, 42−44, 49, 52−54, 62, 67, 71−73, 75, 80, 81, 85−95, 101 и др.]. Достоинством такого подхода является принципиальная возможность решения задач большой размерности с относительно малыми вычислительными затратами. Однако большинству эвристических методов присущ серьезный.

Рис.В.1. Структура вычислительной сети: БСЦЦ — базовая сеть передачи данных,.

ГВМ — главная ЭВМ, ТСЦЦ — терминальная сеть передачи данных, Т — терминал. недостаток — поровдение одного единственного решения, точность которого зависит от специфики решаемой задачи. Поэтому наибольшее предпочтение следует отдать субоптимальным поисковым методам [54], позволяющим вести субоптимальный поиск на множестве допустимых решений и улучшать получаемые решения до тех пор, пока позволяют ограничения на время поиска. При этом решащее значение приобретают вопросы повышения эффективности субоптимального поиска на множестве допустимых решений.

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

Повышение эффективности проектирования может быть достигнуто на основе использования диалоговых человеко-машинных систем автоматизированного проектирования, в которых проектировщику обеспечивается возможность в процессе диалога с машиной проводить постановку и исследование наиболее сложных, неформализуемых проблем, а на ЭВМ возлагается задача информационного обеспечения процесса исследования и решения наиболее трудоемких в вычислительном отношении задач. О важности данного направления говорит тот факт, что оно отмечено в качестве одного из основных направлений развития науки ж ускорения технического прогресса [ I].

Однако к настоящему времени можно привести лишь единичные примеры (например, [20]) человеко-машинных систем проектирования структуры СЦЦ, основной недостаток которых заключается в том, что роль проектировщика в них сводится лишь к ручной коррекции порождаемых ЭВМ решений для удовлетворения определенных критериев, трудно формализуемых или не учтенных в модели оптимизации.

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

Цель диссертационной работы состоит в разработке универсальных и эффективных методов проектирования топологии ТСЦЦ и создании на основе разработанных методов диалоговой системы автоматизированного проектирования топологии ТСЦЦ.

Методы исследования. При решении поставленных задач использовались методы субоптимального программирования, элементы теории массового обслуживания, теории графов и множеств.

При разработке комплекса программ проектирования топологии ТСЦЦ использовались идеи современного программирования: структурного программирования, нисходящего проектирования программ, модульного программирования.

Научная новизна. В диссертационной работе получены следующие основные оригинальные результаты:

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

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

3. Разработан метод синтеза топологии ТСЦЦ, имеющих комбинированную структуру.

4. Разработаны быстродействующие алгоритмы генерации допустимых решений задач синтеза топологии ТСЦЦ на базе метода размытых эвристик и показана их эффективность в задачах практической размерности.

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

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

Реализация и внедрение результатов работы. Результаты диссертационной работы нашли применение при проектировании Республиканской СЦЦ Армянской ССР, разрабатываемой в Ереванском отделении НИИ связи и Армянском филиале Всесоюзного НИИ организации и управления, а также в разработках Института электронных управляющих машин и Московского НИИ приборной автоматики. Субоптимальные методы, предложенные в диссертации, были использованы при решении задачи оптимизации технического обслуживания абонентских установок телеграфной сети на Центральном Телеграфе Минсвязи СССР. Внедрение результатов подтверждается соответствующими актами.

Апробация работы. Материалы диссертации докладывались и обсуждались на научно-технических конференциях профессорско-преподавательского состава Московского электротехнического института связи (Москва, 1979, 1980 гг.), на выездном заседании научно-технического семинара «Машинные методы исследования и проектирования радиотехнических систем, радиоэлектронных цепей и систем связи» (Косов, 1979 г.), на заседаниях 5, 6, 7-й Всесоюзной школы-семинара по вычислительным сетям (Владивосток, 1980, Винница, 1981, Цахкадзор, 1982), на заседании научно-технического семинара «Моделирование и управление в сложных системах передачи и распределения информации» (Москва, 1981 г.), на научно-технической конференции профессорско-преподавательского состава Ереванского политехнического института (Ереван, 1982 г.).

Публикации. Основные результаты диссертации отражены в 8 печатных работах.

На защиту выносятся:

1. Метод повышения эффективности субоптимальных алгоритмов, ведущих поиск на множестве допустимых решений.

2. Методика человеко-машинного проектирования топологической структуры ТСЦЦ.

3. Метод синтеза топологии ТСЦЦ комбинированной структуры.

4. Алгоритмы генерации допустимых решений задач синтеза топологии ТСЦЦ.

5. Диалоговая система автоматизированного проектирования топологии ТСЦЦ.

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

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

Во второй главе разработана методика эффективного субоптимального синтеза топологии ТСЦД. Предложен универсальный метод повышения эффективности субоптимального поиска — метод взаимозаменяемых фрагментов. Разработана методика человеко-машинного проектирования топологии ТСЦД на базе метода эвристического ветвления. Предложен метод синтеза комбинированных топологических конфигураций ТСЦЦ.

Б третьей главе разработаны алгоритмы, реализующие предложенные в главе 2 методы проектирования топологии ТСЦД и приведены экспериментальные оценки их эффективности.

В главе 4 рассмотрены воцросы практической реализации методов и алгоритмов, разработанных в главах 2,3, в виде пакета прикладных программ, работающего в диалоговом режиме. Описаны возможности и структура созданной диалоговой системы проектирования топологии ТСЦД. Разработан язык взаимодействия с пользователем системы и приведен пример практического проектирования, иллюстрирующий работу системы.

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

В заключении представлены основные результаты диссертационной работы.

В приложении I приведены диагностические сообщения диалоговой системы проектирования топологии ТСВД.

В приложении 2 приведены акты, подтверждающие результаты внедрений.

Термины и понятия, использованные в диссертации, заимствованы из терминологии [13].

Основные результаты диссертационной работы заключаются в следующем:

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

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

3. Впервые рассмотрена задача проектирования топологии ТСПД в классе моделей комбинированной структуры и предложен метод ее решения.

4. Разработаны алгоритмы генерации допустимых решений задачи проектирования топологии ТСПД на базе метода размытых эвристик.

5. Проведено исследование разработанных алгоритмов на ЭВМ.

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

6. Предложенная методика реализована в виде пакета прикладных программ, работающего в диалоговом режиме и представляющего собой удобный инструмент проектирования топологической структуры ТСЦЦ.

7. Результаты диссертационной работы внедрены в практику проектирования Московского НИИ приборной автоматики, Института электронных управляющих машин, Ереванского отделения НИИ связи и Армянского филиала ВНИИ проблем организации и управления.

ЗАКЛЮЧЕНИЕ

.

Поставленная в диссертационной работе задача разработки эффективных методов и алгоритмов проектирования топологии ТСПД актуальна. Ее актуальность определяется большими затратами на организацию каналов ТСПД, несовершенством существующих методов проектирования топологии, а также обусловлена целевой комплексной научно-технической программой 0.Ц.025, утвервденной постановлением ГКНТ СССР, Госплана СССР и Президиума АН СССР № 492/245/164 от 8 декабря 1981 г.

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