Протокол бітової карти

У першому протоколі без зіткнень, який ми розглянемо, що називається основним методом бітової карти, кожен період конкуренції полягає рівно з N тимчасових інтервалів. Якщо у станції 0 є кадр для передачі, вона передає одиничний біт під час 0-го інтервалу. Іншим станціям не дозволяється передача в цей час. Під час інтервалу 1 станція 1 також повідомляє, чи є у неї кадр для передачі, передаючи біт 1 або 0. В результаті до закінчення інтервалу N всі N станцій знають, хто хоче передавати. У цей момент вони починають передачу відповідно до свого порядку номерів (мал. 4.6). Оскільки всі знають, чия черга передавати, зіткнень немає. Після того як остання станція передає свій кадр, що всі станції відстежують, прослуховуючи лінію, починається новий період подачі заявок з N інтервалів. Е - станція переходить в стан готовності (отримує кадр для передачі) зразу після того, як вона відмовилася від передачі, це означає, що їй не повезло і вона повинна чекати наступного циклу. Протоколи, в яких намір передавати оголошується всім перед самою передачею, називаються протоколами з резервуванням

Мал. 4.6. Базовий протокол бітової карти

Оцінимо продуктивність такого протоколу. Для зручності вимірюватимемо час в однобітових інтервалах періоду подачі заявок, при цьому кадр даних складається з d одиниць часу. При слабкому завантаженні каналу біт-карта просто буде повторюватися знову і знову, зрідка перемежаючись кадрами. Розглянемо цю ситуацію з погляду станції з невеликим номером, наприклад, 0 або 1. Зазвичай в той момент, коли у неї виникає потреба в передачі, поточний інтервал часу вже знаходиться десь в середині біт-карти. В середньому станція чекатиме N/2 інтервалів до закінчення поточного періоду резервування і ще N інтервалів наступного (свого) періоду зарезервовування, передаваних між двома цими періодами, перш ніж она зможе почати передачу. ерспективи станцій з великими номерами більш веселкові. В середньому час ування передачі складе половину циклу (N/2 однобітових інтервалів). танціям з великими номерами рідко доводиться чекати наступного циклу. скільки станціям з невеликими номерами доводиться чекати в середньому 1,5n нтервалів, а станціям з великими номерами інтервалів, середній час очікування для всіх станцій складає N інтервалів. При низькому завантаженні каналу його продуктивність легко злічити. Накладні витрати на кадр складають JV біти, і при довжині кадру в d біти ефективність рівна d/(N + d). При сильній завантаженості каналу, коли всі станції хочуть щось передати період подачі заявок з N біт чергується з N кадрами. При цьому накладні витрати на передачу одного кадру складають всього один біт, а ефективність рівна d/(d +1). Середній час затримки для кадру буде рівний сумі часу очікування в черзі усередині своєї станції і додаткових N(d + l) /2 однобітових інтервалів, коли він потрапить в початок своєї внутрішньої черги.

Двійковий зворотний відлік

Недоліком базового протоколу біт-карти є накладні витрати в 1 битий на станцію. Використовуючи двійкову адресу станції, можна поліпшити еффективності каналу. Станція, охоча зайняти канал, оголошує свою адресу у вигляді бітового рядка, починаючи із старшого біта. Припускається, що всі адреси станцій мають однакову довжину. Біти адреси в кожній позиції логічно складуются (логічне АБО). Ми називатимемо цей протокол протоколом з двоїчним зворотним відліком. Він використовується в мережі Datakit (Fraser, 1987). Неявно передбачається, що затримки розповсюдження сигналу нехтує малі, по цьому станції чують затверджувані номери практично миттєво. Щоб уникнути конфліктів слід застосувати правило арбітражу: як тільки станція з 0 в старшому біті адреси бачить, що в сумарній адресі цей 0 заміняють одиницею, вона здається і чекає наступного циклу. Наприклад, якщо станції 0010, 0100, 1001 і 1010 конкурують за канал, то в першому бітовому інтервалі вони передають біти 0, 0, 1 і 1 відповідно. В цьому випадку сумарний перший біт адреси буде рівний 1. Отже, станції з номерами 0010 і 0100 рахуються проїгравшимі, а станції 1001 і 1010 продовжують боротьбу. Наступний біт у обох станцій, що залишилися, рівний 0 - таким чином, обидві продовжують. Третій біт рівний 1, тому станція 1001 здається. Переможцем виявляється станція 1010, оскільки її адреса найбільша. Вигравши торги, вона може почати передачу кадру, після чого почнеться новий цикл торгів. Схема протокола показана на мал. 4.7. Даний метод припускає, що пріоритет станції безпосередньо залежить від її номера. В деяких випадках таке жорстке правило може грати позитивну, в деяких - негативну роль.

Мал. 4.7. Протокол з двійковим зворотним відліком. Прочерк означає мовчання

Ефективність використання каналу при цьому методі складає d/(d+log2N)

Проте можна так хитро вибрати формат кадру, що його перше поле буде включати адресу відправника, тоді навіть ці log2ar біт не пропадуть дарма і еффективність складе 100 %. Мокнув (Мокнув) і Уард (Ward) в 1979 році описали варіант протоколу із зворотним відліком, в якому використовувався паралельний, а не послідовний інтерфейс. Вони також запропонували