백오프 알고리즘(Back-off Algorithm)은 네트워크에서 데이터 전송 충돌이 발생했을 때 이를 해결하기 위해 사용되는 알고리즘입니다. 주로 이더넷(Ethernet)의 CSMA/CD(Carrier Sense Multiple Access with Collision Detection) 방식에서 활용됩니다.
백오프 알고리즘이란?
두 개 이상의 장치가 동시에 신호를 전송하면서 충돌(Collision)이 발생하면, 해당 장치들은 일정한 무작위(random) 시간만큼 기다린 후 다시 신호를 재전송합니다. 그리고 데이터가 성공적으로 전송될 때까지 이 과정을 반복합니다.
여기서 '백오프(back-off)'라는 이름은 노드들이 재전송을 시도하기 전에 일정 시간 동안 물러나서(뒤로 물러나서) 기다린다는 의미에서 유래했습니다.
중요한 점은, 이 무작위 대기 시간이 재전송 시도 횟수에 비례하여 증가한다는 것입니다.
알고리즘 동작 과정
아래는 백오프 알고리즘의 동작 흐름을 간략하게 보여주는 순서도입니다.
순서도에서 확인할 수 있듯이, 반복(iteration)이 진행될 때마다 N 값이 증가하고, 이에 따라 난수 선택 범위인 [0, 2n-1]도 함께 커지게 됩니다. 범위가 넓어질수록 두 노드가 같은 값을 선택할 확률이 줄어들기 때문에, 충돌이 발생할 확률이 점차 감소하는 구조입니다.
백오프 알고리즘의 단점
하지만 이 방식에는 단점도 존재합니다. 충돌이 계속 반복되면 백오프 시간이 계속 길어지는데, 최대 재전송 시도 횟수(maximum attempt limit)를 초과하면 일부 노드는 해당 패킷을 포기하고 폐기(discard)하게 됩니다. 즉, 지속적인 백오프는 패킷 손실로 이어질 수 있습니다.
대기 시간(Waiting Time) 계산 공식
충돌이 발생한 후 각 노드는 아래 공식으로 계산된 시간만큼 기다려야 합니다.
대기 시간 = K × Tslot
- Tslot: 길이가 2t인 이산 시간 슬롯(discrete time slot). 여기서 t는 네트워크의 최대 전파 지연(propagation delay)입니다.
- K: [0, 2n - 1] 범위에서 무작위로 선택된 값. n은 충돌 횟수(collision number)입니다.
정리하면, 충돌이 한 번 일어날 때마다 K의 선택 범위가 지수적으로 넓어지므로, 네트워크 상황에 따라 유연하게 재전송 타이밍을 조절할 수 있습니다. 이것이 CSMA/CD 환경에서 백오프 알고리즘이 효과적인 충돌 해결 방법으로 사용되는 이유입니다.