НОУ ІНТУІТ, Лекція, Алгоритми мережі Ethernet

У цьому розділі пропонується докладно розглянути два основні алгоритми, що застосовуються у найпоширенішій сьогодні мережі Ethernet/Fast Ethernet. Йдеться про метод управління обміном (доступу) CSMA/CD і про метод обчислення циклічної контрольної суми (перешкодостійкого циклічного коду) пакета CRC.

Ці самі алгоритми використовуються в багатьох інших локальних мережах. Наприклад, метод доступу CSMA/CD застосовується в мережах IBM PC Network, AT&T Starlan, Corvus Omninet, PC Net, G-Net та ін. Якщо говорити про алгоритм обчислення циклічної контрольної суми CRC, то він став фактичним стандартом для будь-яких локальних мереж . Таким чином, все, що представлено в цьому розділі, відноситься до багатьох локальних мереж.

Метод керування обміном CSMA/CD

Як мовилося раніше у розділі 3, метод управління обміном CSMA /CD ( Carrier - Sense Multiple Access with Collision Detection – множинний доступ із контролем несучої та виявленням колізій ) належить до децентралізованим випадковим (точніше, квазівипадковим) методам. Він використовується як у звичайних мережах типу Ethernet, так і у високошвидкісних мережах (Fast Ethernet, Gigabit Ethernet). Оскільки характеристики та сфери застосування цих популярних на практиці мереж пов'язані саме з особливостями використовуваного методу доступу, його варто розглянути докладніше.

Спочатку про назву методу. У ранній мережі типу Alohanet, що працювала з 1970 р. на Гавайських островах, використовувався радіоканал і встановлений на супутнику ретранслятор (звідси слово "несуча" в назві методу), а також порівняно простий метод доступу CSMA (без виявлення колізій). У мережах типу Ethernet і Fast Ethernet як несучий виступає синхросигнал, "підмішується"до даних таким чином, щоб забезпечити надійну синхронізацію на приймальному кінці. Це реалізується за рахунок організації (за потреби) додаткових примусових переходів сигналу між двома (як у коді Манчестер-II) або трьома електричними рівнями (як у коді типу 8В6Т, що використовується в сегменті Fast Ethernet 100BaseT4 на основі чотирьох неекранованих кручених пар). Порівняно з класичним методом CSMA у методі CSMA /CD додано виявлення конфліктів (колізій) під час передачі, що підвищує швидкість доставки інформації.

При описі тимчасових діаграм мереж типу Ethernet і Fast Ethernet, а також граничних розмірів пакетів (кадрів) широко використовуються такі терміни:

  • IPG (interpacket gap, міжпакетна щілина) – мінімальний проміжок часу між пакетами, що передаються (9,6 мкс для Ethernet / 0,96 мкс для Fast Ethernet). Інша назва – міжкадровий інтервал.
  • ВТ (Bit Time, час біта) – інтервал часу передачі одного біта (100 нс для Ethernet / 10 нс для Fast Ethernet).
  • PDV (Path Delay Value, значення затримки у дорозі) – час проходження сигналу між двома вузлами мережі (круговий, тобто подвоєний). Враховує сумарну затримку у кабельній системі, мережевих адаптерах, повторювачах та інших мережних пристроях.
  • Collision window (вікно колізій) – максимальне значення PDV для цього сегмента.
  • Collision domain (область колізій, зона конфлікту) - частина мережі, на яку поширюється ситуація колізії, конфлікту.
  • Slot time (час каналу) – максимально допустиме вікно колізій для сегмента (512 ВТ).
  • Minimum frame size – мінімальний розмір кадру (512 біт).
  • Maximum frame size - максимальний розмір кадру (1518 байт).
  • Maximum network diameter(максимальний діаметр мережі) -максимальна допустима довжина сегмента, коли він його вікно колізій вбирається у slot time , часу каналу.
  • Truncated binary exponential back off (усічена двійкова експоненційна відстрочка) – затримка перед наступною спробою передачі пакета після колізії (допускається максимум 16 спроб). Обчислюється вона за такою формулою:

RAND(0,2 min(N,10) ) x 512 x ВТ

де N – значення лічильника спроб, RAND(a, b) – генератор випадкових нормально розподілених цілих чисел діапазоні а. b, включаючи крайні значення. Дискрет зміни даного параметра дорівнює мінімальній довжині пакета або максимально допустимої подвійної затримки розповсюдження сигналу в мережі (PDV).

Алгоритм доступу до мережі

На рис. 10.1 показано структурну схему алгоритму доступу до мережі відповідно до методу CSMA /CD для одного з абонентів, що мають дані (кадри) для передачі.

На початку кадру, призначеного передачі, абонент (вузол) формує пакет. p align="justify"> Далі при позначенні блоків інформації, що передаються по мережі при використанні алгоритму CSMA / CD, поняття "кадр" і "пакет" не різняться, що не зовсім правильно, але відповідає практиці, що склалася.

Якщо після підготовки пакета мережа вільна, абонент (вузол) має право розпочати передачу. Але в першу чергу він повинен перевірити, чи минув мінімально допустимий час IPG після попередньої передачі (блок 1 малюнку). Тільки після закінчення часу IPG абонент може розпочати передачу бітів свого пакета (блок 2 малюнку).

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

Якщо після передачі якогось біта виявлено колізію, то передача пакета припиняється. Абонент (вузол) посилює колізію , передаючи 32-бітовий сигнал ПРОБКА ( JAM ) і починає готуватися до наступної спроби передачі (блок 3 малюнку). Сигнал ПРОБКА гарантує, що наявність колізії виявлять усі абоненти, що беруть участь у конфлікті.

Після передачі сигналу ПРОБКА абонент, який виявив колізію, збільшує значення лічильника числа спроб (перед початком передачі лічильник був скинутий в нуль). Максимальна кількість спроб передачі має бути не більше 16, тому якщо лічильник спроб переповнився, спроби передати пакет припиняються. Вважається, що в цьому випадку мережа сильно перевантажена, в ній дуже багато колізій. Ця ситуація – аварійна, і обробляється на більш високих рівнях протоколів обміну.

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

лекція

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