Методи оцінки швидкодії багатоступеневих комутуючих мереж в умовах нерівномірного трафіку

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Харківський національний університет

Радіоелектроніки

05.13.05 - Комп'ютерні системи та компоненти

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня кандидата технічних наук

Методи оцінки швидкодії багатоступеневих комутуючих мереж в умовах нерівномірного трафіку

Євграфов В'ячеслав Миколайович

Харків 2009

Дисертацією є рукопис.

Робота виконана у Харківському національному університеті радіоелектроніки, Міністерство освіти і науки України.

Науковий керівник - доктор фізико-математичних наук,

професор Дікарєв Вадим Анатолійович,

Харківський національний університет радіоелектроніки,

професор кафедри прикладної математики.

Офіційні опоненти: доктор технічних наук,

професор Хаханов Володимир Іванович,

Харківський національний університет радіоелектроніки,

декан факультету комп'ютерної інженерії та управління;

доктор технічних наук,

професор Борисенко Олексій Андрійович,

Сумський державний університет,

завідувач кафедри електроніки та комп'ютерної техніки.

Захист відбудеться « 28 » жовтня 2009 р. о 14.00 годині на засіданні спеціалізованої вченої ради Д 64.052.01 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розіслано « 26 » вересня 2009 р.

Вчений секретар спеціалізованої вченої ради Чалий С.Ф.

Размещено на http://www.allbest.ru//

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

У поданій роботі запропоновано новий метод підвищення пропускної здатності багатоступеневих мереж, який ґрунтується на впровадженні паралельних ступенів. Метод передбачає використання паралельного каналу для передачі пакету в разі виникнення колізії. Доведено, що метод дає збільшення пропускної здатності системи більш ніж у 1,5 рази.

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася згідно з планом науково-дослідних робіт Харківського національного університету радіоелектроніки в рамках держбюджетних тем:

- 104-1 «Методи стабілізації та фокусування випадкових розподілень неоднорідних марківських систем» (№ДР 0100U001344);

- 151 «Розробка методів стабілізації та синтезу неоднорідних систем, які мають марківські ознаки» (№ДР 0103U001574).

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

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

Для досягнення цієї мети потрібно вирішити такі завдання:

- розробити метод реконфігурації багатоступеневих комутуючих мереж в умовах нерівномірного трафіку;

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

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

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

- застосувати розроблені методи для синтезу комутуючих фабрик.

Об'єктом дослідження є процес оцінки швидкодії багатоступеневої комутуючої мережі, яка функціонує в умовах нерівномірного трафіку.

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

Методи дослідження. Для розробки методів оцінки швидкодії були використані методи математичного аналізу, теорія ймовірності та теорія систем масового обслуговування.

Наукова новизна отриманих результатів:

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

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

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

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

Програмний комплекс був використаний в: ЗАТ “Softline” для розробки комутуючої мережі при проектуванні багатопроцесорної комп'ютерної системи, що підтверджується відповідним актом впровадження від 27.02.2009; ВАТ «Конектор» при розробці мережевого АТМ роутера (акт впровадження від 16.01.2009); ТОВ «Zoral Labs» при розробці багатокомпонентної системи на кристалі (акт впровадження від 25.03.2009); Харківському національному університеті радіоелектроніки на кафедрі прикладної математики у навчальному процесі (акт впровадження від 06.04.2009).

Особистий внесок здобувача. Дисертаційна робота є результатом самостійних розробок автора. У роботах, виконаних у співавторстві, автору належать такі результати: у роботі [1] - розроблено імітаційну модель марківського випадкового процесу; у роботі [2] - розроблено імітаційну модель стохастичного процесу з нормальною функцією розподілу; у роботі [3] - розроблено метод обчислення пропускної здатності кінцевих каналів; у роботі [4] - досліджено властивості нерівномірного трафіку в багатоступеневих комутуючих мережах; у роботі [5] - розроблено метод оцінки швидкодії багатоступеневої комутуючої мережі для випадку нерівномірного трафіку; у роботі [6] - презентовано метод збільшення пропускної здатності багатоступеневої комутуючої мережі шляхом впровадження паралельних каналів; у роботі [7] - розроблено математичну модель динамічної буферної пам'яті та запропоновано метод реконфігурації буферів для досягнення більш ефективного використання доступної пам'яті; у роботі [8] - розроблено метод оцінки пропускної здатності буферної асинхронної багатоступеневої мережі для випадку нерівномірного трафіку та недетермінованого розміру пакетів.

Апробація результатів дисертації. Основні результати проведених досліджень доповідалися й обговорювалися на таких конференціях: 4-му Міжнародному молодіжному форумі «Радіоелектроніка та молодь у XXI столітті» (Харків, ХНУРЕ, 2000 р.); 8-й Міжнародній конференції «Теорія та техніка передачі, прийому та обробки інформації» («Інтегровані інформаційні системи, мережі та технології») ПСТ-2002 (Харків, ХНУРЕ, 2002 р.); 8-му Міжнародному молодіжному форумі «Радіоелектроніка та молодь у XXI столітті» (Харків, ХНУРЕ, 2004 р.); 4-й Міжнародній науково-технічній конференції «Проблеми інформатики та моделювання» (Харків, НТУ ХПІ, 2004 р.); 7-й Всеукраїнській студентській науковій конференції з прикладної математики та інформатики (Львів, ЛНУІФ, 2004 р.); 10-й ювілейній міжнародній конференції «Теорія та техніка передачі, прийому та обробки інформації» (Харків, ХНУРЕ, 2004 р.); East-West Design & Test International Workshop (Одеса, 2005 р., Сочі, 2006 р.); 10-й Міжнародній науково-технічній конференції CADSM-2009 (Львів, 2009 р.).

Публікації. За результатами виконаних досліджень опубліковано 17 робіт, у тому числі 8 статей у наукових фахових виданнях, що входять до переліків, затверджених ВАК України, та 9 статей у науково-технічних журналах та збірниках праць науково-технічних конференцій.

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, одного додатку. Загальний обсяг роботи складає 195 стор., з яких основний зміст викладено на 150 стор. Дисертація містить 55 рисунків, 16 таблиць та список використаних джерел із 138 назв на 15 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність теми і викладено перелік досліджених питань, сформульовано мету та методи дослідження. Викладаються також положення, що виносяться автором на захист. Представлено дані щодо апробації результатів роботи та їх впровадження.

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

Визначено місце та роль багатоступеневих комутуючих мереж при побудові багатопроцесорних систем та мережевих ATM комутаторів. Багатопроцесорні системи HORIZON, TERRA, Blue Gene/L, Blue Gene/W, ASCI Purple (IBM), Earth Simulator (NEC) використовують багатоступеневі мережі як комутаційне поле. Фірми IBM, AT&T, Fujitsu, Bellcore, Alcatel Data Networks мають моделі ATM комутаторів, які базуються на багатоступеневих мережах. Це пояснює важливість досліджень пропускної здатності багатоступеневих мереж для галузі.

Проведено аналіз умов виникнення нерівномірного трафіку і зроблено висновок, що нерівномірний трафік переважає у ряді випадків.

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

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

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

У другому розділі удосконалено метод оцінки пропускної здатності синхронних багатоступеневих комутуючих мереж та набув подальшого розвитку метод обрахунку швидкодії буферних асинхронних багатоступеневих комутуючих мереж.

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

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

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

Рис. 1. Багатоступенева комутуюча мережа 1616

Запропоновано класифікувати множини пріоритетних каналів за кількістю пріоритетних компонентів, які знаходяться в області досяжності двох підмножин, що утворюються після проходження трафіком наступного ступеня. Визначимо три типи множин пріоритетних каналів:

- кінцеві канали. Одна підмножина каналів має один пріоритетний вихідний канал у своїй області досяжності, а інша - не має жодного;

- загальні канали. Одна підмножина каналів має декілька пріоритетних вихідних каналів, а інша - не має жодного;

- граничні канали. Одна та друга підмножини каналів мають по декілька пріоритетних вихідних каналів.

Розглянемо вирази для обчислення інтенсивності потоку даних на каналах кожного типу. Позначимо інтенсивності потоку даних на пріоритетних та звичайних вихідних каналах пріоритетного КЕ ступеня відповідно через та , . Інтенсивність потоку даних решти каналів позначимо як , .

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

- для кінцевих каналів:

,	(1)

для , ;

- нехай підмножина має пріоритетних вихідних каналів. Тоді для загальних каналів маємо:

- ,	(2)

для , ;

- нехай одна підмножина має , а друга - пріоритетних вихідних каналів. Тоді для граничних каналів маємо:

,	(3)

для ,;

- для решти множин звичайних каналів маємо:

, (4)

для ,.

Метод оцінки пропускної здатності синхронних багатоступеневих комутуючих мереж базується на отриманих співвідношеннях (1-4) та містить у собі такі кроки:

Крок 1. Використовуючи (1), розрахувати інтенсивність вихідного потоку кінцевих каналів.

Крок 2. Використовуючи (2), розрахувати інтенсивність вихідного потоку загальних каналів.

Крок 3. Використовуючи (3), розрахувати інтенсивність вихідного потоку граничних каналів.

Крок 4. Якщо поточний ступінь не є останнім, вибрати наступний ступінь та перейти на крок 1.

Крок 5. Обчислити пропускну здатність багатоступеневої мережі як відношення інтенсивності вихідного потоку останнього ступеня до інтенсивності вхідного потоку першого ступеня.

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

Побудуємо метод обчислення швидкодії буферних асинхронних багатоступеневих комутуючих мереж.

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

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

Оскільки інтенсивність вхідного потоку пакетів дорівнює інтенсивності вихідного потоку пакетів попереднього ступеня, маємо:

, (5)

де - ймовірність переповнення буферної пам'яті на ступені .

Використовуючи теорему Літла, отримуємо вираз для часу перебування пакету на ступені :

. (6)

Час затримки пакетів у мережі розраховується за формулою (6), просумованою за усіма . Пропускна здатність буферної асинхронної мережі розраховується як останнього ступеня з використанням виразу (5). Величини знаходимо за допомогою таких виразів:

;

;

;

, , .

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

1) Обчислення пропускної здатності для кінцевих каналів. Нехай одна підмножина каналів має один пріоритетний вихідний канал. Для цих каналів пропускна здатність обчислюється як . Друга підмножина каналів має один звичайний вихідний канал. , де ;

2) обчислення пропускної здатності загальних каналів. Нехай перша підмножина каналів має множину пріоритетних вихідних каналів . Тоді

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

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

4) для решти звичайних каналів пропускну здатність обчислюємо за формулою (5).

Запропоновані співвідношення (5-6) дозволили розробити метод оцінки швидкодії буферних асинхронних багатоступеневих комутуючих мереж.

Метод містить у собі такі кроки:

Крок 1. Вибрати перший ступінь.

Крок 2. Використовуючи вираз (5), обчислити інтенсивність вихідного потоку поточного ступеня.

Крок 3. Використовуючи співвідношення (6), обчислити час перебування пакетів у буферних елементах поточного ступеня.

Крок 4. Якщо поточний ступінь не є останнім, вибрати наступний ступінь та перейти на крок 1.

Крок 5. Обчислити пропускну здатність мережі як відношення інтенсивності вихідного потоку останнього ступеня до інтенсивності вхідного потоку першого ступеня.

Крок 6. Обчислити час затримки пакетів як сумарний час перебування пакетів на усіх ступенях.

Крок 7. Обчислити швидкодію мережі як відношення пропускної здатності до часу затримки пакетів.

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

Для зменшення ймовірності колізій в умовах нерівномірного трафіку запропоновано ввести три додаткові типи комутуючих елементів:

- КЕ-24. Складається з двох звичайних вхідних каналів, двох паралельних вихідних каналів та комутуючого блоку;

- КЕ-4. Складається з двох паралельних вхідних каналів, двох паралельних вихідних каналів та комутуючого блоку. На вхід до такого елемента може подаватися до чотирьох пакетів даних одночасно. Втрата виникає при колізії двох пакетів;

- КЕ-42. Виконує функцію адаптера між паралельними та звичайними каналами.

Для кожного типу комутуючих елементів розроблено алгоритми комутації.

Запропоновано обчислювати пропускну здатність для синхронних мереж з використанням додаткових типів комутуючих елементів на пріоритетних каналах у такий спосіб:

для КЕ-24: ; (7)

для КЕ-44:

(8)

;

для КЕ-42:

(9)

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

для кінцевих каналів , , ;

для загальних каналів , де - кількість пріоритетних вихідних каналів у підмножині, , ;

для граничних каналів , де та - кількість вихідних каналів у першій та другій підмножині, , .

Пропускна здатність для решти непріоритетних каналів визначається у такий спосіб: нехай , , тоді:

для КЕ-24: ; (10)

для КЕ-44:

; (11)

для КЕ-42:

. (12)

Запропонований метод збільшення пропускної здатності мереж шляхом розпаралелювання ступенів базується на співвідношеннях (1-12) і містить такі кроки:

Крок 1. Побудувати залежність інтенсивності вихідного потоку від інтенсивності вхідного потоку, використовуючи (1-4) або (5).

Крок 2. Якщо пропускна здатність відповідає цільовому значенню, реконфігурація мережі не потрібна.

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

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

Крок 5. Якщо тип комутуючої мережі є синхронним, перейти на крок 9.

Крок 6. Збільшити розмір буферної пам'яті та/або комутуючих елементів.

Крок 7. Використовуючи (5, 6), обчислити пропускну здатність та швидкодію мережі.

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

Крок 9. Розпаралелити наступний ступінь.

Крок 10. Обчислити пропуску здатність першого ступеня, використовуючи співвідношення (10).

Крок 11. Якщо наступний ступінь складається з елементів КЕ-44, обчислити пропускну здатність ступеня, використовуючи (11).

Крок 12. Якщо наступний ступінь складається з елементів КЕ-42, обчислити пропускну здатність ступеня використовуючи (12).

Крок 13. Якщо наступний ступінь складається з елементів КЕ-22, обчислити пропускну здатність ступеня, використовуючи (1-4).

Крок 14. Виконувати кроки 11-13 аж поки не отримаємо значення пропускної здатності для усіх ступенів. Сума цих значень складає загальну пропускну здатність мережі.

Крок 15. Якщо значення пропускної здатності не відповідає цільовій пропускній здатності, перейти на крок 9.

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

У четвертому розділі застосовано методи оцінки та підвищення пропускної здатності синхронних багатоступеневих комутуючих мереж розмірів 256256, 512512, 40964096, 1638416384, 6553665536, 524288524288 та асинхронної буферної багатоступеневої комутуючої мережі 10241024.

У середовищі Java розроблено імітаційну модель, за допомогою якої виконується експериментальна перевірка методів оцінювання та підвищення швидкодії багатоступеневих комутуючих мереж. Експериментальну перевірку виконано на прикладі багатоступеневої мережі 256256, яка складається із восьми ступенів, кожен з яких має по 128 комутуючих елементи. Трафік має такі параметри: , де - ймовірність призначення пакета на -й вихідний порт; - ймовірність призначення пакета на будь-який непріоритетний порт; - розмір мережі. Застосування методу розпаралелювання вихідних каналів дозволило збільшити пропускну здатність у 1,7 разів (рис. 2). Приріст інтенсивності вихідного потоку після впровадження паралельних каналів значно більший при великих значеннях інтенсивності вхідного потоку.

Рис. 2. Інтенсивність вихідного потоку для різної кількості паралельних ступенів

Вихідні канали, які знаходяться на максимальній відстані від пріоритетних вихідних каналів, мають найбільше значення інтенсивності потоку (рис. 3). Після семиразового розпаралелювання каналів структура вихідного трафіку залишилась без змін.

Рис. 3. Структура вихідного трафіку паралельної та звичайної мережі

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

Окремо узяті інтенсивність вихідного потоку та час реагування мережі не є достатніми показниками продуктивності мережі. При зростанні пропускної здатності також збільшується і час відгуку мережі. На рис. 4 зображена швидкодія мережі, яка визначається як відношення інтенсивності потоку до часу реагування.

Рис. 4. Залежність швидкодії мережі від інтенсивності вхідного потоку при розмірах буферної пам'яті на 2, 5 та 9 пакетів

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

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

ВИСНОВКИ

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

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

2. Запропоновано ітеративний метод оцінювання пропускної здатності синхронних багатоступеневих комутуючих мереж при визначених параметрах вхідного трафіку. Порівняння результатів використання методу при обчисленні пропускної здатності синхронної багатоступеневої комутуючої мережі з експериментальними даними показало, що відносна похибка методу становить не більше 3%. На прикладі синхронних мереж розмірів 256256 та 512512 досліджено, що максимальна пропускна здатність спостерігається на каналах максимально віддалених від пріоритетних каналів. При збільшенні кількості паралельних каналів структура вихідного трафіку на змінюється. Максимальне зростання пропускної здатності спостерігається на каналах, віддалених від пріоритетних каналів.

3. Удосконалено метод розрахунку швидкодії буферних асинхронних багатоступеневих мереж, які функціонують в умовах нерівномірного трафіку з довільною кількістю пріоритетних вихідних каналів. Метод базується на побудованому раніше методі Чіти Даса. На відміну від попереднього методу, новий метод застосовний для недетермінованого розміру пакетів. Метод вироджується в раніше розроблений метод Чіти Даса у випадку єдиного пріоритетного вихідного каналу та детермінованого розміру пакетів. Відносна похибка методу не перевищує 3%. Оцінка швидкодії асинхронної багатоступеневої мережі розміру 10241024 показала, що розмір буферної пам'яті та комутуючих елементів впливає на пропускну здатність та час затримки мережі. При зростанні розміру буферної пам'яті пропускна здатність мережі теж зростає деякий час, аж поки не досягне точки насичення. При збільшенні розміру буферної пам'яті час затримки пакетів зростає швидше за умови вищої інтенсивності вхідного трафіку. При великих розмірах буферної пам'яті висока інтенсивність вхідного потоку призводить до зниження швидкодії мережі. Збільшення розміру комутуючого елемента призводить до зменшення часу затримки пакетів та зростання швидкодії мережі.

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

5. Застосування методів оцінки та підвищення швидкодії синхронних та асинхронних комутуючих багатоступеневих мереж розмірів 256256, 512512, 40964096, 1638416384, 6553665536 та 524288524288 дозволило збільшити пропускну здатність мереж більше ніж у 1,5 разів. Розроблені методи використані для синтезу комутуючих фабрик із підвищеною швидкодією завдяки впровадженню паралельних ступенів.

6. Результати дисертаційної роботи доведені до рівня програмних засобів, які були впроваджені в ТОВ «Лабс Зорал», ЗАТ «Софт Лайн», ВАТ «Конектор» та Харківському національному університеті радіоелектроніки що підтверджується відповідними актами впровадження.

СПИСОК ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Евграфов В.Н. Реализация локальных фокусировок распределений марковских процессов по заданным статистикам в случаях, когда фазовое пространство принадлежит пространствам R2, S2, R3 / В.Н. Евграфов, В.А. Дикарев, К.В. Кобылинский, А.В. Котелевцев, В.Н. Шершень // Радиоэлектроника и информатика. - 2001. - № 1. - С. 62-64.

2. Евграфов В.Н. Стабилизация распределений марковских процессов с континуальным множеством состояний для случая нормального распределения / В.Н. Евграфов, В.А. Дикарев, В.Н. Шершень // Радиоэлектроника и информатика. - 2003. - №4. - С. 90-93.

3. Евграфов В.Н. Производительность непрямой многоступенчатой сети при наличии горячего трафика для конечных каналов / В.Н. Евграфов // Радиоэлектроника и информатика. - 2005. - №1. - С. 119-122.

4. Евграфов В.Н. Свойства безбуферных многоступенчатых сетей для произвольного числа горячих модулей памяти / В.Н. Евграфов // Вестник национального технического университета «ХПИ». - 2004. - № 46. - С. 153-160.

5. Евграфов В.Н. Производительность безбуферных многоступенчатых сетей при наличии горячего трафика / В.Н. Евграфов, В.А. Дикарев // Вестник национального технического университета «ХПИ». - 2005. - № 46. - С. 52-59.

6. Евграфов В.Н. Повышение производительности безбуферных многоступенчатых сетей методом дублирования ступеней / В.Н. Евграфов // Вестник национального технического университета «ХПИ». - 2005. - №56. - С. 145-150.

7. Евграфов В.Н. Реконфигурация динамических буферов модулей памяти в условиях горячего трафика / В.Н. Евграфов // Вестник национального технического университета «ХПИ». - 2006. - № 31. - С. 42-48.

8. Евграфов В.Н. Производительность буферных асинхронных многоступенчатых сетей с произвольным числом приоритетных модулей памяти / В.Н. Евграфов // Автоматизированные системы управления и приборы автоматики. - 2008. - № 145. - С. 80-86.

9. Евграфов В.Н. Стабилизация распределений марковских процессов при локальных возмущениях состояний для случаев, когда множество всех элементарных исходов принадлежит либо плоскости, либо трехмерному пространству // В.Н. Евграфов, В.А. Дикарев, К.Н. Кобылинский, В.Н. Шершень // Радиоэлектроника и Молодежь в XXI веке: междунар. молод. форум, 11-13 апр. 2000 г.: тезисы докл. Ч.2. -- Харьков: ХНУРЭ, - С. 116-117.

10. Евграфов В.Н. Математическая модель перемешивания фармакологического препарата в процессе его изготовления / А.В. Мирошниченко, В.А. Дикарев, В.Н. Евграфов // Теория и техника передачи, приема и обработки информации: восьмая междунар. науч.-техн. конф., 2002 г.: тезисы докл. - Харьков: ХНУРЭ, - С. 403-404.

11. Евграфов В.Н. Стабилизация случайных процессов с изменяющимся числом состояний. / В.Н. Евграфов, В.Н. Шершень. // Радиоэлектроника и Молодежь в XXI веке: междунар. молод. форум, 13-15 апр. 2004 г.: тезисы докл. Ч.2. -- Харьков: ХНУРЭ, - С. 141.

12. Євграфов В.М. Атласи економіко-виробничих показників і зв'язків / В.М. Євграфов, В.М. Шершень, В.А. Дікарєв // Сьома Всеукраїнська студентська наукова конференція з прикладної математики та інформатики, 22-23 апр. 2004 г.: тезисы докл. - Львів: ЛНУІФ. - С. 18.

13. Евграфов В.Н. Атласы экономико-производственных показателей и связей / В.Н. Евграфов, В.Н. Шершень, В.А. Дикарев // Теория и техника передачи, приема и обработки информации: десятая юбилейная междунар. науч.-техн. конф., 2004 г.: тезисы докл. - Харьков: ХНУРЭ, - С. 191-192.

14. Евграфов В.Н. Свойства безбуферных многоступенчатых сетей для произвольного числа «горячих» модулей памяти / В.Н. Евграфов // Проблемы информатики и моделирования: четвертая международная науч.-техн. конф., 25-27 ноябр. 2004 г.: тезисы докл. - Харьков: НТУ ХПИ, - С. 153-159.

15. Евграфов В.Н. Throughput evaluation of MIN in case of hot-spot traffic with arbitrary number of hot spots / В.Н. Евграфов // East-West Design & Test International Workshop: междунар. науч.-техн. конф., 15-19 сент. 2005 г.: тезисы докл. - Одесса, - С. 246-250.

16. Евграфов В.Н. Output buffer reconfiguration in case of non uniform traffic / В.Н. Евграфов // East-West Design & Test International Workshop: междунар. науч.-техн. конф., 15-19 сент. 2006 г.: тезисы докл. - Сочи, - С. 267-271.

17. Евграфов В.Н. Performance Analysis of Asynchronous MIN with Variable Packets Length / В.Н. Евграфов // CADSM 2009: Десятая междунар. науч.-техн. конф., 24-28 фев. 2009 г.: тезисы докл. - Львов: НУЛП, 2009, - С. 205-207.

АНОТАЦІЯ

Євграфов В.М. Методи оцінки швидкодії багатоступеневих комутуючих мереж в умовах нерівномірного трафіку. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - комп'ютерні системи та компоненти. - Харківський національний університет радіоелектроніки, Харків, 2009.

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

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

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

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

Ключові слова: багатоступенева комутуюча мережа, пропускна здатність, час затримки, інтенсивність трафіку, комутуюча фабрика.

АННОТАЦИЯ

Евграфов В.Н. Методы оценки производительности многоступенчатых коммутирующих сетей в условиях неравномерного трафика. Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. - Харьковский национальный университет радиоэлектроники, Харьков, 2009.

В диссертационной работе решена актуальная научно-практическая задача оценки и увеличения быстродействия многоступенчатых коммутирующих сетей синхронного и асинхронного типов.

Разработан новый метод реконфигурации синхронных многоступенчатых коммутирующих сетей с целью увеличения пропускной способности сетей путем внедрения параллельных коммутирующих ступеней. Разработаны коммутационные алгоритмы для новых типов переключающих элементов размерности 24, 44 и 42. Определены правила построения параллельных коммутирующих многоступенчатых сетей и разработан обобщенный метод расчета пропускной способности многоступенчатых коммутирующих сетей с произвольным числом параллельных ступеней для случая неравномерного трафика с произвольным числом приоритетных каналов. Данный метод основан на методе Атикуцамана, расширенном на случай произвольного числа приоритетных выходных каналов и произвольного числа параллельных ступеней сети. Метод вырождается в исходный метод Мухаммеда Атикуцамана при единственном приоритетном канале и нулевой степени распараллеливания сети.

Применение метода увеличения пропускной способности для синхронных многоступенчатых сетей размерности 256256, 512512, 40964096, 1638416384, 6553665536 и 524288524288 показало, что метод позволяет увеличить пропускную способность болем чем в 1,5 раза.

Разработан усовершенствованный метод оценки пропускной способности синхронных многоступенчатых коммутирующих сетей. Усовершенствованный метод основан на методе Мухаммеда Атикуцамана и расширен на случай произвольного числа приоритетных выходных каналов. Разработанный метод вырождается в исходный метод Мухаммеда Атикуцамана в случае наличия единственного приоритетного выходного канала.

Разработан усовершенствованный метод оценки производительности асинхронных буферных многоступенчатых коммутирующих сетей. Усовершенствованный метод основан на методе Читы Даса, который расширен на случай недетерминированного размера пакетов и произвольного числа приоритетных каналов. Разработанный метод вырождается в исходный метод Читы Даса при детерминированном размере пакетов и единственном приоритетном канале.

Оценка производительности многоступенчатой коммутирующей сети размерности 10241024 показала, что размерность буферной памяти, переключающих элементов и количество приоритетных каналов влияет на пропускную способность сети, время задержки пакетов и распределение выходного трафика.

На основе методов оценки и увеличения производительности многоступенчатых сетей разработан метод синтеза многоступенчатых коммутирующих сетей синхронного и асинхронного типов с целевыми значениями пропускной способности и времени отклика сети. Увеличение быстродействия многоступенчатых сетей выполняется благодаря повышению размерности коммутирующих элементов, увеличению буферной памяти и распараллеливанию ступеней.

Разработано программное обеспечение для среды Java, реализующее предложенные в диссертационной работе методы оценки и увеличения производительности многоступенчатых коммутирующих сетей синхронного и асинхронного типов, которое может быть использовано как в научных исследованиях, так и в учебном процессе.

Ключевые слова: многоступенчатая коммутирующая сеть, пропускная способность, время отклика, интенсивность трафика, асинхронная буферная сеть, буферная память, коммутирующий элемент.

ABSTRACT

Evgrafov V.N. Performance estimation of multistage interconnection networks under non-uniform traffic patterns. - Manuscript.

Thesis for a Ph.D. science degree by specialty 05.13.05 - computer systems and components, Kharkiv National University of Radioelectronics, Kharkiv, 2009.

The problem of performance evaluation and increasing of synchronous and asynchronous MIN has been solved in this thesis.

The method of throughput increasing of synchronous MIN by introducing parallel stages has been developed which allows increase throughput for more then 1.5 times. The method is concluded in replication of data channels and thus introducing extra stages. There are new types of switching elements with dimensions 24, 44 and 42 has been presented.

The method of throughput evaluation of synchronous MIN has been enhanced for the case of non-uniform traffic with arbitrary number of hot-spots.

The method of performance evaluation of asynchronous MIN has been enhanced for the case of non-deterministic packet's length and arbitrary number of hot-spots. Influence of memory size and switching element dimension has been studied. Impact of hot-spots on the traffic structure also has been extensively analyzed.

Proposed methods are based upon methods developed earlier by Mohamed Atiquzzaman and Chita Das. New methods are generalized regarding arbitrary number of hot spots and non-deterministic packet size.

Key words: multistage interconnection network, throughput, latency, performance, traffic rate, asynchronous buffered network.

Размещено на Allbest.ru

...