Автоматика и телемеханика, Л- 6, 2007
Системы массового обслуживания
РАС S 89.75.-к
© 2007 г. А.Н. ДУДИН, д-р физ.-мат. наук (Белорусский государственный университет, Минск), М.Х. ЛИ, д-р техн. наук, Ч.Х. ЧОЕ
(Национальный университет Чонбук, Джонджу)
МОДЕЛЬ СЕТИ ОБСЛУЖИВАНИЯ С ПАРАЛЛЕЛЬНЫМИ МАРШРУТАМИ1
Рассмотрена сеть массового обслуживания, имеющая несколько параллель-пых путей доставки информации из узла источника в узел назначения. При наличии нескольких свободных каналов из узла источника информация передается одновременно по всем маршрутам, начинающимся с этих каналов. С использованием матричпо аналитических методов найдены стационарные характеристики функционирования сети.
1. Введение
Рассмотрим коммуникационную сеть, имеющую топологию, изображенную на рис. 1.
Узел номер 0 является источником информации, которая должна быть передана в узел n +1 Промежуточные (транзитные) узлы 1,... ,n могут быть интерпретированы как ретрансляторы информации или как некоторые возможные цепочки узлов (маршруты) между узлами 0 и n+1. Передача информации в такой сети может быть описана в терминах сети массового обслуживания, схематически представленной на рис. 2. При предположениях, что потоки информации, передаваемые в сети, являются стационарными пуассоновскими, времена обработки в узлах имеют экспоненциальное распределение, а маршрут выбирается некоторым детерминированным или рандомизированным образом, анализ вероятностно-временных характеристик процесса передачи информации является достаточно тривиальным, поскольку стационарное распределение вероятностей состояний сети будет иметь мультипликативную форму, а распределение состояний узлов легко находится в явном виде.
Вместе с тем поскольку времена обработки информации в узлах случайные, буферы в промежуточных узлах конечные, промежуточные узлы обрабатывают, кроме
0
формации в узел n +1, а также учитывая надежностные аспекты, имеет смысл рассматривать дисциплины передачи информации, позволяющие при наличии несколь-
1 Авторы благодарят за поддержку данного исследования Министерство информации и связи (Ministry of Information and Communication) Республики Корея в рамках программы приглашения зарубежных специалистов в области информационных технологии (IT Foreign Specialist Inviting Program) Института оценивания информационных технологии 11ТЛ (Institute of Information Technology Assessment).
ких свободных исходящих каналов из узла источника 0 передавать информацию одновременно по нескольким или по всем маршрутам, начинающимся в узле 0. В [1] рассмотрена модель многолинейной системы массового обслуживания, описываю-
0
дящие каналы идентичны, а запрос, при наличии нескольких свободных каналов в момент его поступления, копируется и обслуживается независимо во всех свободных каналах. В [1] показано, что хотя такая дисциплина обслуживания приводит к повышенной занятости каналов, она может позволить существенно уменьшить среднее время доставки информации, если под этим временем понимать минимальное из времен доставки копий этой информации. Также отмечено, что такая множественная обработка информации при наличии ошибок в передаче приводит к существенному увеличению вероятности корректной доставки информации. Это и послужило мотивацией рассмотрения сети, представленной на рис. 2. в предположении, что
0
его поступления, копируется и обслуживается независимо во всех свободных каналах и в соответствующих промежуточных узлах сети. Такая модель сети, названная кооперативной ретрансляционной сетыо. при наличии двух альтернативных маршрутов рассмотрена в [2]. Однако анализ, приведенный в [2]. адресуется физическому уровню работы сети. В статье анализируется более общий случай сетевого уровня.
Структура статьи следующая. В разделе 2 описано функционирование модели рассматриваемой сети. В разделе 3 введены необходимые обозначения и многомерная цепь Маркова, описывающая динамику системы, и доказано условие эргодично-
сти этой цепи. В разделе 4 решена проблема нахождения стационарного распределения вероятностей состояний этой многомерной цепи. В разделе 5 приведены выражения для вычисления основных характеристик производительности сети. Раздел 6 содержит численные примеры. Раздел 7 заключает статью.
2. Математическая модель
Топология рассматриваемой коммуникационной сети представлена на рис. 1. Соответствующая модель сети массового обслуживания изображена на рис. 2. Функционирование узла-источника с номером 0, имеющего n исходящих каналов, описывается n-канальной системой массового обслуживания с бесконечным буфером,
0
ционарный пуассоновский поток запросов интенсивности Ао. Время обслуживания запроса в k-м канале системы имеет показательное распределение с параметром k = l,n. Если поступивший запрос застал все каналы занятыми, он становится в очередь. Из очереди запросы выбираются в соответствии с дисциплиной FIFO ("первым пришел первым обслужен"). Если запрос застал в системе один свободный канал, он немедленно начинает обслуживаться в этом канале. Если запрос застал в системе несколько свободных каналов, он копируется (размножается), и его копии начинают обслуживаться во всех свободных каналах. Далее они рассматриваются как самостоятельные запросы, и доставка одного из них в узел назначения номер n + 1 означает доставку размножившегося запроса, но не приводит к удалению из системы всех других копий этого запроса. Таким образом, исходящие каналы сотрудничают (кооперируются) друг с другом в обслуживании запросов.
k0 ется на обслуживание в систему номер k* (см. рис. 2). Это - однолинейная система массового обслуживания с конечным буфером емкости Nk — 1, Nk ^ 1, и временем
обслуживания, имеющим показательное распределение с параметром щ, k = 1,n.
0 k*
дон, запрос начинает обслуживаться. Если прибор занят, но буфер не заполнен, то запрос помещается в буфер. Если буфер занят, будем различать два варианта поведения запроса. В простом варианте будем считать, что этот запрос теряется и не будет доставлен в узел номер n +1. В основном варианте будем считать, что данный
0
k
исходящих каналах. Эта процедура повторяется до тех пор, пока запрос не попадет на обслуживание в соответствующий транзитный узел. После получения обслуживания в транзитном узле запрос считается обслуженным в сети (доставленным в
узел номер n + 1). Отметим, что в модели предполагается, что в каждую систему k*
ставлены в узел номер n +1. Этот поток является стационарным пуассоновским с интенсивностью Ak, k = 1,n. Запросы этого потока, заставшие занятый буфер, теряются. В противном случае они получают обслуживание наравне с запросами,
0
Проведем анализ описанной модели сети массового обслуживания.
3. Процесс состояний сети. Условие эргодичности
Поведение рассматриваемой модели сети массового обслуживания описывается многомерной цепыо Маркова
& = {3ui{t\---,if]}, t > 0, ¿tk) = 0N k = 1n,
где компонента г[к соответствует числу запросов в системе номер к*, к = 1,п, в момент 1,1 ^ 0. Оно включает число запросов в буфере и на приборе. Компонента ^ описывает состояние п-канадьной системы номер 0. Состояние 3,3 ^ 1, компоненты соответствует состоянию системы помер 0, когда все приборы этой системы заняты и 3 запросов находится в буфере.
Если же очередь в систему помер 0 отсутствует, то компонента ^ задается набором из п чисел {¡I,..., ¡п}, где элемент ¡к принимает значение 0, если к-й прибор системы помер 0 пуст, и значение 1, тел и к-й прибор занят в момент ^ 0 к = 1,п. Обозначим через С множество всевозможных таких наборов. Очевидно, что оно состоит из 2п наборов.
Чтобы упростить обозначения и использовать матричную технику исследования, перенумеруем компоненты процесса ^ = {зг,г)1\...1)п^}, t ^ 0, в лексикографическом порядке. В результате можно рассматривать целую группу состояний
{зЛ1
;(п)} -(к)
0,мк, к
3 = {0,...,0}, {0,...,0,1},...,{1,
1,п, как одно состояние 3 процесса Си ^ ^ 0. .,1}, 1, 2, 3,....
Для дальнейшего использования введем следующие обозначения:
п
• I - тождественная матрица размера К = П (Мк + 1); 1к - тождественная
_ к=1
матрица размера N + 1, к = 1,п; О нулевая матрица размера К х К; О нулевая матрица размера К1 х Кт;
• ® - символ Кронекерова произведения матриц; ф - символ Кронекеровой суммы матриц; знак т обозначает транспонирование матрицы или вектора;
• ек - вектор-столбец размера Мк + 1 состоящий из единиц; ек - вектор-столбец размера К, состоящий из единиц; ето - вектор-столбец бесконечного размера, состоящий из векторов ек]
• 0к - вектор-строка размера Ык + 1, состоящая из нулей, к = 1,п; 0к вектор-строка размера К, состоящая из нулей; 0ТО - вектор-строка бесконечного размера,
0к
вектор-столбец размера N + 1, имеющий вид (0,..., 0,1,0,..., 0)т
0,Жк, к
1— ~(0 • 1,Щ ек , г
0,Мк, - вектор-столбец размера К, заданный формулой
: е 1 <&■■■<& ек-1 ® fkг) ® ек+1 ® ■ ■■ ®
. Т Т Т + Т- т* т+
• Тк-, Тк-, тк ■, тк ' тк' тк
следующий вид:
квадратные матрицы размера N + 1 к = 1,п, имеющие
Т+
( 1 0 0 1
0 0 ...
\ 0 0 ...
( 0 10
0 0 1
0 0 0 \ 0 0 0
0 0\
0 0
1 0
0 0 у
.. 0 .. 0
0
/00 0 1
0 0\
0 0
0 0 ...
\ 0 0 ...
( 0 0 0
1 0 0
0 1 0
1 0 0 1/
\ 0 0 0
0 0 \ 0 0 0 0
1 0 /
к
е
к
п
1
Ч = ь - к 1+ = 1+ + II;
__^ п п
Лк = хк 1к + щ1к; А = 0 Лк = А1 Ф---®Ап; Вк = Лк 1+ + щ1— В =0 вк;
к=1
к=1
Н = В-ЛСк = II ® ■■■ ® 1к-1 ® Ик I+ ® 1к+1 ®---®1п', с = 0 Ик I+ = Е Ск;
к=1 к=1 пп
Мк = Ь ® ■ ■■ ® Ь-1 ® Ик Ь ® Ik+l ® ■■■Ф^; Е = 0 Ик 4 = Е Мк;
к=1 к=1
М*к = I! ® ■■■ ®Ik-l ®ИкII ®Ь+1 ® ■■■^п
Ро = Ло4 Р = -Л^ -Е + н Т>1 = -А^ + Н®2 = С;
Q{0,...,0},{0,...,0} = -ЛоI + н Q{0,.,0},{1,.,1} = Ло^
д{о,...,о},{г1,...,г„} = о {¡1,...,1п} е С, {¡1,...,1п} = {0,...,0}, {/1 ,...,п} = = {1,...,1};
1, — — — ,...,1к-1, о,1к + 1,...,1п} = Ск•
Q{l 1 ,...,1п},{1,...,1} = Ло I + £ М*к,{/1,...,/п} = {1,...,1};
=1'11 е{(1,...,1п}
Q{ll,...,ln},{ll,...,ln} = -Л^ + н- Е
Щ = 1,1^ Е{к,...м
Q0,0 - квадратная матрица размера К2п, состоящая из квадратных блоков
МГ,
,...,1п},{11,...,1'п }
размера
К : Qо,о = ^-...-«Л
{11,...,1п},{1[,...,1П}ес;
Ql,о =
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.