Ентропія джерела дискретних повідомлень, властивості ентропії
В [3] показано, що якщо представити дискретне джерело інформації як стаціонарний дискретний ергодичний (точніше марковський) процес, то середня швидкість передачі інформації 
від джерела (з точністю до коефіцієнта) і, отже, середня кількість інформації 
, що від нього можна одержати, визначаються величиною 
виду
. (1)
Формула (1) у теорії інформації носить назву формули Шеннона.
Величина (1) була введена Больцманом у статистичній механіці і названа ентропією. Шеннон при розробці фундаментальних положень теорії інформації ввів цю величину як міру інформації (у середньому) від джерела і теж назвав її ентропією розподілу імовірностей 
деякої події 
( 
). Якщо — імовірність незалежних букв алфавіту потужності 
, то характеризує середню кількість інформації, наприклад, «біт на символ» або «біт на розряд».
Ентропія є безперервною функцією від імовірності 
появи букви у тому чи іншому розряді (символі) повідомлення і володіє наступними властивостями.
1. Ентропія джерела дискретних повідомлень є величина дійсна, обмежена і ненегативна.
2. Ентропія джерела рівна нулю, якщо з імовірністю одиниця в якості символу вибирається одна й та ж буква алфавіту (невизначеність в поведінці джерела відсутня).
3. Ентропія максимальна, якщо всі символи джерела незалежні і рівноімовірні поява будь-якої букви 
алфавіту ( 
). При цьому є монотонною функцією числа та рівна 
.
|
|
|
Загальна характеристика способів маршрутизації повідомлень.
У процесі з'єднання між двома абонентами необхідно вказати маршрут у мережі, тобто визначити ті вузли мережі, через які буде проходити з'єднання.
Процес вибору маршруту проходження повідомлення називається маршрутизацією.
Ціль маршрутизації – доставка пакетів по призначенню з максимальною ефективністю.
Найчастіше ефективність виражена зваженою сумою часів доставки повідомлень при обмеженні на імовірність доставки їхньому одержувачеві. Маршрутизація зводиться до визначення напрямків руху пакетів у вузлах (маршрутизаторах). Вибір одного з можливих у вузлі напрямків залежить від поточної топології мережі, що може мінятися хоча б через тимчасовий вихід деяких вузлів з ладу, довжин черг у вузлах комутації, інтенсивності вхідних потоків і т.п. Алгоритми маршрутизації включають наступні типові процедури:
- вимір і оцінювання параметрів мережі;
- ухвалення рішення про розсилання службової інформації;
- розрахунок таблиць маршрутизації;
- реалізація прийнятих маршрутних рішень.
У комп'ютерних мережах застосовуються різні способи маршрутизації:
|
|
|
- хвильова (лавинна);
- с фіксованими шляхами;
- адаптивна.
Хвильова (лавинна) маршрутизація (flooding). При цьому способі здійснюється децентралізована маршрутизація без обліку якої-небудь інформації про мережі. Суть його полягає в наступному. Пакет, що надійшов у вузол, передається по усіх вихідних напрямках (широкомовна передача), за винятком вузла, з якого надійшов пакет. Якщо у вузол надходить пакет, що вже проходив по ньому, то цей пакет стирається. Щоб пакети, що розмножуються, не перевантажували мережу, віддаляються деякі пакети, тайм-аут яких минув, або минулих через кількість вузлів, що перевищує деяке задане число. Існує удосконалена версія широкомовної маршрутизації, називана селективним широкомовним розсиланням. По цьому способі розсилання виробляється не по всіх можливих напрямках, а тільки по тим, що приблизно ведуть у правильну сторону.
Основним достоїнством способу є висока надійність (використання в спеціальних мережах). Недолік – сильне завантаження мережі, ускладнення вузлів.
Маршрутизація з фіксованими шляхами підрозділяється на одномаршрутну (одношляхову) і на маршрутизацію з альтернативними шляхами. Поточний стан мережі не враховується. З'єднання між вузлами при одномаршрутному способі здійснюється завжди по тому самому шляху. Будь-які зміни в маршрутні таблиці вносить тільки адміністратор мережі. Основне достоїнство способу - його простота, однак, при відмовленнях окремих напрямків частина з'єднань при цьому способі взагалі не можлива. До недоліку такої маршрутизації варто віднести також ігнорування фактичним завантаженням трактів. Тому спосіб з фіксованими шляхами використовується переважно на мережах зі стабільним навантаженням.
|
|
|
Адаптивна маршрутизація враховує динамічний стан вузла або мережі, тобто маршрут адаптується до стану мережі. Способи адаптивної маршрутизації розділяють на локальні (облік тільки стану власного вузла) і глобальні, у яких враховується стан усієї мережі або більшої її частини. Протоколи, побудовані на основі адаптивної маршрутизації, дозволяють усім вузлам збирати інформацію про топологію мережі й оперативно обробляти всі зміни її конфігурації.
Дата добавления: 2023-01-08; просмотров: 16; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!