Вступ
Механізми запобігання перевантаженню і різні політики відкидання пакетів призначені на основі аналізу мережного трафіка відслідковувати вузькі місця в мережі і не допускати виникнення на цих ділянках перевантажень. В умовах перевантаження ці механізми забезпечують тільки пільгову обробку пріоритетного трафіка. Але на практиці часто виникає ситуація, що пакет, який тільки-но надійшов, необхідно поставити у чергу, що вже досягла свого максимального розміру. У результаті деякі пакети слід відкинути. У найпростішому випадку застосовується політика "відкидання хвоста" (tail drop), відповідно до якої відкидаються пакети, які тільки-но надійшли.
Однак політика "відкидання хвоста" призводить до виникнення ефекту глобальної синхронізації – одночасного (синхронного) перезапуску алгоритмів повільного старту множини ТСР-джерел. Крім небажаної зміни розмірів черги, цей ефект здатний також призвести до зростання джитера, затримки пакетів трафіка і зниження продуктивності всієї мережі. Більш ефективними є механізми превентивного управління перевантаженнями, до яких належать алгоритми RED і його модифікації WRED і DWRED.
1. Алгоритм довільного раннього виявлення RED
Алгоритм довільного раннього виявлення (Random Early Detection –RED) є алгоритмом активного управління чергою і має істотні переваги в порівнянні з традиційним механізмом "відкидання хвоста". Механізм RED використовує превентивний підхід до запобігання перевантаженню мережі та замість очікування фактичного переповнення черги, як при "відкиданні хвоста", RED починає відкидати пакети з ненульовою імовірністю, коли середній розмір черги перевищить певне мінімальне граничне значення. Імовірнісний підхід до відкидання пакетів дозволяє бути впевненими в тому, що механізм RED відкине пакети усього лише декількох довільно обраних потоків, тим самим дозволяючи уникнути ефекту глобальної синхронізації.
Возможно вы искали - Курсовая работа: Интерфейс и основные принципы работы в информационной системе "MS Publisher"
Механізм раннього довільного виявлення RED націлений на:
• мінімізацію джитера затримки пакетів шляхом контролю за середнім розміром черги;
• запобігання ефекту глобальної синхронізації ТСР-трафіка;
• забезпечення неупередженого обслуговування трафіка, що характеризується короткочасними сплесками;
• строге обмеження максимального середнього розміру черги (шляхом уведення максимального порога).
Похожий материал - Дипломная работа: Информационные технологии в строительстве
Головна мета механізму RED полягає в мінімізації середнього розміру черги, а виходить, і результуючої затримки пакетів трафіка.
У рамках механізму RED уводиться ряд параметрів:
• 
– мінімальне граничне значення розміру черги, при перевищенні якого чергою починається процес відкидання пакетів. Найменше значення, що рекомендується, 
пакетів;
• 
– максимальне граничне значення, при перевищенні якого відкидаються всі пакети, які тільки-но надійшли. Значення, що рекомендується, 
;
• 
– це експонентний ваговий коефіцієнт, який бере участь в обчисленні середнього розміру черги 
і визначає відносний внесок попереднього середнього 
і поточного розміру черги 
(миттєвий розмір) у новий середній розмір черги, що обчислюється за формулою
Очень интересно - Дипломная работа: Информационные технологии во внешнеэкономической деятельности
, (1)
де рекомендоване значення =9;
• 
– знаменник граничної імовірності (mark probability denominator), який визначає імовірність відкидання пакетів при досягненні середнім розміром черги максимального граничного значення . У загальному випадку
, (2)
де рекомендоване значення =10.
Вам будет интересно - Реферат: Исследование методов вычисления определенных интегралов
При реалізації алгоритму RED у залежності від співвідношень середньої довжини черги і введених граничних значень можливі три ситуації (табл. 1). На рис. 1 наведений характерний для механізму RED графік залежності імовірності відкидання пакетів 
від середнього розміру черги .
Таблиця 1 – Дії механізму RED
| Умова | Дія |
| < | Пакети не відкидаються (=0). |
 << | Частина пакетів відкидається. Імовірність відкидання  прямо пропорційна збільшенню середнього розміру черги від мінімального до максимального граничного значення ( змінюється від 0 до  ). |
| > | Усі нові пакети відкидаються (=1). |
Рисунок 1 – Графік залежності імовірності відкидання пакетів 
( ) для механізму RED
Якщо ж середній розмір черги досить невеликий і знаходиться нижче мінімального граничного значення, механізм RED не здатний забезпечити істотних переваги в порівнянні з традиційними механізмами управління чергами. З іншого боку, при затяжному періоді перевантаження мережі поведінка механізму RED, незважаючи на довгу чергу і високе максимальне граничне значення, аналогічна поведінці класичного механізму "відкидання хвоста". Отже, основне призначення механізму RED полягає в згладжуванні сплесків трафіка і попередженні тривалого перевантаження мережі за допомогою повідомлення джерел трафіка про необхідність зниження інтенсивності передачі інформації. Якщо джерела виявлять здатність до взаємодії й одночасно зменшать інтенсивність переданого трафіка, це допоможе запобігти перевантаженню мережі. У іншому випадку середній розмір черги досить скоро досягне максимального граничного значення, що призведе до відкидання всіх пакетів, які надходять.
Похожий материал - Курсовая работа: Исследование точности численного дифференцирования
Фактично механізм довільного раннього виявлення RED базується на обчисленні середнього розміру черги , що визначає припустимий рівень сплеску трафіку в черзі, та обчисленні імовірності відкидання пакетів , яка визначає частоту відкидання пакетів для заданого середнього розміру черги. Зверніть увагу, що при визначенні імовірності відкидання пакетів механізм RED обчислює не поточний, а експонентно зважений середній розмір черги (1). Використання механізмом RED середнього розміру черги обумовлено прагненням реагувати тільки на довготривале перевантаження мережі, а не на короткочасні сплески трафіка.
Під час розрахунку досить важливим є правильний вибір вагового коефіцієнта . Збільшення експонентного вагового коефіцієнта призведе до домінування попереднього середнього розміру черги над її поточним розміром в аспекті обчислення нового середнього розміру черги . Навпаки, зменшення експонентного вагового коефіцієнта приведе до зростання значущості поточного розміру черги при обчисленні її нового середнього розміру.
Нижче наведена формула для розрахунку експонентного вагового коефіцієнта:
, (3)