пїњ

ќѕ“»ћ»«ј÷»я — ќ–ќ—“≈… ѕ≈–≈ƒј„» Ѕ»“ќ¬ќ√ќ ѕќ“ќ ј ¬  јЌјЋј’ “–јЌ—ѕќ–“Ќќ… —≈“» —¬я«» —  ќћћ”“ј÷»≈… ѕј ≈“ќ¬, ќЅ≈—ѕ≈„»¬јёўјя ћј —»ћ”ћ ¬≈–ќя“Ќќ—“» —¬ќ≈¬–≈ћ≈ЌЌќ… ƒќ—“ј¬ » ѕ–ќ“ќ ќЋ№Ќџ’ ЅЋќ ќ¬ ƒјЌЌџ’

ќѕ“»ћ»«ј÷»я — ќ–ќ—“≈… ѕ≈–≈ƒј„» Ѕ»“ќ¬ќ√ќ ѕќ“ќ ј ¬  јЌјЋј’ “–јЌ—ѕќ–“Ќќ… —≈“» —¬я«» —  ќћћ”“ј÷»≈… ѕј ≈“ќ¬, ќЅ≈—ѕ≈„»¬јёўјя
ћј —»ћ”ћ ¬≈–ќя“Ќќ—“» —¬ќ≈¬–≈ћ≈ЌЌќ… ƒќ—“ј¬ » ѕ–ќ“ќ ќЋ№Ќџ’ ЅЋќ ќ¬ ƒјЌЌџ’
“регубов –оман Ѕорисович,
к.т.н., сотрудник јкадемии ‘—ќ –оссии,
–осси€, г. ќрел,
treba@list.ru
ћ€син Ќиколай »горевич,
к.т.н., сотрудник јкадемии ‘—ќ –оссии,
–осси€, г. ќрел,
staryi_nik@mail.ru
—овременный этап развити€ информационного общества характеризуетс€ развитием глобальной информационной инфраструктуры, совершенствованием методов и средств реализации информационных и телекоммуникационных процессов. ѕо мнению большинства экспертов, дл€ построени€ современных “—— целесо-образно использовать технологии, базирующиес€ на коммутации пакетов ( ѕ), в том числе оборудование, реализующее ретрансл€цию €чеек по протоколу ATM и многопротокольную коммутацию по временным меткам MPLS. Ѕазовым научно-методический аппаратом, примен€емым дл€ описани€ “—— с  ѕ €вл€етс€: обща€ теори€ систем, теори€ массового обслуживани€, теори€ графов, теори€ надежности, теори€ веро€тностей, а так же методы статистического моделировани€. ќднако имеющийс€ математический аппарат требует уточнени€ и развити€ в случае его применени€ дл€ исследовани€ современных “——.
¬ работе методом множителей Ћагранжа решена задача выбора оптимальных скоростей передачи битового потока в каналах транспортной сети св€зи с коммутацией пакетов. ÷ель оптимизации - обеспечить максимум веро€тности своевременной доставки протокольных блоков данных. ѕредложены решени€ сформулированной задачи дл€ различных условий функционировани€ сети: если каналы св€зи сети абсолютно надежны (коэффициент готовности каналов св€зи равен единице) и когда каналы св€зи сети имеют ограниченную надежность (коэффициент готовности меньше единицы).
ƒл€ цитировани€:
“регубов –.Ѕ., ћ€син Ќ.»., ћ€син  .». ќптимизаци€ скоростей передачи битового потока в каналах транспортной сети св€зи с коммутацией пакетов, обеспечивающа€ максимум веро€тности своевременной доставки протокольных блоков данных // T-Comm: “елекоммуникации и транспорт. - 2015. - є2. - —. 34-40.
For citation:
Tregubov R.B., Mjasin N.I., Mjasin K.I. The optimization of a bit transmission rates in channels of a packet switched transport communication network providing a maximum of probability of timely delivery of protocol data UNITS // T-Comm. 2015. No.2. –р. 34-40.
ћ€син  онстантин »горевич,
сотрудник јкадемии ‘—ќ –оссии, –осси€, г. ќрел, ffmc@mail.ru
 лючевые слова: протокольный блок данных, транспортна€ сеть св€зи с коммутацией пакетов, скорость передачи битового потока, канал св€зи, логическое соединение, логическа€ сеть, веро€тность своевременной доставки протокольных блоков данных, метод множителей Ћагранжа.
1. ¬ведение. —овременный этап развити€ информационного общества характеризуетс€ развитием глобальной информационной инфраструктуры, совершенствованием методов и средств реализации информационных и телекоммуникационных процессов [I]. ¬ передовых государствах и трансконтинентальных корпораци€х сформированы и функционируют мультисервисные инфокоммуника-ционные сети, €дром каждой из которой €вл€етс€ транспортна€ сеть св€зи (“——), реализующа€ услугу передани протокольных блоков данных (ѕЅƒ) посредством их переноса между устройствами ввода и вывода данных с требуемыми значени€ми показателей качества [2]. ƒанна€ услуга предполагает:
- поддержку переменной и посто€нной скорости передачи ѕЅƒ в точках ввода и вывода ѕЅƒ в “——, различие скоростей передачи вход€щего и исход€щего потоков ѕЅƒ, а также наличие или отсутствие синхронизации между взаимодействующими устройствами ввода и вывода данных [4];
- поддержку разнообразных конфигураций ("точка-точка", "точка-многоточка" и "многоточка") и топологий (шина, кольцо, дерево и др.) логических сетей, соедин€ющих взаимодействующие устройства ввода и вывода данных [3];
- реализацию функций объединени€, разделени€, сегментировани€ и сборки ѕЅƒ, а также мультиплексировани€, демультиплексировани€, расщеплени€ и рекомбинации логических соединений [5];
- обеспечение выполнени€ требований по надежности, своевременности, достоверности и конфиденциальности передачи ѕЅƒ [3].
ѕо мнению большинства экспертов, дл€ построени€ современных “—— целесообразно использовать технологии, базирующиес€ на коммутации пакетов ( ѕ), в том числе оборудование, реализующее ретрансл€цию €чеек по протоколу ATM и многопротокольную коммутацию по временным меткам MPLS [4, 6, 7].
Ѕазовым научно-методический аппаратом, примен€емым дл€ описани€ “—— с  ѕ €вл€етс€: обща€ теори€ систем, теори€ массового обслуживани€, теори€ графов, теори€ надежности, теори€ веро€тностей, а так же методы статистического моделировани€. ќднако имеющийс€ математический аппарат требует уточнени€ и развити€ в случае его применени€ дл€ исследовани€ современных “——.
2. ѕостановка задачи. «адачи синтеза “—— с  ѕ математической точки зрени€ €вл€ютс€ задачами оптимизации [8, 9]. ќсновные этапы синтеза включают:
- разработку математической модели “—— с  ѕ;
- определение внутренних параметров “—— с  ѕ, позвол€ющих получить оптимальные (наилучшие) значени€ еЄ внешних показателей.
Ќа втором шаге, как правило, рассматриваютс€ вопросы выбора: топологии, алгоритмов маршрутизации и управлени€ потоками ѕЅƒ, скоростей передачи битового потока в каналах “—— и производительности узлов коммутации.
«адачу выбора оптимальных скоростей передачи битового потока в каналах “—— с  ѕ, обеспечивающих макси-
мум веро€тности своевременной доставки ѕЅƒ, целесообразно формализовать следующим образом
ƒано: {,Д,Д} , г, (;,} , к) , » , Х џ .{41 и >доп
ћаксимизировать: –':30—≈ф ¬арьируютс€: {сД | ќграничение: ќ " где {,} - множество элементов; упт - интенсивность
потока ѕЅƒ, поступающего в информационное направление (»Ќ) источник которого п -й узел коммутации (” ), а адресат - т -й ” ; у - это сумма интенсивностей потоков ѕЅƒ дл€ “—— определ€етс€ по следующей формуле
N X
V - суммарное число узлов “—— (узлы нумеруютс€ произвольным образом);
(л/-Ћ ) - суммарное число каналов “—— (каналы нумеруютс€ по пор€дку, дл€ этого определ€етс€ канал, соедин€ющий очередной ”  с узлом сети с наименьшим номером и этому каналу св€зи присваиваетс€ номер, следующий после номера последней вершины и т. д.); ћ - суммарное число узлов и каналов “——; 4 - интенсивность потока ѕЅƒ, поступающих в канал “—— с номером л;
— - интенсивность длины ѕЅƒ, поступающих в канал “—— с номером ;
с, - интенсивность старени€ ѕЅƒ, поступающих в канал “—— с номером 5;
к, - коэффициент готовности канала “—— с номером л ; </, - стоимость единицы скорости передачи бит данных в канале “—— с номером 5 ;
а1, - интенсивность восстановлени€ канала “—— с номером л ;
ќ""" - допустима€ сумма затрат на реализацию “——; !''' 1,"'"г - веро€тность своевременной доставки ѕЅƒ в
“——, выражение [8]
л \
рсвоевр _ ^ ' ^ ' ^ ^-свосвр .
ї1=1 '
–^г ~ веро€тность своевременной доставки ѕЅƒ в »Ќ, выражение [8]
^воевр _ | | ^свогвр , >
—,е¬ Дю
–√Щр ~ веро€тность своевременной доставки ѕЅƒ в канале “—— с номером л , выражение [91
—, - скорость передачи бит данных в канале “—— с номером V.
3. –ешение задачи выбора оптимальных скоростей передачи битов данных в каналах “—— с  ѕ, обеспечивающее максимум веро€тности своевременной доставки ѕЅƒ дл€ абсолютно надежных каналов св€зи (коэффициент готовности каналов св€зи равен единице).
ќдной из наиболее трудных научно-методических проблем проектировани€ €вл€етс€ оптимальный выбор скоростей передачи битового потока отдельных каналов “—— из конечного набора их возможных значений,   насто€щему времени имеетс€ много полуэвристических и эвристических подходов к решению таких задач [10], однако их применение на практике демонстрирует наличие существенных погрешностей (до 20%) полученных результатов. “аким образом, ощущаетс€ недостаток точных аналитических решений задачи выбора пропускных способностей каналов “—— с  ѕ, ѕри решении сформулированной задачи далее предлагаетс€ не учитывать то ограничение, что скорость передачи битового потока может принимать значени€ лишь из дискретного множества.  ак показали исследовани€, более точные решени€ можно получить в предположении, что эта скорость может принимать любые неотрицательные значени€.
”тверждение є I. –аспределение множества скоростей передачи битов данных {с,} в абсолютно надежных каналах “—— с  ѕ, которое максимизирует веро€тность своевременной доставки ѕЅƒ ,:'е"? ], при наличии огра-
ничени€
м

(I)
определ€етс€ выражением
—, =(A.,.-v., )-(Ђ,)-'-
^-¬л-^.^гч)
ч,
тћ^гч XXi ^nzr
11 п т
V »ЌЌЋ1е—,
и1-/- Ei г,......и-сгр
рсвоевр
у ѕ с )
ѕ=1 т=1 .V 4 Ћ л л 4'
(2)
—формулированна€ задача состоит в поиске экстремума (максимума) непрерывной нелинейной функции (2) при наличии ограничени€ в виде равенства (II). ‘ункци€ яагранжа может быть записана в следующем виде
- XI »
SXc.H?-
к - —, - л,) —,с инДД
где р - некоторый неопределенный посто€нный множитель (множитель Ћагранжа).
ќчевидно, что если найти экстремум функции —({— [, –) при вариации скоростей передачи битов данных {с, [ в каналах “—— с  ѕ, то тем самым образом будет получено решение исходной оптимизационной задачи. »спользу€ метод множителей Ћагранжа [I I] можно получить следующую систему уравнений
у у[
” с,-
ЩДе—,
ее.
Jim —√–
lim —"''
—,Ч
1 »ЌД
(3)
где lim - веро€тность того, что ѕЅƒ будет свое-
C,-wc
временно доставлен из ”  » в ”  т , без учета веро€тности своевременности доставки этого блока в канапе “—— с номером $ через который данный маршрут проходит
lim –√"р = 1 ; инД.Д,ес5
с >v
означает, что необходимо
учесть все информационные направлени€, которые проход€т через канал св€зи л .
”множа€ (3) на о, и суммиру€ по всем ,т получаетс€,
что
е.....= ((ј
J=N I 1
ƒоказательство. ¬еро€тность своевременной доставки ѕЅƒ в “—— с  ѕ и абсолютно надежными каналами определ€етс€ выражением [9]
ƒ' ” - ( I 1 1
^ №
откуда
a/tW „/ ZZ 7"->
lim –Щ"Щр
ч 111,1 ' ц,т
с,-її

i
I
J=N 11

lim /'fB,?Щp
(4)
ѕодставл€€ (4) в (3), можно записать

м ;
о- к

ѕт
'Ч>00
X
\ -1
XXI г"-'"с
11т
(5)
что и требовалось доказать.
ќпредел€€ добавочную стоимость ќе как
и
;=л -I
подставл€€ (6) в (5) це >й окончательной форм
(6)
и подставл€€ (6) в (5) целесообразно перейти к следующей окончательной формуле

рсвоевр
(7)
X
] Ћ+1
^^№“ч ’’( г*.ї
II ѕ 171

— <7, -' I
11 I

л! __
(8)
/ЧлЧI
Ўаг 5. ќпределение значени€ веро€тности своевременной доставки ѕЅƒ по формуле (2). ƒл€ расчета используютс€ значени€ скоростей передачи бит данных каналов “—— с  ѕ, полученные на шаге 4.
Ўаг 6. ≈сли значение веро€тности своевременной доставки ѕЅƒ на шаге 5 не отличаетс€ от начального значени€ веро€тности своевременной доставки ѕЅƒ, тогда работа алгоритма заканчиваетс€. ¬ противном случае начальные значени€ скоростей передачи бит данных каналов “—— принимаютс€ равными тем, что были получены на шаге 4, а начальное значение веро€тности своевременной доставки ѕЅƒ принимаетс€ равным тому, что было получено шаге 5 и осуществл€етс€ переход на шаг 4.
4. –ешение задачи выбора оптимальных скоростей передачи битового потока в каналах “—— с  ѕ, обеспечивающее максимум веро€тности своевременной доставки ѕЅƒ дл€ случа€ ненадежных каналов св€зи (коэффициент готовности каналов св€зи меньше единицы).
”тверждение є 2. –аспределение множества скоростей передачи бит данных {с,) в ненадежных каналах “—— с  ѕ, которое максимизирует веро€тность своевременной доставки ѕЅƒ (у>,,|1":'"г), при наличии ограничени€ в виде равенства (I) определ€етс€ выражением
V- + <7,
Ќиже представлен алгоритм выбора оптимальных скоростей передачи битового потока в каналах “—— с  ѕ, обеспечивающих максимум веро€тности своевременной доставки ѕЅƒ дл€ случа€, когда коэффициент готовности каналов равен единице.
Ўаг I. ѕроверка услови€ реализуемости решени€ по формуле

(V
'7 + ^ў

»Ќ^-„",
I
Ўаг 2. Ќачальные значени€ скоростей передачи битов данных всех каналов “—— рассчитываютс€ по формуле [8]
Х/к'√„
1 к)
у,
XI
IЩ —√"
„^" I
»Ќ,Дс—(
ƒоказательство. ¬еро€тность своевременной доставки ѕЅƒ в “—— с  ѕ и ненадежными каналами определ€етс€ выражением [9]
XX п
Ўаг 3. ќпределение начального значени€ веро€тности своевременной доставки ѕЅƒ по формуле (2). ƒл€ расчета используютс€ начальные значени€ скоростей передачи бит данных каналов “——, полученные на шаге 2.
Ўаг 4. –аспределение скоростей передачи бит данных каналов “—— с  ѕ по формуле (7). ƒл€ расчета используем начальные значени€ скоростей передачи данных соответствующих каналов св€зи.
—,- - лЋ)
I. I, V
(?)
Ёто задача поиска экстремума (максимума) непрерывной нелинейной функции (9) при наличии ограничени€ в виде равенства (I). ‘ункци€ ѕагранжа может быть записана в следующем виде

с,И ицД
-а!_
< .1
…—,

VII
к, )
”ц,» г с,-
»““ ,,Д,е—
с, - лД-

V, 1 <1,1 к',
9, V5 1 г/, 4 1 ^ ]
I п т
инД.с
”множа€ (10) на <?, и суммиру€ по всем л получаетс€


vV + rf;

<1
)=Ќ +1
откуда
V, '“у /-



—,-не »ѕ, Д6—,

и-

1 - --' , *>” Х
I
;-л+1

ш ие—,
где /3 - некоторый неопределенный посто€нный множитель (множитель Ћагранжа).
ќчевидно, что если найти экстремум функции ('(— [' /' ) при вариации скоростей передачи битов данных {—, { в каналах “—— с  ѕ, то тем самым образом будет получено решение исходной оптимизационной задачи. »спользу€ метод множителей Ћагранжа [II] может быть получена следующа€ система уравнений
(II)
ѕодставл€€ (I I) в (10), можно записать
1 "л/1 ^
с, =(€,-у1)-(<т,)
еЃ"-
V, - с1Д ч , 1-1
„,

1лп г*а<х 1,1,1 '

I
]=к 1
| ' 1 { 4^ 4-4,
/ ”
нн,,,^-:
(12)
.(10)
что и требовалось доказать.
ќпредел€€ добавочную стоимость √г как

(13)
и подставл€€ (13) в (12) целесообразно перейти к окончательной формуле
, -н I\-dJkl ƒ..
-Ч-гЧ+ Чх


—ѕ


(14)
Ќиже представлен алгоритм выбора оптимальных скоростей передачи битового потока в каналах “—— с  ѕ, обеспечивающий максимум веро€тности своевременной доставки ѕЅƒ дл€ случа€, когда коэффициент готовности каналов св€зи меньше единицы.
Ўаг I, ѕроверка услови€ реализуемости решени€ по формуле
Ўаг 2. Ќачальные значени€ скоростей передачи битов данных всех каналов “—— рассчитываютс€ по формуле [9]
» I и,
с, - л- - к)1 (*; √--^-х
€,
Ўаг 3. ќпределение начального значени€ веро€тности своевременной доставки ѕЅƒ по формуле (9). ƒл€ расчета используютс€ начальные значени€ скоростей передачи бит данных каналов “—— с  ѕ, полученные на шаге 2.
Ўаг 4. –аспределение скоростей передачи бит данных каналов “—— с  ѕ по формуле (14). ƒл€ расчета используютс€ начальные значени€ скоростей передачи данных соответствующих каналов св€зи.
Ўаг 5. ќпределение значени€ веро€тности своевременной доставки ѕЅƒ по формуле (9). ƒл€ расчета используютс€ значени€ скоростей передачи бит данных каналов “—— с  ѕ, полученные на шаге 4.
Ўаг 6, ≈сли значение веро€тности своевременной доставки ѕЅƒ на шаге 5 не отличаетс€ от начального значени€ веро€тности своевременной доставки ѕЅƒ, тогда работа алгоритма заканчиваетс€. ¬ противном случае начальные значени€ скоростей передачи бит данных каналов “—— принимаютс€ равными тем, что были получены на шаге 4, а начальное значение веро€тности своевременной доставки ѕЅƒ принимаетс€ равным тому, что было получено шаге 5 и осуществл€етс€ переход на шаг 4.
«аключение
“аким образом, представленные результаты решени€ оптимизационных задач (7) и (14) нар€ду с известными решени€ми (8) и (15), позвол€ют найти в аналитическом виде такое распределение скоростей передачи битового потока каналов “—— с  ѕ, которое максимизирует веро€тность своевременной доставки ѕЅƒ. ќднако следует помнить, что полученные решени€, хот€ и €вл€ютс€ оптимальными, зачастую оказываютс€ нереализуемыми.
Ёто обусловлено тем, что в процессе решени€ не учитывалс€ целочисленных характер скоростей передачи бит данных в каналах “—— с  ѕ. —ледовательно, после применение предложенных в работе алгоритмов требуетс€ редукци€ полученных оптимальных решений до скоростей, реализуемых на практике. “ем не менее, как показали исследовани€ на тестовых графах и эксперименты на реальных “—— с  ѕ, такие квазиоптимальные решени€ оказываютс€ более точными, чем результаты применени€ существующих эвристических подходов.
Ћитература
1. –ƒ I 15.005-2002. »нформационные технологии. ћониторинг информатизации –оссии, ќсновные положени€ мониторинга.
2. –ƒ 45.128-2000. —ети и службы передачи данных.
3. √ќ—“ 53729-2009.  ачество услуги "ѕредоставление виртуальной частной сети (VPN)". ѕоказатели качества.
4. Ќазаров ј. Ќ., —имонов MB. ATM: технологи€ высокоскоростных сетей. - M : Ёко-“рендз, 1997. - 232 с.
5. √ќ—“ 24402-88. “елеобработка данных и вычислительные сети. “ермины и определени€.
6. √ольдштейн ј.Ѕ., √ольдштейн Ѕ.—. “ехнологи€ и протоколы MPLS, - —ѕб.: Ѕ’¬-ѕетербург, 2005. - 304 с.
7. jMctK-Keepu —., ћак-√рю  ., ‘ой —. ѕередача голосовых данных по сет€м Cisco Frame Relay, ATM и IP. - M.: »здательский дом "¬иль€ме", 2002. - 5 12 с.
8.  лейнрок Ћ. ¬ычислительные системы с очеред€ми / ѕер. с англ, под ред, Ѕ.—, ÷ыбакова. - ћ.: ћир, 1979, - 600 с.
9. «ахаров √.Ћ. ћетоды исследовани€ сетей передачи данных.
- ћ.: –адио и св€зь, 1982. - 208 с,
10. Ћохмотко 8.¬, ћодели и методы оптимизации структуры телекоммуникационных сетей: дис, д-ра техн, наук, - —ѕб,: —ѕб√”“, 1998.- 290 с,
I I. Taxa ј. ¬ведение в исследование операций / ѕер. с англ.
- ћ.: »здательский дом "¬иль€ме", 2001. - 912 с.
T-Comm #2-2015
COMMUNICATION
THE OPTIMIZATION OF A BIT TRANSMISSION RATES IN CHANNELS OF A PACKET SWITCHED TRANSPORT COMMUNICATION NETWORK PROVIDING A MAXIMUM OF PROBABILITY OF TIMELY DELIVERY OF PROTOCOL DATA UNITS
Tregubov Roman Borisovich,
Ph.D., employee of the Academy of Federal Agency of protection of Russian Federation, Orel, Russia,
treba@list.ru
Mjasin Nikolaj Igorevich,
Ph.D., employee of the Academy of Federal Agency of protection of Russian Federation, Orel, Russia,
staryi_nik@mail.ru
Mjasin Konstantin Igorevich,
employee of the Academy of Federal Agency of pro-tection of Russian Federation, Orel, Russia,
ffmc@mail.ru
Abstract
In article the task of a choice of optimum bit transmission rates in channels of a packet switched transport communication network is solved by method of Lagrange multipliers. The optimization purpose - to provide a maximum of probability of timely delivery of protocol data units. Solutions of the formulated task for different operating condi-tions of a network are proposed: if communication channels of a network are absolutely reliable (the channel availability is equal to unit) and when communication channels of a network has limited reliability (the channel availability is less than unit).
Keywords: a protocol data units, a packet switched transport communication net-work, bit transmission rate, communication channel, logical connection, a logical network, probability of timely delivery of protocol data units, a method of Lagrange multipliers.
References
1. Management Directive 115.005-2002. IT. Informatization Monitoring in Russia. Main Monitoring Conditions. [in Russian]
2. Management Directive 45.128-2000. Data transmission network and service. [in Russian]
3. GOST 53729-2009. Quality of service "Allocation of the Virtual Private Network (VPN)". Quality indices. [in Russian]
4. Nazarov A.N., Simonov M.V. ATM: Technology of High-speed Networks. Moscow, 1997. 232 p. [in Russian]
5. GOST 24402-88. Teleprocessing and computer network. Terms and definitions. [in Russian]
6. Gol'dshtejn A.B., Gol'dshtejn B.S. Technology and protocols MPLS. Saint-Petersburg, 2005. 304 p. [in Russian]
7. McQuerry S., McGrew K., Foy S. Cisco Voice over Frame Relay, ATM and IP, Cisco Press, 2002. 512 p. [in Russian]
8. Kleinrock L. Queueing Systems: Volume II - Computer Applications. New York, 1976. 576 p. [in Russian]
9. Zaharov G.P. Data transmission network investigation techniques. Moscow, 1982. 208 p. [in Russian]
10. Lohmotko V.V. Models and methods of telecommunication networks structure optimization. Saint-Petersburg, 1998. 290 p. [in Russian]
11. Taha A. Operations Research: An Introduction. Prentice Hall, 1997. 916 p. [in Russian]

пїњ