Кратко

  • В экспериментальном общем Ethernet коллизия доказывала, что несколько станций передавали в уязвимом временном окне. Она не называла соперника, не строила очередь и не резервировала следующий слот.
  • Контроллер прекращал повреждённую передачу, обновлял счётчик и самостоятельно выбирал случайный интервал. Повторные коллизии расширяли среднее ожидание, а проходящий кадр заставлял уступить ещё раз.
  • Robert Metcalfe и David Boggs описали распределённую координацию, которой требовалось сотрудничество. Случайность разрушала синхронные повторы, но не гарантировала справедливость, доставку или свойства современного full-duplex Ethernet.

Когда два локальных решения столкнулись

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

Общим стал узкий факт: попытки пересеклись во времени, ограниченном распространением сигнала. В коллизии нет адреса конкурента, универсального порядка прибытия или права на следующий интервал. Кабель свидетельствует о конфликте, но не судит будущее.

Статья Metcalfe и Boggs 1976 года описывает широковещательный многостанционный канал с распределённым управлением. Распределённость не означает отсутствие правил: станции слушают, обнаруживают, останавливаются и повторяют. Однако новый момент выбирает каждый источник сам.

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

Захват среды ещё не доставка

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

Последний исход не резервирует следующую попытку. Он также не доказывает проверку кадра получателем или обработку приложением. Авторы называют Ethernet вероятностным и допускают потери из-за помех, шума, неактивного приёмника или намеренного отбрасывания.

Следует хранить разные квитанции: источник закончил передачу; получатель принял кадр; сервис подтвердил действие. Первая зелёная отметка не заменяет третью.

Независимый выбор после общего события

После коллизии источник обновляет её номер и генерирует новый случайный интервал. Metcalfe и Boggs описывают удвоение среднего ожидания после каждого столкновения и уступку любому кадру, который появился до повторной попытки. Процедура названа эвристическим приближением Binary Exponential Backoff.

Смысл не только в более долгом ожидании. Расширяется пространство независимых будущих решений. Фиксированная пауза сохранила бы синхронизацию соперников. Случайный выбор обычно разъединяет их; при устойчивой нагрузке более широкое окно снижает вероятность нового совпадения.

Интерпретация IEEE 802.3 1997 года уточняет позднюю усечённую двоичную форму: после коллизии и jam станция равномерно выбирает целое число slot times, показатель растёт до предела, а попытки заканчиваются успехом или лимитом. Требуется снижать корреляцию случайных чисел разных станций. Эти параметры стандарта нельзя без оговорки переносить на каждый прототип 1973 года.

В устной истории Metcalfe относит часть детектирования к аппаратуре, а backoff — к микрокоду с аппаратной поддержкой. Это полезное свидетельство о месте решения, но не нейтральный тест производительности и не замена опубликованному алгоритму.

Сотрудничество, которого не обеспечивает провод

Исходная работа говорит, что справедливое разделение требует сотрудничества. Станция могла захватить Ether, отказавшись увеличивать интервал под нагрузкой, либо отправляя настолько большие пакеты, что другим редко доставался шанс. Экспериментальная система запрещала оба поведения.

Кабель видит наложение сигналов, но не проверяет честность генератора и не принуждает контроллер к умеренности. Справедливость зависит от общих ограничений, соответствия реализации и длительного наблюдения задержек и долей доступа. Слово «распределённый» её не создаёт.

Авторство также нельзя свести к одному имени. Работа принадлежит Metcalfe и Boggs. В патенте названы Robert M. Metcalfe, David R. Boggs, Charles P. Thacker и Butler W. Lampson. В родословную входят ALOHAnet, инженеры PARC и участники стандартизации. Формулировка премии Тьюринга отмечает изобретение, стандартизацию и коммерциализацию Metcalfe и прямо называет Boggs соавтором PARC Ethernet.

Граница доказательства

Сначала надо подтвердить реальный общий half-duplex домен и соответствие slot time физическому охвату. Затем связать состояние несущей, начало, коллизию, остановку, номер попытки, случайное значение, уступку промежуточному трафику и повтор. Захват среды, проверка приёмником и подтверждение приложения остаются разными событиями.

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

Современный Ethernet обычно использует коммутаторы и point-to-point full-duplex линии. Конкурса на общем коаксиале там нет. Коллизии на интерфейсе, который считается full duplex, скорее требуют проверки среды, смысла счётчика и duplex mismatch, чем объяснения нормальной работой классического механизма.

Источники