авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 |

«Министерство промышленности и торговли Российской Федерации ОТКРЫТОЕ АКЦИОНЕРНОЕ ОБЩЕСТВО «КОНЦЕРН «СИСТЕМПРОМ» УДК 621.39 ...»

-- [ Страница 2 ] --

Отличительной особенностью потокового видео, например IPTV, является отсутствие диалогового элемента, благодаря чему требования к задержкам могут быть снижены по сравнению с требованиями для интерактивного видео. Вариация задержки несущественна, поскольку компенсируется адаптивными буферами на стороне пользователя. При этом задержка, добавляемая буфером, может достигать 100–500 мс.

Для сохранения хорошего качества изображения требуется низкая величина потери пакетов.

Для гарантии эффективного предоставления видеоуслуг по сети IP величина коэффициента потерь пакетов IP не должна превышать 10.

Модель измерения качества видеоуслуг согласно Рекомендации J.241 показана на рисунке 5.

Здесь заданы четыре точки измерений:

A – кодер видео;

• B – уровень IP на стороне головной станции (IP-трафик);

• C – уровень IP на стороне оборудования пользователя (IP-трафик);

• D – декодер видео.

• Рисунок 10 – Модель измерения показателей качества при предоставлении услуг передачи видео В таблице 10 приведены значения параметров NP при передаче видеоинформации.

Таблица 10 – Значения показателей NP при передаче видео Значения ключевых параметров Степень симметрии Скорость передачи данных, бит/с Потеря пакетов, % Приложение Доп. параметры задержки, мс задержка, мс Одностор.

Вариация Предпочт. Рассинхро-низация Интерактив-ное Двустор. 150, допуст. видео и аудио 16–384 - видео 80 мс Потоковое Одностор. 10 с 16–384 - 1 видео Услуги передачи данных (best effort) Традиционно в сетях IP трафик передается по методу «негарантированной доставки» (best effort). Сеть старается обработать поступающий трафик как можно быстрее, но при этом не дается гарантий относительно результата. По методу best effort обслуживаются преимущественно веб услуги, электронная почта, обмен сообщениями, передача файлов. Также популярны приложения реального времени, связанные с передачей данных, например интерактивные игры.

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

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

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

Высокоприоритетные услуги по передаче данных, например электронная коммерция.

• Основные требования пользователя к данной категории услуг – немедленное начало передачи после запроса пользователя. Задержка при передаче в пределах нескольких секунд считается приемлемой.

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

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

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

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

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

Фоновые приложения. Для данной категории единственным требованием к качеству • передачи данных является отсутствие ошибок при передаче. Требования к задержкам минимальны. К данной категории относится передача факсимильных сообщений, задержка при передаче которых не должна превышать 30 секунд, однако допустимы потери информации в некоторых пределах. К фоновым услугам также относится обмен короткими сообщениями, при котором допускается задержка в пределах 10 секунд.

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

Рекомендация МСЭ-Т I.356 определяет 6 классов качества функционирования технологии ATM (от 0 до 5), которые показаны в таблице 11. Специфицируются качества передачи ячеек ATM по сети Ш-ЦСИС.

В Рек. МСЭ-Т Y.1541 предложены предварительные нормы для характеристик качества функционирования IP-сетей, определенных в Рек. МСЭ-Т Y.1540. Здесь рекомендовано шесть классов качества обслуживания – от лучшего класса 0 до худшего («ненормированного») класса 5, для которого нормы не устанавливаются. Все классы QoS пригодны для широкого набора приложений, включая телефонию, мультимедийную конференцсвязь и интерактивную передачу данных. Классы качества технологии IP, заданные в Рек. МСЭ-Т Y.1541, показаны в таблице 12.

В системе ETSI UMTS предусмотрено 4 класса трафика, определяющие классы QoS, основные характеристики которых приведены в таблице 13. В качестве значений параметров указаны диапазоны, которые должны поддерживаться в сетях UMTS.

Таблица 11 Классы сетевого QoS технологии ATM в соответствии с Рек. МСЭ-Т I. Параметры производительности приоритетом 0+1 (CLR0+1) Доля потерянных ячеек с Доля потерянных ячеек с Доля серийных ошибок в Двухточечная вариация Доля ошибочных ячеек передачи ATM ячейки приоритетом 0 (CLR0) блоке ячеек (SECBR) задержки (2 pt. CDV) адресованных ячеек Доля неправильно Средняя задержка Класс QoS (CMR) (CDT) (CER) Класс 1 По По 3 400 мс 3 мс Нет По умолчанию умолчанию умолчанию (строгий) Класс 2 По По Не определено Не определено Нет По умолчанию умолчанию умолчанию (приемлемый) Класс 3 По По Не определено Не определено Не определено По умолчанию умолчанию умолчанию (двухуровневый) Класс 4 Не Не Не определено Не определено Не определено Не определено Не определено определено определено (неопределенный) Класс По По 3 400 мс 6 мс Нет По умолчанию (строгий умолчанию умолчанию двухуровневый) Таблица 12 Классы сетевого QoS уровня IP в соответствии с Рек. МСЭ-Т Y. Нормы показателей качества обслуживания IPDV IPTD IPER IPLR (верхняя граница Класс (верхняя (верхняя Примеры приложений (верхняя граница граница граница разности 1 QoS вероятности среднего вероятности квантили IPTD потерь пакетов) значения) ошибок) и наим. значения IPTD) Реального времени, чувствительные к вариации задержки, высокоинтерактивные 100 мс 50 мс 0 0,1 % 0,01 % (VoIP, видеоконференцсвязь) Реального времени, чувствительные к вариации задержки, интерактивные (VoIP, 400 мс 50 мс 1 0,1 % 0,01 % видеоконференцсвязь) Данные транзакций, высокоинтерактивные 100 мс Н 2 0,01 % 0,01 % (сигнализация) Данные транзакций, интерактивные 400 мс Н 3 0,1 % 0,01 % Чувствительные только к потерям пакетов, а не к задержкам (короткие транзакции, 1с Н 4 0,1 % 0,01 % массовая передача данных, потоки видео) Традиционные приложения стандартных Н Н Н Н сетей IP (веб-услуги, электронная почта) Таблица 13 Классы сетевого QoS UMTS Речевой Потоковый Интерактивный Фоновый Название класса Чувствительность к Нестрогие требования к Интерактивность.

вариации задержки. Точно Чувствительность к задержке.

Чувствительность к Характеристика класса заданная небольшая вариации задержки Чувствительность к потерям задержка потерям Передача речи, VoIP, Потоковая передача Веб-услуги, сетевые игры, Фоновая загрузка, телефония (видео и Пример приложения мультимедийных данных электронная коммерция электронная почта аудио), видеоигры 16 000 кбит/с – верхний 16 000 кбит/с – верхний Макс. скорость передачи 16 000 кбит/с 16 000 кбит/с предел предел данных 1 500 или 1 502 1 500 или 1 502 1 500 или 1 502 1 500 или 1 Макс. размер SDU 5 102, 102, 5 103, 5 102, 102, 5 103, Остаточный коэфф-т 8 4 103, 105, 6 10 (7) 4 103, 105, 6 10 (7) ошибок BER 103, 104, 105, 106 103, 104, 105, 101, 102, 7 103, 103, 102, 7 103, 103, 104, Вероятность ошибок при 103, 104, 106 103, 104, передаче SDU 104, 100 мс 300 мс Н Н Макс. задержка передачи Гарантированная 16 000 кбит/с 16 000 кбит/с Н Н скорость передачи В таблице 14 показано соотношение классов QoS IP, ATM и UMTS.

Таблица 14 Соотношение классов QoS IP, ATM и UMTS Класс QoS IP Класс QoS ATM Класс QoS UMTS Речевой 0 Потоковый 1 2и3 Интерактивный Фоновый 5 Тема 2.1. Первая модель Эрланга Постановка задачи Рассмотрим многолинейный пучок из полнодоступных идентичных линий (обслуживающих устройств, каналов и т. п.), работающих параллельно и не имеющих мест для ожидания. Примем, что на этот пучок поступает пуассоновский поток (ПП) однотипных заявок с En = {n} постоянной интенсивностью заявок в единицу времени. Пусть – состояние рассматриваемой системы массового обслуживания (СМО), когда занято n линий, n J = {0,1,…,}.

Поскольку мест для ожидания нет, то в состоянии E поступающие заявки блокируются, т. е. теряются и не оказывают влияния ни на характер поступающего потока, ни на его интенсивность. С точки зрения приложений это упрощающее предположение означает, что либо вероятность p потерь достаточно мала (например, порядка нескольких процентов), либо что потерянная заявка направляется на другую СМО, так что влиянием повторных попыток установить соединение можно пренебречь. При этом порядок занятия свободных линий пучка может быть любым – случайным или упорядоченным.

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

µ (1 p ) µ p µ MM µ, где p – вероятность блокировки Рисунок 15 – СМО Напомним теперь идею обозначений Кендалла, согласно которой СМО простой структуры задается посредством следующего описания:

число r мест для число линий поток обслуживание ожидания Символ M на первом месте означает пуассоновский поток, а на втором – экспоненциальное MM r= MM µ обслуживание. Рассматриваемую СМО можно кодировать как или как, заявок 1, опуская четвертую позицию при r = 0. Значения интенсивностей ед.вр. и заявок µ ед.вр. указывать не обязательно (рисунок 15), причем физический смысл абстрактного термина «заявка может интерпретироваться по-разному в каждом конкретном случае: вызов, сообщение, пакет, слот и т. д. Каждая заявка на все время обслуживания в моносервисной СМО занимает одно из идентичных обслуживающих устройств, которые можно называть также приборами, линиями, каналами и т. д.

Для пуассоновского потока среднее число заявок, поступивших за интервал длины T, равно T, а средняя длительность экспоненциального обслуживания составляет 1 µ. Поэтому за время T = 1 µ поступит в среднем := µ заявок. Величина не зависит от выбранной единицы времени и называется интенсивностью поступающей нагрузки. На практике измеряется в эрлангах (Эрл), причем, например, = 3.5 Эрл означает, что либо среднее значение числа занятых в СМО линий в некоторый фиксированный или произвольный момент времени равно 3.5, либо в среднем за рассматриваемый интервал занято 3.5 линии.

Построение процесса размножения и гибели Напомним некоторые важные для дальнейшего изложения факты из курса теории вероятностей и ТМО. Пусть X (t ) – число заявок, обслуживаемых -линейным пучком в момент t, t 0. Так как принятая заявка на все время обслуживания занимает одну линию, то число обслуживаемых заявок совпадает с числом занятых линий, т. е. пространством состояний для J = {0,1,…,} 1 случайного процесса X (t ), t 0, служит множество,.

Поскольку по предположению поступающий поток является пуассоновским с параметром, то при любых t0 0, 0 число Y ( ) заявок, предложенных СМО на интервале (t0, t0 + ), обладает пуассоновским распределением с параметром :

( ) m P {Y ( ) = m} = e m !, m = 0,1…. (1) Это распределение не зависит ни от того, будут ли поступившие заявки приняты на обслуживание или получат отказ, ни от того, как долго будут обслуживаться принятые заявки. В частности, из (1) следует, что P {нет поступлений заявок на (t0, t0 + )} = P {Y ( ) = 0} = e, (2) т. е. расстояние между поступающими заявками имеет экспоненциальное распределение и не зависит ни от t0, ни от состояния X (t0 ), ни от возможных уходов заявок из СМО на интервале (t0, t0 + ).

Далее, пусть X (t0 ) = n, n = 1,, а z1,…, zn – остаточные длительности обслуживания этих заявок. Тогда в силу отсутствия последействия у экспоненциального распределения длительности обслуживания заявок и их независимости как от потока, так и друг от друга, получим:

P {ни одна заявка не покинет СМО на (t0, t0 + )} = P {min( z1,…, zn ) } = P { zn } = e nµ = P { z1,…, zn } = P { z1 }. (3) Используя эти факты, легко убедиться в том, что случайный процесс X (t ), t 0, является однородным марковским процессом. Действительно, вероятностный прогноз будущего состояния X (t0 + ) при известном прошлом X ( s ), s t0, зависит лишь от настоящего состояния X (t0 ) и от длины интервала прогнозирования, но не зависит от t0, т. е. от расположения этого интервала.

При этом X (t ), t 0, – ступенчатый марковский процесс (СтМП) типа процесса размножения и гибели (ПРГ), так как за малый интервал времени (t0, t0 + ) с точностью до o ( ) возможно только сохранение «статус-кво» или переход в соседнее «снизу» или «сверху» состояние.

Обозначая функцию Хевисайда 0, x 0, u ( x) = 1, x 0, получим следующие вероятности переходов за интервал длины :

pn,n () := P { X (t0 + ) = n | X (t0 ) = n} = = P {за (t0, t0 + ) не поступила ни одна заявка и не освободилась ни одна линия|X (t0 ) = n} = e u ( n ) e nµ = = [1 u ( n ) + o ( )] [1 nµ + o( )] = = 1 u ( n) nµ + o( ), n = 0, ;

(4а) pn,n1() := P { X (t0 + ) = n 1| X (t0 ) = n} = = P {за (t0, t0 + ) не поступила ни одна заявка и освободилась одна из n занятых линий|X (t0 ) = n} = ( 1n )(1 eµ ) e(n1)µ = nµ + o(), = e n = 1, ;

(4б) pn,n+1() := P { X (t0 + ) = n + 1| X (t0 ) = n} = = P {за (t0, t0 + ) поступила одна заявка и не освободилась ни одна линия|X (t0 ) = n} = ( ) = 1 e e nµ = + o(), n = 0, ;

(4в) m n 2 n, m = 0, pn,m ( ) =,,. (4г) Из формул (4) следует, что при n = 0, интенсивности потоков занятия и освобождения линий имеют следующий вид:

an,n 1 = µn = nµ an,n +1 = n = u ( n) ;

;

an := an,n = u ( n) + nµ ;

(2.5) mn an, m =, т.е. X (t ), t 0, является ПРГ (рисунок 16).

В силу формул (2), (3) и (5) длительность n «сидения» в состоянии n имеет экспоненциальное распределение со средним значением 1 an :

P { n t } = e ( u ( n)+ nµ )t, t 0, n = 0,.

µ µ (n 1) µ (n + 1) µ ( 1) µ 2µ nµ MM µ Рисунок 16 – Диаграмма интенсивностей переходов для СМО Следовательно, моментами выхода из состояния n управляет пуассоновский поток с интенсивностью an, а самими переходами в соседние снизу или сверху состояния управляют соответственно переходные вероятности nµ qn,n1 = qn,n+1 = + nµ, n = 1, ;

+ nµ, n = 0, 1 ;

(6а) причем qn,n = qn,m = 0 m n 2 n, m = 0,,,. (6б) Формулы (6) физически очевидны и поясняют смысл условия 0, µ.

Таким образом, мы показали, что функционирование полнодоступного пучка из линий с явными потерями в стационарном режиме можно описать с помощью ПРГ X (t ), t 0 с J = {0,1,…,} пространством состояний, трехдиагональной матрицей интенсивностей переходов A (5) и двухдиагональной стохастической матрицей Q (2.6).

Упражнение 1. Запишите формулы (5) в виде матрицы A, а (6) – в виде матрицы Q.

Распределение и первая формула Эрланга P { X = n} =: pn n = 0, T Искомое равновесное распределение p = ( p0,…, p ), где, для ПРГ, T T с матрицей A (5) удовлетворяет системе уравнений глобального баланса (СУГБ) p A = 0, которую можно записать в виде:

p0 + µ p1 = 0, pn1 ( + nµ ) pn + (n + 1) µ pn+1 = 0, n = 1, 1, (7) p 1 µ p = 0.

Суммируя теперь уравнения (7) от нулевого до ( n 1) -го включительно, получим следующую систему уравнений локального баланса (СУЛБ) pn1 = nµ pn, n = 1,. (8) Физическую интерпретацию (8) можно дать с помощью рис. 16.: левая часть – это взвешенный поток интенсивностей переходов от состояния ( n 1) к состоянию n, а правая часть - в обратном направлении.

pn = Обозначая = µ, 0, и используя нормировочное условие, получим из n = (8):

n n!

pn =: pn ( ) = m m !, n = 0,.

m =0 (9) Для простоты вычислений в дальнейшем будем полагать, что 1, n = 0, pn (0) = = u (1 n) 0, n = 1,, n = 0,.

Распределение (9) числа занятых линий полнодоступного пучка называется первым распределением Эрланга.

Важная для проектирования реальных систем связи величина p ( ) является вероятностью блокировок предложенного потока или вероятностью потерь по времени, ее обычно обозначают E ( ) := ! m m!, 0 m =0 (10) и называют первой формулой Эрланга или B-формулой Эрланга. Эта формула и другие характеристики полнодоступного пучка неоднократно табулировалась1, а сама модель Эрланга уже почти столетие широко применяется при проектировании телекоммуникационных систем и сетей различных поколений, включая самые современные.

Легко видеть, что справедлива следующая Теорема 1. Если, то при 0 n pn ( ) e n !, n = 0,1….

(11) pn ( ), n = 0,, (9) при Следовательно, распределение является усеченным распределением Пуассона с параметром и, в принципе, может быть получено с помощью таблицы распределения Пуассона. Заметим, что поскольку после Второй мировой войны распределением Эрланга стали называть распределение суммы n независимых случайных величин с одинаковым экспоненциальным распределением каждая, то в настоящее время (9) называют также усеченным распределением Пуассона.

Поскольку вероятность блокировок E ( ) широко используется на практике, а с ростом величины при 1 и ! очень быстро возрастают, то при вычислении по формуле (10) могут произойти как переполнение, так и исчезновение величины !. Поэтому вычисление E ( ) производится с помощью следующей рекуррентной процедуры:

E 1 ( ) E ( ) = E0 ( ) = 1, + E 1 ( ), = 1, 2,… (12) m m!

Действительно, поделив числитель и знаменатель дроби в формуле (10) на m=0, получаем:

Башарин Г.П. Таблицы вероятностей и средних квадратических отклонений потерь на полнодоступном пучке линий. – М.: Изд-во АН СССР, 1962. – 128 с.

1 m m! + ! m =0 E 1 ( ) E ( ) = ! m = 1 1 m 1 + E 1 ( ) m =0 m ! m =0 m !

.

I ( ) = [ E ( ) ] Обозначив, получим из (12) следующую рекуррентную формулу:

I ( ) = 1 + I ( ) 1, = 1, 2,… I0 ( ) = 1, (13) Обе рекуррентные процедуры дают устойчивый результат, но каждая из них имеет свою предпочтительную область изменения параметров и.

Упражнение 2. К АТС подключено 10 абонентов, каждый из которых создает нагрузку в 0,04 Эрл, причем 10% вызовов являются междугородными. Требуется найти количество каналов для междугородных вызовов при условии, что вероятность их блокировки не превысит 1%.

Решение. Полагая N = 10, получим для интенсивностей 1 общей и 2 междугородной нагрузки на АТС следующие значения:

1 = 104 0, 04 = 400 Эрл;

2 = 0,11 = 40 Эрл.

Согласно формуле (12) и условию задачи 2 E 1 ( 2 ) 0, + 2 E 1 ( 2 ).

Отсюда сразу следует, что 99 2 E 1 ( 2 ).

Используя таблицы для E ( ) или рекуррентную процедуру (12), получим, что при 2 = условие задачи будет выполнено, если 53 канала.

E ( ) [1 E ( ) ] = Упражнение 3. Докажите, что E 1 ( ).

Тема 2.2. Определение и виды нагрузки Определение 1. Обслуживаемой (принятой) некоторой СМО в момент времени t мгновенной нагрузкой называется случайный процесс X (t ), t 0, представляющий собой число одновременно обслуживаемых в этой системе заявок или число одновременно занятых ресурсов (приборов).

Определение 2. Интенсивностью обслуживаемой в момент t системой S мгновенной нагрузки называется среднее число занятых приборов (единиц ресурсов) этой системы, т. е.

E X (t ;

S ) 0, t 0.

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

Если процесс X (t ) стационарный и эргодический, то можно показать, что EX (t ) EX = h t, (13) где – средняя интенсивность принятого к обслуживанию потока, h – средняя длительность обслуживания. Поэтому h – средняя интенсивность нагрузки на S, которую в приложениях для краткости часто называют просто «нагрузка.

Примечание. Если каждая заявка при обслуживании занимает не единицу рассматриваемого ед.ресурса ресурса, а b заявку, то это учитывается в начале или после расчетов. В этой главе все заявки принадлежат к одному типу (моносервисные СМО), так что можно считать b = 1. Если же на СМО поступают потоки заявок K типов (мультисервисные СМО) с независимыми пуассоновскими распределениями и независимыми экспоненциальными длительностями обслуживания, то наряду с 1, …, K, µ1, …, µ K b1, …, bK.

параметрами приходится вводить и параметры Для мультисервисной полнодоступной -линейной СМО с такой пуассоновско-экспоненциальной нагрузкой и потерями при блокировке удобно использовать обозначение M M, b µ. (14) MM µ Проиллюстрируем определение 2 с помощью СМО. Пусть случайная величина (СВ) X имеет первое распределение Эрланга (9), т. е. распределение СВ X является равновесным распределением для соответствующего СтМП и описывает функционирование этой СМО в стационарном (равновесном) режиме. Тогда из СУЛБ (8) получим EX = npn ( ) = p ( ) = [1 E ( )] µ n=1 n n =1. (15) В силу определения 2 эту величину естественно принять за интенсивность обслуженной нагрузки:

Yобсл = [1 E ( )]. (16) и любого, 0, интенсивность предложенной нагрузки равна Для = интенсивности обслуженной:

Yпредл = pn1 ( ) = npn ( ) = = Yобсл n =1 n=1. (17) Очевидно, что при и отсутствии мест для ожидания часть предложенной (поступающей) нагрузки теряется. Пусть Yпот – интенсивность потерянной нагрузки. Тогда Yпредл = Yобсл + Yпот, (18) причем физически очевидно, что это соотношение справедливо при очень широких предположениях.

Для первой модели Эрланга Yпот = Yпредл E ( ). (19) Тема 2.3. О статистической оценке характеристик нагрузки. Работа На практике обычно измеряется обслуживаемая системой S с емкостью нагрузка на интервале [t0, t0 + T ). Пусть n(t ), t [t0, t0 + T ) X (t ), t 0, некоторая реализация ПРГ описывающего мгновенную обслуживаемую нагрузку в рассматриваемой системе. Величину t0 +T Z (t0, t0 + T ) := n(t )dt t (20) будем называть работой по обслуживанию заявок, выполняемой системой S на рассматриваемом интервале. Величина работы равна общей продолжительности занятий линий (каналов, входов, выходов или других обслуживающих устройств) системы S на [t0, t0 + T ) и измеряется в эрланг часах (Эрл-ч), эрланг-минутах (Эрл-мин), эрланг-секундах (Эрл-с) и т. д., причем в нашей стране раньше эрланг-час назывался «часозанятие». Работу в 1 Эрл-ч выполняет линия, непрерывно занятая в течение 1 часа;

2 Эрл-ч – 2 линии, непрерывно занятые в течение 1 часа, или 1 линия, но занятая непрерывно в течение 2 часов.

1 мин.

h= = 3 заявку заявок = 15 µ Пример 1. Пусть. Тогда интенсивность предложенной мин., Yпредл = = 45 Эрл нагрузки равна. Объем нагрузки, или работы за 4 часа составляет 4 ч 45 Эрл = 180 Эрл-ч, за 30 минут – 0, 5 ч 45 Эрл = 22, 5 Эрл-ч.

Упражнение 4. Приведите несколько примеров подсчета объема нагрузки, аналогичных примеру 1, когда за единицу времени естественно принять минуты, секунды и миллисекунды.

Если работу системы S на интервале [t0, t0 + T ) представить графически как функцию от t, то получим быстро возрастающую ломаную линию, вершины которой соответствуют моментам изменения мгновенной нагрузки n(t ).

В силу (20) работу, выполняемую системой S на непересекающихся отрезках времени, можно суммировать, т. е. работа системы S обладает свойством аддитивности.

Средняя величина работы (20) в единицу времени t +T n(t )dt Y (t0, t0 + T ) := Tt 0 (21) служит статистической оценкой для среднего значения интенсивности обслуживаемой нагрузки (21), причем EX = h Y (t0, t0 + T ). (22) На рисунке 17 приводится пример результатов измерения величины n(t ) обслуживаемой нагрузки на пяти последовательных интервалах длиною T каждый (кривая C ). Кроме того, приводятся (кривая D ) результаты измерения на каждом из этих интервалов величины 1 iT n(t )dt Yi = T (i 1)T, i = 1, 5. (23) Величина Y служит оценкой среднего числа занятых линий и, тем самым, оценкой среднего значения интенсивности обслуживаемой нагрузки на интервале [(i 1)T, iT ). Аналогичным образом можно оценить дисперсию и другие характеристики обслуживаемой нагрузки.

C D T Рисунок 17 – Мгновенная обслуживаемая нагрузка n(t ) На выбор T влияют многие факторы, включая специфику и параметры самой системы S, применяемой аппаратуры измерений и требуемую точность статистических оценок. Исторически в телефонии обычно принимают T = 1 час и измеряют обслуживаемую нагрузку в течение суток, в разные дни недели – рабочие, выходные и праздничные – в течение года. На основе этих измерений можно определить часы наибольшей нагрузки (ЧНН) для различных суток в течение года. При проектировании или модернизации современных телекоммуникационных систем требуемые характеристики нагрузки могут также рассчитываться на основе измерений типа (23) с соответствующим T, после чего определяется период времени наибольшей нагрузки (ПНН) в интересующем оператора временном интервале. Применяется также и экспертная оценка характеристик предполагаемых предложенной и обслуженной нагрузок.

Тема 2.4. О порядке занятия свободных приборов MM | µ Рассмотрим СМО при случайном и упорядоченном занятии (искании) Yобсл ( i ) =: aiуп уп Yобсл ( i ) =: aiсл сл, i = 1,, – среднее использование свободных приборов и пусть и (загрузка) прибора № i, или интенсивность обслуженной им нагрузки, в первом и втором случаях соответственно. Очевидно, что в силу (22) (1 E ( ) ) Yобсл aiсл = =, i = 1,.

(24) На рисунке 18 видно, что при упорядоченном искании на прибор № i поступает нагрузка, потерянная на приборе № (i 1), с интенсивностью Ei 1 ( ), а на прибор № (i + 1) – потерянная на приборе № i с нтенсивностью Ei ( ). Поэтому интенсивность обслуженной прибором № i нагрузки равна aiуп = ( Ei 1 ( ) Ei ( ) ) i = 1,,. (25) a уп = [1 E1 ( )] Поскольку E0 ( ) = 1, то 1. Так как интенсивность обслуженной приборами нагрузки равна сумме интенсивностей нагрузок, обслуженных каждым из приборов, то в силу (24) и (25) Yобсл = aiуп = Ei 1 ( ) Ei ( ) = [1 E ( )] = Yобсл = Yобсл уп сл i =1 n =1 i =1. (26) E ( ) E2 ( ) Ei 2 ( ) Ei ( ) E 2 ( ) E1 ( ) Ei 1 ( ) 1 E 1 ( ) i 1 i aiуп1 = [ Ei 2 ( ) Ei 1 ( )] a1уп = [1 E1 ( ) ] aуп1 = [ E 2 ( ) E 1 ( )] aуп = [ E 1 ( ) E ( ) ] aiуп = [ Ei 1 ( ) Ei ( )] уп a2 = [ E1 ( ) E2 ( )] Рисунок 18 – Схема расчета пучка из упорядоченных приборов Таким образом, как вероятность потерь, так и суммарная интенсивность обслуженной пучком из приборов нагрузка не зависит от вида искания свободных приборов, а загрузка i прибора – зависит.

Эта задача возникла в 1930-е годы при планировании работы искателей свободных выходов или свободных линий в декадно-шаговых АТС. Аналогичные задачи возникают в координатных и электронных АТС, а также в других системах.

Тема 2.5. Вторая модель Эрланга с конечной очередью и с сохранением места в очереди Постановка задачи Рассмотрим -линейную СМО с r местами для ожидания, на которую поступает ПП однородных заявок с постоянной интенсивностью, а длительности обслуживания заявок независимы и имеют идентичное экспоненциальное распределение с интенсивностью µ :

MM 1 1 r µ. (27) Алгоритм обслуживания с ожиданием состоит в том, что если в момент поступления заявки есть свободные линии, то заявка занимает одну из них в установленном порядке. Если же все линий заняты, то заявка занимает комплект ожидания (устройство или зону в памяти), т. е.

принимается в очередь до получения доступа к одной из освободившихся линий пучка. При этом может быть рассмотрен как тот случай, когда заявка освобождает место в очереди (комплект ожидания) после начала обслуживания, так и тот, когда заявка удерживает за собой место в очереди до завершения обслуживания. В первом случае емкость системы R := + r, а во втором R = r.

Для простоты мы будем рассматривать лишь первый случай.

Порядок выбора заявок из очереди на обслуживание при появлении свободной линии может быть различным: в порядке поступления (first come – first served, FCFS), в обратном порядке (last come – first served, LCFS), случайно (Random) и др. Если с точки зрения проектировщика или оператора вероятность блокировки p + r столь мала, что ею можно пренебречь, то анализируют самый простой случай r =, когда блокировок нет. При r заявка, заставшая в СМО еще обслуживаемых и r ожидающих заявок, т. е. полностью занятую систему, получает отказ и теряется, не оказывая дальнейшего влияния на поступающий поток (рисунок 19).

(1 p + r ) p +r MM r µ, где p + r – вероятность блокировки Рисунок 19 – СМО Эту вторую модель Эрланга в теории телетрафика называют также системой Эрланга с неявными потерями, поскольку затянувшееся ожидание часто приводит к отказу ожидающей заявки (абонента) от требуемого соединения или к повторению вызовов, что значительно усложняет модель и соответствующие расчеты.

Второе распределение Эрланга Пусть R := + r – общая емкость СМО;

X (t ), t 0, – случайный процесс, описывающий общее число заявок в СМО в момент t ;

J = {0,1,…,, + 1,…, R} – пространство состояний системы. В силу сделанных предположений о пуассоновском характере входящего потока заявок и экспоненциальном распределении длительности их обслуживания, процесс X (t ), t 0, является ступенчатым марковским типа ПРГ с интенсивностями переходов из состояния n соответственно «вверх», «вниз» и сохранения «статус-кво» (n = 0, R ) an,n +1 =: n = u ( R n), an,n1 =: µn = µ min( n, ), (28) an,n = n µ n.

Физический смысл интенсивностей переходов «вверх» и «вниз» хорошо поясняет рисунок 20.

+r µ µ µ (n + 1) µ 2µ nµ µ MM r µ Рисунок 20 – Диаграмма интенсивностей переходов для СМО Действительно, интенсивность n перехода «вверх» в состоянии n = 0, R 1 является постоянной и равна интенсивности предложенного потока, а в состоянии R все заявки предложенного потока блокируются, так что интенсивность n принятого потока равна 0.

Интенсивность µn переходов «вниз» в состоянии n = 0, равна nµ, а затем при n = + 1, R интенсивность µn остается постоянной и равна µ.

В силу (29) матрица A интенсивностей переходов для рассматриваемого ПРГ X (t ), t 0, является трехдиагональной и имеет вид, изображенный в таблице 15.

MM r µ Таблица 15 – Матрица интенсивностей переходов для СМО +1 + r n 0 A R 0 µ µ 1 n 1 nµ n ( n + 1) µ n +1 1 µ µ µ +1 0 µ + r 1 µ R µ T Искомое равновесное распределение p = ( p0,…, pR ) удовлетворяет СУГБ pT A = 0T, которая, в силу (29) и вида матрицы A, принимает следующий вид:

p0 + µ p1 = 0 ;

pn1 ( + nµ ) pn + (n + 1) µ pn+1 = 0, n = 1, 1 ;

(30) pn1 ( + µ ) pn + vµ pn+1 = 0, n =, + r 1 ;

pR 1 µ pR = 0.

Упражнение 5. Выведите уравнения (30) при помощи таблице 15.

Используя функцию Хевисайда, запишем СУГБ (30) более компактно:

pn1u (n) [ u ( R n) + µ min(n, )] pn + + µ min( n + 1, ) pn +1u ( R n) = 0, n = 0, R. (30а) Суммируя теперь уравнения (30) от нулевого до ( n 1) -го включительно, получим следующую СУЛБ:

pn1 = nµ pn, n = 1, ;

pn1 = µ pn, n =, R, (31) или, что эквивалентно, pn1 = min(n, ) µ pn, n = 1, R. (31а) Физическую интерпретацию СУЛБ можно дать с помощью рисунка 21: левая часть – это взвешенный поток интенсивностей переходов от состояния ( n 1) к состоянию n, а правая часть – в обратном направлении. Очевидно, что эта интерпретация справедлива как при n = 1,, так и при n = + 1, R.

pn = pn Обозначая = µ, запишем рекуррентное соотношение (31а) в виде min(n, ), n = 1, R. Поэтому n p, n = 0, ;

n! pn = n n p0, n =, R.

p = ! n (32) Из условия нормировки следует, что n 1 1 n R r m 1 n = = + + = ! m =0 p0 n=0 n ! ! n= n!

n =0 (33) r + 1 n 1 = + ! n =0 n !

.

Теорема 2. Равновесное распределение числа заявок в системе Эрланга с ожиданием MM r µ при r и любом определяется формулами (3.6)–(3.7). При r = R = эти формулы справедливы, если выполняется условие, (34) причем формула (33) упрощается:

1 1 n = + p0 n=0 n ! !. (34а) Распределение (32) называют вторым распределением Эрланга.

MM 1r µ Следствие 1. Для однолинейной системы массового обслуживания из (32)–(33) при r и любом получаем:

1 1 r + = pn = n p0, n = 0, R ;

p0 1. (35) Поэтому вероятность блокировки := pR = R 1 R+ 2. (36) При r = R = блокировки отсутствуют, но (36) справедливо, если 1, причем pn = n (1 ), n = 0,1,…. (37) Таким образом, при = 1 и r = второе распределение Эрланга является геометрическим с параметром 1.

Для проверки полученных результатов применим соотношение (32) к системе без мест для ожидания (r = 0, R = ) :

n n = pn = p n !, n = 0, ;

p0 n=0 n !. (38) Поскольку (38) совпадает с (32), то контроль выполняется, причем, как и следовало ожидать, первое распределение Эрланга является частным случаем второго.

Упражнение 6.

MM r µ при r и любом средняя длина очереди q Доказать, что в СМО 1) имеет вид r +1 r 1 + r ( r + 1) q = p.

= При получить формулу для q при r = и изучить скорость роста q при 2).

1 2 3) Рассмотреть несколько численных примеров при = 10, 10, 10.

Оценка интенсивности принятой нагрузки и вторая формула Эрланга Рассмотрим снова случайную величину X – число заявок в СМО, имеющую второе распределение Эрланга, и пусть случайная величина Y – число обслуживаемых, а случайная величина Z – число ожидающих заявок.

Тогда очевидно, что X, X, =: ( X ) + Z = 0, X Y = min( X, ),, (39) X =Y +Z. (40) Пусть := pR – вероятность блокировки, т. е. потерь по времени.

Теорема 3. При r и любом средняя интенсивность принятого потока равна средней интенсивности обслуженного потока, а при r = и равна интенсивности предложенного потока Доказательство. Суммируя уравнения локального баланса по n от 1 до R, получим:

R (1 ) = µ npn + pn n=1.

n = +1 (41) r Левая часть представляет собой интенсивность принятого при и предложенного при r = R =, = 0 потоков. Вместе с тем правая часть в обоих случаях представляет собой среднюю интенсивность обслуженного потока. Равенство (41) допускает еще одну полезную интерпретацию.

Следствие 2.

(1 ), r,, EY =, r =,. (42) Это означает, что среднее число занятых приборов равно средней интенсивности принятой при r и средней интенсивности предложенной при r = нагрузки. Поскольку EY, то (42) влечет Следствие 3.

(1 ). (43) Данное соотношение означает, что средняя интенсивность как принятой, так и предложенной нагрузки не превосходит число имеющихся в СМО обслуживающих приборов, что физически очевидно.

Рассмотрим теперь случайную величину – длительность ожидания заявкой начала обслуживания при r =,. Очевидно, что в силу формулы (43) n ! P { 0} = pn = p0 = 1 n ! n n= + ! n =0 n !. (44) В теории телетрафика формулу (44) называют второй формулой Эрланга или C-формулой Эрланга, поскольку ее можно интерпретировать как вероятность неявных потерь. Выразим теперь P { 0} через E ( ) – вероятность явных потерь в первой модели Эрланга. Поделив числитель и n n ! и произведя очевидные упрощения, получим:

знаменатель (44) на n = n ! n =0 n !

P { 0} = = 1 n n n=0 n ! ! n0 n !

+ = E ( ) E ( ) = = ( )[1 E ( )] + E ( ) [1 E ( )]. (44а) P { 0} как функции от и, в Эта формула позволяет вычислять значения требуемом диапазоне с помощью ранее полученных значений E ( ) или с использованием рекуррентных соотношений (32) для E ( ).

Тема 2.6. Модель Энгсета. Представление распределения вероятностей в виде биномиального распределения Описание модели Энгсета MM µ В первой модели Эрланга предложенный поток заявок является пуассоновским с постоянной интенсивностью поступления заявок, которая не зависит от числа обслуживаемых в этот момент в СМО заявок.

В модели Энгсета2 также рассматривается полнодоступный пучок линий без мест для N, N, ожидания, но вместо одного пуассоновского потока заявок рассматривается малоинтенсивных независимых источников заявок, каждый из которых может находиться в одном из двух состояний: «0» – свободен или «1» – занят сам и занимает одну из линий. Каждый из N источников в свободном состоянии может с интенсивностью сгенерировать одну заявку, которая мгновенно займет одну из свободных линий, если они имеются, а источник перейдет в состояние «1», либо предложенная источником заявка будет потеряна с вероятностью p занятия всех линий пучка, а источник останется в состоянии «0» (рисунок 21 и рисунок 22).

T. Engset (1869–1943) – норвежский математик, один из основателей теории телетрафика.

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

состояние источника 1 1 2 блокировка пост уход пост уход заявки заявки 1 Ei = Ei =, i = 1, 2,… µ, Рисунок 21 – Смена состояний отдельного источника, p (1 p ) (1 p ) N p MM N, µ, где p – вероятность блокировок при N Рисунок 22 – СМО Длительность пребывания источника в состоянии «1» совпадает с длительностью занятия его заявкой линии и имеет экспоненциальное распределение со средним значением 1 µ, т. е. с интенсивностью µ завершения обслуживания и перехода источника из состояния «1» в состояние «0». Отметим, что на практике чаще всего рассматривается случай µ.

Построение процесса размножения и гибели Легко убедиться, что функционирование модели Энгсета без мест для ожидания описывается посредством ПРГ X (t ), t 0, параметры которого определяются числом j занятых линий в j J = {0,1,…, min( N, )} J = {0,1,…,}. Если N, то системе, причем, т. е. пространство состояний для модели Энгсета при r = 0 совпадает с пространством состояний для модели Эрланга при r = 0. Модель Энгсета с местами для ожидания при условии N + r мы рассматривать не будем, рекомендуя заинтересованному читателю рассмотреть ее самостоятельно.

µ Если j из линий заняты, то интенсивность j освобождения одной из них, как и для первой модели Эрланга, равна µ j = jµ, j = 0,. (45) Если j из линий заняты, то N j источников нагрузки свободны, так что суммарная j предложенного потока заявок зависит от j, совпадает с интенсивностью j интенсивность принятого потока при j = 0, 1 и равна интенсивности предложенного, но заблокированного потока при N (рисунок 23):

j = ( N j ), j = 0, ;

j = j, j = 0, 1.

(46) Отметим, что при N = в состоянии нет свободных источников, так что = 0, блокировки отсутствуют, потери по вызовам равны 0, хотя вероятность занятия всех линий положительна. Этот факт иллюстрирует принципиальное различие моделей Эрланга и Энгсета.

( N j + 2) ( N j + 1) ( N j ) ( N + 2) ( N + 1) ( N 1) N 1 j 1 j µ ( j 1) µ ( j + 1) µ ( 1) µ jµ µ p MM N, µ, где p – Рисунок 23 – Диаграмма интенсивностей переходов для СМО вероятность блокировок при N j Заметим теперь, что интенсивность предложенного пуассоновского потока заявок в модели Эрланга не зависит от ее состояния j и равна при j = 0,, причем j совпадает с интенсивностью принятого потока при j = 0, 1 и с интенсивностью заблокированного потока при j =. Хотя в модели Энгсета разделение предложенного потока заявок на принятый и заблокированный потоки происходит аналогичным образом, но интенсивность этих потоков в силу (46) зависит от j, т. е. от состояния СМО. Поэтому предложенный пуассоновский поток с постоянной интенсивностью, не зависящей от параметров СМО, называют еще чисто случайным, N, а предложенный поток с параметрами, интенсивность которого зависит еще от параметров и µ модели Энгсета, называют потоком Энгсета, или квазислучайным.

Если распределение длительности обслуживания вызовов является экспоненциальным, то создаваемая пуассоновским потоком нагрузка называется пуассоновской нагрузкой первого рода, или чисто случайной, а потоком Энгсета – пуассоновской нагрузкой второго рода, или квазислучайной.

В классической телефонии обычно применяется модель Энгсета при N порядка нескольких единиц, а при N порядка 10 и более единиц применяют модель Эрланга с = N.

Распределение Энгсета числа занятых линий для случая N В силу (32)–(33) матрица интенсивностей переходов для рассматриваемого ПРГ X (t ), t имеет вид, представленный в таблице 16.

T Равновесное распределение p = ( p0,…, p ) удовлетворяет СУГБ pT A = 0T, (46) которая, в силу вида матрицы A, принимает вид:

p0 N + µ p1 = 0, ( N j + 1) p j 1 [( N j ) + j µ ] p j + ( j + 1) µ p j +1 = 0 j = 1,,, (47) ( N + 1) p 1 µ p = 0.

Поскольку матрица A трехдиагональная, а сумма элементов в каждой строке равна 0, то суммируя уравнения (47) от нулевого до ( j 1) -го включительно, получим систему уравнений локального баланса ( N j + 1) p j 1 = j µ p j, j = 1,. (48) Физическую интерпретацию этого рекуррентного соотношения можно дать с помощью рисунка 23: левая часть (48) – это взвешенный поток интенсивностей перехода из состояния j 1 в состояние j, а правая часть – в обратном направлении. Очевидно, что эта интерпретация справедлива при любом j, j = 1,.

Пусть теперь 1 := µ – интенсивность нагрузки от одного свободного источника. Тогда (48) влечет N j +1 ( N j + 1)( N j + 2) ( N 1) N 1j p 1 p j 1 =... = pj =, j = 1,.

j!

j MM N, µ Таблица 16. – Матрица интенсивностей переходов для СМО j 0 A N 0 N µ ( N 1) µ 1 0 ( N j + 1) j 1 ( N j ) j µ j ( j + 1) µ j +1 0 ( N + 1) ( 1) µ ( N + 1) 1 µ µ Записывая эту формулу с помощью сочетаний и используя нормировочное условие pj = ;

N, j =0, получим распределение Энгсета с параметрами :

N j j p j ( ;

N, 1 ) := p j = N m 1m m =0, j = 0,, N. (49) pj – вероятность того, что в СМО Энгсета занято j каналов из, т. е. при большом Здесь pj T состоятельной статистической оценкой может служить доля времени пребывания СМО в состоянии j на интервале (t0, t0 + T ). Поэтому p при N называют также вероятностью блокировки по времени в СМО Энгсета.

1;

1, Рассмотрим теперь систему Энгсета при = N = 1, т. е. с параметрами. Для нее в силу (49) вероятность занятия единственного канала p1 (1;

1, 1 ) = =:

1 + 1, (50а) а вероятность того, что канал свободен p0 (1;

1, 1 ) = =: 1 + 1. (50б) Отсюда следует, что при 0 1 = 1. (51) N Подставляя теперь (51) в (49) и умножая числитель и знаменатель на (1 ), получим усеченное биномиальное распределение:

N j N j j (1 ) p j = N m m (1 ) N m m =0, j = 0,. (51а) Физический смысл этих результатов становится более ясным при сопоставлении со случаем N.

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

J = {0,1,…,} Если в модели Энгсета N, а пространство состояний системы, то в этом J = {0,1,…, N } разделе N, так что. Оба эти случая охватывает пространство состояний J = {0,1,…, min(, N )} и, повторяя рассуждения предыдущего раздела с заменой на min(, N ), получим следующую формулу для вероятности числа занятых каналов в стационарном режиме:

N j j p j ( ;

N, 1 ) =: p j = min(, N ) N m 1m m =0, j = 0, min(, N ). (52) При N (2.40) совпадает с распределением Энгсета (49), которое в силу (51а) является N, (52) является одновременно а при усеченным биномиальным распределением, биномиальным распределением с параметрами N,. Действительно, справедлива следующая MM 1 N N, µ Теорема 4. Для СМО равновесное распределение числа X занятых каналов является биномиальным с числом N опытов и вероятностью успеха в каждом из них.

Доказательство. Утверждение теоремы сразу следует из формул (50) и (51):

N j N j j 1 j N = N = j (1 ) N j P { X = j} := p j = N N j (1 + 1 ) m 1m m =0, j = 0, N. (53) Этот интересный результат можно пояснить с помощью следующих элементарных рассуждений. Разделим все N источников на две группы – занятые и свободные. Вероятность того, что некоторый источник занят, равна, причем она не зависит от состояния всех других источников, поскольку блокировки отсутствуют и любой поступающей заявке предоставляется свободный канал. Поэтому распределение числа занятых источников совпадает с распределением числа занятых каналов и описывается биномиальным распределением Bi( N, ).

Легко показать, что среднее значение и дисперсия числа X занятых линий соответственно равны EX = N, DX = N (1 ). (54) Рассмотрим теперь предельный случай, когда число N источников нагрузки и число приборов, N, неограниченно возрастают, а интенсивность каждого из источников стремится к 0, причем N = lim N, 0. (55) Отметим, что при этом 0 = 1 0 1 = µ 1 + 1, N µ N N = N =:

= µ + µ 1+ µ. (55а) Как и в первой модели Эрланга, здесь – интенсивность предложенной нагрузки для бесконечнолинейного пучка, а после предельного перехода распределение Энгсета, как и первое распределение Эрланга, становится распределением Пуассона с параметром :

j P { X = j} = p j = e j j !, j = 0,1,…. (56) N 1 = µ Вместе с тем предельный переход (55а) в распределении Энгсета (56) в силу дает распределение Эрланга.

Тема 2.7. Связь между вероятностями блокировок по времени, по вызовам и по нагрузке В теории телетрафика часто рассматривают блокировки по времени и по вызовам, поскольку вторые проще измерять экспериментально. Поэтому остановимся вкратце на этом вопросе на примере СМО Энгсета при N.

Вероятность блокировки по времени в силу (50) имеет вид:

N E, N ( 1 ) = p = N j j j =0. (58) За определение вероятности блокировки по вызовам в силу (46) и (50) естественно принять величину Ср. число заблокир. заявок на [t0, t0 + T ) B, N ( 1 ) := lim = T Ср. число предл. заявок на [t0, t0 + T ) N N ( N ) 1 ( N ) Tp = = lim = N j N 1 j T ( N j ) Tp j ( N j ) j 1 j j =0 j =0 j =0. (59) ( N j ) N N = N j j.

Здесь мы воспользовались соотношением Таким образом, B, N ( 1 ) = E, N 1 ( 1 ). (60) Физическая интерпретация этого равенства состоит в том, что вероятность отвергнуть вызов от одного случайно выбранного источника равна вероятности того, что остальные N 1 источников заняли все каналов.

Так как с ростом N растут и потери по времени, то очевидно, что B, N ( 1 ) = E, N 1 ( 1 ) E, N ( 1 ). (61) B, N ( 1 ) E, N ( 1 ) Неравенство можно также легко как непосредственно доказать аналитически, так и интерпретировать физически.


Рассмотрим теперь потери по нагрузке. Поскольку 1 = µ – интенсивность нагрузки от одного свободного источника, то величины a j := ( N j ) 1 j = 0,,, (62) ( N j ) 1, j = 0, 1, y j := 0, j =, (63) представляют собой соответственно интенсивности предложенной и принятой нагрузки в j = 0,. Очевидно, что интенсивность предложенной нагрузки совпадает с j, состоянии интенсивностью принятой (обслуженной) нагрузки при j = 0, 1 и с интенсивностью потерянной нагрузки при j =.

Рассмотрим теперь три случайные величины X, A и Y :

{ }{ } P { X = j} = P A = a j =P Y = y j = p j j = 0,,, с распределением Энгсета и запишем СУЛБ в виде y j 1 p j 1 = jp j, j = 1,. (64) Отсюда сразу следует равенство средних значений Y=X, (65) причем факт равенства интенсивностей принятой и обслуженной нагрузок физически также очевиден. Вычислим теперь средние значения (65) с помощью (50):

N Y = X = jp j = p0 j 1j = j =1 j j = N 1 1 N j = N 1 p0 1 = N 1 p0 s s j j =1 s =0. (66) Вероятностью блокировки по нагрузке назовем отношение интенсивности блокированной к интенсивности поступающей нагрузки:

( N ) 1 p A Y C, N ( 1 ) = = B, N ( 1 ) = A ( N j ) 1 p j j =0. (67) Таким образом, справедливо соотношение C, N ( 1 ) = B, N ( 1 ) = E, N 1 ( 1 ) E, N ( 1 ). (68) Повторяя теперь рассуждения этого раздела для первой модели Эрланга, получим, что для нее вероятности блокировок по времени, по вызовам и по нагрузке совпадают:

E ( ) = B ( ) = C ( ). (69) Это утверждение следует также и из (69), когда число N источников нагрузки растет, а интенсивность 1 каждого из них в свободном состоянии уменьшается, так что выполняются условия (37)–(37а).

Практические рекомендации о том, когда предложенную пуассоновскую нагрузку второго рода с параметрами N, 1 можно аппроксимировать пуассоновской нагрузкой первого рода с параметром можно найти в учебниках по инженерной ТТ.

Тема 3.1. Модель сети с одноадресными соединениями В этой главе предложен подход к анализу сети с многоадресной передачей данных – мультивещанием. Применение принципа «точка - много точек» при установлении соединений позволяет более эффективно использовать ресурсы сети. Действительно, при традиционных способах передачи информации для каждого пользователя устанавливается соединение «точка точка» (англ. unicast). Это приводит к тому, что по общим для нескольких соединений звеньям сети передается несколько копий одной и той же информации. При мультивещании пользователи совместно используют пропускную способность некоторых звеньев сети, поскольку дублирования информации на этих звеньях не происходит. Этот основной принцип мультивещания проиллюстрирован на рисунке 24.

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

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

При динамическом мультивещании источник начинает передачу информации, соответствующей содержанию услуги, по запросу пользователя. Момент окончания предоставления услуги также определяется пользователем. Примером динамического мультивещания служит теле и радиовещание в мультисервисной сети.

Постановка задачи Будем рассматривать сеть связи произвольной топологии, состоящую из некоторого числа узлов, соединенных звеньями. Пусть L – общее число звеньев сети, а L = {1, 2,..., L} – множество всех звеньев, занумерованных произвольным образом. Обозначим Cl емкость l-звена. Емкость соответствует пропускной способности звена, выраженной в условных единицах измерения (единицах емкости). Величина единицы емкости выбирается в зависимости от конкретной задачи и требований соединений к ШПП. Часто бывает удобно выбрать в качестве единицы емкости наименьшее из таких требований. Если, например, принять за единицу емкости 8 кбит/с, то емкость канала с пропускной способностью 622 Мбит/с составит 77750 единиц.

Для передачи информационных потоков между узлами сети могут быть установлены двухточечные соединения различных классов. Каждый класс соединений характеризуется двумя параметрами: маршрутом, то есть множеством звеньев сети, через которые устанавливается соединение, и требованием к емкости звеньев маршрута. Обозначим K = {1, 2,..., K } множество всех классов соединений сети, и пусть Lk L – маршрут, а d k – требование к емкости всех звеньев маршрута соединения k-класса.

Заметим, что рассматриваемая модель является наиболее естественным с точки зрения приложений частным случаем базовой модели мультисервисной сети с фиксированной маршрутизацией, которую использовал в своих работах Ф. Келли. Базовая модель мультисервисной сети в этих работах отличается от рассматриваемой здесь модели лишь тем, что требования ( d kl )kK,lL соединений к емкости звеньев задаются матрицей, и, следовательно, число занятых одним соединением единиц емкости может различаться на разных звеньях маршрута.

На рисунке 25 представлен пример сети рассматриваемого типа. Здесь сеть состоит из трех звеньев – 1-го, 2-го и 3-го, – имеющих емкость 30, 35 и 40 единиц соответственно, то есть L = {1, 2, 3}, C1 = 30, C2 = 35 и C3 = 40. Между любыми двумя соответствующими висячим вершинам изображающего сеть графа узлами могут быть установлены соединения, требующие 1 или передаточных единиц. Таким образом, мы получаем 6 классов соединений, то есть K = {1, 2,..., 6}, параметры которых указаны на рисунке. Например, соединения класса 1 устанавливаются через звенья 1 и 2 и занимают 1 единицу емкости звена, то есть L1 = {1, 2} и d1 = 1.

Рисунок 25 – Пример сети с одноадресными соединениями Введем теперь нагрузочные параметры модели. Пусть в систему поступают запросы пользователей на установление соединения того или иного класса. Будем считать, что запросы на установление соединения k-класса образуют пуассоновский поток интенсивности k, а продолжительности таких соединений независимы в совокупности, не зависят от моментов установления соединения и одинаково распределены по произвольному закону со средним 1 k.

Обозначим через ak = k k интенсивность предложенной нагрузки, чтобы упростить дальнейшие выкладки.

По запросу пользователя будет установлено соединение требуемого класса, если на момент прихода запроса на всех звеньях соответствующего маршрута окажется необходимое число свободных единиц емкости звена. В этом случае требуемое число единиц ресурса предоставляется данному соединению до его разъединения. Если же хотя бы на одном из звеньев маршрута требуемого числа свободных единиц ресурса не окажется, то происходит блокировка запроса и запрос теряется. Обратимся вновь к рисунку 25: если, например, в момент поступления запроса на установление соединения класса 4 ( d 4 = 5, L4 = {1, 2} ) в нашей сети имеется пять активных соединений класса 6 ( d6 = 5, L6 = {1, 3} ) и одно соединение класса 1 ( d1 = 1, L1 = {1, 2} ), запрос будет заблокирован, так как на звене 1 ( C1 = 30 ) окажется свободно лишь 4 единицы емкости (30 – 55 – 11 = 4), что меньше требуемых пяти.

Стационарное распределение вероятностей состояний Пусть емкости всех звеньев сети неограниченны: Cl =, l L. В этом случае запрос пользователя на установление соединения любого класса принимается на обслуживание и потерь N k (t ) число установленных в момент времени t соединений k не происходит. Обозначим через класса. Тогда состояние системы можно описать с помощью многомерного случайного процесса { N (t ) = ( N1 (t ), N 2 (t ),..., N K (t )), t 0}, каждая компонента которого соответствует одному классу соединений. Поскольку емкости { N (t ), t 0} звеньев сети неограниченны, множество состояний случайного процесса имеет вид N = {0,1, 2,...}K.

{ N k (t ), t 0} Легко видеть, что случайный процесс является процессом размножения и гибели (ПРГ) со стационарным распределением вероятностей состояний n ak k e ak, nk {0,1, 2,...} pk ( nk ) = P{N k (t ) = nk } = nk !, и обратим.

Поскольку, в силу неограниченной емкости звеньев, компоненты составного случайного { N (t ), t 0} независимы, он также является ОМП и имеет стационарное распределение процесса вероятностей состояний мультипликативного вида:

n ak k e ak, n N ( n) = P{ N (t ) = n} = nk !

kK.

Cl, l L.

Пусть емкости звеньев снова ограничены: Введем множество K l = {k K : l Lk } классов соединений, маршруты которых проходят через l-звено, и функцию, соответствующую числу единиц емкости, занятых на l-звене, когда система находится в состоянии nN :

dl (n) = d k nk kK l. (70) Теперь пространство состояний системы (с ограниченными звеньями) можно представить в виде N = {n N : dl (n) Cl, l L }. (71) Обозначим { N (t ), t 0} сужение ОМП { N (t ), t 0} на множество состояний N N.

Справедлива следующая теорема.

Теорема 5. Случайный процесс { N (t ), t 0} является ОМП, и его стационарное распределение вероятностей имеет мультипликативный вид:

n ak k ( n) =, nN G ( N ) kK nk !, (72) где G ( N ) – нормировочная константа:

n ak k G(N ) = nk !.

nN kK (73) Опираясь на формулы (72) и (73), можно выписать выражения для многих важных характеристик сети. К ним относится важнейший показатель качества обслуживания – вероятность блокировки установления соединения.


Вероятности блокировок установления соединений Если при поступлении запроса пользователя на звеньях сети недостаточно ресурсов для установления соединения, происходит блокировка. Пусть Bk – стационарная вероятность блокировки запроса на установление соединения k-класса. Вычислить эту величину можно с помощью распределения (72) по формуле Bk = (n), k K nBk. (74) Здесь Bk – множество таких состояний сети, когда происходит блокировка запросов на установление соединения k-класса, то есть множество таких состояний сети, что хотя бы на одном из звеньев маршрута соединения k-класса недостаточно свободных ресурсов для его установления:

Bk = {n N : l Lk : dl (n) Cl dk }, k K. (75) Дополнением подпространства блокировки Bk установления соединения k-класса до пространства состояний N является подпространство приема Bk = {n N : dl (n) + d k Cl, l Lk }, объединяющее такие состояния сети, в которых запрос на установление соединений k-класса будет Bk = P{n Bk } = 1 Bk принят. Очевидно, что вероятность приема.

Вернемся к сети на рисунке 25 и рассмотрим, например, состояние n = (4, 3,1, 2, 3, 3). В этом состоянии d1 (n) = 30, d 2 (n) = 32 и d3 (n) = 34. Следовательно, оно является состоянием блокировки для соединений всех классов, кроме 2-го, так как на звене 1 свободных ресурсов нет, а на звене свободно только 3 единицы емкости. Для класса 2 состояние n является состоянием приема. Далее, анализируя, например, множество B1 блокировок класса 1, заметим, что оно включает все состояния из N, в которых на звене 1 занято 30 единиц емкости или на звене 2 занято 35 единиц емкости. Таким образом, помимо состояния n, в B1 войдут состояния (2,8,1, 2, 3, 3), (0, 0, 0, 0, 0, 6) и другие.

Тема 3.2. Модель звена сети с одноадресными соединениями. Алгоритм Кауфмана-Робертса Частным случаем рассмотренной в предыдущем разделе системы является отдельное звено сети. В данном разделе мы покажем, как применить предложенную модель к анализу отдельного звена МСС с одноадресными соединениями, приведем известный алгоритм Кауфмана – Робертса для вычисления вероятностных характеристик модели, а также рассмотрим два подхода к их приближенному расчету.

Постановка задачи * Пусть все звенья сети, кроме звена l, имеют неограниченную емкость. Тогда задача анализа C =C* * блокировок сводится к рассмотрению системы, состоящей из одного звена l емкости и l * l* множества классов соединений K, маршруты которых ограничены одним звеном: Lk = {l }, далее * для краткости индекс l будем опускать. Напомним, что каждый класс соединений характеризуется требованием к емкости звена d k, а также интенсивностью предложенной нагрузки ak = k k.

Функционирование такой системы описывает построенный в разделе случайный процесс { N (t ), t 0} с пространством состояний N = {n N : d (n) C}. (76) Для этого случайного процесса верна теорема 5 и, следовательно, стационарное распределение вероятностей состояний системы выражается формулами (72) и (73).

Опираясь на формулы (72) и (73), выпишем выражения для основных вероятностных характеристик звена. Стационарную вероятность блокировки запроса на установление соединения k-класса можно получить по формуле (76), при этом соответствующее пространство блокировок имеет вид Bk = {n N : d (n) C dk }, k K. (77) Важным показателем производительности системы является коэффициент использования звена. Для его вычисления нам потребуется среднее число занятых единиц емкости, которое можно получить по формуле d = d (n) ( n) nN. (78) Теперь выражение для коэффициента использования звена имеет вид d U= C. (79) Таким образом, мы показали, как более общая модель мультисервисной сети применима к анализу отдельного звена сети. Полученная система представляет собой известную в теории телетрафика модель простого стохастического ранца, или мультисервисную модель Эрланга с явными потерями. Подробно построение данной модел, мы же перейдем к методам расчета ее вероятностных характеристик.

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

C (n) = {n N : d (n) = n}, n = 0,..., C, (80) C C (n);

C (i) C ( j ) =, i j.

N= n = Оказывается, что соответствующие вероятности (распределение вероятностей числа занятых единиц емкости) ( n) P(n) = P{C (n)} = nC ( n ) (81) связаны меду собой рекуррентным соотношением K nP (n) = d k ak P (n d k ), n = 0,..., C k =1. (82) Данные соотношения позволяют построить простой и эффективный алгоритм расчета искомых характеристик. Введем функцию 0, n 0;

1, n = 0;

h ( n) = K 1 d k ak h( n d k ), n = 1,..., C.

n k = (83) Предложение 1. Значение нормирующей константы (73) стационарного распределения вероятностей состояний отдельного звена сети можно получить по формуле C h( n) G(N ) = n =0. (84) Предложение 2. Вероятность блокировки установления соединения k-класса вычисляется по формуле C h(n) n =C d k +, k K Bk = G(N ). (85) Предложение 3. Среднее число занятых единиц емкости звена вычисляется по формуле C n h(n) d = n= G(N ). (86) Добавим, что временная сложность вычисления нормирующей константы данным методом C при рекурсивном расчете функции (83) имеет порядок O(CK ). Если не использовать рекурсию и последовательно вычислять промежуточные значения функции (83), записывая их в память, то порядок временной сложности алгоритма составит O (CK ) и, следовательно, время вычисления характеристик будет увеличиваться линейно с ростом емкости звена.

Тема 3.3. Приближенный метод «просеянной нагрузки» для расчета вероятностей блокировок Оказывается, что чем больше и сложнее структура сети, тем проще во многом становится ее анализ, поскольку в этом случае можно допустить, что установление соединения блокируется независимо на различных звеньях маршрута. Предположение о независимости блокировок на звеньях, значительно облегчающее исследование, лежит в основе метода просеянной нагрузки3 – метода приближенного расчета вероятностей блокировок в сети. Этот метод впервые был предложен еще в 1960-х гг., но долгое время был незаслуженно обделен вниманием ученых. И Вард Уит, и английский математик Фрэнк Келли исследовали метод просеянной нагрузки в сетях с одноадресными одноканальными соединениями4. При этом если первый в своей работе уделил больше внимания способам решения получающихся при использовании метода уравнений, то второй математически обосновывает метод, рассматривая асимптотическое поведение системы при одновременном увеличении емкости звеньев и предложенной нагрузки, а также изучает вопросы существования решения упомянутых уравнений. Кроме того, Ф. Келли сделал попытку обобщить полученные результаты на сети с многоканальными соединениями5.

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

метод стохастического ранца и метод Паскаля, дающие более точные результаты в случае многоканальных соединений, чем метод, предложенный Ф. Келли. Основное различие трех подходов состоит в выборе модели для расчета вероятности блокировки на отдельно взятом звене От англ. Reduced load approximation, другое название – Fixed-point method (метод неподвижной точки).

Сети, в которых любое соединение занимает на звеньях маршрута одну единицу ширины полосы пропускания (англ. networks with single-rate traffic).

Сети, в которых требования классов соединений к ширине полосы пропускания звеньев различны (англ. networks with multirate traffic).

сети. Тогда как Ф. Келли использует несколько обобщенную модель Эрланга, то в [15] предлагаются более адекватные модель стохастического ранца и процесс гибели и размножения, у которого состояние соответствует числу занятых единиц емкости звена, а интенсивности переходов подобраны таким образом, что при неограниченной емкости звена математическое ожидание числа занятых единиц емкости и дисперсия совпадают с аналогичными характеристиками в модели стохастического ранца.

Сеть с одноадресными соединениями Изложение метода просеянной нагрузки проще всего начать с модели сети с одноканальными одноадресными соединениями. Рассмотрим модель, представленную в разделе 1, при d k = 1, k K. Введем систему событий:

B (l ) = {n N : dl (n) = Cl }, l L.

Ясно, что если имеет место событие B (l ), то запрос на установление соединения любого класса, маршрут которого проходит через l-звено, будет заблокирован. С другой стороны, блокировка запроса происходит тогда и только тогда, когда нет свободных ресурсов хотя бы на одном из звеньев маршрута, то есть Bk = B (l ), k K lLk. (87) Отсюда, используя закон де Моргана, получаем Bk = P(Bk ) = P( B (l )) = 1 P( B (l )), k K lLk lLk. (88) Если предположить, что блокировки на всех звеньях сети не зависят друг от друга, то есть события { B (l )}lL независимы в совокупности, то из (88) вытекает Bk = 1 (1 B(l ) ), k K * lLk, (89) * где B (l ) = P(B (l )) и Bk – условная вероятность блокировки запроса на установление соединения k класса при условии, что блокировки на звеньях происходят независимо.

Будем и дальше считать, что потери на звеньях происходят независимо. Тогда на каждое звено сети поступает пуассоновский поток запросов и для расчета вероятности блокировки звена можно воспользоваться формулой Эрланга B(l ) = E(a (l ), Cl ), l L, (90) где a(l ) – интенсивность нагрузки, поступающей на l-звено, и aC C!

E(a, C ) = Cn a n!

n =0.

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

Таким образом, интенсивность предложенной нагрузки на звено можно представить в виде a ( l ) = ak (1 B( j ) ), lL kK l jLk \{l }. (91) Подставляя это выражение в (91), получим систему уравнений B (l ) = E ak (1 B( j ) ), Cl, l L kK l jLk \{l }. (92) Решение этой системы существует, согласно теореме Брауэра, как неподвижная точка L L E : [ 0,1] [ 0,1] непрерывного отображения, а доказательство единственности решения для общего случая ( d k 1, k K ). Что же касается способа решения системы, то наиболее удобным здесь представляется использовать метод последовательных приближений. Вопрос сходимости итерационной последовательности при решении данной системы был подробно изучен В. Уиттом.

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

Получив решение системы (92), следует подставить его в формулу (89) и таким образом * рассчитать искомые вероятности. Вообще говоря, то, насколько точно Bk приближают Bk, зависит от того, насколько правомерно делать предположение о независимости блокировок на звеньях для данной конкретной сети. Свойства модели во многом становятся проще при рассмотрении больших сетей сложной топологии, когда велико количество звеньев и различных маршрутов соединений. В качестве обоснования применимости метода просеянной нагрузки доказана асимптотическую точность приближения при одновременном стремлении емкости звеньев сети и интенсивности предложенной нагрузки к бесконечности.

Вернемся к общему случаю, когда d k 1, k K, и разберем метод вычислений вероятностей блокировок, которыq является попыткой обобщить уже рассмотренный нами алгоритм на мультисервисные сети с дифференцированными требованиями соединений к емкости звеньев.

Опять будем предполагать, что блокировки на звеньях сети происходят независимо. Приближенные * значения Bk вероятностей блокировки запросов Bk предлагается вычислять по следующей формуле:

d * Bk = 1 (1 B(l ) ) k, k K lLk, (93) где B (l ), l L – решение системы уравнений 1 d 1 B (l ) l k k j ( 1 B ( j ) ) k, Cl, l L B (l ) = E da Lk kK. (94) Соотношения (94) объясняются следующим образом: если заявка на одну единицу ресурса на звене блокируется с вероятностью B (l ) и если предположить, что такие блокировки происходят независимо на различных звеньях, то поток заявок, приходящий на l-звено, будет пуассоновским, а интенсивность обслуженной этим звеном нагрузки составит d a l ) = d k ak (1 B ( j ) ) k, l L ( kK l jLk. (95) Тогда интенсивность предложенной нагрузки можно выразить следующим образом:

d d k ak (1 B( j ) ) k ( a l) kK l jLk, lL a (l ) = = 1 B (l ) 1 B (l ), (96) и уже эту величину следует подставить в формулу Эрланга.

Легко проверить, что при d k = 1, k K, соотношения (95) и (96) сводятся к (92) и (93) соответственно. Существование решения системы (96) вновь вытекает из теоремы Брауэра, поскольку мы опять ищем неподвижную точку непрерывного отображения выпуклого компактного n множества из R на себя.

Применение формулы Эрланга для расчета вероятности блокировки на отдельном звене приводит к системе уравнений неподвижной точки (96), имеющей единственное решение, однако использование других более адекватных моделей отдельного звена ощутимо повышает точность метода на уровне всей сети. Рассматривается система событий Bk (l ) = {n N : di ni Cl d k }, k K, l Lk.

iK l В этом случае соотношения (93) и (94) принимают вид Bk = Bk (l ), k K lLk, Bk = 1 (1 Bk (l ) ), k K * lLk, (97) * где Bk (l ) = P(Bk (l )), k K, l L, а Bk, напомним, – условная вероятность блокировки запроса на установление соединения k-класса при условии, что блокировки на звеньях происходят независимо.

Для нахождения Bk (l ) применима модель отдельного звена (ее также называют моделью стохастического ранца), и алгоритм Кауфмана – Робертса. При этом Bk (l ) вычисляются как функции от интенсивности поступающей на звено нагрузки, которая, в свою очередь, выражается через вероятности блокировок на других звеньях:

(1 Bk ( j ) ), k Kl, l L ak (l ) = ak jLk \{l}. (98) Таким образом, мы вновь ищем эти вероятности как неподвижную точку некоторого отображения. Однако в данном случае система неподвижной точки не обязательно имеет единственное решение.

Тема 3.4. Модель сети с многоадресными соединениями Многоадресная передача данных (multicast), или мультивещание – технология доставки информации по принципу «точка–много точек», позволяющая более эффективно по сравнению с одноадресной передачей использовать ресурсы сети при рассылке идентичных данных нескольким пользователям. При традиционных способах передачи информации для каждой пары источник– получатель устанавливается соединение «точка–точка» (unicast). В случае передачи одинаковых данных нескольким получателям (например, рассылка обновлений программного обеспечения или телетрансляция в СДОП) это приводит к тому, что по общим для нескольких соединений звеньям сети передается несколько копий одной и той же информации. При мультивещании пользователи совместно используют пропускную способность общих звеньев маршрутов без дублирования информации.

Первые спецификации многоадресной передачи появились в середине 1980-х гг., однако востребована эта технология стала только в конце 1990-х гг. при организации на базе мультисервисных сетей связи включая Интернет, телевизионного вещания и (МСС), видеотрансляций, поскольку предоставление таких услуг предполагает обеспечение возможности передавать большим группам абонентов трафика существенного объема – десятков видеопотоков, соответствующих различным телевизионным каналам, со скоростью не ниже 2–4 Мбит/с в случае телевидения традиционного качества и около 25–34 Мбит/с в случае телевидения высокой четкости (High Definition Television, HDTV).

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

При динамическом мультивещании источник начинает передачу информации, соответствующей содержанию услуги, по запросу пользователя. Момент окончания предоставления услуги также определяется пользователем. Примером динамического мультивещания служит теле и радиовещание в мультисервисной сети.

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

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

Рассмотрим фрагмент мультисервисной сети заданной структуры, состоящей из L звеньев (рисунок 26). Последовательность звеньев сети от узла подключения пользователя до источника будем называть физическим путем. Обозначим L = {1,..., L} – множество звеньев сети;

S = {1,..., S } – множество источников информации;

Ps = {1,..., Ps } – множество всех физических путей к источнику s S ;

Ms = {1,..., M s } – множество услуг, предоставляемых источником s S ;

L ps L – множество всех звеньев физического пути p Ps к источнику s S ;

S l = {s S : Psl } – множество источников информации, предоставляющих услуги через звено l L ;

Psl = { p Ps : l L ps } l – множество физических путей к источнику s S, проходящих через звено l L ;

bms – число единиц емкости звена, требуемое для предоставления услуги m Ms ;

Cl – емкость звена l L.

Рисунок 26 – Пример сети мультивещания Упражнение 7. Для примера сети многоадресной передачи, схема которой изображена на L l рис. 3.2, выпишите множества L, S, Ps, Ms, ps, где s S, а также множества S, Ps, где l L l l, s S. Постройте дерево мультивещания от каждого из источников.



Pages:     | 1 || 3 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.