Елементи моделі організаційної структури

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

Пункти мережі підрозділяються на кінцеві і вузлові.

Кінцеві пункти (КП) (Endpoints) – це пункти, в яких розміщено термінальне обладнання користувачів і кінцеві системи мережі (сервери, на яких зосереджено інформаційні ресурси й застосовання, у тому числі застосовання системи керування мережею).

Пункти, призначені для розміщення термінального обладнання користувачів, яке забезпечує доступ в мережу, функціонують у ролі абонентських пунктів (АП). Пункти, у яких зосереджено інформаційні ресурси, називаються інформаційними центрами (ІЦ), а пункти системи керування відповідно – центрами керування (ЦК).

У кінцевих пунктах телекомунікаційна мережа представлена пристроєм мережевого закінчення (Network Termination Unit, NTU), або просто мережевим закінченням (Network Termination, NT), яке в організаційній структурі набуває статусу точки присутності телекомунікаційної мережі. Прикладом цього є звичайна телефонна розетка, інформаційна розетка з телекомунікаційним роз'ємом для під’єдання комп'ютера.

Вузловий пункт (Node Рoints) – це пункт мережі, в якому сходяться дві і більше ліній зв'язку.

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

Концентрація (Concentration) передбачає поєднання декількох невеликих за потужністю вхідних інформаційних потоків з метою отримання більш потужного вихідного потоку. Функція може бути реалізована в спеціалізованому пристрої на основі статистичного ущільнення (асинхронне мультиплексування). Слід зауважити, що в концентраторі для локальних мереж, який має назву «хаб», ця функція виконується досить умовно. Повідомлення, яке надходить на один з входів хаба, передається одночасно на всі виходи.

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

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

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

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

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

Порядок відносень між елементами (їх статус) в моделі організаційної структури визначається рівнями їх ієрархії (рис. 3.9).

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

АП зазвичай під’єднуються до вузлових пунктів рівня доступу. Таким чином для них реалізується право доступу в мережу (до її ресурсів).

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

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

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

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

Лінії зв'язку в моделі організаційної структури також отримують відповідний статус.

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

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

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

4. Архітектура мережі. Функціональна модель. Протокольна модель. Модель програмного забезпечення.

Функціональна модель – це абстрактний опис мережі зв'язку, що не залежить від принципів її фізичної реалізації.

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

Функція – це певний логічний елемент, що виконує конкретне завдання в мережі. Реалізація функцій допустима в таких варіантах:

• у вигляді апаратних засобів;

• у вигляді програмного продукту.

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

Розрізняють такі основні типи функцій мережі зв'язку:

• прикладні функції – об'єкти застосовань користувачів;

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

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

• комунікаційні функції – транспортні функції, функції керування передачею потоків даних, функції керування телекомунікаційними послугами;

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

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

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

Логічний інтерфейс між об'єктами одного типу називається протоколом.

Логічний інтерфейс між комунікаційними функціями отримав назву еталонної точки телекомунікаційної мережі.

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

Функціональні модулі можуть формуватися як функціональні підсистеми й домени.

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

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

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

Домен – це функціональний модуль, сформований за принципом приналежності функцій і об'єктів одній групі. При цьому враховувати їх спільну дію при реалізації в апаратних засобах або програмних продуктах не потрібно. Прикладами можуть бути домен користувача (рис. 3.11) і домен оператора мережі (рис. 3.12).

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

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

Крім вищесказаного слід наголосити ще на одному принципово важливому аспекті функціональної моделі мережі.

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

Проілюструємо це таким чином. Наприклад, концепція телефонної мережі полягає в побудові дорогих АТС як єдиної структури, в якій поєднують функції комутації, керування обслуговуванням викликів, об'єкти послуг та застосовань, а також білінгу. Така АТС у мережі є монолітною, закритою системною структурою та, як правило, не допускає розширення або модернізації з використанням обладнання інших виробників. Спроба відокремити від АТС підсистему послуг та застосовань породила концепцію інтелектуальної мережі (Intelligent Network, IN). Це дозволило організувати в телефонній мережі додаткові види обслуговування (ДВО) (розширити конфігурацію домену) та надавати різні послуги за заявками користувачів, формуючи їх з окремих компонентів.

Концепція IN припускає наявність таких функціональних модулів (підсистем), як модуль розпізнавання викликів, що вимагається виконанням ДВО; модуль формування необхідного сервісу з незалежних функціональних компонентів; модуль керування мережевими ресурсами та ін.

При цьому функціонування підсистеми ДВО є абсолютно незалежним від типу мережі зв'язку. Технологія IN може бути реалізована на базі будь-якої комутованої мережі (аналогової або цифрової), а також мережі передачі даних.

Протокольна модель описує роботу мережі зв'язку на рівні правил взаємодії (протоколів) об'єктів (функцій) та функціональних модулів, розосереджених на різних кінцевих системах.

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

Ієрархію протокольних рівнів (блоків) протокольної моделі конкретної мережі зв'язку називають стеком протоколів.

(Рисунок: нечто, похожее на схему взаимодействия двух OSI).

N-об'єкти виконуючи завдання N-рівня, здійснюють локальний комплекс функцій даного рівня. Протокольні блоки розташовані на рівні таким чином, що можливість виконання завдання N-рівня цілком залежить і забезпечується участю об'єктів нижчерозташованого (N−1)-го рівня й так далі. Таким чином, N-об'єкти виявляються залученими у взаємодію з (N-1)-об'єктами, а (N–1)- об’єкти з (N –2)- об’єктами і т. д.

Кажуть, що кожен нижчий рівень надає сервіс вищому рівню.

Будь-який об'єкт N-рівня, активізуючись, видає інформацію двох типів:

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

2) інформацію керування, яка призначена для об'єкта (N–1)-го рівня, за допомогою якої здійснюється координація процедур "з'єднання" об'єктів N-го рівня різних кінцевих систем.

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

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

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

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

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

5. Компоненти і моделі фізичної структури мережі. Модель апаратурної реалізації функцій та об’єктів. Активне та пасивне обладнання мережі.

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

Загальна архітектура зв'язку та принципи взаємодії функцій і об'єктів кожного рівня вже є відомими з попереднього розділу.

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

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

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

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

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

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

Елементами моделі апаратурної реалізації є такі:

• апаратне забезпечення (Hardware)– обладнання, в якому одна або декілька функцій реалізовано фізично;

• програмне забезпечення (Software) – один або декілька програмних модулів, які представляють собою реалізацію одного або декількох об'єктів;

• фізичний інтерфейс (Phisical interface) – фізичне середовище (проводи) для передачі сигналів між різної апаратурою.

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

Активне обладнання мережі:

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

У технічній літературі набули вжитку такі позначення класів апаратури: DTE, DCE і DTE/DCE. Охарактеризуймо кожен з них більш детально.

Усі пристрої в мережі, які функціонують як джерела та приймачі даних на фізичному рівні моделі OSI/ISO, визначаються як клас DTE (Data Terminal Equipment) – кінцева апаратура даних (КАД). У термінології електрозв'язку дана апаратура називається ще «кінцевим обладнання даних» (КОД).

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

Відмінною особливістю обладнання класу DTE є те, що воно не належить до складу устатковання ліній зв'язку.

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

Обладнання, що забезпечує сполучення DTE з каналами зв'язку, визначається як клас DCE (Data Communication Equipment) - апаратура передачі даних (АПД). Пристрої DCE працюють на фізичному рівні, відповідаючи за передачу й прийом сигналів потрібної форми та потужності в середовищі передачі, й не можуть розглядатися в якості джерел і приймачів даних.

Визначаючи чіткіше, варто зауважити, що мережеве обладнання важко розподілити за конкретними класами DTE та DCE. Наприклад, мережевий адаптер можна вважати як складовою комп'ютера (DTE), так і частиною каналу зв'язку (DCE).

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

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

Зважаючи на вищепростежене, такі комунікаційні пристрої, як мости, комутатори і маршрутизатори розглядають у межах змішаного класу – класу DTE/DCE, де розрізняють відповідні типи портів: DTE або DCE. Для цих портів принципами функціонування є такі: для порту DTE сигнал даних передавача є вихідним, а сигнал даних приймача – вхідним; для порту DCE– відповідно навпаки.

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

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

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

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

Загальне поняття про задачі синтезу та аналізу:

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

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

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

Для синтезу мережі, зазвичай, є заданим географічне розташування пунктів мережі, які слід об'єднати в зв’язну мережу (саме поняття «синтез» у перекладі з грецької означає «з'єднання», «складання»). При цьому топологія ліній зв'язку є невідомою характеристикою, яку необхідно з’ясувати, й вона може варіюватися залежно від оптимізації економічних показників. Це дає змогу розглядати мінімум витрат на лінії зв'язку як цільовий критерій оптимального синтезу мережі.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Моделювання зв'язувальної мережі як об'єкта синтезу та аналізу:

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

О з н а ч е н н я. Графом називають певну сукупність точок, з’єднаних лініями.

Точки графа називають вершинами, а лінії – дугами.

Граф математично позначають як G(N,V), де N – кінцева множина вершин потужністю n, а V – кінцева множина дуг потужністю m.

Вершини можна позначити малими латинськими літерами (i, j, k, l, s) або арабськими цифрами (1, 2, 3, 4, 5), а дуги – відповідно парами: {(i,j), (j,k), (k,l),...} або {(1,2), (2,3), (3,4),...}, де перший індекс визначає початок, а другий – кінець дуги (див. рис. 6.1).

Між двома вершинами, з'єднаними дугою (ребром), існує відношення суміжності (для орієнтованого графа вершини i і j суміжні, лише якщо дуга починається в i та направлена в j).

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

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

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

Крім геометричного зображення у вигляді точок і ліній, граф можна відтворити дискретно. Саме таку форму використовують у програмній реалізації алгоритмів для розв’язування задач із застосуванням графових моделей в ЕОМ Однією з найбільш поширених дискретних форм графа є матриця суміжностей. Це матриця А=[aij], розміром (n×n) елементів, які можуть набувати значень:

аij = 1, якщо в графі G є дуга (ребро) між вершинами i та j;

аij = 0, – у протилежному випадку.

Матрицю суміжності графа наведено на рисунку 6.2.

Для зберігання в пам'яті ЕОМ матриці суміжності, як бачимо, необхідно n 2 комірок.

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

Якщо перенумерувати довільно дуги (ребра) графа G і проставити ці номери відповідно до номерів рядків деякої матриці В=[bij], а номери стовпців залишити, як і раніше, відповідними номерам вершин графа, то в такій матриці можна відобразити відношення інцидентності елементів графа G. Елементи матриці Bij можуть набувати значень {0, 1}.

Якщо перенумерувати дуги графа, наведеного на рисунку 6.1, так: (i, j) – 1; (j, k) – 2; (k, l) – 3; (l, s) – 4; (s, i) – 5;

(s, j) – 6; (s,k) – 7, то матриця інцидентності набуде вигляду (див. рис. 6.3):

Зверніть увагу, що орієнтованість графа в цій матриці, на відміну від матриці суміжностей, не відображається.

Мережа (зважений граф) у дискретному вигляді може бути відтворена матрицею ваг W=[wij], де wij – вага дуги (ребра), якщо вона (воно) існує в графі G. Вага ненаявних дуг (ребер), вважають, дорівнює ∞ або 0, що залежить від умов поставленої задачі.

Якщо граф є розрідженим (має малу кількість дуг (ребер)), то можливим є більш компактне подання графа G, а саме списком дуг (ребер). Цей список можна реалізувати двома одновимірними масивами (R1 і R2) розмірністю m, у першому з яких записано початкові вершини дуг (ребер), а в другому – кінцеві, або двовимірним масивом R розмірністю (2, m).

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

Date: 2016-07-22; view: 504; Нарушение авторских прав