RU   EN

ДонНТУ   Портал магістрів

Рум'янцев Дмитро Артемович

Факультет комп'ютерних інформаційних технологій та автоматики

Кафедра автоматики та телекомунікації (АТ)

Спеціальність « Інфокомунікаційні технології та системи зв'язку »

Дослідження механізмів керування трафіком у Центрах обробки даних (ЦОД)

Науковий керівник: д.т.н., проф. кафедри АТ Турупалов Віктор Володимирович

Резюме Біографія Реферат

Дослідження механізмів керування трафіком у Центрах обробки даних (ЦОД)

Содержание

• Вступ
• 1. Актуальність теми
• 2. Мета і завдання дослідження, плановані результати
• 3. Огляд досліджень і розробок
• 3.1 Порівняльний аналіз топологій ЦОД
• 3.2 Аналіз методів управління трафіком ЦОДа
• 3.3 Аналіз загальних стратегій побудови оптичної мережі із забезпеченням параметрів якості обслуговування
• 4. Аналіз підходів до маршрутизації та призначення спектра в оптичних мережах ЦОД
• 4.1 Порівняльний аналіз топологій ЦОД
• 4.2 Аналіз політик розподілу спектра для маршрутизації
• Висновок
• Список джерел

Вступ

Впровадження хмарних і ресурсномістких додатків призвело до підвищення навантаження на глобальні центри обробки даних (ЦОД). Отже, з'явилася необхідність у високій продуктивності із забезпеченням необхідних параметрів якості обслуговування (QoS). Для їх забезпечення розроблено спеціальні транспортні протоколи і методи управління трафіком, реалізовані як в апаратних, так і в програмних засобах ЦОДів. Основні складові компоненти мереж ЦОДа, комутатори стійок (ToR, Top of Rack) [1],повинні підключатися через велике міжз'єднання, що дає змогу машинам обмінюватися даними між стійками із серверами. Так, описана мережа має діяти як величезний неблокувальний комутатор, до якого безпосередньо під'єднані всі сервери, що дає змогу останнім одночасно обмінюватися даними з максимальною швидкістю.

Одним із відомих рішень такої задачі є еластичні (EON, Elastic Optic Network) або програмно-конфігуровані оптичні мережі, для яких є можливість використовувати маршрутизацію і призначення довжини хвилі (RWA, Routing and wavelength assignment), а також стратегії захисту і відновлення. Розглянемо запропоноване рішення в рамках поставленого науково-дослідного завдання.

1. Актуальність теми

Сучасні технології оптичної комутації дають можливість забезпечити більшу пропускну здатність. Однак, існуючі обмеження, такі як залежність від використовуваної топології, використання мікро-електромеханічних перемикачів (МЕМП), а також використання механізму мультиплексування з розподілом за довжиною хвилі (WDM), зменшують ефективність обробки надхожого трафіку. Таким чином, тема магістерської дисертації, спрямована на дослідження та розробку механізмів управління трафіком у центрах обробки даних є актуальною.

2. Мета і завдання дослідження, плановані результати

Метою роботи є підвищення ефективності використання ресурсів еластичних оптичних мереж ЦОДів із забезпеченням параметрів якості обслуговування за рахунок розробки методу розподілу частотних інтервалів і повторного використання смуги пропускання.

Для досягнення поставленої мети сформульовано та вирішено такі завдання:

• аналіз проблем ефективного управління трафіком ЦОДів;
• аналіз наявних математичних моделей і методів розподілу спектра оптичної мережі із забезпеченням параметрів якості обслуговування;
• розроблення математичної моделі та методу розподілу частотних інтервалів і повторного використання смуги пропускання із забезпеченням якості обслуговування;
• оцінка ефективності розробленого методу шляхом імітаційного моделювання та вироблення рекомендацій щодо його практичного використання.

Об'єктом дослідження є процес перерозподілу оптичних ресурсів із забезпеченням якості обслуговування.

Предмет дослідження: методи ефективного використання доступних ресурсів оптичної мережі.

Методи дослідження. Для розробки математичних моделей і методів підвищення ефективності використання ресурсів оптичної мережі використовувалися методи маршрутизації та розподілу спектра в оптичних мережах. Для розробки методу розподілу спектра оптичної мережі із забезпеченням якості обслуговування використовувалися методи теорії графів, статистичного аналізу; для аналізу запропонованих математичних моделей використовувалися методи математичного моделювання, математичного програмування та імітаційного моделювання.

Під час розв'язання поставлених задач отримано наступний науковий результат: набув подальшого розвитку метод підвищення ефективності використання мережевих ресурсів. Новизна методу полягає в удосконаленні методу розподілу спектра оптичної мережі із забезпеченням параметрів якості обслуговування.

У рамках магістерської роботи планується отримання таких наукових і практичних результатів:

1. Набув подальшого розвитку метод підвищення ефективності використання мережевих ресурсів. Новизна методу полягає в удосконаленні методу розподілу спектра оптичної мережі із забезпеченням параметрів якості обслуговування;
2. Показано, що запропонована стратегія розподілу спектра забезпечує зменшення значення ймовірності мережевого блокування на 46 %, при підвищенні продуктивності на 22 %.

3. Огляд досліджень і розробок

3.1 Порівняльний аналіз топологій ЦОД

• «повне дерево» [2]. Як показано на рис. 3.1, топологія являє собою топологію багатокореневого дерева, у якій кожен корінь називається основним комутатором. Її можна розглядати як згорнуту мережу Кло. Збільшуючи кількість коренів, можна зменшити коефіцієнт переприйому (з огляду на фіксовану ємність каналу).
  

  Рисунок 3.1 — Топологія «повне дерево»

  Ця топологія забезпечує високу пропускну здатність, використовуючи велику кількість менш дорогих комутаторів, що дає змогу підтримувати велику кількість серверів за набагато менших витрат. До недоліків цієї топології належить використання складної конфігурації маршрутизації на комутаторах, для уникнення утворення петель під час використання доступних шляхів під час балансування навантаження;

• "лист-стовбур", рис. 3.2, дворівнева топологія, де "листя" (ToR-комутатори) прив'язані до серверів, а кожний магістральний комутатор безпосередньо під'єднаний до всіх "листових" комутаторів, подібно до дводольного графа.
  

  Рисунок 3.2 — Топологія «лист-стовбур»

  Канали, підключені між серверами і кінцевими комутаторами, можуть мати пропускну здатність, відмінну від каналів, що з'єднують кінцеві комутатори з магістраллю. Топологія спрощує розширення ємності і портів (шляхом додавання більшої кількості магістральних або листових комутаторів), а також дає змогу безпосередньо використовувати маршрутизацію з підтримкою балансування навантаження без створення петель. До недоліку топології можна віднести збільшення витрат на магістральні комутатори з великою кількістю портів високої ємності при збільшенні кількості серверів у кластері

• віртуальний рівень 2 (VL2) [3], представлений на рис. 3.3, характеризується тим, що реалізує всі функції з маршрутизації та пересилання поверх згорнутих мереж Кло.
  

  Рисунок 3.3 — Топологія VL2

  Відмінність цієї топології від "повне дерево" полягає в тому, що пропускна здатність ліній між комутаторами більша, ніж у ліній сервер-комутатор. Це вимагає меншої кількості фізичних ліній між рівнями агрегації та ядра. для з'єднання рівня агрегації та ядра. Кожен ToR-комутатор під'єднаний до двох комутаторів агрегації таким чином, що кожен комутатор агрегації під'єднується до рівної кількості прикордонних комутаторів;

• «медуза» [4], представлена на рис. 3.4, топологія, у якій порти ToR-комутаторів підключаються випадковим чином доти, доки не можна буде додати більше каналів; потім для будь-якого S-комутатора з двома або більше вільними портами наявний канал A-B видаляється і додаються два канали між двома вільними портами S і двома кінцями віддаленого мережевого каналу (тобто A-S і B-S), поки у комутатора не буде більше, ніж один порт.
  

  Рисунок 3.4 — Топологія «медуза»

  ТОскільки ToR-комутатори під'єднані безпосередньо, середній шлях (кількість стрибків) значно менший, як порівняти з трирівневими згорнутими мережами Кло. До переваг топології можна віднести її масштабованість: при повному завантаженні каналів, дана топологія підтримує більше серверів, ніж топологія "повне дерево". Крім того, за тієї самої кількості відмов ліній, у топології "медуза" середня пропускна здатність на сервер вища, ніж у топології "повне дерево". До недоліків цієї топології можна віднести низьку ефективність наявних схем маршрутизації. Для цієї топології передбачається використовувати спільно потокову маршрутизацію за найкоротшими шляхами з багатошляховою TCP (MPTCP). [5].

• D-кластер, представлена на рис. 3.5, є ієрархічною топологією ЦОДа [6] , у якій кластер вищого рівня будується об'єднанням кількох структур кластерів нижчого рівня.
  

  Рисунок 3.5 — Топологія D-кластер

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

• топологія «розширювач» [7], представлена на рис. 3.6, заснована на розширених графах [8].
  

  Рисунок 3.6 — Tопологія «розширювач»

  Вона поєднує в собі всі поліпшення продуктивності топології "медуза", як порівняти з топологією "повне дерево", з вищою пропускною спроможністю в міру поступового розширення мережі. Ця топологія створюється шляхом з'єднання декількох метавузлів на основі таких правил: по-перше, кожен метавузол складається з рівної кількості ToR-комутаторів; по-друге, жодні два ToR-комутатори не пов'язані всередині одного і того ж метавузла; по-третє, для з'єднання кожної пари метавузлів використовується однакова кількість ліній. До переваг представленої топології можна віднести її структурованість, що підвищує передбачуваність станів ЦОДа.

  Незважаючи на всі перераховані вище переваги топологій ЦОД, перехід на оптичні технології мережі дасть змогу забезпечити більшу пропускну спроможність (Тбіт/с у кожному волокні, що маршрутизується) незалежно від відстані. Також оптична комутація може бути гнучкішою завдяки багатохвильовій маршрутизації, що дає змогу не тільки вдосконалити наявні топології ЦОДів, а й підвищувати параметри якості обслуговування.

  Прозорі оптичні мережі - мережі, орієнтовані на з'єднання, які можна налаштувати під час роботи мережі, щоб вони найкраще підходили для мінливого трафіку ЦОДів. Порівняно з електричними, оптичні перемикачі розсіюють менше тепла, що призводить до менших витрат на охолодження. Крім того, оптична комутація дає змогу плавно збільшити пропускну здатність до 100 Гбіт/с і вище, щоб задовольнити зростаючий попит на системи зберігання даних.

3.2 Аналіз методів управління трафіком ЦОДа

Наразі існує досить велика кількість робіт, спрямованих на опис різних методів управління трафіком, що переслідують ті чи інші цілі, рисунок 3.7.

З наведеної на малюнку взаємодії зрозуміло, що залежно від поставленої проблеми і переслідуваної мети, наприклад, забезпечення параметрів якості обслуговування, необхідно використовувати рекомендовані алгоритми з поправкою на використання останній в оптичних мережах. також варто зазначити, що залежно від використовуваної архітектури оптичних мереж варто досліджувати не тільки питання забезпечення параметрів якості обслуговування, а й питання живучості.

3.3 Аналіз загальних стратегій побудови оптичної мережі із забезпеченням параметрів якості обслуговування

Для звичайних оптичних мереж живучість є важливим параметром. Швидке відновлення, завдяки захисту підканалу, для мереж WDM пояснюється в [9]. Принцип цієї процедури такий: велика оптична мережа розділена на менший домен і пропонований захист підканалу, а також захист загального каналу.

Живучість у разі виходу з ладу оптичної мережі описана в [10]. Очевидно, що в представленій ситуації, яка виникає через стихійні лиха, необхідний різноманітний підхід.

У роботі [11] вивчали схему проміжного і попереднього резервування в еластичних оптичних мережах. В [12-13] запропоновано схеми захисту якості обслуговування (QoS) для гнучких оптичних мереж. В [14] представлено механізм маршрутизації та призначення спектра в еластичних оптичних мережах.

Схеми захисту/відновлення каналів і ліній у разі відмов (лінія і вузол) в оптичних мережах WDM подано в [15]. Відмова лінії та вузла в оптичних мережах призводить до одночасної відмови декількох оптичних каналів, що призводить до величезних втрат даних і доходів для оператора мережі. Вимоги до смуги пропускання довжини хвилі для основного і резервного маршруту та призначення маршрутизації розглянуті в [16]. Тут же описано пропонований підхід, що забезпечує живучість у разі множинних відмов у мережі, пояснено час відновлення під час перемикання і час відновлення.

Стратегію відновлення спільно використовуваної смуги пропускання в еластичних оптичних мережах запропоновано в [17]. В [18] проаналізовано ключові особливості живучості оптичних мереж. Відновлення мережі визначається як мережа, яка надає безперервні послуги навіть після того, як у мережі стався збій. Пропускна здатність оптоволоконної мережі вказана в Гбіт/с і Тбіт/с.

Робота [19] присвячено схемі відновлення квазіканалу, подано визначення основних мережевих параметрів різних топологій (COST239, NSFNET і ARPANET), коефіцієнти надання смуги пропускання та використання ресурсів.

4 Аналіз підходів до маршрутизації та призначення спектра в оптичних мережах ЦОД

4.1 Аналіз підходів до маршрутизації в еластичних оптичних мережах ЦОД

Проблему маршрутизації та призначення спектра в еластичних оптичних мережах можна розділити на два напрямки: онлайн і офлайн RSA. Під час роботи в режимі офлайн, для успішної RSA, необхідне знання топології та вимоги до обслуговування трафіку заздалегідь. Для роботи в режимі онлайн, заздалегідь відома топологія мережі, а вимоги до обслуговування трафіку надходять у довільному порядку.

Для фіксованої маршрутизації маршрути кожної пари джерело-приймач визначені наперед. Коли надходить запит на з'єднання, алгоритми встановлюють світловий канал за заздалегідь визначеним маршрутом. Під час маршрутизації з мінімальною кількістю переприймань, вага кожного з'єднання встановлюється рівною 1, і обирається маршрут, що відповідає мінімальному маршруту. Під час маршрутизації за найкоротшим шляхом, як вагу використовують фізичну довжину лінії, і шлях обирають із використанням алгоритмів знаходження найкоротшого шляху, таких як алгоритм Дейкстри.

Алгоритми адаптивної маршрутизації динамічно вибирають маршрути залежно від стану мережі. У цьому разі невикористовуваним каналам у мережі призначається єдина вартість, а під час надходження запиту на з'єднання маршрут із мінімальною вартістю обирається динамічно. Для маршрутизації найменш завантаженого шляху з'єднання визначається кількістю вільних частотних інтервалів, доступних у каналі, і для встановлення з'єднання обирається канал із максимально доступними вільними довжинами хвиль. Алгоритм маршрутизації потужностних серій, заснований на біо-компонентах для адаптивної маршрутизації, де він може оптимізуватися і адаптуватися до умов мережі. На етапі планування, функція вартості каналу, така як нормалізована доступність каналу і нормалізована довжина каналу, використовуються для визначення вхідної змінної. На етапі експлуатації алгоритму використовується алгоритм рою частинок для оптимізації показників продуктивності мережі.

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

В [21] автори запропонували близьке до стану каналу формулювання проблеми RSA, відоме як завдання маршрутизації, присвоєння довжини хвилі та розподілу спектра. Завдання спрямоване на вибір набору швидкостей лінії для кожного запиту разом із відповідним набором світлових шляхів для мінімізації використання потужності загального спектра в мережі. В [22] автори запропонували алгоритм маршрутизації, який обчислює кілька альтернативних шляхів для кожного запиту на з'єднання. Потім алгоритм розподілу спектра використовується для визначення набору доступних суміжних слотів, які призначені запиту. Автори [23] запропонували адаптивний алгоритм маршрутизації для розв'язання першої підзадачі таблиць маршрутизації в кожному вузлі та пов'язування ймовірності з кожною парою. Тоді оптимізаційний алгоритм мурашиної колонії виконується безперервно, який оновлює ці ймовірності на основі використання спектра, і визначається оптимальний шлях. Після вибору шляху для розподілу спектра використовується політика перший відповідний.

Автори в [24-25] використали задачу цілочисельного програмування зі стратегією призначення спектра перший підходящий і знайшли оптимальний розв'язок проблеми RSA/RMSA, використовуючи попередньо розраховані - найкоротших шляхів для маршрутизації. В [26] адругі сформулювали завдання RSA як завдання, засноване на цілочисельному програмуванні, з метою знайти наскрізний шлях для запиту на з'єднання і призначити частотні слоти, задовольняючи обмеженням безперервності спектра і суміжності. Результат моделювання показує, що запропонований евристичний підхід забезпечує зниження ймовірності мережевого блокування до 9,4% з часом виконання менш ніж одну секунду.

В [27] автори розглянули динамічну версію проблеми RMSA, розклавши її на підзадачі вибору швидкості динамічної маршрутизації та вибору каналу. Автори додатково використовували теорію графів для розв'язання задачі динамічної маршрутизації та вибору каналу. В [28]представили два різних однокрокових онлайн-алгоритми RSA. У першому алгоритмі використовувався модифікований алгоритм пошуку найкоротшого шляху Дейкстри, який використовував канали з достатньою кількістю піднесучих у порядку зростання довжини шляху. Другий однокроковий алгоритм RSA будує вектор шляху у вихідному вузлі таким чином, щоб усі канали кожного шляху мали достатній безперервний спектр. Потім алгоритм шукає вектори шляху, щоб знайти канал із достатнім доступним спектром і мінімальною вартістю.

Автори в [29] представили модель цілочисельного програмування статичної проблеми RSA в EON з метою мінімізації кількості піднесучих в EON. Автори також проаналізували верхню і нижню межі максимальної кількості піднесучих у звичайних і кільцевих мережах. Два евристичні алгоритми - збалансований розподіл спектра і найкоротший шлях із максимальним повторним використанням спектра - запропоновано для розв'язання проблеми RSA у великій мережі. Результат моделювання підтверджує розв'язання моделі цілочисельного програмування та евристичних алгоритмів при оптимальному використанні ресурсів.

В [30] адругі представили архітектуру зі змішаною лінійною швидкістю (MLR) для обслуговування різнорідного трафіку. Автори розробили математичну ситуаційну модель для проектування енергоефективних та економічних MLR оптичних мереж. Оцінка продуктивність розробленої моделі при різних сценаріях навантаження трафіку показує, що MLR мережі можуть підвищити енергоефективність мережевої архітектури.

Автори в [31] запропонували алгоритм маршрутизації з адаптацією до відстані, призначення спектра та реконфігурації для розв'язання задачі надання запитів у встановлені терміни (DDR) у мережах ЕОС. Надання DDR вимагає, щоб дані передавалися протягом заданого терміну без накладання конкретних вимог до пропускної здатності. Результати моделювання показують значне поліпшення продуктивності завдяки перерозподілу пропускної здатності. Автори в [32] представили проблему RSA, використовуючи канали як набір суміжних піднесучих заданої ширини для моделювання обмеження безперервності спектра. Для даної ширини спектра всі можливі канали з піднесучими визначені на кожній ланці мережі. Тоді проблема RSA трансформується в проблему маршрутизації та розподілу каналів безперервного спектра. Цей механізм призводить до більш компактного формулювання задачі цілочисельного програмування, що забезпечує значне скорочення часу роботи порівняно з прямими обмеженнями безперервності спектра.

Автори [33-34] запропонували два алгоритми RSA, засновані на алгоритмах -найкоротших шляхів, що використовують FF для призначення спектра в динамічному сценарії. В [35] автори представили триступеневу схему динамічної маршрутизації з урахуванням якості передавання (QoT), рівня модуляції та призначення спектра (QoT-aware RSA). Для обчислення шляху використовуються два модифіковані алгоритми: Дейкстри та алгоритм балансування трафіку для присвоєння спектра. Результати моделювання показують, що запропонований алгоритм працює ефективно і забезпечує вищий коефіцієнт співвідношення рівня сигнал/шум оптичного сигналу, як порівняти зі стратегіями FF, RF і SA.

Автори [36-37] використали багатоколійну маршрутизацію, розбиваючи запит вхідного трафіку на кілька запитів і використовуючи для їхнього передавання кілька шляхів. Симуляційний аналіз показує, що запропоновані схеми працюють ефективніше порівняно з одноколійною маршрутизацією.

Подальші дослідження алгоритмів маршрутизації показали, що необхідно застосовувати додаткові механізми, такі як фрагментація спектра.

4.2 Аналіз політик розподілу спектра для маршрутизації

Алгоритм BLSA, щоб зменшити максимальну кількість піднесучих у волокні, заснований на балансуванні навантаження. Спочатку алгоритм генерує k-найкоротших шляхів для кожної пари джерело-приймач. Потім, на основі оцінки завантаження волокна вибирається канал. Алгоритм ухвалення рішення простий: вибирається той канал, максимальне завантаження якого мінімальне. Розподіл спектра потім здійснюється за допомогою стратегій призначення: перша відповідність (First Fit, FF), точна відповідність (Exact Fit, EF) або випадкова відповідність або (Random Fit, RF).

Завантаження волокна можна визначити згідно з формулою (4.1):