РОЗДІЛ 2
РОЗРОБКА ТА ДОСЛІДЖЕННЯ ШВИДКОГО ПАРАЛЕЛЬНОГО МЕТОДУ ПЛАНУВАННЯ КОМУТАЦІЇ ТА
ШЛЯХІВ ЙОГО РЕАЛІЗАЦІЇ
2.1. Базова структура ПКПД з багатоканальною вхідною буферизацією
З метою досягнення мінімального середнього часу затримки комутації пропонується
використовувати багатоканальну вхідну буферизацію, яка забезпечує вибір
декількох пакетів з вхідної черги в одному часовому проміжку шляхом
просторового (а не часового, як у відомих) суміщення доступу. На основі
проведених досліджень та враховуючи відомі вимоги [79] до алгоритму планування
комутації та ПКПД, що виконує вибір декількох пакетів з вхідного буферу шляхом
просторового суміщення доступу, ПКПД з багатоканальною буферизацією повинен
задовольняти наступні вимоги:
1. У випадку відсутності вихідного буферу, тільки один пакет в одному часовому
проміжку може бути спланований для одного вихідного порта.
2. Структура пристрою повинна забезпечувати вибір та передачу більше одного
пакету з одного вхідного буферу.
3. Планування комутації для кожного з вихідних портів є незалежним та може
виконуватись незалежно.
4. За умови використання ефективного алгоритму планування комутації досягається
максимальна пропускна здатність.
На основі сформованих вимог, з метою досягнення максимальної пропускної
здатності та мінімального середнього часу затримки комутації пакетів
запропоновано новий метод побудови ПКПД з вхідною буферизацією [83].
Запропонований метод передбачає застосування багатоканальної вхідної
буферизації (рис.2.1) та планування комутації, що забезпечують вибір та
планування більше одного пакету з одного вхідного буферу, чим досягається, в
порівнянні з відомими, мінімальний середній час затримки комутації в пристроях
комутації пакетів даних з вхідною буферизацією. Запропонований метод планування
комутації відноситься до класу методів планування комутації на основі вікна
обслуговування W.
Пристрій комутації пакетів згідно запропонованого методу складається з
(рис.2.1) вхідного буферу Q, що представляється масивом буферів пакетів
Q=[qi,k], i=1,2,…,M, k=1,2,…,W, пристрою планування комутації (ППК) та КМС. Де
M – кількість входів, N – виходів ПКПД. В ПКПД за кожен часовий проміжок t
поступає тільки один пакет в кожен з вхідних портів.
Рис.2.1 Структура ПКПД з багатоканальною вхідною буферизацією.
В порівнянні з відомими, ПКПД містить вхідні буфери, які забезпечують вибір та
передачу на свої виходи одночасно декількох пакетів. Кількість виходів буферів
є однаковою, та рівною N. Кількість пакетів, що вибираються з вхідних буферів
загалом та з кожного буферу зокрема задається ППК. При цьому ППК вказує, який з
буферів має передати на вихід пакет, тому загальні кількість пакетів що
вибираються з вхідних буферів загалом не перевищує N.
2.2. Швидкий паралельний метод планування комутації
Функціонування ПКПД будемо розглядати в дискретному часі t=0,1,2,..., –часових
проміжках. В одному часовому проміжку ПКПД може прийняти та передати з одного
порта пристрою не більше одного пакету.
Означення 1. Матриця ідентифікаторів H(t)=[hi] – це матриця-стовпець,
елементами якої є ідентифікатори hi(t), які в кожному часовому проміжку t разом
з вхідними пакетами поступають в ПКПД, та містять для кожного входу i=1,2,…M,
номер вихідного порта j=1,2,…,N, на який даний пакет має бути зкомутований.
Якщо h(t)i=0, пакет – відсутній.
При поступленні в момент часу t множини вхідних пакетів A(t), дані пакетів
зберігаються в масиві Q(t), а відповідні ідентифікатори H(t) поступають в ППК.
Для моменту часу t (часового проміжку) ППК на основі отриманих вхідних
ідентифікаторів визначає вектор комутації S(t):=[sj], j=1,2,…,N, який містить
слово комутації sj для кожного j-го вихідного порта. Слово комутації sj задає
номер пакету масиву Q, який комутується за допомогою комутуючої мережі на вихід
j.
Означення 2. Матриця ідентифікаторів V(t)=[vi,k] – це масив, елементами якого є
ідентифікатори vi,k, де vi,k =hi(t-k-1), i=1,2,…,M, k=1,2,…,W.
Означення 3. Матриця вибору G(t)=[gj,k] – це масив, елементами якого є числові
значення номеру стовпця матриці ідентифікаторів, де j=1,...,N, k=1,..,W.
Планування комутації для ПКПД з багатоканальною вхідною буферизацією
виконується згідно наступного методу планування:
, j=1,..,N;
де
На основі запропонованого методу планування комутації розроблено швидкий
паралельний алгоритм планування комутації ШПАК (рис.2.2). Основою даного
алгоритму є функція вертикального вибору V_SEL(V(t),j,k) та функція
горизонтального вибору H_SEL(G(t),j), які виконують пошук та вибір елементів
матриць V(t) та G(t) згідно певних критеріїв.
Функція вертикального вибору V_SEL(V(t),j,k) виконує пошук елемента, значення
якого рівне j серед елементів k-того стовпця матриці V(t). Функція повертає
номер рядка елемента, чи 0 у випадку відсутності в рядку елемента, значення
якого рівне j. У випадку наявності декількох елементів в k-му стовпці матриці
V(t), функція повертає найбільший номер рядка.
Функція горизонтального вибору H_SEL(G(t), j) виконує пошук серед елементів
j-того рядка матриці G(t) значення ненульового елемента. Якщо такий елемент
gj,k знайдено, то функція повертає пару чисел {i,k} , де i=gj,k та k – номер
стовпця знайденого елемента. У випадку наявності декількох ненульових елементів
в j-му рядку матриці G(t), функцією вибирається елемент з найбільший номером
стовпця. У випадку відсутності в j-му рядку ненульових елементів функція
повертає {0,0}.
Швидкий паралельний алгоритм планування комутації в кожному часовому проміжку t
виконує планування комутації згідно наступної послідовності дій:
Крок 1. Вертикальний пошук
Обчислення за допомогою функції ве
- Київ+380960830922