Использование аппарата идемпотентных алгебр для анализа процессов в сети с предоставлением интегрированных услуг
Показано применение уравнений «min-plus» алгебры для анализа сети с предоставлением интегрированных услуг. Рассмотрена работа протокола RSVP. Показана возможность управления ресурсами сети в зависимости от требований к задержке по типу трафика. Предложен вариант расчета маршрута передачи с учетом ог...
Saved in:
| Published in: | Системні дослідження та інформаційні технології |
|---|---|
| Date: | 2011 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/50096 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Использование аппарата идемпотентных алгебр для анализа процессов в сети с предоставлением интегрированных услуг / В.И. Бессараб, Э.Е. Зайцева, Е.Г. Коваленко // Систем. дослідж. та інформ. технології. — 2011. — № 2. — С. 35-40. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859693649572397056 |
|---|---|
| author | Бессараб, В.И. Зайцева, Э.Е. Коваленко, Е.Г. |
| author_facet | Бессараб, В.И. Зайцева, Э.Е. Коваленко, Е.Г. |
| citation_txt | Использование аппарата идемпотентных алгебр для анализа процессов в сети с предоставлением интегрированных услуг / В.И. Бессараб, Э.Е. Зайцева, Е.Г. Коваленко // Систем. дослідж. та інформ. технології. — 2011. — № 2. — С. 35-40. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | Показано применение уравнений «min-plus» алгебры для анализа сети с предоставлением интегрированных услуг. Рассмотрена работа протокола RSVP. Показана возможность управления ресурсами сети в зависимости от требований к задержке по типу трафика. Предложен вариант расчета маршрута передачи с учетом ограничений на задержку.
Показано застосування рівнянь «min-plus» алгебри для аналізу мережі з наданням інтегрованих послуг. Розглянуто роботу протоколу RSVP. Показано можливість керування ресурсами мережі в залежності від вимог до затримки за типом трафіку. Запропоновано варіант розрахунку маршруту передачі з урахуванням обмежень на затримку.
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-11-30T23:35:34Z |
| 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 | nasplib_isofts_kiev_ua-123456789-50096 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-11-30T23:35:34Z |
| publishDate | 2011 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Бессараб, В.И. Зайцева, Э.Е. Коваленко, Е.Г. 2013-10-04T22:12:55Z 2013-10-04T22:12:55Z 2011 Использование аппарата идемпотентных алгебр для анализа процессов в сети с предоставлением интегрированных услуг / В.И. Бессараб, Э.Е. Зайцева, Е.Г. Коваленко // Систем. дослідж. та інформ. технології. — 2011. — № 2. — С. 35-40. — Бібліогр.: 4 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/50096 621.391.512 Показано применение уравнений «min-plus» алгебры для анализа сети с предоставлением интегрированных услуг. Рассмотрена работа протокола RSVP. Показана возможность управления ресурсами сети в зависимости от требований к задержке по типу трафика. Предложен вариант расчета маршрута передачи с учетом ограничений на задержку. Показано застосування рівнянь «min-plus» алгебри для аналізу мережі з наданням інтегрованих послуг. Розглянуто роботу протоколу RSVP. Показано можливість керування ресурсами мережі в залежності від вимог до затримки за типом трафіку. Запропоновано варіант розрахунку маршруту передачі з урахуванням обмежень на затримку. 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. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Использование аппарата идемпотентных алгебр для анализа процессов в сети с предоставлением интегрированных услуг Використання апарату ідемпотентних алгебр для аналізу процесів в мережі з наданням інтегрованих послуг Usage of the apparatus of idempotent algebra for the analysis of the processes in network with the provision of integrated services Article published earlier |
| spellingShingle | Использование аппарата идемпотентных алгебр для анализа процессов в сети с предоставлением интегрированных услуг Бессараб, В.И. Зайцева, Э.Е. Коваленко, Е.Г. Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| 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 | использование аппарата идемпотентных алгебр для анализа процессов в сети с предоставлением интегрированных услуг |
| topic | Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| topic_facet | Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50096 |
| work_keys_str_mv | AT bessarabvi ispolʹzovanieapparataidempotentnyhalgebrdlâanalizaprocessovvsetispredostavleniemintegrirovannyhuslug AT zaicevaée ispolʹzovanieapparataidempotentnyhalgebrdlâanalizaprocessovvsetispredostavleniemintegrirovannyhuslug AT kovalenkoeg ispolʹzovanieapparataidempotentnyhalgebrdlâanalizaprocessovvsetispredostavleniemintegrirovannyhuslug AT bessarabvi vikoristannâaparatuídempotentnihalgebrdlâanalízuprocesívvmerežíznadannâmíntegrovanihposlug AT zaicevaée vikoristannâaparatuídempotentnihalgebrdlâanalízuprocesívvmerežíznadannâmíntegrovanihposlug AT kovalenkoeg vikoristannâaparatuídempotentnihalgebrdlâanalízuprocesívvmerežíznadannâmíntegrovanihposlug AT bessarabvi usageoftheapparatusofidempotentalgebrafortheanalysisoftheprocessesinnetworkwiththeprovisionofintegratedservices AT zaicevaée usageoftheapparatusofidempotentalgebrafortheanalysisoftheprocessesinnetworkwiththeprovisionofintegratedservices AT kovalenkoeg usageoftheapparatusofidempotentalgebrafortheanalysisoftheprocessesinnetworkwiththeprovisionofintegratedservices |