використовувати віртуальні номери станцій. Після кожної передачі станції, яка успішно послала кадр, привласнюється віртуальний номер 0, тим самим дається можливість захоплення каналу сханциямі, які мовчать дуже довго. Наприклад, якщо станції З, Н, D, A, G, В, Е, F мали пріорітети 7, 6, 5, 4, 3, 2, 1 і 0 відповідно, тоді при успішній передачі станції D вона поміщається в кінець списку, отримуючи номер 0. Пріоритети старших станцій З і Н залишаються незмінними (7 і 6), а пріоритети решти станцій збільшуються на 1 (наприклад, пріоритет А був 4, а став 5). Таким чином, на наступному циклі формується такий список: З, Н,а, G, В, Е, F, D. Тепер станція D зможе дістати доступ до каналу, тільки якщо він більше нікому не потрібний. Двійковий зворотний відлік є прикладом простого, елегантного і ефективного протоколу, який ще належить відкрити наново розробникам майбутніх мереж. Хочеться сподіватися, що коли-небудь він займе свою нішу в мережевих технологіях.
Протоколи з обмеженою конкуренцією
Отже, ми розглянули дві основні стратегії надання доступу до каналу у кабельних мережах: змагання, як в CSMA, і безконфліктні методи. Кожному стратегію можна оцінити по двох важливих параметрах: часу затримки при низькому завантаженні каналу і ефективності каналу при великому завантаженні. В умовах низького завантаження конфлікти (тобто чиста або дискретна системи ALOHA) переважно, оскільки час затримки в таких системах менший. У міру зростання завантаженості каналу системи із зіткненнями стають всі менш привабливими, оскільки зростають накладні витрати, зв'язані
з конфліктами. Для безконфліктних протоколів справедливо зворотне. При низькому навантаженню у них досить високий час затримки, але у міру збільшення навантаження ефективність використання каналу не зменшується, як у конфліктних протоколів, а навпаки, зростає. Очевидно, було б непогано об'єднати кращі властивості обох стратегій
і отримати протокол, що використовує різні стратегії при різній загруженості каналу. Такі протоколи ми називатимемо протоколами з обмеженою конкуренцією. Вони насправді існують, і їх розглядом ми завершимо вивчення мереж з опитом носія. До цих пір ми розглядали тільки симетричні протоколи коллективного доступу, в яких кожна станція намагається дістати доступ до каналу з рівний вірогідністю р. Цікаво, що продуктивність всієї системи може бути покращувана при використанні асиметричного протоколу, в якому станціями призначаються різна вірогідність. Перш ніж приступити до розгляду асиметричних протоколів, давайте коротко розглянемо продуктивність в симетричному випадку. Припустимо що до станцій борються за доступ до каналу. Вірогідність передачі кожної станції в кожен інтервал часу рівний р. Вірогідність того, що якась станція успішно дістане доступ до каналу на даний інтервал часу, рівна kp(l -p)k'1. Щоб знайти оптимальне значення вірогідності р, продиференціюємо дане вираз по р, прирівняємо результат до нуля і вирішимо отримане рівняння щодо р. В результаті ми отримаємо, що якнайкраще значення р рівне 1/k. Замінюючи у формулі р на 1/k, отримуємо вірогідність успіху при оптимальному значенні р:
Залежність цієї вірогідності від кількості готових станцій графічно показана на мал. 4.8. Для невеликого числа станцій значення вірогідності успіх є непоганим, проте як тільки кількість станцій досягає хоч би п'яти, вірогідність знижується майже до асимптотичної величини, рівною 1/е.
Мал. 4.8. Вірогідність діставання доступу до каналу в симетричному протоколі
З малюнка очевидно, що вірогідність діставання доступу до каналу для ка¬
який-либо станції можна збільшити, тільки понизивши конкуренцію за канал. Цим
займаються протоколи з обмеженою конкуренцією. Вони спочатку ділять все
станції на групи (необов'язково непересічні). Змагатися за інтер¬
вал 0 вирішується тільки членам групи 0. Якщо хтось з них виграє, він
отримує канал і передає по ньому кадр. Якщо ніхто з них не хоче передавати
або відбувається зіткнення, члени групи 1 змагаються за інтервал 1, і так далі
При відповідному розбитті на групи конкуренція за кожен інтервал
часу зменшується, що збільшує вірогідність його успішного іспользова¬
нія (див. ліву частину графіка).
Питання в тому, як розбивати станції на групи. Перш ніж обговорювати об¬
щий випадок, розглянемо декілька окремих випадків. У одному з крайніх слу¬
чаю в кожній групі буде по одній станції. Таке розбиття гарантує
повна відсутність конфліктів, оскільки на кожен інтервал часу буде пре¬
тендовать тільки одна станція. Подібні протоколи вже розглядалися ра¬
її (наприклад, протокол з двійковим зворотним відліком). Ще одним особливим
випадком є розбиття на групи, що складаються з двох станцій. Вірогідність
того, що обидві станції одночасно почнуть передачу протягом одного інтерва¬
ла, рівна р2, і при малих значеннях р цим значенням можна нехтувати. По ме¬
ре збільшення кількості станцій в групах вірогідність зіткнень буде
зростати, проте довжина біт-карти, необхідною щоб перенумерувати все
групи, зменшуватиметься. Іншим граничним випадком буде одна група
до якої увійдуть всі станції (тобто дискретна система ALOHA). Нам требу¬
ется механізм динамічного розбиття станцій на групи з невеликим колі¬
чеством крупних груп при слабкій завантаженості каналу і великій кількості
дрібних груп (можливо, що навіть складаються з однієї станції кожна), коли за¬
груженность каналу висока.
Протокол адаптивного проходу по дереву Одним з простих способів динамічного розбиття на групи являєтсяалго¬
ритм, розроблений під час Другої світової війни в армії США для провер¬
ки солдат на сифіліс (Dorfman, 1943). Брався аналіз крові у N солдатів. Частина ка¬
ждого зразка поміщалася в одну загальну пробірку. Цей змішаний зразок
перевірявся на наявність антитіл. Якщо антитіла не виявлялися, всі солдати в
даній групі оголошувалися здоровими. У осоружному ж випадку група ділилася
навпіл, і кожна половина групи перевірялася окремо. Подібний процес
продовжувався до тих пір, поки розмір групи не зменшувався до одного солдата.
У комп'ютерній версії даного алгоритму