Рис. 4.15. Обнаружение столкновения может занять 2т

Последнее поле кадра стандарта Ethernet — Checksum, которое содержит контрольную сумму. По сути дела, это 32-битный код CRC того же типа, как мы обсуждали выше. Он определен как раз при помощи того же порождающего многочлена, что используется для PPP, ADSL и других типов каналов. Этот CRC позволяет обнаруживать ошибки: он проверяет, правильно ли приняты биты кадра. Исправления ошибок нет, и если ошибка обнаруживается, кадр удаляется.

Экспоненциальный двоичный алгоритм выдержки

В классическом Ethernet используется алгоритм CSMA/CD с настойчивостью 1, который мы рассматривали выше. Это означает, что станции прослушивают среду передачи, когда у них появляется кадр на отправку, и отправляют данные, когда среда передачи освобождается. Отправляя кадр, они проверяют, не произошло ли в канале коллизий. Если столкновение случилось, они прерывают передачу, отправляя короткий сигнал о наличии конфликта, и повторяют отправку данных через случайный интервал времени.

Рассмотрим, как определяется случайная длина интервала ожидания после столкновения, так как это новый метод. Модель остается та же, что представлена на рис. 4.5. После возникновения коллизии время делится на дискретные интервалы, длительность которых равна максимальному времени кругового обращения сигнала (то есть его прохождения по кабелю в прямом и обратном направлении), 2т. Для удовлетворения потребностей Ethernet при максимальном размере сети необходимо, чтобы один интервал составлял 512 битовых интервалов или 51,2 мкс.

После первого столкновения каждая станция ждет или 0 или 1 интервал, прежде чем попытаться передавать опять. Если две станции столкнутся и выберут одно и то же псевдослучайное число, то они столкнутся снова. После второго столкновения каждая станция выбирает случайным образом 0, 1, 2 или 3 интервала из набора и ждет опять.

При третьем столкновении (вероятность такого события после двойного столкновения равна 1/4) интервалы будут выбираться в диапазоне от 0 до 2³ - 1.

В общем случае, после i столкновений случайный номер выбирается в диапазоне от 0 до 2ⁱ - 1, и это количество интервалов станция пропускает. Однако после 10 столкновений подряд интервал рандомизации фиксируется на отметке 1023. После 16 столкновений подряд контроллер признает свое поражение и возвращает компьютеру ошибку. Дальнейшим восстановлением занимаются более высокие уровни.

Этот алгоритм, называемый экспоненциальным двоичным алгоритмом выдержки (binary exponential backoff), был выбран для динамического учета количества станций, пытающихся осуществить передачу. Если выбрать интервал рандомизации равным 1023, то вероятность повторного столкновения будет пренебрежимо мала, однако среднее время ожидания составит сотни тактов, в результате чего среднее время задержки будет слишком велико. С другой стороны, если каждая станция будет выбирать время ожидания всего из двух вариантов, 0 и 1, то в случае столкновения сотни станций они будут продолжать сталкиваться снова и снова до тех пор, пока 99 из них не выберут 1, а одна станция — 0. Такого события можно будет ждать годами. Экспоненциально увеличивая интервал рандомизации по мере возникновения повторных столкновений, алгоритм обеспечивает небольшое время задержки при столкновении небольшого количества станций и одновременно гарантирует, что при столкновении большого числа станций конфликт будет разрешен за разумное время.

Если коллизии не произошло, отправитель предполагает, что кадр, вероятно, был успешно доставлен. Таким образом, ни в CSMA/CD, ни в Ethernet подтверждения не применяются. Такой вариант подходит для кабельных и оптоволоконных каналов с низким числом ошибок. Любые возникающие ошибки распознаются с помощью кода CRC и исправляются более высокими уровнями. Как мы увидим далее, в зашумленных беспроводных каналах подтверждения используются.

4.3.3. Производительность сети Ethernet

Оценим производительность классической сети Ethernet в условиях большой постоянной загрузки, то есть когда k станций постоянно готовы к передаче. Строгий анализ экспоненциального двоичного алгоритма выдержки довольно сложен. Вместо этого мы последуем за рассуждениями Меткальфа (Metcalfe) и Боггса (Boggs) (1976) и предположим, что вероятность повторной передачи в каждом интервале времени постоянна. Если каждая станция передает в течение одного интервала времени с вероятностью р, то вероятность того, что какой-либо станции удастся завладеть каналом, равна

Значение A будет максимальным, когда р = 1/k. При k, стремящемся к бесконечности, A будет стремиться к 1/e. Вероятность того, что период соревнования за канал будет состоять ровно из j интервалов, будет равна A(1 - A) ^j-1, следовательно, среднее число интервалов борьбы за канал будет равно

Так как длительность каждого интервала времени равна 2т, средняя продолжительность периода борьбы будет составлять w = 2т/А При оптимальном значении вероятности p среднее количество интервалов за период борьбы никогда не будет превосходить е, таким образом, средняя продолжительность периода борьбы будет равна 2те « 5,4т.

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

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

Полезно переформулировать выражение (4.6) в терминах длины кадра F, пропускной способности сети B, длины кабеля L и скорости распространения сигнала c для оптимального случая: e интервалов столкновений на кадр. При P = F/B выражение (4.6) примет вид:

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

На рис. 4.16 показана зависимость эффективности канала от числа готовых станций для 2т = 51,2 мкс и скорости передачи данных, равной 10 Мбит/с. Для расчетов используется выражение (4.7). При 64-байтном временном интервале 64-байтные кадры оказываются неэффективными, и это неудивительно. С другой стороны, если использовать кадры длиной 1024 байта, то при асимптотическом значении е периода состязания за канал, равном 64-байтовому интервалу, то есть 174 байтам, эффективность канала составит 85 %. Это намного лучший результат, чем 37 % в системе ALOHA с дискретными интервалами.

Следует отметить, что теоретическому анализу производительности сетей Ethernet (и других сетей) было посвящено много работ. Большинство результатов следует воспринимать с долей (или, лучше, с тонной) скептицизма по двум причинам. Во-первых, практически во всех этих теоретических исследованиях предполагается, что трафик подчиняется пуассоновскому распределению. Когда же исследователи рассмотрели реальные потоки данных, то обнаружилось, что сетевой трафик редко распределен по Пуассону, а чаще включает множество пиков (Paxson and Floyd, 1994; Leland и др., 1994). Это означает, что при увеличении периода усреднения трафик не сглаживается.