В даній статті представлено застосування м'яких обчислювальних методів для вирішення завдання проектування і оптимізації хмарних мереж розповсюдження контенту (CDN). Для вирішення проблеми виділення ресурсів для побудови мережевої інфраструктури застосовується багатоцільовий підхід з урахуванням мети мінімізації вартості віртуальних машин, мережі та сховища, а також максимізації якості обслуговування, що надається кінцевим користувачам. Пропонується конкретна модель посередництва, яка дозволяє одній хмарної CDN розміщувати декількох постачальників контенту, які застосовують стратегію спільного використання ресурсів. На основі запропонованої моделі посередництва вивчаються три багатоцільових еволюційних підходу оффлайновой оптимізації надання ресурсів, а для вирішення проблеми онлайнової маршрутизації контенту пропонується жадібний евристичний метод. Експериментальна оцінка запропонованого підходу виконується на наборі реалістичних окремих випадків. Отримані експериментальні результати показують, що запропонований підхід ефективний для проектування і оптимізації хмарних мереж розповсюдження контенту: Загальні витрати знижуються на 10,34% при збереженні високого рівня якості обслуговування.

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Ітурріага Фабра С.Д., Несмачний Кановас С.Є., Жени Бофріско Н., Дорронзоро Діаз Б., Черних О.М..


Design and optimization of Content Distribution Networks

This article presents the application of soft computing methods for solving the problem of designing and optimizing cloud-based Content Distribution Networks (CDN). A multi-objective approach is applied to solve the resource provisioning problem for building the infrastructure for the network, considering the objectives of minimizing the cost of the virtual machines, network, and storage, and the maximization of the quality-of-service provided to end-users. A specific brokering model is proposed to allow a single cloud-based CDN to be able to host multiple content providers applying a resource sharing strategy. Following the proposed brokering model, three multiobjective evolutionary approaches are studied for the offline optimization of resource provisioning and a greedy heuristic method is proposed for addressing the online routing of contents. The experimental evaluation of the proposed approach is performed over a set of realistic problem instances. The obtained experimental results indicate that the proposed approach is effective for designing and optimizing cloud-based Content Distribution Networks: Total costs are reduced by up to 10.34% while maintaining high quality-of-service values.


Область наук:

  • Комп'ютер та інформатика

  • Рік видавництва: 2019


    Журнал: Праці Інституту системного програмування РАН


    Наукова стаття на тему 'КОНСТРУЮВАННЯ ТА ОПТИМІЗАЦІЯ МЕРЕЖ ПОШИРЕННЯ КОНТЕНТУ'

    Текст наукової роботи на тему «КОНСТРУЮВАННЯ ТА ОПТИМІЗАЦІЯ МЕРЕЖ ПОШИРЕННЯ КОНТЕНТУ»

    ?Б01: 10.15514 / КРКЛ8-2019-31 (2) -1

    Конструювання і оптимізація мереж розповсюдження контенту

    1 С.Д. Ітурріага Фабра, Оксю: 0000-0002-0212-7916 <Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.> 1 С.Є. Несмачний Кановас, Оксю: 0000-0002-8146-4012 <Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.> 1 Н. Жени Бофріско, Оксю: 0000-0002-4552-9210 <Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.> 2 Б. Дорронзоро Діаз, Оксю: 0000-0003-0481-790Х <Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.> 3,4,5А.Н. Черних, Оксю: 0000-0001-5029-5212 <Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.>

    1 Республіканський університет, Уругвай, 11300, Монтевідео, вул. Хуліо Еррера-і-Рейссіг, 565 2 Кадісскій університет, Іспанія, 11001, Кадіс, вул. Анча, 16 3 Центр наукових досліджень та вищої освіти, Мексика, 22860, Нижня Каліфорнія, Енсенада, ш. Тіхуана-Енсенада, 3918 4 Інститут системного програмування РАН ім. В.П. Іваннікова, 109004, Россия, г. Москва, вул. А. Солженіцина, д. 25. 5Южно-Уральський державний університет, 454080, Росія, м Челябінськ, вул. Леніна, 76

    Анотація. В даній статті представлено застосування м'яких обчислювальних методів для вирішення завдання проектування і оптимізації хмарних мереж розповсюдження контенту (CDN). Для вирішення проблеми виділення ресурсів для побудови мережевої інфраструктури застосовується багатоцільовий підхід з урахуванням мети мінімізації вартості віртуальних машин, мережі та сховища, а також максимізації якості обслуговування, що надається кінцевим користувачам. Пропонується конкретна модель посередництва, яка дозволяє одній хмарної CDN розміщувати декількох постачальників контенту, які застосовують стратегію спільного використання ресурсів. На основі запропонованої моделі посередництва вивчаються три багатоцільових еволюційних підходу оффлайновой оптимізації надання ресурсів, а для вирішення проблеми онлайнової маршрутизації контенту пропонується жадібний евристичний метод. Експериментальна оцінка запропонованого підходу виконується на наборі реалістичних окремих випадків. Отримані експериментальні результати показують, що запропонований підхід ефективний для проектування і оптимізації хмарних мереж поширення контенту: загальні витрати знижуються на 10,34% при збереженні високого рівня якості обслуговування.

    Ключові слова: хмарні обчислення; оптимізація; еволюційні алгоритми; мережі розповсюдження контенту

    Для цитування: Ітурріага Фабра С.Д., Несмачний Кановас С.Є., Жени Бофріско Н., Дорронзоро Діаз Б., Черних О.М. Конструювання і оптимізація мереж розповсюдження контенту. Праці ІСП РАН, тому 31, вип. 2, 2019, сс. 15-20. DOI: 10Л5514ЛSPRAS-2019-31 (2>1

    Design and optimization of Content Distribution Networks

    1 S.D. Iturriaga Fabra, ORCID: 0000-0002-0212-7916 <Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.>

    1 S.E. Nesmachnow Canovas, ORCID: 0000-0002-8146-4012 <Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.>

    1 G. Goni Bofrisco, ORCID: 0000-0002-4552-9210 <Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.>

    2 B. Dorronsoro Diaz, ORCID: 0000-0003-0481-790X <Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.>

    3,4,5A.N. Tchernykh, ORCID: 0000-0001-5029-5212 <Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.> 1 Universidad de la Republica Julio Herrera y Reissig 565, Montevideo, 11300, Uruguay 2 Universidad de Cadiz C / Ancha 16, Cadiz, 11001, Spain 3 Centro de Investigacion Cientifica y Educacion Superior de Ensenada Carretera Ensenada-Tijuana No.3918 Zona Playitas, Ensenada, Baja California, 22860, Mexico 4 Ivannikov Institute for System Programming of the Russian Academy of Sciences, 25, Alexander Solzhenitsyn st., Moscow, 109004, Russia

    5 South Ural State University, Chelyabinsk, 76 Lenina St., Chelyabinsk, 454080, Russia

    Abstract. This article presents the application of soft computing methods for solving the problem of designing and optimizing cloud-based Content Distribution Networks (CDN). A multi-objective approach is applied to solve the resource provisioning problem for building the infrastructure for the network, considering the objectives of minimizing the cost of the virtual machines, network, and storage, and the maximization of the quality-of-service provided to end-users. A specific brokering model is proposed to allow a single cloud-based CDN to be able to host multiple content providers applying a resource sharing strategy. Following the proposed brokering model, three multiobjective evolutionary approaches are studied for the offline optimization of resource provisioning and a greedy heuristic method is proposed for addressing the online routing of contents. The experimental evaluation of the proposed approach is performed over a set of realistic problem instances. The obtained experimental results indicate that the proposed approach is effective for designing and optimizing cloud-based Content Distribution Networks: total costs are reduced by up to 10.34% while maintaining high quality-of-service values.

    Keywords: cloud computing; optimization; evolutionary algorithms; content distribution networks.

    For citation: Iturriaga Fabra S.D., Nesmachnow Canovas S.E., Goni Bofrisco G., Dorronsoro Diaz B., Tchernykh A.N. Soft computing methods for design and optimization of cloud-based Content Distribution Networks. Trudy ISP RAN / Proc. ISP RAS, vol. 31, issue 2, 2019. pp. 15-20 (in Russian). DOI: 10.15514 / ISPRAS-2019-31 (2) -1

    1. Введення

    Термін «мережа розповсюдження контенту» (Content Distribution Network, CDN), часто замінюється терміном «мережу доставки контенту» (content delivery network), використовується для позначення розподілених мереж для доставки послуг і контенту користувачам. CDN є ключовими інфраструктурами для ефективного надання по всьому світу масштабованих інтернет-послуг, здатними відповідати конкретним угодам про рівень обслуговування між постачальниками послуг і кінцевими користувачами, що дозволяє забезпечувати високу якість обслуговування (Quality of Service, QoS). Основною метою CDN є поширення контенту серед кінцевих користувачів з високою доступністю і високою продуктивністю. Для досягнення цієї мети CDN повинна включати велику кількість серверів, розподілених по центрам обробки даних по всьому світу. Оскільки потрібна велика комп'ютерна інфраструктура, бізнес-модель CDN економічно невигідна для невеликих постачальників контенту, у яких немає власних центрів обробки даних або подібних великих обчислювальних систем. Традиційним вирішенням цієї проблеми, що дозволяє створити прибуткову бізнес-модель для невеликих постачальників контенту, є оренда послуг CDN у великих постачальників 16

    CDN. Однак в останні п'ять років спостерігається зростаюча тенденція до використання глобальної распределенности і еластичності хмарних сервісів для створення хмарних CDN [1,2,3,4]. Однією з основних проблем підходу хмарних CDN є надання необхідних ресурсів в хмарі. Це добре відома важка проблема, яка була властива більшості хмарних програмних рішень [5]. Ми представляємо підхід до вирішення проблеми надання ресурсів хмарного постачальнику CDN. Підхід заснований на обліку точок зору як постачальника хмарних послуг, так і кінцевих користувачів. У базовій моделі пропонується одночасна оптимізація системних і призначених для користувача метрик, що розширює загальні підходи, представлені в попередніх роботах з відповідних літературних джерел. Вводиться багатоцільова модель оптимізації для обліку витрат на одночасну оптимізацію, включаючи витрати на оренду віртуальних машин (ВМ), ресурсів зберігання даних і забезпечення необхідної пропускної спроможності мережі, а також QoS, що надається кінцевим користувачам.

    У запропонованій моделі враховуються деякі особливості сучасних хмарних платформ, в тому числі, географічне розташування ресурсів, наявність знижок на оптові покупки і можливість оренди зарезервованих примірників. Крім того, подано загальну бізнес-модель, що включає поняття агента віртуального брокера [6], де брокер використовує мультітенантний підхід для зниження витрат на одночасне керування кількома постачальниками контенту. Ця мультітенантная модель дозволяє брокеру скористатися пільговими цінами для масових віртуальних машин і стратегіями спільного використання ресурсів.

    Ми розробили три багатоцільових еволюційних алгоритму (MultiObjective Evolutionary Algorithm, MOEA) для вирішення проблеми надання хмарних ресурсів і жадібний евристичний алгоритм для вирішення підзадачі маршрутизації запитів контенту. Запропоновані алгоритми оцінюються на наборі реалістичних прикладів, побудованих з використанням методології, запропонованої Бусарєв і ін. [7]. Ця методологія враховує кілька загальних характеристик, виявлених в робочих навантаженнях Web, таких як Zipf-подібний розподіл популярності контенту, розподіл «з важким хвостом» (heavy-tailed) розмірів контенту великої кількості контенту, до якого звертаються тільки один раз

    2 Порівняння пропонованої бізнес-моделі зі звичайною бізнес-моделлю

    У традиційній бізнес-моделі (Business As Usual, BAU) відсутня сутність «брокер». У такій моделі кожен постачальник контенту повинен розгорнути свою власну індивідуальну хмарну CDN. У цьому розділі ми представляємо економію бюджету, розрахованого по запропонованій нами моделі, в порівнянні з моделлю BAU. У більшості реальних сценаріїв нас будуть цікавити рішення з високою якістю обслуговування. Тому для порівняння ми будемо брати до уваги тільки рішення з QoS від 0,95 і вище.

    На рис. 1 представлена ​​середня економія витрат, що отримується при застосуванні пропонованої нами моделі, в порівнянні з моделлю BAU.

    12%

    ill

    Smalt Medium Large

    ?r ob term size

    Мал. 1. Середня економія витрат на забезпечення рішень з високою якістю обслуговування (QoS>0,95) в порівнянні зі звичайним сценарієм бізнесу Fig. 1. Average budget savings of computed high quality of service solutions (QoS>0.95) when compared to

    a business as usual scenario. Результати показують зменшення економії при зменшенні розміру розв'язуваної задачі. Це пов'язано з тим, що чим більше завдання, тим більше можливостей для її поліпшення її рішення. Наш підхід найбільш ефективний при роботі з великорозмірними завданнями, обчислювальними рішеннями з середньою економією бюджету на 10,34 ± 0,21%. Для завдань середнього розміру розрахункова середня економія бюджету складає 7,30 ± 0,19%, а для невеликих - 5,21 ± 0,26%. Результати показують, що наша система бізнес-моделі і алгоритм планування забезпечують економію бюджету в середньому приблизно на 7,6%.

    3 Висновок і плани на майбутнє

    У даній роботі розглядається багатоцільова проблема надання ресурсів в хмарі для створення хмарної CDN. Цілі оптимізації - мінімізація віртуальних машин, вартості мережі і сховища, а також максимізація QoS для кінцевого користувача.

    Розглядається модель мультітенантного брокера, коли в одній хмарної CDN може розміщуватися декілька постачальників контенту. Введено новий об'єкт - брокер, службовець для управління мультітенантной хмарної CDN. Пропонується точна математична формулювання, а набір прикладів будується відповідно до реалістичної методологією, представленою Бусарєв і ін. [7].

    Через свою складність запропонована завдання розділена на дві підзадачі, для вирішення яких потрібні алгоритми оптимізації. Однією з підзадач є надання хмарних ресурсів, а інший - онлайн-маршрутизація запитів контенту. Порівняння пропонованої моделі брокерства з моделлю BAU показує, що наш підхід здатний знизити вартість хмарних ресурсів на 5,2-10,3% при збереженні високих значень QoS. Ці результати говорять про те, що пропонований нами підхід достатній для розгортання хмарних CDN з меншим бюджетом в порівнянні з моделлю BAU. Основні напрямки майбутньої роботи включають створення більш широкого набору окремих випадків і побудова більш точної функції QoS. З одного боку, більший набір прикладів забезпечить більш глибоке розуміння ефективності запропонованої моделі. З іншого боку, більш точна функція QoS, заснована, наприклад, на фактичних вимірах мережі, допоможе забезпечити більш реалістичні рішення

    а 854

    з >

    'V

    i 6 »

    на і-

    m 4 (4

    2%

    Список літератури / References

    [1] Gao G., Zhang W., Wen Y., Wang Z., Zhu W. Towards Cost-Efficient Video Transcoding in Media Cloud: Insights Learned from User Viewing Patterns. IEEE Transactions on Multimedia, vol. 17, no. 8, 2015-го, pp. 1286-1296.

    [2] Hu M., Luo J., Wang Y., Veeravalli B. Practical resource provisioning and caching with dynamic resilience for cloud-based content distribution networks. IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 8, 2014 року, pp. 2169-2179.

    [3] Jokhio F., Ashraf A., Lafond S., Lilius J. A computation and storage trade-off strategy for cost-efficient video transcoding in the cloud. In Proc. of the 39th Euromicro Conference Series on Software Engineering and Advanced Applications, 2013, pp. 365-372.

    [4] Xiao W., Bao W., Zhu X., Wang C., Chen L., Yang L.T. Dynamic request redirection and resource provisioning for cloud-based video services under heterogeneous environment. IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 7, 2016, pp. 1954-1967.

    [5] Zhang J., Huang H., Wang X. Resource provision algorithms in cloud computing: A survey. Journal of Network and Computer Applications, vol. 64, 2016, pp. 23-42.

    [6] Nesmachnow S., Iturriaga S., Dorronsoro B. Efficient heuristics for profit optimization of virtual cloud brokers. IEEE Computational Intelligence Magazine, vol. 10, no. 1, 2015-го, pp. 33-43.

    [7] Busari M., Williamson C. ProWGen: a synthetic workload generation tool for simulation evaluation of web proxy caches. Computer Networks, vol. 38, no. 6, 2002 pp. 779 - 794.

    Інформація про авторів / Information about authors

    Сантьяго Даміан ІТУРРІАГА Фабрі отримав ступінь PhD в галузі комп'ютерних наук в Республіканському університеті в 2018 р В даний час він є штатним дослідником і навчальним асистентом в Інституті комп'ютерних наук Інженерного факультеті Республіканського університету в Монтевідео, Уругвай. Його основні наукові інтереси включають в себе методи високопродуктивних обчислень і метаеврістікі для вирішення завдань оптимізації.

    Santiago Damian ITURRIAGA FABRA obtained Ph.D. degree in computer science from Universidad de la Republica (Uruguay) in 2017. Now he is the full-time researcher and teaching assistant at the Instituto de Computacion, Facultad de Ingenieria, Universidad de la Republica, Uruguay. His main research interests include high performance computing and metaheuristics methods for solving optimization problems.

    Серджо Енріке Несмачний Кановаса має ступінь PhD в області комп'ютерних наук, отриманої в Республіканському університеті, Уругвай. В даний час він займає посаду професора в Обчислювальному центрі Інституту комп'ютерних наук Інженерного факультету Республіканського університету. Основні наукові інтереси: паралельні та розподілені обчислення, наукові обчислення, еволюційні алгоритми і метаеврістіка, а також чисельні методи.

    Sergio Enrique NESMACHNOW CANOVAS has a Ph.D. degree in Computer Science from Universidad de la Republica, Uruguay. He currently holds an Aggregate Professor position in the Numerical Center (CeCal) at Computer Science Institute, Engineering Faculty. His main research interests are parallel and distributed computing, scientific computing, evolutionary algorithms and metaheuristics, and numerical methods.

    Херардо ГОНИ БОФРІСКО виконує дослідження в Центрі інформаційних технологій Республіканського університету. Його основним науковим інтересом є комп'ютерні мережі.

    Gerardo GONI BOFRISCO does research in Computer Engineering at Servicio Central de Informatica of Universidad de la Republica. His main research interest is computer networking.

    Бернабе ДОРРОНСОРО ДІАЗ отримав ступінь PhD в університеті Малаги, Іспанія. В даний час він є науковим співробітником факультету комп'ютерних наук і

    інженерії Кадісского університету. Він удостоєний стипендії Рамона-і-Кахала в Кадісськая університеті, Іспанія. У число його наукових інтересів входять автоматичне програмування, багатоцільова оптимізація, машинне навчання, управління ресурсами в центрах даних, хмарні обчислення, еволюційні алгоритми і т.д.

    Bernabe DORRONSORO DIAZ has a Ph.D. degree in Computer Science from University of Malaga. Currently he is a researcher assistant at the Computer Science Engineering Department of the University of Cadiz, Spain. He is the Ramon y Cajal Fellow at University of Cadiz. His research interests include automatic programming, multi- and many-objective optimization, exact approaches, machine learning, resource management for data-centers, cloud computing, sustainable computing, evolutionary algorithms, ets.

    Андрій Миколайович ЧОРНИХ отримав ступінь кандидата наук в Інституті точної механіки та обчислювальної техніки РАН. В даний час він є професором Центру наукових досліджень і вищої освіти в Енсенада, Нижня Каліфорнія, Мексика. У науковому плані його цікавлять багатоцільова оптимізація розподілу ресурсів в хмарному середовищі, проблеми безпеки, планування, евристики і метаеврістікі, енергозберігаючі алгоритми, інтернет речей і т.д.

    Andrei TCHERNYKH received his PhD degree at the Institute of Precision Mechanics and Computer Engineering of the Russian Academy of Sciences. Now he is holding a full professor position in computer science at CICESE Research Center, Ensenada, Baja California, Mexico. He is interesting in grid and cloud research addressing multi-objective resource optimization, both, theoretical and experimental, security, uncertainty, scheduling, heuristics and meta-heuristics, adaptive resource allocation, energy-aware algorithms and Internet of Things.


    Ключові слова: хмарні обчислення /ОПТИМІЗАЦІЯ /ЕВОЛЮЦІЙНІ АЛГОРИТМИ /МЕРЕЖІ РОЗПОВСЮДЖЕННЯ КОНТЕНТУ /CLOUD COMPUTING /OPTIMIZATION /EVOLUTIONARY ALGORITHMS /CONTENT DISTRIBUTION NETWORKS

    Завантажити оригінал статті:

    Завантажити