сматріваются у вигляді листя двійкового дерева, як показано на мал. 4.9. У пер¬

вом тимчасовому інтервалі змагання за право передачі беруть участь всі станції.

Якщо кому-небудь це вдається, то на цьому работа4алгорітма закінчується. Якщо

же відбувається зіткнення, то до другого етапу змагань допускається толь¬

до половина станцій, а саме станції, що відносяться до вузла 2 дерева. Якщо одна

із станцій успішно захоплює канал, то наступне змагання влаштовується

для другої половини станцій (що відносяться до вузла 3 дерева). Якщо знову проїс¬

ходить конфлікт, то до наступного інтервалу часу серед ос¬, що змагаються

таєтся вже чверть станцій, що відносяться до вузла 4.

Таким чином, якщо зіткнення відбувається під час інтервалу 0, то все

дерево сканується на одиничну глибину для пошуку готових станцій. Кожен

однобітовий слот асоціюється з певним вузлом дерева. Якщо проїсхо¬

діт зіткнення, пошук продовжується для лівого і правого дочірніх вузлів. Ес¬

чи кількість станцій, що претендують на передачу, рівна нулю або одиниці

пошук в даному вузлі дерева припиняється.

При сильній завантаженості каналу навряд чи варто починати пошук готової

станції з вузла 1, оскільки шансів, що всього одна станція зі всіх буде пре¬

тендовать на канал, мало. З тієї ж причини можуть бути пропущені також

вузли 2 і 3. А на якому рівні дерева слід починати опит в загальному випадку?

Очевидно, що чим сильніше завантаженість каналу, тим на нижчому рівні

дерева повинен починатися пошук готових станцій. Припускатимемо, що каж¬

дая станція досить точно може оцінити q (кількість готових на даний

момент станцій), відстежуючи недавній трафік.

Пронумеруємо рівні дерева на мал. 4.9 - вузол 1 на рівні 0, вузли 2 і 3 на

рівні 1 і так далі Звернете увагу на те, що кожен вузол на рівні i включає

2"' частина від всіх станцій. Якщо q готових станцій розподілені рівномірно, то

очікуване їх число нижче за вузол на рівні i рівне 2-'q. Інтуїтивно ясно, що оп¬

тімальним рівнем для початку пошуку буде той, на якому середнє число кон¬

станцій, що курирують в інтервалі, рівне 1, тобто рівень, на якому 2~'q = 1.

Звідси i = Iog2<?.

Були розроблені численні удосконалення базового алгоріт¬

ма-в частковості, деякі деталі обговорюються у Бертсекаса (Bertsekas) і Гал-

лагера (Gallager) у виданні 1992 року. Наприклад, розглянемо випадок, при кото¬

ром передавати хочуть тільки станції G і Н. На вузлі 1 відбудеться конфлікт

тому буде перевірений вузол 2. Він виявиться порожнім. Вузол 3 перевіряти немає смис¬

ла, оскільки там гарантовано буде зіткнення. (Нам відомо, що під уз¬

лом 1 знаходяться 2 або більш за станції, а оскільки під вузлом 2 немає жодній стан¬

циі, то всі вони повинні бути під вузлом 3.) Тому перевірку вузла 3 можна

пропустити і відразу перевірити вузол 6. Оскільки під вузлом 6 нічого не оказа¬

лось, то перевірку вузла 7 також можна пропустітьі перевірити вузол G.

Протоколи множинного доступу

із спектральним розділенням

Ще один метод розподілу каналу полягає в його розбитті на подкана¬

ли за допомогою частотного, тимчасового або змішаного розділення і дінаміче¬

ського розподіли підканалів в міру необхідності. Подібні схеми часто

застосовуються в оптоволоконних локальних мережах, при цьому можлива одновре¬

менная передача по каналу на різних довжинах хвиль (тобто частотах). У даному

розділі ми розглянемо один такий протокол (Humblet і ін., 1992).

Найпростіше побудувати цілком оптичну локальну мережу за допомогою ком¬

мутатора «пасивна зірка» (див. мал. 2.8). Сенс полягає в тому, що два оптіче¬

ських волокна від кожної станції вплавляються в скляний циліндр. По одно¬

му волокну світло потрапляє в циліндр, а по іншому він з циліндра потрапляє в

інше волокно. Світло, що виходить в циліндр з одного волокна, освітлює весь

циліндр і потрапляє у всі волокна, що виходять з нього. Пасивні зірки можуть

об'єднувати до декількох сотень станцій.

Для реалізації одночасної передачі спектр ділиться на канали (діапа¬

зони довжин хвиль), як показано на мал. 2.27. У протоколі WDMA (Wavelength

Division Multiple Access - множинний доступ із спектральним разделені¬

їм) кожній станції виділяється два канали. Вузький канал забезпечує получе¬

ніє станцією інформації, що управляє, а широкий канал - передачу даних

станцією.

Кожен канал ділиться на групи тимчасових інтервалів, як показано на

мал. 4.10. Хай кількість інтервалів в каналі, що управляє, рівна т, а колі¬

чество інтервалів в каналі даних - п+ 1, з яких п інтервалів ісполь-

зуются для даних, а останній інтервал - для повідомлення станцією про своє со¬

стоянні (головним чином про те, які інтервали в обох каналах вільні).

У обох каналах послідовність інтервалів повторюється нескінченно, при

цьому інтервал 0 позначається спеціальним чином, щоб всі могли його распо¬

знати. Всі канали синхронізуються одними глобальними годинами.

Мал. 4.10. Множинний доступ із спектральним розділенням

Протоколом підтримуються три класи трафіку: 1) орієнтований на

з'єднання з пострянной швидкістю передачі даних, наприклад, нестисле ві¬

део; 2) орієнтований на з'єднання із змінною швидкістю передачі дан¬

них, наприклад, передача файлів; 3) дейтаграммний трафік, як, наприклад

UDP-пакеты. Для двох орієнтованих на з'єднання протоколів ідея заклю¬

чаєтся в тому, що якщо станція А хоче зв'язатися із станцією В, вона спочатку

повинна вставити кадр CONNECTION REQUEST (запит на з'єднання) у вільний ін¬

тервал каналу В. Еслі, що управляє, станція В згодна, зв'язок відбувається по

каналу даних А.

У кожної станції є два передавачі і два приймачі.

1. Приймач з фіксованою довжиною хвилі для прослуховування свого управ¬

ляющего каналу.

2. Передавач з довжиною хвилі, що настроюється, для передачі по керівникові

каналу іншої станції.

3. Передавач з фіксованою довжиною хвилі для передачі кадрів даних.

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

Іншими словами, кожна станція прослуховує свій канал, що управляє

Для отримання запитів,