Из за чего происходят коллизии

Коллизии HashCode

Представьте, вы пишите мессенжер или почтовый клинт. Вам придется работать с кучей повторяющихся строковых значений. Например в чате — какой-то влюбленный Вася может спамить десятки аналогичных признаний в любви своей даме сердца Насте. Но мы то знаем, что все Насти шлю** Наверняка мы захотим как-то кэшировать эти сообщения. Для этого подойдет HashMap или HashSet, например. Все знают, что эти структуры данных, ссылаются на хэш значение объекта, которое не бесконечно, а ограничено 32 битами. Но проблемы могут начаться уже с пары строк.

Пример такой коллизии:

Вообще если длина строк одинаковая и выполняется:

то, хэши всегда будут одинаковыми, не буду вдаваться в подробности почему так 😀

Окей, хэши могут быть одинаковыми на ровном месте, но по какому принципу они рассчитываются?

Стандартная реализация hashCode

Посмотри сгенерированный idea hashCode() для простого POJO класса.

У String, кстати свой алгоритм: h(s)=∑(s[index] * 31 ^(n-1-index)) Смысл тот же, только проходим по всем char

Как вы заметили везде используется это непонятное число 31. Вопрос: А че не 41 или 97, например?

А по каким критериям оно отбирается?

• Число должно быть простым и нечетным, чтобы уменьшить вероятность коллизий.
• Число должно занимать мало места в памяти
• Умножение должно выполняться быстро

Оказывается 31 идеальный кандидат ведь:

• Оно простое и нечетное
• Занимает всего 1 байт в памяти
• Уго умножение можно заменить на быстрый побитовой сдвиг. 31 * i == (i << 5) — i

PS: А че за (i << x) — i ?

Побитовой сдвиг влево на x позиций. Работает точно также как умножить какое-то число на 2 x раз.

Вернемся к сути.

Окей, выяснили, по какому принципу считается HashCode и что в любой момент может произойти коллизия и данные перетрутся. Так че делать?

Да ничего, HashMap и HashSet самоcтоятельно обрабытывают такие ситуации. Важно только правильно переопределить метод equals(o) у класса.

Логика работы такая:

Кладем в список объект по ключу “cat”

Кладем в него другой по этому же ключу

HashMap/Set проверяет равны ли эти объекты в методе equals

Если равны — заменяет, если нет, создает в этой ячейке связный список, а например в седьмой джаве бакет в HashMap, при появлении в нём более семи объектов, меняет начинку со связного списка на дерево.

Важно помнить, что получение элемента из связного списка работает за время O(n), и если колиизий наберется много, скорость hash таблицы станет уже далеко не константной.

Поэтому если все же решили использовать String в качестве ключа, можно за основу брать 2 простых числа, скажем 17 и 37. Ребята из Project Lombok придумали здесь

Минуточку

Переопределил я hashCode() , но как-же теперь JVM узнает, на какой адрес в памяти ссылается этот объект?

На самом деле у каждого объекта есть идентификационный хеш (identity hash code). Если класс переопределил hashCode() , всегда можно вызвать System.identityHashCode(o) .

Да и вообще, hashCode() не возвращает какой-либо адрес объекта в памяти, что бы это не значило. В версиях java 6 и 7 это случайно генерируемое число. В версиях 8 и 9 это число, полученное на основании состояния потока. Подробнее об этом можно почитать здесь

Почему возникают коллизии?

Как известно, ситуация, когда у разных объектов одинаковые хеш-коды называется — коллизией. Вероятность возникновения коллизии зависит от используемого алгоритма генерации хеш-кода.

Но вот вопрос, почему она возникает? Неужели тяжко придумать «защиту» от возникновения коллизии? Кто что думает?

Хеш код в java создается методом

У integer диапазон от -2147483648 до 2147483647, т.е. округлив получаем 4 миллиарда разных целых чисел.

А теперь представим ситуацию, у вас 8-10 миллиардов объектов. Вопрос: как каждому из них дать уникальный хеш код используя диапазон в 4 миллиарда?

При этом вы не знаете сколько объектов вашего класса могут создать пользователи.

Если ваш класс будет использоваться в Hash структурах как ключ, вы так же должны постараться обеспечить объекты такими хеш кодами, чтобы они попадали в разные корзины и получить равномерное заполнение структуры.

Box2d: анатомия коллизий

В Box2D принято считать, что друг с другом сталкиваются тела, однако на самом деле при расчете коллизий используются фикстуры (fixtures, переводы слова существуют, но я не уверен, есть ли среди них устоявшийся). Объекты могут сталкиваться разными способами, поэтому библиотека предоставляет большое количество уточняющей информации, которая может быть использована в игровой логике. Например, вы можете захотеть узнать следующее:

• Когда столкновение начинается и заканчивается
• Точку соприкосновения фикстур
• Вектор нормали к линии контакта фикстур
• Какая энергия была приложена и результат коллизии

Все настроено таким образом, чтобы нижняя часть треугольника столкнулась с верхним углом квадрата. Тонкости реализации этого процесса выходят за рамки статьи — основное внимание уделим тому, какую информацию можно извлечь на каждом этапе столкновения. Если есть желание самостоятельно запустить предлагаемый пример, исходный код прилагается.

Получении информации о столкновении

Информация о столкновении содержится в объекте типа b2Contact. Из него можно узнать, какие именно фикстуры сталкиваются, и определить их положение и направление результирующих импульсов. Существует два способа получения объектов b2Contact в Box2D. Первый — перебрать текущий список контактов каждого тела объекта, второй — использовать слушатель контактов. Рассмотрим каждый из них, чтобы дальше было понятнее, о чем идет речь.

Проверка списка контактов

В любой момент можно перебрать все контакты мира (имеется в виду b2World)

или получить контакты тела определенного объекта

Если выбран этот подход, очень важно помнить, что наличие контакта в этих списках не означает, что фикстуры соприкасаются — это значит только, что пересекаются их AABB. Если требуется убедиться, что контактируют сами фикстуры, воспользуйтесь методом IsTouching(). К этому вопросу мы еще вернемся.

Слушатели контактов

Проверка списка контактов становится неэффективной в ситуациях, когда столкновения происходят часто и в больших количествах. Устанавливая слушателей контактов, вы отдаете поручение Box2D сообщать, когда происходит что-то интересное, вместо того, чтобы вручную следить за началом и завершением столкновений. Слушатель контактов — это объект класса b2ContactListener, часть функций которого замещается при необходимости.

Должен заметить, что в зависимости от ситуации, некоторые события дают нам не только объект b2Contact. В процессе выполнения функции Step, когда Box2D определяет, что произошел контакт, он выполняет обратный вызов определенных функций слушателя, чтобы уведомить вас. Практическое использование «обратных вызовов при коллизиях» рассматривается в отдельной статье. Здесь мы все внимание сосредоточим на том, что можно узнать, обрабатывая события столкновений.

В общем случае я рекомендую метод слушателей контактов. На первый взгляд он может показаться несколько неуклюжим, однако он более эффективен и полезен в долгосрочной перспективе. До сих пор мне не встречалась ситуация, когда проверка списка контактов давала бы ощутимый выигрыш.

Вне зависимости от способа получения контактов, они содержат одинаковую информацию. Наиболее важные данные о пересекающихся фикстурах можно получить так

Когда происходит обход списка контактов определенного объекта, возможно, одна из фикстур коллизии известна, но если используется слушатель контактов, придется полностью положиться на эти функции, чтобы понять, что с чем сталкивается. Четко заданного порядка фикстур не существует, так что часто приходится устанавливать пользовательские данные (user data), чтобы понять, какому именно объекту принадлежит фикстура или тело. Располагая объектом фикстуры, можно воспользоваться методом GetBody(), чтобы получить ссылку на тело.

Столкновение шаг за шагом.

Теперь давайте подробнее рассмотрим последовательность событий, происходящих при столкновении. Надеюсь, картинок с описанием каждого шага будет достаточно для понимания материала. Возможно, вы захотите загрузить исходники к уроку, чтобы запускать их во время чтения. Тестовая программа позволяет ставить симуляцию на паузу, перезапускать и выполнять ее по шагам.

Начнем с ситуации, когда AABB фикстур не пересекаются, так мы сможет проследить историю полностью. Кликните флажок «AABBs», чтобы увидеть фиолетовые прямоугольные области вокруг каждой фикстуры.

AABB фикстур начинают перекрываться

Несмотря на то, что сами фикстуры еще не пересеклись, на этом этапе уже создается экземпляр b2Contact и добавляется в список контактов мира и списки каждого тела. Если вы просматриваете эти списки, то по наличию объектов b2Contact можно судить о том, что в принципе контакт возможен, хотя фикстуры не обязательно пересеклись.

Результат: контакт существует, но IsTouching() возвращает ложь

Продолжаем симуляцию, пока не пересекутся непосредственно фикстуры…

Фикстуры начинают пересекаться.

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

Шаг n

Шаг n+1 (не bullet-объекты)

Все это происходит за один шаг симуляции, значит, реальную точку пересечения (к которой ведет пунктирная линия на рисунке выше), мы проскочили. Это происходит потому, что Box2D сначала смещает все тела и только потом проверяет пересечения, по крайней мере, это его поведение по умолчанию. Если вам нужна реальная точка соприкосновения, то нужно сделать следующее

Шаг n+1 (треугольник — bullet-объект)

Bullet-тела, расходуют больше процессорного времени на расчеты и для большинства приложений не требуются. Просто помните о том, что при обычных настройках, иногда коллизии могут пропускаться — в нашем примере, если бы треугольник двигался достаточно быстро, он мог бы пролететь сквозь угол квадрата, не инициировав столкновения. Если у вас есть очень быстро перемещающиеся тела, контакты которых не должны пропускаться, например, мммм… пули 🙂 тогда их нужно объявлять как bullet-объекты. Дальнейшее изложение будет вестись для не-bullet-тел.

• IsTouching() возвращает истину
• Срабатывает функция обратного вызова BeginContact

Точки столкновения и нормаль

К этому моменту в нашем контакте присутствует реальное соприкосновение, что дает возможность ответить не некоторые вопросы в начале статьи. Для начала давайте получим нормаль и точку касания. Предполагается, что приведенный далее код вызывается или из метода BeginContact слушателя контактов или из вашего метода после предварительного получения контакта из списка.

Объект контакта содержит информацию о коллизии в локальных координатах тел сталкивающихся объектов, а это не совсем то, что нам нужно. Однако можно запросить у контакта более полезную структуру b2WorldManifold, которая содержит позицию коллизии в мировых координатах.

Полученные точки будут использованы Box2D для расчета реакции на столкновение для вычисления импульса, который направит фикстуры в противоположные стороны. Это будут неточные места соприкосновения фикстур (если только вы не использовали bullet-объекты), хотя на практике их обычно достаточно для расчетов столкновений в игровой логике.

Далее рассмотрим нормаль коллизии, которая направлена от фикстуры A к B:

Похоже на то, что для этого столкновения самый быстрый способ избавиться от перекрывающихся объектов, это оттолкнуть угол треугольника вверх и влево, а квадрата — вниз и вправо. Хотелось бы обратить ваше внимание на то, что нормаль — это просто направление, она не привязана ни к какой точке контакта — я изобразил ее проходящей через points[0] для удобства.

Важно также помнить, что нормаль столкновения не определяет угол между фикстурами (ведь треугольник двигается вообще горизонтально) — она лишь задает направление, следуя которому быстрее всего компенсируется перекрытие объектов. Например, представьте, что треугольник двигается немного быстрее, и перекрытие выглядит так:

Тогда самый быстрый способ разделить фикстуры — оттолкнуть треугольник вверх и вправо. Так что использовать нормаль для расчета угла между объектами нецелесообразно. Если требуется узнать направления, по которым будут разделяться фигуры, можно воспользоваться следующим кодом:

Он позволит получить относительную скорость реакции всех точек столкнувшихся тел. В нашем простом случае можно было бы ограничиться линейной скоростью треугольника, так как известно, что квадрат неподвижен, а треугольник не вращается. Но вышеуказанный код будет учитывать и случаи, когда оба дела движутся или вращаются.

Также нужно заметить, что не при каждом столкновении будет именно две точки коллизии. Я намерено остановился на достаточно сложном примере, когда перекрываются два угла многоугольников, но чаще бывает только одна такая точка. Вот несколько примеров столкновений, для которых достаточно одной точки

Итак, только что мы рассмотрели, как определить точки и нормаль коллизии, на основе которых Box2D будет рассчитывать реакцию, направленную на компенсацию перекрытий. Теперь вернемся к последовательности событий.

Реакция на столкновение

( (b2Contact::Update, b2Island::Report))
Шаг_столкновения

Шаг_столкновения + 1

Шаг_столкновения + 1

Когда фикстуры перекрываются, реакция Box2d по умолчанию — приложить импульс к каждой из них, чтобы направить в разные стороны. Однако это не всегда удается сделать за один шаг моделирования. Как показано на рисунках для нашего примера, две фикстуры будут перекрываться на протяжении трех шагов, пока отскок не состоится, и они окончательно не разделятся.

В это время мы можем вмешаться и настроить поведение модели, как нам захочется. Если используется подход со слушателем контактов, методы PreSolve и PostSolve будут вызываться на каждом шаге, пока фикстуры перекрываются, давая возможность модифицировать контакт перед тем, как он будет обработан стандартными средствами реакции на коллизию (PreSolve), и узнать, какие импульсы были приложены Box2D (PostSolve)

Для большей наглядности приведу вывод printf, которая помещена в в функцию Step и каждый метод слушателя контактов:

Результат: PreSolve and PostSolve вызываются несколько раз

PreSolve and PostSolve

Оба эти метода получают в качестве параметра указатель на b2Contact, так что мы имеем доступ к той же информации о точках и нормалях, что и в BeginContact. PreSolve дает на возможность изменить характеристики контакта перед расчетом реакции на столкновение и даже отменить реакцию полностью. PostSolve позволяет получить информацию о вычисленной реакции.

В PreSolve можно сделать следующие настройки объекта контакта:

Вызов SetEnabled(false) деактивирует контакт, значит, реакция на столкновение просчитываться не будет. Это может понадобиться, когда необходимо временно позволить объектам пролетать друг сквозь друга. Классический пример — односторонняя стена или платформа, когда игрок может пройти сквозь обычно непроходимый объект при определенных условиях, которые можно проверить только во время выполнения — например, позиция игрока или направление его движения.

Важно помнить, что на следующей итерации контакт снова активируется, так что если нужно отключить его на продолжительное время, придется делать это на каждом шаге.

Кроме ссылки на контакт, PreSolve содержит второй параметр, из которого можно получить характеристики коллизии (точки и нормаль) с предыдущего шага моделирования. Если кто-то знает, зачем это может пригодиться — расскажите мне 😀

PostSolve вызывается после того, как реакция на столкновение была рассчитана и применена. У метода есть второй параметр, содержащий информацию о приложенном в результате импульсе. Обычно он используется для проверки, не превысила ли реакция некоторое пороговое значения, в результате чего объект можно разрушить и т.п. В статье » sticky projectiles» содержится пример использования функции PostSolve для определения, должна ли стрела застревать в мишени.

Возвращаемся к сценарию столкновения

Фикстуры больше не перекрываются

(b2Contact::Update)
AABB все еще перекрываются, так что контакт пока остается в соответствующих списках мира и тела.

(увеличенный масштаб)

• Вызывается EndContact
• IsTouching() возвращает ложь

AABB фикстур не перекрываются

(b2ContactManager::Collide)

Результат: контакт удаляется из списка контактов мира и тела.

Метод EndContact получает указатель на b2Contact, когда фикстуры уже не соприкасаются, так что в нем уже не содержится актуальной информации. Тем не менее EndContact является неотъемлемым элементом слушателя контактов, так как позволяет контролировать, когда игровые объекты покидают зону соприкосновения.

Возникновение коллизии

При описанном подходе возможна ситуация, когда две станции одновременно пы­таются передать кадр данных по общей среде. Механизм прослушивания среды и пауза между кадрами не гарантируют от возникновения такой ситуации, когда две или более станции одновременно решают, что среда свободна, и начинают переда­вать свои кадры. Говорят, что при этом происходит коллизия (collision), так как содержимое обоих кадров сталкивается на общем кабеле и происходит искажение информации — методы кодирования, используемые в Ethernet, не позволяют выде­лять сигналы каждой станции из общего сигнала.

ПРИМЕЧАНИЕ Заметим, что этот факт отражен в составляющей ТBase, присутствующей в названиях всех физичес­ких протоколов технологии Ethernet (например, lOBase-2, lOBase-T и т. п.). Baseband network означает сеть с немодулированной передачей, в которой сообщения пересылаются в цифровой форме по единственно­му каналу, без частотного разделения.

Коллизия — это нормальная ситуация в работе сетей Ethernet. В примере, изоб­раженном на рис. 3.4, коллизию породила одновременная передача данных узла­ми. Для возникновения коллизии не обязательно, чтобы несколько станций начали передачу абсолютно одновременно, такая ситуация маловероятна. Гораздо вероятней, что коллизия возникает из-за того, что один узел начинает передачу раньше другого, но до второго узла сигналы первого просто не успевают дойти к тому времени, когда второй узел решает начать передачу своего кадра. То есть коллизии — это следствие распределенного характера сети.

Чтобы корректно обработать коллизию, все станции одновременно наблюдают за возникающими на кабеле сигналами. Если передаваемые и наблюдаемые сигна­лы отличаются, то фиксируется обнаружение коллизии (collision detection, CD). Для Увеличения вероятности скорейшего обнаружения коллизии всеми станциями сети станция, которая обнаружила коллизию, прерывает передачу своего кадра (в про­извольном месте, возможно, и не на границе байта) и усиливает ситуацию кол­лизии посылкой в сеть специальной последовательности из 32 бит, называемой Jam-последовательностью.

Рис. 3.4. Схема возникновения и распространения коллизии

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

Пауза = L х (интервал отсрочки),

где интервал отсрочки равен 512 битовым интервалам (в технологии Ethernet принято все интервалы измерять в битовых интервалах; битовый интервал обозначй ся как bt и соответствует времени между появлением двух последовательных данных на кабеле; для скорости 10 Мбит/с величина битового интервала 0,1 мкс или 100 );

L представляет собой целое число, выбранное с равной вероятностью из диапазона О, 2, где N — номер повторной попытки передачи данного кадра: 1,2. 10.

После 10- опытки интервал, из которого выбирается пауза. Таким образом, случайная пауза может принимать значения от 0 до 52,4 мс.

Если 16 последовательных попыток передачи кадра вызывают коллизию, передатчик должен прекратить попытки и отбросить этот кадр. Из описания метода доступа видно, что он носит вероятностный характер вероятность успешного получения в свое распоряжение общей среды зависит от загруженности сети, то есть от интенсивности возникновения в станциях потребности в передаче кадров. При разработке этого метода в конце 70-х годов предполагалось, что скорость передачи данных в 10 Мбит/с очень высока по сравнений потребностями компьютеров во взаимном обмене данными, поэтому загрузка будет всегда небольшой. Это предположение остается иногда справедливым и по сей день, однако уже появились приложения, работающие в реальном масштабе времени с мультимедийной информацией, которые очень загружают сегменты Ethernet. При этом коллизии возникают гораздо чаще. При значительной интен­сивности коллизий полезная пропускная способность сети Ethernet резко падает, так как сеть почти постоянно занята повторными попытками передачи кадров. Для уменьшения интенсивности возникновения коллизий нужно либо уменьшить трафик, сократив, например, количество узлов в сегменте или заменив приложе­ния, либо повысить скорость протокола, например перейти на Fast Ethernet.

Следует отметить, что метод доступа CSMA/CD вообще не гарантирует стан­ции, что она когда-либо сможет получить доступ к среде. Конечно, при небольшой загрузке сети вероятность такого события невелика, но при коэффициенте исполь­зования сети, приближающемся к 1, такое событие становится очень вероятным. Этот недостаток метода случайного доступа — плата за его чрезвычайную простоту, которая сделала технологию Ethernet самой недорогой. Другие методы доступа — маркерный доступ сетей Token Ring и FDDI, метод Demand Priority сетей 100VG-AnyLAN — свободны от этого недостатка.

Время двойного оборота и распознавание коллизий

Четкое распознавание коллизий всеми станциями сети является необходимым ус­ловием корректной работы сети Ethernet. Если какая-либо передающая станция не распознает коллизию и решит, что кадр данных ею передан верно, то этот кадр данных будет утерян. Из-за наложения сигналов при коллизии информация кадра исказится, и он будет отбракован принимающей станцией (возможно, из-за несов­падения контрольной суммы). Скорее всего, искаженная информация будет по­вторно передана каким-либо протоколом верхнего уровня, например транспортным или прикладным, работающим с установлением соединения. Но повторная передача сообщения протоколами верхних уровней произойдет через значительно более дли­тельный интервал времени (иногда даже через несколько секунд) по сравнению с микросекундными интервалами, которыми оперирует протокол Ethernet. Поэтому если коллизии не будут надежно распознаваться узлами сети Ethernet, то это при­ведет к заметному снижению полезной пропускной способности данной сети.

Для надежного распознавания коллизий должно выполняться следующее соот­ношение:

Tmin — время передачи кадра минимальной длины, a PDV — время, за которое сигнал коллизии успевает распространиться до самого дальнего узла сети. Так как в худшем случае сигнал должен пройти дважды между наиболее удаленными друг от друга станциями сети (в одну сторону проходит неискаженный сигнал, а на обратном пути распространяется уже искаженный коллизией сигнал), то это вре­мя называется временем двойного оборота (Path Delay Value, PDV).

При выполнении этого условия передающая станция должна успевать обнару­жить коллизию, которую вызвал переданный ее кадр, еще до того, как она закончит передачу этого кадра.

Очевидно, что выполнение этого условия зависит, с одной стороны, от длины Минимального кадра и пропускной способности сети, а с другой стороны, от длины

кабельной системы сети и скорости распространения сигнала в кабеле (для разных типов кабеля эта скорость несколько отличается).

Все параметры протокола Ethernet подобраны таким образом, чтобы при нор­мальной работе узлов сети коллизии всегда четко распознавались. При выборе параметров, конечно, учитывалось и приведенное выше соотношение, связываю­щее между собой минимальную длину кадра и максимальное расстояние между станциями в сегменте сети.

В стандарте Ethernet принято, что минимальная длина поля данных кадра со- ставляет 46 байт (что вместе со служебными полями дает минимальную длину кадра 64 байт, а вместе с преамбулой — 72 байт или 576 бит). Отсюда может быть определено ограничение на расстояние между станциями.

Итак, в 10-мегабитном Ethernet время передачи кадра минимальной длины pas но 575 битовых интервалов, следовательно, время двойного оборота должно быть меньше 57,5 мкс. Расстояние, которое сигнал может пройти за это время, зависит ( типа кабеля и для толстого коаксиального кабеля равно примерно 13 280 м. Учип вая, что за это время сигнал должен пройти по линии связи дважды, расстояи между двумя узлами не должно быть больше 6 635 м. В стандарте величина этой расстояния выбрана существенно меньше, с учетом других, более строгих ограничение

Одно из таких ограничений связано с предельно допустимым затуханием сигнала. Для обеспечения необходимой мощности сигнала при его прохождении между наиболее удаленными друг от друга станциями сегмента кабеля максимальная длина непрерывного сегмента толстого коаксиального кабеля с учетом вносимого затухания выбрана в 500 м. Очевидно, что на кабеле в 500 м условия распознавай коллизий будут выполняться с большим запасом для кадров любой стандарта длины, в том числе и 72 байт (время двойного оборота по кабелю 500 м составляет всего 43,3 битовых интервала). Поэтому минимальная длина кадра могла бы быть установлена еще меньше. Однако разработчики технологии не стали уменьшать и нимальную длину кадра, имея в виду многосегментные сети, которые строятся из нескольких сегментов, соединенных повторителями.

Повторители увеличивают мощность передаваемых с сегмента на сегмент сигналов, в результате затухание сигналов уменьшается и можно использовать гораздо большей длины, состоящую из нескольких сегментов. В коаксиальных линиях Ethernet разработчики ограничили максимальное количество сегментов в сети пятью, что в свою очередь ограничивает общую длину сети 2500 метров. Даже в такой многосегментной сети условие обнаружения коллизий по-прежнему выполняется с большим запасом (сравним полученное из условия допустимого затухания расстояние в 2500 м с вычисленным выше максимально возможны) времени распространения сигнала расстоянием 6635 м). Однако в действительности временной запас является существенно меньше, поскольку в многосегменых сетях сами повторители вносят в распространение сигнала дополнительную задерэ в несколько десятков битовых интервалов. Естественно, небольшой запас был также для компенсации отклонений параметров кабеля и повторителей.

В результате учета всех этих и некоторых других факторов было тщательно подобрано соотношение между минимальной длиной кадра и максимально возможным расстоянием между станциями сети, которое обеспечивает надежное распо вание коллизий. Это расстояние называют также максимальным диаметром с

С увеличением скорости передачи кадров, что имеет место в новых стандартов, базирующихся на том же методе доступа CSMA/CD, например Fast Ethernet.

Максимальное расстояние между станциями сети уменьшается пропорционально уве­личению скорости передачи. В стандарте Fast Ethernet оно составляет около 210 м, а в стандарте Gigabit Ethernet оно было бы ограничено 25 метрами, если бы разра­ботчики стандарта не предприняли некоторых мер по увеличению минимального размера пакета.

В табл. 3.1 приведены значения основных параметров процедуры передачи кад­ра стандарта 802.3, которые не зависят от реализации физической среды. Важно отметить, что каждый вариант физической среды технологии Ethernet добавляет к этим ограничениям свои, часто более строгие ограничения, которые также должны выполняться и которые будут рассмотрены ниже.

Таблица 3.1. Параметры уровня MAC Ethernet

3.3.2. Максимальная производительность сети Ethernet

Количество обрабатываемых кадров Ethernet в секунду часто указывается произ­водителями мостов/коммутаторов и маршрутизаторов как основная характерис­тика производительности этих устройств. В свою очередь, интересно знать чистую максимальную пропускную способность сегмента Ethernet в кадрах в секунду в идеальном случае, когда в сети нет коллизий и нет дополнительных задержек, вно­симых мостами и маршрутизаторами. Такой показатель помогает оценить требова­ния к производительности коммуникационных устройств, так как в каждый порт устройства не может поступать больше кадров в единицу времени, чем позволяет это сделать соответствующий протокол.

Для коммуникационного оборудования наиболее тяжелым режимом является обработка кадров минимальной длины. Это объясняется тем, что на обработку каждого кадра мост, коммутатор или маршрутизатор тратит примерно одно и то же время, связанное с просмотром таблицы продвижения пакета, формированием нового кадра (для маршрутизатора) и т. п. А количество кадров минимальной длины, Поступающих на устройство в единицу времени, естественно больше, чем кадров любой другой длины. Другая характеристика производительности коммуникаци­онного оборудования — бит в секунду — используется реже, так как она не говорит о том, какого размера кадры при этом обрабатывало устройство, а на кадрах макси­мального размера достичь высокой производительности, измеряемой в битах в се­кунду гораздо легче.

Используя параметры, приведенные в табл. 3.1, рассчитаем максимальную про­изводительность сегмента Ethernet в таких единицах, как число переданных кад­ров (пакетов) минимальной длины в секунду

ПРИМЕЧАНИЕ При указании пропускной способности сетей термины кадр и пакет обычно используются как синонимы.;

Соответственно, аналогичными являются и единицы измерения производительности fremes-per-second, fps и pockets—per—second, pps

Для расчета максимального количества кадров минимальной длины, проходящих по сегменту Ethernet, заметим, что размер кадра минимальной длины вместе с преамбулой составляет 72 байт или 576 бит (рис. 3.5.), поэтому на его передачу затрачивается 57,5 мкс. Прибавив межкадровый интервал в 9,6 мкс, получаем, что период следования кадров минимальной длины составляет 67,1 мкс. Отсюда максимально возможная пропускная способность сегмента Ethernet составляет 14 880 кадр/с.

Рис. 3.5. К расчету пропускной способности протокола Ethernet

Естественно, что наличие в сегменте нескольких узлов снижает эту величину за счет ожидания доступа к среде, а также за счет коллизий, приводящих к необходимости повторной передачи кадров.

Кадры максимальной длины технологии Ethernet имеют поле длины 1500 байт что вместе со служебной информацией дает 1518 байт, а с преамбулой состава 1526 байт или 12 208 бит. Максимально возможная пропускная способность с мента Ethernet для кадров максимальной длины составляет 813 кадр/с. Очевид что при работе с большими кадрами нагрузка на мосты, коммутаторы и маршру заторы довольно ощутимо снижается.

Теперь рассчитаем, какой максимальной полезной пропускной способность бит в секунду обладают сегменты Ethernet при использовании кадров разного размера.

Под полезной пропускной способностью протокола понимается скорость передачи пользовательских данных, которые переносятся полем данных кадра. Эта пропускная способность всегда меньше номинальной битовой скорости проток Ethernet за счет нескольких факторов:

• служебной информации кадра;

• межкадровых интервалов (IPG);

• ожидания доступа к среде.

Для кадров минимальной длины полезная пропускная способность равна:

Сп = 14880 х 46 х 8 = 5,48 Мбит/с.

Это намного меньше 10 Мбит/с, но следует учесть, что кадры минимальной длины используются в основном для передачи квитанций, так что к передаче соб­ственно данных файлов эта скорость отношения не имеет.

Для кадров максимальной длины полезная пропускная способность равна:

Сп = 813 х 1500 х 8 — 9,76 Мбит/с,

что весьма близко к номинальной скорости протокола.

Еще раз подчеркнем, что такой скорости можно достигнуть только в том слу­чае, когда двум взаимодействующим узлам в сети Ethernet другие узлы не мешают, что бывает крайне редко.

При использовании кадров среднего размера с полем данных в 512 байт про­пускная способность сети составит 9,29 Мбит/с, что тоже достаточно близко к пре­дельной пропускной способности в 10 Мбит/с.

ВНИМАНИЕ Отношение текущей пропускной способности сети к ее максимальной пропускной способности называ­ется коэффициентом использования сети (network utilizationl. При этом при определении текущей пропус­кной способности принимается во внимание передача по сети любой информации, как пользовательской, так и служебной. Коэффициент является важным показателем для технологий разделяемых сред, так как при случайном характере метода доступа высокое значение коэффициента использования часто говорит о низкой полезной пропускной способности сети (то есть скорости передачи пользовательских данных) -слишком много времени узлы тратят на процедуру получения доступа и повторные передачи кадров пос­ле коллизий.

При отсутствии коллизий и ожидания доступа коэффициент использования сети зависит от размера поля данных кадра и имеет максимальное значение 0,976 при передаче кадров максимальной длины. Очевидно, что в реальной сети Ethernet среднее значение коэффициента использования сети может значительно отличать­ся от этой величины. Более сложные случаи определения пропускной способности сети с учетом ожидания доступа и отработки коллизий будут рассмотрены ниже.

3.3.3. Форматы кадров технологии Ethernet

Стандарт технологии Ethernet, описанный в документе IEEE 802.3, дает описание единственного формата кадра уровня MAC. Так как в кадр уровня MAC должен вкладываться кадр уровня LLC, описанный в документе IEEE 802.2, то по стандар­там IEEE в сети Ethernet может использоваться только единственный вариант кад­ра канального уровня, заголовок которого является комбинацией заголовков MAC и LLC подуровней.

Тем не менее на практике в сетях Ethernet на канальном уровне используются кадры 4-х различных форматов (типов). Это связано с длительной историей разви­тия технологии Ethernet, насчитывающей период существования до принятия стан­дартов IEEE 802, когда подуровень LLC не выделялся из общего протокола и, соответственно, заголовок LLC не применялся.

Консорциум трех фирм Digital, Intel и Xerox в 1980 году представил на рас­смотрение комитету 802.3 свою фирменную версию стандарта Ethernet (в которой был, естественно, описан определенный формат кадра) в качестве проекта между­народного стандарта, но комитет 802.3 принял стандарт, отличающийся в некото­рых деталях от предложения DIX. Отличия касались и формата кадра, что породило существование двух различных типов кадров в сетях Ethernet.

Еще один формат кадра появился в результате усилий компании Novell по уско­рению работы своего стека протоколов в сетях Ethernet.

И наконец, четвертый формат кадра стал результатом деятельности комитета 802.2 по приведению предыдущих форматов кадров к некоторому общему стандарту.

Различия в форматах кадров могут приводить к несовместимости в работе ап-

паратуры и сетевого программного обеспечения, рассчитанного на работу только с

одним стандартом кадра Ethernet. Однако сегодня практически все сетевые адапте- ры, драйверы сетевых адаптеров, мосты/коммутаторы и маршрутизаторы умеют работать со всеми используемыми на практике форматами кадров технологии Ether- net, причем распознавание типа кадра выполняется автоматически.

Ниже приводится описание всех четырех типов кадров Ethernet (здесь под кадром понимается весь набор полей, которые относятся к канальному уровню, то есть поля MAC и LLC уровней). Один и тот же тип кадра может иметь разные названия, поэтому ниже для каждого типа кадра приведено по нескольку наиболее употребительных названий:

• кадр 802.3/LLC (кадр 802.3/802.2 или кадр Novell 802.2);

• кадр Raw 802.3 (или кадр Novell 802.3);

в кадр Ethernet DIX (или кадр Ethernet II);

• кадр Ethernet SNAP.

Форматы всех этих четырех типов кадров Ethernet приведены на рис. 3.6.

Заголовок кадра 802.3/LLC является результатом объединения полей заголови кадров, определенных в стандартах IEEE 802.3 и 802.2.

Стандарт 802.3 определяет восемь полей заголовка (рис. 3.6; поле преамбулыЦ начальный ограничитель кадра на рисунке не показаны).

• Поле преамбулы (Preamble) состоит из семи синхронизирующих байт 1010101 При манчестерском кодировании эта комбинация представляется в физичесю среде периодическим волновым сигналом с частотой 5 МГц.

• Начальный ограничитель кадра (Start—of—frame—delimiter, SFD) состоит из одни байта 10101011. Появление этой комбинации бит является указанием на то, Ч следующий байт — это первый байт заголовка кадра.

в Адрес назначения (Destination Address, DA) может быть длиной 2 или 6 байт. I практике всегда используются адреса из 6 байт. Первый бит старшего баЙ адреса назначения является признаком того, является адрес индивидуальна или групповым. Если он равен 0, то адрес является индивидуальным (unicast, если 1, то это групповой адрес (multicast). Групповой адрес может предназначат» всем узлам сети или же определенной группе узлов сети. Если адрес состоит всех единиц, то есть имеет шестнадцатеричное представление OxFFFFFFFFFFK то он предназначается всем узлам сети и называется широковещательным адресом (broadcast). В остальных случаях групповой адрес связан только с те1 узлами, которые сконфигурированы (например, вручную) как члены групп номер которой указан в групповом адресе. Второй бит старшего байта адре определяет способ назначения адреса — централизованный или локальный. Если этот бит равен 0 (что бывает почти всегда в стандартной аппаратуре Ethernet), то адрес назначен централизованно, с помощью комитета IEEE. Комитет IEEE распределяет между производителями оборудования так называемые организа­ционно уникальные идентификаторы (Organizationally Unique Identifier, OUI). Этот идентификатор помещается в 3 старших байта адреса (например, идентифи­катор 000081 определяет компанию Bay Networks). За уникальность млад- ших 3-х байт адреса отвечает производитель оборудования. Двадцать четыре бита, отводимые производителю для адресации интерфейсов его продукции, позволяют выпустить 16 миллионов интерфейсов под одним идентификатором организации. Уникальность централизованно распределяемых адресов распространяется на все основные технологии локальных сетей — Ethernet, Token Ring, FDDI и т. д.

ВНИМАНИЕ В стандартах IEEE Ethernet младший бит байта изображается в самой левой позиции поля, а старший бит — в самой правой. Этот нестандартный способ отображения порядка бит в байте соответствует порядку передачи бит в линию связи передатчиком Ethernet. В стандартах других организаций, например RFC IETF, ITU-T, ISO, используется традиционное представление байта, когда младший бит считается самым правым битом байта, а старший — самым левым. При этом порядок следования байтов остается традиционным. Поэтому при чтении стандартов, опубликованных этими организациями, а также чтении данных, отображаемых на экране операционной системой или анализатором протоколов, значения каждого байта кадра Ethernet нужно зеркально отобразить, чтобы получить правильное представление о значении разрядов этого байта в соответствии с документами IEEE. Например, групповой адрес, имеющийся в нотации IEEE bug 1000 0000 0000 0000 101001И111] 0000 0000 0000 0000 0000 или в шестнадцатеричной записи 80-00-A7-FO-00-00, будет, скорее всего, отображен анализатором протоколов в традиционном виде как 01-00-5E-OF-00-00.

в Адрес источника (Source Address, SA) — это 2- или 6-байтовое поле, содержащее адрес узла — отправителя кадра. Первый бит адреса всегда имеет значение 0.

• Длина (Length, L) — 2-байтовое поле, которое определяет длину поля данных в кадре.

• Поле данных (Data) может содержать от 0 до 1500 байт. Но если длина поля меньше 46 байт, то используется следующее поле — поле заполнения, — чтобы дополнить кадр до минимально допустимого значения в 46 байт.

в Поле заполнения (Padding) состоит из такого количества байт заполнителей, которое обеспечивает минимальную длину поля данных в 46 байт. Это обеспе­чивает корректную работу механизма обнаружения коллизий. Если длина поля данных достаточна, то поле заполнения в кадре не появляется.

• Поле контрольной суммы (Frame Check Sequence, FCS) состоит из 4 байт, содер­жащих контрольную сумму. Это значение вычисляется по алгоритму CRC-32. После получения кадра рабочая станция выполняет собственное вычисление контрольной суммы для этого кадра, сравнивает полученное значение со значе­нием поля контрольной суммы и, таким образом, определяет, не искажен ли полученный кадр.

Кадр 802.3 является кадром МАС-подуровня, поэтому в соответствии со стан­дартом 802.2 в его поле данных вкладывается кадр подуровня LLC с удаленными флагами начала и конца кадра. Формат кадра LLC был описан выше. Так как кадр LLC имеет заголовок длиной 3 (в режиме LLC1) или 4 байт (в режиме LLC2), то максимальный размер поля данных уменьшается до 1497 или 1496 байт.

Рис. 3.6. Форматы кадров Ethernet

Кадр Raw 802.3/Novell 802.3

Кадр Raw 8023, называемый также кадром Novell 8023, представлен на рис. 3.6. л рисунка видно, что это кадр подуровня MAC стандарта 802.3, но без вложенно кадра подуровня LLC. Компания Novell долгое время не использовала служебного поля кадра LLC в своей операционной системе NetWare из-за отсутствия необа димости идентифицировать тип информации, вложенной в поле данных, — та всегда находился пакет протокола IPX, долгое время бывшего единственным пр токолом сетевого уровня в ОС NetWare.

Теперь, когда необходимость идентификации протокола верхнего уровня явилась, компания Novell стала использовать возможность инкапсуляции в ка подуровня MAC кадра LLC, то есть использовать стандартные кадры 802.3/LI Такой кадр компания обозначает теперь в своих операционных системах как кг 802.2, хотя он является комбинацией заголовков 802.3 и 802.2.

Кадр Ethernet DIX/Ethernet II

Кадр Ethernet DIX, называемьш также кадром Ethernet II, имеет структуру,

совпадающую со структурой кадра Raw 802.3. Однако 2-байтовое поле Длину кадра Raw 802.3 в кадре Ethernet DIX используется в качестве поля типа протоке Это поле, теперь получившее название Type (Т) или EtherType, предназначено;

тех же целей, что и поля DSAP и SSAP кадра LLC — для указания типа проток верхнего уровня, вложившего свой пакет в поле данных этого кадра.

В то время как коды протоколов в полях SAP имеют длину в один байт, в по Type для кода протокола отводятся 2 байта. Поэтому один и тот же npOTOKOJ поле SAP и поле Type будет кодироваться в общем случае разными числовыми значениями. Например, протокол IP имеет код 2048ю (0х0800) для поля EtherType и значение 6 для поля SAP. Значения кодов протоколов для поля EtherType появи­лись раньше значений SAP, так как фирменная версия Ethernet DIX существовала до появления стандарта 802.3, и ко времени распространения оборудования 802.3 уже стали стандартами де-факто для многих аппаратных и программных продук­тов. Так как структуры кадров Ethernet DIX и Raw 802.3 совпадают, то поле дли­ны/типа часто в документации обозначают как поле L/T.

Кадр Ethernet SNAP

Для устранения разнобоя в кодировках типов протоколов, сообщения которых вложены в поле данных кадров Ethernet, комитетом 802.2 была проведена работа по дальнейшей стандартизации кадров Ethernet. В результате появился кадр Ethernet SNAP (SNAP — SubNetwork Access Protocol, протокол доступа к подсетям). Кадр Ethernet SNAP (см. рис. 3.6) представляет собой расширение кадра 802.3/LLC за счет введения дополнительного заголовка протокола SNAP, состоящего из двух полей: OUI и Type. Поле Type состоит из 2-х байт и повторяет по формату и назна­чению поле Type кадра Ethernet II (то есть в нем используются те же значения кодов протоколов). Поле OUI (Organizationally Unique Identifier) определяет иден­тификатор организации, которая контролирует коды протоколов в поле Type. С помощью заголовка SNAP достигнута совместимость с кодами протоколов в кад­рах Ethernet II, а также создана универсальная схема кодирования протоколов. Коды протоколов для технологий 802 контролирует IEEE, которая имеет OUI, равный 000000. Если в будущем потребуются другие коды протоколов для какой-либо новой технологии, для этого достаточно указать другой идентификатор ор­ганизации, назначающей эти коды, а старые значения кодов останутся в силе (в сочетании с другим идентификатором OUI).

Так как SNAP представляет собой протокол, вложенный в протокол LLC, то в полях DSAP и SSAP записывается код ОхАА, отведенный для протокола SNAP. Поле Control заголовка LLC устанавливается в 0х03, что соответствует использо­ванию ненумерованных кадров.

Заголовок SNAP является дополнением к заголовку LLC, поэтому он допустим не только в кадрах Ethernet, но и в кадрах протоколов других технологий 802. Например, протокол IP всегда использует структуру заголовков LLC/SNAP при инкапсуляции в кадры всех протоколов локальных сетей: FDDI, Token Ring, 100VG-AnyLAN, Ethernet, Fast Ethernet, Gigabit Ethernet.

Правда, при передаче пакетов IP через сети Ethernet, Fast Ethernet и Gigabit Ethernet протокол IP использует кадры Ethernet DIX.

Использование различных типов кадров Ethernet

Автоматическое распознавание типов кадров Ethernet выполняется достаточно не­сложно. Для кодирования типа протокола в поле EtherType указываются значения, превышающие значение максимальной длины поля данных, равное 1500, поэтому кадры Ethernet II легко отличить от других типов кадров по значению поля L/T. Дальнейшее распознавание типа кадра проводится по наличию или отсутствию полей LLC. Поля LLC могут отсутствовать только в том случае, если за полем Длины идет начало пакета IPX, а именно 2-байтовое поле контрольной суммы па­кета, которое всегда заполняется единицами, что дает значение в 255 байт. Ситуация, когда поля DSAP и SSAP одновременно содержат такие значения, возникнуть не может, поэтому наличие двух байт 255 говорит о том, что это кадр Raw 802.3. В остальных случаях дальнейший анализ проводится в зависимости от значений по­лей DSAP и SSAP. Если они равны ОхАА, то это кадр Ethernet SNAP, а если нет, то 802.3/LLC.

В табл. 3.2 приведены данные о том, какие типы кадров Ethernet обычно под­держивают реализации популярных протоколов сетевого уровня.

Таблица 3.2. Типы кадров Ethernet, поддерживающие реализации популярных протоколов сетевого уровня

3.3.4. Спецификации физической среды Ethernet

Исторически первые сети технологии Ethernet были созданы на коаксиальном кабеле диаметром 0,5 дюйма. В дальнейшем были определены и другие спецификации физического уровня для стандарта Ethernet, позволяющие использовать различные среды передачи данных. Метод доступа CSMA/CD и все временные параметры остаются одними и теми же для любой спецификации физической среды технологии Ethernet 10 Мбит/с.

Физические спецификации технологии Ethernet на сегодняшний день включав ют следующие среды передачи данных.

• lOBase-5 — коаксиальный кабель диаметром 0,5 дюйма, называемый «толстым| коаксиалом. Имеет волновое сопротивление 50 Ом. Максимальная длина сегмента — 500 метров (без повторителей).

• lOBase-2 — коаксиальный кабель диаметром 0,25 дюйма, называемый «тоню коаксиалом. Имеет волновое сопротивление 50 Ом. Максимальная длина ( мента — 185 метров (без повторителей).

в lOBase-T — кабель на основе неэкранированной витой пары (Unshielded Twii Pair, UTP). Образует звездообразную топологию на основе концентратора. Расстояние между концентратором и конечным узлом — не более 100 м.

• lOBase-F — волоконно-оптический кабель. Топология аналогична топологии ста дарта lOBase-T. Имеется несколько вариантов этой спецификации — FOH (расстояние до 1000 м), lOBase-FL (расстояние до 2000 м), lOBase-FB (расстояние до 2000 м). Число 10 в указанных выше названиях обозначает битовую скорость передав данных этих стандартов — 10 Мбит/с, а слово Base — метод передачи на одни базовой частоте 10 МГц (в отличие от методов, использующих несколько несущих частот, которые называются Broadband — широкополосными). Последний символа названии стандарта физического уровня обозначает тип кабеля.

Стандарт lOBase-5 в основном соответствует экспериментальной сети Ethernet фир­мы Xerox и может считаться классическим Ethernet. Он использует в качестве среды передачи данных коаксиальный кабель с волновым сопротивлением 50 Ом, диаметром центрального медного провода 2,17 мм и внешним диаметром около 10 мм («толстый» Ethernet). Такими характеристиками обладают кабели марок RG-SHRG-ll.

Различные компоненты сети, состоящей из трех сегментов, соединенных повто­рителями, выполненной на толстом коаксиале, показаны на рис. 3.7.

Кабель используется как моноканал для всех станций. Сегмент кабеля имеет максимальную длину 500 м (без повторителей) и должен иметь на концах согласу­ющие терминаторы сопротивлением 50 Ом, поглощающие распространяющиеся по кабелю сигналы и препятствующие возникновению отраженных сигналов. При отсутствии терминаторов («заглушек») в кабеле возникают стоячие волны, так что одни узлы получают мощные сигналы, а другие — настолько слабые, что их прием становится невозможным.

Рис. 3.7. Компоненты физического уровня сети стандарта 10 Base-5, состоящей из трех сегментов

Станция должна подключаться к кабелю при помощи приемопередатчика — трансивера (transmitter+receiver = transceiver). Трансивер устанавливается непо­средственно на кабеле и питается от сетевого адаптера компьютера. Трансивер может подсоединяться к кабелю как методом прокалывания, обеспечивающим непосред­ственный физический контакт, так и бесконтактным методом.

Трансивер соединяется с сетевым адаптером интерфейсным кабелем A UI(Attach—ment Unit Interface) длиной до 50 м, состоящим из 4 витых пар (адаптер должен иметь разъем AUI). Наличие стандартного интерфейса между трансивером и осталь­ной частью сетевого адаптера очень полезно при переходе с одного типа кабеля на Другой. Для этого достаточно только заменить Трансивер, а остальная часть сетево­го адаптера остается неизменной, так как она отрабатывает протокол уровня MAC. При этом необходимо только, чтобы новый Трансивер (например, Трансивер для витой пары) поддерживал стандартный интерфейс AUI. Для присоединения к ин­терфейсу AUI используется разъем DB-15.

Допускается подключение к одному сегменту не более 100 трансиверов, причем Расстояние между подключениями трансиверов не должно быть меньше 2,5 м. На кабеле имеется разметка через каждые 2,5 м, которая обозначает точки подключе­ния трансиверов. При подсоединении компьютеров в соответствии с разметкой илияние стоячих волн в кабеле на сетевые адаптеры сводится к минимуму.

Трансивер — это часть сетевого адаптера, которая выполняет следующие функции:

о прием и передача данных с кабеля на кабель;

в определение коллизий на кабеле;

• электрическая развязка между кабелем и остальной частью адаптера;

• защита кабеля от некорректной работы адаптера.

Последнюю функцию иногда называют «контролем болтливости», что является буквальным переводом соответствующего английского термина (jabber control). При возникновении неисправностей в адаптере может возникнуть ситуация, когда на кабель будет непрерывно выдаваться последовательность случайных сигналов. Так как кабель — это общая среда для всех станций, то работа сети будет заблокирована одним неисправным адаптером. Чтобы этого не случилось, на выходе передатчика ставится схема, которая проверяет время передачи кадра. Если максимально воз­можное время передачи пакета превышается (с некоторым запасом), то эта схема просто отсоединяет выход передатчика от кабеля. Максимальное время передачи кадра (вместе с преамбулой) равно 1221 мкс, а время jabber-контроля устанавли­вается равным 4000 мкс (4 мс).

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

Детектор коллизий определяет наличие коллизии в коаксиальном кабеле по повышенному уровню постоянной составляющей сигналов. Если постоянная составляющая превышает определенный порог (около 1,5 В), значит, на кабель работает более одного передатчика. Развязывающие элементы (РЭ) обеспечивают гальвани^ ческую развязку трансивера от остальной части сетевого адаптера и тем самым защищают адаптер и компьютер от значительных перепадов напряжения, возникав ющих на кабеле при его повреждении.

Рис. 3.8. Структурная схема трансивера устройства

Стандарт 10Base-5 определяет возможность использования в сети специального устройства – повторителя. Повторитель служит для объединения в одну

сеть нескольких сегментов кабеля и увеличения тем самым общей длины сети. Повторитель принимает сигналы из одного сегмента кабеля и побитно синхронно повторяет их в другом сегменте, улучшая форму и мощность импульсов, а также синхронизируя импульсы. Повторитель состоит из двух (или нескольких) транси-веров, которые присоединяются к сегментам кабеля, а также блока повторения со своим тактовым генератором. Для лучшей синхроннизации передаваемых бит по­вторитель задерживает передачу нескольких первых бит преамбулы кадра, за счет чего увеличивается задержка передачи кадра с сегмента на сегмент, а также не­сколько уменьшается межкадровый интервал IPG. .

Стандарт разрешает использование в сети не более 4 повторителей и, соответ­ственно, не более 5 сегментов кабеля. При максимальной длине сегмента кабеля в 500 м это дает максимальную длину сети lOBase-5 в 2500 м. Только 3 сегмента из 5 могут быть нагруженными, то есть такими, к которым подключаются конечные узлы. Между нагруженными сегментами должны быть ненагруженные сегменты, так что максимальная конфигурация сети представляет собой два нагруженных крайних сегмента, которые соединяются ненагруженными сегментами еще с одним центральным нагруженным сегментом. На рис. 3.7 был приведен пример сети Ethernet, состоящей из трех сегментов, объединенных двумя повторителями. Край­ние сегменты являются нагруженными, а промежуточный — ненагруженным.

Правило применения повторителей в сети Ethernet lOBase-5 носит название вправило 5-4-Зу. 5 сегментов, 4 повторителя, 3 нагруженных сегмента. Ограничен­ное число повторителей объясняется дополнительными задержками распростране­ния сигнала, которые они вносят. Применение повторителей увеличивает время двойного распространения сигнала, которое для надежного распознавания колли­зий не должно превышать время передачи кадра минимальной длины, то есть кад­ра в 72 байт или 576 бит.

Каждый повторитель подключается к сегменту одним своим трансивером, поэто­му к нагруженным сегментам можно подключить не более 99 узлов. Максимальное число конечных узлов в сети lOBase-5 таким образом составляет 99х3 = 297 узлов.

К достоинствам стандарта lOBase-5 относятся:

• хорошая защищенность кабеля от внешних воздействий;

• сравнительно большое расстояние между узлами;

• возможность простого перемещения рабочей станции в пределах длины кабеля AUI. Недостатками lOBase-5 являются:

• высокая стоимость кабеля;

• сложность его прокладки из-за большой жесткости;

• потребность в специальном инструменте для заделки кабеля;

останов работы всей сети при повреждении кабеля или плохом соединении;

необходимость заранее предусмотреть подводку кабеля ко всем возможным местам установки компьютеров.

Стандарт IOBase-2 использует в качестве передающей среды коаксиальный кабель с диаметром центрального медного провода 0,89 мм и внешним диаметром около

5 мм («тонкий» Ethernet). Кабель имеет волновое сопротивление 50 Ом. Такими характеристиками обладают кабели марок RG-58 /U, RG-58 A/U, RG-58 C/U.

Максимальная длина сегмента без повторителей составляет 185 м, сегмент дол­жен иметь на концах согласующие терминаторы 50 Ом. Тонкий коаксиальный ка­бель дешевле толстого, из-за чего сети lOBase-2 иногда называют сетями Cheapemet (от cheaper — более дешевый). Но за дешевизну кабеля приходится расплачиваться качеством — «тонкий» коаксиал обладает худшей помехозащищенностью, худшей механической прочностью и более узкой полосой пропускания.

Станции подключаются к кабелю с помощью высокочастотного BNC Т-коннек-тора, который представляет собой тройник, один отвод которого соединяется с сетевым адаптером, а два других — с двумя концами разрыва кабеля. Максималь­ное количество станций, подключаемых к одному сегменту, — 30. Минимальное расстояние между станциями —1м. Кабель «тонкого» коаксиала имеет разметку для подключения узлов с шагом в 1 м.

Стандарт lOBase-2 также предусматривает использование повторителей, при- менение которых также должно соответствовать «правилу 5-4-3». В этом случае сеть будет иметь максимальную длину в 5х185 = 925 м. Очевидно, что это ограничение является более сильным, чем общее ограничение в 2500 метров.

ВНИМАНИЕ Для построения корректной сети Ethernet нужно соблюсти много ограничений, причем некоторые из них относятся к одним и тем же параметрам сети — например, максимальная длина или максимальное количество компьютеров в сети должны удовлетворять одновременно нескольким разным условиям. Корректная сетьи Ethernet должна соответствовать всем требованиям, но на практике нужно удовлетворить только наиболее. жесткие. Так, если в сети Ethernet не должно быть более 1024 узлов, а стандарт lOBase-2 ограничивает числи нагруженных сегментов тремя, то общее количество узлов в сети lOBase-2 не должно превышать 29х3. Менее жесткое ограничение в 1024 конечных узла в сети lOBase-2 никогда не достигается.

Стандарт lOBase-2 очень близок к стандарту lOBase-5. Но трансиверы в него объединены с сетевыми адаптерами за счет того, что более гибкий тонкий коак- сиальный кабель может быть подведен непосредственно к выходному разъем платы сетевого адаптера, установленной в шасси компьютера. Кабель в данном случае «висит» на сетевом адаптере, что затрудняет физическое перемещение компьютеров.

Типичный состав сети стандарта lOBase-2, состоящей из одного сегмента:

ля, показан на рис. 3.9.

Рис. 3.9. Сеть стандарта ЮВазе-2

Реализация этого стандарта на практике приводит к наиболее простому реши нию для кабельной сети, так как для соединения компьютеров требуются толый сетевые адаптеры, Т-коннекторы и терминаторы 50 Ом. Однако этот вид кабе ных соединений наиболее сильно подвержен авариям и сбоям: кабель более восп имчив к помехам, чем «толстый» коаксиал, в моноканале имеется больше количество механических соединений (каждый Т-коннектор дает три механичес­ких соединения, два из которых имеют жизненно важное значение для всей сети), пользователи имеют доступ к разъемам и могут нарушить целостность монокана­ла. Кроме того, эстетика и эргономичность этого решения оставляют желать луч­шего, так как от каждой станции через Т-коннектор отходят два довольно заметных провода, которые под столом часто образуют моток кабеля — запас, необходимый на случай даже небольшого перемещения рабочего места.

Общим недостатком стандартов lOBase-5 и lOBase-2 является отсутствие опера­тивной информации о состоянии моноканала. Повреждение кабеля обнаруживает­ся сразу же (сеть перестает работать), но для поиска отказавшего отрезка кабеля необходим специальный прибор — кабельный тестер.

Стандарт принят в 1991 году, как дополнение к существующему набору стандар­тов Ethernet, и имеет обозначение 802.31.

Сети IOBase-Т используют в качестве среды две неэкранированные витые пары (Unshielded Twisted Pair, UTP). Многопарный кабель на основе неэкранированной витой пары категории 3 (категория определяет полосу пропускания кабеля, вели­чину перекрестных наводок NEXT и некоторые другие параметры его качества) телефонные компании уже достаточно давно использовали для подключения теле­фонных аппаратов внутри зданий. Этот кабель носит также название Voice Grade, говорящее о том, что он предназначен для передачи голоса.

Идея приспособить этот популярный вид кабеля для построения локальных сетей оказалась очень плодотворной, так как многие здания уже были оснащены нужной кабельной системой. Оставалось разработать способ подключения сетевых адаптеров и прочего коммуникационного оборудования к витой паре таким обра­зом, чтобы изменения в сетевых адаптерах и программном обеспечении сетевых операционных систем были бы минимальными по сравнению с сетями Ethernet на коаксиале. Это удалось, поэтому переход на витую пару требует только замены трансивера сетевого адаптера или порта маршрутизатора, а метод доступа и все протоколы канального уровня остались теми же, что и в сетях Ethernet на коаксиале.

Конечные узлы соединяются по топологии «точка-точка» со специальным уст­ройством — многопортовым повторителем с помощью двух витых пар. Одна витая пара требуется для передачи данных от станции к повторителю (выход Тх сетевого адаптера), а другая — для передачи данных от повторителя к станции (вход Rx сетевого адаптера). На рис. 3.10 показан пример трехпортового повторителя. По­вторитель принимает сигналы от одного из конечных узлов и синхронно передает их на все свои остальные порты, кроме того, с которого поступили сигналы.

Многопортовые повторители в данном случае обычно называются концентра­торами (англоязычные термины — hub или concentrator). Концентратор осуществ­ляет функции повторителя сигналов на всех отрезках витых пар, подключенных к его портам, так что образуется единая среда передачи данных — логический моно­канал (логическая общая шина). Повторитель обнаруживает коллизию в сегменте в случае одновременной передачи сигналов по нескольким своим Rx-входам и по­сылает последовательность на все свои Тх-выходы. Стандарт определяет бито­вую скорость передачи данных 10 Мбит/с и максимальное расстояние отрезка витой пары между двумя непосредственно связанными узлами, станциями и концентраторами, не более 100 м при наличии витой пары качества не ниже категории 3. Это расстояние определяется полосой пропускания витой пары — на длине 100 м она позволяет передавать данные со скоростью 10 Мбит/с при использовании манчес­терского кода.

Рис. 3.10. Сеть стандарта 10Base-T: Тц — передатчик; R, — приемник

Концентраторы 10Base-T можно соединять друг с другом с помощью тех жй;

портов, которые предназначены для подключения конечных узлов. При этом нужно позаботиться о том, чтобы передатчик и приемник одного порта были соединены соответственно с приемником и передатчиком другого порта.

Рис. 3.11. Иерархическое соединение концентраторов Ethernet

Для обеспечения синхронизации станций при реализации процедур доступа CSMA/CD и надежного распознавания станциями коллизий в стандарте определино максимальное число концентраторов между любыми двумя станциями сети, именно 4. Это правило носит название «правила 4-х хабов» и оно заменяет правило 5-4-3», применяемое к коаксиальным сетям. При создании сети 10Base-T с большим числом станций концентраторы можно соединять друг с другом иерархическим способом, образуя древовидную структуру (рис. 3.11).

Петлевидное соединение концентраторов в стандарте 10Base-T запрещено, так как оно приводит к некорректной работе сети. Это требование означает, что в сети 10Base-T не разрешается создавать пораллельные каналы связи между критически важными концентраторами для резервирования связей на случай повреждения концентратора или кабеля. Резервирование связей возможно только за счет перевода одной из пар дельных связей в неактивное (заблокированное) состояние.___________________

Общее количество станций в сети 10Base-T не должно превышать общего предела в 1024, и для данного типа физического уровня это количество действительно можно достичь. Для этого достаточно создать двухуровневую иерархию концентраторов, расположив на нижнем уровне достаточное количество концентраторов общим количеством портов 1024 (рис. 3.12). Конечные узлы нужно подключить портам концентраторов нижнего уровня. Правило 4-х хабов при этом выполняеся — между любыми конечными узлами будет ровно 3 концентратора.

Рис. 3.12. Схема с максимальным количеством станций

Максимальная длина сети в 2500 м здесь понимается как максимальное расст< яние между любыми двумя конечными узлами сети (часто применяется такя термин «максимальный диаметр сети»). Очевидно, что если между любыми двум узлами сети не должно быть больше 4-х повторителей, то максимальный диамет сети 10Base-T составляет 5х100 = 500 м.

Сети, построенные на основе стандарта 10Base-T, обладают по сравнению с га аксиальными вариантами Ethernet многими преимуществами. Эти преимуществ связаны с разделением общего физического кабеля на отдельные кабельные отрезки, подключенные к центральному коммуникационному устройству. И хотя логически эти отрезки по-прежнему образуют общую разделяемую среду, их физическое разделение позволяет контролировать их состояние и отключать в случае обрыва, короткого замыкания или неисправности сетевого адаптера на индивидуальной основе. Это обстоятельство существенно облегчает эксплуатацию больших сетей Ethernet, так как концентратор обычно автоматически выполняет такие функции уведомляя при этом администратора сети о возникшей проблеме.

В стандарте 10Base-T определена процедура тестирования физической работе способности двух отрезков витой пары, соединяющих трансивер конечного узла и порт повторителя. Эта процедура называется тестом связности (link test), и она

основана на передаче каждые 16 мс специальных импульсов J и К манчестерского кода между передатчиком и приемником каждой витой пары. Если тест не прохо­дит, то порт блокируется и отключает проблемный узел от сети. Так как коды J и К являются запрещенными при передаче кадров, то тестовые последовательности не влияют на работу алгоритма доступа к среде.

Появление между конечными узлами активного устройства, которое может кон­тролировать работу узлов и изолировать от сети некорректно работающие, являет­ся главным преимуществом технологии lOBase-T по сравнению со сложными в эксплуатации коаксиальными сетями. Благодаря концентраторам сеть Ethernet приобрела некоторые черты отказоустойчивой системы.

В качестве среды передачи данных 10 мегабитный Ethernet использует оптическое волокно. Оптоволоконные стандарты в качестве основного типа кабеля рекоменду­ют достаточно дешевое многомодовое оптическое волокно, обладающее полосой, пропускания 500-800 МГц при длине кабеля 1 км. Допустимо и более дорогое од-, номодовое оптическое волокно с полосой пропускания в несколько гигагерц, но при этом нужно применять специальный тип трансивера.

Функционально сеть Ethernet на оптическом кабеле состоит из тех же элемен­тов, что и сеть стандарта lOBase-T — сетевых адаптеров, многопортового повторителя и отрезков кабеля, соединяющих адаптер с портом повторителя. Как и в случае с витой парой, для соединения адаптера с повторителем используются два оптоволокна — одно соединяет выход Тх адаптера со входом Rx повторителя, а другое — вход Rx адаптера с выходом Тх повторителя.

Стандарт FOIRL (Fiber Optic Inter—Repeater Link) представляет собой первый стандарт комитета 802.3 для использования оптоволокна в сетях Ethernet. Он гарантирует длину оптоволоконной связи между повторителями до 1 км при общей длине сети не более 2500 м. Максимальное число повторителей между любыми узлами сети — 4. Максимального диаметра в 2500 м здесь достичь можно, хотя максимальные отрезки кабеля между всеми 4 повторителями, а также между повторителями и конечными узлами недопустимы — иначе получится сеть длиной 5000 м.

Стандарт 10Base—FL представляет собой незначительное улучшение стандарт FOIRL. Увеличена мощность передатчиков, поэтому максимальное расстояи между узлом и концентратором увеличилось до 2000 м. Максимальное число п вторителей между узлами осталось равным 4, а максимальная длина сети — 2500

Стандарт 10Base—FB предназначен только для соединения повторителей. К нечные узлы не могут использовать этот стандарт для присоединения к порт;

концентратора. Между узлами сети можно установить до 5 повторителей 10Base-FB при максимальной длине одного сегмента 2000 м и максимальной длине сети 2740 м.

Повторители, соединенные по стандарту 10Base-FB, при отсутствии кадров передачи постоянно обмениваются специальными последовательностями сигналами, отличающимися от сигналов кадров данных, для поддержания синхронизаци. Поэтому они вносят меньшие задержки при передаче данных из одного сегментав другой, и это является главной причиной, по которой количество повторителей удалось увеличить до 5. В качестве специальных сигналов используются манчее терские коды J и К в следующей последовательности: J-J-K-K-J-J-. Эта последовательность порождает импульсы частоты 2,5 МГц, которые и поддерживающие синхронизацию приемника одного концентратора с передатчиком другого. Поэто­му стандарт 10Base-FB имеет также название синхронный Ethernet.

Как и в стандарте lOBase-T, оптоволоконные стандарты Ethernet разрешают соединять концентраторы только в древовидные иерархические структуры. Любые петли между портами концентраторов не допускаются.

В технологии Ethernet, независимо от применяемого стандарта физического уров­ня, существует понятие домена коллизий.

Домен коллизий (collision domain) — это часть сети Ethernet, все узлы которой распознают коллизию независимо от того, в какой части этой сети коллизия воз­никла. Сеть Ethernet, построенная на повторителях, всегда образует один домен коллизий. Домен коллизий соответствует одной разделяемой среде. Мосты, ком­мутаторы и маршрутизаторы делят сеть Ethernet на несколько доменов коллизий.

Приведенная на рис. 3.11 сеть представляет собой один домен коллизий. Если, например, столкновение кадров произошло в концентраторе 4, то в соответствии с логикой работы концентраторов lOBase-T сигнал коллизии распространится по всем портам всех концентраторов.

Если же вместо концентратора 3 поставить в сеть мост, то его порт С, связан­ный с концентратором 4, воспримет сигнал коллизии, но не передаст его на свои остальные порты, так как это не входит в его обязанности. Мост просто отработа­ет ситуацию коллизии средствами порта С, который подключен к общей среде, где эта коллизия возникла. Если коллизия возникла из-за того, что мост пытался передать через порт С кадр в концентратор 4, то, зафиксировав сигнал коллизии, порт С приостановит передачу кадра и попытается передать его повторно через случайный интервал времени. Если порт С принимал в момент возникновения коллизии кадр, то он просто отбросит полученное начало кадра и будет ожидать, когда узел, передававший кадр через концентратор 4, не сделает повторную по­пытку передачи. После успешного принятия данного кадра в свой буфер мост передаст его на другой порт в соответствии с таблицей продвижения, например на порт А. Все события, связанные с обработкой коллизий портом С, для осталь­ных сегментов сети, которые подключены к другим портам моста, останутся про­сто неизвестными.

Узлы, образующие один домен коллизий, работают синхронно, как единая рас­пределенная электронная схема.

Общие характеристики стандартов Ethernet 10 Мбит/с

Втабл. 3.3 и 3.4 сведены основные ограничения и характеристики стандартовEthernet.

Таблица 3.3. Общие ограничения для всех стандартов Ethernet

Таблица 3.4. Параметры спецификаций физического уровня для стандарта Ethernet