Содержание к диссертации
ВВЕДЕНИЕ 5
ГЛАВА 1. ПРИНЦИПЫ УПРАВЛЕНИЯ ПОТОКАМИ ДАННЬК И РЕСУРСАМИ 15
1.1. Общие задачи и функции механизмов управления потоками
данных и ресурсами и методы их моделирования 15
1. 2. Управление в многопроцессорных системах 23
1. 3. Управление в локальных сетях 30
1. 4. Управление в глобальных сетях 35
Выводы к главе 1 47
ГЛАВА 2. АНАЛИЗ КОНФЛИКТОВ ДОСТУПА К РЕСУРСАМ
МНОГОПРОЦЕССОРНЫХ СИСТЕМ 49
2. 1. Система с полносвязным интерфейсом:
непрерывные модели 49
2. 2. Асимптотический анализ моделей большой размерности 70
2. 3. Система с полносвязным интерфейсом:
дискретные модели 76
2. 4. Система с односвязным интерфейсом и блоками
локальной памяти 84
Выводы к главе 2 90
ГЛАВА 3. СРАВНИТЕЛЬНЫЙ АНАЛИЗ СТРАТЕГИЙ ДОСТУПА С ОБРАТНОЙ
СВЯЗЬЮ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ 92
3. 1. Системы с неравномерным доступом к памяти 92
3. 2. Стратегии доступа и критерии эффективности 95
3. 3. Точные модели и основные допущения 102
3. 4. Приближенные модели и методы 108
3. 5. Численные результаты 116
3. 6. Вывод приближений для дисперсий и вероятностных
распределений 138
Выводы к главе 3 141
ГЛАВА 4. УПРАВЛЕНИЕ КРИТИЧЕСКИМИ РЕСУРСАМИ
В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ 143
4. 1. Описание модели 144
4. 2. Системы с малым числом критических ресурсов 148
4. 3. Система с большим числом критических ресурсов 158
Выводы к главе 4 168
ГЛАВА 5. УПРАВЛЕНИЕ ПОТОКАМИ ДАННЫХ И РЕСУРСАМИ
В ЛОКАЛЬНЫХ СЕТЯХ 170
5. 1. Анализ методов приоритетного доступа 170
5. 2. Оценка производительности локальной сети
архитектуры <клиент-сервер» 182
Выводы к главе 5 196
ГЛАВА 6. УПРАВЛЕНИЕ КАНАЛАМИ СВЯЗИ 198
6. 1. Структура линейных протоколов 198
6. 2. Модели линейных протоколов 211
Выводы к главе 6 221
ГЛАВА 7. УПРАВЛЕНИЕ СКВОЗНОЙ ТРАНСПОРТИРОВКОЙ ДАННЫХ 223
7. 1. Методы управления сквозной транспортировкой данных 223
7. 2. Анализ ограничения нагрузки и длительности тайм-аута
на ожидание подтверждений в логическом соединении 248
7. 3. Анализ схем повторных передач пакетов 263
7. 4. Имитационное моделирование сквозных протоколов 270
7. 5. Управление передачей пакетов при объединении сетей 292
Выводы к главе 7 303
ЗАКЛЮЧЕНИЕ 3 05
Список обозначений и сокращений 309
ЛИТЕРАТУРА 311
ПРИЛОЖЕНИЕ. МОДЕЛИРОВАНИЕ ОСНОВНЫХ ПАРАМЕТРОВ
ФУНКЦИОНИРОВАНИЯ КОМПЬЮТЕРНОЙ СЕТИ ГОСУДАРСТВЕННОЙ ДУМЫ 329
Введение к работе
Актуальность проблемы. Достижения микроэлектроники и техники связи создали предпосылки для быстрого развития распределенных вычислительных систем (ВС). Их основными компонентами в части обработки и передачи информации являются многопроцессорные ВС (МВС) и сети. Появление сетей было связано со стремлением к коллективному использованию автономных компьютерных, программных и информационных ресурсов, находящихся во многих отдельных вычислительных центрах, и соответственно, к более эффективному совместному распределению нагрузки на эти ресурсы [1, с.307]. Создание МВС основано на использовании параллелизма алгоритмов многих задач [2] путем выполнения ветвей такой задачи одновременно на множестве вычислительных элементов (процессоров), осуществляющих доступ к общим устройствам хранения информации, основным из которых является общая память. Таким образом, МВС обладают тем же преимуществом перед однопроцессорными системами, что и сети ЭВМ перед отдельными ЭВМ, а именно - повышением коэффициентов использования ресурсов системы.
Одним из основных критериев эффективности и качества ВС и сетей, принимаемых во внимание при проектировании, производстве, определении и расширении конфигурации и настройке в процессе эксплуатации, т. е. в течении всего жизненного цикла, является их производительность [3,4]. При проектировании новых ВС и сетей, архитектура которых значительно отличается от существующих, единственным методом прогнозирования производительности является моделирование [5]. При настройке ВС или сетей на определенную нагрузку
(траффик) и при планировании их мощности для удовлетворения возрастающих потребностей, моделирование является наиболее экономичным способом поиска оптимальной конфигурации среди огромного множества возможных конфигураций. Даже при повседневном управлении ВС и сетью моделирование помогает выбрать наилучший вариант ее использования. Принципиальным достоинством применения моделирования, помимо получаемых численных оценок производительности, является осознание внутренних особенностей структуры и поведения ВС и сети, которое приходит в процессе разработки и анализа модели [6]. С ростом возможностей и мощностей средств вычислительной техники и связи требования к методам их моделирования становятся все более жесткими, так как эффективность ВС и сетей наряду с применением передовых технических и программных средств определяется уровнем проработки и корректностью решения вопросов их моделирования и оценки.
В связи с этим проблемы моделирования и оценки производительности ВС и сетей представляют устойчивый интерес: издаются специализированные журналы по данной тематике (Performance Evaluation, Performance Evaluation Review, Computer Performance и др. ); в ведущих журналах типа IEEE Transaction on Computers и Communications of the ACM периодически выходят тематические выпуски, посвященные появлению новых методов оценки производительности; ежегодно проходит множество специализированных международных конференций по оценке производительности и моделированию ВС и сетей.
Сети ЭВМ и МВС представляют собой совокупность устройств хранения и обработки информации, обменивающихся потоками данных посредством некоторой сети связи, также состоящей из различного рода устройств. Число и быстродействие этих устройств всегда ограничены,
поэтому возникают очереди и, следовательно, задержки в обслуживании. Поэтому естественным аппаратом аналитического моделирования сетей ЭВМ и МВС является теория систем и сетей массового обслуживания, называемая также теорией очередей [7, с.7]. При этом сети ЭВМ и МВС представляются в виде сетей очередей, где узлами являются устройства связи, хранения и обработки, а заявки - это запросы пользователей или одних устройств к другим, а также задачи, процессы, пакеты или сообщения.
Первые подходы к анализу сетей очередей были даны в работах [8-10] с 1957 г. по 1967 г., однако только с работы [11] в 1971 г. начинается активное использование сетей массового обслуживания в качестве адекватных моделей ВС и информационно-вычислительных сетей. Далее особый вклад в развитие методов анализа и применения сетей очередей для моделирования различных ВС и сетей внесли работы следующих ученых: Bard [12], Baskett и Chandy [13], Busen [14], Kelly [15], Kleinrock [1,16,17], Kobayashi [18,19], Lavenberg [6], Reiser [20], Sevcik [21], Whitt [22], Авен [3,23], Башарин и Бочаров [7], Вишневский и Жожикашвили [24], Головкин [25], Гнеденко и Коваленко [26], Игнатущенко [27], Каган [28], Липаев [29], Майоров [30], Прангишвили [31,32], Самойленко [33], Сокол [34], Якубайтис [35] и др. Широкое использование аппарата сетей массового обслуживания привело к тому, что с 1986 г. стал выходить специальный журнал Queueing Systems; как в нашей стране (в том числе и в Институте проблем управления), так и за рубежом появилось много коммерческих программных систем по расчету сетей массового обслуживания (из зарубежных систем следует отметить QNET4, RESQ, PANACEA и др. ).
Многие проблемы проектирования сетей ЭВМ и МВС связаны с распределением ресурсов среди конкурирующих требований на эти ресурсы,
причем моменты появления этих требований и требуемые объемы ресурсов заранее неизвестны, носят случайный характер, возможно различный для разных категорий источников (абонентов, пользователей), и варьируются в широких пределах [23]. Эти обстоятельства приводят к необходимости включения в сети ЭВМ и МВС некоторого механизма управления потоками данных и ресурсами (УПДР). Обычно механизм УПДР представляет собой множество операционных правил [1], согласно которым обрабатываются потоки данных (запросов, сообщений, пакетов и т.п.). Эти правила должны определять маршруты прохождения потоков данных, а также стратегии, алгоритмы и дисциплины обслуживания в узлах МВС и сети; прогнозировать, предотвращать и исключать перегрузки и блокировки путем регулирования входного траф-фика и управления распределением буферной памяти.
В связи с вышеизложенным, особенность обобщенной модели сети ЭВМ или МВС состоит в том, что она включает три взаимосвязанных компонента: модель оборудования, модель потоков данных и модель механизма УПДР. Модель оборудования сети или ее участка отражает ресурсное обеспечение сети ЭВМ (топологию, быстродействие каналов и процессоров, количество буферов) или МВС (быстродействие процессоров и модулей памяти, особенности и характеристики системы коммутации). Моделью потоков данных (или нагрузки) описывается поведение требований к ресурсам сети ЭВМ или МВС (места возникновения и потребления потоков, их интенсивность и т.п.). Модель механизма УПДР представляет собой алгоритм распределения ресурсов, включающий пороговые ограничения, выбор маршрутов, вид алгоритмов доступа и т. п.
К настоящему времени в России и за рубежом создан значительный задел математических методов оценки производительности сетей
ЭВМ и МВС (см. выше), основанных на аппарате теории массового обслуживания и учитывающих влияние первых двух компонент, т. е. параметров оборудования и потоков данных, при простейших видах механизмов управления (или при существенно упрощающих допущениях). В гораздо меньшей степени решена проблема разработки методов оценки производительности для достаточно сложных реальных механизмов УПДР, обеспечивающих высокоэффективную работу современных сетей ЭВМ и МВС. Главная трудность при этом состоит в сильной взаимозависимости поведения различных очередей в соответствующих моделях реальных механизмов УПДР [1,5]. Имеющиеся по этой проблематике публикации в значительной степени разрозненны и отражают, как правило, отдельные частные аспекты указанной проблемы.
Целью диссертационной работы является разработка методологической базы и математического аппарата моделирования механизмов УПДР в сетях ЭВМ и МВС в ориентации на построение, анализ эффективности и развитие реальных сетей и МВС.
Методы исследования. Основные методы исследования механизмов УПДР, применяемые в диссертации, относятся к теории систем и сетей массового обслуживания. Кроме того, используется аппарат теории марковских и полумарковских процессов, теории восстановления, теории управляемых и регенерирующих марковских процессов, а также широко применяются различные методы аппроксимации, в частности: декомпозиция сетей, метод анализа равновесного состояния, асимптотический анализ сетей очередей большой размерности.
Научная новизна работы заключается в обосновании и разработке единой методологической базы и комплекса новых математических моделей и методов для исследования, оценки эффективности и практического выбора механизмов управления потоками данных и ресурсами
(УПДР) в сетях ЭВМ и многопроцессорных вычислительных системах (МВС) при их построении и развитии с учетом конкретных особенностей их структур, оборудования, систем коммуникаций, протоколов, потоков данных.
Практическая ценность работы. Результаты диссертационной работы позволяют научно обоснованно решать такие важные в практике разработки, создания и развития сетей ЭВМ и МВС задачи, как оценка проектных решений при выборе архитектуры и конфигурации МВС и сети, при выборе технических и управляющих программных средств, уточнении и настройке параметров сети или МВС; оценка эффективности средств распределенной обработки и хранения данных - иерархической памяти в локальных сетях и МВС, спецпроцессоров в МВС, сетевой архитектуры «клиент-сервер*-; сравнительный анализ и выбор механизмов УПДР в МВС, в частности - стратегий доступа к критическим ресурсам с учетом конкретных особенностей реальных МВС; оценка эффективности и выбор параметров линейных, сквозных и интерсетевых протоколов с учетом особенностей потоков данных и степени загрузки оборудования сети, и др.
Достоверность научных положений, выводов и практических рекомендаций подтверждена корректным обоснованием и анализом математических моделей рассматриваемых процессов и структур, подтверждающими их результатами имитационных экспериментов, а также результатами практического использования предложенных и исследованных в дисертации методов, моделей и средств.
Реализация и внедрение результатов. Результаты диссертационной работы были использованы:
- при разработке системы программного обеспечения МОСТ, предназначенной для построения неоднородных сетей из однородных сетей
(или отдельных ЭВМ) произвольной топологии;
при создании ВСКП АН Молдовы;
при создании информационно-вычислительных сетей угледобывающего концерна «ХДБ Соколов» (Чешская республика), Кошицкого Политехнического института (Словацкая республика), в Мосприватизации (г. Москва) и Государственной Думе РФ.
Практическое использование результатов диссертационной работы подтверждено соответствующими материалами о внедрении.
Результаты диссертации, опубликованные в монографиях и статьях, используются в учебном процессе в Московском физико-техническом институте (МФТИ) и Московском Государственном Университете путей сообщения (МГУПС).
Апробация работы. Основные положения и результаты работы докладывались на следующих совещаниях, семинарах и конференциях:
10-й Международный конгресс IFAC (Мюнхен, ФРГ, 1987 г.);
Международная конференция по локальным и городским сетям связи «LAN & MAN» (Киото, Япония, 1994 г. ) ;
6-я, 10-я, 11-я и 13-я Всесоюз. школа-семинар по вычислительным сетям (1981, 1985, 1986, 1988 гг.);
Всесоюз. совещание по проблемам управления (Ереван, 1983 г.);
2-е Всесоюз. совещание «Автоматизация проектирования и конструирования» (1983 г.).
4-я Всесоюз. шк.-сем. «Распараллеливание обработки информации» (1983 г.).
2-е Всесоюз.совещ. «Высокопроизводительные вычислительные системы» (Батуми, 1984 г.).
4-я Всесоюз. конференция «Вычислительные сети коммутации пакетов» (Рига, 1985 г. ) ;
- Всесоюз. семинар по методам и средствам применения ЭВМ в на
родном хозяйстве (Москва, 1985 г. ) ;
- 6-я Всесоюз.шк. «Многопроцессорные вычислительные системы*
(Звенигород, 1985 г.).
Публикации. По теме диссертации опубликовано 37 печатных работ, в том числе следующие 3 монографии:
Богуславский Л. Б. Управление потоками данных в сетях ЭВМ. М. . Энергоатомиздат, 1984. 168 с.
Богуславский Л.Б., Дрожжинов В.И., Основы построения вычислительных сетей для автоматизированных систем. М. : Энергоатомиздат, 1990. 256 с.
Богуславский Л.Б., Ляхов А.И.. Методы оценки производительности многопроцессорных систем. М.: Наука, 1992. 213 с.
Структура и объем работы. Диссертация состоит из введения, семи глав, заключения, списка литературы и приложения. Общий объем основной части работы составляет 252 страницы машинописного текста, 71 рисунок и 13 таблиц. Список литературы содержит 175 работ. Приложение, посвященное практической реализации результатов диссертации, занимает 22 страницы.
Содержание работы. В вводной гл. 1 выявляются общие принципы и цели УПДР в современных сетях ЭВМ и МВС: динамическое согласование интенсивности поступления потока данных в сеть или МВС и скорости его вывода, а также скоростей работы взаимодействующих абонентов; ограничение общего числа пакетов в сети связи и числа обрабатываемых процессов; равномерное распределение потоков данных с учетом всех ресурсов; распределение функций обработки и хранения информации; минимизация задержки пакетов (сообщений) и времени реакции системы и максимизирование пропускной способности. Определяется
основной математический аппарат моделирования, позволяющий наиболее адекватно отразить выявленные общие черты механизмов УПДР и оценить их эффективность. Показаны особенности реализации общих принципов организации, задач и функций механизмов УПДР в современных МВС, локальных и глобальных сетях ЭВМ. Основные результаты гл. 1 опубликованы в [36-45].
Главы 2-4 посвящены моделированию УПДР в МВС, основные результаты которого опубликованы в [42,46-57]. В гл.2 анализируются методы УПДР, связанные с применением иерархической памяти и спецпроцессоров и таким образом реализующие принцип распределения функций обработки и хранения данных среди множества ресурсов системы; строятся непрерывные и дискретные модели МВС, учитывающие указанные особенности, и разрабатываются точные, приближенные и асимптотические методы их решения.
В гл. 3 предлагаются и анализируются алгоритмы с обратной связью для доступа к распределенной общей памяти в МВС с общей шиной; строятся приближенные модели, позволяющие оценить и сравнить влияние вида алгоритма на различные показатели производительности МВС.
В гл.4 рассматриваются стратегии доступа к критическим ресурсам, применяемым для синхронизации параллельных процессов в МВС; на базе асимптотического анализа определяются почти оптимальные стратегии.
В гл. 5 рассматриваются методы управления доступом к общей передающей среде в локальной сети и их модели. Строится модель локальной сети архитектуры «клиент-сервер» и разрабатываются точные методы ее анализа, позволяющие оценивать основные показатели производительности. Основные результаты гл. б опубликованы в [38,53, 58-63].
Наконец, главы 6 и 7 посвящены моделированию УПДР в глобальных сетях. В гл.6 рассматриваются процедуры управления каналами связи (линейные протоколы) и их марковские модели, на основе анализа которых разрабатываются формулы оценки основных критериев качества линейных протоколов и решаются задачи выбора их параметров. Основные результаты гл.6 опубликованы в [37,64-68].
Методы управления сквозной транспортировкой данных в логических соединениях <отправитель-адресат> (сквозные протоколы) и межсетевых соединениях (интерсетевые протоколы) рассматриваются в гл. 7. Предлагаются принципиально новые схемы ограничения нагрузки и разрабатывается метод определения их параметров. Систематизируются существующие аналитические модели механизмов сквозного управления и проводится их имитационное моделирование. Решаются задачи оценки производительности, возникающие при создании шлюзов. Основные результаты гл.7 опубликованы в [37,38,59,64-67,69-74].
В заключении даются основные результаты диссертационной работы.
Приложение к работе посвящено практической реализации результатов диссертации и содержит расчет производительности иерархической информационно-вычислительной сети, реализуемой в Государственной Думе РФ.
