[네트워크] CSMA (Carrier-Sense Multiple Access)

나뭇잎으로코딩·2024년 6월 20일
네트워크

네트워크

목록 보기
2/7

데이터 링크 레이어의 Medium Access Control 중, Random Access protocol의 한 종류인 CSMA에 대해 알아보자.

CSMA (Carrier Sense Multiple Access)

  • ALOHA (pure/slotted)에서는, 노드는 다른 노드가 전송 중이어도 전송을 시작한다.
  • 운이 좋으면 다른 노드가 나의 vulnerable time period에 전송을 하지 않지만, 운이 나쁘면 충돌이 일어난다.

→ 만약 medium(channel)을 센싱할 수 있는 하드웨어가 있다면, 충돌을 줄일 수 있을 것이다.

→ CSMA : “말하기 전에 듣는다”

  • 노드가 전송할 프레임이 있으면, 먼저 채널을 감지한다.
  • 채널에 다른 시그널이 없으면 (idle), 전송한다.
  • 채널에 다른 시그널이 있으면 (busy), 전송하지 않는다.

그렇다면 CSMA가 충돌을 완전히 방지할 수 있을까? 그렇지 않다.

  • B가 t1에 전송하면, 이 신호는 t3에 C에 도착한다.
  • t2에, C는 채널이 idle로 보인다.
  • C가 t2에 전송한다면 충돌이 발생한다.

  • 즉, 한 노드의 propagation time동안 다른 노드가 전송한다면, 충돌 발생
  • 2명이 동시에 전송하는 경우 서로 채널이 idle이라고 판단하는 경우

→ Vulnerable time: Tp\text{T}_\text{p} = propagation time = t3 - t1
(일반적으로, 시스템에서 가장 멀리 있는 노드의 전파시간)


  • Transmission delay와 Propagation delay (참고)
    • Transmission delay: source에서 첫 번째 비트가 떠나는 시점 ~ 마지막 비트가 떠나는 시점
    • Propagation delay: 비트가 source에서 destination까지 이동하는 데 걸리는 시간

채널을 관측했을 때 busy라면, 노드는 무엇을 해야할까?
이때 노드의 행동에 따라, CSMA는 3종류로 나뉜다.

  1. 1-persistent CSMA
  2. non-persistent CSMA
  3. p-persistent CSMA

1-persistent CSMA

  • 채널이 busy인 동안 계속해서 채널을 관측한다.
  • 채널이 idle이 되는 순간 바로 전송한다.
  • 여러 노드가 채널이 idle이 되기를 기다릴 수 있기 때문에, 충돌 확률이 크다.

Non-persistent CSMA

  • 채널이 busy이면, 노드는 일정 시간 기다렸다가 다시 채널을 관측한다.
  • 관측했을 때 채널이 idle이면 전송한다.
  • 충돌 확률은 낮지만, 노드는 채널이 idle이 된 후에도 기다리느라 시간을 낭비할 수 있다.

p-persistent CSMA

  • 채널이 busy이면, 채널이 idle이 될 때까지 계속해서 채널을 관측한다.
  • 채널이 idle이 되면,
    • 노드는 p확률로 전송한다.
    • 1-p확률로 전송을 미룬다.

CSMA/CD (Collision Detection)

  • Collision Detection: 충돌 발생 시 송신자가 충돌을 감지하고 대응한다.
  • Ethernet에서 사용된다.
  • Collision situation: 노드 A가 프레임을 전송했지만, 해당 프레임이 C에 도착하기 전에 C가 전송해버렸다.
  • 이런 상황에서 노드가 어떻게 충돌을 감지할 수 있을까?
    → 내 프레임을 전송하는 동안 다른 프레임이 도착했다면, 충돌을 감지할 수 있다.

  • 성공적인 충돌 감지

    • 충돌 발생 시, 노드는 그것을 감지할 수 있어야 한다.
    • 충돌된 프레임이 도착했을 때, 나는 내 프레임을 전송하고 있어야 한다.
    • 내 전송이 너무 일찍 끝나면, 충돌을 감지하지 못할 수 있다.

  • Condition for collision detection failure

    • A가 t1에 보낸다.
    • C가 t2에 보낸다 → A의 프레임과 충돌
    • 충돌된 프레임이 A에 t4에 도착한다.
    • A가 t4가 되기 전에 전송을 끝낸다면, A는 충돌을 감지하지 못한다.

그렇다면 A는 얼마나 긴 시간동안 전송해야 할까?

  • A가 t1에 전송을 시작한다면, 첫 비트는 C에 t1+tp에 도착한다.
  • C가 t1+tp 이전에 전송한다면, 충돌이 발생한다.
    • C는 carrier sensing 때문에, t1+tp 이후에 전송할 수 없다.
  • t1+tp 바로 직전에 C가 전송했다고 해보자.
  • 충돌난 프레임은 A에 t1+2tp에 도착한다.
  • t1 + 2tp에, A는 여전히 전송중이어야 한다.
  • 따라서, tfr≥2tp\text{t}_\text{fr} \ge 2\text{t}_\text{p} 을 만족해야 충돌을 감지할 수 있다.
    (transmission time ≥ 2 * propagation time)

즉, A의 전파시간(A가 보낸 비트가 C에 도달하는 시간) + C의 전파시간(C가 보낸 비트가 A에 도달하는 시간)보다, A가 긴 시간동안 전송해야 한다 (A의 transmission time = A가 모든 비트를 채널에 쏘는 데 걸리는 시간).

충돌이 감지되었을 때 → Binary exponential backoff (ALOHA와 유사한 방식)

  • Examples
    A network using CSMA/CD has a bandwidth of 10Mbps. If the maximum propagation time is 25.6μs, what is the minimum size of the frame?

tfr≥2tp\text{t}_\text{fr} \ge 2\text{t}_\text{p}

frame size (num of bits)bandwidth(bps)≥Sender-Reciever distancepropagation speed\displaystyle \frac{\text{frame size (num of bits)}}{\text{bandwidth(bps)}} \ge \displaystyle\frac{\text{Sender-Reciever distance}}{\text{propagation speed}}

위 수식에서 의도적으로 조절할 수 있는 것은 frame size 뿐이다.

F10×106≥2×25.6×1106\displaystyle\frac{F}{10\times10^6} \ge 2\times25.6\times\frac{1}{10^6}

F≥512F \ge 512 (bits)

F = 64 byte

CSMA/CA (Collsion Avoidance)

  • 충돌을 감지할 수 없는 시스템에서 사용된다
  • Wi-Fi에서 사용된다.
  • 와이파이 인터페이스는 half-duplex이다. 즉, 동시에 전송하거나 수신할 수 없다. → CSMA/CD를 통해 충돌을 감지할 수 없다.
  • 충돌이 발생하면 random backoff를 한다.
  • ACK를 기다린다.
  • ACK가 오지 않으면 충돌로 간주한다 → backoff를 지수적으로 증가시킨다.
  • IFS (Inter-Frame Spacing)
    • 채널이 idle로 관측되었더라도, 다른 노드가 막 전송을 시작했을 수 있다. 이러한 충돌을 방지하기 위해 IFS를 삽입한다. (idle이어도 잠깐 기다렸다가 전송)

  • Contention window
    • 노드가 랜덤넘버를 뽑는 범위이다 (e.g. 0-31)
    • 노드는 contention window에서 숫자를 선택한다.
    • 각 time slot마다, 채널이 idle이라면 숫자를 카운트다운한다.
    • 숫자가 0이 되면, 전송을 시작한다.

    • Contention window의 크기 = R x time slot
    • 노드가 랜덤으로 15을 선택했다고 하자. (time slot = 20us)
    • 채널이 15*20=300us동안 idle이면, 노드는 전송한다.
    • 카운트다운을 하는 동안 채널이 busy가 된다면, 노드는 채널이 다시 idle이 될 때까지 정지한다.
    • 채널이 idle이 되면 노드는 IFS동안 기다리고 다시 이어서 카운팅을 시작한다.

  • Binary exponential backoff
    • 충돌이 발생하면, contention window size는 2배가 된다 (0-31 → 0-63)
    • 프레임이 성공적으로 전송되면, contention window size는 초기 범위로 돌아간다.

Example

  • Assumptions

    • time slot = 20us
    • IFS = 50us
    • initial contention window: [0-31]
    • transmission time of a frame = 100us
    • propagation time = 0 (neglected)
    • no ACK

  • 노드 A, B, C가 같은 무선LAN에 있다. A가 전송하면, B와 C가 모두 시그널을 볼 수 있다.

  • 0us: ABC 모두 보낼 프레임이 있다. 모두가 IFS(50us)를 기다린다.

  • 50us: ABC가 랜덤넘버를 고른다. A는 10, B는 15, C는 20을 골랐다. 카운트다운을 시작한다.

  • 250us: A의 카운터가 가장 먼저 0이 된다. A가 전송을 시작한다 (transmission time 100us동안 전송). B와 C는 A의 시그널을 보고 카운트다운을 중지한다.

  • 350us: A의 전송이 끝난다. B와 C는 채널이 idle이 되었음을 보고, IFS를 기다린다.

  • 400us: B와 C는 카운팅을 재개한다. B의 카운터는 5, C는 10이 남아있다.

  • 500us: B의 카운터가 0이 되어 전송을 시작한다. C는 카운팅을 중지한다.

  • 600us: B의 전송이 끝난다. C가 IFS를 기다린다.

  • 650us: C가 카운팅을 재개한다. 5가 남아있다.

  • 750us: C가 전송을 시작한다.

  • 850us: C가 전송을 마친다.

Summary

CSMA: 전송 전에 채널을 관측해서 idle이면 보내고, busy이면 보내지 않는다
Vulnerable Time = propagation time (한 노드가 채널에 보내는 동안 다른 노드가 채널을 관측하여 idle로 판단하고 전송하면 충돌이 발생한다)

1-persistent: busy이면 계속 관측하다가 idle이 되자 마자 보낸다
n-persistent: busy이면 일정 시간 기다렸다가 관측한다. 관측시 idle이면 보낸다
p-persistent: busy이면 계속 관측하다가 idle이 되면 p확률로 보낸다.

CSMA/CD (Collision Detection):

  • 내 프레임을 전송하는 동안 다른 프레임이 도착하면 충돌을 감지할 수 있다.
  • Ethernet에서 사용된다.
  • transmission time ≥ 2 * propagation time

CSMA/CA (Collision Avoidance)

  • 채널이 idle이면, IFS를 기다리고, 자신의 contention window 크기 (R*time slot)만큼 카운트다운한 후 전송한다.
  • 카운트다운 하는 동안 채널이 busy가 되면 카운팅을 일시 정지한다. idle이 되면 멈췄던 부분부터 다시 카운트다운한다.
  • Wi-fi에서 사용된다.
profile
나뭇잎으로코딩
이전 포스트

[네트워크] ALOHA protocol

다음 포스트

[네트워크] Controlled Access

0개의 댓글