Компьютерные сети. 6-е изд. - Эндрю Таненбаум

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

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

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

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

После первой коллизии каждая станция ждет или 0, или 1 слот, прежде чем снова предпринять попытку передачи. Если после коллизии две станции выберут одно и то же псевдослучайное число, они снова будут конфликтовать друг с другом. После второй коллизии каждая станция выбирает случайным образом 0, 1, 2 или 3 слота из набора и ждет снова. При возникновении третьей коллизии (вероятность такого события после предыдущих двух равна 1/4) слоты будут выбираться в диапазоне от 0 до 23 – 1.

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

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

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

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

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

A = kp(1 – p)k – 1.

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

Так как длительность каждого слота равна 2τ, средняя продолжительность периода конкуренции w составит 2τ/A. При оптимальном значении вероятности p среднее количество слотов конкуренции никогда не превысит e; таким образом, w будет равна 2τ e ≈ 5,4τ.

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

Эффективность канала =

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

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

Эффективность канала =

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

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

Илл. 4.16. Эффективность Ethernet на скорости 10 Мбит/с, 512-битные временные слоты

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