logo
ІСвЕ Савенко_конспект лекций

20. Основні задачі оптимізації іс

Розглянемо деякі типові варіанти оптимізаційних задач, зв'язаних із топологічним проектуванням ІС. Можлива наступна їхня класифікація:

1. Вибір оптимальної пропускної здатності (ВЗП). Дано: топологія мережі, потоки, маршрути. Потрібно: мінімізувати затримки Т по змінній пропускній здатності каналів С,- при обмеженнях на вартість W і пропускні здібності С;

  1. Розподіл потоку. Дано: топологія мережі, потоки, пропускні здібності каналів. Потрібно: мінімізувати Т по змінній «маршрут руху» при заданих обмеженнях на потоки;

  2. Оптимальний розподіл потоків і одночасно вибір пропускних здібностей. Дано: топологія мережі, потоки. Потрібно: мінімізувати W по змінних «маршрут» і «пропускна здатність» при заданих обмеженнях на потік і час затримки;

  3. Визначення оптимальної топології мережі. Дано: характеристики трафіка ІС. Потрібно: мінімізувати по змінним «топологія», «маршрут» і «пропускна здатність» при обмеженнях на потік, затримки й топологію.

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

де W — повна вартість ліній; Wі — вартісний коефіцієнт для і-лінії; Сі — пропускна здатність і - лінії.

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

Середня затримка для і-ї лінії задається часом чекання в черзі при допущеннях, що довжина повідомлень має експоненціальний розподіл [11].

де , — інтенсивність потоку повідомлень в і-м каналі; 1/ — середня довжина повідомлень (у бітах).

Середнє значення затримки по всім складовим виходить шляхом усереднення значення узятого з ваговими коефіцієнтами , де — сумарна швидкість надходження повідомлень. Таким чином, середня затримка Т при цьому визначається виразом:

Шукані пропускні здібності, що мінімізують Т при постійному , визначаються методом невизначених множників Лагранжа. Опускаючи відповідні математичні перетворення, приведемо результат у готовому виді:

де — визначається виразом:

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

Величина результуючої транзитної затримки при передачі по лініях із пропускними здібностями Сі- вищенаведеними рівностями, що задаються, визначається так:

( -сума інтенсивностей трафіка по всіх лініях).

Розглянута задача дозволяє при заданому обмеженні на вартість каналів зв'язку так вибрати пропускні здібності, щоб середня затримка повідомлень була мінімальною.

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

Як вихідне вираження для рішення задачі використовуємо приведену вище формулу.

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

Відповідно до цього закону сумарний трафік (j — k), що надходить у вузол, дорівнює сумарному трафіку (j—k), що виходить з вузла, за винятком випадку, коли вузол u = j є вузлом-джерелом або при n = k — вузлом призначення. На пропускні здібності накладаються обмеження, сутність яких в тім, що потік у каналі і не повинний бути негативним і меншим пропускної здатності, тобто .

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

Часто при оптимізації ІС використовується метод відхилення потоку (ВП), суть якого полягає в перебуванні вартості мережі для значень «довжин» і-х ребер. Значення довжин ребер задаються виразом:

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