close

Вход

Забыли?

вход по аккаунту

?

Решение задачи о размещении узлов сети.

код для вставкиСкачать
Институт Государственного управления,
права и инновационных технологий (ИГУПИТ)
Главный редактор - д.э.н., профессор К.А. Кирсанов
тел. для справок: +7 (925) 853-04-57 (с 1100 – до 1800)
Опубликовать статью в журнале - http://publ.naukovedenie.ru
Интернет-журнал «НАУКОВЕДЕНИЕ» №3 2013
Аль-Таяр Башир Али Касем
Al-Tayar Basheer Ali Qasem
Тверской Государственный Технический Университет
Tver State Technical University
Аспирант кафедры Информационных систем ТвГТУ
The post-graduate student of the department of Information Systems of Tver State Technical
University / Аспирант
E-Mail: basheeraltayar@yahoo.com
Матвеев Юрий Николаевич
Matveev Yuri Nikolayevich
Тверской Государственный Технический Университет
Tver State Technical University
Профессор кафедры Информационных систем ТвГТУ
Professor of the department of Information Systems of Tver State Technical University
Доктор технических наук / Профессор
E-Mail: fmas@tstu.tver.ru
05.13.01 Системный анализ, управление и обработка информации (по отраслям)
Решение задачи о размещении узлов сети
Solving of network nodes placement problem
Аннотация: В статье рассматривается решение задачи о размещении узлов сети
доставки контента с использованием метода максимального элемента. Представлен пример
использования данного метода на примере размещения узлов сети в некоторых странах
Ближнего Востока и Северной Африки.
The Abstract: The paper considers a solution to the problem of content delivery network
nodes placement by using the maximum element method. An example of placing some network
nodes in a set of countries by using this method is illustrated.
Ключевые слова: Сети доставки контента, размещение, сетевые узлы, метод
максимального элемента.
Keywords: Content delivery network, network nodes, nodes placement.
***
В развитии информационных технологий в настоящее время проявляется стремление
эффективно использовать распределенные вычислительные ресурсы и системы хранения
информации для решения как научных, так и производственных задач. Важным направлением
исследований в области передачи и доставки информации является анализ и решение задач
оптимального размещения серверов и других сетевых объектов и устройств. Такие задачи
необходимо решать как при проектировании сети, так и в процессе модернизации сети.
Очевидно, что первым шагом при построении новой или модернизации существующей сети
доставки контента является оптимальное размещение устройств. Начиная с начальных
моментов системного проектирования, должны быть выбраны оптимальные места
размещения узлов и серверов сети в соответствии с определенными показателями.
1
http://naukovedenie.ru
109ТВН313
Институт Государственного управления,
права и инновационных технологий (ИГУПИТ)
Интернет-журнал «НАУКОВЕДЕНИЕ» №3 2013
Главный редактор - д.э.н., профессор К.А. Кирсанов
тел. для справок: +7 (925) 853-04-57 (с 1100 – до 1800)
Опубликовать статью в журнале - http://publ.naukovedenie.ru
Целью настоящей работы является решение задачи оптимизации размещения сетевых
узлов методом максимального элемента, использующим критерии эффективности внедрения
(эффекта от размещения) сетей и важности зон (пунктов) размещения для выбора
оптимальных из них.
Максимальный уровень обеспеченности или удовлетворенности – это уровень,
который может быть, достигнут, если вычислительные и сетевые мощности эффективно
используются и обслуживание запросов пользователей из региона продолжается до полного
их удовлетворения. Правильно рассчитанные вычислительные и сетевые мощности не могут
использоваться на 100 %, так как в условиях неопределенности вероятностного характера
развития сетевой инфраструктуры обязательно должен быть резерв вычислительных
мощностей и других ресурсов. Кроме того, в силу различности активности пользователей из
разных регионов в потреблении различного вида контента и услуг, объективно необходимо
прогнозирование потребности пользователей каждого региона в конкретных услугах, в том
числе в доставке представляемого контента провайдерами из удаленных регионов.
Следовательно, постоянное и стопроцентное удовлетворение потребности пользователей из
региона вычислительными и сетевыми мощностями сети, как правило, актуально, так как все
зависит от востребованных ими услуг и от самих сетей и поэтому постоянно требуется анализ
существующих и требуемых ресурсов.
Используемый в данной работе подход к решению задачи размещения состоит в
использовании метода максимального элемента для получения варианта оптимального
вектора размещения.
Постановка задачи
Пусть имеется N узлов, т.е. оборудование для построения узла сети доставки контента.
Примем, что все узлы однотипны (равноэффективны) в том смысле, что эффект от их
размещения зависит только от зоны, в которой они будут размещены.
Определены S зон, в которых можно будет размещать узлы сети. Зоны соответствуют
странам, городам или другому разделению региона, из которого поступают пользовательские
запросы на обслуживание. Каждая i-я зона (i = 1,…, S) имеет выражаемую через Аi
относительную важность (вес, отражающий некую характеристику зоны, например развитость
инфраструктуры или количество пользователей Интернета в этой зоне и тем самым
примерный уровень запросов поступающих от зоны). Обозначим через ωi коэффициент
удовлетворения запросов пользователей i зоны размещаемым в ней узлом сети. Другими
словами ωi является характеристикой эффективности узла в зоне или ожидаемым эффектом
от функционирования узла в i-ой зоне. Он отражает способность узла обслуживать запросы от
зоны (т.е. размещение узла в i-ой зоне удовлетворяет запросы (потребность) пользователей
этой зоны с вероятностью ωi ).
Для анализа можно использовать следующие показатели эффективности сети доставки
контента, в частности [1], и сети передачи данных вообще [3, 6]:
•
стоимостные характеристики, включающие капитальные затраты на
оборудование узлов коммутации и линий связи, а также подключение или
прокладку линий связи, и эксплуатационные расходы - стоимость аренды
каналов связи. В качестве интегральной характеристики может быть взята
приведенная стоимость;
•
ожидаемые временные характеристики передачи данных по сети;
2
http://naukovedenie.ru
109ТВН313
Институт Государственного управления,
права и инновационных технологий (ИГУПИТ)
Главный редактор - д.э.н., профессор К.А. Кирсанов
тел. для справок: +7 (925) 853-04-57 (с 1100 – до 1800)
Опубликовать статью в журнале - http://publ.naukovedenie.ru
Интернет-журнал «НАУКОВЕДЕНИЕ» №3 2013
•
среднее и максимальное время задержки сообщений и пакетов в сети передачи
данных, определяющее время реакции (обслуживания запросов пользователей).
Комплексное свойство — эффективность размещаемого узла, показывающее степень
его приспособленности к достижению цели порождается функциональными свойствами узла
— результативностью, ресурсоемкостью и оперативностью. Это свойство, проявляется при
функционировании системы и зависит как от свойств самой системы, так и от внешней среды.
Так как узлы однотипны, то эффективность узла в конкретной зоне в основном будет
зависеть от типа контента. Например, если пользователи зоны предпочитают
мультимедийный контент, то эффект от его размещения будет больше чем эффект от его
размещения в той зоне, пользователи которой неактивно пользуются Интернетом или не
интересуются насыщенным Интернет-контентом (видео, аудио, изображения).
ωi = 1 − εi , где εi – коэффициент неэффективности узла в i-ой зоне (вероятность
неудовлетворения запросов пользователей).
Необходимо определить оптимальное размещение узлов, т. е. назначить для
обслуживания пользователей зон такое количество xi узлов, при размещении которых
суммарный эффект будет наибольшим.
Поставленная задача может быть исследована с помощью разных математических
методов. Например, с помощью теории дискретных задач размещения можно моделировать
ситуацию, в которой требуется в конечной области разместить конечное число объектов (в
нашем случае это узлы сети и составляющие их серверы и другое сетевое оборудование) так,
чтобы достичь наибольшего эффекта или получить наименьшие издержки.
Задачу оптимального размещения математически можно сформулировать следующим
образом. Требуется найти оптимальный вектор размещения X = {xi }s , характеризующий
собой вариант распределения узлов между s зонами и максимизирующий целевую функцию,
отражающую суммарный эффект от размещения:
s
s
F ( x) = ∑ Fi ( xi ) = ∑ Ai (1 − εi i ) ,
i =1
x
(1)
i =1
при следующих ограничениях:
s
∑ xi ≤ N
(2)
i =1
xi ∈ {0,1,..., N },


0 ≤ (εi = 1 − ωi ) ≤ 1 , i = 1,.., S ,

Ai > 0

(3)
где N – количество узлов (серверов) подлежащих размещению.
Ограничение (2) ограничивает сумму числа размещенных единиц узлов заданным
значением N; xi ∈ {0,1,..., N } в ограничении (3) – допускает только планы размещения с
неотрицательными значениями xi .
3
http://naukovedenie.ru
109ТВН313
Институт Государственного управления,
права и инновационных технологий (ИГУПИТ)
Главный редактор - д.э.н., профессор К.А. Кирсанов
тел. для справок: +7 (925) 853-04-57 (с 1100 – до 1800)
Опубликовать статью в журнале - http://publ.naukovedenie.ru
Интернет-журнал «НАУКОВЕДЕНИЕ» №3 2013
Метод максимального элемента и алгоритм решения задачи
Задачи размещения объектов различного вида составляют широкий класс задач
дискретной оптимизации. Возможны различные постановки задач оптимального размещения
в зависимости от того, какие ограничения являются существенными, и какие показатели
оптимальности выбраны [5].
Для решения нашей задачи воспользуемся описанным в [2, 4] методом максимального
элемента. Метод максимального элемента относится к градиентным методам. На
произвольном шаге процесса решения рассматривается только один из имеющихся узлов. На
формальном языке это означает, что на t-м (t =1,…, d) шаге процесса дается единичное
приращение ( ∆xr =1) только одной, i=rt -й компоненте искомого оптимального вектора
t
размещения однотипных узлов между зонами. После конечного числа (d) шагов, равного
числу узлов N, все узлы оказываются размещенными, а задача решенной.
Очевидно, что максимизация общего эффекта F(X) получаемого от размещения всех
узлов распределенной сети эквивалентна максимизации величины среднего эффекта
получаемого от размещения каждого N узла, за счет которых получается этот общий эффект.
Средний эффект, получаемый от размещения единицы однотипного узла будет максимален, если на каждом шаге процесса закреплять один узел (сервер) для обслуживания
пользовательских запросов поступающих из зоны i = rt, , где прирост эффекта на данном шаге
процесса ( ∆ +r ) наибольший.
t
Можно предположить, что такой процесс распределения, не учитывающий перспективу, а исходящий только из интересов каждого шага, будет тем не менее оптимален, так
как, во-первых, каждая из функций Fi ( xi ) выпукла верх и составляет убывающую
+
последовательность приращений эффекта ∆ tk
от действия каждого очередного узла:
x −1
x
Fi ( xi ) = A(1 − εi i ) = Ai ωi + Ai εi ωi + ... + Ai εi i ωi =
∆1+i + ∆ 2+i + ... + ∆ +x i =
i
xi
∑ ∆+ki , .........∆+ki = Ai εik −1ωi ,
k =1
и, следовательно, допускает распределение узлов равными и минимальными порциями
(единицами), а, во-вторых, в силу однотипности (равноэффективности) узлов не потребуется
взаимозаменяемости каких-либо двух единиц узлов.
Чтобы разработать алгоритм решения задачи, необходимо только определить
выражение для вычисления величины приращения ∆ +r целевой функции, получаемого ею на
произвольном (t-м) шаге процесса оптимизации. К моменту размещения t-й единицы узлов на
t-м шаге процесса уже было распределено (t - 1) единиц, так что i-я зона удовлетворена с
некоторой вероятностью ρti −1 (i = 1,.., S), следовательно, текущее значение целевой функции
можно записать в виде:
s
F + = ∑ Ai ρ(rt −1)
t −1
(4)
i =1
После размещения t-й единицы узлов для обслуживания r-й зоны (r = 1,..,S) текущее
значение целевой функции увеличится только за счет увеличения эффекта r-ой зоне и станет
равным:
4
http://naukovedenie.ru
109ТВН313
Институт Государственного управления,
права и инновационных технологий (ИГУПИТ)
Интернет-журнал «НАУКОВЕДЕНИЕ» №3 2013
Главный редактор - д.э.н., профессор К.А. Кирсанов
тел. для справок: +7 (925) 853-04-57 (с 1100 – до 1800)
Опубликовать статью в журнале - http://publ.naukovedenie.ru
Ft+ = ∑ Ai ρ(rt −1) + Ar (1 − Qr(t −1) ε r )
(5)
i≠r
где Qr(t −1) = 1 − ρ(rt −1) - вероятность неудовлетворения r-й зоны до «размещения» t-го
узла; εr = 1 − ωr - условная вероятность ее неудовлетворения t-м узлом.
Прибавляя и вычитая из правой части формулы (5) член Ar ρ(rt −1) и учитывая запись
(4), получаем Ft+ = F + + Ar (1 − Qr(t −1) ε r ) − Ar ρ(rt −1)
t −1
Искомое приращение после элементарных преобразований запишется в виде:
∆ +r = Ft+ − F + = Ar Qr(t −1) ωr = Ar(t −1) ωr
t −1
Если Ar - исходная важность (вес) зоны, то
распределения ( t - 1 ) единиц узлов.
Ar(t −1) = Ar Q(t −1) - её вес после
Знак плюс у функции Ft означает только то, что эта функция не убывает по мере
увеличения t (приращение ∆+r неотрицательно).
Таким образом, алгоритм решения задачи (1) - (3) состоит из следующих шагов:
1.
Вычисление компонент вектора {∆ +r }s по формуле:
∆ r+ = Ar ωr , _______ r = 1,..., S .
t
2.
Размещение одного узла в i= rt –ой зоне согласно условию ∆ +r = max ∆ r+
t
1≤ r ≤ s
Если существует несколько таких элементов, то из них берется любой.
3.
Вычисление
текущих
значений
компонент
 x(t −1) , _____ если _____ r ≠ r ( x (0) = 0), __ r = 1,..., S ,
r
t r
xr = 
(t −1)
+ 1, ___ если _____ r = rt .
 xr
4.
Вычисление текущего значения целевой функции:
вектора
Ft+ = F + + ∆ +r , __ F0+ = 0, __ t := t + 1.
t −1
t
5.
X (t ) :
(6)
Проверка условия: t ≤ N , если Да - переход к пункту 6,
а если Нет – переход к пункту 7,
6.
Пересчитать
компоненты
текущего
{∆ +r }(st ) :
вектора
∆ + , ____ если __ r ≠ r
t
∆ +r =  r
+
∆ r εr , ___ если __ r = rt
Переход к пункту 2.
7.
Конец вычислений и печать результатов ( F ( X ) = FN+ ,{xi } = {xi( N ) }) .
5
http://naukovedenie.ru
109ТВН313
Институт Государственного управления,
права и инновационных технологий (ИГУПИТ)
Главный редактор - д.э.н., профессор К.А. Кирсанов
тел. для справок: +7 (925) 853-04-57 (с 1100 – до 1800)
Опубликовать статью в журнале - http://publ.naukovedenie.ru
Интернет-журнал «НАУКОВЕДЕНИЕ» №3 2013
Метод, реализуемый данным алгоритмом, называют методом максимального элемента,
потому что на каждом шаге процесса размещение соответствует максимальному элементу
текущего вектора {∆ +r }(St ) .
В качестве примера рассмотрим решение следующей задачи.
Пусть требуется размещать N = 7 имеющихся однотипных узлов сети доставки
контента в зонах, таким образом, чтобы суммарный эффект от размещения был
максимальным. Задано множество S=7 возможных зон размещения, каждая зона будет
представлять собой одну страну из региона Ближнего Востока и Северной Африки. S=
{Саудовская Аравия, Сирия, Ливия, Египет, Йемен, Марокко, ОАЭ}. Априорно определены
Ai _(∑ Ai = 100%) важности (весы) всех S зон в зависимости от числа пользователей
Вектором {ωi } заданы ожидаемые эффекты от размещения
Интернета в каждой стране.
единицы однотипного узла сети доставки контента в i зоне. Значения {ωi } приведены в
таблице. Вычислительная схема представлена той же таблицей. В ней записана
последовательность текущих векторов {∆ r+ }t = Ar( t − 1) ω r .
{
}
S
Из строки t=1, где записаны компоненты вектора { Ar ωr } , для первого шага процесса
оптимизации, следует, что согласно 2-ому пункту алгоритма один (первый) узел размещается
в зоне i = r1=6, следующий - в зоне r2=4 и т. д в соответствии с максимальными элементами
вектора
{∆ +r } .
t
Согласно 6-ему пункту
{
алгоритма производится пересчет только той
}
компоненты вектора {∆ +r } = Ar( t −1) ω r , которая соответствует зоне, где был размещен узел
t
(ri = 6).
1
2
3
i
4
5
6
7
6.0
23.0
9.0
0.86
5.16
5.16
5.16
5.16
5.16
5.16
0.72
1
0.75
17.25
4.31
4.31
4.31
4.31
4.31
4.31
2
0.6
5.4
5.4
5.4
5.4
5.4
2.16
2.16
1
Ai
t
14.0
13.0
6.0
29.0
ωi
1
2
3
4
5
6
7
xi
0.44
6.16
6.16
6.16
3.45
3.45
3.45
3.45
1
0.3
3.9
3.9
3.9
3.9
3.9
3.9
3.9
0
0.5
3
3
3
3
3
3
3
0
0.3
8.7
8.70
6.09
6.09
4.26
4.26
4.26
2
Ft+
17.25
25.95
32.11
38.2
43.6
48.76
53.07
53.07
Результат расчета можно записать в виде цепочки размещений, т.е. последовательности
номеров зон выбранных для размещения в них узлов. Из таблицы ясно, что оптимальным
решением будет последовательностью размещения узлов в зонах в следующем порядке :
(rt ) N =(6→ 4→ 1→ 4→ 7→ 5→ 6) = (Марокко→ Египет→ Саудовская Аравия→ Египет→
ОАЭ→ Йемен→ Марокко).
6
http://naukovedenie.ru
109ТВН313
Институт Государственного управления,
права и инновационных технологий (ИГУПИТ)
Интернет-журнал «НАУКОВЕДЕНИЕ» №3 2013
Главный редактор - д.э.н., профессор К.А. Кирсанов
тел. для справок: +7 (925) 853-04-57 (с 1100 – до 1800)
Опубликовать статью в журнале - http://publ.naukovedenie.ru
Текущие значения целевой функции, полученные согласно формуле (6), приведены в
крайнем правом столбце таблицы, например: F4 = F3 + ∆ +r 3 = 32.11 + 6.09 = 38.2 .
Использование предлагаемого алгоритма, основанного на методе максимального
элемента, для решения задачи размещения узлов сети доставки контента в странах Ближнего
Востока и Северной Африки позволяет в зависимости от числа пользователей сети Интернет в
этих стран и ожидаемого эффекта в каждой стране получить оптимальный вариант размещения
узлов сети.
ЛИТЕРАТУРА
1.
Аль-Таяр Б.А., Музанна М.М.. Критерии эффективности внедрения сетей
доставки контента. XL Неделя науки СПбГПУ: материалы международной
научно-практической конференции. Ч. VIII // СПб.: Изд-во Политехн. ун-та,
2011. –C. 146-147.
2.
Берзин Е.А. Оптимальное распределение ресурсов и элементы синтеза систем //
М.: Советское радио, 1974.-304 с.
3.
Гостев В.М. Об одном подходе к решению проблемы проектирования сетей
передачи данных территориальных компьютерных сетей // Новые
информационные технологии в университетском образовании: Материалы 8-й
международн. науч.-методич. конф. (Новосибирск, 6-8 июня 2001 г.). Новосибирск, 2001. - С.187.
4.
Громов Ю.Ю., Сергин М.Ю. Метод и алгоритм определения ситуации
функционирования в замкнутом производственном пространстве // Двойные
технологии. 2000. - № 4. - С. 36-40.
5.
Кондратьев В. Д. Методы решения задачи размещения объектов обслуживания
// Управление большими системами: сборник трудов, 2008.- С. 46–56.
6.
Пятибратов А.П., Гудыно Л.П., Кириченко А.А. Вычислительные системы, сети
и телекоммуникации: Учебник. 2-е изд., // - М.: Финансы и статистика, 2004. 512 с.
Рецензент: Калабин Александр Леонидович. Зав. кафедрой Программного
обеспечения вычислительной техники, д.ф-м.н., профессор, Тверской Государственный
Технический Университет.
7
http://naukovedenie.ru
109ТВН313
Документ
Категория
Без категории
Просмотров
8
Размер файла
159 Кб
Теги
решение, размещения, узлов, сети, задачи
1/--страниц
Пожаловаться на содержимое документа