12주차: Link) MAP

multiple access protocol:

두종류의 링크:

• Point to Point: Ethernet switch와 host간의 1ㄷ1 매칭
• Broadcast: old-fashiond Ethernet, upstream HFC, wireless LAN (bus 같은거)

위 사진에서는 한 링크를 여러 장치가 공유해서 사용하고 있다.

collision:한 링크에 여러 신호를 동시에 전송하게 되면 신호 간에 간섭이 발생함.

 

Multiple access protocol:

    distributed algorithm: 노드가 채널을 어떻게 나눠서 가질 지 결정하는 방법. (충돌 방지 등)

    즉, 언제 노드가 전송할 지 결정하는 알고리즘이다.

 

-Ideal Multiple access protocol:

가정: Rbps의 대역폭을 가진 broadcast channel

1. 하나의 노드가 사용할 땐 R 속도로 보냄

2. M개의 노드가 원할땐 R/M 속도로 보냄

3. 분산 시스템: 중앙집중식으로 하면 제어노드가 필요하고 제어노드가 문제가 생기면 전부 먹통이 된다. (no sync, 제어 노드)

4. 간단해야함.

---

MAC protocol: taxonomy

-3가지 방식의 broad class:

1. 채널 나눠쓰기 (partition):

• 시분할, 주파수분할, 코드 분할
• 하나의 노드가 채널을 독점하는 방식 (사용하지 않을 때 효율이 떨어짐)

2. random access

• 나누지 않음 (충돌을 허용함)
• 충돌시 발생하는 문제를 해결해야함.

3. taking turns

• 노드간 순서를 정해서 보냄 (turn은 사용량에 따라 길이가 다르게 할당 됨)

-TDMA(Time Division MAC Protocols):

노드별로 채널을 사용할 수 있는 시간을 할당함.

본인에게 할당된 시간에 노드가 채널을 사용하지 않으면 효율이 떨어짐.

*위 사진에선 2,5,6 노드가 사용하지 않아 전체 채널 사용량은 1/2

 

-FDMA(Frequency Division Multiple Access):

노드별로 주파수를 나누어 할당함.

각 노드는 할당받은 주파수 대역을 언제든지 사용할 수 있음.

노드가 주파수 대역을 독점하는 형태라 사용하지 않는 만큼 사용량이 떨어짐. (위 사진에서 사용량은 1/2)

주파수에 파형을 어떻게 싣는지 설명하는데 전자과 내용이라 몬 알아듣겠다.

셤에 안나올거 같지만 일단 사진은 넣어둔다.

 

-Code Division Access Protocol:

같은 시간대에 같은 대역폭을 쓰지만 이를 코드로 송수신한다.

Walsh Code를 사용하고 orthogonal기법으로 나의 코드가 아니면 전부 0으로 

 

-Random Access Protocol:

특정 노드가 데이터를 보낼 때 채널의 최대 속도인 R rate로 보냄.

제어 노드 없음

두개이상의  노드가 보낼 시 collision 발생:

• collision 감지 어케함?
• 어케 복구함?

random access mac protocol의 예시:

• slotted ALOHA
• ALOHA
• CSMA, CSMA/CD, CSMA/CA

 

-slotted ALOHA:

Frame 크기는 전부 같음

시간을 동일한 time slot 으로 나눈다.

노드들은 slot 단위로만 신호를 보내려고 시도한다.

전송시:

• 노드들은 동기화되어 slot의 시작점을 알고 있다.
• 둘 이상의 노드가 같은 slot에 신호를 보내면, 모든 노드는 collision을 감지한다.
• 만약 collision이 발생하였다면 한 슬롯 쉬고 성공할 때까지 재전송한다.

장점:

    single node일 경우 full rate로 보낼 수 있다.

    분산화 되어 있다.

    간단하다

단점:

    충돌시 슬롯이 낭비된다.

    idle 슬롯이 생긴다. (사용되지 않는)

    clock sync를 맞춰야한다.

 

*최대 37% 의 efficiency

 

-Pure ALOHA:

위 방식에서 슬롯을 없앰.

더 간단함 (no snycronization)

전송시:

• 전송할 프레임이 생기면 바로 전송한다.
• 다른 프레임과 겹치게 되면 collision이 발생한다.

t0에서 보낸 frame은 [t0-1, t0+1] 시간에 보내진 다른 패킷과 충돌이 발생한다.

 

*최대 18% 의 efficiency

 

-CSMA(carrier sense multiple access):

데이터를 보내기 전에 채널 상에 데이터를 보내고 있는 노드가 있는지 확인한다. (LBT: Listen Before Talk)

carrier: 채널 상에 나타나는 신호

carrier sense: carrier를 통해 신호가 존재하는지를 감지하는 것.

*CSMA는 collision의 가능성을 줄일 수는 있지만, 완전히 방지할 수는 없다.

 

A노드에서 전송한 frame이 B노드에 도달해야 감지 할 수 있는데,

도달 전에 B노드가 frame을 전송하면 충돌이 발생한다.

 

-CSMA/CD(collision detection):

CSMA의 충돌 상황을 보자.

A노드에서 전송한 frame이 B노드에 도달하기 전에 B노드는 전송을 시작하였다.

B노드의 전송 중 A노드에서 frame을 보내고 있다는 것을 감지하면 B노드는 전송을 중단한다.

*collision은 짧은 시간 내에 감지되고 이 방식을 적용하면 채널의 낭비를 줄일 수 있다.

 

wired LAN에서는 감지가 쉽지만 무선에서는 어렵다.

 

1. NIC(Network Interface Card)이 network layer에서 datagram을 받아 frame을 만든다.

2. NIC가 채널의 사용여부를 확인하고 idle일 경우에만 보낸다. (아니면 기다림)

3. 전체 frame을 아무런 문제 없이 보낸경우 NIC는 할 일 다 했다! 끝이다!

4. 만약 NIC가 frame을 보내는 도중에 다른 노드의 전송을 감지하면 전송을 중단하고 jam signal을 보낸다.

5. 중단 후 NIC은 binary(exponential) backoff을 수행한다.

 

binary exponential backoff:

m번 충돌 이후 {0, 1, 2, ... 2^m - 1} 숫자 중 랜덤하게 K를 선택하여 K*512 bit time 만큼 기다렸다가 다시 전송함.

충돌이 많이 발생할수록 backoff interval이 길어질 확률이 높아지지만 그만큼 충돌이 발생할 확률이 줄어든다.

 

두 노드간 propagation delay가 0에 가까워질수록 효율은 1에 수렴한다.

두 노드간 transmission rate가 높아질수록 효율은 1에 수렴한다.

*ALOHA보다 간단하고, 싸고, 분산되어있음

---

유선 네트워크에서의 예시:

DOCSIS(Data Over Cable Service Interface Spec)

 

40Mbps downstream: 채널로 single CMTS 전송을 보낸다.

30Mbps upstream: mulitple access이다. 모든 사용자가 time slot을 차지하려고 경쟁한다. 

*결론적으로 TDM, FDM, Random Access등 여러 기법이 쓰인다~

 

Taking turns MAC protocols:

channel partitioning:

    각 채널의 사용량이 많은 경우(high load) 유리하다.

    적은경우 그만큼 idle 채널이 발생한다.

random access:

    각 채널의 사용량이 적은 경우(high load) 유리하다.

    많은 경우

*둘의 장점을 조합한게 taking turns이다.

 

Polling 방식:

master를  마스터 노드가 순서를 지정해 주는 방식이다.

장점: 구현이 간단하고 충돌이 발생하지 않으며 낭비가 되는 채널이 없다

단점: 순서를 지정하는 알고리즘의 오버헤드가 발생하고, 마스터 노드가 다운되면 전체 시스템이 다운된다.

 

Token passing:

각 노드들이 토큰을 순서대로 주고받는다.

현재 토큰을 가지고 있는 노드만이 데이터를 전송할 수 있다.

 

이 방식의 문제점은 토큰을 관리함에 있어 고려할 사항이 많아 구현이 어렵고,

내가 데이터를 보내야 함에도 다른 노드들을 거쳐 토큰이 다시 나에게 돌아올 때까지 기다려야 하는 latency가 발생한다는 점이 있다.

---