CSMA/CD - 충돌 감지 알고리즘의 랜덤성에 대한 고찰

CSMA/CD 란

CSMA/CD는 LAN의 통신 프로토콜 중 하나로 Carrier Sense Multiple Access/Collision Detection의 약자입니다.

완전 간단하게 CSMA/CD에 대해 설명드리겠습니다.

네트워크 상에 Carrier 신호가 없을 때 데이터를 전송하고, 충돌이 발생할 시 랜덤한 시간 동안 대기한 후 다시 데이터를 전송하는 방식입니다.

이번에는 랜덤한 시간 동안 대기한 후 에 초점을 맞춰봤습니다.

문제

N명의 네트워크 사용자가 있고, 랜덤한 대기 시간은 주어진 정수 범위에서 {1, 2, 3, ..., N} 선택된다고 가정합니다.

• 실제로는 대기 시간도 실수 범위라서 전혀 다른 문제지만 그냥 재미난 상상을 해봤습니다.

위와 같은 가정하에 데이터가 전송되는데 평균적으로 걸리는 시간은 어떻게 될까요?

풀이

2명만 충돌이 발생하더라도 랜덤한 시간의 대기가 필요하기 때문에 기대값을 다음과 같이 계산할 수 있습니다.

기대값을 계산한 수식

위의 수식을 풀면 기대값을 N에 대한 간단한 식으로 풀어낼 수 있습니다.

• 무한등비급수 계산하듯이 풀었습니다.

N에 대한 표현

기대값을 N에 대해서 표현할 수 있다면 우리가 더 알아야 할 내용은 기대값을 최소로 낮추는 N을 찾는 것이겠죠?

local minima를 찾으면 되는데 이것은 wolfram alpha에게 맡겼습니다!

• wolfram alpha 링크

계산하면 약 3.56

N이 정수였으므로 N이 3일 때, 4일 때를 비교하면 4일 때가 더 작습니다.
따라서 N은 4일 때 가장 빨리 충돌이 해소되는 것이지요.

후기

실제로는 실수 범위에서 대기 시간을 랜덤으로 선택하기 때문에 큰 고민 없이 0~1 범위에서 랜덤하게 선택해도 괜찮을 것 같습니다.

혹시라도 CSMA/CD 알고리즘을 사용하는데 정수 범위에서 대기 시간을 골라야 한다면 위 내용들을 고려하면 좋을 것 같습니다.

문제를 잘못 해석한 부분이 있다면 피드백 부탁드립니다 :)