Спосіб нейро-нечіткого управління пакетною чергою вихідного порту маршрутизатора телекомунікаційної мережі

Реферат: Спосіб нейро-нечіткого управління пакетною чергою вихідного порту маршрутизатора телекомунікаційної мережі полягає у тому, що протягом кожної ділянки часу встановленої тривалості здійснюється підрахунок кількості пакетів, що надходять до вихідного порту маршрутизатора для подальшого передавання, підраховані значення кількості пакетів, що надійшли до вихідного порту маршрутизатора протягом чотирьох попередніх ділянок часу, як вхідні величини подаються до двох нейро-нечітких систем, одна з яких здійснює прогнозування кількості пакетів, що будуть втрачені протягом наступної ділянки часу у наслідок переповнення пакетної черги вихідного порту маршрутизатора, а друга - прогнозування кількості пакетів, що надійдуть до вихідного порту маршрутизатора протягом наступної ділянки часу, якщо прогнозована кількість пакетів, що надійдуть до вихідного порту маршрутизатора протягом наступної ділянки часу, виявиться меншою, ніж прогнозована кількість пакетів, втрачених протягом наступної ділянки часу у наслідок переповнення пакетної черги, то кожний пакет, що надходитиме до вихідного порту маршрутизатора протягом поточної ділянки часу, буде відкинуто, в іншому випадку пакет буде відкинуто протягом поточної ділянки часу, якщо результат ділення значення прогнозованої кількості пакетів, втрачених протягом наступної ділянки часу у наслідок переповнення пакетної черги, на значення прогнозованої кількості пакетів, що надійдуть до вихідного порту маршрутизатора протягом наступної ділянки часу, буде не нижчим, ніж псевдовипадкове число з рівномірним розподілом в межах значень від нуля до одиниці. Рішення про відкидання пакетів, що надходять до вихідного порту маршрутизатора протягом поточної ділянки часу, здійснюється на основі нейро-нечіткого прогнозування кількості пакетів, що будуть втрачені протягом наступної ділянки часу у наслідок переповнення пакетної черги вихідного порту маршрутизатора, та кількості пакетів, що надійдуть до вихідного порту маршрутизатора протягом наступної ділянки часу. UA 72989 U (12) UA 72989 U UA 72989 U 5 Спосіб, що заявляється, належить до області активного управління пакетними чергами в маршрутизаторах телекомунікаційних мереж. Наявні способи управління пакетними чергами в телекомунікаційних мережах призначені для боротьби з мережними перевантаженнями. Згідно зі способом пасивного управління чергами Tail Drop [1] усі пакети, що надходять до вихідного порту маршрутизатора, відкидаються, якщо довжина відповідної пакетної черги q досягає граничного значення B , тобто наявне перевантаження у відповідному напрямку передавання даних телекомунікаційної мережі. Згідно зі способом Tail Drop функція імовірності відкидання пакетів має вигляд: 0, q  B, Pb q   , 1 q  B. 10 15 20 (1) Графік функції Pb q при пасивному управлінні пакетною чергою зображено на Фіг. 1. Цей спосіб має такі недоліки. По перше, в умовах перевантаження пакети, знаходячись у довгій черзі, тривалий час очікують передавання. У наслідок цього на приймальному боці спостерігаються великі значення середньої затримки пакетів. По-друге, через різке коливання довжини пакетної черги має місце значна дисперсія затримки пакетів (джиттер). По-третє, реалізація Tail Drop часто викликає несправедливий захват черги пакетами лише одного або декількох потоків. У наслідок цього інші потоки передаються з великим відсотком втрачених пакетів. У цьому випадку якість обслуговування частини користувачів у мережі значно знижується. Відомий більш ефективний спосіб управління пакетними чергами - спосіб випадкового завчасного виявлення перевантаження (Random Early Detection, RED) [2]. Цей спосіб є найбільш близьким до способу, що заявляється, належить до способів активного управління чергами пакетів вихідного порту маршрутизатора телекомунікаційної мережі та включає обчислення середнього розміру пакетної черги q за формулою (1),  P q 25 імовірності відкидання пакета b за формулою (2) та прийняття рішення про відкидання пакета, що надходить до вихідного порту маршрутизатора, якщо виконується умова (3). Зазначені вище формули та умова мають такий вигляд: q  1  w qn  wq , (1) qn 30 де - попереднє значення середнього розміру пакетної черги вихідного порту маршрутизатора; q - значення поточної довжини черги у момент надходження пакета до вихідного порту маршрутизатора; w - ваговий коефіцієнт, що приймає фіксоване значення в межах 0  w  1 , рекомендоване значення w  0,002 ;    q  Tmin Pmax , Tmin  q  Tmax ;   Tmax  Tmin  Pb q   0, q  Tmin ;  1, q  Tmax .    (2) Tmax  CR C  де ( пакета в черзі); 35 - значення пропускної здатності лінії; R - величина допустимої затримки Tmin  Tmax 3 ; Pmax - імовірність відкидання пакета при q  Tmax , рекомендоване значення Pmax  0,1 ; N P Pb , (3) де N - кількість не відкинутих пакетів, що були відправлені через вихідний порт маршрутизатору з моменту останнього відкинутого. P q 40 Графік функції b при активному управлінні пакетною чергою, що здійснюється згідно зі способом RED, ілюструється Фіг. 2. Використання способу RED дозволяє запобігти перевантаженню мережі і, в порівнянні з Tail Drop, отримати виграш в середній затримці пакетів. Недоліком цього відомого способу є те, що при його застосуванні величина втрат пакетів зростає у порівнянні з реалізацією пасивного управління пакетними чергами. 1 UA 72989 U В основу корисної моделі поставлена задача створення способу управління пакетною чергою вихідного порту маршрутизатора, при здійсненні якого в телекомунікаційній мережі буде знижено втрати пакетів та їхню середню затримку у маршрутизаторах. Поставлена задача вирішується тим, що протягом кожної ділянки часу i встановленої 5 тривалості здійснюється підрахунок кількості пакетів Ki , що надходять до вихідного порту маршрутизатора для подальшого передавання, підраховані значення кількості пакетів Ka, Kb, Kc та K d , що надійшли до вихідного порту маршрутизатора протягом чотирьох попередніх ділянок часу (див. Фіг. 3), як вхідні величини подаються до двох нейро-нечітких систем, одна з яких ~ N 10 здійснює прогнозування значення f - кількості пакетів, що будуть втрачені протягом наступної ділянки часу у наслідок переповнення пакетної черги вихідного порту маршрутизатора, а друга ~ K здійснює прогнозування значення e - кількості пакетів, що надійдуть до вихідного порту маршрутизатора протягом поточної ділянки часу, потім обчислюється імовірність завчасного відкидання пакетів протягом поточної ділянки часу за виразом: ~ ~  1 K N ; , f ~ e pe   Nf ~ ~  ~ , K e  Nf ; Ke (4) 15 пакет, що надійшов до вихідного порту маршрутизатора протягом поточної ділянки часу буде відкинуто, якщо виконується умова: pe  P , (5) де P - псевдовипадкове число з рівномірним розподілом, 0  P  1 . 20 Технічний результат, який може бути отриманий при використанні корисної моделі, полягає у зниженні втрат пакетів та зменшенні їхньої середньої затримки у маршрутизаторах телекомунікаційної мережі. Реалізацію корисної моделі розглянуто на прикладі, в якому поточні значення 25 30 Ki відповідають виборці, що ілюструється Фіг. 4, а поточні значення величини Ni - кількості пакетів, що були втрачені протягом ділянки часу номер i при пасивному управлінні пакетною чергою вихідного порту маршрутизатора, зображено на Фіг. 5. З метою зменшення обчислювальної складності способу, що заявляється, вибрано найпростіші параметри нейро-нечітких систем: алгоритм нечіткого виводу - Сугено 0-го порядку [3], кількість функцій приналежності для кожної вхідної величини - 2, форма функцій приналежності для кожної вхідної величини - трикутна, алгоритм навчання нейронів зворотного розповсюдження помилки [4]. Для налаштування кожної нейро-нечіткої системи використано 12 циклів навчання. ~ N ~ K f та значення e Для налаштування ваг нейронів систем прогнозування значення сформовано дані для навчання у вигляді матриць (6) та (7) відповідно, що містять по 95 рядків кожна: K1 K2 35 K2 K3 K3 K4 K4 K5 N6 N7 . K 95 . K 96 . K 97 . K 98 . N100 K1 K2 K2 K3 K3 K4 K4 K5 K5 K6 . K 95 . K 96 . K 97 . K 98 . K 99 , (6) . (7) В результаті налаштування нейро-нечіткої системи прогнозування значення вирази для функцій приналежності вхідних величин: 1, якщо K a  0,008;    9,966  K a 1K a    , якщо 0,008  K a  9,966;  9,958 0, якщо K a  9,966;   (8) 2 ~ Nf одержано UA 72989 U 0, якщо K a  0,001 ;   K a  0,001   2 K a    , якщо 0,001  K a  9,992;  9,991 1, якщо K a  9,992;   (9) 1, якщо K b  2,045;   9,867  K b  1K b    , якщо 2,045  K b  9,867;  7,822 0, якщо K b  9,867;   (10) 0, якщо K b  2,131 ;   K b  2,131   2 K b    , якщо 2,131  K b  10,04;  7,909 1, якщо K b  10,04;   (11) 1, якщо K c  2,013;   9,948  K c  1K c    , якщо 2,013  K c  9,948;  7,935 0, якщо K c  9,948;   (12) 5 0, якщо K c  2,055;   K c  2,055   2 K c    , якщо 2,055  K c  10,01 ;  7,955 1, якщо K c  10,01 ;   1, якщо K d  1,97;   9,676  K d  1K d    , якщо 1,97  K d  9,676;  7,706 0, якщо K d  9,676;   (14) 0, якщо K d  2,081 ;    K c  2,081  2 K d    , якщо 2,081  K d  9,971 ;  7,89 1, якщо K d  9,971 ;   а також значення (13) (15) індивідуальних висновків Y1  0,999, Y2  0,776, Y3  1714, Y4  2,897, Y5  3,85, Y6  0,39, Y7  0,669, Y8  4,027, , 10 15 20 Y9  2,912, Y10  5,769, Y11  1233, Y12  8,498, Y13  0,178, Y14  5,771 Y15  1132, Y16  0,321. , , , ~ Nf Структура нейро-нечіткої системи прогнозування величини ілюструється Фіг. 6. Функціонування цієї системи ґрунтується на використанні бази нечітких правил: Якщо K Якщо K Якщо K Якщо K Якщо K Якщо K Якщо K Якщо K Якщо K Якщо K Якщо K Якщо K Якщо K a a a a a a a a a a a a a      та K    та K    та K    та K    та K    та K    та K    та K    та K    та K    та K    та K      та K    та K    та K    та K    та K    та K    та K    та K    та K    та K    та K    та K     , (16) ~    та K    то N  Y  , , (17) ~    та K    то N  Y  , , (18) ~    та K    то N  Y  , , (19) ~    та K    то N  Y  , , (20) ~    та K    то N  Y  , , (21) ~    та K    то N  Y  , , (22) ~    та K    то N  Y  , , (23) ~    та K    то N  Y  , , (24) ~    та K    то N  Y  , , (25) ~    та K    то N  Y  , , (26) ~    та K    то N  Y  , , (27) ~ та K   , то N  Y , (28)  ~  1 та Kb  1 та K c  1 та K d  1 , то Nf  Y1 1 2 3 4 1 1 1 1 b b 1 1 b 1 1 b 1 1 b 1 1 1 1 2 1 2 1 b b b b 2 1 b 2 1 b 2 1 b 1 2 1 2 c c 1 2 c 2 2 c 2 2 c 2 2 2 2 1 2 1 2 c c c c 1 2 c 1 2 c 2 2 c 1 3 2 3 d 2 4 f 2 d 1 4 f 3 2 3 d 2 4 f 4 1 3 d 1 4 f 5 1 3 d 2 4 f 6 d 1 4 f 7 d 2 4 f 8 d 1 4 f 9 2 3 2 3 1 3 1 3 d 2 4 f 10 2 3 d 1 4 f 11 2 3 d 2 4 f 12 1 3 d 1 4 f 13 3 правил: UA 72989 U Якщо K Якщо K Якщо K де 5 Kb A 1 a a a      та K    та K      та K    та K      та K    та K   ~    то N , ~    то N , ~ 2  1 та Kb  2 та K c  1 та K d  2 , то Nf  Y14 2 3 4 2 1 b 2 1 b 2 2 c 2 2 c 2 3 d 2 3 d 1 4 f  Y15 2 4 f  Y16   , (29) , (30) , (31) B - терм номер A вхідної величини K a , A  1,2 ; 2 - терм номер B вхідної величини     C D , B  1,2 ; 3 - терм номер C вхідної величини K c , C  1,2 ; 4 - терм номер D вхідної     величини K d , D  1,2 ; Yr - індивідуальний висновок нечіткого правила номер r  1,16 . Нейро-нечітка система прогнозування величини ~ Nf складається з чотирьох шарів. Перший шар виконує процедуру фазифікації, яка полягає у тому, що для конкретних значень та 10 15 K d           обчислюються       K , K , K a b c величини         1 K  , 2 K ,  ,  A max K  , 1 K , 2 K ,  , B max K , 1 K  , 2 K  ,  , C max K  , 1 K , 2 K  ,  , D max K a a a b b b c c c d d d значення функцій приналежності вхідних величин відповідним термам. Другим шаром нейро-нечіткої системи здійснюється процедура агрегування, в процесі якої визначаються ступені істинності умов кожного правила при конкретних значеннях вхідних змінних: G r        . (32)   A K  B K  C K  D K a b c d За допомогою третього шару обчислюється сума та зважена сума вихідних сигналів другого шару. При цьому виконується активізація, суть якої в алгоритмі Сугено 0-го порядку полягає у Y , Y , , Y , , Y 20 r  визначенні індивідуальних висновків правил: 1 2 . Четвертий шар реалізує операцію ділення вихідних сигналів третього шару, тобто визначає результат процедури дефазифікації, в результаті якої методом центру тяжіння для одноточкових множин визначається чітке значення вихідної змінної за таким виразом:  ~ K  e YG r r r 1  G r r 1 . (33) В результаті налаштування нейро-нечіткої системи прогнозування значення вирази для функцій приналежності вхідних величин: 25 1, якщо K a  0,017;   9,918  K a  1K a    , якщо 0,017  K a  9,918;  9,901 0, якщо K a  9,918;   (34) 0, якщо K a  0,029;   K  0,029  2 K a    a , якщо 0,029  K a  10,02;  9,991 1, якщо K a  10,02;   (35) 1, якщо K b  2,06;   9,904  K b  1K b    , якщо 2,06  K b  9,904;  7,844 0, якщо K b  9,904;   (36) 0, якщо K b  2,149;   K b  2,149  2 K b    , якщо 2,149  K b  10,06;  7,911 1, якщо K b  10,06;   (37) 1, якщо K c  2,063;    9,793  K c 1K c    , якщо 2,063  K c  9,793;  7,73 0, якщо K c  9,793;   (38) 4 ~ Ke одержано UA 72989 U 0, якщо K c  2,17;   K c  2,17  2 K c    , якщо 2,17  K c  10,06;  7,89 1, якщо K c  10,06;   (39) 1, якщо K d  1,951 ;   9,833  K d  1K d    , якщо 1,951  K d  9,833;  7,882 0, якщо K d  9,833;   (40) 0, якщо K d  2,006;   K c  2,006  2 K d    , якщо 2,006  K d  9,951 ;  7,945 1, якщо K d  9,951 ;   (41) а також значення індивідуальних висновків правил: Y1  8,452, Y2  6, Y3  1284, Y4  18,96, Y5  25,31 Y6  9,983, Y7  8,011 Y8  4,957, , , , Y9  4,676, Y10  6,303, Y11  0,447, Y12  24,32, Y13  2,996, Y14  2138, Y15  4,183, Y16  4,737. , ~ Ke 5 Нейро-нечітка система прогнозування значення за побудовою та функціонуванням є схожою з нейро-нечіткою системою прогнозування значення ~ Nf , за винятком того, що вихідним сигналом останнього шару нейронів у першому випадку є величина ~ Nf 10 15 20 25 30 35 40 45 ~ Ke , а у другому - величина . Побудовані нейро-нечіткі системи використано для управління пакетною чергою вихідного порту маршрутизатора. Фіг. 7 ілюструє фрагмент процесу надходження пакетів у вихідний порт маршрутизатора. Кожен пакет, що надходить, зображений у вигляді короткого прямокутного імпульсу, амплітуда якого k П відповідає порядковому номеру цього пакета. Значення і відповідають номерам еквідистантних ділянок часу, на які розбивається аналізований процес. Динаміка зміни поточної довжини пакетної черги Q вихідного порту маршрутизатора при реалізації способу Tail Drop представлена на Фіг. 8. Максимальний розмір вказаної черги обмежений бітовою довжиною шістнадцяти пакетів. При пасивному управлінні пакетною чергою втрати пакетів спостерігаються на ділянках з номерами 6, 7 і 8 (див. Фіг. 9), на яких Q=16. Кількість відкинутих пакетів дорівнює 8. Номери відкинутих пакетів відповідають значенням k 0 . В зазначеному прикладі при використанні способу Tail Drop значення середньої затримки пакетів у черзі вихідного порту маршрутизатора дорівнює t1=43,62 мс. Динаміку зміни поточної довжини пакетної черги Q вихідного порту маршрутизатора та номери відкинутих пакетів при використанні способу RED представлено на Фіг. 10 та Фіг. 11 відповідно. В цьому випадку кількість відкинутих пакетів дорівнює 9, а значення середньої затримки пакетів у черзі вихідного порту маршрутизатора дорівнює t2=41,86 мс. Динаміку зміни поточної довжини пакетної черги Q вихідного порту маршрутизатора та номери відкинутих пакетів при використанні способу, що заявляється, представлено на Фіг. 12 та Фіг. 13 відповідно. В цьому випадку при використанні способу, що заявляється, кількість відкинутих пакетів дорівнює 8, а значення середньої затримки пакетів у черзі вихідного порту маршрутизатора дорівнює t3=39,97 мс. В результаті досліджень встановлено, що використання способу, що заявляється, забезпечує зниження втрат пакетів на 5 % - 12 % та скорочення середньої затримки пакетів у черзі вихідного порту маршрутизатора на 4 % - 10 % у порівнянні з використанням відомого способу. Таким чином, спосіб, що заявляється, дозволяє знизити втрати пакетів та зменшити їхню середню затримку у маршрутизаторах телекомунікаційної мережі. Джерела інформації: 1. Recommendations on Queue Management and Congestion Avoidance in the Internet/Braden В., Clark D., Cmwcrofi J., Davie В., Peering S., Estrin D, Floyd S., Jacobson V., Minshall C, Partridge C, Peterson L, Ramakrishnan K., Shenker S., Wroclawski J., Zhang L., April 1998. 2. Floyd S., Jacobson V. Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on networking 1993 - 1 (4), p. 397-413. 3. Takagi Т., Sugeno M. Fuzzy Identification of Systems and Its Applications to Modeling and Control // IEEE Transactions on Systems, Man and Cybernetics. - 1985. - Vol. 15, N. 1. - pp. 116-132. 5 UA 72989 U 4. Rumelhart D. E., Hilton G. E., Williams R. J. Learning Internal Representations by Error Propagation // In Parallel Distributed Processing, t. 1. - Cambridge: M.I.T. Press, 1986. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 5 10 15 20 25 Спосіб нейро-нечіткого управління пакетною чергою вихідного порту маршрутизатора телекомунікаційної мережі полягає у тому, що протягом кожної ділянки часу встановленої тривалості здійснюється підрахунок кількості пакетів, що надходять до вихідного порту маршрутизатора для подальшого передавання, підраховані значення кількості пакетів, що надійшли до вихідного порту маршрутизатора протягом чотирьох попередніх ділянок часу, як вхідні величини подаються до двох нейро-нечітких систем, одна з яких здійснює прогнозування кількості пакетів, що будуть втрачені протягом наступної ділянки часу у наслідок переповнення пакетної черги вихідного порту маршрутизатора, а друга - прогнозування кількості пакетів, що надійдуть до вихідного порту маршрутизатора протягом наступної ділянки часу, якщо прогнозована кількість пакетів, що надійдуть до вихідного порту маршрутизатора протягом наступної ділянки часу, виявиться меншою, ніж прогнозована кількість пакетів, втрачених протягом наступної ділянки часу у наслідок переповнення пакетної черги, то кожний пакет, що надходитиме до вихідного порту маршрутизатора протягом поточної ділянки часу, буде відкинуто, в іншому випадку пакет буде відкинуто протягом поточної ділянки часу, якщо результат ділення значення прогнозованої кількості пакетів, втрачених протягом наступної ділянки часу у наслідок переповнення пакетної черги, на значення прогнозованої кількості пакетів, що надійдуть до вихідного порту маршрутизатора протягом наступної ділянки часу, буде не нижчим, ніж псевдовипадкове число з рівномірним розподілом в межах значень від нуля до одиниці, який відрізняється тим, що рішення про відкидання пакетів, що надходять до вихідного порту маршрутизатора протягом поточної ділянки часу, здійснюється на основі нейронечіткого прогнозування кількості пакетів, що будуть втрачені протягом наступної ділянки часу у наслідок переповнення пакетної черги вихідного порту маршрутизатора, та кількості пакетів, що надійдуть до вихідного порту маршрутизатора протягом наступної ділянки часу. 6 UA 72989 U 7 UA 72989 U 8 UA 72989 U Комп’ютерна верстка Д. Шеверун Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 9