1. Формат кадра Ethernet
начало
|
|
На рис.1 показан формат кадра Ethernet.
Рис.1.
|
Два базовых MAC формата (raw formats) кадра Ethernet |
Поля имеют следующие назначения:
- Преамбула: 7 байт, каждый из которых представляет чередование единиц и нулей 10101010. Преамбула позволяет установить битовую синхронизацию на приемной стороне.
- Ограничитель начала кадра (SFD, start frame delimiter): 1 байт, последовательность 10101011, указывает, что далее последуют информационные поля кадра. Этот байт можно относить к преамбуле.
- Адрес назначения (DA, destination address): 6 байт, указывает MAC-адрес станции (MAC-адреса станций), для которой (которых) предназначен этот кадр. Это может быть единственный физический адрес (unicast), групповой адрес (multicast) или широковещательный адрес (broadcast).
- Адрес отправителя (SA, source address): 6 байт, указывает MAC-адрес станции, которая посылает кадр.
- Поле типа или длины кадра (T or L, type or length): 2 байта. Существуют два базовых формата кадра Ethernet (в английской терминологии raw formats - сырые форматы) - Ethernet_II и IEEE 802.3 (рис.1), причем различное назначение у них имеет именно рассматриваемое поле. Для кадра Ethernet_II в этом поле содержится информация о типе кадра. Ниже приведены значения в шестнадцатеричной системе этого поля для некоторых распространенных сетевых протоколов: 0x0800 для IP, 0x0806 для ARP, 0x809B для AppleTalk, 0x0600 для XNS, и 0x8137 для IPX/SPX. С указанием в этом поле конкретного значения (одного из перечисленных) кадр приобретает реальный формат, и в таком формате кадр уже может распространяться по сети.
Для кадра IEEE 802.3 в этом поле содержится выраженный в байтах размер следующего поля - поля данных (LLC Data). Если эта цифра приводит к общей длине кадра меньше 64 байт, то за полем LLC Data добавляется поле Pad. Для протокола более высокого уровня не возникает путаницы с определением типа кадра, так как для кадра IEEE 802.3 значение этого поля не может быть больше 1500 (0x05DC). По этому, в одной сети могут свободно сосуществовать оба формата кадров, более того один сетевой адаптер может взаимодействовать с обоими типами посредством стека протоколов.
- Данные (LLC Data): поле данных, которое обрабатывается подуровнем LLC. Сам по себе кадр IEEE 802.3 еще не окончательный. В зависимости от значений первых нескольких байт этого поля, могут быть три окончательных формата этого кадра IEEE 802.3:
- Ethernet_802.3 (не стандартный, в настоящее время устаревающий формат, используемый Novell) - первые два байта LLC Data равны 0xFFFF;
- Ethernet_SNAP (стандартный IEEE 802.2 SNAP формат, которому отдается наибольшее предпочтение в современных сетях, особенно для протокола TCP/IP) - первый байт LLC Data равен 0xAA;
- Ethernet_802.2 (стандартный IEEE 802.2 формат, взят на вооружение Novell в NetWare 4.0) - первый байт LLC Data не равен ни 0xFF (11111111), ни 0xAA (10101010).
- Дополнительное поле (pad - наполнитель) - заполняется только в том случае, когда поле данных невелико, с целью удлинения длины кадра до минимального размера 64 байта -преамбула не учитывается. Ограничение снизу на минимальную длину кадра необходимо для правильного разрешения коллизий.
- Контрольная последовательность кадра (FCS, frame check sequence): 4-х байтовое поле, в котором указывается контрольная сумма, вычисленная с использованием циклического избыточного кода по полям кадра за исключением преамбулы, SDF и FCS.
|
2. Основные варианты алгоритмов случайного доступа к среде
начало
|
|
Протокол CSMA/CD определяет характер взаимодействия рабочих станций в сети с единой общей для всех устройств средой передачи данных. Все станции имеют равноправные условия по передаче данных. Нет определенной последовательности, в соответствии с которой станции могут получать доступ к среде для осуществления передачи. Именно в этом смысле доступ к среде осуществляется случайным образом. Реализация алгоритмов случайного доступа представляется значительно более простой задачей, чем реализация алгоритмов детерминированного доступа. Поскольку в последнем случае требуется или специальный протокол, контролирующий работу всех устройств сети (например протокол обращения маркера, свойственный сетям Token Ring и FDDI), или специальное выделенное устройство - мастер концентратор, который в определенной последовательности предоставлял бы всем остальным станция возможность передавать (сети Arcnet, 100VG AnyLAN).
Однако сеть со случайным доступом имеет один пожалуй главный недостаток - это не совсем устойчивая работа сети при большой загруженности, когда может проходить достаточно большое время, прежде чем данной станции удается передать данные. Виной тому коллизии, которые возникают между станциями, начавшими передачу одновременно или почти одновременно. При возникновении коллизии передаваемые данные не доходят до получателей, а передающим станциям приходится повторно возобновлять передачу. Дадим определение:
множество всех станций сети, одновременная передача любой пары из которых приводит к коллизии, называется коллизионным доменом (collision domain).
Из-за коллизии могут возникать непредсказуемые задержки при распространении кадров по сети, особенно при большой загруженности сети (много станций пытаются одновременно передавать внутри коллизионного домена, > 20-25) и при большом диаметре коллизионного домена (> 2 км). Поэтому при построении сетей желательно избегать таких экстремальных режимов работы.
Проблема построения протокола, способного наиболее оптимальным образом разрешать коллизии, и оптимизирующего работу сети при больших загрузках, была одной из ключевых на этапе формирования стандарта Ethernet IEEE 802.3. Первоначально рассматривались три основных подхода в качестве кандидатов для реализации стандарта случайного доступа к среде: непостоянный, 1-постоянный и р-постоянный (рис.2).
Рис.2.
|
Алгоритмы множественного случайного доступа (CSMA) и выдержка времени в конфликтной ситуации (collision backoff) |
Непостоянный (nonpersistent) алгоритм. При этом алгоритме станция, желающая передавать, руководствуется следующими правилами.
- Прослушивает среду, и если среда свободна (т.е. если нет другой передача или нет сигнала коллизии) передает, в противном случае - среда занята - переходит к шагу 2;
- Если среда занята, ждет случайное (в соответствии c определенной кривой распределения вероятностей) время и возвращается к шагу 1.
Использование случайного значения ожидания при занятой среде уменьшает вероятность образования коллизий. Действительно, предположим в противном случае, что две станции практически одновременно собрались передавать, в то время, как третья уже осуществляет передачу. Если первые две не имели бы случайного времени ожидания перед началом передачи (в случае, если среда оказалась занятой), а только прослушивали среду и ждали когда она освободится, то после прекращения передачи третей станцией первые две начали бы передавать одновременно, что неизбежно приводило бы к коллизиям. Таким образом случайное ожидание устраняет возможность образования таких коллизий. Однако неудобство этого метода проявляется в неэффективном использовании полосы пропускания канала. Поскольку может случиться, что к тому моменту, когда среда освободится, станция, желающая передавать еще будет продолжать ожидать некоторое случайное время прежде чем решится прослушивать среду, поскольку перед этим уже прослушивала среду, которая оказалась занятой. В итоге канал будет простаивать какое то время, даже если только одна станция ожидает передачи.
1-постоянный (1-persistent) алгоритм. Для сокращения времени, когда среда не занята, мог бы использоваться 1-постоянный алгоритм. При этом алгоритме станция, желающая передавать, руководствуется следующими правилами.
- Прослушивает среду, и если среда не занята передает, в противном случае переходит к шагу 2;
- Если среда занята, продолжает прослушивать среду до тех пор пока среда не освободится, и как только среда освобождается сразу же начинает передавать.
Сравнивая непостоянный и 1-постоянный алгоритмы, можно сказать, что в 1-постоянном алгоритме желающая передавать станция ведет себя более "эгоистично". По этому, если две или более станций ожидают передачи (ждут пока не освободится среда), коллизия, можно сказать, будет гарантирована. После коллизии станции начинают думать, что им делать дальше.
Р-постоянный (p-persistent) алгоритм. Правила этого алгоритма следующие:
- Если среда свободна, станция с вероятность p сразу же начинает передачу или с вероятность (1-p) ожидает в течение фиксированного интервал времени T. Интервал T обычно берется равным максимальному времени распространения сигнала из конца в конец;
- Если среда занята, станция продолжает прослушивание до тех пор, пока среда не освободится, затем переходит к шагу 1;
- Если передача задержана на один интервал T, станция возвращается к шагу 1.
И здесь возникает вопрос выбора наиболее эффективного значения параметра p. Главная проблема, как избежать нестабильности при высоких загрузках. Рассмотрим ситуацию, при которой n станций намерены передать кадры, в то время как уже идет передача. По окончанию передачи ожидаемое количество станций, которые попытаются передавать будет равно произведению количества желающих передавать станций на вероятность передачи, то есть np. Если np > 1, то в среднем несколько станций будут пытаться передать сразу, что вызовет коллизию. Более того, как только коллизия будет обнаружена, все станции вновь перейдут к шагу 1, что вызовет повторную коллизию. В худшем случае новые станции, желающие предавать, могут добавиться к n, что еще больше усугубит ситуацию, приведя в конечном итоге к непрерывной коллизии и нулевой пропускной способности. Во избежании такой катастрофы произведение np должно быть меньше единицы. Если же сеть подвержена возникновению состояний, когда много станций одновременно желают передавать, то необходимо уменьшать p. С другой стороны, когда p становиться слишком малым, даже отдельная станция может прождать в среднем интервалов T, прежде чем осуществит передачу. Так если p=0,1 то средний простой, предшествующий передаче, составит 9T. |
|
Протокол множественного случайного доступа к среде с разрешением коллизий CSMA/CD воплотил в себе идеи выше перечисленных алгоритмов и добавил важный элемент - разрешение коллизий. Поскольку коллизия разрушает все передаваемые в момент ее образования кадры, то и нет смысла станциям продолжать дальнейшую передачу своих кадров, коль скоро они (станции) обнаружили коллизии. В противном случае, значительной была бы потеря времени при передаче длинных кадров. По этому для своевременного обнаружения коллизии станция прослушивает среду на всем протяжении собственной передачи. Приведем основные правила алгоритма CSMA/CD для предающей станции.
Передача кадра (рис.3а):
- Станция, собравшаяся передавать, прослушивает среду. И передает, если среда свободна. В противном случае (т.е. если среда занята) переходит к шагу 2. При передаче нескольких кадров подряд станция выдерживает определенную паузу между посылками кадров - межкадровый интервал, причем после каждой такой паузы перед отправкой следующего кадра станция вновь прослушивает среду (возвращение на начало шага 1);
- Если среда занята, станция продолжает прослушивать среду до тех пор, пока среда не станет свободной, и затем сразу же начинает передачу;
- Каждая станция, ведущая передачу прослушивает среду, и в случае обнаружения коллизии, не прекращает сразу же передачу а сначала передает короткий специальный сигнал коллизии - jam-сигнал, информируя другие станции о коллизии, и прекращает передачу;
- После передачи jam-сигнала станция замолкает и ждет некоторое произвольное время в соответствии с правилом бинарной экспоненциальной задержки и затем возвращаясь к шагу 1.
Межкадровый интервал IFG (interframe gap) составляет в 9,6 мкм (12 байт). С одной стороны он необходим для того, чтобы принимающая станция могла корректно завершить прием кадра. Кроме этого, если бы станция передавала кадры непрерывно, она бы полностью захватила канал и тем самым лишила другие станции возможности передачи.
Jam-сигнал (jamming - дословно глушение). Передача jam-сигнала гарантирует, что не один кадр не будет потерян, так как все узлы, которые передавали кадры до возникновения коллизии, приняв jam-сигнал, прервут свои передачи и замолкнут в преддверии новой попытки передать кадры. Jam-сигнал должен быть достаточной длины, чтобы он дошел до самых удаленных станций коллизионного домена, с учетом дополнительной задержки SF (safety margin) на возможных повторителях. Содержание jam-сигнала не принципиально за исключением того, что оно не должно соответствовать значению поля CRC частично переданного кадра (802.3), и первые 62 бита должны представлять чередование ‘1’ и ‘0’ со стартовым битом ‘1’.
Рис.3а.
|
Структурная схема алгоритма CSMA/CD (уровень MAC): при передаче кадра станцией |
Рис.3б.
|
Структурная схема алгоритма CSMA/CD (уровень MAC): при приеме кадра станцией |
На рис.4 проиллюстрирован процесс обнаружения коллизии применительно к топологии шина (на основе тонкого или толстого коаксиального кабеля (стандарты 10Base5 и 10Base2 соответственно).
В момент времени узел A (DTEA) начинает передачу, естественно прослушивая свой же передаваемый сигнал. В момент времени , когда кадр почти дошел узла B (DTE B), этот узел, не зная о том, что уже идет передача, сам начинает передавать. В момент времени , узел B обнаруживает коллизию (увеличивается постоянная составляющей электрического сигнала в прослушиваемой линии). После этого узел B передает jam-сигнал и прекращает передачу. В момент времени сигнал коллизии доходит до узла A, после чего A также передает jam-сигнал и прекращает передачу.
Рис.4.
|
Обнаружение коллизии в при использовании схемы CSMA/CD стандарта Ethernet |
По стандарту Ethernet узел не может предавать очень короткие кадры, или иными словами вести очень короткие передачи. Как говорилось при описании формата кадра, даже если поле данных не заполнено до конца, то появляется специальное дополнительное поле, удлиняющее кадр до минимальной длины 64 байта без учета преамбулы. Время канала ST (slot time)- это минимальное время, в течении которого узел обязан вести передачу, занимать канал. Это время соответствует передаче кадра минимального допустимого размера, принятого стандартом Ethernet IEEE 802.3. Время канала связано с максимальным допустимым расстоянием между узлами сети - диаметром коллизионного домена. Допустим, что в приведенном выше примере реализуется наихудший сценарий, когда станции A и B удалены друг от друга на максимальное расстояние. Время, распространения сигнала от A до B обозначим через . Узел A начинает передавать в нулевой момент времени. Узел B начинает передавать в момент времени и обнаруживает коллизию спустя интервал после начала своей передачи. Узел A обнаруживает коллизию в момент времени . Для того, чтобы кадр, испущенный A, не был потерян, необходимо, чтобы узел A не прекращал вести передачу к этому моменту, так как тогда, обнаружив коллизию, узел A будет знать, что его кадр не дошел, и попытается передавать его повторно. В противном случае кадр будет потерян. Максимальное время, спустя которое с момента начала передачи узел A еще может обнаружить коллизию равно - это время называется задержкой на двойном пробеге RTD (round-trip delay). В более общем случае RTD определяет суммарную задержку, связанную как с задержкой из-за конечной длины сегментов, так и с задержкой, возникающей при обработке кадров на физическим уровнем промежуточных повторителей и оконечных узлов сети. Для дальнейшего удобно использовать также другую единицу измерения времени: битовое время BT (bit time). Время в 1 BT соответствует времени, необходимому для передачи одного бита, т.е. 0,1 мкс при скорости 10 Мбит/с.
Стандартом Ethernet регламентированы следующие правила обнаружения коллизии конечным узлом сети :
- Узел A должен обнаружить коллизию до того, как передаст свой 512-й бит, включая биты преамбулы;
- Узел A должен прекратить передачу раньше, чем будет передан кадр минимальной длины - передано 576 бит (512 бит, начиная отсчет после ограничителя начала кадра SFD);
- Перекрытие между передачами узлов A и B - битовый интервал начиная с момента передачи первого бита преамбулы узлом A и заканчивая приемом узлом A последнего бита испущенного узлом B - должно быть меньше чем 575 BT.
Последнее условие для сети Ethernet является наиболее важным, поскольку его выполнение автоматически влечет выполнение и первых двух. Это третье условие задает ограничение на диаметр сети. Применительно к задержке на двойном пробеге RTD третье условие можно сформулировать в виде: T.
При передаче больших кадров, например 1500 байт, коллизия, если она вообще возникнет, обнаруживается практически в самом начале передачи, не позднее первых 64 переданных байт (если коллизия не возникла в это время, то позже она уже не возникнет, поскольку все станции прослушивают линию и, "слыша" передачу, будут молчать). Так как jam-сигнал значительно короче полного размера кадра, то при использовании алгоритма CSMA/CD количество в холостую израсходованной емкости канала сокращается до времени, требуемого на обнаружение коллизии. Раннее обнаружение коллизий приводит к более эффективным использование канала. Позднее обнаружение коллизий, свойственное более протяженным сетям, когда диаметре коллизионного домена составляет несколько километров, снижает эффективность работы сети. На основании упрощенной теоретической модели поведения загруженной сети (в предположении большого числа одновременно передающих станций и фиксированной минимальной длины передаваемых кадров у всех станций) можно выразить производительность сети U через отношение RTD/ST:
,
где - основание натурального логарифма. На производительность сети влияет размер транслируемых кадров и диаметр сети. Производительность в наихудшем случае (когда RDT=ST) составляет около 37%, а в наилучшем случае (когда RTD много меньше, чем ST) стремится к 1. Хотя формула и выведена в пределе большого числа станций, пытающихся передавать одновременно, она не учитывает особенностей алгоритма усеченной бинарной экспоненциальной задержки, рассмотренного ниже, и не справедлива для сильно перегруженной коллизиями сети, например, когда станций, желающих передавать становится больше 15.
Усеченная бинарная экспоненциальная задержка (truncated binary exponential backoff). Алгоритм, принятый в стандарте IEEE 802.3 CSMA/CD, наиболее близок к 1-постоянному алгоритму, но отличается дополнительным элементом - усеченной бинарной экспоненциальной задержкой. При возникновения коллизии стация подсчитывает, сколько раз подряд при отправке пакета возникает коллизия. Поскольку повторяющиеся коллизии свидетельствуют о высокой загруженности среды, MAC-узел пытается увеличивать задержку между повторными попытками передачи кадра. Соответствующая процедура увеличения интервалов времени подчиняется правилу усеченной бинарной экспоненциальной задержки и работает следующим образом.
Количество слотовых времен (интервалов по 51,2 мкс), которое станция ждет перед тем как совершить N-ую попытку передачи (N-1 попыток потерпели фиаско из-за возникновения коллизий во время передачи) представляет случайное целое число с однородной функцией распределения в интервале , где , и BL (backoff limit) - установленная стандартом предельная задержка, равная 10. Если количество последовательных безуспешных попыток отправить кадр доходит до 16, то есть коллизия возникает 16 раз подряд, то кадр сбрасывается.
Алгоритм CSMA/CD с использованием усеченной бинарной экспоненциальной задержки признан лучшим среди множества алгоритмов случайного доступа и обеспечивает эффективную работу сети как при малых, так и при средних загрузках. При больших загрузках следует отметить два недостатка. Во-первых, при большом числе коллизий станция 1, которая впервые собирается отправить кадр (до этого не пыталась передавать кадры), имеет преимущество перед станцией 2, которая уже несколько раз безуспешно пыталась передать кадр, натыкаясь на коллизии. Поскольку станция 2 ожидает значительное время пред последующими попытками в соответствии с правилом бинарной экспоненциальной задержки. Таким образом может наблюдаться нерегулярность передачи кадров, что нежелательно для зависящих от времени приложений. Во-вторых, при большой загруженности снижается эффективность работы сети в целом. Оценки показывают, что при одновременной передаче 25 станций общая полоса пропускания снижается примерно в 2 раза. Но число станций в коллизионном домене может быть больше, поскольку далеко не все они одновременно будут обращаться к среде.
Прием кадра. (рис.3б) Принимающая станция или другое сетевое устройство, например, концентратор или коммутатор первым делом синхронизируется по преамбуле и затем преобразовывает манчестерский код в бинарную форму (на физическом уровне). Далее обрабатывается бинарный поток.
На уровне MAC оставшиеся биты преамбулы сбрасываются, а станция читает адрес назначения и сравнивает его со своим собственным. Если адреса совпадают, то поля кадра за исключением преамбулы, SDF и FCS помещаются в буфер и вычисляется контрольная сумма, которая сравнивается с полем контрольной последовательности кадра FCS (используется метод циклического суммирования CRC-32). Если они равны, то содержимое буфера передается протоколу более высокого уровня. В противном случае кадр сбрасывается. Возникновении коллизии при приеме кадра обнаруживается либо по изменению электрического потенциала, если используется коаксиальный сегмент, либо по факту приема дефектного кадра, неверная контрольная сумма, если используется витая пара или оптическое волокно. В обоих случая принятая информация сбрасывается.
Основные функциональные параметры стандарта Ethernet приведены в табл.1.
Таблица 1.
|
Основные функциональные параметры Ethernet IEEE 802.3 |
Битовая скорость (bit rate), Мбит/с |
10 (Манчестерское кодирование) |
Время слота (slot time), мкс (BT) |
51,2 (512) |
Межкадровый интервал (interframe gap), мкс (BT) |
9,6 (96) |
предел попыток (attempt limit) |
16 |
предельная задержка (backoff limit) |
10 |
размер jam-сигнала (jam size), биты |
32 |
максимальный размер кадра (maximum frame size), байты |
1518 |
минимальный размер кадра (minimum frame size), байты |
64 |
Длительность Jabber-сигнала, при которой повторитель останавливает передачу и изолирует сегмент, мс |
20-150 |
|