Дискретний протокол ALOHA
Почнемо наше вивчення протоколів довільного доступу з одного з найбільш простих протоколів, так званого дискретного протоколу ALOHA. У нашому описі дискретної системи ALOHA ми будемо припускати наступне:
□ всі кадри складаються рівно з L біт;
□ час розділено на інтервали часу (слоти) тривалістю L / R секунд (це час, протягом якого передається один кадр);
□ вузли починають передачу кадрів тільки в момент початку чергового слота;
□ вузли синхронізуються так, що кожен вузол знає, коли починається слот;
□ якщо протягом даного тимчасового слота стикаються кілька кадрів, тоді все вузли виявляють факт зіткнення, перш ніж закінчиться цей слот.
Робота дискретного протоколу ALOHA на кожному вузлі проста. Коли у вузла є новий кадр для передачі, він чекає, поки не почнеться новий тимчасовий слот, після чого весь кадр передається протягом одного тимчасового слота. Якщо передача проходить без колізії, повторна передача кадру не потрібно (вузол може підготувати до передачі новий кадр). У разі колізії вузол виявляє факт колізії, перш ніж закінчується даний слот. Потім при настанні кожного наступного слота з вероятностьюр вузол передає кадр повторно до тих пір, поки кадр не буде переданий без колізії.
Під повторною кадру з ймовірністю р ми маємо на увазі, що вузол як би підкидає монетку. При цьому кадр передається повторно, тільки якщо випадає решка, що відбувається з імовірністю р. При випаданні орла, що відбувається з ймовірністю (1-р), вузол пропускає даний часовий інтервал і підкидає монетку ще раз. Всі вузли, залучені в колізію, підкидають свої монетки незалежно один від одного.
Може здатися, що дискретний протокол ALOHA має ряд переваг. На відміну від протоколів мультиплексування з поділом каналу, дискретний протокол ALOHA дозволяє єдиному активному в мережі вузла передавати кадри без перерви з максимальною швидкістю R (вузол називається активним, якщо у нього є кадр для передачі). Дискретний протокол ALOHA є у великій мірі децентралізованим, так як кожен вузол сам виявляє факт колізії і незалежно від інших вузлів приймає рішення про час повторної передачі. (Однак для використання дискретного протоколу ALOHA потрібна синхронізація вузлів. Далі ми коротко обговоримо безперервну версію протоколу ALOHA, а також протоколи CSMA, які не потребують подібної синхронізації і, таким чином, є повністю децентралізованими.) Крім того, ALOHA є надзвичайно простий протокол.
Дискретний протокол ALOHA добре працює в тих ситуаціях, коли є тільки один активний вузол, але яка його ефективність при наявності декількох активних вузлів? Ефективність дискретного протоколу ALOHA знижується завдяки двом факторам. По-перше, як показано на рис. 5.13, коли в мережі декілька активних вузлів, певна частка слотів марнується через колізії. (Як показано на малюнку, в першому слоті в колізію залучаються три вузла. Потім вузлу 2 вдається передати кадр в четвертому слоті, вузлу 1 - у восьмому слоті, а вузлу 3 - в дев'ятому.) По-друге, інша частка слотів витрачається даремно, коли всі активні вузли одночасно відмовляються від передачі. Дискретний протокол ALOHA працює продуктивно тільки в ті слоти, коли передавати потрібно рівно одному вузлу. Слот, протягом якого передає тільки один вузол, називається успішним слотом. Ефективність дискретного протоколу колективного доступу визначається часткою успішних слотів в ситуації великої кількості активних вузлів, у кожного з яких завжди є велика кількість кадрів для передачі. Зверніть увагу, що, якщо взагалі не використовувати протоколу колективного доступу і після колізії негайно повторювати передачу кожним з вузлів, ефективність мережі була б дорівнює нулю. Дискретний протокол ALOHA очевидно збільшує ефективність мережі, але наскільки?
Спробуємо визначити максимальну ефективність дискретного протоколу ALOHA. Щоб спростити наші обчислення, трохи змінимо протокол, припустивши, що кожен вузол з імовірністю р намагається передати кадр з настанням кожного нового слота. Тобто ми припускаємо, що у кожного вузла завжди є кадр для передачі і вузол завжди з ймовірністю р намагається передати кадр незалежно від того, новий це кадр або передається повторно. Нехай в мережі буде N вузлів. В цьому випадку слот виявляється успішним, якщо один з вузлів передає, а N - 1 вузлів утримуються від передачі. Імовірність того, що якийсь конкретний вузол буде передавати, дорівнює р. Імовірність того, що інші N- 1 вузлів не передаватимуть, дорівнює (1 - p) (N-1). Таким чином, ймовірність того, що даного вузла вдасться успішно передати кадр, дорівнює р (1 -p) (N-1). Оскільки існує N вузлів, ймовірність того, що пощастить одному (будь-якого) з них, дорівнює Np (i -p) (N-1).
Таким чином, при наявності N активних вузлів ефективність дискретного протоколу ALOHA дорівнює Np (l -p) (N-1). Щоб визначити максимальну ефективність протоколу при iV активних вузлах, нам потрібно знайти таке значення ймовірності р *, при якому цей вислів сягає максимуму. А щоб отримати максимальну ефективність протоколу для великої кількості активних вузлів, ми можемо знайти межа значення Np * (l -p *) (N-l) для значення N, що прагне до нескінченності (знову ж, см. Вправи в кінці глави). Виконавши всі ці обчислення, ми виявимо, що максимальна ефективність протоколу становить 1 / е
0,36788. Таким чином, коли у великої кількості вузлів є багато кадрів для передачі, то (в кращому випадку) лише окбло 37% слотів канал буде працювати з користю. Тобто ефективна пропускна здатність каналу одно не R біт / с, а всього лише 0,37 R біт / с! Виявляється, що близько 37% часу канал буде простоювати і ще близько 26% часу витрачати на обробку колізій. Уявіть собі нещасного мережевого адміністратора, який придбав дискретну систему ALOHA з пропускною спроможністю 100 Мбіт / с і збирається використовувати її для обслуговування трафіку між великою кількістю користувачів з сумарною пропускною спроможністю близько 80 Мбіт / с! Незважаючи на те що миттєва пропускна здатність каналу дорівнює 100 Мбіт / с, його успішна пропускна спроможність складе менше 37 Мбіт / с.
Мій блог знаходять за такими фразами
Відповідальність, за все зміни, внесені в систему за порадами даної статті, Ви берете на себе.