6. Link Layer and LANs (2)

6.3 Multiple Access Protocol

링크는 2가지 타입이 있다.

· 특정 링크를 독점적으로 사용하는 PPP(Point to Point)

· Ethernet이나 802.11 무선 랜 처럼 공유해서 사용하는 Broardcast

가 있다.

​

여러 사람이 링크를 공유할 때의 문제점은 동시에 링크를 사용할 때 충돌(Collision)이 발생한다는 점이다.

​

이 충돌을 피하기 위해서 등장한 것이 바로 multiple access protocol이다.

분산 알고리즘을 사용해서 어떻게 노드들이 채널을 공유할지를 결정한다.

​

그리고 컨트롤을 위해 추가 채널을 쓰는 것이 아닌 주어진 채널 만으로 multiple access를 하는 것이다.

​

R bps를 가지고 있는 링크가 있다고 해보자.

​

우리의 목표는

1. 만약 한명의 노드만 있으면 R bps로 보낼 수 있어야 한다(그 링크를 full로 다 썻으면 좋겠다라는 뜻).
2. M명의 노드가 있으면 각각 평균적으로 R/M의 전송 속도로 보낼 수 있어야 한다.(즉, 균등하게 나눠서 사용한다.)
3. 완전히 분산적이여야 한다. 즉, 전송을 조정하는 special node(=master node)가 없어야 하고, 클락이나 슬롯의 synchronization이 없어야 한다(즉, 나 보내고 싶을 때 보낼 수 있어야 한다).
4. 간단해야 한다.

​

공용된 채널에 다수의 사용자가 접속할 수 있도록 도와주는 정의한 프로토콜인MAC(Medium Access Control) Protocol이 등장했다.

​

위에서 설명한 저 desiderata를 만족하기 위해서 여러 방법을 사용해서 만들어봤더니, 이 MAC 프로토콜에는 3가지 그룹으로 나뉘어졌다.

​

· channel partitioning

채널을 쪼개서 사용하자.(시간별로 쪼개는 TDMA, 주파수 별로 쪼개는 FDMA, 사용자별로 고유의 코드를 부여해서 그 코드를 가진자만이 디코딩할 수 있는 CDMA 등이 이 방법이다.)

독점적으로 사용할 수 있도록 노드들에게 할당해준다.

​

· random access

쪼개지 말고 공유한다. 이때 발생하는 충돌은 허용하되, 효율적으로 극복해보자.

​

· "taking turns"

돌아가면서 보내는 방식. 단 공평하게 보내는 시간을 주는 것이 아닌 보내야할 데이터량이 많은 노드에게 더 많은 시간을 준다.

​

TDMA 말 그대로 시간 단위(round)로 쪼개서 multiple access를 하는 방식이다. 그림의 저 6개의 time slot frame이 하나의 round이고 저 하나의 round를 고정된 크기로 나눈 것이 time slot이다. 이 하나의 time slot을 하나에 station에게 할당한다. 위 그림처럼 만약에 1, 3, 4번이 보낼 패킷이 있으면 보내고 2, 5, 6번은 idle한 상태를 유지한다. (자원의 낭비가 좀 있다. 저 idle한 상태인 2, 5, 6번 time slot은 그냥 노는 것이기 때문)

​

그리고 주파수 별로 쪼개는 FDMA가 있다.

​

하나의 케이블(채널 스펙트럼)에 주파수 별로 나누어서 각 station에게 할당해주는 방법

TDMA와 마찬가지로 waste가 있다.

​

channel partitioning의 waste 문제를 해결하기 위해서 등장한 것이 랜덤 액세스 프로토콜(Random Access Protocol)이다.

​

랜덤 액세스 프로토콜은

1. 오직 하나의 노드만 보낼 패킷이 있다면 Bandwidth를 모두 할당받아서 R의 데이터 전송 속도를 가진다.

2. coordinate하는 노드가 없다.

​

2개 이상의 노드가 있어서 충돌이 발생해도 don't care한다. 대신 이 충돌을 빠르게 검출해서 recover하자.

​

slotted ALOHA, ALOHA, CSMA, CSMA/CD, CSMA/CA 등이 바로 random access protocol이다.

​

제일 먼저 slotted ALOHA를 알아보자.

​

먼저 몇가지 가정이 있는데,

먼저 모든 frame은 동일한 사이즈이고, 시간을 동일한 사이즈 슬롯으로 나눈다.

모든 노드는 오직 슬롯이 시작하는 그 순간에만 전송을 시작할 수 있다. 만약, 그 순간을 놓치면 다음 time slot이 시작하는 그 순간에 보낸다. 즉, 노드들이 synchronize되어있다.

collision이 발생할 수 있으므로 detection하는 능력이 있다.

​

그래서 network layer로부터 datagram을 받아서 frame으로 만든 다음, 다음 노드에게 이 frame을 전송하는데,

만약 충돌이 발생하지 않았다면 그냥 다음 time slot 때 다음 frame을 보낸다.

그런데 충돌이 일어나면 딜레이가 발생한다. 재전송(retransmit)을 해야하는데, 다음 time slot때 보낼지 말지를 P의 확률로 정해서 정한다.

​

예시를 통해 알아보자.

먼저 첫번째 slot 에서 node1, 2, 3이 모두 frame을 전송해서 충돌이 발생했다. 그리고 다음 slot에서는 모두 delay가 일어나서 아무도 패킷을 전송하지 않았다. 3번째 slot에서는 3번은 보내지 않고 1번과 2번이 동시에 보내서 또다시 충돌이 일어났다. 4번째 slot에서는 2번만 보내서 패킷 전송에 성공했다.

이러한 방식으로 랜덤하게 전송을 해서 성공하면 그냥 보내고, 충돌이 발생하면 랜덤으로 다시 보내서 성공할 때까지 재전송을 하는 것이다.

​

slotted ALOHA의 장점

· 만약 다른 노드는 전송을 하지않고 나만 전송했다면, 내가 그 채널을 full로 사용할 수 있다.

· 매우 분산적이다 : slot 타이밍에만 동기화될 필요가 있다.

· 심플하다

​

slotted ALOHA의 단점

· 충돌이 발생할 수 있고, 충돌났을 때의 slot은 모두 waste가 된다.

· idle한 슬롯이 발생할 수 있다(slot이 Empty일 수 있음).

· clock synchronization을 맞춰줘야함

​

​

다음은 Pure ALOHA에 대해서 알아보자.

​

이 ALOHA 프로토콜의 특징은 좀더 심플하고, synchronization을 없앴다는 점이다. 즉, slot이 시작하는 지점을 맞출 필요 없이 언제나 보낼 수 있다.

​

대신에 내가 frame을 보내는 동안 누군가가 frame을 전송하면 바로 충돌이 일어난다.

​

그래서 Pure ALOHA는 synchronization이 없어서 언제든지 내가 보내고 싶을 때 보낼 수 있다는 장점은 있지만 Efficiency는 slotted ALOHA보다 더욱 떨어진다.

​

ALOHA들보다 효율성을 높이기 위해서 등장한 것이 CSMA(Carrier Sense Multiple Access)이다.

​

CSMA는 전송하기 전에 listen하는 방식이다. 즉, 채널 상태를 계속 감지하면서 채널이 busy한지 idle한지를 체크하는 것이다. idle한 상태이면 보내고, busy한 상태이면 delay한다.

그런데 CSMA에서도 collision은 발생한다. 왜냐하면 idle한 상태라는 것을 감지하고 2명 이상의 node가 전송하면 충돌이 발생할 수 있기 때문.

​

예를 들어, 위 그림처럼 2번째 노드가 딱 보냈는데, 4번째 노드가 감지하는 메시지를 보내고 idle한 상태라는 신호를 받을 때까지 딜레이가 조금 있으므로 4번째 노드는 idle이라고 판단하고 보내버렸다가 충돌이 발생하게 된다.

​

그럴 경우 저 색칠된 부분은 모두 waste가 된다.

​

CSMA는 충돌이 발생해도 그냥 다 보내버렸는데, 충돌이 발생하면 전송을 중단시켜서 낭비를 좀 막아보자는 취지로 CSMA/CD(Collision Detection)이 등장했다.

​

그런데 이 CSMA/CD도 문제가 있는데,

유선 LAN의 경우에는 신호가 강해서 괜찮지만, 무선 LAN의 경우 잡음이 좀 심해서 신호가 좀 약해서 detection이 잘 안된다;;.

​

CSMA/CD 알고리즘을 알아보자.

사실 1~4는 우리가 이제 안다.

1. NIC가 datagram을 받으면 frame으로 만든다.
2. 채널이 idle한지 busy한지 감지한다.
3. 성공적으로 잘 보내면 굳
4. 충돌이 발생하면 즉시 전송을 중단한다.
5. 중단하고 delay를 해야하는데, 어느 정도 delay할지가 이제 관건이다. 방법은 binary (exponential) backoff 방법을 사용한다. 즉, m번째 충돌이 난다면, {0~2m-1}중에서 하나를 뽑아서 그 값에 512bit를 곱한 시간만큼 딜레이시킨다. 즉, 1번노드가 2*512bit 타임을, 2번노드가 16*512bit타임을 기다리게 해서 충돌을 회피한다. 이 방법을 충돌이 일어나지 않을때까지 반복한다.

​

그래서 CSMA/CD의 Efficiency는 propagation delay가 0으로 가고 transmission time이 무한대로 갈때, 즉, 링크를 full로 사용할 때 efficiency가 1이 된다.

​

정리를 조금 해보자면

​

channel partitioning MAC protocol은

high load일 때, efficiency와 fairness를 보장해줄 수 있다(채널을 분할해서 나만 쓰니까).

그런데 low load일때는 다른 노드들은 모두 전송을 안하는데, 나만 보낼때 효율성이 떡락을 해버린다.

​

random access MAC protocol은

low load일 때, 링크를 full로 사용할 수 있다는 장점이 있지만, high load일때는 충돌 때문에 효율성이 떡락한다.

​

이 중간점을 찾기위해서 등장한 것이 take turns MAC protocol이다.

​

Take turns MAC protocol 중 하나인 polling을 먼저 알아보자.

​

이 방법은 master node와 slave node가 있어서 master node가 slave node들에게 polling 즉, 송신 요구의 유무를 문의를 해서 slave node가 보낼 패킷이 있으면 master에게 보내는 방식이다. slave node들은 master node에게 polling을 받을 때까지 데이터를 송신하지 않는다.

​

이 방법의 장점은 충돌이 없고, slot도 waste되지 않는다는 장점이 있지만,

polling overhead가 있고, 느리고, master node에 문제가 발생하면 시스템이 붕괴된다.

​

다음은 token passing 프로토콜이다.

이 방법은 토큰이 순차적으로 돌면서, 이 토큰을 받은 노드가 보낼 데이터가 있으면 전송하고, 보낼 데이터가 없으면 토큰을 다음 노드에게 전달하는 메커니즘이다.

​

이 방법도 token overhead가 있고, 느리고, 어느 한 구역에서 토큰을 보내는 데 문제가 발생하면 시스템이 붕괴된다.

​