Модели и основные показатели информационных потоков в задачах сетевого управления

Данные, передаваемые по ТКС, представляют собой закодированные сообщения. Они измеряются числом битов передаваемой информации, определяющим длину данных.

Передаваемые данные часто разбиваются на блоки постоянной или переменной длины, называемые пакетами. Такая декомпозиция данных используется в ТКС с коммутацией пакетов. В этом случае пакеты передаются от узла-источника информации к узлу-получателю данных по некоторому маршруту, разделяя между собой доступные каналы и средства связи ТКС.

В случае ТКС с коммутацией каналов между источником информации и её получателем устанавливается специальный (выделенный) маршрут передачи данных от одного узла к другому без разделения коммуникационных ресурсов.

Пакеты, поступающие на вход узла ТКС, в процессе движения к узлу-получателю, накапливаются (запоминаются) и обрабатываются с целью выбора доступного ими наилучшего канала связи. Затем они считываются в этот канал, как только наступит время их передачи.

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

Пропускная способность канала связи - это число, которое ограничивает общее количество пакетов определенной длины, передаваемых по каналу за заданное время. Для определения этого числа обычно используется следующая формула [7]

, (3.28)

где - максимальное число передаваемых пакетов определенной длины d, T - время передачи. Величина m измеряется числом пакетов, передаваемых в секунду (пакет/c). Интенсивность поступления пакетов l определяется скоростью в единицах пакет/c.

Канал связи характеризуется скоростью s передачи данных, измеряемой обычно в бит/c. Если, например, канал связи, передающий пакеты длиной d=10³ бит, работает со скоростью s=2 × 10³ бит/c, то он сможет передавать пакеты, поступающие с интенсивностью l= 2 пакетов/c.

В общем случае, если l ³ m, входные пакеты будут накапливаться и возникнет очередь.

Для количественной оценки таких ситуаций используется показатель

, (3.29)

называемой коэффициентом использования канала связи или интенсивностью сетевой нагрузки. При r ³ 1 возникают перегрузки (“скученность” пакетов) и возрастает время задержки. В этих случаях поступающие пакеты начинают блокироваться.

Для обслуживания очереди из интенсивно (с перегрузкой) поступающих пакетов обычно используются следующие стратегии (дисциплины) обслуживания [1, 4, 6]:

- обслуживание в порядке поступления;

- обслуживание в обратном порядке, когда первым обслуживается пакет, который поступил последним;

- обслуживание с приоритетом.

Эти стратегии основываются на вероятностном подходе, связанном с анализом статистики входящих пакетов и распределением их длин в терминах теории массового обслуживания (queueing theory) [9].

Пакеты поступают на входы узлов ТКС или отправляются с выходов узлов, образуя изменяющиеся с течением времени информационные потоки.

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

Независимо от природы возникновения потоков данных, представляющие их пакеты последовательно поступают на входы узлов ТКС. Они запоминаются и ждут своего обслуживания (передачи) в накопителе соответствующего узла ТКС с ограниченной памятью. Затем эти потоки в некоторые дискретные моменты времени (вообще говоря, управляемые) передаются по свободным каналам связи в другие узлы ТКС.

Обозначим через z(t) общее число входных пакетов, поступивших в накопитель (буфер) узла ТКС к моенту времени t. Аналогично введём функцию y(t), определяющую общее число выходных пакетов, отправленных к моменту времени t в канал связи после ожидания в накопителе. Тогда целочисленная функция

l(t)=z(t)-y(t), t Î [t₀, t), (3.30)

определит текущее число пакетов, ожидающих своего обслуживания (передачи) к моменту времени t.

Пакеты данных последовательно поступают на вход узла ТКС в дискретные моменты времени t₁, t₂, …. В эти моменты времени значения целочисленной функции z(t) возрастает на 1, т.е.

z(t_k+1) = z(t_k) + 1, k= 0, 1, 2, …. (3.31)

Аналогичным образом в некоторые дискретные моменты времени рекуррентно изменяется функция y(t), т.е.

. (3.32)

Моменты отправления пакетов данных в ТКС образуют монотонно возрастающую последовательность вида

. (3.33)

Моменты отсылки пакетов могут совпадать с моментами их поступления t_k в тех случаях, когда канал связи свободен.

Ради простоты предположим, что входные пакеты обслуживаются в порядке их поступления в узел ТКС. Однако следует отметить, что рассматриваемые модели и результаты справедливы и при других стратегиях (дисциплинах) обслуживания входных пакетов [1, 7].

Примеры возможного изменения функции получения пакетов данных z(t) и функции передачи пакетов данных y(t) по мере последовательного поступления входных пакетов в узел ТКС представлены на рис. 3.3. Здесь функция z(t) изображена сплошной линией, а функция y(t) - пунктирной линией.

Рис.3.3. Динамика получения и передачи пакетов данных в ТКС

На рис. 3.3 показаны также времена ожидания (задержки) пакетов данных D₁, D₂, …, D₆ . Эти величины определяют период времени, в течение которого соответствующий пакет находится в накопителе узла ТКС с момента его поступления t_k до момента его отправки , причём ³ .

Наряду с начальным моментом t₀ рассмотрим некоторый конечный момент t_T . Тогда общее число поступлений входных пакетов в узел ТКС на интервале времени T= t_T - t₀ можно вычислить по формуле

n(T)=z(t_T)-z(t₀). (3.34)

В примере на рис. 3.3. общее время поступления потоков данных n(T)=6.

Аналогично определяется общее число отсылок (передачи) пакетов данных за время T

m(T)=y(t_T)-y(t₀). (3.35)

Средние скорости поступления и передачи входных пакетов определяются соответственно по формулам

(3.36)

(3.37)

Рассмотрим интегральный показатель процесса ожидания (задержки) входных пакетов в узле ТКС

. (3.38)

Геометрически этот показатель определяет площадь под кривой l (t) на интервале [t₀, t). Так как это площадь образована прямоугольниками с высотой 1 и длиной D_k, то справедливы следующие соотношения

(3.39)

Таким образом, величина J(T) зависит не от времён ожидания D_k, а от суммы моментов времени отправки пакетов по каналам связи ТКС.

Так как l (t) -это общее число ожидающих отправки входных пакетов в момент времени передачи t, то среднее число входных пакетов в накопителе узла ТКС можно определить по формуле

. (3.40)

Средним временем ожидания на интервале [t₀, t) принято называть величину [9]

. (3.41)

Поскольку средняя скорость поступления пакетов в узел ТКС определяется формулой (3.36), то можно установить связь между средними величинами (3.40) и (3.41) в виде

. (3.42)

Выражение (3.42) совпадает с известной формулой Литта [1, 9], полученной для стратегии (дисциплины) обслуживания пакетов в порядке их поступления на конечном интервале времени [t₀, t).

Для адресной и своевременной передачи информации в ТКС необходимо разработать модели на алгоритмы управления коммуникационным оборудованием и дискретными потоками данных.

Одной из важнейших проблем управления ТКС является задача маршрутизации потоков данных, т.е. определение пути на графе ТКС, связывающего некоторый начальный узел ТКС с конечным узлом. Обычно эта проблема ставится как оптимизационная задача, в результате решения которой определяются оптимальные (например, по длине или по времени передачи) маршруты.

Другая проблема заключается в управлении потоками данных в ТКС по определённому маршруту “из конца в конец”, т.е. от начального узла маршрута к его конечному узлу. При этом необходимо учитывать ограниченные сетевые ресурсы ТКС, связанные с ограничениями на пропускную способность каналов связи, объём памяти накопителей узлов и т.п. Вследствие этого приходится регулировать темп (скорость) передачи данных между всеми узлами маршрута передачи сообщений.

Важной проблемой управления ТКС является анализ влияния сетевого трафика (нагрузки), который может случайным или непредсказуемым образом изменяться в широких пределах, на качество работы ТКС и представляемые ей услуги.

Анализ трафика ТКС необходим для учёта в процессе управления потоками данных реально складывающегося сетевого трафика. Дело в том, что резкое возрастание сетевой нагрузки может временно исчерпать возможности сетевых ресурсов (каналы связи и накопители в узлах ТКС) и вызвать значительные сетевые перегрузки (“скрученность” потоков).

Таким образом, возникает необходимость в синтезе алгоритмов робастного или адаптивного управления потоками данных, обеспечивающих работоспособность ТКС в условиях неопределённости стохастически или непредсказуемо изменяющегося трафика.

Значительное увеличение трафика x приводит к резкому возрастанию задержки (времени обслуживания) D. При этом производительность ТКС, измеряемая общим числом P пакетов, доставляемых по назначению (т.е. адресату ТКС) в единицу времени, может сильно снижаться.

Общий характер этих динамических явлений, неблагоприятно влияющих на качество предоставляемых ТКС услуг, показан на рис. 3.4, a) и b).

Рис. 3.4. Зависимость задержки пакетов данных a) и производительности ТКС b) от изменения трафика

Как видно из Рис. 3.4, a), b), при увеличении сетевой нагрузки x, превышающей допустимый предел x_*, происходит значительное увеличение задержки пакетов и резкое падение производительности ТКС. Это связано с блокировкой ограниченных сетевых ресурсов (ограничения пропускной способности каналов связи и объёма памяти накопителей узлов) и возможностью возникновения тупиковой ситуации (при x=x^*), когда все накопители узлов ТКС переполнены. В этом случае поступление пакетов данных прекращается и производительность ТКС падает до нуля (P=0), т.е. ТКС перестаёт функционировать.

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