Исследование компьютерных сетей связи с протоколами случайного множественного доступа | Вестн. Том. гос. ун-та. 2000. № 271.

Исследование компьютерных сетей связи с протоколами случайного множественного доступа

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

Investigation of computer communication network with random multiple access pronocol.pdf Качество функционирования компьютерных сетей связи определяется вероятностно-временными характеристиками, основными из которых являются: производительность сети, ев пропускная способность, вероятность потери сообщения, вероятность доставки сообщения с нулевым временем ожидания, вероятность простоя канала, среднее число пакетов, ожидающих передачи, среднее или гарантированное время доставки сообщения; для нестабильных сетей - гарантированное время их устойчивого функционирования. Естественно, более полно характеристики сети отражаются не средними значениями, а соответствующими распределениями вероятностей. Актуальность этих исследований отмечалась в работах [1-4], здесь же обсуждаются проблемы сложности этих исследований классическими методами теории случайных процессов. Нужно было искать нетрадиционный путь. Им оказался метод асимпто-Фиче'ского анализа м&рко'вюйруемых'сйсФем [5J. ' * ' Были рассмотрены следующие компьютерные сети с протоколами случайного множественного доступа: Алоха [6-9], с оповещением о конфликте [10-11], с контролем несущей и обнаружением конфликтов [12]. Исследованы три модификации протоколов доступа: статические [7,11], когда стратегия доступа не меняется с течением времени; динамические [8], если она определяется состояниями сети, и адаптивные [13]. В этом случае сеть имеет специальное устройство, называемое адаптером, который по состояниям только канала связи оценивает состояние всей сети и меняет значения параметров протокола доступа в зависимости от полученных оценок. Функционирование компьютерных сетей связи с протоколами случайного множественного доступа моделируется однолинейными системами массового обслуживания (СМО) [4,14,15]. На вход такой системы поступает примитивный [16] для сетей с конечным числом абонентских станций (АС) либо простейший поток заявок, обслуживание которых рекуррентное. Прибор может находиться в различных состояниях, моделируя различные состояния канала связи: фазу успешной передачи сообщения, состояние конфликта при одновременной передаче нескольких сообщений, период передачи сигнала оповещения (заглушки) и т.д. Эти модели отличаются от классических СМО тем, что в них выделен ещё один элемент, называемый источником повторных вызовов (ИПВ), который моделирует функционирование АС с задолженностью в режиме ожидания повторной попытки передачи сообщений, попавших в конфликт. При этом возможны две стратегии контроля состояния канала: дискретный и непрерывный [12]. Для исследования таких СМО разработан метод асимптотического анализа марковизируемых систем [5], реализуемый в асимптотических условиях: большой загрузки, когда загрузка канала ptS, где S - пропускная способность сети; большой задержки, когда интенсивность у повторного обращения заявки из ИПВ у->0; либо для числа N абонентских станций в сети N->оо. Методом имитационного моделирования определяется область применимости полученных асимптотических результатов. Исследования предлагаемых математических моделей показывают, что в сетях со статическими протоколами доступа при простейшем входящем потоке поступления заявок не существует стационарного режима [17,18]. Такие сети естественно называть нестабильными [19). В сетях с конечным числом АС (примитивный поток) может возникнуть явление бистабильности [9,20], которое характеризуется тем, что во множестве состояний сети определяются два состояния - точки стабилизации. В этом случае сеть функционирует следующим образом. Ее состояния флуктуируют то в окрестности одной точки стабилизации, то, после случайного перехода, попадают в окрестность другой точки, после чего вновь возвращаются к первой точке стабилизации и т.д. При этом вероятностно-временные характеристики сети в окрестности одной точки стабилизации достаточно приемлемы, а в другой могут ухудшаться во много раз и сеть функционирует крайне неудовлетворительно. Аналог приемлемой точки стабилизации определён и для нестабильных сетей, Показано, что в окрестности этой точки нестабильная сеть может оставаться достаточно долго, практически бесконечное время. Т.е. нестабильная сеть в этом случае функционирует как моностабильная [19]. Определена область соответствующих значений параметров таких сетей. Динамические протоколы, как правило, технически не реализуемы, так как в них требуется наличие информации в каждом узле о текущем состоянии всей сети, что практически невозможно осуществить для децентрализованных сетей связи. Объём обмена такой информацией между узлами может многократно перекрывать пропускную способность канала связи. При этом может оказаться существенной задержка передачи, что естественно искажает информацию о текущем состоянии сети. Тем не менее исследование таких протоколов оказывается полезным по двум причинам. Во-первых, эти протоколы целесообразны в сетях с выделенным центральным узлом, через который проходит вся информация о изменениях состояний сети. Во-вторых, они показывают потенциальную возможность адаптивных протоколов, в которых точная информация о состояниях сети заменяется некоторыми их оценками, реализованными по состояниям только канала связа Исследование сетей с адаптивными протоколами представляет наибольшую сложность в связи с увеличением размерности исследуемых систем и возникновением некоторых принципиальных проблем асимптотического анаг лиза. Однако представляется возможным модификация метода [5] и для исследования адаптивных сетей связи с протоколами случайного множественного доступа. Наиболее известным адаптивным протоколом является синхронная Алоха, управляемая алгоритмом Ривеста [21], в котором строится байесовская оценка числа АС с задолженностью. К сожалению, в литературе отсутствует описание детального аналитического исследования отого протокола. Эвристические соображения и результаты имитационного моделирования приведены в [4]. В отличие от алгоритма Ривеста адаптацию протоколов случайного множественного доступа предлагается осуществлять автоматами с целесообразным поведением [22] с достаточно простой тактикой. Можно показать, что нестабильные сети с такими протоколами функционируют устойчиво как моностабильные. Определяется положительная пропускная способность сети, величину которой можно сделать равной пропускной способности сети с динамическим протоколом, выбирая соответствующие значения параметров адаптера. В адаптивных сетях с конечным числом АС исчезает явление бистабильности, и сети становятся моностабильными. Здесь обнаружено качественно различное функционирование сетей в условиях нормальной загрузки, когда потенциально возможная всеми АС загрузка меньше пропускной способности сети, и в условиях перегрузки, если она выше пропускной способности. Для всех рассмотренных сетей связи получены асимптотические распределения вероятностей состояний соответствующих математических моделей, которые позволяют получать все маргинальные распределения: распределение вероятностей состояний канала, состояний ИПВ, т.е. числа АС с задолженностью! состояний адаптера, а также найти все интересующие исследователя характеристики функционирования сети связи с протоколом случайного множественного доступа, в том числе и характеристики времени доставки сообщения [23,24].

Ключевые слова

Авторы

ФИООрганизацияДополнительноE-mail
Назаров Анатолий АндреевичТомский государственный университетпрофессор, доктор технических наук, зав. кафедрой теории вероятностей и математической статистики факультета прикладной математики и кибернетики
Всего: 1

Ссылки

Шварц М. Сети связи: протоколы, моделирование и анализ. М.: Наука, 1992.
Флинт Д. Локальные сети ЭВМ. М.: Финансы и статистика, 1986.
Самойленко С.И. Сети ЭВМ. М.: Наука, 1986.
Бертсекас Д., Галлагер Р. Сети передачи данных. М.: Мир, 1989.
Назаров А. А. Асимптотический анализ марковизируемых систем. Томск: Изд-во Том. ун-та, 1991.
Назаров А.А., Юревич Н.М. Исследование сети с протоколом случайного множественного доступа Алоха без повторной передачи искаженных сообщений // Автоматика и вычислительная техника. 1993. № 3. С. 52-56.
Назаров А.А., Юревич Н.М. Исследование сети со статическим h-настойчивым протоколом случайного множественного доступа Алоха // Автоматика и вычислительная техника. 1995. J6 1. С. 68-78.
Назаров А.А., Юревич Н.М. Исследование сети с динамическим протоколом случайного множественного доступа Алоха // Автома тика и вычислительная техника. 1995. № 6. С. 53-59.
Назаров А.А., Юревич Н.М. Исследование явления бистабильности в сети с протоколом Алоха для конечного числа станций // Автоматика и телемеханика. 1996. № 9. С. 91-100.
Назаров А.А., Пичугин С.Б. Исследование спутниковой сети связи методом математического моделирования // Изв. вузов. Физика 1992. № 9. С. 120-129.
Назаров А.А., Неволько М.П., Пичугин С.Б. Аналитические соотношения для расчета производительности спутниковой сети связи с множественным доступом // Изв. РАН. Техническая кибернетика 1993. № 6. С. 90-97.
Бергман О.С., Назаров А.А. Сравнение стратегий контроля несущей в протоколе МДКН/ОК // Автоматика и вычислительная техника. 1996. № 2. С. 59-68.
Кузнецов Д.Ю., Назаров А.А. Исследование сетей связи с адаптивными протоколами случайного множественного доступа // Материалы четырнадцатой Белорусской зимней школы-семинара по теории массового обслуживания. Минск: 1998. С. 195-199.
Скитович В.П. Элементы теории массового обслуживания. Л.: Изд-во ЛГУ, 1976.
КяейнрокЛ. Вычислительные системы с очередями. М.: Мир, 1979.
Башарин Г.П., Харкевич А.Д., Шнепс М.А. Массовое обслуживание в телефонии. М.: Наука, 1968.
Фалин Г.И. О неустойчивости сети Алоха // Проблемы передачи информации. 1990. № 1. С. 79-82.
Цыбаков Б.С., Бакиров В.Л. Анализ устойчивости сети с коммутацией пакетов и его приложение к построению единого подхода к синхронным и асинхронным радиосетям Алоха // Проблемы передачи информации. 1988. № 2. С. 70-85.
Назаров А.А. Устойчивое функционирование нестабильных сетей связи с протоколами случайного множественного доступа // Проблемы передачи информации 1997. №2. С. 101-111.
Назаров А. А. Исследование явления бистабильности в спутниковых сетях связи // Автоматика и телемеханика. 1994. № 10. С. 117-124.
Rrvest R.L. Network control by bayessian broadcast (Report M)T/LCS/TM-285) Cambridge, MA: MIT, Laboratory for computer scince, 1985.
Цетлин М.Л. Исследование по теории автоматов и моделированию биологических систем. М.: Наука, 1969.
Бутакова Е.Л., Назаров А.А. О распределении числа повторных попыток передачи сообщения в сети с одним протоколом случайного множественного доступа//Международная конференция «Всесибирские чтения по математике и механике»: Тезисы докладов. Томск, 1997. С. 135-136.
Бутакова Е.Л. Назаров А.А. Распределение времени доставки сообщения в сетях с протоколами случайного множественного доступа// Автоматика и вычислительная техника. 1997. № 6. С. 65-75.
 Исследование компьютерных сетей связи с протоколами случайного множественного доступа | Вестн. Том. гос. ун-та. 2000. № 271.

Исследование компьютерных сетей связи с протоколами случайного множественного доступа | Вестн. Том. гос. ун-та. 2000. № 271.

Полнотекстовая версия