Реализация модели канала

Продолжение темы имитационного моделирования канала коллективного доступа.

При построении алгоритма имитации работы всех каналов сети, сеть рассматривается как совокупность параллельно протекающих процессов. Каждый процесс есть некоторая последовательность событий, приводящих к изменению состояний синхронных автоматов, описывающих поведение элементов сети, причём, под событием понимается любое изменение сигналов на входах этих автоматов.

В общем случае, эти процессы не должны считаться независимыми, а а должны взаимодействовать между собой.

Принципы взаимодействия процессов могут быть проиллюстрированы следующим примером. Представим себе фрагмент сети, включающий в себя N абонентов, работающий на одной и той же частоте. Такой фрагмент может рассматриваться как система массового обслуживания с одним прибором, который обслуживает некий поток требований от N станций. Если требование, придя в систему, застаёт прибор свободным, то оно занимает прибор и обслуживается в нём в течение некоторого промежутка времени, после чего покидает систему. В противном случае, требование поступает в очередь к прибору, где будет дожидаться завершения обслуживания всех ранее поступивших в систему требований. Причём эта очередь «виртуальна» - требования могут быть сосредоточены как в одном узле, так и распределены по разным узлам.

В такой системе, на начальных фазах обслуживания, «передатчик» каждого узла может находиться в одном из следующих состояний:

1. ожидание очередного кадра;
2. ожидание освобождения канала;
3. запуск таймера, определяющего время начала передачи кадра (основной принцип канального протокола – «слушать», прежде чем «вещать»);
4. ожидание завершения данного интервала;
5. захват канала и передача кадра.

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

Например, (см. рисунок 1), переход автомата из состояния «ожидание кадра» в состояние «ожидание освобождения канала» осуществляется при появлении сигнала «требование передачи», а переход в следующее состояние – «запуск таймера отсрочки» - зависит от состояний аналогичных автоматов, претендующих на тот же канал.

Если какой либо другой аналогичный автомат находится в состоянии «захват канала», то рассматриваемый автомат будет получать сигнал «канал занят».

Рисунок 1

Из рассматриваемого примера видно, что в моделируемой сети могут сосуществовать параллельные «типовые» процессы, каждый из которых может находиться в своём уникальном состоянии. Но, при их имитации на одной ЭВМ, эти события необходимо рассматривать последовательно. Поэтому, совокупность параллельно протекающих процессов должна быть представлена в виде упорядоченной последовательности моментов наступления событий во времени.

При таких условиях, сканируя эту последовательность, и определяя, в каждый наступивший момент реакции автоматов на изменения входных сигналов, можно сымитировать любую ситуацию в системе. При этом, любая сложившаяся ситуация может быть представлена в виде вектора Z=║Z_n║, каждый элемент которого - Z_n, соответствует конкретному автомату - M_n, а значение этого элемента – состоянию данного автомата. Например, если некий автомат M₁ занял канал, (состояние St₄), а автомат M₂ ожидает его освобождения (состояние St₁), то фрагмент вектора Z будет содержать информацию, которая показана на рисунке 2:

Конечный автомат	Текущее состояние
M1	St4
M2	St1
.	.

Рисунок 2

При наступлении особого состояния, (изменении входных сигналов), этот вектор модифицируется с помощью следующего алгоритма:

- поочерёдно рассматриваются состояния всех автоматов;

- при рассмотрении каждого состояния определяется соответствующая ему выходная комбинация - µ;

- на основании полученных µ отыскиваются входные комбинации для всех автоматов - λ;

- найденные входные комбинации фиксируются в памяти ЭВМ;

- с помощью таблиц переходов определяются новые состояния автоматов.

В принципе, такие операции («ревизии» состояний системы) можно производить на каждом такте имитации – любая ситуация может считаться особым состоянием.

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

В основном, моменты выхода из пассивных состояний определяются таймерами, поскольку именно они определяют моменты системного времени, соответствующие узловым точкам в имитируемых параллельных процессах.

Состояния этих таймеров – числа T_k, которые соответствуют моментам активизации тех или иных автоматов. Если таймер запущен, то это число должно каким-то образом уменьшаться, и в тот момент, когда оно станет равным нулю, заданный тайм-аут должен считаться завершённым.

Как в реальной системе, так и в имитационной модели, могут одновременно работать k таймеров, причём каждый из них может завершить отсчёт в конкретный момент времени – T_k. Имея такие числа можно определить момент наступления ближайшего особого состояния системы, которое может быть определено с помощью проверки условия (1):

TR = min Tk	(1)
k

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

Следует отметить, что особые события могут порождаться не только таймерами, но и всеми другими автоматами. Причём эти автоматы могут находиться в пассивных состояниях, время выхода из которых – T_a, определить нельзя.

В таких случаях возможно следующее решение – если входной сигнал не меняет состояния автомата, то считать T_a = ∞. В противном же случае считать, что T_a = 0.

Для определения значения T_a можно воспользоваться таблицей переходов, действуя следующим образом:

1. выделить строку такой таблицы, которая соответствует текущему состоянию автомата;
2. убедиться в том, что текущая комбинация входных сигналов соответствует «петле», то есть возвращает автомат в то же состояние, в котором он уже находиться;
3. если это условие выполняется – то T_a : = ∞, в противном случае - T_a : = 0.

Например, в представленной на рисунке 3 таблице переходов, выделенные элементы соответствуют активным состояниям автомата, которые следует считать особыми событиями, а все остальные элементы – пассивным состояниям автомата.

Состояние	Символы входного алфавита
	λ0	λ1	λ2	λ3	λ4	λ5	λ*
St0	St0	St1	St4	St4	-	-	-
St1	St2	St1	St4	St4	-	-	-
St2	-	-	-	-	-	-	St3
St3	-	-	-	-	St3	-	-
St4	St0	-	St4	St4	-	-	-

Рисунок 3

Рассмотренный принцип имитации поведения сложных систем с дискретными событиями может являться основой для построения других аналогичных моделей. При этом программные модули, обеспечивающие имитацию квазипараллельных процессов в системе, могут оставаться неизменными – если потребуется исследовать поведение групповых каналов, основанных на использовании иных протоколов, то программное обеспечение может оставаться неизменным, и только модели поведения «передатчиков» и «приёмников» могут быть представлены в виде таблиц иного содержания.

В то же время, данный принцип может являться основой для обеспечения наглядной интерпретации поведения системы. Но это возможно лишь только в том случае, если основными мотивами расчленения модели на операторы и блоки (конечные автоматы) будут являться не только «вычислительные удобства» для программистов, но и категории, понятия и образы, которые понятны и привычны для большинства специалистов, работающих в данной области.

Здравствуйте и разрешите представиться! 

Это блог компании Смарт Текнолоджис. Мы занимаемся разработкой в сфере телекоммуникаций.
Все, что связанно с сетевыми технологиями представляет для нас огромный интерес.

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

Тонкости языков программирования, мощь методологий разработки программных проектов, сложность архитектур распределенных программных систем, строгость алгоритмов и методов оптимизации заставляют нас постоянно уделять им повышенное внимание и учиться, учиться, учиться…

А мы не против!

И конечно в нашей стране не мы одни идем этим не простым путем. Именно из осознания этого и родился это блог. В нем мы постараемся освещать вопросы, которые показались нам наиболее интересными и непростыми. И если хотя бы один пост окажется полезными студенту, инженеру, ученому или просто случайному читателю, мы будем считать, что все это не зря.