Математическая модель управления ресурсами гибридной сети доставки контента с гарантированным качеством обслуживания

Размещено на http://www.allbest.ru//

170

ІSSN 0485-8972 Радиотехника. 2013. Вып. 175

Размещено на http://www.allbest.ru//

Математическая модель управления ресурсами гибридной сети доставки контента с гарантированным качеством обслуживания

О.Ю. Евсеева, д-р техн. наук

Введение

Понимание сети Internet как распределенного хранилища всевозможного контента, экспоненциальный рост числа пользователей, часто возникающие проблемы, связанные с перегрузкой Web-серверов и недоступностью услуги, обусловили необходимость организации эффективной системы хранения и доставки контента: книг, журналов, новостных лент, фотографий, фильмов с высоким разрешением, видеотрансляций и др. С этой целью были разработаны и реализованы на практике сети доставки контента (Content Delivery Network, CDN) и конкурирующие с ними многочисленные пиринговые (одноранговые) сети (Peer-to-Peer, P2P), развертываемые поверх существующей транспортной инфраструктуры Internet.

Принципы построения сетей доставки контента

В основу построения сетей CDN и P2P положены разные принципы, что обуславливает их зачастую диаметрально противоположные свойства. Основная идея построения сетей CDN заключается в дублировании (или зеркалировании) контента и/или сервисов основного сервера (origin server) несколькими периферийными серверами, называемыми репликами (replica) или суррогатными (surrogate), которые географически расположены на удалении от основного сервера и друг от друга, но вблизи от потребителя услуг [1, 2]. Тогда запросы, поступающие от Internet-пользователей из различных локальных сетей, направляются на обслуживание на ближайший незагруженный сервер (основной или периферийный), обеспечивая тем самым повышение пропускной способности, надежности и эффективности всей системы доставки контента в конечном итоге. В то же время функционирование CDN связано с решением ряда задач, таких как репликация контента и синхронизация серверов, авторизация и маршрутизация запросов пользователей на тот или иной сервер, что ведет к усложнению системы и, соответственно, повышает стоимость предоставляемых услуг. В рамках сетей P2P каждый хост, на котором установлено соответствующее программное обеспечение, может выступать как в качестве клиента, запрашивающего контент, так и в качестве сервера, хранящего и распространяющего его, что обеспечивает совместное использование канальных и вычислительных ресурсов всех подключенных в данный момент к сети пользователей. В итоге для сетей P2P характерны, с одной стороны, высокая масштабируемость и низкая себестоимость услуги, с другой стороны - низкая надежность, неконтролируемая пропускная способность системы, сложность контроля как самого контента, так и пользователей [3]. Тем не менее, основной недостаток P2P сетей связан с невозможностью гарантировать пользователю качество предоставляемой услуги, так как скорость загрузки контента и его доступность всецело зависят от числа активных в данный момент пиров, и не являются, строго говоря, управляемыми величинами.

С целью повышения качества обслуживания пользователей, построения масштабируемой и при этом контролируемой и управляемой системы хранения и доставки контента в литературе были предложены и на практике реализованы различные гибридные подходы, основанные на совместном использовании CDN и P2P. В рамках гибридной сети пользователь может загрузить контент с сервера CDN, с выполняющих роль серверов хостов P2P или использовать оба типа источника. В общем случае интеграция CDN и P2P может осуществляться в соответствии с двумя основными сценариями [2]:

Основная роль в гибридной сети отводится CDN, ресурсы которой используются в первую очередь и для которой P2P-сеть является вспомогательной.

Основная роль отводится P2P-сети, которая дополняется CDN-серверами, выполняющими функции резервных и задействуемыми только лишь в том случае, если запрашиваемый контент не может быть предоставлен P2P-сетью.

С точки зрения организации логических связей в рамках гибридной сети доставки контента, как показывает анализ, наиболее перспективной видится модель взаимодействия, показанная на рис. 1, в которой ресурсы одной CDN доступны для нескольких P2P-сетей [2].

Рис. 1. Принцип построения гибридной сети доставки контента

Переход к гибридным сетям доставки контента сопряжен с решением ряда задач, одной из которых является задача управления. Система управления гибридной сетью доставки контента должна сочетать в себе централизованный, основанный на информации о глобальном состоянии подход, используемый в CDN, и принципы локального, децентрализованного управления, реализуемого в P2P. В соответствии с повышением уровня требований пользователей к качеству их обслуживания, управление запросами, включая выбор сервера или совокупности серверов и непосредственно доставку контента, должно осуществляться исходя из типа услуги и запрашиваемого качества ее предоставления. Кроме того, на систему управления возлагается дополнительная задача балансировки нагрузки между CDN и P2P-сетями, а также сбалансированного использования ресурсов внутри каждой из них. Причем с целью повышения эффективности управление ресурсами разного типа должно быть в высокой степени согласованным, т.е. управление вычислительными ресурсами серверов CDN и P2P должно быть скоординировано с распределением канальных и буферных ресурсов телекоммуникационной сети, обеспечивающей транспортные функции по доставке контента.

В свете перечисленных требований известные методы управления сетями CDN, в основе которых, как показывает анализ, лежат простейшие, зачастую эвристические схемы принятия решения, не могут быть применены [1]. Гибридизация, гарантированное качество обслуживания, необходимость балансировки нагрузки - те факторы, которые требуют пересмотра известных решений в направлении реализации принципов адаптивного оптимального управления ресурсами сети доставки контента. Это, в свою очередь, предполагает подведение четкой математической базы под указанные задачи. Таким образом, актуальной является задача разработки математической модели управления ресурсами гибридной сети доставки контента с гарантированным качеством обслуживания.

Анализ математических моделей управления ресурсами CDN

Поскольку CDN и P2P представляют собой оверлейные (наложенные) сети, транспортные функции по доставке контента возлагаются на лежащую в их основе телекоммуникационную сеть (ТКС). Тогда при построении математической модели CDN следует исходить из того, в процессе доставки контента участвуют два компонента: транспортная телекоммуникационная сеть и периферийные серверы, выступающие в роли источников трафика. Каждый из компонентов вносит равнозначный вклад в результирующее качество обслуживания, а потому оба должны выступать в качестве объекта управления. Тем не менее, описанные в литературе математические модели CDN предполагают управление лишь серверной частью, в то время как задача управления ресурсами транспортной телекоммуникационной сети не принимается во внимание и решается независимо.

Традиционно к задачам управления в CDN относятся следующие [1, 2]:

- выбор числа и мест размещения периферийных серверов, что состоит в назначении тому или иному серверу (узлу) сети функций по хранению контента;

- распределение контента между периферийными серверами;

- маршрутизация запроса (request-routing), которая заключается в выборе ближайшего в определенной метрике незагруженного сервера (основного или периферийного), способного предоставить запрашиваемый контент.

Зачастую эти задачи не разделяются и решаются в рамках единой модели. Например, в [3] предлагается следующая их формализация в виде задачи целочисленного программирования со стоимостной целевой функцией

(1)

при ограничениях

, (2)

, (3)

, (4)

где - переменная использования -го узла в качестве периферийного сервера; - переменная обслуживания -м сервером запроса от -го пользователя; - переменная размещения контента -го типа на -м сервере; - множество пользователей системы; - множество узлов, на которые могут быть возложены функции периферийного сервера; - множество типов контента; - размер файла, содержащего -й контент; - скорость, с которой передается запрос -го пользователя на контент -го типа; и - «стоимость» соединения между узлами и и между основным сервером и -м периферийным сервером соответственно; - емкость запоминающего устройства -го сервера.

В работе [4] из модели (1) - (4) была исключена подзадача размещения периферийных серверов, но добавлено условие, связанное с качеством обслуживания, т.е. условие (3) заменено на следующее:

, (5)

где - задержка передачи контента между -м и -м узлами; - задержка передачи контента между основным и -м периферийным серверами; - допустимая величина задержки.

В рамках представленных моделей каждый запрос пользователя может быть направлен только к одному серверу, однако с целью повышения эффективности системы хранения и доставки контента в модели, представленной в [5], предусматривается возможность перенаправления запроса для загрузки контента от одного к другому периферийному серверу:

(6)

при ограничениях (2), а также

, (7)

, (8)

, (9)

, (10)

где , если запрашиваемый -м пользователем контент -го типа доступен на -м сервере, в противном случае.

Таким образом, как показывает анализ, представленные в литературе математические модели CDN основываются на формализации задачи управления в классе целочисленного программирования. При этом каждый запрос обрабатывается индивидуально и допускается загрузка контента только от одного сервера, что снижает масштабируемость системы. В то же время эффективность и масштабируемость системы в целом существенно возрастет, если допустить возможность загрузки контента от нескольких серверов, по аналогии с сетями P2P. С точки зрения практики в условиях гибридных сетей доставки контента такой подход может быть реализован, поскольку в этом случае запрос на сервер поступает не от каждого пользователя в отдельности, а от группы пользователей, объединенных в одну P2P-сеть (рис. 1). Кроме того, в тех немногих моделях, в рамках которых предпринимается попытка ввести показатели качества обслуживания, например через ограничения (5), задержки передачи контента между пользователем и сервером, его обслуживающем, предполагаются величинами постоянными. Однако на практике величина задержки доставки контента зависит от скорости его передачи, выбранного маршрута в нижележащей транспортной телекоммуникационной сети и от объема свободных ресурсов вдоль него. Это указывает на необходимость интегрального подхода и управления ресурсами CDN совместно с ресурсами ТКС [6].

Более того, в области управления ресурсами телекоммуникационной сети на данный момент получено множество заслуживающих внимания результатов, в том числе и в плане гарантированного качества обслуживания. При этом основным классом моделей являются потоковые модели, в которых наряду со структурой сети, учитываются параметры каналов связи и передаваемого трафика [7, 8].

Математическая модель управления ресурсами гибридной сети доставки контента с гарантированным качеством обслуживания

Таким образом, при построении математической модели гибридной сети доставки контента целесообразно ориентироваться на потоковую постановку задачи с возможностью подключения одного сервера P2P-сети к нескольким контент-серверам CDN-сети одновременно. В таком случае задача управления ресурсами может быть сформулирована как задача поиска совокупности серверов, которые будут выступать в качестве источников контента, а также множества маршрутов доставки данного контента от каждого сервера до потребителя (пользователя) с выполнением гарантий относительно качества предоставляемой услуги.

В рамках предлагаемой модели введем следующие множества: - множество периферийных серверов, на которых доступен контент -го типа, ; - множество всех серверов CDN; и - множества узлов (маршрутизаторов) и трактов передачи транспортной телекоммуникационной сети соответственно; - множество пользователей, генерирующих запросы на тот или иной контент; - множество возможных типов контента, распространяемых данной сетью. Причем справедливо , означающее, что в качестве получателя в рамках предлагаемой математической модели будем рассматривать не непосредственно конечного пользователя, а узел транспортной телекоммуникационной сети, к которому он подключен и который среди прочего выполняет функции сервера сети P2P (рис.1).

В качестве управляющих введем два типа переменных: переменные , которые указывают на долю контента -го типа, запрашиваемого -м пользователем и загружаемого с -го сервера, , и переменные , которые указывают на долю трафика, передаваемого по тракту передачи от -го маршрутизатора к -му, где индекс отражает тип передаваемого контента, а индекс связан с получателем , .

Исходя из физического смысла введенных переменных, на них накладываются ограничения вида

(11)

, (12)

где выражение (11) связано с одновременным подключением к нескольким источникам контента , а (12) обеспечивает сбалансированное использование ресурсов ТКС путем реализации многопутевого способа доставки контента.

С целью обеспечения целостности запрашиваемого контента потребуем

. (13)

В рамках введенных переменных закон сохранения потока для -го маршрутизатора транспортной телекоммуникационной сети примет вид

(14)

где - обозначение источника трафика для -го получателя.

В выражении (14) третье слагаемое указывает на долю трафика, поступающего на -й маршрутизатор ТКС от -го сервера, тогда условие (14) может быть дополнено

(15)

С ограниченными объемами сетевых ресурсов ТКС и вычислительных ресурсов серверов CDN связаны следующие выражения^

, (16)

, (17)

где - интенсивность трафика, создаваемого при передаче контента -го типа к -му пользователю; - максимальное число сессий -го типа, которое способен обслужить -й сервер (производительность сервера).

Одновременное использование совокупности серверов в качестве источника контента способствует повышению эффективности использования сетевых и вычислительных ресурсов в целом, однако не гарантирует требуемые значения скорости загрузки контента и задержки передачи. С целью обеспечения гарантированного качества обслуживания для каждого потока, создаваемого при доставке контента -го типа -му пользователю, введем в модель (11) - (17) дополнительное условие [9]

, (18)

где - вектор размера , элементы которого указывают на интенсивности потоков трафика, поступающих к пользователю от различных источников (серверов); - число задействованных в передаче контента серверов; - вектор размера , элементы которого содержат значения межконцевой средней задержки , допустимой в рамках транспортной ТКС; , , причем - квадратная матрица размера , - квадратная подматрицы размера , , - общее число узлов в сети доставки контента, учитывая число маршрутизаторов транспортной ТКС и количество серверов CDN; - матрица размера , являющаяся проекцией метрического тензора сети доставки контента в базисе узловых пар и контуров; - число трактов передачи, как между маршрутизаторами ТКС, так и между маршрутизаторами и серверами.

Поскольку условие (18) должно быть записано для каждого запроса в отдельности, можно опустить индексы и , указывающие на тип контента и запрашивающего его пользователя, тогда имеем, элементы вектора связаны с ранее введенными переменными следующим образом:

, (19)

где все переменные относятся к одной и той же паре и ; - номер узловой пары, создаваемой -м пользователем и -м сервером, .

Причем в соответствии с исходными данными суммарная интенсивность трафика , поступающего от множества источников, должна отвечать скоростным требованиям к качеству обслуживания, т.е.

, (20)

где - требуемая скорость передачи контента.

Фигурирующая в (18) матрица проекции метрического тензора вычисляется следующим образом:

, (21)

где - матрица ковариантного координатного преобразования, определяемая на основании структуры сети по правилам, описанным, например, в [10], - диагональная матрица размера , элементы главной диагонали которой при условии описания каждого сетевого интерфейса системой массового обслуживания рассчитываются согласно выражениям [8, 9]

, (22)

где - емкость буфера -го тракта передачи; - коэффициент загруженности

-го тракта передачи; и - интенсивность потока пакетов и пакетная пропускная способность -го тракта передачи соответственно, причем , при условии, что -й тракт передачи телекоммуникационной сети соответствует тракту в двухиндексной нумерации.

Таким образом, в рамках модели (11) - (22) процесс управления ресурсами сети доставки контента связан с поиском переменных двух типов: переменных , за счет которых реализуется управление ресурсами серверов CDN и решается задача маршрутизации запросов

в CDN, а также переменных , формализующих управление ресурсами транспортной телекоммуникационной сети и обеспечивающих решение задачи многопутевой маршрутизации

в ней. При этом в качестве целевой функции может выступать стоимостная функция

, (23)

где - вектор, объединяющий в себе переменные ; - вектор, объединяющий переменные ; , - векторы весовых коэффициентов, определяющие стоимость использования сетевых и вычислительных ресурсов соответственно.

Однако поскольку одним из требований к управлению сетью доставки контента является сбалансированное использование всех ее ресурсов, целесообразно в качестве целевой функции использовать [6]

, (24)

где , - весовые коэффициенты, - управляемый порог использования канальных

ресурсов транспортной телекоммуникационной сети, ; - управляемый порог

использования вычислительных ресурсов всех серверов CDN, , , .

Выводы

Основными проблемами, с которыми приходится сталкиваться при решении задачи управления гибридной сетью доставки контента, являются, во-первых, необходимость гарантированного обеспечения требуемого качества предоставления услуги, как минимум по двум показателям: скорости и задержке загрузки контента, во-вторых, необходимость балансировки нагрузки между CDN и P2P-сетями, а также сбалансированного использования ресурсов внутри каждой из них. Предложенная в статье математическая модель позволяет сформулировать задачу управления ресурсами гибридной сети доставки контента как оптимизационную; скоординировать в ее рамках решение задач управления ресурсами CDN и ТКС, заключающиеся в выборе контент-сервера и маршрутов его доставки к конечному пользователю; обеспечить гарантированное качество обслуживания по скоростным и временным показателям сетевого уровня; достичь высокой эффективности использования сетевых и вычислительных ресурсов за счет многопутевого способа маршрутизации и перераспределения запросов между серверами CDN.

Список литературы

контент обслуживание сеть гибридный

1. Content Delivery Networks / Buyya, Rajkumar; Pathan, Mukaddim; Vakali, Athena (Eds.). - Springer, 2008. - 418 p. - (Series: Lecture Notes in Electrical Engineering).

2. ZhiHui Lu, Ye Wang, Yang Richard Yang. An Analysis and Comparison of CDN-P2P-hybrid Content Delivery System and Model // Journal of Communications. - 2012. -Vol. 7, N. 3. - Р. 232 - 245.

3. Bektas, T., Oguz, O., Ouveysi, I. Designing cost-effective content distribution networks // Computers & Operations Research. - 2007. - 34 (8). - Р. 2436 - 2449.

4. Bektas, T., Cordeau, J-F., Erkut, E., Laporte, G. Exact algorithms for the joint object placement and request routing problem in content distribution networks // Computers & Operations Research. - 2008. - 35 (12). - Р. 3860 - 3884.

5. Datta, A., Dutta, K., Thomas, H., VanderMeer, D. World Wide Wait: A Study of Internet Scalability and Cache Based Approached to Alleviate it // INFORMS Management Science. - 2003. - Vol. 49, Issue 10. - P. 1425 - 1444.

6. Евсеева, О.Ю., Кадер, М.Б. Математическая модель маршрутизации запросов в сетях доставки контента // Системи обробки інформації. - 2012. - № 9 (107). - С. 165 - 170.

7. Лемешко, А.В., Вавенко, Т.В. Усовершенствование потоковой модели многопутевой маршрутизации на основе балансировки нагрузки // Проблеми телекомунікацій. - 2012. - № 1 (6). - С. 12 - 29. - Режим доступу: http://pt.journal.kh.ua /2012/1/1/121 lemeshko_multipath.pdf.

8. Лемешко, А.В., Евсеева, О.Ю. Тензорная модель многопутевой маршрутизации с гарантиями качества обслуживания одновременно по множеству разнородных показателей // Проблеми телекомунікацій. - 2012. - № 4 (9). - С. 16 - 31. - Режим доступа: http://pt.journal.kh.ua/2012/4/1/124_lemeshko_tensor.pdf.

9. Евссева, О.Ю. Тензорная модель многополюсной телекоммуникационной сети // Радиотехника. - 2013. - Вып. 175.

10. Математичні основи теорії телекомунікаційних систем / В.В. Поповський, С.О. Сабурова, В.Ф. Олійник, Ю.І. Лосєв, Д.В. Агеєв та ін.: За заг. ред. В.В. Поповського. - Харків : ТОВ «Компанія СМІТ», 2006. - 564 с.

Размещено на Allbest.ru