Використання апарату ідемпотентних алгебр для аналізу процесів в мережі з наданням інтегрованих послуг
The implementation of algebra is equations "min-plus" for network analysis with the provision of integrated services is show. The protocol is operation RSVP is considered. The possibility of network resources control depending on the requirements for the delays by traffic type, is...
Saved in:
| Date: | 2011 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2011
|
| Online Access: | https://journal.iasa.kpi.ua/article/view/106466 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1866301861897699328 |
|---|---|
| author | Bessarab, V. I. Zaytseva, E. Ye. Kovalenko, E. G. |
| author_facet | Bessarab, V. I. Zaytseva, E. Ye. Kovalenko, E. G. |
| author_sort | Bessarab, V. I. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-03-30T15:04:48Z |
| description | The implementation of algebra is equations "min-plus" for network analysis with the provision of integrated services is show. The protocol is operation RSVP is considered. The possibility of network resources control depending on the requirements for the delays by traffic type, is shown. The variant of the transmission rout calculation is proposed, taking into account restrictions for the delay. |
| first_indexed | 2025-07-17T10:21:21Z |
| format | Article |
| fulltext |
© В.И. Бессараб, Э.Е. Зайцева, Е.Г. Коваленко, 2011
Системні дослідження та інформаційні технології, 2011, № 2 35
УДК 621.391.512
ИСПОЛЬЗОВАНИЕ АППАРАТА ИДЕМПОТЕНТНЫХ АЛГЕБР
ДЛЯ АНАЛИЗА ПРОЦЕССОВ В СЕТИ
С ПРЕДОСТАВЛЕНИЕМ ИНТЕГРИРОВАННЫХ УСЛУГ
В.И. БЕССАРАБ, Э.Е. ЗАЙЦЕВА, Е.Г. КОВАЛЕНКО
Показано применение уравнений «min-plus» алгебры для анализа сети с пре-
доставлением интегрированных услуг. Рассмотрена работа протокола RSVP.
Показана возможность управления ресурсами сети в зависимости от требова-
ний к задержке по типу трафика. Предложен вариант расчета маршрута пере-
дачи с учетом ограничений на задержку.
ВВЕДЕНИЕ
Традиционные сетевые приложения, такие как передача файлов и электрон-
ная почта, некритичны к задержкам, тогда как для приложений мультимедиа
увеличение задержки является неприемлемым. Гарантированное качество
обслуживания в IntServ (Integrated Service — интегрированный сервис)
обеспечивается за счет непревышения верхней границы задержки передачи
данных по сети. IntServ использует для своих целей протокол сигнализации
RSVP (Resource ReSerVation Protocol — протокол резервирования сетевых
ресурсов), что позволяет пограничным узлам резервировать сетевые ресур-
сы для получения необходимого качества услуг [1]. Механизм RSVP-
резервирования ресурсов приведен на рис. 1. Для определения количествен-
ных характеристик этих требований с целью управления доступом, исполь-
зуются служебные параметры. RSVP-запросы передаются по сети при прохо-
ждении каждого узла, который используется для передачи потока. Протокол
RSVP резервирует ресурсы для потока данных на каждом из этих узлов.
Цель работы — рассмотреть задачу анализа процессов в IntServ сети с
целью обеспечения заданного качества обслуживания на основе протокола
RSVP.
ПОСТАНОВКА ЗАДАЧИ
Рассмотрим сеть, состоящую из n узлов, по которой передается поток, оп-
ределенный T-SPEC (traffic specification — характеристики трафика):
Рис. 1. Механизм RSVP-резервирования ресурсов
В.И. Бессараб, Э.Е. Зайцева, Е.Г. Коваленко
ISSN 1681–6048 System Research & Information Technologies, 2011, № 2 36
• максимальный размер пакета — ;M
• пиковая скорость передачи данных — ;p
• средняя скорость передачи данных — ;r
• максимальный размер всплеска — .b
В исследуемой сети необходимо по заданному ограничению на сквоз-
ную задержку d рассчитать резервируемую скорость .R′
Метод решения поставленной задачи. Для решения поставленной за-
дачи предлагается использовать аппарат идемпотентных алгебр, а именно
«min-plus» алгебры. «Min-plus» алгебра — это алгебраическое множество
),,(min ∧∨= εRR , где }{+∞∪= RRε , а операции ∨ и ∧ определяются ра-
венствами: ),(min baba ≡∨ и baba +≡∧ для всех εR∈ba, [2].
Результаты решения задачи. Для потока T-SPEC (2К, 15 Мбит/с,
1024 Кбит/с, 32 К), проходящего путь из трех маршрутизаторов, и требуемой
сквозной задержки сети 5,0=d с рассчитана резервируемая (гарантирован-
ная) скорость передачи 1200=′R Кбит/с.
Протокол RSVP работает следующим образом: узел-источник до пере-
дачи данных, требующих определенного нестандартного качества обслужи-
вания (например, постоянной полосы пропускания для передачи видеоин-
формации), посылает по сети специальное сообщение в формате протокола
RSVP. Это сообщение о пути (PATH) содержит данные о типе передаваемой
информации и требуемой пропускной способности. Оно передается между
маршрутизаторами по всему пути от узла-отправителя до узла назначения,
при этом определяется последовательность маршрутизаторов, в которых
необходимо зарезервировать определенную полосу пропускания. Сообще-
ние PATH направляется по тому же маршруту, по которому движутся инфо-
рмационные пакеты. Маршрутизатор, получив такое сообщение, проверяет
свои ресурсы с целью определения возможности выделения требуемой про-
пускной способности. При ее отсутствии маршрутизатор отвергает запрос.
Если требуемая пропускная способность достижима, то маршрутизатор на-
страивает алгоритм обработки пакетов таким образом, чтобы указанному
потоку всегда предоставлялась требуемая пропускная способность, а затем
передает сообщение (RESV — reservation — сообщение о резервировании)
предыдущему маршрутизатору. Сообщения RESV несут в себе запросы в
направлении противоположном движению потока данных.
В результате, по всему пути от узла-отправителя до адреса назначения
резервируется необходимая пропускная способность с целью обеспечения
запрашиваемого качества обслуживания по задержке.
Протокол RSVP передает сигнальную информацию о запросах резер-
вирования ресурсов по доступному маршрутизируемому пути в сети. При
этом RSVP не производит собственную маршрутизацию. Маршрут, при оп-
ределении пути для данных и управляющего трафика RSVP, определяется
применяемым в сети протоколом маршрутизации, в основе которого лежит
алгоритм нахождения кратчайшего пути между любой парой узлов [3].
Каждый узел вдоль маршрута задает для потока кривую сервиса — не-
убывающую функцию β , такую, что 0)0( =β и для входящего в узел пото-
ка )(tI и покидающего узел потока )(tI ∗ выполняется неравенство
))(()( tItI β∧≥∗ (рис. 2).
Использование аппарата идемпотентных алгебр для анализа процессов в сети …
Системні дослідження та інформаційні технології, 2011, № 2 37
Для потока, определенного T-SPEC, кривая сервиса для n -го сетевого
маршрутизатора задается функ-
цией
nn TR ,β , которая определяет
характер зависимости скорости
nR и задержки nT , где =nT
n
R
n DC ∧= /1)( , здесь nn DС , —
константы, зависящие от характе-
ристик n -го маршрутизатора, а
именно nС — максимальный раз-
мер пакета, проходящего через
n -й маршрутизатор;
c
LDn = , L
— максимальный размер пакета в
n -м маршрутизаторе по всем по-
токам, проходящим через него, с — скорость планировщика [4]. Необходи-
мо по заданному ограничению на сквозную задержку d рассчитать резер-
вируемую скорость R′ .
В результате процедуры резервирования протоколом RSVP узел n при-
сваивает потоку значение скорости rRn ≥ , а именно:
( )( )⎪
⎪
⎩
⎪
⎪
⎨
⎧
∧=
=
∧
∨
=
=
.
,
/1
1
1
n
R
n
N
n
n
N
n
DCT
RR
n
Ограничение на сквозную задержку — ,d при условии, что все узлы на
пути зарезервируют nRR =′ определяется:
tot
tot )()()( D
R
CM
rp
Rp
R
MbRf ∧
′
∧
∧⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
Ο/
′Ο/
⎟
⎠
⎞
⎜
⎝
⎛
′
Ο/
=′ , (1)
где n
N
n
CC ∧
=
=
1
tot , n
N
n
DD ∧
=
=
1
tot , totC и totD — параметры AD-SPEC (Ad Spe-
cifications — дополнительная информация о потоке), которые несут в себе
информацию о потоке (OPWA — One Pass With Advertising — вариант од-
нопроходного алгоритма). С помощью OPWA управляющие пакеты RSVP,
посланные вдоль маршрута для сбора данных, могут быть использованы для
предсказания значения QoS маршрута в целом. На рис. 3 приведен расчет
параметра AD-SPEC.
(C1; D1) (C1+C2+C3; D1+D2+D3)(C1+C2; D1+D2)
Рис. 3. Расчет параметра AD-SPEC
)(tI )(tI ∗
))(( tI β∧
t
Рис. 2. Кривая сервиса узла сети
В.И. Бессараб, Э.Е. Зайцева, Е.Г. Коваленко
ISSN 1681–6048 System Research & Information Technologies, 2011, № 2 38
Получатель рассчитывает R′ , как наименьшее значение из всех ,r≥
для которого, такое значение существует только, если .tot dD ≤
Для получения количественных характеристик по предлагаемой мето-
дике используется сеть, топология которой приведена на рис. 4.
Для определения алгоритма маршрутизации используется уравнение
«min-plus» алгебры:
)( k
Nk
AA
∈
+ ∨= . (2)
Элементами матрицы A являются метрики дуг графа, которым пред-
ставлена сеть. Метрика представляет собой оценку эффективности связи в
канале: чем меньше метрика, тем эффективнее организация связи. В част-
ном случае, метрика, оценивающая пропускную способность канала опре-
деляется, как количество времени необходимое для передачи 100 Мбит по-
тока данных. Для сети, изображенной на рис. 4, матрица A имеет вид:
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
εεεεεεεε
εεεεεεεεε
εεεεεεε
εεεεεεεε
εεεεεε
εεεεεε
εεεεεεε
εεεεεεεεε
εεεεεεε
εεεεεεεε
εεεεεεεε
21148
248
1111482
48112
481121111
48112248
221148
1148
1121111
484811
481111
A .
В соответствии с (2) рассчитана матрица кратчайших расстояний меж-
ду любой парой узлов сети +A :
2Мбит/с
48
34,368Мбит/с
2
2Мбит/с
48
2Мбит/с
48
34,368Мбит/с
2
34,368Мбит/с
2
8,448Мбит/с
11
8,448Мбит/с
11
8,448Мбит/с
11
2Мбит/с
48
8,448Мбит/с
11
8,448Мбит/с
11
8,448Мбит/с
11
8,448Мбит/с
11
34,368Мбит/с
2
8,448Мбит/с
11
34,368Мбит/с
2
2,024
Мбит/с
481
2
3
4
5
6
7
8
9
10
11
34,368Мбит/с
2
Sender Receiver
Рис. 4. Топология исследуемой сети
Использование аппарата идемпотентных алгебр для анализа процессов в сети …
Системні дослідження та інформаційні технології, 2011, № 2 39
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=+
42111522241333244635
24131724261535264837
1113441113222133524
1517441311224133524
2224111342131142615
2426131124131322413
1315221313424113322
3335222411132422153726
2426131342111542211
4648353526243337222211
3537242415132226111122
A .
Например, в полученной матрице, расстояние между парами узлов со-
ставляет:
• 2-й узел – 11-й узел — 46 у.е.;
• 5-й узел – 8-й узел — 2 у.е.;
• 7-й узел – 5-й узел — 13 у.е.
Таким образом, кратчайший путь от отправителя к получателю в нашем
примере составляет 35 1,11)( +А условных единиц оценки расстояния. Мето-
дом «обратного хода» определяем кратчайший маршрут, который проходит
через узлы 1–3–5–9–11 (рис. 5).
Для маршрутизаторов 3, 5 и 8 параметры C и D соответственно
составляют: 8,93 =C Кбит и 05,03 =D с; 2,205 =C Кбит и 05,05 =D с;
5,128 =C Кбит и 15,08 =D с.
Итак, для найденного кратчайшего маршрута параметр AD-APEC со-
ставляет: 5,42tot =C Кбит и 25,0tot =D с. Для заданного потока T-SPEC
(2 К, 15 Мбит/с, 1024 Кбит/с, 32 К), проходящего путь через 3-й, 5-й и 8-й
маршрутизаторы, и требуемой сквозной задержки сети, 5,0=d в соответст-
вии с формулой (1) рассчитана гарантированная скорость передачи
1200=′R Кбит/с.
ВЫВОДЫ
В работе показано применение уравнений «min-plus» алгебр для анализа се-
ти с предоставлением интегрированных услуг. Рассмотрена работа протоко-
8,448Мбит/с
11
8,448Мбит/с
11
8,448Мбит/с
11
34,368Мбит/с
2
1
3 5 8
11
Sender T-SPEC
(2К,15Мбит/с,
1024Кбит/с,32К)
R-SPEC (1200Кбит/с) R-SPEC (1200Кбит/с)R-SPEC (1200Кбит/с)R-SPEC (1200Кбит/с)
Sender T-SPEC
(2К,15Мбит/с,
1024Кбит/с,32К)
Sender T-SPEC
(2К,15Мбит/с,
1024Кбит/с,32К)
Sender T-SPEC
(2К,15Мбит/с,
1024Кбит/с,32К)
Receiver T-SPEC (2К,
15Мбит/с,1024Кбит/с,24К)
Receiver T-SPEC (2К,
15Мбит/с,1024Кбит/с,24К)
Receiver T-SPEC (2К,
15Мбит/с,1024Кбит/с,24К)
Receiver T-SPEC (2К,
15Мбит/с,1024Кбит/с,24К)
Sender Receiver
Рис. 5. Кратчайший маршрут
В.И. Бессараб, Э.Е. Зайцева, Е.Г. Коваленко
ISSN 1681–6048 System Research & Information Technologies, 2011, № 2 40
ла RSVP, определены сквозная задержка сети и соответствующая ей заре-
зервированная скорость передачи.
1. Показана возможность управления ресурсами сети в зависимости от
требований к задержке по типу трафика.
2. Предложен вариант анализа динамики процессов передачи по сети с
использованием аналитических уравнений одной из разновидностей идем-
потентных алгебр.
3. Предложен вариант расчета маршрута передачи с учетом ограниче-
ний на задержку.
ЛИТЕРАТУРА
1. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, прото-
колы: учеб. для вузов. — 3-е изд. — СПб.: Питер, 2006. — 958 с.
2. Cohen G., Gaubert S. and Quadrat J.-P. Max-plus algebra and system theory: where
we are and where to go now // Annual Reviews in Control. — 1999. —
№ 23(1):207. — Р. 219.
3. Таненбаум 3.Э. Компьютерные сети. — 4-е изд. — Спб.: Питер, 2007. — 992 с.
4. Boudec J.-Y. Le and Thiran P. Network calculus viewed as a min-plus system theory
applied to communication networks // Technical Report. — 1998. — 34 p.
Поступила 27.05.2009
|
| id | journaliasakpiua-article-106466 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:21:21Z |
| publishDate | 2011 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/fc/dce4352bf5edd6472949d59504043ffc.pdf |
| spelling | journaliasakpiua-article-1064662018-03-30T15:04:48Z Usage of the apparatus of idempotent algebra for the analysis of the processes in network with the provision of integrated services Использование аппарата идемпотентных алгебр для анализа процессов в сети с предоставлением интегрированных услуг Використання апарату ідемпотентних алгебр для аналізу процесів в мережі з наданням інтегрованих послуг Bessarab, V. I. Zaytseva, E. Ye. Kovalenko, E. G. The implementation of algebra is equations "min-plus" for network analysis with the provision of integrated services is show. The protocol is operation RSVP is considered. The possibility of network resources control depending on the requirements for the delays by traffic type, is shown. The variant of the transmission rout calculation is proposed, taking into account restrictions for the delay. Показано применение уравнений "min-plus" алгебры для анализа сети с предоставлением интегрированных услуг. Рассмотрена работа протокола RSVP. Показана возможность управления ресурсами сети в зависимости от требований к задержке по типу трафика. Предложен вариант расчета маршрута передачи с учетом ограничений на задержку. Показано застосування рівнянь "min-plus" алгебри для аналізу мережі з наданням інтегрованих послуг. Розглянуто роботу протоколу RSVP. Показано можливість керування ресурсами мережі в залежності від вимог до затримки за типом трафіку. Запропоновано варіант розрахунку маршруту передачі з урахуванням обмежень на затримку. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2011-06-16 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/106466 System research and information technologies; No. 2 (2011); 35-40 Системные исследования и информационные технологии; № 2 (2011); 35-40 Системні дослідження та інформаційні технології; № 2 (2011); 35-40 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/106466/101561 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Bessarab, V. I. Zaytseva, E. Ye. Kovalenko, E. G. Використання апарату ідемпотентних алгебр для аналізу процесів в мережі з наданням інтегрованих послуг |
| title | Використання апарату ідемпотентних алгебр для аналізу процесів в мережі з наданням інтегрованих послуг |
| title_alt | Usage of the apparatus of idempotent algebra for the analysis of the processes in network with the provision of integrated services Использование аппарата идемпотентных алгебр для анализа процессов в сети с предоставлением интегрированных услуг |
| title_full | Використання апарату ідемпотентних алгебр для аналізу процесів в мережі з наданням інтегрованих послуг |
| title_fullStr | Використання апарату ідемпотентних алгебр для аналізу процесів в мережі з наданням інтегрованих послуг |
| title_full_unstemmed | Використання апарату ідемпотентних алгебр для аналізу процесів в мережі з наданням інтегрованих послуг |
| title_short | Використання апарату ідемпотентних алгебр для аналізу процесів в мережі з наданням інтегрованих послуг |
| title_sort | використання апарату ідемпотентних алгебр для аналізу процесів в мережі з наданням інтегрованих послуг |
| url | https://journal.iasa.kpi.ua/article/view/106466 |
| work_keys_str_mv | AT bessarabvi usageoftheapparatusofidempotentalgebrafortheanalysisoftheprocessesinnetworkwiththeprovisionofintegratedservices AT zaytsevaeye usageoftheapparatusofidempotentalgebrafortheanalysisoftheprocessesinnetworkwiththeprovisionofintegratedservices AT kovalenkoeg usageoftheapparatusofidempotentalgebrafortheanalysisoftheprocessesinnetworkwiththeprovisionofintegratedservices AT bessarabvi ispolʹzovanieapparataidempotentnyhalgebrdlâanalizaprocessovvsetispredostavleniemintegrirovannyhuslug AT zaytsevaeye ispolʹzovanieapparataidempotentnyhalgebrdlâanalizaprocessovvsetispredostavleniemintegrirovannyhuslug AT kovalenkoeg ispolʹzovanieapparataidempotentnyhalgebrdlâanalizaprocessovvsetispredostavleniemintegrirovannyhuslug AT bessarabvi vikoristannâaparatuídempotentnihalgebrdlâanalízuprocesívvmerežíznadannâmíntegrovanihposlug AT zaytsevaeye vikoristannâaparatuídempotentnihalgebrdlâanalízuprocesívvmerežíznadannâmíntegrovanihposlug AT kovalenkoeg vikoristannâaparatuídempotentnihalgebrdlâanalízuprocesívvmerežíznadannâmíntegrovanihposlug |