요약

  • 공유 실험 이더넷에서 충돌이란 취약 구간 내에 둘 이상의 스테이션이 전송했음을 뜻했다. 충돌은 경합이 있었음을 드러내지만, 상대 스테이션의 신원도, 중앙에서 선정된 승자도, 다음 슬롯에 대한 예약도 알려주지 않는다.
  • 송신 측 컨트롤러는 전송을 중단하고 자신의 충돌 이력을 갱신한 뒤 독립적으로 무작위 재전송 간격을 선택했다. 충돌이 반복되면 평균 대기 시간이 늘어나고, 지나가는 트래픽이 있으면 다음 시도 전에 한 번 더 양보하게 된다.
  • Robert Metcalfe와 David Boggs는 확률뿐 아니라 협력까지 필요로 하는 분산 시스템을 기술했다. 이 시스템의 교훈은 무작위성이 공정성을 보장한다는 것이 아니라, 작은 공통 감지 규칙 하나가 증거와 한계를 분리해 둔 채 각 지역의 의사결정을 지탱할 수 있다는 점이다.

아무도 선출하지 않은 충돌

하나의 동축 케이블 양 끝에 두 개의 송신 컨트롤러가 놓여 있다고 상상해 보라. 둘 다 이더(Ether)가 비어 있음을 감지한다. 첫 신호가 상대에게 도달하기 전에 둘 다 패킷 전송을 시작한다. 이제 각자는 자신이 보내는 것과 케이블에 흐르는 것을 비교하고 간섭을 감지한다. 공유된 사실은 명확하다. 이 시도는 온전한 전송으로 계속될 수 없다.

이 이후의 모든 일은 이 사실의 범위를 좁게 유지할 때 훨씬 이해하기 쉽다. 충돌에는 경합 상대의 주소가 담겨 있지 않다. 어떤 패킷이 보편적 순서에서 먼저 도착했는지도 말해주지 않는다. 이벤트를 가장 먼저 감지한 스테이션에 다음 구간을 넘겨주지도 않는다. 전파 지연이 존재하는 분산 매체에는 전선 안에 숨어 있는 심판이 없다.

Robert Metcalfe와 David Boggs의 1976년 논문은 스테이션들 사이에 분산 제어가 이루어지는 브로드캐스트 다중 접속 네트워크를 기술한다. "분산"은 규칙이 없다는 뜻이 아니었다. 스테이션은 간섭을 감지하고, 손상된 전송을 종료하고, 재전송 절차에 들어가야 했다. 공유 매체가 충돌의 증거를 제공했고, 컨트롤러는 그 증거를 자신의 미래 결정으로 바꾸었다.

이 구분은 익숙한 보도 오류를 막아 준다. 충돌 카운터는 순서대로 줄 서 있는 패자들의 대기열이 아니다. 열 번의 충돌 이벤트가 열 개의 서로 다른 스테이션이 경합했음을 증명하지 않으며, 카운트가 낮다고 우대 서비스가 있었다고 증명하지도 않는다. 이 카운터는 특정 타이밍 가정 하에서 특정 경합 도메인에 이루어진 시도에 대한 증거일 뿐이다. 신원, 대기 시간, 최종 수신 여부는 다른 관측이 필요하다.

하나의 슬롯, 세 가지 가능한 결과

원래 분석에서 슬롯은 전송 시작부터 충돌 발견까지의 최대 간격, 즉 공유 매체상의 한 번의 종단 간 왕복 전파 지연으로 경계가 정해졌다. 부하가 걸린 상태에서 경합 슬롯에는 세 가지 유용한 결과가 있다. 아무도 전송하지 않아 슬롯이 비어 있는 경우, 둘 이상의 스테이션이 전송해 슬롯이 충돌하는 경우, 그리고 정확히 하나가 전송해 자신의 패킷을 위해 이더를 획득하는 경우다.

세 번째 결과는 성공적인 획득이지 미래 일정의 소유권이 아니다. 패킷이 끝나면 다른 스테이션들이 다시 경합한다. 또한 획득이 종단 간 전달의 증명도 아니다. 논문은 이더넷을 명시적으로 확률적으로 다루며, 간섭·잡음·비활성 수신기·의도적 폐기로 인해 패킷이 손실될 수 있음을 지적한다. 따라서 상위 계층 프로토콜은 애플리케이션 처리에 대한 링크 계층 인증서가 아니라 높은 확률의 수신을 전제로 동작해야 한다.

이 경계는 운영적으로도 중요하다. 송신 측은 반송파 감지, 충돌 감지, 자기 전송의 완료를 기록할 수 있다. 수신 측은 프레임 검증과 로컬 전달을 기록할 수 있다. 애플리케이션은 작업을 승인할 수 있다. 이 세 가지는 서로 다른 세 개의 영수증이다. 첫 번째를 세 번째처럼 승격시키면 증거 없는 확신이 만들어진다.

분산된 재시도

충돌 후 송신 컨트롤러는 갱신된 충돌 횟수를 바탕으로 새로운 무작위 재전송 간격을 생성한다. Metcalfe와 Boggs는 충돌이 발생할 때마다 평균 지연을 두 배로 늘리고, 재시도 전에 지나가는 패킷에 양보한다고 기술했다. 그들의 논문은 이 절차를 이진 지수 백오프(Binary Exponential Backoff)의 휴리스틱 근사라고 부른다.

중요한 동작은 단순히 "더 오래 기다리는 것"이 아니다. 서로 다른 스테이션들이 독립적인 선택을 하는 선택 공간을 넓히는 것이다. 두 스테이션이 항상 동일한 고정 간격을 기다린다면 동기화를 유지하며 다시 충돌할 수 있다. 무작위 선택은 그 상관관계를 대부분의 경우 깨뜨린다. 반복되는 경합 하에서 범위를 늘리면 혼잡한 집단이 계속 같은 순간을 선택할 가능성이 줄어든다.

이후의 IEEE 802.3 문서는 특정 잘린(truncated) 이진 형식을 명시한다. 충돌과 잼(jam) 시퀀스 이후 스테이션은 균등 분포를 따르는 정수 슬롯 타임 수를 선택하고, 지수는 상한까지 시도 횟수와 함께 증가하며, 전송은 결국 성공하거나 시도 한도에 도달한다. 이 해석은 구현체들이 스테이션 간 난수의 상관관계를 최소화할 것도 요구한다. 이러한 후대 매개변수는 표준화된 메커니즘을 명확히 해 주지만, 1973년 프로토타입에 모든 상수가 그대로 등장했던 것처럼 소급 적용해서는 안 된다.

Metcalfe의 구술 역사는 충돌 감지를 부분적으로 하드웨어에, 백오프 로직을 하드웨어 보조를 받는 마이크로코드에 배치한다고 전한다. 이 회고는 결정이 어디에 존재했는지 설명하는 데 도움이 된다. 그러나 이는 1인칭 증언일 뿐, 중립적인 벤치마크도, 공개된 알고리즘의 대체물도 아니다.

협력은 프로토콜의 일부였다

확률만으로 공정한 사용이 확보되지 않았다. 1976년 논문은 어느 정도의 협력이 필요하다고 말한다. 스테이션은 부하 상황에서 재전송 간격을 늘리기를 거부하거나, 다른 스테이션이 기회를 얻기 어렵도록 패킷을 지나치게 크게 보냄으로써 이더를 독차지할 수 있었다. 실험 시스템은 이 두 가지 행태를 모두 금지했다.

이 관찰은 "네트워크는 알아서 정리된다"는 안심시키는 문구보다 훨씬 중요하다. 모든 스테이션은 자기만의 로컬 타이머를 갖지만, 모든 스테이션은 공유된 기대를 위반할 능력도 갖는다. 케이블은 겹치는 신호를 드러낼 수 있지만 컨트롤러의 동기를 검사하거나 정직한 무작위성을 강제할 수는 없다. 따라서 공정성은 일부가 규격 준수, 패킷 규칙, 관측된 결과의 속성이지 분산화가 자동으로 선물하는 것이 아니다.

특허 기록 역시 영웅 한 명의 서사를 거부한다. 특허는 Robert M. Metcalfe, David R. Boggs, Charles P. Thacker, Butler W. Lampson을 발명자로 명시하고, 간섭 감지 후 반복 충돌에 비례해 가중된 무작위 지연을 선택하는 절차를 기술한다. 역사적 계보에는 ALOHAnet, PARC의 개발자들, 표준화 커뮤니티도 포함된다. ACM 튜링상 시상 근거는 Metcalfe의 이더넷 발명, 표준화, 상용화를 인정하면서 Boggs를 PARC 시스템의 공동 발명자로 밝힌다. 정확한 공로 기재는 메커니즘을 강화할 뿐, 메커니즘을 축소하지 않는다.

증거가 증명할 수 있는 것과 없는 것

방어 가능한 재구성에는 하나의 카운터가 아니라 일련의 단계가 필요하다. 먼저 토폴로지를 확립하라. 이것이 실제로 하나의 공유 반이중(half-duplex) 충돌 도메인이었는지, 그리고 그 전파 상한은 무엇이었는지 확인하라. 다음으로 시도를 확립하라. 어느 송신이 시작했는지, 어떤 반송파 상태를 관측했는지, 언제였는지를 확인하라. 이어서 충돌 감지, 중단 또는 잼 동작, 갱신된 시도 횟수, 무작위 슬롯 선택, 그리고 지나가는 트래픽에 대한 양보를 기록하라. 마지막으로 매체 획득의 결과를 수신자 수용 및 상위 계층 승인과 분리하라.

이 체인은 스테이션이 경합 절차를 따랐음을 보여줄 수 있다. 그러나 모든 피어가 독립적인 난수 생성기를 사용했다는 것, 대기 시간이 같았다는 것, 어느 스테이션도 굶지 않았다는 것, 애플리케이션이 페이로드를 받았다는 것을 증명할 수는 없다. 분포에 대한 주장에는 스테이션과 시간에 걸친 통계적 관측이 필요하다. 전달에 대한 주장에는 수신자 및 애플리케이션 영수증이 필요하다.

역사적 경계도 똑같이 중요하다. 현대 이더넷은 대개 스위치를 통해 지점 간 링크를 연결하고 전이중(full duplex)으로 동작한다. 그런 링크에는 여기서 분석한 종류의 공유 동축 충돌 경쟁이 없다. 전이중이라고 믿어지는 장비에서 충돌 카운터가 증가하고 있다면, 그것은 고전적 경합이 설계대로 동작하고 있다는 증거라기보다 매체, 카운터, 모드 가정 또는 이중 모드 불일치(duplex mismatch)를 점검하라는 신호일 가능성이 높다.

출처