[컴퓨터 네트워크] Link layer - Multiple Access Protocol

# 컴네 10일차 - 2 

link layer에서의 introduction, service(6.1), error detection & correction(6.3)에 대해서 알아보았다.

link에는 두가지 타입이 있다. point-to-point, broadcast
point-to-point타입은 링크의 한쪽 끝에 송신자가, 다른 끝에 수신자가 존재하는 것이고
broadcast는 동일한 하나의 공유된 브로드캐스트 채널에 다수의 송신 노드 및 수신 노드가 연결된 것이라고 한다.

single shared broadcast channel에서 여러 노드가 하나의 채널을 공유하고 있을 때, 여러 노드가 동시에 데이터를 보내면 충돌이 발생하기 때문에 이러한 환경에서는 multiple access protocol, 다중 접근 프로토콜을 사용한다. 이 프로토콜은 충돌을 방지하기 위해 어떤 노드가 언제 채널에 access하면 좋을지 조절해주는 것이다.

이상적인 mac일 경우 하나의 노드만 있다면 그 노드가 혼자 R의 처리율로 데이터를 전송할 수 있을 것이다. M개의 노드가 있다면 평균적으로 한 노드의 처리율은 R/M일 것이다. 프로토콜은 중앙 조율자 없이 분산된 방식으로 작동해야 하며 구현이 간단해야 한다.

MAC 프로토콜은 세가지 방법이 존재한다.

1. Channel Partitioning
time slot, frequency band, code 등을 기준으로 채널을 나누는 것이다. 채널을 나누어서 전송하므로 충돌이 발생하지 않는다.

2. taking turns
순서를 정해서 보내는 것이다. 이 역시 충돌이 발생하지 않는다.

3. random access
랜덤하게 보내는 방식으로, 충돌이 발생할 수 있지만 회복이 가능하다.

각각에 대해 구체적으로 알아보자.

---

먼저 Channel partitioning을 하는 방법으로는 FDMA가 있다. 다수의 사용자가 주파수를 나누어서 사용하는 것이다. 채널 스펙트럼을 주파수 bands로 나누어서 사용한다. 주파수 자원을 효율적으로 사용할 수 있지만 각 주파수 밴드가 고정되어 있기 때문에 사용되지 않는 주파수 밴드는 낭비될 수 있다.

 

TDMA는 타임슬롯을 기준으로 나누는 것이다. 한 프레임에서 고정 길이의 타임 슬롯을 할당한다. 각 타임 슬롯은 노드들에 할당되고 노드는 전송 패킷이 있을 때마다 자신에게 할당된 타임슬롯에서 패킷 비트를 전송한다. 

---

다음으로는 taking turns 방식이다.
polling 방식은 마스터 노드가 각 노드들에게 순서를 정해주는 방식이다. 마스터 노드가 고장나면 전체 채널이 동작하지 못한다는 문제가 있다. 

token passing 방식은 토큰을 가진 노드만 프레임을 전송할 수 있다. 토큰을 가진 노드가 프레임을 전송하고 다른 노드에게 토큰을 전달하는 방식이다. 이 방식에서도 토큰을 넘겨주는 구조나 노드 하나가 고장나면 전체 채널이 동작하지 못하게 된다는 문제가 있다.

 

---

다음은 random access protocol이다. 노드는 항상 채널의 최대 전송률 R로 프레임을 전송한다. 충돌이 발생하면 일정 시간 동안 기다렸다가 충돌 없이 전송될때까지 재전송한다. 이 방법은 충돌이 발생할 수 있으므로 충돌이 발생했을 때 이를 detection하고 correction해줄 방법이 필요하다.

먼저 pure (unslotted) ALOHA 방식이 있다. 이 방법은 슬롯을 나누지 않으므로 동기화를 시킬 필요가 없어서 단순하다. 프레임이 도착하면 노드는 이를 즉시 전송한다. 충돌이 발생하면 충돌된 프레임을 완전히 전송한 후에 p의 확률로 프레임을 재전송한다. 충돌이 발생하지 않으면 노드는 프레임 전송 시간을 기다린 후 확률 p로 프레임을 전송한다. 하지만 pure ALOHA 방식은 충돌 가능성이 너무 높다는 문제가 있다. 아래 그림을 보면 프레임의 시작 또는 끝이 겹쳐서 충돌이 발생하는 상황을 확인할 수 있다.

---

그래서 Slotted ALOHA 방식이 나왔다. 이는 슬롯을 나눠서 전송의 시작과 끝을 맞춰주는 것이다.

모든 프레임의 크기는 동일하고 시간은 동일한 크기의 슬롯으로 나누어진다. 노드는 슬롯이 시작할 때만 전송을 시작하므로 전송의 시작과 끝을 모두 맞춰줄 수 있다. 두 개 이상의 노드가 동일한 슬롯에서 전송을 시작하면 모든 노드는 충돌을 감지한다. 

노드가 새로운 프레임을 얻으면 다음 슬롯에서 전송을 시작한다. 충돌이 발생하지 않으면 노드는 다음 슬롯에서 새로운 프레임을 전송할 수 있고, 충돌이 발생하면 노드는 각 후속 슬롯에서 일정 확률 p로 프레임을 재전송한다.

활성 노드가 하나인 경우 채널의 최대 속도로 전송을 할 수 있고 구조가 단순하지만, 충돌이 발생하거나 사용하지 않고 빈 슬롯인 경우가 생긴다는 단점이 있다.

---

CSMA(Carrier Sense Multiple Access)는 캐리어를 감지한다. 캐리어는 네트워크 채널(매체)을 의미하는 것이다. 보내기전에 채널을 listen하고 busy이면 누군가 다른 노드가 이 채널을 쓰고 있으니까 조금 더 기다렸다가 idle해지면 보내는 것이다. 보내기 전에 센싱을 해본다는 점에서 충돌 확률을 낮춰준다.

하지만 모든 문제가 해결된 것은 아니다. 그림의 노드들을 순서대로 A, B, C, D라고 하자. 이때 노드 B에서 채널을 사용하기 시작했다. t1시점에 노드 D도 채널을 사용하고 싶어 listen했는데 아무도 채널을 사용하고 있지 않았다. 사실 B가 채널을 사용하고 있지만 전파 지연(propagation delay) 때문에 아직 노드 D가 알 수 없었던 것이다. 노드 D는 채널이 idle한 상태이므로 프레임을 보냈는데, 이는 곧 B가 보내고 있던 프레임과 충돌이 일어나서 다 깨지게 된다. 어쩔 수가 없다. 노드 D는 채널 상태를 확인하고 idle하다길래 보냈을 뿐이다.
간단히 다시 정리하면 listen 하고 idle 이라길래 전송을 했는데 전파지연 시간으로 인해 나중에 busy가 되어 충돌이 발생할 수도 있다는 것이다.

여기서 충돌 발생 후에 프레임을 계속해서 보내주는 시간이 낭비되는 것 같다. 충돌한거라 다 깨져있을 것이므로 어차피 나중에 다시 보내주어야 하는데 이미 깨진 프레임을 보내는데에 리소스를 계속 사용하고 있을 필요가 없다. 이미 충돌이 났으면 의미가 없으므로 끝까지 계속 전송할 필요가 없다.

 

---

그래서 CSMA/CD(Carrier Sense Multiple Access / Collision Detection)가 등장했다. 이 알고리즘은 CSMA 방식에서 충돌이 감지되면 전송을 중단하여 채널의 낭비를 줄인다.

유선 LAN에서는 신호 세기를 측정하고 전송된 신호와 수신된 신호를 비교하여 쉽게 충돌을 감지할 수 있으나 무선 LAN에서는 수신된 신호 세기가 로컬 전송 신호 세기에 의해 압도되어 충돌감지가 어렵다. 따라서 충돌 감지가 어렵다는 무선 LAN의 특성 때문에 무선에서는 CSMA/CD를 사용하기가 어렵다. 따라서 CSMA/CA(Collision Avoidance)를 사용한다. 충돌을 감지하는 대신, 충돌을 피하려고 한다. 이 방법에 대해서는 추후에 무선에 대해 더 깊게 배우며 다시 알아볼 것이다.

CSMA/CD 프로토콜은 이더넷 네트워크에서 사용된다. (이더넷이란 같은 지역의 네트워크(LAN, Local Area Network)를 유선으로 구현하는 기술 중 하나, 가장 많이 쓰이는 기술이다.) 이더넷 네트워크에서 CSMA/CD 알고리즘이 사용되는 단계에 대해 알아보자

1. NIC(네트워크 인터페이스 카드)가 네트워크 계층으로부터 데이터그램을 수신하고 이를 프레임으로 만든다.

2. NIC가 채널이 idle 상태라는 것을 감지하면 프레임 전송을 시작한다. 만약 채널이 busy상태라는 것을 감지하면 채널이 idle할때까지 기다렸다가 전송한다.

3. NIC가 다른 전송을 감지하지 않고, 프레임을 모두 전송하면, 전송이 완료된다.

4. NIC가 전송 중에 다른 전송을 감지하면, 전송을 중단하고 혼잡 신호(jam signal)을 보낸다.

5. 전송 중단 후 NIC는 이진 백오프 단계에 들어간다. backoff는 충돌이 발생했을 때 얼마나 더 기다렸다가 보낼 것인가?에 대한 것이다. 충돌 횟수가 많을수록 백오프 간격이 길어진다.