ВСТУП

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

Динамічні системи перерозподілу навантаження можна знайти у будь-якій області застосування сучасних телекомунікаційних мереж: розподільник навантаження у сучасних центрах обробки даних; протоколи керування потоками [2] в IP/MPLS; концепція SON (Self-Organization Network), на базі якої краще розгортати мобільні мережі 4-го покоління [3]. Але всі ці системи використовують різні методи, алгоритми та принципи організації задля вирішення задачі балансування навантаження (перерозподілу потоків).

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

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

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

Задля реалізації мети були поставлені наступні задачі:

–  аналіз сучасних тенденцій розвитку телекомунікаційної сфери та послуг, що надаються;

–  аналіз існуючих методів балансування навантаження (розподілення потоків) в різноманітних системах;

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

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

–  адаптація моделі до дослідження балансування навантаження в мережах, що самоорганізуються;

–  розробка власного алгоритму балансування навантаження.

В роботі вперше запропонована універсальна модель для системи, яка реалізує функції розподілення потоків. На базі моделі був створений програмний продукт, що дозволяє аналізувати та досліджувати системи балансування навантаження в новітніх стільникових мережах 4-го покоління та в центрах обробки даних, заснованих на кластерних мережах. Буде розроблено власний алгоритм балансування навантаження.

АНАЛІЗ ОБ’ЄКТА ДОСЛІДЖЕННЯ

Аналіз сучасних тенденцій розвитку телекомунікаційної сфери

Проведемо аналіз статистики надання телекомунікаційних послуг, та тенденцій їх розвитку в Україні [4], та у лідера впровадження сучасних телекомунікаційних технологій – Швеції [5]. Аналізуючи статистичні дані, доходимо висновку: ринок стаціонарного зв'язку зменшується [6], а мобільного (стільникового) зростає. Так само зростають темпи надання послуг Internet і широкосмугового доступу до цієї послуги. Ця тенденція підтверджується компанією МТС [7] і аналізом, що був проведений iKS-CONSTULTING [8].

Підтвердження цих тенденцій можна відзначити в статистиці зниження використання стаціонарного голосового зв'язку (зазначалося вище) та ефірного телебачення [9], а також в підвищенні попиту на послуги VoIP та зростанні відео-інтернет трафіку [10]. Зокрема в 2008 році частка прибутку VoIP в загальному прибутку послуг зв’язку в Росії не перевищувала 8 %, а за 2009 рік зросла майже вдвічі - до 15 %. Очікується, що наприкінці 2012 р. частка трафіку VoIP сягатиме 40% [11].

Звіт Morgan Stanley прогнозує взагалі у світі 103%-е зростання трафіку VoIP к 2014 р. – показник, який поступається лише темпам росту відео-трафіку. Важливу роль у цьому відіграла зростаюча популярність передачі даних в мобільних мережах за допомогою смартфонів. З лютого 2009 року по лютий 2010 року цей вид трафіку зріс на 193% [12].

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

Відзначимо новітні технології, які акцентовані на надання послуг широкосмугового доступу: мобільні мережі 4-го покоління (LTE [3,13-17], WiMAX [18,19]), технологію надання мультисервісних послуг IP/MPLS [2,20,21], маркетингову концепцію Triple Play [22], сервіси розподілених обчислюваних центрів обробки даних [23-25].

Усі системи застосовуються для надання послуг ШСД на різних ділянках телекомунікаційної мережі. Їх загальну взаємодію та взаємопроникнення можна відобразити схемою – рисунок 1. Розглянемо деякі з цих систем детальніше, відзначивши застосування в них балансування навантаження.

Рисунок 1 - Мережа Triple Play, що побудована на новітніх технологіях

Аналіз системи розподілу навантаження в центрах обробки даних

Вже зараз набули широкого поширення мультимедійні сайти, що надають можливості отримати одночасний доступ до будь-якого виду контенту: відео, текст, музика, графіка і т.д. Крім того, ці сайти є дуже великими та популярними, багато з них відвідують мільйони щодня [26]. Для реалізації такого сервісу необхідно мати величезний кластер обчислювальних систем, який зберігає інформацію та обробляє запити що надходять. Для оцінки навантаження, що надходить, наведемо дані компанії Twitter [27]:

–  близько 600 запитів в секунду;

–  в середньому система підтримує 200-300 з’єднань на секунду;

–  MySQL обробляє приблизно 2400 запитів в секунду;

–  в середньому відповідь на запит до бази даних складає 50-100 мілісекунд.

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

До статичних дисциплін відносять Random і Round Robbin. У Random сервер обирається випадковим чином за допомогою рівномірного розподілу. Дисципліна Round Robbin реалізує принцип циклічного перебору.

Для будь-якої динамічної дисципліни виникає питання вибору керуючого параметру. Як критерій ефективності зазвичай приймають два показники [23]:

–  час перебування заявки на сервері;

–  сповільнення (slowdown), у скільки раз уповільнюється обслуговування запиту через наявність черги.

Найбільш розповсюдженими динамічними дисциплінами є:

–  Least Loaded (LL) – вибір сервера за критерієм найменшого завантаження його ресурсів (процесора, пам'яті, диска, кількості черг повідомлень);

–  Least Connected (LC) – вибір сервера за критерієм найменшого числа поточних відкритих TCP/IP-з'єднань;

–  Fast Response (FR) – вибір сервера за критерієм самої швидкої відповіді на тестовий запит від розподільника навантаження;

–  Weighted Round Robbin (WRR) – при циклічному переборі кожному серверу передається декілька запитів, відповідно до ваги сервера, яка є пропорційною, наприклад, його поточному завантаженню [24];

–  Multi Class Round Robbin (MC-RR) - всі можливі запити розділені за очікуваним впливом на мережу, процесор і диск: з високим навантаженням на диск; з високим навантаженням на процесор; з високим навантаженням на диск та процесор. Запити першого класу характерні для систем Web-публікацій, інші для обробки Web-транзакцій і мультимедійних Web-додатків. Запити одного типу (класу) обслуговуються згідно дисципліни RR на визначених для цього типу запитів серверах. З невеликими модифікаціями метод MC-RR відомий також як CAP(Client-Aware Policy).

Універсальний підхід до використання динамічних дисциплін було реалізовано в IBM Network Dispatcher [24,25]. Автори запровадили поняття індексу завантаження Load Metrics Index (LMI) і розділили показники якості роботи системи на три класи.

–  Input – обчислюються локально в розподільнику. Наприклад, кількість з'єднань, встановлених із сервером за останні t одиниць часу.

–  Host – обчислюються на кожному сервері. Наприклад, завантаження сервера.

–  Forward – обчислюються шляхом мережевої взаємодії розподільника навантаження з сервером. Ці характеристики доставляють спеціальні скрипти-агенти. Наприклад, подача HTTP-запиту "GET /" і вимірювання часу відповіді. Далі, за вектором LMI для кожного сервера обчислюються значення функції WCF (Weight Computation Function), і вибирається сервер із найбільшим ії значенням.

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

Балансування навантаження в мережі LTE-SON за рахунок використання властивостей самоорганізації

Технологія LTE та WiMAX створені спеціально для надання на ділянці останньої милі мобільного каналу доступу до мережі Internet із рівнем швидкості порівняним зі стаціонарними каналами доступу [17]. Ці технології ґрунтуються на модуляції сигналу OFDM і мають дуже високу ефективність використання частотного ресурсу (5-10 біт/с/Гц). Але у самих системах закладений ще один спосіб підвищення ефективності використання ресурсів мережі – побудова мережі на засадах самоорганізації. Self Organization Network (SON) легко інтегрується в LTE завдяки існуючим інтерфейсам, модулям та протоколам керування мережею [13-16].

Існують три основні складові частини концепції SON, які критичні для створення мережі [3].

–  Cамоконфігурація – plug-and-play, автоматичне створення базовою станцією переліку сусідніх станцій (АNR – Automated Neighbour Relation), автоматичне призначення CellID та налаштування радіопараметрів: частоти, що використовується, контролю інтерференцій, потужності сигналу випромінювання та кута нахилу антени.

–  Cамооптимізація – автоматичне визначення параметрів базових станцій, які забезпечують найвищу можливу якість обслуговування абонентів (знаходження нових сусідніх станцій та видалення неактивних сусідів, координацію рівнів потужності для зменшення інтерференції між сусідніми базовими станціями, оптимізацію процесів хендоверу і конфігурації QoS).

–  Cамовідновлення, яке включає до себе автоматичне визначення відмов у роботі обладнання і відповідну реконфігурацію мережі у разі відмови будь-якої базової станції.

При розподіленні потужностей в стандартах 2G/3G кожна БС має фіксовану зону покриття. Однак абоненти розподілені по території нерівномірно та постійно пересуваються по площі - через це навантаження на БС також розподілено нерівномірно. Деякі сучасні системи дозволяють частково перерозподілити ресурси за допомогою так званих «дихаючих стільників», але таке рішення також не є досконалим, тому що не враховує режим роботи сусідніх стільників. Тому найбільш вдалим і є рішення на базі концепції мереж, що самоорганізуються.

Завдяки обміну інформацією між сусідніми БС – кожна сусідня станція може узгодити з сусідами потужність випромінювання свого приймально-передавального пристрою, таким чином змінити свою зону покриття. Це дозволить плавно перерозподілити навантаження (потоки) між усіма ділянками мережі. Так само БС передають повідомлення центральному ядру управління, яке може керувати змінами відразу на декількох ділянках й узгодити їх між собою. Саме така гібридна схема взаємодії між базовими станціями і отримала розвиток в концепції LTE-SON.

Тобто в мережі LTE-SON можна виділити декілька головних елементів: головне ядро, яке керує сегментом мережі, базові та мобільні станції. Також важливими параметрами є пропускна спроможність БС та пропускна спроможність каналу, що потребує кожна МС. Змінення потужності БС призводить до перерозподілу МС між БС з урахуванням критерію рівномірності завантаження.

РОЗРОБКА УНІВЕРСАЛЬНОЇ МОДЕЛІ

Розробка аналітичної універсальної моделі для системи з розподільником потоків

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

Розгляньмо систему розподілу потоків LTE-SON. Головним ресурсом, що перерозподіляється, є загальна пропускна спроможність кожної БС. Цей ресурс перерозподіляється, виходячи з існуючих тарифних планів, вимог до якості обслуговування, місцеположення МС та інше. Приведемо структурну схему, що відображує вище сказане – рисунок 2.

У ЦОД використовується багато різних алгоритмів розподілення, але відтворимо узагальнену структурну схему. Під час роботи системи перерозподіляються ресурси процесора та пам’яті кожного серверу, що входить до кластеру. Кожен запит, що належить вхідному потоку, має свій тип, ціль, розмір, час обслуговування – завдяки чому несе якусь «вагу» для ресурсів кластера на свою обробку. Крім того, кожен сервер по своїм можливостям (швидкість відповіді, швидкість обслуговування конкретного типу запиту, багатопоточність та інше) є особливою одиницею. Розподільник навантаження у цьому випадку керує потоками, виходячи із вільних ресурсів у кластеру – рисунок 3.

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

Рисунок 2 - Структурна схема розподілення потоків в LTE-SON

Рисунок 3 - Структурна схема розподілення потоків в ЦОД

Розробка програмної універсальної моделі для системи з розподільником потоків

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

Найтиповішим елементом в усіх структурах є потік чогось: запитів, пакетів, миттєвих пропускних спроможностей. Тож, найпершим виділено об’єкт – «Потік». Він являє з себе багатовимірний масив. Де в стовпці перше значення є деяким унікальним ключем (відлік часу для запитів, UID для мобільних станцій). А інші значення – набір параметрів, що характеризують конкретний елемент (тип запиту, адреса одержувача, необхідна мінімальна та бажана пропускна спроможність та ін.). Також в цьому об’єкті актуально реалізувати ще ряд методів: визначення параметра Херста, визначення пачечности потоку, визначення його статистичних характеристик та ін.

Так само у всіх структурах є «Робочий елемент». Це власне ті елементи, що вносять у систему поняття обмеженості ресурсів: базові станції, сервер у кластері, смуга пропускної спроможності каналу в IP/MPLS. Цей об'єкт дуже специфічний для кожної задачі. Але його можна описати в глобальному масштабі через такі параметри: робочий ресурс (потужність процесора, виділений діапазон частот і потужність випромінювання, максимально можлива пропускна спроможність), стан (усталені робочі параметри), зміна стану (нове завдання, поломка) та ступінь завантаження (процесора, частотного ресурсу, каналу зв'язку та ін.).

Так як у нас завжди є група «робочих елементів», що працюють спільно, то необхідно створити інтегруючий об'єкт - «Система», який завжди буде описувати роботу елементів у сукупності. Його параметрами будуть: масив «робочих елементів», стан системи, зміна стану системи, загальносистемні та середні показники завантаження.

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

Для кожного випадку потік потрібно задавати згідно своїх правил. Наприклад, для LTE/SON це буде набір усіх мобільних станцій у сегменті мережі та пропускні спроможності, які вони вимагатимуть, а для WEB-проекту – послідовність запитів та їх тип за певний проміжок часу. Тому необхідно створити об'єкт - «Генератор початкового потоку». Він повинен зчитувати необхідний потік із заданого джерела, або сам його генерувати за наданими принципами.

Найважливішим об'єктом-параметром є об'єкт «Керування», який вирішує задачі розподілу вхідного (вихідного) потоку в «Розподільник» між вихідними (вхідними) потоками. Враховуючи, що керування в багатьох алгоритмах не можливо без методів оптимізації – виділяється черговий об'єкт-параметр «Оптимізація». Методи оптимізації можуть накопичувати інформацію минулих рішень, початкових даних й уточнювати прийняті рішення виходячи з цього обсягу інформації. За дану функцію відповідає об'єкт-параметр - «Пам'ять». Можливості застосування прогностичного контролю диктують появу об'єкта-параметра «Прогноз». Всі ці об'єкти описують загальні принципи взаємодії моделі з задачами прогнозу, оптимізації та ін. А реальні методи прогнозу, оптимізації та ін. задаються в успадкованих об'єктах, що дозволяє легко змінювати вживаний метод, не змінюючи структуру всієї моделі.

Дана універсальна програмна модель була реалізована програмними засобами динамічної об'єктно-орієнтованої мови програмування Ruby. Загальний вигляд програмної моделі представлений нижче за допомогою UML-діаграми – рисунок 4.

Рисунок 4 - UML-діаграма універсальної програмної моделі

ВИСНОВКИ

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

Була розроблена та реалізована програмна модель (framework) для дослідження задач розподілу потоків. Дана модель дає спільний інструментарій для створення конкретних моделей дослідження, полегшуючи:

–  використання однакових алгоритмів та структурних одиниць у різних методах і системах;

–  опис взаємодії між елементами;

–  акцентування уваги на реалізації математичного апарату, а не програмних реалізацій.

Далі, в процесі виконання магістерської роботи, буде розглянута адаптація моделі до вже зазначених систем розподілу потоків. На базі цих адаптувань будуть створені програми для дослідження поставлених нижче задач. Перша задача (статична) – дослідження перерозподілу навантаження мережі LTE-SON у порівнянні з LTE. Друга задача (динамічна) – оцінка ефективності різних алгоритмів балансування навантаження в кластерних мережах. На підставах цих досліджень буде виявлені плюси та мінуси різних алгоритмів, що дозволить врахувати недоліки інших алгоритмів при розробці власного алгоритму балансування навантаження.

ПРИМІТКА:При написанні даного автореферату кваліфікаційна робота магістра ще не завершена. Дата остаточного завершення роботи: 1 грудня 2011р. Повний текст роботи та матеріали по темі роботи можуть бути отримані у автора або його наукового керівника після зазначеної дати.