자연계열 4번

컴퓨터 네트워크(network)의 한 종류인 이더넷(Ethernet)에서는 여러 개의 컴퓨터가 하나의 통신 채널(channel)을 공유하여 프레임(frame)을 전송한다. 일반적으로 컴퓨터는 데이터(data)를 일정 크기로 나누고 편지 봉투와 같은 제어정보를 추가한 프레임으로 전송한다. 이러한 하나의 통신 채널을 공유하는 이더넷 구조는 간단하다는 장점은 있으나, 컴퓨터들이 동시에 프레임을 전송할 때 충돌이 발생한다. 즉 이더넷은 사회자 없이 여러 사람들이 모여 대화하는 구조로, 두 사람 이상이 동시에 발언하면 음성신호가 충돌되어 수신자들이 정확하게 청취할 수 없다.

이러한 충돌 문제를 해결하기 위한 다양한 방법들이 제안되었다. 가장 간단한 방식인 PA(Pure Aloha)방식에서는 전송할 프레임이 있으면 바로 프레임을 전송한다. PA의 최대 효율은 약 18%정도로, 주어진 시간의 18%동안에만 프레임을 성공적으로 전송하며 나머지 시간은 충돌로 낭비된다.

SA(Slotted Aloha)방식은 전송 시작시간을 동기화하여 전송 효율을 향상시킨다. 시간을 TS(Time Slot)라는 일정한 구간으로 나누고, 프레임을 TS구간의 시작시간에만 전송한다. 프레임이 TS구간 중간에 생성되더라도 다음 TS구간의 시작시간까지 전송을 지연한다. SA는 동기화를 통해 충돌구간의 길이를 감소시켜 효율을 향상시킨다. 즉 프레임 전송시간과 TS구간의 길이를 같은 $\displaystyle F$시간으로 가정하면, SA방식은 $\displaystyle F$시간만이 낭비된다. 이에 반해 PA방식은 아무 때나 프레임을 전송하므로 충돌로 인하여 최대 $\displaystyle 2F$시간이 낭비된다.

고효율을 위해 CSMA/CD방식은 CSMA와 CD방식을 채택한다. CSMA방식은 통신 채널의 상태를 측정하여 채널이 사용되지 않는 휴무상태일 때만 프레임을 전송한다. CD방식은 프레임 전송 중에 충돌신호가 감지되면 바로 프레임 전송을 중지한다. 그러나 CSMA방식은 한 컴퓨터들이 프레임을 전송하는 도중에는 다른 컴퓨터들은 채널을 사용하지 못하므로, 이 기간 동안에 기다리는 컴퓨터들이 누적되어 다음 휴무상태에 충돌확률이 높아진다. 이를 위해 p-persistent CSMA방식은 휴무상태일 때 확률 $\displaystyle p$$\displaystyle (0 < p \le 1)$로 프레임 전송을 결정한다. 일례로 $\displaystyle p$가 1/6인 경우에는 주사위를 던져 6이 나오면 프레임을 전송하고, 6이 아니면 고정된 지연구간 시간 $\displaystyle r$만큼 지연한다. 지연한 다음 다시 채널 상태를 측정하여 휴무상태이면 확률 $\displaystyle p$로 전송 여부를 결정한다.

CSMA/CD의 효율은 다음과 같이 근사하게 계산할 수 있다. 먼저 $\displaystyle k$개의 컴퓨터가 각각 확률 $\displaystyle p$로 프레임을 전송한다고 가정하면, 어느 한 컴퓨터가 성공적으로 전송할 확률 $\displaystyle A$는 식 (1)과 같다.

$\displaystyle A = kp(1-p) ^{k-1}$ (1)

식 (1)에서 $\displaystyle k$는 $\displaystyle k$개의 컴퓨터 중에서 한 컴퓨터를 선택하는 가지 수를, $\displaystyle p(1-p) ^{k-1}$은 선택된 한 컴퓨터만이 프레임을 전송하고 나머지는 전송하지 않을 확률이다.

성공적인 프레임 전송 전까지 소요되는 평균 낭비구간 횟수 $\displaystyle E[\mathrm{col}]$는 식 (2)와 같다. 낭비구간은 충돌구간과 전송 지연구간을 포함하는데, 충돌구간은 2개 이상의 컴퓨터가 전송할 때, 지연구간은 모든 컴퓨터가 전송하지 않을 때 발생한다.

$\displaystyle E[\mathrm{col}]=\sum_{i=1}^{\infty}iA(1-A)^i$ (2)

식 (2)의 $\displaystyle (1-A)$는 낭비구간이 발생할 확률이므로 $\displaystyle (1-A) ^{i} A$는 $\displaystyle i$번 연속으로 낭비구간이 발생한 후에 프레임을 전송할 확률이다. 참고로 임의의 사건 값의 평균은 사건 값과 해당 확률을 곱하고 이를 모든 사건에 대해서 합한 값이다.

CSMA/CD방식의 효율 $\displaystyle \mathrm{Eff}$는 식 (3)과 같다. 이때 $\displaystyle F$는 프레임 전송 시간을, $\displaystyle rE[\mathrm{col}]$는 하나의 프레임 전송 전에 소요되는 평균 낭비 시간이다. 이때 하나의 지연구간 시간과 충돌구간 시간은 각각 $\displaystyle r$로 동일하다고 가정한다.

$\displaystyle \mathrm{Eff}=\frac F{F+rE[\mathrm{col}]}$ (3)

이러한 CSMA/CD방식에서 식 (1)의 $\displaystyle p$값이 $\displaystyle k$값에 상관없이 고정된다면 전송 효율이 저하될 것이다. 일례로 전송하려는 컴퓨터 수가 많을 때 전송확률이 크다면 충돌로 낭비되는 시간이 클 것이다. 고효율을 위해서 식 (1)의 $\displaystyle A$값을 극대화해야 하고, 이를 위해서는 $\displaystyle p$값을 $\displaystyle k$값에 따라 동적으로 조정하여 지연시간과 충돌시간을 감소시켜야 할 것이다.

그러나 $\displaystyle k$값은 가변적이어서 알맞은 $\displaystyle p$값을 계산하는 것은 어렵다. 이러한 문제를 해결하기 위해 이더넷에서는 채널이 휴무상태이면 먼저 $\displaystyle p=1$의 확률로 프레임을 즉시 보내고, 충돌이 발생하면 BEB(Binary Exponential Backoff)방식을 사용한다. BEB방식에서는 한번 충돌이 발생하면 컴퓨터들은 0과 1의 두 수 중에서 하나를 무작위로 선택하여, 프레임을 전송할 휴무상태 차례를 결정한다. 0을 선택한 컴퓨터는 첫 번째 휴무상태에, 1을 선택한 컴퓨터는 두 번째 휴무상태에 전송한다. 연속해서 $\displaystyle n$번의 충돌이 발생되면 0에서 $\displaystyle (2 ^{n} -1)$ 범위의 $\displaystyle 2 ^{n}$개 정수 중에서 한 수를 무작위로 선택하여, 선택한 수만큼의 휴무상태가 경과한 다음에 프레임을 전송한다. 이 방법은 충돌 횟수에 따라 선택하는 정수 범위를 확장하므로, 동일한 휴무상태 차례에 프레임을 전송할 확률이 감소된다. 즉 BEB방식은 충돌 횟수가 증가하면 전송차례를 더욱 무작위화하여, 전송확률을 동적으로 조절하는 것과 같은 효과를 낸다.