Додаткові матеріали по темі.

Алгоритм зв'язуючого дерева (Spanning-Tree Algoritm) (STA)

Алгоритм був розроблений для того, щоб зберегти переваги петель, усунувши їх проблеми. Спочатку алгоритм був документований корпорацією Digital - основним постачальником Ethernet. Новий алгоритм, розроблений Digital, був згодом переглянутий комітетом IEEE 802 і опублікований в специфікації IEE 802. 1d як алгоритм STA.

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

STA користуються висновком з теорії графів як базис для побудови вільної від петель підмножини топології мережі. Теорія графів затверджує наступне:

Для будь-якого приєднаного графа, що складається з вузлів і ребер, що сполучають пари вузлів, існує зв'язуюче дерево з ребер, яке підтримує зв'язність даного графа, але не містить петель.

Мал. 29-3 пояснює, яким чином STA усуває петлі. STA вимагає, щоб кожному мосту був призначений унікальний ідентифікатор. Звичайно цей ідентифікатор є однією з адрес МАС даного моста, який доповнений пріоритетом. Кожному порту у всіх мостах також призначається унікальний (в межах цього моста) ідентифікатор (як правило, його власна адреса МАС). І нарешті, кожний порт моста взаємозв'язаний з витратами якого-небудь тракту. Витрати тракту є витратами на передачу якого-небудь блоку даних в одну з локальних мереж через цей порт. На Мал. 29-3 "Мережа ТБ до прогону STA" витрати трактів відзначені на лініях, витікаючих з кожного моста. Витрати трактів звичайно встановлюються за умовчанням, але можуть бути призначені уручну адміністраторами мережі.

Першим кроком при обчисленні зв'язуючого дерева є вибір кореневого моста (root bridge), який є мостом з якнайменшим значенням ідентифікатора моста. На Мал. 29-3 кореневим мостом є Міст 1. Далі визначається кореневий порт (root port) у всій решті мостів. Кореневий порт моста - це порт, через який можна потрапити в кореневий міст з якнайменшими комбінованими витратами тракту. Ця величина (тобто якнайменші комбіновані витрати тракту до кореневого моста) називається витратами кореневого тракту (root path cost).

І нарешті, визначаються призначені мости (designated bridges) і їх призначені порти (designated ports). Призначений міст - це той міст кожної локальної мережі, який забезпечує мінімальні витрати кореневого тракту. Призначений міст локальної мережі є єдиним мостом, який дозволяє просувати блоки даних в ту локальну мережу (і з неї), для якої цей міст є призначеним. Призначений порт локальної мережі - це той порт, який сполучає її з призначеним мостом.

В деяких випадках два або більш мостів можуть мати однакові витрати кореневого тракту. Наприклад, на Мал. 29-3 як Міст 4, так і Міст 5 можуть досягти Міст 1 (кореневий міст) з витратами тракту 10. В цьому випадку знову використовуються ідентифікатори моста, цього разу для визначення назначеных мостів. При виборі перевага віддана порту LAN V Моста 4 перед портом LAN V Моста 5.

При використовуванні цього процесу усуваються всі мости, безпосередньо сполучені з кожною LAN, окрім одного; таким чином, віддаляються всі петлі між двома LAN. STA також усуває петлі, що включають більше двох LAN, в той же час зберігаючи зв'язність. На Мал. 29-4 "Мережа ТБ після прогону STA" показані результати дії STA в мережі, зображеній на Мал. 29-3. На Мал. 29-4 більш чітко показана топологія дерева. Порівняння цього малюнка з малюнком мережі до прогону STA показує, що STA перевів в режим резерву як порти Моста 3 в LAN V, так і порти Moста 5 в LAN V.

Розрахунок зв'язуючого дерева має місце при подачі живлення на міст і у всіх випадках виявлення зміни топології. Для розрахунку необхідний зв'язок між мостами зв'язуючого дерева, який здійснюється через повідомлення конфігурації (іноді звані протокольними інформаційними одиницями моста - bridge protocol data units, або BPDU). Повідомлення конфігурації містять інформацію, що ідентифікує той міст, який вважається кореневим (тобто ідентифікатор кореневого моста), і відстань від моста-відправника до кореневого моста (витрати кореневого тракту). Повідомлення конфігурації також містять ідентифікатори моста і порту моста-відправника, а також вік інформації, що міститься в повідомленні конфігурації.

Мости обмінюються повідомленнями конфігурації через регулярні інтервали часу (звичайні 1-4 сек.). Якщо який-небудь міст відмовляє (викликаючи зміну в топології), то сусідні мости незабаром знаходять відсутність повідомлень конфігурації і ініціюють перерахунок зв'язуючого дерева.

Всі рішення, пов'язані з топологією ТБ, приймаються логічно. Обмін повідомленнями конфігурації проводиться між сусідніми мостами. Центральні повноваження або адміністрація управління мережною топологією відсутні.

Підтримка алгоритму Spanning Tree

Алгоритм Spanning Tree (STA) дозволяє комутаторам автоматично визначати деревовидну конфігурацію зв'язків в мережі при довільному з'єднання портів між собою. Як вже наголошувалося, для нормальної роботи комутатора потрібна відсутність замкнутих маршрутів в мережі. Ці маршрути можуть створюватися адміністратором спеціально для утворення резервних зв'язків або ж виникати випадковим чином, що цілком можливе, якщо мережа має численні зв'язки, а кабельна система погано структурована або документована.

Підтримуючі алгоритм STA комутатори автоматично створюють активну деревовидну конфігурацію зв'язків (тобто зв'язну конфігурацію без петель) на безлічі всіх зв'язків мережі. Така конфігурація називається покриваючим деревом - Spanning Tree (іноді її називають остовным або основним деревом), і її назва дала ім'я всьому алгоритму. Комутатори знаходять покриваюче дерево адаптивний за допомогою обміну службовими пакетами. Реалізація в комутаторі алгоритму STA дуже важлива для роботи у великих мережах - якщо комутатор не підтримує цей алгоритм, то адміністратор повинен самостійно визначити, які порти потрібно перевести в заблокований стан, щоб виключити петлі. До того ж при відмові якому-небудь зв'язку, порту або комутатора адміністратор повинен, по-перше, знайти факт відмови, а, по-друге, ліквідовувати наслідки відмови, перевівши резервний зв'язок в робочий режим шляхом активізації деяких портів.

Основні визначення

В мережі визначається кореневий комутатор (root switch), від якого будується дерево. Кореневий комутатор може бути вибраний автоматично або призначений адміністратором. При автоматичному виборі кореневим стає комутатор з меншим значенням МАС-адреси його блоку управління.

Для кожного комутатора визначається кореневий порт (root port) - це порт, який має по мережі найкоротшу відстань до кореневого комутатора (точніше, до будь-якого з портів кореневого комутатора). Потім для кожного сегменту мережі вибирається так званий призначений порт (designated port) - це порт, який має найкоротшу відстань від даного сегменту до кореневого комутатора.

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

На малюнку 4.12 показаний приклад побудови конфігурації покриваючого дерева для мережі, що складається з 6 сегментів (N1 - N6) і 6 комутаторів (S1 - S6). Кореневі порти закрашені чорним кольором, призначені не закрашені, а заблоковані порти перекреслені. В активній конфігурації комутатори S2 і S6 не мають портів, що передають кадри даних, тому вони закрашені як резервні.

Мал. 4.12. Побудова покриваючого дерева мережі по алгоритму STA

Відстань до кореня визначається як сумарний умовний час на передачу даних від порту даного комутатора до порту кореневого комутатора. При цьому вважається, що час внутрішніх передач даних (з порту на порт) комутатором нехтує мало, а враховується тільки час на передачу даних по сегментах мережі, що сполучають комутатори. Умовний час сегменту розраховується як час, затрачуваний на передачу одного біта інформації в 10-наносекундних одиницях між безпосередньо зв'язаними по сегменту мережі портами. Так, для сегменту Ethernet цей час рівний 10 умовним одиницям, а для сегменту Token Ring 16 Мб/с - 6.25. (Алгоритм STA не пов'язаний з яким-небудь певним стандартом канального рівня, він може застосовуватися до комутаторів, що сполучають мережі різних технологій.)

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

Для автоматичного визначення початкової активної конфігурації дерева всі комутатори мережі після їх ініціалізації починають періодично обмінюватися спеціальними пакетами, званими протокольними блоками даних моста - BPDU (Bridge Protocol Data Unit), що відображає факт первинної розробки алгоритму STA для мостів.

Пакети BPDU поміщаються в полі даних кадрів канального рівня, наприклад, кадрів Ethernet або FDDI. Бажано, щоб всі комутатори підтримували загальну групову адресу, за допомогою якої кадри, що містять пакети BPDU, могли одночасно передаватися всім комутаторам мережі. Інакше пакети BPDU розсилаються широкомовно.

Пакет BPDU має наступні поля:

Ідентифікатор версії протоколу STA - 2 байти. Комутатори повинні підтримувати одну і ту ж версію протоколу STA, інакше може встановитися активна конфігурація з петлями.

Тип BPDU - 1 байт. Існує два типи BPDU - конфігураційний BPDU, тобто заявка на можливість стати кореневим комутатором, на підставі якої відбувається визначення активної конфігурації, і BPDU повідомлення про реконфигурации, яке посилається комутатором, що знайшов подію, що вимагає проведення реконфигурации - відмову лінії зв'язку, відмову порту, зміну пріоритетів комутатора або портів.

Прапори - 1 байт. Один біт містить прапор зміни конфігурації, другий біт - прапор підтвердження зміни конфігурації.

Ідентифікатор кореневого комутатора - 8 байтів.

Відстань до кореня - 2 байти.

Ідентифікатор комутатора - 8 байтів.

Ідентифікатор порту - 2 байти.

Час життя повідомлення - 2 байти. Вимірюється в одиницях по 0.5 з, служить для виявлення застарілих повідомлень. Коли пакет BPDU проходить через комутатор, той додає до часу життя пакету час його затримки даним комутатором.

Максимальний час життя повідомлення - 2 байти. Якщо пакет BPDU має час життя, перевищуючий максимальний, то він ігнорується комутаторами.

Інтервал hello, через який посилаються пакети BPDU.

Затримка зміни станів - 2 байти. Мінімальний час переходу портів комутатора в активний стан. Така затримка необхідна, щоб виключити можливість тимчасового виникнення альтернативних маршрутів при неодночасній зміні станів портів під час реконфигурации.

У пакету BPDU повідомлення про реконфигурации відсутні всі поля, окрім двох перших.

Після ініціалізації кожний комутатор спочатку вважає себе кореневим. Тому він починає через інтервал hello генерувати через все свої порти повідомлення BPDU конфігураційного типу. В них він указує свій ідентифікатор як ідентифікатор кореневого комутатора (і як даний комутатор також), відстань до кореня встановлюється в 0, а як ідентифікатор порту указується ідентифікатор того порту, через який передається BPDU. Як тільки комутатор одержує BPDU, в якому є ідентифікатор кореневого комутатора, менше його власного, він перестає генерувати свої власні кадри BPDU, а починає ретранслювати тільки кадри нового претендента на звання кореневого комутатора. При ретрансляції кадрів він нарощує відстань до кореня, вказану в BPDU, що прийшов, на умовний час сегменту, по якому прийнятий даний кадр.

При ретрансляції кадрів кожний комутатор для кожного свого порту запам'ятовує мінімальну відстань до кореня, що зустрілася у всіх прийнятих цим портом кадрах BPDU. При завершенні процедури встановлення конфігурації покриваючого дерева (за часом) кожний комутатор знаходить свій кореневий порт - це порт, який ближче за інші порти знаходиться по відношенню до кореня дерева. Окрім цього, комутатори розподіленим чином вибирають для кожного сегменту мережі призначений порт. Для цього вони виключають з розгляду свій кореневий порт, а для всіх своїх портів, що залишилися, порівнюють прийняті по них мінімальні відстані до кореня з відстанню до кореня свого кореневого порту. Якщо у свого порту ця відстань менше прийнятих, то це значить, що він є призначеним портом. Всі порти, окрім призначених переводяться в заблокований стан і на цьому побудову покриваючого дерева закінчується.

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

Способи управління потоком кадрів

Деякі виробники застосовують в своїх комутаторах прийоми управління потоком кадрів, відсутні в стандартах протоколів локальних мереж, для запобігання втрат кадрів при перевантаженнях.

Мал. 4.13. Чергування передач кадрів при обміні даними через комутатор

На малюнку 4.13 приведений приклад обміну кадрами між комутатором і портом мережного адаптера комп'ютера в режимі пікового завантаження комутатора. Комутатор не встигає передавати кадри з буфера передавача Tx, оскільки при нормальному напівдуплексному режимі роботи передавач повинен частина часу простоювати, чекаючи, поки приймач не прикмет черговий кадр від комп'ютера.

Оскільки втрати, навіть невеликої частки кадрів, звичайно набагато знижують корисну продуктивність мережі, то при перевантаженні комутатора раціонально б уповільнити інтенсивність надходження кадрів від кінцевих вузлів в приймачі комутатора, щоб дати можливість передавачам розвантажити свої буфера з більш високою швидкістю. Алгоритм чергування передаваних і приймаються кадрів (frame interleave) повинен бути гнучким і дозволяти комп'ютеру в критичних ситуаціях на кожний кадр, що приймається, передавати дещо своїх, причому не обов'язково знижуючи при цьому інтенсивність прийому до нуля, а просто зменшуючи її до необхідного рівня.

Для реалізації такого алгоритму у розпорядженні комутатора повинен бути механізм зниження інтенсивності трафіку підключених до його портів вузлів. У деяких протоколів локальних мереж, таких як FDDI, Token Ring або 100VG-AnyLAN є можливість змінювати пріоритет порту і тим самим давати порту комутатора перевагу перед портом комп'ютера. У протоколів Ethernet і Fast Ethernet такої можливості немає, тому виробники комутаторів для цих дуже популярних технологій використовують два прийоми дії на кінцеві вузли.

Ці прийоми засновані на тому, що кінцеві вузли строго дотримують всі параметри алгоритму доступу до середовища, а порти комутатора - ні.

Перший спосіб "гальмування" кінцевого вузла заснований на так званій агресивній поведінці порту комутатора при захопленні середовища після закінчення передачі чергового пакету або після колізії. Ці два випадки ілюструються малюнком 4.14.

Мал. 4.14. Агресивна поведінка комутатора при перевантаженнях буферів

В першому випадку комутатор закінчив передачу чергового кадру і замість технологічної паузи в 9.6 мкс зробив паузу в 9.1 мкс і почав передачу нового кадру. Комп'ютер не зміг захопити середовище, оскільки він витримав стандартну паузу в 9.6 мкс і знайшов після цього, що середовище вже зайнято.

В другому випадку кадри комутатора і комп'ютера зіткнулися і була зафіксована колізія. Оскільки комп'ютер зробив паузу після колізії в 51.2 мкс, як це встановлено за стандартом (інтервал відстрочення рівний 512 бітових інтервалів), а комутатор - 50 мкс, то і в цьому випадку комп'ютеру не вдалося передати свій кадр.

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

Другий прийом, яким користуються розробники комутаторів - це передача фіктивних кадрів комп'ютеру у тому випадку, коли у комутатора немає в буфері кадрів для передачі по даному порту. В цьому випадку комутатор може і не порушувати параметри алгоритму доступу, чесно змагавшися з кінцевим вузлом за право передати свій кадр. Оскільки середовище при цьому рівноімовірно діставатися в розпорядження то комутатору, то кінцевому вузлу, то інтенсивність передачі кадрів в комутатор в середньому зменшиться удвічі. Такий метод називається методом зворотного тиску (backpressure). Він може комбінуватися з методом агресивного захоплення середовища для більшого придушення активності кінцевого вузла.

Метод зворотного тиску використовується не для того, щоб розвантажити буфер процесора порту, безпосередньо пов'язаного з пригнічуваним вузлом, а розвантажити або загальний буфер комутатора (якщо використовується архітектура із загальною пам'яттю, що розділяється), або розвантажити буфер процесора іншого порту, в який передає свої кадри даний порт. Крім того, метод зворотного тиску може застосовуватися в тих випадках, коли процесор порту не розрахований на підтримку максимально можливого для протоколу трафіку. Один з перших прикладів вживання методу зворотного тиску якраз пов'язаний з таким випадком - метод був застосований компанією LANNET в модулях LSE-1 і LSE-2, розрахованих на комутацію трафіку Ethernet з максимальною інтенсивністю відповідно 1 Мб/с і 2 Мб/с.

Можливості комутаторів по фільтрації трафіку

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

Якщо комутатор не підтримує протоколи мережного і транспортного рівнів, в яких є поля, вказуючі до якого сервісу відносяться передавані пакети, то адміністратору доводиться для завдання умов інтелектуальної фільтрації визначати поле, по значенню якого потрібно здійснювати фільтрацію, у вигляді пари "зсув-розмір" щодо початку поля даних кадру канального рівня. Тому, наприклад, для того, щоб заборонити деякому користувачу друкувати свої документи на певному принт-сервері NetWare, адміністратору потрібно знати положення поля "номер сокета" в пакеті IPX і значення цього поля для принт-сервісу, а також знати МАС-адреси комп'ютера користувача і принт-серверу.

Звичайно умови фільтрації записуються у вигляді булевих виразів, формованих за допомогою логічних операцій AND і OR.

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

Окрім умов загального вигляду комутатори можуть підтримувати спеціальні умови фільтрації. Одним з дуже популярних видів спеціальних фільтрів є фільтри, що створюють віртуальні сегменти. Вони розглядаються в розділі 4.3.7 окремо з причини їх особливого значення.

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

Лабораторна робота №6. Налагодження комутаторів.

Лабораторна робота №7. Створення проекту мережі на базі технології Ethernet.