Динамічний розподіл каналів у локальних і регіональних мережах

Перш ніж приступити до розгляду численних методів розподілу каналів, слід ретельно сформулювати вирішувану проблему. У основі всіх розробок в даній області лежать наступні п'ять допущень.

1. Станційна модель. Модель складається з JV незалежних станцій (компьютерів, телефонів, персональних засобів зв'язку і т. д.), у кожній з яких програма користувача формує кадрів для передачі. Станції іноді називают терміналами. Вірогідність формування кадру в інтервалі часу At рівна Axt, де X є константою (швидкість прибуття нових кадрів). Як тільки кадр сформований, станція блокується і нічого не робить, поки

кадр не буде успішно переданий.

2. Припущення про єдиний канал. Єдиний канал доступний для всіх. Все станції можуть передавати і приймати дані по ньому. З погляду апаратури всі станції вважаються рівними, хоча програмно протокол може встановлювати для них різні пріоритети.

3. Допущення про колізії. Якщо два кадри передаються одночасно, вони перекриваются за часом, в результаті сигнал спотворюється. Така подія називаєтся конфліктом, або колізією. Всі станції можуть виявляти флікти. Спотворений унаслідок конфлікту кадр повинен бути переданий повторно. Інших помилок, окрім тих, які викликані конфліктами, немає.

4а. Безперервний час. Передача кадрів може початися у будь-який момент часу. Не існує ніяких синхронізірущих імпульсів, які ділили би час на дискретні інтервали.

46 Дискретний час. Час розділений на дискретні інтервали (такти). Передача кадру може початися тільки з початком такту. Один часовий інтервал може містити 0, 1 або більш за кадрів, що відповідає вільному інтервалу, успішній передачі кадру або колізії.

5а. Контроль тієї, що несе. Станції можуть визначити, вільна або зайнята лінія до її використання. Якщо канал зайнятий, станції не намагатимуться передавати кадри по ньому, поки він не звільниться.

56. Відсутність контролю тієї, що несе. Станції не можуть визначити, вільна або зайнята лінія, поки не спробують її використовувати. Вони просто починають передачу. Тільки потім вони можуть визначити, чи була передача успішної. Про приведені раніше допущення слід сказати декілька слів. Перше допущення стверджує, що станції незалежні і працюють з постійною швидкістю. Також неявно передбачається, що у кожної станції є тільки один користувач або програма, тому поки станція заблокована, вона не проводить ніякої роботи. Складніші моделі розглядають багатопрограмні станції, які можуть працювати в заблокованому стані, однак і аналіз подібних станцій набагато складніший. Допущення про єдиний канал є, насправді, центральним в даній моделі. Ніяких зовнішніх каналів зв'язку не немає. Станції не можуть тягнути руки привертаючи до себе увагу і переконуючи вчителя запитати їх. Допущення про колізії також є основним, хоча в деяких системах (особливо в системах з розширеним спектром) дане допущення звучить не так строго, що приводить до несподіваних результатів. Крім того, в деяких локальних мережах, наприклад в мережі token ring (маркерне кільце), використовується механізм дозволу колізій, що реалізовується за рахунок спеціальних пакетів - маркерів, що передаються від станції до станції. Поміщати в канал кадр може тільки той, у кого в даний момент знаходиться маркер. Далі ми обговоримо модель моноканалу з конкуренцією і колізіями. Для часу існує два альтернативні допущення. У одних системах час може бути безперервним (4а), в інших - дискретним, тому ми розглянемо обидва варіанти.

2. Протоколи колективного доступу

Відомо багато алгоритмів колективного доступу. У наступних розділах ми розглянемо найцікавіші алгоритми і дани приклади їх застосування.

Система ALOHA

У 70-х роках Норман Абрамсон (Norman Abramson) і його колеги з Гавайського університету розробили новий елегантний метод вирішення проблеми разподілення каналів. Їх праці згодом стали основою багатьох досліджень. 1 Слово «carrier» («що несе») в англійській мові означає також «перевізник». (Abramson, 1985). Хоча в роботі Абрамсона, що отримала назву ALOHA, використувався широкомовний радіозв'язок із стаціонарними передавачами основна ідея застосовна до будь-якої системи, в якій незалежні користувачі змагаються за право використання одного загального каналу. У даному розділі ми розглянемо дві версії системи ALOHA: чисту і дискретную. Вони відрізняються тим, чи ділиться час на дискретні інтервали, в період яких передаються кадри, чи ні. У чистій системі ALOHA не потрібна загальна синхронізація часу, а в дискретній потрібний.

Чиста система ALOHA

У основі системи ALOHA лежить проста ідея: дозволити користувачам передачу, як тільки у них з'являються дані для відсилання. Звичайно, при цьому будуть зіткнення, і кадри, що зіткнулися, будуть зруйновані. Проте завдяки властивості зворотного зв'язку широкомовної системи відправник завжди може встановити, чи дійшов його кадр до одержувача або був зруйнований. Для цього йому потрібно просто прослуховувати канал, як це робить решта всіх користувачів. У локальних мережах зворотний зв'язок миттєвий, а в супутникових системах існує затримка в 270 мс, і лише після цього відправник може дізнатися, наскільки успішної була передача. Якщо кадр був знищений, відправник просто очікує деякий випадковий час і намагається переслати цей кадр знову. Час очікування повинно бути випадковим. Інакше при рівних фіксованних інтервалах часу очікування колізії повторюватимуться знову і знову. Системи, в яких декілька користувачів використовують один загальний канал у такий спосіб, що час від часу виникають конфлікти, називаються системи з конкуренцією.

На мал. 4.1 показаний приклад формування кадрів в системі ALOHA. Всі кадри на нашому малюнку мають один розмір, оскільки при цьому пропускна спроможність системи зроблена максимальною саме за рахунок фіксованого розміру