A Scenario for Multiple Access among Stations
- 각 MS(Mobile Station)에는 송/수신기가 부착되어 있고, 각 노드에 공유된 채널을 통해 통신한다.
- Broadcast channel: 한 노드의 전송이 모든 노드에 전달 가능한 채널 -> 1 to all
- 1개 이상의 MS가 송신을 시도하면 collision(충돌)의 위험이 있다.
- 이러한 충돌을 막기 위해 다중 접속 시 공유 규칙을 정해 놓은 프로토콜인 Multiple Aceess Protocol로 충돌 감지와 충돌 해결을 실시한다.
Multiple Access Protocols
Multiple Aceess Protocol는 Medium Access Control (MAC) Protocol라고도 부른다. (2계층)
- 정의: 다중 MS에게 공정하고 효율적으로 자원(채널, BW 등)을 공유하도록 하는 프로토콜
- Different types:
- Contention protocols(경쟁 프로토콜): 충돌이 발생하고 난 후 이를 해결하는 프로토콜.
- Collision-free protocols(충돌 없는 프로토콜): 충돌이 전혀 발생하지 않음을 보장하는 프로토콜. 예를 들어 bit-map protocol과 binary countdown 등이 있다.
Medium-Sharing Techniques
채널을 공유하는 방식은 크게 2가지로 나눌 수 있다.
- Static allocation(정적 할당): 노드에 고정된 채널 크기를 할당한다. 데이터 통신 측면에서는 적합하지 않다.
- Dynamic allocation(동적 할당): 노드가 요구하는 정도에 따라 동적으로 채널 자원을 할당한다. 동적 할당은 크게 2가지로 또 나뉜다.
- Scheduled: 스케쥴러(대장 노드)가 누가 채널을 얼마나 쓸 지를 결정한다.
- Random access: 경쟁을 통해 채널을 할당해 사용한다. 가장 많이 쓰는 방법이다.
Multiple Access Protocols
Bit-Map Protocol
- 각 MS마다 데이터가 있음을 표시한다. 채널을 사용할 경우 slot 별로 1을 표시한다.
- 1이 표시된 slot을 파악하여, 프레임을 숫자 순서대로 전송한다.
Token Ring Protocol
- 각 MS는 Token(전송 허가권)이라 불리는 작은 메시지를 가지고 있어야만 통신이 가능하다. 수건 돌리기 하듯이 각 MS가 토큰을 넘기며 전송권을 돌아가면서 쓰기 때문에 collision이 발생하지 않는다.
- 프레임을 전송하고 싶은 경우 다른 MS로 Token을 전달하기 전에 전송을 실시한다.
- Token을 돌아가면서 전달받는 구조이기 때문에 queue에 프레임이 쌓이지 않는다.
Binary Countdown
- MS가 채널 사용을 원하면 각자의 2진수 주소를 브로드캐스트한다. 이후 노드 별로 전송한 각자의 MAC Address를 비교하여 전송 우선순위를 부여한다.
- Bit의 MSB부터 순서대로 크기를 비교한다. 1이면 win, 0이면 lose
Binary Tree Walk Protocol
- 이전에 설명한 프로토콜들보다 어느정도 비중이 있다.
- 충돌이 발생하면 그룹을 2개씩 나누어 우선순위를 결정한다.
- 방식 (총 8개의 Station이 있고, 처음에 동시에 전송 시도를 한다고 가정)
- Slot 0(Time이라고 생각, 위 그림에서 1 -> 2, 3번으로 갈라지는 부분): 모든 Station이 채널을 사용하기를 원한다. 2개 이상의 station이 채널 사용을 요청하면 충돌이 발생하여 Random하게 0과 1의 카운트를 부여하여 그룹을 분리한다.
- Slot 1: 아직 2개 이상의 station이 채널 사용을 요구하기 때문에 다시 한번 랜덤하게 카운트를 부여하여 그룹을 나눈다.
- Slot 2: 아직 2개 이상의 Station이 채널 사용을 요구한다. 다시 한번 서브트리를 기준으로 2개의 그룹으로 station을 분리한다. 맨 마지막 부분이 모든 스테이션이 우선순위로 분리되어 충돌이 발생하지 않는 상황이다.
- Binary Tree Walk Protocol의 철학
- Binary Tree Walk Protocol은 깊이 우선 프로토콜이다. 따라서 Slot 0에서 충돌이 발생하여 그룹이 나뉜 경우, 왼쪽(우선순위가 높은)부터 충돌을 해결한다. 1 -> 2 -> 4 -> A,B -> 5 -> C,D -> 3 -> 6 ...
- 만약 어떤 Station도 전송을 시도하지 않는 idle 상태나, 한 개의 Station만 전송을 시도하는 경우에는 깊이 우선 탐색은 종료된다.
ISO 18000-6 Type B RFID System
- 태그는 태그 ID 번호를 방출하고 리더는 RFID 고유번호를 조회한다.
- RFID 시스템을 예로 들어 위의 프로토콜을 설명한다. 태그들이 존재하고 각 태그들은 리더기로 본인의 태그를 전송하려 한다.
- SELECT 명령을 받으면 태그들은 각자의 Count 값을 확인한다. 0의 Tag Count를 갖는 태그들은 모두 전송을 시도한다. 당연하게 Collision이 발생한다. Reader는 충돌이 발생함을 알지만 Tag들은 충돌 발생 여부를 모른다.
- 충돌이 발생하면 리더가 다음 Slot이 시작하기 전에 Fail을 각 태그로 보내게 된다. 이 때 각 태그들은 랜덤하게 0과 1 중 하나의 값을 Tag Count에 더한다.
- 랜덤으로 발생하였음에도 0의 Tag Count를 갖는 태그들이 존재하는 경우 다시 한번 FAIL 명령을 리더가 전송하고 랜덤으로 Tag Count를 증가시킨다. 이 때 이미 1 이상의 Tag Count를 갖는 태그는 고정적으로 1을 증가시킨다.
- 모든 Tag Count가 1 이상인 경우 전송이 일어나지 않는다. (idle 상태) 이 때는 모든 Tag Count를 1 감소시킨다.
- 이를 반복하여 1개의 태그의 Count만 0이어서 충돌이 발생하지 않을 때 DATA_READ 명령이 리더로부터 전송되고 0의 Count를 가진 태그가 이를 받아 전송을 시도하여 리더가 태그의 정보를 인식하게 된다.
- 이렇듯 이진트리 프로토콜은 간단히 8-bit Counter와 Random number 발생기 2개로 구현이 가능하다.
- 위는 각 Slot 별로 태그들의 전송 시도 과정을 나타낸 것이다.
- 보통 위와 같은 경쟁에서는 짧은 데이터를 이용하여 진행하고 경쟁에서 승리하면 본인의 진짜 데이터인 고유 ID를 보낸다.
Aloha
- 1970년 하와이 대학교에서 개발되었으며, Station을 네트워크에 최초로 알릴 때 사용하는 간단한 프로토콜이다.
- 프로토콜 방식은 매우 간단하다.
- 데이터가 있으면 일단 전송을 한다. 충돌 발생 시 충돌 제거 프로그램이 실행된다.
- 목적지 Station으로부터의 브로드캐스트를 확인하여 Sender가 전송에 충돌이 있는 지, 없는 지를 찾는다.
- 만약 충돌이 일어나면 Sender가 랜덤 시간을 각 Station으로 전송하여 전송 시간을 분리시켜 충돌을 해결한다.
- MS 1에 데이터가 발생하여 바로 전송을 시작한다. MS 1에서 보낸 데이터는 성공적으로 전송됐다.
- MS 2에 데이터가 발생하여 전송을 시작했으나 중간에 MS 3가 전송을 시도하여 충돌이 발생했다.
- 충돌에 의해 랜덤 시간이 각 MS로 전송되어 전송 시간까지 기다린다. 짧은 랜덤 시간을 부여받은 MS가 먼저 전송을 시도한다.
- N ~ Uniform으로 전송 시간을 랜덤으로 발생시킬 때 랜덤 값의 상한을 고정하면 패킷이 많아지면 충돌이 늘어나기 때문에 충돌이 거듭될수록 8 -> 16 -> 32 -> 64 .. 처럼 랜덤 시간의 상한을 늘리는 방법이 선호된다. 이렇게 Adaptive하게 시스템을 적용하는 이유는 처음부터 128과 같은 큰 랜덤 시간을 상한으로 두는 경우, 랜덤 숫자를 고르는데 걸리는 지연 시간이 길어지기 때문이다.
- Aloha의 Maximum throughput은 0.184로 100개의 slot 중 약 18개의 slot에서만 전송 성공이 이뤄진다.
- Throughput이 낮더라도 꼭 나쁜 것이 아닌 게, Aloha는 Simple하기 때문에 Robust하다.
- 패킷이 늘수록 충돌이 많아져서 오히려 효율이 감소한다. -> 시간 증가
Carrier Sense Multiple Access(CSMA)
다른 패킷이 먼저 전송하고 있는 지를 확인하는 프로토콜이다.
- Aloha의 낮은 Throughput을 보완하기 위해 고안됐다.
- 채널 공유로 인해 야기될 수 있는 충돌 문제를 사전에 방지하여 Throughput을 높이고자 한다.
- 이는 "listen-before-talk"라고도 불린다.
CSMA의 방법은 다음과 같다.
- 1) Data 도착
- 2) Carrier Sensing 수행
- Busy: 누가 쓰고 있음 -> busy는 또다시 3가지 종류로 구분된다. 이는 후술
- Idle: 아무도 안 쓰고 있음
- 3) 수신확인(Ack)
그러나, CSMA는 충돌을 방지하기 위해 사용하는 프로토콜이지만 무조건 피할 수 있는 것은 아니다.
B가 t0라는 시간에 idle이어서 전송을 시작했으나 Propagation Delay에 의해 D까지 B의 전송 소식이 전달되지 않아서 D에서는 t1라는 시간에 idle 상태로 전송을 시작한다. 이때 충돌이 발생한다.
CSMA의 종류
Non-persistent CSMA
- Step 1: 만약 채널이 idle 상태라면, 전송을 즉시 수행한다. (p=1)
- Step 2: 만약 채널이 busy 상태라면, 랜덤 시간을 발생하고 그만큼 기다린 후에 Step 1을 다시 수행한다.
- 랜덤 시간을 발생시켜 후순위로 보냄
- Backoff(뒤로 보내기)로 인해 채널 용량이 낭비되는 문제가 있다. 바로 바로 전송을 하는 게 좋으며, 트래픽 부하가 적은 경우 낭비가 심하다.
1-persistent CSMA
- Step 1: 만약 채널이 idle 상태라면, 전송을 즉시 수행한다.
- Step 2: 만약 채널이 busy 상태라면, 계속 Carrier Sensing을 수행하고 idle 상태가 되면 전송을 수행한다.
- 패킷의 트래픽이 적으면 효율적이나 2개 이상이 busy인 상황이라면 끝나고 그 busy끼리 충돌이 다시 발생하는 문제가 있다.
p-persistent CSMA
- Step 1: 만약 채널이 idle 상태라면
- p라는 확률로 전송을 한다.
- 1-p의 확률로 전송하지 않는 경우 지연 시간을 발생시킨다.
- Step 2: 만약 채널이 busy 상태라면, 계속 Carrier Sensing을 수행하고 idle 상태가 되면 Step 1을 수행한다.
- Step 3: 지연 시간이 모두 지나면 Step 1을 다시 수행한다.
- p-persistent CSMA는 트래픽 양에 따른 함수를 가지며 매우 유동적인 현재의 모바일 네트워크와 가장 흡사하다.
Performance Trade-off
- 트래픽 양에 따라 CSMA 중 무엇이 좋은 지가 달라진다.
- Case 1: 노드 A가 전송 중일 때 노드 B와 C가 전송을 시도
- 1-persistent: idle이 될 때 B와 C가 충돌을 일으킨다.
- non-persistent: B와 C가 충돌을 안 일으킬 수도 있다. -> 더 적합
- Case 2: 노드 A가 전송 중일 때 노드 B만 전송을 시도
- 1-persistent: idle이 되면 즉시 전송을 시도한다. -> 더 적합
- non-persistent: 전송 딜레이가 발생한다. 즉시 전송을 안 해서 효율이 낮아질 수 있다.
- 패킷 전송 시간 별 패킷의 양에 따른 Throughput을 나타낸 그림이다.
- 그런데 여기서 G=9가 의미하는 것은 패킷 전송 시간 당 9개 중 1개밖에 보내지 않는 것을 의미하므로 G=1.5까지의 Throughput만 의미있게 보자.
CSMA/CD
CSMA에 Collision Detection이 추가되었다.
- CSMA에서 2개의 터미널이 동시에 패킷 전송을 시작하면 각각은 전체 패킷을 전송한다. (충돌 발생하더라도 전송)
- 전송이 시작되면 채널 모니터링을 시행하여 충돌 발생 여부를 판단한다.
- 충돌 발생 시 중간에 전송을 끄고 충돌 방지 시스템을 실행하여 채널 낭비를 줄인다.