Ключові положення

Алгоритм RED представляє собою механізм управління трафіком, розроблений спільнотою Internet для запобігання перевантажень на магістральних мережах. Даний механізм документований IETF (Internet Engineering Task Force) і володіє суттєвими перевагами по зрівнянню із традиційним механізмом “відкидання “хвоста”.

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

Рисунок 3.1 – Трафік до і після застосування алгоритму RED

Основні цілі механізму RED:

-Запобігання перевантажень.

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

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

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

-Запобігання ефекту "глобальної синхронізації" трафіку.

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

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

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

- Мінімізація затримки пакетів на вузлі (маршрутизаторі) шляхом контролю за середнім розміром черги.

Використання алгоритму вкрай не бажано при присутності UDP-трафіку, так як у зв'язку з нерозбірливістю алгоритму при видаленні пакетів з черги і принципом роботи UDP-протоколу, дані можуть не дійти до одержувача.

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

Алгоритм обчислення ймовірності відкидання пакетів. Визначає ймовірність (частоту) відкидання пакетів для заданого середнього розміру черги.

Алгоритм обчислення середнього розміру черги. Визначає допустимий рівень сплеску трафіку в черзі.

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

(3.1)

де – середній розмір черги;

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

K – знаменник граничної імовірності, що визначає частину пакетів, що відкидаються при досягненні середнім розміром черги максимального порогового значення.

Рисунок 3.2 – Залежність ймовірності відкидання пакетів від розміру черги

Відповідно до принципу роботи механізму RED, ймовірність відкидання пакетів зростає прямо пропорційно збільшенню середнього розміру черги в діапазоні від мінімального до максимального порогових значень (Рисунок 3.2).

Ймовірність відкидання пакетів залежить не тільки від розміру черги, а й від значення K (знаменник граничної імовірності), графічне зображення даної залежності представлене на рисунку 3.3.

Рисунок 3.3 – Залежність ймовірності відкидання пакетів від розміру черги при К=1 і К=2

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

(3.2)

де – попередній середній розмір черги;

– поточний розмір черги;

n − експоненціально ваговий коефіцієнт, що визначається користувачем.

Експоненціальний ваговий коефіцієнт n є ключовим параметром, який визначає відносний внесок попереднього середнього і поточного розміру черги в новий середній розмір черги. Його збільшення призводить до домінування попереднього середнього розміру черги над її поточним розміром в процесі обчислення нового середнього розміру черги. Навпаки ж, зменшення експоненціального вагового коефіцієнта призведе до зростання значимості [7].

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

Дата добавления: 2015-10-24