CSMA

상위 문서: Multiple Access Protocols

개요

Sloted ALOHA와 pure ALOHA 프로토콜에서는, 어떤 노드의 전송은 채널에 연결된 다른 노드들의 활동과는 무관하게 독립적으로 이루어진다. 하지만 CSMA 프로토콜에서는 이와는 다른 방식을 사용한다. 이는 아래와 같다:

1. 노드는 프레임을 전송하기 전에 채널이 다른 노드에 의해 사용중인지 청취하며, 이를 carrier sensing이라고 한다.
   • 만약 다른 노드가 해당 채널을 사용중이라면, 노드는 이를 기다린 후 프레임 전송을 시작한다.
2. 전송 중인 노드는 채널을 감시하면서, 다른 노드의 프레임이 전송되고 있다는 것을 감지하면 전송을 중단하며, 이를 collision detection이라고 한다.
   • 충돌을 감지하여 전송을 중단하였다면, 무작위 시간(delay)를 기다리고, 다시 감지하고, 채널이 비어있다면 전송하는 사이클을 반복한다.

이들 규칙은 CSMA(Carrier Sense Multiple Access) 및 CSMA/CD(Collision Detection 포함)프로토콜들에 구현되어 있다.

CSMA with Collision Dection (CSMA/CD)

Figure 1. Space-time diagram of CSMA without CD

CSMA 프로토콜은 언뜻 보기에 충돌이 발생할 가능성이 없어보인다. 하지만 실제로는 여전히 충돌이 발생하며, 그 이유는 figure 1에 나타난 공간-시간(space-time) 다이어그램으로 설명할 수 있다. Figure 1은 네 개의 노드 (A, B, C, D)가 선형 브로드캐스트 버스에 연결된 구조를 보여준다. 시간 t₀에 노드 B는 채널이 쉬고(idle)있다는 것을 감지하고 전송을 시작한다. 이때 B의 비트들은 브로드캐스트 채널을 따라 양 방향으로 전파된다. Figure 1에서 B의 비트가 시간에 따라 아래로 전파되는 이미지는, 비트가 전파되기 위해 시간이 소요된다는 것을 의미한다. 시간 t₁일 때에, 노드 D는 노드 B의 비트가 아직 D에 도달하지 않았으므로, 채널이 쉬고있다고 잘못 판단하고 전송을 시작한다. 잠시 후, B의 전송이 D의 전송과 충돌하게 된다. 이는, 전파 지연(propagation delay)가 성능에 중요한 역할을 한다는 것을 보여준다. 전파 지연이 길수록, 다른 노드의 전송을 감지하기 어려워지고 충돌 확률이 증가한다.

Figure 2. CSMA with collision detection

Figure 1는 노드들이 충돌 감지를 수행하지 않는 상황을 보여준다. 즉, 충돌이 발생하더라도 B와 D는 프레임을 끝까지 전송한다. 하지만 충돌 감지를 수행하는 경우, 노드는 충돌을 감지하는 즉시 전송을 중단한다. Figure 2는 같은 상황에서 충돌 감지로 인해 두 노드가 전송을 중단하는 예시를 보여준다. Collision detect/abort time은 노드가 충돌을 감지하고, 전송을 중단하기까지 걸리는 시간을 의미한다. 충돌 감지를 통한 프레임 전송의 정지는 손상된 프레임 전체를 낭비하지 않고 전송을 도중에 중단하므로, 프로토콜 성능 향상에 도움을 준다.

아래는 위를 바탕으로 한, NIC(네트워크 어댑터)의 관점에서 바라본 CSMA/CD 프로토콜의 동작을 요약한 것이다.

1. NIC는 네트워크 계층에서 데이터그램을 받아, link layer를 준비하고 버퍼에 저장한다.
2. 어댑터는 채널이 쉬고(idle)있다면 프레임 전송을 시작한다. 하지만 채널이 사용 중이라면 다른 노드가 전송하는 것이 감지되지 않을 때까지 기다린다.
3. 프레임 전체를 전송할 때까지, 타 노드의 전송이 감지되지 않으면 성공이고, 반대로 전송 중 타 노드의 전송이 감지되면 전송을 즉시 중단한다.
   • 전송을 중단한 경우에는, 무작위 시간을 기다린 다음 2단계부터 다시 시작한다.

이때 고정된 시간이 아니라 무작위 시간을 대기하는 이유는, 같은 시간 동안 계속 대기할 경우, 계속 충돌이 발생하기 때문이다. 이때 무작위 시간 간격을 정하는 것은 또다른 문제이며, 간격이 너무 크다면 활성화된 노드의 수가 적을 때 불필요한 지연을 야기할 수 있고, 간격이 너무 작으면 활성화된 노드의 수가 많을 때 충돌이 재발될 가능성이 높아진다. 이문제를 해결하는 방법이 binary exponential backoff이다. 해당 방법은 이더넷(Ethernet)과 DOCSIS 케이블 네트워크에서 사용된다. 이는 아래와 같이 작동한다.

1. 프레임을 전송하는 어떤 노드가 n번의 충돌을 경험하였을 때, 노드는 K ∈ {0, 1, ..., 2n − 1}를 만족하는 K를 무작위로 선택한다.
   • 즉, 충돌 횟수가 증가함에 따라 K의 최댓값은 기하급수적으로 증가한다.
2. 해당 노드는 충돌을 감지하면 즉시 전송을 중단하고, 대기 시간을 K × 512 bit times으로 설정한다.
   • 즉, 충돌 횟수가 증가함에 따라 대기 시간도 증가한다.
3. 노드가 새 프레임을 전송을 준비할 때는, 이전의 충돌 이력을 고려하지 않고, CSMA/CD 프로토콜 절차를 처음부터 시작한다.

CSMA/CD Efficiency

어떤 채널을 통해 프레임을 전송하려는 노드가 단 하나만 있는 경우, 해당 노드는 채널의 대역폭을 모두 사용할 수 있다. 하지만 여러 노드가 한 채널을 통해 전송하고자 할 경우에는, 채널의 실질적인 전송 속도(effective transmission rate)는 훨씬 낮아질 수 있다. 이때 CSMA/CD의 효율은 다음과 같이 정의된다:

어떤 채널에 대해 많은 수의 노드가 프레임을 보내고자 할때, 
충돌 없이 채널에서 실제로 프레임이 전송되는 시간의 장기적인 비율(long-run fraction)

이를 근사하기 위해 다음과 같은 정의를 사용하자:

• d_prop: LAN에서 두 노드 사이의 최대 전파 지연(propation delay)
• t_trans: 최대 크기의 프레임을 전송하는데 걸리는 시간

위와 같은 정의를 이용하면, CSMA/CD의 효율을 나타내는 근사식은 아래와 같다.

Efficiency = $\frac{1}{1+5\cdot \frac{d_{prop}}{d_{trans}}}$

이 수식으로부터 다음과 같은 사실을 알 수 있다:

• d_prop이 0에 가까워 질수록, 효율성은 1에 가까워진다.
  • 충돌을 경험한 노드는 전송을 즉시 중단(abort)하므로 채널의 낭비가 없다.
• t_trans가 매우 커질수록, 효율성은 1에 가까워진다.
  • 한번 프레임이 채널을 확보하면 오랫동안 채널을 사용하므로, 채널은 대부분의 시간 동안 사용된다.

이는 ALOHA 프로토콜보다 더욱 나은 퍼포먼스를 보여준다. 또한 구현이 간단하고 쌀 뿐만 아니라, decentralized되어 있다.