Метод динамического перераспределения потоков между портами устройства пакетной коммутации, позволяющий увеличить загрузку сетевого оборудования
Предложенный метод динамического перераспределения потоков между портами устройства пакетной коммутации, который позволяет увеличить допустимую нагрузку сетевого оборудования без существенного ухудшения качества предоставления сетевых услуг. Метод базируется на поточной сплайн-интерполяции в реаль...
Збережено в:
| Дата: | 2005 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2005
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/2399 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод динамического перераспределения потоков между портами устройства пакетной коммутации, позволяющий увеличить загрузку сетевого оборудования / Г.Ф. Конахович, И.В. Вербицкий// Мат. машини і системи. — 2005. — N 1. — С. 148-160. — Бібліогр.: 11 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859861810736267264 |
|---|---|
| author | Конахович, Г.Ф. Вербицкий, И.В. |
| author_facet | Конахович, Г.Ф. Вербицкий, И.В. |
| citation_txt | Метод динамического перераспределения потоков между портами устройства пакетной коммутации, позволяющий увеличить загрузку сетевого оборудования / Г.Ф. Конахович, И.В. Вербицкий// Мат. машини і системи. — 2005. — N 1. — С. 148-160. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| description | Предложенный метод динамического перераспределения потоков между портами устройства пакетной коммутации, который
позволяет увеличить допустимую нагрузку сетевого оборудования без существенного ухудшения качества предоставления
сетевых услуг. Метод базируется на поточной сплайн-интерполяции в реальном времени динамических характеристик
пульсаций трафика на портах пакетного коммутатора и на адаптивном авторегулировании полос пропускания портов
коммутатора в зависимости от характеристик пульсаций трафика. Выбранный способ полиномиальной сплайн-
интерполяции позволяет получить необходимую точность аппроксимации реальных пульсаций трафика. Для сокращения
объёма обрабатываемых данных в процессе интерполяции предлагается использовать известные методы разряжения
экспериментальных данных. Приведенные примеры правил авторегулирования полосы пропускания портов коммутатора
реализующего данный метод.
Запропонований метод динамічного перерозподілу потоків між портами пакетної комутації, що дозволяє збільшити
припустиме навантаження мережевого обладнання без суттєвого погіршення якості мережевих послуг, які надаються. Метод
базується на поточній сплайн-інтерполяції у реальному часі динамічних характеристик пульсації трафіка на портах пакетного
комутатора та на адаптивному авторегулюванні смуг пропускання портів комутатора в залежності від характеристик
пульсацій трафіка. Обраний спосіб поліноміальної сплайн-інтерполяції дозволяє отримати необхідну точність апроксимації
реальних пульсацій трафіка. Для скорочення обсягу оброблювальних даних у процесі інтерполяції пропонується
використовувати відомі методи прорідження експериментальних даних. Наведені приклади правил авторегулювання
смугами пропускання портів комутатора, що реалізують розглянутий метод
The offered method of dynamic redistribution of flows between ports of the device of batch switching, which allows to increase a safe
load of the network equipment without essential deterioration of quality of the given network services. The method is based on
current spline-interpolation in real time of dynamic characteristics of a pulsation of traffic on ports of the batch switchboard and on
adaptive auto regulation of passbands of ports of the switchboard depending on the characteristics of a pulsation of traffic. The
chosen way polynominal spline - interpolation allows to receive necessary accuracy of approximation of real pulsations of traffic. For
reduction of volume processable given during interpolation it is offered to use known methods of underpressure of experimental data.
The given examples of rules of auto regulation by passbands of ports of the switchboard, which realize the considered method.
|
| first_indexed | 2025-12-07T15:46:17Z |
| format | Article |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
148
УДК 681. 324. 658
Г.Ф. КОНАХОВИЧ, И.В. ВЕРБИЦКИЙ
МЕТОД ДИНАМИЧЕСКОГО ПЕРЕРАСПРЕДЕЛЕНИЯ ПОТОКОВ МЕЖДУ
ПОРТАМИ УСТРОЙСТВА ПАКЕТНОЙ КОММУТАЦИИ, ПОЗВОЛЯЮЩИЙ
УВЕЛИЧИТЬ ЗАГРУЗКУ СЕТЕВОГО ОБОРУДОВАНИЯ
Abstract: The offered method of dynamic redistribution of flows between ports of the device of batch switching, which
allows to increase a safe load of the network equipment without essential deterioration of quality of the given network
services. The method is based on current spline-interpolation in real time of dynamic characteristics of a pulsation of
traffic on ports of the batch switchboard and on adaptive auto regulation of passbands of ports of the switchboard
depending on the characteristics of a pulsation of traffic. The chosen way polynominal spline-interpolation allows to
receive necessary accuracy of approximation of real pulsations of traffic. For reduction of volume processable given
during interpolation it is offered to use known methods of underpressure of experimental data. The given examples of
rules of auto regulation by passbands of ports of the switchboard, which realize the considered method.
Key words: traffic, spline-interpolation.
Анотація: Запропонований метод динамічного перерозподілу потоків між портами пакетної комутації, що
дозволяє збільшити припустиме навантаження мережевого обладнання без суттєвого погіршення якості
мережевих послуг, які надаються. Метод базується на поточній сплайн-інтерполяції у реальному часі
динамічних характеристик пульсації трафіка на портах пакетного комутатора та на адаптивному
авторегулюванні смуг пропускання портів комутатора в залежності від характеристик пульсацій трафіка.
Обраний спосіб поліноміальної сплайн-інтерполяції дозволяє отримати необхідну точність апроксимації
реальних пульсацій трафіка. Для скорочення обсягу оброблювальних даних у процесі інтерполяції
пропонується використовувати відомі методи прорідження експериментальних даних. Наведені приклади
правил авторегулювання смугами пропускання портів комутатора, що реалізують розглянутий метод.
Ключові слова: трафік, сплайн-інтерполяція.
Аннотация: Предложенный метод динамического перераспределения потоков между портами
устройства пакетной коммутации, который позволяет увеличить допустимую нагрузку сетевого
оборудования без существенного ухудшения качества предоставления сетевых услуг. Метод базируется
на поточной сплайн-интерполяции в реальном времени динамических характеристик пульсаций трафика
на портах пакетного коммутатора и на адаптивном авторегулировании полос пропускания портов
коммутатора в зависимости от характеристик пульсаций трафика. Выбранный способ полиномиальной
сплайн-интерполяции позволяет получить необходимую точность аппроксимации реальных пульсаций
трафика. Для сокращения объёма обрабатываемых данных в процессе интерполяции предлагается
использовать известные методы разряжения экспериментальных данных. Приведенные примеры правил
авторегулирования полосы пропускания портов коммутатора реализующего данный метод.
Ключевые слова: трафик, сплайн-интерполяция.
1. Введение
Одна из основных проблем управления ресурсами любой телекоммуникационной сети с
коммутацией пакетов (далее сети) – определение компромисса между допустимым уровнем
загрузки пользовательским трафиком сетевого оборудования и приемлемым уровнем качества
предоставления сетевых услуг. В обычной ситуации с целью улучшения экономических
показателей оператор сети стремится к наиболее полной загрузке сетевого оборудования (в
первую очередь, пакетных коммутаторов, маршрутизаторов и каналов передачи данных) для того,
чтобы обеспечить транспортировку возможно больших объёмов информации в единицу времени в
пересчёте на единицу стоимости используемого оборудования. Однако такой феномен как
пульсации потоков данных, которые почти всегда существуют в пакетных сетях, не позволяет
добиться качественного обслуживания в условиях, когда уровень нагрузки на элементы сети
превышает некоторый пороговый диапазон значений. Поэтому на практике даже в хорошо
оптимизированных сетях коэффициент загрузки оборудования в среднем не превышает 0,4
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
149
(приходится резервировать активные сетевые ресурсы для того, чтобы во время повышенных
пульсаций трафика качество обработки пакетов не снижалось ниже требуемого уровня). Работа
пакетной сети считается эффективной, если каждый её ресурс является существенно
загруженным, но не перегруженным. Обоснованный выбор величины коэффициента загрузки
ресурса с учетом тонкой структуры условий его использования имеет решающее значение при
оптимизации работы сети, поскольку величина этого коэффициента непосредственно влияет на
длину очередей пакетов к ресурсу, величину задержек пакетов в очередях и, в конечном счете, на
качество предоставления сетевых услуг. Поэтому в процессе совершенствования работы сети
пытаются найти разумный компромисс в достижении двух противоположных целей, суть которых
состоит в следующем. С одной стороны, стремятся улучшить качество обработки трафика, то есть
снизить задержки в продвижениях пакетов и уменьшить потери пакетов, что на практике
достигается, в основном, за счет резервирования ресурсов каналов передачи и коммутирующих
устройств. С другой стороны, пытаются, в меру возможностей, увеличить загрузку ресурсов сети с
целью улучшения экономических показателей их использования. Компромисс в достижении
вышеуказанных целей составляет основное содержание инженерии трафика.
До недавнего времени решение вышеуказанной задачи искали на путях использования
средств и механизмов борьбы с перегрузками в сети [1,2, 3], а именно:
1) осуществляли рациональную настройку параметров сетевого оборудования с целью
ограничения неуправляемого увеличения интенсивностей входных потоков на портах
коммутирующих устройств;
2) реализовывали разнообразные алгоритмы управления очередями;
3) оптимизировали маршруты прохождения трафика через сеть (другими словами,
осуществляли инженерию трафика).
Тем не менее активное применение всех этих механизмов, как показывает
эксплуатационная практика, позволяет увеличить коэффициент загрузки сетевого оборудования в
среднем лишь до величины 0,5 – 0,55, не больше. Поэтому разработка методов управления
ресурсами сети, позволяющих обеспечить дальнейшее увеличение загрузки дорогостоящего
сетевого оборудования без заметного снижения качества сетевых услуг, является актуальной
задачей.
2. Суть предлагаемого метода
В данной работе с целью обеспечения возможности увеличения допустимого коэффициента
загрузки оборудования без существенного снижения качества обслуживания в сетях с пакетной
коммутацией предлагается использовать механизм адаптивного динамического
перераспределения ресурсов сети в процессе её функционирования по критерию максимизации
загрузки на основе использования данных, получаемых в процессе мониторинга характеристик
потоков пакетов в реальном масштабе времени. В частности, предлагается динамически
перераспределять пропускную способность пакетного коммутатора (или маршрутизатора) между
его портами в зависимости от текущей загрузки трафиком этих портов. Пропускная способность
коммутирующего устройства перераспределяется между его портами пропорционально текущим
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
150
величинам интенсивностей потоков пакетов, поступающим на эти порты. Такой подход, как
показывают результаты моделирования, позволит увеличить коэффициент загрузки
коммутирующего оборудования в сети во многих практически возникающих ситуациях до величин
порядка 0,65 – 0,7.
Так, например, если мгновенная интенсивность потока пакетов на каком-либо порте в
определённых пределах увеличивается, а загрузка остальных портов существенно не изменяется
(или даже уменьшается), то этому порту «мгновенно» выделяется большая доля пропускной
способности коммутатора за счет уменьшения долей пропускной способности коммутатора,
выделяемых другим портам. В противном случае, если поток пакетов на каком-либо из портов
уменьшается при неизменной или увеличивающейся нагрузке на других портах, то,
соответственно, уменьшается и доля пропускной способности коммутатора, которая этому порту
выделяется. Соответственно, появляется возможность увеличения пропускных способностей
(полос пропускания) других портов. При этом динамика процесса перераспределения при
определённых ограничениях должна совпадать с динамикой пульсаций трафика на управляемых
портах коммутатора. Такое перераспределение разумно осуществлять не только на основе
определения текущего состояния характеристик потоков пакетов, поступающих на порты
коммутатора, но и путём использования результатов прогнозирования характера изменений
интенсивностей этих потоков. Прогнозирование «поведения» потоков пакетов на портах
коммутатора позволяет повысить динамические характеристики системы автоматического
регулирования и, в конечном счете, повысить коэффициент загрузки сетевого оборудования.
Вышеизложенное является упрощённым пояснением основной идеи адаптивного
регулирования пропускными способностями (или, как говорят, полосами пропускания) портов
коммутатора по критерию максимизации допустимой загрузки коммутатора. На практике
необходимо учитывать ряд условий, характерных для задач управления трафиковыми нагрузками:
классификация трафика, установление приоритетов классам трафика, выбор механизмов
управления очередями и т.п.
В качестве объектов регулирования при оптимизации загрузки сети целесообразно
выбирать наиболее дорогостоящие и высокопроизводительные элементы сетевого оборудования,
в первую очередь, магистральные коммутаторы и маршрутизаторы, а также, во многих случаях,
граничные коммутаторы и маршрутизаторы абонентского доступа, работающие с
производительностью от единиц до сотен миллионов пакетов в секунду. Особенно эффективно
использование рассматриваемого метода в сетях, трафик которых имеет ярко выраженный
пульсирующий характер с большими, но спорадическими всплесками.
3. Основные пути реализации метода
Известные методы кондиционирования трафика на портах коммутирующего устройства [1,2] не
могут быть использованы для решения задачи динамического перераспределения пропускной
способности коммутатора между его портами. Трудности состоят в том, что современный пакетный
коммутатор (магистральный или граничный) – это высокоскоростная система. Поэтому для того,
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
151
чтобы обеспечить возможность фиксации в реальном времени текущих значений его параметров,
связанных с обработкой динамических характеристик пульсаций пакетного трафика, необходимо
накапливать и обрабатывать значительные объёмы данных, что требует значительных затрат
вычислительных ресурсов. В данном случае такими ресурсами являются объём памяти в общей
справочной службе сети (Directory Service), в которой сохраняются разнообразные данные о
текущем состоянии сети (в частности, данные службы Q0S), и затраты времени на необходимую
обработку этих данных. При приемлемых затратах вышеназванных ресурсов сомнительно, чтобы
удалось в реальном времени определить все необходимые для кондиционирования трафика
параметры. Поэтому существенный интерес представляют методы высокоскоростной обработки
трафика, которые позволяют выполнить профилирование и формирование трафика на
относительно небольших объёмах данных.
В данной работе динамическое регулирование полос пропускания портов коммутатора
предлагается выполнять на основе «прореженных» данных мониторинга характеристик потоков
пакетов на его портах. Эти «прореженные» данные предлагается использовать для построения в
реальном времени функциональных аналитических зависимостей, аппроксимирующих реальные
зависимости значений динамических характеристик потоков от времени. Аппроксимацию
предлагается осуществлять путём сплайн-интерполяции данных мониторинга трафиков (точнее,
данных, полученных в результате измерений динамических характеристик потоков пакетов) на
портах коммутатора с использованием, например, кусочно-полиномиальных сплайнов для
непериодических функций. Методы сплайн-интерполяции подробно изложены во многих
монографиях, посвящённых теории функций, в частности в [4, 5].
4. Математическая основа метода
Физическая природа пульсаций трафика на портах коммутатора носит случайный и, к сожалению,
во многих случаях непредсказуемый характер, обусловленный нерегулярностью и
непредсказуемостью генерации потоков данных на терминальных узлах сети [6]. Тем не менее,
любая телекоммуникационная сеть – это физическая инерционная система. Поэтому при
постановке и выборе методов предсказания «поведения» потоков пакетов на портах коммутатора
можно использовать известные методы решения задач прогнозирования, разработанные для
физических систем с быстропротекающими случайными процессами. В частности, в качестве
динамической характеристики (динамической функции) случайного процесса ( )tv , «поведение»
которого предстоит предсказать и отобразить в аналитической форме, удобно взять количество
пакетов, приходящих на порт коммутатора, как функцию времени. Кроме того, как будет показано
далее, удобно ввести в рассмотрение первые две производные от ( )tv , т.е. случайную скорость
потока пакетов ( ) ( ) dttdvtb /= и случайное ускорение потока ( ) ( ) 221 / dttvdtb = .
Первым шагом в решении задачи определения и прогнозирования «поведения» потока
пакетов на каком-либо из портов коммутатора является аппроксимация данных мониторинга
значений ( )tv . Такую аппроксимацию предлагается выполнить на основе сплайн-интерполяции, а
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
152
для интерполяции взять конструкцию полиномиальных сплайнов относительно непериодических
функций. Как показано в [7], сплайн-подход к задаче аппроксимации в пространстве [ ]cTtL ,02 для
сплайнов степени n и набора узлов интерполяции [ ]nii tttt ,...,,...,0∈ , где і = 1, 2, …, n, даёт
меньшую ошибку аппроксимации в смысле нормы [ ]cTtL ,02 , чем разложение в ряд по многим
другим ортогональным базисам (Эрмита, Лагерра, Чебышева и т.д.).
Если бы функцию ( )tv можно было непрерывно дифференцировать неограниченное число
раз, то разумно выбрать сплайны тригонометрического вида. Однако анализ характера пульсаций
трафика позволяет лишь надеяться, что ( )tv можно непрерывно дифференцировать не более s
раз, где значение s априори неизвестно и его приходится выбирать, исходя из конкретных
условий применения коммутатора. В такой ситуации, как показано в [8], целесообразно
использовать кусочно-полиномиальные сплайны вида
),,(),(~
12 ktQstv s+= [ ],, 1+∈ kk ttt Кк ...,1,0 ±= , (1)
где ktQ s ,(12 + ) – полином степени не выше 12 +s , определяемый равенствами:
,
),(
),(12
k
jk
ktt tt
m
ts
m
m
s
m
dt
vtPd
dt
ktQd
=
+ =
=
где sKm ,...,...2,1= ; (2)
,
),(),(
1
1
1
12
+
+
+= =
+ =
k
jk
ktt tt
m
ts
m
m
s
m
dt
vtPd
dt
ktQd
где sKm ,...,...2,1= . (3)
В выражениях (1) – (3) предполагается, что сплайн имеет непрерывные производные
степени s , заданы узлы интерполяции λt и значения функции
λλ t
vtv =)( в них j – натуральное
число в диапазоне 10 −≤≤ sj . Каждой точке λt сопоставлен интерполяционный
полином ),,(
λts vtP построенный по значениям ( )jtv −λ , ( )1+− jtv λ , K , ( )sjtv +−λ в узлах jt −λ , 1+− jtλ ,
K , .sjt +−λ
Часто полином ),(12 ktQ s+ представляют в виде суммы классического интерполяционного
полинома ),(
jks vtP и поправки к нему ),(12 ktR s+ , т.е.
),(12 ktQ s+ = ).,(),( 12 ktRvtP sks j ++ (4)
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
153
Поправка согласно [8] представляется в виде
,,),...,...,,,()(),(
1
1211
1
112
−
−−=
+
+++−+−−
+
++ k
tt
tt
qtKttvttktR
kk
k
ssjkjkjk
s
kks (5)
где ),,,( 11 ++−+−− sjkjkjk tKttv – разностное отношение порядка 1+s и
;
),(),(
1
0
)(
1111
1
12
kk
k
r
s
r
r
Tkk
kijk
s
ikk
jkjsk
s
tt
tt
T
T
tt
tt
T
tt
tt
kTq
−
−=
−
−
−
−
−
=
+
= =+
+−
=+
−+−+
+ ∑ Π λ
(6)
∑
−
=
+
−+−−=
rs
m
mm
rs
r T
m
ms
sr
TT
T
0
1
,)1(
!
)!(
)1(
!!
)1(
)(λ (7)
[ ] )(
1
r
T =Κ означает производную по T порядка r , вычисленную при 1=T .
Если на рассматриваемом временном отрезке [ ] [ ],,, 01 cjj Tttt ⊂+ 1−≤≤ Njo известны
значения )(tv в )1( +n -ой точке, а функция [ ]1,)( +∈ jj
n ttCtv , то интерполяционная
формула представляется в виде полинома Лагранжа степени n .
Погрешность интерполяционной формулы в общем случае оценивают по значению невязки
)(~)()( tvtvtRn −= на временном отрезке [ ]1, +jj tt как
[ ]1,
sup)(
+∈
≤
jj ttt
n tR
)!1(
)()(
1
1
+
⋅+
+
n
t
dt
tdv n
n
n ω
, где =)(tnω .)(
0
∏
=
−
n
i
itt (8)
Интерес представляет также оценка погрешности производных от динамической
характеристики потока пакетов. Для этого, следуя [8], обозначим рассматриваемый временной
отрезок следующим образом:
[ ] [ ] [ ]cmininjj Tttttt ,,, 011 ⊂= ++−−+ , miNn ≤≤−≤≤ 0,10 .
И далее будем считать, что функция ( )tv на этом временном отрезке имеет ограниченную
производную порядка 1+m . Тогда погрешность производных от ( )tv на отрезках
[ ] [ ]cnn Tttt ,, 01 ⊂+ определяется следующим соотношением [9]:
)(~)( tv
dt
d
tv
dt
d
s
s
s
s
−
s
nn
m
immin
tt
tt
const
)(
)(
1
1
1
−
−≤
+
+
−++− x )(max
1
1
1
tv
dt
d
m
m
ttt minin
+
+
≤≤ ++−−
, (9)
где mKs ,,1,0= ; .0 mi ≤≤
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
154
5. Схема реализации метода
С учётом вышеизложенного представляется такая схема динамического перераспределения
пропускной способности коммутирующего устройства между его портами.
Первым обязательным элементом процесса авторегулирования полос пропускания портов
коммутатора является мониторинг потоков пакетов на всех его портах в пределах наблюдаемого
временного отрезка [ ]cTt ,0 . Мониторингу подвергается динамическая характеристика потока
пакетов на каждом из портов. Процесс мониторинга, отображенный на верхней строке рис. 1,
представляет собой последовательно выполняемую во времени итеративную процедуру,
состоящую из конечного числа шагов.
1шаг
процедуры
Последовательность итеративного процесса авторегулирования
0 1 2 3 4 k k+1
t0
(1)
n-1 n 0 1 2 3 k k+1 n-1 n
Tc
Измерение Измерение
Пред-
сказание Пред-
сказание
ν(ti)
ν'(ti)
ν"(ti)
t
t
t
t0
(2) t0
(3)
t0
(i) t0
(i+1) t0
(i+2)
Управ-
ление
Управ-
ление
t
(+)
(-)
0
Рис.1. Иллюстрация процедуры реализации метода динамического перераспределения
пропускной способности коммутатора между его портами
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
155
Первый шаг процедуры начинается в момент
( )1
0t , второй шаг – в момент
( )2
0t , i - ый шаг – в
момент
( )it0 и т.д. В свою очередь, с целью осуществления полиномиальной сплайн-интерполяции
длительность каждого шага процедуры разбивается на ещё более малые временные интервалы 1,
2, 3, …, К, …, n, где K – количество измерений функции ( )tv на i-ом шаге, а n – общее количество
узлов интерполяции (совпадающее со степенью интерполяционного полинома). Другими словами,
с некоторым весьма малым интервалом времени внутри каждого шага итеративной процедуры,
выбор которого выполняется исходя из рассмотренных выше условий (см. вторую строку сверху на
рис. 1), на каждом из портов коммутатора последовательно во времени берётся K отсчётов
«мгновенных» значений динамической характеристики потока ( )tv . И далее по измеренным
данным выполняется аппроксимация случайной функции ( )tv рассмотренным выше методом
полиномиальной сплайн-интерполяции. Берётся полином n-й степени. Значения отсчетов для
первых K узлов интерполяции измеряются, а значения остальных ( )Kn − узлов предсказываются.
Затем на втором шаге итеративной процедуры выполняется аппроксимация на следующих K
узлах интерполяции с предсказанием «поведения» потока в следующих ( )Kn − узлах и т.д.,
вплоть до момента времени
с
Т . Как видно из рис. 1, на каждом шаге первые K временных
промежутка связаны с получением данных о реальном «поведении» функции ( )tv , а следующие
временные промежутки, идущие после K -го, в количестве ( )Kn − связаны с прогнозированием
«поведения» функции ( )tv . После накопления необходимых данных (т.е., сразу после окончания
K -го отсчета динамической характеристики) на каждом шаге итеративной процедуры выполняются
полиномиальная аппроксимация и предсказание рассмотренным выше способом. В результате
находится в аналитической форме приемлемое приближение к действительной зависимости
динамической характеристики каждого из потоков от текущего времени.
В качестве критерия точности интерполяции удобно использовать критерий nε –
ограниченной невязки:
[ ] ,)(),( nm tPtvp ε≤ [ ]1, +∈ nn ttt , (10)
где )(tv – значение динамической характеристики потока; )(tPm – полиномиальный
интерполянт динамической характеристики потока; [ ]⋅p – заданное расстояние в соответствующем
метрическом пространстве. Критерий nε – ограниченной невязки запишем в виде
[ ]
.)()(sup
1,
nm
ttt
tPtv
nn
ε≤−
+∈
(11)
Интерполирующий полином )(tPm выбирается минимальной степени, т.е. minmm = . Выбор
осуществляется по следующему критерию:
)(minargmin tPm n= . (12)
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
156
Введя новое обозначение
[ ]
)(sup
1,
tv
dt
d
M m
m
ttt
m
nn +∈
= (13)
и используя соотношение (8) вместо (11), критерий nε – ограниченной невязки записывают в виде
[ ] [ ]
nm
ttt
m
m
ttt
t
m
M
tPtv
nnnn
εω ≤
+
≤−
+= ∈
+
∈
)(sup
)!1(
)()(sup
11 ,
1
,
. (14)
Задаваясь значением ,nε из (14) можно численным путем подобрать такие значения m и
1+mM , при которых будет обеспечиваться требуемая точность интерполяции. При этом значение
шага t Кitt ii ,...2,1,1 =−+ выбирают таким образом, чтобы уменьшить значение погрешности
интерполяции, а именно, чтобы узлы интерполяции совпадали с корнями многочлена Чебышева. В
этом случае
mi
m
itttt
t nnnn
i ,,2,1,
2
12
cos
22
11 Κ=
−−−+= ++ π (15)
и при оценке сверху величины )(1 tm+ω можно воспользоваться следующей формулой:
.
4
2)(sup 1
m
nn
m
t
tt
t
−≤ +ω (16)
При реализации во времени быстроизменяющихся динамических характеристик потоков
приходится фиксировать значительные объёмы данных, что может существенно загрузить
вычислительные ресурсы коммутатора. Поэтому в процессе аппроксимации целесообразно
использовать предложенный в [10] способ прореживания данных, который позволяет без
ухудшения точности интерполяции существенно сократить объёмы необходимых измерений.
Рассмотрим ситуацию, когда значения некоторой функции )(tv в моменты времени srt +
фиксируются и запоминаются, а промежуточные )( srtv + восстанавливаются по какой-либо
интерполяционной формуле, причем Rr ,...1,0= , ,...,1,0=s maxs . Сначала за ( 1)1max ++ Rs
моментов времени 1+R значений функции фиксируются и запоминаются, а Rsmax значений
затем восстанавливаются приближенно.
Суммарная ошибка может быть определена в одной из двух метрик:
∑∑
−
= =
++ −=
1
0 0
1
max
)()(
R
r
s
s
srsrms tvtPε ; (17)
.)()(
2
1
1
0 0
2
max
−= ∑∑
−
= =
++
R
r
s
s
srsrms tvtPε (18)
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
157
Далее после нахождения аппроксимирующей функции на каждом шаге итеративной
процедуры находятся приближения в аналитической форме для первой и второй производной от
полученного аналитического выражения, аппроксимирующего )(tv , т.е. находятся приближенные
выражения для скорости потока пакетов ( )tb и для ускорения потока ( )tb1 . Значения этих
производных от функции )(tv в узлах интерполяции, полученные на каждом шаге итеративной
процедуры, являются исчерпывающей информацией для управления регуляторами службы QoS
(Quality of Service). Нижние три строки на рис. 1 отображают соответственно отсчёты случайных
функций )(tv , ( )tb и ( )tb1 на первом шаге итеративной процедуры. Как корректно распорядиться
этой информацией в целях рационального перераспределения пропускной способности
коммутатора между его портами? Какие с этой целью синтезировать правила управления
механизмами регулирования? Ответы на эти вопросы зависят от многих факторов, анализ которых
выходит за рамки данной статьи. В принципе, знание значений производных динамических
характеристик потоков пакетов в узлах интерполяции на каждом шаге итеративной процедуры и
для каждого из портов коммутатора позволяет осуществить постановку и решение задачи синтеза
оптимальной структуры системы авторегулирования механизмом перераспределения пропускной
способности коммутатора, например, на основе метода динамического программирования
Р. Бэллмана. Однако в эксплуатационной практике часто можно удовлетвориться более простыми,
хотя и менее эффективными, правилами управления механизмами регулирования.
Оценки производных сплайн-интерполяции динамической характеристики потока )(tv ,
согласно (9), в случае постоянного шага hNtTtt cnn =−=−+ /)( 01 гарантируют сходимость
)(~ tv
dt
d
s
s
к )(tv
dt
d
s
s
с порядком msh sm ,,1,0,1 Κ=++ [9].
Развивая подход на основе критерия nε – ограниченной невязки на производные сплайн-
интерполяции можно записать критерий точности в следующем виде:
[ ] [ ] .,,1,0,,, 1
1 msttth nn
s
n
sm Κ=≤ +
++ εε (19)
Последовательно оценивания значения [ ]s
nε для выбранных значений s , из (19) можно
численным путем подобрать такое значение ,1 smh −+ при котором будет обеспечиваться высокая
точность производных сплайн-интерполяции. При этом значение шага nn tt −+1 будем выбирать
таким образом, чтобы уменьшить значение погрешности производных сплайн-интерполяции,
изменяя, при необходимости, представление временного интервала [ ] [ ]1
1
0
0 ,, +
−
=
Υ= nn
N
n
tttt и повторяя
всю рассмотренную здесь последовательность действий. В итоге можно определить
полиномиальную сплайн-интерполяцию, обладающую высокой точностью аппроксимации как
самой динамической характеристики )(tv , так и ее производных.
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
158
В качестве примера относительно простой схемы регулирования, использующей
информацию только о значениях второй производной динамических характеристик потоков на
портах коммутатора, но с использованием знания о «будущем поведении» этих потоков, можно
предложить следующее.
Чтобы использовать всю информацию об ускорениях потока на r-ом порте как измеренную,
так и предсказанную на каком-либо і-ом шаге итеративной процедуры регулирования,
проинтегрируем значения полученного приближения для второй производной динамической
характеристики этого потока по всем n узлам интерполяции на рассматриваемом шаге итерации:
,)(
)(
)(
0
" dttI l
t
t
rr
i
n
i
∫= ν (20)
где lt – узлы интерполяции; [ ])()()(
2
)(
1
)(
0 ,...,...,, i
n
i
k
iii
l tttttt ∈ ; r – номер порта коммутатора;
)(i – номер шага итеративной процедуры.
Если окажется, что I 0>r , то можно утверждать, что на r-ом порте коммутатора в среднем
существует тенденция к возрастанию интенсивности потока пакетов (при этом учитывается как
реально наблюдаемое, так и прогнозируемое «поведение» потока). Если окажется, что I 0<r , то
можно утверждать, что на r-ом порте коммутатора в среднем существует тенденция к уменьшению
интенсивности потока пакетов. Если I 0=r , то интенсивность потока в среднем не изменяется. С
учетом вышеизложенного, можно предложить такое правило регулирования механизмом
перераспределения пропускной способности коммутатора между его портами. Если на каком- либо
r-ом порте окажется I 0<r , а на этом же шаге итеративного процесса на каком-либо ином,
например, p-ом порте окажется I 0>r , то заранее обусловленная часть ширины полосы r-го порта
отнимается от этого порта и прибавляется к имеющейся ширине полосы p-го порта. В любом ином
случае перераспределение ресурса коммутатора не выполняется. Заметим, что сам механизм
перераспределения выполняется штатными средствами оборудования, реализующего почти
любую современную телекоммуникационную технологию. Наиболее развит такой механизм в
технологии АТМ [3].
Можно предложить и другое правило регулирования. Если вычисленное значение
интеграла от ( )tb1 на одном из портов коммутатора оказалось с положительным знаком и достигло
заранее определённого порогового уровня при условии, когда на остальных портах коммутатора
интегральные значения ускорения потоков не претерпели существенных изменений, то в
коммутаторе активизируется механизм перераспределения пропускной способности в направлении
увеличения ширины полосы того порта, на котором зафиксировано увеличение интегрального
значения второй производной от динамической характеристики потока. Точнее, механизм
перераспределения активизируется в момент достижения определённого для этой производной
порогового уровня. Пороговые уровни, в свою очередь, определяются экспериментальным путём в
процессе функционирования коммутатора с учетом реальных условий его эксплуатации. В
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
159
противном случае, когда интегральное значение второй производной будет существенно
возрастать, но с минусовым знаком, то механизм перераспределения начнёт уменьшать ту часть
пропускной способности коммутатора, которая временно «прикреплена» к данному порту в пользу
других портов.
Система управления коммутатором на каждом шаге итеративной процедуры должна
успевать выполнить, прежде чем начнётся следующий шаг процедуры, все необходимые
вычисления, связанные с построением необходимых аналитических выражений, их
математическими преобразованиями и с генерацией сигналов воздействия на исполнительные
механизмы службы QoS в соответствии с принятыми правилами адаптивного регулирования
пропускной способности коммутатора. Такое «успевание» должно достигаться за счёт
рационального выбора необходимой точности аппроксимации данных мониторинга потоков пакетов
на портах коммутатора, степени интерполянта и параметров процедуры прореживания данных.
6. Выводы
Предложен метод динамического перераспределения потоков между портами устройства пакетной
коммутации, позволяющий увеличить допустимую загрузку сетевого оборудования без
существенного ухудшения качества предоставляемых сетевых услуг. Метод основан на текущей
сплайн-интерполяции в реальном времени динамических характеристик пульсаций трафика на
портах пакетного коммутатора и на адаптивном авторегулировании полос пропускания портов
коммутатора в зависимости от характеристик пульсаций трафика. Выбранный способ
полиномиальной сплайн-интерполяции с использованием полинома степени n позволяет путём
целенаправленного выбора узлов интерполяции, варьированием длины временного интервала, на
котором формируется интерполяционный полином, и степенью интерполянта получить
необходимую точность аппроксимации реальных пульсаций трафика. В качестве критерия точности
сплайн-интерполяции предлагается использовать критерии ε -ограниченной невязки. Выбор
управляющих воздействий на исполнительные механизмы системы авторегулирования базируется
не только на апостериорном знании «поведения» потоков пакетов на портах коммутатора, но и на
результатах предсказания «поведения» потоков в будущем. Для сокращения объёма
обрабатываемых данных в процессе интерполяции предложено использовать известные методы
прореживания экспериментальных данных. Представлены примеры правил авторегулирования
полосами пропускания портов коммутатора, которые могут быть применены на практике.
Внедрение предложенного метода в практику управления трафиковыми нагрузками
позволит существенно повысить коэффициент использования сетевого оборудования без
заметного ухудшения качества обработки сетевых нагрузок и предоставляемых
телекоммуникационных услуг.
СПИСОК ЛИТЕРАТУРЫ
1. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. – 2-е
изд. – Санкт-Петербург: Питер, 2003. – 864 с.
2. Олифер В.Г., Олифер Н.А. Новые технологии и оборудование IP-сетей. – Санкт-Петербург: БХВ-Петербург,
2001. – 512 с.
ISSN 1028-9763. Математичні машини і системи, 2005, № 1
160
3. Назаров А.Н., Симонов М.В. АТМ: технология высокоскоростных сетей. – М.: Эко-Трендз, 1997. – 232 с.
4. Корнейчук Н.П. Сплайны в теории приближений. – М.: Наука, 1984. – 352 с.
5. Алберг Дж. Теория сплайнов и её приложения. – М.: Мир, 1972. – 316 с.
6. Корнышев Ю.Н., Пшеничников А.П., Харкевич А.Д. Теория телетрафика: Учебник для вузов. – Москва:
Радио и связь, 1996. – 272 с.
7. Кашин Б.С., Саакян А.А. Ортогональные ряды. – М.: Наука, 1984. – 496 с.
8. Рябенький В.С. Введение в вычислительную математику: Учебное пособие для вузов. – М.: Физматлит,
1994. – 336 с.
9. Каханер Д., Моулер К., Нэш С. Численные методы и математическое обеспечение. – М.: Мир, 1998. – 575 с.
10. Аджемов А.С., Синева И.С. Метод аналогово-цифровых преобразований на основе сплайн-интерполяции.
– М.: Электросвязь, 1998. – № 2. – С. 37 – 39.
11. Клименко В.П. Основные принципы кантиона // Кибернетика. – 1990. – № 2. – С. 49 – 56.
|
| id | nasplib_isofts_kiev_ua-123456789-2399 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-12-07T15:46:17Z |
| publishDate | 2005 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Конахович, Г.Ф. Вербицкий, И.В. 2008-10-07T08:56:24Z 2008-10-07T08:56:24Z 2005 Метод динамического перераспределения потоков между портами устройства пакетной коммутации, позволяющий увеличить загрузку сетевого оборудования / Г.Ф. Конахович, И.В. Вербицкий// Мат. машини і системи. — 2005. — N 1. — С. 148-160. — Бібліогр.: 11 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/2399 681. 324. 658 Предложенный метод динамического перераспределения потоков между портами устройства пакетной коммутации, который позволяет увеличить допустимую нагрузку сетевого оборудования без существенного ухудшения качества предоставления сетевых услуг. Метод базируется на поточной сплайн-интерполяции в реальном времени динамических характеристик пульсаций трафика на портах пакетного коммутатора и на адаптивном авторегулировании полос пропускания портов коммутатора в зависимости от характеристик пульсаций трафика. Выбранный способ полиномиальной сплайн- интерполяции позволяет получить необходимую точность аппроксимации реальных пульсаций трафика. Для сокращения объёма обрабатываемых данных в процессе интерполяции предлагается использовать известные методы разряжения экспериментальных данных. Приведенные примеры правил авторегулирования полосы пропускания портов коммутатора реализующего данный метод. Запропонований метод динамічного перерозподілу потоків між портами пакетної комутації, що дозволяє збільшити припустиме навантаження мережевого обладнання без суттєвого погіршення якості мережевих послуг, які надаються. Метод базується на поточній сплайн-інтерполяції у реальному часі динамічних характеристик пульсації трафіка на портах пакетного комутатора та на адаптивному авторегулюванні смуг пропускання портів комутатора в залежності від характеристик пульсацій трафіка. Обраний спосіб поліноміальної сплайн-інтерполяції дозволяє отримати необхідну точність апроксимації реальних пульсацій трафіка. Для скорочення обсягу оброблювальних даних у процесі інтерполяції пропонується використовувати відомі методи прорідження експериментальних даних. Наведені приклади правил авторегулювання смугами пропускання портів комутатора, що реалізують розглянутий метод The offered method of dynamic redistribution of flows between ports of the device of batch switching, which allows to increase a safe load of the network equipment without essential deterioration of quality of the given network services. The method is based on current spline-interpolation in real time of dynamic characteristics of a pulsation of traffic on ports of the batch switchboard and on adaptive auto regulation of passbands of ports of the switchboard depending on the characteristics of a pulsation of traffic. The chosen way polynominal spline - interpolation allows to receive necessary accuracy of approximation of real pulsations of traffic. For reduction of volume processable given during interpolation it is offered to use known methods of underpressure of experimental data. The given examples of rules of auto regulation by passbands of ports of the switchboard, which realize the considered method. ru Інститут проблем математичних машин і систем НАН України Моделювання і управління великими системами Метод динамического перераспределения потоков между портами устройства пакетной коммутации, позволяющий увеличить загрузку сетевого оборудования Метод динамічного перерозподілу потоків між портами пристрою пакетної комутації, який дозволяє збільшити навантаження мережевого обладнання The offered method of dynamic distribution of flows between ports of the device of batch switching, which allows to increase a safe load of the network equipment Article published earlier |
| spellingShingle | Метод динамического перераспределения потоков между портами устройства пакетной коммутации, позволяющий увеличить загрузку сетевого оборудования Конахович, Г.Ф. Вербицкий, И.В. Моделювання і управління великими системами |
| title | Метод динамического перераспределения потоков между портами устройства пакетной коммутации, позволяющий увеличить загрузку сетевого оборудования |
| title_alt | Метод динамічного перерозподілу потоків між портами пристрою пакетної комутації, який дозволяє збільшити навантаження мережевого обладнання The offered method of dynamic distribution of flows between ports of the device of batch switching, which allows to increase a safe load of the network equipment |
| title_full | Метод динамического перераспределения потоков между портами устройства пакетной коммутации, позволяющий увеличить загрузку сетевого оборудования |
| title_fullStr | Метод динамического перераспределения потоков между портами устройства пакетной коммутации, позволяющий увеличить загрузку сетевого оборудования |
| title_full_unstemmed | Метод динамического перераспределения потоков между портами устройства пакетной коммутации, позволяющий увеличить загрузку сетевого оборудования |
| title_short | Метод динамического перераспределения потоков между портами устройства пакетной коммутации, позволяющий увеличить загрузку сетевого оборудования |
| title_sort | метод динамического перераспределения потоков между портами устройства пакетной коммутации, позволяющий увеличить загрузку сетевого оборудования |
| topic | Моделювання і управління великими системами |
| topic_facet | Моделювання і управління великими системами |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/2399 |
| work_keys_str_mv | AT konahovičgf metoddinamičeskogopereraspredeleniâpotokovmežduportamiustroistvapaketnoikommutaciipozvolâûŝiiuveličitʹzagruzkusetevogooborudovaniâ AT verbickiiiv metoddinamičeskogopereraspredeleniâpotokovmežduportamiustroistvapaketnoikommutaciipozvolâûŝiiuveličitʹzagruzkusetevogooborudovaniâ AT konahovičgf metoddinamíčnogopererozpodílupotokívmížportamipristroûpaketnoíkomutacííâkiidozvolâêzbílʹšitinavantažennâmereževogoobladnannâ AT verbickiiiv metoddinamíčnogopererozpodílupotokívmížportamipristroûpaketnoíkomutacííâkiidozvolâêzbílʹšitinavantažennâmereževogoobladnannâ AT konahovičgf theofferedmethodofdynamicdistributionofflowsbetweenportsofthedeviceofbatchswitchingwhichallowstoincreaseasafeloadofthenetworkequipment AT verbickiiiv theofferedmethodofdynamicdistributionofflowsbetweenportsofthedeviceofbatchswitchingwhichallowstoincreaseasafeloadofthenetworkequipment |