Введение к работе
Актуальность темы диссертации.
Современный уровень научных исследований предполагает широкое использование научных баз данных, автоматизацию процессов передачи, обработки и хранения научной информации. Эти проблемы решаются с помощью локальных и глобальных вычислительных сетей (ВС).
Компьютерные сети представляют собой сложные технические системы, эффективное функционирование которых в значительной степени зависит от многих стуктурпых и нагрузочных параметров, от используемых на разных уровнях иерархии протоколов доступа к общим ресурсам. Анализ ВС с целью определешія и оптимизации вероятностно-временных характеристик, таких как пропускная способность, время и вероятность доставки сообщений, является актуальной проблемой, которую приходится решать на етапах разработки и эксплуатации ВС. Одним из наиболее распространенных методов анализа ВС является математическое моделирование, в частности, методами теории массового обслуживания. Однако, классические системы массового обслуживания с ожиданием и потерями не могут служить адекватными моделями сложных процессов передачи информации в компьютерных сетях, имеющих многоуровневую иерархическую структуру с различными протоколами доступа! Это послужило стимулом к рассмотрению новых классов систем массового обслуживания и, соответственно, к разработке математігческих методов расчета их вероятностно-временных характеристик. Одним из таких классов математических моделей, активно исследуемых в последнее время, является класс систем массового обслуживания с повторными вызовами. Особенностью данных систем обслуживания является то, что заявки поступившие в систему и обнаружившие прибор занятым не теряются (как в системах с потерями) и ае становятся в очередь-(как в системах с ожиданием), а через случайные промежутки времени неоднократно поступают на прибор пока не застанут его свободным. Традиционные системы массового обслуживания с повторными вызовами, рассмотренные впервые в 50-60 годах и активно исследуемые в послед-тие годы, возникли как модели узлов коммутаций телефонных линий. Но, *ак оказалось, они могут служить адекватными математическими моделями чоноканалышх сетей передачи данных с протоколами случайного доступа.
Моноканальная сеть передачи данных шинной структуры представляет :обой совокупность источников (потребителей) информации, объединенных еди-іствешшм общим каналом связи. Источниками (потребителями) информации
являются абонентские станции (АС), подключенные через адаптеры сети к моноканалу и осуществляющие приём, храпение и передачу информации в виде Пакетов данных. В качестве АС могут быть персональные компьютеры, средние и большие ЭВМ, любое другое микропроцессорное оборудование. Каналом связи физически может быть кабель (телефонный, коаксиальный, оптоволоконный) или радиовфир в случае радио или спутниковой сети связи. Количество АС в сети всегда конечно, однако, иногда их число может быть достаточно большим или неизвестным, например, когда станции работают па одной час* тоте в радиоэфире. В втих случаях принято полагать, что число станций в сети бесконечно, и исходящий от них суммарный поток нагрузки характеризуется фиксированной интенсивностью. Моменты появления пакетов у абонентских станций, а также длительности передачи пакетов в канал являются случайными. Поатому не исключены ситуации, когда несколько АС одновременно претендуют на использование единственного канала связи. Это приводит к разрушению передаваемых пакетов. Проблема состоит в разделении между станциями единственного ресурса — канала связи. Алгоритм распределения канального ресурса между АС сети принято называть протоколом множественного доступа. Одна из основных задач, которую приходится решать разработчикам сети, состоит в выборе известных или разработке новых протоколов доступа, которые обеспечивали бы заданные основные вероятностно-временные характеристики (ВВХ) сети, такие как производительность, пропускная способность, средняя задержка пакетов, вероятность их доставки и др. Решение данной технической задачи предполагает проведение расчетов ВВХ существующих или разрабатываемых протоколов, что, в свою очередь, связано с проблемами построения их математических моделей и разработкой математических методов анализа втих моделей. Согласно классификации, приведенной в ', наиболее известны две группы протоколов множественного доступа: детерминированные и случайные. В соответствии с детерминированными протоколами, каждой АС выделяется гарантированная доля общей пропускной способности канала сети. Это достигается различными алгоритмами планирования передач, например, путем выделения абонентским станциям кванта времени со некоторому расписанию или путем передачи маркера (исключительного права) на занятие канала. Во всех втих случаях детерминированные протоколы исключают одновременное использование канала несколькими станциями. Наиболее известными протоко-
'Выи&рия Г.П., Ефимушюю В.А. Методы ыииина локмьяш инфориыщовио-вычислитель-іш сетей Ц Итоги науки и теинки. Сер. Связь. Т.2: Сети связи. М.: ВИНИТИ, 1988. - С. 60 - 109.
лами такого типа являются маркерний доступ к шине (стандарт IEEE 892.4), и маркерный доступ к кольцу (стандарт IEEE 802.5). Математические задачи, возникающие при моделировании детерминированных протоколов, как правило, связаны с анализом систем массового обслуживания с дисциплинами разделения времени и разделения процессора. Методы анализа данных систем обслуживания достаточно полно разработаны.
Иначе обстоит дело с разработкой математических методов исследования систем массового обслуживания, являющихся моделями протоколов случайного доступа. Существуют два типа случайных протоколов: синхронные и асинхронные. В нервом случае временная ось разбивается на равные промежутки времени - такты. Все станции сети синхронизированы и пачинают передачу пакетов только в начале тактов. Длительность передачи пакетов и другие временные параметры сети выбираются кратными длительности такта. Модели синхронных протоколов представляются, как правило, п виде дискретных цепей Маркова, рассматриваемых в начальные моменты тактов. При атом, матрица переходов цепи рассчитывается с учетом событий, происходящих в сети в течение ближайшего такта времени.
В случае асинхронных протоколов события в сети происходят в произвольные моменты времени. Удобным аппаратом для описания и исследования подобных моделей является математический аппарат теории массового обслуживания, в частности, методы исследования марковских процессов с непрерывной компонентой. При построении "непрерывных" моделей, необходимо учитывать следующую особенность случайных протоколов. В отличие от детерминированных, где в распределении канального ресурса АС играют пассивную роль, в сетях со случайными протоколами каждая станция независимо от остальных, сама инициирует начало передачи своего пакета. При втом не исключается возможность наложепия передач от нескольких станций, одновременно передающих пакеты по единственному каналу. Очевидно, что в втом случае пакеты поступят потребителям в искаженной форме и поэтому они должны быть переданы повторно. Каждый пакет передается повторно несколько раз до тех пор, пока не произойдет его успешная передача. Это приводит к случайному характеру задержек пакетов в сети, произвести точную оценку которых можно только с помощью моделей, учитывающих повторные передачи искаженных пакетов. Адекватными моделями асинхронных протоколов, учитывающих ату особенность являются системы массового обслуживания с повторными вызовами.
Данная диссертационная работа посвящена проблемам разработки математических методов исследования нетрадиционных систем массового обслужи-
палия с повторными вызовами, являющихся адекватными математическими моделями мопоканалыгых сетей передачи данных с асинхронными протоколами случайного множественного доступа.
Связь работы с крупными паучдьшя программами, темами.
В течение 1989-1993 годов работа выполнялась в рамках научно-исследовательской программы Белоруссии "Информатика". Подпрограмма: 06. "Локальные и региональные шформационпо-вычислительные сети". Пункт программы: 06.02.01 "Разработка математических методов и программного обеспечения для определения и анализа вероятностно-ипформационво-временпых характеристик вычислительных сетей".
Результаты работы внедрены в части ОКР-365, проводимой ОКБ "Квант" НПО "Гранат" (г.Минск) в 1990 году по теме: "Моделирование ЛВС па основе случайного множественного доступа".
Цель и задачи исследования.
Основная цель данной работы состоит в создании комплекса математических моделей систем массового обслуживания с повторными вызовами, разработке и совершепствовашш методов и алгоритмов расчета их ВВХ с целью дальнейшего практического применения моделей и результатов расчета для прогнозирования и оптимизации характеристик создаваемых и существующих сетей передачи данных с асинхронными протоколами случайного множественного доступа.
Сформулированная цель достигается решением следующих задач:
определение ВВХ систем с двухдташшм обслуживанием и сдвоенными соединениями ва первом этапе и иа интервале уязвимости заявок;
определение ВВХ систем обслуживания с уходом заявок при сдвоенных соединениях;
определение ВВХ систем обслуживания с непастойчивыми, 1- и р-настой-чивыми заявками;
разработка комплекса программных средств, реализующих алгоритмы расчета ВВХ перечисленных классов систем обслуживания;
проведение численных экспериментов расчета ВВХ моделей и проведение исследований по численной оптимизации и сравнению результатов расчета характеристик моделей с измерениями в реальїшї мялз;
Научная новизна полученных результатов Все результаты, изложенные d диссертации получены впервые. В отличие от исследуемых ранее моделей протоколов случайного доступа, рассматриваемых, как правило, в виде систем обслуживания с потерями или с ожиданием и не учитывающих повторную передачу искаженных пакетов, в диссертации разнит иной подход: исследуются системы обслуживания с повторными вызовами, учитывающие ату особенность. Для втих целей введены повые классы систем с повторными вызовами и дисциплинами обслуживания, учитывающих особенности случайных протоколов. В частности, введены новые классы систем с повторггыми вызовами, моделирующих 1- и р-настойчивие протоколы CSMA/CD, обобщепы ранее известные результаты для непастойчивого протокола CSMA/CD на случай произвольного вида распределений вероятностных параметров моделей, решены задачи расчета стационарного распределения СМО с повторными вызовами и сдвоенными соединениями, р&яее исследуемые только асимптотическими методами.
Практическая значимость полученных реэультатоз.
Результаты диссертационной работы имеют как теоретическое так и прикладное значение. Теоретическое значение состоит в дальнейшем развитии аналитических методов теории массового обслуживания. В частности:
* Получила дальнейшее развитие методика нахождения производящих фу
нкций стационарного распределения однолинейных систем с повторными
вызовами, состоящая в сведении исходпых дифференциально-разностных и
иптегро-дифферешщальных уравнений к
однородным дифференциальным уравнениям второго порядка класса Фукса с регулярными особыми точками, решения которых находятся в виде специальных функций или степенных рядов;
интегральным уравнениям типа Вольтерра второго рода, приближенное решение которых находится численными методами;
линейным однородным дифференциальным уравнениям в частпых производных.
Развита конструктивная методика нахождения достаточных условий су
ществования стационарного распределения цепи Маркова с ленточным
графом переходов.
Получили дальнейшее развитие матричные методы расчета стационарного
распределения марковских и немарковских систем обслуживания с коне
чным числом источников нагрузки, состоящие в индуктивных способах
получения сложных рекуррентных матричных соотношений.
Прикладное значение результатов диссертации состоит в использовании их при математической моделировании процессов передачи инфориащш в сетях с протоколами случайного множественного доступа. В частности:
Полученные результаты позволяют находить предельные значения нагрузки (пропускной способности), средней задержки передачи пакетов, вероятности состояний канала связи, скорости передачи битов сообщений, вероятности конфликтных ситуаций и многие другие характеристики моноканалышх сетей передачи данных с ненастойчивым, 1- и р- настойчивым протоколом случайного доступа с контролен несущей и обнаружением конфликтов (CSMA/CD).
Результаты могут быть использованы для определения оптимальных значений параметров механизма повторной передачи искаженных пакетов при различных критериях качества, таких как минимизация времени доставки пакетов, максимизация коэффициента использования канала (производительности) или других сметанні критериях.
Полученные результаты позволяют проводить комплексные исследования зависимости характеристик создаваемых и существующих сетей от изменения значений различных нагрузочных и системных параметров, таких как дыша пакетов в байтах, количество станций в сети, время распространения сигнала в передающей среде и др.
Разработанные модели протоколов могут быть использованы в качестве подмоделей при математическом моделировашш процессов передачи информации на более высоких уровнях (транспортном, прикладном, сетевом) сетевой иерархии.
Все полученные результаты реализованы на языке Turbo Pascal для персональных компьютеров типа PC
AT и могут служить готовыми блоками при создании комплексной программы анализа случайных протоколов.
Экономическая значимость полученных результатов.
Комплекс программ, написанных па языке Turbo-Pascal для PC ЛТ и реализующих все теоретические результаты диссертации, представляет интерес для организаций, занимающихся проектированием, созданием, внедрением и эксплуатацией локальных, радио и спутниковых сетей на основе протоколов случайного множественного доступа. О помощью втих программ можно прогнозировать характеристики сетей, производить настройку параметров протоколов доступа, исследовать влияние на характеристики существующих сетей значений различных параметров (числа станций, длины кабеля, роста нагрузки и др.), использовать в качестве подмоделей при расчете характеристик протоколов более высокого уровня.
Основные положеная диссертации, выносимые на защиту. На защиту выносятся:
-
Методы теории массового обслуживания, позволяющие получить точные (в замкнутой форме или в виде алгоритмов) стационарные распределения для систем обслуживания с повторными вызовами, являющихся моделями протоколов случайного доступа, и ранее исследуемых приближенными пли асимптотическими методами. .
-
Результаты исследования пеяастойчивых протоколов CSMA/CD, представленных в виде классических систем обслуживания с повторными вызовами при некоторых дополнительных предположениях, вызванных спецификой протоколов, обобщающие многие результаты, полученные ранее, и представляющие собой наиболее полное исследование в атой области.
-
Модели широко используемых в локальных сетях типа ETHERNET 1-настойчивых протоколов CSMA/CD в виде систем обслуживания с 1-настойчивымн заявками, адекватность которых доказывается совпадением рассчитанных с помощью моделей характеристик с данными измерений в реальной сета.
-
Модели р-настойчивых протоколов CSMA/CD. Показано, что практически во всей области параметров сети р- настойчивый протокол имеет преимущество по сравнению с широко распространенным 1-вастойчнвым протоколом.
Личный вклад соискателя.
Все результаты, приведенные в диссертации, получены лично автором. Соавторам в двух совместных работах принадлежат предметные постановки задач.
Апробация результатов диссертации.
Результаты диссертации представлялись и докладывались на:
Конференции ученых социалистических стран "ЛОКСЕТЬ'вб/ЭО" (Рига, 1986,1990),
V Всесоюзной конференции "КОМПАКТ" (Рига, 1987),
Республиканском научно-техническом семинаре "Совершенствование методов исследования потоков событии и систем массового обслуживания" (Киев, 1989),
I, II Всесоюзных конференциях по информационным системам множественного доступа (Минск, 1989, 1991),
XIV, XV, XVII Всесоюзных школах-семинарах по вычислительным сетям (Минск, 1989, Ленинград, 1990, Алма-Ата, 1992),
Республиканской научно-технической школе-семинаре "Анализ и синтез систем массового обслуживания и сетей ЭВМ" (Одесса, 1990),
Всесоюзном научно-техническом совещании-семинаре "Микропроцессорные системы управления технологическими процессами в ГПС" (Одесса, 1990),
III, V Всесоюзном совещ&ниипо распределенным вычислительным системам и сетям (Винница, 1990, Калинкград, 1992),
Всесоюзной научно-технической конференции "МИКРОСИСТЕМА'Эг.'ЭЗ" (Калининград, 1992, Москва, 1993),
IV Международном семинаре по теории телетрафика и компьютерному моделированию (Москва, 1992),
II Конференции по информационным сетям и системам КИСС'93 (Санкт-Петербург, 1993),
Математической конференции "Проблемы прикладной математики и информатики" (Гомель, 1994),
в I- XII Белорусских зимних школах-семинарах по теории- массового обслуживания (Гродно, 1985, 1987-1989, 1991, Гомель, 1986, Витебск, 1990, Брест, 1992, Минск, 19ЭЗ-199Б, Гродно, 1996, Минск, 1997).
Опубликовадность результатов.
Основные используемые в диссертации методы и полученные результаты опубликованы в 46 научных работах. Из них 16 статей и сообщений в научных журналах, одна статья в сборішке научных работ н двадцать девять тезисов научных конференций.
Структура и объём диссертации.
Диссертация состоит из введения, семи глав, выводов и списка используемых источников.
Общий объём диссертации составляет 2БЗ страницы.
Общее количество иллюстраций - 77, занимающих 36 страниц.
Общее число используемых источников равно 218. Они занимают 22 страницы.
