Carrier Sense Multiple Access (CSMA)
CSMA 란?
CSMA는 Carrier Sense Multiple Access의 약자로, 데이터를 통신 매체에서 전송하는 방법을 관리하는
네트워크 프로토콜이다.
위 그림은 통신 중 발생하는 충돌의 예시이다.
B는 t1에 safe를 확인하고 데이터를 보냈고, C또한 t2 시점에, B가 보낸 데이터가 도착하지
않은 상태이기에 safe를 확인하고 데이터를 보냈지만 두개의 데이터가 충돌!
CSMA는 이러한 문제를 완화하기 위한 방법이다.
Vulnerable time
좀 전 예시에서 B가 데이터를 보냈음에도 C가 무시하고 데이터를 보낼 수 있었던 건
B의 데이터가 전송중인 상태로 C에 아직 도달하지 않았기 때문이다. Propagation time만큼 전송하는데
시간이 소요되면서 데이터가 보내졌음에도 이를 알지 못한 것이다.
이때의 Propagation time을 Vulnerable time이라고 한다.
위 그림에서 D는 t1 + tv(Vulnerable time)에 데이터를 전송받게 된다.
다음은 Sender가 channel이 Idle임을 감지했을 때 Data를 언제 보낼지에 대한 메커니즘들이다.
1-Persistent
node가 채널을 계속 감시하다가 채널이 비어있는 것이 확인되면 확률 1로 즉시 전송한다.
채널이 사용중이라면 대기한다.
매우 단순한 형태.
Non-Persistent
채널을 감시(Sensing)하면서 기다리는 것까지는 동일.
채널이 비어있으면 즉시 전송.
채널이 비어있지 않으면 랜덤한 시간만큼 기다리고 다시 시도함.
랜덤한 시간만큼 기다리기에 충돌을 줄일 수 있지만 대기시간이 많이 걸릴수 있음.
Collision이 발생한 이후, random 시간만큼 기다리고 다시 시도한다.
P-Persistent
channel 이 time slot을 가지고 있을 때(그리고 slot duration이 maximum propagation time보다 클 때)
사용된다.
node가 channel을 sensing한다.
만약 channel이 idle 상태라면 p의 확률로 다음 slot 시작 시점에 전송한다.
전송하지 못했다면(q = 1 - p), 다음 슬롯을 기다렸다가 다시 시도한다.
만약 채널이 busy한 상태라면 collision으로 간주하고 back-off time(다음 time slot) 만큼 기다린다.
이상으로 1-persistent, non-persistent, p-persistent를 정리해보았다.
CSMA는 CSMA/CD와 CSMA/CA가 있다.
Collision Detection (CSMA/CD)
station은 medium을 frame이 보내진 후 모니터링 한다. 이 작업은 전송이 잘 되고 있는지 확인하는 것이다.
만일 전송이 잘 이루어졌다면 station은 끝나게 된다.
collision이 발생하면 frame은 다시 보내도록 설계된다.
위 그림은 CSMA/CD가 작동하는 과정을 더 자세하게 나타낸 것이다. K는 시도 횟수라고 보면된다. 시도 횟수가 너무 많아지면 그냥 Abort 시킨다. jamming signal은 tx를 abort하도록 하는 신호이다.
여기서 더 고려해야 할 사항이 있다. station은 전송이 끝나면 그냥 사라져버리는데, frame의 마지막
비트까지 전부 보내게 되면 station이 종료되기에 더 이상 monitoring을 할 수가 없다. 그래서, station이 충돌을
감지할 시간을 충분히 줘야 한다.
그래서 프레임 전송시간 Tfr은 Tp(전송시간)의 2배 이상이어야 한다.
bandwidth가 정해져 있을 때 Tfr은 frame의 사이즈에 의해 결정된다.
따라서 frame의 사이즈가 최소 얼마나 되어야 하는지를 정할 수 있게 된다.
(min frame size = bandwidth x Tfr)
Energy Level
위 그림은 CSMA/CD에서 sender(Network Interface Card(NIC))가 collision을 detection할 때
energy level을 사용하는데, 이를 나타낸 것이다.
3가지 타입이 있겠다.
zero: channel 이 idle 상태
normal: frame을 보내는 상태
abnormal: collision상태. normal보다 2배 정도의 에너지 차이를 보임.
node가 transmit할 data가 있을때, cable의 energy level이 zero인지 확인한다.
zero라면 데이터를 보낸다. 계속 상태를 모니터링 한다.
collision을 detection하는 순간 transmition을 멈추고 32 bit jamming signal을 보낸다.
jamming signal은 다른 노드들이 collision이 있다는 것을 알게 해준다.
Throughput(처리량)
처리량은 네트워크가 데이터를 성공적으로 전달할 수 있는 비율을 의미한다.
Pure ALOHA, Slot ALOHA 보다 CSMA/CD의 처리량이 더 높다.
아래에 나오는 G는
G : 시스템이 한 프레임 전송 시간 동안 생성하는 프레임의 평균수
이다.
1-persistent 방식
- 최대 처리량 약 50%
- G = 1
- 충돌 발생 가능성이 있지만 재전송을 통해 효율을 유지.
non-persistent 방식
- 3 < G < 8일 때
- 90% 정도의 처리량.
Collision Avoidance(CSMA/CA)
이름에서 알 수 있듯이 collision을 미리 예방하는 방법이다.
wireless LANs에서 사용된다.
frame을 보내기 전에 collision을 미리 예방하는 방법인데, 3가지 전략을 사용한다.
- The interframe space (IFS)
- The contention window
- Acknowledgements
먼저 RTS(Request to Send) and CTS(Clear to Send)를 다룰 것이다.
RTS: Request To Send
CTS: Clear To Send
RTS로 채널 사용이 가능한지 요청한다.
위 그림에서 RTS를 받은 노드 B는 채널이 clear하면 CTS를 보낸다.
CTS를 받은 A를 제외한 다른 노드들은 NAV(Network Allocation Timer)를 생성한다.
A가 data를 성공적으로 보내고, B가 이를 제대로 받았다면 ACK를 보낸다.
ACK를 받은 노드들은 다시 평상시로 돌아가게 된다.
위 그림은 CSMA/CA flow를 나타낸 것이다.
여기서 Channel이 idle일 때 IFS만큼 기다린다는 내용이 있는데, 이건 왜 그런 걸까?
channel이 idle로 평가되더라도 실제로는 idle이 아닐 수도 있기 때문이다. 아직 도달하지 않은 것일 수
있으니 잠깐 기다렸다가 보내는 것.
Interframe space (IFS)
IFS time만큼 기다린 후, 보낸다.
Interframe space, 프레임 사이의 간격 시간을 의미한다.
IFS 이후에도 Contention window를 기다려야 한다.
Contention window (CW)
Contention window는 시간을 slot으로 나누어진 것이다.
보내는 node는 랜덤 슬롯을 고른다.
Collision이 발생할 때마다 기다리는 slot의 수는 지수적으로 증가한다.
Acknowledgement
이렇게 해도 collision은 언제든 발생할 수 있다. data corruption이 발생할 가능성도 배제할 순 없다.
ACK는 전에도 배운적이 있었는데, 데이터를 성공적으로 수신받은 쪽에서 ACK를 송신해 데이터가
정상적으로 전달되었음을 알리게 된다.
이제 전체적으로 CSMA/CA를 정리해보겠다.
보낼 data frame을 가지고 있는 sender A는 앞에서 배운 persistent 방법 중 하나를 이용해 channel의 상태를 점검한다.
channel이 idle이라면 DIFS(Distributed Coordination Function Interframe Space) 만큼 기다리고 RTS(Request to send)를 Receiver B에게 보낸다.
B는 RTS를 받은 후 SIFS(Short Interframe Space)만큼 기다린 후 CTS(Clear to Send)를 다른 노드와 A에게 보낸다.
A는 CTS를 받고 SIFS만큼 기다린 후 data를 보낸다.
B는 data를 받은 후 SIFS 만큼 기다리고 ACK를 보낸다.
앞에서도 나왔지만 NAV(Network Allocation Vector)란 무엇일까?
A가 데이터를 보낼 때 다른 노드들이 얼마나 기다려야 하는지를 명시한 것이다.
RTS와 CTS에는 NAV timer의 값이 포함되어 있다.
노드가 NAV를 받으면 지정된 시간 만큼 timer를 설정하고 그 동안 데이터를 송신하지 않는다.
이를 사용해 충돌을 방지할 수 있다.
CSMA/CA의 다른 Collision 상황들
Handshaking Collision
RTS또는 CTS가 서로 충돌하면 어떻게 될까?
이런 상황을 Handshaking이 발생했다고 표현한다.
이때는 다른 Collision detection mechanism이 필요치 않다.
어처피 sender는 CTS가 돌아오지 않으면 데이터를 다시 송신할 준비를 하기 때문이다.
Hidden Station Problem
A와 C가 서로를 인지하지 못하는 상황일 때, B로 RTS를 동시에 보내는 상황이다.
이때는 RTS가 B로 다른 방향에서 접근하기에 B는 둘 중 하나의 RTS를 먼저 받게 된다.
A의 RTS를 먼저 받았다면 CTS를 보내게 되고, C가 CTS를 받게 되면 일정 시간 동안 송신을 멈출 것이므로 - NAV
문제가 발생하지 않는다.
Exposed Terminal Problem
위 그림에서 B가 A에게 보내려고 한다.
C는 D에게 보내려고 한다.
B가 보낸다는 소식(CTS)에 C는 송신을 멈춘다.
그런데 C가 D에게 데이터를 보내는데 있어 B의 송신을 방해하지 않는다. 그럼에도 송신을 멈추게 된다.
이때 C를 exposed terminal to "from B to A"라고 부르게 된다.