Імовірне визначення кількості інформації за ШЕННОНОМ
Існує взаємозв'язок елементів у повідомленні. Зв'язок розуміється у імовірному змісті, тобто існує умовна імовірність появи (при даному алфавіті) символу «А» слідом за символом «В» – 
.
Нехай мається алфавіт 
, що складається з 
елементів (символів) 
, 
, … 
. Імовірності появи цих елементів у повідомленні відповідно рівні 
, 
, … 
. Складемо повідомлення, що містить 
довільних елементів алфавіту . Серед них буде 
елементів , 
елементів , ... , 
елементів . Імовірність появи кожної комбінації з елементів виразиться добутком імовірностей окремих елементів, тому що передбачається, що поява кожного елемента є незалежна подія. З урахуванням повторюваних елементів імовірність деякого повідомлення дорівнює
,
а імовірність появи 
-ro символу
.
Можна вважати, що всі 
можливих повідомлень (усі перестановки) рівноімовірні. Тому
,
відкіля число можливих повідомлень
. (5)
Логарифмуючи (5), одержимо середню кількість інформації в повідомленні довжиною при нерівноймовірності і незалежності його елементів:
. (6)
З вираження (6) неважко одержати (4) для випадку рівноймовірних подій ( 
), тобто міра кількості інформації з ХАРТЛІ є частковим випадком кількості інформації за ШЕННОНОМ.
Алгоритми і протоколи маршрутизації в комп'ютерних мережах.
|
|
|
На відміну від класичних телефонних мереж і інтегральних цифрових мереж передачі даних, комп'ютерні мережі мають специфічні особливості транспортування повідомлень, зокрема наступні:
- багато з'єднань проходять через дуже велике число вузлів комутації;
- лінії і вузли мають недостатньо високу надійність;
- характер переданих повідомлень протягом декількох хвилин може істотно змінитися;
- мала кількість альтернативних шляхів передачі.
При розгляді найбільше широко використовуваних алгоритмів маршрутизації будемо виходити з того, що кожному з вузлів мережі відомі адреси сусідніх вузлів, а для всіх ліній зв'язку, що з'єднують сусідні вузли, визначена їхня метрика. Як метрику зв'язків часто використовується «вартість» або «відстань». Узагальнене поняття «вартості» враховує як фактичну вартість використання лінії, так і ряд інших параметрів (відстань, пропускну спроможність, затримку передачі і т.д.).
Розглянуті алгоритми відносяться до розподілених, у яких вузлам удається так вибудувати глобальну маршрутну інформацію, що визначається маршрут з мінімальною вартістю, хоча кожен вузол обмінюється повідомленнями тільки зі своїми сусідами. Для цього в загальному потрібне велике число кроків (хопів), поки мережа не установиться в стабільний стан.
|
|
|
При виконанні алгоритму маршрутизації вузол повинний одержувати інформацію від сусідніх вузлів, що виконують такий же алгоритм маршрутизації, про мережі, що можуть бути досяжні при передачі даних через кожен сусідній вузол. Накопичуючи отриману інформацію, кожен вузол може визначити напрямок – маршрут передачі даних для кожної з досяжних мереж. У випадку, якщо таких маршрутів виявилося трохи, алгоритм маршрутизації може передбачати використання спеціального критерію для вибору кращого з них.
У залежності від способу, використовуваного для забезпечення обміну інформацією про маршрути в мережі між вузлами при виконанні алгоритму маршрутизації, розрізняють два типи протоколів маршрутизації:
- дистанційно-векторні (distant vector);
- оцінки стану ліній (link state) (стану зв'язків).
Дистанційно-векторні протоколи передають інформацію про маршрути періодично через встановлені інтервали часу.
Протоколи оцінки стану ліній (зв'язків) передбачають передачу інформації про маршрути в момент первісного включення або при виникненні змін в існуючій структурі інформаційних зв'язків.
|
|
|
До дистанційно-векторних алгоритмів (DVA – Distance Vector Algorithms) відноситься алгоритм Беллмана-Форда. Вихідним положенням у цьому алгоритмі є те, що кожному вузлові відомі розташування і можливості вузлів мережі, але невідомі найкоротші шляхи до них. Під «найкоротшим шляхом» мається на увазі шлях з мінімальною «вартістю». На кожнім вузлі є вектор відстаней, що представляє собою список із записами виду: «Одержувач; Вартість». Вартість позначає при цьому поточне значення суми «вартостей» доставки повідомлення по найкоротшому шляху до відповідного одержувача. Як початкове значення кожен вузол установлює такі вартості доставки повідомлень до несуміжних вузлів, що свідомо вище найвищих очікуваних витрат (установлюється нескінченно велике значення).
Маршрутизація з урахуванням стану зв'язків. Недоліки, властиві дистанційно-векторної маршрутизації, викликані тим, що вузли мають занадто мало інформації про топологію всієї мережі. При обліку стану ліній зв'язку (Link State Routing - LSR) вузли мережі мають інформацію про топологію всієї мережі і про вартість зв'язків між ними. Усі вузли мережі використовують той самий алгоритм для визначення першого найкоротшого шляху SPF (Shortest Path First).
|
|
|
На початку функціонування мережі кожен вузол формує групу пакетів стану ліній LSA (Link State Advertisements). LSA-пакет містить ідентифікатори власного і сусіднього вузлів, а також вартість зв'язків між ними. На наступному кроці пакети стану ліній розсилаються широкомовно всім іншим вузлам мережі. Вузли, що одержали LSA-пакети від усіх маршрутизаторів мережі, паралельно один з одним створюють топологічну базу даних, утримуючі всі LSA-повідомлення. На основі отриманої інформації вузли розраховують шляхи з мінімальними вартостями. При цьому маршрутизатор розраховує топологію найкоротших шляхів у виді SPF-дерева, поміщаючи себе в корінь. Усякий раз, коли LSA-пакет викликає зміну в базі дані стани каналів, алгоритм обліку станів ліній перераховує шляхи й обновляє таблицю маршрутизації.
Алгоритм SPF гарантує правильне функціонування мережі при порушеннях зв'язку або виході з ладу окремих маршрутизаторів і виключає можливість дворазової передачі пакета по тому самому шляхи. До алгоритмів, що використовують знання про топологію всієї мережі і враховуючої вартості зв'язків між усіма її вузлами, відноситься алгоритм Дейкстри (Dijkstra's algorithm) (Эдсгер Вайб Дейкстра). За допомогою цього алгоритму знаходяться найкоротші маршрути від даного вузла-джерела до всіх інших вузлів мережі.
На основі алгоритму Дейкстри найкоротші шляхи від заданого вузла-джерела до всіх інших вузлів мережі визначаються ітераційно (покроково) в процесі перебору маршрутів у порядку збільшення числа їхніх сегментів. Побудова шляхів відбувається поетапно. На 
-м кроці знаходяться шляхів з мінімальною вартістю до вузлів.
Білет №3
1. Ентропія джерела повідомлень. Властивості ентропії.
2. Загальна характеристика способів і протоколів маршрутизації повідомлень.
Відповіді.
Дата добавления: 2023-01-08; просмотров: 77; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!