Содержание к диссертации
Введение
ГЛАВА I. Состояние проблемы и обзор литературы . 8
I. Вычислительные сети и их характеристики . 8
І.І. Логическая структура вычислительной сети. Уровни программного обеспечения. Протоколы 12
2. Методы и средства исследования протоколов 15
2.1. Цель исследования 15
2.2. Методы формального описания и логического анализа протоколов 17
2.3. Оценка эффективности функционирования протоколов передачи данных 21
ГЛАВА 2. Стрэдтурно-параметрическая имитационная модель протоколов межмашинной связи . 50
I. Постановка задачи 30
2. Концептуальная модель ПМС 32
2.1. Общая характеристика ПМС . 32
2.2. Балансный класс процедур ПМС 34
2.3. Концептуальная схема процедур ПМС . 39
3. Математическое описание СПИ модели . 45
3.1. Агрегативное представление системы межмашинной связи . 47
3.2. Описание агрегативной модели . 50
4. Принципы построения программного обеспечения СПИ модели 66
ГЛАВА З. Моделирование процесса швдионирования ПМС 72
І. Постановка задачи 72
I.L, Модель системы . 74
2. Алгоритм вычисления пропускной способности ПМС 76
2.1» Схема алгоритма . 76
2.2., Оценка времени подтверждения 78
2.3« Анализ механизма "окна" 82
2.4,, Анализ и вычисление виртуального времени передачи кадра (насыщенный вариант трафика) 86
2.5, Вычисление статистических характеристик реального потока 95
3. Алгоритм среднего времени передачи сообщений 99
3.1. Схема алгоритма 101
3.2. Анализ и вычисление виртуального времени передачи кадра (ненасыщенный вариант трафика) 106
ГЛАВА 4 Численные эксперименты и исследование характеристик функционирования балансного класса процедур ПМС
I. Насыщенный вариант трафика 114
2. Ненасыщенный вариант трафика 125
3. Оценка адекватности, эффективности моделей и точности результатов моделирования . 133
4. Выводы 135
Заключение 137
Список литературы
- Логическая структура вычислительной сети. Уровни программного обеспечения. Протоколы
- Концептуальная модель ПМС
- Алгоритм вычисления пропускной способности ПМС
- Ненасыщенный вариант трафика
Введение к работе
Объем издержек, связанный с созданием и сопровождением программных средств, вызывает необходимость научного обоснования управленческих решений относительно разработок программного обеспечения. Доводы в пользу того или иного программного обеспечения оказываются более убедительными, если они подкреплены экспериментами, демонстрирующими его преимущество. Поэтому в процессе разработки технического задания на программное обеспечение в течение ряда лет используется моделирование [69], предназначенное для развития количественного подхода и повышения точности при определении требований к рабочим характеристикам программного обеспечения. При этом очень важно какие методы и средства применяются для оценки параметров системы.
Чтобы получить информацию, необходимую для определения требований к системе обработки данных (например, пропускную способность, задержку и т.п.),обычно приходится использовать функциональное (т.е. управляемое событиями) моделирование аппаратных и программных средств системы, алгоритмов управления и модель связи с внешней средой [63]. И прежде чем сделать выводы относительно свойств программных средств, следует понимать характер и "природу" задачи, которая реализуется программными средствами [ИЗ-].
Таким образом, установлению свойств программных средств, определяющих их эффективность и надежность, способствует моделирование процессов, лежащих в основе той или иной функции, выполняемой программным обеспечением.
Все сказанное в полной мере относится к программному обеспечению вычислительных сетей, которое является специальным и - 5 -относительно новым видом программного обеспечения, что в свою очередь предъявляет свои требования при его исследовании и разработке .
В классическом подходе программное обеспечение вычислительной се:?и организуется по слоистой (многоуровневой) архитектуре [45, 96]. Разработка каждого уровня базируется на множестве процедур, определяемых протоколами [14] данного уровня. Следовательно,, программное обеспечение уровня выполняет задачи и функции, в основе которых лежат процессы определенного протокола. Отсюда становится очевидным необходимость моделирования процессов функционирования протоколов на этапе логического проектирования соответствующего программного обеспечения [19, 91].
Протоколам связи вычислительных сетей, как новой концепции в области обработки данных, присущ ряд особенностей: протоколы соединяют две традиционно различные технологии - обработку данных и технику связи, и естественно ожидать от такого сочетания двух сложившихся технологий всякого рода "загадок" ; протоколы функционируют в таких условиях, в которых последовательность и время наступления событий заранее не известны и в процессе передачи возможны ошибки; - в протоколах выполняются параллельные операции приема и передачи сообщений и их элементы имеют многопараметрический ха рактер и т.д.
Все это делает протоколы, как предмет исследования, трудным и интересным и для их исследования требуется поиск новых подходов и методологий, отличных от традиционных.
Объектом исследования в данной диссертационной работе яв- ляются протоколы межмашинной связи (ПМС), предназначенные для обеспечения надежной и эффективной передачи данных между двумя удаленными ЭВМ, соединенными физическим каналом связи.
Цель работы состоит в развитии подходов функционального моделирования ПМС, в разработке и исследовании комплекса моделей, которые позволили бы понять характер функционирования ПМС, их поведение в различных условиях. Кроме того, следовало выявить те параметры и механизмы, которые определяют производительность ПМС и получить эффективным способом количественные оценки характеристик протокола. При этом существенным требованием является то, что модели должны позволить исследовать ПМС в условиях как можно более близких к реальным.
Решению перечисленных задач и посвящена диссертационная работа. Она состоит из введения, четырех глав, заключения и списка литературы.
В первой главе кратко рассматриваются концепции вычислительных сетей и протоколов, их структура и основные характеристики. Обсуждаются проблемы исследования протоколов передачи данных, анализируются методы и средства моделирования протоколов. Проводится обзор литературы, посвященной исследованию протоколов. Отмечаются задачи, которые остались нерешенными в области исследования и разработки протоколов.
Вторая глава посвящена созданию структурно-параметрической имитационной модели ПМС. Рассматриваются три уровня описания модели - концептуальное, математическое и программное.
В третьей главе предложен гибридный метод оценки процесса функционирования ШЛО. Описаны алгоритмы вычисления двух основных показателей производительности ПМС - пропускной способности и среднего времени передачи сообщений. _ 7 -
Результаты численных экспериментов с моделями обсуждаются в четвертой главе. Там же анализируется поведение балансного класса процедур ПМС [62J . Указываются те параметры и механизмы, которые влияют на производительность протокола. Здесь же производятся оценки адекватности и эффективности моделей, точности результатов моделирования.
В заключении перечислены основные результаты, полученные в диссертационной работе.
Разработанные в диссертации научные положения, методы и алгоритмы послужили основой для создания методики и программных средств исследования вопросов функционирования коммутационной подсистемы локальной сети ЭВМ МГУ (тема: "Исследование и разработка принципов построения локальных сетей ЭВМ"; В госрегистрации 81048220, целевое задание 027.05.01 ГКНТ, Госплана, АН СССР) и используются в процессе разработки программного обеспечения связи. Основные практические результаты внедрены в НИИСЧЕТМАШ, ЦАМ АН МССР.
На зашиту выносятся следующие положения : структурно-параметрическая имитационная модель ПМС с тремя уровнями описания: концептуальным, математическим и программным; метод гибридного моделирования процесса функционирования ПМС; алгоритмы вычисления показателей производительности ПМС -пропускной способности и среднего времени передачи сообщений; результаты исследования характеристик функционирования балансного класса процедур ПМС при вероятностном распределении длин обслуживаемых сообщений и с учетом всех основных механизмов и параметров протокола.
Логическая структура вычислительной сети. Уровни программного обеспечения. Протоколы
Логическую структуру ВС можно представить [96] как множество взаимосвязанных объектов, каждый из которых ассоциируется с одним вычислительным ресурсом (ГВМ, СП, программа, процесс) и, взаимодействуя с другими объектами, обеспечивает выполнение определенных функций согласно требованиям пользователей и услугам, предлагаемым сетью. Взаимосвязанные объекты, функционирующие в разных географических точках сети, для координации своих действий и достижения синхронизации обмениваются сообщениями (команды, сигналы, данные). Такой обмен производится в соответствии с тщательно разработанными процедурами. Эти процедуры называются протоколами [14, 96]. Их основной особенностью является способность к работе в таких условиях, в -которых последовательность и время наступления событий заранее неизвестны, и в процессе передачи возможны ошибки.
Таким образом, функции протокола связаны с обменом сообщениями между объектами. Форматы и содержание этих сообщений, а также последовательность событий посылки и приема сообщений составляют синтаксис протокола, другими словами, синтаксис протокола описывает его логические характеристики. Правила или условия, при которых выполняются переходы между состояниями объектов, и осуществляемые при этом операции составляют семантику протокола. Иначе, семантика протокола определяет его процедурные характеристики. Используя эти понятия, протокол формально можно определить как совокупность логических и процедурных характеристик механизма связи между объектами [14].
Разнообразие требований и услуг в сети, с одной стороны, и общность функционирования различных объектов, с другой стороны, позволшот образовать иерархию уровней вычислительной сети. В этом случае каждый уровень, объединяя один или несколько объектов, выполняет одну из основных задач вычислительной сети (управление информационным каналом, управление сетью и т.д.) [45, 96]. В соответствии с функциональным назначением уровня и определяются протоколы данного уровня. Проблема определения границ между уровнями вычислительной сети и выбор числа уровней является достаточно сложной и поэтому в различных сетях она решается по-разному. Но несмотря на это в общем случае выделяют две группы уровней и, следовательно, протоколов [7,45,96J : протоколы, ориентированные на применение (верхние уровни) и протоколы, ориентированные на транспортировку данных в сети (нижние уровни).
Первая группа протоколов определяет процедуры, обеспечивающие сервис высоких уровней (виртуальный терминал, удаленный ввод заданий, удаленный доступ файлам, распределенная обработка и т.д.) [14, 96].
Протоколы второй группы определяют процедуры управления передачей данных в межмашинной и межпроцессной связи. Эти процедуры обеспечивают такие функции как: - обмен управляющей информацией для синхронизации действий объектов; - обмен пользовательскими данными; - управление потоком данных; - определение маршрута следования данных; - фрагментацию данных, исходящих от источника, и сборку данных на месте назначения, если в процессе обмена разрешается передавать блоки данных ограниченного размера; - контроль и обнаружение ошибок и восстановительные действия при ошибке передачи; - управление таймаутом, являющимся основной мерой контроля передачи во времени; - временная буферизация данных для дальнейшей передачи и т.д.
Выполнение перечисленных выше, а также других функций может повторяться на нескольких уровнях. Целесообразность реализации той или иной функции, их дублирование на разных уровнях решаются в конкретных случаях исходя из структуры сети и предъявляемых к ней требований.
Концептуальная модель ПМС
Концептуальная модель разрабатывается с целью понимания спецификации протокола и присущих ему причинно-следственных связей, которые существенны в рамках данного исследования. Она служит основой разработки математической модели протокола. Следует отметить, что процесс создания концептуальных моделей носит эвристический характер, то есть разработчик в основном руководствуется лишь собственной интуицией, опирающейся на понимание процесса функционирования системы.
Общая характеристика ПМС
Сообщения между узлами сети передаются в виде пакетов или блоков, представляющих последовательность битов, которые, в свою очередь, образуют символы. Но передаваемый блок по своему содержанию и назначению нечто большее, чем произвольный набор символов. Принимающая сторона должна определить начало и конец нового сообщения, а передача должна быть синхронизирована по битам и символам, чтобы дать возможность принимающей стороне декодировать поступающие сообщения. Эти и другие функции по организации обмена данными между конечными точками одной линии связи обеспечиваются протоколами межмашинной связи или процедурами управления каналом межмашинной связи [14, 43].
Таким образом, управление каналом межмашинной связи основывается на правилах и процедурах, которые позволяют установить связь между взаимодействующими ЭВМ, обеспечить обмен информацией, осуществить синхронизацию в процессе передачи сообщений, оповещать об окончании сеанса связи, когда передача сообщений закончена. Управление накладывает ограничения на формат сообщений и скорости передачи. Оно включает средство обнаружения ошибок, процедуры квитирования, которые позволяют указать, что сообщения приняты верно или неверно, а также процедуры, определяющие действия, необходимые при обнаружении ошибок при передаче. В качестве расширения последних процедур, необходимо определить, как обнаружить различного рода случайные отклонения от нормального процесса передачи и какие действия в этом случае следует предпринимать.
Взаимодействие обменивающихся сторон происходит по трем фазам [43]. I. Фаза инициирования сеанса связи, при которой можно произвести идентификацию станции-партнера, затребовать разрешение посылать данные или передавать уведомление о том, что начинает ся передача сообщений. 2. Фаза передачи сообщений. 3. Фаза завершения сеанса связи. В этой фазе разрывается логическое соединение и система возвращается в первоначальное состояние.
Передача сообщений может осуществляться по сквозному каналу (соединение "точка-точка"), когда от одной станции к другой сообщения передаются на основе полудуплексной или полнодуплексной передачи; передача сообщений может также производиться по каналу, к которому подключаются много станций (многоточечное соединение).
В иерархии протоколов вычислительных сетей уровень управления каналом межмашинной связи представляет важную часть. За последнее десятилетие многими организациями разработаны протоколы этого уровня: НЫХ (150 - международная организация по стандартизации) [623 , ЬЬСПР (фирма ЬЕС) [l09], BSC,Si)LC (фирма IBM) [ЗЗ] и т.д. Среди них наиболее развитым является протокол HbLC , который, к тому же предложен в качестве стандарта канального уровня Рекомендации Х.25 МККТТ [45, 60J .
Далее рассматривается определенное множество процедур управления межмашинной связью, а именно: балансный класс процедур протокола H3 LC .
Алгоритм вычисления пропускной способности ПМС
Рассматривается насыщенный вариант трафика данных - станции все время имеют информацию для передачи. Станции Л и В из-за симметрии имеют одинаковые статистические характеристики функционирования. Поэтому все необходимые характеристики вычисляются для одного направления - от -А к
Рассмотрим последовательность случайных чисел №Л , при s Здесь и в дальнейшем ВВП - вирутальное время передачи кадра. нимающих значения t »»& с вероятностями г ,г ,. .,? где N число различных длин. Последовательность (] задает длины кадров, которые последовательно передаются по каналу. На этой последовательности выполняется итерационный алгоритм. Обозначим: через і - номер итерации и одновременно номер кадра, для которого в данный момент проводятся вычисления; через Т/і -ВВП кадра I . Пусть TV , Ту%\. %сю - виртуальные времена передачи кадров с длинами , f. . имеют математиче-ское ожидание ty ,tv ,..., у . Тогда пропускная способность протокола определяется по формуле:
Значения tv ytv i"- tv являются выходными пара метрами алгоритма. Они вычисляются следующим образом.
Для данного кадра /- вычисляется математическое ожидание 2-v виртуального времени передачи 7yL для той конфигурации, которая определяется упорядоченным набором длин кадров, следующих до и после кадра с номером і . В предположении что исходы, отвечающие итерациям алгоритма независимы и равновероятны, оценка величин tv проводится усреднением величин tvu по множеству исходов для каждой длины кадра в отдельности: іТ тшЖ K=i,a,... #, (8-2 где tfi-Ш - число итерации алгоритма, для которых длина I -ого кадра равна с- ; - множество номеров кадров, у которых длина равна В . Кадр с номером / на каждой итерации рассматривается вместе со своим окружением: /1-Я кадрами, передаваемыми по каналу связи до и -ого кадра и t\ Z кадрами, следующими за і -ым кадром. По первой последовательности определяются ситуации, когда происходят задержки в процессе передачи кадров из-за достижения максимального допустимого числа неподтвержденных кадров. По последовательности M-Z кадров, следующих за данным кадром определяется то время, по истечении которого станция-получатель обнаруживает ошибку последовательной нумерации кадров, если кадр с номером I был передан с ошибкой.
При фиксированном I зафиксированы кадры из его окружения. Для данного фрагмента из Ш-#)+1+(М-Й)я2.№-3 кадров вычисляется математическое ожидание ВВП кадра і (см. 2.4) и вспомогательные характеристики (см. 2.5), позволяющие оценить реальный поток кадров по каналу и учесть взаимодействие потоков данных, протекающих в противоположных направлениях по дуплексному каналу связи (см. 2.2). Затем выполняется переход к следующей итерации алгоритма - фрагмент из Ш-Ъ сдвигается по последовательности { } на один кадр влево.
В этом параграфе получены аналитические выражения для вычисления средних значений величин времен подтверждений о приеме и неприеме I -кадров.
Подтверждение о приеме кадра. Определим случайную величину Таас , которая равна времени, необходимому для прибытия подтверждения об успешном приеме данного кадра. Такое подтверждение может быть получено с информационным или супервизорным кадром. Математическое ожидание случайной величины ТІ,си -Іоли-МЕТлич вычисляется при следующих предположениях (рис. 3.3): а) отсчет времени начинается с окончанием передачи кадра станцией А ; б) момент времени, когда прибывает кадр / на станцию
В случаен и не зависит от состояния передачи от А к Ь ; в) если в момент приема рассматриваемого кадра станция В передавала кадр, то начало передачи подтверждения задерживает ся до освобождения канала в направлении В- А ;
г) если в передаче / -кадров от В к А не произошло остановки , то подтверждение посылается в следующем J -кад ре, в противном случае посылка подтверждения осуществляется с помощью -кадра;
д) если /-кадр, который носит подтверждение на рассмат риваемый кадр, ошибочен, то прибытие подтверждения задержива ется и оно приходит со следующим /-кадров или 5 -кадром.
Ненасыщенный вариант трафика
В данном пункте рассматривается более реальная ситуация межмашинной связи, когда обслуживаются сообщения, поступающие с некоторой интенсивностью при условии конечного времени обслуживания каждого сообщения 1.41] : где Л - интенсивность поступления сообщений; tf - среднее время обслуживания сообщения. Наиболее важными характеристиками в данном случае являются среднее время передачи сообщений и среднее время занятости буферов. Как уже определялось ранее, среднее время передачи - это время, вычисляемое с момента поступления сообщения на передаю щую станцию до момента безошибочного приема его принимающей станцией. Это означает, что среднее время передачи включает и время ожидания в очереди на обслуживание.
Время занятости буферов определяется как время с момента поступления сообщения на передающую станцию и до получения подтверждения от соседней станции о приеме этого сообщения. Это время состоит из времени передачи сообщений и времени подтверждения.
Обе временные характеристики рассматриваются как функции от длины информационного поля I -кадра.
На рис. 4.II-4.I6 представлены зависимости среднего времени передачи сообщений от их длин, когда протокол обслуживает сообщения постоянной длины при условии, что трафик симметричный, т.е. полезная нагрузка в обоих направлениях одинакова. Полезная нагрузка (обозначим ее через U ) соответствует той части общей пропускной способности канала, которая используется для безошибочной передачи информационных битов (или байта): где б - длина информационного поля I -кадра, V - скорость передачи по каналу.
Кривые, показанные на рис. 4.II, построены по результатам моделирования, при следующих параметрах; скорость передачи -9600 бит/сек. (непрерывные линии) с вероятностью ошибки бита Л л 10 и 10 , а также скорость 48000 бит/сек. (прерывистая ли-ния) с вероятностью ошибки бита 10 ; полезная нагрузка постоянная и равна 0,6; время обработки - 0,05 сек.; модуль нумерации и максимальный размер "окна" равен 8. Сообщения поступают по пу-ассоновскому закону. Как видно из рис. 4.II, все три кривые имеют явно выраженный минимум. При этом для малых значений длин ин формационного поля наблюдается резкое возрастание среднего времени передачи. Это объясняется относительным увеличением объема накладных затрат. Если сравнить кривые, указанное возрастание при скорости передачи 48000 бит/сек. происходит для сообщений длиной « 128, а при 9600 бит/сек. - для сообщений с 32. Причиной такого отличия является механизм "окна", который сильно проявляет себя при скорости 4800 бит/сек.
Относительно большое время передачи при вероятности ошибки бита 10 по сравнению с ошибкой 10 при скорости передачи 9600 бит/сек. вызвано увеличением вероятности ошибки блока и, следовательно, задержкой передачи из-за повторных передач.
С увеличением длины информационного поля объем накладных затрат относительно уменьшается, но происходит возрастаїше среднего времени передачи за счет друтих эффектов: а) растет вероятность ошибки блока сообщений, б) больше становится время восстановительных действий, в) время передачи J -кадра, даже если нет ошибки в процес се передачи, возрастает пропорционально увеличению длины инфор мационного поля.
Если сопоставить результаты моделирования, полученные при оценке максимальной пропускной способности (см. рис. 4.1), и среднего времени передачи сообщения (см. рис. 4.II), то можно заметить, что малые значения среднего времени достигаются при существенно более коротких сообщениях, чем большие значения ШС (при одних и тех же условиях).
