Книги по разным темам
Збрник наукових праць Харквського унверситету Повтряних Сил м. . Кожедуба, випуск 1(13), 2007 УДК 621.391 О.В. Лемешко1, О.А. Дробот1, Д.В. Симоненко2 1 Харквський унверситет Повтряних Сил м. вана Кожедуба, Харкв 2 Харквський нацональний унверситет радоелектронки, Харкв РЕЗУЛЬТАТИ ПОРВНЯЛЬНОГО АНАЛЗУ ПОТОКОВИХ МОДЕЛЕЙ МАРШРУТИЗАЦп В ТЕЛЕКОМУНКАЦЙНИХ МЕРЕЖАХ Наведено результати порвняльного аналзу потокових моделей маршрутизац з метриками рзних мережних протоколв за часовими та швидксними показниками якост обслуговування. телекомункацйна мережа, математична модель, багатошляхова маршрутизаця, яксть обслуговування, середня затримка, трафк тому що в загальному випадку розрахувати шуканий Вступ маршрут (множину маршрутв) можна деклькома Постановка проблеми в загальному вигляд.
способами. Для розвТязання сформульованих таким Незважаючи на широке поширення графових (графочином оптимзацйних задач можуть використатися комбнаторних) моделей маршрутизац [1, 2], як рзн засоби: для графових моделей - комбнаторн покладено в основу бльшост снуючих протоколв - алгоритми Дйкстри (OSPF, S-S, PNN), БеллманаRP (Routng nternet Protocol), GRP (nteror Форда (RP, GRP, EGRP), Флойда-Уоршела [3, 6], а Gateway Routng Protocol), EGRP (Extended GRP), для потокових моделей - методи математичного S-S (ntermedate System - to - ntermedate System), програмування або оптимального управлння [4, 5].
OSPF (Open Shortest Path Frst), PNN (Prvate Для кожно з потокових моделей вдповдних Network - to - Network nterface), все бльше затребуй алгоритмв та методв розвТязання задач маршруван саме потоков модел маршрутизац, як, з одтизац характерн сво особливост, умови й область ного боку, враховують потоковий характер сучаснозастосування. На жаль, у ранше вдомих роботах, го, переважно мультимедйного трафка (вдео, мова присвячених аналзу рзних моделей маршрутизац й н.), а з ншого боку, бльш адаптован пд вир- [4, 6 - 8], отриман досить загальн й переважно якшення завдань балансування навантаження й забез- сн висновки, за якими досить важко, а нод й зопечення якост обслуговування в мультисервсних всм неможливо з'ясувати х основн переваги, недотелекомункацйних мережах (ТКМ). ки, а також кращ варанти використання.
Аналз останнх дослджень публкацй до- Формулювання мети статт. Метою дано розволя зробити висновок про те, що до тепершнього боти одержання кльксних результатв порвняльчасу запропонована значна низка пдходв до пото- ного аналзу потокових моделей маршрутизац для кового моделювання задач маршрутизац в рамках рзних мережних топологй характеристик трафкв снуючих перспективних телекомункацйних тех- користувачв ТКМ. Проведення порвняльного ананологй [3 - 6]. Залежно вд повноти облку особли- зу потокових моделей маршрутизац в аспектах востей структурно-функцонально побудови й фун- балансування навантаження й забезпечення гарантовано якост обслуговування дозволить бльш точкцонування телекомункацйно мереж на виход но визначитися з напрямками х подальшого застот або ншо математично модел маршрутизац, сування.
як правило, формулються оптимзацйна задача, й О.В. Лемешко, О.А. Дробот, Д.В. Симоненко й Y Y Кбернетика та системний аналз грамування з забезпеченням мнмуму тако цльоЗагальна характеристика порвнюваних во функц:
моделей маршрутизац f max{xij ij}. (5) У робот в ход дослджень порвняльному ана- (i, j) зу пддавалися так основн п'ять потокових модеВикористання виразу (5) гаранту мнмзацю лей маршрутизац:
максимального коефцнта використання всх трак1. М-1. Модель одношляхово маршрутизац, тв передач в ТКМ. Крм того, у процес розвТязання яка рунтуться на пошуку найкоротшого шляху, необхдно виконувати умову збереження потоку який мстить мнмальну кльксть переприйомв k i ri, при xi,k, (6) i, j j k, j j,i i,j j,k (hop), як у протокол RP v1 [10].
j M k Mi 2. М-2. Модель багатошляхово маршрутизац i (БШМ), у якй на вдмну вд модел М-1 пдтриму- де Mi - множина сусднх вузлв вузлу ; ri,j - нться балансування навантаження за шляхами з рвтенсивнсть вхдного потоку (1/с), що надходить вд ною вартстю (довжиною). У цьому випадку користувачв на вузол i для вузла j ; - сума i,j розвТязання маршрутно задач було зведено до вхдного потоку й потоку, що надходить на вузол i розвТязання задач нйного програмування шляхом i мнмзац цльово функц вд сусднх вузлв для вузла j ; - маршрутна j,k f ctx, (1) змнна, тобто частина потоку, яку вдправля i,j де с - вектор вартсних (метричних) коефцнтв вузол i по тракту (i, k).
розмрност n, вс координати якого дорвнюють На маршрутн змнн накладаються так умови:
одиниц, тобто сi,j 1 ( i, j 1, m ; i j ); n - кль0, якщо i j; i i jk ксть трактв передач (ТП); m - кльксть мережних j,k 0, якщо i j, k Mi вузлв у ТКС у ТКМ x - шуканий вектор, коорди та. (7) ната xi, j якого моделю величину нтенсивност Через обмежену пропускну здатнсть трактв передач в модел М-5, так як в моделях М-3 М-4, трафка (1/с) у тракт передач ( i, j).
враховуться обмеження (4).
Вдповдно до фзики розв'язувано задач на 5. М-5. Модель БШМ Галлагера (5) - (7), яка координати вектора x накладаться система обмеотримала розвиток у робот [9] шляхом введення жень, що моделю умови збереження потоку в кожумов забезпечення гарантовано якост обслуговуному з мережних вузлв у ТКМ у цлому [4]:
вання за показниками швидкост передач пакетв, х середньо затримки, джитеру та ймоврност свочаxi,j x 0 - для транзитних вузл в ;
j,i сно доставки.
j:(i,j) j:( j,i) Критер порвняльного аналзу (2) xi,j x rвх - для вузла вдправника ;
j,i j:(i,j) j:( j,i) При проведенн порвняльного аналзу дослджувалася яксть розвТязання маршрутних задач на xi,j x rвх - для вузла отримувача, j,i множин структур С-1 та С-2 (рис. 1), як вдрзняj:(i,j) j:( j,i) лись розмрнстю, пропускними здатностями трактв де rвх - нтенсивнсть трафка на вход в мережу.
передач й звТязнстю мережних вузлв.
3. М-3. Модель БШМ з закладеною в основу Ефективнсть розвТязання задач маршрутизац метрикою протоколу GRP забезпеченням балансуоцнювалась за коефцнтом завантаження мереж вання навантаження за шляхами з нервною вартс( k ), який характеризував яксть балансування зав тю (довжиною). Модель М-5 представлена виразами навантаження в мереж, та двома основними показ(1) - (3) з рзницею лише в тому, що метрики трактв никами якост обслуговування - середньою затримпередач в протокол GRP, яким вдповдають кооркою ( ) та швидкстю передач пакетв ( r ). При сер динати вектора с у вираз (1), являють собою навемоделюванн, наприклад, трактв передач системою ден значення пропускно здатност ТП [1]:
масового обслуговування M / M /1, затримка в довсi,j 107 i, j ( i, j 1, m ; i j ). (3) льному ТП ( i, j ) розраховувалася за формулою [10] Крм того, з метою формалзац умов запоб1 (сi, j xi, j ).
i, j гання перевантаженням ТП поряд з виразом (2) ввоДля наочност швидксть передач даних ( r ) дяться додатков обмеження вигляду нормувалась по вдношенню до пропускно здатносxi, j i, j ( i, j 1, m ; i j ), (4) т мереж ( ), тобто r0 r.
де - пропускна здатнсть тракту передач (1/с).
i, j Вдповдно до структур ТКС (рис.1) кльксть 4. М-4. Модель БШМ, запропонована Галлаге- вузлв мереж варювалося вд 4 до 7; кльксть тракром [3], у рамках яко розвТязання маршрутно зада- тв передач - вд 5 до 12; пропускн здатност тракч зводиться до розвТязання задач нелнйного про- тв передач ТКМ - вд 500 до 900 1/с. нтенсивнсть Збрник наукових праць Харквського унверситету Повтряних Сил м. . Кожедуба, випуск 1(13), зовншнього трафка ( ) обмежувалася пропускною r Зона високого М - здатнстю ТКМ, обумовлено пропускними здатнос- навантаження М - тями трактв передач.
М - * + М - Вузол М - 11% 13% Вузол Вузол Абонентське навантаження, rВузол а а - С-Зона високого Вузол 2 Вузол М - навантаження М - М - * 1 + М - 3 М - Вузол Вузол 1,Вузол 3 Вузол 1,б - С-2,Рис. 1. Тополог ТКМ, як дослджувалися Абонентське навантаження, rАналз отриманих результатв б На пдстав отриманих результатв моделювання, порвняння та кльксно оцнки ефективност розглянутих потокових моделей маршрутизац за обраними критерями (рис. 2, 3) можна зробити так висновки.
По-перше, модель одношляхово маршрутизац (М-1) та модель БШМ (М-2) з балансуванням М - навантаження за шляхами з рвною вартстю (довМ - жиною) забезпечують необхдн показники якост М - * обслуговування лише в област невисокого наван+ М - М - таження ( r0 0 0,5 ).
По-друге, потокова модель багатошляхово маАбонентське навантаження, rршрутизац з метрикою протоколу IGRP (М-3) ста- в бльно працю практично на всй длянц абонентсьРис. 2. Результати порвняльного аналзу моделей кого навантаження. Ця модель з ростом навантаМ-1 - М5 для структури С-ження на мережу забезпечу послдовне використання шляхв у порядку зростання х пропускно швидкост передач (до 30%) та коефцнта викориздатност, тобто спочатку використовуться один стання мереж (у середньому на 30-60%), нж модель шлях з максимальною пропускною здатнстю, якщо М-3 в област середнього та високого навантаження.
цей шлях перевантажуться, то включаться в По четверте, модифкована модель Галагера, роботу другий шлях з наступною за величиною протобто модель з врахуванням умов забезпечення пускною здатнстю (рис. 2, а). Ця процедура повтоякост обслуговування (М-5), також здйсню баларються до використання всх доступних шляхв мж нсування навантаження одночасно за всма доступзаданою парою вузлв мереж.
ними шляхами мж заданою парою мережних вузПо-трет, модель Галлагера (М-4) забезпечу в. Однак ця модель у порвнянн з моделлю попебалансування навантаження одночасно за всма досредньою М-4 забезпечу зниження середньо затупними шляхами мж заданою парою мережних тримки доставки пакетв в 1,2 - 1,9 рази або збльвузлв. Ця модель сприя ефективному функцонушення швидкост х передач в середньому на ванню ТКМ на всй област абонентського наванта10 - 13% при зростанн коефцнта завантаження ження ( r0 0 1 ) та забезпечу кращ показники ТКМ у середньому на 18-22 % в област високого середньо затримки (у середньому в 1,3 - 2 рази), навантаження (рис. 3, в).
Середня затримка Середня затримка Коефцнт використання мереж Кбернетика та системний аналз Крм того, слд зазначити, що вдалий вибр метЗона високого М - навантаження рики ТП лише необхдною, але недостатньою умоМ - М - вою забезпечення бльш високих показникв якост * + М - 4 обслуговування. Необхдно в рамках математичних М - моделей маршрутизац не тльки забезпечувати балансування навантаження з реалзацю багатошляхових стратегй маршрутизац, а й у явному вигляд врахо7% вувати умови забезпечення якост обслуговування 10% (М-5) за тими чи ншими показниками [9]. Прикладом цьому результати порвняння моделей М-4 та М-5, 18% серед яких модель М-4 забезпечу бльш яксне балансування навантаження (рис. 3, в), однак значення покаАбонентське навантаження, rзникв середньо затримки та швидкост передач кращ а в модел М-5.
У подальшому при проведенн порвняльного Зона високого М - навантаження М - аналзу рзних моделей багатошляхово маршрутизац М - * + необхдно бльше уваги звернути на дослдження М - 4 М - впливу щодо якост розвТязання задач балансування та якост обслуговування не лише нтенсивност трафка, але й нших його характеристик - розмру пакета пач1,ковост та нших.
1,71 1,Список тератури 1,1,1. Остерлох Х. Маршрутизация в IP-сетях. Принципы, протоколы, настройка. - С.-Пб.: BHV, 2002. - Абонентське навантаження, r512 c.
2. Руденко И. Маршрутизаторы CISCO для IPб сетей. - М.: КУДИС-ОБРАЗ, 2003. - 656 с.
3. Бертсекас Д., Галлагер Р. Сети передачи данных. - М.: Мир, 1989. - 544 с.
4. Вишневский В.М. Теоретические основы проектирования компьютерных систем. - М.: Техносфера, 2003. - 512 с.
5. Дымарский Я.С., Крутякова Н.П., Яновский Г.Г.
Управление сетями связи: принципы, протоколы, приМ - кладные задачи. - М.: Эко-Трендз, 2003. - 384 с.
М - 6. Lee G. M. A survey of multipath routing for traffic М - * engineering // Proc. of LNCS 3391. Springer-Verlag, 2005. - + М - Vol. 4. - P. 635-661.
М - 7. Дымарский Я.С., Нурмиева М. В. Оптимальное распределение ресурсов в сети с разнородными потоками // Абонентське навантаження, rВестник МАИСУ. - 2002. - № 6. - С. 31-35.
8. Vutukury S., Garcia-Luna-Aceves J.J. A traffic enв gineering approach based on minimum-delay routing // Proc.
Рис. 3. Результати порвняльного аналзу моделей of IEEE IC3N. Las Vegas, 2000. - P. 42-47.
М-1 - М-5 для структури С-9. Лемешко А.В., Дробот О.А. Модель многопутеВисновки вой QoS-маршрутизации в мультисервисной телекоммуникационной сети // Радиотехника: Всеукр. межвед.
Як показали результати проведеного порвнянауч.-техн. сб. - Х.: ХТУРЭ, 2006. - Вып. 144. - С. 16-22.
ьного аналзу рзних потокових моделей маршру10. Клейнрок Л. Вычислительные системы с очеретизац (М1-М5), найбльш ефективними в рамках дями. - М.: Мир, 1979. - 600 с.
обраних критерв модел з балансуванням навантаження за шляхами з нервною вартстю (довжиНадйшла до редколег 9.01.ною). Причому в цих моделях БШМ важлива роль вдводиться вибору метрики трактв передач, вд Рецензент: д-р техн. наук, проф. В.В. Поповський, Харвигляду яко залежить стратегя (послдовна або па- квський нацональний унверситет радоелектронки, Харкв.
ралельна) використання шляхв нервно вартост.
Книги по разным темам