Введение к работе
Актуальность темы. В последнее десятилетие широкое распространение получили компьютерные сети и системы передачи цифровой информации. В традиционных сетях и системах используются каналы связи, соединяющие абонентов (узлы) попарно, т.е. каждый канал используется только парой соседних абонентов. Такая структура сети имеет то преимущество, что процесс передачи сообщений мевду одной парой абонентов непосредственно не влияет на процесс передачи между другими парами. Распределение каналов мевду парами чаще всего фиксировано и происходит на стадии проектирования системы. Однако традиционный подход к построению сети не всегда приемлем или по экономическим соображениям, или из-за необходимости иметь динамическую топологию сети, а в некоторых случаях (связь с подвижными абонентами) невозможен.
Альтернативный подход - использование широковещательного канала связи. Когда говорят о широковещательном канале, предполагают, что каждый абонент имеет возможность принимать любое передаваемое сообщение. Широковещательными могут являться наземные и спутниковые радиоканалы, волоконно-оптические каналы и т.п. Применение широковещательного канала имеет свои преимущества и недостатки. С одной стороны, появляется возможность сравнительно легко изменять топологию сета, обеспечивать связь с абонентами, перемещающимися в пространстве. С другой стороны, возникает необходимость каким-то образом управлять доступом абонентов к каналу, иначе могут возникнуть конфликтные ситуации, ведущие к полной или частичной потере сообщений.
Задача разделения ресурса широковещательного канала между абонентами может решаться различными методами. Эти метода называются методами множественного доступа. Среди методов множественного доступа можно выделить два полярных типа: бесконфликтные и конфликтные.
В случав бесконфликтных методов сообщение, переданное одним абонентом, никогда ке может Сыть разрушено при передаче сообщением, переданным другим абонентом. Среда бесконфликтных методов М05ШО выделить статические и динамические. К статическим методам относятся частотное (FDMA) и временное (ТША) разделение
каналов, а также смешанный вариант частотно-временного разделения, осуществляемый, например, в широкополосшх системах с кодовым разделением (CDMA) . К бесконфликтным методам с динамическим распределением ресурса канала относятся различные методы, использующие резервирование. К этой же категорші относятся методы с передачей маркера, в которых физический или логический маркер передается от одного абонента к другому, передавая тем самым право на передачу.
При использовании конфликтных методов, как следует из их названия, могут возникать конфликты, т.е. разрушение сообщений в результате их взаимного наложения. Как и в случае бесконфликтных методов здесь можно выделить два класса.К первому относятся алгоритмы с разрешением конфликтов с помощью номеров абонентов, различные алгоритмы с контролем несущей (CSMA). Методы, принадлежащие ко второму классу, принято называть методами случайного множественного доступа (СВД). К этим методам относятся алгоритмы типа АЛОХА, стек-алгоритмы , алгоритмы типа алгоритма дробления и их многочисленные модификации.
В работах отечественных и зарубежных авторов показано, что при пульсирующем потоке малой интенсивности и большом числе абоненте»:., алгоритмы случайного множественного доступа более оффектнвны, чем другие метода доступа. Они обеспечивают меньшую задержку, чем другие метода, при этом задержка практически не зависит от числа абонентов.
В большинстве работ, посвященных исследованию систем СВД, предполагается, что абоненты способны отличить наложение в канале нескольких пакетов от отсутствия передачи. Однако на практике это не всегда так. В этом случае говорят об обратной связи типа успех-неуспех. Исследованию СВД с этим типом обратной связи посвящено относительно небольшое число работ. Практически во всех алгоритмах, предложенных в этих работах , в отличие от алгоритмов для других типов обратной связи, используется так называвши тестирующий пакет, который позволяет отличить ситуацию "пусто" от ситуации "конфликт". Однако применение тестирующего пакета в реальных системах не всегда приемлемо. Кроме того, в некоторых системах передаваемая информация, получившая слишком большую задержку при передаче, теряет ценность для получателя. Модель
такой системы Сила названа моделью с нетерпеливыми пакетами.
Целью работы является разработка и исследование эффективности алгоритмов СЭД для системы с обратной связью типа успех-н&услех без тестирующих пакетов.
Методы исследования. При получении основных результатов работы автором использовались , в основном, методы теории вероятности, теорий случайных процессов, в частности марковских и регенирируюших процессов, численные метода, методы комбинаторного анализа.
Научная новизна диссертационной работы заключается в следующем:
- предложен алгоритм СМД для системы с обратной связью типа
успех-неуспех, не использующий тестирующие пакеты;
предложены простые для реализации алгоритмы СМД для системы с обратной связью типа успех-неуспех и нетерпеливыми пакетами;
предложена методика ' построения двухсторонних оценок характеристик алгоритмов с нетерпеливыми пакетами;
- предложена методика имитационного моделирования алгоритмов
СВД на основе ассоциированных алгоритмов.
Практическая ценность диссертационной работа.
Предложенные алгоритмы СМД позволяют повывать оперативность обмена информацией го каналам с недостоверным определением конфликта в сетях ЭВМ и системах связи с большим 'шелом абонентов и пульсирующим потоком сообщений.
Разработанный в работе метод имитационного моделирования позволяет получать оценки характеристик алгоритмов СВД для широкого класса алгоритмов.
Апробация работы. Основные материалы работы докладывались на I (Минск, 1989) и II (Минск. 1991) Всесоюзных конференциях по информационным системам множественного доступа, на X Симпозиуме по проблеме избыточности в информационных системах (Ленинград, 1989), на XV Всесоюзной школе - семинаре по вычислительным сетям (Ленинград, 1990), на семинарах в СНТЛАП и ИППИ РАН.
Публикации- Материалы, отражающие основное
содерасание и результаты даосертациониой работы, опубликованы в 9 печатных работах.
Основные положения, выносимые на защиту:
алгоритм ОВД о отложенными интервалами;
стек-алгоритм и алгоритм с перемешиванием для нетерпеливых пакетов;
- метод построения двухсторонних оценок характеристик
алгоритмов с нетерпеливыми пакетами.
Структура и об ъем работы. Диссертационная работа состоит из введения, 4 , разделов, заключения и приложения. Работа содержит 112 страниц основного машинописного текста, 15 рисунков.' Список использованной литературы содержит 57 наименований.
