CH6 : Data Link Layer (2)

* 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. *

 

MAC Sublayer

---

IEEE 표준에서 데이터 링크 레이어는 두개의 레이어로 나뉜다.

IP주소를 담당하는 LLC와 MAC주소를 담당하는 MAC레이어 두개로 나뉘게 된다.

우리가 살펴볼 레이어는 MAC레이어이다.

MAC레이어 에서는 현재 나에개 할당된 bandwidth를 여러 사용자에게 어떻게 할당해줄지에 대한 스케쥴링을 담당한다.

(LTE네트워크나 5G네트워크에서도 MAC레이어에서 이 스케쥴링을 담당한다.)

 

MAC레이어에는 여러가지의 프로토콜들이 있다.

뒤에서 차차 알아볼 것이다.

 

가장 이상적인 RATE분배는 모두에게 최대한 공평하게 나누어주는 것이다.

R rate만큼을 가지고 있으면 M개의 노드에 대하여 R/M만큼의 rate를 제공해주는 것이 가장 공평하다.

 

그러나 네트워크 상황에는 많은 변수가 있고, 항상 공평하게 나누어주기엔 무리가 따른다.

 

이글에서는 MAC레이어에서 어떻게 node들에게 자원을 할당하는가에 대해 다룰 것이다.

 

MAC Protocols

---

MAC 프로토콜은 크게 세가지 분류로 나누고, 그 안에서 여러 종류의 방법이 있다.

 

1. Channel Partitioning

채널을 하나의 조각으로 나누어 분배하는 방식이다. 이때 조각은 시간, 주파수, 코드에 따라 나눌 수 있다.

시간에 따라 나누면 TDMA

주파수에 따라 나누면 FDMA

코드에 따라 나누면 CDMA이다.

 

TDMA와 FDMA는 많이 다루었으므로 넘어가고, 처음보는 CDMA에 대해서 다루어보겠다.

 

CDMA(Code Division Multiple Access)

무선 브로드캐스트에서 주로 쓰이는 방법이다. (위성 등)

각 사용자에게 "code"를 할당하여 보낼 데이터에 곱해 보내는 방식이다.

 

이때 어떤 두 사용자의 코드의 곱은 항상 0이어야 한다. 이를 orthogonal하다고 한다.

때문에 다음과 같은 식이 성립한다.

모든 i와 다른 j들에 대하여 ci * cj는 0이므로 결국 j와 i가 같을때 (cj * ci = 1) di만 나오는 방식이다.

예제를 보며 이해해보자.

어떤 사용자 m에게 아래와 같은 코드가 할당되었다고 가정해보자.

sender는 자신이 보낼 데이터에 자신이 할당받은 코드를 곱해 보내주고, receiver는 받은 데이터에 해당 사용자의 코드를 다시 곱해 디코딩하는 방식이다. 지금은 사용자가 한명이기 때문에 굳이 이런 방식을 사용할 필요가 없지만 사용자가 두명 이상이 되게 되면 얘기가 달라진다.

 

아래 예시를 살펴보자.

사용자1과 사용자2에게 각각 다른 코드가 주어졌다. 이때 이 두 코드는 곱해서 무조건 0이 되어야 한다.

사용자1과 사용자2는 모두 각각 자신이 보낼 데이터에 자신의 코드를 곱했고 그 최종 데이터를 모두 더해 recevier에게 보냈다. 해당 데이터를 받은 receiver는 거기에 원하는 사용자의 코드를 곱해 해당 사용자가 보낸 데이터만을 정확히 복원할 수 있다. (이 부분 때문에 모든 코드는 서로 곱해서 0이 되어야 함)

 

2. Random Access Protocol

MAC레이어는 자신에게 할당된 R rate를 랜덤하게 사용자를 지정해 전체 rate를 주는 방식이다.

full channel을 한명에게 몰빵해주기 때문에 여러 노드가 연결되어있는 상태에서 충돌이 발생할 수 있다.

 

때문에 random access MAC protocol에서는 이런 충돌을 어떻게 detect하고 recover할지가 중요한 화두이다.

Random Access Protocol에는 많은 종류가 있다.

 

- Slotted ALOHA

모든 프레임은 같은 사이즈를 갖는다.

똑같은 사이즈의 slot으로 시간이 나누어지는 개념이다. 때문에 노드들은 동기화가 되어있다.

노드들은 정해진 slot의 시간에만 전송할 수 있고, 두개 이상의 노드들이 하나의 slot에서 전송하면 collision으로 간주한다.

이때 collision이 났다고 detect가 되면 노드는 각자의 확률로 데이터를 보낼지 말지 판단한다.

예를 보며 이해해보자.

첫번째 slot에서 1,2,3모두가 데이터를 전송하려다보니 충돌이 발생했다.

때문에 1,2,3,은 각각 자신의 확률로 데이터를 다시 전송할지 안할지 판단하는데

두번째 slot에서는 모두가 보내지 않기로 결정한 것이다.

다시 세번째 slot에서는 1과 2만 보내기로 결정했고 다시 충돌이 발생하고 계속 이어지는 그림이다.

 

아이디어도 간단하고 성능도 나쁘지 않지만 slot을 나눠 node들을 모두 동기화 시켜야한다는 단점이 있다.

 

- Pure ALOHA (unslotted)

위의 방식과 같은데 slot으로 구분하지 않는 것이다.

node들은 아무때나 데이터를 전송할 수 있고, 만약 어떤 노드가 데이터를 보내는 와중에 누군가가 데이터를 보낸다면 충돌로 간주한다.

위와 같이 노란색노드가 데이터를 보낼때 충돌이 안나기 위해선 [t0, t0+1]동안은 아무도 데이터를 보내면 안된다.

slotted ALOHA보다 성능은 떨어지지만 모든 노드들을 동기화시키지 않아도 된다는 장점이 있다.

 

Pure ALOHA의 성능을 수학적으로 계산해 비교했는데, 너무 어려워서 그냥 그림만 올리겠다. poisson 과정에 대해 공부해야 이해할 것 같다.

최종적으로 두 방식(pure, slotted)을 비교하면 다음과 같은 그래프가 나온다.

위에서 말했듯이 성능은 slotted ALOHA가 압도적으로 좋지만 모든 노드를 동기화시키기는 너무 어려워서 그냥 pure방식을 쓴다고 한다.

 

ALOHA방식의 과정을 나타내면 아래와 같다. 천천히 따라가보며 이해해보자 꼭

이때 RTT동안 기다리는 부분이 있는데 이부분이 바로 충돌이 일어났는지 아닌지 확인하는 부분이다 (보냈다가 ACK을 받아봐야 알기 때문)

또한 Increment가 너무 크면 abort하는 부분이 있는데 만약 충돌이 계속 감지되어 주구장창 재전송을 기다릴 수만은 없으니 일정 횟수이상 충돌이 감지되면 그냥 보내기를 포기한다는 뜻이다.

 

 

- CSMA(Carrier Sense Multiple Access)

위 두 방식에 대한 불만으로 CSMA라는 방식이 나왔다.

기존 ALOHA방식에서는 일단 무지성으로 보내보고 충돌이 발생하면 처리를 하는 방식이었다.

 

CSMA는 무지성이 아니다! carrier를 보내 망의 상태를 체크한 후 현재 아무도 쓰고 있지 않다면 보내는 방식이다. 

하긴 뭐 사람 둘이 대화할 때 누가 얘기하고 있으면 말 안하는게 예의니까.. ALHOA가 무지성인건 맞다.

 

CSMA의 방식은 persistent와 non-persistent로 나뉜다.

 

1. persistent : 지속적으로 채널의 상태를 확인한다. 그리고 idle인 상태를 포착하면 그때 channel을 사용한다.
이 방식은 다시 두개로 나뉜다. 1-persistent vs p-persistent

1-persistent는 prob를 즉시 무조건 보내는 것이다. 즉 channel의 상태가 idle인것을 찾을 때까지 계속계속계속 확인한다.

p-persistnet는 prob를 p만큼의 확률로 보낸다. 즉 p에 대해 prob를 보내고 (1-p)에 대해선 보내지 않는다.

 

2. non-persistent : 즉시 보내지 않고 랜덤한 시간동안 기다린 후 prob를 보내는 방식이다. 

 

CSMA의 과정을 보면 다음과 같다. 잘 이해하고 따라가보자 꼭

 

지금 까지 알아본 방식, 그리고 p-persistent에서 p를 바꿔가며 성능을 측정하면 다음과 같다.

절대적인 지표라고는 할 수 없지만 어느정도 성능을 대변해준다.

 

그렇다면 CSMA에서는 무조건 충돌이 발생하지 않는 것인가?

아니다. 충돌이 발생할 수 있다.

아니 왜? channel의 상태를 확인하고 쓰는 것인데 어떻게 충돌이 나는가?

 

바로 propagation delay가 범인이다. 아래 예제를 보자.

2번 node가 channel이 빈것을 확인하고 자신의 데이터를 보내기 위해 망을 사용하고 있다. 하지만 propagation delay가 존재하기 때문에 해당 링크의 모든 부분에 동시에 이 상황을 알릴 수가 없다. 

이 신호가 4번 node까지 미처 도달하지 못했을 때, 4번노드가 channel의 상태를 확인하면 idle로 인식이 될 것이다.

때문에 4번도 해당 채널을 사용하게 되고, 그렇게 되면 체크무늬부분의 데이터가 서로 엉키게 된다.

 

- CSMA/CD (Collision Detection)

때문에 이 방식이 등장했다. 

위의 방식에서 충돌을 감지하게 된다면 어차피 체크무늬 부분은 오류가 발생하기 때문에 보내지 않고 (Collision detection)그만두는 것이다.

 

기본적으로 충돌을 감지하는 방법은 어떤 한 부분에서 양쪽에서 신호가와서 신호가 급격히 증가하면 충돌이 났음을 인지할 수 있다. 그러나 이 방법은 유선에서는 쉽지만 무선에서는 거의 불가능하다.

때문에 CSMA/CD방식은 유선에서 사용하고 무선에서는 사용할 수 없다. 

(무선에서는 CSMA/CA 방식을 사용하는데 이는 다음글에서 알아보겠다.)

 

위와 같이 A는 t4에서 충돌이 났음을 인지하고, C는 t3에서 충돌이 났음을 인지하여 서로 각각의 시간에서 전송을 중단하는 것이다.

 

충돌을 정확히 어떤식으로 판별할까?

channel이 idle하다고 판단한 node는 데이터를 보낸 후 계속 망을 체크한다. 그리고 망에서 특정 신호세기가 매우 커지게 되면 충돌이 났다고 인지하는 것이다.

 

그렇다면 어떤 노드는 데이터를 보낸 후 얼마의 시간동안 망을 체크하고 있어야 할까?

RTT이다.

극단적인 상황에서 B는 A가 보낸 데이터를 보기 직전에 망이 IDLE하다고 판단하여 데이터를 보낸다. 그렇게 B가 보낸 데이터를 A가 알기까지는 위의 예제에서 (worst case) 2*propagation delay라고 할 수 있다.

 

3. Taking Turns

이 방식은 위에서 언급해던 channel을 partitioning하는 방식과 random access하는 방식을 혼합한 것이다.

현재 세계에서 가장많이 쓰고있는 방식이다.

 

- Polling

하나의 master node를 두고 그 밑에 slave node들을 둔다. 

slave들은 master와 통신을 한다.

 

1. Master -> Slave

master는 데이터를 보낼 slave에게 현재 데이터를 받을 수 있는 상황인지 물어보고, ACK이 오면 그때 데이터를 보낸다. 때문에 충돌이 일어날일은 없다.

2. Slave -> Master

master는 지속적으로 slave들에게 자신에게 보낼 데이터가 있냐고 물어본다. (polling) 그리고 slave는 없다면 NAK을, 있다면 데이터를 보낸다.

Polling방식은 충돌이 날 일이 없지만 polling을 하는 과정에서 많은 overhead가 발생한다. 

근데 그냥 딱봐도 안전한 무지성이라고 보면 된다. (브루트포스같은..)

 

- Token passing

MAC은 node들에게 token을 나누어준다. 그리고 token을 가지고 있는 node들만 channel을 사용할 수 있는 구조이다.

마치 OS에서 token scheduling과 같다.

 

그러나 보내는 token또한 패킷이고 그 token packet이 loss가 날경우 대참사로 이어질 수 있다는 단점이 있다.

이 방식에는 크게 두가지 프로토콜이 있다.

 

1. Token Ring Protocol (delayed release)

 

모든 노드는 자신에게 token이 존재할 때만 channel을 사용한다. 

token이 있다는 것은 token bit로 확인한다.

 

모든 노드들은 한방향으로 계속 통신하며, 자신에게 할당된 token_bit가 1일때 비로소 channel을 사용할 수 있는 것이다.

그렇다면 노드들은 계속 어떤식으로 통신하고 있을까?

 

보낼 데이터, token bit 그리고 ACE bit를 사용한다. (Address recongized, Frame copied, Error detected)

token을 받은 A는 token bit를 1로 하고, 보낼 데이터를 붙여 B에게 보낸다.

데이터에서 현재 token은 1이므로 B는 token을 얻지 못하고, 만약 데이터에서 나타내는 주소와 자신의 주소가 같으면 A를 1로, 그리고 자신에게 현재 데이터를 복사한 후 C를 1로 만약 Error가 존재했다면 E를 1로하여 C에게 보낸다.

 

계속돌다보면 A에게 다시 돌아올텐데, A는 token, ACE bit를 통해 에러가 있었는지 확인하고, token을 release한다.

토큰을 release하는 방식에는 delayed와 early가 있는데, 위의 방식이 delayed이다. (자신에게 돌아와야 token release)

 

early release방식은 데이터를 보낸 후에 바로 token을 해제하는 것이다.

보통 빠른 rate에선 early release를 사용하고, 반대에선 delayed release를 사용한다고 한다.

 

2. Token Bus

물리적으로는 일직선 상으로 연결되어 있지만 논리적으로는 ring을 이룬다고 생각하고 있는 것이다.

각 노드들은 linked list로 연결이 되어 하나가 추가되어도 중간에 끼워넣을 수 있다.